автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка метода маршрутизации для беспроводной ячеистой сети с учетом качества обслуживания

На правах рукописи

Иванов Дмитрий Викторович

Разработка метода маршрутизации для беспроводной ячеистой сети с учетом качества обслуживания

Специальность - 05.13.13 Телекоммуникационные системы и компьютерные сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

,1 7 дек 2003

Москва 2009 г.

003488925

Работа выполнена в государственном образовательном учреждении высшего профессионального образования "Московский государственный университет путей сообщения (МИИТ)"

Научный руководитель: кандидат технических наук, профессор

Соловьев Владимир Павлович

Официальные оппоненты: доктор технических наук, профессор

Корниенко Анатолий Адамович

кандидат технических наук, доцент Крепков Игорь Михайлович

Ведущая организация: Институт системного анализа

Российской Академии Наук (ИСА РАН)

Защита состоится "10" декабря 2009 г. в 16 час. 30 мин. на заседании диссертационного совета Д 218.005.10 при Московском государственном университете путей сообщения по адресу: 127994, г. Москва, ул. Образцова, д. 9, строение 9, ауд. 1235.

С диссертацией можно ознакомиться в библиотеке Московского государственного университета путей сообщения (МИИТ).

Автореферат разослан ноября 2009 г.

Ученый секретарь диссертационного совета к.т.н., профессор

л

Соловьев В.П.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность ■

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

Однако существующие протоколы маршрутизации, в том числе стандарта IEEE 802.11, не были спроектированы с учетом ячеистой топологии и не учитывают возможность многомаршрутной передачи данных. Кроме того, мультимедийные приложения занимают все большую долю среди пользовательских приложений. Как следствие, происходит смещение фокуса от сервисов доставки данных без гарантий к сервисам, обеспечивающим качество обслуживания (Quality of Service, QoS) в беспроводных сетях.

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

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

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

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

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

Задачи работы:

1. Анализ среды функционирования беспроводных ячеистых сетей, в том числе классификация параметров состояния каналов связи и узлов, которые можно принимать во внимание при оценке потенциальных маршрутов передачи данных, и классификация показателей качества обслуживания.

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

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

4. Разработка метода оптимизации параметров работы предложенного метода маршрутизации для заданного сценария функционирования сети.

5. Реализация разработанных алгоритмов и построение модели предлагаемого метода маршрутизации.

6. Проведение модельных экспериментов для оценки эффективности его работы с точки зрения качества обслуживания.

Методы исследования.

Для решения поставленных задач были использованы методы теории вероятностей, аппарата нечеткой логики, теории многокритериальной оптимизации, теории стохастической оптимизации (генетические алгоритмы). При разработке программного обеспечения использован объектно-ориентированный подход.

Научная новизна работы.

Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, прежде всего, составляют:

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

• Метод многокритериальной оптимизации параметров метода маршрутизации, построенный на основе генетического алгоритма.

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

Достоверность результатов работы подтверждена серией модельных ■ экспериментов.

Основные практические результаты, выносимые на защиту:

• Разработанный протокол маршрутизации для беспроводных ячеистых сетей по требованию, который позволяет находить множество всех доступных маршрутов передачи данных и передавать параметры состояния узлов и каналов связи.

• Разработанный метод маршрутизации для беспроводных ячеистых сетей на основе аппарата нечеткой логики, который опирается на указанный выше протокол маршрутизации.

• Разработанный метод многокритериальной оптимизации параметров предложенного метода маршрутизации, построенный на основе генетического алгоритма.

• Разработанная модель предложенного метода маршрутизации.

• Результаты, полученные в ходе проведения модельных экспериментов.

Реализация результатов работы.

Результаты были применены в ОАО "Российская телекоммуникационная сеть" в проекте по тестированию и подготовке к эксплуатации на территорий г.Москвы беспроводной ячеистой сети с целью снижения средней задержки передачи и доли потерянных пакетов.

Апробация работы.

Основные положения диссертационной работы докладывались и обсуждались на заседаниях кафедры "Математическое обеспечение автоматизированных систем управления" МИИТа в 2005-2009 гг., а также на следующих научных конференциях:

• Пятая международная научно-практическая конференция "Тгапэ-МесЬ-АЛ-СЬега". Москва, МИИТ, 2008 г.

• Шестнадцатая межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика". Зеленоград, МИЭТ, 2009 г.

• Шестая международная научно-практическая конференция "Trans-Mech-Art-Chem". Польша, Радом, 2009 г.

Публикации.

По теме диссертации опубликовано 5 печатных работ. Структура и объем работы.

Диссертация состоит из введения, четырех глав и заключения. Диссертация содержит 163 страницы, 52 рисунка и 6 таблиц. Список литературы насчитывает 55 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновываются актуальность исследуемой в диссерта-циии проблемы, формулируются основные цели и задачи исследования.

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

Далее в главе отмечается, что метод маршрутизации при выборе оптимального маршрута может учитывать целый ряд параметров состояния узлов и каналов связи на потенциальных маршрутах. Были выделены и проанализированы следующие параметры (в скобках указаны единицы измерения): доступная пропускная способность на маршруте передачи данных (бит/с), задержка передачи пакета на маршруте от узла источника до узла назначения (с), размер пакетного буфера узла (количество пакетов), вариация задержки на потенциальном маршруте передачи пакета (с), доля потерянных пакетов (в процентах), энергозатраты (Вт), относительная мобильность/стабильность узла, отношение сигнал-шум (SIR, Signal-noise ratio) (дБ), доля битовая ошибок (в процентах).

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

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

Отмечается, что наиболее важными показателями качества обслуживания являются два показателя: средняя задержка передачи пакета и доля потерянных пакетов для всей сети. Они определяют комфорт работы пользователя в беспроводной сети.

В процессе исследования также анализируются основные подходы к построению протоколов маршрутизации: реактивные, проактивные и гибридные протоколы. В оставшейся части главы проводится анализ существующих методов маршрутизации для беспроводных ячеистых сетей с учетом качества обслуживания: OLSR, AODV. QOLSR, ODCR, Application aware QoS routing, Cross-layer ACOR, AQOR. В результате анализа сделан вывод, что существующие решения имеют ряд недостатков, а именно:

• Учитывают малое количество параметров при оценке пригодности каналов связи и маршрутов передачи данных.

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

• Не предоставляют возможностей оптимизации параметров работы под заданный сценарий функционирования сети.

В заключении главы, опираясь на результаты проведенного исследования проблемы, раскрываются цели и задачи диссертационной работы:

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

•• Улучшение двух показателей качества обслуживания - доли потерянных пакетов и средней задержки передачи пакета - для всей сети в целом.

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

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

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

Таким образом, предлагаемый метод маршрутизации в беспроводных ячеистых сетях состоит из двух этапов:

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

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

Следовательно, разработка всего метода маршрутизации разбивается на три подзадачи:

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

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

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

