Пошук маршруту передачі даних у безпровідній сенсорній мережі із використанням генетичного алгоритму
| dc.citation.epage | 81 | |
| dc.citation.issue | 2 | |
| dc.citation.journalTitle | Інфокомунікаційні технології та електронна інженерія | |
| dc.citation.spage | 72 | |
| dc.citation.volume | 4 | |
| dc.contributor.affiliation | Національний університет “Львівська політехніка” | |
| dc.contributor.affiliation | Lviv Polytechnic National University | |
| dc.contributor.author | Пиріг, Я. | |
| dc.contributor.author | Pyrih, Ya. | |
| dc.coverage.placename | Львів | |
| dc.coverage.placename | Lviv | |
| dc.date.accessioned | 2025-11-03T11:06:30Z | |
| dc.date.created | 2024-12-10 | |
| dc.date.issued | 2024-12-10 | |
| dc.description.abstract | Висвітлено застосування генетичного алгоритму для визначення оптимального марушруту в безпровідній сенсорній мережі. Наведено класифікацію стратегій маршрутизації даних на основі: способу визначення маршрутів, структури мережі, мережевих операцій, орга- нізатора комунікацій. Генетичний алгоритм зараховано до багатошляхової маршрутизації, оскільки його використання дає змогу отримати множину маршрутів. Відповідно, коли передавання даних по найкращому маршруту неможливе, доступна інформація із множини маршрутів, що дає змогу отримати альтернативні рішення у випадку відмови основного. Наведено основні етапи роботи генетичного алгоритму: відбір, схрещування та мутація. Значну увагу звернено на налаштування його параметрів, зокрема розміру популяції, кількості поколінь, імовірності схрещування та імовірності мутації. Для визначення маршруту в безпровідній сенсорній мережі використано сукупність таких генетичних операторів: турнірний оператор відбору, впорядкований оператор схрещування та оператор мутації перемішування, та сформовано функцію для оцінювання пристосованості кожної особини (маршруту). Для перевірки працездатності пропонованого генетичного алгоритму розроблено програмний продукт на мові програмування Python із використанням бібліотеки DEAP. Змодельовано мережу із 25 вузлів, розміщених довільно на ділянці розміром 100×100, радіус дії кожного із них 30 метрів. Щоб урахувати неможливість передавання даних між вузлами із радіусом дії, більшим за заданий, використано штраф на відстань 1000 м, що спонукає генетичний алгоритм шукати коротші маршрути. Представлено матрицю вузлів розглянутої мережі, що містить інформацію про топологію та взаємозв’язки між вузлами. На основі результатів імітаційного моделювання показано, що найкоротший маршрут між двома розглянутими вузлами встановлено для кількості поколінь 150 та розміру популяції 300. Також отримані результати демонструють лінійне зростання часу пошуку маршруту зі збільшенням кількості поколінь та розміру популяції. | |
| dc.description.abstract | The article is devoted to the application of a genetic algorithm for determining the optimal route in a wireless sensor network. The paper presents a classification of data routing strategies based on: the method of determining routes, network structure, network operations, and communication organiser. The genetic algorithm is classified as a multi-path routing strategy, since its use allows obtaining a set of routes. Accordingly, when data transmission via the best route is not possible, information from a set of routes is available, which allows obtaining alternative solutions in case of failure of the main route. The main stages of the genetic algorithm are presented: selection, crossing and mutation, with considerable attention paid to setting its parameters, in particular, population size, number of generations, crossover probability and mutation probability. To determine the route in a wireless sensor network, the following set of genetic operators is used: a tournament selection operator, an ordered crossover operator, and a mixing mutation operator, and a function is formed to assess the fitness of each individual (route). To test the performance of the presented genetic algorithm, a software product in the Python programming language was developed using the DEAP library. A network of 25 nodes was modelled, randomly placed on a 100 by 100 area, with each node having a range of 30 metres. To take into account the impossibility of data transmission between nodes with a greater range than the specified one, a distance penalty of 1000 metres is used, which encourages the genetic algorithm to search for shorter routes. The matrix of nodes of the considered network is presented, which contains information about the topology and relationships between nodes. Based on the results of simulation modelling, it is shown that the shortest route between the two considered nodes is established at a number of generations of 150 and a population size of 300. The results also demonstrate a linear increase in the route search time with an increase in the number of generations and population size. | |
| dc.format.extent | 72-81 | |
| dc.format.pages | 10 | |
| dc.identifier.citation | Пиріг Я. Пошук маршруту передачі даних у безпровідній сенсорній мережі із використанням генетичного алгоритму / Я. Пиріг // Інфокомунікаційні технології та електронна інженерія. — Львів : Видавництво Львівської політехніки, 2024. — Том 4. — № 2. — С. 72–81. | |
| dc.identifier.citation2015 | Пиріг Я. Пошук маршруту передачі даних у безпровідній сенсорній мережі із використанням генетичного алгоритму // Інфокомунікаційні технології та електронна інженерія, Львів. 2024. Том 4. № 2. С. 72–81. | |
| dc.identifier.citationenAPA | Pyrih, Ya. (2024). Poshuk marshrutu peredachi danykh u bezprovidnii sensornii merezhi iz vykorystanniam henetychnoho alhorytmu [Search for a data transmission route in a wireless sensor network using a genetic algorithm]. Infocommunication technologies and electronic engineering, 4(2), 72-81. Lviv Politechnic Publishing House. [in Ukrainian]. | |
| dc.identifier.citationenCHICAGO | Pyrih Ya. (2024) Poshuk marshrutu peredachi danykh u bezprovidnii sensornii merezhi iz vykorystanniam henetychnoho alhorytmu [Search for a data transmission route in a wireless sensor network using a genetic algorithm]. Infocommunication technologies and electronic engineering (Lviv), vol. 4, no 2, pp. 72-81 [in Ukrainian]. | |
| dc.identifier.doi | https://doi.org/10.23939/ictee2024.02.072 | |
| dc.identifier.uri | https://ena.lpnu.ua/handle/ntb/116930 | |
| dc.language.iso | uk | |
| dc.publisher | Видавництво Львівської політехніки | |
| dc.publisher | Lviv Politechnic Publishing House | |
| dc.relation.ispartof | Інфокомунікаційні технології та електронна інженерія, 2 (4), 2024 | |
| dc.relation.ispartof | Infocommunication technologies and electronic engineering, 2 (4), 2024 | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [12] Пиріг, Я., Климаш, М., Пиріг, Ю., & Лаврів, О. (2023). Генетичний алгоритм як засіб розв’язання оптимізаційних задач. Інфокомунікаційні технології та електронна інженерія. № 3(2). С. 95–107. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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. | |
| dc.relation.references | [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, pp. 1875–1880. | |
| dc.relation.references | [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. | |
| dc.relation.references | [19]Пиріг, Я. (2024). Оцінка обчислювальної складності генетичного алгоритму. Інфокомунікаційні технології та електронна інженерія. № 4(1). С. 52–60. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [12] Pyrih, Ya., Klymash, M., Pyrih, Yu., & Lavriv, O. (2023). Henetychnyi alhorytm yak zasib rozviazannia optymizatsiinykh zadach. Infokomunikatsiini tekhnolohii ta elektronna inzheneriia. No 3(2). P. 95–107. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [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, pp. 1875–1880. | |
| dc.relation.referencesen | [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. | |
| dc.relation.referencesen | [19]Pyrih, Ya. (2024). Otsinka obchysliuvalnoi skladnosti henetychnoho alhorytmu. Infokomunikatsiini tekhnolohii ta elektronna inzheneriia. No 4(1). P. 52–60. | |
| dc.rights.holder | © Національний університет „Львівська політехніка“, 2024 | |
| dc.subject | генетичний алгоритм | |
| dc.subject | маршрут | |
| dc.subject | безпровідна сенсорна мережа | |
| dc.subject | гене- тичний оператор | |
| dc.subject | genetic algorithm | |
| dc.subject | route | |
| dc.subject | wireless sensor network | |
| dc.subject | genetic operator | |
| dc.subject.udc | 519.876 | |
| dc.title | Пошук маршруту передачі даних у безпровідній сенсорній мережі із використанням генетичного алгоритму | |
| dc.title.alternative | Search for a data transmission route in a wireless sensor network using a genetic algorithm | |
| dc.type | Article |