DEVS - Википедия - DEVS

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

История

DEVS, аббревиатура Discrete Event System Specification - это модульный и иерархический формализм для моделирования и анализа общих систем, которые могут быть дискретными системами событий, которые могут быть описаны таблицами переходов состояний, и системами непрерывного состояния, которые могут быть описаны дифференциальными уравнениями, и гибридными ... DEVS - это формализм для моделирования и анализа дискретных систем событий (DES). Формализм DEVS был изобретен Бернард П. Зейглер, который является заслуженным профессором Университет Аризоны. DEVS была представлена публике в первой книге Зейглера, Теория моделирования и моделирования, в 1976 году, в то время как Зиглер был доцентом в университет Мичигана. DEVS можно рассматривать как расширение Машина Мура формализм,^[1] который является конечным автоматом, в котором выходы определяются только текущим состоянием (и не зависят напрямую от входа). Расширение было выполнено

связывая продолжительность жизни с каждым состоянием [Zeigler76],
предоставление иерархической концепции с помощью операции, называемой связь [Zeigler84].

Поскольку продолжительность жизни каждого состояния является действительным числом (точнее, неотрицательным вещественным числом) или бесконечностью, оно отличается от систем с дискретным временем, последовательных машин и Машины Мура, в котором время определяется временем тика, умноженным на неотрицательные целые числа. Более того, продолжительность жизни может быть случайная переменная; например, продолжительность жизни данного состояния может быть распределена экспоненциально или равномерно. Функции перехода между состояниями и вывода DEVS также могут быть стохастический.

Цейглер предложил иерархический алгоритм моделирования модели DEVS в 1984 году. [Zeigler84] который был опубликован в Моделирование journal в 1987 году. С тех пор многие расширенные формализмы от DEVS были введены с собственными целями: DESS / DEVS для комбинированных непрерывных и дискретных систем событий, P-DEVS для параллельных DES, G-DEVS для кусочно-непрерывного моделирования траекторий DES, RT-DEVS для DES в реальном времени, Cell-DEVS для сотовых DES, Fuzzy-DEVS для нечетких DES, DEVS динамического структурирования для DES, динамически изменяющих свои структуры связи, и так далее. В дополнение к его расширениям есть несколько подклассов, таких как SP-DEVS и FD-DEVS были исследованы для достижения разрешимости свойств системы.

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

Формализм

Рис. 1. Модель DEVS для игры в пинг-понг.

Интуитивный пример

DEVS определяет поведение системы, а также структуру системы. Поведение системы в формализме DEVS описывается с помощью входных и выходных событий, а также состояний. Например, для игрока в пинг-понг на рис. 1 входным событием является ?получить, а выходное событие !Отправить. Каждый игрок, А, B, имеет свои состояния: послать и Подождите. послать состояние занимает 0,1 секунды, чтобы отправить обратно мяч, который является выходным событием !Отправить, в то время как Подождите состояние длится до тех пор, пока игрок не получит мяч, который является входным событием ?получить.

Структура игры в пинг-понг состоит в том, чтобы соединить двух игроков: Игрок А событие вывода !Отправить передается игроку B событие ввода ?получить, и наоборот.

В классическом формализме DEVS Атомные DEVS фиксирует поведение системы, а Связанные DEVS описывает структуру системы.

Следующее формальное определение предназначено для Classic DEVS [ZKP00]. В этой статье мы будем использовать временную базу, ${ Displaystyle mathbb {T} = [0, infty)}$ это набор неотрицательных действительных чисел; расширенная временная база, ${ Displaystyle mathbb {T} ^ { infty} = [0, infty]}$ это набор неотрицательных действительных чисел плюс бесконечность.

Атомные DEVS

Атомарная модель DEVS определяется как 7-кортеж

{ displaystyle M = }

где

${ displaystyle X}$ является набор входных событий;
${ displaystyle Y}$ является набор выходных событий;
${ displaystyle S}$ является набор последовательных состояний (или также называемый набор частичных состояний);
${ displaystyle s_ {0} in S}$ является начальное состояние;
${ displaystyle ta: S rightarrow mathbb {T} ^ { infty}}$ является функция опережения времени который используется для определения продолжительности жизни состояния;
${ displaystyle delta _ {ext}: Q times X rightarrow S}$ является функция внешнего перехода который определяет, как входное событие изменяет состояние системы, где ${ Displaystyle Q = {(s, t_ {e}) | s in S, t_ {e} in ( mathbb {T} cap [0, ta (s)]) }}$ это набор общих состояний, и ${ displaystyle t_ {e}}$ это пройденное время поскольку последнее событие;
^[2]

${ displaystyle delta _ {int}: S rightarrow S}$ является функция внутреннего перехода который определяет, как состояние системы изменяется внутри (когда прошедшее время достигает времени жизни состояния);
${ displaystyle lambda: S rightarrow Y ^ { phi}}$ является функция вывода где ${ Displaystyle Y ^ { phi} = Y чашка { phi }}$ и ${ displaystyle phi not in Y}$ это тихий событие или ненаблюдаемый мероприятие. Эта функция определяет, как состояние системы генерирует выходное событие (когда прошедшее время достигает времени существования состояния);

