автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Модели управления конфликтными потоками в случайной среде

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

КУДЕЛИН Александр Николаевич

МОДЕЛИ УПРАВЛЕНИЯ КОНФЛИКТНЫМИ ПОТОКАМИ В СЛУЧАЙНОЙ СРЕДЕ

Специальность 05.13.17 - Теоретические основы информатики

Автореферат

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

Нижний Новгород, 1997

^ /

/Ъ <5Г «ъ

Работа выполнена в Нижегородском государственном университете им.Н.И.Лобачевского.

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

Официальные оппоненты: - *

доктор физико-математических наук, доцент В.Г.Ушаков, кандидат физико-математических наук, доцент А.Г.Факеев.

Ведущая организация - Опытно-конструкторское бюро машиностроения (г. Нижний Новгород).

Защита состоится " 6 " 199 У г. в

■(О/<90 часов на заседании диссертационного совета ССК 063.43.01 научно-исследовательского института прикладной математики и кибернетики при Нижегородском госуниверситете им. Н.И. Лобачевского по адресу: 603005, Нижний Новгород, ул.Ульянова, д. 10.

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

Автореферат разослан " " 199 ? г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

А^Л

I

Ю.Л.Кетков

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

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

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

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

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

в) структура некоторых элементов системы может изменяться в процессе ее функционирования.

Значительный вклад в развитие теории управляемых систем массового обслуживания внесли работы Бронштейна О.И., Гнеденко Б.В., Башарина Г.П., Боровкова A.A., Климова Г.П., Коваленко И.Н., Королюка B.C., Рыкова В.В., Ушакова В.Г. и ряда зарубежных ученых, например, Джейсуола Н., Данна М., Клейнрока JI., Неугса М.Ф., Потгса Р. и других. Однако классические способы описания систем алгоритмического управления потоками приводят к весьма сложным математическим моделям, трудно поддающимся аналитическому исследованию ( см., например, Климов Г.П. Системы обслуживания с разделением времени I. // Теория вероятностей и ее применения,-1974,-Т. 19.-Вып.3.-стр. 558-576. ). Поэтому проблема разработки методов описания и анализа подобных систем является актуальной. Среди систем алгоритмического управления потоками заявок можно выделить класс систем, функционирующих в случайной среде, которая оказывает влияние на вероятностную структуру входных потоков. При этом в зависимости от состояния среды входные потоки могут представлять собой или потоки отдельных заявок или так называемые неординарные потоки (потоки пачек). Построение и анализ моделей таких систем также представляются весьма важными.

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

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

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

Практическая ценность. Исследование систем алгоритмического управления конфликтными потоками требований в случайной среде проводилось в рамках НИР "Изучение функционалов от случайных процессов в задачах построения статистических решающих правил, вероятностного представления решений дифференциальных и интегральных уравнений и массового обслуживания" ( № гос. регистрации 0191.10054234 ), "Построение и анализ нетрадиционных • вероятностных моделей процессов обслуживания и адаптивного управления" (N9 гос. регистрации 0191.0041837 ), "Анализ однородных алгоритмов управления конфликтными потоками в случайной среде" (№ гос. регистрации 0196.60012274), выполненных на кафедре прикладной теории вероятностей ННГУ и в лаборатории теории вероятностей и математической статистики НИИ прикладной математики и кибернетики при ННГУ. Результаты исследований использованы при выполнении хоздоговорной работы "Разработка

вероятностно-статистических методов построения, анализа и синтеза моделей конфликтных управляемых систем обслуживания" по программе "Университеты России" (номер темы 1.3.26, направление "Фундаментальные проблемы математики и механики", раздел "Вероятностно-статистический анализ").

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

Апробация полученных результатов. Результаты

диссертационной работы включены в сборники тезисов докладов и трудов следующих конференций и семинаров:

1. Республиканская научная конференция "Математическое и программное обеспечение анализа данных" (БГУ, Минск, 1990).

2. VII Белорусская зимняя школа-семинар "Сети связи и сети ЭВМ как модели массового обслуживания" (Гродно, 1991).

3. IV Всесоюзное совещание "Распределенные автоматизированные системы массового обслуживания" (Душанбе, 1991).

4. Всесоюзная конференция "Математическое и машинное моделирование" (ВТИ, Воронеж, 1991).

5. Международная конференция "Компьютерный анализ данных и моделирование" (БГУ, Минск, 1995).

6. XI Белорусская Межгосударственная зимняя школа-семинар "Исследование сетей связи и компьютерных сетей методами теории массового обслуживания" (БГУ, Минск, 1995).

По теме диссертации опубликовано 10 работ, список которых приводится в конце автореферата.

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

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

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

В первой главе проводится построение и последующий анализ вероятностной модели системы управления конфликтными потоками

заявок П1 , Ш.....Пт в классе однородных циклических алгоритмов.

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

При этом, если среда находится в состоянии е<°>, то входные потоки являются простейшими потоками Пуассона. При состоянии среды е"> входные потоки представляют собой потоки пачек заявок, для которых достаточно адекватной математической моделью являются неординарные потоки Бартлетта (см., например, работы: Федоткин М.А. Неполное описание потоков неоднородных требований // В книге: Теория массового обслуживания,- М.: Изд-во МГУ, ВНИИСИ, 1981. - с. 113-118; Высоцкий A.A., Федоткин М.А. Методы анализа потоков с зависимыми интервалами поступления требований // Тезисы докл./ Научно-техническая конференция с международным участием "Микросистема-92",- Томск, 1992.-е. 57-59.). Обслуживающее устройство имеет 2т циклически сменяющихся состояний П», Г<2>, ... , Г'2т) . В каждом состоянии Пг> оно находится в течение времени Тг, г=1,2,...2ш. При этом обслуживающее устройство выполняет не только функции по обслуживанию требований, находящихся в накопителях, но также функции по управлению потоками, по формированию очередей, по отбору требований из накопителен в соответствии с некоторыми присущими ему механизмами. Для таких управляющих систем обслуживания задают так называемые потоки насыщения П'| ,

П'г.....П'ш , определяющие выходные потоки в случае бесконечных

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

отдельной заявки, а целой группы заявок в некоторые специальные моменты времени. Рассматриваемые при построении модели случайные объекты определяются или задаются конструктивно на некотором полном вероятностном пространстве (П, Р(-))

элементарных событий со е Í2 с ст-алгеброй ? и вероятностной мерой Р(А), А е Все протекающие в системе процессы рассматриваются либо на интервалах времени, либо в моменты, порождаемые некоторым заданным точечным случайным процессом х = {t¡ ; i > 0 } на оси времени.

Произвольный входной поток n¡ описывается векторной случайной последовательностью {(t¡,v^rij.i) ; i > 0} , где r|j,i - число заявок типа v¡ , поступивших по потоку nj на интервале времени [tí,Tí+i). Поведение случайной среды описывается марковской последовательностью {v¡ ;i > 0}, где v¡ е {е<°>,е<»}. В качестве идеализации в рассматриваемой модели принимается, что на любом промежутке времени [t¡,t¡+i) состояние случайной среды не меняется. Случайные элементы (метки заявок) v¡, i > 0 связаны соотношениями

где V I ( • , • ) - некоторые измеримые отображения пространства {е<°>,е<»}х(0,1) на {е<°>,е<'>}, а {со, ; I > 0} - последовательность независимых случайных величин (например, равномерно распределенных на интервале (0,1)). В данной модели принимаем, что величины ъ , \ > 0 являются моментами смены состояний обслуживающего устройства. Предполагается, что в любой момент времени I > 0 обслуживающее устройство находится в некотором состоянии Г(0еГ={ Г<'>, П«,..., }.

Равенство Г(1) = Г<г> при т-2]-\ означает обслуживание только

требований из очереди потока П^ j=l,2.....т. При т=2) равенство Г(0 =

=ПГ) соответствует запрету на обслуживание всех потоков (состояние переналадок). Циклическое управление входными потоками и изменениями состояний обслуживающего устройства можно представить в виде '

