Connectivity Prediction in Mobile Ad Hoc Networks for Real-Time Control E-Book

Sebastian Thelen

• Herausgeber: Books on Demand
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch
• Veröffentlichungsjahr: 2015

Seitenzahl: 304

Beschreibung

Cyber-physical systems are the next step in realizing the centuries old ubiquitous computing idea by focusing on open real-time systems design and device connectivity. Mobile ad hoc networks offer the flexible, local connectivity that cyber-physical systems require, if the connectivity can be realized dependably. One aspect of the dependability is the prediction of connectivity in the mobile ad hoc network. The presented research contributes to the connectivity prediction in mobile ad hoc networks with moving network participants in two ways: It systematically analyses the influence of scenario parameters on a set of connectivity metrics and it proposes and evaluates three classes of prediction models for these metrics.

Leseprobe

Von der Fakultät für Maschinenwesen der Rheinisch-Westfälischen Technischen Hochschule Aachen zur Erlangung des akademischen Grades eines Doktors der Ingenieurwissenschaften genehmigte Dissertation

vorgelegt von

Sebastian Thelen

Berichter: Univ.-Prof. Dr. rer. nat. Sabina Jeschke

Univ.-Prof. Dr.-Ing. Klaus Henning

Tag der mündlichen Prüfung: 26. Juni 2015

Acknowledgements

The ideas behind this thesis emerged from the engineering and research that I performed for the German telemedicine project TemRas. This was one of the research areas that I was lucky to be involved in during my five years of work as scientific researcher at the Institute of Information Management in Mechanical Engineering (IMA) that is part of the institute cluster IMA/ZLW & IfU of the RWTH Aachen University. Further research in this cluster encouraged me to widen my view regarding the applicability of these ideas to other domains such as autonomous vehicles and cooperative driving. At the same time, this work gave me the necessary freedom to complete my thesis during these five years.

Hence, my sincere gratitude belongs to every person who supervised me, supported me, or worked with me at the IMA/ZLW & IfU or in the research projects or otherwise supported me and my work. First and foremost, this is of course my adviser and head of the institute cluster, Prof. Sabina Jeschke, who always encouraged me in my work, provided critical feedback, and offered helpful support. I want to thank Prof. Klaus Henning for his role as second examiner of my thesis. Furthermore, I want especially to thank Prof. Daniel Schilberg, Tobias Meisen, Marie-Thérèse Menning, Max Haberstroh, Philipp Meisen, and Jesko Elsner for their time and effort they put into critical discussions and comments regarding my research and thoughts that contributed to the thesis. Special thanks go to Margit Werden, Jürgen Heinel, and Nicolai Mathar for their uncomplicated technical support, to Tomas Sivicki for making nice figures out of my sketched drawings, and Christian Schwier for helping to implement the simulation studies.

I am thankful to the parties that funded my work. Namely, the EU’s EFRE-Fonds and the Ministry of Innovation, Science and Research of the state of North Rhine-Westphalia (Germany) for the public funding of TemRas. In addition, the involved project partners—Philips HealthCare, P3 communications, 3M, the RWTH Aachen University, and the University Hospital Aachen—contributed own financial resources and have my gratitude.

Finally, I would never have completed the thesis without the loving support, dedication, and encouragement from my fiancée Juliane. I am also greatly thankful for the love and support I received from my parents, who have always believed in me and helped me to go my way.

Aachen, July 2015

Sebastian Thelen

Abstract

The term cyber-physical systems expresses the fundamental issues that arise when embedded systems are no longer encapsulated, closed systems but form open, interconnected systems of systems and established abstractions of system design begin to fail; namely, the aspect of time and availability of resources must no longer be hidden from application layer functions. From the numerous open research challenges that remain, this thesis addresses the prediction of local communication in mobile ad hoc networks in order to contribute to a more dependable communication in such a system of systems that cyber-physical systems are envisioned to form.

A research gap concerning the influence that contextual factors exert on the three connectivity metrics end-to-end communication delay, packet delivery ratio, and streaming window width, i.e., the amount of successive end-to-end transmissions without a packet loss, in a mobile ad hoc network with moving nodes has been identified. To fill this gap, a simulation study that follows a systematic, full factorial design using discrete event simulations is carried out. The simulation study’s outcome is analyzed with statistical data analysis methods to identify the study’s scenario parameters that have significant influence on the connectivity metrics.

