A Comparison of Existing Optimisation Techniques with the Univariate Marginal Distribution Algorithm for the Channel Assignment Problem

Abstract

The channel assignment problem has an important role to play in mobile telephone communication. Since the frequency band width is limited, the optimal assignment problem of channels has become increasingly  important. In this paper we give a review of methods that have been used to solve the channel assignment  problem and propose a new algorithm, namely the univariate marginal distribution algorithm. The existing  techniques that are described are the simulated annealing, graph colouring, neural networks, genetic  algorithms and tabu search. We discuss the drawbacks of each of these optimization techniques and we show how the proposed algorithm performs in terms of the number of generations required for convergence. We apply the univariate marginal distribution algorithm to a benchmark problem known as the Philadelphia problem or the 21-cell problem so that we can compare our simulation results. We consider a series of different problems by altering the channel assignment constraints, which are the co-channel constraint, the adjacent channel constraint and the co-site constraint. We show how the proposed technique also achieves the theoretical lower bounds in each of the cases.

Keywords: Channel Allocation, Estimation of Distribution Algorithms