Оценивание состояний и длительности мертвого времени в MAP-потоке событий Соловьев Александр Александрович

Содержание к диссертации

Введение

1 Оптимальная оценка состояний MAP-потока событий 22

1.1 Постановка задачи 22

1.2 Плотность вероятности длительности интервала между соседними событиями MAP-потока 25

1.3 Апостериорные вероятности состояний MAP-потока событий при отсутствии мертвого времени 35

1.3.1 Рекуррентные соотношения для апостериорных вероятностей 36

1.3.2 Явный вид апостериорных вероятностей состояний MAP потока 38

1.4 Важные случаи соотношения параметров, определяющие MAP-поток событий 49

1.5 Алгоритм оптимальной оценки состояний MAP-потока событий 54

1.6 Вероятность ошибки при оценивании состояний MAP-потока событий 55

1.6.1 Условная вероятность ошибочного решения о состоянии MAP потока событий в общем случае 58

1.6.2 Условная вероятность ошибки о состоянии MAP-потока для частных и особых случаев 62

1.6.3 Безусловная вероятность ошибки о состоянии MAP-потока для частных и особых случаев 66

1.7 Оптимальная оценка состояний MAP-потока в условиях мертвого времени 72

1.7.1 Апостериорные вероятности состояний MAP-потока в условиях мертвого времени 74

1.7.2 Алгоритм оптимального оценивания состояний MAP-потока в условиях мертвого времени 78

1.8 Результаты и выводы к первому разделу 79

2 Оценивание длительности мертвого времени в MAP-потоке событий 81

2.1 Постановка задачи 81

2.2 Вывод плотности вероятности длительности интервала между соседними событиями в потоке в условиях мертвого времени 83

2.3 Совместная плотность вероятности длительности смежных интервалов в потоке в условиях мертвого времени 92

2.3.1 Условия рекуррентности наблюдаемого потока 94

2.3.2 Частные случаи наблюдаемого потока событий 97

2.4 Оценка длительности мертвого времени методом максимального правдоподобия 99

2.4.1 Построение функции правдоподобия 100

2.4.2 Решение оптимизационной задачи

2.5 Оценка длительности мертвого времени модифицированным методом моментов 128

2.6 Результаты и выводы ко второму разделу 131

3 Результаты численных экспериментов на имитационной модели MAP-потока событий 132

3.1 Результаты численных расчетов апостериорных вероятностей состояний и оценок состояний в случае отсутствия мертвого времени 132

3.2 Результаты численных расчетов апостериорных вероятностей и оценок состояний в условиях мертвого времени 136

3.3 Результаты численных расчетов вероятности ошибки для общего случая и для случая рекуррентных потоков 140

3.4 Результаты численных расчетов оценки длительности мертвого времени 143

3.5 Результаты и выводы к третьему разделу 146

Заключение 148

Список используемых источников и литературы 151

• Важные случаи соотношения параметров, определяющие MAP-поток событий
• Совместная плотность вероятности длительности смежных интервалов в потоке в условиях мертвого времени
• Оценка длительности мертвого времени модифицированным методом моментов
• Результаты численных расчетов вероятности ошибки для общего случая и для случая рекуррентных потоков

Введение к работе

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

