The Coverage Problem in Three-Dimensional Wireless Sensor Networks

One of the fundamental issues in sensor networks is the coverage problem, which reflect-show well a sensor network is monitored or tracked by sensors. In this paper, we formulate this problem as a decision problem, whose goal is to determine whether every point in the servicearea of the sensor network is covered by at least α sensors, where ff is a given parameter andthe sensing regions of sensors are modeled by balls (not necessarily of the same radius). This problem in a 2D space is solved in [10] with an efficient polynomial-time algorithm (in termsof the number of sensors). In this paper, we show that tackling this problem in a 3D space is still feasible within polynomial time. Further, the proposed solution can be easily translated intoan efficient polynomial-time distributed protocol. We demonstrate an application of the derived result by proposing an energy-conserving scheduling protocol.