Сети связи

Методы распределения каналов первичной сети | назад |

ВВЕДЕНИЕ

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

1. Методы распределения каналов первичной сети

1.1. Симплекс-метод

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

Пусть М = {

μi} – совокупность путей, которые могут быть использованы для передачи потоков информации между узлами сети; fi – емкость пути μi, а ci – вес этого пути, который определяет относительную целесообразность использования пути и может быть выбран обратно пропорционально его длине, стоимости и т.п. (Выбор сi зависит от критерия, по которому производится оптимизация распределения). При оптимизации по длине пути в качестве сi можно, например, взять отношение самого длинного пути к длине рассматриваемого i-го пути, выбрав коэффициент k таким образом, чтобы сi были целыми числами:

сi = k(lmax / li).

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

F = ∑ cjfj

μ

j Є М

при следующих ограничениях:

1) емкости путей не могут принимать отрицательных значений, т.е. fj = 0 для всех μjЄМ;

2) суммарная емкость совокупности путей Мkl = {μj(kl)} между произвольной парой k и l узлов сети должна быть равна (если это возможно) числу каналов φkl, которое необходимо организовать в пучке между указанной парой узлов сети для передачи потока с требуемым качеством обслуживания, т.е.

∑ fj (kl) ≤ φkl;

μj(kl) Є Mkl

3) для любой ветви βxy сети суммарная емкость всех путей, содержащих эту ветвь, не может быть больше емкости ветви, т.е.

∑ fj ≤ bxy.

μj Є βxy

Можно показать, что приведенный перечень ограничений является полным.

В произвольной сети из n узлов и m ветвей, ограничение (2) содержит m неравенств (по одному на ветвь), а ограничение (3) до (n-1)n неравенств (по одному на пучок каналов между парой узлов). Таким образом, линейная программа будет содержать всего n(n-1) + m ограничивающих неравенств.

Для упрощения учета ограничений (2) и (3) целесообразно несколько видоизменить структуру сети, введя фиктивные узлы и ветви. Фиктивный узел вводится для каждого отличного от нуля требования φkl. Каждый введенный фиктивный узел kl соединяется с существующим в сети узлом k, являющимся началом пучка каналов, и фиктивной ветвью βkl,k, емкость которой bkl,k =φkl. В этом случае система ограничений (2) становится однотипной с системой ограничений (3), а любой путь μj, связывающий между собой узлы k и l и используемый для передачи потока φkl, должен всегда проходить вначале по фиктивной ветви βkl,k от узла kl к узлу k, а дальше по действительным ветвям βpq Є μ. Поэтому в таблице путей для видоизмененной сети каждый путь будет дополнительно содержать фиктивный узел и фиктивную ветвь, соответствующую требованиям, которые могут быть удовлетворены по этим путям.

Одним из наиболее эффективных методов решения задач линейного программирования является симплекс-метод. Алгоритм симплекс-метода включает две основные операции: операции отбора ведущего элемента и операцию преобразования элементов симплекс-таблицы относительно выбранного ведущего элемента.

Ведущий элемент симплекс-таблицы лежит на пересечении ведущего столбца и ведущей строки. Ведущим выбирается столбец jо таблицы, которому принадлежит максимальная положительная величина коэффициента целевой функции, т.е.

сj = max[cj] > 0.
j

Ведущей выбирается строка iо таблицы, в которой отношение свободного члена bi к элементу ведущего столбца а > 0 является минимальным, т.е.

bio/aiojo = min[bi/aijo].
i

Элементы таблицы преобразуются по следующим правилам:

1. Все элементы аio ведущей строки io делятся на ведущий элемент, т.е.

а

ioj = аioj/аiojo.

2. Элементы a׳ij(i ≠ io) получаются путем вычитания из них соответственных элементов аioj ведущей строки, преобразованных в п.1 и предварительно умноженных на значение элемента аijo ведущего столбца в рассматриваемой i-й строке, т.е.

a

׳ij = аij - a׳ioj аijo.

Из п.2 следует, что в процессе преобразования будут изменяться элементы только тех строк, у которых элемент ведущего столбца аijo ≠ 0. В результате преобразования таблицы ведущий элемент будет равен 1, а все остальные элементы ведущего столбца будут равны 0.

