Курсовая работа управление сложными системами тема 2 Управление сетью передачи информации с коммутацией сообщений

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

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



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

АВТОМАТИЗИРОВАННОЕ УПРАВЛЕНИЕ

В ТЕХНИЧЕСКИХ СИСТЕМАХ

Курсовая работа

УПРАВЛЕНИЕ СЛОЖНЫМИ СИСТЕМАМИ
Тема 2

Управление сетью передачи информации

с коммутацией сообщений.

Вариант 16

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

Габорак Е.В. Проверил : доц. Давыдюк В.Б.

Москва 2000
Рабочее задание

1. 
   По статистическим данным построить гистограмму количества символов в сообщении. Проверить гипотезу о нормальности закона распеделения количества символов с помощью критериев Пирсона и Колмогорова. Получить оценки максимального правдоподобия для параметров нормального закона распределения.
   
2. 
   Разработать алгоритм оптимального распределения потоков информации с помощью симплекс-метода линейного программирования. Построить граф вторичной сети СПИ при оптимальном распределении потоков информации.
   
3. 
   Определить емкости ЗУ на узлах коммутации исходя из заданной вероятности переполнения ЗУ в час наибольшей нагрузки.
   
4. 
   Построить доверительный интервал для оценок параметров закона распределения, принимая  =  = 0,95.
   

Исходные данные

1. 
   Схема СПИ.
   

2. 
   Матрица потоков сообщений [] : ₄₂ = 50, ₄₃ = 40. ₃₂= 70
   
3. 
   T=90 ,P0=0,02.
   
4. 
   Матрица емкостей ветвей : В = {}.
   
5. 
   Диапазон длительностей сообщений t_i = {0200, 200500, 500800, 8001100, 11001440}.
   
6. 
   Количество наблюдений в диапазонах : m_i = {18, 80,140,240, 245,140,28,9}
   

7. Интервалы количества символов.(20-60,60-80,80-100,100-120,120-140,140-160,160-180,180-220)

1. 
   По статистическим данным построить гистограмму количества символов в сообщении.
   

Таблица 1

ti	0  200		200  500		500  800		800 1100		1100  1440
	90		330		640		950		1260
mi	300		135		24		6		2
	0,6424		0,2891		0,0514		0,0128		0,0043
hi	0,00321		0,00096		0,00017		0,00009		0,00001
	0,6424		0,9315		0,9828		0,9957		1,0000
f(t)	0	0,0049	200	0,0018	500	0,0004	800	9,7210-5	1100	2,2410-5
	200	0,0018	500	0,0004	800	9,7210-5	1100	2,2410-5	1440	4,2210-6
F(t)	0	0	200	0,7447	500	0,9537	800	0,9862	1100	0,9958
	200	0,7447	500	0,9537	800	0,9862	1100	0,9963	1440	0,9998
	0,6247		0,2864		0,0664		0,0153		0,0037
	0,2344		0,1726		1,594		0,1806		0,0428
-	0,1023		0,0222		0,0034		0,0006		0,0002

(1.1.1)

(1.1.2)

(1.1.3)

(1.1.4)

Данные, рассчитанные по формулам (1.1.2), (1.1.3) и (1.1.4) , занесем в сводную таблицу 1. Построение гистограммы распределения длительности сообщений h_i(x_i) см. рис. 1.

2. 
   Вывести и рассчитать оценку максимального правдоподобия для параметра экспоненциального закона распределения.
   

Так как закон распределения – экспоненциальный, то функция плотности вероятности f(t) и функция распределения вероятности F(t) имеют вид :

(1.2.1)

(1.2.2)

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

(1.2.3)

где k = 5 – количество диапазонов длительностей сообщений.

Прологарифмируем выражение (1.2.3) :

(1.2.4)

Исследуем выражение (1.2.4) на экстремум. Для этого возьмем производную по ^* и приравняем полученное выражение к нулю :

(1.2.5)

Преобразуем выражение (1.2.5) , и выразим из него :

(1.2.6)

Тогда, с учетом данных из таблицы 1, получим оценку максимального правдоподобия для параметра экспоненциального закона распределения :

(1.2.7)

Подставив значение в (1.2.1) и (1.2.2), получим :

(1.2.8)

(1.2.9)

Рассчитанные по формулам (1.2.8) и (1.2.9) значения запишем в таблицу 1.

Построим гистограмму распределения длительности сообщений h_i(t_i) и функцию плотности вероятности f(t) на рисунке 1.

Гистограмму (t_i) и функцию распределения вероятности F(t) построим на рисунке 2.



Рис. 1.2.1



Рис. 1.2.2

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

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

(1.3.1)

(1.3.2)

где (1.3.3)

Воспользуемся данными из таблицы 1, а также результатами расчетов, полученными в (1.2.7). Получим :

(1.3.4)

(1.3.5)

(1.3.6)

(1.3.7)

(1.3.8)

