Facoltà di Ingegneria - unina.it

Facoltà di Ingegneria Corso di Studi in Ingegneria Informatica

tesi di laurea specialistica

Tecniche software per l’iniezione di guasti su microcontrollori per reti di sensori senza filo

Anno Accademico 2006/2007 Relatore Ch.mo prof. Stefano RUSSO correlatore Ing. Marcello CINQUE candidato Andrea AIELLO matr. 885/50

Ai miei genitori

III

Indice

Introduzione 6

Capitolo 1. Reti di sensori senza filo 10

1.1 Reti di sensori senza filo 10

1.1.1 Applicazioni 11

1.1.2 Architettura 14

1.1.3 Descrizione del nodo sensore 15

1.2 Il sistema operativo TinyOS 18

1.2.1 I componenti 19

1.2.2 Il frame 20

1.2.3 I comandi 21

1.2.4 Gli eventi 21

1.2.5 I task 22

1.2.6 Lo Scheduler 22

1.2.7 Split-phase operation 23

1.2.8 Active messages 24

1.3 Il linguaggio nesC 25

1.3.1 Modello a componenti 27

1.3.2 Modello di concorrenza 32

Capitolo 2. Dependability di reti di sensori senza filo 35

2.1 La Dependability dei sistemi software 35

2.1.1 Gli attributi della Dependability 36

2.1.2 Le minacce della Dependability 37

2.1.3 Tecniche per la valutazione della Dependability 38

2.1.3.1 La Fault Injection 41

2.2 Reti di sensori e Applicazioni critiche 42

2.2.1 Esempi applicativi 43

2.2.2 Requisiti della dependability di WSN critiche 43

2.3 Guasti di una WSN 45

2.3.1 Guasti di un nodo sensore 46

2.4 Valutazione della Dependability di WSN 47

2.4.1 Stato dell’arte 47

2.4.2 Valutazione della Dependability di un nodo sensore 49

IV

Capitolo 3. Tecniche di Fault Injection 51

3.1 Introduzione 51

3.2 Sistema di Fault Injection 53

3.3 Metodi e implementazioni dell’injection 54

3.3.1 Fault Injection Hardware 54

3.3.1.1 Injection con contatto 55

3.3.1.2 Injection senza contatto 56

3.3.2 Fault Injection Software (SWIFI) 56

3.3.2.1 Injection a tempo di compilazione 57

3.3.2.2 Injection a tempo di esecuzione 57

3.4 Injection a livello Assembly 58

3.4.1 Tecniche di analisi del codice 59

3.4.2 Regole di analisi del codice 60

3.4.3 Classificazione dei risultati dell’analisi 61

Capitolo 4. Una tecnica per la SWIFI su nodi sensore 62

4.1 Descrizione della tecnica e assunzioni sui guasti 62

4.2 Analisi del sistema fault-free 63

4.3 Set-up degli esperimenti 63

4.4 Conduzione degli esperimenti 64

4.5 Analisi dei risultati e confronto con la Golden copy 64

4.6 Libreria dei guasti e relativi injector 65

4.6.1 Guasti localizzati nella memoria dati 65

4.6.2 Guasti localizzati nel codice 66

4.6.3 Guasti localizzati nei registri del processore 66

4.7 Procedura per la decisione dell’instante di injection 68

Capitolo 5.Valutazione della tecnica 73

5.1 Strumenti di simulazione di reti di sensori senza filo 73

5.1.1 Emulatori di reti di sensori senza filo 78

5.2 Specifica del sistema 79

5.3 Descrizione del file disassemblato 80

5.3.1 Analisi della sezione text 80

5.4 Analisi del sistema fault-free 81

5.4.1 Analisi del codice 83

5.4 Analisi dell’area dati 85

5.5 Campagna di Fault Injection 85

5.6 Risultati della campagna 91

Conclusioni 98

Sviluppi futuri 99

Appendice A. Microcontrollore ATmega128L 100

A.1 Introduzione 100

A.2 Registri Generali 101

V

A.3 Registri per funzioni speciali 102

A.4 Vettori di interruzione 103

A.5 Memoria istruzioni 104

A.6 Memoria dati 105

A.7 Instruction Set 106

Appendice B. Emulatori per reti di sensori 107

B.1 Atemu 107

B.2 Avrora 111

Bibliografia 115


6

Introduzione

Gli avanzamenti nel campo della tecnologia dell‟informazione avvenuti negli ultimi anni

hanno reso possibile lo sviluppo di reti di sensori wireless. Si tratta di reti composte da

sensori di dimensioni molto ridotte, dal basso costo, alimentati a batteria e dunque

autonomi, capaci di effettuare la ricetrasmissione wireless di messaggi. In virtù delle loro

caratteristiche, le Wireless Sensor Networks possono essere adoperate per una moltitudine

di applicazioni nei campi più disparati; generalmente sono chiamate a svolgere compiti di

rilevazione, controllo, comunicazione, sorveglianza e monitoraggio in scenari di tipo sia

militare che civile. Le loro dimensioni, l‟autonomia energetica e la capacità di ricevere e

inviare messaggi senza fili permettono il loro impiego in ambienti di lavoro e locazioni

altrimenti irraggiungibili; il basso costo consente di dispiegarne un grande numero,

coprendo aree anche molto estese.

Tali sensori possono essere applicati anche per applicazioni critiche, cioè applicazioni

critiche che si distinguono dalle normali applicazioni informatiche per requisiti

estremamente stringenti di qualità e affidabilità, sulla base di tale tecnologia nuovi tipi di

applicazioni diventano possibili.

In tali applicazioni devono essere tenuti in conto i requisiti della dependability, in quanto il

malfunzionamento del sistema porterebbe problemi molto gravi che potrebbero mettere a

repentaglio la vita delle persone.

In particolare ci riferiremo al concetto di affidabilità e i requisiti che le WSN dovrebbero


7

rispettare. Il concetto di affidabilità si formalizza come la capacità che deve avere una rete

di conservare le proprie funzionalità indipendentemente dall‟eventuale guasto di qualche

sensore o semplicemente da una trasmissione fallita. Un nodo, ad esempio, può diventare

inutilizzabile a causa dell‟esaurimento della batteria o per danni fisici subiti nell‟ambiente

operativo.

Ci concentreremo esclusivamente sui guasti che causano i soft error, poiché con la

progressiva evoluzione delle tecnologie microelettroniche, che ha portato alla realizzazione

di circuiti integrati sempre più complessi, caratterizzati, per contro, da una riduzione delle

loro dimensioni fisiche e dei loro parametri elettrici, ha fatto sì che alcuni fenomeni

atmosferici o ambientali, prima considerati ininfluenti sul comportamento dei circuiti

integrati, siano ora in grado di perturbare il funzionamento dei moderni dispositivi

microelettronici.

Fra questi fenomeni va ricordata soprattutto la ionizzazione del substrato di ossido, dovuta

alle radiazioni, ai disturbi elettromagnetici o alle variazioni della temperatura.

L‟impatto di particelle dotate di carica elettrica su zone sensibili dei circuiti elettronici può

provocare la temporanea inversione dei bit (chiamata anche upset o bit-flip) delle

informazioni immagazzinate nel dispositivo, causando malfunzionamenti di vario tipo. A

questi disturbi si dà il nome di Single Event Upsets (SEU).

Gli studi condotti fin ora sull‟affidabilità delle reti di sensori sono per lo più orientati ai

guasti di rete o ai guasti di nodo permanenti (ad es. esaurimento batteria) ma non a quelli

intermittenti. Inoltre nessun lavoro scende nel dettaglio del comportamento faulty del

singolo nodo, che risulta quindi non ben conosciuto. Il lavoro di tesi quindi mira a colmare

questa mancanza proponendo di utilizzare le ben note tecniche di fault injection ai nodi

sensori, in particolare si propone di progettare e sperimentare una tecnica di fault injection

software, chiamata in letteratura SoftWare Implemented Fault Injection nota con

l‟acronimo di SWIFI.

Lo studio condotto utilizza una campagna di fault injection nel microcontrollore del nodo

sensore, precisamente nella memoria e nei registri, simulando il comportamento dei guasti

transienti, in particolare i bit-flip. La scelta della fault injection è dovuta alla volontà di


8

ridurre l‟attesa del sistema in esercizio, dato che i guasti che si riscontrano durante

l‟esercizio del sistema potrebbero richiedere degli anni e dato il rapido avanzamento delle

tecnologia, i risultati che otterremmo sarebbero inutili un volta pervenuti. La fault injection

ci permettere di studiare in maniera più rapida la dependability del sistema in quanto può

essere applicata anche durante fase prototipale del sistema, utilizzando quindi il prototipo.

Inoltre la tecnica proposta realizza la fault injection a livello Assembly, tale scelta è

motivata dall‟impossibilità nel realizzare tale tecnica a livello dei normali linguaggi

imperativi, quali ad esempio il „c‟ con cui è possibile programmare il microcontrollore

attraverso il compilatore avr-gcc appartenente alle binutils, cioè linguaggi con un (ad es.

impossibile stabilire quale cella di memoria dovrà essere affetta dal fault) elevato livello di

astrazione in cui l‟esperimento risulta essere difficilmente controllabile; inoltre rispetto alla

possibilità di utilizzare dell‟hardware dedicato risulta essere più economico.

Infine verrà effettuata una campagna di fault injection con lo scopo di sperimentare la

metodologia proposta e dare delle informazioni aggiuntive per future campagne di faul

injection.

Utilizzeremo l‟emulatore per reti di sensori Avrora, preferito rispetto al sistema reale, in

quanto gli strumenti forniti dall‟emulatore permettono uno studio delle informazioni di

trace e di profiling migliore e più veloce dato che l‟esecuzione del sensore in real time,

rallenta il processo di raccolta dei dati.

Il lavoro si articola in 5 capitoli, nel seguito daremo una breve descrizione.

Il capitolo 1 fornisce una panoramica delle WSN, in particolare introduce alcune

importanti definizioni e aspetti salienti che le contraddistinguono. Si procede poi con la

discussione delle possibili applicazioni di una WSN fornendo alcuni concetti di base per la

comprensione del presente lavoro di tesi.

Il capitolo 2 introduce brevemente il concetto di Dependability e inoltre si sofferma sulla

Dependability delle WSN critiche definendo i requisiti, le tipologie dei guasti, lo stato

dell‟arte relativo alla valutazione della Dependability di WSN e la possibilità di valutarla

nel singolo nodo sensore.


9

Il capitolo 3 descrive le tecniche di fault injection conosciute, in particolare il sistema di

fault injection e le possibili metodologie conosciute per emulare i guasti in un sistema.

Inoltre fornisce i concetti e le tecniche di analisi dell‟iniezioni a livello Assembly,

importanti per la progettazione della metodologia proposta.

Il capitolo 4 illustra la tecnica SWIFI proposta, in particolare analizza il sistema fault-free,

la specifica delle tipologie di guasti che formano la libreria del sistema di fault injection e

la descrizione del funzionamento del controllore del sistema di fault injection progettato.

Infine nel capitolo 5 descrive la valutazione sperimentale della metodologia progettata,

soffermandosi sugli strumenti di simulazione, la campagna realizzata e sulle informazioni

prodotte dalla campagna, importanti per le successive campagne e la valutazione della

Dependability delle WSN.


10

Capitolo 1

Reti di sensori senza filo

1.1 Reti di sensori senza filo

Le reti di sensori senza filo rappresentano l‟ultima frontiera della ricerca nel campo dei

sistemi cosiddetti embedded. Tali dispositivi sono stati concepiti per interagire con

l‟ambiente circostante, ma mentre fino ad ora la possibilità di cooperare con altri sistemi

era limitata in molti casi dalle connessioni via cavo, oggigiorno i progressi nelle

comunicazioni senza fili hanno eliminato questo vincolo permettendo una flessibilità

maggiore nel collocare tali dispositivi all'interno dell'ambiente da monitorare. Formando

così delle vere e proprie reti nelle quali ciascun nodo assolve uno specifico compito e

collabora con gli altri nodi della rete per raggiungere determinati obbiettivi.

I benefici introdotti dalle reti di sensori senza filo possono essere riassunti in:

1. Facile dislocazione: la copertura dei tradizionali macrosensori cablati è limitata a

certe aree a causa dei vincoli imposti dal costo e dalla posa, rigorosamente ad opera

di personale specializzato. In contrasto, le WSN possono contenere un grande

numero di nodi fisicamente separati. Anche se la copertura radio fornita da un

singolo nodo è ridotta, nodi densamente distribuiti possono lavorare

simultaneamente e in maniera cooperativa così da estendere la copertura dell‟intera

rete; inoltre i sensori possono essere letteralmente paracadutati in zone avverse;

2. Ridondanza naturale: una densa dislocazione dei sensori senza filo e la correlazione

tra dati di nodi vicini in una specifica area rende le WSN molto più flessibili


11

rispetto alle classiche reti di sensori cablati. In caso di malfunzionamento di uno dei

nodi, la rete riesce a reagire molto bene grazie alla forte ridondanza spaziale che

caratterizza le WSN cosa che invece non sarebbe proponibile nelle reti di

macrosensori. Inoltre, la possibilità di poter raggiungere diversi nodi direttamente

(poiché posizionati in una area di raggio minore di quello di trasmissione)

garantisce una ridondanza anche nei possibili cammini verso la destinazione

3. Accuratezza: anche se i macrosensori possono fornire misure con una maggiore

precisione rispetto ad un nodo sensore, la grande quantità di dati collezionati da una

moltitudine di minuscoli sensori riflette meglio le caratteristiche della realtà.

Inoltre, adottando appositi algoritmi di cooperazione tra nodi è possibile abbattere il

rumore di misura incorrelato e incrementare la componente comune.

4. Costo: E‟ previsto che le WSN siano molto meno costose rispetto alle reti di

macrosensori: basti pensare che il solo costo del cablaggio sia per la trasmissione

delle misure che per l‟alimentazione dei sensori, a volte raggiunge costi molto

superiori a quelli dei soli nodi.

1.1.1 Applicazioni

Le reti di sensori possono essere implementate utilizzando una vasta tipologia di sensori

come sensori sismici, magnetici, termici, infrarossi, acustici, radar, che sono in grado di

monitorare una ampia classe di condizioni ambientali fra le quali possiamo ricordare:

Temperatura;

Umidità;

Movimenti di veicoli;

Condizioni di illuminazione;

Pressione;

Livelli di rumore;

Presenza o assenza di determinati tipi di oggetti;

Stress meccanici;

Velocità, direzione e dimensione di oggetti.


12

Ciascun nodo sensore potrà inoltre essere utilizzato in diverse modalità, sarà possibile

interrogare periodicamente un sensore per avere una informazione continua, utilizzarli solo

per verificare il raggiungimento di una particolare condizione, o modalità ibride in cui

viene controllata periodicamente una grandezza, ma se questa supera una determinata

soglia il sensore avverte direttamente il controllore (es: Controllo di processi e lavorazioni

dell‟industria chimica).

Alcune delle principali applicazioni delle reti di sensori wireless possono essere

classificate in cinque macro gruppi: applicazioni militari, applicazioni industriali, controllo

ambientale, applicazioni mediche, home automation.

Applicazioni militari

Le reti di sensori wireless possono diventare parte integrante delle più comuni attività

militari come il comando, il controllo dei campi di battaglia, la rilevazione degli

spostamenti delle truppe nemiche, la sorveglianza e le operazioni di localizzazione dei

bersagli. Questo perché le WSN sono caratterizzate da un elevato numero di nodi dal costo

contenuto che possono essere impiegati in grandi quantità anche in ambienti inospitali

quale può essere un campo di battaglia.

L‟eventuale distruzione infatti di uno o più nodi non influenza l‟efficienza della rete, cosa

che invece potrebbe accadere utilizzando reti cablate.

Alcune delle applicazioni del campo militare possono essere il controllo ed il rilevamento

dello stato degli equipaggiamenti, la sorveglianza del campo di battaglia per monitorare le

attività delle fazioni nemiche, o ancora per rilevare i danni conseguenti ad una battaglia, o

il riconoscimento di agenti chimico fisici nell‟ambito di battaglie chimico biologiche.

Applicazioni industriali

L‟utilizzo delle WSN nel settore industriale si inserisce nella continua ricerca della

diminuzione dei costi per implementare sistemi di controllo per i processi produttivi. Le

prime applicazioni si hanno laddove non vengano richiesti elevati data rate, utilizzati in

applicazioni non critiche, dove gli intervalli di campionamento non risultano essere un

problema.

Al contrario l‟attenzione viene posta sui costi di implementazione e di manutenzione, ciò


13

comporta la necessità di dispositivi che non richiedano manutenzione, dove per

manutenzione intendiamo primariamente la necessità di sostituire e/o ricaricare le batterie.

Altre tipiche applicazioni industriali possono essere la realizzazione di bridge wireless

verso altre reti già esistenti come DeviceNet o FieldBus creando un‟interfaccia che possa

consentire il monitoraggio remoto e la modifica dei parametri di funzionamento di

dispositivi connessi alle reti preesistenti impiegando PDA o altri sistemi.

Controllo ambientale

Alcune delle applicazioni delle WSN in questo ambito possono essere i sistemi di

prevenzione degli incendi, le statistiche relative alla fauna protetta, agricoltura di

precisione, ricerche meteorologiche e geofisiche, controllo dell‟inquinamento.

Consideriamo ad esempio l‟impiego di una rete di sensori wireless nella lotta agli incendi,

un numero elevato di sensori possono essere posizionati in zone strategiche in modo

casuale all‟interno di una vasta area boschiva, questi nodi ovviamente devono essere dotati

di opportuni meccanismi di power scavenging, come celle solari, poiché i sensori possono

essere abbandonati nel territorio per lunghi periodi. L‟utilizzo di sensori wireless permette

di superare gli ostacoli tipici degli ambienti boschivi quali le rocce, gli alberi e la

vegetazione in genere, che non consentirebbe l‟installazione delle corrispettive versioni

cablate, a meno di considerare interventi radicali molto costosi e distruttivi.

Applicazioni Mediche

Alcuni esempi in questo campo possono essere la trasmissione dei parametri fisiologici dei

pazienti all‟interno degli ospedali, attività diagnostiche, somministrazione di medicinali,

personal healthcare ed altro. L‟utilizzo di WPAN consente all‟interno delle strutture

ospedaliere di poter monitorare i parametri fisiologici dei pazienti come temperatura,

pressione sanguigna, pulsazioni cardiache in modo non invasivo per il paziente e

consentendo l‟intervento tempestivo dei medici in caso di bisogno. Applicazioni simili

possono essere individuate anche nel personal healthcare, basti pensare ad una serie di

sensori dotati di interfaccia wireless integrati per esempio all‟interno di un orologio da

polso che consenta la misurazione dei battiti cardiaci, o in una bilancia per monitorare il

peso; in questo modo con una trasmissione giornaliera verso un PDA o un personal


14

computer è possibile costituire un archivio personale in cui vengono memorizzate le

informazioni salienti del nostro stato di salute. Altra applicazione interessante è il controllo

remoto di persone anziane per prevenire situazioni di pericolo quali per esempio una

caduta o uno sbalzo improvviso delle pulsazioni cardiache.

Home and Building automation

Con l‟evoluzione tecnologica ci aspettiamo di trovare degli smart transducer in ogni

apparato elettronico all‟interno della casa come televisori, VCR, forni a microonde,

frigoriferi e quant‟altro, in modo che tutti questi dispositivi siano in grado di interagire fra

loro e verso il mondo esterno attraverso altre infrastrutture di rete come comunicazioni via

satellite o più diffusamente internet.

Il progetto di una casa intelligente di questo tipo può prevedere due diversi approcci

progettuali, un sistema human centered che prevede che la tecnologia sia in grado di

rispondere alle esigenze dell‟utente finale in termini di interazione input/output o

technology centered che vuole creare un cosiddetto smart environment, in cui ogni

dispositivo della casa integra uno smart device in grado di comunicare con un server di

stanza, il quale a sua volta è in grado di comunicare con i server delle stanze adiacenti in

modo da creare un sistema integrato autoconfigurante, ed auto organizzato.

1.1.2 Architettura

Una rete di sensori rappresenta un insieme di nodi sensore che formano una prestabilita

topologia.

I nodi sono collocati all‟interno dell‟area in cui si osserva il fenomeno che si vuole

analizzare, oppure qualora non sia possibile, nelle sue immediate vicinanze. Questa attività

può essere ripetuta quando c‟è ad esempio l‟esigenza di rimpiazzare dei nodi che hanno

esaurito l‟energia della loro batteria o sono stati danneggiati. Il numero di sensori che

compongono la rete può variare da qualche decina a svariate migliaia. Le informazioni

raccolte vengono successivamente inviate verso una stazione base (anche chiamata sink),

passando da un nodo ad un altro secondo un protocollo multi-hop, ed infine trasferite, via

internet o via satellite, verso un centro di raccolta. Si possono prevedere configurazioni con


15

più stazioni base, eventualmente mobili (ad esempio un utente con un PDA oppure un

aereo in volo), e in questo caso, i nodi convogliano i dati verso un sottoinsieme delle

stazioni stesse. In altri casi le reti sono completamente isolate. Ciò può accadere quando i

nodi sono equipaggiati con attuatori e controllori, e programmati per svolgere determinate

attività.

1.1.3 Descrizione del nodo sensore

Esistono diverse piattaforme hardware di nodi sensore, nella seguente Figura è possibile

distinguere cinque componenti fondamentali: uno o più sensori della grandezza fisica da

rilevare (trasduttore), un ricetrasmettitore per la comunicazione e lo scambio dei dati

(radio), un‟unità di elaborazione digitale della grandezza misurata che sovrintende anche

alla comunicazione radio (unità di elaborazione e controllo), un sistema di alimentazione

autonomo (power management) e, in infine, uno o più attuatori.

Sensing Module

Comunemente col termine sensore si indica l‟intero nodo di una WSN. In questo contesto

però indicheremo con il termine sensore l‟hardware di cui è dotato un nodo per trasformare

la grandezza fisica acquisita in un segnale elettrico che possa essere elaborato (trasduttore).

Un nodo può disporre di più sensori, anche di grandezze fisiche diverse, che sono

strettamente legate alla specifica applicazione; si possono avere ad esempio sensori di

luminosità, pressione, temperatura, prossimità. La maggior parte dei sensori, prevede

inoltre la presenza di un blocco di conversione analogica-digitale (ADC, Analog to Digital


16

Converter), da utilizzare durante la fase di acquisizione del segnale. Il tipo di elaborazione

da effettuare dipende dalla grandezza fisica rilevata e influisce direttamente sui consumi: si

pensi ad esempio di dover digitalizzare un particolare segnale analogico: la rapidità con

cui varia determina la velocità di campionamento necessaria per acquisirlo correttamente,

mentre la sua dinamica e la precisione con cui lo si vuol rappresentare stabiliscono il

numero di bit della parola associata ad ogni campione. All‟aumentare della velocità di

campionamento e del numero di bit del convertitore analogico digitale, si ha un incremento

dei consumi.

Unità di elaborazione

La presenza di una CPU permette di dotare il nodo delle capacità elaborative per gestire le

comunicazioni e le grandezze misurate. Il ruolo della CPU può essere svolto da diverse

tipologie di circuiti logici. Comunemente la scelta ricade su un microcontrollore a basso

