Оптимизация структуры сетей связи

Министерство образования и науки Российской Федерации Пермский национальный исследовательский политехнический университет Кафедра автоматики и телемеханики Сети связи расчетно-графическая работа

«Оптимизация структуры сетей связи»

Вариант N=8 M=4

Работу выполнил Студент гр. ТКбз-09

Волков А. В Проверил доцент кафедры АТ Байдаров А.А.

Пермь, 2013

Задание Подготовка исходных данных

1. Расчет сетей с минимальной протяженностью ветвей

1.1 Определение структуры сети с МПВ

1.2 Расчет суммарной протяженности сети с МПВ

1.3 Построение модели структуры сети с МПВ

1.4 Вывод

2. Расчет сетей связи с минимальной протяженностью связей.

2.1 Исходные данные

2.2 Расчет суммарной протяженности связей при n=nmax=28

2.3 Расчет суммарной протяженности связей при n=nmax-1=27

2.4 Расчет суммарной протяженности связей при остальных n

2.5 Построение модели структуры сети с МПС при n=nmin =7

2.6 Вывод

3. Расчет сети с МКЗ

3.1 Исходные данные

3.2 Расчет суммарных капитальных затрат

3.3 Построение модели структуры сети с МКЗ:

3.4 Вывод

4. Заключение

5. Список используемой литературы Приложение 1. Расстояние между пунктами сети Lij

Приложение 2. Требуемое число каналов между пунктами сети Vij

Приложение 3. Значения КЗ кан.-км кабельной линии связи при различном числе каналов Приложение 4. Графики зависимостей Приложение 5. Модель структуры сети соединении станций по принципу «каждая с каждой» .

Сеть электросвязи можно отвести к тем большим системам, для которых пока ещё не удалось дать корректное математическое описание во всем многообразии ее параметров и критериев. Поэтому особую важность приобретает освоение навыков моделирования структуры сети, отвечающей тем или иным требованиям, выдвигаемым в конкретных условиях. Например, при проектировании зоновых сетей связи в районах Крайнего Севера, вечной мерзлоты основным становится требование обеспечения минимальных земляных работ, так как затраты на этот вид работ определяют общие капитальные затраты на создание сети. Учет этих требований приводит к созданию модели структуры сети, которая имеет минимальную суммарную протяженность всех ветвей.

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

В общем же случае следует стремиться создать сеть такой структуры, которая удовлетворяла бы потребности в связи при минимальных затратах на ее создание и эксплуатацию. Выбор наилучшего из всего множества вариантов схем сети представляет весьма трудоемкую задачу. Это объясняется тем, что количество различных структур сети при числе станций N может быть оценено как 2N!/(N-2)!2. Так, например, при числе станций N = 10 выбирать пришлось бы из более чем 1 000 000 различных структур сети.

Целью работы является освоение методики и алгоритмов построения сетей связи с:

1) минимальной протяженностью ветвей (МПВ);

2) минимальной протяженностью связей (МПС);

3) минимальными капитальными затратами (МКЗ).

Задание

Подготовка к работе

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

2. Подготовить индивидуальные исходные данные, используемые при расчете на ЭВМ.

3. Определить максимальное nmax и минимальное nmin число магистралей.

4. Начертить блок-схемы и уметь объяснить алгоритмы построения сети с МПВ, МПС, МКЗ.

Порядок выполнения задания

1. Определить структуру сети с МПВ (т.е. соединение каких станций обеспечит выполнение заданного условия).

2. Рассчитать суммарную протяженность ветвей сети с МПВ.

3. Рассчитать суммарную протяженность ветвей сети с МПВ при заданном их числе.

4. Рассчитать суммарную протяженность ветвей сети при соединении станций по принципу «каждая с каждой».

5. Рассчитать суммарную протяженность связей сети, обладающей МПС.

6. Рассчитать суммарную протяженность связей сети, обладающей МПС при заданном числе ветвей сети n=nmax-R.

