АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра автоматической электросвязи

 

 

 

МОДЕЛИРОВАНИЕ СИСТЕМ ТЕЛЕКОММУНИКАЦИЙ

Конспект лекций

для студентов всех форм обучения специальности

 050719 – Радиотехника, электроника и телекоммуникации

 

 

Алматы 2009 

СОСТАВИТЕЛИ: К. Х. Туманбаева, Э.М. Лещинская.  Моделирование систем телекоммуникаций. Конспект лекций  для студентов  всех форм обучения специальности 050719 – Радиотехника, электроника и телекоммуникации. - Алматы: АИЭС, 2009.- 50с.

 

Приведен краткий курс лекций по дисциплине «Моделирование систем телекоммуникаций» для специальности «Радиотехника, электроника и телекоммуникации». Изложены основные положения аналитического и имитационного моделирования систем связи. Аналитическое моделирование  осуществляется с применением математического аппарата теории массового обслуживания. Система моделирования GPSS World использована при имитационном моделировании телекоммуникационных систем.

Введение

         Конспект лекций   преследует  цель  краткого изложения теоретических основ дисциплины "Моделирование систем телекоммуникаций" для освоения студентами современной технологии аналитического моделирования и имитационных исследований, приобретения  знаний по разработке и исследованию имитационных моделей при работе на базе системы моделирования GPSS World.

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

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

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

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

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

В соответствии с учебным планом для данной дисциплины отводится 3 кредита, всего 135 часов, из них для аудиторных занятий - 56, для самостоятельной работы – 39 час.

 

Курс

Семестр

Аудит.

занятия

Лекции

Практ.

занятия

Лаборат.

работы

Курсовая

работа

Экзамен

3

6

56

24

16

16

6

6

 

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

 

Количество кредитов

Курс

Аудит.

занятия

Лекции

Практ.

занятия

Лаборат.

работы

Курсовая

работа

Экзамен

3

3

32

10

10

12

3

3

  

Лекция 1.  Моделирование систем

 

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

      Содержание:

а) цели и задачи дисциплины;

б) основные понятия теории моделирования систем;

в) использование моделирования при исследовании и проектировании сетей и систем телекоммуникаций;

г) моделирование случайных чисел с заданными законами распределения;

          д) этапы математического моделирования. 

Основным современным методом исследования телекоммуникационных систем (ТС) на всех стадиях их разработки, проектирования и модернизации является моделирование.

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

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

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

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

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

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

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

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

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

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

Итак, имитационное моделирование в области телекоммуникаций применяется, в основном, в следующих трех случаях:

а) при исследовании эксплуатируемой системы коммутации или сети связи; для определения пропускной способности, характеристик качества обслуживания;

б) при проектировании; можно определить структурные оптимальные параметры, апробировать алгоритмы;

в) при создании обучающих тренажеров.

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

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

В 1949 году в США была опубликована научная статья «Метод Монте-Карло». Эту дату принято считать годом рождения имитационного или статистического моделирования, который иногда также называют методом Монте-Карло. Авторами статьи были американские математики Дж. Нейман и С. Улам. В основе метода лежит генерирование случайных чисел. Примерами генераторов случайных чисел могут служить игральные кости,   рулетка в казино и т.д.  В настоящее время известно множество алгоритмов, генерирующих случайные числа, с заданным законом распределения. Такие числа называют псевдослучайными. Познакомимся с одним из них. Для того чтобы получить последовательность случайных чисел с заданным законом распределения необходимо:

а) получить равномерно  распределенные случайные числа R в промежутке (0,1). В состав стандартных функций многих алгоритмических языков входят стандартные функции, генерирующие RÎ(0,1); 

б) подставив в соответствующую формулу преобразования полученные числа, смоделировать случайные числа с заданным законом распределения. V= f(R).

Для каждого закона распределения существует иногда несколько формул преобразования. Приведем некоторые формулы преобразования для наиболее употребляемых законов распределения:

а) для равномерного закона распределения

 

                                                V=a+(b-a)*R

 

где V – случайное число;

(а, в) - интервал, в котором моделируется случайное число;

RÎ(0,1); 

б) для показательного закона распределения

                                    ,

где l - плотность потока, RÎ(0,1); 

в) для нормального закона распределения

 

                                           ,

где М- математическое ожидание; 

s - среднеквадратическое отклонение;

n – любое целое положительное число, при этом n < 12.

 

Этапы моделирования систем.

Моделирование системы S состоит из трех основных этапов:

а) построение концептуальной модели системы и ее формализация;

          б) алгоритмизация модели системы и ее машинная реализация;

в) получение и интерпретация результатов моделирования системы.

          Каждый из перечисленных этапов состоит из нескольких частей. 

Рассмотрим подробней каждый из них.

1 Построение концептуальной модели системы и ее формализация.

1.1 Определение цели моделирования.

1.2 Постановка задачи.

1.3 Анализ задачи.

1.4 Определение требований к исходной информации и организация ее сбора.

1.5 Определение параметров и переменных.

1.6 Обоснование критериев оценки эффективности системы.

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

         

          2 Алгоритмизация модели системы и ее машинная реализация.

2.1 Построение логической схемы модели.

2.2 Получение математических соотношений в виде функций.

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

2.4 Разработка программы, реализующей алгоритм модели.

 

3 Получение и интерпретация результатов моделирования системы.

3.1 Планирование машинного эксперимента с моделью системы.

3.2 Определение требований к вычислительным средствам.

3.3 Проведение рабочих расчетов.

3.4 Анализ результатов моделирования системы.

3.5 Представление результатов моделирования (в виде графиков, диаграмм, таблиц и т. д.).

 

 

 

 

 

 

 

 

          Лекция 2.   Общие сведения о системах массового обслуживания (СМО)

          

          Цель лекции:  ознакомление с системами массового обслуживания, с основными элементами СМО, с задачами теории массового обслуживания и с символическими обозначениями СМО.

           Содержание:

           а) определение системы массового обслуживания:

б) основные элементы СМО;

в) задачи теории массового обслуживания;

  г) символическое обозначение моделей СМО;

  д) имитационное моделирование СМО. Система моделирования GPSS World.

Одним из важных разделов математического моделирования является теория систем массового обслуживания.

Основоположником теории является датский математик А. К. Эрланг.     Являясь сотрудником Копенгагенской телефонной компании, он опубликовал в 1909г работу «Теория вероятностей и телефонные переговоры», в которой впервые поставил и решил некоторые задачи теории систем массового обслуживания.

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

Системы массового обслуживания могут быть одноканальными или многоканальными.

Каждая СМО предназначена для обслуживания некоторого потока заявок, поступающих на вход системы в случайные моменты времени. Обслуживание заявок длится случайное время. После обслуживания заявки канал освобождается и готов к приему следующей заявки.

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

Таким образом, во всякой СМО можно выделить следующие основные элементы:

а) входящий поток заявок;

б) очередь;

в) каналы обслуживания;

г) выходящий поток обслуженных заявок;