Furthermore, the thesis contributes to the current state of the art research of real-time communication for control tasks via mobile ad hoc networks by proposing and evaluating three classes of prediction models for each of the three mentioned connectivity metrics. The three model classes differ in their complexity and intrusiveness regarding the network architecture. The simple black-box models fully reside in the application layer of the flow’s end-point nodes and use time-series forecasting and statistical models from reliability engineering. The cross-layer models require cooperation from intermediate nodes in the network to acquire information that is sensed along a flow’s current route. Most complex are the probabilistic network graph models that incorporate predictions of uncertain node locations and information sensed from throughout the network. Second level adaptation models use on-line supervised machine learning to improve the domain and statistical models’ predictions. The proposed prediction models are evaluated in carefully designed simulation studies using discrete event simulations that follow state of the art recommendations from the computer networking community to ensure the results’ validity.

Zusammenfassung

Der Begriff Cyber-Physische Systeme steht für die fundamentalen Herausforderungen die sich ergeben, wenn eingebettete Systeme nicht länger abgeschirmte, geschlossene Systeme sind, sondern offene, vernetzte Systeme von Systemen bilden und etablierte Abstraktionen des Systementwurfs versagen. Konkret heißt das, dass der Aspekt Zeit und die Verfügbarkeit von Ressourcen nicht länger vor der Anwendungsschicht eines Systems verborgen bleibt. Von den zahlreichen offenen Forschungsfragen, die in diesem Bereich noch bestehen, adressiert die vorliegende Arbeit die Vorhersage lokaler Kommunikation in mobilen ad-hoc Netzwerken, um so zu einer Verbesserung der Verlässlichkeit der Kommunikation beizutragen.

Eine Forschungslücke bezüglich des Einflusses, der durch Kontextfaktoren auf die drei Konnektivitätsmetriken Verzögerung der Kommunikation, Paketzustellungsverhältnis und Länge des Datenstromfensters, das heißt der Menge an konsekutiven Ende-zu-Ende Übertragungen ohne Paketverlust, in einem mobilen ad-hoc Netzwerk mit sich bewegenden Netzteilnehmern ausgeübt wird, wurde identifiziert. Um diese Forschungslücke zu schließen, wird eine Simulationsstudie mit ereignisdiskreten Simulationen durchgeführt, die einem systematischen, voll faktoriellen Experimentdesign folgt. Die Ergebnisse der Simulationsstudie werden mit statistischen Datenanalyseverfahren untersucht, um die Szenarioparameter zu bestimmen, die einen signifikanten Einfluss auf die Konnektivitätsmetriken ausüben.

Zusätzlich trägt die Arbeit zum aktuellen Stand der Forschung zu Echtzeit-Kommunikation für Steuerungs- und Regelungsaufgaben über mobile ad-hoc Netzwerke bei, indem drei Klassen von Vorhersagemodellen für jede der drei genannten Konnektivitätsmetriken vorgeschlagen und evaluiert werden. Die drei Modellklassen unterscheiden sich hinsichtlich ihrer Komplexität und Durchdringung der zugrundeliegenden Netzwerkarchitektur. Die einfachen Black-Box Modelle arbeiten vollständig in der Anwendungsschicht der Endpunkte eines Datenstroms und nutzen Methoden der Zeitreihenvorhersage sowie statistische Modelle der Zuverlässigkeitsmodellierung. Die Cross-Layer Modelle bedürfen der Kooperation intermediärer Netzwerkteilnehmer, um auf Informationen zuzugreifen, die entlang der Route eines Datenstroms durch das Netzwerk erfasst werden. Die höchste Komplexität besitzen die probabilistischen Netzwerkgraph Modelle, die unsichere Vorhersagen über zukünftige Positionen der Netzwerkteilnehmer sowie Informationen aus dem gesamten Netzwerk einbeziehen. Nachgelagerte Adaptionsmodelle verwenden Methoden der künstlichen Intelligenz, um die Vorhersagen der vorgelagerten Domänen- und statistischen Modelle durch überwachtes Online-Lernen zu verbessern. Die vorgeschlagenen Vorhersagemodelle werden mit Hilfe ereignisdiskreter Simulationen evaluiert. Um die Validität der Ergebnisse sicherzustellen, sind die Simulationen unter Berücksichtigung des aktuellen Standes der Empfehlungen der Computernetzwerk Forschungsgemeinde entworfen worden.

Contents

1. Introduction

1.1. Existing Research Gaps

1.2. Objectives

1.3. Methodology and Structure

2. Fundamental Concepts and Definitions

2.1. Real-Time Systems and Communication

2.2. Networked Control Systems

2.3. Mobile Ad Hoc Networks

2.3.1. Computer Networking Basics

