A new radio channel allocation strategy using simulated annealing and Gibbs sampling

Since the problem of optimal radio channel assignment (RCA) is NP-hard, the existing RCA algorithms have to use heuristic approaches for any networks of practical sizes. However, the algorithms suffer from two major issues, i.e., unable to consider the co-channel interference (CCI), and finding only sub-optimal assignment. In this work, we propose a new strategy to overcome the two challenging issues. (1) To consider CCI among neighboring head routers (HRs) and their terminals, we propose to choose the average effective channel utilization (ECU) of an HR as the basic objective function. The function can be also the sum of the average ECU, for which the optimization target is directly to maximize the overall throughput. (2) We propose to use the simulated annealing (SA) algorithm to find the optimal assignment and use the Gibbs sampling (GS) technique to convert the global optimization problem to a series of local optimization problems. In this way, we propose a distributed optimal assignment, i.e., SA-GS-based RCA (SRCA) algorithm. Our extensive simulation results have demonstrated that SRCA outperforms all the existing RCA algorithms in achieving global optimality with bounded CS.