The recent enhancement of sensor devices, such as the Micro-Electro Mechanical Devices (MEMs) used for information collection and dissemination, has led to the emergence of the Internet of Things (IoT), Internet of Vehicles (IoV). This new paradigm overlaps with many research areas such as the Wireless Sensor Networks (WSNs) where sensor nodes are deployed over an area to perform local computations based on information gathered from the surrounding. Virtual Backbone is a mechanism that aims at constructing a path with multi-hop from cluster-heads (CHs) to a Base Station (BS) via gateway nodes. This mechanism is efficient since it allows enhancing the reliability and prolonging the network lifetime. In this paper, we propose a new routing protocol, denoted Multi-Hop Routing (MHR), which uses a virtual backbone to improve the network lifetime and reduce the number of lost packets. The aim of our proposition is to find the best connection between the CHs to ensure a fast and efficient backbone construction while minimizing the energy consumption. MHR uses the number of Advertisement (ADV) messages, the residual energy and the distance to the BS in the choice of the backbone’s gateways. Our simulation results show that MHR outperforms EEUC and MH-LEACH in terms of packet delivery ratio and network lifetime.
Cite this paper
Cisse, C. S. M. (2020). Multi-Hop Routing Algorithm for Wireless Sensor Network. Open Access Library Journal, 7, e6955. doi: http://dx.doi.org/10.4236/oalib.1106955.
Heinzelman, W.R., Chandrakasan, A. and Balakrishnan, H. (2000) Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, 4-7 January 2000, 10.
Manjeshwar, A. and Agrawal, D.P. (2001) TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. Parallel and Distributed Processing Symposium, International, Vol. 3, 30189a.
Heinzelman, W.B., Chandrakasan, A.P. and Balakrishnan, H. (2002) An Application-Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Transactions on Wireless Communications, 1, 660-670.
https://doi.org/10.1109/TWC.2002.804190
Ali, M.S., Dey, T. and Biswas, R. (2008) ALEACH: Advanced LEACH Routing Protocol for Wireless Microsensor Networks. IEEE International Conference on Electrical and Computer Engineering, Phuket, 20-22 December 2008, 909-914.
https://doi.org/10.1109/ICECE.2008.4769341
Manjeshwar, A. and Apteen, A.D. (2002) A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks. Proceedings of the 2nd International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, Fort Lauderdale, FL, 15-19 April 2002, 195-202.
Lindsey, S. and Raghavendra, C.S. (2002) PEGASIS: Power Efficient Gathering in Sensor Information Systems. Aerospace Conference Proceedings, Vol. 3, 3-1125.
https://doi.org/10.1109/AERO.2002.1035242
Chen, H., Zhang, C., Zong, X. and Wang, C. (2013) LEACH-G: An Optimal Cluster-Heads Selection Algorithm Based on LEACH. Journal of Software, 8, 2660-2667.
https://doi.org/10.4304/jsw.8.10.2660-2667
Younis, O. and Fahmy, S. (2004) HEED: A Hybrid, Energy Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks. IEEE Transactions on Mobile Computing, 3, 366-379. https://doi.org/10.1109/TMC.2004.41
Li, C., Ye, M., Chen, G. and Wu, J. (2005) An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Washington DC, 7-10 November 2005, 8.
Mardini, W., Yassein, M.B., Khamayseh, Y. and Ghaleb, B.A. (2014) Rotated Hybrid, Energy-Efficient and Distributed (RHEED) Clustering Protocol in WSN. WSEAS Transactions on Communications, 13, 275-290.
Aierken, N., Gagliardi, R., Mostarda, L. and Ullah, Z. (2015) RUHEED-Rotated Unequal Clustering Algorithm for Wireless Sensor Networks. IEEE 29th International Conference on Advanced Information Networking and Applications Workshops, Gwangiu, 24-27 March 2015, 170-174.
https://doi.org/10.1109/WAINA.2015.86
Neto, J.H.B., Rego, A., Cardoso, A.R. and Celestino Jr., J. (2014) MH-LEACH: A Distributed Algorithm for Multi-Hop Communication in Wireless Sensor Networks. ICN 2014, Nice, 23-27 February 2014, 55-61.
Patra, A. and Chouhan, S. (2013) Energy Efficient Hybrid Multihop Clustering Algorithm in Wireless Sensor Networks. 2013 IEEE International Conference on Communication, Networks and Satellite (COMNETSAT), Yogyakarta, 3-4 December 2013, 59-63. https://doi.org/10.1109/COMNETSAT.2013.6870861
An, N., Yan, X., Zhu, Y. and Duan, L. (2007) A Virtual Backbone Network Algorithm Based on the Multilevel Cluster Tree with Gateway for Wireless Sensor Networks.
Cisse, C.S.M., Ahmed, K., Sarr, C. and Gregory, M.A. (2016) Energy Efficient Hybrid Clustering Algorithm of Wireless Sensor Network. 2016 26th International Telecommunication Networks and Applications Conference (ITNAC), Dunedin, 7-9 December 2016, 38-43. https://doi.org/10.1109/ATNAC.2016.7878779
Aierken, N., Gagliardi, R., Mostarda, L. and Ullah, Z. (2015) RUHEED-Rotated Unequal Clustering Algorithm for Wireless Sensor Networks. 2015 IEEE 29th International Conference on Advanced Information Networking and Applications Workshops (WAINA), Gwangiu, 24-27 March 2015, 170, 174.
https://doi.org/10.1109/WAINA.2015.86
