Метод машинного имитационного моделирования

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

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

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

Термин «имитационное моделирование» не очень уда­чен, так как имитация сама по себе есть моделирование, а моделирование — имитация. Тем не менее этот термин устойчиво «прижился» в специальной технической лите­ратуре и часто отождествляется с терминами «машинная имитация», «машинный имитационный эксперимент», «имитационный эксперимент на ЭВМ», «моделирование на вычислительных машинах», «статистическое модели­рование». Употребление последнего термина обусловле­но тем, что статистическое моделирование как метод ма­шинной реализации имитационных моделей систем, под­верженных случайным воздействиям, в настоящее время наиболее употребим, хотя в детерминированных случаях имитационные модели реализуются и другими методами (например, метод «Динамо», метод ситуационного управ­ления).

Статистическое моделирование представляет собой численный метод, дающий частное решение, отвечающее фиксированным значениям параметров системы, входной информации и начальным условиям. В основе его лежит процедура, применяемая для моделирования случайных величин и функций и носящая название метода ста­тистических испытаний (метод Монте-Карло),

Общая схема метода Монте-Карло может быть запи­сана в виде

_ . (2.6)

Результат ищется как математическое ожидание неко­торой случайной величины Y, которая чаще всего явля­ется неслучайной функцией случайной величины X, име­ющей распределение р(х). Нестрогое выражение «слу­чайная величина X имеет распределение р(х)» и запись X _ р(х) означают для непрерывной случайной величи­ны, что ее плотность вероятности равна р(х); для ди­скретной случайной величины функцию р(х) надо пони­мать как функцию вероятности. Для дискретной случай­ной величины интеграл (2.6) заменяется суммой у(х)р{х)_у в которой суммирование осуществляете;: по всем возможным значениям X. Функция у(х) может иметь несколько аргументов, т. е. зависеть от несколь­ких случайных величин. В таком случае запись (2.6) остается в силе, только интеграл надо считать многомер­ным, X рассматривать как вектор, а р(х)—как много­мерную плотность (или функцию) вероятности. Прибли­женная оценка неизвестного математического ожидания, совпадающая с искомым результатом, находится как среднее арифметическое результатов независимых опы­тов. Это отражено в правой части (2.6). По закону больших чисел среднее арифметическое сводится к мате­матическому ожида­нию. В каждом опыте разыгрывается реалиация х случайной величины X (в i-м опыте реализация х_i) в соответствии с распределением р(х) и вычисляется значение функции в виде y(х_i). Индекс i подчеркивает, что для каждой (i-й) реализации процесса аргу­менты, составляющие вектор X, имеют свои случайные значения. Вычисленное очередное значение y(x_i) добав­ляется к накапливаемой сумме у(х_i). На этом заканчи­вается очередной опыт. После того как проведено М опытов, вычисляется итоговая оценка . Опыты повторяются до тех пор, пока дисперсия оценки не cнизится до требуемой величины, зависящей от допустимой погрешности и коэффициента доверия. Проиллюстрируем суть метода Монте-Карло относительно простым примером. Пусть требуется оценить надежность системы (рис. 2.11). Система выполняет свою функцию, если работают цепочки блоков: 1, 2, 5, 7; 1, 3, 5, 7; 4, 6, 7. Какие-то блоки могут отказать. Каждый блок характеризуется временем безотказной работы .

Рис. 2.11. Блочная структура системы

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

= min {, max [min (,), min [max (,),]],} (2.7)

— время безотказной работы системы. В одном опыте разыгрывается значение в соответствии с . Через полученные реализации по формуле (2.7) вычисляем реализацию . Один опыт дает одну реализацию . Проводим М опытов (испытаний), полу­чаем «статистический» материал (выборку). Берем сред­нее арифметическое времени безотказной работы систе­мы _ср в качестве оценки надежности системы. При не­обходимости можно построить и закон распределения случайной величины .

