Distributed computation of virtual coordinates for greedy routing in sensor networks

Mirela Ben Chen, Steven J. Gortler, Craig Gotsman, Camille Wormser

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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 protocolone 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.

Original languageEnglish (US)
Pages (from-to)544-560
Number of pages17
JournalDiscrete Applied Mathematics
Issue number7
StatePublished - Apr 6 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


  • Graph embedding
  • Routing
  • Sensor network


Dive into the research topics of 'Distributed computation of virtual coordinates for greedy routing in sensor networks'. Together they form a unique fingerprint.

Cite this