Содержание к диссертации
Введение
1. Анализ моделей функционирования цов 13
1.1. Необходимость математического описания работы цов 13
1.2. Сравнение телефонного и мультисервисного ЦОВ 15
1.2.1. Недостатки телефонного ЦОВ 15
1.2.2. Преимущества мультисервисного ЦОВ 19
1.2.3. Сравнение процессов обслуживания вызова в ЦОВ и МЦОВ 24
1.3. Существующие модели и методы исследования мцов 29
1.3.1. «Классические» модели ЦОВ 29
1.3.2. Модели ЦОВ с нетерпеливостью пользователей 34
1.3.3. Модели ЦОВ с нестационарностыо характеристик 36
1.3.4. Модели ЦОВ с повторными вызовами 39
1.3.5. Приоритетные модели ЦОВ 41
1.3.6. Модели ЦОВ для расчета операторов 43
1.3.7. Аппроксимационные модели ЦОВ 44
1.4. Выводы 48
2. Разработка математической модели мцов 51
2.1. Учет в модели особенностей функционирования мцов 51
2.2. Описание модели мцов 54
2.3. Выводы 67
3. Оценка качественных характеристик функционирования МЦОВ 68
3.1. Расчет параметров качества функционирования мцов 68
3.1.1. Расчет времени ожидания для высокоприоритетных вызовов 69
3.1.2. Расчет времени ожидания для низкоприоритетных вызовов 75
3.2. Расчет числа операторов 80
3.3. Управление переходами низкоприоритетных вызовов в высокоприоритетную очередь 81
3.4. Исследование влияния параметров модели на вероятностно-временные характеристики мцов 83
3.5. Выводы 94
4. Имитационное моделирование процесса функционирования МЦОВ 96
4.1. Описание имитационной модели мцов 96
4.1.1. Генератор случайных чисел 97
4.1.2. Процесс представления времени в имитационной модели 100
4.1.3. Процесс поступления вызовов в МЦОВ 101
4.1.4. Процесс ухода вызовов из МЦОВ 103
4.1.5. Процесс ухода вызовов из-за нетерпеливости пользователей 104
4.1.6. Процесс перехода вызовов в высокоприоритетную очередь 104
4.1.7. Процесс ожидания вызовов в очереди 105
4.1.8. Расчет времени ожидания 106
4.1.9. Расчет характеристик качества обслуживания 108
4.2. Результаты моделирования 112
4.2.1. Исходные данные для имитационной модели 112
4.2.2. Сравнение результатов расчетов для исходного МЦОВ 116
4.2.3. Сравнение результатов расчетов для МЦОВ при r| = 20 122
4.3. Оценка точности имитационного моделирования 129
4.4. Выводы 135
Заключение 136
Литература
- Сравнение телефонного и мультисервисного ЦОВ
- Учет в модели особенностей функционирования мцов
- Расчет времени ожидания для низкоприоритетных вызовов
- Процесс представления времени в имитационной модели
Введение к работе
Актуальность темы
Одним из перспективных направлений развития информационных услуг является организация центров обслуживания вызовов (ЦОВ), ориентированных на оказание услуг широкому кругу пользователей. ЦОВ интенсивно внедряются за рубежом и в Российской Федерации [1, 2].
Происходящая в последнее время конвергенция телефонной и компьютерной индустрии, появление сетей следующего поколения NGN обусловили появление мультисервисных ЦОВ (МЦОВ), обладающих несравненно большим набором услуг и возможностями. МЦОВ обеспечивают обработку вызовов, передаваемых как по телефонным, так и по пакетным сетям (Интернету, сетям IP-телефонии). Потребность в расширении спектра предоставляемых информационных услуг постоянно растет почти во всех сферах применения МЦОВ. Прежде всего, это касается таких услуг, как обслуживание по электронной почте, совместный просмотр веб-страниц компании и текстовый диалог (чат).
В настоящее время имеется достаточно большое количество публикаций по тематике ЦОВ, особенно за рубежом. Здесь следует отметить работы таких авторов, как A. Mandelbaum, W. Whitt, G. Koole, M. Reiman и др. В России в последнее время также появились первые работы в данном направлении, прежде всего Б.С. Гольдштейна, А.В. Рослякова и их учеников [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]. Защищены кандидатские диссертации (А.А. Зарубиным и М.Н. Беловым), посвященные исследованиям отдельных математических моделей ЦОВ [26, 27]. Однако в большинстве работ анализируются телефонные ЦОВ и используются подходы на основе «классической» теории массового обслуживания [28, 29, 30]. Математические модели современных МЦОВ должны учитывать такие факторы, как наличие нескольких классов вызовов,
7 различные дисциплины обслуживания заявок, нетерпеливость пользователей, повторные вызовы, нестационарность характеристик и др., что существенно усложняет их анализ.
В связи с этим, актуальной является задача анализа вероятностно-временных характеристик (ВВХ) МЦОВ, влияющих на качество обслуживания вызовов с учетом явлений, свойственных современным МЦОВ.
Объект исследования
Объектом исследования являются мультисервисные центры обслуживания вызовов.
Цель работы и задачи исследования
Цель диссертации состоит в повышении уровня обслуживания пользователей и снижении эксплутационных расходов МЦОВ путем разработки моделей МЦОВ, учитывающих «нетерпеливость» пользователей, наличие приоритетов между различными классами вызовов и нестационарность характеристик.
Поставленная цель определила необходимость решения следующих задач:
разработка формализованного математического описания исследуемого объекта - МЦОВ;
разработка аналитической модели процесса функционирования МЦОВ с возможностью совместного обслуживания различных классов вызовов с учетом динамических приоритетов между ними, «нетерпеливости» пользователей и нестационарности характеристик;
разработка метода расчета ВВХ МЦОВ, с возможностью определения оптимального количества операторов;
разработка рекомендаций по расчету параметров функционирования МЦОВ;
разработка имитационной модели функционирования МЦОВ для получения зависимостей между основными параметрами МЦОВ и качеством обслуживания вызовов различных классов.
Методы исследования
Исследования базировались на методах теории вероятностей, теории массового обслуживания, теории аппроксимации, вычислительной математики и имитационного моделирования.
Научная новизна
Научная новизна диссертационной работы заключается в следующем:
разработана математическая модель функционирования МЦОВ с тремя классами вызовов, позволяющая получать аналитическую оценку ВВХ МЦОВ с учетом динамических приоритетов между вызовами, отказов от обслуживания как следствие «нетерпеливости» пользователей и нестационарности параметров МЦОВ;
разработан аналитический метод расчета параметров МЦОВ с использованием непрерывной и диффузионной аппроксимаций;
разработана методика определения оптимального количества операторов в модели МЦОВ с тремя классами вызовов, где учитываются динамические приоритеты, отказы от обслуживания из-за «нетерпеливости» пользователей и нестационарность характеристик;
разработан алгоритм управления переходами низкоприоритетных вызовов в высокоприоритетную очередь;
разработана имитационная модель МЦОВ, позволяющая проводить оценку основных ВВХ МЦОВ.
Личный вклад
Теоретические и практические исследования, аналитические расчеты и проведенное имитационное моделирование на ЭВМ, а также выводы и рекомендации получены автором лично.
Практическая ценность работы и реализация результатов работы
Полученные методы, формулы, алгоритмы и модели позволяют произвести оценку ВВХ МЦОВ с учетом обслуживания нескольких классов вызовов, улучшить качественные показатели функционирования МЦОВ, сократить штат операторов центра и уменьшить задержки при обслуживании высокоприоритетных телефонных вызовов. Это позволяет эффективно решить проблему проектирования МЦОВ, управления его работой в процессе эксплуатации и добиться положительного экономического эффекта.
Результаты могут быть использованы научно-исследовательскими, проектными и эксплутационными организациями при разработке, проектировании, внедрении новых и усовершенствовании существующих МЦОВ.
Основные теоретические и практические результаты, полученные в работе, использованы в MP «Поволжье Юго-Восток» ОАО «Мобильные ТелеСистемы», Группе компаний «СТАРТ» (г. Москва) и внедрены в учебный процесс в ГОУВПО ПГАТИ, что подтверждено соответствующими актами.
Апробация работы
Основное содержание работы докладывалось и обсуждалось на 5-й Международной конференции молодых ученых и студентов (Самара, 2004),
10 XII и XIII российских научных конференциях профессорско-преподавательского состава, научных сотрудников и аспирантов (Самара, ПГАТИ, 2005-2006), 1-м Международном форуме молодых ученых и студентов «Актуальные проблемы современной науки» (Самара, 2005), Шестой международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (Уфа, 2005).
Публикации
По теме диссертации опубликовано 14 работ, в том числе одна монография (336 с), 1 статья в журнале из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных работ, 2 статьи в научных изданиях и 10 тезисов докладов.
Основные положения, выносимые на защиту
функциональная модель МЦОВ, отражающая принципы поступления и обслуживания вызовов различных классов;
математическая модель МЦОВ, учитывающая динамические приоритеты для низкоприоритетных различных классов вызовов, «нетерпеливость» высокоприоритетных вызовов, нестационарность характеристик;
алгоритм управления переходами низкоприоритетных вызовов в высокоприоритетную очередь
методика определения оптимального количества операторов в модели МЦОВ с тремя классами вызовов;
анализ ВВХ рассматриваемого МЦОВ средствами имитационного моделирования на ЭВМ
Структура и объем работы
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 157 страниц машинописного текста, 59 рисунков, 4 таблицы. В списке литературы 165 наименований.
В первой главе производится анализ объекта исследования и существующих математических моделей, которые описывают процесс его функционирования.
При анализе МЦОВ показаны основные принципы его функционирования, рассмотрены архитектуры построения телефонного и мультисервисного ЦОВ, проведен сравнительный анализ процессов обслуживания вызовов в ЦОВ и МЦОВ. На основании данного анализа показаны основные преимущества использования современных МЦОВ по сравнению с ЦОВ, обслуживающих один класс вызовов.
Показано, что существующие в настоящее время математические модели и методы расчета характеристик качества обслуживания вызовов развиты для центров, оперирующих только телефонными вызовами. С другой стороны, анализ «классических» математических моделей, описывающих процесс функционирования ЦОВ, показал, что они уже не способны адекватно отражать принцип функционирования современных МЦОВ. Наиболее существенные недостатки таких моделей вытекают из предположений об однотипности поступающих вызовов, стационарности характеристик и бесконечной терпеливости пользователей. В случае расхождения условий рассматриваемой модели с реальными условиями функционирования МЦОВ расчет характеристик на основе существующих моделей может оказаться весьма неточным.
Во второй главе разработана аналитическая модель МЦОВ, позволяющая учитывать три класса вызовов, «нетерпеливость»
12 высокоприоритетных вызовов, динамические приоритеты для низкоприоритетных вызовов и нестационарность параметров МЦОВ. При этом использовались методы непрерывной и диффузионной аппроксимации.
В третьей главе получены выражения для расчета наиболее важной характеристики качества функционирования МЦОВ - времени ожидания разных классов вызовов. Разработан алгоритм для определения оптимального количества операторов в соответствии с качеством обслуживания различных классов вызовов, которое определяется как процент вызовов, ожидающих в очереди меньше определенного времени. Проведено исследование влияния параметров модели МЦОВ на ВВХ МЦОВ. На основании результатов расчетов были предложены рекомендации по выбору параметров функционирования МЦОВ и определены закономерности, учет которых позволяет повысить эффективность функционирования центра.
Четвертая глава содержит экспериментальное исследование ВВХ МЦОВ на основе дискретно-событийного моделирования. Приводится описание основных компонентов имитационной модели.
На основании сравнения с результатами имитационного моделирования сделаны выводы о точности аналитических моделей. При этом был определен достаточный объем серий испытаний и испытаний внутри серий, а также использованы методы доверительного интервального оценивания, которые предлагают подходящую альтернативу критериям значимости применительно к задачам инженерного расчета.
В приложении содержатся акты внедрения результатов диссертации.
Сравнение телефонного и мультисервисного ЦОВ
Центры обслуживания вызовов (ЦОВ), и их современные преемники -мультисервисные центры обслуживания вызовов (МЦОВ) или как их ещё называют - контакт-центры, уже давно стали общепризнанным и преобладающим средством общения компании со своими клиентами [28, 29, 30]. Большинство организаций, работающих с клиентами, а это могут быть как частные компании, так и правительственные и экстренные службы, переоснастили свою инфраструктуру, которая может включать один или несколько распределенных ЦОВ. Они могут находиться во внутреннем ведении фирмы, либо предоставлять свои ресурсы для других компаний (так называемый аутсорсинг). Для многих компаний, таких как авиакомпании, гостиницы, коммерческие банки и банки кредитно-карточной системы, ЦОВ предоставляют выделенную линию между потребителем и поставщиком.
Качество и эффективность работы современных крупных ЦОВ поражают воображение. В таком ЦОВ несколько сотен операторов могут обслужить до тысячи разнообразных вызовов за час; уровень эффективности работы оператора может достигать 90-95%; ни одна заявка не остается без обслуживания и, фактически, около половины различных заявок обслуживаются немедленно; время ожидания задержанных вызовов измеряется секундами, а доля вызовов, покинувших систему при ожидании, колеблется в пренебрежимо малых пределах: 1-2%.
Представившему эту картину может показаться, что структура и управление большинства ЦОВ основаны на строгих и сложных научных принципах. Но, в действительности, программное обеспечение, которым зачастую поддерживается их работа, оперирует лишь простейшими аналитическими моделями. Эти модели, конечно, сильно повлияли на развитие ЦОВ, но в наше время они становятся не актуальными. Для повышения качества обслуживания вызовов и эффективности функционирования ЦОВ требуются более детальные и глубокие подходы.
Продолжающийся рост как экономической роли, так и сложности ЦОВ побудил исследователей к углублению и усовершенствованию математического аппарата моделей, описывающих центры. Свидетельством тому является увеличивающееся количество публикаций по данной тематике в зарубежных и отечественных периодических изданиях, на сайтах в сети Интернет. На повестку дня встают конкретные вопросы у тех, кто хочет использовать эту технологию на практике: сколько надо иметь рабочих мест операторов в центре, какое количество телефонных линий подключить, каковы будут параметры качества обслуживания вызовов центром, как эффективно организовать работу операторов и т.д. В силу специфики функционирования таких центров (случайный характер поступления вызовов, случайное время обслуживания вызова оператором, наличие сложных приоритетных дисциплин обслуживания и др.) для решения данных задач необходимо использовать сложные математические модели и методики [31,32,33].
Иногда возникает вопрос: а зачем же нужно настолько глубоко «влезать» в математические принципы функционирования ЦОВ, если многие математические модели уже интегрированы в существующее программное обеспечение ЦОВ? Ответ лежит в области поддержки работоспособности ЦОВ и оперативного принятия решений. Ни одна компьютерная система пока не может полностью автоматизировать сложные процедуры планирования, управления и оперативного составления расписания работы операторов. В работу ЦОВ требуется периодическое вмешательство человека, а оно возможно только при понимании принципов работы программного обеспечения и смысла математических формул, в него заложенных. В этом смысле понимание менеджерами ЦОВ математического аппарата только увеличивает эффективность программного обеспечения. С другой стороны, программное обеспечение ЦОВ способно выполнять некоторые сложные операции самостоятельно. Например, маршрутизация вызовов является полностью автоматизированной. Однако и здесь зачастую требуется понимание динамики работы ЦОВ и возможность принятия правильного решения относительно алгоритма маршрутизации. Это возможно, опять же, только при понимании математических принципов работы ЦОВ.
Стоит сказать, что, несмотря на относительно большой возраст технологии ЦОВ, терминология в отечественной литературе до сих пор не устоялась. ЦОВ называют по-разному, мешая при этом русские и английские слова, и, пожалуй, за 10 с лишним лет существования индустрии ЦОВ перечень названий практически не уменьшился - их называют операторскими центрами, кол-центрами, call-центрами, центрами обработки обращений, контакт-центрами, центрами обработки вызовов и др. В диссертации при анализе математических моделей простых телефонных центров используется аббревиатура ЦОВ, принятая в Руководящем документе отрасли связи РД 45.191-2001 «Центры обслуживания вызовов. Общие технические требования» (утверждены Минсвязи РФ 05.10.2001г.). При анализе мультисервисных центров используется обозначение МЦОВ.
Хотя во многом эффективность работы ЦОВ определяется человеческим фактором - уровнем подготовки и квалификации операторов и менеджеров, - необходимо также уделить внимание технической стороне дела [28, 29,30, 34,35].
Учет в модели особенностей функционирования мцов
Количество вызовов, поступающих на МЦОВ, меняется в течение всего дня. Для обслуживания различных вызовов в минимально возможное время требуется определенное количество операторов. К счастью, некоторые типы вызовов не требуют быстрого ответа и могут быть обслужены через некоторое время. Например, телефонные звонки имеют самый высокий приоритет и должны быть обслужены в течение нескольких секунд или минут, ответы на электронную почту или факс могут быть отложены на несколько часов или даже дней. Таким образом, различным типам вызовов можно присвоить различные приоритеты в обслуживании, соответствующие их чувствительности к времени ожидания. Чем меньше должна быть задержка, тем больше приоритет вызова при обслуживании. С учетом различных типов вызовов можно значительно повысить эффективность функционирования ЦОВ путем распределения нагрузки в течение всего дня -в периоды низкой загруженности операторы МЦОВ могут обслуживать низкоприоритетный трафик [148, 149].
В соответствии с рис. 1.7 наиболее популярными запросами являются (по убыванию): - телефонные, - электронная почта, - web-запросы, - текстовый чат.
Очевидно, что наивысший приоритет среди различных классов вызовов должны иметь телефонные вызовы, которые обрабатываются в реальном масштабе времени. Только после их обслуживания на очереди должны стоять запросы из сети Интернет, такие как текстовый чат, электронная почта или web-запросы. Наименьший приоритет имеют отложенные запросы в виде электронной почты. Ответы на такие запросы могут поступать в течении, например, 24 часов. Web-запросы и текстовый чат не такие требовательные, как телефонные вызовы, но и не терпят длительного ожидания. Поэтому все классы вызовов, поступающих на МЦОВ, можно классифицировать относительно масштаба времени, требуемого на их обслуживание: - класс 1 - реальный масштаб времени (телефонные вызовы), - класс 2 - фоновая обработка (web-запросы, текстовый чат), - класс 3 - отложенная обработка (электронная почта).
Основными элементами в модели МЦОВ являются вызовы и операторы. Вызовы поступают в систему обслуживания из бесконечного источника. Поступив в систему, они могут сразу же попасть на обслуживание или ожидать в очереди, если все операторы заняты. После завершения процедуры обслуживания оператор автоматически «выбирает» из очереди вызов с наивысшим приоритетом, который ожидал дольше всех. Если же очередь отсутствует, то оператор становится незанятым до поступления нового вызова.
Поскольку в дальнейшем рассматривается модель с прерываниями обслуживания - вызовы класса 1 могут прерывать обслуживание вызовов класса 2 и 3, а вызовы класса 2 могут прерывать облуживание вызовов класса 3, то для низкоприоритетных вызовов класса 2 и 3 целесообразно ввести динамический приоритет. В этом случае при достижении определенного времени ожидания s2 и s3 (как правило это время согласуется с заданным менеджерами МЦОВ уровнем обслуживания вызовов) для вызовов класса 2 и 3 соответственно они переводятся в конец очереди для высокоприоритетных вызовов. Таким образом, интенсивности их перехода в высокоприоритетную очередь будут равны P2=l/s2 и Р3 = 1 / з соответственно. Это позволит избежать длительного ожидания низкоприоритетных вызовов класса 2 и 3, что может привести к потере эффективности функционирования МЦОВ. Можно сказать, что вызовы в рассматриваемом МЦОВ обслуживаются в соответствии со смешанными динамическими абсолютно-относительными приоритетами.
Важным фактором при анализе работы МЦОВ является дисциплина очереди или принципы построения очереди, определяющие порядок, в соответствии с которым выбираются вызовы из очереди для обслуживания. Вызовы в МЦОВ внутри класса обслуживаются в соответствии с дисциплиной FCFS. Общая дисциплина обслуживания в МЦОВ является приоритетной с прерыванием обслуживания низкоприоритетных вызовов и продолжением их обслуживания в прерванном месте (preemptive resume priority, PRP). Данная дисциплина является наиболее распространенной в современных МЦОВ, поскольку она позволяет максимально загрузить операторов при сохранении качества обслуживания телефонных вызовов.
В модели предполагаются однородные операторы, которые обладают одинаковыми навыками обслуживания различных классов вызовов. Это объясняется современной политикой набора операторов МЦОВ, которые проходят соответствующее обучение и не должны сталкиваться с проблемами при обслуживании рассматриваемых классов вызовов, а также современным программным обеспечением, которое значительно облегчает обработку вызовов из сети Интернет.
Поступление вызовов в ЦОВ характеризуется интервалом между их последовательными поступлениями, а обслуживание - длительностью обслуживания вызова. В общем случае эти параметры могут быть и случайшлми, и детерминированными. В рассматриваемой модели процесс поступления вызовов предполагается Пуассоновским с нестационарными промежутками времени между поступлениями вызовов. Кроме того, для возможности анализа модели МЦОВ предполагается экспоненциальное распределение времени обслуживания различных классов вызовов, хотя, конечно, в реальности оно таковым не является. Тем не менее, во всех пакетах программного обеспечения, которое функционирует в ЦОВ, время обслуживания предполагается распределенное но экспоненциальному закону, и практика показывает, что данное распределение хорошо согласуется со статистическими данными [74, 150, 151, 152]. Некоторые исследования также показывают, что данное распределение является целесообразным для анализа характеристик ЦОВ, включая и те случаи, когда происходит обслуживание заявок электронной почты [153]. Стоит отметить, что время обслуживания также может хорошо аппроксимироваться лопюрмальным распределением [152, 154].
При анализе ЦОВ определенную роль играет длина очереди, которая может быть конечной или бесконечной. В рассматриваемой модели берется бесконечная очередь, поскольку предполагается, что количество линий в МЦОВ будет достаточным для предотвращения блокировки пользователей.
Для высокоприоритетных телефонных вызовов предусматривается возможность отказа от обслуживания из-за нетерпеливости. Время нетерпеливости для каждого телефонного вызова предполагается распределенным по экспоненциальному закону с временем терпеливости 1/9 [76, 77, 78, 85]. Параметр нетерпеливости 6 является, таким образом, интенсивностью отказов.
Расчет времени ожидания для низкоприоритетных вызовов
Определение времени ожидания низкоприоритетных вызовов двух классов является более сложной задачей, чем для высокоприоритетных вызовов. Поскольку обслуживание данных вызовов может быть прервано высокоприоритетным вызовами и они могут переходить в высокоприоритетную очередь, процесс ожидания данных вызовов является совокупностью трех процессов. Первый процесс является процессом ожидания низкоприоритетных вызовов в очереди. Второй процесс - процесс частичного обслуживания низкоприоритетных вызовов до момента его прерывания приходом высокоприоритетного вызова. И третий процесс -процесс ожидания в высокоприоритетной очереди при условии достижения граничного времени ожидания sk, к = 2,3, в низкоприоритетной очереди.
Аналогично определению времени ожидания высокоприоритетных вызовов, после некоторого фиксированного времени і, интенсивность поступления низкоприоритетных вызовов устанавливается равной нулю, т.е. Х2 = 0, А-з =0. Тот факт, что низкоприоритетные вызовы могут переходить в высокоприоритетную очередь значительно усложняет результаты предельных выражений (2.2), (3.4) и (3.5). Однако, если отделить покидающие очередь низкоприоритетные вызовы от общего их числа, тогда сходимости можно применить для определения общего времени ожидания, равному сумме времен ожидания вызовов в низкоприоритетной и высокоприоритетной очередях. То есть, отдельные распределения времени ожидания низкоприоритетных вызовов в высокоприоритетной и низкоприоритетной очередях будут Гауссовскими. Стоит также отметить, что общее распределение времени ожидания может быть отличным от Гауссовского, поскольку переходящие в высокоприоритетную очередь низкоприоритетные вызовы влияют на время ожидания всех вызовов в низкоприоритетной очереди - они увеличивают его.
При прерывании обслуживания низкоприоритетных вызовов класса 2 и 3 высокоприоритетными, обслуживание низкоприоритетных вызовов прерывается и их ожидание в низкоприоритетной очереди основывается на оставшемся времени обслуживания. Поскольку распределение времени обслуживания принимается экспоненциальным, оставшееся время обслуживания будет также распределено но экспоненциальному закону. То есть, дополнительным компонентом времени ожидания является оставшееся время обслуживания после каждого прерывания. Таким образом, полное время ожидания низкоприоритетных вызовов состоит из времени ожидания в низкоприоритетной очереди, времени оставшегося обслуживания после прерывания и времени ожидания в высокоприоритетной очереди. То есть, распределение времени ожидания низкоприоритетных вызовов будет экспоненциальным в случае прерывания обслуживания и совокупностью двух Гауссовских распределений в случае перехода в высокоприоритетную очередь.
Для низкоприоритетного вызова, поступившего в момент времени т может произойти несколько событий: 1. Вызов ожидает начала обслуживания в очереди. 2. Обслуживание вызова прерывается поступившим в МЦОВ высокоприоритетным вызовом. 3. Вызов получает обслуживание у оператора.
Необходимо получить уравнения, аналогичные (3.6) и (3.7) для низкоприоритетных вызовов класса 2 и 3. Поскольку необходимо решать различные системы уравнений для разных низкоприоритетных классов А вызовов, введем дополнительно в обозначении процессов Qj, 7 = 1,2,3, в нижнем индексе 2 или 3 для низкоприоритетных вызовов класса 2 и 3 соответственно. Рассмотрим случай S\0)(x) x (что эквивалентно Qfi{x) {n-Q {x))) и случай S3(0)(T) T (ЧТО эквивалентно Qx\x) {n-Q\l\x)-Qx(x))). Более того, предположим, что множество моментов времени { 1 =(//-2,7)} и {/бзз =("-Ж "б!")} имеет нулевую меру Лебега в [0,т]. Тогда получаем \imW2\x) = Wf(x)и lim (ВД- W2w(x))=W2w(x) = 0) , 1- л 4- Я4 ( 2 (і)) а также lim И?(т) = WfWи lim П W(x)- (1))= (1) = ;o), где ( (5j0) (x)) и (1 (б"]0 (т)) является Гауссовскими процессами с математическим ожиданием и дисперсией, определяемыми следующим образом. Решая второе и третье уравнения в системе уравнений (2.3), модифицированные в соответствии с выражением (3.1) для 022{-) и (2зз (") соответственно в интервале [т,оо] получаем две системы уравнений, при t х, для вызовов второго класса:
Процесс представления времени в имитационной модели
Процессы поступления, обслуживания, ухода вызовов и процесс назначения класса вызовов при их поступлении являются источниками случайности в МЦОВ. Поэтому требуется разработать подходящий и эффективный метод генерации случайных чисел, соответствующих вероятностным распределениям рассматриваемых процессов.
Все способы получения (генераторы) случайных чисел можно разделить на три основных класса: - Алгоритмические (программные) генераторы псевдослучайных чисел. В общем случае эти генераторы производят последовательную кольцевую выборку из заранее известной (вычисляемой) цепочки чисел; - Накопительные генераторы. Случайные числа генерируются на основе собираемой статистики о сложно предсказуемых событиях, например аппаратных прерываниях или интервалах между нажатиями клавиш клавиатуры; - Истинные (аппаратшле) генераторы, которые опираются на физические непредсказуемые (с точки зрения современной физики и квантовой механики) процессы, например распад радиоизотопа, «тепловой шум» и т.д.
Можно выделить следующие основные требования к генераторам случайных чисел [161]: - равномерность, - стохастичность (случайность), - независимость.
Одним из наиболее распространенных генераторов случайных чисел является линейный конгруэнтный генератор (linear congruential generator, LCG) [162]. Алгоритм генерации случайных чисел при использовании данного метода заключается в итеративном применении следующей формулы: Xk+l = (аХк + с) mod т, (4.1) где а 0, с 0, т 0 - некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа Х0 и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности X} определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим т. Для получения случайных чисел Un / = 1,2,... необходимо воспользоваться формулой Ul =Хк 1т.
При с = 0 в уравнении (4.1) генератор становится мультипликативным линейным конгруэнтным генератором. Такие генераторы наиболее популярны среди LCG, так как позволяют избежать дополнительных вычислительных операций. При этом основным параметром становится число /;/, а период будет равен т-\. В этом случае LCG становится мультипликативным линейным конгруэнтным генератором простого модуля (prime modulus multiplicative linear congruential generator, PMMLCG).
Для целей диссертационной работы бы использован накопительный генератор, который проявил себя лучше, чем PMMLCG [163]. Затраты на обслуживание накопительного генератора и сбор «исходной случайности» минимальны.
Накопительный генератор построен на 32 параллельных регистрах сдвига по неприводимому полиному Xм + XА + Хъ + X (период 2м -1) и нелинейной функции обратной связи, «сшивающей» генераторы воедино. Криптостойкость этого генератора немного выше чем «классических генераторов» основанных на регистрах сдвига и их комбинациях. Равномерность распределения достигается алгоритмическими (программными) преобразованиями накопленных данных
После выбора генератора случайных чисел необходимо выбрать алгоритм генерации случайных чисел. Среди таких алгоритмов можно выделить метод обратного преобразования, композиционный метод и метод разрешения и запрета. При моделировании для процессов поступления, обслуживания, ухода вызовов и процесса назначения класса вызовов в МЦОВ будет использоваться метод обратного преобразования. При этом для моделирования каждого из этих четырех процессов будет использоваться экспоненциальное распределение с различной интенсивностью.
Метод обратного преобразования может быть применен к непрерывным (в том числе экспоненциальному) и дискретным вероятностным распределениям. Пусть X будет являться непрерывной случайной величиной с функцией распределения F. Предположим, что F является непрерывной и строго возрастающей функцией при 0 F(_Y) 1. То есть, если .v, .v2 и 0 F(.Y,) F(X,) 1, тогда F(.Y,) F(.Y2). Также, пусть F" обозначает функцию, обратную F, где F \y) = {x:F(x) = y}. Тогда общий алгоритм обратного преобразования будет выглядеть следующим образом [164]: - генерация /-/(0,1). - возврат X = F_1 (U). X будет рассчитана из алгоритма, если показать, что для всех действительных чисел х, Р(Х х) = F(x). То есть, поскольку F - обратимая функция, имеем:
