Research of the dynamic and adaptive retrial queue systems with input MMPP-process requests.pdf Построению и исследованию RQ-систем (Retrial Queue) [1, 2] в настоящее время посвящается достаточно большое количество научных работ, например работы Г.И. Фалина [3], В.И. Клименок [4], А.Н. Дудина [5], А.А. Назарова [6, 7], поскольку считается важным оценить производительность и спроектировать телефонные сети, локальные вычислительные сети с протоколами случайного множественного доступа, широковещательные радиосети, мобильные сотовые радиосети. Наличие повторных попыток получить обслуживание является неотъемлемой чертой этих систем, игнорирование данного эффекта может привести к значительным погрешностям при принятии инженерных решений. Методы теории массового обслуживания [8-10] являются наиболее результативными в исследовании RQ-систем. Наиболее эффективным является метод асимптотического анализа [11], которым воспользуемся при проведении исследования динамической и адаптивной RQ-систем с ММРР-потоком заявок. 1. Математическая модель динамической RQ-системы В данной работе динамической RQ-системой c входящим ММРР-потоком заявок будем называть систему массового обслуживания (СМО) с источником повторных вызовов (ИПВ) и входящим марковски-модулированным пуассоновским потоком (ММРР-потоком) заявок, управляемую динамическим протоколом доступа [12]. На вход RQ-системы поступает ММРР-поток заявок из внешнего источника, определяемый диагональной матрицей Л условных интенсивностей Xn и матрицей Q инфинитезимальных характеристик qvn цепи Маркова n(t), управляющей ММРР-потоком. Заявка, заставшая прибор свободным, занимает его для обслуживания в течение случайного времени, распределенного по экспоненциальному закону с параметром ц. По завершении обслуживания заявка покидает прибор. Если во время обслуживания заявки поступает другая, то поступившая заявка переходит в ИПВ. Из ИПВ после случайной задержки заявка с динамической (зависящей от состояния ИПВ) интенсивностью у / i вновь обращается к прибору с повторной попыткой его захвата, i - число заявок в ИПВ. Если прибор свободен, то заявка становится на обслуживание, если же он занят, то возвращается в ИПВ. Состояние системы в момент времени t определяется трехмерной цепью Маркова {k(t), n(t),i(t)}, где i(t) - число заявок в ИПВ, n(t) - значения цепи Маркова, управляющей ММРР-потоком, а k(t) определяет состояние прибора следующим образом: к(t) = 0 , если прибор свободен, и к(t) = 1, если прибор занят. Обозначим P {к(t) = к,n(t) = n, i(t) = i} = P(k, n,i, t) - вероятность того, что в момент времени t прибор находится в состоянии к, цепь Маркова в состоянии n и в ИПВ i заявок. Таким образом, распределение вероятностей P(k, п, i, t) удовлетворяет следующей системе дифференциальных уравнений Колмогорова для распределения вероятностей P(k,n,i,t): d^0:^t) = -(X n + Y ) P(0, n, i, t) + цР(1, n, i, t) + X P(0, V, i, t )qvn dt v . dP(1, n,t) = -(X + ц)P(1, i, t) + yP(0, n, i +1, t) + XnP(0, n, i, t) + (1) dt +XnP(0, n,i -1, t) + XP(1, v,i, t)qvn. V Решение системы уравнений Колмогорова (1) достаточно полно определяет функционирование динамической RQ-системы с входящим ММРР-потоком заявок. Допредельное исследование проведем методом производящих функций. 2. Исследование динамической RQ-системы методом производящих функций Будем полагать, что система функционирует в стационарном режиме, то есть P(k, n, i, t) = P(k, n, i). Запишем систему (1) для стационарного распределения в матричном виде. Обозначив вектор-строки P (к, i) = {P(k, 1, i), P(k ,2, i),..., P(k, N, i)}, получим P(0,0)(Q - Л) + P(1,0)ц = 0 , i = 0, P(1,0)(Q - Л - ц/) + P(0,0)Л + P(0,1)y = 0, i = 0, P(0, i)(Q - Л - y/) + P(1, 1)ц = 0 , i > 1, (2) P(1, i)(Q - Л - ц/) + P(0, i)Л + P(1, i -1)Л + P(0, i + 1)y = 0 , i > 1. Чтобы решить систему (2), определим векторные производящие функции ад G (к, x) = X xiP(k, i), k = 0,1. (3) i=0 Из системы (2), с учетом равенства (3), получаем следующую систему для функций G(k, x): {G(0, x)(Q - Л - у/) + G(1, х)ц = -yP(0,0), (4) G(0, x)(Лх + у/) + G(1, x)(Q + (X -1)Л - ц/)x = yP(0,0). ( ) Из системы (4) получаем выражения для G(0, x) и G(1, x): G (0, x) = P(0,0) j у/ + ■^^ x (Q + (x -1) Л - ц/) j {(1 - x) у/ + xQ- --1 (Q - Л-y/)(Q + (x -1) Л) j , (5) ц J G(1, x) = - - [ yP(0,0) + G(0, x)(Q - Л - y/)]. ц Обозначим матрицы А( x) = y/ + -x (Q + (x - 1)Л-ц/), ц B(x) = (1 - x)y/ + xQ -x(Q - Л -y/)(x-1) (Q + Л), ц тогда равенство (5) перепишется в следующем виде: G(0, x) = P(0,0) A(x)B- (x). Производящая функция G(0, x) определена для всех значений x е [0,1], но матрица B(x) вырождена при x = xv , где xv - корни уравнения |B(x) = 0, принадлежащие рассматриваемому интервалу [0,1]. T (x), где элемен -1 -1 1 Обратную матрицу B (x) запишем в виде B (x) =г-- D \B( x)\ тами D(x)nn2 матрицы D(x) являются алгебраические дополнения к элементам B(x)„j„2 матрицы B(x). Из равенства нулю определителя |B( xv ) = 0 следует, что компоненты вектора P(0,0) удовлетворяют однородной системе линейных алгебраических уравнений P (0,0) A( xv )B T(xv) = 0. Эта система определяет значения компонент вектора P(0,0) с точностью до мультипликативной постоянной, значение которой определяется условием нормировки. Таким образом, удалось найти выражения (5) для производящих функций G(k, x) 3. Исследование динамической RQ-системы методом асимптотического анализа Нахождение явного выражения (5) для производящей функции в математических моделях RQ-систем является исключительной ситуацией, поэтому требуется разработка других методов анализа таких моделей. Наиболее плодотворным в этом направлении является метод асимптотического анализа, изложение которого выполним для данной модели. Это позволит выявить эффективность разработанного метода путем сравнения асимптотических результатов с допредельными [13], а также позволит сравнить их с асимптотическими результатами, полученными для адаптивной RQ-системы. Систему (4) модифицируем следующим образом: Г H (0, u )(Q -рЛ - y/ ) + H (1, и)ц = -yP (0,0), (6) 1#(0,u)(рЛ + e~juy/) + H(1,u)(Q + (e]u - 1)рЛ-ц/) = e-uyP(0,0), ( ) где р - параметр, который используется для получения предельного условия большой загрузки RQ-системы, а функция H(k, u) = G(k, eiu) = G(k, x). Систему (6) будем решать методом асимптотического анализа в условии большой загрузки рТ S1, где S1 - пропускная способность динамической RQ-системы [14]. Обозначив s = S1 -р , будем полагать также s^-0 и систему (6) будем решать при выполнении этого условия. В системе (6) выполним замены р = S1 -е , u = sw , Hk(u) = Fk(w,s), P(0,0) = еИ(е) и перепишем в виде [F, (w, s) (Q - (S - s) Л - y/) + F1 (w, s) ц = -Yen(s), (7) [f0 (w, s) ((S1 - s) Л + e"jsw y/ ) + F (w, s) (Q + (ejsw -1) (S1 - s) Л - ц/) = e"jsw Ysn (s). Теорема 1. Значение S1 пропускной способности динамической RQ-системы с входящим ММРР-потоком заявок равно значению корня уравнения YR E - S1R1ЛЕ = 0, (8) где вектор-строка Rk - совместное распределение вероятностей состояний прибора и значений цепи Маркова, управляющей входящим ММРР-потоком, которое определяется равенствами Ro (S ) = mR{(ц + Y)/ + S1 л-Q}-1, (9) R1 (S1 ) = R {/-цКц + Y)/ + S1Л - Q]-1}. Доказательство. Доказательство этой теоремы выполним в два этапа. Этап 1. Обозначим lim Fk (w, s) = Fk (w), выполнив в (7) указанный предельный переход, получим систему [Fo (w)(Q-^-y/) + F1 (w)ц = 0, (1o) Fo (w)(SЛ + y/) + F1 (w)(Q -ц/) = 0. ( ) Решение Fk (w) системы (10) будем искать в виде Fk (w) = Rk Ф( w), (11) где функция Ф(w) на бесконечности равна нулю, а Rk - распределение вероятностей состояний прибора, определяемое системой ГRo (Q-S1Л-Y/) + RJЦ = 0, (12) Ro (SЛ + y/) + R1 (Q-ц/) = 0. ( ) Нетрудно показать, что (R + R1)Q = 0, то есть RQ = 0, где R = R + R1 и удовлетворяет условию нормировки RE = 1, тогда R и R1, зависящие от S1, определяются равенствами r (s ) = цг {(ц+y)/+S л-Q}-1, R (S1 ) = R {/-^[(ц + y)/ + S Л - Q Г1}, совпадающими с (9). Этап 2. Переписав (7) в виде F0 (w,s)(Q-SjЛ-y/ + еЛ) + F (w,s^ = -Ysn(s) + O(s2), F0 (w,s)(SjЛ + y/-s(Л + ;wy/)) + F (w,s)(Q-ц/ + jswS1 Л) = Yen(s) + O(s2), просуммируем по k и n все уравнения полученной системы и получим уравнение F0 (w,s)sjwYE - Fj (w,s) jswSj ЛЕ = 0 , из которого имеем F0 (w,s)yE - F (w,s)SjЛЕ = 0 . Используя (11), получим равенство «оФ(w)yE - R1Ф(w)S1 ЛЕ = 0 , откуда получаем выражение YR E - Sj R ЛЕ = 0, которое совпадает с (8) и определяет значение пропускной способности S-й динамической RQ-системы. 4. Математическая модель адаптивной RQ-системы Рассмотрим однолинейную СМО с ИПВ и входящим ММРР-потоком, управляемую адаптивным протоколом доступа [15]. Такую систему будем называть адаптивной RQ-системой с входящим ММРР-потоком. На вход системы поступает ММРР-поток заявок [7], определяемый диагональной матрицей рЛ условных интенсивностей pXn и матрицей Q инфинитезималь-ных характеристик qvn цепи Маркова n(t), управляющей ММРР-потоком. Заявка, заставшая прибор свободным, занимает его для обслуживания в течение случайного времени, распределенного по экспоненциальному закону с параметром ц. По завершении успешного обслуживания заявка покидает прибор. Если во время обслуживания заявки поступает другая, то поступившая заявка переходит в ИПВ. Из ИПВ после случайной задержки заявка, с интенсивностью 1/T , где T - состояние адаптера в текущий момент времени, которое определим ниже, вновь обращается к прибору с повторной попыткой его захвата. Если прибор свободен, то заявка становится на обслуживание, если занят - возвращается в ИПВ. Состояние системы в момент времени t определяется четырехмерным процессом Маркова {k(t), n(t), i(t), T(t)} [5, 6], где k(t) определяет состояние прибора следующим образом: k(t) = 0 , если прибор свободен, и k(t) = 1, если прибор занят; n(t) - значения цепи Маркова, управляющей ММРР-потоком; i(t) - число заявок в ИПВ; адаптер с течением времени t свои состояния T(t) меняет следующим образом: T(t + At) = T(t) -aAt, если k(t) = 0, и T(t + At) = T(t) + pAt, если к (t) = 1, где величины а > 0, р> 0 - параметры адаптера, значения которых заданы [11]. Исследования данной адаптивной RQ-системы были выполнены методом асимптотического анализа в условии большой загрузки при определении величины S2 пропускной способности адаптивной RQ-системы как точной верхней границы тех значений р, для которых существуют стационарные режимы функционирования рассматриваемой математической модели RQ-системы и при выполнении асимптотического условия рТ S2. Результаты данного исследования опубликованы авторами в работе [16]. В ходе этих исследований была сформулирована и доказана следующая теорема. Теорема 2. Значение S2 пропускной способности адаптивной RQ-системы с входящим ММРР-потоком заявок определяется системой уравнений [YRЕ - S2R ЛЕ = 0, aRЕ -PRЕ = 0, ( ) где a, р - параметры адаптера, значения которых заданы, y - некоторая положительная постоянная, также определяемая этой системой, Rk - распределение вероятностей состояний прибора, которое определяется равенствами R (S2, Y) = MR{(ц + Y)/ + S2Л - Q}-1, R (S2, Y) = R {/-цКц + Y)/ + S2 Л - Q ]--. Из вида первого уравнения системы (13) для нахождения пропускной способности адаптивной RQ-системы и уравнения (8) для нахождения пропускной способности динамической RQ-системы следует, что пропускная способность адаптивной RQ-системы S2 равна пропускной способности динамической RQсистемы S1, то есть S1 = S2. Вид равенств (14) для нахождения распределений вероятностей состояний прибора адаптивной RQ-системы также совпадает с равенствами (9) для нахождения распределений вероятностей состояний прибора динамической RQ-системы. 5. Численный анализ динамической RQ-системы Векторную характеристическую функцию H (u) для распределения вероятностей P (i) = P (0, i) + P (1, i) числа заявок в ИПВ запишем в виде H(u) = H(0, u) + H(1, u) = H(0, u) | / - - (Q - Л - Y/) I --P(0,0). ц ; ц Тогда распределение вероятностей p(i) = P(i)Е числа заявок в ИПВ определяется обратным преобразованием Фурье от скалярной характеристической функции h(u) = Me]m(t) = X e]mp(i) = H(u)Е : i 1 г ■ ■ p(i) = — f e"juih(u)du . (15) 2п J Для заданных значений параметров ц = 1, у = 3 и матриц (-0.7 0.4 0.3 А (10 0А (1А (1 0 0А 0.1 -0.4 0.3 v 0.4 0.5 -0.9^ Q = Л = 0 2 0 0 E = 1 чЪ I = 0 1 0 0 (16) определяющих h(u), численным интегрированием (15) получим распределение вероятностей числа заявок в ИПВ p(i) (табл. 1). Таблица 1 Распределение вероятностей p(i) числа заявок в ИПВ, i = 0, 1, 2,... i 0 1 2 3 4 5 6 7 p(i) 0,220 0,094 0,082 0,072 0,063 0,056 0,049 0,043 Si 0,425 0,872 0,878 0,880 0,881 0,881 0,882 0,882 Особенность данного распределения заключается в том, что последовательность отношения Si = p(i +1) / p(i) достаточно быстро стабилизируются и при i > 3 принимает постоянное значение с точностью до двух знаков после запятой. Аналогичные результаты имеют место и для других значений параметров ц, Y и матриц Л и Q . При приведенных значениях параметров и матриц значение пропускной способности динамической RQ-системы равно S1 = 0,790. 6. Численный анализ адаптивной RQ-системы При заданных параметрах адаптивной RQ-системы определим значения пропускной способности S2 и величины y . Пусть значения параметров будут определены в виде ц = 1, Р = 1, а значения матриц в виде (16). Решая относительно S2 и y систему (13) получим следующие численные результаты (табл. 2). Таблица 2 Значения величин S2 и у при различных а а 0,2 0,4 0,6 0,8 1 2 3,768 5 10 100 S2 0,167 0,286 0,375 0,444 0,5 0,667 0,790 0,833 0,909 0,99 Y 0,036 0,121 0,236 0,369 0,516 1,355 3 4,187 9,105 99,01 По данным табл. 2 можно сделать вывод, что при увеличении а/р значение пропускной способности S2 увеличивается, при этом значительно увеличивается и значение величины Y . В табл. 3 при а = 3,768 пропускная способность адаптивной RQ-системы S2 = 0.790 и у = 3, что соответствует пропускной способности динамической RQ-системы S1 = 0,790 при у = 3, что подтверждает асимптотическую эквивалентность адаптивной и динамической RQ-систем с входящим MMPP-потоком заявок. Заключение Вв данной статье проведены исследования динамической и адаптивной RQ-системы с входящим ММРР-потоком заявок методом асимптотического анализа в условии большой загрузки. В результате исследования динамической RQ-системы получены распределение вероятностей числа заявок в ИПВ p(i), уравнение (8) для нахождения пропускной способности S1. При исследовании адаптивной RQ-системы получена система уравнений (13) для нахождения пропускной способности S2 и значения величины y . Было показано, что S1 и S2 совпадают. Далее все полученные аналитические результаты были представлены численно. Также было показано равенство пропускных способностей S1 и S2 при заданных параметрах.

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