A testbed validated simple time synchronization protocol for clustered wireless sensor networks for IoT

2.1. Background

In a WSN, each node keeps its own local time using cheap crystal oscillators which do not have a very precise clock tick rate. However, we cannot use high-precision crystal oscillator on every node as it increases the cost of the network tremendously. Further climatic conditions like temperature, humidity, etc. and aging of the crystals affects the accuracy of the local time at these nodes [9]. Therefore it is very essential to synchronize these nodes to a level of accuracy required by the application. Some industrial, health and automotive applications require a micro-second accuracy time synchronizationprotocol [1].

Time synchronization in WSN is particularly challenging as the nodes are deployed in harsh environments like industrial plants [17], volcanoes [11], etc. They are deployed for unattended operation targeted to work with minimal or no maintenance, generally for a few months to a couple of years. Thus the synchronization protocol must be robust to node failures and must provide synchronization of required accuracy-level. Also, since a WSN is an ad-hoc network which involves joining and leaving of nodes in a dynamic manner, the TSP should be scalable with the increasing network size without significant degradation in its performance. Also since a WSN is largely battery operated, the TSP should be energy efficient. We say a TSP is energy efficient if it requires the least number of packets for achieving the synchronization and/or requires infrequent resynchronizations. Further, WSNs are often used in critical applications like health monitoring, surveillance, etc. which require immediate reporting of emergency events. Therefore the TSP protocol must be immediate and thus must be computationally efficient. A detailed discussion about the characteristics and requirements of a TSP in WSNs can be foundin [9].

As stated earlier, it is not possible for all the nodes in a WSN to be equipped with either a GPS device or high accuracy crystal oscillator. Thus each network typically consists of either one or few nodes called the anchor or master nodes which provide the time reference for synchronization of all other nodes in the network which are involved in the synchronization process. These anchor nodes are either equipped with a GPS device or they simply provide the reference for the local clock of the network. All other non-anchor nodes determine their local clocks with respect to these anchor nodes. These non-anchor nodes are called agent nodes [4, 5].

Time synchronization typically involves the exchange of packets between the anchor nodes and the agent nodes periodically. The period of such exchange depends on the level of synchronization accuracy required, the efficiency of the TSP, capabilities of the WSN nodes, etc. As stated above, it is desired that this period is as large as possible for the energy efficiency of the TSP and for prolonging the lifetime of the WSN nodes. However, various dynamic factors in a WSN like nondeterministic network access time, processor load on the WSN node, propagation time etc. cause time delays in the delivery of the packet to the receiver after it is generated at the sender. These delays like send time, access time, propagation time, reception time, receive time, etc. become a source of significant error in time synchronization. They have been elaborately discussed in [9, 25]. Of these, send time, receive time, access time and interrupt handling times are non-deterministic in nature while transmission and reception times and propagation delays are deterministic [25].

Having discussed the background of TSPs in WSN, we describe the related work in the next subsection.

2.2. Related work and problem addressed

As stated before, the focus of this work is a WSN with cluster-based topology. This kind of topology is extremely energy efficient, particularly in route formation, data fusion, etc. [21, 31] and these functionalities/applications are most common parts of a generic WSN. Thus we chose to focus our TSP for a clustered WSN. In a cluster-based topology, a few nodes are grouped together to form clusters. Each cluster has a cluster-head (CH) and other nodes are the cluster members (CMs).

TSPs for clustered WSN have been reported by L-SYNC [21], SLTP [29] and PC-Avg [23]. In PC-Avg, the CH collects information about the local time of its CMs, calculates its average and sends this average to the CMs. PC-Avg shows very poor synchronization accuracy and does not account for the previously mentioned non-deterministic and deterministic delays during packet transmission and reception. Also, it requires frequent synchronizations which undesirably increases the packet traffic in the network and thus decreases the lifetime of the nodes [29].

SLTP [29] and L-SYNC [21] synchronize the CMs to their respective CH. They use the regression-based scheme to improve the synchronization accuracy. SLTP and L-SYNC differ from each other in the way form the clusters. Both SLTP and L-SYNC have poor synchronization accuracy of the order of milliseconds, which is not sufficient for many applications. Also, they do not account for non-deterministic and deterministic delays in the packet transmission.

