Geometric spanners for routing in mobile networks

被引：75
作者：
Gao, J [1 ]
Guibas, LJ
Hershberger, J
Zhang, L
Zhu, A
机构：
[1] CALTECH, Ctr Math Informat, Pasadena, CA 91125 USA
[2] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA
[3] Mentor Graph Corp, Wilsonville, OR 97070 USA
[4] Compaq Syst Res Ctr, Palo Alto, CA USA
来源：
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS | 2005年 / 23卷 / 01期
关键词：
geographical routing; spanners; wireless ad hoc networks;
D O I：
10.1109/JSAC.2004.837364
中图分类号：
TM [电工技术]; TN [电子技术、通信技术];
学科分类号：
0808 ; 0809 ;
摘要：
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.
引用
收藏
页码：174 / 185
页数：12
相关论文
共 26 条
[11]  
Eppstein D, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P425, DOI 10.1016/B978-044482537-7/50010-3
[12]   Discrete mobile Centers [J].
Gao, J ;
Guibas, LJ ;
Hershberger, J ;
Zhang, L ;
Zhu, A .
DISCRETE & COMPUTATIONAL GEOMETRY, 2003, 30 (01) :45-63
[13]  
GAO J, 2003, P 35 ANN ACM S THEOR, P483
[14]  
HERSHBERGER J, 2003, P ACM S COMP GEOM, P48
[15]   Geographical routing using partial information for wireless ad hoc networks [J].
Jain, R ;
Puri, A ;
Sengupta, R .
IEEE PERSONAL COMMUNICATIONS, 2001, 8 (01) :48-57
[16]  
Karp B., 2000, P O ACM IEEE INT C M, P2343
[17]  
KEIL JM, 1989, LECT NOTES COMPUT SC, V382, P47
[18]  
Kuhn Fabian, 2002, PROC 6 INT WORKSHOP, P24
[19]  
Li J., 2000, P OFIEEEACM MOBICOM, P120130, DOI DOI 10.1145/345910.345931
[20]  
Li XY, 2002, IEEE INFOCOM SER, P1268, DOI 10.1109/INFCOM.2002.1019377
123