This thesis follows the collection thesis structure commonly recommended in
the technical departments of the Nordic universities.
The contributions presented in this thesis have previously appeared in the manuscripts listed under
the Included Papers.
It shall be noted that the papers: A, E, J, K and the draft
of B were also part of my Licentiate thesis .
Full list of publications available on Google scholar .
Advisors:
Olaf Landsiedel (Chalmers and Kiel),
Philippas Tsigas (Chalmers), and
Simon Duquennoy (Yanzi Networks, formerly: RISE SICS).
Examiner:
Andrei Sabelfeld (Chalmers).
Faculty opponent:
Kay Römer (TU Graz, Austria).
Grading committee:
Marco Zúñiga (TU Delft, Netherlands).
Utz Roedig (University College Cork, Ireland).
Mikael Gidlund (Mid Sweden University, Sweden).
Thesis to be defended in public on
Wednesday, November 6, 2019, at 10.00 in lecture hall HA2,
Campus Johanneberg, Hörsalsvägen 4, Chalmers University of Technology (map )
for the Degree of Doctor of Philosophy.
Full text: Open access at Chalmers University library
With the emergence of the Internet of Things, autonomous vehicles and the Industry 4.0, the need for dependable yet adaptive network protocols is arising. Many of these applications build their operations on distributed consensus. For example, UAVs agree on maneuvers to execute, and industrial systems agree on set-points for actuators. Moreover, such scenarios imply a dynamic network topology due to mobility and interference, for example. Many applications are mission- and safety-critical, too. Failures could cost lives or precipitate economic losses.
In this thesis, we design, implement and evaluate network protocols as a step towards enabling a low-power, adaptive and dependable ubiquitous networking that enables consensus in the Internet of Things. We make four main contributions:
The papers are available to download in pdf format
Simon Duquennoy, Beshr Al Nahas, Olaf Landsiedel, and Thomas Watteyne.
Proceedings of the Conference on Embedded Networked Sensor Systems
(ACM SenSys), 2015.
Time slotted operation is a well-proven approach to achieve highly-reliable low-power networking through scheduling and channel hopping. It is, however, difficult to apply time slotting to dynamic networks as envisioned in the Internet of Things. Commonly, these applications do not have pre-defined periodic traffic patterns and nodes can be added or removed dynamically.
This paper addresses the challenge of bringing TSCH (Time Slotted Channel Hopping MAC) to such dynamic networks. We focus on low-power IPv6 and RPL networks, and introduce Orchestra. In Orchestra, nodes autonomously compute their own, local schedules. They maintain multiple schedules, each allocated to a particular traffic plane (application, routing, MAC), and updated automatically as the topology evolves. Orchestra(re)computes local schedules without signaling overhead, and does not require any central or distributed scheduler. Instead, it relies on the existing network stack information to maintain the schedules. This scheme allows Orchestra to build non-deterministic networks while exploiting the robustness of TSCH.
We demonstrate the practicality of Orchestra and quantify its benefits through extensive evaluation in two testbeds, on two hardware platforms. Orchestra reduces, or even eliminates, network contention. In long running experiments of up to 72 h we show that Orchestra achieves end-to-end delivery ratios of over 99.99%. Compared to RPL in asynchronous low-power listening networks, Orchestra improves reliability by two orders of magnitude, while achieving a similar latency-energy balance.
Beshr Al Nahas, Simon Duquennoy, and Olaf Landsiedel.
Proceedings of the Conference on Embedded Networked Sensor Systems
(ACM SenSys), 2017.
In low-power wireless networking, new applications such as cooperative robots or industrial closed-loop control demand for network-wide consensus at low-latency and high reliability. Distributed consensus protocols is a mature field of research in a wired context, but has received little attention in low-power wireless settings. In this paper, we present A2: Agreement in the Air, a system that brings distributed consensus to low-power multi-hop networks. A2 introduces Synchrotron, a synchronous transmissions kernel that builds a robust mesh by exploiting the capture effect, frequency hopping with parallel channels, and link-layer security. A2 builds on top of this reliable base layer and enables the two- and three-phase commit protocols, as well as network services such as group membership, hopping sequence distribution and re-keying.
We evaluate A2 on four public testbeds with different deployment densities and sizes. A2 requires only 475 ms to complete a two-phase commit over 180 nodes. The resulting duty cycle is 0.5% for 1-minute intervals. We show that A2 achieves zero losses end-to-end over long experiments, representing millions of data points. When adding controlled failures, we show that two-phase commit ensures transaction consistency in A2 while three-phase commit provides liveness at the expense of inconsistency under specific failure scenarios.
Beshr Al Nahas, Simon Duquennoy, and Olaf Landsiedel.
Proceedings of the International Conference on Embedded Wireless Systems and Networks
(EWSN), 2019.
Bluetooth is an omnipresent communication technology, available on billions of connected devices today. While it has been traditionally limited to peer-to-peer and star network topology, the recent Bluetooth 5 standard introduces new operating modes to allow for increased reliability and Bluetooth Mesh supports multi-hop networking based on message flooding. In this paper, we present BlueFlood. It adapts concurrent transmissions, as introduced by Glossy, to Bluetooth. The result is fast and efficient network-wide data dissemination in multi-hop Bluetooth networks. Moreover, we show that BlueFlood floods can be reliably received by off-the-shelf Bluetooth devices such as smartphones, opening new applications of concurrent transmissions and a seamless integration with existing technologies.
We present an in-depth experimental feasibility study of concurrent transmissions over Bluetooth PHY in a controlled environment. Further, we build a small-scale testbed where we evaluate BlueFlood in real-world settings of a residential environment. We show that BlueFlood achieves 99% end-to-end delivery ratio in multi-hop networks with a duty cycle of 0.13% for 1-second intervals.
Valentin Poirot, Beshr Al Nahas, and Olaf Landsiedel.
Proceedings of the International Conference on Embedded Wireless Systems and Networks
(EWSN), 2019.
Many applications in low-power wireless networks require complex coordination between their members. Swarms of robots or sensors and actuators in industrial closed-loop control need to coordinate within short periods of time to execute tasks. Failing to agree on a common decision can cause substantial consequences, like system failures and threats to human life. Such applications require consensus algorithms to enable coordination. While consensus has been studied for wired networks decades ago, with, for example, Paxos and Raft, it remains an open problem in multi-hop low-power wireless networks due to the limited resources available and the high cost of established solutions.
This paper presents Wireless Paxos, a fault-tolerant, network-wide consensus primitive for low-power wireless networks. It is a new flavor of Paxos, the most-used consensus protocol today, and is specifically designed to tackle the challenges of low-power wireless networks. By building on top of concurrent transmissions, it provides low-latency, high reliability, and guarantees on the consensus. Our results show that Wireless Paxos requires only 289 ms to complete a consensus between 188 nodes in testbed experiments. Furthermore, we show that Wireless Paxos stays consistent even when injecting controlled failures.
Simon Duquennoy, Atis Elsts, Beshr Al Nahas, and George Oikonomou.
Proceedings of the Conference Distributed Computing in Sensor Systems
(DCOSS), 2017.
Domenico De Guglielmo, Beshr Al Nahas, Simon Deuqennoy, Thiemo Voigt, and Giuseppe Anastasi.
IEEE Transactions on Vehicular Technology (TVT), 2016.
Beshr Al Nahas, Simon Duquennoy, Venkatraman Iyer, and Thiemo Voigt.
Proceedings of the Conference Distributed Computing in Sensor Systems
(DCOSS), 2014.
Liam McNamara, Beshr Al Nahas, Simon Deuqennoy, Joakim Eriksson, and Thiemo Voigt.
Proceedings of the International Conference on Embedded Wireless Systems and Networks
(EWSN), 2014.
The following papers are extended abstracts of our solutions of the EWSN Dependability Competition where we scored the third place twice (2016, 2017) and then the fourth place (2018).
Beshr Al Nahas, and Olaf Landsiedel.
Proceedings of the International Conference on Embedded Wireless Systems and Networks
(EWSN), 2018.
Beshr Al Nahas, and Olaf Landsiedel.
Proceedings of the International Conference on Embedded Wireless Systems and Networks
(EWSN), 2017.
Beshr Al Nahas, and Olaf Landsiedel.
Proceedings of the International Conference on Embedded Wireless Systems and Networks
(EWSN), 2016.