Проект ГТС на базе систем передачи SDH (стр. 6 из 8)
Математическая постановка задачи. Задан граф G =(X, U), где X- множество вершин, в которых заканчиваются ситуационные трассы; U – множество ребер, соответствующих участкам ситуационных трасс.
Х¢ÍХ – подмножество вершин, в которых расположены телефонные станции. Lij- длина участка трассы uij. Требуется найти цикл С в графе G, проходящий по всем вершинам множества Х¢ и имеющий минимальную длину:
. 
Анализ алгоритмов. Рассмотрим задачу, когда Х¢ = Х. В этом случае требуется построить кольцо, проходящее по всем вершинам, то есть, предполагаем, что во всех вершинах расположены станции. Эта задача известна в теории графов как «Задача коммивояжера». Она принадлежит классу NP – трудных задач, для которых не существует точных эффективных алгоритмов. Поэтому задачу решают приближенными, эвристическими алгоритмами с вычислением нижней и верхней оценок решения.
В случае Х¢Ì Х наша задача еще более усложняется. Опишем метод, с помощью которого она может быть сведена к «Задаче коммивояжера».
Построение аппроксимирующего графа.
Шаг 1. Вычислить по алгоритму Дейкстры кратчайшие пути между всеми парами вершин из множества Х¢. Алгоритм реализуется следующим образом:
· выбираем вершину (ОТС) и находим вершины, смежные с ней. Присваиваем каждой найденной вершине пару чисел, состоящую из номера корневой (выбранной) и длины соответствующего ребра. Для остальных вершин графа сопоставляют пару (0, ¥);
· из множества неотмеченных вершин найдем вершину с минимальным весом, включаем ее в дерево кратчайших путей и отмечаем ее. Далее уже для вновь отмеченной вершины находим смежные с ней. Найденной вершине (смежной) присваиваем вес минимальный из двух возможных: либо уже существующий, либо вес, полученный из суммы длины ребра с весом предыдущей вершины; так необходимо повторять до тех пор, пока вершины не будут просмотрены и отмечены.
Шаг 2. Построить полный граф G¢ = (X¢, U¢), у которого множество вершин совпадает с множеством вершин X¢. Множество ребер соединяет две пары вершин. Для каждого ребра uij положить его вес равным длине кратчайшего пути из Хi в Хj в исходном графе G, полученном на шаге 1.
Шаг 3. На полученном графе можно решать задачу коммивояжера, т. е. найти цикл минимального веса, проходящий по всем вершинам X¢.
Шаг 4. Получив структуру цикла в графе G¢, выделить кратчайшие пути в графе G, соответствующие ребрам полученного цикла.
Методы решения «Задачи коммивояжера».
Рассмотрим алгоритм получения верхней и нижней оценок для «Задачи коммивояжера» (ЗК).
Нижней оценкой для ЗК является решение, полученное с помощью алгоритма Прима-Краскала, в результате которого строится кратчайшее остовое дерево (КОД). Длина искомого цикла не может быть меньше суммарного веса КОД.
Верхняя оценка цикла в ЗК может быть получена с использованием стратегии «иди в ближайший». Опишем подробнее этот алгоритм.
Шаг 1. Выбрать исходную вершину и считать ее текущей вершиной строящегося нового цикла.
Шаг 2. Найти ближайшую вершину к текущей вершине относительно длины ребра и сделать ее текущей. Увеличить вес цикла на длину ребра.
Шаг 3. Если не все вершины включены в цикл, то шаг 2 повторяется. Если в цикл включены все вершины графа, то запомнить суммарный вес ребер, включенных в цикл. Если вес полученного цикла меньше предыдущего решения, считать его наилучшим.
Шаг 4. Если не все вершины графа просмотрены как исходные вершины циклов, то перейти на шаг 1, иначе цикл, имеющий минимальный вес является верхней оценкой для ЗК.
Шаг 5. Полученное кольцо минимальной длины вложить в структуру ситуационных трасс первичной сети. При этом ветви кольца не должны содержать элементы структуры ситуационных трасс более одного раза.
Используя данные задания на выполнение курсового проекта и изложенную методику, необходимо определить длину оптимального кольца по структуре ситуационных трасс города.
Вычислим по алгоритму Дейкстры кратчайшие пути между всеми парами АТС.
А)Кратчайшие пути от РАТС1 до всех станций данной сети
Б)Кратчайшие пути от РАТС2 до всех станций данной сети
В)Кратчайшие пути от РАТС3 до всех станций данной сети
Г)Кратчайшие пути от РАТС4 до всех станций данной сети
Д)Кратчайшие пути от РАТС5 до всех станций данной сети
Е)Кратчайшие пути от АМТС до всех станций данной сети
Полученные данные сведем в таблицу 4.2.1.
Таблица 4.1 Кратчайшие пути между АТС
| ОТС1 | ОТС2 | ОТС3 | ОТС4 | ОТС5 | АМТС | |
| ОТС1 | - | 8 | 12 | 16 | 28 | 12 |
| ОТС2 | 8 | - | 12 | 16 | 20 | 4 |
| ОТС3 | 12 | 12 | - | 4 | 24 | 8 |
| ОТС4 | 16 | 16 | 4 | - | 20 | 12 |
| ОТС5 | 28 | 20 | 24 | 20 | - | 16 |
| АМТС | 12 | 4 | 8 | 12 | 16 | - |
Используя выбранные кратчайшие пути, построим граф и решим для него «Задачу коммивояжера».
Длина оптимального цикла равна 64.
Нанесем полученное кольцо на сетку улиц города (рисунок 4.2.1) в соответствии с выбранными кратчайшими путями (рисунок 4.2.2 – 4.2.7) получим рисунок 4.2.9.
5 Выбор типа синхронного транспортного модуля
5.1 Расчет числа ИКМ трактов передачи
В качестве каналов доступа узлов коммутации (ОТС, АМТС, УСС) к первичной сети, реализованной на базе SDH, будем использовать плезиохронные системы передачи ИКМ-30 (стандарт Е1).
Для расчета количества цифровых потоков типа Е1, необходимых для реализации пучков соединительных линий (каналов) между различными станциями сети, следует учитывать:
1) число СЛ в направлениях связи;
2) тип используемых СЛ (односторонние или двусторонние);
3) тип используемой системы сигнализации.
При использовании односторонних линий и децентрализованной системы сигнализации (2ВСК, «2 из 6» и т. д.), для расчета требуемого числа потоков Е1 от i-ой станции к j-ой станции, воспользуемся формулой:
, где 
- требуемое число цифровых потоков Е1 от i-ой станции к j-ой станции; 
- число соединительных линий (каналов) между i-ой и к j-ой станциями, ( 
); 
- знак целой части числа.При использовании двусторонних пучков и централизованной системы сигнализации (ОКС №7) воспользуемся формулой:
.Эта формула справедлива, если
> 60 каналов. В противном случае необходимо использовать предыдущую формулу, заменив на 
.Результаты расчета числа цифровых потоков Е1 заносятся в таблицу 5.1.1.
Таблица 5. 1.Число ИКМ трактов передачи цифровых потоков Е1 между станциями сети
| РАТС1 | РАТС2 | РАТС3 | РАТС4 | РАТС5 | АМТС | УСС | |
| РАТС1 | - | 7 | 7 | 8 | 6 | 7 | 1 |
| РАТС2 | - | - | 6 | 9 | 4 | 4 | 2 |
| РАТС3 | - | - | - | 9 | 7 | 4 | 2 |
| РАТС4 | - | - | - | - | 10 | 6 | 2 |
| РАТС5 | - | - | - | - | - | 5 | 2 |
5.2. Выбор типа модуля STM.
Синхронный транспортный модуль STM- это информационная структура, используемая для осуществления соединений в SDH. Состоит из информационной (полезной) нагрузки и секционного заголовка, объединенных в блочную цикловую структуру с периодом повторения 125 мкс. Эта информация соответственно подготовлена для последующей передачи со скоростью синхронизированной с сетью. Базовый синхронный модуль STM-1 позволяет собрать потоки со скоростью 2Мбит/с в один модуль и передавать их со скоростью 155 Мбит/с. STM-1 позволяет объединить 63 потока Е1. Каждому 2 Мбитному потоку соответствует свой адрес выделения.
Модуль STM-4 обеспечивает передачу 252 цифровых потоков Е1 со скоростью 622 Мбит/с. Модуль STM-16 позволяет объединить 1008 цифровых потоков типа Е1 и обеспечивает их передачу со скоростью 2.5 Мбит/с.