A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks
Maher Rebai, Matthieu Le Berre, Faicel Hnaien, Hichem Snoussi, Lyes Khoukhi · International Journal of Distributed Sensor Networks · 2014
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 is an NP- Complete problem. 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. (2013), for the same problem.