Предельные теоремы для одного класса поллинговых моделей тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

На правах рукописи УДК 519.21

Сергеев Артём Александрович

ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ ОДНОГО КЛАССА ПОЛЛИНГОВЫХ МОДЕЛЕЙ

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва 2006

Работа выполнена на кафедре теории вероятностей Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор Л. Г. Афанасьева

Официальные оппоненты: доктор физико-математических наук,

Защита диссертации состоится 12 мая 2006 года в 16 часов 15 минут на заг седании диссертационного совета Д.501.001.85 в Московском государственном университете имени М. В. Ломоносова по адресу: 119992, ГСП-2, г. Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета (Главное здание, 14 этаж).

Автореферат разослан 12 апреля 2006 года.

профессор В. А. Каштанов

доктор физико-математических наук, доцент В. В. Ульянов

Ведущая организация: Институт проблем передачи

информации РАН

Учёный секретарь диссертационного совета Д.501.001.85 в МГУ, доктор физико-математических наук, профессор

Т. П. Лукашенко

OCXS &

Ов

Общая характеристика работы

Актуальность темы.

Многие реально существующие объекты (компьютерные, коммуникационные, транспортные сети и т.п.) математически могут быть описаны как сети массового обслуживания. Из разнообразных сетей обслуживания в отдельную группу выделяют системы поллинга, которые состоят из конечного числа станций (узлов), посещаемых одним или несколькими обслуживающими приборами. В на, стоящее время теория поллинговых систем активно развивается, о чём свидетельствует обширная отечественная и зарубежная литература. Среди прочих можно выделить работы Боровкова - Шассбергера1, Делкуаня, Файоля2,8, ' Фосса4.

К типу поллинговых можно отнести системы, в которых обслуживание состоит в перемещении требований от одной станции к другой. Такие модели естественно возникают при описании транспортных сетей. , Одна из первых задач при анализе поллинговых моделей — определение усло-

вий существования стационарного распределения. Другая задача состоит в отыскании этого стационарного распределения или построении приемлемых оценок г для него. Здесь возникают существенные трудности, поскольку даже в простейших предпосылках (все характеристики имеют показательное распределение) случайный процесс, описывающий функционирование системы, оказывается достаточно сложным. В связи с этим внимание исследователей сосредоточено на получении предельных теорем типа закона больших чисел для симметричных сетей, когда число узлов и число приборов велико5,8. Если входящий поток тре-

'Borovkov A.A., Schönberger R A. Ergodicity of a polling network // Stoch. Proceeees Appl. —1004. — V. 50. — P. 263-282.

'Delcoigne F., Fayolle G. Thermodynamic limit and propagation of chaoa in polling eyeteme // Markov Proceam Heist, field*. -1009. - V. 5, * 1. - P. 80-124.

'Fayolle G., Lasgoutte* J.M. A »tate-dependent polling model with Markovian routing // IMA Volume* in Math. к it* Applications. -1006. - V. 71. - P. 28S-301.

4Фосс С.Г., Чернова Н.И. Теоремы сравнения ■ »ргодгаескке свойства систем поллинга // Проблемы передача информации. —1006. — Т. 32, вып. 4. — С. 46-71.

'Afanasrieva L.G., Fayolle G , Popov S.Yu. Models for transportation network* //1. Math. Sei. —1007. - V. 84, »3.-P. 1001-1103.

'Введенская Н.Д., Добрушин PJL, Карпелевго Ф.И. Система обслуживания с выбором наименьшей из двух очередей - асимптотически* подход // Проблемы передача информации. —1006. — Т. S2, вып. 1. — С. 20-

РОС НАЦИОНАЛЬНАЯ

CUCJIUOTPIfi

бований пуассоновский, а времена движения приборов имеют показательное распределение, то состояние системы описывается марковским процессом со счётным фазовым пространством и сходимость к некоторой динамической системе вытекает из известной теоремы об эквивалентности сходимости полугрупп сдвига, порождённых марковским процессом, на конечном временном отрезке и их производящих операторов на существенном подпространстве области определения7. Подобный подход был использован рядом авторов при анализе коммуникационных сетей8. Сети с произвольно распределённым временем обслуживания также рассматривались в литературе9,10 с помощью введения марковского процесса с достаточно сложным фазовым пространством и существенного использования специфики сети.

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

Согласно обзору в статье Карпелевича и др.11, этот метод в «интуитивной» форме известен математикам и инженерам довольно давно — с 60-х годов XX века, однако, вопрос о строгом обосновании всех описанных шагов сталкивается с большими трудностями. Авторы обзора называют гипотезой Р. Л. Добрушина утверждение о том, что указанный метод действительно можно строго обосновать математически в большинстве систем. Одной из первых работ, посвя-щённых исследованию справедливости гипотезы Добрушина, является статья Столяра12, где изучена замкнутая сеть с детерминированным временем обслу-

rEthier S.N., Kurts T.G. Markov ргоовжй: Characterisation and convergence. — New York: J. Wiley, 1986. — 544 p.

"См., например, упомянутую работу Введенской в др.

*Vveden*kaya N.D., Suhov Yu.M. Dobruihin'a mean-field approximation for a queue with dynamic routing // Markov Processes Heiat. Fields. - 1997. - V. 3, * 4. - P. 493-626.

'"Карпелевнч Ф.И., Рыбко A.H. Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе // Проблемы передачи информации. — 2000. — Т 36, вып. 2. — С. 69-95.

"Karpelevich F.I., Pechersky Е A., Suhov Yu.M. Dobrushin's approach to queueing network theory // J. Appl. Math. Stoch. Anal. -1996. - V. 9, * 4. - P. 379-397.

"Столяр А.Л. Асимптотика стационарного распределения для одной замкнутой системы массового обслуживания // Проблемы передачи информации. —1989. — Т. 25, аьш. 4. - С. 80-92.

живания. Эта тема затрагивалась и в упомянутых выше работах Карпелеви-ча - Рыбко и Введенской и др., а также в недавно вышедшей статье Рыбко и Шлосмана13.

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

Цель работы.

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

Научная новизна.

Все полученные результаты являются новыми. Стоит отметить, что транспортные сети с произвольно распределённым временем движения, несмотря на популярность поллинговых моделей, прежде в научных работах не рассматривались. Предпринятые исследования потребовали разработки новых подходов, поскольку даже для сетей с пуассоновскими входящими потоками требований, время движения приборов в которых распределено не экспоненциально, не удалось применить известные методы анализа систем массового обслуживания и сетей Джексона. Основные результаты работы состоят в следующем.

1. Найдены условия, при которых имеет место асимптотическая независимость любого конечного множества узлов и любой конечной группы приборов при стремлении числа узлов к бесконечности.

13Rybko A.N., Sblonnao S. Poiaaon Hypotheria for information networks (A study in non-linear Markov proceasea). http://arxiv.org/abe/math-ph/0303010

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

3. Доказана сходимость случайного процесса, описывающего состояния узлов сети, к динамической системе (в смысле слабой сходимости конечномерных распределений процесса).

4. Для сети без мест для приборов в узлах доказана глобальная устойчивость предельной динамической системы, найден явный вид точки-аттрактора.

5. Для этой же модели получены достаточные условия эргодичности случайного процесса, описывающего её состояния, и сходимости эргодических мер при стремлении числа узлов к бесконечности.

6. Для системы с местами для ожидания приборов и распределением времени обслуживания специального вида (смесь распределений Эрланга) доказана сходимость к предельной динамической системе, найден вид стационарного решения; доказана его инвариантность относительно параметров распределения при фиксированном математическом ожидании.

Методы исследования.

В диссертации используются классические и современные методы теории массового обслуживания и теории случайных процессов (мажорирование, теорема Смита, метод Кифера - Вольфовица, метод расщепления и теорема Боровко-ва об эргодичности асимптотически стохастически непрерывного марковского процесса). Подход к доказательству глобальной устойчивости и сходимости эргодических мер во многом аналогичен использованному Введенской, Добруши-ным и Карпелевичем для анализа открытых многоканальных систем массового обслуживания. Изучение получающихся в пределе динамических систем потребовало использования ряда утверждений, относящихся к теории обыкновенных дифференциальных уравнений и уравнений с частными производными.

Теоретическая и практическая ценность.

Диссертация носит теоретический характер. Её методы и результаты могут найти применение в дальнейшем исследовании псшлинговых моделей.

Апробация работы.

Результаты диссертации докладывались и обсуждались на семинаре «Случайные процессы в теории массового обслуживания», на Большом семинаре кафедры теории вероятностей Механико-математического факультета МГУ (20042005 гг.), а также на Всероссийской школе-коллоквиуме по стохастическим методам (Сочи-Дагомыс, 1-7 октября 2005 г.) и на Воронежской зимней математической школе С. Г. Крейна (Воронеж, 27-30 января 2006 г.). Тематика работы была поддержана грантом РФФИ 05-01-00256.

Публикации.

Результаты диссертации опубликованы в 6 работах, список которых приведён в конце автореферата.

Структура диссертации.

Диссертация состоит из введения, двух глав (разбитых на разделы), заключения и списка литературы, насчитывающего 26 наименований. Общий объём диссертации — 88 страниц.

Краткое содержание диссертации

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

Первая глава посвящена сетям массового обслуживания, в которых приборы передвигаются между узлами безостановочно. Вначале даётся подробное описание изучаемой модели.

Рассматривается открытая сеть, состоящая из N узлов и М приборов, перемещающихся между ними, при этом M/N -л г при 7V —► оо (0 < г < оо). В каждом узле имеется L мест для ожидания требований (L ^ оо), места для

ожидания приборов отсутствуют. Если в момент прихода требования в узле есть свободные места для ожидания, то оно присоединяется к очереди, в противном случае теряется. Дождавшись прибора, требование выбирает равновероятно узел назначения, в который и направляется. По прибытии в этот узел требование покидает сеть, а прибор либо забирает другое требование, если очередь из них в узле непуста, либо покидает его без требования и с равной вероятностью направляется в любой узел. Мы предполагаем, что потоки требований в разные узлы взаимно независимы и одинаково распределены, а времена перемещений приборов независимы друг от друга и от входящих потоков и имеют общую функцию распределения В(х), причём В(+0) < 1 (движения приборов не мгновении). Эти предположения распространяются также на начальные условия: количества требований в узлах в начальный момент времени являются взаимно независимыми одинаково распределёнными случайными величинами; все приборы начинают движение в узлы либо уже движутся, и их остаточные времена движения взаимно независимы и имеют общую функцию распределения В(х) (совпадающую с В(х) в первом случае).

Зафиксируем произвольный узел системы. Пусть Х{Ь) — количество требований, поступивших в этот узел за время [0, £], У14^) — количество прибытий приборов в него в течение того же временного отрезка, 5^(4) — число требований в узле в момент Ь, (<) — число передвижений (окончаний движения) ¡-то прибора вплоть до момента

Теорема 1. Последовательность случайных процессов {УЛГ(<)} слабо сходится при N ос к пуассоновскому процессу У(£) с ведущей функцией гУ{€), гдеУ(г) =

Доказательство опирается на теорему Григелиониса14, поскольку при отсутствии мест для ожидания приборов представляет собой сумму независимых процессов восстановления.

