Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Исследование математических моделей динамических и адаптивных RQ-систем с входящим ММРР-потоком Любина, Татьяна Викторовна

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Любина, Татьяна Викторовна. Исследование математических моделей динамических и адаптивных RQ-систем с входящим ММРР-потоком : диссертация ... кандидата физико-математических наук : 05.13.18 / Любина Татьяна Викторовна; [Место защиты: Нац. исслед. Том. гос. ун-т].- Томск, 2013.- 163 с.: ил. РГБ ОД, 61 14-1/382

Введение к работе


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

^-0,7 0,4 0,3 Л (\ 0 0\

їх = 1, а = 3,768, р = 1, Q

0,1 -0,4 0,3 0,4 0,5 -0,9,

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

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

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

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

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

Таблица 6

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

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

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

-- 0,028,

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

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

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

Х = 0,440, [1 = 1, 7 = 5.
При данных параметрах адаптивной и динамической RQ-систем значение про
пускной способности 5составляет 0,458.
Таблица 3

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

^{Ра(п)-РдЩ

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

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

аппроксимирует полученное распределение вероятностей Pa(J) для адаптивной

RQ-системы.

В данном примере значение параметра входящего потока равно загрузке RQ-системы, т. к. ц, = 1, а р = ?i/|i . Установлено, как ведет себя расстояние Колмогорова при различных значениях загрузки, для этого рассмотрена величина а=р/5.

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожие диссертации на Исследование математических моделей динамических и адаптивных RQ-систем с входящим ММРР-потоком