Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu, Geometric Spanner for Routing in Mobile Networks. IEEE Journal on Selected Areas in Communications Wireless Ad Hoc Networks (J-SAC), 23(1), pp. 174-185, January, 2005.

Abstract:

We propose a new routing graph, the restricted Delaunay graph (RDG), for mobile ad hoc networks. Combined with a node clustering algorithm, the RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive properties: 1) it is planar; 2) between any two graph nodes there exists a path whose length, whether measured in terms of topological or Euclidean distance, is only a constant times the minimum 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 show by simulation that the RDG outperforms previously proposed routing graphs in the context of the Greedy perimeter stateless routing (GPSR) protocol. Finally, we investigate theoretical bounds on the quality of paths discovered using GPSR.

Bibtex: 

@article{gao05geometric
    ,author = "Jie Gao and Leonidas J. Guibas and John Hershberger and Li Zhang and An Zhu"
    ,title = "Geometric Spanners for Routing in Mobile Networks"
    ,journal = "IEEE Journal on Selected Areas in Communications Special issue on Wireless Ad Hoc Networks"
    ,year = "2005"
    ,volume = "23"
    ,number = "1"
    ,pages = "174--185"
}