Предлагаемые в данной работе модели могут быть отнесены к классу поллинговых. Поллииговая модель является системой массового обслуживания, состоящей из некоторого количества станций обслуживания (узлов) и некоторого количества приборов, осуществляющих обслуживание поступающих в узлы требований. Приборы могут передвигаться между узлами, выбирая узел назначения в соответствии с некой стохастической матрицей маршрутизации (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. Г. Афанасьевой за ценные обсуждения и всестороннюю поддержку в течение всего диссертационного исследования.
