И синтеза структуры сетей связи

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

• тип сети;
• вид задачи: задача анализа качества работы или задача синтеза структуры;
• подтип по признаку одновременности требований;
• надежностный подтип;
• технологический подтип;
• вид критерия (критерия качества для задач анализа, целевого критерия для задач синтеза);
• вид ограничения (или комбинации ограничений).

Как и следовало ожидать, тип сети здесь является главным классификационным признаком ввиду его определяющего влияния на постановку и методы решения задач анализа и синтеза.

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

 

12.2 Элементы математического аппарата анализа и синтеза

Графы, их свойства и способы представления

При решении задач анализа и синтеза сетей связи различных типов широко используется вспомогательный теоретический объект, называемый конечным графом. Рассмотрим некоторые важные для дальнейшего свойства графов и стандартные методы работы с ними.
Конечным графом G принято называть конечный набор n узлов А={а₁.... ai,, аn}, некоторые из которых попарно соединены ребрами {ветвями), образующими множество В. Любых два узла a_i,a_jєA,;i≠j могут быть соединены некоторым числом х≥0 ориентированных и неориентированных ребер, образующих пучок {a_ia_j}. Неориентированное ребро будет обозначаться через , ориентированное от a_i к a_j —символом ; символ (a_ia_j) без стрелки будет означать, что наличие или отсутствие ориентации несущественно. Граф называется простым (некратным) и обозначается PG, если для любых a_i, a_j є A пучок {a_ia_j} содержит не более одного ребра каждого из трех возможных способов ориентации, и кратным, если это условие не выполняется. В частных случаях, когда все ребра графа ориентированы либо все ребра не имеют ориентации, граф называется, соответственно, ориентиро-ванным или неориентированным и обозначается символом или .В против-ном случае граф называется смешанным. Ориентированный граф называется симметрическим, если в нем каждому ребру сопутствует ребро встречной ориентации, и антисимметрическим, если ребра встречной ориентации отсутствуют. Ребра называются инцидентными узлу a_i, ребро - исходящим из a_i, a - входящим (заходящим) в a_j. Отсюда возникают следующие локальные конфигурационные характеристики графа, относящиеся к отдельному узлу a_i: число ребер, инцидентных узлу ai, называется его рангом (степенью), а числа ориентированных ветвей, исходящих из a_i и входящих в него, — соответственно полурангами (полустепенями) исхода и захода.
Цепью, соединяющей узлы a_i и a_i, называется последовательность ветвей (a_i a_k), (a_ka_l)… (a_ra_j) не обязательно согласованной ориентации. Путем μ_ij из узла a_i в узел a_i называется цепь, соединяющая a_i и a_j, в которой ориентация всех ориентированных ветвей соответствует направлению движения от a_i к a_j. Путь называется ациклическим (самонепересекающимся), если через любой узел сети он проходит не более одного раза. Будем говорить, что a_i и a_j связаны, если одновременно существуют пути из узла a_i в узелa_j и из a_j в a_i. Граф или его компонент (подграф) называется связным, только если все его узлы попарно связаны, в противном случае имеет место несвязность. Сечением или разрезом графа (сети связи) называется минимальная совокупность ветвей (ребер), разделяющих граф (сеть) на две несвязные между собой части (под-

сети, подграфа). Под емкостью сечения понимается суммарная емкость входящих в

него ветвей (ребер). Сечение с минимальной емкостью называется минимальным сечением. Для определения минимального сечения используются методы исследования потоковых графов.
Конфигурация простого неориентированного или ориентированного графа может быть представлена булевской матрицей размера n*n (n - число узлов графа), называемой матрицей смежности. Ее строки и столбцы соответствуют n узлам из множества A. В случае графа элемент этой матрицы β_ij принимает значение 1 только при наличии ребра ; для графа при наличии ребра (а_iа_j) имеем

β _ij = β_ji =1. При отсутствии ребра (а_iа_j) - β_ij принимает значение 0. Иногда вершинам и ребрам графа G приписываются числа, называемые весом. В зависимости от решаемой задачи в качестве весов может использоваться: длина; стоимость; пропускная способность, выраженная числом каналов или допустимой скоростью передачи информации; пропускаемая нагрузка (например, в Эрлангах) при заданном качестве обслуживания; время задержки передаваемого сообщения и т.п. В ряде случаев в качестве весов могут быть использованы: вероятности потерь вызова, надежностные показатели (например, коэффициент готовности) и т.п. Если веса присваиваются только ребрам графа, то граф называется графом c взвешенным ребрами. Если веса присваиваются только вершинам, то граф называется графом с взвешенными вершинами. Если веса присваиваются и ребрам и вершинам, то граф называется просто взвешенным графом.

Для алгебраического представления графов удобно использовать следующие основные матрицы:

· Структурная матрица B графа G c n узлами. Это квадратурная матрица порядка n, в которой каждому узлу a_i соответствует i – ая строка и i- ый столбец: B = || b_ij ||. Вхождения b_ij определяются по следующему правилу:

1 при i = j

b_ij = b_ij в случае, если есть непосредственная связь от узла a_i к узлу a_j.

0, если такой непосредственной связи нет.

· Матрица длин ребер L = || l_ij ||, где l_ii = 0; l_ij – длина ребра от узла a_i до узла a_j; l_ij = ∞,если между a_i и a_j нет ребра.

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

· Матрица прямых каналов U = || u_ij ||, вхождение которой u_ij – число каналов, начинающихся в узле a_i и кончающихся в узле a_j независимо от того, через какие еще транзитные или сетевые узлы эти каналы проходят. Такая матрица уже характеризует возможности сети по установлению связи, если считать, что узлы являются коммутационными.

· Матрица надежности P = || p_ij ||, где p_ij – вероятность нахождения элемента сети в работоспособном состоянии.

· Матрица стоимостей Ц = || ц_ij ||, где ц_ij – стоимость ребра между узлами a_i и a_j, ц_ii – стоимость узла. В стоимость ребра может быть включена стоимость каналообразующей, а иногда и части коммутационной аппаратуры узлов a_i и a_j.

Используя характеристики ребер и вершин графа, можно получить соответствую-щие характеристики для отдельных путей. Для пути μ_st = {b_sl,b_lm, …,b_pt} между вершиной s и t, содержащего ребра b_sl,b_lm, … и b_pt, в зависимости от поставленной задачи, могут быть получены различные параметры. Например:

- Ранг r (μ_st) пути - число входящих в него ребер.

- Длина пути l (μ_st) – сумма длин всех ребер, образующих данный путь.

l (μ_st) = ∑ l_ij.

b _ij Є μ_st

- Пропускная способность пути c(μ_st) при использовании сети для передачи инфор-мации только от узла s к узлу t определяется наиболее узким местом – минимальной пропускной способностью ребер, образующих путь.

c(μ_st) = min c(b_ij).

b_ij Є μ_st

 

- Под пропускной способностью сечения понимается суммарная емкость входящих в него ребер.

Используя теорию графов можно решить множество весьма важных сетевых задач. К ним можно отнести:

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

· Определение самых коротких по длине или самых надежных путей между любыми узлами графа сети.

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

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

· Решение задачи коммивояжера, что позволяет оптимизировать первичные сети кольцевой структуры.

· Определение максимальной пропускной способности некоммутируемых и коммутируемых сетей и т.п.