Wireless Sensor Network, 2010, 2, 739-745
doi:10.4236/wsn.2010.210089 October 2010 (http://www.SciRP.org/journal/wsn/) Published Online
Fault-Tolerant WSN Time Synchronization*
Ung-Jin Jang, Sung-Gu Lee, Jun-Young Park, Sung-Joo Yoo
Department of Electronic and Electrical Engineering, Pohang University of Science and Technology, Pohang, Korea
Received June 13, 2010; revised July 16, 2010; accepted August 21, 2010
Abstract
This paper proposes a new fault-tolerant time synchronization algorithm for wireless sensor networks that
requires a short time for synchronization, achieves a guaranteed time synchronization level for all non-faulty
nodes, accommodates nodes that enter suspended mode and then wake up, is computationally efficient, oper-
ates in a completely decentralized manner and tolerates up to f (out of 2 f + 1 total) faulty nodes. The per-
formance of the proposed algorithm is analyzed, and an equation is derived for the resynchronization interval
required for a specific level of synchronization precision. Results obtained from real runs on multi-hop net-
works are used to demonstrate the claimed features of the proposed algorithm.
Keywords: Fault Tolerance, Time Synchronization, Wireless Sensor Network
1. Introduction
A wireless sensor network (WSN) can be used to gather
specific physical or chemical data in a target area. A
sensor node typically uses a microprocessor with low
speed and low power usage and a radio module with low
data rates because most sensor nodes used in WSNs are
low-cost devices powered by batteries. In spite of the
limited capabilities of the sensor node, the WSN is still a
very useful system for data gathering because it “auto-
nomously” gathers data and maintains network connec-
tions until its nodes’ batteries are entirely consumed. For
example, a WSN can be constructed to monitor the eco-
logical environment for a long period without additional
human intervention. A WSN is also useful for monitor-
ing harsh environments such as fire areas, toxic-spill
areas, and mind fields.
In some WSN applications, the sensor nodes require
identical time values, i.e. synchronized clocks, with each
other. For example, let us consider an application to de-
tect and track a target using triangulation. If we use the
time difference of arrival of sonic waves for target detec-
tion, time differences can be measured exactly when
three nodes that hear the sound have synchronized clocks.
Another useful applications is time-division multiple
access (TDMA) for wireless communication. By using
the TDMA method, each node of a WSN can communi-
cate without radio channel conflicts, thereby reducing
packet loss and energy consumption due to rebroadcast-
ing. If the nodes don’t have synchronized clocks, TDMA
communication on a fine scale cannot be used. Synchro-
nized clocks are also required for periodic sleep-and-
wake scheduling of sensor nodes. The sensor nodes go to
sleep to reduce energy consumption when they have
nothing to do; then they wake up when there is some-
thing to do such as sensing, transmitting, or receiving. To
make sure that sufficient numbers of nodes remain
awake in a given area at any one time, such sleep-wake
cycles must be coordinated using synchronized clocks.
Time synchronization, or clock synchronization, refers
to the means by which nodes in a distributed network are
able to maintain clock values that are identical with each
other within a specific error bound. Time synchroniza-
tion has been studied by many researchers over the past
30+ years. Most of the previously studied works consid-
ered general computing system and wired communica-
tion environments. However, the computational capabili-
ties of a node in a WSN are limited, and the wireless
communication environment is more unpredictable and
unreliable than a wired communication environment. So,
such works can’t be directly adopted for use in WSNs. In
recent years, a number of time synchronization methods
have been specifically proposed for use with WSNs. Re-
ference Broadcast Synchronization (RBS) [1], Time-sync
Protocol for Sensor Networks (TPSN) [2] and Flooding
Time Synchronization Protocol (FTSP) [3] are three of
*A very preliminary version of this work was presented at the 2008
International Symposium on Object/component/service-oriented Real-
time distributed Computing (ISORC). This paper is a major rewrite o
f
that version that includes basic changes to the proposed algorithm, more
detailed analysis and additional experimental results.

U. JANG ET AL. 740
the most well-known and practical methods that have
been proposed. RBS uses receiver-receiver synchroniza-
tion, in which a reference node broadcasts an event
packet to let receivers compare time differences with
each other. By having receivers compare the times when
they received the same broadcast event packet, it is pos-
sible to mitigate the effect of widely variable communi-
cation delays in wireless networks. TPSN uses a tree
structure and adopts MAC-layer timestamps for accurate
synchronization, whereas FTSP uses flooding and more
precise MAC-layer timestamps to improve performance.
These methods are all highly dependent on the reference
node selected, and there are no mechanisms for dealing
with timer faults or otherwise faulty nodes.
Since WSNs typically use large numbers of low-cost
devices, fault-tolerance should be of utmost concern with
any WSN application. Recently, a few works have ad-
dressed the fault-tolerance problem with regards to WSN
time synchronization. However, methods such as [4] and
[5] only work in single-hop networks, while other me-
thods such as [6-8] considered multi-hop networks with
severe restrictions on node behavior and/or limited to-
pologies.
In this paper, fault-tolerance is addressed by proposing
a practical and generally usable fault model (based on
experiments with actual WSN devices), and a time syn-
chronization method is proposed that can achieve a
guaranteed level of fault-tolerance in arbitrary multi-hop
networks. The proposed method, Fast-Fault Tolerant
Synchronization (FFTS), tolerates up to f faulty nodes
while guaranteeing a specific level of maximum syn-
chronization error. This paper is organized as follows.
Section 2 gives the system model and Section 3 describes
the proposed time synchronization method, FFTS. Sec-
tion 4 provides an analysis of the FFTS algorithm and
Section 5 gives experimental results. Finally, Section 6
provides concluding remarks.
2. System Model
The system model used is based on our experience with
practical WSN systems built using current commercial
devices, such as MICAz motes. Let us consider a net-
work N with n sensor nodes. Each node si (i = 1, 2, ..., n)
has a hardware counter (also referred to timer), which is
increased at a rate based on a hardware oscillator. The
value of counter ci(t) at real time t is used to represent a
local time value tvi(t),
i
i
iFO
t
c
ttv )( )(  (1)
where FOi is the frequency of the local timer. If the exact
value of FOi is known and this value remains constant,
then time synchronization between two nodes can be
achieved simply by a one-time adjustment of the effec-
tive timer frequency and initial offset of one node to fol-
low that of the other node. However, in real hardware
devices, the value of FOi varies over time due to envi-
ronmental factors and intrinsic hardware variations. To
model this type of behavior, let the drift rate ρi of si de-
note the difference between the current local time value
and the real time value. Then, the local time value can be
expressed as (2). The local time value increases faster
than real time when ρi is positive and increases slower
than real time when ρi is negative.
tttv ii 

)1()(

(2)
In a general WSN N, the local time values of the sen-
sor nodes will tend to drift away from other. Thus, in
order to maintain a global time base, a time synchroniza-
tion procedure needs to be executed at each node. Let us
consider the use of a procedure in which each node peri-
odically adjusts the frequency and offset of its timer
based on the local time value of a unique reference node,
as communicated to it through a multi-hop wireless net-
work.
“Real time” is extremely difficult to maintain as real
time is an “amorphous concept” whose exact value de-
pends on the movement of celestial objects in space.
Thus, real time is normally approximated by an interna-
tionally agreed-upon standard time referred to as Coor-
dinated Universal Time (UTC) [9]. However, even accu-
rate UTC time is difficult to maintain as it requires a ra-
dio receiver that receives periodic radio broadcasts of
UTC time. With the low-cost sensor nodes typically used
in WSNs, it is assumed that such radio receivers are not
used. Given this limitation, time synchronization in the
WSN depends heavily on the unique reference node used.
This reference node should be a “nonfaulty” node with
small variability in the drift rate of its timer. If we regard
t to be the reference time value (the local time of the ref-
erence node), the synchronized time value tv_synci (t)
can be obtained by adjusting the drift rate and initial off-
set of the local time of node si relative to the reference
node. If the node si has been resynchronized at times t1
and t2 (in that sequence), then the synchronized time at
time t after t2 can be approximated using the following
formula:
offsetelapsedadji ttftsynctv 

)(_ (3)
where
,
)()( 12
12
ttvttv
tt
f
ii
adj 


),()( 1 ttvttvt iielapsed 

)(ttvt 1ioffset

Due to cost limitations, each sensor node of a WSN is
assumed to have low-cost timer, processor, and wireless
communication modules. This will result in high node
failure rates and wide variations in the quality of timer
modules. The use of fault tolerance techniques can sig-

U. JANG ET AL. 741
nificantly increase the reliability and accuracy of appli-
cations executed on such WSNs. Thus, in this paper, we
propose a fault-tolerant time synchronization method
based on message-passing. To analyze the expected be-
havior of our method, the set of faults to be tolerated will
be restricted to timer faults as defined below. If nodes
can fail in any manner, then time synchronization cannot
be achieved for nonfaulty nodes that can communicate
with the reference node only through such faulty nodes.
However, it is expected that most faults in WSNs will
involve nodes that either stop working altogether (due to
depletion of batteries) or produce highly inaccurate timer
values. “Fail-stop” nodes can be tolerated by commonly-
used fault-tolerance techniques that involve routing around
such nodes. Thus, the fault-tolerance techniques presented
in this paper will focus on timer faults.
Definition 1: Given a permitted drift rate ρ, a node
si is nonfaulty during the real time interval [t1, t2] if
212 121
(1)( )()()(1)( )
ii
tt tvt tvttt

  . Otherwise,
si has a timer fault.
A node with a timer fault will be considered to be a
faulty node. Since the local time maintained by each no-
de will be adjusted periodically according to Equation (3),
a faulty node will be one in which the drift rate has
changed drastically from the last time it was measured. A
node reporting a local time value drastically different
from neighboring nodes can also be diagnosed as faulty
by those neighboring nodes based on Definition 1. A no-
de with a timer fault should definitely not be selected as
the reference node. The level of synchronization to be
achieved and the problem to be solved in this paper can
be written as follows.
Definition 2: Given a synchronization bound δ, two
nodes si, sj are δ-synchronized at real time t if and only if
 )()( ttvttv ji [10].
Fault-Tolerant Time Synchronization Problem: For a
given WSN with 2 f + 1 nodes, of which up to f nodes
may be faulty, devise a software procedure that can be
executed at each nonfaulty node such that all nonfaulty
no- des remain δ-synchronized during the lifetime of the
WSN.
3. Fast Fault-Tolerant Time Synchronization
The proposed Fast Fault-tolerant Time Synchronization
(FFTS) algorithm, executes iteratively in two phases. In
Phase 1, executed by a node when it first starts time
synchronization and when it wakes up after being in
sleep mode (in order to conserve its energy) for a long
time, a short resynchronization interval P1 is used. After
Phase 1 has been executed for a fixed number of itera-
tions (after K SYNC packets have been received), the
node will enter Phase 2 and use a much longer resyn-
chronization interval P2. The use of a short resynchroni-
zation interval during Phase 1 permits a node to quickly
become synchronized to a reference node. The use of a
longer resynchronization interval during Phase 2 permits
a node to maintain time synchronization with low mes-
saging and computing overhead. Except for the resyn-
chronization interval used, the operation of a node during
Phase 1 and Phase 2 are identical.
Within each phase of the FFTS algorithm, the nodes in
the WSN first cooperate with each other to decide on a
reference node. After the reference node has been deter-
mined, each node adjusts its local time iteratively (with
period P1 or P2) based on Equation (3).
The main “intelligence” of the FFTS algorithm in-
volves the selection of the reference node. Given the
possibility of up to f faulty nodes, a node should collect
at least f + 1 timestamp values since up to f of these val-
ues may be faulty. However, for f + 1 timestamps to be
sufficient, there must be an indicator of which of these f
+ 1 timestamps are nonfaulty (such as a nonforgeable
signature). Since such a nonfaulty indicator is not as-
sumed, 2 f + 1 timestamps are used. The nonfaulty time-
stamp can then simply be selected as the median value,
which must be nonfaulty by Definition 1.
The possibility of multi-hop message transmissions in
WSNs presents a challenge when attempting to select a
unique nonfaulty reference node for time synchroniza-
tion purposes. If timestamps are broadcast by all nodes in
a periodic manner and each node waits until 2 f + 1 time-
stamps are collected before selecting a median value,
several such median values will exist in a multi-hop
network since areas of the network that are widely sepa-
rated will tend to form separate cliques. All such median
values must be reconciled into a unique reference time-
stamp in order to realize a time-synchronized network.
The approach adopted in the FFTS algorithm is to com-
bine two median values into the maximum of the two
values whenever two such values are observed (a
“max-of-median” approach). After a few iterations (with
the number of iterations dependent on the network di-
ameter, the maximum distance in hops between any two
nodes of the network), this will result in a globally
unique reference timestamp (the timestamp generated by
the reference node) value.
Two types of packets are used to implement the above
procedure. INITSYNC packets contain up to 2 f + 1 time
values (ID and timestamp pairs). If a node receives an
INITSYNC packet that contains less than 2 f + 1 time
value, the node appends its time value to an empty time
value field of the INITSYNC packet and rebroadcasts the
INITSYNC packet. However, since time elapses during
this action, the node must also add the elapsed time to
the previously recorded time values before rebroadcast-

U. JANG ET AL. 742
ing the INITSYNC packet. Once an INITSYNC with 2 f
+ 1 values is received, a SYNC packet, which only re-
quires only time value field, is sent out with the median
value. If a node receives two SYNC packets with differ-
ent timestamps, the larger value is chosen as the unique
reference and used to form subsequent SYNC packets.
Eventually, all nodes will receive a SYNC packet having
the unique reference time value. Then the local time of
each node can be adjusted using Equation (3) and the
timestamp of the reference node.
Besides the two main techniques discussed above (the
use of two different synchronization intervals and max-
of-median reference time selection), several other meth-
ods are used to enhance the performance of the FFTS
algorithm. When creating the timestamps to be included
in INITSYNC and SYNC packets, the timestamps are
created immediately before the packets are transmitted at
the Medium Access Control (MAC) layer of the software.
Such MAC-level timestamps [2,3] result in highly accu-
rate communication delay estimates since the highly
variable channel access delays are not included in the
communication delay estimates. Also, before each INITS-
YNC or SYNC packet is transmitted, a random backoff
delay is used. If an INITSYNC or SYNC packet is re-
ceived before the random backoff delay expires, the
random backoff is canceled and the received packet is
processed first. This is a method that is commonly used
in wireless networks with independently operating nodes
since this reduces packet collisions and permits coordi-
nated behavior using independently operating nodes. For
details on the implementation of the FFTS algorithm as
described above, the reader is referred to the pseudocode
description given in Figure 1. This pseudocode shows
the procedure to be executed by each node in the WSN
N.
4. Analysis
Let us first form an analysis of the FFTS algorithm for
one-hop time synchronization and then extend that
analysis to the general multi-hop case. In FFTS, time
synchronization is performed by adjusting the local timer
frequency (fadj) and the local timer offset (toffset) (refer to
Section 2) based on the timestamp in a SYNC packet.
This is done periodically with period T (T = P1 or P2).
Thus, differences in the global time maintained by two
nodes result from changes in the drift rates of the two
nodes over the time period T. In [1], Elson et al. showed,
based on analysis and experiments, that the differences in
the times when two nodes receive a packet broadcast
over a wireless medium follows a Gaussian distribution
with zero mean and σ standard deviation. Thus, for a
Algorithm: FFTS
Repeat for each node si in N:
1: If iter < K
2: Wait for P1;
3: else
4: Wait for P2;
5: iter ← iter + 1;
6: Wait for a random backoff delay;
7: If a INITSYNC is received during back-off
8: If timestamps in the INITSYNC < 2 f + 1
9: Append tvi(t) to the INITSYNC;
10: Adjust all timestamps in INITSYNC to
account for time elapsed thus far in node si;
11: Broadcast updated INITSYNC;
12: Else /* 2 f + 1 timestamp values present */
13: Select median timestamp value;
14: Broadcast SYNC packet with median value;
15: Else if a SYNC (with reference r) is received at time tvi(t)
16: If the SYNC is the first SYNC in this period or tvr(t) > tvref(t)
/* max-of-median */
17: ref ← r;
18: fadj = Drift_Adjust(tvi(t), tvr(t));
19: Broadcast updated SYNC;
20: Else
21: Drop the SYNC;
22: Else /* no packet is received during backoff */
23: Send INITSYNC with tvi(t);
Figure 1. FFTS algorithm.
Procedure: Drift_Adjust
Input: receive time tvi(t), send time tvr(t)
Output: adjusted drift-rate
1: If tvr(t) is the first received time value for r
2: t1_r ← tvr(t);
3: toffset ← tvi(t);
4: return 0;
5: Else
6: return 1_
()
()
rr
i offset
tv tt
tv tt

;
Figure 2. Drift_Adjust procedure.
one-hop network, we have the following useful theorem.
Theorem 1: Given a maximum change in timer drift-
rate of ρ', the maximum synchronization error δ among
non-faulty nodes in a one-hop network is given by the
following Gaussian distribution.
))'1(2,'2(~ 2  TN
Proof: The exact resynchronization (drift-rate adjust-
ment) periods observed by different non-faulty nodes in
a one- hop network are T plus or minus ti, where ti is a
term determined by INITSYNC packet exchange times,
random back-off times, CPU processing times and varia-
tions in SYNC packet reception times. Of these compo-
nents in ti, FFTS compensates for all measurable delays
incurred (and appends the corresponding drift-rate-
adjusted timestamp to the SYNC packet) before a SYNC
packet is sent. Thus, since variations in packet reception
times are not compensated in FFTS, the resynchroniza-
tion periods observed by non-faulty nodes follow a
Gaussian distribution with mean T and variance σ2. Let s1

U. JANG ET AL. 743
be the node that experiences the largest positive change
in timer drift during one resynchronization period. Then,
after one period, s1 will have a synchronization error
described by [11]. Likewise, if
s2 is the node that experiences the largest negative chan-
ge in timer drift during one period, s2’s synchronization
error will be 22
2
))'1(,'(~ 2
111
 TNX
~( ',(1'XN T2 ))


))'' 2
21
 

