Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями

Пусть дана беспроводная ячеистая магистральная сеть, моделируемая графом (V, E). Вершина <math>t \in V \;</math> представляет проводную сеть. Ребро e = (u, v) существует в E в том и только том случае, если u и v располагаются внутри ''диапазона связи'' <math>R_T \;</math>. Множество <math>V_G \subseteq V \;</math> представляет множество шлюзовых вершин. Система имеет K каналов в сумме. Каждая вершина <math>u \in V \;</math> имеет I(u) карт плат сетевых интерфейсов и суммарный спрос l(u) от связанных с ней пользователей. Для каждого ребра e обозначим за <math>I(e) \subset E \;</math> множество ребер, с которыми у него возникает интерференция. Пара вершин, которые используют один и тот же канал и находятся в ''диапазоне интерференции'' <math>R_Ix \;</math>, могут создавать помехи друг для друга, даже если они не связываются напрямую. Пары вершин, использующие разные каналы, могут одновременно отправлять пакеты, не вызывая интерференции. Задача заключается в максимизации <math>\lambda \;</math>, где по меньшей мере <math>\lambda l(u) \;</math> объема пропускной способности может быть направлено из каждый вершины u в Интернет (представленный вершиной t). Пропускную способность <math>\lambda l(u) \;</math> для каждой вершины u можно получить, вычислив (1) сетевой поток, ассоциирующий с каждым ребром e = (u, v) значения <math>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)), такое, что для любых f(e(i)) > 0, <math>i \in F(u) \cap F(v) \;</math>; (3) ''осуществимый'' график S, согласно которому множество пар «ребро-канал» (e, i) (где ребро e использует канал, т.е. f(e(i)) > 0 планируется на отрезок времени <math>\tau \;</math> для <math>\tau = 1, 2, ... , T \;</math>, где T – период графика. График является осуществимым, если никакие ребра из пар ребер <math>(e_1, i), (e_2, i) \;</math>, спланированных на один отрезок времени на общий канал i, не интерферируют друг с другом: <math>e_1 \notin I(e_2), e_2 \notin I(e_1) \;</math>. В силу этого осуществимый график также называют графиком с ребрами, свободными от интерференции. Мы будем использовать переменную-индикатор <math>X_{e, i, \tau}, e \in E, i \in F(e), \tau \ge 1 \;</math>. Ей присваивается значение 1 в том и только том случае, если линия связи e активна в отрезок времени <math>\tau \;</math> на канале i. Отметим, что <math>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>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>\lambda \;</math> (1)