Атомная модель DEVS для игроков в пинг-понг

Атомарной модели DEVS для игрока A на рис. 1 задано Player = ${ displaystyle }$ такой, что

${ displaystyle { begin {align} X & = {? { textit {receive}} } Y & = {! { textit {send}} } S & = {(d, sigma ) | d in {{ textit {Wait}}, { textit {Send}} }, sigma in mathbb {T} ^ { infty} } s_ {0} & = ( { textit {Send}}, 0.1) t_ {a} (s) & = sigma { text {для всех}} s in S delta _ {ext} ((({ textit { Подождите}}, sigma), t_ {e}),? { Textit {receive}}) & = ({ textit {Send}}, 0.1) delta _ {int} ({ textit {Отправить }}, sigma) & = ({ textit {Wait}}, infty) delta _ {int} ({ textit {Wait}}, sigma) & = ({ textit {Send}} , 0,1) lambda ({ textit {Send}}, sigma) & =! { Textit {send}} lambda ({ textit {Wait}}, sigma) & = phi конец {выровнен}}}$

И игрок A, и игрок B являются атомарными моделями DEVS.

Поведение атомных DEVS

Проще говоря, есть два случая, когда атомарная модель DEVS ${ displaystyle M}$ может изменить свое состояние ${ displaystyle s in S}$ : (1) когда внешний вход ${ displaystyle x in X}$ входит в систему ${ displaystyle M}$ ; (2) когда истекшее время ${ displaystyle t_ {e}}$ достигает продолжительности жизни ${ displaystyle s}$ который определяется ${ displaystyle ta (s)}$ . (В то же время из (2), ${ displaystyle M}$ генерирует вывод ${ displaystyle y in Y}$ который определяется ${ displaystyle lambda (s)}$ .) .

Для формального описания поведения данной модели Atomic DEVS см. Страницу Поведение DEVS. Компьютерные алгоритмы для реализации поведения данной модели Atomic DEVS доступны по адресу Алгоритмы моделирования для атомарных DEVS.

Связанные DEVS

Связанный DEVS определяет, какие подкомпоненты ему принадлежат и как они связаны друг с другом. Связанная модель DEVS определяется как 8-кортеж

{ displaystyle N = }

где

${ displaystyle X}$ является набор входных событий;
${ displaystyle Y}$ является набор выходных событий;
${ displaystyle D}$ является набор имен подкомпонентов;
${ displaystyle {M_ {i} }}$ является набор подкомпонентов где для каждого ${ displaystyle i in D, M_ {i}}$ может быть либо атомарной моделью DEVS, либо связанной моделью DEVS.
${ displaystyle C_ {xx} substeq X times bigcup _ {я in D} X_ {i}}$ является набор внешних входных муфт;
${ displaystyle C_ {yx} substeq bigcup _ {i in D} Y_ {i} times bigcup _ {i in D} X_ {i}}$ является комплект внутренних муфт;
${ displaystyle C_ {yy}: bigcup _ {i in D} Y_ {i} rightarrow Y ^ { phi}}$ является функция связи внешнего выхода;
${ displaystyle Select: 2 ^ {D} rightarrow D}$ является функция разрыва связи который определяет, как выбрать событие из набора одновременных событий;

Совместная модель DEVS для игры в пинг-понг

Игра в пинг-понг, показанная на рис.1, может быть смоделирована как связанная модель DEVS. ${ displaystyle N = }$ где ${ Displaystyle X = {}}$ ; ${ Displaystyle Y = {}}$ ; ${ Displaystyle D = {А, В }}$ ; ${ displaystyle M_ {A} { text {и}} M_ {B}}$ описано выше; ${ Displaystyle C_ {хх} = {}}$ ; ${ displaystyle C_ {yx} = {(A.! отправить, B.? получить), (B.! отправить, A.? получить) }}$ ; и ${ displaystyle C_ {yy} (A.! send) = phi, C_ {yy} (B.! send) = phi}$ .

Поведение связанных DEVS

Проще говоря, как и поведение атомарного класса DEVS, связанная модель DEVS ${ displaystyle N}$ изменяет состояния своих компонентов (1), когда внешнее событие ${ displaystyle x in X}$ входит в ${ displaystyle N}$ ; (2) когда один из компонентов ${ displaystyle M_ {i}}$ где ${ displaystyle i in D}$ выполняет переход внутреннего состояния и генерирует выходные данные ${ displaystyle y_ {i} in Y_ {i}}$ . В обоих случаях (1) и (2) инициирующее событие передается на все воздействия, которые определяются связующими наборами. ${ displaystyle C_ {xx}, C_ {yx},}$ и ${ displaystyle C_ {yy}}$ .

Для формального определения поведения связанных DEVS вы можете обратиться к Поведение связанных DEVS. Компьютерные алгоритмы для реализации поведения данного режима связанных DEVS доступны по адресу Алгоритмы моделирования для связанных DEVS.

Методы анализа

