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

Актуальность работы. Развитие теории массового обслуживания определялось (и определяется) исследованием систем связи, транспортных систем, систем управления запасами и других систем. Например, в [9] отмечается, что системы связи как объекты приложений математической теории массового обслуживания и поныне являются доминирующими. В последние два десятилетия появилась еще одна важная сфера приложений теории массового обслуживания — проектирование и создание информационно-вычислительных систем, объединяющих в себе большое количество компьютеров, а также компьютерных сетей связи, спутниковых систем связи и т. п.

В этой связи различным аспектам математической теории массового обслуживания и ее приложениям посвящена обширная литература как отечественных, так и зарубежных авторов. Основы теории заложены в монографиях А. Я. Хинчина [81], Б. В. Гнеденко, И. Н. Коваленко [14], Г. П. Климова [42], Т. JL Саати [71], А. Кофмана, Р. Крюона [50], Д. Риордана [66], JL Клейнрока [41]. Дальнейшее развитие теории массового обслуживания связано с изучением различного рода приоритетных систем, которым посвящены монографии Б. В. Гнеденко, Э. А. Даниэляна, Б. Н. Димитрова, Г. П. Климова, В. Ф. Матвеева [16], О. И. Бронштейна, И. М. Духовного [6], В. В. Мовы, JT. А. Пономаренко, А. М. Ка-линовского [54], Г. П. Климова, Г. К. Мишкоя [43], М. И. Волковинского, А. Н. Кабалевского [11], Н. Джейсуола [28]. Методы теории массового обслуживания в достаточно сжатой форме изложены в монографии Д. Ке-нига, Д. Штояна [40]. Основные элементы тенденций развития теории массового обслуживания даны в работе Г. И. Ивченко, В. А. Каштанова, И. Н. Коваленко [36]. Обширная библиография по различным аспектам теории массового обслуживания и ее приложениям, а также направлениям исследований приведены в целом ряде обзорных статей (И. Н. Коваленко [44, 45], Б. В. Гнеденко, И. Н. Коваленко [15], В. В. Рыков [69], М. А. Файнберг, Е. А. Файнберг [78], Ю. К. Беляев, Б. В. Гнеденко, И. А. Ушаков [4], Ю. Бхат [9], Д. Кениг, В. В. Рыков, Ф. Шмидт [39]).

Одним из перспективных и актуальных направлений в теории массового обслуживания и ее приложениях, как отмечалось, по-видимому, впервые в [15, 44], является направление, связанное с управляемыми системами массового обслуживания (СМО). Одними из первых работ, в которых ставятся и решаются задачи оптимизации управлений в СМО, являются работы [7, 8, 10, 12, 68, 70, 88, 102, 112, 113], появившиеся в середине шестидесятых годов. Последовавшие за первыми статьями в этой области многочисленные публикации связаны с различными оптимизационными постановками задач и их решением. Достаточно полные обзоры работ по управляемым СМО, появившиеся до середины 70-х годов, даны в [69, 78, 17, 57]. Анализ этих и последующих работ позволяет заключить, что исследования, проводимые в области управляемых СМО, наиболее интенсивно ведутся по изучению а) приоритетных систем (например, систем с динамическими (ситуационными, ка-тегорийными во времени) приоритетами (характерные публикации — [27, 55, 70, 88, ЮЗ])), б) систем с управляемыми длительностями обслуживания (например, систем с изменяющейся интенсивностью обслуживания (публикации [29, 72, 87, 104, 109, 113]), систем с изменяющейся функцией распределения длительности обслуживания (характерные работы ¦— [33, 38, 67, 108, 111])), в) систем с управляемым входящим потоком заявок (например, систем с изменяющейся интенсивностью входящего потока заявок (работы [35, 46, 99]), систем с формированием очередей (работы [56, 59, 77, 90])), г) систем с управляемой (переменной) структурой (например, систем с резервными обслуживающими каналами (публикации [1, 34, 51, 85, 95, 96, 97, 98, 106, 107])).

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

Подавляющее число авторов рассматривает ситуации, когда все параметры, характеризующие СМО, точно известны. Однако в реальности дело обстоит, как правило, иначе. Если в отношении параметров, характеризующих обслуживающие устройства, можно сказать, что они известны и с течением времени не меняются, то в отношении интенсивностей входящих потоков или других их параметров этого сказать в многих случаях нельзя. Интенсивность входящих потоков обычно меняется со временем, часто эти изменения носят случайный характерпоследнее приводит к рассмотрению дважды стохастических потоков событий (понятие впервые введено Кингмэном [91] в 1964 году). С другой стороны, очевидно, что функционирование СМО непосредственно зависит от интенсивностей входящих потоков заявок: чем больше интенсивности входящих потоков, тем напряженнее режим обслуживания, требующий, например, подключения дополнительных обслуживающих приборов.

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

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

