39 KAM Mathematical Colloquium
Prof. MARTIN GROETSCHEL
Konrad-Zuse-Centrum fuer Informationstechnik and Technische Universitaet Berlin
FREQUENCY ASSIGNMENT IN MOBILE PHONE SYSTEMS
February 1, 2001 Lecture Room S4, Charles University, Malostranske nam. 25, Praha 1 14:00 PM
Abstract
In mobile telecommunication systems a large number of communication links have to be established with a limited number of available frequencies (or channels). How should the channels be assigned to the transceivers so that the customers receive high quality service?In the early days of mobile telephony this channel assignment problem was modelled as an (ordinary) graph colouring problem, and colouring algorithms were used to solve it. Practical experience revealed that these solutions have a number of deficiencies.
A detailed analysis of this problem showed that a better way to formulate the channel assignment problem is the following: Obeying several technical and legal restrictions, channels have to be assigned to transceivers so that interference is as small as possible. It turns out that this problem can be considered as a list coloring problem with additional side constraints.
I will present several formulations of this problem as integer linear programs, I will outline a relaxation that leads to a semidefinite program, and I will discuss heuristic and exact algorithms for its solution. Computational results for channel assignment problems of a German cellular phone network operator will be presented.
This lecture is based on efforts of the ZIB telecommunications research group, in particular the work of Andreas Eisenblaetter and Arie Koster.
