Paper Info
Title
Complexity of Connectivity in Cognitive Radio Networks through Spectrum Assignment.
Abstract
Cognitive Radio Networks (CRNs) are considered as a promising solution to the spectrum shortage problem in wireless communication. In this paper, we address the algorithmic complexity of the connectivity problem in CRNs through spectrum assignment. We model the network of secondary users (SUs) as a potential graph, where if two nodes have an edge between them, they are connected as long as they choose a common available channel. In the general case, where the potential graph is arbitrary and 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 when 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 special cases that the potential graph is complete or a tree, we prove the problem is NP-complete and fixed-parameter tractable (FPT) when parameterized by the number of channels. Furthermore, exact algorithms are derived to determine the connectivity. © 2013 Springer-Verlag Berlin Heidelberg.
Year
DOI
Venue
2012
10.1007/978-3-642-36092-3-13
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Field
DocType
Volume
Parameterized complexity,Wireless,Computer science,Computer network,Communication channel,Algorithmic complexity,Economic shortage,Cognitive network,Cognitive radio,Special case
Conference
7718 LNCS
Issue
ISSN
Citations 
null
16113349
4
PageRank 
References 
Authors
0.39
11
5
Name
Order
Citations
PageRank
Hongyu Liang18416.39
Tiancheng Lou245519.49
Tan Haisheng318227.13
Yuexuan Wang438544.81
Dongxiao Yu536556.90