An analysis of queueing networks with unreliable servers and information delay.pdf Сети массового обслуживания с переменной структурой используются в качестве моделей дискретных стохастических систем с сетевой структурой и ненадежными элементами. Удобство их применения связано с простотой и естественностью отображения структуры и процессов функционирования таких систем. Работы [1-4] являются одними из первых, в которых сети массового обслуживания используются в качестве моделей для исследования влияния различных алгоритмов маршрутизации на характеристики сетей передачи данных с коммутацией пакетов и ненадежными каналами [1], для определения характеристик и выявления узких мест в многопроцессорных системах с переменной структурой [2], для решения задачи отыскания оптимальных конфигураций гибких производственных систем с надежными и ненадежными элементами [3], а также для моделирования распределенных информационных систем с ненадежными рабочими станциями [4]. В дальнейшем сети массового обслуживания с переменной структурой были использованы в качестве моделей мультимедийных систем с ненадежными элементами [5], для решения задач анализа сетей мобильной связи [6], задач управления сетями связи с изменяемой топологией, к которым, в частности, относятся сети спутниковой связи и сети мобильной связи [7], а также для исследования динамических характеристик производственных систем конвейерного типа [8]. Класс сетей массового обслуживания с переменной структурой постоянно расширяется за счет рассмотрения различных особенностей изменения структуры, и это требует разработки методов их анализа. Например, в работе [9] рассматривается замкнутая экспоненциальная сеть массового обслуживания с ненадежными приборами в одноприборных системах обслуживания. Предложен приближенный метод анализа этой сети в предположении, что длительность обслуживания требований с учетом поломок и восстановлений приборов также является экспоненциально распределенной случайной величиной, но с уменьшенной интенсивностью обслуживания. Стационарное распределение вероятностей состояний получено для открытой экспоненциальной сети массового обслуживания, в которой уничтожаются все требования в системе обслуживания в момент отказа прибора этой системы [10]. Восстановление прибора происходит мгновенно, так что после отказа система готова принимать и обслуживать требования. Открытая экспоненциальная сеть массового обслуживания с последовательным расположением узлов рассматривается в работе [11]. Каждый узел состоит из нескольких параллельных систем обслуживания с неограниченными очередями. Длительности наработки на отказ и длительности 90 Метод анализа сетей массового обслуживания с ненадежными приборами и задержкой информации восстановления систем обслуживания являются экспоненциально распределенными случайными величинами. Требования, находящиеся в отказавшей системе обслуживания, ожидают ее восстановления. Требования после обслуживания в работоспособных системах направляются только в работоспособные системы. Предложенный в данной работе метод анализа сети сочетает в себе несколько известных методов анализа сетей массового обслуживания. Основными результатами работ [12-14] являются расширение класса сетей BCMP до сетей массового обслуживания с ненадежными элементами и получение в мультипликативном виде стационарных распределений вероятностей состояний этих сетей. Метод производящих функций для определения зависящих от времени вероятностей состояний открытой сети массового обслуживания с ненадежными системами обслуживания применен в работе [15]. Предполагается, что сеть функционирует в условиях высокой нагрузки. Интенсивности поступления и обслуживания требований, а также параметры исправной работы и восстановления приборов систем обслуживания зависят от времени. Получены приближенные выражения для определения вероятностей состояний, среднего числа исправных приборов и среднего числа требований в системах сети в произвольный момент времени. В работе [16] рассматривается открытая сеть массового обслуживания с подвижными системами обслуживания. Когда две системы меняются местами, каждая забирает с собой все требования, стоящие в очереди к ней. Основным результатом работы является доказательство сходимости процесса эволюции сети к некоторому нелинейному марковскому процессу. Несмотря на значительное количество научных работ, посвященных ненадежным сетям массового обслуживания, мало внимания уделяется развитию методов анализа сетей массового обслуживания с задержкой информации об изменении структуры этих сетей. В данной работе рассматривается открытая экспоненциальная сеть массового обслуживания с одним классом требований, состоящая из систем массового обслуживания типа М/М/2. Каждая система обслуживания содержит один абсолютно надежный и один ненадежный прибор. Ненадежный прибор последовательно переходит из работоспособного в неработоспособное состояние и обратно. Длительности пребывания ненадежных приборов систем обслуживания в работоспособном и неработоспособном состояниях являются экспоненциально распределенными случайными величинами. Если в момент отказа прибор был занят, то обслуживаемое требование переходит в очередь системы. В сети обслуживания реализован алгоритм управления потоком требований в системы обслуживания с задержкой информации о состоянии работоспособности ненадежных приборов систем, который заключается в следующем. Через экспоненциально распределенный интервал времени производится наблюдение за состоянием работоспособности ненадежных приборов систем. На основании полученной информации через экспоненциально распределенный интервал времени принимается решение о перенаправлении потоков требований в системы обслуживания. Критерием оптимального функционирования сети обслуживания является равенство математических ожиданий длительностей пребывания требований во всех системах обслуживания. Получено стационарное распределение вероятностей состояний работоспособности приборов систем обслуживания, а также стационарное распределение вероятностей числа требований в системах сети обслуживания. 1. Ненадежная сеть массового обслуживания Рассматривается открытая сеть массового обслуживания, состоящая из L систем массового обслуживания Si, i = 1, ..., L, типаM/M/2. Из источника So в сеть поступает пуассоновский поток требований одного класса с интенсивностью ^о. Матрица смежности W = (Wj), i, j = 0, 1, ..., L, ориентированного графа определяет структуру сети систем массового обслуживания. Элемент Wj = 1, если имеется связь из Si в Sj, и Wj = 0, если такой связи нет, i, j е {0, 1, ..., L}. Маршрутная матрица Ѳ = (Ѳу), i, j = 0, 1, ..., L, определяет переходы требований в сети обслуживания, где Ѳоі - вероятность поступления требований из источника So в систему Si, Ѳю - вероятность того, что после завершения обслу-91 И.Е. Тананко, Н.П. Фокина живания в системе Si требование покинет сеть обслуживания и возвратится в источник So, Ѳу - вероятность того, что после завершения обслуживания в системе Si требование перейдет в систему Sj, i,j е {1, ...,L}. Один из двух приборов каждой из систем обслуживания Si, i = 1, ..., L, является абсолютно надежным. Интенсивность обслуживания требований этим прибором рг- > 0, i = 1, ., L. Другой прибор системы Si, i = 1, ..., L, является ненадежным и последовательно переходит из работоспособного состояния в неработоспособное состояние. Пребывание ненадежного прибора системы обслуживания Si в работоспособном состоянии означает, что интенсивность обслуживания требований этим прибором равна рг- > 0, i = 1, ..., L. Когда же прибор системы Si находится в неработоспособном состоянии, то его интенсивность обслуживания рг- = 0. Когда отказавший прибор восстанавливается, то система обслуживания представляет собой систему типа M/M/1. Если в момент отказа ненадежный прибор обслуживал требование, то это требование возвращается в очередь данной системы. После восстановления ненадежного прибора система обслуживания вновь становится системой типа M/M/2. Длительности наработки на отказ и восстановления ненадежного прибора системы Si являются экспоненциально распределенными случайными величинами соответственно с параметрами аг- и рг-, i = 1, ., L, соответственно. Будем считать, что в сети массового обслуживания существует стационарный режим вне зависимости от того, сколько всего восстанавливается приборов в сети обслуживания и в каких системах обслуживания. Обозначим n(t) = (ni(t)) - вектор числа работоспособных приборов в системах сети обслуживания в момент t, ni(t) - число работоспособных приборов в системе Si в момент t. Состояние nt (t) = 2 означает, что ненадежный прибор системы Si работоспособен в момент t, ni(t) = 1 - в момент t ненадежный прибор системы Si восстанавливается, i = 1, ., L. В процессе функционирования сети обслуживания производится наблюдение за работоспособностью ненадежных приборов систем Si и управление входящими потоками требований в системы Si, основанное на результатах этих наблюдений. Управление потоками заключается в изменении маршрутной матрицы Ѳ. Полагаем, что, начиная с момента t получения информации о состоянии n(t), необходимо время для изменения маршрутной матрицы Ѳ и, следовательно, изменения потоков требований, поступающих в системы обслуживания. Формализуем алгоритм наблюдения за состоянием n(t) и управления матрицей Ѳ. Пусть в момент tks , k = 1, 2, ..., производится наблюдение за состоянием работоспособности ненадежных приборов в каждой из систем Si, i = 1, ., L. В момент tkd , tkd > tks , принимается решение об изменении потоков требований в системы сети обслуживания. Буквы s и d символизируют соответственно наблюдение за системами обслуживания и принятие решения об изменении матрицы Ѳ. Обозначим через Ѳ(п(tks)) - маршрутную матрицу, используемую в сети массового обслуживания с момента t d , при условии, что в момент td состояние работоспособности приборов систем сети определялось вектором n(tk). Маршрутная матрица Ѳ(п(tSk)) не меняется с момента td до момента tkl+1. Длительности интервалов времени между моментами td и tk+1, t^+1 >td , k = 1, 2, ..., следующего наблюдения за состоянием работоспособности приборов систем обслуживания, являются независимыми экспоненциально распределенными случайными величинами с параметром А. Полагаем также, что длительности интервалов времени между моментами tSk и td , k = 1, 2, ..., являются независимыми экспоненциально распределенными случайными величинами с параметром т. В качестве критерия оптимальности функционирования сети обслуживания установим равенство математических ожиданий (м.о.) длительностей пребывания требований в системах массового обслуживания, т.е. = U, i = 1, ..., L, где U - некоторое заданное значение. Задача оптимизации 92 Метод анализа сетей массового обслуживания с ненадежными приборами и задержкой информации заключается в определении маршрутной матрицы &(n(tk)), к = 1, 2, ..., которая обеспечивает выполнение критерия оптимальности функционирования сети обслуживания. Целью работы является нахождение вероятностно-временных характеристик сети обслуживания с ненадежными приборами в системах обслуживания и с задержкой в принятии решения об изменении потоков требований. 2. Решение задачи оптимального управления маршрутными матрицами Пусть ц - интенсивность обслуживания требований прибором системы, X - интенсивность потока требований в систему обслуживания. Тогда м.о. длительности пребывания требований в системе обслуживания типа M/M/1 определяется выражением и = 1/ (ц - X). Определим м.о. длительности пребывания требований в экспоненциальной системе обслуживания с двумя приборами, используя выражения для системы с числом приборов к > 2. Для этого используем формулу Литтла и = (b + h) / X, где b - м.о. числа требований в очереди системы, h - м.о. числа занятых приборов системы, определяются соотношениями b = P(0) ч2 , h = Ук , к!(1 -у)2 P(0) = (ку)К к!(1 -у) + g(ку) =0 П! -1-1 где у = X/кц - коэффициент использования системы, -Р(Ѳ) - стационарная вероятность того, что в системе нет требований. Тогда, при к = 2 2ц-X P(0) = и = P(0) X2 2ц + X ’ 1_ 4ц ц(2ц-Х)2 ц 4ц2 -X2' Следовательно, необходимые интенсивности потоков требований в системы с одним и с двумя приборами соответственно, обеспечивающие заданное U , определяются соотношениями X(1) = ц- 1/ U, X(2) = уІ4ц(ц-1/ U) . Используя метод синтеза маршрутных матриц сетей обслуживания [17] для известного вектора ю относительных интенсивностей потоков требований, можно получить маршрутную матрицу Ѳ, удовлетворяющую системе уравнений юѲ = ю с условием нормировки I 1=0 ю =1. 3. Анализ ненадежной системы и сети обслуживания с учетом задержки в управлении потоком Введем обозначение (a., nt (t), nt (tk), c(t)) для определения числа работоспособных приборов и параметров управления потоком в систему Si, i = 1, ..., L, где at - состояние потока (at = 2 - поток в систему обслуживания установлен из расчета, что в этой системе работоспособны оба прибора, т.е. интенсивность такого потока равна Xt (2); если at = 1, то интенсивность потока в систему Si равна Xt (1); П (t), n (tk) - состояния работоспособности приборов системы соответственно в текущий момент времени t и в момент tSd , tSd < t; c(t) - параметр управления, который равен d, если в момент t, t е [ tSd, tkd ), принимается решение об интенсивности потока требований в систему. Параметр c(t) = s, если t е [ t'd , tSd+1). 93 И.Е. Тананко, Н.П. Фокина Из всех возможных 16 состояний (a;,nt(t),nt(tks),c(t)) системы Si, i = 1, ..., L, состояния (1, 2, 2, 5), (1, 1, 2, 5), (2, 2, 1, 5), (2, 1, 1, 5) являются невозвратными. Остальные образуют класс положительных возвратных состояний, вероятности которых могут быть найдены из решения системы линейных уравнений (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) -(аг + т)Р (2,2,2, d) + PP (2,1,2, d) + ДРІ (2,2,2, s) = 0 , -(Р; + т) р (2,1,2, d) + а р (2,2,2, d) = 0, (аг + Д)Р (2,2,2, s) + тРг (2,2,2, d) + РР (2,1,2, s) + тРг (1,2,2, d) = 0, -(Д + Рг)Р(2,1,2,s) + тр(2,1,2,d) + агр(2,2,2,s) + тр.(1,1,2,d) = 0 , -К + т)Р (1,2,2, d) + РР (1,1,2, d) + Щ (1,2,1, s) = 0 , -(т + Рг )Р (1,1,2, d) + ар (1,2,2, d) = 0, -(Р; +т)Р(1,1,1,d) + а;Р(1,2,1,d) + ДР-(1,1,1,s) = 0 , -(«;■ + т)Р (1,2,1, d) + Р;Р (1,1,1, d) = 0, -(а; + Д)Р (1,2,1, s) + тР (1,2,1, d) + Р;Р (1,1,1, s) + тР (2,2,1, d) = 0, -(Д + Р; )Р (1,1,1, s) + тР (1,1,1, d) + а,Р (1,2,1, s) + тР (2,1,1, d) = 0, -(Р; + т)Р (2,1,1, d) + а;Р (2,2,1, d) + ДР (2,1,2, s) = 0, -(а; +т) Р (2,2,1, d) + Р;Р (2,1,1, d) = 0 с условием нормировки Jaf, П; ,c Р(а; , П; (t), П; ^ ), С) = 1 . (13) Поскольку система обслуживания Si, i = 1, ..., L, характеризуется потоком требований с двумя возможными интенсивностями, а также числом работоспособных приборов, то изменение числа требований в системе представляется случайными процессами рождения и гибели ^(a.,n.), a; = 1, 2, П = 1, 2. Введем обозначения для стационарных вероятностей того, что в системе обслуживания Si, i = 1, ..., L, осуществляются соответственно процессы £;.(2,2), £;.(2,1), Е>і(1,2), £;.(1,1) : Я;. (2,2) = Р (2,2,2, d) + Р (2,2,2, s) + Р (2,2,1, d), К; (2,1) = Р (2,1,2, d) + Р (2,1,2, s) + Р (2,1,1, d), Я; (1,2) = Р (1,2,1, d) + Р (1,2,1, s) + Р (1,2,2, d) , К; (1,1) = Р (1,1,1, d ) + Р (1,1,1, s) + Р (1,1,2, d ) . Следующие предложения содержат утвержения о свойствах рассмотренных вероятностей. Предложение 1. Вероятность Р(2,1,2,s) = Р(1,2,1,s) , i = 1, ..., L. Доказательство. Воспользуемся методом Крамера для решения системы линейных уравнений (1)-(13). Можно показать, что определители матриц, получаемых заменой соответствующих столбцов на столбец свободных членов, равны друг другу и равны а;Р;Дт4(а; +Р; +т)2(а; +Р; + Т + Д)2 , i = 1, ., L, откуда следует требуемое равенство. Что и требовалось доказать. Предложение 2. Вероятность действия процесса 4;- (2,1) в системе обслуживания Si равна вероятности действия процесса ^(1,2) в этой системе обслуживания, т.е. л.(2,1) = к■ (1,2) , i = 1, ., L. Предложение 3. Вероятность того, что в систему Si поступает поток требований с интенсивностью р (2), равна вероятности того, что ненадежный прибор этой системы работоспособен, т.е. i = 1, -.., L. К; (2,2) + К; (2,1) К; (2,2) +К; (1,2) , Предложение 2, так же как и Предложение 1, доказывается с использованием свойств определителей. Предложение 3 непосредственно следует из Предложения 2. Можно показать также, что 94 Метод анализа сетей массового обслуживания с ненадежными приборами и задержкой информации пг (2,2) + Я,. (2,1) = рг/(«,. +Рг) и %,(1,1) + %,(2,1) = аг/(аг +рг), і = 1, ..., L. Обозначим q = (qt) - вектор состояния сети обслуживания, где qt - число требований в системе Si; (a,n) - вектор состояния потоков требований и числа приборов в системах сети обслуживания, где a = (ai), n = (nt), i = 1, ..., L; P(q, a, n) - стационарная вероятность пребывания сети обслуживания в состоянии q с вектором состояния потоков а и вектором n числа приборов в системах обслуживания, определяемая по теореме Джексона [18]. Тогда стационарная вероятность п(а, n) того, что сеть обслуживания находится в состоянии (a, n), определяется выражением %(а,п) = 7iL(aL,nL). Стационарная вероятность состояния q сети массового обслуживания с ненадежными приборами и с задержкой информации имеет вид: P(q) = Za,np(q,а,п)к(a,n), q eE, где E - множество всех состояний сети обслуживания. Заключение Сети массового обслуживания с переменной структурой и задержкой в принятии решений, связанных с управлением потоком требований, могут быть использованы не только для анализа стохастических сетевых систем с физическими отказами и восстановлениями отдельных элементов, но также для анализа и разработки методов управления системами, в которых каждый элемент является неделимым общим ресурсом определенного множества пользователей. К таким системам можно отнести, например, некоторые производственные и транспортные системы, сети передачи информации, конфигурируемые вычислительные и информационные ресурсы, на которых основаны, в частности, технологии «облачных вычислений».

Скачать электронную версию публикации