MILP, Pseudo-Boolean, and OMT Solvers for Optimal Fault-Tolerant Placements of Relay Nodes in Mission Critical Wireless Networks*

Autor: Qian Matteo Chen, Toni Mancini, Igor Melatti, Alberto Finzi, Enrico Tronci
Přispěvatelé: Chen, Qian Matteo, Finzi, Alberto, Mancini, Toni, Melatti, Igor, Tronci, Enrico
Rok vydání: 2020
Předmět:
FOS: Computer and information sciences
Computer Science - Logic in Computer Science
Linear programming
Computer Science - Artificial Intelligence
Optimisation
Mixed Linear Optimisation Problems
Satisfiability Modulo Theories
Pseudo-Boolean Optimisation
Critical infrastructures
Computer science
Mission critical
J.6
I.2.8
Theoretical Computer Science
law.invention
Computer Science - Networking and Internet Architecture
Relay
law
Default gateway
Networking and Internet Architecture (cs.NI)
Algebra and Number Theory
business.industry
Wireless network
Fault tolerance
Telecommunications network
Logic in Computer Science (cs.LO)
Artificial Intelligence (cs.AI)
Computer Science - Distributed
Parallel
and Cluster Computing
Computational Theory and Mathematics
Software deployment
Distributed
Parallel
and Cluster Computing (cs.DC)
business
68T20 (Primary)
68T27 (Secondary)
Information Systems
Computer network
Zdroj: Fundamenta Informaticae. 174:229-258
ISSN: 1875-8681
0169-2968
DOI: 10.3233/fi-2020-1941
Popis: In critical infrastructures like airports, much care has to be devoted in protecting radio communication networks from external electromagnetic interference. Protection of such mission-critical radio communication networks is usually tackled by exploiting radiogoniometers: at least three suitably deployed radiogoniometers, and a gateway gathering information from them, permit to monitor and localise sources of electromagnetic emissions that are not supposed to be present in the monitored area. Typically, radiogoniometers are connected to the gateway through relay nodes. As a result, some degree of fault-tolerance for the network of relay nodes is essential in order to offer a reliable monitoring. On the other hand, deployment of relay nodes is typically quite expensive. As a result, we have two conflicting requirements: minimise costs while guaranteeing a given fault-tolerance. In this paper, we address the problem of computing a deployment for relay nodes that minimises the relay node network cost while at the same time guaranteeing proper working of the network even when some of the relay nodes (up to a given maximum number) become faulty (fault-tolerance). We show that, by means of a computation-intensive pre-processing on a HPC infrastructure, the above optimisation problem can be encoded as a 0/1 Linear Program, becoming suitable to be approached with standard Artificial Intelligence reasoners like MILP, PB-SAT, and SMT/OMT solvers. Our problem formulation enables us to present experimental results comparing the performance of these three solving technologies on a real case study of a relay node network deployment in areas of the Leonardo da Vinci Airport in Rome, Italy.
33 pages, 11 figures
Databáze: OpenAIRE
Externí odkaz: