Optimization

ZIB  →  Discrete Methods  →  Optimization  →  Projects  →  Telecommunications  →  FAP

FAP

Frequency Assignment in Cellular Phone Networks

GSM network operators have only a very limited number of radio frequencies at their disposal. A frequency plan allocates frequencies to the base station antennas. Several antennas have to share the same frequency. A major challenge in setting up the frequency plan is to avoid, as much as possible, interference caused by reuse. The design and evaluation of automatic planning methods was the goal of this project.

path loss prediction

Scope

The operators of cellular phone networks are allowed to use a portion of the electro-magnetic radio spectrum for the radio communication with cellular phones. Networks operating according to the GSM standard use, among others, a frequency division multiple access scheme. The available portion of the radio spectrum is partitioned into slots of equal size, called channels. Radio links to cellular phones are established via stationary transceivers. Each transceiver uses a fixed channel, whereas cellular phones tune to the channel of the transceiver via which they are communicating.

A central problem in radio communication is that the signals of transceivers (and cellular phones) may be subject to interference. Interference usually comes from a near-by transceiver transmitting at the same or an adjacent channel. In practice, the number of transceivers in a cellular phone network exceeds the number of available channels by a factor of 30 or more. Thus, channels have to be reused often. Elaborate interference predictions are performed to determine for which pairs of transceivers the use of the same channel or adjacent channels would lead to interference.

Achievements

This project ended after almost 6 years. At first, we concentrated on the development of algorithms for the automatic generation of frequency-plans. The research was centered on the design and implementation of primal heuristics that minimize the interference. Substantial improvements could be achieved in comparison with previously used techniques [Ei01]. Some of the developed techniques have been in at E-Plus for years. In addition, the E-Plus licensed Cosiro to integrate the software in their radio interface planning tool Fun.

Like in 2000, in 2001 we focussed on methods for the computation of unavoidable interference. Together with Christoph Helmberg (Technical University of Chemnitz), we developed a method based on the solution of a semidefinte relaxation for the k-partition problem [Ei02]. This method provided the best lower bound achieved so far for the unavoidable co-channel interference. The results show that around half the interference that appears in the best frequency plans cannot be avoided. It can be shown that in most cases both lower and upper bound have to be improved further to close the gap between them. So far, such improvement could only be achieved by the use of significant computer power and computing time.

The internet server FAP web is operated since year 2000. Besides a description of frequency assignment problems, cf. [AaHoKoMaSa03], the server provides also practical test instances for research purposes. These are partly provided by the EU-sponsored COST-259 project [Co01]. These instances have been made available to the public via our server for the first time. Finally, an annotated bibliography on frequency assignment problems have been added to FAP web.

Publications

Miscellaneous

Poster