Организация интерактивной системы вероятностного моделирования стохастических систем

Оренбургский государственный университет

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

Для расчета характеристик систем массового обслуживания (СМО) в предположении, что времена между заявками во входном потоке и обслуживания распределены по произвольному закону, не существует точных методов. Использование же традиционных методов, основанных на пуассоновских входных потоках и экспоненциальности времени обслуживания не всегда оправдано. Существующие аппроксимационные методы, использующие два первых момента распределений входного потока и времени обслуживания имеют большую погрешность в случае отклонения коэффициентов вариаций этих распределений от единицы.

Для расчета характеристик сетевых моделей систем сеть декомпозируется на отдельные узлы (рис.1).

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

Для определения среднего значения и дисперсии распределения времени между соседними заявками на входе и выходе каждого узла сети необходимо выразить среднее и дисперсию времени в выходном потоке отдельного узла через параметры входного потока и времени обслуживания. Для решения этой задачи выведены точные формулы: τ _вых = τ_µ + p ₀′ τ_λ ′ ,        (1)

где T_ , T.. , D , Du - соответственно сред- ВЫХ ’ H ’ вых’ ^г                             .г

ние и дисперсии времени между заявками выходного потока и времени обслуживания, т_х , D ‘ - среднее и дисперсия остаточного

времени (времени простоя узла), а p ₀ - вероятность того, что обслуженная заявка оставляет узел пустым. Для системы без потерь средние времена между заявками в выходном и входном потоках совпадают. Уравнения (2) решаются совместно со следующими уравнениями преобразования дисперсии времени между заявками:

D = ( л ₁ / X ) 3 D + ( л / X ) 3 D 2

- для суммы двух независимых потоков с интенсивностями X j , X 2 и дисперсиями D 1 , D 2 (узел композиции потоков) и

p

V

p J

-для потока с интенсивностью X и дисперсией времени между заявками D , в котором заявки с вероятностью p уходят из потока (узел декомпозиции потоков). Из уравнений (2)-(4) следуют основные уравнения декомпозиции сети, так называемые уравнения баланса для средних и дисперсий времени между заявками на входе и выходе i-го узла сети (i=1,…,n)

X.

i

oi    j=1 Ji J ,

D = вх . i

T0 i

i

n

