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

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

Любина Татьяна Викторовна

ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ДИНАМИЧЕСКИХ И АДАПТИВНЫХ ИО-СИСТЕМ С ВХОДЯЩИМ ММРР-ПОТОКОМ

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

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

1 7 ОКТ 2013

Томск-2013

005535065

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

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

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

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

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

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

Ведущая организация: Федеральное государственное бюджетное

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

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

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

Автореферат разослан 27 сентября 2013 г.

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

Скворцов

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

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

Актуальность работы. Математические модели систем массового обслуживания (СМО) с повторными вызовами (Retrial Queue Systems или RQ-системы) являются адекватными для описания телефонных сетей, локальных вычислительных сетей с протоколами случайного множественного доступа, широковещательных и мобильных сотовых радиосетей, технологических и транспортных систем и др. Исследованием RQ-систем занимаются J. R. Artalejo, В. D. Choi, Г. И. Фалин, И. И. Хомичков, А. Н. Дудин, А. А. Назаров, В. И. Клименок, В. А. Михайлов. Отличие RQ-систем от классических СМО в том, что заявки, пришедшие в систему и обнаружившие прибор занятым обслуживанием, не покидают систему, а переходят в источник повторных вызовов (ИПВ) для того, чтобы попытаться занять прибор в будущем.

Статические протоколы случайного доступа анализируются в работах

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

Для решения проблем потери информации и стабилизации функционирования RQ-систем предлагаются модификации протоколов случайного множественного доступа:

- динамические протоколы доступа, рассмотренные в работах И. И. Хомичкова, Ю. Д. Одышева, С. JI. Шохора и др. для простейшего входящего потока RQ-систем;

- адаптивные протоколы доступа, рассмотренные в работах R. L. Rivest,

B. А. Михайлова, Д. Ю. Кузнецова для систем с простейшим входящим потоком.

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

Показано, что модели простейшего потока в RQ-системах не адекватны реальным телекоммуникационным потокам, поэтому возникает задача исследования RQ-систем с коррелированным входящим потоком (например, MMPP, MAP). Описание ММРР-потока приведено в работах Б. В. Гнеденко, И. Н. Коваленко, А. Н. Дуди-на, С. В. Лопуховой, А. Е. Горбатенко. Исследованию потоков в локальных сетях посвящены работы JL Б. Богуславского, Д. В. Колоусова, Е. А. Лебедева, А. А. Че-чельницкого и др.

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

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

Целью диссертационной работы является исследование математических моделей динамических и адаптивных RQ-систем с входящим ММРР-потоком, а именно нахождение следующих вероятностных характеристик:

- пропускная способность RQ-систем;

- стационарное распределение вероятностей состояний прибора и значений цепи Маркова, управляющей ММРР-потоком;

- распределение вероятностей числа заявок в источнике повторных вызовов.

Научная новизна:

1. Впервые построены математические модели динамических и адаптивных Яр-систем с входящим ММРР-потоком, в том числе яр-системы без конфликтов и с конфликтами заявок.

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

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

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

5. Впервые показана асимптотическая эквивалентность динамических и адаптивных Яр-систем, что позволяет использовать результаты, полученные при исследовании динамических Яр-систем для нахождения распределения вероятностей числа заявок в ИПВ адаптивных Яр-систем.

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

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

1. Математические модели динамических и адаптивных ЯР-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок.

2. Методы исследования марковских динамических и адаптивных Яр-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок.

3. Методы исследования немарковских динамических и адаптивных Яр-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок.

4. Асимптотическая эквивалентность динамических и адаптивных ЯР-систем.

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

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

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

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

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

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

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

Апробация работы. Основные положения работы и отдельные её результаты докладывались и обсуждались на следующих научных конференциях:

1-4. VIII-XI Всероссийских научно-практических конференциях с международным участием «Информационные технологии и математическое моделирование», г. Анжеро-Судженск, 2009-2012 гг.

5-7. XIV-XV, XVII Всероссийских научно-практических конференциях «Научное творчество молодежи», г. Анжеро-Судженск, 2010-2011,2013 гг.

8-9. VIII, IX Российских конференциях с международным участием «Новые информационные технологии в исследованиях сложных структур», г. Томск, 2010, 2012 гг.

10. Международной научной конференции «Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей», г. Минск, 2011 г.

11. Российской научной конференции с участием зарубежных исследователей «Моделирование систем информатики», г. Новосибирск, 2011 г.

12. Международной научной конференции «Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей», г. Минск, 2013 г.

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

1. «Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи» (№ 11803) Аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009-2011 годы)» Министерства образования и науки Российской Федерации.

2. «Исследование адаптивных RQ-систем с коррелированными входящими потоками заявок» (№ 12-01-90810-мол_рф_нр) Российского фонда фундаментальных исследований.

Публикации. По результатам исследований автором опубликовано 19 печатных работ, в том числе 5 в изданиях, рекомендованных ВАК, 1 из них в журнале, включенном в международные базы цитирования SCOPUS и Web of Science, 3 в материалах зарубежных конференций.

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав, заключения и списка использованной литературы из 141 наименования. Общий объем диссертации составляет 163 страницы, в том числе основной текст - 149 страниц.

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

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

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

производящих функций.

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

В параграфах 1.1 и 1.2 исследованы математические модели марковской динамической RQ-системы М|М|1 без конфликтов и с конфликтами заявок, описан процесс их функционирования.

Состояние динамической RQ-системы определяется двумерной цепью Маркова {k(t),i(t)}, где i{t) - число заявок в ИПВ, a k(í) описывает состояние прибора следующим образом: к = 0, если прибор свободен, к = 1, если прибор занят обслуживанием.

