Основы марковской теории сетей массового обслуживания

Анализ систем массового обслуживания без явных потерь. Анализ сетей массового обслуживания с блокировками. Метод вероятностных графов Ли Основы марковской теории сетей массового обслуживания возможность расчета характеристик более сложных по структуре систем массового обслуживания.

2015-01-12

48.83 KB

11 чел.


Поделитесь работой в социальных сетях

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


Лекция  №8

по дисциплине “Теория распределение информации»

Наименование темы: Основы марковской теории сетей массового обслуживания

1. Анализ систем массового обслуживания без явных потерь

2. Анализ сетей массового обслуживания с блокировками. Метод вероятностных графов Ли

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

1. Анализ систем массового обслуживания без явных потерь

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

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

Рассмотрим простейшую последовательную систему с двумя узлами (Рис. 1).

Рис. 1  Простейшая последовательная система с двумя узлами

Это топологическая структура сети, а не диаграмма состояний. Предположим, что входной поток пуассоновский с интенсивностью λ, который поступает на первый узел, в котором находится СМО типа M/M/1, с сервером, имеющим показательное распределение времени обслуживания со средним значением  μ. Будем считать, что второй узел состоит из единственного обслуживающего прибора с показательным распределением времени обслуживания с интенсивностью  также равной μ. Основная задача состоит в вычислении распределения промежутков времени между последовательными заявками, поступающими в узел 2, т.е. уходящими из 1.

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

Обозначим ее преобразование Лапласа

.

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

.

Здесь B(s) – преобразование Лапласа плотности вероятности времени обслуживания.

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

.

Используя то свойство, что вероятность того, что заявка покинет систему пустой, равна вероятности того, что заявка поступит в момент, когда в системе  нет заявок и равна в точности 1-ρ. Это позволяет записать преобразование Лапласа для плотности вероятности распределения промежутка времени полностью в виде

Следовательно, плотность вероятности распределения промежутков времени между заявками, покидающими узел 1, является также случайной величиной с показательным законом распределения с тем же самым параметром. Это значит, что СМО типа М/M/1 превращает пуассоновский поток на входе в пуассоновский поток на выходе с тем же самым параметром. Этот результат называют теоремой Бёрке. Им было показано, что этот факт имеет место для всех СМО типа M/M/m. На основании этой теоремы можно исследовать многофазные последовательностные схемы.

 

2. Анализ сетей массового обслуживания с блокировками. Метод вероятностных графов Ли

Рассмотренный выше марковский подход к анализу сетей массового обслуживания позволяет рассчитать вероятности состояний для сетей, состоящих из узлов, каждый из которых есть СМО типа M/M/m. При этом предполагается, что каждый узел содержит бесконечный накопитель и все заявки будут обслужены через некоторое время.  Другой постановкой задачи является анализ сети с узлами, в которых может быть СМО с блокировкой заявок. Часто такими СМО выступают коммутационные схемы, имеющие конечные пучки соединительных линий. Другой моделью являются сети с множественным доступом к фиксированному числу каналов. Рассмотрим в качестве примера (рис.2) подключение сельского абонента С через абонентскую линию с блокиратором к сельской АТС  в пункте В, которая в свою очередь имеет два канала связи с АТС в пункте А.  Требуется определить вероятность блокировки звонка абоненту С из пункта А. Поставим в соответствие рассматриваемой сети так называемый вероятностный граф (граф Ли), с вершинами А, В и С и ребрами a,b,c соответствующими потокам заявок. Будем называть их далее звеньями, и параметризовать значениями некоторых вероятностей  их занятия.

Рис. 2  Подключение абонента С с абонентом А через  АТС  в пункте В.

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

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

Обозначим вероятности занятия звеньев a,b,c соответственно.

Вероятности того, что звено свободно можно найти как

.

Вероятность блокировки пути АВ будет определяться как совместная вероятность занятости a и b:.

Вероятность свободности этого пути:.

Общая вероятность свободности пути АС будет

.

Тогда вероятность блокировки пути АС будет

.

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

Вероятность занятости (блокировки)

wi=1-qi

Вероятность свободности (неблокированности)

 qi=1-wi

Параллельное включение звеньев

 w=w1w2w i…wn

Последовательное включение звеньев

 q=q1q2qi…qn

Бывают случаи, когда граф сети не сводится к параллельно-последовательным схемам. Например, мостиковый граф (рис. 3)

Рис. 3  Мостиковый граф.

Для такого графа можно получить вероятность блокировки пути АВ в виде

.

