A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks - Université de technologie de Troyes Access content directly
Journal Articles International Journal of Distributed Sensor Networks Year : 2014

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

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.

Dates and versions

hal-02271684 , version 1 (27-08-2019)

Identifiers

Cite

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, 2014, 10 (2), pp.769658. ⟨10.1155/2014/769658⟩. ⟨hal-02271684⟩
21 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More