Спектральное разложение для модели задержки на основе СМО с эрланговским и гиперэкспоненциальным распределениями

Обложка

Цитировать

Полный текст

Аннотация

Настоящая статья посвящена исследованию и получению решения в замкнутой форме для средней задержки требований в очереди для СМО, образованной двумя потоками с эрланговским и гиперэкспоненциальным законами распределений второго порядка для временных интервалов. Как известно, распределение Эрланга обеспечивает коэффициент вариации интервалов поступлений меньше единицы, а гиперэкспоненциальное распределение – больше единицы. Также известно, что главная характеристика СМО – средняя задержка связана с этими коэффициентами вариаций квадратичной зависимостью. Исследования систем G/G/1 в теории массового обслуживания актуальны в связи с тем, что они используются при моделировании систем передачи данных для анализа телетрафика. Для решения поставленной задачи использован метод спектрального разложения решения интегрального уравнения Линдли. Спектральное разложение для рассматриваемой системы позволило получить решение для средней задержки требований в очереди в замкнутой форме. Для практического применения полученных результатов использован метод моментов.

Полный текст

Введение

В данной работе использован метод спектрального разложения решения интегрального уравнения Линдли для систем массового обслуживания типа G/G/1 для нахождения среднего времени ожидания требований в очереди. Наиболее доступно для исследователей этот метод продемонстрирован в [1]. Важным моментом данного метода является конструирование спектрального разложения для рассматриваемой системы, а затем – нахождение нулей и полюсов этого разложения.

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

Настоящая статья посвящена анализу СМО E2/H2/1 по символике Кендалла с эрланговским и гиперэкспоненциальным входными распределениями второго порядка и является продолжением исследований [3–6]. В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика при моделировании систем передачи данных различного назначения, к тому же нельзя получить решения для таких систем в конечном виде для общего случая.

В работе также использованы приемы и способы аппроксимации законов распределений методом моментов теории вероятностей [7–12]. Схожие результаты современных исследований по системам массового обслуживания приведены в работах [13–15].

Постановка и решение задачи

В работе ставится задача вывода решения по средней задержке требований в очереди в системе E2/H2/1 с эрланговским и гиперэкспоненциальным входными распределениями второго порядка как основной характеристики любой СМО.

Для системы E2/H2/1 законы распределения интервалов входного потока и времени обслуживания задаются функциями плотности вида:

at=4λ2te2λt, (1)

bt=qμ1eμ1t+1qμ2eμ2t. (2)

Запишем преобразования Лапласа функций (1) и (2):

A*s=2λ2λ+s2,

B*s=qμ1s+μ1+1qμ2s+μ2.

Выражение для спектрального разложения решения интегрального уравнения Линдли для системы E2/H2/1 примет вид:

A*(s)B*(s)1= ψ+sψs=2λ2λs2× (3)

×qμ1μ1+s+1qμ2μ2+s1==s(s+s1)(s+s2)(ss3)(2λs)2(s+μ1)(s+μ2),

т. к. многочлен четвертой степени в числителе выражения (3) можно представить в виде разложения 

s(s3c2s2c1sc0) с коэффициентами 

c2=4λμ1μ2, c1=4λ(μ1+μ2λ)μ1μ2,

c0=4λ2q(μ1μ2)+4λμ1(μ2λ)].

В свою очередь кубический многочлен

s3c2s2c1sc0 (4)

с такими коэффициентами имеет два действительных отрицательных корня s1, s2 и один положительный корень s3 в случае стационарного режима, т. е. когда 0<ρ= τ¯μ/τ¯λ<1, где ρ, τ¯λ, τ¯μ соответственно коэффициент загрузки, средний интервал поступлений и среднее время обслуживания в системе.

Исходя из правил построения функций ψ+s и ψs, из выражения (3) за функцию ψ+s примем

ψ+s=ss+s1s+s2s+μ1(s+μ2),

т. к. нули многочлена (4) s=0, s1, s2 и полюсы s=μ1, s=μ2 лежат в области Re(s)0. За функцию ψs из выражения (3) примем

ψs=(2λs)2(ss3),

т. к. ее нуль s=2λ и полюс s=s3 лежат в области ResD.

На рис. отображены нули и полюса отношения ψ+s/ψs на комплексной s плоскости для исключения ошибок построения спектрального разложения. На рис. полюсы отмечены крестиками, а нули – кружками.

 

