Системы массового обслуживания с изменяемым режимом работы и их оптимизация тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

ЧС С* 9 2

г БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

КЛИМЕНОК ВАЛЕНТИНА ИВАНОВНА

СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ИЗМЕНЯЕМЫМ РЕЖИМОМ РАБОТЫ И ИХ ОПТИМИЗАЦИЯ

Специальность 01.01.05 - теория вероятностей и математическая статистика

Автореферат диссертации на соискаяие

ученой степени кандидата Физико-математических наук

ншгк

Работа выполнена в Белорусском государственном университете.

Научный руководитель - кандидат физико-математических наук, ,

старший научный сотрудник Дудин А.Н.

Официальные оппоненты: доктор физико-математических наук,

профессор Харин Ю.С. кандидат физико-математических наук, доцент Малинковский Ю.В.

Ведущая организация - Московский институт электронного машиностроения

Защита состоится 13 мая 1992 года в 10 часов на заседании специализированного совета К 056.03.17 при Белгосуниверситете (220080, г. Минск, проспект Скорины 4, Университетский городок).

С диссертацией можно ознакомиться в библиотеке Белгч ^университета

Автореферат разослан апреля 199? г

Ученый секретарь специализированное совета

доцент ' — Ш.В. Мз.^ннц

''кты

/ ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

"■'j j J

,/г'гд'циГ|ттуальность темы диссертации. Математические модели систем "ТНЬбшого обслуживания (СМО) достаточно адекватно описывают ситуации, возникающие при обслуживании очередей в бытовом обслуживании, в промышленности, сетях связи и т.д. Классические модели СМО, к настоящему времени довольно хорошо изученные, не учитывают возможности изменения параметров систем во времени, что существенно ограничивает их применение.

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

СМО с изменяемым режимом функционирования рассматривались в работах /.Н.Дудина, В.А.Каштанова, И.А.Коротаева, А.Д.Соловьева, Ю.И.Рыжикова, Г.И.Фалина, У.Ечиади, Т.Крейбелла, П.Наора. М.Сотело, А.Фукуда и др. Обзоры работ по управляемым системам массового обслуживания опубликованы В.В.Рыковым; М. и Е.Файнбер-гами; Т.Крейбеллом, Д.Гроссом, М.Мэгэзином; С.Сгидхемом; Дж.Тегхемом. Библиографию работ, посвященных исследованию СМО, функционирующих в случайной среде можно найти в *), **).

Появление качественно новых систем управления и связи,

*) Скляревич ЙП1Т] Скляревич ф. К. Вероятностные модели объектов с возможными изменениями. - рига ; 3"натне. - 1989. -'

36В с.

Sotelo М, Mukumoto К., Fukuda Л. On nmltiserver queue with M-phase synchronous fluctuation of traffic intensity // Transactions of the IEICK CjapanX - 1<Д17. -. E-70 - If' 12. - p. 11H7-1191.

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

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

Сформулированная цель предопределяет следующие задачи исследований:

- исследование случайных процессов в ' СМО типа 61/М/1 с управляемым режимом функционирования, получение' аналитических зависимостей для стационарных распределений состояний системы, решение задачи оптимального управления в заданных параметрических классах однородных марковских стратегий;

- изучение математических моделей УСМО типа М/М/1, М/в/1 с повторными требованиями с изменяемым режимом функционирования. Исследование задачи оптимального управления СМО в заданных' классах однородных марковских стратегий;

— исследование процесса функционирования СМО типа М/в/1 и МАЗЛ/И в синхронной случайной среде, определение маргинальных и совместных распределений среды и системы, других основных вероятностно-временных характеристик СМО.

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

Научная новизна. Впервые:

- исследованы математические модели УСМО типа в1/М/1 с управляемым режимом функционирования и многопороговыми, гистерезисными. многопороговыми с отключением входного потока стратегиями управления, решена задача синтеза оптимальных стратегии в указанных классах;

