Taming Wheel of Fortune in the Air: An Algorithmic Framework for Channel Selection Strategy in Cognitive Radio Networks

Cognitive radio (CR) has been proposed to improve spectrum efficiency by taking advantage of the vacancies in primary channels. Since the frequency range of operation is very wide in a CR network (CRN) and, usually, CRs cannot scan all the channels simultaneously, one of the fundamental tasks for a CR is the channel selection strategy, which directly impacts its performance. In this paper, we present a distributed polynomial time algorithmic framework for computing channel strategies in a CRN with no assumption on the distribution followed by the primary users´ channel occupancy. For a secondary user (SU), the upper bound on the gap between the expected profit obtained at each time slot by using the global optimal strategy and the expected profit by using our algorithm is guaranteed to be arbitrarily small when the time horizon is sufficiently large. We also prove an upper bound on the gap between the expected profit by using any strategy sequence and the expected profit by using our strategy sequence.