Рис. Нули и полюсы функции ψ+(s)/ψ(s) для системы E2/H2/1

Fig. Zeros and poles ψ+(s)/ψ(s) function for the E2/H2/1 system

 

Необходимая для получения решения константа равна 

К=lims0ψ+ss=s1s2μ1μ2.

Далее строим преобразование Лапласа функции распределения вероятностей времени ожидания

Φ+s=Kψ+s=s1s2s+μ1s+μ2ss+s1s+s2μ1μ2.

Откуда следует, что преобразование Лапласа функции плотности времени ожидания в системе E2/H2/1:

W*s=sΦ+s=s1s2s+μ1s+μ2s+s1s+s2μ1μ2. (5)

Производная от функции W*s со знаком минус в т. s=0 даст среднее время ожидания:

dW*sds|s=0=s1s2s+μ1s+μ2s+s1s+s2μ1μ2|s=0==1s1+1s21μ11μ2.

Окончательно среднее время ожидания в системе E2/H2/1 может быть определено из выражения

W¯=1s1+1s21μ11μ2, (6)

где s1, s2 абсолютные значения отрицательных корней s1, s2 кубического многочлена (4) с приведенными выше коэффициентами, а μ1, μ2 – параметры распределения (2). Таким образом, для среднего времени ожидания в СМО E2/H2/1 получено решение в замкнутой форме (6). Для того, чтобы им воспользоваться в практических расчетах, необходимо определить неизвестные параметры распределений (1) и (2) через их числовые характеристики.

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

τ¯λ=1λ, τλ2¯=32λ2 , cλ=12.

Для распределения (2) воспользуемся свойством преобразования Лапласа воспроизведения моментов и запишем два начальных момента для распределения (2):

τ¯μ=qμ1+1qμ2, τμ2¯=2qμ12+21qμ22. (7)

При аппроксимации с использованием первых двух моментов неизвестные параметры распределения (2) μ1, μ2, q определяются с помощью следующих выражений [3]:

μ1=2qτ¯μ, μ2=2(1q)τ¯μ, (8)

q=121±cμ21cμ2+1,

причем в качестве вероятности q можно использовать любое из двух значений. Отсюда квадрат коэффициента вариации времени обслуживания

cμ2=(1q2)μ122q(1q)μ1μ2+q(2q)μ22[(1q)μ1+qμ2]2. (9)

Из выражения для вероятности q следует, что коэффициент вариации cμ1. При аппроксимации закона распределения с использованием первых трех моментов для нахождения параметров распределения (2) необходимо в пакете Mathcad решить систему трех уравнений, полученных методом моментов. При этом необходимым и достаточным условием существования решения является выполнение условия: τμ3¯τμ¯1,5τμ2¯ [8].

Такой подход к использованию метода спектрального разложения позволяет определить не только среднюю задержку в очереди из (5), но и моменты высших порядков времени ожидания. Вторая производная от функции (5) при s=0 дает второй начальный момент времени ожидания. С учетом определения вариации задержки – джиттера в телекоммуникациях как разброс времени ожидания от его среднего значения, тем самым получим возможность определения джиттера через дисперсию времени ожидания.

Таким образом, гиперэкспоненциальный закон распределения второго порядка может определяться полностью двумя первыми моментами и перекрывать весь диапазон изменения коэффициента вариации [1,). Величины τ¯λ, τ¯μ, cλ=1/2, cμ будем считать входными параметрами для расчета pсреднего времени ожидания для системы E2/H2s3c2s2c1sc0/1 с использованием выражения (6). Тогда алгоритм расчета сведется к последовательному определению параметров распределения (2) из выражений (8) и к нахождению нужных корней многочлена с приведенными выше коэффициентами, а затем к использованию расчетной формулы (6).

Результаты вычислительных экспериментов

Ниже в таблице приведены данные расчетов для системы E2/H2/1 для различных случаев нагрузки (малой, средней и высокой) ρ=0,1; 0,5; 0,9 при cμ=1, 2, 4, 8. Коэффициент загрузки в данном случае определяется отношением средних интервалов ρ=τ¯μ/τ¯λ. Расчеты, приведенные в таблице проведены для удобства для случая нормированного времени обслуживания τ¯μ=1.

 

Таблица. Результаты экспериментов для СМО E2/H2/1

Table. Experimental results for QS E2/H2/1

Входные параметры ρ, cμ

Среднее время ожидания для системы E2/H2/1

