Зайцев Д.А., Шмелева Т.Р. Моделирование телекоммуникационных систем в CPN Tools

Подождите немного. Документ загружается.

fun metr (x) =

let

val mminm=1000;

x div mminm

end;

5.5. Случайные функции

Случайные функции обеспечивают возможность моделирования

статистических характеристик. Например, они позволяют описывать

интенсивность трафика или вероятность ошибок в телекоммуникационных

системах. Существуют несколько способов описания случайного выбора в CPN

Tools:

– свободные (несвязанные) переменные;

– функция ran;

– специальные случайные функции с указанным законом распределения.

Свободные (несвязанные) переменные являются переменными

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

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

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

цветов. Множества цветов могут быть классифицированы как большие или

малые. Это

различие определяет, какие предопределенные функции могут

применяться для указанного множества цветов. Множество цветов является

большим, если оно содержит много (по умолчанию более 100)

пронумерованных элементов, иначе множество является малым. Множества

цветов unit, Boolean, index и enumerated являются малыми.

В следующем примере переменная i – свободная переменная в диапазоне

1.. 31. На втором рисунке показано состояние модели после четырех шагов;

четыре значения переменной i были выбраны CPN Tools случайным образом:

colset mday = int with 1..31;

var i : mday;

INT

colset mday = int with 1..31;

var i : mday;

INT

1`10++

1`13++

1`14++

1`20

Функция ran генерирует случайную величину для больших множеств

цветов. В следующем примере функция ranRange() генерирует случайную

величину в диапазоне 1..10000:

1`ranRange()

colset Range = int with 1..10000;

fun ranRange () = Range.ran();

INT

1`ranRange()

colset Range = int with 1..10000;

fun ranRange () = Range.ran();

INT

1`158++

1`569++

1`728++

1`8978

Система СPN Tools предоставляет также ряд специальных случайных

функций с различными законами распределения случайных величин:

Бернулли, биномиальное, Эрланга, показательное, нормальное, Пуассоновское,

Стьюдента, равномерное (дискретное и непрерывное). Например, функция

erlang(n:int, r:real) : real

где n>=1 и r>0.0, возвращает выборку из n–го распределения Эрланга с

интенсивностью r.

5.6. Мультимножества

Мультимножества широко используются в CPN Tools для представления

маркировки позиций и в других целях. Рассмотрим концепцию

мультимножества. В отличие от обычных множеств, мультимножества

содержат элементы с определенной кратностью, другими словами в

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

«портфелями».

