Heuristic algorithm for estimating the number of states of asynchronous MC-flow events.pdf Математические модели теории массового обслуживания широко применяются при описании реальных физических, технических, экономических и других процессов и систем. В связи с развитием компьютерной техники и информационных технологий появилась важная сфера приложений теории массового обслуживания - проектирование и создание цифровых сетей интегрального обслуживания (ЦСИО). Условия функционирования реальных объектов и систем таковы, что если в отношении параметров обслуживающих устройств можно сказать, что они известны и с течением времени не меняются, то в отношении интенсивностей входящих потоков этого сказать во многих случаях нельзя. Более того, интенсивности входящих потоков обычно меняются со временем, часто эти изменения носят случайный характер, что приводит к рассмотрению математических моделей дважды стохастических потоков событий. По-видимому, статьи [1, 2] являются одними из первых работ в этом направлении, где дважды стохастический поток определяется как поток, интенсивность которого есть случайный процесс. С другой стороны, функционирование систем массового обслуживания (СМО) зависит от параметров и состояний входящих потоков. В подобных ситуациях наиболее рациональным является применение адаптивных СМО, которые в процессе функционирования оценивают неизвестные параметры либо состояния входящих потоков и изменяют дисциплину обслуживания в соответствии с полученными оценками [3]. Дважды стохастические потоки можно разделить на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс; ко второму классу - потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным числом состояний. Подчеркнём, что потоки второго класса впервые введены в рассмотрение практически одновременно и независимо в 1979 г. в [4-6]. В [4, 5] введённые потоки названы МС (Markov СЬат)-потоками; в [6] - MVP (Markov Versatile Processes)-потоками. С начала 1990-х гг. отечественные и зарубежные авторы называют в своих работах введённые потоки событий либо дважды стохастическими потоками, либо МАР-потоками, либо МС-потоками [7-13]. В свою очередь, в зависимости от того, каким образом происходит переход из состояния в состояние, МС-потоки событий можно разделить на три типа: 1) синхронные потоки [14, 15]; 2) асинхронные потоки [16, 17]; 3) полусинхронные потоки [18]. Здесь указаны ссылки на статьи, в которых авторы впервые рассматривали МС-потоки событий в соответствии с приведённой классификацией. Наиболее полная литература по изучаемым типам МС-потоков событий приведена в [19]. Отметим, что синхронные, асинхронные и полусинхронные потоки возможно представить в виде моделей МАР-потоков событий первого либо второго порядков [20]. В [20] показано, что синхронный МС-поток является частным случаем МАР-потока первого порядка, асинхронный и полусинхронный МС-потоки являются частными случаями МАР-потока второго порядка. Как было отмечено выше, в реальных ситуациях интенсивность входящего потока событий изменяется со временем случайным образом, поэтому при реализации адаптивного управления СМО возникают, в частности, следующие задачи: 1) оценка состояний потока по наблюдениям за моментами наступления событий [21]; 2) оценка параметров потока по наблюдениям за моментами наступления событий [22]. В приведённой литературе [14-21] задачи по оценке состояний и параметров того или иного потока решаются в предположении, что число состояний потока известно и равно двум. В статьях [22-26] решены задачи по оценке параметров и состояний потоков событий, когда число состояний потока произвольно и конечно. Однако на практике часто возникают ситуации, когда априорные данные о числе состояний потока отсутствуют. Вследствие этого для реализации адаптивного управления в СМО возникает задача об оценке числа состояний потока, которая решается в настоящей статье для асинхронного МС-потока событий (далее асинхронный поток либо просто поток). 1. Постановка задачи Рассматривается асинхронный поток событий с произвольным конечным числом состояний. Интенсивность потока является кусочно-постоянным случайным процессом A(t) с n состояниями: A2,..., An (A1 > A2 > ... > An > 0). Процесс (поток) A(t) в момент времени t находится в i-м состоянии, если A(t) = A;- (i = 1,n). В течение времени пребывания в i-м состоянии поток ведет себя, как пуассоновский с параметром Xi (i = 1, n ). Длительность пребывания в i-м состоянии есть экспоненциально распределённая случайная величина с функцией распределения Fi (т) = 1 - ea"x, где аи = - X aiJ- (i = 1, n); aiJ- > 0 (i, j = 1, n, i * j ) - интенсивность перехода процесса A(t) из состоj=1, j *i яния i в состояние j. В сделанных предпосылках A(t) - скрытый марковский процесс. Блочная матрица инфинитезимальных коэффициентов примет вид г n \ X + X «1 j V j=2 J A, 0 a a a 12 13 2n '2 + X a 2 j V j=1, j * 2 J 0 A2 a a a 21 23 2n = |D0 I D1|. D = n-1 ■ X a j j=1 J A n A. 0 0 a a a n1 n2 n3 Элементами матрицы Di являются интенсивности перехода процесса A(t) из i-го состояния в i-е (i = 1, n) с наступлением события. Недиагональные элементы матрицы D0 - интенсивности переходов из состояния i в состояние j (i, j = 1, n , i * j ) без наступления события. Диагональные элементы матрицы D0 - интенсивности выхода процесса A( t) из своих состояний, взятые с противоположным знаком. Отметим, что определённый таким образом поток событий называется асинхронным, так как переходы процесса A(t) из i-го состояния в j-е (i, j = 1,n , i ф j ) не привязаны к моментам наступления событий пуассоновских потоков. Асинхронный поток также называют ММР (Markov Modulated Ро1880и)-потоком [27]. Предполагается, что на вход адаптивной СМО поступает асинхронный поток событий с заданными, но неизвестными параметрами, т.е. значения параметров Xi, aij (i, j = 1,n, i ф j ) и значение числа состояний потока n неизвестны. Процесс А(t) является принципиально ненаблюдаемым, наблюдению доступны только временные моменты наступления событий потока. Рассматривается стационарный режим функционирования наблюдаемого потока событий, поэтому переходными процессами на отрезке наблюдения [t1,tk], k = 2,3,..., где t1 - начало наблюдений (момент наступления первого события потока), tk - окончание наблюдений (момент наступления k-го события потока), пренебрегаем. Общая задача заключается в следующем: необходимо по наблюдениям (моментам наступления событий t1,., tk) оценить значения неизвестных параметров Xi, щ (i, j = 1,n , i ф j ), n. Замечание 1. Существенным является значение числа n: если n велико, то на отрезке наблюдения [t1,tk], k = 2,3,. , возможны ситуации, когда процесс A(t) не перейдёт во все возможные состояния, и принятое решение об оценке n числа состояний процесса А(t) будет в принципе неверным. Замечание 2. Если тем или иным статистическим алгоритмом построена оценка n числа n, то тогда для оценки параметров Xi, щ (i, j = 1,n , i ф j ) можно использовать алгоритм, разработанный в [26]. 2. Свойство плотности вероятностей оценки интенсивности простейшего потока В соответствии с определением потока реализация процесса А(t) имеет временные участки, где A(t) = А;-, i = 1,n, - так называемые интервалы стационарности. Если алгоритм обработки моментов наступления событий tx,..., tk каким-либо образом оценит число таких интервалов стационарности, то тем самым будет осуществлена оценка n . Предположим, что последовательность моментов наступления событий t2,..., tk, k = 2,3,. , целиком принадлежит некоторому интервалу стационарности, для которого A(t) = Ai, i = 1, n . Положим для конкретности А(t) = A, Ае(А1,.,An), при этом конкретное значение X неизвестно. Отметим, что число событий на этом интервале может быть равным нулю, единице и т.д. (k = 0,1,2,.). Обозначим Tk = tk+1 - tk, k = 1,2,..., - значение длительности k-го интервала между соседними событиями пуассоновского потока интенсивности X. Обозначим Tk = т1 + т2 +... + Tk - значение длительности отрезка [t1,tk+1 ], k = 1,2,_Тогда, так как длительность интервала (tk,tk+1) , k = 1,2,..., между соседними событиями в пуассоновском потоке распределена по экспоненциальному закону с параметром X, то плотность вероятностей суммы независимых экспоненциально распределённых случайных величин при фиксированном k есть [28]: P(Tk ) = X(-^e-XTk, Tk > 0. (1) Как известно [29], оценка максимального правдоподобия А = k/Tk интенсивности X является смещённой оценкой. Будем рассматривать исправленную оценку A(k) =( k - 1)/Tk , k = 2,3,. . (2) Тогда, с учётом (1), математическое ожидание оценки (2), её дисперсия и количество информации о параметре X в выборке (х1,т2,...тк) , к = 1,2,..., примут вид MX = X, D- = X2/( к - 2), Ik (X) = к/ X2 . Таким образом, оценка (2) является сильно состоятельной, несмещённой и асимптотически эффективной. Плотность вероятности оценки X(к) при фиксированном к, с учётом (1), примет вид P (X(к )) = хк fclL- [X(к) к-1 ,, 1Ч X к-1 (к) W к 23 (3) e X , к = 2,3,. . (3) (к - 2) Пусть на интервале стационарности, где X(t) = X, реализовалось N +1 событий пуассоновско-го потока интенсивности X: t1,t2...,tN,tN+1. Соответствующие значения длительностей интервалов между соседними событиями есть тj = tj+1 - tj, j = 1, N . Построим набор оценок для интенсивности X с использованием (2) по следующему правилу: Xf^ - Wlv^, к = 2, N; j = 1, N - к +1. (4) / s=1 Количество оценок набора (4) N (N -1)/2. Доля оценок X(к), полученных при фиксированном к (к = 2, N), в наборе (4) составляет величину ш) = 2(N - к +1) к=TN • = 1 (5) Чк = N(N -1) , к 2N • к?2Як = (5) Вернёмся к формуле (2), которая даёт оценку интенсивности X. Так как X(к) (X(к ] > 0 ), с одной стороны, является значением случайной величины (или просто случайной величиной) для каждого к (к = 2, N), с другой стороны, для каждого к определены плотности вероятностей (3), то в (3) число к можно рассматривать как параметр, принимающий значения 2,3,.,N . При этом величину q, определённую в (5), можно рассматривать как вероятность того, что параметр к принял некоторое значение из ряда чисел 2,3,.,N . Тогда в (3) переменную X(к) можно заменить на переменную X и рассматривать смесь плотностей вероятностей (3) для к = 2, N : Pn (x) = NqC \ (X) Рк (К (к-)1 (X. (6) где q(N) определена в (5). Таким образом, (6) является выпуклой линейной комбинацией функций Рк (X). Исследуем функциюPn (X) как функцию переменной X (X > 0). Введём новую переменную = X/X ( х > 0). Из (6) вытекает (х ) = Ц '"'(г1)- хк+'е-('-')Х ■ х > 0. (7) х , , ^ _ )-1 Pn (х) = - г q^;, л. хк+ , х > Точки функции (7), подозрительные на экстремум, определяются уравнением P„ ' (x)=1 q-' ^Vxj [(к+1) - (к :1, к = где (Як" V^2" )) < 1, к = 3,N. Тогда из (8) следует, что корни функции P'N (x) находятся из уравнения n F' (x) = 0; Fn (x)=± f()(x); к=2 \к-1 (9) (N) (к _ 1\к-1 f(N) (x) = J") (B^хк-2е-(к-2)x [(к +1) - (к -1) x]. Единственный ноль функции fк')(x) есть x0)= 1 + 2 (к -1) 1, к = 2, N . Тогда имеем FN (x)> 0 для 0 < x < 1 + 2 (N -1)-1, Fn (x)< 0 для x > 3. Таким образом, нули функции FN (x) (один или несколько) будут лежать в полуинтервале (1 + 2 (N -1)-1;3 . Покажем, что функция Fn (x) является строго монотонной на полуинтервале (1 + 2(N -1) 1;3 . Тогда FN (x) будет иметь на этом полуинтервале единственный ноль, а следовательно, функция (7) - единственный максимум. Производная FN (x) выпишется в виде ,( n)((- 1)-1 (з ,к7) x("V^"2^ (x ), (10) (x) = (к -2))к- 1)x2 - (к-1)2 +(к -2))к +1) x + (к-2))к +1). Отметим, что функция zk (x) в (10) определяет знак каждого слагаемого функции FN (x) ; кроме того, Z( (x) - выпуклая функция переменной x, её минимум достигается в точке Fn '(* ) = ".. к" '(x ) = ' f x(-3е-к-2)4(x ). к=2 = 1 + (к -1) 1 +(2(к -1)) 1, к = 3, N. Функция zk (x) отрицательна на интервале (x2), x^)), 0к к = 3, N, где + 1 ( 1 к - 2 [ 4 (к - ^к (0к ) = -[(к +1) + (к - 3)2 (4 ( - 2 )(к -1)) к2 - 2 г(к ) = 1,2 _ , x2к)< xfк)< 4; x?) 0 для 1 < x < 5/3, ф4 (x)< 0 для x > 2,5, то в единственной точке x* (5/3 < x* < 2,5) имеет место ф4 (x = x* ) = 0 . Тогда ф4 (x) < 0 для x > x* : а) ф4 (x) < 0 для x* < x < 2,5 в силу строгой монотонности функции ф4 (x) на полуинтервале (x*;2,5 ; б) ф4(x) < 0 для x > 2,5 в силу определения функции ф4(x) в (12). Наконец, в точке xj(4) имеет место F4(x = x14)) 0, F4 (x14)) < 0. Таким образом: 1) функция F4 (x) имеет единственный ноль в точке x4 е (1, x14)): 1 Г 1 i к - 2 [4 (к -2) к2 - 2 1 1 к -1 2 (к - 2) к -1 к=4 к=4 2) функция F4 (x) не достигает нуля для x > x4 ; 3) функция ф4 (x) - строго монотонная (убывающая) для 1 < x < x14), имеющая единственный ноль в точке x* (^3 < x* < x14)) и не достигающая нуля для * . (3) (4) x > x4 ; x 1 > x 1 . Рассмотрим произвольное N +1. Имеем 11 1 fn+i (x) = fn (x) + 9n+I (x) fn+1 (x) = fn (x) + 9n+I (x) 1 N+1 x°N . Так как x'+1 < x'^+1 < x1N), то FN+1 (x) не достигает нуля для x > xN0 +1 . Чтобы замкнуть доказательство, нужно доказать, что функция 9N+1 (x) не достигает нуля для x > x*N+1 и 1 < x*N+1 < x1 N+1). Имеем 9N+1 (x) = FN+1 (x) - FN (x), N > 3. В точке x = x1 N+1) выполняется (x1N+1))< 0. Тогда: 1) если FN(x1 N+1))< 0 и FN+1 (x1 N+1))>-FN(x1N+1)), то 9N+1 (x1 N+1))< 0 и F < N+1 9n+1 (x) имеет единственный ноль x*N+1 е (1; x[N+1)) ; 2) если FN(x1( N+1))< 0 и FN+1 (x1N+1)) < -Fn (x(+1)) , то фN+1 (xJN+1)) > 0, т.е. FN+1 (x) > FN (x) для 1 < x < x|N+1) и точка xN+1, определяющая ноль функции фN+1 (x) на интервале (1; x|N+1)), отсутствует, что противоречит рассмотренным случаям N = 3 и N = 4; 3) если FN (x|N+1))> 0, то фN+1 (x|N+1))< 0 и фN+1 (x) имеет единственный ноль в точке xN+1 е (1; x|N+1)) . Таким образом, ф^1 (x(N+1)) < 0 и 1 < xN+1 < x|N+1). Представим фN+1 (x) в виде ф-N+1 (x ) = N(N-1) xe-*ф N+1 (x ). Ф N+1 (x ) = N x-2e-(k-2" ( - - . Знак функции фN+1 (x) определяется знаком функции ФN+1 (x) , при этом точка нуля этих функций есть xN+1. Точки xk = (k + 2))k образуют интервалы (1 + 2/ (k +1) ;1 + 2/ k ), k = 2, N, в один из которых попадает точка x|N+1), в которой ФN+1 (x|N+1)) < 0 , при этом x|N+1) > x*N+1. Точка x|N+1) разбивает слагаемые в ФN+1 (x) на положительные и отрицательные. При изменении x от x1(N+1) до 2 количество положительных слагаемых уменьшается (для x > 2 положительных слагаемых нет). Тогда ФN+1 (x) < 0 для x > x1(N+1). Таким образом, функция фN+1 (x) не достигает нуля для x > xN+1. Доказательство завершено. Следствие 1. Функция PN ( x) (x > 0), определённая формулой (7), имеет единственный максимум в точке xN0 , лежащей в границах (13). Следствие 2. Плотность вероятностей PN (1), определённая в (6), имеет единственный максимум в точке 10 = l/ xN . Следствие 3. В силу неравенства (13) при N точка нуля функции (7) x° ^ 1, т.е. 10 . 3. Оценивание числа состояний асинхронного потока Результатом процесса наблюдения за пуассоновским потоком является последовательность оценок (2), которая позволяет построить гистограмму оценок, являющуюся, в свою очередь, оценкой плотности вероятностей PN (1). В силу этого корректно построенная огибающая гистограммы будет иметь единственный максимум. Если на временной оси в течение достаточно большого временного интервала функционирует пуассоновский поток интенсивности а затем на таком же достаточно большом интервале времени - пуассоновский поток интенсивности (11 ^ 12), то построенная по результатам наблюдений гистограмма оценок будет иметь два максимума. Корректно построенная огибающая первой гистограммы (1 = 11) и огибающая второй гистограммы (1 = 12) будут иметь общую точку пересечения, которая делит ось оценок на две части: в одной части будет иметь место гипотеза 1 = 11, в другой - гипотеза 1 = 12 . Так как асинхронный поток имеет n состояний: 1(t) = 1, i = 1, n , то в процессе наблюдения за потоком при построении оценок (2) одна часть оценок будет относиться к оценкам, построенным на участках стационарности, другая часть - к оценкам, построенным на временных интервалах, одна часть которых относится к одному участку стационарности (1(t) = 1i, i = 1, n ) процесса 1(t), другая часть - к другому участку стационарности (1 (t) = 1 j , J = 1, n, i ф j ) процесса A(t). Построенная при этом гистограмма оценок при достаточно больших длительностях участков стационарности будет иметь несколько максимумов. Число этих максимумов n и будет оценкой числа состояний n асинхронного потока событий. Оценки Ai, i = 1, n , определятся как точки максимума огибающей гистограммы оценок. Другой путь определения оценок Ai, i = 1, n , заключается в построении n функций правдоподобия и решении n оптимизационных задач на максимизацию по переменной X функций правдоподобия. Заключение Полученные результаты делают возможным в процессе наблюдения за потоком оценивание неизвестного числа состояний асинхронного МС-потока событий. Кроме того, предложенный эвристический подход позволяет осуществлять оценку Ai, i = 1, n , величин Ai, соответствующих тому или иному участку стационарности процесса A( t) .

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