2.3.2. Wireless Networks

2.3.3. Routing in Mobile Ad Hoc Networks

2.4. Data Analysis, Prediction, and Machine Learning

2.4.1. Regression, Classification, and Measures of Error

2.4.2. Time-Series

2.4.3. Forecasting Methods for Time-Series

2.4.4. Statistical Machine Learning

3. Application Scenarios

3.1. Scenario 1: Telemedicine for Disaster Intervention

3.2. MANETs for Telemedicine

3.3. Scenario 2: External Sensor Assistance for Autonomous Vehicles

3.4. MANETs for Autonomous Vehicles and Vehicular Communication

4. Related and Previous Work

4.1. Related Research in the Computer Networking Community

4.1.1. Enhanced Routing Protocols for Mobile Ad Hoc Networks

4.1.2. Quality of Service Mechanisms for Mobile Ad Hoc Networks

4.1.3. Connectivity Analysis in Wireless Sensor Networks

4.2. Related Research in the Control Systems Community

4.2.1. Using Real-Time Guarantees From the Network

4.2.2. Increased Robustness Towards Connectivity Issues

4.3. End-to-End Communication Delay Prediction

4.3.1. Aggregating Single-Hop Communication Delay Predictions

4.3.2. Communication Delay Prediction in the Internet

4.3.3. Forecasting of End-to-End Communication Delay Time-Series

4.4. Context Awareness in Mobile Ad Hoc Networks

4.5. Node Mobility and Localization

4.5.1. Node Mobility Prediction

4.5.2. Uncertainty in Node Localization

4.6. Conclusion

5. Connectivity in Mobile Ad Hoc Networks with Moving Nodes

5.1. Design of Experiment

5.1.1. Physical Layer Parameters

5.1.2. Scenario Parameters

5.2. Method for Statistical Experiment Analysis

5.3. Results

5.3.1. Observed Communication Delay

5.3.2. Observed Streaming Window Width

5.3.3. Rank Correlations and Explanatory Linear Models

5.3.4. Autocorrelation in Communication Delay Time-Series

5.3.5. Factor Influence Models

5.4. Discussion

5.4.1. Simulation Performance

5.4.2. Connectivity Metrics

5.4.3. Influencing Factors

5.5. Conclusion

6. Connectivity Prediction for Mobile Ad Hoc Networks

6.1. Mathematical Notations for the Network Model

6.2. Sensory Capabilities and Network Context Awareness

6.3. Predicting Connectivity from Node Locations

6.3.1. Probabilistic Network Graph

6.3.2. Prediction of Communication Link Probability

6.3.3. Handling Uncertainty in Predicted Node Locations

6.3.4. Constructing the Probabilistic Network Graph

6.4. Connectivity Prediction Models

6.4.1. Black-Box Models

6.4.2. Cross-Layer Models

6.4.3. Probabilistic Network Graph Models

6.5. Online Supervised Learning of Second-level Adaptation Models

6.6. Conclusion

7. Evaluation

7.1. Method for Model Assessment

7.2. Simulation Scenarios

7.3. Prediction Model Cross-Validation

7.3.1. Results

7.3.2. Discussion

7.4. Prediction Errors in Simulation Studies

7.4.1. Results

7.4.2. Discussion

7.5. Conclusion

8. Conclusion

8.1. Summary

8.2. Critical Discussion

8.3. Outlook

Bibliography

Appendix

A. Extended Concepts and Definitions

A.1. Mobile Ad Hoc Networks

A.1.1. Computer Networking Basics

A.1.2. IEEE 802.11 Wireless Local Area Networks

A.1.3. Routing in Mobile Ad Hoc Networks

A.2. Data Analysis, Prediction, and Machine Learning

A.2.1. Regression, Classification, and Measures of Error

A.2.2. Time-Series

A.2.3. Forecasting Methods for Time-Series

B. Mathematical Formulations and Computations

B.1. Log-distance Path Loss Model

B.2. Log-normal Shadowing Model

C. Software Packages

C.1. Use of the Statistical Computing Environment R

C.2. Use of the Discrete Event Simulator OMNeT++

List of Figures

1.1.   From embedded system to cyber-physical systems

1.2.   Structural model of the thesis’s contents

2.1.   Complexity cube of interconnected systems

2.2.   MANET with an application level data stream

3.1.   Telemedicine scenario

3.2.   Sensor assistance for autonomous vehicles

5.1.   Parametrized simulation scenario

5.2.   Data preparation and explanatory model fitting

5.3.   Data collection and factor influence model fitting

5.4.   Comparison of passive network metrics