д) поток необслуженных заявок.

Примерами СМО могут служить: телефонные станции, билетные кассы, магазины, парикмахерские и т. д.

   

 

 

 

 

 

 

 

                               

 

                                  Рисунок 2.1 – Схема СМО

 

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

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

Задачи теории массового обслуживания – нахождение вероятностей различных состояний СМО, а также установление зависимости между заданными параметрами (числом каналов n, интенсивностью потока заявок l, и т. д.) и характеристиками качества работы СМО. Характеристиками качества работы СМО могут быть:

- среднее число заявок, обслуживаемое в единицу времени, или пропускная способность СМО;

- вероятность обслуживания поступившей заявки;

- вероятность отказа в обслуживании;

- среднее число заявок в СМО;

- среднее число заявок в очереди;

- среднее время пребывания заявки в СМО;

- среднее время пребывания заявки в очереди;

- среднее число занятых каналов.

 Для удобства изложения начальных сведений об исследуемых моделях американским ученым Кендаллом были предложены символические обозначения СМО. Символика использует до шести разрядов. Первый разряд определяет поступающий поток вызовов, второй – закон распределения времени обслуживания, третий - структуру системы обслуживания, четвертый - дисциплину обслуживания, пятый - способ выбора из очереди, шестой – порядок занятия свободных приборов.

В первом разряде используются следующие символы:

M – экспоненциальное распределение промежутка между вызовами;

D – детерминированное распределение;

En  - эрланговское  n – го порядка;

HMn – гиперэранговское n – го порядка;

Gl – произвольное распределение;

Mi  - примитивный поток.

   Во втором разряде используются те же символы, но они уже обозначают распределение времени обслуживания. Только вместо Gl используется просто    G.

Стрелка над символом соответствует многомерному случаю. Например, Mn означает поступление  n   простейших потоков.

В третьем разряде используются следующие символы:

S – произвольная структура;

FM – полнодоступная система (Full Matrix), иногда используется v - число приборов;

G – неполнодоступная система  (Grading);

HG – равномерная неполнодоступная система;

PG – ступенчатая неполнодоступная система;

  Иногда для обозначения неполнодоступной системы используются D - доступность,  g – число нагрузочных групп. Многозвенные системы обозначаются символом LS (Link System).

В четвертом разряде используются следующие символы:

LL - дисциплина обслуживания без потерь (Lossles);

L – обслуживание с явными потерями (Loss);

W – обслуживание с ожиданием (Wait);

R – обслуживание с повторением (Reattemt).

В пятом разряде символики указывается способ выбора из очереди  в системе с ожиданием:

SP (Same Probability) - равновероятный, FF (First in Firstout) –упорядоченный (первый пришел – первый ушел), LF (LastinFirstout)  - стековый или магазинный (последний пришел – первый ушел),  PR (Priority) – приоритетный.

 Шестой разряд символики используется в тех моделях, где требуется указать порядок занятия свободных приборов или путей. При последовательном занятии применяется символ S,  при случайном – R.

 

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

 Мы с вами познакомимся с одной из специализированных систем моделирования, наиболее часто применяемых при моделировании систем телекоммуникаций, а именно: с  GPSS World.

           

  GPSS – General Purpose Simulation System, общецелевая система моделирования. Последняя версия GPSS World разработана компанией Minuteman (США), работает в операционной системе Windows.

 Учебную версию GPSS World можно бесплатно получить по адресу:

 www.minutemansoftware.com/download.

Необходимо отметить, что GPSS – это язык моделирования СМО.

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

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

Транзакты являются движущимися элементами GPSS-модели. Работа GPSS модели заключается в перемещении транзакта. В самом начале моделирования в модели нет ни одного транзакта. В процессе моделирования транзакты входят в модель в определенные моменты времени и в соответствии с теми логическими требованиями, которые возникают в модели. Подобным же образом транзакты покидают систему в определенные моменты времени. В общем случае в модели может существовать большое число транзактов, однако в один момент времени двигается только один транзакт.

 Следующими обязательными объектами  GPSS-модели являются блоки. Блоки представляют собой подпрограммы и содержат набор операндов для обращения к ним. В языке число таких блоков более 50.

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

Формат GPSS-блоков

  [<метка>] <Операция>  <Операнды> <;Комментарии>

 

 Метка (имя блока). Последовательность символов, начинающаяся с буквы. В некоторых блоках данное поле является обязательным.

Операция. Название операции совпадает с названием блока и является глаголом, указывающим,  какую функцию выполняет блок.

Операнды. Блоки могут иметь операнды. Операнды блоков задают информацию, необходимую для выполнения действия. В блоках не может быть использовано более 7 операндов. В общем случае операнды обозначаются символами А, В, С, D, E, F, G. Одни операнды являются обязательными, другие нет. Операнды отделяются друг от друга запятыми и одним пробелом. Если операнд опущен, то вместо него ставится запятая. 

 Комментарии. Необязательное поле. Комментарии отделяются от поля операндов символом «;».

 В GPSS World строка описания блока может содержать до 250 символов.

 

 

 

 

Лекция 3.  Моделирование одноканальных и многоканальных устройств на языке GPSS World

        

         Цель лекции: изучение блоков языка GPSS World, необходимых для моделирования одноканального устройства.

          Содержание:

а) блоки, составляющие модель одноканального обсуживающего устройства;

б) статистический отчет о процессах в системе;

          в) управление продолжительностью процесса моделирования;

          г) блоки и операторы, составляющие модель многоканального устройства.

Рассмотрим блоки, составляющие модель одноканального обслуживающего устройства.

Блок  GENERATE (генерировать)  – это блок, через который транзакты поступают в модель. В модели может быть несколько таких блоков.

  Формат записи:

 GENERATE     А, В,

здесь А – среднее время между последовательными приходами транзактов, В – половина поля допуска при равномерном распределении.

 

GENERATE     18,7

 

                                                         

 

              

Рисунок 3.1 – Поле допуска

 

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

Блок SEIZE (занять) – блок моделирует занятие прибора, переводит его в состояние «занято».

        Формат записи:

SEIZE    A,

здесь А – символическое или числовое имя прибора.

Например,

                     SEIZE 1

            или   SEIZE EQO.

Прибор из состояния «незанято» переходит в состояние «занято».

Свойства блока:

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

2. Если устройство свободно, то транзакт входит в блок.

 

Блок RELEASE (освободить) – освобождает обслуживающий прибор, переводит его в состояние «незанято».

       Формат записи:

RELEASE А,

здесь А – символическое или числовое имя прибора.

Таким образом, блоки SEIZE и RELEASE моделируют использование устройства, прибора, канала. Статистическая информация о работе устройства при моделировании собирается автоматически. В конце моделирования выдается стандартная статистика о работе использованного устройства.

 

 

FACILITY

Номер или

имя устрой-

ства

ENTRIES

Количество

входов

UTIL

Коэффициент

использования

AVE. TIME

Среднее время преб. в

 устройстве

AVAIL

Состояние

