Spectral solution for a delay system with hyper-Erlang distributions

Full Text

Введение

Для моделирования трафика современных сетей телекоммуникаций широко используются системы G/G/1 при частных законах распределений, т. к. не существует решения для таких систем в конечном виде для общего случая. Для исследования таких систем используют метод спектрального разложения решения интегрального уравнения Линдли, который наиболее доступно представлен в [1]. В русскоязычной научной литературе аналогом этого метода является метод факторизации с использованием характеристических функций [2].

Настоящая статья посвящена анализу СМО HE2/HE2/1 со сдвинутыми вправо от нулевой точки гиперэрланговскими (HE2) входными распределениями второго порядка и является продолжением исследований [3–6]. В результате этого будем иметь новую СМО с запаздыванием во времени, которую обозначим через ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$ в отличие от обычной системы HE2/HE2/1, рассмотренной в [5].

В общем случае гиперэрланговский закон распределения порядка R задается плотностью 

$f\left(t\right)=\left\{\begin{array}{cc}\sum _i^R{\alpha }_i\frac{k_i{\lambda }_i{\left(k_i{\lambda }_{i}t\right)}^{k_i-1}}{(k_i-1)!}{e}^{-k_i{\lambda }_{i}t},& t>0;\\ \mathrm{0,}& t\le \mathrm{0,}\end{array}\right.$

$\sum _{i=1}^R{\alpha }_i=1$

и обозначается HE_R [1]. Гиперэрланговское распределение представляет собой вероятностную смесь нормированных распределений Эрланга порядка k с функцией плотности вида

$f_k\left(t\right)=\frac{k\lambda {\left(k\lambda t\right)}^{k-1}}{(k-1)!}{e}^{-k\lambda t}$

и является наиболее общим распределением неотрицательных непрерывных случайных величин, поскольку имеет коэффициент вариации  в интервале от 0 до ∞ [8].

В данной работе мы ограничимся гиперэрланговским распределением второго порядка при $k_i=2$ с функцией плотности

$f\left(t\right)=4p{\lambda }_1^{2}t{e}^{-2{\lambda }_{1}t}+4\left(1-p\right){\lambda }_2^{2}t{e}^{-2{\lambda }_{2}t}$

в связи с тем, что при $k_i\ge 3$ дальнейшие выкладки становятся чрезвычайно трудоемкими.

Для системы ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$ интервалы поступлений и времени обслуживания описываются функциями плотностей сдвинутых вправо от нулевой точки гирерэрланговских законов распределений второго порядка:

$a\left(t\right)=4p{\lambda }_1^2(t-t_0)e^{-2{\lambda }_1(t-t_0)}+$

$+4\left(1-p\right){\lambda }_2^2(t-t_0)e^{-2{\lambda }_2(t-t_0)},$ (1)

$b\left(t\right)=4q{\mu }_1^2(t-t_0)e^{-2{\mu }_1(t-t_0)}+$

$+4\left(1-q\right){\mu }_2^2(t-t_0)e^{-2{\mu }_2(t-t_0)},$ (2)

где $t_0\ge 0$ – параметр сдвига закона распределения.

Кроме метода спектрального решения в статье использован опыт аппроксимации законов распределений [7–12]. Результаты современных исследований по системам массового обслуживания приведены в работах [13–15].

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

В статье ставится задача нахождения решения для задержки требований в очереди в СМО ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1.}$ Вкратце решение интегрального уравнения Линдли методом спектрального разложения состоит в нахождении для выражения

$A^{*}(-s)\cdot B^{*}\left(s\right)-1= \frac{{\psi }_{+}\left(s\right)}{{\psi }_{-}\left(s\right)}$

представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Здесь $A^{*}\left(s\right)$ и $B^{*}\left(s\right)$ соответственно, преобразования Лапласа функций плотности распределения интервалов входного потока $a\left(t\right)$ и времени обслуживания $b\left(t\right), {\psi }_{+}\left(s\right) и {\psi }_{-}\left(s\right)$ компоненты спектрального разложения – некоторые рациональные функции от s, которые можно разложить на множители.

