A multi-objective modeling of K-coverage problem under accuracy constraint

Matthieu Le Berre (1) , Faicel Hnaien (2) , Hichem Snoussi (1)

1 LM2S - Laboratoire Modélisation et Sûreté des Systèmes
2 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

In recent years, wireless sensor networks have become attractive for tracking and target surveillance. For these applications, the accuracy is an important constraint. In this paper, we study a multi-objective sensor placement problem taking into account the K-coverage and the accuracy. The objectives are the maximization of the K-coverage and the minimization of the number of deployed sensors, under an accuracy constraint. A linear formulation and an adaptation of the NSGA-II and Beam Search are proposed. Results show the NSGA-II is better than the BS heuristic for small instances but this trend is inverted for larger instances.

Domains: Computer Science [cs]; Performance [cs.PF]; Computer Science [cs]; Cryptography and Security [cs.CR]

Matthieu Le Berre, Faicel Hnaien, Hichem Snoussi. A multi-objective modeling of K-coverage problem under accuracy constraint. 2013 5th International Conference on Modeling, Simulation and Applied Optimization (ICMSAO 2013), Apr 2013, Hammamet, Tunisia. pp.1-6. ⟨hal-02287561⟩