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

• Название: Учебник для студентов высших учебных заведений, обучаемых по направлениею
• Анкор: Приложения теории массового обслуживания
• Дата: 30.06.2022
• Размер: 1.27 Mb.
• Имя файла: lozhkovskii_ag_teoriia_massovogo_obsluzhivaniia_v_telekommun.pdf
• Тип: Учебник; #621010
• страница: 8 из 14

7.5 Система с неограниченной очередью M/G/1/∞
Односерверная система (рис. 7.3) с неограниченным количеством мест ожидания обслуживает пуассоновский поток требований. Длительность обслу- живания имеет произвольный закон распределения B(x) с математическим ожиданием
x
. Интенсивность потока требований λ. Найти характеристики QoS.
Рисунок 7.3 – Модель односерверной системы с очередью
В модели распределение длительности обслуживания не экспонентное, а интервал времени между требованиями имеет экспонентное распределение.
Поэтому данная задача решается методом вложенных цепей Маркова.
Понятие вложенной цепи Маркова сводится к следующему. Пусть (g
t
)– случайный процесс с непрерывным временем, приобретающим только целые числовые значения из некоторого множества G, и существует последова- тельность t
1
, t
2
, ... (тоже случайная) моментов времени такая, что процесс (ξ
n
)
n
t
n
g


