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