Основные свойства потоков

Размещено на http://www.allbest.ru/

1. Наиболее распространенные классы потоков

поток математический ожидание дисперсия

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

Для описания потока заявок, в общем случае, необходимо задать интервалы времени между соседними моментами t_k-1 и t_k поступления заявок с порядковыми номерами (k -1) и k соответственно (k =1, 2, ...; t₀=0 - начальный момент времени).

Основной характеристикой потока заявок является его интенсивность л- среднее число заявок, проходящих через некоторую границу за единицу времени. Величина a=1/л определяет средний интервал времени между двумя последовательными заявками.

Поток, в котором интервалы времени ф_k между соседними заявками принимают определенные заранее известные значения, называется детерминированным. Если при этом интервалы одинаковы (ф_k=ф для всех k =1, 2, ...), то поток называется регулярным. Для полного описания регулярного потока заявок достаточно задать интенсивность потока л или значение интервала ф=1/л.

Поток, в котором интервалы времени ф_k между соседними заявками представляют собой случайные величины, называется случайным. Для полного описания случайного потока заявок, в общем случае, необходимо задать законы распределений A_k (ф_k ) всех интервалов ф_k (k =1, 2, ...).

Случайный поток, в котором все интервалы ф₁,ф₂,… между заявками независимы в совокупности и описываются функциями распределений A1(ф₁), A2 (ф₂ ) ,…, называется потоком с ограниченным последействием.

Случайный поток, в котором все интервалы ф₁,ф₂,… распределены по одному и тому же закону A(ф) , называется рекуррентным.

Поток заявок называется стационарным, если интенсивность л и закон распределения A(ф) интервалов между последовательными заявками не меняются со временем. В противном случае поток заявок является нестационарным.

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

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

Стационарный ординарный поток без последействия называется простейшим.

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

Простейший поток часто называют пуассоновским, поскольку число заявок k, поступающих за некоторый заданный промежуток времени t, распределено по закону Пуассона.

Следует отметить, что пуассоновский поток, в отличие от простейшего, может быть:

- стационарным, если интенсивность л не меняется со временем;

- нестационарным, если интенсивность потока зависит от времени: л = л(t).

В то же время, простейший поток, по определению, всегда является стационарным.

2. Основные свойства потоков

В настоящем мы рассмотрим потоки событий, обладающие некоторыми особенно простыми свойствами. Для этого введем ряд определений.

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

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

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

Если поток событий обладает всеми тремя свойствами (т. е. стационарен, ординарен и не имеет последействия), то он называется простейшим (или стационарным пуассоновским) потоком. Название «пуассоновский» связано с тем, что при соблюдении условий 1-3 число событий, попадающих на любой фиксированный интервал времени, будет распределено по закону Пуассона.

Рассмотрим подробнее условия 1-3, посмотрим, чему они соответствуют для потока заявок и за счет чего они могут нарушаться.

1. Условию стационарности удовлетворяет поток заявок, вероятностные характеристики которого не зависят от времени. В частности, для стационарного потока характерна постоянная плотность (среднее число заявок в единицу времени). На практике часто встречаются потоки заявок, которые (по крайней мере, на ограниченном отрезке времени) могут рассматриваться как стационарные. Например, поток вызовов на городской телефонной станции на участке времени от 12 до 13 часов может считаться стационарным. Тот же поток в течение целых суток уже не может считаться стационарным (ночью плотность вызовов значительно меньше, чем днем). Заметим, что так обстоит дело и со всеми физическими процессами, которые мы называем «стационарными»: в действительности все они стационарны лишь на ограниченном участке времени, а распространение этого участка до бесконечности - лишь удобный прием, применяемый в целях упрощения анализа. Во многих задачах теории массового обслуживания представляет интерес проанализировать работу системы при постоянных условиях; тогда задача решается для стационарного потока заявок.

2. Условие отсутствия последействия - наиболее существенное для простейшего потока - означает, что заявки поступают в систему независимо друг от друга. Например, поток пассажиров, входящие на станцию метро, можно считать потоком без последействия потому, что причины, обусловившие приход отдельного пассажира именно в тот, а не другой момент, как правило, не связаны с аналогичными причинами для других пассажиров. Однако условие отсутствия последействия может быть легко нарушено за счет появления такой зависимости. Например, поток пассажиров, покидающих станцию метро, уже не может считаться потоком без последействия, так как моменты выхода пассажиров, прибывших одним и тем же поездом, зависимы между собой.

