Constructing virtual coordinate for routing in wireless sensor networks under unreliable links

ABSTRACT

Several works have shown that the virtual coordinate based routing protocol has better performances than the real coordinate when the network density is low. However, unit disk graph model is adopted in most of those works. Many recent experimental studies show that wireless links among low power radios are unreliable. This has severe impacts on the performances of the routing protocols. In [1], the virtual geographic information proposed adopts unit disk graph model. In this paper, three new simple and effective strategies that take the unreliable links into consideration are proposed for constructing virtual coordinate in wireless sensor networks. We simulate the greedy routing protocol which uses the virtual coordinate constructed by our proposed strategies under unreliable links. Simulation results show that the delivery ratio of our proposed strategies is higher than the delivery ratio of the existing one, and closer to the delivery ratio of the real coordinate under unreliable links, without introducing any additional cost.

REFERENCES

• 1: Ananth Rao , Sylvia Ratnasamy , 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]
• 2: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 3: 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]
• 4: 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]
• 5: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 6: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 7: Rodrigo Fonseca , Sylvia Ratnasamy , Jerry Zhao , Cheng Tien Ee , David Culler , Scott Shenker , Ion Stoica, Beacon vector routing: scalable point-to-point routing in wireless sensornets, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.329-342, May 02-04, 2005
• 8: 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, p.349-358, December 05-08, 2004 [doi>10.1109/REAL.2004.8]
• 9: B. Leong, B. Liskov, and R. Morris, "Greedy virtual coordinates for geographic routing," in Proc. IEEE ICNP, 2007.
• 10: Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990081]
• 11: M. Zuniga and B. Krishnamachari, "Analyzing the transitional region in low power wireless links," in Proc. IEEE SECON, 2004, pp. 517--526.
• 12: 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]
• 13: Shan Lin , Jingbin Zhang , Gang Zhou , Lin Gu , John A. Stankovic , Tian He, ATPC: adaptive transmission power control for wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182830]
• 14: Seungjoon Lee , Bobby Bhattacharjee , Suman Banerjee, Efficient geographic routing in multihop wireless networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062720]
• 15: 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]
• 16: T. Watteyne, D. Simplot-Ryl, I. Augé-Blum, and M. Dohler, "On using virtual coordinates for routing in the context of wireless sensor networks," in Proc. IEEE PIMRC, 2007, pp. 1--5.
• 17: Qing Cao , Tarek Abdelzaher, Scalable logical coordinates framework for routing in wireless sensor networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.4, p.557-593, November 2006 [doi>10.1145/1218556.1218561]
• 18: 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]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
routing, virtual coordinate, wireless sensor networks