Behavior of DEVS

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Behaviors of a given DEVS model is a set of sequences of timed events including null events, called event segments which make the model move one state to another within a set of legal states. To define this way, the concept of a set of illegal state as well a set of legal states are needed to be introduced.

In addition, since the behaviors of a given DEVS model needs to define how the state transition change both when time is passed by and when an event occurs, it has been described by a much general formalism, called general system [ZPK00]. In this article, we use a sub-class of General System formalism, called timed event system instead.

Depending on how to define the total state and its external state transition function of DEVS, two ways to define the behavior of a DEVS model using Timed Event System. Since behavior of a coupled DEVS model is defined as an atomic DEVS model, behavior of coupled DEVS class is defined by timed event system.

View 1: total states = states * elapsed times[edit]

Suppose that a DEVS model, \mathcal{M}=<X,Y,S,s_0,ta,\delta_{ext},\delta_{int},\lambda> has

  1. the external state transition  \delta_{ext}:Q \times X \rightarrow S.
  2. the total state set Q=\{(s,t_e)| s \in S, t_e \in (\mathbb{T} \cap [0, ta(s)])\} where  t_e denotes elapsed time since last event and  \mathbb{T}=[0,\infty) denotes the set of non-negative real numbers, and


Then the DEVS model, \mathcal{M} is a Timed Event System \mathcal{G}=<Z,Q,Q_0,Q_A,\Delta> where

  • The event set Z=X \cup Y^\phi.
  • The state set Q=Q_A \cup Q_N where  Q_N=\{\bar{s} \not \in S \}.
  • The set of initial states  \,Q_0 = \{(s_0,0)\}.
  • The set of accepting states  Q_A = \mathcal{M}.Q.
  • The set of state trajectories  \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]}
\times Q is defined for two different cases:  q \in Q_N and  q \in Q_A . For an non-accepting state  q \in Q_N , there is no change together with any even segment \omega \in \Omega_{Z,[t_l,t_u]} so (q,\omega,q) \in \Delta.

For a total state  q=(s,t_e) \in Q_A at time  t \in \mathbb{T} and an event segment  \omega \in \Omega_{Z,[t_l,t_u]} as follows.

If unit event segment  \omega is the null event segment, i.e.  \omega=\epsilon_{[t, t+dt]}

\, (q, \omega, (s, t_e+dt)) \in \Delta.\,

If unit event segment  \omega is a timed event  \omega=(x, t) where the event is an input event  x \in X,

 
(q, \omega, (\delta_{ext}(q,x), 0)) \in \Delta.

If unit event segment  \omega is a timed event  \omega=(y, t) where the event is an output event or the unobservable event  y \in Y^\phi,

 
\begin{cases}
(q, \omega,(\delta_{int}(s), 0)) \in \Delta& \textrm{if } ~ t_e = ta(s), y = \lambda(s)\\
(q, \omega, \bar{s})                      & \textrm{otherwise}.
\end{cases}

Computer algorithms to simulate this view of behavior are available at Simulation Algorithms for Atomic DEVS.

View 2: total states = states * lifespans * elapsed times[edit]

Suppose that a DEVS model, \mathcal{M}=<X,Y,S,s_0,ta,\delta_{ext},\delta_{int},\lambda> has

  1. the total state set Q=\{(s,t_s, t_e)| s \in S, t_s\in \mathbb{T}^\infty, t_e \in (\mathbb{T} \cap [0, t_s])\} where  t_s denotes lifespan of state  s ,  t_e denotes elapsed time since last t_s update, and  \mathbb{T}^\infty=[0,\infty) \cup \{ \infty \} denotes the set of non-negative real numbers plus infinity,
  2. the external state transition is  \delta_{ext}:Q \times X \rightarrow S \times \{0,1\} .

Then the DEVS Q=\mathcal{D} is a timed event system \mathcal{G}=<Z,Q,Q_0,Q_A,\Delta> where

  • The event set Z=X \cup Y^\phi.
  • The state set Q=Q_A \cup Q_N where  Q_N=\{ \bar{s} \not \in S \}.
  • The set of initial states \,Q_0 = \{(s_0,ta(s_0),0)\}.
  • The set of acceptance states  Q_A = \mathcal{M}.Q.
  • The set of state trajectories  \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]}
