Close

PhD Thesis and List of Publications

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.

Synchronous and Concurrent Transmissions for Consensus in Low-Power Wireless

Reliable and Low-Latency Autonomous Networking for the Internet of Things

Full text: Open access at Chalmers University library

Abstract

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:

Included Papers

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.

  1. Orchestra: Robust Mesh Networks Through Autonomously Scheduled TSCH
    pdf Code , use in Contiki-ng IoT OS
  2. Abstract

    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.

  3. Network-wide Consensus Utilizing the Capture Effect in Low-power Wireless Networks
    pdf Code
  4. Abstract

    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.

  5. Concurrent Transmissions for Multi-Hop Bluetooth 5
    pdf Code
  6. This paper received the best paper award of the conference.

    Abstract

    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.

  7. Paxos Made Wireless: Consensus in the Air
    pdf Code
  8. This paper was nominated as a candidate to the best paper award.

    Abstract

    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.

    Other Papers

    Simon Duquennoy, Atis Elsts, Beshr Al Nahas, and George Oikonomou.
    Proceedings of the Conference Distributed Computing in Sensor Systems (DCOSS), 2017.

  9. TSCH and 6TiSCH for Contiki: Challenges, Design and Evaluation
    pdf
  10. Domenico De Guglielmo, Beshr Al Nahas, Simon Deuqennoy, Thiemo Voigt, and Giuseppe Anastasi.
    IEEE Transactions on Vehicular Technology (TVT), 2016.

  11. Analysis and experimental evaluation of IEEE 802.15.4e TSCH CSMA-CA Algorithm
    pdf
  12. Beshr Al Nahas, Simon Duquennoy, Venkatraman Iyer, and Thiemo Voigt.
    Proceedings of the Conference Distributed Computing in Sensor Systems (DCOSS), 2014.

  13. Low-Power Listening Goes Multi-Channel
    pdf
  14. 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.

  15. Demo Abstract: SicsthSense - Dispersing the Cloud
    pdf
  16. Dependability Competition

    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.

  17. Competition: Aggressive Synchronous Transmissions with In-network Processing for Dependable All-to-All Communication
    pdf poster
  18. Beshr Al Nahas, and Olaf Landsiedel.
    Proceedings of the International Conference on Embedded Wireless Systems and Networks (EWSN), 2017.

  19. Competition: Towards Low-Power Wireless Networking that Survives Interference with Minimal Latency
    pdf
  20. Beshr Al Nahas, and Olaf Landsiedel.
    Proceedings of the International Conference on Embedded Wireless Systems and Networks (EWSN), 2016.

  21. Competition: Towards Low-Latency, Low-Power Wireless Networking under Interference
    pdf