4430
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Материал из WEGA
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 12:34, 26 декабря 2016
, 26 декабря 2016→Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
Затем задача линейного программирования заново решается с использованием этой целевой функции и при фиксированном значении | Затем задача линейного программирования заново решается с использованием этой целевой функции и при фиксированном значении <math>\lambda \;</math>, равном <math>\lambda^* \;</math>. | ||
'''Распределение каналов''' | |||
Решение задачи линейного программирования (1) представляет собой набор значений потока f(e(i)) для ребра e и канала i, максимизирующих значение <math>\lambda \;</math>. Обозначим за <math>\lambda^* \;</math> оптимальное значение <math>\lambda \;</math>. Поток f(e(i)) подразумевает распределение каналов, при котором обе конечных точки ребра e назначены каналу i в том и только том случае, если f(e(i)) > 0. Заметим, что подразумеваемое распределение каналов для потока f(e(i)) может не быть допустимым (для него может потребоваться более I(v) каналов в вершине v). Алгоритм распределения каналов преобразует заданный поток таким образом, чтобы искоренить недостаток допустимости. Ниже приводится краткое описание алгоритма. Более детальное изложение можно найти в работе [1]. | |||
Вначале заметим, что в «холостом» сценарии, в котором все вершины v имеют одно и то же количество интерфейсов I (т.е. I = I(v)) и количество доступных каналов K также равно I, распределение каналов, найденное алгоритмом LP (1), является допустимым. Этот так, поскольку даже тривиальное распределение каналов, в котором всем вершинам назначаются все каналы от 1 до I, является допустимым. Основная идея алгоритма заключается в следующем. Вначале следует преобразовать решение LP (1) в новый поток, в котором каждое ребро e имеет поток f(e(i)) > 0 только для каналов <math>1 \le i \le I \;</math>. Базовая операция, используемая алгоритмом, заключается в равномерном распределении для каждого ребра e потока f(e(i)), <math>I \le i \le K \;</math>, на ребра <math>e(j), 1 \le i \le I \;</math>. Это гарантирует, что после завершения операции все <math>f(e(i)) = 0, I \le i \le K \;</math>. Данная операция будет называться ''первым этапом'' алгоритма. На первом этапе не нарушаются ограничения сохранения потока управления и ограничения на радиостанции в вершинах (5) из алгоритма LP (1). Можно показать, что в полученном решении поток f(e(i)) может превышать пропускную способность ребра e не более чем на коэффициент ф = K/I. Он называется «коэффициентом инфляции» первого этапа. Аналогичным образом ограничение нагруженности линий связи (5) у нового потока также может нарушаться для ребра e и канала i на величину, не превышающую коэффициент инфляции. Иными словами, в полученном потоке c(e) c(e0) + e02I(e) | |||
Вначале заметим, что в «холостом» сценарии, в котором все вершины v имеют одно и то же количество интерфейсов I (т.е. I = I(v)) и количество доступных каналов K также равно I, распределение каналов, найденное алгоритмом LP (1), является допустимым. Этот так, поскольку даже тривиальное распределение каналов, в котором всем вершинам назначаются все каналы от 1 до I, является допустимым. Основная идея алгоритма заключается в следующем. Вначале следует преобразовать решение LP (1) в новый поток, в котором каждое ребро e имеет поток f(e(i)) > 0 только для каналов 1 | |||