Подставив (1.3.4), (1.3.5), (1.3.6), (1.3.7), (1.3.8) в (1.3.1), получим :

(1.3.9)

(1.3.10)

(1.3.11)

(1.3.12)

(1.3.13)

Значение = 2,2246. Воспользовавшись таблицами распределения Пирсона «» , найдём = 0,5276 > 0,1, значит можно сделать вывод о том, что по критерию согласия Пирсона «» гипотеза об экспоненциальности закона распределения принимается.

Проверим гипотезу об экспоненциальности закона распределения по критерию согласия Колмогорова. Для этого необходимо вычислить величину (1.3.14)

По таблице 1 находим : D = 0,1023.

Воспользовавшись (1.1.1) и значением D, рассчитаем :

(1.3.15)

По таблице определяем : P = 0,9999 . Это значение больше 0,1, значит гипотеза об экспоненциальности закона распределения принимается по критерию согласия Колмогорова.

Т.к. гипотеза принята по обоим критериям, то можно сделать вывод о том, что гипотеза верна, и закон распределения действительно является экспоненциальным.
2.1. Методом динамики средних рассчитать нагрузку, создаваемую потоком сообщений на узле УК4 в УК2.

Для определения нагрузки необходимо сначала составить граф состояний одного источника. Источник может либо передавать информацию (назовем это состояние рабочим и обозначим «1»), либо не передавать информацию (назовем это состояние нерабочим и обозначим «0»). Источник может переходить из одного состояния в другое : из «1» в «0» с интенсивностью ₁₀, из «0» в «1» с интенсивностью ₀₁. Численные значения этих интенсивностей равны :

(2.1.1)

(2.1.2)

Построим граф состояний источника на рисунке 2.1.1



Рис. 2.1.1
Найдем ₁(t) – среднее количество источников, находящихся в состоянии «1», т.е. передающих сообщения. При этом искомой величиной нагрузки ₄₂ будет установившееся значение ₁(t), т.е. значение ₁(t) через время , которое определим далее.

Для этого составим уравнения динамики средних, которые получаются из уравнений Колмогорова путем умножения левой и правой частей на N₄.

(2.1.3)

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

(2.1.4)

Из уравнения (2) выразим :

(2.1.5) и подставим выражение (2.1.5) в уравнение (1) системы (2.1.4) :

(2.1.6)

Преобразуем выражение (2.1.6) :

(2.1.7)

Проинтегрировав выражение (2.1.7) и выразив из него ₁ , получим:

(2.1.8)

Подставив в (2.1.8) исходные данные, (2.1.1) и (2.1.2), получим :

(2.1.9)

Отсюда время переходного процесса :

(2.1.10)

Т.к. время переходного процесса  = 750 [с], то для построения графика преобразуем формулу (2.1.9), выразив значение интенсивности (19 [1/ч]) через величину [1/c]. Округлим значение 131,58 до 132.

(2.1.11)

Установившееся значение среднего количества работающих источников . Эта величина и есть значение потока сообщений ₄₂ = 132.

2.2. Рассчитать дисперсию количества одновременно передаваемых сообщений.

Источник передает сообщения, когда он находится в состоянии «1», т.е. в рабочем состоянии. Тогда дисперсия вычисляется по формуле :

(2.2.1)

Как видно из (2.2.1), дисперсия является функцией времени. Рассчитаем дисперсию в установившемся режиме, т.е. при t=. В установившемся режиме значение равно 132. Подставим это значение в (2.2.1), получим :

=11,2² (2.2.2)

2.3. Построить графики плотности распределения вероятностей количества одновременно передаваемых сообщений.

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

Так как количество источников сообщений N₄ = 2500, т.е. достаточно большое число, то можно сказать, что количество одновременно передаваемых сообщений распределяется по нормальному закону. Тогда плотность распределения вероятности определяется по формуле :

(2.3.1)

Где ² = Д{х₁(t)} = 125. (2.3.2)

Таким образом, при х₁ = ₁ = 132, получаем :

(2.3.3)

Определим величину «3». Согласно (2.3.2), получаем :

3 = (2.3.4)

Качественно построим график плотности распределения. Для этого воспользуемся (2.3.3) и (2.3.4).



Рис. 2.3.1.

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

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

Из узла 3 в узел 2 : ₃₂ = 70

Из узла 4 в узел 3 : ₄₃ = 40

Из узла 4 в узел 2 : ₄₂ = 50

Чтобы построить целевую функцию, необходимо определить все возможные пути 32, 43 и 42. Чтобы найти эти пути, составим матрицу смежностей для исходной схемы СПИ.



Рис. 3.1.1.

Согласно рис. 3.1.1, матрица смежностей (С) имеет вид :

(3.1.1)

По матрице смежностей построим деревья путей для следующих узлов :

Дерево путей для M32.



Рис. 3.1.2.

Дерево путей для M43.



Рис. 3.1.3.

