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(logn)-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.