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

где 1/l - средняя длина пакета, измеряемая в битах.

     Процесс поступления пакетов в систему  является пуассоновским с параметром L_r (пакетов/с), где r - номер пары «узел-источник» - «узел адресат». Все пары упорядочены в соответствии с номерами 1,2,..., R. Маршрут пакетов r-го класса (передаваемых в r-й паре источник-адресат) определяется матрицей ||P_ij ( r )||, где P_ij ( r ) - вероятность того, что пакет r-о класса, закончивший обслуживание в i-м канале, поступит потом в j-й канал (i,j=1,M ).

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

     Сделанные предположения позволяют определить проектируемую систему, как открытую неоднородную сеть массового обслуживания, моделирующую функционирование системы. В такую СеМО поступают r классов пуассоновских потоков пакетов с интенсивностью L_r, маршрут каждого из которых характеризуется матрицей ||Р_ij(r)|| Функция распределения длительности обслуживания пакетов r-го пасса в i-м центре СеМО, который моделирует соответствующий канал, является экспоненциальной с параметром m_ir (пакетов/с).

     Интенсивность потока пакетов класса r, поступающих  в i-й канал l_ir удовлетворяет уравнению баланса потоков:

     Общий поток пакетов, поступающих в i-й  канал l_ir и извне в сеть L, равен соответственно:

     Обозначим через r_ir загрузку i-го канала пакетами r-го класса и r_i общую загрузку канала i:

Одноканальные СМО с неограниченной очередью можно  представить в виде графа состояний, который представлен на рисунке 3.  

     

     Рис. 3   Граф состояний одноканальной СМО с неограниченной очередью  

     S₀ – СМО свободна

     S₁ – канал занят, очереди

     S₂ – канал занят, одна заявка в очереди

     S_k – канал занят, k-1 заявок в очереди

     Финальные вероятности состояний [5]:

     Характеристики  эффективности СМО с учетом выше представленных формул            

      A=l,  Q=1, P_отк=0

     Вероятность того, что обслуживающий канал  занят:

     Многоканальные  СМО с неограниченной очередью можно  представить в виде графа состояний  которой представлен на рисунке 4. На n-канальную СМО поступает  простейший поток заявок с интенсивностью l, время обслуживания одной заявки – показательное с параметром m.

     Состояния СМО нумеруются по числу заявок в  СМО:

     S₀ – СМО свободна;

     S₁ – занят один канал;

     S_k – занято k каналов;

     S_n – заняты все n каналов;

     S_n+1 – заняты все n каналов, одна заявка стоит в очереди;

     S_n+r – заняты все n каналов, r заявок стоит в очереди.

     

     Рис. 4 Граф состояний многоканальной СМО  с неограниченной очередью  

     Финальные вероятности состояний выражаются формулами [2]:

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

Глава II. УРАВНЕНИЯ, ОПИСЫВАЮЩИЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ. ПРИМЕР МОДЕЛИРОВАНИЯ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

2.1 Процессы «рождения – гибели».³

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

³Мухин Олег Игоревич  курс «Моделирование систем» 1995 г. 

 

 

λ₀ λ₁   λ₂ λ₃ λ_n-1 

 
 

μ₀ μ₁ μ₃ μ₄ μ_n-1

Рис. 2.1 Размеченный граф процесса «рождения - гибели»  

Этот  граф воспроизводит известную биологическую  интерпретацию: величина λ_k отображает интенсивность рождения нового представителя некоторой популяции, например, кроликов, причем текущий объем популяции равен k; величина μ является интенсивностью гибели (продажи) одного представителя этой популяции, если текущий объем популяции равен k. В частности, популяция может быть неограниченной (число n состояний марковского процесса является бесконечным, но счетным), интенсивность λ может быть равна нулю (популяция без возможности возрождения), например, при прекращении воспроизводства кроликов.

Для Марковского  процесса «рождения - гибели», описанного стохастическим графом, приведенным  на рис. 2.1, найдем финальное распределение. Пользуясь правилами составления  уравнений для конечнего числа n предельных вероятностей состояния  системы S₁, S₂, S₃,… S_k,…, S_n, составим соответствующие уравнения для каждого состояния:

для состояния S₀-λ₀p₀=μ₀p₁;

для состояния S₁-(λ₁+μ₀)p₁= λ₀p₀+μ₁p₂, которое с учетом предыдущего уравнения для состояния S₀ можно преобразовать к виду λ₁р₁= μ₁p₂.

Аналогично  можно составить уравнения для  остальных состояний системы S₂, S₃,…, S_k,…, S_n. В результате получим следующую систему уравнений:

 

Решая эту систему уравнений, можно  получить выражения, определяющие финальные  состояния системы массового  обслуживания:

     

Следует заметить, что в формулы определения  финальных вероятностей состояний  р₁, р₂, р₃,…, р_n, входят слагаемые, являющиеся составной частью суммы выражения, определяющей р₀. В числителях этих слагаемых находятся произведения всех интенсивностей, стоящих у стрелок графа состояний, ведущих слева на право до рассматриваемого состояния S_k, а знаменатели представляют собой произведения всех интенсивностей, стоящих у стрелок, ведущих справа на лево до рассматриваемого состояния S_k, т.е. μ₀, μ₁, μ₂, μ₃,… μ_k. В связи с этим запишем эти модели в более компактном виде:

   к=1,n 
 

2.2 Пример. Автозаправочная станция (АЗС).

1. Постановка задачи. На рис. 30.5 приведен план АЗС. Рассмотрим метод моделирования СМО на ее примере и план ее исследования. Водители, проезжая по дороге мимо АЗС по дороге, могут захотеть заправить свой автомобиль. Хотят обслужиться (заправить машину бензином) не все автомобилисты подряд; допустим, что из всего потока машин на заправку в среднем заезжает 5 машин в час.

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение 

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