Рассмотрим систему массового обслуживания, поток требований в которую Х(*) в стохастическом смысле такой же, как в узел рассматриваемой сети. Приборы приходят в систему в соответствии с нестационарным пуассоновским по-

14Грнгелионнс Б И. Предельные теоремы для сумм процессов восстановления // В сб Кибернетику на службу коммунизму - М.-Л.: Энергия, 1964. - Т. 2. — С. 246-265.

током Y(t) с ведущей функцией rV{t). Имеется L мест для ожидания требований, места для ожидания приборов отсутствуют. Принцип взаимодействия требований и приборов тот же, что и в узле исходной сети. Пусть q(t) — число требований в такой системе. Путём установления функциональных связей между введёнными случайными процессами для узла исходной сети и для вспомогательной системы (например, при L — оо qN(t) = ZN(t) — WN(t), где ZN(t) = qN(0)+X{t) - YN(t), W«(t) = min[0,inf0^( ZN{s)]) доказывается следующее утверждение.

Теорема 2. Если qN(0) Л q(0) при N оо, то последовательность случайных процессов {^(i)}^-! слабо сходится к случайному процессу q(t).

Заметим, что предельная система может быть сведена к одноканальной системе массового обслуживания, обозначаемой в символике Кендалла GI\M{t)\\\L.

Приведённые выше утверждения справедливы для широкого класса поллин-говых моделей. Наиболее интересные результаты (эргодичность сети, сходимость предельных вероятностных мер) удаётся получить при дополнительных ограничениях: требования поступают в каждый узел в соответствии с однородным пуассоновским потоком X{t) интенсивности А, у распределения времени движения приборов существует абсолютно непрерывная компонента и среднее, равное а. В этом случае предельные вероятности состояний узла сети pj(t) = = P{g(£) — j} являются решением системы уравнений

Po(t) = ~^Mt) + rv(t)Pl(t) (1)

p'j(t) = A(p,-_,(t) + rv(t)(pj+i(t) —Pj(t)), j = 1,2,... (2)

(r(i) = V'(t)) в случае L = оо. Если L < оо, то первые L уравнений этой системы сохраняются, и к ним добавляется уравнение

p'L(t) = \pL-i(t) - rv(t)pL(t). Данная система дифференциальных уравнений глобально устойчива.

Теорема 3. Пусть р = —. Если L — оо, р < 1, то при любых начальных

г

условиях, являющихся вероятностным распределением, lim pj(t) = fP(\ — р), j = 0,1,...

Если же L = оо, р ^ 1, то lim pj{t) = О, j = 0,1,... В случае конечного L

í—юо

при любых значениях р

Результат теоремы 3 остаётся верным и в случае пуассоновского входящего потока с переменной интенсивностью A(t), имеющей предел при t —у оо: lim A(í) = À > 0.

Вернёмся к рассмотрению исходной сети в целом. Её поведение характеризуется случайным процессом

$*(«)-(if (*),■•.,«£(«))■

Теорема 4. Если входной поток требований в каждый узел пуассоновский с параметром À, а число мест для них в узле L < оо, то случайный процесс q1* (t) обладает предельным при t оо распределением вероятностей состояний, не зависящим от начальных условий ¡^(О). То же справедливо и для случая L — 00 при выполнении дополнительного условия А <

В основе доказательства теоремы лежит утверждение из книги A.A. Воров-кова15 об условиях эргодичности асимптотически стохастически непрерывного марковского процесса. Используются также теорема Смита для регенерирующих процессов16 и метод Кифера - Вольфовица17.

Следующий результат касается сходимости предельных при í —► оо вероятностных мер, когда число узлов в системе неограниченно растёт. Итак, при некоторых условиях для каждого N € N на множестве {0,1,..., L}N определена вероятностная мера я>(-), к которой сходятся при í —» оо распределения процесса <?*(t) в каждый момент времени при любых начальных условиях. Для вектора k Е Z+ — некоторого состояния сети — введём функцию

«(*) = («„(£),«,(*),...), где

"Боровков А А. Эргодичность я устойчивость случайных процессов. — М.: Эдиториал УРСС, 1999.—440 с.

"Smith W.L. Regenerative stochastic processes // Proc. Roy. Soc Ser. A. - 1956 — V 232. — P 6-31.

"Kiefer J., Wolfowitz J. On the theory of queues with many servers // Trans. Amer Math. Soc —1955. — V 78.-P. 1-18.

Значения этой функции принадлежат множеству

17 = {(uo,«i,...): 1 = «о •••><)}.

Рассмотрим случайный процесс

ико, .

В силу того, что значение процесса Un{t) однозначно определяется значением процесса fit): UN{t) = u{q"{t)), функция PN(ti) = „ф^МФ на U является предельной вероятностной мерой процесса Un(t), сходимость к которой имеет место при любых начальных условиях.

Теорема 5. Если число мест для требований в узлах L бесконечно, то при

р — — <1 последовательность предельных вероятностных мер 0n случай-г

ных процессов описывающих состояния узлов исходной сети, слабо схо-

дится при N —> оо к вероятностной мере, сосредоточенной в точке g* £ U, где

9i — Я*) » = 0,1,...

При конечном L приведённое выше утверждение верно в любом случае, а точка д* имеет вид

Отметим, что точка д* соответствует пределу при £ —► ос решений системы уравнений (1)-(2). Таким образом, гипотеза о независимости устойчивой точки и других предельных характеристик сети от конкретного вида распределения времени перемещения приборов В{х) при фиксированном среднем а подтверждается для данного типа моделей. Кроме того, теорема позволяет вычислять многие из этих характеристик. Например, справедливо

