MMPISiS

Лекция 7

Графические методы построения инфокоммуникационных сетей и систем (ИСС)

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

1. Системы массового обслуживания, которые базируются на результатах ТТТ (ТТТ изучает вероятностно временные характеристики процессов):

А) анализ входного потока Б) нагрузки телетрафика задачи анализа

В) качества обслуживания (потери)

Г)синтез новых систем с заданными параметрами

2.Графические модели. Они удобны для решения задач, связанные со структурой сетей.

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

Рассмотрим модель фрагмента сети в виде сети графа:

в12

			а2
	а1		в02		а3
		в01		в03
а7		в07	а0	в04	а4

в06

в45

в56

а5

а6

Граф состоит из множества вершин аi и множества ребер bij.

Число вершин графа n. В данной модели n=8, которое определяет количество узлов в сети.

Местоположение аi позволяет указать координаты той точки, в которой размещается узел.

Длина ребра bij определяет протяженность линии связи или ее пропускную способность или стоимость.

Этот граф считается удобной моделью для различных характеристик типов ИСС. Граф имеет 8 вершин и 9 ребер и является неориентированным.

Неориентированный граф хорошо отображает возможность использования линии связи в дуплексном режиме. А в ориентированном графе ребро будет иметь стрелку. Смешанные графы имеют ребра разных типов.

Если ребро начинается и заканчивается в одной и той же вершине, то оно образует петлю.

В теории сетей связи обычно используются графы без петель. Иногда петля бывает «полезной». Если вершина графа представляет конденсатор, то наличие петли отражает тот факт, что часть трафика замыкается внутри узла.

Обозначим ранг вершины R(ai) как число инцидентных (входящих/выходящих) ей ребер.

R(ai): min R(a3) = 1 max R(a0) = 6

Две вершины, соединенные ребром, называются смежными. Обозначим Mij – путь между двумя вершинами из ai до aj, который представляет собой упорядоченный набор ребер, который начинается в ai и заканчивается в aj. В любом пути ни одна вершина не повторяется.

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

Различают так же ранг пути R(Mij). Это число ребер между вершинами ai и aj. И эта вершина не может быть < 1.

МВК6

МВК5

МВК1

МВК4

МВК2

РК21

РТ211

МВК3	РК22
	РТ212
	РТ221

РТ222

МВК - мультиплексор РК-распределительных коробок, РТ – телефонные розетки

Рассмотрим сеть доступа ТФОП (телефонная сеть доступа). Созданные транспортные ресурсы могут использоваться и для других коммутируемых сетей. Структура представляет собой шесть мультиплексоров в объединении с оптоволоконным кабелем. Телефонные аппараты включаются в распределительные коробки и между РК и МВК используются двухразрядные физические сети.

Изобразим данную сеть в виде графа:

а3	а2

а1

а4			b61
		а6
			b6-61
			a61
			b61-611
		b6-62	a611
	а5	a62	a611
			a621

a622

Индексы, содержащие разное число цифр, указывают на то, что ребра проложены между разными уровнями иерархии. Фрагмент графа между вершинами a6 и а611 является типичным примером древовидной топологии.

При разработке модели телекоммуникационных сетей широко используются графы со следующими структурами:

1) Полно связная структура

2) Звездообразная структура

3) Сотовая структура

4) Решетчатая структура

1) В полно связной структуре, где все вершины соединены между собой число ребер M = N(N-1)/2, где N – вершины графа. Сеть с такой структурой отличается высокой надежностью, однако, она наиболее затратная по числу линий.

2)Структура звезда, где одна из вершин – центральная. Такая структура имеет небольшую суммарную длину N: M=N-1. Она используется для построения центральной части сетей и при небольшом количестве узлов ( до 10), а так же она используется при построении сельских телефонных сетей.

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

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

а)

а6

а1

а5	а2

а4

а3

Этим способом можно получить кольцевую и другие структуры, а также древовидную.

б)	а6	а2
	а5

а1

а3

а4

Граф может быть представлен матрицей. Например, графу с данной структурой соответствует матрица смежности

– 1 1 1 0 1 1 – 1 0 1 0

1 1 – 1 0 0 Са = 1 0 1 – 1 0

0 1 0 1 – 1

1 0 0 0 1 –

0 ставится если ребра нет между вершинами

1 – если ребро есть Вместо 1 в матрице могут быть расставлены иные вершины, к примеру, пропускные способности

ребер, их стоимость и другие атрибуты сети.

Лекция 8

Имитационное моделирование

Имитационное моделирование – это метод построения такой модели, которая описывает процессы так как они происходили бы в действительности.

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

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

Имитационные модели используются для экспериментирования средств, для проектирования анализа и оценки качества функционирования системы.

Кимитационному моделированию прибегают в следующих случаях:

1.Когда дорого и невозможно экспериментировать на реальном объекте.

2.Когда невозможно построить аналитическую модель в следствие нелинейности случайности происходящих в системе процессов.

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

системы.

Имитация – как метод решения нетривиальных задач появилась в 50-60-х годах прошлого века.

Можно выделить две разновидности имитации:

1.Метод Монте-Карло (метод статистических испытаний)

2.Метод имитационного моделирования (статистическое моделирование)

1.Метод Монте-Карло состоит из трех составляющих:

А) Моделирование случайных величин, подчиняющихся различным распределениям: равномерное, показательное, нормальное и др.

Существует множество способов получения случайных величин.

Равномерно распределенную случайную величину на отрезке [0,1) можно получить из дискретной случайной величины равновероятно принимающей 0 и 1. Например, с помощью датчика псевдослучайных чисел.

Работа с датчиком псевдослучайных чисел:

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

2.Моделирование системы массового обслуживания (максимально упрощается процесс обслуживания, сохраняя лишь существенное)

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

3.Определение точности и достоверности результатов моделирования. Общее время моделирования разбивается на n серий. В каждой серии проводится равное число испытаний m. Для каждой серии определяется экспериментальное значение исследуемой характеристики по формуле:

xi = ri /m

ri – число появлений исследуемого события

После завершения моделирования определяется n

				Σ xi
	МО:		=	i=0
		х
				n

1 D: Dx= n

n 2

Σ (xi – x)

i=0

Оценка точности и достоверности результатов проводится по некоторым критериям: Стьюдента, Хи-квадрат и др.

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

Существуют три подхода:

1.Агентное моделирование, которое используется для исследования децентрализованных систем, динамика, функционирования которого, определяется не глобальными правилами и законами, а, наоборот, какие

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

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

Объект обладает активностью, которую может принимать решение с некоторым набором правил может взаимодействовать с окружением и изменяться.

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

3.Системная динамика6 метод моделирования в котором для исследуемой системы строится график диаграммы причинных связей и влияние одних параметров на другие. Затем созданная на основе этих диаграмм модель

имитируется на компьютере.

4.

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

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