Каналы связи между городами

Рис 1. Регион 1 до оптимизации

Рис 2. Регион 1 после оптимизации.

Рис 3. Регион 2 до оптимизации.

Рис 4. Регион 2 после оптимизации

Рис 6. Регион 3 после оптимизации

3.3. ПРОЕКТИРОВАНИЕ МЕЖРЕГИОНАЛЬНОЙ ГОРИЗОНТАЛЬНОЙ СЕТИ

При проектировании горизонтальной сети я основывался на заданных критериях:

- тип проектируемой топологии: оптимальная;

- критерий оптимизации: общая стоимость сети;

- ограничения на проектирование:

14 секунд: - максимальное время задержки;

1 секунда: - среднее время задержки

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

Для синтеза оптимальной кольцеобразной сети используется задача коммивояжера. Суть данной задачи заключается в том, что коммивояжер должен выехать из одного города, побывать во всех остальных по одному разу и вернуться обратно. Задача заключается в определении последовательности объезда городов, при котором коммивояжеру требуется проехать наименьшее суммарное расстояние, при этом предполагается, что расстояние до каждой пары городов известно. Рис.7.

Рис. 7. Топология «Кольцо»

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

Рис.8. Топология «Дерево»

Задача синтеза оптимальной звездообразной сети по критерию минимальной стоимости заключается в переборе всех возможных вариантов звездообразных сетей и выборе варианта с минимальной стоимостью. Рис.9

Рис. 9. Топология «Звезда»

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

- решить задачу коммивояжера, в результате которой будет получена минимальная связная кольцеобразная сеть;

- задать допустимое число переприемов в маршруте;

- решить задачу маршрутизации, если число «плохих» маршрутов равно нулю – то закончить;

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

- добавить очередную минимальную неиспользованную дугу в решение;

- решить задачу маршрутизации;

- если добавление данной дуги в решение привело к уменьшению количества «плохих» маршрутов, то оставить дугу в решении, иначе исключить эту дугу из решения;

- если число «плохих» маршрутов равно нулю, то закончить, иначе перейти к сортировке.

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