автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Исследование математических моделей RQ-систем в условии большой загрузки

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

Фёдорова Екатерина Александровна

ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ИО-СИСТЕМ В УСЛОВИИ БОЛЬШОЙ ЗАГРУЗКИ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

005558010

Томск - 2015

005558010

Работа выполнена в федеральном государственном автономном образовательном учрежден™ высшего образования «Национальный исследовательский Томский государственный университет», на кафедре теории вероятностей и математической статистики.

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

Назаров Анатолий Андреевич

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

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

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

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Российский университет дружбы народов», г. Москва

Защита состоится 26 марта 2015 г. в 12:00 на заседании диссертационного совета Д 212.267.08, созданного на базе федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (корп. 2, ауд. 102).

С диссертацией можно ознакомиться в Научной библиотеке и на сайте федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский Томский государственный университет» www.tsu.ru.

Материалы по защите диссертации размещены на официальном сайте ТГУ:

http://www.tsu.ni/content/news/announcement_of_the_dissertationsJn_the_tsu.php

Автореферат разослан <о1/» января 2015 г.

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

Скворцов Алексей Владимирович

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

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

В связи с этим в теории массового обслуживания стали выделять новый класс СМО - системы с повторными вызовами (Retrial Queueing System или RQ-системы).

Возникновение моделей RQ-систем, прежде всего, связывают с работами американских ученых R. I. Wilkinson и J. W. Cohen в середине XX в. Большинство первых работ о системах с повторными вызовами были посвящены практическим задачам, возникающим в телефонных сетях, и описанию влияния эффекта повторных вызовов на производительность технических систем.

Первые подходы к математическому описанию систем с повторными вызовами были предприняты в 1970 г. G. Gosztony и A. Elldin. J. W. Cohen в своей работе предложил необходимые условия эргодичности систем, найденные при помощи усеченных методов. Кроме этого, вопросами эргодичности занимались N. Deul, Г. И. Фалин, F. С. Foster, Т. Hanschke, А. А. Назаров, L. I. Sennot и др. Наиболее полное описание RQ-систем и детальное их сравнение с классическими СМО было проведено учеными J. R. Artalejo, A. Gomez-Corral, Г. И. Фалин и J. G. С. Templeton и отражено в их монографиях, которые признаны фундаментальными в рассматриваемой области.

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

RQ-системы с входящими MAP и ВМАР-потоками активно исследуются уче-лымн белоруской школы В. И. Клименок, А. Н. Дудин, в.работах которых используются преимущественно матричные методы решения полученных систем уравнений. Кроме того, матричными методами исследования RQ-систем пользуются такие ученные М. F. Neuts, J. R. Artalejo, A. Gomez-Corral, J. E. Diamond, A. S. Alfa и др.

В рамках исследования систем массового обслуживания с повторными вызовами также большой интерес приобрела задача моделирования протоколов множественного доступа. Такие протоколы имеют место в сетях связи, когда на коммутационный узел приходится несколько абонентских станций (АС), посылающих сигналы. Очевидно, что могут возникать ситуации одновременной отправки данных несколькими АС, в результате чего возникают конфликты, искажающие или вовсе не позволяющие получить информацию. Поэтому каждая станция «прослушивает» канал на предмет его занятости, и если канал не свободен, то осуществляет случайную задержку, после которой снова пытается передать данные. Модели подобных протоколов были исследованы И. И. Хомичковым, А. А. Назаровым, В. А. Вавиловым, Д. Ю. Кузнецовым, Д. В. Колоусовым, Ю. Д. Одышевым, Е. А. Судыко, А. Н. Туенбае-вой, С. Л. Шохором и др.

Асимптотические и приближенные методы исследования Яр-систем развивались Г. И. Фалиным, В. В. Анисимовым и др. Исследования Яр-систем в условии большой и малой загрузки проводились Г. И. Фалиным, А. А^аш и В. В. Анисимовым. Кроме того, работы С. Н. Степанова посвящены исследованиям систем в условии экстремальной загрузки (интенсивность входящего потока стремиться к бесконечности или к нулю).

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

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

