Authors
Maher Rebai, Matthieu Le Berre, Faicel Hnaien, Hichem Snoussi, Lyes Khoukhi,
Title
A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks
In
International Journal of Distributed Sensor Networks
Publisher
Hindawi Publishing Corporation
Year
2014
Publisher's URL
http://www.hindawi.com/journals/ijdsn/aip/769658/
Indexed by
Abstract
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.
Affiliations
Offprint