Theory and Practice of Geographic Routing
Pp. 69-88 (20)
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.
Department of Computer Science, University of Freiburg, Germany