Multiobjective Frequency Assignment Problem

Improving the assignment of radiocommunication frequencies in wireless networks

Coordinator/contact:

Esta dirección electrónica esta protegida contra spam bots. Necesita activar JavaScript para visualizarla
Esta dirección electrónica esta protegida contra spam bots. Necesita activar JavaScript para visualizarla

Introduction

A GSM (Global System for Mobile) network has several components, as shown in Fig. 1 that are grouped in three major systems: the Network and Switching SubSystem (NSS), the Base Station SubSystem (BSS), and the Operation and maintenance SubSystem (OSS). Regarding their functions, the Network and Switching SubSystem (NSS) is responsible for performing call processing and subscriber-related functions.

Figure 1: GSM architecture.

In our multiobjective formulation of FAP (Frequency Assignment Problem) the most relevant components are the antennas (BSS SubSystem), which are known as base transceiver stations (BTSs) and the transceivers (or TRXs). Transceivers are indeed the key element in the definition of the problem. A BTS contains a set of TRXs and they are organized in sectors. The physical equipment responsible for providing the communications between the mobile terminal and the GSM network are the TRXs. The number of TRXs installed inside each sector is fixed and it depends on the traffic demand which the sector where they are installed has to support.

The number of available frequencies (or channels) to be assigned to every TRX is very scarce. Therefore, the available frequencies need to be reused by many transceivers of the network. Hence, it is extremely important to make an adequate reuse of frequencies to the several TRXs, in such a way that significant interferences may be minimized. In the multiobjective formulation of FAP is extremely important to quantify the interferences provoked by an assignation of a frequency to a TRX and its influence on the remaining TRXs of the other sectors of the network. The separation cost also needs to be considered.

Interference cost

Interferences occur when frequencies are reused by several TRXs. Considering that T = {t1, t2, ..., tn} is a set of n TRXs, and let Fi = {fi1, ..., fik} ε N be the set of valid frequencies that can be assigned to a transceiver ti ε T, i = 1, ..., n (the cardinality of Fi could be different for each TRX). Furthermore, let S = {S1, S2, ..., Sm} be a set of given sectors (or cells) of cardinality m. Each transceiver ti ε T is installed in exactly one of the m sectors and is denoted as s(ti) ε S.

To quantify the interference cost, an interference matrix M is used, where each element M(i, j) represents the degradation of the network quality if sector i and j operate with the same frequency value, representing the co-channel interferences. Adjacent-channel interferences occur when two TRXs, in two different sectors, operate on adjacent channels (i.e., when one TRX operates on channel f and the other on channel f + 1 or f - 1).

The two elements µij and σij of a matrix entry M(i, j) = (µij, σij) represent the mean and standard deviation respectively of a Gaussian probability distribution used to quantify the interferences on the GSM network. Higher mean value corresponds to lower interferences or a better communication quality.

A solution to the problem p lies in assigning to all the TRXs a valid frequency (ti) from its domain (Fi). Thus, interference cost (to minimize) is accordingly defined as:

where, Csig computes the co-channel interferences (Cco) and the adjacent-channel interferences (Cadj) for all sector st and su, in which the transceivers t and u are installed, that is s(t) and s(u), respectively. In the following equation several conditions used are presented to obtain the Csig cost:

where K is a very large value, defined in the configuration files of the network. The K value makes it undesirable to allocate the same or adjacent frequencies to TRXs that are installed in the same sector. The Cco(µ,σ) denotes the cost due to co-channel interferences, whereas Cadj(µ,σ) is the adjacent-channel interference cost. The p(t) is the frequency assigned to transceiver t and p(u) is the frequency assigned to transceiver u.

Separation cost

Technical limitations in the construction of sectors and BTSs mean that certain combinations of TRX channel are not permitted. Consequently the constraints that arise include the following:

