On the complexity of connectivity in cognitive radio networks through spectrum assignment

Hongyu Liang (), Tiancheng Lou (), Haisheng Tan (), Yuexuan Wang () and Dongxiao Yu
Additional contact information
Hongyu Liang: IIIS, Tsinghua University
Tiancheng Lou: Google Inc.
Haisheng Tan: IIIS, Tsinghua University
Yuexuan Wang: IIIS, Tsinghua University
Dongxiao Yu: The University of Hong Kong

Journal of Combinatorial Optimization, 2015, vol. 29, issue 2, No 9, 472-487

Abstract: Abstract Cognitive Radio Networks (CRNs) are considered as a promising solution to the spectrum shortage problem in wireless communication. In this paper, we initiate the first systematic study on the algorithmic complexity of the connectivity problem in CRNs through spectrum assignments. We model the network of secondary users (SUs) as a potential graph, where two nodes having an edge between them are connected as long as they choose a common available channel. In the general case, where the potential graph is arbitrary and the SUs may have different number of antennae, we prove that it is NP-complete to determine whether the network is connectable even if there are only two channels. For the special case where the number of channels is constant and all the SUs have the same number of antennae, which is more than one but less than the number of channels, the problem is also NP-complete. For the special cases in which the potential graph is complete, a tree, or a graph with bounded treewidth, we prove the problem is NP-complete and fixed-parameter tractable when parameterized by the number of channels. Exact algorithms are also derived to determine the connectability of a given cognitive radio network.

Keywords: Computational complexity; Spectrum assignment; Connectivity; Cognitive radio networks (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9605-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:2:d:10.1007_s10878-013-9605-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9605-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().