Analisi sperimentale di algoritmi di sincronizzazione per reti di sensori wireless basati su regressione lineare

Introduzione 
 
 
II 
 
 
 
Introduzione 
 
 
 
 
Le reti di sensori wireless (WSN, acronimo di Wireless Sensor Network) 
rappresentano la migliore soluzione dinamica a basso costo degli ultimi anni per tutte 
quelle applicazioni in cui le reti wired risultano una scelta impraticabile o inefficiente: si 
pensi ad esempio al controllo di ambienti ostili o fisicamente inaccessibili, oppure al 
monitoraggio dei parametri vitali di un paziente all’interno di un ospedale e alla 
domotica. Per ottenere un risultato significativo, tuttavia, non è sufficiente che i singoli 
nodi sensore di una rete acquisiscano dati utili, ma è necessario che il set di 
informazioni raccolte da ogni dispositivo venga combinato con gli altri mediante 
un’operazione di fusione dati. Tale fusione è possibile solo grazie ad un coordinamento 
tra i nodi della rete e, di conseguenza, ad una correlazione fra i dati nel dominio del 
tempo. Come in tutti i sistemi distribuiti, quindi, la sincronizzazione temporale è una 
componente fondamentale nelle reti di sensori wireless, ed impone che tutti i dispositivi 
appartenenti alla rete condividano il medesimo riferimento temporale. A causa delle 
peculiari limitazioni in termini di energia, memoria, capacità computazionale e banda di 
trasmissione di queste reti, tuttavia, gli schemi di sincronizzazione tradizionali non 
risultano adatti all’impiego nelle WSN; questo ha attirato l’interesse di numerosi 
ricercatori a sviluppare nuovi protocolli di sincronizzazione. 
Una classe di protocolli che sta assumendo un’importanza crescente nel panorama 
della sincronizzazione nelle WSN è quella basata sulla regressione lineare. Il più 
semplice di questa categoria di protocolli è il Flooding Time Synchronization Protocol 
(FTSP). La sua progettazione è nata con l’obiettivo di raggiungere la sincronizzazione 
temporale di un’intera rete di nodi sensore con errori dell’ordine del µs e scalabilità fino 
a centinaia di nodi, insieme con la robustezza ai cambiamenti di topologia della rete ed
Introduzione 
 
 
III 
 
ai guasti di collegamenti e nodi. L’algoritmo raggiunge un’elevata precisione grazie al 
timestamping a livello MAC e la compensazione del drift tra i clock e della variabilità 
della comunicazione mediante la regressione lineare. 
Sebbene esso sia stato già trattato in numerosi lavori scientifici, attualmente in 
letteratura non esistono studi che ne abbiano valutato le prestazioni in maniera 
sistematica. L’assenza di un approccio di questo tipo ha motivato e stimolato il presente 
lavoro, che si propone da una parte di effettuare una caratterizzazione sperimentale delle 
prestazioni intrinseche dell’algoritmo mediante un setup di misura che consenta di 
controllare i fenomeni di maggiore influenza come il drift tra i clock e la latenza di 
comunicazione ed abbia una precisione adeguata alle misure da effettuare, dall’altra di 
proporre un’ottimizzazione dell’algoritmo in termini di tempo di risincronizzazione e 
consumo energetico. 
Nel primo capitolo vengono descritte le motivazioni che giustificano la necessità di 
una sincronizzazione temporale nelle reti di sensori wireless, le problematiche tipiche di 
questa tipologia di reti ed i principi di progettazione dei protocolli di sincronizzazione, i 
quali devono rispondere alla richiesta di minimizzazione del consumo di risorse da parte 
dei dispositivi di una WSN. 
Nel secondo capitolo viene descritto il protocollo FTSP così come è stato ideato 
dagli autori, insieme con un sintetico confronto con altri protocolli di sincronizzazione 
sviluppati tenendo conto delle particolari esigenze delle reti di sensori. 
Nel terzo capitolo viene descritta la stazione di misura realizzata per effettuare le 
prove sperimentali volte a valutare le prestazioni dell’algoritmo nelle diverse 
implementazioni proposte, nonché forniti i dettagli circa la scelta della strumentazione e 
la modalità di valutazione delle prestazioni dell’algoritmo. 
Nel quarto capitolo vengono presentate le prove sperimentali eseguite per 
caratterizzare le prestazioni dell’algoritmo in diverse condizioni di drift e di latenza di 
comunicazione. 
Nel quinto capitolo, infine, è stata presentata un’ottimizzazione dell’algoritmo ed è 
stato effettuato il confronto tra le sue due implementazioni, il quale ha dimostrato che 
l’implementazione proposta garantisce le medesime prestazioni di quella originale con 
una significativa riduzione del tempo di risincronizzazione e del consumo energetico.
Capitolo 1: Sincronizzazione temporale nelle reti di sensori wireless 
 
