Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Печеный Е.А. 1 Муршед Ф.А. 1 Нуриев Н.К. 1

---

1 ФГБОУ ВО «Казанский национальный исследовательский технологический университет»

В статье рассматривается проблема моделирования поллинговых систем массового обслуживания, работающих в особых условиях, когда в силу причин естественного или организационного порядка время пребывания заявок в стадии обслуживания (время жизни) ограничено. Показано, что использование классических математических моделей в этом случае малоэффективно, так как не позволяет получить удобные расчетные соотношения для оценки параметров системы. Показаны изменения, происходящие с функцией распределения потока обслуживания при введении ограничений на время жизни заявок, предложен аналитический вид этой функции и описаны ее свойства. С помощью специализированного программного продукта AnyLogic выполнено имитационное моделирование поллинговой системы, функционирующей в режиме циклического обхода обслуживающего устройства четырех независимых очередей, пополняемых пуассоновскими потоками заявок. В ходе имитационных экспериментов установлено отсутствие значимых различий между исчерпывающим и шлюзовым вариантами обслуживания при введении ограничений на время жизни заявок, а также выявлены дополнительные возможности администрирования, возникающие при этом. Произведена оценка изменений эксплуатационных свойств системы, происходящих при ограничении времени жизни заявок; обоснована возможность подключения к обслуживанию дополнительной очереди и получены условия, когда это становится технически осуществимым.

Статья в формате PDF

0 KB

поллинговые системы

эффективное администрирование

ограниченное время жизни заявок

исчерпывающее

шлюзовое

1. Leibowitz M.A. An approximate method for treating a class of multiqueue problems / M.A. Leibowitz // IBM Journal of Research and Development. – 1961. – Vol. 5, № 3. – P. 204–209.

2. Муршед Ф.А. Оптимизация системы поллинга с применением динамической схемы маршрутизации сервера / Ф.А. Муршед, Н.К. Нуриев // Вестник Казанского технологического университета. – 2017. – Т. 20, № 22. – С. 88–91.

3. Муршед Ф.А. Имитационная модель системы поллинга с циклическим опросом и исчерпывающей дисциплиной обслуживания очередей / Ф.А. Муршед, Н.К. Нуриев // Вестник Казанского технологического университета. – 2017. – Т. 20, № 13. – С. 107–109.

4. Boon M.A. Applications of polling systems / M.A. Boon, R.D. Van der Mei, E.M. Winands // Surveys in Operations Research and Management Science. – 2011. – Vol. 16, № 2. – P. 67–82.

5. Dorsman J.-P.L. Markovian polling systems with an application to wireless random-access networks / J.-P.L. Dorsman, S.C. Borst, O.J. Boxma, M. Vlasiou // Performance Evaluation. – 2015. – Vol. 85. – P. 33–51.

6. Муршед Ф.А. Исследование поллинговых систем на основе имитационных моделей с использованием программного комплекса anylogic / Ф.А. Муршед, Е.А. Печеный, Н.К. Нуриев // Вестник Казанского технологического университета. – 2018. – Т. 21, № 2. – С. 109–115.

7. Рыжиков Ю.И. Расчет сети обслуживания с ограничением времени жизни заявок / Ю.И. Рыжиков, А.В. Уланов // XII всероссийское совещание по проблемам управления ВСПУ-2014. – 2014. – С. 8620–8624.

8. Вишневский В.М. Системы поллинга: теория и применение в широкополосных беспроводных сетях / В.М. Вишневский, О.В. Семенова. – М.: Техносфера, 2007. – 312 с.

9. Митропольский А.К. Техника статистических вычислений / А.К. Митропольский. – М.: Наука, 1971. – 576 с.

Поллинговые системы, то есть системы массового обслуживания, где единственное обслуживающее устройство обрабатывает заявки, накапливающиеся в нескольких независимо формирующихся очередях, известны давно. Одна из первых публикаций, посвященная этой проблематике, работа Лейбовица [1], датирована еще 1961 г. В последние два десятилетия интерес к таким системам значительно вырос. Это обусловлено прежде всего бурным развитием телекоммуникационных технологий и компьютерных сетей, работа которых построена таким образом, что одно обслуживающее устройство (сервер) принимает в установленном порядке пакеты информации от нескольких несвязанных между собой источников. Растущий интерес научного сообщества к поллинговым системам подтверждается значительным числом опубликованных результатов исследований в этой области [2–5], касающихся различных аспектов построения и функционирования таких систем. Важность и оригинальность этих работ характеризует, в частности, тот факт, что наряду с известным аппаратом метода производящих функций, специально для анализа поллинговых структур, были разработаны и применены такие новые приёмы, как метод ветвящихся процессов и метод анализа средних. В целом математический аппарат, используемый для описания поллинговых систем, весьма совершенен, а конечной результат представляет собой итог изящных, но не всегда очевидных рассуждений и умозаключений.

