Оптимізація маршруту мобільного стоку в бездротовій сенсорній мережі з використанням евристичних алгоритмів
DOI:
https://doi.org/10.30837/2522-9818.2025.4.058Ключові слова:
евристичні алгоритми; мобільний стік; оптимізація; задача комівояжера; бездротова сенсорна мережа.Анотація
Предметом дослідження є бездротова сенсорна мережа (БСМ) з мобільним стоком. Мета роботи – підвищити працездатність БСМ, збільшити тривалість її життя та функціювання завдяки зменшенню часу затримки передачі даних у процесі опитування маршрутизаторів унаслідок оптимізації маршруту мобільного стоку способом обрання найбільш ефективного алгоритму. Для досягнення окресленої мети необхідно виконати такі завдання: оптимізувати маршрут мобільного стоку БСМ за допомогою розв’язання задачі комівояжера методом гілок і меж та порівняння умовної середньої довжини маршруту множини рішень без оптимізації та з оптимізацією за допомогою процедури Роббінса – Монро; провести порівняльний аналіз точного розв’язку задачі комівояжера, отриманого методом гілок і меж, і наближеного рішення, отриманого евристичними методами; сформулювати практичні рекомендації щодо вибору алгоритмів оптимізації маршруту мобільного стоку залежно від розміру сенсорної мережі. Застосовано такі методи: імітаційне моделювання, методи оптимізації, математичне оброблення даних. Досягнуті результати. Досліджено розв’язання задачі оптимізації маршруту мобільного стоку в БСМ з використанням евристичних алгоритмів з метою формулювання практичних рекомендації щодо вибору алгоритмів оптимізації маршруту мобільного стоку залежно від розміру сенсорної мережі. Проведено порівняльний аналіз точного розв’язку задачі комівояжера, виконаного методом гілок і меж, і наближеного рішення, виконаного евристичними методами. Для отримання наближеного рішення реалізовано два евристичні алгоритми: мурашиний алгоритм (ACO) і алгоритм імітації відпалу (SA). Зазначені алгоритми було реалізовано для задачі комівояжера з конкретними координатами для кожної задачі. Ефективність алгоритмів оцінюється на мережах різного масштабу – від 10 до 500 вузлів. Результати моделювання демонструють, що ACO має високу ефективність на малих і середніх мережах (до 50 вузлів), забезпечуючи більш короткі маршрути та швидкий час обчислень. SA визначається кращою масштабованістю на великих мережах (100 вузлів і більше), пропонуючи стабільну продуктивність за високого обчислювального навантаження. Висновки. Продемонстровано, що введення оптимізації у виборі маршруту мобільного стоку в БСМ приводить до зменшення довжини контуру обходу мобільного стоку в діапазоні 30–40% залежно від розмірності мережі та відстаней між маршрутизаторами. Скорочення часу опитування маршрутизаторів у сенсорній мережі сприяє збільшенню залишкової потужності блоків живлення, а отже, продовжує тривалість життя мережі. Доведено, що використання евристичних алгоритмів доцільне тільки тоді, коли необхідна висока швидкість розрахунку нового маршруту мобільного стоку. Якщо швидкість розрахунку нового маршруту не є критичною, тоді краще використовувати точні алгоритми обчислення. Для кожного алгоритму потрібно підбирати параметри залежно від поставленого завдання, оскільки ці параметри впливають на швидкість роботи алгоритму й здатні зменшити діапазон можливих маршрутів, які можна отримати внаслідок розрахунків. Дослідження доводить значущість індивідуального налаштування параметрів алгоритмів для підвищення точності й адаптивності рішень у задачах маршрутизації мобільного стоку.
Посилання
References
Hannan, M.A., Hossain Lipu, M.S., Mahmuda, Akhtar, Begum, R.A., Md Abdullah Al Mamun, Hussain, Aini, Mia, M.S., Basri, Hassan (2020), "Solid waste collection optimization objectives, constraints, modeling approaches, and their challenges toward achieving sustainable development goals". Journal of Cleaner Production, Vol 277, 2020, 123557. ISSN 0959-6526. DOI: 10.1016/j.jclepro.2020.123557
Bondarenko, O., Ageyev, D., Mohammed, O. (2019), "Optimization Model for 5G Network Planning", 2019 IEEE 15th International Conference on the xperience of Designing and Application of CAD Systems (CADSM), Polyana, Ukraine, 2019, Р. 1–4, DOI: 10.1109/CADSM.2019.8779298
Löppenberg, M., Yuwono, S., Mochammad Rizky Diprasetya, Schwung, A. (2024), Dynamic robot routing optimization: State-space decomposition for operations research-informed reinforcement learning", Robotics and Computer-Integrated Manufacturing", Vol.90, 102812. DOI:10.1016/j.rcim.2024.102812
Chekubasheva, V., Glukhov, O., Kravchuk, O., Levchenko, Y., Linnyk, E., Rohovets, V. (2022), "Possibility of Creating a Low-Cost Robot Assistant for Use in General Medical Institutions During the COVID-19 Pandemic". Optics and Its Applications. Springer Proceedings in Physics, Vol 281. Springer, Cham., P. 203–213. DOI:10.1007/978-3-031-11287-4_16
Melnikova, L., Linnyk, E., Ageyev, D., Melnikova, O., Kryvoshapka, N., Barsouk, V. (2019), "Minimizing the Route of Sink Node in Wireless Sensor Network," 2019 IEEE International Scientific Practical Conference Problems of Infocommunications, Science and Technology, PIC S&T, Kyiv, Ukraine, 2019, Р. 861–864, DOI: 10.1109/PICST47496.2019.9061563
Anufriiev, V., Kravchuk, O., Levchenko, Y., Hlukhova, H., Linnyk, E., Glukhov, O. (2024), "Perspective of Creating a Low-Cost Medical Assistant Robot Based on the Waffle PI4 Platform with a Palm Vein Pattern Scanner". Preprints, 2024031696. DOI:10.20535/RADAP.2024.98.46-54
Sasan, Z., Shokrnezhad, M., Khorsandi, S., Taleb, T. (2024), "Joint Network Slicing, Routing, and In-Network Computing for Energy-Efficient 6G", IEEE Wireless Communications and Networking Conference (WCNC), Dubai, United Arab Emirates, Р. 1–6, DOI: 10.1109/WCNC57260.2024.10571186
Mezni, H., Yahyaoui, H., Elmannai, H. et al. (2025), "Personalized service recommendation in smart mobility networks". Cluster Comput, Vol. 28, № 3. DOI: https://doi.org/10.1007/s10586-024-04694-y
Rema, C.; Costa, P.; Silva, M.; Pires, E.J.S. (2025), "Task Scheduling with Mobile Robots a Systematic Literature Review". Robotics, Vol. 14, DOI: https://doi.org/10.3390/robotics14060075
Teja GK, Mohanty PK, Das S. (2025), "Review on path planning methods for mobile robot". Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science. 2025;239(14). Р. 5547–5580. DOI: 10.1177/09544062251330083
Christensen, J., Bastien, C. (2016), "Heuristic and Meta-Heuristic Optimization Algorithms", Nonlinear Optimization of Vehicle Safety Structures, Р. 277–314, 2016, DOI: 10.1016/b978-0-12-417297-5.00007-9
Melnikova, L., Shtangei, S., Linnyk, O. (2025), "Heuristic algorithms for optimization of mobile flow route using structured databases". Zenodo. DOI: https://doi.org/10.5281/zenodo.16903056
Obeidat, A., Shalabi, M. (2022), "An Efficient Approach towards Network Routing using Genetic Algorithm". International Journal of Computers, Communications & Control (IJCCC). 17(5). DOI: 10.15837/ijccc.2022.5.4815
Malavalli, A., Sama, K., Chhabra, J., Bassin, P., Srinivasa, S. (2025), "Engineering Resilience: An Energy-Based Approach to Sustainable Behavioural Interventions". Multiagent Systems. DOI: 10.48550/arXiv.2506.16836
Christopher Bayliss, Djamila Ouelhadj (2024), "Mobility as a Service: An exploration of exact and heuristic algorithms for a new multi-modal multi-objective journey planning problem", Applied Soft Computing, Vol. 162, 111871, DOI: https://doi.org/10.1016/j.asoc.2024.111871
Frías, N., Franklin J., Carlos V. (2023), "Hybrid Algorithms for energy minimizing vehicle routing problem: integrating clusterization and ant colony optimization." IEEE Access. P.: 125800-125821. DOI:10.1109/ACCESS.2023.3325787
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Наше видання використовує положення про авторські права Creative Commons для журналів відкритого доступу.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0), котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
Автори мають право укладати самостійні додаткові угоди щодо не комерційного та не ексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису опублікованої роботи, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи.
