Skip to Main content Skip to Navigation
Conference papers

Maximizing a Submodular Utility for Deadline Constrained Data Collection in Sensor Networks

Abstract : 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.
Complete list of metadata
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Monday, December 10, 2012 - 4:38:05 PM
Last modification on : Wednesday, December 12, 2012 - 10:25:58 AM
Long-term archiving on: : Monday, March 11, 2013 - 12:46:10 PM


Explicit agreement for this submission


  • HAL Id : hal-00763393, version 1



Zizhan Zheng, Ness B. Shroff. Maximizing a Submodular Utility for Deadline Constrained Data Collection in Sensor Networks. WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.116-123. ⟨hal-00763393⟩



Record views


Files downloads