Un modello markoviano per lo studio dell'evoluzione in transitorio di una rete di sensori

 2
Per esempio il numero di nodi è molto più elevato e i sensori sono inesorabilmente soggetti 
ad esaurimento energetico, dato che le loro batterie in genere non possono essere ricaricate. 
Per questi ed altri motivi occorre definire una architettura protocollare specifica, in cui ad 
ogni livello si tenga conto dell’esigenza fondamentale di una rete di sensori: risparmiare 
energia e prolungarne la vita. Il traguardo della ricerca è quello di trovare soluzioni che 
rendano fattibile lo sviluppo di progetti che oltrepassino i limiti delle tradizionali 
applicazioni che fanno uso di sensori.  
In [1] gli autori descrivono lo stato dell’arte delle reti di sensori, soffermandosi su alcune 
possibili applicazioni, delle quali alcune già in fase di sperimentazione. Inoltre definiscono 
i fattori che influenzano il progetto di questo tipo di rete e riassumono alcune soluzioni 
protocollari. In [2] gli autori si dedicano alla descrizione dettagliata di molti protocolli di 
routing, classificandoli in categorie e confrontandoli sulla base dei parametri che 
interessano maggiormente questo settore. Infatti le classiche tecniche di routing, come il 
flooding, sono totalmente inefficienti per una rete di sensori, come dimostrato in [3]. 
Anche a livello di MAC i protocolli utilizzati nelle reti ad hoc, come MACA [4] e 
MACAW [5], non tengono conto di alcune problematiche presenti nelle reti di sensori. In 
[6] è presente una panoramica sulle diverse soluzioni che la ricerca ha proposto a questo 
livello dell’architettura mentre in [7] gli autori confrontano i protocolli di MAC che 
sembrano più adatti a trattare l’accesso al mezzo trasmissivo.  
Allo stato attuale è molto difficile definire una metodologia di progetto affidabile che tenga 
presente le diverse problematiche di una rete di sensori; il lavoro in [8] è un tentativo in tal 
senso. Gli autori individuano un insieme di caratteristiche generali per questo tipo di rete e 
le utilizzano per assegnare un punteggio di merito ai possibili protocolli di comunicazione, 
al fine di scegliere quelli più convenienti.  
Per studiare una rete di sensori si possono seguire due diversi approcci: quello simulativo e 
quello basato sulla definizione di modelli analitici. Nel primo caso occorre uno strumento 
 3
che implementi le modalità di funzionamento che si vogliono analizzare e i risultati devono 
essere sottoposti ad analisi di errore. Nel secondo caso è invece richiesto un maggiore 
sforzo di astrazione per modellare l’oggetto dell’analisi ma permette normalmente di avere 
risultati in tempi più brevi. Questo lavoro di tesi parte dalla discussione di un modello 
analitico, per cui ci sembra opportuno riassumere brevemente altri lavori simili. In [9] gli 
autori introducono due aspetti critici di una rete di sensori: la copertura e la connettività. 
Dopo aver definito un modello statistico del comportamento di un  sensore, formulano un 
problema di ottimizzazione che fornisce i valori dei parametri in grado di minimizzare il 
consumo energetico, fissate le percentuali richieste di copertura e connettività. Un lavoro 
simile è in [10], in cui vengono individuate le relazioni che legano il raggio di trasmissione 
del sensore, il diametro della rete e la probabilità che il sensore sia funzionante per 
assicurare la copertura e la connettività in una rete di sensori con topologia a griglia. In 
[11] gli autori definiscono un modello statistico dell’interferenza tra sensori e della 
connettività della rete. Esaminano quindi la relazione tra queste due grandezze per 
differenti tipi di topologia. In [12] viene presentato un modello probabilistico per 
determinare la distribuzione di energia in una rete di sensori (mappa energetica); gli autori 
lo considerano un punto di partenza per massimizzare la vita della rete. In [13] l’attenzione 
è rivolta al routing. Gli autori definiscono la vita del sensore e della rete, quindi ricavano 
un problema di programmazione lineare la cui soluzione è data dal flusso di pacchetti che 
massimizza la vita della rete. Un altro aspetto critico di una rete di sensori è la necessità di 
individuare dei punti di aggregazione ottimali. Infatti è frequente la situazione in cui 
diversi sensori rilevano le stesse informazioni perché coprono aree sovrapposte. Ciò 
determina la generazione di informazioni ridondanti che sprecano le risorse energetiche 
della rete. Per questo motivo i protocolli di routing prevedono che alcuni sensori 
aggreghino i dati ricevuti da altri dispositivi, inviando solo le informazioni necessarie. In 
[14] gli autori propongono degli algoritmi per individuare i punti di aggregazione che 
 4
