Surface Coverage in Wireless Sensor Networks

Coverage is a fundamental problem in Wireless Sensor Networks (WSNs). Existing studies on this topic focus on 2D ideal plane coverage and 3D full space coverage. The 3D surface of a targeted Field of Interest is complex in many real world applications; and yet, existing studies on coverage do not produce practical results. In this paper, we propose a new coverage model called surface coverage. In surface coverage, the targeted Field of Interest is a complex surface in 3D space and sensors can be deployed only on the surface. We show that existing 2D plane coverage is merely a special case of surface coverage. Simulations point out that existing sensor deployment schemes for a 2D plane cannot be directly applied to surface coverage cases. In this paper, we target two problems assuming cases of surface coverage to be true. One, under stochastic deployment, how many sensors are needed to reach a certain expected coverage ratio? Two, if sensor deployment can be planned, what is the optimal deployment strategy with guaranteed full coverage with the least number of sensors? We show that the latter problem is NP-complete and propose three approximation algorithms. We further prove that these algorithms have a provable approximation ratio. We also conduct comprehensive simulations to evaluate the performance of the proposed algorithms.