Implementazione di meccanismi real-time
su sistemi distribuiti data-centrici realizzati
con tecnologie di reti di sensori wireless
Tesi di laurea di:
Daniele Alessandrelli
1
• Tesi svolta presso il ReTiS lab
della Scuola Superiore Sant’Anna
• Motivazione:
– permettere lo sviluppo di applicazioni per
WSN dotate di supporto real-time:
• permetterà l’uso delle WSN in applicazioni
industriali, per la sicurezza, ecc.
• finora l’accento è stato posto su altri aspetti
come il risparmio energetico e l’auto-configurabilità della rete.
• Obiettivo:
– Progettare ed implementare un middleware data-centrico
per WSN dotato di caratteristiche real-time
2
INTRODUZIONE
3
Wireless Sensor Network
• Insieme di nodi
– autonomi (generalmente alimentati a batteria)
– che effettuano misurazioni di grandezze fisiche
sull’ambiente
– che collaborano tra loro comunicando in maniera
wireless
• I nodi sono sistemi embedded dotati di
– funzionalità di rete
– strumenti di misurazione
– un certa capacità computazionale
4
Caratteristiche di un nodo
• Un nodo è equipaggiato con:
–
–
–
–
un micro-controllore (MCU);
uno o più sensori;
una radio;
una sorgente di energia
(generalmente batterie).
• Componenti opzionali:
– moduli per la raccolta di energia
– ASIC supplementari;
– dispositivi supplementari di
comunicazione (RS-232, USB, ecc.).
Sensor 1
Sensor 2
Radio
MCU
• I principali vincoli sono:
–
–
–
–
ridotta capacità computazionale;
scarsità di memoria;
network bandwidth;
consumo energetico
Power supply
5
Wireless Sensor Network
• Peculiarità delle WSN
– flessibilità
– pervasività
– costo ridotto
• Applicazioni:
–
–
–
–
–
militari
ambientali
medico-sanitarie
domestiche
industriali e commerciali
6
LO STANDARD IEEE 802.15.4
Velocità massima 250 kb/s = 62.5 ksym/s
@ 2.4GHz (codifica 16-aria , 1sym = 4 bits);
Traffico real-time
Struttura a superframe (beacon-enabled, 16 slot):
•
Periodo inattivo
•
Periodo attivo
1. CAP (Contention Access Period)
slotted CSMA-CA
2. CFP (Contention Free Period)
GTS (max 7)
Open research topics
• Sfide:
– efficienza energetica
(massimizzare l’autonomia
del nodo)
– gestione della topologia
– data management (estrazione
dell’informazione necessaria)
– code management
(riprogrammazione dei nodi)
– auto-configurazione della rete
– architettura software del
nodo (definizione dei servizi
di sistema)
8
Middleware per WSN
• Motivazione:
– ridurre la difficoltà di progettazione ed implementazione di
un’applicazione per WSN
• Un middleware astrae la WSN nascondendo la
complessità dei singoli nodi e fornendone una visione
olistica.
• Classificazione middleware per WSN
–
–
–
–
classici (gestione della comunicazione)
data-centrici (astrazione come DB)
virtual-machine (esecuzione di script sui nodi)
adaptive middleware (adattamento alla specifica
applicazione)
9
Sistema real-time
• la correttezza di funzionamento dipende
– dalla validità dei risultati (come nei sistemi normali)
– dal tempo in cui sono
prodotti
• le attività (task) di un
sistema real-time hanno
una deadline che va
rispettata
• Caratteristica fondamentale: predicibilità
– capacità di determinare in anticipo se uno o più task
termineranno entro la proprie deadline
10
PROGETTAZIONE
11
Descrizione generale
• Permettere all’utente di
interfacciarsi alla WSN
secondo l’approccio per
le Basi di Dati per
estrarre informazioni
sulla misura di variabili
distribuite
• Sensoristica eterogenea
12
Requisiti Funzionali
• Query snapshot e periodiche
– di tipo semplice
– con funzioni aggregative di tipo statistico
– eventualmente con restrizioni (confronti con valori
di soglia parametrici)
13
Requisiti non funzionali
•
•
•
•
•
•
•
•
•
•
•
•
Real-time
Trasparenza e data-centrismo
In-network processing
Adattabilità alla specifica applicazione
Efficienza energetica
Robustezza
Estendibilità
Supporto multipiattaforma
Scalabilità
Eterogeneità hardware
Concorrenza con altri applicativi distribuiti
Attinenza al protocollo di comunicazione IEEE
802.15.4
14
Requisiti real-time nel dettaglio
• Relativi alle query periodiche
– la periodicità deve essere rispettata
– l’esecuzione deve terminare entro l’inizio del prossimo
periodo (D = T)
– se non è possibile soddisfare tali requisiti la query va
rifiutata (test di accettazione)
• Relativi alle query snaphost (o aperiodiche)
– devono essere schedulati, ma senza interferire con le
periodiche
– no starvation
• ma non è prevista una deadline
15
AMBIENTE DI SVILUPPO
16
Software
ERIKA Enterprise
•
•
•
•
OSEK-like RTOS per sistemi embedded minimali
1-4 Kb ROM footprint
avanzati algoritmi di scheduling (EDF con SRP)
GNU/GPL with Linking Exception
μWireless
•
implementazione dello standard IEEE 802.15.4
• GNU/GPL with Linking Exception
RT-Druid
• Configurazione di ERIKA tramite OSEK OIL
• integrated in eclipse.org
17
Erika Enterprise
Piattaforme supportate
Attualmente disponibile come prodotto per:
• Microchip dsPIC
• AVR
• Altera NIOS II
– con supporto multi-core!
Disponibile anche per:
• ARM7TDMI (Samsung KS32C50100, Triscend A7, ST Janus,
ST STA2051)
• Tricore 1
• PPC 5xx (PPC 566EVB)
• Hitachi H8 (RCX/Lego Mindstorms)
• C167/ST10 (Ertec EVA 167, tiny/large mem. model)
Erika Enterprise - Funzionalità
•
•
•
•
•
•
•
•
•
•
•
Preemptive fixed priority (OSEK) multithreading
Scheduler EDF con SRP
Implementazione multi-core dello scheduling a priorità fissa e
con EDF (MSRP)
Immediate Priority Ceiling to avoid priority inversion
Risorse condivise
Algoritmi di ottimizzazione dello stack
Condivisione dello stack con soglie di preemption (SRP) per
ridurre l’uso di RAM
Allarmi peridici
Footprint ridotto (ROM)
Ridotti requisiti di memoria (RAM)
Ridotto tempo di esecuzione delle primitive (gestione IRQ,
scheduling, context switching, ecc.)
Eclipse + RT-Druid
Editor
Projects
Output
Hardware
• Flex base board
• Flex demo board
• Microchip ICD2
programmer/debugger
• CC2420EM Packet
Sniffer
21
PROGETTAZIONE
22
Progettazione del
funzionamento real-time
• Problema:
– serve un meccanismo di diffusione della query che sia
predicibile
• Soluzione:
– topologia stella
– Il coordinator
•
•
•
•
tiene informazioni sui device
invia la query ai device (nel beacon payload)
disciplina la comunicazione assegnando GTS
riceve le risposte dai device (che rispondono utilizzando i
GTS assegnati)
23
Esempio di comunicazione
In questo modo la query ha un tempo di esecuzione:
• noto a priori
• multiplo del tempo di beacon
24
Schedulazione real-time
• La banda è paragonabile ad una CPU
– il tempo di clock è il tempo di beacon
 una query è paragonabile ad un task
