Алгоритм аналитического расчета вероятностей состояний нестационарных систем обслуживания

09.11.2011 г.

На главную раздела "Смагин Владимир Александрович"

УДК 681.142.2
Модель графа нестационарной системы предложена Смагиным В. А.
Алгоритм расчёта разработан Бубновым В. П.

В. П. Бубнов (ФГБОУ ВПО ПГУПС)

АЛГОРИТМ АНАЛИТИЧЕСКОГО РАСЧЕТА ВЕРОЯТНОСТЕЙ СОСТОЯНИЙ НЕСТАЦИОНАРНЫХ СИСТЕМ ОБСЛУЖИВАНИЯ

аналитический метод расчёта, нестационарная модель обслуживания, вероятности состояний.

Введение

          Нестационарные модели обслуживания нашли широкое применение при анализе качества функционирования вычислительных систем и сетей, находящихся в контуре управления подвижными объектами и технологическими процессами [1, 2], функциональной безопасности средств железнодорожной автоматики [3], а также при оценке надежности программного обеспечения [4, 5].

          На основе нестационарной системы обслуживания (НСО) и метода планирования испытаний программных средств разработан комплекс программ расчёта надежности и планирования испытаний программных средств [6].

          Однако желание учёта большего числа факторов реальных процессов, подлежащих моделированию, приводит к увеличению числа дифференциальных уравнений Чэпмена-Колмогорова относительно вероятностей состояний. Время численного решения такой системы дифференциальных уравнений, как показали эксперименты, экспоненциально зависит от числа состояний НСО, что накладывает значительные ограничения на вновь разрабатываемые модели нестационарных систем.

          В связи с вышеизложенным, актуальность разработки аналитического метода расчёта НСО не вызывает сомнения.

1. Модель одноканальной нестационарной системы обслуживания

На вход одноканальной нестационарной системы обслуживания последовательно поступает N заявок на обслуживание. Распределения временных интервалов между поступлениями заявок описываются экспоненциальными законами с интенсивностями {λ₁, λ₂, …, λ_N}, зависящими от номера заявки. Считается, что система обслуживания без потерь. Закон распределения времени обслуживания двухэтапный неоднородно-эрланговский с интенсивностями μ_j, μ'_j обслуживания j-ой заявки.

Такая НСО представима в виде вложенной марковской цепи с дискретным множеством состояний и непрерывным временем. Состояния НСО в каждый момент времени характеризуется числом находящихся в ней заявок i = 0, N, числом обслуженных заявок j = 0, N и номером этапа неоднородно-эрланговского распределения временных интервалов обслуживания k = 0,1. Переход из состояния (i, k, j) в состояние (i+1, k, j) означает, что в НСО поступила (i+j+1) заявка. Переход из состояния (i, 0, j) в состояние (i-1, 0, j+1) означает, что была обслужена (j+1)-я заявка. Граф переходов между состояниями НСО представлен на рис. 1.

Рис. 1. Граф переходов между состояниями НСО

Где Р_{i, k, j} (t) есть вероятность пребывания НСО в состоянии (i, k, j). Общие число состояний Т = (N+1)². Приведенная НСО описывается системой из Т дифференциальных уравнений Чэпмена-Колмогорова, каждое из которых выглядит следующим образом:

(1)

Здесь Н(х) — функция Хэвисайда, заданная как

Для каждого момента времени t должно соблюдаться условие нормировки вида

Задав начальные условия к системе к примеру

(2)

можно найти численное решение соответствующей задачи Коши для произвольного значения t. В векторно-матричном виде систему уравнений (1) можно записать:

(3)

где

;

А — переходная матрица, имеющая размерность T×T, есть функция от интенсивности поступления заявок и интенсивностей обслуживания.

2. Метод аналитического расчета НСО

          Для решения задачи (1), традиционно используются численные методы [7]. Однако увеличение размерности системы влечёт за собой многократный рост вычислительных затрат, и в силу большего числа действий, совершаемых на каждом шаге решения, и в силу роста погрешностей, приводящих к необходимости увеличения общего числа шагов на заданном интервале.

          Система (1) является линейной однородной системой обыкновенных дифференциальных уравнений первого порядка. Её аналитическое решение легко выписывается через собственные числа и собственные векторы матрицы А [8]. Соответственно, если удастся их найти, то нахождение численных значений решений в конкретные моменты времени не составит труда. Покажем, что для рассматриваемой модели НСО построение фундаментальной системы решений не требует дополнительных затрат, связанных с поиском собственных значений матрицы А.

          Все состояния НСО являются невозвратными. Разбив все состояния на группы так, что в первую группу входят состояния, у которых j = 0, во вторую j = 1, и т. д. до j = N. Каждую группу в свою очередь разобьем на подгруппы в порядке возрастания i, где i = 0, N - j. В каждой подгруппе каждой группы, за исключением группы j = N, два состояния (i, 0, j) и (i, 1, j). Состояние (0, 0, N) является поглощающим.

          Невозможны переходы:

          1.   из состояния группы h в состояние группы ℓ, если h > ℓ;
          2.   из состояния подгруппы h группы j в состояние подгруппы ℓ группы j, если h > ℓ;
          3.   из состояния группы j в состояние группы ℓ, если ℓ > j +1;
          4.   из состояния подгруппы h группы j в состояние подгруппы ℓ этой же группы, если ℓ > h +1;
          5.   из состояния группы j, подгруппы i, k = 1 в состояние группы j, подгруппы i, k = 0

          Если ввести сквозную нумерацию всех состояний НСО в порядке возрастания номеров групп, внутри групп в порядке возрастания номеров подгрупп, а внутри подгрупп от состояния, в котором k = 0 до k = 1, то система дифференциальных уравнений (1) преобразуется к виду