Данный метод линейного программирования дает возможность получить оптимальный план распределения каналов.

Таким образом, используя методы линейного программирования, которые достаточно хорошо разработаны и широко используются для решения различного рода задач оптимизации, можно получить оптимальное распределение каналов. Однако необходимость производить каждый раз операции над всей симплекс-таблицей приводит к тому, что решать задачи с числом переменных больше десяти вручную практически невозможно.

1.2 Метод поочередного выбора

При увеличении числа узлов и усложнении конфигурации сети возрастают объем линейной программы и трудоемкость подготовки исходных данных, связанная с определением всех допустимых путей передачи между парами узлов сети.

Для получения плана распределения каналов в сети с большим числом узлов можно использовать более простые приближенные методы распределения каналов. Один из таких методов – метод поочередного (последовательного) выбора и занятия кратчайших по длине путей между парами узлов сети.

Распределение каналов методом поочередного выбора заключается в следующем.

Составляется таблица путей, выбирается пара узлов k и l сети, между которыми существует отличное от нуля требование на передачу потоков φkl > 0, выбирается кратчайший путь μi(kl) между указанной парой узлов и определяется емкость этого пути. (Если оптимизация распределения производится не по длине, а, например, по надежности, то выбирается самый надежный путь и определяется его емкость). Из величины требований φkl и емкости ветвей βij μi(kl) вычитается величина di = min[φkl,fi]. Затем выбирается следующая пара узлов, и процесс повторяется до тех пор, пока существует хотя бы одно φkl > 0 и, по крайней мере, один путь μi(kl) между выбранной парой узлов k и l сети с fi > 0.

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

1.3 Метод поочередного выбора путей с коррекцией

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

Метод поочередного выбора путей с коррекцией состоит из:

- выбора пути между парой узлов и определения его емкости;

- определения целесообразности занятия этого пути;

- определения необходимости и величины коррекции проведенного распределения.

Выбор пути между парой узлов и определение его емкости производятся так же, как и в описанном ранее методе поочередного выбора. Определение целесообразности занятия этого пути, необходимости и величины коррекции произведенного распределения осуществляется аналогично тому, как это делается в симплексном методе линейного программирования.

В методе поочередного выбора путей с коррекцией исходные данные представляются в виде матрицы емкостей ветвей, системы требований и таблицы путей для видоизмененной сети связи с учетом требований на передачу потоков.

Метод поочередного выбора с коррекцией, как и симплексный метод, требует создания начального допустимого плана распределения, в который входят m путей μ1, …, μm, соответствующих действительным и фиктивным ветвям сети. Емкость каждого из путей определяется емкостью соответствующей ветви сети, т.е. f1 = b1, f2 = b2, …, fm = bm. Пути μ1, …, μm образуют в таблице путей подтаблицу с единицами по главной диагонали. Ни один из n оставшихся в таблице путей μj (j = m + 1, …, m + n) не входит в начальный допустимый план распределения и, следовательно, все они имеют емкость fj = 0.

Целью распределения является получение максимальной суммарной емкости путей, используемых для удовлетворения требований на организацию пучков, поэтому целевая функция может быть представлена в виде

m+n

F = ∑ cifi.

i=1

Так как единица емкости любого пути, используемого для передачи потока, увеличивает на единицу емкость соответствующего пучка, то все коэффициенты сj (j = m + 1, …, m + n) целевой функции F равны единице.

Пути μ1, …, μm начального допустимого плана распределения не используются для организации пучков и поэтому коэффициенты сk , (k = 1, …, m) целевой функции F равны нулю, т.е.

m+n m m+n m+n

F = ∑ cifi = ∑ ckfk + ∑ cjfj = ∑ fj.

i=1 k=1 j=m+1 i=m+1

Метод поочередного выбора путей с коррекцией состоит в последовательной замене путей μk, (k = 1, …, m), входящих в начальный допустимый план распределения, путями μj, (j = m + 1, …, m + n) из таблицы путей. На каждом шаге может быть произведена замена только одного пути, емкость которого при введении нового пути обращается в нуль. Если при введении нового пути несколько путей исходного допустимого плана обращаются в нуль, то они должны быть выведены из плана на последующих шагах введением новых путей μj с fj = 0. Чтобы обеспечить удовлетворение требований при использовании минимального числа каналов в ветвях сети, на каждом шаге в план из таблицы путей должен вводиться самый короткий путь.

