|
 ABSTRACT
For many years, scalable routing for wireless communication systems was a compelling but elusive goal. Recently, several routing algorithms that exploit geographic information (e.g. GPSR) have been proposed to achieve this goal. These algorithms refer to nodes by their location, not address, and use those coordinates to route greedily, when possible, towards the destination. However, there are many situations where location information is not available at the nodes, and so geographic methods cannot be used. In this paper we define a scalable coordinate-based routing algorithm that does not rely on location information, and thus can be used in a wide variety of ad hoc and sensornet environments.
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
|
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]
|
| |
2
|
Nicklas Beijar Networking. Zone Routing Protocol (ZRP). citeseer.nj.nec.com/538611.html
|
| |
3
|
|
| |
4
|
Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States
[doi> 10.1145/288235.288256]
|
| |
5
|
Douglas S. J. De Couto and Robert Morris, Location Proxies and Intermediate Node Forwarding for Practical Geographic Forwarding, MIT Laboratory for Computer Science technical report MIT-LCS-TR-824, June 2001.
|
| |
6
|
Gregory G. Finn. Routing and addressing problems in large metropolitan-scale intemetworks. ISi/RR-87-180, ISI, March 1987.
|
| |
7
|
Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA
[doi> 10.1145/501422.501424]
|
| |
8
|
John Heidemann , Fabio Silva , Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , Deepak Ganesan, Building efficient wireless sensor networks with low-level naming, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
|
| |
9
|
T. Imielinski and J. Navas. GPS-Based Addressing and Routing RFC nnnn, Computer Science, Rutgers University, March 1996. citeseer.nj.nec.com/33074.html
|
| |
10
|
Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States
[doi> 10.1145/345910.345920]
|
| |
11
|
Per Johansson , Tony Larsson , Nicklas Hedman , Bartosz Mielczarek , Mikael Degermark, Scenario-based performance analysis of routing protocols for mobile ad-hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.195-206, August 15-19, 1999, Seattle, Washington, United States
[doi> 10.1145/313451.313535]
|
| |
12
|
|
| |
13
|
David B. Johnson and David A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz Imielinski and Hank Korth, Chapter 5, pages 153--181, Kluwer Academic Publishers, 1996.
|
| |
14
|
David B. Johnson. Scalable and Robust Internetwork Routing for Mobile Hosts. In Proceedings of the 14th International Conference on Distributed Computing Systems, pages 2--11, IEEE Computer Society, Poznan, Poland, June 1994.
|
| |
15
|
|
| |
16
|
|
| |
17
|
|
| |
18
|
|
| |
19
|
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]
|
| |
20
|
Wen-Hwa Liao and Jang-Ping Sheu and Yu-Chee Tseng. GRID: A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks", In Telecommunication Systems, Volume 18, pages 37--60, 2001.
|
| |
21
|
Nathan Linial, Laszlo Lovasz, Avi Wigderson. Rubber bands, convex embeddings and graph connectivity. In Combinatorica, 8(1): 91-102 (1988).
|
| |
22
|
|
| |
23
|
|
| |
24
|
S. Shenker, S. Ratnasamy, B. Karp, R. Govindan, and D. Estrin, Data-centric Storage in Sensornets, In ACM SIGCOMM HotNets\/, Jul. 2002.
|
| |
25
|
Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA
[doi> 10.1145/570738.570750]
|
| |
26
|
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
[doi> 10.1145/872035.872044]
|
| |
27
|
|
| |
28
|
|
| |
29
|
Yi Shang , Wheeler Ruml , Ying Zhang , Markus P. J. Fromherz, Localization from mere connectivity, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA
[doi> 10.1145/778415.778439]
|
| |
30
|
Y. Yu, D. Estrin, and R. Govindan. Geographical and Energy-Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks. UCLA Computer Science Department Technical Report, UCLA-CSD TR-01-0023, May 2001.
|
CITED BY 95
|
|
|
|
|
|
|
|
David Kiyoshi Goldenberg , Jie Lin , A. Stephen Morse , Brad E. Rosen , Y. Richard Yang, Towards mobility as a network control primitive, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
|
|
|
|
|
|
|
|
|
Hsing-Jung Huang , Ting-Hao Chang , Shu-Yu Hu , Polly Huang, Magnetic diffusion: disseminating mission-critical data for dynamic sensor networks, Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 10-13, 2005, Montréal, Quebec, Canada
|
|
|
|
|
|
|
|
|
Fang Bian , Ramesh Govindan , Scott Schenker , Xin Li, Using hierarchical location names for scalable routing and rendezvous in wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA
|
|
|
Thomas Moscibroda , Regina O'Dell , Mirjam Wattenhofer , Roger Wattenhofer, Virtual coordinates for ad hoc and sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jeong-Hun Shin , Jaesub Kim , Keuntae Park , Daeyeon Park, Railroad: virtual infrastructure for data dissemination in wireless sensor networks, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Primoz Skraba , Qing Fang , An Nguyen , Leonidas Guibas, Sweeps over wireless sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA
|
|
|
Farid Benbadis , Jeremie Leguay , Vincent Borrel , Marcelo Amorim , Timur Friedman, Millipede: a rollerblade positioning system, Proceedings of the 1st international workshop on Wireless network testbeds, experimental evaluation & characterization, September 29-29, 2006, Los Angeles, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Simon Dobson , Spyros Denazis , Antonio Fernández , Dominique Gaïti , Erol Gelenbe , Fabio Massacci , Paddy Nixon , Fabrice Saffre , Nikita Schmidt , Franco Zambonelli, A survey of autonomic communications, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.1 n.2, p.223-259, December 2006
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Paolo Baronti , Prashant Pillai , Vince W. C. Chook , Stefano Chessa , Alberto Gotta , Y. Fun Hu, Wireless sensor networks: A survey on the state of the art and the 802.15.4 and ZigBee standards, Computer Communications, v.30 n.7, p.1655-1695, May, 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Franck Rousseau , Yan Grunenberger , Vincent Untz , Eryk Schiller , Paul Starzetz , Fabrice Theoleyre , Martin Heusse , Olivier Alphand , Andrzej Duda, An architecture for seamless mobility in spontaneous wireless mesh networks, Proceedings of first ACM/IEEE international workshop on Mobility in the evolving internet architecture, August 27-30, 2007, Kyoto, Japan
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
David Chu , Lucian Popa , Arsalan Tavakoli , Joseph M. Hellerstein , Philip Levis , Scott Shenker , Ion Stoica, The design and implementation of a declarative sensor network system, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia
|
|
|
Lucian Popa , Afshin Rostamizadeh , Richard Karp , Christos Papadimitriou , Ion Stoica, Balancing traffic load in wireless networks with curveball routing, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada
|
|
|
L. Galluccio , A. Leonardi , G. Morabito , S. Palazzo, MACRO+: a network coding driven integrated MAC/routing protocol for multihop wireless networks, Proceedings of the 1st international conference on MOBILe Wireless MiddleWARE, Operating Systems, and Applications, February 13-15, 2008, Innsbruck, Austria
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thomas Watteyne , Isabelle Augé-Blum , Mischa Dohler , Stéphane Ubéda , Dominique Barthel, Centroid virtual coordinates - A novel near-shortest path routing paradigm, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.10, p.1697-1711, July, 2009
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2