Следствие 1. Пусть L < оо, L*(u) = — средняя длина очереди в

узле системы (и € U). Тогда

lim ЕлгГ(в) - ¿rf - LpL+jL~l)r + - + 2f + P,

где Ejv — математическое ожидание по стационарной мере случайного процесса Un-

Окончание главы посвящено одной дискретной поллинговой модели без мест для приборов в узлах. Входящие потоки в узлы являются пуассоновскими с параметром А. Все приборы начинают движение в начальный момент времени и достигают узлов за постоянное время, равное единице. Данная система проанализирована методами теории случайных блужданий. Основным результатом раздела является

Теорема 6. Пусть 0 < t < 1. Тогда для всех j 6 Z+

lim Р+ <) = Я = £ = 3 ~ т)^-*.

п—уоо ■ ' 771.

т=О

где q^ — случайная величина, распределение которой задаётся производящей функцией

ехр {£ * £ * S ^-«Cfr* (1 ~ ЪГ~т)

п = 1=1 t=1t7-А

ехр {£ £ i £ <* -

^ ;=1 *=1 т=0 J

Во второй главе рассматриваются более сложные модели — сети, в которых приборы могут задерживаться в узлах, ожидая прихода требований. В результате процессы движения приборов перестают быть процессами восстановления и становятся зависимыми друг от друга и от состояний узлов. В начале главы приведены две модели, на примере которых показано, как можно преодолевать эти трудности — благодаря специальному виду функции распределения времени движения приборов в первой (смесь распределений Эрланга) и дискретности во второй — эволюцию системы всё-таки можно описать цепью Маркова. В обоих случаях оказалось, что стационарная точка предельной динамической системы зависит не от конкретного вида функции распределения времени движения приборов, а лишь от его математического ожидания. Отметим также, что смесью распределений Эрланга можно приблизить широкий класс функций распределения. Далее приводятся предельные теоремы для более общего случая сетей с местами для приборов в узлах.

Рассматривается открытая сеть S, состоящая из N узлов и М приборов, перемещающихся между ними. В каждом узле имеется L мест для ожидания

требований и К мест для ожидания приборов (L < оо, К < оо). Если в момент прихода требования в узле есть приборы, то один из них забирает это требование и равновероятно выбирает узел назначения, в который и направляется. По прибытии в этот узел требование покидает сеть, а прибор либо становится в очередь, если нет требований и есть места для ожидания приборов, либо забирает требование, если очередь из них непуста, либо покидает его и с равной вероятностью направляется в любой узел, если все места для ожидания приборов заняты. Требование, заставшее в узле все места для ожидания занятыми, теряется. Таким образом, в каждом узле находятся либо требования, либо приборы, либо узел свободен. Мы предполагаем, что потоки требований в разные узлы взаимно независимы и одинаково распределены, а времена перемещений приборов независимы друг от друга и от входящих потоков и имеют общую функцию распределения В(х). Предельные теоремы доказываются в предположении, что число узлов N и число приборов М стремятся к бесконечности так, что M/N г (0 < г < оо). При этом на функцию распределения времени перемещения В(х) наложено условие

1 - В(х) > е~>"

для некоторого р > 0 и всех х ^ 0.

Рассмотрим случайный процесс qfit), характеризующий состояние t-го узла в момент t в сети с N узлами. При этом qf{t) = j, если в узле в момент t имеется j требований, q?(t) = —j, если там находится j приборов, и qf(t) = 0, если узел свободен.

Теорема 7. При любом фиксированном I € N и t > 0 случайные процессы {qi(s),8^t},...,{qfi(s),8 ^ t} асимптотически независимы, то есть для любых моментов времени «ii,...,«iirai,...,«/i,...,«/)Fn,, предшествующих моменту t, и целых чисел Лц,...,.,.,кц,...,kiitn,

i

= *у,»' = = Mi} - П = *y.J = Mi} -> о

i=l

при N —¥ оо. Предполагается, что для любого N случайные величины (<?^(0),

j — 1, N) взаимно независимы и одинаково распределены.

Теорема доказывается введением множеств общения узлов за определённое время. Определим для фиксированного узла г и момента времени £ множество Д(*), предположив, что Д-(*) = {1}, если до момента времени * в узел не прибывало никаких приборов. В противном случае пусть * 1 < < — последний момент времени, когда прибыл прибор, например, из узла ]. Тогда положим

Д(*) = Д(«,-0) и £>,(*!-0).

