An evolutionary hybrid search heuristic for monitor placement in communication networks

Robin Mueller-Bady (), Martin Kappes (), Inmaculada Medina-Bulo () and Francisco Palomo-Lozano ()
Additional contact information
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

Journal of Heuristics, 2019, vol. 25, issue 6, No 2, 899 pages

Abstract: 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.

Keywords: Network monitoring; Evolutionary algorithm; Local search; Hybrid search heuristic; Population injection (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-019-09414-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:25:y:2019:i:6:d:10.1007_s10732-019-09414-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-019-09414-z

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().