Collecting data in ad-hoc networks with reduced uncertainty

摘要

We consider the data gathering problem in wireless ad-hoc networks where a data mule traverses a set of sensors, each with vital information on its surrounding, and collects their data. The mule goal is to collect as much data as possible, thereby reducing the information uncertainty, while minimizing its travel distance. We show that the problem is solvable by a generalized version of the Prize Collecting Steiner Tree Problem, and present a dual-primal 6-approximation algorithm for solving it. Simulation results show that the proposed schema converges to the optimal results for varying set of topologies, such as grids, stars, linear and random networks.