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

Одним из преимуществ беспроводной децентрализованной сети является ее многовариантное свойство передачи данных: узлы связи (УС) могут пересылать пакеты от источника к месту назначения на базе маршрута hop-by-hop. Тем не менее релейная трансляция может снизить пропускную способность (ПС) сети, так как УС конкурируют за ПС не только с другими передатчиками на ближайших маршрутах, но и с УС, участвующими в релейной трансляции на этом же пути. ПС децентрализованной сети может быть поразительно низкой из-за такой конкуренции внутри и между потоками [1].

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

В данной статье приводятся основные положения для метода маршрутизации BAR, который учитывает узкие места и принимает во внимание текущую пропускную способность УС, а также местоположение узлов с узкими местами, чтобы повысить их ПС в разнородной децентрализованной сети. Данный метод основан на примере маршрутизации [2], которая включает ПС УС, чтобы повысить ПС беспроводных децентрализованных сетей.

Модель пропускной способности

Для примера возьмем разнородную сеть с тремя различными типами узлов связи (основным, агрегирующим и граничным). Основные УС отличаются наименьшей способностью передачи данных в диапазонах с малой шириной полосы пропускания — от 100 кбит/с до 1 Мбит/с (например, сенсорные УС в беспроводных сенсорных сетях). У агрегирующих узлов средняя способность передачи данных. Эти узлы связи отвечают за объединение трафика нескольких узлов с низкой ПС и отличаются средней шириной полосы 1–2 Мбит/с (например кластеры). Граничные УС отличаются высокой ПС при передаче данных с высокой шириной полосы 2–4 Мбит/с. Эти УС могут действовать с применением передовых технологий (например с направленными антеннами), которые отправляют трафик по магистрали непосредственно в высокоскоростные инфраструктуры. ПС УС определяется по его типу. ПС сети можно повысить, оптимизируя использование сетевой иерархии децентрализованных сетей [3].

Рис. 1. Пример трафика, идущего по сети

Введем понятие виртуальной ПС УС, так как ПС распределяется в линии связи в зависимости от конкретного вида маршрутизации. Это часть необработанной ПС УС, которая определяется по уровню межканальных помех (уровню перегрузки УС, который определяется предъявляемыми к сети требованиями по пропускной способности). Допустим, что используется справедливое планирование TDMA, в силу которого каждой линии связи, которая конкурирует за этот же канал, можно назначить свой слот времени при равной длине. Данный сценарий подразумевает, что канал должен делить ширину полосы не только с маршрутами, проходящими через интересующий нас УС, но также с маршрутами, проходящими через узлы, создающие помехи для интересующего нас УС. Следовательно, виртуальная ПС УС N0 — это необработанная ПС канала, деленная на уровень перегрузки в зависимости от задачи маршрутизации. Например, на рис. 1 показано, что виртуальная пропускная способность УС N0 равна C/8, так как через узел N0 проходят восемь линий связи и необработанная ПС равномерно делится на все передачи, как показано на рис. 2.

Рис. 2. Использование пропускной способности в N0, включая помехи линии связи

Маршрутизация на основе пропускной способности

В разнородных сетях УС имеют разную скорость отправки, мощность передачи и настройки антенны. Эти факторы приводят к различной ПС в каждом направлении на линии связи. Традиционные произвольные методы маршрутизации, такие как маршрутизация по кратчайшему пути, не могут принять во внимание разную мощность линий связи. В результате линии связи с повышенной ПС могут остаться неиспользованными, а линии связи с низкой ПС могут оборваться из-за перегрузки. Для децентрализованной сети крайне важно отправлять больше трафика по линиям связи с повышенной ПС, чтобы распределить нагрузку равномерно. На рис. 3 показан пример, где более длинный маршрут с большим количеством транзитных участков может оказаться лучше в силу предпочтительной ПС линии связи на данном маршруте.

Рис. 3. Маршрутизация A–D (показанный пунктиром маршрут предпочтителен в силу особенностей ПС линии связи на данном маршруте)

