Оптимізація маршрутів передавання даних у безпровідних сенсорних мережах із використанням генетичного алгоритму та алгоритму мурашиної колонії

Анотація

Стаття присвячена задачі визначення маршруту передавання даних між сенсорними вузлами безпровідної сенсорної мережі за допомогою двох метаевристичних підходів – генетичного алгоритму та алгоритму оптимізації мурашиною колонією. Актуальність дослідження зумовлена тим, що вибір послідовності проміжних вузлів безпосередньо впливає на протяжність шляху, кількість операцій приймання і повторного передавання пакетів, затримку тощо. Метою роботи є методично узгоджене порівняння генетичного алгоритму та алгоритму мурашиної колонії за спільної топології, однакового радіуса зв’язку (30 м), фіксованої пари вузлів «джерело-отримувач» і єдиного критерію мінімізації сумарної довжини маршруту для здійснення оцінки щодо впливу механізму пошуку на вибір найкращого маршруту. У генетичному алгоритмі кандидатне рішення кодується впорядкованою послідовністю вузлів від джерела до отримувача. Еволюційне вдосконалення популяції виконується із застосуванням турнірного відбору, схрещування маршрутів за спільним проміжним вузлом та мутації підмаршруту. Якість особини визначається за сумарною довжиною ребер, що входять до відповідного шляху. Аналіз зміни найкращого й середнього значень цільової функції протягом 200 поколінь показав швидке поліпшення популяції на початковій стадії та подальше уповільнення пошуку. Орієнтовно після ста поколінь спостерігалася стабілізація оцінок, що вказує на зосередження еволюційного процесу поблизу найкращого знайденого рішення. Алгоритм мурашиної колонії (ACO) реалізує послідовне формування маршруту штучними агентами. Імовірність вибору наступного сенсорного вузла визначається поєднанням феромонної інформації та евристичної привабливості доступного переходу. Після завершення руху агентів концентрація феромону коригується шляхом випаровування та підсилення ребер, що входять до коротших шляхів. Завдяки багаторазовому оновленню феромонної матриці колонія поступово накопичує інформацію про перспективні напрями передавання даних. За результатами імітаційного моделювання, в межах досліджуваного сценарію застосування генетичного алгоритму забезпечило формування маршруту, сумарна довжина якого була меншою порівняно з маршрутом, отриманим методом ACO: на 28,39 % для топології з 25 вузлів і на 30,75 % для топології зі 100 вузлів. Отримані результати показують, що для заданих координатних конфігурацій еволюційне опрацювання повних маршрутних хромосом дозволило сформувати компактнішу послідовність передавання даних, тоді як покрокова феромонна стратегія привела до довшого шляху.