ABSTRACT

Time synchronization is one of the important aspects in wireless sensor networks. Time synchronization assures that all the sensor nodes in wireless sensor network have the same clock time. There are various applications such as seismic study, military applications, pollution monitoring where sensor nodes require synchronized time. Time synchronization is mandatory for many wireless sensor networks protocols such as MAC protocols and also important for TDMA scheduling for proper duty cycle coordination. Time synchronization is a stimulating problem in wireless sensor networks because each node has its own local clock which keeps on varying due to variation in the oscillator frequency. The oscillator frequency is time varying due to ambient conditions which leads to re-synchronization of nodes time and again. This re-synchronization process is energy consuming whereas energy is constraints in WSN. This paper proposes a novel cluster based time synchronization technique for wireless sensor networks in which cluster head rotation is based on minimum clock offset. Simulation results based on energy analysis of the proposed model demonstrate that proposed novel cluster based time synchronization technique reduces the energy consumption and also the synchronization error compared with other existing protocols.

Keywords:

Cluster, Offset, Delay, Time Synchronization

1. Introduction

Recent advancements in the electronic and communication technologies have resulted in the emergence of wireless sensor networks (WSNs). WSNs are composed of small size, low power and low cost wireless micro-sensors, known as Sensor Nodes (SNs) [1] [2] [3] . These SNs can be embedded in various objects in order to form intelligent multipurpose distributed systems. These SNs generally perform three major tasks i.e. sensing, data processing and communication [4] . SNs are capable of sensing various environmental conditions such as sound, temperature, humidity, strain, acidity pressure, vibration, motion or pollutants [5] [6] , etc.

Wireless Sensor Network (WSN) consists of large number of SNs deployed in unattended environment [7] . These SNs monitor objects in the sensing field and report the activities and events to sink. In order to establish correct logical order of the events, the data must be time stamped by the SNs. In WSN some applications such as military applications require accurate time of the event. Data fusion in WSN also demands time stamp of SNs to suppress the duplicate information of the SNs. Time is also important to implement the TDMA schedule in WSNs. Due to various challenges and constraints in WSNs, the clock synchronization protocols (NTP) [8] [9] designed by researchers for wired networks do not work in wireless sensor networks. In WSNs each node has its own local clock that may vary from the local clock of other nodes in the network which leads to clock offset. Higher clock offset degrade the WSNs performance and the information collected by the nodes may not provide the accurate timing of the event. Whereas time synchronization in WSNs is important for efficient duty cycling, location based monitoring, target/event tracking data fusion and network scheduling and routing.

Keeping in view the importance of time synchronization as well as the constraints of SNs, the objective of the proposed research is to develop time synchronization technique that helps to synchronize the SNs in an energy efficient manner. This paper proposes a novel cluster based time synchronization technique for wireless sensor networks to keep local clocks of all the SNs synchronized with global clock.

In wireless sensor networks, a lot of research [10] - [31] has already been carried out to design time synchronization protocols such as Reference Broadcast Synchronization (RBS) [11] , Romer synchronization [13] , TPSN (Timing Sync Protocols for Sensors Networks) [15] , Two-hop time synchronization protocol for sensor networks (TTS) [18] , Fast distributed multi-hop relative time synchronization protocol and estimators for wireless sensor networks [19] , Long term and large scale time synchronization in wireless sensor networks (2LTSP) [20] , and Average time synchronization in wireless sensor networks by pairwise messages (ATSP) [21] , Time synchronization protocol based on spanning tree [28] , Lightweight and Energy Efficient Time Synchronization (LEETS) Protocols [29] and Lightweight Fault-tolerant Time synchronization [30] . Some of these protocols synchronize the nodes internally by placing the nodes on common notion of time and some synchronize externally by using large number of messages to adjust the clocks of the sensor nodes with global clock.

The proposed novel cluster based time synchronization technique for wireless sensor networks to keep local clocks of all the SNs synchronized with global clock by using less number of messages. In the proposed technique initially the SNs are arranged in clusters by using energy efficient clustering algorithm (EECA) and then time synchronization is performed.

The rest of the paper is organized as follows. In Section 2 describes the proposed energy efficient clustering algorithm (EECA) for WSNs. Section 3 describes the proposed time synchronization algorithm and synchronization error estimation. Energy analysis is performed in Section 4. Section 5 contains simulation and analysis and finally we conclude the paper in Section 6.

2. Energy Efficient Clustering Algorithm

