Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях
Ключевые слова и синонимы
Раскраска графа, децентрализованные сети
Постановка задачи
Одной из важнейших проблем беспроводных сетей является снижение емкости из-за интерференции при нескольких одновременных передачах. В беспроводных ячеистых сетях наличие роутеров ячеистой мультирадиосети способно существенно снизить остроту этой проблемы. В мультирадиосетях вершины способны одновременно передавать и принимать сигнал либо передавать сигнал одновременно по нескольким каналам. Однако из-за ограниченного числа доступных каналов невозможно полностью устранить интерференцию; для снижения влияния интерференции необходимо аккуратное распределение каналов. Распределение каналов и маршрутизация взаимосвязаны, поскольку распределение влияет на пропускную способность линий связи и на то, в какой степени передачи по этим линиям подвержены помехам. Очевидно, что это влияет и на маршрутизацию, задача которой заключается в удовлетворении запросов на трафик. Точно так же маршрутизация трафика определяет его потоки по каждой линии, что определенно влияет на распределение каналов. Распределение должно выполняться таким образом, чтобы удовлетворялись требования к коммуникациям для каналов связи. Таким образом, задачу максимизации пропускной способности в беспроводных ячеистых сетей необходимо решать при помощи распределения каналов, маршрутизации и планирования.
Пусть дана беспроводная ячеистая магистральная сеть, моделируемая графом (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]
Из этого следует, что если новый поток отличается в 1/ф раз, то он является допустимым для LP (1). Отметим, что подразумеваемое распределение каналов (назначение каждой вершине каналов от 1 до I) также является допустимым. Таким образом, вышеприведенный алгоритм находит допустимое распределение каналов со значением Я не менее Х*/ф.
Одним из недостатков описанного алгоритма распределения каналов (этапа 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 для каждого канала 1 < i: < I. Это повторное преобразование выполняется таким образом, чтобы удовлетворялись ограничения линейного программирования с коэффициентом инфляции, не превышающим ', как в случае немасштабированного потока после заверения первого этапа алгоритма.
Затем, на третьем этапе работы алгоритма, связные компоненты каждого графа G(e, i) группируются таким образом, чтобы получилось количество групп, максимально близкое к K (но не превышающее его), и чтобы максимальная интерференция внутри каждой группы были минимизирована. Затем вершины в l-й группе назначаются каналу l при помощи операции переключения канала для выполнения соответствующего преобразования потока. Можно показать, что распределение каналов, подразумеваемое потоком на третьем этапе алгоритма, является допустимым. Кроме того, потоки f(e(i)) удовлетворяют ограничениям LP (1) с коэффициентом инфляции, не превышающим ф = K/I.
После этого алгоритм масштабирует поток с учетом максимального возможного фрагмента (не менее l/ф) таким образом, чтобы полученный поток представлял собой допустимое решение задачи линейного программирования LP (1) и подразумевал допустимое решение задачи распределения каналов. Таким образом, полный алгоритм находит допустимое распределение каналов (за счет того, что не ограничивается каналами с 1 до I) со значением Я не менее Х*/ф.