Таким образом, испытания реальной системы заменены на испытания математической модели. Каждое испы­тание сопровождается расчетом. Поэтому имитационное моделирование и называют численным экспериментом на ЭВМ с математической моделью (модель выступает как объект испытания). При реализации испытания воз­можны и логические операции. И расчетные и логиче­ские операции реализуются на ЭВМ с помощью соответ­ствующих алгоритмов, которые в совокупности составля­ют определенный выше моделирующий алгоритм.

Структурная схема эксперимента по имитационному моделированию показана на рис. 2.12.

Традиционно модель рассматривается как «черный ящик», имеющий входы Х и выходы Y. В качестве входов подразумевают параметры входных сигналов (напри­мер, параметры входных сообщений — тип, категория срочности, длина, время возникновения сообщения), в качестве выходов — различные характеристики, интере­сующие разработчика.

После выбора X и Y определяется план эксперимен­та, т.е. процедура выбора входных параметров х₁, х₂,..., на которые желательно знать реакцию модели. Само вычисление значений у₁, у₂,... производится с помощью работы моделирующего алгоритма, позволяющего при заданных х₁, х₂, ... воспроизвести траекторию системы Z(t), noкоторой вычисляются показатели y_i. В блоке об­работки результатов происходит накопление сумм и ста­тистическая обработка. Выбор плана эксперимента за­висит от цели исследования. Если, например, интересует оптимизация некоторого критерия качества, то его зна­чения являются выходом, а план заключается в выборе оптимизирующей последовательности х₁, х₂, ... в соответ­ствии с определенным методом (например, градиентно­го поиска). Если необходимо выявить существенные па­раметры модели или выбрать структуру, то план заклю­чается в изучении влияния того или иного параметра или вида структуры на выход модели.

Для формирования реализаций случайных объектов (событий, функций, процессов) используется датчик слу­чайных чисел (ДСЧ), генерирующий в каждом опыте набор значений базовой случайной величины, на основе которых формируются реализации входных сигналов и влияющих внешних факторов. Функция влияния являет­ся характеристикой, отражающей действие внешних фак­торов на изменения параметров модели.

Рис. 2.12. Структурная схема эксперимента с моделью

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

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

При исследовании компьютерных сетей ставится задача определения большого числа пока­зателей их функционирования. Эффективная оценка каждого показателя требует своей модели, своего моде­лирующего алгоритма. Здесь возможны два подхода. Первый связан с построением универсальной автомати­зированной имитационной модели (УАИМ), модули ко­торой могут настраиваться с разной степенью детализации, определяемой требованиями решаемой задачи. При этом каждый модуль и схема сопряжения должны быть реализованы с максимальной степенью детализации сво­их микрооператоров и связей, УАИМ в этом случае пред­ставляет сама по себе сложную программную систему, разработка и отладка которой требует значительных ре­сурсов, да и сам процесс настройки отдельных отлажен­ных модулей по ходу имитации сопряжен с большими затратами машинного времени. Второй подход связан с разработкой библиотеки стандартных программных мо­дулей, реализованных с разной степенью детализации операторов. В этом случае каждому элементу соответст­вует множество модулей, характеристики каждого из которых строго соответствуют уровню решаемой задачи. При этом настройка моделей сводится к компоновке мо­дели из названных модулей, отвечающих условиям зада­чи исследования. Если в первом случае избыточность описания элементов внесена в модель системы и взаимо­действие элементов строится с учетом этой избыточно­сти, то во втором случае избыточность проявляется на уровне представления элементов и во взаимодействии не проявляется. В практике имитационного моделирования встречаются оба подхода.

