Open AccessImpact of Constraints on the Complexity and Performance of Channel Assignment in Multi-Hop Wireless Networks
Author(s) -
Chetan Nanjunda Mathur,
M.A. Haleem,
K. P. Subbalakshmi,
R. Chandramouli
Publication year - 2012
Publication title -
journal of cyber security and mobility
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.198
H-Index - 9
eISSN - 2245-4578
pISSN - 2245-1439
DOI - 10.13052/jcsm2245-1439.1232
Subject(s) - computer science , hop (telecommunications) , channel (broadcasting) , wireless network , wireless , computer network , constraint (computer aided design) , channel allocation schemes , heuristic , wireless ad hoc network , mathematical optimization , computational complexity theory , assignment problem , algorithm , mathematics , telecommunications , geometry , artificial intelligence
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.