Geographic Routing

Existing geographic routing algorithms work as follows: they first try to forward packets greedily, i.e., to the immediate neighbor that is closest in geographic distance to the destination. When a packet reaches a dead end, they switch to a forwarding mode that guarantees packet delivery. There are two existing techniques to guarantee packet delivery:

1. Face Routing. The idea is to route the packet around voids in the routing topology by forwarding it along a face of the planarized network graph. This technique was first proposed by Kranakis et al. and called Compass Routing II. Variants of face routing that have been proposed include GPSR/GPG, GOAFR+, and GPVFR.

2. Hull Tree Routing. Instead of maintaining information of a planarized version of the network connectivity graph, nodes instead maintain information of the network in the form of a hull tree. A hull tree is a spanning tree where each node maintains information about the points that can be reached below it in the tree. Algorithms that employ this technique includes the GDSTR-family of algortihms.

While geographic routing was originally proposed in order to achieve stateless routing, it has since become clear that the reason why the original algorithms (GPG/GPSR) seemed stateless was due to the assumptions that the network satisfied the unit disk graph assumption and that the locations of nodes were known. In general, real wireless networks do not satisfy the unit disk graph assumption and the locations of nodes, even if known, are not always accurate. Under such conditions, it turns out that the correct planarization of the network connectivity graph is a hard problem.

The planarization problem was effectively solved by Kim et al. with the Cross Link Detection Protocol (CLDP). Unfortunately, it turns out that the amount of network generated by CLDP turns out to be relatvively large and thus efforts were then turned to achieving geographic routing without resort to planarization (or face routing). Greedy Distributed Spanning Tree Routing (GDSTR) was developed as a result of these efforts.

Greedy Distributed Spanning Tree Routing (GDSTR)

GDSTR is a geographic routing algorithm that uses a spanning tree as the backup routing topology instead of a planar graph like the geographic face routing algorithms. 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.

Greedy Embedding Spring Coordinates (GSpring)

GSpring is a new virtual coordinate assignment algorithm that derives good coordinates for geographic routing of non-location-aware wireless nodes. Starting from a set of initial coordinates derived from a set of elected perimeter nodes, GSpring uses a modified spring relaxation algorithm that incrementally adjusts virtual coordinates to increase the convexity of voids in the virtual routing topology. This reduces the probability of packets ending up in dead ends during greedy forwarding and improves the routing performance of existing geographic routing algorithms.

$Date: 2008/01/01 06:35:12 $