Использование модельных распределений в задаче анализа систем массового обслуживания с коррелированными заявками

Re ц > 0,

2^x

Ф(x) = —;= Je^t dt ^ П 0

( ^ х \\^ц ;

– интеграл вероятностей, для

f" (x) = T ] ej exp I ^^ (jur6k ) du 2n                  k!

-to                 k —1

и f (y) можно получить:

f (У) — 2 (1+ A)ey2 X

x

y -\Ie’1(y 1

+¹Ae^{2 y 2}

-1)

a           a1 -фН IIA     A V2 ))

+

y ~ej^e 2 (2 y2 - 1) (1 -ф( y))

Рисунок 1. Распределение f(y)

—

8 Л e - -2

П Чг 2 з>,fi у У у — e 3 (У ) 1 — Ф

У 3        4 I I Vs JJ

На рисунке 1 построена плотность f (у) для у = ;3 — у4 из выражения (5) с учетом того, что R= R₀₁ = 0.63 (как соседние элементы) и А = R ^’j/2.592 = 0.243.

Из выражения (5) следует, что для первых трех слагаемых будут получены примерно такие же, как на рисунке 1, распределения, отличающиеся использованием в расчетах других коэффициентов корреляции.

Аппроксимация произвольного распределения модельным распределением

В общем случае для анализа распределений слагаемых в выражении (5) при использовании произвольных распределений для последовательности исходных элементов уi можно предложить подход, основанный на аппроксимации неизвестной плотности «модельным» распределением [9].

Суть использования данного подхода для построения модельного распределения заключается в следующем. Если случайная величина формируется посредством сложных функциональных связей с некоторой совокупностью других случайных величин, то нахождение плотности вероятностей рассматриваемой случайной величины аналитическими методами, как правило, является чрезвычайно сложной, а чаще всего практически не решаемой задачей.

С другой стороны, вычисление кумулянтов (и моментов) при различных функциональных преобразованиях случайных величин осуществляется гораздо проще. По найденному конечному набору кумулянтов всегда может быть вос- произведена с определенной погрешностью «модельная» плотность вероятностей, записываемая в виде:

?       n^(hA^k

fn (x) = — Je" jux exp ^5 (j^ 3 du, (10)

2пД        I t1 k!

где n - порядок модельного распределения, 9_k -k-й кумулянт искомого распределения f (x).

Принципиальным недостатком данного подхода, как указано в [9; 10], является то, что, строго говоря, выражение вида (10) не является вероятностным распределением, т. к. полученная модельная плотность на некотором множестве значений аргумента может принимать отрицательные значения.

Каждое слагаемое в выражении (5) можно представить в виде:

Пm = km (Yi — Y J ), m = 1, N/2, и, соответственно, кумулянты порядка n распределения каждого nm определяются как:

n

9П^{1 m}) = km 5 cn (—1) l 9n——Y;,*.          (11)

I=0

В формуле (11) 9n— Yj) - совместный кумулянт порядка (n — l, l), относящийся к случайным величинам Y_i и Y_J, C_n^l - число сочетаний.

При этом все распределения для величин n_m будут иметь одно и то же «модельное» представление, отличающееся только численным значением кумулянтов, которые могут быть вычислены по известным формулам [9–11]. Для кумулянтов второго порядка справедливо:

9V" ■ ’ = km (920* j' — 290;'^Yj⁾+902^Yj ’),

91; i ’"’ = m!?'-'’ — m,"'¹' ml’'⁾,             (12)

920yj) = m 2 ’■)-( m;’))2.

В (12) именно кумулянт УЦ'i^Yj) определяет корреляционные связи величин yi и yj. Все совместные кумулянты находятся через совместные моменты, которые, в свою очередь, могут быть определены только при известном двумерном распределении для совокупности уi, уj. Выражение для вычисления совместных моментов имеет вид:

to to mk = mkz iYj) = JJ xkxif^Yy (Xi, x 2) dx1 dx 2 •

Для кумулянтов четвертого порядка можно записать [10; 11]:

А ⁽П m )               ^(Yi ^Yj)          ^(Yi ^Yj)

У4     km (У40     4У31   +

⁽YiYj)           ⁽YiYj)         ⁽YiYj)

+ 6У22   - 4У13   + У04

04, j) = m 4Yi) — 3( m 2Yi))2 — 4 mJY i) m 3

+12(m₁^(Yi) )²m2^Yi) - 6(m₁^(Yi) )⁴,