Преобразования Лапласа функций (1) и (2) будут соответственно:

$A^{*}\left(s\right)=\left[p{\left(\frac{2{\lambda }_1}{2{\lambda }_1+s}\right)}^2+\left(1-p\right){\left(\frac{2{\lambda }_2}{2{\lambda }_2+s}\right)}^2\right]e^{-t_{0}s};$

$B^{*}\left(s\right)=\left[q{\left(\frac{2{\mu }_1}{2{\mu }_1+s}\right)}^2+\left(1-q\right){\left(\frac{2{\mu }_2}{2{\mu }_2+s}\right)}^2\right]e^{-t_{0}s}.$

Тогда спектральное разложение решения интегрального уравнения Линдли для рассматриваемой системы $A^{*}(-s)\cdot B^{*}\left(s\right)-1= \frac{{\psi }_{+}\left(s\right)}{{\psi }_{-}\left(s\right)}$ примет вид

$\frac{{\psi }_{+}\left(s\right)}{{\psi }_{-}\left(s\right)}=\left[p{\left(\frac{2{\lambda }_1}{2{\lambda }_1-s}\right)}^2+\left(1-p\right){\left(\frac{2{\lambda }_2}{2{\lambda }_2-s}\right)}^2\right]e^{t_{0}s}\times$

$\times \left[q{\left(\frac{2{\mu }_1}{2{\mu }_1+s}\right)}^2+\left(1-q\right){\left(\frac{2{\mu }_2}{2{\mu }_2+s}\right)}^2\right]e^{-t_{0}s}-1=$

$=\left[p{\left(\frac{2{\lambda }_1}{2{\lambda }_1-s}\right)}^2+\left(1-p\right){\left(\frac{2{\lambda }_2}{2{\lambda }_2-s}\right)}^2\right]\times$

$\times \left[q{\left(\frac{2{\mu }_1}{2{\mu }_1+s}\right)}^2+\left(1-q\right){\left(\frac{2{\mu }_2}{2{\mu }_2+s}\right)}^2\right]-1.$ (3)

Выражение (3) получено на основании теоремы о запаздывании в теории преобразования Лапласа. Здесь показатели степени у экспонент с противоположными знаками в спектральном разложении обнуляются, и таким образом операция сдвига во времени нивелируется. Следовательно спектральные разложения решения интегрального уравнения Линдли для системы со сдвинутыми распределениями ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$ и для обычной системы HE2/HE2/1 будут идентичными. Тогда мы можем использовать результаты, полученные в [5] для обычной системы HE2/HE2/1, и сразу записать компоненты спектрального разложения, не повторяя выкладки в [5]:

${\psi }_{+}\left(s\right)=\frac{s(s+s_1)(s+s_2)(s+s_3)(s+s_4)}{\left[{(s+2{\mu }_1)}^2{(s+2{\mu }_2)}^2\right]},$

${\psi }_{-}\left(s\right)=-\frac{{(2{\lambda }_1-s)}^2{(2{\lambda }_2-s)}^2}{(s-s_5)(s-s_6)(s-s_7)}.$ (4)

В выражениях (4) $-s_1, -s_2, -s_3, -s_4$ – корни многочлена (5) седьмой степени с отрицательными вещественными частями, а $s_5, s_6, s_7$ – корни с положительными вещественными частями. Многочлен в числителе разложения (3), содержащий 92 слагаемых после приведения подобных членов, имеет вид

$s^7-c_6{s}^6-c_5{s}^5-c_4{s}^4-c_3{s}^3-c_2{s}^2-c_{1}s-c_0,$ (5)

и собран с помощью символьных операций Mathcad. Его коэффициенты:

$$\begin{gathered} c_0=a_0{b}_1-a_1{b}_0-256{\lambda }_1{\lambda }_2{\mu }_1{\mu }_2\times \\ \times \left[{\lambda }_1{\lambda }_2\right({\mu }_1+{\mu }_2)-{\mu }_1{\mu }_2({\lambda }_1+{\lambda }_2\left)\right], \\ {c}_1=a_0{b}_2-a_1{b}_1+a_2{b}_0-64[{\lambda }_1^2{\lambda }_2^2\left({\mu }_1^2+{\mu }_2^2\right)+ \\ +{\mu }_1^2{\mu }_2^2\left({\lambda }_1^2+{\lambda }_2^2\right)]-256{\lambda }_1{\lambda }_2{\mu }_1{\mu }_2\times \\ \times ({\lambda }_1{\lambda }_2-{\lambda }_1{\mu }_1-{\lambda }_1{\mu }_2-{\lambda }_2{\mu }_1-{\lambda }_2{\mu }_2+{\mu }_1{\mu }_2), \\ {c}_2=a_2{b}_1-a_1{b}_2-64\left\{\right[{\lambda }_1^2{\lambda }_2^2+{\mu }_1{\mu }_2({\lambda }_1^2+{\lambda }_2^2)]\times \\ \times ({\mu }_1+{\mu }_2)-({\lambda }_1^2{\lambda }_2+{\lambda }_1^{}{\lambda }_2^2\left)\right({\mu }_1^2+{\mu }_2^2)+ \\ +{\mu }_1^2{\mu }_2^2({\lambda }_1+{\lambda }_2\left)\right]\}+256{\lambda }_1{\lambda }_2{\mu }_1{\mu }_2({\lambda }_1+{\lambda }_2-{\mu }_1-{\mu }_2), \end{gathered}$$

$$\begin{gathered} c_3=a_2{b}_2-16[{\lambda }_1^2{\lambda }_2^2+{\mu }_1^2{\mu }_2^2+({\lambda }_1^2+{\lambda }_2^2\left)\right({\mu }_1^2+{\mu }_2^2\left)\right]+ \\ +64\left[\right({\lambda }_1+{\lambda }_2\left)\right({\mu }_1+{\mu }_2\left)\right({\lambda }_1{\lambda }_2+{\mu }_1{\mu }_2)- \\ -{\lambda }_1{\lambda }_2({\mu }_1^2+{\mu }_2^2)-{\mu }_1{\mu }_2({\lambda }_1^2+{\lambda }_2^2)-4{\lambda }_1{\lambda }_2{\mu }_1{\mu }_2], \\ {c}_4=16\left[\right({\lambda }_1+{\lambda }_2\left)\right({\lambda }_1{\lambda }_2+4{\mu }_1{\mu }_2)-({\mu }_1+{\mu }_2)\times \\ \times ({\lambda }_1^2+{\lambda }_2^2+4{\lambda }_1{\lambda }_2+{\mu }_1{\mu }_2)+({\lambda }_1+{\lambda }_2\left)\right({\mu }_1^2+{\mu }_2^2\left)\right], \\ {c}_5=16\left[\right({\lambda }_1+{\lambda }_2\left)\right({\mu }_1+{\mu }_2)-{\lambda }_1{\lambda }_2- \\ -{\mu }_1{\mu }_2-4({\lambda }_1^2+{\lambda }_2^2+{\mu }_1^2+{\mu }_2^2\left)\right], \\ {c}_6=4({\lambda }_1+{\lambda }_2-{\mu }_1-{\mu }_2). \end{gathered}$$ (6)

Коэффициенты (6) для сокращения их записи содержат промежуточные параметры:

$a_0=16{\lambda }_1^2{\lambda }_2^2, ····a_1=16{\lambda }_1{\lambda }_2[p{\lambda }_1+\left(1-p\right){\lambda }_2],$

$a_2=4[p{\lambda }_1^2+\left(1-p\right){\lambda }_2^2], ····b_0=16{\mu }_1^2{\mu }_2^2,$

$b_1=16{\mu }_1{\mu }_2[q{\mu }_1+\left(1-q\right){\mu }_2],$

$b_2=4[q{\mu }_1^2+\left(1-q\right){\mu }_2^2].$

