Greedy Geographical Void Routing for Wireless Sensor Networks

Authors: Chiang Tzu-Chiang, Chang Jia-Lin, Tsai Yue-Fu, Li Sha-Pai

Abstract:

With the advantage of wireless network technology, there are a variety of mobile applications which make the issue of wireless sensor networks as a popular research area in recent years. As the wireless sensor network nodes move arbitrarily with the topology fast change feature, mobile nodes are often confronted with the void issue which will initiate packet losing, retransmitting, rerouting, additional transmission cost and power consumption. When transmitting packets, we would not predict void problem occurring in advance. Thus, how to improve geographic routing with void avoidance in wireless networks becomes an important issue. In this paper, we proposed a greedy geographical void routing algorithm to solve the void problem for wireless sensor networks. We use the information of source node and void area to draw two tangents to form a fan range of the existence void which can announce voidavoiding message. Then we use source and destination nodes to draw a line with an angle of the fan range to select the next forwarding neighbor node for routing. In a dynamic wireless sensor network environment, the proposed greedy void avoiding algorithm can be more time-saving and more efficient to forward packets, and improve current geographical void problem of wireless sensor networks.

Keywords: Wireless sensor network, internet routing, wireless network, greedy void avoiding algorithm, bypassing void.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058137

References:

[1] B. Karp and H. T. Kung, "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks," in Proceedings of the Annual International Conference on Mobile Computing and Networking, Aug. 2000, pp. 243 254.
[2] Q. Fang, J. Gao, and L. J. Guibas, "Locating and Bypassing Holes in Sensor Networks,"Mobile Networks and Applications, Vol. 11, No. 2, pp. 187-200, Apr. 2006.
[3] M. Aissani, A. Mellouk, N. Badache, and M. Djebbar, "A New Approach of Announcement and Avoiding Routing Voids in Wireless Sensor Networks," in Proceeding of the IEEE Global Telecommunications Conference, Nov. 2008, pp. 1-5.
[4] W-J. Liu and K-T. Feng, "Greedy Routing with Anti-Void Traversal for Wireless Sensor Networks," IEEE Transactions on Mobile Computing, Vol. 8, No. 7, pp. 910-922, July 2009.
[5] M.Aissani, A.Mellouk, N.Badache, and M.Djebbar, "A Preventive Rerouting Scheme for Avoiding Voids in Wireless Sensor Networks," in Proceeding of the IEEE Global Telecommunications Conference, Dec. 2009, pp. 1-5.
[6] H. Wang, X. Zhang, and A. Khokhar, "Efficient Void Handling in Contention-Based Geographic Routing for Wireless Sensor Networks," in Proceeding of the IEEE Global Telecommunications Conference, Nov. 2007, pp. 663-667.
[7] T. He, J. Stankovic, C. Lu, and T. Abdelzaher, "SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks,"Proc. IEEE Int-l Conf. Distributed Computing Systems, May.2003, pp. 46-55.
[8] I. Stojmenovic, M. Russell, and B. Vukojevic, "Depth First Search and Location Based Localized Routing and QoS Routing in Wireless Networks," Proc. IEEE Int-l Conf. Parallel Processing, 2000, pp. 173- 180.
[9] W. Jia, T. Wang, G. Wang, and M. Guo, "Hole Avoiding in Advance Routing in Wireless Sensor Networks," Proc. IEEE WCNC 2007, March. 2007, pp. 3519 - 3523.
[10] M. Aissani, A. Mellouk, N. Badache, and B. Saidani, "Oriented Void Avoidance Scheme for Real-Time Routing Protocols in Wireless Sensor Networks," IEEE Global Communications Conference, Nov. 2008, pp.1- 5.
[11] E. Felemban, C.-G. Lee, and E. Ekici, "MMSPEED: Multipath Multi- SPEED Protocol for QoS Guarantee of Reliability and Timeliness in Wireless Sensor Networks," IEEE Trans. Mobile Comput., Vol. 5, No. 6, June 2006, pp. 738-754.
[12] S. Chen, G. Fan, and J.-H. Cui, "Avoid ÔÇÿvoid- in Geographic Routing for Data Aggregation in Sensor Networks," International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC), Vol. 2, No. 1, July 2006, pp. 169-178.
[13] T. Roosta , M. Menzo, and S. Sastry, "Probabilistic Geographic Routing Protocol for Ad Hoc and Sensor Networks," in International WorkShop on Wireless AdHoc Networks ( IWWAN) ,May 2005.
[14] Y. Xu, W. C. Lee, J. Xu, and G. Mitchell, "PSGR: Priority-based Stateless Geo-routing in Wireless Sensor Networks," in IEEE International Conference on Mobile Ad-hoc and Sensor Systems, Nov. 2005, 8 pp. - 680.
[15] J. Na, D. Soroker, and C. K. Kim, "Greedy geographic routing using dynamic potential field for wireless ad hoc networks," IEEE Communications Letters, Vol. 11, No. 3, March 2007, pp. 243-245.
[16] R. Tang, S. Guo , H. Ji, and C. Gong, "A Heuristic Optimization Algorithm For Geographic Greedy Hole-Bypassing Routing Algorithms in WMSNS," Proceedings of Broadband Network and Multimedia Technology (IC-BNMT), Oct. 2010, pp. 540-545.
[17] P.Pranitha ,G.Swamy , and A. Manjula, "A Review on Enhanced GPSR protocol For Wireless Sensor Networks," Computer Engineering and Intelligent Systems, Vol. 2, No.4, 2011.
[18] A. Baadache, and A. Belmehdi, "Avoiding Black hole and Cooperative Black hole Attacks in Wireless Ad hoc Networks," International Journal of Computer Science and Information Security, Vol. 7, No. 1, 2010.
[19] G-Y. Chang, J-P. Sheu, C-W. Chen, S-Y. Wang, and C-C. Chang, "Contour-Based Hole Avoiding Routing Protocol in Wireless Sensor Networks," IEEE Communications Society subject matter experts for publication in the IEEE Globecom, 2010.
[20] S. Xia, X. Yin, H. Wu, M. Jin, and X. Gu, "Deterministic Greedy Routing with Guaranteed Delivery in 3D Wireless Sensor Networks," in Proc. of the 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2011.
[21] N. Le, N. Hieu, B. Quan, N. Van, "Efficient Approximation of Routing Holes in Wireless Sensor Networks," Proceedings of the Second Symposium on Information and Communication Technology, 2011.
[22] Z. Wang, D. Zhanga, O. Alfandi, and D. Hogrefe, "Efficient Geographical 3D Routing for Wireless Sensor Networks in Smart Spaces," Baltic Congress on Future Internet and Communications, 2011.
[23] H. Choo, M. Choi, M. Shon, "Efficient Hole Bypass Routing Scheme Using Observer Packets for Geographic Routing in Wireless Sensor Networks," ACM SIGAPP Applied Computing Review, Vol.11,No.4, 2011, pp. 7-16.
[24] S-F. Hwang, C-H. Yang, Y-Y. Su, C-R. Dow, "Energy Efficient Hole Bypassing Routing in Wireless Sensor Networks," Computer Science and Information Technology (ICCSIT) , July 2010, pp. 576-580.
[25] J. Jia, J. Chen, X. Wang, and L. Zhao, "Energy-Balanced Density Control to Avoid Energy Hole for Wireless Sensor Networks," International Journal of Distributed Sensor Networks, 2012.
[26] Y. Liu, L-X. Cai, X. Shen, and J-W. Mark, "Exploiting Heterogeneity Wireless Channels for Opportunistic Routing in Dynamic Spectrum Access Networks," IEEE Communications Society subject matter experts for publication in the IEEE ICC, 2011, pp. 1-5.
[27] N-D. Nguyen, D-Tu. Nguyen, M-A- L. Gall, N. Saxena, and H. Choo, "Greedy Forwarding with Virtual Destination Strategy for Geographic Routing in Wireless Sensor Networks," International Conference of Computational Science and Its Applications, 2010, pp. 217-221.
[28] B.S. Raja, N.Prabakaran, V.R.S. Dhulipala, "Modified GPSR Based Optimal Routing Algorithm for Reliable Communication in WSNs," International Conference on Devices and Communications (ICDeCom), 2011, pp. 1-5.
[29] L. Nithyanandan, G. Sivarajesh, and P. Dananjayan, "Modified GPSR Protocol for Wireless Sensor Networks," International Journal of Computer and Electrical Engineering, Vol. 2, No. 2, April 2010, pp. 324-328.
[30] C-H. Lin, S-A. Yuan, S-W. Chiu, and M-J. Tsai, "ProgressFace: An Algorithm to Improve Routing Efficiency of GPSR-like Routing Protocols in Wireless Ad Hoc Networks," IEEE Transactions on Computers , Vol. 59, No. 6, 2010, pp. 822-834.
[31] P. Samundiswary, D.Sathian1, and P. Dananjayan, "Secured Greedy Perimeter Stateless Routing for Wireless Sensor Networks," International Journal of Ad hoc, Sensor & Ubiquitous Computing (IJASUC) , Vol. 1, No. 2, June 2010.
[32] Z. Wang, X. Qian, X. Zhao, "The Strategies of Avoiding Energy Holes in Wireless Sensor Networks," 4th International Congress on Image and Signal Processing (CISP), Vol. 5, 2011, pp. 2687-2691.
[33] J. You, Q. Han, D. Lieckfeldt, J. Salzmann, and D. Timmermann, "Virtual Position Based Geographic Routing for Wireless Sensor Networks," Computer Communications, Vol. 33, July 2010, pp. 1255- 1265.