Цель и задачи исследования. Целью настоящей диссертации является развитие методов исследования систем Яр-систем в условии большой загрузки.

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

1. Развитие метода асимптотического анализа для исследования Яр-систем в условии большой загрузки.

2. Расширение области применимости метода асимптотического анализа в виде получения асимптотики второго порядка.

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

4. Разработка численных алгоритмов исследования рассматриваемых систем.

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

Научная новизна результатов, изложенных в диссертации:

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

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

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

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

Положения н результаты, выносимые на защиту, состоят в следующем:

1. Развитие метода асимптотического анализа в условии большой загрузки для исследования Яр-систем различной сложности.

2. Асимптотические характеристические функции распределения вероятностей числа заявок в ИПВ в яр-системах ММРР|М|1 и ММРР|С1|1.

3. Единый вид характеристических функций распределения вероятностей числа заявок в ИПВ в условии большой загрузки для всех исследуемых Яр-систем.

4. «Квазиточные» формулы вычисления первого и второго начальных моментов для Яр-системы с входящим ММРР-потоком и квазигеометрическая и гамма аппроксимации исследования Яр-систем.

5. Оригинальный комплекс программ, вычисляющий вероятностные характеристики исследуемых Яр-систем.

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

Результаты, полученные в работе, Имеют как теоретическое, так и практическое значения.

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

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

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

Достоверность полученных результатов подтверждается строгими математическими выкладками, проведенными в работе с использованием математического аппарата теории вероятностей и случайных процессов, интегрально-дифференциального исчисления, численных методов, а также согласованностью результатов диссертации в частных случаях с результатами, полученными ранее другими учеными (а именно, асимптотическая характеристическая функция распределения вероятностей числа заявок в ИПВ в RQ-системе M|GI|1, полученная в п. 1.2, в предельном переходе р|1 эквивалентна формуле, описанной в монографии Г.И. Фалина).

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

Связь работы с крупными научными проектами. Значительная часть результатов, представленных в данной работе, была получена в рамках выполнения следующих научных проектов: научный проект АВЦП «Развитие научного потенциала высшей школы (2009-2011)» Федерального агентства по образованию, проект № 4761 «Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи»; научно-исследовательская работа проектов в рамках госзадания Ми-нобрнауки РФ на проведение научных исследований в Томском государственном университете (2012-2013) «Разработка и исследование вероятностных, статистических и логических моделей компонентов интегрированных информационно-телекоммуникационных систем обработки, хранения, передачи и защиты информации» № 8.4055.2011; научно-исследовательская работа в рамках проектной части государственного задания в сфере научной деятельности Министерства образования и науки РФ .Nb 1,511.2014/К «Исследование математических моделей информационных потоков, компьютерных сетей, алгоритмов обработки и передачи данных» (2014-2016).

Апробация- работы. Основные положения работы и отдельные ее вопросы докладывались и обсуждались на следующих научных конференциях: Российская научная конференция с участием зарубежных исследователей. «Моделирование систем информатики (МСИ-20111). Школа научной молодежи», Новосибирск, 2011; X-XII Всероссийская научно-практическая конференция с международным участием имени А.Ф. Терпугова «Информационные технологии и математическое моделирование», Анжеро-Судженск, 2011-2013; IX Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Томск, 2012; Юбилейная 50 международная студенческая конференция «Студент и научно-технический прогресс», 2012; XVI-XVIII Всероссийская научно-практическая конференции «Научное творчество' молодежи», Анжеро-Судженск, 2012-2014; IV International Conference «Problems of Cybernetics and Informatics». Baku, Azerbaijan, 2012; Международная научная конференция «Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей» (22 белорусская зимняя школа-

семинар по теории массового обслуживания (BWWQ-2013)), Минск, 2013; Всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем», Москва, 2013; 1-И Всероссийская молодежная научная конференция «Математическое и программное обеспечение информационных, технических и экономических систем», Томск, 2013-2014; International Conference «Distributed computer and communication network: control, computation, communications», Москва, 2013; Международная научная конференция «Теория вероятностей, случайные процессы, математическая статистика и приложения», Минск, Республика Беларусь, 2014; 10 Российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур», Алтай, 2014; XIII Международная научно-практическая конференция с международным участием имени А.Ф. Терпугова «Информационные технологии и математическое моделирование», Анжеро-Судженск, 2014.

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

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

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

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