5.5.   Histogram of the factorial experiment simulations’ packet delivery ratio

5.6.   The observed flow’s end-to-end communication delay

5.7.   Observed distributions from the factorial experiment’s communication delay

5.8.   Spread of observed communication delay

5.9.   Streaming window width and duration

5.10. Observed streaming window width distributions

5.11. Spread of observed streaming window widths

5.12. Communication delay explanatory models’ goodness of fit

5.13. Streaming window width explanatory models’ goodness of fit

5.14. Packet delivery ratio explanatory models’ goodness of fit

5.15. Coefficients for communication delay explanatory models

5.16. Coefficients for streaming window width explanatory models

5.17. Coefficients for packet delivery ratio explanatory models

5.18. Partial autocorrelation for the communication delay time-series

5.19. Model coefficients for factor influence models

6.1.   Sensory capabilities of network protocol layers

6.2.   Estimates for KLD

6.3.   Comparison of the path loss coefficient’s time-series

6.4.   Evaluation of Data-link layer frame reception prediction

6.5.   Evaluation of Data-link layer frame reception prediction with small training set sizes

6.6.   Comparison of reference and approximated uncertain distance distributions

6.7.   Estimated kernel densities of communication link probabilities

6.8.   Distribution of errors of estimated communication link probability

7.1.   Connectivity metrics computation using Application layer packet timings

7.2.   Normalized differences in model score

7.3.   Comparison of communication delay forecasting models

7.4.   Comparison of packet delivery ratio forecasting models

7.5.   Total packet delivery ratios

7.6.   Median hop counts

7.7.   Median of observed communication delay forecast errors

7.8.   Maximum of observed communication delay forecast errors

7.9.   Median of observed packet delivery ratio forecast errors

7.10. Maximum of observed packet delivery ratio forecast errors

7.11. Observed transmissions until next stream interruption prediction errors

A.1.   Communication between two applications via intermediate hosts

A.2.   Carrier-Sensing Multiple Access scheme with collision avoidance

List of Tables

2.1.   Naming of protocol messages for each layer in an Internet protocol/IEEE 802.11 protocol suit

5.1.   Configuration parameters used to analyse the factorial experiment study

5.2.   Transmit power of IEEE 802.11 WLAN devices

5.3.   Path loss exponents for various environments

5.4.   Physical layer model parameters

5.5.   Morpholigical field of simulation parameters

5.6.   Node speed and simulation area scenario parameters

5.7.   Definitions of node densities depending on average node speed

5.8.   Traffic type and other traffic scenario parameter

5.9.   Summary statistics for each simulation run in the factorial experiment study

5.10. Exact values to the communication delay order statistics distributions’ of figure 5.7

5.11. Exact values to the streaming window width order statistics distributions’ of figure 5.10

5.12. Spearman rank correlation coefficients of the factorial experiment’s configuration parameters to the connectivity metrics’ median

6.1.   Overview of the black-box connectivity prediction models

6.2.   Overview of the cross-layer connectivity prediction models

6.3.   Overview of the probabilistic network graph connectivity prediction models

7.1.   Usage of the adaptation models for cross-validation

7.2.   Selection of models for further evaluation after cross-validation

7.3.   Estimation of the forecast horizon’s influence on the prediction errors

C.1.   Utilized R packets and their versions

List of Acronyms

AODV Ad hoc On demand Distance Vector

ARIMA Autoregressive Integrated Moving Average

CAN Controller Area Network

CPS Cyber-Physical System

CSMA Carrier-Sensing Multiple Access

DCF Distributed Coordination Function

DSR Dynamic Source Routing

ECG electrocardiogram

EDCA Enhanced Distributed Channel Access

EIRP Equivalent Isotropic Radiated Power

GNSS Global Navigation Satellite System

GPS Global Positioning System

HTTP Hyper Text Transfer Protocol

ICMP Internet Control Message Protocol

IoT Internet of Things

IP Internet Protocol

IQR interquartile range

ISM Industrial, Scientific, and Medical

ISO International Organization for Standardization

LAN Local Area Network

MAC Medium Access Control

MANET Mobile Ad hoc Network

MSSE Mean Squared Scaled Error

MMC Mobility Markov Chain

NCS Networked Control System

OLSR Optimized Link State Routing

OSI Open Systems Interconnection

POI Point Of Interest

QoS Quality of Service

RSSI Received Signal Strength Indicator

SNR Signal to Noise Ratio

TCP Transport Control Protocol

UDP User Datagram Protocol

VANET Vehicular Ad hoc Network

