Approximating the largest connected topology in cognitive radio networks

Connection between two secondary users (SUs) in cognitive radio networks (CRNs) is not only determined by their transmission power and distance, it also depends on the availability of a common channel for both SUs to open it for communication. In CRN, each SU is equipped with a number of antennas, denoted as β, which is the maximum number of channels that an SU can open simultaneously, known as antenna budget constraint. As each SU has a limit on the maximum number of channels it can open simultaneously, so network may not be connectable. But, it is desirable to connect the largest subset of SUs while minimizing the interference introduced due the nearby transmissions among SUs on the same channel, this problem is called the largest-connected minimum-interference topology control (LMTC) problem in CRNs. In this paper, we model the network of SUs as a potential graph PG=(V(PG),E(PG)), where V(PG) is set of SUs and E(PG) is set of potential edges. First, we show that the LMTC problem is NP-hard then we propose an approximation algorithm to address LMTC problem with min (m/log n, n.β/2log n) ratio, where n and m are the number of nodes and edges in potential graph respectively. We also propose a distributed algorithm called distributed-LMTC with message complexity O(n2), to address the LMTC problem. To address this NP-hard problem, we combine both topology control and channel assignment phase. In topology control phase, a network subgraph is derived with satisfying antenna budget constraints. In channel assignment phase, we assign channel to link to minimize interference. Simulation results show that the constructed topology can achieve higher connectivity and throughput than other competitive topology control algorithms.