Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях
Ключевые слова и синонимы
Раскраска графа, децентрализованные сети
Постановка задачи
Одной из важнейших проблем беспроводных сетей является снижение емкости из-за интерференции при нескольких одновременных передачах. В беспроводных ячеистых сетях наличие роутеров ячеистой мультирадиосети способно существенно снизить остроту этой проблемы. В мультирадиосетях вершины способны одновременно передавать и принимать сигнал либо передавать сигнал одновременно по нескольким каналам. Однако из-за ограниченного числа доступных каналов невозможно полностью устранить интерференцию; для снижения влияния интерференции необходимо аккуратное распределение каналов. Распределение каналов и маршрутизация взаимосвязаны, поскольку распределение влияет на пропускную способность линий связи и на то, в какой степени передачи по этим линиям подвержены помехам. Очевидно, что это влияет и на маршрутизацию, задача которой заключается в удовлетворении запросов на трафик. Точно так же маршрутизация трафика определяет его потоки по каждой линии, что определенно влияет на распределение каналов. Распределение должно выполняться таким образом, чтобы удовлетворялись требования к коммуникациям для каналов связи. Таким образом, задачу максимизации пропускной способности в беспроводных ячеистых сетей необходимо решать при помощи распределения каналов, маршрутизации и планирования.
Пусть дана беспроводная ячеистая магистральная сеть, моделируемая графом (V, E). Вершина [math]\displaystyle{ t \in V \; }[/math] представляет проводную сеть. Ребро e = (u, v) существует в E в том и только том случае, если u и v располагаются внутри диапазона связи [math]\displaystyle{ R_T \; }[/math]. Множество [math]\displaystyle{ V_G \subseteq V \; }[/math] представляет множество шлюзовых вершин. Система имеет K каналов в сумме. Каждая вершина [math]\displaystyle{ u \in V \; }[/math] имеет I(u) карт плат сетевых интерфейсов и суммарный спрос l(u) от связанных с ней пользователей. Для каждого ребра e обозначим за [math]\displaystyle{ I(e) \subset E \; }[/math] множество ребер, с которыми у него возникает интерференция. Пара вершин, которые используют один и тот же канал и находятся в диапазоне интерференции [math]\displaystyle{ R_Ix \; }[/math], могут создавать помехи друг для друга, даже если они не связываются напрямую. Пары вершин, использующие разные каналы, могут одновременно отправлять пакеты, не вызывая интерференции. Задача заключается в максимизации [math]\displaystyle{ \lambda \; }[/math], где по меньшей мере [math]\displaystyle{ \lambda l(u) \; }[/math] объема пропускной способности может быть направлено из каждый вершины u в Интернет (представленный вершиной t). Пропускную способность [math]\displaystyle{ \lambda l(u) \; }[/math] для каждой вершины u можно получить, вычислив (1) сетевой поток, ассоциирующий с каждым ребром e = (u, v) значения [math]\displaystyle{ f(e(i)), 1 \le i \le K \; }[/math], где f(e(i)) – интенсивность трафика от вершины u к вершине v по каналу i; (2) допустимое распределение каналов F(u) (F(u) представляет собой упорядоченное множество, в котором i-й интерфейс u работает на i-м канале в F(u)), такое, что для любых [math]\displaystyle{ f(e(i)) \gt 0, i \in F(u) \cap F(v) \; }[/math]; (3) допустимый график S, согласно которому множество пар «ребро-канал» (e, i) (где ребро e использует канал, т.е. f(e(i)) > 0 планируется на отрезок времени [math]\displaystyle{ \tau \; }[/math] для [math]\displaystyle{ \tau = 1, 2, ... , T \; }[/math], где T – период графика. График является допустимым, если никакие ребра из пар ребер [math]\displaystyle{ (e_1, i), (e_2, i) \; }[/math], спланированных на один отрезок времени на общий канал i, не интерферируют друг с другом: [math]\displaystyle{ e_1 \notin I(e_2), e_2 \notin I(e_1) \; }[/math]. В силу этого допустимый график также называют графиком с ребрами, свободными от интерференции. Мы будем использовать переменную-индикатор [math]\displaystyle{ X_{e, i, \tau}, e \in E, i \in F(e), \tau \ge 1 \; }[/math]. Ей присваивается значение 1 в том и только том случае, если линия связи e активна в отрезок времени [math]\displaystyle{ \tau \; }[/math] на канале i. Отметим, что [math]\displaystyle{ 1/T \sum_{1 \le \tau \le T} X_{e, i, \tau} c(e) = f(e(i)) \; }[/math]. Это верно в силу того, что коммуникация с интенсивностью c(e) выполняется в любой отрезок времени, в рамках которого линия связи e активна на канале i, и того, что f(e(i)) – средняя интенсивность, полученная для линии связи e для канала i. Из этого следует [math]\displaystyle{ 1/T \sum_{1 \le \tau \le T} X_{e, i, \tau} = \frac{f(e(i))}{c(e)} \; }[/math].
Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи
Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан объединенный алгоритм аппроксимации под названием RCL для маршрутизации, распределения каналов и планирования линий связи. Алгоритм выполняет следующие операции в приведенном порядке:
1. Решение LP-задачи. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения Я, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом.
2. Распределение каналов. На этом этапе алгоритм распределения каналов используется для регулировки потока управления в управляющем графе (изменения в маршрутизации), что позволяет гарантировать допустимое распределение каналов. Этап регулировки потока также стремится сохранить рост интерференции каждого канала на минимальном уровне.
3. Планирование линий связи в отсутствие интерференции. На этом этапе формируется план линий связи без возникновения интерференции для потоков по ребрам, соответствующих потоку управления в управляющем графе.
Каждый из этих этапов далее будет описан в соответствующем подразделе.
Алгоритм маршрутизации на базе линейного программирования
Линейная программа LP (1) для нахождения потока, максимизирующего значение [math]\displaystyle{ \lambda \; }[/math]:
[math]\displaystyle{ max \lambda \; }[/math] (1)
При условии [math]\displaystyle{ \lambda l(v) + \sum_{e = (u, v) \in E} \sum^k_{i = 1} f(e(i)) = \sum_{e = (v, u) \in E} \sum^k_{i = 1} f(e(i)), \; \forall v \in V - V_G }[/math] (2)
[math]\displaystyle{ f(e(i)) \le c(e), \; \forall e \in E }[/math] (3)
[math]\displaystyle{ \sum_{1 \le i \le K} \bigg( \sum_{e = (u, v) \in E} \frac{f(e(i))}{c(e)} + \sum_{e = (v, u) \in E} \frac{f(e(i))}{c(e)} \bigg) \le I(v), \; v \in V }[/math] (4)
[math]\displaystyle{ \frac{f(e(i))}{c(e)} + \sum_{e' \in I(e)} \frac{f(e'(i))}{c(e')} \le c(q), \; \forall e \in E, 1 \le i \le K. }[/math] (5)
Первые два ограничения представляют собой ограничения потока управления. Первое из них является ограничением сохранения потока; второе гарантирует, что пропускная способность линий связи не будет нарушаться. Третье ограничение касается радиостанций в вершинах. Вспомним, что вершина IWMN (беспроводной ячеистой мультирадиосети без интерференции?) [math]\displaystyle{ v \in V \; }[/math] имеет I(v) радиостанций и, следовательно, может попасть в распределение не более чем I(v) каналов, [math]\displaystyle{ 1 \le i \le K \; }[/math]. Один из способов моделирования этого ограничения основан на наблюдении, что в силу ограничений интерференции вершина v может быть вовлечена не более чем в I(v) одновременных коммуникаций (с разными соседями, доступными в результате одного перехода). Иными словами, это ограничение следует из неравенства [math]\displaystyle{ \sum_{1 \le i \le K} \sum_{e = (u, v) \in E} X_{e, i, \tau} + \sum_{1 \le i \le K} \sum_{e = (v, u) \in E} X_{e, i, \tau} \le I(v) }[/math]. Четвертое ограничение касается нагруженности линий связи, что будет более детально рассматриваться в разделе «Планирование потока управления линий связи». Отметим, что все перечисленные ограничения являются обязательными условиями для любого допустимого решения. Однако эти ограничения не всегда являются достаточными. Таким образом, если найденное решение удовлетворяет этим ограничениям, оно может не быть допустимым. Следует начать с «хорошего», но не обязательно допустимого решения, удовлетворяющего всем ограничениям, и использовать его для построения допустимого решения, не ухудшая его качества.
Решение этой задачи линейного программирования может рассматриваться как потоковый граф [math]\displaystyle{ H = (V, E^H) \; }[/math], где [math]\displaystyle{ E^H = \{ e(i) | \forall e \in E, 1 \le i \le K \} \; }[/math]. Хотя оптимальное решение этой задачи дает наилучшее возможное значение [math]\displaystyle{ \lambda \; }[/math] (скажем, [math]\displaystyle{ \lambda^* \; }[/math]), с практической точки зрения возможны дополнительные улучшения:
• Поток управления может содержать ориентированные циклы. Такой случай может иметь место, поскольку алгоритм линейного программирования не старается напрямую минимизировать объем интерференции. Удаляя поток из ориентированного цикла (равное количество от каждого ребра), можно обеспечить ограничение сохранения потока; кроме того, поскольку в результате становится меньше передач, снижается объем интерференции.
• Поток управления может использовать длинный путь, в то время как доступны более короткие. Отметим, что более длинные пути включают больше передач по линиям связи. В таком случае нередко возникает возможность снижения интерференции в системе за счет перераспределения потока на более короткие пути.
Вышеприведенное рассуждение предполагает, что было бы практичным среди всех решений, обеспечивающих оптимальное значение [math]\displaystyle{ \lambda \; }[/math] в виде [math]\displaystyle{ \lambda^* \; }[/math], найти такое, для которого общее значение следующей величины будет минимальным:
[math]\displaystyle{ \sum_{1 \le i \le K} \sum_{e = (v, u) \in E} \frac{f(e(i))}{c(e)}. }[/math]
Затем задача линейного программирования заново решается с использованием этой целевой функции и при фиксированном значении [math]\displaystyle{ \lambda \; }[/math], равном [math]\displaystyle{ \lambda^* \; }[/math].
Распределение каналов
Решение задачи линейного программирования (1) представляет собой набор значений потока f(e(i)) для ребра e и канала i, максимизирующих значение [math]\displaystyle{ \lambda \; }[/math]. Обозначим за [math]\displaystyle{ \lambda^* \; }[/math] оптимальное значение [math]\displaystyle{ \lambda \; }[/math]. Поток f(e(i)) подразумевает распределение каналов, при котором обе конечных точки ребра e назначены каналу i в том и только том случае, если f(e(i)) > 0. Заметим, что подразумеваемое распределение каналов для потока f(e(i)) может не быть допустимым (для него может потребоваться более I(v) каналов в вершине v). Алгоритм распределения каналов преобразует заданный поток таким образом, чтобы искоренить недостаток допустимости. Ниже приводится краткое описание алгоритма. Более детальное изложение можно найти в работе [1].
Вначале заметим, что в «холостом» сценарии, в котором все вершины v имеют одно и то же количество интерфейсов I (т.е. I = I(v)) и количество доступных каналов K также равно I, распределение каналов, найденное алгоритмом LP (1), является допустимым. Этот так, поскольку даже тривиальное распределение каналов, в котором всем вершинам назначаются все каналы от 1 до I, является допустимым. Основная идея алгоритма заключается в следующем. Вначале следует преобразовать решение LP (1) в новый поток, в котором каждое ребро e имеет поток f(e(i)) > 0 только для каналов [math]\displaystyle{ 1 \le i \le I \; }[/math]. Базовая операция, используемая алгоритмом, заключается в равномерном распределении для каждого ребра e потока f(e(i)), [math]\displaystyle{ I \le i \le K \; }[/math], на ребра [math]\displaystyle{ e(j), 1 \le i \le I \; }[/math]. Это гарантирует, что после завершения операции все [math]\displaystyle{ f(e(i)) = 0, I \le i \le K \; }[/math]. Данная операция будет называться первым этапом алгоритма. На первом этапе не нарушаются ограничения сохранения потока управления и ограничения на радиостанции в вершинах (5) из алгоритма LP (1). Можно показать, что в полученном решении поток f(e(i)) может превышать пропускную способность ребра e не более чем на коэффициент [math]\displaystyle{ \phi = K/I \; }[/math]. Он называется «коэффициентом инфляции» первого этапа. Аналогичным образом ограничение нагруженности линий связи (5) у нового потока также может нарушаться для ребра e и канала i на величину, не превышающую коэффициент инфляции. Иными словами, в полученном потоке выполняется соотношение [math]\displaystyle{ \frac{f(e(i))}{c(e)} + \sum_{e' \in I(e)} \frac{f(e'(i))}{c(e')} \le \phi c(q). }[/math]
Из этого следует, что если новый поток отличается в [math]\displaystyle{ 1 / \phi \; }[/math] раз, то он является допустимым для LP (1). Отметим, что подразумеваемое распределение каналов (назначение каждой вершине каналов от 1 до I) также является допустимым. Таким образом, вышеприведенный алгоритм находит допустимое распределение каналов со значением [math]\displaystyle{ \lambda \; }[/math] не менее [math]\displaystyle{ \lambda^* / \phi \; }[/math].
Одним из недостатков описанного алгоритма распределения каналов (этапа 1) является то, что он использует только I из K доступных каналов. При использовании большего количества каналов возникает возможность дополнительного снижения интерференции, что позволяет передавать через систему поток большего объема. Алгоритм распределения каналов использует для этого дополнительную эвристику. Назовем ее вторым первым этапом алгоритма.
Теперь определим операцию под названием «операция переключения каналов». Пусть A – максимальная связная компонента (вершины из A не связаны с вершинами вне A) в графе, образованная ребрами e для заданного канала i, для которого f(e(i)) > 0. Можно заметить, что для заданного канала j операция полного переноса потока f(e(i)) в поток f(e(j)) для каждого ребра e из A не влияет на допустимость подразумеваемого распределения каналов. Это верно в силу того, что после преобразования потока не увеличивается количество каналов, назначенных одной вершине: конечные вершины ребер e в A, которые ранее были назначены каналу i, теперь назначены каналу j. Таким образом, это преобразование эквивалентно переключению распределения каналов в вершинах из A таким образом, словно канал i отбрасывается, а канал j добавляется, если он еще не был назначен.
Эвристика на втором этапе пытается заново преобразовать немасштабированные потоки f(e(i)) из первого этапа таким образом, что в графах G(e, i) будут иметься множественные связные компоненты, образованные ребрами e для каждого канала [math]\displaystyle{ 1 \le i \le I \; }[/math]. Это повторное преобразование выполняется таким образом, чтобы удовлетворялись ограничения линейного программирования с коэффициентом инфляции, не превышающим [math]\displaystyle{ \phi \; }[/math], как в случае немасштабированного потока после заверения первого этапа алгоритма.
Затем, на третьем этапе работы алгоритма, связные компоненты каждого графа G(e, i) группируются таким образом, чтобы получилось количество групп, максимально близкое к K (но не превышающее его), и чтобы максимальная интерференция внутри каждой группы были минимизирована. Затем вершины в l-й группе назначаются каналу l при помощи операции переключения канала для выполнения соответствующего преобразования потока. Можно показать, что распределение каналов, подразумеваемое потоком на третьем этапе алгоритма, является допустимым. Кроме того, потоки f(e(i)) удовлетворяют ограничениям LP (1) с коэффициентом инфляции, не превышающим [math]\displaystyle{ \phi = K/I \; }[/math].
После этого алгоритм масштабирует поток при помощи максимального возможного коэффициента (не менее [math]\displaystyle{ l / \phi \; }[/math]) таким образом, чтобы полученный поток представлял собой допустимое решение задачи линейного программирования LP (1) и подразумевал допустимое решение задачи распределения каналов. Таким образом, полный алгоритм находит допустимое распределение каналов (за счет того, что не ограничивается каналами с 1 до I) со значением [math]\displaystyle{ \lambda \; }[/math] не менее [math]\displaystyle{ \lambda^* / \phi \; }[/math].
Планирование потока управления линий связи
Результаты данного раздела получены путем расширения результатов работы [4] для случая с единственным каналом и для модели протокола интерференции [2]. Вспомним, что план S с разбиением на отрезки времени предполагается периодическим (с периодом T), где переменная-индикатор [math]\displaystyle{ X_{e, i, \tau}, e \in E, i \in F(e), \tau \ge 1 \; }[/math] равна 1 в том и только том случае, если линия связи e активна во временном отрезке [math]\displaystyle{ \tau \; }[/math] на канале i, а i – общий канал между множеством каналов, присвоенных конечным вершинам ребра e.
Если непосредственно применить результат (утверждение 2) из [ ], получим, что обязательное условие для планирования линий связи в отсутствие интерференции заключается в том, что для любых [math]\displaystyle{ e \in E, i \in F(e), \tau \ge 1: X_{e, i, \tau} + \sum_{e' \in I(e)} X_{e', i, \tau} \le c(q) \; }[/math]. Здесь c(q) – константа, которая зависит только от модели интерференции. В модели интерференции эта константа является функцией от фиксированного значения q – отношения диапазона интерференции [math]\displaystyle{ R_I \; }[/math] к диапазону передачи [math]\displaystyle{ R_T \; }[/math]; интуитивные соображения по ее выводу для конкретного значения q = 2 приведены ниже.
Лемма 1. c(q) = 8 для q = 2.
Доказательство. Вспомним, что ребро [math]\displaystyle{ e' \in I(e) \; }[/math], если существуют две вершины [math]\displaystyle{ x, y \in V \; }[/math], которые находятся не более чем на расстоянии [math]\displaystyle{ 2R_T \; }[/math] друг от друга, такие, что ребро e инцидентно вершине x, а ребро e' инцидентно вершине y. Пусть e = (u, v). Заметим, что u и v находятся не более чем на расстоянии [math]\displaystyle{ R_T \; }[/math] друг от друга. Рассмотрим область C, образованную объединением двух кругов [math]\displaystyle{ C_u \; }[/math] и [math]\displaystyle{ C_v \; }[/math] радиусом [math]\displaystyle{ 2R_T \; }[/math] каждый, с центрами в вершинах u и v, соответственно. Тогда [math]\displaystyle{ e' = (u', v') \in I(e) \; }[/math] в том и только том случае, если по меньшей мере одна из вершин u', v' находится в C. Обозначим такую вершину как C(e'). Пусть даны два ребра [math]\displaystyle{ e_1, e_2 \in I(e) \; }[/math], не интерферирующие друг с другом – это означает, что вершины [math]\displaystyle{ C(e_1) \; }[/math] и [math]\displaystyle{ C(e_2) \; }[/math] находятся на расстоянии не менее [math]\displaystyle{ 2R_T \; }[/math] друг от друга. Таким образом, верхнюю границу количества ребер множества I(e), не интерферирующих попарно друг с другом, можно получить при помощи вычисления числа вершин, которые могут быть помещены в множество C, находящихся попарно на расстоянии не менее [math]\displaystyle{ 2R_T \; }[/math] друг от друга. Можно показать [1], что это количество не превышает 8. Таким образом, в плане S в заданном отрезке времени существует только одна из двух возможностей: либо в план входит ребро e, либо «независимое» множество ребер из I(e) размером не более 8, что вытекает из заявленной границы.
Необходимое условие (ограничение нагруженности линий связи). Вспомним, что [math]\displaystyle{ \frac{1}{T} \sum_{1 \le \tau \le T} X_{e, i, \tau} = \frac{f(e(i))}{c(e)} }[/math]. Таким образом, любое допустимое ребро, «свободное от интерференции», должно удовлетворять ограничению нагруженности для каждой линии связи e и каждого канала i:
[math]\displaystyle{ \frac{f(e(i))}{c(e)} + \sum_{e' \in I(e)} \frac{f(e'(i))}{c(e')} \le c(q) }[/math]. (6)
Также было установлено соответствующее достаточное условие [1].
Достаточное условие (ограничение нагруженности линий связи). Если для каждой линии связи e и каждого канала i поток по ребру удовлетворяет следующему ограничению планируемости линий связи, то можно составить график коммуникации с ребрами, свободными от интерференции, при помощи алгоритма, предложенного в [1].
[math]\displaystyle{ \frac{f(e(i))}{c(e)} + \sum_{e' \in I(e)} \frac{f(e'(i))}{c(e')} \le 1 }[/math]. (7)
Из вышеприведенного соотношения следует, что если поток f(e(i)) удовлетворяет ограничению нагруженности линий связи, то в результате масштабирования потока с коэффициентом 1/c(q) его можно спланировать свободным от интерференции.
Основные результаты
Теорема. Алгоритм RCL представляет собой алгоритм Kc(q)/I-аппроксимации для маршрутизации и распределения каналов в задаче планирования ребер в отсутствие интерференции.
Доказательство. Заметим, что поток f(e(i)), возвращаемый алгоритмом распределения каналов в разделе «Распределение каналов», удовлетворяет ограничению нагруженности линий связи. Таким образом, из результата, полученного в разделе «Планирование потока управления линий связи», следует, что в результате масштабирования потока с дополнительным коэффициентом 1/c(q) можно сформировать его план, свободный от интерференции. В результате получаем допустимое решение объединенной задачи маршрутизации, распределения каналов и планирования со значением [math]\displaystyle{ \lambda \; }[/math], равным по меньшей мере [math]\displaystyle{ \lambda^* / \phi c(q) \; }[/math]. Таким образом, алгоритм RCL представляет собой алгоритм [math]\displaystyle{ \phi c(q) = Kc(q)/I \; }[/math] -аппроксимации. □
Применение
Ячеистые сети инфраструктуры получают все большее распространение – как для коммерческого использования, так и для правоохранительной деятельности. Подобный контекст использования налагает строгие ограничения на эффективность лежащих в их основе беспроводных ячеистых мультирадиосетей без интерференции (IWMN). Гарантированная ширина пропускной способности является одним из важнейших требований при работе в подобных условиях. В таких IWMN изменение топологии происходит нечасто, а вариабельность объединенного запроса на трафик от каждого роутера ячеистой сети (точки агрегации клиентского трафика) невысока. Эти характеристики допускают периодическую оптимизацию сети, которая может выполняться управляющим системой программным обеспечением на основе оценки потребности в трафике. Данная работа может быть напрямую применена к сетям типа IWMN. Кроме того, она может использоваться в качестве эталонной для сравнения с эвристическими алгоритмами в многоскачковых беспроводных сетях.
Открытые вопросы
В дальнейшем было бы любопытно исследовать задачу, в которой решения для маршрутизации могут быть дополнены изменением весов линий связи при помощи протокола распределенной маршрутизации – такого как OSPF. Также интересно узнать, нельзя ли улучшить границу для наихудшего случая (например, получить константный коэффициент, независимый от KandI)?
См. также
Литература
1. Alicherry, M., Bhatia, R., Li, L.E.: Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In: Proc. ACM MOBICOM 2005, pp. 58-72
2. Gupta, P., Kumar, P.R.: The Capacity of Wireless Networks. IEEE Trans. Inf. Theory, IT-46(2), 388-404 (2000)
3. Jain, K., Padhye, J., Padmanabhan, V.N., Qiu, L.: Impact of interference on multi-hop wireless network performance. In: Proc. ACM MOBICOM 2003, pp. 66-80
4. Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: Algorithmic aspects of capacity in wireless networks. In: Proc. ACM SIGMETRICS 2005, pp. 133-144
5. Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: End-to-end packet-scheduling in wireless ad-hoc networks. In: Proc. ACM-SIAM symposium on Discrete algorithms 2004, pp. 1021-1030
6. Kyasanur, P., Vaidya, N.: Capacity of multi-channel wireless networks: Impact of number of channels and interfaces. In: Proc. ACM MOBICOM, pp. 43-57. 2005