Investigation of HM-network with stochastic incomesfrom transitions between their states.pdf Марковские сети массового обслуживания (МО) с доходами впервые быливведены в рассмотрение в работах [1 - 3]. Они описываются с помощью цепейМаркова с непрерывным временем и доходами, введенными Р. Ховардом [4] и поэтому в последнее время называются НМ-сетями [5, 6] подобно тому, как марковские сети с отрицательными и положительными заявками, впервые введенныеE. Gelenbe, названы G-сетями. Ранее было проведено исследование замкнутых сетей с большим числом состояний и открытых сетей со счетным числом состояний; при этом были рассмотрены случаи, когда: а) доходы от переходов междусостояниями сети зависят от состояний и от времени либо б) являются случайными величинами (СВ) с известными конечными моментами первых двух порядков.Для ожидаемых доходов систем сети в случае а) можно получить системы разностно-дифференциальных уравнений, которые сводятся к системам линейныхнеоднородных обыкновенных дифференциальных уравнений (ОДУ), для решениякоторых были предложены различные методы - метод многомерных z-преобразований, а также известные методы: метод преобразований Лапласа, матричныйметод, численные методы.В [5, 7] были получены приближенные соотношения для ожидаемых доходов и дисперсий доходов в системах экспоненциальных НМ-сетей в случае б). Методика получения этих соотношений основана на разбиении интервала функционирования сети на большое число m малых интервалов величиной ƒt, оценке доходовна каждом интервале и суммировании этих доходов путем предельного переходапри m, ƒt0. При этом среднее число заявок в системах сети в нестационарном режиме находилось с помощью разработанного рекуррентного по моментамвремени метода. В данной работе предлагается метод нахождения ожидаемых доходов систем сети в случае б), основанный на решении полученных для них и для среднего числа заявок линейных неоднородных ОДУ.1. Нахождение ожидаемых доходов в системахРассмотрим открытую экспоненциальную сеть МО с однотипными заявкамипроизвольной топологии, состоящую из n систем массового обслуживания (СМО)S1, S2, , Sn с mi линиями обслуживания в системе Si, i = 1,n . Обозначим через92 Е.В. Колузаева, М.А. Маталыцкийk(t) = (k1(t), k2 (t),..., kn (t) ) - вектор состояний сети, где ki (t) - число заявок в системе Si (в очереди и на обслуживании) в момент времени t. В сеть поступаетпростейший поток заявок с интенсивностью ƒ. Условная интенсивность обслуживания заявок в момент времени t ƒi(ki(t)) в системе Si зависит от числа заявок в этой системе, i = 1,n . Заявка при переходе из одной СМО в другую приносит последней системе некоторый случайный доход и соответственно доход первой системы уменьшается на эту случайную величину.Рассмотрим -----динамику изменения доходов некоторой системы Si сети. Обозначим через Vi (t) ее доход в момент времени t. Пусть в начальный момент временидоход системы равен Vi (0)= vi0. Доход этой СМО в момент времени t- ƒt можнопредставить в видеVi (t - ҐДt) = Vi (t) - ҐДVi (t,ҐДt) , (1)где ƒVi(t,ƒt) - изменение дохода системы Si на интервале времени [t,t-ƒt). Для нахождения этой величины выпишем условные вероятности событий, которыемогут произойти за время ҐДt , и изменения доходов системы Si, связанные с этимисобытиями.1. С вероятностью Ґлp0iҐДt - o(ҐДt) в систему Si из внешней среды поступит заявка, которая принесет ей доход в размере r0i , где r0i - СВ с математическиможиданием (МО) M {r0i} = a0i , p0i - вероятность поступления заявки из внешнейсреды в систему Si , i = 1,n .2. С вероятностью Ґмi (ki (t))u(ki (t)) pi0ҐДt - o(ҐДt) заявка из системы Si перейдетво внешнюю среду, при этом доход системы Si уменьшится на величину Ri0 , где Ri0 - СВ с МО { }M Ri0 = bi0 , pi0 - вероятность ухода заявки из системы Si во внешнюю среду, i = 1,n , 1, 0, ( )0, 0, x u x x ⎧ > = ⎨ ЎВ ⎩- функция Хевисайда.3. С вероятностью Ґм j (k j (t))u(k j (t)) pjiҐДt - o(ҐДt) заявка перейдет из системы Sj в систему Si, при этом доход системы Si возрастет на величину rji , а доход системы Sj уменьшится на эту величину, где rji - СВ с МО { } M rji = a ji , pji - вероятность перехода заявки из системы Sj в систему Si, i, j = 1,n, i ЎБ j .4. С вероятностью Ґмi (ki (t))u(ki (t)) pijҐДt - o(ҐДt) заявка из системы Si перейдет в систему Sj, при этом доход СМО Si уменьшится на величину Rij , а доход системыSj возрастет на эту величину, где Rij - СВ с МО { } M Rij = bij , i, j = 1,n , i ЎБ j .5. С вероятностью 011 ( ( )) ( ( )) ( ( )) ( ( )) ( )ni i i i j j j ji j j i p ktukt k tuk t p t o t =ЎБ⎛ ⎞− ⎜Ґл - Ґм - Ґм ⎟ҐД - ҐД ⎜ ⎟⎝ ⎠ҐТна отрезке времени [t,t-ƒt) изменение состояния системы Si не произойдет, i = 1,n .Исследование НМ-сетей со случайными доходами от переходов между их состояниями 93Кроме того, за каждый малый промежуток времени ҐДt система Si увеличиваетсвой доход на величину ri ҐДt , где ri - СВ с МО M{ri} = ci , i = 1,n . Будем такжесчитать, что СВ rji , Rij , r0i , Ri0 являются независимыми по отношению к СВ ri , i, j = 1,n .Очевидно, что rji = Rji с вероятностью 1, т.е.aji = bji , i, j = 1,n. (2)Тогда из вышеуказанного следует0 00 0c вероятностью ( ), c вероятностью ( ( )) ( ( )) ( ), c вероятностью ( ( )) ( ( )) ( ), c вероятностью ( ( )) ( ( )) ( ), ( , )i i i i i i i i i ji i j j j ji ij i i i i ij i r r t p t o t R r t k t uk t p t o t r r t k t uk t p t o t R r t k t uk t p t o t V t t - ҐД Ґл ҐД - ҐД − - ҐД Ґм ҐД - ҐД - ҐД Ґм ҐД - ҐД − - ҐД Ґм ҐД - ҐД ҐД ҐД 01c вероятностью 1 ( ( )) ( ( ))( ( )) ( ( )) ( ).i i i i i n j j j ji j j i r t p ktuktk t u k t p t o t =ЎБ⎧⎪⎪⎪⎪⎪⎪⎨⎪ ҐД − ⎛Ґл - Ґм - ⎪ ⎜⎝ ⎪⎪⎞⎪ - Ґм ⎟ҐД - ҐД ⎪ ⎟⎩ ⎠ҐТ(3)При фиксированной реализации процесса k(t) , учитывая (3), можно записать{ } 0 0 0 01( , )/ ( ) ( ( )) ( ( ))ni ii i i i i i i ij ij j j i M V t t kt p a c k t uk t p b pb =ЎБ⎡ ⎛ ⎞ҐД ҐД = ⎢Ґл - −Ґм ⎜ - ⎟ ⎢⎣ ⎜⎝ ⎟⎠ҐТ1( ( )) ( ( )) ( )nj j j ji ji j j i k t u k t p a t o t =ЎБ⎤- Ґм ҐД - ҐД ⎥⎥⎦ҐТ .Усредняя по k(t) с учетом условия нормировки ( ( ) ) 1kҐТP k t = k = , для изменения ожидаемого дохода системы Si получаем{ i ( , )} ( ( ) ) { i ( , ) / ( )}kM ҐДV t ҐДt =ҐТP k t = k M ҐДV t ҐДt k t ( ) { }1 21 2 1 20 0 0... ( ) ( ( ), ( ),..., ( )) ( , )/ ( ) ( ( ), ( ),..., ( ))nn i n k k k Pkt k t k t k t M V t t kt k t k t k t ЎД ЎД ЎД= = =ҐТ ҐТ ҐТ = ҐД ҐД = 0 0 0 0 ( )1( ) ( ( )) ( ( ))ni i i i i ij ij i i i j k j i p a c p b p b P k t k k t u k t =ЎБ⎡ ⎛ ⎞= ⎢Ґл - − ⎜ - ⎟ = Ґм ⎢⎣ ⎝⎜ ⎠⎟ҐТ ҐТ ( )1( ) ( ( )) ( ( )) ( )nji ji j j j j k j i p a P k t k k t u k t t o t =ЎБ⎤- = Ґм ҐД - ҐД ⎥⎥⎦ҐТ ҐТ .94 Е.В. Колузаева, М.А. МаталыцкийПусть система Si содержит mi идентичных линий обслуживания, в каждой из которых время обслуживания заявок распределено по показательному закону с параметром Ґмi , i = 1,n . В этом случае( ), ( ) , ( ( )), () , i i i i i i i i i i k t k t m k t m k t m ⎧Ґм ЎВ Ґм =⎨ Ґм > ⎩Ґмi (ki (t))u(ki (t)) = Ґмi min(ki (t),mi ) , i = 1,n .В качестве аппроксимации среднего значения выражения Ґмi (ki (t))u(ki (t))возьмем Ґмi min(Ni (t),mi ) , т.е. воспользуемся приближенным равенствомM min(ki (t),mi ) ≈ min(Ni (t),mi ) , (4)где Ni (t) - среднее число заявок (ожидающих и обслуживающихся) в системе Si в момент времени t , i = 1,n . С учетом этого равенства получаем следующее приближенное соотношение: { } 0 0 0 01( , ) min( ( ), )ni i i i i i i i i ij ij j j i M V t t p a c N t m p b pb =ЎБ⎡ ⎛ ⎞ҐД ҐД = ⎢Ґл - − Ґм ⎜ - ⎟ ⎢⎣ ⎜⎝ ⎟⎠ҐТ1min( ( ), ) ( )nj j j ji ji j j i N t m p a t o t =ЎБ⎤- Ґм ҐД - ҐД ⎥⎥⎦ҐТ . (5)Поскольку в сеть поступает простейший поток заявок с интенсивностью Ґл , т.е. вероятность поступления l заявок в систему Si за время ҐДt имеет вид ( ) ( ) 0 0ili p t l p t P t e l Ґл ҐД −Ґл ҐД ҐД = , l = 0,1,2,... , то среднее число заявок, поступивших извне в систему Si за время ҐДt , равно Ґлp0iҐДt . Обозначим через Ґсi (t) - среднеечисло занятых линий обслуживания в системе Si в момент времени t , i = 1,n .Тогда ҐмiҐсi (t)ҐДt - среднее число заявок, покинувших систему Si за время ҐДt , а 1( )nj j ji j j i t p t =ЎБҐТҐм Ґс ҐД - среднее число заявок, поступивших в Si из других СМО за время ҐДt . Поэтому01( ) ( ) ( ) ( )ni i i j j ji i i j j i N t t N t p t t p t t t =ЎБ- ҐД − = Ґл ҐД -ҐТҐм Ґс ҐД −Ґм Ґс ҐД , i = 1,n , откуда при ҐДt Ўж0 вытекает система ОДУ для Ni (t) : 01( )( ) ( )nij j ji i i i j j i dN t t p t p dt =ЎБ=ҐТҐм Ґс − Ґм Ґс - Ґл , i = 1,n . (6)Величину Ґсi (t) найти точно невозможно и поэтому, как мы делали раньше, аппроксимируем ее выражением( ), ( ) , ( ) min( ( ), ), () , i i i i i i i i i N t N t m t Nt m m N t m ⎧ ЎВ Ґс = ⎨ > = ⎩.Исследование НМ-сетей со случайными доходами от переходов между их состояниями 95Тогда система уравнений (6) примет вид 01( )min( ( ), ) min( ( ), )nij ji j j i i i i j j i dN t p N tm Ntm p dt =ЎБ=ҐТҐм −Ґм - Ґл , i = 1,n . (7)Это система линейных ОДУ с разрывными правыми частями. Решать ее нужнопутем разбиения фазового пространства на ряд областей и нахождения решения в каждой из них. Систему (7) можно решить, например, используя средства системы компьютерной математики Maple 8.Введем обозначение vi (t) = M{Vi (t)} , i = 1,n . Из (1), (5) получаемvi (t - ҐДt) = vi (t) - M{ҐДVi (t,ҐДt)} 0 0 0 01( ) min( ( ), )ni i i i i i i i i ij ij j j i v t p a c N t m p b p b =ЎБ⎡ ⎛ ⎞= - ⎢Ґл - − Ґм ⎜ - ⎟ ⎢⎣ ⎜⎝ ⎟⎠ҐТ1min( ( ), ) ( )nj j j ji ji j N t m p a t o t ⎤- Ґм ҐД - ҐД ⎥⎥⎦ҐТ .Далее, переходя к пределу при ҐДt Ўж0 , получим неоднородные линейныеОДУ первого порядка: 0 01( )min( ( ), )nii i i i i ij ij j dv t N t m p b p b dt ⎛ ⎞= −Ґм ⎜⎜ - ⎟⎟ ⎝ ⎠ҐТ0 01min( ( ), )nj j j ji ji i i i j j i N t m p a p a c =ЎБ-ҐТҐм - Ґл - , i = 1,n .Задав начальные условия vi (0) = vi0 , i = 1,n , можно найти ожидаемые доходысистем сети.Если сеть функционирует так, что min(Ni (t),mi ) = Ni (t) , i = 1,n , (например, это равенство выполняется для СМО с бесконечным числом линий обслуживанияили когда mi больше или равно числу заявок в замкнутой сети), то системы (7), (8) будут иметь вид 01( )( ) ( )nij ji j i i i j j i dN t p N t N t p dt =ЎБ=ҐТҐм − Ґм - Ґл , i = 1,n ; (9)0 0 0 01 10( )( ) ( ) , (0) , 1, .n n i i i i ij ij i j ji ji j i i i j j j i j i i i dv t p b p b N t p a N t p a c dt v v i n = ЎБ ЎБ⎧ ⎛ ⎞= −Ґм - - Ґм - Ґл - ⎜ ⎟ ⎪⎪⎨ ⎜⎝ ⎟⎠ ⎪⎪⎩ = ҐТ ҐТ (10)Систему (9) можно переписать в матричной форме: dN(t) QN(t) f dt = -, (11)где T ( ) ( 1( ), 2 ( ),..., ( ))N t = N t N t Nn t , Q - квадратная матрица, состоящая из элемен96 Е.В. Колузаева, М.А. Маталыцкийтов qij = Ґм j pji , если положить pii = −1, i, j = 1, n , f - вектор-столбец, элементами которого являются значения Ґлp0i , i = 1,n . Решение системы (11) имеет вид ( )0( ) (0)tN t = N eQt - f ЎтeQ t−Ґу dҐу , где N(0) - некоторые заданные начальные условия, однако нахождение элементов матрицы eQt является сложной задачей даже для относительно небольшихзначений n.Рассмотрим замкнутую сеть с центральной СМО, состоящую из n систем(рис. 1). Пусть в периферийных СМО сети число линий обслуживания бесконечно, в этом случае min(Ni (t),mi ) = Ni (t) , i = 1,n −1 , а центральная СМО функционирует в условиях высокой нагрузки, т.е. min(Nn (t),mn ) = mn . Система (7) в этомслучае перепишется в виде11( )( ) , 1, 1, ( )( ) .ii i n n ni n ni i n n i dN t N t m p i n dt dN t N t m dt −⎧ = −Ґм - Ґм = − ⎪⎪⎨⎪= Ґм −Ґм⎪⎩ҐТ(12)S1 S2  Sn−1SnРис. 1. Структура сети с центральной СМО Общее решение системы (12) при -----начальных условиях Ni (0), i = 1, n , равно( ) it n n ni i i i m p N t e−Ґм Ґм = Ґб Ґм , i = 1,n −1 , 11( ) ( )nn i i N t K N t −= −ҐТ , где 1( )niiK N t = ҐТ - число заявок в сети, (0) n n ni i i i m p N ҐмҐб = −Ґм, i = 1,n −1 . Для таких Ni (t), i = 1, n , система (10) для ожидаемых доходов систем сети принимаетвид( ) i it n n ni i in i i dv t m p b e dt ⎡ −Ґм Ґм ⎤= Ґм ⎢Ґб − ⎥ - ⎣ Ґм ⎦11jnt n n nj n ni ni j i j j m p p a K e c −−Ґм⎡ ⎛ Ґм ⎞⎤-Ґм ⎢ − ⎜⎜Ґб - ⎟⎟⎥ - ⎢⎣ ⎝ Ґм ⎠⎥⎦ҐТ , i = 1,n −1 , Исследование НМ-сетей со случайными доходами от переходов между их состояниями 971 11 1( ) i n n n t n n ni n njnj i j i i dv t m p p b e K dt − −−Ґм= ⎡ ⎛ Ґм ⎞ ⎤= Ґм ⎢ ⎜Ґб - ⎟ − ⎥ - ⎣ ⎝ Ґм ⎠ ⎦ҐТ ҐТ 11jnt n n nj j jn j n j j m p a e c −−Ґм⎛ Ґм ⎞- Ґм ⎜⎜Ґб - ⎟⎟ - ⎝ Ґм ⎠ҐТ .Интегрируя данные ОДУ при начальных условиях vi (0) = vi0 ,i = 1,n , получим11( ) j i n j t t i n ni ni i in j j v t p a e b e −−Ґм −ҐмҐб=Ґм -Ґб Ґм ҐТ 11nnjn ni ni n n ni n in i j j p p Ka ma mb c t −⎡ ⎛ ⎞ ⎤- ⎢Ґм ⎜⎜ −Ґм − ⎟⎟ - ⎥ - ⎢⎣ ⎝ Ґм ⎠ ⎦⎥ҐТ101njn ni ni i in i j j p a b v −Ґб−Ґм −Ґб Ґм ҐТ , i = 1,n −1 , 1 1 11 1 1( ) i j n n n i t t n n nj nj j jn j i i j v t p b e a e − − −−Ґм −Ґм= = Ґб = −Ґм - Ґб Ґм ҐТ ҐТ ҐТ 1 1 1 11 1 1 1n n n n ni n n n nj nj nj nj n nj jn n j i i j j p m pb K pb m pa c t − − − −= = = ⎡ ⎛ ⎞ ⎤- ⎢Ґм ⎜⎜ Ґм − - ⎟⎟ - ⎥ - ⎢⎣ ⎝ Ґм ⎠ ⎦⎥ҐТ ҐТ ҐТ ҐТ 1 1 101 1 1n n n j n nini i jn n i j j j p b a v − − −= = Ґб -Ґм - Ґб Ґм ҐТ ҐТ ҐТ . (14)2. ПримерРассмотрим сеть, описанную в предыдущем пункте при n = 20 , K = 110 , где K - число заявок в сети. Число линий обслуживания в центральной СМО -m20 = 10 . Интенсивности обслуживания заявок в линиях систем сети равныҐм1 = Ґм13 = Ґм19 = 4 , Ґм6 = 6 , Ґм3 = Ґм9 = Ґм10 = Ґм16 = 5 , Ґм2 = Ґм5 = Ґм7 = Ґм11 = Ґм15 = Ґм17 = Ґм18 = 3 , Ґм4 =Ґм8 = Ґм12 = Ґм14 = 2 , Ґм20 = 3 , а вероятности переходов заявокмежду СМО сети - p20i = 1 19, pi 20 = 1, i = 1,19 , определим также pii = −1, i = 1, 20 , остальные pij = 0, i, j = 1, 20 . Пусть также Ni (0) = 5, i = 1, 19 , N20 (0) = 15 .Зададим значения МО доходов от переходов между состояниями сети: 100sin , i 4( 1) c i Ґрi = 1, 20 , a20 i = 0,5, i = 1, 8, a20i = 1, i = 9, 18, a20 19 = 1,5 , ai 20 = (14,3,27,15,18, 20,7,6,29,14,8,15,11,9,22,17,14,13,14), i = 1, 19 .98 Е.В. Колузаева--------, М.А. МаталыцкийТогда, используя соотношения (13), (14) при начальных условиях vi (0) = 50, i = 1, 19, v20 (0) = 1000 , были получены выражения для ожидаемых доходов систем сети. Например, выражение для ожидаемого дохода центральной системыимеет вид 4 3 5 2 620 ( ) 95,1 124,8 315,8 16,6 75,4 2018,8 2908,7 v t = − e− t − e− t − e− t - e− t − e− t − t - .Графики ожидаемых доходов систем сети приведены на рис. 2 - 4.01002003004005002 4 6 8 t v2(t)v1(t)v10(t)v8(t)v7(t)v4(t)v5(t)v9(t)v6(t)v3(t)Рис. 2. Ожидаемые доходы систем Si , i = 1, 10 , сети0200400600800100012001400160018005 10 15 20 25 30v19(t)v11(t)v14(t)v13(t)v18(t)v12(t)v17(t)v15(t)v16(t)Рис. 3. Ожидаемые доходы систем Si , i =11, 19 , сетиИсследование НМ-сетей со случайными доходами от переходов между их состояниями 99-5000-4000-3000-2000-10000100020002 4 6 8 10 12 14 16 18 t Рис. 4. Ожидаемый доход центральной СМО ЗаключениеВ работе предложена методика нахождения ожидаемых доходов в системахНМ-сетей в случае, когда доходы от переходов между состояниями сети являютсяСВ с известными математическими ожиданиями.В настоящее время дальнейшие исследования по НМ-сетям проводятся по следующим направлениям: - исследование марковских НМ-сетей с различными особенностями; - исследование условий, при которых справедлива формула (4); - исследование произвольных (немарковских) НМ-сетей; - решение задач оптимизации и управления для НМ-сетей с использованиемрекуррентного по моментам времени метода анализа средних значений.

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