Scalable routing in 3D high genus sensor networks using graph embedding

Xiaokang Yu, Xiaotian Yin, Wei Han, Jie Gao, Xianfeng Gu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 Scopus citations


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.

Original languageAmerican English
Title of host publication2012 Proceedings IEEE INFOCOM, INFOCOM 2012
Number of pages5
StatePublished - 2012
Externally publishedYes
EventIEEE Conference on Computer Communications, INFOCOM 2012 - Orlando, FL, United States
Duration: Mar 25 2012Mar 30 2012

Publication series

NameProceedings - IEEE INFOCOM


OtherIEEE Conference on Computer Communications, INFOCOM 2012
Country/TerritoryUnited States
CityOrlando, FL

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Scalable routing in 3D high genus sensor networks using graph embedding'. Together they form a unique fingerprint.

Cite this