В первой главе предложено развитие метода асимптотического анализа в условии большой загрузки для исследования RQ-систем.

В параграфе 1.1 методом асимптотического анализа в условии большой загрузки исследуется RQ-система М|М|1, на вход которой поступает простейший поток заявок с параметром X, время обслуживания каждой заявки распределено по экспоненциальному закону1 с параметром jx, продолжительность задержки заявок в ИПВ имеет экспоненциальное распределение с параметром о. Процесс i(t) описывает число заявок в ИПВ, а ОД - определяет состояние прибора. P{k(t) = к, i(t) = /'} =P(k,i,t) — вероятность того, что прибор в момент времени / находится в состоянии Лив источнике повторных вызовов находится i заявок. Процесс {Щ), i(t)} изменения состояний данной системы во времени является марковским. Тогда ставится задача нахождения распределения вероятностей числа заявок в источнике повторных вызовов такой системы в стационарном режиме. Сформулирована и доказана следующая теорема о виде асимптотической характеристической функции (в условии большой загрузки pîl, где р = X / р) распределения вероятностей числа заявок в источнике повторных вызовов.

Теорема 1.1. Асимптотическая характеристическая функция числа заявок в

ц+о

( и

ИПВ в RQ-системе М|М|1 имеет вид h(u) = \l-j-■ характеристической

I i-p;

функции гамма-распределения с параметрами а = (ц + сг)/с и р = 1 - р.

В параграфе 1.2 предложенным методом исследуется ЯС>-система М]01[1, на вход которой поступает простейший поток заявок с параметром X, время обслуживания распределено по произвольному закону В(х), продолжительность задержки заявок в ИПВ имеет экспоненциальное распределение с параметром а. Процесс /"(/) описывает число заявок в ИПВ, г(/) - длина интервала от момента / до момента окончания обслуживания заявки, а к(1) - определяет состояние прибора. Тогда Р{К') = 0, !"(/) = »'} = Р(0,1,1) - вероятность того, что прибор свободен в момент времени I и в источнике повторных вызовов находится / заявок; а Р{Щ) = 1. »(О = ¿(0 < г} = Р( 1,1>,0 - вероятность того, что в момент времени * прибор занят, в источнике повторных вызовов находится / заявок и оставшееся время обслуживания меньше г. Процесс {£(/), /(/), изменения состояний данной системы во времени является марковским с переменным числом компонент. Ставится задача нахождения распределения вероятностей числа заявок в источнике повторных вызовов такой системы в стационарном режиме. Сформулирована и доказана следующая теорема о виде асимптотической характеристической функции распределения вероятностей числа заявок в источнике повторных вызовов в условии большой загрузки р| 1, где р = УЬ.

Теорема 1.2. Асимптотическая характеристическая функция числа заявок в

( ■ V1

ИПВ в ЯО-системе М|С1| 1 имеет вид Л(и) =1--—— характеристической функ-

I а-р)Р;

ции гамма-распределения с параметрами а = 1 + 2ЫаЬ2, р = 2Ь1 ГЬ2, где Ъ - среднее время обслуживания заявок, а Ь2 - момент второго порядка времени обслуживания.

В параграфе 13 исследуется Ж^-система ММРР|М|1, на вход которой поступает ММРР-поток с матрицей условных интенсивностей рX и матрицей инфи-нитезимальных характеристик О, время обслуживания распределено по экспоненциальному закону с параметром ц, продолжительность задержки заявок в ИПВ имеет экспоненциальное распределение с параметром а. Аналогично /(/) - случайный процесс, характеризующий число заявок в ИПВ, «(/) - цепь Маркова, управляющая ММРР-потоком, а Ц?) - определяет состояние прибора. Тогда = К /(') = /, и(/) = «} = Р(к,1,п,{) - вероятность того, что прибор в момент времени г находится в состоянии к, управляющая М\*РР-11отоком цепь Маркова в состоянии п ив источнике повторных вызовов находится / заявок. Трехмерный процесс {£(/), /(/), л(/)} изменения состояний данной системы во времени является марковским. Ставится задача нахождения распределения вероятностей числа заявок в источнике повторных вызовов Яр-системы в стационарном режиме. Сформулирована и доказана следующая теорема.

Теорема 13. Асимптотическая характеристическая функция числа заявок в ИПВ

в Яр-системе ММРР|М|1 имеет вид = характеристической функ-

ции гамма-распределения с параметрами а = 1 + цр/сг, Р = ц(УХ£ - цУЕ + где Е - единичный векгор-столбец, а вектор V является решением неоднородной системы У<2 = Я(д1 - X).

В параграфе 1.4 рассматривается Яр-система ММРР|С1|1, на вход которой поступает ММРР-поток с матрицей условных интенсивностей рХ и матрицей инфини-

тезимальных характеристик Q, время обслуживания распределено по произвольному закону В(х), продолжительность задержки заявок в ИПВ имеет экспоненциальное распределение с параметром ст. Процесс /(/) характеризует число заявок в ИПВ, n(t) - цепь Маркова, управляющая ММРР-потоком, г(/) - оставшееся время обслуживания, a k(t) - определяет состояние прибора. Тогда P{k(i) = 0, n(t) = п, i(t) = /} = P(0,n,i,t) -вероятность того, что прибор свободен в момент времени г, управляющая ММРР-потоком цепь Маркова находится в состоянии пив источнике повторных вызовов находится i заявок; a P{k(t) = 1, n{t) = п, i{t) = i, z(t) < z) = P(l,n,i,z,t) - вероятность того, что в момент времени t прибор занят, управляющая ММРР-потоком цепь Маркова - в состоянии и, в источнике повторных вызовов находится / заявок и оставшееся время обслуживания меньше г. Случайный процесс {k(t), n(t), ;(/), z(i)} изменения состояний данной системы во времени является многомерным марковским с переменным числом компонент. Ставится задача нахождения стационарного распределения вероятностей числа заявок в источнике повторных вызовов Яр-системы. Доказана следующая теорема.

Теорема 1.4. Асимптотическая характеристическая функция числа заявок в

г

ИПВ в RQ-системе MMPP|GI|1 имеет вид й(и)= 1 —

J"

(1-р)Р

характеристической

функции гамма-распределения с параметрами (3 =

V5i£--VE

Ъ 26

. а = 1 +

Ьо'

в которых вектор V является решением неоднородной системы VQ

где I - единичная матрица.

Для всех исследуемых систем проведено численное сравнение допредельных и асимптотических распределений при различных значениях параметров системы. Принимая приемлемым во всей работе значение погрешности менее 5%, был сделан вывод, что метод асимптотического анализа в условии большой загрузки имеет область применимости р > 0,95.

Во второй главе предлагается расширение области, применимости исследований1 в:Ьвде: разработки метода асимптотического анализа второго порядка для исследования Яр-систем в условии большой загрузки.

В параграфе 2.1 проводится асимптотический анализ второго порядка ЯР-системы М|М|1. Приняты обозначения, аналогичные параграфу 1.1. Сформулирована и доказана следующая теорема.

Теорема 2.1. Асимптотическая характеристическая функция второго порядка распределения вероятностей числа заявок в ИПВ в Яр-системе М|М|1 имеет вид:

у» и-р; |1-р 2

1-/

1-р

1+(1-Р)

-J^+JiJl-J^Liji + rij 1-Р о ( 1-pJ U J

1-

JU 1-р

В параграфе 2.2 предложенньш методом исследуется Яр-система М|С1|1. Приняты обозначения, аналогичные параграфу 1.2. Доказана следующая теорема.

Теорема 2.2. Асимптотическая характеристическая функция второго порядка распределения вероятностей числа заявок в ИПВ в яр-системе М|С1|1 имеет вид:

й,(и)= 1-

(1-р)р

1+(1-рШ

где функция

си= |1-

ш. р

-I

2 6,

у'аб 2 ]Ь Ь,

<т 6

1 + 2 <зЪ

ь, ь.

46 6б3

464

А.+

462 663

¿У,

46

а параметры определяются а = I + 1Ь/аЬ2, Р = 2Ь2/Ь2.

В параграфе 23 рассматривается Яр-система ММРР|М|1. Проведено исследование системы предложенным методом. Сформулирована и доказана следующая теорема о виде асимптотической характеристической функции второго порядка распределения вероятностей числа заявок в ИПВ.

Теорема 2.3. Асимптотическая характеристическая функция второго порядка распределения вероятностей числа заявок в ИПВ в Яр-системе ММРР|М|1 имеет вид

А,(и)= 1-

(1-р)Р,

1 + (1-р)

]ч 1-р

1-р

УЬ-] /

<У)

ь ОУ-Р)

4У

где а = 1 + цр/о, р = ц(УХ£ - цУЕ + (д) 1, а вектор V является решением неоднородной системы У<2 = ЩцГ-Я.), функция а(и>) определяется выражением:

• Р

1-^

-уи>-

(2УХ£-цУЕ)

Н.

(2УХ£-цУЕ)

Ц ст V о\ Р ) а

а постоянная 6 = цУЕ +УД^-цЕ)- —, где вектор V! является решением неоднородной системы У,Р = - Я - -(Я! + цЯ) - (V*. - цУ).

