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

Перейти к навигации Перейти к поиску
Строка 94: Строка 94:




Лемма 1. c(q) = 8 для 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, что вытекает из заявленной границы.
Доказательство. Вспомним, что ребро <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, образованную объединением двух кругов Cu и Cv радиусом <math>2R_T \;</math> каждый, с центрами в вершинах u и v, соответственно. Тогда e0 = (u0, v0) 2 I(e) в том и только том случае, если по меньшей мере одна из вершин u0, v0 находится в C. Обозначим такую вершину как C(e0). Пусть даны два ребра e1,e2 2 I(e), не интерферирующие друг с другом – это означает, что вершины C(e1) и C(e2) находятся на расстоянии не менее <math>2R_T \;</math> друг от друга. Таким образом, верхнюю границу количества ребер множества I(e), не интерферирующих попарно друг с другом, можно получить при помощи вычисления числа вершин, которые могут быть помещены в множество C, находящихся попарно на расстоянии не менее <math>2R_T \;</math> друг от друга. Можно показать [1], что это количество не превышает 8. Таким образом, в плане S в заданном отрезке времени существует только одна из двух возможностей: либо в план входит ребро e, либо «независимое» множество ребер из I(e) размером не более 8, что вытекает из заявленной границы.