- проведено исследование УСМО типа МЛЗ/1 и М/М/1 с повторными . требованиями и . управляемым режимом работы, рассмотрены многопороговые, 'рандомизированные - для системы типа МЛ5/1. многопороговые, гистерезисные - для СМО типа М/М/1 стратегии управления режимом их функционирования, исследованы задачи оптимального управления в указанных классах стратегий;

- изучены процессы функционирования СМО типа МЛЗ/1 ' в синхронной случайной среде ралдомиэированно-циклического типа и СМО типа М/в/1/И в синхронной случайной среде специального вида, получены аналитические зависимости для основных вероятностно-временных характеристик случайной среды и системы.

. Практическая значимость работы и внедрение результатов исследований.

1. Решение задачу оптимального управления режимом работы СМО типа в1/М/1 позволит существенно продвинуться в исследовании проблемы динамического управления потоками и ограничения нагрузки в информационно-вычислительных сетях и сетях связи.

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

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

4. Полученные аналитические зависимости для вероятностно-временных характеристик системы типа М/в/1/И, функционирующей в синхронной случайной среде специального вида, с большой степенью точности описывают процесс приема информации в транспортной станции локальной вычислительной сети "Квант-С", указанные результаты использовались при оценке производительности, максимальной пропускной способности и настройке протокольных параметров указанной сети.

Результаты работы использовались при выполнении ряда хоздоговорных ИР, в том числе с номерами гос.регистрации 01870015088. 01900009052. 01900013855. Результаты нашли применение в разработках предприятий п/я А-П29, п/я М-5308

(г.Санкт-Петербург), ОКБ "Квант" НПО "Гранат" (г.Минск).

Апробация результатов работы. Результаты диссертации представлялись и докладывались на V Всесоюзной школе-семинаре"по" распределенным автоматизированным системам массового обслуживания (Рига, 1988), III Всесоюзном совещании по распределенным автоматизированным системам массового обслуживания СВинница, 1990), XVI Всесоюзной школе-семинаре по вычислительным сетям (Винница, 1991), Всесоюзной научно-технической конференции "Распределенные микропроцессорные и локальные вычислительные сети" (Томск, 1991), V - VII' Белорусских' зимних школах по теории массового обслуживания (Гродно, 1989, 1991, Витебск, 1990), республиканском научно-техническом семинаре "Совершенствование методов исследования потоков событий и систем»массового обслуживания " (Киев, 1989), IV Всесоюзном совещании по распределенным вычислительным системам массового обслуживания (Душанбе, 1991).

Публикации. По теме диссертации опубликованы 15 работ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения .и списка литературы в 89 наименований. Содержит 12 рисунков, три таблицы. Общий объем работы 166 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении приведено краткое обоснование актуальности решаемых в диссертации задач. Дан краткий обзор литературы по тематике диссертации. Коротко изложено содержание работы.

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

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

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

