Главная
страница 1
Исследование алгоритмов маршрутизации в беспроводных сетях

Ст.гр. СП09м Кондратюк Д.С.

Зачем это все?

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



И что тут нового?

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


Какие алгоритмы маршрутизации будут исследованы?

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

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

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

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

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

В протоколе использованы следующие методы борьбы с паразитным трафиком:


  • Ограничение времени жизни пакета(TTL) до значения предполагаемого числа промежуточных узлов в сети.

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

Протокол обладает следующими преимуществами:

  • Простота реализации

  • Отсутствие дополнительного трафика при пересылке данных

  • Низкие требования к ресурсам.

Недостатком протокола является большое время установки маршрута.

Рисунок 1. Пример работы алгоритма AODV.

Протокол DSR (Dynamic Source Routing), применяющийся в ячеистых(mesh) сетях, схож с AODV в том, что также формирует маршрут по требованию, посредством передачи запроса (реактивный протокол маршрутизации) .

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



Что моделируется(анализируется)?

В магистерской работе планируется промоделировать беспроводную сеть (Wi-Fi) маршрутизируемую по модифицированному протоколу AODV и, возможно, mesh-сети с DSR.

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

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

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


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

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

  • канал общего типа – может быть использован и как выделенный, и как разделяемый канал.

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

где Ti – множество логических каналов, доступных узлу i для передачи данных,



Rj – множество логических каналов, доступных узлу j для приема данных.

То есть, подмножество k – это множество каналов связывающих эти два узла. Физически это подмножество может представлять собой набор незанятых другими узлами радиочастот(или полос радиочастот), на которых возможна связь между i и j. После освобождения одного из каналов этого подмножества (из вышеуказанной классификации следует, что канал может быть занят и другими узлами), узел переводит его в состояние «занят» (к примеру, начиная посылку преамбулы и фрейма). При этом данный канал не может быть использован ни одним из узлов кластера, в которые входят i и j (поскольку физически они разделяют один и тот же радиоэфир). Точнее, в кластере i (эфир в который этот узел может вещать по данному каналу) не может быть осуществлена передача, а в кластере j (эфир в котором этот узел может прослушивать данный канал) - прием.

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

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

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

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

ti – время нахождения пакета в очереди на передачу на i-ом узле маршрута,

Route – множество узлов, входящих в маршрут, кроме узла получателя.

Для сети, состоящей из одинаковых устройств, параметр T является постоянным для всех узлов и зависит, в основном, от длины пакета и пропускной способности канала связи.

Параметр ti зависит от интенсивности обслуженного каждого i-го трафика, поэтому для каждого узла имеет смысл вести еще один дополнительный параметр – интенсивность обслуженного трафика для кластера данного узла, или коэффициент использования разделяемого ресурса (ресурсов, в случае, если их несколько).»[2]


Как моделируем?

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

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

В GUI запланирована реализация следующей функциональности:



  • Редактор графа (возможно, с возможностью импорта данных из XML-файла).

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

  • Возможность управления процессом моделирования(Пауза/Продолжить).

  • Возможность изменения параметров и структуры графа во время моделирования (в режиме паузы).

  • Возможность конфигурирования устройств (MAС-адрес, IP, и т.д.).

  • Возможность выбора протокола маршрутизации.

- Форма, с кратким описанием ТЗ.
Язык и среда разработки моделирующего ПО?

Выбрана Java(Eclipse) :

- независима от платформы

- поддерживает ООП

- программа может быть реализована в виде апплета к браузеру

- имеются внешние средства для реализации графов(к примеру - JGraph).

- имеется опыт разработки приложений в Java.
Какова планируемая структура ядра разрабатываемого ПО?

В моделирующем ПО планируется реализовать следующие классы:



  • Node – описывает узел(связанное устройство)

  • Device – описывает устройство коммутации(параметры устройства, таблица связей, таблица маршрутизации)

    • WirelessDevice – устройство связи.

    • AP – точка доступа к Интернету.

    • WirelessRouter – маршрутизатор.

  • Packet – описывает пакет, передаваемый по сети (в частности, его статистические характеристики - количество пройденных хопов, время доставки, размер)

    • RoutingPacket – служебный пакет, предназначенный для установления маршрута.

  • Hello – пакет приветствия (отсылается при активации узла, т.е. при добавлении его в сеть).

  • Link – описывает связь (ребро) между узлами. Метод getLinkQuality() моделирует случайные изменения в пропускной способности канала.

  • Net – содержит список узлов сети и некоторые ее характеристики.

  • Packets – содержит список отслеживаемых пакетов и их общие характеристики.


Как при помощи ПО оценить результат?

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



  • Нагрузка на узлы

  • Нагрузка на каналы

  • Задержка при передаче пакетов


Смотрите также:
Исследование алгоритмов маршрутизации в беспроводных сетях
74.2kb.
1 стр.
Исследование и разработка некоторых графических алгоритмов
602.24kb.
6 стр.
Решение задачи многокритериальной маршрутизации в телекоммуникационных сетях Магистерская диссертация
469.87kb.
4 стр.
Вопросы по курсу окс для групп ск-51-53
24.81kb.
1 стр.
X городская научно-практическая техническая конференция школьников «Исследуем и проектируем»
223.36kb.
1 стр.
Маршрутизация
45.08kb.
1 стр.
Занятие по теме: «Продвижение информации о политических партиях и депутатах в социальных сетях: задачи, сроки, показатели эффективности. Воздействие политической рекламы на молодежь в социальных сетях»
42.14kb.
1 стр.
Методы расчета потерь электроэнергии в электрических сетях 0,38 кВ
109.36kb.
1 стр.
Рассказать о современных технологиях беспроводных сетей; изложить историю развития беспроводных сетей и их преимущества
412.63kb.
3 стр.
Программа «Автоматизированные системы обработки информации и управления»
79.58kb.
1 стр.
Разработка алгоритмов управления и исследование применения электрического торможения для повышения динамической устойчивости развивающейся энергодефицитной энергосистемы
207.24kb.
1 стр.
Справочник Томас Ниман Thomas Niemann
467.34kb.
8 стр.