Исследование RQ-систем методом асимптотических семиинвариантов

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

2010 Управление, вычислительная техника и информатика № 3

УДК 519.872

А.А. Назаров, И.А. Семенова ИССЛЕДОВАНИЕ RQ-СИСТЕМ МЕТОДОМ АСИМПТОТИЧЕСКИХ СЕМИИНВАРИАНТОВ

В работе рассматривается RQ-система (Retrial Queue), то есть однолинейная система массового обслуживания с источником повторных вызовов. Исследование данной системы проводится методом асимптотических семиинвариантов с использованием теории характеристических функций. Затем проводится численный анализ RQ-системы и определяется область применимости асимптотических результатов к допредельной ситуации.

Ключевые слова: однолинейные RQ-системы, асимптотический анализ, источник повторных вызовов.

За последние годы выявилась необходимость разработки методов исследования RQ-систем. В частности, стремление максимально использовать возможности современных вычислительных машин, систем связи, технологического оборудования приводит к своеобразным и интересным новым задачам в теории RQ-систем.

В теории массового обслуживания аналитическое решение обладает рядом положительных качеств: оно не привязано к определенным числовым значениям параметров потока и системы обслуживания, позволяет находить оптимальные решения и делать общие заключения. Однако во многих случаях аналитическое решение получить затруднительно, поскольку задача настолько сложна, что решение составленных уравнений, к которым сводится задача, представляет собой практически неразрешимую задачу [1, с. 249]. Альтернативным подходом является применение метода асимптотических семиинвариантов для исследования таких задач [2, т. 13, с. 88].

1. Постановка задачи

Рассмотрим RQ-систему, то есть однолинейную систему массового обслуживания с источником повторных вызовов (ИПВ), на вход которой поступает простейший поток заявок с интенсивностью X. Считается, что требование, заставшее прибор свободным, занимает его для обслуживания в течение случайного времени, распределенного по экспоненциальному закону с параметром д. Если прибор занят, то поступившая заявка переходит в источник повторных вызовов, где осуществляет случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром с. Из ИПВ после случайной задержки заявка вновь обращается к прибору с повторной попыткой его захвата. Если прибор свободен, то заявка из ИПВ занимает его на случайное время обслуживания, если же он занят, то заявка мгновенно возвращается в источник повторных вызовов для реализации следующей задержки случайной продолжительности [3, с. 272]. Необходимо найти распределение вероятностей числа заявок в источнике повторных вызовов.

Пусть /(0 - число заявок в ИПВ, а /(/) - определяет состояние прибора следующим образом:

/ ( ) _ (0 если прибор свободен,

(1, если прибор занят.

Обозначим

Р{I(/) _ I, /(/) _ /} _ Р(I,/,^

вероятность того, что прибор в момент времени t находится в состоянии I и в источнике повторных вызовов находится / заявок. Процесс {/(^,/^)} изменения во времени состояний описанной системы является марковским.

Для распределения вероятностей Р(/,/,0 состояний {/,/} рассматриваемой Я^-системы дифференциальные уравнения Колмогорова [4, с. 22], имеют вид

дР

< дt

дРд1уt) _-(Х + ц)Р(1,/,t) + ХР(0,/,t) + о(/ +1 )Р(0,/ +1,t) + ХР(1,/ -1,t).

2. Метод асимптотических семиинвариантов

Применяя систему (1) для стационарного распределения Р(/,/,0 = Р(1,/), составим систему уравнений, определяющих характеристические функции [5, с. 105]

ад

Н (I, и ) _ £ е/и/Р (I, /) _Р { () _ 1}М { ем‘} \1 (t) _ /} ,

/ _0

где / = л/-Г - мнимая единица.

Получим систему уравнений

-о/ дН(0^ _-ХН (0, и ) + цН (1, и ),

ди

о/е-/и дН (0, и ) _ ХН (0, и ) + (Х ( -1) - ц) Н (1, и ) , ди ' ' ’ '

решение {Н(0,и), Н(1,и)} которой удовлетворяет условию нормировки

Н (0,0) + Н (1,0)_ 1.

Систему (2) будем решать методом асимптотического анализа в условии большой задержки в ИПВ, то есть при условии с^-0.

Для компактной записи вычислений дальнейшие исследования будем проводить в матричном виде [6, с. 83]. Обозначив вектор-строку Н(и)={Н(0,и),Н(1 ,и)}, систему (2) перепишем в виде

о/ Ни) А

ди

(Х + /о)Р(0, /, t) + цР(1,/, t) ,

Н

где Е - единичный вектор-столбец, а равенство (4) - условие нормировки.

Здесь матрицы А (/и) и В(/и) можно записать в виде

А ОиЯ--1 С И^А,

Г-Х Х А *

В(/и)_ /_,И ^ _£— Ву ;

^ ^ ц Х(е /И -1)-|^ ^ V V >

V!

а(°)=('о1 ), 'Ч0 (7), в(0)-(" , *-

-Х ХА __(0 0

ц -ц/ V 10 Х(-1)'

2.1. Асимптотика первого порядка

Для нахождения асимптотики первого порядка обозначим с=е, и в уравнении (3) выполним замены [7, с. 130]

и _еw, Н (и )_ ^ (V, е) .

Тогда уравнение (3) примет вид

/ д-М^ е) А

д^

а равенство (4) запишется следующим образом:

Ъ

Теорема 1. Предельное, при е^0 значение Ъ^мт) решения ^(^е) уравнения (5), удовлетворяющего условию (6), имеет вид

Ъ (^)_ Я • е/ж° , где вектор Я является решением системы

Я

удовлетворяющим условию нормировки

ЯЕ _ 1,

а величина к является решением нелинейного уравнения

Я (В1 +к1 А1) Е _ 0 ,

где вектор Я=Я(К1) зависит от К1 и является решением системы (7), (8).

Доказательство. В задаче (5), (6) выполним предельный переход при е^0, получим систему

.И?14. “ Ъ (V) В0,

1Ъ (0)Е _ 1,

решение -Р^) которой запишем в виде произведения

Ъ

вектора Я, определяемого системой

{Я

(ЯЕ _ 1, ^ ’

и скалярной функции Ф^), вид которой определен равенством (9). Значения величины К1 определим следующим образом.

Сложим все уравнения системы (5), умножив это равенство справа на единичный вектор-столбец Е, получим равенство

/ д-М^ е) А (/еж) Е _ - (ж, е) В (/еж) Е,

в котором разложим матрицы

А(]ем>) _ А0 + /ежАх + О(е2) , В(/еж) _ В0 + /ежВх + О(е2) ,

получим

/ ^ е) /ежА\Е _ - (ж,е) /ежВ1 Е + О (е2 ) .

Выполнив здесь предельный переход при е^0 и подставляя сюда произведение (9), получим нелинейное скалярное уравнение относительно величины К1

Я

где вектор Я=Я(К1) определяется системой (10).

Теорема доказана.

Найденные функции -Цж), служат основой построения асимптотики первого порядка.

Определение. Функцию

кх (и ) = ехр {уи К-}

будем называть асимптотикой первого порядка характеристической функции И(и)=И(0,и)+И(1 ,и) числа заявок ¿(0 в источнике повторных вызов, а величину Кі/с - асимптотическим семиинвариантом первого порядка.

2.2. Асимптотика второго порядка

Для нахождении асимптотики второго порядка в уравнении (3) выполним замену

И (и) = ехр{] ииКі}И2 (и) ,

тогда для вектор-функции И2(и) получим уравнение

СТУ дИ2

ди

решение И2(и) которого удовлетворяет условию

И2

Теперь, в системе (12), (13) обозначим с = є 2 и выполним замены

и = ЕЖ, И2 (и )= ^2 (Ж, є) .

Получим задачу

№Жє) А

дЖ

F2

Теорема 2. Предельное, при е^0 значение F2(w) решения F2(w,e) уравнения (14), удовлетворяющего условию (15), имеет вид