Вообще нужно заметить, что выходной поток (или поток обслуженных заявок), покидающий систему массового обслуживания, обычно имеет последействие, даже если входной поток его не имеет. Чтобы убедиться в этом, рассмотрим одноканальную систему массового обслуживания, для которой время обслуживания одной заявки вполне определено и равно . Тогда в потоке обслуженных заявок минимальный интервал времени между заявками, покидающими систему, будет равен . Нетрудно убедиться, что наличие такого минимального интервала неизбежно приводит к последействию. Действительно, пусть стало известно, что в какой-то момент систему покинула обслуженная заявка. Тогда можно утверждать с достоверностью, что на любом участке времени , лежащем в пределах , обслуженной заявки не появится; значит, будет иметь место зависимость между числами событий на неперекрывающихся участках.

Последействие, присущее выходному потоку, необходимо учитывать, если этот поток является входным для какой-либо другой системы массового обслуживания (так называемое «многофазовое обслуживание», когда одна и та же заявка последовательно переходит из системы в систему).

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

3. Условие ординарности означает, что заявки приходят поодиночке, а не парами, тройками и т. д. Например, поток атак, которому подвергается воздушная цель в зоне действия истребительной авиации, будет ординарным, если истребители атакуют цель поодиночке, и не будет ординарным, если истребители идут в атаку парами. Поток клиентов, входящих в парикмахерскую, может считаться практически ординарным, чего нельзя сказать о потоке клиентов, направляющихся в ЗАГС для регистрации брака.

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

3. Регулярный поток

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

Функция f(х) плотности распределения вероятности случайной величины Т - интервала времени между событиями имеет при этом вид:

,

где - дельта функция, М_т- математическое ожидание, причем М_т=Т, дисперсия D_т=0 и интенсивность наступления событий в поток =1/M_т=1/T.

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

4. Поток с ограниченным последействием (рекуррентный поток)

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

4.1 Поток с ограниченным последействием (поток Пальма)

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

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

Рассмотрим ординарный поток однородных событий

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

Очевидно, простейший поток является частным случаем потока Пальма: в нем расстояния представляют собой независимые случайные величины, распределенные по показательному закону. Что касается нестационарного пуассоновского потока, то он не является потоком Пальма. Действительно, рассмотрим два соседних промежутка и в нестационарном пуассоновском потоке. Как мы видели в предыдущем , закон распределения промежутка между событиями в нестационарном потоке зависит от того, где этот промежуток начинается, а начало промежутка совпадает с концом промежутка ; значит, длины этих промежутков зависимы.

Рассмотрим примеры потоков Пальма.

1. Некоторая деталь технического устройства (например, радиолампа) работает непрерывно до своего отказа (выхода из строя), после чего она мгновенно заменяется новой. Срок безотказной работы детали случаен; отдельные экземпляры выходят из строя независимо друг от друга. При этих условиях поток отказов (или поток «восстановлений») представляет собой поток Пальма. Если, к тому же, срок работы детали распределен по показательному закону, то поток Пальма превращается в простейший.

2. Группа самолетов идет в боевом порядке «колонна» с одинаковой для всех самолетов скоростью . Каждый самолет, кроме ведущего, обязан выдерживать строй, т. е. держаться на заданном расстоянии от впереди идущего. Это расстояние, вследствие погрешностей радиодальномера, выдерживается с ошибками. Моменты пересечения самолетами заданного рубежа образуют поток Пальма, так как случайные величины ; ; … независимы. Заметим, что тот же поток не будет потоком Пальма, если каждый из самолетов стремится выдержать заданное расстояние не от соседа, а от ведущего.



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

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

Основной в теории выходных потоков является теорема Пальма, которую мы сформулируем без доказательства.

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

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

Интересным примером потоков с ограниченным последействием являются так называемые потоки Эрланга. Они образуются «просеиванием» простейшего потока.

Рассмотрим простейший поток и выбросим из него каждую вторую точку (на рисунке выброшенные точки отмечены крестами).

Оставшиеся точки образуют поток; этот поток называется потоком Эрланга первого порядка . Очевидно, этот поток есть поток Пальма: поскольку независимы промежутки между событиями в простейшем потоке, то, независимы и величины , получающиеся суммированием таких промежутков по два.

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

Вообще, потоком Эрланга k-го порядка называется поток, получаемый из простейшего, если сохранить каждую -ю точку, а остальные выбросить. Очевидно, простейший поток можно рассматривать как поток Эрланга нулевого порядка .

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

