Global Time Synchronization in Sensornets
           Richard  Karp


Time synchronization plays a central role in sensornets,
whose deeply distributed nature necessitates fine-grained coordination
among nodes.  Precise time synchronization is needed for a variety of
sensornet tasks such as sensor data fusion, TDMA scheduling,
localization, coordinated actuation, and power-saving duty cycling.
Some of these tasks require synchronization precision measured in 
microseconds,Moreover, the severe power limitations endemic in sensornets 
constrain the resources they can devote to synchronization.  Thus, sensornet 
time synchronization must be both more precise, and more energy-frugal, than 
traditional time synchronization methods.

We assume that each node in a sensornet has a clock which is offset by
an unknown amount from a universal time standard. In order to synchronize,
two nodes must have an accurate estimate of the difference between their 
offsets. The core of any synchronization algorithm is a distributed method of
achieving these estimates. The recent Reference-Broadcast Synchronization 
(RBS) design postulates that many synchronization signals are broadcast 
locally within the sensornet and received simultaneously by different sets of
nodes. The nodes receiving a signal observe (with some error) the times of
reception on their local clocks and share those observations among themselves.

Given a model of measurement error, we consider the problem of characterizing
minimum-variance estimators of the offsets, and developing a distributed 
algorithm for computing these estimators. In order to solve these problems we 
draw upon results from network flow theory, electric circuit theory, random 
walks, computational linear algebra and theoretical statistics. 

This is joint work with Jeremy Elson, Deborah Estrin, Christos Papadimitriou 
and Scott Shenker.