Материал: Моделирование атак сети массового обслуживания. Бугров Ю.Г., Остапенко Г.А

3.2. Потоки событий

Потоком событий называется последователь­ность однородных событий, следующих одно за другим в какие-то случайные моменты времени [35].

Поток событий можно наглядно изобразить рядом точек на оси времени Ot (рис. 3.3); не надо только забывать, что положение каждой из них случайно, и на рис. 3.3 изображена только какая-то одна реализация потока.

Рис. 3.3. Поток событий

Говоря о «потоке событий», нужно иметь в виду, что здесь термин «событие» имеет значение, несколько отличное от того, который используется в теории вероятностей. Там «событием» (или «случайным со­бытием») называется какой-то исход опыта, обладаю­щий той или другой вероятностью. События, образую­щие поток, сами по себе вероятностями не обладают; вероятностями обладают другие, производные от них события, например: «на участок времени (рис. 3.3.) попадет ровно два события», или «на участок време­ни попадет хотя бы одно событие», или «промежу­ток времени между двумя соседними событиями бу­дет не меньше t».

Важной характеристикой потока событий является его интенсивность К — среднее число событий, приходящееся на единицу времени. Интенсивность по­тока может быть как постоянной ( = const), так и переменной, зависящей от времени t.

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

Поток событий называется стационарным, ес­ли его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока должна быть постоянной. Однако это не зна­чит, что фактическое число событий, появляющееся в единицу времени, постоянно — поток неизбежно (если только он не регулярный) имеет какие-то слу­чайные сгущения и разрежения, как, например, по­казано на рисунке 3.3. Важно, что для стационарного потока эти сгущения и разрежения не носят законо­мерного характера: на один участок длины 1 может попасть больше, а на другой — меньше событий, но среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.

Поток событий называется потоком без пос­ледействия, если для любых двух непересекаю­щихся участков времени t₁ и t₂ (рис. 3.4) число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или другие моменты времени независимо друг от друга, вызванные каждое своими собст­венными причинами.

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

Рис. 3.4. Поток событий без последствий

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия. Название «простейший» связано с тем, что процессы, связанные с простейшими потоками, име­ют наиболее простое математическое описание. Между прочим, самый простой, на первый, взгляд, регулярный поток не является «простейшим», так как обладает последействием: моменты появления событий в таком потоке связаны жесткой, функциональной зависи­мостью. Без специальных усилий по поддержанию его регулярности такой поток обычно не создается.

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

Легко доказать, что для простейшего потока с интенсивностью . ин­тервал Т между соседними событиями имеет так назы­ваемое показательное распределение [12] с плотностью

. (3.1)

Величина в формуле (2.1) называет­ся параметром показательного закона. Для слу­чайной величины Т, имеющей показательное распре­деление, математическое ожидание есть величина, обратная параметру, а среднее квадратическое откло­нение равно математическому ожиданию:

. (3.2)

В теории вероятностей в качестве «меры случайно­сти» неотрицательной случайной величины нередко рассматривают так называемый коэффициент вариации:

. (3.3)

Из формул (3.2), (3.3) следует, что для показа­тельного распределения , т. е. для простейшего потока событий коэффициент вариации интервалов между событиями равен единице [40].

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

В расчетах, связанных с потоками событий, очень удобно пользоваться понятием «элемента вероятности». Рассмотрим на оси Ot простейший поток с интенсив­ностью и произвольно расположенный элементарный (очень маленький) участок времени . Элементом вероятности называется вероятность попадания на этот участок хотя бы одного события потока. Элемент ве­роятности (с точностью до малых величин более высо­кого порядка по сравнению с ) равен

_, (3.4)

то есть для простейшего потока элемент вероятности ра­вен интенсивности потока, умноженной на длину эле­ментарного участка. Заметим, что элемент вероятно­сти, в силу отсутствия последействия, совершенно не зависит от того, сколько событий и когда появлялись ранее.

Заметим также, что с точностью до величин выс­шего порядка малости вероятность появления хотя бы одного события на элементарном участке равна ве­роятности появления ровно одного события на этом участке. Это вытекает из ординарности простейшего потока [41].

Поток событий называется рекуррентным (иначе — «потоком Пальма»), если он стационарен, орди­нарен, а интервалы времени между событиями Т₁, Т₂, Т₃, ... (рис. 3.5) представляют собой независимые случайные величины с одинаковым произвольным распределением (например, с плотностью, показанной на рис. 3.5).

Рис. 3.5. Рекуррентный поток

Очевидно, простейший поток представляет собой частный случай рекуррентного потока, когда ин­тервалы между событиями имеют показательное рас­пределение (3.1). Другим частным (вырожденным) случаем рекуррентного потока является регулярный поток событий, где интервалы вообще не случайны, постоянны.