7. Определить структуру сети с МКЗ (т.е. соединение каких станций сети обеспечит заданное условие). Рассчитать сумму капитальных затрат на создание такой сети.

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

9. Рассчитать суммарные капитальные затраты на сеть связи с МКЗ при заданном числе ветвей сети n=nmax-R.

Результаты работы

1. Начертить модели структур сети с МПВ, МПС, МКЗ. Модели структур вычерчиваются без учета масштаба расстояний между станциями на сети.

2. Построить графики зависимостей;

суммарной протяженности ветвей сети от числа ветвей (n);

суммарной протяженности связей от n,

суммы капитальных затрат на сеть от числа ветвей сети n.

3. На основании сравнения полученных структур сети и построенных зависимостей сделать выводы о соответствии полученных структур сетей со структурами, имеющими МПВ, МПС и МКЗ.

Подготовка исходных данных

Номер по журналу M=4, число станций сети N=8.

Из таблицы приложения 1 выписываем матрицу связности L. Матрица симметричная, поэтому можно работать только с верхней половиной матрицы. Элементы матрицы представляют собой протяженности ветвей между парами узлов (станций).

Из таблицы приложения 2 составляем матрицу нij :

Матрица емкости сети V получается из матрицы нij сложением числа каналов нij +нji, то есть чисел симметричных относительно главной диагонали матрицы:

Из таблицы приложения 3 и на основании матрицы V получаем матрицу капитальных затрат:

1. Расчет сетей с минимальной протяженностью ветвей

Структура сети с минимальной протяженностью ветвей (МПВ) соответствует такой сети, в которой сумма длин ветвей минимальна. С точки зрения теории сетей связи сеть с МПВ — это экстремальное полное собственное дерево, для построения которого используется метод Прима.

Алгоритм построения сети с МПВ:

· Записывается матрица связности L;

· Выделяют в каждой строке ветвь наименьшей длины. Следует учитывать, что матрица симметричная и одну и ту же ветвь, встречающуюся в двух строках, можно использовать для сети лишь однажды;

· Наносят на схему наименьшую ветвь из выделенных;

· Из оставшихся выделенных ветвей снова ищут наименьшую, но позволяющую связать один из уже соединенных узлов с еще не имеющими связей;

· Наносят на схему сети ветвь, найденную в предыдущем пункте;

· Проверяют, все ли узлы соединены в сеть.

1.1 Определение структуры сети с МПВ

Сеть с МПВ состоит из ветвей 1−3; 2−3; 3−5;4−5; 5−7; 6−7; 5−8

1.2 Расчёт суммарной протяженности сети с МПВ:

1.3 Построение модели структуры сети с МПВ

Соединяем узлы в следующем порядке: 1−3; 2−3; 3−5; 5−4; 5−7; 5−8; 6−7.

Рис. 1.

Модель структуры сети с МПВ

1.4 Вывод

С увеличением количества ветвей суммарная протяженность ветвей увеличивается. В нашем случае сеть с МПВ состоит при n=nmin = 7 из ветвей: 1−3; 2−3; 3−5; 5−4; 5−7; 5−8; 6−7.имеем сеть с наименьшей протяженностью ветвей. Протяженность ветвей 167 км. При n = nmax = 28 протяженность ветвей максимальна и составляет 1708 км. График зависимости суммарной протяженности ветвей от числа ветвей представлен приложении 4

2. Расчет сетей связи с минимальной протяженностью связей

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

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

Суммарная протяженность связей каждого варианта построения сети определяется по формуле:

сеть ветвь канал станция где lij нij — протяженность пути между пунктами i и j, состоящий из p ветвей нij — требуемое число каналов между пунктами i и j,

n — число ветвей связи для данного варианта построения сети.

Алгоритм построения сети с МПС:

· Ввод исходных данных: N, L, V;

· Расчет значений:

· Расчет

· Расчет? Lсвij при изъятии произвольной ветви i-j;

· Выбор минимального значения? Lсвij и фиксация обходного пути для каналов изъятой ветви i-j;

· Перераспределение элементов в матрицах L и V, связанное с отсутствием изъятой ветви i-j и появлением дополнительного числа каналов Vij в ветвях обхода.

· Расчет

· Присвоение индексу n значения n ?1.

· Проверка значения n: при n = nmin — окончание расчетов.

Таким образом, сеть, имеющая наименьшую протяженность связей, будет образована путем соединения всех пунктов по принципу «каждый с каждым"(см. Приложение 5). Для такой сети потребуется nmax ветвей. При всех других схемах суммарная протяженность связей будет возрастать.

Максимальную протяженность связей будет иметь схема сети с МПВ — «дерево».

2.1 Исходные данные

N = 8;

;

2.2 Расчет суммарной протяженности связей при n=nmax=28

2.3 Расчет суммарной протяженности связей при

n=nmax-1=27:

Возможны следующие обходы:

Кратчайший обходной путь (3−2;2−6;6−7;7−4)без ветви 3−4 дает

?Lсв min = 330 * (116 — (15 +45+19+ 37) = 0 кан.-км Произведем перераспределение каналов в матрицах V и L (? — изъятая ветвь, соединение между парой узлов отсутствует.):

Рассчитаем суммарную протяженность связей при n=nmax=28−1=27

2.4 Расчет суммарной протяженности связей при остальных n

Аналогично рассчитываем протяженность связей для n = nmax ?2=26, n = nmax ?3=25 и т. д. до тех пор, пока n не станет равным n = nmin =7. Результаты представлены ниже в таблице 1.

Таблица 1

Зависимость суммарной протяженности связей от числа ветвей.

2.5 Построение модели структуры сети с МПС при

n=nmin =7

Соединяем те пары узлов, ветви которых не равны бесконечности в окончательной матрице L?.

Рис. 2

Модель структуры сети с МПС при n=nmin =7

2.6 Вывод

Сеть с МПС состоит при n=nmin = 7 из ветвей: 1−3, 2−3, 3−5, 4−5, 5−8, 5−7, 6−7 имеем сеть с наибольшей протяженностью связей. Суммарная протяженность связи при n=nmin = 7 максимальна и составляет 910 910 кан.-км. При n = nmax = 24 суммарная протяженность связи минимальна и составляет 741 620 кан.-км. Наименьшая протяженность связей не соответствует сети «каждый с каждым», так как обходной путь может быть таким же, как прямой путь, поэтому суммарная протяженность не изменяется. График зависмости суммарной протяженности связи от числа ветвей представлен в приложении 4

3. Расчет сети с МКЗ

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

Алгоритм построения сети с МКЗ:

· Ввод исходных данных: N, L, V, КЗ;

· Расчет значений:

· Расчет

· Изъятие произвольной ветви i-j и поиск для нее такого обходного пути, который дает минимум капитальных затрат на построение всей сети.

· Выбор минимального значения среди всех вариантов структур полученных в результате изъятия ветвей в предыдущем пункте и фиксация обходного пути для каналов изъятой ветви i-j;

· Перераспределение элементов в матрицах L и V, связанное с отсутствием изъятой ветви i-j и появлением дополнительного числа каналов Vij в ветвях обхода.

· Расчет

· Присвоение индексу n значения n ?1.

· Проверка значения n: при min n = n — окончание расчетов.

3.1 Исходные данные

Из таблицы приложения 3 и на основании матрицы V получаем матрицу капитальных затрат в соответствии с зависимостью kз кан.-кмij = f (vij):

3.2 Расчет суммарных капитальных затрат

Распишем подробно первую итерацию при n = nmax — 1 = 27:

Возможны следующие обходы:

Таким образом, после первой итерации изымается ветвь 6−8, так как именно ее изъятие дает минимальные КЗ = 12 714 610 руб. с обходом (6−7; 7−5; 5−8), из сети с 27 ветвями.

Произведем перераспределение каналов в матрицах V, L, Кз (? — изъятая ветвь, соединение между парой узлов отсутствует

Дальнейшие итерации в соответствии с алгоритмом представим в таблице 2:

Таблица 2

Зависимость капитальных затрат от числа ветвей

Окончательный вид матриц L и V после последней итерации:

3.3 Построение модели структуры сети с МКЗ

Соединяем те пары узлов, ветви которых не равны бесконечности в окончательной матрице L?.

Рис. 3

Модель структуры сети с Кз при n=nmin =7

3.4 Вывод

Сеть с МКЗ состоит при n=nmin = 7 из ветвей: 1−4, 2−3, 3−5, 4−5, 5−8, 5−7, 6−7 имеем сеть с минимальными капитальными затратами. Суммарные капитальные затраты при n=nmin = 7 минимальны и составляют 6 405 220 руб. При n = nmax = 28 суммарная капитальные затраты максимальны и составляет 13 981 270 руб. График зависимости суммарной протяженности связи от числа ветвей представлен в приложении 4

4. Заключение

Освоив методики и алгоритмы построения сетей связи с минимальной протяженностью ветвей (МПВ), с минимальной протяженностью связей (МПС); с минимальными капитальными затратами (МКЗ)пришли к следующим выводам:

· Структура сети с минимальной протяженностью ветвей (МПВ) соответствует такой сети, в которой сумма длин ветвей минимальна. С точки зрения теории сетей связи сеть с МПВ — это экстремальное полное собственное дерево, для построения которого используется метод Прима. С увеличением количества ветвей суммарная протяженность ветвей увеличивается. Топология «каждый с каждым» будет иметь максимальную протяженность ветвей

· При построении различных вариантов схем сети, отличающихся числом и расположением ветвей связи, будут возникать различия в емкостях, так как при отсутствии непосредственной связи между двумя пунктами, каналы между ними необходимо направлять в обход, укрупняя другие ветви. Требование обеспечения заданного числа каналов между каждой парой пунктов остается обязательным, поэтому задача сводится к оптимальному распределению каналов по ветвям сети, обеспечивающим минимальную протяженность связей. Сеть, имеющая наименьшую протяженность связей, будет образована путем соединения всех пунктов по принципу «каждый с каждым». Для такой сети потребуется максимальное количество ветвей. При всех других схемах суммарная протяженность связей будет возрастать. Максимальную протяженность связей будет иметь схема сети с минимальным числом ветвей — «дерево».

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

5. Список используемой литературы

1. Рогинский В. Н., Харкевич А. Д., Шнепо М. А., Давыдов Г. Б., Толчан А. Я. Теория сетей связи. — М.:Радио и связь, 1981.

2. Демина Е. В., Траубенберг И. А., Иодко Е. К., Майофис Л. И. Организация, планирование и управление предприятиями электрической связи. — М.: Связь, 1979.

3. Аджемов С. А. Метод анализа схем построения сети междугородных связей. — Сб. научных трудов ЦНИИС, вып. I, 1961.

4. Аджемов С. А. Об оценке схем построения сети по надежности и стоимости. — Сб. научных трудов ЦНИИС, вып. I, 1962.

Приложение 1

Расстояние между пунктами сети Lij

1 Приложение 2

Требуемое число каналов между пунктами сети Vij

Приложение 3

Значения КЗ кан.-км кабельной линии связи при различном числе каналов

Приложение 4

Графики зависимостей

График 1

Зависимость суммарной протяженности ветвей от числа ветвей

График 2

Зависимость суммарной протяженности связей от числа ветвей

График 3

Зависимость капитальных затрат от числа ветвей

Приложение 5

Модель структуры сети соединении станций по принципу «каждая с каждой» .