Description:

In GSM (Global System for Mobile Communications) networks the basic communication structure includes a set of base stations (BTS or Base Transceiver Station) located at several sites. Each BTS may have installed either an omni-directional antenna or several directional antennae called sectors (Figure 1). Devices which allow the transmission of radio signals are usually calles transceivers (TRX). Typically, each TRX has to be assigned with a frequency which carry the radio signal.

In general, the number of BTSs and, consequently, the number of TRXs needed to cover large areas, is much higher than the total number of available frequencies. Efficiently reusing these frequencies is, therefore, essential. Reusing generally provokes a reduction in the network performance due to interferences between TRXs. Two basic kinds of interferences are considered in the frequency planning: co-channel interferences, produced by TRXs using the same frequency, and adjacent channel, when TRXs operate with adjacent frequencies. Therefore, the problem relies in assigning the limited spectrum of frequencies available to all TRXs of the GSM network in order to maximize its performance, or, what is the same, minimize interferences. The input data include the network topology as well as the potential interferences between each pair of TRXs. Complexity NP-hard (generalization of graph colouring).

Figure 1: GSM network

 New Results 2016:

Denver Results:

Seattle Results:

 Resources:

Download source code here

Download instances here

 Basic Articles on the AFP Problem:

[SEGR16] Carlos Segura ; Arturo Hernandez ; Francisco Luna ; Enrique Alba. Improving Diversity in Evolutionary Algorithms: New Best Solutions for Frequency Assignment in IEEE Transactions on Evolutionary Computation , vol.PP, no.99, pp.1-1, 2016. Doi: 10.1109/TEVC.2016.2641477

[ALB2008] E. Alba, F. Luna, A.J. Nebro (2008), Applying Evolutionary Algorithms to Solve the Automatic Frequency Planning in GSM Networks, Handbook of Applied Algorithms

[LUN2007a] Francisco Luna, Christian Blum, Enrique Alba, Antonio J. Nebro: ACO vs EAs for solving a real-world frequency assignment problem in GSM networks. GECCO 2007: 94-101

[LUN2007b] Francisco Luna, Enrique Alba, Antonio J. Nebro, Salvador Pedraza: Evolutionary Algorithms for Real-World Instances of the Automatic Frequency Planning Problem in GSM Networks. EvoCOP 2007: 108-120


Click here to get the bibliography in txt format.