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.
Type de document :
Communication dans un congrès
WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.116-123, 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00763393
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : lundi 10 décembre 2012 - 16:38:05
Dernière modification le : mercredi 12 décembre 2012 - 10:25:58
Document(s) archivé(s) le : lundi 11 mars 2013 - 12:46:10

Fichier

p116-zheng.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00763393, version 1

Collections

Citation

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, 2012. 〈hal-00763393〉

Partager

Métriques

Consultations de la notice

59

Téléchargements de fichiers

77