Анализ взаимодействия алгоритмов

Анализ взаимодействия алгоритмов многоадресной маршрутизации
и методов передачи в беспроводной сети
Анастасия Юргенсон, Ольга Соколова
ИВМиМГ СО РАН
{nastya,olga}@rav.sscc.ru
Аннотация
Александр Сафонов, Андрей Ляхов
ИППИ РАН
{safa,lyakhov}@iitp.ru
В середине 2012г. – дополнение IEEE 802.11aa, описывающее несколько различных по структуре методов надежной передачи многоадресных пакетов на
каждом шаге маршрута в mesh-сети. Эти методы заставляют взглянуть по-новому на задачу маршрутизации в mesh-сетях.
О различных постановках и решениях задачи
многоадресной маршрутизации написано множество
работ. Общим подходом является представление сети графом, взвешенным в некоторой метрике маршрутизации, на котором с помощью разумного с точки зрения сложности и точности алгоритма выполняется поиск дерева Штейнера [3], представляющего
собой многоадресный маршрут.
Метрика, в которой взвешиваются дуги графа,
отражает критерий эффективности маршрутизации,
описывающий требования пользователя и используемые в сети алгоритмы и протоколы. В литературе
чаще всего упоминают о двух критериях, во многом
взаимосвязанных: среднем времени доставки пакетов в сети и пропускной способности сети. В случае
передачи мультимедийных потоков, доля которых в
общем объеме трафика телекоммуникационных операторов удваивается каждый год [5], на первый план
в качестве критерия эффективности маршрутизации
выходит емкость сети, измеренная в числе одновременно передаваемых потоков, для которых выполнены требования к качеству обслуживания (QoS). В
литературе описаны различные метрики маршрутизации [4], связанные с этими критериями напрямую
или эвристически. В частности, широко применяется
гипотеза о том, что стратегия, направленная на минимизацию канальных ресурсов, используемых при
доставке пакета, ведет к максимизации емкости сети.
Основываясь на этой гипотезе, IEEE 802.11s предлагает метрику Air Time Link metric (ATL), вычисляемую как объем потребляемых передачей канальных
ресурсов, равный среднему времени, необходимому
для передачи пакета с учетом повторных попыток
передачи, если таковые потребуются. Далее в статье
мы также используем в качестве метрики стоимости
маршрута среднее время занятия канала, необходи-
В работе1 проведен анализ чувствительности стоимости доставки многоадресных пакетов к используемому методу передачи в беспроводных многошаговых сетях. Рассмотрены методы надежной передачи многоадресных пакетов, описанные в 2012г. в
дополнении IEEE 802.11aa к стандарту сетей WiFi. Предложен ряд алгоритмов построения многоадресного маршрута, учитывающих структуру
этих методов передачи и тем самым позволяющих
существенно снизить стоимость доставки пакетов по сравнению с эталонным маршрутом, в качестве которого использовано дерево Штейнера, построенное алгоритмом Takahashi и Matsuyama.
1. Введение
Доставка многоадресных пакетов была и остается основным сервисом в сетях специального назначения [1], в том числе, многошаговых. Однако продолжающееся распространение мобильных беспроводных устройств в последние годы и связанное с
этим появление перспективных ниш на рынке телекоммуникационных услуг создало предпосылки для
предоставления такого сервиса и устройствам потребительской электроники в сетях коммерческих операторов связи, Internet of Things и т.д.
Одним из самых распространенных протоколов беспроводной связи устройств потребительской
электроники является IEEE 802.11 [2], продолжающий свое развитие уже 15 лет и широко известный
под торговой маркой Wi-Fi. В 2010-2011гг. появились черновые версии дополнений к этому протоколу IEEE 802.11ac/ad для работы со скоростью передачи до 1Гбит/с. В конце 2011г. опубликовано дополнение IEEE 802.11s, регламентирующее работу многошаговых самоорганизующихся сетей Wi-Fi Mesh.
1 Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 12-07-31252 мол_а
235
мое для доставки пакета, но, в отличие от метрики ATL, определяемое с учетом различных структур
используемых методов надежной передачи многоадресных пакетов.
новременно передаваемых потоков при ограничении
сверху на долю потерянных пакетов, но добиваться
100%-ой вероятности доставки – необязательно.
Как показало проведенное исследование, применение новых методов передачи само по себе дает значимый эффект, несмотря на то, что дерево Штейнера построено классическим алгоритмом, не учитывающим структуру этих методов.
Ruiz et al. продемонстрировали в [6], что в беспроводных сетях такое дерево Штейнера минимальным в выбранной стоимостной метрике в общем
случае не является. Учитывая широковещательную
природу передачи в беспроводной среде, Ruiz et al.
предложили свой алгоритм построения дерева минимального веса, нацеленный на минимизацию числа
ретрансляторов, что оправдано следующим предположением о методе доставки пакетов. Каждый узелретранслятор, включенный в дерево, передает пакет
ровно один раз, доставляя его при этом всем своим
соседним узлам, в том числе следующим в дереве
ретрансляторам (разумеется, с некоторой вероятностью, вообще говоря меньшей единицы).
Методы, описанные в IEEE 802.11aa, обеспечивают надежную доставку многоадресных пакетов с помощью повторных передач. Алгоритм, предложенный в [6], повторных передач не предусматривает
и поэтому оказывается неприменим. Тем не менее,
исследование Ruiz et al. чрезвычайно полезно, так
как показывает значительный выигрыш, получаемый при учете широковещательного метода передачи в алгоритме маршрутизации.
В данной работе для того, чтобы учесть в алгоритме маршрутизации широковещательный метод
передачи, вес маршрута представляется как сумма весов вершин, а не весов дуг. Вес вершины при
этом является функцией множества соседних вершин, включаемых в маршрут, и связан с вероятностями успешных попыток передачи на исходящих
дугах уравнениями, описывающими структуру используемого метода передачи многоадресных пакетов. В рамках этой модели сети разработаны алгоритмы построения дерева минимального веса, учитывающие структуру используемых методов надежной передачи.
В работе проведен сравнительный анализ маршрутов, построенных с помощью разработанных алгоритмов. Результаты анализа позволяют оценить, вопервых, влияние метода передачи как такового на
стоимость доставки пакета по эталонному маршруту, а, во-вторых, эффективность предложенных алгоритмов построения маршрутного дерева с учетом
используемого метода передачи в смысле веса построенного дерева в сравнении с эталонным весом.
Сравнительный анализ деревьев, в каждом из
которых все вершины используют один и тот же метод передачи, показал, что эффективность этих ме-
Итак, классический метод доставки многоадресного трафика состоит в построении дерева минимального веса и в передаче многоадресных пакетов
по каждой дуге построенного дерева индивидуальным образом, как если бы передаваемый по дуге пакет был одноадресным. Этот метод доставки разработан для проводных сетей и основан на предположении, что веса дуг дерева аддитивны и являются
независимыми величинами, в том числе веса дуг, исходящих из одной вершины дерева. Справедливость
этого предположения в случае беспроводной сети зависит от метода передачи, применяемого на каждом
шаге маршрута. Так, при использовании метода индивидуальных передач (см. раздел 3.1) это предположение выполняется, и в случае неограниченного
числа повторных передач вес дуги описывается метрикой ATL. Однако этот метод не использует очевидное преимущество широковещательной природы
передачи в беспроводной среде: в случаях, когда положительная степень вершины графа (число исходящих дуг) больше единицы, доставка пакета всем
ее соседним вершинам возможна с помощью одной
передачи.
Для использования этого преимущества дополнение IEEE 802.11aa предлагает два других метода надежной передачи многоадресных пакетов: метод безусловных повторов и метод блочной передачи (см. разделы 3.2 и 3.3). Чтобы оценить, какой выигрыш дает применение этих методов само
по себе, в данной работе проведено следующее исследование. С помощью классического алгоритма,
в качестве которого выбран алгоритм, предложенный Takahashi и Matsuyama в [7] (пожалуй, самый
простой приближенный алгоритм построения дерева
Штейнера), на графе, дуги которого взвешены в метрике ATL, построим дерево минимального веса. Будем называть маршрут, описываемый этим деревом,
эталонным маршрутом, а вес этого дерева в метрике ATL – эталонным весом. Сравним эталонный вес
с весами, получаемыми при передаче по эталонному маршруту не методом индивидуальных передач,
а тем или иным методом передачи пакетов, описанным в IEEE 802.11aa, и в предположении, что для
выполнения требований к качеству обслуживания
необходимо обеспечить вероятность доставки пакета
по каждой дуге маршрута не ниже некоторого порогового значения, которое обозначим 1 − q. В отличие от метрики ATL, предполагающей абсолютную
надежность передачи, данное предположение лучше соответствует вышеупомянутому критерию эффективности маршрутизации мультимедийных потоков, когда требуется максимизировать число од-
236
тодов зависит от числа соседних вершин, включенных в дерево, и от вероятностей успешной передачи по дугам до этих вершин. Поэтому при наличии
нескольких различных по структуре методов передачи естественно позволить алгоритму маршрутизации выбирать метод передачи и указывать его протоколам канального уровня на каждом шаге маршрута
независимо от предыдущих и последующих шагов.
В данной работе приведены результаты применения
такого адаптивного выбора метода передачи на каждом шаге.
Передатчик
Приемник 1
Data 1
Data 1
Ack
Приемник 2
...
Data 2
Data 2
Ack
Ack
Ack
Рис. 1. Пример последовательности кадров при
передаче методом индивидуальных передач.
Data 2
2
Data 1
Передатчик Data 1
...
Узел-передатчик
передает Data
кадры
данных (Data)
двум узлам-приемникам.
Приемник 1
Приемник 2
ется средним временем занятия беспроводной среды,
необходимым для доставки пакета, с учетом используемой сигнально-кодовой конструкции, определяюBlock
Block
Передатчик
Data передачи,
1
Data 2 ... и Data
b
щей
скорость
необходимого
числа
AckReq
AckReqпопыток передачи для доставки пакета наBlock
каждом шаге
Приемник 1
маршрута
[8]. В данной работе это определение
расAck
ширено
для
учета
методов
надежной
передачи
мноBlock
Приемник 2
гоадресных пакетов на шаге маршрута, описанныхAckв
IEEE 802.11aa [9]. В разделе 3 для этих методов разработаны модели, позволяющие оценить вес вершины, т.е. среднее время занятия канала, необходимое
для передачи пакета на шаге маршрута.
2. Математическая модель многоадресной маршрутизации
Mesh-сеть. Сеть представляется направленным
взвешенным графом G(V, E), где множество вершин
V соответствует множеству узлов сети, а множество
дуг E – звеньям между этими узлами. Каждой дуге
ei j ∈ E, ∀i, j ∈ V приписана вероятность pi j того, что
попытка передачи пакета узлом i узлу j окажется
неудачной.
Маршрут. Пусть вершина s ∈ V соответствует
узлу-источнику многоадресных пакетов, а множество вершин D ⊂ V, s ∈
/ D – множеству получателей
этих пакетов. Многоадресным маршрутом называется дерево T ⊆ G, включающее (покрывающее) вершины D, с корнем в вершине s. Будем называть шагом маршрута совокупность вершины i ∈ T и множества J = { j1 , j2 , . . . , jk } ее прямых потомков и говорить, что вес вершины i зависит от того, какие вершины J включены в дерево на данном шаге маршрута2 . Для определения веса C(i) каждой вершины
i ∈ T ей приписаны два вещественных числа: стоимость c одной попытки передачи и число n таких попыток. Для листьев дерева c = 0 и n = 0. Для вершины i, не являющейся листом, значения c(i, J) и n(i, J)
зависят от множества J ее прямых потомков и связаны с {pi j1 , . . . , pi jk } уравнениями, описывающими метод передачи: см. раздел 3. Вес вершины равен произведению C(i) = c(i, J)n(i, J). Вес дерева (стоимость
маршрута) складывается из весов вершин, включенных в это дерево.
3. Математическая модель методов надежной передачи
3.1. Метод индивидуальных передач
Метод индивидуальных передач (англ. directed
multicast service, DMS) заключается в передаче многоадресного пакета на каждом шаге маршрута, как
если бы пакет был одноадресным. Узел i ∈ T , имеющий в дереве множество потомков J = { j1 , j2 , . . . , jk },
передает пакет каждому из потомков индивидуально. При этом каждый потомок подтверждает кадром
Ack получение пакета (см. рис.1), а узел i выполняет повторные попытки передачи неподтвержденных
пакетов, за счет чего обеспечивается необходимая вероятность доставки. Таким образом, число попыток
передачи является случайной величиной.
Для того, чтобы на шаге маршрута обеспечить
каждому потомку j ∈ J вероятность доставки не ниже 1 − q и при этом минимизировать среднее время
занятия беспроводной среды, ограничим число возможных попыток передачи значением dlog pi j qe, где
dxe – минимальное целое, большее или равное x. Тогда среднее суммарное число попыток передачи узлом i для доставки многоадресного пакета на данном
шаге маршрута равно
Постановка задачи многоадресной маршрутизации. В данной работе используется следующая
постановка задачи. В классе древовидных маршрутов, таких что вероятность доставки пакета по каждой дуге маршрута не ниже заданного порогового
значения 1 − q, найти маршрут, на котором целевая функция достигает минимума. Целевая функция, принятая для сетей Wi-Fi Mesh, напрямую зада-
dlog p qe
nD (i, J) =
2 Для
краткости, здесь и далее, факт принадлежности узла
i множеству вершин в графе T и дуги ei j множеству дуг графа
T будем обозначать соответственно записью i ∈ T и ei j ∈ T .
∑
j∈J
1 − pi j
ij
1 − pi j
.
(1)
Из структуры данного метода передачи много-
237
Приемник 2
Передатчик
адресного пакета на шаге маршрута следует, что стоимость попытки передачи пропорциональна сумме
l + ξ , где l – длина пакета, а ξ = ξD > 0 – константа,
характеризующая накладные расходы данного метода (передача подтверждения и межкадровые интервалы [2]). Коэффициент пропорциональности, соответствующий скорости передачи, зависящей от используемой сигнально-кодовой конструкции, имеет
размерность время−1 . Пусть все узлы сети используют одну и ту же сигнально-кодовую конструкцию
и соответственно одну и ту же скорость передачи.
Тогда без потери общности можно положить коэффициент пропорциональности равным единице.
Значение l/ξ зависит от типа передаваемого трафика. Так для голосовых пакетов, которые являются сравнительно короткими, можно считать ηvoice =
l/ξ ' 1. Для пакетов видео-потока ηvideo = l/ξ может
быть значительно больше и превышать ηvoice на один
порядок. Мы воспользуемся этим рассуждением при
численном анализе.
Таким образом, вес узла i ∈ T при использовании
метода индивидуальных передач равен
CD (i, J) = nD (i, J)(l + ξ ).
Приемник
Передатчик1
Data 1
Data 1
Data 1
Ack
Data 2
...
Data 2
Data 2
Ack
Data 1
Приемник
Приемник 21
...
Ack
Data 2
Ack
Ack
Приемник 2
Data 2
Data 2
Data 1
Передатчик Data 1
... при
Рис.
2. Пример последовательности
кадров
Block
Block
Передатчик
Data 1
Data 2 ... Data b
AckReq
AckReq
передаче
методом безусловных
повторных
пеПриемник 1
редач.
Узел-передатчик
передает
каждый
паBlock
Приемник 1
Ack
Приемник
2
кет
несколько
раз. Обратная связь
с узламиBlock
Приемник 2
приемниками
отсутствует.
Ack
Передатчик
Data 1
Data 2
...
Data b
Block
AckReq
Block
AckReq
Block
Ack
Приемник 1
Block
Ack
Приемник 2
Рис. 3. Пример последовательности кадров при
передаче методом блочной передачи.
CU (i, J) = nU (i, J)l.
(2)
(4)
3.3. Метод блочной передачи
Заметим, что при q → 0 числитель каждой дроби в (1) обращается в единицу, а вес маршрута,
являющийся суммой весов входящих в него узлов,
∑i∈T CD (i, J), принимает вид целевой функции, принятой в протоколе IEEE 802.11s [8].
Метод блочной передачи (англ. block ack) заключается в передаче нескольких многоадресных пакетов (блока пакетов) подряд и последующем сборе от
узлов-получателей подтверждений, в которых содержится информация о том, какие из пакетов блока
были получены, а какие нет. Узел i ∈ T , имеющий
в дереве множество потомков J = { j1 , j2 , . . . , jk }, широковещательно передает блок, содержащий b пакетов, и после этого с помощью кадра Block AckReq
запрашивает у некоторых потомков кадры блочного подтверждения – Block Ack (см. рис. 3). Узел i
выполняет повторные попытки передачи пакетов, не
подтвержденных хотя бы одним потомком, у которого подтверждение было запрошено, за счет чего
обеспечивается необходимая вероятность доставки.
Таким образом, как и в случае индивидуальных передач, число попыток передачи является случайной
величиной.
Метод блочной передачи является чрезвычайно
гибким инструментом и в зависимости от реализации (размера блока, алгоритма выбора числа опрашиваемых потомков и самих потомков и т.д.) предоставляет практически любое соотношение между достигаемой надежностью доставки пакета и накладными расходами на подтверждения, как показано,
например, в [10].
В данной работе рассматривается случай, когда
узел i опрашивает всех своих k прямых потомков в
маршруте. Как и при методе индивидуальных передач, число возможных попыток передачи одно-
3.2. Метод безусловных повторных передач
Метод безусловных повторных передач (англ.
unsolicited retry) заключается в доставке многоадресного пакета на каждом шаге маршрута путем выполнения фиксированного числа передач.
Узел i ∈ T , имеющий в дереве множество потомков
J = { j1 , j2 , . . . , jk }, передает пакет широковещательно
H(i) раз, а его потомки при этом получение пакета никак не подтверждают (см. рис.2). Очевидно,
максимум от вероятности недоставки пакета, взятый по всем k прямым потомкам, равен pH(i) , где
p = max j∈J {pi j }. Тогда минимальное значение nU (i, J)
числа H(i) попыток передачи многоадресного пакета, обеспечивающее вероятность его потери, не превышающую q, равно
nU (i, J) = dlog p qe.
Ack
(3)
Метод безусловных повторных передач не использует служебных пакетов, поэтому стоимость попытки передачи пропорциональна только длине пакета l, а ξ = 0. Таким образом, вес узла i ∈ T при
использовании метода безусловных повторных передач равен
238
го пакета следует ограничивать некоторым значением H(i) для минимизации среднего времени занятия
беспроводной среды, при этом обеспечивая каждому
потомку j ∈ J вероятность доставки не ниже 1 − q.
Следуя той же логике, что и в предыдущем разделе,
получаем H(i) = dlog p qe. Вероятность того, что хотя
бы один узел из множества J не получит пакет после
h попыток передачи, равна
πh (i) = 1 − ∏ 1 − phij ,
при передаче пакета узлом i соседнему узлу j. В данной работе приведены результаты для сети с N = 9;
r ∈ {r0 , r4 }, P ∈ {(0; 0, 3), (0, 3; 0, 6)}.
В рассматриваемой сети источником назначается один из угловых узлов решетки, а получателями
равновероятно выбираются остальные узлы. В работе рассмотрены случаи, когда число получателей
|D| = {3, 10, 20, 40, 70} (при том что число узлов сети – 81). Для каждого набора (r, P, |D|) генерируется
множество топологий сети, отличающихся вероятностями неудачи pi j ∈ P на звеньях сети и составом |D|
получателей; для каждой из этих топологий с помощью одного из алгоритмов, описанных далее в разделах 4 и 5 (в данном разделе для построения эталонного маршрута используется алгоритм Takahashi
и Matsuyama: см. раздел 4.1), строится маршрут в
виде дерева Штейнера; наконец, усредняя по множеству топологий, находится средний вес маршрута. В
получившихся сценариях варьируется длина пакета
l ∈ {1, 10}, что соответствует размеру голосового или
видео пакета, при ξB = 2ξD = 2. Во всех сценариях используются значения q = 0, 05 и b = 3 (см. описание
методов передачи).
j∈J
причем πh (i) можно также трактовать как вероятность того, что при передаче пакета узлом i потребовалась h+1-я попытка. Тогда среднее число попыток
передачи пакета узлом i равно
H(i)−1
nB (i, J) = 1 +
∑
h=1
H(i)−1
πh (i) = H(i) −
∑ ∏
1 − phij .
h=1 j∈J
(5)
При передаче блока пакетов стоимость попытки
передачи в расчете на один пакет пропорциональна
l + kξB /b (напомним, коэффициент пропорциональности мы положили равным единице). Из структуры
метода следует, что для подтверждения приема многоадресных пакетов каждым из k потомков необходимы два служебных кадра (на рис. 2 – кадры запроса подтверждения Block AckReq и собственно блочного подтверждения Block Ack), в отличие от метода
индивидуальных передач, который использует один
служебный пакет; поэтому, пренебрегая разностью
размеров пакетов, можно положить ξB = 2ξD .
Таким образом, вес узла i ∈ T при использовании
метода блочной передачи равен
CB (i, J) = nB (i, J)(l + kξB /b).
3.4.2. Результаты сравнения. На рис. 4 приведены результаты применения методов передачи, определенных в IEEE 802.11aa и описанных в разделе 3,
при передаче по эталонному маршруту (для всего
маршрута используется один и тот же метод) в случае l = 1. Результаты показывают, насколько средний вес эталонного маршрута снижается по сравнению со средним значением эталонного веса – веса эталонного маршрута при использовании метода
индивидуальных передач с неограниченным числом
попыток передачи, т.е. со 100%-ой надежностью доставки пакета.
Метод индивидуальных передач DMS практически не изменяет вес маршрута по сравнению с эталонным, так как ограничение числа возможных попыток передачи значением dlog pi j qe является слабым ввиду малости q. В то же время существенный
эффект оказывает учет широковещательной природы передачи в беспроводной среде, причем – любым из методов безусловных повторных передач или
блочной передачи, которые здесь и далее будем обозначать соответственно GCR-U и GCR-B3 .
Ключевой разницей в структуре этих методов
является наличие или отстутствие “обратной связи”
между приемником и передатчиком (сравнить рис. 2
и 3), которая, с одной стороны, составляет накладные расходы, но, с другой стороны, позволяет передавать пакеты данных повторно только тогда, когда
это необходимо. Благодаря отсутствию накладных
расходов на обратную связь метод GCR-U оказыва-
(6)
3.4. Сравнительный анализ стоимости передачи по эталонному маршруту при
разных методах надежной передачи
3.4.1. Постановка экспериментов. Численный
анализ проводится в серии следующих экспериментов. Рассматривается сеть, имеющая решетчатую
топологию, с числом узлов, равным N × N, и шагом решетки r. Мы меняем плотность размещения
узлов,
из множества
{r0 , r1 =
√
√ выбирая шаг решетки
√
r0 / 2, r2 = r0 /2, r3 = r0 / 5, r4 = r0 /2 2}, где r0 – такой шаг, при котором узлы решетки имеют наименьшее число соседей, отличное от нуля; например, для
узлов в центральной части сети число соседей равно
4 при r = r0 и 24 при r = r4 . Симметрия решетки нарушается путем равновероятного выбора из некоторого диапазона P значений вероятности pi j неудачи
3 Согласно IEEE 802.11aa эти методы объединяются общим
названием GroupCast with Retries – GCR
239
Рис. 4. Средние значения весов эталонного маршрута, нормированные к среднему эталонному весу, в
зависимости от числа получателей
редачи по звеньям сети (см. рис. 4), естественно позволить алгоритму маршрутизации выбирать метод
передачи на каждом шаге маршрута независимо
от предыдущих и последующих шагов и ожидать
от этого дополнительный вклад в снижение стоимости маршрута. Пунктирные линии на рис. 5 соответствуют результатам такого адаптивного выбора
метода передачи: значения эффекта вычисляется по
формуле Ea = 100%(Cэт −Ca )/Cэт , где Ca — средний
вес маршрута при адаптивном выборе. Сравнивая
значения E и Ea, можно заметить, что в большинстве случаев адаптивный выбор повышает эффект
от применения широковещательных методов передачи по сравнению с использованием одного и того же метода на всем маршруте незначительно: в
лучшем случае, повышение эффекта составляет около 12 процентных пунктов. По всей видимости, это
связано с тем, что в поставленных экспериментах
сеть является в значительной степени однородной в
смысле значений параметров, описанных выше.
ется эффективнее метода GCR-B при малых вероятностях неудачи при передаче пакета, когда необходимое число попыток передачи невелико, и разница в эффективности этих методов растет вместе с
плотностью размещения станций и числом получателей. При большой вероятности неудачи обратная
связь необходима и эффективнее использовать метод GCR-B, если только число получателей не превышает половины числа станций в сети.
Если задаться целью разработать алгоритм
маршрутизации, выбирающий оптимальный метод
передачи (в смысле стоимости маршрута), какого
эффекта можно ожидать от его применения? На
рис. 5 сплошными линиями приведены значения эффекта, вычисляемого по формуле E = 100%(Cэт −
min{CGR−U ,CGR−B })/Cэт , где Cэт – средний эталонный вес, а CGR−U и CGR−B – средние веса при использовании методов GCR-U и GCR-B. Эффект от применения методов GСR-U и GСR-B растет вместе с
плотностью размещения станций и долей станций сети, являющихся получателями многоадресных пакетов, так как в этих случаях положительная степень
вершин графа, соответствующего сети, также растет, и учет широковещательной природы передачи
в беспроводной среде все более оправдан. В частности, в приведенных сценариях моделирования при
низкой плотности размещения станций (r = r0 ) эффект находится на уровне 20 - 30%, а при высокой
плотности (r = r4 ) достигает 70%.
Ввиду того, что относительная эффективность
методов GCR-U и GCR-B оказывается весьма чувствительной к значениям вероятности успешной пе-
Тем не менее, результаты, полученные при адаптивном выборе метода передачи, удобно использовать в дальнейшем исследовании как реперные точки: значения Ea – это максимум, чего можно достичь, используя классический алгоритм построения
маршрута.
240
Рис. 5. Эффект от применения широковещательных методов передачи на эталонном маршруте в зависимости от числа получателей
4. Алгоритмы построения многоадресного маршрута
• Каждой дуге ei j ∈ E припишем вес ai j , вычисленный согласно (7).
2. Добавление очередного получателя.
4.1. Алгоритм Takahashi и Matsuyama
• Среди всех путей (td) найти кратчайший
путь (t ∗ d ∗ ) и включить его в дерево.
Первый приближенный алгоритм построения
дерева Штейнера, имеющий полиномиальную
сложность, был предложен в 1980г. Takahashi и
Matsuyama в [7]. Алгоритм работает на графе, в
котором веса приписаны дугам.
В данной работе алгоритм Takahashi используется для построения эталонного маршрута, и вес дуг
берется в метрике ATL, применяемой в протоколе
IEEE 802.11s [8] и имеющей смысл среднего времени
занятия среды, необходимого для передачи пакета
с учетом повторных попыток передачи в предположении, что для доставки многоадресных пакетов используется метод индивидуальных передач без ограничения на число попыток передачи. Для дуги ei j
метрику ATL можно записать в виде
ai j =
l + ξA
,
1 − pi j
• D0 = D0 \{d ∗ }.
3. Завершение работы.
• Если D0 = ∅ – конец алгоритма.
• В противном случае выполнить шаг 2.
4.2. Алгоритм учета широковещательного характера передачи
Предлагаемый алгоритм является модификацией алгоритма Takahashi и Matsuyama и позволяет
строить дерево минимального веса с учетом применения любого из методов, описанных в разделе 3.
Так как широковещательный характер передачи в
беспроводной среде приводит к модели сети, в которой стоимость передачи связана не с дугами, а с
вершинами, веса дуг вычисляются на основании весов вершин, из которых эти дуги исходят.
(7)
где ξA = ξD .
Обозначим как D0 множество непокрытых, т.е.
не включенных в дерево T , получателей, а (td) – путь
с началом в вершине t ∈ T и концом в вершине d ∈ D0 .
Алгоритм состоит из трех следующих шагов.
1. Инициализация.
• T = {s}, D0 = D.
1. Инициализация.
• Каждой дуге ei j ∈ E припишем вес, равный
весу C(i, J = { j}) вершины i, который она
• T = {s}, D0 = D.
241
имела бы при передаче пакета единственному прямому потомку j. Здесь C(i, J) вычисляется в зависимости от метода передачи по формулам (2), (4) или (6).
диапазоне значений числа получателей и вероятности неудачной передачи, а в некоторых точках увеличение эффекта достигает 20-ти процентных пунктов.
2. Добавление очередного получателя и переоценка дуг графа.
5. Рекластеризация
Описанный в разделе 4.2 алгоритм учета широковещательного характера передачи является приближенным. Следовательно, определение подмножеств (кластеров) вершин, составляющих шаги
маршрута, не является оптимальным, и после завершения работы алгоритма можно попытаться переместить некоторые вершины в другие кластеры, чтобы уменьшить общую стоимость передачи. В данном разделе предложены два алгоритма “рекластеризации”, основанные на замене путей и удалении
вершин.
• Среди всех путей (td) найти кратчайший
путь (t ∗ d ∗ ) и включить его в дерево.
• D0 = D0 \{d ∗ }.
• Каждой дуге ei j , такой что i ∈ (t ∗ d ∗ ), j ∈
/
T , припишем вес, равный разнице C(i, J ∪
{ j}) − C(i, J), где J = J(i) – множество прямых потомков вершины i на данном шаге
алгоритма в частично построенном дереве
T.
3. Завершение работы.
5.1. Алгоритм замены путей в дереве
• Если D0 = ∅ – конец алгоритма.
1. Инициализация (оценка дуг графа).
• В противном случае выполнить шаг 2.
• Каждой дуге ei j ∈ E припишем вес, равный
весу C(i, J = { j}) вершины i, который она
имела бы при передаче пакета единственному прямому потомку j (если у вершины
i нет прямых потомков в построенном дереве), или вес, равный разнице C(i, J ∪ { j}) −
C(i, J), где J = J(i) – множество прямых потомков вершины i на данном шаге алгоритма в частично построенном дереве T . Дугам, вошедшим в дерево T , присваивается
вес ∞. Здесь C(i, J) вычисляется в зависимости от метода передачи по формулам (2),
(4) или (6).
4.3. Численный анализ
Для сравнения исходной и модифицированной
версий алгоритма Takahashi и Matsuyama были поставлены серии экспериментов в сценариях, уже
описанных в разделе 3.4. Исследования показали,
что в случае модифицированного алгоритма применение адаптивного выбора метода передачи на каждом шаге оказывает слабое влияние на стоимость
маршрута, как и в случае исходного алгоритма, и,
вероятно, по той же причине (см. раздел 3.4). Поэтому ниже представлены результаты только для случая адаптивного выбора, результаты же для неадаптивного выбора в целях экономии места опущены.
На рис. 6 показаны результаты применения
модифицированной и немодифицированной версий
алгоритма Takahashi и Matsuyama. Пунктирными линиями показаны значения эффекта E ∗ a =
∗
∗
∗
100%(Cэт − min{CGR−U−a
,CGR−B−a
})/Cэт , где CGR−U−a
∗
и CGR−B−a – средние веса маршрутов RGR−U и
RGR−B , построенных модифицированным алгоритмом с адаптивным выбором метода передачи.
Сплошные кривые Ea показывают значения эффекта при использовании исходного алгоритма (как и
на рис. 5) также с адаптивным выбором метода передачи.
Модифицированный алгоритм улучшает значение эффекта в сетях с низкой плотностью сравнительно слабо. Прирост эффекта составляет 10 процентных пунктов только в случае большого числа получателей. При высокой же плотности такого
же увеличения эффекта можно ожидать в широком
2. Замена пути в дереве.
• По алгоритму Флойда [11] находим кратчайшие пути (td) и упорядочиваем их по
возрастанию весов.
• Просматриваем по очереди все пути (td) .
Если путь (td) имеет вес меньше, чем путь
(td) ∈ T в дереве, то делаем замену пути в
дереве на путь (td) , далее – на шаг 3.
3. Завершение работы.
• Если рассмотрены все пути (td) и не произведено ни одной замены, то – конец алгоритма.
• В противном случае выполнить шаг 1.
5.2. Алгоритм удаления вершин в дереве
1. Инициализация.
242
P=(0.3;0.6) r=r0
P=(0.01;0.3) r=r0
50
50
45
45
40
40
35
35
30
30
25
25
20
20
15
15
10
10
5
5
0
0
3
10
20
L1 E_a
L1 E*_a
40
L10 E_a
3
70
10
L1 E_a
L10 E*_a
20
L1 E*_a
40
L10 E_a
70
L10 E*_a
P=(0.3;0.6) r=r4
P=(0.01;0.3) r=r4
80
80
70
70
60
60
50
50
40
40
30
30
20
20
10
10
0
0
3
10
20
L1 E_a
L1 E*_a
40
L10 E_a
70
3
L10 E*_a
10
L1 E_a
20
L1 E*_a
40
L10 E_a
70
L10 E*_a
Рис. 6. Сравнение исходной и модифицированной версий алгоритма Takahashi и Matsuyama
P=(0.3;0.6) r=r0
P=(0.01;0.3) r=r0
60
50
45
50
40
35
40
30
25
30
20
20
15
10
10
5
0
0
3
10
20
L1 E_a
L1 E*_a
40
L10 E_a
3
70
10
L1 E_a
L10 E*_a
20
L1 E*_a
40
L10 E_a
70
L10 E*_a
P=(0.3;0.6) r=r4
P=(0.01;0.3) r=r4
90
90
80
80
70
70
60
60
50
50
40
40
30
30
20
20
10
10
0
0
3
10
L1 E_a
20
L1 E*_a
40
L10 E_a
3
70
L10 E*_a
10
L1 E_a
20
L1 E*_a
40
L10 E_a
70
L10 E*_a
Рис. 7. Эффект от применения рекластеризации в зависимости от числа получателей
непосредственного потомка, то заменяем v00
в V 00 ее непосредственным потомком).
• Каждой дуге ei j ∈ E припишем вес, равный
весу C(i, J = { j}) вершины i, который она
имела бы при передаче пакета единственному прямому потомку j (если у вершины i нет прямых потомков в частично построенном дереве), или вес, равный разнице C(i, J ∪ { j}) −C(i, J), где J = J(i) – множество прямых потомков вершины i на данном шаге алгоритма в частично построенном дереве T . Дугам, вошедшим в дерево
T , и дугам, исходящим из вершины v0 , при-
• Упорядочиваем вершины дерева (кроме s)
по возрастанию степеней вершин.
2. Удаление вершины в дереве T .
• Удаляем вершину v0 из дерева (начинаем
с вершины с наименьшей степенью). Дерево разбивется на два множества T = T1 ∪ T2 ,
где T1 – связное поддерево с корнем s, T2 –
оставшаяся часть дерева. Обозначим V 00 ⊆
T2 – множество вершин, которые ранее были непосредственными потомками вершины v0 (если вершина v00 ∈ V 00 не принадлежит множеству D и имеет только одного
243
сваивается вес ∞. Здесь C(i, J) вычисляется
в зависимости от метода передачи по формулам (2), (4) или (6).
Для оптимизации работы алгоритма, описанного
в разделе 4.2, т.е. для построения более дешевого маршрутного дерева, применяем последовательно алгоритм удаления вершин и алгоритм замены
путей до тех пор, пока это дает улучшение.
– можно достигнуть с помощью алгоритма, учитывающего широковещательную природу передачи. В
данной работе предложен пример такого алгоритма,
являющийся простой модификацией известного алгоритма Takahashi и Matsuyama.
В продолжении данной работы предполагается
разработать новые алгоритмы, учитывающие широковещательную природу передачи в беспроводной
среде, более совершенные в двух следующих аспектах. Во-первых, к ограничению на вероятность доставки пакета до конечного получателя будет добавлено ограничение на время доставки, чтобы лучше
учитывать требования к качеству обслуживания голосового трафика и видео-трафика реального времени. Во-вторых, будет снято предположение о равномерности распределения требований к надежности
по звеньям, составляющим маршрут, которое в данной работе присутствует в виде ограничения сверху
на долю теряемых пакетов величиной q, равной для
всех звеньев маршрута.
5.3. Численный анализ
Список литературы
• По алгоритму Флойда найти кратчайшие
пути (t1 v00 ), где t1 ∈ T1 , v00 ∈ V 00 , и включить
их в дерево.
3. Завершение работы.
• Если стоимость нового дерева меньше исходного, то принимаем новое дерево за T ,
иначе возвращаем вершину v0 в дерево.
• Если рассмотрены все вершины дерева –
конец алгоритма, иначе перейти на шаг 2.
Рис. 7 демонстрирует результаты, аналогичные
результатам в разделе 4.3, но полученные при использовании алгоритма с рекластеризацией для построения маршрута. Результаты позволяют сделать
вывод о том, что применение рекластеризации позволяет существенно (в 1,5–2 раза) повысить эффект
практически при любых значениях плотности размещения, вероятности неудачи и длины пакета.
Следует заметить, что предложенные алгоритмы рекластеризации довольно ресурсоемки и вряд
ли могут быть применены для динамической маршрутизации. Однако они полезны тем, что позволяют оценить потенциальный эффект, который может
быть достигнут алгоритмом многоадресной маршрутизации с учетом широковещательного характера
передачи, более совершенным, чем алгоритм, предложенный в разделе 4.2.
[1] EADS and Alcatel-Lucent, Interoperable Mission
Critical Broadband/Narrowband Solution for Public
Safety Communications In creating the Shared Wireless
Broadband Network, Strategic White Paper, 2011,
available at http://www.cassidiancommunications.
com/pdf/WhitePaper\_AL\_EADS.pdf
[2] IEEE Std 802.11-2007. IEEE Standard for Information
technology – Telecommunications and information
exchange between systems – Local and metropolitan
area networks – Specific requirements Part 11: Wireless
LAN Medium Access Control (MAC) and Physical
Layer (PHY) Specifications. – Revision of IEEE Std
802.11-1999. N.Y.: IEEE, 2007
[3] P. Winter, Steiner problem in networks: a survey,
Networks, Vol.17, pp.129–167, 1987
[4] Ian F. Akyildiz and XudongWang, Wireless Mesh
Networks, Wiley, 2009
[5] Cisco, Cisco Visual Networking Index: Global Mobile
Data Traffic Forecast Update, 2011–2016, White
Paper, 2012, available at http://www.cisco.com/
en/US/solutions/collateral/ns341/ns525/ns537/
ns705/ns827/white_paper_c11-520862.pdf
[6] Pedro M. Ruiz, Antonio F. Gomez-skarmeta,
Approximating optimal multicast trees in wireless
multihop networks, in Proc. 10th IEEE Symposium on
Computers and Communications (ISCC), pp 686-691,
2005
[7] H. Takahashi and A. Mastsuyama. An approximate
solution for the Steiner problem in graphs.
Math.Japonica, Vol. 24, pp.573–577, 1980
[8] IEEE Std 802.11s-2011. IEEE Standard for
Information technology – Telecommunications and
information exchange between systems – Local and
metropolitan area networks – Specific requirements
Part 11: Wireless LAN Medium Access Control (MAC)
and Physical Layer (PHY) specifications. Amendment
6. Заключение
Результаты, полученные в данной работе, позволяют сделать следующие выводы. Применение методов блочной передачи и безусловных повторных
передач на маршруте, построенном классическим
алгоритмом, который широковещательную природу
передачи в беспроводной среде не учитывает, позволяет снизить стоимость маршрута в зависимости от
доли узлов сети, являющихся получателями, и вероятности ошибки при передаче примерно на 10-45%
для пакетов, размер которых соответствует видео
трафику, и на 20-65% для пакетов, соответствующих
по размеру голосовому трафику. Однако существенно большего снижения стоимости – а именно, в разы
244
10: Mesh Networking, IEEE Computer Society, 2011
[9] IEEE Std 802.11aa-2012. IEEE Standard for
Information technology – Telecommunications and
information exchange between systems – Local and
metropolitan area networks – Specific requirements
Part 11: Wireless LAN Medium Access Control (MAC)
and Physical Layer (PHY) specifications. Amendment
2: MAC Enhancements for Robust Audio Video
Streaming, IEEE Computer Society, 2012
[10] Lyakhov A. Yakimov M. Analytical Study of QoS
Oriented Multicast in Wireless Networks EURASIP
Journal on Wireless Communications and Networking,
Vol.11, pp.1-13, 2011
[11] Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л.
Ривест, Клиффорд Штайн Алгоритмы: построение
и анализ / Introduction to Algorithms. 2-е изд. — М.:
Вильямс, 2006
245