Efficient Neighbor Discovery and Synchronization
in the Face of Intermittency
Overview
Due to their favorable size, cost, and sustainability battery-free devices are preferred in many
applications.
However, battery-free devices operate only intermittently since ambient energy sources such as
light, vibrations, and RF signals are often too weak to continuously power a device.
This work addresses the unsolved problem of efficient device-to-device communication in the face of
intermittency. We present FIND, the first neighbor discovery protocol for battery-free wireless
networks that uses randomized waiting to minimize discovery latency. We also introduce FLYNC, a new
hardware/software solution that taps into the powerline-induced flicker of widely used lamps to
synchronize indoor light harvesting devices, which we exploit to further speed up neighbor
discovery. Experiments with an open-source prototype built from off-the-shelf hardware components
show that our techniques reduce the discovery latency by 4.3x (median) and 34.4x (99th percentile)
compared to a baseline approach without waiting.
As the Internet of Things (IoT) grows to trillions of devices, sustainability and reliability of
this computing infrastructure become matters of utmost importance.
One possible path to sustainability is the adoption of battery-free devices that buffer energy
harvested from the environment in a capacitor. Battery-free devices promise to overcome the
drawbacks of (rechargeable) batteries, such as
bulkiness, wear-out, toxicity, uncertain remaining charge, etc.
Leaving batteries behind allows for building cheap, tiny, and maintenance-free devices that can be
embedded into smart textiles, intelligent surfaces, or even the human body.
What is intermittency?
The power that can be harvested from ambient energy sources can vary significantly across time and
space, and is often too weak to directly power a battery-free node. Thus, as illustrated in the
figure below, a battery-free device first needs to buffer sufficient energy in its capacitor before
it can operate for a short period of time; then the device turns off until the capacitor is
sufficiently charged again. As a result, battery-free devices operate intermittently.
Battery-free Communication
Just like in conventional battery-supported networks, direct communication between battery-free
devices is desirable, for example, to increase the availability of the system, to enable novel
applications, and to reduce infrastructure costs.
However, to communicate with one another, sender and receiver must be active simultaneously for at
least the airtime of one complete packet.
This is difficult in battery-free networks for three reasons:
Battery-free nodes can only become active when they have accumulated sufficient energy in their
capacitors.
They may only be active for a short period, which renders excessive sampling of the wireless
channel infeasible.
Their duty cycles are often low and may change unpredictably due to varying availability of
ambient energy.
The resulting key challenge is that the short activity phases of different nodes are generally
interleaved, as illustrated in the figure below. Therefore, it can take a very long time until nodes
encounter each other. And this is not a one-time endeavor: While nodes may attempt to synchronize their
activity phases at the first encounter, they lose track of time during extended periods without energy,
which forces them to re-synchronize.
What is FIND?
FIND is the first neighbor discovery protocol for battery-free wireless networks.
It empowers battery-free nodes to quickly discover each other's presence despite intermittent
operation and varying ambient energy availability.
It is agnostic as to how the nodes harvest energy (from solar, vibrations, RF, etc.) and as to
whether they communicate using backscatter or radio communication.
The design of FIND is based on the observation that the only way battery-free nodes can reliably
avoid interleaving is to not wake up and become active immediately after reaching the minimum energy
level required to do so.
Instead, FIND delays each wake-up for a random time according to an optimized probability
distribution. This breaks up the interleaving pattern and enables fast discovery as shown in the
figure below.
What is FLYNC?
Although FIND provides fast and energy-efficient neighbor discovery in battery-free networks,
discovery may still take a long time due to the low duty cycles if the ambient energy availability
is low. FLYNC can facilitate a 10x speed-up at an additional cost of only 5μW. The basic idea is
that neighboring nodes harvest energy from the same ambient source(s) and may
therefore have access to a common energy signal that can be used as a time reference. In combination
with FIND, nodes can exploit this common time reference to align their wake-ups, thereby increasing
the chances that nodes are active in the same slot, as illustrated in the figure below.
We implemented FLYNC for indoor light harvesting devices, exploiting the powerline-induced
brightness variations of lamps as a common energy/synchronization signal.
FLYNC is also applicable to battery-supported devices and useful for other purposes beyond speeding
up neighbor discovery.
Can I see FIND & FLYNC in action?
Open Source
We provide a Python implementation of the analytical FIND model, the hardware design
files of our battery-free node, and the corresponding firmware under an MIT license in our GitHub
repository.
FIND Python model
The provided code allows to calculate the probability for each node in a clique to become active in
any slot, the probability for any individual link to be discovered in any slot, and the
network discovery latency.
Installation
pip install neslab.find[examples]
Usage
Instantiate the model with a uniform distribution with scale 10 and three nodes with charging times
of 100, 125, and 200 slots, respectively:
import matplotlib.pyplot as plt
from neslab.find import Model
m = Model(10, "Uniform", [100, 125, 200], offset=0)
Plot the cdf of the discovery latency of the three links:
cdfs = m.cdf()
plt.plot(cdfs)
plt.show()
Print the network discovery latency:
lat = m.disco_latency()
print(f"Discovery latency: {lat} slots")
Hardware Design
We designed a battery-free wireless node implementing a circuit to extract a clock signal from
powerline-induced current variations of the solar panel current (FLYNC).
The node was designed using Eagle and we provide the corresponding schematics and layout files.
Firmware
The firmware running on our battery-free sensor node is written in C and uses protothreads. It
implements an efficient battery-free runtime, the phase-locked loop (PLL) to synchronize the local
clock to the output of the FLYNC circuit and the FIND neighbor discovery protocol. For detailed
instructions on how to build and flash the firmware, please refer to the README.
for (;;) {
/* Timestamp beginning of charging period */
int t_start = timer_now();
/* Wait until voltage reaches turn-on threshold */
pt_wait(pt, adc_read_vcap() > V2ADC(V_THR_ON));
int t_charge = timer_now() - t_start;
/* Maximum waiting time equals charging time */
int wait_time = dist_geom(lookup_scale(t_charge));
/* Wait for waiting time */
pt_event_t *clk_evt = timer_flync_wait(wait_time);
pt_wait(pt, pt_event_get(clk_evt));
discover_neighbors();
pt_event_t *pof_evt = pofwarn_request(V_THR_OFF);
if (disco_results_pop() != NULL) {
LED_ON();
}
while (!pt_event_get(pof_evt)) {
__NOP();
}
LED_OFF();
}
Bootstrapping Battery-free Wireless Networks: Efficient Neighbor Discovery in the Face of
Intermittency
K. Geissdoerfer and M. Zimmerling
USENIX Symposium on Networked Systems Design and Implementation (NSDI), Virtual, April
2021 [ pdf ]
Demo Abstract: Bootstrapping Batteryless Networks Using Fluorescent Light Properties
K. Geissdoerfer, F. Schmidt, B. Kusy, and M. Zimmerling
ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), Virtual,
April 2020 [ pdf ][ video ]
