On Efficient Deployment of Wireless Sensors for Coverage and Connectivity in Constrained 3D Space

Chase Q. Wu, Li Wang

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Sensor networks have been used in a rapidly increasing number of applications in many fields. This work generalizes a sensor deployment problem to place a minimum set of wireless sensors at candidate locations in constrained 3D space to k-cover a given set of target objects. By exhausting the combinations of discreteness/continuousness constraints on either sensor locations or target objects, we formulate four classes of sensor deployment problems in 3D space: deploy sensors at Discrete/Continuous Locations (D/CL) to cover Discrete/Continuous Targets (D/CT). We begin with the design of an approximate algorithm for DLDT and then reduce DLCT, CLDT, and CLCT to DLDT by discretizing continuous sensor locations or target objects into a set of divisions without sacrificing sensing precision. Furthermore, we consider a connected version of each problem where the deployed sensors must form a connected network, and design an approximation algorithm to minimize the number of deployed sensors with connectivity guarantee. For performance comparison, we design and implement an optimal solution and a genetic algorithm (GA)-based approach. Extensive simulation results show that the proposed deployment algorithms consistently outperform the GA-based heuristic and achieve a close-to-optimal performance in small-scale problem instances and a significantly superior overall performance than the theoretical upper bound.

Original languageEnglish (US)
JournalSensors (Basel, Switzerland)
Volume17
Issue number10
DOIs
StatePublished - Oct 10 2017

All Science Journal Classification (ASJC) codes

  • Analytical Chemistry
  • Biochemistry
  • Atomic and Molecular Physics, and Optics
  • Instrumentation
  • Electrical and Electronic Engineering

Keywords

  • approximation algorithm
  • k-coverage
  • network connectivity
  • sensor deployment

Fingerprint

Dive into the research topics of 'On Efficient Deployment of Wireless Sensors for Coverage and Connectivity in Constrained 3D Space'. Together they form a unique fingerprint.

Cite this