F2 (w) = R • exp [j- K2 j,

где вектор R определен в предыдущей теореме, а величина к2 определяется равенством

к = -{g1

K2 = g

в котором векторы g и g1 являются произвольными частными решениями следующих систем уравнений:

g (B0 +K1A0 ) + RA0 = 0 ,

g1 (B0 + K1A0 ) + R (B1 + K1A1 ) = 0 •

Доказательство теоремы выполним в три этапа [9, с. 130].

Этап 1. В задаче (14), (15) выполним предельный переход при е^0, получим систему

р2 (w)(B0 + K1 Л ) = °

к (0) E = 1,

решение F2(w) которой запишем в виде произведения

F (w)=r°! (w)=R •exp P\~i~K 2 j, (

где вектор R определен системой (10), а значение величины к2 определим ниже. Этап 2. Решение F2(w,e) системы (14) запишем в виде разложения

F2 ( ^ e) = R + jewf (w)} Ф2 (w) + 0 (e2 ) =

=<*+f <«>

которое подставим в систему (14), получим равенство

jej2 wk2 RA (jew) = {R + jewf (w)} {B (jew) + кA (jew )} + 0 (e2 ) • Подставляя сюда разложение матриц A (jew) и B(jew):

A (jew) = A0 + jewA1 + 0 (e2 ) ,

B (jew) = B0 + jewB + 0 (e2 ), и принимая во внимание систему R (B0+ kAq^O, запишем равенство

- jewK2RAq = {R + jewf (w)} Ro + к Aq + jew ^ + к A ]} + 0 (e2) =

= jewR (B + K1A1) + jewf (w) ( + K1 Aq ) + 0 (e2 ) , из которого получим систему уравнений

f (w)(B0 +K1 Aq )+R (B1 +K1A1 ) + K2RA0 = 0

относительно вектора /¡(У). Решение Л(м>) этой системы найдем в виде

/

где О1(у) - произвольная скалярная функция, а вектор /1 является решением сис-

темы уравнений

Л

Решение /1 этой системы запишем в виде суммы

Л = £1 +к2Я ,

где векторы £ и £1 являются решениями систем

£ ( В0 +к1 Л ) + ЯА0 = 0

£1

Решение каждой из этих систем содержит слагаемое вида СЯ, которое можно включить в первое слагаемое О1(у)Я разложения (19), поэтому решениями ё и £1 систем (22) могут быть любые частные решения этих неоднородных систем.

Этап 3. Для нахождения значения величины к2 сложим все уравнения системы (14), домножив это равенство справа на единичный вектор Е, получим

А (^у Е = * (у, е) {в (]&М!) + к А (]™)} Е.

дУ

Подставляя сюда разложение матриц АЦгм>) и В(/'єу), разложение (18), а также применяя равенство (11), получим равенство

/1

Тогда, в силу равенства (19) и опять же равенства (11), равенство (23) можно переписать в виде

(О1 (у ) Я + /1)(В1 +к1 А1) Е + -2 Я (В2 +к1 А2 )Е + к2ЯА1Е =

= /1

Подставляя сюда разложение (21), получим

(£1 +К2 ё )( В1 +к1 А1) Е + ^ Я ( В2 +к1 А2 ) Е +к2 ЯА1Е = 0, откуда найдем значение величины к2 в виде

к = -{£1 (В1 +к1 А1 )Е + 2 Я (В2 +К1А2 )Е}

2 £ (В1 +к1 А1 )Е + ЯА1Е ’

совпадающим с (16).

Таким образом, для нахождения величины к2 в разложении (18) достаточно ограничиться постоянными векторами /1, то есть разложение (18) находить в виде * (у,5) = (Я+ /р К2 ) + <°(-),

определяя этот вектор решением системы (20).

Теорема доказана.

Найденные функции *2(у), служат основой построения асимптотики второго порядка.

Определение. Функцию

к ст 2 a J

будем называть асимптотикой второго порядка характеристической функции H(u) числа заявок i(t) в источнике повторных вызовов, а величину к2/с - асимптотическим семиинвариантом второго порядка.

2.3. Асимптотика произвольного порядка

Для нахождении асимптотики произвольного порядка будем применять метод математической индукции. Пусть вектор функция Hn(u) (n>3 Удовлетворяет уравнению

CTj H

du J V=1 v! J

в котором известны все kv при V = 1, 2,..., n - 1.

Пусть с применением уравнения (25) найдено значение величины кп, тогда выполним замену

Hn

I n! a J

и получим уравнение для вектор-функции H-+1(u):

aj dHn&u ^) A

решение Hn+1 (u) этого уравнения удовлетворяет условию

Hn+1

Далее, применяя (26), (27), найдем значение величины k-+1 . Для этого в задаче (26), (27) обозначим с = e n+1 и выполним замены

u = ew, Hn+1(u ) = Fn+1(w, e),

получим

. n dFn+1

jen^±n-----' A (jew) =

dw

=f-+1

Fn+1

Теорема 3. Предельное, при e^-0 значение Fn+1(w) решения Fn+1(w,e) уравнения (28), удовлетворяющего условию (29), имеет вид

Fn+1 (w) = R • eXP{ (/w)1). Kn+1 |(n +1)!

где вектор R определен выше, а величина k-+1 определяется равенством

{n—1 i n-v Л

gn (B1 +K1A1 )E + n+1Z СпЩ Bm+1—v + Z Cn+1—vKk+1 An+1—v—— E + v=1 V k=0 J

n —1

-ik

+«ГГЛ[ВП+1 + Е^+1^+1 А«+1-к]£}/{^

в котором векторы g и gn определяются неоднородными системами линейных алгебраических уравнений

g (Во +к1 Л)+М) = 0

gn (В0 +к1 А0 ) + Ц СП /;ГВп-V + X CÍ-v Кк+1 Ап-V-к '] + Л [" Вп + «£ 1 1+1Ап-Ат 1 = 0 v=1 \ к=0 / \ к=0 /

и произвольными дополнительными условиями, выделяющими частные решения этих систем из множества всех их решений, а векторы определяются разложениями

fv = gv+Kv+1 g , v = \, n - L

Доказательство. Доказательство этой теоремы, как и для асимптотики второго порядка, выполним в три этапа.

Этап 1. В задаче (28) - (29) выполним предельный переход при e^0, получим систему

BFn+1 ( w)(B0 +K1A0 ) = 0, lFn+1 (0) E = 1,

решение Fn+1(w) которой запишем в виде произведения

Fn+1

вектора R, найденного выше и определяемого системой (10), и скалярной функцией 0n+1(w), вид которой определен равенством (31). Значение величины к-+1 будет определено ниже.

Этап 2. Решение Fn+1(w,e) системы (28) запишем в виде разложения

F-+1 (w, e) = |fR + Zjr fv J Ф-+1 (w) + 0 (e-+1) =

= f R + ]| ^ fV J exp K-+1) + 0

которое подставим в систему (28). Получим равенство

wn 4 f „ — (jew )v

jenjn+^ K-+1RA (jew ) = { R + Z^ fv

n! I v=1 V!

j B (jew) + K1A (jew) + Z kv+1 A (jew)) + 0 (e "+) .

Подставляя сюда разложение матриц А

(ІєУ)\ , о(п+1 » п( ™,л = 0'ву)'’

А(У™)= Е^А +0(є”+1 ), В(;Єу) = Е^^, +0(в«+1),

л V! л V!

v=0 л,_ п

получим равенство

Я Е ^ {в,+ІС, к, .А-, }+Е

I ГП / ; ГП Л--Г1 ГП—К / 1 |

,=0 т! I ,=0 ) т=1 т!

{Е С/ [ Bи_v + Е С,-V к,+1 А_-, ]) = 0(є ^) .

Приравнивая здесь коэффициенты при одинаковых степенях є, получим последовательность систем линейных алгебраических уравнений относительно векторов Я и/ :

Я (В0 +к1 А) = 0 ,

/ (В0 +к1А ) + Я (в +к1 А1 + к2А ) = 0 ,

ЕС/V

v=¡ V ,=0 / V ,=0 /

Последнюю систему из (34) для вектора /п запишем в виде

Л (в0 +к1 А0)+П^С^Л (Bn-v +ЕСп^к,+1An—v—k|+Я(вп + Е1 кі+1 Л-,1 + кп+1 ^0 =0

v=¡ V ,=0 / V ,=0 /

и ее решение /п найдем в виде суммы

/п = £п +кп+1 £,

где вектор £ определен системой (22), а вектор £п является решением системы

п-1 Ґ п^ Л Ґ п-1 1

£п (0 + к1 А0 ) + Е Сп лі Bn-v + Е Скп^к,+1 An-v-, I + Я ( вп +Е Сп к+1 Ап-І I = 0 .

v=¡ V ,=0 / V ,=0 /

Этап 3. Для нахождения значения величины кп+1 сложим все уравнения системы (28), домножив это равенство справа на единичный вектор столбец Е. Принимая во внимание разложение (32), и разложение матриц А(]єм>) и В(/ш), получим равенство

п+1 ( /онЛт Г т ( т-V

Е^Т 1 Е С1 ./V I Bm-v + Е ^1+1 А^-к I +

т=1 т! Ь=1 \ к =0 )

+К \Вт + Е Ст Кк+1Ат-к ]} Е + 0

В силу равенств (34) все слагаемые в (36), содержащие величину е в степени меньше чем п+1 равны нулю, поэтому из (36) получим

П+1 А «+1-V ] А П+1 ]

Е Сп+1/ I Bn+1-v + Е Сп+1^Кк+1 An+1-v-к Iе + ЛI Вп+1 +Е С«+1Кк+1 Ап+1-к 1Е = °.

,=0 / V ,=0

(

Приравнивая здесь во внимание равенства A 0E = 0, B0E = 0, можно записать

n i n+1—v Л i n Л

Z Сп+1Ц Bn+1—v + Z Cn+1—vKk+1 An+1—v—k \E + R I Bn+1 + Z Cn+1Kk+1 An+1—k E = Q.

v=1 V k=0 J V k=0 J

Принимая во внимание равенство (35) и выделяя здесь слагаемые, содержащие величину K-+1, получим

{n—1 i n—V Л

g n (B1 +K1A1 )E + -+1Z Cn+1fv I Bm+1—v + Z Cn+1—vKk+1 An+1-v-- E E v=1 V k=0 J

+-+TR|B-+1 + ZCnk+1Kk+1 A-+1—k\E+/{g(B +K1A1 )E + R^E} ,

совпадающее с (30).

Теорема доказана.

Найденные функции Fn+1(w) служат основой построения асимптотики произвольного порядка.

Определение. Функцию

h-+1

будем называть асимптотикой (п+1)-го порядка характеристической функции H(u) числа заявок i(t) в источнике повторных вызовов, а величину кп+1/с - асимптотическим семиинвариантом (п+1)-го порядка.

3. Численный анализ RQ-систем

Для того чтобы получить распределение вероятностей числа заявок в источнике повторных вызовов в допредельной ситуации, необходимо рассмотреть систему уравнений Колмогорова (1) для стационарного распределения P(l,i) [8, с. 76]

g-(X + ia)p (0, i ) + цр (\, i ) = 0,

Решение системы (38) запишем в виде алгоритма численной реализации.

1. i = 0. Сначала найдем решения V

V(1,0)=мт, V(0,1) = (>-^)VI1,0)(M) .

ц a

2. i = 1.

V

ц 2a

3. i = 2.

V

ц 3a

4. Для реализации основного алгоритма, когда i = N, запишем уравнения

V

N a ’ ’ ц

Далее, получаем величину

Р (к, 1) = ^^¡77—) к (к 1),

7v, п)

V п

которая численно определяет двумерное распределение вероятностей Р(к,1). Одномерное маргинальное распределение Р(1), определяемое равенством

Р (I) = Р (0,I) + Р (1,I),

численно решает поставленную задачу нахождения распределения вероятностей числа заявок в источнике повторных вызовов, которое естественно совпадает с Р(1).

4. Область применимости асимптотических результатов к допредельной ситуации

С помощью полученной асимптотики произвольного порядка (37) и обратного преобразования Фурье, запишем асимптотическое распределение вероятностей числа заявок в источнике повторных вызовов [9, с. 107]

