Введение к работе
Актуальность проблемы. Развитие теории массового обслуживания определялось (и определяется) исследованием систем связи, ., транспортных систем, систем управления запасами и других систем. В последние два десятилетия появилась ещё одна ваяная сфера приложений теории массового обслуживания - проектирование и создание вычислительных систем, объединяющих в себе две и более ЭВМ, а также сетей связи ЗКА. В этой связи различным аспектам математической теории массового обслуживания и её приложениям посвящена обдирная литература как отечественных, так и зарубежных авторов. В последние годы особенно много публикаций появилось по проблемшл построения и исследования математических моделей сетей связи, вычислительных систем и сетей ЗВМ. Отметим, что подавляющее количество ра-5ог в теории массового обслуживания и её приложениях посвящено анализу стационарных режимов функционирования систем массового об-злуживания (СМО). Только.в последнее десятилетие начали интенсивно рассматриваться нестационарные режимы функционирования СНО и сетей массового обслуживания, что наиболее полно соответствует усло-зиям работы ре&чьшх систем. В реальных ситуациях параметры, характеризующие СМО, как правило, точно неизвестны. Если относитель-їо интенсивностей обслуживающих устройств мояшо сказать, что они ізвєстіш и со временем не меняются, то относительно интенсивностей '.ходящих потоков заявок этого сказать нельзя. Болев того, неизве-тные параметры потоков, как правило, изменяются во времени, приём характер э.их изменений очень часто носит случайный характер, .апрнмері такие временные изменения-интенсивностей входящих пото-ов заявок характерны для сетей связи ЭВМ, когда степень загружен-ости сети связи определяется временем суток. Вследствие отого, ктуальна проблема исследования функционирования СМО в условиях, огда интенсивности входящих потоков заявок изменяются во времени, ак показывают реальные исследования работы сетей связи ЭВМ, ин-енсивнооти входящих потоков представляют собой скачкообразные /сочно-постоянные случайные процессы. В связи с этим в диссерта--юнной работе рассматриваются вопроси, связанные с исследованием содящих потоков заявок, у которых интенсивность представляет со-эй скачкообразный кусочно- ростояншй_случайный процесс. Подобные іуч'айньїе процесс^аосяг_назваше МС-потоков или потоков с перек-эчег'иями и""рассматриЕались в работах Башарина, Кокотушкина, Hay-'
мова, Sruf.oU't , U^Wb, OcwO» . Однако, ни одна из работ указанных авторов в постановочной части не совпадает с постановкой задачи данной работы, суть которой заключайся в следующем. . Необходимо по наблюдениям за входящим потоком заявок (под наблюдениями понимается количество заявок и моменты их поступления) в течение некоторого временного интервала оценить состояние потока. Самым существенным является то, что моменты наступления заявок ~ наблюдаются с ошибками. Подчеркнём, что автору диссертационной работы неизвестны публикации по теории массового обслуживания.и её приложениям, в которых бы при рассмотрении тех или иных задач моменты поступления заявок наблюдались бы со случайными ошибками.
Подобная задача по оценке состояний входящего потока заявок решалась в диссертации Нехельской Л.А., однако в ней приведены алгоритмы оценивания состояний МС-потока событий, когда моменты наступления событий ошибок не содержат.
Данная диссертационная работа выполнялась в рамках НИР "Математическое моделирование систем обработки информации"(шифр "Модель"}, выполняемой Сибирским физико-техническим институтом при Томском государственном университете в І99І-І993г.г. в соответствии с заказ-нарядом Государственного комитета 1 по высшему образованию на госбюджетную работу, а такке в рамках хоздоговорных НИР "Морслет -АН- ТГУ" и "Сеть-I", выполняемых Томским государственным университетом по Постановлениям правительства'РФ в 1991 -- 1993г.г.
Цель диссертационной работы заключается в :
разработке алгоритма оценки состояний МС-потока событий в условиях, когда измерения моментов наступления событий производятся с ошибками, учитывающий с помощью введения весовой функции старение информации, .
создание программного обеспечения разработанного алгоритма на ЭВМ. ":'
Методы исследования. При выполнении данной работы применялись методы теории вероятностей , теории массового обслуживания, методы оптимизации и численные методы.
Научная новизна диссертационной работы состоит в следующем: разработан алгоритм оценивания состояний МС-потока событий по наблюдениям при наличии ошибок измерений моментов наступления событий с учётом старения информации, при'этом проведена оптимизация параметров алгоритма (вида весовой функции и порога'сравнения) в
сшсле минимума вероятности ошибки принятия решения.
Практическая ценность и внедрение -результатов -работы.
Разработанный алгоритм может быть использован на этапе проектирования вычислительных систем, сетей ЭВМ, а также при оценке состояния технических систем, являющихся источниками заявок. Полученные результаты диссертационной работы внедрены в форме методик расчётов и програю* для ЭВМ в Омском НИИ приборостроения для расчётов оценки состояния информационных потоков и моделирования реальных ситуаций, возникавших н локальных сетях связи.
Публикации. По результатам проводимых исследований опубликовано 7 печатных- работ. Теоретические результаты и результаты практического применения изложены такяе в двух научно-технических отчётах.
Апробация работы. Основные результаты диссертационной работы докладывались на седьмой Белорусской школе-семинаре "Сети связи и сети ЭВМ как модели массового обслуживания" (Гродно, 1991); на Всесоюзной научно-практической конференции "Микросистема-91" (г. Суздаль, 1991): на Всесоюзной научно-технической конференции "Ра--определённые микропроцессорные управляющие системы и локальные вычислительные сети" (Томск, 1991); на восьмой Белорусской школе-семинаре "Сети связи и сети ЭВМ. Анализ и применение" (Брест,1992); на Всесоюзной научно-технической конференции "Микросистема-92" (Калининград, 1992); на Международной научной конференции "Проблемы внедрения и технической эксплуатации тиристорних устройств в судо-зых и береговых установках" (Одесса, 1993).
. Структура и объём работы. Диссертация состоит из введения, срёх глав» заключения, списка литературы и приложения, в котором, з частности, представлены документы, подтверждающие практическое ^пользование-результатов исследований. Работа изложена на 1SQ стра-щцах, включает Юрисунков, і таблицу,список литературы из 93 їаименований. Общий объём диссертации вместе с приложением 180стра-
ІИЦ.
СОдаШАНИЕ РАБОТЫ
Во введении обосновывается актуальность проблемы оценивания остояний МС-потока событий,определены цель и предмет исследования.
В первой главе рассматривается UC-поток событий,-поступающий а вход СМО, интенсивность которого есть кусочно-постоянный стациб-арный случайный процесс ХШ с двумя состояниями Я<и ЛгОЦ:» А г ).
- б -
Будем говорить, что на входе системы массового обслуживания имеет _место первое^остояние природы,если Л(-і)=Лі; наоборот, имеет место второе состояние природы, если А( 4 )=Аг. Длительность пребывания в том или ином состоянии распределена по экспоненциальному закону . і )=l-&xf}.^-t}, і =1,2, где Ui - интенсивность смены первого состояния природы на второе, dz~ интенсивность смены второго состояния природы на первое. На участках стационарности (когда Л ( )= Хі либо Л(-і )= А) имеет место пуассоновский поток событий. Необходимо по наблюдениям за потоком событий (наблюдениями являются моменты наступления событий) оценить его состояние в данный момент времени. Веиду того, что в измерениях моментов наступления событий :. возможны ошибки, то их необходимо учитывать. Вследствие этого моменты наступления событий будем представлять в виде: li = i"+u iit где -ti - наблюдаемые моменты наступления событий,й^і- - ошибки измерений, которые независимы и имеют плотность вероятностей Р(Д^)=Р(д-) для любых I .
Наблюдения за потоком событий производятся непрерывно в интервале времени ( ,? + -,, ), где f - текущее время, І -о - ДЛИТЄт-льность интервала наблюдений J х.д- ie ). Результатом наблюдений яв-,ляется число событий л (- to, "), наступивших за время Ь- to , и моменты наступления событий ii = ii"+ й it. Будем рассматривать процесс {fi( -і -і* , С), j ( - о ,т)} , где J. (і -to , Г) - состояние КС-потока в момент времени t+-t -to , которое и нужно оценить^ (-ho, f)=I,2). Можно показать, что исследуемый процесс in. (i~ier Р ), : j ( і - іо , v ) является стационарным. Тогда при Т-* **> его можно рассматривать как процесс ^(^ - ^),,/ (^ -io )J , вероятностные характеристики которого не зависят.от начала отсчёта о интервала наблюдения, причём "і» -^ іі= ±і + й-іі- -<і для всех і . Финальные вероятности того или иного состояния процесса X (-t) в произвольный
МОМеНТ Времени При ЭТОМ ОПредеЛЯЮТСЯ В ВИДЄ Sii '
События,-наступившие ближе к концу рассматриваемого интервала наблюдений ( io ,i ) несут большую информации о состоянии КС-потока в момент времени' i. . Поэтому алгоритм оценивания долнен учитывать вес любого события, наступившего на интервале наблюдения; при этом вес должен быть тем больше, чем блике момент наступления события к концу интервала наблюдения. Алгоритм вынесения решения будем строить следующим образом.
Будем рассматривать входящий поток событий на временном интервале ( -to.i). Строится сумма *5 = 2р ~Р (^+а^'), где "f (.и + + &Ї) - весовая функция, непрерывная, неубызающая и дифференцируе-
мая на интервале (-la ,"t), ic = ii"+ &il - моменты наступления событий ( io-^lL-tt ). В момент времени t проверяется выполнение неравенств: I) если *f >~W , то принимается решение о том, что оценка Jl ( -fc) = Ді , 2) если ~$ ^ V , то принимается решение о том,. что оценка Л (-t) = Лг , где // - некоторый порог. Смысл этого алгоритма основан на том, что если имеет место первое состояние природы, то количество событий будет в среднем больше (тогда в среднем больше и значение случайной величины 5 ) на интервале наблюдения, чем в случае, если.имеет место второе состояние природы, поэтому вводится порог сравнения t* , относительно которого и принимается то или иное решение о состоянии природы.
Таким образом, для реализации алгоритма оценивания состояний МС-потока событий необходимо определить оптимальный вид весовой функции *f ( ul + а і ) и оптимальное значение порога // в смысле некоторого критерия оптимальности.
Математическое ожидание случайной величины "? при условии,что реализация случайного процесса Л (u-) фиксирована на всём интервале ( 4-, ) определится, с учётом того, что 4<>-д Їі±і-аі\ , в виде
При выводе (I) принято во внимание, что переменные интегрирования
ііі ш-іі" равноправны для всех I = 1,п , поэтому йіі = лі ,
-і = и. Производя далее усреднение (I) по всем реализациям Л (и),
р.е. по всей траектории процесса Л (и.) при условии, что в момент
зремени ^ процесс Я, (и) принимает 'значение ЛИ) =Ai(= 1,2),
іолучим
І'
Ь-At
U-t 4-&i
-tu-t І
Аналогичная формула имеет место для г! л. т ' ЯШ = /їі. Рассмотрим асимптотический случай, когда время функционирования СДО стремится к бесконечности, для этого устремим в (2) і0 к минус бесконечности ( -„-»--<м }. Тогда,производя в (2) замену искомой функции *f ( и. +&±) на Ц* (і -лі - а), делая замену' переменных -t -і.і --U-=X,&i=J к обозначая МС^і ( Ш = *і}*Ліі , находим
Аналогично
-" _
ГДЄ <^ = J.} +Лг, ^-^t%+S^Z-
Второй момент случайной величины 7 при условии фиксированной реализации Л- (и.) определится в виде ' .
+JP(^ v^1 Jp^ W J% **M«Jy»j; .v+*f ? ^^ №>
При Еыводе (5) принято во внимание, что переменные интегрирования л-Ц > л-t; t -ti »-ijb равноправны для всех~ i. = I,n ', j = І,л. , поэтому д&<* Лі', д-fy-*, ді*, -^"-а^^іГ ; . Производі далее усреднение (5) по всоу реализациям Л{и,) при условии, что. в момент времени 4. процесс Л (а ) принимает значение Л W ). = Xi(.l ~ 1,2),-переходя после чего к асимптотическому случаи( -і***'00),.производя при этом аналогичные замены,'что и при выводе (3), (4), и, наконец, учитывая общую формулу для,дисперсии, находим асимптотические условные дисперсии Wl/ЛК ) ~Xi\ = )і. в виде , , .".-.
& -- jp(W ) Ч"(*Э Г5.* Si (*<- Д> Є " ?"***'J W
8і0-ЛЛг-у + *-4/
-см О
и ы*ьш*л*. і ш^і^змг^і-^є^'*"*'"^'*
Во второй главе диссертации делается предположение о том, что ошибка наблюдений является нормальной случайной величиной с нулевым средним и дисперсией "&tt, т,е. p(V ). j ( ^). входящие вфор-мулы (3), .(4), (6), (7), являются нормальньпли плотностями вероятностей, причёь. \ =Х ='0,93^ = ^= "Sz. Далее предполагается, что ошибки наблюдений налы, т.е. Xz^i . Это позволяет сделать разложение интегралов, входящих в (3), (4), (б), (7), по малому параметру г = офг в следующем виде
о о
+ f f^(x)^Me""^'^]+o(e^ (10)
(II)
О о
-Oo -О» О О
«' о
[ffe^(^"'^(St'^^] * OUV. (12)
о о
Подставляя полученные разлокения (8) - (12) по малому параметру СггоСгїг в формулы (3), (4),- (б), (7), находим выражения для условных математических ожиданий и условных дисперсий с точностью до членов ОС 2 ):
Ні = |Y(x) n%+*4*.-^(1+ )е№ -g ^^^W- (із)
о о
о о
CTwe-'^i^fJ^f^-vr^ (іб)
Третья глава диссерта їй посвящена оптимизации порога срав-ения и вида весовой функции. При реализации алгоритма оценивания остпяний МС-потока событий возможны ошибки:. << ( ^.лО =
р ("? ^л// XI і ) = Я*} - вероятность ошибочно принять Д Of )= Аг, огда на самом деле имеет место первое состояние процесса;
j5(^,y) = p {^>^/Л(1 ) = A2j - вероятность ошибочно принять }. ( і ) - Л< , когда на самом деле имеет место второе состояние процесса. Критерий оптимальности выбирается в виде суммарной вероятности ошибки
Pftrf ~ Г, Л{%а1)*^Я^) * (піл / (17)
' о т.е. необходимо определить оптимальный порог /J и оптимальный
вид функции f (а), минимизирующие (17).
Рассматривается асимптотический случай, когда io-» - «> Можно считать, что при этом случайная величина *? является асимптотически нормальной случайной величиной с плотностью вероятностей Pj С ) =^/(/^,) при условии, что в' момент времени t имеет место j -е состояние процесса (j = 1,2); здесь /Wj определяется соответственно формулами (13), (14), $; - формулами (15), (16). Тогда критерий (17) ->рииет вид
п%4'*н^ьщ0-)*>$,. (їв)
где Ф( Ъ) = (І/ІїгїГ) _fe«f> #- интеграл ошибок.
Решая задачу минимизации (18) по л/ при фиксированном V, получаем явное выражение для оптимального порогового значения
ЇЇ* иЪ'Ч-ЪьМ + №<Яг &Нг+гЪ,9г&Єп (Ягіїї/&^Л,/гІ (19)
где /7=л/"'А!іг &М - Mi-fth^ft'tylbJlpK этом можно показать, что
точка Мдействительно является точкой минимума функции.(18), при
чем единственной. -.'
Подставляя (19) в (18), получаем критерий (18) в віще
п*)-**Ш)+*Ч'^)~<р.' ;.';';' (20)
Из (20) следует, что вероятность ошибки РІЧ*) зависит от трёх . функционалов Я< , У)г и 4 М.
Решая вариационную задачу (20), получаем интегральное уравнение для-определения вида весовой функции Ч'і'х) : .
+а» 1Щ)е^т^х'^ -о, ' ; (21>
- ІЗ -
«* = l*/*t) С25Г/К-, (},-** )(7+^1 (<* fU
tf< , fo - неопределённые константы. Взяв сначала первую, затем вторую производные от левой части интегрального уравнения (21), обозначив при этом 4^( а;) -Y^f^Q'^JU/ получаем дифференциальное уравнение для определения весовой функции Y (К):
-і.
Путем преобразований дифференциальное уравнение (22) приводится к однородному дифференциальному гипергеометрическоыу уравнению Гаусса
а (И Vk) + с(1+*+4у -*i %и j* % ~> (23)
где п. < + п+^/^аД"*, У'-гт-^-
jb =і ffzm-O.-tf"77^], i^^tA^^*^4^1^
Решение уравнения (23) получается в виде: I) если '{ Г /а ) > О и о < х< +^ , то
2) если -I <: ( Г/я ) < 0 и о ас^+, то . 3) если (Г /а ) <г -I и сіяг* оа* , ог*= {\U )&Л -), то
)^гргЄ^)+с<е-^)х(-їе"*)^'<г»
4) если (Г/Я) < -I и .ac^ac^ + oo.fa:*= цд/ )&.(_ ), то
Y( х) - с? е-11'^* pf ь^сГ|-^.^ /^-,-^
где Сі ( і = 1,5) - некоторые константы, ' = t-I,
til,/-,*.} ) = i+ Л *= їгг*»*^... [***--<; *
гипергеоыетрический ряд Гаусса, кругом сходимости когорого является единичный круг Jyl = I, ппичём сходимость имеет особенности на окружности круга.
Показывается, что решение существует только для областей -I < (Г/а) * О u ( г/а ) > 0. Тогда,учитывая связь меадуУЧ» ) и искоиой функцией 4у (ж ),- находим решение для Ч? ( ) в виде:
-
если ( Г/а ) > 0 и О (= ог * +<*= , то
-
если -I «= ( Г/а, ) < 0 и о^х^/о , то
--^iilifel р(л+г^ H-^,2+efr-f е-"Я ' (25)
Для определения констант- G. и Сг в (24), (25)- используются условия сшивания решений слева и справа в точке ( Г /о* )=0: if сл.(аг»( Г/о. ) =0) = if'-cn.C ог,( Г/а ) = 0), которое даёт соотнесение для констант А и Сг,: Ci (-у* " ' = Сг.
Второе условие сшивания, а именно: ра жство производных решений слева и справа в точке {Ґ /& ) = 0 ( 4^( ог, (Г/ а) = 0) = = ^,,(05, ( г/а ) =0)), даёт второе условие сшивания, которое, в свою очереди даёт соотношение для. констант Г* и Cz , идентичное предыдущему. Зто говорит о том, что в точке (г/л ) =0 при сшивании решений слева и справа нет излома функции Ц^{х) в точке (Г/а) = 0. Таким образом, в решении (25) (в решении слева) можно положить Cz_-C , тогда в решении (24)(в решении справа) имеем Сі = С(-1Г**^ + 1Р . Наконец, константу С можно взять произвольной, т.к. её значение не влияет Н" результат сравнения величины ^ = V Ц> (: ) с порогом /Ve( если У (*') определяется с точностью до1 константы, то порог У также определяется с точностью до той ке константы). Вследствие этого С выбирается равной I. Тогда, с учётом преобразований гипергеометрических рядов,окончатель-
-16- ,
ный вид радения выгладит следующим образом:
I) если -I ^ ( Г /и ) * 0 и о і х*+о , то
2) если (Г/а) > 0, о^сс^і-со и (4t/^)-I ^0, то
, lU f 'QUwir (l^Yl 1 (27)
me p.-іо-*30л.
3) если (Г/а ) ^ О, о "c't<0 и (4^/«<г)-І > 0, то
'Ги 1іі^«г>\ . (!b-.Yi г (2B,
В качестве иллюстрации на рис.I - ряс.2 пр зецены графики оптимальной весовой функции, вычисленные по формуле (27).. На рис.1 графики вычислены для следующих значений параметров:
Л( = 5, Лч.= I, сЛ - 7, р4 = 5, значение константы Г выбрано равным 0,7666. Переменным параметром является дисперсия ошибки наблюдений тг , принимающая значения 0; 0,001;.0,005; 0,008. На рис.2 зависимости ^ (ее) от д» вычислены для значений параметров Лі = II, Лг= I, J<- б, t/j = 5 и значение константы Г = я 0,6575, переменный параметр "2принимает значения 0; 0,001; 0,003;.0,004» Поведение функции Ч'Х'^) согласуетец с интуитивными представлениями о её поведении.„На рис.3, рис.4 приведены зависимости вероятности ошибки Р(Г) от параметра Г, подсчитанные по формуле .(20),- при этом вид функции ty(,х) даётся выражением (27)., На рис.3 графики Р(Г) вычисляются для ?ч = 5, Яг. = I; <4 = 7,с/г =5, переменным параметром является дисперсия ошибок измерений ~S'Z , принимающая значения , 0; 0,001; 0,005,, 0.00В. На рис. 4 вычисле-. ния вероятности.сшибки Р(Г.) проделаны для значений параметров
Ь' = II, li = I, J, ~ 6, <4= 5, переменным параметром является %г, принимавдая значения.0; 0,001; 0,003; 0,004. Анализ поведения вероятности ошибки Р(Г) приводит к выводу о том, что это поведение совпадает.с интуитивными представлениями. В частности, увеличение дисперсии ' ошибок измерений моментов наступления событий приводит к увеличения вероятности ошибки вынесения резения Р(Г).
Вид оптимальной весовой функции ty.{ х) в формулах (26)-(28) определён с точностью до параметра (^/.. ), так как величина Г, зависящая от 2S\ , вообще говоря, произвольная, Вследствие этого, для того, чтобы решить вопрос об оптимальном значении ( f/o. ) необходимо решить задачу параметрической оптимизации:
f.5
Ц(х)
6Ї&0ОГ
l .№t 0.СОІ2 О.ШІ QM1! в.01Г ЦМШ
Рис. . 1
X
Ц)(х)
if й.цоч ош аж ям а.т о-ом
Рас. 2
J.9
03?
№
0-5S
Р(П
а.$оо о.т шб is?? ws
Рг/а.Ъ Р(Г)
0.571)
3.510
/Ш" —
д.ив
И.і'йі Я73І 0,962 1.193 Рас. 4
pw-fi *ф+**<- ^в "" &л- (2Э)
Задача (29) допускает лишь численное решение. Алгоритм численного решения достаточно прост: I) задаются исходные параметры % , Лг , Ji , <^г , "ez. 2) рассчитываются коэффициенты U, <г ,,?,%., р , р„ и величина {.(ч*/сг)-іЗ , 3) задаётся начальное значение (Г /о. )0 > -I; для (Г/а )0 вычисляется вероятность ошибки РЇ(Г/а )01 с помощью одной из формул (26) - (28) (в зависимости от того каким выбрано начальное приближение (. Г М )0); затем (Г/ft ) увеличивается на л [Г /а. ) и снова вычисляете: вероятность ошибки Р Г( Г/а ),]для ( F/a. )i= ( Г/ч X, +л (^/а ) и т.д.;-вычисления производятся до тех пор, пока
тогда CV« );= ( 0^)^- ' Подчеркнём, что при переходе из области -I <:{!" Ja ) *: 0 в область (Г/а ) > 0 расчётная'формула (26) заменяется либо на формулу (27), либо на формулу (28) в зависимости от знака величины Г(4 t/<^2) -I J .
На рис. 5 приведены результаты работы алгоритма по численному решению задачи параметрической оптимизации вероятности ошибки Р(Г/си) по (Г/а ). Зависимость Р(Г/а ) от (Г/о.) на рис.5 построена для следующих значений параметров "Х<= 5, Аг= I, <Л = 0,05, о/г = 0,04, %z= 0,001. При работе алгоритма в области отрицательных (Г /а ) вероятность ошибки рассчитывалась с использованием формулы (26) для оптимальне! весовой функции"f (а.*)-, в области положительных (Г1 /о,) - с использованием формулы (27). Из анализа графика видк , что существует ярко выраженный минимум вероятности ошибки Р(Г/о.) по (Г/4.), при атом {Т/а. )опг> = -0,153. При отыскании точки минимума шаг по (Г/а) в окрестности точки, подозрительной на экстремум, выбирался равный 0,001. Алгоритм нахождеиия_ оптимального значения (?/&)от реализован на языке РокґМ/^-1У%
В приложении диссертации приведено краткое описание программы,' реализующей алгоритм нахояэдения оптимального (Г/ а.}. Программа вклвчает в себя процедуру вычисления значений оптимальной весовой функции и процедуры вычисления всех интегралов, входящих в выражения (13), (14) для условных математических ожиданий и в выражения (15), (16) для условных дисперсий.
0.07S"
J.W
№0
в№
as -лі о и.ч Ac. 5
a.s
CL
-"22 -
