Fine Grained Network Time Synchronization using Reference Broadcasts Jeremy Elson Lewis Girod and Deborah Estrin U C L A Presenter Todd Fielder Time Synchronization Applications to Sensor Networks Security Cryptography Coordinate Future Action Domain Specific Integrate proximity detections into a velocity estimate Suppress redundant messages by recognizing duplicated sensed events Sources of Time Synchronization Errors Send Time Message construction time varies among senders Non determinant Dependant on instantaneous load on CPU Access Time Channel access time is indeterminate Non determinant Dependant on instantaneous load on Network Propagation Time Distance to receivers varies Effectively zero RF close to speed of light RBS only takes into account differences in distance of receivers However Increases if receivers are at different sides of sender Receive Time Time to deliver to application varies messages in queue can cause delay Mitigated by reading timestamp at interrupt time Reference Broadcast Synchronization Synchronizes a set of receivers with one another Traditional method synchronizes senders with receivers Receivers use the arrival time of a reference broadcasts as a point of reference for comparing their clocks Avoids errors due to Send Time and Access Time Synchronization Algorithm Phase Offset Estimation Transmitter broadcasts a reference packet to two receivers Each receiver records the time according to its local clock Receivers Exchange their observations and synchronize with the average Synchronizes relative timescales Global time is not important in Sensor Networks Or is it Synchronization Algorithm cont Estimation of Clock Skew Accuracy The agreement between an oscillator s expected and actual frequencies Stability An oscillator s tendency to stay at the same frequency over time least squares linear regression Finds the best fit line through the phase error observations over time Additional Comments Requires additional overhead between all communicating nodes If two nodes cannot communicate directly multi hop communication is required or substantial message passing No energy usage graphs presented How does a node know if reference broadcasts is meant for it May cause nodes to unnecessarily expend energy to synchronize However more efficient than traditional protocols because receivers do not need to maintain synchronization Can synchronize after hours or days of sleep Do receivers need to maintain synchronization in NTP Experiment Traffic scenarios Heavy traffic Light traffic Three synchronization techniques tested RBS synchronizes receivers NTP uses GPS and a NTP server to synchronize to an external timescale NTP offset NTP limits rate at which to correct phase error this variation does not in order to allow for more fair testing of synchronization precision Experimental Results application Level Light Traffic RBS performed 8 times better than NTP RBS 6 29 6 45 usec Causes of jitter Code path through network stack Time required to schedule daemon System calls to get current time NTP 51 18 53 30 usec Heavy Traffic RBS performance remained almost consistent while NTP performance degraded 30 fold RBS 8 44 usec NTP 1 542 usec For reasons unknown performance of NTP offset was much worse than NTP Experimental Results Kernal Level Timestamps acquired at the network interrupt handler RBS performance improved considerably 1 85 1 26usec Result limited by 1usec clock resolution Multi Hop Synchronization Nodes 1 2 3 4 synchronize to each other based on A s broadcast Nodes 4 5 6 7 synchronize to each other based on B s broadcast Node 4 is now common among all nodes and can synchronize A and B based on a best fit line At next reference broadcast all nodes will be synchronized Time Routing Not necessary to have a common node actively synchronize two distinct regions Can dynamically determine the timeroute for packets to be routed and converted on the fly Route packets through gateway node which can determine conversion from one time base to another Performance Each conversion step can introduce error How is that error amplified as the hoplength increases Average per hop error is e For n hops estimated error is e n 1 2 Experimental Results For a 4 hop network average error is 3 68 2 57usec Additional Comments Causes Gateway nodes to perform additional computation Is there a way to verify gateway node is not compromised Can C be a watchdog over 4 7 8 9 to ensure that all times reported are in a specified range Is there a way for C to Know that 8 and 9 should be reporting the same value i e that they are both in the same region External Timescales Treat GPS as a Broadcasts Beacon To Work effectively GPS must be attached to every Broadcast beacon in network Need to distribute additional computation load Time routing causes some conversion between unsynchronized regions