Сеть 5 по средней мощности множества общения произвольного узла можно мажорировать сетью ■!>, в которой узлы не имеют мест для ожидания приборов, а времена их перемещений распределены по показательному закону с параметром ц. Ключевыми в дальнейшем доказательстве являются утверждения, что средняя мощность множества общения к моменту ( во вспомогательной сети может быть оценена сверху величиной, не зависящей от N, и что случайные процессы, описывающие состояния узлов вплоть до момента I, условно независимы при условии, что соответствующие множества общения за время < не пересекаются.

Из теоремы об асимптотической независимости узлов сети и теоремы Севаг стьянова18 о сумме зависимых случайных индикаторов следуют теоремы, аналогичные доказанным в первой главе (смысл обозначений сохраняется).

Теорема 8. Если существует предел У(<) = Нтдг-юо Е^(Ь), то последовательность случайных процессов слабо сходится при N —> оо к пуас-соновскому процессу У(£) с ведущей функцией гУ{1).

Теорема 9. Если существует Шплг-моЕ !>*(*) = У(Ь) и имеет место сходимость 5^(0) —-—► я(0), то последовательность случайных процессов N —юс

слабо сходится к случайному процессу

Случайный процесс <?(£) описывает состояние системы массового обслуживания (в том же смысле, в котором определено состояние узла на с. 11), поток требований в которую в стохастическом смысле такой же, как и в узел сети «5, а приборы поступают в соответствии с нестационарным пуассоновским процессом с ведущей функцией гУ(£). Количества мест для ожидания требований и

"Севастьянов В А. Предельны! закон Пуассона в схеме сумм зависимых случайных величин // Теория вероятн ■ ее примен - 1972. — Т. 17, вып. 4. - С. 733-738.

приборов в системе, а также принцип взаимодействия заявок и приборов те же, что и для сети 5.

В заключении ещё раз выделены основные результаты работы и очерчено её место в круге современных исследований поллинговых моделей.

Автор выражает глубокую признательность своему научному руководителю профессору JI. Г. Афанасьевой за ценные обсуждения и всестороннюю поддержку в течение всего диссертационного исследования.

Работы автора по теме диссертации

[1] Сергеев A.A. Предельные теоремы для одного класса поллинговых моделей // Теория вероятностей и ее применения. — 2005. — Т. 50, вып. 3. — С. 585593.

[2] Afanasieva L., Sergeev A. Large transportation networks with general distribution of travel time // XXV International Seminar on Stability problems for Stochastic Models. Transactions. — Maiori/Salerno, Italy, 2005. — P. 2-7.

JI. Г. Афанасьевой принадлежит постановка задачи и гипотеза асимптотической независимости узлов. А. А. Сергееву принадлежит проверка этой гипотезы с помощью множеств общения.

[3] Сергеев А. А. Глобальная устойчивость одной поллинговой модели с подвижными приборами // Воронежская зимняя математическая школа С. Г. Крей-на 2006. Тезисы докладов. - Воронеж, 2006. - С. 92-95.

[4] Сергеев A.A. Предельные теоремы для случайных процессов, характеризующих работу системы массового обслуживания с подвижными приборами // Обозрение прикладной и промышленной математики. —2005.— Т. 12, вып. 3. —С. 680.

[5] Afanasieva L., Sergeev A. Thermodynamic limit in a model of transportation network // International Conference Modern Problems and New Trends in Probability Theory. Abstracts. - Chernivtsi, Ukraine, 2005. - P. 18-19.

Л. Г. Афанасьевой принадлежит идея использования теоремы Севастьянова при доказательстве предельных теорем. А. А. Сергееву принадлежит исследование получающихся случайных процессов.

[6] Сергеев A.A. Дискретизированная открытая транспортная сеть с произвольным временем обслуживания // Воронежская зимняя математическая школа - 2004. Тезисы докладов. - Воронеж, 2004.-С. 98.

»

'I í

I

о

I 1

<

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносов! Подписано в печать ОЗ. 0*1. &6 Формат 60x90 1/16. Усл. печ. л. С

Тираж Заказ //

*t

Я,00вА 770&

'77 06

Введение

1 Сети без мест для ожидания приборов

1.1 Описание модели.

1.2 Предельные теоремы для фиксированного узла большой сети

1.3 Предельная динамическая система в случае пуассоновского входящего потока.

1.4 Эргодичность сети.

1.4.1 Теорема Боровкова.

1.4.2 Случай конечного числа мест для требований в узлах

1.4.3 Случай бесконечного числа мест для требований в узлах

1.5 Сходимость предельных вероятностных мер

1.6 Сеть с детерминированным временем обслуживания.

2 Сети с местами для ожидания приборов

2.1 Сеть с распределением времени обслуживания специального вида.

2.1.1 Построение марковского процесса.

2.1.2 Генератор марковского процесса.

2.1.3 Сходимость полугрупп.

2.1.4 Стационарный режим.

2.2 Сеть с решётчатым распределением времени обслуживания G

2.2.1 Сходимость к детерминированному процессу.

2.2.2 Стационарный режим.

2.3 Общая модель — постановка задачи

2.4 Асимптотическая независимость узлов.

2.5 Предельные теоремы для фиксированного узла большой сети

Предлагаемые в данной работе модели могут быть отнесены к классу поллинговых. Поллииговая модель является системой массового обслуживания, состоящей из некоторого количества станций обслуживания (узлов) и некоторого количества приборов, осуществляющих обслуживание поступающих в узлы требований. Приборы могут передвигаться между узлами, выбирая узел назначения в соответствии с некой стохастической матрицей маршрутизации (pij). Случайные времена перемещения приборов образуют матрицу движения также индексируемую номерами узла отправления и узла назначения. Основное отличие поллинговых моделей от сетей Джексона в том, что по сети перемещаются не требования, а приборы. Изначально исследовались поллинговые модели с одним прибором, который совершает обход узлов по некоторому правилу. Первые результаты в этом направлении принадлежат Боровкову и Шассбергеру [1]. Также можно выделить работы Делкуаня, Файоля [2, 3], Фосса [4, 5]. Однако изучаемые в данной работе модели имеют некоторое отличие, состоящее в том, что приборы либо не задерживаются в узлах, либо задерживаются, стоя в очереди, а не обслуживая требования. Собственно, само обслуживание состоит в перемещении требований из одного узла в другой.

Другая уместная аналогия — транспортные сети. Эти модели также предполагают наличие определённого количества узлов и обслуживающих заявки приборов, закономерности передвижения которых описываются матрицами маршрутизации и движения. Транспортные сети отличаются от поллинговых моделей тем, что обслуживание поступающих требований состоит в их перемещении в нужный узел с помощью прибора, после чего они покидают систему. Этот раздел теории массового обслуживания был довольно популярен в 90-ые годы. Целый ряд полезных моделей был изучен Афанасьевой, Файолем [6, 7], Оселедцем, Хмелёвым [8] и другими исследователями.

Иногда модели, подобные описанным в работе, удобно понимать как системы со взаимодействием частиц двух типов. Частицы первого типа поступают в узлы извне, частицы второго типа (аннигиляторы) находятся в системе и, будучи в узле, уничтожают частицы первого типа. Таким образом, возможны три интерпретации объектов изучения данной работы: поллинговые модели, транспортные сети и системы со взаимодействием частиц двух типов.

Одна из первых задач и при анализе поллинговых моделей, и при анализе транспортных сетей — определение условий существования стационарного распределения. В этом направлении имеется ряд интересных результатов (см., например, [1, 7, 9]). Другая задача — отыскание этого стационарного распределения или построение приемлемых оценок для него. Здесь возникают существенные трудности, поскольку даже в простейших предпосылках (все характеристики имеют показательное распределение) случайный процесс, описывающий функционирование системы, оказывается достаточно сложным. В связи с этим внимание исследователей сосредоточено на получении предельных теорем типа закона больших чисел для симметричных сетей, когда число узлов N и число приборов М велико [6, 7, 10, И]. Если входящий поток требований пуассоновский, а времена движения приборов имеют показательное распределение, то состояние системы описывается марковским процессом со счётным фазовым пространством и сходимость к некоторой динамической системе вытекает из известной теоремы об эквивалентности сходимости полугрупп сдвига, порождённых марковским процессом, на конечном временном отрезке и их производящих операторов на существенном подпространстве области определения [12]. Подобный подход был использован рядом авторов при анализе коммуникационных сетей [10, 11]. Сети с произвольно распределённым временем обслуживания рассматривались в работах [13, 14], где вводился марковский процесс с достаточно сложным фазовым пространством и существенно использовалась специфика сети. Изучаемые в данной работе модели содержат самые общие ограничения на структуру входных потоков требований, а времена перемещения приборов имеют, вообще говоря, произвольное распределение. Зависимость функционирования системы от прошлого оказалась очень сложной, и кажущийся весьма перспективным метод рассмотрения состояния сети из N узлов как распределения вероятностей на состояниях отдельного фиксированного узла и анализа системы с помощью аппарата теории функций и функционального анализа, разработанный в [14], применить не удалось. Вместо этого предлагаются другие подходы, которые будут описаны ниже.

Работа состоит из двух частей. В первой части изучаются модели без мест для ожидания приборов в узлах. Сеть состоит из N узлов, между которыми передвигаются М приборов. В каждый узел поступают требования. В ожидании прибытия прибора, который переместит их в другой узел узел назначения выбирается равновероятно), они встают в очередь. Длина очереди в узлах может быть как конечной, и тогда рассматриваемая модель становится сетыо с отказами, так и бесконечной. Если прибор по прибытии в узел не застаёт там требований, он сам равновероятно выбирает узел назначения и немедленно уезжает туда. Входные потоки требований в узлы независимы и одинаково распределены. Времена движения приборов также независимы друг от друга и от входных потоков и одинаково распределены. В такой модели движения приборов не зависят от длины очереди из требований в узлах. Начало главы посвящено доказательству предельных теорем для случайных процессов, описывающих функционирование одного отдельно взятого узла, в предположении, что число узлов N и число приборов М стремятся к бесконечности так, что M/N —у г (0 < г < оо). Доказательство слабой сходимости входящего в узел потока приборов к нестационарному пуассоновскому процессу (теорема 1.1) опирается на известную теорему Григелиониса [15], поскольку движения приборов образуют взаимно независимые процессы восстановления. Далее путём установления функциональных соотношений между вышеуказанными случайными процессами из этого факта выводится теорема 1.2 о сходимости случайного процесса, описывающего состояние узла (под состоянием узла понимается длина очереди в нём), к случайному процессу, описывающему состояние некоторой предельной системы, которая может быть интерпретирована как одно-канальная система массового обслуживания. При таком подходе теоремы остаются верными не только при пуассоновском входном потоке требований в узлы, что являлось существенным ограничением в других работах на эту тему. Для случая стационарных пуассоновских входных потоков оказалось возможным доказать сходимость предельной динамической системы к некоторой точке и найти условия, при которых она является вероятностным распределением (теорема 1.3), а также доказать эргодические теоремы для всей сети (теоремы 1.5, 1.6). Доказательство теорем опирается на введение дополнительных переменных, соответствующих остаточным временам движения ириборов, и построение вспомогательных конструкций, с тем чтобы были выполнены условия теоремы Боровкова [16] об эргодичности асимптотически стохастически непрерывного марковского процесса. Используется в доказательстве и метод Кифера - Вольфовица [17]. Также найдены достаточные условия сходимости при N —> оо эргодических мер на фактор-пространстве состояний исходной сети к вырожденной мере, сосредоточенной в точке, которая найдена в теореме 1.3. Этот факт, выраженный теоремой 1.7, подтверждает естественную гипотезу о независимости устойчивой точки предельной динамической системы от вида распределения времени движения приборов при фиксированном среднем значении. Кроме того, теорема имеет ряд полезных следствий, касающихся предельного поведения различных характеристик сети при N оо: длины очереди в узлах, вероятности отказа и т.п. Заканчивается глава рассмотрением модели, описанной на языке частиц и аннигиляторов. Частицы поступают в каждый из N узлов в соответствии с пуассоновским потоком, а М = rN аннигиляторов, осуществляя безостановочное перемещение между узлами за единичное время, уничтожают одну из частиц, находящихся в узле, куда они прибыли. С помощью теорем о случайных блужданиях, доказанных в [18], для числа частиц в узле в целые моменты времени п найдена производящая функция предельного распределения при п —> оо теорема 1.8). Вообще же число частиц в узле представляет собой периодический случайный процесс в смысле теоремы 1.9.

