TY - GEN
T1 - Impact of constraints on the complexity of dynamic spectrum assignment
AU - Mathur, Chetan N.
AU - Haleem, M. A.
AU - Chandramouli, R.
AU - Subbalakshmi, K. P.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=67249146015&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67249146015&partnerID=8YFLogxK
U2 - 10.1109/GLOCOM.2008.ECP.607
DO - 10.1109/GLOCOM.2008.ECP.607
M3 - Conference contribution
AN - SCOPUS:67249146015
SN - 9781424423248
T3 - GLOBECOM - IEEE Global Telecommunications Conference
SP - 3164
EP - 3169
BT - 2008 IEEE Global Telecommunications Conference, GLOBECOM 2008
T2 - 2008 IEEE Global Telecommunications Conference, GLOBECOM 2008
Y2 - 30 November 2008 through 4 December 2008
ER -