Графы типа приведенных выше часто встречаются при анализе многозвенных коммутационных схем. Там они имеют более сложный вид, например как на рис. 4 и 5.

Рис. 4  Пример параллельно – последовательного графа.

Рис. 5  Пример параллельно – последовательного графа.

Для этих графов можно получить явные выражения для вероятности блокировки пути АВ

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



 

Другие похожие работы, которые могут вас заинтересовать.
18278. Исследование системы массового обслуживания 289.05 KB
  Теоретические аспекты теории массового обслуживания. Математическое моделирование систем массового обслуживания. Имитационное моделирование систем массового обслуживания. Перечень задач исследования операций. Исследование системы массового обслуживания.
6269. Модели систем массового обслуживания 45.43 KB
  Будущие состояния зависят от прошлого только через текущее состояние. Для непрерывный цепей Маркова основным также является уравнение Чепмена –Колмогорова, для однородной цепи имеющее вид:
21670. Теория систем массового обслуживания 185.18 KB
  Ширина полосы налета определяется возможностями обстрела всеми каналами любой цели в пределах полосы налета. Предполагается, что если самолет летит вне пределов полосы налета (слева или справа), тот эти самолеты не могут быть обстреляны ни одним из каналов данной системы ПВО.
6290. Анализ систем массового обслуживания с приоритетами 731.09 KB
  Основная модель расчета среднего времени ожидания. Дисциплины обслуживания с приоритетами зависящими от времени. Основная модель расчета среднего времени ожидания Будем использовать далее следующие обозначения для среднего значения времени ожидания в очереди требований из приоритетного класса p Wp и среднего времени пребывания в системе для требований этого класса Tp: . Первая составляющая времени ожидания для меченого требования связана с требованием которое оно застает в сервере.
6267. Анализ систем массового обслуживания с марковскими потоками требований 54.55 KB
  Система с несколькими серверами: M M m 2.Система обслуживания с m серверами явными потерями: M M m Loss 1. Система с несколькими серверами: M M m Рассмотрим сначала простой случай системы содержащей два сервера любой из которых доступен для поступающих на вход заявок. Системы с несколькими серверами такого типа называют полнодоступными.
17795. Организация ремонта и обслуживания сетей освещения на примере ЗАО Аграриос 164.87 KB
  Интенсивность фотосинтеза зависит от интенсивности света, содержания двуокиси углерода, обеспечения водой и температуры окружающей среды. Важным является не только количество световой энергии, но и спектральный состав света, а также соотношения периодов освещения и отсутствия света – т.н. фотопериодизм
10981. Лекции по теории и приложениям искусственных нейронных сетей 207.52 KB
  Среди магистральных путей развития данной отрасли эксперты издания выделили Компьютеры с высокой степенью параллелизма обработки информации которые могут разделить ту или иную задачу на части и обрабатывать их одновременно тем самым значительно сокращая общее время вычислений; Компьютеры в которых вместо электронных сигналов для передачи информации используется оптика. Оптические сигналы уже начали использоваться для передачи данных между компьютерами; Компьютеры с нейронными сетями представляющие собой машины работающие аналогично...
2486. ОБЩИЕ СВЕДЕНИЯ О ПОСТРОЕНИИ ГОСУДАРСТВЕННОЙ ГЕОДЕЗИЧЕСКОЙ СЕТИ, СЕТЕЙ СГУЩЕНИЯ И СЪЕМОЧНЫХ СЕТЕЙ 1.85 MB
  Основной принцип построения геодезической сети - от общего к частному. Он заключается в том, что вначале c высокой точностью определяется взаимное положение сравнительно небольшого числа пунктов, расположенных на большой территории. Затем, используя эти пункты, переходят к построению более густой сети меньшей точности.
13042. Основы теории информации 123.51 KB
  Потребности теории связи привели к развитию комплекса идей составивших в конечном счете теорию информации. Теория информации в ее современном виде это научная дисциплина изучающая способы передачи и хранения информации наиболее надежными и экономными методами. Однако являясь разделом математики и кибернетики теория информации используется для решения широкого круга задач в самых разных областях знания.
13040. ОСНОВЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ 176.32 KB
  Отголоски этого сохраняются и поныне что видно из примеров и задач приводимых во всех руководствах по теории вероятностей в том числе и в нашем. Они договариваются что тот кто первым выиграет шесть партий получит весь приз. Предположим что в силу внешних обстоятельств игра прекращается до того как один из игроков выиграл приз например один выиграл 5 а второй 3 партии. Однако правильный ответ в этом конкретном случае гласит что справедливым является раздел в отношении 7:1.
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.