TY - JOUR
T1 - Impact of constraints on the complexity and performance of channel assignment in multi-hop wireless networks
AU - Mathur, Chetan Nanjunda
AU - Haleem, M. A.
AU - Subbalakshmi, K. P.
AU - Chandramouli, R.
N1 - Publisher Copyright:
© 2013 River Publishers.
PY - 2012/4/1
Y1 - 2012/4/1
N2 - In this paper we systematically study several channel assignment problems in multi-hop ad-hoc wireless networks in the presence of several constraints. Both regular grids and random topology models are considered in the analysis. We identify three fairness constraints (unfair, fair, and 1-fair), Signal to Interference Ratio (SINR) constraint (to measure the link quality) and balance constraint (for uniform assignment) and study their impact on the complexity of the channel assignment problems. Note that these constraints have an impact on the network capacity, lifetime and connectivity. Although optimal channel assignment for links in a multi-hop wireless network has been shown to be NP complete, the impact of fairness, link quality and balance constraints on the hardness of channel assignment problems is not well studied. In this paper, we show that a class of unfair SINR constrained channel assignment problems can be solved in polynomial time. We show that when fairness is desired the channel assignment problems are NP Complete. We propose two heuristic algorithms that provide 1-fair and fair channel assignments, comment on their complexity and compare their performance with optimal solutions.
AB - In this paper we systematically study several channel assignment problems in multi-hop ad-hoc wireless networks in the presence of several constraints. Both regular grids and random topology models are considered in the analysis. We identify three fairness constraints (unfair, fair, and 1-fair), Signal to Interference Ratio (SINR) constraint (to measure the link quality) and balance constraint (for uniform assignment) and study their impact on the complexity of the channel assignment problems. Note that these constraints have an impact on the network capacity, lifetime and connectivity. Although optimal channel assignment for links in a multi-hop wireless network has been shown to be NP complete, the impact of fairness, link quality and balance constraints on the hardness of channel assignment problems is not well studied. In this paper, we show that a class of unfair SINR constrained channel assignment problems can be solved in polynomial time. We show that when fairness is desired the channel assignment problems are NP Complete. We propose two heuristic algorithms that provide 1-fair and fair channel assignments, comment on their complexity and compare their performance with optimal solutions.
KW - Graph coloring
KW - NP
KW - Scheduling
KW - Set covering
KW - Wireless ad-hoc networks
UR - http://www.scopus.com/inward/record.url?scp=85000402246&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85000402246&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85000402246
SN - 2245-1439
VL - 1
SP - 161
EP - 187
JO - Journal of Cyber Security and Mobility
JF - Journal of Cyber Security and Mobility
IS - 2-3
ER -