Дважды стохастические потоки характеризуются тем, что их интенсивность изменяется во времени по некоторому случайному закону, т.е. является случайным процессом. В зависимости от вида случайного процесса дважды стохастические потоки можно разделить на два класса: 1) интенсивностью потоков является непрерывный случайный процесс; 2) интенсивностью потоков является кусочно-постоянный случайный процесс с конечным или бесконечным числом состояний. Первый класс потоков был введен в статьях Д. Кокса и Дж. Кингмена. Потоки второго класса были введены в рассмотрение в 1979 г. в статьях Г. П. Башарина и В. А. Кокотушкина, В. А. Наумова и М. Ньютса. В настоящее время в литературе данные потоки обычно называют либо дважды стохастическими потоками, либо MC-потоками, либо MAP-потоками. В свою очередь, в зависимости от того, каким образом происходит переход из состояния в состояние, МС-потоки можно разделить на три типа: 1) синхронные потоки событий — потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени, являющиеся моментами наступления событий; 2) асинхронные потоки событий — потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени и не зависит от моментов наступления событий; 3) полусинхронные потоки событий — потоки, у которых для одного множества состояний справедливо определение первого типа, а для остальных состояний справедливо определение второго типа. Синхронные, асинхронные и полусинхронные потоки возможно представить в виде моделей MAP-потоков событий (Markovian Arrival Process) с определенными ограничениями на параметры последних. Одной из моделей дважды стохастических потоков событий является BMAP-поток (Batch Markovian Arrival Process). В BMAP-потоке в один и тот же момент времени может наступить несколько событий (одно, два, три и т.д.). Дважды стохастические потоки событий хорошо применимы для моделирования реального сетевого трафика (интенсивность сетевого трафика будет меняться в зависимости от объема передаваемой информации), реального транспортного трафика (в зависимости от времени суток интенсивность движения на дорогах будет разная), для моделирования атмосферных осадков и т. д.

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

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

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

Одним из искажающих факторов при оценке состояния и параметров потоков событий выступает мертвое время регистрирующих приборов. В большей части публикаций по теории массового обслуживания, в области исследования потоков событий, чаще всего рассматриваются математические модели потоков, функционирующие в условиях отсутствия мертвого времени. На практике же очень часто встречаются ситуации, когда наступившее событие потока порождает период мертвого времени (события потока не наблюдаются). Этот период продолжается некоторое время. Примером является протокол CSMA/CD – протокол случайного множественного доступа с обнаружением конфликта, широко используемого в компьютерных сетях. В момент регистрации (обнаружения) конфликта на входе сети по сети рассылается сигнал «заглушки»; в течение времени рассылки сигнала «заглушки» заявки, потупившие в данный узел сети, получают отказ в обслуживании и направляются в источник повторных вызовов. Здесь время, в течение которого узел сети закрыт для обслуживания заявок, поступающих в него после обнаружения конфликта, можно трактовать как мертвое время прибора, регистрирующего конфликт в узле сети.

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

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

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

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

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

5 ния дважды стохастических потоков событий внесли ученые России из Томского государственного университета А. Ф. Терпугов, А. М. Горцев, А. А. Назаров, К. И. Лившиц, С. П. Сущенко, С. П. Моисеева, Л. А. Нежельская, А. Н. Моисеев; из Российского государственного университета нефти и газа В. В. Рыков; из Российского университета Дружбы народов Г. П. Башарин, П. П. Бочаров, А. В. Печинкин, К. Е. Самуйлов, Ю. В. Гайдамака; из Института проблем управления РАН В. М. Вишневский, М. П. Фархадов; из Московского университета путей сообщения В. А. Ивницкий; из Института прикладной математики Дальневосточного отделения РАН Г. Ш. Цициашвили, Н. И. Головко; из Нижегородского государственного университета M. А. Федоткин, А. В. Зорин. Вклад в развитие теории массового обслуживания внесли ученые Белоруссии из Белорусского государственного университета Г. А. Медведев, А. Н. Дудин, В. И. Клименок, Г. В. Царенков; из Гомельского университета Ю. В. Малинковский; из Гродненского университета М. А. Маталыцкий.

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

Задачи исследования:

1. аналитическое исследование MAP-потока событий в условиях отсутствия мертвого времени и в условиях наличия мертвого времени; вывод аналитических формул для получения оптимальных оценок состояний MAP-потока и длительности мертвого времени;

2. разработка алгоритмов оценивания состояний и длительности мертвого времени;

3. реализация на ЭВМ программы имитационного моделирования MAP-потока событий, а также алгоритмов оценивания состояний MAP-потока и длительности мертвого времени;

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

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

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

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

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

