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

Министерство образования  Российской Федерации

Пермский государственный  технический университет

Кафедра Автоматики и телемеханики

 

 

 

 

 

 

 

 

 

 

 

 

Расчетная работа

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

 

Вариант 21

 

 

 

 

 

 

Выполнил: ст.гр. ТК -06-1

Козлов П.В.

    Проверил:  Байдаров А.А.

 

 

 

 

 

 

                                                 

 

 

Пермь 2010

 

 

ЗАДАНИЕ:

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

 

1. Ознакомиться с методическими пояснениями к работе, алгоритмами вычислений, рекомендуемой литературой.
2. Подготовить индивидуальные исходные данные, используемые при расчете на ЭВМ.
3. Определить максимальное n_max и минимальное n_min число магистралей.
4. Начертить блок-схемы и уметь объяснить алгоритмы построения сети с МПВ, МПС, МКЗ.

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

 

1. Определить структуру сети с МПВ (т.е. соединение каких станций обеспечит выполнение заданного условия).
2. Рассчитать суммарную протяженность ветвей сети с МПВ.
3. Рассчитать суммарную протяженность ветвей сети с МПВ при заданном их числе.
4. Рассчитать суммарную протяженность ветвей сети при соединении станций по принципу "каждая с каждой".
5. Рассчитать суммарную протяженность связей сети, обладающей МПС.
6. Рассчитать суммарную протяженность связей сети, обладающей МПС при заданном числе ветвей сети n=n_max-R.
7. Определить структуру сети с МКЗ (т.е. соединение каких станций сети обеспечит заданное условие). Рассчитать сумму капитальных затрат на создание такой сети.
8. Рассчитать суммарные капитальные затраты на сеть связи, станции которой соединены по принципу "каждая c каждой".
9. Рассчитать суммарные капитальные затраты на сеть связи с МКЗ при заданном числе ветвей сети n=n_max-R.

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

 

1. Начертить модели структур сети с МПВ, МПС, МКЗ. Модели структур вычерчиваются без учета масштаба расстояний между станциями на сети.
2. Построить графики зависимостей;
• суммарной протяженности ветвей сети от числа ветвей (n);
• суммарной протяженности связей от n,
• суммы капитальных затрат на сеть от числа ветвей сети n.
3. На основании сравнения полученных структур сети и построенных зависимостей сделать выводы о соответствии полученных структур сетей со структурами, имеющими МПВ, МПС и МКЗ.

 

 

 

 

 

 

 

 

 

Цель работы:

 

Закрепление теоретических  знаний по разделу "Структура и  структурные свойства сети" и  освоение методики и алгоритмов построения сетей связи с:

1. минимальной протяженностью ветвей (МПВ);
2. минимальной протяженностью связей (МПС);
3. минимальными капитальными затратами (МКЗ).

 

 

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

 

M=21, задано число станций сети N=8.

1. Из таблицы приложения 1 выписываем  матрицу связности L , элементы которой представляют собой протяженности ветвей между парами узлов:

 

 

0	110	21	31	41	52	61	71
	0	78	52	32	42	53	62
		0	89	23	33	43	54
			0	114	24	34	44
				0	65	125	35
					0	89	26
						0	117
							0

 

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

140	340	270	60	340	250	100	60
40	340	160	530	360	50	410	240
290	120	160	60	240	510	70	320
200	140	230	510	260	190	250	140
140	80	260	340	180	360	120	240
80	110	210	180	60	130	100	810
30	320	200	140	540	610	880	50
50	130	40	270	120	50	130	80

 

 

Матрица емкости сети V получается из матрицы сложением числа каналов v_ij+v_ji.Получаем:

 

0	380	560	260	480	330	130	110
	0	280	670	440	160	730	370
		0	290	500	720	270	360
			0	600	370	390	410
				0	420	660	360
					0	710	860
						0	180
							0

 

 

 

 

 

 

 

РАСЧЕТ СЕТИ С  МПВ

0	110	21	31	41	52	61	71
	0	78	52	32	42	53	62
		0	89	23	33	43	54
			0	114	24	34	44
				0	65	125	35
					0	89	26
						0	117
							0

 

Выпишем найденные значения:

1-3, 2-5, 3-5, 4-6, 5-8, 6-8, 7-8

 

 

Построим модель структуры  сети с МПВ (рис. 1).

 

 

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

 

 

 

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

;

;

;

и т.д.

n – число ветвей.

 

Построим график зависимости  суммарной протяженности ветвей от числа ветвей

