Главная страница

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


Скачать 1.27 Mb.
НазваниеУчебник для студентов высших учебных заведений, обучаемых по направлениею
АнкорПриложения теории массового обслуживания
Дата30.06.2022
Размер1.27 Mb.
Формат файлаpdf
Имя файлаlozhkovskii_ag_teoriia_massovogo_obsluzhivaniia_v_telekommun.pdf
ТипУчебник
#621010
страница8 из 14
1   ...   4   5   6   7   8   9   10   11   ...   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
1   ...   4   5   6   7   8   9   10   11   ...   14


написать администратору сайта