Bases de donné Bases de donn ééées et es et rrréréééseaux de capteursseaux de ...defude/RECAP06-BDCapteurs.pdf · 2006. 3. 15. · 2 Workshop RECAP Rennes mars 2006 Plan 1

1

Bases de donnBases de donnBases de donnBases de donnéééées et es et es et es et

rrrrééééseaux de capteursseaux de capteursseaux de capteursseaux de capteurs

Bruno DefudeGET-Institut National des Télé[email protected]

http://www-inf.int-evry.fr/~defude

2Workshop RECAP Rennes mars 2006

Plan1. Introduction

• BD & Mobilité

• Requêtes Continues, Flots de Données

2. Bases de données de capteurs

1. TinyDB (modèle de données & langage de requêtes)

2. TinyDB (évaluation de requêtes complexes)

3. Conclusion et problèmes ouverts

3

Introduction


Capteurs : le point

� Véritable petit processeur� Capteur de lumière, champ magnétique, accélération, son, etc.� Canal radio en half-duplex, ne peut pas émettre et recevoir à la

fois (917MHz, 50 kb/s)� Le coût de transmission est élevé / exécution processeur (envoi

1 bit = 800 instructions)� Problème de batterie : 5,5 Millions de messages (30 octets), càd

1 msg/s chaque jour pendant 2 mois.� En général broadcast/diffusion, les voisins reçoivent même s’ils

ne sont pas destinataires.


Nature des données des capteurs ?

� Données des capteurs sont fournies par

traitement du signal (mesures, détection,…)

� Chaque élément de donnée du capteur a une estampilleN.B. {[ti, vi]} = BD Historique/ Temporelle

� Données provenant d’un seul capteur ou d’un groupe (nécessité d’agrégation)


Gestion de données

� Modèles de données : Relationnel, Object, Semi-structuré, …

� Persistance : Modèle, Stockage

� Langages de requêtes & API : SQL,QBE, OQL, QL+PL…

� Optimisation de requêtes

� Intégrité et sécurité des données : contraintes, droits d’accès,

crypto,..

� Gestion de transaction : cohérence, concurrence, reprise

� Systèmes & Architectures : SGBD (des smartcards aux

architectures spécialisées), Client(s)/Server(s), Web, P2P/Grid,

MOBILE…


Langages de requêtes

� Quoi et non comment : indépendance des données� Langages déclaratifs� SQL, QUEL, QBE, OQL, XQUERY� Évaluation de requêtes

� Pull vs push� Requêtes continues� Requêtes dépendantes de la localité� Exacte vs approchée� Tous vs top-k� Statique vs dynamique


Optimisation de requêtes� Indépendance des données

� stockage, localisation, distribution, partition, réplication

� transformations algébriques(relationnel, objet, …)

� Réécriture de requêtes

� sélection d’un plan d’accès optimal :

� modèle de coûtMin (αN+βP+γM) � à base de règles

� Statique vs. Dynamique

� Méta-données, statistiques, administrateur


Requêtes sur réseau de capteurs ?

Requêtes à la SQL sur un réseau de capteurs� Accès à un grand ensemble de capteurs� Accès associatif, indépendant de l’organisation

physique du réseau (approche BD)

Exemple #1: Chaque minute, avoir une mesure dans la région X

Exemple #2: Quand deux capteurs distants de 12 m détectent un oiseau

envoyer leur emplacement.

Exemple #3: Toutes les 5 minutes, avoir le nombre d’oiseaux dans la

Région X.

Aspects flots de données, événements, spatial


Problèmes “BD réparties” ?

� Modèle pour les données des capteurs� Accès aux données des capteurs� Faibles capacités de stockage et de traitements� Coût d’accès aux données de capteurs� Représenter le réseau de capteurs� Gérer l’aspect dynamique du réseau et le nombre

de noeuds� Prendre en compte les fautes� Minimiser les communications : faire le maximum de

traitements localement.


Techologie BD à réutiliser/adapter� SGBD à petite empreinte (ex. PicoDBMS)� Facile à configurer, zéro administration� évaluation des requêtes : exact/approché,

diffusion, échantillonnage, algos spécifiques� Optimisation de requêtes : trouver une solution

