synchronization whenever it is necessary and the reference node is
available. However, SRP is not suitable for the WSNs where all sen-
sor nodes are required to get synchronized in a short period of time
since SRP can only synchronize two nodes at one execution.
In [18], RBS which is a time synchronization approach based on
RRP is proposed. It requires that each node in a cluster must calcu-
late time offset of every other node in the cluster. This would bring
large storage and calculation burden to the entire network, and
thus a considerable amount of energy would be wasted. Based on
RBS, RBIS [28] can be set up by using only commercial equipment
such as wireless access point (AP). This means that it permits inex-
pensive implementations to be developed easily and readily.
However, the approach can only synchronize the nodes within
the broadcast range of an AP and no multi-hop time synchroniza-
tion approach is presented. Also based on RBS, OPRBS [29] can be
used in environment with large number of nodes by managing
transmission power. Two lightweight synchronization algorithms
based on SRP were proposed in [17]: Tiny-Sync and Mini-Sync,
with the assumption that the frequency of each clock can be
approximately fixed. TPSN [22] and LTS [31] are similar approaches
to Tiny-Sync and Mini-Sync. However, all of them are not suitable
for densely connected network. In [23], an approach based on SRP
was proposed to achieve energy efficiency. First, a spanning tree of
all the nodes in the network is created. Then, it is divided into mul-
tiple sub-trees. Each sub-tree performs the sub-tree synchroniza-
tion algorithm. However, energy efficiency is at the sacrifice of
time synchronization accuracy. In [32], authors present an
approach that develops uncertainty-driven mechanism to adap-
tively adjust each clock calibration individually rather than peri-
odic synchronization. This effectively helps reducing network
traffic, and thus achieves energy efficiency. However, the approach
is unable to synchronize all the nodes in a short time. In [33],
authors propose an algorithm that aims at synchronizing sensor
nodes to a reference node while these nodes optimize the clock
skew between their neighboring nodes at the same time.
Although this can help reducing the frequency of time synchro-
nization by adjusting clock skew, the network topology has to be
pre-constructed. However, in many real applications sensor nodes
have to form network topology by themselves. In [34], TSync com-
bines both a push mechanism for accurate and low overhead global
time synchronization as well as a pull mechanism for on-demand
synchronization by individual sensor nodes. But the accuracy is
similar to that of the compared algorithms in [31].In[35], PBS is
similar to our approach on combining RRP and SRP, but no layering
algorithm is given.
2.2. Motivation
It takes a considerable amount of energy to execute many
extant WSNs time synchronization schemes such as [17,18,22–
24]. These approaches put a lot of emphasis on accuracy. In order
to reach minimum time error, numerous message exchanges are
needed. However, the highest-energy-consuming period during a
sensor node’s lifetime is the period of sending and receiving mes-
sages. Therefore, high accuracy is always at the sacrifice of huge
consumption of energy which is extremely limited and precious
in WSNs. As a result, the lifetime of the entire networks will
decrease sharply due to pursuit of high accuracy of time
synchronization.
The above circumstance further deteriorates in densely con-
nected WSNs. The messages transmitted through a WSNs’ channel
are in the form of broadcast which is received by all the sensor
nodes in the broadcast range. The denser a network is, the more
receiving processes will be among the recipients whenever a
broadcast is transmitted and thus the more energy cost will be.
In order to deal with the problems described above, we incorpo-
rate the RRP and SRP to present a novel energy-efficient time syn-
chronization approach, namely STETS. Our approach takes
advantage of the property of RRP, namely being able to synchro-
nize a large number of nodes at one time. This can help reducing
number of messages and thus energy. Also, by using SRP, STETS
successfully solves the problems brought by RRP, namely synchro-
nizing the unsynchronized nodes brought by RRP. Furthermore,
RRP completely eliminates the negative effect of SD while SRP
can offset the effect of SD,PD and RD by performing two-way mes-
sage exchange. Therefore, the time accuracy of our approach is also
satisfactory. In STETS, only a small number of nodes in WSNs have
the right to send information and each of these nodes only needs to
send a few messages in a single round of time synchronization.
Moreover, all the messages in our approach are in the form of
broadcast for the purpose of decreasing protocol overhead. Thus,
energy-efficiency can be ensured in STETS.
3. Model and strategy
3.1. Assumption
We assume that the sensor nodes have unique identifiers. Each
node is aware of the set of nodes with which it can directly com-
municate. These nodes are also termed as the neighboring nodes.
Moreover, we also assume that each node knows the distance to
each of its neighboring nodes. This can be achieved through vari-
ous distance estimation algorithms such as TOA (Time of Arrival)
[36], TDOA (Time Difference of Arrival) [37], and RSSI (Received
Signal Strength Indicator) [38].
3.2. Symbols and description
The symbols and description used in paper are listed in Table 1.
3.3. Node classification
The sensor nodes in the entire network of STETS are classified
into three categories, namely undefined node (UN), backbone node
(BN) and passive node (PN).
Undefined node (UN): the initial state of each node in WSNs.
These nodes will become either BN or PN during the time
synchronization.
Backbone node (BN): the nodes of this state form a spanning
tree structure in the network (Fig. 2). One certain BN on level
l (0 < l 6 n) can communicate with only one BN on level l 1
and the BN on level l synchronizes with the BN on level l 1
through SRP. In the spanning tree, every branch node or root
node has one or more child nodes. Not all the leave nodes are
distributed on the last level.
Table 1
Symbols and description.
Symbol Description
b
l;i
(l P 0; i P 0)
i-th BN on the l-th level
p
l;i;j
(l P 0; i P 0; j P 0)
j-th PN of i-th BN on the l-th level
B
l;i
The set of all the sensor nodes in the broadcast
domain of b
l;i
except for the BN itself
C
l;i
The set of all the PNs in the area in the charge of b
l;i
D
ðx; yÞ Measured time offset between node x and node y
r
ðx; yÞ Real time offset between node x and node y
Lðx; yÞ Local time error between node x and node y
GðxÞ Global time error of node x
T. Qiu et al. / Microprocessors and Microsystems 39 (2015) 1285–1295
1287