Класс моделей, рассмотренных во второй части диссертации, отличается только наличием мест для стоянки приборов в узлах. Количество этих мест также может быть как конечным, так и бесконечным. При конечном числе мест ожидания прибор, найдя все эти места в узле прибытия занятыми, сам равновероятно выбирает следующий узел назначения и отправляется в него без клиента. Из-за того, что приборы могут задерживаться в узлах, процесс движения прибора перестаёт быть процессом восстановления, более того, становится зависимым от состояний узлов (числа требований или числа приборов в них) и от процессов движения других приборов. Поэтому теорему Григелиониса в этом случае применить не удаётся. В предположении, что выполняется условие (2.14), физический смысл которого заключается в том, что время перемещения приборов стохастически больше некоторой показательно распределённой случайной величины, установлена асимптотическая независимость случайных процессов, выражающих состот яиия любого конечного набора узлов сети (теорема 2.3), и, как следствие, асимптотическая независимость случайных процессов, описывающих движения приборов, при стремлении числа узлов N к бесконечности. Доказательство проводится с использованием конструкции множеств общения узлов, идея которых заимствована из работы [19]. Утверждение о сходимости потока приборов в фиксированный узел к нестационарному пуассоновскому процессу при N —у оо (теорема 2.4), аналогичное теореме 1.1, следует из теоремы Севастьянова [20] о сходимости последовательности сумм зависимых индикаторов и из асимптотической независимости процессов движений любого конечного множества приборов. Теорема 2.5 о сходимости состояний фиксированного узла по распределению к состояниям некой предельной системы массового обслуживания формулируется и доказывается аналогично теореме 1.2. Модель с наличием мест для приборов в узлах является более сложной, поэтому основную гипотезу о независимости стационарного режима предельной динамической системы от вида распределения времени движения приборов при фиксированном среднем значении доказать не удалось, но она представляется весьма правдоподобной и в этом случае, что некоторым образом подтверждается её справедливостью в частных случаях сети с непрерывным распределением времени обслуживания специального вида (раздел 2.1) и сети с решётчатым распределением времени обслуживания (раздел 2.2). В разделе 2.1 рассмотрена сеть с распределением времени движения приборов, представляющим собой смесь распределений Эрлан-га. Такую модель можно интерпретировать так, что становится возможным построить марковский процесс со счётным фазовым пространством, описывающий эволюцию сети, и анализировать его поведение известными методами. Схема доказательства сходимости на конечном временном интервале полугрупп сдвига, порождённых фактор-процессом этого марковского процесса, к полугруппе сдвига некоторой предельной динамической системы (теорема 2.1) довольно стандартна: вычисляются производящие операторы (генераторы) допредельных и предельных полугрупп сдвига, находится существенное подпространство области определений генератора предельной полугруппы, которым в данном случае является множество функционалов с равномерно ограниченными по норме первыми и вторыми частными производными, и применяется известная теорема [12]. В конце