Моделирование дискретных систем событий

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

Моделирование систем с непрерывным состоянием

Путем введения метода квантования, который абстрагирует непрерывный сегмент как кусочно-константный сегмент, DEVS может моделировать поведение систем с непрерывным состоянием, которые описываются сетями дифференциально-алгебраические уравнения. Это исследование было инициировано Зейглером в 1990-х годах.^[3] и многие свойства были разъяснены профессором Кофманом в 2000-х годах и доктором Нутаро. В 2006 году профессор Селье, автор книги Непрерывное моделирование системы[Cellier91], а профессор Кофман написал учебник, Непрерывное моделирование системы[CK06] в главах 11 и 12 описывается, как DEVS моделирует системы с непрерывным состоянием. Книга доктора Нуаро [Nutaro10], охватывает также дискретное моделирование систем с непрерывным состоянием.

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

В качестве альтернативного метода анализа методу моделирования на основе выборки используется метод исчерпывающего генерирования поведения, обычно называемый проверка был применен для анализа моделей DEVS. Доказано, что бесконечные состояния данной модели DEVS (особенно связанной модели DEVS) могут быть абстрагированы поведенчески изоморфной конечной структурой, называемой график достижимости когда данная модель DEVS является подклассом DEVS, например, с сохранением расписания DEVS (SP-DEVS ), Конечные и детерминированные DEVS (FD-DEVS ) [HZ09], а также конечные устройства и устройства реального времени (FRT-DEVS) [Hwang12]. В результате, на основе графика доступности, (1) свобода тупиковой и динамической блокировки, поскольку качественные свойства решаются с помощью SP-DEVS. [Hwang05], FD-DEVS [HZ06], и FRT-DEVS [Hwang12]; и (2) минимальные / максимальные ограничения времени обработки как количественное свойство могут быть решены с помощью SP-DEVS к 2012 году.

Варианты DEVS

Расширения (суперклассы)

За последние десятилетия были разработаны многочисленные расширения классического формализма DEVS, в том числе формализмы, которые позволяют изменять структуру модели по мере эволюции времени моделирования.

G-DEVS [Giambiasi01] [Zacharewicz08], Параллельные DEVS, DEVS с динамическим структурированием, Cell-DEVS [Wainer09], dynDEVS, Fuzzy-DEVS, GK-DEVS, ml-DEVS, Symbolic DEVS, Real-Time DEVS, rho-DEVS

Ограничения (подклассы)

Есть несколько подклассов, известных как УСТРОЙСТВА с сохранением расписания (SP-DEVS ) и конечные и детерминированные DEVS (FD-DEVS ), которые были предназначены для поддержки проверочного анализа.SP-DEVS и FD-DEVS чья выразительность E(SP-DEVS ) ${ displaystyle subset}$ E(FD-DEVS ) ${ displaystyle subset}$ E(DEVS) где E(формализм) обозначает выразительность формализм.

Смотрите также

DEVS Статьи по теме

Сегмент события
Система синхронизированных событий
Поддающиеся проверке подклассы DEVS: SP-DEVS, FD-DEVS
Поведение атомных DEVS
Поведение связанных DEVS
Алгоритмы моделирования для атомарных DEVS
Алгоритмы моделирования для связанных DEVS

Другие формализмы

Теория автоматов: формальный метод для систем перехода состояний
Конечный автомат: машина перехода между состояниями с конечным набором событий и состояний
Сети Петри: графическое представление состояний и переходных отношений
Цепь Маркова: а стохастический процесс, в котором будущее будет определяться текущим состоянием
Спецификация и язык описания: SDL, формальный полный и однозначный язык для графического представления имитационных моделей.

Сноски

^ автоматы были математическими моделями доктора Зейглера, доктора философии. Тезис [Zeigler68]
^ Мы также можем определить внешнюю функцию перехода как ${ displaystyle delta _ {ext}: Q times X rightarrow S times {0,1 }}$ где ${ Displaystyle Q = S раз mathbb {T} ^ { infty} times mathbb {T}}$ так что для полного состояния ${ displaystyle (s, t_ {s}, t_ {e}) in Q}$ , ${ displaystyle s in S}$ частичное состояние, ${ displaystyle t_ {s} in mathbb {T} ^ { infty}}$ это продолжительность жизни ${ displaystyle s}$ , и ${ displaystyle t_ {e} in ( mathbb {T} cap [0, t_ {s}])}$ это время, прошедшее с последнее обновление из ${ displaystyle t_ {s}}$ . Подробнее о том, как понять эту функцию, читайте в статье Поведение DEVS.
^ использование квантованных значений для моделирования непрерывных систем с помощью дискретное событие метод был опробован эмпирически на несколько лет раньше - в начале 1990-х гг. Французский инженер <Нам нужна ссылка на этот аргумент>. Тогда он работал в компании, возникшей из Университет Валансьена, а теперь часть Schneider Electric. Этот квантование это особенность симуляция программного обеспечения из которых этот инженер является разработчиком и главным разработчик, который используется для ПЛК проверка программ и обучение операторов.