готовности

 

        1

     50

     0,07

     70,3

  

 

  OWNER

PEND

INTER

RETRY

DELAY

 

 

 

 

 

 

Блок ADVANCE (задержать) – моделирует задержку транзакта в течение некоторого модельного времени.

Формат записи:

 ADVANCE          А, [В] ,

 где А – задержка на время обслуживания, В – половина допуска равномерно распределенного интервала времени задержки.

 Транзакт всегда может войти в этот блок. Вычисляется время пребывания  в нем транзакта. В блоке может одновременно находиться несколько транзактов.

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

Блок QUEUЕ  (стать в очередь) - организует очереди и осуществляет сбор статистики.

Формат записи:

QUEUE    A, [B

где А – имя или номер очереди;

В – число единиц, на которое необходимо увеличить длину очереди.

Счетчик числа транзактов увеличивается на единицу, запоминается текущее модельное время.

Блок DEPART   (покинуть очередь) – моделирует выход транзакта из очереди.

Формат записи:

DEPART   A, [B]

        где А – имя или номер очереди;

        В – число единиц, на которое необходимо уменьшить длину очереди.

Счетчик длины очереди уменьшается на единицу, или на величину В.

В конце моделирования автоматически распечатывается статистика, содержащая информацию о значении счетчика входов, среднем значении длины очереди, максимальном времени пребывания в очереди и т.д.

Блок TERMINATE    (завершить) – моделирует выход транзакта из модели.

        Формат записи:

TERMINATE А

где А – величина, которая должна вычитаться из счетчика завершений.

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

Счетчик завершений задается с помощью оператора START.

Оператор START (начать)

START   A, [B]

где А – число завершений, или число транзактов, необходимых в модели;

В – операнд вывода статистики, по умолчанию выводится стандартная статистика.

Моделирование идет до тех пор, пока содержимое А не будет равно 0. Счетчик уменьшает блок TERMINATE.

        Управление продолжительностью процесса моделирования.

В языке GPSS продолжительностью процесса моделирования можно управлять двумя способами:

а) завершить моделирование после того, как модель покинет заданное число транзактов:

 

GENERATE   40,5

TERMINATE  1

START   100

 


б) завершить моделирование по истечению заданного интервала времени, например, 3 минут:

GENERATE 40,5

     . . .

     . . .

TERMINATE 0

GENERATE 180

TERMINATE 1

START 1

  Моделирование параллельно работающих каналов обслуживания в GPSS осуществляется с помощью следующих операторов и блоков.

     Оператор описания многоканального устройства имеет следующий формат:

 

          A_ STORAGE_ B,

 

где А – номер или имя многоканального устройства, а В – емкость устройства, положительное, целое.

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

 

STORAGE_ имя1, С1/имя2, С2…/имяn, Cn

 

где  имяi – число или символ;

Ci – емкость i-го устройства.

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

 

Блок ENTER (войти) – транзакт занимает многоканальное устройство

Формат записи:

ENTER A, [B]

где A – имя многоканального устройства;  

B – количество одновременно занимаемых устройств. По умолчанию В=1.

При моделировании МКУ события происходят в следующем порядке:

а) транзакт ожидает своей очереди, если это необходимо;

б) транзакт занимает устройство;

в) устройство осуществляет обслуживание на протяжении некоторого интервала времени;

г) транзакт освобождает устройство.

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

 

Блок LEAVE (выйти) – транзакт выходит из многоканального устройства.

Формат записи блока:

          LEAVE A, [B]

где А  - номер или имя многоканального устройства;

В - число освобожденных единиц многоканального устройства.

Текущее содержимое многоканального устройства уменьшается на В.

 

 

                                             

           Лекция 4. Объекты  GPSS World. Стандартные числовые атрибуты

 

Цель лекции: изучение основных объектов GPSS World, из которых строится модель. Формирование знаний об стандартных числовых атрибутах, которые содержат информацию, необходимую для каждого объекта в процессе моделирования.

Содержание

1. Перечень объектов и назначение каждого их них.

          2. Стандартные числовые атрибуты (СЧА).

          3. Переход транзакта в блок, отличный от последующего.

Модель в GPSS строится из отдельных элементов, называемых объектами.

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

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

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

1. Транзакты – это динамические объекты GPSS. Они создаются в определенных точках модели, затем уничтожаются.

2. Блоки – операционные объекты, в них выполняются операции  модели. В блоках могут происходить события четырех основных типов:

а) создание или уничтожение транзактов;

б) изменение числового атрибута объекта;

в) задержка транзакта на определенный период времени;

г) изменение маршрута движения транзакта в модели.

3. Одноканальные устройства  – оборудование, которое в каждый момент времени может быть использовано только одним транзактом. К ним относятся каналы, линии связи и д.р. Если другой транзакт попытается захватить устройство, то он задерживается до тех пор, пока устройство не освободится.  Автоматически подсчитывается общее время занятости устройства, общее число транзактов,  занимавших устройство.

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

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

5. Логические ключи. Для изменения движения транзактов введены логические ключи. Транзакт может устанавливать  ключ в положение «включено», «выключено» или инвертировать состояние ключа.

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

7. Булевы переменные   позволяют проверять в одном блоке одновременно несколько условий. Булева переменная принимает два значения: 0 и 1.

8. Функции. Используя функции, пользователь может производить вычисления непрерывных или дискретных функциональных зависимостей. Все функции GPSS задаются табличным способом с помощью специальных операторов описания функции.

9. Очереди. В любой системе движение транзакта может быть задержано из-за недоступности оборудования. Требуемые устройства могут быть уже заняты или многоканальные устройства уже переполнены. В этом случае транзакты становятся в очередь. Интерпретатор GPSS автоматически собирает статистику об очередях (длину очереди, среднее время пребывания в очереди и т.д.).

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

11. Ячейки сохраняемых величин и матрицы ячеек сохраняемых величин. Ячейки и матрицы в GPSS используются для сохранения некоторой числовой информации. Любой транзакт может произвести запись информации в эти ячейки и матрицы. Затем эту информацию может считывать любой транзакт. Значения ячеек будут распечатаны в конце прогона модели.

12. Модельное время. Для того чтобы обеспечить правильную временную последовательность событий в модели, организованы часы, которые хранят значения текущего момента в модели. Все отрезки времени измеряются целыми значениями, т.е. время дискретно, в отличие от реального времени. Физический смысл одной единицы модельного времени  (час, минута, секунда и т.д.) определяет пользователь. Следует помнить, что модельное время не есть время работы компьютера. Это время, продвигающееся вперед от одного момента смены состояния на другой.

 

           

 

          Стандартные числовые атрибуты СЧА

 

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

К большинству из этих атрибутов может обращаться только управляющая программа, однако к некоторым атрибутам может обращаться и пользователь. Такие атрибуты называются стандартными числовыми атрибутами (СЧА).

Каждый объект в GPSS имеет свой набор СЧА. Кроме СЧА - объектов, существуют еще системные числовые атрибуты, к которым пользователь может обращаться в модели, но  не может изменить их значения.

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

 Атрибуты транзакта:

Pj – значение параметра j текущего транзакта,  обрабатываемый в данный момент времени;

MPj – промежуточное время прохождения транзактом участка программы, записываемое в j-ом параметре;

PR – приоритет транзакта, обрабатываемого управляющей программой в данный момент времени;

M1 – время прохождения транзактом участка модели;

MBj – флаг синхронизации: 1, если транзакт в блоке j принадлежит тому же семейству, что и текущий транзакт; 0 – в противном случае.

Атрибуты блоков:

Nj - общее число транзактов, которое должно войти в j-й блок;

Wj - счетчик задержанных в j-ом блоке транзактов.

Атрибуты многоканальных устройств:

Sj – содержание  j - го многоканального устройства;

Rj- число свободных единиц j-го многоканального устройства.

Атрибуты одноканального устройства:

Fj – текущее состояние j-го устройства;

FRj – коэффициент использования j-го устройства одним транзактом;

FCj – общее число входов в устройство j;

FTj – среднее время использования устройства транзактами.

          Атрибуты очереди:

          Qj – текущая длина очереди;

          QAj – среднее значение длины очереди;

          QTj – среднее время пребывания в очереди.

Во всех случаях j – номер объекта, если   j – имя, то перед ним ставится знак $.

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

 Блок TRANSFER  (передать)  предназначен для передачи входящего в него транзакта в любой другой блок модели.

                                                                                                            

Блок имеет следующий формат:

                                                                                                            

           TRANSFER [A], [B], [C], [D],

                                                                                                      

здесь А – режим выбора блока,  которому должен быть передан транзакт.

Существуют следующие режимы работы блока:

- Безусловный (пробел);

- Статистический (.);

- Both;

- ALL и другие.

Безусловный режим выбора. Если операнд А опущен, то входящий в блок TRANSFER  транзакт переходит к блоку, указанному в поле B.

 

Например,   

TRANSFER  , B1

 

Режим BOTH. Транзакт пытается войти в блок, указанный в поле B. Если не может войти в этот блок, то пытается войти в блок, указанный в поле С. Если транзакт не может перейти и к этому блоку, то опять пытается войти в блок, указанный в В, и т.д., пока не сможет войти в один из блоков.

 

  TRANSFER BOTH TR1,TR2

  .

  .

  .

         TR1 SEIZE 1         

TR2 SEIZE 2

 

Статистический режим выбора. В этом режиме в поле А записывается точка (.), после неё следует трехзначное число. Это число показывает, какой процент, входящих в блок транзактов, следует  направить к блоку, указанному в поле С. Остальные транзакты направляются к блоку, указанному в поле В. Если операнд В опущен, то транзакт направляется к следующему блоку.

         Например,

         TRANSFER  .700, BLK1, BLK2

0.700 будут пытаться войти в BLK2, остальные 0.300 в BLK1.

0.700 – интерпретируется как вероятность.

 

 

 

 

Лекция 5. Объекты вычислительной категории.

Цель лекции: ознакомление с объектами вычислительной категории

Содержание

1)     Арифметические, условные и логические операторы.

2)     Арифметические переменные и арифметические выражения.

3)     Булевы переменные.

4)     Сохраняемые величины.

5)     Параметры транзакта. Изменение значений параметров транзакта.

6)     Проверка числовых выражений.

 

Арифметические, условные и логические операторы.

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

 

 Т а б л и ц а  5.1

Оператор

Операция

 

Аргумент, значение

         ^

Возведение  в  степень

А ^ В; А, возведенное в степень В

         #

Умножение

А # В; произведение А на В

         /

Деление

А / В; частное от деления А на В

         \

Целочисленное значение

А \ В; частное от целочисленного деления А на В

         @

Целый остаток

А @ В; целый остаток от деления А на В

          -

Вычитание

 

          +

Сложение

 

      >=`GE`

Больше или равно

1, если А>=В, иначе - 0

      <=`LE`

Меньше или равно

1, если А<=В, иначе - 0

       >`G`

Больше

1, если А>В, иначе - 0

       <`L`

Меньше

1, если А<В, иначе - 0

       =`E`

Равно

1, если А=В, иначе - 0

       =`NE`      

Не равно

1, если А!=В, иначе - 0

    &`AND`

Логическое  «И»

1, если А и В не 0, иначе - 0

      `OR`

Логическое  «ИЛИ»

1, если А или В или оба не 0, иначе - 0

 

 

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

Арифметические переменные и арифметические выражения

В языке GPSS имеются три типа переменных:

а) арифметические переменные с фиксированной точкой;

б) арифметические переменные с плавающей точкой;

в) булевы переменные.

         Переменная c фиксированной точкой задается оператором описания переменной   VARIABLE

Оператор имеет следующий формат:

а) поле метки, содержащее имя переменной;

б) поле операции, слово VARIABLE;

в) поле операндов, содержащее выражение для вычисления значения переменной.

Например,

 

VADD    VARIABLE  P10+25

 

Значение переменной VADD вычисляется как P10+25.

Или

COMP   VARIABLE X1*P4/10

 

Арифметические переменные  с фиксированной  точкой вычисляются следующим образом:

а) сначала берется целая, часть от входящих в выражение значений и производится вычисление;

б) затем выделяется целая часть результата.

Арифметические переменные  с плавающей  точкой отличаются лишь тем, что только окончательный результат преобразуется к целому числу. Для их описания служит оператор  FVARIABLE.

 

Булевы переменные

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

Логические операторы используются в блоке GATE:

SFj, SMFj, SNEj, LRj, LSj

SFj= 1, если МКУj заполнено, иначе 0;

SNFj=1, если МКУj не заполнено, иначе 0;

         Sej = 1, если МКУj пусто, иначе 0;

         SNEj = 1, если МКУj не пусто, иначе 0;

         LRj = 1, если логический ключ j выключен, иначе 0;

         LSj = 1, если логический ключ j включен, иначе 0.

Под j понимается номер или имя. Например,

          Port     BVARIABLE   LS3

Переменная   Port   равна 1, если логический ключ номер 3 включен

Операторы отношения производят алгебраическое сравнение операндов. Имеются следующие операторы отношений “G”- больше, “L” – меньше, “E” – равно, “NE” – не равно, “LE” – меньше или равно, “GE” – больше или равно

ATEST BVARIABLE X4 `G` P6

ATEST = 1, если значение ячейки 4 больше значения параметра 6 текущего транзакта.

 

Булевы операторы OR(ИЛИ)  и AND(И).

Оператор ИЛИ проверяет выполнение хотя бы одного из условий, а оператор И требует выполнения обоих условий.

BVAR1 BVARIABLE (X4 `G` P6) OR  (V3`L` 8)

BVAR1 равна 1, если если значение ячейки 4 больше значения параметра 6 текущего транзакта или значение переменной  3  меньше  8.

 

 Сохраняемые величины

 

