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

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

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

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

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

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

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

Особый интерес у специалистов в области теории МО в последнее десятилетие (см., например, [6], [21], [11], [37], [39], [40], [57]) вызывает исследование систем МО с входным потоком типа В MAP (Batch Markovian Arrival.

Process) и его различными обобщениями, учитывающими пространственный фактор (Spatial ВМАР), различные классы заявок и число заявок в системе разных классов (уровень). Это связано с тем, что с введением Д. Лукантони (см. [32]) этого понятия решилась проблема учета зависимости между интервалами поступления заявок, наблюдаемой в коммуникационных системах.

Входной поток, описываемый ВМАР, модулируется марковским процессом с дискретным множеством состояний, называемым фазовым. В г-ой фазе в систему поступает пуассоновский групповой поток интенсивности Аг-. Анализ таких систем МО даже с одним обслуживающим прибором требует манипуляций с матрицами больших размерностей. Например, для вычисления стационарного распределения числа заявок (см. [22]) в BMAP/G/1 системе с уровнезависимым входным потоком получено матрично-интеграль-ное соотношение. Рассчитывать распределение, используя это соотношение, можно, предварительно найдя преобразования Лапласа-Стильтьеса для определенных матриц и на их основе решив системы алгебраических уравнений. Не менее сложный алгоритм предложен для рассматриваемой системы, но с конечным буфером в работе [7], который заключается в решении матрично-дифференциального уравнения методом последовательных итераций.

Предположение зависимости между процессами прихода и обслуживания заявок в системах с ВМАР потоками вызывают еще большую сложность (см., например, [2], [44], [50], [56]). Самый последний результат в этом направлении содержится в работе Ф. Мачихары (см. [33]). Для одноканаль-ной системы с полумарковским обслуживанием автору удалось получить матрично-интегральное соотношение для производящей функции стационарного распределения числа заявок в системе.

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

Предположение ординарности входного потока в системах МО, функционирующих в марковской случайной среде, еще не является выходом из создавшейся ситуации (см., например, [64], [66], [71]). Для нахождения распределений процессов, описывающих функционирование исследуемых систем, составляются линейно-разностные уравнения в стационарном случае и дифференциально-разностные уравнения в нестационарном случае, при решении которых используется классический метод производящих функций. Сложность используемого метода объясняется хотя бы тем, что разложение в ряд Тейлора производящих функций стационарных распределений и преобразований Лапласа-Стильтьеса производящих функций нестационарных распределений требует использования аппарата теории функций комплексного переменного.

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

В диссертационной работе получены точные аналитические формулы для вычисления стационарных распределений не только систем МО, но и сетей МО с пуассоновским входным потоком интенсивности А (£), где A (t) марковский процесс. Это удалось сделать для моделей МО (систем и сетей), функционирование которых описывается марковским процессом в предположении, что параметры этого процесса линейно зависят от состояний внешней среды, модулируемой процессом Л (t).

Введение

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

Вообще, интерес к мультипликативной форме стационарного распределения начинается с работ Джексона (см. [17]), который показал, что в стационарном режиме распределения узлов независимы, и их произведение есть стационарное распределение всей сети. Заметный вклад в развитие этой тематики сделали Гордон и Ньюэл (см. [18]), Уиттл (см. [55]), Баскет и др. (см. [5]), Мунтц (см. [34]), Ноетзел (см. [35]), Лэм (см. [30]), Келли (см. [27], [28]) и другие. В основном эти работы сфокусированы на поиске необходимых и достаточных условий существования мультипликативной формы стационарного распределения сетей МО. Подобные условия устанавливаются обычно из уравнения глобального баланса и представляют собой множество уравнений локального баланса.

Поиск условий существования мультипликативной формы стационарного распределения и в последнее десятилетие сводится в основном к оперированию с уравнениями локального баланса (см., например, [10], [16], [19], [20], [31], [45], [46]). Это приводит к распространению известных результатов на сети более общего вида. Обобщаются дисциплины обслуживания, зависимости интенсивностей входного потока от состояния сети и т. д. Но работы по изучению сетей МО, функционирующих в случайной среде редки. Один результат содержится в [58]. Ю. Жу в своей работе установил мультипликативную форму стационарного распределения сети Джексона в случайной среде в предположении временной обратимости марковского процесса, описывающего ее функционирование.

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

Вообще, построением марковских процессов определенного вида с целью получения мультипликативной формы стационарного распределения занимались Серфозо [47], Рамазвами [40], Келли [27]. В работе [47] построен пространственный процесс гибели и рождения, в [40] уровне-фазовый процесс гибели и рождения, в [27] марковский процесс, покомпонентные переходные интенсивности которого отличны от нуля.

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

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

В теории страхования огромное число работ посвящено изучению вероятности разорения в классических моделях страхования. Получить точные аналитические формулы для вероятности разорения удалось только в модели Андерсена. Поэтому многие авторы строили двусторонние оценки для вероятности разорения, всевозможные аппроксимации, применяли численные методы. Все перечисленные результаты можно найти в известных монографиях [3], [13], [24], [26] и в работе [25].

Работы по изучению неклассических систем страхования, а именно, систем взаимного страхования, редки. Например, проблемой построения оптимальной премиальной стратегии для группы страховых компаний, принадлежащих холдинговой компании и обменивающихся определенным процентом резерва, занимался в [59] А. Зимбидис. Изучением эффекта корре-леции ущербов отдельных компаний на общий групповой размер претензий занимался Н. Колев в [29]. Поведением предельной вероятости разорения Ф интересовался автор работ [76], [77].

В работах [76], [77] построена модель страхования, основанная на эффекте объединения п однотипных компаний, характеризующаяся нулевой величиной начального капитала, малым страховым процентом b = п-7, у > О (разность между премиальной ставкой и средней величиной ущерба, др. словами «плата за риск») и найдено 7* > 0 такое, что.

Ф = / 7 < (0.0.1) 1, 7 >7*.

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

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

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

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

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

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

Вообще, задача вычисления вероятности невыхода марковской цепи из некоторого множества возникает во многих приложениях: в финансовой математике [15], [36], [43], в технической теории надежности [60], в теории эпидемий [14], [54] и т. д, но, несмотря на это, алгоритм ее вычисления, как указал А. А. Новиков, в общем случае не строился.

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

Во второй главе исследуется поведение предельной вероятности разорения в модели страхования, взятой из [76], [77], со слабо зависимыми ущербами. В этой модели обнаружено явление контрастного перехода в дву-параметрической плоскости благодаря специальным образом подобраной зависимости между ущербами объединенных компаний.

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

В «Приложении» содержатся тексты программ, используемые в вычислительных экспериментах. Список опубликованных и принятых к печати работ по теме диссертации приведен в конце [80]-[101].

Заключение

.

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

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

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

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

Таким образом, основными результатами работы являются:

1. Доказательство теоремы мультипликативности, позволяющей строить взаимодействующие сетевые модели МО и модели МО в случайной среде (в том числе модель мобильной телефонной сети), стационарные распределения которых имеют мультипликативный вид. Эта теорема обобщает известные результаты Ф. Келли и Ю. Жу.

2. Доказательство принципа управления параметрами марковских сетевых моделей МО с целью представления их стационарных распределений в условно-мультипликативном виде.

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

4. Построение алгоритма вычислений стационарных распределений марковских моделей МО на основе метода вложенных цепей Маркова и метода пошаговой аппроксимации.

5. Построение алгоритма вычисления вероятности невыхода марковской цепи из некоторого множества и его тестирование на математической модели эпидемий.