Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420102 | Discrete Applied Mathematics | 2011 | 17 Pages |
Abstract
Sensor networks are emerging as a paradigm for future computing, but pose a number of challenges in the fields of networking and distributed computation. One challenge is to devise a greedy routing protocol—one that routes messages through the network using only information available at a node or its neighbors. Modeling the connectivity graph of a sensor network as a 3-connected planar graph, we describe how to compute on the network in a distributed and local manner a special geometric embedding of the graph. This embedding supports a geometric routing protocol called “greedy routing” based on the “virtual” coordinates of the nodes derived from the embedding.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mirela Ben Chen, Steven J. Gortler, Craig Gotsman, Camille Wormser,