ИМИТАЦИОННАЯ  МОДЕЛЬ  МОДУЛИРОВАННОГО  МАР-ПОТОКА  СОБЫТИЙ  В  УСЛОВИЯХ  НЕПРОДЛЕВАЮЩЕГОСЯ  ЭКСПОНЕНЦИАЛЬНОГО  МЕРТВОГО  ВРЕМЕНИ

Березин  Дмитрий  Владимирович

магистрант  2  курса,  кафедра  исследования  операций  НИТГУ, 
РФ,  г.  Томск

Е-mail:  berezin14@mail.ru

Нежельская  Людмила  Алексеевна

научный  руководитель,  канд.  техн.  наук,  доцент  НИТГУ, 
РФ,  г.  Томск

Е-mail:  ludne@mail.ru

1.  Введение

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

Основные  элементы  и  методы  исследования  теории  массового  обслуживания  можно  найти  в  книгах  Б.В.  Гнеденко,  И.Н.  Коваленко  [1].

В  реальных  ситуациях  часто  приходится  сталкиваться  с  тем,  что  параметры  входящих  потоков  и  обслуживающих  приборов  неизвестны  или  частично  известны,  кроме  того,  могут  изменяться  со  временем.  При  этом  изменения  обычно  носят  случайный  характер,  что  приводит  к  рассмотрению  дважды  стохастических  потоков  событий.  Двойная  случайность  заключается  в  следующем:  во-первых,  моменты  наступления  событий  случайны,  во-вторых,  интенсивность  потока  есть  случайный  процесс.  Более  того,  встречаются  ситуации,  когда  не  все  моменты  наступления  событий  наблюдаемы.  Это  может  происходить  по  многим  причинам.  Одной  из  таких  причин  является  период  ненаблюдаемости,  порождаемый  зарегистрированным  событием,  получивший  название  «мертвое  время». 

Потоки  событий  с  интенсивностью,  зависящей  от  времени  можно  разделить  на  два  класса.  К  первому  классу  относятся  потоки  с  интенсивностью,  которая  является  непрерывным  случайным  процессом.  Ко  второму  классу  относятся  потоки,  у  которых  интенсивность  есть  кусочно-постоянный  случайный  процесс  с  конечным  числом  состояний.  Такие  потоки  получили  название  MC-потоки  (Markov  chain).  MC-потоки  являются  хорошей  математической  моделью  телекоммуникационных  сетей.  Зачастую  реальные  информационные  потоки  аппроксимируются  MC-потоками  с  числом  состояний  большим  двух  [2],  но  исследование  дважды  стохастических  потоков  с  двумя  состояниями  также  имеет  большое  значение.  MC-потоки  возможно  представить  в  виде  моделей  MAP-потоков  событий  (Markovian  Arrival  Process)  [3].

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

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

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

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

второй  случайный  фактор  –  случайная  величина,  также  распределенная  по  экспоненциальному  закону  ,  .  В  момент  окончания  состояния    возможны  3  ситуации:

Процесс  остается  в  состоянии    и  наступает  событие  потока.  Вероятность  этой  ситуации  .

Процесс  переходит  из  состояния    в  состояние    и  наступает  событие  потока.  Вероятность  этой  ситуации  ,  .

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

При  этом  .

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

Матрица  инфинитезимальных  характеристик  запишется  в  виде

.

Элементами  матрицы    являются  интенсивности  переходов  процесса    из  состояния  в  состояние  с  наступлением  события.  Недиагональным  элементам  матрицы    соответствуют  интенсивности  переходов  из  состояния  в  состояние  без  наступления  события.  Описанный  выше  поток  носит  название  модулированного  MAP-потока  событий  [3].

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

На  рисунке  1  приведен  пример  возникающей  ситуации.  Здесь    и    –  значения  состояний  ненаблюдаемого  процесса  ,    –  моменты  наступления  событий  в  наблюдаемом  потоке,    –  длительность  мертвого  времени  после  -го  зарегистрированного  события. 

