«управление сетью передачи информации (спи) с коммутацией сообщений»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПУТЕЙ СООБЩЕНИЯ

(МИИТ)



Кафедра «Управление и информатика в технических системах»

КУРСОВОЙ ПРОЕКТ

по дисциплине:
«АВТОМАТИЗИРОВАННЫЕ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫ»
на тему:
«УПРАВЛЕНИЕ СЕТЬЮ ПЕРЕДАЧИ ИНФОРМАЦИИ (СПИ)

С КОММУТАЦИЕЙ СООБЩЕНИЙ»

Вариант 16

Выполнил: ст. гр. АУИ-511

Мошненко И. А.

Принял: доцент Давыдюк В. Б.
Москва 2006

СОДЕРЖАНИЕ

	стр.
Исходные данные ………………………………………………………………………………..	2
Рабочее задание ………………………………………………………………………………….	3
1. Общая характеристика СПИ как сложной информационно-управляющей системы ..…...	4
2. Анализ статистических данных входного воздействия .…………………………………...	5
2.1. Построение гистограммы и статистической функции распределения вероятностей .	5
2.2. Определение методом максимального правдоподобия оценок параметров предполагаемого закона распределения .....…………………………………………….	5
2.3. Проверка гипотезы о предполагаемом законе распределения с помощью критериев согласия Пирсона и Колмогорова ….…………………………………………………...	10
3. Разработка алгоритма управления СПИ по критерию максимальной ёмкости пучков каналов ………………………………………………………………………………………...	11
3.1. Маршрутизация потоков сообщений..………………………………….……………….	11
3.2. Математическая модель потоков сообщений ……………………….…………………	13
3.3. Построение симплекс-таблицы …………………………………………………………	15
3.4. Расчёт на ЭВМ потоков сообщений ……………………………………………………	15
3.5. Построение вторичного графа СПИ ……………………………………………………	17
4. Разработка алгоритма управления СПИ по критерию максимальной надёжности ……...	18
4.1. Построение матрицы надёжных маршрутов (дистанционной таблицы) …………….	18
4.2. Построение маршрутной таблицы …………………………………….………………..	20
5. Определение ёмкости ЗУ на узлах коммутации ……………………………………………	21
6. Выводы ………………………………………………………………………………………...	22
7. Список литературы …………………………………………………………………………...	23

ИСХОДНЫЕ ДАННЫЕ

1. 
   Схема СПИ (рис. 1).
   

Рис. 1. Схема СПИ.

2. 
   Среднее время передачи сообщения .
   
3. 
   Вероятность переполнения ЗУ - .
   
4. 
   Матрица потоков сообщений
   

   50	40	70

5. 
   Матрица емкостей ветвей
   

   45	35	20	30	50	20	50	0	0	80	55	0

6. 
   Интервалы количества символов .
   
7. 
   Количество наблюдений в интервале .
   

Статистические данные о распределении количества символов в сообщении.

Интервалы количества символов	Среднее в интервале	Количество наблюдений в интервале
20-60	35	18
60-80	70	80
80-100	95	140
100-120	108	240
120-140	132	245
140-160	148	140
160-180	167	28
180-220	200	9

8. 
   Для хранения символа требуется один байт памяти.
   
9. 
   Матрица надёжности ветвей вязи
   

Ветви связи
1-2	1-3	1-4	2-3	3-5	6-7	2-5	4-5	2-6	5-7	5-6	4-7
Величина
6	7	4	1	8	6	5	9	2	3	4	5
Формула для вычисления показателя надёжности
0,996	0,997	0,994	0,991	0,998	0,996	0,995	0,999	0,992	0,993	0,994	0,995

РАБОЧЕЕ ЗАДАНИЕ

1. 
   Дать общую характеристику СПИ как сложной информационно-управляющей системы. Описать задачи и структуру управления СПИ. Обосновать выбор целевой функции.
   
2. 
   По статистическим данным построить гистограмму количества символов в сообщении. Получить оценки максимального правдоподобия для параметров нормального закона распределения. Проверить гипотезу о нормальности закона распределения количества символов с помощью критерия и Колмогорова.
   
3. 
   Разработать алгоритм оптимального распределения потоков информации с помощью симплекс-метода линейного программирования. Дать математическую формулировку задачи. Составить таблицу симплекс-метода, кратко описать ход решения, решить задачу на ПЭВМ. Описать алгоритм управления СПИ на основе полученных результатов. Построить граф СПИ, на котором обозначить оптимальные потоки сообщений.
   
4. 
   Построить матрицу надёжных маршрутов и маршрутную таблицу.
   
