Development of an Object-Orientated DEVS-Simulator with MATLAB®

Deatcu, Christina

Leseprobe

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

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.

Contents

Contents

Introduction ... 1

Modeling and Simulation ... 3

2.1

The General Scientific Problem Solving Process... 3

2.2

Simulation ... 4

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

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

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

Bank Simulation Example... 60

6.1

System Decomposition ... 61

6.2

Model Building ... 63

6.3

Execution of the Example ... 65

Conclusions and Open Problems ... 66

A References... 69

B Figure Index... 70

C Appendix... 71

D Abbreviations ... 96

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

way of defining classes, a complicated, hard to follow up file structure is needed to

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.

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.

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].

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

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.

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]

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].

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).

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 = <

set of states

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 = <

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].

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].

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].

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

: 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

System Specification Formalism

3.4.1 Specification Semantics for an Atomic DEVS Model

An atomic discrete event systems (DEVS) is a structure[Zeigler]

(

)

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

int

ext

and

( )

{

)

(

}

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.

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

EOC

EIC

selector

breaking

tie

relation

coupling

internal

relation

coupling

output

external

relation

coupling

input

external

DEVS

models

component

all

set

events

output

set

events

input

SELECT

OUT

EOC

EIC

where the extensions .IN and .OUT represent the input ports set and the output ports

set of respective DEVS models [2].

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

coordinator

Figure 3.5-1 Abstract simulator attached to a hierarchical model [1]

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:

process its external transition function

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

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

System Specification Formalism

3.5.1 The DEVS simulator

Implementation of a DEVS simulator with pseudo-code

Devs-simulator

variables:

parent

--parent

coordinator

--time of last event

--time of next event

DEVS

--associated

model

with total state (s, e)

--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

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:=

tn:= tl + ta(s)

end DEVS-simulator

Ende der Leseprobe aus 104 Seiten - nach oben

Details

Titel

Development of an Object-Orientated DEVS-Simulator with MATLAB®

Autor

Christina Deatcu (Autor:in)

Erscheinungsjahr

2003

Seiten

104

Katalognummer

V223665

ISBN (eBook)

9783832486884

ISBN (Buch)

9783838686882

Dateigröße

1275 KB

Sprache

Englisch

Schlagworte

simulation programmierung softwareentwicklung modellbildung oberfläche

Produktsicherheit

Diplom.de

Arbeit zitieren

Christina Deatcu (Autor:in)

, 2003, Development of an Object-Orientated DEVS-Simulator with MATLAB®, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/223665

Kommentare

Noch keine Kommentare.

Melden Sie sich an, um einen Kommentar zu schreiben

Development of an Object-Orientated DEVS-Simulator with MATLAB®

Autor

Kategorie

Institution / Hochschule

Note

Leseprobe

Details

Kommentare

Ihre Vorteile als Autor