Article Preview
Top1. 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).