ACO vs EAs for solving a real-world frequency assignment problem in GSM networks

ABSTRACT

Frequency planning is a very important task for current GSM operators. In this work we present a new mathematical formulation of the problem in which the frequency plans are evaluated by using accurate interference information coming from a real GSM network. We have developed an ant colony optimization (ACO) algorithm to tackle this problem. After accurately tuning this algorithm, it has been compared against a (1,10) Evolutionary Algorithm (EA). The results show that the ACO clearly outperforms the EA when using different time limits as stopping condition for a rather extensive comparison.

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. 4OR, 1(4):261--317, 2003.
• 2: 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, To appear, 2007.
• 3: Patrik Björklund , Peter Värbrand , Di Yuan, Optimized planning of frequency hopping in cellular networks, Computers and Operations Research, v.32 n.1, p.169-186, January 2005 [doi>10.1016/S0305-0548(03)00210-7]
• 4: C. Blum and M. Dorigo. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics - Part B, 34(2):1161--1172, 2004.
• 5: 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]
• 6: R. Borndörfer, A. Eisenblätter, M. Grötschel, and A. Martin. Frequency assignment in cellular phone networks. Annals of Operations Research, 76:73--93, 1998.
• 7: A. De Pasquale, N. P. Magnani, and P. Zanini. Optimizing frequency planning in the GSM system. In IEEE 1998 Int. Conf. on Universal Personal Communications, pages 293--297, 1998.
• 8: Marco Dorigo , Thomas Stützle, Ant Colony Optimization, Bradford Book, 2004
• 9: R. Dorne and J.-K. Hao. An evolutionary approach for frequency assignment in cellular radio networks. In Proc. of the IEEE Int. Conf. on Evolutionary Computation, pages 539--544, 1995.
• 10: A. Eisenblätter. Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds. PhD thesis, Technische Universität Berlin, 2001.
• 11: A. Eisenblätter, M. Grötschel, and A. M. C. A. Koster. Frequency planning and ramifications of coloring. Discussiones Mathematicae Graph Theory, 22(1):51--88, 2002.
• 12: FAP Web. http://fap.zib.de/.
• 13: A. Furuskar, J. Naslund, and H. Olofsson. EDGE - enhanced data rates for GSM and TDMA/136 evolution. Ericsson Review, (1), 1999.
• 14: H. Granbohm and J. Wiklund. GPRS - general packet radio service. Ericsson Review, (1), 1999.
• 15: W. K. Hale. Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497--1514, 1980.
• 16: N. Jaldén. Autonomous frequency planning for GSM networks. Master's thesis, Royal Institute of Technology, Stockholm, 2004.
• 17: 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.
• 18: F. Luna, E. Alba, A. Nebro, and S. Pedraza. Evolutionary algorithms for real-world instances of the automatic frequency planning problem in GSM networks. In 7th European Conf. on Evolutionary Computation in Combinatorial Optimisation, EVOCOP 2007, 2007 (to appear).
• 19: Vittorio Maniezzo , Antonella Carbonaro, An Ants heuristic for the frequency assignment problem, Future Generation Computer Systems, v.16 n.9, p.927-935, June 2000
• 20: 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.
• 21: J. N. J. Moon, L. A. Hughes, and D. H. Smith. Assignment of frequency lists in frequency hopping networks. IEEE Trans. on Vehicular Technology, 54(3):1147--1159, 2005.
• 22: Michel Mouly , Marie-Bernadette Pautet , Thomas Haug, The GSM System for Mobile Communications, Telecom Publishing, 1992
• 23: 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
• 24: J. Rapeli. UMTS: Targets, system concept, and standardization in a global framework. IEEE Personal Communications, 2(1):30--37, 1995.
• 25: S. Ruíz, X. Colet, and J. J. Estevez. Frequency planning optimisation in real mobile networks. In IEEE VTS 50th Vehicular Technology Conference, pages 2082--2086, 1999.
• 26: M. K. Simon and M-S. Alouini. Digital Communication over Fading Channels: A Unified Approach to Performance Analysis. Wiley, 2005.
• 27: B. H. Walke. Mobile Radio Networks: Networking, protocols and traffic performance. Wiley, 2002.

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:
ant colony optimization, evolutionary algorithms, frequency assignment