Целесообразность введения в план распределения выбранного пути определяется на каждом шаге при помощи относительных оценок сj. Относительные оценки для каждого из путей μj (j = m+1, …, m+n) определяются корректирующим вектором Р = (р1, …, рm), каждая компонента рj которого является симплекс - множителем или весом соответствующей ветви этого пути. Относительная оценка для произвольного пути μj, (j = 1, …, m+n) может быть получена из выражения

_ m

cj = cj - ∑aijpi ,

i=1

где cj – коэффициент при емкости fj в целевой функции F. (В рассматриваемом методе всегда для j = 1, …, m; cj =0, а для j = m+1, …, m+n; cj = 1); aij – значение элемента ij таблицы путей А, (aij = [0,1]).

На каждом шаге в план распределения вводится только тот путь μj, относительная

оценка которого , т.е. путь, для которого

m

∑aijpi < 1

i=1

(т.к. для j= m+1, …, m+n коэффициент cj = 1).

Вектор Р = (р1, …, pm) должен определяться на каждом шаге, поскольку его компоненты зависят от того, какие пути введены в план распределения. Компоненты вектора Р = (р1, …, рm) можно определить, используя свойство относительных оценок, состоящее в том, что ∙ fj = 0 для всех j = 1, …, m+n. Указанное свойство относительных оценок выполняется для всех путей μi, не вошедших в план распределения, так как у всех этих путей fi = 0. Для путей, вошедших в план распределения с fk > 0, условие = 0 может быть выполнено, только если . Поэтому для путей μk, (k = 1, …, m), входящих в функцию цели F c коэффициентом, ck = 0

,

откуда

а для путей μj, (j = m+1, …, m+n), входящих в целевую функцию F с коэффициентом cj = 1,

,

откуда

.

Выражения (а) и (б) составляют систему уравнений, позволяющую определять компоненты вектора Р = (р1, …, pm). Условие cj > 0 выполняется только, если все компоненты вектора pi > 0, поэтому появление отрицательной компоненты вектора р указывает на то, что полученный план распределения не является оптимальным и что путем его коррекции можно увеличить значение целевой функции F.

Коррекция заключается в возвращении выведенного ранее из начального допустимого плана пути μi, компонента вектора Р которого pi < 0, перераспределении емкостей путей, введенных в план, и выведении одного из путей μk начального плана, емкость которого в процессе коррекции уменьшилась до нуля.

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

1.4 Параллельный метод

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

Поясним на примере этот метод.

Требования задаются числом каналов между различными парами узлов, при этом необходимо, чтобы для удовлетворения требований было использовано минимальное число каналов первичной сети и образован план распределения каналов вторичной некоммутируемой сети.

Исходные данные:

Заданы – структура первичной сети в виде графа и пучков каналов, например, такая, как представлена на рисунке 1, а также матрица требований (или отдельные ее ненулевые элементы).

Рисунок 1

Пусть необходимо, чтобы между узлами 1-3, 2-4, 3-6 и 5-6 в путях передачи информации было соответственно: φ13

=18; φ36 =16; φ24 =12; φ56 =16 каналов. Тогда матрица требований имеет вид:

Таблица 1.4.1

| 1 | 2 | 3 | 4 | 5 | 6
1 | 0 | 0 | 18 | 0 | 0 | 0
2 | 0 | 0 | 0 | 12 | 0 | 0
3 | 18 | 0 | 0 | 0 | 0 | 16
4 | 0 | 12 | 0 | 0 | 0 | 0
5 | 0 | 0 | 0 | 0 | 0 | 16
6 | 0 | 0 | 16 | 0 | 16 | 0

Число каналов первичной сети задано как веса соответствующих ветвей на графе. По этим данным можно простроить матрицу емкостей ребер.

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

