Efficient Many-to-All Broadcast
in Dynamic Wireless Mesh Networks
Overview
Future applications in Cyber-Physical Systems and the Industrial Internet of Things rely on the fast and reliable many-to-all exchange of messages across dynamic wireless mesh networks: Sensors, actuators, and controllers may be attached to rotating, flying, or otherwise mobile entities, and fast feedback for closed-loop control and multi-agent coordination is required to keep up with the dynamics of physical processes. Mixer is a many-to-all broadcast primitive that satisfies this need. Experiments show that Mixer outperforms the state of the art by up to 3.8x and provides a reliability greater than 99.99% even at a node moving speed of 60 km/h (about 40 mph). Our Mixer implementation and a demo application are available as open source. For more details see here.
Getting Started
You may obtain the source code of Mixer, available under the BSD license for the ARM Cortex-M4 based nRF52840 DK and the TI MSP430 based Tmote Sky, from https://gitlab.com/nes-lab/mixer. This includes a simple demo application for you to get started playing around with Mixer.
For more details on Mixer's design and implementation, you may continue reading here or have a look at our publications.
Details
What is many-to-all broadcast and why is it important?
Many-to-all broadcast is a communication primitive whereby one, multiple, or all nodes can disseminate messages to every node in a wireless network. It is fundamental for a variety of network services and applications that involve multiple sources and multiple destinations. Examples include data replication in support of programming abstractions and fault-tolerance mechanisms, as well as closed-loop control and multi-agent coordination in Cyber-Physical Systems (CPS) and the Industrial Internet of Things (IIoT).
These applications rely on the fast and reliable many-to-all exchange of sizable messages across dynamic wireless mesh networks: The nodes may be attached to rotating, flying, or otherwise mobile entities, and fast feedback is required to keep up with the dynamics of physical processes (in the order of a few hundred milliseconds or less). However, existing many-to-all solutions do not satisfy these end-to-end latency requirements and scale suboptimally with the number of messages to be exchanged. For example, using sequential flooding, it takes O(MT) to exchange M messages, where T is the time needed to flood a single message. Although protocols like Glossy achieve the theoretically minimum T in real dynamic wireless mesh networks, the scaling with factor T becomes problematic as M increases.
What is Mixer?
Mixer is a new many-to-all broadcast primitive that supports the full spectrum from one-to-all to all-to-all communication and approaches the order-optimal scaling O(M+T) in real dynamic wireless mesh networks by considering all M messages together. That is, rather than performing M floods in sequence, Mixer overlays all M floods and simultaneously disseminates all M messages to every node in the network. To this end, Mixer nodes combine packets using random linear network coding (RLNC) and transmit random linear combinations of previously received packets. Moreover, Mixer integrates RLNC with synchronous transmissions in a clever way so that the constants hidden in O(M+T) become as small as possible.
Can I see Mixer in action?
The video clips below visualize Mixer’s operation during a real-world execution on the FlockLab testbed. Specifically, the animations show the behavior and status of all nodes in each slot during a Mixer round. Nodes with a bright green border are transmitting while nodes with a dark green border are receiving. The orange fill status of a node indicates its progress towards completion, and as soon as a node has decoded all messages it turns green. After that nodes shut down step by step, indicated by changing their color to blue.
The first video is an example for one-to-all communication. That is, initially node 1 has 27 messages that it wants to disseminate. After the execution of Mixer, every node has acquired all 27 messages from node 1.
You can download the video here and use your favorite media player to retrace the Mixer round slot by slot.
The second video is an example for all-to-all communication. That is, initially each of the 27 nodes has 1 message that it wants to disseminate. After the execution of Mixer, every node has acquired all 27 messages.
You can download the video here and use your favorite media player to retrace the Mixer round slot by slot.
What is Mixer's performance?
Mixer outperforms the state of the art in latency, goodput, and radio-on time. Results from real-world experiments show that Mixer improves performance by up to 3.8x compared with fine-tuned sequential Glossy floods, and provides a reliability greater than 99.99% even at a node moving speed of 60 km/h (about 40 mph). Mixer runs on commodity low-power devices and benefits from any physical layer that features the capture effect (e.g., BLE, 802.11, 802.15.4). For example, using 802.15.4 devices, Mixer achieves a goodput of up to 53.7 kbit/s and needs less than 290 ms to exchange 27 60-byte messages in an all-to-all fashion on the FlockLab testbed. Our microbenchmarks indicate that the same scenario would take less than 10 ms when running Mixer on 802.11 devices with a faster CPU. For detailed results have a look into our paper.
What does Mixer's API look like?
The core API of Mixer is very simple and consists of 5 steps:
At first, each node initializes Mixer:
mixer_init(node_id);
Those nodes that have one or more messages to be sent hand them over to Mixer before starting the round. As a prerequisite, the application must assign a unique index to each message.
mixer_write(index, msg, size);
Each node finalizes the preparation phase of Mixer. Thereafter, Mixer is ready to run immediately. The mode parameter defines the initiator of the round and controls the startup behavior of the corresponding node.
mixer_arm(mode);
Each node starts Mixer and waits until Mixer has finished.
mixer_start();
After the end of the Mixer round, each node can read out all messages.
Mixer: Efficient Many-to-All Broadcast in Dynamic Wireless Mesh Networks
Carsten Herrmann, Fabian Mager, Marco Zimmerling
ACM SenSys, Shenzhen (China), November 2018 [ pdf ][ slides ]
One for All, All for One: Toward Efficient Many-to-Many Broadcast in Dynamic Wireless Networks
Fabian Mager, Carsten Herrmann, Marco Zimmerling
ACM HotWireless (co-located with ACM MobiCom), Snowbird (UT, USA), October 2017 [ pdf ][ slides ]
Poster Abstract: All-to-all Communication in Multi-hop Wireless Networks with Mixer
Fabian Mager, Johannes Neumann, Carsten Herrmann, Marco Zimmerling, Frank Fitzek
ACM SenSys, Stanford (CA, USA), November 2016 [ pdf ][ poster ]