Для распределения вероятностей P{k(t) = k,i(t) = i}= P(k,i,t) состояний рассматриваемых RQ-систем получены системы уравнений Колмогорова, которые запи-

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

ОО

0(к,х) = ^Гх'Р(к,1).

1=о

Решая систему уравнений для производящих функций, получены условия существования стационарного режима д ля динамических Л(3-систем (табл. 1):

_ Таблица 1

без конфликтов заявок с конфликтами заявок

Ч 1 -V

* ч 2 ^ 4 у ' N У

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

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

В параграфе 1.3 представлена к рассмотрению марковская динамическая RQ-система ММРР|М|1 с входящим ММРР-потоком заявок.

ММРР-поток заявок, определяется диагональной матрицей Л условных интен-сивностей ~Кп и матрицей Q инфинитезимальных характеристик qvn цепи Маркова п(/), управляющей ММРР-потоком.

Состояние системы в момент времени t определяется трёхмерной цепью Маркова {k(t),n(t),i(t)}, где /'(/) - число заявок в ИПВ, n(t) - значения цепи Маркова, управляющей ММРР-потоком, a k(t) определяет состояние прибора.

Для распределения вероятностей P(k,n,i) составлена система уравнений Колмогорова, которая решена методом производящих функций.

В результате метода производящих функций найдены выражения для G(0,x) и G(1,jc) . Далее для нахождения величины пропускной способности S применено предельное условие большой загрузки р t S.

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

В параграфе 1.4 рассмотрена динамическая RQ-система ММРР|М[1 с входящим ММРР-потоком и конфликтами заявок.

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

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

Теорема 1.2. Значение S пропускной способности динамической RQ-системы с входящим ММРР-потоком и конфликтами заявок равно значению корня уравнения

y(Ro(S) - Ri(S))E - 2£R(S), АЕ = 0, где вектор-строка Rk(S) - совместное распределение вероятностей состояний прибора и значений цепи Маркова, управляющей входящим ММРР-потоком, которое определяется равенствами

R0(S)= R{SA + (H + Y)I}{HI + 2(5A + YI)-Q}"1, Rl(s) =R{I- [S\ + (ц + Y)lp + 2(SA + Yl)- QV }

где R - стационарное распределение вероятностей значений цепи Маркова n{f),

определяемое системой RQ = 0, RE = 1.

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

Приведены примеры численных реализаций вероятностных характеристик немарковских динамических RQ-систем M|GI|1 с конфликтами заявок и MMPP|GI|1.

В параграфе 2.1 проведено допредельное исследование немарковской динамической RQ-системы M|GI|1.

Процесс {¿(/),/(i),z(0} изменения во времени состояний описанной системы является марковским, где ¿(/) - число заявок в ИПВ; z(t) - длина интервала от момента t до момента окончания обслуживания заявки, стоящей на приборе в момент времени Г, k(i) - определяет состояние прибора следующим образом: к-О, если прибор свободен, к = 1, если прибор занят обслуживанием. Компонента z(t) определяется только в те моменты, когда А(/)=1.

Введено обозначение р{k{t)= 0,/(г) = i}= К°>М) - вероятность того, что прибор в момент времени t свободен и в ИПВ находится i заявок, а Р{*(/■) = 1,/(f) = /,z(f) <z} = P(l,i,:,t) - вероятность того, что прибор в момент времени t занят, до конца обслуживания заявки, стоящей на приборе в момент времени /, осталось время меньшее, чем z и в ИПВ находится i заявок. Для стационарного распределения вероятностей p(o,i,t)= P(Q,i), P(Uz,0 = P(Uz) составлена система

уравнений Колмогорова, которую решаем методом производящих функций.

В результате получено аналитическое выражение для производящей функции распределения вероятностей P(i) числа заявок в ИПВ, стационарное распределение вероятностей состояний прибора и пропускная способность S данной RQ-системы.

Распределение вероятностей P(i) числа заявок в ИПВ определяется обратным преобразованием Фурье при переходе от производящих к характеристическим функциям.

В параграфе 2.2 рассмотрена немарковская динамическая RQ-система M|GI|1 с конфликтам» заявок. Исследование проведено аналогично методом производящих

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

В параграфе 2.3 исследована немарковская динамическая RQ-система MMPP|GI|1 с входящим ММРР-потоком. Для данной RQ-системы записана система уравнений Колмогорова в матричном виде:

LP(0,0)(Q_a)+Ä = 0,

oz

SP(U0) _ ЙРОДО) + р(1) Z;0)(Q _Л)+ p(0;0)Aß(z) + P(0,l)yß(z) = О,

dz 8z

5P(1'-'') - 5Р(1Д') - P(l, z, 0(Q - Л) + P(l, z, / -1 )Л + P(0, ;)Aß(z) + P(0, / + \)yB(z) = 0, dz 8z

исследование которой проведено методом производящих функций:

00 СО

G(0,jc) = ^У Р(0,/), G(1 ,z,x) = JV Р(1,*,0. /=о 1=0

Неизвестные вектор-функции G(0,x) и G(l,z,x) и вектор Р(0,0) найдены с помощью преобразования Лапласа матричного аргумента.

Определив значение вектора Р(0,0) и значения вектор-функций G(0,x) и

G(1,jc) = lim G(l,z,x), было получено аналитическое выражение для производящей

2—>00

функции числа i(t) заявок в источнике повторных вызовов.

Интерес представляет поведение распределений вероятностей числа заявок в ИПВ для рассматриваемой немарковской динамической RQ-системы MMPP|GI|1 с конфликтами заявок при различных распределениях времени обслуживания. В табл.2 приведены значения вероятностей Pv(i) распределений

?(/)= — f e~ju'h(u)du, когда среднее значение времени обслуживания равно еди-2л ¿-к

нице, у = 5, а матрицы А и Q имеют вид:

"0,2 0 0" -0,6 0,2 0,4

А = 0 0,5 0 . Q = ОД -0,4 0,3

0 0 1,0 0,1 0,3 -0,4

при различных распределениях времени обслуживания:

1) детерминированное обслуживание, при этом Д = 0, (V = 1);

2) гамма-распределение времени облуживания с параметрами а = Р = ц для случаев: ц = 5 (малая дисперсия П2 = 1/ц = 0,2; V = 2); ц = 1 (экспоненциальное распределение с дисперсией £>3=1; у = 3); ц = 0,2 (большая дисперсия Д,= 1/ц = 5 ; у = 4).

Таблица 2

i 0 1 2 3 4 5 6 7

Л( 0 0,407 0,162 0,118 0,085 0,062 0,045 0,033 0,024

P2(i) 0,394 0,152 0,114 0,085 0,064 0,048 0,036 0,027

Рз( 0 0,359 0,124 0,089 0,080 0,064 0,052 0,042 0,034

P4d) 0,297 0,068 0,059 0,051 0,046 0,042 0,038 0,034

Основной причиной различия полученных распределений является существенное различие значений величины дисперсии Д, времени обслуживания, значения которой составляют Д =0, =0,2, Оъ=\, £>4=5, при этом характеристики

(среднее значение av и дисперсия oj) числа заявок в ИПВ значительно различаются, а именно с ростом дисперсии времени обслуживания среднее значение и дисперсия числа заявок в ИПВ также возрастают.

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

Приведены примеры расчетов характеристик адаптивных RQ-систем, таких как М|М|1, М|М|1 с конфликтами заявок, ММРР|М|1, ММРР|М|1 с конфликтами заявок, для которых найдены значение S пропускной способности и величины у — основной характеристики динамической RQ-системы

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

В параграфе 3.2 и 3.3 выполнено исследование марковских адаптивных RQ-систем М|М|1 без конфликтов и с конфликтами заявок.

Состояние систем в момент времени t определяется трёхмерным процессом Маркова {k(t),i(t),T(t)}, где /(/) - число заявок в ИПВ; k(t) определяет состояние прибора следующим образом: к = 0, если прибор свободен, к = 1, если прибор занят обслуживанием; T(t) - состояния адаптера, которые с течением времени t меняются следующим образом: T(t + At) = T(t)-aAt, если k(t) = 0 и T(t + At) = T(t) + РД/, если k(t) = 1, где величины а > 0, Р > 0 - заданные параметры адаптера.

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

В параграфе 3.4 проведено исследование марковской адаптивной RQ-системы с входящим ММРР-потоком без конфликтов заявок. Для этого получена основная векторно-матричная система уравнений для частичных характеристических функций:

Н0(и„и2ХО-рЛ + аа21)+ F^^U-e'"' Pfr'JrU + H1(»1,H2)(e-2»'pA + |il)=0,

J ОЩ J OUJ

«2 u2

Н0(«„И2)рЛ-е"> + TI,(„,,„2XQ-РЛ-(ц + P«2)[) = 0,

J Ш] J 0«i