massimizzano la vita della rete. Oltre all’algoritmo che fornisce la soluzione esatta 
presentano soluzioni alternative, approssimate ma più efficienti dal punto di vista 
computazionale. Un ambito che risulta ancora poco esplorato riguarda lo sviluppo di 
tecniche compatibili con le risorse dei sensori per eseguire la correzione degli errori sul 
canale. A tal proposito in [15] si trova un modello analitico di un protocollo derivato 
dall’ARQ che tiene conto delle esigenze di una rete a ridotta disponibilità energetica. 
Tuttavia tale soluzione sembra ancora poco efficiente per le reti di sensori, come 
sottolineato in [1]. Infine in [16] è descritto un modello probabilistico, basato sul 
formalismo delle catene di Markov, che ha l’obiettivo di dimensionare i parametri che 
regolano le dinamiche di accensione e spegnimento dei sensori. Tali dinamiche si 
riferiscono all’opinione comune dei ricercatori secondo cui, al fine di salvaguardare le 
risorse energetiche, i sensori devono essere tenuti per più tempo possibile in uno stato a 
minimo consumo energetico. Questo stato, detto di sleep, è caratterizzato dal fatto che il 
sensore non è in grado di comunicare con gli altri dispositivi, per cui risulta disconnesso 
dalla rete fino a che non ritorna nello stato di piena funzionalità, detto di active.  
Occorre pertanto individuare le durate dei tempi di permanenza nei due stati sulla base del 
compromesso tra durata della rete e garanzia di qualità di servizio. Un lavoro simile a 
quello in [16] si trova in [17], in cui viene utilizzato un approccio fluidico.  
L’obiettivo della tesi è stato quello di definire un modello analitico in grado di analizzare 
l’evoluzione delle prestazioni di una rete di sensori, sino al completo esaurimento delle sue 
risorse energetiche. A tal fine abbiamo preso spunto dal lavoro in [16] e apportato i 
contributi necessari per permette lo studio del transitorio, in contrapposizione all’analisi a 
regime svolta dagli autori.  
La tesi è strutturata come segue: il cap. II descrive le principali problematiche riguardanti 
le reti di sensori, con attenzione particolare ai protocolli di routing e di accesso al canale; il 
cap. III mostra in dettaglio il funzionamento del modello di partenza; il cap. IV esamina le 
 5
tecniche risolutive da noi scelte per rendere concretamente utilizzabile il modello; il cap. V 
presenta lo strumento analitico definitivo per lo studio del transitorio e i risultati ottenuti; il 
cap. VI  conclude la tesi. 
L’ambiente di sviluppo utilizzato è MATLAB; le funzioni che implementano il modello si 
trovano in appendice. 
Nel seguito, con riferimento alla terminologia tipicamente utilizzata nelle reti di 
telecomunicazione, i termini nodo e sensore saranno usati indistintamente. 
 
 6
CAPITOLO II 
LE RETI DI SENSORI 
 
 
2.1 Premessa 
I recenti sviluppi tecnologici nel campo della microelettronica, dell’elettromeccanica e dei 
sistemi di comunicazione wireless hanno permesso la realizzazione di sensori di piccola 
dimensione, a basso costo e a bassa potenza, in grado di comunicare entro brevi distanze. 
Questi dispositivi svolgono tre funzioni principali: la rilevazione di grandezze fisiche, 
meglio nota come funzione di sensing, l’elaborazione di informazioni e la comunicazione 
di dati.  
Sebbene ogni singolo sensore possa svolgere autonomamente questi compiti, si parla di 
rete di sensori quando un gran numero di dispositivi è organizzato per raggiungere un 
obiettivo comune. 
I sensori vengono sparsi a diretto contatto o in prossimità del fenomeno fisico da studiare, 
in posizioni che generalmente non è possibile determinare a priori; se da un lato ciò 
permette alla rete di avere un elevato grado di adattamento dall’altro richiede che i 
protocolli di comunicazione supportino tecniche di auto-organizzazione dei nodi. 
Una rete di sensori può essere vista come caso particolare di rete ad hoc, sebbene possieda 
delle caratteristiche peculiari che impediscono di utilizzare i vari protocolli proposti per 
questo tipo di reti.  
Tali caratteristiche sono: 
 ξ  l’ elevato numero di nodi (dell’ordine delle centinaia, delle migliaia o anche più) e 
