EUROPEAN COOPERATION IN
THE FIELD OF SCIENTIFIC
AND TECHNICAL RESEARCH
EURO-COST
COST 259 TD (00) 44
Bergen, Norway, April 27-28, 2000
SOURCE: ZIB, E-Plus (Germany)
Benchmarking Frequency Allocation Strategies
Andreas Eisenblätter, Thomas Kürner
Abstract: This paper describes the results generated by COST 259 SWG 3.1 using the available frequency planning scenarios. Apart from the presentation of selected results the paper contains a detailed table of results for all available scenarios using the algorithms investigated within the project. The implementations of the different algorithms produce assignments with a recognisable spread in terms of the characteristics analysed. Nonetheless, all of them seem to be reasonable choices from a practical point of view.
Contact details:
Andreas Eisenblätter
Konrad-Zuse-Zentrum für Informationstechnik (ZIB)
Takustr. 7
D-14195 Berlin / Germany
Tel. ++49-30-84185-284
Fax ++49-30-84185-269
E-mail eisenblaetter_at_zib.de
Thomas Kürner
E-Plus Mobilfunk GmbH
Abt. Funknetzplanung
E-Plus-Platz
D-40468 Düsseldorf / Germany
Tel. ++49-211-448-4139
Fax ++49-211-448-4096
Mobile ++49-177-4484139
E-mail thomas.kuerner_at_eplus.de
1. Introduction
Many of the presently commercially available algorithms are already close to their limits when planning a GSM-system with few TRXs per cell. From the operators point of view, it is therefore pressing to support continued research and development in the area of automated frequency planning. For researches and developers, on the other hand, it is important to have realistic test problems available to check new ideas. That was the starting point for Subgroup 3.1. The goal was to establish a collection of planning scenarios, extracted from real-world or forecasted situations by network operators. This should give the opportunity to compare different algorithms on the same set of data, stimulate competition among developers of planning algorithms, and lead to significant improvements of the planning algorithms. The focus was predominantly on fixed (or static) frequency allocation for GSM-networks.
In the following, we document the scenarios supplied by network operators and give a (necessarily partial) evaluation of all contributed frequency assignments.
2. Available Scenarios
There are 32 planning scenarios available. The scenarios have been contributed from three sources, E-Plus Mobilfunk GmbH, Siemens AG, and Swisscom Ltd., in alphabetical order.
3. Contributed Assignments
At the time of writing, 115 assignments are available, with at least two assignments for every scenario. Thus, there is the opportunity to compare several planning methods on the basis of their results. Most of the employed planning methods are described in Section 4.2.4 of [COST00]. Table 1 introduces some acronyms to simplify notation, states the algorithmic principle of the methods, and gives references to the original literature.
Table 1: Sources of contributed assignments
Acronym |
Method |
Supplied by |
Reference |
DC5_IM(ZIB) |
"DSATUR with Costs" (5%) followed by "Iterated 1-Opt" |
Andreas Eisenblätter, ZIB, Germany |
[BEGM98] |
SA(Telefonica) |
Simulated Annealing |
Luis de Urries, Telefonica, Spain |
|
SA(TUHH) |
Simulated Annealing |
Dirk Beckmann, |
[BeKi99] |
TA(RWTH) |
Threshold Accepting |
Martin Hellebrandt, RWTH Aachen, Germany |
[HeHe00] |
TA(Siemens) |
Threshold Accepting |
Hans Heller, |
[HeHe00] |
U(Siemens) |
Unpublished |
Reinhard Enders, Siemens AG, Germany |
A number of characteristics are determined for each assignment. All of these characteristics together should allow a fair comparison of assignments for the same scenario. A sound comparison of the run-times is unfortunately not possible. In most cases the run-time is, in fact, not known. The following are rough estimates: DC5_IM(ZIB) and U(Siemens) typically compute an assignment within several minutes time, whereas all other methods from Table 2 typically have a run-time of a few to several hours on a modern PC. Notice also that results of particular implementations of heuristics are compared. Especially for the run-time intensive two local search heuristics considered here, namely, Simulated Annealing and Threshold Accepting, the produced frequency plans (and their quality) as well as the run-time (if not set explicitly) depend significantly on the implementation and on how much effort is spent in tuning the program.
The characteristics of the assignments presented for comparison are the following:
Figures 1 up to 4 show a selection of these characteristics for the assignments corresponding to the five bradford_nt-t-eplus scenarios with traffic factor t = 0, 1, 2, 4, 10. The full evaluation is contained in the Annex. The assignments computed using SA(TUHH), TA(RWTH), and TA(Siemens) give comparable results in terms of all evaluation criteria stated above. The only noteworthy difference can be observed in Fig. 4, where the number of carrier pairs with interference larger than 15% is displayed. TA(RWTH) shows worse results there. In comparison, the assignments computed by DC5_IM(ZIB) have up to 25% more interference in terms of the total as well as in terms of the maximum interference between two carriers. The picture is, however, reversed for the number of carrier pairs with interference more than 15%. DC5_IM(ZIB) produces noteworthy fewer occurrences of severe interference than the other three algorithms.
Figure 1: Total interference of various assignments for the bradford_nt-t-eplus scenarios
Figure 2: Maximum interference between a pair of carriers (TRX) of various assignments for the bradford_nt-t-eplus scenarios
Figure 3: Number of pairs of carriers with a mutual interference of more than 1 % for various assignments for the bradford-nt-t-eplus scenarios
Notice that only three assignments produced by SA(Telefonica) are available. None of these assignments is feasible. This seems to be caused by an error in the data conversion. The effect is that in case of an hand-over relation between two cells, a reduced minimum separation of 1 rather than 2 is imposed. Disregarding the infeasibility, the amount of incurred interference is consistent with results obtained by a SA implementation of ZIB using the same type of moves. In Fig. 5, the total interference for the scenarios siemens1, siemens2, siemens3, and siemens4 as well as Swisscom is shown. The assignments produced by the faster U(Siemens) method show a 20 to 25% higher total interference than the assignments produced by SA(TUHH), TA(RWTH), and TA(Siemens) implementations. The assignments are slightly inferior to those produced by SA(TUHH)
Figure 4: Number of pairs of carriers with a mutual interference of more than 15 % for various assignments for the bradford-nt-t-eplus scenarios
Figure 5: Total interference for Siemens�and Swisscom� scenarios. No assignment by U(Siemens) is available for the Swisscom scenario.
4. Conclusions
In summary, the following conclusion can be drawn. From our point of view, the activities of SWG 3.1 have met the expectations. The availability of a set of planning scenarios has significantly influenced the development of new planning algorithms and contributed to the exchange of ideas among the participators. The same algorithmic ideas were often implemented more than once and the impact of implementation choices became apparent.
The compared frequency assignments are produced by several implementations of frequency planning algorithms, see Table 1. Their common objective is to minimise the overall interference in a cellular network. A number of characteristical figures for all frequency plans are computed, among others, the amount of interference. A detailed listing of all these characteristics is contained in the Annex.
There are recognisable differences among the different approaches. All of them seem, however, to be reasonable choices from a practical point of view. Within the actual planning cycle, one may prefer a method like DC5_IM(ZIB) or U(Siemens) with shorter run-time for the frequency planning at intermediate stages, and produce the final assignment using something like TA(Siemens), spending several hours of computing time.
5. References
[Eis98] Eisenblätter, A., "Proposal: File Formats for the Standard Scenarios for Frequency Planning", COST 259, Temporary Document TD(98)048, Bern, Switzerland, Jan. 1998
[EKF98] Eisenblätter, A., Kürner, Th., Fauß, R., "Radio Planning Algorithms for Interference Reduction in Cellular Network", in Proc. COST 252/259 Joint Workshop, University of Bradford, 21-22 April 1998, pp. 87-92
[EKF99] Eisenblätter, A., Kürner, Th., Fauß, R., "Analysis of C/I Ratio Thresholds for Frequency Planning", COST 259, Temporary Document TD(99)012, Thessaloniki, Greece, Jan. 1999
[GGR97] Gotzner, R., Gamst, A., Rathgeber, R., "Spatial Traffic Distribution in Cellular Networks", 48th IEEE Veh. Techn. Conf., Ottawa, Canada, 1997, pp. 1994-1998
[Kürn99] Kürner,T., "Randomised Generation of Realistic Spatial Teletraffic Distributions for Frequency Planning Simulations", COST 259, Temporary Document TD(99)011, Thessaloniki, Greece, Jan. 1999.
[BEGM97] Borndörfer, R., Eisenblätter, A., Grötschel, M., Martin, A., "Frequency assignment in cellular phone networks", Annals of OR, Vol. 76, 1998, pp. 73-93
[BeKi99] Beckmannn, D., Killat, U., "Frequency Planning with respect to Interference Minimization in Cellular Radio Networks", COST 259, Temporary Document TD(99)032, Vienna, Austria, Jan. 1999
[HeHe00] Hellebrandt, M., Heller, H., "A New Heuristic Method for Frequency Assignment", COST 259, Temporary Document TD(00)003, Valencia, Spain, Jan. 2000
[COST00] COST 259 Final Report, chapter 4, April 2000
Annex : Detailed table of results for all scenarios