иг иг

исследование которой вьшолняется в предельном условии большой загрузки. Для выполнения исследования вводится обозначение s = S-p, предполагается, что s ->0 и в системе уравнений (3) выполняются замены р = S — г, щ= ewj , и2 = еи>2, Вк(щ,и2) = Fî.(wi,w2,c) . Доказана следующая теорема.

Теорема 3.3. Значение величины у и пропускной способности S адаптивной RQ-системы с входящим ММРР-потоком заявок определяется системой уравнений

yR0(s,y)E - SRj^/VE = О, aR0(s,y)E-PR1(5,y)E = 0, где а, Р - параметры адаптера, значения которых заданы, Rt(s,y) —распределение вероятностей состояний прибора и значений цепи Маркова, управляющей входящим ММРР-потоком, которое определяется равенствами

R0 (5, у) = nR{(n + y)l + 5Л - Q}"1, R, (s, y) = R jl - ц[(и + y)l + 5Л-Q]-1 j где R - стационарное распределение вероятностей значений цепи Маркова n(t), определяемое системой RQ = 0 и RE = 1.

Аналогичные исследования выполнены при исследовании адаптивной RQ-системы ММРР|М|1 с входящим ММРР-потоком и конфликтами заявок.

В параграфе 3.6 рассматривается немарковская адаптивная RQ-система MMPP|G1|1 с входящим ММРР-потоком заявок. Здесь состояние системы в момент времени t описывается процессом Маркова {k(t), :(t),n(t), i(t), T(t)\, где k(t) = 0,1 определяет состояния прибора; z{t) — остаточное время обслуживания заявок, стоящих на приборе в момент времени t; n{t) - значения цепи Маркова, управляющей ММРР-потоком; /(/) - число заявок в ИПВ; адаптер с течением времени t свои состояния T{t) меняет следующим образом: T(t + At) = T(t) - aAt, если k(t) = 0 и T(t + At) = T(t) + РД/, если k(t) = 1, где величины а > 0, Р > 0 - параметры адаптера, значения которых заданы.

Исследование проводилось в условии большой загрузки RQ-системы. В результате получена система уравнений для нахождения значений пропускной способности S и величины у, а также найдено распределение вероятностей Rjt(S',y) состояний

прибора и значений цепи Маркова, управляющей ММРР-потоком.

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

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

В результате имитационного моделирования адаптивной КС>-системы с простейшим входящим потоком и конфликтами заявок для следующих заданных входных параметров

А, = 0,440, ц = 1, а = 0,845 , Р = 1 было получено распределение вероятностей Ра (:') числа заявок в ИПВ. В табл. 3 приведены значения Ра(¡') и распределения вероятностей Рд(0 динамической

Кр-системы М|М|1 с конфликтами заявок с соответствующими входными параметрами:

X = 0,440 , ц = 1, у = 5 .

При данных параметрах адаптивной и динамической ШЗ-систем значение пропускной способности 5 составляет 0,458.

_Таблица 3

i 0 1 2 3 4 5 6 7

0,103 0,035 0,041 0,037 0,035 0,034 0,032 0,031

0,109 0,019 0,036 0,034 0,033 0,031 0,030 0,029

Область применимости аппроксимации характеристик адаптивной Яр-системы характеристиками динамической ЯС^-системы с указанным значением параметра у

определена с помощью расстояния Колмогорова Ä = тах

ад] = 0,028,

л=0

которое позволяет сделать вывод о том, что допредельное распределение вероятностей PA(i) числа заявок в ИПВ для динамической RQ-системы достаточно точно

аппроксимирует полученное распределение вероятностей Ра (г) для адаптивной RQ-системы.

В данном примере значение параметра входящего потока равно загрузке RQ-системы, т. к. ц = 1, а р = • Установлено, как ведет себя расстояние Колмогорова при различных значениях загрузки, для этого рассмотрена величина a = p/S. Это позволило сделать вывод о том, при какой загрузке, определяемой параметром а, характеристики, полученные аналитическими методами при исследовании динамической RQ-системы, наиболее близки к характеристикам адаптивной RQ-системы, найденным по результатам статистического анализа ее имитационной модели (табл. 4).

_ Таблица 4

а 0,900 0,850 0,800 0,700 0,600 0,500 0,400 0,200 0,100

Р 0,412 0,389 0,366 0,321 0,275 0,229 0,183 0,092 0,046

А 0,029 0,025 0,030 0,029 0,026 0,022 0,023 0,021 0,022

ст 0,012 0,010 0,011 0,009 0,008 0,006 0,004 0,004 0,004

Результаты, приведенные в табл. 4, показывают, что при изменении величины а имитационные результаты одинаково близки к допредельным. Расстояние Колмогорова для всех ситуаций не превышает 0,030, что говорит о применимости динамической аппроксимации адаптивных RQ-cиcтeм не только в условии большой загрузки, но и во всем спектре значений 0 < а < 1 загрузки системы.

В связи с тем, что величина среднеквадратического отклонения а в 3-5 раз меньше величины Д, можно утверждать, что найденные значения расстояний Колмогорова являются достаточно точными.

Далее проведен анализ имитационного моделирования адаптивной Яр-системы с входящим ММРР-потоком заявок с параметрами

'-0,7 0,4 0,3 4 '1 0 о4

ц = 1, а = 3,768, P = l, Q = 0,1 -0,4 0,3 , Л = 0 2 0

[0,4 0,5 -0,9; ,0 0

Таким параметрам аир соответствует параметр интенсивности обращения из ИПВ у = 3 динамической яр-системы с входящим ММРР-потоком.

Определено, при какой загрузке, определяемой параметром а, характеристики, полученные аналитическими методами при исследовании динамической Яр-системы ММРР|М|1, наиболее близки к характеристикам адаптивной Яр-системы ММРР|М|1, найденным по результатам анализа ее имитационной модели. Для этого рассмотрено поведение расстояния Колмогорова при различных значениях загрузки Яр-систем (табл. 5).

Таблица 5

а 0,900 0,800 0,700 0,600 0,500 0,400 0,300 0,200 0,100

Р 0,711 0,632 0,553 0,474 0,395 0,316 0,237 0,158 0,079

А 0,020 0,029 0,014 0,013 0,009 0,006 0,004 0,002 0,001

о 0,006 0,010 0,005 0,004 0,003 0,002 0,001 0,001 0,0002

Из табл. 5 видно, что при изменении значения а во всем спектре значений 0<а<1 имитационные результаты, определяющие функционирование адаптивной ГКЗ-системы, близки к допредельным, найденным в результате исследования динамической Яр-системы с указанным значением параметра у, кроме того при уменьшении а расстояние Колмогорова уменьшается, что также говорит о высокой точности динамической аппроксимации.

Величина среднеквадратического отклонения а в 3-5 раз меньше величины А, следовательно, найденные значения расстояний Колмогорова являются достаточно точными.

Далее проверяется точность имитационного моделирования. Для этого рассмотрена имитационная модель адаптивной Яр-системы с конфликтами заявок, в которой параметры выбраны таким образом, что разработанный программный комплекс моделирует динамическую яр-систему с конфликтами заявок, результаты которой сравниваются с допредельными результатами (табл. 6).

Таблица 6

а 0,900 0,850 0,800 0,700 0,600 0,500 0,400 0,200 0,100

Р 0,412 0,389 0,366 0,321 0,275 0,229 0,183 0,092 0,046

До 0,012 0,014 0,010 0,008 0,013 0,014 0,011 0,012 0,012

Расстояние Колмогорова AD при различных значениях а составляет менее

0,015, что подтверждает высокую точность имитационного моделирования.

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

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

Таблица 7

а 0,900 0,800 0,700 0,600 0,500 0,400 0,300 0,200 0,100

Р 0,711 0,632 0,553 0,474 0,395 0,316 0,237 0,158 0,079

До 0,013 0,014 0,010 0,008 0,005 0,003 0,001 0,0009 0,0004

Из табл. 7 видно, что расстояние Колмогорова Дв в зависимости от значений загрузки а меняется от 0,014 до 0,0004, что также подтверждает высокую точность имитационного моделирования.

В параграфе 4.2 описан комплекс проблемно-ориентированных программ расчета вероятностных характеристик адаптивных и динамических RQ-систем.

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

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

1. Любина Т. В. Исследование марковской динамической RQ-системы с конфликтами заявок / Т. В. Любина, А. А. Назаров // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. - № 3 (12). - С. 73-84. - 0,73 / 0,49 п. л.

2. Любина Т. В. Исследование немарковской модели компьютерной сети связи, управляемой динамическим протоколом доступа / Т. В. Любина, А. А. Назаров // Вестник Томского государственного университета. Управление, вычислительная техника н информатика. — 2012. — № 1 (18). — С. 16-27. — 0,73 / 0,52 п. л.

3. Любина Т. В. Исследование немарковской динамической RQ-системы с конфликтами заявок / Т. В. Любина, А. А. Назаров // Вестник Кемеровского государственного университета. - 2012. - № 1 (49). - С. 38-44. - 0,39 / 0,29 п. л.

4. Любина Т. В. Исследование динамической и адаптивной RQ-систем с входящим ММРР-потоком заявок / Т. В. Любина, А. А. Назаров // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2013. - № 3. - С. 104-112. - 0,36 / 0,27 п. л.

5. Любина Т. В. Немарковская динамическая RQ-система с входящим ММР-потоком заявок / Т. В. Любина, А. А. Назаров // Автоматика и телемеханика. - 2013. - № 7. - С. 89-101. - 0,79 / 0,52 п. л.

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

6. Любина Т. В. Исследование системы массового обслуживания М|М|1|ИПВ с конфликтами заявок, управляемой динамическим протоколом доступа / Т. В. Любина, А. А. Назаров // Информационные технологии и математическое моделирование (ИТММ-2009) : Материалы VIII Всероссийской научно-практической конференции с международным участием (13-14 ноября 2009 г.). — Томск: Изд-во Том. ун-та, 2009. — Ч. 1.-С. 65-68.-0,24/0,16 п. л.

7. Любина Т. В. Исследование системы массового обслуживания М|М|1[ИПВ с конфликтами заявок, управляемой адаптивным протоколом доступа / Т. В. Любина, А. А. Назаров // Теория вероятностей, математическая статистика и их приложения : сб. науч. ст. (материалы Междунар. конф., посвящ. 75-летию проф., д-ра физ.-мат. наук Г. А. Медведева, Минск, 22-25 февр. 2010 г.). Вып. 3 / редкол.: Н. Н. Труш (отв. ред.) [и др.]. - Минск : РИВ111, 2010. - С. 220-224. - 0,30 / 0,25 п. л.

8. Любина Т. В. Исследование динамической Ш^-системы с конфликтами заявок / Т. В. Любина, А. А. Назаров // Научное творчество молодежи: Материалы XIV Всероссийской научно-практической конференции (14-15 апреля 2010 г.). - Томск : Изд-во Том. ун-та, 2010.-Ч. 1.-С. 57-61.-0,31 /0,18п. л.

9. Любина Т. В. Аппроксимация допредельного распределения в динамической Яр-системе с конфликтами заявок / Т. В. Любина, А. А. Назаров // Новые информационные технологии в исследованиях сложных структур : тезисы докладов Восьмой Российской конференции с международным участием. - Томск : Изд-во НТЛ, 2010. -С. 38.-0,06/0,03 п. л.

10. Любина Т. В. Исследование немарковской динамической Л(3-системы / Т. В. Любина, А. А. Назаров // Информационные технологии и математическое моделирование (ИТММ-2010): Материалы IX Всероссийской научно-практической конференции с международным участием (19-20 ноября 2010 г.). - Томск : Изд-во Том. ун-та, 2010. - Ч. 1. - С. 28-33. - 0,36 / 0,25 п. л.

11. Любина Т. В. Исследование марковской динамической ЯО-системы с входящим ММР-потоком заявок / Т. В. Любина, А. А. Назаров // Массовое обслуживание: потоки, системы, сети : материалы междунар. науч. конф. «Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей», Минск, 31 янв. - 3 февр. 2011 г. Вып. 21 / редкол.: А. Н. Дудин (отв. ред.) [и др.]. - Минск: РИВШ, 2011. - С. 148-154.-0,42/0,30 п. л.

12. Любина Т. В. Распределение вероятностей числа заявок в ИПВ в немарковской модели компьютерной сети связи, управляемой динамическим протоколом доступа // Труды X международной ФАМЭТ'2011 конференции / под ред. О.Ю. Воробьева. - Красноярск : КГТЭИ, СФУ, 2011. - С. 219-223. - 0,30 / 0,15 п. л.

13. Любина Т. В. Нахождение распределения вероятностей числа заявок в ИПВ в немарковской динамической ЯС^-системе с конфликтами заявок / Т. В. Любина, А. А. Назаров // Научное творчество молодежи: материалы XV Всероссийской научно-практической конференции (28-29 апреля 2011 г.). — Томск : Изд-во Том. ун-та, 2011. - Ч. 1. - С. 20-24. - 0,29 / 0,16 п. л.

14. Любина Т. В. Исследование марковской динамической Яр-системы с входящим ММР-потоком заявок методом асимптотического анализа / Т. В. Любина, А. А. Назаров // Моделирование систем информатики. Российская научная конференция с участием зарубежных исследователей. Школа научной молодежи, 8-11 ноября 2011, Новосибирск.

15. Любина Т. В. Исследование адаптивной ЯС>-системы с входящим ММР-потоком заявок / Т. В. Любина, А. А. Назаров // Информационные технологии и математическое моделирование (ИТММ-2011): Материалы X Всероссийской научно-практической конференции с международным участием (25-26 ноября 2011 г.). -Томск: Изд-во Том. ун-та, 2011.-Ч. 1.-С. 157-160.-0,24/0,14 п. л.

16. Любина Т. В. Исследование адаптивной Ш^-системы с входящим ММРР-потоком методом асимптотического анализа / Т. В. Любина, А. А. Назаров // Новые информационные технологии в исследовании сложных структур: тезисы докладов Девятой Российской конференции с международным участием. - Томск : Изд-во НТЛ, 2012. - С. 93. - 0,06 / 0,04 п. л.

17. Любина Т. В. Исследование адаптивной ЯО-системы с входящим ММРР-потоком заявок методом асимптотического анализа / Т. В. Любина, А. А. Назаров // Информационные технологии и математическое моделирование (ИТММ-2012) : материалы XI Всерос. науч.-практ. конф. с международ, участием (г. Анжеро-

Судженск, 23-24 нояб. 2012 г.). - Кемерово : Практика, 2013. - Ч. 2. - С. 94-99. -0,36 / 0,21 п. л.

18. Любина Т. В. Исследование адаптивной Яр-системы с входящим ММРР-потоком и конфликтами заявок / Т. В. Любина, А. А. Назаров // Массовое обслуживание: потоки, системы, сети : материалы междунар. науч. конф. «Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей», Минск, 28-31 янв. 2013 г. Вып. 22 / редкол. : А. Н. Дудин (отв. ред.) [и др.]. - Минск : Изд. центр БГУ, 2013. - С. 91-96. -0,36 / 0,20 п. л.

19. Любина Т. В. Исследование марковской адаптивной Яр-системы с входящим МАР-потоком и конфликтами заявок / Т. В. Любина // Научное творчество молодежи : материалы XVII Всероссийской научно-практической конференции (25-26 апреля 2013 г.) [Электронный ресурс]. - Электрон, дан. (15,5 Мб). - Анжеро-Судженск, 2013.-Ч. 1.-С. 31-36.

Подписано в печать 23.09.2013 г. Формат А4/2. Ризография

Печ. л. 0,95. Тираж 120 экз. Заказ № 1083._

Отпечатано на участке оперативной полиграфии филиала федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Кемеровский государственный университет» в г. Анжеро-Судженске. 652470, Кемеровская область, г. Анжеро-Судженск, ул. Ленина, 8.

Национальный исследовательский Томский государственный университет

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

04201454556 ЛЮБИНА ТАТЬЯНА ВИКТОРОВНА

ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ДИНАМИЧЕСКИХ И АДАПТИВНЫХ КО-СИСТЕМ С ВХОДЯЩИМ ММРР-ПОТОКОМ

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

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

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

Томск - 2013

Содержание

Введение 4 Глава 1 Исследование математических моделей марковских динамических ИХ^-систем....................................................... 26

1.1 Исследование марковской динамической ЯС)-системы М|М| 1..... 26

1.2 Исследование марковской динамической ЯС>-системы М|М|1 с конфликтами заявок............................................................... 33

1.3 Исследование марковской динамической ИХ^-системы ММРР|М|1 с входящим ММРР-потоком заявок................................................ 38

1.4 Исследование марковской динамической ЯС>-системы ММРР|М|1 с

входящим ММРР-потоком и конфликтами заявок......................... 47

Резюме............................................................................... 56

Глава 2 Исследование математических моделей немарковских динамических Яр-систем.................................................... 57

2.1 Исследование немарковской динамической Б1С)-системы М|С1| 1... 57

2.2 Исследование немарковской динамической ЯС)-системы М|01| 1 с конфликтами заявок.............................................................. 64

2.3 Исследование немарковской динамической ИХ^-системы

ММРР|С1|1 с входящим ММРР-потоком.................................... 75

Резюме................................................................................ 89

Глава 3 Исследование математических моделей адаптивных И.С)-систем...................................................................... 90

