4430
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 22:34, 3 января 2017
, 3 января 2017→Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
== Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи == | == Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи == | ||
Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан | Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан алгоритм аппроксимации под названием RCL для решения объединенной задачи маршрутизации, распределения каналов и планирования линий связи. Алгоритм выполняет следующие операции в приведенном порядке: | ||
1. '''Решение LP-задачи'''. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения Я, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом. | 1. '''Решение LP-задачи'''. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения Я, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом. | ||