Maximum Lifetime Temporal Q-Coverage in Directional Sensor Networks
Xianling Lu, Deying Li, Wenping Chen, Yuqing Zhu, Hongwei Du and Zhiming Ding
Directional sensors networks have been employed in various surveillance applications. Target coverage is a fundamental problem in such applications. In some applications, the coverage requirements change with the time. However, none of the existing works on target coverage takes into account the time-dependent characteristic of requirements. In this paper, we study the Maximum Lifetime Temporal Q-Coverage (MLTQC) problem in directional sensor networks. Given m targets with known locations and an energy constrained directional sensor network composed by n sensors, each of which has p sectors, the MLTQC problem is to schedule sensors to switch sectors to maximize the network lifetime such that each target ol is covered by at least ql (ql ≥ 1) sectors in vulnerable time of a period and by at least one sector in any other time of the period. We formulate the problem into an Integral Programming and compute the upper bound of the network lifetime for the problem. Then we present a relaxation-rounding algorithm based on the relaxation LP. Finally, we propose a greedy algorithm for the MLTQC problem. Simulation results demonstrate the performance of our algorithms.
Keywords: Directional sensor network; target coverage; scheduling; temporal Q-coverage; relaxation-rounding algorithm.