Allocation of Opportunistic Spectrum for Cognitive Radio Ad hoc Networks

Abstract

Cognitive Radios (CRs) address the problems of spectrum scarcity and under-utilization of the spectrum. However, realizing a CR network is neither easy nor straight-forward. The link layer in CR Ad hoc Networks is responsible for allocating suitable channels, out of the currently available channels. It is also responsible for setting up communication between nodes. Further, the spectrum efficiency should be maximized in a fair way. The problem of spectrum allocation can be modeled as a graph-theoretic problem. The selection of channels amongst the CR nodes in the network is an NP class problem. We prove this is, in fact, an NP complete problem. We propose a time-slotted system. In such a system, the schedule length needs to be kept to a minimum for higher spectrum utilization. We analyze the problem to determine conditions for an optimal allocation. We use edge coloring as a tool to analyze and propose heuristics. In ad hoc networks, distributed solutions are preferred due to the lack of infrastructure. We propose two distributed algorithms: (i) clique based, and (ii) localized heuristic algorithms. We compare the results of these heuristics with the algorithm proposed in literature. We also find the worst case bounds for these algorithms. For efficiency purposes, it is required to have a constant number of slots per frame. In such cases, producing a valid schedule is not enough since unfairness of allocation will eventually arise. To address this issue, we modify the edge coloring and clique based heuristics to produce valid fair schedules. Finally, we briefly consider the advantages of having a joint spectrum sensing-allocation scheme at the link layer. When the spectrum sensing scheme at the PHY layer is not completely reliable, a link layer scheme can help in reducing the false alarms and miss-detections. We, further constrain the system by limiting the number of channels that can be sensed within a frame. We present the spectrum utilization with this joint sensing-allocation policy.