علوم رایانش و فناوری اطلاعات

مقایسه الگوریتم‌های مسطح‌سازی GG و RNG در روش‌های مسیریابی جغرافیایی شبکه‌های بی‌سیم

نویسندگان

1 پژوهشکده علوم کامپیوتر، پژوهشگاه دانش های بنیادی، تهران، ایران

2 دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

چکیده

در تحقیقاتی که تا کنون در زمینه الگوریتم­های جغرافیایی گزارش شده است، به دو روش مسطح­سازی GG و RNG بصورت یکسان نگاه شده است، در حالیکه گراف حاصل از این دو روش خصوصیاتی متفاوت را ارائه می­کنند. در این مقاله، بررسی دقیق این دو روش مسطح­سازی و مطالعه اثر آنها بر الگوریتم‌های مسیریابی جغرافیایی مورد نظر قرار گرفته است. تلقی اولیه این است که چون گراف مسطح­شده به روش GG دارای تعداد لبه بیشتری است، استفاده از آن بهصورت وجه­پیمایی منجر به تولید تعداد گام‌های بیشتری خواهد شد، ولی نتایج شبیه­سازی پژوهش حاضر نشان می‌دهد که در بیشتر موارد گام‌های بلند روش RNG خطر به بیراهه رفتن را افزایش و مسیرهای نسبتاً بلندتری را برای پیمایش تا گره مقصد پیشنهاد می‌دهد. در مقابل و در مواردی که الگوریتم جغرافیایی مورد استفاده رسیدن تا مقصد را تضمین نمی‌کند، تعداد موارد مسیریابی ناموفق با استفاده از گراف مسطح شده GG  اندکی بیشتر از موارد مشابه به روش مسطح­سازی RNG خواهد بود.

کلیدواژه‌ها

  • [1] S. Boussoufa-Lahlaha, F. Semchedinea, and L. Bouallouche-Medjkounea, “Geographic routing protocols for Vehicular Ad hoc NETworks (VANETs): A survey,” Vehicular Communications, Vol. 11, pp. 20 – 32, 2018.
  • [2] F. Cadger, K. Curran, J. Santos, and S. Moffett, “A Survey of Geographical Routing in Wireless Ad-Hoc Networks,” IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 15, NO. 2, pp. 621 – 653, 2013.
  • [3] B. Karp, and H.T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” Proceedings of the 6th international conference on Mobile computing and networking, ACM, p. 243–254, 2000.
  • [4] B. Karp, Geographic Routing for Wireless Networks, PhD Thesis, Harvard University, 2000.
  • [5] F. Kuhn, R. Wattenhofer, and A. Zollinger, “Asymptotically optimal geometric mobile ad-hoc routing,” Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (Dial-M’02), Atlanta, GA, USA, 2002.
  • [6] F. Kuhn, R. Wattenhofer, and A. Zollinger, “Worst-case optimal and average-case efficient geometric ad-hoc routing,” Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC’ 03), USA, 2003.
  • [7] O. Alzamzami, and I. Mahgoub, “Link utility aware geographic routing for urban VANETs using two-hop neighbor information,” Ad Hoc Networks, Volume 106, 2020.
  • [8] K. Katsaros, M. Dianati, R. Tafazolli, and R. Kernchen, “CLWPR; a novel cross-layer optimized position based routing protocol for VANETs,” Vehicular Network-ing Conference (VNC), pp. 139–146, 2011.
  • [9] O. Alzamzami, and I. Mahgoub, “An enhanced directional greedy forwarding for VANETs using link quality estimation,” IEEE Wireless Communications and Networking Conference, pp. 1–7, 2016.
  • [10] A. C. Souza, C. Castro, J. Garcia, L. Torres, L. Jaimes, and B. Jaimes, “Improving the Efficiency of Gabriel Graph-based Classifiers for Hardware-optimized Implementations,” XXII Symposium on Image, Signal Processing and Artificial Vision (STSIVA), Colombia, Apr 24 - 26, 2019.
  • [11] P. Wan, and C. Yi, “On the Longest Edge of Gabriel Graphs in Wireless Ad Hoc Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol 18, Issue: 1, pp. 111-125, 2007.
  • [12] S. Ruhrup, H. Kalosha, A. Nayak, and I. Stojmenovic, “Message-Efficient Beaconless Georouting with Guaranteed Delivery in Wireless Sensor, Ad Hoc, and Actuator Networks,” IEEE/ACM Transactions on Networking, Vol. 18 (1), 2010.
  • [13] A. Arshad, Z. Hanapi, S. Subramaniam , and R. Latip, “Performance Evaluation of the Geographic Routing Protocols Scalability,” International Conference on Information Networking (ICOIN), Malaysia, 2019.
  • [14] D. Das and R. Misra, “Improvised geographic scheme for greedy perimeter stateless routing,” IEEE Recent Advances in Intelligent Computational Systems (RAICS), pp. 68-73, India, 2013.
  • [15] Test D. Das and R. Misra, “Improvised k-hop Neighbourhood Knowledge Based Routing in Wireless Sensor Networks,” The 2nd International Conference on Advanced Computing, Networking and Security, pp. 136-141, Mangalore, India, 2013.
علوم رایانش و فناوری اطلاعات
دوره 17، شماره 2
پاییز و زمستان
آذر 1398