Работа выполнена в рамках следующих научных проектов: – госзадание Минобрнауки России на проведение научных исследований в Национальном исследовательском Томском государственном университете на 2012–2013 гг.: «Разработка и исследование вероятностных, статистических и логических моделей компонентов интегрированных информационно-телекоммуникационных систем обработки, хранения, передачи и защиты информации» № 8.4055.2011, номер госрегистрации 01201261193;

– научно-исследовательская работа в рамках проектной части государственного задания в сфере научной деятельности на 2014–2015 гг.: «Исследование и разработка вероятностных, статистических и логических методов и средств оценки качества компонентов телекоммуникационных систем» № 2.739.2014/К, номер госрегистрации 114071440030;

– научно-исследовательская работа в рамках проектной части государственного задания в сфере научной деятельности Минобрнауки РФ № 1.511.2014/К «Исследование математических моделей информационных потоков, компьютерных сетей, алгоритмов обработки и передачи данных» (2016 г.).

Результаты работы используются в учебном процессе на факультете прикладной математики и кибернетики (ФПМК) Томского государственного университета при разработке курсов лекций образовательных дисциплин «Марковские системы массового обслуживания» и «Имитационное моделирование» для студентов бакалавриата 4-го курса ФПМК и дисциплины «Методы идентификации и оценки параметров телекоммуникационных потоков» для магистрантов 2-го курса ФПМК.

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

Положения, выносимые на защиту:

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

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

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

8. алгоритм оптимальной оценки состояний MAP-потока в условиях отсутствия мертвого времени;

9. алгоритм оптимальной оценки состояний MAP-потока в условиях наличия мертвого времени;

6) алгоритмы оценки длительности мертвого времени в MAP-потоке,
функционирующем в условиях мертвого времени;

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

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

Апробация результатов исследования. Основные результаты диссертации докладывались и обсуждались на следующих научных конференциях:

1. VIII международная конференция «Новые информационные технологии в исследовании сложных структур», Томск, 5–8 октября 2010 г.

2. IX международная конференция «Новые информационные технологии в исследовании сложных структур», Томск, 5–8 июня 2012 г.

3. V международная научно-практическая конференция «Актуальные
проблемы радиофизики» «АПР – 2013» с элементами научной школы для мо
лодежи, Томск, 1–6 октября 2013 г.

4. X Международная конференция «Новые информационные технологии в исследовании сложных структур», Томск, 9–11 июня 2014 г.

5. III Всероссийская молодежная научная конференция с международным участием «Математическое и программное обеспечение информационных, технических и экономических систем», Томск 22–23 мая 2015 г.

6. 2-я Международная летняя школа молодых ученых «Новые информационные технологии в исследовании сложных структур», Анапа, 8–12 июня 2015 г.

7. XV Международная конференция имени А. Ф. Терпугова «Информационные технологии и математическое моделирование», Алтайский край, пос. Катунь, 12–16 сентября 2016 г.

Публикации.

По материалам диссертации автором опубликовано 14 работ, из них 8 статей в журналах, включенных в Перечень рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук (из них 4 статьи в изданиях, индексируемых Web of Science и Scopus), 6 публикаций в сборниках материалов международных и всероссийских научных конференций.

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

Структура и объём диссертации. Диссертация состоит из введения, трех разделов, заключения, списка использованных источников и литературы, трех приложений. Общий объем диссертации составляет 185 страниц, включая приложения; иллюстративный материал представлен 16-ю рисунками (из них 4 в приложениях) и 18-ю таблицами; список использованных источников и литературы содержит 208 наименований.

Важные случаи соотношения параметров, определяющие MAP-поток событий

Рассмотрим ситуацию, когда длительность мертвого времени равна нулю (Т = 0), т.е. MAP-поток функционирует в условиях отсутствия мертвого времени. В дальнейшем изложении результаты данного подраздела потребуются при получении результатов для случая Т 0. Сформулируем лемму устанавливающую характер стационарного кусочно-постоянного случайного процесса (t). Лемма 1.2.1. Стационарный случайный кусочно-постоянный процесс (t) является марковским процессом.

