Содержание к диссертации
Введение
1 Оптимальная оценка состояний модулированного обобщенного полусинхронного потока событий при его полной и неполной наблюдаемости .
1.1 Постановка задачи
1.2 Апостериорные вероятности состояний модулированного обобщенного полусинхронного потока событий
1.2.1 Рекуррентное соотношение для апостериорных вероятностей состояний потока
1.2.2 Явный вид апостериорных вероятностей состояний .
1.3 Алгоритм оптимального оценивания состояний потока при его полной наблюдаемости
1.4 Плотность вероятности значений длительности интервала между соседними событиями потока
1.5 Совместная плотность вероятности значений длительности смежных интервалов между событиями в потоке
1.5.1 Выражение для совместной плотности вероятности значений длительности смежных интервалов между событиями в потоке
1.5.2 Условия рекуррентности потока событий
1.6 Вероятность ошибки при оценивании состояний модулированного обобщенного полусинхронного потока событий
1.6.1 Условная вероятность ошибки при оценивании состояний потока в общем случае
1.6.2 Условная и безусловная вероятность ошибки при оценивании состояний потока для частных и особых случаев .
1.7 Оптимальная оценка состояний модулированного обобщенного полусинхронного потока событий при его неполной наблюдаемости 75
1.7.1 Апостериорные вероятности состояний потока при его неполной наблюдаемости 77
1.7.2 Алгоритм оптимального оценивания состояний потока при
его неполной наблюдаемости 80
1.8 Результаты и выводы к первому разделу 81
2 Оценивание длительности мертвого времени в модулированном обобщенном полусинхронном потоке событий 84
2.1 Постановка задачи 84
2.2 Плотность вероятности значений длительности интервала между соседними событиями потока при наличии мертвого времени 86
2.3 Совместная плотность вероятности значений длительности смежных интервалов между событиями в потоке при наличии мертвого времени 90
2.3.1 Выражение для совместной плотности вероятности зна
чений длительности смежных интервалов между событиями в наблюдаемом потоке 91
2.3.2 Условия рекуррентности наблюдаемого потока событий 93
2.4 Оценка длительности мертвого времени методом максимального правдоподобия 96
2.4.1 Построение функции правдоподобия 97
2.4.2 Решение оптимизационной задачи 100
2.5 Оценка длительности мертвого времени модифицированным методом моментов 122
2.6 Результаты и выводы ко второму разделу 126
3 Результаты численных экспериментов по оценке состояний и длительности мертвого времени в модулированном обобщенном полусинхронном потоке событий 127
3.1 Результаты численных экспериментов по оценке состояний в модулированном обобщенном полусинхронном потоке событий 128
3.2 Результаты численных расчетов вероятности ошибки при оценивании состояний потока 140
3.3 Результаты численных расчетов по оценке длительности мертвого времени 144
3.4 Результаты и выводы к третьему разделу 152
Заключение 154
Список использованных источников и литературы 157
- Алгоритм оптимального оценивания состояний потока при его полной наблюдаемости
- Вероятность ошибки при оценивании состояний модулированного обобщенного полусинхронного потока событий
- Оценка длительности мертвого времени методом максимального правдоподобия
- Результаты численных расчетов вероятности ошибки при оценивании состояний потока
Введение к работе
Актуальность темы исследования. Ввиду относительной простоты систем связи и изолированности различных видов связи друг от друга до середины 80-х гг. XX столетия в теории массового обслуживания для входящих потоков заявок использовались относительно простые модели - простейший поток. реже регулярный и эрлапговский потоки. Усложнение структуры информационных систем, интеграция различных систем связи, разнообразие программного и аппаратного обеспечения, протоколов передачи информации в конце XX и начале XXI веков приводят к тому, что существующие модели во многом становятся непригодными для анализа случайных процессов, функционирующих в современных сетях связи. В рассмотрение вводятся математические модели потоков с переменной интенсивностью или дважды стохастических потоков событий (англ. «doubly stochastic Poisson process»), которые можно охарактеризовать двумя случайностями: числом событий па любом рассматриваемом интервале функционирования потока и случайным процессом A(t), называемым интенсивностью потока.
В зависимости от характера случайного процесса X(t) дважды стохастические потоки событий можно разделить па два класса: потоки, интенсивность которых есть непрерывный случайный процесс, и потоки, интенсивность которых представляет собой кусочпо-постояппый случайный процесс. Потоки второго класса наиболее характерны для реальных телекоммуникационных и информационно-вычислительных сетей связи. Впервые и независимо они были введены в рассмотрение в работах Г. П. Башарипа, В. А. Кокотушкипа, В. А. Наумова и М. Ныотса. В свою очередь, в зависимости от того, каким образом происходит переход интенсивности из состояния в состояние, данные потоки событий можно разделить па три типа: 1) синхронные потоки - потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени, являющиеся моментами наступления событий; 2) асинхронные потоки - потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени и не зависит от моментов наступления событий: 3) полусипхроппые потоки - потоки, у которых для одного множества состояний справедливо определение первого типа, а для остальных состояний справедливо определение второго типа. Синхронные, асинхронные и полусипхроппые потоки возможно представить в виде моделей МАР-потоков (Markovian Arrival Process) событий с определенными ограничениями па параметры последних. В качестве еще одного примера потоков с кусочпо-постояп-пой интенсивностью можно привести ВМАР-поток (Batch МАР), для которого характерно то, что события в каждый момент времени появляются «пачками» по одному, два, три и т.д.
Основная литература по исследованию систем массового обслуживания
посвящена нахождению различных стационарных характеристик системы в условиях известных параметров входящих потоков и обслуживающих приборов. В реальных ситуациях параметры, задающие входящий поток событий, известны либо частично, либо вообще неизвестны, поэтому при реализации адаптивного управления системой массового обслуживания возникают, в частности. следующие задачи: 1) задача оценивания состояний потока по наблюдениям за моментами наступления событий; 2) задача оценивания параметров потока по наблюдениям за моментами наступления событий.
Отметим, что одним из искажающих факторов при исследовании дважды стохастических потоков является мертвое время регистрирующих приборов. Большинство авторов рассматривают системы массового обслуживания в условиях полной наблюдаемости событий функционирующих в системе потоков. Необходимость рассмотрения случая мертвого времени вызвана тем, что па практике любое регистрирующее устройство затрачивает на измерение и регистрацию события некоторое конечное время, в течение которого оно не способно правильно обработать следующее событие. Все устройства регистрации с достаточной степенью приближения можно разделить па две группы: первую группу составляют устройства с пепродлевающимся мертвым временем, которое не зависит от поступления других событий в пределах его действия; ко второй группе относятся устройства с продлевающимся мертвым временем, в этом случае мертвое время возникает после любого события, поступившего па вход системы, вне зависимости от факта его регистрации.
Проведенные статистические эксперименты показывают возможность достаточно точной аппроксимации реальных телекоммуникационных потоков событий дважды стохастическими потоками. Кроме того, теория дважды стохастических потоков находит широкое применение в различных отраслях пауки и техники таких как теория сетей, статистическое моделирование, финансовая математика и др. Большое количество исследований дважды стохастических потоков событий и систем массового обслуживания с входящими дважды стохастическими потоками было проведено такими учеными как А. Ф. Терпугов,
A. М. Горцев, А. А. Назаров, К. И. Лившиц, С. П. Сущепко. С. П. Моисеева.
Л. А. Нежельская, А. Н. Моисеев - в Томском государственном университе
те: Г. А. Медведев. А. Н. Дудип. В. И. Климепок, Г. В. Царепков - в Бело
русском государственном университете; К). В. Малипковский - в Гомельском
университете: М. А. Маталыцкий - в Гродненском университете: В. В. Гыков
в Российском государственном университете нефти и газа; Г. П. Башарип. П. П. Бочаров. А. В. Печипкип, К. Е. Самуилов. К). В. Гайдамака - в Российском университете дружбы пародов; В. М. Вишневский, М. П. Фархадов
в Институте проблем управления РАН; Г. Ш. Цициашвили. Н. И. Головко,
B. В. Катрахов - в Институте прикладной математики Дальневосточного отде
ления РАН; М. А. Федоткип, А. В. Зорин - в Нижегородском государственном
университете: Д. Ефросиний - в университете Johannes Kepler University Linz (Austria); M. Пагапо - в Пизапском университете (Pisa, Italy); M. F. Neuts. D. M. Lucantoni - в США и другими учеными.
В настоящей диссертационной работе впервые исследуется модулированный обобщенный полусипхропный поток событий (далее - поток или поток событий), относящийся к классу дважды стохастических потоков событий, при этом решаются актуальные задачи оптимального оценивания состояний потока событий в условиях полной наблюдаемости и оценивания состояний и длительности мертвого времени в потоке, функционирующем в условиях пепродлева-ющегося мертвого времени.
Цели и задачи исследования. Целью работы является аналитическое и численное исследование модулированного обобщенного полусипхрошюго потока событий, в рамках которого были поставлены и решены следующие задачи: 1) аналитическое исследование потока событий в условиях полной наблюдаемости и при наличии пепродлевающегося мертвого времени, построение соответствующих математических моделей с целью оценивания состояний и длительности мертвого времени; 2) построение оценок состояний и длительности мертвого времени в потоке событий: 3) разработка алгоритмов оценивания состояний и длительности мертвого времени в потоке событий, их программная реализация; 4) проведение статистических экспериментов па имитационной модели потока событий с целью установления качества получаемых оценок состояний и длительности мертвого времени.
Научная новизна исследования состоит в решении задачи оптимального оценивания состояний модулированного обобщенного полусипхрошюго потока событий, функционирующего в условиях полной наблюдаемости, а также задач оптимального оценивания состояний и длительности мертвого времени потока событий, функционирующего при наличии мертвого времени, по наблюдениям за моментами наступления событий в потоке.
Теоретическая и практическая значимость диссертации. Теоретическая ценность работы заключается в аналитическом решении задачи оптимального оценивания состояний модулированного обобщенного полусипхроп-пого потока событий по наблюдениям за моментами наступления событий в потоке в условиях полной наблюдаемости, а также в аналитическом решении задачи оптимального оценивания состояний и задачи оценивания длительности мертвого времени в потоке событий в условиях его частичной наблюдаемости.
Практическая ценность работы состоит в возможности использования разработанных алгоритмов оценивания состояний и длительности мертвого времени модулированного обобщенного полусипхрошюго потока событий в задачах анализа и проектирования систем и сетей массового обслуживания, в частности, автоматизированных систем управления, информационно-вычислительных систем, телекоммуникационных и компьютерных сетей и др., дисциплины
обслуживания которых зависят от параметров и текущих состояний входящих потоков событий, а также для обработки результатов физических экспериментов, осложненных наличием мертвого времени регистрирующих приборов.
Работа выполнена в рамках следующих научных проектов: 1) госзадапие Мипобрпауки России па проведение научных исследований в Национальном исследовательском Томском государственном университете па 2012-2013 гг.: «Разработка и исследование вероятностных, статистических и логических моделей компонентов интегрированных информационно-телекоммуникационных систем обработки, храпения, передачи и защиты информации» № 8.4055.2011, помер госрегистрации 01201261193; 2) научно-исследовательская работа в рамках проектной части государственного задания в сфере научной деятельности па 2014-2015 гг.: «Исследование и разработка вероятностных, статистических и логических методов и средств оценки качества компонентов телекоммуникационных систем» № 2.739.2014/К, помер госрегистрации 114071440030; 3) научно-исследовательская работа в рамках проектной части государственного задания в сфере научной деятельности Мипобрпауки РФ № 1.511.2014 К «Исследование математических моделей информационных потоков, компьютерных сетей. алгоритмов обработки и передачи данных» (2016 г.).
Результаты работы используются в учебном процессе па факультете прикладной математики и кибернетики НИ ТГУ при разработке курсов лекций образовательных дисциплин «Марковские системы массового обслуживания». «Имитационное моделирование» и «Методы идентификации и оценки параметров телекоммуникационных потоков».
Методология и методы исследования. Для реализации поставленных в работе задач применен аппарат теории вероятностей, теории марковских случайных процессов, теории массового обслуживания, математической статистики, теории дифференциальных уравнений, математического анализа, линейной алгебры и имитационного моделирования. Проведение статистических экспериментов выполнено па имитационной модели модулированного обобщенного полусипхрошюго потока событий. Программа расчета реализована па языке программирования С// в интегрированной среде разработки Microsoft Visual Studio 2015 в виде пользовательского приложения и интерфейса командной строки. Дополнительно для проведения численных расчетов и анализа полученных результатов созданы скрипты па языке программирования Python.
Положения, выносимые на защиту:
-
Аналитическое решение задачи оптимальной оценки состояний модулированного обобщенного полусипхрошюго потока событий при его полной наблюдаемости по наблюдениям за моментами наступления событий в потоке:
-
Аналитическое решение задачи оптимальной оценки состояний модулированного обобщенного полусипхрошюго потока событий при его неполной наблюдаемости (при наличии мертвого времени) по наблюдениям за момента-
ми наступления событий в наблюдаемом потоке:
-
Аналитическое решение задачи оценивания длительности мертвого времени в модулированном обобщенном полусипхрошюм потоке событий, функционирующем в условиях пепродлевающегося мертвого времени, по наблюдениям за моментами наступления событий в наблюдаемом потоке:
-
Алгоритм оптимальной оценки состояний модулированного обобщенного полусипхронпого потока событий при его полной наблюдаемости;
-
Алгоритм оптимальной оценки состояний модулированного обобщенного полусипхронпого потока событий при его неполной наблюдаемости (при наличии мертвого времени);
-
Алгоритмы оценивания длительности мертвого времени в модулированном обобщенном полусипхрошюм потоке событий, функционирующем в условиях пепродлевающегося мертвого времени, полученные методом максимального правдоподобия и модифицированным методом моментов;
-
Результаты статистического исследования предложенных оценок, полученные с помощью имитационной модели модулированного обобщенного полусипхронпого потока событий и разработанных алгоритмов оценки состояний потока в условиях его полной наблюдаемости, и оценки состояний и длительности мертвого времени в потоке, функционирующем в условиях неполной наблюдаемости.
Степень достоверности полученных результатов. Достоверность и обоснованность полученных результатов обеспечена строгими математическими доказательствами с использованием аппарата теории вероятностей, теории марковских случайных процессов, теории массового обслуживания, математической статистики, теории дифференциальных уравнений, математического анализа и линейной алгебры, корректностью методик исследования и проведенных расчетов, а также многочисленными статистическими экспериментами. проведенными па имитационной модели потока событий.
Апробация результатов исследования. Основные положения и результаты диссертации докладывались и обсуждались па следующих научных конференциях: Юбилейная 50-я международная научная студенческая конференция «Студент и научно-технический прогресс»: Математика, Новосибирск. 13-19 апреля 2012 г.; IX Российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур», Томск, 5-8 июня 2012 г.; 51-я международная научная студенческая конференция «Студент и научно-технический прогресс»: Математика, Новосибирск. 12-18 апреля 2013 г.: I Всероссийская молодежная научная конференция «Математическое и программное обеспечение информационных, технических и экономических систем», Томск, 17-18 мая 2013 г.; 5-я Международная научно-практическая конференция «Актуальные проблемы радиофизики», Томск, 1-6 октября 2013 г.; II Всероссийская молодежная научная конференция «Математи-
ческое и программное обеспечение информационных, технических и экономических систем», Томск, 16-17 мая 2014 г.; X Российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур», Алтайский край, 9-11 июня 2014 г.: XIII Междупарод-пая научно-практическая конференция имени А. Ф. Терпугова «Информационные технологии и математическое моделирование» (ИТММ-2014), Анжеро-Судженск, 20-22 ноября 2014 г.; Международная научная конференция, посвященная 80-летию профессора, доктора физико-математических паук Г. А. Медведева, «Теория вероятностей, случайные процессы, математическая статистика и приложения», Минск, 23-26 февраля 2015 г.; 2-я Международная летняя школа молодых ученых «Новые информационные технологии в исследовании сложных структур», Анапа, 8-12 июня 2015 г.; XIV Международная научно-практическая конференция имени А. Ф. Терпугова «Информационные технологии и математическое моделирование» (ИТММ-2015), Апжеро-Суджепск, 18-20 ноября 2015 г.; XI Международная конференция «Новые информационные технологии в исследовании сложных структур», Екатеринбург, 6-8 июня 2016 г.; XI Международная научно-практическая конференция имени А. Ф. Терпугова «Информационные технологии и математическое моделирование» (ИТММ-2016), Катупь, 12-16 сентября 2016 г.
Публикации. По материалам диссертации автором опубликовано 22 работы, из них 12 статей в журналах, включенных в Перечень рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертаций па соискание ученой степени кандидата паук, па соискание ученой степени доктора паук (из них 4 статьи в зарубежных изданиях. индексируемых Web of Science и Scopus), 10 публикаций в сборниках материалов международных и всероссийских научных конференций.
Личный вклад автора. Постановка представленных в диссертации задач сделана научным руководителем, д.т.н., профессором А. М. Торцевым. Полученные результаты, изложенные в исследовании и выносимые па защиту. принадлежат лично автору. Математические выкладки, программная реализация разработанных в ходе исследования алгоритмов и численные расчеты выполнены лично автором. В совместных публикациях научному руководителю А. М. Горцеву принадлежат постановки задач и указания основных направлений исследований: основные результаты теоретического исследования принадлежат автору, выкладки и численные расчеты выполнены лично автором.
Структура и объем диссертации. Диссертация состоит из введения, трех разделов, заключения, списка использованных источников и литературы. трех приложений. Общий объем диссертации составляет 199 страниц, включая приложения; иллюстративный материал представлен 23 рисунками (из них 9 в приложениях) и 21 таблицей; список использованных источников и литературы содержит 190 наименований.
Отделвно стоит отметитв, что одним из искажающих факторов при оценке состояний и параметров потока ввіступает мертвое время регистрирующих приборов. Необходимости рассмотрения случая мертвого времени вызвана тем, что на практике любое регистрирующее устройство затрачивает на измерение и регистрацию собвгтия некоторое конечное время, в течение которого оно не способно правилвно обработатв следующее собвгтие, т.е. собвітие, поступившее на обслуживающий прибор, порождает период так называемого мертвого времени [3, 5, 119, 175], в течение которого другие наступившие собвгтия потока недоступнві наблюдению (теряются). По-видимому, одним из перввіх примеров наличия мертвого времени можно считатв регистрацию интенсивности ядерного излучения прибором, получившим название счетчика Гейгера-Мюллера. Одна из особенностей действия данного прибора состоит в том, что частица, попавшая в счетчик и ввивавшая в нем разряд, запирает счетчик на некоторое время для подсчета новвіх частиц. Вообще говоря, это время зависит от характера зарегестрированной чистины и от той энергии, которую она несет, но часто в ядерной физике ограничиваются предположением, что это время постоянно. В частности, подобнвю ситуации встречаются и в компвютернвіх сетях, например, при исполвзовании протокола случайного множественного доступа с обнаружением конфликта (протокол CSMA/CD [145]). В момент регистрации (обнаружения) конфликта на входе некоторого узла сети по сети рассылается сигнал «заглушки»; в течение времени рассылки сигнала «заглушки» заявки, поступившие в данный узел сети, получают отказ в обслуживании и направляются в источник повторнвіх ввізовов. Здесв время, в течение которого узел сети закрыт для обслуживания заявок, поступающих в него после обнаружения конфликта, можно трактоватв как мертвое время прибора, регистрирующего конфликт в узле сети. В конкретнвіх устройствах величина и характер мертвого времени зависят от многих факторов. Все устройства регистрации с достаточной степенвю приближения можно разделитв на две группы. Первую группу составляют устройства с непродлеваюгцемся мертвым временем, которое не зависит от поступления других собвітий в пределах его действия. Непродлеваюгцееся мертвое время иногда называют мертвым временем первого рода, а соответствующие устройства регистрации - счетчиками типа I. Ко второй группе относятся устройства с продлевающимся мертвым временем. В этом случае мертвое время возникает после любого собвгтия, поступившего на вход системні, вне зависимости от факта его регистрации. Устройства, обладающие продлевающимся мертвым временем, называют счетчиками типа II, а само мертвое время - мертвым временем второго рода [3]. Вопросам анализа искажающего влияния мертвого времени при регистрации случайных потоков уделяется болвшое внимание. Наиболее ПОЛНВІЙ обзор литературы по данному направлению можно найти в [3], в книгах [3, 5, 119] вопросу влияния мертвого времени посвященві отделвнвіе параграфы. Стоит отметитв, что болвшое количество исследований дважды стохастических потоков собвітий и систем массового обслуживания с входящими два- ждві стохастическими потоками собвітий бвіло проведено такими учеными как А. Ф. Терпугов, А. М. Горцев, А. А. Назаров, К. И. Лившиц, С. П. Сущенко, С. П. Моисеева, Л. А. Нежелвская, А. Н. Моисеев - в Томском государственном университете [59, 85, 87, 97, 99, 100, 102, 109, 116, 158-160]; Г. А. Медведев, А. Н. Дудин, В. И. Клименок, Г. В. Царенков - в Белорусском государственном университете [69, 71, 93-95, 127]; Ю. В. Малинковский - в Гомелв- ском университете [88-90]; М. А. Маталыцкий - в Гродненском университете [91, 92]; В. В. Рвіков - в Российском государственном университете нефти и газа им. И. М. Губкина [67, 153]; Г. П. Башарин, П. П. Бочаров, А. В. Печинкин, К. Е. Самуйлов, Ю. В. Гайдамака - в Российском университете Дружбы народов [23, 24, 27, 41, 113, 114]; В. М. Вишневский - в Институте проблем передачи информации им. А. А. Харкевича Российской академии наук [37-39]; М. П. Фархадов - в Институте проблем управления им. В. А. Трапезникова Российской академии наук [118]; Н. И. Головко, В. В. Катрахов, Г. Ш. Цициашвили - в Институте прикладной математики Далвневосточного отделения Российской академии наук [44-46, 128]; М. А. Федоткин, А. В. Зорин - в Нижегородском государственном университете имени Н. И. Лобачевского [73, 74, 190]; Д. Ефросинии - в университете Johannes Kepler University Linz (Austria) [153]; М. Пага- HO - в Пизанском университете (Pisa, Italy) [149]; M. F. Neuts, D. M. Lucantoni, A. D. Banik, U. C. Gupta - в США [137, 171, 172, 174] и другими учеными. Задачи по оцениванию состояний и параметров потоков событий, а также оценке длителвности мертвого времени рассматривалисв преимущественно в работах А. М. Горцева и его учеников. При этом в [51-53] получены резулвта- ты для пуассоновского потока событий, в [32, 144] - для синхронного дважды стохастического потока событий, в [34, 35] - для асинхронного дважды стохастического потока событий, в [47, 48] - для асинхронного дважды стохастического потока событий с произволвным числом состояний, в [59, 158] - для полусинхронного дважды стохастического потока событий, в [160] - для МАР-потока событий и др. При этом в [32, 47, 49, 62] исследования проведены в условиях отсутствия мертвого времени; в [34, 35, 51, 58, 61] исследования проведены для непродлевающегося мертвого времени, в [35, 53, 59, 106] - для продлевающегося мертвого времени. Таким образом, проведено достаточно болвшое количество исследований дважды стохастических потоков событий с точки зрения задач определения характеристик систем массового обслуживания, оценивания параметров и состояний потока. Тем не менее, нелвзя сказатв, что построенными моделями исчерпываются все потоки с двумя состояниями, аппроксимирующие реалвные потоки событий. Протоколы в компыотерных сетях таковы, что при определении окна передачи информации сервером (то еств в случае асинхронного или полусинхронного потоков), в канал могут поступатв так называемые до- полнителвивіє события, представляющие собой пакеты-уведомления на открытие и/или закрытие окна передачи. Такие события названы дополнителвивши, поскольку не являются событиями пуассоновского потока, а вызываются переходом случайного процесса (интенсивности потока) из состояния в состояние. Дополнительные события могут значительно изменить картину потока и исказить результаты оценивания состояний и параметров потока, поэтому Отделвно стоит отметитв, что одним из искажающих факторов при оценке состояний и параметров потока ввіступает мертвое время регистрирующих приборов. Необходимости рассмотрения случая мертвого времени вызвана тем, что на практике любое регистрирующее устройство затрачивает на измерение и регистрацию собвгтия некоторое конечное время, в течение которого оно не способно правилвно обработатв следующее собвгтие, т.е. собвітие, поступившее на обслуживающий прибор, порождает период так называемого мертвого времени [3, 5, 119, 175], в течение которого другие наступившие собвгтия потока недоступнві наблюдению (теряются). По-видимому, одним из перввіх примеров наличия мертвого времени можно считатв регистрацию интенсивности ядерного излучения прибором, получившим название счетчика Гейгера-Мюллера. Одна из особенностей действия данного прибора состоит в том, что частица, попавшая в счетчик и ввивавшая в нем разряд, запирает счетчик на некоторое время для подсчета новвіх частиц. Вообще говоря, это время зависит от характера зарегестрированной чистины и от той энергии, которую она несет, но часто в ядерной физике ограничиваются предположением, что это время постоянно. В частности, подобнвю ситуации встречаются и в компвютернвіх сетях, например, при исполвзовании протокола случайного множественного доступа с обнаружением конфликта (протокол CSMA/CD [145]). В момент регистрации (обнаружения) конфликта на входе некоторого узла сети по сети рассылается сигнал «заглушки»; в течение времени рассылки сигнала «заглушки» заявки, поступившие в данный узел сети, получают отказ в обслуживании и направляются в источник повторнвіх ввізовов. Здесв время, в течение которого узел сети закрыт для обслуживания заявок, поступающих в него после обнаружения конфликта, можно трактоватв как мертвое время прибора, регистрирующего конфликт в узле сети. В конкретнвіх устройствах величина и характер мертвого времени зависят от многих факторов. Все устройства регистрации с достаточной степенвю приближения можно разделитв на две группы. Первую группу составляют устройства с непродлеваюгцемся мертвым временем, которое не зависит от поступления других собвітий в пределах его действия. Непродлеваюгцееся мертвое время иногда называют мертвым временем первого рода, а соответствующие устройства регистрации - счетчиками типа I. Ко второй группе относятся устройства с продлевающимся мертвым временем. В этом случае мертвое время возникает после любого собвгтия, поступившего на вход системні, вне зависимости от факта его регистрации. Устройства, обладающие продлевающимся мертвым временем, называют счетчиками типа II, а само мертвое время - мертвым временем второго рода [3]. Вопросам анализа искажающего влияния мертвого времени при регистрации случайных потоков уделяется болвшое внимание. Наиболее ПОЛНВІЙ обзор литературы по данному направлению можно найти в [3], в книгах [3, 5, 119] вопросу влияния мертвого времени посвященві отделвнвіе параграфы. Стоит отметитв, что болвшое количество исследований дважды стохастических потоков собвітий и систем массового обслуживания с входящими два- ждві стохастическими потоками собвітий бвіло проведено такими учеными как А. Ф. Терпугов, А. М. Горцев, А. А. Назаров, К. И. Лившиц, С. П. Сущенко, С. П. Моисеева, Л. А. Нежелвская, А. Н. Моисеев - в Томском государственном университете [59, 85, 87, 97, 99, 100, 102, 109, 116, 158-160]; Г. А. Медведев, А. Н. Дудин, В. И. Клименок, Г. В. Царенков - в Белорусском государственном университете [69, 71, 93-95, 127]; Ю. В. Малинковский - в Гомелв- ском университете [88-90]; М. А. Маталыцкий - в Гродненском университете [91, 92]; В. В. Рвіков - в Российском государственном университете нефти и газа им. И. М. Губкина [67, 153]; Г. П. Башарин, П. П. Бочаров, А. В. Печинкин, К. Е. Самуйлов, Ю. В. Гайдамака - в Российском университете Дружбы народов [23, 24, 27, 41, 113, 114]; В. М. Вишневский - в Институте проблем передачи информации им. А. А. Харкевича Российской академии наук [37-39]; М. П. Фархадов - в Институте проблем управления им. В. А. Трапезникова Российской академии наук [118]; Н. И. Головко, В. В. Катрахов, Г. Ш. Цициашвили - в Институте прикладной математики Далвневосточного отделения Российской академии наук [44-46, 128]; М. А. Федоткин, А. В. Зорин - в Нижегородском государственном университете имени Н. И. Лобачевского [73, 74, 190]; Д. Ефросинии - в университете Johannes Kepler University Linz (Austria) [153]; М. Пага- HO - в Пизанском университете (Pisa, Italy) [149]; M. F. Neuts, D. M. Lucantoni, A. D. Banik, U. C. Gupta - в США [137, 171, 172, 174] и другими учеными. Задачи по оцениванию состояний и параметров потоков событий, а также оценке длителвности мертвого времени рассматривалисв преимущественно в работах А. М. Горцева и его учеников. При этом в [51-53] получены резулвта- ты для пуассоновского потока событий, в [32, 144] - для синхронного дважды стохастического потока событий, в [34, 35] - для асинхронного дважды стохастического потока событий, в [47, 48] - для асинхронного дважды стохастического потока событий с произволвным числом состояний, в [59, 158] - для полусинхронного дважды стохастического потока событий, в [160] - для МАР-потока событий и др. При этом в [32, 47, 49, 62] исследования проведены в условиях отсутствия мертвого времени; в [34, 35, 51, 58, 61] исследования проведены для непродлевающегося мертвого времени, в [35, 53, 59, 106] - для продлевающегося мертвого времени. Таким образом, проведено достаточно болвшое количество исследований дважды стохастических потоков событий с точки зрения задач определения характеристик систем массового обслуживания, оценивания параметров и состояний потока. Тем не менее, нелвзя сказатв, что построенными моделями исчерпываются все потоки с двумя состояниями, аппроксимирующие реалвные потоки событий. Протоколы в компыотерных сетях таковы, что при определении окна передачи информации сервером (то еств в случае асинхронного или полусинхронного потоков), в канал могут поступатв так называемые до- полнителвивіє события, представляющие собой пакеты-уведомления на открытие и/или закрытие окна передачи. Такие события названы дополнителвивши, поскольку не являются событиями пуассоновского потока, а вызываются переходом случайного процесса (интенсивности потока) из состояния в состояние. Дополнительные события могут значительно изменить картину потока и исказить результаты оценивания состояний и параметров потока, поэтому очевидна необходимость построения и исследования моделей дважды стохастических потоков событий с двумя состояниями и наличием дополнительных событий при переходе из состояния в состояние. Данные потоки получили название обобщенных потоков событий и впервые были исследованы в работах [49, 54, 62]. чевидна необходимость построения и исследования моделей дважды стохастических потоков событий с двумя состояниями и наличием дополнительных событий при переходе из состояния в состояние. Данные потоки получили название обобщенных потоков событий и впервые были исследованы в работах [49, 54, 62]. Алгоритм оптимального оценивания состояний потока при его полной наблюдаемости
Вероятность ошибки при оценивании состояний модулированного обобщенного полусинхронного потока событий
Для получения явного вида апостериорнвіх вероятностей w(Xi\t)7 і = 1, 2, модулированного обобщенного полусинхронного потока собвітий докажем нес- колвко вспомогателвнвіх лемм.
Лемма 1.1. Длительность пребывания процесса X (t) в первом состоянии распределена, по экспоненциальному закону с параметром рХ1 + Д Fx (г) = 1 — е—(рХі+/3)т, г 0. Доказательство. По определению модулированного обобщенного полусинхронного потока собвітий длителвноств пребвівания процесса Л (t) в первом состоянии определяется двумя случайными величинами: 1) первая случайная величина Д распределена по экспоненциалвному закону с параметром Д. F-1(1) (т) = = 1 — е—/3\ т 0; 2) вторая случайная величина Д распределена по экспоненциалвному закону с параметром рХр. F(2\T) = 1 — e—pXl\ т 0 [119]. Тогда длителвноств пребвівания процесса Л (t) в первом состоянии еств случайная величина р = тіп{ДД2}7 представляющая собой минимум из двух независимых случайных величиных Д и 2, следователвно, случайная величина = тт{ДД2} имеет экспоненциальное распределение с параметромрХ\ +Д. F1(r) = 1 — e- ypXl+ T, г 0 [101]. Лемма доказана.
Доказательство. Докажем, что после произволвного момента времени to поведение процесса Л (t) не зависит от предвістории, т.е. не зависит от того, как протекал процесс Л (t) до момента времени t0. Поведение процесса Л (t) после момента времени to зависит только от того, в каком состоянии процесс Л (t) находится в момент времени to Пусть в момент времени / процесс A (t) находится в і-м состоянии (і = = 1, 2). Поскольку длительность пребывайия процесса Л (t) в г -м состоянии является случайной величиной, имеющей экспоненциальное распределение (в первом состоянии - с параметромр\1 + Д во втором - с параметром а), обладающее свойством отсутствия последействия, то оставшаяся часть длительности пребывания процесса Л (t) в том или ином состоянии не зависит от того, как долго до момента времени to процесс Л (t) находился в этом состоянии. Переход процесса Л Д) из г-го состояния в j-e (і = j; i,j = 1, 2) полностью определяется моментом окончания пребывания процесса Л (t) в состоянии г.
Таким образом, поведение процесса Л (t) не зависит от предыстории, а зависит только от состояния процесса в момент времени to Следовательно, Л (t) - марковский процесс. Так как Л (t) является принципиально ненаблюдаемым, то Л (t) - скрытый марковский процесс. Лемма доказана.
Получим явный вид априорных стационарных вероятностей состояний процесса Л (t). Обозначим через щ (г = 1, 2) - априорную стационарную вероятность того, что процесс Л (t) в любой момент времени находится в г -м состоянии. Для вероятностей щ (г = 1,2) справедлива лемма 1.3. Лемма 1.3. Априорные стационарные вероятности состояний процесса X (t) есть а
Доказательство. Обозначим через л (тТО), І = 1,2 - вероятность того, что случайный процесс Л (t) (поток событий) в момент времени т находится в г -м состоянии при условии, что функционирование потока началось в момент времени ТО. Тогда для вероятностей ті(тТО и Т2(Тт0) справедлива система дифференциальных уравнений: я! (т ТО) = -(рХі + р )лДл ТО) + a 2 (т ТО), л2(тТО) = (рХі + р)лі(тТО) - а%2(тТО), с начальными условиями ті(т = т0т0) = я, л2(л = т0т0) = 1 — л, решая которую, находим яфт ТО) = 2 (т ТО) = а рХі + Р + а рХ і + р рХі + Р + а + а л — л — рХі + Р + а а 3 —(рЛі+ +а)(г—TQ) 3 —(рЛі+ +а)(г—TQ) рХі + Р + а Для рассматриваемого стационарного режима функционирования потока событий имеет место т го. Тогда лц л2 определяются в виде (1.2.1). Лемма доказана.
Момент t вынесения решения о состоянии потока будет принадлежать интервалу (tk Ак+р, к = 1,2,..., между соседними событиями потока. Для начального интервала (t0,t\) момент t будет лежать между моментом начала наблюдения за потоком t0 (to = 0) и первым наблюденным событием потока. Рассмотрим интервал (tk, tk+і), значение длительности которого есть Tk = tk+і — tk, к = 0,1,.... Для вывода формулві апостериорной вероятности w(X1[t) исполвзуем известную методику [120]: сначала рассмотрим дискретнвю наблюдения через рав- нвіе достаточно малвіе промежутки времени At, а затем совершим предельный переход при стремлении At к нулю. Пусть время меняется дискретно с шагом At: t = nAt, п = 0,1,.... Введем в рассмотрение двумерный процесс (A(n), гп), где Х(п) = X(nAt) - значение процесса A (t) в момент времени nAt (А(п) = А{, і = 1, 2) rn = rn(At) = г (nAt) — г((п — 1)At) - число событий потока, наблюденных на временном интервале ((п — 1)At, nAt) длительности At, rn = 0,1,.... Обозначим через Rm = (r0, r1,..., rm) последовательность значений числа наблюденных событий на интервалах ((п — 1)At, nAt) длительности At (п = 0,т). Здесь г0 - число событий, наблюденных на интервале (—At, 0). Это число не определено, так как на этом интервале наблюдений не производится, поэтому его можно задать произвольным, например г0 = 0. Обозначим через Л(то) = (А(0), А(1),..., \(т)) последовательность неизвестных (ненаблюдаемых) значений A (nAt) процес са A (t) в моменты вре мени nAt (п = 0, т); А(0) = А(0) = Хг, і = 1, 2.
Оценка длительности мертвого времени методом максимального правдоподобия
Полученные в подразделах 2.2, 2.3 результаты делают возможным решение задачи оценивания длительности мертвого времени в модулированном обобщенном полусинхронном потоке событий, функционирующем в условиях неполной наблюдаемости. Как было отмечено ранее, в течение периода мертвого времени происходит потеря событий потока. Для того чтобы оценить потери (или количество потерянных событий потока), возникающие из-за эффекта мертвого времени, необходимо оценить длительность мертвого времениТ. Рассмотрим за дачу оценивания длительности мертвого времени методом максимального прав 97 доподобия.
По-прежнему рассматривается стационарный режим функционирования потока собвітий, поэтому переходивши процессами на полуинтервале наблюдений Д0Д], где t0 _ начало наблюдений, t - окончание наблюдений (момент вынесения решения), пренебрегаем. Тогда без потери общности можно положити to = 0 Посколвку процесс Л (t) является принципиалвно ненаблюдаемым, то говорити о состоянии потока можно толвко в вероятностном смвісле. Вся доступная информация о потоке - это моментві t2j ..., tn+\ наступления собвітий с момента to начала наблюдений за потоком до момента времени t. Параметрві потока АІ5 А2, д, Д а, 5 полагаются известивши, длителвноств мертвого времени Т неизвестна. Необходимо в момент окончания наблюдений (в момент времени t) на основании ввіборки Д О, ..., tn+l наблюденнвіх моментов наступления собвітий потока получитв методом максималвного правдоподобия оценку Т длителвности мертвого времени.
Обозначим через ту = tk+i — Д, к = 1,2,..., значение длителвности к-го интервала между соседними собвітиями наблюдаемого потока (ту 0). Так как рассматривается стационарный режим функционирования потока, плотности вероятности значений длителвности к-го интервала еств рт(ту) = рт(т), т 0, для любого к (индекс Т подчеркивает, что плотности вероятности зависит от длителвности мертвого времени). В силу ЭТОГО момент времени tk без потери общности можно положити равным нулю, т.е. момент наступления собвгтия еств т = 0.
Обозначим здесв и далее Д = рХ1 + Д Д = а. Для удобства далвнейших выкладок и доказателвств преобразуем ввіра 98 ЖЄНИЄ (2.2.10) ДЛЯ одномерной ПЛОТНОСТИ вероятности Рт(т), т 0, к виду 0, 0 т Т, Рт (г) = Z1 Z2 - Z1 %2 X А + @2 f (Т) е-ч(г-Т)_ Л х - 1 (2.4.1) А + @2 f (Т) 3- 2(г-Т) т Т, f (Т) — A1G + (р\1 + Р) (Л2 + оА) + о;(А1 — А2 — GA) Х g-(4l+ 2 )Т Х {(PM + P) [Ax(1 - p + p6) - A2 + dp] - p\1a} F , F (T) — Z1Z2 - qe- 1 + 2)T, q — A1 [A2 - p (X2 + oA)] , 1,2 — [A + A + a + P T \J(A - A2 - G + [3)2 + 4оф(1 - 6)], 0 щ Z2.
Пуств n — t2 - , T2 — h - A, , rn — tn+1 - tn, n 0 2 0, ..., тп 0 - последователвноств измереннвіх в резулвтате наблюдения за потоком в течение полуинтервала наблюдений (0,] значений длителвностей интервалов между соседними собвгтиями потока.
При построении функции правдоподобия учтем имеющуюся априорную информацию: 1) из конструкции наблюдаемого потока собвітий (см. рисунок 1.3) вытекает, что значение длителвности мертвого времениТ Tmjn, где ттіп — min Tk (к — 1,п); 2) наблюдаемый поток в общем случае является коррелированным потоком собвітий (см. теорему 2.2); 3) формулу ДЛЯ совместной n-мерной ПЛОТНОСТИ РТ(Т1,...,ТП) получитв в явном виде не представляется возможным; 4) конструкция наблюдаемого потока собвітий (см. рисунок 1.3) такова, что корреляционнвіе связи в последователвности наблюденнвіх величин Тц ..., тп ослабевают по мере увеличения значения длителвности мертвого времени; 5) при выполнении условий рекуррентности (см. пункт 2.3.2) наблюдаемый поток становится рекуррентным, т.е. последовательность тц ..., тп представля ет собой значения независимых одинаково распределеннвіх случайных величин. Тогда при выполнении первого либо второго условий рекуррентности с очевид- ноствю следует, что оценка максималвного правдоподобия значения длительности мертвого времени есть Т = ттіп. Для третьего условия рекуррентности оценка максимального правдоподобия есть Т ттіп.
Приведенные предпосылки позволяют воспользоваться (в случае коррелированного наблюдаемого потока) методом максимального правдоподобия в его обычной форме: выписать совместную п-мерную плотность рт(ті, ...,тп) в виде произведения одномерных плотностей Рт(т(fc)), к = 1,п. Очевидно, что такой подход закладывает внесение погрешности при получении оценки длительности мертвого времени методом максимального правдоподобия.
Упорядочим величины ті, Т2, ..., тп по возрастайию: rmin = г(1) т(2) ... т(п). Тогда функция правдоподобия [130] с учетом (2.4.1) запишется в виде L (тт(1 ,...,г " ) = ПРТ(т Д 0 Т тт,„, к=1 L(TТ(1),...,т(таЛ =0, Т Поскольку задача заключается в построении оценки Т длительности мертвого времени в предположении, что все параметры потока АІ5 А2, ц, Д, а, 5 известны, то согласно методу максимального правдоподобия, ее реализация есть решение оптимизационной задачи: П L (тт(1),..., т(п)) = рт(т(к)) = max, 0 Т ттгп, ттт 0, (2.4.2) к=1 где рт (т(fc)) определена в (2.4.1) длят = т (к\ к = 1,п. Значение Т, при котором функция правдоподобия (2.4.2) достигает своего глобального максимума, есть оценка Т длительности мертвого времени.
Результаты численных расчетов вероятности ошибки при оценивании состояний потока
В настоящем подразделе приводятся резулвтатві статистических экспериментов ПО ВВІЧИСЛЄНИЮ условной вероятности P0(w(X1[tk + 0), Tk) вынесения ошибочного решения В любой момент времени Тк 0 к = 0,1,..., для общего случая и безусловной вероятности ошибки Р0 ДЛЯ особого случая соотношения параметров (Аі — А2 — аб = 0, Аі (1 — р) — аб = 0) для различнвіх значений параметров модулированного обобщенного полусинхронного потока собвітий. Приведеннвш в подразделе 1.6 алгоритм расчета условной вероятности ошибки P0(w(X1[tk + 0),Tk) в любой момент времени Tk 0 к = 0,1,..., положен в основу реализации программві расчета для проведения статистических экспериментов С ЦЄЛВЮ ВВІЧИСЛЄНИЯ условной вероятности ошибки P0(w(X1[tk + 0),Tk) для общего случая.
На первом этапе эксперимента осуществляется имитационное моделирование потока при зила иных значениях параметров потока и заданном времени моделирования и как резулвтат получение истинной траектории процесса A (t) и временнвіх моментов tii t2) ... наступления собвітий потока. На втором этапе производится непосредственное ввічисление апостериорнвіх вероятностейш(А1т0), То = t — to 0 w(Xiltk + 0) к = 1,2, ...; w(Xilrk), Tk = t — tk 0 к = 1,2,..., по формулам (1.6.2), (1.6.3); построение оценки X(t) процесca X(t) и вычисление условной вероятности ошибки P0(w(X1[tk + 0),тк) к = 0,1,..., для общего случая.
В качестве иллюстрации на рисунке 3.7 приведен пример реализации потока событий при следующих значениях параметров: Х1 = 0.8, Х2 = 0.2, р = 0.2, f3 = 0.5, а = 0.8, 5 = 0.9 и времени моделирования Тт = 1000. В верхней части рисунка 3.7 (ось 1) приведена траектория случайного процесса X(t) (истинная траектория процесса АЦ)), полученная путем имитационного моделирования. Цифрами 1, 2 обозначены первое и второе состояния процесса X(t) соответственно. На оси 1 отображены события модулированного обобщенного полусинхронного потока событий: белыми кружками отображены события пуассоновских потоков, черными кружками отображены дополнительные события, которые могут наступить в первом состоянии потока при переходе процесса X(t) из второго состояния в первое. На оси 2 все события потока отображены одинаково (белыми кружками).
Траектории процесса X(t) (верхняя часть рисунка) и оценки \(t) (нижняя часть рисунка) (Ai = 0.8, А2 = 0.2, р = 0.2, X = 0.5, а = 0.8, 6 = 0.9) В нижней части рисунка 3.7 (ось 3) приведена траектория оценки X(t) процесса X(t). Цифрами 1, 2 обозначены первое и второе состояния оценки X(t) соответственно. На оси 3 жирными линиями отмечены промежутки, на которых оценка АЦ) не совпадает с истинным значением процесса X(t) (область ошибочных решений). Расчет апостериорной вероятности ш(Аіт ), к = 0,1,..., и вынесение решения о состоянии процесса X(t) производилось с шагом At = 0.001.
На рисунке 3.8 приведена траектория поведения апостериорной вероятности w(X1\rk), к = 0,1,..., первого состояния процесса X(t), соответствующая полученной при имитационном моделировании последовательностиЦ, Ц, ... на ступления событий модулированного обобщенного полусинхронного потока событий (см. рисунок 3.7, ось 2). Цифрами 1, 0.5, 0 обозначены возможные значения апостериорной вероятности по оси ординат. На рисунке 3.9 приведена траектория условной вероятности ошибки P0(w(\iltk + 0),Tk), к = 0,1,..., соответствующая той же последовательности наступления событий. Цифрами 1, 0.5, 0 обозначены возможные значения условной вероятности по оси ординат.
Таким образом, при реализации предложенного алгоритма в любой момент времени осуществляется оценка состояния процесса АД) и одновременно вычисляется условная вероятность ошибки при вынесении решения о состоянии процесса АД).
Для особого случая соотношения параметров потока (Ai — А2 — аб = 0, Ay (1 — р) — аб = 0) построены графики безусловной вероятности ошибки Р0 для различных значений параметров модулированного обобщенного полусинхронного потока событий и для любого полуинтервала [Ц, Ц+1), к = 1, 2,....
Алгоритм расчета состоит из следующих этапов: 1) задается ft; 2) вычисляется Р, w(\\\tk + 0); 3) определяется один из шести возможнвіх вариантов (см. пункт 1.6.2), и ввічисляєтся значение Ро для этого варианта; 4) значение ft увеличивается; 5) алгоритм переходит на шаг 1 и т.д. В качестве иллюстрации на рисунке 3.10 представлены графики изменения значений безусловной вероятности ошибки Ро в зависимости от значений параметров потока: 1 - при Ai = 4, А2 = 0.8, р = 0.2, а = 4, $ = 0.8; 2 - при А1 = 5 А2 = 1.8 Р = 0.36 а = 4, 6 = 0.8 Параметр ft изменяется по оси абсцисс и принимает значения 0.05, 0.1, 0.2 и так далее до 10.
Поясним поведение Ро на рисунке 3.10. При малвіх значениях ft (по сравнению со значением а) процесс A(t) будет находитися преимущественно в первом состоянии, тої да различимость первого и второго состояний в вероятностном смысле будет достаточно высока, и соответственно вероятность ошибки мала. При увеличении ft (при его стремлении к а) различимость состояний ухудшается, и соответственно увеличивается вероятность ошибки. При дальнейшем увеличении ft (по сравнению со значением а) процесс A(t) будет преимущественно находиться во втором состоянии, тої да различимость первого и второго состояний улучшается, и соответственно уменьшается вероятность ошибки.
В настоящем подразделе приводятся результаты статистических экспериментов по вычислению оценок длительности мертвого времени методом максимального правдоподобия (МП-оценок) и модифицированным методом моментов (ММ-оценок) для различных значений параметров модулированного обобщенного полусинхронного потока событий. Приведенный в разделе 2 алгоритм нахождения единственной оценки Тмм длительности мертвого времени положен в основу реализации программы расчета.
Эксперимент заключается в следующем: 1) при заданных значениях параметров потока Ai, А2, р, А а, 3, Т и заданном времени моделирования Тт осуществляется имитационное моделирование потока и как результат получение истинной траектории процесса X(t) и последовательности значений длительностей временных интервалов тІ5 т2, ..., тп (п = 2,3,...); 2) находится оценка максимального правдоподобия длительности мертвого времени Тмп = min (г.min = minткі к = l,n); 3) вычисляется статистика (2.5.4), решается уравнение (2.5.6), и осуществляется реализация алгоритма нахождения единственной оценки Тмм длительности мертвого времени модифицированным методом мо ментов; 4) осуществляется повторение N раз (j = l ,N) шагов 1-3 для получения выборок достаточного объема.