Для поиска потенциальных маршрутов передачи данных и сбора значений параметров состояния каналов связи и узлов был разработан реактивный протокол маршрутизации от источника, названный ODSR (Оп-Demand Source Routing, Маршрутизация от источника по требованию),

алгоритм работы которого будет рассмотрен ниже. Реактивный протокол маршрутизации был выбран по причине его лучшей масштабируемости в больших ячеистых сетях. Маршрутизация от источника означает, что при отправке пакета данных узел сам записывает в него полный маршрут (все промежуточные узлы), по которому нужно передать пакет. Каждый из промежуточных узлов извлекает адрес следующего узла на маршруте и передает ему пакет, в результате чего пакет и достигает узла назначения. Логика работы предлагаемого протокола маршрутизации состоит в следующем:

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

• Другие узлы, получая данный пакет 1Хои1е1^иез<;, проверяют, не являются ли они тем узлом, с которым запрашивающий узел хочет установить соединение. Если нет, то данный узел добавляет себя в список промежуточных узлов, через которые прошел пакет, и рассылает пакет дальше широковещательно. В противном случае, пакет достиг узла назначения, и данный узел отправляет ответ 11о1Ц;е11ер1у по маршруту, записанному в пришедшем пакете По^еБодиев^

• Если на узел приходит запрос Пот^еПодиев!;, но узел уже видел данный пакет ранее (его адрес есть в списке промежуточных узлов), он отбрасывает пакет для устранения петель маршрутизации.

• Когда приходит запрос на установление соединения, узел отправляет Р1о1^еВ*х}ие51 и устанавливает таймер ожидания ответов. В течение этого периода узел собирает полученные пакеты 11о1Ле11ер1у с различными маршрутами до узла назначения. При срабатывании таймера собранные маршруты передаются в контроллер нечеткой логики, который принимает решение, какой маршрут является оптимальным.

• После выбора оптимального маршрута узел записывает этот маршрут в таблицу маршрутизации на определенный период времени (кэ-ширует маршрут).

Пакеты 11оиЛе11ер1у с найденными маршрутами содержат помимо списка адресов промежуточных узлов значения различных параметров состояния узлов и каналов связи. Каждый промежуточный узел на маршруте вносит свой вклад в оценку всего маршрута. Следовательно, предлагаемый протокол маршрутизации позволяет решить возложенную на него задачу: поиск потенциальных маршрутов по требованию и сбор значений параметров состояния узлов и каналов связи. Далее в данной главе проводится анализ, какие параметры могут быть использованы на практике и как построить оценочные функции для них. В результате анализа были выбраны

следующие параметры состояния узлов и каналов связи, которые учитываются при оценке потенциальных маршрутов:

• Пропускная способность канала связи между двумя узлами. Модуль маршрутизации в стеке протоколов может запросить только значение номинальной пропускной способности канала связи у канального уровня. Значение доступной пропускной способности канальному уровню неизвестно. Поэтому был предложен метод определения доступной пропускной способности на основе механизма RTS-CTS. Узел А проводит мониторинг занятости среды за период TwatCh и по собранным данным вычисляет доступную пропускную способность канала связи до узла В как:

д _ В пот ' {Thatch ~ Тьизу Ttrans Trecv TnojSy 1node—b—nay)

£>res — rp )

■'■■watch

(1)

где Brcs - доступная пропускная способность канала, Вптп - номинальная пропускная способность канала, Twatch - период мониторинга состояния среды, Тъияу - период занятости среды, Tirana - период передачи данных, Trecv - период приема данных, Tnoisy - период, когда сигнал детектируется, но не может быть декодирован, Tno<ie-b-nav -период, когда среда для узла назначения В оказывается занятой.

Поскольку узел А не может знать значение Tnode-b-nav, то вычисление доступной пропускной способности канала связи между узлами А и В проводится совместно этими узлами. Когда узел А получает пакет Route Request, он записывает в него текущие значения T-watcht Tbusyi Ttrans, Trectii TnoiSy, Bnorrt и рассылает Route Request далее широковещательно. Каждый из получивших этот Route Request узлов (в том числе и В), добавляет свое значение Tnodc-b-nav, вычисляет Bres и записывает его в Route Request. Так как пропускной способностью всего маршрута считается минимум пропускной способности среди всех каналов на маршруте, то в пакете Route Request не передаются значения доступной пропускной способности для всех каналов связи, составляющих маршрут. Вместо этого после вычисления Brea узел сравнивает это значение с текущим минимумом, записанным в Route Request, и перезаписывает старое значение, если новое значение оказалось меньше. Таким способом производится вычисление доступной пропускной способности каждого из каналов связи и всего маршрута целиком.

• Задержка передачи пакета. Задержка в данном случае означает период времени, проходящий от момента отправки пакета на канальном уровне до момента прихода подтверждения о его получении от другого узла. Параметр „задержка передачи пакета" является ад-

дативным, поэтому когда на узел приходит запрос маршрутизации RouteRequest, то это значение просто прибавляется к текущему значению в пакете. Пакет Route Request будет содержать значение задержки передачи для всего маршрута, когда достигнет узла назначения.

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

Пусть маршрут состоит из п промежуточных узлов, относительная загруженность его буфера составляет U. Был введен весовой коэффициент для загруженности каждого узла в отдельности в составе суммарной загруженности:

Л, = М

i=l

Загруженность пакетных буферов узлов всего маршрута при этом вычисляется как:

п ¿=1

