Модели систем массового обслуживания. Классификация систем массового обслуживания - Коммуникации, связь, цифровые приборы и радиоэлектроника реферат

Главная

Коммуникации, связь, цифровые приборы и радиоэлектроника
Модели систем массового обслуживания. Классификация систем массового обслуживания

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
кафедра сетей и устройств телекоммуникаций
«Модели систем массового обслуживания. Классификация систем массового обслуживания»
Математическое введение в теорию цепей Маркова. ( Markov ' s chain )
Дискретные цепи Маркова . Будем говорить, что задана дискретная цепь Маркова, если для последовательн о сти случайных величин выполняется равенство .
Это означает, что поток случайных величин определяется только вероятностью перехода от предыдущего значения случайной величины к последующему. Зная н ачальное распределение вероятностей, можно найти распределение на любом шаге. Величины i n можно интерпретировать как номера состояний некоторой динамической системы с дискретным множеством состояний (типа конечного автомата). Если вероятности переходов не зависят от номера шага, то такая цепь Маркова называется однородной и ее определение задается набором вероятностей .
Для однородной Марковской цепи можно определить вероятности перехода из состояния i в состояние j за m шагов
Цепь Маркова называется неприводимой, если каждое ее состояние может быть достигнуто из любого другого состояния. Состояние i называется поглощающим, если для него p ii =1.
Состояние называется возвратным, если вероятность попадания в него за конечное число шагов равна единице. В другом случае состояние относится к невозвратным. Возвратное состояние может быть периодическим и апериодическим в зависимости от наличия кратных шагов возврата. Введем вероятности возврата в состояние i через n шагов после ухода из этого состояния:
Они позволяют определить среднее число шагов или, иначе говоря, среднее время возврата:.
Состояние называется возвратным нулевым , если среднее время возвращения в него равно бесконечности, и возвратным ненулевым , если это время конечно. Известны две важные теоремы:
Состояния неприводимой цепи Маркова либо все невозвратные, либо все возвратные нулевые, либо все возвратные ненулевые. В случае периодической цепи все состояния имеют один и тот же период.
Вторая теорема рассматривает вероятности достижения состояний в стационарном (то есть не зависящем от начального распределения вероятностей) режиме. Соответствующее распределение вероятностей также называют стационарным. Нахождение стационарного распределения вероятностей достижения состояний одна из основных задач теории телетрафика.
Для неприводимой и апериодической цепи Маркова всегда существуют предельные вероятности, не зависящие от начального распределения вероятностей. Более того, имеет место одна из следующих двух возможностей:
А) все состояния цепи невозвратные или все возвратные нулевые, и тогда все предельные вероятности равны нулю и стационарного состояния не существует;
Б) все состояния возвратные ненулевые и тогда существует стационарное распределение вероятностей:
Состояние называется эргодическим , если оно апериодично и возвратно ненулевое. Если все состояния цепи Маркова эргодичны , то вся цепь называется эргодич е ской . Предельные вероятности эргодической цепи Маркова называют вероятностями состояния равновесия, имея в виду, что зависимость от начального распределения вероятностей полностью отсутствует.
Цепь Маркова с конечным числом состояний (конечная цепь), удобно изображать в виде ориентированного графа, называемого диаграммой переходов. Вершины графа ассоциируются с состояниями, а ребра с вероятностями переходов.
Вычисления вероятностей достижения состояний производится прямыми методами или с помощью z-преобразования.
Введем матрицу вероятностей переходов и вектор-строку вероятностей на шаге n
Распределение вероятностей на произвольном шаге тогда будет подчиняться матричному соотношению:
Оно позволяет рекуррентно вычислять все вероятности состояний. Для нахождения предельного распределения (стационарного) нужно решить уравнение:
Его можно решать как систему линейных алгебраических уравнений, если цепь конечна.
и решение матричного уравнения сводится к решению системы трёх уравнений:
Коэффициенты первого уравнения в этой системе дополняют до единицы сумму коэффициентов второго и третьего уравнений; это свидетельствует о линейной зависимости между ними. Поэтому для решения системы уравнений нужно ввести дополнительное нормирующее условие. В данном примере: .
Решая систему полученных уравнений, имеем:
Уравнение для вероятности достижения состояния в переходном режиме решить значительно труднее. Некоторого упрощения можно достигнуть, используя z - преобразование. Применим его к уравнению для переходных вероятностей
Обозначая соответствующие преобразования, получим:
Все полученные здесь математические результаты относились к однородным Марковским процессам, где вероятности переходов не зависят от времени. В более общем случае такая зависимость имеет место.
Рассмотрим вероятности перехода системы из состояния i на m-том шаге в состояние j на n-том шаге для n > m.
Можно показать, что эти вероятности связаны между собой, так называемым уравнениями Чепмена-Колмогорова.(Chapman - Kolmogorov)
Для однородных цепей Маркова эти уравнения упрощаются так как
Случайный процесс X(t) с дискретным множеством значений образует непрерывную цепь Маркова, если
Будущие состояния зависят от прошлого только через текущее состояние. Для непрерывный цепей Маркова основным также является уравнение Чепмена -Колмогорова, для однородной цепи имеющее вид: .
Здесь матрица H (t) = [ p ij (t)] - матрица вероятностей перехода из состояния i в состояние j в момент времени t , а матрица Q называется матрицей интенсивностей переходов. Ее элементы имеют следующий смысл: если в момент времени t система находилась в состоянии E i , то вероятность перехода в течение промежутка времени (t,t+Дt) в произвольное состояние E j задается величиной q ij (t)Дt + o(Дt), а вероятность ухода из состояния E i величиной -q ii Дt + o(Дt).
Таким образом, интенсивности переходов можно вычислять как соответствующие пределы при стремлении к нулю длительности временного интервала.
Наиболее важным для дальнейшего использования является класс непрерывных цепей Маркова называемых «процессами гибели - размножения» ( Birth - death process ). Для таких систем из состояния k возможны переходы только в состояния k, k-1 и k+1 в следующие моменты времени:
в момент t объем популяции был равен k и в течение времени (t,t+Дt) не произошло изменения состояния
в момент t объем популяции был равен k-1 и в течение времени (t,t+Дt) родился один член популяции
в момент времени t объем популяции был равен k+1 и в течение времени (t,t+Дt) погиб один член популяции
Рис. 1. Возможные переходы в состояние Ек.
Будем искать вероятность того, что в момент времени t объем популяции равен k , обозначив его P k (t). Можно записать соотношения для вероятности достижения со-стояния k в момент времени t+Дt:
Определим граничные и нормирующие условия:
Выразим вероятности переходов за интервал Дt через интенсивности
Вер(+1)=л k Дt+o(Дt) ; Вер(-1)=м k Дt+o(Дt).
Вероятность нуля рождений 1- л k Дt+o(Дt) , а нуля гибелей 1- м k Дt+o(Дt).
Таким образом, вероятность того, что состояние k сохранится неизменным, будет равно произведению [1- л k Дt+o(Дt)][ 1- м k Дt+o(Дt)].
Тогда уравнения Чепмена-Колмогорова приобретают вид
Раскрывая скобки и проводя деление на Дt, получим:
В пределе получается система дифференциально-разностных уравнений, решение которой будут играть важную роль для практических задач.
В соответствие этой системе уравнений можно поставить наглядную диаграмму интенсивностей переходов, которая аналогична диаграмме переходов для дискретных цепей Маркова (Рис. 2)
Рис. 2 Диаграмма интенсивностей переходов для процесса размножения и гибели.
Овалам здесь соответствуют дискретные состояния, а стрелки определяют интенсивности потоков вероятности ( а не вероятности !) переходов от одного состояния к другому.
Имеет место своеобразный « закон сохранения »:
Разность между суммой интенсивностей, с которой система попадает в состо я ние k и суммой интенсивностей, с которой система покидает это состояние дол ж на равняться интенсивности изменения потока в это состояние (производной по вр е мени).
Применение закона сохранения позволяет получать уравнения для любой по дсистемы Марковской цепи типа процесса «гибели-размножения». Особенно эффективным оказывается построение решений в стационарном, установившемся режиме, когда можно полагать что вероятности в произвольный, достаточно отдаленный момент времени, остаются постоянными.
Приравнивая производную по времени нулю, получаем систему разностных уравнений
Полагая, что интенсивности л -1 =л -2 = л -3 =…0; м 0 = м -1 = м -2 = м -3 =…=0, второе уравнение выписывать отдельно далее не потребуется. Итак, стационарный режим в цепи Маркова будет описываться системой разностных уравнений и условием нормировки для вероятностей
Нетрудно видеть, что эти уравнения легко выводятся из закона сохранения интенсивностей вероятностей. В стационарном режиме разность потоков равна нулю и полученные выше уравнения приобретают смысл уравнений равновесия или баланса, как их и называют.
Интенсивность потока вероятностей в состояние k равна интенсивности потока из этого состояния.
Решать уравнение баланса можно, сначала определив при k =0 значение
Затем, построив систему уравнений для k =1, можно получить .
Система, описываемая полученными выше выражениями, будет иметь стационарные вероятности состояний, когда она эргодическая. Это условие может быть выражено через соотношение интенсивностей. Необходимо и достаточно, чтобы существовало некоторое значение k , начиная с которого выполнялось неравенство
Для большинства реальных систем массового обслуживания это неравенство выполняется.
Классификация систем массового обслуживания.
Используется трех -, четырех -, шести - компонентное символическое обозначение системы массового обслуживания, предложенное Кендаллом (Candall) и развитое в работах Г.П.Барашина.
a - распределение поступающего потока запросов.
b - закон распределения времени обслуживания.
М - экспоненциальное (Марковское) распределение,
D - детерминированное распределение,
E k - эрланговское распределение k-го порядка,
HE k - гиперэрланговское распределение порядка k,
GI - произвольное распределение независимых промежутков между заявками,
G - произвольное распределение длительностей обслуживания.
c - структура системы обслуживания (обычно число серверов).
d - дисциплина обслуживания (параметры после двоеточия иногда опускают).
Обычно используется сокращенное символическое обозначение, например FF вместо FIFO, LF, PR и т.п.
e - максимальное число запросов, воспринимаемое системой, может употребляться символ .
f - максимальное число запросов к системе обслуживания.
В некоторых публикациях последними символами отражают качественные характеристики системы обслуживания. Некоторые общие результаты и основы математического аппарата, необходимого для анализа можно получить, рассматривая системы G/G/m.
Рассмотрим временную диаграмму работы системы массового обслуживания (рис. 3), отразив на ней последовательность поступления требований, помещение требований в очередь и обработки серверами системы.
Временная диаграмма работы системы массового обслуживания.
В общем случае ясно, что с увеличением числа требований растет время ожидания. Установим соотношение между средним числом требований в системе, интенсивностью потока и среднего времени пребывания в системе. Обозначим число поступающих в промежутке времени (0 , t ) требований как функцию времени б ( t ).
Число исходящих из системы заявок (обслуженных) на этом интервале обозначим д(t). На рисунке 4 показаны примеры функциональных зависимостей этих двух случайных процессов от времени.
Рис. 4 Зависимость между средним числом требований в системе, интенсивностью потока и средним времени пребывания в системе.
Число требований, находящихся в системе в момент t будет равно:
Площадь между двумя рассматриваемыми кривыми от 0 до t - дает общее время, проведенное всеми заявками в системе за время t.
Обозначим эту накопленную величину г(t) . Если интенсивность входного потока равна л, а средняя интенсивность за время t: ,то время, проведенное одной заявкой в системе, усредненное по всем заявкам будет равно:
Наконец, определим среднее число требований в системе в промежутке (0,t): .
Из последних трех уравнений следует, что: , (где ).
Если в СМО существует стационарный режим, то при t> ? , будут иметь место соотношения:
Последнее соотношение означает, что среднее число заявок в системе равно произведению интенсивности поступления требований в систему на среднее время пребывания в системе. При этом не накладывается никаких ограничений на распределения входного потока и времени обслуживания. Впервые доказательство этого факта дал Дж.Литтл и это соотношение носит название формула Литтла.
Интересно, что в качестве СМО можно рассмотреть только очередь из заявок в буфере. Тогда формула Литтла приобретает иной смысл - средняя длина очереди равна произведению интенсивности входного потока заявок на среднее время ожидания в очереди: .
Если наоборот рассматривать СМО только как серверы, то формула Литтла дает:
где - среднее число заявок в серверах, а - среднее время обработки в сервере.
Одним из основных параметров, которые используются при описании СМО, является коэффициент использования ( utilization factor ) . Это фундаментальный параметр, так как он определяется как отношение интенсивности входного потока к пропускной способности системы. Поскольку пропускная способность СМО содержащей m серверов может быть определена как: , то коэффициент использования может быть определен как:
Нетрудно видеть, что коэффициент использования равен в точности интенсивности нагрузки, если СМО с одним сервером и в m раз меньше для систем с m серверами. Величина коэффициента использования равна среднему значению от доли занятых серверов и .
Если в СМО типа G/G/1 существует стационарный режим и можно определить вероятность того, что в некоторый случайный момент сервер будет свободный, то
Л.Н. Волков, М.С. Немировский, Ю.С. Шинаков. Системы цифровой радиосвязи: базовые методы и характеристики. Учебное пособие.-М.: Эко-трендз, 2005.
М.В. Гаранин, В.И. Журавлев, С.В. Кунегин. Системы и сети передачи информации. - М.: Радио и связь, 2001.
Передача дискретных сообщений./Под ред. В.П. Шувалова. - М.: Радио и связь, 1990.
Основы передачи дискретных сообщений./Под ред. В.М. Пушкина. - М.: Радио и связь, 1992.
Н.В. Захарченко, П.Я. Нудельман, В.Г. Кононович. Основы передачи дискретных сообщений. -М.: Радио и связь, 1990.
Цепь Маркова и Марковские процессы. Сеть массового обслуживания. Мультипликативность стационарного распределения в открытых сетях с многорежимными стратегиями обслуживания. Анализ изолированного узла. Стационарное распределение сети. Обслуживание заявок. курсовая работа [200,1 K], добавлен 08.01.2014
Определение нагрузки, поступающей на станцию системы массового обслуживания. Определение необходимого числа каналов для полнодоступной системы при требуемом уровне потерь. Моделирование в среде GPSS World СМО с потерями от требуемого числа каналов. курсовая работа [972,3 K], добавлен 15.02.2016
Устройство и принцип действия открытых систем сети массового обслуживания с простейшим входящим потоком. Понятие квазиобратимости. Сети с переключением режимов при определенном количестве заявок в узле. Примеры открытых сетей с переключением режимов. курсовая работа [286,6 K], добавлен 21.02.2010
Методика построения программной модели. Обобщенная структурная схема ВС. Моделирование работы абонента и работы буферной памяти. Разработка программы сбора статистики и управляющей программы имитационной модели. Методика реализации событийной модели. курс лекций [190,1 K], добавлен 24.06.2009
Характеристика замкнутых сетей массового обслуживания с экспоненциальным обслуживанием в узлах и марковской маршрутизацией. Примеры замкнутых сетей с переключением режимов. Условия мультипликативности стационарного распределения состояний замкнутой сети. курсовая работа [199,4 K], добавлен 21.02.2010
Общая классификация систем и сетей радиодоступа. Классификация систем радиодоступа по параметрам и характеристикам радиоинтерфейса. Системы с аналоговой и цифровой передачей. Услуги цифровой передачи речи. Классификация по решаемым прикладным задачам. реферат [49,3 K], добавлен 06.10.2010
Аналитическое исследование сетей массового обслуживания с помощью стационарного (инвариантного) распределения вероятностей состояний, его зависимость от вида функций распределения времени обслуживания. Постановка задачи, составление уравнения уравновесия. курсовая работа [165,0 K], добавлен 18.09.2009
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Модели систем массового обслуживания. Классификация систем массового обслуживания реферат. Коммуникации, связь, цифровые приборы и радиоэлектроника.
Курсовая работа: Инфляция в России и за рубежом
Список Аргументов К Итоговому Сочинению 2022
Примерный План Курсовой Работы
Контрольная работа по теме Ряды распределения: виды, графическое изображение, формы распределения
Курсовая Работа На Тему Рак Молочной Железы
Реферат: Дельвиг Антон Антонович. Скачать бесплатно и без регистрации
Хуй Защитил Диссертацию
Всемирная Организация Здравоохранения Реферат
Дневник Практики Заполненный Детский Сад
Фразеологизмы В Текстах Сми Курсовая
Философия И Культура Эпохи Возрождения Реферат
Сочинение Про Словосочетание 8
Как Делать Доклад Дипломной Работы
Следственная Практика Отчет
Курсовая работа по теме Поисково-разведочные работы. Восточные Саяны
Где Заказать Курсовую Работу
Можно Ли Победить Бездуховность Сочинение
Карьерный План Эссе
Курсовая работа по теме Внешняя разведка как важнейший элемент государственного механизма и системы обеспечения национальной безопасности
Доклад: Академик Б.Патон
Образование Русского централизованного государства - Государство и право курсовая работа
Защита права собственности - Государство и право контрольная работа
Телевизионный бизнес - Журналистика, издательское дело и СМИ реферат