Литвиненко І.А., Котінов О.Л., Грищенко О.Л., Косенко Н.М.,

Хижняк Д.С., Голосков А.С., Люта М.В.

Київський національний університет технологій та дизайну

Використання мурашиних алгоритмів в маршрутизації потоків даних в телекомунікаційних системах

Вступ

В автономних системах для розвитку задач оптимальної маршрутизації використовують дистанційно-векторні методи та протоколи, які враховують стан каналу як за пропускною здатністю, так і за часовою затримкою пакетів. Наприкінці ХХ сторіччя, інтенсивно розробляється науковий напрямок Natural  Computing - «Природні обчислення», що об'єднує математичні методи, в яких закладені принципи природних механізмів прийняття рішень [1].

Постановка завдання

В роботі запропоноване запозичення мурашиних алгоритмів для розв’язку актуальних задач доставки пакетів  найкоротшим шляхом в  автономних системах телекомунікації. На цьому шляху важливі  врахування реальної динаміки ТКС, так і адаптація до різних чинників невизначеності.

Дослідження в цій області почалися в середині 90-х років XX століття, автором ідеї є Марко Доріго з Університету Брюсселя, Бельгія

Поняття про мурашині алгоритми

Мурахи відносяться до соціальних комах, що створює колективи. У біології колектив мурах називається колонією. Число мурах в колонії може досягати декількох мільйонів, Одним з підтверджень оптимальності поведінки колоній є той факт, що мережа гнізд суперколоній блізка до мінімального остовного дерева Основу поведінки мурашиної колонії становить самоорганізація, що забезпечує досягнення загальних цілей колонії на основі низькорівневого взаімодействія. Колонія немає централізованого управління, і її особливостями є обмін локальної інформацією тільки між окремими особинами (прямий обмін-їжа, візуальні та хімічні контакти) та наявність непрямого обміну, який і використовується в мурашиних алгоритмах [2].

Непрямий обмін стігмержі (stigmergy), являє собою рознесене в часі взаємодію, при якому одна особина змінює деяку область навколишнього середовища, а інші використовують цю інформацію пізніше, в момент, коли оні в неї потрапляють. Біологи встановили, що таке відкладене взаємодія відбувається через спеціальне хімічна речовина-феромон (pheromone),секрет спеціальних залоз, відкладається при переміщенні мурахи. Концентрація феромона на стежці визначає перевагу руху по ній. Адаптивність поведінки реалізується випаровуванням феромона, який в природі сприйнятий-мається мурахами протягом декількох діб.

Перевага такої системи поведінки в тому, що використовується тільки локальна інформація, без централізованого керування та звернення до глобального образу.

Ідея мурашиного алгоритму - моделювання поведінки мурах, пов'язане з їх здатністю швидко знаходити найкоротший шлях від мурашника до джерела їжі і адаптуватися до мінливих умов, знаходячи новий найкоротший шлях. При своєму русі мураха мітить свій шлях феромоном, і ця інформація використовується іншими мурашками для вибору шляху. Це елементарне правило поведінки і визначає здатність мурашок знаходити новий шлях, якщо старий виявляється недоступним. Дійшовши до перепони, мурахи з однаковою ймовірністю будуть обходити її праворуч і ліворуч. Те ж саме буде відбуватися і на зворотному боці перешкоди. Однак, ті мурахи, які випадково виберуть найкоротший шлях, будуть швидше його проходити, і за кілька пересувань він буде більш збагачений феромоном. Оскільки рух мурашок визначається концентрацією феромону, то наступні будуть віддавати перевагу саме цей шлях, продовжуючи збагачувати його феромоном, до тих пір, поки цей шлях з якої-небудь причини не стане доступний. Очевидна позитивний зворотний зв'язок швидко призведе до того, що кратчайшій шлях стане єдиним маршрутом руху більшості мурашок [3].

