FTSP

Contact: Miklos Maroti, Brano Kusy

Institution: Vanderbilt University, Stanford University

License: Vanderbilt/Stanford BSD License

Date Modified: August, 2008

Description

Flooding Time Synchronization Protocol (FTSP) is an ad-hoc, multi-hop time synchronization protocol for WSNs. It achieves high accuracy by utilizing timestamping of radio messages in low layers of radio stack, completely eliminating access time to the radio channel required in CSMA MAC protocols. Further accuracy is achieved by compensating for clock skews of participating nodes via linear regression. Several mechanisms are used to provide robustness against node and link failures, most notably periodic flooding of synchronization messages throughout the whole network. FTSP uses relatively low communication bandwidth by using one-way traffic for synchronization. FTSP is an in-network timesync protocol - one of the nodes is selected to be the root which is responsible for broadcasting global time.

Links

• paper: acm link
• code: library testapp
• TinyOS2 documents: PacketTimeStamp TEP TimeSyncPacket TEP

Known Problems

• radio message timestamping: in TinyOS2, timestamping and timesync are strictly separated (see TEPs 132, 133) and FTSP is implemented on top of PacetTimeStamp, TimeSyncPacket, and TimeSyncAMSend interfaces.
  • so far only code for CC2420 and RF320 radios was ported to TinyOS2, CC1000 still needs to be ported
  • CC2420 timestamping code has a [PacketTimeStamp_CC2420 bug]

FAQ

• QUESTION: do i need the skew thing?

you need the skew thing! it is necessary because frequencies of crystals at different nodes are slightly different. since we want precision in microsecond range, we need to compensate for the skew. specs for MICA2 say that CPU frequency should be 7.3828 MHz. In reality your mote's frequency would be eg. 7.3827 MHz and of a different mote 7.3829 MHz which introduces 20 clock ticks error each second. this small error would accumulate over time far beyond the intended precision...

• QUESTION: i don't understand how you calculate and update skew!

A: skew is defined as the ratio of global and local time frequencies:

       global = SKEW*local + OFFSET

where global, local are variables and SKEW, OFFSET are constants specific to individual motes (however, skew is time-dependent)

since we know that frequencies of 2 different clock crystals are almost the same, value of SKEW is very close to 1.0: i.e., SKEW = 1.0+ 10^-5. representing such value is less efficient than representing close-to-zero value. therefore, we always subtract 1.0 from SKEW (SKEW_1=SKEW-1.0), getting the following equation for offset of global and local times (offset=global-local):

   offset = SKEW_1*local + OFFSET  (1)
   

in order to further decrease the error of the multiplication, we keep OFFSET_A for some recent point in time (LOCAL_A) and do the following:

    OFFSET_A = SKEW_1*LOCAL_A + OFFSET (2)
    offset - OFFSET_A = SKEW_1 * (local - LOCAL_A)
    offset = OFFSET_A + SKEW_1 * (local - LOCAL_A)	

formula for the global time is then:

    global = local + OFFSET_A + SKEW_1 * (local - LOCAL_A)

FTSP implementation defines LOCAL_A as the average of times stored in FTSP's linear regression table. one problem to take care of is that the root node does not update LOCAL_A time which introduces large multiplication error after some time. therefore, FTSP forces the root to update LOCAL_A and OFFSET_A values (infrequently):

   if( (int32_t)(local - LOCAL_A) >= 0x20000000 ) (line 330, TimeSyncP.nc file)