Logo image
Back
On the Complexity of Minimum Partition of Frequency-Agile Radio Networks
Conference proceeding

On the Complexity of Minimum Partition of Frequency-Agile Radio Networks

V.S.A Kumar, M.V Marathe, S.V Pemmaraju and I.A Pirwani
2008 3rd IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks, pp.1-10
10/2008
DOI: 10.1109/DYSPAN.2008.43

View Online

Abstract

New advances in cognitive radio technology, and the recent proposals for opening up the licensed spectrum bands raise new challenges for frequency allocation problems. In this paper, we study the clustering in frequency-agile radios problem (CFRP), which involves partitioning the network into the smallest number of connected clusters, where nodes within a cluster can communicate with a common frequency without creating interference to any primary user. This problem was formulated by Steenstrup (DySPAN '05) to model one-to-many broadcasts and Steenstrup's paper explored the empirical performance of greedy heuristics. In this paper, we focus on the formal computational complexity of this problem, and prove that it is NP-complete. Moreover, we show that it is unlikely that there exists a polynomial-time algorithm for this problem that always produces a solution (for n-vertex graphs) with at most In n times the optimal number of components. We show that several natural greedy heuristics, including the one studied by Steenstrup, can have highly sub-optimal performance in the worst case. For trees, we show that the optimum solution can be computed in polynomial time. There are instances where the number of components required is very large, if we require them to be strictly disjoint. We observe that in practice, allowing even a small amount of overlap among clusters significantly reduces the number of clusters needed. Motivated by this, we study a relaxation of the CFRP problem, that allows components to overlap, and study bicriteria approximations for this version of the problem, by simultaneously bounding the number of components and the average overlap between them. We present efficient algorithms that produce solutions with the cost related to both of these metrics being within a factor of O(log n) of the optimum. We end with simulations results for our algorithms on a wide range of instances.
 Approximation algorithms Approximation methods Clustering algorithms Interference Partitioning algorithms Polynomials Switches

Details

Metrics

13 Record Views
Logo image