[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

A permutation-coded evolutionary strategy for multi-objective GSM network planning

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

The base station placement problem, with n potential candidate sites is NP-Hard with 2n solutions (Mathar and Niessen, Wirel. Netw. 6, 421–428, 2000). When dimensioned on m unknown variable settings (e.g., number of power settings + number of tilt settings, etc.) the computational complexity becomes (m+1)n (Raisanen, PhD. thesis, 2006). We introduce a novel approach to reduce the computational complexity by dimensioning sites only once to guarantee traffic hold requirements are satisfied. This approach works by determining the maximum set of service test points candidate sites can handle without exceeding a hard traffic constraint, T MAX . Following this, the ability of two evolutionary strategies (binary and permutation-coded) to search for the minimum set cover are compared. This reverses the commonly followed approach of achieving service coverage first and then dimensioning to meet traffic hold. To test this approach, three realistic GSM network simulation environments are engineered, and a series of tests performed. Results indicate this approach can quickly meet network operator objectives.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Akl, R.G., Hedge, M.V., Naraghi-Pour, M., Min, P.S.: Multicell cdma network design. IEEE Trans. Veh. Technol. 50, 711–722 (2001)

    Article  Google Scholar 

  • Amaldi, E., Capone, A., Malucelli, F.: Improved models and algorithms for UMTS radio planning. In: Proceedings 54th IEEE Conference on Vehicular Technology, vol. 2, pp. 920–924 (2001a)

  • Amaldi, E., Capone, A., Malucelli, F.: Optimizing base station siting in UMTS networks. In: Proceedings 53rd IEEE Conference on Vehicular Technology, vol. 4, pp. 2828–2832 (2001b)

  • Anderson, H.R., McGeehan, J.P.: Optimizing microcell base station locations using simulated annealing techniques. In: Proceedings 44th IEEE Conference on Vehicular Technology, pp. 858–862 (1994)

  • Berny, A., Sarzeud, O.: Optimization de resaux de radiotelephonie mobile par recherche locale et selection. JNCP, Marseille, France, 953–966 (2000)

  • Calegari, P., Guidec, F., Kuonen, P., Wagner, D.: Genetic approach to radio network optimizations for mobile systems. In: Proceedings 47th IEEE Conference on Vehicular Technology, vol. 2, pp. 755–759 (1997)

  • Chamaret, B., Josselin, S., Kuonen, P., Pizarroso, M., Salas-Manzanedo, B., Ubeda, S., Wagner, D.: Radio network optimization with maximum independent set search. In: Proceedings of the IEEE VTC’97 Conference, Phoenix, AZ, May 1997, pp. 770–774

  • Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester (2001)

    MATH  Google Scholar 

  • Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. In: Lecture Notes in Computer Science, vol. 1917, pp. 849–858 (2000)

  • Galota, M., Glasser, C., Reith, S., Vollmer, H.: A polynomial-time approximation scheme for base station positioning in UMTS networks. In: Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Rome, Italy, July 2001, pp. 52–59

  • Ganz, A., Krishna, C.M., Tang, D., Haas, Z.J.: On optimal design of multiter wireless cellular systems. IEEE Commun. Mag. 16(5), 88–93 (February 1997)

    Article  Google Scholar 

  • Han, J.K., Park, B.S., Choi, Y.S.: Genetic approach with a new representation base station placement in mobile communications. In: Proceedings 54th IEEE Conference on Vehicular Technology, vol. 4, pp. 2703–2707 (2001)

  • Hata, M.: Empirical formula for propagation loss in land mobile radio services. IEEE Trans. Veh. Technol. 29(3), 317–325 (1980)

    Article  MathSciNet  Google Scholar 

  • Huang, X.: Automatic cell planning for mobile network design: optimization models and algorithms. Ph.D. thesis, Universität Karlsruhe (2001)

  • Huang, X., Behr, U., Wiesbeck, W.: Automatic cell planning for a low-cost and spectrum efficient wireless network. In: Proceedings of Global Telecommunications Conference (GLOBECOM), vol. 1, pp. 276–282 (2000)

  • Ibbetson, L.J., Lopes, L.B.: An automatic base station placement algorithm. In: Proceedings of the IEEE VTC’97 Conference, Phoenix, AZ, May 1997, pp. 770–774

  • Julstrom, B.A., Raidl, G.R.: A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In: 2003 Genetic and Evolutionary Computation Conference’s Workshops Proceedings, Workshop on Analysis and Design of Representations, pp. 2–7 (2003)

  • Laki, I., Farkas, L., Nagy, L.: Cell planning in mobile communication systems using sga optimization. In: Proceedings of International Conference on Trends in Communications, vol. 1, pp. 124–127 (2001)

  • Lee, C.Y., Kang, H.G.: Cell planning with capacity expansion in mobile communications: a tabu search approach. IEEE Trans. Veh. Technol. 49(5), 1678–1691 (March 2000)

    Article  Google Scholar 

  • Mathar, R.M., Niessen, T.: Optimum positioning of base stations for cellular radio networks. Wirel. Netw. 6, 421–428 (2000)

    Article  MATH  Google Scholar 

  • Mathar, R.M., Schmeink, M.: Optimal base station positioning and channel assignment for 3G mobile networks by integer programming. Ann. Oper. Res. 107, 225–236 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  • Meunier, H., Talbi, E., Reininger, P.: A multiobjective genetic algorithm for radio network optimization. In: Proceedings of the 2000 Congress on Evolutionary Computation, vol. 1, pp. 317–324 (2000)

  • Molina, A., Athanasiadou, G.E., Nix, A.R.: The automatic location of base-stations for optimised cellular coverage: a new combinatorial approach. In: Proceedings of the IEEE VTC’99 Conference, pp. 606–610 (1999)

  • Molina, A., Athanasiadou, G.E., Nix, A.R.: Optimised base-station location algorithm for next generation microcellular networks. Electron. Lett. 36(7), 668–669 (2000)

    Article  Google Scholar 

  • Raisanen, L.: Multi-objective site selection and analysis for GSM cellular network planning. Ph.D. thesis, Cardiff University (2006)

  • Reininger, P., Caminada, A.: Model for gsm radio network optimization. Presented at the 2nd ACM Int. Conf. Discrete Algorithms and Methods for Mobility, Dallas, Texas, a

  • Reininger, P., Caminada, A.: Connectivity management on mobile network design. Presented at the 10th Conf. Eur. Consortium for Mathematics in Industry, Goteborg, Sweden, b

  • Reininger, P., Iksal, S., Caminada, A., Korczak, J.J.: Multi-stage optimization for mobile radio network planning. In: Proceedings of the IEEE VTC’99 Conference, vol. 3, pp. 2034–2038 (1999)

  • Tcha, D.-W., Myung, Y.-S.: Base station location in a cellular cdma system. Telecommunication Syst. 14, 163–173 (2000)

    Article  MATH  Google Scholar 

  • Tutschku, K.: Interference minimization using automatic design of cellular communication networks. In: Proceedings of the IEEE VTC’98 Conference, pp. 634–638 (1998)

  • Vasquez, M., Hao, J.-K.: A heuristic approach for antenna positioning in cellular networks. J. Heuristics 7, 443–472 (2001a)

    Article  MATH  Google Scholar 

  • Vasquez, M., Hao, J.-K.: A heuristic approach for antenna positioning in cellular networks. J. Heuristics 7, 443–472 (2001b)

    Article  MATH  Google Scholar 

  • Zimmermann, J., Hons, R., Muhlenbein, H.: ENCON: evolutionary algorithm for the antenna placement problem. Comput. Ind. Eng. 44, 209–226 (2003)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Cardiff University, P.O. Box 916, Cardiff, CF24 3XF, UK

    Larry Raisanen

Authors
  1. Larry Raisanen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Larry Raisanen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Raisanen, L. A permutation-coded evolutionary strategy for multi-objective GSM network planning. J Heuristics 14, 1–21 (2008). https://doi.org/10.1007/s10732-007-9024-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-007-9024-4

Keywords