
sawine@1: \chapter{Entwurf}
sawine@1: Die Entwurfsphase definiert die zu realisierenden Module, die alle gestellten Anforderungen erfüllen. Dabei werden u.a. verschiedene Lösungsvarianten verglichen und die Einbindung von Hilfswerkzeugen geplant.\\\\
sawine@1: Ab diesem Abschnitt werden die beiden Komponenten mit ihren Systemnamen referenziert:
sawine@1: \begin{itemize}
sawine@1: \item \textbf{ATCCL}\\
sawine@1: Die \emph{Air Traffic Control Constraint Language} ist die domänenspezifische Modellierungssprache der Luftraumbeschränkungen. Sie gilt als die Konfigurationssprache der DFLOW-Komponente. Der dazugehörige Compiler und die virtuelle Maschine werden oft auch mit dieser Abkürzung, oder aber explizit als das \emph{ATCCL-Framework}, referenziert.
sawine@1: 
sawine@1: \item \textbf{DFLOW}\\
sawine@1: DFLOW bezeichnet die Abflugplanungskomponente und steht für \emph{Departure Flow}.
sawine@1: \end{itemize} 
sawine@1: 
sawine@1: \section{ATCCL}
sawine@1: Die Anforderungen spannten einen Raum von möglichen Lösungsansätzen auf, während die Sicherheits- und Benutzerakzeptanz  die realisierbaren Möglichkeiten reduzierten. So wurde die Gestaltungsmöglichkeit der Syntax der Modellierungssprache durch die Benutzerzielgruppe stark begrenzt, die Semantik wurde zum großen Teil durch die Anwendungsdomäne bestimmt.\\\\
sawine@1: Bei strikten Vorgaben, also der Reduktion der Freiheiten, gestaltet sich die Entwicklung des Systementwurfs höchst effizient. Da der Grobentwurf zu einem großen Teil eine direkte Ableitung der Anforderung ist, hat sich die Entwurfsphase auf die einzelnen Module und deren Interaktion beschränkt.
sawine@1: 
sawine@1: \subsection{Syntax}
sawine@1: Bereits in der Anforderungsanalyse wurden Syntaxprototypen entwickelt, welche sowohl dem Kunden als auch den Projektmitarbeitern präsentiert wurden. Dieses Vorgehen ist hilfreich, um aus einer Reihe von Kandidaten, die mit vergleichbarer Komplexität die selben Ergebnisse liefern, die geeigneteren herauszufinden.\\\\
sawine@1: Zur Spezifizierung der ATCCL-Syntax wurde anhand der Anforderungen und den Prototypen ein vollständige \emph{Erweiterte Backus-Naur-Form} -- kurz EBNF, siehe \cite{ebnf} -- für die Syntax erstellt. Die EBNF wird zur Darstellung von kontextfreien Grammatiken genutzt, ist standardisiert und eignet sich sowohl als Spezifikation der Syntax einer Sprache als auch als Basis für die Erstellung von Parser oder Compiler mit Hilfe von Werkzeugen. Folgend befindet sich die komplette Spezifikation der ATCCL.
sawine@1: 
sawine@1: \subsubsection{Notation}
sawine@1: Die Syntax ist in EBNF spezifiziert. Klein geschriebene Produktionsnamen werden zur Tokenidentifizierung verwendet. Nicht-Terminale werden groß geschrieben. Direkte lexikalische Symbole werden in doppelten Anführungszeichen umschlossen.\\\\
sawine@1: Die Form a ... b beschreibt eine Menge von Zeichen, angefangen von a bis b.\\
sawine@1: \lstinputlisting[label=EBNF Notation,caption=EBNF Notation,language=TeX]{ebnf.txt}
sawine@1: 
sawine@1: \subsubsection{Buchstaben und Ziffern}
sawine@7: Standardflugpläne unterstützen nur ASCII-Zeichen, deshalb gibt es keine Unicode-Unter"-stützung bei Zeichen. Die Sprache und der Compiler sind in der Lage, neben den natürlichen Zahlen auch reelle Zahlen zu verarbeiten. Jedoch gibt es keine reellen Merkmale in einem Flugplan.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Buchstaben und Zeichen,caption=ATCCL EBNF Buchstaben und Zeichen,language=TeX]{atccl_letters_digits.txt}
sawine@1: Zusätzlich gibt es eine Produktionsregel für alle sichtbaren Zeichen, diese sind zulässige Eingaben innerhalb eines Kommentars oder einer Zeichenkettenkonstante.
sawine@1: 
sawine@1: \subsubsection{Kommentare}
sawine@1: ATCCL unterstützt nur einen Typ von Kommentaren, den Zeilenkommentar.
sawine@1: 
sawine@1: Ein Kommentar wird mit dem Zeichen \# eingeführt, zum Kommentar gehört der nachfolgende Text bis zum Ende der Zeile. Will man ein Kommentar über mehrere Zeilen setzen, so muss jede Kommentarzeile mit \# eingeleitet werden.\\\\
sawine@1: Kommentare werden vom Parser ignoriert und können alle unterstützen Zeichen enthalten.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Kommentare,caption=ATCCL EBNF Kommentare,language=TeX]{atccl_comments.txt}
sawine@1: 
sawine@1: \subsubsection{Terminatoren}
sawine@7: ATCCL ist frei von Terminatoren. Es muss kein besonderes Zeichen -- bei vielen Sprachen ist es ein Semikolon, bei Prolog ein Punkt und bei Python das Zeilenende -- zur Terminierung einer Anweisung gesetzt werden. Die Sprache verzichtet dadurch auf ein weiteres syntaktisches Element zur Vereinfachung und Bereinigung der Syntax.\\\\
sawine@1: Aufgrund der einfachen und abgeschlossenen Struktur der Regeldefinitionen wird eine differenzierte Fehlerdiagnose basierend auf der Klammersetzung erreicht.
sawine@1: 
sawine@1: \subsubsection{Bezeichner}
sawine@1: Ein Bezeichner setzt den Identifizierungsnamen für eine Regeldefinition. Er kann sich aus beliebigen Buchstaben und Ziffern zusammensetzen und das Unterstrichsymbol beinhalten, solange er mit einem Buchstaben beginnt.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Bezeichner,caption=ATCCL EBNF Bezeichner,language=TeX]{atccl_ids.txt}
sawine@1: 
sawine@1: \subsubsection{Schlüsselwörter}
sawine@1: Schlüsselwörter werden in ATCCL zur Festlegung von Regeldefinitionstypen und für die Operatoren verwendet. Zusätzlich gibt es eine Reihe von Schlüsselwörter, welche die Einträge eines Flugplans bezeichnen.
sawine@1: 
sawine@1: Folgende Schlüsselwörter sind reserviert und dürfen nicht als Regeldefinitionsbezeichner genutzt werden.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Schluesselwoerter,caption=ATCCL EBNF Schluesselwoerter,language=TeX]{atccl_keywords.txt}
sawine@1: Die SI-Typen zur Zeitangabe, \emph{s} für Sekunde und \emph{min} für Minute, sind Schlüsselwörter in der ATCCL-Syntax, diese sind jedoch nicht auf globaler Ebene reserviert und werden nur innerhalb einer Constraint-Regeldefinition genutzt.
sawine@1: 
sawine@1: \subsubsection{Datentypen und Konstanten}
sawine@1: Zur erfolgreichen Modellierung der Flussdichtenbeschränkungen eines Fluginformationsgebiets müssen sowohl alle Einträge eines Flugplans als auch Zeitangaben von der Sprache unterstützt werden.
sawine@1: 
sawine@3: Die Flugplaneinträge sind in sechs verschiedenen Datentypen erfasst. Als Grundtypen gelten einzelne Zeichen, zusammengesetzte Zeichenketten (Wörter) und die natür\-lichen Zahlen. Für jeden Grundtyp gibt es die Möglichkeit mehrere Werte in einer Liste zusammenzufassen.\\\\
sawine@1: Zur Festlegung von Separationsregeln ist es notwendig Zeitangaben sowohl in Minuten und in seltenen Fällen sekundengenau zu definieren. Um Regeln bestimmten Uhrzeiten zuzuweisen, ist es notwendig, minutengenau die Tageszeit festzulegen.\\\\
sawine@1: ATCCL kennt folgende Datentypen:
sawine@1: \begin{itemize}
sawine@1: \item Zeichenkette (String)
sawine@7: \item ganze Zahl (Integer)
sawine@1: \item Zeichenkettenliste 
sawine@7: \item Liste von ganzen Zahlen
sawine@1: \end{itemize}
sawine@1: \lstinputlisting[label=ATCCL EBNF Datentypen,caption=ATCCL EBNF Datentypen,language=TeX]{atccl_datatypes.txt}
sawine@1: Die Sprache kommt mit nur zwei Basisdatentypen aus und sie erlaubt zudem noch die Zusammenfassung mehrerer Konstanten in einer Liste. Eine Liste wird durch eckige Klammern gekennzeichnet, wobei die einzelnen Element mit Kommata separiert sind.\\\\
sawine@1: Zu bemerken sind der fehlende Datentyp zur Uhrzeitbestimmung und eine ungewöhnliche Variante von natürlichen Zahlen, wobei eine Zahl mit einer Null beginnen darf. Beide Besonderheiten hängen zusammen: indem vorgeschaltete Nullen bei dem Integer-Datentyp zugelassen werden, kann man auf einen dedizierten Datentyp für die Uhrzeit verzichten und akzeptiert somit die direkte Eingabe im HHMM-Format. Dieses Format ist in der Flugsicherung geläufig und wird auch in den Flugplänen und anderen Flugsicherungssystem so erfasst.\\\\
sawine@1: Alle im Code verwendeten Konstanten müssen von einem der definierten Datentypen sein.
sawine@1: 
sawine@1: \subsubsection{Flugplaneigenschaften}
sawine@1: Alle für das System relevanten Einträge eines Flugplans -- auch Flugplaneigenschaften genannt -- sind in ATCCL als Schlüsselwörter reserviert und mit einem festen Datentyp versehen.
sawine@1: 
sawine@1: Um auf Eigenschaften zu operieren, werden diese entsprechend ihrem Datentyp in eine Produktion zusammengefasst.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Flugplaneigenschaften,caption=ATCCL EBNF Flugplaneigenschaften,language=TeX]{atccl_properties.txt}
sawine@1: Eine Besonderheit stellt das Property EQUIP dar. In der EBNF-Spezifizierung ist es als Zeichenliste definiert. Bei der weiterführenden Verarbeitung wird trotzdem auf den Datentyp Zeichenkette (String) zurückgegriffen, dadurch werden spezielle Operationen auf dieser Eigenschaft möglich.\\\\
sawine@1: Das Navigationsausrüstungsfeld (Navigational Equipment) eines Flugplans ist eine Aneinanderreihung von Buchstaben, wobei jeder Buchstabe für eine fest definierte Navigationsausrüstung steht. Es ist üblich, die einzelnen Buchstaben ohne Trennungszeichen aneinanderzureihen, was dem Basisdatentyp Zeichenkette entspricht. Gleichzeitig gilt diese besondere Zeichenkette als eine Liste von Zeichen, damit auch Teilmengenoperatoren darauf angewendet werden können.
sawine@1: 
sawine@1: \subsubsection{Operatoren}
sawine@1: Nach der Definition der Datentypen und der Zuweisung der Flugplaneigenschaften zu dem jeweiligen Datentyp folgt die Spezifizierung der Operationen auf den Konstanten und Flugplaneigenschaften.\\\\
sawine@1: Alle Operationen werden mit Hilfe von Operatoren definiert. Eine Operation ist in der Regel ein Tupel von Operator, einer Flugplaneigenschaft und mindestens einer Konstanten.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Operatoren,caption=ATCCL EBNF Operatoren,language=TeX]{atccl_operators.txt}
sawine@1: 
sawine@1: \subsubsection{Regeldefinitionen}
sawine@1: Ein ATCCL-Programm besteht aus Regeldefinitionen. Es gibt drei Typen von Regeldefinitionen: 
sawine@1: \begin{itemize}
sawine@1: \item Flugplanmuster
sawine@1: \item Separationsregel
sawine@1: \item Flow-Point
sawine@1: \end{itemize}
sawine@1: Ein Flugplanmuster definiert eine Regel, die bestimmte Flugplaneigenschaften prüft. Diese Regel setzt sich aus booleschen Termen zusammen und bedient sich dabei den Operatoren, Properties und Konstanten.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Flugplanmuster,caption=ATCCL EBNF Flugplanmuster,language=TeX]{atccl_patterns.txt}
sawine@1: Eine Separationsregel (Constraint) dient zur Festlegung der Separation an einem, oder mehreren Wegpunkten.\\\\
sawine@7: Zum erfolgreichen Durchsetzen einer Flussdichtenregelung reicht eine zeitliche Staffelung, denkbar sind jedoch auch Abstandsseparationen und das Setzen von durchschnittlichen Durchflussdichten verteilt auf eine Zeitspanne. Bei Fertigstellung dieser Arbeit wurde nur die zeitliche Staffelung unterstützt.\\\\
sawine@1: Die Separation kann in Minuten und Sekunden festgelegt werden, kann einen oder eine Liste von Wegpunkten betreffen und kann zeitabhängig sein.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Separationsregeln,caption=ATCCL EBNF Separationsregeln,language=TeX]{atccl_constraints.txt}
sawine@1: Der Flow-Point definiert eine Zuweisung von Flugplanmuster auf eine Separationsregel. Ein Flow-Point ist somit nicht an einen geographischen Wegpunkt gebunden. Diese Abbildung wird von der Abflugplanungskomponente zur Zuweisung von Flow-Points zu Flugplänen genutzt, worauf die Kalkulation des optimalen Abflugzeitpunkts basiert.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Flow Point,caption=ATCCL EBNF Flow Point,language=TeX]{atccl_flowpoints.txt}
sawine@1: Zur Verdeutlichung: die erste id dient zur Vergabe des Flow-Point-Namen, die zweite zur Identifizierung des Pattern und die dritte zur Zuweisung des Constraint. Dabei spielt die Lokalität der Pattern- und Constraint-Definition innerhalb der Konfigurationsdatei keine Rolle, diese müssen also nicht der Flow-Point-Definition voranstellen.
sawine@1: 
sawine@1: \subsubsection{Programm}
sawine@1: Ein ATCCL-Programm ist eine Konfiguration, welche sich aus einer Reihe von Regeldefinitionen zusammensetzt.\\
sawine@1: \lstinputlisting[label=ATCCL EBNF Konfiguration,caption=ATCCL EBNF Konfiguration,language=TeX]{atccl_config.txt}
sawine@10: \newpage
sawine@1: \subsection{Beispiele}
sawine@1: Anhand von repräsentativen Beispielen werden nun mögliche Einsätze der ATCCL vorgeführt.
sawine@1: 
sawine@10: \subsubsection{Bsp. 1: Zielstellung}
sawine@1: Es soll eine zeitliche Mindestseparationsbeschränkung von 5 Minuten an Wegpunkt \emph{COPPI} gesetzt werden. Die Beschränkung soll für alle Flüge gelten, die vom \emph{Dubai International Airport} starten und den Frankfurter Flughafen als Ziel haben. Der ICAO-Code für den Flughafen Frankfurt-Main ist \emph{EDDF} und für den Flughafen Dubai \emph{OMDB}.
sawine@1: 
sawine@10: \subsubsection{Bsp. 1: Code}
sawine@1: \lstinputlisting[label=ATCCL Einfaches Beispiel,caption=ATCCL Einfaches Beispiel,language=TeX]{atccl_example1.txt}
sawine@1: 
sawine@10: \subsubsection{Bsp. 1: Bemerkungen}
sawine@1: Der obige Code definiert einen Flow Point mit dem Namen \emph{DBCoppiDF}. Die Beschränkung auf diesem Flow Point, ist eine zeitliche Separation auf dem Wegpunkt \emph{COPPI}, dies ist in dem Constraint \emph{Coppi5} definiert. Die Bestimmung der Flugpläne, die dem Flow Point \emph{DBCoppiDF} zugeordnet werden, wird durch das Pattern \emph{DBCoppiDF} realisiert. Wie man sieht, ist die Namensauflösung nicht global, sondern basiert auf den drei Regeldefinitionstypen. So ist die mehrfache Vergabe eines Namens für mehrere Pattern-Definitionen nicht zulässig. Die Definition eines Patterns und eines Constraints mit gleichem Namen ist dagegen erlaubt.
sawine@1: 
sawine@10: \subsubsection{Bsp. 2: Zielstellung}
sawine@1: Ein weiteres Beispiel soll eine komplexe Regel realisieren. Es sollen folgende zeitliche Mindestseparationsbeschränkungen in Abhängigkeit der Uhrzeit gewährleistet werden:
sawine@1: \begin{enumerate}
sawine@1: \item 0:00 bis 6:00 Uhr: 5 Minuten, freigeschaltete Flugflächen sind 300, 320, 340
sawine@1: \item 6:01 bis 12:00 Uhr: 3 Minuten, freigeschaltete Flugflächen sind 300, 320
sawine@1: \item 12:01 bis 22:00 Uhr: 130 Sekunden, keine Höhenstaffelung
sawine@1: \end{enumerate}
sawine@1: Wie im ersten Beispiel gilt der Flow Point für alle Flüge, die von Dubai nach Frankfurt unterwegs sind. Die Separation soll dieses mal jedoch an dem Wegpunkt \emph{COPPI} oder \mbox{\emph{BALUS}} durchgeführt werden, abhängig davon welcher der beiden Wegpunkte in der jeweiligen Flugroute liegt.
sawine@1: 
sawine@10: \subsubsection{Bsp. 2: Code}
sawine@1: \lstinputlisting[label=ATCCL Komplexes Beispiel,caption=ATCCL Komplexes Beispiel,language=TeX]{atccl_example2.txt}
sawine@1: 
sawine@10: \subsubsection{Bsp. 2: Bemerkungen}
sawine@1: Der Flow Point \emph{Example2} realisiert alle Anforderungen aus der Zielstellung. Es ist ersichtlich, dass für den Zeitraum von 22:01 Uhr bis 23:59 keine Separation definiert wird, in dieser Zeit gilt keine Beschränkung auf dem Flow Point. Liegen beide Wegpunkte in der Route, so wird lediglich auf einem Wegpunkt gestaffelt. Die Sprache macht keine Aussagen darüber, welcher Wegpunkt in so einem Fall gewählt wird.\\\\
sawine@1: Diese Beispiele sollen keine realistischen Gegebenheiten realisieren und dienen somit ausschließlich der Beschreibung der möglichen Anwendungen der Sprache. Im letzten Beispiel tritt durch die Wegpunkte eine Uneindeutigkeit für die Wegpunktwahl zur Staffelung auf, da die Wegpunkte \emph{BALUS} und \emph{COPPI} sich oft in einer Route befinden. Die Konfigurationen der realen Luftraumbeschränkungen sind im Gegensatz dazu eindeutig gewählt.
sawine@1: 
sawine@1: \subsection{Compiler}
sawine@1: Der Übersetzer soll eine ATCCL-Konfiguration in C++-Strukturen überführen. Die entstandene Objektdatenbank wird die Eingabe für die virtuelle Maschine darstellen, auf der alle Laufzeitoperationen stattfinden.\\\\
sawine@1: Vor der Überführung in den Bytecode wird der Syntaxbaum erstellt, dabei gilt es die Konfiguration auf Fehler zu überprüfen. Der Compiler besteht somit aus einem Analysemodul und einem Synthesemodul. Die Analysephase beinhaltet die lexikalische Analyse gefolgt von der Syntaxanalyse.
sawine@1: \begin{figure}[h]
sawine@1: \centering \includegraphics[width=220pt]{images/compile_process.pdf}
sawine@1: \caption{Der Übersetzungsprozess}
sawine@1: \label{fig:compile_process}
sawine@1: \end{figure}
sawine@1: 
sawine@1: \subsubsection{Scanner}
sawine@1: Das Modul der lexikalischen Analyse -- auch Scanner genannt -- erstellt aus dem ATCCL-Code eine Token-Codierung. Der Quellcode wird hierbei auf definierte Token untersucht, die Token dienen als Eingabe für die Syntaxanalyse.\\\\
sawine@1: \texttt{GNU flex} bietet eine effektive Möglichkeit lexikalische Scanner zu generieren. Die Basis des Scanners ist eine \texttt{flex}-spezifische Konfiguration zur Definition der Token. Die Konfiguration verwendet eine Syntax ähnlich den regulären Ausdrücken und ist in der Lage Produktionen für Untermengen von Zeichenketten zu erstellen, die bestimmte Entitäten einer Sprache darstellen. Anhand der Konfiguration erstellt \texttt{flex} C-Code für einen Scanner, welcher durch das Bereitstellen eines Interface mit einen \texttt{yacc}- oder \texttt{bison}-generierten Parser gekoppelt werden kann.
sawine@1: 
sawine@1: \subsubsection{Parser}
sawine@1: Getrieben durch die Ausgabe des Scanners wird die Syntaxanalyse durchgeführt. Diese Aufgabe übernimmt im ATCCL-Framework der Parser.\\\\
sawine@1: Der Parser wird mit Hilfe von \texttt{bison - GNU Parser Generator} erstellt. Der Parser benötigt ähnlich wie der Scanner eine spezifische Konfiguration, diesmal analog zu der BNF/EBNF-Notation. \texttt{bison} generiert ebenfalls C-Code, basierend auf der \texttt{bison}-Konfigurations"-datei und der Header-Datei des \texttt{flex}-generierten Scanners.\\\\
sawine@1: Das Resultat ist ein Syntaxbaum und eine Symboltabelle der ATCCL-Konfiguration. Der Baum hält die Struktur des Codes fest, während die Symboltabelle Tupel mit Regelsymbol, Regeltyp und Regelreferenz hält. Die semantische Prüfung erlaubt die Analyse von Zusammenhängen zwischen den Elementen eines Programms. Die Prüfung meldet u.a. die Verwendung unerlaubter Kombinationen von Datentyp und Operator und falsche Typenwahl bei Konstanten. 
sawine@1: 
sawine@1: \subsubsection{Synthese}
sawine@1: Nach Abschluss der Analysephase erfolgt die Synthese. Anhand der Symboltabelle werden alle Symbole in dem Syntaxbaum aufgelöst. Das Resultat sind vollständige Regeldefinitionen, die im nächsten Schritt in C++-Objekte transformiert werden.\\\\
sawine@7: Die Basis der Objektinstanziierung sollen \emph{Factory}-Klassen nach \cite{design_patterns} bilden. Die \texttt{Term"-Factory} wird die Instanzen der Regelterme realisieren. Durch ein Klassen-Template soll der Datentyp abstrahiert und dadurch eine generische Lösung für alle Fälle bereitgestellt werden. Gleiches gilt für die \texttt{OperatorFactory}. Diese soll je nach Datentyp einen passenden Operator instantiieren.\\\\
sawine@1: Durch die semantisch korrekte Verknüpfung der einzelnen Terme entstehen die Regeldefinitionen. Die Regelobjekte werden in einer semantischen Datenbank zusammengefasst und beinhalten zu diesem Zeitpunkt alle Konstanten und die Entscheidungsbäume zur Regelauswertung. Die semantische Datenbank -- auch \texttt{SemanticTree} genannt -- dient als Eingabe und Basis aller Transformationen für die virtuelle Maschine. Sie beinhaltet:
sawine@1: \begin{itemize}
sawine@1: \item \texttt{Pattern}-Regelinstanzen
sawine@1: \item \texttt{Constraint}-Regelinstanzen
sawine@1: \item \texttt{Flowpoint}-Mappings
sawine@1: \end{itemize}
sawine@1: Die \texttt{SemanticTree}-Datenstruktur bietet zusätzlich verschiedene Zugriffsmöglichkeit auf die Regeln und Mappings, u.a. nach der, in der Konfiguration, vergebenen id, also den Namen bzw. Symbol der Regeldefinition. 
sawine@1: 
sawine@1: \subsection{Virtuelle Maschine}
sawine@7: Die virtuelle Maschine bietet eine API\footnote{Application Programmable Interface -- eine Programmierschnittstelle zur Bereitstellung von Softwarefunktionen und zur Integration mit anderen Softwaremodulen} mit folgenden Merkmalen:
sawine@1: \begin{itemize}
sawine@1: \item \textbf{Evaluierung von Flugplan nach Flugplanmuster}\\
sawine@1: Eingangsparameter: \emph{Pattern}, \emph{FlightPlan} (siehe Abschnitt \ref{design:flight_plan})\\
sawine@1: Ausgangswert: \emph{Boolean}, \emph{true} falls das Muster für den Flugplan gültig ist, sonst \emph{false}
sawine@1: 
sawine@1: \item \textbf{Zuordnung von Flow-Points zu Flugplan}\\
sawine@1: Eingangsparameter: \emph{FlightPlan}\\
sawine@1: Ausgangswert: \emph{FlowpointCollection}, eine Liste von \emph{Flowpoint}-Referenzen, denen der Flugplan zugeordnet wird
sawine@1: 
sawine@1: \item \textbf{Durchsetzung einer Separationsregel zwischen zwei Flugplänen}\\
sawine@1: Eingangsparameter: \emph{FlightPlan 1}, \emph{FlightPlan 2}, \emph{Constraint}\\
sawine@1: Ausgangswert: \emph{FlightPlan}, dessen Abflugzeit entsprechend des \emph{Constraint} angepasst wurde, um keine Luftbeschränkungen zu verletzen
sawine@1: \end{itemize}
sawine@1: Alle Operationen basieren auf den übergebenen Flugplänen und der semantischen Datenbank, die vom Compiler geliefert wird (Abb. \ref{fig:virtual_machine_basic}). Eine detaillierte Beschreibung zu der Evaluation von Flugplanmuster und der Bestimmung von optimalen Abflugzeiten befindet sich in den Abschnitten \ref{design:pattern_evaluation} und \ref{design:atot_calculation}.\\
sawine@1: \begin{figure}[h]
sawine@1: \centering \includegraphics[width=300pt]{images/virtual_machine_basic.pdf}
sawine@1: \caption{ATCCL \texttt{VirtualMachine}}
sawine@1: \label{fig:virtual_machine_basic}
sawine@1: \end{figure}
sawine@1: 
sawine@1: \subsubsection{FlightPlan-Interface}
sawine@1: \label{design:flight_plan}
sawine@1: Die ATCCL-API steht in Abhängigkeit zum \texttt{FlightPlan}-Interface. Die Entscheidung über die Schnittstelle zum Flugplan war essentiell und deshalb nicht einfach. Dabei galt es möglichst hohe Sicherheit bei Laufzeit zu garantieren, ohne die Nutzung und das Testen der API unnötig kompliziert zu machen.\\\\
sawine@1: Zur Auswahl standen ein \texttt{StorageBinder}, der dynamisch zur Laufzeit Objekte vom Typ \texttt{Storage} binden und den internen Prozeduren in der \texttt{VirtualMachine} bereitstellen kann. Der Vorteil dieses Systems wäre der niedrige Wartungsaufwand bei Änderungen in den Flugplaneigenschaften. Bestandteile eines Flugplans, die für ein Projekt nicht relevant sind, könnten ignoriert werden. Der Nachteil ist die hohe Fehleranfälligkeit seitens des Benutzers. Sobald ein Benutzer nicht alle notwendigen Strukturen in den \texttt{StorageBinder} übergibt, fehlen der virtuellen Maschine möglicherweise \texttt{Properties}, die es zur Verarbeitung benötigt. Die Fehlerbehandlung muss bei Laufzeit geschehen und erhöht dadurch die Fehleranfälligkeit des Systems.\\\\
sawine@1: Zur Vorbeugung vor Bedienungsfehler wird ein monolithisches Interface verwendet, das \emph{Zugriffsmethoden} zu allen Flugplaneigenschaften deklariert, siehe Anhang \ref{uml:flight_plan_interface}. Der Vorteil dieses Designs bietet eine vollständige Kontrolle über die Implementierung bei \emph{Über"-setzungszeit}. Der Nachteil liegt in der Test- und Wartbarkeit der Klasse. Zum Testen muss hierfür auf eine \emph{Dummy}\footnote{Ein Objekt, das ein Interface mit statischen Rückgabewerten und Verhalten implementiert}-Implementierung oder ein \emph{Mock-Object}\footnote{Ein Objekt, das ein Interface mit zur Laufzeit bestimmten Werten und Verhalten implementiert} zurückgegriffen werden. Sobald eine Änderung des Interface erfolgt, muss jeder Nutzer dieser Bibliothek Anpassungen vornehmen.\\\\
sawine@1: Um dem Letzteren entgegenzuwirken, wurde das Interface außerhalb des ATCCL-Frame"-works, in der sog. \texttt{stdbase}-Bibliothek abgelegt. Zusätzlich wurde eine \texttt{DMAP}-spezifische Implementierung in der \texttt{DMAP}-Bibliothek erstellt. Dies bedeutet, dass ein Benutzer des ATCCL-Frameworks nicht selbständig das Interface zu realisieren hat, sondern auf die \texttt{DMAP}-spezifische Version zurückgreifen kann. Gleichzeitig bleibt das ATCCL-Framework unabhängig von externen Bibliotheken. Eine Ausnahme bildet die Abhängigkeit von \texttt{stdbase}, wobei diese bereits bestand und wünschenswert ist.\\\\
sawine@1: Flugsicherungssysteme und insbesondere deren Standards erfahren eine sehr langsame Evolution. So wurde die Spezifikation des aktuellen Flugplanstandards bereits vor mehrere Dekaden verabschieden. In den kommenden Jahren wird jedoch ein neuer Standard eingeführt, somit sind die Überlegungen zur effektiven Anpassung der Schnittstelle berechtigt.
sawine@1: 
sawine@1: \subsection{Compilerprototyp}
sawine@1: Als Abschluss der Entwurfsphase des ATCCL-Frameworks und Einleitung der Implementierung wurde ein Prototyp für den Übersetzer entwickelt. Anhand eines Beispiels sollte die Realisierbarkeit des Entwurfs bestätigt werden, besonderes Augenmerk galt dabei der erfolgreichen Integration der externen Werkzeuge wie \texttt{flex} und \texttt{bison} in den Compiler-Baustein.\\\\
sawine@1: Die drei Phasen des Compilers wurden inkrementell entwickelt und auf Funktionalität und Fehleranfälligkeit getestet. Bei diesem Vorgehen wurde eine alternative Compiler-Architektur verwendet, als in der finalen Version des Prototyps. Zur Steigerung der Flexibilität der Tests wurde ein Interpreter entwickelt, welcher eine dynamischere Eingabe erlaubte als es mit statischen Konfigurationsdateien möglich gewesen wäre.\\\\
sawine@1: Mit Hilfe des Interpreters konnte gut mit den Werkzeugen experimentiert werden. Es war ohne großen Aufwand möglich, die Syntax zu erweitern oder zu verändern. Durch das unmittelbare Feedback wurden so die letzten Zweifel beseitigt.\\\\
sawine@7: Der Verzicht auf unnötige Syntaxelemente, wie z.B. den Terminatoren, erhöhte die Komplexität der Fehlerfindung und Fehlerbehandlung. Sollen in einem Übersetzungs"-durchgang möglichst viele -- im Idealfall alle -- Fehler einer ATCCL-Konfiguration diagnostiziert werden, so muss eine differenzierte Fehlerbehandlung implementiert werden. Der Compiler muss in der Lage sein, eine Fehlerquelle genau zu lokalisieren, den Fehlerraum von der Bearbeitung ausschließen und die Zustandsmaschine in den letzten korrekten Zustand versetzen.\\\\
sawine@1: Terminatoren sind bei vielen Sprachen gut dafür geeignet solche Fehlerräume abzugrenzen, dadurch wird durch einen Fehler maximal eine Anweisung invalidiert. Durch das Entfernen der fehlerhaften Anweisung kann das restliche Programm übersetzt werden, mögliche Folgefehler sind meist trivial zu lösen. Im Falle der ATCCL-Syntax boten sich die runden Klammern zur Abgrenzung der Fehlerräume an. Alle ATCCL-Regeln enden mit einer solchen Klammer, somit ist im trivialen Fall ein Fehler dadurch auf eine Regel isoliert.\\\\
sawine@1: Die Nachteile dieser Fehlerbehandlungsmethode sind:
sawine@1: \begin{itemize}
sawine@1: \item bei einfachen Regeln\\
sawine@1: Es wird maximal ein Fehler pro einfacher Regel berichtet.
sawine@1: \item bei komplexen Regeln\\
sawine@1: Ein Fehler kann propagieren, es werden Folgefehler für die Regel berichtet.
sawine@1: \end{itemize}
sawine@1: Die Unterscheidung zwischen einfachen und komplexen Regeln besteht in dem Vorhandensein von Klammern innerhalb einer Regeldefinition, die dazu genutzt werden um Prioritäten der Auswertung von booleschen Termen festzulegen. Einfache Regeln haben keine Klammersetzung innerhalb der Regeldefinition.
sawine@1: 
sawine@1: \subsection{Evaluation von Flugplanmustern}
sawine@1: \label{design:pattern_evaluation}
sawine@7: Die virtuelle Maschine des ATCCL-Frameworks soll in der Lage sein, die Gültigkeit eines Musters anhand von Flugplandaten zu bestimmen. Die virtuelle Maschine initiiert die Evaluation des Musters durch die Weiterleitung des Flugplans an die \texttt{evaluate}-Methode der entsprechenden \texttt{Pattern}-Referenz.
sawine@1: 
sawine@1: \subsubsection{Beispiel}
sawine@1: Es sei folgendes Flugplanmuster definiert:\\
sawine@1: \lstinputlisting[label=ATCCL Pattern-Beispiel,caption=ATCCL Pattern-Beispiel,language=TeX]{pattern_example1.txt}
sawine@7: Das Muster definiert die Menge aller Flüge, die in Dubai starten (\emph{Aerodrome of Departure} ist \emph{OMDB}) und entweder eine höhere Geschwindigkeit als 200 kn erreichen (\emph{True Airspeed} ist größer als 200) oder der Wegpunkt \emph{BALUS} ist in der Flugplanroute enthalten.\\\\
sawine@1: Die Synthese übersetzt diese Konfiguration in eine Baumstruktur mit zwei Booleschen Termen repräsentativ für die beiden Booleschen Verknüpfungen und sechs Blattknoten, jeweils paarweise eine Konstante und eine Flugplaneigenschaft. Die Operatoren sind für die Aktionen der Terms zuständig, in diesem Beispiel realisieren diese eine Und-Verknüpfung, eine Oder-Verknüpfung, einen Äquivalenztest, einen numerischen Vergleich und eine Teilmengenrelation. Der genaue Schrittabfolge der Auswertung eines solchen Flugplanmusters wird anhand eines Beispiels erläutert.\\\\
sawine@1: Die folgenden Schritte beschreiben die Stationen des Algorithmus, Abb. \ref{fig:pattern_evaluation1} visualisiert den Pattern-Baum und die Schrittabfolge:
sawine@1: \begin{enumerate}
sawine@1: \item[0.] Per \texttt{evaluate}-Methode wird ein Flugplan an den Wurzelknoten übergeben. Die Flugplaneigenschaften seien wie folgt: ADES: OMDB, TAS: 280, ROUTE: DESDI TARDI RASKI.
sawine@1: \item Der \texttt{evaluate}-Aufruf propagiert bis zum ersten Blattknoten.
sawine@1: \item Das \emph{True Airspeed}-Attribut wird aus dem Flugplan extrahiert und an den Operator zurück"-gegeben. \emph{Wert: 280}.
sawine@1: \item Der Wert der Konstante wird an den Operator zurückgegeben. \emph{Wert: 200}.
sawine@1: \item Der Operator führt den Vergleich \emph{280 \textgreater 200} aus. Die \texttt{evaluate}-Methode terminiert mit dem \emph{Rückgabewert: true}.
sawine@1: \item Der Wert der \texttt{evaluation}-Rückgabe wird an den Oder-Operator zurückgegeben.
sawine@1: \item Der Oder-Operator wertet den Ausdruck \emph{true $\vee$ ?} aus. Die Auswertung des rechten Terms ist dadurch unnötig. \emph{Rückgabewert ist true}.
sawine@1: \item Der Rückgabewert aus 6 propagiert zurück zur Wurzel.
sawine@1: \item Zum Auswerten des Wurzelausdrucks \emph{true $\wedge$ ?} ist die Auswertung des rechten Terms nötig.
sawine@1: \item Das \emph{Aerodrome of Departure}-Attribut wird aus dem Flugplan extrahiert und zurück"-ge"-ge"-ben. \emph{Wert: OMDB}.
sawine@1: \item Der Wert der Konstante wird zurückgegeben. \emph{Wert: OMDB}
sawine@1: \item Der Operator führt den Äquivalenzvergleich \emph{OMDB $=$ OMDB} aus mit dem \emph{Ergebnis true}.
sawine@1: \item Das Ergebnis des Äquivalenzvergleichs wird zurück propagiert.
sawine@7: \item Der Operator evaluiert den Booleschen Ausdruck \emph{true $\wedge$ true} mit dem \emph{Ergebnis true}. Die Auswertung terminiert, der \texttt{evaluate}-Methodenaufruf gibt \emph{true} zurück.
sawine@1: \end{enumerate}
sawine@1: \begin{figure}[h]
sawine@1: \centering \includegraphics[width=280pt]{images/pattern_evaluation.pdf}
sawine@1: \caption{ATCCL \texttt{Pattern}-Evaluation-Beispiel}
sawine@1: \label{fig:pattern_evaluation1}
sawine@1: \end{figure}
sawine@1: 
sawine@1: %\begin{table}
sawine@1: %\begin{center}
sawine@1: %\begin{tabular}{cl}
sawine@1: %\toprule
sawine@1: %\textbf{Schritt} 	& \textbf{Aktion} \\
sawine@1: %\midrule
sawine@1: %0	& Per \texttt{evaluate}-Methode wird ein Flugplan an den\\
sawine@1: %	& Wurzelknoten übergeben. Die Flugplaneigenschaften seien wie folgt:\\ 
sawine@1: %	& ADES: OMDB, TAS: 280, ROUTE: DESDI TARDI RASKI.\\
sawine@1: %1	& Der \texttt{evaluate}-Aufruf propagiert bis zum ersten Blattknoten.\\ 
sawine@1: %2	& Das \emph{True Airspeed}-Attribut wird aus dem Flugplan\\
sawine@1: %	& extrahiert und an den Operator zurückgegeben. \emph{Wert: 280}.\\ 
sawine@1: %3	& Der Wert der Konstante wird an den Operator zurückgegeben.\\
sawine@1: %	& \emph{Wert: 200}.\\ 
sawine@1: %4	& Der Operator führt den Vergleich \emph{280 \textgreater 200}\\
sawine@1: %	& aus. Die \texttt{evaluate}-Methode terminiert mit dem\\
sawine@1: %	& \emph{Rückgabewert: true}.\\
sawine@1: %5	& Der Wert der \texttt{evaluation}-Rückgabe wird an den\\
sawine@1: %	& Oder-Operator zurückgegeben.\\ 
sawine@1: %6	& Der Oder-Operator wertet den Ausdruck \emph{true $\vee$ ?} aus.\\
sawine@1: %	& Die Auswertung des rechten Terms ist dadurch unnötig.\\
sawine@1: %	& \emph{Rückgabewert ist true}.\\
sawine@1: %7	& Der Rückgabewert aus 6 propagiert zurück zur Wurzel.\\ 
sawine@1: %8	& Zum Auswerten des Wurzelausdrucks \emph{true $\wedge$ ?} ist \\
sawine@1: %	& die Auswertung des rechten Terms nötig.\\
sawine@1: %9	& Das \emph{Aerodrome of Departure}-Attribut wird aus dem\\
sawine@1: %	& Flugplan extrahiert und zurückgegeben. \emph{Wert: OMDB}.\\ 
sawine@1: %10	& Der Wert der Konstante wird zurückgegeben. \emph{Wert: OMDB}\\ 
sawine@1: %11	& Der Operator führt den Äquivalenzvergleich \emph{OMDB $=$ OMDB}\\
sawine@1: %	& aus mit dem \emph{Ergebnis true}.\\
sawine@1: %12	& Das Ergebnis des Äquivalenzvergleichs wird zurück propagiert.\\
sawine@1: %13	& Der Operator evaluiert den Booleschen Ausdruck\\
sawine@1: %	& \emph{true $\wedge$ true} mit dem \emph{Ergebnis true} aus.\\
sawine@1: %	& Die Auswertung terminiert, der \texttt{evaluate}-Methodenaufruf\\
sawine@1: %	& gibt \emph{true} zurück.\\
sawine@1: %\bottomrule
sawine@1: %\end{tabular}
sawine@1: %\caption{Schrittabfolge des ATCCL Pattern-Evaluation-Beispiel 1.}
sawine@1: %\label{tab:pattern_evaluation1}
sawine@1: %\end{center}
sawine@1: %\end{table}
sawine@1: 
sawine@1: \subsection{Optimierung der Abflugzeit}
sawine@1: \label{design:atot_calculation}
sawine@1: In den folgenden Gleichungen werden Vergleichsrelationen auf Uhrzeiten angewandt, hierbei gilt stets: datiert ein Zeitpunkt $t1$ einen \emph{späteren} Zeitpunkt, unabhängig von der Tageszeit, als ein Zeitpunkt $t2$, so gilt: 
sawine@1: \[
sawine@1: t1 > t2
sawine@1: \]
sawine@1: Anders formuliert liegt $t1$ zum Zeitpunkt $t2$ in der Zukunft.\\\\
sawine@1: Die Optimierung der Abflugzeit bedeutet eine konfliktfreie Slot-Zuordnung an allen betreffenden Flow Points.\\
sawine@1: Sei $f$ ein Flow Point und $M$ die Menge aller Slot-Zeiten von $f$. Eine Slot-Zeit $t$ ist konfliktfrei für Separationszeit $s$, wenn gilt:
sawine@1: \[
sawine@1: \forall m \in M: |t - m| \geq s
sawine@1: \]
sawine@1: Wird die Optimierung angestoßen, findet die virtuelle Maschine die früheste Abflugzeit, sodass im nachfolgendem Routenverlauf kein Separationsregelverstoß auftritt.\\\\
sawine@1: Sei $K$ die Menge aller Abflugzeitenkandidaten. Eine Abflugzeit $d$ ist optimal für die früheste Abflugzeit $e$, wenn gilt:
sawine@1: \[
sawine@7: d = \min\{k \in K | k \geq e\}
sawine@1: \]
sawine@1: Dabei ist ein Abflugzeitenkandidat eine Abflugzeit, durch die nur konfliktfreie Slot-Zeiten auf den Wegpunkten der Route folgen.\\\\
sawine@7: Zur Realisierung dieser Optimierung wurden verschiedene Entwürfe in Betracht gezogen, wobei eine kundenspezifische Beschränkung von einem Flow Point pro Flugplan gesetzt wurde. Der Entwurf sollte eine möglichst einfache und dadurch robuste Implementierung ermöglichen. Der Algorithmus wurde hierfür in möglichst kleinen Teilschritten mit niedriger Komplexität modelliert.
sawine@1: 
sawine@1: \subsubsection{Algorithmus}
sawine@10: Zur Bestimmung der optimalen Abflugzeiten in Abhängigkeit der geltenden Luftraumbeschränkungen und der frühest möglichen Abflugzeit, wurde ein Algorithmus entwickelt.
sawine@10: 
sawine@10: Vor der Initiierung der Berechnung wird der DFLOW-Komponente die früheste Abflugzeit über"-geben. Der Flugplan des betreffenden Fluges und alle weiteren Flugpläne, die den gleichen Flow Point teilen, werden bereitgestellt. Die Route des Flugplans muss vor der Kalkulation durch die SID-Wegpunkt vervollständigt worden sein.\\\\
sawine@10: Basierend auf der gesetzten frühesten Abflugzeit werden mit Hilfe von \texttt{CalcEstimates} die Überflugzeiten bestimmt, insbesondere auch die Überflugzeit des Wegpunkts an dem die Separation stattfinden soll, hier mit $flowtime$ referenziert. $flowtimes$ ist die Menge aller Wegpunktzeiten der anderen Flüge, die den Flow Point teilen. $separation$ hält den definierten Mindestseparationsabstand. Alle Zeiten sind fortlaufende natürliche Zahlen, wie z.B.  durch die \emph{POSIX Time}\footnote{Zeitangabe basierend auf der Anzahl an vergangenen Sekunden seit 1. Januar 1970 0:00 Uhr UTC -- UTC steht für Universal Time Coordinated und stellt die heute gültige Weltzeit dar}-Konvention gegeben.\\\\
sawine@10: Algorithmus 1 beschreibt die Bestimmung der konfliktfreien Flow Point-Zeit.
sawine@1: \begin{algorithm}
sawine@1: \floatname{algorithm}{Algorithmus}
sawine@1: \caption{$resolve(separation, flowtime, flowtimes) \rightarrow flowtime$}
sawine@1: \begin{algorithmic}
sawine@1: \STATE $t_s \gets separation$
sawine@1: \STATE $t_a \gets flowtime$
sawine@1: \STATE $t_b \gets invalid$
sawine@1: \WHILE{$t_a \neq t_b$}	
sawine@1: 	\STATE $t_b \gets t_a$ 
sawine@1: 	\FORALL{$t_f \in flowtimes$}
sawine@1: 		\STATE $t_d \gets (t_a - t_f)$
sawine@1: 		\IF{$|t_d| < t_s$}
sawine@1: 			\STATE $t_a \gets (t_a + t_s - t_d)$
sawine@1: 		\ENDIF
sawine@1: 	\ENDFOR
sawine@1: \ENDWHILE
sawine@1: \RETURN $t_a$
sawine@1: \end{algorithmic}
sawine@1: \end{algorithm}\\
sawine@10: Nach der Terminierung wird die erhaltene Flow Point-Zeit zurück propagiert, um daraus die optimale Abflugzeit zu erhalten. Der Algorithmus ist auf die eindeutige Zuweisung von maximal einem Flow Point pro Flugplan beschränkt. Sollen mehrere Flow Points pro Flugplan erlaubt sein, so gilt es den gleichen Algorithmus iterativ auf die Menge aller gemeinsamen Flow Points anzuwenden.\\\\
sawine@10: Algorithmus 2 ist ein Vorschlag, wie der Algorithmus 1 erweitert werden kann, um mehrere Flow Points pro Flugplan zu erlauben. $atot$ steht für die optimierte Abflugzeit, $flightplan$ ist ein Objekt mit den Eigenschaften früheste Abflugzeit ($etot$) und den zugeordneten Flow Points ($flowpoints$). Das Flow Point-Objekt hält Informationen zu der Flow Point-Überflugzeit ($flowtime$) und der definierten Separation ($separation$). Die Beschreibung soll nur die Idee des tatsächlichen Algorithmus erfassen, zur Vereinfachung wurde u.a. auf die Berücksichtigung der Tageszeit und die Höhenstaffelung verzichtet.
sawine@1: \begin{algorithm}
sawine@1: \floatname{algorithm}{Algorithmus}
sawine@1: \caption{$multresolve(flightplan, flightplans) \rightarrow atot$}
sawine@1: \begin{algorithmic}
sawine@1: \STATE $atot_a \gets flightplan.etot$
sawine@1: \STATE $atot_b \gets invalid$
sawine@1: \WHILE{$atot_a \neq atot_b$}	
sawine@1: 	\STATE $atot_b \gets atot_a$
sawine@1: 	\FORALL{$flowpoint \in flightplan.flowpoints$}
sawine@1: 		\STATE $atot_d \gets (flowpoint.flowtime - atot_b)$
sawine@1: 		\STATE $s \gets flowpoint.separation$
sawine@1: 		\STATE $f \gets flowpoint.flowtime$
sawine@1: 		\STATE $fs \gets flightplans.flowtimes(flowpoint)$
sawine@1: 		\STATE $flowpoint.flowtime \gets resolve(s, f, fs)$
sawine@1: 		\STATE $atot_b \gets flowpoint.flowtime - atot_d$
sawine@1: 	\ENDFOR
sawine@1: \ENDWHILE
sawine@1: \RETURN $atot_a$
sawine@1: \end{algorithmic}
sawine@1: \end{algorithm}
sawine@1: 
sawine@1: \subsubsection{Komplexität}
sawine@1: Die Entscheidung fiel auf ein iteratives Vorgehen, wobei pro Iteration alle beteiligten Flugpläne sequenziell zur Konfliktauflösung in Betracht gezogen werden. Eine Iteration besteht aus $n$ Schritten, wobei $n$ gleich der Anzahl der Flugpläne ist, welche die selben Flow Points belegen, die auch für den zu optimierenden Flugplan gelten. Schrittweise werden auftretende Konflikte zwischen zwei Flugplänen aufgelöst, solange die ermittelte optimale Abflugzeit am Anfang der Iteration ungleich der optimalen Abflugzeit am Ende einer Iteration ist.
sawine@1: 
sawine@10: Ist dies der Fall -- also sind die optimalen Abflugzeiten am Anfang und Ende einer Iteration identisch, so terminiert der Algorithmus und man erhält die optimale Abflugzeit. Die obere Schranke der Laufzeitkomplexität für diesen Ansatz liegt bei $\mathcal{O}(n^{2})$, wobei $n$ die Anzahl der Flugpläne ist mit mindestens einem gemeinsamen Flow Point. Bei Konfliktfreiheit oder anderen günstigen Konfliktbedingungen gleicht das asymptotische Verhalten $\Omega(n)$, da nach einer Iteration bereits die Abbruchbedingung erfüllt ist.
sawine@1: 
sawine@1: \subsubsection{Alternative}
sawine@1: Eine Alternative beinhaltet die Vorsortierung der Flugpläne nach Slot-Zeiten. Die Sortierung bereitet den Weg für eine Optimierung vor, bei der mit jedem Schritt der Suchraum halbiert werden kann. Man reduziert die betrachteten Flugpläne auf diejenigen, deren Slot-Zeiten in Konflikt oder in der Zukunft zur eigenen liegen. Das asymptotische Verhalten dieses Algorithmus liegt bei $\mathcal{O}(n^{2})$ bzw. $\Omega(n \log n)$ für das Sortieren unter Einsatz von \emph{Quicksort} und insgesamt bei $\mathcal{O}(n^2)$, da im ungünstigstem Fall $n$ Schritte notwendig sind um nach der Sortierung die optimale Zeit zu bestimmen. Im Durchschnitt läge die Komplexität bei $\Theta(n \log n)$.\\\\
sawine@1: Der alternative Ansatz bedeutet eine höhere Komplexität für die Implementierung, da zusätz"-lich das Sortieren zu realisiert ist. Standardalgorithmen wie das \texttt{std::sort} der Standardbibliothek von C++ kommen aufgrund der dynamischen Speicherallokierung nicht in Frage. Außerdem wird für den operativen Betrieb mit einem hohem Aufkommen von günstigen Bedingungen für den iterativen Algorithmus gerechnet, wodurch die Vorsortierung der Flugpläne nur eine Verschlechterung der Leistung bedeutet.
sawine@1: 
sawine@1: \subsubsection{Höhenstaffelung}
sawine@1: Eine zusätzliche Komplexität bei der Bestimmung der optimalen Abflugzeit bestand in der Separation nach Flugflächen, siehe \ref{research:flight_level_separation}. ATCCL soll, wenn definiert, auf allen freigegebenen Flugflächen eines Flow Points separieren. Dieser Art der Staffelung soll eine höhere Priorität besitzen als die Längsstaffelung, siehe \ref{research:time_separation}.\\\\
sawine@1: Zur Realisierung dieses Verhaltens wird jede freigegebene Flugfläche für einen Flow Point getrennt behandelt. Besteht auf einer Flugfläche kein Konflikt, ausgehend von der frühesten Abflugzeit, so terminiert der Vorgang frühzeitig, weil das automatisch die optimale Abflugzeit darstellt. Findet kein frühzeitiger Abbruch statt, so wird nach der Ermittlung aller optimalen Zeiten die früheste Zeit mit der entsprechenden Flugfläche für den Flug reserviert.\\\\
sawine@1: Mit der Höhenstaffelung beträgt die Laufzeitkomplexität der Optimierung $\mathcal{O}(m*n^{2}) \rightarrow \mathcal{O}(n^{3})$, wobei $n$ für die Anzahl an Flugplänen und $m$ für die Anzahl an freigegebenen Flugflächen steht. Jedoch ist die Anzahl an möglichen Flugflächen sehr begrenzt. Für einen Flow Point -- der stets nur eine Flugrichtung realisiert -- kann z.B. FL 200 bis FL 600 in Abständen von FL 20 freigegeben sein, was ein $m = 20$ ergibt und als Maximalwert gesehen werden kann.
sawine@1: 
sawine@1: \section{DFLOW}
sawine@1: Die DFLOW-Komponente soll als Teil des FDPS in die PRISMA-Architektur integriert werden. Die Komponente hat die Aufgabe, auf Anfragen zu reagieren, die Flugpläne mit Hilfe der virtuellen Maschine des ATCCL-Frameworks zu verarbeiten und die transformierten Flugpläne wieder in das System einzuspeisen. Die DFLOW-Komponente reagiert auf folgende Ereignisse:
sawine@1: \begin{itemize}
sawine@1: \item \textbf{Benutzeranfrage zur optimalen Abflugzeiten- und Flugflächenbestimmung}\\
sawine@1: Über das DFLOW-Display wird eine Anfrage zur Bestimmung der Abflugzeit erzeugt. Die Komponente registriert die Anfrage, bearbeitet sie und gibt die optimale Abflugzeit und Flugfläche in das System.
sawine@1: \item \textbf{Neuer Überflug registriert}\\
sawine@1: Wird ein noch nicht registrierter Überflug erkannt, wird dieser bearbeitet, um ihn bei folgenden Anfragen bei eventuell auftretenden Konflikten zu berücksichtigen.
sawine@1: \end{itemize}
sawine@1: Zur Realisierung dieser Logik und der Integration in PRISMA wurden u.a. PRISMA-Standard"-klassen verwendet. PRISMA folgt einem datengetriebenen Modell, die interne Daten"-über"-tragung findet über die DMAP statt.
sawine@1: 
sawine@1: \subsection{DMAP-Interaktion}
sawine@1: PRISMA definiert Schnittstellen zur DMAP mit Hilfe von einer Reihe von Klassen. Es gibt u.a. eine Klasse, die den Lese- und Schreibzugriff auf die einzelnen Datensätze der DMAP bereitstellt. Eine weitere Klasse bietet Möglichkeiten an, auf Transaktionen bestimmter Datensätze zu reagieren.
sawine@1: 
sawine@1: \subsubsection{Map}
sawine@1: Für jeden DMAP-Datensatz existiert als Schnittstelle zu den Transaktionen mit diesem Datensatz ein zugehöriges MAP-Interface. Mit Hilfe der MAP-Klasse lassen sich sog. Notify-Objekte als \emph{Observer}, siehe \cite{design_patterns},  registrieren. Weiter bietet die Klasse Zugriffs"-möglich"-keiten auf die Dateneinträge an. 
sawine@1: 
sawine@1: \subsubsection{Notify}
sawine@1: Ein Notify-Objekt realisiert die Reaktionen auf Datensatztransaktionen. Mögliche Transaktionen sind:
sawine@1: \begin{itemize}
sawine@1: \item Einfügen eines neuen Eintrags
sawine@1: \item Ändern eines vorhandenen Eintrags
sawine@1: \item Löschen eines vorhandenen Eintrags
sawine@1: \end{itemize}  
sawine@1: Die Basis der Logik der datenverarbeitenden Module des PRISMA und insbesondere des FDPS basiert auf Notify-Objekten. Gänzlich entkoppelt von der Verarbeitungsoperationen der parallel laufenden Prozessen, wird mit dieser Architektur eine modulare und stabile Grundlagen für ein sicherheitskritischen System bereitgestellt.\\\\
sawine@1: Das DFLOW braucht zur Realisierung der Logik Zugriff auf folgende DMAP-Datensätze:
sawine@1: \begin{itemize}
sawine@1: \item \textbf{DFLOW}\\
sawine@8: Dieser Datensatz beinhaltet die DFLOW-spezifischen Einträge. Dazu gehört der sog. \emph{Slot State} -- der aktuelle Verarbeitungszustand des Eintrags. Weiterhin hält der Eintrag Daten über die Startbahn und die geltenden Flow Points. Als Zeiten sind der Zeitpunkt der Anfrage und die früheste und zugewiesene Abflugzeit Bestandteil eines Eintrags. Die DFLOW-Erweiterung der DMAP-Datensätze wurden zum Zeitpunkt der Entwicklung bereitgestellt.
sawine@1: \item \textbf{FPATH}\\
sawine@8: Die \emph{Flight Path}-Datensätze halten Informationen über die Wegpunkte und deren veranschlagte Überflugzeiten. Diese Datensätze werden stets vom FDPS korrigiert, um möglichst verlässliche Prognosen über den Flugverlauf der Luftfahrzeuge zu erlauben.
sawine@1: \item \textbf{SFPL}\\
sawine@1: Alle Datensätze halten für jeden Eintrag eine Referenznummer -- die SFPI -- zum dazugehörigen \emph{System Flight Plan} -- oder auch SFPL. Dadurch wird die Verbindung zwischen weiterführenden Informationen zum Flugplan gemacht. Der SFPL beinhaltet alle Details eines regulären Flugplans mit einigen systemspezifischen Zusatzinformationen.
sawine@1: \end{itemize}
sawine@1: Die oben genannten Datensätze bieten alle Informationen, die eine DFLOW-Verarbeitung eines Flugplans benötigt. Die Idee ist es möglichst effiziente Entscheidungen anhand von abgefangen Transaktionen der DMAP zu treffen, um dabei die Zugriffe auf die Datensätze zu reduzieren.
sawine@1: 
sawine@1: \subsection{Verarbeitungslogik}
sawine@8: Die Aufgabe des DFLOW ist es, optimale Abflugzeiten in Abhängigkeit der betroffenen Flow Points und dem, dafür zugewiesenen, Flugverkehr zu bestimmen. Zur Bedienung der Komponente wird ein DFLOW-Display entwickelt, das nicht Bestandteil dieser Arbeit war. 
sawine@1: 
sawine@1: Das Display bietet dem Benutzer Möglichkeiten, Flugpläne zu selektieren, sie mit Zusatzinformationen wie der Startbahn und der frühesten Abflugzeit zu vervollständigen, und die Bestimmung der optimalen Abflugzeit anzufordern. Die Anfrage der optimalen Abflugzeit initiiert die Verarbeitungslogik, hierfür wird dem erzeugten DFLOW-Eintrag ein \texttt{REQUEST}-Flag gesetzt.
sawine@1: 
sawine@1: \begin{enumerate}
sawine@1: \item \textbf{Ergänzung: SID-Wegpunkte}\\
sawine@1: Bevor die eigentliche Berechnung beginnen kann, müssen alle notwendigen Informationen bereitgestellt werden. Der erste Schritt ist die Ergänzung der Route um die SID-Wegpunkte, siehe \ref{grundlagen:routensystem}. Für alle internationalen Flughäfen gibt es fest definierte Routen, die in Abhängigkeit der Startbahn eine Verbindung zwischen den Startvektor und der Reiseroute herstellt.
sawine@1: 
sawine@8: Im Fall DFLOW ist die vollständige Route essentiell für die Genauigkeit der Zeitenprognosen und somit ausschlaggebend für die Qualität der Optimierung.
sawine@1: 
sawine@1: \item \textbf{Bestimmung: Flow Points}\\
sawine@1: Sobald die Vervollständigung der Route abgeschlossen ist, findet die erste Interaktion mit der virtuellen Maschine des ATCCL-Frameworks statt. Die virtuelle Maschine wird mit der Ermittlung aller Flow Points beauftragt, die für den betreffenden Flugplan gelten. Dazu gilt es, den Flugplan durch die Flugplanmuster der Flow Points zu evaluieren. Details dazu sind in Abschnitt \ref{design:pattern_evaluation} zu finden.
sawine@1: 
sawine@1: \item \textbf{Laden: Flugpläne}\\
sawine@1: Sobald alle Flow Points bekannt sind, werden alle Einträge im DFLOW-Datensatz geladen, die den gleichen Flow Points zugewiesen sind. Bei Flow Point-Überschneidungen kann es zu Kollisionen in der Zeit-Slot-Vergabe führen, somit müssen alle betroffenen Flugpläne bei der Vergabe der Abflugzeit berücksichtigt werden.
sawine@1: 
sawine@1: \item \textbf{Berechnung: Wegpunktzeiten}\\
sawine@8: Mit Hilfe der PRISMA-Klasse \texttt{CalcEstimates} lassen sich die Wegpunktzeiten der Route bestimmen. Ausgangspunkt der Rechnung ist die \emph{Estimated Entry Time} -- oder ETN -- die wir mit der frühesten Abflugzeit belegen. Die Berechnung der Zeiten ist für die Konfliktauflösung der Flow Point Slot-Zeiten notwendig.
sawine@1: 
sawine@1: \item \textbf{Berechnung: optimale Abflugzeit}\\
sawine@8: Die Vorbereitungsphase ist abgeschlossen und die Berechnung der optimalen Abflugzeit wird eingeleitet. Die Kalkulation wird von der virtuellen Maschine geleistet. Die Eingabeparameter bestehen aus dem Flugplan, der zur Bearbeitung steht und den Flugplänen mit den gleichen zugewiesenen Flow Points. Der Optimierungsalgorithmus ist in \ref{design:atot_calculation} beschrieben. In diesem Schritt ist ebenfalls die Höhenstaffelung realisiert.
sawine@1: \end{enumerate}
sawine@1: Nach Abfolge der Verarbeitungsschritte sind die Flow Points und Flugflächen zugewiesen, die optimale Abflugzeit bestimmt und die resultierende Flow Point-Überflugzeit ermittelt. Die gewonnen Informationen werden durch eine Transaktion an den DMAP-Datensatz übermittelt. Mit der Über"-mittlung beendet die Verarbeitung des DFLOW, für die Visualisierung der DFLOW-spezifischen Daten ist das DFLOW-Display zuständig. Zur Verifizierung der Verarbeitungsterminierung wird dem Eintrag das \texttt{PROPOSAL}-Flag gesetzt.\\\\
sawine@1: Eine automatisierte Vergabe von Abflugzeiten ist stets nur ein Vorschlag, welcher vom Benutzer überstimmt werden kann. Dies stellt eine wichtige Anforderungen an das System dar. Eine voll automatisierte Verarbeitung bietet nicht die Flexibilität, die in einem Umfeld wie der Flugsicherung zu einem reibungsfreien und effektiven Betrieb notwendig ist. Treten Ausnahmesituationen ein, oder wird die Qualität der Automatisierung durch andere Faktoren gestört, so muss es möglich sein, den Flugverkehr ordnungsgemäß in manueller Steuerung abzuhalten. Ist die manuelle Steuerung unmöglich, so kann das zu einer Beeinträchtigung der Flugsicherung und damit der Sicherheit oder Effektivität führen, was letztendlich mit der Abschaltung des Systems enden kann, \cite{flugleiter_dman}.
sawine@1: %\begin{figure}[h]
sawine@1: %\centering \includegraphics[width=450pt]{images/dflow_cln_tables.png}
sawine@1: %\caption{DFLOW DMAP-Client-Tables}
sawine@1: %\label{uml:dflow_cln_tables}
sawine@1: %\end{figure}
sawine@1: 
sawine@1: \subsection{Protokollierung}
sawine@8: DFLOW bedient sich der DMAP, welche alle Transaktionen protokolliert. Diese Zustand erleichtert die Nachvollziehbarkeit der Entscheidungen, die von der DFLOW-Komponente automatisch oder manuell gemacht werden. Zur Ergänzung der statistischen Auswertemöglichkeiten des FDPS, sollen zusätzlich DFLOW-spezifische persistente Logdateien erzeugt werden. Ein Logeintrag soll einen Starter mit relevanten Zusatzinformationen wie dessen Rufzeichen, zugewiesene Flow Points und den Zeiten protokollieren.\\\\
sawine@1: Um eine automatisierte Auswertung solcher Protokolle zu erleichtern, wird für die DFLOW-Protokolle ein CSV-Datenformat verwendet. Ein Protokolleintrag hat folgende Datenfelder:
sawine@1: \begin{itemize}
sawine@1: \item \emph{Call Sign:} das Rufzeichen des Luftfahrzeugs
sawine@1: \item \emph{ADEP:} die ICAO-Kennung des Startflughafens
sawine@1: \item \emph{RWY:} die Kennung der Startbahn
sawine@1: \item \emph{ADES:} die ICAO-Kennung des Zielflughafens
sawine@1: \item \emph{ETOT:} die früheste Abflugzeit -- vom Planer gesetzt
sawine@1: \item \emph{ATOT:} die optimierte Abflugzeit -- von DFLOW berechnet
sawine@1: \item \emph{Flow Point:} der von DFLOW zugewiesene Flow Point
sawine@1: \item \emph{Flow Time:} die Prognose der Überflugzeit über den Wegpunkt des Flow Points
sawine@1: \item \emph{Flow Flight Level:} die von DFLOW zugewiesene Flugfläche
sawine@1: \item \emph{ATD:} die tatsächliche Abflugzeit -- von PRISMA automatisch erfasst
sawine@1: \end{itemize}