In this section, we describe our proposed protocol, called Energy Efficient Clustering Algorithm (EECA) for wireless sensor networks. The proposed technique has been segregated into different phases; creation of clusters to prolong the network lifetime, CH selection and cluster head rotation. EECA forms clusters before selecting cluster-head. Our proposed EECA works in three steps: (2.1) Cluster formation process, (2.2) Cluster head selection process and (2.3) Cluster head rotation process.

2.1. Cluster Formation Process

In EECA clustering process is initiated by the sink. Sink calculates the preliminary mean points by sensing field size, optimum number of clusters and average distance of the nodes from the center of the sensing field. After the deployment of SNs in sensing field, the sink initiates the clustering process by finding the

centroid of the sensing field by using the Equation (1) where and

where and is the size of the sensor field and is the area of

the sensing field.

(1)

When the value of centroid is calculated, sink node finds the average distance d between centroid and all the SNs by using the Equation (2). Where X_i and Y_i are the coordinates of the node SN_i.

(2)

Sink also computes the optimum number of clusters k using the Equation (3) [32] . The total number of nodes deployed in the sensing field is n, M is the side of square sensing field and is average distance to cluster heads from the base station. is energy coefficient of power amplifier stage of SN for free space energy dissipation model and is energy coefficient of power amplifier stage of SN for multipath energy dissipation model.

(3)

Once the values of centroid, d and k are calculated, sink calculates the value of the preliminary mean points where using Equation (4) and broadcasts the locations of preliminary mean points to the SNs.

(4)

The objective of finding the preliminary mean points is to significantly reduce the iteration time of cluster formation. Figure 1 shows the preliminary mean points in 100 m × 100 m sensing filed area with 50 sensor nodes.

When the SNs receive the sink message of preliminary mean points, each node find its minimum distance from preliminary mean points by using the Equation (5) and retain the minimum distance.

(5)

is the coordinate of SN_i, is the cluster j and is the coordinate of preliminary mean points. The minimum distance between preliminary mean points and SNs helps to form uniform distributed clusters. Nodes join the cluster on the minimum distance to the preliminary mean points using the Equation (6). In each round SNs check their distance with all nearby clusters and node nearest to the preliminary mean point in the r^th round joins the cluster j.

(6)

is the Cluster j in r^th round. After tagging all the nodes with different clusters new mean points are created by using the Equation (7).

(7)

is the number of SNs in the cluster j. Figure 2 shows the new mean points.

The process of finding the new mean points is iterative till the new mean points stop moving. As long as the preliminary mean points keep on changing the nodes are re-arranged again and again as per the Equation (6) and (7). The cluster formation process is complete when the new mean points are fixed and nodes join the final mean points with minimum distance. Figure 3 shows the flowchart of clustering process.

2.2. Cluster Head Selection

The clustering algorithm divides the whole network into different clusters. The next step is to elect CH within each cluster. Each node within the cluster calculates its distance from the cluster by using the Equation (8). Where X_i is the coordinates of the SN_i and C_j is the coordinates of the final mean point in which the SN_i tagged itself.

(8)

The cluster head selection is performed using back off timer strategy. SN_i sets its back off timer by using the Equation (9).

(9)

is the random variable between [0.9, 1]. is distance of SN_i from final mean point in a cluster. is average distance of all the senor nodes within a cluster.

The back off timer of each node starts decrementing and the node whose back

off timer expires first within the cluster, broadcasts a CH advertisement message to other nodes. The nodes receive a CH advertisement message joins the CH by sending the cluster member join message to CH. A node may receive more than one CH advertisement messages. If a node receives more than one message, checks the received signal strength of the messages and send the reply to the CH message received with larger signal strength. Figure 4 shows the clusters with their cluster heads formed after CH selection.

2.3. Cluster Head Rotation

The role of CH in a cluster must be rotated regularly among its members to prolong the network lifetime of sensor network by balancing the energy consumption of various sensor nodes. CH is required to perform extra tasks such as data gathering, data aggregation, etc. compared to the other sensor nodes. Energy consumption of CH is more compared to other sensor nodes therefore, some mechanism must be applied for CH rotation among the cluster members. A number of methods for CH rotation have been discussed in literature [33] - [38] .

In CH rotation process, the new CH is selected from cluster members. CH rotation/re-election process is initiated when residual energy of a node falls below the threshold value. The new CH is elected with higher value of Candidacy factor (CF). Candidacy factor of SN_i is defined as

(10)

