4430
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Материал из WEGA
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 22:20, 27 декабря 2016
, 27 декабря 2016→Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 68: | Строка 68: | ||
Вначале заметим, что в «холостом» сценарии, в котором все вершины 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 не более чем на коэффициент <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> | Вначале заметим, что в «холостом» сценарии, в котором все вершины 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 не более чем на коэффициент <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/ф раз, то он является допустимым для LP (1). Отметим, что подразумеваемое распределение каналов (назначение каждой вершине каналов от 1 до I) также является допустимым. Таким образом, вышеприведенный алгоритм находит допустимое распределение каналов со значением Я не менее Х*/ф. | |||
Одним из недостатков описанного алгоритма распределения каналов (этапа 1) является то, что он использует только I из K доступных каналов. При использовании большего количества каналов возникает возможность дополнительного снижения интерференции, что позволяет передавать через систему поток большего объема. Алгоритм распределения каналов использует для этого дополнительную эвристику. Назовем ее вторым первым этапом алгоритма. | |||
Теперь определим операцию под названием «операция переключения каналов». Пусть A – максимальная связная компонента (вершины из A не связаны с вершинами вне A) в графе, образованная ребрами e для заданного канала i, для которого f(e(i)) > 0. Можно заметить, что для заданного канала j операция полного переноса потока f(e(i)) в поток f(e(j)) для каждого ребра e из A не влияет на допустимость подразумеваемого распределения каналов. Это верно в силу того, что после преобразования потока не увеличивается количество каналов, назначенных одной вершине: конечные вершины ребер e в A, которые ранее были назначены каналу i, теперь назначены каналу j. Таким образом, это преобразование эквивалентно переключению распределения каналов в вершинах из A таким образом, словно канал i отбрасывается, а канал j добавляется, если он еще не был назначен. | |||
Эвристика на втором этапе пытается заново преобразовать немасштабированные потоки f(e(i)) из первого этапа таким образом, что в графах G(e, i) будут иметься множественные связные компоненты, образованные ребрами e для каждого канала 1 < i: < I. Это повторное преобразование выполняется таким образом, чтобы удовлетворялись ограничения линейного программирования с коэффициентом инфляции, не превышающим ', как в случае немасштабированного потока после заверения первого этапа алгоритма. | |||
Затем, на третьем этапе работы алгоритма, связные компоненты каждого графа G(e, i) группируются таким образом, чтобы получилось количество групп, максимально близкое к K (но не превышающее его), и чтобы максимальная интерференция внутри каждой группы были минимизирована. Затем вершины в l-й группе назначаются каналу l при помощи операции переключения канала для выполнения соответствующего преобразования потока. Можно показать, что распределение каналов, подразумеваемое потоком на третьем этапе алгоритма, является допустимым. Кроме того, потоки f(e(i)) удовлетворяют ограничениям LP (1) с коэффициентом инфляции, не превышающим ф = K/I. | |||
После этого алгоритм масштабирует поток с учетом максимального возможного фрагмента (не менее l/ф) таким образом, чтобы полученный поток представлял собой допустимое решение задачи линейного программирования LP (1) и подразумевал допустимое решение задачи распределения каналов. Таким образом, полный алгоритм находит допустимое распределение каналов (за счет того, что не ограничивается каналами с 1 до I) со значением Я не менее Х*/ф. | |||
== Планирование потока управления линий связи == | |||
