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

Концепция в моделировании и системном анализе

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

История

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

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

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

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

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

Формализм

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

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

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

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

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

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

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

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

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

где

• ${\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}$— внешняя функция перехода , которая определяет, как входное событие изменяет состояние системы, где — множество всех состояний , а — время, прошедшее с момента последнего события ; ^[2] ${\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}}$ ${\displaystyle t_{e}}$

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

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

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

${\displaystyle {\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 может изменить свое состояние : (1) когда в систему поступает внешний вход ; (2) когда прошедшее время достигает срока службы , который определяется как . (В то же время (2) генерирует выход , который определяется как .) . ${\displaystyle M}$ ${\displaystyle s\in S}$ ${\displaystyle x\in X}$ ${\displaystyle M}$ ${\displaystyle t_{e}}$ ${\displaystyle s}$ ${\displaystyle ta(s)}$ ${\displaystyle M}$ ${\displaystyle y\in Y}$ ${\displaystyle \lambda (s)}$

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

Связанные DEVS

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

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

где

• ${\displaystyle X}$— это набор входных событий ;
• ${\displaystyle Y}$— набор выходных событий ;
• ${\displaystyle D}$— это набор имен подкомпонентов ;
• ${\displaystyle \{M_{i}\}}$представляет собой набор подкомпонентов , где для каждого может быть либо атомарная модель DEVS, либо связанная модель DEVS. ${\displaystyle i\in D,M_{i}}$
• ${\displaystyle C_{xx}\subseteq X\times \bigcup _{i\in D}X_{i}}$- набор внешних входных муфт ;
• ${\displaystyle C_{yx}\subseteq \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=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$ ${\displaystyle X=\{\}}$ ${\displaystyle Y=\{\}}$ ${\displaystyle D=\{A,B\}}$ ${\displaystyle M_{A}{\text{ and }}M_{B}}$ ${\displaystyle C_{xx}=\{\}}$ ${\displaystyle C_{yx}=\{(A.!send,B.?receive),(B.!send,A.?receive)\}}$ ${\displaystyle C_{yy}(A.!send)=\phi ,C_{yy}(B.!send)=\phi }$

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

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

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

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

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

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

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

Вводя метод квантования, который абстрагирует непрерывный сегмент как кусочно-константный сегмент, DEVS может моделировать поведение непрерывных систем состояний, которые описываются сетями дифференциальных алгебраических уравнений . Это исследование было инициировано Зейглером в 1990-х годах ^[3] , и многие свойства были разъяснены профессором Кофманом в 2000-х годах и доктором Нутаро. В 2006 году профессор Селье, который является автором Continuous System Modeling [Cellier91], и профессор Кофман написали учебник Continuous System Simulation [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

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

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

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

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

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

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

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

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

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

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

Сноски

1. Автоматы были математическими моделями докторской диссертации доктора Зейглера [Zeigler68]
2. Мы также можем определить внешнюю функцию перехода как , где так, что для полного состояния , является частичным состоянием, является продолжительностью жизни , а является временем, прошедшим с момента последнего обновления . Для получения дополнительной информации о том, как понять эту функцию, обратитесь к статье Поведение DEVS . ${\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}}$ ${\displaystyle Q=S\times \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}}$
3. использование квантованных значений для моделирования непрерывных систем с помощью метода дискретных событий было эмпирически опробовано несколькими годами ранее - в начале 1990-х годов - французским инженером <Нам нужна любая ссылка для этого аргумента>. Тогда он работал в компании, отделившейся от Университета Валансьена , а теперь являющейся частью Schneider Electric . Это квантование является функцией программного обеспечения для моделирования , концептуалистом и основным разработчиком которого является этот инженер , которое используется для проверки программ ПЛК и обучения операторов.

Ссылки

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