Metaheuristics for solving a real-world frequency assignment problem in GSM networks

ABSTRACT

The Frequency Assignment Problem (FAP) is one of the key issues in the design of GSM networks (Global System for Mobile communications), and will remain important in the foreseeable future. There are many versions of FAP, most of them benchmarking-like problems. We use a formulation of FAP, developed in published work, that focuses on aspects which are relevant for real-world GSM networks. In this paper, we have designed, adapted, and evaluated several types of metaheuristic for different time ranges. After a detailed statistical study, results indicate that these metaheuristics are very appropriate for this FAP. New interference results have been obtained, that significantly improve those published in previous research.

REFERENCES

• 1: K. I. Aardal, S. P. M. van Hoesen, A. M. C. A. Koster, C. Mannino, and A. Sassano. Models and solution techniques for frequency assignment problems. Annals of Operations Research, 153(1):79 -- 129, 2007.
• 2: S. Baluja. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning. 1994.
• 3: C. Blum and M. Dorigo. The hyper-cube framework for ant colony optimization. IEEE Trans. on System, Man, and Cybernetics -- Part B, 34(2):1161--1172, 2004.
• 4: Christian Blum , Andrea Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys (CSUR), v.35 n.3, p.268-308, September 2003 [doi>10.1145/937503.937505]
• 5: E.K. Burke and G. Kendall. Search methodologies: introductory tutorials in optimization and decision support techniques. Springer, 2005.
• 6: Janez Demšar, Statistical Comparisons of Classifiers over Multiple Data Sets, The Journal of Machine Learning Research, 7, p.1-30, 12/1/2006
• 7: A. Eisenblätter. Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds. PhD thesis, Technische Universität Berlin, 2001.
• 8: FAP Web. http://fap.zib.de/.
• 9: A. Furuskar, J. Naslund, and H. Olofsson. EDGE -- enhanced data rates for GSM and TDMA/136 evolution. Ericsson Review, (1), 1999.
• 10: F. W. Glover and G. A. Kochenberger. Handbook of Metaheuristics (International Series in Operations Research & Management Science). Springer, January 2003.
• 11: H. Granbohm and J. Wiklund. GPRS -- general packet radio service. Ericsson Review, (1), 1999.
• 12: W. K. Hale. Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497 -- 1514, 1980.
• 13: Y. Hochberg , A. C. Tamhane, Multiple comparison procedures, John Wiley & Sons, Inc., New York, NY, 1987
• 14: A. M. J. Kuurne. On GSM mobile measurement based interference matrix generation. In IEEE 55th Vehicular Technology Conference, VTC Spring 2002, pages 1965 -- 1969, 2002.
• 15: Manuel Laguna , Karen Price Hossell , Rafael Marti, Scatter Search: Methodology and Implementation in C, Kluwer Academic Publishers, Norwell, MA, 2002
• 16: Francisco Luna , Christian Blum , Enrique Alba , Antonio J. Nebro, ACO vs EAs for solving a real-world frequency assignment problem in GSM networks, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1276972]
• 17: R. Martí, M. Laguna, and F. Glover. Principles of scatter search. European Journal of Operational Research, 169(2):359--372, 2006.
• 18: A. R. Mishra. Fundamentals of Cellular Network Planning and Optimisation: 2G/2.5G/3G... Evolution to 4G, chapter Radio Network Planning and Optimisation, pages 21 -- 54. Wiley, 2004.
• 19: M. Mouly and M. B. Paulet. The GSM System for Mobile Communications. Mouly et Paulet, Palaiseau, 1992.
• 20: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 21: J. Rapeli. UMTS: Targets, system concept, and standardization in a global framework. IEEE Personal Communications, 2(1):30 -- 37, 1995.
• 22: D. J. Sheskin. Handbook of Parametric and Nonparametric Statistical Procedures. CRC Press, 2003.
• 23: M. K. Simon and M-S. Alouini. Digital Communication over Fading Channels: A Unified Approach to Performance Analysis. Wiley, 2005.
• 24: Bernhard H. Walke, Mobile Radio Networks: Networking and Protocols, John Wiley & Sons, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

General Terms:
Algorithms, Performance

Keywords:
automatic frequency planning, metaheuristics