A Probabilistic Greedy Algorithm for Channel Assignment in Cellular Radio Networks

An important problem that arises in the design of cellular radio networks is the channel assignment problem that addresses the key issue of the scheduling of the transmissions of all stations in the network while avoiding interference. The problem consists of identifying a frame of minimum length that avoids interference while satisfying channel demands of the stations and maximizing channel utilization. The problem is known to be NP-hard and is formulated as a nonlinear integer program in prior research. This paper develops, for the first time, an integer programming formulation for the problem and presents a Probabilistic Greedy Algorithm that avoids the basic shortcoming of the classical greedy approach which is getting trapped in local optima. The algorithm incorporates simultaneously two diversification techniques, namely randomization and perturbation. Computational experiments are conducted on benchmark data sets and randomly generated problem instances with up to 500 stations. The results show the proposed algorithm is very effective in generating good solutions in short computing time. While a general-purpose branch-and-bound algorithm fails to find feasible solutions even for small instances, the proposed algorithm produces solutions that are far better than those obtained using a classical greedy approach in acceptable time.