[IPSN’23 Best Paper] Network On or Off? Instant Global Binary Decisions over UWB with Flick
In a nutshell: Flick is a novel network primitive that can establish a binary decision over a large wireless network in a fraction of a millisecond, with order-of-magnitude improvement over state of the art.
Introduction: Low-power wireless & concurrent transmissions
Low-power wireless networks are used in a wide range of applications, from sensing to localization. With no cabling involved, installation is simple, cheap, and battery-powered devices can be deployed in areas with no access to the power grid. However, this flexibility comes at a cost: communication protocols must be carefully tuned to save energy, by keeping the radio of the transceivers off as much as possible.
For decades, researchers have refined MAC layers, designed new communication stacks, studied ways to establish overlay networks to route messages efficiently, and categorized traffic patterns to find the best routing strategy. A lot of this effort stemmed from a supposedly fundamental requirement: signals from different transmitters should not overlap in time, space, and frequency, or else they would result in a collision, making it impossible for the receiver to decode any of the incoming data packets. In other words, no concurrent transmission is allowed.
In reality, concurrent transmissions (CTX) are not only possible across many PHY layers, but also surprisingly advantageous. The seminal work on flooding with Glossy showed that, when the right PHY-level constraints are met, CTX allow the construction of communication primitives and network stacks that outperform existing solutions in terms of reliability, latency, and energy consumption. All three aspects are key for low-power wireless communication systems. Following this result, many protocols have integrated Glossy or other CTX variants.
On or off: The main question in low-power networks
Glossy is often used to disseminate “events” from a node to the rest of the network.
Indeed, several systems exhibit a pattern of operation where the network must check at designated times whether a given condition holds at some node. If so, all involved nodes schedule a Glossy flood, signaling that the whole network must remain awake to perform a required action; otherwise, it returns immediately to sleep. Prominent examples exhibiting this pattern include event-triggered control, aperiodic data collection, and distributed schedule updates.
This signaling phase is often the prevalent operation in the system, thus the decisive factor affecting the battery life of a node. When a check is scheduled, the faster the network agrees on the binary on/off condition the faster it can enter sleep, saving energy.
Although Glossy-based stacks are faster and more efficient than conventional alternatives, their energy cost and latency still pose significant limitations, especially in large networks and when events are checked at high rates. This is where our proposed primitive, Flick, comes into play.
Instant decisions, like the Flick of a switch
The basic principle behind CTX is that nodes can re-transmit a packet as soon as they receive it, together with any other node, with no delays and yet without compromising reliability. Flick takes the same approach, with a stark difference: nodes do not even wait to receive an entire packet, with its full preamble, header, and data payload; instead, they re-transmit immediately after detecting an incoming packet preamble. Hop by hop, Flick effectively creates a preamble flood.
The presence or absence of a Flick flood establishes the true/false value of the binary decision. Let’s make an example. Suppose you have a wireless system deployed in an industrial facility, connecting sensors that monitor the state of machinery for predictive maintenance. Each node in the multi-hop network periodically wakes up its radio; sensors detecting a fault must report data about the anomaly. To this end, a Flick round is scheduled. Any sensor node observing a fault (“true”) transmits a preamble via Flick, the others listen. If a preamble is detected, the listening Flick node takes the value “true” and repropagates the preamble; if there is no detection, it’s “false” instead and no preamble is transmitted. At the end of a “true” Flick round, every node in the network knows it should stay awake to propagate the anomaly data; instead, after a “false” round, the whole network can immediately enter sleep mode again with no need for further coordination, saving significant energy.
The benefits of Flick depend on how fast the preamble flood propagates. Its speed depends on several factors: the time it takes to detect a preamble, the time it takes for the MCU to handle the incoming interrupt from the radio, and the time it takes to transmit the preamble to continue the flood. While some of these are implementation-related, preamble detection depends on the radio technology and PHY layer used, and those used in Flick may come as a surprise.
Ultra-wideband = Ultra-fast flooding
Although the basic principles of Flick can be applied to various radio technologies, we focused on ultra-wideband (UWB) and the popular DW1000 chip. Mostly known for its distance estimation capabilities, UWB actually offers valuable features for communication as well.
In this case, we are mainly interested in the possibility to detect UWB preambles very quickly, which indeed happens in just 8 microseconds for the DW1000.
Quick preamble detection is obviously an asset in Flick, and not only in terms of latency. Quick detection shortens the total duration of the round, and energy consumption with it.
This offsets the relatively high consumption of the DW1000 chip compared to narrowband radios.
Reliability, latency, and energy consumption
How reliable is preamble detection across multiple hops, as done in Flick? This is the first question that needs to be answered to understand if our approach is feasible in practice. To do this, we needed a playground with many nodes, many links, and many hops. We exploited CLOVES, the largest public UWB testbed, installed at the University of Trento, Italy.
Across 10 hops, 78 nodes, and over 25 million detection attempts, Flick approaches 6-nines reliability with just 0.00024% false negatives. Since the decision is established based solely on preamble detection, and the radio can mistakenly detect a preamble that is not actually there, Flick may suffer from false positives as well. This happens in only 0.0032% of the cases, demonstrating that our approach is applicable in practice even in large networks.
For comparison, Glossy does not suffer from false positives, but false negatives happen more frequently than in Flick, 0.00031%.
The advantages of Flick with respect to Glossy become evident when we look at latency and energy consumption. In the time it takes Glossy to propagate a packet through one hop, roughly half a millisecond, Flick has crossed ten hops and reached the other side of the network. All while reducing consumption by 4.4× compared to Glossy. And it only gets better if there are multiple nodes that start the preamble flood!
We embedded Flick in Crystal and Weaver, two data collection protocols based on CTX. In both protocols, Flick is used at the start to signal if the network should remain active or enter sleep mode. In addition, Flick is exploited during the execution to replace the different termination procedures in Crystal and Flick, essentially asking the network “is there more data to collect?”.
We executed the original and Flick-enhanced protocols on CLOVES for a varying number of data packets to collect. When applied to an aperiodic data traffic profile, Flick abates energy costs by a 2× factor in Weaver, and by 2.5× in Crystal.
Flick can be embedded in other types of protocols as well. We already mentioned some interesting use cases, such as event-triggered control, and update distribution upon system changes. However, an intriguing opportunity is to use Flick directly at the application layer. Indeed, its main functionality is to establish a binary value across the entire network, effectively enabling the quick, reliable, energy-efficient execution of global boolean operators (OR and AND) across the entire network, a novel building block potentially enabling entirely new approaches to the design of low-power wireless distributed systems.
Authors: Gian Pietro Picco is currently a Professor with the Department of Information Engineering and Computer Science (DISI), University of Trento, Italy. His research interests include software engineering, middleware, and networking, and currently oriented toward wireless sensor networks, the Internet of Things and cyber-physical systems, mobile computing, and large-scale distributed systems. The research performed in his group combines theoretical study and in-field validation in real-world applications, and has led to several awards, including the Most Influential Paper from ICSE’07 (for a paper published a decade earlier) and the Best Paper Awards from IPSN, in 2009, 2011, and 2015; PerCom, in 2012; EWSN, in 2018; and IPIN, in 2019. He is an Associate Editor of ACM Transactions on Sensor Networks (TOSN), IEEE Transactions on Software Engineering (TSE), and the Pervasive and Mobile Computing Journal. He is also the founding Co-Editor-in-Chief of the ACM Transactions on Internet of Things (TIOT)
Disclaimer: Any views or opinions represented in this blog are personal, belong solely to the blog post authors and do not represent those of ACM SIGBED or its parent organization, ACM.