The optimization of channel assignment in cellular mobile networks is an NP-complete combinatorial optimization problem. For any reasonable size network, only sub-optimal solutions can be obtained by heuristic algorithms. In this paper, six channel assignment heuristic algorithms are proposed and evaluated. They are the combinations of three channel assignment strategies and two cell ordering methods. What we found are (i) the node-color ordering of cells is a more efficient ordering method than the node-degree ordering; (ii) the frequency exhaustive strategy is more suitable for systems with highly non-uniformly distributed traffic, and the requirement exhaustive strategy is more suitable for systems with less non-uniformly distributed traffic; and (iii) the combined frequency and requirement exhaustive strategy with node-color re-ordering is the most efficient algorithm. The frequency spans obtained using the proposed algorithms are much lower than that reported in the literature, and in many cases are equal to the theoretical lower bounds.

A new carrier based dynamic channel assignment for FDMA/TDMA cellular systems, called borrowing with directional carrier locking strategy, is proposed in this paper. When a call arrives at a cell and finds all voice channels busy, a carrier which consists of multiple voice channels can be borrowed from its neighboring cells for carrying the new call if such borrowing will not violate the cochannel interference constraint. Two analytical models, cell group decoupling analysis and phantom cell analysis, are constructed for evaluating the performance of the proposed strategy. Using cell group decoupling (CGD) analysis, a cell is decoupled together with its neigbors from the rest of the network for finding its call blocking probability. Unlike conventional approaches, decoupling enables the analysis to be confined to a local/small problem size and thus efficient solution can be found. For a planar cellular system with three-cell channel reuse pattern, using CGD analysis involves solving of seven-dimenional Markov chains. It becomes less efficient as the number of carriers assigned to each cell increases. To tackle this, we adopt the phantom cell analysis which can simplify the seven-dimensional Markov chain to two three-dimentional Markov chains. Using phantom cell analysis for finding the call blocking probability of a cell, two phantom cells are used to represent its six neighbors. Based on extensive numerical results, we show that the proposed strategy is very efficient in sharing resources among base stations. For low to medium traffic loads and small number of voice channels per carrier, we show that both analytical models provide accurate prediction on the system call blocking probability.