Impact of constraints on the complexity and performance of channel assignment in multi-hop wireless networks

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)161-187
Number of pages27
JournalJournal of Cyber Security and Mobility
Volume1
Issue number2-3
StatePublished - 1 Apr 2012

Keywords

  • Graph coloring
  • NP
  • Scheduling
  • Set covering
  • Wireless ad-hoc networks

Fingerprint

Dive into the research topics of 'Impact of constraints on the complexity and performance of channel assignment in multi-hop wireless networks'. Together they form a unique fingerprint.

Cite this