New approximations for Maximum Lifetime Coverage

Abstract

In this article dedicated to Professor Yue Minyi on the occasion of his 95th birthday, we present a new polynomial-time approximation scheme for the well-known Maximum Lifetime Coverage problem in wireless sensor networks. For any , this scheme contains an approximation algorithm with performance , which improves the performance ratio of previously known approximation in the literature.

Keywords:

• Maximum Lifetime Coverage
• sensor cover
• minimum weight set cover
• approximation
• optimal solution

Acknowledgments

All authors are Professor Minyi Yue’s student or student’s students. They respect and appreciate very much the great contributions of Professor Yue on research and education.

Notes

1 By ‘maximal position on the left side’ we mean the disk has the leftmost intersection point with some horizontal line, and that intersection point is at least distance left of the cell among all sensing disks of sensors lying in . For example, in Figure 3, and have maximal position on the right side, due to their intersections with lines and , respectively, but does not have maximal position on the right side. Similar meaning holds for ‘maximal position on the right side’, ‘maximal position on the upper side’ and ‘maximal position on the lower side’.

This work was supported in part by the National Science Foundation of USA under [grant number CNS101630], [grant number CCF0829993].