График наглядно показывает  как  нелинейно увеличивается размер протяжности ветвей сети с увеличением числа ветвей.

 

РАСЧЕТ СЕТИ С МПС

1. Исходные данные:

N=8;

Матрица L

 

0	110	21	31	41	52	61	71
	0	78	52	32	42	53	62
		0	89	23	33	43	54
			0	114	24	34	44
				0	65	125	35
					0	89	26
						0	117
							0

 

 

 

Матрица V

0	380	560	260	480	330	130	110
	0	280	670	440	160	730	370
		0	290	500	720	270	360
			0	600	370	390	410
				0	420	660	360
					0	710	860
						0	180
							0

 

 

;

 

2. Рассчитаем суммарную протяженность связей при n=n_max:

кан.-км.

 

3. Рассчитаем суммарную протяженность связей при n=n_max-1=44:

Наименьший размер сети будет достигаться при удалении ветви 5-7, что показывает программа:

-	-14060	24080	11700	1440	660	390	440
-14060	-	-6440	9380	28600	5440	24090	1850
24080	-6440	-	-10730	19500	28800	10530	1440
11700	9380	-10730	-	-25200	17020	22620	2460
1440	28600	19500	-25200	-	-3780	-38940	15120
660	5440	28800	17020	-3780	-	-22010	36120
390	24090	10530	22620	-38940	-22010	-	-7020
440	1850	1440	2460	15120	36120	-7020	-

 

Из матрицы, которая  начинается во 2ой строке видно, что  наименьшее приращение будет при  удалении из сети ветви 1-2, в данном случае обход будет осуществляться через узел 4.

Матрица L

 

0	110	21	31	41	52	61	71
	0	78	52	32	42	53	62
		0	89	23	33	43	54
			0	114	24	34	44
				0	65	-	35
					0	89	26
						0	117
							0

 

Матрица V

 

 

0	380	560	260	480	330	130	110
	0	280	670	440	160	730	370
		0	290	500+660=1160	720	270+660=930	360
			0	600	370	390	410
				0	420	660	360
					0	710	860
						0	180
							0

 

 

Суммарная протяженность  связей составит = 683020

кан.-км.

 

Дальнейшие  шаги сведем в таблицу

 

Исходный узел 1	Исходный узел 2	Обходной узел	Суммарная протяженность
7	5	3	644080
5	4	1	618880
7	6	4	596870
2	1	5	582810
4	3	1	572080
8	7	4	565060
3	2	5	558620
6	5	3	554840
7	1	3	555230
8	1	3	555670
6	1	3	556330
8	2	5	558180
8	3	5	560060
8	4	6	563600
5	1	3	567980
6	2	4	573420
7	2	4	597510

 

 

Матрица V будет:

-	0	2880	1150	0	0	0	0
	-	0	1560	1470	0	0	0
		-	0	3790	1470	1060	0
			-	0	1830	2010	0
				-	0	0	1200
					-	0	1450
						-	0
							-

 

В данном случае не достигается  т.к. отсутствуют обходы длинной 2.

 

 

 

 

 

 

Рис. 2. Модель структуры сети с МПС

 

4. Построим график зависимости суммарной протяженности связи от числа ветвей сети.

5. Из графика видно что с увеличением числа ветвей суммарное кол-во связей падает. 
   

РАСЧЕТ СЕТИ С МКЗ

 

Матрица L

0	110	21	31	41	52	61	71
	0	78	52	32	42	53	62
		0	89	23	33	43	54
			0	114	24	34	44
				0	65	125	35
					0	89	26
						0	117
							0

 

 

Матрица V

0	380	560	260	480	330	130	110
	0	280	670	440	160	730	370
		0	290	500	720	270	360
			0	600	370	390	410
				0	420	660	360
					0	710	860
						0	180
							0

 

 

Матрица Кз

0	6	8	12	6	6	8	8
8	0	6	6	6	12	6	6
8	8	0	8	8	6	10	6
8	8	6	0	6	8	8	8
8	10	8	6	0	6	6	8
8	8	8	8	10	0	8	6
12	6	8	8	6	6	0	8
10	8	12	6	8	15	6	0

 

Рассчитаем суммарные  капитальные затраты на сеть при  связи по принципу «каждая с каждой» (n=n_max):

при = 5 639 540р.

 

 

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

