A Framework for the Optimal k-Coverage Deployment Patterns of Wireless Sensors

The strategy for node deployment to achieve multiple connectivity and coverage plays an important role in various wireless senor network applications. To alleviate the operational cost, the number of nodes to be deployed needs to be reduced. While the optimal k-connectivity deployment patterns (k ≤ 6) and the multiple k-coverage problem (k ≤ 3) have been extensively studied for 2-D networks, a general method to identify the optimal deployment pattern for any given sensor coverage requirement has yet to be found. Considering the ease of sensor deployment and operation, the deployment patterns should be identical and symmetric in the deployment region. This implies that the Voronoi diagram of the optimal deployment is a regular tessellation. Based on the fact that there exist only three regular tessellations, we propose a framework, namely, range elimination scheme (RES), to compute the optimal k-coverage deployment pattern for any given k value to accommodate various wireless sensor application requirements. We apply RES to show the optimal k-coverage deployment patterns for 4 ≤ k ≤ 9. Our analytical and simulation results show that our proposed framework successfully identifies the optimal deployment patterns and significantly reduces the number of sensors to be deployed.