4.3. СИНТЕЗ СТРУКТУРЫ СЕТИ

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

Синтез структуры сети по детерминированным параметрам живучести

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

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

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

где , — степень узла. В таком прафе для четных узел соединен с узлом причем

При нечетном узел соединяется также с узлом.

Структуры сетей, соответствующие максимально связным реберно-критическим графам, строятся следующим образом [46]. Все узлы сети нумеруются и размещаются по окружности в соответствии с присвоенными номерами. Затем каждый узел соединяется с (при четном ) и (при нечетном ) соседними узлами. Если нечетно, то каждый узел также соединяется с наиболее удаленным от него узлом, т. е. узел соединяется с узлом. Граф сети, построенный по изложенной методике для изображен на рис. 4.4.

Рис. 4.4

Рис. 4.5

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

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

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

Сеть, синтезированная на основе данного правила для представлена на рис. 4.5 и имеет диаметр сети на рис.

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

где — множество наборов по узлов; — число ребер в подграфе включающем узлов одного из наборов, принадлежащих

В соответствии с (4.33) сеть на рис. 4.4 имеет а сеть на рис. узлов. Таким образом, по данному критерию вторая структура более живуча.

Задача синтеза структуры по детерминированным показателям может быть расширена, если учитывать:

различия в требованиях по связности для различных пар узлов;

затраты на построение отдельных линий связи;

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

Такое расширение задачи приводит к значительному усложнению методов синтеза структуры.

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