Обоснование и расчет оптимальной структуры сети

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

Содержание

1. Задание на курсовой проект

2. Обоснование и расчет оптимальной структуры сети

3. Интерация 1

4. Интерация 2

Список литературы



1. Задание на курсовой проект

Обосновать выбор оптимальной структуры сети, состоящей из сервера линейного района и N АРМ-ов дежурных по станциям (АРМ ДСП), расположенных на прилегающих к району малых станциях. Подключение АРМ-ов к серверу может быть организовано по выделенным каналам связи или через концентраторы, для которых известны три возможных пункта установки на малых станциях (n=3). Топологическое расположение абонентов Ai (i=l,7), пунктов возможной установки концентраторов Wj (j=l,3) и сервера W0 (рис.1.1).

Три возможных пункта установки концентраторов совпадают с пунктами расположения абонентов А2, А5, А7. К каждому концентратору может быть подключено не более d=6 абонентов. Суммарная стоимость концентратора равна С1=9, С2=6, С3=10.

Стоимости каналов связи Cij между абонентами A; (i=l,7) и пунктами Wi (j=1,3) приведены в таблице 1.1:

Таблица 1.1 Стоимость каналов связи между абонентами Аi и пунктами Wj

Wj Ai	W0	W1	W2	W3
A1	6	2	1	10
A2	7	6	6	11
A3	6	4	6	7
A4	9	9	6	6
A5	3	7	0	6
A6	11	13	8	2
A7	8	10	5	0



2. Обоснование и расчет оптимальной структуры сети

сервер концентратор сеть автоматизированный

Сеть передачи данных Автоматизированной системы управления железнодорожным транспортом (АСУЖТ) содержит большое число территориально рассредоточенных абонентов, которые в зависимости от объемов передаваемой информации и требований по срочности ее доставки могут включаться в СПД различными способами. Эти способы ориентированы в основном на использование аналоговых телефонных каналов связи, высокоскоростных цифровых каналов связи или физических цепей. При этом абоненты, которым предоставляются выделенные каналы связи, могут быть соединены с центром обработки данных (например, ИВЦ дороги) непосредственно либо через промежуточные узлы коммутации (коммутаторы пакетов или сообщений, концентраторы).

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

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

Задано N пунктов размещения абонентов. Каждый абонент Ai (i=1,N) должен быть соединен с центром обработки либо непосредственно по выделенному каналу связи, либо через концентратор. Место расположения центра обработки обозначим W0. Также задано n пунктов возможной установки концентраторов. Пункты установки концентраторов Wj(j=1,n) могут совпадать с пунктами размещения абонентов Ai(i=1,N). К каждому концентратору можно подключить не более d абонентов. Требуется определить, сколько и в каких пунктах нужно установить концентраторов, и каких абонентов подключить к каждому концентратору, с тем, чтобы стоимость СПД была минимальной.

Обозначим:

cy -- стоимость канала связи между абонентом Ai(i=1,N) и пунктом Wj(j=1,n), где ci0-- стоимость прямого выделенного канала связи между абонентом и центром обработки; cj -- суммарная стоимость концентратора в пункте Wj(j=1,n) и канала связи от пункта Wj до центра обработки данных в пункте W0.

Для записи целевой функции введем булевы переменные Xij и Yij :

1 - если абонент Ai подключен к концентратору Wj или к центру обработки данных в пункте W0;

0 - в противном случае.

1 - если в пункте W, установлен концентратор;

0 - в противном случае.

Между этими переменными имеется очевидная зависимость

1 - если ?Xij > 0 (j=1,n);

0 - в противном случае.

Тогда общая стоимость СПД составит

Z=? ? cij Xij + ? cj yj

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

? Xij =1, i=1,N, указывает на то, что любой абонент должен быть соединен единственным образом либо непосредственно с центром обработки данных, либо с концентратором;

? Xij ? d, j=1,n. (учитывает, что к каждому концентратору может быть подключено не более d абонентов)

В результате решения задачи оптимизация структуры СПД должен быть определен набор переменных{Yj}(j=1,n) и {Xij}, (i=1,N) (j=0,n) обеспечивающий минимум целевой функции при ограничениях.

Данная задача может быть решена методами целочисленного линейного программирования с использованием специальных алгоритмов либо методом ветвей и границ. Однако для СПД с большим числом абонентов (несколько сотен) и для большого числа возможных пунктов установки концентраторов использование этих методов вызывает определенные сложности вычислений.

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

