Инструментальная среда имитационного моделирования распределенных систем мобильных агентов



страница2/21
Дата07.03.2016
Размер2.3 Mb.
1   2   3   4   5   6   7   8   9   ...   21

ВВЕДЕНИЕ


В настоящее время существует множество сложных систем, состоящих из разных компонентов, активно между собой взаимодействующих. Для улучшения понимания взаимодействия отдельных компонентов модели удобно использовать автоматизированное имитационное моделирование, так как это экономит силы и время. Для выполнения автоматизированного моделирования необходимо реализовать программу-эмулятор исследуемой системы. Для подобных эмуляторов должна быть определена формальная модель, распознаваемая и выполняемая программным эмулятором. Под каждую конкретную задачу реального мира сложно создавать отдельную формальную модель и эмулятор, поэтому необходима обобщенная модель, учитывающая различные параметры в рассматриваемой области моделирования. В данной работе акцент ставится на активном взаимодействии агентов, мобильности агентов, сложности устройства агентов (агент – это объект, принимающий различные состояния и манипулирующий в процессе своей работы входными и выходными ресурсами), учете временных параметров. Теоретическими примерами такого класса моделей могут выступать: задача об обедающих философах, задача о курильщиках, задача о спящем парикмахере. В реальном мире это могут быть сложные веб-сервисы, передающие информацию одновременно нескольким пользователям и использующие общие ресурсы; многоканальные центры с несколькими параллельными линиями, принимающие звонки и т.д.

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



Таблица 1

Интересующие нас свойства формальных моделей

Формальная модель

Основные интересные для нас свойства

Классические Сети Петри [8]

Известная классическая модель, графическая визуализация, наличие большого количества алгоритмов для проверки свойств

Временные сети Петри: модель Мерлина [6], модель Штарке [7]

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

Временные автоматы [1]

Учет временных характеристик: несколько счетчиков внутри одной модели, сбросы счетчиков, ограничения

Сети активных ресурсов [2] – AR nets

Эквиваленты по выразительности классическим сетям Петри. Модель ресурсно-ориентированна: вместо классического разделения вершин на позиции и переходы (активные и пассивные компоненты) в данной модели один тип вершин, но два типа дуг – потребляющие и производящие.

Ресурсно-управляемые сети автоматов [3] – RDA nets

Двухуровневое обобщение сетей активных ресурсов. Конечные автоматы, представляющие элементные сети в данной модели (аналог фишки в классических сетях Петри) могут вести себя как активным, так и пассивным образом (производить/потреблять ресурсы или быть потребленными/быть произведенными ресурсами)

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


Таблица 2

Программные инструменты и реализуемые ими формальные модели

Программный инструмент

Формальная модель

CPN Tool [10], ProM [11]

Классические сети Петри [8]

UPPAAL [9]

Временные сети Петри: модель Мерлина [6], модель Штарке [7]

UPPAAL [9]

Временные автоматы [1]



Сети активных ресурсов [2]



Ресурсно-управляемые сети автоматов [3]

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

Разработать формальную модель для описания распределенных систем мобильных агентов – ресурсо-управляемые сети временных автоматов и создать инструментальную среду имитационного моделирования на основе данного формализма.



  1. ФОРМАЛЬНЫЕ МОДЕЛИ РАСПРЕДЕЛЕННЫХ СИСТЕМ


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

Схема 1. Предыстория формализма TRDA


1.1. Классические сети Петри


Классические сети Петри - это формальная модель, разработанная Карлом Адамом Петри в 1962 для описания химических реакций [8]. Модель представляется в виде двудольного ориентированного графа, где два типа вершин соответствуют позициям (метсам) и переходам. Внутри вершин типа «Позиция» находятся фишки, изображенные в виде черных точек, символизирующие ресурсы. Позиции соединены с переходами (вершинами типа «Переход») с помощью направленных дуг, сверху на которых указывается их кратность. Считается, что переход готов к срабатыванию, если имеется достаточное количество фишек во входных позициях данного перехода (достаточность определяется с учетом кратности входных дуг данного перехода).

Дадим формальное определение Сети Петри. Сетью Петри называется набор N=(P,T,F,M0), где

P — конечное множество мест

T — конечное множество переходов, PT=

F: (PT)(TP)Nat — функция инцидентности (0 включается в множество натуральных чисел). Функция инцидентности определяет наличие и кратность направленных дуг между позициями и переходами (и наоборот, между переходами и позициями) .

