|
Minimizing Interference In Frequency Assignment Problem Based On Guided Particle Swarm Optimization Algorithm
[Full Text]
AUTHOR(S)
Osman M. S. A., Zein EL din. R. A., Emam A. M.
KEYWORDS
Communication cells; Convergence rate; Frequency Assignment problem; Interference; Local minimum; Particle swarm optimization
ABSTRACT
This paper presents a modified approach based on Particle Swarm Optimization algorithm (PSO) for minimizing interference in Frequency Assignment Problem (FAP). This problem, known to be NP-hard, is to find an assignment of limited available frequencies for a number of communication cells. The main goal of the minimum interference FAP (MI-FAP) is to minimize the interference penalty cost provided in the solution. This cost related to the number of violated interference constraints, which predefined in interference matrix (IM). The modified algorithm named Guided search PSO (GPSO), which improve the particle location update strategy of the regular PSO to escape from local minimum. The proposed algorithm, enhance the convergence rate; robustness of the regular algorithm, and optimization stability of the search results. The computational efficiency and quality of the solutions obtained from the presented algorithm has been tested on well-known benchmark problems. The results obtained shows more efficiency than other results of previously related works.
REFERENCES
[1] Shi, F.，Xia, X., Chang, C., Xu, G., Qin, X., Jia Z., (2011), " An Application in Frequency Assignment Based on Improved Discrete Harmony Search Algorithm", International Conference on Advances in Engineering, Vol. 24, P.P.247-251.
[2] Pathak, N. R. (2014), "Channel Allocation in Wireless Communication using Genetic Algorithm", International Journal of Engineering and Innovative Technology (IJEIT), Vol. 4, No. 5, P.P. 161-164.
[3] Chen, X., Xu, J., Yuan, W., Liu, W., Cheng, W., (2013), "Channel Assignment in Heterogeneous Multi-Radio Multi-Channel Wireless Networks: A Game Theoretic Approach", International Journal of Computer Network, Vol.57, No.17, P.P.3291–3299.
[4] B.-H. Koo, H. B. Yilmaz, C.-B. Chae, H.-S. Park, J.-H. Ham, and P. S.-H. (2016) ,“Heuristics for frequency assignment problem with realistic interference constraints,” in Proc. of IEEE International Conference on Communications(ICC).
[5] Del Ser, J., Matinmikko, M., Gil-López, S., Mustonen, M. (2012), "Centralized and Distributed Spectrum Channel Assignment in Cognitive Wireless Networks: A Harmony Search Approach", Applied Soft Computing, Vol. 53, No.11-12, P.P.2108-2118.
[6] Lin, J-W., Lin, S-M. (2014), "A Weight-Aware Channel Assignment Algorithm for Mobile Multicast in Wireless Mesh Networks ", International Journal of Systems and Software, Vol.94, P.P.98–107.
[7] Wang, J., Cai, Y. (2015), "Multi objective evolutionary algorithm for frequency assignment problem in satellite communications", International Journal of Soft Computing, Vol. 19, No. 5, P.P.1229-1253.
[8] Yang, G., Wu, S., Jin, Q., Xu, J. (2016), "A Hybrid Approach Based on Stochastic Competitive Hopfield Neural Network a nd E f fic ient Genetic Algorithm for Frequency Assignment Problem", International Journal of Applied Soft Computing, Vol.39, No.7, P.P.104–116.
[9] Dorne, R., Hao, J.K. (1999), "Tabu search for graph coloring, T-colorings and set T-colorings", Meta-heuristics, P.P. 77–92.
[10] Lai, X., Hao, J.K. (2015), "Path relinking for the fixed spectrum frequency assignment problem", Expert Syst. Appl., V o l.42, No. 10, P.P.4755–4767.
[11] Montemanni, R., Moon, J.N.J., Smith, D.H. (2003), "An improved tabu search algorithm for the fixed spectrum frequency assignment problem", IEEE Transactions on Vehicle Technology, Vol.52, No.4, P.P.891–901.
[12] Montemanni, R., Smith, D.H. (2010), "Heuristic manipulation, tabu search and frequency assignment ", International journal of Computation and Operations Research, Vol.37, No.3, P.P.543–551.
[13] Luna, F., Blum, C., Alba, E., Nebro, A.J. (2007), "ACO vs EAs for solving a real-world frequency assignment problem in GSM networks", proceedings of Annual Conference on Genetic and Evolutionary Computation, P.P. 94–101.
[14] Tiourine, S.R., Hurkens, C.A.J., Lenstra, J.K. (2000), "Local Search Algorithms for the Radio Link Frequency A s s ignm ent P ro blem ", Telecommun. Syst., 13(2–4), P.P.293–314.
[15] Duque-Anton, M., Kunz, D., Ruber, B. (1993), "Channel assignment for cellular radio using simulated annealing", IEEE Transactions on Vehicle Technology, Vol. 42, No.1, P.P.14–21.
[16] Fischetti, M., Lepschy, C., Minerva, G., Romanin-Jacur, G., Toto, E. (2000), "Frequency assignment in mobile radio systems using branch-and-cut techniques", International European Journal of Operations Research, Vol.123, No.2, P.P.241–255.
[17] Alami, J., El Imrani, A. (2008), "Using cultural algorithm for the fixed-spectrum frequency assignment problem", International Journal of Mobile Communications, Vol2, No.1, P.P.1–9.
[18] Luna, F., Estebanez, C., Coromoto, L., Chaves-Gonzalez, J.M., Nebro, A.J., Aler, R., Segura, C., Vega -Rodriguez, M.A., Alba, E., V a lls , J.M., Miranda, G., Gomez Pulido, J.A. (2011), "Optimization algorithms for large-scale real-world instances of the frequency assignment problem", International Journal of software Computations, Vol.15, No.5, P.P.975–990.
[19] Mabed, H., Caminada, A., Hao, J.K. (2011), "Genetic tabu search for robust fixed channel assignment under dynamic traffic data ", Comput. Optim. Appl. Vol.50, No.3, P.P.483–506.
[20] Lahsinat, Y., Benhamou, B., Boughaci, D. (2015), "Trois hyper-heuristiques pour le problème d’affectation de fréquence dans un réseau cellulaire", In: 11th Journées Francophones de programmation par contraintes (JFPC), P.P.184–193.
[21] Audhya, G.K., Sinha, K., Mandal, K., Dattagupta, R., Ghosh, S.C., Sinha, B.P. (2013), "A new approach to fast near - optimal channel assignment in cellular mobile networks", IEEE Transactions of A Mobile Computations, Vol.12, No.9, P.P.1814–1827.
[22] Del Ser, J., Bilbao, M.N., Gil-Lopez, S., Matinmikko, M., Salcedo-Sanz, S. (2011) "Iterative power and subcarrier allocation in rate - constrained orthogonal multicarrier downlink systems based on hybrid harmony search heuristics ", Eng. Appl. Artif. Intell., Vol.24, No. 5, P.P.748–756.
[23] Wu, J., Dai, Y., Zhao, Y.C. (2013), "The effective channel assignments in cognitive radio networks", Comput. Commun. V o l. 71, No. 1, P.P.411–420.
[24] Lahsinat, Y., Boughaci, D., Benhamou, B. (2017) , "Harmony Search Based Algorithms for the Minimum Interference Frequency Assignment Problem", International Conference on Harmony Search Algorithm ICHSA, P.P. 179-189
[25] Anitha, Perumal, S. (2016), " Optimum Frequency Planning for Efficient Channel Utilization ", International Journal of Innovative Research in Computer and Communication Engineering, Vol. 4, No. 1, P.P.989-994.
[26] Kennedy J, Eberhart , RC., (1995), "Particle Swarm Optimization,” In: Proc.IEEE international conference on neura l net wo rks (P ert h, Australia), vol. IV. IEEE Service Center: Piscataway, NJ, P.P.1942–1948.
[27] Allouche, D., de Givry, S., Schiex, T. ( 2010), "Towards Parallel Non Serial Dynamic Programming for Solving Hard Weighted C S P ", Proceedings of 16th International Conference of Constraint Programming, Part of the Lecture Notes in Computer Science book series , Vol.6308, P.P. 53-60,Scotland.
[28] Sanchez, M., Allouche, D., De givry, S., Schiex,T. (2009), " Russian Doll Search with Tree Decomposition", International Joint Conference on Artificial Intelligence, P.P.603-609.
[29] Kolen, A. (2007), " A genetic algorithm for the partial binary constraint satisfaction problem: an application to a frequency assignment problem", International Journal of Statistica Neerlandica, Vol. 61, No.1, P.P.4-15.
[30] Pasechnik, D.V. (1998)" An interior point approximation algorithm for a class of combinatorial optimization problems: Implementation and enhancements", Technical report, Delft university of technology.
|
