Ad-Hoc-Netze sind selbstorganisierende Netze ohne zentrale Infrastruktur, die heutzutage in vielen Bereichen Verwendung finden. Sie bestehen aus drahtlosen Knoten, die zur Erfüllung ihrer Aufgaben miteinander kommunizieren. Jedoch befinden sich nicht notwendigerweise alle Knoten in Reichweite zueinander. Damit entfernte Knoten einander erreichen können, werden Routingverfahren benötigt. Die Etablierung einer beliebigen Route ist jedoch oft nicht ausreichend, denn viele Anwendungen stellen spezielle Dienstgüteanforderungen (QoS-Anforderungen) an die Verbindung, beispielsweise die Gewährleistung einer Mindestbandbreite. Um diese QoS-Anforderungen erfüllen zu können, werden sie bereits bei der Ermittlung einer Route berücksichtigt, und die benötigten Ressourcen werden entlang der Route reserviert. Dazu dienen QoS-Routing- und Reservierungsprotokolle.
In dieser Arbeit wird zunächst der Aspekt der deterministischen Reservierung von Bandbreite in Form von konkreten Zeitslots einer TDMA-basierten MAC-Schicht betrachtet. Da sich die Übertragungen verschiedener Knoten in drahtlosen Netzen gegenseitig stören können, wurde ein Interferenzmodell entwickelt. Dieses identifiziert Bedingungen, unter denen Zeitslots innerhalb eines Netzes für mehr als eine Übertragung verwendet werden können. Zudem definiert es durch Aggregation der Informationen anderer Knoten Möglichkeiten zur Ermittlung der benötigten Informationen, um zu entscheiden, welche Zeitslots für eine störungsfreie Übertragung verwendet werden können.
Weiterhin werden existierende QoS-Routing- und Reservierungsprotokolle auf inhärente Probleme untersucht, wobei der Schwerpunkt auf Protokollen liegt, die deterministische Reservierungen von Zeitslots vornehmen. In diese Kategorie fällt auch das im Rahmen der Arbeit entwickelte Protokoll RBBQR, dessen Hauptziel darin besteht, die identifizierten Probleme zu eliminieren. Ferner wird das ebenfalls zu dieser Kategorie gehörende Protokoll QMRP beschrieben, welches zentralisiert Multicast-Routen inklusive der zugehörigen Reservierungen in teilstationären Netzen ermittelt.
Ein weiterer Bestandteil der Arbeit behandelt die Entwicklung von Simulationskomponenten, welche beispielsweise zur Evaluation von QoS-Routing- und Reservierungsprotokollen genutzt werden können. Das existierende Simulationsframework FERAL wurde um eine Komponente erweitert, die die Verwendung von Kommunikationstechnologien des Netzwerksimulators ns-3 ermöglicht. Weiterhin wurde ein Modul zur Simulation eines CC2420-Transceivers entwickelt, welches in eigenständigen ns-3-Simulationen und in Simulationen mit FERAL verwendet werden kann.
Typically software engineers implement their software according to the design of the software
structure. Relations between classes and interfaces such as method-call relations and inheritance
relations are essential parts of a software structure. Accordingly, analyzing several types of
relations will benefit the static analysis process of the software structure. The tasks of this
analysis include but not limited to: understanding of (legacy) software, checking guidelines,
improving product lines, finding structure, or re-engineering of existing software. Graphs with
multi-type edges are possible representation for these relations considering them as edges, while
nodes represent classes and interfaces of software. Then, this multiple type edges graph can
be mapped to visualizations. However, the visualizations should deal with the multiplicity of
relations types and scalability, and they should enable the software engineers to recognize visual
patterns at the same time.
To advance the usage of visualizations for analyzing the static structure of software systems,
I tracked difierent development phases of the interactive multi-matrix visualization (IMMV)
showing an extended user study at the end. Visual structures were determined and classified
systematically using IMMV compared to PNLV in the extended user study as four categories:
High degree, Within-package edges, Cross-package edges, No edges. In addition to these structures
that were found in these handy tools, other structures that look interesting for software
engineers such as cycles and hierarchical structures need additional visualizations to display
them and to investigate them. Therefore, an extended approach for graph layout was presented
that improves the quality of the decomposition and the drawing of directed graphs
according to their topology based on rigorous definitions. The extension involves describing
and analyzing the algorithms for decomposition and drawing in detail giving polynomial time
complexity and space complexity. Finally, I handled visualizing graphs with multi-type edges
using small-multiples, where each tile is dedicated to one edge-type utilizing the topological
graph layout to highlight non-trivial cycles, trees, and DAGs for showing and analyzing the
static structure of software. Finally, I applied this approach to four software systems to show
In der aktuellen technologischen Entwicklung spielen verteilte eingebettete Echtzeitsysteme eine immer zentralere Rolle und werden zunehmend zum Träger von Innovationen. Durch den hiermit verbundenen steigenden Funktionsumfang der verteilten Echtzeitsysteme und deren zunehmenden Einsatz in sicherheitsrelevanten Anwendungsgebieten stellt die Entwicklung solcher Systeme eine immer größere Herausforderung dar. Hierbei handelt es sich einerseits um Herausforderungen bezogen auf die Kommunikation hinsichtlich Echtzeitfähigkeit und effizienter Bandbreitennutzung, andererseits werden geeignete Methoden benötigt, um den Entwicklungsprozess solcher komplexen Systeme durch Tests und Evaluationen zu unterstützen und zu begleiten. Die hier vorgestellte Arbeit adressiert diese beiden Aspekte und ist entsprechend in zwei Teile untergliedert.
Der erste Teil der Arbeit beschäftigt sich mit der Entwicklung neuer Kommunikationslösungen, um den gestiegenen Kommunikationsanforderungen begegnen zu können. So erfordert die Nutzung verteilter Echtzeitsysteme im Kontext sicherheitsrelevanter Aufgaben den Einsatz zeitgetriggerter Kommunikationssysteme, die in der Lage sind, deterministische Garantien bezüglich der Echtzeitfähigkeit zu gewähren. Diese klassischen auf exklusiven Reservierungen basierenden Ansätze sind jedoch gerade bei (seltenen) sporadischen Nachrichten sehr ineffizient in Bezug auf die Nutzung der Bandbreite.
Das in dieser Arbeit verwendete Mode-Based Scheduling with Fast Mode-Signaling (modusbasierte Kommunikation) ist ein Verfahren zur Verbesserung der Bandbreitennutzung zeitgetriggerter Kommunikation, bei gleichzeitiger Gewährleistung der Echtzeitfähigkeit. Um dies zu ermöglichen, erlaubt Mode-Based Scheduling einen kontrollierten, slotbasierten Wettbewerb, welcher durch eine schnelle Modussignalisierung (Fast Mode-Signaling) aufgelöst wird. Im Zuge dieser Arbeit werden verschiedene robuste, zuverlässige und vor allem deterministische Realisierungen von Mode-Based Scheduling with Fast Mode-Signaling auf Basis existierender drahtgebundener Kommunikationsprotokolle (TTCAN und FlexRay) vorgestellt sowie Konzepte präsentiert, welche eine einfache Integration in weitere Kommunikationstechnologien (wie drahtlose Ad-Hoc-Netze) ermöglichen.
Der zweite Teil der Arbeit konzentriert sich nicht nur auf Kommunikationsaspekte, sondern stellt einen Ansatz vor, den Entwicklungsprozess verteilter eingebetteter Echtzeitsysteme durch kontinuierliche Tests und Evaluationen in allen Entwicklungsphasen zu unterstützen und zu begleiten. Das im Kontext des Innovationszentrums für Applied Systems Modeling mitentwickelte und erweiterte FERAL (ein Framework für die Kopplung spezialisierter Simulatoren) bietet eine ideale Ausgangsbasis für das Virtual Prototyping komplexer verteilter eingebetteter Echtzeitsysteme und ermöglicht Tests und Evaluationen der Systeme in einer realistisch simulierten Umgebung. Die entwickelten Simulatoren für aktuelle Kommunikationstechnologien ermöglichen hierbei realistische Simulationen der Interaktionen innerhalb des verteilten Systems. Durch die Unterstützung von Simulationssystemen mit Komponenten auf unterschiedlichen Abstraktionsstufen kann FERAL in allen Entwicklungsphasen eingesetzt werden. Anhand einer Fallstudie wird gezeigt, wie FERAL verwendet werden kann, um ein Simulationssystem zusammen mit den zu realisierenden Komponenten schrittweise zu verfeinern. Auf diese Weise steht während jeder Entwicklungsphase ein ausführbares Simulationssystem für Tests zur Verfügung. Die entwickelten Konzepte und Simulatoren für FERAL ermöglichen es, Designalternativen zu evaluieren und die Wahl einer Kommunikationstechnologie durch die Ergebnisse von Simulationen zu stützen.
Most of today’s wireless communication devices operate on unlicensed bands with uncoordinated spectrum access, with the consequence that RF interference and collisions are impairing the overall performance of wireless networks. In the classical design of network protocols, both packets in a collision are considered lost, such that channel access mechanisms attempt to avoid collisions proactively. However, with the current proliferation of wireless applications, e.g., WLANs, car-to-car networks, or the Internet of Things, this conservative approach is increasingly limiting the achievable network performance in practice. Instead of shunning interference, this thesis questions the notion of „harmful“ interference and argues that interference can, when generated in a controlled manner, be used to increase the performance and security of wireless systems. Using results from information theory and communications engineering, we identify the causes for reception or loss of packets and apply these insights to design system architectures that benefit from interference. Because the effect of signal propagation and channel fading, receiver design and implementation, and higher layer interactions on reception performance is complex and hard to reproduce by simulations, we design and implement an experimental platform for controlled interference generation to strengthen our theoretical findings with experimental results. Following this philosophy, we introduce and evaluate a system architecture that leverage interference.
First, we identify the conditions for successful reception of concurrent transmissions in wireless networks. We focus on the inherent ability of angular modulation receivers to reject interference when the power difference of the colliding signals is sufficiently large, the so-called capture effect. Because signal power fades over distance, the capture effect enables two or more sender–receiver pairs to transmit concurrently if they are positioned appropriately, in turn boosting network performance. Second, we show how to increase the security of wireless networks with a centralized network access control system (called WiFire) that selectively interferes with packets that violate a local security policy, thus effectively protecting legitimate devices from receiving such packets. WiFire’s working principle is as follows: a small number of specialized infrastructure devices, the guardians, are distributed alongside a network and continuously monitor all packet transmissions in the proximity, demodulating them iteratively. This enables the guardians to access the packet’s content before the packet fully arrives at the receiver. Using this knowledge the guardians classify the packet according to a programmable security policy. If a packet is deemed malicious, e.g., because its header fields indicate an unknown client, one or more guardians emit a limited burst of interference targeting the end of the packet, with the objective to introduce bit errors into it. Established communication standards use frame check sequences to ensure that packets are received correctly; WiFire leverages this built-in behavior to prevent a receiver from processing a harmful packet at all. This paradigm of „over-the-air“ protection without requiring any prior modification of client devices enables novel security services such as the protection of devices that cannot defend themselves because their performance limitations prohibit the use of complex cryptographic protocols, or of devices that cannot be altered after deployment.
This thesis makes several contributions. We introduce the first software-defined radio based experimental platform that is able to generate selective interference with the timing precision needed to evaluate the novel architectures developed in this thesis. It implements a real-time receiver for IEEE 802.15.4, giving it the ability to react to packets in a channel-aware way. Extending this system design and implementation, we introduce a security architecture that enables a remote protection of wireless clients, the wireless firewall. We augment our system with a rule checker (similar in design to Netfilter) to enable rule-based selective interference. We analyze the security properties of this architecture using physical layer modeling and validate our analysis with experiments in diverse environmental settings. Finally, we perform an analysis of concurrent transmissions. We introduce a new model that captures the physical properties correctly and show its validity with experiments, improving the state of the art in the design and analysis of cross-layer protocols for wireless networks.
Computer Vision (CV) problems, such as image classification and segmentation, have traditionally been solved by manual construction of feature hierarchies or incorporation of other prior knowledge. However, noisy images, varying viewpoints and lighting conditions of images, and clutters in real-world images make the problem challenging. Such tasks cannot be efficiently solved without learning from data. Therefore, many Deep Learning (DL) approaches have recently been successful for various CV tasks, for instance, image classification, object recognition and detection, action recognition, video classification, and scene labeling. The main focus of this thesis is to investigate a purely learning-based approach, particularly, Multi-Dimensional LSTM (MD-LSTM) recurrent neural networks to tackle the challenging CV tasks, classification and segmentation on 2D and 3D image data. Due to the structural nature of MD-LSTM, the network learns directly from raw pixel values and takes the complex spatial dependencies of each pixel into account. This thesis provides several key contributions in the field of CV and DL.
Several MD-LSTM network architectural options are suggested based on the type of input and output, as well as the requiring tasks. Including the main layers, which are an input layer, a hidden layer, and an output layer, several additional layers can be added such as a collapse layer and a fully connected layer. First, a single Two Dimensional LSTM (2D-LSTM) is directly applied on texture images for segmentation and show improvement over other texture segmentation methods. Besides, a 2D-LSTM layer with a collapse layer is applied for image classification on texture and scene images and have provided an accurate classification results. In addition, a deeper model with a fully connected layer is introduced to deal with more complex images for scene labeling and outperforms the other state-of-the-art methods including the deep Convolutional Neural Networks (CNN). Here, several input and output representation techniques are introduced to achieve the robust classification. Randomly sampled windows as input are transformed in scaling and rotation, which are integrated to get the final classification. To achieve multi-class image classification on scene images, several pruning techniques are introduced. This framework provides a good results in automatic web-image tagging. The next contribution is an investigation of 3D data with MD-LSTM. The traditional cuboid order of computations in Multi-Dimensional LSTM (MD-LSTM) is re-arranged in pyramidal fashion. The resulting Pyramidal Multi-Dimensional LSTM (PyraMiD-LSTM) is easy to parallelize, especially for 3D data such as stacks of brain slice images. PyraMiD-LSTM was tested on 3D biomedical volumetric images and achieved best known pixel-wise brain image segmentation results and competitive results on Electron Microscopy (EM) data for membrane segmentation.
To validate the framework, several challenging databases for classification and segmentation are proposed to overcome the limitations of current databases. First, scene images are randomly collected from the web and used for scene understanding, i.e., the web-scene image dataset for multi-class image classification. To achieve multi-class image classification, the training and testing images are generated in a different setting. For training, images belong to a single pre-defined category which are trained as a regular single-class image classification. However, for testing, images containing multi-classes are randomly collected by web-image search engine by querying the categories. All scene images include noise, background clutter, unrelated contents, and also diverse in quality and resolution. This setting can make the database possible to evaluate for real-world applications. Secondly, an automated blob-mosaics texture dataset generator is introduced for segmentation. Random 2D Gaussian blobs are generated and filled with random material textures. These textures contain diverse changes in illumination, scale, rotation, and viewpoint. The generated images are very challenging since they are even visually hard to separate the related regions.
Overall, the contributions in this thesis are major advancements in the direction of solving image analysis problems with Long Short-Term Memory (LSTM) without the need of any extra processing or manually designed steps. We aim at improving the presented framework to achieve the ultimate goal of accurate fine-grained image analysis and human-like understanding of images by machines.
The task of printed Optical Character Recognition (OCR), though considered ``solved'' by many, still poses several challenges. The complex grapheme structure of many scripts, such as Devanagari and Urdu Nastaleeq, greatly lowers the performance of state-of-the-art OCR systems.
Moreover, the digitization of historical and multilingual documents still require much probing. Lack of benchmark datasets further complicates the development of reliable OCR systems. This thesis aims to find the answers to some of these challenges using contemporary machine learning technologies. Specifically, the Long Short-Term Memory (LSTM) networks, have been employed to OCR modern as well historical monolingual documents. The excellent OCR results obtained on these have led us to extend their application for multilingual documents.
The first major contribution of this thesis is to demonstrate the usability of LSTM networks for monolingual documents. The LSTM networks yield very good OCR results on various modern and historical scripts, without using sophisticated features and post-processing techniques. The set of modern scripts include modern English, Urdu Nastaleeq and Devanagari. To address the challenge of OCR of historical documents, this thesis focuses on Old German Fraktur script, medieval Latin script of the 15th century, and Polytonic Greek script. LSTM-based systems outperform the contemporary OCR systems on all of these scripts. To cater for the lack of ground-truth data, this thesis proposes a new methodology, combining segmentation-based and segmentation-free OCR approaches, to OCR scripts for which no transcribed training data is available.
Another major contribution of this thesis is the development of a novel multilingual OCR system. A unified framework for dealing with different types of multilingual documents has been proposed. The core motivation behind this generalized framework is the human reading ability to process multilingual documents, where no script identification takes place.
In this design, the LSTM networks recognize multiple scripts simultaneously without the need to identify different scripts. The first step in building this framework is the realization of a language-independent OCR system which recognizes multilingual text in a single step. This language-independent approach is then extended to script-independent OCR that can recognize multiscript documents using a single OCR model. The proposed generalized approach yields low error rate (1.2%) on a test corpus of English-Greek bilingual documents.
In summary, this thesis aims to extend the research in document recognition, from modern Latin scripts to Old Latin, to Greek and to other ``under-privilaged'' scripts such as Devanagari and Urdu Nastaleeq.
It also attempts to add a different perspective in dealing with multilingual documents.
Asynchronous programs are challenging to implement correctly: the loose coupling between asynchronously executed tasks makes the control and data dependencies difficult to follow. Even subtle design and programming mistakes on the programs have the capability to introduce erroneous or divergent behaviors. As asynchronous programs are typically written to provide a reliable, high-performance infrastructure, there is a critical need for analysis techniques to guarantee their correctness.
In this dissertation, I provide scalable verification and testing tools to make asyn- chronous programs more reliable. I show that the combination of counter abstraction and partial order reduction is an effective approach for the verification of asynchronous systems by presenting PROVKEEPER and KUAI, two scalable verifiers for two types of asynchronous systems. I also provide a theoretical result that proves a counter-abstraction based algorithm called expand-enlarge-check, is an asymptotically optimal algorithm for the coverability problem of branching vector addition systems as which many asynchronous programs can be modeled. In addition, I present BBS and LLSPLAT, two testing tools for asynchronous programs that efficiently uncover many subtle memory violation bugs.
Today, many publishers (e.g., websites, mobile application developers) commonly use third-party analytics services and social widgets. Unfortunately, this scheme allows these third parties to track individual users across the web, creating privacy concerns and leading to reactions to prevent tracking via blocking, legislation and standards. While improving user privacy, these efforts do not consider the functionality third-party tracking enables publishers to use: to obtain aggregate statistics about their users and increase their exposure to other users via online social networks. Simply preventing third-party tracking without replacing the functionality it provides cannot be a viable solution; leaving publishers without essential services will hurt the sustainability of the entire ecosystem.
Automata theory has given rise to a variety of automata models that consist
of a finite-state control and an infinite-state storage mechanism. The aim
of this work is to provide insights into how the structure of the storage
mechanism influences the expressiveness and the analyzability of the
resulting model. To this end, it presents generalizations of results about
individual storage mechanisms to larger classes. These generalizations
characterize those storage mechanisms for which the given result remains
true and for which it fails.
In order to speak of classes of storage mechanisms, we need an overarching
framework that accommodates each of the concrete storage mechanisms we wish
to address. Such a framework is provided by the model of valence automata,
in which the storage mechanism is represented by a monoid. Since the monoid
serves as a parameter to specifying the storage mechanism, our aim
translates into the question: For which monoids does the given
(automata-theoretic) result hold?
As a first result, we present an algebraic characterization of those monoids
over which valence automata accept only regular languages. In addition, it
turns out that for each monoid, this is the case if and only if valence
grammars, an analogous grammar model, can generate only context-free
Furthermore, we are concerned with closure properties: We study which
monoids result in a Boolean closed language class. For every language class
that is closed under rational transductions (in particular, those induced by
valence automata), we show: If the class is Boolean closed and contains any
non-regular language, then it already includes the whole arithmetical
This work also introduces the class of graph monoids, which are defined by
finite graphs. By choosing appropriate graphs, one can realize a number of
prominent storage mechanisms, but also combinations and variants thereof.
Examples are pushdowns, counters, and Turing tapes. We can therefore relate
the structure of the graphs to computational properties of the resulting
In the case of graph monoids, we study (i) the decidability of the emptiness
problem, (ii) which storage mechanisms guarantee semilinear Parikh images,
(iii) when silent transitions (i.e. those that read no input) can be
avoided, and (iv) which storage mechanisms permit the computation of
In this thesis we developed a desynchronization design flow in the goal of easing the de- velopment effort of distributed embedded systems. The starting point of this design flow is a network of synchronous components. By transforming this synchronous network into a dataflow process network (DPN), we ensures important properties that are difficult or theoretically impossible to analyze directly on DPNs are preserved by construction. In particular, both deadlock-freeness and buffer boundedness can be preserved after desyn- chronization. For the correctness of desynchronization, we developed a criteria consisting of two properties: a global property that demands the correctness of the synchronous network, as well as a local property that requires the latency-insensitivity of each local synchronous component. As the global property is also a correctness requirement of synchronous systems in general, we take this property as an assumption of our desyn- chronization. However, the local property is in general not satisfied by all synchronous components, and therefore needs to be verified before desynchronization. In this thesis we developed a novel technique for the verification of the local property that can be carried out very efficiently. Finally we developed a model transformation method that translates a set of synchronous guarded actions – an intermediate format for synchronous systems – to an asynchronous actor description language (CAL). Our theorem ensures that one passed the correctness verification, the generated DPN of asynchronous pro- cesses (or actors) preserves the functional behavior of the original synchronous network. Moreover, by the correctness of the synchronous network, our theorem guarantees that the derived DPN is deadlock-free and can be implemented with only finitely bounded buffers.