5. 
   Определить ёмкости запоминающих устройств на узлах коммутации, исходя из заданной вероятности переполнения ЗУ в час наибольшей загрузки.
   

1. 
   ОБЩАЯ ХАРАКТЕРИСТИКА СПИ КАК СЛОЖНОЙ ИНФОРМАЦИОННО-УПРАВЛЯЮЩЕЙ СИСТЕМЫ
   

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

Основные элементы СПИ:

• 
  узлы коммутации (УК);
  
• 
  линии связи (ЛС).
  

ЛС характеризуются:

1. 
   Одно- и двусторонностью;
   
2. 
   Ёмкостью;
   
3. 
   Длиной;
   
4. 
   Надёжностью;
   
5. 
   Стоимостью.
   

УК характеризуются:

1. 
   Мощностью (ёмкостью);
   
2. 
   Надёжностью;
   
3. 
   Стоимостью.
   

УК включает в себя аппаратуру коммутации и устройство управления (УУ).

Существуют также центральные устройства управления (ЦУУ), необходимые для согласованной работы УК, входящих в состав СПИ.

Существует три вида СПИ:

1. 
   Некоммутируемые СПИ (см. рис. 1.1).
   

Рис. 1.1. Некоммутируемые СПИ.
Данные СПИ характеризуются быстротой, дешевизной, простотой организации маршрутов. Однако здесь нет возможности гибкого распределения сообщений по ЛС, что влечёт за собой перегрузки и недоиспользование возможностей. Такие СПИ используются при организации правительственной связи.

2. 
   Коммутируемые СПИ.
   

Такие СПИ имеют аппаратуру коммутации каналов (см. рис. 1.2).



Рис. 1.2. УК коммутируемых СПИ.
Такие СПИ способны гибко распределять информацию в пространстве, но неизбежна потеря времени на организацию маршрутов.

3. 
   СПИ с коммутацией сообщений (см. рис. 1.3).
   

В таких СПИ информация распределяется не только в пространстве, но и во времени.



Рис. 1.3. УК СПИ с коммутацией сообщений.
При выборе целевой функции необходимо определить задачи, которые должна решать проектируемая СПИ. Такими задачами могут быть:

1. 
   Максимальное удовлетворение запросов на передачу информации;
   
2. 
   Обеспечение живучести системы при повреждении определённого числа линий связи;
   
3. 
   Максимальная надёжность маршрутов или минимальная вероятность искажения передаваемой информации;
   
4. 
   Минимальная стоимость передачи сообщения;
   
5. 
   Максимальное быстродействие.
   

2. 
   АНАЛИЗ СТАТИСТИЧЕСКИХ ДАННЫХ ВХОДНОГО ВОЗДЕЙСТВИЯ
   

1. Построение гистограммы и статистической

функции распределения вероятностей

В таблице 2.2.1 приведены данные к построению гистограммы, статистической функции распределения, данные по гипотезе о законе распределения и по критериям согласия Пирсона и Колмогорова. Гистограмма представлена на рис. 2.2.1, статистическая функция распределения представлена на рис. 2.2.2.

2. 
   Определение методом максимального правдоподобия
   

оценок параметров предполагаемого закона распределения
Сделаем предположение, что имеет место нормальный закон распределения:



Необходимо оценить параметры и .

На основании метода максимального правдоподобия составим функцию максимального правдоподобия:



Запишем систему уравнений для нахождения оценок параметров закона распределения:

(2.2.1)



Оценка дисперсии в системе (2.2.1) является смещённой, необходимо найти несмещённую оценку.

Несмещённая оценка дисперсии:



График функции представлен на рис. 2.2.1.

.

Таблица 2.2.1

Границы диапазонов количества символов	2060			6080		80100		100120		120140		140160		160180		180220
Количество наблюдений в интервале	18			80		140		240		245		140		28		9
Среднее в интервале	35			70		95		108		132		148		167		200
Частоты события	0,02			0,08889		0,15556		0,26667		0,27222		0,15556		0,03111		0,01
	0,00057			0,00127		0,00164		0,00247		0,00206		0,00105		0,00019		0,00005
Статистическая функция распределения вероятности	0,02			0,10889		0,26445		0,53112		0,80334		0,9589		0,99001		1
	20	35	60	70	80	90	100	110	120	130	140	150	160	170	180	200	220
	0,00004	0,00021	0,00186	0,00358	0,00607	0,00907	0,01194	0,01384	0,01413	0,01271	0,01007	0,00703	0,00432	0,00234	0,00112	0,00017	0,00002
	-3,44764	-2,91257	-2,0208	-1,66409	-1,30738	-0,95067	-0,59396	-0,23725	0,11946	0,47617	0,83288	1,18959	1,5463	1,90301	2,25972	2,97314	3,68656
	0,0003	0,0018	0,0217	0,0485	0,0951	0,1711	0,2743	0,4052	0,5478	0,6808	0,7967	0,8830	0,9394	0,9713	0,9881	0,9985	0,9999
	0,0214			0,0734		0,1792		0,2735		0,2489		0,1427		0,0487		0,0118
	0,0824			2,942		2,8067		0,1535		1,9664		1,043		5,718		0,2471
	0,0017			0,01379		0,00985		0,01668		0,00664		0,0195		0,00191		0,0001