Р 2

В параграфе 2.4 рассматривается Яр-система ММРР|01|1. Приняты обозначения, аналогичные параграфу 1.4. Сформулирована и доказана следующая теорема.

Теорема 2.4. Асимптотическая характеристическая функция второго порядка распределения вероятностей числа заявок в ИПВ в Яр-системе ММРР|С1|1 имеет вид

J»

(1-P)ß

l + (l-p)

i-p

o(y) 0 0>-P)

dy

где a = l + —, ß = ab

b\VkE--V Е + Лг l b 2b3

неоднородной системы VQ = R| I -

, в которых вектор V является решением

X. , функция с(и') определяется выражением:

<-H'-f f

2--

р стб Ь

где параметры а и ß определяются равенствами (2.71), постоянные 6 и т| равны:

5 = |- + 2bV)uE-VE+A-\2 2Ь

Ь Ь.

6-Ü 2 Ь

_L 6Ь~

4 Ь1

+ fcV1£-i)VlkE,

1

1

г) = 5 — + — + 6 VE - — —— VE—— +

1

4стй

2 26 ß 2сг oß 2а

а вектор Vi является решением неоднородной системы

Для всех исследуемых систем проведенное численное сравнение допредельных и асимптотических распределений при различных значениях параметров системы показало, что метод асимптотического анализа второго порядка применим при значениях загрузки р > 0,8, что указывает на увеличение области применимости метода в 4 раза, по сравнению с результатами главы 1.

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