Доказательство. Покажем, что поведение процесса (t) после некоторого момента времени t0 не зависит от поведения процесса до момента времени t0 , т.е. не зависит от предыстории. Пусть процесс (t) в момент времени t0 находится в i ом состоянии (/=1,2). В силу того, что длительность пребывания процесса (t) в каждом состоянии распределена по экспоненциальному закону (Fi(t) = 1-e , i = 1, 2), оставшееся время пребывания процесса в z-ом состоянии после момента времени t0 не зависит от того, как долго процесс (t) находился в /-ом состоянии до момента времени t0. Переход из /-го состояния в -ое, (iJ = 1, 2) процесса (t) полностью определен моментом окончания пребывания процесса (t) в /-ом состоянии. Исходя из этого, поведение процесса X(t) зависит только от того, в каком состоянии он находился в момент времени to, и не зависит от предыстории. Следовательно X(t) - марковский процесс. Лемма доказана.

Замечание. В силу того, что X(t) является принципиально ненаблюдаемым случайным процессом, то X(t) - скрытый марковский процесс. Лемма 1.2.2. Априорные стационарные вероятности состояний процесса X(t) есть Р? Зі щ = —, 712 = —, Bi + в2 Pi +3? (1.2.1) Pj = kl[\-Pl(kl I A,j)], P2 = X2\\-Pl(X2 2)].

Доказательство. В силу того, что процесс X(t) может пребывать либо в первом состоянии, либо во втором состоянии, условие нормировки для априорных стационарных вероятностей запишется в виде: 7 + ти2 = 1

Получим выражения для априорных вероятностей первого (второго) состояния процесса X(t). Обозначим nx(t \ t0)- вероятность того, что процесс X(t) в момент времени t находится в состоянии X(t) = Хг (в первом состоянии) при условии, что его функционирование началось в момент времени t = t0 (t to). Аналогично, тт:2(ґґ0). Воспользуемся At - методом. Определим вероятность Т1г + At\t0) того, что процесс X(t) находится в момент времени t + AtB первом состоянии, где At - здесь и далее достаточно малая положительная величина. Это может произойти в следующих ситуациях: 1) в момент времени t процесс X(t) находится в первом состоянии и за время Аґ(на полуинтервале [t,t + At)) первое состояние процесса X(t) не закончилось, т.е. процесс X(t) остался в первом состоянии в момент времени t + At; вероятность этой ситуации есть Tzx{t t0)e 1 l =(\-XlAt)iil(t\t0) + o(Aty, 2) в момент времени t процесс X(t) находится в первом состоянии и за время Аґ(на полуинтервале [t,t+At)) наступило событие потока и процесс X(t) перешел в первое состояние; вероятность этой ситуации есть 71J(t 1t0)(1 - е 1 t)Pl(Хх Хх) = XxAtPx(Хх \Xx)nx(t\t0) + o(At); 3) в момент времени t процесс X(t) находится во втором состоянии и за время At (на полуинтервале [t, t + At)) второе состояние закончилось и процесс X(t) перешел в первое состояние; вероятность этой ситуации есть n2(t\t0)(\-e 2 /) о(Л,11 Х2) = X2AtP0(Xx X2)n2(t I t0) + o(At); 4) в момент времени t процесс X(t) находится во втором состоянии и за время At (на полуинтервале [ t, t + At)) наступило событие потока и процесс X(t) перешел в первое состояние; вероятность этой ситуации есть n2(t\t0)(\-e 2 1)РХ(ХХ Х2) = X2AtPx(Xx X2)n2(t J t0) + o(At); Другие возможные ситуации имеют вероятность o(At). Собрав все возможные ситуации, получим равенство: 71J(t + At 1t0) = (1 - XxAt)izx(t\t0) + XxAtPx(Xx Xx)щ(t\t0) + X2At(P0(Xx \ X2) + + Px(Xx X2))7i2(t\t0) + o(At); Из равенства имеем izx(t + At\ t())-izx(t\ t()) Л „ _, , Л ч, , . Г1 „,. . , , , ч о(Аґ) " = _ iLI м( l I Хх)\Щ(t\ t0) + X2[l - /j(X2 A2)J7T:2U но)H j Аґ Аґ В последнем выражении, устремляя Аґ к нулю (At —» 0), получим TC l (У Uo) = _ l[1_ l( l I l)]71 I о) + 2[1 — 1 ( 2 І іУІ11! І о) (1.2.2)

