Maximizing a Submodular Utility for Deadline Constrained Data Collection in Sensor Networks
The authors 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. Their 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, they consider the class of monotone sub-modular utility functions defined on subsets of nodes, which is more appropriate for the applications they consider. While sub-modular maximization subject to a cardinality constraint has been well understood, their problem is more challenging due to the multi-hop data forwarding nature even under a simple interference model.