Ananth Rao
Sylvia Ratnasamy
Scott Shenker
Ion Stoica
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.
- S. Basagni, I. Chlamtac, V. Syrotiuk, and B. Woodward, "A distance routing effect algorithm for mobility (DREAM)," in Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, MobiCom '98, (Dallas, Texas), August 1998. Google Scholar
Digital Library
- Nicklas Beijar Networking. Zone Routing Protocol (ZRP). citeseer.nj.nec.com/538611.htmlGoogle Scholar
- Prosenjit Bose and Pat Morin and Ivan Stojmenovic and Jorge Urrutia. Routing with Guaranteed Delivery in Ad Hoc Wireless Networks, In Wireless Networks, Vol. 7, pages 609 -- 616, 2001. citeseer.nj.nec.com/bose00routing.html Google ScholarDigital Library
- Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. In Proceedings of the Fourth Annual International Conference on Mobile Computing and Networking (MobiCom'98), ACM, Dallas, TX, October 1998. Google ScholarDigital Library
- 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.Google Scholar
- Gregory G. Finn. Routing and addressing problems in large metropolitan-scale intemetworks. ISi/RR-87-180, ISI, March 1987.Google ScholarCross Ref
- J. Gao, L. J. Guibas, J. Hershburger, L. Zhang, A. Zhu, "Geometric Spanner for Routing in Mobile Networks ", In Proceedings of the 2nd ACM", In Proceedings of the 2nd ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2001), pages 45--55, October 2001. Google ScholarDigital Library
- J. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan, Building efficient wireless sensor networks with low-level naming, In Proceedings of the Symposium on Operating Systems Principles, pages 146--159, Banff, Alberta, Canada, Oct. 2001. Google ScholarDigital Library
- T. Imielinski and J. Navas. GPS-Based Addressing and Routing RFC nnnn, Computer Science, Rutgers University, March 1996. citeseer.nj.nec.com/33074.htmlGoogle Scholar
- C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom 2000), 2000. Google ScholarDigital Library
- Per Johansson and Tony Larsson and Nicklas Hedman and Bartosz Mielczarek and Mikael Degermark. Scenario-based performance analysis of routing protocols for mobile ad-hoc networks, In Proceedings of the fifth annual ACM/IEEE International Conference on Mobile computing and Networking, pages 195 -- 206, Seattle, Washington, 1999. ACM Press. Google ScholarDigital Library
- David B. Johnson, David A. Maltz, and Josh Broch. DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks. in Ad Hoc Networking, edited by Charles E. Perkins, Chapter 5, pages 139--172, Addison-Wesley, 2001. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- Charles Perkins and Pravin Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, in Proceedings of ACM SIGCOMM'94 Conference on Communications Architectures, Protocols and Applications, 1994, pages 234--244. Google ScholarDigital Library
- B. Karp. Geographic Routing for Wireless Networks. Ph.D. Dissertation, Division of Engingeering and Applied Sciences, Harvard University, 2000. Google ScholarDigital Library
- B. Karp and H. Kung. Greedy Perimeter Stateless Routing. In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom 2000), 2000. Google ScholarDigital Library
- Young-Bae Ko and Nitin H. Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks In Mobile Computing and Networking, pages 66--75, 1998. Google ScholarDigital Library
- Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger, and Robert Morris, A Scalable Location Service for Geographic Ad Hoc Routing, ACM Mobicom 2000. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Nathan Linial, Laszlo Lovasz, Avi Wigderson. Rubber bands, convex embeddings and graph connectivity. In Combinatorica, 8(1): 91-102 (1988).Google ScholarCross Ref
- Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks. OSDI, 2002. Google ScholarDigital Library
- Charles E. Perkins and Elizabeth M. Royer. "Ad hoc On-Demand Distance Vector Routing." Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pages 90--100. Google ScholarDigital Library
- S. Shenker, S. Ratnasamy, B. Karp, R. Govindan, and D. Estrin, Data-centric Storage in Sensornets, In ACM SIGCOMM HotNets\/, Jul. 2002.Google Scholar
- S. Ratnasamy, B. Karp, D. Estrin, R. Govindan, and S. Shenker. GHT: A Geographic Hash-Table for Data-Centric Storage in SensorNets. Under submission to the First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA) (June 2002). Google ScholarDigital Library
- Fabian Kuhn, Roger Wattenhofer, Yan Zhang and Aaron Zollinger, "Geometric Ad-Hoc Routing: Of Theory and Practice," in Principles of Distibuted Computing, 2003. Google ScholarDigital Library
- Prosenjit Bose, Pat Morin, Ivan Stojmenovic, and Jorge Urrutia, "Routing with Guaranteed Delivery in Ad-Hoc Wireless Networks," ACM Wireless Networks, November 2001. Google ScholarDigital Library
- "Graph Drawing: Algorithms for the Vizualization of Graphs," Ioannis Tollis, Giuseppe Di Battista, Peter Eades (Editor), Loannis Tollis, Prentice Hall, 1998. Google ScholarDigital Library
- Yi Shang, Wheeler Ruml, Ying Zhang, Markus Fromherz, "Localization from Mere Connectivity," in The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2003. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Geographic routing without location information
Recommendations
A scalable location service for geographic ad hoc routing
MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networkingGLS is a new distributed location service which tracks mobile node locations. GLS combined with geographic forwarding allows the construction of ad hoc mobile networks that scale to a larger number of nodes than possible with previous work. GLS is ...
A Geographic Unicast Routing Algorithm Using no Location Service
NCA '10: Proceedings of the 2010 Ninth IEEE International Symposium on Network Computing and ApplicationsIn this paper, we present a geographic routing algorithm which can adapt to different levels of mobility by changing its parameters according to the network in which it is running. Routing decisions are based on directions and geographical positions of ...
Minimizing recovery state In geographic ad-hoc routing
MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computingGeographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes ...
Comments