4446
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Материал из WEGA
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 12:11, 3 января 2017
, 3 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 126: | Строка 126: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема. Алгоритм RCL представляет собой алгоритм Kc(q)/I-аппроксимации для маршрутизации и распределения каналов в задаче планирования ребер в отсутствие интерференции. | |||
Доказательство. Заметим, что поток f(e(i)), возвращаемый алгоритмом распределения каналов в разделе «Распределение каналов», удовлетворяет ограничению нагруженности линий связи. Таким образом, из результата, полученного в разделе «Планирование потока управления линий связи», следует, что в результате масштабирования потока с дополнительным коэффициентом 1/c(q) можно сформировать его план, свободный от интерференции. В результате получаем допустимое решение объединенной задачи маршрутизации, распределения каналов и планирования со значением A, равным по меньшей мере \*l(pc{q). Таким образом, алгоритм RCL представляет собой алгоритм cpc(q) = Kc(q)/I-аппроксимации. □ | |||
== Применение == | |||
