A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks. (26th February 2014)

• Record Type: Journal Article
• Authors: Rebai, Maher; Le Berre, Matthieu; Hnaien, Faicel; Snoussi, Hichem; Khoukhi, Lyes
• Is Part Of: International journal of distributed sensor networks. Volume 10:Number 2(2014)
• Publication Date: 2014-02-26
• Subjects: Sensor networks -- Periodicals; Intelligent agents (Computer software) -- Periodicals; Multisensor data fusion -- Periodicals; 681.2
• DOI: 10.1155/2014/769658
• Languages: English
• ISSNs: 1550-1329

Abstract

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.