4 Задачи синтеза: а) алгоритм структурного синтеза; б) синтез централизованных сетей; в) синтез втричных сетей.
4 Синтез мәселелері: а) құрылымдық синтез алгоритмі; б) орталықтандырылған желілерді құру; в) екінші реттегі желілерді құру.
Синтез структуры сети является одной из основных задач проектирования сетей связи, при этом необходимо выбрать число и местоположение узлов, число каналов или тип линий, соединяющих отдельные пункты с соблюдением заданных ограничений и технических требований к качеству связи при минимальных затратах.
В задачах синтеза сеть будем представлять:
-
набором оконечных пунктов и узлов 
-
совокупностью линий связи с указанием
их ориентации 
и
необходимыми параметрами линий: емкостью
в числе стандартных каналов 
;
надежностью и т. д.
Требуется определить структуру сети таким образом, чтобы удовлетворить потребность в связи всех пар пунктов при минимальных затратах.
В общей постановке задача чрезвычайно сложна, поэтому разработан ряд более простых постановок и методов их реализации.
Синтез централизованных сетей
Централизованной называется сеть, если она представлена двумя иерархическими уровнями:
-
терминалами 
,
которые могут подключаться к удаленному
концентратору или непосредственно к
центральной ЭВМ;
-
удаленные концентраторы 
,
которые соединяются с центральной ЭВМ.
Итак, в настоящей задаче заданными являются:
-
множества терминалов 
и
концентраторов 
и ЭВМ -
;
-
стоимость линий связи, заданных матрицей
стоимости 
;
-
стоимость создания концентраторов 
.
Определить:
– схему
подключения терминалов к концентраторам
или ЭВМ, количество и расположение
задействованных концентраторов,
стоимость сети, учитывая, что каждый
терминал
может
быть подключен только к одному
концентратору 
,
а каждый концентратор может быть соединен
только с тем количеством терминалов,
которое не превышает пропускной
способности 
.
Введем обозначения:
переменная
означает
наличие связи
с
,
а 
-
отсутствие связи.
Будем называть концентратор открытым, если к нему подключен хотя бы один терминал, в противном случае – закрытым. Введена переменная
,
если
-
открыт
,
если
-
закрыт
Математическая модель задачи будет иметь вид
при ограничениях
Задача представлена целочисленной (ноль-единичной) моделью линейного программирования.
Для данной модели разработано большое количество приближенных методов, т. к. получение точного решения весьма трудоемко.
Задача синтеза вторичных сетей
Задача состоит в том, чтобы на заданной первичной сети построить пучки каналов, отвечающие определенным требованиям. Она называется задачей распределения каналов некоммутируемой сети. Для её решения выбираются пути передачи, в которых с помощью долговременных соединений на узлах сети образуются пучки соединительных линий (прямых каналов).
Задача.
Дана первичная сеть, структура которой представлена графом
Задана
емкость каждой линии первичной сети
(в виде матрицы емкостей), иногда – их
длина 
или
стоимость 
.
Для некоторого набора корреспондирующих пар заданы величины требуемых пучков каналов.
.
Построить план распределения каналов вторичной сети, отвечающий определенным технологическим требованиям.
План
– это набор путей для каждой
корреспондирующей пары 
и оптимальное число каналов в каждом пути
Требования
1. Общее число задействованных каналов должно быть минимально (минимизироваться может длина каналов или их стоимость).
Условие
1 – это целевая функция задачи. Пусть
-
ранг пути 
,
а 
-
число каналов в нем.
Тогда минимизация числа каналов выразится формулой
минимизация длины
минимизация стоимости
2. Каждая корреспондирующая пара обеспечена требуемым числом каналов
3.
Для любой ветви 
суммарная
емкость всех путей, содержащих эту
ветвь, не может быть больше емкости
ветви