ρ

cμ=1

cμ=2

cμ=4

cμ=8

0,1

0,030

0,160

0,795

3,448

0,5

0,618

2,094

8,082

32,079

0,9

6,588

20,072

74,065

290,063

 

Заключение

Таким образом, по результатам работы можно сделать следующие выводы:

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

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

×

Об авторах

Вениамин Николаевич Тарасов

Поволжский государственный университет телекоммуникаций и информатики

Автор, ответственный за переписку.
Email: tarasov-vn@psuti.ru

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

Россия, 443010, г. Самара, ул. Л. Толстого, 23

Список литературы

  1. Клейнрок Л. Теория массового обслуживания / пер. с англ. под ред. В.И. Неймана. М.: Машиностроение, 1979. 432 с.
  2. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. М.: РУДН, 1995. 529 c.
  3. Tarasov V.N. Extension of the class of queueing systems with delay // Automation and Remote Control. 2018. Vol. 79, no. 12. p. 2147–2158. DOI: https://doi.org/10.1134/S0005117918120056
  4. Тарасов В.Н. Анализ и сравнение двух систем массового обслуживания с гиперэрланговскими входными распределениями // Радиоэлектроника, информатика, управление. 2018. № 4. С. 61–70. DOI: https://doi.org/10.15588/1607-3274-2018-4-6
  5. Тарасов В.Н. Исследование и сравнение двойственных систем E2/M/1 и M/E2/1 // Инфокоммуникационные технологии. 2019. Т. 17, № 2. С. 157–162. DOI: https://doi.org/10.18469/ikt.2019.17.2.03
  6. Тарасов В.Н., Липилина Л.В., Бахарева Н.Ф. Автоматизация расчета характеристик систем массового обслуживания для широкого диапазона изменения их параметров // Информационные технологии. 2016. Т. 22, № 12. С. 952–957. URL: http://novtex.ru/IT/it2016/it1216_web-952-957.pdf
  7. Brännström N. A Queueing Theory Analysis of Wireless Radio Systems: master’s thesis applied to HS-DSCH. Lulea University of Technology, 2004. 79 p. URL: http://ltu.diva-portal.org/smash/get/diva2:1016709/FULLTEXT01
  8. Алиев Т.И. Основы моделирования дискретных систем. СПб.: СПбГУ ИТМО, 2009. 363 с.
  9. Алиев Т.И. Аппроксимация вероятностных распределений в моделях массового обслуживания // Научно-технический вестник информационных технологий, механики и оптики. 2013. № 2 (84). С. 88–93. URL: https://ntv.ifmo.ru/ru/article/4127/approksimaciya_veroyatnostnyh_raspredeleniy_v_modelyah_massovogo_obsluzhivaniya.htm
  10. Myskja A. An improved heuristic approximation for the GI/GI/1 queue with bursty arrivals // Teletraffic and Datatraffic in a Period of Change, ITC-13: proc. of congress. Copenhagen, Denmark. 19–26 June 1991. P. 683–688. URL: https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc13/myskja911.pdf?inline=true
  11. Whitt W. Approximating a point process by a renewal process, I: Two basic methods // Operation Research. 1982. Vol. 30, no. 1. P. 125–147. DOI: https://doi.org/10.1287/opre.30.1.125
  12. Тарасов В.Н., Бахарева Н.Ф. Компьютерное моделирование вычислительных систем. Теория, Алгоритмы, Программы. Оренбург: ОГУ, 2005. 183 с.
  13. Jennings O.B., Pender J. Comparisons of ticket and standard queues // Queueing Systems. 2016. Vol. 84, no. 1–2. P. 145–202. DOI: https://doi.org/10.1007/s11134-016-9493-y
  14. Gromoll H.C., Terwilliger B., Zwart B. Heavy traffic limit for a tandem queue with identical service times // Queueing Systems. 2018. Vol. 89, no. 3–4. P. 213–241. DOI: https://doi.org/10.1007/s11134-017-9560-z
  15. Legros B. M/G/1 queue with event-dependent arrival rates // Queueing Systems. 2018. Vol. 89, no. 3–4. P. 269–301. DOI: https://doi.org/10.1007/s11134-017-9557-7

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
2. Рис. Нули и полюсы функции для системы E2/H2/1

Скачать (22KB)

© Тарасов В.Н., 2022

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ФС 77 - 68199 от 27.12.2016.

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах