Three Local Search Meta-Heuristics for the Minimum Interference Frequency Assignment Problem (MI-FAP) in Cellular Networks

Three Local Search Meta-Heuristics for the Minimum Interference Frequency Assignment Problem (MI-FAP) in Cellular Networks

Yasmine Lahsinat (LRIA-FEI- Computer Science Department, USTHB, BP 32 El-Alia Bab-Ezzouar, 16111, Algiers, Algeria), Dalila Boughaci (LRIA-FEI- Computer Science Department, USTHB, BP 32 El-Alia Bab-Ezzouar, 16111, Algiers, Algeria) and Belaid Benhamou (AIX-Marseille University (AMU), LIS, Domaine Universitaire de Saint Jérôme Avenue Escadrille Normandie Niemen 13397 Marseille Cedex 20, Marseille, France)
Copyright: © 2019 |Pages: 17
DOI: 10.4018/IJAMC.2019070107

Abstract

The minimum interference frequency assignment problem (MI-FAP) plays an important role in cellular networks. MI-FAP is the problem of finding an assignment of a small number of frequencies to a large number of transceivers (TRXs) that minimizes the interferences level. The MI-FAP is known to be NP-Hard, thus it cannot be solved in polynomial time. To remedy this, researchers usually use meta-heuristic techniques to find an approximate solution in reasonable time. Here, the authors propose three meta-heuristics for the MI-FAP: a variable neighborhood search (VNS) and a stochastic local search (SLS) that are combined to obtain a third and a new one, which is called VNS-SLS. The SLS method is incorporated into the VNS process as a subroutine in order to enhance the solution quality. All three proposed methods are evaluated on some well-known datasets to measure their performance. The empirical experiments show that the proposed method VNS-SLS succeeds in finding good results compared to both VNS and SLS confirming a good balance between intensification and diversification.
Article Preview
Top

1. Introduction

Managing the interferences in a radio network is a relevant issue considering that they can severely damage the quality of the communication. In this paper, we propose to study this issue with a related problem arising in a cellular radio network namely the Minimum Interference Frequency Assignment Problem. The MI-FAP is a well-known challenging combinatorial optimization problem. The issue is to assign a frequency to every transceiver of the network. The difficulties appear due to these two facts: the radio resource is scarce, and the tremendous number of transceivers distributed over the cell's network. Therefore, it is unavoidable to reuse the frequencies multiple times between the transceivers within the network. But this will cause interferences. Indeed, when stations in close geographical area use the same or adjacent frequency, interferences occur. To avoid this, it is necessary to assign frequencies to all the geographically close TRXs respecting some required separation constraints.

In a cellular radio network, the objective is then to assign frequencies to TRXs within the different cells in such a way to minimize the total interferences. It is worth recalling these two facts: the TRXs in the same cells cannot use the same frequency and some frequencies are not operational in some cells.

In this work, we consider the two major types of interferences:

  • The Co-channel interferences: these interferences appear when two geographically close TRXs use the same frequency (f);

  • The Adjacent-channel interferences: these interferences appear if two geographically close TRXs use neighboring (adjacent) frequencies (f+1, f-1).

In the eighties, Hale demonstrated that the considered problem is NP-hard. He proved that the MI-FAP is related to the graph-coloring problem (Hale, 1980). Therefore, the frequency assignment is an important and a complex task when planning a radio network. Considering the limited radio resource, the tremendous number of TRXs, a particular attention is given to achieve this task avoiding or at least minimizing the interferences.

The MI-FAP cannot be solved in polynomial time. Thus, using meta-heuristic techniques offers a good compromise to find approximate solutions for the problem in a reasonable time. Several meta-heuristics have been proposed in the literature. These methods have shown their ability to solve various problems through years. They had been used to handle scheduling problem (Taghavifard, 2012), bioinformatics problem (Zemali, 2016), big data (Benmounah, 2017) and many other problems. In this paper, we propose three meta-heuristic search methods for the MI-FAP. First, we adapt and study the effectiveness of the Variable Neighborhood Search (VNS) for the MI-FAP. Second, we propose a Stochastic Local Search (SLS) method for the MI-FAP. Finally, we propose to merge these two last methods in a new method which we called VNS-SLS. The new method VNS-SLS, includes the SLS method as a local search step to attempt to enhance the solution quality. Since VNS has good diversification properties, integrating SLS in it, will logically result in a good balance between intensification and diversification. We expect then that VNS-SLS will have this feature which is essential for producing good results. We note that collaborative and hybrid methods are worthwhile to ensure a success of optimization tools. There are tremendous works that used hybrid approaches to handle optimization problems. Among them, we mention some recent works (Wang, 2017), (Boucheham, 2017), (Abunaser, 2015).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing