Calculation of moments in retrial queueing system MMPP|M|1.pdf Исследования реальных систем передачи данных и сетей сотовой связи привели к тому, что описанные системы требуют рассмотрения математических моделей, выходящих за рамки множества классических систем массового обслуживания - систем с ожиданием и систем с потерями. Таким образом, стали выделять новый класс систем, который получил название RQ-системы (Retrial Queueing Systems [1-3]) или системы с повторными вызовами. Принципиальное отличие RQ-систем от классических систем массового обслуживания состоит в том, что заявки, пришедшие в систему и обнаружившие прибор занятым, не покидают систему, а идут в источник повторных вызовов, где после некоторой задержки пытаются снова занять прибор для обслуживания. Первые работы, посвященные исследованию систем с повторными вызовами, были опубликованы в середине ХХ в. R.I. Wilkinson [4] и J.W. Cohen [5]. Основные подходы к описанию систем с ИПВ были рассмотрены G. Gosztony [6], A. Elldin [7] и др. Большинство первых работ посвящено описанию практических задач и влиянию эффекта повторных вызовов в телекоммуникационных системах. Наиболее полное и глубокое исследование различных процессов в системах с повторными вызовами проведено в работах Г.И. Фалина, J.R. Artolejo, A. Gomez-Corral и J.G.C. Templeton [1-3]. Ими получены допредельные характеристические функции для RQ-систем М|М|1, M|GI|1, M|M|c и т.д., а также рассмотрены разнообразные методы для исследования RQ-систем. Большинство исследований Retrial Queueing System реализуются численно или с помощью имитационного моделирования [08-11]. Аналитические методы получены только в тех случаях, когда модели потока и дисциплина обслуживания относительно просты (например, пуассоновский поток и экспоненциальное распределение закона обслуживания) [1]. RQ-системы с входящими МАР- и ВМАР-потоками исследуются в работах В.И. Клименок, А.Н. Дудина [12], в которых используются преимущественно матричные методы исследования. Кроме того, матричные методы исследования RQ-систем используются также в работах M.F. Neuts, J.R. Artalejo, A.G omez-Corral [13], J.E. Diamond, A.S. Alfa [14] и др. В ТГУ под руководством А.А. Назарова активно развиваются различные асимптотические методы исследования моделей СМО, в том числе и RQ-систем [15, 16]. Асимптотические и приближенные методы исследования RQ-систем развивались также Г.И. Фалиным [17], В.В. Анисимовым [18] и др. Часто для построения аппроксимирующих распределений необходимо, чтобы были известны точные моменты искомых распределений. Однако в RQ-системах известны аналитические формулы вычисления моментов распределения вероятностей числа заявок в источнике повторных вызовов лишь для систем с простейшим входящим потоком. В данной работе предложено вычислить моменты для RQ-систем с входящим марковским модулированным потоком (MMPP). 1. Математическая модель Рассмотрим однолинейную RQ-систему с источником повторных вызовов (ИПВ), на вход которой поступает MMPP-поток заявок с матрицей условных интенсивностей рЛ и матрицей инфинитези-мальных характеристик Q (рис. 1), время обслуживания каждой заявки распределено по экспоненциальному закону с параметром ц. Если поступившая заявка застает прибор свободным, то она занимает его для обслуживания. Если прибор занят, то заявка переходит в ИПВ, где осуществляет случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром о. Из ИПВ после случайной задержки заявка вновь обращается к обслуживающему прибору с повторной попыткой его захвата. Если прибор свободен, то заявка из ИПВ занимает его для обслуживания, в противном случае заявка мгновенно возвращается в источник повторных вызовов для реализации следующей задержки. Рис. 1. RQ-система MMPP|M|1 Обозначим вектор-столбец R - стационарное распределение вероятностей значения цепи Маркова, управляющей входящим MMPP-потоком, которое определяется из следующей системы: RQ = 0, (1) RE = 1, где Е - единичный вектор-столбец, 0 - вектор-столбец с нулевыми элементами. Очевидно, что интенсивность входящего потока равна Х = R • рЛ • E . Пусть параметры системы таковы, что выполняется R • Л • E = ц. (2) Тогда загрузка системы определяется как р = Х / ц = А, / (R •Л • E). Для данной системы ставится задача найти математическое ожидание и дисперсию распределения вероятностей числа заявок в источнике повторных вызовов такой системы. Пусть i(t) - процесс, характеризующий число заявок в ИПВ. Процесс i(t) не является марковским. Однако его можно марковизировать путем введения дополнительных компонент: n(t) - цепь Маркова, управляющая ММРР-потоком, а процесс k(t) определяет состояние прибора следующим образом: k^^ |0, если прибор свободен, [1, если прибор занят. Обозначим P{k(t) = k, i(t) = i, n(t) = n} = P(k,i,n,t) - вероятность того, что прибор в момент времени t находится в состоянии k, управляющая MMPP-потоком цепь Маркова - в состоянии n, и в источнике повторных вызовов находится i заявок. Очевидно, что процесс {k(t), i(t), n(t)} изменения состояний данной системы во времени является марковским. Для получения распределения вероятностей P(k,i,n,t) состояний рассматриваемой RQ-системы составим систему уравнений Колмогорова: aP(°;^t) =P, n, i, t)-(pXn +io-qnn) P(0, n, i, t) + £ P(0, v, i, t) •qm, ot v^n aP(1;n't) = -(p^n + ц- qnn) P(1, n, i, t) + p^P(0, n, i, t) + (3) ot +p^P(1,n,i -1, t) + c(i +1) • P(0,n,i +1, t) + XP(1, v,i, t)qvn. Обозначим векторы-строки P(k,i) = {P(k,1,i) P(k,2,i) ... P(k,N,i)}, где в стационарном режиме limP(k,i,n,t) = P(k,i,n). Тогда в матричном виде система (3) примет вид t -^да P(0,i)(Q -рЛ - io • I) + цР(1,i) = 0, P(1,i)(Q - рЛ - |I) + Р(0,/)рЛ + P(1,i - 1)рЛ + o(i +1) • P(0,i + 1) = 0, () где I - единичная матрица. Перейдем в системе (4) к частичным характеристическим функциям H(k,ы) = ^ eJmP(k,i), где i j = V-1 - мнимая единица. Тогда система уравнений (4) для характеристических функций перепишется в виде Н(0,ы)(Q - рЛ) + j■oдH(QЫ + |Н(1,ы) = 0, ды (5) Н(1,ы)(Q - рЛ - |I) + Н(0,ы)рЛ + Н(1,ы)рЛe■ - joe- ■ дН(0,Ы) = 0. ды Из системы (5) найдем первый и второй моменты распределения вероятностей числа заявок в ИПВ, для этого будем использовать метод моментов. 2. Метод моментов дН (k, ы) Обозначим mk = - j ды , где k = 1,2, тогда математическое ожидание числа заявок в ы=0 ИПВ вычисляется как m = (m 0 + m1)E = mE. Кроме того, введем обозначения {R0, R1} - двумерное совместное стационарное распределение вероятностей состояний ММРР-потока и состояний прибора. Очевидно, что для векторов R0 и R1 выполняются равенства (R 0 + R1)Q = 0 и R0 E + R1E = 1. Метод моментов состоит из нескольких этапов Этап 1. Примем ы = 0 в системе (5). Получим следующую систему: |R q(Q -рЛ)-om 0 +1R1 =0, [R1 (Q - |I) + R0рЛ + omQ = 0. ( ) Умножим уравнения системы (6) на единичный вектор-столбец: | R Q (Q - рЛ)E -omQE + |R1E = 0, [R1 (Q - |I)E + R ^E + omQE = 0. В результате упрощения получим два одинаковых уравнения: J-R QрЛE - omQE + |R1E = 0, |-R1|E + R QрЛE + om QE = 0. Из этих уравнений можно выразить m QE : om0 E = | - R0(|E + рЛE). (7) Объединив первое уравнение системы (6) и уравнение (7), получаем систему для определения вектора m0 (при условии, что будут найдены векторы R0 и R1): jomo = R q(Q -рЛ) + 1R1, (8) [om 0E = R 0(|E + рЛE). Этап 2. Продифференцируем систему (5) по переменной и: 02H(0,u) oH(1,u) 0H(0,u) ц- Ои oH(1, и) 5u Ои +j 2oe (Q -рЛ) + jo Ои2 (Q - рЛ - ц1) + рЛ + °HM pЛe ju + jH(1,u)pЛe ju Ои Ои 2oe-и 0H(0,u) - yoe-и О2H(0,u) 0. Ои2 joe Ои , где k = 1,2, тогда второй момент распределения вероятностей О2 H (k, и) Обозначим dk = j' Ои2 и=0 числа заявок в ИПВ вычисляется как d = (d0 + d1)E = dE . Примем и = 0 в системе (9): Гш 0(Q -рЛ) -od0 +цт1 =0, [m1 (Q - ц1) + ш 0рЛ + R1pЛ - om 0 + od0 = 0. Сложив уравнения системы (10), получим (m0 + m1)Q + R1pЛ -om0 = 0. Умножим уравнение (11) на единичный вектор-столбец: om0 E = RpЛE - R°pЛE. Учитывая условие (2), имеем следующее выражение: om0E = рц - pR0 ЛE. Приравняем (12) к (7): рц - pR0ЛE = ц - R0 (^E + pЛE). Отсюда несложно получить, что выполняются следующие равенства: |R 0E = 1 -р, [R1E = р. Умножим уравнения системы (10) на единичный вектор-столбец: f-pm0 AE - od0E + цm1E = 0, [-цш^ + pm0ЛК + pR1ЛE - om0E + od0E = 0. В итоге некоторых преобразований получим дополнительное уравнение od0E = цш^ - pm0 AE. Этап 3. Продифференцируем систему (9): H(0." )(Q - рЛ) + joОH°U) + цО^ = 0, Ои2 Ои2 Ои3 2 О2H(1,u) А тч О2H(0,u) .ОЩ1,и) jU О2H(1,u) и ^ л j (Q -рЛ -ц1) +-рЛ + j-^ рЛеj +-рЛеj + j 2Щ1,и)рЛеj Ои2 Ои 2_ _ ,u О2 H(0,u ), - ju О2 H(0,u) v_-ju 03H(0,u) A ju -3_ - ju °H(0,u) .2 - ju ^ "v^,"/ .2 - ju рЛе - j oe--+ j oe--L ' 0. +j ■] oe joe Ои2 Ои3 Ои2 Ои Ои2 Ои2 QH(1,u) Ои (10) (11) (12) (13) (14) , где k = 1,2 . Аналогично предыдущему этапу, д3Н (k, ы) Обозначим вектор-строки ek =- j ды3 ы=0 примем ы = 0 в системе (15): jdo(Q - рЛ) - oeQ + id = 0, [d1 (Q - |I) + dQрЛ + 2ш1рЛ + R1рЛ + omQ - 2od0 + oeQ = 0. Сложив уравнения системы (16), получим следующее равенство: (dQ + d1)Q - 2od0 + 2ш1рЛ + R1рЛ + omQ = 0. Умножим полученное уравнение на единичный вектор-столбец. 2od0E = 2ш1рЛE + R1рЛE + om 0E. (16) Подставляя в последнее уравнение выражение (14), можно получить следующее скалярное уравнение: m1 (|E - рЛБ) = 2 R^E + 2 m 0(2рЛE + oE). (17) (18) Из матричного уравнения (11) и скалярного уравнения (17) получаем систему для определения вектора m1: m^ = omQ - moQ - ^рЛ, m1 (|E - рЛE) = 2 RlрЛE + 2 шQ(2рЛE + oE). (19) Так как векторы m1 и do связаны соотношением (14), то из (10) для определения вектора do получаем систему [odo = m q(Q -рЛ) + цш1, (od 0E = |m1E - рш q AE. Этап 4. Немного преобразуем систему (15): д!Н

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