( PiiX i 1

' ••ZL • ji j

i

D 0 i

-

j

pji

D выхj

pji

A

p _Ji ² _J

где т ₀ i и D о i - среднее и дисперсия времени

между заявками в потоке, идущем от внешнего источника на вход i-го узла, X i -интенсивность потока на входе и выходе i - го узла, D _вхi , D _выхi - дисперсии времени между заявками во входном и выходном потоках i - го узла, p j_i - вероятность передачи заявки от j-го узла к i-му, а n - количество узлов в сети. Для решения системы (6) совместно с (5) и (2) предложена итерационная процедура, где в каче стве первого приближения в уравнении (2) используется замена p 0 = p о , т ^= T x , d x = D X • ^Здесь p ₀ = 1 - р - вероятность простоя узла, т _X и D X - среднее и дисперсия времени между заявками во входном потоке. Это приближение в случае экспоненциальной сети не вносит погрешности, а уравнения (6) становятся линейными относительно искомых дисперсий. На последующих этапах значения дисперсий входных и выходных потоков уточняются с использованием уравнений (2) и (6), одновременно вычисляются основные характеристики отдельных узлов и всей сети в целом.

При приближенном расчете замкнутых сетевых моделей систем в выражениях (5) и (б) первые слагаемые исчезают. В этом случае в итерационной процедуре значения интенсивностей X i подбираются так, чтобы с заданной точностью е выполнялось условие n

Е N i = N , где через N i обозначено сред- i = 1

нее количество заявок в i-м узле, а N - количество заявок, постоянно циркулирующих в замкнутой сети.

Для определения параметров p 0 , Т ‘ , D ‘ , входящих в формулы (I) и (2), а также основных характеристик узла, процесс его функционирования на периоде занятости аппроксимируется двумерным диффузионным процессом (x₁, x₂). Процесс x₁(t) аппроксимирует число заявок N₁(t), поступивших в

узел к моменту времени t, а x₂(t) - число заявок N₂(t), покинувших узел к тому же времени. Текущее значение N числа заявок в узле определяется разностью N = [ X i ] — [ x 2 ] , где [ x ] - целая часть от x (рис.2а, траектория 1).

Потребуем, чтобы компоненты двумерного процесса (x1, x2) в моменты времени первого прохождения целочисленного уровня (моменты поступления и ухода заявок) имели средние значения и дисперсии, совпадающие со средними и дисперсиями компонент дискретного процесса (N1, N2). Тогда коэффициенты сноса ai = Ti"* и диффузии в. = Dt. процесса xi можно выразить через средние значения Ti и дисперсии Di интервалов времени между скачками дискретного процесса Ni(i=1,2). В области D, определенной условием N > 0 и приведенной на рисунке 2а, плотность распределения to(t, x1, x2) векторного диффузионного процесса удовлетворяет уравнению Колмогорова

— = s

д t    i=1

( b

I

V

д to дx.

i

a

i

дю "

д x.

. 7

Так как период занятости начинается с

уровня x₁=1, то начальным условием для (7) будет ю ( о, x 1 , x ₂ ) = 5 ( x 1 -1 ) 5 ( x 2 ) . Рассматри-

вая функционирование узла на периоде занятости, добавим к уравнению (7) граничное

условие поглощения ю _Г 1 = 0. Граница Г 1 ,

определенная условием [ N ] = 0, имеет ступенчатый характер, а попадание ординаты процесса на границу физически означает завершение периода занятости. Вследствие сложного характера границы, решение уравнения (7) будем искать в виде совокупности решений в подобластях D_к = ( x 1 <  к +1, x ₂<  к ), ( к = 1,2,... ) и “сши-вая” их на границах x 1 = к , ( к = 2,3,... ) . Введем обозначения Т к ( у 1 ) для распределения

ординаты процесса x1 в момент достижения

Рис.2. Аппроксимация СМО GI/G/1/m с потерями, а также с переменными параметрами двумерным диффузионным процессом (x₁, x₂) (а) и выделенная область Dⁱ_k (б) (индекс k определяет уровень по оси x₁, а i - по x₂). Траектория 1 - для СМО GI / G /1/ ^ при m ^ ^ , траектория 2 - для СМО с потерями, траектория 3 ě для СМО с переменными параметрами

уровня х₂=к (границы Г) и ф к ( у 2 ) для распределения ординаты процесса х₂ в момент прохождения процессом (х₁, х₂) уровня х₁=к+1 (границы области D _k ). Эти распределения позволяют определить все основные характеристики функционирования отдельного узла. Указанные распределения можно представить через решение уравнения (7), т.е. плотность распределения to k ( t , X i , x 2 ) . Для этого в статье с использованием аппарата теории функций Грина Q ( t , x , x | k , у' ) k 12   2

получены рекуррентные формулы:

∞

V, ⁽ У ) = J ф k 1     0

k

⁽ У' ) Q ⁽ У. , У' ) ^dУ',

- 12 V 1

( V ( у ) = Q ( у I 0)) ,       (10)

11 V 1

q ( у \у;) =

V 1    ²

1 + У

π bb

\ 1 2

a

■ е ^х Р ^[—^{(1 -} У ₁)

b ¹

a

+ ²

b

(1 + У ₂)] X

X [

: — K (2 в Т7) - — K (2 /в ■ Y )]; ^в 3 ^{1     3} Г 4 ^{1     4}

to ( t , x , x ) = k 1 2

^в 3

∞

J ф,      ⁽ У' ) Q , ⁽ t , ^x , ^x | ^k , У' ) dy' , (8)

0 k -12 k 1 2     2    2 ^v ’

(1 - У ₁) ²

2 b

(1 + У ) ²

2 b

Ф, ⁽ У

k

∞

) = J ф

2    0 k

-

