On k-channel connectivity in cognitive radio networks through channel assignment

Cognitive radio network (CRN), forces the secondary users (SUs) to vacate the channel and switch to other unused channel when a primary user (PU) starts using its channel. Thus, the channels available for an SU vary over time depending on PU's activities. This temporal variation in channel availability can cause network partitioning, if there is no other available channel is present in the network which poses challenge among researchers “how to ensure robust connectivity in CRN?” A topology generated by a channel assignment is called k-channel connected if the nodes in the remaining topology can be connected when any set of (k-1) channels from channel set have been reclaimed by PUs and become unavailable to SUs. To the best of our knowledge, this is the first work on k-channel connectivity in CRN. We proved that this problem is NP-hard using c-colorability problem. To address this problem, we first present a polynomial time centralized algorithm, called Centralized k-channel Connected Spanning Subgraph (CCSSk), which use O(k2logn) approximation algorithm to find minimum cost subset k-connected subgraph problem as a subroutine. Based on CCSSk, we propose a distributed algorithm, called Distributed k-channel Connected Spanning Subgraph (DCSSk) with message complexity O(2n+n(1+Δ)+nlog2n), where n denotes the number of nodes and Δ is the maximum node degree in topology under maximum transmission power. Through simulations it has be observed that the proposed algorithms are able to preserve minimum energy paths and reduce the number of required channels efficiently to address the k-channel connected topology control problem. Simulation results also show that the CCSSk and DCSSk reduce the number of links by 55% and 45% respectively.