consumo, ma è possibile impiegare anche un FPGA (Field Programmable Gate Array), un

DSP (Digital Signal Processing) o un ASIC(Application Specific Integrated Circuit). Un

compito tipico del microprocessore in queste piattaforme è la verifica dell‟effettiva

necessità di utilizzare le risorse: per preservare la carica della batteria il nodo deve

disattivare tutti i dispositivi come chip radio, timer, oscillatori, ogni volta che questi non

sono indispensabili per le attività del nodo stesso. La gestione dei tempi e delle modalità

del passaggio dallo stato a basso consumo a quello di attività dei vari componenti è affidata

al microprocessore.

Il microprocessore è spesso integrato con alcuni blocchi di memoria ROM e RAM utilizzati

per ospitare il codice eseguibile del sistema operativo e dell‟applicazione, nonché i dati

acquisiti dai sensori ed elaborati dall‟applicazione. La gestione e l‟utilizzo delle memorie

è una fonte di consumo energetico, pertanto i blocchi di memoria integrati hanno capacità

ridotte, limitate a poche decine di kbyte e la loro dimensione, in termini di capacità di

immagazzinare dati, non va sovrastimata. Alcune piattaforme, tuttavia, possono essere

dotate di memorie Flash aggiuntive, connesse al microprocessore per mezzo di interfacce

seriali. Queste memorie, solitamente di capacità superiore rispetto alle memorie integrate

con il microprocessore, possono essere utilizzate per contenere parametri per la


17

configurazione del nodo o altri dati. Chiaramente, l‟utilizzo delle memorie aggiuntive

aumenta la potenzialità del nodo, ma influisce negativamente, come già detto, sui consumi

energetici.

Unità di comunicazione

Per garantire la connettività tra i nodi di una WSN è possibile adottare diverse strategie.

Tipicamente la connessione è realizzata via radio, anche se per alcune particolari

applicazioni sono disponibili soluzioni alternative che impieghino ultrasuoni o

comunicazioni ottiche. Solitamente tra tutti i componenti del nodo, il chip radio è il

dispositivo che consuma la maggior parte dell‟energia. Per ridurre il costo e il consumo

energetico dei nodi, si utilizzano tipicamente modulazioni ben consolidate e di bassa

complessità, a discapito della capacità trasmissiva che è spesso limitata a qualche decina

di kbit/s. Per limitare ulteriormente il costo finale del dispositivo, la modulazione radio

avviene normalmente nelle bande comprese tra gli 868-870 MHz o nelle bande ISM

(Industrial ScientificMedical) attorno ai 900 MHz e ai 2,4 GHz, per le quali non è richiesta

licenza governativa.

Alimentazione

Data l‟impossibilità di usufruire di una rete di distribuzione dell‟energia, è necessario che

ciascun elemento della WSN sia equipaggiato con un sistema autonomo di alimentazione.

Attualmente l‟unica soluzione diffusa è data dall‟utilizzo di pile elettrochimiche, il cui

sviluppo tecnologico non ha visto notevoli incrementi nell‟ultimo ventennio; ecco perché

la progettazione delle reti di sensori è centrata sul risparmio energetico. Fonti di energia

alternative sono argomento di ricerca ma al momento non sono ancora in grado di

rimpiazzare l‟alimentazione a batterie; l‟unica strategia applicabile per ora è lo

spegnimento selettivo dei nodi per la maggior parte del tempo, in modo da ridurre il

consumo di potenza medio. Promettente è la combinazione data da energia solare ed

elettrochimica, in cui l‟energia elettrica prodotta dalle celle fotovoltaiche esposte alla luce

del sole, va a ricaricare una batteria tampone che il nodo utilizza in assenza di luce.


18

1.2 Il sistema operativo TinyOS

TinyOS è un sistema operativo open-source, sviluppato dalla University of California at

Berkeley. Data la caratteristica di essere open-source, questo sistema operativo è diventato

la piattaforma di sviluppo per le reti di sensori.

TinyOS è stato progettato principalmente per le reti di sensori. A differenza delle

tradizionali architetture hardware, dove disponiamo di grandi quantità di memoria,

complessi sottosistemi per la gestione dei dati di ingresso e per quelli d‟uscita, forti

capacità di elaborazione e sorgenti di energia praticamente illimitate, nelle reti di sensori ci

troviamo a confronto con sistemi di piccole dimensioni, fonti di energia limitate, scarsa

quantità di memoria, modeste capacità di elaborazione, etc. Sono necessarie quindi

soluzioni molto semplici ed efficienti, e che soprattutto riducano al massimo i consumi di

energia. Anche il sistema operativo risente di queste limitazioni. Infatti TinyOS non

possiede un nucleo ma permette l‟accesso diretto all'hardware, inoltre sparisce i concetto di

processore virtuale per evitare i cambi di contesto, e quello di memoria virtuale: la

memoria viene infatti considerata come un unico e lineare spazio fisico, che viene

assegnato alle applicazioni a tempo di compilazione. In pratica viene eliminato qualsiasi

tipo di overhead, poichè nelle reti di sensori questo causa un inutile dispersione di energia

senza portare tangibili vantaggi. Queste scelte impattano direttamente sull‟architettura che

risulta molto compatta e ben si sposa con le dimensioni ridotte della memoria che a volte

raggiunge la quantità di pochi chilobyte.

Gli obbiettivi dei progettisti di TinyOS sono:

ridurre i consumi di energia;

ridurre il carico computazionale e le dimensioni del sistema operativo;

supportare intensive richieste di operazioni concorrenti e in maniera tale da

raggiungere un alto livello robustezza ed un efficiente modularità.

Per soddisfare il requisito della modularità, TinyOS favorisce lo sviluppo di una serie di

piccoli componenti, ognuno realizza una ben precisa funzione.

Ogni componente poi, definisce un interfaccia che garantisce la riusabilità del componente

ed eventualmente la sua sostituzione. Guardando in modello a strati del sistema in figura


19

del sistema operativo possiamo intuire come sia facilitato lo sviluppo di applicazioni

mediante il riutilizzo dei componenti esistenti.

TinyOS implementa il modello ad eventi. Nei tradizionali modelli infatti, è necessario

allocare un certa quantità di memoria sullo stack per ogni attività in esecuzione e inoltre, il

sistema è soggetto a frequenti commutazioni di contesto per servire ogni tipo di richiesta,

come l‟invio di pacchetti, la lettura di un dato su un sensore, etc. Naturalmente i nodi non

dispongono di grosse quantità di memoria ed il modello ad eventi ben si addice ad un

sistema continuamente sollecitato.

Nel campo delle reti di sensori il consumo di energia è un fattore critico e l'approccio

basato sugli eventi utilizza il microprocessore nella maniera più efficiente possibile.

Quando il sistema viene sollecitato da un evento questo viene gestito immediatamente e

rapidamente. In effetti non sono permesse condizioni di bloccaggio né attese attive che

sprecherebbero energia inutilmente. Quando invece non ci sono attività da eseguire il

sistema mette a riposo il microprocessore che viene risvegliato all'arrivo di un evento.

Di seguito riportiamo un analisi dettagliata sia dei componenti sia del modello di

esecuzione.

1.2.1 I componenti

Per componente intendiamo un‟unità indipendente e che svolge un determinato compito.

L‟insieme di componenti che forma un‟applicazione, chiamato grafo dei componenti, è

costituito da componenti preesistenti (che appartengono a librerie o applicazioni sviluppate

in precedenza) e da nuovi componenti, cioè quelli necessari a completare l‟applicazione. Il


20

grafo fissa una gerarchia nel senso che il processo di composizione dell‟applicazione

produce una stratificazione all‟interno della stessa. I componenti di livello inferiore

segnalano eventi a quelli di livello più alto, mentre i componenti di livello superiore

richiedono dei servizi ai componenti di livello più basso. Lo strato inferiore infine, è

formato da componenti che rappresentano direttamente i dispositivi hardware.

Un componente è costituito da quattro parti tra loro collegate:

un insieme di comandi;

un insieme di eventi;

un frame;

un certo numero di task.

Comandi, eventi e task operano all‟interno del frame, modificandone lo stato (Figura 1.).

Un componente definisce poi delle interfacce che permettono di realizzare applicazioni

modulari.

1.2.2 Il frame

Il frame rappresenta l‟area di memoria all‟interno del quale il componente conserva i dati

relativi al suo stato. Si tratta, in particolare, di una struttura C-like allocata staticamente in

memoria al tempo di compilazione ed accessibile unicamente al componente stesso. Esso

viene allocato a tempo di compilazione e permette di conoscere non solo la quantità di

Figura 1.: Rappresentazione di un componente TinyOS


21

memoria richiesta da un componente ma quella dell‟intera applicazione. Questa soluzione

permette di evitare gli sprechi dovuti all‟overhead associato alle allocazioni dinamiche.

Infatti il sistema operativo non deve compiere delle operazioni per risolvere gli indirizzi in

memoria, dato che i riferimenti all'interno del programma corrispondono ad indirizzi fisici.

1.2.3 I comandi

I comandi sono richieste di un servizio offerto da un componente di livello più basso.

Generalmente, un comando deposita dei parametri nel frame e poi attiva un task, ma è

possibile anche che questo chiami un altro comando. A causa del limitato quantitativo di

memoria del frame, un componente può rifiutare un comando. Convenzionalmente un

comando fornisce un feedback al suo chiamante per mezzo di opportuni parametri di

ritorno, informandolo cosi del successo o meno dell‟operazione richiesta.

I comandi sono progettati nell‟ottica di ritornare immediatamente, svolgendo

semplicissime funzioni di triggering su altri componenti. I servizi richiesti dai comandi

saranno, quindi, svolti concorrentemente all‟interno dei task del componente.

1.2.4 Gli eventi

In generale, un evento è un‟occorrenza di un oggetto di interesse per uno o più oggetti,

mentre una notifica è un messaggio che un oggetto invia alle parti interessate per

comunicare un determinato evento.

Il modello a eventi prevede due tipologie di attori: il supplier, che produce eventi, e il

consumer, che utilizza gli eventi prodotti.

La notifica di un evento può avvenire mediante due modelli di interazione:

push model, in cui il supplier prende l‟iniziativa trasferendo l‟evento al consumer;

pull model, in cui il consumer prende l‟iniziativa richiedendo l‟evento al supplier.

In TinyOS gli eventi sono, direttamente o indirettamente, delle interruzioni hardware: il

componente di livello più basso, ossia l‟hardware abstraction, trasforma un‟interruzione

hardware in un evento e poi notifica tale evento ai livelli più alti, come previsto dal

modello di interazione di tipo push.


22

Come i comandi, un gestore di evento può depositare dei parametri nel frame e poi attivare

un task. Un gestore di evento può notificare altri eventi e alla fine chiamare un comando,

come a formare una catena che prima si dirige verso l‟alto e infine verso il basso Per

evitare che questa catena si possa chiudere viene impedito ai comandi di notificare eventi.

Gli eventi sono stati progettati per eseguire piccole quantità di calcoli e, tipicamente, sono

associati a condizioni di risveglio del nodo sensore. Per tale motivo, è necessario che gli

eventi vengano eseguiti nel più breve tempo possibile, in modo da permettere ai nodi

sensori di ritornare in uno stato di riposo.

1.2.5 I task

TinyOS esegue un solo programma alla volta, il quale è composto da un solo tipo di

attività indipendente: il task. I task non hanno diritto di prelazione su nessuna delle attività

in corso, in pratica sono atomici rispetto agli altri task. Inoltre possono richiamare

comandi, notificare eventi o attivare altri task all'interno dello stesso componente.

I task sono stati progettati per eseguire considerevoli quantità di calcoli e, pertanto, non

sono critici per il tempo. Inoltre, la caratteristica di un task di essere eseguito fino al suo

completamento permette di gestire un unico stack, il quale viene assegnato a turno al task

in esecuzione.

1.2.6 Lo scheduler

Il componente principale, l‟unico sempre presente in ogni applicazione, è lo scheduler.

Esso lancia in esecuzione i task dei diversi componenti secondo una politica FIFO run-to-

completion, ossia un task non può interromperne un altro. Lo scheduling ha due livelli di

priorità: quello normale per i task e quello più alto per gli eventi, che possono interrompere

i task. Inoltre esistono livelli di priorità anche tra gli eventi stessi: un evento con priorità

più alta di quello attualmente in esecuzione può interrompere l‟esecuzione dell‟evento

corrente.

In particolare ci soffermiamo sull‟implementazione dello scheduler, sottolineando due

procedure importanti, TOS_POST() che rappresenta la procedura che posiziona il


23

puntatore al task nel primo slot libero della coda dello scheduler, e la procedura principale

dello scheduler, la TOSH_run_task() in cui viene richiamata la procedura

TOSH_run_next(), che schedula il primo task presente nella coda, qualora non vi fossero

dei task da eseguire viene posto il sensore in sleep (low power), attendendo che venga

invocata un interruzione che risvegli il processore, come mostrato nel seguente codice:

void TOSH_run_task() {

while (TOSH_run_next_task()) ;

TOSH_sleep();

TOSH_wait();

}

Si nota dal codice che se la coda dei task è vuota, lo scheduler mette a riposo il

microprocessore, tutto ciò per evitare inutili sprechi di energia.

1.2.7 Split-phase operation

In generale, il distributed callback è una tecnica di comunicazione asincrona con la quale il

cliente invia una richiesta al servente e prosegue nella propria elaborazione. Il servente,

eseguito il servizio, interrompe il cliente richiamando un‟apposita operazione del cliente

stesso per la restituzione dei risultati.

L‟adozione di un modello basato sul distributed callback permette di realizzare un

meccanismo di comunicazione asincrona tra due entità. Tuttavia, tale meccanismo è basato

su un accoppiamento stretto tra cliente e servente. Inoltre la comunicazione è di tipo uno a

uno, vale a dire tra due sole entità. Molto spesso, invece, è necessario realizzare un

meccanismo di comunicazione asincrono ad accoppiamento lasco tra un insieme di cliente

e un insieme di serventi. Per superare tali problematiche, si deve far ricorso al modello a

eventi, già discusso precedentemente.

In TinyOS, la comunicazione tra componenti situati a diversi livelli è asincrona ad

accoppiamento lasco. Il meccanismo che il sistema operativo utilizza si basa sul distributed

callback, ma fa ricorso al modello a eventi per realizzare l‟accoppiamento lasco e per

superare quindi i limiti del distributed callback. Infatti, in TinyOS, ogni operazione non


24

banale è una split-phase operation, ovvero la chiamata e l‟operazione di ritorno sono in

realtà due funzioni separate. Un‟operazione viene invocata chiamando un comando su un

componente di livello inferiore. Il comando avvia un task in tale componente e ritorna

immediatamente il controllo al componente chiamante. Il ritorno dei risultati

dell‟operazione avviene attraverso la notifica di un evento al componente chiamante,

quando il task precedentemente attivato nel componente chiamato è terminato. Ogni

componente implementa una delle due metà delle operazioni split-phase previste, ossia o il

comando o l‟evento. In particolare, il componente chiamato implementa il comando,

mentre il componente chiamante implementa il gestore dell‟evento.

1.2.8 Active messages

L‟active messages implementa un protocollo inaffidabile di livello data-link che si occupa

del controllo di accesso al mezzo e della comunicazione single-hop tra i nodi della rete.

Ciò significa che un nodo equipaggiato con il solo sistema operativo può inviare messaggi

solamente ai nodi direttamente collegati ad esso tramite un mezzo trasmissivo, mentre non

può inviare messaggi a un qualsiasi nodo della rete, perché i protocolli di routing sono

implementati ai livelli superiori.

Active messages è una tecnologia molto leggera, infatti non specifica meccanismi di

comunicazione orientati alla connessione, ma prevede che ogni pacchetto sia un‟unità

indipendente. Essa consente di inviare pacchetti verso un singolo nodo, specificando un

indirizzo di 16 bit, oppure di inviare pacchetti in broadcast, specificando l‟indirizzo

0xFFFF.

Il funzionamento di active messages consiste nell‟inviare al nodo destinazione un

pacchetto che, oltre al campo dati, contiene un‟informazione che specifica il tipo di evento

che deve essere generato sul nodo destinazione a seguito della ricezione del pacchetto.

Quando un nodo riceve un pacchetto, esso viene elaborato dall‟active messages, il quale

individua il tipo di evento da generare, incapsula il campo dati del pacchetto in un evento e

invia la notifica di tale evento al componente appropriato.

Active messages consente di inviare più di 256 tipi di messaggi diversi, ognuno dei quali


25

associato a un differente gestore di evento. Questa caratteristica permette a più reti o a più

protocolli di alto livello di funzionare in concorrenza e senza causare conflitti.

Inoltre, l‟active messages fornisce anche l‟astrazione di 256 gruppi di nodi differenti.

Questa ulteriore funzionalità consente di suddividere una grande rete di sensori in più

sottoreti logicamente separate e tra di loro invisibili.

Il sistema di comunicazione su cui si basa active messages permette di eliminare il

complesso utilizzo di buffer delle implementazioni TCP/IP, ma il principale svantaggio

dell‟approccio è che tutti i nodi comunicanti devono avere un componente in grado di

gestire un ben preciso tipo di eventi.

1.3 Il linguaggio nesC

Il linguaggio nesC è una variante del linguaggio C sviluppata appositamente per la

programmazione di motes. Per alcuni versi questo linguaggio è un estensione del C, in

quanto implementa un modello a eventi, mentre per altri versi restringe il linguaggio C,

poiché limita diverse operazioni riguardanti i puntatori. Le caratteristiche principali di

nesC sono:

separazione della costruzione dalla composizione. Sviluppare un‟applicazione in

nesC significa realizzare una serie di componenti che verranno poi assemblati per

produrre un codice eseguibile. Ogni componente ha due obbiettivi da realizzare:

deve definire le specifiche del suo comportamento e deve implementare tali

specifiche;

specificare il comportamento del componente mediante una serie di interfacce. Le

interfacce possono essere pubblicate o usate dai componenti. Le interfacce

pubblicate rappresentano le funzionalità che un componente intende mettere a

disposizione degli altri. Le interfacce usate invece, sono le funzionalità di un altro

componente che si intendono utilizzare per realizzare il proprio comportamento;

le interfacce sono bidirezionali. Queste specificano una serie di funzioni che devono

essere implementate dal fornitore dell‟interfaccia e un altro insieme di funzioni che

devono essere implementate dal componente che le utilizza. Questo permette di


26

realizzare operazioni complesse con un singola interfaccia. Ciò è necessario in

quanto l'esecuzione di un comando non può essere un operazione bloccante, anche

se esistono delle operazioni che richiedono un tempo non determinato per giungere

a conclusione, come ad esempio l‟invio di un pacchetto. In questo caso viene

associato al comando un evento che segnala il termine dell'operazione. Quindi se si

utilizza un‟interfaccia per l‟invio dei pacchetti, un componente non può chiamare il

comando send (invio del pacchetto), senza implementare l'evento send_done (invio

del pacchetto completato);

i componenti sono collegati staticamente attraverso le loro interfacce. Questo per

raggiungere una maggiore velocità di esecuzione, per incoraggiare le

implementazioni robuste e per permettere l‟analisi statica del programma. Nel caso

si annidassero possibili problemi di accesso concorrente a una risorsa, il

compilatore è in grado di accorgersene e di segnalarlo all‟utente;

il modello di concorrenza del nesC aderisce a modello del TinyOS. Il modello del

compilatore nesC è basato su task, che sono eseguiti fino al loro completamento, e

da eventi, che possono interrompere i task e, se di priorità maggiore, anche gli

eventi stessi.

In accordo con la politica di utilizzo delle risorse di alimentazione del sensore, ossia sleep

per la maggior parte del tempo e awake solo durante la fase di elaborazione, il linguaggio

nesC permette di definire un‟elaborazione event-driven: i componenti di un‟applicazione

vengono mandati in esecuzione solo quando si verificano gli eventi associati a ciascun

componente.

Il sistema operativo TinyOS è programmato in nesC. Nel momento in cui un‟applicazione

viene compilata, i componenti di TinyOS vengono compilati insieme ad essa e il risultato

costituisce l‟intero software del sensore. Questo approccio consente un ingente risparmio

di energia e di memoria, tuttavia limita molto la versatilità: infatti non è possibile installare

più applicazioni indipendenti sullo stesso nodo sensore e non è possibile effettuare linking

dinamico di librerie esterne o riconfigurazione dinamica di parte del codice presente sul

sensore.


27

Dal punto di vista dell‟affidabilità, la presenza di una singola applicazione alla volta e

l‟assenza di linking dinamico permette di eseguire molti controlli statici sulla bontà del

codice che altrimenti non sarebbero possibili. Inoltre diverse funzionalità proprie del C,

come allocazione dinamica e puntatori a funzione, che spesso sono fonte di problemi

relativi alla robustezza del codice, vengono escluse.

1.3.1 Modello a componenti

Un‟applicazione nesC è un insieme di componenti collegati tramite interfacce. Questo

approccio separa la costruzione dei componenti dalla composizione degli stessi.

Interfacce

Un‟interfaccia è composta da un insieme di comandi e da un insieme di eventi. Ogni

componente definisce un insieme di interfacce pubblicate ed un insieme di interfacce

utilizzate: per ogni interfaccia utilizzata, un componente implementa i gestori degli eventi

e invoca i comandi, mentre per ogni interfaccia pubblicata, un componente implementa i

comandi e notifica gli eventi. Tali interfacce rappresentano gli unici punti di accesso per

interagire con il componente.

Un comando generalmente è una richiesta di servizio, mentre l‟evento segnala il

completamento di un servizio. In questo modo, ogni interfaccia è bidirezionale: l‟insieme

dei comandi descrive il servizio offerto dal componente, mentre l‟insieme degli eventi

descrive il servizio utilizzato dal componente.

Si riporta un esempio di interfaccia:

interface Send {

command error_t send(message_t* msg, uint8_t len);

event void sendDone(message_t* msg, error_t err);

command error_t cancel(message_t* msg);

command void* getPayload(message_t* msg);

command uint8_t maxPayloadLength(message_t* msg);

}

interface Read<val_t> {


28

command error_t read();

event void readDone(error_t err, val_t t);

}

Moduli e configurazioni

In nesC ci sono due tipi di componenti:

moduli;

configurazioni.

Un modulo è un componente che implementa le interfacce che esso stesso dichiara, ossia

implementa i comandi di ogni interfaccia pubblicata e i gestori degli eventi di ogni

interfaccia utilizzata. Nell‟implementazione di un modulo è possibile notificare eventi

tramite la parola chiave signal, mentre è possibile invocare comandi tramite la parola

chiave call. Inoltre, l‟attributo asynch applicato ai comandi indica che questi possono

essere richiamati all‟interno dei gestori degli eventi. Infine, ogni modulo contiene il suo

stato sotto forma di variabili locali dichiarate similmente alle variabili in C.

Si riporta un esempio di modulo:

module ComponentModule {

provides interface StdControl;

provides interface Read<uint16_t>;

uses interface Send;

}

implementation {

message_t racket;

command error_t StdControl.start() {...}

command error_t Read.read() {...}

event void Send.sendDone(message_t* msg, error_t err) {...}

}

Una configurazione è un componente che ha la funzione di:

assemblare altri componenti, ossia collegare le interfacce utilizzate da alcuni

