J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, A. Zhu, Geometric Spanner for Routing in Mobile Networks, Proc. of the 2nd ACM Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc'01), 45-55, October 2001.

Abstract:

We propose 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: (1) it is a planar graph; (2) 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 (3) the graph can be maintained efficiently in a distributed manner when the nodes move around. Furthermore, each node only needs constant time to make routing decisions. We also show by simulation that the RDG outperforms the previously proposed routing graphs under the Greedy Perimeter Stateless Routing (GPSR) protocol. In addition, we investigate theoretical bounds on the quality of paths discovered using GPSR.

Bibtex: 

@inproceedings{gghzz-gsrmn-01 ,
    author = "Jie Gao and Leonidas J. Guibas and John Hershberger and Li Zhang and An Zhu",
    title="Geometric Spanner for Routing in Mobile Networks",
    booktitle="Proceedings of the 2nd {ACM} Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'01)",
    pages="45-55",
    year=2001
}