Joint Multi-hop Clustering and Routing in VANETs using Array of Doubly Linked List

Document Type : Power Article

Authors

1 Department of Electrical Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

2 Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University Najafabad, Iran

Abstract

This paper addresses the problems of multi-hop clustering, Cluster Head (CH) selection, and routing in vehicular ad-hoc networks. We propose an efficient algorithm called Joint Multi-hop Clustering and Routing (JMCR) to improve the performance of the network. JMCR uses only local information to cluster vehicles in such a way that not only reduces the total number of clusters, but also maximizes the stability of clusters. It considers both relative speed and Euclidean distance factors to select an appropriate CH for each cluster. In order to update the routing database of each node, an array of doubly linked list is used in which the creation of different routing paths starts from the boundary nodes and continues to CH. Compatibility with reactive clustering and the ability to dynamically follow the network conditions are another advantages of the proposed intra-cluster routing method. Simulation results conducted in NS2 confirm the efficiency of the proposed method in terms of end-to-end delay, overhead, and packet delivery rate.

Keywords


  • Katiyar, D. Singh and R.S. Yadav, "State-of-the-art approach to clustering protocols in VANET: a survey", Wireless Networks, Vol. 26, 2020, pp. 5307–5336.
  • A. Nazib and S. Moh, "Routing protocols for unmanned aerial vehicle-aided vehicular ad hoc networks: a survey", IEEE Access, Vol. 8, April 2020, pp. 77535 – 77560,.

[3] سید مهدی حسینی مطلق، محمدرضا قطره سامانی و عباس جوکار، «ارائة یک مدل ریاضی و روش حل ابتکاری برای مسئلة مکان‌یابی-مسیریابی دوسطحی با در نظر گرفتن شرایط گذاشت و برداشت در حالت عدم قطعیت»، مجلة مدل‌سازی در مهندسی، دورة 16، شمارة 53، تابستان 1397، صفحة 339-361.

[4] R. Pitakaso, K. Sethanan and C. Theeraviriya, "Variable neighborhood strategy adaptive search for solving green 2-echelonlocation routing problem", Computers and Electronics in Agriculture, Vol. 173, Jun. 2020, 105406.

[5] عرفان بابایی تیرکلایی، ایرج مهدوی و میر مهدی سیداصفهانی، «حل مسئلة مسیریابی وسایل نقلیه با در نظر گرفتن سفرهای چندگانه و پنجره‌های زمانی در مدیریت پسماند شهری با استفاده از الگوریتم بهینه‌سازی گرگ خاکستری»، مجلة مدل‌سازی در مهندسی، دورة 15، شمارة 50، پاییز 1396، صفحة 179-191.

[6] S.T. Miri and S. Tabatabaei, "Improved routing vehicular ad-hoc networks (VANETs) based on mobility and bandwidth available criteria using fuzzy logic", Wireless Personal Communications, Apr. 2020, pp. 1263–1278.

[7] مجید یوسفی‌ خوشبخت، اعظم دولت‌نژاد ثمرین و اسماعیل خرم، «یک الگوریتم ترکیبی اصلاحی مورچگان برای حل مسئلة مسیریابی وسیلة نقلیة باز ظرفیت‌دار»، مجلة مدل‌سازی در مهندسی، دورة 17، شمارة 57، تابستان 1398، صفحة 930-110.

[8] J. Li, Y. Han, P. Duan, Y. Han, B. Niu, C Li, Z Zheng and Yi. Liu, "Meta-heuristic algorithm for solving vehicle routing problems with time windows and synchronized visit constraints in prefabricated systems", Journal of Cleaner Production, Vol. 250, March 2020.

[9] Y. Chen, M. Fang, S. Shi, W. Guo and X. Zheng, "Distributed multi-hop clustering algorithm for VANETs based on neighborhood follow", EURASIP Journal on Wireless Communications and Networking, Vol. 2015, No. 1, pp. 1-12.

[10] G. Wolny, "Modified DMAC clustering algorithm for VANETs", in proc. 2008 Third International Conference on Systems and Networks Communications, 2008, pp. 268-273.

[11] S. S. Wang and Y. S. Lin, “Performance evaluation of passive clustering based techniques for inter-vehicle communications”, in proc. The 19th Annual Wireless and Optical Communications Conference (WOCC 2010), 2010, pp. 1-5.

[12] S. Ucar, S. C. Ergen and O. Ozkasap, "Multihop-cluster-based IEEE 802.11p and LTE hybrid architecture for VANET safety message dissemination", IEEE Transactions on Vehicular Technology, Vol. 65, No. 4, 2016, pp. 2621-2636.

[13] Z. Zhang, A. Boukerche and R. Pazzi, “A novel multi-hop clustering scheme for vehicular ad-hoc networks”, in Proc. of the 9th ACM International Symposium on Mobility Management and Wireless Access, 2011, pp. 19-26.