3.1 Виртуальные интервалы между моментами обращения к прибору заявок из ИПВ и асимптотическая эквивалентность адаптивных и динамических ЯС)-систем............................................................ 91

3.2 Исследование марковской адаптивной ЯС>-системы М|М| 1......... 93

3.3 Исследование марковской адаптивной ЯС)-системы М|М|1 с конфликтами заявок................................................................... 99

3.4 Исследование марковской адаптивной ЯС)-системы ММРР|М|1 с

входящим ММРР-потоком.......................................................

, 106

3.5 Исследование марковской адаптивной ЯО-системы ММРР|М|1 с входящим ММРР-потоком и конфликтами заявок......................... 112

3.6 Исследование немарковской адаптивной 11С)-системы ММРР|С1|1 с

входящим ММРР-потоком заявок............................................. 119

Резюме................................................................................ 128

Глава 4 Численный анализ и комплекс проблемно-ориентированных программ для исследования ЯС)-систем с входящим ММРР-потоком....................................................... 129

4.1 Имитационное моделирование адаптивных ЯС)-систем и область применимости результатов в допредельной ситуации..................... 129

4.2 Комплекс проблемно-ориентированных программ расчета вероятностных характеристик динамических и адаптивных

ЯС^-систем............................................................................... 142

Резюме................................................................................. 146

