ID 8688
Deatcu, Christina: Development of an Object-Orientated DEVS-Simulator with MATLAB®
Hamburg: Diplomica GmbH, 2005
Zugl.: Hochschule Wismar, Diplomarbeit, 2003
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2005
Printed in Germany
Project Task
Project Task
Subject: Development of an Object-Orientated DEVS-Simulator with MATLAB
®
Starting with the DEVS theory by Zeigler and an existing MATLAB
®
-based
DEVS-simulator, a new DEVS-simulator is to be designed and implemented, which
especially eases the interfaces for modeling and simulation.
Special impact is put on:
·
Gaining acquaintance of the DEVS theory and the abstract simulator algorithms
based on it,
·
Familiarization with the object orientated features of MATLAB
®
and programming
of GUI's using MATLAB
®
,
·
Analysis of the existing simulation runtime system MatlabDEVS,
·
Development of a proposal for a better structure for a MATLAB
®
-based DEVS
runtime system,
·
Implementation of an improved runtime system (MatlabDEVS2),
·
Verification of the implementation using a selected example.
First Supervisor:
Prof. Dr.-Ing. Sven Pawletta, Hochschule Wismar
Second Supervisor:
Prof. Dr.-Ing. Ernst Jonas, Hochschule Wismar
I
Abstract
Abstract
To solve problems of real world systems using scientific methods, the model-based
approach is an effective and widely used method. To help rebuilding a system
properly, there exist formalistic descriptions of systems` behavior.
One of several system specification formalisms, the DEVS formalism and associated
abstract simulator algorithms provide the bases of this work.
The DEVS formalism offers ways to describe systems which change their state
driven by events at discrete times.
Several implementations for computer aided simulation based on the DEVS
formalism and associated abstract simulator concepts using object-orientated
programming languages exist. One of those implementations, the MatlabDEVS
simulation runtime system was modified and improved during this project and
MatlabDEVS2, a modified version was developed.
To make improvement possible, a proper understanding of the fundamental theories
is indispensable. Hence, they are exhibited as a part of this work.
Because the modeler should be supported by the computer application while passing
the process of modeling and simulation, the user interfaces are crucial for the quality
of the system. The existing MatlabDEVS system did not offer any support for
modeling and simulation, as well as it was not well documented.
Object orientated programming within the MATLAB
®
programming environment
results in a complicated file structure representing the classes. This fact cannot be
influenced. Hence, a GUI for modeling and simulation which creates the source code
files for the classes was implemented.
II
Contents
Contents
1
Introduction ... 1
2
Modeling and Simulation ... 3
2.1
The General Scientific Problem Solving Process... 3
2.2
Simulation ... 4
3
System Specification Formalism ... 7
3.1
The Systems Approach to Modeling and Simulation... 7
3.2
Levels of System Description by Zeigler ... 9
3.3
Atomic Model and Coupled Model ... 11
3.4
DEVS Formalism ... 12
3.4.1
Specification Semantics for an Atomic DEVS Model ... 13
3.4.2
Specification Semantics for a Coupled DEVS Model... 14
3.5
Abstract Simulators for DEVS Models ... 15
3.5.1
The DEVS simulator ... 17
3.5.2
The DEVS coordinator... 18
4
MatlabDEVS MATLAB
®
Based Simulation Runtime System ... 21
4.1
MATLAB
®
's Features for Object-orientated Programming ... 21
4.2
Class Hierarchy of MatlabDEVS ... 24
4.3
File Structure ... 26
4.4
The Simulation Engine... 28
4.5
User Interface for Modeling and Simulation ... 30
4.5.1
Development of Atomic Devs Models ... 32
4.5.2
Development of Coupled Devs Models... 34
4.5.3
Simulation... 36
4.6
Evaluation of the System ... 38
5
MatlabDEVS2 ... 42
5.1
System Requirements... 44
5.2
Installation... 45
5.3
Directory Structure... 46
5.4
DEVSModeler ... 48
5.4.1
Development of Atomic DEVS Models ... 50
5.4.2
Development of Coupled DEVS Models ... 53
III
Contents
5.5
DEVSSimulator... 56
6
Bank Simulation Example... 60
6.1
System Decomposition ... 61
6.2
Model Building ... 63
6.3
Execution of the Example ... 65
7
Conclusions and Open Problems ... 66
A References... 69
B Figure Index... 70
C Appendix... 71
D Abbreviations ... 96
IV
Introduction
1 Introduction
The DEVS (Discrete Event Systems Specification) formalism introduced and
developed by Zeigler is a formalistic way of describing systems which are subjects to
event-driven changes of system states. An example for such a system could be any
kind of sales office where something happens, if a customer arrives at the shop. The
system then changes state, which means that the salesman is busy, or if he was
already, the waiting queue grows. After a given time the customer is served and the
system changes state again. Characteristically, the time base for such a system is
continuous, this means a customer could arrive at any time not just at discrete times.
The DEVS formalism and associated simulator concepts have been implemented for
simulation means in different ways using several object-orientated programming
languages. To gain acquaintance of this field, first the general rules for modeling and
simulation have to be exposed. Then an overview over system specification
formalism is given and the DEVS formalism needs to be explained detailed.
Because the DEVS formalism includes a modular hierarchical concept, it fits well with
the object-orientated programming paradigm and implementation with an object-
orientated programming language is obvious.
The analysis of the MatlabDEVS simulation runtime system, which acts as starting-
point, begins with the characterization of the object-orientated features of the
MATLAB
®
programming language. The object-orientated programming within the
MATLAB
®
environment differs quite a lot from object-orientated programming using
for example C++, Java or Object Pascal.
Then MatlabDEVS, a simulation runtime system developed by Prof. T. Pawletta in
1998 and advanced as a diploma at the Wismar University of Technology, Business
and Design and the Tomsk Polytechnic University by Issaev Artem in 2002, is
explained and tested. The MatlabDEVS system is realized with the MATLAB
®
programming language and uses class definitions for both, model building and
simulation.
MatlabDEVS implements the entire DEVS formalism well, but caused by MATLAB
®
's
way of defining classes, a complicated, hard to follow up file structure is needed to
1
Introduction
build models. This is the biggest disadvantage of MatlabDEVS:
The modeler has to keep track of many source code files and may easily loose
perspective.
Next step is to give prospects for further improvement of the system.
Especially the user interfaces for modeling and simulation are of interest, because
they are crucial for the quality of the system.
Those prospects did lead to the development of the MatlabDEVS2 system, which
includes some smaller changes in the simulation engine as well as a graphical user
interface (GUI) for modeling and simulation. The GUI is implemented taking benefit of
MATLAB
®
's facilities for creating graphical user interfaces.
Since it is impossible to avoid models` complicated file structure, the user interface
for modeling offers support to create and administer those files in a clearly arranged
way.
System requirements for, structure and facilities of MatlabDEVS2 are presented and
described. A user guide for MatlabDEVS2 can be found in appendix.
Last step in this project is the verification of the MatlabDEVS2 system using the Bank
Simulation example taken from the diploma of Issaev Artem [4]. This model
represents the flow of customers in a bank. It consists of a waiting queue, two
counters to serve the customers and the experimental frame which generates the
customers and computes statistics of system's behavior.
2
Modeling and Simulation
2 Modeling and Simulation
2.1 The General Scientific Problem Solving Process
To solve a problem in the real world often the model-based approach is used. This
means that a problem which needs to be eliminated is first solved using a model.
After a solution is found for the model, it is interpreted for the real world problem.
Now it is possible to eliminate the real problem by implementing the solution.
real
system
model
implementation
model
building
problem solving
interpretation
solution
in model
world
solution
in real
world
Figure 2.1-1 General problem solving process [1]
Model application methods are mainly classified into two categories:
·
analytical methods
·
simulation.
The applicability of analytical methods is restricted, because many real world
problems are very large and complex. Hence, simulation in many cases offers the
better opportunity.
3
Modeling and Simulation
2.2 Simulation
Simulation is defined in the following way:
Simulation is the reproduction of the dynamical behavior of a real system using a
(real) model to arrive at conclusions which are applicable to the real world[1].
Hence, the quality of simulation, especially the quality of the model is crucial for the
applicability of solutions.
Simulation models can be categorized into[1]:
·
physical simulation models,
·
graphical simulation models,
·
computer simulation models.
In this context just the computer simulation models are of interest. Four levels in
which computer simulation models can be employed are defined by Zeigler:
·
explanatory,
·
forecast,
·
improvement,
·
design.
In the first level, simulation is used to get more insight into the operation of the real
system. In the forecast level, a simulation model of an existing system is used to get
information as to how it will behave in the future[1].
In the third level , we use a model of an existing real system to analyze its operation
and then to study different alternatives to improve its operation. Studying alternatives
is done in the model world and only the best realizable alternative is implemented. In
the design level, no real system exists and the models serve as design blueprints
which are tested by simulation[1].
4
Modeling and Simulation
Irrespective of what the simulation results are to be used for, computer simulation
models can also be classified by internal classification criteria.
Ören uses following criteria[1]:
·
the time set of the model,
·
trajectory or descriptive variables,
·
existence and range of variables,
·
functional relations of variables,
·
spatial distribution,
·
organization of component models, and
·
goals to be pursued.
Since dynamical behavior of simulation models is of central interest, we state that
from these criteria the first two are the most important, namely how is time modeled
and how do the changes in the descriptive variables occur. Figure 2.2-1 shows a
taxonomy according to these two criteria[1].
computer simulation model
time
change
continuous-time discrete-time
continuous-change
discrete-change
differential
difference
discrete finite
state
equations
equations
event
models machines
Figure 2.2-1 Simulation model taxonomy [1
Zeigler depicts three main elements involved in computer simulation:
·
the real system,
·
the model,
·
the computer.
5
Modeling and Simulation
The real system is regarded to be nothing more than a source of data. The model is
a set of instructions capable of generating such data and the computer is a means of
carrying out these instructions to actually generate such data.
The relations between the three involved elements are represented in figure2.2-3.
A direct relation exists between the real system and the model and is summarized by
the term modeling. A direct relation between the model and the computer exists and
this relation can be denoted simulation [1].
modeling
validation
simulation
verification
computer
model
real
system
Figure 2.2-2 Digital computer simulation [1]
6
System Specification Formalism
3 System Specification Formalism
3.1 The Systems Approach to Modeling and Simulation
A generally agreed definition of what a system is does not exist [1]. Basically, we
distinguish two different interpretations which we adapt for our needs and summarize
by the following definitions:
·
A system (real system) is a combination of one or more structural related
elements whose states are influenced by states of itself or other elements and
which influence states of other elements [Bossel, Laux, Lerner] [1].
·
A system (dynamical system) is every formal construct which provides general
modeling concepts for various kinds of disciplines[Pichler, Zeigler, Wymore] [1].
According to the first definition, we use the term system mainly to denote the part of
the real world we are interested in as well as its representation, namely its model.
Central to our point of view is that the system consists of elements and that there is
some sort of interrelation between these elements.[1]
According to the second definition, we use the term system to denote every formal
construct which is to be used to model some part of the reality and has been
developed according to system theoretical principles, this means, which is
interdisciplinary in its nature. So a `system` in this sense is a system theoretical
means to model a `system` in the sense of the first definition. When meaning is not
obvious, we will distinguish these two interpretations by denoting the first real system
and the second dynamical system, as in simulation we exclusively deal with a system
showing some sort of dynamical behavior [1].
7
System Specification Formalism
Together with the definition of a system several related terms have to be introduced:
·
system boundary (encloses the part of reality which should be used for modeling
and excludes everything else),
·
system environment (everything not enclosed by the system boundary),
·
system input,
·
system output,
·
system behavior (how it reacts to inputs by outputs),
·
system state and system dynamic (describe the interior of a system),
·
state variables (represent the systems state),
·
state transition function (describes the dynamic of the system, depends on the
input and the state itself),
·
output function (matches current state and input to the output),
·
system elements (part of the system corresponding to parts of the real world),
·
system element state,
·
system structure (interdependencies of system elements contributing to the
systems dynamic),
·
system component (part of a system which is a system itself),
·
system coupling (interdependencies between the components),
·
coupled system (system consisting of coupled components).
8
System Specification Formalism
3.2 Levels of System Description by Zeigler
Zeigler defines a hierarchy of levels of system descriptions which exposes different
means to describe a system and stratifies them according to their level of
concreteness - from a very abstract level to a very concrete level. Each level
introduces more concreteness into the description of the internal structure of a
system [1].
Listed from the most abstract to the most concrete level of description:
Level 0:
Observation Frame O =<
,
,
>
·
just the system boundary is defined
·
input interface in form of a set of inputs
·
output interfaces in form of a set of inputs
·
time base
(real numbers continuous time base or integers
discrete time base)
Level 1:
Relation Observation IORO = <
,
,
,
, R>
·
defines the behavior of the system using a relation R of possible
input values at particular times and their possible output values
·
for a particular input there can be several outputs
Level 2:
Function Observation IOFO = <
,
,
,
, F>
·
equal to level 1, but R is partitioned into a set F of functions f
·
each function f defines a unique output response for a particular
input segment
Level 3:
Input / Output System ( or dynamical system) IOS = <
,
,
,
Q
,
,
,
>
·
set of states
Q
·
global state transition function
(realizes the dynamic of the system)
·
output function
(used to model how the current state manifests at
the output interface)
·
possibility to model the interior of the system
·
most important concept for simulation modeling
Level 4:
Structured Input /Output System SIOS = <
,
,
,
Q
,
,
,
>
A structured input / output system is an input / output system where the
set of inputs, outputs, and states are multi-variable sets, this means,
that it is possible to identify several input, output and state variables[1].
9
System Specification Formalism
Level 5:
Coupled System CS = <
,
,
, Components, Coupling>
In a coupled system the interior of the system is represented by
identifying several component systems and the couplings between
them. The coupling defines how the coupled system inputs and the
component system outputs are mapped into component system inputs
and coupled system outputs. The state of the coupled system is built up
by the states of all component systems. The system dynamic is built up
by the dynamic of the components and the coupling scheme. As a
coupled system also has an input / output interface and is a system
itself, it can appear as a component in a bigger coupled system [1].
10
System Specification Formalism
3.3 Atomic Model and Coupled Model
The most powerful way of constructing models is to build them up by coupling
together simpler component models using coupled system specification [Zeigler,
Bossel, Ören] [1].
A coupled system consist of components which can be coupled system themselves.
Hence, it is possible to construct hierarchical models. Zeigler defines a hierarchical
model in the following way [Zeigler] [1]:
·
an atomic model, this means, every model which is not a coupled model, is a
hierarchical model;
·
a coupled model whose components are hierarchical models is a hierarchical
model;
·
nothing else is a hierarchical model.
The static structure the structure representing the system without its dynamical
behavior of a hierarchical model can be represented by a finite tree the so called
composition tree [Zeigler] [1]. The root node is the "biggest model". The interior
nodes are coupled systems and their children represent their components. To make
sense, the leaves have to be atomic models. An input / output interface is associated
with every node . With the interior nodes we associate the definition of the couplings,
while with the leaves we associate the state descriptions [1].
11
System Specification Formalism
3.4 DEVS Formalism
When we derive constraints on the parts of a dynamical system description, we
derive different system formalism [1].
Only those parts which distinguish this particular system from others have to be
specified [Zeigler] [1].
Basic system formalisms are differential equation specified systems, discrete time
specified systems, or discrete event specified systems [1].
Characteristic for a discrete event specified system is the event-driven change of
system states and the continuous time base (figure 2.2-1).
As in this context only the discrete event specified systems have to explained more
detailed, the other formalisms will not be mentioned more concrete.
For the discrete event system specification (DEVS) formalism at the input / output
level (level 3) following constraints exist:
·
time base T:
continuous reals
·
basic sets
,
,
Q
: arbitrary
·
input segments:
discrete event segment
·
state trajectory:
piecewise constant
·
output trajectory:
discrete event segment
On the most concrete level, the coupled systems level (level 5) a DEVS could be
described like this:
·
time base T:
continuous reals
·
basic sets
,
:
arbitrary
·
input segments:
discrete event segments
·
components:
discrete event systems
·
couplings:
no direct feedbacks allowed
12
System Specification Formalism
3.4.1 Specification Semantics for an Atomic DEVS Model
An atomic discrete event systems (DEVS) is a structure[Zeigler]
(
)
ta
S
Y
X
DEVS
ext
,
,
,
,
,
,
int
=
where
is the set of external events
is the set of outputs
is the set of sequential states
is the external transition function
is the internal transition function
is the output function
is the time advance function
×
+
0
int
:
:
:
:
S
ta
Y
S
S
S
S
X
Q
S
Y
X
ext
and
( )
{
|
)
(
,
,
:
s
ta
e
S
s
e
s
Q
=
0
}
is the set of total states
Discrete event systems have a continuous time base but inputs and state transitions
at discrete time instances [1].
Beyond this formal description for an atomic DEVS model some more rules are
established. The internal transition function specifies to which next state the system
will transit after the time given by the time advance function has elapsed. The second
transition function, the external transition function, specifies how the system changes
state when an input is received. When an external event (or input) is received, the
external transition function has to place the system in a state thus scheduling it for a
next internal transition, this means it has an effect on the time advance function ta,
which controls the timing of the internal transitions.
The output function
generates an external output just before an internal transition
takes place.
13
System Specification Formalism
3.4.2 Specification Semantics for a Coupled DEVS Model
The second form of a model, the coupled model (or coupled DEVS), tells how to
couple several component models together to form a new model. This latter model
can be employed as a component in a larger coupled model, thus giving rise to the
construction of complex models in hierarchical fashion [2].
A coupled model contains the following information:
·
set of input ports through which external events are received,
·
set of output ports through which external events are sent,
·
external input coupling (EIC) which connects the input ports of the coupled model
to one more of the input ports of the components this directs inputs received by
the coupled model to designated component models,
·
external output coupling (EOC) which connects output ports of components to
output ports of the coupled model thus when an output is generated by a
component it may be sent to a designated output port of the coupled model and
thus be transmitted externally,
·
internal coupling (IC) which connects output ports of components to input ports of
other components- when an input is generated.
Formally, a coupled model DN is defined as:
SELECT
IC
EOC
EIC
M
Y
X
DN
,
,
,
,
,
,
=
selector
breaking
tie
0
2
relation
coupling
internal
relation
coupling
output
external
relation
coupling
input
external
DEVS
in
models
component
all
of
set
set
events
output
set
events
input
:
.
:
:
.
.
:
.
.
:
.
.
:
:
:
M
SELECT
IN
M
OUT
M
IC
OUT
DN
OUT
M
EOC
IN
M
IN
DN
EIC
M
Y
X
M
-
×
×
×
where the extensions .IN and .OUT represent the input ports set and the output ports
set of respective DEVS models [2].
14
System Specification Formalism
3.5 Abstract Simulators for DEVS Models
In order to interpret the model, the computer needs an abstract simulator. This
concept was defined by Zeigler.
The abstract simulator is a conceptual device capable of interpreting the dynamics of
DEVS models. It takes a modular, hierarchical discrete event model and runs a
simulation experiment. So the modular, hierarchical model can be readily transferred
into an executable simulation program.
The abstract simulator for DEVS has an hierarchical structure reflecting the structure
of the model (figure 3.5-1). It consists of two types of object the simulators and the
coordinators. With every atomic model we associate a simulator, with every coupled
model a coordinator is associated. To initiate the simulation cycles a root coordinator
is employed. It is attached to the overall network coordinator. While simulation takes
place, messages are passed among the simulators and coordinators. Thereby, it is
not important, if a message is passed to a coordinator or a simulator, both are able to
process the same kinds of messages.
The abstract simulator consisting of objects and working with message passing is
readily implementable in an object-oriented programming language [1].
root coordinator
coordinator
simulator
simulator
simulator
simulator
coordinator
Figure 3.5-1 Abstract simulator attached to a hierarchical model [1]
15
System Specification Formalism
As the models are passive elements, all kinds of events and messages are caused
by and passed among simulators and coordinators not among the associated
models.
The job of an abstract simulator for an atomic model is to schedule the next event
time and to request the associated atomic model to execute its transition functions
and output function timely. After an external event message is received by a
simulator it causes the associated atomic model to:
e
·
process its external transition function
xt
·
its time advance function ta
When the scheduled time comes, a simulator requests the associated model to
execute the following functions in the order:
·
output function
·
internal transition function
in
t
·
time advance function ta
It is to be kept in mind that the order of the calls is very important for the simulation
flow.
The complete definition for an abstract simulator by Zeigler is more detailed.
Zeigler defines four different kinds of messages passed among coordinators and
simulators:
1. i-messages for initialization purposes
2. *-message which indicates that an internal event shall be executed
3. x-message which indicates the arrival of an external event
4. Y-message which reports the output of selected components
16
System Specification Formalism
3.5.1 The DEVS simulator
Implementation of a DEVS simulator with pseudo-code
Devs-simulator
variables:
parent
--parent
coordinator
tl
--time of last event
tn
--time of next event
DEVS
--associated
model
with total state (s, e)
y
--current output value of the associated model
when receive i-message (i, t) at time t
tl:=
t-e
tn:= tl + ta(s)
when receive *-message (*, t) at time t
then
tn
t
if
error:
bad
synchronization
y:=
(s)
send value y in y-message (y, t) to parent coordinator
s:=
int
(s)
tl:= t
tn:= tl + ta(s)
when receive x-message (x, t) at time t with input value x
if not (tl t tn) then
error:
bad
synchronization
s:=
ext
(s, t tl, x)
tl:=
t
tn:= tl + ta(s)
end DEVS-simulator
17
Ende der Leseprobe aus 104 Seiten
- nach oben
Details
- Arbeit zitieren
- , 2003, Development of an Object-Orientated DEVS-Simulator with MATLAB®, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/223665
Ähnliche Arbeiten
Deutschlands größter Sharing Community
Jetzt Zusammenfassungen, Skripte und Klausuren kostenlos downloaden!
Uniturm.de
Ihre Vorteile als Autor
Geld verdienen Für jedes verkaufte Exemplar erhalten Sie Autorenhonorar - bis zu 40%.Kostenlose Buchveröffentlichung
Als eBook-Studie im Original und / oder auf Wunsch zusätzlich als hochwertiges Fachbuch in unserem renommierten Buchverlag.
Renommee als Fachbuchautor
Präsentieren Sie sich als Fachfrau oder Fachmann in Ihrem Fachgebiet und machen Sie sich bekannt.
Persönliche Betreuung
Unser Lektorat wird Sie persönlich betreuen und ist auch telefonisch unter 040-655992-14 erreichbar.
Weltweit im Buchhandel
Ihr Buch ist weltweit im Buchhandel und Online-Buchhandel wie z.B. amazon erhältlich.
Jetzt Autor werden!
Kommentare