Здесь полагаем, что П = Г(ъ) = Г(ъ+0), Г($=Г(тО , i¡< t < t,+i , i > 0.

v,+i=\j/¡(vi, со i) ,

Последовательность {ц ; 1 > 0} при То=0 определяется рекуррентным соотношением

тм = т, +У(П),

где У(*) - отображение множества Г на числовое множество {Т| , Тг , ...Дгш}, такое что Тг = У(ПГ>) . Назовем величину Тг

2т

длительностью фазы (состояния) Пг>, а величину Т=^ Тг - периодом

г=I

работы обслуживающего устройства.

Произвольный поток насыщения П^ описывается с помощью маркированного точечного процесса {(ъ.у'^,,) ; 1 > 0}, где у\ - метка обслуженных заявок на промежутке времени [ъ,тж), а при каждом j=l,2,...,m случайная величина определяет на этом же промежутке времени по потоку ^ максимально возможное число обслуженных заявок при наличии бесконечной очереди. Ради простоты полагаем, что случайная среда не влияет на процесс обслуживания и метка у', = =П, т.е. процедура обслуживания определяется только состоянием обслуживающего устройства.

Пусть = (Хи . "/2,1 , ... , Х"м) " вектор длин очередей, .¡-я координата которого Хм задает число заявок в очереди по потоку П, в момент ъ. Обозначим через число фактически обслуженных заявок

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

величинами Хьь Пм и . те-Из естественных ограничений

вытекает, что

£ тт{хи+Т1у, & } , j = 1, т , \ > 0 . (1)

В дальнейшем полагаем в'(1) выполнение только равенств. Такую стратегию механизма обслуживания назовем экстремальной.

Поведение системы в целом можно теперь описать маркированным точечным процессом {(т, , П , v, , ; i > 0} с выделенной дискретной компонентой (меткой) {(Г,, V,, ; i > 0}. Для точечного процесса имеет место рекуррентное по i > 0 соотношение

(Ti+i, Гм , v1+), Xi+0 = (Ti +У(П), и(П), \^i(Vi,C0i), max{Xi+t|r § , 0 }),

где r|i - (r|i,i , r|2,i , ... , T|m,i ) , = , £,2,i , ... , ) , 0 - вектор размерности m с нулевыми координатами. Поскольку входные потоки и потоки насыщения независимы, а обслуживающее устройство работает в жестком циклическом режиме, можно рассматривать процесс обслуживания отдельно по каждому потоку. По любому потоку Flj этот процесс описывается маркированным точечным процессом {(ti, Ti, Vi, Xi,i) ; i ^ 0} , дискретная компонента которого удовлетворяет рекуррентному соотношению

(П+|, Vi+i, Xi.i+0 = ( и(П), V|/i(Vi,(Oi), maxJXj.i+'nj.i- £j,i, 0}) . (2)

Для изучения вероятностных свойств метки {(П , v, , ^ьО ; i > 0} в данной модели принимаем, что при фиксированных значениях метки {(Гк, vK, ; 0 < к < i} случайные величины t|j,i и независимы и их условные распределения удовлетворяют соотношениям

Р(ТЪ,1 = у | Гк = Ск, .VK = d* ,50,к = Xj,K , 0 < к < i )=P(ru,i = y|ri = Ci,vi = di), P(£j,i = z | Гк = ск ,VK = dK, Xi,k = Xj,K, 0 < к ^ i )=Pfe = z | П = сi ,vi =d¡), (3)

где у = 0,1,...; z=0,l,...; ск e Г; dK e {e<°>,e<')}; Xj,K = 0,1,...; j = TJn, P(ru,i = у | Г, = ГМ, Vi = &»>) = (XjTr)y (y!)-'exp {-A.jTr} ,Xj > 0 (4)

и

p( 4>j = Уi п = rw ,vi = ©■))=( (VjTr) У Су!)1 (1-gj) У +Z (m!)-' x

m=0

M

x(l-&)m2 (VjTr)4s!)-"gj41-qj)Sqjy-m-2sCs-1y-m.s.i)exp(-VjTr), (5)

s=\

y—m

где M=[--]- целая часть (y-m)/2, 0 < gj , qj < 1 ;

Ъ = ъ (1 +а 0 -<й )•')•', (6)

Р(5м=4 |П=ГЙ-'))=1,

где = [^Ти и] - целая часть (-1), щ > 0 ,

Р(^=0 |Г,= ГМ) = 1 , 1 <г^2ш , г*2>1 . Здесь X] - интенсивность пуассоновского поступления заявок, -интенсивность обслуживания заявок по потоку Г^ ; а , - параметры распределения Бартлегта, X'] - интенсивность поступления пачек в потоке Бартлетта. В данной модели принято, что интенсивности поступления заявок по потокам Пуассона и Бартлетта совпадают (см.(6)). Используя соотношения (2),(3), доказывается следующее утверждение.

Теорема 1. Последовательность {(П , VI, ; 1 > 0} при заданном распределении вектора (Го, Уо, Хь°) является марковской.

При изучении марковской последовательности {(П , Хи) ; I > 0} одной из основных задач является исследование свойств ее одномерных распределений. Эти распределения при некоторой выбранной нумерации состояний цепи Маркова представляют собой бесконечномерные векторы Р(, \ > 0 из вероятностей

Р( П = ГМ, V; = е« , Хм = ), гм 6 Г, е<5> е {ее»,ес>} , х^ = 0,1.....

Считая, что начальное распределение Ро задано, можно найти соотношение Рм= Р^Р , где Р- бесконечномерная матрица переходных вероятностей цепи за один шаг. Обозначим вероятности

Р(Г| = ГМ, У1=е<'>,хи = х) = 0и(гм,е<*>,х) , ¡>о,

а условные вероятности (4) и (5) соответственно через Ф;,о(у,Тг) и ф],|(у,Тг) . На основании рекуррентных соотношений (2) и свойств распределений (4) и (5) были получены рекуррентные по I > 0 формулы для одномерных распределений

{ Оы( Г<г>, ем, х ) : Г« € г,е«е {е«»,»1)} , х = 0,1,... } ; ¡>0,

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

распределений выделенной дискретной компоненты. Из функциональной зависимости и() нетрудно видеть, что изучаемая марковская цепь {(П , V; , ХьО ; 1 > 0} является периодической с периодом 2т. Из общей теории цепей Маркова со счетным числом состояний следует, что с течением времени либо все вероятности 0)Х Пг>, ей , х) стремятся к 0 и в системе не существует стационарное распределение, либо сущесвует стационарное распределение, соответствующее устойчивой работе системы. Важно выяснить, каким условиям должны удовлетворять параметры входных потоков, случайной среды и системы управления, при которых стационарное распределение существует. С этой целью в последующих исследованиях использовался аппарат производящих функций

Ф^ (гм, ем, у)= £ 0ы( гм, ем, х) Vх , | у] < 1, / >о (7)

х=0

распределений дискретной компоненты. На основании рекуррентных формул для вероятностей

{ 0ы( ГМ, е« , х): Г« е Г, ем е {е«»,е<'>} , X = 0,1,... } ; 1 > 0 ,

были получены рекуррентные по 1 >: 0 соотношения для производящих функций (7). Эти соотношения, в свою очередь, позволили получить рекуррентные соотношения, связывающие значения производящих функций через 2т шагов, т.е. через период Т работы обслуживающего устройства. С использованием этих соотношений был предложен итеративно-мажорантный метод, который позволил доказать следующие утверждения.

Теорема 2. Для существования стационарного распределения последовательности {(П , VI, Хы); 1 2 0} необходимо выполнение условия Х;Т-1>< 0.

Теорема 3. Для существования стационарного распределения последовательности {(Г,, VI, Х),0 ¡1^0} достаточно, чтобы < 0 .

При доказательстве теоремы 3 было также показано, что если стационарное распределение указанной последовательности существует, то очередь по потоку ^ с течением времени не может возрастать неограниченно. Следует отметить, что в рассматриваемой модели возможно существование стационарного распределения как для любого отдельного потока Ц , j=l,2,...,m, так и во всей системе в целом (для всех потоков одновременно), если А/Г- ¡¡<0 , j=l,2,...,m. Это также является следствием независимости входных потоков, потоков

насыщения и строгой цикличности работы обслуживающего устройства.

Во второй главе диссертации рассматривается модель системы управления ш конфликтными потоками заявок в случайной среде (свойства среды описаны в первой главе). При этом среди ш потоков выделены три характерные группы: поток П| является малоинтенсивным, информативным и приоритетным потоком; потоки Ш, ... , Пш-1 образуют группу малоинтенсивных потоков; поток Пт является интенсивным и приоритетным. Информативность потока П| означает, что в динамике работы системы обслуживания учитывается наличие заявок в накопителе и поступление требований по этому потоку. Приоритетность потока П1 означает необходимость оперативного обслуживания заявок, -поступающих по этому потоку. Приоритетность потока Пш означает, что при отсутствии заявок по потоку П| (разрыв) может быть продлено обслуживание по потоку Пш. В соответствии с этими соображениями организована работа обслуживающего устройства, имеющего 2ш+1 состояний, образующих множество Г={Пг> : г=1,2, ... ,2ш+1}. В некотором состоянии Пг> обслуживающее устройство находится в течение времени Тг, г=1,2,...,2ш+1. Как и в случае циклического алгоритма, обслуживающее устройство выполняет функции по обслуживанию требований (в состоянии Гй-'), j=l,m обслуживается только поток П|), по управлению входными потоками, по формированию очередей в накопителях и по отбору требований из очередей с помощью некоторых механизмов. В состояниях П2-!), j=l,m не обслуживаются требования ни по одному из потоков. В состоянии П2т+|> обслуживаются требования из очереди по потоку Пт . При построении математической модели системы управления потоками использованы те же соображения, что и в первой главе, естественно, с соответствующими поправками на применяемый алгоритм. Специфика используемого в данной модели алгоритма с упреждением отражена в формуле

Гт=и(П,хи,Г||.0 =

для всех 1 = 0,1,...

р(|) _ г<г»о.

Г1"" , Г, =Г<", г= 1,2.....2т- 2;

г'2"" , г, б{г<г"-" ,г,г,"и,}&шах{^ ,77м}>0;

Г12""'', Г, е{г(2~" ,Г(!"""}&шах{^ = 0

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

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

Д = {(Ti.n, Vi,Xi);i^0},

для которого имеет место векторное рекуррентное по i > О соотношение

(Xi+i, Гн-i, Vhi , Xi+i)

= (xi + V(rO, и(Г,, X'.i . Ли) . Vi(vi, coi), max +t]i - $ I 0}).

При изучении вероятностных свойств дискретной компоненты процесса Д, т.е. его метки {( П , v, , Xi ) I ' ^ 0} оставим в силе предположения о независимости входных потоков и потоков насыщения, а также о свойствах условных распределений величин rjj.i и . Поскольку при управлении потоками в классе алгоритмов с упреждением (или приоритетных алгоритмов), используемых в данной модели, обслуживающее устройство имеет еще одно состояние П2т+|>, то формулы, отражающие дополнительные свойства условных распределений величин r[j,i , нетрудно получить из (4) и (5),

полагая в них Пг> = П2т+|), Тг= Тгт+i и обозначая через /'т= [|imT2m+i] -целая часть величины (imT2m+i . В соответствии со структурой рассматриваемой системы управления m конфликтными потоками заявок наибольший интерес представляет изучение процессов обслуживания по потокам П| и Пга . Важное свойство выделенной дискретной компоненты процесса Д сформулировано и доказано в виде теоремы.

Теорема 4. Последовательности {(П, Vi, хО; i S: 0 } , {(Г,, Vi, Хи); i > 0} и {(П, Vi, Xi.i, X.n.0;' -0} при заданном распределении вектора (Го, Vo, X») являются марковскими.

Следующим этапом исследований явилось подробное рассмотрение вероятностных свойств последовательностей {(Г , Vi , Xi,i); i > 0} и {(^, Vi, Xi,i, Xm,i); i > 0} .Из рекуррентного соотношения для точечного процесса Д нетрудно получить рекуррентные по i > 0 соотношения

(П+1, Vi+|, xi,i+i) = (U(n, Xi,i, T|1.0 . v|/i(Vi, C0i), шах +Ли - Ы > 0}). (Гж, Vi+1 , Xl.i+l , Xrn,i+l) =

= (и(Г], х>.1, Ли), , ©О, тах{хи , 0},

. тах{Хт,1 +Г|т,1-^т,1 , 0}).

Заметим, что исследование последовательностей {(П, , хО ; 1 £ 0} и {(П , VI, XI,I, Хь'); 1^0}, j=2,3,...,m-l, проводится аналогичным образом.

Обозначая вероятности

Р( п = г<г>, у, = ем, Х'Л = х) = (31,,(Пг>, е«, х),

Р( п = Пг>, у, = е«, хи = х , Хт,1 = у) = , е«, х, у),

на основании доказанной теоремы 4 и формулы полной вероятности можно получить рекуррентную формулу

(31+1( Пг>, ем , №1 , \Ут) = I (К Г^), ее) , X , у ) tpi.bC т, Тк) фт,н( Пт, Тк) X хР(4м = * | П = ГОО) = > | П = Пк) )Р( и(ГВД, х, п, )= П'> )х хР(^(ем, ш0=ем)Р(шах{х+п 1 | ,0}=W|)P(max{y+nш-jm ,0}= чгт). (8)

В этой формуле суммирование ведется по всем точкам (гоо, ем, х, у, ш , пт,.м,^ )е Гх{е<°),е(|)}х{о,1, ...}х{о,1, ...}х{о,1, ...}х х{0,1, ...}х{0,1, ...}х{0,1, ...} .

С учетом (8) и вида условных распределений для т^ , , Г)т,| , 4т,■ были получены рекуррентные формулы для одномерных распределений дискретной компоненты {(П , V, , хи , Хт.' ); > ^ 0}. Принимая во внимание специфику алгоритма управления, легко видеть, что

<2,+ |( П2т>, е<»), 0 , Wm) = о при всех wm > 0 и 1 > 0 ; д1+1( П2т+|>, ем , ип , \ут) = 0 при > 1 , 1 > 0 .ее {0,1},

а также что СМ П1', ем , 0 , \ут) = 0 при всех \ут> 0 , 1 > 1 , в е {0,1}. Это позволило доказать следующее вспомогательное утверждение.

Лемма 1. Пространство X состояний цепи Маркова {(П,У|,Х1й , Хш,0; ¡>0} распадается на незамкнутое множество Хо несущественных состояний и минимальное замкнутое множество Х1 существенных сообщающихся непериодических состояний.

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

Лемма 2. При любом начальном распределении {Qo(nr), e<s>, wi, wm): (ГМ, ew, wi, Wm ) б X} векторной цепи Маркова {(П ,Vi, %i,i, ); i > 0}

либо для всех (Пг>, e<s>, wi , wm) e X имеем lim Qi(r<r>, e<s>, wi , wm) = 0

/-»00

и в системе не существует стационарного распределения, либо существуют пределы

lim Qi(Hr>, e« , wi, wm ) = Q(Hr>, e« , wi , wm) > 0 , /->00

такие, что £ Q(nr> , e<s> , wi , wm ) = 1 и в системе существует стационарное распределение.

Фактом независимости предельного распределения от начального мы пользовались в дальнейшем, полагая, что вероятности Qo(r<r> , e<s> , wi , wm ) = 0 для всех (Пг>, ем, wi, wm)eX0 и что для некоторого zo > 1 выполняется неравенство

2/И+1 1 СО СО

2 I z Е zoW|+w™Qo(nr), ew , Wi, wm) < +00 .

r=1 i=0w,=0w.=0

При изучении асимптотических свойств распределений' векторной последовательности {(Fi.v,, Xu, 7vm,i); i>0}, как и для циклического алгоритма, использовался аппарат производящих функций распределений и итеративно-мажорантный метод. На основании рекуррентных формул для одномерных распределений дискретной компоненты были получены рекуррентные соотношения для двумерных производящих функций

00 00

Oj(r<r>, ем, Z, V) = 2 Z Qi(nr>, ем, Wl, Wrn) zw' Vw» ,

w,=0w.=0

iäO, ГМе Г, ем 6 {em.eo},

соответствующих одномерным распределениям рассматриваемой векторной последовательности. Здесь для комплексных аргументов z и v полагаем, что по крайней мере max{|z|,|v|} < 1 . Полученные соотношения, в свою очередь, позволили найти рекуррентные формулы для последовательностей производящих функций вида

{Ф2гш(Пг>, ем, z , v); i > 0 } , Пг> е Г, ем е {ет.ео}

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

2т

Теорема 5. Если АлТ- Л > 0 , где Т=£ Тг , то имеет место

г=1

предельное равенство Нт СМПГ>, ем, \ут) = 0 для всех (Пг>, /->00

Из теоремы 5 непосредственно следует, что условие ЬТ- /1 < О является необходимым для существования стационарного распределения в цепи Маркова {(П Л'., X1 , Хш,0; 1 > 0} .

Теорема 6. Если \т - Цт ^ 0 , то при любом состоянии (Г<г>, ей, , шт)бХ верно предельное равенство

Нт (Ж<г>, е<'>, ич, \ут) = 0 . /->00

Из теоремы 6 следует, что условие Хт - Цш < 0 также является необходимым для существования стационарного распределения в изучаемой цепи Маркова. Поэтому в дальнейшем полагали, что Х1Т- А < 0 и

Хщ- Цш < 0 .

Теорема 7. Пусть одновременно выполняются неравенства

ЛЯ -1\< о, Хт- (1т <0, Я1/|-|(Т-Т2ш-1)+ХтИт-|>1, тогда Нт С>,(ПГ>, ем, W|,

г—>оо

Wш) = 0 для всех (Г«, е«,

Таким образом, для существования стационарного распределения в рассматриваемой цепи Маркова необходимо, чтобы выполнялось еще и условие Х|/1|(Т-Т2т-1)+ < 1 . Следует отметить, что для

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

Р = Х|/1-,(Т-Т2га-1)+ ХтЦга'1 .

Теорема 8. Пусть Х|Т - 1\ < 0 . Тогда для марковской последовательности {(п .v,, ' - 0} с пространством состояний x имеем:

Нт Р( П = Пг>, VI = ем , = > 0 ; /->00

£ lim P( n = Пг>, Vi = ем , Xi,i = wi) = 1

T'ji.H'i l'-> CO

и, значит, в системе существует стационарное распределение по потоку Iii.

Из теорем 7 и 8 следует, что при некоторых ограничениях на

параметры Xm, Ць Цш и на выбор параметров Tr, r=l,2.....2т+1,

алгоритма управления математическое ожидание числа заявок в очереди по потоку Iii будет ограничено (это установлено при доказательстве теоремы 8). В то же время для векторной марковской последовательности {(Fi.Vi, Xu, Xm,0l i ^ 0} стационарное распределение может не существовать и М(Хш,0 неограниченно возрастает с течением времени.

Теорема 9. Для существования стационарного распределения цепи Маркова {(n,Vi, Х'.ь Xm.Dl i - 0} достаточно выполнения условий XlT- l\ < 0 , ХтТ- Im < 0.

Теорема 10. При XiT - Л < 0 , ХгаТ - /ш < 0 и T2m+i > Тгш-i + +(Х,гаТ- /m)(|im - km)"1 выполняются неравенства

ос 2m 1

lim M(xu) = I w,n limP(ri=n'),vi = eC),xu = wi)<+oo,

г—>oo w[=0 r=ls=0 >oo

oo 2m 1 oo

lim M(Xm,i) = Z wmS I I lim Р(Г,=Г(0, Vi = eW, xu = w,,

I->oo wm=0 r=ls=0 wj=0 /'->oo

Xmj = Wm) <+■»•

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

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

соответствующие определенным фазам работы светофора. Так, интервал Ti соответствовал зеленой фазе (фазе пропускания машин через перекресток) для потока П1 и красной фазе - для потока ГЬ ; интервалы продолжительности Т2 и Т4 соответствовали желтому сигналу по обоим потокам, когда ни один поток не обслуживался; интервал Тз соответствовал зеленой фазе по потоку ГЪ и красной - по потоку П| . При реализации алгоритма управления с учетом информации о наличии очереди и поступлении машин по потоку П1 вводилась дополнительная фаза длительности Т5 - интервал времени, соответствующий зеленому сигналу по потоку Ш и красному - по потоку П| . В зависимости от состояния случайной среды входной поток имитировался либо как поток отдельных машин (поток Пуассона), либо как поток пачек, возглавляемых "медленными" машинами (поток Бартлетта). Все случайные элементы имитационной модели формировались с помощью датчика псевдослучайных чисел с равномерным распределением на интервале (0,1).

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

y* = х2у2*)(х1+х2)^ ,

где yi* - оценка среднего времени пребывания на перекрестке произвольной машины потока П) , j=l,2. В качестве исходных параметров модели задавались: интенсивности поступления машин Xi, Х.2 , интенсивности пропускания машин через перекресток |ii , (i: , параметры потоков Бартлетта gj , qy , j=l,2, начальные очереди по потокам Х1.0 , Х2.0. длительности фаз светофора Тг, г=1,5 , параметры а , b , определяющие поведение случайной среды, точность г и надежность а оценивания основных характеристик системы, шаг Н контроля достижения заданной точности оценок с заданной надежностью, начальное состояние датчика ПСЧ, точность 8 оценивания длительности переходного процесса в системе после некоторого стандартного ее возмущения и число реализаций алгоритма за время одной инициации программы (всего 23 параметра). Выходными величинами являлись оценки у* среднего времени пребывания произвольной машины на. перекрестке, время tc наблюдения, необходимое для получения оценок с заданной точностью и надежностью, время tn продолжительности переходного процесса в системе, определяемое согласно некоторому критерию. Алгоритм реализован в виде программы на языке FORTRAN.

При моделировании "параметры потоков и системы выбирались так, чтобы выполнялись неравенства

>.iT-hiTi<0,

ЪТ - Ц2Т3 < 0 ,

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

р = max {pi,pz} ,

где pi = XiT^iTi)-' , р2 = ЪТХцгТз)"1 - загрузки по потокам П| и Пг соответственно. Все эксперименты проводились при значении надежности а = 0,9 . Параметры входных потоков, потоков насыщения и автомата-светофора выбирались так, чтобы загрузка системы принимала одно из четырех значений: р £ {0,3 ; 0,5 ; 0,7 ; 0,9} .

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

Л= I+fi(I-qd-1 ■

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

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

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

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

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

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

- при одной и той же загрузке наименьшей длительностью переходного процесса обладает система с входными потоками типа Пуассона; в "смесях" потоков Пуассона и Бартлетта длительность переходного процесса увеличивается, причем существенную роль играет соотношение параметров а и Ь, определяющих поведение случайной среды, а также средний размер пачки машин в потоке Бартлетта;

- наибольшей продолжительностью переходного процесса и обладают системы с входными потоками типа Бартлетта; и в этом случае с увеличением Лп величины 1п возрастают.

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

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

1. Впервые построены и проанализированы математические модели систем управления конфликтными потоками заявок, когда вероятностная структура входных потоков изменяется в динамике процесса управления.

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Федоткин М.А., Куделин А.Н. Статистическое моделирование и изучение переходного процесса циклического управления интенсивными потоками Бартлетта // Тезисы доклада республик, научной конференции "Математическое и программное обеспечение анализа данных".-БГУ, Минск, 1990.-е. 99.

2. Федоткин М.А., Куделин А.Н. Анализ и оптимизация переходного процесса управления интенсивными потоками Бартлетта в классе алгоритмов с поиском • разрыва // Тезисы доклада VII Белорусской зимней школы - семинара "Сети связи и сети ЭВМ как модели массового обслуживания".-Гродно,1991.-с. 125-126.

3. Федоткин М.А., Куделин А.Н. Изучение переходного процесса обслуживания при различных алгоритмах управления интенсивными потоками Бартлетта // Тезисы доклада IV Всесоюзного совещания "Распределенные автоматизированные системы массового обслуживания",- -Москва, Душанбе, 1991.-2 с.

4. Федоткин М.А., Куделин А.Н. Имитационное моделирование процессов обслуживания с переменной структурой // Тезисы доклада Всесоюзной конференции "Математическое и машинное моделирование".-ВТИ, Воронеж, 1991.-е. 142.

5. Куделин А.Н., Федоткин М.А. Компьютерное моделирование циклического дорожного трафика // Труды международной конфер.

"Компьютерный анализ данных и моделирование".-БГУ, Минск, 1995,-с. 138-143.

6. Куделин А.Н., Федоткин М.А. Построение математической модели циклического управления конфликтными потоками заявок в случайной среде.-ННГУ, Нижн. Новгород, 1995.-19 е.- Депонир. в ВИНИТИ 14.03.95, N 688-В95.

7. Куделин А.Н., Федоткин М.А. Анализ математической модели циклического управления конфликтными потоками заявок в случайной среде.-ННГУ, Нижн. Новгород, 1995.-16 е.- Депонир. в ВИНИТИ 06.06.95, N 1636-В95.

8. Куделин А.Н., Федоткин М.А. Управление конфликтными потоками в случайной среде по информации о наличии очереди.-ННГУ, Нижн.Новгород, 1996.-22 е.- Депонир. в ВИНИТИ 28.05.96, N 1717-В96

9. Куделин А.Н., Федоткин М.А. Предельные теоремы для систем управления потоками в случайной среде в классе алгоритмов с упреждением.-ННГУ, Нижн. Новгород, 1996.-40 е.- Депонир. в ВИНИТИ 02.08.96, N 2593-В96.

10. Куделин А.Н., Федоткин М.А. Анализ управляемых маркированных точечных процессов циклического дорожного трафика И Тезисы доклада XI Белорусской Межгосударственной зимней школы-семинара "Исследование сетей связи и компьютерных сетей методами теории массового обслуживания". - БГУ, Минск, 1995. - с. 72-73.