Minimum Cost Deployment of Heterogeneous Directional Sensor Networks for Differentiated Target Coverage

A basic deployment goal of a directional sensor network (DSN) is to satisfy the coverage quality requirements of targets. The limited sensing angle of directional sensors makes the deployment of such a network more complicated than that of an omnidirectional sensor network. In some emerging DSN applications, targets may have differentiated coverage quality requirements due to their differentiated importance or priorities. Meanwhile, directional sensors of multiple types with different sensing ranges and prices are available for optimally organizing a network. To deploy such a DSN with satisfied network connectivity under the minimum cost constraint is a significant problem to be solved. This work formulates and addresses the problem for the first time. First, we prove its NP-completeness. Then, this problem is formulated as an integer linear programming model. To solve it, we propose three algorithms, i.e., a greedy heuristic, local search, and particle swarm optimization. Extensive numerical experiments are conducted to validate the proposed algorithms. The results show that all the proposed algorithms can effectively solve the problem, and the last one can achieve both highest success rate and best solution quality.