Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях
Ключевые слова и синонимы
Раскраска графа, децентрализованные сети
Постановка задачи
Одной из важнейших проблем беспроводных сетей является снижение емкости из-за интерференции при нескольких одновременных передачах. В беспроводных ячеистых сетях наличие роутеров ячеистой мультирадиосети способно существенно снизить остроту этой проблемы. В мультирадиосетях вершины способны одновременно передавать и принимать сигнал либо передавать сигнал одновременно по нескольким каналам. Однако из-за ограниченного числа доступных каналов невозможно полностью устранить интерференцию; для снижения влияния интерференции необходимо аккуратное распределение каналов. Распределение каналов и маршрутизация взаимосвязаны, поскольку распределение влияет на пропускную способность линий связи и на то, в какой степени передачи по этим линиям подвержены помехам. Очевидно, что это влияет и на маршрутизацию, задача которой заключается в удовлетворении запросов на трафик. Точно так же маршрутизация трафика определяет его потоки по каждой линии, что определенно влияет на распределение каналов. Распределение должно выполняться таким образом, чтобы удовлетворялись требования к коммуникациям для каналов связи. Таким образом, задачу максимизации пропускной способности в беспроводных ячеистых сетей необходимо решать при помощи распределения каналов, маршрутизации и планирования.
Пусть дана беспроводная ячеистая магистральная сеть, моделируемая графом (V, E). Вершина t 2 V представляет проводную сеть. Ребро e = (u, v) существует в E в том и только том случае, если u и v располагаются внутри диапазона связи RT. Множество VG С V представляет множество шлюзовых вершин. Система имеет K каналов в сумме. Каждая вершина u 2 V имеет I(u) карт плат сетевых интерфейсов и суммарный спрос l(u) от связанных с ней пользователей. Для каждого ребра e обозначим за I(e) С E множество ребер, с которым у него возникает интерференция. Пара вершин, которые используют один и тот же канал и находятся в диапазоне интерференции RIx, могут создавать помехи друг для друга, даже если они не связываются напрямую. Пары вершин, использующие разные каналы, могут одновременно отправлять пакеты, не вызывая интерференции. Задача заключается в максимизации Я, где по меньшей мере Xl{u) объема пропускной способности может быть направлено из каждый вершины u в Интернет (представленный вершиной t). Пропускную способность Яl (u) для каждой вершины u можно получить, вычислив (1) сетевой поток, ассоциирующий с каждым ребром e = (u, v) значения f(e(i)), 1 < i < K, где f(e(i)) – интенсивность трафика от вершины u к вершине v по каналу i; (2) осуществимое распределение каналов F(u) (F(u) представляет собой упорядоченное множество, в котором i-й интерфейс u работает на i-м канале в F(u)), такое, что в случае f(e(i)) > 0, i 2 F(u) \ F(v); (3) осуществимый график S, согласно которому множество пар «ребро-канал» (e, i) (где ребро e использует канал, т.е. f(e(i)) > 0 планируется на отрезок времени т для т = 1, 2, ... , T, где T – период графика. График является осуществимым, если никакие ребра из пар ребер (e1, i), (e2, i), спланированных на один отрезок времени на общий канал i, не интерферируют друг с другом (e1 ^ I(e2) и e2 $- I(e1)). В силу этого осуществимый график также называют графиком с ребрами, свободными от интерференции. Мы будем использовать переменную-индикатор XC;,;T, e 2 E; i 2 F(e), r > 1. Ей присваивается значение 1 в том и только том случае, если линия связи e активна в отрезок времени т на канале i. Отметим, что l/rj]1<T<rIe,iltc(e) = f(e(i)). Это верно в силу того, что коммуникация с интенсивностью c(e) выполняется в любой отрезок времени, в рамках которого линия связи e активна на канале i, и того, что f(e(i)) – средняя интенсивность, полученная для линии связи e для канала i. Из этого следует (e)
Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи
Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [ ]. Был разработан объединенный алгоритм аппроксимации под названием RCL для маршрутизации, распределения каналов и планирования линий связи. Алгоритм выполняет следующие операции в приведенном порядке:
1. Решение LP-задачи: Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения Я, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом.
2. Распределение каналов: На этом этапе алгоритм распределения каналов используется для регулировки потока управления в управляющем графе (изменения в маршрутизации), что позволяет гарантировать допустимое распределение каналов. Этап регулировки потока также стремится сохранить рост интерференции каждого канала на минимальном уровне.
3. Планирование линий связи в отсутствие интерференции: На этом этапе формируется план линий связи без возникновения интерференции для потоков по ребрам, соответствующих потоку управления в управляющем графе.
Каждый из этих этапов далее будет описан в соответствующем подразделе.
Алгоритм маршрутизации на базе линейного программирования
Линейная программа LP (1) для нахождения потока, максимизирующего значение Я: