Математическая модель системы с выбором на обслуживание

Страницы:   1   2

---

Содержание

 

• Введение
• 1. Теория массового обслуживания
• 1.1. История теории массового обслуживания
• 1.2.  Описание систем поллинга
• 1.3.  Постановка задачи
• 2. Одноканальная система поллинга с двумя потоками заявок
• 2.1. Описание системы с бесконечным накопителем
• 2.2. Частные случаи
• Заключение
• Список литературы

 

Введение

 

На сегодняшний день теорию массового обслуживания как научное направление принято рассматривать в рамках теории вероятностей. Основная цель теории – выбор оптимального варианта организации производства и обслуживания населения, который обеспечивает наименьшее время обслуживания при минимальных затратах и максимальном качестве обслуживания. Базой рассматриваемой теории является математическая статистика и теория вероятности. Область применения ТМО широка, наибольшее распространение она получила в логических системах, торговле, организации узлов и систем передачи данных, т.д., в частности, для анализа количества обслуживаемых заказчиков и продолжительности их обслуживания.

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

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

Как правило, для моделей массового обслуживания устанавливаются некоторые ограничения: источники поступления заявок; вывод необслуженных заявок при заполнении очереди; очередь; проблемы наличия и количества обслуживаемых приборов и аппаратуры, время поступления заявок в систему, время обслуживания заявок, т.д.

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

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

Цель работы – обосновать теоретически и продемонстрировать практически функциональные возможности и применение теории систем массового обслуживания. Для достижения поставленной цели в работе решаются задачи:

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

 

1. Теория массового обслуживания

1.1. История теории массового обслуживания

 

В последние годы одним из основных направлений развития сетевой индустрии становятся беспроводные сети передачи информации. Для оценки характеристик таких сетей используют различные имитационные и стохастические модели. Одним из подходов к исследованию сетей является теория массового обслуживания (ТМО), в общем, и системы поллинга, в частности.

Теория массового обслуживания возникла в начале 20 века, основоположником теории считается А.К. Эрланг, который работал в телефонной компании и занимался исследованием телефонных сетей. В дальнейшем эта теория получила интенсивное развитие и применение в разных областях науки, экономики, производства. Дело в том, что эта теория исследует очень часто встречающуюся ситуацию, когда имеется некоторый прибор (или ресурс) и много заявок на его использование (в теории массового обслуживания говорят «обслуживание на приборе»). Естественно, что в такой ситуации может возникнуть очередь и задержки в обслуживании. Математическую природу этих явлений и изучает теория массового обслуживания.

Формальное описание системы массового обслуживания (СМО) состоит из следующих объектов:

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

Дж. Кендалл в 1953 году предложил краткое кодирования СМО в таком виде: A|B|n|m. Символ A характеризует входящий поток заявок, который может быть М – пуассоновским или простейшим, E – эрланговским, G – общим рекуррентным и так далее. Символ B характеризует распределение времени обслуживания заявок, которое может быть распределено по экспоненциальному закону (М), по закону Эрланга (E), и так далее. n задает число обслуживаемых приборов, m – емкость накопителя.

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

 

1.2. Описание систем поллинга

 

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

Также системы поллинга бывают дискретными (с конечным или счетным числом очередей) и непрерывными (с более чем счетным числом очередей). В данной работе рассматривается дискретная система с конечным числом очередей.

Дискретные системы поллинга отличаются следующими параметрами:

• число очередей;
• емкость накопителей для ожидания – места ожидания;
• процессами поступления и обслуживания заявок;
• длительность переключения прибора между очередями;
• порядок и дисциплина обслуживания заявок.

Порядком опроса – это правило, по которому выбирается следующая очередь для обслуживания. Порядок опроса запишем по книге [2]:

• циклический порядок – все очереди опрашиваются по кругу, такие системы поллинга называются циклическими;
• периодический порядок – прибор опрашивает очереди в соответствии с таблицей поллинга, которая содержит номера всех очередей системы;
• случайный порядок – прибор выбирает очередь для обслуживания с какой-то заданной вероятностью, или заданы вероятности перехода от обслуживания одной очереди к другой;
• приоритетный порядок – похож на обслуживание с приоритетом в обычных СМО.

Также системы поллинга различаются по дисциплине обслуживания очереди – это число заявок, которые прибор обслуживает за один раз. Дисциплины обслуживания подразделяются на следующие виды (согласно книге [2]):