where is residual energy of SN_i, is the distance between SN_i and centroid of the cluster. is clock offset of SN_i. Each node sends its value to cluster head. CH would choose the node with highest value and pass information to sink and other members about new cluster head. Figure 5 shows the flowchart of CH selection/rotation process.

3. Cluster Based Time Synchronization

The proposed cluster based time synchronization (CBTS) algorithm is based on external synchronization. Once the clustering process is complete using EECA protocol proposed in section 3, time synchronization process is initiated by the parent node, which is the sink/base station during the initial phase. Sink/base station is used as a reference node for time. The proposed algorithm is using k CHs. There are k' CHs at level-1 and k'' CHs at level-2. The proposed model is shown in Figure 6.

The parent node () initiates the synchronization process by broadcasting the Syn_start packet which contains the timestamp and then waits for the reply. When the CHs of level 1 (CH_L1) receive Syn_start packet, they send reply to sink/base station by sending the Syn_ack packet. The Syn_ack packet contains the timestamp where time is the time of sending Syn_start packet, is the time when the CHs of level 1 receive the packet and time when CHs of level 1 send the Syn_ack packet. The parent node after receiving the Syn_ack packets, broadcasts Syn_pkt with timestamp where is the time when the parent node receives the Syn_ack packet and is the time to set the clocks of the CHs of level-1. All CHs of level-1 receive the Syn_pkt and calculate the offset (θ) and delay (δ) and set the clocks as:

(11)

In the initial synchronization phase, sink/base station functions as parent node. After synchronizing the CHs of level 1, it further functions as parent nodes and synchronizes the cluster nodes and CHs of level 2. Cluster based time synchronization algorithm is as below:

Sink/Base Station

1.

2. while nodes are not synchronized do

3. set SCOUNT = k' × T_m

4. broadcasts (Syn_start,)

SCOUNT - -

5. if wait for reply && SCOUNT = = 0 then repeat step 4

6. else

receive (Syn_ack,)

7. broadcasts (Syn_Pkt,) to CH_L1

8. endif

Cluster Heads

9. if CH_L1 receives (Syn_start,) then send (Syn_ack,) to

10. else

CH_L1 waits

11. endif

12. if CH_L1 receives (Syn_Pkt,) from P_n then

calculate

calculate

synchronize

13. else

14. CH_L1 waits

15. endif

16. Repeat step from 1 to 15 in next Synchronization Phase

In the algorithms, is the maximum time required to receive a message from CH and, or vice versa, whereas t is the current time and t_α is the maximum propagation delay. This algorithm sets the logical clock of the CHs and nodes with the global time.

Synchronization Error

All WSN synchronization schemes [10] - [31] have four basic packet delay components: send time, access time, propagation time, and receive time as shown in Figure 7. The send time is that of the sender constructing the time message to transmit on the network. The access time is that of the MAC layer delay in accessing the network. The time for the bits to be physically transmitted on the medium is considered the propagation time. Finally, the receive time is the time spent by the receiver for processing the message. The synchronization error is calculated by using the time stamp message shown in the Figure 6. In synchronization error calculation, access time is combined with send time. The main problem of time synchronization besides having a packet delay is that, it is able to foresee the time spent on each, which can be challenging. Disregarding any of these will significantly surge the performance of the synchronization technique.

In the proposed CBTS synchronization, a message from the sink to SNs transmits through multi-hops that induce the time delay error because of various delays as shown in Figure 7. Exchange of timestamp messages among parent node and cluster heads (shown in the Figure 6) are used to analyse the synchronization error of the proposed CBTS. Simply by using send time, propagation time, receive time and clock drift and then equating the timestamps of cluster head and parent node following equations obtained:

(12)

(13)

and represent the timestamps of cluster head and parent node respectively, where n is representing the level. and represent the send time, receive time and propagation delay, respectively. is the clock drift of the node. To calculate one-hop synchronization error subtract the Equation (12) from Equation (13) as:

(14)

Dividing both sides by 2

(15)

(16)

where Offset is computed as and by subtracting the clock drift from the clock offset, synchronization error for one-hop is obtained as:

(17)

The Equation (17) can be modified to obtain multi-hop synchronization error as:

(18)

(19)

Equation (19) calculates synchronization error for multi-hop communication. The objective of finding the synchronization error is to ensure that at any real time T, is between lower and upper bounds. If the value of synchronization error goes below or exceeds, the resynchronization process is initiated by the sink/base station.

4. Energy Analysis of CBTS