В GPSS пользователь может задать перед моделированием начальные значения некоторых переменных, к которым затем можно обращаться из любого места модели. Эти величины называются сохраняемыми величинами (ячейками). Совокупность логически связанных между собой ячеек образует матрицу. Сохраняемые величины могут принимать положительные и отрицательные значения. Стандартный числовой атрибут Xj (X$/имя ячейки/) дает значение соответствующей сохраняемой величины. Например, X2 –значение ячейки 2, X$DAY – значение ячейки DAY.

 Блок SAVEVALUE (сохранить значение) – значение сохраняемой величины изменяется при входе транзакта в этот блок.

         Формат блока:

         SAVEVALUE A, B,                                                          

где A – номер ячейки, в которую должно быть записано значение В. Если в поле А стоит знак «+» или «-», то это означает, что к существующему значению прибавляется или вычитается значение операнда В.

Например,

         SAVEVALUE 3,1000

Записывает 1000 в ячейку 3

         SAVEVALUE 3+,1000

К содержимому ячейки 3 прибавляет 1000.

Оператор INITIAL (инициализировать) – инициализирует все начальные значения перед моделированием.

Имеет следующий формат:

         INITIAL A, [B],

где А – номер или имя ячейки, В – величина, которая присваивается А.

По умолчанию равна 1.

Например,

INITIAL Х3, 25

Ячейке с номером 3 присваивается начальное значение 25.

Оператор позволяет задавать  начальные значения ячеек (матриц и логических ключей)

 

  Параметры транзакта

 

Параметры транзакта – это свойства транзакта, определяемые пользователем. Множество параметров транзакта – набор стандартных числовых атрибутов, которые принадлежат транзакту. Параметры транзакта доступны только данному транзакту.  Параметры именуются буквой P и номером. Например, Р3, Р23. Параметры могут быть только целыми числами со знаком. Назначение и изменение параметра производится с помощью следующего блока.

Блок ASSIGN (назначить) - значения параметров могут задаваться или изменяться.                                              

Формат блока:

         ASSIGN A, B, [C],

где A – номер параметра, В – стандартный числовой атрибут (СЧА), значение которого присваивается параметру, С – номер функции.

         Блок ASSIGN является основным средством присваивания числовых значений параметрам транзактов. Из блока ASSIGN транзакт без задержки переходит в следующий блок.

         Непосредственно за аргументом поля А может стоять знак «+» или «-». Знак «+» означает, что значение аргумента поля В прибавляется к текущему значению параметра, знак «-» отнимается. Если знака нет, то значение В заменяет текущее значение параметра.

Например,

ASSIGN 5, X10

ASSIGN 2+, 1

Если используется поле С, то выполняется следующее:

а) вычисляется значение операнда в поле С;

б) значение операнда перемножается с содержимым поля В;

в) целую часть использует для замены значения параметра в поле А.

 

Проверка числовых выражений

Блок TESTосуществляется сравнение СЧА.

Формат блока

TEST X A, B, [C],

здесь X один из символов G, L, GE, LE, E, NE; A и B – стандартные числовые атрибуты, числа или имена; C – номер или имя блока, переход к которому осуществляется.

Блок TEST может работать в двух режимах:

     а) в режиме безусловного входа;

     б) в режиме условного входа.

В режиме безусловного входа, если в поле С задан номер следующего блока,  транзакты не задерживаются на входе блока.

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

 

Лекция 6. Таблицы и функции

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

Содержание

1) Определение и использование таблиц.

2) Организация таблицы.

3)     Определение функций в GPSS WORLD.

4)     Моделирование неравномерных случайных величин.

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

 Каждую таблицу нужно сначала определить и только потом использовать в модели.

Формат записи оператора TABLE

 

                           Name    TABLE  A,B,C,D

 

Name – имя таблицы;

A  - аргумент;

B  - верхний предел первого частотного интервала;

C – ширина частотного интервала;

D – число частотных интервалов.

      Блок TABULATE (табулировать) – заполняет таблицу, определенную оператором TABLE .

       Формат записи оператора:

 

                           TABULATE   А,

   

где  А – имя таблицы.  Одну таблицу можно использовать в нескольких блоках TABULATE.

     Оператор QTABLE используется для сбора статистики только о времени пребывания транзакта в очереди.

 

                           Name    QTABLE  A,B,C,D,

 

где А – имя очереди, остальные поля заполняются также, как в случае использования TABLE. Если таблица определена оператором QTABLE, то блок TABULATE не используется.

Если в модели используются операторы  TABLE  и QTABLE, то в файле стандартной статистики будет представлена следующая информация:

 

 

 

 

TABLE

Имя

табли

цы

MEAN

Средн

значен

ие

STD.DEV

Средн.

квадр.

отклон.

RANGE

Границы интер

валов

RETRY

Ждут

условий

FREQUENCY

Количество

попаданий

CUM,%

Накопленная частость

 

 

 

 

 

 

 

 

 

 Функции

В GPSS имеются два типа вычислительных объектов: арифметические переменные и функции.

     Функции используются для вычисления величин,  заданных табличными зависимостями. Каждая функция определяется перед началом моделирования с помощью оператора определения FUNCTION.

Существует пять типов функций:

а) непрерывная числовая – С;

б) дискретная числовая – D;

в) табличная числовая – L;

г) дискретная атрибутивная – Е;

д) табличная атрибутивная – M.

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

FUNCTION.

Формат оператора:

Name FUNCTION A,B

Поле А содержит аргумент. Аргументом может быть любой из стандартных числовых атрибутов. Если в качестве аргумента функции используется псевдослучайное число RNj , то оно может изменяться в пределах Ø<RNj<1. Во всех остальных случаях  Ø<RNj<999. Запись в поле B определяет тип и число точек функции, точнее число пар x[i] и y[i]. Примеры: С4, D5.

За каждым оператором FUNCTION  должны следовать операторы для задания координат (x[i] и y[i]) функции. Для задания координат можно использовать не целые числа:

RLGEX  FUNCTION RN1, C5

0,0/.33,.45/.40,1.60/.70,2.75/1.00,3.90

Значение координат разделяется запятой, пара координат разделяется чертой (/),  каждое последующее значение x[i] должно быть больше предыдущего. Каждая функция должна иметь, по крайней мере, две описанные точки.

Рассмотрим подробней каждый тип функции.

        1. Непрерывные числовые функции – С.

Когда значение аргумента непрерывной числовой функции попадает в интервал между двумя заданными значениями x[i] и x[i+1], программа производит линейную интерполяцию для определения значения функции.

 

 

           у

 

 

 


                                                     х

              x[i]              x[i+1]

               

 Рисунок 6.1 – График непрерывной числовой функции

 

2.     Дискретные числовые функции  - D.

Они задают одно и то же значение функции y[i] для всех х, которые

x[i-1]<x<=x [i]

 

        у

 

 

 

 

 


                                                       х

                       x[i-1]         x[i]

 

     Рисунок  6.2 – График дискретной числовой функции

 

3. Табличные числовые функции L

Значениями аргумента x[i] является последовательность целых чисел:

1, 2, 3,…, n.

Значение y[i] должны быть записаны в соответствующих полях операторов.

 

4. Дискретные и табличные атрибутивные функции.

В предыдущих трех случаях значениями функций были числа. Дискретные атрибутивные функции подобны функциям второго типа, но значениями могут быть СЧА. Табличные атрибутивные функции подобны третьему типу, но значениями могут быть СЧА.

 

 Моделирование неравномерных случайных величин.

 Использование функций в блоках GENERATE и ADVANCE.

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

Рассмотрим работу блоков:

 

GENERATE     A, B

ADVANCE      A, B

 

В данном случае время распределено по равномерному закону в промежутке (А±В).  Для моделирования  случайных величин,  подчиняющихся другим законам распределения, используются функции. От значения функции берется целая часть, за исключением тех случаев, когда это значение используется в качестве операнда В блоков GENERATE и ADVANCE Покажем в виде таблицы различные варианты значения полей А и В в блоках GENERATE, под результатом понимается значение интервала.

 

Т а б л и ц а 6.1

Операнд А

Операнд В

Результат

α (число или СЧА)

β (число или СЧА)

Генерируется случайное число, равномерно распределенное на интервале α ± β. Результат равен полученному числу.

FN$DIS

Отсутствует

Результат равен значению функции DIS

Отсутствует

FN

Данная комбинация недопустима

FN$DIS

β (число или СЧА)

Вначале вычисляется значение функции DIS. Берется целая часть этого значения (пусть α), генерируется случайное число, равномерно распределенное на интервале α ± β.  Результат равен полученному числу.

α (число или СЧА)

FN$DIS

Вначале вычисляется значение функции DIS (пусть это будет β), после чего находится произведение α х β. Результат равен целой части произведения.

FN$DIS1

FN$DIS2

Вычисляются значения функций DIS1 и DIS2 (пусть α и β), после чего находится произведение α х β. Результат равен целой части произведения.

  

Лекция 7.  Основы теории массового обслуживания. Модели потоков событий. Марковский случайный процесс. Одноканальная СМО с ожиданием

 

Цель лекции: освоение понятий: поток событий, простейший поток событий, Марковский случайный  процесс.

Содержание

1.Поток событий. Свойства потоков событий. Простейший поток событий. Формула Пуассона.

2. Процесс обслуживания как Марковский случайный процесс.

3. Одноканальная СМО с ожиданием.

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

Примерами могут быть:

- поток вызовов на телефонной станции;

 - поток сбоев компьютера;

- поток выстрелов, направляемых в цель и т.д. 

Регулярным потоком называется поток, в котором события следуют одно за другим через одинаковые промежутки времени (детерминированная последовательность событий).

 Такой поток событий редко встречается на практике. В телекоммуникационных системах чаще встречаются потоки, для которых и моменты наступления событий, и промежутки времени между ними являются случайными.

Рассмотрим такие свойства потоков событий, как стационарность, ординарность и отсутствие последействия.

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

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

В системах телекоммуникаций поток принято считать ординарным.

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

 

 

вероятность появления числа событий  на втором интервале не зависит от числа появления событий  на первом интервале.

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

 

,

 

где  — вероятность того, что на интервале появятся заявки.

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

Для стационарного потока его параметр не зависит от времени  .

    Для стационарного и ординарного потока λ= μ.

Простейшим или пуассоновским потоком называется стационарный, ординарный поток без последействия.  

Простейший поток  подчиняется пуассоновскому закону распределения

 

 

где    — интенсивность потока;

          — количество событий, появляющихся за время .

Простейший поток можно задать  функцией распределения промежутка между соседними вызовами

                                       F(t)=P(z<t)=1-P(z>t),

P(z>t) равносильна вероятности того, что в промежутке длиной t не поступит не одного вызова.

                                     F(t)=P(z>t)=1-(t)=1-

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

Свойства и характеристики простейшего потока:

а) для простейшего потока математическое ожидание и среднеквадратическое отклонение  величины промежутка z равны между собой MZ= σz=1/λ;

           б) математическое ожидание и дисперсия числа вызовов i за промежуток времени t равны между собой  Mi=Di= λt.

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

 

    Процесс обслуживания как марковский  случайный процесс

Пусть система может находиться в состояниях  где  —  в системе находится  заявок. Обозначим вероятность нахождения системы в конкретном состоянии  в момент времени  через  Очевидно, что для каждого

 

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

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

Очевидно, что для вероятности можно написать

 

                          (7.1)

 

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

Соотношение (7.1) может быть записано в векторной форме

 

                                                    (7.2)

 

где квадратная матрица  образована из элементов  удовлетворяющих условиям

 

,

.

 

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

 

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

 

,

в частности,

,

 

т.е.  марковская последовательность целиком определяется матрицей перехода  и начальными условиями

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

     

                                                                       

·

 

·

 

·

 

 

·

 

·

 

·

 

·

 

 

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

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


...

 
                       

    

Рисунок 7.1- Граф переходов для одноканальной СМО с ожиданием.

 

 

 

 

Лекция 8. Уравнения Колмогорова. Схема гибели и размножения

 

Цель лекции: изучить правило составления уравнений Колмогорова.

Освоить методы нахождения предельных вероятностей для установившихся режимов.

Содержание

1. Общее правило составления уравнений Колмогорова.

2. Схема гибели и размножения.

3. Формула Литтла.

4. Одноканальная СМО с отказами.

Познакомимся с общим правилом составления уравнений Колмогорова. Рассмотрим граф переходов из предыдущей лекции.

В левой части уравнения стоит производная вероятности -го состояния; в правой части — сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние, на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (-го) состояния.

Построим по этому правилу систему дифференциальных уравнений

                              ,

,

. . .

  

После преобразований получаем

,

,

. . .

.

Эти уравнения могут быть решены при начальных условиях

,

,

частотными методами с использованием преобразования Лапласа.

Чаще интересуются установившимся или стационарным режимом, для которого справедливо

.

 

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

,

,

. . .

,

 

отсюда , .

Учитывая, что  получаем

,

 

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

Установившийся режим не зависит от начальных условий. Получим некоторые числовые характеристики установившегося режима.

Среднее число заявок в системе

 

.

 

Среднее число занятых каналов

 

 

 

Среднее число заявок в очереди

,

проще:

.

 

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

                           Рисунок 8.1


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

       или   ,

   отсюда 

аналогично

  отсюда  .

Преобразуем

Учитывая, что   получаем

и

 

Полученные формулы мы будем в дальнейшем использовать для расчета вероятностей состояний различных СМО.

Формула Литтла.

Запомним еще одну важную формулу, связывающую (для стационарного режима) среднее число  заявок  в системе  и среднее время пребывания заявки  в системе.

 Для таких СМО справедлива формула Литтла

.

Для любой СМО среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок.

Аналогично выводится формула, связывающая среднее число заявок в очереди (v)  и среднее время пребывания заявки в очереди (w)  .

Рассмотрим одноканальную СМО с отказами.