optimale dans un environnement dynamique (adaptatif), minimiser énergie (BD mobiles)

� Traitement des événements : BD Actives, ECA, Publish/Subscribe� Flots de données générés doivent être traités à leur

production

� BD sur flots de données: requêtes continues, optimisation


Caractéristiques environnement mobile

� Déconnexions fréquentes� Bande passante variable (55kbs à 100Mbs)� Coût de communication peut être élevé� MU ont des capacités limitées

� Batteries� Puissance de calcul� Mémoire secondaire


Problèmes liés aux données mobiles (1/2)

� Réplication & Cache

� Contraintes de cohérence différentes� Réplication optimiste vs pessimiste� Nouveaux algos de cache (broadcast, cohérence,

invalidation ...)� Evaluation de requêtes : Pull / Push

� Diffusion de données vers une MU� Broadcast disk� Requêtes continues� Requêtes dépendantes de la localisation


Problèmes liés aux données mobiles (2/2)� Transactions : nouveaux modèles (ACID?)

� Transaction Mobile : une transaction où au moins une MU estimpliquée dans l’exécution

� Produits : PointBase, Navajo de Poet, Oracle Lite, DB2 Every Place, Sybase Anywhere, SQL Server CE

� Recherche : Clustering, Two-tier replication, Pro-motion,

Reporting, Semantics-based, Kangaroo transactions, MDSTP,

Moflex transactions…� Reprise

� Partitionnement de réseau fréquent� Déconnexion n’est pas (toujours) une panne� Plus de journalisation


Requêtes dépendantes de la localisation

1. Trouver l’hôtel le moins cher à Paris

2. Trouver l’hôtel le moins cher et le plus près

3. Trouver l’hôtel le moins cher et le plus près / où je serai dans une heure

1 : requête classique BD spatiale (et temporelle)

2 : suppose une géo localisation de l’utilisateur qui peut être immobile ou mobile

3 : utilisateur mobile : le localiser et prévoir sa trajectoire


Flots de données� Flots continus, non bornés, “rapides”, liés au temps de données

élémentaires� Présents dans de nombreuses applications

� Surveillance de réseau et ingénierie de trafic� Réseaux de capteurs, tags RFID� Logs des opérateurs télécoms� applications financières� logs Web� E-sciences� …

�� DSMSDSMS = Data Stream Management System


Windows� Méchanisme pour extraire une relation finie d’un flot

infini� De nombreuses variations

� Windows définie sur un attribut ordonné (e.g., temps)� Windows définie par un nombre de tuples� Windows définie par des marqueurs explicites� …


Windows ordonnée selon un attribut


DSMS

Scratch Store

Architecture Générale de STREAM

Input streams

RegisterQuery

StreamedResult

StoredResult

Archive

StoredRelations


Exemple Q1

Deux Flots : (avec estampille pour chaque tuple)Commandes (cID, client, cout)Prise_charge (cID, employe)

Coût total des commandes prises en charge le jour précédent par “Sue” pour le client “Joe”

Select Sum(C.cout)

From Commandes C, Prise_charge P [Range 1 Day]

Where C.cID = P.cID

And P.employe = “Sue”

And C.client = “Joe”


Q2

Sur un échantillon de 10% du flot des prises en charge, prendre les 5 plus récentes par employé et renvoyer le coût maximum

Select P.employe, Max(C.cout)

From Commandes C, Prise_charge P

[Partition by employe ROWS 5] 10% SAMPLE

Where C.cID=P.cid

Group by P.employe


Problèmes des DSMS

� Relations : ensemble de tuples ou séquences?� BD types de màj ? Ajout seulement?� Requête immédiate ou continue ?� Résultat exact ou approché ?� Évaluation de requête en une passe ou + ?� Plan d’exécution figé ou adaptatif ?� Ressources limitées (ex. mémoire) � Nécessité de traiter les données en temps réel

23

Bases de données sur réseaux

de capteurs

Workshop RECAP Rennes mars 2006

Some Sensornet Apps

redwood forest

microclimate

monitoring

smart cooling

in data centers

condition-based

maintenance

And More…

• Homeland security

• Container monitoring

• Mobile environmental apps

• Bird tracking