• исчерпывающая дисциплина – прибор обслуживает все заявки в очереди;
• шлюзовая дисциплина – прибор обслуживает только те заявки, которые находились в очереди в момент опроса;
• l_i-ограниченную дисциплина – прибор обслуживает для каждой очереди число заявок не более l_i, которое заранее задано;
• l_i-уменьшающую дисциплина – прибор обслуживает заявки, пока длина очереди не станет на l_i меньше, или пока очередь не опустеет;
• T-ограниченная дисциплина – время обслуживания очереди ограничено;
• пороговая дисциплина – прибор обслуживает очередь, если число заявок в ней не меньше заданной величины;
• случайная дисциплина – число заявок, которые может обслужить прибор определяется значением дискретной случайной величины, причем закон распределения этой случайной величины может меняться при каждом переключении прибора.

Например, случайные дисциплины могут быть такие:

• биномиальная дисциплина, при которой случайная величина имеет биномиальное распределение с параметром, зависящим от числа заявок в данной очереди;
• дисциплина Бернулли – первая заявка в очереди обслуживается с вероятностью 1, а каждая последующая с некоторой вероятностью p_i.

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

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

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

Далее рассмотрим обзор литературы.

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

В монографии Х. Такаги [4] проведена систематизация и обобщение теоретических результатов, полученных с 1950 до 1985 года. В книге В.М. Вишневского «Теоретические основы проектирования компьютерных сетей» [1] описаны аналитические методы исследования систем массового облуживания с несколькими очередями. В [3] проведен обзор математических методов исследования систем поллинга, которые применяются при моделировании и проектировании транспортных и промышленных процессов. В книге [2] проводится систематизация моделей и методов исследований систем поллинга, также рассмотрены новые модели, описывающие функционирование широкополосных беспроводных сетей.

В работе [5] с помощью цепей Маркова доказаны некоторые свойства стационарного распределения вероятностей для системы, где заявки при поступлении выбирают очередь наименьшей длины.

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

Для систем поллинга с двумя очередями и временем обслуживания, равным одному такту дискретизации, получена система алгебраических уравнений для средних времен ожидания в очередях в [7], [8]. Такт дискретизации — это деление всего времени на интервалы равной длины, обычно равные 1. Также рассмотрена система двух очередей, когда одна очередь имеет 1-ограниченное обслуживание, а число заявок, обслуженных из второй очереди, зависит от числа заявок в первой.

Хорошо исследованы системы с циклическим обходом очередей и бернуллиевскими входящими потоками заявок в [9], [10], [11]. Для такой системы с n очередями применен принцип декомпозиции модели на n однолинейных СМО, получена функция распределения времени цикла и стационарное распределение вероятностей числа заявок в системе. Также для систем с бернуллиевскими приоритетными потоками рассмотрены следующие дисциплины обслуживания: исчерпывающая, шлюзовая, 1-ограниченная и 1-уменьшающая.

Для циклической системы поллинга с исчерпывающим обслуживанием и мгновенным переключением сервера найдены явные выражения для производящих функций числа заявок в системе и среднего времени ожидания в [12].

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

Рассмотрена система поллинга с мгновенным переключением прибора и произвольным порядком обхода очередей в [14]. Окончание обслуживания заявки в очереди определяется состоянием специально введенной случайной величины, которая может менять свое состояние только в конце такта дискретизации. Для такой системы введено понятие стабилизируемости (существует такой способ обхода очередей, при которой цепь Маркова, описывающая число заявок в очередях, является неприводимой), и получен критерий того, что система является стабильной.

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

Хорошо исследована система поллинга с двумя очередями, причем время обслуживания очереди первого типа детерминирована, время обслуживания второй очереди рекуррентно в [15]. Дисциплина обслуживания исчерпывающая. Для такой системы получено преобразование Лапласа-Стилтьеса функции распределения периода занятости системы.

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

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

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

Рассмотрена система двух очередей с l_i-ограниченным обслуживанием каждой в [19]. Для такой системы исследован рост очередей в режиме большой загрузки, получены формулы для приближенного вычисления вероятностей распределения числа заявок в каждой очереди.

