DEVS

From Wikipedia, the free encyclopedia

DEVS abbreviating Discrete Event System Specification is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state systems which might be described by differential equations (or continuous systems), and hybrid continuous state and discrete event systems.

1 History
2 Formalism
3 Analysis Methods
4 Variations of DEVS
5 Other Formalisms
6 External links
7 Footnotes
8 References

[edit] History

DEVS is a formalism for modeling and analysis of discrete event systems (DESs). DEVS formalism was invented by Dr. Bernard P. Zeigler who is currently a professor at the University of Arizona in 2007, and was introduced to the public in his first book Theory of Modeling and Simulation in 1976 when he was an associate professor at University of Michigan. DEVS can be seen as an extension of automaton ^[1] by adding

the real-value time base,
the modular concept with input and output events [Zeigler76], and
the hierarchical concept with the coupling operation [Zeigler84].

Zeigler proposed a hierarchical simulation algorithm for DEVS model simulation in 1984 [Zeigler84] which was published in Simulation journal in 1987. Since then, many extended formalism from DEVS have been introduced with their own purposes: DESS/DEVS for combinded continuous and discrete event systems, P-DEVS for parallel DESs, G-DEVS for piecewise linear state trajectory modeling of DESs, RT-DEVS for realtime DESs, Cell-DEVS for cellular DESs, Fuzzy-DEVS for fuzzy DESs, Dynamic Structuring DEVS for DESs changing their coupling structures dynamically, and so on. In addition to its extensions, there are some subclasses such as SP-DEVS and FD-DEVS have been researched for achieving decidability of system properties.

Due to the modular and hierarchical modeling views as well as its simulation-based analysis capability, DEVS formalism and its variantions have been used in many application of engineering (such as hardware design, hardware/software codesign, communication systems, manufacturing systems) and science (such as biology, and sociology).

[edit] Formalism

The following formal definition is for Classic DEVS [ZKP00].

Atomic DEVS

An atomic DEVS model is defined as a 7-tuple

   $M = < X, Y, S,τ,δ e x t,δ i n t,λ >$

where

$X$ is the set of input events;

$Y$ is the set of output events;

$S$ is the set of sequential states;

$\tau:S \rightarrow \mathbb{R}_{[0,\infty]}$ is the time advance function which is used to determine the lifespan of a state where $\mathbb{R}_{[0,\infty]}$ is the set of non-negative real numbers plus infinity;

$\delta_{ext}:Q \times X \rightarrow S$ is the external state transition function which defines how an input event changes a state of the system, where $Q=\{(s,t_e)|s \in S, 0 \le t_e \le \tau(s) \}$ and $t e$ is the elapsed time since the last event;

$\delta_{int}:S \rightarrow S$ is the internal state transition function which defines how a state of the system changes internally (when the elapsed time reaches to the lifetime of the state);

$\lambda:S \rightarrow Y$ is the output function which defines how a state of the system generates an output event (when the elapsed time reaches to the lifetime of the state);

Behavior of Atomic DEVS

There are two cases that an atomic DEVS model $M$ can change its state $s \in S$ : (1) when an external input $x \in X$ comes into the system $M$ ; (2) when the elapsed time $t e$ reaches the lifespan of $s$ which is defined by $τ(s)$ . (At the same time of (2), $M$ generates an output $y \in Y$ which is defined by $λ(s)$ .)

Coupled DEVS

The coupled DEVS defines which sub-components belong to it and how they are connected with each other. A coupled DEVS model is defined as a 8-tuple $N = < X, Y, D,{M i}, C x x, C y x, C y y, S e l e c t >$ where

$X$ is the set of input events;

$Y$ is the set of output events;

$D$ is the name set of sub-components;

${M i}$ is the set of sub-components where for each $i \in D, M_i$ can be either an atomic DEVS model or a coupled DEVS model.

$C_{xx}\subseteq X \times \bigcup_{i \in D} X_i$ is the set of external input couplings;

$C_{yx}\subseteq \bigcup_{i \in D} Y_i \times \bigcup_{i \in D} X_i$ is the set of internal couplings;

$C_{yy}\subseteq \bigcup_{i \in D} Y_i \times Y$ is the set of external output couplings;

$Select:2^D \rightarrow D$ is the tie-breaking function which defines how to select the event from the set of simulataneous events;

Behavior of Coupled DEVS

Like the behavior of the atomic DEVS class, a coupled DEVS model $N$ changes its components' states (1) when an external event $x \in X$ comes into $N$ ; (2) when one of components $M i$ where $i \in D$ executes its internal state transition and generates its output $y_i \in Y_i$ . In both cases (1) and (2), a triggering event is transmitted to all influencees which are defined by coupling sets $C x x, C y x,$ and $C y y$ .

[edit] Analysis Methods

Simulation for Discrete Event Systems

The simulation algorithm of DEVS models considers two issues: time synchronization and message propagation. Time synchronization of DEVS is to control all models to have the identical current time. However, for an efficient execution, the algorithm makes the current time jump to the most urgent time when an event is scheduled to execute its internal state transition as well as its output generation. Message propagation is to transmit a triggering message which can be either an input or output event along the associated couplings which are defined in a coupled DEVS model. For more detailed information, the reader can refer to [Zeigler84] [Zeigler87] [ZKP00].

Simulation for Continuous State Systems

