Approximate algorithms for sensor deployment with k-coverage in constrained 3D space

Yunyue Lin, Chase Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Sensor deployment is one fundamental task in sensor network implementation. We generalize and investigate the problem of deploying a minimum set of wireless sensors at candidate locations in constrained 3D space of interest to achieve k-coverage of given target areas such that each point in the target areas is covered by at least k sensors. Based on different constraints on sensor locations and target areas, we formulate four sensor deployment problems: Discrete / Continuous sensor Locations (D/CL) with Discrete / Continuous Target areas (D/CT). We propose an approximate algorithm for DLDT and reduce DLCT and CLDT to DLDT by discretizing continuous sensor locations or target areas into a number of divisions without loss of sensing precision. We further consider the connected version of these four sensor deployment problems where deployed sensors must form a connected network, and propose an approximate algorithm for each of these connected deployment problems.

Original languageEnglish (US)
Title of host publicationProceedings - 16th International Conference on Parallel and Distributed Systems, ICPADS 2010
Pages550-557
Number of pages8
DOIs
StatePublished - Dec 1 2010
Externally publishedYes
Event16th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2010 - Shanghai, China
Duration: Dec 8 2010Dec 10 2010

Other

Other16th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2010
Country/TerritoryChina
CityShanghai
Period12/8/1012/10/10

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Approximate algorithms for sensor deployment with k-coverage in constrained 3D space'. Together they form a unique fingerprint.

Cite this