раздела изучен стационарный режим предельной динамической системы и, несмотря на невозможность его задания в аналитическом виде, доказано его существование и единственность, а также независимость от конкретного вида функции распределения времён движения приборов (весов в смеси гамма-распределений, параметров формы и масштаба) при фиксированном математическом ожидании этих случайных величин. Раздел 2.2 посвящен модели, в которой приборы могут перемещаться между узлами только за время, равное какому-либо натуральному числу. В этом случае функционирование системы описывается цепью Маркова, и её сходимость при количестве узлов N, стремящемся к бесконечности, к динамической системе (теорема 2.2) проверяется сравнительно несложно. Завершается раздел также доказательством существования, единственности и независимости от вида функции распределения времени обслуживания стационарного режима предельной динамической системы.

Заключение

Резюмируя, стоит ещё раз отметить основные результаты работы.

1. Найдены условия, при которых имеет место асимптотическая независимость любого конечного множества узлов и любой конечной группы приборов при стремлении числа узлов к бесконечности (Теорема 2.3).

2. Найдены достаточные условия слабой сходимости случайного процесса, представляющего собой общее число посещений фиксированного узла приборами за определённый промежуток времени, к пуассоновскому процессу с зависящим от времени параметром, когда число узлов стремится к бесконечности (Теоремы 1.1, 2.4).

3. Доказана сходимость случайного процесса, описывающего состояния узлов сети, к динамической системе в смысле слабой сходимости конечномерных распределений процесса (Теоремы 1.2, 2.5).

4. Для сети без мест для приборов в узлах доказана глобальная устойчивость предельной динамической системы, найден явный вид точки-аттрактора (Теорема 1.3).

5. Для этой же модели получены достаточные условия эргодичности случайного процесса, описывающего её состояния, и сходимости эр-годических мер при стремлении числа узлов к бесконечности (Теоремы 1.5, 1.6, 1.7).