componenti con le interfacce pubblicate da altri componenti;


29

esportare interfacce, ossia delegare ad altri componenti l‟implementazione delle

interfacce che la configurazione stessa dichiara;

rinominare interfacce, ossia collegare un‟interfaccia utilizzata dalla configura-zione

con un‟interfaccia pubblicata dalla configurazione;

Ogni applicazione è composta da una configurazione globale che definisce le connessioni

dei vari componenti di cui è composta.

Nell‟implementazione di una configurazione bisogna innanzitutto definire, tramite la

parola chiave components, i componenti che si intendono utilizzare nelle operazioni di

assemblaggio, esportazione e rinomina. Successivamente si specificano i cosiddetti vincoli

di wiring, ossia si specifica come collegare i componenti precedentemente dichiarati. I

vincoli di wiring si specificano tramite due tipi di operatori:

gli operatori „->‟ o „<-‟ realizzano l‟assemblaggio dei componenti. La sintassi vuole

che la direzione della freccia vada dall‟interfaccia utilizzata verso l‟interfaccia

pubblicata;

l‟operatore „=‟ realizza l‟esportazione o la rinomina delle interfacce. La sintassi

vuole che come operatore sinistro venga specificata una delle interfacce dichiarate

dalla configurazione e come operatore destro venga specificata un‟interfaccia da

esportare o da rinominare. In caso di rinomina, l‟operatore deve collegare

un‟interfaccia utilizzata con un‟interfaccia pubblicata, mentre in caso di

esportazione, l‟operatore deve collegare interfacce dello stesso tipo.

A un‟interfaccia possono essere collegate zero, una o più interfacce. Nei primi due casi la

semantica è banale, mentre nell‟ultimo caso la semantica coinvolge i concetti di fan-in e

fan-out: il fan-out è la proprietà che caratterizza un‟interfaccia quando essa è collegata a

più interfacce pubblicate, mentre il fan-in è la proprietà che caratterizza un‟interfaccia

quando essa è collegata a più interfacce utilizzate.

La semantica di un collegamento uno a molti varia in base alle proprietà di fan-in o fan-out

a cui è soggetta un‟interfaccia:

fan-out. L‟invocazione di un comando presente in un‟interfaccia soggetta a fan-out

equivale all‟invocazione del medesimo comando su tutti i componenti che


30

implementano le interfacce pubblicate collegate a quella soggetta a fan-out;

fan-in. La notifica di un evento presente in un‟interfaccia soggetta a fan-in equivale

alla notifica del medesimo evento a tutti i componenti che implementano le

interfacce utilizzate collegate a quella soggetta a fan-in.

In entrambi i casi, l‟ordine delle chiamate non è noto a priori, mentre il valore di ritorno

complessivo è costruito da una funzione che compone i risultati, come ad esempio un AND

logico.

Si riporta un esempio di configurazione:

configuration ComponentConfiguration {

provides interface StdControl;

}

implementation {

components BlinkM, LedsC, SingleTimer;

BlinkM.Timer -> SingleTimer.Timer; // assemblaggio

BlinkM.Leds -> LedsC.Leds; // assemblaggio

StdControl = SingleTimer.StdControl; // esportazione

StdControl = BlinkM.StdControl; // esportazione

}

Assemblaggio dei componenti

Come già spiegato, per realizzare un‟applicazione è necessario collegare tra di loro i vari

componenti, in modo da produrre il cosiddetto grafo dei componenti.


31

Nell‟esempio riportato in figura, i componenti ComponentD, ComponentF e Application

sono delle configurazioni e servono a collegare tra loro componenti preesistenti. Il resto dei

componenti sono dei moduli.

Il componente ComponentD fornisce un‟interfaccia che verrà usata da ComponentC e

utilizza un‟interfaccia che sarà fornita da ComponentF. Il componente ComponentF

fornisce una sola interfaccia che corrisponde a quella fornita da ComponentE. Il

componente Application costituisce l'applicazione vera e propria. Non utilizza né fornisce

interfacce ma effettua il semplice collegamento tra i componenti ComponentC,

ComponentD e ComponentF.

Come si può notare, la ragione per cui un componente si distingue in moduli e

configurazioni è per favorire la modularità di un‟applicazione. Ciò permette allo

sviluppatore di assemblare velocemente le applicazioni. In effetti, si potrebbe realizzare

un‟applicazione solo scrivendo un componente di configurazione che assembli componenti

già esistenti. D‟altra parte questo modello incoraggia l‟aggiunta di librerie di componenti

tali da implementare algoritmi e protocolli che possano essere utilizzati in una qualsiasi

applicazione.

Stratificazione e componenti

La figura seguente mostra il grafo di un‟applicazione che potrebbe, ad esempio, leggere i

valori di luminosità e temperatura dell'ambiente con una certa frequenza e comunicare i

dati raccolti via radio.


32

Quello che interessa maggiormente è le relazioni che intercorrono tra i vari componenti e

la stratificazione del sistema operativo TinyOS. Questa relazione favorisce la modularità

delle applicazioni e, come si può notare, se si volesse modificare il protocollo di routing

basterebbe sostituire solo quei componenti che appartengono al blocco Routing Layer,

lasciando inalterato il resto dell‟applicazione. Lo stesso discorso vale nel caso si volesse

installare l‟applicazione su una piattaforma diversa. I componenti di più basso livello sono

direttamente collegati all'hardware: infatti, un‟interruzione hardware viene tradotta

direttamente in un evento. In pratica questi componenti realizzano un‟astrazione software

dei dispositivi fisici ai quali sono connessi. Quindi, se si volesse utilizzare un sistema di

comunicazione diverso, basterebbe sostituire i componenti del blocco RFM. Ed è appunto

questa l‟operazione che il compilatore „ncc‟ esegue quando si compila un‟applicazione per

una piattaforma diversa, sia questa Mica, Mica2, Mica2dot oppure PC.

1.3.2 Modello di concorrenza

Il linguaggio nesC prevede un modello d‟esecuzione che consiste di task e di interruzioni

sollevate asincronamente dall‟hardware.

Un task può essere attivato da qualunque punto del codice di comandi, eventi o altri task,

attraverso la parola chiave post, mentre viene implementato con una funzione senza

argomenti e senza valore di ritorno, preceduta dalla parola chiave task.

Formalmente, il codice scritto in nesC si divide in:

codice sincrono, ossia codice che può essere mandato in esecuzione solo da task;

codice asincrono, ossia codice che può essere mandato in esecuzione da almeno

un‟interruzione hardware.

In altri termini, è considerato codice sincrono tutto il codice eseguito solo come parte di un


33

task, mentre è considerato codice asincrono tutto il codice eseguito come parte

dell‟elaborazione di un evento notificato a seguito di un‟interruzione hardware.

I comandi e i gestori di evento che fanno parte del codice asincrono devono essere

dichiarati con la parola chiave asynch.

Un pezzo di codice sincrono non può interrompere o essere interrotto dallo scheduler per

eseguire un altro pezzo di codice sincrono, poiché il codice sincrono è eseguito in modalità

run-to-completion. Il codice asincrono, invece, interrompe il codice sincrono in

esecuzione. In altri termini, un pezzo di codice sincrono è atomico rispetto agli altri pezzi

di codice sincrono, mentre non è atomico rispetto un pezzo di codice asincrono.

Sebbene la politica run-to-completion elimini, all‟interno di codice sincrono,

problematiche relative all‟utilizzo di risorse comuni ad uso esclusivo, la presenza di codice

asincrono potrebbe far comunque sorgere tali questioni. In generale, qualsiasi

aggiornamento allo stato condiviso che è possibile eseguire da codice asincrono è

considerato un potenziale problema di accesso concorrente. In particolare, esistono due

possibili scenari di accesso concorrente e avvengono quando:

un aggiornamento allo stato condiviso può essere eseguito solo da codice asincrono;

un aggiornamento allo stato condiviso può essere eseguito sia da codice sincrono che

da codice asincrono.

Per prevenire queste condizioni, il compilatore nesC controlla al momento della

compilazione (cosa resa possibile dal linking statico, dalla mancanza di allocazione

dinamica e da limitazioni sull‟uso dei puntatori) che ogni aggiornamento a un elemento

dello stato condiviso tra più elementi di codice avvenga solo in codice sincrono oppure

avvenga in una sezione atomica.

Una sezione atomica è una sezione di codice eseguita disabilitando le interruzioni

hardware. Le sezioni atomiche sono definibili mediante blocchi dichiarati tramite la parola

chiave atomic. Per limitare gli effetti negativi prodotti da una lunga sospensione delle

interruzioni hardware, all‟interno di una sezione atomica non è permesso invocare comandi

o notificare eventi. Inoltre, il corpo di una funzione utilizzata all‟interno di una sezione

atomica è considerata essa stessa una sezione atomica se tutte le chiamate a tale funzione


34

avvengono all‟interno di sezioni atomiche.

La politica di consentire aggiornamenti allo stato condiviso solo da codice sincrono o da

sezioni atomiche è estremamente restrittiva: infatti, rileva molti problemi di accesso

concorrente là dove in realtà non esistono. In questi casi, il programmatore può indicare al

compilatore di non verificare le condizioni di accesso concorrente su una particolare

variabile attraverso la parola chiave norace posta prima della dichiarazione della variabile

stessa.


35

Capitolo 2

Dependability di reti di sensori senza filo

2.1 Dependability dei sistemi software

La Dependability è un attributo di qualità composito dei sistemi di elaborazione,

comprendente sottoattributi quali affidabilità, sicurezza, manutenibilità e disponibilità.

La diffusione su larga scala dei sistemi di elaborazione, ormai parte integrante dei processi

politici, economici e sociali, ha fatto sì che la dependability assumesse un sempre più

crescente interesse nel mondo accademico quanto in quello industriale.

Dato un sistema di elaborazione esso interagisce, tramite la sua interfaccia di servizio, con

degli utenti, che possono essere sia umani sia altri sistemi. Le interazioni del sistema con

gli utenti sono caratterizzate dalla funzione che il sistema deve implementare, definita

tramite le sue specifiche funzionali, e dal servizio, che è il comportamento del sistema così

come è percepito dall'utente. L'utente quindi non è onnisciente ma ha una cognizione

limitata del reale comportamento del sistema e del suo stato.

La Dependability di un sistema di elaborazione è la sua capacità di fornire un servizio su

cui si può fare affidamento in maniera giustificata. Quando il servizio corrisponde alle

specifiche funzionali si dice corretto, mentre si dice non corretto nel caso contrario.

Nell‟istante in cui si passa da servizio corretto a servizio non corretto si ha un

malfunzionamento del sistema. Il periodo in cui il sistema fornisce un servizio non corretto

si dice di outage. Il passaggio inverso al malfunzionamento, da un servizio non corretto ad

un servizio corretto viene detto ripristino o service restoration.


36

Il termine include più attributi di qualità (Dependability Attributes), ed in senso più ampio,

comprende concetti quali le minacce (Dependability Threats), ovvero dei fenomeni che

ostacolano l‟erogazione di un servizio corretto e i mezzi (Dependability Means) attraverso i

quali viene raggiunta.

2.1.1 Gli attributi della Dependability

Gli attributi della Dependability permettono di darne una definizione più articolata e

complessa. Di seguito sono definiti sei attributi fondamentali:

Availability.

L’availability è sinteticamente definita come la probabilità che un sistema sia

pronto a fornire il servizio in un certo istante t, ovvero:

A=P(!Failure at t)

Più esplicitamente un sistema è available in un dato istante t se è in grado di fornire

un servizio corretto all‟istante t.

Reliability.

La reliability R(t) è la misura della continuità di un servizio ovvero la misura

dell‟intervallo di tempo in cui viene fornito un servizio corretto:

R(t)=P(!Failure in (0,t))

Safety.

Per safety si intende generalmente l‟assenza di condizioni di funzionamento che

possano portare il sistema a danneggiare gli utenti e/o l‟ambiente in cui opera. Dal

punto di vista matematico la safety S(t) è la probabilità che non vi siano guasti

catastrofici in [0,t].

S(t)= P (!CatastrophicFailures in [0,t])

È chiaro che il concetto di safety risulta relativo alla soggettiva valutazione dei

rischi e dell‟entità dei danni provocati dal sistema.

Maintainability.

La maintainability M(t) è definita come la capacità di un sistema di essere

sottoposto a modifiche e riparazioni, ovvero di poter essere facilmente ripristinato


37

in seguito al verificarsi di un guasto.

Security.

La security è definita come l‟assenza di manipolazioni improprie e accessi non

autorizzati al sistema. Più in dettaglio un sistema sicuro è un sistema in cui

coesistono gli attributi di availability (riadattata alla disponibilità del sistema solo

verso utenti autorizzati), confidentiality (prevenzione della diffusione non

autorizzata delle informazioni) e integrità (prevenzione di alterazioni improprie

dello stato del sistema).

A seconda dell‟uso che si vuole fare del sistema si può cercare di massimizzare alcune di

queste caratteristiche rispetto alle altre.

2.1.2 Le minacce della Dependability

La dependability è spesso compromessa dai malfunzionamenti che occorrono nel sistema,

causati a loro volta da errori e guasti.

Un guasto, fault, è uno stato improprio dell‟hardware e/o del software del sistema

derivante dal guasto di un componente, da fenomeni di interferenza o da errori di

progettazione. Esso può portare ad un errore, error, cioè la parte dello stato di un sistema

che può indurre lo stesso al malfunzionamento, failure ovvero a fornire un servizio non

conforme alle specifiche (unproper service).

Un guasto si definisce “attivato” nel momento in cui genera un errore, mentre un errore “si

propaga” in un malfunzionamento quando raggiunge l‟interfaccia del sistema. Il processo

di propagazione è quello attraverso cui gli errori raggiungono l'interfaccia del sistema. La

catena guasto - errore - malfunzionamento permette di rappresentare il nesso causale, che

adesso illustreremo, esistente tra i tre concetti nel processo di propagazione.

La catena guasto - errore - malfunzionamento

Un sistema consiste in un insieme di componenti che interagiscono, quindi lo stato del

sistema è l‟insieme degli stati dei suoi componenti. Lo stato di un componente, come il

componente A, può essere corrotto dall‟attivazione di un guasto interno (e

precedentemente dormiente) o esterno. L‟errore così generato può essere utilizzato, ovvero


38

attivato, nel processo computazionale e, di conseguenza, può propagarsi internamente e

determinare la creazione di altri errori all‟interno del componente. Un errore presente nel

sistema ma non rilevato viene definito un errore latente. Il malfunzionamento di un

componente avviene quando la propagazione di un errore al suo interno raggiunge la sua

interfaccia, provocando l‟erogazione di un servizio errato. A sua volta, il

malfunzionamento di un componente determina l‟erogazione di un servizio errato ad altri

componenti e quindi la propagazione esterna di un errore verso di essi. Nell‟esempio il

componente A, fallendo, propaga esternamente un errore al componente B. Un errore che

corrompe lo stato di un componente a causa della ricezione di un servizio non corretto

viene definito input error, e appare come causato da un guasto esterno. L’input error così

determinato potrà a sua volta propagarsi all'interno del nuovo componente, ricorsivamente.

Propagandosi esternamente e internamente ai componenti gli errori possono infine

raggiungere l‟interfaccia del sistema, provocandone il malfunzionamento.

In generale quindi un errore all‟interno di un sistema può essere causato da:

1. un guasto interno, precedentemente dormiente, che si è attivato;

2. un guasto operazionale fisico, sia interno che esterno;

3. un guasto esterno, dovuto alla propagazione di un errore da un altro sistema tramite

la sua interfaccia.

Poiché il malfunzionamento di un componente può rappresentare un guasto esterno per un

altro componente, la catena è ricorsiva.

2.1.3 Tecniche per la valutazione della Dependability

La Dependability di un sistema si può ottenere attraverso l‟uso combinato di quattro

tecniche:

Fault prevention: per prevenire l‟occorrenza o l‟introduzione di guasti;

Fault tolerance: per fornire un servizio corretto in presenza di guasti;

attivazione

Guasto Errore Malfunzionamento propagazione


39

Fault removal: per ridurre il numero o la gravità dei guasti;

Fault forecasting: per stimare la presenza attuale, la futura incidenza e le probabili

conseguenze dei guasti.

La fault prevention mira alla realizzazione di sistemi con il minor numero di guasti

possibili, originati sia durante la fase di sviluppo che durante la loro vita operativa. Per

ridurre la presenza di guasti di progettazione si utilizzano tecniche di controllo della qualità

durante la progettazione e la realizzazione dell‟hardware e del software, come

programmazione strutturata e information hiding per il software e rigide regole di

progettazione per l‟hardware. Per prevenire guasti fisici operazionali si usano, per esempio,

schermature contro le radiazioni, per i guasti di interazione si ricorre a corsi di formazione

per gli utenti e ad una rigida manutenzione, mentre per i guasti dolosi ci si protegge con

firewalls ed Intrusion Detection Systems. Anche se tramite la fault prevention si può

ridurre l‟incidenza dei guasti, non è tuttavia possibile eliminare del tutto la possibilità di

errori umani nella progettazione o di eventi sfavorevoli durante la vita operativa del

sistema. Per questo è necessario fare ricorso alla fault tolerance.

La fault tolerance consente l‟erogazione del servizio corretto anche in presenza di guasti

attivi. Si compone di due fasi consecutive: error detection e system recovery.

L’error detection ha l‟obiettivo di verificare la presenza di errori nel sistema e di segnalare

l‟errore. L‟error detection può essere concorrente, nel caso in cui la verifica del sistema

avvenga durante l‟erogazione del servizio, oppure preventiva, se viene effettuata mentre

l‟erogazione del servizio è sospesa.

La system recovery rappresenta la seconda fase della fault tolerance ed include le

operazioni che vengono effettuate, in seguito al rilevamento di un errore, per preservare il

corretto funzionamento del sistema. Da uno stato in cui sono presenti uno o più errori, ed

eventualmente guasti, si cerca di passare ad uno stato senza gli errori rilevati e privo di

guasti dormienti che possano essere attivati ancora. La system recovery consiste nell’error

handling e nel fault handling.

L‟error handling elimina dallo stato del sistema gli errori rilevati. Può essere effettuata

tramite tre tecniche:


40

Compensation, usata quando la ridondanza dello stato permette di eliminare l'errore

correggendolo;

Backward recovery, usata quando si ripristina uno stato del sistema (detto

checkpoint) memorizzato precedentemente al rilevamento dell'errore;

Forward recovery, usata quando si porta il sistema in un nuovo stato di default privo

degli errori rilevati.

La fault handling invece cerca di prevenire ulteriori attivazioni dei guasti che hanno

provocato l‟errore. Essa è composta da quattro passi:

1. Fault diagnosis: in cui si cerca di determinare e registrare la locazione ed il tipo del

guasto che ha generato l'errore;

2. Fault isolation: in cui si effettua l'esclusione logica o fisica del componente guasto,

che verrà escluso dalla partecipazione all'erogazione del servizio;

3. System reconfiguration: in cui si attivano componenti di riserva o si ridistribuisce il

carico di lavoro del componente isolato agli altri componenti non guasti;

4. System reinizialization: in cui si controlla, si aggiorna e si registra la nuova

configurazione modificando le strutture dati del sistema.

In seguito alla procedura di fault handling si può effettuare la manutenzione correttiva, in

cui il componente guasto viene in genere rimosso e sostituito da un operatore.

La fault removal consiste nell‟eliminazione dei guasti del sistema e può avvenire sia

durante il suo sviluppo che durante la sua vita operativa. Durante lo sviluppo avviene la

verifica, il processo attraverso il quale si determina se il sistema implementa le sue

specifiche. Nella verifica in genere ci si limita a controllare se il sistema rispetta alcune

proprietà. Se così non è si cerca di capire qual è il guasto che impedisce il soddisfacimento

delle specifiche, lo si corregge, e si ripete il controllo per vedere se la correzione ha a sua

volta introdotto guasti. Tecniche di verifica possono essere statiche, e consistere in

un‟analisi statica delle caratteristiche del sistema, o dinamiche, e richiedere l'esecuzione

del sistema con degli input definiti.

La validazione è complementare alla verifica e consiste nel controllare se le specifiche

sono adeguate. Di particolare importanza nei sistemi dependable è la verifica dei


41

meccanismi di fault tolerance che permettono di raggiungere i dependability requirements.

Questo può essere fatto tramite verifiche statiche formali o dinamiche. In quest‟ultimo caso

si inseriscono guasti ed errori nel sistema per studiarne la capacità di reazione, usando

tecniche dette di fault injection; tale tecniche verranno utilizzate durante il lavoro di tesi.

Durante la vita operativa del sistema la rimozione dei guasti è chiamata manutenzione e

può essere correttiva, quando il guasto viene rimosso dopo che ha prodotto uno o più errori

rilevati, oppure preventiva, quando si cercano di rimuovere guasti presunti prima che si

manifestino producendo errori.

La fault forecasting consiste nel valutare il comportamento futuro del sistema

considerando la possibile occorrenza e/o attivazione dei guasti. Si possono fare valutazioni

qualitative, che cercano di determinare i modi in cui un sistema può fallire e le

combinazioni di guasti che possono portare al malfunzionamento, e quantitative, che

cercano di valutare in maniera statistica fino a che punto il sistema soddisfa gli attributi di

dependability, anche tale tecnica utilizza le campagne di fault injection.

2.1.3.1 La Fault Injection

Con tale tecnica i guasti sono inseriti artificiosamente nel sistema di studio osservando il

comportamento risultante. La Fault injection tenta di stabilire se la risposta del sistema

corrisponde a quella stabilita nelle specifiche in presenza di un definito spazio di fault.

Normalmente, i guasti sono iniettati in punti e stati del sistema scelti in maniera

appropriata secondo una precedente analisi del sistema.

Le tecniche di fault injection vengono adoperate per realizzare la fault removal e la fault

forecasting.

L‟applicazione delle tecniche di Fault Injection permette:

Una comprensione degli effetti dei reali guasti e di conseguenza dei relativi

comportamenti del sistema.

Una stima dell‟efficacia dei meccanismi di fault tolerance presenti nel sistema target

e di conseguenza un feedback per arricchirli o correggerli, come rimuovere dei

guasti di progettazione nei meccanismi stessi.


42

Una previsione dei comportamenti faulty del sistema target, in particolare

aggiungendo una misura di copertura fornita dai meccanismi di fault detection.

Diverse tecniche e metodi sono stati sviluppati ed integrati in strumenti specifici per la

fault injection. Due tipi di criteri devono essere considerati per caratterizzare gli studi di

fault injection destinati a verificare un sistema tollerante ai guasti: il livello di astrazione

del sistema e la forma di applicazione dell‟injection. Per quanto riguarda il livello di

astrazione, si distingue il caso in cui il sistema sotto esame è:

un sistema fisicamente disponibile (eventualmente un prototipo);

un modello di simulazione che descrive la struttura e/o il comportamento del

sistema.

Per quanto riguarda la forma di applicazione dell‟injection, distinguiamo tra:

injection hardware, quando i guasti sono introdotti direttamente sui componenti

fisici tramite alterazioni meccaniche o elettromagnetiche;

injection software, quando vengono utilizzati strumenti software che condizionano il

normale funzionamento del sistema.

2.2 Reti di sensori e Applicazioni critiche

