Введение к работе
Актуальность темы.
Многие реально существующие объекты (компьютерные, коммуникационные, транспортные сети и т.п.) математически могут быть описаны как сети массового обслуживания. Из разнообразных сетей обслуживания в отдельную группу выделяют системы поллинга, которые состоят из конечного числа станций (узлов), посещаемых одним или несколькими обслуживающими приборами. В на-
, стоящее время теория поллинговых систем активно развивается, о чём сви-
детельствует обширная отечественная и зарубежная литература. Среди прочих можно выделить работы Боровкова - Шассбергера1, Делкуаня, Файоля2,8,
' Фосса4.
К типу поллинговых можно отнести системы, в которых обслуживание состоит в перемещении требований от одной станции к другой. Такие модели естественно возникают при описании транспортных сетей.
, Одна из первых задач при анализе поллинговых моделей — определение усло-
вий существования стационарного распределения. Другая задача состоит в отыскании этого стационарного распределения или построении приемлемых оценок
» для него. Здесь возникают существенные трудности, поскольку даже в простей-
ших предпосылках (все характеристики имеют показательное распределение) случайный процесс, описывающий функционирование системы, оказывается достаточно сложным. В связи с этим внимание исследователей сосредоточено на получении предельных теорем типа закона больших чисел для симметричных сетей, когда число узлов и число приборов велико5,8. Если входящий поток тре-
'Borovkov А.А., Schassberger R.A. Ergodicity of » polling network // Stoch. Processes Appl. —1004. — V. 50. — P. 263-282.
'Delcoigne F., Fayolle G. Thermodynamic limit and propagation of chaos in polling systems // Markov Proceaaea Relet. Field.. -1900. - V. 5, № 1. - P. 89-124.
'Fayolle G., Laegotittes J.M. A state-dependent polling model with Markovian routing // IMA Volume» in Math. к it» Application». -1006. - V. 71. - P. 288-301.
4Фосс С.Г., Чернова Н.И. Теоремы сравнения эргоджческке свойства систем поллинга // Проблемы передачи информации. —1996. — Т. 32, вып. 4. — С. 46-71.
'Afanassieva L.G., Fayolle G , Popov S.Yu. Models for transportation networks // J. Math. Sci. —1997. - V. 84, *S.-P. 1001-1103.
'Введенская Н.Д., Добрушнн РЛ., Карпелешгч ФИ. Система обслуживания с выбором наименьшей из двух очередей - асимптотический подход // Проблемы передача информации. —1096. — Т. 82, вып. 1. — С. 20-
**' РОС НАЦИОНАЛЬНАЯ I
БИБЛИОТЕКА {
1 СПетер6ург*2 И (V,
09 Wfc*M$V/;
бований пуассоновский, а времена движения приборов имеют показательное распределение, то состояние системы описывается марковским процессом со счётным фазовым пространством и сходимость к некоторой динамической системе вытекает из известной теоремы об эквивалентности сходимости полугрупп сдвига, порождённых марковским процессом, на конечном временном отрезке и их производящих операторов на существенном подпространстве области определения7. Подобный подход был использован рядом авторов при анализе коммуникационных сетей8. Сети с произвольно распределённым временем обслуживания также рассматривались в литературе9,10 с помощью введения марковского процесса с достаточно сложным фазовым пространством и существенного использования специфики сети.
При изучении подобных моделей часто используется тот факт, что при наличии достаточно сильной симметрии у системы, когда число компонент увеличивается, зависимость их друг от друга ослабевает и, в конце концов, все компоненты начинают эволюционировать независимо друг от друга. Эта эволюция описывается системой дифференциальных уравнений, предельная точка которой представляет собой устойчивое состояние каждой из компонент.
Согласно обзору в статье Карпелевича и др.11, этот метод в «интуитивной» форме известен математикам и инженерам довольно давно — с 60-х годов XX века, однако, вопрос о строгом обосновании всех описанных шагов сталкивается с большими трудностями. Авторы обзора называют гипотезой Р. Л. Добрушина утверждение о том, что указанный метод действительно можно строго обосновать математически в большинстве систем. Одной из первых работ, посвященных исследованию справедливости гипотезы Добрушина, является статья Столяра12, где изучена замкнутая сеть с детерминированным временем обслу-
TEtbier S.N., Kurti T.G. Markov ргосеак»: Characterisation and convergence. — New York: J. Wiley, 1986. — 544 p.
*Сн., например, упомянутую работу Введенской в др.
*Vveden*kaya N.D., Suhov Yu.M. Dobnuhin'* mean-field approximation for a queue with dynamic routing // Markov Рюсеиеа Relat. Fields. - 1997. - V. 3, J* 4. - P. 493-52«.
'"Карпелевич Ф.И., Рыбко A.H. Асимптотическое поведение симметричное замкнутой сети массового обслуживания в термодинамическом пределе // Проблемы передата информации. — 2000. — T 36, вып. 2. — С. 69-95.
"Karpelevich F.I., Pechersky Е A., Suhov Yu.M. Dobruahm'e approach to queueing network theory // J. Appl. Math. Stoeh. Anal. -1996. - V. 9, * 4. - P. 373-397.
"Столяр А.Л. Асимптотика стационарного распределения для одной замкнуто* системы массового обслуживания // Проблемы передача информации. —1989. — Т. 25, вып. 4. - С. 80-92.
живания. Эта тема затрагивалась и в упомянутых выше работах Карпелеви-ча - Рыбко и Введенской и др., а также в недавно вышедшей статье Рыбко и Шлосмана13.
Вследствие популярности и активного развития теории сетей массового обслуживания вообще и изучения поллинговых моделей в частности, а также внимания исследователей к вопросам справедливости гипотезы Добрушинадля различных классов систем проблематика диссертации и подходы, предложенные в ней, представляются весьма актуальными.
Цель работы.
Основная цель работы состоит в проверке гипотезы об инвариантности устойчивой точки предельной динамической системы относительно вида функции распределения времени движения приборов при фиксированном математическом ожидании, что потребовало также решения ряда вопросов, связанных с эргодичностью допредельных моделей и условиями сходимости к динамической системе при неограниченном росте числа узлов.
Научная новизна.
Все полученные результаты являются новыми. Стоит отметить, что транспортные сети с произвольно распределённым временем движения, несмотря на популярность поллинговых моделей, прежде в научных работах не рассматривались. Предпринятые исследования потребовали разработки новых подходов, поскольку даже для сетей с пуассоновскими входящими потоками требований, время движения приборов в которых распределено не экспоненциально, не удалось применить известные методы анализа систем массового обслуживания и сетей Джексона. Основные результаты работы состоят в следующем.
1. Найдены условия, при которых имеет место асимптотическая независимость любого конечного множества узлов и любой конечной группы приборов при стремлении числа узлов к бесконечности.
**Rybko A.N., Sbloaman S. Poieaon Hypotheaia for information networks (A study in non-linear Markov proceaaes).
-
Найдены достаточные условия слабой сходимости случайного процесса, представляющего собой общее число посещений фиксированного узла приборами за определённый промежуток времени, к пуассоновскому процессу с зависящим от времени параметром, когда число узлов стремится к бесконечности.
-
Доказана сходимость случайного процесса, описывающего состояния узлов сети, к динамической системе (в смысле слабой сходимости конечномерных распределений процесса).
-
Для сети без мест для приборов в узлах доказана глобальная устойчивость предельной динамической системы, найден явный вид точки-аттрактора.
-
Для этой же модели получены достаточные условия эргодичности случайного процесса, описывающего её состояния, и сходимости эргодических мер при стремлении числа узлов к бесконечности.
-
Для системы с местами для ожидания приборов и распределением времени обслуживания специального вида (смесь распределений Эрланга) доказана сходимость к предельной динамической системе, найден вид стационарного решения; доказана его инвариантность относительно параметров распределения при фиксированном математическом ожидании.
Методы исследования.
В диссертации используются классические и современные методы теории массового обслуживания и теории случайных процессов (мажорирование, теорема Смита, метод Кифера - Вольфовица, метод расщепления и теорема Боровко-ва об эргодичности асимптотически стохастически непрерывного марковского процесса). Подход к доказательству глобальной устойчивости и сходимости эргодических мер во многом аналогичен использованному Введенской, Добруши-ным и Карпелевичем для анализа открытых многоканальных систем массового обслуживания. Изучение получающихся в пределе динамических систем потребовало использования ряда утверждений, относящихся к теории обыкновенных дифференциальных уравнений и уравнений с частными производными.
Теоретическая и практическая ценность.
Диссертация носит теоретический характер. Её методы и результаты могут найти применение в дальнейшем исследовании поллинговых моделей.
Апробация работы.
Результаты диссертации докладывались и обсуждались на семинаре «Случайные процессы в теории массового обслуживания», на Большом семинаре кафедры теории вероятностей Механико-математического факультета МГУ (2004-2005 гг.), а также на Всероссийской школе-коллоквиуме по стохастическим методам (Сочи-Дагомыс, 1-7 октября 2005 г.) и на Воронежской зимней математической школе С. Г. Крейна (Воронеж, 27-30 января 2006 г.). Тематика работы была поддержана грантом РФФИ 05-01-00256.
Публикации.
Результаты диссертации опубликованы в 6 работах, список которых приведён в конце автореферата.
Структура диссертации.
Диссертация состоит из введения, двух глав (разбитых на разделы), заключения и списка литературы, насчитывающего 26 наименований. Общий объём диссертации — 88 страниц.
