Асимптотические результаты для одного класса поллинговых моделей с управлением тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Гинзбург, Екатерина Михайловна

• Гинзбург, Екатерина Михайловна
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Гинзбург, Екатерина Михайловна

Введение

1. Транспортные модели с управлением. Описание и эргодические теоремы

1.1. Постановка задачи и методы исследования

1.2. Теоремы эргодичности для сетей малой размерности.

1.2.1. Системы из двух узлов. Формулировка эргодической теоремы

1.2.2. Вспомогательные марковские цепи.

1.2.3. Доказательство эргодической теоремы для систем из двух узлов

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

1.3. Эргодические теоремы для полусимметричных систем.

1.4. Исследование стационарного режима

1.5. Исследование неэргодического случал.

1.5.1. Свойства векторов усредненных сносов

1.5.2. Построение вспомогательной марковской цепи и ее свойства

1.5.3. Построение пробной функции.

1.5.4. Доказательство теоремы 4.

2. Управляемая симметричная транспортная система с потерями

2.1. Постановка задачи и форму^й^оёкатеоремы о сходимости полугрупп операторов.

2.2. Доказательство корректности краевой задачи.

2.3. Обоснование теоремы о сходимости полугрупп.

2.3.1. Лемма о существенном подпространстве.

2.3.2. Доказательство теоремы о сходимости полугрупп.

2.4. Стационарная точка системы дифференциальных уравнений.

3. Асимптотическая оптимизация

3.1. Свойства стационарных точек динамических систем с разным пороговым уровнем.

3.2. Исследование эффективности управления и оптимизация.

3.3. Поведение сети при быстром движении перевозчиков

3.4. Поведение сети при увеличении числа приборов.

Введение диссертации (часть автореферата) на тему «Асимптотические результаты для одного класса поллинговых моделей с управлением»

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

Из разнообразных сетей обслуживания в отдельную группу выделяют системы поллинга. Эти системы состоят из конечного числа станций, посещаемых одним или несколькими обслуживающими приборами. Прибор после окончания обслуживания на станции г направляется на станцию j в соответствии со стохастической матрицей маршрутизации Р = (Pij)- В литературе рассматривались различные варианты обслуживания требований в узле. Например, прибор может обслуживать по одному требованию в каждой очереди, или все требования, которые поступили в данный узел к моменту его прихода, или часть требований, пока время на их обслуживание не превысит некоторой величины (обслуживание с прерыванием) и т.д. По поллинговым системам имеется обширная литература. В частности, им посвящен специальный выпуск журнала "Queueing Systems" (v. 11, 1992).

К типу шиллинговых можно отнести транспортные модели, в которых обслуживание клиентов состоит в их перевозке из одного узла сети в другой. Системы такого вида впервые были исследованы в работе [15] Афанасьевой, Файолем и др. в 1997 г. Ими была рассмотрена открытая система из N узлов и V приборов, которые передвигаются по узлам сети, развозя требования. Прибытия требований образуют некоторый случайный процесс. Каждое требование с вероятностью pi направляется в узел г, pi > 0, Y^iLiPt — 1- Если в момент поступления требования в узел в нем есть прибор, то он перевозит требование из узла г в узел назначения j, в течение случайного времени rt-j. Узел назначения j выбирается с вероятностью p,j, числа Pij образуют стохастическую матрицу Р. После прибытия в узел назначения требование сразу же покидает систему, а поведение прибора определяется тем, есть ли ожидающие требования в этом узле. Если таких требований нет, то прибор остается там. Если же ожидающие требования есть, прибор забирает одно из них и везет его в узел к, который выбирается с вероятностью pjk- Прибор развозит требования до тех пор, пока не остановится в узле без клиентов. Такую систему мы будем называть Б-системой. б-системы отличаются от стандартных систем поллинга тем, что приборы передвигаются по узлам сети только вместе с требованиями.

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

Обозначим через X — однородную цепь Маркова со значениями в фазовом пространстве X, и будем использовать ее представление в виде

Хп+1 = Хп + в(Хп,п), где распределение 9(х,п) = 9(х), х 6 X, зависит только от х.

