TY - GEN
T1 - Scalable routing in 3D high genus sensor networks using graph embedding
AU - Yu, Xiaokang
AU - Yin, Xiaotian
AU - Han, Wei
AU - Gao, Jie
AU - Gu, Xianfeng
PY - 2012
Y1 - 2012
N2 - We study scalable routing for a sensor network deployed in complicated 3D settings such as underground tunnels in gas system or water system. The nodes are in general 3D space but they are very sparsely located and the network has complex topology. We propose a routing scheme by first embdding the network on a surface with possibly non-zero genus. Then we compute a canonical hyperbolic metric of the embedded surface, and use geodesics to decompose the network into canonical components called pairs of 'pants' whose topology is simpler (with genus zero). The adjacency of the pants components is extracted as a high level routing map and stored at every node. With the hyperbolic metric one can use greedy routing to navigate within and across pants. Altogether this leads to a two-level routing scheme by first finding a sequence of pants and then realizing the route with greedy steps. We show by simulation that the number of pants is closely related to the true 'genus' of the network and that the routing scheme is efficient and scalable.
AB - We study scalable routing for a sensor network deployed in complicated 3D settings such as underground tunnels in gas system or water system. The nodes are in general 3D space but they are very sparsely located and the network has complex topology. We propose a routing scheme by first embdding the network on a surface with possibly non-zero genus. Then we compute a canonical hyperbolic metric of the embedded surface, and use geodesics to decompose the network into canonical components called pairs of 'pants' whose topology is simpler (with genus zero). The adjacency of the pants components is extracted as a high level routing map and stored at every node. With the hyperbolic metric one can use greedy routing to navigate within and across pants. Altogether this leads to a two-level routing scheme by first finding a sequence of pants and then realizing the route with greedy steps. We show by simulation that the number of pants is closely related to the true 'genus' of the network and that the routing scheme is efficient and scalable.
UR - http://www.scopus.com/inward/record.url?scp=84861585906&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861585906&partnerID=8YFLogxK
U2 - https://doi.org/10.1109/INFCOM.2012.6195678
DO - https://doi.org/10.1109/INFCOM.2012.6195678
M3 - Conference contribution
SN - 9781467307758
T3 - Proceedings - IEEE INFOCOM
SP - 2681
EP - 2685
BT - 2012 Proceedings IEEE INFOCOM, INFOCOM 2012
T2 - IEEE Conference on Computer Communications, INFOCOM 2012
Y2 - 25 March 2012 through 30 March 2012
ER -