Моделирование канала связи с контролем конфликтов одновременности

Моделирование канала связи с контролем конфликтов одновременности

Содержание

1. Имитационное моделирование системы массового обслуживания

.1 Анализ динамики функционирования СМО

.2 Формализация модели СМО средствами GPSS World

.3 Имитационное моделирование СМО в среде GPSS World

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

.1 Формализация модели СМО для задач анализа и оптимизации

.2 Модификация имитационной модели 

.3 Реализация модельных экспериментов и анализ результатов 

Выводы

Литература

1. Имитационное моделирование системы массового обслуживания

.1 Анализ динамики функционирования СМО

Целью данного курсового проекта является моделирование и анализ канала связи с контролем конфликтов одновременности. Структурная схема заданной СМО приведена на рисунке 1.

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

На схеме (см. рисунок 1) представлены следующие устройства:

NAK- входной буфер, в котором может размещаться только 1 пакет;

S1- Sn-устройства канала в которых обрабатываются пакеты (n-количество устройств позволяющее передавать параллельно любое количество пакетов).

На схеме обозначен выход пакетов из системы:

V1- вывод из системы обработанных пакетов.

V2- вывод пакетов, которые не были обработаны.

На вход системы поступают пакеты переменной длины трех типов.

Вероятности поступления пакетов каждого типа составляют: 1 - 0.3; 2 - 0.32; 3 - 0.38. Пакеты передаются по каналу связи. Канал связи может параллельно передавать любое количество пакетов, но между передачами, то есть с момента передачи одного пакета до начала передачи другого пакета, должен иметь место перерыв не менее минимально допустимого интервала для данной пары пакетов с учетом типа. Если это ограничение не выполняется - имеет место конфликт одновременности. Минимально допустимый интервал для всех по-парных возможных сочетаний типов пакетов приведен в таблице 1.

Таблица 1 - Интервалы времени задержек минимально допустимых для каждой пары типов

Конфликт одновременности разрешается задержкой начала передачи конфликтного пакета на 1±0.2 сек. Если после первой задержки конфликт не устраняется -задержка передачи повторяется по тому же правилу необходимое число раз. Время передачи пакета по каналу зависит от его размера, и распределено по заданному закону.

Характеристики объектов СМО представлены в таблице 2.

Таблица 2 -Интенсивности и законы распределения времени поступления передачи и размеров пакетов в СМО

Примечания: * - четная величина. ** - в расчет на 1 бит.

Выполним классификацию устройств заданной СМО.

Классификационное обозначение СМО имеет вид A/B/C/D/E, где буквенные позиции имеют следующий смысл:

A  - обозначение закона распределения времени поступления заявок входного потока (обозначение М соответствует экспоненциальному закону распределения, Г - гамма-распределению, N - нормальному распределению, R - равномерному распределению, D - постоянному времени обслуживания, G - произвольному или неизвестному закону распределения, Gr - групповому (пакетному) поступлению заявок на обслуживание);

B       - обозначение закона распределения времени обслуживания в устройствах (используются те же обозначения, что и для распределения времени поступления заявок);         - число обслуживающих приборов (для одноканальной СМО равно 1, для многоканальной - числу каналов); - число мест в очереди (для неограниченных очередей данное обозначение опускается);   - дисциплина обслуживания (для дисциплины FIFO данное обозначение опускается, также используются обозначения LIFO и RANDOM).

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

Заданный канал передачи пакетов является неоднородным, все его устройства обладают одинаковым законом распределения (экспоненциальным) но типы пакетов разные. От размера пакета зависит время его обработки. Классификационное обозначение заданной СМО:G/M/11 (Примечание - тип распределения времени поступления заявок на вход устройств не определен, так как заявки поступают на входы этих устройств с разными интенсивностями и задержками из-за конфликтов).

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

Пакеты, сгенерированные по экспоненциальному закону (l=0.25) поступают в систему. Типы пакетов задаются функцией распределения пакетов по типам: 1 - 0.3; 2 - 0.32; 3 - 0.38.Размер пакетов задается функцией по равномерному закону распределения. Пакеты поступают в буфер канала, в буфере может находиться только 1 пакет; если буфер занят очередной пакет теряется. Запускается отсчет времени, это не обходимо для определения перерыва между передачами. Выполняются проверки на превышение ограничения для каждой пары пакетов. Если это ограничение не выполняется - имеет место конфликт одновременности. Он разрешается задержкой конфликтного пакета на 1±0.2 секунды (задержка будет повторяться необходимое число раз). Из буфера пакет передается к одному из свободных устройств канала. Нахождение пакета в устройстве зависит от его размера. После обработки пакет поступает на выход.

