РАЗРАБОТЧИКИ

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

История

DEVS — это формализм для моделирования и анализа систем дискретных событий (DES). Формализм DEVS был изобретен Бернардом Зейглером , почетным профессором Университета Аризоны . DEVS был представлен публике в первой книге Зейглера « Теория моделирования и симуляции», заархивированной 21 июня 2012 г. в Wayback Machine , в 1976 году, когда Зейглер был доцентом Мичиганского университета . DEVS можно рассматривать как расширение формализма машины Мура . ^[1] который представляет собой конечный автомат, в котором выходные данные определяются только текущим состоянием (и не зависят напрямую от входных данных). Расширение было сделано

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

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

Зейглер предложил иерархический алгоритм для моделирования модели DEVS в 1984 году [Zeigler84] , который был опубликован в журнале Simulation в 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 и его вариации использовались во многих инженерных приложениях (таких как проектирование аппаратного обеспечения, разработка кода аппаратного / программного обеспечения, системы связи , производственные системы). и наука (например , биология и социология )

Формализм

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

DEVS определяет поведение системы, а также ее структуру. Поведение системы в формализме DEVS описывается с использованием входных и выходных событий, а также состояний. Например, для игрока в пинг-понг, показанного на рис. 1, входное событие — ?receive , а выходное событие — !send . У каждого игрока A , B есть свои состояния: Отправить и Ожидать . Состояние отправки занимает 0,1 секунды для отправки мяча обратно, что является выходным событием !send , а состояние ожидания длится до тех пор, пока игрок не получит мяч, что является входным событием ?receive .

Структура игры в пинг-понг заключается в соединении двух игроков: игрока A ! выходное событие send передается B игрока входному событию ?receive , и наоборот.

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

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

Атомные разработки

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

M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >

где

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

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

Представлена атомарная модель DEVS для игрока А на рис. 1. Игрок= $<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >$ такой, что

${\begin{aligned}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)\\ta(s)&=\sigma {\text{ for all }}s\in S\\\delta _{ext}((({\textit {Wait}},\sigma ),t_{e}),?{\textit {receive}})&=({\textit {Send}},0.1)\\\delta _{int}({\textit {Send}},\sigma )&=({\textit {Wait}},\infty )\\\delta _{int}({\textit {Wait}},\sigma )&=({\textit {Send}},0.1)\\\lambda ({\textit {Send}},\sigma )&=!{\textit {send}}\\\lambda ({\textit {Wait}},\sigma )&=\phi \end{aligned}}$

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

Поведение атомного DEVS

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

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

Связанные ДЕВС

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

N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>

где

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

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

Игру в пинг-понг, показанную на рис. 1, можно смоделировать как связанную модель DEVS. $N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>$ где $X=\{\}$ ; $Y=\{\}$ ; $D=\{A,B\}$ ; $M_{A}{\text{ and }}M_{B}$ описано выше; $C_{xx}=\{\}$ ; $C_{yx}=\{(A.!send,B.?receive),(B.!send,A.?receive)\}$ ; и $C_{yy}(A.!send)=\phi ,C_{yy}(B.!send)=\phi$ .

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

Проще говоря, как и поведение атомарного класса DEVS, связанная модель DEVS $N$ меняет состояние своих компонентов (1) при внешнем событии $x\in X$ приходит в $N$ ; (2) когда один из компонентов $M_{i}$ где $i\in D$ выполняет переход внутреннего состояния и генерирует выходные данные $y_{i}\in Y_{i}$ . В обоих случаях (1) и (2) событие срабатывания передается всем воздействиям, которые определяются наборами связей. $C_{xx},C_{yx},$ и $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] и конечное и детерминированное DEVS (FRT-DEVS) [Hwang12] . В результате, на основе графика восстанавливаемости, (1) отсутствие взаимоблокировок и активных блокировок как качественные свойства можно определить с помощью SP-DEVS [Hwang05] , FD-DEVS [HZ06] и FRT-DEVS [Hwang12] ; и (2) границы минимального/максимального времени обработки как количественная характеристика могут быть определены с помощью SP-DEVS к 2012 году.

Варианты ДЕВС

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

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

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

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

Существуют некоторые подклассы, известные как DEVS с сохранением расписания ( SP-DEVS ) и конечные и детерминированные DEVS ( FD-DEVS ), которые были предназначены для поддержки проверочного анализа. SP-DEVS и FD-DEVS, выразительность которых равна E ( SP-DEVS ). $\subset$ Э ( ФД-ДЕВС ) $\subset$ E (DEVS), где E ( формализм ) обозначает выразительность формализма .

См. также

Статьи, связанные с DEVS

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

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

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

Сноски

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

Ссылки

