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

Доказательство. Вспомним, что ребро <math>e' \in I(e) \;</math>, если существуют две вершины <math>x, y \in V \;</math>, которые находятся не более чем на расстоянии <math>2R_T \;</math> друг от друга, такие, что ребро e инцидентно вершине x, а ребро e' инцидентно вершине y. Пусть e = (u, v). Заметим, что u и v находятся не более чем на расстоянии <math>R_T \;</math> друг от друга. Рассмотрим область C, образованную объединением двух кругов <math>C_u \;</math> и <math>C_v \;</math> радиусом <math>2R_T \;</math> каждый, с центрами в вершинах u и v, соответственно. Тогда <math>e' = (u', v') \in I(e) \;</math> в том и только том случае, если по меньшей мере одна из вершин u', v' находится в C. Обозначим такую вершину как C(e'). Пусть даны два ребра <math>e_1, e_2 \in I(e) \;</math>, не интерферирующие друг с другом – это означает, что вершины <math>C(e_1) \;</math> и <math>C(e_2) \;</math> находятся на расстоянии не менее <math>2R_T \;</math> друг от друга. Таким образом, верхнюю границу количества ребер множества I(e), не интерферирующих попарно друг с другом, можно получить при помощи вычисления числа вершин, которые могут быть помещены в множество C, находящихся попарно на расстоянии не менее <math>2R_T \;</math> друг от друга. Можно показать [1], что это количество не превышает 8. Таким образом, в плане S в заданном отрезке времени имеет место только одна из двух возможностей: либо в план входит ребро e, либо «независимое» множество ребер из I(e) размером не более 8, что вытекает из заявленной границы.  □

<math>\frac{f(e(i))}{c(e)} + \sum_{e' \in I(e)} \frac{f(e'(i))}{c(e')} \le c(q)</math>. (6)

'''Достаточное условие''' (ограничение нагруженности линий связи). Если для каждой линии связи e и каждого канала i поток по ребру удовлетворяет следующему ограничению планируемости линий связи, то можно составить график коммуникации с ребрами, свободными от интерференции, при помощи алгоритма, предложенного в [1].

<math>\frac{f(e(i))}{c(e)} + \sum_{e' \in I(e)} \frac{f(e'(i))}{c(e')} \le 1</math>. (7)

Из вышеприведенного соотношения следует, что если поток f(e(i)) удовлетворяет ограничению нагруженности линий связи, то в результате масштабирования потока с коэффициентом 1/c(q) его можно спланировать свободным от интерференции.