В параграфе 3.1 исследуются системы М|М|1 и ММРР|М[1 методом начальных моментов. В результате; проведенного исследования получены формулы для вычисления начальных моментов первого и второго порядков распределения вероятностей числа заявок в ИПВ.

В параграфе 3.1.1 были найдены начальные моменты первого и второго порядков распределения вероятностей числа заявок в источнике повторных вызовов в RQ-системе М|М| 1, которые имеют вид:

' 'ü + I

d=-

(1-РГ

1 + p+ü + 2p*ü + p' ü CS (J lo

2\

В параграфе 3.1.2 метод моментов был применен к RQ-cиcтeмe ММРР|М|1. {Ио, Нц} — двумерное совместное стационарное распределение вероятностей состояний ММРР-потока и состояний прибора, для которых выполняются равенства:

Обозначив т, = — }-1--

ди

12

(кв+к,)0=о,

К0Е + Я,Е = 1.

. .2д211{к,и) и йк =J --

где к —1,2, тогда ма-

5м2

тематическое ожидание числа заявок в ИГГВ вычисляется как т - (гп0 + т,)Е = тЕ, а второй момент распределения вероятностей числа заявок в ИПВ вычисляется как (1 = (с!0 +<1,)Е = с!Е. Были получены системы уравнений для определения векторов

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

ГИоЕ = 1-р, {к,Е = р.

С помощью описанных выше уравнений однозначно вектора Ио и К] определить нельзя. В связи с этим было предложено Ко и К] определять следующим образом:

[К0 = (1-р)Я,

1»,=рК.

Проведенное численное сравнение полученных моментов с допредельными, вычисленными с помощью численного алгоритма, описанного в главе 4, показало, что такие моменты достаточно близки к точным (относительная погрешность менее 5%) для широкого спектра значений параметров системы, что позволило их назвать «квазиточными» моментами.

В параграфе 3.2 описывается гамма аппроксимация распределения вероятностей числа заявок в ИПВ в К(3-системах. Метод гамма аппроксимации распределения вероятностей />(/) числа заявок в ИПВ заключается в построении аппроксимирующего дискретного аналога гамма-распределения £?(/), параметры которого вычислены путем приравнивания моментов первого и второго порядков распределений Р(/) и С(1). То есть параметры гамма-распределения аир выражаются через математическое ожидание И дисперсию распределения />(/) следующим образом: •

а = Л/2{¡(О}/£>{!'(/)} и р = Л/{1(0}/О{'(0}-где А/{/(/)} - математическое ожидание, а £>{/(*)} - дисперсия распределения вероятностей Р(г).

В параграфе 33 описана квазигеометрическая аппроксимация распределения вероятностей числа заявок в ИПВ в 11(3-системах.

Определение. Квазигеометрическим распределением дефекта 1 называют такое дискретное распределение вероятностей К^О, Для которого выполняется равенство

[а-Л,Х1-б)5'Л при г > 1,

[/>„ при / = 0.

Метод квазигеометрической аппроксимации распределения вероятностей Р(/) числа заявок в ИПВ заключается в построении аппроксимирующего квазигеометрического распределения £#(/), параметры которого вычислены путем приравнивания моментов первого и второго порядков распределений Р(1) и

То есть параметры р„ и 5 распределения определяются через моменты первого и второго порядков следующим образом:

8 = -

и = 1 - (1 - 5)М{;'(/)},

2- А/{/(/)} + £>{/(/)}

где М{/'(<)} - математическое ожидание, а Д{/(0} — дисперсия распределения вероятностей Р(г).

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

Значения параметров системы 0 = 0,1 а = 0,5 а = 1 о = 2 а =10

Р = 0,1 те) те) те) Кф) АШ

Р = 0,3 Ыг) КяИ)

Р = 0,5 те

Р = 0,8 а о СО) сад те) те

Р = 0,9 <7(0 СО) С(/-) ао те)

р = 0,95 С(/) сад СО) сад садите)

В четвертой главе описан комплекс программ, реализующий численные алгоритмы исследования рассматриваемых систем (в том числе рекуррентный алгоритм и «мегаматричный» метод вычисления распределения вероятностей числа заявок в ИПВ в Яр-системе ММРР|М|1), а также программы, реализующие асимптотические методы, предложенные в главах 1-3.

В заключении сформулированы основные результаты и выводы диссертационной работы.

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

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

1. Назаров, А. А. Исследование Яр-системы ММРР|М|1 методом асимптотического анализа в условии большой загрузки / А. А. Назаров, Е. А. Моисеева (Фёдорова) // Известия Томского политехнического универаггета. - 2013. - Т. 322, № 2. -С. 19-23.-0.58/0.29 пл.

2. Моисеева (Фёдорова), Е. А. Исследование Яр-системы ММРР|С1|1 методом асимптотического анализа / Е. А. Моисеева, А. А. Назаров // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2013. - № 4 (25). - С. 84-94. - 0.87 / 0.44 пл.

3. Назаров А. А., Исследование Яр-системы ММРР|01|1 методом асимптотического анализа второго порядка в условии большой загрузки / А. А. Назаров, Е. А. Фёдорова //. Известия Томского политехнического университета. - 2014. -Т. 325, № 5. - С. 6-15. - 1.16 / 0.58 пл.

