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

На правах рукописи

ВАСИЛЬЕВА ЛАРИСА АНАТОЛЬЕВНА

ОЦЕНИВАНИЕ ДЛИТЕЛЬНОСТИ МЕРТВОГО ВРЕМЕНИ И ПАРАМЕТРОВ АСИНХРОННОГО ДВАЖДЫ СТОХАСТИЧЕСКОГО ПОТОКА СОБЫТИЙ МЕТОДОМ МОМЕНТОВ

05.13.01-Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Томск - 2005

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

Научный руководитель:

доктор технических наук, профессор

Горцев Александр Михайлович

Официальные оппоненты:

доктор физико-математических наук,

профессор

Терпугов Александр Федорович

кандидат физико-математических наук,

доцент

Буркатовская Юлия Борисовна

Ведущая организация:

Московский государственный институт электроники и математики (технический университет) (г. Москва)

Защита состоится:

07 апреля 2005 г. в 10.30 на заседании диссертационного совета Д 212.267.12 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина, 36.

С диссертацией можно ознакомиться:

В научной библиотеке Томского государственного университета.

Автореферат разослан:

февраля 2005 г.

Ученый секретарь диссертационного совета, д.т.н., профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

относятся потоки с интенсивностью, являющейся непрерывным случайным процессом. Ко второму классу можно отнести потоки, у которых интенсивность есть кусочно-постоянный случайный процесс с конечным числом состояний. Такие потоки (потоки с переключениями, МС-потоки событий) являются наиболее характерными для реальных телекоммуникационных сетей, вычислительных сетей и систем. В свою очередь, в зависимости от того каким образом происходит переход из состояния в состояние МС-потоки можно разделить на 3 класса: 1) синхронные дважды стохастические потоки событий - потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени, являющиеся моментами наступления событий; 2) асинхронные дважды стохастические потоки событий - потоки с интенсивностью, для которой переход из состояния в состояние не зависит от моментов наступления событий; 3) полусинхронные дважды стохастические потоки событий - потоки, у которых для одного множества состояний справедливо 1, а для остальных состояний справедливо 2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-на юбилейной конференции СФТИ при Томском госуниверситете, посвященной 70-летию образования института (Томск, 29 сентября - 2 октября 1998г.);

-на IV Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" и Сибирской научной школе-семинаре "Проблемы компьютерной безопасности" (Томск, ТГУ, 10-13 сентября 2002г.).

-на Всероссийской научно-практической конференции "Новые технологии и комплексные решения: наука, образование, производство" (Анжеро-Судженск, 18-19 октября 2001г.)

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

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

Структура и объем диссертации. Диссертация состоит из введения, 3-х глав, заключения, приложения, списка использованной литературы. Работа содержит 147 страниц машинописного текста, 13 рисунков, 20 таблиц. Список литературы включает 119 наименований.

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

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

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

(первое состояние) и (второе состояние) (Х,>Х.2). Длительности

пребывания процесса в том или ином состоянии распределены по экспоненциальному закону /-;(г)=1-ехр{-а,г}, 1=1,2, где «ц- интенсивность смены первого состояния процесса на второе, а2- наоборот. На участках стационарности (когда , либо имеет место пуассоновский

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

! :I П

х, !-1 !-! ь

Проиесс Я(/)

тп ! П '

Асинхронный дважды стохастический поток событий

1 ¿1 »

т т т 1 т т

Схема создания мертвого времени

А 1

1г 1> Ь •>

Наблюдаемый поток событий Рис 1

По наблюдениям на конечном интервале времени требуется

построить оценки параметров случайного процесса и

длительности мертвого времени Т, а также исследовать их свойства.

Рассматривается установившийся режим функционирования потока событий. Осуществляется переход от моментов наступления событий

к длительностям интервалов ' = 1,2,____ Тогда основой для

исследования является плотность распределения вероятностей случайной величины - интервала времени между соседними событиями в наблюдаемом потоке. Изложим кратко вывод формулы для /?(т).

Пусть регистрируется событие в наблюдаемом потоке. Припишем этому событию, момент времени ¿=0. Обозначим ч е до^Д) - условную

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

