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

Полный текст

Введение

Для моделирования входящего потока заявок в задачах телекоммуникации, а также при решении транспортных задач в основном применяется обобщенный закон распределения Эрланга, поскольку при его использовании теоретические результаты хорошо согласуются с эмпирическими [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 раз – против однопоточного режима.

Заключение

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

Об авторах

Иван Сергеевич Дегтярев

Военный учебно-научный центр военно-воздушных сил «Военно-воздушная академия» имени профессора Н. Е. Жуковского и Ю. А. Гагарина

Email: romankolmykov@gmail.com

научный сотрудник

Россия, Воронеж

Максим Анатольевич Перегудов

Военный учебно-научный центр военно-воздушных сил «Военно-воздушная академия» имени профессора Н. Е. Жуковского и Ю. А. Гагарина

Email: romankolmykov@gmail.com

кандидат технических наук

Россия, Воронеж

Роман Юрьевич Колмыков

Военный учебно-научный центр военно-воздушных сил «Военно-воздушная академия» имени профессора Н. Е. Жуковского и Ю. А. Гагарина

Автор, ответственный за переписку.
Email: romankolmykov@gmail.com

адъюнкт

Россия, Воронеж

Анастасия Сергеевна Колмыкова

Военный учебно-научный центр военно-воздушных сил «Военно-воздушная академия» имени профессора Н. Е. Жуковского и Ю. А. Гагарина

Email: romankolmykov@gmail.com

младший научный сотрудник

Россия, Воронеж

Список литературы

Дополнительные файлы