Маркировкой сети Петри N называется функция M: P  Nat, сопоставляющая каждой позиции сети некоторое натуральное число - количество фишек в данной позиции.

Маркировка M0 – начальная маркировка, то есть начальная разметка системы.

Переход tT активен при разметке M, если pP M(p)F(p,t) . Это условие означает, что во входных позициях перехода t количество фишек больше или равно кратности соответствующих входных дуг этого перехода.

Активный при разметке M переход t может сработать, породив при этом новую разметку M', где pP M'(p) =def M(p)F(p,t)+F(t,p). В новой разметке количество фишек, в позициях, из которых идут входные дуги перехода, уменьшается на кратность соответствующих дуг. Аналогичным образом, количество фишек в позициях, в которые идут выходные дуги перехода, увеличивается на кратность выходных дуг перехода.

1.2 Временные сети Петри


Для более выразительного моделирования можно использоваться сети Петри со временем. Время может быть введено в различные элементы сети: время срабатывания перехода; время, которое фишка находится в состоянии, и т.д. Существует две основные модели временных сетей Петри: модель Мерлина [6] и модель Штарке [7].

Рассмотрим эти две модели, введя время в срабатывание переходов.

Пусть N - множество натуральных чисел, а R – множество рациональных чисел

1)Модель Мерлина – непрерывно временная модель.

Непрерывно-временной сетью Петри называется набор CTN=(P,T,F,M0,D), где

(P,T,F,M0) – классическая сеть Петри

D:T→Interv — временная функция, сопоставляющая каждому переходу t ∈ T интервал D(t) из множества Interv, где множество Interv = {[d1,d2] ⊂R,d1≤d2}.

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

Пусть V:T→R — множество наборов значений часов, связанных с переходами из T.

Состоянием в CTN называется пара q=, где M — маркировка в CTN и ν∈V.

Будем говорить, что в состоянии q= переход t ∈ T может сработать, если переход T активен t ∈ En(M) и счетчик времени v(t)∈D(t), соответствующий переходу t v(t), имеет значение, попадающее в интервал, задаваемый временной функцией данного перехода D(t).

Срабатывание перехода происходит мгновенно.

2)Модель Штарке – дискретно временная модель. [7]

Дискретно-временной сетью Петри называется набор  DTN=(P,T,F, M0,D), где

(P,T,F,M0) – классическая сеть Петри

D:T→N — временная функция, сопоставляющая каждому переходу натуральное число, соответствующее временной длительности его срабатывания.

Для каждого перехода t значение D(t) определяет длительность срабатывания t, т.е если переход t срабатывает в момент времени x, то фишки из входных мест перехода t "уходят" в момент времени x и появляются в выходных местах перехода t в момент времени x + D(t).

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

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

1.3 Сети активных ресурсов


Сеть активных ресурсов [2], AR nets, - еще один формализм для моделирования распределенных систем. Идея связана с тем, что активные агенты системы являются одновременно ее ресурсами. AR nets по выразительности эквиваленты классическим сетям Петри. Однако они отличаются от классических сетей Петри способом моделирования. В отличие от классических сетей Петри, в которых вершины разбиты на позиции и переходы (активные и пассивные компоненты), в AR nets все вершины одного типа, а дуги делятся на производящие и потребляющие.

Сетью активных ресурсов называется набор AR=(V,I,O), где

V — конечное множество вершин

I: (VV)  Nat — множество потребляющих дуг. Потребляющей дуге ставится в соответствие количество потребляемых ресурсов.

O: (VV)  Nat — множество производящих дуг. Производящей дуге ставится в соответствие количество производимых ресурсов.

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

Разметкой сети AR называется функция вида M: V  Nat. Для каждой вершины определяется количество находящихся в ней фишек (ресурсов).

Ресурс (агент) в вершине vV активен при разметке M, если M(v)>0 (узел v непустой) и wV M(w)I(w,v) (в потребляемых узлах вершины v, из которых идут потребляющие дуги в вершину v, содержится достаточное количество фишек). Активный ресурс v при разметке M может сработать, порождая при этом новую разметку M', где wV  M'(w) =def M(w)I(w,v)+O(v,w). Как видно, вершина, в которой находится активный ресурс, срабатывает, как если бы она временно стала переходом в обычной сети Петри.



1.4 Ресурсно-управляемые сети автоматов


