Impact of constraints on the complexity of dynamic spectrum assignment

Chetan N. Mathur, M. A. Haleem, R. Chandramouli, K. P. Subbalakshmi

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

In this paper we study the complexity of spectrum assignment problems in cognitive radio networks (CRNs) in the presence of several constraints. Although optimal spectrum assignment for secondary transmissions in CRNs is generally believed to be NP complete, the impact of fairness and link quality constraints on the hardness of the problem is not well studied. In this paper we show that when a minimum quality constraint is imposed on secondary transmissions, the spectrum assignment problem can be solved in polynomial time. However, such assignments may not guarantee fairness. We also show that when fairness is desired, even in the presence of quality constraints spectrum assignment problems remain NP complete. We then propose a tree pruning based algorithm to solve distance constrained spectrum assignment problem. We also discuss some heuristic techniques to solve fair distance constrained spectrum assignment problems in polynomial time.

Original languageEnglish
Title of host publication2008 IEEE Global Telecommunications Conference, GLOBECOM 2008
Pages3164-3169
Number of pages6
DOIs
StatePublished - 2008
Event2008 IEEE Global Telecommunications Conference, GLOBECOM 2008 - New Orleans, LA, United States
Duration: 30 Nov 20084 Dec 2008

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference

Conference

Conference2008 IEEE Global Telecommunications Conference, GLOBECOM 2008
Country/TerritoryUnited States
CityNew Orleans, LA
Period30/11/084/12/08

Fingerprint

Dive into the research topics of 'Impact of constraints on the complexity of dynamic spectrum assignment'. Together they form a unique fingerprint.

Cite this