Заключение..................................................................... 147

Список использованной литературы....................................... 150

Введение

С развитием и распространением компьютерных и телекоммуникационных сетей, транспортных и других задач растёт потребность в проведении исследований математических моделей сетей связи для увеличения их производительности, оптимального выбора сетевого оборудования, надёжности передачи и доставки требований, объема передаваемой информации. Поэтому возникла необходимость создания адекватных математических моделей, применимых к реальным телекоммуникационным системам [2, 3, 89].

Распространенной в исследованиях математических моделей сетей связи выступает теория массового обслуживания, результаты которой используются для значимых практических задач не только в области сетей связи, но и экономико-математического моделирования, автоматизированных систем управления, технологических систем и другого [10, 11, 23, 24, 31, 36, 140].

Первые работы по теории массового обслуживания А. К. Эрланга, например [123], были опубликованы в 1908-1922 гг. и посвящены анализу функционирования телефонных станций, а также задачам по теории систем массового обслуживания с отказами. Далее были опубликованы фундаментальные работы по теории массового обслуживания А. Н. Колмогоровым [133], А. Я. Хин-чиным [24, 100, 101].

Наряду с этими учеными большой вклад в развитие теории массового обслуживания внесли А. А. Боровков [10, 11], Б. В. Гнеденко [22-24], И.Н.Коваленко [23, 31], Дж. Кендалл [33], Л. Клейнрок [36], С. Пальм, Ф. Поллачек, Т. Л. Саати [88] и др.