Recent works like CCTS [15] and CMTS [33] use consensus-based schemes to achieve synchronization. They perform an intra-cluster synchronization first which is followed by an inter-cluster synchronization to converge the virtual clocks on the nodes to a consensus clock. However, CCTS and CMTS use a large number of iterations to achieve convergence. Thus, they are not practically suitable for energy-constrained WSN nodes and thus we have not compared our protocol with CCTS and CMTS. Also, CCTS does not consider the non-deterministic delay in packet transmissions. It writes-off these delays by saying that MAC-layer timestamping will take care of these delays. But that is not true in reality [25].

Importantly, the performance of CMTS, CCTS, SLTP, L-SYNC, and PC-Avg have only been demonstrated on simulators. Their performance on a real WSN testbed and their suitability for WSNs is thus questionable. Simulator-based works cannot give a complete picture of the performance of a TSP as they make many assumptions at a high level of abstraction, they do not consider packet loss and its effect on synchronization accuracy [6]. Another aspect that the works on TSPs lack are that they do not do a performance analysis under different LOS conditions. The performance of a TSP is affected by the fact whether the communicating WSN nodes are in LOS condition or in NLOS condition. Thus, as the conditions vary, the results may vary. We need to know the degree of efficiency of a TSP in a given condition. This would also help us choose an appropriate TSP for a given scenario. We, therefore, address the above issues in our TSP called H-SATS that is presented in this paper. We discuss the methodology of H-SATS in the next section.

OPEN IN VIEWER

Fig.1

A typical network considered.

3.1. Clock model and mathematical basis

A typical network having a cluster based topology considered in H-SATS is shown in Fig. 1. A Base-Station (BS) is connected to the internet. All the cluster heads are connected to the BS either directly or in a hierarchical manner. A cluster consists of a cluster head and cluster members. Each cluster member communicates only to its CH. The CH nodes are chosen a priori on the basis of their hardware capabilities like superior computation capacity compared to a CM, availability of continuous power supply or greater battery energy availability, etc. We consider a network where nodes are stationary and assume that the nodes are connected via symmetric links for the sake of simplicity. A CM which can hear from more than one CH is called a gateway node. The network is divided into clusters using the cluster formation technique discussed in SLTP [29] or L-SYNC [21]. We can incorporate the feature by which all the nodes in the cluster become CH in turns so that no single node is burdened with CH role which could lead to draining of energy resources on that node.

We consider a WSN network consisting of n nodes defined by the set N . Further, we have u cluster heads in this network defined by the set H ≜ { h 1 , h 2 , … h } and there are v cluster members defined by the set ɛ ≜ {e₁, e₂, …, e _v }. The network consists of only nodes which are either CHs or CMs and there is no node which is both a CH and CM simultaneously. We define a function f _CM  (x, y) which tells whether a node y is a CM of a CH x or not, i.e.

f CM ( x , y ) = { 1 if node y is a CM of the CH x 0 otherwise .(1)

We also define a function g _CH  (x, y), which tells whether a CH node y is a child of the BS or CH node x or not, i.e.

g CH ( x , y ) = { 1 if CH node y is a child of x 0 otherwise .(2)

The clock model considered for this work is the skew-offset model [9, 18]. This model relates the local time of a node with the global time using the following equation. C i ( t ) = α i t + β i ,(3) where t is the global time or the time of the reference clock, α _i is the skew and β _i is the offset of the local clock of the ith node with respect to the reference clock. Skew refers to the frequency or the rate of the local clock with respect to the reference clock and offset is the difference between the local clock and reference clock at time t. Ideally α _i  = 1 and β _i  = 0 when the local clock is fully synchronized to the reference clock. However, due to the clock crystal’s imperfections as discussed before, in reality, these ideal conditions will not be true. Further, the skew is not constant over time, i.e., d α i dt ≠ 0 is not strictly true. But skew can be approximated to a fixed value as the change of skew with time is very slow [9, 22].

H-SATS is a simple synchronization scheme which was presented in a preliminary form in [10]. In [10], all the CMs are synchronized to its CH only. The present work H-SATS extends [10] by achieving network-wide synchronization which is very helpful for a hierarchical WSN used in an IoT network. Further, this work also does a performance analysis of H-SATS for different LOS conditions, i.e., in a complete LOS condition where all the nodes in a cluster are LOS and a mixed-LOS condition where some CMs are LOS with their CH while other CMs are NLOS with their CH. A detailed explanation of the cluster-tree formation, cluster-formation phase, and the mathematical basis of H-SATS is also presented in this work. The CH tree formation phase and the cluster formation phase are described in the following subsection.

We refer to Fig. 1 to explain different phases of H-SATS. The BS initiates the CH tree formation phase by broadcasting Hello_packet. The BS is at level-0 and this level-information is also present in this Hello_packet of the BS. The CHs h₁, h₂, and h₃ which are able to hear these packets assign themselves a level-1. These CHs, in turn, broadcast Hello_packet with its level information and also its id denoted as CH_ID. The CHs which hear these packets assign themselves as level-2 and also note the CH_ID of their parent CH. In the example that we are referring to in Fig. 1, h₄ and h₅ hear the Hello_packet sent by h₁ and they become the children of h₁. If a CH hears the Hello_packet of more than one parent CH, it chooses the CH whose packet is received with greater signal strength as its parent CH. In this way, CH tree is formed. Note that this CH tree formation is performed only once as the CHs are fixed and are stationary.

OPEN IN VIEWER

Fig.2

Two-way message exchange between parent CH head node and child CH node along the time axis.

The cluster tree formation phase is followed by the cluster formation phase. The CHs begin this phase by broadcasting the CM_joining packet. This packet also contains the CH_ID of the broadcasting CH. All the nodes (which are not CHs), which hear this CM_joining packet from a CH, join the cluster of that particular CH. In this case, the nodes e₁, e₂, e₃, e₄ and e₅ hear the CM_joining packet of h₁ and join the Cluster 1. A node which hears the CM_joining packets of multiple CHs joins the cluster of more than one CH. For instance, the node e₄ hears the CM_joining packets of h₁ and h₂ and thus joins both Cluster 1 and Cluster 2. Such a node becomes a cluster gateway node as it is a part of more than one cluster. Since this gateway node has more than one CH, it records the CH_IDs of all its CHs. It sends this list of its CHs to all its CHs. So e₄ sends the list of its CHs to h₁ and h₂ which will help h₁ and h₂ to communicate with each other through e₄. After the cluster formation phase is complete, when a new node joins the network, it can search for a CH by broadcasting a CH_initial packet. Any CH which hears this packet and is ready to join this newly joining node into its cluster, responds to this packet. If the new node receives a response from more than one CH, it joins more than one cluster and it becomes a gateway node. This phase is followed by the synchronization phase.

The level-1 CHs are first synchronized to the BS. In Fig. 1, the BS synchronizes h₁ (i.e.CH of cluster 1), h₂ and h₃. These CHs, in turn, synchronize their children CHs i.e. in this case h₁ synchronizes h₄ and h₅. Once the CHs are synchronized, the CHs synchronize the CMs within their clusters. For instance, h₁ synchronizes its own CMs i.e. e₁, e₂, e₃, e₄ and e₅. The method by which a CH is synchronized with its parent CH is the same as the method by which a CM is synchronized with its CH. We first describe the procedure for synchronizing a CH with its parent. The parent could be a CH or the BS itself. In H-SATS each child CH is synchronized to its parent CH. Thus the clock model in Equation (3) can be written as C ih ( t ) = α ih C h + β ih ,(4) where C _ih is the local time of the child CH, C _h is the local clock of the parent CH, β _ih is the relative offset and α _ih is the relative skew of the ith child CH with respect to the parent CH.

Synchronization in H-SATS is performed using a two-way message exchange between the parent CH and the child CH as represented in Fig. 2. The packets are time stamped by each node as per its local clock on a packet transmission and reception. The first packet was sent from the parent CH at T_1,1 as per its local clock. This packet is received by the child CH at T_2,1 as per its local clock. The child CH acknowledges this packet by sending another packet to the parent CH at T_3,1 as per child CH’s local clock. The parent CH receives this acknowledgment packet at T_4,1 as per its local clock. The packet exchanged between a child CH and its parent CH will contain the time stamps of transmission and reception, i.e., T_1,1, T_2,1, T_3,1, and T_4,1. MAC-layer timestamping as used in [25, 28] can be employed here to reduce the send time, access time and reception time delays in the transmission. Thus, when the acknowledgment packet is received at the parent CH, it gets all the four local time stamps of one complete two-way exchange. A total of P such two-way exchanges are performed between a parent CH and one child CH. Using Equation (4) we can relate the time stamps of an mth two-way exchange (where 1 ≤ m ≤ P) as follows

T 2 , m = α ih ( T 1 , m + ν f + ψ m ) + β ih(5)T 3 , m = α ih ( T 4 , m - ν f - γ m ) + β ih ,(6) where ν _f represents the deterministic delays, ψ _m and γ _m represent the non-deterministic delays in the packet exchange. Note that these delays are measured with respect to the parent CH’s local clock.The above Equations (5 and 6) can be written as follows T 2 , m = α ih T 1 , m + β ih + α ih ( ν f + ψ m )(7)T 3 , m = α ih T 4 , m + β ih - α ih ( ν f + γ m ) .(8)

We observe from Equation (7) that as α _ih , ν _f and ψ _m are always positive, T_2,m lies above the line α _ih T_1,m + β _ih . Similarly from Equation (8) we see that since α _ih , ν _f and γ _m are always positive, T_3,m lies below the line α _ih T_4,m + β _ih . We know that α _ih is the rate of child CH’s clock with respect to parent CH’s clock. So if we plot the timestamps of child CH (on the y-axis) with respect to parent CH’s timestamps, α _ih is the slope and β _ih is the y-intercept. So very good estimate of the α _ih and β _ih can be obtained by fitting a line for these points (T_2,m, T_1,m) and (T_3,m, T_4,m) where 1 ≤ m ≤ P. An approximate yet a good estimate for this fit-line can be obtained by taking two points M1 and M2 such that M 1 = { 0.5 * ( T 4 , l + T 1 , l ) , 0.5 * ( T 2 , l + T 3 , l ) }(9)M 2 = { 0.5 * ( T 4 , r + T 1 , r ) , 0.5 * ( T 2 , r + T 3 , r ) }(10) where l = arg min 1 ≤ m ≤ P ( T 4 , m - T 1 , m ) and r = arg min 1 ≤ m ≤ P , m ≠ l (T_4,m - T_1,m).

From Equations (9 and 10), we can note that M1 refers to the two-way exchange with the least deterministic and non-deterministic delays while M2 refers to the next least. Thus when a line is drawn through M1 and M2, the slope of this line gives α _ih and the intercept of it gives β _ih . Thus we get α ih = ( T 2 , l + T 3 , l ) - ( T 2 , r + T 3 , r ) ( T 4 , l + T 1 , l ) - ( T 4 , r + T 1 , r )(11)β ih = ( T 2 , l + T 3 , l ) 2 - α ih ( T 4 , l + T 1 , l ) 2(12)

The above mentioned simple method to estimate the relative skew and offset has an accuracy comparable to the much complicated and computationally intensive maximum-likelihood estimate [26]. Note that [26] just gives the basis for this simple synchronization scheme and it is a simulation-based work. The current work improvises on this scheme by applying it for clustered WSN and demonstrates its efficacy on a testbed. Further, we have also employed the cluster tree formation, cluster formation phases and a schedule for message exchanges to achieve a network-wide synchronization. Once a CH is synchronized, it initiates the synchronization with its CMs. The CMs of a cluster are synchronized to their CH in the same method as a child CH is synchronized to the parent CH. Each CM performs Q two-way exchanges with its CH and then the relative offset and relative skew of a CM with respect to the CH is calculated.

Thus, after the synchronization phase, the CMs are synchronized to their CH and the CHs are synchronized to the BS. Thus, any sensor data that is recorded at a CM can be easily timestamped according to the internet time by the BS which is synchronized to the internet clock and also to a CM in the WSN. The algorithm of the synchronization phase of H-SATS is presented in Algorithm 1. The important notations used in this paper are summarized in Table 1.

In this subsection, H-SATS is compared with a regression-based synchronization scheme. The regression-based method has been used both in SLTP [29] and L-SYNC [21]. Both L-SYNC and SLTP have been shown to be scalable time synchronization algorithms for clustered WSN. As stated before, SLTP and L-SYNC differ from each other in the cluster formation method while both use linear regression in the synchronization phase. Linear regression-based synchronization method has very high computational complexity and thus is more expensive than H-SATS. The number of multiplications, as well as additions to be performed for time synchronization in the linear regression method, are much higher as compared to those in H-SATS. The computational complexities for synchronization between two nodes (for instance CH and its CM) are compared in Table 2. In this table, Q represents the two-way exchanges performed between the two nodes which are trying to get synchronized with each other (like a CM with its CH). H-SATS requires one subtraction (which can be seen as an addition) to calculate a two-way exchange’s duration which is computed by (T_4,m - T_1,m). Thus Q two-way exchanges require Q addition (or subtraction) operations. Further, 2 (Q - 2) subtractions are required for comparison operations to determine the two-way exchange with minimum delays. Further, 4 additions are required in Equations (9 and 10). It requires a total of 7 multiplications, 4 of which are required in Equations (9 and 10) and the rest of the 3 multiplications are required in Equation (12). The size of the timestamp variable in the microcontroller of a WSN node needs to be increased to 32-bits to maintain a clock of microsecond resolution and also to measure a considerable time duration before the clock overflows. When computationally intensive 32-bit multiplications are involved, a reduction in the number of multiplications to an order of 1 gives H-SATS a significant computational edge over regression-based method. WSN processors like MSP430 of TelosB WSN nodes may find it difficult to support the intense computations involved in the regression-based method. Powerful WSN nodes like NXP’s JN5179 [16] or Lotus [19], can execute such intensive computations as they are equipped with 32-bit processors. However, they do so at the cost of consuming higher processor time and power which is generally not desirable for energy constrained WSN nodes. Also, the use of such expensive powerful nodes inhibits their large-scale deployment in WSNs. Thus, H-SATS, which is less computationally intensive, is a suitable TSP for energy-constrained WSN nodes.

4.1. LOS environment

The WSN nodes were deployed in an open field as shown in Fig. 3. Each cluster was deployed in an area of 5 sq. meters. The inter-cluster distance was less than 1 meter, i.e., it is a very dense deployment. The experiment was initially performed with just one cluster turned on. Other clusters were turned on one-by-one gradually so as to generate the traffic which will help us analyze the performance of these algorithms in dense traffic conditions. A total of 30 WSN nodes, i.e., 6 clusters were used in this experiment. The CHs were first synchronized to the BS. Then the synchronization packets were exchanged between a CH and its CMs. The CH unicast the synchronization packets to each CM one-by-one and the CM replied to them via a unicast communication. However, the traffic caused by the packet exchange in one cluster did cause packet drops in other clusters. A snapshot of a part of the network deployed can be seen in Fig. 3. The WSN nodes are encircled in red.

OPEN IN VIEWER

Fig.3

Picture showing part of the network deployed with WSN.

In this deployment, some of the nodes were placed inside a lab and the rest of the nodes were deployed in the gallery outside the lab (as shown in Fig. 4). The BS was inside the lab. The nodes in the gallery were separated from the nodes inside the lab by thick concrete walls. The CH of a cluster could communicate LOS with two of its CMs and other two CMs were in an NLOS position. These CMs in NLOS position with respect to their CH were separated by a thick concrete wall to provide a formidable obstacle for packet transmission. The experiment was performed with only one cluster turned on initially. The other clusters were turned on one-by-one to generate the traffic.

OPEN IN VIEWER

Fig.4

An indicative diagram depicting part of the deployment for mixed LOS (a mixture of LOS and NLOS) environment.

The methodology described in this subsection used to perform H-SATS and to compare it with the regression-based method is common to both environments mentioned previously. In H-SATS, as stated before, each CM is synchronized with its CH. In the current implementation, we employ a training phase to perform the synchronization and a testing phase to evaluate the performance of the TSP. The synchronization phase (i.e training phase) of H-SATS algorithm has been summarized in Algorithm 1. It is to be noted that the testing phase is not a part of the H-SATS algorithm as such. The training and testing phases are described below in detail.

4.3.1. Training phase

In this phase, each CH initiates two-way packet exchanges (described in section 3.1) with its parent CH (or the BS if the CH is level-1 CH). It performs P two-way exchanges with the parent CH (or BS) and it identifies the two-way exchanges with minimal and next minimal delays as shown in Equations (9 and 10). The relative offset and relative skew of the child CH with respect to the parent is calculated using Equations (11 and 12). This procedure is then repeated by all the CHs with all its CMs to synchronize the CMs to their respective CH. The only difference is each CH performs Q two-way exchanges with each of its CM one-by-one. In the current evaluations, P and Q values have been taken to be 17 the reason for which will be explained in the next section. Also, the timestamps of the two-way exchanges of all CHs with their CMs are forwarded to a PC which has the base-station (as shown in Fig. 5) connected to it. The calculations for H-SATS and regression method (i.e., to calculate the relative skew and offsets) are done on a PC in the current implementation. Figure 5 shows the base-station node connected to the PC on the left. The right side portion of the figure shows the zoomed portion of a part of the PC’s screen in which four timestamps collected for a single two-way exchange are encircled in red.

OPEN IN VIEWER

Fig.5

Base-station collecting the timestamps of the cluster and forwarding it to a PC. The right portion of the figure shows a zoomed out portion.