Величина представляет собой сумму независимых случайных величин

,

где - независимые случайные величины, подчиненные одному и тому же показательному закону

.

Можно было бы найти закон распределения величины как композицию законов Однако проще вывести его элементарными рассуждениями.

Обозначим плотность распределения величины для потока ; есть вероятность того, что величина примет значение между и . Это значит, что последняя точка промежутка должна попасть на элементарный участок , а предыдущие точек простейшего потока - на участок . Вероятность первого события равна вероятность второго, на основании формулы, будет

.

Перемножая эти вероятности, получим

,

откуда

.

Закон распределения с плотностью называется законом Эрланга -го порядка. Очевидно, при он обращается в показательный

.

Найдем характеристики закона Эрланга : математическое ожидание и дисперсию . По теореме сложения математических ожиданий

,

где - математическое ожидание промежутка между событиями в простейшем потоке.

Отсюда

.

Аналогично по теореме сложения дисперсий

, .

Плотность потока будет обратна величине

.

Таким образом, при увеличении порядка потока Эрланга увеличиваются как математическое ожидание, так и дисперсия промежутка времени между событиями, а плотность потока падает.

Выясним, как будет изменяться поток Эрланга при , если его плотность будет сохраняться постоянной? Пронормируем величину так, чтобы ее математическое ожидание (и, следовательно, плотность потока) оставалось неизменным. Для этого изменим масштаб по оси времени и вместо рассмотрим величину

.

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

,

, или .

Математическое ожидание величины , распределенной по закону, не зависит от и равно

,

где - плотность потока, совпадающая при любом с плотностью исходного простейшего потока. Дисперсия величины равна

и неограниченно убывает с возрастанием .

Таким образом, мы приходим к выводу: при неограниченном увеличении нормированный поток Эрланга приближается к регулярному потоку с постоянными интервалами, равными .

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

Пример. В результате статистической обработки промежутков между заявками в потоке получены оценки для математического ожидания и дисперсии величины :

(мин), (мин2).

Заменить этот поток нормированным потоком Эрланга с теми же характеристиками.

Решение. Имеем

.

Из формулы получим

, .

Поток можно приближенно заменить нормированным потоком Эрланга четвертого порядка.

4.2 Нестационарный пуассоновский поток

Если поток событий нестационарен, то его основной характеристикой является мгновенная плотность . Мгновенной плотностью потока называется предел отношения среднего числа событий, приходящегося на элементарный участок времени , к длине этого участка, когда последняя стремится к нулю:

,

где - математическое ожидание числа событий на участке .

Рассмотрим поток однородных событий, ординарный и без последействия, но не стационарный, с переменной плотностью . Такой поток называется нестационарным пуассоновским потоком. Это - первая ступень обобщения по сравнению с простейшим потоком. Легко показать методом, аналогичным примененному в 5.9, что для такого потока число событий, попадающих на участок длины , начинающийся в точке , подчиняется закону Пуассона

,

где - математическое ожидание числа событий на участке от до равное

.

Здесь величина зависит не только от длины участка, но и от его положения на оси .

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

.

Найдем - вероятность того, что на участке от до не появится ни одного события:

,

откуда

.

Дифференцируя, найдем плотность распределения

 .

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

плотность (19.4.5) имеет вид

.

График этого закона при ; и представлен на рис.

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

5. Потоки с неоднородной структурой

Неоднородные потоки - такие потоки, в которых требования обладают неодинаковыми свойствами: требования удовлетворяются по принципу приоритетности (пример, карта прерываний в ЭВМ), обрабатываемые требования имеют различные физические свойства.

Схематично неоднородный поток событий может быть изображен следующим образом

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

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

Для моделирования неоднородных потоков системы можно разделить на три класса.

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

У системы для каждого типа заявки имеется отдельный канал (один или несколько). Моделирование таких систем выполняется так же, как и для однородных потоков, но, во-первых, необходимо предусмотреть разделитель заявок в соответствии с типами и предусмотреть то, что эти заявки могут обследоваться как каждая в своём канале;

Рис. 1. У каждой заявки отдельный канал

Системы, в которых типы заявок и номера каналов переплелись. При моделировании таких систем необходимо предусмотреть распределение потоков заявок по соответствующим каналам. Один из вариантов распределения этих потоков предусматривает создание массива соответствующих параметров.



Рисунок 2. Типы заявок и номера каналов переплелись.

Размещено на Allbest.ru