Таким образом, возможные варианты прохождения пакетом СМО:

-   пакет входит в буфер обрабатывается без ожидания и выходит;

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

-   пакет не входит в буфер (из-за занятости) и удаляется из системы.

.2 Формализация модели СМО средствами GPSS

имитационный модель gpss формализация cmo

В качестве программного обеспечения моделирования заданием на курсовое проектирование задана среда GPSS World, предназначенная для имитационного вероятностного моделирования систем с дискретными и непрерывными процессами. Для моделирования в GPSS World используются динамические и статические объекты. Динамическими объектами являются заявки, которые создаются в определенных точках модели, продвигаются планировщиком через операторы, а затем уничтожаются. С каждой заявкой связаны параметры, номера или имена которых используются для ссылок на значения, присвоенные параметрам. Заявкам может присваиваться приоритет. Приоритет определяет предпочтение, которое получает заявка, когда она и другие заявки претендуют на один и тот же ресурс. Статические объекты в GPSS World представлены объектами операционной, аппаратной, вычислительной, статистической, запоминающей и группирующей категорий. Каждому объекту соответствуют атрибуты, описывающие его состояние в данный момент времени. Они доступны для использования в процессе моделирования и называются стандартными числовыми атрибутами (СЧА). Исходя из задания на курсовое проектирование с использованием имитационного моделирования в среде GPSS World, необходимо смоделировать канал связи с контролем конфликтов одновременности, построить гистограммы времени пребывания сообщений каждого типа, а также определить следующие характеристики функционирования СМО:

. Среднее время пакетов каждого типа в системе;

. Среднеквадратическое отклонение времени пребывания пакетов каждого типа в системе;

. Среднеквадратическое отклонение времени пребывания пакетов в буфере;

. Коэффициент использования буфера;

. Среднее время пребывания пакета в буфере;

. Коэффициент использования канала;

. Вероятность возникновения конфликта одновременности;

. Вероятность потери пакета из-за занятости буфера.

Характеристики функционирования 1. - 5.являются первичными параметрами имитационного моделирования в среде GPSS World, то есть представляют собой СЧА и определяются автоматически встроенными средствами GPSS.

Характеристика первичных параметров моделирования канала связи с конфликтом одновременности приведена в таблице 3.

Характеристики функционирования 6. -8. являются вторичными параметрами. Их оценка с использованием GPSS World может быть осуществлена с использованием первичных параметров программно или расчетно, по результатам статистического моделирования.

Таблица 3 - Первичные параметры моделирования

Вторичными параметрами, подлежащими определению программно или расчетно через первичные параметры (СЧА), согласно заданию на имитационное моделирование канала связи с контролем конфликтов одновременности являются следующие характеристики функционирования:

-  коэффициент использования канала;

-  вероятность возникновения конфликта одновременности

-  вероятность потери пакета из-за занятости буфера.

Введем формулы расчета вторичных параметров моделирования.

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

Коэффициент использования канала равен:

 (1)

где - коэффициент использования канала;_мод - время моделирования;_{простоя}- время простоя канала.

Согласно теории вероятностей, если некоторое случайное событие А наступает как следствие какого-либо из n_А событий при общем числе n возможных событий (несовместимых и равновероятных), то вероятностью события А называют число

.

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

Вероятность возникновения конфликта одновременности равна числу конфликтов к общему числу проверок:

                                                            2

где Р _{конфликта} - вероятность возникновения конфликта;

N_{конфликтов} - количество конфликтов, возникших за время моделирования;_{пр_пакетов}- общее количество проверок.

Вероятность потери пакета из-за занятости буфера равна числу потерянных пакетов к общему числу пакетов прошедших через буфер:

                                                            3

где Р_потерь - вероятность потери пакета из-за занятости буфера;

N_{потер_пакетов}- количество пакетов, которое было потеряно из-за занятости буфера;_{пакетов}- общее количество пакетов, которые вошли в СМО.

.3 Имитационное моделирование СМО в среде GPSS World

Рассмотрим принципиальные особенности реализации имитационной вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World.

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

Таблица 4 - Сохраняемые ячейки программной реализации

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

-  размеру пакета;

-   типу пакета;

-   абсолютное время моделирования (время вхождения в канал; время вхождения в буфер).

