Distributed and compact routing using spatial distributions in wireless sensor networks

Rik Sarkar, Xianjin Zhu, Jie Gao

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In traditional routing, the routing tables store shortest paths to all other destinations and have size linear in the size of the network, which is not scalable for resource-constrained networks such as wireless sensor networks. In this article we show that by storing selectively a much smaller set of routing paths in the routing tables one can get low-stretch, compact routing schemes.

Our routing scheme includes an approximate distance oracle with which one can obtain approximate shortest path length estimates to destinations. This distance oracle can be obtained, for example, by a landmark-based scheme, or in case of sensor networks, from the geographic distance between node locations. With an approximate distance oracle one can attempt greedy routing by forwarding to the neighbor whose estimate is closer to the destination. But there is no guarantee of delivery nor of the routing path length. We augment the distance oracle by storing, for each node u, routing paths to O(log2 n) strategically selected nodes that serve as intermediate destinations. These nodes are selected with probability proportional to 1/rρ, where r is the distance to u and ρ is a suitable constant for the network. Then we derive a set of sufficient conditions to select the next step at each stage of routing, such that these conditions can be verified locally and guarantee 1+ϵ stretch routing on any metric. These conditions serve as the “greedy routing” or local decision rule.

On graphs of bounded growth, our scheme guarantees 1+ϵ stretch routing with high probability, with an average routing table size of O(√n log2 n). This scheme is favorable for its simplicity, generality, and blindness to any global state. It demonstrates that global routing properties could emerge from purely distributed and uncoordinated routing table design.

Original languageEnglish
Article number32
Pages (from-to)32:1-32:20
Number of pages20
JournalACM Transactions on Sensor Networks
Issue number3
Publication statusPublished - 1 Jun 2013

Keywords / Materials (for Non-textual outputs)

  • Sensor networks
  • small stretch routing
  • spatial distribution


Dive into the research topics of 'Distributed and compact routing using spatial distributions in wireless sensor networks'. Together they form a unique fingerprint.

Cite this