Radio channel allocations with global optimality and bounded computational scale

Ming Yu, Xiaoguang Ma, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

The radio channel assignment (RCA) in wireless networks is an optimization problem that is often found NP-complete. For networks of practical sizes, various heuristic algorithms are used to solve it. However, there are two major issues: finding a globally optimized solution without relying on specific interference models and estimating the computational complexity of general heuristic algorithms. In this paper, we propose a new simulated annealing (SA)-based RCA (SRCA) algorithm to find the globally optimized channel assignment in a distributed way but with bounded computational complexity. We propose using effective channel utilization (ECU) as the evaluation vector, whereas the objective function is to maximize the total ECU in a neighborhood. The ECU can be easily calculated by an access point (AP). The impact of interference is included in the ECU. We propose a hybrid method for estimating the algorithm's computational scale (CS), i.e., the number of channel reallocations until the network reaches a convergence state, by combining analytical and experimental methods. The resulting algorithm is a dynamic and distributed algorithm. Our extensive simulation results have demonstrated that it quickly achieves 99% of the global maximum with a chance over 95%, whereas its complexity is linear with the number of routers in the network.

Original languageEnglish (US)
Article number6766730
Pages (from-to)4670-4680
Number of pages11
JournalIEEE Transactions on Vehicular Technology
Volume63
Issue number9
DOIs
StatePublished - Nov 1 2014

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Aerospace Engineering
  • Electrical and Electronic Engineering
  • Applied Mathematics

Keywords

  • Gibbs sampling
  • radio channel allocation
  • simulated annealing (SA)
  • wireless networks

Fingerprint Dive into the research topics of 'Radio channel allocations with global optimality and bounded computational scale'. Together they form a unique fingerprint.

Cite this