Для идентификации каждого пакета по этим трем признакам в программной реализации было использовано сохранение значений в параметры пакета. Характеристика используемых параметров приведена в таблице 5.

Таблица 5 - Сохраняемые параметры пакетов

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

Характеристика булевых переменных приведена в таблице 6.

Таблица 6 - Булевы переменные

Кроме этого, в программной реализации имитационной вероятностной модели СМО с контролем конфликтов одновременности имеются следующие особенности:

-  для сбора данных о времени пребывания пакетов каждого типа в СМО использованы статистические таблицы с именами Tab1,Tab2 и Tab3 соответственно;

-   для сбора данных о времени пребывания пакетов в буфере использована статистическая таблица с именем TBUF;

-   для задания типов пакетов использована дискретная функция распределения вероятностей с именами tipe, реализованная в соответствии с исходными данными о вероятностях поступления пакетов каждого типа во входном потоке;

-   для задания размеров пакетов использована дискретная функция распределения вероятностей с именами size, реализованная в соответствии с исходными данными о законе распределения пакетов каждого размера во входном потоке;

-   для моделирования буфера, ограниченного по количеству мест, использован накопитель с именем NAK;

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

Листинг программной реализации имитационной вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World имеет следующий вид.

ЗАДАНИЕ ТАБЛИЦ:TABLEM1,0,15,15 ;таблица для 1-го типа по времени пребывания пакетов в системеTABLEM1,0,15,18 ;таблица для 2-го типа по времени пребывания пакетов в системеTABLEM1,0,15,15 ;таблица для 3-го типа по времени пребывания пакетов в системе,0,0.2,40 ;таблица для определения среднего времени нахождения в буфере

ЗАДАНИЕ ФУНКЦИЙ:

функция распределения вероятности по 3-ем типам

.3,1/0.62,2/1,3 ;вероятности каждого типаFUNCTIONR N2,D9  ;функция генерации размера пакета

,12/0.125,14/0.250,16/0.375,18/0.5,20/0.625,22/0.75,24/0.875,26/1,28 ;значения вероятностей

ЗАДАНИЕ БУЛЕВЫХ ПЕРЕМКННЫХ И СОХРАНЯЕМЫХ ЯЧЕЕКBVARIABLEP11' ;булева функция проверяет равенство 11 параметра заявки 1-му типуBVARIABLEP11'E'2; булева функция проверяет равенство 11 параметра заявки 2-му типуBVARIABLEP11'E'3; булева функция проверяет равенство 11 параметра заявки 3-му типуBVARIABLEF1'OR'F2'OR'F3'OR'F4'OR'F5'OR'F6'OR'F7'OR'F8'OR'F9'OR'F10'OR'F11 ;булева функция проверки на занятость всех устройств, если занято хоть одно устройство то равна 1 иначе 0,0 ;ячейка хранит время входа в канал предыдущего пакета,0 ;ячейка хранит время входа в буфер текущего пакета,0 ;ячейка хранит тип предыдущего пакета,0 ;ячейка хранит тип текущего пакета,0 ;ячейка хранит разность между входом в канал предыдущего пакета и входом в буфер текущего,0 ;ячейка хранит время входа в буфер активного пакета,0 ;ячейка хранит общее время простоя канала,0 ;ячейка хранит время завершения простоя канала,0 ;ячейка хранит время начала простоя канала

БЛОК ГЕНЕРАЦИИ ЗАВОК:1 ;буфер для хранения 1 пакета(Exponential(1,0,4)) ;эксплненциальный закон распределения генерации пакетов10,(FN$size); запись типа в 10-ый параметр заявки11,(FN$tipe); запись размера в 11-ый параметр заявки,OUT; если буфер занят, то заявка удаляется из системы; помещение заявки в буфер15; запись в 15 параметр заявки значения времени входа в буфер40,P15; запись в ячейку 32 времени вхождения в буфер,0,STEP1; если значение ячейки Х34 не равно нулю, то заявка отправится в блок проверок,STEP2; иначе заявка отправится в канал без проверок на задержку, т.к. она первая в системе