По этой причине при проектировании СПД используют эвристические алгоритмы, например направленный перебор с оценкой целесообразности того или иного варианта соединения абонентов с центром обработки данных. С помощью одного из таких алгоритмов, который называется алгоритмом добавления, решается данная задача [5].

Топологическое расположение абонентов Ai (i =1,7), пунктов возможной установки концентраторов Wj (j = 1,3) и сервера АСУ ЛP W0 показаны на рис.3.1, из которого видно, что три возможных пункта установки концентраторов совпадают с пунктами расположения абонентов А2,A5,A7 на соответствующих станциях.

К каждому концентратору может быть подключено не более d=6 абонентов. Суммарная стоимость концентратора равна С1=9, С2=6, С3=10.

Стоимости каналов связи с, между абонентами Ai (i=l,7) и пунктами Wj (j=l,3) приведены в таблице 3.1:

Таблица 3.1 Стоимость каналов связи между абонентами Ai и пунктами Wj

Wj Ai	W0	W1	W2	W3
A1	6	2	1	10
A2	7	6	6	11
A3	6	4	6	7
A4	9	9	6	6
A5	3	7	0	6
A6	11	13	8	2
A7	8	10	5	0



Реализация алгоритма добавления

Инициализация алгоритма добавления начинается со структуры сети, в которой все абоненты соединяются с центром обработки выделенными каналами (без использования концентраторов). Такая структура приведена на рис. 3.2

Рис 3.2 Соединение абонентов с центром обработки выделенными каналами

В этом случае общая стоимость СПД составит:

Z = ? Ci0 = 6 + 7 + 6 + 9 + 3 + 11 + 8 = 50

Далее последовательно предусматриваем установку концентраторов в возможных пунктах установки Wj (j=l,3) и для каждого абонента вычисляем разность стоимости подключения в новой структуре со стоимостью подключения в предыдущей структуре. Если для некоторого абонента А разность оказывается отрицательной, это означает, что вариант подключения для данного абонента является более дешевым и потенциально может быть достигнуто снижение общей стоимости сети Z (при условии, что стоимость установки концентратора не превысит общего снижения стоимости за счет отрицательных значений разностей подключения в новой структуре со стоимостью подключения в предыдущей структуре).

3. Итерация 1

Устанавливаем концентратор в пункте W1 и проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети на рис. 3.3

Рис 3.3 Структура сети передачи данных с концентратором в пункте W1

Для этого вычисляем разности ci1 - ci0 , i = 1,7 .

c11 - c10 = 2-6 = -4

c21 - c20 = 6-7 = -1

c31 - c30 = 4-6 = -2

c41 - c40 = 9-9 = 0

c51 - c50 = 7-3 = 4

c61 - c60 = 13-11 = 2

c71 - c70 = 10-8 = 2

Отсюда видно, что подключение к концентратору в пункте W1 абонентов А1, А2, А3, может привести к снижению общей стоимости сети Z.

Общая стоимость сети

Z = C1 +? Ci1+? Ci0 =9 + 2 + 6 + 4 + 9 + 3+11+8 = 47

Далее устанавливаем концентратор в пункте W2 проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети на рис. 3.4

Рис. 3.4 Структура сети передачи данных с концентратором в пункте W2

Для этого вычисляем разности сi2 - ci0 , i = 1,7 .

c12 - c10 = 1-6=-5

c22 - c20 = 6-7=-1

c32 - c30 = 6-6=0

c42 - c40 = 6-9=-3

c52 - c50 = 0-3=-3

c62 - c60 = 8-11=-4

c72 - c70 = 5-8=-3

Отсюда видно, что подключение к концентратору в пункте W 2 абонентов А1, А2, А4, А5, А6, А7 может привести к снижению общей стоимости сети Z. Общая стоимость сети

Z = С2 +? Сi2 + C3= 6+1+6+6+0+8+5+6=46



Далее устанавливаем концентратор в пункте W3 и проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети на рис 3.5

Рис. 3.5 Структура сети передачи данных с концентратором в пункте W3

Для этого вычисляем разности ci3 - ci0, i=1.7

c13 - c10 = 10-6=4

c23 - c20 = 11-7=4

c33 - c30 = 7-6=1

c43 - c40 = 6-9=-3

c53 - c50 = 6-3=3