Ресурсно-управляемые сети автоматов, RDA-сети, [3] – разработанный на основе AR-сетей формализм для моделирования взаимодействия распределенных агентов с учетом ресурсных зависимостей. RDA-сеть имеет два уровня. Системный уровень задается сетью активных ресурсов, которая описывает распределение агентов/ресурсов и порты, через которые они могут взаимодействовать. Агенты, представлены конечными автоматами, взаимодействующими друг с другом через порты системной сети. Выполнение агентом перехода может быть связано с потреблением и производством ресурсов.

Константа в модели RDA nets - это аналог фишки в классических сетях Петри. Константы могут быть как простыми ресурсами, так и агентами, имеющими структуру конечного автомата. Все константы типизированы. Пусть Ω - конечное множество типов (types). Типы Ω типизируют как константы, так и порты системной сети. Тип порта означает, что по нему возможна обработка (потребление или производство) констант только данного типа.

П – конечное множество типизированных портов. Для порта p П, тип порта обозначается type(p). При этом type(p)  Ω.

Const – Множество констант, каждая из которых принадлежит некоторому типу A, где А Ω.



Системная сеть - кортеж SN= (V,I,O,π), где

(V,I,O) – сеть активных ресурсов: набор вершин, соединенных между собой потребляющими и производящими дугами.

π : (IO)  П - функция разметки дуг именами портов

Маркировкой M системной сети SN называется функция M: V  Μ(Const), где Μ(Const) – мультисет множества Const, множество состоящее из произвольного (в том числе и равного 0) количества элементов множества Const. Таким образом, в любой вершине системной сети может находится произвольное количество констант из множества Const любого типа и маркировка М задает заполнение вершин системной сети фишками (агентами и ресурсами).


Элементная сеть

Ресурсно-управляемый автомат A=( SA,TA,lA), типа A (AΩ), где

S A - конечное множество состояний

TA SA SA - конечное множество переходов

lA: TALA пометки переходов (перечень входных и выходных термов перехода)

LA – выражение на языке L для автомата A.

L - язык выражений вида π1σ1e1+ π2σ2e2+…+ πkσkek, где

πi имена портов ( type(πi)  Ω )

σiσ{?,!}, где ? – потребление, ! - производство

ei – переменная или константа типа πi

Например, выражение get ? fish на переходе автоматной сети (конечного автомата или агента), означается, что в системе есть объект (агент или ресурс) fish, порт get на системной сети, и при выполнении рассматриваемого перехода автоматной сети (при условии, что агент находится в позиции, имеющей порт потребления get, ведущий к другой позиции, в которой находится ресурс fish) ресурс fish будет потреблен через порт get.

Выполнение перехода t агента А требует ресурсы, перечисленные во входных термах этого перехода lA(t). Входной терм имеет вид πi?ej, где ej – переменная или константа того же типа , что и порт πi. Выходной терм имеет вид πi!ej. Выходной терм определяет, где и какие объекты будут созданы (произведены) в результате выполнения перехода.



1.5 Временные автоматы


Формальная модель временных автоматов [1] была разработана Alur и Dill в 1994 году.

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

Временной автомат – это кортеж A = (L, L0,Lacc , ∑, X, E), где

L –конечное множество позиций (вершин)

L0  L – начальная позиция (вершина)

Lacc ⊆ L – множество принимаемых (в качестве финальных) позиций

∑ - конечный алфавит

X – конечное множество счетчиков

E  LG ∑2XL – множество ребер

G = {x op c | x  X, c  N} – множество охранников

op  {<,<=,=, >=,>}

2Xвсе возможные комбинации наборов счетчиков (для сброса, обнуления, значений счетчиков – reset). Сброс счетчика x обозначается на схеме «{x}».

Пример:

Рисунок 1. Пример классического временного автомата.

Зеленым выделены охранники (guard) (x > 0, x=1, y=1) (ττ, в данной нотации, обозначает отсутствие охранников)

Синим – символы входного слова (a, b)

Красным – сбросы счетчиков (reset clocks) ({x}, {y} )

Голубым – счетчики (часы) (clock) ( X ={x,y} )

Значение vR назначает каждому счетчику его часовое значение

Состояние (l,v) LR состоит из позиции и значений счетчиков

Изменение состояний временного автомата могут быть двух типов:


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

(l,v) (l,v+τ)

  1. переход в новое состояние, то есть автомат переходит в следующую позицию, а вместе с этим изменяется и значение счетчиков

(l,v) (l’,v’)
    1. Ресурсно-управляемые сети временных автоматов


