Convex Combination Approximation for the Min-Cost WSN Point Coverage Problem

摘要

This paper presents a new algorithm for finding better approximation solutions to the min-cost point coverage problem in wireless sensor networks. The problem is to compute a deterministic sensor deployment plan, with minimum monetary cost on sensors, to cover the set of targets spread across a geographical region such that each target is covered by multiple sensors. This is a Max-SNP-complete problem. Our approximation algorithm, called alpha-beta approximation, is a convex combination of greedy LP-rounding and greedy set-cover selection. We show that, through a large number of numerical simulations on randomly generated targets and sites, alpha-beta approximation produces efficiently better approximation results than the best approximation algorithm previously known. In particular, the alpha-beta approximation in our experiments never exceeds an approximation ratio of 1.07. providing up to 14.86% improvement over previous approximation algorithms.