A Graph-Theoretic Approach to Scheduling in Cognitive Radio Networks - Gözüpek, Didem; Shalom, Mordechai; Alagoz, Fatih (IEEE-Inst Electrical Electronics Engineers Inc, 2015)
We focus on throughput-maximizing, max-min fair, and proportionally fair scheduling problems for centralized cognitive radio networks. First, we propose a polynomial-time algorithm for the throughput-maximizing scheduling problem. We then elaborate on certain special cases of this problem and explore their combinatorial properties. Second, we prove that the max-min fair scheduling problem is NP-Hard in the strong sense. We also prove that the problem cannot be approximated within any constant factor better than 2 unless P = NP. Additionally, we propose an approximation algorithm for the max-min fair scheduling problem with approximation ratio depending on the ratio of the maximum possible data rate to the minimum possible data rate of a secondary users. We then focus on the combinatorial properties of certain special cases and investigate their relation with various problems such as the multiple-knapsack, matching, terminal assignment, and Santa Claus problems. We then prove that the proportionally fair scheduling problem is NP-Hard in the strong sense and inapproximable within any additive constant less than log(4/3). Finally, we evaluate the performance of our approximation algorithm for the max-min fair scheduling problem via simulations. This approach sheds light on the complexity and combinatorial properties of these scheduling problems, which have high practical importance in centralized cognitive radio networks.
Keywords: Algorithmic graph theory; approximation algorithms; cognitive radio networks; dynamic spectrum access; resource allocation; scheduling