Исследование моделей RQ-систем с конфликтами заявок в условии большой задержки

Судыко, Елена Александровна

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

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

кандидата физико-математических наук: Судыко, Елена Александровна
город: Томск
год: 2011
специальность ВАК РФ: 05.13.18
цена: 450 рублей

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

Автореферат диссертации по теме "Исследование моделей RQ-систем с конфликтами заявок в условии большой задержки"

005003560

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

Судыко Елена Александровна

ИССЛЕДОВАНИЕ МОДЕЛЕЙ ШЗ-СИСТЕМ С КОНФЛИКТАМИ ЗАЯВОК В УСЛОВИИ БОЛЬШОЙ ЗАДЕРЖКИ

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

2 4 НОЯ 2011

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

Томск-2011

005003560

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

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

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

Официальные оппоненты: доктор физико-математических наук,

профессор Змеев Олег Алексеевич

кандидат физико-математических наук, доцент Вавилов Вячеслав Анатольевич

Ведущая организация: Балтийский федеральный университет имени

Иммануила Канта, г. Калининград

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

Отзывы на автореферат (в двух экземплярах), заверенные гербовой печатью организации, просим направлять по адресу: 634050, г. Томск, пр. Ленина, 36, ученому секретарю ТГУ Буровой Н.Ю.

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

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

Ученый секретарь

диссертационного совета

доктор технических наук, профессор

А.В. Скворцов

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

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

RQ-системы. Одни из таких моделей, используемые для анализа и исследования процессов функционирования телекоммуникационных и компьютерных систем - модели с повторной очередью (retrial queueing systems, RQ-системы), определенные Г.И. Фалином (G.I. Falin). Принципиальное отличие RQ-систем от классических систем массового обслуживания состоит в том, что заявки, пришедшие в систему и обнаружившие прибор занятым, не покидают систему, а присоединяются к повторной очереди с тем, чтобы попытаться занять прибор в будущем.

Исследованию RQ-систем посвящено большое количество работ. Только в монографии Д.Р. Арталехо (J.R. Artalejo) приведено более семисот ссылок на издания различного уровня.

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

Г.Л. Ионин (G.L. Jonin) и Г.И. Фалин (G.I. Falin) и Ю.И. Сухарев (Yu.I. Sukharev) проанализировали RQ-систему с конфликтами, которая носит название системы с двойным соединением. Б.Д. Чои (B.D. Choi) и соавт. рассматривали RQ-систему с конфликтами заявок, управляемую протоколом случайного множественного доступа CSMA-CD. Также вопросами анализа RQ-систем с конфликтами заявок занимались В. Krishna Kumar, G. Vijayalakshmi, A. Krishnamoorthy, S. Sadiq Basha, И.И. Хомичков (I.I. Khomichkov), П. Русков и Б. Димитров, а также В.В. Анисимов (V.V. Ап-isimov) и X.JI. Атаджанов (H.L. Atadzanov), A.A. Назаров.

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

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

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

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

RQ-системы с конфликтами заявок применяются при проектировании различных сетей и протоколов передачи данных (Ethernet, EtherTalk, G-Net, использующих протокол CSMA/CD).

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

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

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

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

3. Разработка комплекса проблемно-ориентированных программ, реализующих предложенные численные методы.

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

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

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

3. На основе предложенной модификации метода асимптотического анализа RQ-систем с конфликтами заявок, а также в допредельной ситуации, разра-

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

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

1. Метод асимптотических семиинвариантов для исследования Яр-систем с конфликтами заявок в предельном условии растущей задержки.

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

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

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

5. Условия существования стационарного режима в Яр-системах.

6. Условия применимости асимптотических результатов в допредельной ситуации.

7. Численные методы для исследования вероятностно-временных характеристик Яр-систем с конфликтами заявок, а также комплекс пролемно-ориентированных программ, реализующий предложенные численные методы.

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

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

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

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

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

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

1. XII - XV Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2008 - 2011 гг.

2. Международная научная конференция «Теория вероятностей и, случайные процессы, математическая статистика и приложения», г. Минск, 2008 г.

3. VII - IX Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2008-2010 гг.

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

5. VIII Международная конференция по финансово-актуарной математике и смежным вопросам. Красноярск, 2009 г.

6. Международная конференция по финансово-актуарной математике и эвентоконвергенции технологий, г. Красноярск, 2010 г.