21XX 
2(,)''((   TN
. Thus, since
s1 and s2 are independent, will also be a Gaus-
sian distribution 21[11].
Substituting the maximum change in timer drift ρ' for
both ρ'1 and ρ'2, the theorem follows.
Let us now extend the above theorem to a multi-hop
network. In [1], Elson et al. showed that the standard
deviation of inter-receiver phase offsets increases by a
factor of m over the one-hop standard deviation,
given a hop-distance of m. Thus, the following corollary
is also true.
Corollary 1: Given an m-hop network, the maximum
synchronization error δ is given by the following Gaus-
sian distribution.
))'1(2,'2(~2  mTN
Corollary 1 can be used to derive the resynchroniza-
tion interval T = P2 to be used to achieve a specific level
of global time precision. A typical large value for ρ that
we observed in experiments with MICAz WSN devices
was around 100 μs/s. However, the maximum change in
the drift rate (ρ') that we observed in our experiments
(refer to Figure 3) was around 0.16 μs/s. The standard
deviation σ of the differences in packet delivery times
was observed to be around 4.65 μs. Assuming a maximum
permitted change in drift-rate, for non-faulty nodes, of
0.15 μs/s and m = 5, the resynchronization period re-
quired for δ = 50 μs (with 99% probability) was found to
be T = 52.5 seconds. If δ = 55 μs, T = 69.2 seconds, and
if δ = 60 μs, T = 85.8 seconds (both with 99% probability).
5. Experimental Results
In order to evaluate the proposed algorithm, experiments
were conducted using 13 MICAz (Berkeley “mote”) WSN
devices. MICAz uses an 8-bit ATmega128 microproces-
sor, a 7.3728 MHz clock and a CC2420 ZigBee radio. In
the first set of experiments, shown in Figure 3, one
MICAz device was used as a reference node, and the
drift-rate changes of the timers used in the other 12 no-
des were measured with respect to the reference node.
The most severe drift rate change observed was appro-
ximately 0.16 μs/s. The next most severe drift rate ob-
served was about 0.12 μs/s. Depending on the require-
ments of the application, the nonfaulty timer drift-rate
change threshold could be set to a value such as ρ' = 0.15
μs/s (to tolerate 0.16 μs/s) or ρ' = 0.1 μs/s (to tolerate 0.16
μs/s and 0.12 μs/s).
Figure 3. The drift-rate changes of 12 nodes. Black solid lines
represent two nodes that have the most severe (ID2) and next
most severe (ID3) drift-rate change and dotted gray lines
represent the other nodes.
In the second set of experiments, the fault-tolerance
characteristics of the FFTS algorithm were compared
with the FTSP algorithm in a 12-node one-hop network.
In this case, since the faults being tolerated are timer
faults (timers with widely varying drift-rate changes),
fault-tolerance implies a smaller drift away from the ref-
erence time value after a synchronization operation.
FTSP was used for comparison purposes because it used
a similar system model and had the best time synchroni-
zation performance of the previously proposed methods
[3]. Since FTSP uses an arbitrary fixed node as its refer-
ence node, we experimented with several different fixed
nodes as the reference node. FFTS was implemented
with f = 1. The reference node used by FFTS changed
several times during these experiments.
Experiments are conducted for FFTS and FTSP with
different choices of reference nodes. Each experiment
was repeated 100 times and average values recorded.
Figures 4 and 5 show the average and maximum, re-
spectively, time synchronization errors (pair-wise time
differences) observed in the five minutes after all nodes
were synchronized. The results for the FTSP algorithm
are summarized by showing the plots with the best, worst
and an arbitrary intermediate choice for the reference
node, determined in hindsight (labeled as FTSP_Best,
FTSP_Worst, and FTSP_Arbitrary respectively).The ex-
perimental results show that the use of FFTS results in
significantly lower synchronization error than FTSP.
This is a byproduct of the fact that faulty nodes are de-
fined to be those nodes with high drift-rate changes. As
shown in Figure 3, drift rates of the timers for all nodes
tend to change as time progresses. Thus, the FFTS policy
of continually selecting the node with the median drift
rate as the reference node tends to keep time values
tightly clustered together. The lower synchronization error

U. JANG ET AL. 744
Figure 4. Average pair-wise time offsets of 12-node during
5-minute period with various reference node selection
methods. Black solid line with black circles represents syn-
chronization error of FFTS. Solid line with squares, dotted
line with diamonds and dotted line with white circles rep-
resent FTSP_Worst, FTSP_Arbitrary and FTSP_Best, re-
spectively.
Figure 5. Maximum pair-wise time offsets of 12-node dur-
ing 5-minute period with various reference node selection
methods. Black solid line with black circles represents syn-
chronization error of FFTS. Solid line with squares, dotted
line with diamonds and dotted line with white circles rep-
resent FTSP_Worst, FTSP_Arbitrary and FTSP_Best, re-
spectively.
of FFTS implies that FFTS can achieve the same time
synchronization precision as FTSP while using a longer
resynchronization interval, thereby also reducing energy
usage.
In the third set of experiments, time synchronization
was performed using the FFTS algorithm in multi-hop
networks. The time synchronization precision achieved
was quantified by measuring the average and maximum
pair-wise offsets between every pair of nodes. The re-
sults of the multi-hop experiments are shown in Figure 6.
A 3 x 4 2-dimensional mesh network topology was used
and P1 and P2 were set to 2 seconds and 30 seconds,
respectively. K, the number of times when the short pe-
riod P1 was used, was set to 6 (one more than the net-
work diameter of a 3 x 4 mesh) and f was again set to 1.
The drift-rate change threshold was set to ρ' = 0.15 μs/s.
Using a target maximum time synchronization error of
45 μs, the resynchronization interval required was 35.8
seconds. However, during the course of our experiments,
it was discovered that operations within MICAz devices
could not be timed exactly due to interrupts and slow
CPU operation. Thus, a P2 value of 30 seconds was used.
There are several notable features about the results
shown in Figure 6. First, the precision of the time syn-
chronization achieved was about 20 μs throughout the
20-minute experiment. This was well within the δ value
predicted by Corollary 1. Second, initial synchronization
was completed in about K·P1 = 12 seconds. Third, resyn-
chronization of newly woken-up nodes was also very fast.
At time A (about 8.6 min), we turned off 4 nodes in the
third row of the 3 x 4 mesh. Then, when we turned on
these nodes again at time B (about 14 min), these nodes
were resynchronized within about 10 seconds. This fast
initial synchronization and resynchronization are the re-
sult of the short time period P1 used.
These results can be compared with the simulation re-
sults shown for FTSP in [3]. The degree of precision
achieved was about the same as the results obtained by
FTSP [3], which used a similar experimental platform
and had the best time synchronization results among the
previously proposed methods. However, FFTS has the
additional benefit of a quantified level of fault-tolerance.
In addition, resynchronization (after being turned off and
on) was very slow in FTSP (around 6 minutes in one set
of experiments [3]) whereas it is much faster (on the order
Figure 6. Average and maximum pair-wise time offsets in a
3 x 4 2D mesh-type network. Solid line represents average
offset and dotted line represents maximum offset during 20
minutes.

U. JANG ET AL. 745
of a few seconds) with FFTS.
6. Conclusions
This paper presents a system model and a new time syn-
chronization algorithm, termed Fast Fault-tolerant Time
Synchronization (FFTS), based on this model. Analysis
is used to quantify the resynchronization interval required
for a desired level of time synchronization precision and
the protocol to be used to achieve a desired level of fault-
tolerance. Experimental results are used to show that, in
terms of the level of time precision achieved, the pro-
posed algorithm works as well as the best previously pro-
posed algorithms. The FFTS algorithm, however, works
in a completely decentralized manner, thereby increasing
its fault-tolerance and adaptability to changing network
conditions, is able to tolerate faulty nodes (nodes with
faulty timers) and achieves extremely fast resynchroniza-
tion of nodes that wake up from suspended mode.
7
. References
[1] J. E. Elson, L. Girod and D. Estrin, “Fine-Grained Net-
work Time Synchronization Using Reference Broadcasts,”
The 5th Symposium on Operating Systems Design and
Implementation, Vol. 36, No. Winter 2002, 2002, pp. 147-
163.
[2] S. Ganeriwal, R. Kumar and M. B. Srivastava, “Timing-
Sync Protocol for Sensor Networks,” Proceeding of the
1st International Conference on Embedded Networked
Sensor System, Los Angeles, 2003, pp. 138-149.
[3] M. Maroti, B. Kusy, G. Simon and A. Ledeczi, “The Flood-
ing Time Synchronization Protocol,” Proceeding of the
2nd International Conference on Embedded Networked
Sensor Systems, Baltimore, 2004, pp. 39-49.
[4] P. N. K. Sun and C. Wang, “Fault-Tolerant Cluster-Wise
Clock Synchronization for Wireless Sensor Networks,”
IEEE Transactions on Dependable and Secure Comput-
ing, Vol. 2, No. 3, 2005, pp. 177-189.
[5] S. Z. H. Song and G. Cao, “Attack-Resilient Time Syn-
chronization for Wireless Sensor Networks,” Proceeding
of the International Conference on Mobile Adhoc and
Sensor Systems, Washington D.C., 2005, pp. 765–772.
[6] S. Hwang and Y. Baek, “Fault Tolerant Time Synchroni-
zation for Wireless Sensor Networks,” Lecture Note in
Computer Science, Vol. 3894, 2006, pp. 480-493.
[7] P. N. K. Sun and C. Wang, “Secure and Resilient Clock
Synchronization in Wireless Sensor Networks,” IEEE
Transactions on Selected Areas in Communications, Vol.
24, No. 2, 2006, pp. 395-408.
[8] Q. Li and D. Rus, “Global Clock Synchronization in Sen-
sor Networks,” IEEE Transactions on Computers, Vol.
55, No. 2, 2006, pp. 214-226.
[9] D. Mills, “Internet Time Synchronization: The Network
Time Protocol,” IEEE Transactions on Communications,
Vol. 39, No. 10, 1991, pp. 1482-1493.
[10] P. Ramathan, K. G. Shin and R. W. Butler, “Fault-Toler-
ant Clock Synchronization in Distributed Systems,” Com-
puter, Vol. 23, No. 10, 1990, pp. 33-42.
[11] A. Papoulis and S. U. Pillai, “Probability, Random Vari-
ables and Stochastic Processes,” McGraw-Hill, New York,
2002.