4430
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Материал из WEGA
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 14:31, 14 декабря 2016
, 14 декабря 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
Распределение каналов | Распределение каналов | ||
Решение задачи линейного программирования (1) представляет собой набор значений потока f(e(i)) для ребра e и канала i, максимизирующих значение A. Обозначим за A* оптимальное значение A. Поток 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 только для каналов 1 < i: < I. Базовая операция, используемая алгоритмом, заключается в равномерном распределении для каждого ребра e потока f(e(i)), I < i < K, на ребра e(j), 1 < i < I. Это гарантирует, что после завершения операции все f(e(i)) = 0, I < i < K. Данная операция будет называться первым этапом алгоритма. На первом этапе не нарушаются ограничения сохранения потока управления и ограничения на радиостанции в вершинах (5) из алгоритма LP (1). Можно показать, что в полученном решении поток f(e(i)) может превышать пропускную способность ребра e не более чем на коэффициент ф = K/I. Он называется «коэффициентом инфляции» первого этапа. Аналогичным образом ограничение нагруженности линий связи (5) у нового потока также может нарушаться для ребра e и канала i на величину, не превышающую коэффициент инфляции. Иными словами, в полученном потоке c(e) c(e0) + e02I(e) | |||
