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,
TU Hamburg-Harburg, Germany

[BeKi99]

TA(RWTH)

Threshold Accepting

Martin Hellebrandt, RWTH Aachen, Germany

[HeHe00]

TA(Siemens)

Threshold Accepting

Hans Heller,
Siemens AG, Germany

[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:

  • The total interference is the sum over all co- and adjacent-channel interference occurring between pairs of cells.
  • The co- and adjacent-channel interference is given in terms of the maximum, average (among the occurrences), and standard deviation of interference of each type. These figures are computed on the basis of the sum of the (two) directed interference predictions for pairs of cells.
  • The interference for TRXs is given in terms of the maximum, average (among the occurrences), and standard deviation as well. The basis is here the amount of the interference a TRX causes in and suffers from other cells.
  • The histogram of interference displays how many times the interference between two carriers exceeds the value of 1, 2, 3, 4, 5, 10, 15, 20, and 50% of affected cell area, respectively.

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


Last modified: Wed Mar 2 12:15:07 CET 2005 by the FAP web master (fapzib.de)