Approximating Maximum Lifetime $k$ -Coverage Through Minimizing Weighted $k$ -Cover in Homogeneous Wireless Sensor Networks
Zhao Zhang, James K. V. Willson, Zaixin Lu, Weili Wu, Xuding Zhu, Ding‐Zhu Du · IEEE/ACM Transactions on Networking · 2016
Energy efficiency is an important issue in the study of wireless sensor networks. Given a set of targets and a set of sensors with bounded lifetime, the maximum lifetime k-coverage problem is to schedule active/sleeping status of sensors to maximize the time period during which every target is covered by at least k active sensors. Previously, it was known that when the sensing ranges are uniform, this problem has a polynomial time (4+ε)-approximation for k = 1 and (6+ε)-approximation for k = 2. In this paper, we make significant progress by showing that for any positive integer k, there exists a polynomial-time (3 + ε)-approximation.