Модель ресурсно-управляемых сетей временных автоматов, TRDA nets, – модель, созданная в рамках данной работы. TRDA модель строится на базе ресурсно-управляемых сетей автоматов с добавлением возможностей временных сетей Петри или временных автоматов. Тем самым в данной работе были созданы две разновидности TRDA моделей. Будем обозначать TRDAPetri nets – модель, построенную с добавлений возможностей временных сетей Петри в элементную сеть и TRDATimed automata – модель с добавлений возможностей временных конечных автоматов. В случае, если при изложении нет разницы, про какую из моделей идет речь, будем обозначать модель как TRDA. TRDA сеть (обеих разновидностей) является двухуровневой сетью, состоящей из системного и автоматного (элементного) уровней. Системная сеть – это распределенная система позиций (вершин), соединенных между собой потребляющими и производящими дугами, аналогичная сетям активных ресурсов. Автоматные (элементные) сети - это совокупность графов изменения состояния агентов, которые являются расширенными конечными автоматами, асинхронно потребляющими/производящими общие ресурсы через входные/выходные порты (поименованные и типизированные дуги) системной сети.

Константа в модели TRDA nets - это аналог фишки в классических сетях Петри. Константы могут быть как простыми ресурсами, так и агентами, имеющими структуру конечного автомата с добавлением временных характеристик. Все константы типизированы. Пусть Ω - конечное множество типов (types). Типы Ω типизируют как константы, так и порты системной сети. Тип порта означает, что по нему возможна обработка (потребление или производство) констант только данного типа.

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

Обозначим R как множество вещественных чисел.

Дадим определение системной сети TRDA модели. Оно аналогично системной сети RDA модели.

(Напомним,



Системная сеть SN=(V,I,O,π) - это сеть активных ресурсов, где

V — конечное множество вершин

I: (VV) — множество потребляющих дуг

O: (VV) — множество производящих дуг

π : (IO)  П - функция разметки дуг именами порта)

Теперь дадим определение элементной сети. Ее определение различно для TRDAPetri nets и TRDATimed automata.



Рассмотрим элементную сеть TRDAPetri nets:

Элементная сеть APetri nets=(SA, TA, lA, WaitA, TimeA) конечный автомат с дополнительными пометками переходов, где

A=( SA,TA,lA) – RDA сеть.

( Напомним,

SA - конечное множество состояний

TA SA SA - конечное множество переходов

LA :TA L – функция разметки переходов, сопоставляющая каждому переходу описание входных и выходных термов на языке выражений (L) вида π1σ1e1+ π2σ2e2+…+ πkσkek, где

πi имена портов ( type(πi)  Ω )

σi{?,!}, где ? – потребление (вход), ! – производство (выход)

ei – переменная или константа типа πi )


WaitA: TA Interv – функция, сопоставляющая каждому переходу временной интервал, время ожидания срабатывания перехода. В ходе выполнения модели в момент, когда переход становится активным, из этого интервала произвольным образом выбирается число. Это число означает время, когда сработает (начнет выполняться) переход при условии, если он в течение всего этого времени будет оставаться активными.
TimeA: TAInterv – функция, сопоставляющая каждому переходу временной интервал, время выполнения перехода. В ходе выполнения модели в момент, когда переход начинает выполняться, из этого интервала произвольным образом выбирается число. Выбранное число означает длительность выполнения данного перехода.

Interv = {[d1,d2] ⊂R,d1≤d2}.


Теперь рассмотрим элементную сеть TRDA Timed automata.

Элементная сеть ATimed automata =(SA, TA, lA, TimeA, XA, GA, ResetA) конечный автомат с дополнительными пометками переходов, где

A=( SA,TA,lA) – RDA сеть

TimeA - аналогично TRDAPetri nets

XA – множество счетчиков времени. В начале работы все счетчики равны нулю. В процессе работы все счетчики синхронно увеличиваются.

GA: TA{ConstrA} - функция, сопоставляющая каждому переходу набор ограничений ConstrA., где

ConstrA - ограничение, предикат вида x∆c или y+z∆c или x-y∆c, где x,y,zXA, а ∆ может принимать значения {<,≤,=,≥,>}, с N.

В случае, если все ограничения GA(t) перехода t автомата A выполняются в некоторый момент времени, когда данный переход активен, то переход может сработать.

ResetA: TA{reset(x)|xXA} – функция, сопоставляющая каждому переходу набор счетчиков времени, сбрасывающих свои значения в ноль при выполнении этого перехода. Сбросы счетчиков могут отсутствовать в некотором переходе, это означается, что ни одно из значений счетчиков при выполнении этого перехода в ноль не сбрасывается. Так же возможно сбрасывать значения сразу нескольких счетчиков при выполнении одного перехода.