Gli avanzamenti nel campo della tecnologia dell‟informazione avvenuti negli ultimi anni

hanno reso possibile lo sviluppo di reti di sensori wireless. Si tratta di reti composte da

sensori di dimensioni molto ridotte, dal basso costo, alimentati a batteria e dunque

autonomi, capaci di effettuare la ricetrasmissione wireless di messaggi. In virtù delle loro

caratteristiche, le Wireless Sensor Networks (per riferirci alle quali useremo l‟acronimo

WSN da ora in avanti) possono essere adoperate per una moltitudine di applicazioni nei

campi più disparati; generalmente sono chiamate a svolgere compiti di rilevazione,

controllo, comunicazione, sorveglianza e monitoraggio in scenari di tipo sia militare che

civile. Le loro dimensioni, l‟autonomia energetica e la capacità di ricevere e inviare

messaggi senza fili permettono il loro impiego in ambienti di lavoro e locazioni altrimenti

irraggiungibili; il basso costo consente di dispiegarne un grande numero, coprendo aree

anche molto estese.


43

La necessità dell‟implementazione di un‟infrastruttura di rete al contempo richiede però

l‟utilizzo di sensori più evoluti che non sono più dei semplici trasduttori di grandezze

fisiche, ma sistemi più complessi che integrano oltre alle capacità di misura anche capacità

di memorizzazione, di calcolo ed ovviamente interfacce di comunicazione. Queste

osservazioni portano alla definizione degli “smart sensor”, dispositivi integrati che sono

dotati di microcontrollori in grado di effettuare attività di comunicazione ed elaborazione

dell‟informazione.

Tali sensori possono essere applicati anche per applicazioni mission critical, cioè

applicazioni critiche che si distinguono dalle normali applicazioni informatiche per

requisiti estremamente stringenti di qualità e affidabilità, sulla base di tale tecnologia nuovi

tipi di applicazioni diventano possibili.

2.2.1 Esempi applicativi

Le reti di sensori possono essere impiegate nel controllo ambientale, come l'individuazione

degli incendi boschivi, ma anche essere installate su ponti e costruzioni per studiare il

fenomeno dei terremoti; possono essere utilizzate per compiti di sorveglianza come il

riconoscimento di intrusioni in aree protette; possono essere inseriti nei macchinari dove

non sono possibili collegamenti via cavo tra i sensori, oppure attaccati al corpo umano per

il monitoraggio a distanza dei dati fisiologici di un paziente.

2.2.2 Requisiti della dependability di WSN critiche

Delineando quali siano i requisiti a cui una rete di sensori wireless deve rispondere si

osserva che alcuni risulteranno essere comuni a qualsiasi tipologia di rete wireless (Fra gli

altri possiamo ricordare prestazioni, range, sicurezza e consumi); altri risulteranno essere

dipendenti dalla particolare applicazione, è questo il caso per esempio della determinazione

della velocità di trasmissione, visto che alcune applicazioni richiedono decine di megabits

al secondo (es. Applicazioni di video sorveglianza), mentre altre hanno requisiti meno

stringenti nell‟ordine di pochi kbit al secondo (es. Telecomandi, sensori di temperatura

ecc…). Infine vanno tenuti in conto i requisiti della dependability, dato che le WSN


44

vengono utilizzate in applicazioni critiche in cui l‟affidabilità di tali reti è fondamentale

durante il funzionamento della stessa, in quanto il malfunzionamento del sistema

porterebbe problemi molto gravi che potrebbero mettere a repentaglio la vita delle persone.

In particolare ci riferiremo al concetto di affidabilità e i requisiti che le WSN dovrebbero

rispettare. Il concetto di affidabilità si formalizza come la capacità che deve avere una rete

di conservare le proprie funzionalità indipendentemente dall‟eventuale guasto di qualche

sensore o semplicemente da una trasmissione fallita. Un nodo, ad esempio, può diventare

inutilizzabile a causa dell‟esaurimento della batteria o per danni fisici subiti nell‟ambiente

operativo.

Il livello di affidabilità ottenibile è ostacolato da tre fattori, quali:

la limitatezza delle risorse sia energetiche che di memorizzazione e di computazione

dei nodi;

limitata robustezza fisica dei sensori che assume un ruolo non trascurabile visto che

le WSN vengono spesso utilizzate in ambienti esterni avversi e persino estremi;

la casualità della topologia della rete.

I requisiti principali possono essere individuarti tra i seguenti:

1. Longevità, aumentare il „lifetime‟ del nodo sensore in modo tale da rimanere

disponibile per tutta la durata dell‟applicazione, evitando di sostituire le batterie;

2. Fault tolerant & autoconfigurazione, qualora si verificassero dei guasti ai nodi

sensore la rete dovrebbe continuare a svolgere le funzioni, automatizzare il

processo di configurazione e di adattamento dinamico ai cambiamenti della

topologie e dell‟ambiente circostante evitando l‟intervento umano potrebbe essere

vista come una possibile tecnica di fault tolerance;

3. Sicurezza, evitare situazioni che possano compromettere il normale funzionamento

della rete dovute a diversi tipi di „attacchi‟ maliziosi o meno;

4. Copertura, con il quale si cerca di stimare un numero sufficiente di nodi sensori

affinché un evento possa essere esaminato nella sua totalità e permettere di

ricoprire in maniera opportuna l‟area qualora un nodo o un insieme di nodi

cadessero, fornendo una specie di ridondanza;


45

5. Trasporto dati affidabile, aspetto con il quale si definiscono strategie per assicurare

il recapito delle misurazioni al centro raccolta. In particolare si definiscono

strategie per combattere errori di trasmissione, di omissione e di congestione;

6. Intolleranza al ritardo(real time), i ritardi del sistema devono essere minimizzati

poiché potrebbero compromettere la risposta del sistema a situazioni di pericolo.

Tali requisiti sono in conflitto tra loro, nel migliorare un di essi potrebbe essere

compromesso un altro, ciò è dovuto ai problemi esposti precedentemente, ad esempio la

fault tolerance e la longevità possono essere in contrapposizione in quanto per garantire

una maggiore fault tolerance, ad esempio aggiungendo maggiori controlli e aumentare il

numero di nodi presenti nella rete, vi sarà un maggiore consumo energetico e una relativa

riduzione del lifetime. Stabilire il giusto tradeoff rappresenta una sfida nelle reti di sensori

senza filo.

2.3 Guasti di una WSN

Le reti di sensori wireless sono soggette a numerosi possibili guasti quali:

Errori di trasmissioni: l‟inaffidabilità del mezzo wireless e la non prevedibilità

dell‟ambiente potrebbero determinare la corruzione dei pacchetti trasmessi e quindi

ad essere ricevuti con errori o anche non ricevuti.

Guasti ai nodi: molto spesso a causa delle condizioni difficili nell‟ambiente in cui

una rete di sensori potrebbe operare, guasti imprevedibili dei nodi possono avvenire

in qualsiasi momento. Inoltre l‟inevitabile esaurimento dell‟energia di cui un nodo

dispone lo porta prima o poi a scomparire dalla rete. Tale problematica sarà

approfondita successivamente.

Guasti nei collegamenti: il guasto di un nodo potrebbe causare l‟interruzione di uno

o più link della rete, inoltre cambiamenti nelle condizioni dell‟ambiente in cui

opera la rete (ad esempio un aumento dei livelli di interferenze elettromagnetiche)

potrebbe far nascere fenomeni di asimmetrie tra i collegamenti o la completa

rottura.

Interruzione di un percorso: quando la topologia della rete cambia a seguito di un


46

guasto ad un nodo o ad un collegamento, i percorsi verso la base-station potrebbero

non essere più validi. Pertanto protocolli di routing poco reattivi a fronte di tali

situazioni, potrebbero fare uso di percorsi, nei quali i pacchetti potrebbero essere

persi o essere ritardati a seguito di eventuali cicli.

Nodi o collegamenti congestionati: a seguito della topologia della rete e della natura

dei protocolli di routing, certi nodi o certi collegamenti potrebbero diventare

congestionati. Questo potrebbe portare a grandi ritardi o anche alla perdita di

qualche pacchetto.

2.3.1 Guasti di un nodo sensore

In particolare ci occuperemo dei guasti che si presentano nei singoli nodi sensore,

distinguendoli tra quelli transienti e quelli permanenti.

Per guasti permanenti intendiamo guasti stabili e continui nel tempo, come ad esempio

l‟esaurimento della batteria oppure la rottura del ricetrasmettitore del sensore.

Per guasti transienti intendiamo guasti legati a momentanee condizioni ambientali, ad

esempio condizioni fisiche e di interazione con altri componenti, e che scompaiono

definitivamente senza la necessità di alcuna operazione di ripristino, gli errori che essi

causano sono detti “soft errors”.

Ci concentreremo esclusivamente sui soft error, poiché con la progressiva evoluzione delle

tecnologie microelettroniche che ha portato alla realizzazione di circuiti integrati sempre

più complessi, caratterizzati, per contro, da una riduzione delle loro dimensioni fisiche e

dei loro parametri elettrici, ha fatto sì che alcuni fenomeni atmosferici o ambientali, prima

considerati ininfluenti sul comportamento dei circuiti integrati, siano ora in grado di

perturbare il funzionamento dei moderni dispositivi microelettronici.

Fra questi fenomeni va ricordata soprattutto la ionizzazione del substrato di ossido, dovuta

alle radiazioni, ai disturbi elettromagnetici o alle variazioni della temperatura.

L‟impatto di particelle dotate di carica elettrica su zone sensibili dei circuiti elettronici può

provocare la temporanea inversione dei bit (chiamata anche upset o bit-flip) delle

informazioni immagazzinate nel dispositivo, causando malfunzionamenti di vario tipo. A


47

questi disturbi si dà il nome di Single Event Upsets (SEU).

In base alle precedenti considerazioni, lo studio degli effetti dei SEU sui dispositivi

microelettronici destinati a lavorare in presenza di radiazioni ha assunto una particolare

importanza. Va inoltre tenuto presente che, visti i livelli di integrazione attualmente

raggiunti, anche i neutroni presenti nell‟atmosfera – finora ritenuti innocui – possono avere

abbastanza energia da causare bit-flip nelle celle di memoria presenti nei circuiti integrati.

Questa fonte di disturbi, sebbene costituisca un problema anche nei sistemi che lavorano a

terra, interessa in modo particolare i dispositivi destinati a lavorare su veicoli aerospaziali,

in quanto a 30000 piedi il flusso di neutroni è da 4 a 8 volte più alto che al livello del

suolo.

Da rilevare l‟assoluta mancanza nel microcontrollore del nodo sensore di circuiti di

ridondanza e di controllo dell‟errore, ciò è dovuto alle problematiche esposte

precedentemente ed a vincoli di progettazione in cui si è data maggiore importanza alla

semplicità dell‟architettura in maniera tale da ridurre il consumo di energia e le dimensioni

del nodo.

2.4 Valutazione della Dependability di WSN

Come spiegato in precedenza le WSN vengono utilizzate in applicazioni critiche, in cui ad

esempio la vita delle persone può essere in serio pericolo quindi valutare l‟affidabilità delle

WSN risulta essere uno studio obbligato.

Di seguito discuteremo brevemente, nel primo sotto-paragrafo, daremo una panoramica

dello stato dell‟arte della valutazione dell‟affidabilità delle reti di sensore senza filo; nel

secondo sotto-paragrafo invece descriveremo l‟approccio utilizzato nel lavoro di tesi

proposto.

2.4.1 Stato dell’arte

Negli ultimi anni sono stati condotti degli studi dedicati alla valutazione dell‟affidabilità

nelle reti di sensori senza cavo.

Gli effetti sollevati dal malfunzionamento di un singolo nodo sullo stato di funzionamento


48

di una WSN sono analizzati nel lavoro di Shakkottai et al. In questo contesto è stato

individuato un limite superiore alla probabilità che tutti i nodi siano connessi e tutta l‟area

della rete sia coperta, questo nell‟ipotesi che i nodi siano uniformemente distribuiti sul

suolo e che la probabilità di malfunzionamento sia anch‟essa uniforme in tutta la rete.

Viene inoltre ricavata una condizione necessaria e sufficiente affinché la rete continui a

coprire l‟intera area (nonostante l‟inaffidabilità dei nodi che la compongono) e viene anche

ricavata la minima probabilità di funzionamento di un nodo al di là della quale la

“copertura” dell‟area non è più garantita. Un aspetto non contemplato dal lavoro è però

come la connettività sia influenzata dalla morte di nodi faulty o con batterie scariche,

ipotesi in cui non varrebbe più l‟assunzione di densità uniforme della rete.

Un modello di reliability è poi fornito in Beinet al. e AboElFotoh et al.. Negli studi di

Beinet et al. sono presentati alcuni modelli a catene di Markow per diverse tipologie di

sensori. La reliability viene calcolata per diversi “failure rate” e poi i modelli sono

comparati in termini di costo e della distribuzione cumulativa e media della funzione di

reliability. Arricchisce il lavoro anche un‟analisi comparativa della reliability della rete

condizionata all‟utilizzo di tecniche di ridondanza spaziale o di codici ECC (error

correcting code)

In Iyengar et al. focalizzano l‟attenzione sulle misure di reliability per WSN, fornendo

anche delle stime sul minimo e massimo ritardo nella consegna di un messaggio di un

nodo verso il sink. Viene adottato all‟uopo un modello a grafo probabilistico per

rappresentare la rete, dove le probabilità (di perdita di pacchetti) sono ricavate da stime sul

tasso di malfunzionamento dei sensori. Viene definita la reliability di una WSN come la

probabilità che esista un cammino tra il sink e almeno un unico nodo funzionante del

cluster: adottando questa definizione viene dimostrato come per reti di topologia

arbitraria, la soluzione del modello di affidabilità considerato rappresenti un problema di

complessità non polinomiale, tranne che per un caso particolare analizzato, per cui

vengono fornite anche delle misure ottenute tramite simulazione.

Gupta e Kumar analizzano l‟impatto della connettività sulla reliability della rete. A tale

scopo viene analizzano il comportamento di una WSN organizzata in clusters, attraverso


49

un fault model in cui vengono considerati solo i malfunzionamenti del gateway relativi

all‟esaurimento delle batterie e a malfunzionamenti del modulo radio: questi ultimi dovuti

sia a guasti hardware che a malfunzionamenti di nodi nel suo range operativo. Tutti i

malfunzionamenti considerati sono di durata permanente. In base a questo modello dei

malfunzionamenti, viene proposto un meccanismo di recupero basato sul consenso tra i

gateway ancora funzionanti. Per testare la copertura della strategia proposta, viene adottata

una tecnica di iniezione dei guasti simulata, tramite la quale viene dimostrato che

l‟approccio fornisce un miglioramento considerevole sulla stabilità del sistema riducendo

l‟overhead della ri-clusterizzazione e della riorganizzazione della rete. Il lavoro fornisce

anche un‟analisi teorica sulla soglia del range radio che garantisce la connettività tra nodi

di una rete dislocata casualmente, utilizzando un modello matematico.

Infine, uno studio, sull‟impatto di fenomeni di invecchiamento dei nodi sulla reliability

della rete, è sviluppato da Krishmachari dove viene analizzata la correlazione tra la durata

della vita di ogni nodo e il suo consumo energetico in rispetto di alcune metriche di

affidabilità come il Mean Time To Failure. Risultati interessanti sono forniti in merito alle

misure relative all‟impatto delle strategie di data aggregation sulla durata della vita di un

nodo.

2.4.2 Valutazione della Dependability di un nodo sensore

I precedenti lavori descritti sono per lo più orientati ai guasti di rete o ai guasti di nodo

permanenti (ad es. esaurimento batteria) ma non a quelli intermittenti. Inoltre nessun

lavoro scende nel dettaglio del comportamento faulty del singolo nodo, che risulta quindi

non ben conosciuto. Il lavoro di tesi quindi mira a colmare questa mancanza proponendo di

utilizzare le ben note tecniche di fault injection ai nodi sensori, in particolare si propone di

progettare e sperimentare una tecnica di fault injection software, chiamata in letteratura

SoftWare Implemented Fault Injection nota con l‟acronimo di SWIFI.

Lo studio condotto utilizza una campagna di fault injection nel microcontrollore del nodo

sensore, precisamente nella memoria e nei registri, simulando il comportamento dei guasti

transienti, in particolare i bit-flip. La scelta della fault injection è dovuta alla volontà di


50

ridurre l‟attesa del sistema in esercizio, dato che i guasti che si riscontrano durante

l‟esercizio del sistema potrebbero richiedere degli anni e dato il rapido avanzamento delle

tecnologia, i risultati che otterremmo sarebbero inutili un volta pervenuti. La fault injection

ci permettere di studiare in maniera più rapida la dependability del sistema in quanto può

essere applicata anche durante fase prototipale del sistema, utilizzando quindi il prototipo.

Inoltre la tecnica proposta realizza la fault injection a livello Assembly, tale scelta è

motivata dall‟impossibilità nel realizzare tale tecnica a livello dei normali linguaggi

imperativi, quali ad esempio il „c‟ con cui è possibile programmare il microcontrollore

attraverso il compilatore avr-gcc appartenente alle binutils, cioè linguaggi con un (ad es.

impossibile stabilire quale cella di memoria dovrà essere affetta dal fault) elevato livello di

astrazione in cui l‟esperimento risulta essere difficilmente controllabile; inoltre rispetto alla

possibilità di utilizzare dell‟hardware dedicato risulta essere più economico.


51

Capitolo 3

Tecniche di Fault Injecton

3.1 Introduzione

Generalmente, la valutazione della dependabilty si basa sullo studio degli errori e dei

malfunzionamenti, localizzando le origini e ripristinando le applicazioni usando i

meccanismi di fault tolerance. La natura distruttiva dei crash e la lunga latenza degli errori

rendono difficile identificare le cause dei malfunzionamenti negli ambienti operativi.

Per identificare e capire i potenziali malfunzionamenti, è possibile utilizzare un approccio

sperimentale per studiare la dependability di un sistema. L‟approccio sperimentale è

applicato non solo durante le fasi d‟ideazione e progettazione, ma anche durante la fase

prototipale e quella operativa.

Per utilizzare l‟approccio sperimentale, bisogna prima comprendere l‟architettura del

sistema, la struttura e il comportamento. Precisamente, sorge la necessità di conoscere la

tolleranza ai guasti e ai malfunzionamenti, includendo i meccanismi di rilevazione

intrinseca e di recupero, e il bisogno di strumenti specifici per iniettare guasti, creare

malfunzionamenti ed errori, monitorando infine i loro effetti.

Gli ingegneri molto spesso usano la Fault Injection, economica e basata sulla simulazione,

per stimare la dependability del sistema, durante le fasi di definizione e progettazione. A

questo punto, il sistema in osservazione è solo un insieme di astrazioni di alto livello; i

dettagli implementativi sono ancora da determinare. Di conseguenza il sistema è simulato

sulla base di assunzioni semplificate.


52

La Fault Injection basata sulla simulazione assume che errori e malfunzionamenti

accadano in accordo con determinate assunzioni, è utile per stimare l‟efficacia dei

meccanismi di fault tolerance e la dependability del sistema; essa fornisce un tempestivo

feedback agli ingegneri del sistema. In tale approccio i guasti sono iniettati nel modello di

simulazione del sistema target in modo tale da permettere di controllare la tempificazione,

il tipo di guasto e i componenti affetti nel modello con accuratezza dipendente dal livello

di astrazione del simulatore. Con un simulatore è possibile anche iniettare molto

precisamente dei guasti e raccogliere informazioni dettagliate sui loro effetti. Comunque,

essa richiede accurati parametri di input, difficili da fornire, in quanto la progettazione e la

tecnologia cambiano rendendo difficile usare il precedente sistema di misura. Inoltre tale

tecnica richiede dei tempi lunghi per fornire un modello di simulazione accurato di un

sistema complesso.

Testare un prototipo permette di valutare il sistema senza alcuna assunzione sulla

progettazione del sistema fornendo risultati più accurati. Nella Fault Injection basata sui

prototipi, iniettiamo fault nel sistema per:

Rilevare i colli di bottiglia della dependability;

Studiare il comportamento del sistema in presenza di fault;

Determinare la copertura della rilevazione degli errori e dei meccanismi di recupero;

Valutare l‟efficacia dei meccanismi di Fault Tolerance e perdite di prestazioni.

Per realizzare la Fault Injection basata sui prototipi, i fault vengono iniettati sia a livello

hardware (fault logici o elettrici) che a livello software (alterando codice e dati) e poi gli

effetti vengono monitorati. Il sistema valutato può essere sia un prototipo che il sistema

completamente operativo.

Invece di iniettare guasti, gli ingegneri possono direttamente misurare il sistema in

esercizio, manipolando gli effettivi workload. L‟analisi basata sulle misure usa dati reali, i

quali contengono molte informazioni sulla naturale occorrenza di errori, malfunzionamenti

e in alcuni casi sui tentativi di recupero. Analizzando tali dati si può fornire una

comprensione degli errori reali, le caratteristiche dei malfunzionamenti e costruire dei

modelli analitici. Comunque l‟analisi basata sulle misure è limitata a rilevare gli errori. In


53

aggiunta, i dati devono essere raccolti in periodi temporali lunghi poiché gli errori e i

malfunzionamenti possono verificarsi nel lungo periodo. Le condizioni sul campo possono

variare ampiamente, creando così dubbi sulla validità statistica dei risultati.

Sebbene ognuno dei tre metodi sperimentali ha le sue limitazioni, i loro valori sono

complementari l‟uno all‟altro permettendo così uno ampio spettro per lo studio della

dependability.

Gli ingegneri usano la Fault Injection per testare sistemi o componenti fault-tolerant. La

Fault Injection testa la fault detection, fault isolation e le capacità di riconfigurazione e

recupero.

3.2 Sistema di Fault Injection

Un sistema di Fault Injection tipicamente è composto da un target system, un fault

injector, una libreria di fault, un generatore di workload, una libreria di workload, un

controllore, un raccoglitore di dati, un monitor e un analizzatore di dati.

Il fault injector inietta guasti nel target system come se fossero comandi eseguiti dal

generatore di workload.

Il monitor si occupa dell‟attivazione dei guasti e il loro impatto sul comportamento del

target system, inoltre inizializza la raccolta dei dati ogniqualvolta sia necessario. Il

raccoglitore di dati realizza una raccolta di dati online, e l‟analizzatore di dati, il quale può

essere offline, realizza un‟analisi ed una elaborazione dei dati. Il controllore esamina

l‟esperimento.

Fisicamente, il controllore è un programma che è in esecuzione sul target system o su un

computer diverso. Il fault injector può essere un hardware o software ad-hoc. Esso può

supportare diversi tipi di fault, locazioni dei fault, istanti di fault e appropriate semantiche

hardware e strutture software – tali valori sono prelevati da una libreria dei fault. La

libreria dei fault è un componente distinto, il quale permette un più grande portabilità e

flessibilità.

Il Generatore di workload, il monitor e i restanti componenti possono essere realizzati nel

medesimo modo.


54

3.3 Metodi ed implementazioni dell’Injection

L‟iniezione dei guasti può essere realizzata in due modi:

via software, cioè utilizzando dei strumenti software;

via hardware, utilizzando dell‟hardware aggiuntivo al target system.