• Zebranet

• Home automation

• Etc!

structural

integrity


Data Management Landscape

Stable Store(DBMS)

Field Tools

Local Servers

Internet

Client Tools GUIs,etcExternal Tools

Sensor Network

TinyD

B

Server-side

applications

Data management Issues:

APIs for current + historical access?

Which data when?

How to act on data?

Network and node status?


High Level (Query Based) Interfaces

are Good� Programming Apps is Hard

� Limited power budget� Lossy, low bandwidth communication� Require long-lived, zero admin deployments� Distributed Algorithms� Limited tools, debugging interfaces

� Queries abstract away much of the complexity� Burden on the database developers� Users get:

� Safe, optimizable programs� Freedom to think about apps instead of details


TinyDB: Declarative Query Interface to

Sensornets� Platform: Berkeley Motes + TinyOS� Continuous variant of SQL : TinySQL

� Power and data-acquisition based in-network optimization framework

� Extensible interface for aggregates, new types of sensors


TinyDB Revisited

SELECT MAX(mag) FROM sensors WHERE mag > threshSAMPLE PERIOD 64ms

High level abstraction:

Data centric programming

Interact with sensor network as a whole

Extensible framework

Under the hood:

Intelligent query processing

Fault Mitigation

App

Sensor Network

TinyDB

Query, Trigger

Data

Cougar is very similar


Feature Overview

� Declarative SQL-like query interface

� Metadata management

� Multiple concurrent queries

� In-network, distributed query processing

� Extensible w/ new attributes, commands,

aggregates

� In-network, persistent storage


TinyDB GUI

TinyDB Client APIDBMS

Sensor network

Architecture

TinyDB query

processor

0

4

1

5

2

6

7

JDBC

Mote side

PC side

8

31

TinyDB Interface


Data Model

� Entire sensor network as one single, logical table: sensors

� Columns consist of all the attributes defined in the network

� Typical attributes:

� Sensor readings

� Meta-data: node id, location, etc.

� Internal states: routing tree parent, timestamp, queue length, etc.

� Nodes return NULL for unknown attributes


Query Language (TinySQL)

SELECT ,

[FROM {sensors | }]

[WHERE ]

[GROUP BY ]

[SAMPLE PERIOD | ONCE]

[INTO ]

[TRIGGER ACTION ]


Comparison with SQL

� Single table in FROM clause� Only conjunctive comparison predicates in WHERE

and HAVING� No subqueries� No column alias in SELECT clause� Arithmetic expressions limited to column op constant� Only fundamental difference: SAMPLE PERIOD

clause


TinySQL Examples

SELECT nodeid, nestNo, lightFROM sensorsWHERE light > 400SAMPLE PERIOD 1s

1

2

1

2

1

NodeidNodeid

405251

422171

389250

455170

LightLightnestNonestNoEpochEpoch

Sensors

“Find the sensors in bright nests.”


TinySQL Examples (cont.)

3

3

3

3

CNT(…

)

520

370

520

360

AVG(…)

South0

North1

South1

North

region

0

Epoch

“Count the number occupied nests in each loud region of the island.”

SELECT region, CNT(occupied) AVG(sound)

FROM sensors

GROUP BY region

HAVING AVG(sound) > 200

SAMPLE PERIOD 10s

3

Regions w/ AVG(sound) > 200

SELECT AVG(sound)

FROM sensors

SAMPLE PERIOD 10s

2


Event-based Queries

� ON event SELECT …

� Run query only when interesting events happens

� Event examples� Button pushed� Message arrival� Bird enters nest

� Analogous to triggers but events are user-defined� Wired into TinyOS events


Query over Stored Data

� Named buffers in Flash memory� Store query results in buffers� Query over named buffers� Analogous to materialized views

� Example:� CREATE BUFFER name SIZE x (field1 type1, field2 type2, …)� SELECT a1, a2 FROM sensors SAMPLE PERIOD d INTO name� SELECT field1, field2, … FROM name SAMPLE PERIOD d


Extending TinyDB

� Why extend TinyDB?� New sensors � attributes� New control/actuation � commands� New data processing logic � aggregates� New events

� Analogous to concepts in object-relational databases

40

TinyDB Internals


