Analysis in non-stationary regime of exponential G-network with bypass of queueing systems positive customers.pdf СеМО с положительными и отрицательными заявками были введены Э. Геленбе [1, 2]. Основное применение данной сети в качестве модели заключается в ее использовании при моделировании воздействия компьютерных вирусов на исполняемые программы, на сервер или локальный компьютер пользователя. В переходном режиме данная сеть была исследована в работе [3]. Экспоненциальная СеМО с обходами узлов заявками была введена в [4]. В этой работе показано, что такая модель включает возможность обхода систем за счет ограничений на количество заявок или на предполагаемое время ожидания. В ней найдены стационарные вероятности состояний сети в форме произведения. В переходном режиме сеть с обходами была исследована в работе [5]. Применение сети с обходами связано, например, с возможностью клиента, прибывшего в сервисный центр информационной сети, не присоединяться к очереди по тем или иным причинам, а перейти в другой сервисный центр. В данной работе рассматривается открытая СеМО с отрицательными заявками и обходами узлов положительными заявками, которые учитывают первые две особенности, причем обход систем обслуживания осуществляется только положительными заявками. В стационарном режиме они были исследованы в работе [6]. Ниже для нахождения нестационарных вероятностей состояний сети предложено использовать метод многомерных производящих функций. 1. Система РДУ для вероятностей состояний Рассмотрим открытую экспоненциальную СеМО с однотипными заявками, состоящую из n однолинейных СМО. Состояние сети в момент времени t описывается вектором размерности п + 1: к = k(t) = {k,t^ = (k],k-1,...,kn,l j, который образует цепь Маркова с непрерывным временем и счетным числом состояний, где состояние (k , t) означает, что в момент времени t в /-й СМО находятся к положительных заявок, i = 1, n . 66 Анализ в нестационарном режиме экспоненциальной G-сети В i-ю систему из внешней среды поступает простейший поток положительных заявок с интенсивностью ^+, и простейший поток отрицательных заявок с интенсивностью X-t , i = 1, n . Все потоки заявок, которые поступают в сеть независимы. Длительности обслуживания положительных заявок в i-й СМО распределены по показательному закону с параметром р,., i = 1, n . Положительная заявка, направленная в і-ю СМО извне или из другой системы, когда сеть находится в состоянии к , с вероятностью f'"(kj) присоединяется к очереди, а с дополнительной вероятностью 1 - f(i)(ki) не присоединяется к очереди, считаясь мгновенно обслуженной (т.е. обходит СМО). Положительная заявка, обслуженная в СМО S,., с вероятностью р+ направляется в СМО Sj как отрицательная, и с вероятностью как положительная заявка, а с вероятностью p n _ pi0 = 1 - ^ (Р+ + Р- ) уходит из сети во внешнюю среду (в СМО S0), i, j = 1, n . j=i Отрицательные заявки представляют собой особый тип заявок: они не обслуживаются и поступают непосредственно в СМО (для них f(')(kt) = 1), где уменьшают длину очереди на единицу, если число заявок в системе больше нуля, и не производят никаких изменений, если в СМО нет заявок. После указанных операций отрицательные заявки исчезают и в дальнейшем не оказывают влияния на сеть. Пусть ф, ^А" j - условная вероятность того, что заявка, поступающая в і-ю СМО, когда сеть находится в состоянии к , не будет обслужена ни одной из СМО и не изменит состояние сети; \\|/)( ^A:j -условная вероятность того, что положительная заявка, поступающая в і-ю СМО, когда сеть находится в состоянии к , впервые получит обслуживание в /-и СМО, j = \\,п ; Ъ,у[к^ - условная вероятность того, что заявка, прибывшая извне в і-ю СМО, когда сеть находится в состоянии к , впервые окажет воздействие на j-ю СМО как отрицательная заявка, / = 1./? ; ос, - условная вероятность того, что заявка, обслуживание которой в /-й СМО завершено, когда сеть находится в состоянии к , не будет больше обслужена ни в одной из СМО и уйдет из сети; Р;/ ^А" j - условная вероятность того, что заявка, обслуживание которой в /-й СМО завершено, когда сеть находится в состоянии к , впервые после этого получит обслуживание в j-й СМО, i,j = \\,n ; уу{к^ - условная вероятность того, что заявка, обслуженная в і-й СМО, когда сеть находится в состоянии к, впервые окажет воздействие на j-ю СМО, будучи при этом отрицательной, i, j = 1, n . На основании формулы полной вероятности получим: i = 1, n, (1) (2) (3) (4) 3=1 Ф, р)=(і - /(,¥))f до+t[p;ф, р)+Ру (і - и (к )) / ХѴг3^)= f(f) Ф)% +(1-/г>(кЖРиЪ(к)’ kJ=l’n’ ^Р) = (1-/(і)(^)) Pp+tp-Ay(k) , i,j = \\n, i = 1, n , «,■ (*) = Pro + t p^j (* -/,■) + p- ((l - и [k})) + 5y (2 - и (к,))) 67 Д.Я. Копать, М.А. Маталыцкий Р, (£) = ZPuVij (k-It), i,j = \\,n, Уѵ(к) = Рѵ +tpn^(k-Ii), Uj = l,n.. (5) (6) i ij \\ "' I Jr'ij ' еі-/іі^>іі v 7 I=1 где by - символ Кронекера, It - нулевой вектор размерности n, за исключением компоненты с номером i, которая равна 1, u(x) - единичная функция Хевисайда: 1, х > 0, [0, х< 0. Пусть P{k,t j - вероятность состояния сети к в момент времени /. Нетрудно доказать следующую лемму. Лемма. Нестационарные вероятности состояний рассматриваемой СеМО удовлетворяют системе РДУ Колмогорова: dP(k,t^j '( х ) = dt “Ё хм(1-Фі(^)м(^)) + ^м(^)(1_Ри{к)) + ХоР{К) p(k,t) и(к,)Р(к-1,, t) + + ' i=1 j=1 + +Е i =1 K+±K£ji (k + Ii) + Piai (k +1г) p(k +1i,t) 3= 1 +ЕЕрЛР+/.-/,./) i=1 j =1 J (7) +Ё Ё p д a {k+,j+,i)I>{k+,j+,ij)i=1 j=1 2. Нахождение вероятностей состояний и средних характеристик сети, функционирующей в режиме насыщения Z Ч(і-Ф,^)) + ^(і-Рй(^)) + ^ Т^ + ЕКЕч'др-7-y^k-h, t) + Будем считать, что все СМО сети функционируют в режиме насыщения, т.е. kt (t) > 0 Vt > 0, / = 1, и, тогда система (7) примет вид: dp{k,tj dt i=1 j=1 + Е К+ІК£ji(k+Ii)+p,ai(k+Ii) p(k+i,d) 3= 1 П П \\ , П П \\ , +E E pA. [k+h ~ 7< )p [k+h ~ 7< ’ ■f)+E E PA* (k+7j +Ir)p(k+к +Ird)- (8) i=1 j=1 j ^l i=1 j=1 Для решения этой системы применим метод многомерных производящих функций. Обозначим через Ти (z, t), где z = (z1, z 2,.., zn ), n-мерную производящую функцию: да да да да да да n * n(z, t) = ЕЕ... Е р(а k2,.., kn, t)zk *2 ■... ■ zt" = ЕЕ... Z p(k t)n zii, N ОГК = Ё^Ё ч'.л,, КО; i=1 j=1 k1 =1 kn =1 l=1 i=1 j=1 Ё 2 (z,t) = Ё i=1 ^о,-+Ё^0 j ^ ji+Pi( j=1 СО СО n n 1 n £...ZpP+v)rK' =z-(k,+Z^ k1 =1 kn =1 l =1 i=1 zi j=1 j, + P,a, )Tn (z, t), так как вероятности типа P (k, к,..., =._j, 0, kM,..., к ) = 0, поскольку сеть функционирует в режиме насыщения; ад ад i,j=1 = =1 =n =1 ZsM=ZkAZ-Z^4-о 0, P (a1, a2,..., an ,0) = 1, P (k1, k2,..., kn ,0) = 0 , Va. Ф kt, i = 1, n . Тогда начальным условием для n n уравнения (12) будет T п (z,0) = P(a^ a2,..., an ,0)^ z^1 =^ z^1 . Используя его, получаем Ся = 1 • i=1 i=1 Таким образом, если в начальный момент времени СеМО находится в состоянии (^, х2,..., хп,0), x > 0, i = 1,n , то выражение для производящей функции Tn(z,t) (12) имеет вид: a 69 Д.Я. Копать, М.А. Маталыцкий где ^n (Z О = a0 (') exp x exp < < Z^zZv* t i=1 j=1 J ^ n -7 Z^jP if i,J=1 ZJ І n 1 n eXP\\Z ~(X0i +Z^Oj \\ Ji +^iai) ' [ i=1 Zi J=1 1 eXP \\Z^J У Ji- ' Zl‘ , I i,J=1 ZiZJ x (13) a0 (') = exP j -Z (X°i (1 “ Ф ) 0 ^ (1 - Pii ) + X-i ) Для нахождения вероятностей состояний сети преобразуем (13) к удобному виду. Разложим в ряд Маклорена входящие в него экспоненты и преобразуем полученные после этого произведения. Тогда справедливо следующее утверждение. Теорема. Выражение для производящей функции представимо в виде: СО СОСО СОСО СОСО СО П i =1 '¥n(z,t)=a«(OZ-Z Z-Z Z-Z Z-Z'~ (=0 /„=0 qx= 0 qn =0 rx=0 rn= 0 щ=0 un= 0 f f \\i f л-,1,,,. I(^У' Wii к+Zvo£jio№ n^j-Pji у. li! qi! ri! ui! J=1 V J=1 У V J =1 У V J=1 Z,(Ji + ch +rl+ul) x Oi oli - q onr -R-Ui-U , (14) n n где R = Z Г ’ U = Z ui • i=1 i=1 С помощью полученного выражения для производящей функции можно найти вероятности состояний рассматриваемой сети. Вероятность состояния P(кх,кгкп,') является коэффициентом при z*1 Zk,...,zk" в разложении функции (9) в многократный ряд (14) при условии, что в начальный момент времени сеть находится в состоянии (о,O,...,0,0) • Заключение В статье проведено исследование открытой экспоненциальной G-сети с обходами систем обслуживания положительными заявками, функционирующей в режиме насыщения. Для решения системы РДУ для зависящих от времени вероятностей состояний сети применуен метод многомерных производящих функций.

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