TY - GEN
T1 - Bounded stretch geographic homotopic routing in sensor networks
AU - Huang, Kan
AU - Ni, Chien Chun
AU - Sarkar, Rjk
AU - Gao, Jie
AU - Mitchell, Joseph S.B.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84904438526
U2 - 10.1109/INFOCOM.2014.6848027
DO - 10.1109/INFOCOM.2014.6848027
M3 - Conference contribution
AN - SCOPUS:84904438526
SN - 9781479933600
T3 - Proceedings - IEEE INFOCOM
SP - 979
EP - 987
BT - IEEE INFOCOM 2014 - IEEE Conference on Computer Communications
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
Y2 - 27 April 2014 through 2 May 2014
ER -