Hochschule Wismar - University of Technology Business & Design

Master-Projektarbeit

Untersuchungen zur Transformation von DEVS-Modellen in EGM-Modelle

Dipl.-Ing. (FH) Frank Meller		Betreuer: Prof. Dr.-Ing. Thorsten Pawletta, FB MVU

Problemstellung

Für diskret-ereignisorientierte Systeme gibt es eine Vielzahl von Modellierungs- und Simulationsansätzen. Dazu gehört neben Petri-Netzen und anderen auch die Modellierung mittels Ereignisgraphenmodellen (EGM). Es existiert zudem ein allgemeiner Ansatz zur Abbildung dieser Systeme mit Hilfe der Discrete Event System Specification (DEVS).

Es wurde ein Weg gefunden, um EGM-Modelle direkt in DEVS-Modelle überführen zu können. Die Transformation soll die Simulation von EGM-Modellen mit einem DEVS-Simulator ermöglichen. Basierend auf den Grundlagen beider Modellierungsansätze und deren Simulatorstrukturen wurden zwei Variationen der Transformation entwickelt. Für einen der beiden generierten Transformationsansätze wurde eine prototypische Modellierungs- und Simulationsumgebung erstellt, die eine vollständige programmtechnische Validierung erlaubt. Für den zweiten Transformationsansatz wurden die Grundlagen der Programmstrukturen theoretisch erläutert.

EGM-Formalismus

Ereignisgraphen stellen für diskret-ereignisorientierte Modelle eine intuitive und leistungsfähige grafische Modellierungsbasis dar. Wie in der nachfolgenden Abbildung gezeigt, besteht eine einfache Struktur aus Knoten (A, B) und Kanten (Pfeile). Auf den Kanten befinden sich eine Verzögerung (Zeit t) und eine Bedingung (i). Den Knoten sind Zustandsänderungen zugeordnet. Sie befinden sich in den geschweiften Klammern unterhalb der Knoten und stellen die Ereignisse dar. Die abgebildete Struktur enthält folgende Aussage:

,,Wenn Ereignis A eingetreten und Bedingung i wahr ist, dann plane Ereignis B für den Zeitpunkt T+t ein.''

T ist die aktuelle Simulationszeit.

Figure: Grundlegende EGM-Struktur

Die Zustandsänderungen beziehen sich auf globale Zustandsgrößen, die im ganzen Modell bekannt sind. Die Struktur lässt sich beliebig erweitern. Knoten können auch mit sich selbst verknüpft werden.

DEVS-Formalismus

Ausgangspunkt ist der Formalismus für klassische DEVS (classic DEVS). Alle klassischen DEVS setzen sich aus atomaren (atomic) und gekoppelten (coupled) DEVS zusammen. Ein gekoppeltes DEVS kann von außen betrachtet als atomares DEVS angesehen werden, da es sich entsprechend verhält. Damit lassen sich auf einfache Weise hierarchische Systeme aufbauen.

Ein atomares DEVS hat äußerlich betrachtet folgendes Verhalten:

• nimmt jederzeit (über Ports) Eingangswerte entgegen
• liefert spontan (über Ports) Ausgangswerte

Innerlich betrachtet findet sich eine exakt definierte Struktur, die über zwei Überführungsfunktionen und eigene Zustände verfügt. Vereinfacht beschrieben geschieht Folgendes:

• Trifft ein äußeres Ereignis ein, dann wird die externe Überführungsfunktion $\delta ext$ aufgerufen, die ggf. die Zustände des atomaren DEVS verändert. Aus den aktualisierten Zuständen wird die Zeit $ta$ ermittelt, die bis zur inneren Überführung $\delta int$ verstreichen wird wenn zwischenzeitlich keine weiteren Signale eingehen.
• Ist die Zeit $ta$ verstrichen und kein weiteres Signal eingegangen, werden Ausgangswerte generiert ($\lambda$-Funktion). Anschließend wird die interne Überführung ausgeführt, die wiederum die Zustände des atomaren DEVS ändert. Eine neue Zeit $ta$ wird ermittelt und gespeichert.

Folgende Abbildung veranschaulicht diesen Prozess:

Figure: Atomares DEVS

Gekoppelte DEVS regeln das Zusammenspiel der atomaren DEVS. Sie enthalten Informationen, kennen alle vorhanden Komponenten, deren Verbindungen untereinander und mit der Umgebung des gekoppelten DEVS. Weiterhin enthalten sie Informationen um die Prioritäten der Komponenten einzuordnen.

Ein DEVS-Modell kann eine beliebige hierarchische Struktur annehmen:

Figure: DEVS-Hierarchie (Beispiel)

Transformationsansatz

Die Transformation beruht darauf, dass ein EGM-Modell, wie in der Abbildung dargestellt, in einzelne Elemente eingeteilt wird. Jedes einzelne Element beinhaltet nur eine externe Kante:

Figure: Aufteilung eines EGM-Modells in Elemente (Beispiel)

Aus den Elementen werden anschließend atomare DEVS generiert. Die Struktur des EGM-Modells wird im gekoppelten DEVS abgelegt und beinhaltet alle zuvor erzeugten atomaren Komponenten.

Da es im DEVS-Formalismus keine globalen Variablen gibt, wird in einer erweiterten Variante ein Synchronisator eingeführt. Der Synchronisator ist ein zusätzliches atomares DEVS, dass für die modellweite Aktualisierung der Zustandsgrößen verantwortlich ist:

Figure: Synchronisator im DEVS-Modell

Modellierungs- und Simulationsumgebung

Mit Hilfe des Programmsystems Matlab wurde eine Simulationsumgebung geschaffen in der alle Zustandsgrößen global vorliegen. Aus Vorlage-Dateien werden geeignete Modelldateien zur Verarbeitung im Simulator generiert. Dazu werden die Informationen aus den zuvor generierten Elementen beziehungsweise aus den atomaren DEVS entnommen und in die Dateien eingetragen. Das gekoppelte DEVS wird gleichermaßen in einer Vorlage-Datei abgebildet. Zusätzlich sind die Kennzeichnung der globalen Zustandsvariablen sowie deren Auswertung zu beachten.

Zusammenfassung und Ausblick

Aufgrund der sehr umfangreichen Programmierung konnten die Modellierungsansätze und Formalismen zwar nur bedingt programmtechnisch validiert werden, jedoch ist es gelungen die wesentlichen Aspekte einer Transformation herauszuarbeiten.

Die konsequente Übertragung der elementaren in einem EGM enthaltenen Daten ermöglicht eine sichere Transformation der Modellierungsstrukturen von EGM nach DEVS. Es konnte nachgewiesen werden, dass der erarbeitete Formalismus prinzipiell lauffähig ist. Der erweiterte Ansatz mit Synchronisator zeigt, wie sich die Zustandsgrößen in das Modell einfügen lassen.

Die Forschungsarbeit wird vom Autor in Form einer Master-Thesis weitergeführt. Zusätzliche Schwerpunkte dabei sind:

• Literaturrecherche
• DEVS-Erweiterungen
• Entwicklung eines verbesserten oder neuen Transformationsansatzes
• Objektorientierte Programmierung mit Matlab und objektorientierter DEVS-Simulator-Prototyp