Система с двумя потоками вызовов с рекуррентным обслуживанием со специальным режимом опроса очередей рассмотрена в [20]. Если в момент переключения прибора очередь пуста, то он ждет поступление заявки случайное время. Если заявка так и не поступила, то прибор переключается на следующую очередь. Рассмотрена две дисциплины обслуживания: одна очередь обслуживается исчерпывающе, а в другой обслуживается только одна заявка, и обе очереди обслуживаются исчерпывающе. Для такой системы получено преобразование Лапласа-Стилтьеса функции распределения времени ожидания в каждой очереди и средневзвешенное время ожидания. Также рассмотрена модификация этой системы, при которой прибор не ждет поступления заявки, а длительность обслуживания одной из очередей имеет распределение с тяжелым хвостом. Для такой системы получены приближенные формулы для вычисления средних времен ожидания для каждого типа заявок.

Система поллинга с дисциплиной обслуживания Бернулли или система, у которой одна очередь имеет дисциплину обслуживания Бернулли, а другая обслуживается исчерпывающе рассмотрена в [21]. Для такой системы получены стационарное распределение вероятностей в моменты окончания обслуживания, преобразование Лапласа-Стилтьеса функции распределения времени ожидания в каждой очереди и средние времена ожидания.

Система с мгновенным переключением прибора рассмотрена в [22]. Дисциплина обслуживания – пороговая, то есть заданная числом L. Если в момент окончания обслуживания число заявок в первой очереди больше чем L, то прибор мгновенно переключается на эту очередь, в ином случае прибор продолжает обслуживать вторую очередь, пока она не опустеет. Для такой системы получена производящая функция числа заявок в системе в моменты окончания обслуживания.

Система поллинга с мгновенным переключением и смешанной дисциплиной обслуживания рассмотрена в [23]. Одна очередь имеет исчерпывающее обслуживание, а другая – 1-ограниченное (или k-ограниченное) или k-уменьшающее. Для таких систем получены стационарное распределение вероятностей числа заявок в системе в моменты окончания обслуживания, средние времена ожидания для каждой очереди и проведен их анализ при разных значениях k.

Система поллинга с приоритетом рассмотрена в [24]. Очередь первого типа имеет приоритет и обслуживается исчерпывающе. Очередь второго типа обслуживается только, когда обслужены все заявки в первой очереди. Если за время обслуживания заявки второй очереди поступает вызов первого типа, то прибор дообслуживает только те заявки, которые поступили в очередь второго типа до этого момента и переключается на очередь первого типа. Для такой системы получено среднее время ожидания для каждой очереди и средняя доля времени обслуживания очереди первого и второго типа.

Система со специальным правилом обслуживания, которые задаются двумя порогами (M, N), рассмотрена в [25]. После завершения обслуживания заявки прибор выбирает очередь в соответствии с числом заявок в очереди второго типа, порогами и номером очереди, к которой прибор подключен в данный момент. Для такой системы получены условия существования стационарного режима, стационарное распределение вероятностей состояний системы в моменты окончания обслуживания и преобразования Лапласа-Стилтьеса функций распределения времени ожидания в каждой очереди. Эта модель имеет обобщение на случай нескольких приборов.

Система с обслуживанием, ограниченным по времени рассмотрена в [26]. Для такой системы получены приблизительные выражения для среднего времени ожидания в каждой из очередей.

Система со специальным выбором очереди рассмотрена в [5]. Заявка при поступлении в систему выбирает очередь с наименьшей длиной, или, при равных длинах очередей, выбирает одну из очередей с заранее заданной вероятностью. Такие системы похожи на процессы гибели-размножения и для них получены условия существования стационарного режима и аппроксимации среднего времени ожидания в очередях.

Система со специальной дисциплиной обслуживания рассмотрена в [27]. Входящие потоки заявок марковские, и емкости накопителей ограничены. Если обе очереди имеют заявки, то прибор обслуживает одновременно две заявки из каждой очереди. Если одна из очередей пустая, то прибор обслуживает заявки из другой очереди. Для такой системы построена цепь Маркова, описывающая число заявок в очередях, и найдены вероятности потери заявок каждого типа, средние длины очередей и средние времена ожидания для заявок каждого типа.

Далее перечислим результаты для систем поллинга с циклическим порядком опроса.

Система с исчерпывающим обслуживанием рассмотрена в [28]. Для такой системы найден алгоритм приближенного вычисления основных стационарных характеристик при мгновенном переключении прибора между очередями. В условиях большой загрузки процесс, описывающий число заявок в системе, сходится к диффузному процессу Бесселя. Результаты также расширены на систему с немгновенным переключением прибора в [29].