WAVE Wireless Access in Vehicular Environments

WLAN Wireless Local Area Network

WSN Wireless Sensor Network

1.   Introduction

Ubiquitous computing has been a vision of computer scientists since the late 1980s: originating from the Xerox Palo Alto Research Center and pioneered by Mark Weiser, ubiquitous computing envisions “a physical world richly and invisibly interwoven with sensors, actuators, displays, and computational elements, embedded seamlessly in the everyday objects of our lives and connected through a continuous network” [WGB99, p. 694]. The currently more prevalent term Internet of Things (IoT) refers to the technological vision in which physical things that a user interacts with are connected to services in the Internet that enrich them with contextual information and provide a pervasive service experience [Zor+10]. In their comprehensive survey, Atzori, Iera, and Morabito [AIM10] emphasise the shift from IoT’s initial focus on uniquely identifiable physical objects, the things, to a more converged vision of information that is attached to things via Internet services. The information transfer via the Internet ensures interoperability and seamless accessibility, but is unable to provide reliable, dependable communication in the sense of critical real-time applicability.

Combining computing capabilities and physical objects has typically been the domain of embedded systems: devices, whose functionality is defined by their hardware as much as their software, running on microprocessors or in electronic circuits. The term Cyber-Physical System (CPS) marks a change of perspective in the development of such embedded systems. E. A. Lee [Lee06] argues that the currently available level of computing power and networking capabilities for embedded systems caused this change away from regarding their development mostly as an optimization problem towards a focus on reliability and predictability, especially for safety-critical applications like avionics or medicine. Following the vision of ubiquitous computing, embedded systems are now getting designed for much closer interaction with their physical vicinity, while at the same time relying more on the interaction with other computing systems through networking than before [Sta+05]. Their tight, often closedloop, coupling with the physical world inherently enforces time as a measure for correctness onto software and communication in these embedded systems [Lee06]. But unlike classical embedded systems that are designed as closed systems, fully validated at design time, figure 1.1 expresses how this has changed to individual CPSs that together form an open, dynamic system of systems.

Figure 1.1.: Embedded systems typically were designed as single, closed systems; CPSs instead are embedded systems that connect to other systems to form an open, dynamic system of systems.

The fundamental issue that arises when embedded systems are no longer encapsulated, closed systems but form open, interconnected systems of systems, is that established abstractions of system design begin to fail; namely, the aspects of time and availability of resources must no longer be hidden from application layer functions [Lee08]. Time becomes a coordinated measure and the ability of individual systems to keep their timing constraints or to offer a certain service might vary with time and the presence of other systems.

With this background, IoT and CPS are merely regarded as labels for formerly distinct, but strongly converging efforts to get closer to the old idea of ubiquitous computing. A view that, three centuries later, underlines the visionary power at the Xerox Palo Alto Research Center. The definition of said distinction is that IoT is about devices, in the form of things, that present or gather contextual information; CPS is about devices that actively manipulate the physical world. The former is all about semantic interoperability and connectivity to Internet services that store and process the information, the latter is inherently real-time and requires dependable systems. From the numerous open research challenges that remain, this thesis addresses the prediction of local communication, an aspect that falls into the CPS label of ubiquitous computing, when considering the above distinction.

Lee et al. [Lee+12] name the rise of network dependant functionality in embedded devices as one of the major issues that drive the complexity of system design for CPSs; connectivity between devices in CPSs is still a challenge and an open field of research, while at the same time being one of the core aspects of CPSs [Lee08; Lee+12]. An abundance of wireless networking technologies for communication between multiple computing devices exist today. Of these, infrastructure based Wireless Local Area Networks (WLANs), often called WiFi networks, and cellular mobile networks, currently in their fourth generation, are ubiquitous around the world. Less common are Mobile Ad hoc Networks (MANETs), computer networks that connect devices without the necessity of dedicated infrastructure. The ability to create a communication network between dynamically changing participants without any additional infrastructure lets MANETs appear to be designated for the role of providing local communication between the individual devices of the described system of systems. Yet, the technological challenges that arise from the lack of central coordination and general dynamics in the communication network have prevented widespread adoption of MANETs, a matter that Basagni et al. [Bas+13] discuss further. With the intention to contribute to some of the challenges that arise when using MANETs to connect CPSs, the thesis’s focus lies on this networking concept.

Principally, the thesis’s research objectives, which are laid out in more detail below, are independent of specific use cases. Nevertheless, two application scenarios, to which the investigated subject is of relevance, are introduced to provide a less abstract perspective on the matter and to help to derive concrete requirements for evaluation. The two application scenarios are motivated by previous work by the author and general research interest: telemedicine and cooperative driving.

