Асимптотические результаты для одного класса поллинговых моделей с управлением

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

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