Technical Report No. 275 - Abstract

Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn, Calvin Newport
Maximal Independent Sets in Multichannel Radio Networks

We present new upper bounds for fundamental problems in multichannel wireless networks. These bounds address the benefits of dynamic spectrum access, i.e., to what extent multiple communication channels can be used to improve performance. In more detail, we study a multichannel generalization of the standard graph-based wireless model without collision detection, and assume the network topology satisfies polynomially bounded independence. Our core technical result is an algorithm that constructs a maximal independent set (MIS) in O(log² n/F)+Õ(log n) rounds, in networks of size n with F channels, where the Õ-notation hides polynomial factors in loglog n. Moreover, we use this MIS algorithm as a subroutine to build a constant-degree connected dominating set in the same asymptotic time. Leveraging this structure, we are able to solve global broadcast and leader election within O(D + log²n/F)+Õ(log n) rounds, where D is the diameter of the graph, and k-message multi-message broadcast in O(D + k + log²n/F)+Õ(log n) rounds for unrestricted message size (with a slow down of only a log factor on the k term under the assumption of restricted message size). In all five cases above, we prove:

1. our results hold with high probability (i.e., at least 1 - 1/n);
2. our results are within polyloglog factors of the relevant lower bounds for multichannel networks; and
3. our results beat the relevant lower bounds for single channel networks.
These new (near) optimal algorithms significantly expand the number of problems now known to be solvable faster in multichannel versus single channel wireless networks.