Publications-Detail

Frequency Assignment in Cellular Radio using Genetic Algorithms

Authors:
Zürbes, S.
Book Title:
Proceedings of 13th Umbrella-Symposium "Optimization in Engineering"
Pages:
p.p. 11-12
Address:
Aachen University of Technology and Research Centre Jülich GmbH, Germany
Date:
Oct. 1996
Language:
English

Abstract

The frequency assignment problem in cellular radio is a combinatorial optimization problem. Due to communication traffic demands a certain number of carrier frequencies is required in each cell of the network. In cellular radio networks usually frequency re-use is realized, which means that the same carrier frequencies are used for radio transmission in several cells of a network. Hence cells using the same or adjacent carriers interfere with each other, therefore reducing the transmission quality. The aim of frequency assignment is to assign the carriers to the cells in such a way that the total spectrum required by the network does not exceed a given limit and the interference in all cells is as low as possible. In Genetic Algorithms the optimization methods of nature are imitated by computer simulation. The maximum of a function of a bit vector is searched. In terms of Genetic Algorithms the bit vector usually is called an individual, and the function determines the fitness of the individual. The optimization starts with a random set of individuals, called the parents generation. According to their fitness values, the bit vector values of normally two individuals (parents) are mixed at random positions (crossover and recombination), so that part of the information of both parents is contained in the new individual (child). Better individuals are given a higher probability to be used as parents. The bit vector of the child may be additionally disturbed by random changes of bits (mutation). By means of these procedures a set of new individuals is created, which is the children generation. According to a selection scheme, some members of the parents and children generations are used to form the next parent generation, and then the algorithm iterates. This scheme leads to fitter and fitter individuals over some generations, but prevents from being stuck in a local optimum. Applied to the frequency assignment problem, an individual is a bit vector that indicates which carriers are used in which cell. The fitness function determines how good a given assignment is in terms of interference or transmission quality. In contrast to other frequency assignment algorithms, the overall `transmission quality' can be defined with an arbitrary degree of real-world accuracy by using an appropriate fitness function. Realizations of suitable fitness functions for high-capacity cellular radio networks are given. Further frequency assignment and transmission quality results for exemplary GSM type networks are presented.

Download

BibTeX