A channel allocation algorithm for large scale cellular networks

Due to the insufficiency of available bandwidth resources and the continuously growing demand for cellular communication services, the channel assignment problem becomes increasingly important. To trace the optimal assignment, several heuristic strategies have been proposed. So far, most of them focus on the small-scale systems containing no more than 25 cells and they use an anachronistic cost model that does not satisfy the requirements of most existing cellular operators to measure the solution quality. Solving the small-scale channel assignment problems could not be applied into existing large scale cellular networks' practice. This article proposes a decomposition approach to solve the fixed channel assignment problem (FCAP) for large-scale cellular networks through partitioning the whole cellular network into several smaller sub-networks and then a sequential branch-and-bound algorithm is designed to solve the FCAP for them sequentially. The key issue of partition is to minimize the dependences of the sub-networks so that the proposed heuristics for solving smaller problems will suffer fewer constraints in searching better assignments. The experimental results show that the proposed algorithms perform well and we applied our algorithms in finding better assignments for the cellular network of the Taiwan Cellular Cooperation in ChungLi city.