(3)

где а_nm — интенсивность перехода из состояния с номером m в состояние с номером n.

Так как матрица коэффициентов А системы (3) нижнетреугольная, то очевидно, что характеристическое уравнение для определения собственных чисел будет иметь вид

(4)

Заметим, что состояние с номером Т является поглощающим, что влечёт за собой а_TT = 0. Остальные диагональные элементы матрицы в данном случае будут выражаться следующим образом:

(5)

с соответствующим пересчётом состояния (i, k, j) в состояние с номером m.

Соответственно, если среди собственных чисел α_m = a_mm(m = 1,T) нет кратных, то фундаментальное решение системы (3), а значит, и равнозначной ей системы (1) имеет вид

(6)

В случае, если α_m — корень кратности r, то есть для некоторых m₁, …, m_r выполняется

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

(7)

Решения (3) в общем виде, при начальных условиях P_m(0) = P_0m, следующие.

Решение первого уравнения системы (3)

, и ему соответствует фундаментальное решение .

Предположив, что решения первых m-1 уравнений найдено в форме

(8)

причём

где υ_n — кратность собственного числа а_nn в системе первых n уравнений, которую назовём промежуточной кратностью. Тогда после подстанов (8) в m-ое уравнение системы (3), последнее можно записать в виде

(9)

коэффициенты в_mn в котором находятся как

Решение (9) будет иметь вид

(10)

и весь вопрос заключается в определении значений К_mn. Пусть а_mm — собственное число промежуточной кратности υ_m, и собственные числа

, пронумерованы в порядке возрастания промежуточной кратности, то есть υ_mω = ω, ω = 1,υ_m. Тогда

(11)

Коэффициенты при всех остальных фундаментальных решениях

, для которых а_nn ≠ а_mm находятся следующим образом. Если а_nn — собственное число промежуточной кратности υ_n, то

(12)

где а_ωω = а_nn и υ_ω = υ_n - 1.

Когда найдены все коэффициенты (11) и (12), находится

(13)

что позволяет выписать решение (10) в явном виде. Полученный алгоритм решения системы (1) требует на каждом шаге О(m²) арифметических операций и не более m сравнений. Общая же сложность алгоритма оценивается как О(Т³).

Заключение

В таблице 1 приведены результаты расчёта численным и аналитическим методами. Шаг интегрирования численным методом составляет Δt = 0,5 с.

Таблица 1. Сравнительный анализ расчёта численным и аналитическим методами

t, c	Вероятность решения задач
	N = 5		N = 10
	Численный	Аналитический	Численный	Аналитический
40	0,0183	0,0246	0,0	0,0
80	0,4023	0,4008	0,0033	0,0054
120	0,8071	0,7967	0,1019	0,1103
160	0,9532	0,9481	0,3935	0,3934
200	0,9899	0,9883	0,6932	0,6853
240	0,9979	0,9975	0,8752	0,8676
280	0,9995	0,9995	0,9567	0,9523
320			0,9866	0,9845
360			0,9962	0,9955
400			0,999	0,9988

На рисунке 1 показаны графики зависимости времени расчёта вероятностей состояний НСО от числа задач в потоке. Кривая 1 демонстрирует зависимость времени расчёта модели численным методом при шаге интегрирования Δt = 0,5 с, кривая 2 — при Δt = 1. Кривая 3 показывает зависимость времени расчёта модели предложенным аналитическим методом.

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

Рис. 1. Зависимость времени расчёта модели от числа задач в потоке
(1 — числ., Δt = 0,5; 2 — числ., при Δt = 1; 3 — аналит.)

Библиографический список

1.   О загрузке вычислительной системы с изменяющейся интенсивностью по-ступления заданий /Бубнов В. П., Сафонов В. И., Смагин В. Л.// Автоматика и вычислительная техника. – 1987. – № 6. – С. 19-22.

2.   Разработка динамических моделей нестационарных систем обслуживания / Бубнов В. П., Сафонов В. И. // СПб. – Издательство «Лань». – 1999. – С. 64.

3.   Нестационарная модель оценки функциональной безопасности средств же-лезнодорожной автоматики / Бубнов В. П., Бурцева К.И. // Труды Междуна-родной научно-методической конференции, 11-12 ноября 2010 г. – СПб. – Петербургский государственный университет путей сообщения. – 2011. – С. 269.

4.   Обоснование стратегии отладки программ на основе нестационарной моде-ли надёжности / Бубнов В.П., Тырва А.В., Хомоненко А.Д. // Научно-технические ведомости Санкт-Петербургского государственного политехни-ческого университета. – 2010. – № 2 (97). – С. 85-92.

5.   Model of reliability of the software Coxian distribution of length of intervals between the moments of detection of errors / Bubnov V.P., Tyrva A.V., Khomonenko A.D. // In proceedings of 34th Annual IEEE Computer Software and Applications Conference (COMPSAC 2010). – Seoul, Korea, 19-23 Jule 2010. – p.p. 238-243.

6.   Комплекс программ расчета надежности и планирования испытаний про-граммных средств / Тырва А.В., Хомоненко А.Д., Бубнов В.П. // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. Свидетельство о государственной регистрации программ для ЭВМ №2010615617. – Москва. – 2010.

7.   Решение обыкновенных дифференциальных уравнений. Нежёсткие задачи / Хайрер Э., Нёрсетт С., Ваннер Г. // Пер. с англ. – Москва. – Мир. – 1990.

8.   Обыкновенные дифференциальные уравнения с приложениями / Егоров А.И. // 2-е изд., испр. – Москва. – ФИЗМАТЛИТ. – 2005.

Материал поступил в редакцию 05.11.2011