Простейшая задача: СМО содержит один канал обслуживания; заявка, поступившая на вход системы и заставшая канал занятым, получает отказ. Граф переходов:

 

 

 


 Рисунок 8.2 – Граф переходов для одноканальной СМО с отказами.

                      

Тогда   ,     .

Исходя из условия  и начальных условий   получаем

Для стационарного режима   

Получим некоторые характеристики СМО.

Вероятность отказа  заявка получит отказ, если канал занят

Относительная пропускная способность () равна среднему числу обслуженных заявок к общему числу поступивших заявок (показывает долю обслуженных заявок):

Абсолютная пропускная способность () — число обслуженных заявок в единицу времени 

Среднее число занятых каналов () равно среднему числу заявок в системе  

Среднее время, проведенное заявкой в системе   

 

 

 Лекция  9. Расчет основных характеристик для различных типов СМО

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

Содержание:

1) Одноканальная СМО с ограниченной очередью.

2) Многоканальная СМО с ожиданием.

 3) Многоканальная СМО с отказами.

4) Замкнутые СМО.

Одноканальная СМО с ограниченной очередью

Пусть длина очереди в одноканальной СМО ограничена числом . Тогда граф переходов будет иметь следующий вид:

 

             

 

                                       

               Рисунок 9.1– Граф переходов

                            Используя формулы схемы гибели и размножения, получаем

 

.

Среднее число занятых каналов .

 

Среднее число заявок в очереди   .

 

Среднее число заявок в системе  .

Вероятность в отказе 

Относительная пропускная способность

.

 Многоканальная СМО с ожиданием

 

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

Построим граф переходов

 

 


         

 

 

 

 Рисунок 9.2 – Граф переходов

 

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

По графу строим уравнения вероятностей состояний

 

 

                                                    

                                         

Учитывая   получим 

 

Выведем основные характеристики системы

Абсолютная пропускная способность     

 

отсюда, среднее число занятых каналов       .

Среднее число заявок в очереди   ,

после преобразований  .

 

Общее число заявок в системе: 

Среднее время пребывания в системе    .

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

Многоканальная СМО с отказами  

Имеется  обслуживающих каналов, каждый из которых доступен, когда он свободен для каждой из поступающих в систему заявок. Если при поступлении очередной заявки все каналы заняты, то заявка получает отказ и теряется (). Граф переходов имеет вид

 

 


 

 

 

 

           Рисунок 9.3 – Граф переходов            

 

Уравнения вероятностей состояний здесь такие же, как и для любой многоканальной СМО, только для условия 

 

.

 

Заявка получает отказ в том случае, если все каналы заняты, тогда вероятность отказа

 

Относительная пропускная способность

 

.

 

Учитывая, что   среднее число занятых каналов равно

 

 

Среднее время, проводимое заявкой в системе

 

 

Если в системе очередь, ограниченная числом мест  (M/M/s/m), то заявка получит отказ только в том случае, когда в системе заняты все каналы обслуживания и все места в очереди (заявок). Тогда вероятность отказа

 

 где  .

 

 Замкнутые СМО

 

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

Если в некоторый момент времени ремонтируются или ожидают ремонта n единиц оборудования, а работают m-n, то вероятность отказа в течение  равна  — интенсивность прихода заявок в систему зависит от количества уже находящихся в системе заявок.

 

 

 

 

 

 


            Рисунок 9.4 – Граф переходов

 

Используя схему гибели и размножения, построим уравнения вероятностей состояний

,

или  ,

 

Абсолютная пропускная способность А для данной СМО — среднее количество неисправностей, устраняемых каналом обслуживания в единицу времени, и

,

 

где  — вероятность занятости канала, или 

 

Среднее число неисправных станков

 


Лекция 10. Сети  СМО

 

Цель лекции: изучить методы анализа сетей СМО.

Содержание

1) Определение сети СМО. Замкнутые и разомкнутые сети.

2) Граф и матрица передач.

3) Характеристики сети СМО.

4) Теорема Джексона.

В общем случае сеть СМО (Queuing Networks) можно представить в виде графа, вершинами которого являются одноканальные и многоканальные СМО (дуги определяют потоки передачи требований).

Простейшая разомкнутая или открытая сеть получается при по­следовательном соединении СМО (рис.7.1). Она еще называется многофазной СМО.

 

 

 

Рисунок 11.1

 

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

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

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

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

Сеть СМО удобно представлять в виде графа передач (рисунок 10.2), где вершины графа соответствуют СМО, дуги указывают возможности перехода заявки из одной СМО в другую, а  числа в дугах — вероятности перехода.

 

                                  

 

 

 

 

 

 

 

Рассмотрим сеть систем массового обслуживания, которая включает M СМО и один источник заявок. Заявки, выходящие из -ой системы  с постоянной вероятностью , поступают в систему  или покидают сеть. Из источника в -ю систему заявки поступают с вероятностью  Матрицу вероятностей поступления требований из одной системы в другую называют матрицей передач:

 

где   — циркулирование потока заявок в источнике,

 

 

Для графа передач, представленного на рис.10.2, матрица передач будет следующей

 

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

 

 

В матричной форме это выражение имеет вид:

 

.

 

Интенсивности потоков заявок в СМО зависят от   следовательно, можно определить:

,

где  — интенсивность источника заявок (интенсивность потока, поступающего на вход сети).

      Допустим, сеть замкнута, и в ней циркулирует конечное число заявок.

Тогда

 

 

Здесь интенсивности потоков определяются общим числом требований в сети. Выбрав некоторую СМО  за базовую, можно определить

 

.

 

Важной характеристикой сети СМО служит среднее время пребывания в ней заявки. Пусть сеть разомкнута. В установившемся режиме вероятность нахождения заявки в СМО определяется

 

 

Сравнивая с  , получаем:

 ,

где  — вероятность нахождения заявки в -й СМО.

Относительная частота прохождения требования через систему j за достаточно большой интервал времени t:

где   — число случаев, когда заявка оказалась в системе ;

— общее число заявок, прошедших через сеть.

Тогда

При достаточно большом интервале времени

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

Следовательно, 

 

где   — среднее время пребывания заявки в СМО с номером  .

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

Для показательных сетей существует установившийся режим, если для каждой -й СМО загрузка .   

Теорема Джексона

 

Рассмотрим сеть, содержащую N узлов, причем каждый i – ый узел состоит из mi  серверов с показательным распределением времени обслуживания с параметром  μi . В каждый узел поступает простейший поток заявок с интенсивностью   γi . Покидая i – ый узел, заявка с вероятностью  rij поступает в j – ый узел. Вероятность того, что заявка после обслуживания в i – ом узле вообще покинет сеть, будет равна 1 - ∑ rij .

Полная интенсивность потока λi , поступающего в i – ый узел, будет равна

                       

λi = γi + ∑ λj rij , где i = 1,2,3, … , N.

 

Состояние сети с N узлами описывается вектором, компонентами которого являются количества заявок в каждом из узлов сети (k1, k2, … , kN).

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

 

