Time Synchronization for Wireless Sensor Networks - Adaptive Signal Processing in Wireless Communications - page 395

round-trip delay to their neighbors. For nodes that are not diffused leaders, if they only
receive a message from one diffused leader node (e.g., node D in Figure 13.7 ), they just set
their clock according to the time stamp they received. For the nodes that have received
more than one time-stamped message originating from different diffused leader nodes
(e.g., node E in Figure 13.7), they will use the standard deviations as weightings (the
smaller the deviation, the larger the weighting) to combine the clock values and set their
clocks according to the result.
The purpose of the third phase is to allow the sensor nodes to evaluate the stability of
their local clock. First, the elected master nodes broadcast a number of time-stamped
messages. The neighbor nodes receiving these messages calculate the two-sample Allan
variance [32] of the local clock from the clock of the master nodes and send back these
calculated Allan variances to the master nodes. Then the master nodes compute the
average of all the Allan variances they received and send the result back to their neigh-
bor nodes. By this procedure, all the neighbor nodes can evaluate the quality of their
clocks with respect to those of their neighbors by comparing their calculated Allan vari-
ance with the average value. The above procedure is repeated, but with the elected dif-
fused leader nodes broadcasting the time-stamped messages.

13.4.2.7 Synchronous and Asynchronous Diffusion Algorithms
In [33], two diffusion algorithms are proposed. The first one is called rate-based synchro-
nous diffusion algorithm. The idea behind this algorithm is that in order for a network
to achieve an equilibrium time, the clock at node i , denoted as c i , should be adjusted
according to the differences between its clock and its neighbors' clocks (assuming node i
has exchanged clock readings with its neighbors). That is, the clock at node i should be
set to

∑ (

c − r cc − ),

i

ji ij

i j

≠

where r ij > 0 is the diffusion rate, r ij = 0 if node i and node j cannot directly communicate,
and the condition

∑ ≤1

ji i r ≠

is enforced. The above algorithm can also be formulated using matrix notation. For a
group of n sensor nodes, let c t be the vector of length n containing the clock readings of
all the sensor nodes at time t . The synchronous diffusion algorithm adjusts the clocks of
different nodes using c t +1 = Rc t , where

 

r 


  


r r


 
 


 
 
   

11 12 1 n

r r r

21 22 2 n

r = (13. 35)

   

r r r

 n 1 nn 

n 2