наступило. Тогда для введенных вероятностей (у =1,2) имеет место

7с1/(г,г)=-а1л1(г,г)+а2л2(?,г), я2/(г,г)=а1л|(/,г)-а,т12(/,г)

Для определения констант А\{Г), А2(т) в (1), найдем яДо,Т) - условную вероятность того, что процесс в момент времени находится в

состоянии при условии, что в этот момент времени событие

наступило и наступило мертвое время длительности Т. Обозначим . Введем в рассмотрение переходные вероятности -

вероятность того, что за время, которое пройдет от момента до

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

следующего события в наблюдаемом потоке), /,_/=1,2. Тогда, так как моменты времени образуют вложенную цепь Маркова, справедливы уравнения для финальных вероятностей

+ > ^2(г) = 1. (2)

Обозначим - вероятность того, что за мертвое время длительности Г

процесс перейдет из состояния (момент в состояние (момент

Пусть . Тогда для введенных вероятностей имеют

место следующие формулы:

где - финальные вероятности состояний процесса

я, =а2/(а( +а2), п2 =а1/(а| +а2)

Припишем моменту окончания мертвого времени момент . Тогда на полуинтервале где - достаточно малый интервал времени, с

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

Пусть - вероятность того, что на интервале нет событий

наблюдаемого потока и в момент времени имеет место при

условии, что в момент времени имеет место . Тогда совместная

вероятность наступления события на полуинтервале и перехода

процесса Х(/) из состояния «в состояние _/запишется в виде />у(т)Х;Дт + о(Дт). Соответствующая плотность вероятностей есть . Так как

произвольный момент времени, то вероятность перехода процесса из

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

запишется в виде

Рг, = ' (0=1,2).

(4)

о о

Находя явный вид вероятностей рДт) и подставив их в (4), получаем выражения для :

Л1--I Р\1--- » Р1\--> РТ2-- >

(5)

где

г1,2 = ^ + + а1+ а2)+ ~ + а1 ~ а2? + 4а,а2 ^ О

< г, < г-> ,

В силу марковости процесса Х.(/) выписываем выражения для переходных вероятностей в виде где

определены формулами (3), в которых рг] определены в (5).

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

Тем самым находим

Рассмотрим временной интервал длительности х = Т + 1, состоящий из двух смежных интервалов: первый длительности Т, второй - длительности /.

