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

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

doi:10.1109/INFCOM.2011.5935240

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 proceeding › Conference 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 Möbius transformation. We employ an optimization routine to look for the Mö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 language	English
Title of host publication	INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China
Pages	621-625
Number of pages	5
DOIs	https://doi.org/10.1109/INFCOM.2011.5935240
Publication status	Published - 2011

Access to Document

10.1109/INFCOM.2011.5935240

Yu Ban ET AL 2011 Spherical Representation and Polyhedron Routing for Load Balancing in Wireless Sensor NetworksAccepted author manuscript, 16.1 MB

http://dx.doi.org/10.1109/INFCOM.2011.5935240

Cite this

Yu, X., Ban, X., Zeng, W., Sarkar, R., Gu, X., & Gao, J. (2011). Spherical representation and polyhedron routing for load balancing in wireless sensor networks. In INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China (pp. 621-625) https://doi.org/10.1109/INFCOM.2011.5935240

@inproceedings{2ff7d8adeaf547498d3323fe841a7d14,

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{\"o}bius transformation. We employ an optimization routine to look for the M{\"o}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.",

author = "Xiaokang Yu and Xiaomeng Ban and Wei Zeng and Rik Sarkar and Xianfeng Gu and Jie Gao",

year = "2011",

doi = "10.1109/INFCOM.2011.5935240",

language = "English",

isbn = "978-1-4244-9919-9",

pages = "621--625",

booktitle = "INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China",

}

Yu, X, Ban, X, Zeng, W, Sarkar, R, Gu, X & Gao, J 2011, Spherical representation and polyhedron routing for load balancing in wireless sensor networks. in INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China. pp. 621-625. https://doi.org/10.1109/INFCOM.2011.5935240

Spherical representation and polyhedron routing for load balancing in wireless sensor networks. / Yu, Xiaokang; Ban, Xiaomeng; Zeng, Wei et al.
INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China. 2011. p. 621-625.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Yu, Xiaokang

AU - Ban, Xiaomeng

AU - Zeng, Wei

AU - Sarkar, Rik

AU - Gu, Xianfeng

AU - Gao, Jie

PY - 2011

Y1 - 2011

N2 - 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 Möbius transformation. We employ an optimization routine to look for the Mö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.

AB - 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 Möbius transformation. We employ an optimization routine to look for the Mö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.

U2 - 10.1109/INFCOM.2011.5935240

DO - 10.1109/INFCOM.2011.5935240

M3 - Conference contribution

SN - 978-1-4244-9919-9

SP - 621

EP - 625

BT - INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China

ER -

Yu X, Ban X, Zeng W, Sarkar R, Gu X, Gao J. Spherical representation and polyhedron routing for load balancing in wireless sensor networks. In INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China. 2011. p. 621-625 doi: 10.1109/INFCOM.2011.5935240

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

Abstract / Description of output

Access to Document

Fingerprint

Cite this