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

13.4.2 Network-Wide Synchronization
Until this point, we have only described the time synchronization between two neighboring
sensor nodes. In this section, we will discuss protocols for network-wide synchronization.
13.4.2.1 Extension of TPSN
In order to establish a global timescale for all the nodes in the sensor field based on
TPSN, [17] proposes to create a hierarchical structure (spanning tree) in the network
(named level discovery phase) before pairwise synchronization is performed between
adjacent levels (named synchronization phase). The level discovery phase consists of the
following steps:
1. Select a root node using an appropriate leader election algorithm and assign a 0
level to the root node.
2. The root node broadcasts a level discovery packet (LDP) containing the identity
and level of the packet.
3. Every node that receives an LDP assigns its level to a level greater (by one) than
that of the received packet and sends a new level discovery packet attaching its
own level (once being assigned a level, a node neglects future packets requesting
level discovery to avoid flooding congestion).
4. Repeat step 3 until every node in the network successfully assigns a level.
After the spanning tree is formed, the root node initiates the synchronization phase
by synchronizing all the nodes in level 1. Next, the nodes in level 1 synchronize with
the nodes in level 2, and so on, until all the nodes have been synchronized. Notice that
the synchronization error of a node with respect to the root node is a nondecreasing
function of the hop distance because the random signal errors over each hop add up.
A number of different searching algorithms can be considered in the construction of
the spanning tree. For instance, Van Greunen and Rabaey suggested some preliminary
ideas on constructing spanning trees with low depth in order to improve the accuracy
of synchronization [12].
13.4.2.2 Lightweight Time Synchronization (LTS)
Also based on two-way message exchanges, [12] proposes two network-wide synchroni-
zation protocols. The first one is called centralized multihop LTS, which is basically the
same protocol as the extension of TPSN discussed above. The other one is called distrib-
uted multihop LTS. This distributed LTS algorithm moves the resynchronization from
the root node to the nodes that need resynchronization. When a node A determines that
it needs to be resynchronized, it will send a resynchronization request to the root node.
In order for node A to resynchronize, all nodes along the routing path from the root
node to node A will be synchronized in a pairwise fashion.
13.4.2.3 Extension of RBS
The RBS protocol discussed in the above subsection can only synchronize a set of nodes
that lie within a single broadcast domain. In order to synchronize a large sensor network,