В 70-е годы начинают исследоваться системы с повторными вызовами, которые получили название Retrial Queue Systems или RQ-системы [35, 120]. Их отличие от классических систем массового обслуживания в том, что заявки, пришедшие в систему и обнаружившие прибор, занятым обслуживанием, не покидают систему, а переходят в источник повторных вызовов для того, чтобы попытаться занять прибор в будущем. Наличие повторных попыток получить обслуживание является важнейшей чертой этих систем.

Практическими приложениями RQ-систем являются оценивание производительности и проектирование телефонных сетей, локальных вычислительных сетей с протоколами случайного множественного доступа, широковещательных радиосетей, мобильных сотовых радиосетей, технологических систем, транспортных систем и др. [4-8, 90, 91, 141]. Поэтому разработка методов нахождения аналитических выражений вероятностно-временных характеристик таких систем массового обслуживания является актуальной задачей.

Изучению систем с повторными вызовами посвящено большое число современных исследований [43, 76, 77, 95], в которых рассматриваются разные варианты RQ-систем. В монографии J. R. Artalejo и A. Gomez-Corral [116] приведено огромное количество ссылок на работы, посвященные RQ-системам, опубликованные за последние 20 лет.

Математическому моделированию сетей связи в виде RQ-систем посвящены работы J. R. Artalejo [113-115, 127], В. D. Choi [118, 119], Г. И. Фалина [124-126, 128, 129], И. И. Хомичкова [102-104], А. Н. Дудина [28, 29, 122], А. А. Назарова [72, 82], В. И. Клименок [121, 122], В. А. Михайлова [69-70], в которых исследуются основные вероятностно-временные характеристики [34].

