Research Abstracts - 2006

Geographic Routing without Planarization

Ben Leong, Barbara Liskov & Robert Morris

Introduction

Geographic routing algorithms [1-8] are an attractive alternative to traditional ad hoc routing algorithms for wireless networks, because they scale better: the routing state maintained per node is dependent only on local network density and not network size [6,9]. Recently, geographic routing algorithms have also been proposed as a routing primitive for data-centric applications. Even when physical locations are not available, geographic routing can still be applied using virtual coordinates.

All previous proposed geographic routing algorithms are based on face routing [1], which guarantees packet delivery by routing on a planar subgraph of the network. It turns out that distributed planarization is difficult for real wireless networks and the problem was only solved recently by Kim et al. with the Cross-Link Detection Protocol (CLDP) [9]. However, CLDP is complex and somewhat costly, while face routing requires the handling of many subtle corner cases [10]. While practical distributed planarization is now a solved problem, the high maintenance costs and complexities associated with the deployment of face routing algorithms (with CLDP) make it worthwhile to consider an alternative approach to face routing.

We have developed a new geographic routing algorithm, the Greedy Distributed Spanning Tree Routing (GDSTR) algorithm, that does not require planarization. GDSTR is better than existing geographic face routing algorithms in the following respects:

• It requires significantly less maintenance bandwidth than CLDP;
• It achieves lower path and hop stretch than existing geographic face routing algorithms; and
• It is simpler and easier to understand and implement.

A simulation evaluation shows that GDSTR achieves a peak improvement of about 20% in terms of path and hop stretch over the best available geographic face routing algorithm in situations where dead ends are common, and that GDSTR performance is consistently good over a wide range of network densities and sizes.

Simulation also shows that GDSTR generates significantly less maintenance traffic than CLDP. GDSTR sends two orders of magnitude fewer messages to build its trees initially than what CLDP sends to construct a planar subgraph, and GDSTR's communication when maintaining existing trees is one order of magnitude less than CLDP.

Approach

Like existing geographic routing algorithms, we assume that nodes have assigned coordinates and that links are bi-directional. Unlike some previous work, we do not require that radio ranges be uniform and cover unit disks [2,6].

Geographic routing algorithms forward packets greedily whenever possible, by routing through a directly connected neighbor in the direction of the ultimate destination. When there is no such neighbor, face routing algorithms avoid the obstacle by forwarding around the faces of a planar subgraph of the network graph. GDSTR, in contrast, switches to forwarding along the edges of a spanning tree.

A common technique for achieving scalability in traditional networking is the aggregation of information about the address space. A key insight of our work is that GDSTR can apply the same principle to help it route along its spanning tree by aggregating the locations covered by subtrees using convex hulls. We call a tree annotated with convex hulls a hull tree.

A hull tree is a spanning tree where each node has an associated convex hull that contains within it the locations of all its descendant nodes in the tree. Hull trees provide a way of aggregating location information and they are built by aggregating convex hull information up the tree. This information is used in routing to avoid paths that will not be productive; instead we are able to traverse a significantly reduced subtree, consisting of only the nodes with convex hulls that contain the destination point.

GDSTR forwards packets using simple greedy forwarding whenever possible. It switches to forwarding based on a hull tree only to route packets around ``voids,'' and escape from a local minimum. It switches back to greedy forwarding as soon as it is feasible to do so.

GDSTR requires only one hull tree for correctness. However, we use a second tree because doing so provides better robustness in the event of node failures and an additional routing choice.

Progress

This work will be presented at the 3rd Symposium on Network Systems Design and Implementation (NSDI 2006) [11].

Conclusion

The key insight of our work is that for geographic routing, it is no less efficient to use two hull trees instead of a planar graph as the backup routing topology when greedy forwarding fails, and it is significantly easier to build and maintain trees rather than a planar graph. Our simulations have demonstrated that GDSTR requires an order of magnitude less maintenance bandwidth than CLDP, while achieving lower path and hop stretch than existing geographic face routing algorithms in networks of moderate size (less than 5,000 nodes).

GDSTR is immediately applicable to a large class of stationary wireless networks, e.g. roofnets and sensornets. While we have not explicitly evaluated the performance of GDSTR for mobile networks, our simulations show that GDSTR requires only a small number of packets to set up and repair its hull trees. This suggests that it is quite plausible that GDSTR will work well in a mobile setting with some tuning and optimization. It remains as future work to implement and evaluate GDSTR in a practical mobile environment.

Research Support

This research was supported by the National Science Foundation under Grant No. ANI-0082503.

References:

[1] Evangelos Kranakis, Harvinder Singh and Jorge Urrutia. Compass Routing on Geometric Networks Title of the paper. In The Proceedings of the 11th Canadian Conference on Computational Geometry, 1999.

[2] Prosenjit Bose, Pat Morin, Ivan Stojmenovic and Jorge Urrutia. Routing with Guaranteed Delivery in ad hoc Wireless Networks. In Wireless Networks, 2000.

[3] Fabian Kuhn, Roger Wattenhofer and Aaron Zollinger. Asymptotically Optimal Geometric Mobile Ad-Hoc Routing. In The Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications (Dial-M), 2002.

[4] Fabian Kuhn, Roger Wattenhofer, Yan Zhang and Aaron Zollinger. Geometric Ad-Hoc Routing: Of Theory and Practice. In The Proceedings of the 22nd ACM Int. Symposium on the Principles of Distributed Computing (PODC), 2003.

[5] Fabian Kuhn, Roger Wattenhofer and Aaron Zollinger. Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing. In The Proceedings of the 4th ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc), 2003.

[6] Brad Karp and H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In The Proceedings of the 6th annual international conference on Mobile computing and networking (Mobicom 2000), August 2000.

[7] Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz, Pat Morin and J. Ian Munro. Online Routing in Convex Subdivisions. In The Proceedings of the Proceedings of the International Symposium on Algorithms and Computation, 2000.

[8] Ben Leong, Sayan Mitra, and Barbara Liskov. Path Vector Face Routing: Geographic Routing with Local Face Information. In The Proceedings of the 13th IEEE International Conference on Network Protocols (ICNP 2005), Boston, MA, November 2005.

[9] Young-Jin Kim, Ramesh Govindan, Brad Karp and Scott Shenker. Geographic Routing Made Practical. In The Proceedings of the Proceedings of the 2nd Symposium on Network Systems Design and Implementation (NSDI 2005), May 2005.

[10] Young-Jin Kim, Ramesh Govindan, Brad Karp and Scott Shenker. On the Pitfalls of Geographic Face Routing. In The Proceedings of the Proceedings of the Third ACM/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIAL-M-POMC 2005), September 2005.

[11] Ben Leong, Barbara Liskov, and Robert Morris. Geographic Routing without Planarization. In The Proceedings of the 3rd Symposium on Network Systems Design and Implementation (NSDI 2006), San Jose, CA, May 2006.