Clock Synchronization in Wireless Sensor Networks: Statistical and Algorithmic Analysis

Negli ultimi anni abbiamo assistito alla continua comparsa di applicazioni distribuite, la cui implementabilita' risulta consentita dalla possibilita' di avere a disposizione sensori piccoli ed economici. I recenti progressi tecnologici nel settore micro-elettronico-meccanico hanno infatti consentito una miniaturizzazione dei nodi sensore. La comunita' scientifica si e' oramai abituata alla possibilita', con una spesa minima, di collocare piccoli dispositivi intelligenti lungo un'area specifica. Sensori economici e a basso consumo, una volta muniti dell'hardware necessario per le telecomunicazioni, risultano ideali per l'utilizzo in reti senza infrastruttura, uno scenario in cui spicca l'assenza di un nodo centrale e la robustezza diviene quindi una proprieta' fondamentale. Monitoraggio ambientale e sorveglianza militare sono solamente un paio di esempi di applicazioni adatte a reti di sensori, cosi' come la domotica e l'ambito sanitario risultano scenari in cui l'uso di una rete distribuita di sensori puo' rivelarsi, in effetti, utile e vantaggiosa. I sensori necessitano di una base temporale comune. Questo bisogno risulta fondamentale al fine di prolungare il tempo di vita di una rete, ottimizzando schemi di accesso deterministico al mezzo, ad esempio, oppure schedulando i periodi di attivita' dei nodi in maniera precisa. La sincronizzazione risulta fondamentale anche in applicazioni legate alla localizzazione, o piu' genericamente, per permettere l'elaborazione distribuita di dati raccolti dai sensori stessi. Dal momento che la nozione di tempo locale in un sensore e' fornita da un oscillatore di bassa qualita', anche minime perturbazioni delle condizioni ambientali (come temperatura e pressione) si riflettono in modifiche nella frequenza di oscillazione del cristallo di quarzo, producendo discrepanze nel comportamento tra oscillatori in diversi sensori, che diventano non trascurabili man mano che il tempo scorre. Questa tesi affronta il problema della sincronizzazione di clock in reti di sensori, sia da una prospettiva di stima dei parametri di clock, sia da un punto di vista algoritmico lungo tutta la rete, con l'obiettivo finale di permettere ai nodi interessati di trovare una concordanza su una scala temporale comune. Nella prima parte di questa tesi viene analizzato il processo di scambio di informazioni tra due nodi chiamato two-way message exchange. Dopo aver richiamato la letteratura esistente sulla stima dei parametri del clock utilizzando questo protocollo di scambio dati attravero il canale wireless, viene introdotto un nuovo framework matematico per permettere un'assunzione piu' generale riguardo i ritardi casuali presenti nei dati raccolti. Basandosi su questo framework, viene proposto e studiato un nuovo stimatore del clock offset basato sulla teoria dei factor graphs. Dal confronto della varianza dell'errore di stima con classici limiti inferiori presenti in letteratura risulta che il nuovo stimatore proposto permette degli ottimi risultati, per cui puo' a pieno titolo essere considerato meritevole di menzione nella teoria della stima Bayesiana applicata al clock offset. La seconda parte della tesi riguarda invece la progettazione di algoritmi di consensus distribuiti per reti di sensori wireless, in special modo per operazioni di averaging svolte in maniera distribuita. Viene proposto e valutato un nuovo algoritmo di consensus velocizzato basato su alternating direction multipliers method, un metodo distribuito per risolvere problemi di minimizzazione in modo iterativo. Il nuovo algoritmo di consensus viene confrontato con lo stato dell'arte del consensus velocizzato, mostrando un'eccellente velocita' di convergenza e una resistenza al rumore migliore rispetto agli altri algoritmi presenti in letteratura. Lo schema proposto viene poi applicato al problema della sincronizzazione di clock in reti di sensori wireless, assumendo presenza di clock skew e clock offset tra i vari oscillatori della rete. L'algoritmo di sincronizzazione risultante consente un rilevante miglioramento delle prestazioni rispetto a schemi di sincronizzazione basati su consensus proposti in precedenza. Infine, nell'Appendice viene descritto un lavoro il cui argomento si discosta da quello principale della tesi: in reti cellulari in uplink, in base alla statistica del canale le stazioni base cooperanti vengono selezionate tramite l'utilizzo di tecniche iterative con l'obiettivo di garantire al terminale mobile una certa qualita' del servizio in termini di probabilta' di disservizio massima permessa e allo stesso tempo di minimizzare l'utilizzo della rete di backhaul.