1 
 
 
CAPITOLO 1 
 
Sincronizzazione temporale nelle reti di 
sensori wireless 
 
 
1.1 Introduzione alle reti di sensori wireless 
 
I continui progressi nelle tecnologie wireless e nell’ambito della microelettronica 
come l’introduzione dei MEMS (Micro Electro-Mechanical Systems) hanno condotto 
allo sviluppo di piccoli dispositivi a basso costo e a basso consumo energetico capaci di 
rilevare e monitorare vari aspetti del mondo fisico: i nodi sensore. 
Come mostrato in Figura 1.1, in generale un nodo sensore è costituito da una 
Sensing Unit formata da uno o più sensori, ovvero dispositivi in grado di tradurre una 
grandezza fisica in un segnale di natura diversa (tipicamente elettrico, tensione o 
corrente) allo scopo di acquisirlo ed elaborarlo in formato digitale; un convertitore ADC 
che converte la tensione in uscita dal sensore in un segnale digitale che viene elaborato 
dalla Processing Unit, composta da un microcontrollore che elabora le informazioni e 
che è supportato da un blocco di memoria; una Communication Unit con un
Capitolo 1: Sincronizzazione temporale nelle reti di sensori wireless 
 
2 
 
trasmettitore radio; una Power Unit, tipicamente una batteria, costituente la fonte di 
energia dell’intero dispositivo. 
 
Figura 1.1 – Architettura generale di un nodo sensore 
 
Le reti di sensori wireless (WSN, acronimo di Wireless Sensor Network) sono una 
particolare tipologia di reti ad-hoc costituite da un elevato numero di nodi sensore 
distribuiti in una regione di interesse detta sensing region in modo da formare 
spontaneamente una rete distribuita senza alcun bisogno di una infrastruttura 
preesistente [1]. A causa della mancanza di infrastruttura, i nodi in una rete ad-hoc 
cooperano nella comunicazione inoltrando pacchetti dalla sorgente alla destinazione, 
creando in tal modo un ambiente di comunicazione multi-hop. 
Sebbene siano una particolare tipologia di reti ad-hoc, comunque, le reti di sensori 
wireless presentano caratteristiche peculiari in termini di risorse di energia, memoria, 
capacità computazionale e banda di trasmissione limitate, elevata densità nello 
schieramento dei nodi, nodi sensore economici e non completamente affidabili.
Capitolo 1: Sincronizzazione temporale nelle reti di sensori wireless 
 
3 
 
1.2 Applicazioni e introduzione alla sincronizzazione 
temporale 
 
Lo sviluppo delle WSN fu originariamente motivato dalle possibili applicazioni in 
campo militare, come ad esempio la sorveglianza di un campo di battaglia e il 
rilevamento ed inseguimento di oggetti in movimento, ma la loro estrema versatilità a 
basso costo ha consentito loro di trovare ampio spazio in una molteplicità di ambiti 
applicativi. Alcuni esempi di applicazioni sono riassunti nella Tabella 1.1 [2]. 
 
