Scalable logical coordinates framework for routing in wireless sensor networks

ABSTRACT

In this article, we present logical coordinates based routing (LCR), a novel framework for scalable and location-independent routing in wireless sensor networks. LCR assigns each node a logical coordinate vector, and routes packets following these vectors. We demonstrate that LCR (i) guarantees packet delivery with a high probability, (ii) finds good paths, and (iii) exhibits robust performance in the presence of network voids and node failures. We systematically evaluate the performance of LCR through simulations and compare it with other state-of-the-art protocols. We also propose two extensions of LCR, one for three-dimensional node deployments and the other for unreliable wireless links.

REFERENCES

• 1: ARGO. http://www.argo.ucsd.edu/. Project argo website.
• 2: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 3: 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]
• 4: Bulusu, N., Heidemann, J., and Estrin, D. 2000. Gps-less low cost outdoor localization for very small devices. IEEE Pers. Comm. Mag. 7, 5 (Oct.), 28--34.
• 5: Qing Cao , Tarek Abdelzaher, A Scalable Logical Coordinates Framework for Routing in Wireless Sensor Networks, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.349-358, December 05-08, 2004 [doi>10.1109/REAL.2004.8]
• 6: Carzaniga, A., Rosenblum, D., and Wolf, A. 2000. Content-based addressing and routing: A general model and its application. Tech. Rep. CU-CS-902-00, Dept. of Computer Science, Univ. of Colorado, Sept.
• 7: Finn, G. March 1987. Routing and addressing problems in large metropolitan-scale internetworks. In Tech. Rep. Vol. ISI/RR-87-180. USC/ISI.
• 8: Fonseca, R., Ratnasamy, S., Zhao, J., Ee, C., Culler, D., Shenker, S., and Stoica, I. 2005. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In the 2nd Symposium on Networked Systems Design and Implementation. ACM Press.
• 9: GloMoSim. http://pcl.cs.ucla.edu/projects/glomosim/. Glomosim website.
• 10: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 11: Johnson, D. and Maltz, D. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, Imielinski and Korth, Eds. vol. 353. Kluwer Academic Publishers.
• 12: 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]
• 13: Kim, Y., Govindan, R., Karp, B., and Shenker, S. 2005. Geographic routing made practical. In Proceedings of the 2nd Symposium on Networked Systems Design and Implementation.
• 14: 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]
• 15: Nagpal, R. 1999. Organizing a global coordinate system from local information on an amorphous computer. In A.I. Memo 1666, MIT A.I. Laboratory.
• 16: 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]
• 17: Niculescu, D. and Nath, B. 2003a. Dv based positioning in ad hoc networks. In J. Telecomm. Syst. 22, 1--4 (Jan.), 267--280.
• 18: Dragos Niculescu , Badri Nath, Trajectory based forwarding and its applications, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939012]
• 19: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 20: 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]
• 21: 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]
• 22: Karim Seada , Marco Zuniga , Ahmed Helmy , Bhaskar Krishnamachari, Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031509]
• 23: 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]
• 24: Gilman Tolle , Joseph Polastre , Robert Szewczyk , David Culler , Neil Turner , Kevin Tu , Stephen Burgess , Todd Dawson , Phil Buonadonna , David Gay , Wei Hong, A macroscope in the redwoods, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098925]
• 25: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 26: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 27: Hu Zhou , Suresh Singh, Content based multicast (CBM) in ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 28: Zuniga, M. and Krishnamachari, B. 2004. Analyzing the transitional region in low power wireless links. In Proceedings of the 1st IEEE Conference on Sensor and Ad Hoc Communications and Networks (SECON).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Performance

Keywords:
Sensor network routing, logical coordinates, routing