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

Randomized heuristics for handover minimization in mobility networks

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

A mobile device connects to the cell tower (base station) from which it receives the strongest signal. As the device moves it may connect to a series of towers. The process in which the device changes the base station it is connected to is called handover. A cell tower is connected to a radio network controller (RNC) which controls many of its operations, including handover. Each cell tower handles an amount of traffic and each radio network controller has capacity to handle a maximum amount of traffic from all base stations connected to it. Handovers between base stations connected to different RNCs tend to fail more often than handovers between base stations connected to the same RNC. Handover failures result in dropped connections and therefore should be minimized. The Handover Minimization Problem is to assign towers to RNCs such that RNC capacity is not violated and the number of handovers between base stations connected to different RNCs is minimized. We describe an integer programming formulation for the handover minimization problem and show that state-of-the-art integer programming solvers can solve only very small instances of the problem. We propose several randomized heuristics for finding approximate solutions of this problem, including a GRASP with path-relinking for the generalized quadratic assignment problem, a GRASP with evolutionary path-relinking, and a biased random-key genetic algorithm. Computational results are presented.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

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

Notes

  1. Available at http://www.research.att.com/~mgcr/data/handover-minimization.

  2. COLT is a open source library for high performance scientific and technical computing in Java. See http://acs.lbl.gov/~hoschek/colt/.

References

  • Aiex, R.M., Pardalos, P.M., Resende, M.G.C., Toraldo, G.: GRASP with path-relinking for three-index assignment. INFORMS J. Comput. 17, 224–247 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  • Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: TTTPLOTS: a perl program to create time-to-target plots. Optim. Lett. 1, 355–366 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 2, 154–160 (1994)

    Article  Google Scholar 

  • Deng, Y., Bard, J.F.: A reactive GRASP with path relinking for capacitated clustering. J. Heuristics 17, 119–152 (2011)

    Article  MATH  Google Scholar 

  • Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  • Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6, 109–133 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  • Ferreira, C.E., Martin, A., de Souza, C.C., Weismantel, R., Wolsey, L.A.: The node capacitated graph partitioning problem: a computational study. Math. Program. 81, 229–256 (1998)

    MATH  Google Scholar 

  • Festa, P., Pardalos, P.M., Resende, M.G.C., Ribeiro, C.C.: Randomized heuristics for the MAX-CUT problem. Optim. Methods Softw. 7, 1033–1058 (2002)

    Article  MathSciNet  Google Scholar 

  • Glover, F.: Tabu search and adaptive memory programming—advances, applications and challenges. In: Barr, R.S., Helgason, R.V., Kennington, J.L. (eds.) Interfaces in Computer Science and Operations Research, pp. 1–75. Boston, Kluwer Academic Publishers (1996)

  • Gonçalves, J.F., Resende, M.G.C.: A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem. J. Comb. Optim. 22, 180–201 (2011a)

    Article  MathSciNet  Google Scholar 

  • Gonçalves, J.F., Resende, M.G.C.: Biased random-key genetic algorithms for-combinatorial optimization. J. Heuristics 17, 487–525 (2011b)

    Article  Google Scholar 

  • Katzela, I., Naghshineh, M.: Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey. IEEE Pers. Commun. 3(3), 10–31 (1996)

    Article  Google Scholar 

  • Laguna, M., Martí, R.: GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J. Comput. 11, 44–52 (1999)

    Article  MATH  Google Scholar 

  • Mateus, G.R., Resende, M.G.C., Silva, R.M.A.: GRASP with path-relinking for the generalized quadratic assignment problem. J. Heuristics 17, 527–565 (2011)

    Article  MATH  Google Scholar 

  • Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8, 3–30 (1998)

    Article  MATH  Google Scholar 

  • Mehrotra, A., Trick, M.A.: Cliques and clustering: a combinatorial approach. Oper. Res. Lett. 22, 1–12 (1997)

    MathSciNet  Google Scholar 

  • Morán-Mirabal, L.F., González-Velarde, J.L., Resende, M.G.C.: Automatic tuning of GRASP with evolutionary path-relinking. In: Blesa, M.J. (ed.) Hybrid Metaheuristics, vol. 7919, pp. 62–77. Lecture Notes in Computer Science, Heidelberg (2013)

  • Resende, M.G.C., Werneck, R.F.: A hybrid heuristic for the \(p\)-median problem. J. Heuristics 10, 59–88 (2004)

    Article  MATH  Google Scholar 

  • Resende, M.G.C., Ribeiro, C.C., Glover, F., Martí, R.: Scatter search and path-relinking: Fundamentals, advances, and applications. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, vol. 146 of International Series in Operations Research & Management Science, 2nd edn, pp. 87–107. Springer, Boston (2010)

  • Ribeiro, C.C., Resende, M.G.C.: Path-relinking intensification methods for stochastic local search algorithms. J. Heuristics 18, 193–214 (2012)

    Article  Google Scholar 

  • Spears, W.M., DeJong, K.A.: On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230–236 (1991)

  • Tekinay, S., Jabbari, B.: Handover and channel assignment in mobile cellular networks. IEEE Commun. Mag. 29(11), 42–46 (1991)

    Article  Google Scholar 

  • Toso, R.F., Resende, M.G.C.: A C++ application programming interface for biased random-key genetic algorithms. Technical report, AT &T Labs Research. Florham Park, NJ (2012)

    Google Scholar 

  • University of Wisconsin. Condor high throughput computing, 2012. http://research.cs.wisc.edu/condor. Accessed 25 June 2012

Download references

Acknowledgments

This research was done while L.F. Morán-Mirabal and R.M.A. Silva were Visiting Scholars at AT&T Labs Research in Florham Park, New Jersey. The research of L.F. Morán-Mirabal was partially funded by Tecnológico de Monterrey Research Fund CAT128. The research of R.M.A Silva was partially supported by the Brazilian National Council for Scientific and Technological Development (CNPq), the Foundation for Support of Research of the State of Minas Gerais (FAPEMIG), the Brazilian Coordination for the Improvement of Higher Education Personnel (CAPES), the Office for Research and Graduate Studies of the Federal University of Pernambuco (PROPESQ), and the Foundation for Support of Science and Technology of the State of Pernambuco (FACEPE).

Author information

Authors and Affiliations

  1. Quality and Manufacturing Center, Tecnológico de Monterrey, Monterrey, Mexico

    L. F. Morán-Mirabal & J. L. González-Velarde

  2. Algorithms and Optimization Research Department, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ, 07932, USA

    M. G. C. Resende

  3. Centro de Informática (CIn), Federal University of Pernambuco, Av. Prof. Luís Freire s/n, Cidade Universitária, Recife, PE, Brazil

    R. M. A. Silva

Authors
  1. L. F. Morán-Mirabal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. L. González-Velarde
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. G. C. Resende
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. R. M. A. Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. G. C. Resende.

Additional information

AT&T Labs Research Technical Report, August 2012.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Morán-Mirabal, L.F., González-Velarde, J.L., Resende, M.G.C. et al. Randomized heuristics for handover minimization in mobility networks. J Heuristics 19, 845–880 (2013). https://doi.org/10.1007/s10732-013-9223-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-013-9223-0

Keywords

Search

Navigation