Maximizing Capacity in Cognitive Radio Networks under Physical Interference Model

Michael Brown, Colin Marshall, Dejun Yang, Ming Li, Jian Lin, Guoliang Xue

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


A fundamental problem in cognitive radio networks (CRN) is the following capacity maximization in CRN (CM-CRN) problem: given a set of primary links with a common transmitter, together with a set of secondary links, select a maximum cardinality subset of the links that can concurrently transmit successfully under the constraint that all primary links are selected. This problem is intrinsically different from the well-known link scheduling (LS) problem in wireless mesh networks, which does not have the constraint to select all primary links. In this paper, we make both theoretical and practical contributions to the CM-CRN problem. To achieve deep theoretical understanding of the problem, we show that CM-CRN is NP-hard and design a polynomial time approximation algorithm with a constant approximation ratio. In addition, we extend the designed algorithm to find approximate solutions to two variations of CM-CRN, one with the objective of maximizing the number of selected secondary links and the other with multiple primary users. To achieve good performance in practice, we design a simple but effective heuristic algorithm based on a greedy strategy. We also design an optimal algorithm based on integer linear programming, which serves as a benchmark for evaluating the performance of the approximation algorithm and heuristic algorithm, for problem instances of small sizes. Extensive evaluations show that our proved constant ratio of the approximation algorithm is considerably conservative and our heuristic algorithm produces results that are very close to the optimal solution. Our approximation algorithm for CM-CRN is motivated by and can be viewed as a non-trivial extension of the elegant approximation algorithm for the LS problem by Wan et al. to CRNs.

Original languageEnglish (US)
Article number7967737
Pages (from-to)3003-3015
Number of pages13
JournalIEEE/ACM Transactions on Networking
Issue number5
StatePublished - Oct 2017


  • Capacity maximization
  • approximation algorithms
  • cognitive radio networks
  • physical interference model

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Maximizing Capacity in Cognitive Radio Networks under Physical Interference Model'. Together they form a unique fingerprint.

Cite this