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

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.