БЛОК ПРОВЕРКИ:MARK 12; записываем в параметр 12 активной заявки значение времени перед проверкой32,P12; запись в ячейку 32 значения времени35,P11; запись в ячейку 35 значения типа активной заявки37,(X32-X31); запись в ячейку 37 значения разности времени между входом в канал предыдущего пакета и входом в буфер текущего$PROV1,0,T1; определение типа активного пакета$PROV2,0,T2; определение типа активного пакета$PROV3,0,T3; определение типа активного пакетаTESTEX34,1,MET12; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета),3.5,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 1 1 при недостатке конфликт,STEP2; иначе передаем пакет в канал связиTESTEX34,2,MET13; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета)                         ,4.2,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 1 2 при недостатке конфликт,STEP2; иначе передаем пакет в канал связиTESTGEX37,3.8,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 1 3 при недостатке конфликт,STEP2; иначе передаем пакет в канал связиTESTEX34,1,MET22; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета),5,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 2 1 при недостатке конфликт,STEP2; иначе передаем пакет в канал связиTESTEX34,2,MET23; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета),4,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 2 2 при недостатке конфликт,STEP2; иначе передаем пакет в канал связиTESTGEX37,4.8,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 2 3 при недостатке конфликт,STEP2; иначе передаем пакет в канал связиTESTEX34,1,MET32; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета),5.7,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 3 1 при недостатке конфликт,STEP2; иначе передаем пакет в канал связиTESTEX34,2,MET33; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета),4,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 3 2 при недостатке конфликт,STEP2; иначе передаем пакет в канал связиTESTGEX37,5.5,CONFLICT   ;сравнение времени обслуживания с заданным для каждой пары типов 3 3 при недостатке конфликт,STEP2; иначе передаем пакет в канал связи

БЛОК КАНАЛАMARK 12; запись в параметр 12 активного пакета значения времени вхождения в канал34,P11; запись в ячейку 34 значения типа пакета31,P12; запись в ячейку 31 значения времени начала обработки пакета9,1$PROV5,0,MET1; проверка, свободен ли канал52,P12; если канал свободен записываем в ячейку 52 время завершения простоя канала51+,(X52-X53); запись в ячейку 51 значения разности времени конца и начала простоя канала,MET19+,1; если устройство было занято то проверка следующего,MET1GATENUP9,INC; проверка свободно ли устройствоPiP9; проверка свободно ли устройство; выход пакета из буфера15; присвоение 15 параметру заявки значения времени, когда пакет вышел из буфера16,(P15-X40); присвоение 16 параметру пакета значения разности времени между входом активного пакета в буфер и выходом из буфера(Exponential(1,0,P10)) ;реализация экспоненциального закона для обработки заявки в зависимости от размераP9; освобождение уст-ва,STEP3; перехд к выходной очереди

БЛОК КОНФЛИКТА:1,0.2 ;задержка пакета,STEP1; возвращение пакета после задержки

БЛОК ВЫХОДАTESTEBV$PROV5,0,MET2; провекрка при выходе пакета из канала все устройства свободны53,P12; если да записываем время начала простоя канала в ячейку 53,MET2; возвращение пакета в системуTABULATETBUF; оператор занесения в таблицу для определения времени нахождения в буфере$PROV1,0,PT1; определение типа активного пакета: сравниваем значение 11 параметра пакета с возможными значениями типов$PROV2,0,PT2; сравниваем значение 11 параметра пакета с возможными значениями типов$PROV3,0,PT3; сравниваем значение 11 параметра пакета с возможными значениями типовTABULATE Tab1; оператор занесения в таблицу для типа 1,QUIT; выход пакета из статистического анализаTABULATE Tab2; оператор занесения в таблицу для типа 2,QUIT; выход пакета из статистического анализаTABULATE Tab3; оператор занесения в таблицу для типа 3,QUIT; выход пакета из статистического анализа, OUT_OK;выход из системы обработанного пакета_OKTERMINATE 1; выход из системы обработанного пакета; удаление пакета из системы

Результаты эксперимента по моделированию процесса обслуживания пакетов в заданной СМО с контролем конфликтов одновременности, время моделирования для которой равно 309640 секунд, были получены в виде полного стандартного отчета GPSS World Simulation Report, приведенного ниже.

. Общая информация о результатах работы модели:TIME END TIME BLOCKS FACILITIES STORAGES

.0       309640.750 76 11 1

. Информация о блоках:LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

. GENERATE 77417 0 0

. ASSIGN 77417 0 0

. ASSIGN 77417 0 0

. GATE 77417 0 0

. ENTER 50003 0 0

. MARK 50003 0 0

. SAVEVALUE 50003 0 0

. TEST 50003 0 0

. TRANSFER 1 0 010. MARK 160331 0 0

