Coalesced CAP: an improved technique for frequency assignment in cellular networks

This paper presents an elegant technique for solving the channel assignment problem (CAP) for second generation (2G) cellular mobile networks, where channel allocation is made on a quasi-fixed basis and all sessions are connection oriented. It first maps a given CAP P to a modified coalesced CAP P´ on a smaller subset of cells of the network, which appreciably reduces the search space. This helps to solve the problem P´ by applying approximate algorithms very efficiently, reducing the computing time drastically. This solution to P´ is then used to solve the original problem P by using a modified version of the forced assignment with rearrangement (FAR) operation reported by Tcha et al. (IEEE Trans. Veh. Technol., vol. 49, p. 390, 2000). The proposed technique has been tested on well-known benchmark problems. It has produced optimal solutions for all cases with an improved computation time. For instance, it needs only around 10 and 20 s (on an unloaded DEC Alpha station 200 4/233) to get an optimal assignment for the two most difficult benchmark problems 2 and 6, respectively, with zero call blocking, in contrast to around 60 and 72 s (on an unloaded Sun Ultra 60 workstation) reported by Ghosh et al. Moreover, as a by-product of this approach, there remain, in general, many unused or redundant channels that may be used for accommodating small perturbations in demands dynamically.