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

Вначале заметим, что в «холостом» сценарии, в котором все вершины 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)