Lazy cross-link removal for geographic routing

ABSTRACT

Geographic techniques promise highly scalable any-to-any routing in wireless sensor networks. In one thread of research on geographic routing, researchers have explored robust, distributed graph planarization. Arguing that such planarization techniques have high overhead, researchers have more recently pursued a thread in which they propose precomputation of routing structures (e.g., hull trees and grids) to achieve low-overhead geographic routing.In this paper we introduce a third approach, LCR, that does not involve any precomputation of distributed routing structures, nor full a priori planarization. Instead, LCR removes non-planarities lazily only when they interfere with correct geographic routing. Lazy removal of link crossings results in an order of magnitude or more lower overhead than any previously proposed approach.

REFERENCES

• 1: 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]
• 2: Jehoshua Bruck , Jie Gao , Anxiao (Andrew) Jiang, MAP: medial axis based geometric routing in sensor networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080839]
• 3: FANG, Q., GAO, J., GUIBAS, L.J., DE SILVA, V., AND ZHANG, L. GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks. In Proc. IEEE Infocom (2005).
• 4: FINN, G. Routing and addressing problems in large metropolitan-scale internetworks. Tech. Rep. ISI/RR-87-180, USC/Information Sciences Institute, Mar. 1987.
• 5: FONSECA, R., RATNASAMY, S., ZHAO, J., EE, C., CULLER, D., SHENKER, S., AND STOICA, I. Beacon Vector Routing: Scalable Point-to-point Routing in Wireless Sensor Networks. In Proc. USENIX Symposium on Networked Systems Design and Implementation (Boston, MA, April 2005).
• 6: GABRIEL, K., AND SOKAL, R. A new statistical approach to geographic variation analysis. Systematic Zoology 18 (1969), 259--278.
• 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: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 9: Brad Nelson Karp , H. T. Kung, Geographic routing for wireless networks, 2000
• 10: KARP, B. Challenges in geographic routing: Sparse networks, obstacles, and traffic provisioning. Presentation at the DIMACS Workshop on Pervasive Networking, May 2001.
• 11: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 12: KIM, D., AND MAXEMCHUK, N. Simple Robotic Routing in Ad-Hoc Networks. In Proc. IEEE International Conference on Network Protocols (2004).
• 13: KIM, Y.J., GOVINDAN, R., KARP, B., AND SHENKER, S. Geographic Routing Made Practical. In Proc. USENIX Symposium on Networked Systems Design and Implementation (Boston, MA, April 2005).
• 14: Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, On the pitfalls of geographic face routing, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080818]
• 15: KLEINROCK, L., AND TAKAGI, H. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Comm. 32, 3 (1984), 246--257.
• 16: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 17: 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]
• 18: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 19: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 20: 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]
• 21: LIANG, B., LISKOV, B., AND MORRIS, R. Geographic Routing without Planarization. In Proc. USENIX Symposium on Networked Systems Design and Implementation (April 2006).
• 22: James Newsome , Dawn Song, GEM: graph eMbedding for routing and data-centric storage in sensor networks without geographic information, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958501]
• 23: 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 [doi>10.1145/938985.938996]
• 24: 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]
• 25: Karim Seada , Ahmed Helmy , Ramesh Govindan, On the effect of localization errors on geographic face routing in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984633]
• 26: TOUSSAINT, G. The relative neighborhood graph of a finite planar set. Pattern Recognition 12, 4 (1980), 261--268.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Reliability

Keywords:
cross-link detection, geographic routing, planarization