An efficient real-time routing with presence of concave voids in wireless sensor networks

ABSTRACT

To bypass voids in sensor networks, most existing geographic routing protocols tend to route packets along the boundary nodes. Generally, a packet will be either forwarded along a void boundary by the right-hand rule or pushed back to find another route when it encounters the void. The two techniques consume more energy of boundary nodes, drop many packets and may incur data collisions if multiple communication sessions share the same boundary nodes. We propose in this paper an alternative and efficient void avoidance scheme. The proposed on-demand scheme consists of void discovery, void announce and packet rerouting steps. After discovering a void, a sender node inside the void's announce-area reroutes all data packets to get around the void in advance by selecting one appropriate forwarding side. The double objective of our scheme is to prevent data packets from traveling along the boundaries of voids and to avoid them the concave zones of voids. By achieving this objective we can reduce the energy consumption of boundary nodes and data collisions in these nodes. We can also reduce the packets rerouting overhead and the number of packets dropped by nodes on the boundaries of voids. Simulation showed the efficiency of our scheme.

REFERENCES

• 1: Nadeem Ahmed , Salil S. Kanhere , Sanjay Jha, The holes problem in wireless sensor networks: a survey, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.2, April 2005 [doi>10.1145/1072989.1072992]
• 2: D. Chen, P. Varshney, "A survey of void handling techniques for geographic routing in wireless networks," IEEE Communications Surveys and Tutorials, pp. 50--67, 2007.
• 3: Qing Fang , Jie Gao , Leonidas J. Guibas, Locating and bypassing holes in sensor networks, Mobile Networks and Applications, v.11 n.2, p.187-200, April 2006 [doi>10.1007/s11036-006-4471-y]
• 4: 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]
• 5: Chenyang Lu , Brian M. Blum , Tarek F. Abdelzaher , John A. Stankovic , Tian He, RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.55, September 25-27, 2002
• 6: Tian He , John A. Stankovic , Chenyang Lu , Tarek F. Abdelzaher, A Spatiotemporal Communication Protocol for Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.10, p.995-1006, October 2005 [doi>10.1109/TPDS.2005.116]
• 7: W. Jia, T. Wang, G. Wang and M. Guo, "Hole Avoiding in Advance Routing in Wireless Sensor Networks," IEEE Wireless Communications and Networking Conference (WCNC), pp. 3519--3523, 2007.
• 8: L. Zhao, B. Kan, Y. Xu and X. Li, "FT-SPEED: A Fault-Tolerant, Real-Time Routing Protocol for Wireless Sensor Networks," International Conference on Wireless Communications, Networking and Mobile Computing (WiCom), pp. 2531--2534, 2007.
• 9: O. Chipara, Z. He, G. Xing, Q. Chen, X. Wang, C. Lu, J. A. Stankovic and T. F. Abdelzaher, "Real-time Power-Aware Routing in Sensor Networks," IEEE International Workshop on Quality of Service, June 2006.
• 10: Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, Geographic routing made practical, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.217-230, May 02-04, 2005
• 11: Collaboration between researchers at UC Berkeley, LBL, USC/ISI, and Xerox PARC. The ns Manual, http://www.isi.edu/nsnam/ns/, 2005.

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.1 Network Architecture and Design
          Subjects: Network topology; Network communications

General Terms:
Algorithms, Experimentation, Management, Performance, Reliability, Verification

Keywords:
avoiding voids, concave voids, real-time routing, sensor networks