Первые сравнительно общие условия эргодичности для многомерных марковских цепей были получены, по-видимому, в [6]-[9], где рассматривается решетчатое блуждание в положительном октанте с ограниченными скачками |0(х)| < с, распределение которых в точке х не зависит от х при х,- > с (свойство частичной однородности в пространстве). Примерно через 10 лет после работ [6]-[9] появились работы [2], [10], [22], [29], [30], [31], посвященные изучению решетчатых цепей Маркова в положительном квадранте X = {(ж^хг) : х\ > 0, х\ > 0}, для которых Е{ 9(х) } не зависит от Х{ при ж,- > с, а также выполнены некоторые другие условия. Примерно в то же время были анонсированы результаты [16], [17], касающиеся эргодичности так называемых асимптотически однородных в пространстве (зависимость распределения 9{х) от Х{ исчезает при —» оо) цепей Маркова в К^ = 2,3) и включающие в себя оценки скорости сходимости и оценки вероятности больших уклонений.

Переход к анализу марковских цепей большей размерности выявил появление принципиально новых возможностей (по сравнению с цепями в 11, Ы2), которые приводят к эргодичности. Само их описание представляет трудности (см. [27]).

В монографии А. А. Боровкова [1] приведены результаты, посвященные эргодичности и устойчивости широкого класса случайных процессов, в том числе многомерных марковских процессов как с дискретным, так и с непрерывным временем. Однако теоремы, касающиеся необходимых и достаточных условий эргодичности для многомерных марковских процессов, содержат громоздкие, трудно проверяемые условия. Видимо, для приложений наиболее плодотворным является путь непосредственного использования методов, примененных при доказательстве таких теорем, поскольку часто технически проще доказать эргодические теоремы для конкретного процесса, нежели проверять условия общих теорем. В разделе, посвященном приложениям, именно так доказаны необходимые и достаточные условия эргодичности систем поллинга. "Прямой подход" к отысканию таких условий был предложен еще в [18].

Другое направление при изучении сетей обслуживания состоит в исследовании количественных характеристик процесса, описывающего поведение сети, при увеличение размеров сети. Из разнообразной литературы, посвященной поллинговым системам (см., например, [32]), известно, что получить точные результаты такого рода при конечном числе узлов в сети N практически невозможно даже при простейших предположениях. Однако во многих приложениях (телекоммуникационные, транспортные системы) основной проблемой является изучение именно больших сетей, N —» оо.

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

Техника, позволяющая получать результаты такого рода, опирается на использование полугрупп линейных операторов, связанных с рассматриваемыми случайными процессами. Особый подход к изучению общих однородных по времени марковских процессов с применением теории полугрупп линейных преобразований в банаховом пространстве принадлежит В. Феллеру ([24], [25]). Этот подход был в дальнейшем использован Е. Б. Дынкиным и его учениками, которым удалось получить стройное описание довольно широкого класса процессов. Полученные результаты были впоследствии объединены в монографии [5]. В настоящее время этот метод является классическим при изучении однородных марковских процессов (см., напр. [4], [21]), на его основе разработана техника для доказательства теорем сходимости.

Для В-системы были доказаны и эргодические теоремы, и теоремы, устанавливающие поведение системы при увеличении размеров сети. Так, в работе [15] было доказано, что процесс 2, описывающий поведение Б-системы, ни при каких соотношениях параметров не является эргодическим. В статье [14] получены аппроксимации для полностью симметричных систем с потерями при увеличении количества узлов и числа приборов в сети.

Данная работа посвящена изучению модификаций В-системы. Для обеспечения более равномерного распределения приборов по узлам сети в систему введены приборы второго типа, которые развозят свободные приборы первого типа. Приборы второго типа будем называть перевозчиками. Перевозчики все время движутся от одного узла к другому. Каждый из них не может транспортировать более одного прибора. Пустой перевозчик забирает прибор из очереди г, если в ней есть хотя бы I приборов, и доставляет его в узел j, который он выбирает с вероятностью Числа qц образуют стохастическую матрицу ф. Если в момент приезда перевозчика с прибором в узел j количество приборов в этом узле меньше, чем / — 1, перевозчик оставляет прибор. Если же в узле ] есть 1 — 1 прибор, то перевозчик продолжает свое движение вместе с прибором, пока не найдет узел, где сможет его оставить. Значение I мы будем называть пороговым уровнем. Таким образом, введение перевозчиков по существу эквивалентно введению управления системой.

Диссертационная работа посвящена исследованию свойств процессов, возникающих при описании подобных систем.

Исследована система с произвольным числом узлов и приборов, в которой перевозчики и приборы передвигаются мгновенно, в каждом узле не может находится более одного прибора, а матрицы Р и ф симметричны. Для нее установлены условия эргодичности и найдено стационарное распределение. Получены необходимые и достаточные условия эргодичности для систем малой размерности (А^ = 2,3) при произвольных матрицах Р, и при выполнении некоторых дополнительных условий. Эргодические теоремы доказаны с помощью построения пробных функций.

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

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

Основные результаты, полученные в диссертации, докладывались на семинарах кафедры теории вероятностей механико-математического факультета МГУ и Кол-могоровских чтениях (2000 г.). Эти результаты опубликованы в работах автора

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

Заключение диссертации по теме «Теория вероятностей и математическая статистика», Гинзбург, Екатерина Михайловна

Заключение

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Гинзбург, Екатерина Михайловна, 2001 год

1. Боровков А. А. (1999) Эргодичность и устойчивость случайных процессов. М.: Эдиториал УРСС.

2. Ваницкий К.Л., Лазарева Б.В. Об условиях эргодичности и невозвратности однородной цепи Маркова в положительном квадранте. Проблемы передачи информации, 1988, Т. 24, В. 1, с. 105-110

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

4. Гихман И.И., Скороход А.В. Теория случайных процессов Т.2. М.: Наука, 1973.

5. Дынкин Е.Б. Марковские процессы М., Физматгиз, 1963.

6. Малышев В.А. Классификация двумерных положительных случайных блужданий и почти линейные семимартингалы. Докл. АН СССР, 1972, Т. 202, N 3, с. 526-528.

