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

Перейти к навигации Перейти к поиску
Строка 12: Строка 12:
Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан алгоритм аппроксимации под названием RCL для решения объединенной задачи маршрутизации, распределения каналов и планирования линий связи. Алгоритм выполняет следующие операции в приведенном порядке:
Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан алгоритм аппроксимации под названием RCL для решения объединенной задачи маршрутизации, распределения каналов и планирования линий связи. Алгоритм выполняет следующие операции в приведенном порядке:


1. '''Решение LP-задачи'''. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения Я, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом.
1. '''Решение LP-задачи'''. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения <math>\lambda \;</math>, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом.


2. '''Распределение каналов'''. На этом этапе алгоритм распределения каналов используется для регулировки потока управления в управляющем графе (изменения в маршрутизации), что позволяет гарантировать допустимое распределение каналов. Этап регулировки потока также стремится сохранить рост интерференции каждого канала на минимальном уровне.
2. '''Распределение каналов'''. На этом этапе алгоритм распределения каналов используется для регулировки потока управления в управляющем графе (внесения изменений в маршрутизацию), что обеспечивает допустимость распределения каналов. Данный этап регулировки потока также пытается сохранить повышение интерференции в каждом канале на минимальном уровне.


3. '''Планирование линий связи в отсутствие интерференции'''. На этом этапе формируется план линий связи без возникновения интерференции для потоков по ребрам, соответствующих потоку управления в управляющем графе.
3. '''Планирование линий связи в отсутствие интерференции'''. На этом этапе формируется план линий связи без возникновения интерференции для потоков по ребрам, соответствующих потоку управления в управляющем графе.
Источник — http://pco.iis.nsk.su/wega/index.php/Распределение_каналов_и_маршрутизация_в_беспроводных_ячеистых_мультирадиосетях