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

Ключевые слова и синонимы

Раскраска графа, децентрализованные сети

Постановка задачи

Одной из важнейших проблем беспроводных сетей является снижение емкости из-за интерференции при нескольких одновременных передачах. В беспроводных ячеистых сетях наличие роутеров ячеистой мультирадиосети способно существенно снизить остроту этой проблемы. В мультирадиосетях вершины способны одновременно передавать и принимать сигнал либо передавать сигнал одновременно по нескольким каналам. Однако из-за ограниченного числа доступных каналов невозможно полностью устранить интерференцию; для снижения влияния интерференции необходимо аккуратное распределение каналов. Распределение каналов и маршрутизация взаимосвязаны, поскольку распределение влияет на пропускную способность линий связи и на то, в какой степени передачи по этим линиям подвержены помехам. Очевидно, что это влияет и на маршрутизацию, задача которой заключается в удовлетворении запросов на трафик. Точно так же маршрутизация трафика определяет его потоки по каждой линии, что определенно влияет на распределение каналов. Распределение должно выполняться таким образом, чтобы удовлетворялись требования к коммуникациям для каналов связи. Таким образом, задачу максимизации пропускной способности в беспроводных ячеистых сетей необходимо решать при помощи распределения каналов, маршрутизации и планирования.

Пусть дана беспроводная ячеистая магистральная сеть, моделируемая графом (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)

Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи