Chase++: Fountain-Enabled Fast Flooding in
Asynchronous Duty Cycle Networks
Zhichao Cao
∗
, Jiliang Wang
∗
, Daibo Liu
†
, Xin Miao
∗
, Qiang Ma
∗
, Xufei Mao
‡
∗
School of Software and TNLIST, Tsinghua University, China
†
School of CSE, University of Electronic Science and Technology of China, China
‡
WIN Lab, Dongguan University of Technology, China
{caozc, jiliang, miao, maq}@greenorbs.com, {dbliu.sky, xufei.mao}@gmail.com
Abstract—Due to limited energy supply on many Internet of
Things (IoT) devices, asynchronous duty cycle radio management
is widely adopted to save energy. Flooding is a critical way to
quickly disseminate system parameters to adapt diverse network
requirements. Capture effect enabled concurrent broadcast is
appealing to accelerate network flooding in asynchronous duty
cycle networks. However, when the length of flooding payload
is long, due to frequently unsatisfied capture effect construction,
the performance of concurrent broadcast is far from efficient.
Intuitively, senders can send short packet that contains partial
flooding payload to keep the efficiency of concurrent broadcast.
In practice, we still face two challenges. Considering packet loss, a
receiver needs an effective way to recover entire flooding payload
from several received packets as soon as possible. Moreover,
considering diverse channel state of different senders, how a
sender chooses the optimal packet length to guarantee high
channel utilization in a light-weight way is not easy.
In this paper, we propose Chase++ a Fountain code based
concurrent broadcast control layer to enable fast flooding in asyn-
chronous duty cycle networks. Chase++ uses Fountain code to
alleviate the negative influence of the continuous loss of a certain
part of flooding payload. Moreover, Chase++ adaptively selects
packet length with the local estimation of channel utilization.
Specifically, Chase++ partitions long payload into several short
payload blocks, which are further encoded into many encoded
payload blocks by Fountain code. Then, with temporal and spatial
features of the sampled RSS (received signal strength) sequence,
a sender estimates the number of concurrent senders. Finally,
according to the estimated number of concurrent senders, the
sender determines the optimal number of encoded payload blocks
in a packet and assembles the encoded payload blocks as lots of
packets. Then, concurrent broadcast layer continuously transmits
these packets. Receivers can recover original flooding payload
after several independent encoded payload blocks are collected.
We implement Chase++ in TinyOS with TelosB nodes. We further
evaluate Chase++ on local testbed with 50 nodes and Indriya
testbed with 95 nodes. The improvement of network flooding
speed can reach 23.6% and 13.4%, respectively.
I. INTRODUCTION
More and more IoT applications have appeared in many
scenarios such as Industry 4.0 [1], smart city [2], smart
home and so on. In an IoT application, tens to thousands of
devices are used to collect sensory data. For the feasibility
of IoT deployment, some kinds of wireless techniques (e.g.,
Lora, ZigBee, Bluetooth, WiFi) are usually utilized to forward
packets. In sensory data collection, some system settings (e.g.,
radio management [3], time synchronization [4], binary image
[5]) of every node usually need timely update to adapt diverse
Receiver
Broadcaster
D
DCCA Preamble Packet
D D D D D
Listen Tail
sleep
interval
Fig. 1. Illustration of LPL radio management.
system requirements. Network flooding serves as the basic
function which disseminates control packets to every node in
whole network wide. During the update of system settings,
considering system reliability and consistency, the flooding
packet must be quickly forwarded to every node.
When nodes keep their radio always on, flooding becomes a
connected dominating set problem with the constraints of link
quality and conflict. Under this scenario, many structured [6]
[5] and structureless [7] [8] [4] network flooding protocols
have been widely adopted. However, due to the limited on-
board energy resource [9], duty cycle radio management is
widely used to save energy. Low Power Listening (LPL, e.g.,
Box-MAC [10], Zisense [11]) is a widely used asynchronous
duty cycle control mechanism. In LPL as shown in Figure 1,
each node periodically turns on its radio to sample signals
(i.e., Clear Channel Access (CCA)) with a preconfigured
interval (called sleep period). If a signal is detected, the
node further keeps its radio on for a while (call listen tail).
Otherwise, the radio is directly turned off. The schedule to
turn radio on (called sleep schedule) is not synchronized
among different nodes. To meet the rendezvous with every
neighbor, a broadcaster needs continuously send the same
packet (called preamble packet) for whole sleep period. The
significant difference (i.e., asynchronous sleep schedule, long
time channel occupation) between LPL broadcast and always
radio-on broadcast keeps the directly inherited LPL network
flooding schemes far from efficient.
To solve this urgent problem, Chase [12] has proposed a
capture effect based LPL concurrent broadcast to accelerate
network flooding. With Chase, each node can immediately
forwards the received flooding packet without any channel
access backoff. In this way, each node cannot miss the earliest
chance to receive flooding packet. Unfortunately, we observe
IEEE INFOCOM 2018 - IEEE Conference on Computer Communications
978-1-5386-4128-6/18/$31.00 ©2018 IEEE