### Technical Report No. 273 - Abstract

Amir Bannoura, Christian Ortolf, Christian Schindelhauer, and Leonhard Reindl
*The Wake Up Dominating Set Problem *

Recently developed wake-up receivers pose a viable alternative
for duty-cycling in wireless sensor networks. Here, a special radio
signal can wake up close-by nodes. We model the wake-up range by the
unit-disk graph. Such wake-up radio signals are very energy expensive
and limited in range. Therefore, the number of signals must be minimized.
So, we revisit the Connected Dominating Set (CDS) problem for unit-disk
graphs and consider an online variant, where starting from an initial node
all nodes need to be woken up, while the online algorithm knows only
the nodes woken up so far and has no information about the number and
location of the sleeping nodes.
We show that in general this problem cannot be solved effectively, since
a worst-case setting exists where the competitive ratio, i.e. the number
of wake-up signals divided by the size of the minimum CDS, is Θ(*n*) for *n* nodes. For dense random uniform placements, this problem can be
solved within a constant factor competitive ratio with high probability,
i.e. 1 - *n* ^{-c}.
For a restricted adversary with a reduced wake-up range of 1 - ε we
present a deterministic wake-up algorithm with a competitive ratio of
*O*(ε^{-1/2}) for the general problem in two dimensions.
In the case of random placement without any explicit position information
we present an *O*(log*n*)-competitive epidemic algorithm with high
probability to wake up all nodes. Simulations show that a simplified
version of this oblivious online algorithm already produces reasonable
results, that allows its application in the real world.

Report No. 273 (PDF)