Символ обратной кавычки (`) является конструктором мультимножества.

Например, 3`5 – это мультимножество, состоящее из трех

элементов цвета

(типа) 5. Синтаксис описания мультимножества имеет вид:

i`c,

где целое i – неотрицательное число, в противном случае будет возвращено

пустое мультимножество. Конструктор мультимножества, дополненный

операторами сложения (++) и вычитания (-–) мультимножеств, обеспечивает

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

описанном в разделе 1, в позиции «sack of mixture» указана начальная

маркировка:

1000`rice ++ 2000`wheat ++ 3000`oat

Это означает, что мешок содержит 1000 зерен риса, 2000 зерна пшеницы и

3000 зерен овса. Следует обратить внимание на знак конструктора

мультимножества: это – обратная кавычка (`), а не апостроф ('). Для примера

фрейма Ethernet с множеством цветов frame1 содержание буфера может быть

представлено как:

1`{src=2, dst=5, d=”request”} ++ 1`{src=5, dst=2, d=”answer”}

Указаны два кадра: первый с данными ”request”, направленный на устройство

5 от устройства 2, и второй с данными

”answer”, направленный на устройство

2 от устройства 5.

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

операции и функции:

empty

константа empty создает пустое мультимножество, которое сопоставимо

с любыми типами мультимножеств

ms1 == ms2

равенство мультимножеств

ms1 <><> ms2

неравенство мультимножеств

ms1 >> ms2

мультимножество больше, чем

ms1 >>== ms2

мультимножество больше или равно

ms1 << ms2

мультимножество меньше, чем

ms1 <<== ms2

мультимножество меньше или равно

ms1 ++ ms2

сложение мультимножеств

ms1 -- ms2

вычитание мультимножеств (ms2 должно быть меньше или равно ms1),

генерирует прерывание, если ms2 не меньше или равно ms1.

i ** ms

скалярное произведение

size ms

размер мультимножества

random ms

возвращает псевдослучайный цвет из мультимножества

cf(c,ms)

возвращает количество появлений цвета в мультимножестве

filter p ms

берет предикат p и мультимножество ms и генерирует

мультимножество всех элементов ms, удовлетворяющих предикату p

Например,

m1 = 2`5 ++ 3`4 ++ 4`5;

m2 = 1`5 ++ 2`4 ++ 3`5;

тогда

m1 ++ m2 = 3`5 ++ 5`4 ++ 7`5

m1 – m2 = 1`5 ++ 1`4 ++ 1`3

m1 >> m2 имеет значение true

size m1 = 9

cf(4,m1) = 3

В CPN Tools начальная и текущая маркировки позиции представлены

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

фишки в переменную надписи дуги CPN Tools обеспечивает случайный выбор

фишки, как с помощью функции random.

5.7. Временные мультимножества

Временные мультимножества используются в CPN Tools, чтобы

представить временные задержки в модели. Описание соответствующего

множества цветов должно быть дополнено модификатором timed. Операторы

@, @+, и @@ + используются, чтобы добавить временные метки к цветам.

Добавление временной задержки x к цвету c присоединяет временную метку с

величиной, равной текущему времени модели + x, к цвету c. Следующие

операции

применимы к временным мультимножествам:

c @ t

присоединение временной метки (с типом Time.time) к цвету c

ms @+ i

добавление целой временной задержки i к каждому из цветов

мультимножества

ms, возвращает временное мультимножество

tms1 +++ tms2

сложение временных мультимножеств

Например, описание

colset tint = int timed;

var t : tint;

t = 1`2@100 ++ 1`3@200 ++ 1`4@300;

означает, что фишка 2@100 может быть использована CPN Tools только когда

модельное время больше или равно 100, фишка 3@200 – только когда

модельное время больше или равно 200 и т.д. До наступления момента

активации фишка не может быть извлечена ни одним переходом модели.

6. Язык описания моделей

В CPN Tools каждый элемент сети Петри имеет свои атрибуты, описанные

на языке CPN ML. Используя инструменты для создания элементов

сети, можно поместить элемент на страницу модели. Затем добавляются

атрибуты элементов. Для этого необходимо щелкнуть мышью на

соответствующем элементе и использовать кнопку Tab на клавиатуре для

переключения атрибутов. Нажатие на клавиатуре клавиши Esc позволяет

покинуть

выбранный элемент; такой же результат может быть получен

щелчком мыши в любой другой области модели. Рассмотрим атрибуты каждого

элемента сети отдельно.

6.1. Атрибуты позиций

Существует три типа атрибутов, которые могут быть связаны с позицией.

Два из них – необязательные:

• Цвет фишек – обязательный атрибут;

• Начальная маркировка – необязательный атрибут;

• Имя – необязательный атрибут.

NAME

COLOR SET

INITIAL MARKING

По начальной маркировке CPN Tools автоматически создает текущую

маркировку, которая отображается зеленым цветом и показывает общее число

фишек и детали маркировки. Например, в примере о Золушке:

sack with

mixture

1000`rice++2000`wheat++3000`oat

6000

1000`rice++

2000`wheat++

3000`oat

Имя

Множество

ветов

Начальная маркировка

6.2. Атрибуты дуг

Атрибут имеет вид:

Множество цветов выражения на дуге expr должно соответствовать

множеству цветов позиции, связанной с дугой. Если множество цветов

выражения на дуге не соответствует множеству цветов позиции, связанной с

дугой, то около дуги во время проверки синтаксиса появится сообщение об

ошибке. Между атрибутами входных и выходных дуг перехода есть

существенное различие.

Выражение

входной дуги перехода является шаблоном для выбора фишки.

Этот шаблон описывается как предикат, который может быть применен в

функции filter, для соответствующего множества цветов. В самом простом

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

цветов, как в вышеуказанных примерах. В следующей сети

x x

var x: INT;

INT

2`5++3`4++1`3

1`3++

3`4++

2`5

INT

любая из 6 фишек может быть выбрана переменной x. Более сложный случай

представляет собой выбор кадров с адресом отправителя, равным двум для

кадров сети Ethernet:

(2,dst,d)

get

colset MAC=INT;

colset DATA=string;

colset frame=product MAC * MAC * DATA;

var src, dst : MAC;

var d : DATA;

buffer

frame

1`(2,5,"a")++1`(3,4,"b")++1`(2,4,"c")

1`(2,4,"c")++

1`(2,5,"a")++

1`(3,4,"b")

Любой из кадров (2,5,"a") и (2,4,"c") может быть выбран выражением

(2,dst,d).

Выражение выходной дуги перехода представляет собой конструктор для

создания новых фишек. Такой конструктор часто использует переменные

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

следующем примере переход sum вычисляет сумму входных фишек:

1`(x+y)

sum c

INT

5`10++4`20

5`10++

4`20

INT

7`3++5`4

7`3++

5`4

1`(x+y)

sum c

INT

1`13++

1`14++

1`24

INT

5`10++4`20

3`10++

3`20

INT

7`3++5`4

6`3++

3`4

Кроме того, временные задержки могут быть применены к выходным

фишкам. В следующем примере обеспечивается формирование (генерация)

кадра через каждые 100 единиц модельного времени:

x@+100 x

gen

colset tframe=frame timed;

var x: tframe;

clock

tframe

(2,4,"ping")

1`(2,4,"ping")@0

buf

tframe

x@+100 x

gen

colset tframe=frame timed;

var x: tframe;

clock

tframe

(2,4,"ping")

1`(2,4,"ping")@300

buf

tframe

1`(2,4,"ping")@200+++

1`(2,4,"ping")@100+++

1`(2,4,"ping")@0

6.3. Атрибуты переходов

Существует четыре типа атрибутов, которые могут быть связаны с

переходом. Все они являются необязательными:

• Имя перехода;

• Условие запуска перехода;

• Время задержки;

• Сегмент кода.

NAME

CODE SEGMENT

[GUARD] @+(TIME DELAY)

Время задержки перехода должно быть положительным целым числом.

Выражение, следующее за @+, означает, что временной атрибут имеет форму

@+delay–expr. Прежде, чем временная задержка будет добавлена, по

умолчанию вводится текст надписи – @+. Задержка времени всегда

добавляется относительно текущего времени. Например, если текущее время –

10 и задержка времени – @+2, тогда временная метка фишки, направленной в

выходную

позицию, будет равной 12. Отсутствие атрибута времени

эквивалентно нулевой задержке. В отличие от задержки дуг, задержки

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

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

с примером в разделе 6.2:

Имя

Условие на

переходе

@ + время задержки

Сегмент кода

x x

gen

@+100

clock

tframe

(2,4,"ping")

1`(2,4,"ping")@0

buf

tframe

x x

gen

@+100

clock

tframe

(2,4,"ping")

1`(2,4,"ping")@300

buf

tframe

1`(2,4,"ping")@300+++

1`(2,4,"ping")@200+++

1`(2,4,"ping")@100

Условие запуска перехода является логическим выражением языка CPN

ML, которое оценивается как true (правда) или false (ложь). Перед тем как

условие будет добавлено, выводится текст надписи по умолчанию: []. Условие

может быть простым логическим выражением или списком логических

выражений [b-exp1, b-exp2,..., b-expn]. Переход срабатывает

только в том случае, если условие является истинным, что также ограничивает

выбор входных

фишек. Например, проверка входных фреймов, представленных

в разделе 6.2, может быть описана следующим образом:

(src,dst,d)

get

[src=2]

colset MAC=INT;

colset DATA=string;

colset frame=product MAC * MAC * DATA;

var src, dst : MAC;

var d : DATA;

buffer

frame

1`(2,5,"a")++1`(3,4,"b")++1`(2,4,"c")

1`(2,4,"c")++

1`(2,5,"a")++

1`(3,4,"b")

Кроме того, условие допускает сравнение параметров фишек из различных

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

моделирует процесс извлечения кадров из сегмента Ethernet:

addr

get

[#1 f = addr]

var addr : MAC;

var f : frame;

segment

frame

1`(2,5,"a")++1`(3,4,"b")++1`(2,4,"c")

1`(2,4,"c")++

1`(2,5,"a")++

1`(3,4,"b")

own

MAC

1`2

buffer

frame

Адрес рабочей станции храниться в позиции own. Для его проверки

используется двунаправленная дуга.

Любой переход может содержать присоединённый сегмент кода

, который

представляет собой процедуру языка ML. Сегмент кода выполняется, когда

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

переменные CPN и может связывать переменные CPN, расположенные в

надписях входных дуг, которые не связаны в других атрибутах. Каждый

сегмент кода может содержать:

• Входной шаблон (необязательный);

• Выходной шаблон (необязательный);

• Код операций (обязательный).

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

ключевым словом input. Он перечисляет переменные CPN, которые могут

быть использованы в коде операций. Код операций может использовать

значения этих переменных CPN, но не может изменять их. Переменные CPN,

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

операций, если их объявили как идентификатор ML с таким же

именем в

области описания переменных. Если входной шаблон опущен, то

подразумевается, что никакие переменные CPN не могут быть использованы в

коде операций.

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

ключевым словом output. Он перечисляет переменные CPN, которые

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

быть переменной CPN или кортежем переменных CPN без

повторений. Если

выходной шаблон опущен, то подразумевается, что никакие переменные CPN

не вычисляются.

Код операций является выражением языка ML, следующим за ключевым

словом action. Он не может содержать описание множеств цветов,

переменных CPN или ссылочных переменных. Тем не менее, к кодовому

выражению можно применить объявленные пользователем константы,

операции, и функции. Кроме того, новые функции

и константы могут быть

определены для локального использования посредством let-in-end.

Кодовое выражение выполняется как локальное описание в среде, содержащей

переменные CPN, определенные во входном шаблоне. Это гарантирует, что

кодовое выражение не может изменить непосредственно любые переменные

CPN, а может изменить только их локальные копии. Когда кодовое выражение

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

CPN переменным в выходном

шаблоне. Кодовое выражение при оценке в среде, содержащей входные

переменные, должно дать результаты такого же типа как выходные

переменные. Если не представлено никакой выходного шаблона, то

подразумевается тип результата unit.

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

фишек. Например, суммирование фишек, описанное в разделе 6.2, можно

представить,

используя кодовый сегмент:

sum

input (x,y);

output (z);

action

(x+y);

INT

5`10++4`20

5`10++

4`20

INT

7`3++5`4

7`3++

5`4

Создать

список

будущих

событий

Найти ближайшее

будущее событие

со временем NTime

Увеличить

время

Time:=

Time

Последовательно

запустить все

возбужденные

переходы

7. Особенности временных сетей CPN Tools

CPN Tools обеспечивает моделирование сетей Петри, как временных, так и

невременных. Если ни одно из множеств цветов модели не имеет временной

модификатор timed, тогда сеть считается невременной untimed. В этом

случае CPN Tools использует только внутреннюю переменную Step, которая

обозначает количество выполненных переходов. Алгоритм имитационного

моделирования CPN Tools можно представить следующим образом:

Следует обратить внимание на то, что выбор перехода может быть

осуществлен вручную в пошаговом режиме моделирования, либо

автоматически случайном образом при выполнении указанного количества

шагов.

Для временных сетей Петри, алгоритм более сложный, так как

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

Следующий момент модельного времени не будет являться моментом

времени Time+1. Система двигает время до ближайшего будущего события

Time:=time–of–nearest–future–event и затем выполняет все события,

которые могут произойти в этот момент времени, увеличивая переменную

Step, описанную выше. Поэтому необходимо быть осторожным при

объединении временных и невременных сетей, так как разрешенные переходы

срабатывают до

тех пор, пока множество разрешенных переходов не станет

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

следующей сети время не продвигается и количество сгенерированных кадров

постоянно увеличивается:

x x

gen

@+100

clock

frame

(2,4,"ping")

1`(2,4,"ping")

buf

tframe

42`(2,4,"ping")@100

Следует отметить, что CPN Tools поддерживает простой и очень мощный

класс временных сетей Петри, соответствующий использованию временных

меток (штампов). Каждая фишка имеет свою временную метку t (k@t). Для

моментов модельного времени Time<t фишка не обрабатывается системой

моделирования; она находится в так называемом недействительном состоянии

Create the set

of permitted

transitions

Выбрать

активный

переход t

Запустить

выбранный

переход

Увеличить

номер шага:

STEP:=STEP+1

Создать

множество

возбужденных

пе

еходов

и не принимает участие в срабатывании переходов. После момента времени t

фишка k «просыпается» и принимает участие в срабатывании переходов. Такой

способ представления времён разрешает мгновенное срабатывание переходов.

Выходные фишки, имеющие временную задержку (k@t+d), ожидают своего

времени активации в соответствующих выходных позициях. Следующий

пример трассировки иллюстрирует способ обработки времён в CPN Tools:

x x

@+50

Step: 0

Time: 0

tint

1`5@+100++1`4@+100++1`3@+100++

1`4@+200++1`3@+200++

1`5@+300++1`4@+300

1`3@200+++

1`3@100+++

1`4@300+++

1`4@200+++

1`4@100+++

1`5@300+++

1`5@100

tint

x x

@+50

Step: 1

Time: 100

tint

1`5@+100++1`4@+100++1`3@+100++

1`4@+200++1`3@+200++

1`5@+300++1`4@+300

1`3@200+++

1`4@300+++

1`4@200+++

1`4@100+++

1`5@300+++

1`5@100

tint

1`3@150

x x

@+50

Step: 2

Time: 100

tint

1`5@+100++1`4@+100++1`3@+100++

1`4@+200++1`3@+200++

1`5@+300++1`4@+300

1`3@200+++

1`4@300+++

1`4@200+++

1`4@100+++

1`5@300

tint

1`3@150+++

1`5@150

x x

@+50

Step: 3

Time: 200

tint

1`5@+100++1`4@+100++1`3@+100++

1`4@+200++1`3@+200++

1`5@+300++1`4@+300

1`3@200+++

1`4@300+++

1`4@200+++

1`5@300

tint

1`3@150+++

1`4@150+++

1`5@150

x x

@+50

Step: 5

Time: 300

tint

1`5@+100++1`4@+100++1`3@+100++

1`4@+200++1`3@+200++

1`5@+300++1`4@+300

1`4@300+++

1`5@300

tint

1`3@250+++

1`3@150+++

1`4@250+++

1`4@150+++

1`5@150

x x

@+50

Step: 7

Time: 300

tint

1`5@+100++1`4@+100++1`3@+100++

1`4@+200++1`3@+200++

1`5@+300++1`4@+300

tint

1`3@250+++

1`3@150+++

1`4@350+++

1`4@250+++

1`4@150+++

1`5@350+++

1`5@150

В момент времени 0 ни один переход не разрешен, так как ни у одной фишки

нет временной метки 0. Следующий момент времени равен 100. CPN Tools

выполняет 3 шага в этот момент времени, перемещает 3 фишки в позицию c;

все эти фишки имеют начальные временные метки, равные 100. В момент

времени 200 перемещаются 2 фишки с временными метками 200 и, наконец, в

момент времени 300 перемещаются 2 оставшиеся фишки.

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

переходов или задержки дуг. Задержки переходов в большинстве случаев более

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

задержек дуг дает большую гибкость при построении моделей.

Для моделирования трафика удобно использовать случайные функции в

качестве временных задержек.

Большой выбор случайных функций с

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

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

(генерируется) Пуассоновский поток кадров:

x@+poisson(100.0) x

genclock

tframe

(2,4,"ping")

1`(2,4,"ping")@642

buf

tframe

1`(2,4,"ping")@536+++

1`(2,4,"ping")@430+++

1`(2,4,"ping")@329+++

1`(2,4,"ping")@217+++

1`(2,4,"ping")@105+++

1`(2,4,"ping")@0

8. Работа с фрагментами сети

Работу с фрагментами можно рассматривать, как стандартную

возможность графического редактора. Большинство графических редакторов

(например, Corel Draw) обеспечивают выполнение операций с выделенными

прямоугольными фрагментами изображения. В CPN Tools понятие фрагментов