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

Вначале заметим, что в «холостом» сценарии, в котором все вершины 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 потока <math>f(e(i)), I < i \le K \;</math>, на ребра <math>e(j), 1 \le i \le I \;</math>. Это гарантирует, что после завершения операции все <math>f(e(i)) = 0, I < i \le K \;</math>. Данная операция будет называться ''первым этапом'' алгоритма. На первом этапе не нарушаются ограничения сохранения потока управления и ограничения на радиостанции в вершинах (5) из алгоритма LP (1). Можно показать, что в полученном решении поток f(e(i)) может превышать пропускную способность ребра e не более чем на коэффициент <math>\phi = K/I \;</math>. Он называется «коэффициентом инфляции» первого этапа. Аналогичным образом ''ограничение нагруженности линий связи'' (5) у нового потока также может нарушаться для ребра e и канала i на величину, не превышающую коэффициент инфляции. Иными словами, в полученном потоке выполняется соотношение <math>\frac{f(e(i))}{c(e)} + \sum_{e' \in I(e)} \frac{f(e'(i))}{c(e')} \le \phi c(q).</math>

Одним из недостатков описанного алгоритма распределения каналов (этапа 1) является то, что он использует только I из K доступных каналов. При использовании большего количества каналов возникает возможность дополнительного снижения интерференции, что позволяет передавать через систему поток большего объема. Алгоритм распределения каналов использует для этого дополнительную эвристику. Назовем ее вторым этапом алгоритма.

Эвристика второго этапа пытается заново преобразовать немасштабированные потоки f(e(i)) из первого этапа таким образом, что в графах G(e, i) будут иметься множественные связные компоненты, образованные ребрами e для каждого канала <math>1 \le i \le I \;</math>. Это повторное преобразование выполняется таким образом, чтобы удовлетворялись ограничения линейного программирования с коэффициентом инфляции, не превышающим <math>\phi \;</math>, как в случае немасштабированного потока после заверения первого этапа алгоритма.