Software Model for Determining the Optimal Routes in a Computer Network Based on the Two-Colonial Ant Algorithm

<jats:p>Purpose. At present, the computer networks of the information and telecommunication system (ITS) of railway transport use the OSPF protocol, which does not allow taking into account several metrics when determining the optimal route. Therefore, there is a need to study the possibility of organizing routing in computer networks of rail transport ITS using a two-colonial ant algorithm. Methodology. According to the Two-ACO software model, created in the Python language based on the two-colonial ant algorithm, the optimal route in a computer network was determined. Two-ACO model inputs: computer network parameters (network adjacency matrix, number of routers); parameters of the ant algorithm (number of iterations; number of ants in the colony; number of elite ants; initial pheromone level; evaporation rate; parameter for adjusting the amount of pheromone deposition). Findings. The results of the Two-ACO model are presented in the form of graphs depicting the optimal paths: the criterion of the total delay on the routers (for the first colony of ants) and the number of hops (for the second colony of ants). Originality. According to the created Two-ACO software model for a computer network of 7 routers and 17 channels, a study of the time for determining the optimal path in a computer network by the number of ordinary and elite ants, evaporation rate and deposited pheromone was conducted. It is determined that it is enough to use the number of ants equal to the number of routers and have 2 elite ants in the colony, with 1000 iterations, evaporation rate from 0.2 to 0.7, and pheromone deposition by ants close to one. Practical value. Created Two-ACO software model using two colonies of ants on the following criteria: the total delay on the routers (for the first colony of ants) and the number of hops that make up the route (for the second colony of ants) allows you to parallel determine the optimal routes in a computer network of railway transport. It is estimated that for a computer network of 15 routers and 17 channels, it is sufficient to have 30 agents (two ants on top), the value of the pheromone deposited by the agents is close to one, and the evaporation rate is 0.4.</jats:p>

section_content: Основним питанням під час функціонування комп'ютерних мереж залізничного транспорту є організація маршрутизації, що досягається на сучасному етапі використанням відомого протоколу OSPF за принципом пошуку найкоротшого шляху. Але такий протокол маршрутизації не може працювати в умовах різкої зміни інтенсивності потоків трафіка, а також зміни конфігурації мережі та врахування декількох метрик визначення оптимального шляху. У зв'язку з цим виникає необхідність в інших підходах до маршрутизації в комп'ютерних мережах залізничного транспорту, зокрема з використанням мультиагентних методів інтелектуальної оптимізації: мурашиний алгоритм, бджолиний алгоритм, метод часток, метод переміщення бактерій та інші [1-11, 14, 15]. 

Одним із найбільш розповсюджених є мурашиний алгоритм, першу версію якого запропонував Марко Доріго [9]. 

У подальшому мурашиний алгоритм для отримання розв'язку різних задач використовували такі вчені: Б. Бульнхаймер, K. Гамбарделла, С. Глушко, А. Павленко, Р. Хартл, Х. Хоос, Біологічний аналог. Мурахи використовують два способи передачі інформації: прямий -обмін їжею, візуальні й хімічні контакти, і непрямий -стигмержі [9]. Стигмержі (stigmergy)це відокремлений у часі тип взаємодії, коли один суб'єкт змінює деяку частину навколишнього середовища, а інші використовують інформацію про його стан пізніше, коли перебувають у його межах. Біологічно стигмержі здійснюється через феромон -спеціальний секрет, який мурахи відкладають як слід під час переміщення [6]. Феромон (pheromone) -досить стійка речовина, його мурахи можуть сприймати кілька діб. Чим вища концентрація феромону на шляху, тим більше мурах буде по ньому рухатися. Із часом феромон випаровується, що дозволяє мурахам адаптувати свою поведінку під зміну зовнішнього середовища. Розподіл феромону по простору пересування мурах є свого роду динамічно-змінною глобальною пам'яттю мурашника. 

