Анализ функционирующих в полумарковской среде RQ-систем с возвратом заявок

Вавилов Вячеслав Анатольевич кандидат физико-математических наук доцент, кафедра программной инженерии, Национальный исследовательский Томский государственный университет 634050, Россия, Томская область, г. Томск, ул. Ленина, 36 Vavilov Viacheslav PhD in Physics and Mathematics Associate Professor, Department of Software Engineering, National Research Tomsk State University 634050, Russia, Tomskaya oblast', g. Tomsk, ul. Lenina, 36 vavilovv@yandex.ru Другие публикации этого автора

1. Введение

Основным средством исследования стохастических систем являются марковские процессы ^[1-7]. Марковские цепи накладывают определённые ограничение на исследуемые процессы, что обусловлено требованием перехода из одного состояния марковской цепи в другое в каждый единичный промежуток времени. Если же снять это ограничение и допустить произвольное распределение времени пребывания в данном состоянии, то получится полумарковский процесс [4-6, 8-11], являющийся обобщением марковских процессов.

Необходимость оптимизации сетей связи, математическими моделями которых являются системы массового обслуживания, привела к рассмотрению управляемых систем массового обслуживания ^[12-15]. По-другому такие системы называют системами с переменными параметрами. Таким системам посвящены работы Коротаева И. А. ^[16-21].

Изменение параметров может происходить как внутри системы в зависимости от ее состояния, так и под воздействием внешних условий, например изменения случайной среды, в которой и функционирует система. В работе ^[22] представлены исследования систем массового обслуживания со случайной интенсивностью входящего пуассоновского потока.

Впервые понятие дважды стохастического входящего потока было введено Кингманом ^[23]. Системы массового обслуживания с входящим дважды стохастическим пуассоновским потоком не сводятся к классическим системам массового обслуживания с постоянными параметрами, поскольку входящий поток в данном случае не является рекуррентным.

Можно рассматривать задачу, когда изменяются не только параметры входящего потока, но и параметры обслуживания. Такие системы принято называть системами массового обслуживания, функционирующими в случайной среде ^[24-25]. Впервые понятие система, функционирующая в случайной среде, появилось в работе ^[26].

Соответствующие исследования применительно не только к системам массового обслуживания, но и к сетям связи представлены в трудах Дудина А.Н. ^[27-30], Neuts M.P. ^[31], Sztrick J. ^[32], Takahashi H., Akimaru H. A ^[33]. Возможные значения параметров систем массового обслуживания связываются со значениями некоторого случайного процесса, который называют управляющим процессом. Изменения значений управляющего процесса приводит к изменению параметров функционирования системы.

В связи с тем, что получение точных выражений для вычисления требуемых вероятностно-временных характеристик является достаточно сложной задачей, возникло направление решения задач теории массового обслуживания с помощью асимптотических методов ^{[10, 34-37]}. Эти методы позволяют отойти от явной разрешимости с использованием диффузионных процессов.

В ряде работ при анализе систем массового обслуживания, функционирующих в случайной среде, применяется метод диффузионной аппроксимации. В этом случае задача сводится к анализу характеристик диффузионного процесса с изменяющимися в случайные моменты времени коэффициентами переноса и диффузии. Плотности распределения можно найти из системы дифференциальных уравнений Фоккера-Планка. Такой подход используется в ^[38-43].

Особый интерес в последнее время представляет исследование RQ-систем (retrial queueing systems, системы с повторными вызовами), которые являются адекватными моделями широкого класса технических и социально-экономических систем ^[43-50]. Так, например, в работе ^[44] приводится более семи сотен ссылок на работы данной направленности. Тем не менее, исследованию RQ-систем, функционирующих в случайной среде, уделяется недостаточно внимания. В наших работах представлены RQ-системы, где в качестве математической модели случайной среды рассмотрена цепь Маркова ^[46-47], полумарковский процесс ^[48-49], диффузионный процесс ^[50].

В данной работе предлагается математическая модель RQ-систем с возвратом заявок и функционированием в полумарковской среде, проводится асимптотическое исследование.

2. Математическая модель