[14] H. Fatemidokht, M.K. Rafsanjani, B.B. Gupta and Ch. Hsu, "Efficient and secure routing protocol based on artificial intelligence algorithms with UAV-assisted for vehicular ad hoc networks in intelligent transportation systems", IEEE Transactions on Intelligent Transportation Systems, January 2021, PP. 1-13.

[15] A. Avokh and G. Mirjalily, "Interference optimization for multicast and broadcast traffics in multi-radio multi-channel wmns equipped with directional antennas", International Journal of Electronics and Communications (AEU), Vol. 83, 2018, pp. 439–450.

[16] امین شماعی چهارسوق و آوید آوخ، «مقایسه و ارزیابی الگوریتم‌های خوشه‌بندی چند-پرشی در شبکه‌های بین-خودرویی»، پنجمین کنفرانس ملی مهندسی برق و سیستم‌های هوشمند ایران، دانشگاه آزاد اسلامی واحد نجف‌آباد، اسفند 1397، صفحة 1-6.

[17] E. Dror, C. Avin and Z. Lotker, “Fast randomized algorithm for hierarchical clustering in vehicular ad-hoc networks”, in proc. Ad Hoc Networking Workshop (Med-Hoc-Net), 2011 The 10th IFIP Annual Mediterranean, 2011, pp. 1-8.

[18] D. Zhang, H. Ge, T. Zhang, Y.Y. Cui, X. Liu and G. Mao, "New Multi-Hop Clustering Algorithm for Vehicular Ad Hoc Networks", IEEE Transactions on Intelligent Transportation Systems, Vol. 20, No.4, 2018, pp. 1517 – 1530.

[19] W. Li, A. Tizghadam and A. Leon-Garcia, “Robust clustering for connected vehicles using local network criticality”, in proc. IEEE International Conference on Communications (ICC), 2012, pp. 7157-7161.

[20] A. Calhan, "A fuzzy logic based clustering strategy for improving vehicular ad-hoc network performance", Sadhana, Vol. 40, No. 2, 2015, pp. 351-367.

[21] O. Senouci, Z. Aliouat and S. Harous, "MCA-V2I: a multi-hop clustering approach over vehicle-to-internet communication for improving VANETs performances", Future Generation Computer Systems, Vol. 96, 2019, pp. 309-323.

[22] K. Huang and B. J. Hu, “A new distributed mobility-based multi-hop clustering algorithm for vehicular ad hoc networks in highway scenarios”, in proc. IEEE Conference on Vehicular Technology (VTC2019-Fall),2019, pp. 1-6, Honolulu, HI, USA.

[23] H. Alabbas and Á.H. Huszák, “CAMVC: stable clustering algorithm for efficient multi-hop vehicular communication on highways”, in proc. 2020 43rd International Conference on Telecommunications and Signal Processing (TSP), Jul. 2020, Milan, Italy.

[24] S. Guo, J. Zheng, Y. Qu, B.H. Zhao and Q.K. PanK, "Clustering and multi-hop routing with power control in wireless sensor networks", The Journal of China Universities of Posts and Telecommunications, Vol. 14, No. 1, 2007, pp. 49-57.

[25] Z. Li and P. Xin, "Evidence-efficient multihop clustering routing scheme for large-scale wireless sensor networks", Wireless Communications and Mobile Computing, Vol. 2017, Nov. 2017.

[26] Z. Xu, L. Chen, C. Chen and X. Guan, "Joint clustering and routing design for reliable and efficient data collection in large-scale wireless sensor networks", IEEE Internet of Things Journal, Vol. 3, No. 4, 2016, pp. 520-532.

[27] Y. Li, J. Zheng, H. Zhang, X. Ye, Z. Liu and J. Li, “Energy-efficient clustering and multi-hop routing algorithm based on GMM for power IoT network”, in proc. Proceedings of the 9th International Conference on Computer Engineering and Networks, 2020, pp. 1169-1176.

[28] A. Avokh and G. Mirjalily, “Performance analysis of broadcasting in small-scale multi-radio multi-channel wireless mesh networks”, in Proc. International Conference on Advanced Communications Technology, 2012, pp. 537 542.

[29] The network simulator NS-2, september 19, 2018. [Online]. Available: http://nsnam.isi.edu/nsnam/index.php/Main_Page. [accessed: september 19, 2018].

[30] M. Fiore, J. Harri, F. Filali, and C. Bonnet, “Vehicular mobility simulation for vanets,” 40th Annual Simulation Symposium (ANSS’07), 2007, pp. 301–309.

[31] R.K. Jaiswal, "Position-based routing protocol using Kalman filter as a prediction module for vehicular ad hoc networks", Computers & Electrical Engineering, Vol. 83, 2020, 106599.