An algorithm for measuring the parameters of the generalized second-order Erlang distribution law

Full Text

Введение

Для моделирования входящего потока заявок в задачах телекоммуникации, а также при решении транспортных задач в основном применяется обобщенный закон распределения Эрланга, поскольку при его использовании теоретические результаты хорошо согласуются с эмпирическими [1 – 3]. Ряд авторов утверждает, что с помощью обобщенного закона Эрланга можно аппроксимировать практически любое распределение случайной величины [4, 5]. Данный закон распределения используется в полумарковских цепях, где переходы между состояниями подчиняются непоказательному закону распределения. Такие цепи используются, например, при моделировании радиосвязи [6], а также в модели функционирования информационно-технического средства (ИТС), приведенной в [7]. Решение полумарковской цепи осуществляется путем приведения ее к марковской [8] и дальнейшего решения системы уравнений Колмогорова. При этом необходимо знать интенсивности переходов между состояниями для закона распределения (далее – интенсивности переходов). Однако существует ряд задач, в которых вместо интенсивностей даны средние времена перехода между состояниями полумарковской цепи (далее – средние времена перехода) [7, 9]. С учетом этого решение полумарковской осуществляется в три этапа: нахождение интенсивностей переходов по заданным средним временам; преобразование полумарковской цепи в марковскую, используя полученные интенсивности переходов; решение системы уравнений Колмогорова для полученной марковской цепи. Данный алгоритм реализован в программном комплексе оценки соотношения сил противоборствующих формирований при планировании общевойскового боя «Стронций» для моделирования функционирования ИТС [10]. Одно из требований, предъявляемых в процессе разработки к комплексу – возможность проводить моделирование в режиме времени, близком к реальному. Для этого необходимо провести оптимизацию всех модулей программного комплекса. При этом одним из узких мест является модуль определения интенсивностей переходов. Нахождение интенсивностей осуществляется численно, путем их перебора в целях определения максимума плотности обобщенного закона распределения для заданного среднего времени. При увеличении точности определения интенсивностей повышается длительность такого преобразования. При этом для требуемой точности комплекс не способен моделировать в режиме реального времени. Поэтому требуется получить аналитическое решение задачи определения интенсивностей переходов обобщенного закона распределения Эрланга второго порядка (ОЗРЭ ВП) по известному среднему времени перехода.

Цель работы – разработка алгоритма определения интенсивностей перехода ОЗРЭ ВП по известному среднему времени перехода с минимизацией количества решаемых уравнений численными методами.

Разработка алгоритма определения параметров обобщенного закона распределения Эрланга второго порядка

Существующий алгоритм поиска интенсивностей перехода по заданному среднему времени перехода, используемый в моделирующем комплексе [10], основан на следующем принципе: среднее время перехода будет достигнуто в максимуме плотности распределения ОЗРЭ ВП с искомыми интенсивностями перехода. При этом существующий алгоритм заключается в осуществлении перебора всех значений интенсивностей в заданном диапазоне с заданным шагом. Для каждой пары значений интенсивностей перехода численно находится максимум плотности вероятности. Затем выбирают пару значений с наибольшей плотностью вероятности, соответствующую заданному среднему времени. Блок-схема существующего алгоритма приведена на рис. 1.

 

Рис. 1. Известный алгоритм поиска интенсивностей переходов между состояниями полумарковской цепи по заданному среднему времени перехода

 

Шаг 1. Задают исходные данные.

В качестве исходных данных выступают: $[{\lambda }_1^{\min },{\lambda }_1^{\max }]$, $[{\lambda }_2^{\min },{\lambda }_2^{\max }]$ – интервалы подбора значений первой и второй интенсивности соответственно; ${\lambda }_1^{\text{step}}$, ${\lambda }_{\text{2}}^{\text{step}}$ – шаги подбора значений первой и второй интенсивности соответственно; $[t_{\min },t_{\max }]$ – временной интервал; $t_{\text{step}}$, $t_{\epsilon }$ – шаг и погрешность подбора по времени соответственно; $t_{\text{avg}}$ – среднее время перехода.

Шаг 2. Выбирают значения для интенсивностей перехода ОЗРЭВП из заданного интервала.

Шаг 3. Определяют максимальное значение плотности вероятности $E_i$ для выбранных на предыдущем шаге значений интенсивностей переходов ${\lambda }_1^i,{\lambda }_2^i$ перебором значений времени из заданного интервала с использованием аналитического выражения