7. The third international Conference «Problems of Cybernetics and Informatics» (PCI'2010). Baku, 2010.

8. International conference «Modern Stochastics: Theory and Applications II», Kiev, 2010.

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность работы, сформулирована цель и задачи диссертационного исследования, изложена его научная новизна, раскрыты теоретическое значение и практическая ценность полученных результатов, кратко излагается содержание диссертационной работы.

В первой главе проводятся исследования марковских 11(}-систем с конфликтами заявок методом асимптотических семиинвариантов в предельном условии растущего времени задержки заявки в источнике повторных вызовов.

Случайный процесс {/(/), /(/)} изменения во времени состояний Яр-системы с конфликтами заявок и простейшим входящим потоком является двумерной цепью Маркова, где /(*) - число заявок в источнике повторных вызовов (ИПВ) в момент времени I, а 1(1) определяет состояние прибора в момент времени / следующим образом: /(/) £СЛи пРи^°Р св°боден;

[1, если прибор занят. В параграфе 1.2. выполнено допредельное исследование Ш^-системы с конфликтами заявок и простейшим входящим потоком и найден явный вид семиинвариантов первых шести порядков.

В параграфе 1.3 проводится исследование ¡К^-системы с конфликтами заявок и входящим МАР-потоком методом асимптотических семиинвариантов в условии растущего времени задержки заявки в ИПВ, т.е. а 0.

Для МАР-потока была введена дополнительная переменная - значения цепи Маркова, управляющей входящим МАР-потоком и рассмотрен случайный процесс {/(/), ¿(г),/(/)}, который является цепью Маркова. Для этого марковского процесса определены характеристические функции

Я(/Лк)=£е;м/>(Ш). / = {0,1}, /

и составлена следующая векторно-матричная система дифференциальных уравнений Колмогорова

(О

си

для векторной характеристической функции

Н(и)= {Я(0Д,к)я(1,1,и), Я(0,2,и),Я(1,2,4.......}.

Здесь блочные матрицы А(/и) и В(у'и) являются матрицами коэффициентов системы уравнений Колмогорова относительно характеристических функций Н(1,к,и)

а(у«)= ' е V , В(»=

<2-А-У Л + V

\ц1 + е2;ы(Л + У) д-А-У-ц1;

где О - матрица инфинитезимальных характеристик, управляющей цепи Маркова £(/), а У - матрица из элементов й^ц^, величины - элементы матрицы Б вероятностей наступления событий МАР-потока в момент изменения

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

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

Теорема 1.1. Предельное при е 0 значение Р, (и-) решения ^ (м>, г) уравнения

дн>

полученного выполнением в (1) замен

ст = е, и = еи\ Н(«)=Р,(и',е),

имеет вид Р, (н1) = Ке7"'*', где вектор К = (к(о), к(1)} является решением системы

К(В0 + К1Ао) = 0, (2)

удовлетворяющим условию нормировки ЯЕ = 1, а компоненты вектора И определяются га равенств

Я(о)+ Я(1)= г, гЕ = 1, гО = 0,

величина к, является решением нелинейного скалярного уравнения

К(В,+к,А1)Е = 0, (3)

где вектор И = Н(к,) зависит от к, и является решением системы (2) и условия нормировки.

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

Уа ^ А(/и) = »тф0-«)+ Ек,+, М а(/и)

ди [_ /=0

(4)

выполним замены

Тогда уравнение (4) примет вид

ою ,-_о V.

(5)

Теорема 1.2. Предельное при е—»0 значение Рт+1 (и>) решения Рт+1(и',е) уравнения (5) имеет вид

где вектор Я = (я(о), И(1)} определен в теореме 1.1, а скалярная величина кт+, определяется формулой

т +1 \_п=2 \ к=о ) V 4=0 У.

ёт(В|+к,А,)Е

RA1E+g(B1 +к,А,)Е'

уравнения, определяющие векторы § к приведены в диссертации, а векторы Гу для V = 1 ,т -1 определяются равенствами = +

рядка. Тогда величину ку/о будем называть асимптотическим семиинвариантом у-го порядка.

Приводится частный случай ЯС>-системы с конфликтами заявок с входящим МАР-потоком для случая входящего ММР-потока и простейшего входящего потока. Для этих ЯС>-систем справедливы сформулированные теоремы 1.1

В параграфе 1.4 производится сравнение результатов (семиинвариантов и распределений вероятностей числа заявок в ИПВ) допредельного и асимптотического исследований ЯС>-системы с конфликтами заявок и простейшим входящим потоком для определения области применимости асимптотического метода. Построена таблица значений расстояния Колмогорова между допредельным и асимптотическим распределением вероятностей числа заявок в ИПВ, найденных при помощи обратного преобразования Фурье, для различных значений параметра о.

Во второй главе выполнены исследования немарковских Я(}-систем с конфликтами заявок при помощи метода асимптотических семиинвариантов в предельном условии растущего времени задержки заявки в источнике повторных вызовов, т.е а -» 0.

В параграфе 2.1 определяются условия существования стационарного режима в немарковской Яр-системе с простейшим входящим потоком.

Так как случайный процесс /(/) для рассматриваемой Ж^-системы является полумарковским, а эргодические свойства полумарковского процесса полностью определяются эргодическими свойствами его вложенной цепи Маркова, то для рассматриваемого процесса /(/) определили его вложенную цепь и выполнили исследование ее эргодических свойств.

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

1. При 0<5'(0)<°о

где величина загрузки р = ХЬ, величина 5 - пропускная способность системы, В'(0)= В'(х]х=0 - значение производной в нуле от функции распределения в(х),

Функцию Ьу(и) = ехр будем называть асимптотикой у-го по-

и 1.2.

Р<5 = |Б'(О),

b - среднее значение времени обслуживания в рассматриваемой RQ-системе, то

есть

Ь= \xdD(x).

2. При В'(0)=оо цепь Маркова является эргодической при любых значениях загрузки р = ХЬ.

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

Для МАР-потока была введена дополнительная переменная k(t) - значения цепи Маркова, управляющей входящим МАР-потоком, и рассмотрен случайный процесс {/(i),fc(f),i(f)}.

Так как случайный процесс {/(/),£(г),;'(/)} изменения во времени состояний {l,k,i} рассматриваемой RQ-системы является немарковским, поэтому для значения /(/)=1 (состояние занятости прибора) определили дополнительную переменную z(i), равную длине интервала от момента t до момента окончания обслуживания заявки, стоящей на приборе в момент времени /.

Асимптотическое исследование данной RQ-системы выполнено при помощи метода асимптотических семиинвариантов при выполнении предельного условия растущего времени задержки заявки в источнике повторных вызовов, т.е а-> 0. Реализация асимптотического метода аналогична изложенному в главе 1.

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

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

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

Случайный процесс {/(/), /(/)} изменения во времени состояний RQ-системы с конфликтами заявок и простейшим входящим потоком является двумерной цепью Маркова, где /(/) определяет состояние прибора в момент времени t следующим образом:

О, если прибор свободен;

/(/) = • 1, если прибор занят;

2, если прибор находится в состоянии оповещения о конфликте.

Асимптотическое исследование данной RQ-системы выполнено при помощи метода асимптотических семиинвариантов при выполнении предельного

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

В параграфе 3.3 доказывается неэргодичность 11(}-систем с конфликтами заявок и оповещением о конфликте.

Применяя условие Каплана и теорему Сеннота, определили, что такая система является неэргодической при любых значениях загрузки р = ХЬ > 0.

В параграфе 3.5 выполнено асимптотическое исследование немарковской 1К)-системы с конфликтами заявок и оповещением о конфликте с простейшим входящим потоком в предельном условии растущего времени задержки заявки в ИПВ, т.е. при а -> 0.

Реализация асимптотического метода аналогична изложенному в главе 1.

Приводится частный случай немарковской ЛС>-системы с конфликтами заявок и оповещением о конфликте с входящим МАР-потоком для случая экспоненциальных времени обслуживания заявки на приборе и этапа оповещения о конфликте.

В четвертой главе применяются алгоритмы численного анализа 11()-систем с конфликтами заявок и математических моделей компьютерных сетей связи с оповещением о конфликте.

В параграфах 4.2 и 4.3 приводятся численные методы нахождения допредельных вероятностно-временных характеристик рассматриваемых Яр-систем с конфликтами заявок и Яр-систем с конфликтами заявок и оповещением о конфликте.

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

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

к к I

где ру{}) - асимптотиче-

/=0 /=0 I

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

Приведем некоторые из рассмотренных 11<3-систем.

Рассмотрим марковскую ЯС>-систему с конфликтами заявок и входящим МАР-потоком.

расстояние Колмогорова Д„ = тах

О<к£К

Пусть

о = {0,01; 0,05; 0,1}, ц = 1,

"0,1 0 0' -03 0,1 0,2 " " 0 0,9 од"

Л = 0 0,2 0 , 0 = 0,2 -0,4 0,2 1 0 0

0 0 0,1 0,2 03 -0,5 0,5 0,5 0

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

Таблица 4.1

а 0,1 0,05 0,01 о -» 0

к,(с) 0,56 0,53 0,51 0,51

к2(о) 1,76 1,67 1,59 1,58

к3(о) 8,09 7,66 7,32 6,65

Приведенные в таблице результаты не противоречат предположению, что с приближением о -» 0 допредельные последовательности сходятся к асимптотическим результатам.

При помощи метода обратного преобразования Фурье, построим асимптотические аппроксимации Ру(г) допредельного распределения порядков V = 2, 3.

Ниже на графиках (рис. 4.1 и 4.2) показаны распределения вероятностей состояний системы, полученные асимптотически (/) и в допредельной ситуации РЬ) при заданных значениях параметров (7).

Рис. 4.1. Допредельное и асимптоты- Рис. 4.2. Допредельное и асимптотическое распределения вероятностей ческое распределения вероятностей числа заявок в ИПВ при а = 0.1 числа заявок в ИПВ при а = 0,01

В таблице 4.2 приведены значения Ау расстояния Колмогорова между асимптотическими аппроксимациями порядка V распределения Р (;) состояний системы, найденными в предельном условии а~»0 и допредельным распределением Р(г) при различных значениях величины а.

Таблица 4.2

о 0,1 0,05 0,01

Порядок аппроксимации V

2 0,107 0,048 0,017

3 0,75 0,041 0,016

Рассмотрим марковскую ЯС)-систему с конфликтами заявок, оповещением о конфликте и простейшим входящим потоком.

Определим значения параметров следующим образом

о = {0,01;0,05;ОД}, ц,=5, ц2=6, А. = 0,8. (8)

Построим график (рис,4.3) изменения значений функции к,(т) в зависимости от начального условия.

т I

Рис. 4.3. Изменение значений функции Рис. 4.4. Изменение значений функции к,(т) в зависимости от времени кг(У) в зависимости от времени

Из графика 4.3 видно, что с течением времени значения функции к,(т) концентрируются в окрестности точки к,(т)= 0,436.

Аналогичным образом проанализируем поведение семиинварианта второго порядка к2(т) с течением времени. Построим график (рис. 4.4) изменения значений функции к2(т) в зависимости от начального условия к2(0)= 0.

Из графика 4.4 видно, что с течением времени значения функции к2(т) концентрируются в окрестности точки к2(т)= 1,014.

Таблиц 4.3

ст 0,1 0,05 0,01 сг->0

к, (а) 0,46 0,45 0,44 0,44

к2(а) 1,10 1,06 1,02 1,01

к3(с) 3,66 3,44 3,27 3,23

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

Ниже на графиках (рис. 4.5 и 4.6) показаны распределения вероятностей состояний системы, полученные асимптотически />3(г) и в допредельной ситуации P(i) при заданных значениях параметров (8).

Рис. 4.5. Допредельное и асимптотическое распределения вероятностей числа заявок в ИПВ при <т = 0,1

Рис. 4.6. Допредельное и асимптотическое распределения вероятностей числа заявок в ИПВ при сг = 0,01

В таблице 4.4 приведены значения Ау расстояния Колмогорова между асимптотическими аппроксимациями порядка V распределения Ру(/) состояний системы, найденными в предельном условии с->0 и допредельным распределением Р(/') при различных значениях величины с.

Таблица 4.4.

Порядок аппроксимации V 0,1 0,05 0,01

2 0,099 0,046 0,013

3 0,046 0,037 0,011

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

В комплекс входят следующие приложения:

1. Рекуррентный М-М.

2. Рекуррентный М-Ск

3. Мегаматричный МАР-М.

4. Кр-Р.

5. Рекуррентный М-М-М.

6. Рекуррентный М-М-ЯрЫ.

7. Рекуррентный М-в^ИрМ.

Каждое из предложенных приложений реализует численные алгоритмы, подробно изложенные в параграфах 4.2 и 4.3 главы 4.

Работа с приложениями состоит из нескольких этапов.

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

Ввод данных

Диагональная матрица с элементами ¿к на главной диагонали Л

¡'-ОЗ 01 0.2 Л

Матрица инфинитезимапьных характеристик о ?

0.2 -0.1 02 1^0.2 03 -45)

0.1 о о • и I 1 I и

а!

Матрица вероятностей перехода цели Маркова

'0 0.9 0.Г

1 0 О 1.0.5 0.5 О,

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

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

ЯЕггяшаоащгяиДОтиэва^яа

________„___________________________________

Рис. 4.7. Этап ввода начальных данных в приложении Мегаматричный МАР-М

2 этап. После ввода начальных данных автоматически начинается реализация численных алгоритмов, запрограммированных в теле приложения. Численные методы, реализованные в представленном комплексе программ, подробно изложены в параграфах 4.2 и 4.3.

3 этап. После того как были выполнены предыдущие два этапа, пользователь получает визуализированные результаты «Результаты реализации программы». В качестве результатов работы программы доступна следующая полученная информация: распределение вероятностей числа заявок в ИПВ (/40) ~ график и таблица значений, а также допредельные семиинварианты первых трех порядков (рис. 4.8).

Результаты реализации программы

Распределение вероятностей числа заявок а 1 - 0 100

повторных вызовов:

0 1.75-10-5

1 5.801-10-5

2 1.486104

3 3.084-10-*

4 5.656-104

5 9447104

6 1.4710-3

7 2.159-10-3

8 3.027-10-3

9 4.079-103

10 5313103

11 6.72103

12 8284 10-3

13 Э.Эв1103

и 0012

15 0.014

Семиинварианты. Семиинвариант первого порядка Семиинвариант второго порядка Семиинвариант третьего порядки

Рис. 4.8. Результаты реализации программы Рекуррентный М-М

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

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

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

Статьи в журналах, рекомендованных ВАК

1. Судыко Е.А. Метод асимптотических семиинвариантов для исследования математической модели сети случайного доступа / A.A. Назаров, Е.А. Судыко // Проблемы передачи информации. - 2010. - Т. 46, № 1. - С. 94-111.

2. Судыко Е.А. Исследование марковской RQ-системы с конфликтами заявок и простейшим входящим потоком / A.A. Назаров, Е.А. Судыко II Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. - № 3 (12). - С. 97-106.

3. Судыко Е.А. Асимптотический анализ системы ММРIМ11 с источником повторных вызовов / Е.А. Судыко // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. -№4 (12). -С. 79-90.

4. Судыко Е.А. Условия существования стационарного режима в немарковских RQ-системах с конфликтами заявок / A.A. Назаров, Е.А. Судыко // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. - 2011. - Т. 318, № 5. - С. 166-168.

5. Судыко Е.А. Неэргодичность математической модели компьютерной сети случайного доступа / A.A. Назаров, Е.А. Судыко II Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Ре-шетнева. - 2011. - № 3 (36). - С. 62-65.

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

6. Судыко Е.А. Асимптотический анализ марковской системы массового обслуживания с двумя входящими потоками / Е.А. Судыко, С.А. Цой // Научное творчество молодежи : материалы XII Всероссийской научно-практической конференции (Филиал КемГУ в г. Анжеро-Судженске, 18-19 апреля 2008 г.): в 2 ч. - Томск: Изд-во Том. ун-та, 2008. - Ч. 1. - С. 43-^15.

7. Судыко Е.А. Одноканальная сеть связи с оповещением о конфликте и резервированием с бесконечным числом станций / Е.А. Судыко // Информационные технологии и математическое моделирование (ИТММ-2008): материалы VH Всероссийской научно-практической конференции с международным уча-

стием (Филиал КемГУ в г. Анжеро-Судженске, 14-15 ноября 2008 г.): в 2 ч. -Томск: Изд-во Том. ун-та, 2008. - Ч. 2. - С. 60-63.

8. Судыко Е.А. Исследование математической модели сети случайного доступа методом асимптотических семиинвариантов третьего порядка / A.A. Назаров, Е.А. Судыко // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2009. - № 2 (7). -С. 52-64.

9. Судыко Е.А. Численное исследование математической модели сети случайного доступа / A.A. Назаров, Е.А. Судыко // Научное творчество молодежи : материалы XIII Всероссийской научно-практической конференции (Филиал КемГУ в г.Анжеро-Судженске, 14 - 15 мая 2009 г.): в 2 ч. - Томск : Изд-во Том. ун-та, 2009. - Ч. 1. - С. 88-90.

10. Судыко Е.А. Характеристические функции в асимптотическом анализе математической модели сети случайного доступа / A.A. Назаров, Е.А. Судыко, С.А. Цой // Массовое обслуживание: потоки, системы, сети: материалы международной научной конференции «Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей» (Минск, 26 -29 января 2009 г.). - Минск : РИВШ, 2009. - С. 210-215.

И. Судыко Е.А. Исследование двулинейных систем массового обслуживания с источником повторных вызовов / ЕЛ. Судыко // Труды VIII Международной конференции по финансово-актуарной математике и смежным вопросам (Красноярск, 24 - 26 апреля 2009 г.). / Сибирский федеральный ун-т. -Красноярск, 2009. - Ч. 2. - С. 26-28.

12. Судыко Е.А. Метод асимптотических семиинвариантов для исследования системы М|М|1|ИПВ с конфликтом заявок / Е.А. Судыко /У Информационные технологии и математическое моделирование (ИТММ-2009) : материалы VIII Всероссийской научно-практической конференции с международным участием (Филиал КемГУ в г.Анжеро-Судженске, 12 - 13 ноября 2009 г.): в 2 ч. -Томск: Изд-во Том. ун-та, 2009. - Ч. 1. - С. 70-74.

13. Судыко Е.А. Исследование однолинейных систем массового обслуживания с конфликтами заявок / Е.А. Судыко // Труды Международной конференции по финансово-актуарной математике и эвентоконвергенции технологий (Красноярск, 23 - 25 апреля 2010 г.) / Сибирский федеральный ун-т. - Красноярск, 2010. - Ч. 2. - С. 20-25.

14. Судыко Е.А. Допредельные характеристики RQ-системы с конфликтами заявок / Е.А. Судыко И Научное творчество молодежи : материалы XIV Всероссийской научно-практической конференции (Филиал КемГУ в г. Анжеро-Судженске, 15 - 16 апреля 2010 г.): в 2 ч. - Томск : Изд-во Том. ун-та, 2010. -Ч. 1.-С. 97-100.

15. Sudyko Е. Investigation of system MAP|M|1|RQ by the method of asymptotical semiinvariants by the third order / E. Sudyko // Problems of cybernetics and informatics : the third international conference (PCI'2010) (Baku, Azerbaijan. 6-8 September, 2010). - Baku: Elm, 2010. - Vol. 2. - P. 228-231.

16. Судыко Е.А. Исследование 11(}-системы с оповещением о конфликте методом асимптотического анализа до второго порядка / Е.А. Судыко // Информационные технологии и математическое моделирование (ИТММ-2010) : материалы IX Всероссийской научно-практической конференции с международным участием (Филиал КемГУ в г.Анжеро-Судженске, 19-20 ноября 2010 г.): в 2 ч. - Томск: Изд-во Том. ун-та, 2010. - 4.1. - С. 83-87.

17. Судыко Е.А. Стационарный режим в немарковских Яр-системах с конфликтами заявок / А.А. Назаров, Е.А. Судыко // Научное творчество молодежи : материалы XV Всероссийской научно-практической конференции (Филиал КемГУ в г. Анжеро-Судженске, 28 - 29 апреля 2011 г.): 2 ч. - Томск: Изд-во Том. ун-та, 2011.-Ч. 1.-С.31-34.

Тираж 100 экз; Отпечатано в ООО «Позитив-НБ» 634050 г. Томск, пр. Ленина 34а

Оглавление автор диссертации — кандидата физико-математических наук Судыко, Елена Александровна

Введение.

Глава 1 Исследование марковских Ж^-систем с конфликтами заявок.

1.1 Математическое моделирование компьютерных сетей связи применением Ш^-систем.

1.2 Исследование марковской ЯС>-системы с конфликтами заявок и простейшим входящим потоком.

1.3 Метод асимптотических семиинвариантов для исследования марковских Ж^-систем с конфликтами заявок и входящим МАР-потоком.

1.4 Сравнительный анализ результатов допредельного и асимптотического исследований Яр-систем с конфликтами заявок.

Резюме.

Глава 2 Исследование немарковских ЯС)-систем с конфликтами заявок.

2.1 Условия существования стационарного режима в немарковских Ж^-системах с конфликтами заявок.

2.2 Немарковская Ж^-система с конфликтами заявок и входящим МАР-потоком

Резюме.

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

3.1 Математическое моделирование компьютерных сетей связи с оповещением о конфликте применением Яр-систем.

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

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

3.4 Немарковская математическая модель компьютерной сети связи с простейшим входящим потоком.

Резюме.

Глава 4 Численные методы, компьютерное моделирование и комплекс проблемно-ориентированных программ численного исследования ИХ^-систем с конфликтами заявок.

4.1 Численная реализация асимптотических результатов.

4.2 Алгоритмы численного исследования допредельных ЯС^-систем с конфликтами заявок.

4.3 Алгоритмы численного исследования допредельных Я(3-систем с конфликтами заявок и оповещение о конфликте.

4.4 Область применимости асимптотических результатов в допредельной ситуации.

4.5 Компьютерное моделирование и комплекс проблемно-ориентированных программ.

Резюме.

Введение 2011 год, диссертация по информатике, вычислительной технике и управлению, Судыко, Елена Александровна

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

Исследованию сетей связи посвящено большое количество работ [9, 16, 42, 51, 54-56, 68-70, 87, 96]. На поведение систем связи влияет большое число случайных факторов. Их исследование использует аппарат теории случайных процессов [5, 17, 19, 66] и теории массового обслуживания [8, 12, 13, 15, 20-22, 27-28, 31, 36, 37, 39, 75], что позволяет построить математическую модель изучаемой сети связи [38, 44] и провести теоретические исследования параметров функционирования реальной системы.

С работ датского ученого К.А.Эрланга (1878-1929), сотрудника Копенгагенской телефонной компании, изучавшего в 1908-1922 гг. функционирование телефонных сетей, началось развитие теории массового обслуживания.

Краткий исторический очерк развития теории массового обслуживания содержится, например, в работе [131].

В 1924 г Г. Юл (G. Jule). определил понятие процесса чистого размножения, а в 30-х годах В. Феллер (W. Feller) ввел понятие процесса размножения и гибели. Большой вклад в развитие теории массового обслуживания внесли А.Н. Колмогоров, А.Я. Хинчин [84], Б.В. Гнеденко [20-22], A.A. Боровков и Ф. Пол-лачек (F. Pollaczek). В СССР теория массового обслуживания начинает развиваться с 60-х годов XX в.

Активное развитие научно-технического прогресса во второй половине XX в. привело к существенным изменениям в области вычислительной техники и средств связи. Системы массового обслуживания оказались наилучшим математическим аппаратом для исследования и оптимизации процессов в телекоммуникационных сетях [45]. Применение классических моделей систем массового обслуживания к исследованию процессов в телекоммуникационных сетях давало достаточно грубые результаты. Поэтому появилась необходимость создания адекватных математических моделей систем массового обслуживания применимых к реальным телекоммуникационным системам.

RQ-системы. Одни из таких моделей, используемые для анализа и исследования телекоммуникационных и компьютерных систем - модели с повторной очередью (retrial queueing system) [6,38,41,102,104,133].

В 50-х годах появляются первые статьи по исследованию Retrial queueing systems (RQ-системы), определенные Г.И. Фалином (G.I. Falin) [104]. Принципиальное отличие RQ-систем от классических систем массового обслуживания состоит в том, что заявки, пришедшие в систему и обнаружившие прибор занятым, не покидают систему, а присоединяются к повторной очереди с тем, чтобы попытаться занять прибор в будущем.

Исследованию RQ-систем посвящено большое количество работ. Только в монографии Д.Р. Арталехо (J.R. Artalejo) [95] приведено более семисот ссылок на издания различного уровня. Основы и фундаментальные исследования в области теории RQ-систем также можно найти в работах Г.И. Фалина (G.I. Falin) [103-116].

Для получения характеристик системы нужно было найти необходимые и достаточные условия эргодичности. В 1957 г. Д.В. Коэн (J.W. Cohen) [99] предложил необходимые условия, найденные при помощи усеченных систем. Позже, в 1980 г. Н. Деул (N. Deul) [101] исследовал эргодичность многоканальных моделей при помощи вложенных цепей Маркова для непрерывных марковских процессов. Также вопросами эргодичности занимались Г.И. Фалин (G.I. Falin) [105, 106], Т. Ханшке (T. Hanschke) [118], Ф.С. Фостер (F.C. Foster) [117], М.Д. Мустафа (M.D. Moustafa ) [123], A.A. Назаров и СЛ. Шохор [69, 70], а также Л.И. Сеннот (L.I. Sennot) [125], Т. Кернане (T. Kernane) [120], Д.Р. Арталего (J.R. Artalejo) [93].

В 1982 г. А.Г. де Кок (A.G. de Kok) [100] предложил методы численного подсчета стационарного распределения вероятностей для RQ-систем, которые в дальнейшем были адаптированы для различных задач и моделей [94].

В 60-х годах исследователи стали применять метод асимптотического анализа RQ-систем. Этот метод заключается в получении каких-либо характеристик исследуемого процесса при выполнении некоторого предельного условия, вид которого конкретизируется, исходя из поставленных задач. В числе таких исследователей были Д.В. Коэн (J.W. Cohen) [99], Д. Риордан (J. Riordan) [124], Г.И. Фалин (G.I. Falin) [103, 105-107], Д.Р. Арталего (J.R. Artalejo) [93], B.B. Анисимов (V.V. Anisimov) и X.JI. Атаджанов (H.L. Atadzhanov) [1, 2, 3, 89], Л.И. Лукашук (L.I. Lukashuk) [122], A.A. Боровков [10], С.Н. Степанов (S.N. Stepanov) [76, 126-130], A.A. Назаров и его ученики [23-26, 30, 46, 50-53, 58-60, 65, 77-82,130] и другие [4, 73].

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

Г.Л. Ионин (G.L. Jonin) [32] и Г.И. Фалин (G.I. Falin) и Ю.И. Сухарев (Yu.I. Sukharev) [115] проанализировали RQ-систему с конфликтами, которая носит название системы с двойным соединением. Б.Д. Чои (B.D. Choi) и соавт. [97] рассматривали RQ-систему с конфликтами заявок, управляемую протоколом случайного множественного доступа CSMA-CD [7, 49]. Для этой системы производящая функция предельного распределения была получена для произвольных моментов времени. Также, вопросами анализа RQ-систем с конфликтами заявок занимались В. Krishna Kumar, G. Vijayalakshmi, A. Krishnamoorthy, S. Sadiq Basha [121], И.И. Хомичков (I.I. Khomichkov) [85, 86], П. Русков и Б. Димитров [74], а также В.В. Анисимов (V.V. Anisimov) и Х.Л. Атаджанов (H.L. Atadzanov) [2], A.A. Назаров [57-65]. Обзор работ, посвященный исследованию систем массового обслуживания с повторными вызовами за последние 10 лет приведен в [90-92].

Межпредметность рассматриваемых моделей. Математические модели систем массового обслуживания широко применяются при исследовании процессов в системах управления и организации промышленными предприятиями, в сфере обслуживания (от предприятий общественного питания и бытового обслуживания до регулирования уровня воды в водохранилищах [71-72]); очистки воды [71]; в системах проектирования и анализа функционирования автоматизированных систем управления (АСУ) [71], в системах противовоздушной обороны и средствах радиолокации, в различных экономических системах, системах телекоммуникации и т.п.

В частности, Яр-системы, то есть системы с повторной очередью, возникли как аппарат для моделирования систем телефонии [43, 119], и теория таких систем достаточно хорошо развита [32-34, 40, 83, 98, 132]. Применение таких моделей для исследования компьютерных сетей тоже оказалось достаточно продуктивным.

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

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

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

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

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

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

3. Разработка комплекса проблемно-ориентированных программ, реализующих предложенные численные методы.

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

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

2. Впервые получены эргодические условия для ЯХ^-систем с конфликтами заявок и математических моделей компьютерных сетей связи, управляемых протоколом случайного множественного доступа в виде 11(3-систем с конфликтами заявок и оповещением о конфликте, позволяющие определять условия существования стационарного режима в рассматриваемых системах.

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

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

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

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

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

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

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

Публикации. По материалам диссертации опубликовано 17 работ, из них 5 статей в журналах списка ВАК:

2. Судыко Е.А. Исследование марковской RQ-системы с конфликтами заявок и простейшим входящим потоком / A.A. Назаров, Е.А. Судыко // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. - № 3 (12). - С. 97 -106.

3. Судыко Е.А. Асимптотический анализ системы ММР | М11 с источником повторных вызовов / Е.А. Судыко // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. - № 4 (12). - С. 79 - 90.

4. Судыко Е.А. Условия существования стационарного режима в немарковских RQ-системах с конфликтами заявок / A.A. Назаров, Е.А. Суды

10 ко // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. - 2011. - Т. 318. - № 5. - С. 166 -168.

5. Судыко Е.А. Неэргодичность математической модели компьютерной сети случайного доступа / A.A. Назаров, Е.А. Судыко // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - 2011. - № 3 (36). - С. 62 - 65.

6. Судыко Е.А. Асимптотический анализ марковской системы массового обслуживания с двумя входящими потоками / Е.А. Судыко, С.А. Цой // Материалы XII Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 18-19 апреля 2008 г. -Томск: Изд-во Том. ун-та, 2008. - Ч. 1. - С. 43 - 45.

7. Судыко Е.А. Одноканальная сеть связи с оповещением о конфликте и резервированием с бесконечным числом станций / Е.А. Судыко // Информационные технологии и математическое моделирование (ИТММ-2008): Материалы VII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г. Анжеро-Судженске, 14-15 ноября 2008 г. - Томск: Изд-во Том. ун-та, 2008. - Ч. 2. - С. 60 - 63.

9. Судыко Е.А. Численное исследование математической модели сети случайного доступа / A.A. Назаров, Е.А. Судыко // Материалы XIII Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 14-15 мая 2009 г. - Томск: Изд-во Том. ун-та, 2009. - 4.1. - С. 88 - 90.

11 ждународной научной конференции «Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей». Минск, 26 - 29 января 2009 г. - Минск: РИВШ, 2009. - С. 210 - 215.

11. Судыко Е.А. Исследование двулинейных систем массового обслуживания с источником повторных вызовов / Е.А. Судыко // Труды VIII Международной конференции по финансово-актуарной математике и смежным вопросам. Красноярск, 24 - 26 апреля 2009 г. - Красноярск: Сибирский федеральный ун-т,

2009.-Ч. 2.-С. 26-28.

12. Судыко Е.А. Метод асимптотических семиинвариантов для исследования системы М|М|1|ИПВ с конфликтом заявок / Е.А. Судыко // Информационные технологии и математическое моделирование (ИТММ-2009): Материалы VIII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г.Анжеро-Судженске, 12-13 ноября 2009 г. - Томск: Изд-во Том. ун-та, 2009. - Ч. 1. - С. 70 - 74.

13. Судыко Е.А. Исследование однолинейных систем массового обслуживания с конфликтами заявок / Е.А. Судыко // Труды Международной конференции по финансово-актуарной математике и эвентоконвергенции технологий. Красноярск, 23 - 25 апреля 2010 г. - Красноярск: Сибирский федеральный ун-т,

2010.-Ч. 2.-С. 20-25.

14. Судыко Е.А. Допредельные характеристики RQ-системы с конфликтами заявок / Е.А. Судыко // Материалы XIV Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г. Анжеро-Судженске, 15-16 апреля 2010 г. - Томск: Изд-во Том. ун-та, 2010. — Ч. 1. - С.97 - 100.

15. Sudyko Е. Investigation of system MAP|M|1|RQ by the method of asymptotical semiinvariants by the third order / E. Sudyko // The third international conference «Problems of cybernetics and informatics»(PCr2010), Baku, Azerbaijan. 6-8 September, 2010. - Baku: Elm, 2010. - Vol. 2. - P.228 - 231.

16. Судыко Е.А. Исследование RQ-системы с оповещением о конфликте методом асимптотического анализа до второго порядка / Е.А. Судыко // Информационные технологии и математическое моделирование (ИТММ-2010): Материалы IX Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г.Анжеро-Судженске, 19-20 ноября 2010 г. -Томск: Изд-во Том. ун-та, 2010. - Ч. 1. - С. 83 - 87.

17. Судыко Е.А. Стационарный режим в немарковских RQ-системах с конфликтами заявок / A.A. Назаров, Е.А. Судыко // Материалы XV Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г. Анжеро-Судженске, 28 - 29 апреля 2011 г. - Томск: Изд-во Том. ун-та, 2011. - Ч. 1. - С.31 - 34.

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

1. XII Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2008 г.

3. VII Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2008 г.

5. VIII Международная конференция по финансово-актуарной математике и смежным вопросам. Красноярск, 2009 г.

6. XIII Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2009 г.

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

8. Международная конференция по финансово-актуарной математике и эвентоконвергенции технологий, г. Красноярск, 2010 г.

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

10. The third international Conference «Problems of Cybernetics and Informatics» (РСГ2010). Baku, 2010.

11. International conference «Modem Stochastics: Theory and Applications II», Kiev, 2010.

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

13. IX Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2010 г.

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

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

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

Случайный процесс {/(í), i(t)} изменения во времени состояний RQ-системы с конфликтами заявок и простейшим входящим потоком является двумерной цепью Маркова, где l(t) определяет состояние прибора в момент времени t следующим образом: Í0, если прибор свободен, l{t) =«

1, если прибор занят.

Для этого марковского процесса {/(í), z(/)} определены характеристические функции Н(1,и) = £ eiuiP{l, i), и для них составлена следующая система диффе ренциальных уравнений Колмогорова, определяющая функционирование этой системы

- ХН(0,и)+цЯ(1, и) + е2»\Н(1,и) + - = О, ди ди

- (Л + ц)я(1,и) + ЛЛ(0, и) + = 0. ди ди

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

2(Я,+с)+д

Н(0,и)=»-Хе* ' x-2X ) 1 2ст

Я(1,и)=-Ц

А, 4(1 Г Меуи-1)1

--ехгк----'-1

1-2Х ) [2а а также семиинварианты первых шести порядков.

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

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

Я(/,А:,и)=^емР(1,к,г), / = {0Д}, I и составлена следующая векторно-матричная система дифференциальных уравнений Колмогорова г-ст^)А(уи) = Н(и)в(уи) ди для векторной характеристической функции

Н(и)= (я(0Д,и),Я(1Д,и), Я(0,2,и),Я(1,2,и),.}.

Здесь блочные матрицы А(/и) и В(у'и) являются матрицами коэффициентов системы дифференциальных уравнений Колмогорова относительно характеристических функций Н(1,к,и).

Результатом асимптотического исследования Яр-системы с конфликтами заявок и входящим МАР-потоком стали уравнение относительно семиинварианта первого порядка и формулы, определяющие асимптотические семиинварианты порядка v = 2, 3, 4,.

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

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

Р(}) = ^-)емН(иУ1и.

Во второй главе выполнены исследования немарковских 11(2-систем с конфликтами заявок при помощи метода асимптотических семиинвариантов в предельном условии растущего времени задержки заявки в источнике повторных вызовов.

В параграфе 2.1 определяются условия существования стационарного режима в немарковской ИХ^-системе с простейшим входящим потоком.

Так как случайный процесс /(¿) для рассматриваемой ЯС^-системы является полумарковским, а эргодические свойства полумарковского процесса полностью определяются [67] эргодическими свойствами его вложенной цепи Маркова, то для рассматриваемого процесса /(/) определим его вложенную цепь и выполним исследование ее эргодических свойств.

Применяя эргодическую теорему Мустафы [67], определили условия существования стационарного режима для построенной цепи Маркова: 1. При 0<Я'(0)<оо где величина загрузки р = ХЬ, величина 5 - пропускная способность системы, В'(0)=В'(х]х о - значение производной в нуле от функции распределения В(х),

Ъ - среднее значение времени обслуживания в рассматриваемой ЯС^-системе, то есть

Ъ = \х(1В(х). о

2. При В'(0) = оо цепь Маркова является эргодической при любых значениях загрузки р = ХЬ.

В параграфе 2.2 выполнено асимптотическое исследование немарковской ЕХ^-системы с входящим МАР-потоком в предельном условии растущего времени задержки заявки в ИПВ.

Для МАР-потока была введена дополнительная переменная Щ) - значения цепи Маркова, управляющей входящим МАР-потоком и рассмотрен случайный процесс {/(/),

Так как случайный процесс {/(/),&(/),/(/)} изменения во времени состояний {1,к,г} рассматриваемой Яр-системы является немарковским, поэтому для значения /(0=1 (состояние занятости прибора) определили дополнительную переменную г{{), равную длине интервала от момента / до момента окончания обслуживания заявки, стоящей на приборе в момент времени

Случайный процесс {/(*), к{(), изменения во времени состояний {/, к, и г) описанной ЛС^-системы является марковским.

Для этого процесса введены характеристические функции

I I и составлена векторно-матричная система дифференциальных уравнений Колмогорова относительно этих функций

Н(0,«ХЛ + V - = е»Н(1,«ХЛ + V) - /Л^ + ди ои ан(1Ди)

Н (и,и\А + = Н(0, мХА + У )в{г) ди ди дг дг где <2 - матрица инфинитезимальных характеристик, управляющей цепи Маркова Щ), А - диагональная матрица условных интенсивностей МАР-потока, У -матрица из элементов величины с1кк2 - элементы матрицы Б вероятностей наступления событий МАР-потока в момент изменения состояния управляющей цепи Маркова.

Результатом асимптотического исследования немарковской 11С)-системы с конфликтами заявок и входящим МАР-потоком стали уравнение относительно семиинварианта первого порядка и формулы, определяющие асимптотические семиинварианты второго и третьего порядков.

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

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

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

Случайный процесс {/(¿), /(/)} изменения во времени состояний ЯС)-системы с конфликтами заявок и простейшим входящим потоком является двумерной цепью Маркова, где /(/) определяет состояние прибора в момент времени * следующим образом:

О, если прибор свободен, = < 1, если прибор занят,

2, если прибор находится в состоянии оповещения о конфликте.

Для этого марковского процесса {/(?), /(/)} определены характеристические функции Н(1,и) = ^е]и'Р(1,/), и для них составлена следующая система диффеI ренциальных уравнений Колмогорова, определяющая функционирование этой системы 1(р Х)ШМ=ш(0,и)+ц Н(1и)+ц Я(2;Ц),

Ту ди 2(ае-> 2(а - = ХЯ(0,и) ди ' ди v ;

Т\Г ди N ' ди к } а,(1 - е]и)+ ц2 ]н(2,и) + ^е2*Н{\,и).

Эту систему дифференциальных уравнений Колмогорова относительно характеристических функций Н(1,и) представили в векторно-матричной форме

МАи«Ьн(и)вин)+Ыи)оОи),

N ди N где обозначили вектор-строку Н(и)= (#(0,и), Я(1,м),Я(2,г/)} и матрицы коэффициентов А (ум), В (ум) и 0(ум).

Результатом асимптотического исследования такой системы стали уравнение относительно семиинварианта первого порядка и формулы, определяющие асимптотические семиинварианты порядка v = 2,3,4,.

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

Так как случайный процесс /(/) для рассматриваемой 11С)-системы является полумарковским, а эргодические свойства полумарковского процесса полностью определяются [67] эргодическими свойствами его вложенной цепи Маркова, то для рассматриваемого процесса /(/) определим его вложенную цепь и выполним исследование ее эргодических свойств.

Применяя условие Каплана и теорему Сеннота [120], определили, что такая система является неэргодической при любых значениях загрузки р = ХЬ > 0.

В параграфе 3.5 выполнено асимптотическое исследование немарковской математической модели компьютерной сети связи с простейшим входящим потоком и оповещением о конфликте в предельном условии растущего времени задержки заявки в И!IB.

Так как двумерный случайный процесс {/(/), /(0} изменения во времени состояний {/, /} рассматриваемой RQ-системы является немарковским, поэтому для значений процесса l(t)=l (состояние занятости прибора) и l(t)=2 (состояние оповещения о конфликте) определим дополнительную переменную z(t), равную длине интервала от момента t до момента освобождения прибора с окончанием обслуживания заявки, стоящей на приборе в момент времени t или завершением этапа оповещения о конфликте, продолжающегося в момент времени t.

Случайный процесс {l(t), i(t), z(t)} изменения во времени состояний {/, /, zj описанной RQ-системы является марковским.

Для этого процесса введены характеристические функции

H(0,u,t) = ZeM,)P(0,U), H(\,z,u,t) = Y,eM,)P(l,z,i,t), i i

H{2>z,u,t)=YJeiui{t)P{2,z,i,t), i и составлена система дифференциальных уравнений Колмогорова относительно этих функций

ЭЯ(О,м,0 Л , . dH(0,u,t) , dH(\,%u,t) , dH(2,0,u,t) - -XH{0,u,t) + J^—^— + dz + ^ . -XH(\,z,u,t) + + XH{b,u,t)B{z) dt du A dH(0,U,t)B,s [ dH(\,z,u,i) dH{\,0,u,t)

Л \ / Л Л ' си dz dz

ШЩ^А = -XH(2,z,u,t) - jae" ^¿^ a(z)+\e* H(2,u,t)a(z)+ dz dz ч

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

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

В главе 4 применяются алгоритмы численного анализа ЯС)-систем с конфликтами заявок и математических моделей компьютерных сетей связи в виде ЯР-систем с конфликтами заявок и оповещением о конфликте.

В параграфе 4.1 производится результаты реализации асимптотического метода исследования Ж^-систем с конфликтами заявок и Ж^-систем с конфликтами заявок и оповещением о конфликте

В параграфах 4.2 и 4.3 приводятся численные методы нахождения допредельных вероятностно-временных характеристик рассматриваемых Ж^-систем с конфликтами заявок и Ж^-систем с конфликтами заявок и оповещением о конфликте.

В параграфе 4.4. определяются условия применимости асимптотического метода в допредельной ситуации.

При увеличении времени задержки заявки, то есть при уменьшении параметра а или увеличении параметра N, уменьшается отклонение результатов асимптотического анализа от результатов допредельного исследования Ж^-систем с конфликтами заявок.

Заключение диссертация на тему "Исследование моделей RQ-систем с конфликтами заявок в условии большой задержки"

Заключение

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

Разработан комплекс численных методов для расчета допредельных вероятностно-временных характеристик Ж^-систем с конфликтами заявок.

В главе 1 выполнено исследование марковских ЯХ^-систем с конфликтами заявок с простейшим входящим потоком и входящим МАР-потоком методом асимптотических семиинвариантов до произвольного порядка, а также выполнено допредельное исследование марковской Ж^-системы с конфликтами заявок и простейшим входящим потоком.

Для приведенных моделей в явном виде были выведены определяющие их системы дифференциальных уравнений Колмогорова.

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

Получены асимптотические семиинварианты первых у=1, 2, 3,. порядков, характеризующие изменение состояний системы.

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

В главе 2 выполнено исследование немарковских Яр-систем с конфликтами заявок с простейшим входящим потоком и входящим МАР-потоком мето

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

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

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

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

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

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

Асимптотический анализ Ж^-системы с конфликтами заявок, оповещением о конфликте и конечным числом абонентских станций был проведен при вы

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

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

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

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

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

В главе 4 описаны и рассмотрены различные модели сетей передачи данных с протоколами случайного множественного доступа.

В главе 4 для сравнения результатов, полученных с помощью метода асимптотического анализа применяются алгоритмы численного анализа к исследованию ИХ^-систем с конфликтами заявок и математических моделей компьютерных сетей связи в виде 11С>-систем с конфликтами заявок и оповещением о конфликте.

Для определения точности аппроксимации находится расстояние Колмогорова Ак. При уменьшении параметра а (или увеличением параметра число абонентских станций) и увеличении порядка аппроксимации асимптотических результатов в допредельной ситуации уменьшается отклонение результатов

149 асимптотического анализа БК^-систем с конфликтами заявок и математических моделей компьютерных сетей связи в виде 11(2-систем с конфликтами заявок и оповещением о конфликте от результатов допредельного исследования таких систем. 1 I

Библиография Судыко, Елена Александровна, диссертация по теме Математическое моделирование, численные методы и комплексы программ

1. Анисимов В.В. Асимптотические методы анализа стохастических систем. Тбилиси: Мицниереба, 1984. - 178 с.

2. Анисимов В.В., Атаджанов Х.Л. Асимптотический анализ очередей в системах с повторными вызовами и сдвоенными соединениями. // препринт. Акад. Наук Украины. Инст. Кибернетики. Киев. 1991.

3. Анисимов В.В., Атаджанов Х.Л. Асимптотический анализ высоко на-дежныхсистем с повторными вызовами. // Исследование операций и АСУ. -1991.-№37.-С. 24-31.

4. Баранцев Р.Г. Перспективные идеи в асимптотической методологии. Автообзор // Вестник молодых ученых. Серия Прикладная математика и механика. 2000. - С. 27 - 35.

5. Баруча-Рид А.Т. Элементы теории марковских процессов и их приложения. М.: Наука, 1969. - 511 с.

6. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных системах. Теория и методы расчета. М.: Наука, 1989.

7. Башарин Г.П., Ефимушкин В.А., Прейдунов Ю.Н. Сравнительный анализ двух протоколов случайного множественного доступа // Автоматика и вычислительная техника. 1986. - № 4. - С. 34 - 39.

8. Башарин Г.П., Харкевич А.Д., Шнепс М.А. Массовое обслуживание в телефонии. М.: Наука, 1969. - 511 с.

9. Бертсекас Д., Галагер Р. Сети передачи данных. М.: Мир, 1989.544 с.

10. Боровков A.A. Асимптотические методы в теории массового обслуживания. М.: Наука, 1980. - 381 с.

11. Боровков A.A. Вероятностные процессы в теории массового обслуживания. М.: Наука, 1972. - 368 с.

12. Бородин А.Н. Элементарный курс теории вероятностей и математической статистики. 3-е изд. СПб.: изд. «Лань», 2002. - 256 с.

13. З.Бочаров П.П., Печинкин A.B. Теория массового обслуживания. -М.: Изд-во РУДН, 1995. 529 с.

14. Н.Бочаров П.П., Шлумпер JI.O. Система массового обслуживания MAP|G|l|r с фоновыми заявками // Информационные процессы. 2005. - Т. 5. -№5.-С. 367-369.

15. Буримов А.Д., Малинковский Ю.В., Маталыцкий М.А. Теория массового обслуживания: учебное пособие по спецкурсу. Гродно, 1984.

16. Вавилов В.А. Исследование математических моделей сетей множественного доступа, функционирующих в случайной среде: Дис. . канд. физ.-мат. наук. Томск, 2006. - 158 с.

17. Вентцель Е.С. Теория случайных процессов и ее инженерные приложения / Е.С. Вентцель, JI.A. Овчаров. М.: Наука, 1991. - 384 с.

18. Гантмахер Ф.Р. Теория Матриц: учебное пособие для вузов. М.: Наука,1967.-576 с.

19. Гихман И.И., Скороход A.B. Теория случайных процессов. Т. 1. -М.: Наука, 1971.-567 с.

20. Гнеденко Б.В. Курс теории вероятностей: учебник. 6-е изд. М.: Наука, 1988.-448 с.

21. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: КомКнига, 2007. - 336 с.

22. Гнеденко Б.В. Коваленко И.Н. Введение в теорию массового обслуживания. 4-е изд. М.: изд-во ЖИ, 2007. - 400 с.

23. Горбатенко А.Е. Асимптотики произвольного порядка для системы MAP|GI|oo в условии растущей интенсивности входящего потока // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2010 - № 2 (11). - С.35 - 43.

24. Горцев A.M., Назаров A.A., Терпугов А.Ф. Управление и адаптация в системах массового обслуживания. Томск: Изд-во Том. гос. ун-та, 1978. -110 с.

25. Дудин А.Н., Клименок В.И. Системы массового обслуживания с коррелированными потоками. Мн.: БГУ, 2000. - 175 с.

26. Иванова О.В., Назаров A.A. Асимптотический анализ протокола множественного доступа «синхронная Алоха» к локальной сети // Радиотехника. — 1991.-№5.-С. 20-24.

27. Ивченко Г.И., Каштанов, В.А., Коваленко И.Н. Теория массового обслуживания: учебное пособие для вузов. М.: Высшая школа, 1982. - 256 с.

28. Ионин Г.JI. Определение вероятностных характеристик однолинейной системы со сдвоенными соединениями и повторными вызовами // Модели систем распределения информации и их анализ. М.: Наука, 1982. - С. 51 - 54.

29. Ионин Г.Л., Седол Я.Я. Исследование телефонных систем при повторных вызовах // Латв. мат. ежегодник. Рига, 1970. - № 7. - С. 71 - 83.

30. Ионин Г.Л., Седол Я.Я. Таблицы вероятностных характеристик полнодоступного пучка при повторных вызовах. М.: Наука, 1970. - 156 с.

31. Кендалл М., Стюарт А. Теория распределений. М.: Изд. «Наука», 1966.-587 с.

32. Кёниг Д., Рыков В., Штойян Д. Теория массового обслуживания (основной курс: марковские модели, методы марковизации): учебное пособие по математике для студентов специальности 0647 прикладная математика - М., 1979 г.

33. Кёниг Д., Штойян Д. Методы теории массового обслуживания. -М.: Радио и связь, 1981.

34. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.

35. Клейнрок, Л. Теория массового обслуживания /Л. Клейнрок. М.: Машиностроение, 1979. - 432 с.

36. Коваленко И.Н., Кузнецов Н.Ю., Шуренков В.М. Случайные процессы. Киев: Наукова думка, 1983. - 366 с.

37. Кокс Д., Смит В. Теория очередей. М.: изд. «МИР», 1966. - 216 с.

38. Колоусов Д.В. Исследование математических моделей потоков в сетях случайного доступа: Дис. канд. физ.-мат. наук. Томск, 2004. - 141 с.

39. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1984. - 832 с.

40. Кузнецов H.A. Математическое обеспечение телекоммуникационных систем // Вестн. РАН. 1995. - № 11. - С. 975 - 981.

41. Лившиц Б.С., Пшеничников А.П., Харкевич A.A. Теория телетрафика. -М.: Связь, 1979.

42. Лопухова C.B. Асимптотические и численные методы исследования специальных потоков однородных событий: Дис. . канд. физ.-мат. наук: 05.13.18; Томский гос. ун-т. Томск. 2008. - 167 с.

43. Лукач Е. Характеристические функции. М.: Наука, Главная редакция физ. мат. лит., 1979. - 424 с.

44. Марголис Н.Ю., Терпугов А.Ф. Имитационное моделирование случайности: учебно-справочное пособие. Томск: изд. Том. гос. ун-та, 2003. - 63 с.

45. Михайлов В.А. Методы случайного множественного доступа: Дис. На соикс. учен. степ. канд. техн. наук. М.: МФТИ, 1979.

46. Назаров A.A. Асимптотический анализ марковизируемых систем. -Томск: изд-во Том. ун-та, 1991. -158 с.

47. Назаров A.A. Устойчивое функционирование нестабильных сетей связи с протоколом случайного доступа // Проблемы передачи информации, 1997. -№2.-С. 101-111.

48. Назаров A.A., Моисеева A.A. Метод асимптотического анализа в теории массового обслуживания. Томск: Изд-во HTJI, 2006. - 112 с.

49. Назаров A.A., Одышев Ю.Д. Исследование сетей связи с протоколами «адаптивная Алоха» для конечного числа станций в условиях перегрузки // Пробл. передачи информ. 2000. - Т. 36. - № 13. - С. 83 - 93.

50. Назаров A.A., Одышев Ю.Д. Исследование сетей связи с протоколом «синхронная Алоха» в условиях большой загрузки // Автоматика и вычислительная техника, 2001. № 1. - С. 77 - 84.

51. Назаров A.A., Пичугин С.Б. Исследование спутниковой сети связи методом математического моделирования // Изв. вузов. Физика. 1992. - № 9. - С. 120-129.

52. Назаров A.A., Судыко Е.А. Исследование марковской RQ-системы с конфликтами заявок и простейшим входящим потоком // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2010. - № 3(12). - С. 97 - 106.

53. Назаров A.A., Судыко Е.А. Метод асимптотических семиинвариантов для исследования математической модели сети случайного доступа // Проблемы передачи информации. 2010. - Т. 46. - № 1. - С. 94 - 111.

54. Назаров A.A., Судыко Е.А. Неэргодичность математической модели компьютерной сети случайного доступа // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. 2011. -№3(36).-С. 62-65.

55. Назаров A.A., Судыко Е.А. Условия существования стационарного режима в немарковских RQ-системах с конфликтами заявок // Известия Томскогополитехнического университета. Управление, вычислительная техника и информатика.-2011.-Т. 318.-№ 5.-С. 166-168.

56. Назаров A.A., Терпугов А.Ф. Теория вероятностей и случайных процессов. Томск: Изд-во HTJI, 2006. - 204 с.

57. Назаров A.A., Терпугов А.Ф. Теория массового обслуживания. -Томск: Изд-во HTJI, 2004. 228 с.

58. Назаров A.A., Шохор C.JI. Исследование управляемого несинхронного множественного доступа в спутниковых сетях связи с оповещением о конфликте // Пробл. передачи инфор. 2000. - Т. 36, № 1 - С. 77 - 89.

59. Павский В.А. Лекции по теории вероятностей и элементам математической статистики: учеб. пособие для студентов технолог, специальностей /В.А. Павский. Кемерово: КемТИПП, 2005. - 184 с.

60. Павский В.А. Моделирование процесса очистки природных и сточных вод: монография / В.А. Павский, Ю.Л. Сколубович, Т.А. Краснова. Новосибирск: НГАСУ, 2005. - 144 с.

61. Ротенберг А.Р. Асимптотическое укрупнение состоянии некоторых стохастических автоматов// Проблемы передачи информации. 1973. - Т.9. -№ 4. - С. 66-70.

62. Русков П., Янев К., Димитров Б., Боянов К. Модель исследования локальных компьютерных сетей связи. // Конроль систем и машин. 1984. - № 5. -С. 37-40.

63. Саати Т.Л. Элементы теории массового обслуживания и ее приложения. 2-е изд. М.: Советское радио, 1971. - 519 с.

64. Степанов С.Н. Асимптотический анализ моделей с повторными вызовами в области больших потерь // Пробл. передачи информ. 1993. - № 3. -С. 54-75.

65. Судыко Е.А. Асимптотический анализ системы ММР | М11 с источником повторных вызовов // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2010. - № 4 (12). -С. 79-90.

66. Терпугов А.Ф. Теория случайных процессов. Томск: изд. Томск. Унта, 1974. -136 с.

67. Хинчин, А .Я. Работы по математической теории массового обслуживания /А.Я. Хинчин; под ред. Б.В. Гнеденко. М.: Наука, 1963. - 528 с.

68. Хомичков И.И. Исследование моделей локальной сети с протоколом случайного множественного доступа // АиТ. 1993. - № 12. - С. 89 - 90.

69. Хомичков И.И. Модель локальной сети с протоколом доступа CSMA/CD // Автоматика и вычислительная техника. 1988. - № 5. - С. 53 - 58.

70. Шварц М. Сети связи. Протоколы, моделирование и анализ. М.: Наука, 1992.

71. Шеннон Р. Имитационное моделирование систем. искусство и наука. -М.: Мир, 1978

72. Anisimov V.V., Atadzhanov Kh.L. Diffusion approximation of systems with repeated calls. // Theory of Probability and Mathematical Statistics. -1991. № 44.

73. Artalejo J.R. A Classified Bibliography of Research on Retrial Queues: Progress in 1990-1999 // Sociedad de Estadística e Investigación Operativa Top. -1999. Vol. 7, Issue 2. - P. 187 - 211.

74. Artalejo J.R. Accessible Bibliography on Retrial Queues // Mathematical and Computer Modeling. 1999. - Vol. 30, Issue 1 - 2. - P. 1 - 6.

75. Artalejo J.R. Accessible Bibliography on Retrial Queues: Progress in 20002009 // Mathematical and Computer Modeling. 2010. - Vol. 51. - P. 1071 - 1081.

76. Artalejo J.R., Chakravarthy S.R. Computational analysis of the maximal queue length in the MAP|M|c retrial queue, Applied Mathematics and Computation 183,2006-P. 1399-1409.

77. Artalejo J.R., Gomez-Coral A. Retrial queueing systems: A computational approach. Springer. Berlin. - 2008.

78. Boucherie R.J., Van Dijk N.M. On a Queuing Network Model for Cellular Telecommunication Networks // Operations Research . Jan/Feb, 2000. - Vol. 48, Issue 1.-P. 38-50.

79. Choi B.D., Shin Y.W., Ahn W.C. Retrial queues with collision arising from unslotted CSMA/CD protocol. // Queueing systems. 1992. - Vol. 11. - № 4. -P. 335-356.

80. Clare D.D., Pogran K.T., Reed D.P. An Introduction to Local Area Networks // Proc. IEEE. 1978. - Vol. 66, Issue 11. - P. 1497 - 1517.

81. Deul N. Stationary conditions for multi-server queueing systems with repeated calls. // Electronische Informationsverarbeitung und Kubernetik (Journal of Information processing and Cybernetics). 1980. - Vol. 18. - №№ 10 - 11. -P. 587-594.

82. Dudin A., Klimenok V. Queuing System BMAP|G|1 with Repeated Calls // Mathematical and Computer Modeling. 1999. - № 30. - P. 115 - 128.

83. Falin G.I. A diffusion approximation for retrial queueing systems. // Theory of Probability and Its Applications. 1991. - Vol. 36. - № 1. - p. 149 - 152.

84. Falin G.I. A Survey of Retrial Queues // Queuing Systems. 1990. -Vol. 7.-P. 127-167.

85. Falin G.I. Asymptotic investigation of fully available switching systems with high repetition intensity of blocked calls. // Moscow University Mathematics Bulletin. 1984. - Vol. 39. - № 6. - P. 72 - 77.

86. Falin G.I. Continuous approximation for a single server system with an arbitrary service time under repeated calls. // Engineering Cybernetics. 1984. - Vol. 22. - № 2. - P. 66-71.

87. Falin G.I. Limit theorems for queueing systems with repeated calls. // A paper presented at the 4th Int. Vilnius Conf. on Probability Theory and Mathematical Statistics. Vilnius. -1985.

88. Falin G.I. M|G|1 system with repeated calls in heavy traffic. //Moscow University Mathematics Bulletin. 1980. -Vol. 35. -№ 6. - P. 48 - 51.

89. Falin G.I. Multichannel Queuing System with Repeated Calls Under High Intensity of Repetition // Journal of Inform. Processing and Cybernetics. 1987. -№23.-P. 37-47.

90. Falin G.I. On ergodicity of multilinear queueing systems with repeated calls. // Soviet Journal of Computer and systems sciences. 1987. - Vol. 18. - № 4. -P. 60-65.

91. Falin G.I. On Sufficient Conditions for Ergodicity of Multichannel Queuing Systems with Repeated Calls // Advanced in Applied Probability. 1984. -Vol. 16.-P. 447-448.

92. Falin G.I. Single-line Repeated Order Queuing Systems // Optimization. 1986. - Vol. 17. - P. 649 - 667.

93. Falin G.I., Artalejo J.R. A Finite Source Retrial Queue // European Journal of Operation Research. 1998. - № 108. - P. 409 - 424.

94. Falin G.I., Artalejo J.R., Martin M. One the Single Server Retrial Queue with Priority Customers // Queuing Systems. 1993. - № 14. - P. 439 - 455.

95. Falin G.I., Sukharev Yu.I. On single-line queue with double connections. // All-Union Institute for Scientific and Technical Information, Moscow. 1985.

96. Falin G.I., Tempeton J.G.C. Retrial Queues. London: Chapman and Hall, 1997.-328 p.

97. Foster F.C. On the Stochastic Matrices Associated with Certain Queuing Processes // Ann. Math. Stat. 1953. - Vol. 24. - P. 355 - 360.

98. Hanschke T. Explicit formulas for the characteristics of the M|M|2|2| queue with repeated attempts. // Journal of applied probability. 1987. - № 24. -P. 486-494.

99. Jonin G.L., Sedol J.J. Telephone systems with repeated calls // A paper presented at 6th International Teletraffic Congress, Munich. -1970.

100. Kernane T. Conditions for stability and instability of retrial queueing systems with general retrial times // Statistics and Probability Letters. 2008. - № 78. -P. 3244-3248. .

101. Krishna Kumar B., Vijayalakshmi G., Krishnamoorthy A., Sadiq Basha S. A single server feedback retrial queue with collisions. // Computer and operations research. 2010. - № 37. - P. 1247 - 1255.

102. Lukashuk L.I. Diffusion approximation and filtering for a queuing system with repeats. // Cybernetics. 1990. - № 2. - P. 253 - 264.

103. Moustafa M.D. Input-Output Markov Processes // Proc. Koninkijke Nederlande Akad. Wetenshappen. 1957. - Vol. 60. - P. 112 - 118.

104. Riordan J. Stochastic service systems. Wiley, New York. - 1962.

105. Sennot L.I., Humblet P.A., Tweedie R.L. Mean drifts and the non-ergodicity of markov chains // Operations research. 1983. - № 31 (4). -P. 783 - 789.

106. Stepanov S.N. Asymptotic Analysis of Models with Repeated Calls in Case of Extreme Load // Problems of Inform. Transmission. 1993. - Vol. 29, Issue 3.-P. 54-75.

107. Stepanov S.N. Generalized Model with Repeated Calls in Case of Extreme Load // Queuing Systems. 1997. - № 27. - P. 131 - 151.

108. Stepanov S.N. Markov Models with Retrials: The Calculation of Stationary Performance Measures Based on the Concept of Truncation // Mathematical and Computer Modeling. 1999. - Vol. 30. - P. 207 - 228.

109. Stepanov S.N. Numerical Calculation Accuracy of Communication

110. Models with Repeated Calls // Problems of Control and Inform. Theory. 1985. - № 14.-P. 25-32.

111. Syski R. A personal view of queueing theory // Frontiers in Queueing Vodels and Applications in Science and Engineering/ Boca Raton: CRC. 1997.

112. Vo-Dai T. A Throughput-Delay Analysis of CSMA-CD // INFOR. -1987. Vol. 25, Issue 4. - P. 287 - 301.

113. Yang, T. and Templeton, J. G. C. A survey on retrial queues. // Queueing Systems: Theory and Applications. 1987. - № 3. - P.201 - 233.1. P.13-18.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00