Energy-Efficient Task Mapping for Data-Driven Sensor Network Macroprogramming

Abstract : Data-driven macroprogramming of wireless sensor networks (WSNs) provides an easy to use high-level task graph representation to the application developer. However, determining an energy-efficient initial placement of these tasks onto the nodes of the target network poses a set of interesting problems. We present a framework to model this task-mapping problem arising in WSN macroprogramming. Our model can capture placement constraints in tasks, as well as multiple possible routes in the target network. Using our framework, we provide mathematical formulations for the task-mapping problem for two different metrics -- energy balance and total energy spent. For both metrics, we address scenarios where a) a single or b) multiple paths are possible between nodes. Due to the complex nature of the problems, these formulations are not linear. We provide linearization heuristics for the same, resulting in mixed-integer programming (MIP) formulations. We also provide efficient heuristics for the above. Our experiments show that our heuristics give the same results as the MIP for real-world sensor network macroprograms, and show a speedup of up to several orders of magnitude. We also provide worst-case performance bounds of the heuristics.
Type de document :
Article dans une revue
IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2010, 59 (7), pp.955-968. 〈10.1109/TC.2009.168〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00723797
Contributeur : Animesh Pathak <>
Soumis le : vendredi 7 septembre 2012 - 15:13:39
Dernière modification le : mardi 17 avril 2018 - 11:34:36
Document(s) archivé(s) le : samedi 8 décembre 2012 - 02:55:08

Fichier

pathak-prasanna-taskmapping-TC...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Animesh Pathak, Viktor Prasanna. Energy-Efficient Task Mapping for Data-Driven Sensor Network Macroprogramming. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2010, 59 (7), pp.955-968. 〈10.1109/TC.2009.168〉. 〈hal-00723797〉

Partager

Métriques

Consultations de la notice

155

Téléchargements de fichiers

164