09.11.2011 г.

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


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

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


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

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

Введение

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

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

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

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


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

          На вход одноканальной нестационарной системы обслуживания последовательно поступает N заявок на обслуживание. Распределения временных интервалов между поступлениями заявок описываются экспоненциальными законами с интенсивностями {λ1, λ2, …, λ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)2. Приведенная НСО описывается системой из Т дифференциальных уравнений Чэпмена-Колмогорова, каждое из которых выглядит следующим образом:
Пример изображения(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 = amm (m = 1,T) нет кратных, то фундаментальное решение системы (3), а значит, и равнозначной ей системы (1) имеет вид

Пример изображения(6)


          В случае, если αm — корень кратности r, то есть для некоторых m1, …, mr выполняется  Пример изображения, соответствующие этому собственному числу фундаментальные решения запишутся как

 Пример изображения(7)


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

          Решение первого уравнения системы (3)  Пример изображения, и ему соответствует фундаментальное решение  .Пример изображения

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

Пример изображения
(8)


причём
Пример изображения

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

Пример изображения(9)


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

Пример изображения


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

Пример изображения(10)


и весь вопрос заключается в определении значений Кmn. Пусть аmm — собственное число промежуточной кратности υm, и собственные числа  Пример изображенияПример изображения , пронумерованы в порядке возрастания промежуточной кратности, то есть υ = ω, ω = 1,υm. Тогда

Пример изображения(11)


          Коэффициенты при всех остальных фундаментальных решениях  Пример изображения, для которых аnn ≠ аmm находятся следующим образом. Если аnn — собственное число промежуточной кратности υn, то

Пример изображения
(12)


где аωω = аnn и υω = υn - 1.

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

Пример изображения(13)


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


Заключение

          В таблице 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
 

Добавить комментарий Сообщение модератору


Защитный код
Обновить