И все они зависят от параметров распределений (1) и (2).

Исследование многочлена числителя разложения, нахождение его нулей, а также полюсов разложения – это главное в спектральном решении интегрального уравнения Линдли. Далее по методике спектрального разложения определим постоянную

$$\begin{gathered} K=\underset{s\to 0}{\lim }\frac{{\psi }_{+}\left(s\right)}{s}= \\ =\underset{s\to 0}{\lim }\frac{(s+s_1)(s+s_2)(s+s_3)(s+s_4)}{{(s+2{\mu }_1)}^2{(s+2{\mu }_2)}^2}=\frac{s_1{s}_2{s}_3{s}_4}{16{\mu }_1^2{\mu }_2^2}. \end{gathered}$$

Через нее определяем преобразование Лапласа ФРВ времени ожидания

$$\begin{gathered} {\Phi }_{+}\left(s\right)=\frac{K}{{\psi }_{+}\left(s\right)}= \\ =\frac{s_1{s}_2{s}_3{s}_4{(s+2{\mu }_1)}^2{(s+2{\mu }_2)}^2}{16{\mu }_1^2{\mu }_2^{2}s(s+s_1)(s+s_2)(s+s_3)(s+s_4)}. \end{gathered}$$

Тогда преобразование Лапласа функции плотности времени ожидания будет

$W^{*}\left(s\right)=\frac{s_1{s}_2{s}_3{s}_4{(s+2{\mu }_1)}^2{(s+2{\mu }_2)}^2}{16{\mu }_1^2{\mu }_2^2(s+s_1)(s+s_2)(s+s_3)(s+s_4)},$ (7)

а его производная со знаком минус в т. $s=0$ дает среднее время ожидания ${\left.-\frac{dW*\left(s\right)}{ds}\right|}_{s=0}=\frac{1}{s_1}+\frac{1}{s_2}+\frac{1}{s_3}+\frac{1}{s_4}-\frac{1}{{\mu }_1}-\frac{1}{{\mu }_2}.$

Окончательно, среднее время ожидания требований в очереди будет выражаться формулой

$\overline{W}=\frac{1}{s_1}+\frac{1}{s_2}+\frac{1}{s_3}+\frac{1}{s_4}-\frac{1}{{\mu }_1}-\frac{1}{{\mu }_2}.$ (8)

2. Методика использования расчетной формулы (8)

Для практического использования формулы (8) необходимо определить входящие в нее параметры. Для этого нужно найти неизвестные параметры сдвинутых распределений (1) и (2), а через них – коэффициенты (6) многочлена (5). Неизвестные параметры сдвинутых распределений найдем методом моментов, которые, в свою очередь, определяем с помощью преобразований Лапласа функций (1) и (2). Первые два начальных момента распределения (1) имеют вид

$$\begin{gathered} {\overline{\tau }}_{\lambda }=p{\lambda }_1^{-1}+(1-p){\lambda }_2^{-1}+t_0, \\ \overline{{\tau }_{\lambda }^2}=t_0^2+2t_0[\frac{p}{{\lambda }_1}+\frac{(1-p)}{{\lambda }_2}]+\frac{3p}{2{\lambda }_1^2}+\frac{3(1-p)}{2{\lambda }_2^2}. \end{gathered}$$ (9)

Через них найдем квадрат коэффициента вариации

$c_{\lambda }^2=\frac{{\lambda }_1^2-2p{\lambda }_2({\lambda }_1-{\lambda }_2)+p(1-2p){({\lambda }_1-{\lambda }_2)}^2}{2{[t_0{\lambda }_1{\lambda }_2-p({\lambda }_1-{\lambda }_2)+{\lambda }_1]}^2}.$ (10)

Аналогично для распределения (2) запишем

$$\begin{gathered} {\overline{\tau }}_{\mu }=q{\mu }_1^{-1}+(1-q){\mu }_2^{-1}+t_0, \\ \overline{{\tau }_{\mu }^2}=t_0^2+2t_0[\frac{q}{{\mu }_1}+\frac{(1-q)}{{\mu }_2}]+\frac{3q}{2{\mu }_1^2}+\frac{3(1-q)}{2{\mu }_2^2}, \end{gathered}$$ (11)

