Theory and Practice of Geographic Routing

Geographic routing algorithms use position information for making packet forwarding decisions. Unlike topological routing algorithms, they do not need to exchange and maintain routing information and work nearly stateless. This makes geographic routing attractive for wireless ad hoc and sensor networks. Most geographic routing algorithms use a greedy strategy that tries to approach the destination in each step, e.g. by selecting the neighbor closest to the destination as a next hop. However, greedy forwarding fails in local minimum situations, i.e. when reaching a node that is closer to the destination than all its neighbors. A widely adopted approach to recover from such situations is planar graph routing, which guides the packet around the local minimum and guarantees delivery, required that a planar subgraph of the network graph can be constructed. A combination of greedy forwarding with a recovery mechanism is still the state-of-the-art in geographic routing, and many algorithms have been developed that follow this scheme. This chapter gives an overview of the fundamentals of geographic routing as well as theoretical results and new developments towards practical applicability.