Complexity of Connectivity in Cognitive Radio Networks through Spectrum Assignment

Hongyu Liang, Tiancheng Lou, Haisheng Tan, Amy Yuexuan Wang, Dongxiao YuALGOSENSORS 2012 · DOI

TL;DR

This paper tackles the fundamental problem of ensuring network connectivity in Cognitive Radio Networks (CRNs) by analyzing the algorithmic complexity of spectrum assignment. The authors prove that determining network connectability is NP-complete in many general and even some restricted scenarios, but also provide efficient algorithms for specific cases, offering a comprehensive understanding of this critical challenge.

What Problem Does This Paper Address?

Cognitive Radio Networks (CRNs) are a promising solution to spectrum scarcity, allowing secondary users (SUs) to dynamically access unused licensed spectrum (white spaces). A key challenge in CRNs is ensuring reliable communication between SUs, which is complicated by the fact that available channels can vary spatially and temporally, and SUs may have multiple antennas. Unlike traditional networks where connectivity is primarily determined by distance and transmission power, in CRNs, SUs must also coordinate their spectrum usage. This paper addresses the core question: how complex is it to determine if a CRN can be made connected through intelligent spectrum assignment? They model this as a "potential graph" where an edge exists if two SUs could communicate, and a "realization graph" which shows actual communication links after spectrum assignment. The goal is to find an assignment that makes the realization graph connected.

Methods

The authors employ a combination of theoretical computer science techniques to analyze the problem:

  • NP-completeness proofs: They use reductions from known NP-complete problems (like SAT and Vertex Cover) to demonstrate that determining network connectability is computationally hard in general and in several specific cases.
  • Fixed-Parameter Tractability (FPT): For certain restricted scenarios (e.g., when the number of channels is small or the network structure has bounded treewidth), they show that the problem can be solved efficiently if a specific parameter (like the number of channels) is small, even if the network size is large.
  • Exact Algorithms: They develop algorithms that can determine connectability, though their runtime might be exponential in some parameters, they are often more efficient than brute-force enumeration.
  • Graph Theory Models: They utilize concepts like potential graphs, realization graphs, tree decompositions, and spectrum graphs to formally model and analyze the network connectivity problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and algorithmic design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Connectivity is Hard, Even with Few Channels: The most striking insight is that even when SUs have limited antenna budgets (e.g., 2 antennas) and there are only a few available channels (e.g., 2 or 3), determining network connectability remains NP-complete. This highlights the inherent difficulty of spectrum coordination for connectivity.
  • Structure Matters: While general graphs are hard, specific network structures like complete graphs, trees, or graphs with bounded treewidth offer some relief. For these structured networks, the problem becomes more tractable, especially when parameterized by the number of channels.
  • Parameterization is Key: The concept of fixed-parameter tractability is crucial. It shows that if certain parameters (like the number of channels or the treewidth of the network's potential graph) are small, efficient algorithms exist, making the problem solvable in practice for many realistic CRN deployments.
  • Bridging Theory and Practice: The paper provides a theoretical foundation for understanding the limits of spectrum assignment for connectivity and offers concrete algorithmic approaches that can guide practical system design.

Key Results

  • General Case: The SPECTRUM CONNECTIVITY problem is NP-complete even with only two channels and a limited number of antennas (β ≥ 2).
  • Special Cases (NP-complete):
    • For constant k > β ≥ 2 channels, the problem is NP-complete.
  • For complete potential graphs with β = 2, the problem is NP-complete.
  • For tree-like potential graphs, even with depth one, the problem is NP-complete.
  • Special Cases (Tractable/FPT):
    • If β = 1 or k < β, the problem is polynomial-time solvable.
  • For complete potential graphs, the problem is solvable in 2<sup>O(k)</sup>n<sup>O(1)</sup> time, and is fixed-parameter tractable when parameterized by the number of channels (k).
  • For tree-like potential graphs, an algorithm with runtime 2<sup>O(t)</sup>(kn)<sup>O(1)</sup> exists (where t is the max spectrum map size), and is FPT w.r.t. k.
  • For bounded treewidth graphs, an algorithm with runtime 2<sup>O(k)</sup>n<sup>O(1)</sup> is presented.

Limitations and Future Work

  • NP-Hardness: The paper establishes the NP-hardness of the problem in many scenarios, implying that finding optimal solutions for large, complex networks might be computationally infeasible.
  • Approximation Algorithms: The authors suggest that for applications where connectability is not strictly required but a large connected subset is desired, developing polynomial-time approximation algorithms for this optimization problem would be a valuable direction.
  • Low Antenna Budget: The problem of finding the minimum antenna budget (β) required for connectivity is mentioned as a generalization of the minimum-degree spanning tree problem, which is NP-hard. Further research into this area is suggested.
  • Distributed Algorithms: The paper calls for the design of distributed algorithms for achieving network connectivity, which is more realistic for large-scale CRNs.
  • Interference Models: Investigating distributed algorithms that jointly consider channel assignment, link scheduling, and realistic interference models is highlighted as an important future research avenue.

Summary updated

BibTeX
@inproceedings{liang2012complexity,
  author = {Hongyu Liang and Tiancheng Lou and Haisheng Tan and Amy Yuexuan Wang and Dongxiao Yu},
  title = {{Complexity of Connectivity in Cognitive Radio Networks through Spectrum Assignment}},
  booktitle = {ALGOSENSORS},
  year = {2012},
  doi = {10.1007/978-3-642-36092-3\_13},
}
Figure