. Имеется однолинейная СМО с неограниченным числом мест для ожидания. Система может работать в г>2 режимах. При работе системы в р-ом режиме интервалы между поступлениями соседних требований во входном потоке распределены по закону (Ар(0 (преобразование Лапласа-Стилтьеса а^Сэ), первый момент л^1, / л^>0). времена обслуживания требований распределены по зкспоненциально.му закону с параметром ^ > 0. Система, рассматриваемая в § 3, может работать еще в одном, (п+1)-м режиме, описание которого будет дано несколько ниже.

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

Кригерием качества управления СМО с N режимами функционирования является средний штраф в единицу времени при работе системы в стационарном режиме:

n

I = а1_т-' + 2 р^ + аМ, (I)

V- 1

где 1_ - среднее число требований в системе в момент поступления требования, т - средняя величина интервала времени . между поступлениями требований во. входном потоке, а - штраф за пребывание одного требования в системе в момент поступления требования, а > 0;-Рр - средняя доля времени, в течение которого система работает в и-ом режиме, - стоимость единицы времени использования и-го режима, и = I , М - среднее число переключений режимов в единицу времени, а - штраф за одно такое

переключение, d > 0.

Основное различие моделей УСМО, рассматриваемых в первой главе, касается классов используемых в них стратегий управления. Рассматриваются классы многопороговых, гистерезисных и многопороговых с отключением входного потока стратегий. Задача выбора оптимальной стратегии во всех трех моделях решается при помоши простых численных процедур на ПЭВМ типа IBM PC после получения явной зависимости критерия качества (I) от параметров, определявших стратегии соответствующего класса.

В § I рассматривается модель УСМО с п режимами' функционирования и многопороговыми стратегиями управления переключением режимов. Штраф за переключение режимов отсутствует, т.е. d = 0. Стратегии управления задаются

параметрами - натуральными числами j .j.....Jn-i' называемыми

порогами и удовлетворяющими условиям -I=j <j ..<J <j =®

О 1 2 n-1 П

При такой стратегии управление осуществляется следующим образом если число требований в системе в момент поступления требования принадлежит интервалу . то до следующего момента

система будет работать в v -ом режиме, р=Г7п .

Под состоянием системы в моменты поступления требований понимается число i требований в системе непосредственно перед этими моментами, i>0. Состояния системы в моменты поступления требований образуют цепь Маркова с переходными вероятностями.

m - о

1 ~ 2 ^С' • еСЛИ l~°> JP-, < 1 *

^-Wi' ейли 0 < 1 * 1+I' < 1 < -¡и- (2)

О, если 1 > i+I. j < i < v = Ti

п

где..

•в' ' = | —^П- е V аА, Ль). т> 0, и =Т~п .

т •> т! и

о

Доказано, что достаточным условием существования стационарного распределения цепи с переходными вероятностями (2) является выполнение неравенства а < 1.

п п

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

I -1- 2 г

•V I

п-1 „ 1=1

Р = Се1 ГТ! 2

и = 1 г,.= о

J , (3)

Л-1'

р. = Сб\ i > J ,

V п-1

п-1

где п

и=I

Л,"'- г

1-1 3 - V-г

I < I > Г 1*1 I <1+ 1 > г

1(1) б1 X ш « * + 1

+1 П-1

г1 а-вг1* г

I п-1

2 в1 П

П-2

\ -1-2 г

п-1 I

1=1 <п-1> г

г -О п-1

р-1 \ -1- Г г

2

ш в К Г,, л

1=1 - = »-■ = «■ Величины подсчитываются рекуррентным образом:

<

< р*1>

V •

<г->)

ш

ш —Ш ф — ±+Ф

о 0 1_

< Р) ' ~1 <р>

*%» «о

< < Р ) < V}. < Р>+1) и - ь и, Ф ,->-Ф т-1 I __I =о

т-1 т

п<и>

> 2. V =Т^Т.

Величина ® является корнем уравнения е - а (ц (1-е)) =0

Г> и

в интервале 0 < в < I.

Характеристики системы Р^, р>=ГГп, системы, входящие в ; критерий качества (I), вычисляются следушим образом:

г1Р

V

V =1

Р,

'и 2 Р

(4)

Формулы (I), (3), (4) определяют явную зависимость критерия качества функционирования системы от параметров .1 ,,1 :. ^

1 2 П ~ 1

Во втором параграфе первой главы рассматривается задача оптимального управления системой с двумя режимами функционирования при наличии платы (а>о) за переключение режимов. Стратегии управления режимом работы системы принадлежат классу гистерезисных стратегий и-задаются двумя порогами .^к

о>

г

г

Г -е. I

1 + 1

г =о 1 + 1

т

-1

.Управление в соответствии с такими стратегиями осуществляется следующим образом. Если в данный момент поступления требования число i требований в системе удовлетворяет неравенству то после этого момента система будет работать в первом режиме, если 1>к - то втором. При система сохраняет тот режим, в котором она работала до данного момента. Использование гистерезисных стратегий вместо пороговых за счет некоторого запаздывания в переключении позволяет уменьшить число переключений с режима на режим, что существенно при наличии платы за переключения.

Под состоянием системы в данный момент поступления

требования понимается пара чисел где 1 - число требований

в системе непосредственно перед'данным моментом, и - номер

режима, в котором будет работать система после данного момента.

Состояния системы в моменты поступления требований образуют цепь