la grande densità che ne deriva 
 ξ  l’ elevata probabilità di insuccesso del singolo sensore 
 7
 ξ  la frequente variazione di topologia della rete 
 ξ  la scarsa disponibilità di energia, di capacità computazionale e di memoria dei nodi 
 ξ  l’impossibilità di assegnare ad ogni nodo un identificativo globale perchè ciò 
comporterebbe un overhead troppo elevato 
 
Per questi ed altri motivi il progetto efficiente di una rete del genere richiede 
un’architettura protocollare specifica.  
Il fattore più limitante in una rete di sensori è di certo la ridotta potenza utilizzabile, dato 
che ogni sensore dispone di una batteria generalmente non ricaricabile né sostituibile viste 
le condizioni ambientali in cui agisce il dispositivo. Soluzioni tecnologiche che prevedono 
la possibilità di recuperare energia dall’ambiente circostante, per esempio mediante celle 
solari, sono ancora poco fattibili. Per questo motivo i protocolli specifici per le reti di 
sensori, a differenza di quelli normalmente usati nelle reti ad hoc, tendono a preservare il 
consumo energetico piuttosto che garantire un’alta qualità di servizio, intesa questa come 
rapporto capacità / ritardo. Si dice pertanto che tali protocolli sono power-aware 
(consapevoli della necessità di risparmiare energia). 
 
 8
2.2 Applicazioni delle reti di sensori 
Un sensore è  in grado di rilevare innumerevoli grandezze tra cui: 
 ξ  temperatura 
 ξ  umidità 
 ξ  spostamento di veicoli 
 ξ  pressione 
 ξ  condizioni del terreno e dell’atmosfera 
 ξ  livello di rumore 
 ξ  presenza o assenza di oggetto 
Di seguito presentiamo alcuni possibili scenari in cui risulta vantaggioso l’utilizzo di una 
rete di sensori.  
 
2.2.1 Applicazioni militari 
Una rete di sensori può diventare parte integrante del sistema militare C4ISRT (command, 
control, communications, computing, intelligence, surveillance, reconaissance, targeting).  
In particolare essa permette di: 
 ξ  monitorare gli equipaggiamenti di un commando militare attaccando sensori  alle 
divise dei soldati, ai veicoli e alle armi  
 ξ  sorvegliare il campo di battaglia  
 ξ  riconoscere la presenza di forze nemiche  
 ξ  accertare i danni subiti in battaglia 
 ξ  rilevare attacchi di natura chimica, biologica o nucleare 
Tutto ciò permette di effettuare operazioni militari riducendo il rischio di perdite umane e 
di sorvegliare territori altrimenti inaccessibili. Inoltre l’alta probabilità di distruzione dei 
dispositivi non preclude, entro certi margini di tolleranza, l’adempimento del compito della 
rete. 
 9
2.2.2 Applicazioni ambientali 
Una rete di sensori è in grado di: 
 ξ  tracciare gli spostamenti degli animali 
 ξ  monitorare il livello di pesticidi nell’acqua potabile e quello dell’inquinamento 
atmosferico 
 ξ  rilevare lo scoppio di un incendio prima che diventi incontrollabile 
 ξ  esaminare la bio-complessità di un territorio con elevata risoluzione spaziale, 
spettrale e temporale e con un ragionevole costo per unità di superficie (un 
esempio di questa applicazione si trova nella James Reserve in California) 
 ξ  avvertire il rischio di alluvione e misurare il tasso di pioggia 
 