. SAVEVALUE 160331 0 0

. SAVEVALUE 160331 0 0

. SAVEVALUE 160331 0 0

. TEST 160331 0 0

. TEST 119915 0 0

. TEST 67985 0 017. TEST 40416 0 0

. TEST 10976 0 0

. TRANSFER 4475 0 020. TEST 29440 0 0

. TEST 14135 0 0

. TRANSFER 4788 0 023. TEST 15305 0 0

. TRANSFER 5770 0 025. TEST 51930 0 0

. TEST 17271 0 0

. TRANSFER 4921 0 028. TEST 34659 0 0

. TEST 14078 0 0

. TRANSFER 5084 0 031. TEST 20581 0 0

. TRANSFER 6037 0 033. TEST 67985 0 0

. TEST 22786 0 0

. TRANSFER 5636 0 036. TEST 45199 0 0

. TEST 17364 0 0

. TRANSFER 6171 0 039. TEST 27835 0 0

. TRANSFER 7119 0 041. MARK 50002 0 0

. SAVEVALUE 50002 0 0

. SAVEVALUE 50002 0 0

. ASSIGN 50002 0 0

. TEST 50002 0 0

. SAVEVALUE 1121 0 0

. SAVEVALUE 1121 0 0

. TRANSFER 1121 0 049. ASSIGN 93311 0 0

. TRANSFER 93311 0 051. GATE 143313 0 0

. SEIZE 50002 0 0

. LEAVE 50002 0 0

. MARK 50002 0 0

. ASSIGN 50002 0 0

. ADVANCE 50002 2 0

. RELEASE 50000 0 0

. TRANSFER 50000 0 059. ADVANCE 110330 1 0

. TRANSFER 110329 0 061. TEST 50000 0 0

. SAVEVALUE 1120 0 0

. TRANSFER 1120 0 064. TABULATE 50000 0 0

. TEST 50000 0 0

. TEST 34968 0 0

. TEST 18926 0 068. TABULATE 15032 0 0

. TRANSFER 15032 0 070. TABULATE 16042 0 0

. TRANSFER 16042 0 072. TABULATE 18926 0 0

. TRANSFER 18926 0 074. TRANSFER 50000 0 0_OK 75. TERMINATE 50000 0 076. TERMINATE 27414 0 0

. Информация об объектах типа «устройство»:ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

. 12583 0.846 20.807 1 77407 0 0 0 0

. 11488 0.773 20.844 1 77412 0 0 0 0

. 9859 0.662 20.780 1 0 0 0 0 0

. 7514 0.512 21.118 1 0 0 0 0 0

. 4834 0.339 21.709 1 0 0 0 0 0

. 2472 0.168 21.086 1 0 0 0 0 0

. 952 0.063 20.594 1 0 0 0 0 0

. 255 0.018 21.922 1 0 0 0 0 0

. 36 0.002 20.869 1 0 0 0 0 0

. 8 0.000 15.767 1 0 0 0 0 0

. 1 0.000 19.777 1 0 0 0 0 0

. Информация об ограниченной очереди:CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY1 0 0 1 50003 1 0.356 0.356 0 0

. Информация о сохраняемых величинах (ячейках):RETRY VALUE

0 309636.979

0 309640.741

0 1.000

0 2.000

0 3.762

0 309637.999

0 20893.893

0 308971.151

0 308954.534

Определение характеристик времени пребывания пакетов каждого типа в СМО с контролем конфликтов одновременности включает в себя построение гистограмм времени пребывания, определение среднего времени пребывания и среднеквадратического отклонения времени пребывания.

Гистограмма времени пребывания пакетов типа 1,2 и 3 в СМО с контролем конфликтов одновременности, полученная путем табулирования времени пребывания пакетов за время моделирования с использованием статистических таблиц Tab1,Tab2 и Tab3приведена на рисунках2 - 4 соответственно. Больше 40% пакетов всех типов обслужены меньше чем за 15 секунд - это пакеты маленьких размеров, которые прошли буфер без задержки или с наименьшим числом конфликтов.

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

Фрагмент стандартного отчета GPSS World Simulation ReportMEAN STD.DEV. RANGE RETRY FREQUENCY CUM.%22.449 21.641

Рисунок 2 - Гистограмма времени пребывания в СМО пакетов типа 1

Фрагмент стандартного отчета GPSS World Simulation Report TAB2 23.521 22.517

Рисунок 3 - Гистограмма времени пребывания в СМО пакетов типа 2

