Abstract In this paper, we address one of the issues in the frequency assignment problem for cellular mobile networks in which we intend to minimize the interference levels when assigning frequencies from a limited frequency spectrum. In order to satisfy the increasing demand in such cellular mobile networks, we use a hybrid approach consisting of a Particle Swarm Optimization (PSO) combined with a Tabu Search (TS) algorithm. This approach takes both advantages of PSO efficiency in global optimization and TS in avoiding the premature convergence that would lead PSO to stagnate in a local minimum. Moreover, we propose a new efficient, simple, and inexpensive model for storing and evaluating solution's assignment. The purpose of this model reduces the solution's storage volume as well as the computations required to evaluate these solutions in comparison with the classical model. Our simulation results on the most known benchmarking instances prove the effectiveness of our proposed algorithm in comparison with previous related works in terms of convergence rate, the number of iterations, the solution storage volume and the running time required to converge to the optimal solution.

About author: Houssem Eddine Hadji, is a Doctoral student in Badji Mokhtar University Annaba Algeria. The corresponding author. E-mail: houssem.hadji@gmail.com. Malika Babes, is a PhD in Computer Sciences and has been a Lecturer in the Department of Computer Science at Badji Mokhtar University, Annaba, Algeria. E-mail: malikababes@yahoo.fr.

Houssem Eddine Hadji,Malika Babes. Integrating Tabu Search in Particle Swarm Optimization for the Frequency Assignment Problem[J]. China Communications, 2016, 13(3): 137-155.

[1] Benameur L, Alami L, El Imrani. A hybrid discrete particle swarm algorithm for solving the fixed-spectrum frequency assignment problem. Int. J. of Computational Science and Engineering, 2010, 5(1): 68 - 73. [2] Hale W. K. Frequency assignment: theory and application. Proc. IEEE, 1980, 68: 1497-1514. [3] Cheng R-H, Yu C. W, Wu T-K. A Novel Approach to the Fixed Channel Assignment Problem. Journal of Information Science and Engineering, 2005, 21: 39-58. [4] A. Gamst and W. Rave. On frequency assignment in mobile automatic telephone systems. IEEE GLOBECOM. 1982: 309-315. [5] Guirguis L.A, Ghoneimy M.R.El. Channel Assignment for Cellular Networks Based on a Local Modified Hopfield Neural Network. Wireless Personal Communications, 2007,41(4): 539-550. [6] Parsapoor M, Bilstrup U. Ant Colony Optimization for Channel Assignment Problem in a Clustered Mobile Ad Hoc Network. Advances in Swarm Intelligence, Lecture Notes in Computer Science, 2013, 7928: 314-322. [7] R.Montemanni, Moon J.N.J and Smith D. H. An improved Tabu search algorithm for the fixed spectrum frequency assignment problem. IEEE Transactions on Vehicular Technology, 2003, 52(4): 891-901. [8] Alami J, El Imrani A. Using Cultural Algorithm for the Fixed-Spectrum Frequency Assignment Problem. Journal of Mobile Communication, 2008, 2(1): 1-9. [9] Liwei Lu, Rongshuang Fan. Simulated annealing algorithm in solving frequency assignment problem. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE), 20-22 Aug. 2010, 1:361-364. [10] Luna F, Estébanez C, León C, Chaves-González J, Nebro A, Aler R, Segura C, Vega-Rodríguez M, Alba E, Valls J, Mir,a C, Gómez-PulidoJ. Optimization algorithms for large-scale real-world instances of the frequency assignment problem. Soft Comput, 2011, 15(5): 975-990. [11] L.M. San José-Revuelta. A new adaptive genetic algorithm for fixed channel assignment. Information Sciences, 2007, 177(13): 2655-2678. [12] Ghosh S.C, Sinha B.P, and Das N. Channel Assignment Using Genetic Algorithm Based on Geometric Symmetry. IEEE Trans. Vehicular Technology, July 2003, 52(4): 860-875. [13] Acan A, altincay H, tekol Y, Unveren A, A genetic algorithm with crosser operators for optimal frequency assignment problem. Proceeding of the IEEE 2003 Congress on Evolutionary Computation, 2003, 256-263. [14] Ngo C. Y and Li V.O.K. Fixed channel assignment in cellular radio networks using a modified genetic algorithm. IEEE Trans. Veh.Technol, 1998, 47: 163-172. [15] Beckmann D, Killat U. A new strategy for the application of genetic algorithms to the channel-assignment problem. IEEE Trans. Veh. Technol., July 1999, 48: 1261-1269. [16] Eberhart RC, Kennedy J. A new optimizer using particle swarm theory. Proceedings of the sixth international symposium on micro machine and human science. IEEE service center. Piscataway, NJ, Nagoya, Japan, 1995, 39-43. [17] Talbi N, Bekarbi K. Fast Hybrid PSO and Tabu Search Approach for Optimization of a Fuzzy Controller. International Journal of Computer Science, 2011, 8(5): 215-219. [18] Zhang Y, Chen M. A Metaheuristic Approach for the Frequency Assignment Problem. Wireless Communications Networking and Mobile Computing (WiCOM), 2010. [19] Dai J, Chen M. Modified PSO algorithm for the FAP problem. Communication Technology (ICCT), 2010, 885-888. [20] Chakraborty G. An efficient heuristic algorithm for channel assignment problem in cellular radio networks. IEEE Trans. Veh. Technol., 50: 1528-1539. [21] Segura C, Segredo E, León C. Scalability and robustness of parallel hyperheuristics applied to a multiobjectivised frequency assignment problem. Soft Computing, 2013, 17(6): 1077-1093. [22] Audhya G.K, Sinha K, Mandal K, Dattagupta R, Ghosh S.C, Sinha B.P. A New Approach to Fast Near-Optimal Channel Assignment in Cellular Mobile Networks. IEEE TRANSACTIONS ON MOBILE COMPUTING, 2013, 12(9):1814-1827. [23] Battiti R, Bertossi A, and Cavallaro D. A randomized saturation degree heuristic for channel assignment in cellular radio networks. IEEE Trans. Veh. Technol. , 2001, 50: 364-374. [24] Funabiki N, Takefuji Y. A neural network parallel algorithm for channel assignment problems in cellular radio networks. IEEE Transactions on Vehicular Technology, 1992, 41: 430-436. [25] S. Ghosal, S.C. Ghosh. A Probabilistic Greedy Algorithm with Forced Assignment and Compression for Fast Frequency Assignment in Cellular Network. NCA 2014: 189-196. [26] S. C. Ghosh, B. P. Sinha and N. Das. Coalesced CAP : An improved technique for frequency assignment in cellular networks. IEEE Transactionon Vehicular Technology, March 2006, 55: 640-653. [27] X. Fu, A. G. Bourgeois, P. Fan, and Y. Pan. Using a genetic algorithm approach to solve the dynamic channel-assignment problem. Int. J. Mobile Communications, 2006, 4(3). [28] W. Wang and C. K. Rushforth. An adaptive local-search algorithm for the channel-assignment problem (CAP). IEEE Transaction on Vehicular Technology, August 1996, 45(3): 459-466. [29] H.E. Hadji, M. Babes. Accelerating the convergence of a modified Tabu Search algorithm using a new objective function for the frequency assignment problem. ICSCS 2013: 286-290. [30] Audhya G.K, Sinha K, Ghosh S.C and Sinha B.P. A Survey on the Channel Assignment Problem in Wireless Networks. Wireless Communications and Mobile Computing, 2011, 11(5): 583-609.