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

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