[Селье91] Франсуа Э. Селье (1991). Непрерывное системное моделирование (первое изд.). Спрингер. ISBN 978-0-387-97502-3 .
[CK06] Франсуа Э. Селье; Эрнесто Кофман (2006). Непрерывное системное моделирование (первое изд.). Спрингер. ISBN 978-0-387-26102-7 .
[Giambiasi01] Джамбиаси Н., Эскьюд Б. Гош С. «Обобщенное дискретно-событийное моделирование динамических систем», в: Выпуск 4 транзакций SCS: последние достижения в методологии DEVS, часть II, Vol. 18, стр. 216–229, декабрь 2001 г.
[Hwang05] MH Hwang, «Учебное пособие: Верификация системы реального времени на основе DEVS с сохранением расписания», Материалы симпозиума DEVS 2005 г. , Сан-Диего, 2–8 апреля 2005 г., ISBN 1-56555-293-8 ,
[HZ06] М. Х. Хван и Б. П. Зейглер, «Модульная структура проверки с использованием конечных и детерминированных DEVS», Материалы симпозиума DEVS 2006 г. , стр. 57–65, Хантсвилл, Алабама, США,
[HZ09] М. Х. Хван и Б. П. Зейглер, «Граф достижимости конечных и детерминированных сетей DEVS», IEEE Transactions on Automation Science and Engineering , том 6, выпуск 3, 2009 г., стр. 454–467,
[Hwang12] М. Х. Хван, «Качественная проверка сетей DEVS конечного уровня и реального времени», Труды симпозиума 2012 г. по теории моделирования и симуляции – Интегративный симпозиум M&S DEVS , статья № 43,
[Миттал13] Саураб Миттал; Хосе Л. Риско Мартин (2013). Сетецентрическая система системного проектирования с унифицированным процессом DEVS (первое изд.). ЦРК Пресс. ISBN 978-1439827062 .
[Нутаро10] Джеймс Нутаро (2010). Создание программного обеспечения для моделирования: теория, алгоритмы и приложения на C ++ (первое изд.). Уайли. ISBN 978-0-470-41469-9 .
[Сарджугян09] Хессам С. Сарджокян; Винеш Эламважути (2009). «CoSMoS: визуальная среда для компонентного моделирования, экспериментального проектирования и моделирования». Материалы международной конференции по средствам и методам моделирования. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
[Вайнер09] Габриэль А. Вайнер (2009). Дискретно-событийное моделирование и моделирование: практический подход (первое изд.). ЦРК Пресс. ISBN 978-1-4200-5336-4 .
[Вайнер10] Габриэль А. Вайнер и Питер Мостерман, ред. (2010). Дискретно-событийное моделирование и моделирование: теория и приложения (первое изд.). ЦРК Пресс. ISBN 978-1-4200-7233-4 .
[Zacharewicz08] Грегори Захаревич, Клаудия Фридман и Норберт Джамбиаси (2008) Среда G-DEVS/HLA для распределенного моделирования рабочих процессов, SIMULATION, май 2008 г., 84: 197–213, дои : 10.1177/0037549708092833 .
[Указатель68] Бернард Зейглер (1968). О сложности обратной связи автоматов (ред. Кандидатская диссертация). Мичиганский университет.
[Зейглер76] Бернард Зейглер (1976). Теория моделирования и симуляции (первое изд.). Wiley Interscience, Нью-Йорк. ISBN 0-12-778455-1 .
[Зейглер84] Бернард Зейглер (1984). Многогранное моделирование и дискретное моделирование событий . Академическая пресса, Лондон; Орландо. ISBN 978-0-12-778450-2 .
[Зейглер87] Бернард Зейглер (1987). «Иерархическое, модульное дискретно-событийное моделирование в объектно-ориентированной среде». Моделирование . 49 (5): 219–230. дои : 10.1177/003754978704900506 . S2CID 62648626 .
[ЗКП00] Бернард Зейглер; Таг Гон Ким; Герберт Прехофер (2000). Теория моделирования и симуляции (второе изд.). Академик Пресс, Нью-Йорк. ISBN 978-0-12-778455-7 .

[1] автоматы были математическими моделями доктора философии Зейглера. диссертация [Zeigler68]

[2] Мы также можем определить внешнюю функцию перехода как $\delta _{ext}:Q\times X\rightarrow S\times \{0,1\}$ где $Q=S\times \mathbb {T} ^{\infty }\times \mathbb {T}$ такое, что для полного состояния $(s,t_{s},t_{e})\in Q$ , $s\in S$ является частичным состоянием, $t_{s}\in \mathbb {T} ^{\infty }$ это продолжительность жизни $s$ , и $t_{e}\in (\mathbb {T} \cap [0,t_{s}])$ это время, прошедшее с момента последнего обновления $t_{s}$ . Подробнее о том, как понять эту функцию, читайте в статье « Поведение DEVS» .

[3] использование квантованных величин для моделирования непрерывных систем с помощью метода дискретных событий было эмпирически опробовано несколькими годами ранее - в начале 1990-х годов - французским инженером <Нам нужна какая-либо ссылка для этого аргумента>. Тогда он работал в компании, выделенной из Университета Валансьена , а теперь являющейся частью Schneider Electric . Это квантование является особенностью для моделирования программного обеспечения которого является этот инженер , концептуальным и главным разработчиком , и которое используется для проверки программ ПЛК и обучения операторов.

[1]

[2]

[3]