Submodular Utility Maximization for Deadline Constrained Data Collection in Sensor Networks

We study the utility maximization problem for data collection in a wireless sensor network subject to a deadline constraint, where the data on a selected subset of nodes are collected through a routing tree subject to the 1-hop interference model. Our problem is closely related to the traditional utility maximization problems in networking and communications. However, instead of a separable concave form of utility functions commonly seen in this area, 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 the 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.