NSDI '06 — Abstract
Pp. 339–352 of the Proceedings
Geographic Routing Without Planarization
Ben Leong, Barbara Liskov, and Robert Morris, MIT Computer Science and Artificial Intelligence Laboratory
Abstract
We present a new geographic routing algorithm, Greedy Distributed
Spanning Tree Routing (GDSTR), that finds shorter routes and
generates less maintenance traffic than previous algorithms. While
geographic routing potentially scales well, it faces the problem of
what to do at local dead ends where greedy forwarding fails. Existing
geographic routing algorithms handle dead ends by planarizing the node
connectivity graph and then using the right-hand rule to route around
the resulting faces.
GDSTR handles this situation differently by switching instead to
routing on a spanning tree until it reaches a point where greedy
forwarding can again make progress. In order to choose a direction on
the tree that is most likely to make progress towards the destination,
each GDSTR node maintains a summary of the area covered by the subtree
below each of its tree neighbors. While GDSTR requires only one tree
for correctness, it uses two for robustness and to give it an
additional forwarding choice.
Our simulations show that GDSTR finds shorter routes than geographic
face routing algorithms: GDSTR's stretch is up to 20% less than the
best existing algorithm in situations where dead ends are common. In
addition, we show that GDSTR requires an order of magnitude less
bandwidth to maintain its trees than CLDP, the only distributed
planarization algorithm that is known to work with practical radio
networks.
- View the full text of this paper in HTML and PDF. Listen to the presentation in MP3 format.
Until May 2007, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2006 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