Будь-яка мураха у фіксований момент часу може сприймати й змінювати лише одну локальну комірку цієї глобальної пам'яті [6]. Самоорганізована система базується як на позитивному (інші мурахи укріплюють феромонну тропу) так і на негативному (випаровування феромонної тропи) зворотному зв'язку, рис. 2. Математичний апарат. Робота починається з розміщення мурах у вершинах графа, потім відбувається рух мурах -напрям визначають імовірнісним методом на підставі відомої формули:
section_name: Вступ

section_content: Кількість феромону, який був залишений на кожному ребрі шляху для мурахи k, розраховують за допомогою формули:

Для збільшення кількості феромону вздовж кожного ребра пройденого мурахою шляхом, отриманий результат обчислюється за формулою:

Випаровування феромону визначають за формулою:

Програмна реалізація мурашиного алгоритму виконана мовою Python з використанням фреймворку для віконних інтерфейсів Qt, а також бібліотек NetworkХ та Matplotlib для відображення графів на екран та визначення оптимального маршруту в мережі [3]. У програмі створені класи: NetworkХ, що дозволяє представляти мережу як граф, та ACO (Ant Сolony Оptimization) для роботи з алгоритмом мурашиної оптимізації. 

Вхідні параметри моделі: n -кількість маршрутизаторів; graph -матриця суміжності ме-режі; iteration -кількість ітерацій; antsкількість мурах у колонії; elite_ants -кількість елітних мурах; phero_lvl -початковий рівень феромону; ro -коефіцієнт випаровування; qпараметр для регулювання величини відкладення феромону. 

Результати роботи моделі подають у вигляді графів (Figure1, Figure2) із зображенням на них оптимальних шляхів: за критерієм сумарної затримки на маршрутизаторах (для першої колонії мурах) та кількістю хопів (для другої колонії мурах). 

Обмеження, які накладають на програмну модель: коефіцієнт випаровування набуває значення між 0 та 1 (включно); кількість елітних та звичайних мурах не обмежена. Визначено, що за n > 20 (кількість маршрутизаторів у мережі) та iterations > 10 000 (кількість ітерацій) програмна модель починає працювати помітно повільніше. Загальна структура програмної моделі «Two-ACO» подана на рис. 3 [3]. 

У програмі створений клас Network, який дозволяє представляти комп'ютерну мережу як граф. Клас має такі властивості: routers_num, що показує кількість маршрутизаторів у графі; graph -матриця суміжності для графа мережі; cost -функція, яка приймає два номери маршрутизаторів як аргументів та повертає затримку. 

Клас ACO (Ant Colony Optimization) -клас для роботи з алгоритмом мурашиної оптимізації, що має такі властивості: iterations -кількість ітерацій алгоритму; ants -кількість звичайних мурах у колонії; elite_ants -кількість елітних мурах у колонії; phero_lvl -початковий рівень феромону; a -величина, що визначає «жадібність» алгоритму; b -величина, що визначає «стадність» алгоритму; ro -величина, що визначає «швидкість» випаровування феромону; q -параметр для регулювання величини відкладення феромону, а також такі функції: init_pherо -установлює початкову кількість феромону в мережі; calculate_probs -розраховує можливості передачі даних між сусідніми маршрутизаторами; recalculate_phero -функція для коригування рівня феромону, залишеного звичайними мурахами; recalculate_elite_pheroфункція для коригування рівня феромону, залишеного елітними мурахами; path -функція, що визначає найкращий шлях між двома маршрутизаторами.
section_name: Рис. 2. Прокладання маршруту на основі феромону

section_content: За програмною моделлю «Two-ACO» проведені дослідження кількості ітерацій, необхідних для пошуку оптимального шляху, за параметрами алгоритму. Чим більше агентів, тим менша кількість ітерацій для знаходження оптимального шляху (рис. 6), для досліджуваної мережі двох мурах на вершину достатньо. 

У разі 30 агентів оптимальне значення феромону, який вони відкладають, близьке до одиниці (риc. 7). 

Проведемо дослідження кількості ітерацій за коефіцієнтом випаровування феромону в разі 30 агентів та визначеної кількості феромону, відкладеного на ребрах графа. Чим вище його значення, тим менше ітерацій пошуку оптимального шляху в комп'ютерній мережі із 15 маршрутизаторів та 17 каналів (рис. 8).
section_name: Результати