■Предлагаемая оценочная функция (3) позволяет учитывать относительную загруженность пакетного буфера каждого из узлов на маршруте. Таким образом, каждый из промежуточных узлов при получении пакета запроса на маршрутизацию Route Request вычисляет значение U и записывает его вместе с своим адресом в пакет. Когда узел-источник запроса Route Request получает ответ Route Reply, он извлекает все значения k для всех промежуточных узлов и вычисляет значение I для оценки загруженности маршрута, в Качество связи. Качество связи предлагается выражать через долю потерянных пакетов. Отмечается, что этот параметр учитывает и долю битовых ошибок, и отношение сигнал шум („плохие" значения обоих параметров ведут к потере пакетов). Узел может детектировать

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

Пусть доля потерянных пакетов для г-того узла составляет р{. Это значение является вероятностью того, что пакет при передаче с данного узла будет потерян. Вероятность того, что пакет будет отправлен без потерь составляет \ ~Pi- Следовательно, вероятность, что пакет дойдет до узла назначения, составляет:

где п - количество промежуточных узлов, - доля потерянных пакетов на г-том узле. ргеот является оценкой пригодности маршрута с точки зрения качества связи.

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

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

Каждому входному параметру контроллера сопоставляется лингвистическая переменная, имеющая пять термов:

• Доступная пропускная способность - „очень малая", „малая", „средняя", „высокая", „очень высокая".

• Задержка передачи пакета - „очень малая",,¡малая", „средняя", „высокая", „очень высокая".

• Загруженность пакетных буферов - „очень малая",,.малая", „средняя", „высокая", „очень высокая".

п

(4)

• Качество связи - „очень плохое", „плохое", „среднее", „высокое", ,рчень высокое".

• Количество промежуточных'узлов - ,рчень малое", „малое", „среднее", „высокое", „очень высокое".

Такое разбиение на термы достаточно хорошо детализирует лингвистическую переменную, и при этом не ведет к образованию чрезмерно огромной базы правил. В качестве функций принадлежности для каждого терма всех лингвистических переменных были выбраны треугольные функции принадлежности, поскольку, как показывает практика и исследования, они хорошо подходят для использования при решении широкого круга проблем управления. Выводом каждого правила импликации является лингвистическая переменная „рейтинг маршрута", множество значений которой также состоит из пяти термов от „очень малый" до „очень большой". База правил нечеткого вывода будет состоять из правил следующего вида: Если загруженность пакетных буферов ВЫСОКАЯ и доступная пропускная способность НИЗКАЯ и задержка передачи пакета ВЫСОКАЯ и качество связи СРЕДНЕЕ и количество промежуточных узлов БОЛЬШОЕ, то рейтинг маршрута ОЧЕНЬ НИЗКИЙ.

В качестве Т-нормы используется операция minimum, в качестве S-нормы - операция maximum:

т

/лА{х) * ив{х) - min{i±A{x),HB{x)). (5)

цА{х) *Цв{х) =тах(цА(х),цв{х))- (6)

Правило нечеткой импликации задается правилом Мамдани:

Я4-»в(я,у) = Мя(х,у) = Ma(z) Амв(у) = гтшг(/1А(я),Мв(у)), (7)

где А и В - нечеткие; множества, А С Х,В С Y, отношение R определено на X х У.

В результате получаем, что:

Ке' (у) = тах^{тт[иАь (xi), цА* (¿г), (¿з),/^ О^),/^ (^5 )фв(у)]},

(8)

где х\, Х2, хз, Х4, $ь соответственно входные переменные (доступная пропускная способность, задержка передачи пакета, загруженность пакетных буферов, качество связи, количество промежуточных узлов), А\,... ,А*1 -соответствующие им нечеткие множества, k — 1,..., N - правила нечеткого вывода, N - количество правил нечеткого вывода (N — 55 = 3125, поскольку каждая из пяти лингвистических переменных может принимать пять

различных значений), у - выходная переменная (рейтинг маршрута), В -соответствующее ей нечеткое множество.

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

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

• Параметры функций принадлежности 6 лингвистических переменных (5 входных и 1 выходная переменная).

• Значения выходной переменной для всех 3125 правил нечеткого вывода.

• Значения таймаутов поиска маршрута и кэширования маршрута.

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

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

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

Минимизировать: у = /(ж) — (/'(х), }"{х)), При ограничениях: хр < х < хд,

Ут<У< Уз- (9)

где х = (xj, Х2, ■ ■ ■, хп) € X является вектором решений (настраиваемые параметры метода маршрутизации, п = 3189); у 6 У является векторным критерием, в котором /' - доля потерянных пакетов, /" - средняя задержка передачи пакета; X обозначает множество (альтернативных) решений; Y - множество векторных оценок. Заданные ограничения хр < х < хд определяют множество допустимых решений и устанавливаются для каждого сценария функционирования сети. Ограничения уг < у < ys определяют множество допустимых векторных оценок и задаются для каждого сценарии функционирования сети в отдельности (например, доля потерянных пакетов от 0 до 10% и задержка передачи от 100 до 200 мс).

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

• Для отбора решений (хромосом) должен использоваться принцип оптимальности по Парето.

• Генетический алгоритм должен направлять популяцию решений в сторону фронта Парето-оптимальных решений.

• Генетический алгоритм должен поддерживать разнообразие решений для предотвращения преждевременной сходимости.

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

• Селекция хромосом в родительский пул производится на основании принципа доминирования по Парето, а не по значениям функции приспособленности (например, на рисунке lb решение А доминирует решения С и В). Кроме того, для направления генетического алгоритма

в сторону фронта Парето поддерживается внешняя популяции недоминируемых решений, заполняемая хромосомами текущего недоминируемого фронта (например, на рисунке 1Ъ решения Е, Г, в, Н, К составляют фронт недоминируемых решений). При выполнении селекции эти хромосомы смешиваются с хромосомами популяции на следующем шаге и наравне с ними участвуют в процедуре отбора.

• Оператор скрещивания выбирает хромосомы в зависимости от расстояния между ними в пространстве значений целевых функций и от отношения между ними в смысле Парето. Расстояние между двумя решениями в пространстве значений целевых функций (критериев) вычисляется как:

гц = х/(л-/;)2+(Л'-/,т, (ю)

где г^ - решения, /',/" - критерии „доля потерянных пакетов" и „средняя задержка передачи пакета" соответственно (к примеру, на рисунке 1Ь длина проведенных отрезков между решениями и является расстоянием между решениями).

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

00

(Ь)

Рис. 1: Иллюстрация предположения о скрещивании хромосом

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

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

Итогом исследований, проведенных в данной главе, является метод оптимизации параметров метода маршрутизации, основанный на генетическом алгоритме. Он состоит из следующих шагов:

1. Инициализация алгоритма заключается в генерации популяции случайных решений в заданном количестве. Для кодирования параметров задачи в хромосому используется двоичное кодирование. Получаемая хромосома показана на рисунке 2.

2. Затем происходит оценка приспособленности хромосом. В диссертационной работе целью оптимизации контроллера маршрутизации на

параметры 6-ти функций принадлежности

значения таймаутов протокола и

интервалов сбора значения выходной переменной

данных

для 3125 правил

|0...1|0...1| 0...1|0..,1 |0...1|0...1 | О..Л)0...1|О..Л10...1|001| ... | ... | ... | ... |001|

Рис. 2: Кодирование параметров задачи в хромосоме

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

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

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

3. Далее проверяется условие остановки алгоритма: сходимость популяции решений либо достижение заданного числа итераций.

4. После этого, если прошло некоторое число итераций, проводится процедура „разреживания" популяции решений и ввода „хромосом-иммигрантов".

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

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

ГПг бит

т^ т^га^т^ з бита

бит бит бит бит

Таким образом, в данной главе были решены следующие поставленные в диссертационной работы задачи: (1) разработка метода оптимизации параметров работы метода маршрутизации (2) с целью улучшения двух показателей качества обслуживания - доли потерянных пакетов и средней задержки передачи пакета для всей сети в целом.

В четвертой главе описана постановка и проведение серии модельных экспериментов, целями которых были:

• Подтверждение эффективности разработанного метода маршрутизации для беспроводной ячеистой сети с точки зрения качества обслуживания. Для этого было проведено сравнение его работы с другими широко используемыми методами маршрутизации (OLSR, QOLSR, AODV, ACOR) по указанным в задачах диссертационной работы показателям качества обслуживания - доли потерянных пакетов и средней задержки передачи пакета для всей сети в целом;

• Исследование влияния предложенного метода оптимизации на основе генетического алгоритма на работу метода маршрутизации. Для этого была проведена серия экспериментов с варьированием данных, используемых для процедуры оптимизации и для оценки работы метода маршрутизгщии;

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

Для проведения модельных экспериментов была выбрана среда моделирования OMNeT-f+, поскольку исследования показывают, что она с высокой точностью позволяет проводить моделирование работы беспроводных сетей. Для нее была разработана модель предложенного метода маршрутизации. Была выбрана и реализована модель распространения сигнала согласно рекомендациям ITU-T, и был реализован генератор трафика, отражающий поведение реальных пользователей в реальной телекоммуникационной сети с целью получения достоверных результатов (Muscariello L. Markov models of internet traffic and a new hierarchical MMPP model / L. Muscariello. // Computer Communications. - 2005. - I. 28.- P. 1835-1851.).

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

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

Далее для каждого из 10 сгенерированных сценариев была проведена процедура оптимизации параметров метода маршрутизации с использованием разработанного генетического алгоритма. Затем для сравниваемых методов был проведен анализ следующих показателей: средняя задержка передачи пакета, доля потерянных пакетов, время ожидания установления сессии, время восстановления сессии после сбоя. Результаты анализа показали, что разработанный метод маршрутизации на основе нечеткой логики лучше справляется с распределением трафика в сети и превосходит по выбранным показателям качества обслуживания широко используемые методы маршрутизации для беспроводных ячеистых сетей. К примеру, на рисунке За показаны полученные значения задержки передачи пакета, а на рисунке ЗЬ - значения доли потерянных пакетов (для шаблона „опорная сеть"; разработанный метод маршрутизации отмечен как ОББИ,).

Номер сцеилриа

(а) (Ъ)

Рис. 3: Результаты моделирования для шаблона „опорная сеть" Кроме того, была проведена оценка эффективности предложенных модификаций генетического алгоритма по сравнению с классическим генетическим алгоритмом. Для этого для каждого из 10 сценариев была проведена еще одна процедура оптимизации (через классический генетический алгоритм), но оба критерия (показателя) качества, обслуживания были приведены к единому при помощи метода свертки. Результаты проведения процедур оптимизации по разным методам пок£1зали, что в целом оба генетических алгоритма находят практически одинаковые решения (расхождение результатов менее 5%), но значительным преимуществом предложенного алгоритма является его более быстрая сходимость при сохра-

нении качества получаемых решений, что экономит время при проведении процедуры оптимизации.

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

Рис. 4: Результаты моделирования при оптимизации на 1 и на 10 сценариях

Первый эксперимент показал, что метод маршрутизации с параметрами, оптимизированными для одного шаблона работы („мобильная сеть"), демонстрирует низкие; показатели качества обслуживания при работе на совершенно ином, сильно отличающемся шаблоне („стационарная сеть"). Для оценки влияния оптимизации на возможности метода работать в похожих, относительно слабо отличающихся сценариях, была проведена еще одна серия модельных экспериментов, для чего было сгенерировано 50 сценариев работы, которые отличались лишь количеством узлов - от 400 до 500 и топологией их размещения (генерируется случайным образом). Один из 50 сгенерированных сценариев с наименьшим количеством узлов (400) использовал ся для оптимизации параметров метода маршрутизации, а остальные 49 использовались для проверки эффективности работы метода маршрутизации с данными оптимизированными параметрами. Результаты эксперимента показали, что при оптимизации параметров для заданного сценария возникает эффект чрезмерной оптимизации: эффективность работы метода снижается при работе на сходных (относительно слабо отличающихся) сценариях работы (на рисунке 4 график отмечен как "ОББИ"). Было выдвинуто предположение, что для устранения эффекта чрезмерной оптимизации следует использовать большее количество сценариев работы сети. Для проверки данного предположения был поставлен модельный эксперимент, в котором для проведения процедуры оптимизации было выбрано случайным образом 10 сценариев из ранее сгенерирован-

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

Результаты эксперимента подтвердили, что большее разнообразие данных при оптимизации метода маршрутизации позволяет устранить упомянутый выше эффект чрезмерной оптимизации, но лишь за счет снижения "приспособленности" к отдельно выбранным сценариям (на рисунке 4 график отмечен как "ODSR opt"). Иными словами, метод маршрутизации может не демонстрировать оптимальные показатели качества обслуживания на отдельных сценариях данного диапазона, но зато при изменении условий функционирования эффективность его работы не будет значительно снижаться.

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

• Разработанный метод маршрутизации превосходит по выбранным показателям качества обслуживания широко используемые методы маршрутизации для беспроводных ячеистых сетей.

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

Пример практической реализации

Методы и алгоритмы, разработанные в диссертационной работе, были применены в ОАО „Российская телекоммуникационная сеть" в проекте по созданию тестовой беспроводной ячеистой сети для апробирования программно-аппаратного обеспечения с целью последующего введения в эксплуатацию на территории г. Москвы. Практическая реализация предложенных методов и алгоритмов позволила добиться более высоких показателей качества обслуживания по сравнению с протоколом маршрутизации, заложенным в протестированное программно-аппаратное обеспечение.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В процессе исследований, выполненных в диссертационной работе, получены следующие результаты:

1. Разработан метод маршрутизации для беспроводной ячеистой сети с учетом качества обслуживания на основе ашшрата нечеткой логики, который:

• учитывает больший набор (по сравнению с существующими протоколами маршрутизации) параметров состояния узлов и кана-

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

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

2. Разработан метод оптимизации на основе генетического алгоритма для предложенного метода маршрутизации.

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

4. Для всех учитываемых параметров состояния узлов и каналов связи были предложены оценочные функции, которые позволяют на основании значений параметров для отдельных узлов вычислить значение параметра для всего маршрута в целом. Разработан метод оценки доступной пропускной способности на основе механизма RTS-CTS.

5. Разработана программная модель предложенного метода маршрутизации для выбранной среды моделирования.

6. Разработан генератор трафика, имитирующий работу пользователей с ресурсами в многопользовательской сети.

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

Основные результаты диссертации опубликованы в работах:

В изданиях из перечня ВАК:

1. Иванов Д.В. Метод оптимизации протокола маршрутизации для беспроводной сети / Д.В. Иванов // Наукоемкие технологии. - М.: Радиотехника, 2009. - №3. - с. 26-32. - ISSN 1999-8465.

/

2. Иванов Д.В. Применение аппарата нечеткой логики для маршрутизации в беспроводных ячеистых сетях / Д.В. Иванов // Телекоммуникации. - М.: Наука и технологии, 2009. - №5. - с. 13-18.

В других изданиях:

3. Иванов Д.В. Маршрутизация на основе нечеткой логики в беспроводных ячеистых сетях / Д.В. Иванов // Труды V Международной научно-практической конференции "Trans-Mech-Art-Chem". - М.: МИ-ИТ, 2008. - с. 85-86. - ISSN 978-5-7876-0129-9.

4. Ivanov D.V. Fuzzy Computing in Stationary Wireless Railway Control Network / D.V. Ivanov // Proceedings of the 6th International Students' Scientific Conference "Trans-Mech-Art-Chem". - Poland, Radom: Politechnika Radomska, 2009. - pp. 30-33.

5. Иванов Д.В. Применение нечетких вычислений для оптимизации процесса маршрутизации в беспроводных ячеистых сетях / Д.В. Иванов // Тезисы докладов 16-ой межвузовской научно-технической конференции студентов и аспирантов "Микроэлектроника и информатика". - Зеленоград.: МИЭТ, 2009. - с. 246. - ISBN 978-5-7256-0535-8.

Иванов Дмитрий Викторович

РАЗРАБОТКА МЕТОДА МАРШРУТИЗАЦИИ ДЛЯ БЕСПРОВОДНОЙ ЯЧЕИСТОЙ СЕТИ С УЧЕТОМ КАЧЕСТВА ОБСЛУЖИВАНИЯ

Специальность - 05.13.13 Телекоммуникационные системы и компьютерные сети

Подписано к печати 26.10.2009 Формат бумаги 60 х 84 1/16 Заказ № 654.

Объем печ. л. 1.5

Тираж 80

Типография МИИТ, 127994 ГСП-4, г. Москва, ул. Образцова 15

Введение

1 Анализ предметной области и определение целей исследования

1.1 Особенности работы беспроводных ячеистых сетей

1.2 Анализ среды функционирования беспроводных ячеистых сетей с учетом качества обслуживания

1.2.1 Факторы, влияющие на обеспечение качества обслуживания в беспроводных ячеистых сетях.

1.2.2 Параметры состояния узлов и каналов связи с точки зрения качества обслуживания.

1.2.3 Показатели качества обслуживания.

1.2.4 Факторы, влияющие на эффективность метода маршрутизации с учетом качества обслуживания.

1.2.5 Ресурсы сети, необходимые для обеспечения качества обслуживания

1.2.6 Компромиссы построения методов маршрутизации

1.3 Анализ существующих методов маршрутизации в беспроводных ячеистых сетях с учетом качества обслуживания.

1.3.1 Протокол OLSR.

1.3.2 Протокол AODV.

1.3.3 Протокол QOLSR.

1.3.4 Протокол ODCR

1.3.5 Протокол Application Aware QoS Routing.

1.3.6 Протокол Cross Layer ACOR.

1.3.7 Протокол AQOR.

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

1.4 Выводы.

2 Разработка метода маршрутизации на основе аппарата нечеткой логики

2.1 Разработка протокола маршрутизации для беспроводной ячеистой сети.

2.2 Аппарат нечеткой логики.

2.3 Разработка блока принятия решения для метода маршрутизации на основе контроллера нечеткой логики.

2.3.1 Входные параметры контроллера и блок фаззификации

2.3.2 Блок нечеткого вывода и блок дефаззификации.

2.4 Выводы.

3 Разработка метода оптимизации параметров метода маршрутизации на основе генетического алгоритма

3.1 Постановка задачи оптимизации.,

3.2 Классический генетический алгоритм как метод оптимизации

3.3 Анализ задачи многокритериальной оптимизации.

3.3.1 Традиционные подходы к нахождению Парето-оптимальных решений.

3.4 Разработка генетического алгоритма для оптимизации контроллера маршрутизации па основе нечеткой логики.

3.4.1 Кодирование параметров задачи.

3.4.2 Селекция.'.

3.4.3 Оператор скрещивания.

3.4.4 Противодействие преждевременной сходимости алгоритма

3.5 Выводы.

4 Постановка и проведение модельного эксперимента

4.1 Разработка модели предложенного метода маршрутизации для беспроводной ячеистой сети.

4.1.1 Выбор среды моделирования.

4.1.2 Разработка модели предложенного метода маршрутизации для среды моделирования OMNeT-f-f-.

4.1.3 Выбор и реализация модели распространения сигнала

4.1.4 Выбор и реализация модели генератора трафика

4.2 Проведение модельного эксперимента.

4.2.1 Сравнение эффективности разработанного метода с протоколами

OLSR, QOLSR, AODV, ACOR с точки зрения качества обслуживания

Шаблон „опорная сеть".

Шаблон „мобильная сеть".

4.2.2 Оценка влияния оптимизации на эффективность работы метода маршрутизации.

4.3 Пример практической реализации.

4.4 Выводы.

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

Однако существующие протоколы маршрутизации, в том числе стандарта IEEE 802.11, не были спроектированы с учетом ячеистой топологии и не учитывают возможность многомаршрутной передачи данных. Кроме того, мультимедийные приложения занимают все большую долю среди пользовательских приложений. Как следствие, происходит смещение фокуса от сервисов доставки данных без гарантий к сервисам, обеспечивающим качество обслуживания (Quality of Service, QoS) в беспроводных сетях.

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

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

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

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

3.5 Выводы

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

• Генетический алгоритм должен направлять популяцию решений в сторону фронта Парето-оптимальных решений.

• Генетический алгоритм должен поддерживать разнообразие решений ' для предотвращения преждевременной сходимости.

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

• Оператор скрещивания выбирает хромосомы в зависимости от расстояния между ними в пространстве значений целевых функций и от отношения между ними в смысле Парето.

• Для поддержания разнообразия популяции решений с целью защиты от преждевременной сходимости и попадания в локальные оптимумы был предложен метод понижения плотности решений и введения „хромосом-иммигрантов".

Предложенные модификации предоставляют возможность производить оптимизацию по нескольким критериям и управлять сходимостью генетического алгоритма. Таким образом, были решены следующие поставленные в диссертационной работы задачи: (1) разработка метода оптимизации работы метода маршрутизации (2) с целью улучшения двух показателей качества обслуживания - доли потерянных пакетов и средней задержки передачи пакета для всей сети в целом.

Глава 4. ПОСТАНОВКА И ПРОВЕДЕНИЕ МОДЕЛЬНОГО ЭКСПЕРИМЕНТА

В этой главе будет рассмотрен процесс разработки модели и проведения модельного эксперимента. Цель проведения модельных экспериментов состоит в следующем:

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

• Необходимо исследовать влияние предложенного метода оптимизации на основе генетического алгоритма на работу метода маршрутизации.

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

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

Для постановки и проведения модельного эксперимента требуется решить следующие задачи:

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

• Разработать модель предложенного метода маршрутизации.

• Провести модельный эксперимент и проанализировать полученные результаты.

4.1 Разработка модели предложенного метода маршрутизации для беспроводной ячеистой сети

4.1.1 Выбор среды моделирования

В задачу диссертационной работы входит разработка метода маршрутизации с учетом качества обслуживания для беспроводной ячеистой сети. К сожалению, постановка эксперимента на реальном оборудовании в реальных условиях работы невозможна из-за того, что потребуется большое количество беспроводных устройств (от нескольких десятков до нескольких сотен) и большая площадь, на которой эти устройства можно было бы разместить. Поэтому для апробирования разработанных в диссертационной работе методов и подтверждения сделанных во второй и третьей главе выводов был поставлен модельный эксперимент, для чего требовалось или разработать собственную, или выбрать существующую среду моделирования работы телекоммуникационных сетей. К счастью, существует множество подходящих для дайной задачи систем моделирования, как с открытым исходным кодом, например, ns-2 [40], OMNeT++ [41], J-Sim [42], так и коммерческие решения, например, QualNet [43], OPNET [44]. Выбор среды моделирования диктовался следующими требованиями:

• Среда должна позволять моделировать работу беспроводных сетей стандарта IEEE 802.11.

• Моделирование беспроводной среды передачи с высокой точностью.

• Модель стека сетевых протоколов TCP/IP должна быть полностью реализована.

• Легкость добавления новых модулей в стек сетевых протоколов.

• Наличие средств отладки.

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

В результате, после рассмотрения и апробирования нескольких систем моделирования телекоммуникационных систем предпочтение было отдано программной среде OMNeT++. OMNeT++ является модульной объектно-ориентированной дискретно-событийной средой моделирования и позволяет моделировать передачу и обработку трафика в телекоммуникационных сетях, работу протоколов сетевого стека, систем массового обслуживания, работу многопроцессорных и распределенных систем, проводить оценку других систем, где возможен дискретно-событийный подход к моделированию. Основными достоинствами OMNeT++ являются наличие открытого исходного кода, всеобъемлющая документация на ядро моделирования и всех поставляемых моделей, возможность параллельной обработки модели в распределенной системе. Исследование [45] показывает, что данная среда моделирования позволяет моделировать работу беспроводных сетей с очень высокой точностью. OMNeT-H- предоставляет графический интерфейс для отладки модели и интерфейс командной строки для высокопроизводительного моделирования. Кроме того, сценарии моделирования описываются в отдельных модулях на специальном языке, поэтому очень легко связывать OMNeT+-f-с другими процессами (что и потребуется нам для оптимизации метода с использованием генетического алгоритма).

• ' OMNeT+-f предоставляет базовое ядро и инструменты для создания моделей и проведения дискретно-событийного моделирования. Сам по себе программный пакет не предоставляет средств моделирования телекоммуникационных сетей, систем массового обслуживания, распределенных систем. Эти средства доступны в виде готовых моделей и дополнений, например-, INET framework [46] реализует инструменты моделирования телекоммуникационных сетей и модели большинства протоколов сетевого стека, включая протоколы доступа для беспроводных сетей стандарта IEEE 802.11. Это дополнение и будет использовано для создания модели беспроводной ячеистой сети и предложенного метода маршрутизации.

4.1.2 Разработка модели предложенного метода маршрутизации для среды моделирования OMNeT++

Любая модель в OMNeT++ состоит из иерархически вложенных модулей, которые общаются между собой путем передачи сообщений. Самым верхним модулем (корнем) в этой иерархии является системный модуль. Глубина вложения модулей не ограничена. Для описания структуры модели используется специальный язык NED [47]. Модули, которые содержат в своем составе другие модули, называются составными (compound). Иначе модули называются простыми (simple).

Как было отмечено выше, модули обмениваются сообщениями. При проведении моделирования сообщения могут служить в качестве кадров или пакетов в телекоммуникационной сети. Простые модули могут посылать сообщения либо напрямую другим модулям (в редких случаях), либо через шлюзы (gates) и соединения (connections). Шлюзы являются входными и выходными интерфейсами модулей, сообщения приходят в модуль через входные шлюзы, и уходят через выходные шлюзы. Соединения можно устанавливать между шлюзами различных модулей, например, можно соединить входной шлюз модуля протокола TCP с выходным шлюзом приложения пользователя (генератора трафика), или соединить шлюзы внутри составного модуля.

Для описания соединений используется три параметра, которые упрощают моделирование телекоммуникационных сетей:

• Задержка передачи (в миллисекундах): время, на которое пакет будет задержан при передаче через соединение (эмулируется задержка передачи по телекоммуникационным каналам связи).

• Доля битовых ошибок: отражает вероятность, с которой бит данных будет передан некорректно (эмулируется зашумленность канала связи).

• Пропускная способность (в бит/с): показывает, какой объем данных может передать соединение за единицу времени.

Тип, структура и параметры модулей, составляющих модель описываются на языке NED в специальном файле omnetpp.ini. Все соединения между модулями также описываются в этом файле.

Таким образом, модель в OMNeT++ состоит из следующих компонент:

• Исходный текст простых модулей, реализующих алгоритм работы протокола или иного компонента (на языке программирования С++).

• Файлы описания сообщений (файлы .msg). Можно определить различные типы сообщений и их структуру, например, формат пакета маршрутизации. В состав OMNeT++ входит транслятор файлов .msg в исходный код С++.

• Файлы описания структуры и параметров модели на языке NED (файлы .ned). Используются ядром моделирования во время исполнения.

• Конфигурационный файл omnetpp.ini, который описывает: как будет исполняться моделирование, время выполнения моделирования, количество проходов, какие статистические параметры о работе модели будут собираться, будет ли включен графический интерфейс пользователя и т.д.

Система сборки и запуска моделирования среды OMNeT++ на основе этих компонент и ядра системы моделирования собирает и запускает модель на исполнение.

Алгоритм работы предложенного протокола маршрутизации, показанный на рисунке 2.1, для беспроводной ячеистой сети был реализован в виде простого модуля OMNeT++. Модуль протокола маршрутизации (с названием ODSR), предназначен для работы на сетевом уровне, поэтому был подключен в стек сетевых протоколов мобильного узла, как показано на рисунке 4.1. Входной шлюз модуля подключен к гёнератору трафика, который используется для моделирования работы пользовательских приложений. Выходной шлюз подключен к модулю протокола IP, который отвечает за дальнейшую пересылку сообщения (сетевого пакета). Модуль RoutingTable содержит таблицу маршрутизации узла. х * (Host) scenariDl.host[4]= v * X jii^mai^^siMMf ^^ (Host) scenario!.hostJ4j (id-7) (ptr(Mcd34c8)

Рис. 4.1. Подключение протокола маршрутизации в стек протоколов узла

Модуль протокола маршрутизации ОРЭК реализовывает интерфейс простого модуля 81тр1еМос1и1е, поэтому обработка всех входящих сообщений происходит в функции handleMessage(). Таймауты ожидания ответа маршрутизации и кэширования реализуются в виде сообщений модуля самому себе. Функция harldleMessage() в зависимости от типа сообщения в соответствии с алгоритмом, изображенным на рисунке 2.1, передает это сообщение дальше на обработку в следующие функции (исходный текст модели протокола ОИвВ. приведен в приложении):

• handleOutgoingDataMessage() для обработки исходящего пакета данных (от генератора).

• Ьа1^1е1псопш^СМ5гМе88а§е() для обработки входящего управляющего сообщения протокола маршрутизации.

• handleOdsrPacketForMe() для обработки входящего сообщения протокола маршрутизации, предназначенного для данного узла.

• handleOdsrPacketForRelay() для обработки проходящего через узел управ ляющего сообщения протокола маршрутизации.

• handleDiscoveredRouteQ для обработки найденного протоколом маршрутизации маршрута (пакет Route Reply).

• handlelncomingDataPacketQ для обработки пакета данных от другого узла.

• processQueueTimeout() для обработки таймера ожидания пакетов Route Reply.

• processRouteTimeout() для обработки таймера сброса кэша маршрутов.

Модуль ODSR также подключен к модулям FuzzyRoutingController и RuleBasis (не показаны на рисунке), которые отвечают за функционирование контроллера нечеткой логики.

Формат пакета разработанного протокола маршрутизации в виде файла .msg показан ниже: class noncobject IPAddress; class noncobject RoutingVector; class noncobject LinkData; message ODSRPacket

-C fields: unsigned int odsrType; IPAddress source; IPAddress destination; unsigned int pointer; RoutingVector vector; LinkData linkData; unsigned int bandwidth; unsigned int delay; unsigned int linkQuality; unsigned int bufferFullness;

Поле odsrType определяет тип пакета маршрутизации: RouteRequest - запрос на поиск маршрута, RouteReply - ответ с найденным маршрутом до узла назначения. Поля Source и Destination содержат IP-адреса источника и узла назначения соответственно. Поля pointer и vector вместе определяют цепочку промежуточных узлов, через которые проходит маршрут от источника до узла назначения. Поля linkData, bandwidth, delay, linkQuality и bufferFullness содержат параметры состояния маршрута.

На рисунке 4.2 показан графический интерфейс среды моделирования OMNeT++, который использовался во время отладки разработанной модели. Во время проведения модельных экспериментов графический интерфейс отключался для экономии ресурсов.

4.1.3 Выбор и реализация модели распространения сигнала

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

Рис. 4.2. Модель беспроводной ячеистой сети в OMNeT++ во время отладки протокола она города) практически невозможно. Как результат, существует множество моделей распространения радиосигнала для различных характеристик окружающей обстановки и условий передачи сигнала, например ¡G, 49]:

• Модель ITU-T для открытых пространств

• Модель Янга для города

• Модель Хата для открытых пространств

• Модель ITU-T для неблагоприятных погодных условий (дождя)

Для моделирования распространения радиосигнала была выбрана модель затухания, которая рекомендована ITU-T для расчета затухания сигнала в пространстве смешанного типа (открытое пространство с природными препятствиями, помещения): = 20- logl0(d) + 10 • п • logl0(f) - 147.56, (4.1) где L - затухание сигнала (дБ), d - расстояние между узлами (м), f -частота несущего сигнала (Гц), п - коэффициент затухания, выбирается в

ЗАКЛЮЧЕНИЕ

1. Разработан метод маршрутизации для беспроводной ячеистой сети с учетом качества обслуживания на основе аппарата нечеткой логики, который:

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

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

2. Разработан метод оптимизации на основе генетического алгоритма для предложенного метода маршрутизации.

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

4. Для всех учитываемых параметров состояния узлов и каналов связи были предложены оценочные функции, которые позволяют на основании значений параметров для отдельных узлов вычислить значение параметра для всего маршрута в целом. Разработан метод оценки доступной пропускной способности на основе механизма ИТЗ-СТЗ.

5. Разработана программная модель предложенного метода маршрутизации для выбранной среды моделирования.

6. Разработан генератор трафика, имитирующий работу пользователей с ресурсами в многопользовательской сети.

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

1. Вишневский В.М. Широкополосные беспроводные сети передачи информа-s ции / В.М. Вишневский, А.И. Ляхов, С.Л. Портной, И.В. Шахнович. М.: Техносфера, 2005. - 592с.

2. Борисов, В.В. Нечеткие модели и сети / В.В. Борисов, В.В. Круглов, A.C. Федулов. М.: Горячая линия - Телеком, 2007. - 284 с.

3. Рутковская, Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский; пер. И.Д. Рудинского. М.: Горячая линия - Телеком, 2007. - 452 с.

4. Подиновский В.В. Парето-оптимальные решения многокритериальных задач / В.В. Водиновский, В.Д. Ногин. М.: Наука, 1982. - 255с.

5. Пантелеев A.B. Методы оптимизации в примерах и задачах / A.B. Пантелеев, Т.А. Летова. М.: Высшая школа, 2005. - 544 с.

6. Беделл. Сети. Беспроводные технологии / Беделл. М.: НТ Пресс, 2009. -441с.

7. Шиллер Й. Мобильные коммуникации / Й. Шиллер. М.: Вильяме, 2002. -384 с.

8. Столлингс В. Беспроводные линии связи и сети / В. Столлингс. М.: Вильяме, 2003. -640 с.

9. Олифер В.Г. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд / В.Г. Олифер. Санкт-Петербург: Питер, 2005. - 960 с.

10. Советов Б.Я. Моделирование систем: Учебник для вузов Зе издание, пере-раб. и доп. / Советов Б.Я., Яковлев С.А. - М: Высшая школа, 2001. - 348с.

11. Becker Р. QoS Routing Protocols for Mobile Ad-hoc Networks A Survey / P. Becker // Technical Report 368/08. - University of Kaiserslautern. - Режим доступа: http://kluedo.ub.uni-kl.de/volltexte/2008/2235/pdf/

12. BelAmID2.5.01-QoSRoutingSurvey-TechnicalReport.pdf, свободный.

13. Zhang Y. Broadband Mobile Multimedia: techniques and applications / Y. Zhang, S. Mao, L. Yang, T. Chen. Boca-raton: Auerbach publications. - 2008. - 566p.

14. Stine J. A paradigm for quality of service in wireless ad hoc networks using synchronous signalling and node states / J. Stine, G. de Veciana // IEEE J. Select. Areas Commun. 2004. - V. 22. - P. 1301-1321.

15. Chen T.-W. QoS routing performance in multihop, multimedia,wireless networks / T.-W. Chen, J. T. Tsai, M. Gerta //in Proc. IEEE 6th Int. Conf. Universal Personal Communications. 1997. - V. 2. - P. 557- 561.

16. Clausen T. Optimized Link State Routing Protocol (OLSR) / T. Clausen, P. Jacquet // Request for Comments: 3626. 2003. - Режим доступа: http://www.ietf.org/rfc/rfc3626.txt, свободный.

17. McQuillan J. The New Routing Algorithm for the ARPANet / J. McQuillan, I. Richer, E. Rosen // IEEE Trans, on Comm. 1980. - V. 28(5). - P. 711-719.

18. Perkins C. Ad hoc On-Demand Distance Vector (AODV) Routing / C. Perkins, E. Belding-Royer // Request for Comments: 3561. 2003. - Режим доступа: http://tools.ietf.org/html/rfc3561, свободный.

19. Badis H. QOLSR, QoS routing for ad hoc wireless networks using OLSR / H. Badis, K. A. Agha // Wiley European Trans. Telecommunications. 2005. -V. 15. - N. 4. - R 427-442.

20. Zhang B. QoS routing for wireless ad hoc networks: problems, algorithms and protocols / B. Zhang, H. T. Mouftah // IEEE Commun. Mag. 2005. - V. 43,. -P. 110-117.

21. Wang M. An application-aware QoS routing scheme with improved stability for multimedia applications in mobile ad hoc networks / M. Wang, G.-S. Kuo. //in Proc. IEEE Vehicular Technology Conf. 2005. - P. 1901-1905.

22. Schulzrinne H. RTP: A transport protocol for real-time applications (rfc 3550) / H. Schulzrinne, S. Casner, R. Frederick, V. Jacobson // IETF RFC. 2003.

23. Kettaf N. A Cross layer Admission Control On-demand Routing Protocol for QoS Applications / N. Kettaf, H. Abouaissa, T. Vuduong, P. Lorenz // IJCSNS International Journal of Computer Science and Network Security. 2006. - V. 6.- N. 9B.

24. Xue Q. Ad hoc QoS On-demand Routing in Mobile Ad hoc Networks / Q. Xue, A. Ganz // Journal on Parallel and Distributed Computing. 2003. - V. 63. - I. 2. - P. 154 - 165.

25. A1 Amri H. Scalability of MANET Routing Protocols for Heterogeneous and Homogenous Networks / H. A1 Amri, M. Abolhasan , T. Wysocki. Режим доступа: http://users.rsise.anu.edu.au/famtin/ICSPCS/ICSPCS07/papers/ 204.pdf, доступ свободный.

26. Zadeh L. Fuzzy sets / L. Zadeh // Information and control. 1965. - V. 8. - P. 338 - 353.

27. Lin W. Application of Soft Computing Techniques to Adaptive User Buffer Overflow Control on the Internet / W. Lin, A. Wong, T. Dillon // IEEE Transcations on systems, man, and cybernetics Part C: Apllications and reviews. 2006. - V. 36.- N. 3.

28. Rea S. Multi-metric routing decisions for ad hoc networks using fuzzy logic / S. Rea, D. Pesch // 1st International Symposium on Wireless Communication Systems. 2004. - P. 403- 407.

29. Alandjani G. Fuzzy routing in ad hoc networks / G. Alandjani, E. Johnson // Performance, Computing, and Communications Conference: Conference Proceedings of the 2003 IEEE International. 2003. - P. 525-530.

30. IEEE 802.11 Wireless Local Area Networks. Режим доступа http://www.ieee802.org/ll/, свободный. - Загл. с экрана.

31. Status of Project IEEE 802.11s. Режим доступа http://grouper.ieee.org/ groups/802/ll/Reports/tgsupdate.htm. - Загл. с экрана.

32. Spall, J. Introduction to Stochastic Search and Optimization: Estimation, Simulation and Control / J. Spall. San-Francisco: WileyBlackwell, 2003. - 618 P

33. Holland. Adaptation in Natural and Artificial Systems / Holland // The MIT Press; Reprint edition. 1992.

34. Whitley D. In Foundations of Genetic Algorithms 3, ed. / D. Whitley, M. Vose. // Morgan Kaufmann, San Francisco. 1995.

35. Nortel Networks / Nortel Wins Taipei's Mobile City Project Phase II Contract to Deploy Wireless Mesh Network. Режим доступа: http://www.nortel.com/ corporate/news/newsreleases/2005b/060205qware.html, свободный. -Загл. с экрана.

36. Meraki is bringing free wireless Internet to San Francisco!. Режим доступа http://sf.meraki.com/, свободный. - Загл. с экрана.

37. The Network Simulator ns-2. - Режим доступа: http://www.isi.edu/nsnam/ ns/, свободный. - Загл. с экрана.

38. OMNeT++ Discrete Event Simulation System. Режим доступа: http://www.omnetpp.org/index.php, свободный. - Загл. с экрана.

39. J-Sim Home Page. Режим доступа: http://nsr.bioeng.washington.edu/jsim/, свободный. - Загл. с экрана.

40. Qualnet. Режим доступа: http://www.scalable-networks.com/products/ qualnet/, свободный. - Загл. с экрана.

41. OPNET Modeler: Network simulations. Режим доступа: http://www.opnet.com/solutions/networkrd/modeler.html, свободный. -Загл. с экрана.

42. М. Bredel М. On the accuracy of IEEE 802.llg wireless LAN simulations using OMNeT++ / M. Bredel, M. Bergner. // Proceedings of the 2nd International Conference on Simulation Tools and Techniques. 2009.

43. INET Framework for OMNeT++ 4.0. Режим доступа: http://inet.omnetpp.org/, свободный. - Загл. с экрана.

44. OMNeT++ User manual. Режим доступа: http://www.omnetpp.org/doc/ omnetpp40/manual/usman.html, свободный. Загл. с экрана.

45. Akyildiz I. A survey on wireless mesh networks / I. Akyildiz, X. Wang. // IEEE Radio Communications. 2005. - V. 43.- N. 9. - P. S25-S30. - Режим доступа: http://www.ece.gatech.edu/wxudong/XudongWangcommesh.pdf, свободный.

46. Mishra A. Security and Quality of Service in Ad hoc wireless networks: / A. Mishra. Cambridge: Cambridge University Press, 2008. - 180 p.

47. D-Link: Серия высокоскоростных беспроводных устройств 2.4ГГц (802.lib/ llg) до 108 Мбит/с. Режим доступа: http://dlink.ru/ru/ products/2/, свободный. - Загл. с экрана.

48. Eramilli A. An application of deterministic chaotic maps to model packet traffic / A. Eramilli, R.P. Singh / Queueing Systems. V. 20. - 1995. - p. 171-206.

49. Reyes Lecuona A. A Page-oriented WWW Traffic Model for Wireless System Simulations / A. Reyes Lecuona, E. Gonzalez Parada, E. Casilari, J.C. Casasola, A. Diaz Estrella // International Teletraffic Conference ITC16, Edinburgh, UK. 1999.

50. Miiscariello L. Markov models of internet traffic and a new hierarchical MMPP model / L. Muscariello. // Computer Communications. 2005. - I. 28.- P. 18351851.

51. Adewuya, A. New Methods in Genetic Search with Real-Valued Chromosomes / A. Adewuya. Massachusetts Institute of Technology. - Режим доступа: http://dspace.mit.edu/handle/1721.1/10930, свободный.