QUEUEING SYSTEM HE2/HE2/1

Full Text

Введение. Постановка задачи Статья посвящена исследованию системы массового обслуживания (СМО) HE2/HE2/1 типа G/G/1 с гиперэрланговскими входными распределениями второго порядка. В теории массового обслуживания исследования систем G/G/1 особо актуальны в связи с тем, что до сих пор не существует решения в конечном виде для общего случая. Начнем с определения гиперэрланговского закона распределения. Распределение с плотностью , где , называют гиперэрланговским порядка R и обозначают HER [1-2]. Гиперэрланговское распределение представляет собой вероятностную смесь нормированных распределений Эрланга порядка k с функцией плотности вида и является наиболее общим распределением неотрицательных непрерывных случайных величин, поскольку имеет коэффициент вариации в интервале от 0 до ∞ [3]. Ограничимся гиперэрланговскими входными распределениями 2-го порядка с функцией плотности . Ниже будет показано, что коэффициент вариации для такого распределения . Это распределение в литературе обозначают как НE2. Оно содержит три параметра (0 < p < 1, ) и таким образом, позволяет аппроксимировать произвольные входные распределения на уровне трех первых моментов с использованием известного метода моментов. Ниже будет показано, что распределение НE2, как и гиперэкспоненциальное H2 может определяться как двумя, так и тремя первыми моментами. В статье ставится задача нахождения решения для времени ожидания требований в очереди в СМО HE2/HE2/1 и построения механизма аппроксимации произвольных законов распределений гиперэрланговским. Вывод решения для системы HE2/HE2/1 В СМО HE2/HE2/1 интервалы между соседними требованиями входного потока распределены по закону: , (1) а время обслуживания - . (2) Преобразование Лапласа (1) имеет вид: , (3) а функции (2) - . (4) Перейдем к определению спектрального разложения решения интегрального уравнения Линдли (ИУЛ) в виде отношения двух рациональных функций в случае распределений (1)-(2) с учетом преобразований Лапласа (3)-(4), где сами функции и в отдельности могут быть определены только после получения полного разложения. Получим следующее выражение для отношения: Первый сомножитель в правой части в квадратных скобках представим в виде: где ; ; . Аналогично представим второй сомножитель: где , , . Тогда искомое выражение для спектрального разложения будет иметь вид: Многочлен в числителе в правой части такого разложения (5) как правило всегда имеет один нуль [1]. В данном случае свободный член разложения также равен нулю: . В числителе дроби в правой части разложения (5) получили многочлен 8-й степени , коэффициенты которого равны: (6) . Данные коэффициенты получены с помощью выполнения трудоемких символьных операций математического пакета Mathcad над числителем разложения (5), так как числитель разложения включает 90 слагаемых и вручную привести подобные члены после раскрытия скобок проблематично. Видимо поэтому в литературе, включая web-ресурсы, нет упоминаний о такой системе. Выделим многочлен в числителе (5): , (7) так как определение его корней и работа с ними является важным моментом метода спектрального разложения решения ИУЛ. Исследование многочлена (7) с коэффициентами (6) с использованием формул Виета подтверждает наличие четырех отрицательных действительных корней либо двух отрицательных действительных корней и двух комплексно-сопряженных корней с отрицательными вещественными частями, а также трех положительных действительных корней либо одного положительного и двух комплексно сопряженных корней с положительными вещественными частями. Исследование знака младшего коэффициента многочлена (7) показывает, что . С учетом знака минус в многочлене перед коэффициентом , формулы Виета не противоречат факту наличия четырех отрицательных корней у многочлена (7). В общем случае, наличие таких корней следует из существования и единственности спектрального разложения [1] или же факторизации [4]. Обозначив корни многочлена (7) с отрицательными вещественными частями для удобства через , а с положительными вещественными частями через , отношение окончательно можно разложить на следующие множители: (8) Тогда с учетом условий, налагаемых на функции и , за функцию примем , так как нули многочлена (7): , , и полюсы , лежат в области . За функцию примем . Таким образом, построенные функции и удовлетворяют всем условиям метода спектрального разложения. Далее по методике спектрального разложения определим постоянную которая физически определяет вероятность того, что поступающее в систему требование застает ее свободной. Функция позволяет найти преобразование Лапласа функции распределения вероятностей времени ожидания : Тогда преобразованием Лапласа для функции плотности времени ожидания будет функция , то есть . (9) Среднее время ожидания в очереди равно значению производной от преобразования Лапласа (11) функции плотности со знаком минус в точке : . Окончательно, среднее время ожидания в очереди для СМО НE2/НE2/1: . (10) Из выражения (9) также можно определить дисперсию времени ожидания. Вторая производная от преобразования (9) в точке дает второй начальный момент времени ожидания, что позволяет определить дисперсию времени ожидания. Учитывая определение джиттера в телекоммуникациях как разброс времени ожидания [8], тем самым получим возможность его определения через дисперсию. Этот результат является важным для анализа трафика, чувствительного к задержкам. Аппроксимация законов распределения на уровне двух первых моментов Воспользуемся свойством преобразования Лапласа воспроизведения моментов и запишем начальные моменты до второго порядка для распределения (1): (11) . (12) Рассматривая равенства (11)-(12) как запись метода моментов, найдем неизвестные параметры распределения (1) . Система уравнений (11)-(12) при этом является не доопределенной, поэтому к ней добавим выражение для квадрата коэффициента вариации , (13) как связующее условие между (11) и (12). Кроме того, коэффициент вариации будем использовать в расчетах в качестве входного параметра системы. Исходя из вида уравнения (11) положим , (14) и потребуем выполнения условия (13). Подставив выражения (11)-(12) и частное решение (14) в (13) и решив квадратное уравнение относительно параметра p, выберем одно нужное значение: . Отсюда следует, что коэффициент вариации Таким образом, получено частное решение недоопределенной системы уравнений (11) и (12) методом подбора. Аналогично поступив с законом распределения (2), определяем его неизвестные параметры . Такой же подход к аппроксимации законов распределения гиперэкспоненциальным распределением применен в работах [5-7]. Таким образом, гиперэрланговский закон распределения может определяться полностью двумя первыми моментами и перекрывать весь диапазон изменения коэффициента вариации от до , что шире, чем у гиперэкспоненциального распределения . Учитывая тот факт, что распределение НE2 является трехпараметрическим, аппроксимацию можно выполнить и на уровне трех первых моментов. Для этого запишем выражения для начального момента третьего порядка, полученное через преобразование Лапласа (3): (15) Теперь присоединив уравнение (15) к уравнениям моментов (11) и (12) и решив систему 3-х нелинейных уравнений с тремя неизвестными в пакете Mathcad находим все три параметра распределения (1). Аналогично определяем три параметра распределения (2). Как показано в работе [5] на примере гиперэкспоненциальных входных распределений, аппроксимация с использованием двух первых моментов в отличие от трех моментов, может занижать величину среднего времени ожидания до 10% в зависимости от загрузки и величины третьего момента. Практическое применение полученных результатов Ниже в таблицах 1-2 приведены результаты расчетов в пакете Mathcad среднего времени ожидания для системы НE2/НE2/1 по полученной расчетной формуле (12) для случаев малой, средней и высокой нагрузки . Коэффициент загрузки в расчетах определяется отношением средних интервалов времени обслуживания и интервалов между требованиями . Расчеты проведены для нормированного времени обслуживания . В таблице 1 приведены результаты для коэффициентов вариаций меньших единицы, а в таблице 2 - больших единицы. При этом для сравнения использованы результаты для СМО E2/E2/1 и H2/H2/1 соответственно. Как видно из таблиц 1-2, результаты в обеих случаях достаточно близки. Кроме того, полученные результаты хорошо согласуются с данными [11]. Таблица 1. Результаты для времени ожидания при коэффициентах вариаций , меньших единицы Входные параметры Среднее время ожидания ρ для системы HE2/HE2/1 для системы E2/E2/1 0,1 (0,71; 0,71) 0,02 0,02 0,5 (0,71; 0,71) 0,40 0,39 0,9 (0,71; 0,71) 4,40 4,36 Таблица 2. Результаты для времени ожидания при коэффициентах вариаций , больших единицы Входные параметры Среднее время ожидания ρ для системы HE2/HE2/1 для системы H2/H2/1 0,1 (2,2) 0,34 0,45 (4,4) 1,68 1,78 (8,8) 7,16 7,11 0,5 (2,2) 3,98 4,04 (4,4) 16,53 16,13 (8,8) 66,73 64,18 0,9 (2,2) 36,21 36,20 (4,4) 145,31 144,83 (8,8) 580,56 577,86 Заключение В работе получено аналитическое решение для среднего времени ожидания для системы HE2/HE2/1 с использованием символьных операций пакета Mathcad. Этот результат дополняет и расширяет известную формулу для среднего времени ожидания для систем типа G/G/1. Используя предложенный подход, помимо среднего времени ожидания, можно определить дисперсию и моменты высших порядков времени ожидания. Полученный результат, с одной стороны, дополняет систему Н2/Н2/1, а с другой стороны, расширяет диапазон изменения коэффициентов вариаций интервалов поступлений и времени обслуживания от до . Для убедительности, данные расчетов для системы HE2/HE2/1 сравниваются с результатами для систем E2/E2/1 и Н2/Н2/1, что демонстрирует их достаточную близость. Полученный результат с успехом может быть применен в современной теории телетрафика, где задержки пакетов входящего трафика играют первостепенную роль. Для этого необходимо знать числовые характеристики интервалов входящего трафика и времени обслуживания на уровне двух первых моментов, что не вызывает трудностей при использовании современных анализаторов трафика [7].

About the authors

Veniamin Nikolaevich Tarasov

Povolzhsky State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru

Nadezhda Fedorovna Bakhareva

Povolzhsky State University of Telecommunications and Informatics

Email: bakhareva-nf@psuti.ru

Othmane Kada

Povolzhsky State University of Telecommunications and Informatics

Email: otman2333@gmail.com

References

Supplementary files