Greedy Geographical Void Routing for Wireless Sensor Networks

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.

Authors:

• Chiang Tzu-Chiang
• Chang Jia-Lin
• Tsai Yue-Fu
• Li Sha-Pai

Keywords:

• Wireless sensor network
• internet routing
• wireless network
• greedy void avoiding algorithm
• bypassing void.

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.