Asymptotical analysis of a non-Markovian queueing system with renewal input process and random capacity of customers.pdf При проектировании систем обработки и передачи сообщений, таких как систем коммутации сообщений и систем обработки радиолокационной информации возникает задача определения объема памяти, предназначенной для хранения информации о сообщении во время его передачи и обслуживания. Величина такого объема определяется непрерывной случайной величиной, которую будем называть суммарным объемом требований [1]. Задача определения характеристик суммарного объема требований в классических системах теории массового обслуживания и ее приложениях к решению задач проектирования компьютерных и коммутационных систем обсуждалась в работах [2-4], где исследовались некоторые характеристики таких систем в предположении, что входящий поток является простейшим, время обслуживания распределено по экспоненциальному закону, а параметры обслуживания требования могут зависеть от объема требования. Современные потоки данных в информационных и телекоммуникационных системах включают в себя интегрированные потоки, содержащие передачу текста, голоса и видеоисточников, что требует использования более сложных моделей потоков. В качестве таких моделей, как правило, используют математические модели модулированных или рекуррентных потоков [5, 6]. Для исследования систем с входящими непуассоновскими потоками, например, рекуррентным и марковски модулированными потоками, в работах [7-9] предлагается использовать метод асимптотического анализа, позволяющий находить приемлемое для практических приложений решение в определенных условиях. 1. Постановка задачи Рассмотрим систему массового обслуживания (СМО) с неограниченным числом приборов, на вход которой поступает рекуррентный поток, заданный функцией распределения длин интервалов между последовательными моментами поступления заявок в систему A(x). Продолжительность обслуживания заявки имеет произвольную функцию распределения, одинаковую для всех приборов B(x). Предполагаем, что каждое требование характеризуется некоторым случайным объёмом v > 0, G(y) = P{v < y} -функция распределения случайной величины v. Объемы различных требований независимы. По окончании обслуживания заявка покидает систему и «уносит» свой объем. Пусть i(t) - число заявок, находящихся на обслуживании в системе в момент t, V(t) - полная сумма объемов требований, находящихся в системе в момент времени t. Поставим задачу нахождения характеристик двумерного случайного процесса [i(t),V(t)}. Отметим, что исследуемый процесс не является марковским. Поэтому для его исследования будем использовать метод динамического просеивания [10]. Построим просеянный поток для рассматриваемой СМО GljGIjw. Для этого зафиксируем некоторый момент времени T. Полагаем, что заявка входящего потока, поступившая в систему в момент времени t < T с вероятностью S(t) = 1 - b(t -1), формирует событие просеянного потока, а с вероятностью 1 - S(t) эта заявка в просеянном потоке не рассматривается. Обозначим n(t) - число событий просеянного потока, наступивших до момента времени t, W(t) -суммарный объем просеянных требований. Тогда, если в начальный момент t0 < T система была свободна, то для момента времени T для любых m и v выполняются равенства P{i(T) = m} = P{n(T) = m}, P{V(T)< v} = P{W(T) < v}. Следует отметить, что использование метода просеянного потока позволяет точно определить характеристики процесса V(t), так как в просеянном потоке присутствуют только те заявки, которые не закончат обслуживание к моменту времени T. 2. Дифференциальное уравнение Колмогорова Введем обозначение P(z,n,w,t) = P{z(t) < z,n(t) = n,W(t) < w} - распределение вероятностей трехмерного Марковского процесса, где z(t) - остаточное время от момента t до момента наступления следующего события в исходном рекуррентном потоке. Для этого распределения составим At-методом прямую систему дифференциальных уравнений Колмогорова. По формуле полной вероятности запишем равенство P(z, n, w, t + At) = [[(z + At, n, w, t) - P(At, n, w, t)] + P(At, n, w, t )(1 - S (t ))A(z) + V + S(()A(z)JP(At,n -1, w - y, t)dG(y) + o(At), (1) 0 z > 0, n = 0,1,2,..., w > 0 . Из (1) получаем систему дифференциальных уравнений Колмогорова 8P(z, n, w, t) 8P(z, n, w, t) + 8P(0, n, w, t) ((z)-1) + 8t 8z 8z S ()A(z) + с начальным условием v 8P(0, n -1, w - y, t))) - 8P(0, n, w, t) 0 8z 8z z > 0, n = 0,1,2,..., w > 0, ч [R (z), n = 0, w > 0, P (z, n, w, t0 ) = M ^0 [ 0 иначе. Здесь и далее R(z) - стационарное распределение вероятностей значений случайного процесса z(t), определяемое выражением z 1 R( z) = IJ (1 - A( x))dx, где I = --. 0 J (1 - A( x))dx 0 Введем частичную характеристическую функцию вида дада h(z,u1,u2,teJU1" JeJ"2wP(z,n,dw,t), z > 0. n=0 0 Учитывая, что Y jn f eju2w jr ap(0,n -1,d(w - y),t)(y) = j 8h(О,Цд,ц2,t)Q.() «=1 ' ' 8z 8z 2 ' где G (u2) определяется как да G * (u 2 )=J eJ'"2 ydG (y ), можно записать дифференциальное уравнение в частных производных первого порядка 8h(z, uf Ц2,t) = 8h(z, uz u 2,t) + 8h(0, uz u2,t) [a(z ) -1 + S (t )A(z )(e « G * (u2)-1)] (2) с начальным условием h(z, u1, u 2, 10 ) = R(z). (3) 3. Метод асимптотического анализа Так как прямое решение уравнения (2) не представляется возможным, то для решения задачи (2)-(3) воспользуемся методом асимптотического анализа [11] в условии неограниченно растущей интенсивности входящего потока [10]. Запишем функцию распределения длин интервалов между моментами поступления заявок в систему в виде A(Nz), где N ^ да - параметр высокой интенсивности потока. Тогда, выполнив преобразования, уравнение (2) примет вид 1_8h(z,u1,u2,t) = 8h(z,u1,u2,t) + 8h(0,u1,u2,t) [a(z)-1 + S(t)A(z(G* (u2)-1)] (4) N 8t 8z 8z с начальным условием h(z, u1, u 2, 10 ) = R(z). (5) Асимптотический анализ первого порядка проведем в виде доказательства теоремы 1. Теорема 1. Асимптотическая характеристическая функция распределения вероятностей процесса {z(t), n(t), V(t)} первого порядка имеет вид h(z , u1 ,u 2, t) = R(z )exp< Nk[ju1 + ju 2 a1 ]] S (t Ш, I (0 J где a1 - математическое ожидание случайной величины, определяемой функцией распределения объема требований G(y). Доказательство. Выполним в выражениях (4) и (5) замены 8 = N-, u1 = gw1, u2 = sw2, h(z, u1, u 2, t ) = f1 (z, w1, w2, t, 8) . (6) Тогда задача (4)-(5) примет вид 8 8f1(z, w1, w2,t,8) = 8/1(z, w1, w2,t,8) + 8/1(0, w1, w2,t,8) [a(z) -1 + s(t)A(z)(e jw G* (8w2 )-1)] (7) 8t 8z 8z с начальным условием /1 (z, w1, w2, t0, 8)= R(z) . (8) Найдем асимптотическое, при e ^ 0, решение задачи (7)-(8), т.е. /1 (z, w1, w2, t) = lim /1 (z, w1, w2, t, 8). Этап 1. Положим в (7) e ^ 0, получим 8/1 (( w1, w2 , t) + 8/1 (0, wb w2 , t) (A(z)- 1) = 0 8z 8z Можем сделать вывод, что /1 (z, w1, w2, t) может быть представлена в виде /1 (1, w2, t ) = R(z )Ф1 (w1, w2, t), (9) где Ф1 (w1, w2, t) - некоторая скалярная функция, в силу (8) удовлетворяющая условию Ф1 (w1, w2, t0 ) = 1. Этап 2. Выполним в (7) предельный переход z ^ да. Получим е f (да,w2,г,в) = f (0,w2,г,в)^{f ) тG*(ew2) _ 1. dt dz Подставим сюда выражение (9), воспользуемся разложениями ejew1 = 1 + jew1 + о(е2), ejew2 = 1 + jew2 + о(е 2), поделим обе части на е и произведем предельный переход при е ^ 0. С учетом того, что R (о) = X [10], получим дифференциальное уравнение относительно функции Ф1 (w1, w2, t): (W2,t) = Ф1 (W1,W2,t)S(t)jW1 + jwa)], (10) ot да здесь и далее a1 = J ydG (y) - математическое ожидание случайной величины, определяемой функцией 0 распределения объема требований G (у). Решение (10) с учетом начального условия дает Ф1 (w1,W2,t) = exp•^X((W1 + jw2a1 ))S(t))t| . Подставляя данное выражение в (9), получаем f1 (w1, W2 , t) = R(z)exp ^(М + jw2a1 )) S(t)t 11 . В силу замен (6) можно записать асимптотическое, при е ^ 0, приближенное равенство: h(z,«1,u2,t) = /1 (z, W1,W2,t,e)» /1 (z, W1,W2,t) = R(z)®1 (w1,W2,t) = uu j- + j-a1 ее = R(z )exp = R(z)exp< NXjj + ju2a1]]S(t)dT >. t J l t0 J Теорема доказана. Функция h(u1,«2,t)= lim h(z,u1,u2,t) есть характеристическая функция для процесса {n(t),V(t)} z ^да числа событий, наступивших в просеянном потоке к моменту времени t и суммарного объема требований в просеянном потоке к моменту времени t. Следствие. Полагая t = T, t0 = _да, для характеристической функции процесса {((), V(t)} в стационарном режиме получим h(u1, u 2 ) = exp{NX61 [ju1 + ju 2 a1 ]}, здесь и далее да b1 = J (1 _ B(t )))t 0 определяет математическое ожидание случайной величины с функцией распределения B(x). Асимптотический анализ второго порядка проведем в виде доказательства теоремы 2. Теорема 2. Асимптотическая характеристическая функция распределения вероятностей процесса {z(t),n(t),V(()} второго порядка имеет вид h(z, u1, u 2, t) = R(z) exp J NX(j'u1 + ju 2 a1 )J S(t^t + (u1) NX J S (t )dt + Nk J S 2 (t )dt 2 ( t t + 2 V '0 '0 у , (u2) NXa2 J S(t)dT + Na12к J S2 (t)dT +(j)2u1u2 NXa1 J S(T)dT + Na1K J S2 (t)dT 2 V t0 t0 у V t0 t0 где к = 2(f '(0) Xf (да)), a2 - второй начальный момент случайной величины, определяемой функцией G(y); функция f (z) -некоторая функция. Доказательство. В уравнении (4) выполним замену h(z, u1, u 2, t) = h2 (z, u1, u2, t)exp

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