Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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



1. Сравнительный анализ топологий сетей телекоммуникаций

1.1 Этапы развития сетей

Различные виды электросвязи длительный период времени развивались независимо друг от друга. Каждый вид электросвязи ориентировался на создание своих каналов, систем передачи (СП) и сетей. Структура сети выбиралась в соответствии с особенностями распределения потоков сообщений, характерных для конкретного виды электросвязи. Некоторые отрасли промышленности и транспорта стали создавать свои сети, предназначенные для удовлетворения потребностей отрасли в передаче сообщений. Разобщенность технических средств не только не позволяла повысить эффективность совокупности сетей в масштабах страны, но и тормозила развитие обособленных сетей. Поэтому уже в начале 1960-х гг. стало ясно, что перспективным направлением развития сетей должно было стать объединение сетей. Было принято решение о создании ЕАСС (Единая автоматизированная сеть связи). ЕАСС базировалась на объединении разрозненных и многочисленных мелких сетей в общегосударственные сети каждого вида электросвязи, а затем в единую сеть с целью совместного использования определенных технических средств, и, в первую очередь, систем передачи и систем коммутации.

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

1) первичную сеть - совокупность сетевых станций, сетевых узлов (дать определение в приложении) и соединяющих их линий передачи, которая позволяет организовывать сеть каналов передачи и групповых трактов.

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

* местные первичные сети - часть сети, ограниченная территорией города или сельского района;

* зоновые первичные сети - часть сети, охватывающая территорию зоны (область, край, республика), обеспечивающая соединение между собой каналов разных местных сетей внутри одной зоны;

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

Структура первичной сети показана на рисунке 1.1.

Рисунок 1.1. Структура первичной сети

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

Вторичные сети подразделяются на следующие виды:

* телефонные;

* телеграфные;

* передачи данных;

* факсимильные;

* телевизионного вещания;

* звукового вещания.

1.2 Основные способы построения телекоммуникационных сетей связи

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

При полносвязанном способе построения (принцип «каждый с каждым») между узлами существует непосредственная связь. Используется при небольшом количестве узлов на сети (рисунок 1.2 а).

При радиальном способе построения сети связь между узлами осуществляется через центральный узел (рисунок 1.2 б). Используется при построении сети на сравнительно небольшой территории.

На большой территории сеть связи строится по радиально-узловому способу (рисунок 1.2 в).

Кольцевой способ построения сети предусматривает возможность осуществления связи как по часовой, так и против часовой стрелки (рис. 1.2 г.). В этом случае при повреждении на определенном участке сеть сохраняет свою работоспособность.

При комбинированном способе построения сети узлы на верхнем иерархическом уровне связываются по полносвязанной схеме рисунок 1.2 д). В этом случае выход одного из узлов не нарушает работу всей сети.

Рисунок 1.2. Способы построения сетей связи



2. Построение модели топологии разрабатываемой сети телекоммуникаций

Данные представляем в виде таблицы 2.1

Таблица 2.1. Расстояния между узлами проектируемой сети

Город	№	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Ивье	1.	М	56	73	76	148	129	145	182	194	52	139	82	98	98	98
Ошмяны	2.	56	М	31	21	96	82	123	138	144	54	127	61	64	89	98
Сморгонь	3.	73	31	М	32	77	57	93	111	121	54	99	35	34	65	76
Островец	4.	76	21	32	М	80	70	123	126	129	44	131	67	64	97	109
Поставы	5.	148	96	77	80	М	27	100	54	49	69	120	89	69	109	126
Мядель	6.	129	82	57	70	27	М	77	56	64	116	95	63	42	82	99
Плещеницы	7.	145	123	93	123	100	77	М	80	108	92	24	65	60	49	60
Глубокое	8.	182	138	111	126	54	56	80	М	29	92	105	107	87	113	128
Шарковщина	9.	194	144	121	129	49	64	108	29	М	139	132	124	103	136	151
Воложин	10.	52	54	44	69	116	92	92	139	155	М	87	32	52	46	49
Логойск	11.	139	127	99	131	120	95	24	105	132	87	М	66	69	41	43
Молодечно	12.	82	61	35	67	89	63	65	107	124	32	66	М	21	30	43
Вилейка	13.	98	64	34	64	69	42	60	87	103	52	69	21	М	43	57
Радошковичи	14.	98	89	65	97	109	82	49	113	136	46	41	30	43	М	17
Заславль	15.	98	98	76	109	126	99	60	128	151	49	43	43	57	17	М

Задача коммивояжера

Возьмем в качестве произвольного маршрута:

X₀ = (1,2); (2,3); (3,4); (4,5); (5,6); (6,7); (7,8); (8,9); (9,10); (10,11); (11,12); (12,13); (13,14); (14,15); (15,1);

