The DEVS formalism was among the first discrete systems theories with a mathematical background: while before the advent of the computer, continuous systems were mostly described by differential equations, with the growing computational power of computers discrete-event simulations were made possible but usually lacked a profound mathematical theory. Only roughly since the early seventies, it was recognized that deeper, i.e. mathematical, understanding of complex systems can help their efficient simulation, and research in this area began to be carried out. The DEVS formalism was one of the resulting mathematically well-founded methodologies in the area of discrete-event systems simulation.
During the past years, several implementations of the theoretical concept defined by the DEVS formalism have emerged (see the introductory part of [Kofman03] for examples), among which also PowerDEVS [Kofman03].
The next two sections will discuss the theory of the DEVS formalism as it has been defined by Zeigler. The first section covers the topic of atomic models which actually reveals the fundamental principles of the formalism. The second section discusses an "extension" of these ideas, namely a) the possibility of linking models to each others such that they form a coupled (multi-component) system and b) the hierarchic use of a coupled model as a component of another coupled model.
Atomic Models
A DEVS model has the following structure (see also [Cellier05], Chapter 11):
- X represents all possible inputs, Y represents the outputs and S is the set of states.
- The variable e (used within the dext function) indicates the amount of time the system has already been in the current state.
-
dext(s,e,x) is the external transition which is executed after having received an external event.
As an example, assume the system adopted state 6 at time t=7.5 and it receives an external event with the value 3.33 at time t=9. Then, the new state is computed by snew=dext(6,1.5,3.33). -
dint(s) is the internal transition which is executed as soon as the system has elapsed the time indicated by the time-advance function.
Example: If the system is in state 3 at a given time instant, the new state is computed by snew=dint(3). -
ta(s) is the so called time-advance function which indicates how much time is left until the system undergoes the next internal transition. Note that the ta function is always dependent on the current state.
If for example at time t=2 the system is in state 4, and the value of ta(s=4) is 3, the system will change its state autonomously at time t=5. If on the other hand, an event arrives in the meantime (let us say at time t=4.5) which puts the system into state 9, the new time when the system will change by itself is computed by tnew=4.5+ta(s=9).
Note that the time-advance function manipulates the simulation time of a model "by hand". There is no global clock anymore that gives equidistant ticks. When the system's time-advance function adopts a certain value, let us say three, it means that the system will be idle for the next three units of time (provided the absence of external inputs), so it does not make any sense to simulate this period of inactivity, and the system clock is allowed to directly jump three time units forward.
The time-advance function is often represented by the variable sigma which holds the value for the amount of time that the system still has to remain in the current state (in the absence of external events). If sigma is present, the time-advance function merely returns sigma. - The lambda-function is the output function. It is only active before internal transitions. Thus, external transitions do not produce any output.
The above figure illustrates the mechanism of a DEVS model: the system receives inputs (see the uppermost graph) at certain time instants, changes its states according to the internal and external transitions, and gives outputs (see the lowermost graph). The graph in the middle shows the state trajectory of the system. Apparently, the system starts in state s1 and changes to state s2 after the time advance ta(s1) has been elapsed. Right before executing the internal transition, it generates the output y1. When it receives the input x1, it again changes its state, this time though undergoing the external transition. Note that no output is produced. When the time advance of state s3 has been elapsed, it produces an output (y2), executes the internal transition again and thereby changes to state s4.
Coupled Models
DEVS models can describe arbitrarily complex systems. The only drawback is that the more complex the system is, the more difficult it is to set up the correct functions (dint, dext, time-advance and lambda-function) that describe the system. Fortunately, most complex systems can be broken down into simpler submodels that are easier to handle. It is therefore convenient not to have just one model that tries to simulate the whole system, but an interconnection of a number of smaller models that, together, represent the system. Even though this approach seems to be very intuitive, it is only possible because DEVS models are closed under coupling [Cellier05], which means that a coupled model can can be described by the same functions as an atomic model (internal, external, time-advance and lambda function). Due to this fact, coupled models can be seen as atomic models, too, which allows for hierarchical modelling.
The following figure illustrates these ideas: the model N consists of two coupled atomic models Ma and Mb. N can be seen as an atomic model itself and it is therefore possible to connect it to further models (coupled or atomic ones).
In such a network where submodels interact with each other through ports, so that output events of one submodel are transformed automatically into input events for other submodels, events do not only carry the output value but also a number indicating the port where the event is appearing. Hence, inputs and outputs take the following form:
Besides "normal" connections between submodels (Ma and Mb in our case), there are also connections that lead to or come in from the outside: as already mentioned, model N can be seen as an atomic model with two input and two output ports. Events coming in through port number 0 are immediately forwarded to submodel Ma, those from port number 1 to Mb. This kind of connection is called external input connection. Analogous, the connections leading from the output ports of the submodels to the output ports of the surrounding model N are called external output connections.
The behaviour of model N is determined by the behaviour of its submodels Ma and Mb. The actual task of N is to wrap Ma and Mb in order to make them look like as if they were one single model. The dynamics of N (or any multi-component/coupled model) can be defined by the following loop [Kofman03]:
-
Evaluate the atomic model that is the next one to execute an internal transition. Let this model be called d* and let tn be the time when the transition has to take place.
In case there are more than one candidates ready to execute their internal transitions, choose the one that is designed by the so called tie-breaking function (the tie-breaking function imposes an ordering onto the components of the model, such that in case of two components ready to execute their internal transition, the simulation knows which one to process first). - Advance the simulation time (of the coupled model) to t=tn and let d* execute the internal transition. Note that tn=tcur+ta(scur).
-
Forward the output event produced by d* to all atomic models that are connected to d* and let them execute their external transitions.
Go to step 1.