Целую гамму рекуррентных потоков событий, обла­дающих разной степенью упорядоченности, можно по­лучить «просеиванием» про­стейшего потока. Такой поток получается из простейшего, если сохранять в потоке каждое n-е событие, а промежуточные — выбрасывать. Простейший поток есть не что иное, как поток Эрланга первого порядка. Можно показать, что при таком просеивании простейшего по­тока коэффициент вариации интервалов уменьшается, и при увеличении порядка n поток Эрланга приближа­ется к регулярному. Коэффициент вариации интерва­лов между событиями потока Эрланга n-го порядка равен . Потоки Эрланга образуют целую гамму потоков с различной степенью упорядочен­ности — от «полного беспорядка» (простейший поток) до полной упорядоченности (регулярный поток).

3.3. Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний

Рассматривая марковские процессы с дискретными состояниями и непрерывным временем, нам удобно будет представлять себе, что все переходы системы S из состояния в состояние происходят под действием каких-то потоков событий (поток вызовов, поток отка­зов, поток восстановлений и т. д.). Если все потоки со­бытий, переводящие систему S из состояния в состоя­ние — простейшие, то процесс, протекающий в системе, будет марковским. Это и естественно, так как про­стейший поток не обладает последействием: в нем «бу­дущее» не зависит от «прошлого» [48].

Если система S находится в каком-то состоянии S_i, из которого есть непосредственный переход в другое состояние S_j (стрелка, ведущая из S_i в S_j на графе состояний), то мы себе это будем представлять так, как будто на систему, пока она находится в состоянии S_i, действует простейший поток событий, переводящий ее по стрелке _. Как только появится первое событие этого потока, происходит «перескок» системы из S_i в S_j.

Для наглядности очень удобно на графе состояний у каждой стрелки проставлять интенсивность того по­тока событий, который переводит систему по данной стрелке. Обозначим интенсивность потока событий, переводящего систему из состояния S_i в S_j. На рис. 3.6 дан граф состояний с проставленными у стрелок интенсивностями (мы будем называть такой граф размеченным).

Построим размеченный граф состояний для состояний системы:

S₀ — оба узла исправны,

S₁ — первый узел ремонтируется, второй исправен,

S₂ — второй узел ремонтируется, первый исправен,

S₃ — оба узла ремонтируются.

Рис. 3.6. Размеченный граф состояний

Интенсивности потоков событий, переводящих сис­тему из состояния в состояние, будем вычислять, пред­полагая, что среднее время ремонта узла не зависит от того, ремонтируется ли один узел или оба сразу. Это будет именно так, если ремонтом каждого узла занят отдельный специалист. Найдем все интенсивно­сти потоков событий, переводящих систему из состоя­ния в состояние. Пусть система находится в состоянии S₀. Какой поток событий переводит ее в состояние S₁? Очевидно, поток отказов первого узла. Его интенсив­ность равна единице, деленной на среднее время безотказной работы первого узла. Какой поток собы­тий переводит систему обратно из S₁ в S₀? Очевидно, поток «окончаний ремонтов» первого узла. Его интен­сивность равна единице, деленной на среднее время ремонта первого узла.

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

В самом деле, пусть рассматривается система S, имеющая п возможных состояний S₁, S₁, ..., S_n. Назо­вем вероятностью i-ro состояния вероятность того, что в момент t система будет находиться в состоянии S_i. Очевидно, что для любого момента сумма всех вероятностей состояний равна единице:

. (3.5)

Имея в своем распоряжении размеченный граф со­стояний, можно найти все вероятности состояний как функции времени.

Для это­го составляются и решаются так называемые уравнения Колмогорова — особого ви­да дифференциальные уравне­ния, в которых неизвестными функциями являются вероятно­сти состояний.

Покажем на конкретном примере, как эти уравнения со­ставляются. Пусть система S имеет четыре состояния: S₁, S₂, S₃, S₄, размеченный граф которых показан на рис. 3.7.

Рис. 3.7. Размеченный граф состояний

Рассмотрим одну из вероятностей состояний, например . Это — вероятность того, что в момент t система будет в состоянии S₁. Придадим t малое приращение и найдем — вероятность того, что в момент система будет в состоянии S₁. Как это может произойти? Очевидно, двумя способами: либо 1) в мо­мент t система уже была в состоянии S₁ а за вре­мя не вышла из него; либо 2) в момент t систе­ма была в состоянии S₂, а за время перешла из него в S₁.

Найдем вероятность первого варианта. Вероятность того, что в момент t система была в состоянии S₁, рав­на p₁(t). Эту вероятность нужно умножить на веро­ятность того, что, находившись в момент t в состоянии S₁, система за время не перейдет из него ни в S₂ ни в S₃. Суммарный поток событий, выводящий систе­му из состояния S₁, тоже будет простейшим, с интен­сивностью (при наложении — суперпозиции — двух простейших потоков получается опять простей­ший поток, так как свойства стационарности, ординарности и отсутствия последействия сохраняются). Зна­чит, вероятность того, что за время система выйдет из состояния S₁, равна вероятность того, что не выйдет: _.

Отсюда вероятность первого варианта равна _.

Найдем вероятность второго варианта. Она равна вероятности того, что в момент t система будет в со­стоянии S₂, а за время перейдет из него в состоя­ние S₁, т. е. она равна _.