Maximal independent sets in multichannel radio networks
Authors:
Open Access
- 22 July 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 335-344
Abstract
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(log2 n/F)+ Õ(logn) rounds, in networks of size n with F channels, where the Õ-notation hides polynomial factors in log log 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 + log2 n/F + Õ(logn) rounds, where D is the diameter of the graph, and k-message multi-message broadcast in O(D + k + log2 n/F}\big)+Õ(logn) 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: (a) our results hold with high probability (i.e., at least 1--1/n); (b) our results are within polyloglog factors of the relevant lower bounds for multichannel networks; and (c) 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.Keywords
This publication has 20 references indexed in Scilit:
- Efficient Symmetry Breaking in Multi-Channel Radio Networks2012
- Lower Bounds for Clear Transmissions in Radio Networks2006
- Maximal independent sets in radio networks2005
- Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs2005
- On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomizationJournal of Computer and System Sciences, 1992
- A lower bound for radio broadcastJournal of Computer and System Sciences, 1991
- A design concept for reliable mobile radio networks with frequency hopping signalingProceedings of the IEEE, 1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- On Broadcasting in Radio Networks--Problem Analysis and Protocol DesignIEEE Transactions on Communications, 1985