Title | ||
---|---|---|
Spherical representation and polyhedron routing for load balancing in wireless sensor networks |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1109/INFCOM.2011.5935240 | INFOCOM |
Keywords | Field | DocType |
geodesic routing,optimisation,optimization routine,message delivery,distributed algorithms,sensor nodes,koebe-andreev-thurston theorem,spherical representation,continuous setting,distributed algorithm,computational geometry,resource allocation,load balanced routing,load balancing property,möbius transformation,3-connected planar graphs,greedy algorithms,graph theory,wireless sensor networks,discrete ricci flow,polyhedron routing,telecommunication network routing,greedy routing scheme,convex polyhedron,face,wireless sensor network,planar graph,wireless network,load balance,wireless networks,optimization,three dimensional,routing | Load management,Mathematical optimization,Dynamic Source Routing,Load balancing (computing),Static routing,Computer science,Destination-Sequenced Distance Vector routing,Greedy algorithm,Wireless sensor network,Geographic routing,Distributed computing | Conference |
Volume | Issue | ISSN |
null | null | 0743-166X |
ISBN | Citations | PageRank |
978-1-4244-9919-9 | 6 | 0.44 |
References | Authors | |
18 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xiaokang Yu | 1 | 67 | 10.86 |
Xiaomeng Ban | 2 | 39 | 3.81 |
Wei Zeng | 3 | 75 | 3.80 |
Rik Sarkar | 4 | 393 | 22.38 |
Xianfeng Gu | 5 | 2997 | 189.71 |
Jie Gao | 6 | 2174 | 155.61 |