Построение моделей систем массового обслуживания средствами пакета MATLAB+Simulink

Министерство образования  и науки Российской Федерации

Новосибирский Государственный  Технический Университет

Кафедра Вычислительной техники

 

 

 

 

 

Индивидуальное  задание

по дисциплине

"Системы автоматизированного  проектирования"

на тему

"Построение  моделей систем массового обслуживания 

средствами пакета MATLAB+Simulink"

 

 

 

 

 

Факультет: АВТ Преподаватель:

Группа: АМ-509 к.т.н.,  с.н.с.,  доцент

Студент: Плизга В. В. Киселев А. Г.

 

 

 

 

 

Новосибирск 2009 

 

Оглавление

 

ВВЕДЕНИЕ 3

1 Выбор и обоснование инструментальных средств 4

2 Ход выполнения работы 5

2.1 Анализ основных требований 5

2.2 Подсистема Канала обслуживания 6

2.3 Подсистема Очереди 7

2.4 Подсистема Источника заявок 8

2.5 Подсистема Приемника заявок 10

2.6 Обобщение модели и подготовка к моделированию 11

2.7 Моделирование 14

3 Пути совершенствования модели 18

ЗАКЛЮЧЕНИЕ 19

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

 

 

ВВЕДЕНИЕ

Целью настоящей работы является исследование средств инженерного программного пакета MATLAB для построения, отладки и тестирования моделей систем массового обслуживания (СМО).

Задачи практикума вытекают из следующих необходимостей.

С помощью пакета MATLAB и  входящего в его состав комплекса Simulink необходимо построить модель и обеспечить возможность моделирования однофазной одноканальной СМО с ограниченной очередью и обратной связью. Потоки заявок и обслуживания должны иметь показательный закон распределения (в нотации СМО: M/M/1/10 [1]). Заявки в общем случае представляют собой сложные объекты, поэтому модель должна характеризовать каждую из них как минимум одним параметром (например, весом).

Для каждого эксперимента с моделью необходимо предусмотреть возможности задания следующих параметров:

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

По окончании каждого  эксперимента необходимо представить  следующие результаты:

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

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

 

 

1. Выбор и обоснование инструментальных средств

Инженерный программный  пакет MATLAB включает в себя множество средств для построения моделей в самых разных предметных областях. Одним из таких средств является инструмент StateFlow, входящий в состав комплекса Simulink. StateFlow изначально предназначен для построения моделей реактивных систем (или конечных автоматов), характеризующихся множеством состояний, в которые система переходит при наступлении определенных событий. Существуют приемы [2, 3], позволяющие успешно использовать этот инструмент для моделирования СМО. Однако его применение в этих целях сопряжено с рядом трудностей, главными из которых являются следующие факты:

• представление СМО в виде конечного автомата не очевидно и не однозначно (в частности, моделирование СМО с бесконечной очередью [4] (абстракция), может стать невозможным);
• переход конечного автомата из состояния в состояние не предполагает передачи какой-либо информации, в то время как почти всякое изменение в СМО сопровождается передачей какой-либо информации в/из/внутри системы;
• моделирование СМО как конечного автомата требует явного определения множества событий и условий, обеспечивающих смену состояний системы. Это существенно усложняет процесс описания модели и загромождает ее графическое представление.

В связи с перечисленными трудностями для решения поставленной задачи был выбран другой инструмент, также входящий в состав Simulink – библиотека SimEvents. Эта библиотека представляет собой набор блоков Simulink, предназначенных для моделирования систем дискретных событий (Discrete Event System, DES). Процесс построения моделей средствами SimEvents лишен недостатков, присущих StateFlow и перечисленных выше. Кроме того, эта библиотека обладает рядом полезных свойств и функций:

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

Перечисленные особенности  определяют выбор библиотеки SimEvents в качестве основного инструментального средства (наряду с MATLAB и Simulink) для решения поставленной задачи.

2. Ход выполнения работы

2.1 Анализ основных требований

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

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

Описанные требования позволяют в общих чертах обозначить функциональную схему проектируемой модели, а возможность использования иерархических блоков (подсистем) в Simulink – начать составление этой схемы (рисунок 1).

 

Рисунок 1 - Схема проектируемой модели в первом приближении

 

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

2.2 Подсистема Канала обслуживания

Для упрощения описания функциональная схема канала обслуживания приведена  на рисунке 2.

 

Рисунок 2 - Схема подсистемы канала обслуживания

 

Основным элементом подсистемы является собственно канал обслуживания (в терминологии SimEvents – сервер). Он принимает на вход заявку и "обслуживает" (задерживает) ее на заданный период времени. Длительность периода может задаваться как свойство блока, а может быть передана ему как входной сигнал. Последний вариант применен в данной работе. Источником сигнала времени задержки является подсистема Генератор времени обслуживания. Необходимость выделения отдельной подсистемы для Генератора продиктована необходимостью сформировать сигнал, величина которого, согласно заданию, случайна и распределена по показательному закону [5]. Кроме того, также согласно заданию, в блоке учитывается вес пришедшей заявки. Этот учет проявляется в суммировании сгенерированного времени обслуживания и веса заявки. Схема Генератора приведена на рисунке 3.

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

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

Рисунок 3 - Схема генератора времени обслуживания

 

В проектируемой модели для  каждой обслуженной заявки необходимо решить вопрос: будет ли заявка передана на выход, или она должна быть возвращена в очередь и, пройдя ее, вновь поступить на обслуживание? Согласно заданию, ответ должен быть  случайным, но с заданной вероятностью. Для простоты положим, что "решающая" величина имеет равномерный закон распределения и лежит в диапазоне от 0 до 1 – это позволит легко задавать пороговую вероятность возврата заявки в очередь. Именно такой подход реализован в канале обслуживания (рисунок 2). Выходной сигнал схемы "принятия решений" представляет собой индекс вывода Выходного переключателя. Этот блок в зависимости от полученного сигнала отправит пришедшую в него заявку либо на вывод 1 (обратно в очередь), либо на вывод 2 (далее в приемник).

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

2.3 Подсистема Очереди

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

Главным элементом этой подсистемы является блок очереди из библиотеки SimEvents. Он реализует очередь сущностей (заявок) заданной емкости с дисциплиной обслуживания FIFO. Емкость очереди согласно заданию равна 10 и задана как свойство блока. Дисциплина обслуживания выбрана такой лишь из соображений упрощения модели. Блок принимает на вход заявку, ставит ее в конец очереди, а заявку, стоящую в начале очереди (ею может быть и только что пришедшая), отправляет на выход, если он не заблокирован. Кроме того, в данной модели блок очереди является ценным источником разнообразной информации. Он в каждый момент опроса сообщает свое содержимое (количество заявок в очереди, ее длину), среднюю длину очереди и среднее время ожидания каждой заявки в очереди. Последняя характеристика не представляет особого интереса и потому отражается лишь на "локальном" осциллографе в отладочных целях.

 

Рисунок 4 - Схема подсистемы очереди

 

Заявки в очередь могут  поступать не только из источника  заявок, но и по обратной связи из канала обслуживания. Однако очередь  имеет лишь один вход. Решением проблемы является блок Объединителя путей, который направляет заявки с обоих своих входов на один выход. Настройки блока таковы, что если две заявки прибудут в блок одновременно, на выход первой поступит заявка, пришедшая на вход IN1. Счетчик вернувшихся заявок и соответствующий дисплей оставлены лишь в отладочных целях для верификации схемы "принятия решений" в канале обслуживания.

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

2.4 Подсистема Источника заявок

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

Ключевым элементом этой подсистемы является Формирователь  заявок – блок из библиотеки SimEvents. Его настройки позволяют указывать интервал между заявками как свойство самого блока, так и через входной сигнал. В данной модели интервал для Формирователя задает Генератор времени между заявками, схема которого представлена на рисунке 6.

Блок аналогичен Генератору времени обслуживания в подсистеме канала обслуживания. Отличия заключаются лишь в задании интенсивности потока в качестве входа подсистемы и в наличии участков контроля границ (позаимствованы из демонстрационных примеров к библиотеке SimEvents).

 

Рисунок 5 - Схема подсистемы Источника заявок

 

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

Согласно заданию, у каждой заявки должно быть некоторое собственное  свойство. В проектируемой модели таким свойством является вес  заявки. Его смысл проявляется  в увеличении времени обслуживания заявки с большим весом. Другим применением  этого параметра могло стать  распределение приоритетов в "блатной" очереди в соответствии с весами поступивших в нее заявок. Чтобы  веса у заявок были разными, но подчинялись  пользователю модели, предусмотрен простой генератор весов заявок. Он генерирует равномерно распределенное случайное число от 0 до 1, которое умножается на заданный максимальный вес, обеспечивая тем самым и случайность этого параметра, и "подчиненность" его пользователю. В частности, влияние веса на процесс моделирования может быть исключено установкой слайдера максимального веса на значение 0.

 

Рисунок 6 - Схема Генератора интервала между заявками