Lately, Haupt et al. [Hau+14] have presented techniques to use MANETs for control applications that require real-time communication. In the field of transportation, MANETs are currently gaining importance as a method to provide future operation-critical communication between vehicles that shall enable cooperative driving; first steps to bring such vehicular communication systems to market are underway, e.g., with the European Cooperative ITS Corridor that will disseminate road work and obstacle warnings to drivers, as Ross [Ros15] reports. Other ideas are more visionary, such as Gerla et al. [Ger+14] who propose massive cooperation of autonomous vehicles in the form of Vehicular Clouds.

Besides transportation, network communication for disaster intervention is a field considered for the application of MANETs in order to be independent of possibly destroyed communication infrastructure. A possible application that such a network has to support is remote patient monitoring for real-time telemedicine. This introduces reliability and timing requirements into the communication systems, as discussed by Thelen et al. [The+15]. To highlight the importance of dependability in inter-device communication in medical systems, Lee and Sokolsky [LS10] have coined the term Medical Cyber-Physical Systems. However, Sneha and Varshney [SV13] have identified the predictability of communication to be an open research issue when using MANETs for remote patient monitoring.

1.1.  Existing Research Gaps

In light of the background given above and in anticipation of the detailed discussion of previous and related work in chapter 4, the research gaps that this thesis addresses are presented here. A very specific research gap has already been identified by others: There is a lack of understanding about the influence that node mobility exerts on end-to-end connectivity metrics for mulit-hop MANETs. The two comprehensive, recent survey on Quality of Service (QoS) for MANETs by Khoukhi et al. [Kho+13] and by Al-Anbagi, Erol-Kantarci, and Mouftah [AEM14] prominently highlight the lack thereof in current work. Furthermore, from the work on this thesis, it has been found that existing work not only neglects the effect of mobility, but only addresses the two connectivity metrics delay and packet delivery ratio, i.e., the ratio of successfully received to transmitted packets. There is generally no consideration of a metric that describes the time until the next packet is lost. Much of the existing work uses stochastic and queueing model frameworks to analyse connectivity metrics, but only few of these studies validate their results with experimental methods. Research question 1 that is addressed in chapter 5 contributes toward closing this research gap.

Prediction of connectivity metrics for 1-hop communication between directly neighboring nodes is used in routing protocols to anticipate route breaks and establish new routes before communication is affected. Missing though, is any work on predicting the chance of finding a new route and thus the influence of an anticipated route break for the communication that uses the route. In delay tolerant networks, which realise information dissemination via the communication of moving and intermittently connected participants, predictions of end-to-end connectivity metrics from the participants’ mobility are used to improve the information dissemination strategy. But delay tolerant networks are a different category of networks than ones that shall support real-time communication and the applied methods are hardly transferable. This leaves a research gap on the prediction of end-to-end connectivity in multi-hop MANETs for real-time communication that are affected by node mobility. Research questions 2 and 3 that are addressed in chapters 6 and 7 contribute methods and first prediction models to address this research gap.

Far broader open issues of research are to actually make applications, services, and control systems adaptable to predicted connectivity metrics and to achieve connectivity awareness for applications that use dynamic multi-hop MANETs to improve the dependability of such networks for real-time communication. Solving these issues will improve the versatility of MANETs for communication in highly dynamic CPSs.

The lack of work on the predictability on communication in MANETs may largely stem from the research domains’ focus: research from the computer science community primarily addresses the improvement of routing and other protocols in the network or QoS methods that reserve and guarantee network capacity until the guarantee can no longer be upheld and the participants affected have to reapply for their required capacities. The control systems community on the other hand has focused on research to improve a controlled system’s performance given predefined uncertainties that communication via a packet switched network induces. Recent work, such as Haupt et al. [Hau+14], rigorously address the interactions of network and control system in a joint design approach that is suitable for closed systems. So far no attempt has been published to predict the behaviour of an open MANET in order to increase its dependability for use by future dynamic and interconnected CPSs.

1.2.  Objectives

The introductory discussion of CPSs using both autonomous, cooperative driving and telemedicine as application examples point at a prevalent dilemma: on one hand the need for dynamic and flexible communication between open collections of devices to benefit from their offered services and on the other hand the need for predictable and timely communication between a device and the services its operation depends upon. At a roundtable on the reliability of embedded systems, J. A. Stankovic stipulates that a system’s awareness of various operational aspects is key to increase its robustness [BSS10, p. 32]:

There are many, many examples of physical properties from the real world that cause the system to fail. To address this, we need what I’ve been calling star-aware software, where the star is the Kleen star and refers to such software as physically aware, security aware, privacy aware, and so on. Such an approach has the potential to make the system very robust. The level of robustness must increase, and hopefully we can make this into more of a scientific process, so that when we construct systems, they are robust enough against the vagaries of the real world.

In this sense, the thesis’s objective is to contribute towards making systems network aware by predicting the future connectivity of an ongoing communication flow in a MANET. Connectivity here is used to unite three metrics: the delay that messages experience in the network on their way from origin to destination, the communication delay, and two metrics that are themselves summarized as communication interruption: the remaining time until streaming interruption, i.e., the time until the next Network layer message will be lost, and the packet delivery ratio, i.e., the ratio of successfully received to transmitted Network layer messages. When analysing the connectivity in hindsight, instead of the time varying remaining time until streaming interruption, the streaming window duration is used instead. Having these metrics available to a device’s applications shall then allow the applications to adapt and degrade gracefully under worsening conditions, because the change in conditions will be anticipated.

Communication delay and packet delivery ratio are common metrics for the evaluation of new protocols that are researched and proposed frequently by the computer science community. Still, they are usually not analyzed in and out of themselves, nor with the intention to predict or forecast the metrics. Because of this lack of insight into the properties of connectivity in MANETs that is exploitable for prediction, they are investigated before deriving potential prediction models.

The investigation of connectivity in MANETs is done by looking at the influence that contextual factors in the form of scenario parameters, such as number of participants in the network or their average movement speed, exert. An important property of the contextual factors has to be that they define a setting that remains more or less stable. Thereby a necessary baseline for the connectivity metrics is established and viable directions for realizing the metrics’ prediction models are obtained. Explicitly formulated the thesis addresses three research questions:

RQ 1  To what degree do contextual factors, in the form of scenario parameters, influence the connectivity metrics, communication delay and communication interruption, in a MANET?

RQ 2  By what method can the communication delay in a MANET be predicted to be suitable for real-time control applications?

RQ 3  By what method can the communication interruption in a MANET be predicted to be suitable for real-time control applications?

The primary tool to investigate the research questions is the use of discrete event simulations, as is common place for research in MANETs. It is further assumed that the movement of the devices that form the MANET is predictable to a certain degree. In case of autonomous vehicles, Levinson et al. [Lev+11] suggest that future high precision movement trajectories are usually available at the planning level. For humans, Song et al. [Son+10] have found potential for 93% predictability of the locations visited, based on past locations. The relatively slow movement of a walking human is expected to further simplify the prediction of possible movement trajectories at a time horizon of a few minutes.

1.3.  Methodology and Structure

The main methods that underlie the thesis’s contribution belong to the domains of statistical data analysis, predictive statistical modelling enriched with machine learning, and simulation of computer networks with discrete event simulations. All data analysis in chapter 5 as well as the implementation and evaluation of the predictive models in chapters 6 and 7 is carried out using the statistical computing environment R1. The experiments that provide the data that underlies the statistical analysis in chapter 5 as well as the experiments that are used for model synthesis in chapter 6 and evaluations in chapter 7 are realized with the discrete event simulator OMNeT++2.

Methodologically, the systematic, experimental analysis of contextual scenario parameters regarding their influence on end-to-end connectivity metrics that is discussed in chapter 5 results in knowledge on the metrics variance and dependence on contextual scenario parameters. This answers research question 1 and provides the necessary groundwork to derive the candidate predictive models in chapter 6. For each metric, candidate models from three categories are derived: pure forecasting models that treat the network as a black-box, models based on metrics along the current route that get accessible via cross-layer design, and models that build a probabilistic network graph from predictions of the network participants’ future locations. Furthermore, a second level adaptation model for the predictions from the cross-layer and the probabilistic network graph models is considered that uses on-line supervised learning to continuously adapt the prediction models during their operation. To evaluate the prediction models in chapter 7, the complete set of candidate models is compared in a cross-validation step. A set consisting of the best model per connectivity metric and model category is then evaluated in more detail to answer research questions 2 and 3.

