CAPITOLO IV
TinyDB
TinyDB è un sistema di gestione di “data stream” che semplifica la pro-grammazione e l’esecuzione di applicazioni di monitoring su Reti di Sen-sori. La semplificazione avviene mediante l’utilizzo di un linguaggio dichia-rativo. Con il TinyDB il programmatore non si deve preoccupare di dover scrivere codice di basso livello per i Nodi Sensore. Infatti TinyDB, che vie-ne eseguito sulla piattaforma Berkeley Mica Mote con il sistema operativo TinyOS (vedi appendice A e appendice B), fornisce una semplice interfac-cia ti tipo SQL tramite la quale è possibile specificare i dati che si vogliono estrarre e altri parametri addizionali come ad esempio la frequenza con cui tali dati devono essere aggiornati. Una volta specificati questi parame-tri TinyDB, in modo automatico e autonomo, raccoglie i dati dai sensori, li filtra, li aggrega e infine li rende visibili all’utente. Tutta l’elaborazione vie-ne fatto cercando di minimizzare il consumo evie-nergetico.
Il sistema può essere suddiviso in due sottosistemi come illustrato in Figura 4-1 [TinyDB]:
• Sensor Network Software: gira su ciascun nodo della rete ed è a sua volta composto da:
o Sensor Catalog & Schema manager:il catalog è responsabile di tener traccia del set di attributi, dei tipi di letture (es : light, sound, voltage) e le proprietà disponibili su ciascun nodo (es: nodeId). In generale questa lista non è la stessa per o-gni nodo. Lo schema descrive le capacità dei nodi presenti
nel sistema tramite “tabelle virtuali” così come si intendono nelle basi di dati tradizionali;
o Scheduling and Power Management: il TinyDB prevede dei meccanismi per ottimizzare la comunicazione tra i Nodi Sen-sore e quindi per risparmiare energia;
o Query processor: usa il catalog per prelevare i valori degli at-tributi locali; riceve le rilevazioni degli altri nodi vicini, combi-na e aggrega questi valori insieme, filtra i dati indesiderati e invia i valori di output al nodo padre. Inoltre TinyDB estende TinyOS con una semplice gestione della memoria basata sugli eventi.
o Network topology Management: TinyDB gestisce la connetti-vità dei nodi nella rete.
• Java based client interface: interfaccia che permette di accedere al-la rete dei TinyDB motes dal client PC o Basestation. Questa inter-faccia consiste in un set di classi java e di applicazioni.
4.1
Base di Dati nel TinyDB
TinyDB fornisce un approccio di alto livello dichiarativo per specificare le
query, cioè le interrogazioni. Si descrive “cosa si vuole” e non “come si vuole”. [TinyDB]
TinyDB esegue implicitamente le interrogazioni su una singola e infinita tabella logica chiamata sensors: questa tabella ha una colonna per ogni attributo presente nel catalog (inclusi gli attributi dei sensori, i nodeID); i-noltre la tabella concettualmente contiene una riga per ogni lettura genera-ta da ciascun Nodo Sensore e quindi può essere visgenera-ta come una genera-tabella il cui numero di righe è in continua crescita al passare del tempo.
Per permettere una maggiore comprensione del linguaggio di interroga-zione di TinyDB introduciamo una Rete di Sensori esemplificativa. Suppo-niamo di avere un appartamento composto da 5 stanze (Figura 4.2) e che in tale appartamento siano disposti dei Nodi Sensore come riportato in
da un NodeId che lo identifica univocamente (infatti in TinyDB ogni nodo deve avere un ID) e da un RoomId che identifica la stanza in cui il nodo si trova. Supponiamo inoltre che in ogni nodo siano presenti i seguenti sen-sori: sensore di luminosità (light), sensore di rumore (sound) e il sensore di temperatura (temp).
Figura 4-1: Architettura TinyDB di un elaboratore di interrogazioni per reti si sensori
event eventcold
evento che risulta verificato quando la temperatura rilevata dal sensore risulta inferiore ai 18 °C . Inoltre su ogni Nodo Sensore è definita la primiti-va :
SetSnd(int n)
Che,se invocata, produce sul nodo un suono di durata n secondi.
Figura 4.2:Appartamento esemplificativo
4.2
Linguaggio di’interrogazione del
TinyDB
TinyDB fornisce un linguaggio di interrogazione simile all’SQL e da ora in
poi chiameremo questo linguaggio TinySQL. Così come in SQL, le
inter-rogazioni in TinySQL consistono in un set di attributi da selezionare (es light, temperature), un set di espressioni per creare risultati aggregati, un set di predicati per filtrare i risultati e opzionalmente espressioni di
grou-ping per partizionare i dati prima di effettuare l’aggregazione. A differenza dell’SQL le interrogazioni iniettate in una Rete di Sensori devono essere eseguite ripetitivamente e devono fornire risultati periodicamente (il perio-do che intercorre tra la ricezione di due risultati viene detto epoch). La du-rata di una epoch può essere direttamente specificata nella interrogazio-ne TinySQL.
Tutte le interrogazioni TinySQL hanno la seguente struttura generale:
Figura 4.3:Rete di Sensori esemplificativa
Sensore Stanza
Nodo Sensore n°1 Room 1
Nodo Sensore n°2 Room 1
Nodo Sensore n°3 Room 2
Nodo Sensore n°5 Room 3
Nodo Sensore n°6 Room 4
Nodo Sensore n°7 Room 5
Nodo Sensore n°8 Room 5
Nodo Sensore n°9 Room 5
Tabella 4.1:Nodi Sensore nella rete esemplificativa
[ON event:] SELECT select-list [FROM sensors] WHERE where-clause [GROUP BY gb-list] [HAVING having-list]
[TRIGGER ACTION command-name[(param)] [EPOCH DURATION integer]
[LIFETIME integer] [..] = opzionali
Ad esempio, l’interrogazione: SELECT nodeid, light, temp FROM sensors
EPOCH DURATION 1s FOR 10s
Specifica che ogni sensore deve riportare il proprio Id,la luce e la tempe-ratura rilevata, una volta ogni 10 secondi.
Da notare che il periodo di campionamento (sample period) deve essere
come minimo pari al tempo che un nodo impiega ad elaborare e a tra-smettere un singolo messaggio radio più il tempo necessario ad effettuare
alcune elaborazioni locali (circa 30 ms incluso il tempo medio di backoff utilizzato dal protocollo MAC in un ambiente a bassa contesa).
I tipi di interrogazioni attualmente supportati dal TinyDB sono:
• Event-based query: query la cui esecuzione è scaturita dal verifi-carsi di un evento (paragrafo 4.2.1 ) [Madden TinyDB]
• Lifetime-based query: query in cui viene specificato la durata tem-porale della query (paragrafo 4.2.2 ) [Madden TinyDB]
• Aggregate query: query per creare risultati aggregati (paragrafo 4.2.3 ) [Madden TinyDB]
• Trigger query:query che al verificarsi di un evento scaturiscano una determinata azione sul nodo (paragrafo 4.2.4) [Madden TinyDB] • Query over flash : query tramite le quali è possibile creare ed
utiliz-zare buffer locali al nodo (paragrafo 4.2.5 ) [Madden TinyDB]
4.2.1 EVENT-BASED QUERY
Questo tipo di interrogazioni vanno in esecuzione quando si verifica un evento (es. il rilevamento effettuato da un sensore è maggiore di una de-terminata soglia).
Una interrogazione di tipo event-based è del tipo: ON event:
SELECT ...
Oltre all’interrogazione è necessario definire e registrare l’evento sui Nodi Sensore (nella nostra Rete di Sensori esemplificativa abbiamo supposto di avere a disposizione l’evento eventcold)
Esempio: ON eventcold:
SELECT nodeid,light
Al verificarsi dell’evento eventcold, cioè quando la temperatura rilevata da un sensore risulta inferiore ai 18 °C, il nodo si attiva e inizia a campionare la luce una volta al secondo per 10 secondi.
Gli eventi sono fondamentali nel TinyDB in quanto permettono al sistema di rimanere inattivo fino a quando non accade qualche condizione esterna: in questo modo è possibile avere una significativa riduzione del consumo di energia (Figura 4-4).
Gli eventi possono essere usati anche per stoppare l’esecuzione di una in-terrogazione. Basta appendere ad una interrogazione la proposizione del tipo :
STOP ON EVENT(param) WHERE cond(param)
4.2.2 LIFETIME-BASED QUERY
Al posto di un tempo di campionamento è possibile specificare in una in-terrogazione, tramite la proposizione LIFETIME <x>, il tempo di vita dell’interrogazione. Specificare un tempo di vita è un modo più semplice ed intuitivo per gli utenti per ragionare in termini di consumo di energia.
Poiché molti processori sono dotati di linee di interrupt esterne che posso-no far risvegliare il sistema allora gli eventi possoposso-no apportare un grande risparmio energetico. Nella Figura 4-4 è riportato il consumo energetico dell’esecuzione di una event-query usando gli interrupt (parte superiore della Figura 4-4) e tramite una tecnica di polling (parte inferiore della Figura 4-4).
Specialmente nel monitoraggio di scenari ambientali gli utenti non sono in-teressati a piccoli aggiustamenti del tempo di campionamento e in partico-lar modo non capiscono come tali aggiustamenti influiscano sul consumo di batterie; comunque gli utenti sono molto interessati al tempo di vita dell’interrogazione.
Esempio:
SELECT nodeid, light FROM sensor
LIFETIME 30 days
Questa interrogazione specifica che il campionamento della luminosità deve essere effettuato per almeno 30 giorni ad un rate tale da soddisfare il tempo di vita.
Per soddisfare questo vincolo (lifetime) TinyDB effettua una stima del tempo di campionamento in base al tempo di vita indicato nell’interrogazione ed all’energia (in joule) che rimane a disposizione di ogni nodo.
È possibile inserire nell’interrogazione la proposizione opzionale MIN SAMPLE RATE r che deve essere soddisfatta (naturalmente queste cose valgono per le interrogazioni basate sul lifetime e non per quelle in cui è specificato l’intervallo di campionamento).
In questo modo se la frequenza di campionamento calcolata da un nodo risulta maggiore della frequenza r ,allora il nodo procede con la frequenza calcolata, altrimenti la trasmissione avviene alla frequenza r e il nodo è costretto ad eliminare o ad aggregare alcuni campioni.
4.2.3 AGGREGATE QUERY
Sono interrogazioni il cui risultato è dato dall’applicazione di operatori ag-gregati. La maggior parte delle elaborazioni per l’aggregazione dei risultati viene effettuata proprio dai Nodi Sensore nella rete.
In generale una interrogazione di tipo aggregato ha la seguente sintassi: SELECT {agg(expr), attrs} FROM sensors
WHERE {selPreds} GROUP BY {attrs} HAVING {havingPreds} EPOCH DURATION
Dove agg può essere: COUNT, AVG, MAX o MIN.
Un esempio in cui risulta utile l’utilizzo di questo tipo di interrogazione è quello di richiedere la temperatura media rilevata dai sensori disposti in una stanza:
SELECT AVG(Temp) FROM sensors
EPOCH DURATION 10s
Ogni 10 secondi al nodo Sink arriva la media delle temperature rilevate dai sensori (rilevamenti effettuati ogni 10 s). Un esempio dei risultati ottenibili tramite una interrogazione di questo tipo è riportato nella Tabella 4-2. Invece tramite la seguente interrogazione:
SELECT roomNo, AVG(Temp) FROM sensors
GROUP BY roomNo
HAVING AVG(Temp) > 23 EPOCH DURATION 10s
Viene rilevata la temperatura media di ogni stanza solo se questa risulta superiore a 23 °C. Ad esempio i risultati ottenibili con questo tipo di inter-rogazione sono riportati nella Tabella 4-3.
4.2.4 TRIGGER QUERY
TinyDB include la possibilità di dichiarare interrogazioni che eseguono cer-ti comandi quando viene rilevata una determinata condizione. Attualmen-te, le azioni possono essere intraprese solo in risposta a letture dei senso-ri che soddisfano le condizioni specificate nella proposizione WHERE. Le interrogazioni aggregate non possono contenere azioni di output. L’azione da intraprendere e’ un comando definito nello schema del nodo ed e’ so-stanzialmente una chiamata ad una funzione di sistema.
Epoch AVG(Temp)
0 24
1 25
Tabella 4-2: Risultati aggregate query
Epoch roomNo AVG(Temp)
0 1 25
0 2 24
1 1 26
1 2 25
Tabella 4-3: Risultati aggregate query
Attualmente TinyDB offre come semplici azioni di output l’attivazione lumi-nosa di LED e l’emissione di suoni.
Si supponga di voler emettere un suono di allarme ( per 512ms ) quando la temperatura vicino ai sensori supera i 18°C ; ciò può essere realizzato tramite la seguente interrogazione:
SELECT temp FROM sensors WHERE temp> 18
TRIGGER ACTION SetSnd(512) EPOCH DURATION 512
4.2.5 QUERY OVER FLASH
Il TinyDB permette di formulare interrogazioni che vadano ad agire nella memoria flash del Nodo Sensore.
La sintassi per creare una tabella nella flash:
CREATE BUFFER name SIZE x
( field1 type, field2 type, ... )
In questo modo viene creata una tabella chiamata name, con spazio per x righe (tuple) e ciascuna riga è formata dai campi specificati alla fine dell’interrogazione.
Per popolare la tabella creata è necessario lanciare una interrogazione del tipo:
SELECT field1, field2, ... FROM sensors
EPOCH DURATION x INTO name
Il numero e il tipo dei campi elencati nella select devono coincidere con quelli elencati nell’interrogazione CREATE BUFFER .. precedente. Il rate massimo che è possibile specificare per inserire i dati nella tabella è 1 campione ogni 64ms.
Per selezionare valori da una tabella: SELECT field1, field2, ...
SAMPLE PERIOD y FROM name
Questa interrogazione preleva i valori dalla tabella partendo dall’inizio del-la tabeldel-la e scorrendodel-la verso il basso (del-la tabeldel-la viene vista come un buffer circolare).
È possibile cancellare l’intera memoria flash (ancora non è possibile can-cellare una singola tabella) tramite la proposizione:
4.3
Disseminazione delle Interrogazioni
e raccolta dei risultati in TinyDB
Analizziamo ora il supporto offerto dal TinyDB al linguaggio di interroga-zione TinySQL. In particolare in seguito sono ricostruite le ‘tappe’ percorse da una interrogazione a partire dall’immissione nell’interfaccia grafica of-ferta dal TinyDB fino a quando i risultati sono raccolti e visualizzati.
Per prima cosa introduciamo alcuni concetti basilari presenti nell’architettura software del TinyDB.
4.3.a Catalog
Il Catalog fornisce un’interfaccia unificata di un certo numero di compo-nenti di TinyOS e permette di “chiamare” eventi e comandi(Figura 4-5).[Madden Thesis]
Infatti si possono registrare comandi che possono essere usati nelle inter-rogazioni tramite la direttiva OUTPUT ; è possibile inoltre registrare eventi che si riferiscono a comportamenti asincroni da usare nelle event-based
query.
Il Catalog contiene inoltre i metadati. Ogni nodo mantiene un catalogo di metadati che descrive i propri attributi locali , gli eventi e le funzioni defini-te dall’udefini-tendefini-te. [Madden Thesis]
I metadati sono registrati nel sistema tramite un linking statico effettuato al
tempo di compilazione e usando il linguaggio di programmazione del
tin-yOS (il NESC: linguaggio simile al C).
Gli eventi e gli attributi sono resi accessibili dalle interrogazioni dichiaran-doli in un file di interfaccia e fornendo una semplice funzione handler: ad esempio, per ricavare la topologia della rete, il TinyOS Network compo-nent definisce l’attributo parent di tipo integer e registra un handler che ri-torna l’identificatore del padre nell’albero di routing corrente(vedi 4.3.c). Ci sono diversi tipi di metadati:
Metadati riguardanti eventi: ciascun evento è caratterizzato dai seguenti campi:
Nome dell’evento Firma Frequenza stimata La frequenza stimata viene poi usata dall’ottimizzatore sul Sink per l’ottimizzazione di tipo EVENT QUERY BATCHING (vedi 4.3.3).
Figura 4-5: Il catalog fornisce un’interfaccia per accedere ai sensori e allo stato interno del TinyOS
Metadati riguardanti funzioni definite dall’utente: ciascuna funzione definita dall’utente è composta dai seguenti campi:
Nome Firma Selettività stimata
(fornita dall’utente) Metadati associati ad un attributo: per ogni attributo sono presenti i se-guenti campi:
Sample Time (s) – tempo per campionare l’attributo Constant – indica se l’attributo e’ costante
Rate of Change ( units/s ) – quando velocemente cambia l’attributo
Range – range di valore che l’attributo puo’ assumere
I metadati associati agli attributi vengono usati dalla basestation essen-zialmente in due occasioni:
• Ottimizzazione dell’Interrogazione: paragrafo 4.3.3.
• Disseminazione dell’Interrogazione ed elaborazione dei risultati. Metadati per aggregazione : ogni aggregato contiene dei metadati tramite i quali il nodo può effettuare le elaborazioni necessarie sui dati da aggrega-re che arrivano. Ogni aggaggrega-regato consiste di taggrega-re funzioni: una per l’inizializzazione, una per effettuare il merge, e una per effettuare l’update
del valore finale o dell’aggregato parziale che riceve dalla rete.
Metadati per il costo di computazione e la consegna dei risultati : sono u-sati nella interrogazioni basate su lifetime.
I metadati sono contenuti nel Catalog e sono periodicamente inviati alla radice e usati dall’ottimizzatore.
4.3.b Sincronizzazione tra i Nodi Sensore
E’ necessario che i nodi sincronizzino i loro clock in modo che questi siano concordi sui tempi di attività e spegnimento. I sensori sincronizzano i loro clock ascoltando un clock reference che è periodicamente inviato in modo
broadcast dalla radice. Tale messaggio contiene la lettura corrente del
clock sulla basestation. I nodi al livello uno dell’albero di routing sincroniz-zano il loro clock e ritrasmettono il messaggio includendo il loro time-stamp.
4.3.c Albero di Routing e Albero di Routing Semantico
L’albero di routing viene costruito effettuando l’inoltro di una routing re-quest (che non è altro che una interrogazione in TinyDB) attraverso tutti i nodi della rete. La basestation (la radice dell’albero) invia la richiesta, tutti i nodi vicini che ascoltano questa richiesta la processano e la inviano a loro volta ai loro vicini e così via fino a quando l’intera rete non ha ricevuto la richiesta. Ogni richiesta contiene anche un hop-count che indica la distan-za dalla basestation del nodo che ha ricevuto la richiesta. Un nodo sceglie come padre il nodo che è più vicino alla radice dell’albero: nel caso ci sia-no più sia-nodi allo stesso livello dell’albero allora viene scelto il sia-nodo con la più alta qualità del link di comunicazione.
Ciascun padre ha la responsabilità di effettuare l’inoltro ai propri nodi figlio delle richieste inviate dalla basestation e di inviare verso la basestation sia i propri risultati sia i risultati dei nodi figlio.
È possibile che siano presenti contemporaneamente più di un albero di
routing nel caso in cui i nodi tengano traccia di più di un genitore: questa tecnica può essere usata per supportare interrogazioni simultanee con ra-dici diversi.
L’SRT o Albero di Routing Semantico è invece un albero di routing costrui-to per permettere a ciascun nodo di determinare in modo efficiente se qualche figlio necessita di partecipare a una interrogazione su un attributo costante.
Dato un attributo A ciascun nodo si memorizza un intervallo unidimensio-nale rappresentante il range dei valori assunti da A su ciascuno dei propri figli. Quando una interrogazione q con un predicato riguardante A (es A>100) arriva al nodo n, il nodo guarda se qualche nodo figlio ha un ran-ge di A che si sovrappone al predicato dell’interrogazione In questo caso il nodo n fa l’inoltro dell’interrogazione sul figlio (o sui figli) e si prepara a ri-cevere il risultato; altrimenti l’interrogazione o è applicata solo localmente (se il predicato è soddisfatto) oppure è cancellata.
La costruzione dell’SRT può essere schematizzata in quattro passi signifi-cativi:
1) la richiesta di costruzione dell’SRT è inoltrata a tutti i nodi della rete: questa richiesta include anche il nome dell’attributo sopra il quale sarà costruito l’albero semantico;
2) Se un nodo ha dei figli allora inoltra la richiesta ai figli e aspetta le risposte;
3) Se un nodo non ha figli allora sceglie un padre tra i nodi raggiungi-bili e invia al padre un messaggio in cui viene notificata la selezione ed il range dell’attributo su cui deve essere costruito l’SRT;
4) Se un nodo ha dei figli allora riceve i messaggi dai figli e memorizza il range dell’attributo di ogni figlio; dopo sceglie un nodo padre e in-via un messaggio in cui indica il range di valori assunti dall’attributo in quel nodo e nei nodi figli.
La Figura 4-7 mostra un esempio di SRT costruito sull’attributo latitudine. Le frecce grigie indicano il flusso delle interrogazioni dalla radice verso le foglie dell’albero, i nodi grigi devono produrre o effettuare l’inoltro dei risul-tati. L’interrogazione arriva al nodo radice, viene fatto l’inoltro sull’albero ma solo i nodi grigi possono partecipare (nota che il nodo 3 deve fare l’inoltro dei risultati prodotti dal nodo 4 anche se è precluso dall’esecuzione dell’interrogazione).
Sebbene gli SRT siano limitati agli attributi costanti è necessario prevede-re anche delle operazioni di mantenimento. In particolaprevede-re possono esseprevede-re aggiunti nodi nella rete, può cambiare la qualità dei link o nodi esistenti possono cadere.
L’aggiunta di nuovi nodi o la variazione della qualità di un link possono far sì che un nodo decida di cambiare genitore; per fare questo il nodo invia un nuovo messaggio di selezione al nuovo padre.
Per gestire la caduta di un nodo figlio, il nodo genitore associa un timeout a ciascun nodo figlio; ogni volta che il nodo padre riceve un risultato dal nodo figlio il timeout viene azzerato.
Figura 4-6: Albero di routing
Se il nodo padre non riceve messaggi dal figlio per qualche epoch allora assume che il figlio sia andato via e lo rimuove dalla lista dei figli nell’SRT; a questo punto il nodo padre invia ai rimanenti nodi figli la richiesta di in-viare nuovamente i loro range. Queste informazioni vengono usate per costruirsi un nuovo intervallo; se il nuovo intervallo differisce dal preceden-te allora il padre invia un messaggio al proprio padre per notificare il cam-bio del range ed il messaggio viene propagato fino alla radice dell’albero. E’ possibile notare che , tramite l’algoritmo appena descritto, è possibile sfruttare l’SRT anche per attributi non costanti sebbene che, se questi at-tributi cambiano velocemente, il costo della propagazione dei cambiamenti può diventare proibitivo.
Figura 4-7:Albero di routing Semantico usato per la distribuzione di una interrogazione I benefici apportati dall’uso dell’SRT dipendono dalla qualità del clustering dei figli sotto i genitori.
Se i figli di un nodo n hanno valori dell’attributo in considerazione apparte-nente al cluster costruito intorno al valore assunto da tale attributo nel no-do padre allora è probabile che se una interrogazione è applicabile ad un nodo allora sarà applicabile anche ai suoi discendenti.
Nel TinyDB sono previsti 3 tipi di selezione del genitore nella costruzione di un SRT:
• Random parent selection: ciascun nodo seleziona in modo random il padre tra tutti i nodi che sono raggiungibili in modo affidabile;
• closet-parent selection: ciascun nodo seleziona il padre scegliendo (sempre tra i vari nodi raggiungibili) quello che ha il valore dell’attributo chiave più vicino a quello del nodo. In questa modalità il padre deve inviare al figlio, nel messaggio di richiesta di costruzione dell’SRT, anche il valore dell’attributo chiave;
• clustered parent selection: ciascun nodo seleziona il proprio padre come nel metodo precedente con la differenza che se un nodo
‘a-scolta’ un nodo vicini inviare un messaggio di selezione ad un padre, il nodo può spiare il messaggio e vedere il padre selezionato e il valo-re dell’attributo chiave del fratello. Il nodo sceglie quindi il genitovalo-re cercando di minimizzare lo spread dei valori degli attributi dei figli di tutti i padri raggiungibili.
Sono state effettuate delle simulazioni; in particolare prendiamo in consi-derazione una griglia di 20*20 nodi e vediamo di analizzare il numero di nodi che sono coinvolti nell’interrogazione. Il numero minimo di nodi coin-volti è esattamente pari al numero di nodi a cui l’interrogazione è applicabile.
Prendiamo in considerazioni 2 casi:
• caso in cui la distribuzione dei valori dell’attributo chiave sui nodi è randomicamente e uniformemente distribuita nell’intervallo [0,100]. (Figura 4-8).
• Caso in cui i valore assunto da ciascun nodo sull’attributo indice è scelto in base alla disposizione geografica del nodo (in base ad una funzione delle coordinate x e y del nodo). In questo caso si nota che l’uso di una delle tre tecniche appena elencate migliora di molto l’efficienza rispetto al non usare l’RST (Figura 4-9).
4.3.d Lista dei nodi vicini attivi
Ciascun nodo mantiene una piccola lista di vicini di dimensione fissata e monitorizza la qualità del link con i vicini in base ai pacchetti ricevuti da essi.
Tale lista e’ gestita e mantenuta dal tree-based routing protocol.
Per localizzare i vicini il TinyDB sfrutta delle astrazioni messe a disposi-zioni dal TinyOS che realizzano , a basso livello , l’emissione di suo-ni/ultrasuoni per misurare la distanza tra 2 nodi.
Figura 4-8:Scelta del nodo Padre:Rete con attributi distribuiti in modo Random (griglia di 20x20 sensori)
Figura 4-9:Scelta del nodo Padre:Rete con attributi distribuiti in modo geografico (griglia di 20x20 sensori)
4.3.1 Immissione dell’Interrogazione nella Rete
In questa sezione passiamo ad analizzare come una interrogazione viene elaborata, ottimizzata, iniettata nella Rete di Sensori e poi come i risultati prodotti siano recapitati alla basestation.
Per prima cosa l’interrogazione viene digitata nell’editor visuale di
TinyDB.(Figura 4-10) [TinyDB]. A questo punto viene analizzata dalla ba-sestation. In particolare sulla basestation vengono effettuate le attività di parsing, validazione, ottimizzazione e codifica dell’interrogazione.
4.3.2 Parsing e Validazione dell’Interrogazione
Il Parsing e’ fatto solo sulla basestation in quanto richiede un uso intensivo della memoria; pertanto e’ bene che tale attività sia effettuata fuori dalla rete [Madden Thesis]
Figura 4-10: interfaccia grafica TinyDB
La fase di validazione dell’interrogazione può essere suddivisa in sottofa-si:
• SQL Conformity : la basestation verifica che l’interrogazione SQL sia valida dal punto di vista sintattico;
• Validità del rate di Campionamento: la basestation prova a vedere se il rate di campionamento richiesto può essere fornito dal sistema ( ciò e’ dedotto dalle informazioni contenute nei metadata );
• Compatibilità dei tipi e dei nomi : la basestation verifica che i tipi dei campi e gli operatori applicati a questi siano compatibili.
4.3.3 Ottimizzazione dell’Interrogazione
Calcolo della frequenza di campionamento Avviene solo nelle lifetime-based query.
Un nodo può calcolare il rate di campionamento tramite una semplice for-mula. In generale se abbiamo la seguente interrogazione:
SELECT a1 FROM sensors WHERE p
LIFETIME l hours
In base ai parametri indicati nella Tabella 4-4 il primo passo è quello di calcolare la potenza pk disponibile (in ore):
l c
p crem
h = (3.1)
Ora abbiamo bisogno di calcolare l’energia necessaria per campionare e per trasmettere ogni campione:
N N N N selezione di predicato del à Selettivit tupla una e trasmetter per messaggio un ttere per trasme nodo dal spesa energia messaggio un ricevere per nodo dal spesa energia etc..) a3 a2, a1, campionare devo se (es nto campioname ogni per spesa energia 0 ) ( + × + × σ + =
∑
= rcv trans Energiatrans
numSensors s s s E E E C E e (3.2)
È ora possibile calcolare il massimo rate di trasmissione T sostenibile (in campioni per ora):
s h
e p
T = (3.3)
È possibile inserire nell’interrogazione la proposizione opzionale MIN SAMPLE RATE r che deve essere soddisfatta (naturalmente queste cose valgono per le interrogazioni basate sul lifetime e non per quelle in cui è specificato l’intervallo di campionamento).
Parameter Description Units
l Time remaining until lifetime goal is reached hours
ccrem Remaining Battery Capacity Joules
En Energy to sample sensor n Joules
Etrans Energy to transmit a single sample Joules
Ercv Energy to receive a message Joules
σ Selectivity of selection predicate
C Number of children nodes routing through this node
Tabella 4-4:Parametri usati nel calcolo della frequenza di campionamento per una lifetime-based query
In questo modo se il rate di campionamento calcolato risulta maggiore del rate r ,allora il nodo procede con il rate calcolato, altrimenti la trasmissione avviene al rate r e il nodo è costretto a eliminare o a aggregare alcuni campioni. Si hanno cioè due casi:
• T>=r : la basestation sceglie un tempo di campionamento pari a c e quindi la basestation dissemina nella rete la codifica della seguente interrogazione:
select a1, …., an
from sensors
where p
sample interval c
tici(il sistema può essere forzato a combinare o aggregare qualche campione)
Produzione del Piano di esecuzione dell’interrogazione
La basestation stabilisce il piano di esecuzione di una interrogazione: l’attuale versione del TinyDB non prevede ottimizzazioni nella rete del pia-no di esecuzione in quanto si assume che il server abbia una copia-noscenza sufficiente per ottimizzare le interrogazioni prima che queste siano inietta-te nella reinietta-te.
Prima che una interrogazione sia disseminata nella rete, la basestation ef-fettua delle semplici ottimizzazioni. Queste ottimizzazioni sono efef-fettuate per aumentare le performance di esecuzione e ,nel caso di una Rete di Sensori, naturalmente lo scopo principale è quello di ridurre l’energia spe-sa per l’elaborazione dell’interrogazione.
In generale l’ottimizzazione di una interrogazione deve prendere in consi-derazione due importanti fattori:
• Costi energetici per l’acquisizione dei campioni;
• Costi energetici di comunicazione per far pervenire i risultati alla
basestation.
La basestation usa due tecniche per generare il query execution plan
(piano di esecuzione dell’interrogazione).
La prima è detta Ordering of sampling and predicates. Il campionamento è in generale molto costoso dal punto di vista del consumo energetico; comunque, per valutare i predicati sugli attributi è necessario effettuare il campionamento. Una ottimizzazione potrebbe essere effettuata nel calco-lo dei predicati: se un predicato elimina una tupla (cioè l’attributo di una tupla non soddisfa un certo predicato) allora è inutile verificare se la tupla verifica altri sottopredicati; in questi casi è possibile evitare il campiona-mento degli attributi per la verifica dei sottopredicati.
Ad esempio: SELECT eccel,mag FROM sensors WHERE accel > c1 AND mag > c2 SAMPLE INTERVAL 1s
Ci possono essere tre possibili piani di esecuzione:
1) campiono prima mag e accel prima di applicare i predicati
2) campiono mag e dopo applico il predicato (mag>c2) : solo se il predicato è soddisfatto campiono e verifico accel
3) campiono accel e poi verifico: solo se la verifica va a buon fine campiono e verifico mag
Naturalmente la soluzione 1 è sempre più dispendiosa delle altre due so-luzioni. La convenienza tra la soluzione 2 e 3 dipende dalla selettività di c1 e c2 (questo perché si assume che i campioni siano uniformemente distri-buiti nel proprio range di validità). La basestation effettua la scelta sulla base dei metadati che i nodi inviano periodicamente.
L’altra tecnica è invece detta Event query batching to conserve power . In-fatti un’altra ottimizzazione può essere effettuata valutando questa interro-gazione di esempio: (query 1)
ON EVENT e(nodeid) SELECT a1
FROM sensors AS s
WHERE s.nodeid=e.nodeid SAMPLE INTERVAL d FOR k
Questa interrogazione causa una istanza della query interna (select ….) ogni volta che accade l’evento e. L’interrogazione interna campiona ogni d
secondi per una durata di k secondi: a questo punto la query termina. Per quanto appena detto è possibile avere più istanze dell’interrogazione
in-terna in esecuzione contemporaneamente (ad es l’evento e si verifica due volte in un intervallo di tempo minore di k). Questo comporta una ineffi-cienza perché ciascuna istanza dell’interrogazione interna campiona e in-via il risultato indipendentemente dalle altre. Possiamo risolvere questa inefficienza convertendo l’evento esterno dell’interrogazione in un flusso di eventi e riscrivendo l’intero set delle interrogazioni interne indipendenti (adottando il sistema delle sliding window). L’interrogazione assume quin-di la seguente struttura (query 2):
SELECT s.a1
FROM sensors AS s, event AS e WHERE s.nodeid=e.nodeid AND e.type= e
AND s.time - e.time <= k AND s.time > e.time SAMPLE INTERVAL d
In pratica si campiona solo se un evento e si è verificato sul nodo in que-stione da meno di k secondi.
Quando arriva un evento questo è aggiunto al buffer degli eventi; quando arriva una tupla di sensor gli eventi più vecchi di k secondi sono eliminati dal buffer e viene fatto il join di s con gli altri eventi.
Il vantaggio di questo approccio è che c’è in esecuzione una sola interro-gazione alla volta indipendentemente dalla frequenza di arrivo degli eventi di tipo e .
Questa ottimizzazione permette un grande risparmio nei consumi come è illustrato nella Figura 4-11. Async. Events sono le curve relative a l’esecuzione della prima interrogazione (cioè quella non ottimizzata) al va-riare della frequenza di apparizione degli eventi di tipo e; invece la curva
stream join è reativa all’esecuzione dell’interrogazione ottimizzata (notare che è indipendente dalla frequenza di arrivo dell’evento di tipo e)
Da notare che tra le due interrogazioni(non ottimizzata e ottimizzata ) c’è una leggera differenza: mentre la prima campiona sempre relativamente all’istante in cui si verifica l’evento la seconda campiona relativamente
all’istante in cui si verifica il primo di un set consecutivo di eventi. Ad e-sempio, se abbiamo due eventi di tipo e in successione:
e1 accade al tempo t1 e2 accade al tempo t2
Con la prima interrogazione si campiona ai tempi: t1, t1+d, t1+2d, t1+3d …. e ai tempi: t2, t2+d, t2+2d, t2+3; invece con la seconda, se t2-t1<k, si campiona solo agli istanti: t1, t1+d, t1+2d, t1+3d ….
Molte volte, questa ‘inefficienza’ è pressoché trascurabile ai fini dei risultati che l’utente vuole ottenere ma può essere ad esempio risolta acquisendo più campioni ogni d secondi (a questo punto bisogna però vedere se que-sto sovraccarico non mi renda la query 1 migliore)
Figura 4-11:risultati tecnica Event query batching to conserve power
4.3.4 Traduzione dell’interrogazione SQL in
rappresenta-zione binaria
Le interrogazioni sono tradotte da SQL in una rappresentazione binaria per eliminare il bisogno di un SQL-parser su ciascun sensore e per ridurre la dimensione del messaggio. La codifica è riportata nella Tabella 4-5:
Field Description
Query ID A unique identifier for the query. The basestation chooses this id by consulting the root of the network about currently running queries. Sensors ignore broadcasts of queries that they are already running. Root Node The id of the root node where results will be collected; the
basestation typically chooses this id by consulting the root node for its id, altough a query could be disseminated from a node that is different from the location where its result will be collected. Number of Fields The number of fields in the SELECT list of the query Number of
Expressions
The number of expressions in the WHERE, SELECT, and HAVING lists of the query
Sample Period The number of milliseconds between samples
Duration The numner of samples for witch the query will run, or 0 if the query should runnig immediately
Destination Buffer The number of samples for which results should be written (see SELECT INTO below)
Triggering Event The name and condition of the event that triggers this query, NULL if the query should begin running immediately.
Field Data Variable length data containing names and transformations of fields in the SELECT list as well as the name of the storage point from witch the field should be selected, if it is not sensors. Names are translated into integer-ids in each device’s local catalog after query delivery.
Expression Data Variable length data containing filters from the WHERE clause, as well as HAVING expressions and aggregates from the SELECT list Tabella 4-5:Campi in un TinyDB Query message
4.3.5 Disseminazione dell’interrogazione
L’interrogazione analizzata e codificata dalla basestation può essere a questo punto disseminata nella Rete di Sensori: per fare questo si utilizza l’albero di Routing o l’albero di Routing Semantico analizzati nei paragrafi precedenti.
Nel TinyDB è prevista la possibilità che nodi confinanti condividano inter-rogazioni:questa tecnica permette la disseminazione di interrogazioni an-che a quei nodi an-che sono stati aggiunti alla rete in un secondo momento o
query result inviato dal nodo s confinante e nota che il query-id a cui la trasmissione si riferisce è relativo ad una interrogazione che non è presen-te in n, allora n invia un query Request message al nodo s. [Madden Thesis]
4.3.6 Elaborazione dell’Interrogazione
Una volta che l’interrogazione arriva su un nodo inizia la fase di processing. Questa fase si divide in due sottofasi:Preprocessing ed ese-cuzione.
Il preprocessing viene attuato quando l’interrogazione arriva al sensore per la prima volta e per prima cosa viene effettuata una validazione. L’obbiettivo e’ di controllare proprietà dell’interrogazione che non possono essere controllate dalla parte server. Date le limitate capacità dei sensori , ci aspettiamo che la maggior parte della validazione sia fatta sul server. Tuttavia, poiché la connessione del server alla Rete di Sensori non e’ per-sistente, e’ possibile che il server non abbia la conoscenza di tutti i campi e di tutte le tabelle nella rete. Inoltre viene effettuato l’eventuale ricalcolo del rate di campionamento. Infatti la frequenza di campionamento indicata
dalla basestation può essere accettato dal Nodo Sensore oppure
quest’ultimo può abbassare il rate in base alle proprie disponibilità energe-tiche. Effettuate tutte queste operazioni preliminare ci si prepara all’esecuzione vera e propria dell’interrogazione, vengono cioè settate le strutture dati interne ed effettuate le allocazioni per le strutture tempora-nee necessarie per l’esecuzione( ad es nel caso di aggregazione o join ) e il contenimento dei risultati.
A questo punto si entra nella fase di esecuzione: l’interrogazione può an-dare in esecuzione sul nodo (oppure si attende un determinato evento). Anche questa fase può essere suddivisa in sottofasi:
La prima fase viene detta Start up phase: in questa fase viene attivato l’hardware per il sensing richiesto dall’interrogazione. Questa fase ha du-rata variabile dato che il tempo di attivazione del sensore dipende dal tipo di sensore come illustrato nella Tabella 4-6. Subito dopo inizia la fase
piano di esecuzione. Gli operatori di base sono 4 : acquisizione di dati , selezione , aggregrazione , join. Poiché il TinyDB considera il sampling
come operatore si hanno dei vincoli sui possibili piani di esecuzione dell’interrogazione: un campo deve essere acquisito prima che un opera-tore possa esservi applicato. A questo punto si passa alla Codifica dei ri-sultati dove le tuple, prima di essere accodate nel buffer di uscita, sono codificate in un array di bytes. Non sono supportati campi di lunghezza va-riabile (Figura 4-12). Il campo QID coincide con il campo Query ID del
TinyDB query message corrispondente (4.3.4). Il tipo di ciascun campo è
determinato consultando il campo Field Data del TinyDB query message
corrispondente. Alcuni campi possono contenere il valore NULL: questo nel caso in cui un sensore riceve una interrogazione che si riferisce a campi che non sono presenti nel suo catalogo locale (es: se l’interrogazione specifica di campionare la luce e la pressione ma il nodo ha solo un sensore per la pressione). Per indicare i campi che non sono nulli la codifica della tupla prevede 32 bytes (campo notnull nella Figura 4-12): l’i-esimo bit è settato a uno se l’i-esimo campo (field i ) non è nullo. Sensor Time per
Sample (ms)
Startup Time (ms)
Current (mA) Energy Per Sample (@3V),mJ Weather Board Sensors
Solar Radiation 500 800 0,350 0,525 Barometric Pressure 35 35 0,025 0,003
Humidity 333 11 0,500 0,5
Surface Temp 0,333 2 5,6 0,0056
Ambient Temp 0,333 2 5,6 0,0056
Standard Mica Sensors
Accelerometer 0,9 17 0,6 0,0048
(Passive) Thermistor 0,9 0 0,033 0,00009
Magnetomer 0,9 17 5 0,2595
Other Sensors
Organic Byproducts 0,9 >1000 5 >15
Figura 4-12:Formato delle tuple e esempio di layout
Si arriva quindi alla fase di Result delivery : Una volta che un nodo ha pro-dotto il risultato dell’interrogazione(campionamento + operazioni) questo viene accodato in una coda per la consegna al nodo genitore. Questa co-da contiene sia le tuple generate co-dal nodo in locale sia quelle che sono state inviate dagli altri nodi .Quando nella rete ci sono pochi conflitti e il ra-te di trasmissione dei dati è basso, allora la coda può essere svuotata più velocemente del tasso d’arrivo dei pacchetti in coda. Ci sono invece situa-zioni in cui la coda va in overflow e quindi alcune tuple possono andare perse: in queste occasioni il sistema deve decidere se riprovare a trasmet-tere queste tuple oppure adottare altre politiche. Queste sono decisioni che devono essere prese a run-time: un semplice approccio concettuale che può essere seguito è il seguente: ogni qualvolta il sistema è pronto a inviare una tupla è necessario inviare la tupla che aumenta la qualità della risposta che viene fornita all’utente. Naturalmente la metrica adottata per determinare il parametro “qualità” dipende dall’applicazione. Nel TinyDB
sono state implementate diverse politiche di comportamento. Vediamo 3 diversi schemi di priorità da adottare per semplici interrogazioni di sele-zione:
• naive scheme: nessuna tupla è considerata più preziosa di un’altra; la coda è quindi scaricata in modalità FIFO e le tuple che non en-trano in coda sono cancellate
• winavg scheme: simile allo schema precedente con la differenza che, in caso di overflow del buffer viene creato spazio facendo la media delle due tuple in testa alla coda (in questo caso associamo un contatore alla testa della coda per tener conto quante tuple sono associate a quel risultato)
• delta scheme: ad ogni tupla è assegnato un punteggio relativo alla differenza con il più recente valore che è stato trasmesso con suc-cesso. Viene inviata la tupla con il più alto punteggio. In caso di riempimento del buffer vengono eliminate le tuple con un punteggio più basso. Questo schema si basa sul fatto che le tuple che docu-mentano cambiamenti sostanziali sono probabilmente le più inte-ressanti. Con questa tecnica le tuple possono essere consegnate fuori ordine quindi ciascuna tupla viene marcata con un timestamp
per permettere una fedele ricostruzione dell’ordine .
Questi tre approcci sono stati confrontati su un singolo nodo; per controlla-re il loro effetto è stato imposto un rate di campionamento k volte superio-re al rate con cui i messaggi vengono inviati (in media quindi 1 tupla ogni k viene inviata).I risultati sono mostrati nella Figura 4-13.
Infine inizia la fase di Power down : In questa fase i sensori vengono
spenti . Ciò avviene tramite una segnalazione al power managemente
la-yer che provvede ad invocare una funzione di catalogo apposita. L’accensione e lo spegnimento dei sensori può avvenire secondo 3 proto-colli di scheduling:
• basic approach : ciascun nodo si sveglia e si spenge negli stessi i-stanti di tempo per un certo tempo per ogni epoca. Durante l’intervallo in cui e’ sveglio compie le elaborazioni , le comunicazioni , colleziona risultati dai suoi figli e invia i risultati verso la basesta-tion (Figura 4-14);
• slotted approach : ciascuna epoca e’ divisa in un numero fissato di intervalli di tempo numerati in ordine inverso. A ciascun nodo e’ as-segnato un intervallo uguale al suo livello nell’albero di routing. I nodi si svegliano all’inizio del loro intervallo , compiono le elabora-zioni e le comunicaelabora-zioni e quindi tornano a dormire. Nell’intervallo precedente il nodo ascolta la radio e colleziona i risultati dai nodi fi-gli (che sono un livello sotto nell’albero e quindi trasmettono in que-sto intervallo). In queque-sto modo l’informazione all’intervallo 1 rag-giunte la radice (Figura 4-14);
• pipelined approach :è possibile aumentare il throughput adottando un approccio a pipeline;infatti il communication scheduling impone un lower bound al periodo di campionamento in quanto in ogni e-poch il risultato del campionamento deve essere propagato fino alla
basestation. Tramite un approccio a pipeline è possibile aumentare il rate di campionamento(Figura 4-15).
L’approccio slotted e’ da preferire rispetto a quello basic perché c’e’ meno comunicazione in ciascun slot quindi sono possibili un numero minore di collisioni radio ed inoltre i genitori vedono i risultati da tutti i loro figli prima di comunicare alcun dato ai loro genitori ; questo permette ai genitori di combinare o filtrare i risultati dei figli.
L’unico svantaggio dell’approccio a pipeline è che si ha un ritardo nella consegna dei campioni alla basestation: nell’esempio di Figura 4-15 i risul-tati inviati dal nodo H nella Epoch N arrivano alla basestation solo nella epoch N+1. È il sistema a decidere quale dei due approcci usare: in gene-rale, quando è possibile, viene scelto l’approccio slotted.
Figura 4-13:Segnale (figura in alto) approssimato con un delta scheme (figura centrale) e con winavg scheme (figura in basso)
Figura 4-14:Basic Approach e Slotted Approach in TinyDB
4.3.7 Elaborazione nella Rete di Interrogazioni Aggregate
(TAG)
In TinyDB le interrogazioni di tipo aggregato sono gestite da un in-network service chiamato Tiny Agregation (TAG). Questo servizio ha il compito di
intelligente (sia dal punto di vista del tempo sia da quello dell’energia con-sumata) le interrogazioni di tipo aggregato in una Rete di Sensori [Madden TAG]. La prima fase del TAG viene detta Distribution phase in cui le ag-gregation query sono disseminate nella rete ;dopo, nella fase di Collection
i valori aggregati sono instradati dai figli verso i padri: ad ogni epoch cia-scun nodo padre (dell’albero di routing) aspetta fino a quando non ha rice-vuto i risultati dal nodo figlio: dopo aggrega i risultati ricevuti con i propri risultati e propagata il tutto al proprio padre. (Figura 4-16).
Figura 4-16:Collection phase nel TAG
Nella Figura 4-17 è schematizzato una semplice aggregazione effettuata per una interrogazione del tipo select count…..:
È possibile aumentare il throughput adottando un approccio a pipeline. Nella Figura 4-18 è rappresentato un esempio di aggregazione utilizzando un approccio a pipeline.
Il vantaggio nell’uso del TAG sta nel fatto che ogni nodo, indipendente-mente dalla sua posizione nell’albero,deve trasmettere un solo messaggio per epoch; invece, in un approccio centralizzato, i nodi più vicini alla radice devono trasmettere un numero di messaggi molto maggiore rispetto alle foglie o ai nodi dei livelli più alti. La caduta di un nodo risulta tanto più dannosa quanto questo nodo è più vicino alla radice: questo perché alla radice non arrivano informazioni riguardanti tutto il sottoalbero individuato dal nodo che cade (i nodi si riorganizzano e viene scelto un altro padre al posto di quello che non è più raggiungibile ma per fare questo occorre al-meno una epoch e i dati relativi a quella epoch vengono persi). Per au-mentare le prestazioni in caso di perdite è possibile che ciascun nodo si memorizzi i risultati inviati dai nodi figli nelle epoch precedenti e, se in una epoch il nodo non riceve i risultati dai propri figli allora può inviare i risultati precedenti o una interpolazione dei risultati precedenti.
Group by clause:
Le interrogazioni di tipo aggregato possono comprendere anche una pro-posizione del tipo group by expression.
In questo caso viene applicata la tecnica di grouping: ogni nodo stabilisce, in base all’espressione presente nella proposizione group by, a quale gruppo appartiene e, man mano che i risultati fluiscono dai figli verso i no-di genitore, aggiorna i valori aggregati aggiungendo il proprio risultato al gruppo di cui esso fa parte (esempio Figura 4-19) [Madden TAG]
Una interrogazione può contenere anche la proposizione having che
vin-cola il set di gruppi che devono essere presenti nel risultato finale: non sempre è necessario propagare la proposizione having in tutti i nodi dell’albero (durante il processo di disseminazione); l’having clause deve essere inoltrata nell’albero solo se può ridurre la quantità di informazioni inviate. Ad esempio, se la having clause è del tipo: having MAX(attr)>5, non ha senso che sia inoltrata ai nodi in quanto un nodo foglia, pur non ri-spettando l’espressione presente nell’espressione, non può sapere se un altro nodo appartenente allo stesso gruppo soddisfa l’espressione.
Figura 4-19:Esempio di aggregazione di una interrogazione contenente una group-by clau-se
Problema del grouping: il numero di gruppi può eccedere la memoria di-sponibile in un device: in queste occasioni un nodo può decidere di elimi-nare un gruppo inviando il gruppo eliminato al padre il quale deciderà se tenere il gruppo oppure continuare ad effettuare l’inoltro verso la radice dell’albero.
4.3.8 Adattamento del Rate di Trasmissione e
Ottiimizza-zione del Consumo Energetico
Abbiamo visto come TinyDB sia capace di scegliere un rate di trasmissio-ne e di campionamento basato sulle condizioni attuali di carico della rete sul tasso di campionamento richiesto e sul lifetime. Tuttavia questa deci-sioni statiche fatte all’inizio prima di iniziare a processare una interroga-zione possono rivelarsi inesatte dopo alcuni giorni o mesi ed è quindi ria-dattare tali scelte alle condizioni attuali.
Analizziamo il bisogno di adattabilità in due casi: traffico nella rete e con-sumo di energia.
Traffico nella rete: TinyDB monitorizza la contesa sul canale di trasmissio-ne e in modo adattivo riduce il numero di pacchetti inviati non appena si accorge che la contesa aumenta. Questo algoritmo di backoff è molto im-portante in quanto se tanti nodi provano a trasmettere ad alti rate allora il numero di pacchetti consegnati risulta sostanzialmente minore rispetto alla situazione in cui tutto i nodi trasmettono ad un rate minore. Questo risulta-to è rilevabile anche dal grafico di Figura 4-20:
Figura 4-20:Andamento del Delivery rate in funzione del rate di campionamento Il problema è che il ridurre il rate di trasmissione fa riempire velocemente la coda di trasmissione e quindi è probabile che la coda si riempia: a que-sto punto è necessario adottare una delle tre tecniche precedentemente viste(result delivery). È anche vero che, con la tecnica delta anche se si è costretti a scartare delle tuple aumenta comunque la qualità dei risultati trasmessi all’utente finale. Dalla Figura 4-21 è possibile vedere che, nel caso di interrogazioni di selezione effettuata su 4 nodi, la qualità del risul-tati trasmessi risulta molto maggiore nel caso dell’adozione di una tecnica DELTA e rate adattivo piuttosto di una tecnica delta e rate non adattivo. Consumo Energetico.Vediamo ora il problema di adattare il rate di conse-gna delle tuple per venire incontro ad una errata previsione del tempo di campionamento fatta durante l’ottimizzazione dell’interrogazione.
Il sistema può confrontare il valore attuale di energia disponibile con quello stimato. Assumendo che il voltaggio decade linearmente è possibili stima-re nuovamente il consumo di energia e dopo rieffettuastima-re nuovamente le stime sul tempo di campionamento.
Figura 4-21:Confronto tra segnali reali (accelerometer signal e magnetometer signal) e i segnali inviati adottando nessuna tecnica e la tecnica dell’adaptive delta.
4.3.9 Comportamento da router
Poiché le capacità di comunicazione di ciascun nodo sono limitate attual-mente ad un raggio di 100 feet i sensori devono usare i nodi vicini per consegnare i dati alla basestation tramite un’architettura multi hop (usando l’albero di routing o l’albero di routing semantico)
4.3.10
Visualizzazione dei risultati
Una volta che i risultati di una interrogazione arrivano alla basestation
questi vengono visualizzati in modo grafico all’utente. Basic graph visualization
Il TinyDB fornisce una visualizzazione di un singolo attributo in funzione del tempo (Figura 4-22) [TinyDB]
Topology display
Il TinyDB fornisce un’applicazione per la visualizzazione della topologia della rete e l’indicazione qualitativa del valore di un certo attributo tramite l’invio dei risultati della interrogazione ad un modulo di rendering (Figura 4-23) . La topologia della rete e’ ricavata in base all’analisi dei risultati di una particolare interrogazione che la basestation inietta nella rete.
