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
4Workshop RECAP Rennes mars 2006
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.
5Workshop RECAP Rennes mars 2006
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)
6Workshop RECAP Rennes mars 2006
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…
7Workshop RECAP Rennes mars 2006
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
8Workshop RECAP Rennes mars 2006
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
9Workshop RECAP Rennes mars 2006
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
10Workshop RECAP Rennes mars 2006
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.
11Workshop RECAP Rennes mars 2006
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
12Workshop RECAP Rennes mars 2006
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
13Workshop RECAP Rennes mars 2006
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
14Workshop RECAP Rennes mars 2006
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
15Workshop RECAP Rennes mars 2006
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
16Workshop RECAP Rennes mars 2006
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
17Workshop RECAP Rennes mars 2006
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� …
18Workshop RECAP Rennes mars 2006
Windows ordonnée selon un attribut
19Workshop RECAP Rennes mars 2006
DSMS
Scratch Store
Architecture Générale de STREAM
Input streams
RegisterQuery
StreamedResult
StoredResult
Archive
StoredRelations
20Workshop RECAP Rennes mars 2006
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”
21Workshop RECAP Rennes mars 2006
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
22Workshop RECAP Rennes mars 2006
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
25Workshop RECAP Rennes mars 2006
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?
26Workshop RECAP Rennes mars 2006
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
27Workshop RECAP Rennes mars 2006
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
28Workshop RECAP Rennes mars 2006
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
29Workshop RECAP Rennes mars 2006
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
30Workshop RECAP Rennes mars 2006
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
32Workshop RECAP Rennes mars 2006
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
33Workshop RECAP Rennes mars 2006
Query Language (TinySQL)
SELECT ,
[FROM {sensors | }]
[WHERE ]
[GROUP BY ]
[SAMPLE PERIOD | ONCE]
[INTO ]
[TRIGGER ACTION ]
34Workshop RECAP Rennes mars 2006
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
35Workshop RECAP Rennes mars 2006
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.”
36Workshop RECAP Rennes mars 2006
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
37Workshop RECAP Rennes mars 2006
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
38Workshop RECAP Rennes mars 2006
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
39Workshop RECAP Rennes mars 2006
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
41Workshop RECAP Rennes mars 2006
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
42Workshop RECAP Rennes mars 2006
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
Q
Q
Q
Q
Q QQ
R:{…}
R:{…}
R:{…}
R:{…} R:{…}
43
Tiny DB advanced queries
aggregation and joins
44Workshop RECAP Rennes mars 2006
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!
45Workshop RECAP Rennes mars 2006
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
46Workshop RECAP Rennes mars 2006
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
47Workshop RECAP Rennes mars 2006
Illustration: In-Network Aggregation
1
2
23
14
4
54321
1
2 3
4
5
2
Sensor #
Interval 3SELECT COUNT(*) FROM sensors
Interval #
48Workshop RECAP Rennes mars 2006
Illustration: In-Network Aggregation
1
312
23
14
4
54321
1
2 3
4
5
31
Sensor #
Interval 2SELECT COUNT(*) FROM sensors
Interval #
49Workshop RECAP Rennes mars 2006
Illustration: In-Network Aggregation
51
312
23
14
4
54321
1
2 3
4
5
5
Sensor #
SELECT COUNT(*) FROM sensors Interval 1
Interval #
50Workshop RECAP Rennes mars 2006
Illustration: In-Network Aggregation
51
312
23
14
14
54321
1
2 3
4
5
1
Sensor #
SELECT COUNT(*) FROM sensors Interval 4
Interval #
51Workshop RECAP Rennes mars 2006
Illustration: In-Network Aggregation
zzzzzzzzzzzz51
zzzzzz312
zzz2zzzzzz3
1zzzzzzzzz4
1zzzzzzzzz4
54321
1
2 3
4
5
1
Sensor #
SELECT COUNT(*) FROM sensors Interval 4
Interval #
52Workshop RECAP Rennes mars 2006
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
53Workshop RECAP Rennes mars 2006
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
54Workshop RECAP Rennes mars 2006
In-Network “Join” Processing (REED)
� Complex data filtering in sensor networks
55Workshop RECAP Rennes mars 2006
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
56Workshop RECAP Rennes mars 2006
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
57Workshop RECAP Rennes mars 2006
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
58Workshop RECAP Rennes mars 2006
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
59Workshop RECAP Rennes mars 2006
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}
60Workshop RECAP Rennes mars 2006
Table Distribution
� Group members figure out amongst themselves how the table will be divided across group
� Table flooded to network
61Workshop RECAP Rennes mars 2006
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
62Workshop RECAP Rennes mars 2006
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
63Workshop RECAP Rennes mars 2006
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
64Workshop RECAP Rennes mars 2006
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
65Workshop RECAP Rennes mars 2006
Sources utilisées
� présentations de Sam Madden MIT (http://db.lcs.mit.edu/madden)
66Workshop RECAP Rennes mars 2006
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
67Workshop RECAP Rennes mars 2006
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)