Figure 1.2 shows the thesis’s complete structure. Besides the central chapters 5, 6, and 7 that contain the thesis’s contribution to advance the current state of the art research and that have already been outlined in the presentation of methodology above, the thesis’s structure is as follows: Chapter 2 introduces the terms, fundamental concepts, and methods that are used in the thesis. Chapter 3 introduces the two application scenarios that serve to connect the thesis’s theoretical work with practical applications. The first application scenario, cf. section 3.1, is motivated by previous work in telemedicine: the use of a MANET to perform synchronous telemedical consultations with real-time biomedical patient monitoring. The second application scenario, cf. section 3.3, is geared towards the development of intelligent transportation systems: the use of a MANET of vehicles and infrastructure to increase the sensor coverage of autonomous vehicles and enable cooperation. Both scenarios are used throughout the later chapters to justify parameter and design choices. Chapter 4 presents the relevant previous and related work and chapter 8 concludes the thesis with a summary, a critical review, and an outline of the important open issues in the domain of dependable communication for CPSs via MANETs that future research may address.

Figure 1.2.: Structural model of the thesis’s contents with chapter alignments.

1R is open source software that is available from http://www.r-project.org/. R version 3.1.1 was used for the work that is presented in the thesis, more details are given in the appendix section C.1.

2OMNeT++ (OpenSim Ltd., Budapest, Hungary) is distributed under an Academic Public License that allows free use for academic, non-commercial purposes; the software is available from http://www.omnetpp.org/. OMNeT++ version 4.4.1 with the INET library version 2.4.0 was used for the work that is presented in the thesis, more details are given in the appendix section C.2.

2.   Fundamental Concepts and Definitions

2.1.  Real-Time Systems and Communication

The term real-time emphasises the passing of time, as is immanent in the physical world. For a real-time computation or communication system, the correctness of a computation or a message transaction depends as much on the time of its completion, as on the result or message content itself. Already in 1988 Stankovic raised awareness for a major misconception of real-time systems and argued [Sta88, p. 11]: “Predictability, not speed, is the foremost goal in real-time-systems design.” 20 years later, in his discussion of design challenges for CPS, E. A. Lee raised awareness of the same issue: most advancements in the performance of computing devices, e.g., various levels of caches, branch prediction, and pre-fetchers, have all worsened the predictability of timing [Lee08]. Instead, aspects of time are well hidden by all layers of abstractions that form the basis of today’s computer programming methods, starting down at the level of machine instructions and going all the way up to higher programming languages and model driven development: Systems are first designed and only thereafter validated against their timing requirements [Lee08].

Real-time requirements imposed on a system usually arise from the physical processes of the environment with which it is designed to interact. These requirements are defined in terms of deadlines before which computations or message transactions have to be completed. Depending on the criticality of missing a deadline, three levels of real-time requirements are distinguished [But11]:

hard real-time Missing a deadline leads to a catastrophic system failure.

firm real-time Missing a deadline renders the computation or message useless, but causes no further harm.

soft real-time Missing a deadline reduces the system’s performance but does not invalidate a computation or message.

From a network perspective, hard real-time requirements are the domain of Networked Control System (NCS) with usually fixed network structure and carefully designed and validated scheduling [WY01]. For soft real-time requirements, two traffic categories are further distinguished [Pea+11]:

inelastic soft real-time Communication with stringent delay constraints and usually fixed bandwidth requirements. System performance strongly correlates with the communication delay.

elastic soft real-time Communication for which increased delay is merely inconvenient, like traffic from normal email transmission or web browsing; this traffic is usually greedy in bandwidth consumption [Li+11].

With WirelessHART, the industry has adopted a specialized network protocol stack for centrally managed mesh control networks on top of the IEEE 802.15.4 Physical layer [Che+14]. Never the less, models for control systems over wireless networks are stochastic; they do not allow deriving of deterministic guarantees for upper bounds of network-induced delays [JJ10]. Hence, hard real-time applications depend on a carefully engineered, static setup. With this background it is clear that providing a predictable communication delay is a key issue of networking in real-time systems [WY01]. Given the definitions above, the thesis contributes to prediction of connectivity metrics for inelastic soft real-time communication.

2.2.  Networked Control Systems

A rigorous take on CPSs comes from the control systems research community, to which Lunze and Grüne [LG14] give a state of the art introduction. Understanding this research domain’s methods to incorporate communication properties into system design is important when proposing new concepts that aim at improving the communication’s dependability for such control systems. Research in systems and control theory has developed a wide range of methods to describe and analyze dynamic systems: from simple linear state-less over state-full to non-linear systems, operating with continuous or discrete time. But instead of being a single system of a plant and one or more independent controllers, CPSs usually have the form of multiple, interacting, dynamic systems. The complexity cube of interconnected systems, cf. figure 2.1, classifies such systems based on the three types of complexity that are relevant for system analysis and controller design: individual system’s complexity, link complexity, and topological complexity [Wie10