Учебное пособие 800529

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

4.5.3. Многоканальная СМО с отказами

В связи с наличием n каналов состояние S1 одноканальной СМО последовательно размножится от S1 до Sn. Размеченный граф состояний такой СМО имеет вид

Состояния будут: S0 – все каналы свободны; S1 – занят один канал, все остальные свободны; … Sn – заняты все n каналов. Интенсивность потока, переводящая систему слева направо везде одинакова и равна λ. Интенсивность потока обслуживания наращивается, так как последовательно увеличивается число параллельных каналов, занятых обслуживанием.

Рассмотрим случай, когда система находится в состоянии Sk (k=1, 2, … n-1). В этом состоянии действуют два потока: первый, с интенсивностью λ, стремящийся перевести систему в состояние

Sk+1 (но не в Sk+2 и т.д., то есть не по принципу «домино», а только в соседнее состояние, когда будет задействовано параллельно не

«k», а «k+1» канал); второй, c интенсивностью kμ – поток освобождения всех k занятых каналов сразу, переводящий систему «влево». Так как интенсивность kμ > λ, то перевод системы в «левые» состояния более вероятен, чем в «правые».

Поведение системы также описывается системой дифференциальных уравнений А.Н.Колмогорова, которая для стационарного

ет вид

271

0 = - l p0 + mp1 , K

0 = - (l + km) pk + l pk- 1 + (k + 1)mpk + 1 , K

0 = - nmpn + l pn- 1 ,

где pi , i = 0, n - вероятности нахождения системы в состояниях

Si , i = 0, n .

Введя обозначения

ui = - l pi- 1 + impi , i = 1, n ,

перепишем систему уравнений так: u1 = 0,

K

272

Введѐм обозначение l m = r и будем эту величину именовать

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

С учетом этого обозначения формулы примут вид

рактеристики СМО: относительную и абсолютную пропускные способности q и A соответственно и вероятность отказа Ротк

Вероятность того, что заявка будет принята к обслуживанию, дополняет Ротк до единицы, то есть

q = 1- pn = Pотк .

Абсолютная пропускная способность

4.5.4. Одноканальная СМО с ожиданием

Это тоже простейшая из СМО: n = 1, λ – интенсивность потока заявок; μ – интенсивность обслуживания, под которой понимается среднее число обслуженных заявок, выдаваемых непрерывно занятым каналом в единицу времени.

Будем именовать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и находящихся в очереди, ожидая обслуживания). Эти состояния таковы:

S0 – канал свободен;

S1 – канал занят, очереди нет;

S2 – канал занят, одна заявка стоит в очереди;

…

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

273

…

Sm+1 – канал занят, m заявок стоит в очереди.

Размеченный граф СМО выглядит так:

Изображѐнная схема представляет собой схему «гибели и размножения», давно рассматриваемую в биологии при изучении популяций хищников и их жертв. Так как такие задачи по аналогии часто возникают в технике, рассмотрим эту модель чуть подробнее.

Марковская непрерывная цепь называется «процессом гибели

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

в которой каждое из внутренних состояний (S1, … , Sm) связано прямой и обратной связью с каждым из соседних состояний, а

крайние (S0, Sm+1) – только с одним из соседних состояний. Указанным «гибельным» состояниям можно дать следующую

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

Из-за марковского свойства математическая модель «гибели

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

274

Вспомнив мнемоническое правило составления уравнений (плюс интенсивность, если стрелка входит в состояние и минус интенсивность – если выходит), составим уравнение для первого состояния

dpdt1 = 0 = - l 12 p1 + l 21 p2 ,

где p1 и p2 – вероятность состояний S1 и S2 соответственно;

Заменяя второй член уравнения (2) его значением из уравнения (1), получим:

l 23 p2 = l 32 p3 ,

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

l 34 p3 = l 43 p4 ,

K

l k- 1,k pk - 1 = l k ,k- 1 pk .

В соответствии с этим предельные вероятности состояний p1, p2, … , pn в любой схеме гибели и размножения удовлетворяют уравнениям

l 12 p1 = l 21 p2

l k - 1,k pk - 1 = l k ,k - 1 pk

l n- 1,n pn- 1 = l n,n- 1 pn

и нормировочному условию p1 + p2 + L + pn = 1.

Будем решать систему так: из первого уравнения найдѐм

p2 = l 12 l 21 p1 ,

275

из второго

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

Таким образом находятся предельные вероятности всех состояний

Неизвестное значение p1 находится совместно с учетом нормировочного условия и имеет вид:

Важны также интегральные оценки, имеющие вид:

где n - первичное число особей.

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

276

Определим основные характеристики СМО:

заявка получит отказ, если канал занят и m мест в очереди тоже, то есть

относительная пропускная способность

абсолютная пропускная способность

A = l Чq;

среднее число заявок, находящихся в очереди

277

среднее время ожидания в очереди

tож = r l ;

среднее время пребывания заявки в системе

tсист = tож + q m .

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

278

4.5.5. СМО с «взаимопомощью» между каналами

Мы рассматривали СМО, в которых каждая заявка обслуживается только одним каналом, а незанятые каналы не могут «помогать» занятому в обслуживании. Это не так, особенно в современных телекоммуникациях. В них одна заявка (сообщение), разбившись на пакеты, может одновременно обслуживаться двумя и более каналами.

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

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

2.Какова «дисциплина (протокол!) взаимопомощи», то есть когда и как несколько каналов берут на себя обслуживание одной

итой же заявки?

Ответ на первый вопрос. При увеличении числа каналов, обслуживающих заявку, интенсивность обслуживания будет возрастающей функцией числа каналов μ(k). Вид этой функции следует задать. Для простоты возьмѐм случай, когда μ(k) возрастает линейно до kкр, а при k>kкр остаѐтся постоянной. Если при этом число каналов n, помогающих друг другу, не превосходит kкр, то есть n Ј kкр , то интенсивность обслуживания будет пропорциональна

числу каналов.

Ответ на второй вопрос. Самой простой дисциплиной помощи является помощь по принципу «все как один». То есть с появлением заявки все n каналов «бросаются» еѐ обслуживать и многоканальная СМО превращается в одноканальную, но с бóльшей интенсивностью обслуживания. Выгодно или невыгодно вводить такую дисциплину – помощь? Рассмотрим примеры.

Пример 1. Имеется трехканальная СМО с отказами: интенсивность потока заявок λ=4 (заявки в минуту), среднее время обслуживания одной заявки одним каналом tоб = 0,5 (мин), функция m(k)= km. Спрашивается, выгодно ли с точки зрения пропускной

способности СМО вводить взаимопомощь между каналами по типу «все как один»? Выгодно ли это с точки зрения уменьшения среднего времени пребывания заявки в системе?

279

Решение. а. Без взаимопомощи.

п = 3, λ = 4, μ = 1/0,5 =2, ρ = λ/μ = 2.

По формулам Эрланга имеем:

Относительная пропускная способность СМО:

q = 1- Pотк » 0, 79 .

Абсолютная пропускная способность:

A = l q » 4Ч0, 79 = 3,16.

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

= 0,79Ч0,5 = 0,395 (мин).

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

t(систоб) = tоб = 0,5 (мин).

б. Со взаимопомощью.

п* = 1, λ = 4, μ* = 3μ = 6, ρ* = λ/μ* = 2/3;

A = l q = 4Ч0,6 = 2, 4.

Среднее время пребывания заявки в СМО:

tсист = p1 Ч1 3m= 25Ч6 = 0, 0667 (мин).

Среднее время пребывания обслуженной заявки в СМО:

t(систоб) = 13m= 0,167 (мин).

280