Програмна модель для визначення оптимальних маршрутів у комп’ютерній мережі за двоколоніальним мурашиним алгоритмом
Loading...
Date
2021
Journal Title
Journal ISSN
Volume Title
Publisher
Дніпровський національний університет залізничного транспорту імені академіка В. Лазаряна, Дніпро
Abstract
UK; Мета. На сучасному етапі в комп’ютерних мережах інформаційно-телекомунікаційної системи (ІТС) за-лізничного транспорту використовують протокол OSPF, який не дозволяє враховувати декілька метрик під час визначення оптимального маршруту. Тому ми ставимо за мету дослідити можливість організації марш-рутизації в комп’ютерних мережах ІТС залізничного транспорту за допомогою двоколоніального мураши-ного алгоритму. Методика. За програмною моделлю «Two–ACO», створеною мовою Python за двоколоніа-льним мурашиним алгоритмом, визначено оптимальний маршрут у комп’ютерній мережі. Вхідні дані моделі «Two–ACO»: параметри комп’ютерної мережі (матриця суміжності мережі, кількість маршрутизаторів); па-раметри мурашиного алгоритму (кількість ітерацій; кількість мурах у колонії; кількість елітних мурах; поча-тковий рівень феромону; коефіцієнт випаровування; параметр для регулювання величини відкладеного фе-ромону). Результати. Визначення за програмною моделлю «Two-ACO» оптимального маршруту подано у вигляді графів із зображенням на них оптимальних шляхів: за критерієм сумарної затримки на маршрути-заторах (для першої колонії мурах) та кількістю хопів (для другої колонії мурах). Наукова новизна. За створеною програмною моделлю «Two–ACO» для комп’ютерної мережі із 7 маршрутизаторів та 17 каналів проведено дослідження часу визначення оптимального шляху за кількістю звичайних та елітних мурах, зна-ченнями коефіцієнта випаровування та відкладеного феромону. Установлено, що достатньо використовува-ти кількість мурах, що дорівнює кількості маршрутизаторів, мати в колонії 2 елітних мурах, при цьому ви-стачає 1 000 ітерацій, коефіцієнта випаровування від 0,2 до 0,7, а відкладеного феромону мурахами близько-го до одиниці. Практична значимість. Створена програмна модель «Two–ACO» з використанням двох ко-лоній мурах за загальною затримкою на маршрутизаторах та кількістю хопів, що складають маршрут, дозволяє паралельно визначити оптимальні маршрути в комп’ютерній мережі залізничного транспорту. З’ясовано, що для комп’ютерної мережі з 15 маршрутизаторів та 17 каналів достатньо мати 30 агентів (двох мурах на вершину), значення феромону, відкладеного агентами, близьке до одиниці, при цьому коефіцієнт випаровування складає 0,4.
EN; 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, creat-ed in the Python language based on the two-colonial ant algorithm, the optimal route in a computer network was de-termined. 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 chan-nels, a study of the time for determining the optimal path in a computer network by the number of ordinary and elite 48 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 us-ing 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.
EN; 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, creat-ed in the Python language based on the two-colonial ant algorithm, the optimal route in a computer network was de-termined. 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 chan-nels, a study of the time for determining the optimal path in a computer network by the number of ordinary and elite 48 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 us-ing 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.
Description
В. Пахомова: ORCID 0000-0002-0022-099X; А. Опрятний: ORCID 0000-0001-7145-9677
Keywords
залізничний транспорт, комп’ютерна мережа, маршрутизатор, затримка, двоколо-ніальний мурашиний алгоритм, феромон, відкладання, випаровування, час пошуку, railway transport, computer network, router, delay, two-colonial ant algorithm, pheromone, deposi-tion, evaporation, search time, КЕОМ
Citation
Пахомова В. М., Опрятний А. О. Програмна модель для визначення оптимальних маршрутів у комп’ютерній мережі за двоколоніальним мурашиним алгоритмом. Наука та прогрес транспорту. 2021. № 3 (93). С. 38–49. DOI: 10.15802/stp2021/242046.