| Abstract: |
The confluence of networked embedded computing, low-power wireless communications, and sensor technology has spawned a whole spectrum of powerful applications that are commonly believed to
radically change the way we perceive and interact with the physical world. Data collection applications, for example, enable the monitoring of physical phenomena with unprecedented spatial and
temporal resolutions, and cyber-physical systems (CPS) applications can control physical processes by integrating sensing and computation with actuation into distributed feedback loops.
Application domains include transportation, healthcare, and buildings. Data collection and CPS applications alike demand predictability and efficiency from the wireless communication substrate to
function correctly and effectively. In particular, these applications require a certain energy efficiency, reliability, and timeliness of end-to-end packet transmissions. Meeting perhaps multiple
such non-functional requirements is, however, extremely challenging. This is due to, for example, the need for multi-hop communication over lossy low-power wireless channels, unpredictable and
non-deterministic changes in the environment, and limited resources of the employed devices in terms of computation, memory, and energy. Dedicated solutions have been proposed that attempt to
tackle these challenges in order to satisfy the needs of either non-critical data collection or critical CPS applications. As for the former, adapting the operational parameters of the MAC
protocol proved to be highly effective; however, current efforts focus only on a single performance metric or consider local metrics, whereas applications often exhibit requirements along
multiple metrics that are most naturally expressed in global, network-wide terms. As for the latter, state-of-the-art solutions including industry standards do not provide hard end-to-end
real-time guarantees because of a localized operation, or can hardly keep up with dynamic changes in the network. To address these problems, this thesis presents new analytical results as well as
real implementations of novel protocols and systems that make use of them. Specifically, we make three main contributions: - We design pTunes, a framework that meets multiple soft application
requirements on network lifetime, end-to-end reliability, and end- to-end latency by adapting the MAC protocol parameters at runtime in response to changes in the network and the traffic load.
pTunes exploits a centralized approach that is similar in spirit to a model-predictive controller. Results from testbed experiments show that relative to carefully chosen fixed MAC parameters
pTunes extends network lifetime by up to 3x, and reduces packet loss by 70–80 % during periods of wireless interference or when multiple nodes fail. - A new breed of protocols that utilize
synchronous transmissions has been shown to enhance the reliability and efficiency of protocols that use link-based transmissions. We find that these emerging protocols also enable simpler and
more accurate models, which play a key role in system design, verification, and runtime adaptation to meet given requirements. We show through testbed experiments and statistical analyses that
unlike link-based transmissions, packet receptions and losses using synchronous transmissions with Glossy can largely be considered statistically independent events. This property greatly
simplifies the accurate modeling of protocols based on synchronous transmissions. We demonstrate this by obtaining an unprecedented error below 0.25 % in the energy model of the Glossy-based Low-
power Wireless Bus (LWB), and providing sufficient conditions for probabilistic guarantees on LWB’s end-to-end reliability. - We present Blink, the first protocol that provides hard
guarantees on end-to-end packet deadlines in large multi-hop low-power wireless networks. Built on top of LWB as communication support, we map the scheduling problem in Blink to uniprocessor
scheduling. We devise earliest deadline first (EDF) based scheduling policies that Blink employs to compute online a schedule that provably meets all deadlines of packets released by admitted
real-time packet streams while minimizing the network-wide energy consumption within the limits of LWB, tolerating changes in the network and the set of streams. An efficient priority queue data
structure and algorithms we design prove instrumental for a viable implementation of these policies on resource-constrained nodes. Our experiments show that Blink meets nearly 100 % of packet
deadlines on a large multi-hop testbed, and achieves speed-ups of up to 4.1x over a conventional scheduler implementation on state-of-the-art microcontrollers. |
