Приложения Марковских процессов

⇐ ПредыдущаяСтр 16 из 18Следующая ⇒

Имеется телефонная станция (центр), в которой m каналов (m может быть как конечной, так и бесконечной величиной). Вызовы поступают на станцию в моменты t1, …, tn, …(0< t1 < …< tn < ¥ ).

Сделаем предположения относительно управления вызовами, поступающими на станции.

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

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

3. После окончания разговора занятый канал немедленно становится доступным для нового вызова.

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

Рассмотрим характеристику процесса обслуживания. В системе имеется m обслуживающих приборов. Рассмотрим функцию распределения интервалов между поступлениями вызовов и длительностью обслуживания (разговоров).

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

, (n=1, 2, …) – одинаково распределенные, независимые положительные случайные величины, и A(t) – их общая функция распределения.

Пусть - средняя длительность интервала между поступлениями.

- длительность разговора вызова, поступившего в момент tn. Пусть (n=1, 2, …) одинаково распределенные независимые случайные величины, независящие от процесса {t_n}.

Пусть функция распределения длительностей разговора является показательной:

(6.35)

Одной из основных задач телефонии является определение вероятности P_x(t) того, что из группы в m-каналов в момент t занято х. Особое внимание уделяется исследованию предельных вероятностей

Пример. Рассмотрим Марковский процесс на телефонной станции с бесконечным числом каналов.

Пусть случайная величина x(t) – число занятых каналов в момент t и . Так как x может принимать значения 0, 1, …, то процесс является Марковским со счетным множеством состояний. Система находится в состоянии х, если занято х каналов. В силу предположений о моментах поступления и длительностей разговоров,

1) вероятность того, что в интервале (t, t+Dt) вызов поступит на станцию, равна lDt +0(Dt), l> 0;

2) если в момент t занято х каналов, что один из них освободится в интервале (t, t+Dt), равна хmDt +0(Dt), m> 0;

3) если в момент t занято х каналов, то вероятность того, что ни один из каналов не освободится и вызов не поступит на станцию в интервале (t, t+Dt)=1-(l+хm)Dt +0(Dt);

4) вероятность осуществления любых других событий в интервале (t, t+Dt)=0(Dt);

Поэтому в интервале (t, t+Dt) с точностью до величин вероятностей порядка 0(Dt) возможны лишь следующие переходы: (х®х+1), (х®х-1), (х®х).

Такой Марковский процесс является процессом рождения и гибели с интенсивностями рождения и гибели . Тогда

. (6.36)

Вопросы для самоконтроля:

1. Основные понятия Марковских процессов.

2. Определение цепи Маркова.

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

4. Пуассоновский поток.

5. Просеянные потоки.

6. Дискретные Марковские цепи.

7. Эргодические цепи Маркова.

8. Поглощающие цепи Маркова.

9. Непрерывные Марковские цепи.

10. Правило формирования уравнений.

11. Типовые графы состояний системы.

12. Процесс гибели и размножения.

13. Циклический процесс.

14. Не Марковские случайные процессы, сводящиеся к Марковским.

15. Метод разложения случайного процесса на фазы.

16. Приложения Марковских процессов.

Описание информационных систем с помощью сетей Петри

Учебные вопросы:

Основные понятия сетей Петри.

Типы сетей Петри.

Приложения сетей Петри.

Основные понятия сетей Петри

Информационная система, как один из видов сложных систем, характеризуется:

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

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

3. Параллелизмом: несколько подсистем могут функционировать в системе одновременно, не влияя друг на друга (т.е. в системе могут протекать одновременно ряд параллельных процессов);

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

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

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

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

Условие (condition) - предикат, являющийся логическим описанием ситуации, при которой некоторое событие может произойти (реализоваться). Т.е. если предикат, соответствующий условию имеет значение “истина (“1”)”, то событие может произойти; если предикат, соответствующий условию имеет значение “ложно (“0”)”, то событие реализоваться не может. Через обозначается множество условий, которые связаны с событиями, принадлежащими множеству .

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

Предусловие (pre-condition) – логическое отношение “ ” нескольких условий, при истинном значении, которого некоторое событие может реализоваться.

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

Постусловие (post-condition) – определенное сочетание нескольких условий , на которые оказывает влияние реализация события , делая их значения “истинными”.

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

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

Причинно-следственная связь (pre/consequence condition) – непосредственная зависимость между событием и условиями , принадлежащими его предусловию и постусловию .

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

Состояние системы (state of system) - совокупность значений истинности для каждого из условий , в некоторый момент времени .

Пусть множество всех допустимых состояний системы .

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

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

1. Отказ от временных зависимостей приводит к тому, что события являются элементарными, т.е. являются неделимыми и происходят “мгновенно”, а изменения значений условий в предусловиях и постусловиях происходят одновременно, т.е. выполнение события считается незримым актом.

2. Реализация события приводит к тому, что все условия становятся “ложными”, а - “истинными”.

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

4. Каждое событие при определенных условиях может реализоваться хотя бы один раз.

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

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

- “начало обработки задания в процессоре”;

- “конец обработки задания в процессоре”;

и вновь вводимого условия - “обработка задания в процессоре в течение минут”, которое удовлетворяет следующим отношениям принадлежности: и .

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

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

Условно/событийная система (condition/event system) – четверка , где - конечное непустое множество событий; - конечное непустое множество условий; - множество достижимых состояний; - отображение, описывающее совокупность правил перехода.

⇐ Предыдущая 9 10 11 12 13 14 151617 18 Следующая ⇒