Skip to Main content Skip to Navigation
Journal articles

Exact methods for sensor deployment problem with connectivity constraint in wireless sensor networks

Abstract : In wireless sensor networks, coverage and connectivity are two essential issues. They indicate how all the points of an area of interest are covered and how the sensor devices of the wireless sensor network are connected in an efficient way. In this study, the problem of minimising total grid coverage cost with connectivity constraint is considered. The connectivity constraint means that each deployed sensor has to find a path, composed of connected sensors, until to reach the base station the sink. The problem may be reduced to a 2-dimensional critical grid coverage problem which is an NP-Complete problem. We propose mixed integer linear programming models to solve the problem optimally. We verify by computational experiments that the developed approaches can provide the optimal solution of grid sizes of 15 × 15 width × length in a reasonable time. We also show that one of the proposed methods is more efficient than some methods developed for similar problems.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02485536
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, February 20, 2020 - 11:17:57 AM
Last modification on : Tuesday, June 16, 2020 - 4:04:02 PM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Maher Rebai, Hasan Murat Afsar, Hichem Snoussi. Exact methods for sensor deployment problem with connectivity constraint in wireless sensor networks. International Journal of Sensor Networks, Inderscience, 2016, 21 (3), pp.157. ⟨10.1504/IJSNET.2016.078324⟩. ⟨hal-02485536⟩

Share

Metrics

Record views

41