Главной целью предпринятого исследования являлась проверка для различных моделей транспортных сетей гипотезы о независимости устойчивого режима предельной (при числе узлов, стремящемся к бесконечности) динамической системы от функции распределения времени движения приборов при фиксированном среднем времени перемещения. По существу, это предположение смыкается с пуассоновской гипотезой Добрушина. Первой работой по данной проблематике была [25], где гипотеза была полностью доказана для случая детерминированного времени обслуживания. Вопросы справедливости пуассоновской гипотезы затрагивались и в работах [11, 14], посвящённых различным системам с экспоненциально распределённым временем обслуживания. Сходимости, подобные доказанным в диссертации, рассматривались для замкнутых сетей Джексона в недавно вышедшей работе Рыбко и Шлосмана [26], являющейся продолжением [14]. Она посвящена уже моделям с произвольно распределённым временем обслуживания, но методы, описанные там, применить к транспортным сетям не удалось. Вообще стоит отметить, что транспортные сети с произвольно распределённым временем движения, несмотря на популярность поллин-говых моделей, в литературе не рассматривались. Тем не менее, на них во многом удалось распространить известные методы анализа коммуникационных сетей и сетей Джексона. Этого нельзя сказать о транспортных сетях с произвольно распределёнными входящими потоками клиентов — в этой части исследование потребовало разработки новых подходов к изучению моделей такого рода. Таким образом, настоящая работа, с одной стороны, продолжает линию исследования пуассоновской гипотезы для сетей с произвольно распределённым временем обслуживания, с другой стороны, расширяет спектр рассматриваемых моделей транспортных сетей, попутно изучая возможность применения известных методов, разработанных для систем массового обслуживания и сетей Джексона.

Автор выражает глубокую признательность своему научному руководителю профессору JI. Г. Афанасьевой за ценные обсуждения и всестороннюю поддержку в течение всего диссертационного исследования.

1. Delcoigne F., Fayolle G. Thermodynamic limit and propagation of chaos in polling systems // Markov Processes Relat. Fields. —1999.— V. 5, № 1.— P. 89-124.

2. Fayolle G., Lasgouttes J. M. A state-dependent polling model with Mar-kovian routing // IMA Volumes in Math, h its Applications. —1995.— V. 71.-P. 283-301.

3. Фосс С. Г., Чернова Н. И. О системах поллинга с бесконечным числом станций // Сибирск. матем. журнал. —1996.— Т. 37, вып. 4.— С. 940— 956.

4. Фосс С. Г., Чернова Н. И. Теоремы сравнения и эргодические свойства систем поллинга // Проблемы передачи информации. —1996.— Т. 32, вып. 4.-С. 46-71.

5. Afanassieva L. G., Fayolle G., Popov S. Yu. Models for transportation networks j I J. Math. Sci. 1997. - V. 84, № 3.-P. 1091-1103.

6. Afanassieva L. G., Delcoigne F., Fayolle G. On polling systems where servers wait for customers // Markov Processes Relat. Fields. —1997. — V. 3, № 4. P. 527-545.

7. Оселедец В. И., Хмелёв Д. В. Стохастические транспортные сети и устойчивость динамических систем // Теория вероятн. и ее примен. — 2001.-Т. 46, вып. 1.-С. 147-154.

8. Fricker С., Jaibi М. R. Stability of a polling model with a Markovian scheme: Rapport de recherche —№ 2278. INRIA, 1994. —16 p.

9. Karpelevich F. I., Pechersky E. A., Suhov Yu. M. Dobrushin's approach to queueing network theory // J. Appl. Math. Stoch. Anal. —1996. — V. 9, № 4. P. 373-397.

10. Введенская Н.Д., Добрушин P. JI., Карпелевич Ф.И. Система обслуживания с выбором наименьшей из двух очередей асимптотический подход // Проблемы передачи информации. —1996.— Т. 32, вып. 1.— С. 20-34.

11. Ethier S. N., Kurtz Т. G. Markov processes: Characterization and convergence. — New York: J. Wiley, 1986. — 544 p.

12. Vvedenskaya N. D., Suhov Yu. M. Dobrushin's mean-field approximation for a queue with dynamic routing // Markov Processes Relat. Fields. — 1997.-V. 3, № 4.-P. 493-526.

13. Карпелевич Ф. ИРыбко A. H. Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе // Проблемы передачи информации. — 2000.— Т. 36, вып. 2. — С. 69-95.

14. Григелионис Б. И. Предельные теоремы для сумм процессов восстановления // В сб.: Кибернетику на службу коммунизму. — M.-JL: Энергия, 1964.-Т. 2.-С. 246-265.

15. Боровков А. А. Эргодичность и устойчивость случайных процессов. — М.: Эдиториал УРСС, 1999.-440 с.

16. Kiefer JWolfowitz J. On the theory of queues with many servers I j Trans. Amer. Math. Soc.- 1955.-V. 78.-P. 1-18.

17. Боровков А. А. Вероятностные процессы в теории массового обслуживания.— М.: Наука, 1972. —368 с.

18. Greenberg A., Malyshev V. A., Popov S. Yu. Stochastic model of massively parallel computation // Markov Processes Relat. Fields. —1995. — V. 1, №4.-P. 473-490.

19. Севастьянов Б. А. Предельный закон Пуассона в схеме сумм зависимых случайных величин // Теория вероятн. и ее примен. — 1972. — Т. 17, вып. 4. С. 733-738.

20. Афанасьева Л. Г., Булинская Е. Б. Случайные процессы в теории массового обслуживания и управления запасами. — М.: Изд-во МГУ, 1980.-110 с.

21. Smith W. L. Regenerative stochastic processes // Proc. Roy. Soc. Ser. A. — 1955.-V. 232.-P. 6-31.

22. Ширяев A.H. Вероятность. В 2-х кн. —3-е изд., перераб. и доп. — М.: МЦНМО, 2004.-Кн. 1.-520 с.

23. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: Физматлит, 2004. — 572 с.

24. Столяр A.JI. Асимптотика стационарного распределения для одной замкнутой системы массового обслуживания // Проблемы передачи информации.-1989.-Т. 25, вып. 4. —С. 80-92.

25. Rybko A. N., Shlosman S. Poisson Hypothesis for information networks (A study in non-linear Markov processes). http://arxiv.org/abs/math-ph/0303010