p(k1, k2, … , kN) =   p1(k1), p2(k2), … , pN(kN),

 

которые представляют собой стационарные вероятности для системы M/M/m. Этот результат носит название теорема Джексона.

Другими словами каждый узел в сети ведет себя так, как если он был независимой СМО типа M/M/m.

 

Лекция 11.    Планирование эксперимента и оценка точности результатов моделирования

 

Цель лекции: изучение основ теории планирования экспериментов.

Содержание

1. Цели планирования экспериментов с моделями систем.

2. Стратегическое планирование имитационного  эксперимента.

3. Тактическое планирование эксперимента.

 

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

Эксперимент на имитационной модели будем рассматривать состоящим из наблюдений, а каждое наблюдение — из прогонов модели.

Входные переменные х1, х2, ..., хт называются факторами. Выходная пере­менная у называется наблюдаемой переменной (реакцией, откликом).

Факторное пространство — это множество факторов, значения которых ис­следователь может контролировать в ходе подготовки и проведения модель­ного эксперимента.

 

 

Рисунок 11. 1 - Абстрактная схема системы

 

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

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

 

y = f(xl,x2, ..., хm,) + е(х1х2, ..., хт),

 

где f(xl,x2, ..., хт) - функция отклика (неслучайная функция факторов);

е(х1х2, ..., хт ) - ошибка эксперимента (случайная величина);

          х1х2, ..., хт - определенное сочетание уровней факторов из факторного пространства.

Очевидно, что у является случайной переменной, так как зависит от случай­ной величины е(х1х2, ..., хт). Дисперсия D [у], которая характеризует точность измерений, равна дисперсии ошибки опыта: D [у] = D [е].

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

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

 Эксперимент, в котором реализуются все возможные сочетания уровней фак­торов, называется полным факторным экспериментом (ПФЭ).

Общее число различных сочетаний уровней в ПФЭ для т факторов можно вычислить по формуле:

 

S k1 · k2 · k3 · ... ki · ... · km,

 

где  кi — число уровней i-го фактора.

Если число уровней для всех факторов одинаково, то S = km. Каждому соче­танию уровней факторов соответствует одно наблюдение.

Недостаток ПФЭ — большие затраты на подготовку и проведение, так как с увеличением числа факторов и их уровней число наблюдений в эксперименте растет. Например, если имеется шесть факторов с двумя уровнями каждый, то даже при одном прогоне модели в каждом наблюдении нужно S = 26 = 64 на­блюдения. Очевидно, что каждый прогон удваивает это число, следовательно, увеличивает затраты машинного времени.

 Такого рода задачи и явились одной из причин возникновения теории пла­нирования экспериментов.

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

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

Различают стратегическое планирование эксперимента и тактическое пла­нирование эксперимента.

Стратегическое планирование эксперимента

Целью стратегического планирования эксперимента является определение ко­личества наблюдений и сочетаний уровней факторов в них для получения на­иболее полной и достоверной информации о поведении системы.

При стратегическом планировании эксперимента должны быть решены две основные задачи.

1.       Идентификация факторов.

2.       Выбор уровней факторов.

Под идентификацией факторов понимается их ранжирование по степени вли­яния на значение наблюдаемой переменной.

По итогам идентификации целесообразно разделить все факторы на две груп­пы — первичные и вторичные.

Первичные — это факторы, исследование которых необходимо провести.

Вторичные — факторы, которые не являются предметом исследования, но влиянием которых нельзя пренебречь.

Выбор уровней факторов производится с учетом двух противоречивых требо­ваний:

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

- общее количество уровней по всем факторам не должно приводить к боль­шому количеству наблюдений.

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

Так как ПФЭ может потребовать много машинного времени, необходимо располагать методами отбора факторов, оказывающих существенное влияние на отклик. Если исследователя не интересуют взаимодейст­вия высокого порядка, можно получить большое количество информации с помощью исследования лишь некоторой части (1/2,1/4, 1/8 и т. д.) всех воз­можных сочетаний уровней факторов.

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

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

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

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

В качестве примера рассмотрим план дробного факторного эксперимента (ДФЭ) — одного из видов ЧФЭ, с полным числом возможных сочетаний 25. В ДФЭ каждый фактор имеет два уровня — нижний и верхний, поэтому общее число наблюдений S = 2т.  

Тактическое планирование эксперимента

Целью тактического планирования эксперимента является определение необ­ходимого количества прогонов модели в каждом наблюдении.

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

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

- вида распределения наблюдаемой переменной;

- коррелированности между собой элементов выборки.

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

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

 

                                     

 

где  ε — точность оценки;

          sα   — среднеквадратическое отклонение;

           tα аргумент функции Лапласа, при заданном уровне значимости α/2 на­ходится по таблице 1, в которой даны наиболее актуальные пары α и tα.

 

Т а б л и ц а 11.1

α

0,8

0,85

0,9

0,95

0,99

0,995

0,999

tα

1,28

1,44

1,65

1,96

2,58

2,81

3,30

  

Список литературы 

1.Советов Б.Я., Яковлев С.А. Моделирование систем. - М.: Высшая школа, 1998.

2. Шварц М. Сети связи: Протоколы, моделирование и анализ. - М.: Наука, 1992.

3. Боев В.Д. Моделирование систем. Инструментальные средства GPSS World: Учеб. пособие. – СПб.: БХВ-Петербург, 2004.

4. Кудрявцев Е.М. GPSS World. Основы имитационного моделирования различных систем. – М.: ДМК Пресс, 2004.

5. Томашевский В., Жданова Е. Имитационное моделирование  в среде  GPSS. - М.: Бестселлер, 2003.

6. Учебное пособие по GPSS World. /Перевод с английского /.- Казань: Изд-во «Мастер Лайн», 2002.

7. Туманбаева К.Х. Моделирование систем телекоммуникаций. Учебное пособие. –Алматы: АИЭС, 2006.

  

Содержание

Введение……………………………………………………………………… 3

 1.Лекция 1. Моделирование систем…………………………………………..  5

 2 Лекция 2.  Общие сведения о системах массового обслуживания …………  9

 3.Лекция 3.  Моделирование одноканальных и многоканальных

    устройств на языке GPSS World……………………………………………. 13

 4. Лекция 4. Объекты  GPSS World. Стандартные числовые атрибуты…..... 17

 5. Лекция 5. Объекты вычислительной категории…………………………... 21

 6. Лекция 6. Таблицы и функции………………………………………………25

 7. Лекция 7. Основы теории массового обслуживания. Модели потоков   событий. Марковский случайный процесс. Одноканальная СМО с  ожиданием……………………………………………………………………….29

 8. Лекция 8. Уравнения Колмогорова. Схема гибели и размножения………33

 9. Лекция  9. Расчет основных характеристик для различных типов СМО....37

10. Лекция 10. Сети  СМО………………………………………………………41

11. Лекция 11.    Планирование эксперимента и оценка точности результа-

тов моделирования………………………………………………………………45

12.Список литературы…………………………………………………………..49