Рассмотрим RQ-систему, на вход которой поступает простейший с параметром λ поток заявок. Прибор этой системы может находиться в одном из двух состояний: k=0, если он свободен; k=1, если он занят обслуживанием заявки. Заявка, заставшая в момент поступления прибор свободным, начинает обслуживаться с интенсивностью µ. Если в течение обслуживания этой заявки другие требования на прибор не поступают, то исходная заявка по завершении обслуживания покидает систему с вероятностью r или с вероятностью 1-r переходит на орбиту. Если в течение обслуживания одной заявки поступает другая, то поступившая заявка переходит на орбиту. Повторное обращение заявок к прибору из орбиты происходит после случайной задержки, продолжительность которой имеет экспоненциальное распределение с параметром γ. Число заявок на орбите обозначим i.

Система функционирует в случайной среде. В качестве математической модели случайной среды рассмотрим полумарковский процесс s(t) с непрерывным временем t, то есть такой дискретный случайный процесс, который принимает значения из конечного множества состояний s=1,2,...,S и для которого вложенная по моментам времени tn изменения состояний цепь s(t_n) является Марковской. Времена пребывания этого процесса в различных состояниях являются условно независимыми случайными величинами, распределение вероятностей значений которых зависит лишь от номера состояния полумарковского процесса.

Для определения полумарковского процесса s(t) зададим стохастическую матрицу одношаговых вероятностей ps1s2 переходов вложенной цепи Маркова

при этом будем полагать, что p_ss=0.

Понятно, что

Также зададим набор функций распределения G_s(x) значений времени пребывания полумарковского процесса в s-м состоянии.

Влияние случайной среды на функционирование RQ-системы определяется зависимостью интенсивности µ обслуживания заявок от состояний s(t)=s случайной среды, то есть µ=µ(s), а также зависимостью параметров λ и γ от состояний s(t)=s случайной среды, то есть λ=λ(s), γ=γ(s). Вероятность окончания обслуживания заявки на приборе за бесконечно малый промежуток времени Δt равна µ(s)Δt+o(Δt). Вероятность поступления нового требования в систему за бесконечно малый промежуток времени Δt равна λ(s)Δt+o(Δt). Вероятность обращения заявки на прибор из орбиты за бесконечно малый промежуток времени Δt равна γ(s)Δt+o(Δt).

В силу свойств приведенной математической модели трехмерный случайный вектор {k(t),i(t),s(t)} изменения во времени состояний {k(t),i(t)} RQ-системы и состояний {s(t)} математической модели случайной среды является полумарковским процессом.

Для исследования описанной математической модели марковизируем процесс {k(t),i(t),s(t)} методом дополнительной переменной. Введем переменную ζ(t), имеющую смысл длины интервала времени от момента t до момента смены текущего состояния случайной среды, тогда процесс изменения значений вектора {k(t),i(t),s(t),ζ(t)} является марковским процессом.

Обозначим P(k(t)=k,i(t)=i,s(t)=s, ζ(t)<ζ)=Pk(i,s,ζ,t).

В любой момент времени должно выполняться условие нормировки

Для распределения Pk(i,s,ζ,t) можно составить систему дифференциальных уравнений Колмогорова:

Обозначим γ(s)= γσ(s) и перепишем данную систему в следующем виде

Систему (1) будем исследовать методом асимптотического анализа ^[40] в условиях большой задержки заявок на орбите γ→0. Для этого в (1) выполним замены:

тогда получим

3. Исследование асимптотических средних характеристик

Под асимптотическими средними характеристиками RQ-систем с вызываемыми заявками, будем понимать распределение вероятностей R_k(x) состояний k канала и предельную функцию

имеющую смысл асимптотического среднего нормированного числа заявок в системе.

В системе (3) перейдем к пределу при ε→0 и, полагая, что существуют конечные пределы

получим систему

Решение Hk(y,s,ζ,τ) системы (5) будем искать в виде

Тогда Q_k(x,s,ζ), имеющая смысл условного совместного распределения вероятностей состояний k канала и s среды при условии x(τ)=x определяется системой вида

и условием нормировки

Будем полагать, что Q_k(x,s,ζ) известны, если удается каким либо образом решить систему (7).

Далее покажем, что x=x(τ) является детерминированной функцией.

В системе (3) функции H_k(y±ε,s,τ,ε) разложим в ряд по приращениям аргумента y с точностью до o(ε), получим

Уравнения системы (9) просуммируем по k и по s, и при ζ→∞ получим

Поделим на ε обе части полученного уравнения, выполним предельный переход (4), учтём (6), получим

Учтём условие нормировки (8), обозначим

заметим, что R_k(x) имеет смысл распределения вероятностей состояний канала, получим