Гистограмма и функция плотности вероятности



Рис.2.2.1

h_i(х_i)-гистограмма распределения кол-ва символов в сообщений

f(х)-функция плотности вероятности
Статическая и теоретическая функция распределения



Рис. 2.2.2

F^*(х)-статистическая функция распределения

F(х)-теоретическая функция распределения

2.3. Проверка гипотезы о предполагаемом законе распределения

с помощью критериев согласия Пирсона и Колмогорова
Проверим гипотезу о законе распределения.

По критерию согласия Пирсона вычислим величину (см. табл. 2.2.1) и

, находим 0,013.

Таким образом, p<0,1 , следовательно, экспериментальные данные противоречат гипотезе. Гипотезу нужно принять.
По критерию согласия Колмогорова рассчитываем :

, (см. табл. 2.2.1)



По таблице распределения Колмогорова находим

Таким образом, только по критерию согласия Колмогорова принимаем гипотезу о законе распределения.

3. 
   РАЗРАБОТКА АЛГОРИТМА УПРАВЛЕНИЯ СПИ ПО КРИТЕРИЮ МАКСИМАЛЬНОЙ ЁМКОСТИ ПУЧКОВ КАНАЛОВ
   
   1. 
      Маршрутизация потоков сообщений
      

Исходный граф СПИ с входными потоками сообщений представлен на рис.3.1.1.



Рис. 3.1.1. Исходный граф СПИ.
С учётом данных можно перейти к упрощённому графу СПИ.

Граф СПИ, с учётом данных, представлен на рис. 3.1.2.


Рис. 3.1.2. Итоговый граф СПИ.
Составим матрицу смежности:

1 2 3 4 5 6


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

Дерево путей из узла 4 в узел 2 представлено на рис. 3.1.3.


Рис. 3.1.3. Дерево путей из узла 4 в узел 2.


Дерево путей из узла 4 в узел 3 представлено на рис. 3.1.4.



Рис. 3.1.4. Дерево путей из узла 4 в узел 3




Дерево путей из узла 3 в узел 2 представлено на рис. 3.1.5.

Рис. 3.1.5. Дерево путей из узла 3 в узел 2.

2. 
   Математическая модель потоков сообщений
   

Запишем целевую функцию для максимального удовлетворения запросов на передачу сообщений.

,

Ограничения:

1. ;

2. Суммарные потоки сообщений по путям между каждой парой узлов 4-2 4-3 3-2 не должны превышать соответствующих входных потоков ().



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


Избавимся от избыточных условий:


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

.



где - свободные переменные;

- базисные переменные.

Для решения этой задачи воспользуемся симплекс-методом.

3. 
   Построение симплекс-таблицы
   

Запишем исходную симплекс-таблицу (см. табл. 3.3.1).
Таблица 3.3.1.

Исходная симплекс-таблица.

	с. чл.	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15	х16	х17	х18	х19	х20
F	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
Y1	50	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0
Y2	40	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	0	0	0	0
Y3	70	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1
Y4	45	1	0	0	0	0	0	0	0	1	1	1	0	0	1	0	1	0	0	0	1
Y5	35	0	1	1	1	0	0	0	1	0	0	0	0	0	1	0	1	0	0	0	0
Y6	20	1	1	1	1	0	0	0	1	1	1	1	0	0	0	0	0	0	0	0	1
Y7	30	0	1	0	0	0	1	0	0	1	0	0	0	1	0	1	0	1	0	0	0
Y8	20	0	0	1	0	1	0	0	0	0	1	0	0	1	1	0	0	0	1	0	0
Y9	55	0	0	0	1	0	0	1	0	0	0	1	0	0	0	1	1	0	0	1	0
Y10	50	0	0	1	1	0	1	0	0	0	1	1	1	0	0	0	0	0	1	1	1
Y11	50	0	0	0	0	1	1	1	0	0	0	0	1	1	1	1	1	0	0	0	1

4. 
   Расчёт на ЭВМ потоков сообщений
   

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

Если признак оптимального решения не выполняется, то требуется переразрешение таблицы. Итоговая симплекс-таблица, полученная в результате решения задачи на ЭВМ, представлена в таблице 3.4.1.