Определим вероятностьn2(t + Ах 110) того, что процесс X(t) находится в момент времени t + At во втором состоянии. Это может произойти в следующих ситуациях: 1) в момент времени t процесс X(t) находится во втором состоянии и за время At (на полуинтервале [ t, t + At)) второе состояние процесса X(t) не закончилось, т.е. процесс X(t) остался во втором состоянии в момент времени t + At; вероятность этой ситуации есть n2(t J t0)e 2 = (1- k2At)7i2(t t0) + o(At); 2) в момент времени t процесс k(t) находится во втором состоянии и за время At (на полуинтервале [ t, t + At)) наступило событие потока и процесс k(t) перешел во второе состояние; вероятность этой ситуации есть n2(t t0)(\-e 2 t)Pl(k2 I А2) = k2AtPl(k2 I А2)7Г2(? t0) + o(At); 3) в момент времени t процесс k(t) находится в первом состоянии и за время At (на полуинтервале [ t, t + At)) первое состояние закончилось и процесс k(t) перешел во второе состояние; вероятность этой ситуации есть 71J (t 110 )(1 - е 1 t )Р0 (А2 кг) = AjAtP0 (А2 Aj )7tj (t І ґ0) + о(Аґ); 4) в момент времени t процесе k(t) находится в первом состоянии и за время At (на полуинтервале [ t, t + At)) наступило событие потока и процесс k(t) перешел во второе состояние; вероятность этой ситуации есть щ(t 110)(1 - е 1 t)Р[(А2 кг) = XxAtPx(А2 Aj)7tj(t\t0) + o(At); Другие возможные ситуации имеют вероятность o(At). Собрав все возможные ситуации, получим равенство: 7I2 (t + At 1t0) = kx At(P0 (к 2 kx) + Pi (к 2 I i ))7li (t\t0) + (l- k2At)iz2 (t\t0) + + k2AtPx (k2 I k2 )7i2 (/ Uo)+ (A0i Из равенства имеем: 7і,(ґ + Аґ 0-7Ь(7 ta) Л „ _, ,Л ,. ч, . , . Г1 „ /Л ,. ч, , , о(Аґ) — — = кх[І-Рх(Aj AJJTT: І Ґ0)-А2[l-.r Aj k1)\ii1{t\ t0)-\ . At At В последнем выражении, устремляя At к нулю (At —» 0), получим 7и 2 (ґ 110) = kl[l-Pl(kl A,1)]7i1(? t0)-k2[I-Pl(k21 А2)]тт:2(ґ ґ0); (1.2.3) Таким образом, получили систему дифференциальных уравнений (1.2.2), (1.2.3). Начальные условия для решения этой системы следующие: Tix{t = t0 110) = TZ Q 110) = щ Ti2{t = t0 110) = 7i2(tQ 110) = 1-71. Т.е. в момент времени t = t0 необходимо знать вероятность первого состояния процесса k(t) (начальную вероятность). Решая систему дифференциальных уравнений (1.2.2), (1.2.3), находим

Совместная плотность вероятности длительности смежных интервалов в потоке в условиях мертвого времени

Одним из искажающих факторов при оценке состояний и параметров потока событий выступает мертвое время регистрирующих приборов, которое порождается зарегистрированным событием. Другие же события, наступившие в течение периода мертвого времени, недоступны наблюдению (теряются). Можно считать, что этот период продолжается некоторое фиксированное время. В качестве примера приведем счетчик элементарных частиц (электронов, протонов и др.), когда зарегистрированная элементарная частица отключает счетчик от процесса регистрации на некоторый период (период мертвого времени). В качестве другого примера приведем протокол CSMA/CD - протокол случайного множественного доступа с обнаружением конфликта, широко используемого в компьютерных сетях. В момент регистрации (обнаружения) конфликта на входе некоторого узла сети по сети рассылается сигнал “заглушки” (“пробки”); в течение времени рассылки сигнала “заглушки” заявки, поступившие в данный узел сети, получают отказ в обслуживании и направляются в источник повторных вызовов. Здесь время, в течение которого узел сети закрыт для обслуживания заявок, поступающих в него после обнаружения конфликта, можно трактовать как мертвое время прибора, регистрирующего конфликт в узле сети.

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

Описание MAP-потока событий, функционирующего в условиях мертвого времени, дано в подразделе 1.1. Здесь напомним, что задача, как и в случае отсутствия мертвого времени (Т = 0), заключается в определении апостериорных вероятностей состояний w(\t), w(k2t) (w(k1 t) + w(k2t) = 1) в момент времени t вынесения решения о состоянии наблюдаемого потока. Решение о состоянии наблюдаемого потока (о состоянии процесса ()) выносятся путем сравнения вероятностей: если w(Xjt) w(Xit), /,7= 1,2; i j, то оценка состояния процесса есть L(t) = X 1.7.1 Апостериорные вероятности состояний МАР-потока в условиях мертвого времени

Момент принятия решения о состоянии MAP-потока событий t будет находиться между моментами наступления событий наблюдаемого потока tk и tk+1, к = 1, 2,… . Пусть t0 - момент времени начала наблюдения за MAP-потоком, а t1 момент времени наступления первого наблюдаемого события, тогда момент t будет принадлежать интервалу (t0 , t1). Рассмотрим интервал (tk , tk+1), значение длительности которого есть ik = tk+1 - tk , к = 1,2,… . Так как наблюдаемое в момент tk событие порождает период мертвого времени длительности Г, то к = Т + цк, где т]к - значение длительности интервала между моментом окончания периода мертвого времени tk + Ти моментом tk+1, т.е. интервал (tk , tk+1) разбивается на два смежных: первый - полуинтервал (tk , tk +Т], второй - интервал (tk +Т, tk+1). Отметим, что условия нахождения апостериорной вероятности w(1\t) на полуинтервале (tk, tk+T] и интервале (tk +Т, tk+1) принципиально разные. Кроме того, для нахождения вероятности w(1 \t) необходимо точно знать значение Т либо, по крайней мере, предварительно осуществить оценку Т. В противном случае отсутствие такой информации делает попытку строгого нахождения вероятности w(1 t) невозможной. Здесь предполагается, что значение Т известно точно. Рассмотрим полуинтервал (tk , tk + Т], к = 1, 2,… . На этом полуинтервале событие имеет место в граничной точке tk, на самом полуинтервале события отсутствуют.

Оценка длительности мертвого времени модифицированным методом моментов

Приведенные результаты делают возможным решение задачи оценки неизвестных параметров, задающих MAP-поток событий, функционирующий в условиях мертвого времени, по наблюдениям за моментами наступления событий. Рабочими методами оценки параметров при этом могут быть либо метод максимального правдоподобия, либо метод моментов [153, 154]. При оценке параметров потока событий обычно используется метод моментов, как более простой в аналитическом исполнении, реже используется метод максимального правдоподобия. Последнее связано с возникающими при использовании этого метода аналитическими трудностями. Полученные явные формулы для плотностей вероятностей рт(т) и рт(т1,т2) позволяют выписать в явном виде либо функцию правдоподобия, либо уравнения моментов, которые позволяют оценить значение длительности мертвого времени.

Обозначим Tk = tk+\ - tk (к = 1,2,...) значение длительности к-то интервала между соседними событиями наблюдаемого потока (ти 0). Так как рассматривается стационарный режим, то плотность вероятностей значений длительности к-то интервала рт (Tk) = Рт (т) (т - 0) Для любого к (индекс Т подчеркивает, что плотность вероятностей зависит от длительности мертвого времени). Здесь и далее ситуация, когда т = 0, означает доопределение изучаемых функций в граничной точке. В силу сказанного момент времени tk без потери общности можно положить равным нулю или, что то же самое, момент наступления события наблюдаемого потока есть т = 0. Тогда плотность вероятности (2.2.18) после преобразования примет вид

Пусть Т\ = t2 - t\,T2 = t3 - t2,...,Tk = tk+\ - tk последовательность измеренных (в результате наблюдения за потоком в течение интервала наблюдения (0,0) значений длительности интервалов между соседними событиями потока. Перед построением функции правдоподобия сделаем несколько замечаний. 1) Очевидно, что мертвое время Т ттіп (Xmin = min у, j = \,...,k), так как любой интервал времени между соседними событиями в наблюдаемом потоке (рисунок 2.1) содержит Т. 2) В общем случае наблюдаемый поток является коррелированным потоком событий. 3) Задача по нахождению в явном виде формулы для совместной плотности Рт(т\,...,%к) является практически невозможной. 4) Из-за эффекта мертвого времени корреляционные связи между величинами х\,...,%к, в наблюдаемом потоке, с увеличением длительности мертвого времени, ослабевают. Последнее вытекает из конструкции наблюдаемого потока, чем больше теряется событий МАР-потока, тем слабее становится связь между событиями наблюдаемого потока. 5) При выполнении любого из условий рекуррентности потока, рассмотренных в подразделе 2.3.1, длительности интервалов между соседними моментами наступления событий потока х\,...,хи являются последовательностью взаимно независимых случайных величин. Тогда очевидно, что при выполнении второго (Д Щ (Х1 2) + ї (Х11 Х1 )Р0 (к11 Х2)] - /32 [Рх (Х2 \Х1) + Р1 (к21 Х2 )Р0 (к21 Х1)] = = 0), либо третьего (A,j[1 -.Р0(А,21 А,х)] — Л-2[1 — (A,j 2)] = 0) условий рекуррентности оценка максимального правдоподобия значения длительности мертвого времени есть Т = ттіп . При выполнении первого (Р1( к11 kl)Pl(k21 2)_ i( i Х2)Р1(Х21 A-j) = 0) условия рекуррентности Т xmin.

