Введение к работе
Актуальность работы. Математические модели систем массового обслуживания (СМО) с повторными вызовами (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-систем;
стационарное распределение вероятностей состояний прибора и значений цепи Маркова, управляющей ММРР-потоком;
распределение вероятностей числа заявок в источнике повторных вызовов.
Научная новизна:
-
Впервые построены математические модели динамических и адаптивных RQ-систем с входящим ММРР-потоком, в том числе RQ-системы без конфликтов и с конфликтами заявок.
-
Впервые выполнено исследование марковских динамических RQ-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок, а именно получены аналитические выражения для нахождения пропускной способности RQ-системы, стационарного распределения вероятностей состояний прибора и значений цепи Маркова, управляющей ММРР-потоком, распределения вероятностей числа заявок в ИПВ.
-
Впервые, используя метод дополнительной переменной, выполнено исследование немарковских динамических RQ-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок, а именно получены аналитические выражения для нахождения пропускной способности RQ-системы, стационарного распределения вероятностей состояний прибора и значений цепи Маркова, управляющей ММРР-потоком, распределения вероятностей числа заявок в ИПВ.
4. Впервые выполнено исследование адаптивных RQ-систем с входящим
ММРР-потоком без конфликтов и с конфликтами заявок, в результате чего определе
ны значения пропускной способности 5 и величины у - основной характеристики
динамической RQ-системы, а также стационарного распределения вероятностей со
стояний прибора и значений цепи Маркова, управляющей ММРР-потоком.
-
Впервые показана асимптотическая эквивалентность динамических и адаптивных RQ-систем, что позволяет использовать результаты, полученные при исследовании динамических RQ-систем для нахождения распределения вероятностей числа заявок в ИПВ адаптивных RQ-систем.
-
Методами имитационного моделирования установлена возможность аппроксимации характеристик адаптивных RQ-систем характеристиками динамической RQ-системы с указанным значением параметра у не только в условии большой загрузки, но и во всем спектре значений загрузки системы.
Положения и результаты, выносимые на защиту, состоят в следующем:
-
Математические модели динамических и адаптивных RQ-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок.
-
Методы исследования марковских динамических и адаптивных RQ-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок.
-
Методы исследования немарковских динамических и адаптивных RQ-систем с входящим ММРР-потоком без конфликтов и с конфликтами заявок.
-
Асимптотическая эквивалентность динамических и адаптивных RQ-систем.
-
Разработаны программы для вычисления полученных характеристик для динамических и адаптивных 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 гг.
-
Международной научной конференции «Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей», г. Минск, 2011 г.
-
Российской научной конференции с участием зарубежных исследователей «Моделирование систем информатики», г. Новосибирск, 2011 г.
12. Международной научной конференции «Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей», г. Минск, 2013 г.
Результаты, представленные в данной работе, были получены в рамках выполнения научных проектов:
-
«Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи» (№ 11803) Аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009-2011 годы)» Министерства образования и науки Российской Федерации.
-
«Исследование адаптивных RQ-систем с коррелированными входящими потоками заявок» (№ 12-01-90810-мол_рф_нр) Российского фонда фундаментальных исследований.
Публикации. По результатам исследований автором опубликовано 19 печатных работ, в том числе 5 в изданиях, рекомендованных ВАК, 1 из них в журнале, включенном в международные базы цитирования SCOPUS и Web of Science, 3 в материалах зарубежных конференций.
Структура и объем диссертации. Диссертация состоит из введения, четырёх глав, заключения и списка использованной литературы из 141 наименования. Общий объем диссертации составляет 163 страницы, в том числе основной текст - 149 страниц.
