Bounded stretch geographic homotopic routing in sensor networks

Kan Huang, Chien-Chun Ni, Rik Sarkar, Jie Gao, Joseph S. B. Mitchell

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Homotopic routing asks for a path going around holes according to a given “threading”. Paths of different homo-topy types can be used to improve load balancing and routing resilience. We propose the first lightweight homotopic routing scheme that generates constant bounded stretch compared to the shortest path of the same homotopy type. Our main insight is that in a sequence of triangles to traverse, a message always routed to the nearest point on the next triangle in the sequence travels at most a constant times the length of any shortest path going through the same sequence of triangles. Our routing scheme operates on two levels enabled by a coarse triangulation. The top level is used to specify and represent the requested homotopy type, while the bottom level executes the local greedy routing on a triangle sequence. After a preprocessing step that triangulates the given region and creates a minimum-size auxiliary structure, routing operates greedily at two different resolutions. We also present simulation analysis in a variety of settings and show that the paths indeed have small stretch in practice, considerably shorter than the bounds guaranteed by the theory.
Original languageEnglish
Title of host publication2014 IEEE Conference on Computer Communications
Subtitle of host publicationINFOCOM 2014, Toronto, Canada, April 27 - May 2, 2014
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages9
Publication statusPublished - 2014


Dive into the research topics of 'Bounded stretch geographic homotopic routing in sensor networks'. Together they form a unique fingerprint.

Cite this