Об использовании эволюционных алгоритмов для построения топологии беспроводной mesh–сети

Аннотация

Калабухов Е.Р., Рудаков Д.Ю., Богоченко С.В. Харитонов Р.И. Об использовании эволюционных алгоритмов для построения топологии беспроводной mesh–сетиВ рамках данной работы предполагается выделить основные положения разработки алгоритма расположения узлов mesh-сети (на основе беспроводных стандартов связи) с целью оптимального их расположения.

Общая постановка проблемы

В последние годы беспроводные широкополосные сети на основе технологии Wi–Fi получили очень широкое распространение [1]. Существуют различные типы беспроводных сетей на основе стандарта IEEE 802.11, которые отличаются радиусом действия, поддерживаемыми скоростями соединения, технологией кодирования данных и другими показателями, однако наиболее многообещающей и перспективной является спецификация 802.11s, которая описывает технологию mesh–сетей. Основной проблемой функционирования mesh–сетей является их невысокая производительность (по сравнению с проводными технологиями). Причем увеличение числа пользователей и самих mesh–станций приводит к пропорциональной деградации показателей качества обслуживания (Quality of Service, QoS) [2].

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

Рисунок 1 – Пример Mesh топологии

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

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

Эволюционные алгоритмы включают в себя генетические алгоритмы, эволюционную стратегию, эволюционное программирование, алгоритмы дифференциальной эволюции, а также генетическое программирование [3].

Суть парадигмы эволюционных алгоритмов состоит в использовании базовых принципов теории биологической эволюции – отбора, мутации и воспроизведения особей. Эволюционные алгоритмы являются частью более широкой технологии мягких вычислений, включающих в себя ещё нечеткую логику, нейронные сети, вероятностные рассуждения и сети доверия. Данные технологии дополняют друг друга и используются в различных комбинациях или самостоятельно для создания интеллектуальных систем [4].

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

Генетические алгоритмы перед другими методами оптимизации обладают следующими преимуществами:

• не требуют предварительной информации и поведении функции
• устойчивы стойки к попаданию в локальные оптимумы
• просты в реализации
• применимы для широкого класса задач
• пригодны для решения крупномасштабных проблем оптимизации
• могут быть использованы в задачах с изменяющейся средой

Для применения генетических алгоритмов необходимо прежде всего выбрать функцию пригодности адекватную задаче. Причем целевая функция должна иметь разнообразный рельеф, так как если на поверхности функции есть большие плоские участки, то алгоритм не эффективен. Эта проблема известна как «проблема поля для гольфа», где все пространство абсолютно одинаково, за исключением лишь одной точки, которая и является оптимальным решением – в этом случае генетический алгоритм остановится и будет выполняться абсолютно случайно. На сегодняшний день генетические алгоритмы в основном используются для решения задач, как:

• поиск глобального экстремума многопараметрической функции
• аппроксимация функций
• задачи о кратчайшем пути
• задачи размещения
• настройка искусственной нейронной сети
• обучение машин
• игровые стратегии

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

Выделим основные этапы разработки алгоритма построения топологии беспроводной mesh–сети:

• проведение системного анализа предметной области
• формирование модели оценки производительности беспроводной mesh–сети
• используя тот или иной эволюционный алгоритм, апробация на тестовых задачах
• применение выбранного эволюционного алгоритма для решения оптимизационной задачи построения беспроводной mesh–сети

Практическая значимость данной работы (разработки алгоритма) состоит в возможном использовании исследуемой mesh–топологии в построении беспроводных сетей передачи данных, в развертываемых системах «умного города», в автономных системах, где требуется связать множество датчиков, приборов по беспроводным каналам связи. Также mesh–топология может найти применение для организации связности между спутниками в космическом пространстве и для связности сети беспилотных летательных средств.

Список использованной литературы

1. Осипов И.Е. Mesh–сети: технологии, приложение, оборудование. – Режим доступа: http://www.dateline.ru/resources/mesh–osipov.pdf.
2. Сравнительный анализ критериев оптимальности распределения частотных каналов в mesh–сети IEEE 802.11 / С.В.&nbs;Гаркуша, Е.В. Гаркуша // Системы управления навигации и связи. – 2012. – Вып. 4(24) – С. 125–131.
3. Метаэвристические алгоритмы поиска глобального экстремума / А.В. Пантелеев. – М.: МАИ–ПРИНТ, 2009. – 160 с.
4. Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы / А.В. Пантелеев, Д.В. Метлицкая, Е.А. Алешина. – М.: Вузовская книга, 2013. – 244 с.: ил.