Маршрутизация в беспроводных mesh сетях на основе генетических алгоритмов

Автор: Чабанный А.А.
Источник: Автоматизація технологічних об’єктів та процесів. Пошук молодих. Збірник наукових праць ХІI науково-технічної конференції аспірантів та студентів в м. Донецьку 17-20 квітня 2012 р. - Донецьк, ДонНТУ, 2012.

В данной работе предлагается новый способ построения маршрутов для протокола маршрутизации Optimized Link State Routing Protocol (OLSR). Данный протокол используется как в беспроводных мобильных ad-hoc сетях, так и в беспроводных стационарных mesh сетях. В соответствии со стандартом [1] в данном протоколе используется в качестве метрики количество переприемов, а маршрут строится последовательно: сначала к соседним узлам, а затем от соседей до их соседей и так далее. Это построение возможно, так как узлы имеют полную топологическую базу сети. В данной работе предлагается построение маршрута на основе генетических алгоритмов (ГА). В их основе лежит использование эволюционных принципов для оптимального решения [2]. Сам принцип ГА заключается в следующем: сначала формируется первоначальная популяция, затем к этой популяции применяются операции кроссинговера и мутации, после чего происходит формирование новой популяции. Так продолжается итерационно до тех пор, пока не будет выполнено заданное количество итераций или выполнено условие прекращения поиска. Кодирование маршрута. Каждая хромосома представляет собой существующий маршрут от источника к получателю. Каждый локус хромосомы содержит узел, принадлежащий выбранному маршруту. Пример представлен на рис.1, где S это источник, N1,…, Nk – узлы маршрута, D – узел назначения, l – порядковый номер локуса.

Формирование хромосомы происходит случайным образом при этом первый узел хромосомы это источник. Последующие узлы выбираются на основе топологической базы при этом выбранный узел должен иметь непосредственное соединение с узлом являющимся последним в хромосоме на текущий момент. Все узлы выбранные в данную хромосому запрещены для дальнейшего выбора, это сделано для предотвращения формирования петель в маршруте. При достижении узла назначения формирование хромосомы заканчивается, а данный узел заносится в хромосому. При таком формировании путей хромосомы могут иметь переменную длину.

Формирование первоначальной популяции происходит случайным образом, в результате чего формируется n хромосом то есть популяция.

Фитнес функция. Для оценки качества пути используется следующая функция:

где, DT_i (Delay Time) задержка i линии данного маршрута, а TSR_i (Transmission Success Ratio) доля успешно переданных пакетов через i линию данного маршрута. Чем меньше значение фитнесс функции тем лучшим считается маршрут.

Оператор отбора (селекция) предназначен для формирования набора родительских хромосом для последующего кроссинговера. Отбор тем самым фокусируется на исследовании перспективных областей в пространстве решений. В данной работе выбрана турнирная селекция с размером турнира равным двум. Это способствует более случайному выбору родительских хромосом для кроссинговера. Из родительской популяции случайным образом выбираются две хромосомы и сравниваются и фитнесс функции, та хромосома у которой значение фитнесс функции меньше заносится в специальную базу из которой в дальнейшем может быть выбрана для кроссинговера.

Кроссинговер. Кроссинговер предназначен для формирования новых маршрутов в результате обмена двух выбранных родительских хромосом частями маршрута. На рис. 2 представлен пример осуществления операции кроссинговера.

В данном алгоритме предлагается использовать одноточечный кроссинговер. Механизм работы следующий: сначала из отобранных родительских хромосом, турнирным способом, выбираются случайно две хромосомы для кроссинговера; затем в выбранных хромосомах происходит поиск одинаковых узлов; после этого из набора найденных одинаковых узлов выбирается одна случайная пара для кроссинговера в результате чего получается две новых хромосомы. Это продолжается до тех пор пока не будет образовано n новых хромосом.

В результате кроссинговера могут образовываться петли в новых хромосомах. Для исправления этого используется функция восстановления. Она начинает одновременно просматривать хромосому сначала и с конца, сравнивая узлы маршрута, если будет найдено два одинаковых узла, которые находятся в разных локусах, то все узлы между этими двумя одинаковыми узлами будут удалены, а они будут объединены в один узел. В результате в хромосоме удаляются петли.

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

После осуществления всех выше перечисленных операций происходит формирование нового поколения. Для формирования нового поколения используется стратегия элитизма. В этом случае часть сформированного нового поколения с наихудшей фитнесс функцией заменяется частью родительских хромосом с наилучшей фитнесс функцией. Такая стратегия позволяет сохранять хорошие маршруты даже в случае если в результате кроссинговера будут образовываться маршруты с плохим значением фитнесс функции.

Выводы. В данной работе представлен алгоритм нахождения оптимального пути на основе ГА. В качестве критерия эффективности используется комбинированная функция задержки и доли успешно доставленных пакетов. В дальнейшем планируется реализация данного алгоритма в одном из пакетов моделирования для проверки и сравнения его эффективности с алгоритмом построения маршрута по умолчанию в OLSR.