Фрагмент стандартного отчета GPSS World Simulation Report TAB3 23.433 21.851

Рисунок 4 - Гистограмма времени пребывания в СМО пакетов типа 3

Результаты анализа гистограмм, представленных на рисунках 2-4, занесены в таблицу 7.

Таблица 7 - Результаты анализа гистограмм времен пребывания пакетов в СМО

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

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

Фрагмент стандартного отчета GPSS World Simulation Report TBUF 2.207 1.918

Рисунок 5 - Гистограмма времени пребывания пакетов в буфере

Из анализа данных, представленных на рисунке 5, следует, что среднее время ожидания пакета в буфере составляет 2.207 секунды (выводится в графе MEAN статистической таблицы), а среднеквадратическое отклонение времени ожидания - 1.918 секунды (выводится в графе STD.DEV. статистической таблицы). При этом только 32.41% заявок (16205 из числа вошедших в буфер) будут обслужены без ожидания. Такая форма гистограммы обусловлена характером процесса решения конфликта одновременности, который задерживает пакет в буфере.

Результаты анализа функционирования накопителя, занесены в таблицу 9.

Таблица 9 -Результаты анализа функционирования накопителя

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

Коэффициент использования канала , рассчитан по формуле (1), составляет:

Где =309640.750, общее время моделирования (источник данных: графа стандартного отчета END TIME);

=20893.893, время простоя канала (источник данных: графа стандартного отчета 51блока SAVEVALUE).

Вероятность возникновения конфликта одновременности P_{конфликта}, рассчитанная по формуле (2), составляет:

Где =110330,общее количество конфликтов, равно количеству срабатываний оператора задержки пакетов для решения конфликта одновременности;

=160331, количество пакетов, которые проходили проверку на возможность конфликта, равно количеству пакетов, направленных к меткеSTEP1.

Вероятность потери пакета из-за занятости буфера P_потерь, рассчитанная по формуле (3), составляет:

Где =27414,общее количество потерянных пакетов, равно количеству срабатываний оператора выхода необработанных пакетов;

=50000, количество пакетов, сгенерированных за время моделирования.

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

Таблица 10 -Результаты анализа вторичных параметров СМО

2 Анализ и оптимизация системы массового обслуживания

.1 Формализация модели СМО для задач анализа и оптимизации

В качестве дополнительных задач анализа и оптимизации функционирования СМО с контролем конфликтов одновременности заданием на курсовое проектирование определены следующие задачи:

1) построить гистограмму распределения суммарного времени задержки передачи пакетов в процессе решения конфликтов одновременности;

) определить вероятность возникновения конфликта одновременности для пары пакетов каждого типа;

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

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

  (4)

где Р* _{конфликта} - вероятность возникновения конфликта для пары типов;

N*_{конфликтов} - количество конфликтов, возникших за время моделирования для пары типов;*_{пр_пакетов}- общее количество проверок для пары типов.

Проверкой правильности решения второй задачи анализа является расчет общей суммы проверок для каждой пары типов и расчет суммы конфликтов для каждой пары типов. Эта сумма очевидно должна быть равна общему количеству проверок и общему количеству конфликтов. Общее количество конфликтов, равно количеству срабатываний оператора задержки пакетов для решения конфликта одновременности. Количество пакетов, которые проходили проверку на возможность конфликта, равно количеству пакетов, направленных к меткеSTEP1 и вошедших в оператор.

.2 Модификация имитационной модели

Рассмотрим принципиальные особенности модификаций исходной имитационной вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World, реализованных для решения задач анализа и оптимизации.

При решении первой задачи анализа для сбора данных о суммарном времени задержки передачи пакетов в процессе разрешения конфликтов одновременности использованы статистическая таблица с именемTime. Введение новых таблиц потребовало модификации для задания таблицы программной реализации вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World, а также реализации регистрации времени задержки пакета в процессе разрешения конфликта одновременности. Реализации дополнительной идентификации пакетов по флагу конфликта для проверки условий входа пакетов в оператор табулирования времени, для того чтобы выводить статистику только для тех пакетов которые задерживались из-за конфликта одновременности.

Модифицированные фрагменты имитационной вероятностной модели СМО с контролем конфликтов одновременности и описание их функционирования, использованные для решения первой задачи анализа, в среде GPSS World:

.        Объявление таблицы, где будем табулировать 25 параметр пакета (блок задания таблиц):TABLE (P25),0,0.2,40         ;таблица для времени задержек пакетов во время решения конфликта