В связи с этим, для оценки длительности мертвого времени в наблюдаемом потоке, при условии его коррелированности, будем использовать метод максимального правдоподобия в его обычно форме, представляя совместную плотность рт(т1,...,тк) в виде произведения одномерных плотностей рт(т{), і = \,2,...,к, что обусловливает погрешность при оценки длительности мертвого времени.

Упорядочим величины ті ... ik по возрастанию: xmin = г ; г ; ... т Тогда целевая функция (функция правдоподобия), с учетом (2.4.1) [154], запишется в виде L{Xi,Pl{Xi Xt),Px(Xt I Xj),PQ{Xi I k -),T I x(1),...,x(A:)) = 0,0 imin T; к L{Xi,Pl{Xi I Xt),Px(Xt I Xj),PQ{Xi І ку),Т x(1),...,x(A:)) = ГТ/ г 0 ),! !, т. 7=1 Поскольку поставленная задача заключается в построении оценки f значения длительности мертвого времени (в предположении, что остальные параметры потока Xt, Рі(Хі\кг), Рі(А,г-А,-), РоОЧАД ij=\,2, і-ф-j, известны), то согласно методу максимального правдоподобия, ее реализация есть решение оптимизационной задачи:

Результаты численных расчетов вероятности ошибки для общего случая и для случая рекуррентных потоков

