Asymptotic analysis of queueing system MAP/GI/? with high-rate arrivals.pdf Системы массового обслуживания являются адекватными моделями современных систем передачи и обработки информации [1], социально-экономических систем [2, 3], систем управления транспортными потоками [4] и т.д. В научной литературе, как правило, исследуются системы с пуассоновским входящим потоком, однако имеются исследования [5], которые показывают, что, например, потоки сообщений в современных сетях передачи данных не являются пуассоновскими, а более адекватной моделью таких потоков является так называемый MAP-поток (Markovian Arrival Process) [6-8]. Таким образом, исследование моделей массового обслуживания с входящим MAP-потоком является актуальной научной проблемой. В настоящей работе представлен анализ системы массового обслуживания с входящим MAP-потоком, неограниченным числом приборов и произвольным обслуживанием, которая в нотации Кен-далла [9] обозначается как MAP/GI/да. Исследование проведено в асимптотическом условии растущей интенсивности входящего потока, которое относится к классу широко используемых условий «heavy traffic» [10-12]. В результате получена гауссовская аппроксимация распределения вероятностей числа заявок в системе. Этот результат согласуется с известными результатами, связанными с диффузионной аппроксимацией [10, 13, 14], но предоставляет более удобную форму для использования. Кроме того, изложенная в настоящей работе методика исследования позволяет получить аппроксимацию более высокого порядка точности, которая обеспечивает достаточно малую погрешность и при небольшой интенсивности входящего потока. С другими, близкими по тематике исследованиями в области анализа систем массового обслуживания и случайных потоков можно ознакомиться в работах [15-18]. 1. Постановка задачи Рассмотрим систему массового обслуживания с неограниченным числом приборов, на вход которой поступает высокоинтенсивный MAP-поток, время обслуживания заявки в системе является случайной величиной с функцией распределения B(t). Входящий MAP-поток задан представлением [8] (ND0, ND^, где D0 и Di - квадратные матрицы порядка M, а скалярный мультипликатор N используется для того, чтобы выделить асимптотическую составляющую высокой интенсивности этого потока. Дело в том, что интенсивность MAP-потока, заданного таким образом, составляет AN, где величина А определяется выражением Х = 8D1e. (1) Здесь e - вектор-столбец, состоящий из единиц, 8 - вектор-строка, элементы которой задают закон стационарного распределения вероятностей цепи Маркова m(t), управляющей MAP-потоком. Этот вектор удовлетворяет следующей системе уравнений: f8(Do + Dx ) = 0, [8e = 1. ( ) Таким образом, интенсивность описанного потока неограниченно возрастает при N ^ да. Потоки такого рода называют высокоинтенсивными [18]. Обозначим i(t) - количество заявок (или, что то же самое, количество занятых приборов) в системе в момент времени t. Ставится задача нахождения распределения вероятностей процесса i(t) в произвольный момент времени в стационарном режиме функционирования системы. 2. Метод динамического просеивания. Уравнения Колмогорова Для составления уравнений Колмогорова, которые являются основным механизмом исследования случайных процессов, необходимо провести так называемую марковизацию исследуемого процесса i(t), т. е. преобразовать его таким образом, чтобы полученный в результате преобразований процесс был марковским. Стандартным инструментом такой марковизации является метод дополнительных компонент [9, 19, 20]. Для рассматриваемого процесса i(t) этими дополнительными компонентами будут состояние m(t) цепи Маркова, управляющей входящим MAP-потоком, и значения остаточного времени обслуживания для каждой заявки, находящейся в системе в момент t. Таким образом, получаем многомерный марковский процесс с переменным числом компонент. Прямое исследование такого процесса не представляется возможным ввиду переменного и потенциально неограниченного количества его компонент. В связи с этим в настоящей работе применяется метод динамического просеивания (просеянного потока) [21], который позволяет решить указанную задачу. Основная идея этого подхода заключается в том, чтобы заменить исследование многомерного процесса с переменным числом компонент на исследование двумерного марковского процесса {n(t), m(t)}, где n(t) - считающий процесс просеянного потока, который конструируется следующим образом. Зафиксируем некоторый момент времени T. Будем считать, что заявка, поступившая в систему в момент времени t < T, с вероятностью S(t) = 1 - B(T - t) формирует событие просеянного потока, а с вероятностью 1 - S(t) эта заявка не рассматривается. Через n(t) обозначим число событий просеянного потока, наступивших до момента времени t. Тогда, если в начальный момент времени t0 < T система свободна, получаем, что для момента времени T имеет место равенство P{i(T) = k} = P{n(T) = k)} для любых целых k > 0. Таким образом, найдя распределение вероятностей значений процесса n(t) в момент времени t и полагая t = T, в силу произвольности выбора T получим искомое стационарное распределение вероятностей процесса i(t). Для распределения вероятностей P(n, m, t) = P{n(t) = n, m(t) = m} значений марковского процесса {n(t), m(t)} можно составить следующую систему дифференциальных уравнений Колмогорова: 1 8P(n,m,t) M< Е [P(n,/,t) (Do ) + P(n,l,t) (D ) ш (1 - S(t)) + P(n -1,/,t) ( Д )ы S(t)] N 8t /=1L для n > 0, m = 1, M . Для частичной характеристической функции H(u,m,t) = ЕeJunP(n,m,t). n=0 где j = V-T, эта система перепишется в виде 1 бЩн^О =Е | (u^, t )(D0 )m + H (u,l, t )(DX) (1 - S (t)) + H (u,/, t )(DX \mS (t )eJu N 8t /=1 Приводя подобные и используя обозначения D = D0 + Db H(u, t) = {H(u, 1, t), ..., H(u, M, t)}, получим матричное дифференциальное уравнение _L^H8ut) = H(u,t)|d + DX (eJu - 1)s(t)] (3) с начальным условием H(u, t0) = 8. (4) Так как прямое решение уравнения (3) не представляется возможным, для решения задачи (3)-(4) воспользуемся методом асимптотического анализа [21] в условии растущей интенсивности входящего потока, т.е. при N ^ да. 3. Асимптотический анализ 3.1. Асимптотика первого порядка - = в, u = sw , H(u, t) = F1(w,t, s) . N w Выполним в выражениях (3)-(4) следующие замены: Тогда задача (3)-(4) примет вид s5F1( W,t,S) = F (w, t, s)|D + ^ F1(w,t,s)[D + D1 (ejsw -1)5(t)], (5) F1(w, t0, s) = 8. (6) Относительно асимптотического решения F1(w, t) = lim F1(w, t, s) этой задачи имеет место следующее утверждение. Теорема 1. Асимптотическое решение задачи (5)-(6) имеет вид F1 (w, t) = 8 exp j jwk] S (x)dxj, (7) где 8 и А определяются выражениями (2) и (1) соответственно. Доказательство выполним в два этапа. Этап 1. Положим в (5) s ^ 0, получим F1(w, t)D = 0. Сравнивая это равенство с первым уравнением (2), можем сделать вывод, что F1(w,t) может быть представлена в виде F1(w, t) = 8Фl(w, t), (8) где Ф^, t) - некоторая скалярная функция, в силу (6) удовлетворяющая условию Ф^, t0) = 1. Этап 2. Домножим (5) на вектор e, подставим (8), поделим результат на s и выполним предельный переход s ^ 0. Тогда с учетом того, что De = 0 и 8e = 1, получим дифференциальное уравнение относительно функции Ф^, t) 5Ф1 (w,t) ^ . . . , . -1V ' 7 = Ф1 (w, t) jw AS(t), dt решение которого с учетом начального условия дает j t j Ф^, t) = exp

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