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

Из этого следует, что если новый поток отличается в <math>1 / \phi \;</math> раз, то он является допустимым для LP (1). Отметим, что подразумеваемое распределение каналов (назначение каждой вершине каналов от 1 до I) также является допустимым. Таким образом, вышеприведенный алгоритм находит допустимое распределение каналов со значением <math>\lambda \;</math> не менее <math>\lambda^* / \phi \;</math>.

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

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

После этого алгоритм масштабирует поток при помощи максимального возможного коэффициента (не менее <math>l / \phi \;</math>) таким образом, чтобы полученный поток представлял собой допустимое решение задачи линейного программирования LP (1) и подразумевал допустимое решение задачи распределения каналов. Таким образом, полный алгоритм находит допустимое распределение каналов (за счет того, что не ограничивается каналами с 1 до I) со значением <math>\lambda \;</math> не менее <math>\lambda^* / \phi \;</math>.