La scelta tra un iniezione di guasti software o una hardware dipende dal tipo di guasto di

interesse e dallo sforzo richiesto per crearlo. Per esempio, se si è interessati ad un guasto di

stuck-at-faults (un guasto che forza un valore permanente in un punto del circuito), un

injector hardware è preferibile poichè è possibile controllare direttamente la locazione del

fault. L’injector di fault permanenti usando metodi software va incontro ad un alto

overhead o risulta essere impraticabile. Comunque, se si è interessasti ad un‟alterazione dei

dati, l‟approccio software potrebbe essere sufficiente. Alcuni guasti, come bit-flips nelle

celle di memoria, possono essere realizzati in entrambi i modi. In casi come il precedente

requisiti aggiuntivi quali costo, accuratezza, grado di intrusione e ripetibilità potrebbero

guidare la scelta dell‟approccio da utilizzare.

3.3.1 Fault Injection hardware

La Fault Injection realizzata via hardware utilizza un hardware aggiuntivo per introdurre

guasti nell‟hardware del target system. I metodi di fault injection hardware possono essere

classificati in due categorie, in funzione del guasto e della sua locazione:


55

Con contatto. L’injector è fisicamente contattato con il target system, producendo

tensione o corrente, cambiando quella del chip del target system.

Senza contatti. L’injector non è fisicamente contattato con il target system. Una

sorgente esterna produce dei fenomeni fisici, come radiazioni di ioni pesanti e

interferenze elettromagnetiche, generando correnti spurie nel chip del target

system.

Tali metodi risultano essere molto comodi per studiare le caratteristiche di dependability

dei prototipi che richiedono un‟alta risoluzione temporale per il monitoraggio e

l‟attivazione dell‟hardware (per esempio la latenza dei guasti nella CPU) o la richiesta di

accesso a locazioni che sono difficili da raggiungere da altri metodi di fault injection.

3.3.1.1 Injection con contatto

La Fault Injection hardware usando direttamente il contatto con i pin del circuito, spesso

chiamata pin-level injection, è probabilmente il più comune metodo di fault injection

hardware. Ci sono due principali tecniche per alterare la tensione e la corrente elettrica dei

pin:

Sonde attive. Tale tecnica aggiunge corrente attraverso le sonde collegate ai pin,

alterando il valore della corrente elettrica. Bisogna però fare attenzione al

quantitativo di corrente aggiuntiva da iniettare in quanto potrebbe danneggiare

l‟hardware del target system.

Inserzione di Socket. Questa tecnica inserisce una socket tra l‟hardware del target e la

board. La socket inserita inietta dei stuck-at o più fault logici complessi

nell‟hardware, forzando segnali analogici che rappresentano valori logici desiderati

sui pin dell‟hardware del target system. I segnali dei pin possono essere invertiti,

messi in AND o OR con gli altri pin adiacenti oppure con i segnali presenti

precedentemente sugli stessi pin.

Entrambi i metodi forniscono una buona controllabilità della locazione e dei tempi

dei fault con piccole o nessuna perturbazione al target system.


56

3.3.1.2 Injection senza contatto

Questi guasti sono iniettati creando radiazioni di ioni pesanti. Uno ione passa attraverso la

regione di svuotamento sul dispositivo target e genera corrente. Un‟alternativa potrebbe

essere quella di piazzare l‟hardware del target dentro o vicino ad un campo

elettromagnetico iniettando così un fault. Agli ingegneri considerano tali metodi poiché

essi imitano i fenomeni fisici naturali. Comunque, in tali metodi risulta difficile stabilire

dove e l‟istante dell‟iniezione del fault poiché non può essere precisamente stabilito

quando il campo si instaura e il momento dell‟emissione degli ioni pesanti.

3.3.2 Fault Injection Software (SWIFI)

La Fault Injection software, anche chiamata SWIFI (SoftWare Implemented Fault

Injection), utilizza degli appositi strumenti software per iniettare dei guasti nel target

system. Essa permette di testare applicazioni e sistemi operativi, che risulta essere difficile

realizzare attraverso la fault injection hardware. Se l‟obiettivo è un‟applicazione, l’injector

di guasti è inserito nell‟applicazione stessa oppure si interpone tra l‟applicazione e il

sistema operativo. Se l‟obiettivo è il sistema operativo l’injector deve essere “embedded”

al sistema operativo stesso, in quanto è molto difficile aggiungere uno strato tra il sistema

operativo e la macchina. La SWIFI risulta essere allettante poiché essa non richiede

hardware costoso.

Sebbene l‟approccio software risulti essere flessibile, esso ha dei limiti:

Non può iniettare guasti in locazioni che sono inaccessibili al software;

Gli strumenti software potrebbero disturbare l‟esecuzione del workload sul target

system ed anche alterare la struttura del software originale. Un‟attenta

progettazione dell‟ambiente di iniezione può minimizzare la perturbazione del

workload.

La bassa risoluzione temporale dell‟approccio potrebbe causare problemi di fedeltà.

Per lunghi guasti latenti, come fault di memoria, la bassa risoluzione temporale

potrebbe non essere un problema. Per brevi guasti latenti, come guasti di CPU e

bus, l‟approccio potrebbe fallire nel catturare determinati comportamenti di errore,


57

come la propagazione. Gli ingegneri possono risolvere questo problema utilizzando

un approccio ibrido, combinando la versatilità della fault injection software e

l‟accuratezza del monitoraggio hardware. L‟approccio ibrido è ben adatto per

misurare latenze estremamente brevi. Comunque, il monitoraggio hardware in

questione può far aumentare il costo e diminuire la flessibilità limitando i punti di

osservazione e la dimensione della memoria dati.

I metodi di software fault injection vengono classificati in base al tempo in cui sono

iniettati: durante la compilazione o durante l‟esecuzione.

3.3.2.1 Injection a tempo di compilazione

Per iniettare guasti a tempo di compilazione, le istruzioni del programma devono essere

modificate prima che l‟immagine del programma venga caricata ed eseguita. Piuttosto che

iniettare guasti nell‟hardware del target system, questo metodo inietta errori alterando il

codice sorgente o il codice Assembly del programma in questione per emulare gli effetti dei

guasti hardware, software e transienti. L‟injection genera un‟immagine del software

erronea, e quando il sistema utilizza tale immagine, i guasti vengono attivati. Tale metodo

richiede la modifica del programma che permetterà di valutare gli effetti dei guasti, esso

inoltre non richiede software aggiuntivo durante il tempo di esecuzione. inoltre esso non

causa nessuna perturbazione al target system durante l‟esecuzione. Tale metodo permette

di emulare dei guasti permanenti. L‟implementazione di tale metodo risulta essere molto

semplice, ma non permette l’injection di guasti in maniera interattiva quando il programma

è in esecuzione.

3.3.2.2 Injection a tempo di esecuzione

Durante il tempo di esecuzione, è necessario un meccanismo per attivare la fault injection.

Comunemente i meccanismi di attivazione comprendono:

Time-out. La più semplice tra le tecniche di attivazione, un timer scade ad un

determinato istante, attivando l’injection. Precisamente, l‟evento di time-out genera

un interruzione che invoca la fault injection. Il timer può essere sia software sia


58

hardware. Tale metodo non modifica l‟applicazione del programma di workload.

Tale meccanismo è comodo per realizzare guasti hardware transienti e intermittenti.

Eccezione/trap. In questi casi, un eccezione hardware o una trap software trasferisce

il controllo al fault injector. Diversamente dal time-out, eccezioni/trap possono

iniettare il guasto qualora determinati eventi o condizioni accadano. Quando la trap

viene eseguita un interruzione viene generata la quale trasferisce il controllo al

manipolatore dell‟interruzione. Un‟eccezione hardware invoca l‟injection quando

l‟evento hardware osservato si presenta (ad esempio quando una particolare

locazione di memoria viene acceduta). Entrambi i meccanismi devono essere

linkati al vettore delle interruzioni.

Inserzione di codice. In questa tecnica, vengono aggiunte delle istruzioni al

programma in questione che richiamano la fault injection prima di eseguire

particolari istruzioni, molto simile al metodo di modifica del codice. Diversamente

dal metodo di modifica del codice, l‟inserzione di codice realizza la fault injection

durante l‟esecuzione del programma e aggiunge istruzioni piuttosto che cambiare le

istruzioni originali. Diversamente anche dal metodo trap, l‟iniettore dei fault

potrebbe appartenere al programma in questione ed eseguito nella modalità utente

piuttosto che in quella di sistema.

3.4 Injection a livello Assembly

Iniettare guasti transienti, come detto nel primo capitolo, potrebbe essere molto importante

per studiare la dependability del sistema e qualora fosse possibile, andare a riscontrare

dove accadono, introducendo dei circuiti o strumenti di più alto livello per correggere lo

stato alterato.

Iniettare dei guasti a livello Assembly potrebbe essere una valida modalità per creare dei

SEU e studiarne le conseguenze sul sistema. Il modo tipico di realizzare la fault injection a

tale livello è utilizzarla in maniera casuale ma tale tecnica non risulta essere molto

proficua in quanto molti dei fault iniettati potrebbero non essere attivati. Esempi tipici

potrebbero essere iniettare un valore sbagliato in un registro prima che il registro venga


59

scritto dalla successiva istruzione oppure andare a sporcare il contenuto di un area di

memoria che non verrà mai utilizzata. In molti strumenti la locazione e l‟istante

dell‟iniezione del guasto sono scelti casualmente dallo spazio dei fault, il quale risulta

essere molto esteso, causando un innalzamento dei costi per valutare in maniera

appropriata la dependability del sistema, con una buona rilevanza statistica.

3.4.1 Tecniche di analisi del codice

Per risolvere il problema e ridurre i costi di valutazione, è possibile utilizzare due tecniche

di analisi: La Pre-injection e la Post-injection.

L‟analisi Post-injection usa i risultati degli esperimenti di una campagna di fault injection

precedente per realizzarne una nuova.

L‟analisi di Pre-injection usa le conoscenze del flusso di esecuzione del programma e

delle risorse utilizzate, per scegliere la locazione e l‟istante dove iniettare i guasti, prima di

ogni esperimento.

La tecnica di analisi Pre-injection permette di iniettare in particolare bit-flips transienti

nei registri della CPU e nelle locazioni di memoria.

L‟obiettivo della tecnica di analisi Pre-injected è quello di ottimizzare lo spazio dei fault

dal quale vengono selezionati i fault durante l‟esperimento. L‟analisi usa le informazioni

di esecuzione del programma per:

Eliminare i guasti che non verranno attivati;

Cercare classi di equivalenza dei guasti, inserendo uno solo dei guasti nello spazio dei

fault ottimizzato.

Ciò è raggiunto applicando la seguente regola: i guasti dovrebbero essere posti nelle

risorse immediatamente prima che l’istruzioni che la leggono vengano eseguite. Un bit-

flip in una risorsa, dove per risorsa intendiamo i registri della CPU, locazioni della

memoria centrale e altri elementi a stati dove un bit-flip potrebbe occorrere, potrebbe

manifestarsi quando essa viene letta per realizzare un‟operazione.

Le risorse disponibili nei computer sono, di solito, maggiori rispetto a quelle necessarie

all‟applicazione durante l‟esecuzione. Questo sottolinea la reale necessità di iniettare


60

guasti solo nelle risorse realmente utili specificato nella prima regola per l‟ottimizzazione.

P. Yuste et al. tentarono di evitare i guasti in locazioni di memoria non utilizzati. Essi

ottennero il 12% dei guasti effettivi e indicarono che una scelta casuale dei guasti da uno

spazio dei fault non limitato che consiste di tutte le possibili locazioni e istanti in cui

avvengono i fault non è un approccio valido. Evitare regioni di memoria non utilizzate

potrebbe essere fatto manualmente analizzando il memory map dell‟applicazione e

scegliendo i segmenti (Stack, heap,..) validi per la fault injection.

Alcuni studi condotti da Guthoff e Sieh hanno rilevato che il numero delle iniezioni in un

componente del sistema specifico dovrebbe essere proporzionale alla sua utilizzazione.

L‟utilizzo dei registri è definito come la misura della probabilità che un guasto iniettato si

manifesti come un errore. Inoltre il tempo per la fault injection viene stimato come il ciclo

di vita del dato. Il ciclo di vita del dato ha inizio quando viene inizializzato il registro

(accesso in scrittura) e finisce con l‟ultimo accesso in lettura prima del successivo accesso

in scrittura. Secondo il modello dei guasti del singolo bit-flip, i fault devono essere iniettati

solo durante il ciclo di vita del dato, appena prima di ogni accesso in lettura.

3.4.2 Regole di analisi del codice

Benso et al. presentarono un insieme di regole con l‟obiettivo di ridurre la lista dei guasti

da iniettare. Le regole riducono lo spazio dei fault senza influenzare l‟accuratezza dei

risultati della campagna di fault injection, evitando le iniezioni di guasti per le quali il

comportamento potrebbe essere prevedibile. Dalla analisi del codice Assembly e da alcune

esecuzioni del sistema fault free essi hanno individuato le seguenti regole:

1. Evitare modifiche all‟opcode dell‟istruzione, in quanto è prevedibile che venga

richiamata una eccezione del processore.

2. Eliminare guasti nelle istruzioni già eseguite e che non verranno più eseguite.

3. Eliminare guasti all‟esterno del ciclo di vita del dato.

4. Raggruppare i guasti che operano sugli stessi bit della stessa risorsa in istanti

temporali adiacenti, cioè nello stesso ciclo di vita della risorsa, in un‟unica classe in

modo tale da iniettare un solo guasto tra essi.


61

3.4.3 Classificazione dei risultati dell’analisi

I risultati delle campagne di fault injection, ovvero gli outcome, vengono suddivisi i tre

categorie:

1. Errori rilevati - Tutti gli errori effettivi che sono segnalati dal meccanismo di

rilevamento di errori hardware incluso nel processore.

2. Output sbagliati - Tutti gli effettivi errori che non sono rilevati dal processore che

portano a risultati sbagliati.

3. Errori Non Effettivi - Errori che non influenzano l‟esecuzione del sistema durante

l‟intervallo di tempo dell‟esperimento scelto.

Tecniche software peri l’iniezione di guasti su microcontrollori per reti di sensori senza filo

62

Capitolo 4

Una tecnica per la SWIFI su nodi sensore

4.1 Descrizione della tecnica e assunzioni sui guasti

In questo capitolo verrà descritta la tecnica realizzata per la SWIFI su un microcontrollore

per reti di sensori senza filo. La tecnica proposta può essere brevemente descritta

attraverso i seguenti passi:

1. Analisi del sistema fault-free;

2. Set-up degli esperimenti;

3. Realizzazione della libreria dei fault;

4. Conduzione degli esperimenti;

5. Analisi dei risultati e confronto con la Golden copy.

L‟approccio descritto in seguito più chiaramente, segue le regole descritte nel paragrafo

3.4.2, in particolare esso sfrutterà conoscenze relative all‟esecuzione del sistema nella

modalità fault-free, quindi utilizzeremo la tecnica di analisi di pre-injection, analizzando le

risorse utilizzate, tale conoscenza risulta utile come detto in precedenza per evitare i fault

che non verranno mai attivati, successivamente verranno decise le tipologie di fault da

applicare al sistema.

Il modello dei fault adottato è del singolo bit-flip, conosciuto anche come Single Event

Upsets (SEU). Tali fault possono essere iniettati nei registri del processore, nella memoria

dati e nell‟area codice tramite l‟utilizzo di istruzioni Assembly. Abbiamo scelto di iniettare

dei SEU rispetto ai guasti di stuck-at, come spiegato nel capitolo 2, e in secondo luogo per


63

la facilità di realizzazione.

Utilizzeremo inoltre la tecnica di inserzione di codice, aggiungendo delle istruzioni al

programma in questione che richiamano la fault injection prima di eseguire particolari

istruzioni. Le istruzioni aggiunte prima della istruzione originale vengono realizzate

sottoforma di procedure di injection, tali procedure vengono richiamate solo se

un‟opportuna procedura di controllo stabilisce che l‟instante di injection è raggiunto,

evitando così di ripetere più volte l‟injection qualora l‟istruzione in questione venga

richiamata più volte, simulando così più volte il SEU, cosa che non accade nella realtà.

Una volta selezionati gli esperimenti, verranno analizzati i risultati e le risorse utilizzate.

4.2 Analisi del sistema Fault-Free

L‟analisi del sistema fault free consiste nello studio statico e dinamico del sistema

originario, anche detto golden copy, al fine di comprenderne a fondo le caratteristiche.

Tale studio è fondamentale per la implementare la pre-injection: la pre-injection infatti si

basa su una conoscenza a priori del flusso di esecuzione e delle risorse utilizzate del

sistema in modo da realizzare delle campagne di fault injection, che evitino l‟iniezione di

guasti che non verranno attivati.

Tale analisi si compone di due passi principali:

1. Analisi statica;

2. Analisi dinamica.

L‟Analisi statica del sistema che consiste nel studiare il codice e i moduli del sistema

d‟esame.

L‟Analisi dinamica volta a individuare quali segmenti di codice, e porzioni di memoria

sono utilizzati durante la normale esecuzione del sistema.

Le due analisi effettuate si sposano pienamente con la tecnica di analisi di Pre-injection.

4.3 Set-up degli esperimenti

In tale paragrafo daremo delle delucidazioni sul cosa, dove e quando iniettare i guasti.


64

Il cosa è rappresentato dai SEU (Single Event Upsets ), ma tale tecnica, come detto

precedentemente può iniettare altri tipologie di guasti come ad esempio gli Stuck-at;

Per dove intendiamo la memoria dati, l‟area codice e i registri del microcontrollore, tutto

ciò sarà approfondito nei successivi paragrafi, in particolare nel paragrafo relativo alla

libreria dei guasti.

Il quando è rappresentato dall‟istante in cui è eseguita, tra le „n‟ volte, l‟istruzione da

iniettare, il principio di funzionamento è implementato dalla procedura di controllo,

introdotta nel paragrafo 4.7.

4.4 Conduzione degli esperimenti

Utilizzeremo la tecnica di inserzione di codice, in cui vengono aggiunte delle istruzioni al

programma che richiamano la fault injection dopo di eseguire particolari istruzioni.

Diversamente dal metodo di modifica del codice, l‟inserzione di codice realizza la fault

injection durante l‟esecuzione del programma e aggiunge istruzioni piuttosto che cambiare

le istruzioni originali. Diversamente anche dal metodo trap, l‟iniettore dei guasti potrebbe

appartenere al programma in questione ed eseguito nella modalità utente piuttosto che in

quella di sistema.

Abbiamo deciso di utilizzare le regole proposte da Benso et al., come spiegato nel capitolo

3, per selezionare i guasti da iniettare nel sistema, in maniera tale da evitare i guasti che

non verranno attivati durante la campagna e ridurre lo spazio dei guasti.

L‟approccio proposto inserisce come spiegato delle procedure di injection nel programma

in esecuzione, successivamente è osservato il comportamento classificandolo nel modo

descritto nel capitolo 3 e infine sono raccolte le informazioni relative all‟utilizzo della

memoria e al flusso d‟esecuzione.

4.5 Analisi dei risultati e confronto con la Golden copy

L‟analisi dei risultati ottenuti dall‟applicazione della tecnica consistono nel valutare il

comportamento del sistema in particolar modo rilevare l‟incidenza dei guasti e i possibili

malfunzionamenti causati. Successivamente, una volta raccolti le informazioni relative


65

all‟occupazione di memoria e al trace verrà effettuato il confronto con le informazioni

raccolte durante lo studio precedente sulla Golden copy, in modo tale da valutare in

maniera più approfondita gli effetti dei guasti sul sistema.

4.6 Libreria dei guasti e relativi injector

La libreria dei guasti è composta da un insieme di procedure di injection, ovvero gli

injector che verranno prelevati ed inseriti nel codice sorgente dell‟applicazione durante

l‟esecuzione della stessa.

I guasti prodotti dalle procedure sono stati classificati in base alla locazione dove essi sono

iniettati:

Memoria dati;

Codice;

Registri del processore.

4.6.1 Guasti localizzati nella memoria dati

Per quanto riguarda la memoria, si è pensato di sporcare il valore di una locazione

nell‟area dati statica prima che essa venga letta da un‟istruzione taget, Supponiamo che

l‟istruzione target da iniettare sia una lds, ovvero il caricamento di un valore contenuto

nell‟area dati statica nel registro generale r24, il codice dell‟injector è come segue:

lds r24, 0x0126 ; load diretto dallo spazio dati (istr. target) r24<-(0x0126)

push r16 ; push nello stack

ldi r16,0x20 ; load immediato nel registro r16<-20

eor r24,r16 ; XOR tra registri

sts 0x0126,r24 ; store diretto verso lo spazio dati (0x0126)<-r24

pop r16 ; pop dallo stack

L‟injector sporca il valore letto dalla memoria di un bit. In particolare è effettuato il push

di r16 per non sovrascrivere il valore originale, dato che tale registro viene utilizzato come

maschera per fare la xor col valore letto dalla memoria simulando così il bit-flip del

valore, successivamente verrà memorizzato in memoria il valore sporcato con la store.


66

Un altro caso di fault della memoria, consiste nello sporcare l‟area dati relativa allo stack,

come abbiamo visto nell‟analisi del sistema fault-free l‟area dati è suddivisa in due

porzioni. un esempio della procedura è la seguente:

pop r24 ; pop dallo stack (istruzione target)

push r16 ; push nello stack



pop r16 ; pop dallo stack, ripristino valore precedente del r16

push r24 ; push nello stack del valore sporcato

Tale procedura sostituisce l‟istruzione pop r24, in quanto legge il valore memorizzato

nello stack, da una precedente operazione di push del registro, lo sporca attraverso un xor

col registro r16 di appoggio e inserisce il nuovo valore nello stack.

4.6.2 Guasti localizzati nel codice

Per quanto riguarda l‟iniezione del codice, abbiamo considerato solo guasti relativi agli

operandi evitando di modificare il codice operativo, poiché vi sarà un‟opportuna routine

del processore che gestirà l‟eccezione sollevata. Un possibile injector che implementi un

guasto di tale classe è:

ldi r24, 0xE6 ; load immediato nel registro r24<-E6

push r16 ; push dallo stack




La procedura sporca il valore dell‟operando immediato che è caricato nel registro r24.

Altri possibili injector possono sostituire l‟operando immediato presente nella call, oppure

modificare il nome del registro generale coinvolto nell‟istruzione.

4.6.3 Guasti localizzati nei registri del processore

L‟ultima classe di guasti è rappresentata dalla modifica dei valori presenti nei registri del


67

processore, in particolare i registri generali (R0-R31), il Program Counter (PC), lo Status

Register (sreg) e lo Stack Pointer (SP).

Per i registri generali può essere realizzata un injector come la seguente:

ld r24, Z ; load indiretto tramite registro indice Z r24<-(Z)




st Z,r24 ; store indiretto attraverso registro indice (Z)<-r24


In tale procedura è caricato un valore nel registro generale nel modo indiretto, è sporcato il

2 bit ed infine memorizzato nella locazione di memoria indirizzata da Z.

Per quanto riguarda lo Status Register(SR), sreg nel processore atmega128L, è sufficiente

utilizzare una delle istruzioni disponibili per modificare i flag dello sreg, cioè:

bset k, bclr k che settano rispettivamente ad 1 e a 0 il k-esimo bit dello sreg, oppure sec,

clc, sen, cln, sez, clz, sei, cli, ses, cls, sev, clv, set, clt, seh, clh che settano i flag dello

Status Register.

Per realizzare invece un guasto nel Program Counter basta realizzare un injector che

contenga una semplice istruzione di salto incondizionato, come jmp, rjmp, ijmp, ejmp.

Infine l‟injector relativo all‟iniezione di guasti nello Stack Pointer potrebbe essere:



in r17, SPL ; legge il byte meno significativo dello Stack Pointer



out SPL,r17 ; scrive il valore sporcato dello Stack Pointer



Tale procedura applica il bit-flip al byte meno significativo dello Stack Pointer, ma la

stessa cosa può essere effettuata sulla parte più significativa sostituendo a SPL: SPH.


68

4.7 Procedura per la decisione dell’instante di injection

Una volta individuate le procedure di injection, bisogna stabilire quando esse debbano

essere eseguite, in quanto l‟istruzione target potrebbe essere eseguita più di una volta. Tale

comportamento risulta essere indesiderato poiché i SEU (Single Event Upsets ) sono rari,

e quindi risulta irreale che si verifichino più volte durante una singola esecuzione del

programma.

Lo schema di principio è rappresentato dal seguente diagramma di flusso:

Di seguito sono definite tre procedure di controllo che permettono di eseguire una sola

volta la procedura di injection durante la simulazione, definendo così oltre alla locazione

del guasto anche l‟instante temporale. Tali procedure definiscono la logica del rombo

presente nel diagramma di flusso precedente.

I requisiti richiesti alla procedura di controllo dovrebbero essere:

1. Affidabilità: la procedura deve essere in grado di continuare a funzionare anche in

condizioni di malfunzionamento del sistema, in particolare quando l‟area di

memoria risulta sporcata;

NO

Programma

Principale

mm

Istruzione

Target

Inj?

Blocco

Iniezione

SI


69

2. Flessibilità: la procedura deve dare la possibilità di determinare l‟instante temporale,

il ciclo, in cui iniettare il fault.

La prima procedura è la più semplice ed aggiunge al codice dell‟applicazione un

overhead trascurabile:

push r16 ; salvataggio nello stack del valore del registro r16

in r16,sreg ; lettura dello status register

push r16 ; salvataggio status register nello stack

lds r16,0x0131 ; load del valore memorizzato nella locazione 0x0131

cpi r16,0x55 ; confronto del valore letto con l‟immediato 0x55

breq exit ; salta, se il valore memorizzato è presente nel r16

ldi r16,0x55 ; load immediato 0x55 nel registro r16

sts 0x0131,r16 ; store del valore 0x55 nella memoria

call InjectionProcedure ; invocazione della procedura di injection

exit: pop r16 ; lettura dallo stack del vecchio status register

out sreg,r16 ; ripristino del vecchio valore dello status register

pop r16 ; ripristino del valore iniziale del registro r16

In tale procedura, viene prima salvato il valore dello Status Register evitando così di

alterare il suo valore durante l‟esecuzione della procedura di controllo; successivamente

viene controllato in memoria se l‟injection è stata già effettuata controllando nella

locazione 0x0131, prima locazione libera, nel caso non sia stata effettuata viene scritto il

valore 0x55 e viene richiamata la procedura di injection, altrimenti si va direttamente nel

blocco terminale (etichetta exit) in cui viene ripristinato il valore dello Status Register.

Tale procedura non soddisfa nessuno dei due requisiti descritti precedentemente, quindi

non verrà tenuta in considerazione.

La seconda procedura è più complessa della precedente ed aggiunge dei controlli

aggiuntivi, applicando una forma di ridondanza attraverso un controllo triplice:





70



breq exit ; salta, se il valore immediato è presente nel r16

lds r16,0x0EC1 ; load del valore memorizzato nella locazione 0x0EC1



lds r16,0x0CC1 ; load del valore immediato nella locazione 0x0CC1





sts 0x0CC1,r16 ; store del valore 0x55 nella memoria

sts 0x0EC1,r16 ; store del valore 0x55 nella memoria







viene controllato in memoria se l‟injection è stata già effettuata controllando non solo

nella locazione 0x0131 ma anche in altre due locazioni non contigue, 0x0CC1 e 0x0EC1,

permettendo così di diminuire la probabilità che l‟area di memoria di controllo sia

sporcata, nel caso non sia stata effettuata viene scritto il valore 0x55 nelle tre locazioni e

viene richiamata la procedura di injection, altrimenti si va direttamente nel blocco

terminale (etichetta exit) in cui viene ripristinato il valore dello Status Register.

Tale procedura soddisfa solo il primo requisito dei due descritti precedentemente.

La terza procedura è la più complessa, essa aggiunge un ciclo di controllo che permette di

richiamare la procedura di injection in ciclo diverso dal primo:



71






lds r16,0x0EC1 ; load del valore memorizzato nella locazione 0x0EC1



lds r16,0x0CC1 ; load del valore memorizzato nella locazione 0x0CC1



lds r16,0x0132 ; load del valore di avvenuto init del conteggio


breq Verifica_cont ; salta, se il valore immediato è presente nel r16



ldi r16, NumCicli ; inizializza il contatore specificando il numero di cicli

sts 0x0133,r16 ; store del valore del contatore

jmp exit ;

Verifica_cont: lds r16,0x0133 ; load del valore del contatore

dec r16 ; decrementa il contatore

sts 0x0133,r16 ; aggiorna il valore del contatore

tst r16 ; verifica se il contatore è arrivato a zero

brne exit ; salta, se il valore immediato non è presente nel r16



sts 0x0CC1,r16 ; store del valore 0x55 nella memoria

sts 0x0EC1,r16 ; store del valore 0x55 nella memoria



72






viene controllato in memoria se l‟injection è stata già effettuata controllando non solo

nella locazione 0x0131 ma anche in altre due locazioni non contigue, 0x0CC1 e 0x0EC1,

permettendo così di diminuire la probabilità che l‟area di memoria di controllo sia

sporcata. Vi è inoltre un controllo del ciclo in cui applicare l‟iniezione, in particolare viene

prima verificata l‟avvenuta inizializzazione del contatore dei cicli, nel caso non sia

avvenuta viene inserito il valore del contatore di ciclo nella locazione 0x0133 e si ritorna

al blocco di uscita, altrimenti verrà decrementato il valore del contatore controllando se si

è raggiunto lo zero, in modo da richiamare la procedura di injection.

Tale procedura soddisfa entrambi i requisiti descritti precedentemente, poiché è possibile

specificare il ciclo in cui effettuare l‟injection e per il controllo ridondato di avvenuta

injection, utile per evitare che il valore di avvenuta injection venga modificato durante le

situazioni di malfunzionamento.


73

Capitolo 5

Valutazione della tecnica

5.1 Strumenti di simulazione di reti di sensori senza filo

La simulazione è un importante strumento di ausilio nello sviluppo e collaudo della

componente software delle WSN. Testare nella realtà un‟applicazione, e monitorare il

comportamento della rete per raccoglierne le informazioni desiderate, non sempre è

fattibile. Basti pensare, ad esempio, alle difficoltà di natura pratica che consistono nel

dover programmare le centinaia o migliaia di nodi che costituiscono la rete, dispiegarli nel

reale ambiente di lavoro, tenere traccia dell‟intero traffico di messaggi radio, conoscere i

dati rilevati da ogni sensore, conoscere la durata della batteria e l‟energia consumata da

ogni nodo, conoscere quanti pacchetti sono stati inviati con successo e quanti invece sono

andati persi o sono arrivati a destinazione corrotti.

La simulazione offre un ottimo strumento per la raccolta di informazioni e lo studio del

comportamento della rete, ammesso però che quest‟ultimo venga riprodotto in maniera

fedele e realistica. I normali simulatori di reti di calcolatori spesso si rivelano inadeguati,

perché non interessa studiare soltanto il traffico di rete ma anche aspetti di basso livello

come quelli citati sopra: rilevazione della grandezza fisica da parte del sensore, consumo

energetico, ricetrasmissione dei messaggi via radio con eventuali errori. Ed è proprio

l‟esigenza di esaminare tali aspetti che ha portato alla nascita di simulatori ad hoc, dedicati

specificamente alle reti di sensori wireless.

Di seguito effettueremo una carrellata dei vari ambienti di simulazione per l‟analisi di reti


74

di sensori senza cavo con particolare attenzione rivolta ai simulatori, che permettono di

studiare il comportamento del sensore a basso livello di astrazione, ovvero gli emulatori.

Emstar, insieme a Tossim è stato uno dei primi simulatori esplicitamente progettati per le

reti di sensori senza cavo, questo è framework concepito per studiare due tipi di WSN:

quelle costituite da sensori Microservers con architettura a 32-bit, che fanno uso

tipicamente di sistema operativo Linux, e quelle composte da sensori Mica a 8-bit, che

sfruttano il sistema operativo TinyOS. Emstar consente di studiare l‟esecuzione di

applicazioni di entrambi i tipi secondo varie modalità d‟uso rese disponibili all‟utente; è

chiaro che l‟emulazione sarà richiesta solo per le applicazioni destinate ai sensori Mica,

mentre quelle per i Microservers sono normali applicazioni Linux che non necessitano di

essere emulate. L‟ambiente di simulazione offre anche una serie di servizi utili per creare

applicazioni Linux, come vari algoritmi di routing (tra i quali il Direct Diffusion, che si

occupa di inviare messaggi solo a gruppi di nodi interessati, utile per effettuare query

mirate all‟interno della rete di sensori), un servizio di localizzazione che i sensori possono

adoperare per costruire e mantenere aggiornata in maniera dinamica la topologia della rete

circostante, un servizio di sincronizzazione tempo virtuale/reale indispensabile nelle

simulazioni ibride, ed altri ancora. Purtroppo non viene simulato l‟uso del sensore, né il

consumo energetico, e queste sono delle pecche abbastanza importanti in un emulatore che

si prefigge lo scopo di studiare il funzionamento dei sensori a basso livello.

Tossim è un simulatore ad eventi discreti, con emulazione dei sensori Atmel Mica a 8 bit

con microcontroller AVR, ed è fornito in maniera nativa assieme al sistema operativo

TinyOS. Simula reti di sensori Mica con comportamento omogeneo; il file contenente

l‟applicazione scritta in NesC dev‟essere compilato appositamente per il simulatore,

ottenendo un eseguibile binario diverso da quello che andrà a girare sul sensore. Le

differenze di compilazione riguardano principalmente l‟adattamento del codice ad un

ambiente in cui il programma viene eseguito su di un array di sensori, anziché uno solo.

La simulazione può essere eseguita scegliendo di visualizzare alcuni dei tipi di messaggi

di debug disponibili – stato dei led, contenuto dei pacchetti radio, informazioni sul

consumo energetico, e numerosi altri ancora – oppure utilizzando TinyViz, l‟apposita GUI


75

che permette di seguire l‟andamento della simulazione con molta chiarezza ed in maniera

interattiva: consente di interrompere, riprendere, rallentare, leggere i messaggi di debug,

attivare o disattivare le varie plug-in durante la simulazione.

Tossim ricorre a delle semplificazioni, per ridurre la complessità computazionale

rimanendo ad un basso livello di astrazione. Ogni nodo esegue un task per volta, perché gli

eventi vengono somministrati uno alla volta dallo scheduler, supponendo che ogni evento

richieda poco tempo al singolo sensore per essere consumato e che eventuali interruzioni

hardware possano essere posticipate; questo non accade nella realtà, dove il sistema

operativo TinyOS può consentire interruzioni hardware in alcune occasioni.

I pregi di cui gode Tossim sono numerosi: è facile da utilizzare, permette all‟utente di

seguire la simulazione intervenendo su di essa in tempo reale, è aperto e grandemente

estensibile, le sue funzionalità possono essere ampliate notevolmente scrivendo plug-in

che consentono sia di aumentare la complessità della simulazione, sia di estrapolare dati

da questa, sia di aggiungere nuovi elementi che non erano presenti; inoltre è accurato, in

quanto simula il codice ad un livello molto basso e questo produce risultati precisi su

argomenti come il consumo energetico del sensore. Consente di ottenere molte

informazioni sia sul funzionamento individuale dei sensori, sia sul comportamento

macroscopico della rete.

Atemu è un simulatore del comportamento dell‟intero hardware dei sensori, che usa come

input il binario eseguibile dell‟applicazione. I sensori simulati sono quelli delle famiglie

Atmel e Mica con processore AVR; una delle possibilità più interessanti di Atemu è quella

di poter definire l‟hardware dei sensori su cui eseguire le applicazioni. Il comportamento

della rete può essere più che mai eterogeneo, decidendo sia le applicazioni che

l‟architettura hardware di ciascun nodo o gruppo di nodi della rete, ed indicandone la

posizione in modo da decidere la topologia della rete a piacimento (secondo un semplice

modello 3D). L‟utilizzo di Atemu è soprattutto in ambito di debugging, visto la possibilità

di poter tenere sotto controllo, in ogni step della simulazione, lo stato di ciascun sensore

(valore dei registri interni, uso della memoria, istruzione corrente, messaggi inviati e

ricevuti). Anche in Atemu non esiste alcun modello del consumo energetico dei sensori


76

della rete, e non è prevista nessun meccanismo per l‟analisi dell‟affidabilità.

Avrora è un emulatore scritto in Java che simula il comportamento dell‟intero hardware

dei sensori, eseguendo il codice del programma in linguaggio assemblativo. I sensori

simulati sono quelli delle famiglie Atmel e Mica, dotati di processore AVR. La principale

differenza con Atemu consiste nel fatto che Avrora è un simulatore ad eventi, e non tempo

continuo. Non viene simulato il funzionamento dei sensori quando essi sono in sleep,

saltando direttamente al prossimo evento nella coda d‟attesa di quel sensore che ne

provoca il risveglio ed il funzionamento. A questo si accompagna il fatto che ogni nodo

viene simulato in un thread a parte dal simulatore, il che consente di velocizzare

ulteriormente la simulazione, anche se ciò pone il delicato problema della

sincronizzazione degli eventi che riguardano nodi diversi.

Ns-2, Glomosim e Opnet sono simulatori di rete, adattati o implementati per le WSN.

Sono progettati per simulare specificamente lo strato di rete dello stack di comunicazione.

Ns-2 non supporta in maniera nativa le WSN, ma esistono delle estensioni che forniscono

all‟ambiente di simulazione le capacità di simulare un canale trasmissivo wireless.

Glomosim è stato progettato specificamente per supportare reti wireless e mette a

disposizione un ottimo modello di propagazione radio. Opnet è un simulatore

standardizzato in ambito industriale e commerciale molto simile a ns-2. Opnet viene

fornito con un modulo che simula la propagazione RF e interferenze, ma non supporta in

maniera nativa le WSN.

SensorSim nasce come modulo aggiuntivo per ns-2. Sviluppato dai laboratori di ricerca

UCLA2. SensorSim racchiude alcuni interessanti caratteristiche tra cui un modello

dell‟attività sensoristica, un modello della batteria per il consumo energerico dei nodi, un

leggero stack protocollare appositamente progettato per le WSN e un modulo per la

simulazione che consente l‟interazione attraverso dei reali sensori, per una simulazione

„ibrida’.

J-Sim è un ambiente di simulazione scritto in Java, con front-end in Tcl, sviluppato

prendendo ispirazione da Ns-2 e dalla sua estensione Sensorsim. E‟ realizzato secondo il

paradigma della programmazione a componenti; costituisce un framework per la


77

simulazione di reti di calcolatori in generale, wired e wireless, con in particolare un

supporto dedicato alle WSN ispirato direttamente a Sensorsim; implementa funzionalità in

maniera più completa rispetto a Ns-2, come ad esempio la simulazione ibrida, che può

essere condotta in varie modalità.

Shawn è un simulatore orientato agli algoritmi, che offre all‟utente un ambiente di

supporto in cui può scrivere in linguaggio C++ l‟algoritmo che desidera eseguire su

ciascun nodo della rete. Oltre a decidere l‟algoritmo che andrà in esecuzione sui nodi della

rete in maniera omogenea, si possono stabilire alcune caratteristiche della simulazione,

come il modello topologico (a scelta tra quelli esistenti), la posizione dei nodi, il modello

di trasmissione dei messaggi sui link tra nodi adiacenti.

Algosensim ,alla stregua di Shawn, è un simulatore orientato agli algoritmi. È scritto in

Java e l‟ambiente di simulazione viene configurato mediante la scrittura di file XML. Al

momento è disponibile solo una versione alpha, anche se il framework del simulatore è

stato completamente sviluppato così come buona parte delle classi.

Omnet++, infine, è un simulatore scritto in C++ secondo il paradigma della

programmazione basata sui componenti, che usa il linguaggio Ned per la configurazione

della simulazione. Anche se sul sito ufficiale è dichiarata l‟esistenza di progetti per la

simulazione di reti Internet, anche con elementi wireless, ed eventualmente WSN, per il

momento tali estensioni sono assenti. La struttura del simulatore è sostanzialmente simile

a quella di altri simulatori come Ns-2 e J-Sim. La differenza principale sta nel maggior

livello di astrazione, nel minor numero di funzionalità offerte e nella maggiore semplicità

della simulazione. In Omnet++ non esistono librerie di componenti che implementano

ciascuno strato dello stack protocollare del software di rete; il simulatore è concepito per

una rappresentazione molto più astratta dei nodi della rete, che nella maggior parte dei casi

avviene tramite un unico componente, o un insieme di pochi componenti interni, che si

occupano unicamente di descrivere come il nodo in questione gestisce la ricetrasmissione

di messaggi.


78

5.1.1 Emulatori di reti di sensori senza filo

Gli emulatori sono strumenti in grado di eseguire il codice eseguito dal singolo nodo della

WSN in maniera tale da studiare ad un basso livello di astrazione il comportamento di

ciascun nodo della rete. Inoltre permettono di ottenere risultati più realistici e simulare con

maggiore accuratezza il funzionamento hardware dei sensori. E‟ un‟alternativa all‟impiego

di un modello software più o meno complesso, che si impegna a riprodurre il

comportamento di ciascun singolo nodo ad un livello di astrazione obbligatoriamente più

alto.

Esistono fondamentalmente due approcci possibili all‟emulazione: il primo consiste nel

ricompilare il programma originario, a patto che questo sia disponibile in un linguaggio di

programmazione ad alto livello, ottenendo un nuovo file binario (formato ELF) che sia

eseguibile sul nodo; il secondo consiste nell‟interpretare istruzione per istruzione il codice

del programma in linguaggio macchina o assemblativo.

Il secondo approccio è più potente e portabile del primo, in quanto usa come input

unicamente il file binario originale; i suoi principali svantaggi sono la notevole

complessità computazionale richiesta (interpretare un‟istruzione hardware richiede

l‟esecuzione di un certo numero di istruzioni software), ed il fatto che obbliga ad una

simulazione tempo-continua nella quale vanno eseguite una per volta tutte le istruzioni

dell‟applicazione, non potendo esaminare il programma nel suo complesso e distinguere le

operazioni utili da quelle inutili. Ad esempio, è obbligatorio emulare per intero tutti i cicli

di attesa che verranno eseguiti dall‟applicazione, senza la possibilità di saltare

direttamente all‟evento significativo che interrompe tale ciclo e fa progredire lo stato

complessivo della simulazione. Questo approccio è usato, ad esempio, da Atemu.

Per queste ragioni, alcuni simulatori preferiscono un approccio ad eventi discreti, e la

ricompilazione del programma (che dev‟essere fornito in linguaggio ad alto livello)

consente di effettuare delle ottimizzazioni del codice che riducono la complessità

computazionale, seppur perdendo fedeltà nel riprodurre il programma che si intende

emulare. Un esempio di questo tipo di approccio è Tossim.

Una soluzione intermedia che consente di conservare la fedeltà, e nel contempo


79

guadagnare qualcosa in termini di prestazione, è quella di usare come input il codice in

linguaggio macchina disassemblato. In tal modo è possibile riconoscere i cicli di attesa del

programma, ed il simulatore può evitarne l‟emulazione, ponendo il programma in uno

stato di sleep e schedulando l‟evento successivo. E‟ questo l‟approccio usato da Avrora.

Un‟implicazione dell‟emulazione è che l‟utente dovrà scrivere direttamente il programma

finale, e non una versione astratta degli algoritmi che andrà in seguito riformulata nella

scrittura del programma vero e proprio. Il programma andrà dunque riformulato o meno a

seconda che l‟ambiente di simulazione effettui oppure no l‟emulazione di una particolare

famiglia di sensori wireless.

5.2 Specifica del sistema

Il sistema su cui viene realizzata la campagna di Fault Injection è rappresentato da un

sensore wireless, mica2, che contiene al suo interno un microprocessore AVR

Atmega128L su cui gira il sistema operativo TinyOS tutto ciò viene emulato

dall‟emulatore AVRORA sviluppato dall‟UCLA(University of California, Los Angeles).

L‟applicazione target è Blink, un‟applicazione che genera semplicemente l‟accensione e lo

spegnimento del led rosso del mote, alla frequenza di 1 Hz, tale applicazione è composta

da due componenti: un modulo, chiamato "BlinkM.nc", ed una configurazione, chiamata

"Blink.nc". Il componente di configurazione Blink assembla quattro componenti: Main,

BlinkM, LedsC, TimerC. In particolare il componente LedsC rappresenta l‟interfaccia con

i led, mentre il componente TimerC rappresenta l‟interfaccia col Timer, utilizzata per

contare i millisecondi in modo da sollevare un interruzione qualora passasse un secondo,

richiamando cosi la commutazione del led rosso.

Una volta compilata l‟applicazione Blink, verrà generato dal file eseguibile, formato elf

binario, il file disassemblato “.od” attraverso l‟utility avr-objdump, questo file verrà

utilizzato dall‟emulatore AVRORA.

Per arrestare l‟applicazione, dato che l‟applicazione originale è eseguita senza un criterio

di arresto, utilizzeremo un timeout di 2 secondi in modo tale da verificare l‟accensione e lo

spegnimento del led rosso.


80

5.3 Descrizione del file disassemblato sorgente

Il file è composto da una parte di header che descrive il file ELF binario come è suddiviso

e quali sono le sezioni presenti in esso(data, text, bss, noinit, eeprom, stab e stabstr), dopo

l‟header vi è il listato completo dell‟applicazione(la sezione text), cioè il codice relativo al

sistema operativo TinyOS e l‟applicazione Blink. Il codice prodotto è composto da più di

2700 istruzioni in linguaggio Assembly, tale file è ottenuto dal binario ELF compilato

senza l‟opzione di ottimizzazione, tale scelta è dovuta ad una maggiore comprensione del

listato perdendone però in termini di prestazioni.

Ogni istruzione segue il formato:

Etichetta, indirizzo esadecimale della locazione di memoria in cui è presente

l‟istruzione;

Codice esadecimale, rappresentante l‟istruzione codificata;

Istruzione in linguaggio Assembly, opcode ed operandi;

Commento, dopo il „;‟.

Un esempio:

1612: 81 e0 ldi r24, 0x01 ; load immediato nel registro r24

5.3.1 Analisi della sezione text

