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

Пусть дана беспроводная ячеистая магистральная сеть, моделируемая графом (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> множество ребер, с которыми у него возникает интерференция. Пара вершин, которые используют один и тот же канал и находятся в диапазоне интерференции 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)