OVERVIEW

The applications envisioned for ENS systems require collaborative execution of a distributed task amongst a large set of sensor nodes. The collaborative execution is realized by exchanging messages that are time-stamped using the local clocks on the nodes. To take examples from existing sensor network applications: precise time is needed to measure the time-of-flight of sound; distribute an acoustic beam forming array; form a low-power TDMA radio schedule; integrate a time-series of proximity detections into a velocity estimate; suppress redundant messages by recognizing duplicate detections of the same event by different sensors; or forming a basic building block for cryptographic techniques. Therefore, time synchronization becomes an indispensable piece of infrastructure in such distributed systems. For years, protocols such as NTP have kept the clocks of networked systems in perfect synchrony. However, this new class of wireless sensor networks has a large density of nodes and very limited energy resource at every node; this leads to scalability requirements while limiting the resources that can be used to achieve them. A new approach to time synchronization is needed for the wireless sensor networks.

Time synchronization is a critical piece of infrastructure in any distributed system. Time synchronization problem has been investigated thoroughly in Internet and LANs. Several technologies such as GPS, radio ranging etc have been used to provide global synchronization in networks. Complex protocols such as NTP [4] have been developed that have kept the Internet’s clocks ticking in phase. However, the time synchronization requirements differ drastically in the context of sensor networks. In general such networks are dense, consisting of a large number of sensor nodes. To operate in such large network densities, we need the time synchronization algorithm to be scalable with the number of nodes being deployed. Also, energy efficiency is a major concern in these networks due to the limited battery capacity of the sensor nodes. This eliminates the use of external energy-hungry equipments, such as GPS receivers. Moreover, the time synchronization requirements are much more stringent, often requiring synchronization of the order of microseconds among nodes involved in a task such as tracking a target. Furthermore, the diversity of requirements on timing synchronization accuracy makes it much more challenging to pertain to the different needs of applications. For example, acoustic applications require precision of several microseconds, while sensor tasking works on the timescale of hours or days. Local collaborations often require only a pair of neighbors to be synchronized, while global queries require global time.

APPROACHes

One of the principle design guidelines for our time synchronization approach is that it should be multi-modal.  The wide range of requirements across applications can not be satisfied by a single scheme – as no single scheme is optimal along all axes (e.g. scope, availability, precision, persistence of the timescale, and so forth). For example, GPS time is an attractive form of time synchronization and can often achieve a precision of 50 nanoseconds.  However, it has drawbacks: it is not available ubiquitously (e.g., under foliage, indoors, underwater), and requires a relatively high-power receiver that is not feasible on the smallest, cheapest nodes. We have several approaches to in-network time synchronization.

Timing-sync Protocol for Sensor Networks (TPSN) works on the conventional approach of sender-receiver synchronization. This approach leverages the fact that the operating system has direct access to the underlying MAC layer of the radio: by time-stamping packets directly at the MAC layer, much of the normal non-determinism of channel access is eliminated, resulting in relatively high precision without a complex protocol.

A second approach based on receiver-receiver synchronization, termed as Reference Broadcast Synchronization (RBS) – does not require access to the MAC layer.  Instead, this scheme recognizes that most of the unpredictable jitter in message delivery comes from the sender; by eliminating the sender from the critical path, error can be significantly reduced.

SYSTEMS / EXPERIMENTS

Both TPSN and RBS have been fully implemented on Berkeley motes. Recently, we have also been successful in developing standalone implementations for these protocols on Linux based sensor networking platforms such as Stargates and IPAQs. We have also integrated these protocols with the approach of post-facto synchronization to provide multi hop synchronization over a network of nodes. We have been able to extend these protocols to provide network-wide time synchronization in a sensor network. The algorithm works in two steps. In the first step, a hierarchical structure is established in the network and then a pair wise synchronization is performed along the edges of this structure to establish a global timescale throughout the network. Eventually all nodes in the network synchronize their clocks to a reference node. We have verified the efficacy of our approaches over large-scale networks through simulations in NESLsim, a PARSEC based simulation platform for sensor networks.

ACCOMPLISHMENTS

Our major accomplishments in time synchronization included new design, implementation, and characterization of new methods. We demonstrated three new methods to the palette of synchronization methods available to sensor network developers:

