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

Authors: Maher Rebai; Hasan Murat Afsar; Hichem Snoussi

Addresses: ICD LM2S, UMR 6281, CNRS, University of Technology of Troyes, BP2060, 10010 Troyes, France ' ICD LOSI, UMR 6281, CNRS, University of Technology of Troyes, BP2060, 10010 Troyes, France ' ICD LM2S, UMR 6281, CNRS, University of Technology of Troyes, BP2060, 10010 Troyes, France

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.

Keywords: wireless sensor networks; WSNs; total grid coverage; mixed integer linear programming; MILP; location problem; sensor deployment; connectivity constraints.

DOI: 10.1504/IJSNET.2016.078324

International Journal of Sensor Networks, 2016 Vol.21 No.3, pp.157 - 168

Received: 07 Jan 2014
Accepted: 10 Feb 2015
Published online: 15 Aug 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article