4. Фёдорова Е. А. Вычисление моментов в Яр-системе ММРР|М| 1 / Е. А. Фёдорова // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2014. - № 4 (29). - С. 41-50. - 1.26 пл.

5. Fedorova, E. Quasi-geometric and gamma approximation for retrial queueing systems / E. Fedorova // A. Dudin et al (Eds.): Information Technologies and Mathematical Modelling. - CCIS 487. - Springer International Publishing Switzerland, 2014. - P. 123136. - 0.94 пл. (Входит в базу цитирования Scopus)

Публикации в других научных изданиях:

6. Moiseeva (Fedorova), Е. Asymptotic Analysis of RQ-systems M|M|1 on Heavy Load Condition / E. Moiseeva, A. Nazarov // Problems of Cybernetics and Informatics : Proceedings of the IV International Conference, September 12-14, Baku, Azerbaijan. -Baku, 2012. - P. 164-166.-0.35 / 0.17 п.л. (Входит в базы цитирования Scopus и WoS)

7. Моисеева (Фёдорова), Е. А. Численное исследование RQ-системы М|М|1 в условии большой загрузки / Е. А. Моисеева, А. А. Назаров // Информационные технологии и математическое моделирование (ИТММ-2011) : материалы X Всероссийской научно-практической конференции с международным участием : в 2 ч. - Томск : Изд-во Том. ун-та, 2011.-Ч. 1.-С. 160-164.-0.31/0.16 п.л.

8. Моисеева (Фёдорова), Е. А. Численное исследование RQ-системы ММРР|М|1 / Е. А. Моисеева // Студент и научно-технический прогресс : Математика : материалы юбилейной 50 международной студенческой конференции. - Новосибирск : Новосиб. гос. ун-т, 2012. - С. 194-195.-0.12 пл.

9. Моисеева (Фёдорова), Е. А. Асимптотический анализ RQ-системы ММРР|М|1 в условии большой загрузки / Е. А. Моисеева // Технологии Microsoft в теории и практике программирования : сборник трудов IX Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. - Томск, 2012.-С. 96-98.-0.35 пл.

10. Моисеева (Фёдорова), Е. А. Асимптотический анализ RQ-системы МАР|М|1 в условии большой загрузки [Электронный ресурс] / Е. А. Моисеева // Научное творчество молодежи : материалы XVI Всероссийской научно-практической конференции: в 2 ч. - Анжеро-Судженск, 2012.-1 эл. опт. диск (CD-R). - Ч. 2. - С. 38-41.-0.25 пл.

11. Моисеева (Фёдорова), Е. А. Анализ результатов исследования RQ-системы M|GI|1 / Е. А. Моисеева // Информационные технологии и математическое модели-

• рование (ИТММ-2012) : материалы XI Всероссийской научно-практической конференции с международным участием : в 2 ч. - Кемерово: Практика, 2012. - Ч. 2. - С. 104-109.-038 пл.

12. Назаров, А. А. Исследование RQ -системы M|GI|I методом асимптотического анализа в условии большой загрузки / А. А. Назаров, Е. А. Моисеева (Фёдорова) // Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей : материалы международной научной конференции (22 белорусская зимняя школа-семинар по ТМО (BWWQ-2013)), 22. - Минск: Издательский центр БГУ, 2013. - С. 106-113. - 0.46 / 0.23 пл.

13. Моисеева (Фёдорова), Е. А. Асимптотический анализ RQ-системы MAP|GI|1 в условии большой загрузки [Электронный ресурс] / Е. А. Моисеева // Научное творчество молодежи : материалы XVII Всероссийской научно-практической конференции: в 2 ч. - Анжеро-Судженск, 2013.-1 эл. опт. диск (CD-R). - Ч. 1. - С. 40-44.-0.31 пл.

14. Моисеева (Фёдорова), Е. А. Моделирование телекоммуникационных процессов методами RQ-систем / Е. А. Моисеева // Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных

систем : материалы всероссийской конференции с международным участием. - Москва : РУДН, 2013. - С. 36-38. - 0.17 пл.

15. Моисеева (Фёдорова), Е. А. Исследование RQ-системы M|GI|1 в допредельной ситуации / Е. А. Моисеева // Математическое и программное обеспечение информационных, технических и экономических систем : материалы I Всероссийской молодежной научной конференции. - Томск : ИД Том. гос. ун-та, 2013. - С 116-121 -0.38 п.л. (Труды Томского государственного университета. Серия физ.-мат. Т. 288)

16. Назаров, А. А. Исследование RQ-систем в условии большой загрузки / А. А. Назаров, Е. А. Моисеева (Фёдорова) // Proceedings of International Conference «Distributed computer and communication network : control, computation, communications». - M. : Техносфера, 2013. - С. 448^55. - 0.50 / 0.25 п.л.

17. Назаров, А. А. Метод асимптотического анализа в условии большой загрузки 2-го порядка на примере исследования RQ-системы М|М|1 / А. А. Назаров, Е. А. Фёдорова // Информационные технологии и математическое моделирование (ИТММ-2013) : материалы XII всероссийской научно-практической конференции с международным участием им. А.Ф. Терпугова : в 2 ч. - Томск : Изд-во Том. ун-та 2013. - Ч. 2. - С. 59-65. - 0.43 / 0.22 пл.

18. Фёдорова, Е. А. Квазигеометрическая аппроксимация в RQ-системы M|GI|1 / Е. А. Фёдорова // Научное творчество молодежи. Математика. Информатика : материалы XVIII Всероссийской научно-практической конференции : в 2 ч. - Томск : Изд-во Том. ун-та,2014.-Ч.1.-С. 89-93.-0.31 пл.

19. Fedorova, Е. Retrial Queueing System M|GI|1 researching by means of the second-order asymptotic analysis method under a heavy load condition / E. Fedorova, A. Nazarov // Proceedings of the 3d International conference on application of Information and communication technology and statistics in economy and education (ICAICTSEE -2013) / University of National and World Economy, Sofia, Bulgaria. - Sofia, 2014. - P 510-518.-0.78/0.39 пл.

20. Фёдорова, E. А. Численный анализ результатов исследования RQ-систем методом асимптотического анализа второго порядка в условии большой загрузки / Е. А. Фёдорова, А. А. Назаров // Новые информационные технологии в исследовании сложных структур материалы 10 Российской конференции с международным участием. - Томск : ИД Том. гос. ун-та, 2014. - С. 108-109. - 0.23 / 0.12 п.л.

21. Фёдорова, Е. А. Метод моментов для RQ-системы М|М|1 / Е. А. Фёдорова// Математическое и программное обеспечение информационных, технических и экономических систем: материалы II Всероссийской молодежной научной конференции. - Томск : ИД Том. гос. ун-та, 2014. - С. 137-142. - (Труды Томского государственного университета. Серия физ.-мат. Т. 295). - 0.38 пл.

22. Назаров, А. А. Гамма-аппроксимация в RQ-системе M|GI|1 / А. А. Назаров, Е. А. Фёдорова // Теория вероятностей, математическая статистика и их приложения : сборник научных статей. - Минск : РИВШ, 2014. - С. 165-170. - 0.70 / 0.35 пл.

23. Фёдорова, Е. А. Квазигеометрическая и гамма аппроксимации в RQ-системе ММРР|М|1. / Е. А. Фёдорова, А. А. Назаров // Информационные технологии и математическое моделирование (ИТММ-2014) : материалы XIII Международной научно-практической им. А.Ф. Терпугова : в 3 ч. - Томск : Изд-во Том. ун-та, 2014. -Ч. 2. - С. 207-212. -0.38/0.19 п.л.

Подписано в печать 19.01.2015 г. Формат А4/2. Ризография Печ. л. 0,85. Тираж 100 экз. Заказ № 02/05-13 Отпечатано в ООО «Позитив-НБ» 634050 г. Томск, пр. Ленина 34а