Приравняем нулю свободные переменные.



Теперь можно определить базисные переменные.

Значения х_i представлены в таблице 3.4.2.

Таблица 3.4.2.

Рассчитанные симплекс-методом потоки сообщений

Узел отправления и узел назначения	i	xi	Путь
4 – 2	1	18,8	4-1-2
	7	11,3	4-5-6-2
4 – 3	8	1,3	4-1-3
	12	12,5	4-5-3
	16	26,3	4-5-6-2-1-3
3 – 2	17	30	3-2
	18	20	3-5-2
	19	17,5	3-5-6-2

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

5. 
   Построение вторичного графа СПИ
   

Вторичный граф СПИ представлен на рис. 3.5.1. В нём учитываются только потоки сообщений не равные нулю.


Рис. 3.5.1. Вторичный граф СПИ

4. 
   РАЗРАБОТКА АЛГОРИТМА УПРАВЛЕНИЯ СПИ ПО КРИТЕРИЮ МАКСИМАЛЬНОЙ НАДЁЖНОСТИ
   

1. 
   Построение матрицы надёжных маршрутов (дистанционной таблицы)
   

На рисунке 4.1.1 представлен исходный граф СПИ с указанием надёжности его ветвей.


Рис. 4.1.1. Надёжность ветвей графа СПИ.
Методом Шимбела-Оттермана найдём пути между каждой парой узлов с максимальной надёжностью.

Составим матрицу ненадёжности





Будим возводить матрицу V в степень с помощью операций Шимбела-Оттермана до тех пор, когда матрица-результат перестанет изменяться или показатель степени достигнет значения 6.






Получили матрицу путей с минимальной ненадёжностью (матрицу надёжных маршрутов), так как .

2. 
   Построение маршрутной таблицы
   

Определим теперь конкретные надёжные пути, для этого составим модифицированную матрицу:

Построим маршрутную таблицу, используя формулу

С помощью таблицы 4.2.1 можно определить наиболее надёжный маршрут между каждой парой узлов.

Таблица 4.2.1.

Маршрутная таблица.

		Узлы назначения
		1	2	3	4	5	6	7
Узлы отправления	1		3	3		3	3
	2	1			5	5	6	5
	3	5	5		5	5	5	5
	4	1	5	5		5	5	7
	5	3	3	3	4		6	4
	6	2	2	5	5	5		7
	7	4	4	4	4	4	6

5. 
   ОПРЕДЕЛЕНИЕ ЁМКОСТИ ЗУ НА УЗЛАХ КОММУТАЦИИ
   

Определим потоки сообщений на основе таблице 3. 4. 2:



Определим расхождения с заданными значениями:



Для узлов получим:



Определим средние ёмкости ЗУ из расчёта на час работы:



Задана вероятность переполнения ЗУ - , тогда вероятность непереполнения -

По таблице нормального распределения для вероятности , математического ожидания и СКО определим величину . . Аналогично для вероятности , математического ожидания и СКО определим величину .

Итак,

ёмкость ЗУ 4^го узла за час работы (байт),

ёмкость ЗУ 3^го узла за час работы (байт).

ЗАКЛЮЧЕНИЕ
В данной курсовой работе проводился анализ и расчёт такой сложной системы как сеть передачи информации с коммутацией сообщений. На основе проведённой работы можно сделать вывод, что анализ и расчёт любой сложной системы является объёмной разноплановой работой, затрагивающей многие разделы математики. Это связано с тем, что исследуемая система должна решать множество задач.

Начальной стадией анализа является моделирование, причём можно видеть, что модели могут быть как детерминированные (при известных входных воздействиях), так и стохастические (при случайных входных воздействиях). В этом случае необходимо применять к анализу и расчёту сложных систем аппарат теории вероятностей. Сами модели могут быть чрезвычайно разнообразными, например, графовые, матричные, в виде систем дифферен-циальных и алгебраических уравнений и др. Методы, используемые в расчётах, также чрезвычайно разнообразны (методы линейного программирования (в нашем случае симплекс-метод для разработки алгоритма управления СПИ по критерию максимальной ёмкости пучков каналов), графовые методы (в нашем случае метод Шимбела-Оттермана для нахождения надёжных маршрутов) и др.).

ЛИТЕРАТУРА

1. 
   Давыдюк В. Б. Методические указания к курсовому проектированию по дисциплине «Автоматизированное управление в технических системах». – М.: МГУ ПС, 2002.
   
2. 
   Вентцель Е. С. Теория вероятностей. – М.: Высшая школа, 1999.
   
3. 
   Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся ВТУЗов. – М.: Наука, 1981.