section_content: Усі дослідження проведено для гіпотетичної комп'ютерної мережі із 7 маршрутизаторами та 17 каналами, при цьому: початковий рівень феромону дорівнює -1; кількість звичайних мурах -7; кількість елітний мурах 1. Граф такої мережі представлений на рис. 9 (значення затримок на маршрутизаторах подано в мкс). 

Рис. 9. Граф мережі, на якому проведено дослідження
section_name: Наукова новизна та практична значимість

section_content: Для організації маршрутизації в комп'ютерних мережах можна використовувати мурашиний алгоритм, до основних положень якого належать: стигмержі (stigmergy) та феромон (pheromone). Поведінка мурах може мати різний математичний опис, тому існують такі модифікації: метод мурашиних систем, який використовує елітну стратегію; метод мурашиних систем, заснований на ранжуванні; метод системи мурашиних колоній; максімінний метод мурашиних систем; метод мурашиних колоній зі стратегією королеви. Для подальшої роботи обрано метод мурашиних колоній з елітною стратегією, а для його реалізації -мову Python із широким спектром сучасних стандартних засобів. 

1. Для визначення оптимального маршруту в комп'ютерній мережі за мурашиним алгоритмом елітної стратегії створена мовою Python програмна модель «Two-ACO», вхідні параметри якої: кількість маршрутизаторів у мережі; матриця суміжності мережі та параметри мурашиного алгоритму (кількість ітерацій алгоритму; кількість звичайних та елітних мурах у колонії; початковий рівень феромону, коефіцієнт випаровування; параметр для регулювання величини відкладеного феромону мурахами на ребрах графа мережі). 

2. За створеною програмною моделлю «Two-ACO» для гіпотетичної комп'ютерної мережі (із 7 маршрутизаторів та 17 каналів) проведено дослідження часу визначення оптимального шляху за кількістю звичайних та елітних мурах, значень коефіцієнта випаровування та відкладеного феромону. З'ясовано, що достатньо використовувати кількість мурах, що дорівнює кількості маршрутизаторів, мати в колонії 2 елітних мурах, при цьому вистачає 1 000 ітерацій, коефіцієнта випаровування від 0,2 до 0,7, а значення відкладеного феромону мурахами близького до одиниці. 

3. Визначено оптимальний маршрут у комп'ютерній мережі залізничного транспорту (із 15 маршрутизаторів та 17 каналів) на основі моделі «Two-ACO» з використанням двох колоній мурах за такими критеріями: загальною затримкою на маршрутизаторах (для першої колонії мурах) та кількістю хопів, що складають маршрут (для другої колонії мурах). Установлено, що достатньо мати 30 агентів (двох мурах на вершину), значення феромону, відкладеного агентами, близьке до одиниці, при цьому коефіцієнт випаровування складає 0,4. СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
section_name: Висновки

section_content: Purpose. At present, the computer networks of the information and telecommunication system (ITS) of railway transport use the OSPF protocol, which does not allow taking into account several metrics when determining the optimal route. Therefore, there is a need to study the possibility of organizing routing in computer networks of rail transport ITS using a two-colonial ant algorithm. Methodology. According to the Two-ACO software model, created in the Python language based on the two-colonial ant algorithm, the optimal route in a computer network was determined. Two-ACO model inputs: computer network parameters (network adjacency matrix, number of routers); parameters of the ant algorithm (number of iterations; number of ants in the colony; number of elite ants; initial pheromone level; evaporation rate; parameter for adjusting the amount of pheromone deposition). Findings. The results of the Two-ACO model are presented in the form of graphs depicting the optimal paths: the criterion of the total delay on the routers (for the first colony of ants) and the number of hops (for the second colony of ants). Originality. According to the created Two-ACO software model for a computer network of 7 routers and 17 channels, a study of the time for determining the optimal path in a computer network by the number of ordinary and elite
section_name: Software Model for Determining the Optimal Routes in a Computer Network Based on the Two-Colonial Ant Algorithm