ERCIM News No.37 - April 1999

ARNO: Algorithms for Radio Network Optimization

by Heinz Mühlenbein

---

In the application-oriented project Algorithms for Radio Network Optimization (ARNO) the Breeder Genetic Algorithmis are used to solve optimization problems in the area of digital mobile telecommunication. The optimization problems include the Site Positioning Problem (SPP) and the Frequency Assignment Problem (FAP).

The SPP consists of the task to place antennas in the area where the mobile telecommunication network is developed. It is a very complex task, since many different factors influence the positioning of the antennas.

First of all, the developer must have information of the number and the distribution of the potential mobile services users. Also, the area has to be known from a geographic point of view. Usually, this information is available in the form of digital terrain data. Antennas have to be placed in such a way that users from the whole area may use the mobile services. Another task of the SPP is to predict the number of needed frequencies for each antenna to allow for a maximum number of users to be served simultaneously.

After the SPP task has been completed, the next step is finding an assignment of frequencies to the antennas (the FAP problem). The number of possible frequencies is limited and always much smaller than the total number of frequencies required in such a network.

Frequency Assignment Problem

The assignment of frequencies to the antennas must fullfill several requirements which reflect the following electromagnetic compatibility constraints:

• the co-site constraint: frequencies which are assigned to the same antenna have to respect a minimum distance with regard to the frequency spectrum
• the co-channel constraint: identical frequencies may be assigned but only to antennas which are a minimum distance from each other; otherwise, the frequencies would interfere with each other, making their use impossible
• the adjacent-channel constraint: same as the previous constraint, but for adjacent frequencies regarding the frequency spectrum.

Generally speaking, the FAP may be viewed as the task of assigning a number of available frequencies to a set of requesters, subject to a set of given constraints. The main goal of a FAP solution is to find an assignment that violates as few as possible constraints. Other usual goals are to find an assignment which uses a minimum number of different frequencies, or an assignment whose span (the difference between the smallest and the highest assigned frequency) is at a minimum.

The FAP is a NP-hard problem. The well known Graph Coloring Problem (GCP) is a special case of the FAP.

Cooperation Partners

Cooperation partners are France Telecom - Centre National d’Etudes des Telecommunications, University of Wales Cardiff - Department of Computer Science, GMD - German National Research Center for Information Technology, Laboratoire de Genie Informatique et d’Ingenierie de Production and Etude et Conseil en Techniques Informatiques Avancees.

Please contact:

Heinz Mühlenbein - GMD
Tel: +49 2241 14 2405
E-mail: muehlenbein@gmd.de