La parte text consiste di diverse sezioni, ognuna relativa ad un componente di più alto

livello oppure al compilatore, di seguito daremo una breve descrizione delle più importanti

sezioni:

__vectors: rappresenta il codice relativo alla tabella dei vettori delle interruzioni;

__ctors_end,__do_copy_data, __do_copy_data_loop, __do_copy_data_start,

__do_clear_bss, do_clear_bss_loop, do_clear_bss_start,: rappresentano il codice

relative alla fase di boot, durante la quale vengono caricati i dati dalla memoria

flash alla memoria sram contenente i dati dell‟applicazione in fase di esecuzione.

__nesc_atomic_start, __nesc_atomic_end : rappresentano le procedure che

controllano la mutua esclusione dei task, in cui vengono prima disattivate le


81

interruzioni e poi alla fine vengono riabilitate.

main : è il programma principale in cui avviene la chiamata alle procedure di

inizializzazione dell‟hardware, del kernel e dell‟applicazione infine viene

richiamato lo Scheduler.

Realmain$hardaware$init, Realmain$pot$init: rappresentano le procedure di

inizializzazione dell‟hardware, in particolare la gestione della Potenza del sensore

e dei pin.

TOSH_sched_init: è la procedura di inizializzazione del kernel del tinyOS, in

particolare per lo Scheduler.

RealMain$StdControl$init, RealMain$StdControl$Start: sono le procedure

richiamate dal main che inizializzano l‟applicazione, in particolare

l‟inizializzazione del Timer, utilizzato per commutare il led rosso ogni secondo, e

l‟inizializzazione dei led, che vengono accesi e poi spenti per testarne il

funzionamento.

TOSH_run_task: procedura principale dello Scheduler, in cui viene richiamata la

procedura TOSH_run_next, che schedula il primo task presente nella coda, qualora

non vi fossero dei task da eseguire viene posto il sensore in sleep (low power),

attendendo che venga invocata un interruzione che risvegli il processore.

TOS_post : è la procedura che posiziona il puntatore al task nel primo slot libero

della coda dello Scheduler.

__vector_15 : è la routine che viene richiamata dall‟interruzione, quando il sensore

si sveglia dalla modalità SLEEP.

__nesc_atomic_sleep : è la procedura che pone il sensore nella modalità di

SLEEP(low power).

TOSH_wait : è la procedura che attende che un‟interruzione venga sollevata, dopo

che il sensore si sia riattivato dalla modalità di SLEEP.

5.4 Analisi del sistema fault-free

La normale esecuzione del programma viene effettuata attraverso l‟esecuzione del


82

comando:

avrora blinkNO.od

Che mostra le seguenti informazioni a video:

Loading blinkNO.od...[OK: 0.453 seconds]

=={ Simulation events }=======

Node Time Event

-----------------------------------------

0 12795 Red: on

0 12818 Yellow: on

0 12841 Green: on

0 12864 Red: off

0 12887 Yellow: off

0 12910 Green: off

0 7222030 Red: on

0 14422033 Red: off

========================

Simulated time: 14745600 cycles

Time for simulation: 0.203 seconds

Total throughput: 72.63842 mhz

Utilizzeremo i monitor forniti da AVRORA per studiare al meglio il sistema,

precisamente:

Profile: genera un report testuale della frequenza di esecuzione di ogni istruzione

durante l‟esecuzione del programma.

Calls: genera un report testuale che riporta tutte le sequenze di chiamate a

sottoprogramma e i relativi ritorni, riportando inoltre l‟occorrenza delle routine di

manipolazione degli interrupt.

Trace: visualizza tutte le istruzioni che vengono eseguite durante l‟esecuzione

dell‟intero programma.

Memory: raccoglie informazioni riguardanti statistiche di uso della memoria dati


83

durante l‟esecuzione, includendo il numero di letture e scritture per ogni byte della

memoria dati.

5.4.1 Analisi del codice

Il primo monitor che utilizzeremo è il Trace in modo tale da verificare il flusso di

esecuzione del programma. Il comando da eseguire dal prompt dei comandi di DOS è:

avroraTrace blinkNO.od

Oltre al listato complete delle istruzioni eseguite nel formato: nodo-tempo-evento, vi sono

alcune informazioni riassuntive riguardanti l‟esecuzione dell‟applicazione che riportiamo

di seguito:

Simulated time: 14745600 cycles;

Time for simulation: 0.812 seconds;

Total throughput: 18.159605 mhz;

Instructions executed: 20441;

Program throughput: 0.0013862441 instrs/cycle;

Program throughput: 0.0102205 mips.

La dimensione del file risulta essere di 732KB.

Per analizzare in maniera più chiara il flusso di esecuzione useremo il monitor Calls, esso

ci darà una esaustiva descrizione del flusso di esecuzione. Il monitor viene richiamato

attraverso l‟esecuzione del comando:

avroraCalls blinkNO.od

Oltre a riportare le chiamate a sottoprogramma e i relativi ritorni, riportiamo le

informazioni riassuntive mostrate dal monitor:

Simulated time: 14745600 cycles

Time for simulation: 0.360 seconds

Total throughput: 40.96 mhz

Maximum stack depth: 9 frames

La dimensione del file risulta essere di 170KB.

Il report prodotto da tale monitor mostra con chiarezza il flusso di esecuzione, daremo una


84

rapida descrizione del report.

Le chiamate sono visualizzate nel formato: nodo-tempo-evento.

Nella prima parte del report sono richiamate le procedure di inizializzazione

dell‟hardware, del kernel e dell‟applicazione. Non è mostrata la parte relativa alla fase di

Boot in cui vengono caricati i dati dalla memoria flash alla sram, richiamando le procedure

descritte precedentemente. La procedura di inizializzazione dell‟hardware testa i pin e si

occupa della gestione della potenza, fermandosi quando viene raggiunto il valore di

potenza stabilito. Successivamente vi è l‟inizializzazione del kernel, in particolare dello

Scheduler. Infine vi è l‟inizializzazione dell‟applicazione che testa i led, accendendoli e

spegnendoli tutti, e inizializzando il timer, utilizzato per scandire il tempo.

La seconda parte descrive l‟esecuzione dello Scheduler che esegue un loop, prima estrae

un task dalla coda dei task, poi porta in sleep mode il sensore successivamente dopo un

timeout, un interruzione del timer, si risveglia il sensore e lo Scheduler attende che un

interruzione lo riattivi. In particolare si nota dal report che vi sono due porzioni di codice

che si ripetono. La prima porzione viene invocata la procedura di TOS_post al risveglio

dalla modalità di sleep, che inserisce il puntatore al task nella coda, mentre nella seconda

porzione viene invocato il task in cui viene letto il valore del contatore sempre dopo il

risveglio del sensore, in modo tale da verificare quando il contatore arrivi ad un secondo

ed attivare la commutazione del led rosso.

Infine utilizzeremo il monitor Profile per verificare quali sono i segmenti di codice più

eseguiti durante l‟esecuzione del programma. Il monitor viene attivato mediante il

comando:

avroraProfile blinkNO.od

Ci soffermeremo solo su le porzioni di codice che sono in percentuale maggiori del 5%

dell‟esecuzione totale. Sono state rilevate solo quattro segmenti precisamente:

1. Segmento 0x00CA-0x00F6: 8.2069%;

2. Segmento 0x00F8-0x0128: 9.8697%;

3. Segmento 0x10C0-0x10EE: 16.6492%;

4. Segmento 0x13E8-0x13F8: 7.1996%.


85

Il segmento n°1 rappresenta il codice relativo alla procedura di __nesc_atomic_end,

mentre il segmento n°2 rappresenta la procedura di __nesc_atomic_start, ce lo

aspettavamo visto che la maggior parte delle procedure richiama le due procedure

precedenti per garantire la mutua esclusione delle esecuzioni.

Il terzo e il quarto segmento invece sono relativi alla gestione della potenza, in particolare

la funzione PotM$HPLPot$decrease che richiama la funzione di più basso livello

HPLPotC$Pot$decrease, che riduce il livello del segnale di potenza del sensore;

importante parte di codice in quanto la riduzione del consumo di potenza è tra i principali

obiettivi delle WSN.

5.4.2 Analisi dell’area dati

Il monitor che ci permette di studiare al meglio l‟area dati è il monitor Memory, infatti tale

monitor ci permette di risalire alle locazioni di memoria che vengono utilizzate precisando

il numero di volte che vengono accedute in lettura e scrittura. Tale monitor è richiamato

attraverso il comando:

avroraMemory blinkNO.od

Dal report notiamo che l‟area di memoria utilizzata si divide in due parti, una prima parte

che va dall‟indirizzo 0x0100 all‟indirizzo 0x0130 dove vengono memorizzati i dati

dell‟applicazione mentre nella seconda parte, dall‟indirizzo 0x10C1 all‟indirizzo 0x10FF,

vi è l‟area dove risiede lo stack, lo stack pointer decresce partendo dall‟indirizzo 0x10FF.

Dal monitor inoltre si rileva che gli accessi in memoria in lettura risultano essere 5095

mentre quelli in scrittura 4462, c‟è un leggero bilanciamento.

5.5 Campagna di Fault Injection

La campagna di fault injection realizzata ha lo scopo di sperimentare la metodologia

progettata nel capitolo precedente.

Utilizzeremo l‟emulatore Avrora, preferito rispetto ad Atemu, in quanto, come esposto

precedentemente, comporta una minore complessità computazionale, aumentando le

prestazioni ed evita la simulazione tempo-continua utilizzando quella a tempo-discreta,


86

dato che il nostro primario obiettivo è quello di verificare la metodologia e dare delle

informazioni su cui è possibile fare uno studio successivo più approfondito sulla

dependability. Inoltre Avrora permette l‟utilizzo di monitor, cioè opportuni strumenti di

ausilio alla simulazione, che descrivono in maniera efficace le informazioni sul flusso di

esecuzione, la memoria occupata, il consumo energetico, l‟area stack e i registri del

processore. In secondo luogo tale emulatore è il più utilizzato e conosciuto dalla

community delle WSN, quindi vi sono più studi ed informazioni disponibili che possono

essere di ausilio durante l‟emulazione.

La scelta inoltre di utilizzare l‟emulatore rispetto al sistema reale, possibile attraverso

l‟interfaccia JTAG, è stata fatta in quanto gli strumenti forniti dall‟emulatore permettono

uno studio delle informazioni di trace e di profiling migliore e più veloce in quanto

l‟esecuzione del sensore in real time, rallenta il processo di raccolta dei dati.

Di seguito daremo l‟inquadramento degli esperimenti e le metriche utilizzate durante la

campagna.

L‟inquadramento degli esperimenti è descritto attraverso le seguenti tabelle, che tengono

in conto del tipo di esperimento, il numero di esperimenti e le variabili che sono state

variate.

Il tipo di esperimento, come descritto nel capitolo 4, fa riferimento alla locazione del

guasto da iniettare, cioè:

Memoria

Registri del processore

Codice

Le variabili che sono state variate durante la campagna sono:

1. L‟istruzione, cioè il punto nel listato in cui piazzare l‟injection;

2. Il tempo di iniezione, cioè il ciclo in cui l‟istruzione viene richiamata;

3. Il bit del registro su cui fare il bit-flip;


87

Tipologia Variabile # esperimenti

Memoria locazione 23

bit 80

ciclo 40

Codice locazione 20

bit 80

ciclo 40

Registri locazione 21

bit 80

ciclo 40

Durante la prima parte della campagna è stata variata la locazione dell‟iniezione

mantenendo fissi il bit e il ciclo:

Memoria

# esp Procedura indirizzo ciclo bit Tipo

1 TOS_POST 290 3 6 Dati

2 TOS_POST 272 3 2 Stack

3 NESC_ATOMIC_START F8 3 2 Stack

4 NESC_ATOMIC_START 10C 3 6 Dati

5 NESC_ATOMIC_END F2 3 2 Stack

6 TOSH_RUN_NEXT_TASK 724 3 6 Dati

7 TOSH_RUN_NEXT_TASK 70A 3 2 Stack

8 _VECTOR_15 3C2 3 6 Dati

9 _VECTOR_15 3CA 3 6 dati

10 _VECTOR_15 3DC 3 6 dati

11 _VECTOR_15 3E4 3 6 dati

12 _VECTOR_15 388 3 2 stack

13 _VECTOR_15 38A 3 2 stack

14 POTM$HPLPOT$DECREASE 10CO 3 2 stack

15 TOSH_WAIT 11C4 3 2 stack

16 _NESC_ATOMIC_SLEEP DA6 3 2 stack

17 TOSH_SCHED_INIT 438 1 2 stack

18 REALMAIN$HARDWAREINIT 4A6 1 2 stack

19 TIMERM$CLOCK$FIRE 836 3 6 dati

20 BLINKM$LEDS$REDTOGGLE 1530 1 2 stack

21 NESC_ATOMIC_START FA 3 2 stack

22 NESC_ATOMIC_END CC 3 2 stack

23 _VECTOR_15 3A0 3 2 Stack


88

Codice

# esp Procedura indirizzo ciclo bit

1 TOS_POST 2DA 3 6

2 TOS_POST 2DC 3 6

3 TOS_POST 2F2 3 6

4 TOS_POST 2A4 3 2

5 NESC_ATOMIC_START 100 3 2


7 NESC_ATOMIC_END D2 3 2

8 NESC_ATOMIC_END E6 3 2

9 TOSH_RUN_NEXT_TASK 712 3 2



12 _VECTOR_15 3D6 3 2

13 _VECTOR_15 3FA 3 2

14 POTM$HPLPOT$DECREASE 10C8 3 2

15 POTM$HPLPOT$DECREASE 10DC 3 2

16 POTM$HPLPOT$DECREASE 10DE 3 6

17 TOSH_SCHED_INIT 440 1 2


19 REALMAIN$HARDWAREINIT 4AE 1 2

20 BLINKM$LEDS$REDTOGGLE 1522 2 2

Registri

# esp procedura Indirizzo ciclo Bit

1 TOS_POST 27E 3 8

2 TOS_POST 2A0 3 1



5 NESC_ATOMIC_END D6 3 8



8 _VECTOR_15 3C6 3 2

9 _VECTOR_15 386 3 8

10 POTM$HPLPOT$DECREASE 10CC 3 8

11 TOSH_SCHED_INIT 45E 3 1

12 TOS_POST 27E 3 5


14 NESC_ATOMIC_END CC 3 5

15 TOSH_RUN_NEXT_TASK 71° 3 5

16 _VECTOR_15 392 3 5

17 POTM$HPLPOT$DECREASE 10DA 3 5

18 TOSH_WAIT 11BE 3 5

19 NESC_ATOMIC_SLEEP DAE 3 5

20 REALMAIN$HARDWAREINIT 4B0 1 5


89


Nella seconda parte della campagna abbiamo variato il bit dell‟iniezione come mostrato

nelle seguenti tabelle:

Memoria

# esp procedura indirizzo ciclo bit tipo

1 TOS_POST 290 3 1-8 Dati

2 TOS_POST 272 3 1-8 Stack

3 NESC_ATOMIC_START F8 3 1-8 Stack

4 NESC_ATOMIC_START 10C 3 1-8 Dati

5 NESC_ATOMIC_END F2 3 1-8 Stack

6 TOSH_RUN_NEXT_TASK 724 3 1-8 Dati

7 TOSH_RUN_NEXT_TASK 70A 3 1-8 Stack

8 _VECTOR_15 3C2 3 1-8 Dati

9 POTM$HPLPOT$DECREASE 10CO 3 1-8 Stack

10 TOSH_WAIT 11C4 3 1-8 Stack

Codice

# esp procedura indirizzo ciclo bit

1 TOS_POST 2DA 3 1-8

2 TOS_POST 2DC 3 1-8

3 TOS_POST 2F2 3 1-8

4 TOS_POST 2A4 3 1-8

5 NESC_ATOMIC_START 100 3 1-8


7 NESC_ATOMIC_END D2 3 1-8

8 NESC_ATOMIC_END E6 3 1-8

9 TOSH_RUN_NEXT_TASK 712 3 1-8

10 POTM$HPLPOT$DECREASE 10DC 3 1-8

Registri


1 TOS_POST 27E 3 1-8


3 NESC_ATOMIC_END CC 3 1-8

4 TOSH_RUN_NEXT_TASK 71A 3 1-8

5 _VECTOR_15 392 3 1-8

6 POTM$HPLPOT$DECREASE 10DA 3 1-8

7 TOSH_WAIT 11BE 3 1-8

8 NESC_ATOMIC_SLEEP DAE 3 1-8

9 REALMAIN$HARDWAREINIT 4B0 1 1-8

10 TOSH_SCHED_INIT 464 1 1-8

Nella terza parte della campagna abbiamo variato il ciclo dell‟iniezione come mostrato

nelle seguenti tabelle:


90

Memoria

# esp procedura indirizzo ciclo bit Tipo

1 TOS_POST 290 1-4 6 Dati

2 TOS_POST 272 1-4 2 Stack

3 NESC_ATOMIC_START F8 1-4 2 Stack

4 NESC_ATOMIC_START 10C 1-4 6 Dati

5 NESC_ATOMIC_END F2 1-4 2 Stack

6 TOSH_RUN_NEXT_TASK 724 1-4 6 Dati

7 TOSH_RUN_NEXT_TASK 70A 1-4 2 Stack

8 _VECTOR_15 3C2 1-4 6 Dati

9 POTM$HPLPOT$DECREASE 10CO 1-4 2 Stack

10 TOSH_WAIT 11C4 1-4 2 Stack

Codice


1 TOS_POST 2DA 1-4 6

2 TOS_POST 2DC 1-4 6

3 TOS_POST 2F2 1-4 6

4 TOS_POST 2A4 1-4 2

5 NESC_ATOMIC_START 100 1-4 2


7 NESC_ATOMIC_END D2 1-4 2

8 NESC_ATOMIC_END E6 1-4 2

9 TOSH_RUN_NEXT_TASK 712 1-4 2

10 POTM$HPLPOT$DECREASE 10DC 1-4 2

Registri

# esp procedura Indirizzo ciclo bit

1 TOS_POST 27E 1-4 5


3 NESC_ATOMIC_END CC 1-4 5

4 TOSH_RUN_NEXT_TASK 71° 1-4 5

5 _VECTOR_15 392 1-4 5

6 POTM$HPLPOT$DECREASE 10DA 1-4 5

7 TOSH_WAIT 11BE 1-4 5

8 NESC_ATOMIC_SLEEP DAE 1-4 5

9 REALMAIN$HARDWAREINIT 4B0 1-4 5

10 TOSH_SCHED_INIT 464 1-4 5

Infine le metriche che impiegheremo saranno il numero di istruzioni eseguite durante la

simulazione e la memoria occupata. Inoltre classificheremo gli outcome, ovvero il risultato

osservato, in tre categorie come detto precedentemente cioè:

1. Errori rilevati - Tutti gli errori effettivi che sono segnalati dal meccanismo di


91

rilevamento di errori hardware incluso nel microcontrollore.

2. Output sbagliati - Tutti gli effettivi errori che non sono rilevati dal microcontrollore

che portano a risultati sbagliati.

3. Errori Non Effettivi - Errori che non influenzano l‟esecuzione del sistema durante

l‟intervallo di tempo dell‟esperimento scelto.

5.6 Risultati della campagna

In questo paragrafo sono illustrate le tabelle e i grafici ottenuti attraverso i dati raccolti

durante la campagna e una relativa analisi dell‟informazioni prodotte.

L‟analisi condotta non ha la scopo di fornire dei risultati significativi, ma ha solo

l‟obiettivo di dare delle indicazioni sulle future campagne da condurre e soprattutto a

verificare che gli output prodotti ricomprino tutti i comportamenti previsti dalla

metodologia proposta nel precedente capitolo.

La seguente tabella contiene tutti gli outcome prodotti durante la campagna:

outcome mem-loc mem-bit mem-ciclo cod-loc cod-bit cod-ciclo reg-loc reg-bit reg-ciclo totali cat

os 5 54 12 6 22 19 3 41 11 173

ene 14 11 16 11 33 15 14 26 11 151

er 4 15 12 3 25 6 4 13 15 97

totali 23 80 40 20 80 40 21 80 37 421

Una visione globale degli outcome è data dal seguente grafico:


92

Una visione degli outcome per categoria è mostrata nel successivo grafico:

Dai precedenti grafici si nota che si verificano i tre comportamenti previsti, in particolare

notiamo che i comportamenti sono simili, con un‟attenzione particolare ai guasti iniettati

nella memoria in quanto vi è il 50 % si Output sbagliato, ovvero malfunzionamento del

sistema; ciò potrebbe essere causato sia dalla mancanza di un‟unità di MMU (Memory

Management Unit ) che controlli gli accessi in memoria sia dal fatto che andiamo a

modificare i dati di lavoro dell‟applicazione.

Per quanto riguarda l‟occupazione di memoria la situazione è descritta dal seguente

grafico:


93

Il grafico è stato ottenuto considerando la variazione degli esperimenti (Rosso) che

avevano prodotto un‟occupazione di memoria maggiore rispetto a quella della Golden

copy mentre la seconda variazione degli esperimenti (Blu) che avevano prodotto

un‟occupazione di memoria minore. I valori ottenuti risultano essere contenuti, rispetto

alla dimensione di 4KB della SRAM. Le variazioni superiori possono essere dovute ad un

maggiore riempimento dello stack dovuto ad un numero maggiori di chiamate a procedura

oppure alla mancanza di una unità di MMU che regoli gli accessi alla memoria. Le

variazioni inferiori potrebbero essere causate dalle stesse cause di quelle superiori, solo

con la variante dello stack in quanto potrebbero esserci un numero minore di chiamate a

procedura.


94

Il seguente grafico mostra la variazione del flusso di esecuzione:

L‟alterazione del flusso di esecuzione risulta essere significativa, considerando che il

normale flusso di esecuzione della Golden Copy prevede 20441 istruzioni, infatti si ha una

variazione verso l‟alto e verso il basso del 50% circa; cioè potrebbe essere dovuto a salti

che saltano interi blocchi di codice per la variazione negativa, mentre per quella positiva

potrebbe essere dovuta a richiamare più volte le procedure oppure ad operazioni di reboot

del microcontrollore che rieseguono completamente il codice, modalità con cui vengono

rilevati gli errori.

Di seguito riportiamo i grafici relativi alla seconda parte della campagna, cioè le

informazioni ottenute al variare del bit:


95

Da sottolineare il comportamento dei risultati relativi ai guasti in memoria, si verifica

un‟alta concentrazione di malfunzionamenti soprattutto nei bit più significativi, ciò

supponiamo sia causato dalla radicale modifica della locazione di memoria in cui è

effettuata l‟iniezione.


96

Infine riportiamo i grafici relativi alla seconda parte della campagna, cioè le informazioni

ottenute al variare dell‟istante di iniezione:


97

Notiamo dai precedenti grafici che il comportamento osservato non muta al variare

dell‟instante in cui viene applicata l‟iniezione, quindi possiamo affermare che nelle

successive campagne alterare l‟instate in cui iniettare il guasto può essere messo in

secondo piano rispetto ai risultati ottenibili alterando il bit dell‟iniezione.


98

Conclusioni

Il presente lavoro di tesi nasce dall‟esigenza di valutare la Dependability delle reti di

