close

Вход

Забыли?

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

?

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

код для вставкиСкачать
Вычислительные технологии
Том 13, Специальный выпуск 5, 2008
Исследование математической модели
сети случайного доступа
с рекуррентным входящим потоком
Б. Е. Сейсенбеков
LEADER PRO GROUP Ltd, Prague, Czehia
e-mail: bolat_sbk.ru
А. Н. Туенбаева
Евразийский национальный университет им. Л.Н. умилева, Астана, Казахстан
e-mail: tuenbaeva_aiyamail.ru
A modified method is applied for an asymptotic analysis of Markovian systems
aimed at investigation of a mathematical model for a casual access network. It results
in a differential equation determining the asymptotic average meaning for a number
of messages on a source of repeated calls. The formulas determining the probability
distribution of service states are given.
Исследуем математическую модель сети случайного доступа [1?. В [2? рассмотрена
математическая модель пакетной радиосети, используемой в системе видеонаблюдения
для передачи цировых данных, с потерей искаженных видеосигналов с рекуррентным
входящим потоком. Анализ математической модели сети передачи данных по радиоканалу позволил определить предельные возможности рассматриваемого протокола доступа и получить аналитические выражения, определяющие зависимости для основных
количественных характеристик качества ункционирования обслуживающей системы,
т. е. выразить их через величины, характеризующие входящий поток и обслуживающую
систему.
Основным отличием рассматриваемой в данной статье модели от исследованной
ранее в [2? является то, что заявки, попавшие в конликт, не теряются, а переходят
в источник повторных вызовов (ИПВ). Итак, построим математическую модель сети
случайного доступа в виде системы массового обслуживания (СМО) с оповещением о
конликте, на вход которой поступает рекуррентный поток заявок с ункцией распределения A(z). Заявка, заставшая прибор свободным, немедленно начинает обслуживаться. Продолжительность обслуживания случайная, имеет экспоненциальное распределение с параметром µ1 . Если прибор занят, то обслуживаемая и обратившаяся к
прибору заявки вступают в конликт и переходят в ИПВ. От момента возникновения
конликта на приборе реализуется этап оповещения о конликте, продолжительность
которого имеет экспоненциальное распределение с параметром µ2 . После завершения
этапа оповещения о конликте прибор вновь становится свободным. Все заявки в ИПВ
осуществляют случайную задержку, после которой повторно обращаются к обслуживающему прибору. Время пребывания в ИПВ заявок имеет экспоненциальное распреде
Институт вычислительных технологий Сибирского отделения оссийской академии наук, 2008.
106
Исследование математической модели сети случайного доступа. . .
107
ление с параметром ? . Определим состояние СМО вектором (k(t), i(t), z(t)), где k(t) состояние прибора:
?
?
? 0, прибор свободен,
k(t) = 1, прибор занят,
?
?
2, прибор в состоянии конликта;
i(t) число заявок в ИПВ; z(t) длина интервала от момента t до момента прихода
следующего требования во внешнем входящем потоке.
Очевидно, процесс (k(t), i(t), z(t)) изменения состояний СМО во времени является
марковским. аспределение вероятностей
Pk (i, z, t) = P (k(t) = k, i(t) = i, z(t) < z)
удовлетворяет следующей системе [3?:
?P0 (i, z, t)
?P0 (i, z, t) ?P0 (i, 0, t)
=
?
? i?P0 (i, z, t) + µ1 P1 (i, z, t) + µ2 P2 (i, z, t),
?t
?z
?z
?P1 (i, z, t)
?P1 (i, z, t) ?P1 (i, 0, t)
?P0 (i, 0, t)
=
?
? (µ1 + i?)P1 (i, z, t) + A(z)
+
?t
?z
?z
?z
+(i + 1)?P0 (i + 1, z, t),
?P2 (i, z, t)
?P2 (i, z, t) ?P2 (i, 0, t)
?P2 (i ? 1, 0, t)
=
?
? µ2 P2 (i, z, t) + A(z)
+
?t
?z
?z
?z
?P1 (i ? 2, 0, t)
+A(z)
+ (i ? 1)?P1 (i ? 1)?P (i ? 1, z, t).
?z
(1)
ешение Pk (i, z, t) системы (1) достаточно полно определяет ункционирование математической модели сети случайного доступа, однако точных аналитических методов
решения такой системы не существует. Поэтому для исследования полученной системы предложен модиицированный метод асимптотического анализа марковизируемых
систем [4?.
В новых обозначениях
? = ?,
t? = ?,
i? = x,
1
Pk (i, z, t) = ?k (x, z, ?, ?)
?
система (1) примет вид
??0 (x, z, ?, ?)
??0 (x, z, ?, ?) ??0 (x, 0, ?, ?)
=
?
? x?0 (x, z, ?, ?) + µ1 ?1 (x, z, ?, ?)+
??
?z
?z
+µ2 ?2 (x, z, ?, ?),
?
??1 (x, z, ?, ?)
??1 (x, z, ?, ?) ??1 (x, 0, ?, ?)
=
?
? (µ1 + x)?1 (x, z, ?, ?)+
??
?z
?z
??0 (x, 0, ?, ?)
+A(z)
+ (x + ?)?0 (x + ?, z, ?, ?),
?z
??2 (x, z, ?, ?)
??2 (x, z, ?, ?) ??2 (x, 0, ?, ?)
?
=
?
? µ2 ?2 (x, z, ?, ?)+
??
?z
?z
??1 (x ? 2?, 0, ?, ?)
+A(z) ??2 (x??,0,?,?)
+ A(z)
+ (x ? ?)?1 (x ? ?, z, ?, ?).
?z
?z
?
(2)
108
Б. Е. Сейсенбеков, А. Н. Туенбаева
В системе (2) перейдем к пределу при ? ? 0, полагая
lim ?k (x, z, ?, ?) = ?k (x, z, ? ),
k = 0, 2.
??0
В результате получим систему линейных алгебраических уравнений
??0 (x, z, ? ) ??0 (x, 0, ? )
?
? x?0 (x, z, ? ) + µ1 ?1 (x, z, ? ) + µ2 ?2 (x, z, ? ) = 0,
?z
?z
??1 (x, z, ? ) ??1 (x, 0, ? )
??0 (x, 0, ? )
?
? (x + µ1 )?1 (x, z, ? ) + x?0 (x, z, ? ) + A(z)
= 0,
?z
?z
?z
??2 (x, z, ? ) ??2 (x, 0, ? )
?
? µ2 ?2 (x, z, ? ) + x?1 (x, z, ? )+
?z
?z
??1 (x, 0, ? ) ??2 (x, 0, ? )
+
= 0.
+A(z)
?z
?z
ешение ?k (x, z, ? ) этой системы будем искать в виде
?k (x, z, ? ) = Rk (z)?(x, ? ),
k = 0, 2.
(3)
Функция ?k (x, z, ? ) имеет смысл асимптотической плотности распределения величины
нормированного числа i? заявок в ИПВ, а Rk (z) распределения вероятностей состояний прибора. Для ункций Rk (z) имеет место система уравнений
R0? (z) ? R0? (0) ? xR0 (z) + µ1 R1 (z) + µ2 R2 (z) = 0,
R1? (z) ? R1? (0) ? (x + µ1 )R1 (z) + xR0 (z) + A(z)R0? (0) = 0,
R2? (z) ? R2? (0) ? µ2 R2 (z) + xR1 (z) + A(z) {R1? (0) + R2? (0)} = 0.
Обозначив
(4)
R(z) = R0 (z) + R1 (z) + R2 (z),
R? (0) = R0? (0) + R1? (0) + R2? (0),
в системе (4) просуммировав все уравнения, получим
R? (z) ? R? (0) + {R0? (0) + R1? (0) + R2? (0)} A(z) = 0.
Откуда
?
R(z) = R (0)
Zz
(1 ? A(y))dy.
(5)
0
При z ? ? обозначим
lim Rk (z) = Rk .
z??
Учитывая условие нормировки
2
P
(6)
Rk = 1, из (5) получаем
k=0
1
R(z) =
a
Zz
(1 ? A(y))dy.
(7)
0
Z?
Здесь a = (1 ? A(y))dy среднее значение длины интервала между моментами на0
ступления событий входящего рекуррентного потока. Не нарушая общности, можно
Исследование математической модели сети случайного доступа. . .
109
положить a = 1. Используя (7), одно из уравнений системы (4) можно исключить и
переписать систему в виде
R1? (z) = (2x + µ1 )R1 (z) + xR2 (z) + f1 (z),
R2? (z) = ?xR1 (z) + µ2 R2 (z) + f2 (z),
(8)
f1 (z) = R1? (0) + {R1? (0) + R2? (0) ? 1} A(z) ? xR(z),
f2 (z) = R2? (0) ? {R1? (0) + R2? (0)} A(z).
(9)
где
Выразим решение R1 (z), R2 (z) системы (8) через R1? (0), R2? (0). Для этого запишем
характеристическое уравнение для однородной системы в виде
?2 ? (2x + µ1 + µ2 )? + x2 + 2xµ2 + µ1 µ2 = 0.
Дискриминант уравнения имеет вид
?
? > 0, µ1 > µ2 , µ1 + 4x < µ2 ,
2
2
= 0, µ1 = µ2 , µ1 + 4x = µ2 ,
(2x + µ1 + µ2 ) ? 4(2x + µ1 )µ2 ? 4x =
?
< 0, µ1 < µ2 < µ1 + 4x.
Пусть характеристические числа ?1 6= ?2 , тогда ункции R1 (z) и R2 (z) определяются
как
(1)
(2)
R1 (z) = C1 (z)V1 e?1 z + C2 (z)V1 e?2 z ,
(10)
(1)
(2)
R2 (z) = C1 (z)V2 e?1 z + C2 (z)V2 e?2 z .
(k)
(k)
Здесь величины V1 и V2
раических уравнений
являются решениями однородных систем линейных алгеб(k)
(k)
(2x + µ1 ? ?k )V1 + xV2 = 0,
(k)
(k)
?xV1 + (µ2 ? ?k )V2 = 0,
следовательно, можно полагать
(k)
V1
= µ2 ? ?k ,
(k)
V2
= x.
Функции C1 (z) и C2 (z) определяются системой
(1)
(2)
C1? (z)V1 e?1 z + C2? (z)V1 e?2 z = f1 (z),
(1)
(2)
C1? (z)V2 e?1 z + C2? (z)V2 e?2 z = f2 (z).
Отсюда
Zz
µ2 ? ?2
e
f1 (y) ?
f2 (y) dy,
x
0
Zz
1
µ2 ? ?1
??2 y
C2 (z) =
e
f2 (y) ? f1 (y) dy,
?2 ? ?1
x
1
C1 (z) =
?2 ? ?1
0
??1 y
(11)
110
Б. Е. Сейсенбеков, А. Н. Туенбаева
поэтому из (10) и (11) получаем
Zz
µ2 ? ?1 ?1 z
µ2 ? ?2
??1 y
R1 (z) =
e
e
f1 (y) ?
f2 (y) dy+
?2 ? ?1
x
0
Zz
µ2 ? ?2 ?2 z
µ2 ? ?1
??2 y
+
e
e
f2 (y) ? f1 (y) dy,
?2 ? ?1
x
0
Zz
µ2 ? ?2
x
?1 z
??1 y
e
e
f1 (y) ?
f2 (y) dy+
R2 (z) =
?2 ? ?1
x
0
Zz
x
µ2 ? ?1
?2 z
??2 y
+
e
e
f2 (y) ? f1 (y) dy.
?2 ? ?1
x
(12)
0
Так как существуют пределы (6) и характеристические числа ?k > 0, выполняются
следующие равенства:
Z?
µ2 ? ?2
f2 (y) dy = 0,
e
f1 (y) ?
x
0
Z?
µ2 ? ?1
??2 y
e
f2 (y) ? f1 (y) dy = 0,
x
??1 y
0
которые в силу (9) запишем в виде
{x?1 + x?12 a(?1 ) + (µ2 ? ?2 )?12 a(?1 )} R1? (0)+
+ {x?12 a(?1 ) + (µ2 ? ?2 )?1 (?1 a(?1 ) ? 1)} R2? (0) = x2 (1 ? ?1 )a(?1 ),
{x?2 + x?22 a(?2 ) + (µ2 ? ?1 )?22 a(?2 )} R1? (0)+
+ {x?22 a(?2 ) + (µ2 ? ?1 )?2 (?2 a(?2 ) ? 1)} R2? (0) = x2 (1 ? ?2 )a(?2 ),
где a(?) =
Z?
(13)
e??y A(y)dy .
0
Полученная неоднородная система (13) линейных алгебраических уравнений однозначно определяет зависимость величин R1? (0) и R2? (0) от x. Выполнив предельный переход z ? ? в равенствах (12), запишем
µ2 {R2? (0) ? (1 + x)R1? (0) ? 2} ? x
,
x2 + 2xµ2 + µ1 µ2
(1 + x)x ? 2xR1? (0) + (µ1 + x)R2? (0)
.
R2 =
x2 + 2xµ2 + µ1 µ2
R1 =
(14)
Суммируя уравнения системы (2) и полагая z ? ?, получим
??(x, ?, ?)
?
??1 (x, 0, ?, ?) ??2 (x, 0, ?, ?)
?
= ??
x?1 (x, ?, ?) ? x?0 (x, ?, ?) + 2
+
+ o(?),
??
?x
?z
?z
где ?(x, ?, ?) = ?0 (x, ?, ?) + ?1 (x, ?, ?) + ?2 (x, ?, ?).
Исследование математической модели сети случайного доступа. . .
111
Поделив это равенство на ? и учитывая, что при ? ? 0 ?k (x, ?, ?) ? ?k (x, ? ), получаем уравнение в частных производных, совпадающее с вырожденным уравнением
Фоккера Планка, относительно ?(x, ? ):
?
??1 (x, 0, ? ) ??2 (x, 0, ? )
??(x, ? )
=?
x?1 (x, ? ) ? x?0 (x, ? ) + 2
+
??
?x
?z
?z
или, учитывая (3),
??(x, ? )
?
=?
{?(x, ? ) [x(R1 ? R0 ) + 2R1? (0) + R2? (0)]} .
??
?x
Отсюда
x? (? ) = x{2R1 + R2 } + 2R1? (0) + R2? (0) ? x,
где R1 и R2 определены в (14), а R1? (0) и R2? (0) в (13).
Таким образом, имеем обыкновенное диеренциальное уравнение относительно
ункции x = x(? ).
В результате исследования получено диеренциальное уравнение, определяющее
асимптотическое среднее значение числа заявок в источнике повторных вызовов, приведены ормулы, определяющие распределение вероятностей состояний прибора. Знание
распределения вероятностей обеспечивает наиболее полное, в вероятностном смысле,
описание ункционирования модели, тем самым знание распределения состояний исследуемой сети дает возможность прогнозировать и контролировать случайные процессы, протекающие в сетях.
Список литературы
[1?
Туенбаева А.Н.
[2?
Назаров А.А., Туенбаева А.Н.
[3?
Назаров А.А., Терпугов А.Ф.
[4?
105 с.
Компьютерные сети случайного доступа. Астана: Изд-во ЕНУ, 2006.
Исследование математической модели системы видеонаблюдения с потерей искаженных видеосигналов при рекуррентном входящем потоке //
Вест. Том. гос. ун-та. 2006. ќ 19. С. 156157.
Изд-во НТЛ, 2005. 228 .
Теория массового обслуживания: Учеб. пособие. Томск:
Метод асимптотического анализа в теории массового
обслуживания. Томск: Изд-во НТЛ, 2006. 112 с.
Назаров А.А., Моисеева С.П.
Поступила в редакцию 28 марта 2008 г.
Документ
Категория
Без категории
Просмотров
4
Размер файла
164 Кб
Теги
потоков, доступа, случайное, математические, сети, входящим, исследование, модель, рекуррентный
1/--страниц
Пожаловаться на содержимое документа