Задача  заключается  в  построении  имитационной  модели  модулированного  MAP-потока  событий  в  условиях  непродлевающегося  мертвого  времени.

Рисунок  1.  Формирование  наблюдаемого  потока  событий

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

Задача  построения  имитационной  модели  сводится  к  задаче  генерации  значений    случайной  величины  –  времени  пребывания  процесса    в  -м  состоянии,  .  Длительность  пребывания  процесса    в  -м  состоянии  имеет  плотность  распределения  вероятностей    и  функцию  распределения  ,  .  В  соответствии  с  методом  обратных  функций  [4]  обозначим  .  Тогда  имеем  ,  откуда  находим  –  значение  экспоненциально  распределенной  случайной  величины  –  времени  пребывания  процесса    в  -м  состоянии,  ,  а    есть  значение  случайной  величины  ,  равномерно  распределенной  на  отрезке    [4].  Так  как  длительность  мертвого  времени  также  экспоненциально  распределенная  случайная  величина,  то  для  генерации  ее  значений,  согласно  методу  обратных  функций,  будем  иметь  формулу  .

Построение  реализации  потока  происходит  следующим  образом:

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

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

3.  По  формуле    генерируется  время  пребывания  процесса    в  состоянии  ,  по  истечении  которого  наступает  событие  потока  либо  происходит  переход  в  состояние  ,  ,  учитывая  вероятности  ,  ,  . 

4.  Если    и  переход  не  произошел,  шаг  3  повторяется.  Если  переход  произошел,  либо  ,  возвращаемся  к  шагу  2.  При  этом  текущее  время  увеличивается  на  величину  .

5.  Шаги  2–4  повторяются  пока  текущее  время  ,  где    –  время  моделирования. 

6.  Вывод  результатов  на  экран.

4.  Результаты

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

Таблица  1.

Исходные  данные  для  первого  эксперимента

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

Таблица  2.

Результаты  первого  эксперимента

Здесь    –  моменты  наступления  событий  модулированного  MAP-потока,    –  состояние  процесса  ,  в  котором  наступило  событие  потока  (условимся,  что  сначала  наступает  событие,  затем  процесс    переходит  из  состояния  в  состояние),    –  моменты  наступления  событий  в  наблюдаемом  потоке,    –  длительность  мертвого  времени  после  зарегистрированного  события

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

Таблица  3.

Исходные  данные  для  второго  эксперимента

Результаты  второго  эксперимента  продемонстрированы  в  таблице  4.

Таблица  4.

Результаты  второго  эксперимента

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

5.  Заключение

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

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

1. Гнеденко  Б.В.  Введение  в  теорию  массового  обслуживания  /  Б.В.  Гнеденко,  И.Н.  Коваленко.  –  М.:  Наука,  1966.  –  Гл.  1:  Задачи  теории  массового  обслуживания  в  простейших  предпосылках.  –  С.  12–91. 
2. Горцев  А.М.  Оптимальная  оценка  состояний  асинхронного  дважды  стохастического  потока  событий  с  произвольным  числом  состояний  /  А.М.  Горцев,  В.Л.  Зуевич  –  Вестн.  Томского  гос.  ун-та.  Сер.  Управление,  выч.  техника  и  информатика.  –  2010.  –  №  2  (11).  –  С.  44–65.
3. Горцев  А.М.  Математическое  моделирование:  о  связи  MC-потоков  и  MAP-потоков  событий  /  А.М.  Горцев,  Л.А.  Нежельская.  –  Вестн.  Томского  гос.  ун-та.  Сер.  Управление,  выч.  техника  и  информатика.  –  2011.  –  №  1.  –  С.  13–21.
4. Соболь  И.М.  Численные  методы  Монте-Карло  /  И.М.  Соболь.  –  М.:  Наука,  1973.  –  311  с.