$c_{\mu }^2=\frac{{\mu }_1^2-2q{\mu }_2({\mu }_1-{\mu }_2)+q(1-2q){({\mu }_1-{\mu }_2)}^2}{2{[t_0{\mu }_1{\mu }_2-q({\mu }_1-{\mu }_2)+{\mu }_1]}^2}.$ (12)

Неизвестные параметры ${\lambda }_1, {\lambda }_2, p, {\mu }_1, {\mu }_2,$q для сдвинутых распределений (1) и (2) определим из уравнений моментов (9)–(12) тем же способом, как они в [5] найдены для обычных распределений. Для этого положим

${\lambda }_1=\frac{2p}{({\overline{\tau }}_{\lambda }-t_0)}, ····{\lambda }_2=\frac{2(1-p)}{({\overline{\tau }}_{\lambda }-t_0)},$

и после их подстановки в (10) получим уравнение 4-й степени относительно p, и после исключения тривиальных решений p = 0, p = 1 остается квадратное уравнение, корни которого равны

$p=\frac{1}{2}\pm \sqrt{\frac{1}{4}-\frac{3{({\overline{\tau }}_{\lambda }-t_0)}^2}{8[{({\overline{\tau }}_{\lambda }-t_0)}^2+c_{\lambda }^2{\overline{\tau }}_{\lambda }^2]}}.$

Аналогично для распределения (2):

${\mu }_1=\frac{2q}{({\overline{\tau }}_{\mu }-t_0)}, ····{\mu }_2=\frac{2(1-q)}{({\overline{\tau }}_{\mu }-t_0)},$

$q=\frac{1}{2}\pm \sqrt{\frac{1}{4}-\frac{3{({\overline{\tau }}_{\mu }-t_0)}^2}{8[{({\overline{\tau }}_{\mu }-t_0)}^2+c_{\mu }^2{\overline{\tau }}_{\mu }^2]}}.$

Выражения для вероятностей p и q определяют область применимости системы ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$ через коэффициенты вариаций

$c_{\lambda }\ge 1-\frac{t_0}{{\overline{\tau }}_{\lambda }},····c_{\mu }\ge \frac{1}{\sqrt{2}}(1-\frac{t_0}{{\overline{\tau }}_{\mu }})$

при $0<t_0<{\overline{\tau }}_{\mu }.$

Таким образом, алгоритм расчета среднего времени ожидания при заданных входных параметрах ${\overline{\tau }}_{\lambda }, {\overline{\tau }}_{\mu }, c_{\lambda }, c_{\mu }, t_0$ сводится к последовательному решению уравнений (9)–(12) для нахождения параметров распределений (1) и (2) ${\lambda }_1, {\lambda }_2,$p, ${\mu }_1, {\mu }_2,$ q. Далее определяем коэффициенты многочлена (6) и находим нужные корни с отрицательными вещественными частями $-s_1, -s_2, -s_3, -s_4,$ а после применяем формулу (8).

3. Результаты вычислительных экспериментов

В таблице приведены данные расчетов для системы  для случаев малой, средней и высокой нагрузки $\rho =\mathrm{0,1};$ 0,5; 0,9; при фиксированном значении $c_{\lambda }=c_{\mu }=2$ для обычной системы HE2/HE2/1. Заметим, что обычная система HE2/HE2/1 применима при $c_{\lambda }\ge 1/\sqrt{2}$ и $c_{\mu }\ge 1/\sqrt{2},$ а система ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$ – при $c_{\lambda }>0$ и $c_{\mu }>0.$ Таким образом, система ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$ применима для широкого диапазона изменения параметров, чем обычная система HE2/HE2/1 и расширяет ее возможности.

 

