Research and comparison of pairs of dual systems with hyper-Erlang and exponential distributions

Full Text

Статья посвящена анализу систем массового обслуживания (СМО) HE2/M/1 и M/HE2/1 с гиперэрланговским (HE2) и экспоненциальным (M) входными распределениями. В открытом доступе автору не удалось обнаружить результаты для среднего времени ожидания требований в очереди в таких СМО. Как известно из теории массового обслуживания, среднее время ожидания является главной характеристикой для любых СМО. По этой характеристике, например, оценивают задержки пакетов в сетях пакетной коммутации при их моделировании с помощью СМО. Рассматриваемые СМО относятся к типу G/M/1 M/G/1 соответственно. Исследования таких систем актуальны в связи с тем, что они активно используются в современной теории телетрафика. Законы распределений Вейбулла или гамма наиболее общего вида, которые обеспечивают диапазон изменения коэффициентов вариаций от 0 до ∞ в зависимости от величины их параметров, не позволяют их использовать в теории массового обслуживания. Поэтому остается использовать другие частные законы распределений. Метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) в теории систем массового обслуживания G/G/1 заниG/G/1 зани/G/1 заниG/1 зани/1 зани мает важное место. Для записи ИУЛ, а также при рассмотрении метода спектрального разложения решения ИУЛ будем использовать стандартные обозначения [1]. Через () ∗ As и () ∗ Bs обозначим преобразования Лапласа функций плотности распределения интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения ( ) ( ) * * 1 - ⋅ - A s B s представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: ( ) ( ) * * 1 - ⋅ - = A s B s ( ) ( )/, +- ψψ ss где ( )+ø s и ( ) -ψ s некоторые дробно-рациональные функции от s, удовлетворяющие специальным условиям согласно [1], которые здесь опускаем. Постановка задачи В статье ставится задача вывода формул для среднего времени ожидания для рассматриваемых систем HE2/M/1 и M/HE2/1, а также подтверждения адекватности построенных математических моделей путем численного моделирования в пакете Mathcad. Вывод решения для среднего времени ожидания проводится методом спектрального разложения решения ИУЛ, как это показано в [2-6]. Решение для системы HE2/M/1 В системе HE2/M/1 интервалы времени между поступлениями требований заданы функцией плотности ( ) ( )12 22 22 12 4 4 1 , -λ -λ = λ + - λ tta t p te p te (1) преобразование Лапласа которой имеет вид: ( ) ( ) 22 * 12 12 22 1. 22     λλ = + -     +λ +λ     A s p p ss (2) Время обслуживания распределено с функцией плотности ( ) , -µ=µ t b t e (3) а ее преобразование Лапласа имеет вид ( ) * .  µ = +µ  Bs s (4) Тогда спектральное разложение решения ИУЛ для системы HE2/M/1 ( ) ( ) ( ) * * 1 / A s B s s + - ⋅ - =ψ ( )/ s-ψ примет вид ( ) ( ) ( ) 2 1 1 2 2 2 2 2 21 1. 2 s p ss p ss + - ψ  λ = +   ψ λ -      λµ +- -   λ - µ+   (5) Первый сомножитель (5) после соответствующих выкладок представим в виде ( ) ( ) ( ) 22 12 12 2 0 1 2 22 12 22 1 22 , 22      λλ +- =      λ- λ-       -+ = λ - λ - pp ss a a s a s ss где промежуточные параметры 22 0 1 2 16 , = λ λa ( ) 1 1 2 1 2 16 [ 1], = λ λ λ + - λ a p p ( )22 2 1 2 4[ 1]. = λ + - λ a p p Продолжая разложение (5), получим ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 22 0 1 2 22 12 22 12 22 12 1234 22 12 4 ( ) 2 2 ( ) 2 2 ( ) 2 2 ( ) ( )( )( )( ). 2 2 ( ) + - ψ µ - + = - ψ λ - λ - µ+ λ - λ - µ+ -= λ - λ - µ+ - + + - - = λ - λ - µ+ s a a s a s s s s s s s s s s s s s s s s s s s s s s s Окончательно спектральное разложение решения ИУЛ для системы HE2/M/1 имеет вид ( ) ( ) ( ) ( ) 1234 22 12 ( )( )( )( ). 2 2 ( ) + - ψ - + + - - = ψ λ - λ - µ+ s s s s s s s s s s s s s s (6) Исследование многочлена в числителе разложения (6) и определение его корней является основным моментом метода спектрального разложения решения ИУЛ. Многочлен четвертой степени в числителе разложения 432 3 2 1 0 + + + + s c s c s cs c (7) с коэффициентами 0 1 1 2 1 2 1 2 16 [ ( )], = µ+ λ λ λ λ -µ λ +λ ca 22 1 1 1 2 2 1 2 1 2 2 4 ( 4 ) 16 ( ) , = µ λ + λ λ +λ - λ λ λ +λ - µ ca 22 2 1 2 1 2 1 2 4( ) 16 4 ( ), = λ +λ + λ λ - µ λ +λc 3 1 2 4( ) =µ- λ +λc в случае стабильной системы имеет один действительный отрицательный корень и три положительных корня (либо вместо последних один действительный положительный и два комплексно-сопряженных с положительной вещественной частью). Эти коэффициенты сформированы с помощью символьных операций Mathcad и выMathcad и вы и выражаются через параметры распределений (1) и (3), которые предстоит еще определить. Далее строим рациональные функции ( ) +ψ s и ( ) -ψ : s () + ψ= s 1 ( )/( ), + µ+ s s s s так как нули многочлена (6): 0, =s 1 = - ss и полюс = -µ s лежат в области ) 0 ( , ≤Re s а функция ( ) ( )22 12 234 22 () , ( )( )( )- λ - λ - ψ = - --- ss s ssssss так как ее нули и полюсы лежат в области ( ) , >Re s D как того требует метод спектрального разложения. Далее по методике спектрального разложения найдем константу K: ( ) ( ) ( ) 1 1 00 lim lim , + →→ ψ+ = = = +µ µ ss s s s sK ss где 1 s - абсолютное значение отрицательного корня 1. -s Постоянная K определяет вероятность того, что поступающее в систему требование застает ее свободной. Для нахождения преобразования Лапласа функции плотности времени ожидания построим функцию ( ) ( ) 1 1 () . ()+ + +µ Φ = = ψ µ + K s ss s s s s Отсюда преобразование Лапласа функции плотности времени ожидания ( ) *() + = ⋅Φ W s s s будет равно ( ) ( ) ( ) * 1 1 . +µ = µ+ ss Ws ss (8) Для нахождения среднего времени ожидания найдем производную от функции ( ) *W s со знаком минус в точке s = 0: * 0 1 11 |. = - = - ìs dW s ds s Окончательно среднее время ожидания для системы HE2/M/1 1 1 1/ / -= ì.W s (9) Выражение (8) для преобразования Лапласа функции плотности времени ожидания позволяет определить также моменты высших порядков времени ожидания, а именно вторая производная от преобразования (8) в точке 0 =s дает второй начальный момент времени ожидания, что позволяет определить дисперсию времени ожидания. В стандарте [9] джиттер (дрожание задержки) в телекоммуникациях определен как колебание времени ожидания вокруг его среднего значения. Тогда джиттер можно определить через дисперсию времени ожидания. При анализе трафика, чувствительного к задержкам, это будет важным подспорьем. Для использования формулы (9) при расчетах необходимо знать числовые характеристики распределения (1). Для распределения (3) они легко определяются. Через числовые характеристики будем определять неизвестные параметры распределений (1) и (3) методом моментов. Для этого воспользуемся основным свойством преобразований Лапласа (2) и (4) воспроизведения моментов и запишем первые два начальных момента для распределения (1): ( ) ( ) 2 22 12 12 11 3 ,. 2 λλ --  τ = + τ = + λ λ λ λ  pp pp (10) Рассматривая равенства (10) как форму записи метода моментов, найдем неизвестные параметры распределения (1) 1, λ 2, λ p. Так как система двух уравнений (10) является недоопределенной, к ней добавим в качестве недостающего уравнения выражение для квадрата коэффициента вариации: 22 2 2 () . () λλ λ λ τ-τ = τ c (11) Выбираем значения параметров 1, λ 2 λ так, чтобы они были решениями первого уравнения (10) 1 2/, λ λ = τ p 2 2(1 )/ λ λ = - τ p (12) и потребуем выполнения условия (11) [2; 3]. Подставив выражения (12) в (11), получим уравнение четвертой степени относительно неизвестного параметра p: 22 (1 )[8(1 ) λ -+- p p c p 2 8(1 ) 3] 0. cp λ - + + = Отбросив тривиальные решения 0 =p и 1, =p получим квадратное уравнение следующего вида: 22 8(1 ) λ +- cp 28(1 ) 3 0, λ + + = cp решив которое выберем для однозначности больший корень для параметра p: 2 2 1 2(1 ) 3. 2 8(1 ) λ λ +- = + + cp c (13) Отсюда следует, что коэффициент вариации 1/ 2.λ ≥c Теперь, подставив (13) в (12), определяем все три неизвестных параметра 1, λ 2, λ p распределения (1) [2]. Для распределения (3) числовые характеристики равны 1/ , µ τ = µ 1 µ =c [4]. Аналогичную аппроксимацию законов распределений с использованием начальных моментов можно увидеть в [7; 8]. Решение для системы M/HE2/1 Для двойственной системы законы распределения входного потока и времени обслуживания задаются функциями плотности ( ) , -λ=λ t a t e (14) ( ) ( )12 22 22 12 4 4 1 . -µ -µ = µ + - µ ttb t q te q te (15) Запишем преобразования Лапласа функций (14), (15): ( )*, λ = +λ As s ( ) ( ) 22 12 12 22 * 1 . 22     µµ = + -     +µ +µ     B s q q ss В этом случае выражение для спектрального разложения решения ИУЛ примет следующий вид: ( ) ( ) ( ) 2 12 12 22 1 1. 22 + - ψ λ = × ψ λ-       µµ × + - -      +µ +µ       s ss qq ss (16) Поступив аналогично с системой HE2/M/1 и опустив некоторые выкладки, выпишем многочлен четвертой степени в числителе разложения (16): 432 3 2 1 0 + + + + s d s d s d s d (17) с коэффициентами 0 1 1 2 1 2 1 2 16 [ ( )], = λ+ µµ µµ -λ µ +µ db 22 1 1 2 1 2 1 1 2 2 2 16 ( ) 4 ( 4 ) , = µµ µ +µ - λ µ + µµ +µ + λ db 22 2 1 2 1 2 1 2 4( ) 16 4 ( ), = µ +µ + µµ - λ µ +µd 3 1 2 4( ) . = µ +µ -λd Многочлен (17) с положительными коэффициентами имеет четыре действительных отрицательных корня либо два действительных отрицательных корня и два комплексно-сопряженных корня с отрицательными вещественными частями. Тогда окончательно спектральное разложение решения ИУЛ для системы M/HE2/1 имеет вид ( ) ( ) ( ) ( ) 1234 22 12 ( )( )( )( ), 2 2 ( ) + - ψ +σ +σ +σ +σ = ψ µ + µ + λ- s s s s s s s s s s (18) где через 1, -σ 2, -σ 3, -σ 4 -σ обозначены для удобства отрицательные корни многочлена (17). Далее по правилам спектрального разложения строим функции ( ) +ψ s и ( ) -ψ : s ( ) ( ) ( ) ( ) 1234 22 12 ( )( )( ) , 22+ +σ +σ +σ +σ ψ= µ + µ + s s s s s s ss ( ) . - ψ =λ- ss Константа спектрального разложения ( ) ( ) ( ) ( ) 0 1234 220 12 1234 22 12 lim ( )( )( ) lim 22 . 16 + → → ψ = = +σ +σ +σ +σ = = µ + µ + σσσσ = µµ s s s K s ssss ss Отсюда преобразование Лапласа функции плотности времени ожидания будет равно ( ) ( ) ( ) ( ) * 22 1 2 3 4 1 2 22 1 2 1 2 3 4 22 , 16 ( )( )( ) = σ σ σ σ µ + µ + = µ µ +σ +σ +σ +σ Ws ss ssss (19) а среднее время ожидания ( ) * = - dW s W ds при 0 = :s 123412 111111 . =+++-- σσσσµµ W (20) Определение неизвестных параметров распределений (14) и (15) будет аналогично для системы HE2/M/1. Параметр q аналогично p будет 2 2 2(1 ) 31 , 2 8(1 ) µ µ +- = ± + c q c подставив его в выражения 1 2 / , µ µ = τ q 2µ= 2(1 )/ , q µ =-τ найдем все неизвестные параметры распределения (15). Результаты численного моделирования Ниже в таблице приведены данные расчетов среднего времени ожидания для систем HE2/M/1 и M/HE2/1 для случаев малой, средней и высокой нагрузки 0,1; ρ= 0,5; 0,9. Заметим, что первая система определена для коэффициентов вариаций интервалов поступления и обслуживания 1/ 2 λ ≥c и 1, µ =c а вторая - для 1 λ =c и 1/ 2.µ ≥c Коэффициент загрузки ρ определяется отношением средних интервалов /. µλ ρ= τ τ Результаты, приведенные в таблице, получены для нормированного времени обслуживания 1. µ τ= Данные таблицы свидетельствуют о незначительном различии сравниваемых систем в случае высоких нагрузок и более значительных расхождениях - при средних и малых нагрузках. Двойственные системы этим и отличаются друг от друга. Результаты расчетов для системы хорошо согласуются с данными [10] в той области изменения параметров, при которых применимы данные системы. Заключение В работе получены спектральные разложения решения ИУЛ для систем HE2/M/1 и M/HE2/1, а через них выведены расчетные формулы для среднего времени ожидания требований в очереди для этих систем. Эти формулы дополняют известную незавершенную формулу теории массового обслуживания для среднего времени ожидания систем типа G/G/1. Известно, что среднее время ожидания требований в очереди является главной характеристикой СМО, так как все остальные характеристики: средняя задержка, средняя длина очереди, среднее количество требований в системе и другие определяются через среднее время ожидания. Адекватность полученных результатов обеспечена корректным использованием классического метода спектрального разложения, а проведенные вычислительные эксперименты только подтверждают данный факт. Таблица. Результаты экспериментов для СМО НE2/M/1 и М/HE2/1 Входные параметры Среднее время ожидания ρ cλ cµ для системы НE2/M/1 для системы M/НE2/1 0,1 0,71 0,71 0,03 0,09 2 2 0,08 0,28 4 4 0,10 0,94 8 8 0,11 3,61 0,5 0,71 0,71 0,62 0,75 2 2 2,00 2,50 4 4 4,62 8,50 8 8 10,15 32,50 0,9 0,71 0,71 6,61 6,77 2 2 22,59 22,50 4 4 77,28 76,50 8 8 295,96 292,50

About the authors

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru
Samara, Russian Federation

References

Supplementary files