DEVS

Description

DEVS is a recognised formalism for specifying complex discrete or continuous systems. This formalism is represented by a network of atomic and coupled models, interacting and competing over time.

Atomic model

DEVS defines an atomic model as a set of input and output ports, states and state transition functions.

\[M = \left\langle X,Y, S, \delta_{\text{int}}, \delta_{\text{ext}}, \delta_{\text{con}},\lambda, \tau \right\rangle\]

Where:

  • \(X\) is the set of all input values
  • \(Y\) is the set of all output values
  • \(S\) is the set of all sequential states
  • \(\tau: S \to \mathbb{R}_0^+\) is the time advance function
  • \(Q = \{(s,e) | s \in S, 0 \leq e \leq \tau(s)\}\), \(Q\) is the set of total states where: \(e\) is the time since the last transition
  • \(\delta_{\mathit{int}}: S \to S\) is the internal transition function
  • \(\delta_{\mathit{ext}}: Q \times X^b \to S\) is the external transition function \(X^b\) is the set of values in \(X\) built at \(t\)
  • \(\delta_{con}: S \times X^b \to S\) is the confluent function subject to \(\delta_{con}(s, \emptyset) = \delta_{\mathit{int}}(s)\)
  • \(\lambda: S \to Y\) is the output function

If no external event occurs, the system will stay in state \(s\) for \(\tau(s)\) time. When \(e = \tau(s)\), the system changes to the state \(\delta_{\mathit{int}}\). If an external event, of value \(x\), occurs when the system is in the state \((s,e)\), the system changes its state by calling \(\delta_{\mathit{ext}}(s,e,x)\). If it occurs when \(e = \tau(s)\), the system changes its state by calling \(\delta_{\mathit{con}}(s,x)\). The default confluent function \(\delta_{\mathit{con}}\) definition is \(\delta_{\mathit{con}}(s,x) = \delta_{\mathit{ext}}(\delta_{\mathit{int}}(s), 0, x)\)

The modeller can prefer the opposite order \(\delta_{\mathit{con}}(s,x) = \delta_{\mathit{int}}(\delta_{\mathit{ext}}(s, \tau(s), x))\). Indeed, the modeller can define its own function.

Coupled model

All atomic models can be coupled with one or more other atomic models to form a coupled model. This operation can be repeated to form a hierarchy of coupled models. All of the atomic models, coupled models and their connections form the structure of the model. A coupled model is recursively defined by:

\[N = \langle X, Y, D, \{M_d\}, EIC, EOC, IC \rangle\]

Where \(X\) and \(Y\) are the input and output ports, \(D\) the set of atomic or coupled sub-models. Thus, \(\forall d \in D\), \(M_d\) is an atomic or coupled DEVS model. Variables \(\mathit{EIC}\), \(\mathit{EOC}\) and \(\mathit{IC}\) define the coupling structure of the coupled model while:

  • \(\mathit{EIC}\) is the set of external input couplings; they connect the inputs of the coupled model with the internal components.
  • \(\mathit{EOC}\) is the set of external output couplings; they connect the outputs of the internal components with the outputs of the coupled model.
  • \(\mathit{IC}\) defines the internal couplings. They connect the internal component outputs with the internal component inputs.

The DEVS formalism is very general and the development of operational models is far from simple. Indeed, it is necessary, first of all, to undertake discrete event modelling as numerous models are based on (continuous time) differential equations or (discrete time) recurrent equations and their reformulation into DEVS discrete event models is not trivial. Secondly, DEVS formalism leaves complete freedom in expressing states, transition functions, values transported by the events, and simply offers structuring for the model and minimalist algorithmics. This simplicity makes it possible to define a solid and simple basis for coupling the models. It is therefore necessary, in practice, to have a computer technology infrastructure available to help the modeller. The VLE software is a modular and extendable solution for producing multi-formalism models by coupling.