(k +1) и (1 +1) - четные,

4A

^{1 +}

0,5

V 22

(k +1) и (1 +1) - нечетные,

k !!•

k+1

x

x

1 + 4A

kk+1   1+1   r-

V 2 ²• 2²  • V2

0,5

+

2²• V2

0,25

V2

J

⁽YiYj)

^У31

= m

⁽YiYj) 31

-

3m

⁽YiYj)

m

⁽YiYj)

-

m

⁽YiYj)

m

⁽YiYj)

-

-     (YY j       j) + 6m(Y * Y,)m(YiY,)m( T,’j) + m 20  m11   + m10  m 01  m 20   +

+ 6(m™j))²Щ ■^Yj) -6(m™j))³m,

O'./j) = m'■j) - 4У21^ъ)У^⁷j) - (У2^YiYj ))²-

- 2(y(^Y-^Yj))²- 2У2^ьъ)(У(^yi^Yj))²

-

4у1™⁾(у1™⁾)‘ - (У1^т))*

^(Yij _ ™^(Yij ^y21 ^m 21

-

2 m^⁷ j) m^ j)

-

- m m 0У + 2( mjm 0Г^У, m<Y,) _y(^Yi).

Для примера, рассмотренного выше, c двумерной плотностью (9) при коррелированных случайных величинах и при выбранных значениях для распределения Вейбулла X = 1, a = 2, с использованием стандартных интегралов [12]:

to

J x2 ne - px 2 dx = - to

J x²n⁺¹e - ^px 2 dx =

(2 n -1)!!

2(2P)n Pp ’ n!n

, P > 0

2 pn+1P

формулы для вычисления совместных моментов примут вид:

mkl _

[ k!!• l !!-n k.1    1.1^x

2 ²• 2 ²

x

1 + 2A

k+1 l+1

-

k+1

^2 • 2 2

-

¹     +1

l+1

^2 • 2T

,

0,25    1

⁺-(-+1)   2

2 ²J

0,5

k+1

(k +1) - четные, (1 +1) - нечетные.

Теперь для п₄= k4 (y₃ -Y₄) из (6) на основе выражения (14) можно вычислить моменты величины п₄. При А = 0,243 для начальных совместных моментов, через которые вычисляются совместные кумулянты для формирования модельной плотности, можно записать:

m₁₁= 0,992, m₁₃= 1,52, m₂₂= 1,06, m₁₂= 1,19.

Для вышеуказанных значений совместных моментов численным интегрированием была рассчитана модельная плотность вероятностей f ,(nm) (x)      . Расчеты проводились по формуле m=4, n=6

Ito —1         1           1

У2 u²+ У 4 u ⁴--У6 u⁶

f_n (x) =    e ^{2     24    720}    cos uxdu,

П 0

и результат численного интегрирования приведен на рисунке 2.

Расчет модельной плотности

Теперь можно предложить следующую схему расчета искомой модельной плотности для составляющих элементов n_m = k_m(yi -Yj) декорре-лированного блока ^_k, k = 0, N -1:

– посредством инструментального анализа реального трафика yi, i = 1, 2, • • •, определяются его корреляционные свойства и одномерная плотность вероятностей,

– синтезируется двумерная плотность вероятностей трафика yi, i = 1, 2, — , обладающего измеренной корреляционной функцией,

– рассчитываются совместные моменты и кумулянты для коррелированных величин η_m = = km (Yi -Yj), m = 1, N/2, по которым строится их модельная плотность.

Отсчеты nm = km (Yi -Yj) действительно являются коррелированными, в чем легко убедиться простым вычислением корреляции R для ηpηq любых значений р и q из интервала m = 1, N/2.

К примеру:

R_n= k₂k₃ (R, — R. — R^ + Ry у) * 0.

η₂η₃       23 γ₁γ₂       γ₁γ₅       γ₂γ₆       γ₅γ₆

Рассчитать кумулянты суммы величин η_m = = km (Yi — Yj), m = 1, N/2 для построения модельной плотности величин у_k, к = 0, N — 1 можно с использованием процедуры «суммирования по парам» с декорреляцией.

Суть использования данной процедуры состоит в том, чтобы при получении модельного распределения каждого у_k, k = 0, N — 1 сохранить только корреляцию исходных элементов Yi, i = 1, 2, — , не включая в результат дополнительные корреляционные связи элементов η_m = = km (Yi -Yj), обусловленные методом вычислений, а не реальной «физической» корреляцией исходного трафика. Следует отметить, что использование в модельных распределениях совместных кумулянтов порядка выше второго позволяет учесть не только корреляцию (по Пирсону) между элементами любой последовательности, но и уточнить количественное описание истинной зависимости элементов в анализируемой последовательности.

На примере выражения (5) продемонстрируем эту процедуру.

Пусть 51 =П1 + 42 и 52 =n₃+ 44. Статистические свойства, например элементов n1 и n₂, уже учитывают корреляционные связи исходных элементов трафика yi, i = 1, 2, — N, причем модельные распределения вида (10) дают более полное представление о зависимости элементов трафика, чем коэффициенты корреляции, благодаря наличию кумулянтов более высокого порядка, чем 2. Коме того, модельные распределения инвариантны к линейным преобразованиям случайных переменных, а при независимых переменных кумулянты аддитивны.

Рассмотрим кумулянты модельного распределения для 51. Из (12) следует:

о/) =о2р) - 20^2) + 90^2) =

