Skip to Main content Skip to Navigation
Journal articles

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

Maher Rebai 1 Matthieu Le Berre 2 Faicel Hnaien 1 Hichem Snoussi 2 Lyes Khoukhi 3
1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
ICD - Institut Charles Delaunay
2 LM2S - Laboratoire Modélisation et Sûreté des Systèmes
ICD - Institut Charles Delaunay
3 ERA - Environnement de Réseaux Autonomes
ICD - Institut Charles Delaunay
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.
Document type :
Journal articles
Complete list of metadata
https://hal-utt.archives-ouvertes.fr/hal-02271684
Contributor : Jean-Baptiste Vu Van Connect in order to contact the contributor
Submitted on : Tuesday, August 27, 2019 - 10:32:18 AM
Last modification on : Friday, August 27, 2021 - 3:14:08 PM

Links full text

openaccess

Identifiers

Collections

CNRS | UTT

`

Citation

Maher Rebai, Matthieu Le Berre, Faicel Hnaien, Hichem Snoussi, Lyes Khoukhi. A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks. International Journal of Distributed Sensor Networks, Hindawi Publishing Corporation, 2014, 10 (2), pp.769658. ⟨10.1155/2014/769658⟩. ⟨hal-02271684⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

46