Спросить
Войти
УДК 519.872
Метод анализа открытой сети массового обслуживания с деградируемой структурой и мгновенным восстановлением систем
И. Е. Тананко, Н. П. Фокина
Тананко Игорь Евстафьевич, кандидат физико-математических наук, заведующий кафедрой системного анализа и автоматического управления, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского, Россия, 410012, г. Саратов, ул. Астраханская, д. 83, TanankoIE@info.sgu.ru
Фокина Надежда Петровна, кандидат физико-математических наук, доцент кафедры системного анализа и автоматического управления, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского, Россия, 410012, г. Саратов, ул. Астраханская, д. 83, FokinaNP.sgu@gmail.com
Рассматривается открытая сеть массового обслуживания с ненадежными системами массового обслуживания. В сеть из внешнего источника поступает пуассоновский поток требований одного класса. Для каждой системы длительность обслуживания требований в период ее бесперебойной работы и длительность наработки на отказ являются экспоненциально распределенными случайными величинами с известными параметрами. Последовательный выход из строя систем приводит к изменению в структуре и соответствующему изменению характеристик сети. Предполагается, что интервалы времени между изменениями структуры сети достаточны для наступления стационарного режима функционирования. Характеристикой качества функционирования сети на каждом интервале постоянства структуры является математическое ожидание длительности реакции сети. Мгновенное восстановление всех систем осуществляется в моменты, когда математическое ожидание длительности реакции сети становится больше заданного порогового значения или нарушается связность сети. Показано, что стационарное распределение вероятностей состояний ненадежной сети обслуживания имеет мультипликативную форму. Предложен метод анализа сети с использованием цепей Маркова с непрерывным временем и получены выражения для определения стационарных характеристик ненадежных систем и сети обслуживания, в том числе математического ожидания длительности интервала времени между моментами восстановления систем. На численном примере проведены исследования зависимостей характеристик сети от некоторых ее параметров.
Поступила в редакцию: 23.11.2018 / Принята: 05.04.2019 / Опубликована: 01.06.2020 Статья опубликована на условиях лицензии Creative Commons Attribution License (CC-BY4.0) DOI: https://doi.org/10.18500/1816-9791-2020-20-2-266-276
ВВЕДЕНИЕ
Сети массового обслуживания используются в качестве математических моделей дискретных стохастических систем с сетевой структурой и с ненадежными
элементами. Например, для моделирования систем, в которых учитывается реакция на появление нежелательных изменений в обслуживаемых элементах, используются сети массового обслуживания с системами или группами систем обслуживания с обратной связью. Так, для оценки требуемого объема памяти и производительности проектируемой мультимедийной системы использована открытая сеть массового обслуживания, в которой системы массового обслуживания с обратной связью отображают процессы возникновения ошибок при передаче данных по ненадежным коммуникационным устройствам мультимедийной системы [1]. В работе [2] рассматривается сеть передачи пакетов и исследуется эффект влияния интенсивности возникновения ошибки в канале на среднюю задержку пакета. Каждый из ненадежных каналов моделируется системой массового обслуживания с обратной связью, отображающей повтор передачи пакета, если тот передан с ошибкой. Для моделирования производственных систем с ненадежными элементами может быть использована сеть массового обслуживания, состоящая из нескольких последовательно соединенных многоприборных систем обслуживания. Приборы систем последовательно переходят из работоспособного состояния в неработоспособное. После завершения обслуживания в последней системе требование с определенной вероятностью может перейти в первую систему цепи систем обслуживания [3].
Решение задач анализа и синтеза реальных систем с учетом выхода из строя и восстановления отдельных элементов приводит к необходимости развития теории и методов анализа сетей массового обслуживания с изменяемой структурой. Так, для сетей массового обслуживания с переменным числом систем обслуживания [4-6] и сетей массового обслуживания с включением и отключением связей между системами обслуживания [6,7] получено стационарное распределение вероятностей числа требований в системах сетей. Для замкнутой сети обслуживания с переменной структурой использован метод формирования маршрутных матриц, обеспечивающих одинаковые средние длительности пребывания требований в системах обслуживания [8]. В работе [9] использован метод производящих функций для нахождения переходных вероятностей числа требований в ненадежных системах обслуживания открытой сети массового обслуживания. В работах [10,11] рассматривается экспоненциальная сеть массового обслуживания, в которой любая из систем обслуживания может выходить из строя, т. е. прекращать обслуживание требований, и восстанавливаться. Требования в период восстановления приборов продолжают поступать в системы обслуживания. Предполагается, что интенсивности восстановления приборов систем обслуживания намного больше интенсивностей наработки на отказ этих приборов. Используя метод уменьшения интенсивностей обслуживания требований в системах сети, задача анализа ненадежной сети массового обслуживания сведена к решению задачи анализа абсолютно надежной экспоненциальной сети обслуживания. Открытая сеть с переменным числом параллельных систем обслуживания [12] используется в качестве математической модели вШЭ-системы. Ненадежные системы обслуживания отображают независимые процессы подключения и отключения вычислительных ресурсов вШЭ-системы.
В данной работе рассматривается сеть Джексона, в которой системы обслуживания в процессе функционирования сети последовательно выходят из строя. Длительности наработки на отказ систем обслуживания являются экспоненциально распределенными случайными величинами. В момент отказа очередной системы обслуживания все требования, находящиеся в этой системе, мгновенно теряются. При
этом маршрутная матрица сети обслуживания изменяется таким образом, чтобы требования не поступали в данную систему обслуживания. Предполагается, что как только среднее время реакции сети обслуживания будет превосходить предельное заданное значение из-за последовательного выхода из строя систем обслуживания, все отказавшие системы обслуживания мгновенно восстанавливаются. Мгновенное восстановление ранее отказавших систем обслуживания производится и тогда, когда выход из строя очередной системы обслуживания нарушает связность сети оставшихся работоспособными систем обслуживания. Случайный процесс отказов систем обслуживания с мгновенным их восстановлением представлен цепью Маркова с непрерывным временем. Для определения времени между моментами восстановления систем обслуживания используется поглощающая цепь Маркова. Получены выражения для определения стационарных характеристик систем и сети обслуживания с деградируемой структурой. Представлен численный пример расчета характеристик гипотетической сети массового обслуживания рассматриваемого типа.
Рассмотрим открытую сеть массового обслуживания Г, состоящую из Ь систем массового обслуживания 5, г = 1,...,Ь, типа М/М/к с интенсивностями обслуживания ^,г = 1,...,Ь. Из источника 50 в сеть поступает пуассоновский поток требований одного класса с интенсивностью А0. Переходы требований между всеми системами обслуживания в сети определяются начальной маршрутной матрицей © = (%), г,; = 0,..., Ь.
Предполагается, что системы сети могут выходить из строя независимо друг от друга. Длительность наработки на отказ системы 5 имеет экспоненциальное распределение с параметром т^, г = 1,...,Ь. При отказе системы все требования, находящиеся в ней, теряются. Выход системы из строя приводит к изменению топологии сети и соответствующему изменению маршрутной матрицы В с тем, чтобы исключить поступление требований в неработоспособную систему.
Пусть Ь = (Ь), г = 1,..., Ь, — вектор, определяющий структуру сети, где Ь = 0, если система 5 вышла из строя, иначе Ь = 1. Пусть В(Ь) — маршрутная матрица сети со структурой Ь. Рассмотрим смежные структуры Ь и Ь, отличающиеся только одной компонентой с номером т, т е {1,...,Ь}, причем Ьт = 1, Ьт = 0. В момент выхода из строя системы 5т вектор структуры сети Ь преобразуется в Ь , а маршрутная матрица В(Ь) — в матрицу В( Ь ). Элементы матрицы В( Ь ) определяются по формулам:
Отт ( Ь) = 1.
Пусть п = (п), г = 1,...,Ь, — состояние сети, где щ — число требований в системе тогда в момент выхода из строя системы 5т пт = 0. Основной характеристикой, определяющей качество работы сети со структурой Ь, будем считать математическое ожидание (м.о.) длительности реакции сети т0(Ь). Пусть для сети обслуживания задано пороговое значение м.о. длительности реакции г0. Процесс функционирования сети с нестационарной структурой осуществляется следующим
образом. Системы обслуживания выходят из строя независимо друг от друга с экспоненциальной длительностью наработки на отказ с разными интенсивностями, вызывая изменения в структуре сети Ь. Пока
То(Ь) <Т0, (1)
не предпринимается действий по восстановлению вышедших из строя систем. Если
То (Ь) ^ го, (2)
то предполагается, что все неработоспособные системы мгновенно восстанавливаются. Если при выходе из строя очередной системы обслуживания связность сети нарушается, то все системы также мгновенно восстанавливаются.
Требуется найти вероятностно-временные характеристики сети обслуживания.
Эволюция сети Г представляется множеством реализаций подсетей Г(Ь). Каждая реализация подсети обслуживания однозначно определяется вектором структуры Ь и маршрутной матрицей В(Ь). Другие параметры реализаций подсетей совпадают.
Пусть В — множество всевозможных векторов структур Ь. Подсеть Г(Ь) назовем подсетью со связной конфигурацией, если маршрутная матрица множества исправных систем обслуживания является неприводимой. Пусть В — подмножество векторов Ь, образующих подсети Г(Ь) со связной конфигурацией, для которых выполнено условие (1). Тогда В \\В — подмножество векторов структур Ь, для которых выполнено условие (2), включая случаи нарушения связности, для которых полагаем То (Ь) = то .
Эволюцию сети Г можно рассматривать как два протекающих параллельно процесса: процесс отказов систем обслуживания с мгновенным их восстановлением по событию (2) и вложенный в него процесс функционирования сети с фиксированной топологией.
Изменение структуры сети приводит к возникновению переходного процесса, длительность которого будем считать существенно меньше длительности функционирования сети со структурой Ь е В. Поэтому будем пренебрегать переходным процессом и считать, что сеть Г(Ь) мгновенно переходит в стационарный режим функционирования. Стационарные характеристики сети Г(Ь), Ь е В, могут быть получены известными методами [13].
Случайный процесс отказов систем обслуживания с мгновенным их восстановлением по событию (2) может быть описан цепью Маркова М с непрерывным временем и множеством состояний В. Перенумеруем состояния множества В таким образом, что Ь(1) — структура, при которой все системы сети работоспособны, нумерация остальных состояний — произвольная. В дальнейшем, если из контекста ясно, о каком состоянии идет речь, то нумерация состояний будет опускаться. Пусть В с В — подмножество граничных состояний Ь(г) е В, из которых возможен выход из множества В. Для состояния Ь(г) е В обозначим через Т с В \\ В подмножество смежных состояний таких, что Ь е Т тогда и только тогда, когда ||Ь(г) — Ь|| = 1 и выполнено условие (2). Интенсивность перехода из Ь(г) е В в Т равна
) = ££ Тк (Ьк° — Ьк).
ЬеТ; к= 1
Интенсивности переходов из Ь(?) е В в Ь(^) е В цепи Маркова М
а(Ь(0, Ь(;)) = 7к(Ьк° - Ьк>), если ||Ь<&> - Ь« у = 1,
и интенсивность выхода из состояния Ь(г) е В при г = 1
«(Ь(!) ) = Е Тк Ь®.
Мгновенное восстановление систем при выполнении условия (2) в модели означает, что для состояний Ь(г) е В при г = 1 осуществляется переход в состояние Ь(1) с интенсивностью
а(Ь(?) ,Ь(1)) = а(Ь(?) ). Если Ь(1) е В, то интенсивность выхода из состояния Ь(1)
«(Ь(1)) = Е ^кЬк1& - а(Ь(1)).
Обозначим инфинитезимальный оператор цепи Маркова через А = (а^), где
а^- = а(Ь(?), Ь^&)) для Ь(?), Ь^&) е В, г = а« = -а(Ь(<)).
Стационарное распределение вероятностей состояний цепи п = (п(Ь)), Ь е В, является решением уравнения пА = 0 с условием нормировки ^Ъев п(Ь) = 1.
Тогда стационарные характеристики систем обслуживания сети Г могут быть определены по формуле
Хк = Хк(Ь)п(Ь), к = 1,...,Ь,
где хк — интегральная характеристика системы 5к, хк(Ь) — характеристика системы 5к сети обслуживания Г(Ь), а м.о. длительности реакции сети Г
Т0 = Е Т0(Ь)п(Ь).
В частности, средняя интенсивность входящего потока в систему 5к равна
Ак = ^ Ак (Ь)п (Ь), к = 1,...,Ь.
Тогда пропускная способность ненадежной сети определяется выражением
Л = Е Ак.
Покажем, что стационарные вероятности структур имеют мультипликативную форму и могут быть определены следующим образом.
Пусть Ь(Ь) — множество номеров отказавших систем обслуживания в структуре Ь, А(Ь) — множество перестановок из элементов Ь(Ь). Будем считать, что в каждой из |Ь(Ь)|! возможных перестановок слева направо указана последовательность номеров систем обслуживания в порядке их отказа. Обозначим номера этих систем через к1, к2,..., к|Ь(Ь)| и определим
р(Ь) = Е
;|Ь(Ь)|
ь ь ь
А(Ь)Е 7% Е 7% Е 7« %=1 %=1 %=1
%=к1 %0Ь(Ь)\\к|Ь(Ь)|
Математическое ожидание длительности пребывания сети в структуре Ь е В равна
Тогда вероятности состояний структур
П(Ь) = , Ь е В,
где С = ЬеВ р(Ь)1(Ь) — нормализующая константа.
Определим м. о. времени функционирования сети между моментами восстановления. Пусть 1 = |В| — мощность множества В. Обозначим через М* поглощающую цепь Маркова, отличающуюся от цепи М наличием поглощающего состояния Ь(1). Очевидно, что инфинитезимальный оператор А* цепи М* отличается от оператора А только строкой, соответствующей состоянию Ь(1), и имеет вид
" 0 0 Я1 я
где Я1 — вектор вероятностей поглощения размерности (1 — 1) х 1, Я — субгенератор, матрица интенсивностей перехода в множестве невозвратных состояний размерности (1 — 1) х (1 — 1), 0 — нулевой вектор размерности 1 х (1 — 1). Начальное распределение цепи М* положим равным в = (в%), 2 = 1,... ,1 — 1, где в% = а1,%+1 /(—«%%). Известно [14], что время до поглощения имеет фазовое распределение с математическим ожиданием, равным — вЯ-11, где 1 — единичный вектор-столбец. Тогда м.о. времени между моментами восстановления равно
Рассмотрим открытую экспоненциальную сеть массового обслуживания с одним классом требований, Ь = 8, А0 = 1.1, т0 = 9.2, вектор числа приборов к = (1, 2,1,2,1,1, 2,1), вектор интенсивностей обслуживания требований одним прибором ^ = (1.8,1.0,1.7,1.0,1.9,2.0,1.1,1.9), вектор интенсивностей наработки на отказ систем обслуживания 7 = (0.01,0.02,0.04, 0.03,0.04, 0.02,0.01, 0.01), ненулевые элементы исходной маршрутной матрицы равны 0о1 = 0.2, 0оз = 0.3, 0о5 = 0.3, $07 = 0.2, 012 = 1, $20 = 1, $34 = 1, $40 = 1, $56 = 1, $60 = 1, $78 = 1, $80 = 1.
При данных значениях параметров ненадежной сети обслуживания получены следующие значения характеристик: |В| = 325, т0 = 2.627, Л = 3.143, вероятность того,
что все системы обслуживания находятся в исправном состоянии, равна 0.202. Для сравнения, аналогичная сеть массового обслуживания, но с абсолютно надежными системами имеет следующие характеристики: т0 = 2.531, Л = 3.203.
Проведены исследования зависимостей характеристик сети от ее параметров. Графики функции т0 при изменении интенсивности входящего потока требований А0 для сети с ненадежными и абсолютно надежными системами при пороговых значениях т0 = 15, т0 = 3 и т0 = 2 представлены на рис. 1, а, б, в соответственно.
Рис. 1. Математическое ожидание длительности реакции абсолютно надежной (пунктирная линия) и ненадежной сетей (сплошная линия) при пороговом значении:
а — то = 15; б — то = 3; в — то = 2 Fig. 1. The average response time for a reliable network (dashed line) and an unreliable network (solid line) at the threshold value: a — то = 15; b — то = 3; c — то = 2
состояний для ненадежной сети Fig. 2. The cardinality of the set of admissible states for an unreliable network
Из результатов экспериментов, представленных на рис. 1, ясно, что т0 — кусочно-непрерывная функция. Точки разрыва функции т0 соответствуют изменению мощности множества В из-за состояний, в которых т0 становится больше порогового значения т0. График скачков мощности множества В показан на рис. 2.
Чем меньше пороговое значение т0, тем чаще происходит изменение состава множества В и тем больше точек разрыва-скачков имеет функция т0. На каждом интервале непрерывности функция т0
имеет тенденцию к экспоненциальному росту при увеличении интенсивности входящего потока Л0.
На рис. 3, а показан график зависимости м.о. времени между моментами восстановления д от порогового значения длительности реакции сети т0 при фиксированном значении интенсивности входящего потока Л0. Мощность множества В скачкообразно возрастает при увеличении т0 и фиксированном Л0, поэтому значение д ведет себя аналогично и имеет постоянные значения на интервалах изменения т0, для которых структуры В постоянны.
На рис. 3, б показан график зависимости м.о. времени между моментами восстановления д от интенсивности входящего потока Л0 при т0 = 2. Скачки функции д на этом графике соответствуют изменениям структуры множества В, которые отражены на рис. 2, когда т0 = 2.
а / a б / b
Рис. 3. Математическое ожидание длительности функционирования сети между восстановлениями: а — как функция порогового значения математического ожидания длительности реакции при интенсивности входящего потока Ао = 1.6; б — как функция интенсивности входящего потока при пороговом значении математического ожидания
длительности реакции то = 2 Fig. 3. The average of repair time intervals: a — as a function of the threshold value at the arrival rate А0 = 1.6; b — as a function of the arrival rate at the threshold value то = 2
ЗАКЛЮЧЕНИЕ
В работе предложен метод анализа сети массового обслуживания с последовательно отключающимися многоприборными системами обслуживания и их последующим мгновенным восстановлением, когда математическое ожидание времени реакции сети превышает заданное пороговое значение или выход из строя очередной системы обслуживания приводит к нарушению связности сети. Разработанный метод может быть использован для решения задач проектирования и анализа сетей передачи информации с ненадежными элементами. В модельной сети обслуживания реализован метод технического обслуживания, суть которого состоит в том, что восстановление отказавших элементов сети начинается после того, как качество функционирования сети достигло критического уровня.
Библиографический список
Образец для цитирования:
Тананко И. Е., Фокина Н. П. Метод анализа открытой сети массового обслуживания с деградируемой структурой и мгновенным восстановлением систем // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2020. Т. 20, вып. 2. С. 266-276. 001: https://doi.org/10.18500/1816-9791-2020-20-2-266-276
An Analysis Method of Open Queueing Networks with a Degradable Structure and Instantaneous Repair Times of Systems
I. E. Tananko, N. P. Fokina
Igor E. Tananko, https://orcid.org/0000-0001-8960-9709, Saratov State University, 83 Astrakhan-skaya St., Saratov 410012, Russia, TanankoIE@info.sgu.ru
Nadezhda P. Fokina, https://orcid.org/0000-0002-8085-609X, Saratov State University, 83 Astra-khanskaya St., Saratov 410012, Russia, FokinaNP.sgu@gmail.com
An unreliable open queueing network with Poisson arrivals is considered. For each queueing system the service and failures times are exponentially distributed random variables. The failures of systems lead to changes in the structure of the network and corresponding changes in the performance measures of the queueing network. It is assumed that the times between changes in the network structure are sufficient for the steady-state regime. The main measure of the quality for the network at each structure constancy interval is the average response time. Repairs of all queueing systems occur immediately when the average response time becomes greater than the threshold value. This article presents a method of the network analysis using continuous time Markov chains. It is shown that the steady-state probability distribution of the unreliable queueing network has a product form solution. Expressions for the stationary performance measures of queueing systems and the network including the average of system repair time intervals are obtained. A numerical example to investigate the dependence of the performance measures on some network parameters is demonstrated.
Received: 23.11.2018 / Accepted: 05.04.2019 / Published: 01.06.2020
This is an open access article distributed under the terms of Creative Commons Attribution License (CC-BY 4.0)
References
Cite this article as:
Tananko I. E., Fokina N. P. An Analysis Method of Open Queueing Networks with a Degradable Structure and Instantaneous Repair Times of Systems. Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 2020, vol. 20, iss. 2, pp. 266-276 (in Russian). DOI: https://doi.org/10.18500/1816-9791-2020-20-2-266-276
