Maximizing a submodular utility for deadline constrained data collection in sensor networks

We study the utility maximization problem for data collection in sensor networks subject to a deadline constraint, where the data on a selected subset of nodes are collected through a routing tree rooted at a sink subject to the 1-hop interference model. Our problem can be viewed as a Network Utility Maximization (NUM) problem with binary decisions. However, instead of a separable concave form of system utility commonly seen in NUM, we consider the class of monotone submodular utility functions defined on subsets of nodes, which is more appropriate for the applications we consider. While submodular maximization subject to a cardinality constraint has been well understood, our problem is more challenging due to the multi-hop data forwarding nature even under a simple interference model. We have derived efficient approximation solutions to this problem both for raw data collection and when in-network data aggregation is applied.