4430
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Материал из WEGA
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 14:03, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 10: | Строка 10: | ||
== Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи == | == Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи == | ||
Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан алгоритм | Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан аппроксимационный алгоритм под названием RCL для решения объединенной задачи маршрутизации, распределения каналов и планирования линий связи. Алгоритм выполняет следующие операции в приведенном порядке: | ||
1. '''Решение LP-задачи'''. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения <math>\lambda \;</math>, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом. | 1. '''Решение LP-задачи'''. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения <math>\lambda \;</math>, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом. | ||
| Строка 117: | Строка 117: | ||
== Основные результаты == | == Основные результаты == | ||
'''Теорема. Алгоритм 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>-аппроксимации. □ | ||
== Применение == | == Применение == | ||
Ячеистые сети инфраструктуры получают все большее распространение – как для коммерческого использования, так и для правоохранительной деятельности. Подобный контекст использования налагает строгие ограничения на эффективность лежащих в их основе беспроводных ячеистых мультирадиосетей без интерференции (IWMN). Гарантированная ширина пропускной способности является одним из важнейших требований при работе в подобных условиях. В таких IWMN изменение топологии происходит нечасто, а вариабельность объединенного запроса на трафик от каждого роутера ячеистой сети (точки агрегации клиентского трафика) невысока. Эти характеристики допускают периодическую оптимизацию сети, которая может выполняться управляющим системой программным обеспечением на основе оценки потребности в трафике. Данная работа может быть напрямую применена к сетям типа IWMN. Кроме того, она может использоваться в качестве эталонной для сравнения с эвристическими алгоритмами в многоскачковых беспроводных сетях. | Ячеистые сети инфраструктуры получают все большее распространение – как для коммерческого использования, так и для правоохранительной деятельности. Подобный контекст использования налагает строгие ограничения на эффективность лежащих в их основе беспроводных ячеистых мультирадиосетей без интерференции (IWMN). Гарантированная ширина пропускной способности является одним из важнейших требований при работе в подобных условиях. В таких IWMN изменение топологии происходит нечасто, а вариабельность объединенного запроса на трафик от каждого роутера ячеистой сети (точки агрегации клиентского трафика) невысока. Эти характеристики допускают периодическую оптимизацию сети, которая может выполняться управляющим системой программным обеспечением на основе оценки потребности в трафике. Данная работа может быть напрямую применена к сетям типа IWMN. Кроме того, она может использоваться в качестве эталонной для сравнения с эвристическими алгоритмами в многоскачковых беспроводных сетях. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
В дальнейшем было бы любопытно исследовать задачу, в которой решения для маршрутизации могут быть дополнены изменением весов линий связи при помощи протокола распределенной маршрутизации – такого как OSPF. Также интересно узнать, нельзя ли улучшить границу для наихудшего случая (например, получить константный коэффициент, независимый от | В дальнейшем было бы любопытно исследовать задачу, в которой решения для маршрутизации могут быть дополнены изменением весов линий связи при помощи протокола распределенной маршрутизации – такого как OSPF. Также интересно узнать, нельзя ли улучшить границу для наихудшего случая (например, получить константный коэффициент, независимый от K и I)? | ||
== См. также == | == См. также == | ||
* ''[[Раскраска графа]] | * ''[[Раскраска графа]] | ||
