Net Centric Optimization    (OPLINK::UMA)

      TIN2005-08818-C04-01 - Ministerio de Educación y Ciencia (Spain)
    Presentation Groups Publications Problems Software Meetings Collaborations Links Restricted Zone  
Presentation
Groups
Publications
Problems
Software
Meetings
Collaborations
Links
Restricted Zone
 
     > Problems > AFP
  
The Automatic Frequency Planning Problem
  
  

 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:

Date Score Reference
2007 88345 LUNA07
2008 86908 LUNA08a
2008 84234.5 CHAV08a
2008 83991.8 LUNA08b
2011 83815.7 CHAV11
2011 83725.6 SEGR11
2013 83340 SEGU13
2015 83280 SEGR14
2016 82994.9 SEGR16

Seattle Results:

Date Score Reference
2009 18123 MAXI09
2010 654.5 SEGU10
2011 564 SEGR11
2011 456 CHAV11
2016 349.3 SEGR16

 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.

  
  
Last Updated: 30/06/06                                          For any question or suggestion, click here to contact with us.
  
         Home Concact us Site Map