Поскольку производная плотности распределения H(y,τ) не может тождественно равняться нулю, следовательно, функция x=x(τ) является решением обыкновенного дифференциального уравнения

Получили, что x=x(τ) является детерминированной функцией.

4. Величины отклонения нормированного числа заявок в системе от среднего

Рассмотрим процесс

который характеризует изменение величин отклонения нормированного числа заявок в системе от их асимптотического среднего и покажем, что он является диффузионным процессом авторегрессии.

Обозначим

Будем искать решение H_k(y,s,ζ,τ,ε) системы (3) в виде

Подставим в систему (9) разложение (13), учтём (7) и запишем полученную систему, сократив на все уравнения, в следующем виде

Будем искать решение системы (14) в следующем виде

Подставим (15) в (14) и представим систему в виде двух систем

и

Продифференцируем систему (7) по x, получим

Из последней системы с учётом системы (17) следует, что решение

системы (17) имеет вид

С учётом (18) и (15) разложение (13) примет вид

Теперь найдём вид функции H(y,τ). Для этого функции в правой части системы (3) разложим в ряд по приращениям аргумента y с точностью до o(ε²), получим

Сложим все уравнения системы (20) по k, получим

Подставим в полученную систему разложение функций H_k(y,s,ζ,τ,ε) в виде (19), учтём обозначение (10), получим

Просуммируем уравнения системы (21) по s, выполним предельный переход при ζ→∞, воспользуемся условием нормировки (8), обозначением (10), также обозначим

учтём, что

получим

В силу дифференциального уравнения (11) уничтожим в (23) слагаемые порядка o(ε), поделим обе части полученного уравнения на ε², выполним преобразования, будем иметь

Получили уравнение Фоккера – Планка для плотности распределения вероятностей H(y,τ) значений диффузионного процесса авторегрессии y(τ). Заметим, что коэффициент переноса уравнения (24) есть производная по x от правой части дифференциального уравнения (11). В силу обозначения (12) можно записать

Коэффициент диффузии с учётом (24) обозначим следующим образом

если выражение в правой части больше нуля.

Из (24) следует, что H(y,τ) является плотностью распределения вероятностей диффузионного процесса y(τ), который удовлетворяет стохастическому дифференциальному уравнению

где w(τ) является стандартным процессом Винера, то есть y(τ) является процессом авторегрессии.

5. Плотность распределения вероятностей процесса изменения состояний RQ-системы

Используя предельные процессы x(τ) и y(τ) для достаточно малых значений параметра ε, рассмотрим процесс z(τ)=x(τ)+εy, который аппроксимирует процесс изменения числа заявок в системе ε²i(τ/ε²) и покажем, что он является однородным диффузионным процессом.

Дифференцируя z(τ) по τ получаем dz(τ)=x'(τ)dτ+εdy.

В силу (11) и (12) имеем

Так как правая часть содержит разложение в ряд по приращениям εy аргументаx, то можно записать

С точностью до o(ε), имеем

Обозначим F(z,τ) плотность распределения вероятностей значений процесса z(τ), тогда можно записать уравнение Фоккера – Планка для плотности этого процесса

Рассмотрим функционирование процесса z(τ) в стационарном режиме, то есть F(z,τ)=F(z), тогда стабильное распределение можно найти из уравнения Фоккера – Планка

Уравнение (29) является однородным дифференциальным уравнением второго порядка и имеет решение:

6. Выводы

Таким образом, в данной работе предложена математическая модель функционирующей в полумарковской среде RQ-системы с вызываемыми заявками. Методом асимптотического анализа ^[8] получено обыкновенное дифференциальное уравнение (11), определяющее асимптотическое среднее x=x(τ) нормированного числа заявок в системе. Представлено распределение R_k(x), k=0,1, вероятностей состояний прибора в виде (10), где величины Q_k(x,s,ζ), k=0,1, имеющие смысл условного совместного распределения вероятностей состояний k канала и состояний s полумарковской среды, определяются системой уравнений вида (7). Показано, что процесс y(τ), характеризующий изменение величин отклонения нормированного числа заявок в системе от их асимптотического среднего, является диффузионным процессом авторегрессии и определяется стохастическим дифференциальным уравнением вида (27). Показано, что для достаточно малых значений параметра ε процесс z(τ)=x(τ)+εy, является однородным диффузионным процессом. Найдена важнейшая вероятностно-временная характеристика процесса z(τ) – плотность распределения вероятностей его значений в виде (30).