Исходный узел 1	Исходный узел 2	Обходной узел	Суммарная стоимость
7	5	3	3943280
5	4	1	3775960
7	6	4	3626140
2	1	5	3541780
4	3	6	3486100
8	7	4	3443980
3	2	5	3405340
6	5	3	3382660
3	1	5	3527140
8	1	5	3514820
8	3	5	3523460
7	1	4	3510720
4	2	7	3651420
6	1	4	3657360
8	2	5	3668460
8	4	6	3689700

 

В данном случае не достигается  т.к. отсутствуют обходы длинной 2.

 

 

Матрица V в итоге будет иметь вид:

0	-	-	1320	2130	-	-	-
	0	-	-	1470	160	1400	-
		0	-	2780	1430	930	-
			0	-	2290	2080	0
				0	-	-	1200
					0	-	1450
						0	-
							0

 

 

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

 

Из графика видно, что стоимость  сети почти линейно растет с увеличением числа ветвей в сети.

 

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

Блок-схемы.

 

Код программы на языка Matlab

Код для 1го задания курсовой работы:

function [ output_args ] = kur01( input_args )

%KUR01 Summary of this function goes here

%   Detailed explanation goes here

tic

clear

clc

BIG = 10^4;

N = 8;

x = xlsread('D:\var21.xlsx');

 

x = triu(x) + zeros(N,N);

 

x1 = x + x';

 

x0 = x;

 

x = x + x' * 10000 + eye(N,N) * 10000;

 

% x = x(1 : N - 1 , : );

GetWays(x);

CorrectWay(x);

 

 

 

[MIN_V, MIN_N] = min(x');

 

S = 0;

I = 1;

SUM_ALL = 0;

for i = 1 : N - 1

    [x, x1] = BigAndZero(x, x1, i, MIN_N(i));

    S = S + MIN_V(i);

   

    SUM_ALL(I) = S;

   

   

    MIN_XLS(1,I) = i;

    MIN_XLS(2,I) = MIN_N(i);

    MIN_XLS(3,I) = MIN_V(i);

    MIN_XLS(4,I) = S;

    I = I + 1;

   

   

end

% x

% x1

% S

% while ((CorrectWay(x1) == 1) & (I < 100))

N0 = 8*(8-1)/2;

while (I<N0)

   

    [MIN_V, MIN_ROW] = min(x'); %минимальные значения в каждом столбце

    [V, minN] = min(MIN_V); %строка с минимальным значением

   

    S = S + MIN_V(minN);

%     MIN_V(minN)

    X_before = x1;

    [x, x1] = BigAndZero(x, x1, minN, MIN_ROW(minN));

    SUM_ALL(I) = S;

   

    MIN_XLS(1,I) = minN;

    MIN_XLS(2,I) = MIN_ROW(minN);

    MIN_XLS(3,I) = MIN_V(minN);

    MIN_XLS(4,I) = S;

    I = I + 1;

end

 

xlswrite('D:\var21\kur01.xls',MIN_XLS', 'Лист1', 'B2');

% x

% x1

% X_before

% GetWays(X_before)

I - 1 %последняя не засчитывается, т.к. рвет сеть

% bar(SUM_ALL);

toc

 

'end'

end

 

function [x, x1] = BigAndZero(x, x1, row, col)

BIG = 10^4;

x(row, col) = BIG;

x(col, row) = BIG;

x1(row, col) = 0;

x1(col, row) = 0;

end

 

function  [y] =  GetWays(x)

s = size(x);

N = s(1);

y = 0;

for i = 1 : N

    y = y + x^i;

end

end

 

function [y] = CorrectWay(x)

a = GetWays(x);

y = 1;

if (HaveZero(a) == 1) y = 0; end;

end

 

function [Have] = HaveZero(x)

Have = 0;

s = size(x);

for i = 1 : s(1)

    for j = 1 : s(2)

        if (x(i,j) < 1) Have = 1; end;

    end

end

end

 

 

Код для 2го задания курсовой работы:

function [ output_args ] = kur02( input_args )

%KUR02 Summary of this function goes here

%   Detailed explanation goes here

tic

clear

clc

BIG = 10^4;

ALL = 8;

N = xlsread('D:\var21.xlsx');

N = triu(N) + zeros(ALL, ALL);

N = N + N';

N = N + eye(ALL) * BIG;

% N

L = xlsread('D:\var212.xlsx');

L = L + L';

xlswrite('D:\var21\L.xls',L);

I = 1;

Y_ALL(4, I) = sum(sum(L .* N)) / 2;

L = L + eye(ALL) * BIG;

 

N0 = N;