Система с исчерпывающим обслуживанием, для которой получены совместные обобщенные результаты для мгновенного и немгновенного переключения прибора между очередями рассмотрена в [30]. Также рассмотрены системы с некоторыми специальными дисциплинами обслуживания, такими как глобально-шлюзовая и элеваторная. Для таких систем получено стационарное распределение вероятностей числа заявок в очередях в моменты подключения прибора к очереди. Система, которая прекращает опрос очередей, если они пустые, а не начинает нового опроса, пока очереди не достигнут определенного заранее заданного порога, рассмотрена в [31]. Для такой системы получены условия существования стационарного режима и выражение для средневзвешенной суммы времен ожидания.

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

Система поллинга с коррелированными групповыми заявками с исчерпывающей, шлюзовой и ограниченной дисциплиной обслуживания рассмотрена в [33]. Для такой системы доказано свойство стохастической декомпозиции и получены формулы для приближенного вычисления средних времен ожидания.

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

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

Для таких систем получены преобразования Лапласа-Стилтьеса функций распределения времени ожидания и времени пребывания заявки в каждой очереди в [35].

Система с биномиальной дисциплиной обслуживания рассмотрена в [36] и [37]. Для такой системы получены точные формулы среднего числа заявок в очереди в момент подключения к ней прибора и времени ожидания в каждой очереди.

Система с дисциплиной обслуживания Бернулли. Для такой системы получены преобразования Лапласа-Стилтьеса функций распределения времени ожидания и средние времена ожидания для каждого типа очереди в [38].

Для систем со смешанной дисциплиной обслуживания (то есть дисциплина обслуживания для каждой очереди своя и выбирается из исчерпывающей, шлюзовой, 1-ограниченной или полуисчерпывающей) получены формулы для вычисления моментов любого порядка времени ожидания в очередях, преобразование Лапласа-Стилтьеса распределений времен ожидания в условиях большой загрузки в [39].

Как и в теории массового обслуживания можно рассматривать системы поллинга с ненадежным прибором. Интервалы между поломками распределены экспоненциально. Если поломка произошла в момент обслуживания заявки, то может быть несколько случаев: заявка дообслуживается и уходит или обслуживание заявки прерывается и после восстановления прибора, она обслуживается заново. Для такой системы получены приближенные значения среднего времени ожидания в каждой очереди в [40].

Системы поллинга с двумя очередями с возвращающимися заявками рассмотрена в [41]. В таких системах после обслуживания заявки она может с некоторой вероятностью вернуться в конец очереди. Для такой системы получены средние времена ожидания в очередях.

Система поллинга с приоритетными очередями. В такой системе, как и в СМО, каждая очередь имеет свой приоритет. Очередь может быть обслужена только в том случае, если очереди с более высоким приоритетом пусты. Рассмотрена в [42] симметричная система с двумя приоритетными очередями, в каждую из которых поступает два пуассоновских потока. Очередь не ограничена для приоритетного потока, а для заявок низшего приоритета есть только одно место для ожидания. Если в очереди есть приоритетная заявка, то прибор обслуживает ее и затем переходит к другой очереди. Если более приоритетной заявки нет, то прибор обслуживает очередь с более низким приоритетом. Для такой системы получено среднее время ожидания для заявок каждого приоритета.

Обобщение предыдущей системы на n приоритетных классов заявок рассмотрена в [43]. Для этой системы получено стационарное распределение для цепи Маркова, характеризующей поведение системы в моменты поллинга.

Далее приведем некоторые результаты для систем поллинга с очередями конечной емкости.

Система поллинга вида M|G|1|n с исчерпывающей дисциплиной обслуживания рассмотрена в [44]. Для такой системы получено преобразование Лапласа-Стилтьеса функции распределения времени от момента отключения прибора от данной очереди до момента подключения прибора к этой очереди снова. Для системы с очередями единичной емкости получены формулы для вычисления моментов любого порядка времен ожидания в очередях. Для систем поллинга вида G|D|1|n найден алгоритм расчета стационарного распределения числа заявок в системе в [45].

Система поллинга с ограниченным временем обслуживания очередей рассмотрена в [46]. Среднее время пребывания сервера у i-ой очереди ограничено постоянной величиной T_i. Для такой системы получено стационарное распределение вероятностей системы в моменты подключения прибора к очереди.

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

