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

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

International Journal of Distributed Sensor Networks, 2014, vol. 10, issue 2, 769658

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.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1155/2014/769658 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:10:y:2014:i:2:p:769658

DOI: 10.1155/2014/769658

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().