При анализе вероятностно-временных характеристик устройств компьютерных сетей приходится сталкиваться с необходимо­стью оценки малых вероятностей, например вероятности отказа системы или вероятности ошибочного декодиро­вания. Для получения оценок таких вероятностей имита­ционную модель рекомендуется строить с использовани­ем методов ускоренного моделирования. Ускорить моделирование – значит добиться большей точ­ности при том же числе опытов или получить требуемую точность при меньшем числе опытов. Точность результа­та моделирования измеряется его дисперсией. Чем мень­ше дисперсия, тем выше точность. Поэтому методы ус­коренного моделирования чаще называют методами снижения дисперсии. Если при одном и том же числе опытов один метод дает дисперсию в k раз мень­шую, чем другой, значит для достижения заданной точ­ности оценки первый метод требует в k раз меньше опы­тов. Обычно ускоренные методы требуют на один опыт примерно столько же времени, сколько обычный метод, а иногда даже меньше. Следовательно, при сопоставле­нии одного метода моделирования с другим вместо за­трат машинного времени можно сравнивать дисперсии оценок при одном и том же числе опытов, если затраты времени на один опыт примерно одинаковы.

В практике ускоренного моделирования находят при­менение методы существенной выборки и расслоенной выборки. Идея метода существенной выборки заключа­йся в замене функции у(х) (2.6) другой функцией с тем же математическим ожиданием, но с меньшей ди­сперсией. Для сохранения математического ожидания необходимо соответственно изменить распределение ар­гумента. Схема метода существенной выборки выражается следующей записью

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

(2.7)

Желательно q(x) выбирать в виде

q(x) = q₀(x)=, (2.8)

где постоянная с находится из условия (2.7), т.е.

с=. (2.9)

При таком выборе q(x) оценка _q =₀ будет обладать наименьшей дисперсией. В действительности это возмож­но в принципе, но не реализуемо. Для нахождения q(x) в виде (2.8) необходимо вычислить константу с по формуле (2.9), а это задача не менее трудная, чем исходная, так как интеграл в (2.9) очень похож на искомый интеграл (2.6). Тем не менее, хотя оптимальное распределение (2.8) невозможно реализовать, его вид указывает, к чему надо стремиться при выборе q(x).

Чтобы уменьшить дисперсию оценки с помощью ме­тода существенной выборки, надо использовать функцию q(x), по возможности пропорциональную произведению и при этом удовлетворяющую условиям нормировки. Если исходное распределение р(х) предполага­ет примерно одинаковые вероятности выбора х во всем диапазоне возможных значений, то новое распределение q(x), пропорциональное , предписывает чаще выбирать существенные значения х — те, при которых осредняемая функция у(х) принимает большие значения; при этом учитывается и исходное распределение. Этим объясняется и название метода.

На практике, когда функция у(х) задается сложным алгоритмом, а аргумент х представляет собой вектор со случайным числом элементов, можно попытаться, не опираясь на приведенную выше рекомендацию, подобрать q(x) методом проб и ошибок. Поиск q(x) удобно вести в некотором классе распределений, завися­щих от параметра. Важно, чтобы случайные числа с та­ким распределением легко генерировались на ЭВМ. В широко распространенном случае, когда аргументы яв­ляются равномерно распределенными в интервале [0,1] случайными числами, удобно использовать семейство распределений с плотностью вероятности

Случайные числа с таким распределением получаются из равномерно распределенных чисел и по формуле

.

Значение параметра а, дающее наименьшую дисперсию оценки, ищется методом проб и ошибок на основе пред­варительных опытов.

Другим более распространенным методом ускоренно­го моделирования является метод расслоенной (страти­фицированной) выборки (рис. 2.13).

Рис. 2.13. Кусочно-непрерывная функция у(х) случайного аргумента х

Видно, что область значений аргумента х может быть разбита на участки так, что изменение функции в пре­делах участка значительно меньше, чем в пределах всей области. В таком случае целесообразно сначала осреднить функцию на каждом участке отдельно, а за­тем из частных средних получить общее среднее с учетом неодинаковых вероятностей участков. Предполагает­ся, что вероятности слоев p_r, r=легко вычисляются через заданное распределение р(х):

p_r = p(xB_r)= r=,