Общей особенностью практически всех сложных и содержательных моделей систем массового обслуживания и поллинговых систем в частности является то, что при их построении используются параметры, которые априори, как правило, не известны, а их экспериментальное определение трудноосуществимо. Это существенно снижает востребованность таких моделей применительно к решению прикладных задач. Важно также отметить, что приоритетом практически всех моделей систем массового обслуживания выступают интересы пользователей, а конечным результатом моделирования оказываются такие показатели, как длина очереди, время ожидания и т.п., для достижения желаемого значения которых подбираются различные варианты обслуживания, опроса, дисциплины очереди. При этом по умолчанию предполагается, что для администратора все эти варианты равноприемлемы, хотя, конечно, на самом деле это не так. И поскольку, как было показано в работе [6], технико-экономические характеристики поллинговых систем, функционирующих в шлюзовом и исчерпывающем режимах обслуживания, практически неразличимы, возможности влияния на ситуацию со стороны администратора оказываются ничтожными. Следует упомянуть и о том, что использование большинства математических моделей в составе расчетных схем возможно только для потоков с простейшими однопараметрическими функциями распределения. В любом другом случае получение решения даже с помощью численных алгоритмов является весьма сложной задачей.

Постановка задачи исследования

В последнее время значительное внимание исследователей привлекают системы с ограниченным временем жизни заявок, где в силу природных, технических или организационных причин назначается предельное время пребывания заявок на обслуживании, по истечении которого заявка покидает систему независимо от того, было ли завершено ее обслуживание или нет. Математическое моделирование и расчет подобных систем сложны и трудоемки [7], поскольку привычный вид функций распределения заявок в потоке существенно меняется. Однако если лимит времени устанавливается директивно, то есть имеет организационный порядок, – то это открывает дополнительные, весьма широкие возможности администрирования. Предметом данной статьи является математическое и имитационное моделирование поллинговых систем с ограниченным временем жизни заявок и разработка приёмов эффективного администрирования таких систем.

Математическая модель

Рассмотрим математическую модель поллинговой системы, функционирующей в исчерпывающем режиме обслуживания, построенную методом анализа средних, как рекомендовано в монографии [8]. Пусть система имеет в своем составе N независимых очередей. Обозначим комбинацией символов (i, j) период времени, охватывающий посещение обслуживающим устройством с i-й очереди по j-ю в порядке циклического обхода. Тогда безусловная длина i-й очереди Li выразится как

(1)

где qj1 – вероятность того, что в произвольный момент времени обслуживающее устройство находится в j-й очереди; Li,j – длина i-й очереди в момент нахождения обслуживающего устройства в j-й очереди. Символом qi,j будем обозначать долю времени, когда система пребывает в периоде (i, j), предполагая, что в стационарном режиме эта величина не изменяется от цикла к циклу.

Величины Li,j определяются путем решения системы линейных уравнений

(2)

где λi – интенсивность потока пополнения i-й очереди; – среднее оставшееся время (i, j) периода; – среднее оставшееся время обслуживания заявок в i-й очереди; ρi – коэффициент загрузки i-й очереди; Si – случайная величина, характеризующая время пребывания обслуживающего устройства в i-й очереди; – остаточное время переключения на i-ю очередь; C – общее время цикла; Bi – случайная величина, характеризующая время обслуживания заявки в i-й очереди. Величины вычисляются по соотношению

(3)

для чего предварительно находится

(4)

Здесь vi,j – средняя длительность периода (i, j); bi – первый момент функции распределения потока, пополняющего i-ю очередь.

Для систем, функционирующих в режиме шлюзового обслуживания, базовое расчетное соотношение для отыскания величин Li,j остается справедливым, однако формулы (3) и (4) претерпевают изменения

(5)

(6)

где – заявки, обслуживаемые в текущем цикле; – заявки, поступившие в очередь в ходе обслуживания. Естественно, что

(7)

а безусловная длина i-ой очереди при шлюзовом варианте обслуживания

(8)

Решение системы уравнений (2) задача хотя и трудоёмкая, но не сложная. Главную сложность представляет идентификация выражений (3)–(6). Отыскание и оценка таких параметров, как qi,j, , , , является не простой, отдельной проблемой и оказывается основным препятствием на пути практического использования представленных моделей. Именно это побудило авторов, стремившихся к получению не только достоверных, но и реализуемых результатов, применить в своем исследовании аппарат имитационного моделирования.

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

Рассмотрим ситуацию, когда поток обслуживания распределен экспоненциально и имеет одинаковую интенсивность μ для заявок любой очереди. При этом устанавливается предельное время пребывания заявок в стадии обслуживания ?, по достижении которого их обслуживание прекращается, а заявки либо удаляются из системы, либо снова помещаются в ту же очередь. Это самым существенным образом меняет вид функции распределения. Она приобретает конечный размах [0, ?] и, если представить возникшие изменения на гистограмме, то это выразится в присоединении всех разрядных частот, больших ?, к разряду, для которого величина ? является правой границей (см. рис. 1).

Наиболее близкий аналог этого распределения, аналитическое выражение которого известно, можно отыскать среди так называемых кривых Пирсона [9]. Это обширное семейство функций, порождаемое решениями дифференциального уравнения

(9)

общий интеграл которого может быть записан в виде

(10)

где

(11)

Постоянные, входящие в состав подынтегрального выражения (11), определяются через моменты распределения

(12)

где r3 и r4 – третий и четвертый основные моменты распределения.

Нас будет интересовать случай, когда корни знаменателя подынтегрального выражения действительны и различны по знаку. Это выполняется при условии

и C0C2 < 0, (13)

а функция плотности вероятности искомого распределения имеет вид

(14)

где M – нормировочный множитель.

Значения параметров τ1, τ2, ?1, ?2 также определяются с помощью моментов распределения

(15)

где ? – размах распределения. И если τ1 и τ2 ∈ (–1, 0), то функция плотности вероятности имеет вид, представленный на рис. 2.

Предполагается, что случайная величина x центрирована так, что в точке x = 0 функция f(x) достигает своего минимального значения.

Имитационная модель и обсуждение ее результатов

Функция распределения плотности вероятности (14) дает описание сложного многопараметрического распределения, идентификация параметров которого требует вычисления четырех основных моментов. Поэтому применение его в вычислительных схемах, в частности, для определения параметров системы уравнений (3)–(6), представляется малоперспективным. С помощью имитационного моделирования эти затруднения преодолеваются, поскольку оно позволяет осуществить численный анализ сколь угодно сложного процесса, минуя стадию аналитического сопровождения.

Используя средства имитационного моделирования, мы проследили, как изменятся технико-экономические и эксплуатационные характеристики поллинговой системы с четырьмя независимыми очередями после введения ограничений на время жизни заявок в пуассоновском потоке обслуживания. Прежде всего, рассмотрим как с введением ограничений на время пребывания заявок в стадии обслуживания изменяется величина свободного времени обслуживающего устройства, что для любых систем является важнейшим технико-экономическим показателем. В табл. 1 приведены результаты имитационного эксперимента, целью которого была количественная оценка описанных изменений для различных вариантов организации обслуживания и пополнения очередей внутри поллинговой системы.

Анализ данных, представленных в таблице, показывает, что по мере сокращения времени жизни заявок ? заметно растет количество заявок, покидающих систему в связи с исчерпанием лимита времени ?, а вместе с этим увеличивается доля времени, в течение которого обслуживающее устройство оказывается свободным. Важным, на наш взгляд, является тот факт, что эти величины практически одинаковы и для исчерпывающего, и для шлюзового варианта обслуживания. Заметим также, что доля заявок, покинувших систему до завершения обслуживания, совпадает с точностью до 1 % с аналогичным показателем для системы массового обслуживания с одной очередью, который был вычислен по известному расчетному соотношению. Это полностью согласуется с выводами, сделанными авторами в работе [6], о том, что поллинговая система выполняет функцию усреднения по ансамблю и что для оценки ряда технико-экономических характеристик поллинговых систем можно использовать формулы, описывающие поведение традиционных систем массового обслуживания.

Введение ограничения на время жизни заявок, как упоминалось выше, расширяет возможности администрирования. При наличии резерва свободного времени обслуживающее устройство может быть выведено из эксплуатации для проведения планового профилактического осмотра, мелкого ремонта и т.п. без ущерба для его основной деятельности. Из материалов табл. 1 видно также, что если , величина ресурса свободного времени обслуживающего устройства, становится достаточной для организации дополнительной очереди. Действительно, если резерв свободного времени превышает 20 %, то это означает, что на обработку потока заявок от четырех очередей обслуживающее устройство затрачивает только 80 % рабочего времени. Таким образом, возникает возможность подключения к обслуживанию еще одной очереди, интенсивность пополнения которой равна среднему арифметическому интенсивностей четырех очередей, изначально входивших в состав поллинговой системы.

Еще одной целью имитационного моделирования в настоящей работе была оценка длин очередей и характера их изменения при введении ограничений на время жизни заявок. Это один из важнейших эксплуатационных показателей любых систем массового обслуживания, причем для пользователей он, несомненно, является приоритетным. Результаты имитационных экспериментов, реализованных в среде AnyLogic, представлены в табл. 2.

Как и следовало ожидать, ограничение времени пребывания заявок в стадии обслуживания значительно сокращает длины очередей поллинговой системы. Фактически из материалов табл. 2 ясно видно, что это эквивалентно соответствующему увеличению интенсивности потока обслуживания. Так, введение ограничения времени жизни заявок до дает примерно такой же эффект, как увеличение интенсивности обслуживания μ с 10 до 12. Заметим в очередной раз, что и на длину очереди поллинговой системы изменение режима обслуживания не оказывает сколько-нибудь заметного влияния. Это позволяет не принимать во внимание данный фактор при решении задач администрирования.

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

Выводы

1. Построены имитационные модели поллинговых систем с ограниченным временем жизни заявок.

2. В рамках этой модели предложен вид функции распределения потока обслуживания и установлено ее аналитическое выражение.

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

4. Расширены возможности администрирования, в частности исследована возможность подключения к обслуживанию дополнительной очереди.

Библиографическая ссылка