Приложение. Параллельный метод распределения каналов.

Для нахождения плана распределения каналов (ПРК) существуют точные методы и приближенные. При большом числе узлов в сети применяют более простые приближенные методы. Одним из таких методов является параллельный метод. Поясним на примере этот метод.

Пусть заданы – структура первичной сети в виде взвешенного графа, где веса ребер графа соответствуют числу каналов между различными узлами сети, а также требования между различными корреспондирующими парами узлов в виде необходимого числа каналов. На рисунке 1 представлена структура сети, емкость каждой линии связи которой составляет 20 каналов.

Рисунок 1 Структура сети

Пусть необходимо, чтобы между узлами 1-3, 2-4, 3-6 и 5-6 в путях передачи информации было соответственно: φ₁₃ =18; φ₃₆ =16; φ₂₄ =12; φ₅₆ =16 каналов. В этом случае матрица требований Ф будет иметь вид (таблица 1).

Таблица 1 Матрица требований Ф

Ф =

По данным структуры первичной сети можно простроить матрицу емкостей ребер U, которая представлена в виде таблиц 2.

Таблица 2 Матрица емкостей ребер U

U=

Заданные требования, на первом этапе решения задачи, распределяются по возможным кратчайшим путям для каждой пары узлов независимо друг от друга, т.е. составляется идеальный ПРК. Этот план распределения каналов был бы оптимален, если бы ребра первичной сети имели неограниченную емкость. Затем идеальный ПРК корректируется до тех пор, пока не будут выполнены ограничения по емкостям на всех ветвях первичной сети. Коррекция первоначального плана осуществляется за счет перераспределения требуемого числа каналов между корреспондирующими узлами на ранее выбранных путях. При этом учитывается емкость ребер первичной сети. Процесс повторяется до тех пор, пока все требования не будут удовлетворены или дальнейшее удовлетворение требований станет невозможным.

Более детально использование параллельного метода для распределения каналов первичной сети рассмотрим для сети, представленной на рисунке 1 с матрицей требований Ф (таблица1) и матрицей емкостей ребер U(таблица 2).

1. Из матрицы Ф выбираем требование φ₁₃ = 18 каналов.

2. По рис. 8 определяем кратчайшие пути, которые могут быть использованы для связи узлов 1 и 8:

μ¹_1,2,3; μ²_1,4,3; μ³_1,5,3.

3. Определяем число каналов в каждом из этих путей, распределяя требуемое число каналов между 1 и 8 узлами равномерно по этим путям:

С¹(1,3) = C²(1,3) = C³(1,3) = 6 каналов.

4. Аналогично, все три пункта 1, 2, 3 выполняем для трех других пар узлов. В результате получаем:

φ₃₆ = 16 μ¹_3,2,6 ; μ²_3,4,6;

φ₂₄ = 12 μ¹_2,1,4; μ²_2,3,4;

φ₅₆ = 16 μ¹_5,1,2,6 ; μ²_5,3,2,6; μ³_5,1,4,6; μ⁴_5,3,4,6.

Число каналов в соответствующих путях:

C¹(3,6) = С²(3,6) = 8

С¹(2,4) = С²(2,4) = 6

С¹(5,6) = С²(5,6) = С³(5,6) =С⁴(5,6) = 4.

5. Далее составляем матрицу С - емкостей кратчайших путей и ребер для сделанного идеального варианта ПРК, представленную в табл. 3.

6. Подсчитываем для каждого ребра b_ijего емкость, полученную в результате загрузки в соответствии с идеальными ПРК и определяем D_ij по формуле:

D_ij = С(b_ij) - Σ C(μ^r _ij), μ^r _ij Î b_ij.

В графе D_ij ставим со знаком «+» то число каналов, которое осталось не загруженным (ненасыщенные ребра) и со знаком «-» - число каналов, на которое загрузка ребра в соответствии с идеальным ПРК превышает заданное число каналов в ребре. Поскольку в строке D_ij отмечены перегруженные ветви (b₂₃ и b₃₄), то идеальный ПРК недопустим.

7. По матрице С определяем, что перенасыщенной ветви b₂₃ соответствуют пути С¹(1-3), С¹(3-6), С²(2-4) и С²(5-6).

8. Определяем пару узлов УК, которой соответствует первый из найденных в п.7 путей. Это будет пара узлов 1-3. Далее определяем, есть ли кратчайший путь, соответствующий паре узлов 1-3 и проходящий через ненасыщенных ребера.

Если такой путь найден, то переходим к п.9. Если такого пути нет, т.е. все кратчайшие пути проходят хотя бы через одно насыщенные или перенасыщенные ребра, то переходим к п.11.

9. Путь между парой узлов 1-3, проходящий через ненасыщенные ребра, найден – это путь С³(1-3). Путь С²(1-3) использовать для перераспределения нельзя, так как он проходит через перенасыщенное ребро b₃₄.Определяем величину перераспределяемой с пути С¹(1-3) на путь С³(1-3) емкости. Так как в ребре b₂₃ следует уменьшить число каналов на 4, с тем, чтобы его емкость не превышала заданную, то на всем пути С¹(1-3) – в ребрах b₁₂ и b₂₃ – число требований следует уменьшить на 4, а в пути С³(1-3) – ребрах b₁₅ и b₃₅ – увеличить на 4. Старые значения (они в таблице 3 указаны в скобках) исправляем на новые. Новые значения емкостей проставлены сверху. В строке D'_ij рассчитаны новые величины D_ij, с учетом откорректированного плана распределения каналов.

10. ПРК остался недопустимым, так как еще перенасыщена ветвь b₃₄. Повторяем действия пп. 7, 8, 9. В результате находим, что для пары 2-4 существует путь С¹(2-4), который проходит по ненасыщенным ребрам b_1,2 и b₁₄. В пути С²(2-4) емкости ребер уменьшаем на 4, а в пути С¹(2-4) – увеличиваем на ту же величину. В строке D''_ij рассчитаны новые величины D_ij, с учетом откорректированного плана распределения каналов.

Данный ПРК допустим, так как в строке D''_ij все значения положительные. Полученные элементы матрицы С определяют искомый ПРК.

11. Если кратчайшего пути с ненасыщенными ребрами для данной пары не найдено, то переходим к следующему пути, соответствующему ненасыщенной ветви, и повторяем п.9. Процесс повторяем до тех пор, пока не будет найден для какой-либо пары УК ненасыщенный кратчайший путь. Если для всех пар не найдено путей с ненасыщенными ветвями, то требования не могут быть удовлетворены по кратчайшим путям, и следует найти путь, содержащий большее число транзитных участков и состояний из ненасыщенных ребер. Если такого пути не существует, то требования не могут быть удовлетворены полностью. В этом случае необходимо уменьшить величину требований или увеличить число каналов первичной сети и решать эту задачу заново.

Таблица 3 План распределения каналов