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

Содержание

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

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

Интерация 1………………………………………………………………………9

Интерация 2………………………………………………………………………12

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

 

 

 

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

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

Сервер АСУ ЛР We

                                    

 

_{o                                   o                                         o}

A₂W₁             A ₅W₂                             A₆

_{o                                              o}

A₃                                          A₇W₃

_{o                                          o}

A₁                                     A₄

 

o -расположение абонента

_o -возможное место установки концентратора

Рис.1.1 Топологическое расположение абонентов, пунктов возможной установки концентраторов и сервера W₀.

 Три возможных пункта установки концентраторов совпадают с пунктами расположения абонентов А₂, А₅, А₇. К каждому концентратору может быть подключено не более d=6 абонентов. Суммарная стоимость концентратора равна С₁=9, С₂=6, С₃=10.

 

 

 

 

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

Таблица 1.1

Стоимость каналов связи  между абонентами А_i и пунктами W_j 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

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

Обозначим:

c_y — стоимость канала связи между абонентом A_i(i=1,N) и пунктом W_j(j=1,n), где c_i0— стоимость прямого выделенного канала связи между абонентом и центром обработки; c_j — суммарная стоимость концентратора в пункте W_j(j=1,n) и канала связи от пункта W_j до центра обработки данных в пункте W₀.

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

1 - если абонент A_i подключен к концентратору W_j или к центру обработки данных в пункте W₀;

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

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

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

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

1 – если ∑X_ij > 0 (j=1,n);

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

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

Z=∑ ∑ c_ij X_ij + ∑ c_j y_j

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

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

∑ X_ij ≤ d, j=1,n. (учитывает, что к каждому концентратору может быть

подключено не более d абонентов)

В результате решения задачи оптимизация структуры СПД должен быть определен набор переменных{Y_j}(j=1,n) и {X_ij}, (i=1,N) (j=0,n)

обеспечивающий минимум целевой функции при ограничениях.

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

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

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

Топологическое расположение абонентов A_i (i =1,7), пунктов возможной установки концентраторов W_j (j = 1,3) и сервера АСУ ЛP W₀

показаны на рис.3.1, из которого видно, что три возможных пункта установки концентраторов совпадают с пунктами расположения абонентов А₂,A₅,A₇ на соответствующих станциях.

Сервер АСУ ЛР We

                                    

_{o                                   o                                         o}

A₂W₁             A ₅W₂                             A₆

_{o                                              o}

A₃                                          A₇W₃

_{o                                          o}

A₁                                     A₄

 

o -расположение абонента

_o -возможное место установки концентратора

Рис.3.1 Топологическое расположение абонентов, пунктов возможной установки концентраторов и сервера W₀.

 

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

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

Таблица 3.1

Стоимость каналов связи  между абонентами A_i и пунктами W_j

 

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 = ∑ C_i0  = 6 + 7 + 6 + 9 + 3 + 11 + 8 = 50

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

ИТЕРАЦИЯ 1

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

 

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

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

c₁₁ - c₁₀ = 2-6 = -4

c₂₁ – c₂₀ = 6-7 = -1

c₃₁ – c₃₀ = 4-6 = -2

c₄₁ – c₄₀ = 9-9 = 0

c₅₁ – c₅₀ = 7-3 = 4

c₆₁ – c₆₀ = 13-11 = 2

c₇₁ – c₇₀ = 10-8 = 2

 

Отсюда видно, что подключение  к концентратору в пункте W₁ абонентов А₁, А₂, А₃, может привести к снижению общей стоимости сети Z.

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

Z = C₁ +∑ C_i1+∑ C_i0 =9 + 2 + 6 + 4 + 9 + 3+11+8 = 47

 

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

 

 

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

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

c₁₂ – c₁₀ = 1-6=-5

c₂₂ – c₂₀ = 6-7=-1