A Specific Heuristic Dedicated to a Coverage/Tracking Bi-objective Problem for Wireless Sensor Deployment

International audienceIn recent years, wireless sensor networks (WSN) have become very attractive for surveillance applications and particularly for target tracking. When a target has to be located by a WSN, accuracy is an important constraint. Most of the studies made in the WSNs problems deal with either coverage or tracking focus objectives. In this paper, we propose a modification of a previously studied bi-objective sensor placement problem taking into account both coverage and accuracy. The objectives are the minimization of the number of deployed sensors and the minimization of the tracking constraints violations, under the coverage constraints. The non sorting genetic algorithm and multi objective particle swarm optimization have been implemented to solve the problem. A specific heuristic (H3P) based on the mathematical decomposition of the problem has also been proposed. The performances of these algorithms are checked with integer programming results for small size instances, and they are compared on large size instances by multi-objective metrics. Results have shown that implemented metaheuristics provide less optimal solutions than the H3P for the small size instances. The comparison between the algorithms on large size instances set show that the H3P dominates the other implemented methods