В третьем разделе решается задача по построению имитационной модели MAP-потока событий на ЭВМ с получением численных результатов оценки состояний MAP-потока как в условиях отсутствия мертвого времени (Т = 0), так и при частичной наблюдаемости в условиях наличия мертвого времени (Т Ф 0), а также получения численных результатов оценки длительности мертвого времени с помощью алгоритмов приведенных в первом и втором разделе.

Для анализа качества оценивания состояний MAP-потока в случае отсутствия мертвого времени (Т = 0), и в случае наличия мертвого времени (Т Ф 0), а также для сравнения качества получаемых методом максимального правдоподобия и модифицированным методом моментов оценки длительности мертвого времени поставлен статистический эксперимент на имитационной модели MAP-потока событий. В ходе проведенного статистического эксперимента произведено численное сравнение качества полученных оценок длительности мертвого времени. Описание работы имитационной модели реализовано в виде блок-схемы и приведено в приложениях А, Б.

Результаты раздела 3 приведены в работах [52 - 54, 56].

Результаты численных расчетов апостериорных вероятностей состояний и оценок состояний в случае отсутствия мертвого времени Для получения численных результатов разработан алгоритм вычисления апостериорной вероятности w(1 t). Первый этап расчета предполагает имитационное моделирование MAP-потока. Описание алгоритма имитационного моделирования приводится в приложении А. Второй этап расчета -непосредственное вычисление по формулам (1.3.18) и (1.3.19) вероятностей w(kl \t), t0 t tx; w(k x\tk +0); w(Xx \t), tk t tk+\, к = 1, 2,..., и построение оценки X (t). Расчеты произведены для следующих значений параметров: Хх = 2, Х2 = 0,5, Р0(Х2\Х1) = 0,\, Р1(к2\ к1) = 0,1, Pl(Xl\Xl) = 0,S, P0(Xl\X2) = 0,4, (A-j I X2) = 0,2, Pl(k21X2) = 0,4, и времени моделирования Tm = 20 ед. времени. В качестве иллюстрации на рисунке 3.1 приведена траектория (верхняя часть рисунка 3.1) процесса X(t) (истинная траектория), полученная путем имитационного моделирования, где 1, 2 - состояния процесса X(t), и траектория (нижняя часть рисунка 3.1) оценки X(t), где 1, 2 - состояния оценки X(t).

