Содержание к диссертации
Введение
ГЛАВА 1. Сети массового обслуживания с зависи мым обслуживанием и отрицательными заявками
1. Описание сети 17
2. Вспомогательные функции 21
3. Марковский процесс, описывающий функционирование сети 24
4. Мультипликативное представление стационарного распределения марковского процесса 25
5. Следствия 45
ВЫВОДЫ 47
ГЛАВА 2. G-сети с зависимым обслуживанием и дообслуживанием положительных заявок 48
1. Описание сети 48
2. Вспомогательные функции 49
3. Марковский процесс, описывающий функционирование сети 53
4. Мультипликативное представление стационарного распределения марковского 54 процесса
5. Следствия 70
ВЫВОДЫ
ГЛАВА 3. Экспоненциальные сети массового обслуживания с зависимым обслуживанием, отрицательными заявками и изменением типа заявок
1. Описание сети 75
2. Вспомогательные функции 76
3. Марковский процесс, описывающий функционирование сети 79
4. Мультипликативное представление стационарного распределения марковского 80 процесса
5. Следствия 104
Выводы 109
Заключение 111
Литература
- Марковский процесс, описывающий функционирование сети
- Мультипликативное представление стационарного распределения марковского процесса
- Марковский процесс, описывающий функционирование сети
- Марковский процесс, описывающий функционирование сети
Введение к работе
В последнее время наблюдается бурное развитие вычислительных средств и создаваемых на их основе информационно-телекоммуникационных технологий и сетевых систем.
Функционирование сетевых структур связано с передачей и обработкой большого числа информационных потоков. Вероятностная природа этих потоков приводит к появлению целого ряда проблем, возникающих как на этапе проектирования сетевых систем, так и на этапах их эксплуатации и модернизации. Это, в свою очередь, стимулирует математические исследования, направленные на разработку адекватных стохастических моделей и их анализ с целью получения количественных оценок показателей производительности сетевых систем.
Мощный инструментарий для аналитического моделирования сетевых систем создан на основе теории сетей массового обслуживания (СеМО). Возможности применения СеМО в качестве моделей сетевых систем и их компонентов отражены, например, в [1,2,10,14,15,21,66,67]. В связи с этим большое внимание в литературе уделяется собственно анализу СеМО (см., например [1,2,10,14,20,31,67,77,83]).
В теории СеМО центральное место занимают так называемые мультипликативные сети, для которых стационарное многомерное распределение марковского процесса, описывающего стохастическое поведение сети, представляется в мультипликативной форме.
Впервые такой результат был получен в работе [75] для открытой однородной экспоненциальной сети с узлами неограниченной емкости, которая затем была названа сетью Джексона по имени автора работы. Базовое условие, которое должно выполняться для получения мультипликативного решения для сети Джексона, предполагает пуассоновость всех входящих в сеть потоков заявок и экспоненциальный характер распределений длительностей их обслуживания в узлах сети.
Следующим наиболее серьезным шагом в развитии теории мультипликативных сетей явилось появление работы [25]. В ней была сформулирована так называемая теорема ВСМР, обосновывающая мультипликативное решение для большого класса открытых сетей, обобщающих сети Джексона. Однако, в отличие от сетей Джексона, времена обслуживания в узлах ВСМР-сетей не обязательно распределены по экспоненциальному закону.
В дальнейшем, развитие теории мультипликативных сетей связано с разного рода обобщениями сетей Джексона и ВСМР-сетей.
Например, в работах [16,77,79,80] рассматривались зависимости интенсивностей входящих потоков от числа заявок в сети, зависимости вероятностей переходов заявок между узлами сети от состояния этих узлов, ограничения на число заявок в сети и обходы узлов. В публикациях [2,10,14,20,31,67,77,83] достаточно полно описаны различные исследования сетей Джексона, ВСМР-сетей и их многочисленных обобщений.
Важные результаты в теории мультипликативных сетей были получены в работах [18,19] для более общего, чем ВСМР-сети, класса сетей с так называемым зависимым обслуживанием. Так, в [18] теорема ВСМР была распространена на случай открытых СеМО с зависимым обслуживанием, в которых каждая заявка, входящая в сеть, характеризуется набором случайных параметров: последовательностью номеров проходимых заявкой узлов — маршрутом заявки, длиной маршрута и объемами и длительностями обслуживания заявки в различных узлах сети. Мультипликативное представление, полученное для СеМО, рассмотренной в [18], расширяет результаты работы [19], где была получена мультипликативная форма для стационарных вероятностей открытых СеМО, маршруты и длительности обслуживания заявок в которых задаются траекториями регенерирующего процесса.
Принципиально новый класс открытых сетей, допускающий мультипликативное решение, был введен Е.Геленбе в работах [48,49] а затем активно изучался в работах Е.Геленбе и других авторов [3,13,17, 23,24,26,27,32-47,50-56,59-65,68-74,76,78,81,82]. Это сети, названные G-сетями в честь их основоположника, в которых вместе с потоком обычных (положительных) заявок на узлы сети поступают также дополнительные пуассоновские потоки отрицательных заявок или/и триггеров.
Отрицательная заявка при поступлении в узел сети может уничтожить одну или несколько положительных заявок, если таковые имеются в наличие в данном узле, и покидает сеть, не получая для себя никакого обслуживания.
Поступивший на узел сети триггер мгновенно перемещает положительную заявку из одного узла с заданной вероятностью в некоторый другой узел сети.
Как уже отмечено выше, G-сети относятся к классу мультипликативных сетей и для них стационарное совместное распределение числа заявок в узлах сети представляется в форме произведения. Но для его нахождения необходимо решить систему нелинейных алгебраических уравнений для интенсивностей потоков заявок, циркулирующих в сети, что принципиально отличает G-сеть от сетей Джексона и ВСМР-сетей, для которых системы уравнений для интенсивностей циркулирующих в сети потоков заявок являются линейными.
Первые работы по исследованию G-сетей [48,49] появились в 1989г. В данных работах была исследована базовая G-сеть — сеть с однолинейными узлами неограниченной емкости, пуассоновскими потоками заявок, поступающими на узлы сети, и экспоненциальными распределениями длительностей обслуживания заявок, при этом дополнительный поток, поступающий в сеть, представляет собой лишь поток отрицательных заявок. Отрицательная заявка, поступившая на узел сети, мгновенно уничтожает положительную заявку в очереди или на приборе, если нет очереди в данном узле, и тут же покидает сеть. Отрицательная заявка, заставшая данный узел пустым, сразу покидает сеть, не оказывая на ее функционирование никакого влияния.
Очевидным обобщением базовой G-сети явилась работа [55], в которой подробно была исследована модель G-сети, когда отрицательная заявка с заданной вероятностью уничтожает не одну, а несколько положительных заявок, при этом количество уничтожаемых заявок случайно и задается некоторым распределением вероятностей.
Так, в [68] предполагается, что отрицательные заявки одного класса могут уничтожить положительные заявки только того же класса. В работе [56] используется алгоритм случайного выбора типа положительной заявки, т.е. при поступлении отрицательной заявки в узел і, в котором находится 0 положительных заявок (без учета их типа), с вероятностью ксі/кі будет уничтожена положительная заявка типа с.
В [47] рассматривается G-сеть с различными дисциплинами обслуживания положительных заявок в узлах: FIFO — обслуживание в порядке поступления, PS — разделение процессора и LIFO/PR — инверсионный порядок обслуживания с прерыванием обслуживания. Выбор положительной заявки для уничтожения происходит в соответствии с установленной в узле дисциплиной обслуживания, при этом в узле г отрицательная заявка класса т может уничтожить положительную заявку класса к с вероятностью Kimk- В [65] результаты [47] были распространены на случай нескольких типов триггеров.
В работах [13,16,17] были рассмотрены различные модификации сетей с отрицательными заявками и обходами. Для G-сетей с обходами в [13,16,17] также было получено мультипликативное решение.
Интересная разновидность G-сети была исследована в работе [36]. Это G-сеть с катастрофами. Ее отличие от базовой G-сети состоит в том, что при поступлении в узел отрицательной заявки-катастрофы она уничтожает все положительные заявки в этом узле.
Во всех предыдущих работах предполагается, что сигнал, поступающий в не пустой узел G-сети, срабатывает мгновенно. Работы [3,27] развивают теорию G-сетей на случай, когда активизация (срабатывание) сигнала, поступившего в сеть, происходит не сразу, а через случайное время.
Цикл работ [4-8,11,12,28,29,30], опубликованных в последние годы, связан с развитием мультипликативной теории для G-сетей с зависимым обслуживанием.
Достаточно полный обзор публикаций по G-сетям, включая G-системы (однофазные и двухфазные), содержат обзоры [9)22,58]. Новые направления в развитии G-сетей излагаются в [57].
Теория G-сетей возникла в связи с необходимостью аналитического моделирования биофизических нейронных сетей [48,49]. В биофизических нейронных сетях циркулируют импульсно-подобные сигналы, которые генерируются через случайные интервалы времени, а движение этих импульсов в нейронной сети имеет очень много похожего на циркуляцию заявок в СеМО. При этом сигнал возбуждения (положительная заявка) в принимающем его нейроне (узле сети) увеличивает его потенциал на единицу, а сигнал торможения (отрицательная заявка) уменьшает потенциал нейрона на единицу.
Позже G-сети нашли свое применение для целого ряда других практических приложений. Например, в работах [33,42,43,46,50,51,54, 56,59,60,64,69-71] описаны самые разнообразные приложения G-сетей при моделировании нейронных сетей, информационно-вычислительных систем и сетей (например, в задачах управления потоками в вычислительных сетях, при моделировании эффекта вируса в сетях и др.), производственных систем и сетей, в задачах распознавания образов, в задачах комбинаторной оптимизации и т.д.
Марковский процесс, описывающий функционирование сети
В этом параграфе доказывается теорема о мультипликативном представлении стационарных вероятностей состояний для рассматриваемой сети.
Стационарную плотность распределения вероятностей состояний процесса Z(t) будем обозначать p{z). Ниже прямым построением мы покажем существование этой плотности при естественном ограничении на загрузку сети.
Теорема. Если для узлов з типа 0 р3 св, для узлов з типа 1 р3 оо и для узлов $ типов 2 и 3 р8 1, где р3 определяются формулой (7), то существует предельное (стационарное) распределение вероятностей состояний процесса Z(t) с плотностью распределения вероятностей м P(z) = l[ps(zs), (13) 8=1 причем: для узла s типа О Pa{zs)=Pa{0)ds(K)(—— ) П ((і«,гві,уві), (14) где -W-Cg + Sfey) - W) d J-\l/(Cj!cJ--e-) ipufc.X:,; l J для узла s типа 1 Ps(zs) = е_р ттПБ««(Х» І «іг« »« )зп.Л п « % ); (17) s i=l для узла s типов 2 и З ps( ) = (l-p8) fcen5 (Xs« 1 , , )5 .( , , ). (18) i l
Доказательство. Нетрудно видеть, что марковский процесс Z{t) является регулярным и положительно возвратным по Харрису, так как состояние О является для него положительно возвратным атомом. Поэтому для доказательства теоремы достаточно показать, что функция p(z), определяемая утверждением теоремы, удовлетворяет системе уравнений для стационарной плотности распределения вероятностей состояний процесса, которую аналогично дискретному случаю назовем системой уравнений равновесия (СУР).
Для записи СУР введем следующие обозначения. Пусть СеМО находится в состоянии z. Тогда через vBi{z) обозначим скорость обслуживания г-й заявки, находящейся в узле s, т.е. 1/ ., 0, Vsi(z) - і если г-я заявка обслуживается в узле s типа 1 или находится на приборе в узле s типа 0 или 2; если г-я заявка обслуживается в узле s типа 3 (в котором обслуживается еще ка — 1 заявок); если г-я заявка находится в очереди в узле s типа 0 или 2, (19) а через Р J(z) =vsi(z)P+Jxei j lei,rgityai) (20) и t 7i(Z) = VsM 0n3i {Xei I «i r U Уві) (21) — интенсивности выхода из состояния z за счет окончания обслуживания или "убийства" г-й заявки в s-м узле.
Кроме того, для s Є Мі U ЛІ2 U Ліз, k 0 и і = 1, & положим { 1, если 5 Є Ліг и г = 1; 0, если s Є М.2 и г 1; (22) І/fc, если з є Мі иМз Функция uSi(k) представляет собой вероятность того, что заявке, поступающей в неэкспоненциальный узел s, в котором находится еще к — 1 заявок, будет присвоен номер і.
Так как уравнения СУР будут иметь различный вид для разных состояний множества состояний Z процесса Z(t), то разобьем множество 2 на два подмножества состояний. К первому подмножеству отнесем такие состояния, для которых ХВІ 0 для всех тех (s,i), для которых они определены (т.е. для всех s Є М. \ M.Q). Такие состояния будем называть внутренними состояниями. Очевидно, что внутреннее состояние — это такое состояние, в котором все заявки, находящиеся в узлах типов 1-3, уже обслуживались какое-то время.
Мультипликативное представление стационарного распределения марковского процесса
Каждому внутреннему состоянию z Є Z поставим в соответствие множество состояний Z(z). Состояния, принадлежащие множеству Z(z) будем называть предшествующими состоянию z. Смысл введения предшествующих состояний заключается в том, что только из них возможен непосредственный переход в состояние Z.
В свою очередь, все состояния, предшествующие внутреннему состоянию 2, разобьем на 4 класса. Каждый класс будет соответствовать определенному типу перехода в состояние z.
Первый класс Z+(z) = 2 (z) U Z (z) состоит из двух (пересекающихся) подклассов Z (z) и Z(z). Первый подкласс Zf(z) = {z+{z,s,i,l,rty,x)}, соответствует тем состояниям сети, из которых возможен переход в состояние z за счет ухода заявки из сети при полном окончании ее обслуживания (в последнем узле маршрута) и состоит из состояний z+{z,8,i,l,r,y,x)y имеющих вид z+(z,s,i,J, г, у,х) = {zi,. . . , Ze_l, z Biz3+i,..., zM), где z8 — {ks + l,zel,... ,z8ke+l) и { Zsj, 3 h {l,r,y,l,x), j=i, 2.J-1. 3 h a (I, r, y, x) — параметры уходящей с г-го места в s-м узле полностью обслуженной заявки, которые могут принимать любые (возможные) значения. Второй подкласс Z+{z) = {z+(z,s,i, I, r, y,n,x)}, соответствует состояниям сети, из которых возможен переход в состояние z за счет ухода заявки из сети при "убийстве" ее на г-м месте в 5-м узле сети на тг-м этапе маршрута и состоит из состояний z+(z,$,i,l,r,у,п,х), имеющих вид z+ (z, s, і, І, г, у, п, х) = (zu. . . , Za_і, Z , ZH-1, ..., ZM), где и (l,r,y,n,x), j = i, Zs,j-lj j « , а параметры (I, г, у, n, x) также могут принимать любые (возможные) значения.
Остальные 3 класса предшествующих состояний не пусты только для СеМО, в которых есть экспоненциальные узлы.
Пусть 5 Є M.Q и состояние z таково, что к3 0. Предположим также, что пвкв = 1. Обозначим через z (zys) состояние z (z,s) = (zi,..., z3_ii z ,zs+i,..., ZM), где Zg = [Kg — 1, Zgl, ..., Zgfa-l).
Состояния z (z, s) будем называть предшествующими состояниями класса Z± (z), а множество узлов s, для которых состояния z (z,s) определены — через Si(z). Очевидно, что класс Z (z), состоит из состояний, из которых возможен переход в состояние z за счет поступления новой заявки в экспоненциальный узел сети, а множество Si(z) — из экспоненциальных узлов, в которых при состоянии z на последнем месте находится заявка, только что поступившая в СеМО. Класс 2 %{z) соответствует предшествующим состояниям, переход из которых в состояние z осуществляется при окончании обслуживания в одном экспоненциальном узле и поступлении ее на обслуживание в другой экспоненциальный узел (на последнее место), и состоит из непересекающихся подклассов Z% {z, s), определяемых следующим образом. Пусть s MQ И состояние z таково, что кв 0. Предположим также, что risk, 1 и rStketnaka i = s Є Mo. Тогда Z[zts) = {z-(z,s,j)}, причем каждое состояние z {z, s,j) имеет вид Z (z,S,j) = (z\,..., Zs -i,Z ,, ZS + i,..., za-i,zl,za+i,. ..,ZM) (естественно, s может предшествовать s и даже совпадать с s , если из s-ro узла заявка снова поступает в s-й узел), где zsi = («V + 1, zs i»..., za,tkal+l), { Zs i, i j, {І8кя,гвкв,уака,п8кя-1,х), i=j, z3\i-u і h z 3 — (fce - lizai,...,ZSjk,-l).
Множество узлов s, для которых подклассы Z iz s) не пусты, обозначим через Si{z).
Наконец, класс Z (z) аналогичен классу Z%{z) за исключением того, что переход в состояние z осуществляется при окончании обслуживания в неэкспоненциальном узле. Непересекающиеся подклассы Z (z,s), образующие класс Z$(z), определяются так. Пусть s є Mo и состояние z таково, что ка 0. Предположим также, что п3ьг 1 и гвік„пака-і = d MQ. Тогда ЗО причем каждое состояние z (г, s,j, х) имеет вид z (z,s,j,x) = (zi,..., zar-lyz a,, z3 +i,..., Ze_i,z , za+i,. ..,гм), где V = ( V + 1» я з і s .V + l) ( fe3, rak,, y8ka, nsks - 1,), t = j, Z8 ,i-U і h z a = (fc« - 1 z b J z3,k,-l) Множество узлов s, для которых не пусты подклассы Z (zts), обозначим через і?з( ) Отметим еще раз, что каждый из классов Z (z)-Z (z) может быть пустым. В частности, для состояния О = (0,...,0) пустыми являются все классы Z (z) Z (z).
Выпишем уравнения глобального баланса для внутреннего состояния z. Для этого вычислим потоки вероятностей, входящие и выходящие из состояния Z,
Поток, выходящий из состояния г, состоит из двух частей.
Во-первых, выход из состояния z осуществляется при поступлении новой заявки в СеМО (с интенсивностью А). Выходящий из состояния z поток вероятностей, связанный с поступлением новых заявок, равен Xp{z).
Во-вторых, выход из состояния z происходит и при окончании обслуживания г-й заявки в s-м узле (с интенсивностью fij z)) или "убийства" ее в этом узле (с интенсивностью fi i{z)). Общий выходящий из состояния z поток вероятностей, связанный с окончанием обслуживания или "убийствами" заявок во всех узлах, равен
М к, «=l г=1 Вход во внутреннее состояние z может произойти из состояния z+(z,sfi,l, г, у,х) Є Zf(z) при окончании обслуживания г -й заявки в s-м узле (последнем узле маршрута заявки) и из состояния z+(z,s,i,l7r,y7n,x) Z(z) при "убийстве" г -й заявки в s-м узле на п-м этапе маршрута. Поскольку интенсивность окончания обслуживания г-й заявки в s-м узле равна (г+(г, st г, I, г, у, ж)), а интенсивность "убийства" г -й заявки в s-м узле на п-м этапе маршрута равна //Jj(z+(z,s,i,l, г, у,п,х)), то суммарный входящий в состояние z поток вероятностей, связанный с окончанием обслуживания заявок в узлах или "убийствами", равен
Марковский процесс, описывающий функционирование сети
Определим теперь марковский процесс, описывающий функционирование рассматриваемой СеМО.
Будем обозначать набором z = (г1(... ZM) состояние сети, где, в свою очередь, набор za = {kSizsi ... , ajta), s = 1,M, описывает состояние s-ro узла следующим образом: ка — число заявок, находящихся в s-м узле, а набор zBi, s = 1,М, г — 1,&S, с компонентами &i,"e ,tfsi, i) определяет информацию (lsilrsilysi) об г-й заявке, находящейся в s-м узле, и ее положении (п„»,ж8 ,гу,») в сети: lsi — длина маршрута; Пі — {rail,-. -,raiiBi) — маршрут; УВІ = (УэПт -іУзііві) — объемы заявки на этапах маршрута; nsj — номер этапа маршрута, на котором находится (обслуживается или ожидает обслуживания) заявка (ясно, что пщ l8i)\ xSi — выработанная длительность обслуживания заявки на данном этапе; Wsi — функция, показывающая состояние заявки, причем полагаем wai = 0, если заявка не "убита", и wsi = 1, если заявка "убита" (но продолжает обслуживаться).
Напомним, что в силу принятого обозначения гвІПаі = s. Вектор z6 = 0 в случае кв = О, т.е. когда в s-м узле отсутствуют заявки, а вектор 2 = О = (0,..., 0) в том случае, когда в сети нет заявок.
В дальнейшем примем следующее правило нумерации заявок в узлах. Для узлов типов 1 и 3 будем нумеровать заявки в случайном порядке, а для узлов типа 2 — в порядке, обратном порядку поступления заявок в этот узел.
Множество состояний сети обозначим через Z = {z}. В качестве процесса, описывающего стохастическое поведение рассматриваемой СеМО, рассмотрим процесс Z(t) = z, если в момент t сеть находится в состоянии z. Нетрудно видеть, что введенный таким образом процесс является марковским. Кроме того, введем (немарковские) процессы Z8{t) = zs, если в момент t сеть находится в состоянии z, s = 1,М.
Процесс Zs(t) описывает функционирование узла s сети. В этом разделе доказывается теорема о мультипликативном представлении стационарных вероятностей состояний марковского процесса, введенного выше.
Обозначим через p(z) стационарную плотность распределения вероятностей состояний процесса Z(t). Ниже прямым построением покажем, что при естественном ограничении на загрузку сети, плотность p(z) существует.
Теорема. Если для узлов s типа 1 р8 со и для узлов s типов 2 и 3 р3 1, где р9 определяются формулой (9), то существует предельное (стационарное) распределение вероятностей состояний процесса Z(t) с плотностью распределения вероятностей м 8=1 причем для узла s типа 1 p3{z3) =е р -гіПВ"ч(Хаі \ r ys wsi)glai(lsi,rai,y8i)y (16) а для узла s типов 2 и З к, Доказательство.
Так как состояние 0 марковского процесса Z(t) является положительно возвратным, то процесс Z(t) является регулярным и положительно возвратным по Харрису. Поэтому для доказательства теоремы достаточно показать, что функция p(z)7 определяемая формулами (15)-(17), удовлетворяет системе уравнений для стационарной плотности распределения вероятностей состояний процесса Z(t), которую также будем называть СУР, Введем следующие обозначения, которые потребуются ниже для записи СУР. Пусть СеМО находится в состоянии z. Тогда через v3i(z) обозначим скорость обслуживания г-й заявки, находящейся в узле s, т.е. ( 1, если -я заявка обслуживается в узле s типа 1 Vsi{z) = или находится на приборе в узле s типа 2; 1/к3, если г-я заявка обслуживается в узле $ типа 3 (в котором обслуживается еще ка — 1 заявок); О, если г-я заявка находится в очереди в узле s типа 2, (18) а через litiiz) = vsi(z) 0+ (xsi J Іаі, rsii ysi) (19) и P8i ( ) = i {z) 0Пзі {xsi I lsi, r8i, ysi) SWai (20) — интенсивности выхода из состояния z за счет окончания обслуживания и "убийства" (еще не "убитой") г-й заявки в 5-м узле.
Наконец, для к 0 и i = l,k положим 1, если s Є М.2 и г = 1; и9і{к) = 0, если s Є М.2 и г 1; 1/fc, если s Є Mi U Л4з (21) Функция uai(k) представляет собой вероятность того, что заявке, поступающей в узел я, в котором находится еще к — 1 заявок, будет присвоен номер г.
Так как уравнения СУР будут иметь различный вид для разных состояний множества состояний Z процесса Z(t), то разобьем множество Z на два подмножества состояний. К первому подмножеству отнесем такие состояния, для которых xSi 0. Такие состояния будем называть внутренними состояниями. Очевидно, что к внутренним состояниям относятся такие состояния, в которых все заявки уже обслуживались какое-то время. Остальные состояния, которые будем называть граничными, отнесем ко второму подмножеству.
Построение СУР начнем с внутренних состояний.
Каждому внутреннему состоянию z є Z поставим в соответствие множество состояний Z{z). Состояния из множества Z(z) будем называть предшествующими состоянию z. Физический смысл предшествующих состояний заключается в том, что только из низ возможен непосредственный переход в состояние Z.
В свою очередь, все состояния, предшествующие внутреннему состоянию z, разобьем на два (пересекающихся) класса. Состояния каждого класса соответствуют определенному типу перехода в состояние z.
Марковский процесс, описывающий функционирование сети
Определим теперь марковский процесс, описывающий стохастическое поведение введенной СеМО.
Прежде всего, введем дополнительный бесконечнолинейный экспоненциальный узел с номером 0. Будем считать, что в этом узле происходит активизация заявок, превращающихся из положительных в отрицательные. Интенсивность обслуживания в узле 0 равна о Состояние сети будем обозначать набором z = (ZQ, ZI, ..., ZM) Вектор ZQ = [ко, J?OI, ..., ofeo) соответствует состоянию процесса активизации заявок, причем ко — число активизируемых заявок, а набор га, і = 1,&о, с компонентами ZQI = (ІОІІГОІІУОІ ПОІ) содержит информацию (Іоі, ГОІ, уОІ) о маршруте и объемах на этапах маршрута г-й активизируемой заявки и номере ЩІ этапа, на котором происходит превращение ее в отрицательную (активизация). Положим р0 = j /fiQ. Величина ро имеет смысл загрузки на дополнительный узел 0.
Набор za = (A;e,2ei,. ..,2afcJ, s = 1,М, в свою очередь, описывает состояние s-ro узла следующим образом: ка — число заявок, находящихся в s-м узле, а набор гЯ1-, s = 1,М, І = l,fce, с компонентами z„i = {І8і,гвііУві,пйі) содержит информацию {Ілі,гаі,уаі) о параметрах г-й заявки, находящейся в s-м узле, и ее положении паі в сети, где nsi — номер этапа маршрута, на котором находится (обслуживается или ожидает обслуживания) заявка.
Очевидно, что в силу принятого обозначения гвіПаі — s. Ясно также, что вектор z3 = 0 в случае к3 = 0, т.е. когда в s-м узле отсутствуют заявки, а вектор z = О = (0,..., 0) в том случае, когда во всей сети ней нет ни одной заявки.
В дальнейшем для узла 0 заявки будем нумеровать в случайном порядке, а для остальных узлов — в порядке поступления заявок в узел.
Множество состояний сети обозначим через Z — {г}. В качестве процесса, описывающего функционирование рассматриваемой СеМО, рассмотрим процесс Z(t) = z, если в момент t сеть находится в состоянии z. Нетрудно убедиться, что введенный процесс является марковским. Кроме того, далее будем рассматривать также (немарковские) процессы % {$ = ( 1,... і %м) если в момент t сеть находится в состоянии Z, описывающий совместное функционирование только узлов с положительными заявками, и ZB{t) = zs, если в момент t сеть находится в состоянии z, s = 0,М, описывающие функционирование отдельных узлов сети. Напомним, что в силу определения марковского процесса Z{t) для любых s = 1,М, г и (/«, « 1/в;) состояния z обязательно должно выполняться равенство rs{nBi = s.
Доказательство. Нетрудно видеть, что марковский процесс Z(i) является регулярным и положительно возвратным по Харрису, так как состояние О является для него положительно возвратным атомом. Поэтому для доказательства теоремы достаточно показать, что функция p(z), определяемая утверждением теоремы, удовлетворяет системе уравнений для стационарной плотности распределения вероятностей состояний процесса, называемой СУР.
Для записи СУР введем следующие обозначения. Пусть СеМО находится в состоянии z. Тогда через v8i(z) обозначим скорость обслуживания г-й заявки, находящейся в узле s, т.е. — интенсивности выхода из состояния z за счет окончания обслуживания, за счет "убийства" поступающей извне отрицательной заявкой и за счет превращения в отрицательную г -й заявки в s-ьл узле при поступлении в этот узел извне отрицательной заявки.
Каждому состоянию z Є. Z поставим в соответствие множество состояний Z(z). Состояния, принадлежащие множеству Z{z) будем называть предшествующими состоянию г. Смысл введения предшествующих состояний заключается в том, что только из них возможен непосредственный переход в состояние Z,
Все состояния, предшествующие состоянию z, разобьем на 3 класса. Каждый класс будет соответствовать определенному типу перехода в состояние z. Первый класс Z+(z) = (J Zf(z) состоит из 6 (в том числе переїв секающихся) подклассов Z (Z)-ZQ(Z). Первый подкласс ZHZ) = {z+{z,s,i,l,r,y)} соответствует тем состояниям сети, из которых возможен переход в состояние z за счет ухода положительной заявки из сети при полном окончании ее обслуживания (в последнем узле маршрута) и состоит из состояний, имеющих вид
