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
