Geometric Spanner for Routing in Mobile Networks

This paper proposes a new routing graph, the Restricted Delaunay Graph (RDG), for ad hoc networks. Combined with a node clustering algorithm, RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive properties; it is a planar graph; between any two nodes there exists a path in the RDG whose length, whether measure in terms of topological or Euclidean distance, is only a constant times the optimum length possible; and the graph can be maintained efficiently in a distributed manner when the nodes move around. The paper also shows by simulation that the RDG outperforms the previously proposed routing graphs under the Greedy Perimeter Stateless Routing (GPSR) protocol.