Желательно перенаправить трафик, проходящий через УС с низкой ПС, в узлы с повышенной способностью передачи. Так как ПС для данного метода в основном определяется по активному взаимодействию трафика (при помехах внутри и между потоками), маршрутизация на основе ПС (CBR) может перенаправить поступающий трафик в неперегруженную зону, чтобы вся сеть стала более гибкой. Обратимся к методу CBR. Вес линии связи в нем определяется [2] следующим образом:

w_ij= 1/C_vj,∀i, j∈V,                     (1)

где wij — значение веса линии связи от УС i до УС j, а C_vjобозначает виртуальную пропускную способность УС j.

Виртуальная ПС УС j определяется по максимальной ПС УС B_j[Мбит/с] (в таблице приведен тип каждого УС), деленной на уровень перегрузки CL_j, который испытывает данный УС:

C_{v_j}= _Bj/CL_j.                           (2)

С помощью алгоритма Дейкстра CBR-метод предпочитает выбрать узлы повышенной мощности, где маршруты устанавливаются на основе максимизации аккумулированного воздействия сквозной пропускной способности.

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

Маршрутизация с учетом узких мест

Поскольку узкие места ограничивают сквозную ПС, при выборе маршрута мы должны принимать во внимание влияние труднопроходимых узлов. Существуют другие методы маршрутизации, созданные для повышения ПС, распределения нагрузки и проблем с точками доступа: CBR [2], DLAR [4] и HMP [5]. Метод маршрутизации на основе ПС, созданный Лиу [2], стремится повысить ПС сети, выбирая линии связи с более высокой ПС сети в целом, не принимая во внимание воздействие на сеть отдельных труднопроходимых линий связи. Ли и Джерла продемонстрировали алгоритм маршрутизации с учетом динамичной нагрузки (Dynamic Load-Aware Routing, DLAR) [4], главным критерием отбора у которого является интенсивность трафика промежуточных УС. DLAR концентрируется на выборе маршрутов с наименьшим количеством промежуточных УС с пакетами, буферизированными выше порогового значения. Данная схема пренебрегает межпотоковыми помехами, так как на практике трафик, направляемый через соседние УС, тоже может повысить загруженность узких мест. Ли и Кэмпбелл представили протокол снижающий количество «горячих точек» (Hotspot Mitigation Protocol, HMP) [5], где «горячие точки» — временно возникающие, но сильно перегруженные области беспроводных децентрализованных сетей. Данное решение основано на снижении общей загруженности таких областей, но не принимает во внимание отдельные узкие места. Насколько известно, на данный момент не существует ни комплексных исследований, ни хороших решений по методам маршрутизации для сценариев с большим количеством типов и возможностей УС (например, узлов с низкой, средней и высокой ПС), которые также оптимизируют сквозную ПС, принимая во внимание перегрузку отдельно взятых областей.

Рассмотрим проектирование метода маршрутизации BAR. Маршрутизация с учетом узких мест, как и метод CBR, выбирает УС с максимальным значением ПС на путях передачи с большим количеством узлов, но также обходит узкие места. В BAR вес линии связи определяется следующим образом:

где BN — набор сквозных труднопроходимых узлов каждого потока трафика и УС, находящихся внутри диапазона помех этих сквозных труднопроходимых узлов, а d — значение взыскания.

Если УС не является одним из узких мест сети или источником помех, вес остается как при CBR. Если же УС является одним из узких мест или источником помех для них, вес повышается на d в качестве взыскания. Мы предполагаем, что источник помех УС может получать информацию от перегруженного узла. Обсуждение способов воплощения данного алгоритма находится за рамками данной статьи. Метод маршрутизации с учетом узких мест является одновременно монотонным, так как все весовые значения положительны, и изотонным, так как последующий выбор пути не влияет на весовое значение предыдущего, поскольку текущий путь рассчитывается и выбирается на основе весового значения каждой линии связи из предыдущего события.

