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

Xiaojian Zhu, Jun Li, Xuemin Chen, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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.

Original languageEnglish (US)
Article number7938610
Pages (from-to)4938-4952
Number of pages15
JournalIEEE Sensors Journal
Issue number15
StatePublished - Aug 1 2017

All Science Journal Classification (ASJC) codes

  • Instrumentation
  • Electrical and Electronic Engineering


  • Directional sensor
  • coverage quality
  • network connectivity
  • network deployment
  • optimization
  • target coverage


Dive into the research topics of 'Minimum Cost Deployment of Heterogeneous Directional Sensor Networks for Differentiated Target Coverage'. Together they form a unique fingerprint.

Cite this