Состояние системы Y – это отображение вершины системной сети в мультимножество пар: агент A и его состояние S.

Теперь дадим определение, что будем называть состоянием агента в случае TRDAPetri nets и TRDATimed automata и как будет выполняться модель.



TRDATimed automata:

Возможны следующие варианты смены состояний агента:

  1. агент находится в некотором состоянии, и ни один из его переходов не активен

  2. агент имеет один или несколько активных переходов, и ожидает того, что ограничение на одном или нескольких переходах станет выполняться

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

  4. агент закончил выполнение перехода, произвел все соответственные ресурсы, изменил показания счетчиков (согласно заданным во входном файле правилам), перешел в следующую позицию

Более детальное пояснение приведено ниже. Пусть переходы tr1 и tr2 агента α активны в состоянии s.

После загрузки системы все счетчики принимают значения 0. В случае, если в процессе работы системы создается новый агент, т.е. новая автоматная сеть, а с ней и новые счетчики, то они получают начальные значения так же равные 0. В случае, если на текущий момент, у нас есть два активных (с точки зрения наличия необходимых для их выполнения ресурсов) перехода tr1 и tr2, рассматриваются их ограничения (охранники). В случае, если ограничение ни на перехода tr1, ни на переходе tr2 не выполняется, значения счетчиков (совместно с глобальным временем системы) увеличивается до тех пор, пока одно их ограничений не начнет выполняться. ( В случае, если ограничения на переходах tr1 и tr2 выполняются одновременно, то переход для выполнения выбирается либо случайным образом с учетом весовых коэффициентов вероятности соответствующих переходов, либо на усмотрение пользователя.) Затем для того перехода, для которого выполнилось ограничение, начинается отчет длительности выполнения перехода. В конце выполнения перехода осуществляется обнуление счетчиков, указанных в спецификации reset данного перехода. После этого агент производит все ресурсы, указанные в выходных термах перехода.

Если в системе нет активных (имеющих активные переходы) агентов, то рассматривается множество работающих агентов и их временные характеристики - оставшееся время выполнения работающих переходов. Находится минимальное время: timemin. Время всех агентов перевычисляется путем вычитания timemin и те агенты, которые получили время 0, завершают работу своего перехода и производят ресурсы, предусмотренные для этого перехода.

TRDAPetri nets

Возможны следующие варианты смены состояний агента:


  1. агент находится в некотором состоянии, и ни один из его переходов не активен

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

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

  4. агент закончил выполнение перехода, произвел все соответственные ресурсы, перешел в следующую позицию

. Пусть Y некоторое состояние системы, и пусть переходы tr1 и tr2 агента α активны в состоянии s.

Тогда агент α переходит в состояние {, }, где wi - время ожидания начала работы перехода tri, выбранное из соответствующих временных интервалов переходов tr1 и tr2. В дальнейшем возможны три варианта: если w1w2 и если w1=w2.

В первом случае, по истечению w1, для перехода tr1 определится время t1, выбранное из своего соответствующего интервала, означающее длительности работы перехода tr1. Во втором случае, по истечению w2, для перехода tr2 определится время t2, выбранное из своего соответствующего интервала, означающее длительности работы перехода tr2. В третьем случае, в ход вступает весовой коэффициент вероятности, заданный для переходов (либо, в случае пошагового выполнения, решение принимает пользователь). Если для перехода весовой коэффициент вероятности не задан, то, по умолчанию весовой коэффициент равен 100 (для всех переходов). Если весовые коэффициенты вероятности конкурирующих переходов одинаковые, то вероятность их выполнения так же одинаковая. Согласно имеющимся весовым коэффициентам вероятности, система решает, какой переход будет работать. И для соответствующего перехода определится время ti – длительность выполнения этого перехода. По окончании работы перехода агент производит все ресурсы, указанные в выходных термах перехода.

Если в системе нет активных агентов, то поведение системы аналогично поведению модели TRDATimed automata в аналогичной ситуации.




Каталог: data -> 2013
2013 -> Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки «Журналистика»
2013 -> Программа дисциплины концепции и концептуальный анализ в математике и гуманитарном знании
2013 -> "Применение инструментов конкурентной разведки для анализа конкурентоспособности компании"
2013 -> Программа учебной дисциплины «Психология»
2013 -> Сетевой образовательный клуб «Некрасовская республика»: самоорганизация, саморазвитие, сотворчество. «Некрасовская республика»
2013 -> Информационное сопровождение бизнес проектов


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   21


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница