Distributed Heuristics for Allocating Spectrum in CR Ad hoc Networks

Cognitive Radios (CRs) address spectrum scarcity and under-utilization of the spectrum. However, realizing a CR network is neither easy nor straight-forward. In particular the link layer should facilitate setting up of communication between nodes enabling sharing of channels, while maximizing the spectrum utilization. We address the problem of allocation of channels to CR nodes. For time-slotted model, allocating the channels among CR nodes is an NP complete problem. We propose novel distributed heuristics, one based on clique sets called Clique Based Heuristic and the second one is a low complexity, locally adapting Localized Heuristic; both use local control channel. We compare the results of these heuristics with the optimal and a distributed graph coloring algorithm proposed in the literature. We also compare the spectrum utilization and overheads for all these algorithms.