ПОШУК МАРШРУТУ ПЕРЕДАЧІ ДАНИХ У БЕЗПРОВІДНІЙ СЕНСОРНІЙ МЕРЕЖІ ІЗ ВИКОРИСТАННЯМ ГЕНЕТИЧНОГО АЛГОРИТМУ

Автори:
1
Lviv Polytechnic National University

Робота присвячена застосуванню генетичного алгоритму для визначення оптимального марушруту у безпровідній сенсорній мережі. Наведено класифікацію стратегій маршрутизації даних на основі: способу визначення маршрутів, структури мережі, мережевих операцій, організатора комунікацій. Генетичний алгоритм віднесено до багатошляхової маршрутизації, оскільки його використання дозволяє отримати множину маршрутів. Відповідно, коли передача даних по найкращому маршруту неможлива, доступною є інформація із множини маршрутів, що дозволяє отримати альтернативні рішення у випадку виходу з ладу основного. Наведено основні етапи роботи генетичного алгоритму: відбір, схрещування та мутація, при цьому значну увагу приділено налаштуванню його параметрів, зокрема розміру популяції, кількості поколінь, імовірності схрещування та імовірності мутації. Для визначення маршруту у безпровідній сенсорній мережі використано наступну сукупність генетичних операторів: турнірний оператор відбору, впорядкований оператор схрещування та оператор мутації перемішування, та сформовано функцію для оцінки пристосованості кожної особини (маршруту). Для перевірки працездатності представленого генетичного алгоритму розроблено програмний продукт на мові програмування Python із використанням бібліотеки DEAP. Змодельовано мережу із 25 вузлів, розміщених випадковим чином на ділянці розміром 100 на 100, при цьому кожен із них має радіус дії 30 метрів. Для врахування неможливості передачі даних між вузлами із більшим радіусом дії за заданий використано штраф на відстань 1000 метрів, що спонукає генетичний алгоритм шукати більш короткі маршрути. Представлено матрицю вузлів розглянутої мережі, що містить інформацію про топологію та взаємозв’язки між вузлами. На основі результатів імітаційного моделювання показано, що найкоротший маршрут між двома розглянутими вузлами встановлено при кількості поколінь 150 та розміру популяції 300. Також отримані результати демонструють лінійне зростання часу пошуку маршруту при збільшенні кількості поколінь та розміру популяції.

[1]   Chen, G., & Hu, H.-X. (2022). Finding the Optimal Network Topology for the Distributed Multi-Short-Paths Routing Algorithm – A Genetic Algorithm-Based Approach. 2022 Int. Conference on Intelligent Systems and Computational Intelligence, China, pp, 35-38. doi: 10.1109/ICISCI53188.2022.9941373.

[2]   Chai, Y. & Zeng, X.J. (2019). An effective routing with delay minimization for multi-hop wireless mesh network, IEEE Global Communications Conference. pp. 1-6, doi: 10.1109/GLOBECOM38437.2019.9013776.

[3]   Praveen, J. S., & Kumanan. T. (2024). Link Loss Identification and Congestion-Aware Routing in Mobile Wireless Sensor Network, 2024 2nd International Conference on Device Intelligence, Computing and Communication Technologies, India, pp. 585-589, doi: 10.1109/DICCT61038.2024.10532948.

[4]   Gripsy, J.V., & Jayanthiladevi, A. (2023). Energy Optimization and Dynamic Adaptive Secure Routing for MANET and Sensor Network in IoT, 2023 7th International Conference on Computing Methodologies and Communication (ICCMC), Erode, India, pp. 1283-1290, doi: 10.1109/ICCMC56507.2023.10083519.

[5]   Aluvala, S., Reddy, G., Al-Jawahry, H.M., Ramadan, G.M., & Pareek, P.K. (2023). Improved Sail Fish Optimizer for Energy Efficient Routing in Wireless Sensor Network, 2023 Int. Conference on Integrated Intelligence and Communication Systems, India, pp. 1-4, doi: 10.1109/ICIICS59993.2023.10421391.

