Asymptotical poisson Markovian arrival processes.pdf В работах по теории массового обслуживания в качестве модели входящего потока часто используется простейший поток [1]. Это касается как фундамен-тальных работ, которые послужили базой построения теории, так и современных. В 1955 году А.Я. Хинчин [2] сформулировал три условия, при выполнении кото-рых случайный поток однородных событий является простейшим. Это условия стационарности, ординарности и отсутствия последействия. С тех пор это являет-ся основным определением простейшего потока.Популярность этого потока долгое время объяснялась тем, что он вполне удовлетворительно описывал многие реальные потоки, а также простотой его ис-следования. В то же время было замечено, что простейший поток появляется и в качестве предельного для некоторых последовательностей потоков. В связи с этим в середине ХХ века появился ряд работ, посвященных анализу сходимости суммы большого числа независимых потоков малой интенсивности к простейше-му потоку. Среди них следует отметить работы Пальма [3], Реньи [4], Г.А. Осо-скова [5], Б.И. Григелиониса [6] и А.Я. Хинчина. Вопрос о скорости сходимости таких предельных сумм к потокам Пуассона рассматривался в работах [7, 8].В то же самое время Реньи (в упомянутой выше работе) показал, что простей-ший поток может получаться не только в результате суммирования бесконечно малых независимых потоков. Он рассматривал произвольный поток восстановле-ния и применял к нему операцию прореживания (с некоторой вероятностью каж-дое событие убиралось из рассматриваемого потока). Реньи доказал, что при мно-гократном повторении этой операции и соответствующей нормировке времени рассматриваемый поток сходится к простейшему.Таким образом, как для теоретических, так и для практических целей пред-ставляет интерес исследование таких моделей, которые приводят к пуассоновским потокам.В частности, в качестве существенного обобщения простейших потоков для более адекватного описания реальных потоков была предложена модель MAP (Markovian Arrival Process). Его понятие впервые было введено М. Ньютсом [9], а затем уточнено Д. Лукантони в работе [10], которая также содержит первые ис-следования основных характеристик MAP-потоков. В русскоязычной литературе определения таких потоков даны в книгах Б.В. Гнеденко, И.Н. Коваленко [1], А.Н. Дудина, В.И. Клименок [11], А.А. Назарова, С.П. Моисеевой [12].1 Работа выполнена при поддержке АВЦП «Развитие научного потенциала высшей школы (2009 -2010 годы)» Федерального агентства по образованию проект № 4761.Асимптотически пуассоновские MAP-потоки73Широко используемым частным случаем MAP-потоков является класс MMP-потоков (Markov Modulated Poisson Process). В данной работе формулируется предельное условие, при выполнении которого последовательность MMP-потоков сходится к простейшему. Аналогичное условие формулируется и для случая общего MAP-потока.1. Исследование MAP-потокаСлучайный поток однородных событий будем определять в виде случайного процесса r(t) - числа событий рассматриваемого потока, наступивших за время t. Пусть эргодическая цепь Маркова k(t) с конечным числом состояний задана матрицей инфинитезимальных характеристик Q с элементами qυk. Также задан набор неотрицательных чисел λ k и вероятности dυk, причем dkk = 0, которые целесообразно определять матрицей D = [dυk] и диагональной матрицей Λ с элементами λ k на главной диагонали.Случайный поток однородных событий будем называть [12] МАР-потоком (Markovian Arrival Process), управляемым эргодической цепью Маркова k(t), если выполняются равенстваP{r(t + At) = r + 1|r(t) = r,k(t) = k} = XkAt + o(At),P{r(t + At)>r + 1|r(t) = r, k(t) = k} = o(At),P {r (t + At) = r +1, k ( t + At) = k|r(t) = r, k(t) = v} = dvkqvkAt + o(At),P{r(t + At) = r,k(t + At) = k|r(t) = r,k(t) = v} = (1 -dvk)qvkAt + o(At).Заметим, что пока управляющая цепь Маркова k(t) находится в некотором состоянии ν, события в МАР-потоке наступают как в простейшем с параметром λν. Кроме событий на интервалах постоянства состояний управляющей цепи могут наступать события при переходах цепи из одного состояния в другое. Если управляющая цепь Маркова переходит из состояния ν в некоторое состояние k, событие в МАР-потоке наступает с вероятностью dνk, а с вероятностью 1 - dνk событие не наступает. В MMP-потоке все dνk = 0, то есть события могут наступать только на интервалах постоянства состояний управляющей цепи k(t). Состояния управляющей цепи Маркова будем называть состояниями рассматриваемого потока.Наиболее полной и удобной для исследования характеристикой марковских потоков (MMP, MAP) является вектор-функция H(u,t), компоненты которой определяются равенствомH(k,u,t) = Y,ejurP(k,r,t),rгде P(k, r, t) - распределение вероятностей значений двумерной цепи Маркова { k ( t), r(t)}.Известно [12], что вектор-функция H(u,t) для MMP-потока является решением задачи КошиdtL ( 1) -1(1)H(0,0) = R,а интенсивность κ рассматриваемого MMP-потока определяется равенствомк = RAE,где R - вектор-строка стационарного распределения вероятностей состояний74А.А. Назаров, И.Л. Лапатинуправляющей цепи Маркова k(t), определяемый системой{RQ = 0, (3){RQ = 0, RE = 1.а E - единичный вектор-столбец.Соответствующая задача для MAP-потока имеет следующий видdH( u , t ) = H(u, t)[Q + (eju-1)B]dtLJ,H(0,0) = Rа интенсивность κ рассматриваемого MAP-потока определяется равенствомк = RBE, где R - вектор-строка стационарного распределения вероятностей состояний управляющей цепи Маркова k(t), определяемый системой (3), E - единичный вектор-столбец, а B - матрица с элементами λ k на главной диагонали и элементами dυk·qυk вне главной диагонали.Мы используем одинаковые обозначения в (1), (2) и (4), (5), так как MMP-поток является частным случаем MAP-потока, а функции H(u,t) и величины κ для них имеют одинаковый смысл.2. Условие предельно частых изменений состояний MMP-потокаБудем рассматривать MMP-поток в условии предельно частых изменений его состояний. Зафиксируем некоторую матрицу инфинитезимальных характеристик Q(1), которая определяет управляющую цепь Маркова k(t), и матрицу Λ. Затем, полагая, что S - некоторая положительная величина, в задаче (1) сделаем следующие замены:Q = S-Q(1), H(u,t) = F(u,t,S).Тогда для вектор-функций F(u,t,S) можно записатьdF(u, t ,S)=SfS .Q(1)+(eju-1)A],dtL-1(6)F(0,0,S)=R.Заметим, что стационарные распределения вероятностей состояний управляющей цепи k(t), заданной матрицами инфинитезимальных характеристик Q(1) и Q=S Q(1), совпадают (не зависят от S), но при увеличении значений параметра S интенсивности перехода цепи Маркова k(t) из одного состояния в другое возрастают, что соответствует условию предельно частых изменений состояния потока.Теорема 1. Сумма компонентов предельного, при S ->■ оо , значения вектор-строки F(u,t) решения F(u,t,S) задачи (6) имеет видF(u,t)E = exp{(eju -1)кt},где E - единичный вектор-столбец, величина κ определяется равенством (2).Доказательство. Поделив левую и правую части уравнения для F(u,t,S) задачи (6) на S и устремив S к бесконечности, получим системуF(u,t )Q(1)=0,которая совпадает по виду с системой (3), поэтому ее решение имеет видАсимптотически пуассоновские MAP-потоки75F(u,t)=R⋅Φ(u,t),где R - вектор стационарного распределения состояний управляющей цепи Маркова k(t), а Φ(u,t ) - некоторая скалярная функция. Для определения вида этой функции умножим справа уравнение для F(u,t,S) задачи (6) на единичный вектор-стобец E соответствующей размерности:∂F(u, t ,S)E = F(u,ju-1)ΛE,∂tvустремим S к бесконечности и подставим разложение (8). Тогда, учитывая (2) и условие нормировки RE=1, функция Φ(u,t) будет удовлетворять дифференциальному уравнению∂Φ( u , t ) = Φ(u,t)(e ju-1)κ ∂tс начальным условием Φ(0,0)=1. Подставляя решение этого уравнения в разложение (8), получимF(u,t) = Rexp{(e ju -1)κ t} .В силу условия нормировки RE=1, функция F(u,t)E удовлетворяет равенству (7). Теорема доказана.Сформулированная теорема говорит о том, что MMP-поток в условии предельно частых изменений состояний управляющей цепи (то есть когда средние времена пребывания управляющей цепи Маркова в каждом состоянии стремятся к нулю) является асимптотически простейшим. При этом равномерный рост интен-сивностей перехода управляющее цепи Маркова k(t) из одного состояния в другое не влияет на стационарное распределение состояний этой цепи и на интенсивность потока.3. Условие предельно частых изменений состояний MAP-потока и согласованного интенсивного прореживанияРассмотрим аналогичную схему для MAP-потока. Так как события в нем могут наступать при переходе управляющей цепи Маркова из одного состояния в другое, то рост интенсивностей перехода повлечет за собой появления большого числа событий в потоке. Чтобы избежать этой ситуации, вероятности dνk наступления событий в MAP-потоке при переходе управляющей цепи Маркова из одного состояния в другое будем уменьшать пропорционально росту интенсивностей перехода qνk.Итак, рассмотрим MAP-поток в условии предельно частых изменений его состояний и согласованного интенсивного прореживания. Зафиксируем некоторую матрицу инфинитезимальных характеристик Q(1), которая определяет управляющую цепь Маркова k(t), матрицу D(1) вероятностей наступления событий в потоке при переходе управляющей цепи из одного состояния в другое и матрицу Λ. Затем, полагая, что S - некоторая положительная величина, в задаче (4) сделаем следующие замены:Q = S⋅Q(1), D = -D(1) , H(u,t) = F(u,t,S).Тогда для вектор-функций F(u,t,S) можно записать76А.А. Назаров, И.Л. ЛапатинdtL( 1) -1(9)Заметим, что стационарные распределения вероятностей состояний управляющей цепи k(t), заданной матрицами инфинитезимальных характеристик Q(1) и Q=S Q(1), совпадают (не зависят от S), а матрица B при сделанных заменах не изменяется.Теорема 2. Сумма компонентов предельного, при S -^ оо , значения вектор-строки F(u,t) решения F(u,t,S) задачи (9) имеет видF(u,t)E = exp{(eju-1)Kt},где E - единичный вектор-столбец, величина κ определяется равенством (5).Доказательство этой теоремы полностью повторяет рассуждения доказательства теоремы 1.Терема 2 говорит о том, что MAP-поток в условии предельно частых изменений его состояний и согласованного интенсивного прореживания является асимптотически простейшим. Здесь под согласованным интенсивным прореживанием понимается, что рост значений инфинитезимальных характеристик и уменьшение вероятностей наступления событий при переходе управляющей цепи из одного состояния в другое происходит пропорционально одному параметру S. При этом сохраняется интенсивность рассматриваемого потока.4. Численный экспериментДля оценки области применимости полученных асимптотических результатов проведем численный эксперимент. Будем рассматривать наши потоки для различных значений параметра S. В работе [13] была получена формула для нахождения распределения вероятностей числа событий, наступивших в MAP (MMP)-потоках за некоторое время t:1 пP ( n,t ) = -\e-jatR( ( B-Q-jaI ) -1B) n( B-Q-jaI ) -1Eda.(11)Таким образом, для того чтобы найти распределение вероятностей P(n,t), достаточно задать матрицу инфинитезимальных характеристик Q, матрицу B и найти вектор-строку стационарного распределения состояний цепи Маркова R и применить формулу (11) для заданного значения времени t и набора значений n=0,1,2…. Здесь I является единичной матрицей соответствующей размерности.Полученное с помощью формулы (11) распределение будем сравнивать с распределением Пуассона, которое соответствует асимптотическому распределению вероятностей числа событий, наступивших в MAP (MMP)-потоках за некоторое время t в условии предельно частых изменений состояний потока. Это поможет показать, при каких значениях параметра S эти распределения достаточно близки, а значит, MAP (MMP)-поток можно аппроксимировать простейшим. Время наблюдения за потоками t будем брать равное 10.Пример 1. Рассмотрим класс MMP-потоков, заданных следующими параметрами:040 0011 0.3 0.73 0 0ЛQ = S-1 -3 2 0.4 1.6 -2Асимптотически пуассоновские MAP-потоки77Интенсивность этих потоков κ равна 2,49, а асимптотическое распределение вероятностей числа событий, наступивших в предельном, при S→∞, потоке за некоторое время t является пуассоновским с параметром κ t.В качестве меры отличия распределений вероятностей предлагается брать расстояние Колмогорова между функциями распределения, которое обозначим за ∆:A = max\F1(i)-F2(i)\,iгде F1(i) и F2(i) - сравниваемые функции распределения.Результаты сравнения (для различных значений параметра S) допредельного распределения вероятностей, полученного с помощью формулы (11), и распределения Пуассона, найденного методом асимптотического анализа, представлены в табл. 1.Таблица 1S0.11101001000∆0.06500.02700.01100.00550.0034Пример 2. Рассмотрим класс MAP-потоков, заданных следующими парамет-рами:'-1 0.3 0.7^ 1 -3 2 v0.4 1.6 -2 у, Л ='3 0 0^ 04 0 10 0 1,S' 0 0.3 0.7" 1 0 0.2 ч0.4 0.6 0 ,Интенсивность этих потоков κ равна 3,468, а асимптотическое распределение ве-роятностей числа событий, наступивших в предельном, при S→∞, потоке за неко-торое время t является пуассоновским с параметром κt.Результаты сравнения (для различных значений параметра S) допредельного распределения вероятностей, полученного с помощью формулы (11), и распреде-ления Пуассона, найденного методом асимптотического анализа, представлены в табл. 2.Таблица 2S0.11101001000∆0.06300.02800.01700.00790.0024Погрешность меньше 0,02 можно считать приемлемой для практики. Заметим, что аналогичные результаты были получены для потоков с другими наборами па-раметров и временем наблюдения.ЗаключениеВ данной работе были рассмотрены условия, при выполнении которых MAP-потоки сходятся к пуассоновским. Для класса MMP-потоков это условие предель-но частых изменений состояний потока, то есть когда интенсивности перехода потока из состояния в состояние неограниченно равномерно возрастают. А для класса общих MAP-потоков это условие предельно частых изменений состояний потока и согласованного интенсивного прореживания. При сравнении асимптоти-ческих результатов с допредельными было показано, что MMP-потоки с интен-78А.А. Назаров, И.Л. Лапатинсивностью порядка нескольких единиц можно аппроксимировать пуассоновскими при значениях интенсивностей перехода состояний потока порядка десяти и больше. Аналогичные результаты получились и для MAP-потоков при достаточно малых значениях вероятностей наступления событий при смене состояния потока.

Скачать электронную версию публикации