Authors
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
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