Дерево путей для узла M42.



Рис. 3.1.4.

Запишем целевую функцию, которую необходимо максимизировать.

(3.1.2)

Так как необходимо передать как можно больше сообщений, то

(3.1.3)

Запишем ограничения :

(₁₅) (3.1.4)

(₂₃) (3.1.5)

(₄₂) (3.1.6)

Ограничения (3.1.4), (3.1.5) и (3.1.6) вызваны тем, что нет необходимости передавать из М3 в М2 больше, чем ₄₂ = 50 сообщений. Аналогично ₄₃ и ₃₂.

Следующие ограничения связаны с емкостями линий связи. Емкости линий связи (ветвей) заданы в исходных данных в виде матрицы b.

Ветвь	Ограничение
1-2		(3.1.7)
1-4		(3.1.8)
2-3		(3.1.9)
4-3		(3.1.10)
2-4		(3.1.11)

Так как поставленная задача не является основной задачей линейного программирования, то необходимо привести ее к виду основной, т.е. устремить целевую функцию к минимуму, и записать ограничения в виде равенств. Запишем новую целевую функцию : F’ = -F. Тогда :

(3.1.12)

Устремим эту целевую функцию к минимуму :

Преобразуем ограничения (3.1.4) – (3.1.11) :

(3.1.13)

(3.1.14)

(3.1.15)

(3.1.16)

(3.1.17)

(3.1.18)

(3.1.19)

(3.1.20)

При этом все y_i  0 (3.1.25)

Таким образом, мы получили основную задачу линейного программирования.

С учетом (3.1.13) – (3.1.20) составим симплекс-таблицу, в которой свободными переменными будут Х_{i j}, а базисными y_i. Для переразрешения симплекс-таблицы воспользуемся программой «simplex».

Таблица 3.1.1.

Симплекс-таблица

	С.ч.	х1	х2	х3	х4	х5	х6	Х7	х8	х9
F’	0	1	1	1	1	1	1	1	1	1
y1	55	1	1	1	1	1	1	0	0	0
y2	40	0	0	0	0	0	0	1	1	1
y3	132	0	0	0	0	0	0	0	0	0
y4	20	1	1	0	0	0	0	1	1	0
y5	25	0	0	1	1	0	0	1	0	0
y6	15	0	0	0	0	1	1	0	1	0
y7	20	1	0	1	0	1	0	0	0	1
y8	15	0	1	1	0	1	0	0	0	0

Переразрешив данную таблицу, получим следующие решения :

Таблица 3.1.2

15	23	42
Х11 = 5 Х12 = 0 Х13 = 0 Х14 = 5 Х15 = 2 Х16 = 0	Х21 = 0 Х22 = 5 Х23 = 0 Х24 = 0 Х25 = 0	Х31 = 3 Х32 = 5 Х33 = 5 Х34 = 8 Х35 = 10

Поясним полученное решение. Х_{i j} = 0 означает, что по данному пути не передаются сообщения, т.е. данный путь не является рациональным. Если Х_{i j}  0, это значит, что по данному пути передается определенное количество сообщений. Данное распределение потоков сообщений является оптимальным, хотя и не обеспечивается требуемое количество сообщений. Требовалось передавать 55 + 40 + 132 = 227 сообщений, а реально передаем 48 сообщений. Это объясняется тем, что пропускная способность (емкость) линий не позволяет пропускать большее количество сигналов одновременно.
3.2. Построить граф вторичной сети СПИ при оптимальном распределении каналов.

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

Таблица 3.2.1.

Путь	Количество сообщений, Х
1-2-3-4-5	5
1-3-4-5	5
1-4-3-2-5	2
2-1-4-3	5
2-3	5
4-1-2	3
4-1-3-2	5
4-3-1-2	5
4-3-2	3
4-5-2	10

Построение требуемого графа – см. приложение 1. На рисунке в приложении 1 :



Рис. 3.2.1.

(СМ. Visio).

4. Построить доверительный интервал для оценок параметров закона распределения, принимая  =  = 0,95

Рассчитаем математическое ожидание оценки параметра закона распределения :

(4.1)

Согласно формуле (1.2.6), значение математического ожидания оценки равно самой оценке, т.е. . Следовательно, (4.2)

Рассчитаем дисперсию оценки параметра закона распределения :

(4.3)

При этом значение дисперсии средней длительности сообщений рассчитывается по формуле :

(4.4)
Подставим (4.4) в (4.3) :

(4.5)

Воспользуемся данными из таблицы 1, и рассчитаем :

== 0,0135

Рассчитаем доверительный интервал для :

(4.6)

где определяется с помощью таблиц нормального распределения для заданной вероятности  = 0,95.

Воспользовавшись таблицами нормального распределения, найдем значение = 0,2603.

Тогда доверительный интервал будет :

, при этом  = 0,0014.

Построим доверительный интервал :


Рис. 4.1