Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 116: | Строка 116: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема. Алгоритм RCL представляет собой алгоритм Kc(q)/I-аппроксимации для маршрутизации и распределения каналов в задаче планирования ребер в отсутствие интерференции. | '''Теорема. Алгоритм RCL представляет собой алгоритм Kc(q)/I-аппроксимации для маршрутизации и распределения каналов в задаче планирования ребер в отсутствие интерференции.''' | ||
Доказательство. Заметим, что поток f(e(i)), возвращаемый алгоритмом распределения каналов в разделе «Распределение каналов», удовлетворяет ограничению нагруженности линий связи. Таким образом, из результата, полученного в разделе «Планирование потока управления линий связи», следует, что в результате масштабирования потока с дополнительным коэффициентом 1/c(q) можно сформировать его план, свободный от интерференции. В результате получаем допустимое решение объединенной задачи маршрутизации, распределения каналов и планирования со значением | Доказательство. Заметим, что поток f(e(i)), возвращаемый алгоритмом распределения каналов в разделе «Распределение каналов», удовлетворяет ограничению нагруженности линий связи. Таким образом, из результата, полученного в разделе «Планирование потока управления линий связи», следует, что в результате масштабирования потока с дополнительным коэффициентом 1/c(q) можно сформировать его план, свободный от интерференции. В результате получаем допустимое решение объединенной задачи маршрутизации, распределения каналов и планирования со значением <math>\lambda \;</math>, равным по меньшей мере <math>\lambda^* / \phi c(q) \;</math>. Таким образом, алгоритм RCL представляет собой алгоритм <math>\phi c(q) = Kc(q)/I \;</math> -аппроксимации. □ | ||
== Применение == | == Применение == |