On New Approaches of Maximum Weighted Target Coverage and Sensor Connectivity: Hardness and Approximation
- 8 November 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 7 (3) , 1736-1751
Abstract
In mobile wireless sensor networks (MWSNs), because the movement of sensors consumes much more power than that in sensing and communication, the problem of scheduling mobile sensors to cover all targets and maintain network connectivity such that the total movement distance of mobile sensors is minimized has received a great deal of attention. However, network design in fact indicates that there are situations (limited budget, sensor failure, or obstacle in a sensing field) in which the number of active mobile sensors is insufficient to cover all targets or form a connected network. Therefore, targets must be weighted by their importance. The more important a target, the higher the weight of the target. A more general problem for target coverage and network connectivity, termed the Maximum Weighted Target Coverage and Sensor Connectivity with Limited Mobile Sensors (TAR-CC) problem, is studied. In this paper, an approximation algorithm, termed the weighted-maximum-coverage-based algorithm (WMCBA), is proposed for the subproblem of the TAR-CC problem. Based on the WMCBA, the Steiner-tree-based algorithm (STBA) is proposed for the TAR-CC problem. Simulation results demonstrate that the STBA provides better performance than the other methods.Keywords
All Related Versions
Funding Information
- Ministry of Science and Technology (MOST 108-2221-E-992-018)
This publication has 41 references indexed in Scilit:
- Response-only modal identification of structures using limited sensorsStructural Control and Health Monitoring, 2012
- High energy‐efficient and privacy‐preserving secure data aggregation for wireless sensor networksInternational Journal of Communication Systems, 2012
- Development and In-situ validation of a multi-zone demand-controlled ventilation strategy using a limited number of sensorsBuilding and Environment, 2012
- A survey on coverage and connectivity issues in wireless sensor networksJournal of Network and Computer Applications, 2012
- Hardness Results for Homology LocalizationDiscrete & Computational Geometry, 2011
- The design space of wireless sensor networksIEEE Wireless Communications, 2004
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner TreesJournal of Algorithms, 1995
- Two algorithms for constructing a Delaunay triangulationInternational Journal of Parallel Programming, 1980
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955