Distributed computation of virtual coordinates for greedy routing in sensor networks

作者：Ben Chen Mirela; Gortler Steven J; Gotsman Craig^*; Wormser Camille

来源：Discrete Applied Mathematics, 2011, 159(7): 544-560.

DOI：10.1016/j.dam.2010.10.016

• Sensor network
• Routing
• Graph embedding

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.

• 出版日期2011-4-6
• 单位INRIA