\times Q is depending on two cases: q \in Q_N and q \in Q_A . For a non-accepting state  q \in Q_N , there is no changes together with any segment \omega \in \Omega_{Z,[t_l,t_u]} so (q,\omega,q) \in \Delta.

For a total state  q=(s,t_s, t_e) \in Q_A at time  t \in \mathbb{T} and an event segment  \omega \in \Omega_{Z,[t_l,t_u]} as follows.

If unit event segment  \omega is the null event segment, i.e.  \omega=\epsilon_{[t, t+dt]}

  (q, \omega, (s, t_s, t_e+dt)) \in \Delta.

If unit event segment  \omega is a timed event  \omega=(x, t) where the event is an input event  x \in X,

  
\begin{cases}
(q, \omega, (s', ta(s'), 0))\in \Delta& \textrm{if  } ~\delta_{ext}(s,t_s,t_e,x)=(s',1),\\
(q, \omega, (s', t_s, t_e))\in \Delta& \textrm{otherwise, i.e. }  ~\delta_{ext}(s,t_s,t_e,x)=(s',0). 
\end{cases}

If unit event segment  \omega is a timed event  \omega=(y, t) where the event is an output event or the unobservable event  y \in Y^\phi,

  
\begin{cases}
(q, \omega, (s', ta(s'),0)) \in \Delta& \textrm{if } ~t_e = t_s, y = \lambda(s), \delta_{int}(s)=s',\\
(q, \omega, \bar{s} )\in \Delta& \textrm{otherwise}.
\end{cases}

Computer algorithms to simulate this view of behavior are available at Simulation Algorithms for Atomic DEVS.

Comparison of View1 and View2[edit]

Features of View1[edit]

View1 has been introduced by Zeigler [Zeigler84] in which given a total state  q=(s,t_e) \in Q and

\, ta(s)=\sigma

where  \sigma is the remaining time [Zeigler84] [ZPK00]. In other words, the set of partial states is indeed S=\{(d,\sigma)| d \in S', \sigma \in \mathbb{T}^\infty \} where  S' is a state set.

When a DEVS model receives an input event  x \in X, View1 resets the elapsed time  t_e by zero, if the DEVS model needs to ignore  x in terms of the lifespan control, modellers have to update the remaining time

\, \sigma = \sigma - t_e

in the external state transition function  \delta_{ext} that is the responsibility of the modellers.

Since the number of possible values of  \sigma is the same as the number of possible input events coming to the DEVS model, that is unlimited. As a result, the number of states  s=(d, \sigma) \in S is also unlimited that is the reason why View2 has been proposed.

If we don't care the finite-vertex reachability graph of a DEVS model, View1 has an advantage of simplicity for treating the elapsed time  t_e=0 every time any input event arrives into the DEVS model. But disadvantage might be modelers of DEVS should know how to manage \sigma as above, which is not explicitly explained in \delta_{ext} itself but in \Delta.

Features of View2[edit]

View2 has been introduced by Hwang and Zeigler[HZ06][HZ07] in which given a total state  q=(s, t_s, t_e) \in Q , the remaining time,  \sigma is computed as

\, \sigma = t_s - t_e.

When a DEVS model receives an input event  x \in X, View2 resets the elapsed time  t_e by zero only if  \delta_{ext}(q,x)=(s',1). If the DEVS model needs to ignore  x in terms of the lifespan control, modellers can use  \delta_{ext}(q,x)=(s',0) .

Unlike View1, since the remaining time  \sigma is not component of  S in nature, if the number of states, i.e.  |S| is finite, we can draw a finite-vertex (as well as edge) state-transition diagram [HZ06][HZ07]. As a result, we can abstract behavior of such a DEVS-class network, for example SP-DEVS and FD-DEVS, as a finite-vertex graph, called reachability graph [HZ06][HZ07].

See also[edit]

References[edit]