2.2.3 Applicazioni mediche 
Con una rete di sensori è possibile: 
 ξ  monitorare i dati fisiologici dei pazienti  
 ξ  localizzare medici e pazienti e rilevare eventi come ad esempio una caduta  
 ξ  amministrare i farmaci disponibili riducendo il rischio di effettuare cure errate 
Il progetto “Health Smart Home” è stato realizzato nella Facoltà di Medicina di Grenoble 
in Francia per testare applicazioni di questo tipo. 
 
2.2.4 Applicazioni domestiche 
Lo sviluppo di un ambiente domestico automatizzato e facile da controllare sia localmente 
che in remoto richiede l’inserimento, in ogni elettrodomestico, di sensori che permettano 
l’interazione dei vari apparati. Un progetto del genere può essere visto secondo due 
prospettive: umana e tecnologica. Da un lato deve fornire interfacce input/output per 
l’utente finale e dall’altro proporre  soluzioni vantaggiose a livello di rete e hardware. Un 
 10
esempio di questi ambienti, noti come smart environments, è il “Residential Laboratory” 
presso il Georgia Institute of Technology. 
 
2.2.5 Applicazioni commerciali 
Una rete di sensori è in grado di migliorare l’efficienza del sistema di condizionamento 
dell’aria negli edifici. Un controllo di questo tipo è generalmente realizzato in modo 
centralizzato per cui il flusso di aria non è uniformemente distribuito nella varie parti di 
una stanza e si verificano pertanto variazioni di qualche grado nella temperatura 
dell’ambiente. Uno studio ha dimostrato come una soluzione distribuita permetterebbe 
enormi riduzioni nel consumo di energia e nell’ emissione di carbonio. 
Altre possibili applicazioni commerciali riguardano l’opportunità di: 
 ξ  permettere ai visitatori di un museo di interagire con degli oggetti che reagiscono a 
stimoli vocali o tattili e di partecipare ad esperimenti di causa-effetto (un esempio 
di trova presso il San Francisco Exploratorium) 
 ξ  rilevare furti d’auto entro una certa regione geografica 
 ξ  monitorare le categorie e le quantità di articoli presenti in un grande magazzino 
 
 11
2.3 Fattori che influenzano il progetto di una rete di sensori 
Di seguito presentiamo le linee-guida generalmente seguite nel progettare un algoritmo o 
un protocollo per una rete di sensori, utili anche per confrontare le diverse soluzioni 
proposte. 
 