• Si utilizzano le tecniche di schedulazione
utilizzate per i task
– Periodici schedulati con EDF
– Aperiodici serviti da un TBS
– Test di accettazione su periodici (test di
schedulabilità di EDF+TBS)
25
Earliest Deadline First
• Prevede che ogni task abbia una deadline
• Garantisce che in ogni istante il task in
esecuzione sia il task con deadline più
imminente
– preemptive
26
Schedulazione aperiodici
• Si utilizza un Total Bandwidth Server (TBS)
– Assegna agli aperiodi una deadline nel seguente
modo
• È ora possibile schedulare gli aperiodici con
EDF
27
Architettura
Architettura Logica
Mapping su componenti HW
28
Strutture dati
29
Componenti Coordinator
• Approccio modulare
– estendibilità (posso
aggiungere nuovi
moduli)
– flessibilità (posso
sostituire singoli moduli)
30
IMPLEMENTAZIONE
31
Implementazione client PC
(jMirtes)
• Scritto in Java
– supporto multipiattaforma
• Uso di librerie open source
– RXTX (GNU/LGPL) per
comunicazione seriale
– JSqlParser (GNU/LGPL) per
parser SQL
• E’ fondamentalmente una
libreria
– possibilità di integrazione in
altre applicazioni
• L’interfaccia testuale utilizza
le API della libreria
• ~2000 righe di codice
32
Implementazione software
coordinator e device
• Utilizzo del linguaggio C
• Uso della tecnica delle
pseudo classi
• Problematica legata alla
programmazione di sw
embedded (scarsa
memoria, ridotta
velocità di calcolo,
assenza di filesystem,
ecc.)
• ~4000 righe di codice
33
VALIDAZIONE SPERIMENTALE
34
Test effettuati
• Visualizzazione on-line di una query semplice
su grandezza vettoriale (accelerazione)
• Analisi del costo elettromagnetico delle query
in funzione di condizioni di soglia
• Analisi delle garanzia real-time
35
Visualizzazione on-line di una
query
SELECT NODE_ID,
ACC_X,
ACC_Y,
ACC_Z
FROM ACCELERATION
EVERY 150 MS
36
Scenario sperimentale usato per
la misura degli aggregati
Nodo
Lux
3
42
5
58
7
91
9
126
37
Funzioni di aggregazioni e
condizioni
Costo elettromagnetico
(numero di messaggi inviati)
Valor medio dei valori rilevati
Nodo
SELECT COUNT(LUX), MIN(LUX), MAX(LUX), MEAN(LUX) 3
FROM LUMINOSITY
5
WHERE LUX > THR
7
EVERY 100ms
9
Lux
42
58
91
126
38
Test con solo carico periodico
(senza controllo di garanzia)
ID
Tipo
A
C
T
U
0
Acc
0
3
10
0.3
1
Lux
0
2
4
0.5
2
Temp
0
1
5
0.2
3
Temp
8
1
5
0.2
39
Test con carico aperiodico
Andamento della
latenza di transazione in
funzione del tempo.
Sovrapposta alla figura
il numero di query
aperiodiche accodate e
completate nell’unità di
tempo
40
Conclusioni
• MIRTES
– middleware data-centrico sviluppato secondo le tecniche della software
engineering;
– completamente Open-Source;
– basato su un RTOS come ERIKA;
– per astrarre una WSN come una base di dati con funzionalita in tempo
reale;
– in completa compliance con lo standard IEEE 802.15.4;
– inter-operabile con un framework Open-Source (SCILAB/SCICOS) per la
visualizzazione in linea dei dati recuperati dai sensori. ;
– validato sperimentalmente facendo uso del package ROOT su dati
serializzati sul disco di un PC.
• Il ReTiS prevede di estendere le funzionalità di MIRTES al
management del codice ed alla proattività rispetto alla notifica di
eventi di rete.
• Il progetto verrà inoltre pubblicizzato ed il codice distribuito su
licenza LGPL attraverso il sito web di Evidence srl
(www.evidence.eu.com)
41