где B_r, r=— подмножества множества {х} значений аргумента х, называемые слоями (стратами).

Искомый результат представляется по формуле пол­ной вероятности через условные математические ожидания

опыты проводятся, как в обычной схеме (2.6), но по слоям. Для каждого слоя вычисляются оценки условных математических ожиданий (частные оценки)

где М_r — количество опытов в r-м слое.

В конце вычисляется суммарная оценка

Теория показывает: чтобы оценка имела меньшую дисперсию, чем обычная оценка (без расслоения), доста­точно, чтобы объем выборки рас­пределялся по слоям пропорцио­нально их вероятностям и чтобы условные средние по слоям не бы­ли одинаковы. При разбиениям по слоям надо стремиться к тому, что­бы средние по слоям как можно больше отличались друг от друга. В реальных задачах аргумент X является вектором и разбие­ние на слои надо проводить в многомерном пространстве. Обычно это делают с помощью некоторой функции h(х) называемой параметром расслоения. Разбивают множество значений h(х) на подмножества и считают х, относящимсяк слою B( r), если h(х). Зависимость осредняемой функции у(х)

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

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

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

Независимо от конкретных способов моделирования и разных модификаций в области машинной реализации моделирующих алгоритмов существуют некоторые об­щие методологические принципы имитационного модели­рования на ЭВМ. За основу такой методики обычно при­нимают следующие этапы имитационного моделирования: 1) изучение объекта моделирования; 2) формулировка задачи исследования; 3) построение математической мо­дели; 4) составление программы для ЭВМ; 5) оценка достоверности и пригодности модели; 6) планирование и обработка эксперимента.

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

На этапе построения концептуальной модели форму­лируется замысел модели. Основным содержанием этого этапа является переход от общего описания системы к ее математической модели, т. е. процесс формализа­ции. Этот этап является эвристическим, т. е. разработ­чик в основном руководствуется лишь собственной инту­ицией, опирающейся на накопленные знания и понима­ние процесса функционирования системы. Достоверность полученной новой информации зависит от адекватности модели, т. е. от того, насколько правильно и полно мо­дель отражает черты исследуемой системы, влияющие на искомый результат. Модель всегда дает упрощенное представление о системе. Говорить об адекватности мо­дели можно лишь по отношению к определенной задаче. Поэтому при построении концептуальной модели очень важно четко конкретизировать: что моделируется и для чего (с какой целью).

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

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

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

В процессе применения моделирования выявились многочисленные проблемы его использования, вызванные не способом записи модели, а ее содержанием. Карди­нальными являются вопросы адекватности, точности, чувствительности к вариациям различных параметров модели. Для созданной модели возникают проблемы использования ее «внутренних» свойств, таких, как устой­чивость, надежность, управляемость и др. Решение ука­занных проблем предполагает проведение целенаправленных экспериментов, использующих не только возможно­сти ЭВМ по имитации, но и аналитические результаты исследования соответствующих математических моде­лей, проведенные качественными методами. Перспективными с точки зрения ускорения мо­делирования являются комбинированные методы опреде­ления вероятностных характеристик, базирующиеся на совместном использовании оценок, полученных аналити­ческим и имитационным методами [5].

Литература

1. В.К. Морозов, А.В. Долганов Основы теории информационных сетей. Учеб. для студентов вузов. – М.: Высш. шк., 1987. – 271 с.

2. Г.Ф. Янбых, Б.А. Столяров Оптимизация информационных сетей. – М.: Радио и связь, 1987. – 232 с.

3. А.В. Бутрименко Разработка и эксплуатация сетей ЭВМ. – М.: Финансы и статистика, 1981. – 256 с.

4. Л.Р. Форд, Д.Р. Фалкерсон Потоки в сетях /перевод с английского И.А. Вайнштейна – М.: Мир, 1966. – 276 с.

5. Пугачев В.Н. Комбинированные методы определения вероятностных характеритсик. – м. Сов. Радио, 1973. – 226 с.