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

• Автор: Голубев, Андрей Сергеевич
• Шифр специальности: 05.12.13
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Владимир
• Количество страниц: 141 с. : ил.

Оглавление
Оглавление
Введение

Глава I. Сети MANET

1.1. Тенденции развития программно-аппаратных средств мобильных сетей

1.2. Сети MANET: проблемы и возможности

1.3. Классификация алгоритмов маршрутизации

1.4. Обзор маршрутизирующих протоколов MANET

1.4.1. Destination-Sequenced Distance-Vector Routing (DSDV)

1.4.2. Optimized Link State Routing Protocol (OLSR)

1.4.3. Topology broadcast based on reverse-path forwarding (TBRPF)

1.4.4. Ad hoc On-Demand Distance Vector (AODV)
1.4.5. Dynamic Source Routing (DSR)
1.4.6. Temporally-Ordered Routing Algorithm (TORA)
1.4.7. Zone Routing Protocol (ZRP)
1.4.8. Hazy-Sighted Link State Routing Protocol (HSLS)
1.5. Сравнительная характеристика
1.6. Маршрутизация в самоорганизующихся МО-сетях
1.7. Выводы по главе
Глава II. Разработка метода маршрутизации на основе структурной особенности сети
2.1.1. Область применения
2.2. Математическая модель
2.2.1. Общие положения
2.2.2. п-окрестность
2.2.3. R-отношение
2.2.4. Возможные приложения
2.3. Алгоритм R-маршрутизации
2.3.1. Постановка задачи
2.3.2. Базовый алгоритм
2.3.3. Модификации
2.4. Выводы по главе

Глава III. Экспериментальное тестирование
3.1. Имитационное моделирование сетевой среды
3.2. Программная модель (симулятор)
3.2.1. Библиотека PeerSim
3.2.2. Структура имитационной модели
3.3. Тестирование алгоритма маршрутизации
3.3.1. Исследование R-отношения
3.3.2. Исследование параметров
3.4. Выводы по главе
Глава IV. Макетная реализация
4.1. Цели и задачи
4.2. Лабораторный стенд
4.2.1. Аппаратное обеспечение
4.2.2. Программное обеспечение
4.3. Проведение испытаний
4.3.1. Подключение устройств
4.3.2. Формирование маршрутных таблиц
4.3.3. Имитация разрывов маршрутов при передаче данных
4.4. Выводы по главе
Заключение
Список использованных источников

Введение
Предмет исследования
В последнее время наблюдается повышенный интерес к беспроводным вычислительным сетям, где в качестве среды передачи используются радио или инфракрасные каналы. Подобные технологии передачи данных — одно из наиболее быстро прогрессирующих направлений телекоммуникационного рынка. Они проникают повсюду, вытесняя проводные сети - региональные, локальные, персональные. При этом одним из наиболее востребованных сегодня направлений является использование т.н. сетей MANET — неструктурированных мобильных вычислительных сетей. Это сети нового типа, которые обладают рядом существенных преимуществ: повышенной надежностью, быстротой развертывания и способностью к самоорганизации, малой ресурсоемкостью, масштабируемостью. Такие сети могут использоваться при проведении встреч, конференций, поисковых и спасательных операций, в ходе военных действий, для создания сенсорных сетей, резервных систем связи и многих других областях.
Отличительная черта MANET — отсутствие фиксированной структуры и централизованного управления. Поэтому каждый узел в такой сети должен самостоятельно определять наилучший маршрут для передачи данных другим узлам. Алгоритмы, разработанные специально для решения этой задачи, получили название алгоритмов маршрутизации.
В отличие от классических проводных сетей, где топология изменяется очень редко, маршрутизация в мобильных сетях сопряжена со значительными трудностями. С одной стороны, маршрутизация является основой функционирования всей сети и должна работать максимально надежно. С другой, неустойчивая природа MANET не дает возможности применять «проверенные» способы поддержки маршрутной информации, сводя их эффективность к нулю. Поэтому с самого зарождения MANET начались активные поиски новых, специализированных алгоритмов маршрутизации.

(і(у -» и) — Е(у -» и) І - длина маршрута (у -» и). сДн, и) = шіп{(уи)] гі(і7 -» и) - расстояние от вершины г? до и. Зафиксируем произвольную вершину графа 170 Є V и число п Є М. Определение, п-окрестностью вершины г?0 называется граф, образованный множеством всех маршрутов длиной не более п и проходящих через вершину у0 :
дп(Уо) = С(у(А),Е(А)),
А = {(у -* и): <1(у -* и) < п, г0 Е У(у -* и)}
Отметим следующие очевидные свойства п-окрестности:
1. РпСо) есть подграф графа С(У, Е), порожденный множеством ребер Я(сЛ);
2. множество вершин п-окрестности образует замкнутый шар с центром 170, т.е. с1(у0, и) < п/и Є К(£„О0));
3. 9п(Уо) содержит только ребра всех простых цепей графа С(Е, Е) длиной не более п из вершины п0 (напомним, что простой цепью называется маршрут, не содержащий повторяющихся вершин -кроме, быть может, конечных). Действительно, любое ребро е(н1,ц2) е Е(<А) содержится в маршруте (у0 -* щ) или (у0 -» и2) длиной не более п. Следовательно, существует простая цепь [70, с. 10] из 17о в щ или и2, длиной не более 71, также содержащая е( щ,и2).
Также заметим, что п-окрестность не совпадает, в общем случае, с подграфом, порожденным множеством вершин V (А). В самом деле, если найдутся две вершины гга, гг2 Є Е(сД), удовлетворяющие условиям <2(і70, щ) = сі(р0,щ) = п и е(щ, и2) Є Е, то ни один маршрут из множества А не будет содержать ребро е(щ, и2).
Найдем множество всех простых цепей, упомянутое в свойстве 3.
Пусть X = (ху); і,у = ОД