( y' ) Q 2

ϕ

( У

1 у ^, ₂ ⁾ d^y 2

^в 4

(1 + у ₁) ²

2 b

+

(1 + У ) ²

2      .

2 b

( ф ( У ) = Q ( У I 0)) ,        (9)

12 ф 2

У е [0, ~).

1            aa

Q (У  1 У2) = —■ ехр[— + — (У2 - У 2 + 1)] X ф 2 п b b bb

\ 12       12

Если шу и D v - среднее и дисперсия

X [ — K (2 Iв ■ Y ) - — K (2 Iв ■ Г )];

(^e , ¹ V -      у2 - V ²

в 1 = ¹

^{2 b} 1

₊ ⁽ у 2 - у ₂ ^{+ 1)2}

² b 2      ’

∞ распределения v(y 1 )=^VK(У 1), то иско-к=1

мые параметры двумерного диффузионного приближения p[Т [, D { , входящие в уравнение (2) и формулы для основных характеристик узла, можно выразить через эти величины ^ v , D v и известные параметры входно

^в 2

=+

2 b

( У ‘

+ У +1) ²

2 b

;

γ =

a

+

2 b

a

2 .

2 b

У е [0, ~);

K 1 ( • ) - функция Макдональда;

го потока: среднее Т ^ и дисперсию D ^ времени между заявками. Решение этой задачи связано с использованием функции плотности времени первого достижения марковским процессом заданного уровня g ( t | У 1 ) . Окончательные формулы имеют следующий вид:

^тх = ^тх ■ m V ,

D_λ ′

= D_λmψ

+ τ_λD_ψ

- для среднего и дисперсии времени простоя

узла и

p_jt’ - ММ p ( mm iw^m * / яо

- для вероятности того, что обслуженная заявка оставляет узел пустым. Подставив последние формулы в (1) и (2) получим окончательные формулы для определения парамет-

ров выходного потока.

В случае сетевых моделей с неоднородными потоками, в которых заявки различаются маршрутами и законами поступления и обслуживания, параметры потоков различных классов (m=1,…,М) усредняются с целью приведения неоднородного потока к однородному. Эти параметры будут описывать, так называемую, обобщенную заявку. При этом соблюдается условие, чтобы однородный поток создавал такую же нагрузку в каждом узле сети, что и неоднородный поток. Для определения параметров потоков обобщенных заявок получены следующие формулы:

я° 6 - М wim1 m-1

- для интенсивности поступления потока

обобщенных заявок на вход i ‒ го узла (i=1,…n);

= Е     m* /Об m-1V / ^i )/ Я/

d ” - М [ d* я * * + V* * - ^ ² w m ' ] / я о ⁶

- для среднего и дисперсии времени обслу-

- для значений обобщенной матрицы вероятностей передач.

Итерационная процедура расчета сети с неоднородными потоками будет такая же, что и для однородного потока с приведенными параметрами, т.е. заключается в решении уравнений (5) и (6) совместно с (2). Используя полученные характеристики для отдельного узла сети определяются характеристики сети для каждого типа заявок, аналогично сетям с однородными потоками.

Далее рассмотрим модели систем с ограниченной емкостью накопителя и с потерями (рис.2а траектория 2), а также с переменными параметрами законов поступления и обслуживания заявок (рис.2а траектория 3). Такие модели отражают процесс прохождения задач в отдельной ЭВМ и в более сложных комплексах - с етях передачи данных, имеющих буферные накопители ограниченной емкости. Последняя модель также отражает работу саморегулирующихся динамических систем.

Для определения характеристик моделей систем, содержащих узлы с потерями и ограничениями на длину очереди, сеть также декомпозируется на отдельные узлы на уровне двух моментов. При этом уравнения баланса (5) и (6) модифицируются: учитываются потоки отказов, идущие от узлов с потерями к другим узлам. Вводится матрица Q - { q j } вероятностей передач заявок потоков отказов от i-го узла на вход j-го (i,j=1,…,n), а в системы (5) и (6) добавляются соответствующие слагаемые, учитывающие потоки отказов. Тогда уравнения баланса примут вид:

живания;

^Dоб - _тМ 1Г яоб ¹ ) ³ ° о m *

- 1 ^я 1вх o oi

D

n

n

⁺ J - 1 ^Pij ^X j ^{вых +} J - 1 ^qji ^X j отк

Г 01

i ^вх     X.

вх

V

Doz ⁺

- для интенсивности и дисперсии потока от внешнего источника;

n

Г я

j вых ^Pj

V     / вх     )

1 p.. ji

^Dj вых ⁺ V

¹ - Pji

\

22   P..

j вых jz )

n (^x j отк j 1

■ j 1^    iвх   J

1 q_ji

Dj отк

I

+ ¹ - qji ' ^ j отк qji J J

Для определения среднего Т _отк и дисперсии D _{T omK} времени между заявками в потоке отказов получены формулы:

Тотк = ТвхТвых (-вых - Твх ) (20)

где Твх, и Твых - средние времена между последующими заявками во входном и выходном потоках, и dtotk = DNоткТотк /тц »     (21)

где Тц - среднее время цикла занятости, DN отк - дисперсия числа потерянных заявок на цикле занятости. Численное определение D выполняется аналогично отк вычислению распределения фк(у2): вычисляются условные распределения числа и квадрата числа потерянных заявок.

Основные характеристики для узла с потерями определяются с учетом того, что уравнение Колмогорова решается в области D, определенной двухсторонними условиями N >  0 и N <  m , m - максимально допустимое число заявок в узле (ри-с.2а траектория 2). Граничные условия для уравнения (7) физически эквивалентны условиям поглощения на границе Г₁, где t o | _Г| = 0 и отражения на границе Г₂ где grad^ _Г 2 = 0 .

В задаче анализа систем с переменными параметрами законов по ступления и обслуживания, зависящими от состояния система (длины очереди к ресурсу), вышеуказанные распределения ^к (У|) и фк (у2) определяются отдельно для каждой из подобластей DK(к = I,...,m;i = 1,2,...). Области Dкi физически соответствует период функционирования узла, на котором в узле находится ровно к заявок (индекс к определяет уровень по оси x1, i ‒ уровень по x2). Этот период характеризуется своими интенсивностями поступления и обслуживания заявок, а также дисперсиями этих времен, зависящими от состояния системы. Такой подход означает решение уравнения Колмогорова с переменными коэффициентами сноса и диффузии, зависящими от длины очереди в узле (рис.2б).

Приведены результаты машинных экспериментов по оценке точности метода двумерного диффузионного приближения. Точность методов исследована для диапазонов изменения коэффициента загрузки от 0,1 до 0,9 и коэффициентов вариаций распределений длин интервалов между заявками во входом потоке и времени обслуживания от 0 до 5.Значения среднего числа заявок в узле сравнивались с результатами имитационного моделирования.

В качестве одного из параметров моделирования задавалось количество циклов занятости, которое в зависимости от загрузки изменялось от 1000 до 20000. Для отдельных узлов сети результаты двумерного диффузионного приближения совпадают с результатами имитационного моделирования в пределах 2-5% и в некоторых крайних случаях отклоняются до 10%. При расчете сетевых моделей добавляются ошибки декомпозиции, поэтому погрешно сть получалась несколько выше - до 15%.

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

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

Ниже кратко описан алгоритм разработанной авторами системы моделирования.

Алгоритм функционирования интерактивной системы вероятностного моделирования стохастических систем.

• 1.    Задание конфигурации (топологии) сетевой модели системы, определяемой матрицей вероятностей передач Р={P_ij}(i,j=0,1,…,n).

• 2. Задание параметров входного потока заявок λ_0, с₀ и параметров обслуживающих приборов µ_i, cµ_i (i=1,…,n).

• 3.    Указание типа сетевой модели (однородная, неоднородная).

• 4. Указание типов обслуживающих приборов по емкости накопителей (с неограниченной очередью, с ограниченной очередью и отказами, с ограниченной очередью и переменными параметрами поступления и обслуживания).

• 5.    Задание массивов варьируемых параметров системы (для входного потока требований и параметров в обслуживающих устройствах).

• 6.    Расчет внутренних характеристик сложной системы путем ее декомпозиции на отдельные подсистемы.

• 7.    Запуск итеративной процедуры калибровки модели заданной конфигурации

  

  Рис.3. Зависимость времени задержки в узле при различных значениях интенсивности

  X входного трафика (время обслуживания нормированное): а) - от коэффициента вариации входного потока; б) - от коэффициента вариации времени обслуживания

  
  
  
  
  

• 8.    Окончание процесса моделирования.

(переход к пункту 2 в случае необходимости или к пункту 8).

Здесь использованы следующие обозначения: Pij ‒ элементы стохастиче ской матрицы вероятностей передач; λ0 ‒ интенсивность входного потока заявок (ед/ с); с0 ‒ коэффициент вариации распределения времени во входном потоке; µi‒ интенсивность обслуживания (ед/с) в i-ом узле сетевой модели; cµi ‒ коэффициент вариации распределения времени обслуживания в i-ом узле сетевой модели.