Deploying Directional Sensor Networks with Guaranteed Connectivity and Coverage

In contrast to existing work on the connected coverage problem in wireless sensor networks which assumes omnidirectional sensors with disk-like sensing range, this paper investigates a suite of novel problems related to connected coverage in directional sensor networks where sensors only sense directionally and have a sector-like sensing range. We first consider the problems of deploying a minimum number of directional sensors to form a connected network to cover either a set of point- locations (connected point-coverage deployment (CPD)) or the entire target sensing area (connected region-coverage deployment (CRD)). CPD is NP-hard as its subproblem of geometric sector cover (GSC) is NP-hard. We present two approximation algorithms for GSC as subroutines, and develop a general solution framework for CPD with approximation ratio sigma + O(1), where sigma is the approximation ratio of the selected GSC subroutine. We also describe two efficient deployment patterns with guaranteed covering density for CRD, and analyze their performance bounds with respect to arbitrary non-crossing deployment patterns. Extensive simulation results validate the correctness and merits of the presented algorithms and analysis.