Вынесение решения о том или ином состоянии процесса X(t) производилось с шагом At = 0,001. На рисунке 3.1 штриховкой на оси времени обозначены временные промежутки, на которых оценка состояния не совпадает с истинным значением процесса X(t) (область ошибочных решений). На рисунке 3.2 Рисунок 3.1 - Траектория процесса X(t) и оценки 1 (t) приведена траектория поведения вероятности w(Xx t), соответствующая полученной при имитационном моделировании последовательности наступления событий t\, t2,..., (алгоритм расчета приведен в приложении В).

Траектория апостериорной вероятности Для установления частоты ошибочных решений о состояниях процесса X(t) по наблюдениям за МАР-потоком, проведен статистический эксперимент, состоящий из следующих этапов: 1) для определенного набора параметров Xl,X2, P0(X2\Xl), Pl(X2\Xl), Pl(Xl\Xl), Р0(Х1\Х2), (А А,2), Р1(Х2\Х2), осуществляется имитационное моделирование МАР-потока событий на заданном отрезке времени [0,Тт] (отдельный 7-й эксперимент); 2) рассчитывается вероятность w(kl t) на отрезке [0,7 ]; 3) оценивается траектория процесса X(t) на отрезке [0,rw]; 4) осуществляется определение (для 7-го эксперимента) dj -суммарной протяженности интервалов, на которых значение процесса X(t) не совпадает с его оценкой X(t); 5) вычисляется доля ошибочных решений р = dj /Тт ; 6) производится повторение N раз (j = l,N) шагов 1 - 5 для расчета оценки безусловной (полной) вероятности ошибки принятия решения о состояниях процесса X(t) на отрезке [0, Тт].