By introducing quantization, DEVS can simulate behaviors of continuous state systems which are described by networks of differential algebraic equations. This research has been initiated by Zeigler in 90's and many properties have been clarified by Prof. Kofman in 2000's and Dr. Nutaro. In 2006, Prof. Cellier who is the author of Continous System Modeling[Cellier91], and Prof. Kofman wrote a text book, Continuous System Simulation[CK06] in which Chapters 11 and 12 cover how DEVS simulates continuous state systems.

Verification for Discrete Event Systems

As an alternative analysis method against the sampling-based simulation method, an exhaustive generating approach, generally called ``verification`` has been applied for analysis of DEVS models. Based-on a finite-vertex reachabiligy graph which is behaviorally isomorphic to the original DEVS models, (1) dead-lock and live-lock freeness as qualitative properties are decidable with Schedule-Preserving DEVS (SP-DEVS) and Finite & Deterministic DEVS (FD-DEVS), and (2) min/max processing time bounds as a quantitative property are decidable with SP-DEVS so far in 2007.

[edit] Variations of DEVS

Extensions

Please help improve this article or section by expanding it.
Further information might be found on the talk page or at requests for expansion. (November 2007)

Symbolic DEVS, Parallel DEVS, Real-Time DEVS, Fuzzy-DEVS, Dynamic Structuring DEVS, G-DEVS, Cell-DEVS, GK-DEVS, G-DEVS

Restrictions

There are some sub-classes known as Schedule-Preserving DEVS (SP-DEVS) and Finite and Deterministic DEVS (FD-DEVS) which were designated to support verification analysis. SP-DEVS and FD-DEVS whose expressiveness are E(SP-DEVS) $\subset$ E(FD-DEVS) $\subset$ E(DEVS) where E(formalism) denotes the expresiveness of formalimsm.

[edit] Other Formalisms

Automata Theory: a formal method for state transition systems
Petri Nets: graphical representations of state and transition relations

[edit] External links

Alphabetical Order

DEVS Standardization Group: http://www.sce.carleton.ca/faculty/wainer/standard/
DEVS Study Group: http://tech.groups.yahoo.com/group/DEVSTD/
DEVS Tools: http://www.sce.carleton.ca/faculty/wainer/standard/tools.htm
Dr. Barros' Lab at Universidade de Coimbra: http://eden.dei.uc.pt/~barros/
Dr. Jamshidi's Virtual Laboratory for Autonomous Agenets at University of New Mexico: http://vlab.unm.edu/
Dr. Giambiasi's Lab at Laboratoire des Sciences de I'Information et des Systemes (LSIS): http://www.lsis.org/fiche.php?id=72&page=&afficher=&presentation_publis=&processus=ok
Dr. Hans' Modeling, Simulation & Design Lab at McGill University: http://moncs.cs.mcgill.ca/people/hv
Dr. Hu's Lab at Georgia State University: http://www.cs.gsu.edu/~cscxlh/
Dr. Hwang's Homepage: http://moonho.hwang.googlepages.com/
Dr. Kim's Systems Modeling Simulation Lab at KAIST: http://smslab.kaist.ac.kr/
Dr. Kofman's Laboratory for System Dynamics and Signal Processing at Universidad Nacional de Rosario: http://www.fceia.unr.edu.ar/lsd/
Dr. Mittal's Homepage: http://saurabh-mittal.com/
Dr. Wainer's Lab at Carleton University: http://www.sce.carleton.ca/faculty/wainer/news.htm
Dr. Zeigler and Dr. Sarjoughian's Arizona Center for Integrative Modeling and Simulation (ACIMS): http://www.acims.arizona.edu/
Dr. rer. nat.Adelinde M. Uhrmacher 's Modeling and Simulation Group at University of Rostock: http://wwwmosi.informatik.uni-rostock.de/mosi

[edit] Footnotes

^ automata were the mathematical models of Dr. Zeigler's Ph.D. thesis [Zeigler68]

[edit] References

[Cellier91] Francois E. Cellier (1991). Continuous System Modeling, first, Springer. ISBN 978-0387975023.
[CK06] Francois E. Cellier and Ernesto Kofman (2006). Continuous System Simulation, first, Springer. ISBN 978-0387261027.
[Zeiger68] Bernard Zeigler (1968). On the Feedback Complexity of Automata, Ph.D. Thesis, University of Michigan.
[Zeigler76] Bernard Zeigler (1976). Theory of Modeling and Simulation, first, Wiley Interscience, New York.
[Zeigler84] Bernard Zeigler (1984). Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando. ISBN 978-0127784502.
[Zeigler87] Bernard Zeigler (1987). "Hierarchical, modular discrete-event modelling in an object-oriented environment". SIMULATION 49: 219–230. doi:10.1177/003754978704900506.
[ZKP00] Bernard Zeigler, Tag Gon Kim, Herbert Praehofer (2000). Theory of Modeling and Simulation, second, Academic Press, New York. ISBN 978-0127784557.

Categories: Automata theory

DEVS

From Wikipedia, the free encyclopedia

Contents

[edit] History

[edit] Formalism

[edit] Analysis Methods

[edit] Variations of DEVS

[edit] Other Formalisms

[edit] External links

[edit] Footnotes

[edit] References

Views

Navigation

Interaction

Search

Languages