, n = 1, 2, …
(7...54) является однородной марковской цепью с дискретным временем, т.е. для
п = 2 , 3, ... имеет место:













)
,...
,
|
(
1 1
2 2
1
i
i
i
j
n
n
n
n
)
|
(
)
|
(
1 2
1
i
j
i
j
n
n













,
(7.55) где j, и, и
1
…  G.
Процесс (ξ
n
) есть марковской цепью, вложенной в (g
t
). Основное содержание метода вложенных цепей Маркова состоит в том, что для данного случайного процесса, описывающего поведение рассмотренной модели, конструируется удобная марковская цепь, исследуемая аналитическими методами, обычными для цепей Маркова, и полученные результаты (например, стационарные вероятности состояний) пересчитываются для величин исходной системы.
Исследуемая модель принимает состояния 0, 1, 2, ..., а g
t
– количество требований, находящихся в системе в момент времени t или g
t
, есть состояние системы в момент времени t; (g
t
)– не марковская цепь. Определим характеристики QoS – средние значения количества требований и времени ожидания в системе.
Метод вложенных цепей состоит из следующих четырех шагов:
Ш а г 1 . Определим последовательности моментов времени (t
n
),
0 < t
1
< t
2
< ... < ∞, что позволяет конструирование вложенной цепи Маркова.
Разумеется, если все распределения экспонентные, то (g
t
)– однородная
∞
1 2
3 4
5 очередь
FIFO сервер поток требований λ обслуженные требования

53 марковская цепь и в качестве (t
n
) можно выбрать любую возрастающую последовательность моментов времени 0 ≤ t
n
< ∞. Если не все распределения, характеризующие поведение элементов системы, экспонентные, то (g
t
)– не марковская цепь, и если только одно распределение не экспоненциально, то состояние системы в момент времени t можно описать с помощью величины ξ
*
t
:
ξ
*
t
= (g
t
, r
t
),
(7.56) где
ξ
*
t
– преобразование
Лапласа-Стилтьеса непрерывной функции распределения ξ
t
, с помощью которого путем дифференцирования можно определить соответствующие моменты этого распределения.
Для дополнительной переменной r
t
полагается следующее: r
t
равно остаточному временные не экспонентно распределенной величины в момент времени t, если такой существует (например, остаточное время обслуживания, остаточное время паузы); r
t
= 0, если отсутствует такое остаточное время
(например, не обслуживается ни одно требование; нет паузы с неэкспонентным распределением).
Значения t
n
находится таким способом. Остаточным временем r
t
есть остаточная продолжительность обслуживания. Она будет равна нулю, если некоторое требование оставляет систему. Поэтому полагается, чтобы t
n
равнялось моменту времени, когда n-ое требование покидает систему (момент выхода).
Сконструированный с помощью дополнительной переменной
r
t
двумерный стохастический процесс
(ξ
*
t
) рассматривается только в определенных точках t
n
, то есть в моменты выхода требований из системы, а потому он есть однородным марковским и распределение этого процесса можно определить.
Ш а г 2 . Вычислим переходные вероятности для вложенной цепи
Маркова. Пусть ξ
n
– количество требований, которые находятся в системе непосредственно после момента t
n
, то есть
0



n
t
n
g
. При этом (ξ
n
) – однородная марковская цепь. Пусть р
i,j
– независимая от п вероятность перехода системы в момент выхода из нее требования:
)
|
(
1
,
i
j
p
n
n
j
i







,
и, j = 0, 1, 2, ...
Обозначим через k
j
вероятность того, что за время обслуживания некоторого требования в систему поступает j новых требований; тогда













случаях.
других в
0
:
,
2
,
1
,
1
при
;
0
,...,
2
,
1
,
0
при
1
,
i
i
j
k
i
j
k
p
i
j
j
j
i
(7.57)
Поскольку требования поступают по пуассоновскому закону с интенсивностью λ, то для них вероятность того, что на интервале времени продолжительностью t поступит точно j требований, равна (4.5), и потому







0
,
1
,
0
),
(
!
)
(
j
t
dB
e
j
t
k
t
j
j
(7.58)

54
Производящая функция K*(z) распределения (k
j
) по определению:




0
*
)
(
j
j
j
z
k
z
K
(7.59) где z – комплексная переменная. Из (7.59) с учетом (7.58) и в соответствии с
[5, с.205]
)
(
)
(
*
*
z
B
z
K




(7.60)
Поскольку B(x) есть функцией распределения продолжительности обслуживания, то полученное из (7.58) уравнение устанавливает взаимосвязь между образующей функцией K* дискретного распределения случайной величины
k
j
(количества требований за время обслуживания) и преобразованием
Лапласа-Стилтьеса
B* плотности непрерывного распределения случайной величины x (продолжительности обслуживания) в точке (λ – λz). Первая производная образующей функции в точке z = 1 и преобразования Лапласа-Стилтьеса в точке z = 0 позволяет вычислить первые моменты рассматриваемой случайной величины. Поэтому из этого для данного уравнения следует, что







x
B
K
)
0
(
)
1
(
'
'
*
*
(7.61)
В (7.61) последнее уравнение следует из (5.3) и (7.28).
Ш а г 3 . Вычислим стационарное распределение для вложенной цепи
Маркова. Вложенная марковская цепь неприводима, апериодическая и в случае
ρ < 1 – эргодическая (доказано с помощью теоремы Фостера). Поэтому существует точно одно стационарное начальное распределение (P
j
) цепи, где P
j
– вероятность того, что в стационарном состоянии требование, покидающее систему, после себя оставляет j требований. Поэтому вероятности P
j
удовлетворяют системе уравнений, аналогичной (7.2):


i
j
i
i
j
p
P
P
,
,
(7.62) т. е.
)
(
1 0
0 0
P
P
k
P


;
,
2
,
1
,
1 1
0 0








j
k
P
j
k
P
P
i
j
j
i
i
j
Аналогично (7.59) образующая функция Р*(z) распределения P = (P
j
)





0 1
|
z
|
,
)
(
*
j
j
j
P
z
z
P
, поэтому имеем:



















0 1
1 1
*
1
*
0 1
0 0
)
(
)
(
)
(
*
j
j
i
i
i
i
i
j
i
j
j
j
j
z
K
z
P
z
K
P
k
P
z
z
k
P
z
P

55
После сокращений получаем, что
z
z
K
z
K
z
P
P
z
P
z
z
K
z
K
P
z
P






)
(
)
(
)
1
(
)
)
(
(
)
(
)
(
)
(
*
*
*
0 0
*
*
*
0
(7.63)
В (7.63) входит неизвестная пока что константа Р
0
. Ее можно определить с помощью следующих вычислений, типичных при работе с образующими функциями.
Поскольку
1
)
(
lim
)
(
*
lim
*
1
z
1
z




z
K
z
P
, а























1 1
)
1
(
1 1
1 1
lim
1
)
(
*
lim
'
*
1
z
1
z
K
z
z
z
(z)
K
z
z
z
K
*
, это из (7.63) при z → 1 следует уравнение: 1 = Р
0
/ (1 – ρ), из чего


 1 0
P
,
(7.64)
)
(
1
)
1
)(
1
(
)
(
)
(
)
1
)(
1
(
)
(
*
*
*
*
z
B
z
z
z
z
K
z
K
z
z
P













(7.65)
Формулу (7.65) называют соотношением Поллачека-Хинчина, которое задает образующую функцию стационарного распределения вложенной марковской цепи в точках, когда требования оставляют систему М/G/l/∞, как функцию от преобразования Лапласа-Стилтьса функции распределения продолжительности обслуживания.
Ш а г 4 . Пересчитаем полученные на шаге 3 результаты в искомые величины системы: 1. Среднее количество требований в системе 2. Среднее время ожидания в системе (в том числе и для точек, отличных от t
n
).
1. Среднее количество требований в системе N.
В рассмотренной модели М/G/l/∞ вероятности того, что в стационарном состоянии поступающее в систему требование застает в ней j других требований, равны стационарным вероятностям Р
j
наличия в системе j требований непосредственно после окончания обслуживания некоторого требования, и потому они задаются формулой (7.65). Из-за свойства пуассоновского потока требований эти вероятности равны стационарным вероятностям P
j
в любой момент времени.
Математическое ожидание (среднее значение) количества требований N, которые находятся в системе, равно производной от (7.65):
)
1
(
2
)
1
(
*
2 2
'








x
P
N
,
(7.66) где
2 2
0 2
2
)
(
x
x
x
x
dB
x







(7.67)

56
Параметры
2
x и
2
x

характеризуют математическое ожидание (среднее значение) и дисперсию или второй центральный момент функции распределения случайной длительности обслуживания требований x.
Формулу (7.66) называют формулой Поллачека-Хинчина.
2. Среднее время ожидания в системе W.
Пусть W(t) – стационарная функция распределения времени ожидания и
W*(s) – его преобразования Лапласа-Стилтьеса:
)
(
)
(
0
*
t
dW
e
s
W
st




Пусть V – функция распределения времени пребывания в стационарном состоянии; время пребывания равно времени ожидание плюс время обслуживания. Поскольку время ожидания и следующая продолжительность обслуживания стохастично независимые, то для преобразования Лапласа-
Стилтьеса V*(s)времени пребывания в стационарном состоянии на основании теоремы свертки (умножения) имеем:
)
(
)
(
)
(
*
*
*
s
B
s
W
s
V

(7.68)
Количество требований, находящееся в системе, когда ее покидает некоторое требование, равно количеству требований, поступающих в систему за время пребывания в системе требования, которое покидает её. Поэтому, между функцией распределения времени пребывание V(t)и распределением P
j
существует такая связь:
)
(
!
)
(
0
t
dV
e
j
t
P
t
j
j






(7.69)
Для образующей функции P*(z) распределения (Р
i
)из (7.69) с учетом
(7.68) и (7.60) получаем:





















0 0
*
*
*
)
1
(
*
)
(
)
(
)
(
)
(
)
(
j
z
t
j
j
z
B
z
W
z
V
t
dV
e
P
z
z
P
Из этого и из (7.65) следует, что
)
(
)
1
(
)
(
)
/
1
(
)
(
*
*
*
*
s
B
s
s
s
B
s
P
s
W










Поскольку математическое ожидание W = –W*
'
(0), то, взяв производную для стационарного состояния, получаем:
)
1
(
2
)
(
)
1
(
2 2
2 2










x
x
x
W
(7.70)
Для характеристики второго центрального момента распределения длительности обслуживания
2
x

часто используется коэффициент вариации ν
x
:

57
x
x
x



(7.71)
Сумму
2 2
x
x


с учетом (7.71), можно представить как
)
1
(
2 2
x
x


Подставив это в (7.66) и (7.70) получим окончательные формулы расчета N и W.
С учетом (6.3), (6.4), (7.44) и (7.45) получаем все другие характеристики QoS, формулы которых занесенные в табл. 7.1. Значения W, t
q
и T нормируются по
x
Таблица 7.1 – Характеристики качества обслуживания модели М/G/l/∞
Модель
Характеристика
QoS
M/G/1/∞
M/D/1/∞
M/M/1/∞
Р
w>0
ρ
ρ
ρ
Q
)
1
(
2
)
1
(
2 2





x
)
1
(
2 2






1 2
W
)
1
(
2
)
1
(
2





x
)
1
(
2






1
t
q
)
1
(
2 1
2




x
)
1
(
2 1




1 1
N
)
1
(
2
)
1
(
2 2







x
)
1
(
2 2














1 1
2
T
)
1
(
2
)
1
(
1 2






x
)
1
(
2 1











1 1
1 1
В табл. 7.1 записаны и формулы всех характеристик QoS моделей М/D/l/∞ и М/M/l/∞, для которых коэффициент вариации ν продолжительности обслуживания регулярного и экспонентного распределений равен 0 и 1 соответственно. Из табл. 7.1 видно, что при постоянной продолжительности обслуживания значения W, t
q
и Q в два раза меньшие, чем при экспонентной.
Приведенные в табл. 7.1 значения характеристик QoS для модели М/M/l/∞ соответственно совпадают с (7.27), (7.32), (7.33) и (7.34).
Для m-серверной системы M/G/m/∞ простого решения не существует, однако есть приближенные оценки. В частности, среднее стационарное время ожидания W
m
удовлетворяет неравенству
x
m
x
m
W
x





2 2
2 2
Доказательство данного соотношения приведено в [7].

58