Frequency Assignment in Cellular Phone Networks
Please always quote using this URN: urn:nbn:de:0297-zib-3044
- We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice.
Author: | Ralf BorndörferORCiD, Andreas Eisenblätter, Martin Grötschel, Alexander Martin |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1997/07/11 |
Series (Serial Number): | ZIB-Report (SC-97-35) |
ZIB-Reportnumber: | SC-97-35 |
Published in: | Appeared in: Annals of OR 76 (1998), 73-93 |
DOI: | https://doi.org/10.1023/A:1018908907763 |