An Eclipse-based Graphical Modeling Tool for Discrete Event Simulation
Chapter One
Objective of the study
The objective of this work is to present the DEVS Driven Modeling Language (DDML), a graphical notation for modeling dynamic systems based on DEVS and an Eclipse-based graphical modeling tool based on DDML. The model, when defined in DDML using this tool would be amenable to formal analysis and automated code synthesis.
Chapter Two
Discrete Event System Specification (DEVS)
DEVS [1] is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems. DEVS defines system behavior as well as system structure. System behavior in DEVS formalism is described using system input and output events as well as states.
According to the DEVS theory, the system of interest is seen as a source of behavioral data for study within a given experimental frame (EF). The EF is a restricted set of elements observed in the system and the conditions under which they are observed. These data are used to create an abstract representation of such a system (a model). Using a set of instructions, rules or mathematical equations, the model tries to replicate the behavior of the system of interest under experimental conditions.
A model represents a simplified version of reality and its structure. A model is built in consideration of the conditions of experimentation of the system of interest, including the work conditions of the real system and its application domain. The model is subsequently used to build a simulator (a device capable of executing the model’s instructions) generating the model’s behavior.
DEVS was created for modeling and simulation of discrete event dynamic systems (DEDS); thus it defined a way to specify systems whose states change either upon the reception of an input event or due to the expiration of a time delay. In order to attack the complexity of the system under study, the model is organized hierarchically (i.e. it is organized in such a way that every element is higher than its precedent), and the higher level components of the system are decomposed into simpler elements. The second tool used to attack complexity is information hiding, through the provision of a modular interface for each of the models.
Although many different simulation formalisms have been advanced over the years, the DEVS formalism has emerged as the preferred formalism due to the fact that other formalisms have been proven to have an equivalent DEVS representation. DEVS support full range of dynamic system representation. In particular, a Differential Equation System Specification (DESS) can have an approximate Discrete Time System Specification (DTSS) by selection of a sufficiently small constant time interval (discretization). A DTSS model, in turn has an equivalent DEVS representation. Also, quantization of events in a DESS system can result in an approximate DEVS model. As such DEVS approach can be used to model discrete systems, continuous systems (approximate), and hybrid systems.
The DEVS Formalism
A real system modeled by DEVS can be described as a composition of atomic and coupled components. An atomic model is specified as:
M = <X, Y, S, δint, δext, λ, ta>
Where
X = {(p, v)│p IPorts, v Xp} is the set of input events, where IPorts represents the set of input ports and Xp represents the set of values for the input ports;
Y = {(p, v) │p OPorts, v Yp} is the set of output events, where OPorts represents the set of output ports and Yp represents the set of values for the output ports;
S is the set of sequential states;
δext: Q × X → S is the external state transition function,
With Q = {(s, e)/s S, e [0, ta(s)]} and e is the elapsed time since the last state transition;
δint: S → S is the internal state transition function;
λ: S → Y is the output function; and
ta: S → R0+ U ∞ is the time advance function.
At any given moment, a DEVS model is in a state s ∈ S. In the absence of external events, it remains in that state for a lifetime defined by ta(s). When ta(s) expires, the model outputs the value λ(s) through a port y ∈ Y, and it then changes to a new state given by δint(s). A transition that occurs due to the consumption of time indicated by ta(s) is called an internal transition. On the other hand, an external transition occurs due to the reception of an external event. In this case, the external transition function determines the new state, given by δext (s, e, x), where s is the current state, e is the time elapsed since the last transition, and x ∈ X is the external event that has been received.
The time advance function can take any real value between 0 and ∞. A state for which ta(s) = 0 is called a transient or intermediate state (which will trigger an instantaneous internal transition). In contrast, if ta(s) = ∞, then s is said to be a passive or infinite state, in which the system will remain perpetually unless an external event is received (can be used as a termination condition).
A DEVS coupled model is composed of several atomic or coupled sub-models. It is formally defined by
CM = <X, Y, D, {Md│d D}, EIC, EOC, IC, select>
Where
X and Y are defined as previously;
D is the set of the component names and for each d D; Md is a DEVS (i.e., atomic or coupled) model;
EIC is the set of external input couplings (i.e., how the inputs of the coupled model are linked to the inputs of its sub-components)
EOC is the set of external output couplings (i.e., how the outputs of the coupled model are linked to the outputs of its sub-components
IC is the set of internal couplings (i.e., how the outputs of any the sub-components are linked to the inputs of other sub-components), and
Select: 2D → D is the tiebreaker function
Coupled models group several DEVS into a composite model that can be regarded, due to the closure under coupling property, as a new DEVS model. This closure property guarantees that the coupling of several class instances results in a model of the same class, allowing hierarchical construction.
Because multiple subcomponents can be scheduled for an internal transition at the same time, ambiguity could arise because it is not clear which transition this second component should execute first. There are two alternatives for this:
To execute the external transition first and then the internal transition, with e =
ta(s);
To execute the internal transition first, followed by the external transition, with e = 0.
The select function provides a simple way to solve this ambiguity. The function defines an ordering over all the components of the coupled model so that only the first model to execute in the case of simultaneous internal events can be chosen.
Parallel DEVS
In the previous section, we saw that whenever two models are scheduled for state transitions at the same time, a DEVS coupled model will pick the one specified by the select function to execute first. This tie-breaking strategy is rigid. The select function introduces serialization in the execution of components when many interconnected atomic models are imminent (which could be considered as parallel in a multiprocessor environment).
Parallel DEVS (or PDEVS) is a variant to DEVS that provides a more flexible way of dealing with these ambiguities. Atomic models provide an additional confluent function to specify collision behavior for events that might be scheduled simultaneously and a mechanism for receiving multiple external events at the same time and processing them together. An atomic PDEVS model is defined as
M = <X, Y, S, δint, δext, δcon, λ, ta>
Where
X, Y and S are defined as previously;
δext:Q x Xb→ S is the external transition function; δint: S → S is the internal state transition function; δcon:S x Xb→ S is the confluent transition function; λ: S → Yb is the output function; and
ta: S → R0+ U ∞ is the time advance function.
PDEVS models use bags (multisets) of events for receiving inputs and collecting outputs (Xb and Yb) instead of a single event. This allows multiple events to be processed simultaneously. Because external input events received by the component are added to the bag, external transition functions can combine the functionality of a number of external transitions into a single one, and simultaneous events (like the departure of a vehicle and a collision in the intersection) can be treated simultaneously. Also, PDEVS allows a better way to deal with collisions: the model specification includes a confluent transition function (δcon). When a collision between the internal and external functions occurs, the confluent function determines the new state of the model.
The semantics of PDEVS for internal/external transition functions is similar to DEVS. If one or more external events Xb = {x1
… xn/xi X} occur before ta(s) expires (i.e., while the system
is in total state (s, e) with e < ta(s)), the new state will be given by the model’s external transition function, δext(s, e, Xb). If the external events Xb are received when e = ta(s), the new state of the model will be given by the confluent function (δcon). If multiple components in a coupled model are imminent, all their outputs are first collected and mapped to their influences in parallel. Then the corresponding transition function is executed for every model.
In PDEVS, coupled models are defined as in DEVS, without the need for a select function. Formally, a coupled model is defined as
CM = <X, Y, D, {Md│d D}, EIC, EOC, IC>
Where definitions for the set of input and output events (X and Y), components (D and Md), and couplings (EIC, EOC, and IC) follow the specifications of DEVS coupled models presented earlier in this chapter.
Chapter Three
DEVS Driven Modelling Language (DDML)
As we have seen in chapter 2, DEVS formalism is very generic and several DEVS tools and techniques adopt this mathematical style making it DEVS inaccessible to a very wide community. DDML makes DEVS accessible to wide community of users and modelers by providing a means for defining DEVS-based models graphically. It uses a set of graphical notations to specify, visualize, analyse, verify, and document the characteristics and behaviour of some real or imagined system under development.
DDML uses processes to define the functional aspects of a system and this is described graphically using flowcharts with input and output ports. Dynamic aspects of a system are captured by using notations similar to state/activity diagrams. The static aspects are described using abstract structure graphs. The static aspects are automatically derived from the functional and dynamic aspects thereby clearing all ambiguities that might result if a modeller uses different diagrams to represent different views.Since DDML is visual, it is easier to discuss, understand, modify, and diagnose problems. Graph algorithms can be applied to a DDML model to evaluate the model and resolve problems.
DDML Processes
A simulation model is analogous to a business process that interacts with its environment through input and output ports. It receives messages via its input ports and sends out messages via its output ports. In DDML, the processes are instance of classes and the ports have to be defined by the domain or a set of allowable signals.
A process which cannot be decomposed is said to be atomic. Processes that have sub-processes are coupled. Processes communicate with each other via couplings (constraints are usually attached to these couplings to provide more prescriptions about data that are transferred). These process couplings can either couple two input ports (from a process and a sub-process), two output ports (from a sub-process and a process), or an input port and an output port (from two distinct processes). These couplings are termed External Input Coupling (EIC), External Output Coupling (EOC), and Internal Coupling (IC) respectively.
Figure 1 shows a coupled process (m0) with three sub-processes (m1, m2, m3). Process m0 has input ports (A and B) and output ports (C and D). Each port has a port type which specifies the domain or set of allowed variables. The External Input Coupling (EIC) (represented by a line- dot-dotted style line) is any connection between the parent’s input port and a child’s’ input port. There are two EIC connections in the diagram above. They include {(A—E) and (B—I)}. The External Output Coupling (EOC) (represented by a dashed style line) is any connection between the parent’s output port and a child’s output port). There are two EOC connections in the diagram above. They include: {(H—C) and (J—D)}. Internal Coupling (IC) (represented by a solid line) is any connection between two processes. There only one IC connections in the diagram. It is
{(F—G)}.
Processes usually occur concurrently, but in the case of a mutual exclusion, a flag is used to determine priorities. A paradox could occur when determining priorities. Figure 3 has a compartment for specifying the tie breakers (Select Flags). From the figure, if m1, m2, and m3 are concurrently activated, then m1 is selected to be processed. But if only m3 and m2 are activated, then m3 is selected. This kind of situation is known as Condorcet’s paradox (or voting paradox). Several flags can be added to indicate paradoxes. Flows are also asynchronous and instantaneous.
Chapter Four
Building Graphical Editors with Eclipse
In order to implement the graphical editor for DDML, several frameworks have been considered. Some of them include the basic Java graphic libraries: the Abstract Window Toolkit (AWT) and Swing. Others frameworks considered are the Eclipse graphic utilities: the Standard Widget Toolkit (SWT), JFace, Draw2D, and the Graphical Editing Framework (GEF). AWT, Swing, and SWT are based on Java and they provide general GUI controls useful for building form windows. Furthermore, SWT is a widget set and graphics library integrated with the native window system but with an OS-independent API. JFace is a platform-independent toolkit built on SWT. It provides convenience classes for many typical application features and simplifies a number of common UI tasks. It enhances and works with SWT without ever hiding it from the developer. Nevertheless, AWT, SWT, Swing, and JFace are not practical for manipulating figures and shapes, and they do not provide any special infrastructure for Eclipse-based editors.
Figures are the building blocks of Draw2D that builds on top of the SWT library. The Draw2D tool lets you render GUI components with whatever appearance and functionality you prefer. It provides this capability by creating a high-level drawing region that operates independently from the native platform. GEF allows generating a graphical editor based on an existing application model. Eclipse provides Eclipse Modelling Framework (EMF) for building application models and Graphical Modeling Framework (GMF) to glue EMF models with GEF. Due to these reasons, Eclipse’s GMF has been chosen because this library acts as a bridge between GEF and EMF; and it specifically tackles the creation of graphical Eclipse-based editors.
Chapter Five
Architecture of Eclipse-DDML Graphical Editor
Figure 13 shows the conceptual architecture of the Eclipse-based DDML Editor.
EMF was used to define the model, as it provides several utilities for specifying entities. The model was specified in an Ecore graphical editor which was translated into an Ecore model (XMI format). EMF uses this model to generate Java classes and interfaces. The generated classes implement the observable design pattern, providing methods that notify whenever one of their properties has changed. Custom code and methods to provide extra behaviour and functionality was added to the generated classes. EMF recognises special code comments in the added or customized methods not to overwrite them when the model is regenerated. EMF also provides persistence and validation services for the generated models. Figure 14 below shows the Ecore Graphical Definition for DDML
The DDML Graphical editor is eclipse based and it is as easy to use as eclipse. In this chapter, we present the DDML Coupled Model Editor and the DDML Atomic Model Editor.
The DDML Coupled Model Editor
Figure 45 below shows a screen shot of the coupled model editor. The editor has a menu bar, a tool bar, project explorer, Outline view, Properties View, Palette, and the Model Editor Workspace. In the following sections, we will take a look at each of these sections.
Chapter Seven
Conclusion
We presented DDML as a graphical notation for defining DEVS models. We showed how DDML maps to the formal DEVS specification and how it captures the dynamic, static and functional aspects of a system. We also presented a graphical editing tool with rich editors for defining DEVS coupled models and atomic models. Our tool, with drag and drop features can enable modelers to easily define, edit, share, and store models in a persistent form. DDML is a natural and intuitive approach to modeling. Its notation can easily be understood by both domain experts and modelers. Using a graphical editing tool further increases the simplicity.
DDML is a contribution towards making DEVS available to a wider community. It borrows concepts and ideas from very strong graphical formalisms (like UML and BPMN). Our tool is built as an eclipse plugin, hence it can integrate and be integrated into other utilities using Eclipse platform. This also means that it is extensible, easy to manage, and update.
Future work includes the following:
DDML should be integrated with some methods for formal analysis
Our editor should be extended to include ability to automatically generate simulation code for DEVS libraries like SimStudio, DEVSJAVA, and DEVS-C++.
Our tool should evolve into an integrated development environment for all simulation tasks (modeling, simulation, analysis of results, verification, and validation of simulation models, and visualization of simulation results.
References
- Zeigler,B.; Praehofer, H; Kim, 2000. ―Theory of Modeling and Simulation‖. 2nd Edition, Academic Press.
- Adegoke 2010. ―Efficient Object Oriented Implementations for the DEVS Formalism‖. M.Sc. Thesis, Computer Science Stream, African University of Science and Technology, Abuja, Nigeria.
- Christen, , A. Dobniewski, and G. Wainer. 2004. ―Modeling state-based DEVS models CD++‖. Proceedings of MGA, Advanced Simulation Technologies Conference 2004, Arlington, VA, USA.
- Kidisyuk,, and G. Wainer. 2007. ―CD++Modeler: A graphical viewer for DEVS models‖. Technical report SCE-017, Ottawa, ON, Canada.
- Matias, B.; Wainer; R. Castro; 2010. ―Advanced IDE for Modeling and Simulation of Discrete Event Systems‖. Proceedings of 2010 Symposium on Theory of Modeling and Simulation, DEVS’10. Orlando, FL. 2010.
- Nutaro, J. ADEVS. URL: http://www.ornl.gov/~1qn/adevs/index.html.Accessed: November 1,
- Kim, H., Y. R. Seong, T. G. Kim, and K. H. Park. 1996. ―Distributed simulation of hierarchical DEVS models: Hierarchical scheduling locally and time warp globally‖. Transactions of the SCS 13 (3): 135–154.