Маркова с пространством состояний <«,1>,1<к;

«,2>,Переходные вероятности цепи имеют вид, аналогичный

(2). Достаточным условием наличия стационарного распределения

состояний цепи является выполнение неравенства, л ^ <1. В

результате решения системы уравнений равновесия для стационарных

вероятностей р(1,1), 1<к, р(1,2), 1>}, получены аналитические

зависимости этих вероятностей от порогов .1,к. Характеристики

системы Ь.^.р ,р , входящие в критерий качества, выражаются 1 2

через стационарные вероятности состояний системы по формулам, аналогичным (4). Среднее число М переключений режимов в единицу времЗни определяется из соотношения:

Полученные результаты позволяют найти явную зависимость критерия качества (I) от порогов _|,к.

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

, Рассматриваемая система может работать в п-и режиме. Штраф

за переключение режимов отсутствует, т.е. а=о в (I). п -режимов соответствуют описанию, приведенному в обшей модели. Механизм функционирования системы в (п+1)-ом режиме станет ясен после описания стратегий управления системой.

Стратегии управления режимами работы системы задаются, натуральными числами (порогами) j ^ .....j ,к, такими, что

12Г.

-1=д ^ ■ •<Лп<я>> +1. Управление в соответствии с

такими стратегиями осуществляется следующим образом. Если в момент поступления требования в системе находится 1 требований, ^ . то до следующего момента поступления требования система будет работать в и-ом режиме, ы=1,п. Если в момент поступления в системе уже находится _(п+1 требование, то в этот момент осуществляется переключение на (п+1) режим.

При работе в (п+1)-ом режиме время обслуживания требований распределено по экспоненциальному закону с параметром р >0. В

П*1

момент переключения на (и+1)-ый режим входной поток отключается и происходит только обслуживание ранее поступивших требований до тех пор, пока .их число не уменьшится до к. После этого через время, распределенное по закону А (ъ) возобновляется поступле-

п+1

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

Под ' состоянием системы в данный момент поступления требования понимается число требований в системе непосредственно перед этим моментом. .

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

параметров ......к стратегии управления. Аналогично тому,

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

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

Во второй главе диссертации исследуются управляемые системы

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

Имеется однолинейная система массового обслуживания'., которая может работать в N+1 режиме. При работе в я-ом режиме на вход системы поступает пуассоновский поток первичных требований с интенсивностью * , в = I,N+1 . Первичное требование, заставшее'

в

прибор занятым, через время, распределенное по экспоненциальному закону с интенсивностью V (р>0), делает попытку вновь попасть

* -а

на обслуживание, таким образом образуя источник повторных

требований, генерирующий • пуассоновский поток с параметром и .

8

Требование (первичное или повторное), заставшее прибор

свободным, немедленно поступает на обслуживание и обслуживается

в течение времени, распределенного по закону В^Съ) с

преобразованием Лапласа-Стилтьеса р (*) и первым моментом ,

8 8

^>0. При этом, если поступившее требование было повторным, число. источников повторных требований уменьшается на единицу. Если повторное требование застает прибор занятым, то состояние системы не меняется.

Рассматриваются классы многопороговых, гистерезисных и. рандомизированных стратегий управления режимами функционирования СМО.

""Критерием качества функционирования СМО так же. как и в главе I. является средний штраф в единицу времени при работе системы в стационарном режиме. Структура среднего штрафа аналйгична структуре функционала (I).

В § I второй главы рассмотрена модель СМО типа М/М/1 с • повторными требованиями и многопороговыми стратегиями управления режимами ее функционирования. Она получается из общей модели при В СО=1-«*р.(-/» О, б=ТД+Т. Штраф за переключение режимов отсутствует. Стратегии управления задается порогами

г4,г2.....гм, удовлетворяющими УСЛОВИЮ' 0=г <г . .-<гм<гм+1=оо.

Управление системой осуществляется следующим образом: если в данный произвольный момент времени число 1 требований в системе не превышает г, то в момент ъ+о система будет работать в первом режиме, если 1«Сг ,г ], то в момент ъ-ю система будет

