close

Вход

Забыли?

вход по аккаунту

?

Многомодальность высокоинтенсивного полумарковского потока в условии предельно редких изменений его состояний..pdf

код для вставкиСкачать
Управление, вычислительная техника и информатика
СПИСОК ЛИТЕРАТУРЫ
1. Баласанян С.Ш. Стратифицированная модель для оценки
и анализа эффективности функционирования сложных техно
логических систем со многими состояниями // Известия Том
ского политехнического университета. – 2011. – Т. 318. – № 5.
– С. 25–30.
2. Баласанян С.Ш. Метод стратифицированной формализации
сложных систем с учетом надежности // Вестник ГИУА. Серия
«Моделирование, оптимизация, управление». – 2007. – Т. 1. –
Вып. 10. – С. 22–32.
3. Бусленко Н.П. Моделирование сложных систем. 2е изд. – М.:
Наука, 1978. – 399 с.
4. Сирота А. Компьютерное моделирование и оценка эффектив
ности сложных систем. – М.: Техносфера, 2006. – 280 с.
5. Месарович М., Такахара И. Общая теория систем: математиче
ские основы. – М.: Мир, 1978. – 311 с.
Поступила 19.06.2012 г.
УДК 519.872
МНОГОМОДАЛЬНОСТЬ ВЫСОКОИНТЕНСИВНОГО ПОЛУМАРКОВСКОГО ПОТОКА
В УСЛОВИИ ПРЕДЕЛЬНО РЕДКИХ ИЗМЕНЕНИЙ ЕГО СОСТОЯНИЙ
А.А. Назаров1, В.З. Ямпольский2, М.А. Яценко3
1
Томский государственный университет
Томский политехнический университет
3
ООО «ИНКОМ»
Email: yvz@tpu.ru
2
Построена математическая модель телекоммуникационного потока в виде высокоинтенсивного полумарковского потока
в условии предельно редких изменений его состояний, который обладает свойством многомодальности распределения вероят
ностей числа его событий, наступивших за единицу времени. Показана линейная зависимость его характеристик от времени на
блюдения за потоком.
Ключевые слова:
Телекоммуникационные потоки, высокоинтенсивные полумарковские потоки, предельно редкие изменения состояний потока,
многомодальность распределения.
Key words:
Telecommunication streams, highintensity semiMarkov streams, extremely rare stream state changes, multimodal distributions.
Введение
Статистические исследования реальных теле
коммуникационных потоков показывают, что не
которые из них обладают свойством многомодаль
ности гистограмм числа их событий, наступивших
за единицу времени. Применение методов провер
ки статистических гипотез не отклоняют гипотезу
о том, что теоретическое распределение генераль
ной совокупности является смесью нормальных
распределений.
Ставится задача построения математической
модели таких потоков, обладающих свойством
многомодальности распределений числа событий,
наступивших в этих потоках за единицу времени.
В работе показано, что этим свойством обладает
высокоинтенсивный полумарковский поток в
условии предельно редких изменений его состоя
ний.
Высокоинтенсивный полумарковский поток
в условии предельно редких изменений его состояний
Пусть задана диагональная матрица
А(х) раз
⎯
мерности L с элементами Аl(х), l=1,L и стохастиче
ская матрица
P = I + δQ
размерности L×L с элементами
Pl l = δ l l + δql l ,
1 2
1 2
(1)
1 2
где I – единичная матрица; δl l – символ Кронеке
ра; δ – некоторый малый параметр. Также задан
положительный большой параметр N.
Рассмотрим полумарковский
⎯ процесс l(t), при
нимающий значения l(t)=l=1,L с условно незави
симыми компонентами [1], полумарковская ма
трица которого факторизуется и равна произведе
нию
A(Nx)P =A(Nx)(I+δQ).
(2)
Обрабатывающий его процесс n(t) определяет
число событий, наступивших за время t в полумар
ковском потоке (SMпотоке), заданным полумар
ковской матрицей (2).
Полумарковский процесс l(t) будем называть
процессом, управляющим полумарковским пото
ком, а значения l(t)=l этого процесса будем назы
вать состояниями SMпотока.
В состоянии l длина ξl интервала между момен
тами наступления событий рассматриваемого по
тока определяется функцией распределения
12
19
Известия Томского политехнического университета. 2012. Т. 321. № 5
P{ξl<x} = Al(Nx).
Наличие здесь большого параметра N оправды
вает название – высокоинтенсивный поток. Нали
чие малого параметра δ, который определяет в (2)
вероятности смены состояний потока, оправдыва
ет применение названия условия: условие предель
но редких изменений состояний SMпотока.
Ниже будет выполнено исследование рассма
триваемого высокоинтенсивного полумарковского
потока в условии предельно редких изменений его
состояний, применяя подходы, развитые в работах
[2] и [3].
Уравнение Колмогорова
Применяя метод дополнительных компонент,
рассмотрим трехмерный марковский случайный
процесс {l(t),z(t),n(t)}, где z(t) – длина интервала
от момента t до момента наступления следующего
события в рассматриваемом потоке. Компоненты
l(t) и n(t) этого процесса определены выше. Здесь
l(t) – полумарковский процесс, управляющий рас
сматриваемым потоком, а n(t) – число его собы
тий, наступивших за время t.
Обозначая распределение вероятностей
z
⎧
⎫
P ⎨l (t ) = l , z (t ) < , n(t ) = n ⎬ = P (l , z , n , t ),
N
⎩
⎭
запишем равенство
P{l , z − N Δt , n, t + Δt} =
= P (l , z , n, t ) − P(l , N Δt , n, t ) +
L
+ ∑ P (l1 , N Δt , n − 1, t ) Pl1l Al ( z ) + o (Δt ),
l1 =1
из которого получим уравнение Колмогорова
∂P (l , n, t )
∂P (l , z , n, t )
∂P (l , 0, n, t )
=N
−N
+
∂t
∂z
∂z
L
∂P (l , 0, n − 1, t )
+∑ N
Pl l Al ( z ),
∂z
l =1
1
1
где применяется обозначение
∂P (l ,0, n, t ) ∂P(l , z, n, t )
=
∂z
∂z
.
z =0
Определяя вектор строку
P ( z, n, t ) = {P(1, z, n, t), P(2, z, n, t),..., P( L, z, n, t)},
последнее уравнение перепишем в матричном виде
1 ∂P( z, n, t ) ∂ P( z, n, t ) ∂ P(0, n, t)
=
−
+
N
∂t
∂z
∂z
∂P (0, n − 1, t )
+
(I + δ Q) A ( z ).
(3)
∂z
Обозначая векторную характеристическую
функцию
∞
H ( z, u, t ) = ∑ e jun P( z, n, t ),
n=0
⎯
где j=√–1 – мнимая единица, и применяя уравне
ние (3), для функции H(z,u,t) запишем равенство
20
1 ∂H ( z , u , t ) ∂ H( z , u , t ) ∂ H(0, u, t )
=
+
×
N
∂t
∂z
∂z
×(e ju A ( z ) − I + δ e ju QA ( z )).
(4)
Рассматривая стационарный SMпоток, будем
полагать, что выполнено условие
H ( z, u,0) = R( z).
(5)
Функцию R (z) найдем из уравнения (4), приме
няя равенство
H ( z, u,0) = R( z) = H( z,0, t),
(6)
в котором вектор функция R(z) является стацио
нарным распределением вероятностей
z⎫
⎧
R ( z ) = P ⎨l (t ) = l , z (t ) < ⎬
N
⎩
⎭
двумерного случайного процесса {l(t),z(t)}.
Подставляя (6) в (4), для распределения R(z) по
лучим уравнение
R ′(z ) = R′(0){ I − A( z) − δ QA( z)},
(7)
решение R(z) которого, удовлетворяющее краевому
условию R (0)=0, имеет вид
z
R (z ) = ∫ R ′(0){I − A( x) − δ QA( x)}dx.
(8)
0
Так как существует маргинальное распределе
ние R=R(∞) случайного процесса l(t), то в (7) при
z=∞ выполняется равенство
R ′(0)Q = 0,
(9)
а (7) можно переписать в виде
R ′(z ) = R′(0){I − A( z )}.
(10)
В (9) матрица Q, в силу равенства (1), обладает
всеми свойствами матрицы инфинитезимальных
характеристик некоторой эргодической цепи Мар
кова с непрерывным временем, поэтому решение
R'(0) уравнения (9) имеет вид
R ′(0) = Cr,
(11)
где r – стационарное распределение вероятностей
значений цепи Маркова, определяемой матрицей
Q, то есть распределение r является решением си
стемы линейных алгебраических уравнений
rQ=0, rE=1,
(12)
где E – единичный вектор столбец.
Значение произвольной постоянной С в (11)
найдем из следующего условия нормировки
1 = RE = R (∞)E =
∞
= ∫ R ′(0) {I − A( x) − δ QA( x)}dxE =
0
∞
= C ∫ r {I − A( x) − δ QA( x)}dxE =
0
∞
= Cr ∫ {I − A ( x )}dxE = CraE,
(13)
0
где a – диагональная матрица математических
ожиданий, определяемых функциями распределе
Управление, вычислительная техника и информатика
ния Al(x), которые являются диагональными
элементами матрицы А(х).
Из (13) следует, что выполняется равенство
1
1
,
C=
= L
(14)
raE
∑ rl al
l =1
где rl – элементы вектора r.
Подставляя (11) в (8), для R (z) получим равен
ство
z
R ( z ) = ∫ R ′(0) {I − A ( x) − δ QA ( x)}dx =
0
z
= C ∫ r{I − A ( x)}dx,
(15)
0
в котором вектор r является решением системы
(12), а постоянная С определяется равенством (14).
В частности, из (15) при z→∞ следует равенство
∂R(l ,0)
R(l ) = R (l , ∞) =
al ,
(16)
∂z
которое, обозначив λl =
1
, запишем в виде
al
∂R (l , 0)
= λl R (l ).
(17)
∂z
Таким образом, векторная характеристическая
функция H(z,u,t), в силу равенств (4) и (6), являет
ся решением задачи Коши
⎧ 1 ∂H ( z , u , t )
=
⎪N
∂t
⎪
∂H ( z, u, t ) ∂H(0, u, t )
⎪
=
+
×
⎨
∂z
∂z
⎪
ju
ju
⎪ × (e A( z ) − I + δ e QA ( z )),
⎪H( z, u,0) = R( z),
(18)
⎩
где векторная функция R(z) определяется равен
ством (15).
Отметим, что функция R(z), определяющая на
чальное условие в задаче (18), не зависит от значе
ния параметра δ, но решение H(z,u,t) задачи (18)
зависит от значений этого параметра, поэтому это
решение будем обозначать H(z,u,t,δ), а задачу (18)
перепишем в виде
⎧ 1 ∂H ( z , u , t , δ )
=
⎪N
∂t
⎪
∂H ( z , u , t , δ ) ∂H(0, u, t, δ )
⎪
=
+
×
⎨
∂z
∂z
⎪
× (e ju A( z ) − I + δ e ju QA ( z )),
⎪
⎪H ( z, u,0, δ ) = R( z).
(19)
⎩
Решение этой задачи выполним применением
методов асимптотического анализа в условии пре
дельно редких изменений состояний (δ→0) [2]
и неограниченно возрастающей интенсивности
(N→∞) [3].
Метод асимптотического анализа
в условии предельно редких изменений состояний
Обозначив
lim H ( z, u, t , δ ) = H( z, u, t ),
δ →0
в (19) выполним указанный предельный переход, тогда
для векторной функции H(z,u,t) получим задачу Коши
⎧ 1 ∂H ( z, u, t ) ∂ H( z, u, t ) ∂ H(0, u, t) ju
(e A ( z ) − I ),
=
+
⎪
∂t
∂z
∂z
⎨N
⎪⎩ H ( z, u,0) = R( z),
для системы L дифференциальных уравнений, ко
торая в силу диагональности матриц А(х) и I распа
дается на L независимых задач Коши.
⎧ 1 ∂H (l , z , u , t )
=
⎪N
∂t
⎪
∂H (l , z , u , t ) ∂H (l , 0, u, t )
⎪
=
+
×
⎨
∂z
∂z
⎪
× (e ju Al ( z ) − 1),
⎪
⎪ H (l , z , u , 0) = R(l , z ),
(20)
⎩
для элементов H(l,z,u,t) векторной функции H(z,u,t).
Маргинальное распределение вероятностей чи
сла событий, наступивших за время t в рассматри
ваемом потоке, определяется характеристической
функцией.
∞
h(u , t ) = Me jun (t ) = ∑ eiun P{n (t ) = n},
n=0
которую, при достаточно малых значений параме
тра δ, можно аппроксимировать решением
H(l,z,u,t) задачи (20)
L
h(u , t ) = ∑ H (l , ∞ , u , t ).
(21)
l =1
Решение задачи (20) найдем, применяя метод асим
птотического анализа в условии неограниченно расту
щей интенсивности в предельном условии N→∞.
Метод асимптотического анализа в условии
неограниченно растущей интенсивности
В задаче (20) выполним замену
H (l , z , u, t ) = H 2 (l , z , u, t ) exp{ ju λl Nt},
(22)
где, как указано выше,
λl =
1
=1
al
∞
∫ (1 − A ( z))dz.
l
0
Тогда для функции H2(l,z,u,t) получим задачу
⎧ 1 ∂ H 2 (l , z , u , t )
+ H 2 (l , z , u , t ) ju λl =
⎪N
∂t
⎪
∂H 2 (l , z , u , t ) ∂H 2 (l , 0, u, t )
⎪
=
+
×
⎨
∂z
∂z
⎪
× (e ju Al ( z ) − 1),
⎪
⎪
⎩ H (l , z , u , 0) = R(l , z ).
(23)
В полученной задаче (23), обозначив ε2=1/N,
выполним замены
21
Известия Томского политехнического университета. 2012. Т. 321. № 5
u = ε w, H 2 (l , z , u, t ) = F (l , z, w, t , ε ),
для F(l,z,w,t,ε) запишем задачу
⎧ 2 ∂F (l , z , w, t , ε )
+ F (l , z , w, t , ε ) jε wλl =
⎪ε
∂t
⎪
∂F (l , z , w, t , ε ) ∂F (l , 0, w, t , ε )
⎪
=
+
×
⎨
∂z
∂z
⎪
× (e jε w Al ( z ) − 1),
⎪
⎪ F (l , z , w, 0, ε ) = R(l , z ).
⎩
(24)
(25)
Можно доказать следующее утверждение.
Теорема. Предельное при ε→0 значение F(l,z,w,t)
решения F(l,z,w,t,ε) задачи (25) имеет вид произведения
F (l , z , w, t ) = Φ(l , w, t ) R (l , z ),
(26)
в котором функция Ф(l,w,t) имеет вид
⎧ ( jw) 2
⎫
(27)
( λl + κ l ) t ⎬ ,
Φ(l , w, t ) = exp ⎨
⎩ 2
⎭
κ l = λl3 (σ l2 − al2 ).
(28)
Здесь λl – величина, обратная к среднему al; σl2 –
дисперсия, определяемая функцией распределения Al(z).
Доказательство. Доказательство этой теоремы
выполним в три этапа.
Этап 1. Обозначив
lim F (l , z , w, t , ε ) = F (l , z , w, t ),
где
ε →0
в задаче (25) выполним указанный предельный пе
реход, для функции F(l,z,w,t) получим задачу
⎧ ∂F (l , z , w, t ) ∂F (l , 0, w, t )
( Al ( z ) − 1) = 0,
+
⎪
∂z
∂z
⎨
⎪⎩ F (l , z , w, 0) = R(l , z ),
(29)
совпадающую с ее матричной формой (10), поэто
му решение F(l,z,w,t) задачи (29) имеет вид произ
ведения (26), а функция Ф(l,w,t) удовлетворяет на
чальному условию
Ф(l,w,0) =1.
Этап 2. Уравнение задачи (25) перепишем в виде
∂F (l , z , w, t , ε )
O (ε 2 ) + F (l , z , w, t , ε ) jε wλl =
+
∂z
∂F (l , 0, w, t , ε )
+
( Al ( z ) − 1 + jε wAl ( z )),
(30)
∂z
а его решение F(l,z,w,t,ε) запишем в виде разложения
F (l , z , w, t , ε ) =
= Φ(l , w, t ){R(l , z) + jε wf (l , z)} + O( ε 2),
(31)
подставляя которое в (30), получим равенство
∂R (l , z )
∂f (l , z )
O (ε 2 ) + R(l , z ) jε wλl =
+ jε w
+
∂z
∂z
∂f (l ,0) ⎫
⎧ ∂R (l ,0)
+⎨
+ jε w
⎬ ( Al ( z ) − 1 + jε wAl ( z )) =
∂z ⎭
⎩ ∂z
∂R (l , z )
∂f (l , z ) ∂R (l ,0)
=
+ jε w
+
( Al ( z ) − 1) +
∂z
∂z
∂z
∂f (l ,0)
∂R(l ,0)
+ jε w
( Al ( z ) − 1) + jε w
Al ( z ),
∂z
∂z
22
которое, в силу равенств (10) и (17) можно перепи
сать в виде
∂f (l , z ) ∂f (l , 0)
+
( Al ( z ) − 1) = λl R (l , z ) −
∂z
∂z
∂R (l , 0)
−
Al ( z ) = λl ( R (l , z ) − R (l ) Al ( z )).
∂z
Интегрируя это равенство по z в интервале
[0,∞), получим выражение
∞
∂f (l ,0)
f (l , ∞ ) −
al = λl ∫ ( R(l , z ) − R(l ) Al ( z ))dz ,
∂z
0
которое перепишем в виде
∞
∂f (l ,0)
= λl 2 ∫ ( R(l, z) − R(l ) Al ( z ))dz.
λl f (l , ∞) −
∂z
0
Применяя (15)–(17), нетрудно показать, что
выполняется равенство
∂f (l , 0)
1
= λl 3 R(l ) ( al 2 − σl 2 ),
λl f (l , ∞) −
(32)
∂z
2
где al и σl2 – среднее и дисперсия, определяемые
функцией распределения Al(z).
Этап 3. Обозначив
lim F (l , z , w, t , ε ) = F (l , w, t , ε ),
z →∞
в уравнении задачи (25) выполним указанный предель
ный переход, для функции F(l,w,t,ε) получим равенство
∂F (l , w, t , ε )
ε2
+ F (l , w, t , ε ) jε wλl =
∂t
∂F (l , 0, w, t , ε ) jε w
=
(e − 1),
∂z
в которое подставим разложение (31), запишем
∂Φ(l , w, t )
R(l ) + Φ(l , w, t ) ×
ε2
∂t
×{R(l ) + jε wf (l , ∞)} jε wλl =
∂f (l,0) ⎫
⎧ ∂R(l ,0)
= Φ(l , w, t ) ⎨
+ jε w
⎬×
∂z ⎭
⎩ ∂z
⎛
( jε w) 2 ⎞
3
× ⎜ jε w +
⎟ + O (ε ) = Φ(l , w, t ) ×
2 ⎠
⎝
∂R(l ,0)
⎧
⎫
jε w
+
⎪⎪
∂z
⎪⎪
3
×⎨
⎬ + O(ε ).
2
∂
f
(
l
,0)
(
j
ε
w
)
∂
R
(
l
,0)
⎪ +( jε w) 2
⎪
+
⎪⎩
∂z
2
∂z ⎪⎭
В силу (17) это равенство перепишем в виде
∂Φ(l , w, t )
( jw) 2
R (l ) =
Φ(l , w, t ) ×
∂t
2
⎧
∂f (l , 0) ⎞ ⎫
⎛
× ⎨λl R (l ) − 2 ⎜ λl f (l , ∞) −
⎟⎬.
∂z ⎠ ⎭
⎝
⎩
Применяя здесь равенства (17) и (32), получим
уравнение
∂Φ(l , w, t ) ( jw) 2
=
Φ(l , w, t ){λl + λl3 (σ l2 − al2 )},
∂t
2
относительно функции Ф(l,w,t).
Управление, вычислительная техника и информатика
Решение Ф(l,w,t) этого уравнения, удовлетво
ряющее начальному условию Ф(l,w,0)=1, в силу
обозначения (28), можно записать в виде
⎧ ( jw) 2
⎫
Φ(l , w, t ) = exp ⎨
( λl + κ l ) t ⎬ ,
⎩ 2
⎭
совпадающем с (27). Теорема доказана.
Многомодальность распределения вероятностей
числа событий, наступивших за единицу времени
высокоинтенсивного полумарковского потока
в условии предельно редких изменений
его состояний
Применяя в (27) замену
u
w= =u N
ε
из (24), также равенство (26)
H 2 (l , z , u , t ) = F (l , z , w, t ) =
⎧ ( ju ) 2
⎫
( λl + κ l ) Nt ⎬
= R (l , z )exp ⎨
⎩ 2
⎭
и замену (22), можно записать асимптотическое ра
венство
H 2 (l , z , u , t ) =
⎧
⎫
( ju ) 2
(λl + κl ) Nt ⎬ .
= R (l , z ) exp ⎨ ju λl Nt +
2
⎩
⎭
Для маргинальной характеристической функ
ции h(u,t) из (21) получим аппроксимацию
L
⎧
⎫
( ju ) 2
h(u , t ) = ∑ R(l ) exp ⎨ ju λl Nt +
( λl + κl ) Nt ⎬ (33)
2
l =1
⎩
⎭
распределения вероятностей числа событий, на
ступивших за временя t в высокоинтенсивном по
СПИСОК ЛИТЕРАТУРЫ
1. Королюк В.С. Стохастические модели систем. – Киев: Науко
ва думка, 1989. – 203 с.
2. Горбатенко А.Е. Исследование систем массового обслужива
ния с коррелированными потоками в специальных предель
ных условиях: дис. … канд. физ.мат. наук. – Томск, 2010. –
156 с.
3. Лопухова С.В. Асимптотические и численные методы исследо
вания специальных потоков однородных событий: дис. … канд.
физ.мат. наук. – Томск, 2008. – 167 с.
лумарковском потоке в условии предельно редких
изменений его состояний в виде смеси с весами
R(l) гауссовских распределений с параметрами λlNt
и (λl+κl)Nt. Здесь κl определяется равенством (28) и
распределение вероятностей R(l), как следует из
(15), имеет вид
R (l ) = Crl al = rl al
L
∑ra ,
l l
l =1
⎯
где rl, l=1,L является решением системы (12).
Отметим, что распределение вероятностей,
определяемое равенством (33), при соответ
ствующих значениях параметров является мно
гомодальным с количеством локальных макси
мумов не более L. А его локальные параметры
среднего и дисперсии линейно зависят от вре
мени t наблюдения за рассматриваемым пото
ком.
Заключение
В работе выполнено исследование высокоин
тенсивного полумарковского потока в условии
предельно редких изменений его состояний. Пока
зано, что распределение вероятностей числа его со
бытий, наступивших за время t является взвешен
ной, с весами R(l), суммой гауссовских распределе
ний с параметрами λlNt и (λl+κl)Nt, которые ли
нейно зависимы от времени t наблюдения за пото
ком, что позволяет такой поток рассматривать
в качестве математической модели телекоммуни
кационных потоков с многомодальными гисто
граммами числа событий.
Можно показать, что аналогичные результаты
имеют место и для других специальных [4], корре
лированных [5] потоков, таких как ММРР, МАР,
а так же их неординарных аналогов.
4. Гнеденко Б.В. Коваленко И.Н. Введение в теорию массового
обслуживания. 4е изд. – М.: Издво ЛКИ, 2007. – 400 с.
5. Дудин А.Н., Клименок В.И. Системы массового обслуживания
с коррелированными потоками. – Минск: БГУ, 2000. – 175 с.
Поступила 17.09.2012 г.
23
1/--страниц
Пожаловаться на содержимое документа