Technical Report No. 271 - Abstract

Sebastian Daum, Fabian Kuhn and Calvin Newport
Leader Election in Shared Spectrum Radio Networks

We investigate the complexity of basic symmetry breaking problems in multihop radio networks with multiple communication channels. We assume a network of synchronous nodes, where each node can be awakened individually in an arbitrary time slot by an adversary. In each time slot, each awake node can transmit or listen (without collision detection) on one of multiple available shared channels. The network topology is assumed to satisfy a natural generalization of the well-known unit disk graph model. We study the classic wake-up problem and a new variant we call active wake-up. For the former we prove a lower bound that shows the advantage of multiple channels disappears for any network of more than one hop. For the active version however, we describe an algorithm that outperforms any single channel solution. We then extend this algorithm to compute a constant approximation for the minimum dominating set (MDS) problem in the same time bound. Combined, these results for the increasingly relevant multi-channel model show that it is often possible to leverage channel diversity to beat classic lower bounds, but not always.