.png){kind=icon}
.png){kind=icon}
Return
Distributed and Compact Routing Using Spatial Distributions in Wireless Sensor Networks
.png){kind=icon}
PRE
AI
DOI：10.1145/2480730.2480735.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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(log(2) n) strategically selected nodes that serve as intermediate destinations. These nodes are selected with probability proportional to 1/r(rho), where r is the distance to u and rho 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 + epsilon 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 + epsilon stretch routing with high probability, with an average routing table size of O(root n log(2) 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.
Keywords:
Algorithms
Design
Theory
Sensor networks
small stretch routing
spatial distribution
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.7
Papers:
995
Citations:
2.0K
Organization
View more organizations