Clock Synchronization in Wireless Sensor Networks: Statistical and Algorithmic Analysis

In the past few years, the impressive growth of applications performing tasks in a distributed fashion has been enabled by the availability of tiny, inexpensive devices which, in turn, has been made possible by the recent micro-electromechanical technology advancements. Sparsely disposing small intelligent appliances throughout a specific area is something that the community has become used to. Low cost and low power sensing devices equipped with telecommunication hardware are attractive for use in an infrastructure-less network in which the absence of a central node stands out, making robustness be one of the strengths of this kind of networks. Environmental monitoring and military surveillance are just a few examples of the number of applications suitable for sensor networks; in fact, home automation and several health services also can be implemented given that a distributed network of sensors exists. Sensors need to keep track of a common time scale. This is fundamental for prolonging the network lifetime, making channel access schemes work properly, for example, or for allowing precise duty cycling among the nodes. Clock synchronization is also basic if the goal of a running application is to track moving objects in the battlefield or, more generally, to perform distributed processing of the sensed data. Since the local notion of time in a sensor is based on a low quality local oscillator, it turns out that even small changes in the environmental conditions, like temperature and pressure, lead to modification in the oscillation frequency of the quartz crystals, thus producing time discrepancies among different sensor nodes as time goes by. This thesis tackles the problem of clock synchronization in sensor networks, both from a perspective of clock parameters estimation and from an algorithmic point of view, to pursue the final goal of making nodes agree on a common time scale, all across the network. In the first part of the thesis, the so-called two-way message exchange between two nodes is thoroughly analyzed. After recalling existing results on clock parameters estimation exploiting data collected via this message exchange process on the wireless channel, an innovative mathematical framework is introduced, which encompasses several common assumptions for the random delays present in the collected data, in a more general treatment. Based on this new framework, a factor graph-based clock offset estimator for wireless sensor networks is proposed and evaluated. Comparison of the variance of the estimation error with classical bounds available in the literature shows that the new estimator has extremely good performance, therefore it can be considered outstanding among Bayesian clock offset estimators. The focus of the second part of the thesis is on the design of distributed consensus algorithms in wireless sensor networks, especially for observations averaging purposes. In fact, an innovative fast consensus algorithm is proposed and evaluated, based on the alternating direction multipliers method, which is a distributed method used to solve minimization problems in an iterative fashion. The new consensus algorithm is compared with the state-of-the-art of fast consensus, showing an excellent convergence rate and an outstanding noise resilience. The proposed algorithm is then applied to solve a network-wide clock synchronization issue, assuming both clock skew and offset for the nodes in the network, showing a relevant performance improvement with respect to previously proposed consensus-based synchronization schemes. Finally, the Appendix contains a work whose topic falls out of the main stream of this thesis: in uplink cellular networks, based on the knowledge of channel statistics, surrounding base stations are carefully and iteratively chosen in order to provide the mobile terminal a certain quality of service in terms of the maximum allowed outage probability, with the aim of minimizing the overall backhaul network usage.

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.