Global Time Synchronization in Sensornets

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.

Short Biography:

Homepage: http://www.cs.berkeley.edu/People/Faculty/Homepages/karp.html