МНОГОЛИНЕЙНЫЕ RQ-СИСТЕМЫ С НЕТЕРПЕЛИВЫМИ ЗАЯВКАМИ
|
РЕФЕРАТ 3
Введение 7
1 Асимптотический анализ однолинейной RQ-системы вида М|М|1 с
нетерпеливыми заявками в условии долгой терпеливости 10
1.1 Постановка задачи 10
1.2 Метод асимптотического анализа первого порядка 12
2 Асимптотический анализ двухлинейной RQ-системы вида М|M|2 с
нетерпеливыми заявками в условии долгой терпеливости 14
2.1 Постановка задачи 14
2.2 Метод асимптотического анализа первого порядка 17
2.3 Метод асимптотического анализа второго порядка 19
3 Асимптотический анализ многолинейной RQ-системы вида М|M|N с
нетерпеливыми заявками в условии долгой терпеливости 24
3.1 Постановка задачи 24
3.2 Метод асимптотического анализа первого порядка 27
3.3 Метод асимптотического анализа второго порядка 29
4 Асимптотический анализ двухлинейной RQ-системы ММРР|M|2 с
нетерпеливыми заявками в условии долгой терпеливости 35
4.1 Постановка задачи 35
4.2 Метод асимптотического анализа первого порядка 39
4.3 Метод асимптотического анализа второго порядка 41
5 Численные результаты 45
5.1 Имитационное моделирование для RQ-системы вида M|M|N 46
5.2 Имитационное моделирование для RQ-системы вида MМРР|M|2 52
Заключение 58
Литература 60
Введение 7
1 Асимптотический анализ однолинейной RQ-системы вида М|М|1 с
нетерпеливыми заявками в условии долгой терпеливости 10
1.1 Постановка задачи 10
1.2 Метод асимптотического анализа первого порядка 12
2 Асимптотический анализ двухлинейной RQ-системы вида М|M|2 с
нетерпеливыми заявками в условии долгой терпеливости 14
2.1 Постановка задачи 14
2.2 Метод асимптотического анализа первого порядка 17
2.3 Метод асимптотического анализа второго порядка 19
3 Асимптотический анализ многолинейной RQ-системы вида М|M|N с
нетерпеливыми заявками в условии долгой терпеливости 24
3.1 Постановка задачи 24
3.2 Метод асимптотического анализа первого порядка 27
3.3 Метод асимптотического анализа второго порядка 29
4 Асимптотический анализ двухлинейной RQ-системы ММРР|M|2 с
нетерпеливыми заявками в условии долгой терпеливости 35
4.1 Постановка задачи 35
4.2 Метод асимптотического анализа первого порядка 39
4.3 Метод асимптотического анализа второго порядка 41
5 Численные результаты 45
5.1 Имитационное моделирование для RQ-системы вида M|M|N 46
5.2 Имитационное моделирование для RQ-системы вида MМРР|M|2 52
Заключение 58
Литература 60
Жизнь современного поколения сложно представить без использования средств связи и систем передачи данных. Еще двадцать лет назад люди и представить себе не могли, что мир может стать настолько информационным. Современные технологии с каждым годом охватывают все больше сфер человеческой деятельности. Однако необходимо понимать, что с увеличением объема информации, дальности и качества связи, требования к технологиям возрастают, а это в свою очередь создает необходимость их оптимизировать.
Для того чтобы оптимизировать столь масштабные информационные и технические сети, на каждый тип реальной системы строится своя индивидуальная математическая модель. Математическое представление структуры работы сложных систем стало возможным благодаря системам массового обслуживания. Такое представление способно передать процесс функционирования системы с достаточной для практики точностью.
Появление теории массового обслуживания было бы невозможным без трудов гениального российского математика Андрея Андреевича Маркова. Впервые А.А. Марков сформировал математические основы для построения моделей, которые отражают специфику работы сложных технических, информационных и экономических систем. Такие системы называются системами массового обслуживания (СМО).
Последователи А.А. Маркова [1-17] далеко вперед продвинули границы применения теории массового обслуживания, что позволяет решать многие задачи прогнозирования поведения сложных систем.
Для решения задач, связанных с оптимизацией телефонных систем связи, была разработана теория телетрафика, основоположником которой считается датский математик А.К. Эрланг [18]. Именно на результаты А.К. Эрланга ссылаются специалисты, занимающиеся исследованиями телекоммуникационных систем, сетей мобильной связи, call-центров и др. [19, 20].
Одной из трудных проблем, связанных с построением моделей массового обслуживания для сетевых систем, является учет фактора обращений повторных заявок. Классические модели систем массового обслуживания подразумевают, что заявка, застав обслуживающий прибор занятым, встает в очередь или покидает систему. Чаще на практике возникают ситуации, когда заявки, не обслужившись, не уходят из системы, а осуществляют случайную задержку. Такие системы в русскоязычной литературе называются СМО с орбитой, а в англоязычной - RQ-системами (Retrial queueing system). Детальное описание RQ-систем и результаты их исследований представлены в монографиях Г.И. Фалина [21], Дж. Арталехо, [22], а также учебных пособиях [23-25] и научных работах А.А. Назарова [26-28], Е.А. Федоровой [29-31], А.А. Анисимовой [32] и др.
Характерной чертой RQ-систем является наличие повторных обращений заявок к обслуживающему прибору спустя некоторое случайное время после неудачной попытки получить обслуживание. Такие ситуации могут быть вызваны не только отсутствием свободных серверов в моменты поступления заявок, но и некоторыми техническими причинами [33]. В RQ-системах, как и в реальных системах связи, чаще происходит ситуация, когда заявка, застав обслуживающий прибор занятым, отправляется на орбиту.
Существует достаточно большое число работ, посвященных RQ-системам с нетерпеливыми заявками. Однако в большинстве из них нетерпеливость понимается в том смысле, что заявка с определенной вероятностью уходит из орбиты после неудачной попытки обслуживания. В настоящей работе под нетерпеливыми заявками понимаются заявки, находящиеся на орбите, которые через случайное время, распределенное по экспоненциальному закону, могут покинуть систему, не обращаясь к прибору с повторной попыткой его захвата [34,35]. Предложенная в выпускной квалификационной работе модель ранее не исследовалась, что отражает научную новизну полученных результатов.
В качестве методов исследования RQ-систем широко применяются асимптотические методы, позволяющие получить приемлемые для практики асимптотические выражения для искомых характеристик системы в случаях, когда их допредельное исследование невозможно. Различные асимптотические методы и подходы в теории массового обслуживания описаны в работах [36,37].
Цель работы: провести исследование многолинейных RQ-систем вида M|M|N (в частности, M|M|1, M|M|2) и MMPP|M|2 методом асимптотического анализа первого и второго порядков и получить стационарное распределение числа заявок на орбите для указанных многолинейных RQ-систем.
Задачи:
1. Построить и исследовать математическую модель RQ-системы вида M|M|N (в частности, M|M|1, M|M|2) методом асимптотического анализа первого и второго порядков при условии высокой загрузки и долгой терпеливости.
2. Найти вид асимптотической характеристической функции числа заявок на орбите для RQ-системы вида M|M|N (в частности, M|M|1, M|M|2).
3. Провести численный анализ исследуемой RQ-системы вида M|M|N (в частности, M|M|1, M|M|2). Определить область применимости полученных асимптотических результатов.
4. Построить и исследовать математическую модель RQ-системы вида MМРР|M|2 методом асимптотического анализа первого и второго порядков при условии высокой загрузки и долгой терпеливости.
5. Найти вид асимптотической характеристической функции числа заявок на орбите для RQ-системы вида MМРР|M|2.
6. Провести численный анализ исследуемой RQ-системы вида MМРР|M|2. Определить область применимости полученных асимптотических результатов.
Для того чтобы оптимизировать столь масштабные информационные и технические сети, на каждый тип реальной системы строится своя индивидуальная математическая модель. Математическое представление структуры работы сложных систем стало возможным благодаря системам массового обслуживания. Такое представление способно передать процесс функционирования системы с достаточной для практики точностью.
Появление теории массового обслуживания было бы невозможным без трудов гениального российского математика Андрея Андреевича Маркова. Впервые А.А. Марков сформировал математические основы для построения моделей, которые отражают специфику работы сложных технических, информационных и экономических систем. Такие системы называются системами массового обслуживания (СМО).
Последователи А.А. Маркова [1-17] далеко вперед продвинули границы применения теории массового обслуживания, что позволяет решать многие задачи прогнозирования поведения сложных систем.
Для решения задач, связанных с оптимизацией телефонных систем связи, была разработана теория телетрафика, основоположником которой считается датский математик А.К. Эрланг [18]. Именно на результаты А.К. Эрланга ссылаются специалисты, занимающиеся исследованиями телекоммуникационных систем, сетей мобильной связи, call-центров и др. [19, 20].
Одной из трудных проблем, связанных с построением моделей массового обслуживания для сетевых систем, является учет фактора обращений повторных заявок. Классические модели систем массового обслуживания подразумевают, что заявка, застав обслуживающий прибор занятым, встает в очередь или покидает систему. Чаще на практике возникают ситуации, когда заявки, не обслужившись, не уходят из системы, а осуществляют случайную задержку. Такие системы в русскоязычной литературе называются СМО с орбитой, а в англоязычной - RQ-системами (Retrial queueing system). Детальное описание RQ-систем и результаты их исследований представлены в монографиях Г.И. Фалина [21], Дж. Арталехо, [22], а также учебных пособиях [23-25] и научных работах А.А. Назарова [26-28], Е.А. Федоровой [29-31], А.А. Анисимовой [32] и др.
Характерной чертой RQ-систем является наличие повторных обращений заявок к обслуживающему прибору спустя некоторое случайное время после неудачной попытки получить обслуживание. Такие ситуации могут быть вызваны не только отсутствием свободных серверов в моменты поступления заявок, но и некоторыми техническими причинами [33]. В RQ-системах, как и в реальных системах связи, чаще происходит ситуация, когда заявка, застав обслуживающий прибор занятым, отправляется на орбиту.
Существует достаточно большое число работ, посвященных RQ-системам с нетерпеливыми заявками. Однако в большинстве из них нетерпеливость понимается в том смысле, что заявка с определенной вероятностью уходит из орбиты после неудачной попытки обслуживания. В настоящей работе под нетерпеливыми заявками понимаются заявки, находящиеся на орбите, которые через случайное время, распределенное по экспоненциальному закону, могут покинуть систему, не обращаясь к прибору с повторной попыткой его захвата [34,35]. Предложенная в выпускной квалификационной работе модель ранее не исследовалась, что отражает научную новизну полученных результатов.
В качестве методов исследования RQ-систем широко применяются асимптотические методы, позволяющие получить приемлемые для практики асимптотические выражения для искомых характеристик системы в случаях, когда их допредельное исследование невозможно. Различные асимптотические методы и подходы в теории массового обслуживания описаны в работах [36,37].
Цель работы: провести исследование многолинейных RQ-систем вида M|M|N (в частности, M|M|1, M|M|2) и MMPP|M|2 методом асимптотического анализа первого и второго порядков и получить стационарное распределение числа заявок на орбите для указанных многолинейных RQ-систем.
Задачи:
1. Построить и исследовать математическую модель RQ-системы вида M|M|N (в частности, M|M|1, M|M|2) методом асимптотического анализа первого и второго порядков при условии высокой загрузки и долгой терпеливости.
2. Найти вид асимптотической характеристической функции числа заявок на орбите для RQ-системы вида M|M|N (в частности, M|M|1, M|M|2).
3. Провести численный анализ исследуемой RQ-системы вида M|M|N (в частности, M|M|1, M|M|2). Определить область применимости полученных асимптотических результатов.
4. Построить и исследовать математическую модель RQ-системы вида MМРР|M|2 методом асимптотического анализа первого и второго порядков при условии высокой загрузки и долгой терпеливости.
5. Найти вид асимптотической характеристической функции числа заявок на орбите для RQ-системы вида MМРР|M|2.
6. Провести численный анализ исследуемой RQ-системы вида MМРР|M|2. Определить область применимости полученных асимптотических результатов.
В выпускной квалификационной работе были исследованы системы с повторными вызовами (RQ-системы) вида M|M|1, M|M|2, M|M|N, MMPP|M|2 с нетерпеливыми заявками на орбите. Для каждой из этих систем:
1) построена математическая модель и составлена система дифференциальных уравнений Колмогорова;
2) найдена асимптотика первого и второго порядков с помощью метода асимптотического анализа при условии высокой загрузки системы и долгой терпеливости заявок на орбите;
3) найден вид характеристической функции числа заявок на орбите при асимптотическом условии долгой терпеливости заявок на орбите и высокой загрузки системы. Сделан вывод о том, что стационарное распределение числа заявок на орбите для RQ-систем вида M|M|1, M|M|2, M|M|N, MMPP|M|2 является асимптотически гауссовским
4) проведен численный анализ, подтверждающий теоретические выводы; определена область применимости полученных асимптотических результатов.
Результаты бакалаврской работы докладывались и обсуждались на следующих всероссийских и международных конференциях:
1. Международная научная студенческая конференция (МНСК-2017),
г. Новосибирск, 17-20 апреля 2017 г. [34];
2. V-я Международная молодежная научная конференция «Математическое и программное обеспечение информационных, технических и экономических систем», г. Томск, 19-20 мая 2017 года [38];
3. Молодежная научная школа по прикладной теории вероятностей и телекоммуникационным технологиям «АРТСТ-2017», г. Москва, 23-27 октября 2017 г. [35];
4. Международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2018», г. Москва, 9-13 апреля 2018 г. [39];
5. Международная научная студенческая конференция (МНСК-2018),
г. Новосибирск, 22-27 апреля 2018 г. (доклад на тему «Исследование
двухлинейной RQ-системы вида М|М|2 с помощью метода асимптотического анализа» находится в печати);
6. VI-я Международная молодежная научная конференция
«Математическое и программное обеспечение информационных, технических и экономических систем», г. Томск, 24-26 мая 2018 г. (доклад на тему
«Асимптотический анализ двухлинейной RQ-системы вида ММРР|М|2 с нетерпеливыми заявками в условии долгой терпеливости» находится в печати);
7. Daniluyk E. Retrial queue М|М|Ы with impatient customer in the orbit // E. Daniluyk, O. Vygovskaya, S. Moiseeva / Communications in computer and information Science (CCIS). -Springer. -2018. (находится в печати) [40].
1) построена математическая модель и составлена система дифференциальных уравнений Колмогорова;
2) найдена асимптотика первого и второго порядков с помощью метода асимптотического анализа при условии высокой загрузки системы и долгой терпеливости заявок на орбите;
3) найден вид характеристической функции числа заявок на орбите при асимптотическом условии долгой терпеливости заявок на орбите и высокой загрузки системы. Сделан вывод о том, что стационарное распределение числа заявок на орбите для RQ-систем вида M|M|1, M|M|2, M|M|N, MMPP|M|2 является асимптотически гауссовским
4) проведен численный анализ, подтверждающий теоретические выводы; определена область применимости полученных асимптотических результатов.
Результаты бакалаврской работы докладывались и обсуждались на следующих всероссийских и международных конференциях:
1. Международная научная студенческая конференция (МНСК-2017),
г. Новосибирск, 17-20 апреля 2017 г. [34];
2. V-я Международная молодежная научная конференция «Математическое и программное обеспечение информационных, технических и экономических систем», г. Томск, 19-20 мая 2017 года [38];
3. Молодежная научная школа по прикладной теории вероятностей и телекоммуникационным технологиям «АРТСТ-2017», г. Москва, 23-27 октября 2017 г. [35];
4. Международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2018», г. Москва, 9-13 апреля 2018 г. [39];
5. Международная научная студенческая конференция (МНСК-2018),
г. Новосибирск, 22-27 апреля 2018 г. (доклад на тему «Исследование
двухлинейной RQ-системы вида М|М|2 с помощью метода асимптотического анализа» находится в печати);
6. VI-я Международная молодежная научная конференция
«Математическое и программное обеспечение информационных, технических и экономических систем», г. Томск, 24-26 мая 2018 г. (доклад на тему
«Асимптотический анализ двухлинейной RQ-системы вида ММРР|М|2 с нетерпеливыми заявками в условии долгой терпеливости» находится в печати);
7. Daniluyk E. Retrial queue М|М|Ы with impatient customer in the orbit // E. Daniluyk, O. Vygovskaya, S. Moiseeva / Communications in computer and information Science (CCIS). -Springer. -2018. (находится в печати) [40].