Using Cluster Computing to Solve a Real-World FAP Problem

J.M. Chaves-González, D. Domínguez-González, M.A. Vega-Rodríguez, J.A. Gómez-Pulido, and M. Sánchez-Pérez (Spain)


FAP problem, cluster computing, island model, GSM networks, PBIL, frequency planning.


The frequency assignment problem (FAP) is a well known problem in Operations Research which includes different mathematical models. This importance comes from the relevance of frequency planning in current GSM operators. The FAP problem basically tries to minimize the number of interferences caused when a limited number of frequencies has to be assigned to a quite high number of transceivers. In this work, we focus on solving this problem for a realistic-sized, real-world GSM network using a parallelized version of the PBIL algorithm. PBIL (Population-Based Incremental Learning) is based on genetic algorithms and competitive learning, being a population evolution model based on probabilistic models. Using cluster computing, we have parallelized the PBIL algorithm fixed to the FAP problem, and the analysis of the results proves that we have reached a double goal: on the one hand, with the parallelized version of the algorithm, its execution time is reduced down to the optimum values; and on the other hand, we prove that using a distributed island model applied to PBIL, the results for the network planning are better than the ones obtained with the sequential version.

Important Links:

Go Back