Site Channel Separation: Any pair of frequencies at a site (BTS) must be separated by a certain fixed amount, typically 2 channels for a large problem. If a BTS uses high power TRXs then its channel separation should be larger. The violation of this separation involves a cost (Csite). In our case, in order to calculate this cost we count the number of site channel separations that are violated by a proposed solution to the FAP.
Sector Channel Separation: This is similar to the previous one, but at sector level. In conclusion, any pair of frequencies at a sector must be separated by a certain fixed amount, typically 3 channels for a large problem. It is important to observe that the sector channel separation generally is larger than the site channel separation, due to the greater nearness of the involved TRXs. As in the previous case, the violation of the sector channel separation involves a cost (Csector). In our case, in order to compute this cost we count the number of sector channel separations that are violated by a proposed solution.

As a result of all the previously presented constraints, a solution p lies in assigning to all the TRXs of a network a valid frequency in order to minimize the following separation cost function:

References

"Multiobjective Metaheuristics for Frequency Assignment Problem in Mobile Networks with Large-Scale Real-World Instances". Marisa da Silva Maximiano, Miguel A. Vega-Rodríguez, Juan A. Gómez-Pulido, Juan M. Sánchez-Pérez. Engineering Computations, Volume 29, Issue 2, Emerald, Bingley, United Kingdom, 2012, pag:144-172, ISSN:0264-4401.
"Application of Differential Evolution to a Multi-Objective Real-World Frequency Assignment Problem", in: "Differential Evolution in Electromagnetics, Book Series: Adaptation Learning and Optimization". Marisa da Silva Maximiano, Miguel A. Vega-Rodríguez, Juan A. Gómez- Pulido, Juan M. Sánchez-Pérez. Springer-Verlag, Berlin Heidelberg, Germany, 2010, pag:155-176. ISBN:978-3-642-12868-4.
"Multiobjective Frequency Assignment Problem using the MO-VNS and MO-SVNS Algorithms". Marisa da Silva Maximiano, Miguel A. Vega-Rodríguez, Juan A. Gómez- Pulido, Juan M. Sánchez-Pérez. Proceedings of the World Congress on Nature and Biologically Inspired Computing, IEEE Computer Society, Coimbatore, India, 2009, pag:221-226. ISBN:978-1-4244-5612-3.
"Parameter Analysis for Differential Evolution with Pareto Tournaments in a Multiobjective Frequency Assignment Problem", in: "Intelligent Data Engineering and Automated Learning". Marisa da Silva Maximiano, Miguel A. Vega-Rodríguez, Juan A. Gómez-Pulido, Juan M. Sánchez-Pérez. Springer-Verlag, Berlin Heidelberg, Germany, 2009, pag:799-806. ISBN:978-3-642-04393-2.
"Optimization Algorithms for Large-Scale Real-World Instances of the Frequency Assignment Problem". Francisco Luna, César Estébanez, Coromoto León, José M. Chaves-González, Antonio J. Nebro, Ricardo Aler, Carlos Segura, Miguel A. Vega-Rodríguez, Enrique Alba, José M. Valls, Gara Miranda, Juan A. Gómez-Pulido. Soft Computing - A Fusion of Foundations, Methodologies and Applications, Volume 15, Issue 5, Springer, Berlin Heidelberg, Germany, 2011, pag:975-990, ISSN:1432-7643.
"Optimizing a Realistic Large-Scale Frequency Assignment Problem using a New Parallel Evolutionary Approach". José M. Chaves-González, Miguel A. Vega-Rodríguez, Juan A. Gómez-Pulido, Juan M. Sánchez-Pérez. Engineering Optimization, Volume 43, Issue 8, Taylor & Francis, London, UK, 2011, pag:813-842, ISSN:0305-215X.
"Comparative Analysis of a Hybrid DE Algorithm with the VNS Algorithm and its Variation SVNS to Solve a Real-World Frequency Assignment Problem". Marisa da Silva Maximiano, Miguel A. Vega-Rodríguez, Juan A. Gómez-Pulido, Juan M. Sánchez-Pérez. Applied Artificial Intelligence, Volume 25, Issue 3, Taylor & Francis, London, UK, 2011, pag:217-234, ISSN:0883-9514.