1 п

Рп

2п -1

-п

Распределение (39) будем называть асимптотической аппроксимацией п-го порядка допредельного распределения.

Теперь выясним, насколько результаты, полученные с помощью асимптотического анализа, близки к результатам, полученным численно в допредельной ситуации. Для этого найдем расстояние Колмогорова между этими распределениями

Бп = тах

0< т<ад

XРп

і=0 і=0

где Рп(і) - ряд распределения, полученный с помощью асимптотического анализа, а Р(і) - ряд распределения для допредельной ситуации, полученный численным алгоритмом.

Используем заданные значения параметров: Х=0,5; д=1, тогда для различных значений с значения Бп составили

Сравнение асимптотической аппроксимации второго и третьего порядков с допредельным распределением по расстоянию Колмогорова

с 0,1 0,05 0,01 0,005 0,001

б2 0,1601 0,1246 0,0588 0,0416 0,0186

0,1202 0,0997 0,0417 0,0288 0,0120

Очевидно, что с уменьшением значений величины с расстояние Б уменьшается, то есть повышается точность аппроксимации допредельного распределения распределением, полученным методом асимптотического анализа. Более того, точность такой аппроксимации повышается при переходе от асимптотики второго порядка к асимптотике третьего порядка. Полагая приемлемой погрешность аппроксимации, равную значению 0,05 расстояния Колмогорова, можно определить область применимости с < 0,005 для асимптотики второго порядка и с < 0,01 для асимптотики третьего порядка. Очевидно, что здесь вторая область применимости в два раза больше первой.

Заключение

Таким образом, в работе проведено исследование RQ-систем методом асимптотических семиинвариантов. Получены допредельное и асимптотическое распределения вероятностей числа заявок в источнике повторных вызовов. Проведен численный анализ однолинейной RQ-системы с простейшим входящим потоком.

В результате большого количества численных экспериментов можно сделать вывод о том, что применение метода асимптотического анализа к исследованию RQ-систем целесообразно при с < 0,005, что позволяет находить допредельное распределение вероятностей числа заявок в источнике повторных вызовов, применяя асимптотическую аппроксимацию второго и третьего порядка.

ЛИТЕРАТУРА

1. Artalejo J.R., Go’mez-Corral A. Retrial Queueing Systems. A Computational Approach. // Springer Verlag Berlin Heidelberg. 2008. 318 p.

2. Назаров А.А., Моисеева С.П., Морозова А.С. Исследования СМО с повторным обращением и неограниченным числом обслуживающих приборов методом предельной декомпозиции // Вычислительные технологии. 2008. Т. 13. Специальный выпуск. С. 88 - 92.

3. Назаров А.А., Семенова И.А. Сравнение асимптотических и допредельных результатов анализа системы М/М/1/ИПВ // Сб. науч. статей. Минск, 2010. Вып. 3. С. 272 - 277.

4. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 3-е изд., испр. и доп. М.: КомКнига, 2005. 408 с.

5. Драшева В.И. Однолинейная система массового обслуживания с конечным источником и повторными вызовами // Проблемы передачи информации. Вып. 3. 1994. С. 104 - 111.

6. Назаров А.А., Моисеева С.П. Метод асимптотического анализа в теории массового обслуживания. Томск: Изд-во НТЛ, 2006. 112 с.

7. Цой С.А. Применение характеристических функций для асимптотического исследования сетей связи со статистическими протоколами случайного множества доступа // Вестник ТГУ. 2006. № 293. С.129 - 134.

8. Назаров А.А., Терпугов А.Ф. Теория массового обслуживания: учеб. пособие. Томск: Изд-во НТЛ, 2004. 228 с.

9. Назаров А.А., Судыко Е.А. Метод асимптотических семиинвариантов для исследования математической модели сети случайного доступа // Проблемы передачи информации. 2010. № 1. С. 94 - 111.

Назаров Анатолий Андреевич Семенова Инна Анатольевна Томский государственный университет,

E-mail: anazarov@fpmk.tsu.ru; inna_ac@mail.ru Поступила в редакцию 30 марта 2010 г.