Maximizing a Submodular Utility for Deadline Constrained Data Collection in Sensor Networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

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

Résumé

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.
Fichier principal
Vignette du fichier
p116-zheng.pdf (422.42 Ko) Télécharger le fichier
Origine : Accord explicite pour ce dépôt

Dates et versions

hal-00763393 , version 1 (10-12-2012)

Identifiants

  • HAL Id : hal-00763393 , version 1

Citer

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⟩

Collections

WIOPT2012
31 Consultations
69 Téléchargements

Partager

Gmail Facebook X LinkedIn More