IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v62y2015i3p787-814.html
   My bibliography  Save this article

A heterogeneous cellular processing algorithm for minimizing the power consumption in wireless communications systems

Author

Listed:
  • J. Terán-Villanueva
  • Héctor Fraire Huacuja
  • Juan Carpio Valadez
  • Rodolfo Pazos Rangel
  • Héctor Puga Soberanes
  • José Martínez Flores

Abstract

In this paper, the NP-hard problem of minimizing power consumption in wireless communications systems is approached. In the literature, several metaheuristic approaches have been proposed to solve it. Currently a homogeneous cellular processing algorithm and a GRASP algorithm hybridized with path-relinking are considered the state of the art algorithms. The main contribution of this paper is the analysis of five main characteristics for a heterogeneous cellular processing algorithm, based on scatter search and GRASP. A series of computational experiments with standard instances were carried out to assess the impact of each one of these characteristics. Among the main analyses we found particularly interesting a time reduction by 74.24 %, produced by the stagnation detection characteristic. Also the communication characteristic improves the quality of the solutions by 24.73 %. The computational results show that our heterogeneous cellular processing algorithm is a good alternative for solving the problem. The proposed algorithm finds 34 new best known solutions, which is 27 % of the instances with unknown optimal values. A Friedman hypothesis test was carried out to validate that two state-of-the-art algorithms and the proposed algorithm are statistically equivalent. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • J. Terán-Villanueva & Héctor Fraire Huacuja & Juan Carpio Valadez & Rodolfo Pazos Rangel & Héctor Puga Soberanes & José Martínez Flores, 2015. "A heterogeneous cellular processing algorithm for minimizing the power consumption in wireless communications systems," Computational Optimization and Applications, Springer, vol. 62(3), pages 787-814, December.
  • Handle: RePEc:spr:coopap:v:62:y:2015:i:3:p:787-814
    DOI: 10.1007/s10589-015-9754-4
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-015-9754-4
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10589-015-9754-4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Mauricio G.C. Resende & Celso C. Ribeiro & Fred Glover & Rafael Martí, 2010. "Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 87-107, Springer.
    2. Righini, Giovanni, 2008. "A branch-and-bound algorithm for the linear ordering problem with cumulative costs," European Journal of Operational Research, Elsevier, vol. 186(3), pages 965-971, May.
    3. Abraham Duarte & Manuel Laguna & Rafael Martí, 2011. "Tabu search for the linear ordering problem with cumulative costs," Computational Optimization and Applications, Springer, vol. 48(3), pages 697-715, April.
    4. Thomas A. Feo & Mauricio G. C. Resende & Stuart H. Smith, 1994. "A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set," Operations Research, INFORMS, vol. 42(5), pages 860-878, October.
    5. Dario Landa-Silva & Edmund K. Burke, 2007. "Asynchronous Cooperative Local Search for the Office-Space-Allocation Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 575-587, November.
    6. Bertacco, Livio & Brunetta, Lorenzo & Fischetti, Matteo, 2008. "The Linear Ordering Problem with cumulative costs," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1345-1357, September.
    7. Duarte, Abraham & Martí, Rafael & Álvarez, Ada & Ángel-Bello, Francisco, 2012. "Metaheuristics for the linear ordering problem with cumulative costs," European Journal of Operational Research, Elsevier, vol. 216(2), pages 270-277.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Duarte, Abraham & Martí, Rafael & Álvarez, Ada & Ángel-Bello, Francisco, 2012. "Metaheuristics for the linear ordering problem with cumulative costs," European Journal of Operational Research, Elsevier, vol. 216(2), pages 270-277.
    2. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    3. Irène Charon & Olivier Hudry, 2010. "An updated survey on the linear ordering problem for weighted or unweighted tournaments," Annals of Operations Research, Springer, vol. 175(1), pages 107-158, March.
    4. Ivorra, Benjamin & Mohammadi, Bijan & Manuel Ramos, Angel, 2015. "A multi-layer line search method to improve the initialization of optimization algorithms," European Journal of Operational Research, Elsevier, vol. 247(3), pages 711-720.
    5. Coelho, V.N. & Grasas, A. & Ramalhinho, H. & Coelho, I.M. & Souza, M.J.F. & Cruz, R.C., 2016. "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints," European Journal of Operational Research, Elsevier, vol. 250(2), pages 367-376.
    6. Schirmer, Andreas & Riesenberg, Sven, 1997. "Parameterized heuristics for project scheduling: Biased random sampling methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 456, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    7. Herrán, Alberto & Manuel Colmenar, J. & Duarte, Abraham, 2021. "An efficient variable neighborhood search for the Space-Free Multi-Row Facility Layout problem," European Journal of Operational Research, Elsevier, vol. 295(3), pages 893-907.
    8. García-Martínez, C. & Rodriguez, F.J. & Lozano, M., 2014. "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 454-463.
    9. Francisco Casas & Claudio E. Torres & Ignacio Araya, 2022. "A heuristic search based on diversity for solving combinatorial problems," Journal of Heuristics, Springer, vol. 28(3), pages 287-328, June.
    10. Yogesh K. Agarwal, 2002. "Design of Capacitated Multicommodity Networks with Multiple Facilities," Operations Research, INFORMS, vol. 50(2), pages 333-344, April.
    11. Mario Pavone & Giuseppe Narzisi & Giuseppe Nicosia, 2012. "Clonal selection: an immunological algorithm for global optimization over continuous spaces," Journal of Global Optimization, Springer, vol. 53(4), pages 769-808, August.
    12. Parreño, Francisco & Pacino, Dario & Alvarez-Valdes, Ramon, 2016. "A GRASP algorithm for the container stowage slot planning problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 141-157.
    13. Alejandra Casado & Sergio Pérez-Peló & Jesús Sánchez-Oro & Abraham Duarte, 2022. "A GRASP algorithm with Tabu Search improvement for solving the maximum intersection of k-subsets problem," Journal of Heuristics, Springer, vol. 28(1), pages 121-146, February.
    14. Drexl, Andreas & Salewski, Frank, 1996. "Distribution Requirements and Compactness Constraints in School Timetabling. Part II: Methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 384, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    15. Böttcher, Jan & Drexl, Andreas & Kolisch, Rainer & Salewski, Frank, 1996. "Project scheduling under partially renewable resource constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 398, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    16. Gambardella, L.M. & Montemanni, R. & Weyland, D., 2012. "Coupling ant colony systems with strong local searches," European Journal of Operational Research, Elsevier, vol. 220(3), pages 831-843.
    17. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    18. Jan Mikula & Miroslav Kulich, 2022. "Solving the traveling delivery person problem with limited computational time," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(4), pages 1451-1481, December.
    19. Colombi, Marco & Mansini, Renata & Savelsbergh, Martin, 2017. "The generalized independent set problem: Polyhedral analysis and solution approaches," European Journal of Operational Research, Elsevier, vol. 260(1), pages 41-55.
    20. Qinghua Wu & Yang Wang & Fred Glover, 2020. "Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 74-89, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:62:y:2015:i:3:p:787-814. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.