[6]   Joshi, R. D., & Banu S. (2023). Brief Survey on Wireless Sensor Network Routing, 2023 7th International Conference on Computation System and Information Technology for Sustainable Solutions (CSITSS), Bangalore, India, pp. 1-8, doi: 10.1109/CSITSS60515.2023.10334097.

[7]   Bairagi, P.P., Dutta, M., & Babulal, K.S. (2022). Location based Routing Protocols and its Performances in Wireless Sensor Networks: An Investigation, 2022 3rd International Conference on Electronics and Sustainable Communication Systems, India, pp. 583-590, doi: 10.1109/ICESC54411.2022.9885717.

[8]   Anitha, T., & Sridhar, S. (2023). Novel Improved Communication Steadiness Routing for Wireless Sensor Network's Performance Analysis compared with Network Boundary Maintenance Routing, 2023 International Conference on Artificial Intelligence and Knowledge Discovery in Concurrent Engineering (ICECONF), Chennai, India, pp. 1-8, doi: 10.1109/ICECONF57129.2023.10083655.

[9]   Mishra, J., Bagga, J., Choubey, S., & Gupta, I.K. (2017). Energy optimized routing for wireless sensor network using elitist genetic algorithm, 2017 8th International Conference on Computing, Communication and Networking Technologies, India, pp. 1-5, doi: 10.1109/ICCCNT.2017.8204110.

[10]Pyrih, Y., Kaidan, M., Tchaikovskyi, I., & Pleskanka, M. (2019). Research of Genetic Algorithms for Increasing the Efficiency of Data Routing 2019 3rd International Conference on Advanced Information and Communications Technologies (AICT), Lviv, Ukraine, pp. 157-160, doi: 10.1109/AIACT.2019.8847814.

[11]Rares, M. (2015). Adaptive mutation in genetic algorithms for shortest path routing problem, 2015 7th International Conference on Electronics, Computers and Artificial Intelligence (ECAI), Bucharest, Romania, pp. 69-74, doi: 10.1109/ECAI.2015.7301163.

[12]Пиріг, Я., Климаш, М., Пиріг, Ю., & Лаврів, О. (2023). Генетичний алгоритм як засіб розв’язання оптимізаційних задач. Інфокомунікаційні технології та електронна інженерія, №3(2), с. 95-107.

[13]Bai, Y. et al. (2022). A Deep Reinforcement Learning-Based Geographic Packet Routing Optimization, in IEEE Access, vol. 10, pp. 108785-108796, doi: 10.1109/ACCESS.2022.3213649.

[14]Wang, D., & Li, B.(2015). Analysis of a local routing in scale-free networks, 27th Chinese Control and Decision Conference (CCDC), Qingdao, China, pp. 1936-1939, doi: 10.1109/CCDC.2015.7162236.

[15]Min, J., Kim, W., Paek, J., & Govindan, R. (2024). Effective Routing and Scheduling Strategies for Fault-Tolerant Time-Sensitive Networking, IEEE Internet of Things Journal, vol. 11, no. 6, pp. 11008-11020, doi: 10.1109/JIOT.2023.3328626. 

[16]Rani, S., Beniwal, R., & Saini, K. (2023). Performance Evaluation on Various Routing Strategies in IoT, 2023 9th International Conference on Signal Processing and Communication (ICSC), NOIDA, India, pp. 139-144, doi: 10.1109/ICSC60394.2023.10441445.

[17]Sun, W. (2019). Data link network resource allocation method based on genetic algorithm, 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC): proceedings. Chengdu, China, P. 1875-1880.

[18]Gao, M. (2020). Opposite and Chaos Searching Genetic Algorithm Based for UAV Path Planning, 2020 IEEE 6th International Conference on Computer and Communications, China, P. 2364-2369.

[19]   Пиріг, Я. (2024). Оцінка обчислювальної складності генетичного алгоритму. Інфокомунікаційні технології та електронна інженерія, №4(1),с. 52-60.