Тогда F(X₀) = 56 + 31 + 32 + 80 + 27 + 77 + 80 + 29 + 155 + 87 + 66 + 21 + 43 + 17=801



3. Разработка вычислительной процедуры оптимизации топологии разрабатываемой сети

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

Город	№	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Ивье	1.	М	56	73	76	148	129	145	182	194	52	139	82	98	98	98
Ошмяны	2.	56	М	31	21	96	82	123	138	144	54	127	61	64	89	98
Сморгонь	3.	73	31	М	32	77	57	93	111	121	54	99	35	34	65	76
Островец	4.	76	21	32	М	80	70	123	126	129	44	131	67	64	97	109
Поставы	5.	148	96	77	80	М	27	100	54	49	69	120	89	69	109	126
Мядель	6.	129	82	57	70	27	М	77	56	64	116	95	63	42	82	99
Плещеницы	7.	145	123	93	123	100	77	М	80	108	92	24	65	60	49	60
Глубокое	8.	182	138	111	126	54	56	80	М	29	92	105	107	87	113	128
Шарковщина	9.	194	144	121	129	49	64	108	29	М	139	132	124	103	136	151
Воложин	10.	52	54	44	69	116	92	92	139	155	М	87	32	52	46	49
Логойск	11.	139	127	99	131	120	95	24	105	132	87	М	66	69	41	43
Молодечно	12.	82	61	35	67	89	63	65	107	124	32	66	М	21	30	43
Вилейка	13.	98	64	34	64	69	42	60	87	103	52	69	21	М	43	57
Радошковичи	14.	98	89	65	97	109	82	49	113	136	46	41	30	43	М	17
Заславль	15.	98	98	76	109	126	99	60	128	151	49	43	43	57	17	М

При решении задачи нахождения оптимального пути происходит разделение задачи на процессы (по количеству узлов), в данном случае на 15. Процесс начинается из узла №1. Фактически не важно, откуда его начинать, все равно маршрут круговой и охватывает все узлы.

На первом этапе вычислительной процедурой будет расстояние от узла №1 до каждого из оставшихся узлов.



№ процесса	Значение
1.	0
2.	56
3.	73
4.	76
5.	148
6.	129
7.	145
8.	182
9.	194
10.	52
11.	139
12.	82
13.	98
14.	98
15.	98

На следующем этапе значение вычислительной процедуры принимает значение минимального расстояния в следующий (любой узел).

№ процесса	Значение 1 этапа	Значение 2 этапа
1.	0	0
2.	56	56+21=77
3.	73	73+31=104
4.	76	76+21=97
5.	148	148+27=175
6.	129	129+27=156
7.	145	145+24=169
8.	182	182+29=211
9.	194	194+29=123
10.	52	52+32=85
11.	139	139+24=163
12.	82	82+21=103
13.	98	98+21=119
14.	98	98+17=115
15.	98	98+17=115



Выбирается минимум функции. Следует обратить внимание, что из значений функций можно сразу убирать заведомо неправильные значения. Так же не следует учитывать значения ведущие в «обратную сторону».



4. Разработка блок-схемы программы-оболочки и блок-схем основных программ-процедур для оптимизации топологии сети

Рисунок 4.1. Блок-схема оболочки программы

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



5. Разработка и отладка программы оптимизации топологии сети телекоммуникаций по критерию минимума ее протяженности

Программа разработана на языке программирования Java. Java - объектно-ориентированный язык программирования, разрабатываемый компанией SunMicrosystems с 1991 года и официально выпущенный 23 мая 1995 года. Изначально новый язык программирования назывался Oak (JamesGosling) и разрабатывался для бытовой электроники, но впоследствии был переименован в Java и стал использоваться для написания апплетов, приложений и серверного программного обеспечения

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

В Java используются практически идентичные соглашения для объявления переменных, передачи параметров, операторов и для управления потоком выполнением кода. В Java добавлены все хорошие черты C++.

Три ключевых элемента объединились в технологии языка Java

Java предоставляет для широкого использования свои апплеты (applets) - небольшие, надежные, динамичные, не зависящие от платформы активные сетевые приложения, встраиваемые в страницы Web. Апплеты Java могут настраиваться и распространяться потребителям с такой же легкостью, как любые документы HTML

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

Java предоставляет программисту богатый набор классов объектов для ясного абстрагирования многих системных функций, используемых при работе с окнами, сетью и для ввода-вывода. Ключевая черта этих классов заключается в том, что они обеспечивают создание независимых от используемой платформы абстракций для широкого спектра системных интерфейсов

