Файл: Инфокоммуникаций.pdf

37 стохастические.
Последние могут быть реализованы синхронным и асинхронным способами.
При синхронном способе один из элементов Q-схемы (И, Н или К) выбирается в качестве ведущего и по нему «синхронизируется» весь процесс моделирования.
При асинхронном способе - ведущий (синхронизирующий) элемент не используется, а очередному шагу моделирования (просмотру элементов Q- схемы) может соответствовать любое особое состояние всего множества элементов И, Н и К. При этом просмотр элементов Q-схемы организован так, что при каждом особом состоянии либо циклически просматриваются все элементы, спорадически - только те элементы, которые в этом случае могут изменить своё состояние. (просмотр с прогнозированием)
Прежде чем использовать какой либо язык для моделирования Q-схемы, необходимо глубже вникнуть в суть процесса построения и реализации М.А.
Пример. Рассмотрим Q-схему (рис. 3.4.):
Рис. 3.4 - Трехфазная Q-схема
Примем обозначения:
Р - вероятность потери заявки (Р=N1/(N1+N3)); t
m
- время появления очередной заявки из источника; t
k,j
- время окончания обслуживания заявки каналом Кк,j, k=1,2,3…; j=1,2…; z
i
, z k,j
- состояния накопителей и каналов обслуживания; t
n
- текущее время моделирования;
L
i
- ёмкость i-ого накопителя;
L
km
- число каналов в к-ой фазе;
N
1
, N
2
- число выходных заявок;
Т - интервал моделирования;
При имитации Q-схемы на ЭВМ требуется организовать массив состояний:

38 z
k,j
, t k,j, j=1, L
km
; z i
- число заявок в накопителе Hi; i=1,2; ti - i-ая заявка из источника. z
k,j
= {1- канал занят; 0 - канал свободен; 2 - заблокирован};
Укрупнённая схема детерминированного МА Q-схемы, построенного по
«принципу t» представлена на рис. 3.5.
Рис. 3.5 - Блок схема моделирования Q-схемы по принципу «

t»

39
А далее более подробно рассмотрены алгоритмы блоков 4-9.

40

41
Рис. 3.5 - Блок схема моделирования Q-схемы по принципу «

t»

42 3.2 Обобщенные модели А-схемы
Обобщенный подход базируется на понятии агрегативной системы (от англ, aggregate system), представляющей собой формальную схему общего вида, которую будем называть А-схемой. Этот подход позволяет описывать поведение непрерывных и дискретных, детерминированных и стохастических систем
Комплексное решение проблем, возникающих в процессе создания и машинной реализации модели, возможно лишь в случае, если моделирующие системы имеют в своей основе единую формальную математическую схему, т. е.
А-схему. А-схема должна выполнять несколько функций [11]:
 являться адекватным математическим описанием объекта моделирования;
 позволять в упрощенном варианте (для частных случаев) проводить аналитические исследования.
Представленные требования несколько противоречивы, но в рамках обобщенного подхода на основе А-схемудается найти между ними компромисс.
При агрегативном подходе первоначально дается формальное определение объекта моделирования - агрегативной системы. При агрегативном описании сложный объект (система) разбивается на конечное число частей (подсистем), сохраняя при этом связи, обеспечивающие их взаимодействие. В случае сложной организации полученных подсистем, подсистемы декомпозируются до уровней в которых они могут быть удобно математически описаны. В результате сложная система представляется в виде многоуровневой конструкции из взаимосвязанных элементов, объединенных в подсистемы различных уровней.
Элементом А-схемыявляется агрегат. Связь между агрегатами (внутри системы S и с внешней средой E) осуществляется с помощью оператора сопряжения
R. Агрегат может рассматриваться как А-схема,т. е. может разбиваться на элементы (агрегаты) следующего уровня.
Характеристиками агрегата являются множества моментов времени Т,
входных X и выходных Y сигналов, состояний Z в каждый момент времени t.
Пусть переход агрегата из состояния z(t
1
) в состояние
2 1
( )
( )
z t
z t


происходит за малый интервал времени

z. Переходы из состояния z(t
1
) в z(t
2
) определяются внутренними параметрами агрегата
( )
h t
H

входными сигналами
( )
x t
X

.
В начальный момент времени t
0
состояния z имеют значения, равные z°, т. е. z°=z(t
0
), которые задаются законом распределения L [z(t
0
)]. Пусть изменение состояния агрегата при входном сигнале х
п
описывается случайным оператором V.