Для данного сценария выбрано значение взыскания 7, так как это среднее число УС в пределах одного транзитного участка. Между значениями взыскания существует обратная зависимость. Если значение слишком маленькое, маршрут может не полностью избежать его прохождение через перегруженные области; при слишком большом значении оно может вызвать существенную релейную трансляцию, потенциально ухудшающую в будущем запросы на трафик.

Сеть и модель трафика

Предложенный нами метод маршрутизации будет изучен в среде сети c сеткой 10×10. В данной сети три различных типа узлов связи: узлы-ориентиры, агрегирующие и базисные узлы. Ключевые параметры приведены в таблице.

УС с наименьшим количеством потенциальных подключенных линий связей расположены в углах, где у них только по два соседних узла, а у УС в середине максимальное количество соседей — четыре. Предположим, что маршруты устанавливаются окончательно и впоследствии не меняются. Данное расположение удобно, так как УС могут ощущать состояние сети и решать проблемы отклонения от маршрута [6].

Средние поступление и продолжительность каждого маршрута подключения следуют закону распределения Пуассона [7]. Трафик поступает у левого края сетки сети и пересылается на правый край. Из серединных УС трафик не поступает. Источники и места назначения выбираются на каждом крае сети, так как наша задача — проанализировать характеристики каждого метода маршрутизации во всей сети при многоразовой передаче от узла к узлу релейной трансляции. Агрегирующие узлы выбираются случайным образом из числа серединных. В предлагаемой модели после установления маршрута подключения он остается в сети, пока не закончено моделирование, поступление и продолжительность потоков трафика имеют отрицательное экспоненциальное распределение. Поток поступает на каждый источник 10 раз за период моделирования. Методы маршрутизации изучаются на основе события. Событие происходит, когда сквозной поток трафика в сети включается (ON) или деактивируется (OFF). Максимальное число одновременно протекающих маршрутов — 10.

Оценка производительности

Рассмотрим эффективность различных механизмов маршрутизации: кратчайший путь по транзитным участкам (SH), маршрутизация на основе пропускной способности (CBR) и маршрутизация на основе узких мест (BAR). Сначала мы предлагаем пример выборочного сценария, чтобы показать улучшение сквозной ПС в узких местах с помощью BAR по сравнению с SH (рис. 4 и 5). Рис. 6 иллюстрирует CDF сквозной ПС в узких местах с различными методами маршрутизации при средней интенсивности трафика в три потока. Сравнительная производительность сквозной ПС в узких местах с различной интенсивностью трафика показана на рис. 7.

Рис. 4. Моментный уровень перегрузки УС при использовании метода кратчайшего пути маршрутизации

Рис. 5. Моментный уровень перегрузки УС при использовании BAR

На рис. 4 и 5 показан средний уровень перегруженности каждого УС для методов маршрутизации SH и BAR соответственно:

• Кружок обозначает уровень перегрузки УС; чем больше кружок, тем больше перегрузка.
• Темные линии показывают одновременно протекающие в сети потоки трафика.
• Точки в середине символизируют сквозные труднопроходимые УС по пропускной способности и размещению трафика.
• Крестик обозначает агрегирующий узел.

На рис. 4 метод SH показывает, что, как и ожидалось, УС в середине достаточно перегружены из-за моделей трафика, генерируемых в сети слева направо, при том что метод SH выбирает только пути с минимальным количеством транзитных участков. Этот случай является худшим для распределения нагрузки: УС в середине сети становятся узкими местами, а на периферии ПС растрачивается впустую.

С другой стороны, метод BAR находит путь, направляя трафик через УС с самой высокой ПС и, что более важно, обходя узкие места линии связи. Это повышает распределение нагрузки, как видно на рис. 5, где общее количество и уровень узких мест снижены с применением метода маршрутизации BAR по сравнению с SH. Согласно данному методу, ПС принимает во внимание помехи внутри и между потоками. Метод BAR максимизирует вероятность повышения ПС сети, разрешая одновременные передачи. Потоки распределяются от середины к краям сети.