В исследованиях С. Н. Степанова [93, 139] проводится оценка вероятностных характеристик моделей с повторными вызовами. Системы с повторными вызовами и приоритетным обслуживанием первичных заявок исследуются в работе П. П. Бочарова [13].

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

В [140] рассматривается модель спутниковой сети и методы планирования, позволяющие повысить пропускную способность, благодаря численному моделированию изучается среднее запаздывание.

Математические модели RQ-систем могут различаться конфигурацией (отсутствие конфликта заявок, конфликт заявок, реализация этапа оповещения

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

Для решения проблем с потерей информации в RQ-системах предлагаются следующие модификации протоколов случайного множественного доступа [73, 81], которые позволяют стабилизировать работу сетей связи:

- статические протоколы случайного доступа анализируются в работах А. Н. Туенбаевой [99], Е. А. Судыко, Н. М. Юревич, В. А. Вавилова [15, 16], И. А. Семеновой, А. А. Назарова [75, 78, 79, 84] и др., то есть параметр интенсивности обращения из источника повторных вызовов является постоянным и не зависит от состояний системы. В этих работах показано, что статические RQ-системы с конфликтами и оповещением о конфликтах нестационарны при любой сколь угодно малой загрузке;

- динамические протоколы доступа рассматриваются в работах И. И. Хомичкова, Ю. Д. Одышева, С. JL Шохора [76, 83, 104, 109, 110] и др. для простейшего входящего потока, конечного и бесконечного количества абонентских станций, позволяющие избежать явления бистабильности и обеспечить надежную доставку сообщений между абонентскими станциями;

- адаптивные протоколы доступа рассматриваются в работах R. L. Rivest [137], В. А. Михайлова [69], Д. Ю. Кузнецова и А. А. Назарова [27, 43, 44], в которых предлагаются их математические модели. В адаптивных сетях случайного доступа имеется специальное устройство, называемое адаптером, который по состояниям канала связи оценивает работу всей сети и меняет значения параметров протокола доступа в зависимости от полученных оценок. Самым известным адаптивным протоколом является синхронная ALOHA, управляемая алгоритмом Ривеста [136], в котором строится байесовская оценка числа абонентских станций сети с задолженностью. В [105] адаптацию протоколов случайного множественного доступа предлагается осуществлять автоматами с целесообразным поведением. В работе Д. Ю. Кузнецова [43] также предлагается подход для стабилизации неустойчивых сетей связи с помощью адаптера, в ка-

честве входящего потока заявок для своих моделей автор рассматривает простейший.

Особенностью протоколов случайного доступа является то, что для входящего потока не вводится изначальной строгой очерёдности. Каждая из заявок обращается к прибору, как только истекает ее время пребывания в источнике повторных вызовов. При этом не исключена возможность возникновения конфликта [96], если произойдёт наложение заявок. В этих ситуациях заявка передается в источник повторных вызовов, после чего вновь пытается занять прибор. Примером такой ситуации может служить радиосеть ALOHA [107, 108], которая была первой сетью, построенной на основе метода случайного множественного доступа. В таких сетях заявки, попавшие в конфликт, продолжают обслуживание в искаженном режиме и только после завершения подобного обслуживания передаются в источник повторных вызовов. Заявки, поступившие во время обслуживания искаженных заявок, также искажаются и остаются на приборе до завершения их обслуживания, после этого также переходят в источник повторных вызовов.

Исследование математических моделей сетей множественного доступа, управляемых протоколом ALOHA проводится в работах Г. И. Фалина [98], Б. С. Цыбакова [106] и др. В этих работах показана возможность возникновения бистабильности.

Заслуживают внимание модели, учитывающие интервалы недоступности прибора, то есть когда реализуется этап оповещения о конфликте [79] и полное исследование процессов функционирования прибора и источника повторных вызовов. В сети Ethernet реализуется протокол доступа с резервированием канала и оповещением о конфликте. Требованиями считаются запросы на резервирование, в течение которого и возможны конфликты. Оповещение о конфликте начинает осуществляться с момента наступления конфликта. Запросы, поступившие на этапах обслуживания и оповещения о конфликте, отправляются в источник повторных вызовов, не мешая текущим режимам на приборе. Исследования, посвященные данной теме, представлены в работах [117, 134, 135].

До 90-х годов, как правило, были изучены модели с пуассоновским потоком, но с развитием исследований систем массового обслуживания было доказано, что пуассоновский поток не адекватно описывает информационно-телекоммуникационные потоки [47-48]. В связи с этим возникла необходимость исследования RQ-систем в случае, когда входящий поток заявок является специальным потоком однородных событий [23]. В монографии А. Н. Дудина и

B. И. Клименок [29] специальные потоки названы коррелированными. Математические модели RQ-систем с коррелированными входящими потоками [20] более адекватно описывают настоящие телекоммуникационные сети.

В данной работе будем рассматривать следующие модели входящих потоков: ММРР-поток (Markov Modulate Poisson Process) и его частный случай -простейший поток.

ММРР-поток является частным случаем МАР-потока (Markovian Arrival Process) [25], который является более общей моделью ординарных потоков с дискретной компонентой. Описание ММРР-потока приводится в работах Б. В. Гнеденко, И. Н. Коваленко [23], А. Н. Дудина [28, 29], А. А. Назарова [85],

C. В. Лопуховой [49], А. Е. Горбатенко [26]. Исследованию МАР-потока посвящены работы [86, 111]. Системам массового обслуживания с входящим МАР-потоком посвящены работы [12, 14, 17, 18, 20, 37, 71, 112]. Исследованию потоков в локальных сетях посвящены работы Л. Б. Богуславского [9], A.A. Назарова и Д. В. Колоусова [48-40], Е. А. Лебедева и А. А. Чечельницкого [45, 46], а также [131, 137, 138].

Настоящая диссертационная работа посвящена исследованию математических моделей марковских и немарковских RQ-систем, управляемых динамическим и адаптивным протоколами множественного доступа [130], с входящим ММРР-потоком в ситуациях без конфликтов заявок и с конфликтами заявок. Такие системы в данной диссертации получили название динамических RQ-систем и адаптивных RQ-систем с входящим ММРР-потоком заявок.

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

грузки ЯС^-системы. Для получения результатов при исследовании адаптивных ИХ^-систем использовалось предельное условие большой загрузки системы. Допредельное исследование проводится с помощью имитационного моделирования.

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

Важным направлением является исследование ЯС)-систем, которые возникли для моделирования систем телефонии [132], но использование таких моделей также оказалось достаточно эффективным для изучения компьютерных сетей.