= 92'1) - 20^2) +02^П2).

Так как корреляция определяется кумулянтом 011^2), удалим из последнего выражения слагаемое 201П^1П2). Тогда, очевидно:

02⁵¹) = 02^П1) +02ⁿ2).

Таким образом, кумулянт 02⁵¹) сохранит в себе информацию не только о корреляционных связях элементов yi, i = 1, 2, — N, но и о взаимозависимости этих элементов. Зависимость элементов η₁ и η₂ при этом игнорируется.

Заметим, что последняя операция является вполне допустимой, потому что «разные кумулянты можно рассматривать как некоторые в определенной степени независимые элементы» [9].

Аналогично в выражении для кумулянта четвертого порядка для 51:

0(81) =0(41) - 4034142 ) ₊

+ 60<⁴₂ⁱⁿ2) - 401ⁿ'ⁿ2) +0<ⁿ2)

исключаем элементы, связанные с корреляцией значений 41 и n2, т. е. содержащие 0114142). С учетом формул (13) это приводит к следующим вы- ражениям для составляющих кумулянта 0481) модельного распределения 81:

02Г) = m2П) - m20^1П2)m0П),        (16)

037²) = m32^2) - 3m™)m2™) +

+ 3m^ⁿ2)m0ⁿ1 ⁿ2 )m2^{n n}2 ) - m<ⁿⁿ2 )m3ⁿⁿ2 \

0221^п2) = m<21'¹=) - 2m'у^²)m'^) +

+ 2m^\m<11ⁿ2 ))²- m02)m^) -

• - 2 m^²) m™) + 2 m 02^Лг) (m^²) )²,

а составляющие 04^П1)и 04ⁿ2) вычисляются согласно первой строке формулы (13).

Формулы (16) говорят о том, что после удаления корреляционных связей элементов n1 и П₂ зависимость элементов n1 и П₂ все-таки остается и она может быть учтена совместными моментами. Однако вычисление таких совместных моментов требует знания совместного распределения f (x, у), получить аналитическое выражение которого чрезвычайно сложно.

Ослабление зависимости

Зависимость элементов n1 и п2 можно еще ослабить, если из (16) вообще удалить совмест- ные моменты: mЗ^2)

(П1П2)          (П1П2)          (П1П2)

^m 21   ,   ^m12   ,   ^m 22   •

Дальнейшим упрощением будет служить пред- положение о полной независимости элементов

П_m — k_m(yi -Yj), что приведет к вычислению кумулянтов для суммы n_m в виде:

0^(vk⁾=0⁽ⁿ1⁾ + 0⁽ⁿ2 ⁾₊ ... ₊ 0⁽ⁿN²). n          n         n                 n

Случайная величина 82 — n₃+ П₄ подвергается аналогичной процедуре, а затем для А — 81 +82 все повторяется еще раз с очевидной сменой обозначений. Так может быть определена модельная плотность каждой величины ^_к, к — 0, N -1. В силу независимости всех ^_к, к — 0, N -1 кумулянты распределения их суммы определяются с учетом свойства аддитивности, т. е.

enZvk) = 0n_v,) + en_V2) + ...+en_vN )•

Теперь, для случая обработки блока заявок с некоррелированными интервалами времени между заявками согласно (1) преобразование Лапласа для плотности вероятностей времени ожидания заявки в очереди примет вид:

f⁽⁵) = exp

-

j

X-j(1 -e-^5x)к^(N)(x)dx , (18)

N =1 N 0                     _ где k»(x) = KM.

