Node placement optimization under Q-Coverage and Q-Connectivity constraints in wireless sensor networks

Target coverage and connectivity problems are major challenges for wireless sensor networks (WSNs). In practice, when different targets demand different priority levels, each target is assigned a value q which is the number of sensors covering it as well as the number of node-disjoint paths to transfer sensing data of itself to the base station. When q > 1, the network can ensure fault tolerance. Those constraints are named Q-Coverage and Q-Connectivity. In this paper, we propose a two-phase solution for the problem: Greedy combined with Linear Programming (GLA) for Phase I and Clustering combined with graph Max Flow Approach (CMFA) for Phase II. Besides, we also evaluate the algorithms with multiple datasets and make some comparisons with baseline methods (ESSNP in phase I; CCMFA and FCSA in phase II). Our results show that the proposed algorithms significantly improve in various evaluation metrics compared to baseline methods. Furthermore, the results can be advantageous for our future researches on WSNs in general and target coverage in particular.

Automated summary

This paper proposes a two-phase solution for the target coverage and connectivity problems in wireless sensor networks. The first phase utilizes a greedy algorithm combined with linear programming, while the second phase employs clustering combined with a graph max flow approach. The results of the study demonstrate significant improvements in various evaluation metrics compared to baseline methods. Additionally, the findings provide advantages for future research on WSNs and target coverage.