Energy analyses of CBTS algorithm is performed for levels of CHs by using the energy models [32] [39] [40] [41] [42] . Since most of the energy is dissipated by the SNs in communication, therefore the energy analysis is performed for the transmission and reception of m bit message for a distance of d. To transmit m bit message over a distance d, the energy cost of transmission is as:

(20)

is the energy dissipation per bit to run transmitter and receiver electronics circuitry. is the energy coefficient of power amplifier stage of sensor nodes for free space energy dissipation model when transmission distance is less than threshold i.e.. is the energy coefficient of power amplifier stage of sensor nodes for multipath energy dissipation model when transmission distance is greater than threshold i.e.. For, distance threshold can be calculated as.

The energy consumed to receive m bit data is expressed as:

(21)

Initially two-level network is considered, where

Total number of nodes = n

Total number of cluster heads = k

Number of level 1 CHs = k'

Number of level 2 CHs = k''

Number of normal sensor nodes = n − k

The proposed CBTS algorithm uses messages to synchronize n number of SNs. The energy dissipation for receiving and transmitting m bit time synchronization message derived below depends on the number of messages received and transmitted by the SNs. As the sink/base station is at level 0 with no constraint of energy, the energy exhausted during transmitting and receiving m bit time synchronization message at level 1 CHs and level 2 CHs is calculated by using the Equations (20) and (21).

Energy consumption at level 1 CHs: Total energy consumed in CBTS protocol while receiving and sending synchronization messages at level 1 CHs is given by Equation (22) and (23) respectively and the total energy consumed at level 1 CHs is given by Equation (24).

(22)

(23)

(24)

Energy consumption at level 2 CHs: Energy consumed by level 2 CHs while receiving and transmitting synchronization messages is given by Equations (25) and (26) respectively and the total energy consumed by level 2 CHs is given by Equation (27).

. (25)

(26)

(27)

Energy consumption at SNs level: Energy consumed by SNs while receiving and sending synchronization messages is given by Equations (28) and (29)

respectively and the total energy consumed by SNs for receiving and sending time synchronization messages is given by Equation (30).

(28)

(29)

(30)

Total energy consumption for communication: The energy consumption rate for sensors in a WSN contrasts significantly on the basis of the protocols the sensors employ for communications. However, the total energy expended for communication of synchronization messages in the proposed model is given by Equation (31) which is further simplified in Equations (32)-(39). Therefore, the total energy dissipation for a single round of time synchronization for level of hierarchical sensor networks is given by Equation (39).

(31)

(32)

(33)

Solving above, following equation is obtained:

(34)

(35)

(36)

(37)

(38)

Equation for Level (i > 2) can be standardized as:

(39)

where the value of is taken as and the value of can be ob-

tained as:

(40)

5. Simulation and Results

In this section, the performance of Cluster Based Time Synchronization (CBTS) algorithm has been evaluated through simulation. The simulation has been performed in MATLAB 2013a. The performance of CBTS protocol is compared with TPSN [15] and TTS [18] protocols. The performance metrics include the number of nodes in the WSN, initial energy of the SNs, total number of messages per synchronization round, total energy dissipation per synchronization round, propagated synchronization error and convergence time. The simulation parameters are listed in Table 1 where for each parameter, simulation has been run many times and the average result of all runs has been taken for evaluation.

The performance evaluation includes message complexity, total energy dissipation per synchronization round, propagated synchronization error with number of hops and convergence time.

The message complexity in terms of the total number of time synchronization messages per synchronization round while the number of nodes varies from 50 to 500 and the sensing field area is kept constant i.e. 300 m × 300 m as shown in the Figure 8. The simulation results show that the number of time synchronization messages increase with the increase in the number of nodes in a constant field size because increase in number of nodes leads to increase in time synchronization messages. There is a significant reduction in terms of time synchronization messages in the proposed CBTS method than TPSN and TTS methods. TPSN requires messages to synchronize n SNs and TTS requires messages. CBTS reduces the number of synchronization messages by 40% as compared to TPSN and 25% as compared to TTS. The proposed CBTS method

provides the best results in comparison with other protocols. Fewer time synchronization messages decrease the overhead in terms of communication and thus increase the network lifetime.

Total energy dissipation is calculated as the amount of energy dissipated within the sensor network to perform time synchronization. Figure 9 shows the comparison of simulation results of energy variation for different protocols such as TPSN, TTS and CBTS. The variation in the energy dissipation is studied by varying number of nodes from 50 to 500, while keeping the sensing field size constant as 300 m. It has been observed that the energy dissipation per round increases with increase in the number of nodes. Increased number of nodes leads to increase in the number of time synchronization messages which increases the total routing energy and thus total node energy consumed. The simulation results in Figure 9(a) show that CBTS protocol provides better performance compared to other two protocols. This is due to the less number of synchronization messages and better clustering technique as compared to TPSN and TTS.

It has been observed that the energy dissipation incessantly increases with the increase in the sensing field size. The distance between the sink and the sensing node increases with the increase in the sensing field size, which increases the transmission energy cost, although the time synchronization messages remain the same. Aforementioned, the performance of cluster based time synchronization (CBTS) is better than other two protocols due to the reduction in the number of synchronization messages and better clustering approach.

Figure 9(b) shows the total energy dissipation per round for variation in the sensing field sized between 100 m to 500 m while the number of nodes remains constant at 300 nodes. It has been observed that the energy dissipation goes on increasing with the increase in the sensing field size. The distance between the sink and the sensing node increases with the increase in the sensing field size, which increases the transmission energy cost. In case of TPSN protocol the value

is the highest because it uses n + n messages to synchronize n nodes as compared to TTS and CBTS.

Synchronization error is the difference between the times of a CH with respect to the times of the sink. The synchronization error is added with the increasing number of hops generally. The variation in the synchronization error is studied by fixed number of nodes i.e. 300 nodes, while keeping the sensing field size constant at 300 m. The synchronization error increases with number of hops for CBTS, TTS and TPSN protocols in particular as shown in Figure 10. The values shown in the Figure 10 are the average of 50 simulation results.

The synchronization error of TPSN is high i.e. 16 μs for one hop and 46 μs for five hops because of the topology and number of messages required for synchronization of the TPSN network. Synchronization error in TPSN is high because it

uses large number of messages, since several messages bump into each other causing a collision and required to be sent again and leads to error. A large amount of message transmission leads to collisions and further to performance degradation. Synchronization error of TTS is also high because of using a pair of nodes to synchronize the SNs which increase number of messages and adds errors at each hop. The performance of cluster based time synchronization (CBTS) is better than other two protocols i.e. 2.6 μs for five hops due to less number of synchronization messages and better clustering approach which reduces the packet collisions and thereby reducing the synchronization error. Simulation results show that our proposed protocol outperforms other protocols in terms of synchronization error. In case of TPSN, the unbalanced clustering technique and the overhead of messages for synchronization are responsible for higher synchronization error. CBTS uses EECA clustering technique which required less number of synchronization messages to synchronize the sensor network.

The total time required to synchronize the network is known as convergence time. The variation in the convergence time is studied by fixed number of nodes i.e. 300 nodes, while keeping the sensing field size constant as 300 m. Convergence time is measured for five hops and observes that it increases with number of hops for TPSN, TTS and CBTS protocols as shown in Figure 11. Convergence time is directly proportional to message complexity and bandwidth use. TPSN requires messages to synchronize n SNs and TTS requires time synchronization messages, therefore the convergence time for TPSN and TTS is very high. In TPSN for five hops it is 4 s and for TTS it is 3 s. In CBTS it is 2 s for five hops. Simulation results shows that CBTS protocol outperforms the other protocols in terms of convergence time with respect to number of hops. In TPSN convergence time is higher because of unbalanced hierarchical technique and more number of messages. CBTS uses less number of messages and better clustering topology.

6. Conclusion

The proposed cluster based time synchronization protocol ensures the synchronization of the nodes with global time. The proposed CBTS protocol uses the EECA clustering technique proposed in section 2 for clustering the network. Synchronization is performed using top to bottom approach. CHs synchronize with the sink and SNs synchronize with their respective CHs. The proposed technique uses messages to synchronize the n SNs. Therefore, the proposed CBTS is suitable for time synchronization in energy efficiency manner. Simulation results demonstrate the effectiveness of the proposed protocol in terms of message complexity, total energy dissipation per synchronization round, propagated synchronization error, convergence time and synchronization precision level. The simulation results are compared with TPSN and TTS protocols. The proposed CBTS protocol provides better results in comparison with these protocols and can be used in WSNs for less energy consumption and prolonging the network lifetime.

Cite this paper

Gautam, G.C. and Chand, N. (2017) A Novel Cluster Based Time Synchronization Technique for Wireless Sensor Networks. Wireless Sensor Network, 9, 145-165. https://doi.org/10.4236/wsn.2017.95008

References