Огромное преимущество Java заключается в том, что на этом языке можно создавать приложения, способные работать на различных платформах. К сети Internet подключены компьютеры самых разных типов - Pentium PC, Macintosh, рабочие станции Sun и так далее. Даже в рамках компьютеров, созданных на базе процессоров Intel, существует несколько платформ, например, MicrosoftWindows версии 3.1, Windows 95, Windows NT, OS/2, Solaris, различные разновидности операционной системы UNIX с графической оболочкой X­Windows. Между тем, создавая сервер Web в сети Internet, хотелось бы, чтобы им могло пользоваться как можно большее число людей. В этом случае выручат приложения Java, предназначенные для работы на различных платформах и не зависящие от конкретного типа процессора и операционной системы.

Исходные данные программа берет из текстового файла, представляющего собой таблицу. Путь к файлу прописан в теле программы. ПО умолчанию значение равно «D:\\cites.txt». Имеет значение количества городов, в случае изменения их количества, необходимо изменить значение переменной n.



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

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

Рисунок 5.1. Результат работы программы



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

Результат работы программы представлены на рисунке 5.2. При этом результат проверен в других алгоритмах.

Схема маршрута с привязкой к карте РБ представлена на рисунке 6.1.

Рисунок 6.1. Схема маршрута согласно топологии «Кольцо»



Заключение

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



Список используемых источников

1) Электронный ресурс по дисциплине Основы оптимизационных методов.

2) https://ru.wikipedia.org

3) http://dic.academic.ru/



Приложение

Текст программы

import java.io.*;

import java.util. ArrayList;

import java.util. Arrays;

import java.util. List;

import java.util. StringTokenizer;

public class ShortestPathDynamicMethods {

public static int[][] readDistancesFromFile() throws FileNotFoundException {

File f1 = new File («D:\\Cities2.txt»);

BufferedReader input = new BufferedReader (new FileReader(f1));

BufferedReader input1 = new BufferedReader (new FileReader(f1));

int NUMBER_CITIES = 0;

try {

String line = null;

while ((line = input1.readLine())!= null) {

NUMBER_CITIES++;

}

input1.close();

} catch (IOException e) {

e.printStackTrace();

}

int[][] array = new int [NUMBER_CITIES] [NUMBER_CITIES];

inti = 0;

try {

String line = null;

while ((line = input.readLine())!= null) {

StringTokenizerst = new StringTokenizer(line);

int j = 0;

while (st.hasMoreTokens()) {

String tkn = st.nextToken();

 //System.out.println(tkn);

array[i] [j] = Integer.parseInt(tkn);

j = j + 1;

}

i = i + 1;

}

} catch (IOException e) {

e.printStackTrace();

}

return array;

}

public static intgetShortestDistance (int[][] dist) {

List<String>cityList = new ArrayList<String>();

cityList.add («Ивье»);

cityList.add («Ошмяны»);

cityList.add («Сморгонь»);

cityList.add («Островец»);

cityList.add («Поставы»);

cityList.add («Мядель»);

cityList.add («Плещеницы»);

cityList.add («Глубокое»);

cityList.add («Шарковщина»);

cityList.add («Воложин»);

cityList.add («Логойск»);

cityList.add («Молодечно»);

cityList.add («Вилейка»);

cityList.add («Радошковичи»);

cityList.add («Заславль»);

int n = dist.length;

int[][] dp = new int [1 << n] [n];

for (int[] d: dp)

Arrays.fill (d, Integer.MAX_VALUE / 2);

dp[1] [0] = 0;

for (int mask = 1; mask < 1 << n; mask += 2) {

for (inti = 1; i< n; i++) {

if ((mask & 1 <<i)!= 0) {

for (int j = 0; j < n; j++) {

if ((mask & 1 << j)!= 0) {

dp[mask] [i] = Math.min (dp[mask] [i], dp [mask ^ (1 <<i)] [j] + dist[j] [i]);

}

}

}

}

}

int res = Integer.MAX_VALUE;

for (inti = 1; i< n; i++) {

res = Math.min (res, dp[(1 << n) - 1] [i] + dist[i] [0]);

}



int cur = (1 << n) - 1;

int[] order = new int[n];

int last = 0;

for (inti = n - 1; i>= 1; i-) {

intbj = -1;

for (int j = 1; j < n; j++) {

if ((cur & 1 << j)!= 0 && (bj == -1 || dp[cur] [bj] + dist[bj] [last] >dp[cur] [j] + dist[j] [last])) {

bj = j;

}

}

order[i] = bj;

cur ^= 1 <<bj;

last = bj;

}

System.out.println («Порядокобходагородов:»);

for (inti = 0; i<order.length; i++)

System.out.println((i + 1) + " " + cityList.get (order[i]));

return res;

}

public static void main (String[] args) {

try {

System.out.println («Минимальноерасстояние:» + getShortestDistance (ShortestPathDynamicMethods.readDistancesFromFile()));

} catch (Exception e) {

e.printStackTrace();

}

}

}

Размещено на Allbest.ru

...