Heuristic Algorithms for Underlay Spectrum Sharing in Cognitive Radio Networks

Cognitive radio is the enabling technology that allows the design of dynamic spectrum sharing algorithms that makes unlicensed users able to use frequency bands owned by license holders. Hence, this technology can be considered as the perfect candidate to enhance the spectrum allocation for the next generation of wireless networks. In this paper, we propose two low complexity heuristic algorithms for dynamic spectrum sharing in cognitive radio networks assuming the spectrum underlay paradigm. We mean by spectrum underlay a wireless system where primary and secondary users can transmit simultaneously on the same frequency bands at the condition that the interference perceived by the primary receivers is kept below a determined threshold. The formulated spectrum sharing is shown to be equivalent to a variant of knapsack problems which is \({\mathcal {NP}}\)-hard. Therefore, resolving the tradeoff between computational complexity and system performance is the main concern in the design of the proposed algorithms. The first algorithm is based on a graph-theory. First, the cognitive radio network is modeled as an undirected weighted graph. The spectrum sharing problem is then reduced to the one of finding a sensitive vertex coloring of a subgraph on the constructed graph. The second algorithm involves the use of genetic algorithms and uses a mixed integer coding. We show that the proposed algorithms reduce considerably the computational complexity of finding a near optimal solution.