Inside TinyDB

� ~10 000 lines embedded C code� ~ 5 000 lines (PC-side) Java� ~ 3 200 bytes RAM (w/ 768 byte heap)� ~ 58 KB compiled code

� 3x larger than 2nd largest TinyOS Program


Tree-based Routing

� Tree-based routing� Used in:

� Query delivery � Data collection� In-network aggregation

� Tree formation well studied� ETX Metric (Woo ‘03,

DeCuoto ‘03)

A

B C

D

FE

Q:SELECT …

Q Q

Q

QQ

Q

Q

Q

Q

Q QQ

R:{…}

R:{…}

R:{…}

R:{…} R:{…}

43

Tiny DB advanced queries

aggregation and joins


Tiny Aggregation (TAG)

� In-network processing of aggregates� Common data analysis operation

� Aka gather operation or reduction in || programming� Communication reducing

� Operator dependent benefit� Across nodes during same epoch

� Exploit query semantics to improve efficiency!


Basic Aggregation

� In each epoch:� Each node samples local sensors once� Generates partial state record (PSR)

� local readings � readings from children

� Outputs PSR during assigned comm. interval� Interval assigned based on depth in tree

1

2 3

4

5 Interval 1

2

33

4

• At end of epoch, PSR for whole network output at root

• New result on each successive epoch


Illustration: In-Network Aggregation

1

2

3

14

4

54321

1

2 3

4

5

1

Sensor #

Interval #

Interval 4SELECT COUNT(*) FROM sensors

Sample Period

Time



1

2

23

14

4

54321

1

2 3

4

5

2

Sensor #


Interval #



1

312

23

14

4

54321

1

2 3

4

5

31

Sensor #


Interval #



51

312

23

14

4

54321

1

2 3

4

5

5

Sensor #

SELECT COUNT(*) FROM sensors Interval 1

Interval #



51

312

23

14

14

54321

1

2 3

4

5

1

Sensor #


Interval #



zzzzzzzzzzzz51

zzzzzz312

zzz2zzzzzz3

1zzzzzzzzz4

1zzzzzzzzz4

54321

1

2 3

4

5

1

Sensor #


Interval #


Aggregation Framework

• As in extensible databases, TinyDB supports any aggregation function conforming to:

Aggn={finit, fmerge, fevaluate}

Finit {a0} →

Fmerge {,} →

Fevaluate {} → aggregate value

Example: Average

AVGinit {v} →

AVGmerge {, } → < S1 + S2 , C1 + C2>

AVGevaluate{} → S/C

Partial State Record (PSR)

Restriction: Merge associative, commutative


Hypothesis Testing, Snooping

COUNT : monotonicAVG : non-monotonic

Monotonicity

Routing RedundancyMIN : dup. insensitive,AVG : dup. sensitive

Duplicate Sensitivity

Applicability of Sampling, Effect of Loss

MAX : exemplaryCOUNT: summary

Exemplary vs. Summary

Effectiveness of TAGMEDIAN : unbounded, MAX : 1 record

Partial StateAffectsExamplesProperty

Taxonomy of Aggregates

� TAG insight: classify aggregates according to various functional properties� Yields a general set of optimizations that can automatically be applied


In-Network “Join” Processing (REED)

� Complex data filtering in sensor networks


Example Filter Query

Timestamp Temp

3:05PM 74

MinTS MaxTS MinTemp MaxTemp

2:00PM 2:30PM 70 75

2:30PM 3:00PM 73 78

3:00PM 3:30PM 75 80

3:30PM 4:00PM 83 88

4:00PM 4:30PM 85 90

4:30PM 5:00PM 70 75

5:00PM 5:30PM 72 77

5:30PM 6:00PM 75 80

Join Predicate:

TS > MinTS && TS < MaxTS && (Temp < MinTemp || Temp > MaxTemp)

X

Sensor Data

Predicate Table


Naïve Join Algorithm

• Send all tuples from

data table to root;

perform join at root

Root 0Main PC Controller

1 2

3 4 5

6 7

B

C

D

A

X

BX

X

Predicate Table


Ideal Join Algorithm

Root 0Main PC Controller

1 2

3 4 5

6 7

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

XXB X

