Spherical representation and polyhedron routing for load balancing in wireless sensor networks

Xiaokang Yu, Xiaomeng Ban, Wei Zeng, Rik Sarkar, Xianfeng Gu, Jie Gao

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

Abstract / Description of output

In this paper we address the problem of scalable and load balanced routing for wireless sensor networks. Motivated by the analog of the continuous setting that geodesic routing on a sphere gives perfect load balancing, we embed sensor nodes on a convex polyhedron in 3D and use greedy routing to deliver messages between any pair of nodes with guaranteed success. This embedding is known to exist by the Koebe-Andreev-Thurston Theorem for any 3-connected planar graphs. In our paper we use discrete Ricci flow to develop a distributed algorithm to compute this embedding. Further, such an embedding is not unique and differs from one another by a Möbius transformation. We employ an optimization routine to look for the Möbius transformation such that the nodes are spread on the polyhedron as uniformly as possible. We evaluated the load balancing property of this greedy routing scheme and showed favorable comparison with previous schemes.
Original languageEnglish
Title of host publicationINFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China
Number of pages5
Publication statusPublished - 2011


Dive into the research topics of 'Spherical representation and polyhedron routing for load balancing in wireless sensor networks'. Together they form a unique fingerprint.

Cite this