Multi-modelling in VLE relies on one of the essential properties of DEVS: encapsulation. Indeed, B.P. Zeigler showed that formalisms arising from dynamic systems wherein time is discrete, event-driven or continuous, can be represented or generalised in DEVS. Thus, rather than develop simulators specific to DTSS type discrete time models, continuous time models like DESS, or hybrid like DEV&DESS, encapsulation proposes to model these formalisms directly as a DEVS model.

Graphical representation

An atomic model is a frame with left and right arrows that define input and output ports.

Frame with left and right arrow that define input and output ports

A coupled is a frame with internal subframes and coupling links. Left and right arrows that define input and output ports of the coupled model. Subframes can be atomic or coupled models.

Frame with subframes, with left and right arrow that define input and output ports. Subframes can be atomic or coupled models.

Behaviour as automata

The behaviour of the simulator for atomic models is quite simple. DEVS is an event driven simulator. The functions of the atomic models are called by the simulator. These functions are callbacks in computer programming. In the following description: \(\rightarrow\) means the simulator takes over the control of the simulation. \(\{\) and \(\}\) means that underlying functions are called one after another.

  • If no event arrives on input port, the sequence of callback is:

\[... \rightarrow \{\lambda, \delta_{\text{int}}, \tau\} \rightarrow \{\lambda, \delta_{\text{int}}, \tau\} \rightarrow ...\]

  • If an event arrives on an input port and before the end of the internal events the sequence of callback is:

\[... \rightarrow \{\lambda, \delta_{\text{int}}, \tau \} \rightarrow \{ \delta_{\text{ext}}, \tau \} \rightarrow \{\lambda, \delta_{\text{int}}, \tau \} \rightarrow ...\]

  • Finally, if an event arrives on an input port and the end of the internal events, the sequence of callback is:

\[... \rightarrow \{\lambda, \delta_{\text{int}}, \tau \} \rightarrow \{ \lambda, \delta_{\text{con}}, \tau \} \rightarrow \{\lambda, \delta_{\text{int}}, \tau \} \rightarrow ...\]

DEVS and VLE

VLE us a C++ implementation of the DEVS simulators. A model is a C++ class. To develop a model, you must inherit this class and use its API. For example, the type vle::devs::Time is a C++ double.

class MyModel : public vle::devs::Dynamics
{
public:
MyModel(const DynamicsInit& init, const vle::devs::InitEventList&  events)
    : vle::devs::Dynamics(init, events)
{}

~MyModel() override = default;

// Process the initialization of the model by
// initializing the initial state and return
// the duration (or timeAdvance) of the initial
// state.
vle::devs::Time
init(vle::devs::Time time) override
{}

// Process the output function: compute the output function.
void
output(vle::devs::Time time,
       vle::devs::ExternalEventList& output) const override
{}

// Process the time advance function: compute the duration
// of the current state.
vle::devs::Time
timeAdvance() const override
{}

// Process an internal transition: compute the new
// state of the model with the internal transition function.
void
internalTransition(vle::devs::Time time) override
{}

// Process an external transition: compute the new state
// of the model when an external event occurs.
void
externalTransition(const vle::devs::ExternalEventList& events,
                   vle::devs::Time time) override
{}

// Process the confluent transition, by default,
// confluentTransitions call internalTransition and
// externalTransition but this function can be overridden
// to develop its own dynamics.
virtual void
confluentTransitions(vle::devs::Time time,
                     const vle::devs::ExternalEventList& events) override
{}

// Process an observation event: compute the current state
// of the model at a specified time and for a specified port
std::unique_ptr<vle::value::Value>
observation(const vle::devs::ObservationEvent& event) const override
{}

// When the simulation of the atomic model is finished,
// the finish method is invoked
void finish() override
{}

}; // End of class definition

// Finally, this macro enables the link between VLE, the shared library
// produced by C++ compiler and your model.
DECLARE_DYNAMICS(MyModel);