dx

Аппроксимируем плотность распределения

A(u) в (2) модельным распределением, записан- ным через конечный набор кумулянтов, в виде

-

• (10)    и положим B (у) = 1 - e

  ^py, т. е. будем рассма-

  
  

тривать систему типа G/M/1. Тогда:

к^(N) (x) = j pe-^{p( x+}u) f_n<^N) (u) du = _jr0                           (19)

= p jj e M x+u) exp [Z ]cos zudzdu• n 00

В выражении (19) введено обозначение

I 1 (N) „2 , 1 (N) „4       1     (N) „6 j exp Z — exp —0-, z +--0 z--0 z •

( 2 2      24 ⁴      720 ⁶J

С учетом интеграла [12]:

j e-^px cos(qx + A)dx — 0

для к^(N)(x) получаем:

——i—- (p cos A - q sin A) p²+ q²

j

к^(N)(x) =В- e-^{px п}о

——- exp [Z ] dz•   (20)

p²+ z²

Обозначим интеграл в (20) как Q(p, 0⁽₂^N), 04N), 06N)), тогда:

к^(N) (x) = -^e^Q (p, 02^N), 04^N), 06^N)). n

Интеграл из (18) запишется как:

j (1 - e -^5x) dk^(N)(x) = 0

= PQ(p, 02N), 04N), 06N))—, n x                 ’ 5 + p и окончательно для f (5) будем иметь f ( 5 ) =

5 p

5 + p n

— exp

j

X1 Q(p, 02N', 04N-, 06N¹)

N—1 N где суммирование ограничивается конечным размером выбранного блока N.

В итоге среднее время ожидания заявки в очереди T определится как:

T — - 4/^5)    —¹X1 Q(p, 02^N), 04^N), 06^N) )• (21)

d5 _5—0n N N ^{v              7}

Так, для системы G/M/1, может быть решена задача оценивания среднего времени ожидания заявки в очереди при исходно коррелированном потоке интервалов времени между заявками (с произвольной одномерной плотностью данных интервалов). При этом интеграл Q(p,02n), 04n), 06n)) можно вычислять численно, если полученные значения кумулянтов позволяют это сделать. В противном случае можно ис- пользовать приближенные вычисления, основанные на «методе перевала» [13].

Пример вычислений

Для реализации вычислений по формуле (21) используем полученные выше результаты для коррелированной трафиковой последовательности с выбранными параметрами распределения Вейбулла. Будем предполагать, что корреляционные свойства последовательности величин yi, i = 1, 2, • • • N характеризуются формулой (4).

Проводя вычисления по формулам (12), (13) при N = 8 для n₄= k₄ (Y3 -Y₄), к₄= 0,0975 с учетом R_YY = R₀₁= 0,63 и значений для совместных моментов из (15) можно получить следующие значения кумулянтов для модельного распределения /<^п»\x)| : 02¹⁴) = 0,0014; 04¹⁴) = 0,387.

n=4

Аналогичные вычисления, проведенные для f„^(n,)(x)   , где П1 = k1 (Y0 -Y7), k = 0,49, и ко-

• ⁿ       n= 4

эффициент корреляции R= 0,16, дают значения кумулянтов 02^П1) = 0,1587, 04^П1)= 4,35. То есть слабо коррелированные y₀, Y7 дают более высокое значение четвертого кумулянта и существенно более высокое значение второго кумулянта, чем сильно коррелированные y₃ , Y₄ (соответственно, в 10 и 100 раз).

Аналогично для п₂, П₃ получим: 0*^П2) = = 0,113, 04^п2) = 2,63; 02^П3) = 0,027, 04^П3) = 1,12.

Теперь, предполагая справедливость соотношения (17), для кумулянтов величины ^ запишем 02^V1) = 0,3; 04^V1) = 8,5.

Выберем для ц значение ц = 1. В силу того что среднее значение распределения Вейбулла m₁ при выбранных X = 1, а = 2 равно согласно (8) 0,886 , загрузка р системы будет равна 0,564.

Ограничиваясь при численном вычислении интеграла Q(-) учетом только второго и четвертого кумулянтов, т. е. записывая выражение (21) в виде (для упрощения, принимая N = 1):

T =1 V-т exp I -10(2N) z2 + — 0(N)z4 I dz, nJ0 ц2 + z2     ( 2 2       24 4 J получим для среднего времени ожидания заявки в очереди T = 0, 0726 условных единиц времени.

Заключение

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