| 1 | 2 | 3 | 4 | 5 | 6
1 | 0 | 20 | 0 | 20 | 20 | 0
2 | 20 | 0 | 20 | 0 | 0 | 20
3 | 0 | 20 | 0 | 20 | 20 | 0
4 | 20 | 0 | 20 | 0 | 0 | 20
5 | 20 | 0 | 20 | 0 | 0 | 0
6 | 0 | 20 | 0 | 20 | 0 | 0

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

Процесс повторяется до тех пор, пока все φi,j не будут удовлетворены или дальнейшее удовлетворение требований станет невозможным.

Рассмотрим пример сети на рисунке 1 с матрицей требований (1) и матрицей емкостей ребер (2).

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

2. Из рис. 1 определяем кратчайшие пути:

μ

11,2,3; μ21,4,3; μ31,5,3.

3. Определяем число каналов, потребное для обслуживания данного потока, распределяя общее потребное число каналов равномерно на три пути:

С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. Подсчитываем для каждого ребра bi,j его емкость, полученную в результате загрузки в соответствии с идеальными ПРК, и в графе ∆Сi,j ставим со знаком “+” то число каналов, которое осталось не загруженным (ненасыщенные ребра) и со знаком “-” - число каналов, на которое загрузка ребра в соответствии с идеальным ПРК превышает заданное число каналов в ребре. Поскольку в строке ∆Сij отмечены перегруженные ветви (b2,3 и b3,4), то идеальный ПРК недопустим.

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

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

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

9. Путь между парой 1-3, содержащей ненасыщенные ребра, найден – это путь С3(1-3). Путь С2(1-3) использовать для перераспределения нельзя, так как он содержит перенасыщенное ребро b3,4. Определяем величину перераспределяемой с пути С1(1-3) на путь С3(1-3) емкости. Так как в ребре b2,3 следует уменьшить число требований на 4, с тем, чтобы его емкость не превышала заданную, то во всем пути С1(1-3) – ребрах b1,2 и b2,3 – число требований следует уменьшить на 4, а в пути С3(1-3) – ребрах b1,5 и b3,5 – увеличить на 4. Старые значения (они в таблице 3 указаны в скобках) исправляем на новые. Новые значения емкостей проставлены сверху. В строке ∆С'ij отмечены новые величины ∆Сij.

10. ПРК остался недопустимым, так как перенасыщена ветвь b3,4. Повторяем действия пп. 7, 8, 9. В результате находим, что для пары 2-4 существует путь С1(2-4), который проходит по ненасыщенным ребрам b1,2 и b1,4. В пути С2(2-4) емкости ребер уменьшаем на 4, а в пути С1(2-4) – увеличиваем. В строке ∆С''ij отмечаем новые величины ∆Сij.

Данный ПРК допустим. Полученные элементы матрицы С определяют искомый ПРК.

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

правая кнопка мыши, удалить ячейки, удалить всю строку

План распределения каналов

Таблица 1.4.3

Номер пары УК | Номер пути |
b12 | b14 | b15 | b23 | b26 | b34 | b35 | b46
1-3 | С1 | 2 (6) |  |  | 2 (6) |  |  |  |
С2 |  | 6 |  |  |  | 6 |  |
С3 |  |  | 10 (6) |  |  |  | 10 (6) |
3-6 | С1 |  |  |  | 8 | 8 |  |  |
С2 |  |  |  |  |  | 8 |  | 8
2-4 | С1 | 10 (6) | 10 (6) |  |  |  |  |  |
С2 |  |  |  | 2 (6) |  | 2 (6) |  |
5-6 | С1 | 4 |  | 4 |  | 4 |  |  |
С2 |  |  |  | 4 | 4 |  | 4 |
С3 |  | 4 | 4 |  |  |  |  | 4
С4 |  |  |  |  |  | 4 | 4 | 4
| ∆Сij | +4 | +4 | +6 | -4 | +4 | -4 | +6 | +4 ПРК недопустим
∆С'ij | +8 | +4 | +2 | 0 | +4 | -4 | +2 | +4 ПРК недопустим
∆С''ij | +4 | 0 | +2 | +4 | +4 | 0 | +2 | +4 ПРК допустим

Для проведения лабораторной работы будет использован простой и наглядный параллельный метод распределения каналов, позволяющий получить близкий к оптимальному (и часто оптимальный) план распределения каналов.

назад