.        В блоке входа в систему присвоение каждому пакету (параметр 20) после входа в систему флаг конфликта 0 (0 - неконфликтный пакет, 1 - конфликтный):20,0 ;присвоение 20 параметру пакета 0 (флаг конфликта)

.        После выхода пакета из буфера и входа в канал (блок входа в канал) - проверка (по 20 параметру пакета), был ли пакет конфликтным, если да заносим значение времени задержки в таблицу:

TESTEP20,1,STR8; проверка если пакет конфликтныйTime; занесение результатов в таблицу

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

TESTEP20,0,MET5 ;проверка флага конфликта если 0 конфликтный пакет пришел 1-й раз20,1; флаг переводим в 1MARK 28; начало отсчета задержки1,0.2; задержка пакета29; конец отсчета25+,(P29-P28); разность = задержки

TRANSFER ,STEP1; возвращение пакета после задержки

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

Таблица 11- Булевы переменные модификации модели, реализованной для решения второй задачи анализа

Для сохранения количества проверок и количества пакетов для каждой пары типов, были использованы сохраняемые ячейки GPSS. Также вычисление и запись значения вероятностей возникновения конфликтов одновременности для каждой пары пакетов производился в ячейки. Характеристика использованных сохраняемых ячеек GPSS приведена в таблице 12 (начальное значение всех используемых ячеек равно 0).

Таблица 12 - Сохраняемые ячейки модификации модели, реализованной для решения второй задачи анализа

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

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

ЗАДАНИЕ БУЛЕВЫХ ПЕРЕМКННЫХ И СОХРАНЯЕМЫХ ЯЧЕЕК:BVARIABLEP11'E'1; булева функция проверяет равенство 11 параметра пакета заданному типуBVARIABLEP11'E'2; булева функция проверяет равенство 11 параметра пакета заданному типуBVARIABLEP11'E'3; булева функция проверяет равенство 11 параметра пакета заданному типуBVARIABLEP12'E'11      ; булевая функция проверяет равенство 12 параметра пакета заданной паре типов для 1 1BVARIABLE P12'E'12; для 1 2BVARIABLE P12'E'13; для 1 3BVARIABLE P12'E'21; для 2 1BVARIABLE P12'E'22; для 2 2BVARIABLE P12'E'23; для 2 3BVARIABLE P12'E'31; для 3 1BVARIABLE P12'E'32; для 3 2BVARIABLE P12'E'33; для 3 3,0; ячейка хранит время входа в канал предыдущего пакета,0; ячейка хранит время входа в буфер текущего пакета,0; ячейка хранит тип предыдущего пакета,0; ячейка хранит тип текущего пакета,0; ячейка хранит разность между входом в канал предыдущего пакета и входом в буфер текущего,0; счетчик количества конфликтов для пары типов 1 1X12,0; для 1 2X13,0; для 1 3X21,0; для 2 1X22,0; для 2 2X23,0; для 2 3X41,0; для 3 1X42,0; для 3 2,0; для 3 3,0; счетчик количества проверок на конфликт для пары типов 1 1X18,0; для 1 2X19,0; для 1 3X27,0; для 2 1X28,0; для 2 2X29,0; для 2 3X47,0; для 3 1X48,0; для 3 2X49,0; для 3 3,0; ячейка для хранения вероятности наступления конфликта для пары 1 1X15,0; для 1 2X16,0; для 1 3X24,0; для 2 1X25,0; для 2 2X26,0; для 2 3X44,0; для 3 1X45,0; для 3 2X46,0; для 3 3$PROV11,0,T11          ;проверка пакет какой пары типов пришел для 1 1E BV$PROV12,0,T12; для 1 2E BV$PROV13,0,T13; для 1 3E BV$PROV21,0,T21; для 2 1E BV$PROV22,0,T22; для 2 2E BV$PROV23,0,T23; для 2 3E BV$PROV31,0,T31; для 3 1E BV$PROV32,0,T32; для 3 2E BV$PROV33,0,T33; для 3 3SAVEVALUE 11+,1; пополняем счетчик количества конфликтов для пары типов 1 1,MET4; возвращаем пакет в системуSAVEVALUE 12+,1; пополняем счетчик количества конфликтов для пары типов 1 2,MET4; возвращаем пакет в системуSAVEVALUE 13+,1; пополняем счетчик количества конфликтов для пары типов 1 3,MET4; возвращаем пакет в системуSAVEVALUE 21+,1; пополняем счетчик количества конфликтов для пары типов 2 1,MET4; возвращаем пакет в системуSAVEVALUE 22+,1; пополняем счетчик количества конфликтов для пары типов 2 2,MET4; возвращаем пакет в системуSAVEVALUE 23+,1; пополняем счетчик количества конфликтов для пары типов 2 3,MET4; возвращаем пакет в системуSAVEVALUE 41+,1; пополняем счетчик количества конфликтов для пары типов 3 1,MET4; возвращаем пакет в системуSAVEVALUE 42+,1; пополняем счетчик количества конфликтов для пары типов 3 2,MET4; возвращаем пакет в системуSAVEVALUE 43+,1; пополняем счетчик количества конфликтов для пары типов 3 3,MET4; возвращаем пакет в систему

