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

of nodes, which significantly reduces the overall energy consumption by decreasing the
number of required timing messages in synchronization. PBS requires a much smaller
number of timing messages than other existing protocols, such as RBS, TPSN, and FTSP,
and its benefits remarkably increase as the sensors are more densely deployed.
Let N rbS , N TPSN , N FTSP , and N PbS denote the numbers of required timing messages for
synchronization in RBS, TPSN, FTSP, and PBS, respectively. In TPSN, since every node
in the network is connected to its parent node (except the root node), there are L - 1
branches (edges) in a hierarchical tree, where L is the overall number of sensor nodes
[17]. For TPSN, 2 N timing messages are required in every pairwise synchronization,
hence N TPSN = 2 N ( L - 1). This result can be applied to other level-based SRS protocols
without loss of generality. For RBS, the reference node must broadcast the beacon packet
N times. Besides, every sensor node must send time readings upon receiving the broad-
cast beacons of all the other nodes in the network to compensate relative clock offsets
among each other [18]. hus, N rbS = N + L ( L - 1)/2, since the number of unique pairs in
the network is L ( L - 1)/2. In FTSP, each sensor node must send its timing messages once
upon receiving the timing messages from another sensor due to its flood-based com-
munication procedure [16]. Hence, the number of required timing messages in FTSP
becomes N FTSP = NL .
It is remarkable that the required numbers of timing messages for all the above-men-
tioned protocols are proportional to the number of sensors in the network L or its square
L 2 . However, PBS needs only 2 N timing messages in every synchronization period,
i.e., N PbS = 2 N , assuming all the nodes lie within a single broadcast neighborhood.
Hence, N PbS does not depend on the number of sensors in the network, which incurs
an enormous amount of energy savings. Moreover, this gain proportionally increases
with respect to the scale of the network. Consequently, the benefit of PBS over RBS,
TPSN, and FTSP is clear and huge in terms of energy savings with the cost of allocating
two super nodes in the network. In case there exist other nodes located outside of the
checked region in Figure 13.1 , likewise RBS, the network could be divided into a number
of separated groups (clusters), and they could be synchronized by additional pairwise
synchronizations among the super nodes in different groups, i.e., global synchroniza-
tion can be achieved by a sequence of pairwise synchronizations among the super nodes.
Here, diverse grouping and pair selection algorithms can be considered according to the
type of the network. For instance, assuming the level hierarchy of the network is estab-
lished, there are groups of parents and children nodes, where a group consists of a parent
and its children nodes. Here, every parent node can search the connectivity among its
children nodes to select the best synchronization pairs that maximize the number of
nodes performing ROS, i.e., minimizing the number of pairwise synchronizations. In
fact, no network-wide connection search is required in this case because of its limited
and known set of scanning nodes.
13.4.2.6 Time-Diffusion Synchronization Protocol (TDP)
TDP [32] is a protocol enabling the sensor network to reach an equilibrium time with
the clocks of individual sensors within a small time deviation from the equilibrium
time. The protocol can be understood as periodically applying three phases: (1) election
of master/diffused leader nodes, (2) time-diffusion procedure, and (3) peer evaluation