Embed Size (px)
Citation preview
Traitement de données massives dans les réseaux de
capteurs sans filElmahdi Driouch
sous la supervision de: Prof. Wessam Ajib
24 février 2015
1
Plan
• Motivations• Données massives• IoT et réseaux de capteurs
• Réseaux de capteurs et traitement de données• MapReduce• Formulation du problème• Analogie avec « Facility location »
• Travaux futurs• Conclusion
2
Big Data: défini en 4V et traité en 4C
• « Ensembles de données qui ne peuvent être saisies, gérées et traitées par les systèmes traditionnels »
• 4 V’s (Gartner 2001 puis 2011)• Volume• Vélocité• Variété• Véracité (IBM) or Valeur (IDC)
• 4 C’s (Jim Gray)• Capturer• « Curate » (ETL)• Calculer• Communiquer
3
IoT: sources de données massives
• Selon Vint Cerf:Internet des objets (IoT) = Internet des capteurs
• Caractéristiques des données du IoT• Des données à très grand échelle (dimension temporelle)• Hétérogénéité• Corrélation dans le temps et l’espace• Une petite portion des données est importante
4
Big Data dans Hype cycle de Gartner (2014)
5
IoT dans le Hype cycle de Gartner (2015)
6
2022: Un billion de capteurs?
source: http://tsensorssummit.org/Resources/TSensors%20Roadmap%20v1.pdf7
Big Data en 4 phases
1. Génération des données• depuis plusieurs sources: Internet, données d’entreprise, IoT, médical,…
2. Acquisition des données• inclut la collecte, le transport et le pré-traitement
3. Stockage des données4. Analyse des données
8
Réseau de capteurs (simplifié) Capteurs
Sink(ex. centre
de données) Liens sans fil
9
Réseaux de capteurs sans fil
• Les capteurs peuvent disposer d’une source d’énergie renouvelable Les contraintes d’énergie sont de plus en plus surmontables
• Les capteurs possèdent des processeurs plus performants et des mémoires plus grandes
ils sont près à faire des calculs plus complexes• Augmenter le traitement effectué dans le réseau (in-network
processing)
10
MapReduce par l’exemple (1/4)
« Je vis à MontréalJe vis à Montréalà Montréal je vis
Mais que pensez-vousde la vie à Laval? »
je: 3vis: 3à: 4
Montréal: 3Mais: 1que: 1
…
11
MapReduce par l’exemple (2/4)
« Je vis à MontréalJe vis à Montréal
à Montréal je visMais que pensez-vous
de la vie à Laval? »
{Je: 2,vis: 2,à: 2,Montréal:2}
{à: 1,Montréal: 1,…}
{à: 1,la: 1,…}
{je: 3vis: 3à: 4
Montréal: 3Mais: 1que: 1
…}
12
MapReduce par l’exemple (3/4)
« Je vis à MontréalJe vis à Montréal
à Montréal je visMais que pensez-vous
de la vie à Laval? »
{Je: 2,vis: 2,à: 2,Montréal:2}
{à: 1,Montréal: 1,…}
{à: 1,la: 1,…}
{Je: 3,à: 4,la: 1}
{vis: 3,Mais: 1,…}
{Montréal: 3,Laval: 1,…}
13
MapReduce par l’exemple (4/4)
« Je vis à MontréalJe vis à Montréal
à Montréal je visMais que pensez-vous
de la vie à Laval? »
{Je: 2,vis: 2,à: 2,Montréal:2}
{à: 1,Montréal: 1,…}
{à: 1,la: 1,…}
{Je: 3,à: 4,la: 1}
{vis: 3,Mais: 1,…}
{Montréal: 3,Laval: 1,…}
MAP REDUCE
14
Réseau étudié Capteurs
Sink(ex. centre
de données) Liens sans fil
15
Traitement dans le réseau
mapper of k1
mapper of k1
mapper of k2
reducer of k1
reducer of k2
16
Traitement dans le réseau
mapper of k1
mapper of k1
mapper of k2
reducer of k1
reducer of k2
Capteurrécolteurd’énergie 17
Formulation du problème
• Minimisation du temps total requis pour le traitement des données
• Le temps est en relation direct avec les niveaux d’énergie disponibles
• Décider des capteurs mappers et ceux reducers (et leurs clés)
• Sous plusieurs contraintes• niveaux d’énergie• qualité des canaux sans fil• architecture physique du réseau et des
capteurs• quantités de données capturées
mapper of k1
mapper of k1
mapper of k2
reducer of k1
reducer of k2
18
Problème de localisation des installations
• Ensemble de clients• Chaque client possède une
demande• Ensemble d’endroits pour ouvrir
des installations• Matrice des distances (clients,
installations)• Coûts d’ouverture des
installations
Clients Installations
D1
D2
D3
DN
O1
O2
O3
OM
19
Problème de localisation des installations
Minimiser (coûts d’ouverture + coûts de transport)
Sous contrainteCapacité de chaque installation
Chaque client est associé à une installationChaque client est servi en totalité
Clients Installations
D1
D2
D3
DN
O1
O2
O3
OM20
Analogie avec « Facility location »
• Ensemble des mappers (tous les capteurs)
• Chaque mapper peut traiter un ensemble paires (clé, valeur)
• Ensemble des reducerspotentiels (les capteurs récolteurs d’énergie)
• Matrice des distances (nombre de sauts ou qualité des canaux)
• Coûts d’activations des reducers
• Ensemble de clients• Chaque client possède une
demande• Ensemble d’endroits pour ouvrir
des installations• Matrice des distances (clients,
installations)• Coûts d’ouverture des
installations
21
Différences avec « Facility location »
• Différences avec le problème original• les mappers peuvent traiter plusieurs clés
(les demandes des clients sont plutôt hétérogènes)• Un reducer peut traiter plusieurs types de clé
(un reducer, un fois activé, est associé à un ou plusieurs clés)• Un capteur peut être reducer et/ou mapper• Nature stochastique du problème
(la variation des énergies récoltées selon le temps, la variation des qualités des canaux selon le temps)
• Le problème est au moins aussi difficile que « Facility location »
22
Travaux futurs
• Une modélisation plus précise du problème
• Proposition d’algorithmes distribués pour la résolution du problème(ex. s’inspirer des « facility location games »)
• Proposition d’algorithmes centralisés basé sur une approche « software defined networking »
23
Conclusion
• Les données massives présentent plusieurs défis • pour les réseaux sans fil en général• pour les réseaux de capteurs en particulier
• Les capteurs et le IoT constitueront la source majeure de données massives dans un futur proche
• Un traitement de données dans le réseau (In-network) est essentiel pour des solutions IoT viables
24