Система поллинга с дисциплиной обслуживания, обладающей свойством ветвления, рассмотрена в [48]. Для такой системы получена система уравнений для средних времен ожидания в каждой очереди в условиях большой загрузки.

Система поллинга с простоями прибора рассмотрена в [49]. Если в системе закончились вызовы, то прибор уходит на простой, длительность которого имеет заданную функцию распределения. Для такой системы получены преобразования Лапласа-Стилтьеса функций распределения времен ожидания для каждой очереди, средние времена ожидания в очередях и вероятность простоя прибора.

Системы поллинга с повторными вызовами рассмотрена в [50]. Заявки поступают в виде группового пуассоновского потока. Каждая группа разбивается на подгруппы, поступающие в соответствующую очередь. Когда прибор переключается на одну из очередей, каждая заявка пытается занять прибор через экспоненциальные промежутки времени. Прибор ждет, когда какая-нибудь заявка создаст запрос или поступит новая заявка. После завершения обслуживания прибор опять ждет экспоненциальное время, и если за это время ни одна заявка не сделала попытки обслужиться или не поступала новая заявка, переключается на другую очередь. Для такой системы получено среднее число заявок в каждой очереди при работе в стационарном режиме.

Замкнутые системы поллинга похожи на замкнутые СМО. В таких системах все заявки сразу находятся в системе, и не поступает заявок извне системы. Рассмотрена в [51] система поллинга, в которой каждая очередь содержит по одной заявке. После окончания обслуживания на приборе заявка должна обслужиться на внешнем устройстве, а затем она опять возвращается в очередь. Для такой системы получено преобразование Лапласа-Стилтьеса функции распределения времени ожидания.

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

Система поллинга с исчерпывающей дисциплиной обслуживания рассмотрена в [52]. В случае если в системе нет заявок, возможны различные варианты поведения прибора: прибор останавливается у текущей очереди и ждет поступления в систему заявки, чтобы начать опрос очередей; прибор останавливается у текущей очереди и ждет поступления в систему заявки, чтобы переключиться на эту очередь; прибор перемещается к очереди, которая называется базовой, и ждет поступления в систему заявки, чтобы переключиться на эту очередь. Для такой системы получено преобразование Лапласа-Стилтьеса функций распределения времен ожидания в очередях.

Система, состоящая из очередей типа MAP|PH|1, с мгновенным переключением прибора между очередями и исчерпывающей дисциплиной обслуживания рассмотрена в [53]. Время пребывания прибора у каждой очереди ограничено, и если это время истекло, а обслуживание заявки не закончено, то такая заявка потом дообслуживается. Для такой системы получена функция распределения периода занятости, и разработан алгоритм, с помощью которого можно найти среднее число заявок в очередях.

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

Система с тремя очередями рассмотрена в [54]. Заявки, поступающие в первую очередь, управляются цепью Маркова с двумя состояниями, от которых зависит поступает или нет заявка в систему. Во вторую и третью очередь поступают бернуллиевские потоки заявок. Первая очередь имеет абсолютный приоритет. Если в эту очередь поступает заявка, то прибор на следующем такте переключается на нее. Когда в первой очереди заканчиваются заявки, то прибор переключается на вторую или третью очередь. Дисциплина обслуживания второй очереди – шлюзовая, третьей – 1-ограниченная. Для этой системы получены средние времена ожидания для каждой очереди.

Система с коррелированными заявками, в которой очереди имеют емкость единица, рассмотрена в [55]. Порядок обслуживания определяется с помощью заданного набора вероятностей. Рассматриваются модели двух видов: очередь принимает новую заявку только после окончания обслуживания предыдущей; очередь доступна для новой заявки сразу после начала обслуживания предыдущей заявки. Для такой системы получена система линейных алгебраических уравнений для вычисления средних времен ожидания в очередях.

Использование систем поллинга.

В основном, системы поллинга используются для исследования сетей широкополосного доступа, например, сетей Wi-Fi, для персональных и локальных беспроводных сетей, для систем спутниковой связи. Также задачи по разделению времени прибора возникают в промышленных системах, в нефтегазовой отрасли.

В транспортных системах возникают задачи по опросу датчиков, установленных на разных узлах. Такие задачи можно смоделировать как систему циклического опроса.

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

 

1.3. Постановка задачи

 

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

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

Во 2 части данной работы рассматривается такая система массового обслуживания (поллинга) с двумя накопителями.

---

Страницы:   1   2