43
Тогда для момента времени
n
t
T

при поступлениивходного сигнала х
n
состояние определяется (3.1).


(
0)
, ( ),
n
n
n
n
z t
V t z t
x


(3.1)
Если на интервале времени (t
n
, t
n
+i) нет поступления сигналов, то для
1
( ,
)
n
n
t
t t


состояние агрегата определяется случайным оператором U , можно записать (3.2)


( )
, , (
0)
n
n
z t
U t t z t


(3.2).
Так как на оператор U не накладываются ни какие ограничения, то допустимы скачки состояний

z в моменты времени, не являющимися моментами поступления входных сигналов x.
Моменты скачков

z называются особыми моментами времени t
s
, состояния z(t
s
) - особыми состояниями А-схемы.Для описания скачков состояний

z в особые моменты времени t
s
используется случайный оператор
W, которыйпредставляет собой частный случай оператора U (3.3).


(
0)
, ( )
z t
W t
z t





(3.3).
На множестве состояний Z выделяется такое подмножество Z
(Y)
, что если z (t

) достигает Z
(Y)
, то это состояние является моментом выдачи выходного сигнала. Выходной сигнал можно описать оператором выходов
(3.4)


, ( )
y
G t
z t



(3.4).
Агрегатомбудем понимать любой объект, который описывается следующим образом (3.5).
( )
,
, , ,
,
, , ,
,
Y
n
A
T X Y Z Z
H V U W G


(3.5).
Вопросы для самопроверки по разделу 3:

1. В чем заключается метод имитационного моделирования?
2. Поясните моделирующий алгоритм, который реализует принцип постоянного приращения модельного времени.
3. Перечислите измеряемые характеристики моделируемых систем.
4. Охарактеризуйте методы определения характеристик моделируемых систем.

44 4 Моделирование случайных воздействий
4.1 Моделирование случайных воздействий
В моделировании систем методами имитационного моделирования, существенное внимание уделяется учету случайных факторов и воздействий на систему. Для их формализации используются случайные события, дискретные и непрерывные величины, векторы, процессы.
Формирование реализации случайных объектов любой природы сводится к генерации и преобразованию последовательностей случайных чисел.
В практике имитационного моделирования систем на ЭВМ ключевым факторам является оптимизация алгоритмов работы со случайными числами.
Таким образом, наличие эффективных методов, алгоритмов и программ формирования, необходимых для моделирования конкретных систем последовательностей случайных чисел, во многом определяет возможности практического использования машинной имитации для исследования и проектирования систем.
4.2 Особенности моделирования случайных событий
Важной задачей в практике имитационного моделирования систем на
ЭВМ является расчёт случайных величин. В языках программирования существуют датчики равномерно распределённых псевдослучайных величин в интервале {0,1}. Остановимся на вопросах преобразования последовательности псевдослучайных величин {Xi} в последовательности {Yi} с заданным законом распределения и моделировании различных случайных событий.
Пусть имеются случайные числа xi, т.е. возможные значения случайной величины , равномерно распределённой в интервале {0,1}. Необходимо реализовать случайное событие А, наступающее с заданной вероятностью Р.
Определим А как событие, состоящее в том, что выбранное значение xi удовлетворяет неравенству: x i
Р.
Тогда вероятность события А будет:
P A
dx
p
p
( ) 


0

45
Противоположное событию А состоит в том, что xi>р. Тогда
P A
P
( )  
1
Процедура моделирования состоит в этом случае в выборе значений x i
и сравнение их с р. При этом, если условие (1) удовлетворяется, то исходом испытания будет событие А.
Таким же образом можно рассмотреть группу событий. Пусть А1,
А2…Аn – полная группа событий, наступающая с вероятностями Р1, Р2, … Рn соответственно. Определим Аm как событие, состоящее, в ом, что выбранное значение xi случайной величины  удовлетворяет неравенству: lm-1k
i
i
k
l
p



1
Тогда
P
dx
l
l
m
m
A
P
m
m
(
) 



1
Процедура моделирования испытаний в этом случае состоит в последовательности сравнений случайных чисел x i
со значениями l k
При моделировании систем часто необходимо осуществить такие испытания, при которых искомый результат является сложным событием, зависящим от 2-х и более простых.
Вопросы для самопроверки по разделу 4:
1. Поясните принцип вычисления непрерывных случайных величин.
2. Поясните принципы преобразования случайных величин.
3. Охарактеризуйте метод исключений, применяемый для моделирования непрерывных случайных величин.
4.

Каким образом осуществляется моделирование нормально распределённой случайной величины?

46 5 Моделирование систем с использованием типовых математических схем и автоматизированных программ
5.1 Имитационное моделирование систем массового обслуживания
Одним из методов исследования сложных систем, в том числе, и систем массового обслуживания
(СМО) является метод имитационного моделирования, когда модель (как следует из названия вида моделирования) имитирует работу реальной системы, т.е. модель воспроизводит процесс функционирования реальной системы во времени.
Любая система, как известно, представляет собой совокупность взаимосвязанных элементов и, следовательно, построение ее адекватной имитационной модели предполагает имитацию процесса функционирования каждого отдельного элемента системы с обязательным сохранением логики и правил взаимодействия и развития составляющих систему элементов, как во времени, так и в пространстве (в том числе последовательность и параллелизм их во времени).
Основное преимущество имитационного моделирования перед другими видами моделирования (например, аналитическим) состоит в универсальности в смысле возможности исследования любых достаточно сложных систем, с учетом таких факторов и условий, которые трудно или вообще невозможно учитывать при аналитическом моделировании. Поэтому во многих случаях имитационное моделирование становится наиболее эффективным, а часто и практически единственно доступным методом исследования систем. Например, результативный анализ СМО типа G/G/N аналитическими методами невозможен, в то время как такой анализ методами имитационного моделирования не представляет особой сложности.
При исследовании систем со стохастическим характером функционирования (СМО являются системами такого типа) результаты, полученные при единичном "прогоне" имитационной модели (при единичном воспроизведении на имитационной модели процесса функционирования системы), носят частный характер. Следовательно, для того, чтобы найти одну оценку (одно значение) какой-либо характеристики функционирования системы необходимо многократно "прогонять" имитационную модель
(необходимо получить множество результатов) с последующей статистической

47 обработкой полученных данных. Поэтому в имитационной модели должны быть предусмотрены средства сбора и средства последующей статистической обработки данных, полученных в ходе моделирования по интересующим характеристикам системы. Например, моделирование случайной величины Y, распределенной по экспоненциальному закону
t
e
)
y
(
F



 1
с параметром , предполагает выполнение следующих действий:
1) розыгрыш равномерно распределенного случайного числа x[0,];
2) определение соответствующего значения





/
x
ln
)
x
(
F
y
1
Единичная реализация этой элементарной имитационной модели из двух действий дает одно значение случайной величины Y. Если задача (цель) моделирования состоит в оценке среднего значения
Y
, то необходимо добавить в модель дополнительное (третье) действие S = S + y для накопления суммы случайных величин (средство сбора) и многократно реализовать полученную модель. В конце моделирования в качестве оценки для
Y
принять отношение
S/N (средство обработки), где N – общее число реализаций модели.
Если необходимо построить (найти) функциональную зависимость среднего значения
Y
, например, от параметра , то для множества точек этой зависимости нужно проделать каждый раз всю описанную выше процедуру моделирования, сбора и обработки данных. Даже в такой простой задаче очевидным образом проявляется присущий имитационному моделированию недостаток — это его трудоемкость.
5.2 Действия и события в системах
Процесс функционирования системы - это последовательная смена состояний системы во времени или другими словами, процесс функционирования системы - это переход ее из одного состояния в другое.
Причина перехода системы из состояния в состояние называется событием, которое является, в свою очередь, следствием начала или окончания соответствующего действия.
Рассмотрим действия и события, имеющие место в системах на примере
СМО типа G/G/1, где под состоянием системы понимается число заявок k, находящихся в ней в данный момент времени.
Хронологическая последовательность действий и событий, имеющих место в общем случае в такой СМО при прохождении через систему одной заявки (одного элемента).
Различают два вида событий:
1) основные (особые) события;

48 2) вспомогательные (второстепенные) события. Основным событием называется событие, наступление которого приводит к изменению состояния системы.
Именно основное событие имелось в виду при определении события как причины перехода системы из одного состояния в другое. Очень часто при имитационном моделировании дается другое определение основного события как события, время наступления которого можно планировать (предсказать) заранее, т.е. рассчитать его можно до фактического возникновения события.
Любое событие, не являющееся основным, называется вспомогательным
(второстепенным).
Вспомогательные события являются следствием возникновения основных событий и, следовательно, зависимы от них и наступают тогда же, когда и основные.
Для рассматриваемой нами системы G/G/1 такими параметрами являются интервалы поступления и длительности обслуживания заявок. Очевидно, что по истечении интервала поступления и длительности обслуживания наступают соответственно события «прибытие заявки» и «окончание обслуживания».
Именно эти два события и являются основными в рассматриваемой системе, и появление их вызывает очевидные переходы системы из состояния в состояние.
Все другие события являются вспомогательными. Так, события «начало обслуживания» и «занятие прибора» являются следствием наступления либо события «приход заявки» (если система свободна), либо события «окончание обслуживания» (для предыдущей заявки). В свою очередь, события
«освобождение прибора» и «уход из системы» являются следствием возникновения события «окончание обслуживания».
Ни одно вспомогательное событие, очевидно, не приводит к изменению состояния системы. Таким образом, процесс функционирования системы, будучи процессом перехода из состояния в состояние, можно представить как упорядоченную во времени последовательность основных событий, происходящих в системе и переводящих ее из одного состояния в другое. Для поддержания этой хронологической последовательности основных событий в модели используется время.
5.3 Модельное время
Имитационное моделирование, как правило, проводится с использованием средств вычислительной техники в соответствии с программой, реализующей последовательность возникающих в системе

49 основных событий, т.е. соответствующий процесс функционирования системы.
При этом несколько часов, суток, лет работы реальной системы моделируется за несколько секунд, минут, часов работы компьютера.
При имитационном моделировании различают три вида времени.
1. Время реальной системы - это время, в котором «живет», функционирует моделируемая система.
2. Модельное время - это «искусственное» время, в котором «живет» модель или другими словами это время, которое является имитацией, прообразом (моделью) времени реальной системы.
3. Реальное время - это время, в котором живет исследователь, компьютер или другими словами это время необходимое для моделирования (затратное время).
Для нас наибольший интерес представляет модельное время. Для того, чтобы вести отсчет модельного времени и обеспечить правильную хронологическую последовательность наступления основных событий в имитационной модели используется так называемый таймер модельного времени, которая представляет собой переменную для хранения (фиксации) текущего значения модельного времени.
В процессе моделирования системы, таймер модельного времени, безусловно, должен постоянно корректироваться в соответствии с теми основными событиями, которые возникают в реальной системе. При этом существуют два способа (два принципа) коррекции значения таймера модельного времени:
1) коррекция с постоянным шагом (принцип t);
2) коррекция с переменным шагом (принцип z).
В первом случае при каждой коррекции модельное время увеличивается на одно и то же значение t, выбираемое перед началом моделирования, а во втором случае значение приращения таймера каждый раз является случайной, а, значит, переменной величиной.
5.4 Логическая схема имитационной модели
Используя изложенные выше положения, разработаем обобщенную логическую схему имитационной модели простейшей СМО типа G/G/1, которую затем, зная стандартные процедурные языки программирования, можно реализовать на компьютере. Разработку схемы будем вести при следующих условиях.

50
Заданы функции распределения A(t) и B(t) для интервалов поступления и длительностей обслуживания заявок, т.е. СМО полностью формализована.
В системе соблюдается условие существования стационарного режима, т.е. условие, что загрузка  = b/a < 0, где а и b – средние значения соответственно интервалов поступления и длительностей обслуживания.
В начале моделирования система свободна.
Задано время моделирования Т и в общем случае, когда моделирование завершается, система может быть не свободна.
Дисциплиной обслуживания является дисциплина FIFO.
В результате моделирования определяются следующие характеристики функционирования СМО: а) загрузка системы ; б) среднее время ожидания ; в) средняя длина очереди l; г) среднее время пребывания u; д) среднее число заявок в системе m; е) максимальная длина очереди Nqmax.
5.5 Планирование основных событий
Для рассматриваемой системы G/G/1, как отмечалось ранее, основными событиями являются события «прибытие заявки» и «окончание обслуживания», которые «связаны» соответственно с интервалом поступления и длительностью обслуживания заявки. Ранее также отмечалось, что основные события можно планировать заранее. Что означает это утверждение?
Суть этого утверждения состоит в том, что: а) зная функцию распределения A(t) интервалов поступления, при имитационном моделировании в момент прихода очередной заявки можно определить момент поступления следующей заявки; б) аналогично, зная функцию распределения В(t) длительностей обслуживания, при имитационном моделировании в момент начала обслуживания заявки можно определить момент его окончания.
Необходимо планировать приход следующей заявки. Для этого сначала нужно разыграть (первый этап) случайную величину в соответствии с функцией распределения A(t) интервалов поступления, используя метод обратной функции.