| Geometric spanner for routing in mobile networks |
| Full text |
 Pdf
(275 KB)
|
| Source
|
International Symposium on Mobile Ad Hoc Networking & Computing
archive
Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing
table of contents
Long Beach, CA, USA
Session: Routing and transport
table of contents
Pages: 45 - 55
Year of Publication: 2001
ISBN:1-58113-428-2
|
|
Authors
|
|
Jie Gao
|
Department of Computer Science, Stanford University, Stanford, CA
|
|
Leonidas J. Guibas
|
Department of Computer Science, Stanford University, Stanford, CA
|
|
John Hershberger
|
Mentor Graphics, 8005 S.W. Boeckman Road, Wilsonville, OR
|
|
Li Zhang
|
Compaq Systems Research Center, 130 Lytton Avenue, Palo Alto, CA
|
|
An Zhu
|
Department of Computer Science, Stanford University, Stanford, CA
|
|
| Sponsor |
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 5, Downloads (12 Months): 52, Citation Count: 50
|
|
|
 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 measured 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
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
A. D. Amis, R. Prakash, T. H. P. Vuong, and D. T. Huynh. Max-Min D-cluster formation in wireless ad hoc networks. In 19th IEEE INFOCOM, March 1999.
|
 |
2
|
Stefano Basagni , Imrich Chlamtac , Violet R. Syrotiuk , Barry A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.76-84, October 25-30, 1998, Dallas, Texas, United States
[doi> 10.1145/288235.288254]
|
| |
3
|
P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick. On the spanning ratio of gabriel graphs and B-skeleton submitted to SIAM Jounral onDiscrete Mathematics 2001.
|
| |
4
|
Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States
[doi> 10.1145/313239.313282]
|
| |
5
|
|
| |
6
|
C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla. Routing in clustered multihop, mobile wireless networks with fading channel. In Proc. IEEE SICON '97, pages 197-211, Apr 1997.
|
| |
7
|
B. Das and V. Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets. In IEEE International Conference on Communications (ICC'97), 1997.
|
| |
8
|
D. P. Dobkin, S. J. Friedman, and K. J. Supowit. Delaunay graphs are almost as good as complete graphs. In Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., pages 20-26, 1987.
|
| |
9
|
A. Ephremides, J. E. Wieselthier, and D. J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. of IEEE, 75(1):56-73, Jan 1987.
|
| |
10
|
D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 425-461. Elsevier Science Publishers B.V. North- Holland, Amsterdam, 2000.
|
| |
11
|
Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States
[doi> 10.1145/378583.378666]
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States
[doi> 10.1145/345910.345931]
|
| |
17
|
|
| |
18
|
|
| |
19
|
|
| |
20
|
V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. IEEE J. Selected Areas in Communications, 17(8):1333-1344, August 1999.
|
| |
21
|
E. M. Royer and C.-K. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications, 6(2):46-55, Apr 1999.
|
| |
22
|
R. Wattenhofer, L. Li, P. Bahl, and Y. M. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In Proc. IEEE Infocom, 2001.
|
| |
23
|
|
CITED BY 50
|
|
|
|
|
|
|
|
Christian Schindelhauer , Tamás Lukovszki , Stefan Rührup , Klaus Volbert, Worst case mobility in ad hoc networks, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ananth Rao , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
|
|
|
|
|
|
|
|
|
Guoliang Xing , Chenyang Lu , Robert Pless , Qingfeng Huang, On greedy geographic routing algorithms in sensing-covered networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
|
|
|
Wen-Zhan Song , Yu Wang , Xiang-Yang Li , Ophir Frieder, Localized algorithms for energy efficient topology in wireless ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
|
|
|
Gady Kozma , Zvi Lotker , Micha Sharir , Gideon Stupp, Geometrically aware communication in random wireless networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
|
|
|
|
|
|
Friedhelm Meyer auf de Heide , Christian Schindelhauer , Klaus Volbert , Matthias Grünewald, Energy, congestion and dilation in radio networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
|
|
|
|
|
|
Qing Fang , Jie Li , Leonidas Guiba , Feng Zha, RoamHBA: maintaining group connectivity in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kishore Kothapalli , Christian Scheideler , Melih Onus , Andrea Richa, Constant density spanners for wireless ad-hoc networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
G.2