Рассматривая потоки событий с интенсивностью, зависящей от времени и являющейся случайным процессом, можно выделить два различных типа потоков. К первому типу относятся потоки с интенсивностью Л (£), являющейся непрерывным случайным процессом. Примером исследований задач, связанных с оценкой интенсивности такого рода потоков, являются работы А. Ф. Терпугова и С. А. Поттосиной [65], Е. В. Глуховой [13]. Ко второму типу можно отнести потоки, для которых интенсивность А (£) есть дискретный (кусочно-постоянный) процесс с конечным числом состояний (Ai, Л2, — • •, Ап). Переход процесса A (t) из состояния в состояние происходит в случайные моменты времени, при этом на интервалах времени, когда процесс Л (£) находится в состоянии Лг-, поток событий ведет себя как стационарный пуассоновский поток с интенсивностью Аг-. Такие потоки событий могут быть названы кусочно-стационарными и являются наиболее характерными для реальных вычислительных сетей и систем. По-видимому, впервые потоки второго типа применительно к системам массового обслуживания были рассмотрены в работах М. Ньютса [100] и Г. П. Башарина [2]. В последней работе был рассмотрен поток событий, для которого переход из состояние в состояние управлялся марковской цепью (отсюда название «МС (Markov сЬат)-потоки событий»). Развитие исследований СМО с кусочно-стационарными марковскими потоками событий (публикации [58, 86, 92, 93, 94, 101, 105]) привели к созданию модели ВМАР (Batch Markovian Arrival Process) -потоков. Одной из последних и наиболее полных работ, посвященных исследованию различных систем массового обслуживания с входящими ВМАР-потоками, является, по мнению автора, монография А. Н. Дудина и В. И. Климе-нок [32]. В целом такого рода кусочно-стационарные потоки событий могут быть разделены на 3 класса: 1) потоки с интенсивностью, для которой переход из состояния в состояние происходит только в случайные моменты времени, являющиеся моментами наступления событий потока (или синхронные дважды стохастические потоки событий), 2) потоки с интенсивностью, для которой переход из состояния в состояние не зависит от моментов наступления событий на интервале стационарности и их количества (или асинхронные потоки событий), и 3) потоки, в которых для одного подмножества множества состояний справедливо 1, а для остальных состояний справедливо 2 (или полусинхронные потоки событий). В научной литературе описанные потоки исследуются с двух точек зрения: постороения оценок состояний и параметров ненаблюдаемой интенсивности потока (работы [65, 13, 3, 20, 37, 47, 49, 60, 62, 74, 76, 110]) и анализа процессов функционирования СМО с такого рода входящими потоками [30, 31, 48, 53, 63, 64, 84, 89].

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

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

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

— разработать алгоритмы программной реализации оптимальных алгоритмов оценивания;

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

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

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

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

— алгоритмы оценивания состояний и параметров дважды стохастического потока событий;

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

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

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

Работа выполнялась в рамках научно-исследовательской работы Томского государственного университета «Разработка алгоритмов оценки параметров и состояний дважды стохастических потоков заявок, циркулирующих в информационно-вычислительных, локально-вычислительных сетях и коммутационных системах» (код темы по Г’РН’ТИ: 28.17.19.29.19.15) в период с 1996 по 2000 г. г.

Публикации. По материалам данных исследований опубликовано 8 работ:

1. Горцев А. М., Шмырин И. С. Оптимальные оценки состояния марковского потока с переключениями при наличии ошибок в измерении и моментов времени //IV симпозиум «Оптика атмосферы и океана». Тезисы докладов. — Томск, 1997. — С. 168−169.

2. Горцев А. М., Шмырин И. С. Оптимальные оценки состояний МС-потока событий при наличии ошибок в измерениях моментов времени //Международная конференция «Всесибирские чтения по математике и механике: 17−20 июня 1997 г. Тезисы докладов. Т.1. Математика — Томск: Изд-во ТГУ, 1997. — С. 168−169.

3. Горцев А. М., Шмырин И. С. Оптимальный алгоритм оценки состояний МС-потока событий при наличии ошибок в измерениях моментов времени //Оптика атмосферы и океана. — 1998. — N4. — С. 419−429.

4. Горцев A.M., Шмырин И. С. Оптимальная оценка параметров МС-потока событий при наличии ошибок в измерениях моментов наступления событий //Массовое обслуживание: потоки, системы, сети. Сборник материалов 14 Белорусской школы-семинара по теории массового обслуживания. — Минск: Изд-во БГУ, 1998. — С. 17.

5. Горцев А. М., Шмырин И. С. Оптимальная оценка состояний дважды стохастического потока событий при наличии ошибок в измерениях моментов времени //Автоматика и телемеханика. — 1999. — N1. — С. 52−66.

6. Горцев А. М.} Шмырин И. С. Оптимальная оценка параметров дважды стохастического пуассоновского потока событий при наличии ошибок в измерениях моментов наступления событий //Известия вузов. Физика. — 1999. — N4. — С. 19−27.

7. Шмырин И. С. Оптимальная оценка параметров потока событий с переключениями //Вестник ТГУ. — 2000.— N271. — С.63−66.

8. Шмырин И. С. Оптимальная оценка параметров потока событий с переключениями //Массовое обслуживание. Потоки системы, се.

12 ти: Материалы международной конференции «Современные математические методы исследования информационно-вычислительных сетей», 23−25 января 2001 г., Минск. Выпуск 16. — Минск: Изд-во Б ГУ, 2001. — С. 194 — 199.

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

— на IV симпозиуме «Оптика атмосферы и океана» Института оптики атмосферы и океана Российской Академии Наук (Томск, 1997);

— на международной конференции «Всесибирские чтения по математике и механике при Томском государственном университете (Томск, 1720 июня 1997 г.);

— на 14-ой Белорусской школе-семинаре по теории массового обслуживания (Минск, 1998 г.);

— на Международной конференции «Современные математические методы исследования информационно-вычислительных сетей» (Минск, 2325 января 2001 г.).

Результаты работы отражены в 8 публикациях, одна из которых опубликована в журнале Российской Академии Наук «Автоматика и телемеханика» .

Заключение

.

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

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

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

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

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

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

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

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

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

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