• Pairwise synchronization ---- We have been able to synchronize a pair of neighboring motes to an average accuracy of around 17 ìs on Mica1 and 10 ìs on Mica2 using TPSN. The worst case error between the pair of neighboring motes is less than 50 ìs, clearly showing the efficacy of our approach.
  
  To gauge the performance on Linux based platforms, we use RBS. We use measurements from two wireless implementations to show that removing the sender's nondeterminism from the critical path in this way produces high-precision clock agreement (1.85 -1.28 ìs), using off-the-shelf 802.11 wireless Ethernet), while using minimal energy.
  
• Multi-hop synchronization --- Using TPSN we were able to synchronize motes, having a 5 hop distance between them, to an average accuracy of around 30 ìs. Using RBS, we measured an error of 3.68 - 2.57 usec{} after 4 hops over a network of IPAQs.
  
  Our analysis shows the multi-hop algorithm should experience a slow decay in precision; the standard deviation grows as O(sqrt{n}) after n hops. The multi-hop algorithm allows coordination of any size group; the error incurred is only as large as the distance between the nodes using the synchronization.
  
• Post-Facto Synchronization --- A technique that allows significant energy savings in networks where time synchronization is needed occasionally and unpredictably. Instead of keeping clocks synchronized all the time, clocks run undisciplined (at their natural rate), and are reconciled after an event of interest occurs. We show experimental results that explore the error incurred with variations on this scheme.
  
• Network-wide Synchronization --- We have gauged the performance of TPSN on large-scale networks using simulations over NESLsim. The simulated topologies consist of nodes varying from 150 to 300. We found out that the synchronization error between two neighboring nodes in the network is independent of the total number of nodes in the network. However, the synchronization error of a node with respect to the root node depends on its hop distance from it. This is because error adds up over multihop. Although the randomness in the sign and magnitude of the error and the drift prevents it from blowing up, the synchronization error is still a non-decreasing function of the hop distance. Further, the worst-case scenario of linear increase with the hop distance was never observed. Further, the energy consumed by every node to synchronize itself was also measured to be a constant with the increase in number of nodes. This clearly proves that TPSN is scalable for dense networks but nor for expanding networks.

FUTURE DIRECTIONS

• Group synchronization: All current approached use the technique of pairwise synchronization but this is insufficient in cases where a group of nodes need to be synchronized up for instance in tracking. In a group sync model, a single beacon beacons, all receivers respond with their offset to the beacon. The Beacon has one measurement to relate each pair of nodes which either form a sender-receiver (s-r) pair or a receiver-receiver (r-r) pair. This approach will have a 5x extra cost but will result in 1 measurement between any pair of nodes resulting in achieving better levels of accuracy.
• Using diversity to improve multihop synchronization: Given a fixed number, N, of broadcasts, can we achieve a precision D between the synchronization levels of nodes. N cascading broadcasts, where each broadcast from a beacon carries information about prior relationships (offsets) that the beaconing node knows about.
• Timing synchronization on Stargates: We are currently in the process of implementing TPSN over stargates. The preliminary results look promising. We have been able to achieve level of synchronization accuracy to the order of 10 ìs between a pair of stargates.
• Exploiting hierarchy: As observed from our results, the multihop error between motes increases with distance. A way of reducing the error between distant motes is to reduce the effective number of hops between them. We plan to do this by tunneling the synchronization messages over the long range 802.11 link. The general architecture will consist of motes and stargates in the network, whereby stargates will act as proxy servers between two distant motes.
• Untill now existing work in the literature concentrates on establishing pairwise relationships between a pair of nodes at a given instant of time. However, there is need of developing a unified framework that combines temporal clock characteristics and spatial redundancy in routing paths. Specifically, given an error bound by the user, how can it be achieved for a specific long-lived sensor network application exploiting the temporal and spatial aspect of these networks. From a temporal aspect, the end objective is to decide the frequency of periodic point-to-point synchronization. A node can be potentially synchronized to many nodes in the network; the choice of these reference nodes/beacons forms the spatial aspect of the problem.

PEOPLE

FACULTY

Prof. Deborah Estrin
Prof. Mani Srivastava

GRADUATE STUDENTS

Saurabh Ganeriwal
Deepak Ganesan
Ram Kumar

STAFF

Jeremy Elson