Приложение. Параллельный метод распределения каналов.Для нахождения плана распределения каналов (ПРК) существуют точные методы и приближенные. При большом числе узлов в сети применяют более простые приближенные методы. Одним из таких методов является параллельный метод. Поясним на примере этот метод. Пусть заданы – структура первичной сети в виде взвешенного графа, где веса ребер графа соответствуют числу каналов между различными узлами сети, а также требования между различными корреспондирующими парами узлов в виде необходимого числа каналов. На рисунке 1 представлена структура сети, емкость каждой линии связи которой составляет 20 каналов.
Рисунок 1 Структура сети
Пусть необходимо, чтобы между узлами 1-3, 2-4, 3-6 и 5-6 в путях передачи информации было соответственно: φ13 =18; φ36 =16; φ24 =12; φ56 =16 каналов. В этом случае матрица требований Ф будет иметь вид (таблица 1). Таблица 1 Матрица требований Ф
Ф =
По данным структуры первичной сети можно простроить матрицу емкостей ребер U, которая представлена в виде таблиц 2.
Таблица 2
U=
Заданные требования, на первом этапе решения задачи, распределяются по возможным кратчайшим путям для каждой пары узлов независимо друг от друга, т.е. составляется идеальный ПРК. Этот план распределения каналов был бы оптимален, если бы ребра первичной сети имели неограниченную емкость. Затем идеальный ПРК корректируется до тех пор, пока не будут выполнены ограничения по емкостям на всех ветвях первичной сети. Коррекция первоначального плана осуществляется за счет перераспределения требуемого числа каналов между корреспондирующими узлами на ранее выбранных путях. При этом учитывается емкость ребер первичной сети. Процесс повторяется до тех пор, пока все требования не будут удовлетворены или дальнейшее удовлетворение требований станет невозможным. Более детально использование параллельного метода для распределения каналов первичной сети рассмотрим для сети, представленной на рисунке 1 с матрицей требований Ф (таблица1) и матрицей емкостей ребер U(таблица 2). 1. Из матрицы Ф выбираем требование φ13 = 18 каналов. 2. По рис. 8 определяем кратчайшие пути, которые могут быть использованы для связи узлов 1 и 8: μ11,2,3; μ21,4,3; μ31,5,3. 3. Определяем число каналов в каждом из этих путей, распределяя требуемое число каналов между 1 и 8 узлами равномерно по этим путям: С1(1,3) = C2(1,3) = C3(1,3) = 6 каналов. 4. Аналогично, все три пункта 1, 2, 3 выполняем для трех других пар узлов. В результате получаем: φ36 = 16 μ13,2,6 ; μ23,4,6; φ24 = 12 μ12,1,4; μ22,3,4; φ56 = 16 μ15,1,2,6 ; μ25,3,2,6; μ35,1,4,6; μ45,3,4,6. Число каналов в соответствующих путях: C1(3,6) = С2(3,6) = 8 С1(2,4) = С2(2,4) = 6 С1(5,6) = С2(5,6) = С3(5,6) =С4(5,6) = 4. 5. Далее составляем матрицу С - емкостей кратчайших путей и ребер для сделанного идеального варианта ПРК, представленную в табл. 3. 6. Подсчитываем для каждого ребра bijего емкость, полученную в результате загрузки в соответствии с идеальными ПРК и определяем Dij по формуле: Dij = С(bij) - Σ C(μr ij), μr ij Î bij. В графе Dij ставим со знаком «+» то число каналов, которое осталось не загруженным (ненасыщенные ребра) и со знаком «-» - число каналов, на которое загрузка ребра в соответствии с идеальным ПРК превышает заданное число каналов в ребре. Поскольку в строке Dij отмечены перегруженные ветви (b23 и b34), то идеальный ПРК недопустим. 7. По матрице С определяем, что перенасыщенной ветви b23 соответствуют пути С1(1-3), С1(3-6), С2(2-4) и С2(5-6). 8. Определяем пару узлов УК, которой соответствует первый из найденных в п.7 путей. Это будет пара узлов 1-3. Далее определяем, есть ли кратчайший путь, соответствующий паре узлов 1-3 и проходящий через ненасыщенных ребера. Если такой путь найден, то переходим к п.9. Если такого пути нет, т.е. все кратчайшие пути проходят хотя бы через одно насыщенные или перенасыщенные ребра, то переходим к п.11. 9. Путь между парой узлов 1-3, проходящий через ненасыщенные ребра, найден – это путь С3(1-3). Путь С2(1-3) использовать для перераспределения нельзя, так как он проходит через перенасыщенное ребро b34.Определяем величину перераспределяемой с пути С1(1-3) на путь С3(1-3) емкости. Так как в ребре b23 следует уменьшить число каналов на 4, с тем, чтобы его емкость не превышала заданную, то на всем пути С1(1-3) – в ребрах b12 и b23 – число требований следует уменьшить на 4, а в пути С3(1-3) – ребрах b15 и b35 – увеличить на 4. Старые значения (они в таблице 3 указаны в скобках) исправляем на новые. Новые значения емкостей проставлены сверху. В строке D'ij рассчитаны новые величины Dij, с учетом откорректированного плана распределения каналов. 10. ПРК остался недопустимым, так как еще перенасыщена ветвь b34. Повторяем действия пп. 7, 8, 9. В результате находим, что для пары 2-4 существует путь С1(2-4), который проходит по ненасыщенным ребрам b1,2 и b14. В пути С2(2-4) емкости ребер уменьшаем на 4, а в пути С1(2-4) – увеличиваем на ту же величину. В строке D''ij рассчитаны новые величины Dij, с учетом откорректированного плана распределения каналов. Данный ПРК допустим, так как в строке D''ij все значения положительные. Полученные элементы матрицы С определяют искомый ПРК. 11. Если кратчайшего пути с ненасыщенными ребрами для данной пары не найдено, то переходим к следующему пути, соответствующему ненасыщенной ветви, и повторяем п.9. Процесс повторяем до тех пор, пока не будет найден для какой-либо пары УК ненасыщенный кратчайший путь. Если для всех пар не найдено путей с ненасыщенными ветвями, то требования не могут быть удовлетворены по кратчайшим путям, и следует найти путь, содержащий большее число транзитных участков и состояний из ненасыщенных ребер. Если такого пути не существует, то требования не могут быть удовлетворены полностью. В этом случае необходимо уменьшить величину требований или увеличить число каналов первичной сети и решать эту задачу заново. Таблица 3 План распределения каналов
|
Матрица емкостей ребер U
