ДонНТУ |
Портал магистров ДонНТУ |
Обо мне |
Библиотека |
Ссылки |
Отчет о поиске |
Индивидуальный раздел |
Актуальность темы
В настоящее время беспроводные сети представляют собой наилучшее решение для организации доступа по совокупности
показателей быстроты и стоимости разворачивания, простоте подключения пользователей, степени зависимости от окружающих
условий. Использование беспроводных технологий со временем становится все более распространенным способом доступа в
Интернет или к локальным корпоративным, кампусным или частным сетям.
Проблема мобильного узла - относительно новое явление, но, тем не менее, она стоит довольно остро. Миллионы людей в наши дни путешествуют,
находятся в командировках. Многим из них просто необходимо иметь доступ к своему постовому ящику электронной почты, своей файловой
системе.
Таким образом, вопрос совместимости протоколов и стандартов при построении беспроводных сетей сегодня чрезвычайно актуален. В работе
рассматриваются вопросы оптимизации протоколов беспроводных сетей по скорости и надежности передачи и основные задачи, что возникают при
создании оптимальных протоколов маршрутизации в этих сетях.
Научная значимость работы
Развитие радиосетей передачи данных в настоящее время занимает одно из важнейших мест среди задач технического прогресса. В первую очередь эти
системы призваны обеспечивать беспроводный доступ к узлам провайдеров сетевых услуг, как для подвижных абонентов, так и для стационарных, в условиях,
когда прокладка кабелей к ним технически невозможна или экономически невыгодна.
В настоящее время все еще очень мало опубликованных русско- и украиноязычных обзорных работ об алгоритмах маршрутизации в беспроводных сетях, в то
время как в англоязычной литературе эта тематика представлена достаточно широко. Данная работа должна внести вклад в преодоление этого отставания и в
оптимизацию существующих методов маршрутизации на примере предлагаемого альтернативного алгоритма.
Маршрутизация в беспроводных сетях имеет свои особенности. «Узким местом» тут обычно является фиксированная инфраструктура с ее ограничениями на передачу
трафика между пользователями. В таком случае мобильные устройства должны функционировать в автономном режиме, самостоятельно проводя установление связи с другими
узлами сети, тем самым выполняя некоторые функции маршрутизатора. Усложнения их работы обусловлено характером рассмотренных нами сетей, где узлы-пользователи могут
когда угодно изменять свое местоположение, тем самым постоянно изменяя топологию и общаясь между собой без создания каких-либо определенных стационарных путей
передачи данных. Такие сети носят название MANET (mobile ad hoc networks). В этом случае узлы должны сотрудничать для обеспечения качественной маршрутизации, в
отличие от традиционных WLAN, где абонентское оборудование централизованно управляется точками доступа.
Все эти особенности позволяют сетям значительно варьировать по количеству абонентов: от нескольких единиц до сотен. Соответственно, для различных примеров структуры
спроектировано и создано много протоколов, некоторые из которых будут рассмотрены в данной работе.
Протоколы маршрутизации MANET делятся на две группы: проактивные (tabledriven/proactive routing protocols) и реактивные (on-demand/reactive routing protocols). Особенность первой
группы в том, что узлы сети постоянно собирают и обновляют информацию о ее состоянии, обмениваясь ею с соседями. Проактивные протоколы требуют от узла ведения таблиц
маршрутизации, где указаны маршруты, которые позволяют достичь любого абонента сети. Специальные алгоритмы используются для поддержки актуальности этой информации.
В связи с этим все изменения в топологии сети распространяются в ней. К проактивным протоколам относятся TBRPF (Topology Dissemination Based on Reverse-Path Forwarding ), OLSR
(optimized link state routing), DSDV (Highly Dynamic Destination-Sequenced Distance-Vector Routing).
В протоколах реактивной группы узел ищет путь к пункту назначения только при возникновении необходимости. Для этого существуют две основных операции: поиск маршрута и поддержка
маршрута. Когда узел намерен установить связь и начинает устанавливать маршрут, информацию о доступных каналах он получает по запросам. Для поддержки информации о маршрутах узлы
должны реагировать на изменения в топологии сети. Узел, у которого есть информация о каком-то канале, должен стремиться детектировать его отказ, если это происходит. Основные реактивные
протоколы: DSR (Dynamic Source Routing protocol), AODV (Ad Hoc On-Demand Distance Vector), DYMO (Dynamic MANET On-demand).
Позднее были предложены другие протоколы для пакетных радиосетей, в которых были сделаны попытки соединить преимущества и избавиться от недостатков каждой из групп. Примером
является протокол BVR (Beacon Vector Routing), который использует технологии «жадного продвижения пакетов» (greedy forwarding) и построения системы логических координат, унаследованные
от предыдущих протоколов. Его особенностью является создание ряда «маяков» (beacons), случайно выбранных узлов, которые играют роль синхронизаторов в сети. На их основе строится «дерево»
сетевой структуры, определяются показатели маршрутов и осуществляется построение путей к пунктам назначения: поиск ближайшего соседа, назначение его как следующего элемента маршрута и
переход до его ближайшего соседа (реализация алгоритму «жадного продвижения»). Отличием BVR является применение при этом не географических, а логических координат. Главное назначение
протокола - поддержка соединениий «точка-точка» (point-to-point). Позднее на его основе был разработан протокол LCR (Logical Coordinate Routing).
Таким образом, вопрос адаптивной маршрутизации в беспроводных сетях является объектом интенсивного изучения и многих исследований. Развитие протоколов маршрутизации в беспроводных
сетях идет по пути децентрализации управления трафиком и гибридизации как результата попыток объединения различных подходов. В настоящее время темпы усложнения сетевой инфраструктуры
опережают процессы стандартизации, так что какие-либо конкретные общеупотребительные протоколы пока не выделились.
В данной работе предлагается оптимизированный вариант - алгоритм альтернативной маршрутизации, разработанный на основе существующих решений. Он использует принципы построения
кратчайших путей, которые применяются в алгоритмах Дейкстри и Беллмана-Форда, и методы определения средней задержки, традиционные для сетей с пакетной коммутацией.
Разработанный для ретрансляторов алгоритм альтернативной маршрутизации основан на минимизации средней задержки на всех кратчайших маршрутах, причем определение задержек на участках
включает анализ статических характеристик сети (топологии и пропускных способностей каналов связи) и характера передаваемого трафика (учет оптимальных показателей задержек для разных видов
трафика).
В алгоритме предусмотрены механизмы анализа пропускных способностей каналов связи с точки зрения их оптимальности, расчет оптимального веса путей на основании этой информации и минимизации
функции задержки у сети на основании анализа потока по маршрутам, при котором размер задержки мог бы соответствовать общепринятым характеристикам передачи определенных видов трафика.
Алгоритм использует принципы построения кратчайших путей, которые используются в алгоритмах Дейкстры и Беллмана-Форда, и способы определения средней задержки, традиционные для сетей с пакетною
коммутацией. Функциональная блок-схема алгоритма приведена на рисунке и включает следующие составляющие:
1. Блок определения оптимальных пропускных способностей - анализирует базовую топологию сети и определяет оптимальность пропускных способностей. На основании полученных данных подсчитывает
вес каналов связки сети для дальнейшего анализа.
2. Блок анализа среднего времени задержки - отвечает за расчет среднего времени задержки в сети на основании оптимальных пропускных способностей и начальных потоков в сети.
3. Блок определения маршрутов - отвечает за построение кратчайших маршрутов между всеми узлами сети.
4. Блок построения допустимого потока - обеспечивает распределение потоков по кратчайшим путям.
5. Блок минимизации средней задержки - обеспечивает расчет девиации потоку на основе минимизированной функции значения средней задержки в сети.
6. Тело алгоритма - объединяет работу каждого из блоков и обеспечивает последовательное функционирование алгоритма.
Сформулируем задачи, которые должны быть решены с помощью спроектированного алгоритма:
1) наиболее рациональное использование каналов;
для решения задачи используются следующие приемы:
а) анализ пропускных способностей каналов связи в сети и расчет оптимальных меток;
б) использование альтернативных маршрутов;
в) распределение трафика между альтернативными маршрутами исходя не из соотношения суммарных метрик маршрутов, а из соотношения максимальных метрик каналов
данного маршрута;
г) выбор доступных для использования альтернативных маршрутов только по критерию максимального времени передачи (маршрут может быть принят к использованию, если время передачи по маршруту не превышает
установленного для данного типа трафика максимально допустимого).
2) соблюдение требований к параметрам сетевой передачи.
Далее рассмотрим приемы решения указанных задач;
задача соблюдения требований к параметрам сетевой передачи решается таким способом:
а) минимизация задержки передачи сообщений в сетях сложной топологии;
б) минимизация СКВ задержки.
Сделаем оценку оптимальности функционирования по алгоритму. Введем обозначения:
где і - номер пары узел-адресат - узел-получатель;
первая формула - поток пакетов, которые поступают в і-ый канал; вторая - поток пакетов, поступающих из узла в сеть.
Нагрузку і-ого канала пакетами считаем по следующей формуле:
где первый множитель - средняя длина пакета, Di - пропускная способность і-ого канала.
Среднее количество пакетов в і-ом канале составляет:
Учитывая общее количество узлов в сети, среднее количество пакетов у сети в целом составляет:
В соответствии с формулой Литтла
где Т - средняя задержка в сети. Таким образом, получаем формулу Клейнрока для анализа средней задержки
в сети: 
Полученная формула для оценки времени задержки эффективно используется для решения различных
оптимизационных задач. К таким задачам относят оптимизацию пропускной способности каналов и выбор
маршрутов передачи сообщений.
Данная работа посвящена решению проблем оптимизации методов маршрутизации в современных беспроводных сетях. Приведенный обзор существующих протоколов должен дать общее понятие текущих проблем в отрасли, преимуществ и
недостатков существующих решений и возможные пути развития.
Одним из перспективных решений может стать предлагаемый в данной работе алгоритм маршрутизации для ретрансляторных станций. Он призван оптимизировать их
функционирование в составе магистральной транспортной сети мобильной связи. Применение альтернативной маршрутизации, по результатам проверки работы алгоритма с помощью специально разработанной программы, позволяет снизить
почти вдвое среднюю задержку в сети, если сравнивать с результатами работы по алгоритмам Дейкстры и Беллмана-Форда.
Обо мне |
Библиотека |
Ссылки |
Отчет о поиске |
Индивидуальный раздел |