Data selection for maximum coverage in sensor networks with cost constraints

In many deployments of wireless sensor networks (WSNs), the primary goal is to collect and deliver data from many nodes to a data sink. This goal must be met while considering limited resources, such as battery life, in the wireless nodes. In this work, we propose considering the content of generated data to make intelligent data and node selection decisions. We formally present the problem of maximizing coverage of this collected data while restricting individual node costs to remain within a given budget and provide an algorithm that provides the optimal solution. Next we consider the related problem of finding the optimal long-term average coverage subject to average cost constraints and give its solution, which uses Lyapunov Optimization techniques. For real world implementations, we also provide computationally feasible approximation algorithms of both problems along with proven bounds on their performance, including a novel technique that uses virtual queues for the average maximum coverage problem. Finally, we provide simulation results of all proposed algorithms. These results not only demonstrate the benefits of considering data content in scheduling, but also show the advantages from using the long-term average solution and the near-optimal performance of our greedy virtual queue approximation algorithm.