sensori senza filo, in particolare per le applicazioni critiche in cui i requisiti di affidabilità

risultano indispensabili. Tale lavoro propone uno tecnica software di iniezione dei guasti

su un microcontrollore per reti di sensori ed infine lo valuta per verificare l‟applicabilità.

La scelta di una tecnica di fault injection è stata effettuata dopo un precedente studio delle

possibili tecniche di valutazione della Dependability, ed è stata scelta in quanto permette

di studiare il prototipo del sistema, rappresentando così un giusto compromesso tra la

simulazione del modello e la misura dei dati durante la messa in esercizio del sistema.

La valutazione della tecnica è stata effettuata attraverso l‟emulatore di reti di sensori senza

filo Avrora, la campagna condotta nella fase di valutazione non ha lo scopo di studiare la

Dependability, ma trarre dell‟informazioni basilari per le future applicazioni della tecnica

e soprattutto verificarne l‟applicabilità.

I risultati riscontrati dall‟emulazione sono stati interessanti ed hanno rispettato le

considerazioni fatte durante l‟analisi del sistema, attraverso la tecnica di analisi pre-

injection. In particolare è da sottolineare che l‟occupazione di memoria del sensore

durante i malfunzionamenti non muta di molto, mentre il flusso di esecuzione varia

pressappoco del 50%; Inoltre variare il bit-flip dell‟iniezione è più interessante rispetto a

variare l‟instante in quanto i comportamenti osservati hanno una variabilità maggiore.


99

Sviluppi futuri

Il lavoro di tesi proposto ha come obiettivi definire una tecnica SWIFI su microcontrollori

per reti di sensori e di valutarla; tra i possibili sviluppi futuri possiamo individuare la

sperimentazione di tale tecnica sul sensore reale e l‟introduzione di altri tipi di guasti come

ad esempio gli Stuck-at.

Inoltre sarebbe interessante l‟implementazione di un tool che controlli in maniera

automatica il processo di iniezione e individui i malfunzionamenti una volta verificati nel

sistema.


100

Appendice A

Microcontrollore ATmega128L

A.1 Introduzione

L'ATmega128 è un microcontrollore CMOS a 8-bit basato sull'architettura RISC AVR

della Atmel. La capacità di eseguire le istruzioni in un singolo ciclo consente a questo

dispositivo di raggiungere prestazioni di circa 1 MIPS per MHz, consentendo al progettista

di fissare il tradeoff tra consumo di potenza e velocità di calcolo. Tale dispositivo è dotato

di 32 registri general purpose, tutti connessi in modo diretto alla ALU, così da consentire

l‟accesso simultaneo a due registri e l'esecuzione di istruzioni in un solo ciclo. Le

caratteristiche più importanti sono: 128KB di memoria Flash, 4KB di EEPROM, 4KB di

SRAM, 53 linee di I/O, 2 USART, un ADC ad approssimazioni successive a 10 bit, porte

di comunicazione Two-wire Serial Interface e Serial Peripheral Interface e supporto al

protocollo JTAG sia per il test che per l‟On Chip Debug. Per quanto riguarda il consumo

di potenza il chip dispone di diversi stati operativi per spegnere tutto il dispositivo tranne

l‟oscillatore o il timer asincrono. Infine, un particolare stato è dedicato alla conversione

A/D per limitare al massimo il rumore dovuto alla circuiteria digitale. Sono disponibili 6

porte di I/O ad 8 bit (una delle quali è utilizzata come ingresso per l'ADC) più un'altra

porta a 5 bit, il che fornisce un un totale di 53 pin di I/O disponibili all'utente. Il

microcontrollore utilizza una architettura Harvard dunque con bus e memorie separate per

il codice e i dati ed è inoltre previsto un pipelining a singolo livello così che, mentre

un‟istruzione si trova in esecuzione, quella successiva è già in fase di prefetch, rendendo


101

possibile l‟esecuzione single-cycle delle istruzioni. Il controllo di flusso è consentito dalla

presenza di istruzioni di jump condizionali e non condizionali e istruzioni di call. Una

caratteristica particolare riguarda il fatto che lo stack è allocato all‟interno della memoria

SRAM, in tal modo la sua dimensione è limitata solo dalla quantità di memoria libera,

anche se viene richiesta una maggiore attenzione al programmatore. Il modello esaminato

fornisce diverse possibilità per quanto riguarda il modo in cui viene fornito il segnale di

clock. In particolare, è possibile generare quest'ultimo attraverso un quarzo esterno o

attraverso un oscillatore RC esterno. Si può, in alternativa, scegliere di fornire

direttamente su un apposito piedino il segnale di clock o di sfruttare l‟oscillatore RC

interno in modo da non necessitare di componenti aggiuntivi. I diversi dispositivi presenti

all‟interno del chip non necessitano di avere sempre attivo un segnale di clock al loro

ingresso e si può dunque decidere di disabilitare selettivamente la propagazione del clock

ad alcune periferiche con lo scopo di ridurre i consumi.

Di seguito daremo una breve descrizione degli elementi dell‟Atmega128.

A.2 Regiatri generali

Ci sono 32 registri generali nel microcontrollore. Questi registri sono connessi

direttamente con l‟ALU e sono usati per manipolare dati. I registri sono etichettati R0-

R31.

I registri da R0 a R15 hanno accesso a tutto il range della memoria dati, all‟ALU e alle

periferiche aggiuntive.

I restanti registri, R16-R31, hanno capacità aggiuntive. Essi possono essere utilizzati

nell‟istruzione LDI, che carica un dato immediato, oltre alle funzionalità già indicate dei

precedenti. Essi sono i più usati durante lo sviluppo delle applicazioni.

Inoltre gli ultimi sei registri, R26-R31, hanno un duplice ruolo cioè vengono utilizzati

come puntatori per l‟indirizzamento indiretto. Il microcontrollore ha uno schema di

indirizzamento a 16 bit che necessita di due registri per specificare un solo indirizzo. La

struttura AVR RISC supporta questo schema con i registri X, Y e Z. Questi registri si

ottengono nel seguente modo:


102

A.3 Registri per funzioni speciali

Tali registri controllano o monitorano i differenti componenti del chip. Essi risiedono nella

memoria di I/O dell‟Atmega128 e richiedono le istruzioni IN e OUT per leggere e scrivere

su tali registri. Essi sono lo Status Register (SREG), lo Stack Pointer (SP) e le porte di I/O.

Ci soffermeremo in modo particolare sul SREG e lo SP.

SREG

Tale registro contiene informazioni importanti riguardo l‟ALU quali il bit di Carry, di

Overflow a di Zero. Questi bit vengono modificati durante le istruzioni dell‟ALU. Essi

sono molto utili durante le operazioni di salto. La seguente tabella specifica l‟assegnazione

corretta dei bit nel registro:

Stack Pointer Register

Lo stack è utilizzato principalmente per memorizzare informazioni temporanee, variabili

locali e indirizzi di ritorno dopo chiamate a procedure o a interruzioni. Lo Stack Pointer

Register punta sempre in cima allo stack, da notare che lo stack è implementato ad


103

indirizzi decrescenti, da locazioni di memoria più alte a quelle più basse. Ciò implica che

l‟operazione di PUSH fa decrescere il valore dello SP.

Lo SP dell‟AVR è implementato con due registri, lo Stack Pointer High (SPH) e lo Stack

Pointer Low Register (SPL).

A.4 Vettori d’interruzione

Le interruzioni sono delle funzioni speciali che vengono automaticamente richiamate

quando l‟hardware del microcontrollore le attiva. In generale le interruzioni vengono

abilitate e disabilitate attraverso il settimo bit del SREG, il Global Interrupt Enable. Ci

sono due istruzioni Assembly che abilitano e disabilitano le interruzioni sono

rispettivamente SEI e CLI. Un volta che un interruzione è attivata, il corrente indirizzo è

salvato nello stack e l‟indirizzo del PC salta al vettore delle interruzione associato.

Di seguito viene riportata la tabella delle interruzioni:


104

A.5 Memoria istruzioni

Il microcontrollore contiene un memoria flash da 128Kb per la memoria istruzioni. Dato

che le istruzioni dell‟AVR sono a 16 o 32 bit di ampiezza, la memoria flash è organizzata

a parole di 16 bit (64K x 16). Per la sicurezza del software, lo spazio della memoria

istruzioni flash è diviso in due sezioni, la sezione di Boot Program e la sezione di

Application Program.

La tabella delle costanti può essere allocata dentro l‟intero spazio della memoria istruzioni.

Per accedere a tali costanti oppure ad ogni dato contenuto nella memoria istruzioni si

utilizzano le istruzioni LPM(Load Program Memory) e ELPM (Extended Load Program

Memory).

A.6 Memoria dati

La memoria è rappresentata da una memoria SRAM. Di seguito viene illustrata la

suddivisione della memoria:


105

Il microcontrollore supporta cinque modi di indirizzamento della memoria dati:

1. Diretto;

2. Indiretto;

3. Indiretto con spiazzamento;

4. Indiretto con pre-decremento;

5. Indiretto con post-incremento.

L‟indirizzamento indiretto utilizza i registri X, Y e Z; l‟indirizzamento diretto ricopre tutto

lo spazio della memoria dati.

L‟indirizzamento con spiazzamento raggiunge le 63 locazioni di memoria intorno

all‟indirizzo base dato dai registri X, Y e Z.

Quando si utilizza la modalità di indirizzamento indiretto con l‟automatico post-

incremento e pre-decremento, i registri di indirizzamento X, Y e Z vengono incrementati e

decrementati.

106

Bibliografia

[1] M. Cinque, D. Cotroneo, G. De Caro, and M. Pelella. Reliability requirements of

wireless sensor networks for dynamic structural monitoring. International Conference on

Dependable Systems and Networks (DSN),2006.

[2] C. Perkins, Ad Hoc Networks, Addison-Wesley, Reading, MA, 2000.

[3] I.F.Akyildiz, W.Su, Y.Sankarasubramaniam and E.Cayirci, A Survery on Sensor

Networks, IEEE Communications Magazine, August 2002, pages 102-114, 393-442

[4] A. Y. Wang, S. H. Cho, C. G. Sodini, and A. P. MAC for Asymmetric RF

Microsensor Systems. In Intl. Symp. on Low Power Electronics and Chandrakasan.

Energy Efficient Modulation and Design, August 2001.

[5] C. Schurgers, O. Aberthorne, and M. B. Srivastava. Modulation Scaling for Energy

Aware Communication System In Intl. Symp. on Low Power Electronics and Design,

August 2001.

[6] Wei Ye, John Heidemann, Medium Access Control in Wireless Sensor Networks,

USC/ISI TECHNICAL REPORT ISI-TR-580, October 2003

[7] Brad Karp and H. T. Kung. Gpsr: greedy perimeter stateless routing for wireless

networks. In MobiCom ‟00: Proceedings of the 6th annual international conference on

107

Mobile computing and networking, pages 243–254, New York, NY, USA, 2000. ACM

Press.

[8] Devika Subramanian, Peter Druschel, and Johnny Chen. Ants and reinforcement

learning: A case study in routing in dynamic networks. In IJCAI (2), 1997.

[10] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy - efficient

communication protocol for wireless microsensor networks, Proc. 33rd Hawaii Int'l.

Conf. Sys. Sci.,pp. 3005- 3014, Jan.2000.

[11] Konstantinos Kalpakis, Koustuv Dasgupta and Parag Namjoshi Efficient algorithms

for maximum lifetime data gathering and aggregation in wireless sensor networks ,2002.

[12] Supriyo Chatterjea and Paul Havinga A Dynamic Data Aggregation Scheme for

Wireless Sensor Networks.

[13] R. Nowak. Distributed EM algorithms for density estimation and clustering in

sensor networks. IEEE Trans. on Sig. Proc., 51(8), August 2003.

[14] http://www.alertsystems.org.

[15] A. Cerpa, J. Elson, M. Hamilton, J. Zhao, Habitat monitoring: application driver for

wireless communications technology, ACM SIGCOMM'2000, Costa Rica, April 2001.

[16] http://www.greatduckisland.net/

[17] G. R. Polastre, “Design and Implementation of Wireless Sensor Networks for

Habitat Monitoring ”, Master dissertation, Dept. of Elec. Eng., UCB, Spring 2003.

108

[18] N. Noury, T. Herve, V. Rialle, G. Virone, E. Mercier, G. Morey, A. Moro, T.

Porcheron, Monitoring behavior in home using a smart fall sensor, IEEE-EMBS Special

Topic Conference on Microtechnologies in Medicine and Biology, October 2000, pp.

607-610.

[19] E.M. Petriu, N.D. Georganas, D.C. Petriu, D. Makrakis,V.Z. Groza, Sensor-based

information appliances, IEEE Instrumentation and Measurement Magazine (December

2000) 31-35.

[20] I.A. Essa, Ubiquitous sensing for smart and aware environments, IEEE Personal

Communications (October 2000).

[21] TinyOS: An open source operating system for WSN - www.tinyos.net.

[22] R. Von Behren M. Welsh E. Brewer D. Gay, P. Levis and D. Culler. “The nesC

Language: A Holistic Approach to Networked Embedded Systems”. In Proceedings of

Programming Language Design and Implementation (PLDI) 2003, June 2003.

[23] H. Abrach, J. Carlson, H. Dai, J. Rose, A. Sheth, B. Shucker, and R.Han. MANTIS:

System support for multimodal networks of in-situ sensors. In Proc. 2nd ACM Intl.

Workshop on Wireless Sensor Networks and Applications (WSNA), San Diego, CA,

September 2003.

[24] G. Ananstasi, M. Conti, A. Falchi, E. Fragori e A. Passerella: Performance

Measurements of Mote Sensor networks. ACM/IEEE International Symposium on

Modeling, Analysis and Simulation of Wireless and Mobile System, pp. 174-181, ACM

Press, 2004.

109

[25] D. D. Clark and D. L. Tennenhouse. Architectural Considerations for a New

Generation of Protocols. In Proceedings of SIGCOMM, September 1990.

[26] Philip Levis and Nelson Lee. TOSSIM: A simulator for TinyOS networks,

November 14 2003.

[27] Philip Levis, Nelson Lee, MattWelsh, and David E. Culler. TOSSIM: accurate and

scalable simulation of entire TinyOS applications. In SenSys, pages 126–137, 2003.

[28] Alan Mainwaring, Joseph Polastre, Robert Szewczyk, David Culler, and John

Anderson. Wireless sensor networks for habitat monitoring.

[29] J. Elson, S. Bien, N. Busek, V. Bychkovskiy, A. Cerpa, D. Ganesan, L. Girod, B.

Greenstein, T. Schoellhammer, T. Stathopoulos, D. Estrin, 2003 “Emstar: an environment

for developing wireless embedded systems software”

[30] L. Girod, J. Elson, A. Cerpa, T. Stathopoulos, Nithya Ramanathan, D. Estrin

“Emstar: a software environment for developing and deploying wireless sensor networks”

[31] Jonathan Polley, Dionysys Blazakis, Jonathan McGee, Dan Rusk, John S. Baras

“Atemu: a fine-grained sensor network simulator”.

[32] Ben L. Titzer, Daniel K. Lee, Jens Palsberg “Avrora: scalable sensor network

simulation with precise timing”.

[33] ISI. The network simulator 2 ns-2. http://www.isi.edu/nsnam/nsidenx.html, 2002.

[34] Xiang Zeng, Rajive Bagrodia, and Mario Gerla. Glomosim: A library for parallel

simulation of large-scale wireless networks. In Workshop on Parallel and Distributed

Simulation, pages 154–161, 1998.

110

[35] Y. Huang, J. Huang, L. Hester, A. Allen, O. Andric, P. Chen, and B. O‟Dea. Opnet

simulation of a multi-hop self-organizing wireless sensor network.

[36] A. Savvides S. Park and M. B. Srivastava. Sensorsim: a simulation framework for

sensor networks. In Proceedings of the 3rd ACM international workshop on Modeling,

analysis and simulation of wireless and mobile systems, pages 104–111, Boston, MA

USA.

[37] Ahmed Sobeih, Wei-Peng Chen, Jennifer C. Hou, Lu-Chuan Kung, Ning Li, Hyuk

Lim, Hung-Ying Tyan, Honghai Zhang “J-Sim: a simulation and emulation environment

for wireless sensor networks”

[38] Claudio Basile, Zbigniew Kalbarczyk, and Ravi K. Iyer. Neutralization of errors and

attacks in wireless ad hoc networks. In International Conference on Dependable Systems

and Networks(DSN), 2005.

[39] S. Shakkottai, R. Srikant, and N. Shroff. Unreliable sensor grids: Coverage,

connectivity and diameter. In IEEE INFOCOM2003, pages 241–250, 2003.

[40] D. Bein, V. Jolly, B. Kumar, and S. Latifi. Reliability modeling in wireless sensor

networks. International Journal of Information Technology, Vol. 11 No. 2, 2004.

[41] Hosam M. F. AboElFotoh, S. S. Iyengar, and Krishnendu Chakrabarty. Computing

reliability and message delay for cooperative wireless distributed sensor networks subject

to random failures. IEEE TRANSACTIONS ON RELIABILITY, 54(1), MARCH 2005.

[42] G. Gupta and M. Younis. Fault-tolerant clustering of wireless sensor networks.

IEEE, 2003.

111

[43] Jae-Joon Lee, Bhaskar Krishnamachari, and C.-C. Jay Kuo. Impact of energy

depletion and reliability on wireless sensor network connectivity, 2005.

[44] S. Lindsey and C. S. Raghavendra. PEGASIS: Power-efficient gathering in sensor

information systems. In Proceedings of the IEEE Aerospace Conference, March 2002.

[45] L. Subramanian and R.H. Katz, “An architecture for building self-configurable

systems”, Proceedings of the 1st ACM international symposium on Mobile ad hoc

networking and computing, pp. 63–73, Boston, MA, USA, 2000.

[46] C. V. Ramamoorthy, A. Bhide, and J. Srivastava, “Reliable clustering techniques for

large, mobile packet radio networks”, Proceedings of the 6th Annual Joint Conference of

the IEEE Computer and Communications Societies (INFOCOM ‟87), San Francisco, CA,

USA, 1:218–226, 31 March–2 April 1987.

[47] R. Krishnan and D. Starobinski, Efficient clustering algorithms for self organizing

wireless sensor networks,. Ad Hoc Networks, vol. 4, no. 1, pp. 36.59, January 2006.

[48] Leonidas Tzevelekas, Ziviani Towards Potential-Based Clustering forWireless

Sensor Networks CoNEXT‟05, October 24.27, 2005, Toulouse, France.

[49] Malka Halgamuge, Siddeswara Mayura Guru and Andrew Jennings; Energy

efficient Cluster Formation in wireless sensor networks, International conference on

telecommunications ICT 2003, IEEE Press.

[50] Yuon Guo, Janise Mcnair, Cost Efficient Cluster Formation for wireless sensor

networks, Proc. of CITSA 2004, Orlando, FL, July 2004.

112

[51] Ossama Younis and Sonia Fahmy, HEED: A hybrid energy efficient, distributed

clustering apparoach for Ad-hoc sensor networks, IEEE Transactions on Mobile

Computing, Oct.-Dec. 2004, Volume: 3, Issue: 4, p.p. 366 - 379.

[52] G. Gupta and M. Younis, Load-Balanced Clustering in Wireless Sensor Networks,

IEEE International conference on communications, Anchorage, Alaska, 2003.

[53] S. Banerjee and S. Khuller, A Clustering Scheme for Hierarchical Control in Multi-

hop Wireless Networks, INFOCOM, 2001.

[54] A. Antis, R. Prakash, T. Vuong, and D. Huynh, Max-Min d-Cluster Formation in

Wireless Ad Hoc Networks, IEEE INFOCOM, 2000.

[55] Y. Bejerano, Efficient Integration of Multihop Wireless and Wired Networks with

QoS Constraints, IEEE/ACM Transactions on Networking, 2004.

[56] B. Aoun, R. Boutaba, Clustering in WSN with latency and Energy Consumption

constraints, Journal of Network and Systems Management, Vol. 14, No. 3, September

2006

[57] Mudasser Iqbal, Iqbal Gondal and Laurence Dooley An Energy-Aware Dynamic

Clustering Algorithm for Load Balancing in Wireless Sensor Networks JOURNAL OF

COMMUNICATIONS, VOL. 1, NO. 3, JUNE 2006

[58] A. Kroller, D. Pfisterer, C. Buschmann, S.P. Fekete, S. Fischer, “Shawn: A new

approach to simulating wireless sensor networks”, 2005

[59] http://tcs.unige.ch/doku.php/code/algosensim/overview

113

[60] C. Mallanda, A. Suri, V. Kunchakarra, S.S. Iyengar, “Simulating wireless sensor

networks with Omnet++”, 2005

[61] Fred Stann and John Heidemann. RMST: Reliable Data Transport in Sensor

Networks. 1st IEEE International Workshop on Sensor Net Protocols and Applications,

2003

[62] C. Wan, A. Campbell, L. Krishnahmurthy. PSFQ: A Reliable Transport Mechanism

for Wireless Sensor Networks. ACM International Workshop on Wireless Sensor

Networks and Applications, Atlanta, Georgia, Sept 2002.

[63] C. Intanagonwiwat, R. Govindan, D. Estrin, j. Heidmann and F. Silva “Direct

Diffusion for wireless sensor network” IEEE/ACM Transactions on Networking, vol.11,

pp 2-16, Feb 2003

[64] Seung-Jong Park, Ramanuja Vedantham, Raghupathy Sivakumar and Ian F.

Akyildiz A scalable approach for reliable downstream data delivery in wireless sensor

networks in the Proceedings of ACM International Symposium on Mobile Ad hoc

Networking and Computing (MOBIHOC), Japan, May 2004.

[65] Chieh-Yih Wan, Shane B. Eisenman, Andrew T. Campbell, “CODA: Congestion

Detection and Avoidance in Sensor Networks”, in proceedings of First ACM Conference

on Embedded Networked Sensor Systems (SenSys 2003), November 2003.

[66] J.O‟Rourke. Computational geometry column 15. Int‟l Journal of Computational

Geometry and Application, 2(2):217-217,1992.

[67] Seapahn Meguerdichian, Farinaz Koushanfar, Miodrag Potkonjak, Mani B.

114

Srivastava, Coverage Problems in Wireless Ad-hoc Sensor Networks, in IEEE

INFOCOM, pages 1380-1387, 2001

[68] S. Slijepcevic, M. Potkonjak, Power Efficient Organization of Wireless Sensor

Networks, In IEEE Int‟l Conf. on Communications (ICC) pages 472-476, 2001.

[69] Tian, Georganas, A Coverage-Preserving Node Scheduling Scheme for Large

Wireless Sensor Networks ACM Int‟l Workshop on WSNA, 2002

[70] Catello Di Martino, Valutazione dell'affidabilità di Reti di Sensori senza cavo,

Università degli studio di Napoli Federico II, Ottobre 2005

[71] Fan Ye, Gary Zhong, Jesse Cheng, Songwu Lu, Lixia Zhang PEAS: A Robust

Energy Conserving Protocol for Long-lived SensorNetworks, In Int‟l Conf. on Distributed

Conputing System (ICDCS), 2003

Facoltà di Ingegneria - unina.it

Documents

Transcript of Facoltà di Ingegneria - unina.it