Spatial Distribution in Routing Table Design for Sensor Networks

Rik Sarkar, Xianjin Zhu, Jie Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We propose a generic routing table design principle for scalable routing on networks with bounded geometric growth. Given an inaccurate distance oracle that estimates the graph distance of any two nodes with constant factor upper and lower bounds, we augment it by storing the routing paths of pairs of nodes, selected in a spatial distribution, and show that the routing table enables 1 + epsiv stretch routing. In the wireless ad hoc and sensor network scenario, the geographic locations of the nodes serve as such an inaccurate distance oracle. Each node p selects O (log n loglog n) other nodes from a distribution proportional to 1/r2 where r is the distance to p and the routing paths to these nodes are stored on the nodes along these paths in the network. The routing algorithm selects links conforming to a set of sufficient conditions and guarantees with high probability 1 + epsiv stretch routing with routing table size O(radicn log n loglog n) on average for each node. This scheme is favorable for its simplicity, generality and blindness to any global state. It is a good example that global routing properties emerge from purely distributed and uncoordinated routing table design.
Original languageEnglish
Title of host publicationINFOCOM 2009. 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 19-25 April 2009, Rio de Janeiro, Brazil
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages5
ISBN (Electronic)978-1-4244-3513-5
ISBN (Print)978-1-4244-3512-8
Publication statusPublished - 2009


Dive into the research topics of 'Spatial Distribution in Routing Table Design for Sensor Networks'. Together they form a unique fingerprint.

Cite this