Tabella 1.1 – Esempi di applicazioni delle reti di sensori wireless 
Ambito Applicazioni 
Militare 
Rilevamento di attacchi nucleari, biologici e chimici e presenza di 
materiali pericolosi. Segnalazione di attacchi nemici tramite allarme 
quando un velivolo nemico è individuato. Monitoraggio di forze alleate, 
equipaggiamento e munizioni. 
Ambientale 
Monitoraggio di incendi, rilevamento di alluvioni, smottamenti, terremoti 
ed eruzioni, controllo di habitat naturali. 
Civile 
Individuazione di posti liberi in un parcheggio, sorveglianza per la 
sicurezza di banche e centri commerciali, monitoraggio del traffico. 
Salute 
Ricerca di dottori all’interno di un ospedale, telemonitoraggio dei 
parametri vitali di un paziente o di un soggetto sottoposto a sforzo fisico. 
Domotica Automazione di porte, finestre, climatizzazione, illuminazione, allarmi. 
Scientifico 
Esplorazioni spaziali e interplanetarie, esplorazione di fondali marini, 
studio della radiazione cosmica. 
 
 
La raccolta dei dati di misurazione effettuata da una rete di sensori, tuttavia, può 
non portare alcuna informazione se non è accompagnata da un riferimento temporale 
omogeneo. Affinché le misure siano attendibili e i risultati fruibili, infatti, le 
applicazioni sopra elencate richiedono che i dati raccolti siano correlati fra loro nel 
dominio del tempo; occorre dunque un determinismo temporale delle misure. Come in 
tutti i sistemi distribuiti, quindi, la sincronizzazione temporale è una componente 
fondamentale nelle reti di sensori wireless.
Capitolo 1: Sincronizzazione temporale nelle reti di sensori wireless 
 
4 
 
1.3 Introduzione ai clock e problema della sincronizzazione 
 
Il problema della sincronizzazione in una rete di n nodi corrisponde al problema di 
uguagliare il clock dei diversi nodi. Un clock è essenzialmente un timer che conta le 
oscillazioni di un cristallo al quarzo ed è impiegato per sincronizzare i dispositivi 
elettronici digitali fornendo un riferimento temporale accurato, stabile ed affidabile.  
Nella realtà, nonostante la loro elevata stabilità, i cristalli al quarzo presenti sui 
nodi di un sistema distribuito oscillano a frequenze leggermente diverse, facendo 
divergere gradualmente i valori dei clock fra loro. Tale divergenza è formalmente 
definita clock skew e può condurre ad una nozione di tempo incongruente. La 
sincronizzazione nei sistemi distribuiti viene realizzata per correggere il clock skew. Ci 
sono due diffusi modi per raggiungere questo obiettivo: 
 I clock vengono sincronizzati ad un preciso standard di tempo reale come 
l’UTC (Universal Coordinated Time).  
 I clock vengono sincronizzati solo relativamente fra loro in quanto la 
richiesta in esame prevede di fornire esclusivamente un ordine degli eventi 
e non l’esatto tempo reale in cui ogni evento si è verificato. 
I dispositivi di calcolo sono solitamente dotati di un clock assistito da un oscillatore 
hardware, il quale implementa un’approssimazione C(t) del tempo reale t. La frequenza 
angolare dell’oscillatore hardware determina il rate a cui il clock lavora. Il rate di un 
clock ideale, che può essere indicato con 
dt
dC
, è pari ad 1, ma tutti i clock reali sono 
soggetti a drift; la frequenza dell’oscillatore quindi varia in maniera non prevedibile a 
causa di molteplici fattori quali temperatura, sbalzi di tensione, campi magnetici, 
voltaggio applicato, invecchiamento, usura. Nonostante la frequenza del clock sia 
variabile nel tempo, esso può essere approssimato con buona accuratezza con un 
oscillatore a frequenza fissa [3]. Quindi, per un qualunque nodo i nella rete, 
 