работать в з-ом режиме, ,N+1.

Под состоянием системы в произвольный момент времени ь понимается число 11 требований в системе в этот момент. Чтобы преодолеть затруднения, связанные с нахождением стационарного распределения 4(1), 1>о, вероятностей состояний немарковского процесса , I рассматривается .вспомогательный процесс

«11,п1»1>о Сп^ индекс занятости прибора в момент О, являющийся цепью Маркова с непрерывным временем. Найдено стационарное распределение вероятностей состояний этой цепи и состояний системы. При этом искомое распределение чш,1>о имеет вид: • •

Л Т 8-1 Г -г, к

ч(|) = ЧС0)-^ П Ркк к" П свк-ч) х

а - к=1 1 = г. +1

к -1

х р1""-1 П Св+1). (5)

а а •

I = г +1 а -1

г < -4 < г , з = I ,N+1 ,

а-1 а

где р =л /у\ , в =л /и , э=Т7Я+Г, вероятность ч(о) находится из

я в" а а 9 а

00

УСЛОВИЯ нормировки ^ ЧС1Э=1.

С использованием (5) находится явная зависимость критерия качества фукнционирования СМО от порогов г ,г .....г,..

12 N

В § 2 второй главы исследована модель системы типа М/М/1 с

повторными требованиями и гистерезисными стратегиями управления.

Система может работать в двух режимах. Времена обслуживания

требований . распределены по экспоненциальным законам,

В О, з=1,2. Критерий качества функционирования СМО

в в

включает в себя штраф за переключение режимов.. Стратегии управления задаются порогами .ьк (о^<к<оо). Управление системой осуществляется следующим образом. Если в данный произвольный момент времени ь число 1 повторных требований в системе удовлетворяет условию то в момент система 1>удет

работать в первом режиме, если 1>к, то во втором. При .к^к система в момент л+о сохраняет тот режим, в котором она работала в момент ъ.

Под состоянием системы в произвольный момент времени <понимается пара чисел <а ,г> » ч , где 1 - ' число повторных

111 *о I

требований в системе в момент ъ, г - номер режима, в котором

система работает в момент ь. Для того,■чтобы найти стационарное распределение вероятностей системы, рассматривается, также как и в предыдущем параграфе, вспомогательный процесс

» ^ , явля! шея цепью Маркова. Найдены стационарные распределения вероятностей состояний цепи и системы, а также явная зависимость критерия качества функционирования системы от .порогов .¡,к. Процедура поиска оптимальных значений порогов реализована на ЕС-ЭВМ.

В § 3 второй главы рассмотрена система типа М/в/1 с повторными требованиями и многрпороговыми стратегиями управления режимами ее функционирования. Соответствующая математическая модель получается из обшей модели в предположении, что штраф за переключение режимов отсутствует, а стратегии управления задаются порогами 1 г ,г .....г , где -1=г <г <г ^ =<».

1 г N О 1 N N+1

Управление ' осуществляется следующим образом: если число 1 требований в системе в момент окончания обслуживания требования принадлежит интервалу (Г ,г ], то до следующего момента

п- 1 п

окончания обслуживания система будет работать в

п ~ ом режиме,

N + 1.

Для такой системы найдены рекуррентные формулы для стационарных вероятностей ч ,1>о, наличия 1 требований в системе

V

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

г

П (а) = \2\■< I. п =ТЖГ,

П V '

I = Г +1

п- 1

этих вероятностей.'

В случае экспоненциально распределенного времени обслуживания и одного порога аналитические зависимости

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

В четвертом параграфе второй глары исследована задача оптимального управления режимом функционирования СМО типа МЛЗ/1 с повторными требованиями в классе рандомизированных стратегий. Математическая -модель системы получается из общей модели при следующих предположениях:

- А кА яс, . =?1 '

12 N+1 ' '

- и -и =...■ =и:

»2 N»1

- штраф за переключение отсутствует;

