Target Coverage and Connectivity in Directional Wireless Sensor Networks

Abstract

This paper discusses the problem of deploying a minimum number of directional sensors equipped with directional sensing units and directional communication antennas with beam-width ${\theta _c} \geq \frac{\pi }{2}$ such that the set of sensors covers a set of targets P in the 2D plane and the set of sensors forms a symmetric connected communication graph. As this problem is NP-hard, we propose an approximation algorithm that uses up to 3.5 times the number of omni-directional sensors required by the currently best approximation algorithm proposed by Han et al. [1]. This is a significant result since we have broken the barrier of $2\pi /\frac{\pi }{2} = 4$ when switching from omni-directional sensors to directional ones. Moreover, we improve the approximation ratio of the Strip-based algorithm for the Geometric Sector Cover problem proposed by Han et al. [1] from 9 to 7, and we believe that this result is of interest in the area of Computation Geometry. Simulation results show that our algorithms only require around 3 times the number of sensors used by Han et al.’s algorithm and significantly outperform other heuristics in practice.