Открытые неоднородные сети массового обслуживания с возможностью внутренних изменений в узлах

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
2010 Управление, вычислительная техника и информатика № 2(11)
УДК 519. 2
Ю. В. Малинковский, Ю. Е. Летунович ОТКРЫТЫЕ НЕОДНОРОДНЫЕ СЕТИ МАССОВОГО ОБСЛУЖИВАНИЯ С ВОЗМОЖНОСТЬЮ ВНУТРЕННИХ ИЗМЕНЕНИЙ В УЗЛАХ
Исследуется открытая сеть массового обслуживания с простейшим входящим потоком, экспоненциальным обслуживанием в узлах и марковской маршрутизацией. В сети циркулируют заявки нескольких типов. В каждом из узлов сети находится единственный прибор, который может работать в нескольких режимах. Время пребывания в каждом режиме имеет показательное распределение. Переходы возможны только в соседние режимы. Во время переключения режимов число заявок в узле не меняется. Устанавливаются условия обратимости, при выполнении которых стационарное распределение вероятностей состояний сети имеет мультипликативную форму.
Ключевые слова: сеть массового обслуживания, стационарное распределение, обратимость.
Изучение систем и сетей с многорежимными стратегиями обслуживания представляет большой интерес, поскольку зачастую на практике возникает ситуация, когда оборудование может частично или полностью выходить из строя. Попытка построения таких моделей была предпринята в работе [1]. В ней рассмотрена открытая сеть с многорежимными стратегиями обслуживания, в которой циркулируют заявки одного типа. Настоящая работа обобщает результаты, полученные в [1], на случай, когда в сеть поступают заявки нескольких типов.
Таким образом, исследуется открытая неоднородная сеть с многорежимным обслуживанием. Рассматриваемые режимы отвечают разной степени работоспособности узлов сети. При переходе в режим с большим номером, в менее «надёжный» режим, производительность узла уменьшается. Прибор не выходит из строя полностью. Прибор может частично терять работоспособность как при обслуживании, так и в незанятом состоянии.
Для рассматриваемой сети допускается наличие внутренних изменений в узлах. Под внутренними изменениями будем понимать переходы обслуживающего устройства из одного режима работы в другой. На практике это может означать возможность поломки или восстановления устройства без воздействия внешних факторов.
При описании состояния узла были введены обозначения, аналогичные обозначениям, введённым в работе [2]. Состояние описывается произвольно и может не совпадать с числом заявок определённого типа в узле. Такое описание позволяет упростить процесс обращения времени и обобщить модели сетей с многорежимным обслуживанием, которые были рассмотрены авторами ранее.
1. Изолированный узел
Рассмотрим одноканальную экспоненциальную систему массового обслуживания с ожиданием, в которую поступают М независимых пуассоновских потоков с
параметрами аи, и = 1, М. Здесь аи есть интенсивность поступления заявок типа и.
В системе находится единственный прибор, который может работать в г+1 режимах. Назовём 0 основным режимом работы. Время переключения с одного режима на другой имеет показательное распределение. Во время переключения прибора с одного режима работы на другой число заявок в системе не меняется. Переключение происходит только на соседние режимы.
Состояние системы будем описывать абстрактно, и состояние системы может не совпадать с числом заявок в ней. Пусть х (ґ) — состояние системы в момент времени ґ. Обозначим через Х (- число заявок типа и, и = 1, М, в системе, которая
функционирует в 1-м режиме и находится в состоянии х. Предполагаем, что х (ґ) -однородный марковский процесс с фазовым пространством X.
Пусть пи (х, х) — условная вероятность того, что система перейдёт в состояние
X, если в неё поступит заявка, заставшая его в состоянии х, |х| 1и = |х|и +1- ци (х, х)
— интенсивность перехода из х в х за счёт ухода заявок типа и из системы,
|х|1 = х1 -1, х1 Ф 0.
I 1и I I и I I и
В рассматриваемой системе предполагаются возможными внутренние переходы из состояния х в другое состояние х, но с тем же числом заявок
/ І '-~|/+1 I |/ І '-~|/ -1 I |1
(|х|и = |х|и, |х|и = |х|и, х Ф х). Это значит, что такие переходы связаны не с поступлением или обслуживанием заявок, а с переходами системы из одного режима работы в другой. Для состояний х, у которых номер режима 1 & lt- / & lt- г — 1, время пребывания в режиме / имеет показательное распределение. При этом с интенсивностью v (x, х) прибор переходит в /+1-й режим, а с интенсивностью ф (х, х) — в /-1-й режим. Предполагается, что V (х, х) =0, когда система находится в режиме г, и ф (х, х) =0, когда система функционирует в режиме работы 0.
Предполагается, что введённые параметры выбраны таким образом, что процесс х (ґ) эргодичен. Тогда финальное распределение является единственным стационарным распределением.
Введём следующие обозначения
О+ (и,/, х) = { х є X: |х|и = |х|и +1- |х| 1 т = |х|гт, т є {1,2,…, М} {и}} ,
О-(и,/, х) = { х є X: |х|г = |х|г — 1- |х|г Ф 0, |х|г = |х|г, т є{1,2,…, М }{и}},
V'' / (ІІи 11и Ч1и '11т 11т' *,???
(c)+ (и,/, х) = { х є X: |х|и+ = |х|и -/ Ф г, |х|5 = |х|и, х Ф х, 5 є {0,1,…, г} {/}},
(c) — (и,/, х) = { х є X: |х|и1 = |х|и-/ Ф 0, |х|и = хи, х Ф х, 5 є {0,1,…, г}{/}}.
Обозначим через р (х) стационарные вероятности состояний марковского процесса х (ґ). Уравнения обратимости для рассматриваемой системы запишутся в следующем виде:
аипи (х, х) р (х) = ци (х, х) р (х), х є О+ (и, /, х), и = 1, М- v (x, х) р (х) = ф (х, х) р (х), х є (c)+ (и,/, х), и = 1, М.
Обозначим через у1к — состояние системы с числом заявок типа и, равным |у? | = К, находящейся в режиме работы /.
Лемма. Для обратимости системы необходимо и достаточно выполнения условий
п ((1, у*-1)(У-1, у[ы)^и (у{ы, Уи -1)ф (ук -1, У--1) =
=пи (-1, У*и)-((, у*:1 К ((1, у*: -1 Му*: -1, у" -1
Доказательство леммы аналогично соответствующему доказательству в [1].
Из уравнений обратимости легко определяются стационарные вероятности состояний системы:
м к ап (у*, у*) I V (у0−1 у0)
р (х)=ПП и & quot-(^У*и"-,)П-У^)(*),
и (, Укы -1) *=1 -(, Уо)
и =1 К =
х, 2, у[ є X, г = 0.
Здесь 2 — такое состояние системы, когда в ней отсутствуют заявки, и система работает в основном режиме 0. Вероятности р (х) не зависят в силу обратимости системы от выбора пути, приводящего из состояния, когда система пуста, в состояние х.
2. Склеивание узлов в открытую сеть
Рассмотрим сеть, состоящую из N обратимых однолинейных узлов со структурой, определённой в предыдущем пункте. Это означает, что пи (х, х), Н (х, х), v (x, х), ф (х, х) такие же, но снабжены индексом і, указывающим номер узла. В
сеть поступает простейший поток заявок с параметром X. Заявки могут быть М типов. Каждая заявка входного потока независимо от других заявок направляется
(N М Л
в і-й узел и становится заявкой типа и с вероятностью р0(і, и) І ЕЕ р0(і и) = 11. По-
V і =1 и=1)
сле обслуживания в і-м узле заявка типа и независимо от других заявок мгновенно направляется в ]-й узел и становится заявкой типа V с вероятностью р^"^", а с ве-
(N М ___ ____Л
роятностью р (іи)0 покидает сеть
ЕЕ р (і, и)(і, v) + р (і, и)0 =1-і = і, N, и = IМ
Vі=і
Будем предполагать, что матрица переходов (р (-, и)(/, у)), и, V = 1, М, /'-, ] = 0, N, Р (0,и)(0у& gt- = 0 неприводима. Тогда уравнение трафика
N М ____ _____
8и = Р0(г, и) + XX 8/уР (/, v)(г, u), 1 1 N, и = 1 М, (1)
/=1 v=1
имеет единственное решение (8и), для которого е, и& gt-0 (/ = 1, N, и = 1, М). Обозначим через аи= Я, 8,-и среднюю интенсивность поступления заявок типа и в г'--й узел.
Состояние сети в момент времени t описывается вектором х^^х^О, х2(^,…, х^)), где х (Г) — состояние г-го узла в момент времени t. Очевидно, x (t) — однородный марковский процесс с фазовым пространством Х=Х1 хХ2х… хХдг
Пусть пги (х., х) — условная вероятность того, что узел перейдёт в состояние
х, если в него поступит заявка, заставшая его в состоянии хг, |х ||| = х^ +1.
Здесь х^' - число заявок типа и в 1-м узле, который функционирует в режиме к,
когда система находится в состоянии х. Пусть цім (х, х) — интенсивность перехо-
В каждом узле предполагаются возможными внутренние переходы из состояния хг в другое состояние х, но с тем же числом заявок
поступлением или обслуживанием заявок, а с переходами системы из одного режима работы в другой. Для состояний хі, у которых номер режима 1 * Іі * Г -1, время пребывания в режиме Іі имеет показательное распределение. При этом с интенсивностью V і (х., х) прибор переходит в І+1-й режим, а с интенсивностью ф і (х, X) — в Л-1 -й режим. Предполагается, что V і (х., х) =0, когда система находится в режиме г «и ф і (х., х) =0, когда узел функционирует в режиме работы 0.
Инфинитезимальные интенсивности перехода системы из состояния хі є X і в состояние X є Xi (хі Ф х) принимают следующий вид:
живания -м узлом заявок типа и, когда он находится в состоянии х —
счёт повышения номера режима функционирования -го узла-
нижения номера режима функционирования -го узла. Здесь в суммах 0+У, и, 1 г, хг), О- (, и, 1 г, хг), (c)+ у, и, к, хг), (c)-('-, и, кг, хг) указывают, что суммирование ведётся по X, принадлежащему одному из определённых множеств. Множества 0+ (, и, кг, хг), О-(, и, к, хг), (c)+(, и, к, хг), (c)-(, и, к, хг) вводятся так же, как и в пункте 1, но с указанием номера узла.
Предполагается, что введённые параметры выбраны таким образом, что процесс х (0 эргодичен. Тогда финальное распределение является единственным стационарным распределением.
Согласно предыдущему пункту, стационарное распределение состояний изолированного узла (-го узла сети) находится по формуле
да из хі в X за счёт ухода заявок типа и в і-м узле, |Х '-
(|Х и+1 = їх Iі'-, |х И 1 = їх Iі'-, X Ф х). Это значит, что такие переходы связаны не с
I * и I * и I * и I * и II'- а
я,(х, х)-і '1(х, х), х ^+(кик, х^
0, в остальных случаях.
фг- (х) = Е (c)-(и І х) фг- (х, х) — интенсивность выхода из состояния хі за счёт по-
Здесь і і - такое состояние і-го узла, когда в нём отсутствуют заявки, и система находится в основном режиме работы 0.
3. Основной результат
Обозначим через [х ] Х-мерный вектор х, у которого все координаты, кроме і-й, совпадают с координатами вектора х, а і-я координата равна х. Через [хі, х- ] обозначим Х-мерный вектор х, у которого все координаты, кроме і-й и --й, совпадают с координатами вектора х, а і-я координата равна х, І-я координата равна х^. Если я (х, у) — интенсивность перехода процесса х (ґ) из состояния х в состояние у, я (х) = ХуФХЯ (х, У) — интенсивность его выхода из состояния х, то интенсивности перехода процесса х (ґ) имеют следующий вид:
я (х[х ]) = ^0(г, и) Пи (х, х), х є О+ (i, и,Іі, х) — я (х [х ]) = Ни (х, х) Рс, и)0^^ ФО], х є °- (, иІі, х) —
я (х[х]) = (х, хУ^г]х ^(їиІі, х) — (3)
я (х[х]) = ф (х, х)1[ііф0], х є ® — ((иІі, х) —
я (х,[х, X-]) = Ни (х, X^Р (г, и)(П (х-,) 1 [(хіифо],
х є О- (,'-, І, х), х- єП+(І, V, І -, х-), і, І - 1, Х.
Для всех иных состояний у я (х, у)=0. Интенсивность выхода получается сложением указанных интенсивностей:
Х М Х
я (х) = ь + XX Ни (х)1 [|х-|1, — фО] + X [ (х)1[ііФГі] + Ф (х)1[ііФО] ].
і-1 и-1 ^ 1 и ] і-1
Теорема. Если все изолированные узлы удовлетворяют условию обратимости
п и (у (11,(, уік) н и (уік, уік -1) фг () —
— и (-1, у'-к)ф (, У-)н и (у (, (у (11, у’к -),
то стационарное распределение сети имеет мультипликативную форму
р (х) — д (х)Р2(х2)… Рх (хх), (4)
где р і (х) — стационарное распределение изолированного узла, определяемое с помощью (2).
Доказательство. Для доказательства того, что р (х), определённые в (4), образуют стационарное распределение марковского процесса х (ґ), достаточно подобрать функцию
як: (X, X) {х, х), х є X} - [О, да), которая удовлетворяла бы соотношениям
Р (х)яК (х, у) — Р (у)я (у, х) — (5)
яК (х) -X яК (х, у) -X я (х, у) — я (х). (6)
уф х уф х
Если такие д*(х, у) удастся найти, то окажется, что д*(х, у) являются инфините-зимальными интенсивностями перехода для обращенной во времени цепи Маркова х (-), ар (х) — стационарными вероятностями для х (0 и х (-). Положим
(X, [хг ]) = агпПи (хг, хг) Р (г, и)0, X 6 0+ (', U, 1 г, х1) —
/ (X, [X ]) = ^ а, х'-) ХР0(г, и)7[|х,.к, 0], х 6 0 (Хг ,) —
/ (X, [хг ]) = ^(хг, х)1[, г ] х 6(c)+У, U, кг, хг) (7)
(x, [х ]) = Ф (хг, х)1[, 0] х 6 (c) — У, U, кг, х) —
д* (х, [х, х- ])=ЦШ ах ,) Р (№, и)"^vП] (, х])1Пх,. и, —, 0] ,
аги Г '-1и ]
хг бО-У'-, и, к, хг), х^ б0+ (_/'-, V, I/, х--).
Для всех иных состояний у положим д*(х, у)=0. Для функции д*(х) соотношение (5) выполняется, что проверяется подстановкой в него равенств (3) и (7) и использования (4). Осталось доказать (6). Складывая равенства (7), имеем
N М N М. (х х)
д* (х)=ХХ X аги Пи (х, х) Р (г, и)0 +ХХ X „(г, '-) Х Р0(г, и), 01 +
г=1 и=1. хг-б0+Х, и, 1 г, х,) г=1 и=1 х (б0~у, и, х,) аги Г и
N N
+Х X V (хг, х)1[г,. *т,]+Х X Фг (хг, х)1[, 0] +
г=1 х б (c)+Х, и, кг, х,) г=1 хс{ б (c)-у, ик, х,)
N М N М и (х х)
+ХХ X XX X & quot- а. г, г ^ ^)(г, и) а/V П (^ УГх^и, 01 =
г=1 и=1 х,-б0 Х, ик, хг-)]=! х]б0+(& gt-,/], х/) г и
=^+ХХ X
г=1 и=1 х, 60 Х, ик, х,) а
Иг'-и (хг, х)) V'- / ~ О
Р0(и) +ХХ X Р (], v)(г, u) а/VП^ Iх/, Х/)
/=1 v=1 х]б0+(./ У к], х/)
V
N N
+ХУг (хг)1[к,-, г] +ХФг (хг)1[, 0].
/[1 ,°] +
г=1 г=1
Используя уравнения трафика (1), получим
N М и (х х) N N
д* (х) = Х + ХХ X Ш аг, г) аги1 [|х. |и, 01 +ХУг (хг Уй, г,] + Хфг (хг, 0] =
г=1 и=1:г. б0-у, и,//, х) Г г1и ] г=1 г=1
N М N N
= Х + ХХИги (хг, 0] +ХУг (хг У[ЬЩ] +Хфг (хг У[Ь, 0].
г=1 и=1 Г 1 и ] г=1 г =1
Таким образом, д*(х)=д (х) для любого состояния х 6 X. Теорема доказана.
4. Примеры
Пример 1. Рассмотрим частный случай исследованной выше сети: открытую неоднородную сеть с многорежимными стратегиями обслуживания, заявки в которой выбираются из очереди согласно дисциплине обслуживания ЬСБ8 РЯ с до-обслуживанием. Такая модель сети рассматривалась в [3]. Интенсивность обслу-
живания заявки типа и і-м экспоненциальным прибором равна ціи (хг), где х,= (хі1, хі2,, хія (і), Іі) — состояние і-го узла. Здесь хг1 — тип заявки, находящейся
последней в очереди, …, хі, и (і)_і - тип заявки, стоящей первой в очереди, хі и (і) — тип заявки, находящейся на обслуживания, Іг — режим, в котором работает і-й узел, п (і)
— число заявок в і-м узле. Условия обратимости принимают вид
V (^ (2 — х, пО& gt- Іг — !)), х) (хги хі2 ,…, X, n (г), Іг)ф& lt- (хги хг 2,…, х^г)-^Іг) =
= V ((2 ,…, х^г)-^Іг -1)Н, х) (X¦1, (2 ,…, хі, пС0& gt- Іг -1)фг) (2 ,…, хгМГр Іг).
Здесь вероятность П и (х, х) =1.
Из уравнений обратимости, которые для данной модели сети запишутся в виде
Хєі, х,"(і) Рг (хі1, Xi2,…, хі, п (і)-1,Іг) =
= Р і ((X 2 ,…, хі, п (і), Іг), х) (^ X 2 ,…, хі, п (і), Іг),
V (Xl, х^. -хі, п (і), Іг) Рг (хги хі2 ,…, хі, п (і), Іг) =
= Р г (хг ^ х 2 — хі, п (і), Іг + 1) Ф! (Xl, х 2 ,…, хі, п (і), Іі + 1),
находим стационарное распределение вероятностей состояний изолированного узла
р. (хг) = Г (г)П-------------^-----------П ^(0, к — :) Рі (0,0).
Д ^ ІІ Н, х“ (1, х-2,…, х», Іг) Фг (0, к) РЛ ' '-
Стационарное распределение сети получается умножением найденных вероятностей по всем і = 1, N.
Пример 2. В работе [4] рассматривается открытая неоднородная сеть с многорежимным обслуживанием. Обслуживание в узлах осуществляется согласно дисциплине разделения процессора с весами.
Состояние сети в момент времени ґ будем характеризовать вектором х (0 = (х (ґ), х2 (Ґ),…, XN (ґ)), где х (Ґ) = (х (ґ), Іг (Ґ)) = (^(ґ), хп (ґ),…, хш (ґ), і. (ґ)) описывает состояние і-го узла в момент времени ґ. Здесь хіи (ґ) — число заявок и-го типа в і-м узле в момент времени ґ, І. (ґ) — режим, в котором работает і-й узел в момент времени ґ. Времена обслуживания заявок независимы, не зависят от процесса поступления и для заявок и-го типа в -м узле имеют показательное распределение с параметром ц іихи, х. — общее число заявок в і-м узле.
х
Условия обратимости принимают вид
V (хги х2 — хм ,Іг — 1) Фг (Xl,…, хги + ^ хгМ ,Іг) =
= V (Xl,…, хги +1,…, Хм, Іг -!) фг (х 1, х 2, & quot-^ хМ, Іг).
Здесь вероятность п и (х, х) =1, ци (хі, х)=цИхи +1.
х +1
Уравнения обратимости для данной модели сети запишутся в виде
а і и Рі (х^.^ х и^ хм, Іг) =
Цги-Рг ((и хг 2 ,…, хМ, Іг), и = 1 M, 1 г = 0, ^ - х
V (Х-1& gt-X2,•••, xM, h) Pi (xi1& gt-X2,•••, Xm, li) =
Фг ((1& gt- X 2 '•••, XM, li + 1) (1& gt- X 2 '•••, XM, li +1) li = 0, ^ -1
Стационарное распределение вероятностей состояний изолированного узла
Стационарное распределение сети получается умножением найденных вероятностей по всем I = 1, N.
В настоящей работе исследована неоднородная сеть с экспоненциальным обслуживанием в узлах и марковской маршрутизацией. Однолинейные узлы могут работать в нескольких режимах, отвечающих различной степени работоспособности. Время переключения с одного режима на другой имеет показательное распределение. Переключение происходит только на соседние режимы. Установлены достаточные условия мультипликативности стационарного распределения состояний сети.
1. Малинковский Ю. В., Нуеман А. Ю. Мультипликативность стационарного распределения в открытых сетях с многорежимными стратегиями обслуживания // Весщ НАН Беларуси 2001 № 3. С 129 — 134
2. Малинковский Ю. В. Критерий представимости стационарного распределения состояний открытой марковской сети обслуживания с несколькими классами заявок в форме произведения // Автоматика и телемехани^ 1991 № 4 С 75 — 83.
3. Летунович Ю. Е. Стационарное распределение состояний открытой неоднородной сети с многорежимными стратегиями и немедленным обслуживанием // Современные информационные компьютерные технологии: сб. науч. ст Гродно, 2008. С 97 — 99.
4 Летунович Ю. Е. Открытые неоднородные сети с многорежимными каналами и дисциплиной обслуживания PS // Юбилейная научно-практическая конференция: материалы конф. Гомель, 2009. Ч. 4 С. 141 — 144 •
Малинковский Юрий Владимирович
Летунович Юлия Евгеньевна
Гомельский государственный университет им^ Ф^Скорины
E-mail: Malinkovsky@gsu. by- yu28031984@yandex. ru Поступила в редакцию 8 февраля 2010 г
Заключение
ЛИТЕРАТУРА

ПоказатьСвернуть
Заполнить форму текущей работой