$E(t,{\lambda }_1,{\lambda }_2)=-{\lambda }_1{\lambda }_2\frac{{\text{e}}^{-t{\lambda }_1}-{\text{e}}^{-t{\lambda }_2}}{{\lambda }_1-{\lambda }_2}.$ (1)

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

 Шаг 4. Запоминают наибольшее значение максимума плотности вероятности и соответствующие ему значения интенсивностей переходов.

Если все значения интенсивностей переходов из заданного интервала рассмотрены, то перебор завершается, в противном случае – продолжают перебор значений интенсивностей переходов между состояниями.

Для увеличения точности выборки параметров необходимо уменьшать шаг подбора параметров, что приводит к увеличению количества итераций. С увеличением количества итераций возрастает расчетное время. Как следствие, недостатком данного алгоритма является большое время работы. При попытке ускорить алгоритм (увеличить шаг подбора) – теряется точность.

Для предлагаемого алгоритма плотность вероятности ОЗРЭ ВП определяется также выражением (1) [4], после чего при определении максимального значения плотности вероятности закона распределения Эрланга второго порядка необходимо найти производную, приравнять ее нулю и решить полученное уравнение относительно времени

$\frac{\partial E(t,{\lambda }_1,{\lambda }_2)}{\partial t}=0.$ (2)

Рассмотрим решение пошагово. Вычислим производную по времени от плотности вероятности закона распределения

$\frac{\partial E(t,{\lambda }_1,{\lambda }_2)}{\partial t}=\frac{\partial }{\partial t}\left(-{\lambda }_1{\lambda }_2\frac{{\text{e}}^{-t{\lambda }_1}-{\text{e}}^{-t{\lambda }_2}}{{\lambda }_1-{\lambda }_2}\right)=\frac{-{\lambda }_1{\lambda }_2}{{\lambda }_1-{\lambda }_2}\frac{\partial }{\partial t}\left({\text{e}}^{-t{\lambda }_1}-{\text{e}}^{-t{\lambda }_2}\right)=$

$=\frac{-{\lambda }_1{\lambda }_2}{{\lambda }_1-{\lambda }_2}\left(\frac{\partial }{\partial t}\left({\text{e}}^{-t{\lambda }_1}\right)-\frac{\partial }{\partial t}\left({\text{e}}^{-t{\lambda }_2}\right)\right)=\frac{-{\lambda }_1{\lambda }_2}{{\lambda }_1-{\lambda }_2}\left(-{\lambda }_1{\text{e}}^{-t{\lambda }_1}+{\lambda }_2{\text{e}}^{-t{\lambda }_2}\right);$

$\frac{\partial E(t,{\lambda }_1,{\lambda }_2)}{\partial t}=\frac{{\lambda }_1{\lambda }_2}{{\lambda }_1-{\lambda }_2}\left({\lambda }_1{\text{e}}^{-t{\lambda }_1}-{\lambda }_2{\text{e}}^{-t{\lambda }_2}\right)$. (3)

Уравнение (2) с учетом (3) примет вид

${\lambda }_1{\text{e}}^{-t{\lambda }_1}={\lambda }_2{\text{e}}^{-t{\lambda }_2}.$ (4)

Подставим в уравнение (4) известное значение среднего времени перехода между состояниями $t_d^{*}$ и получим:

${\lambda }_1{\text{e}}^{-t_d^{*}{\lambda }_1}={\lambda }_2{\text{e}}^{-t_d^{*}{\lambda }_2}.$ (5)

Затем умножим обе части уравнения (5) на $-t_d^{*}$ и воспользуемся W-функцией Ламберта [11], обладающей свойством $W\left(x{\text{e}}^x\right)=x$:

$-t_d^{*}{\lambda }_1{\text{e}}^{-t_d^{*}{\lambda }_1}=-t_d^{*}{\lambda }_2{\text{e}}^{-t_d^{*}{\lambda }_2};$

$W\left(-t_d^{*}{\lambda }_1{\text{e}}^{-t_d^{*}{\lambda }_1}\right)=W\left(-t_d^{*}{\lambda }_2{\text{e}}^{-t_d^{*}{\lambda }_2}\right);$

$W\left(-t_d^{*}{\lambda }_1{\text{e}}^{-t_d^{*}{\lambda }_1}\right)=-t_d^{*}{\lambda }_2;$

${\lambda }_2=-\frac{1}{t_d^{*}}W\left(-t_d^{*}{\lambda }_1{\text{e}}^{-t_d^{*}{\lambda }_1}\right).$ (6)

