Efficient algorithms for probabilistic k-coverage in directional sensor networks
Yongan Wu, Jianping Yin, Min Li, En Zhu, Zheng yu Xie · 2008
The fundamental issue in sensor networks is the quality of monitoring provided by the networks under the energy constraint. The quality is usually measured by coverage. In this paper, unlike previous research, the k-coverage problem is investigated in the directional sensor networks with turnable orientation. Furthermore, probabilistic sensing model is adopted for more realistic than deterministic model. Because the problem is NP-hard, two approximate algorithms, centralized Inter Linear Programming Algorithm (ILPA) and distributed Coverage Benefit Detection Algorithm (CBDA), are proposed. By modelling the problem as an ILP problem, ILPA loosens the integer constraint and converts the optimal LP solution to a feasible ILP solution with a proven approximation guarantee. As a distributed algorithm, CBDA utilizes a back-off timer to decide active sensors and their direction with large coverage benefit. It is proved that the solutions gotten by ILPA and CBDA are feasible. And the time complexity, the communication complexity and the performance ratio are theoretically analyzed. Compared with the best known existing coverage algorithm in directional sensor networks [13], simulation results show that ILPA and CBDA significantly reduce the percentage of active sensors and prolong the network lifetime in some sense.