Автоматика и телемеханика, № 10, 2013
© 2013 г. А.А. САФОНОВ, канд. техн. наук, А.И. ЛЯХОВ, д-р техн. наук (Институт проблем передачи информации им. А.А. Харкевича РАН, Москва), А.Н. ЮРГЕНСОН, канд. физ.-мат. наук, О.Д. СОКОЛОВА, канд. техн. наук (Институт вычислительной математики и математической геофизики СО РАН,
Новосибирск)
МНОГОАДРЕСНАЯ МАРШРУТИЗАЦИЯ С ВОЗМОЖНОСТЬЮ ВЫБОРА МЕТОДА ПЕРЕДАЧИ В КАНАЛЕ 1
Рассматривается задача поиска многоадресного маршрута в беспроводной многошаговой сети в следующей постановке: в классе древовидных маршрутов найти маршрут минимальной стоимости, вычисляемой с учетом метода передачи, применяемого протоколом канального уровня. Если метод передачи использует широковещательную природу беспроводной среды, то число попыток передачи, выполняемое каким-либо ретранслятором маршрута, и их стоимость зависят от того, какие из его соседних узлов включены в этот маршрут. Этим рассматриваемая задача существенно отличается от классической задачи поиска дерева Штейнера. Проведен анализ чувствительности стоимости маршрута к используемым методам передачи. Предложен ряд алгоритмов построения многоадресного маршрута, учитывающих структуру методов передачи и позволяющих существенно снизить стоимость маршрута.
1. Введение
Доставка многоадресных пакетов была и остается важнейшим сервисом в беспроводных сетях профессиональной мобильной связи [1] (например, в сетях, развертываемых в местах стихийных бедствий или большого скопления людей) и в тактических сетях, в том числе многошаговых. Однако повсеместное распространение мобильных беспроводных устройств и связанное с этим появление перспективных ниш на рынке телекоммуникационных услуг создали предпосылки для предоставления такого сервиса и устройствам потребительской электроники в сетях коммерческих операторов связи, Internet of Things и т.д.
Одним из самых распространенных протоколов беспроводной связи устройств потребительской электроники является IEEE 802.11 [2], продолжающий свое развитие уже 15 лет и широко известный под торговой маркой Wi-Fi. В 2010-2011 гг. появились черновые версии дополнений к этому протоколу IEEE 802.11ac/ad для работы со скоростью передачи до 1 Гбит/с.
1 Исследование частично выполнено в рамках проекта FP7-ICT FLAVIA (contract No. 257263) при финансовой поддержке Российского фонда фундаментальных исследований в рамках проектов № 12-07-33067 мол_а_вед, № 12-07-31252 мол_а и № 11-07-00183-а.
6 Автоматика и телемеханика, № 10
137
В конце 2011 г. опубликовано дополнение IEEE 802.11s [3], регламентирующее работу многошаговых самоорганизующихся сетей Wi-Fi Mesh, а в середине 2012 г. - дополнение IEEE 802.11aa [4], описывающее несколько разных по структуре методов надежной передачи многоадресных пакетов на каждом шаге маршрута в mesh-сети, повышающих отказоустойчивость таких сетей. Эти методы заставляют взглянуть по-новому на задачу многоадресной маршрутизации в многошаговых беспроводных сетях.
О разных постановках и решениях задачи многоадресной маршрутизации опубликовано множество работ, даже краткий обзор которых составил бы книгу. Во всех этих работах сеть представляется графом, взвешенным в некоторой метрике маршрутизации и на котором с помощью разумного по сложности и точности алгоритма выполняется поиск дерева Штейнера [5], соответствующего многоадресному маршруту.
Метрика, в которой взвешиваются дуги графа, отражает критерий эффективности маршрутизации, описывающий требования пользователя и используемые в сети алгоритмы и протоколы. В литературе чаще всего упоминают о двух критериях, во многом взаимосвязанных: o среднем времени доставки пакетов в сети и o пропускной способности сети. В случае передачи мультимедийных потоков, доля которых в общем объеме трафика телекоммуникационных операторов удваивается каждый год [6], на первый план в качестве критерия эффективности маршрутизации выходит емкость сети, измеряемая в числе одновременно передаваемых потоков, для которых выполнены требования к качеству обслуживания (QoS).
Известны различные метрики маршрутизации, связанные с этими критериями напрямую или эвристически [7]. В частности, широко применяется гипотеза, что стратегия, направленная на минимизацию канальных ресурсов, используемых при доставке пакета, ведет к максимизации емкости сети. Основываясь на такой гипотезе, IEEE 802.11s [3] предлагает метрику Air Time Link metric (ATL), вычисляемую как объем потребляемых передачей канальных ресурсов, равный среднему времени, необходимому для передачи пакета с учетом повторных попыток передачи, если таковые требуются. В данной статье в качестве метрики стоимости маршрута также используется среднее время занятия канала, необходимое для доставки пакета, но (в отличие от метрики ATL) определяемое для разных по структуре методов надежной передачи многоадресных пакетов, которые могут быть использованы протоколом канального уровня.
Итак, классический метод доставки многоадресного трафика состоит в построении дерева минимального веса и в передаче многоадресных пакетов по каждой дуге построенного дерева индивидуальным образом, как если бы передаваемый по дуге пакет был одноадресным. Этот метод доставки разработан для проводных сетей и основан на предположении, что веса дуг дерева аддитивны и являются независимыми величинами, в том числе веса дуг, исходящих из одной вершины дерева. Справедливость этого предположения в случае беспроводной сети зависит от метода передачи, применяемого на каждом шаге маршрута. Так, при использовании метода индивидуальных передач (см. подраздел 3.1) это предположение выполняется, и в случае неограниченного числа повторных передач вес дуги описывается метрикой ATL.
Однако этот метод не использует очевидное преимущество широковещательной природы передачи в беспроводной среде: если положительная степень вершины графа (число исходящих дуг) больше единицы, то доставка пакета всем ее соседним вершинам возможна с помощью одной передачи.
Это преимущество, очевидно, используется при широковещательном методе передачи (англ. broadcast). В [8] показано, что при таком методе маршрут в виде дерева Штейнера в общем случае не является минимальным в выбранной стоимостной метрике, и предложен алгоритм построения дерева минимального веса, нацеленный на минимизацию числа ретрансляторов. К сожалению, широковещательный метод передачи предполагает, что каждый узел-ретранслятор, включенный в дерево, передает пакет ровно один раз, что во многих сценариях не позволяет обеспечить требуемую надежность. Тем не менее исследование [8] чрезвычайно полезно, так как показывает значительный выигрыш, получаемый при учете широковещательного метода передачи в алгоритме маршрутизации.
Для использования преимущества широковещания в беспроводной среде и (вместе с тем) обеспечения надежности дополнение IEEE 802.11aa [4] предлагает два новых метода надежной передачи многоадресных пакетов: метод безусловных повторов и метод блочной передачи (см. подразделы 3.2 и 3.3). Чтобы оценить выигрыш от применения этих методов на уже построенном маршруте, в данной статье проведено следующее исследование. С помощью классического алгоритма, в качестве которого выбран алгоритм, предложенный в [9] (пожалуй, самый простой приближенный алгоритм построения дерева Штейнера), на графе, дуги которого взвешены в метрике ATL, построим дерево минимального веса. Будем называть маршрут, описываемый этим деревом, эталонным маршрутом, а вес этого дерева в метрике ATL — эталонным весом. Сравним эталонный вес с весами, получаемыми при передаче по эталонному маршруту каким-либо методом передачи пакетов, описанным в IEEE 802.11aa, и в предположении, что для выполнения требований к качеству обслуживания необходимо обеспечить вероятность доставки пакета по каждой дуге маршрута не ниже некоторого порогового значения, которое обозначим 1 — q (т.е. q — максимально допустимая вероятность потери пакета на шаге маршрута). В отличие от метрики ATL, предполагающей абсолютную надежность передачи, данное предположение лучше соответствует упомянутому критерию эффективности маршрутизации мультимедийных потоков, когда требуется максимизировать число одновременно передаваемых потоков при ограничении сверху на долю потерянных пакетов, но необязательно добиваться стопроцентной вероятности доставки. Математическая модель методов передачи пакетов, описанных в IEEE 802.11aa, необходимая для оценки стоимости маршрута, разрабатывается в разделе 3.
Как показало это предварительное исследование (см. раздел 4), применение новых методов передачи уже само по себе дает значимый эффект, несмотря на то, что дерево Штейнера построено классическим алгоритмом, не учитывающим структуру этих методов. Ключевой вопрос, которому посвящена данная статья, — какого эффекта в смысле снижения стоимости маршрута можно достигнуть, если учитывать структуру метода передачи при построении маршрута.
6* 139
Чтобы учесть в алгоритме маршрутизации широковещательный принцип новых методов передачи, вес маршрута представляется суммой весов вершин, а не весов дуг. Вес вершины при этом является функцией множества соседних вершин, включаемых в маршрут, и связан с вероятностями успешных попыток передачи на исходящих дугах уравнениями, описывающими структуру используемого метода передачи многоадресных пакетов. В рамках этой модели сети в разделе 5 разрабатываются алгоритмы построения дерева минимального веса, учитывающие структуру используемых методов надежной передачи, и анализируется эффективность предложенных алгоритмов построения маршрутного дерева с учетом используемого метода передачи в смысле веса построенного дерева в сравнении с эталонным весом.
Сравнительный анализ деревьев, в каждом из которых все вершины используют один и тот же метод передачи, показал, что эффективность этих методов зависит от числа соседних вершин, включенных в дерево, и от вероятностей успешной передачи по дугам до этих вершин. Поэтому при наличии нескольких разных по структуре методов передачи естественно позволить алгоритму маршрутизации выбирать метод передачи и указывать его протокол
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.