IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v25y2019i6d10.1007_s10732-019-09414-z.html
   My bibliography  Save this article

An evolutionary hybrid search heuristic for monitor placement in communication networks

Author

Listed:
  • Robin Mueller-Bady

    (Frankfurt University of Applied Sciences)

  • Martin Kappes

    (Frankfurt University of Applied Sciences)

  • Inmaculada Medina-Bulo

    (University of Cadiz)

  • Francisco Palomo-Lozano

    (University of Cadiz)

Abstract

In this paper, a heuristic method for the optimal placement of monitors in communication networks is proposed. In order to be able to make informed decisions, a first step towards securing a communication network is deploying an adequate sensor infrastructure. However, appropriate monitoring should take into account the priority of the communication links as well as the location of monitors. The goal is to cover the whole network with the minimum investment and impact on performance, i.e., the optimal amount and positions of monitors in the network. In order to be able to counteract dynamic changes in those networks, e.g., link failures, attacks, or entering and leaving nodes, this work focuses on swiftly obtaining results having an acceptable quality. To achieve this goal, an effective hybrid search heuristic is introduced, combining the computational efficiency of a greedy local search method with the robustness of evolution-based heuristics. It is shown that this approach works well on synthetic benchmark instances and real-world network models, having up to millions of nodes, by comparing the performance of a common evolutionary algorithm (EA) to its hybrid search counterparts. It is observed that the hybrid search heuristics produce good solutions on the instances under study in a reasonable amount of time. Regarding the fitness of the solutions found, the hybrid approach outperforms the common EA in all the experiments. Moreover, on all problem instances, the hybrid EA finds the best solutions significantly earlier in the search process, which is key when monitoring a communication infrastructure which is subject to change.

Suggested Citation

  • Robin Mueller-Bady & Martin Kappes & Inmaculada Medina-Bulo & Francisco Palomo-Lozano, 2019. "An evolutionary hybrid search heuristic for monitor placement in communication networks," Journal of Heuristics, Springer, vol. 25(6), pages 861-899, December.
  • Handle: RePEc:spr:joheur:v:25:y:2019:i:6:d:10.1007_s10732-019-09414-z
    DOI: 10.1007/s10732-019-09414-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-019-09414-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10732-019-09414-z?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. E. L. Lawler & D. E. Wood, 1966. "Branch-and-Bound Methods: A Survey," Operations Research, INFORMS, vol. 14(4), pages 699-719, August.
    2. López-Ibáñez, Manuel & Dubois-Lacoste, Jérémie & Pérez Cáceres, Leslie & Birattari, Mauro & Stützle, Thomas, 2016. "The irace package: Iterated racing for automatic algorithm configuration," Operations Research Perspectives, Elsevier, vol. 3(C), pages 43-58.
    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. Asghari, Mohammad & Jaber, Mohamad Y. & Mirzapour Al-e-hashem, S.M.J., 2023. "Coordinating vessel recovery actions: Analysis of disruption management in a liner shipping service," European Journal of Operational Research, Elsevier, vol. 307(2), pages 627-644.
    2. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    3. Carolina G. Marcelino & João V. C. Avancini & Carla A. D. M. Delgado & Elizabeth F. Wanner & Silvia Jiménez-Fernández & Sancho Salcedo-Sanz, 2021. "Dynamic Electric Dispatch for Wind Power Plants: A New Automatic Controller System Using Evolutionary Algorithms," Sustainability, MDPI, vol. 13(21), pages 1-20, October.
    4. Coşar Gözükırmızı & Metin Demiralp, 2019. "Solving ODEs by Obtaining Purely Second Degree Multinomials via Branch and Bound with Admissible Heuristic," Mathematics, MDPI, vol. 7(4), pages 1-23, April.
    5. Kezong Tang & Xiong-Fei Wei & Yuan-Hao Jiang & Zi-Wei Chen & Lihua Yang, 2023. "An Adaptive Ant Colony Optimization for Solving Large-Scale Traveling Salesman Problem," Mathematics, MDPI, vol. 11(21), pages 1-26, October.
    6. Amine Lamine & Mahdi Khemakhem & Brahim Hnich & Habib Chabchoub, 2016. "Solving constrained optimization problems by solution-based decomposition search," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 672-695, October.
    7. Arda, Yasemin & Cattaruzza, Diego & François, Véronique & Ogier, Maxime, 2024. "Home chemotherapy delivery: An integrated production scheduling and multi-trip vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 317(2), pages 468-486.
    8. Weiqiang Pan & Zhilong Shan & Ting Chen & Fangjiong Chen & Jing Feng, 2016. "Optimal pilot design for OFDM systems with non-contiguous subcarriers based on semi-definite programming," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 63(2), pages 297-305, October.
    9. Véronique François & Yasemin Arda & Yves Crama, 2019. "Adaptive Large Neighborhood Search for Multitrip Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 53(6), pages 1706-1730, November.
    10. Ofer M. Shir & Xi. Xing & Herschel. Rabitz, 2021. "Multi-level evolution strategies for high-resolution black-box control," Journal of Heuristics, Springer, vol. 27(6), pages 1021-1055, December.
    11. Kallestad, Jakob & Hasibi, Ramin & Hemmati, Ahmad & Sörensen, Kenneth, 2023. "A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 309(1), pages 446-468.
    12. Drexl, Andreas, 1990. "Scheduling of project networks by job assignment," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 247, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    13. Yi-Feng Hung & Wei-Chih Chen, 2011. "A heterogeneous cooperative parallel search of branch-and-bound method and tabu search algorithm," Journal of Global Optimization, Springer, vol. 51(1), pages 133-148, September.
    14. Fox, B. L. & Lenstra, J. K. & Rinnooy Kan, A. H. G. & Schrage, L. E., 1977. "Branching From The Largest Upper Bound: Folklore And Facts," Econometric Institute Archives 272158, Erasmus University Rotterdam.
    15. Andrade, Carlos E. & Toso, Rodrigo F. & Gonçalves, José F. & Resende, Mauricio G.C., 2021. "The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications," European Journal of Operational Research, Elsevier, vol. 289(1), pages 17-30.
    16. Molenbruch, Yves & Braekers, Kris & Caris, An, 2017. "Benefits of horizontal cooperation in dial-a-ride services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 107(C), pages 97-119.
    17. Alexandre D. Jesus & Luís Paquete & Arnaud Liefooghe, 2021. "A model of anytime algorithm performance for bi-objective optimization," Journal of Global Optimization, Springer, vol. 79(2), pages 329-350, February.
    18. Weiner, Jake & Ernst, Andreas T. & Li, Xiaodong & Sun, Yuan & Deb, Kalyanmoy, 2021. "Solving the maximum edge disjoint path problem using a modified Lagrangian particle swarm optimisation hybrid," European Journal of Operational Research, Elsevier, vol. 293(3), pages 847-862.
    19. Pessoa, Luciana S. & Andrade, Carlos E., 2018. "Heuristics for a flowshop scheduling problem with stepwise job objective function," European Journal of Operational Research, Elsevier, vol. 266(3), pages 950-962.
    20. Thomas L. Morin & Roy E. Marsten, 1974. "Brand-and-Bound Strategies for Dynamic Programming," Discussion Papers 106, Northwestern University, Center for Mathematical Studies in Economics and Management Science.

    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:joheur:v:25:y:2019:i:6:d:10.1007_s10732-019-09414-z. 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.