- стратегии упрс_ления режимом работы системы задаются N+1 параметрам ql ,ч2.....ч(|4.1. где

к =1

Управление в соответствии ~ такими стратегиями

осуществляется -следующим образом: в момент окончания

обслуживания требования с вероятностью принимается решение о

том, что очередное поступившее на обслуживание требование будет

обслуживаться в течение случайного времени, распределенного по

закону В (О. Будем считать, что в этом случае до следующего к

момента окончания обслуживания система работает в к-ом режиме, . к=ГЖГ.

Для такой системы найдена явная зависимость критерия

качества ее функционирования от параметров ч .ч.....

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

В третьей главе диссертации рассмотрены две математические модели СМО, функционирующих в синхронной случайной среде.

В О I третьей главы исследована система массового обслуживания, которая работает под управлением случайной среды с * ~ ■ •

т

М<со состояниями (1,и), 1=1,ки, и—1,т, Еки=М. Если среда

и-1

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

моментом ь^1,и><со. Среда может изменять свои состояния только в моменты окончания обслуживания требований в системе. Состояния среды в моменты окончания обслуживания требований образуют цепь Маркова.

Переходные вероятности среды позволяют трактовать поведение среды'следующим образом: за время нахождения случайной среды в состоянии (1,и) в системе обслукится. ^ требований, где случайная величина £ и имеет геометрическое распределение с параметром п „, т.е.' Р-(г ,,,*>=ч!'~Л<1-ч1 После пребывания

I , и 11 и V »и 111»

в состоянии (.1,и) среда переходит в ■ состояние 0+1,и), если 1<к -I. Если же 1=к , то с вероятностью Р среда переходит в

р Р г

состояние С1.р), г=1,т.

Под состоянием системы в моменты окончания обслуживания

требований понимается число 1 требований в системе в эти

1 моменты. Состояния <а ,1 ,и » ^ среды и системы

1к 1к к

"в моменты ь ,к>1, окончания обслуживания требований образуют к

однородную цепь Маркова. Доказано, что достаточным условием наличия стационарного распределения а, ю, 1*0,1=1,^,^=17^. этой цепи является выполнение неравенства:

т . ки 1-е, 1=1

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

' ;=о

стационарного распределения состояний цепи. Найдено решение этой системы в виде:

.»'Л, »А •

-I

1-1

Ри55 П 4>п,и(:г)

к

т г »

С Ея'О.г)

о '

Г = 1)=1

' п = ; ' ...

(6)

1=1 .ки. «->=! ,т.

где

(1-я .

ц> (г)--"-г п'г

■Х.-Ц р

п , г п , г

)р (Л (1-2)) _ __

- г п . г_ _Т , -

(л (1-х)) • П_ ' Г' г"1'т'