Марковские и немарковские адаптивные и динамические ЯС)-системы с коррелированными потоками, без конфликтов и с конфликтами заявок применяются при проектировании различных сетей и протоколов передачи данных.

Цель и задачи исследования. Целью данной работы является исследование математических моделей динамических и адаптивных И.С)-систем с входящим ММРР-потоком, а именно нахождение вероятностных характеристик, таких как:

- пропускная способность К.С)-систем;

- стационарное распределение вероятностей состояний прибора и значений цепи Маркова, управляющей ММРР-потоком;

- распределение вероятностей числа заявок в источнике повторных вы7

зовов.

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

1. Построение математических моделей динамических и адаптивных ЯС>-систем с входящим ММРР-потоком заявок.

2. Разработка методов нахождения вероятностных характеристик для марковских динамических ЯС^-систем с входящими простейшим и ММРР- потоками.

3. Разработка методов нахождения вероятностных характеристик для немарковских динамических ЯС>-систем с входящими простейшим и ММРР-потоками.

4. Разработка методов нахождения вероятностных характеристик для марковских и немарковских адаптивных Ж^-систем с входящими простейшим и ММРР- потоками.

5. Численный анализ вероятностных характеристик динамических и адаптивных ЯС)-систем с входящими простейшим и ММРР- потоками.

6. Разработка имитационной модели адаптивных Ж^-систем с входящими простейшим и ММРР- потоками.

Научная новизна:

1. Впервые построены математические модели динамических и адаптивных ЯС)-систем с входящим ММРР-потоком, в том числе ЯС)-системы без конфликтов и с конфликтами заявок.

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

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

4. Впервые выполнено исследование адаптивных Ж^-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок, в результате чего определены значения пропускной способности 8 и величины у - основной характеристики динамической ЯС)-системы, а также стационарного распределения вероятностей состояний прибора и значений цепи Маркова, управляющей ММРР-потоком.

5. Впервые показана асимптотическая эквивалентность динамических и адаптивных Ж^-систем, что позволяет использовать резул