i i i
b t a t C   ) (  (1)
Capitolo 1: Sincronizzazione temporale nelle reti di sensori wireless 
 
5 
 
dove a
i
 è il drift del clock e b
i 
è l’offset del clock del nodo i. Il drift denota il rate 
(frequenza) del clock, l’offset è la differenza rispetto al tempo reale t. 
Mediante l’equazione (1) è possibile confrontare i clock locali di due nodi di una 
rete, indicati con nodo 1 e nodo 2: 
12 2 12 1
) ( ) ( b t C a t C    
dove a
12
 è il drift relativo e b
12
 è l’offset relativo tra i clock del nodo 1 e del nodo 2. 
Se i clock sono perfettamente sincronizzati il loro drift relativo è pari ad 1 (vale a dire 
che i clock hanno lo stesso rate) ed il loro offset relativo è pari a 0 (ovvero hanno lo 
stesso valore in quell’istante). Alcuni studi in letteratura usano il termine skew al posto 
di drift, definendolo come la differenza tra i rate dei clock. 
La sincronizzazione può essere globale, ovvero riguardare tutti i nodi della rete, o 
locale, cioè coinvolgere un sottoinsieme di nodi della rete, tipicamente vicini nello 
spazio. Uguagliare esclusivamente i valori istantanei (correggendo gli offset) dei clock 
non è sufficiente per la sincronizzazione in quanto i clock subiranno presto una nuova 
deviazione. Uno schema di sincronizzazione, quindi, deve o uguagliare i rate dei clock 
insieme agli offset, oppure correggere ripetutamente gli offset al fine di mantenere i 
clock sincronizzati per un periodo di tempo stabilito. 
La definizione di sincronizzazione appena fornita rappresenta attualmente la forma 
più severa di sincronizzazione, in cui si raggiunge il combaciamento perfetto del tempo 
su clock differenti, ma essa può essere estesa a diversi gradi di precisione a seconda 
delle necessità di un’applicazione. In generale, il problema della sincronizzazione può 
essere classificato in tre tipologie [4]. La prima e più semplice forma di 
sincronizzazione si occupa di ordinare eventi o messaggi. Lo scopo di un algoritmo di 
questo tipo è essere in grado di dire se un evento E
1
 si è verificato prima o dopo un altro 
evento E
2
, quindi esclusivamente paragonare i clock locali piuttosto che sincronizzarli. 
La seconda tipologia di algoritmi di sincronizzazione punta invece a conservare i clock 
relativi. In questo schema, i nodi fanno lavorare i propri clock locali in maniera 
indipendente, ma mantengono le informazioni circa il drift e l’offset relativo del loro 
clock rispetto agli altri clock della rete, così che in ogni istante il tempo locale del nodo 
possa essere convertito nel clock locale di qualche altro nodo e viceversa. La maggior 
(2)
Capitolo 1: Sincronizzazione temporale nelle reti di sensori wireless 
 
6 
 
parte degli schemi di sincronizzazione proposti per le reti di sensori usa questo modello. 
La terza e più complessa forma è il modello “always on”, dove tutti i nodi mantengono 
il proprio clock sincronizzato al clock di riferimento della rete. L’obiettivo di questo 
tipo di algoritmi di sincronizzazione è preservare una scala temporale globale per 
l’intera rete. 
Tutti i metodi di sincronizzazione temporale si basano sullo scambio di messaggi 
tra nodi [1]. Il non determinismo delle dinamiche della rete (legato ad esempio al tempo 
di propagazione o al tempo di accesso al canale fisico) rende l’operazione di 
sincronizzazione una sfida avvincente in molti sistemi. Il nodo che avvia il processo di 
sincronizzazione è denominato sender, il destinatario dei messaggi di sincronizzazione è 
indicato come receiver. Quando un nodo della rete genera un timestamp (sequenza di 
caratteri che identifica il verificarsi di un evento riportandone tipicamente la data e l’ora 
di occorrenza) da inviare ad un altro nodo per la sincronizzazione, il pacchetto 
contenente il timestamp sarà soggetto ad un ritardo variabile finchè non raggiungerà e 
sarà decodificato dal receiver predisposto. Questo ritardo impedisce al receiver di 
confrontare accuratamente i clock locali dei due nodi e sincronizzarsi con precisione al 
nodo sender.  
Per analizzare ed eventualmente compensare i ritardi non-deterministici cui un 
messaggio è soggetto in una WSN è opportuno decomporre le sorgenti di ritardo nelle 
seguenti componenti fondamentali: 
 Send Time 
 Access Time 
 Transmission Time 
 Propagation Time 
 Reception Time 
 Receive Time 
Ciacuna di queste componenti verrà descritta e discussa dettagliatamente nel 
Capitolo 2.