From Task Graphs to Concrete Actions: A New Task Mapping Algorithm for the Future Internet of Things

Abstract : Task mapping, which basically consists of mapping a set of tasks onto a set of nodes, is a well-known problem in distributed computing research. As a particular case of distributed systems, the Internet of Things (IoT) poses a set of renewed challenges, because of its scale, heterogeneity and properties traditionally associated with wireless sensor networks (WSN), shared sensing, continous processing and real time computing. To handle IoT features, we present a formalization of the task mapping problem that captures the varying consumption of resources and various constraints (location, capabilities, QoS) in order to compute a mapping that guarantees the lifetime of the concurrent tasks inside the network and the fair allocation of tasks among the nodes. It results in a binary programming problem for which we provide an efficient heuristic that allows its resolution in polynomial time. Our experiments show that our heuristic: (i) gives solutions that are close to optimal and (ii) can be implemented on reasonably powerful Things and performed directly within the network, without requiring any centralized infrastructure.
Type de document :
Communication dans un congrès
MASS - 11th IEEE International Conference on Mobile Ad hoc and Sensor Systems, Oct 2014, Philadelphia, United States. 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01069838
Contributeur : Benjamin Billet <>
Soumis le : mardi 30 septembre 2014 - 09:34:49
Dernière modification le : lundi 5 octobre 2015 - 16:58:11
Document(s) archivé(s) le : mercredi 31 décembre 2014 - 10:25:48

Fichier

algo-mapping.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01069838, version 1

Collections

Citation

Benjamin Billet, Valérie Issarny. From Task Graphs to Concrete Actions: A New Task Mapping Algorithm for the Future Internet of Things. MASS - 11th IEEE International Conference on Mobile Ad hoc and Sensor Systems, Oct 2014, Philadelphia, United States. 2014. 〈hal-01069838〉

Partager

Métriques

Consultations de
la notice

294

Téléchargements du document

389