Таблица. Результаты экспериментов для СМО ${\mathbf{\text{HE}}}_{\mathbf{\text{2}}}^{\mathbf{-}}{\mathbf{\text{/HE}}}_{\mathbf{2}}^{\mathbf{-}}\mathbf{\text{/1}}$ при ${\mathit{c}}_{\mathbf{\lambda }}\mathbf{=}{\mathit{c}}_{\mathbf{\mu }}\mathbf{=}\mathbf{2}$ для обычной СМО НE2/НE2/1

Table. Results of experiments for QS ${\mathbf{\text{HE}}}_{\mathbf{\text{2}}}^{\mathbf{-}}{\mathbf{\text{/HE}}}_{\mathbf{2}}^{\mathbf{-}}\mathbf{\text{/1}}$ at ${\mathit{c}}_{\mathbf{\lambda }}\mathbf{=}{\mathit{c}}_{\mathbf{\mu }}\mathbf{=}\mathbf{2}$ for ordinary QS НE2/НE2/1

Входные параметры				Среднее время ожидания
$\rho$	${с}_{\lambda }$	${с}_{\mu }$	t0	для СМО ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$	для СМО НE2/НE2/1
0,1	1,999	1,99	0,01	0,33	0,34
	1,99	1,90	0,1	0,30
	1,95	1,50	0,5	0,17
	1,901	1,01	0,99	0,06
0,5	1,995	1,99	0,01	3,93	3,98
	1,95	1,90	0,1	3,51
	1,75	1,50	0,5	1,91
	1,505	1,01	0,99	0,53
0,9	1,991	1,99	0,01	35,84	36,21
	1,91	1,90	0,1	32,53
	1,55	1,50	0,5	19,33
	1,109	1,01	0,99	4,87

 

В правой колонке таблицы для сравнения приведены результаты для обычной системы HE2/HE2/1. Коэффициент загрузки в данном случае определяется отношением средних интервалов $\rho ={\overline{\tau }}_{\mu }/{\overline{\tau }}_{\lambda }.$ Расчеты, приведенные в таблице, проведены для удобства для нормированного времени обслуживания ${\overline{\tau }}_{\mu }=1.$

Заключение

Таким образом, по результатам работы можно сделать следующие выводы.

Операция сдвига во времени уменьшает коэффициенты вариаций интервала между поступлениями и времени обслуживания требований. В связи с тем что среднее время ожидания в системе G/G/1 связано с коэффициентами вариаций интервалов поступления и обслуживания квадратичной зависимостью, среднее время ожидания в системе с запаздыванием будет многократно меньше, чем в обычной системе при одинаковом коэффициенте загрузки. Например, для системы ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$ при загрузке $\rho =\mathrm{0,9}$ и параметре сдвига $t_0=\mathrm{0,99,}$ коэффициент вариации интервалов поступления $c_{\lambda }$ уменьшается с 2 для обычной системы до 1,109, коэффициент вариации времени обслуживания $c_{\mu }$ снижается с 2 до 1,01, а время ожидания уменьшается с 36,21 единицы времени для обычной системы до 4,87 единицы времени для системы с запаздыванием. Таким образом, имеем многократное уменьшение средней задержки в очереди.

С уменьшением значения параметра $t_0$ среднее время ожидания в системе ${\text{HE}}_{\text{2}}^{-}{\text{/HE}}_2^{-}\text{/1}$ стремится к среднему времени ожидания в обычной системе НE2/НE2/1. Это полностью подтверждает адекватность построенной математической модели массового обслуживания.

Основным преимуществом системы со сдвинутыми распределениями является расширение диапазона применимости по сравнению с обычной СМО.

About the authors

Veniamin N. Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru

Doctor of Technical Sciences, professor, head of the Department of Software and Management in Technical Systems

Russian Federation, 23, L. Tolstoy Street, Samara, 443010

Nadezhda F. Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Author for correspondence.
Email: bakhareva-nf@psuti.ru

Doctor of Technical Sciences, professor, head of the Department of Informatics and Computer Engineering

Russian Federation, 23, L. Tolstoy Street, Samara, 443010

References

Supplementary files