Research Abstracts - 2006

Path Vector Face Routing: Geographic Routing with Local Face Information

Ben Leong, Sayan Mitra & Barbara Liskov

Introduction

With the development of wireless ad hoc networks like roofnets and sensornets, there has been a proliferation of geographic routing algorithms [1-6]. These algorithms are more scalable compared to traditional routing algorithms because they require O(1) storage per node, as opposed to O(N) storage, where N is the number of reachable destinations.

Most existing geographic routing algorithms first attempt to forward packets greedily; each node forwards packets to a neighboring node that is closest to the destination. When greedy forwarding causes a packet to be trapped at local minimum, the packet is forwarded by traversing a face of a planarized graph (also known as perimeter forwarding). Existing geographic routing algorithms can guarantee packet delivery only if the network connectivity graph can be planarized without disconnecting the network. The distributed planarization of a real radio network was once a major challenge because traditional planarization algorithms relied on idealized radio models, but recent work showed that planarization can be achieved in practical radio networks [7].

As a node knows only about its immediate neighbors, there is often insufficient information for it to make a good decision on the forwarding direction when a packet gets trapped in a local minimum and has to switch to perimeter forwarding. To deal with this problem, a node usually has to resort to an arbitrary choice, e.g., use the right-hand rule as in Greedy Perimeter Stateless Routing (GPSR) [6]. But this choice may be the wrong one, and the penalty for making a wrong decision may be very high. Most schemes just choose deterministically [2,6]; Greedy Other Adaptive Face Routing (GOAFR+) [3-5] deals with the problem by bounding the search in each direction within an expanding ellipse, thus avoiding the full consequences of a wrong choice.

In this work, we have made both theoretical and practical contributions to the understanding of geographic routing. The theoretical contributions of our work are as follows:

• We show that there exists an oblivious (memoryless) algorithm, Oblivious Path Vector Face Routing (OPVFR), that can guarantee packet delivery for any planar graph if nodes have complete face information;
• Bose et al. had shown earlier that deterministic oblivious routing cannot guarantee packet delivery for arbitrary planar graphs where nodes are only aware of the positions of their one-hop neighbors [8]. We extend this result by showing the impossibility of oblivious routing in planar graphs where nodes are limited to knowing about nodes up to k-hops away, for any finite k.

Since some planar faces can be extremely large in practice, the assumption that nodes can maintain complete face information is sometimes impractical and we augment these theoretical findings with the following practical contributions:

• We present a practical asynchronous distributed algorithm, Path Vector Exchange (PVEX), that propagates and maintains local face information efficiently as well as reacts to network membership changes;
• We propose a non-oblivious algorithm, Greedy Path Vector Face Routing} (GPVFR), that guarantees packet delivery even when nodes do not have complete face information;

Through extensive simulations we evaluate the performance of GPVFR and show that it achieves significantly better routing performance in terms of both path stretch and hop stretch than GPSR and somewhat better performance than GOAFR+ for random networks with only a small amount of additional routing state at each node.

Approach

We explore a different way of tackling the problem of dead ends during geographic routing, by using more information about the planar graph. Our expectation was that having more information would lower the routing cost and lead to an algorithm with better routing performance in terms of both path and hop stretch and we show experimentally via simulation that this is in fact the case.

Like other algorithms, nodes periodically broadcast beacons to inform neighboring nodes of their position and face information. On receiving beacons from its neighbors in the planarized graph, a node extracts the relevant information required to deduce the path vectors for its faces.

Under GPVFR, packets are first routed in Greedy mode. When greedy forwarding to an immediate neighbor fails, a node may find that it knows of another node along its planar faces that is nearer to the destination than itself. Then, the node will apply the OPVFR algorithm to choose a target node, creating ``virtual edges'' for faces with incomplete information if necessary. Once a target node is chosen, it is recorded in the packet and the packet is switched to OPVFR mode and forwarded toward the target node. It is possible that this target node may be replaced by another if one that is nearer to the destination than the recorded target node is found while the packet is forwarded in OPVFR mode. OPVFR forwarding is like greedy forwarding except that nodes have a longer horizon, and packets are restricted to forwarding on the planar faces (edges). If there are multiple paths to the target node n*, the choice can be made based on any performance metric that is monotonic along a path.

Under both Greedy and OPVFR modes, a packet may end up at a node that does not know of any other nodes that is closer to the destination than itself, even including those along the planar faces. If so, we resort to Face Routing [1]. The node forwards the packet along the edges of the planar face that contains the imaginary line from the node to the destination. The choice of the direction to traverse the face is made based on the currently known set of path vectors instead of using an arbitrary right-hand rule like GPSR.

When greedy forwarding works, it is usually the most efficient forwarding strategy, so we want to revert to greedy mode from OPVFR and Perimeter modes as soon as possible. In fact, we do so as soon as we find a neighboring node that is closer to the destination than the node recorded in the packet.

Our algorithm is efficient: it requires little bandwidth to propagate the extra information and only a constant amount of extra storage at each node. Yet it outperforms GPSR substantially, and even does better than GOAFR+, which to our knowledge is the most efficient geographic routing algorithm previously available. Like existing algorithms, we assume in our work that even though network connectivity may change, the planarized graph is quasi-static.

Progress

This work was published at the 13th IEEE International Conference on Network Protocols (ICNP 2005) [9].

Conclusion

We demonstrate that by storing a small amount of local face information at each node, we can achieve better routing performance in terms of reduced path and hop stretch. The extra storage helps because the local face information can be exploited by a greedy-face forwarding mode using the available face information where regular greedy-neighbor forwarding fails to avoid switching to the costly perimeter forwarding mode. Also, where nodes have no choice but switch to perimeter forwarding, this extra information can marginally improve the probability of picking a good forwarding direction.

We make two main contributions: (i) we have shown that while it is possible to guarantee packet delivery with an oblivious algorithm in a network where nodes have full face information, it is impossible to do so when nodes are limited to knowing about nodes up to a fixed number of hops away on each face; and (ii) we developed Greedy Path Vector Face Routing (GPVFR), a non-oblivious algorithm that guarantees delivery even when nodes do not have complete face information. Through extensive simulations we have shown that GPVFR achieves significantly better routing performance in terms of both path stretch and hop stretch than GPSR and somewhat better performance than GOAFR+ with only a small additional amount of routing state at each node.

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] 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.

[8] 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.

[9] 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.