A systematic methodology for channel assignment in mobile radio networks

The optimal assignment of radio channels to base stations, subject to bandwidth and other constraints, is a Non-Polynomial-Complete problem. The known exact solution approaches to the problem are strictly limited by the size of the problem to be solved. In order to solve optimally this problem, an efficient methodology is proposed in this paper. The underlying principle of the proposed methodology is to decompose an intractable Channel Assignment Problem into several small-size, weakly interconnected sub-problems. Each sub-problem so obtained is formulated as a Binary Integer Linear Programming (BILP) problem. The set of small-size BILP problems so developed is then solved using a sequential Branch and Bound algorithm. Experimental evaluations using benchmark problems confirm that the proposed methodology is capable of solving real-world Channel Assignment Problems with the theoretical guarantee of the solutions obtained.