Подставим (6) в (1) и получим выражение максимального значения плотности вероятности ОЗРЭВП в виде функции одной переменной

$E_0\left({\lambda }_1\right)=\frac{{\lambda }_1}{t_d^{*}}W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)\frac{{\text{e}}^{-t_d^{*}{\lambda }_1}-{\text{e}}^{W(-{\lambda }_1{t}_d^{*}{e}^{-{\lambda }_1{t}_d^{*}})}}{{\lambda }_1+\frac{1}{t_d^{*}}W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)}.$ (7)

Найдем значение интенсивности перехода ${\lambda }_1$, при котором функция (7) достигает максимума. Для этого решим уравнение (8) относительно ${\lambda }_1$

$\frac{\partial E_0\left({\lambda }_1\right)}{\partial {\lambda }_1}=\mathrm{0,}$ (8)

в котором производная имеет вид

$\frac{\partial E_0\left({\lambda }_1\right)}{\partial {\lambda }_1}=\frac{W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)}{t_d^{*}\left({\lambda }_1+\frac{1}{t_d^{*}}W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)\right)}\times$ 

$\times \left[\left({\text{e}}^{-{\lambda }_1{t}_d^{*}}-{\text{e}}^{W(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}})}\right)\right.\times \left(1-\frac{1}{{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\left(W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)+1\right)}\right)+$

$+{\lambda }_1\left(-t_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}+\frac{{\text{e}}^{W(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}})}}{{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}}\frac{W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)}{W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)+1}\right)-$ (9)

$-\frac{{\lambda }_1}{{\lambda }_1+\frac{1}{t_d^{*}}W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)}\left({\text{e}}^{-{\lambda }_1{t}_d^{*}}-{\text{e}}^{W(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}})}\right)\times$

$\times \left.\left(1-\frac{W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)}{{\lambda }_1{t_d^{*}}^2{\text{e}}^{-{\lambda }_1{t}_d^{*}}\left(W\left(-{\lambda }_1{t}_d^{*}{\text{e}}^{-{\lambda }_1{t}_d^{*}}\right)+1\right)}\right)\right].$

Решим (8) относительно ${\lambda }_1$ любым известным численным методом, например, методом половинного деления [12], и получим искомое значение ${\lambda }_1$. При этом численно решается только одно уравнение, в отличие от существующего алгоритма.

С учетом полученных аналитических выражений алгоритм определения интенсивностей переходов ОЗРЭ ВП для заданного среднего времени перехода между состояниями представим в виде последовательности действий (рис. 2).

 

Рис. 2. Блок-схема предлагаемого алгоритма

 

Шаг 1. Задают исходные данные. В качестве исходных данных выступает среднее время перехода между состояниями $t_d^{*}$.

Шаг 2. Определяют интенсивность переходов между состояниями ${\lambda }_1$ путем решения уравнения (8) известным численным методом.

Шаг 3. Определяют интенсивность переходов между состояниями ${\lambda }_2$ с использованием выражения (6).

Предложенный алгоритм реализован в программном комплексе оценки эффективности организационно-технических систем в условиях антагонистического конфликта «Стронций» [10].

При вычислении одной пары параметров с помощью существующего алгоритма с точностью 10^–5 в однопоточном режиме работы процессора понадобилось 3 мин 42 с, а в многопоточном режиме – 51 с. Предлагаемый алгоритм справляется с задачей за 2 мс, что дает прирост производительности против многопоточного режима в 25 500 раз и в 100 000 раз – против однопоточного режима.

Заключение

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

About the authors

I. S. Degtyarev

Military Educational and Scientific Centre of the Air Force N. E. Zhukovsky and Yu. A. Gagarin Air Force Academy

Email: romankolmykov@gmail.com

Research fellow

Russian Federation, Voronezh

M. A. Peregudov

Military Educational and Scientific Centre of the Air Force N. E. Zhukovsky and Yu. A. Gagarin Air Force Academy

Email: romankolmykov@gmail.com

Candidate of Technical Sciences

Russian Federation, Voronezh

R. Yu. Kolmykov

Military Educational and Scientific Centre of the Air Force N. E. Zhukovsky and Yu. A. Gagarin Air Force Academy

Author for correspondence.
Email: romankolmykov@gmail.com

Adjunct

Russian Federation, Voronezh

A. S. Kolmykova

Military Educational and Scientific Centre of the Air Force N. E. Zhukovsky and Yu. A. Gagarin Air Force Academy

Email: romankolmykov@gmail.com

Junior Research Fellow

Russian Federation, Voronezh

References

Supplementary files