Ця проблема вирішується завдяки випаровуванню феромона. Час випаровування не повинен бути дуже великим, тому що виникає загроза збігання мурах до одного оптимального маршруту, але він не повинен бути і дуже малим, щоб не втратити пам'ять колонії, і не втратити найкращі розв’язки задачі.

Тепер з врахуванням особливостей задачі комівояжера, ми можемо описати властивості і правила поведінки мурах при виборі шляху.

1.                   Кожна мураха володіє власною «пам’яттю», де буде зберігатись список міст Ji,k, які потрібно пройти мурасі k, яка знаходиться в місті i. Об’єднання списків дає множину всіх міст з маршруту комівояжера.

2.                   Мурахам властива «видимість» – величина обернена до відстані:

ηij=1/Dij,

де Dij – відстань між містами i та j.

3.                   Кожна мураха здатна сприймати слід феромону, який буде визначати бажання мурахи пройти по даному маршруту. Рівень феромону в момент часу t на маршруті Dij буде відповідати τij(t).

4.                   Ймовірність переходу k-ї мурахи з міста i у місто j на i-й ітерації розраховується за випадково пропорційним правилом:

де α і β – регульовані параметри, які є показниками інтенсивності сліду феромону та видимості. Якщо α=0, то най вірогіднішим буде перехід у найближчі міста. Якщо β=0, тоді працює лише феромонне підсилення, що призводить до швидкого завершення роботи алгоритму через збігання маршрутів усіх мурах до одного субоптимального розв’язку.

5.                   Після проходження ребра (i,j), кожна мураха k відкладає на ньому таку кількість феромону:

де Tk(t) маршрут вибраний мурахою на i-й ітерації; Lk(t) – довжина цього маршруту; Q – регульований параметр, який має значення порядка довжини оптимального шляху.

Інтенсивність випаровування феромона визначається наступним правилом:

де m – кількість мурах; p – коефіцієнт випаровування (0≤ p≤1), визначаючий долю феромонів, що залишились після кожної ітерації.

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

Можна виділити основні переваги даного алгоритму, а саме:

-           відносно ефективний при розв’язуванні задачі комівояжера (при невеликій кількості вузлів може бути розв’язана повним перебором, а при великій кількості – задача є повною NP)

-           працює краще ніж інші задачі глобальної оптимізації для задачі комівояжера (нейронні мережі, генетичні алгоритми)

-           може використовуватись в динамічних додатках

-           використовується для розв’язання багатьох різних задач.

Але, як і у всіх інших алгоритмах, там де є переваги є і недоліки:

-           важкий теоретичний аналіз

-           збіжність гарантується, але час збіжності не визначено

-           дуже залежить від початкових даних, які підбираються експериментально.

Висновки

Оскільки поведінка комах є наближеною до оптимальної, завдяки їх взаємодії і використання лише локальної інформації без звернення до централізованого образу, то цю ідею можна використати при маршрутизації потоків даних в телекомунікаційних системах. Перевагою даного методу є те, що його можна використовувати в системах, які змінюються у часі.

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

 

СПИСОК ЛІТЕРАТУРИ:

1.  Штовба С.Д., Рудий О.М. Мурашині алгоритми оптимізації//”Вісник ВПІ”,2004, № 4, с.62-69.

2.  Олифер В. Г., Олифер Н. А. Компьютерные сети. Принципы, технологии, протоколы.3-е изд. СПб.: Питер, 2008.

3.  Колесніков К.В., Бутенко Я.С., Лега Ю.Г. Моделі та методи маршрутизації потоків даних в телекомунікаційних системах із змінною динамікою//”Вісник ЧДТУ”, 2006, №1, с.44-49.

4.      Уолренд Дж. Телекоммуникациионные и компьютерные сети. Вводный курс. М.: Постмаркс, 2001.

5.  Столлингс В.   Современные   компьютерные сети. СПб: «Питер», 2003. 783 с.