2.3.1 Affidabilità 
Per affidabilità si intende la capacità della rete di sostenere le sue funzionalità senza 
interruzioni causate dall’insuccesso del singolo sensore. Le principali cause che rendono 
inutilizzabile un nodo sono l’esaurimento dell’energia disponibile e i danni fisici subiti 
nell’ambiente operativo.  
L’affidabilità del singolo sensore può essere modellata mediante una distribuzione 
Poissoniana nel seguente modo: 
t
k
k
etR
 Ο  
  )(
 
dove )(tR
k
 è la probabilità che il sensore non diventi inutilizzabile nell’intervallo (0,t) e λ
k
 
è la frequenza di insuccesso del nodo. 
Il livello di affidabilità richiesta alla rete dipende dall’ambiente in cui essa opera per cui, in 
base all’applicazione, si useranno i protocolli che danno garanzie più o meno elevate da 
questo punto di vista. 
 
2.3.2. Scalabilità 
Per scalabilità si intende la capacità della rete di garantire certe prestazioni 
indipendentemente dal numero di nodi da cui è composta. Quando si analizza questo 
parametro è più corretto fare riferimento alla densità di sensori, definita come: 
A
RN
R
2
)(
 Σ
 Π    
dove N è il numero di nodi, R il raggio di trasmissione e A la superficie in cui opera la rete. 
 12
 
2.3.3 Costi di produzione 
Visto che una rete di sensori è composta da un grande numero di nodi è fondamentale che 
il costo di produzione di ciascuno di essi sia molto ridotto, affinché la realizzazione della 
rete sia economicamente giustificabile. Il confronto deve essere fatto con le soluzioni 
tradizionali in cui i sensori non hanno un approccio collaborativo. 
Attualmente si richiede che ogni sensore costi meno di 1 $. 
 
2.3.4 Limiti hardware 
La figura seguente mostra i componenti hardware di un tipico sensore. 
 
I componenti di base (in linea continua) sono: 
 ξ  l’ unità di sensing composta dal sensore vero e proprio e dal convertitore analogico-
digitale 
 ξ  l’ unità di processamento che include una piccola memoria 
 ξ  il transricevitore per la comunicazione con gli altri nodi 
 ξ  la batteria che fornisce energia a tutti i blocchi 
 13
A seconda dell’applicazione sono presenti dei componenti opzionali (in tratteggio): 
 ξ  l’unità di ricarica della batteria (per esempio celle solari)  
 ξ  l’unità di spostamento del sensore 
 ξ  l’unità di localizzazione (per esempio un terminale GPS)  
Tali componenti sono fisicamente racchiusi dentro una scatola che dovrebbe avere un 
volume dell’ordine del centimetro cubico, così leggera da poter rimanere sospesa in aria. 
L’energia disponibile per ciascun sensore a carica completa è in genere dell’ordine di 1 J. 
 
2.3.5 Topologia della rete 
La topologia di una rete di sensori subisce frequenti cambiamenti dovuti al 
danneggiamento e all’esaurimento energetico dei nodi. Inoltre, pur considerando solo i 
nodi funzionanti, la topologia varia  perché in ogni istante un certo numero di nodi sono 
tenuti in uno stato di sleep. Si tratta di una modalità di funzionamento che permette al 
sensore di risparmiare notevoli quantità di energia rendendolo tuttavia disconnesso dalla 
rete visto che il transricevitore non è attivo. E’ chiaro che al diminuire dei nodi attivi si 
riducono la capacità, la copertura e la connettività della rete. L’analisi del compromesso tra 
questi parametri e il risparmio energetico in letteratura è nota col nome di topology 
management o topology maintenance. 
 
Tralasciando le dinamiche di accensione e spegnimento dei nodi, che verranno analizzate 
in seguito, l’ evoluzione della topologia di una rete si può racchiudere in tre fasi: 
 
 ξ  schieramento, in cui i sensori sono inizialmente distribuiti nell’ambiente 
generalmente in maniera casuale, sebbene siano possibili tecniche di 
posizionamento che riducano le interferenze o promuovano l’auto-organizzazione 
della rete 
 14
 ξ  post-schieramento, in cui la topologia muta a causa dello spostamento, della 
distruzione o dell’esaurimento di energia dei sensori 
 ξ  ri-schieramento, in cui nuovi sensori vengono distribuiti sul campo per sostituire 
quelli non più funzionanti 
 
2.3.6 Ambiente operativo 
Una rete di sensori può operare in una moltitudine di ambienti eterogenei tra cui: 
 ξ  l’interno di un grande macchinario 
 ξ  il fondo di un oceano 
 ξ  un luogo biologicamente o chimicamente contaminato 
 ξ  il nucleo di un tornado 
 ξ  un campo di battaglia 
 ξ  un grande edificio o un grande magazzino 
 ξ  il corpo di un animale 
 ξ  un fiume o una cascata 
 ξ  la carrozzeria di un veicolo 
Lo scenario applicativo può richiedere soluzioni protocollari differenti da quelle 
comunemente impiegate nelle reti di sensori. 
 
 15
2.3.7 Mezzo trasmissivo 
Il mezzo usato per la comunicazione tra i nodi della rete può essere di tre tipi: 
 ξ  radio 
 ξ  ottico 
 ξ  infrarosso 
 
Nel primo caso risulta favorevole l’utilizzo della banda per le applicazioni industriali, 
mediche e scientifiche (banda ISM). Tale scelta ha il vantaggio di non richiedere licenze 
per l’utilizzo delle frequenze e di non avere standard che possano limitare la ricerca di 
soluzioni che minimizzino il consumo energetico. 
 
Di seguito sono elencate le frequenze della banda ISM. 
 
 
Tenendo conto dei limiti hardware e del compromesso tra efficienza delle antenne e 
consumo energetico, la scelta effettiva ricade nel range UHF (ultra high frequency). In 
particolare è consigliata la portante a 433 MHz per l’Europa e quella a 915 MHz per il 
Nord America.