*(2:>=1- Ерг П ^ гСа>,

а вероятности л ^.к , г=1 ,т, наедятся из • системы

линейных алгебраических уравнений:

к к

? п ^ г(х. )=0, к-1,М-1.

к

m г

Е Erto(j,r)=

r = ij~t

ГО к а L-P

9=1 Е- п= 1 1-4 п , в

m к 9 I

В=1 Е-1 1-4 Г>

где k=I,M-I, - iкорни уравнения в единичном круге

комплексной плоскости Ы<1, ^I, k=I.M-I.

Соотношения (6) позволяют получить производящую функцию маргинального распределения вероятностей состояний системы, а также условные и безусловные средние значения длины очереди в

■системе. В случае, когда л i=I,ky. v=T7m, полечено

преобразование Лапласа-Отилтьеса времени пребывания требования в системе. Реализована процедура расчета вероятностно-временных характеристик системы на ПЭВМ типа IBM PC.

Во втором параграфе третьей главы рассмотрена математическая модель СМО типа M/G/1/M, функционирующей в синхронной случайной среде специального вида, адекватно описывающей влияние процесса передачи информации в транспортной станции локальной вычислительной сети "Квант-С" на процесс приема информации 1151 . Случайная среда может пребывать в четырех фазах (состояниях): О, I, 2, 3. Синхронный характер среды проявляется в том, что смена ее фаз, а также длительности некоторых фаз зависят от процессов поступления и обслуживания в системе. В свою очередь, случайная среда влияет на поведение системы при попадании последней в свободное состояние. Взаимодействие среды и системы происходит следующим образом.

Во время периода занятости в системе случайная среда находится в фазе 3. В момент окончания периода занятости с вероятностью q (CKq<I) среда переходит в фазу 0, с дополнительной вероятностью I-q - в фазу I. Время пребывания среды в фазе О распределено по закону Н (t) с первым моментом ь <».

о о

Если во время пребывания среды в фазе 0 в систему поступят требования, то 'они либо становятся в очередь, либо уходят из системы необслуженными, если в очереди уже нет свободных■мест. • В таком случае (если требования поступили), после окончания фазы О случайная среда-переходит в фазу 3, в системе начинается период занятости. Если во время пребывания средь; в Фазе О в систему не поступило ни одного требования, то по окончании фазы 0 среда

переходит в фазу 2.

Фаза I (фаза 2) длится в течение экспоненциально распределенного с параметром ь"1, i^Ca» (ь~*, ь2<°о) времени, если за это время в систему не поступит требование. После этого среда переходит в фазу 0. Если же'во время пребывания среды в фазе I (фазе 2) в систему поступило требование, то соответствующая фаза .заканчивается, среда переходит в фазу 3, требование немедленно начинает обслуживаться.

Отметим, что при отсутствии фаз 1,2 у случайной среды рассматриваемая модель аналогична моделям СМО с отключением обслуживающего прибора.

Для такой СМО найдены в аналитическом виде стационарные вероятности числа требований в системе в моменты окончания обслуживания требований и в произвольные моменты времени, преобразования Лапласа-Стилтьеса распределений периода занятости и времени пребывания требования в системе, стационарное распределение вероятностей состояний среды, вероятность потери требования.

Численная процедура расчета вероятностно-временных характеристик системы, реализованная на ПЭВМ типа^ IBM PC. использовалась при оценке производительности и настройке протокольных параметров локальной вычислительной сети "Квант-СГ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

I. Исследованы математические модели СМО типа GI/M/1 с управляемым режимом функционирования, адекватно описывающие ситуации, возникающие при организации динамического управления потоками и ограничения нагрузки в информационно-вычислительных сетях. Рассмотрены практически важные классы многопороговых, гистерезисных и 'многопороговых с отключением входного потока стратегий управления режимом функционирования СМО. Для каждой из .систем получено стационарное распределение числа требований в система в моменты поступления требований и явные зависимости критерия качества функционирования СМО от параметров используемой стратегии управления. На основании этих зависимостей реализованы простые численные процедуры поиска оптимальных

стратегий в соответствующих классах.

2.Исследованы математические модели СМО типа М/С/1 и М/М/1 с повторными требованиями и управляемым режимом функционирования, рассмотрены классы многопороговых, гистерезксных и рандомизированных стратегий управления.

Для системы типа М//3/1 с многопороговой стратегией управления получены рекуррентные формулы для стационарного распределения числа требований в системе в моменты окончания обслуживания требований и для частичных производящих функций этого распределения.

Для экспоненциальной УСМО с многопороговыми и гистерезисными стратегиями управления и СМО типа М/г/1 с рандомизированными стратегиями найдены в замкнутом виде стационарные распределения числа требований в системе и явные зависимости критериев качества функционирования систем от параметров используемой стратегии.

Реализована численная процедура поиска оптимальной гистерезисной стратегии управления ренимом функционирования СМО типа М/М/1.

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

3. Изучен процесс функционирования системы типа МЛЗ/1 в синхронной случайной среде рандомизированно-циклического рчда. Получены производящие функции стационарных маргинальных и совместных распределений состояний среды и системы, условные и безусловные средние значения длины очереди. В случав, когда интенсивности входного потока во всех режимах одинаковы, получены преобразования Лапласа-Стилтьеса функции распределения времени пребывания требования в системе и среднее значение времени пребывания. Реализованы процедуры расчета полученных вероятностно-временных характеристик системы на ЗВМ.

4. Изучен процесс функционирования транспортной станции локальной вычислительной сети "Квант-С". Построена математическая модель СМО типа МЛЗ/1/Ы, функционирующей в синхронной случайной среде, адекватная реальному процессу обмена информацией в транспортной станции. Найдены в аналитическом виде все основные стационарные вероятностно-временные характеристики

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

По теме диссертации опубликованы следующие работы:

1. Клименок В.И. О решении функциональных уравнений для преобразования Лалласа-Стилтьеса распределения периода занятости в системах массового обслуживания // Ред. журн. "Вестник БГУ. Сер. I". - Минск. - 1988. - 22 с. Деп. в ВИНИТИ 19.04.88. - (Р 2965-В88. ' "

2. Дудин А.Н., Клименок В.И. Об одной управляемой системе с повторными вызовами // V Всесоюзная школа-семинар по автоматизированным системам массового обслуживания. - Тезисы докладов.

- Рига: ЦНИИСУ ГА. - 1988. - с.301-302.

3. Клименок В.И. Модель системы с повторными требованиями и управлением в моменты окончания обслуживания требований // Методы исследования информационно-вычислительных систем. Тезисы докладов. - Минск: БГУ. - 1989. - с. 52-53.

4. Клименок В.И. Оптимизация управления многоскоростноп системой массового обслуживания с повторными вызовами в классе рандомизированных стратегий // Совершенствование методов исследования потоков событий и систем массового обслуживания. -Тезисы докладов. - Томск: ТГУ. - 1989. - с. 105-106.

5. Клименок В. И. Оптимизация динамического управления режимом работы информационно-вычислительных систем с повторными вызовами // Автоматика и вычислительная техника. - 1990. - № I.

- с. 25-30.

6. Клименок В. И. Стационарные характеристики системы МЛЗ/1, функционирующей в синхронной случайной' среде без памяти // Математические методы исследования сетей связи и сетей ЭВМ. -

; Тезисы докладов.. - Минск: БГУ.- 1990. - с. 50-51. : 7\ Клименок В. И. Расчет характеристик системы МЛЗ/1, функционирующей в синхронной случайной среде // Анализ и синтез систем массового обслуживания и сетей ЭВМ. - Тезисы докладов. -4.1. - Одесса. - 1990. - с. 87-92.

8. Дудин А.Н., Клименок В.И. Модель приемника транспортной станции ЛВС как СМО M/G/1/N с выключающимся прибором // III Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. - Тезисы докладов. - М. - 1990.

- с.81-83.

9/ Клименок В.И. Модель приемника транспортной станции локальной вычислительной сети // Сети связи и сети ЭВМ как модели систем массового обслуживании. - Тезисы докладов. -Минск.: БГУ. - 1991. - с. 69-70.

10. Дудин А.Н., Клименок В.И. Оптимизация динамического управления входной нагрузкой в узле информационно-вычислительной сети // Автоматика и вычислительная техника. - 1991. - 1? 2. - с. 25-31.- *

11. Дудин А.Н., Клименок В.И. Оптимизация управления мультирежимной системой типа GI/M/1 // Математическое моделирование народно-хозяйственных процессов. - Петрозаводск. - 1990. -с. 14-21.

12. Дудин А.Н., КЛименок В.И. Модель функционирования транспортной станции локальной вычислительной сети // Распределенные микропроцессорные управляющие системы и локальные вычислительные сети. - Тезисы докладов. - Томск: ТГУ. - 1991. -с. I0I-I03. •

13. Клименок Б.И. Динамическое управление входной нагрузкой в узле информационно-вычислительной сети //IV Всесоюзное совещание по распределенным вычислительным системам массового обслуживания.'- Тезисы докладов. - М. - 1991. - с.138-139.

14. Клименок В.И. Оптимальное управление входным потоком в узле информационно-вычислительной сети // XVI Всесоюзная школа-семинар по вычислительным сетям..- Тезисы докладов. - ч.2. - М.

- 1991. - с.207-210.

15. Клименок В. И. Математическая модель приемника транспортной станции локальной вычислительной сети //Автоматика и вычислительная техника. - 1991. - К1 5. - с. 62-69.