7. Малышев В.А. Уравнение Винера-Хопфа и их применение в теории вероятностей. Итоги науки и техники. Сер. Теор. вероятн. Матем. стат. Теор. кибернетика, 1976, Т. 13, с. 5-35.

8. Малышев В.А., Меньшиков М.В. Эргодичность, непрерывность и аналитичность счетных цепей Маркова Труды Моск. матем. общества, 1979, Т.39, с. 3-48.

9. Меньшиков М.В. Эргодичность и условия возвратности для случайных блужданий в положительном октанте Докл. АН СССР, 1974, Т. 217, N 4, с. 755-759.

10. Михайлов В.А. Геометрический анализ устойчивости цепей Маркова в R2 и его приложения. Проблемы передачи информации, 1988, Т. 24, В. 1, с. 61-73

11. Понтрягин Л.С. (1982) Обыкновенные дифференциальные уравнения. М.: Наука.

12. В. Феллер (1967) Введение в теорию вероятностей и ее приложения. T.l. М.: Мир.

13. А.А.Ширяев (1989) Вероятность. М.: Наука.

14. Afanassieva L.G., Fayolle G., Popov S.Yu. Models for transportation networks. Journal of Mathematical Science, 1997, v. 4, N 3, p. 1092-1103.

15. Afanassieva L.G., Delcoigne F., Fayolle G. On polling systems where servers wait for customers. INRIA. Paris. Rapport de recherche N 3058. December 1996.

16. Borovkov A.A. Ergodicity and stability problems for Markov chains. Connections with heat equations. Proc. of Symposium on Frontiers of Math. New York, 1988.

17. Borovkov A. A. Ergodicity and stability of Markov chains and of their generalizations.

18. Multidimensional chains. Probab. theory and math, statistics: Proc. 5-th Vilnius conf., 1989. Vilnius, 1990. V.l, p 179-188.

19. Borovkov A.A., Schassberger R.A. Ergodicity of polling network. Stoch. Processes Appl, 1994, V. 50, p. 253-262.

20. Convay A. E, Geordans N. D. Queueng networks — exact computational algorifms: a unified theory based on decomposition and aggregation. MIT Press, 1989.

21. Delongne F., Fayolle G. Thermodynamical limit and propogation of chaos in polling system. Markov Processes and Relative Fields, 1999, v.5, N.l, p. 89-124.

22. Ethier S. N., Kurtz T. G. Markov procceses characterization and convergence. N.Y.: John Willey and Sons, 1986.

23. Fayolle G. On random walks arising in queueing systems: ergodicity and transience via quadric forms as Lyapunov functions. I Queueing Systems, 1989, V. 5, p. 167-184.

24. G. Fayolle, V.A. Malyshev and M.V. Menshikov (1995) Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press.

25. Feller W. The parabolic differential equations and the associated semigroups of transformations. Ann. Math., 1952, V. 55, p. 468-519.

26. Feller W. Diffusion processes in one dimension. Trans. Amer. Math. Soc., 1954, V. 77, p. 1-31.

27. Foster F. G. On the stochastic matrices associated with queueing process. Ann. Math. Statist., 1953, v.24, N.3, p. 355-360.

28. Ignatyuk I. A., Malyshev V.A. Classification of random walks in Z+. INRIA, preprint, 1991.

29. F. P. Kelly Reversibility and stochastic networks. New York: Wiley, 1979.

30. Kesten H. Recurrence criteria for multi-dimensional Markov chains and multidimensional linear birth and death processes. Adv. Appl. Probab., 1976, V.8, N1, p. 58-87.

31. Rozberg Z. A positive reccurence criterion assotiated with multidimensional queueing processes. J. Appl. Probab., 1980, V.17, N3, p. 790-801.

32. Rozenkrants W.A. Ergodicity conditions for two-dimensional Markov chains, on the positive quadrant. Probab. Theory Rel. Fields, 1989, V.83, N3, p. 309-320.

33. Takagi H. Queueing analysis of polling models. ACM Comput. Surveys, 1988, V 20, p. 5-28.

34. N. D. Vvedenskaya, Yu. M. Suhov. Dobrushin's Mean-Field Approximation for a Queue with Dynamic Routing. Markov Processes and Relative Fields, 1997, v.3, N.4, p. 493-526.

35. Гинзбург E.M. Быстрое движение приборов в поллинговой системе с управлением. Выбор оптимального значения. Научные труды ИвГУ. Математика. Вып.2. Иваново, 1999, с. 40-45.

36. Гинзбург Е.М. Эргодичность некоторых управляемых поллинговых систем малой размерности. Математическое моделирование в естественных и гуманитарных науках. Труды школы-симпозиума. Воронеж, 20-27 января 2000 г., с. 54-59

37. Afanassieva L.G., Ginzburg Е.М. Ergodicity condition for a specified polling system. XXI International Seminar on Stability Problems for Stochastic Models. Volume of abstracts. 2001. p.26.

38. Л.Г. Афанасьева, Е.М. Гинзбург. Эргодичность систем со взаимодействующими частицами. Фундаментальная и прикладная математика, 2000, том 6, N4, с. 985-993.