4430
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Перейти к навигации
Перейти к поиску
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 11:53, 3 января 2017
, 3 января 2017→Планирование потока управления линий связи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 89: | Строка 89: | ||
== Планирование потока управления линий связи == | == Планирование потока управления линий связи == | ||
Результаты данного раздела получены путем расширения результатов работы [4] для случая с единственным каналом и для модели протокола интерференции [ ]. Вспомним, что план S с разбиением на отрезки времени предполагается периодическим (с периодом T), где переменная-индикатор ХС);)Т, e 2 E; i 2 F(e), x > 1 равна 1 в том и только том случае, если линия связи e активна во временном отрезке r на канале i, а i – общий канал между множеством каналов, присвоенных конечным вершинам ребра e. | |||
Если непосредственно применить результат (утверждение 2) из [ ], получим, что обязательное условие для планирования линий связи в отсутствие интерференции заключается в том, что для каждой e 2 E;i 2 F(e), r > 1: XC;,;T+ ^2e'€i(e)Xe',i,T — c(q). Здесь c(q) – константа, которая зависит только от модели интерференции. В модели интерференции эта константа является функцией от фиксированного значения q – отношения диапазона интерференции RI к диапазону передачи RT; интуитивные соображения по ее выводу для конкретного значения q = 2 приведены ниже. | |||
Лемма 1. c(q) = 8 для q = 2. | |||
Доказательство. Вспомним, что ребро e0 2 I(e), если существуют две вершины x, y 2 V, которые находятся не более чем на расстоянии 2RT друг от друга, такие, что ребро e инцидентно вершине x, а ребро e0 инцидентно вершине y. Пусть e = (u, v). Заметим, что u и v находятся не более чем на расстоянии RT друг от друга. Рассмотрим область C, образованную объединением двух кругов Cu и Cv радиусом 2RT каждый, с центрами в вершинах u и v, соответственно. Тогда e0 = (u0, v0) 2 I(e) в том и только том случае, если по меньшей мере одна из вершин u0, v0 находится в C. Обозначим такую вершину как C(e0). Пусть даны два ребра e1,e2 2 I(e), не интерферирующие друг с другом – это означает, что вершины C(e1) и C(e2) находятся на расстоянии не менее 2RT друг от друга. Таким образом, верхнюю границу количества ребер множества I(e), не интерферирующих попарно друг с другом, можно получить при помощи вычисления числа вершин, которые могут быть помещены в множество C, находящихся попарно на расстоянии не менее 2RT друг от друга. Можно показать [1], что это количество не превышает 8. Таким образом, в плане S в заданном отрезке времени существует только одна из двух возможностей: либо в план входит ребро e, либо «независимое» множество ребер из I(e) размером не более 8, что вытекает из заявленной границы. | |||
Необходимое условие (ограничение нагруженности линий связи). Вспомним, что T Х!кт<г^е,1, = c(e((ei))). Таким образом, Любое допустимое ребро, «свободное от интерференции», должно удовлетворять ограничению нагруженности для каждой линии связи e и каждого канала i: | |||
< | |||
c(e) | |||
c(e0) | |||
(6) | |||
e02I(e) | |||
Также было установлено соответствующее достаточное условие [1]. | |||
Достаточное условие (ограничение нагруженности линий связи). Если для каждой линии связи e и каждого канала i поток по ребру удовлетворяет следующему ограничению планируемости линий связи, то можно составить график коммуникации с ребрами, свободными от интерференции, при помощи алгоритма, предложенного в [1]. | |||
(7) | |||
c(e) | |||
c(e0) | |||
< 1: | |||
e02I(e) | |||
Из вышеприведенного соотношения следует, что если поток f(e(i)) удовлетворяет ограничению нагруженности линий связи, то в результате масштабирования потока с коэффициентом 1/c(q) его можно спланировать свободным от интерференции. | |||
== Основные результаты == | |||