c63 - c60 = 2-11=-9

c73 - c70 = 0-8=-8

Отсюда видно, что подключение к концентратору в пункте W3 абонентов А4, A6, А7 может привести к снижению общей стоимости сети Z.

Общая стоимость сети

Z= C3 +?Ci3 + ?Ci0 = 10+6+2+0+6+7+6+3= 48



После первой итерации получена оптимальная по стоимости структура сети с одним концентратором, установленном в пункте W2 (см.рис.3.4).

4. Итерация 2

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

Размещаем концентратор в пункте W1 и вычисляем разности стоимости подключения абонентов к этому концентратору и стоимости их подключения в структуре W2.

Получаем

c11-c12=2-1=1

c21-c20=6-7=-1

c31-c32=4-6=-2

c41-c40=9-9=0

c51-c52=7-0=7

c61-c62=13-8=5

c71-c72=10-5=5

Отсюда видно, что к снижению стоимости сети может привести подключение абонентов А2, А3 к концентратору W1. Абоненты А1, А5, А6, А7 целесообразно оставить подключенными к концентратору W2, а абонента А4 подключить по выделенному каналу к серверу АСУ JIP, как показано на рис. 3.6.



Рис. 3.6 Структура сети передачи данных с концентратором в пункте W1 и W2

Общая стоимость сети:

Z = C1 + С2 + ?Ci1 + ?Ci2 + C40 =9+6+6+4+0+8+5+9+1=48

Таким образом, установка концентратора в пункте W1 приведет к повышению стоимости сети.

Далее проверим, приведет ли к снижению стоимости сети с концентраторами в пунктах W1иW2 установка концентратора в пункте W3. Вычислим соответствующие разности:

с13-с11=10-2=8

с23-с21=11-6=5

с33-с31=7-4=3

с43-с40=6-9=-3

с53-с52=6-0=6

с63-с62=2-8=-6

с73-с72=0-5=-5



Отсюда видно, что подключение абонента А4, А6, А7 может привести к снижению общей стоимости сети Z.

Стоимость такой сети:

Z = C1 +С2 +С3 +?Сi1+C52+?Ci3 =9+6+10+2+6+4+0+6+2+0=45

Следовательно, установка третьего концентратора в пункте W3 приводит к уменьшению стоимости сети, рис. 3.7.

Рис. 3.7 Оптимальная по стоимости структура сети

На рис. 3.8 показано последовательное изменение стоимости сети в процессе применения алгоритма добавления.

Изменение стоимости за счет установки концентраторов

Проведя необходимые расчеты мы добились уменьшения стоимости сети за счет установки дополнительных концентраторов.

Список литературы

1. Проектирование информационных систем на ж.-д.т.: Учебник для вузов ж.-д.т./ Под ред. Э.К. Лец- кого,- Маршрут, 2003.

2. Информационные технологии на железнодорожном транспорте: Учебник для вузов ж.-д. транспорта / Э.К. Лецкий, В.И. Панкратов, В.В. Яковлев и др.; Под ред. Э.К. Лецкого, Э.С. Поддавашкина, В.В. Яковлева. - М.: УМК МПС России, 2000. - 680 с.

3. Етрухин Н.Н. Обзор рекомендаций МККТТ по современным технологиям электронных коммуникаций. Технологии электронных коммуникаций. - М.: ЭКО-ТРЕНДЗ, 1993 г. -Т. 10. - С. 95-148.

4. ГОСТ 22348-86. Единая автоматизированная сеть связи. Термины и определения. - М.: Издательство стандартов, 1987. - 16 с.

5. ГОСТ 17657-79. Передача данных.. Термины и определения. - М.: Издательство стандартов, 1987.

6. Беспалов С.Н. Развитие современных цифровых систем связи и передачи данных на Российских железных дорогах: Сборник докладов международной конференции «Совершенствование транспортного обслуживания перевозок грузов на основе внедрения информационных систем». - М:. Издательство ООО «Интекст», 2001.

7. Мартин Дж. Системный анализ передачи данных. Том П. -М.: Мир, 1975. -432 с.

8. Гук М Аппаратные средства локальных сетей.Энциклопедия. СПб.: Питер, 2002

9. Методические указания по выполнению Курсовых и дипломных проектов (работ)/ Сост. А.М. Косолапов , В.Г. Волик , А.П. Долгинцев. - Самара СамГАПС, 2004.

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

...