Рис. 6. CDF долговременной сквозной пропускной способности в узких местах с различными методами маршрутизации

Ранее уже обсуждалось, как ПС труднопроходимых узлов связи может поставить под угрозу производительность не только отдельного потока трафика, но и ПС всей децентрализованной сети. Очень важно попытаться снизить количество узких мест и повысить ПС. Рис. 6 показывает преимущество уменьшения использования узких мест с помощью метода маршрутизации BAR. Горизонтальная пунктирная линия на данном рисунке обозначает 90%-ный уровень. Из-за функции учета узких мест 90% труднопроходимых УС имеют значение виртуальной ПС около 110 кбит/с (точка на оси x, в которой вертикальная линия пересекает кривую BAR на 90-й перцентили), около 75 кбит/с (точка на оси x, в которой вертикальная линия пересекает кривую CBR на 90-й перцентили) и около 63 кбит/с (точка на оси x, в которой вертикальная линия пересекает кривую SH на 90-й перцентили) при использовании BAR, CBR и SH соответственно. На этой перцентили BAR показывает значительный рост ПС узких мест — на 31,8 и 42,7% более высокий, чем SH и CBR соответственно.

Рис. 7. Суммирование сквозной ПС в узких местах относительно интенсивности трафика

На рис. 7 показана сумма ПС узких мест на каждом активном маршруте при различной интенсивности трафика соответственно. Минимальная ПС узла/линии связи на пути рассматривается только до узкого места, а на любом маршруте оно только одно. Причина использовать как метод общую ПС узких мест вместо среднего значения состоит в том, что в узком месте сети ПС минимальна. ПС узких мест зависит от топологии сети, ПС УС, модели трафика и метода маршрутизации. Хотя методы маршрутизации различны, другие условия полностью одинаковы при применении различных методов маршрутизации. На рис. 7 видно, что ПС узкого места определяется только применением метода маршрутизации, что делает невозможным значительное различие между методами, если использовалась средняя ПС. Общее значение показывает максимальную вариацию ПС в узких местах при различных методах маршрутизации.

При небольшом уровне интенсивности трафика ПС сети достаточно для релейной трансляции трафика. Следовательно, BAR может обходить труднопроходимые УС с помощью дополнительных транзитных участков или релейной трансляции без снижения ПС сети. К примеру (рис. 7), BAR повышает ПС узких мест всей сети на 60 и 14% при средней интенсивности трафика и четырех потоках по сравнению с SH и CBR соответственно. При такой интенсивности трафика метод BAR может эффективно разделять узлы линии связи на различные классы. Тем не менее при высокой интенсивности трафика применение CBR и особенно BAR снизит ПС сети, поскольку их функция маршрутизации старается избежать перегруженных районов, которые могут вызывать лишнюю нагрузку на сеть в виде релейной трансляции. Более того, дополнительная релейная трансляция отнимает ПС канала не только у проходящего трафика, но и у других узлов линейной трансляции [8]. Эта конкуренция за ПС канала вызывает большее количество труднопроходимых мест и сниженную проходимость сети.

Выводы

Рассмотрена новая структура метода BAR, которая позволяет повысить сквозную ПС в узких местах в сетях с относительно низкой нагрузкой. Кроме того, обсуждались ограничения ПС маршрутизации методами CBR и BAR. Метод BAR считается более «умным», чем определение кратчайшего пути по транзитным участкам (SH) и маршрутизация на основе помех/затруднений (Difficulties/Interference Routing, DIR), так как он учитывает индивидуальную ПС отдельных узлов/линий связи. Метод BAR принимает во внимание не только помехи отдельных УС и ПС, как метод CBR, но и учитывает размещение труднопроходимых УС, чтобы маршрут можно было выбирать более эффективно на основании УС с высокой ПС, чтобы пересылать пакеты через них и одновременно обходить труднопроходимые УС. По результатам испытаний с низкой нагрузкой BAR может существенно повысить сквозную ПС в узких местах по сравнению с SH и CBR.