Началом первого интервала является момент наступления события в наблюдаемом потоке, началом второго интервала - момент окончания мертвого времени. Обозначим - вероятность того, что в момент времени / процесс будет находиться в г-М состоянии (/=1,2) и на интервале (о,() событий наблюдаемого потока не произойдет. Тогда р({) - плотность вероятностей длительности интервала между моментами окончания мертвого времени и следующим событием наблюдаемого потока, запишется в виде

Р&ЬМЙ+МДО- (8)

Выпишем систему уравнений для определения вероятностей /*](/), /2(О-

^('Ь-^ + аМО+аг^). Я2'(0 = «,/}(')-+«2)/>2(г) , (9)

с граничными условиями где вероятности

яДг=Г,Г) определены выражением (7) для 1=Т, Р,{о) - вероятность того, что процесс в момент времени находится в состоянии Решая систему уравнений (9), находим

(10)

Подставляя (10) в (8), и учитывая при этом, что х = Т + 1 , находим явный вид плотности вероятностей:

2), определены в (5).

Вид плотности вероятностей (11) позволяет сделать вывод о том, что принципиально возможна оценка параметров распределения у, Т. Это

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

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

Оценки находятся путем решения уравнений моментов:

(12)

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

Решая систему уравнений (13), находим:

- оценка длительности мертвого времени является корнем

алгебраического уравнения шестой степени

Л/{т*}=<:*, к = 1,4

Т6 -6С{Г5 + 3 (бС{ - С2)г4 + 4(с3 - 6С,3)г3 + 3 (с4 -8С,С3 +12С,2С2)г2 + + 6 (4С,2С3 -С1С4 + 2С2С3 - бС^Г+(4С32 + 6С,2С4 - 24С,С2С3 - ЗС2С4 +18С,3) = О,

что приводит к неоднозначности в выборе Т; - оценки и ¿2 являются корнями квадратного уравнения

(г4 - 4С,Г3 + 6С|2Г2 - 6С,С,Г + 2СуТ - 2С,С3 +ЗС|) + + 2(27^ -- 6С,Г2 + 6С,2 Г+С3 - ЗС,С2 ) г + б(г2 - 2С,Г - С, +2С2)=0 ; - оценка у определяется из соотношения у = --~г

22 — I ¿2

Оценки параметров ^,Д2,а|, определяются через как решение

системы уравнений:

Далее рассматривается ситуация, когда мертвое время случайная величина. По-прежнему считается, что события, наступившие в течение мертвого времени, не вызывают продления его периода и недоступны наблюдению. По окончании мертвого времени первое наступившее событие снова создает период мертвого времени длительности Г, , где Т, - реализация случайной величины (длительности мертвого времени) с плотностью распределения вероятностей р(Т) и т.д. Вариант возникающей ситуации показан на рис.2. По наблюдениям {г,, /2,...,(„} на конечном интервале времени необходимо построить оценки (в момент окончания наблюдений) параметров случайного процесса и параметров

распределения р(Т)

-[()-! +Х2+ 2а)- 1{(1,-Х2У +402)] = г,, +>.,+ 2а)+ -¿(¡X, - Х2У + 4а2^

х ! | !

Процесс и о

'П Дважды сто ,11, ■■ хастическ нй поток событий

т, Т1 Схема со Т» здания ме| - т* 1твого времени т,

и I, и ь

Наблюдаемый поток событий Рис 2

Плотность распределения вероятностей интервала времени между соседними событиями в наблюдаемом потоке р(т) = р{х/Т), в случае когда период мертвого времени имеет фиксированную длительность Т выписана в (11). Тогда

р(т)=1^/г)Я(г>/7\ (14)

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

распределения. Подставляя (11) в (14), получаем

р( т) = Цг^ ]у{ТУ№-:,)т<ЛГ+¡гЮе'^^Т (15)

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

затруднительным.

Далее рассматриваются частные случаи асинхронного потока событий. Для альтернирующего потока событий, когда )Ч=Х, Х2=0, методом

моментов строятся оценки неизвестных параметров В

результате достаточно трудоемких вычислений получаем систему уравнений для определения оценок параметров (3, ^, г2 , а (где а = СЦ + а2 ).

-|(г2 - Р)(а + 2р)+р2 - С2 +г2) + С,)+(г2 ^ Р)(г2^-а - Р)(С27, -С,) ,

Решение данной системы возможно только численно. Оценки ,

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

В случае, когда параметры асинхронного потока событий описаны как

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

2(3а + IX) - ЗХаС, = 0,4(л? -12а3 + ЗХа2 + 2Хга)+ Х2а(3а - 2Х)(С2а - С,) = 0 .

Очевидно, что решение систем возможно только численно.

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

Рассматривается асинхронный поток событий (определен в первой главе) в

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

По наблюдениям на конечном интервале времени требуется

построить оценки параметров случайного процесса и

длительности мертвого времени Т, а также исследовать их свойства.

Основой для исследования является преобразование Лапласа gt(s) плотности вероятностей временного интервала между соседними

событиями наблюдаемого потока. Изложим кратко вывод формулы для Обозначим общую длительность периода ненаблюдаемости через Наблюдаемое событие создало период ненаблюдаемости длительности Т. Тогда \ = Т , если в течение этого времени события исходного асинхронного потока не наступят. При этом вероятность того, что на интервале (0,7) событий исходного потока не наступит при условии, что в начальный момент

времени событие наступило, равна где - определена в

(11) для Т=0. Однократное продление периода ненаблюдаемости на какое-то время будет в том случае, если в некоторый момент времени

наступит событие в исходном асинхронном потоке, а затем после момента х1 на интервале длиной Т событий больше не наступит. Вероятность описанной ситуации равна р^х^ск^^Т) , при этом ^ = (Т<^<2Т). Аналогично

рассматривается двукратное, трехкратное и т.д. продление мертвого времени. Объединяя все эти случаи, плотность распределения вероятностей р{Е,) можно записать в виде

Р& = - Г)+Фо (А; - X, - Т)р{х{ У*, +

где р(х) определена в (11) дляТ=0, 8(-) - дельта-функция.

Переходя к преобразованию Лапласа функции р(!;), в результате

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

(16)

где <р0(Г) = ')'ехр{-г1Г} + (1-у)ехр{-727'}, у определена в (11) для Т=0.

Рассмотрим теперь интервал времени между событиями в наблюдаемом

потоке, он равен т = \ +ц. Тогда по формуле свертки р(х) = J р(£)р(х - \ | QcK,

Выражение для р(t-i;|i;) находим по той же методике, что и р(т) для случая непродлевающегося мертвого времени, описанной на стр.9-12 автореферата. В результате выражение для p(i-£,находится в виде

Преобразование Лапласа плотности р(т)= \ с учетом (16),

запишется в виде

, г2 определены в (5), у определена в (11) для Т=0.

Как отмечалось в первой главе, даже в случае непродлевающегося мертвого времени принципиально возможна оценка только четырех параметров из пяти X), , щ, О;, Г. В случае продлевающегося мертвого

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

(-1)*м(т4), кг1\,2>.... Для оценки четырех неизвестных параметров имеем уравнения моментов:

Если имеется априорная информация о параметрах исходного асинхронного потока событий, то для оценки длительности мертвого времени Т достаточно одного уравнения моментов Рассматривается частный случай

исходного асинхронного потока, когда Тогда первое уравнение

моментов (к=1) примет вид:

где г2 определены в (5), у определена в (11). Уравнения моментов можно решить только численно.

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

Статистический эксперимент по оценке параметров асинхронного потока событий в схеме с непродлевающимся и продлевающимся мертвым временем заключается в построении доверительных интервалов для математических ожиданий оценок параметров {х^^с^г}. Результаты экспериментов приведены в таблицах и графиках. В качестве иллюстрации на рис.4 приведены графики для случая непродлевающегося мертвого времени для набора параметров {Т = 0.05, = 10.0, Х2 = 0.2, а = 0.5} . На рис.5 в качестве иллюстрации приведены графики для случая продлевающегося мертвого времени для набора параметров {7" = 1.0Д1 = 10.0, Х2 =2.0, а = 0.5} ; на рис.6 -для набора параметров . На графиках

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

оценок параметров - время моделирования.

Анализируя численные результаты, представленные в диссертации, можно сделать следующие выводы:

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

является естественным, и можно сказать, что стационарный режим устанавливается при Гт0(1 > 1400 ед. времени.

Рис 6

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

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

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

- получен явный вид плотности распределения вероятностей интервала между соседними событиями наблюдаемого потока в схеме с непродлевающимся мертвым временем;

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

- получен явный вид преобразования Лапласа плотности распределения вероятностей интервала между соседними событиями наблюдаемого потока в схеме с продлевающимся мертвым временем;

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

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

Список публикаций по теме диссертации

1. Васильева Л.А. Оценивание параметров дважды стохастического потока событий в условиях присутствия мертвого времени // Вестник Томского государственного университета. Приложение. - 2002.—№1(1). - С. 9-13.

2. Васильева Л.А., Горцев A.M. Оценивание параметров МС-потока при условии его частичной наблюдаемости//Математическое моделирование. Кибернетика. Информатика. - Томск: ТГУ, 1999.- С.34-41.

3. Васильева Л. А., Горцев A.M. Оценивание параметров дважды стохастического потока событий в условиях его неполной наблюдаемости//Материалы Всероссийской научно-практической конференции "Новые технологии и комплексные решения: наука, образование, производство". Часть II (математика). - Кемерово: Изд-во Кемеровского университета, 2001.- С. 14-16.

4. Васильева Л.А. Оценивание параметров МС-потока событий при условии его частичной ненаблюдаемости //Сборник материалов конференции СФТИ при Томском госуниверситете, посвященной 70-летию образования института: 29сентября-2 октября 1998г. Тезисы докладов.-Томск: Изд-во СФТИ, 1998.-С. 46-47.

5. Васильева Л.А., Горцев A.M. Оценивание параметров дважды стохастического потока событий в условиях его неполной наблюдаемости //Автоматика и телемеханика. - 2002. - №3. - С.179-184.

6. Васильева Л.А., Горцев A.M. Оценивание длительности мертвого времени асинхронного дважды стохастического потока событий в условиях его неполной наблюдаемости //Автоматика и телемеханика. -2003.-№12.-С.69-79.

Подписано к печати 08.02.2004. Формат 60x84/16. Бумага "Классика". Печать RISO. Усл. печ. л. 1,34. Уч.-изд. л. 1,21. Заказ 127. Тираж 110 экз.

ИШТЕЛЬСТВО^ТПУ. 634050, г. Томск, пр. Ленина, 30.

0f.M-OS-.S3

f-

V)

í j

2 2 АПР 2005

1147

Введение.

1. Оценивание длительности мертвого времени и параметров асинхронного дважды стохастического потока событий в схеме с непродлевающимся мертвым временем.

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

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

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

1.4. Свойства оценок.

1.4.1. Состоятельность оценок.

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

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

1.6. Выводы к главе 1.

2. Оценивание длительности мертвого времени и параметров асинхронного дважды стохастического потока событий в схеме с продлевающимся мертвым временем.

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

2.2. Преобразование Лапласа плотности распределения вероятностей интервала времени между соседними событиями наблюдаемого потока.

2.3. Оценивание длительности мертвого времени и параметров асинхронного потока событий методом моментов.

2.4. Выводы к главе 2.

3. Имитационное моделирование асинхронного дважды стохастического потока событий при условии его частичной наблюдаемости. Статистические эксперименты. Численные результаты.

3.1. Имитационное моделирование асинхронного дважды стохастического потока событий в схеме с непродлевающимся мертвым временем. Статистические эксперименты.

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

3.1.2. Численные результаты.

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

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

3.2. Имитационное моделирование асинхронного альтернирующего дважды стохастического потока событий в схеме с непродлевающимся мертвым временем. Мертвое время -случайная величина. Статистические эксперименты.

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

3.2.2. Численные результаты.

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

3.3. Имитационное моделирование асинхронного дважды стохастического потока событий в схеме с продлевающимся мертвым временем. Статистические эксперименты.

3.3.1. Алгоритм построения доверительных интервалов для математического ожидания оценки периода мертвого времени.

3.3.2. Численные результаты. Доверительные интервалы для математического ожидания оценки периода мертвого времени.

3.4. Выводы к главе 3.

Актуальность работы

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

Основоположником теории массового обслуживания считается известный датский ученый А.К. Эрланг. Являясь сотрудником Копенгагенской телефонной компании, он опубликовал в 1909 г. работу "Теория вероятностей и телефонные переговоры", в которой решил ряд задач по теории систем массового обслуживания с отказами. Значительный вклад в создании и разработку общей теории массового обслуживания внес выдающийся математик А .Я. Хинчин, им и был предложен термин теория массового обслуживания. В зарубежной литературе чаще используется название теория очередей. Основы математической теории массового обслуживания заложены в монографиях и учебных руководствах А.Я. Хинчина [93], Б.В. Гнеденко, И.Н. Коваленко [24], Г.П. Климова [52], Т.Л. Саати [83], Бодино А., Брамбилла [97], А. Кофмана, Р. Крюона [59], Д. Риордана [79], Р. Сиски [115], Л. Клейнрока [51]. Дальнейшее развитие теории массового обслуживания связано с изучением различного рода приоритетных систем, которым посвящены монографии Б.В. Гнеденко, Э.А. Даниэляна, Б.Н. Димитрова, Г.П. Климова, В.Ф. Матвеева [26], О.И. Бронштейна, И.М. Духовного [15], В.В. Мовы, Л.А. Пономаренко, А. М. Калиновского [64], Г.П. Климова, Г.К. Мишкоя [53], М.И. Волковинского, А.Н. Кабалевского [20], Н. Джейсуола [39]. Методы теории массового обслуживания в достаточно сжатой форме изложены в монографии Д. Кенига, Д. Штояна [50]. Основные элементы тенденций развития теории массового обслуживания даны в работе Г.И. Ивченко, В.А. Каштанова, И.Н. Коваленко [46]. Обширная библиография по различным аспектам теории массового обслуживания и ее приложениям, а также направлениям исследований приведены в целом ряде обзорных статей (В.В. Рыков [81], Б.В. Гнеденко, И.Н. Коваленко [25], И.Н. Коваленко [54, 55], Ю.К. Беляев, Б.В. Гнеденко, И.А. Ушаков [12], Ю. Бхат [18], Д. Кениг, В.В. Рыков, Ф. Шмидт [49], М.А. Файнберг, Е.А. Файнберг [90]).

Одним из важных направлений в теории массового обслуживания и ее приложениях, является направление, связанное с управляемыми системами массового обслуживания (СМО). Первые работы по управляемым СМО появились в середине шестидесятых годов [16, 17, 19, 21, 80, 82, 100, 108, 118, 119]. Затем последовали многочисленные публикации, связанные с различными оптимизационными постановками задач [38, 40, 45, 65, 66, 67, 77, 85, 89, 109, 113, 114, 117]. В публикациях [32, 67, 81, 90] имеются достаточно полные обзоры работ по управляемым СМО.

Расширение поля приложений неизбежно привело к увеличению числа исследователей и к расширению того круга изданий, в которых появляются работы по теории массового обслуживания. Однако, несмотря на большое количество работ, остается еще много проблем, требующих дополнительного исследования. В частности, анализ литературных источников приводит к выводу, что в литературе по теории массового обслуживания и ее приложениям совсем незначительное количество работ посвящено адаптивным системам, т.е. системам, функционирующим в условиях полной или частичной неопределенности. Наряду с тем, что подавляющее число авторов рассматривает ситуации, когда все параметры, характеризующие СМО, точно известны, в реальности дело обстоит, как правило, иначе. Если в отношении параметров, характеризующих обслуживающие устройства, можно сказать, что они известны и с течением времени не меняются, то в отношении интенсивностей входящих потоков или других их параметров этого сказать во многих случаях нельзя. Интенсивность входящих потоков обычно меняется со временем, часто эти изменения носят случайный характер; последнее приводит к рассмотрению дважды стохастических потоков событий [102]. С другой стороны, очевидно, что функционирование СМО непосредственно зависит от интенсивностей входящих потоков заявок: чем больше интенсивности входящих потоков, тем напряженнее режим обслуживания, требующий, например, подключения дополнительных обслуживающих приборов. Вследствие этого важной задачей является задача оценки в произвольный момент времени параметров потока событий по наблюдениям за этим потоком.

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

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

Потоки событий с интенсивностью, зависящей от времени и являющейся случайным процессом, можно разделить на два класса. К первому классу относятся потоки с интенсивностью Х(г), являющейся непрерывным случайным процессом. Примером исследований задач, связанных с оценкой интенсивности такого рода потоков, являются работы [22, 23, 78]. Ко второму классу можно отнести потоки, для которых интенсивность есть кусочно-постоянный процесс с конечным числом состояний (х.,Д2,.Д„). Переход процесса из состояния в состояние происходит в случайные моменты времени, при этом на интервалах времени, когда процесс А,(/) находится в состоянии поток событий ведет себя как стационарный пуассоновский поток интенсивности А,. Такие потоки являются наиболее характерными для реальных вычислительных сетей и систем. По-видимому, впервые потоки второго типа применительно к системам массового обслуживания были рассмотрены в работах М. Ньютса [106] и Г.П. Башарина [8, 9]. В последней работе был рассмотрен поток событий, для которого переход из состояния в состояние управлялся марковской цепью (отсюда название "МС (Markov chain)-n0t0kh событий"). Развитие исследований СМО с кусочно-стационарными марковскими потоками событий (публикации [68, 41, 42, 98, 103, 104, 105, 107]) привели к созданию модели ВМАР (Batch Markovian Arrival Process) - потоков. Монография А.Н. Дудина и В.И. Клименок [43] посвящена исследованию различных систем массового обслуживания с входящими ВМАР-потоками. В целом такого рода кусочно-стационарные потоки событий могут быть разделены на 3 класса:

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

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

3) полусинхронные дважды стохастические потоки событий — потоки, в которых для одного множества состояний справедливо 1, а для остальных состояний справедливо 2.

В научной литературе описанные потоки исследуются с двух точек зрения: построения оценок состояний (задачи фильтрации) и параметров ненаблюдаемой интенсивности потока (задачи оценивания) (работы [11, 22, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 47, 56, 58, 69, 87, 94, 116]) и анализа процессов функционирования СМО с такого рода входящими потоками [40,41,57, 63,74, 75, 96, 101].

В данной работе рассматривается задача оценивания параметров асинхронного МС-потока событий с интенсивностью х((), являющейся кусочно-постоянным марковским процессом, принимающим два значения (А., Д2) события которого частично наблюдаемы. Частичная наблюдаемость связана с возникновением, так называемой, схемы мертвого времени, когда после наступления события в асинхронном потоке наступает некоторое время фиксированной длительности (период мертвого времени), в течение которого другие события недоступны наблюдению. Одним из основных искажающих факторов при определении характеристик случайных потоков выступает мертвое время устройств регистрации [7, 61, 62]. В течение мертвого времени обрабатывается зарегистрированное событие, а любое другое событие, поступившее на вход системы в этот период теряется. По этой причине счетчик событий показывает, как правило, не истинную картину, а несколько искаженный ход явлений. В связи с этим возникает задача оценивания параметров (характеристик) истинного потока событий, поступающего на вход системы. В конкретных устройствах величина и характер мертвого времени зависят от многих факторов. В первом приближении можно считать, что этот период продолжается некоторое определенное (фиксированное) время Г. Все устройства регистрации с достаточной степенью приближения можно разделить на две группы. Первую группу составляют устройства с непродлевающимся мертвым временем, которое не зависит от поступления других событий в пределах его действия. Непродлевающееся мертвое время иногда называют мертвым временем первого рода, а соответствующие устройства регистрации - счетчиками или регистраторами типа I. Ко второй группе относятся устройства с продлевающимся мертвым временем (регистраторы II типа). В этом случае мертвое время возникает после любого события, поступившего на вход системы, вне зависимости, от факта его регистрации. В первой главе диссертации решается задача оценивания параметров асинхронного потока событий и длительности мертвого времени в схеме с непродлевающимся мертвым временем методом моментов, во второй главе решается аналогичная задача, но в схеме с продлевающимся мертвым временем, в третьей главе представлены алгоритмы статистических экспериментов и численные результаты.

Подобные задачи решены для простейшего потока событий при наличии непродлевающегося мертвого времени [28] методом максимального правдоподобия, для простейшего потока событий в схеме с продлевающимся мертвым временем - методом моментов [30]. Для альтернирующего дважды стохастического потока событий эти задачи решены в [35, 36, 44, 71, 72, 73].

Остановимся теперь на методе моментов, с помощью которого и предлагается находить оценки для параметров распределения по выборочным значениям в данной работе. Считается, что метод моментов, введенный К. Пирсоном ([110, 111, 112]), является самым первым общим методом оценивания неизвестных параметров по выборочным значениям. Этот метод заключается в приравнивании определенного количества выборочных моментов к соответствующим моментам распределения, являющимися функциями от неизвестных параметров. Рассматривая количество моментов, равное числу подлежащих оценке параметров, и решая полученные уравнения относительно этих параметров, получаем искомые оценки. Известно, что оценки, получаемые таким способом, не являются "наилучшими" из возможных (имеют не наименьшую возможную дисперсию ) [48, 60] (свойства оценок метода моментов обсуждаются в параграфе 4 главы 1 ) . Тем не менее, метод моментов часто очень удобен для практических целей.

Цель работы.

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

Методы исследования.

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

Научная новизна. Результаты, выносимые на защиту.

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

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

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

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

Теоретическая ценность.

Теоретическая ценность заключается в том, что в работе:

1) получен вид плотности распределения временного интервала между соседними событиями для асинхронного дважды стохастического потока событий в схеме с непродлевающимся мертвым временем;

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

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

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

Практическая ценность.

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

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

Публикации.

По материалам данных исследований опубликовано 6 работ: 1. Васильева Л.А. Оценивание параметров дважды стохастического потока событий в условиях присутствия мертвого времени // Вестник Томского государственного университета. Материалы научных конференций, симпозиумов, школ, проводимых в ТГУ.- Томск: ТГУ, 2002.-№1. - С. 9-13.

2. Васильева JI.A., Горцев A.M. Оценивание параметров МС-потока при условии его частичной наблюдаемости//Математическое моделирование. Кибернетика. Информатика. — Томск: ТГУ, 1999.- С.34-41.

3. Васильева JI.A., Горцев A.M. Оценивание параметров дважды стохастического потока событий в условиях его неполной наблюдаемости//Материалы Всероссийской научно-практической конференции "Новые технологии и комплексные решения: наука, образование, производство". Часть II (математика). — Кемерово: изд-во Кемеровского университета, 2001.- С. 14-16.

4. Васшьева JI.A. Оценивание параметров МС-потока событий при условии его частичной ненаблюдаемости // Сборник материалов конференции СФТИ при Томском госуниверситете, посвященной 70-летию образования института: 29сентября-2 октября 1998г. Тезисы докладов. - Томск: Изд-во СФТИ, 1998.-С. 46-47.

5. Васильева JI.A., Горцев A.M. Оценивание параметров дважды стохастического потока событий в условиях его неполной наблюдаемости // Автоматика и телемеханика. - 2002. — №3. — С.179-184.

6. Васильева JI.A., Горцев A.M. Оценивание длительности мертвого времени асинхронного дважды стохастического потока событий в условиях его неполной наблюдаемости // Автоматика и телемеханика. -2003. - № 12. - С.69-79.

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

-на юбилейной конференции СФТИ при Томском госуниверситете, посвященной 70-летию образования института (Томск, 29 сентября - 2 октября 1998г.);

-на IV Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" и Сибирской научной школы-семинара "Проблемы компьютерной безопасности" (Томск, ТГУ, 10-13 сентября 2002г.).

-на Всероссийской научно-практической конференции "Новые технологии и комплексные решения: наука, образование, производство" (Анжеро-Судженск, 18-19 октября 2001г.)

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

Результаты работы отражены в 6 публикациях.

ЗАКЛЮЧЕНИЕ

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

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

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

- получен вид плотности распределения вероятностей интервала между соседними событиями наблюдаемого потока в схеме с непродлевающимся мертвым временем;

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

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

- получен вид преобразования Лапласа плотности распределения вероятностей интервала между соседними событиями наблюдаемого потока в схеме с продлевающимся мертвым временем;

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

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