On-Line Learning-Based Allocationof Base Stations and Channels in Cognitive Radio Networks

We consider the following fundamental problem of dynamic spectrum scheduling in cognitive radio networks. There are N secondary users, each of which gets access to a set of K channels through a collection of M base stations for data communications. Our aim is at addressing the so-called Joint Optimization of Base Station and Channel Allocation (JOBC) towards maximizing the total throughput of the users with the diverse uncertainties of the channels across different base stations and users. To serve this goal, we first investigate a simplified off-line version of the problem where we propose a greedy 1/M-approximation algorithm with the qualities of the channels assumed to be known. By taking the greedy off-line algorithm as a subroutine, we then propose an on-line learning-based algorithm by leveraging a combinatorial multi-armed bandit, which entails polynomial storage overhead and results in a regret (with respect to its off-line counterpart) logarithmic in time.