Maher Rebai, Matthieu Le Berre, Faicel Hnaien, Hichem Snoussi, Lyes Khoukhi,

A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks

International Journal of Distributed Sensor Networks

Hindawi Publishing Corporation

2014

In this paper, we aim to cover a grid fully by deploying the necessary wireless sensors while maintaining connectivity between the deployed sensors and a base station (the sink). The problem is NP − Complete as it can be reduced to a 2 − dimensional critical coverage problem, which was proved NP − Complete by Ke et al. [1], after removing the connectivity constraint. We develop a branch and bound (B&B) algorithm to solve the problem optimally. We verify by computational experiments that the proposed B&B algorithm is more efficient, in terms of computation time, than the integer linear programming model developed by Rebai et al. [2] for the same problem.

• ERA
• LM2S
• LOSI
• Surveillance et sûreté des grands systèmes