XX

• Send join table to

each node

• At node, perform

join

• Problem: Severe

Node Memory

Constraints


X

REED Algorithm 1

• Cluster nodes into groups

• Store portion of predicate

table in each group member

• Send sensor data tuples to

every member of group

Root 0

1 2

3 4 5

6 7

X D

8

X

A

B

C

D

A

B

C

D

A

B

C

D

X

XXX


Group Formation

1

43

Neighbor list: {1, 2, 3, 4, 6}

Broadcast: Want to make group

Choose Me!

{1, 3, 4, 6}

Space: 4

Space: 4

CurrList: {1}

Potential: {1, 2, 3, 4, 6}

Space: 8

CurrList: {1, 4}

Potential: {1, 3, 4, 6}

Choose Me!

{1, 3, 4}

Space: 2

Space: 10

CurrList: {1, 3, 4}

Potential: {1, 3, 4}

Group Accepted:

{1, 3, 4}

6

Neighbor list: {1, 3, 4} Neighbor list: {1, 3, 4, 6}

Neighbor list:

{1, 4, 6}


Table Distribution

� Group members figure out amongst themselves how the table will be divided across group

� Table flooded to network


Conclusions

� Beaucoup de travaux ces dernières années sur les flots de données

� Première génération de DSMS, premières vraies applications

� Deux projets importants de BD sur réseaux de capteurs TinyDB et Cougar

� Premiers prototypes, un ou deux déploiements

� Premiers résultats encourageants mais de nombreux problèmes restent à résoudre

� à l’intersection de systèmes embarqués, BD, réseaux


Problèmes ouverts BD & capteurs

� Model-driven data acquisition � Exploiter les corrélations entre les données

� Optimisation multi-requêtes� Approche Cross-layer (e.g modèle de

communication + modèle évaluation requêtes)

� Stockage des données sur les capteurs (cache, …)

� Hétérogénéité des capteurs


Problèmes ouverts BD & capteurs (2)

� Acquisitional Query Processing� Acquisition de données généralement coûteuse� Intégrer dans tout le processus d’évaluation/optimisation de

requêtes (e.g quand faire l’acquisition, comment entrelacer sélection/acquisition efficacement)

� Sélectionner le sous-ensemble de nœuds permettant de résoudre une requête donnée� Construction d’index (range-partitionning) type P2P� Balancer gain vs coût construction + maintenance index


UbiMob 20063e Journées Francophones Mobilité et Ubiquité

5 - 8 septembre 2006

Conservatoire National des Arts et Métiers - Paris

http://www.ece.fr/ubimob06

Date limite de soumission des articles courts, démonstrations, tutoriels et ateliers

16 mai 2006

Date limite de soumission des articles longs

31 mars 2006


Sources utilisées

� présentations de Sam Madden MIT (http://db.lcs.mit.edu/madden)


Bibliographie

� L. Golab & T. Ozsu, Issues in Data StreamManagement. ACM SIGMOD Record, June 2003.

� Y. Yao, J. E. Gehrke. Query Processing in SensorNetworks. In Proceedings CIDR 2003, January 2003

� S. R. Madden, M. J. Franklin, J. M. Hellerstein, andW. Hong. TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks. OSDI, December 2002.

� S. R. Madden, M.J. Franklin, J.M. Hellerstein, andW. Hong. The Design of an Acquisitional QueryProcessor for Sensor Networks. ACM TODS


Bibliographie (2)

� V. Goebel, T. Plagemann. Data StreamManagement Systems: Applications, Concepts andSystems, Tutorial presented at MIPS 2004 Conference, Grenoble

� J. Gehrke, S. Madden. Query Processing in SensorNetworks, IEEE Pervasive Computing, jan-march2004

� Michel Adiba « Données ambiantes, continues et mobiles » Tutoriel à UbiMob05

� The STREAM group. Stanford Data StreamManagement System, to appear 2006 (voir http://www-db.stanford.edu/stream)

Documents

Bases de donné Bases de donn ééées et es et rrréréééseaux de capteursseaux de ...defude/RECAP06-BDCapteurs.pdf · 2006. 3. 15. · 2 Workshop RECAP Rennes mars 2006 Plan 1