.3 Реализация модельных экспериментов и анализ результатов

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

Рисунок 6 - Гистограмма суммарного времени задержки передачи пакетов в процессе разрешения конфликтов одновременности

Из анализа данных, представленных на рисунке 6, следует, что среднее времени задержки передачи пакетов в процессе разрешения конфликтов одновременности составляет 3.265 секунд (выводится в графе MEAN статистической таблицы), а среднеквадратическое отклонение времени пребывания - 1.411 секунд (выводится в графе STD.DEV. статистической таблицы).

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

Результаты эксперимента, осуществленного для решения второй задачи анализа, состоящего в определении вероятности возникновения конфликта для пары пакетов каждого типа в СМО с контролем конфликтов одновременности были получены в виде полного стандартного отчета GPSS World Simulation Report. Фрагмент стандартного отчета, содержащий информацию о сохраняемых ячейках, приведен ниже.

RETRY VALUE

0 6501.000

0 9347.000

0 9535.000

0 0.592

0 0.661

0 0.623

0 10976.000

0 14135.000

0 15305.000

0 12349.000

0 8994.000

0 14544.000

0 0.715

0 0.639

0 0.707

0 17270.000

0 14078.000

0 20581.000

0 309636.979

0 309639.847

0 1.000

0 2.000

0 2.868

0 17150.000

0 11193.000

0 20716.000

0 0.753

0 0.645

0 0.744

0 22786.000

0 17364.000

0 27835.000

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

Таблица 13 - Вероятности возникновения конфликтов одновременности для пары пакетов каждого типа

Выводы

В результате курсового проектирования по теме «Моделирование канала связи с контролем конфликтов одновременности» решены следующие задачи и получены результаты:

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

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

-  коэффициент использования канала;

-  вероятность возникновения конфликта одновременности;

-  вероятность потери пакета из-за занятости буфера;

1. Осуществлена реализация имитационной вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World. Принципиальными особенностями реализации является использование:

- сохраняемых ячеек GPSS для хранения значения типа предыдущего пакета, времени входа в буфер, разности между входом в буфер и началом обслуживания;

-   идентификации пакета по типу, размеру с сохранением в параметры пакета №10 и №11 соответствующих целочисленных значений, а также его время пребывания в буфере параметр №16;

. Проведен эксперимент по моделированию процесса обслуживания заявок в СМО часов с получением результатов в виде полного стандартного отчета GPSS World Simulation Report. По результатам эксперимента определены все характеристики функционирования СМО по части 1 задания на курсовое проектирование.

Во второй части курсового проекта:

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

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

. Решена вторая задача анализа - определение вероятности возникновения конфликта одновременности для пары пакетов каждого типа. Особенностью модификации имитационной модели является использование ячеек GPSS для сохранения количества проверок на возможность конфликта и количества конфликтов для пары пакетов каждого типа, а также в ячейки были записаны значения вероятностей;

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

Таблица 16

Литература

1. Советов Б.Я., Яковлев С.А. Моделирование систем. Учебник для вузов. -М.:Высш. шк., 2005.-343c.

. Тарасик В.П. Математическое моделирование технических систем. -Мн.: Дизайн ПРО, 2004.-640c.

. Боев В.Д. Моделирование систем. Инструментальные средства GPSS World: Учебное пособие. -СПБ.: БХВ-Петербург, 2004.-348c.

. Кудрявцев Е.М. GPSS World: основы имитационного моделирования различных систем. - М.: ДМК Пресс, 2004.-317c.

. Соболь И.М. Метод Монте-Карло. -М.: Наука, 1978.-64с.