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

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

Алгоритмы маршрутизации в беспроводных сетях делятся на несколько основных классов. Это активные (pro-active, table-driven), реактивные (reactive, on-demand) алгоритмы и гибридные (hybrid) алгоритмы.

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

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

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

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

Рассмотрим алгоритмы маршрутизации AntHocNet и AODV.

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

AODV (Ad-hoc On-demand Distance Vector) - это реактивный алгоритм, основанный на построении таблиц маршрутизации на каждом узле сети для минимизации времени передачи информации между узлами. Первым шагом этого алгоритма является построение таблиц маршрутизации на каждом узле. В таблице содержится длина кратчайшего пути к каждому узлу в сети через каждый соседний узел. На первом шаге в таблице содержится информация только о доступе к соседним узлам в сети. На каждом следующем шаге каждый узел обменивается с соседними узлами информацией о каждом известном ему кратчайшем пути к каждому узлу сети. После некоторого количества шагов, зависящего от количества узлов в сети, таблицы маршрутизации на узлах перестают изменяться, после чего начинается передача данных по кратчайшему найденному пути. При сбое узла сети из таблицы берется следующий наиболее предпочтительный кратчайший маршрут. [2]

Для определения эффективности использования каждого из этих двух алгоритмов можно использовать систему моделирования компьютерных сетей NS2 и подключаемый модуль PDNS.

NS2 (Network Simulator 2) - это система моделирования компьютерных сетей, позволяющая моделировать различные виды компьютерных сетей и собирать всю необходимую информацию об их функционировании. Для распределенного использования этой системы моделирования используется PDNS (Parallel Distributed Network Simulator) - система, позволяющая распределенно моделировать компьютерные сети, запуская экземпляр NS2 на каждом узле вычислительной компьютерной сети и синхронизировать работу между ними.

Запуск данной системы моделирования осуществляется на кластерной сети под управлением Microsoft Windows Compute Cluster 2003 с использованием эмулятора Cygwin, который эмулирует среду UNIX, а также позволяющего компилировать и запускать программы, написанные для этой среды.

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

Литература

1. Gianni Di Caro, Frederick Ducatelle, Luca Maria Gambardella. AntHocNet: an Ant-Based Hybrid Routing Algorithm for Mobile Ad Hoc Networks. http://www.idsia.ch/~luca/anthocnetppsn.pdf

2. Ian D. Chakeres, Elizabeth M. Belding-Royer. AODV Routing Protocol Implementation Design. http://moment.cs.ucsb.edu/pub/wwan_chakeres_i.pdf