A consensus time synchronization protocol in wireless sensor network

CHEN Kesong and ZHANG Yu

School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China

Abstract: Time synchronization is one of the base techniques in wireless sensor networks (WSNs).This paper proposes a novel time synchronization protocol which is a robust consensusbased algorithm in the existence of transmission delay and packet loss.It compensates for transmission delay and packet loss firstly, and then, estimates clock skew and clock offset in two steps.Simulation and experiment results show that the proposed protocol can keep synchronization error below 2 μs in the grid network of 10 nodes or the random network of 90 nodes.Moreover, the synchronization accuracy in the proposed protocol can keep constant when the WSN works up to a month.

Keywords: time synchronization, consensus algorithm, transmission delay, packet loss, wireless sensor network (WSN).

1.Introduction

Wireless sensor network (WSN) is a network composed of many sensor nodes, which consists of sensing, data processing, and communicating components [1].It can be applied in different areas such as environmental monitoring, industrial and manufacturing automation, healthcare, and military by gathering and processing data from the environment or monitoring an environment [2].

Time synchronization is one of the key techniques of WSN.It is a prerequisite for events which require the knowledge of time between sensor nodes such as target tracking.It is also essential for data fusion or security reasons [3].

Consensus time synchronization protocol does not rely on one or several certain nodes.All the nodes are synchronized to a common global time.In 2011, Schenato et al.proposed average timesync (ATS) protocol [4], in which all nodes’ time is synchronized to an average time of the network.In 2014, He et al.proposed the maximum time synchronization (MTS) protocol and the weighted maximum time synchronization (WMTS) protocol [5].In these two protocols, the fastest clock of the network is used as a reference clock while other nodes need synchronize it.In 2015, Wu et al.proposed cluster-based consensus time synchronization (CCTS) [6].It divides the whole synchronization into intra-cluster time synchronization and inter-cluster time synchronization.In 2020,Shi et al.proposed the multihop average consensus time synchronization (MACTS) [7].It employs virtual communication links among multihop nodes to balance the convergence time, accuracy, and communication complexity.

However, these algorithms have not considered transmission delay and packet loss adequately.Also, the simulations and experiments of these protocols usually run at the start of a WSN’s lifetime.The analysis about their performances when they run long time such as a month after the WSN is established is deficient.

This paper has analyzed the transmission delay and the packet loss in WSN, and a novel consensus time synchronization protocol is proposed.In this protocol, synchronization is done in two steps.The clock skew and transmission delay are estimated and compensated in Step 1 whereas the clock offset is synchronized in Step 2.The packet loss is considered and used to revise the synchronization in each step.Simulation and experiment results have shown that the synchronization accuracy in this protocol can reach 2 μs whether at the beginning of the WSN established or a month later.

This paper is organized as follows: Section 2 describes the clock model, the transmission delay, the packet loss,and the necessity of analysing the performance of a time synchronization protocol with different start times.In Section 3, the proposed consensus time synchronization protocol is presented.Simulation and experiment results are shown in Section 4 and Section 5 respectively.The conclusions are given in Section 6.

2.Preliminaries

2.1 Clock model

Ideally, every node in a WSN has the same time configured as

wheretstandsforabsolute reference timeandτi(t)(i= 1,2,3, ···) standsfornodei’shardwareclockwhen absolute reference time ist.

However, as the result of the inaccuracy of clock oscillator and error in initialization, each node has different clock skew and clock offset [8].Suppose that the clock skew is constant for a short period of time, the linear clock model is commonly applied to describe a clock in the WSN as

whereαiandβistand for nodei’s clock skew and clock offset respectively.The clock model is decribed in Fig.1.

Fig.1 Linear clock model

Unfortunately, the absolute reference timetis unknown in WSN.The nodes’ clock can be only synchronized to a consistent time named common global time τ¯(t)[9].After clock skew and offset of each node are estimated, the hardware clock is corrected by

whereLi(t) is named nodei’s logical clock [5].The synchronization parameters αˆiand βˆiare estimators of 1/αiand -βi/αirespectively.

The goal of time synchronization protocol is to find a proper ( αˆi, βˆi) to make the logical clockLi(t) approach to common global time τ ¯(t) for all nodes.

2.2 Transmission delay

If a node synchronizes its time by exchanging time message with other nodes, transmission delay is the main error.After created by the sender’s microcontroller units(MCU), the time message is delivered to the receiver’s MCU via the sender’s and the receiver’s radio chip and antenna.The delays exist in the five stages of time message’s delivery and all of them compose the transmission delay as shown in Fig.2.

Fig.2 Delivery of time messages and the composition of transmission delay

Stage 1 From the sender’s MCU to the sender’s radio chip.After accessing the hardware clock, the sender’s MCU calls its radio chip and writes the time message in it.The main delay in this stage is the time of this writing.

Stage 2 From the sender’s radio chip to the sender’s antenna.The sender’s radio chip waits for the channel to be idle.Then it encodes and modulates the time message before sends it to antenna.The delay in this stage depends on the current traffic in channel and the hardware of encoder and modem.

Stage 3 From the sender’s antenna to the receiver’s antenna.The time message travels via air in the form of electromagnetic waves.This delay only relies on the distance between the two nodes.

Stage 4 From the receiver’s antenna to the receiver’s radio chip.The receiver’s radio chip decodes and demodulates the time message after receives it from antenna.The main delay in this stage is the processing time of decoding and demodulation.

Stage 5 From the receiver’s radio chip to the receiver’s MCU.The receiver’s radio chip calls MCU’s interrupt when gets the time message.MCU responds to this interrupt and reads the time message from radio chip while records the hardware time instantly.The delay of this stage consists of the two delays above.

All these stages except Stage 3 have the delay named byte alignment time [10].This delay occurs because of different byte alignment of these digital devices.

It can be inferred from the analysis above that the transmission delay is a random variable.In linear clock model, the expectation of transmission delay mainly determines the error of clock offset estimation while the error of clock skew estimation depends more on the variance of transmission delay [11].

2.3 Packet loss

There are several causes which may lead to packet loss in wireless communication.The main three causes in WSN are as follows:

Cause 1 The received power is too low.When the signal is transferred from the sender to the receiver, its power fades due to distance and medium between the two nodes.The barrier in the path of transmission may accelerate the fading of the power.When the received power is lower than receiver sensitivity, the packet cannot be detected by the receiver, i.e., packet loss has occurred.

Cause 2 The signal to noise ratio (SNR) is too low.Noise is ubiquitous and random.When SNR is too low,the receiver cannot decode the packet correctly even if the received power is larger than receiver sensitivity.Different from received power, there is no threshold of SNR that determines whether the message is recognized completely.Usually, packet error probability increases as SNR decreases.

Cause 3 The communication collision occurs.If two nodes are not neighbours, they may broadcast their message at the same time.In this case, the communication collision will occur on their common neighbours.

As shown in Fig.3, Node B and Node C are Node A’s neighbours, but Node B and Node C cannot detect each other.If Node B and Node C broadcast their message at the same time, Node A cannot decode either of the two messages.

Fig.3 Communication collision

As analysed above, the packet loss is an unavoidable problem in WSN.It should not be overlooked in time synchronization protocol.All the reasons above are relative to separation distance between the two nodes.Ideally, when the distance increases, the received power and SNR will decrease.Also, in a certain network, larger distance means that the two nodes have fewer common neighbours and more chances of communication collision.

2.4 Performance of a time synchronization protocol with different start time

Consider that WSN works for a few days to several years due to its applications [12], when WSN works for a long time, the nodes’ clock which is synchronized at the beginning of the WSN establish runs out of synchronization again.Moreover, some nodes fail and new nodes join at the lifetime of a WSN [13].It is necessary to run a time synchronization protocol periodically to keep the clocks synchronized for the whole lifetime of the WSN.Therefore, a practical time synchronization should have the same or similar performance with different start time.

3.Proposed consensus time synchronization protocol 3.1 Iterative parameters

The proposed protocol is an iterative algorithm in this paper.Each node updates its iterative parameters at each iteration.For arbitrary nodei, these iterative parameters are as follows:

Parameter 1 Logical timeLiand its parametersαˆiand βˆi.As analysed in Subsection 2.1, αˆiand βˆiare estimators of 1 /αiand - βi/αirespectively.Their relationship is shown in (3).Initially, αˆi(0) is set to 1 and βˆi(0) is set to 0.

Parameter 2ηij, which represents the estimator of proportion of nodej’s clock skewαjto nodei’s clock skewαi, where nodejis nodei’s neighbour.ηij(0) is initialized to 1.

Parameter 3dij, which represents the estimator of delay when nodejsends messages to nodei, where nodejis nodei’s neighbour.The initial valuedij(0) can be set to 0.However if the measurements of transmission delay are available, it is better to use the average of them.

Each node broadcasts a time information packet to its neighbours at each iteration.Supposetjrepresents the absolute reference time when nodejbroadcasts its time information packet andtj,iis the absolute reference time when nodeireceives this packet.dij(tj,i) is the delay between the broadcasting and receiving above, i.e.,

Supposetj,oldandtj,i,oldrepresent the absolute reference time respectively when nodejbroadcasts time information packet and nodeireceives this packet in the last iteration, all the time values above are shown in Fig.4.

Fig.4 Time values used in this protocol

3.2 Clock skew estimation

From Subsection 3.1,ηij, which represents the estimator of proportion of nodej’s clock skewαjto nodei’s clock skewαican be calculated by

Then the statistical expectation of ηijis

In this paper, the first order low-pass filtering algorithm is used to estimateηijas follows:

whereρη∈ (0, 1) is the filter coefficient.

Considering the packet loss,ηij(tj,i) in (7) might be calculated a few periods ago.Consequently, the weight of old data will increase and the convergence rate will decrease.

whereTis the period.Equation (8) is used to ensure that older data has lower weight, which is modified from (7).

After updating iterative parameterηij, update iterative parameter αˆithrough

whereρα∈ (0, 1) is the constant coefficient.Equation (9)is the same as the drift compensation equation in ATS protocol [4].

3.3 Transmission delay estimation

The following equations about transmission delay can easily be drawn from (2) and (4):

From (10), it can be referred that

The clock skewαiandαjare unknown.αˆiand αˆjwhichare estimators of 1/αiand 1αjrespectively as shown in Subsection 3.1 can be used to replaceαiandαj,then

Suppose the expectations of the transmission delay when nodeitransmits to nodejand nodejtransmits to nodeiare equal, i.e., E(dij) = E(dji), then

In this paper, the first order low-pass filtering algorithm is also used to estimatedijas follows:

whereρd∈ (0, 1) is the filter coefficient.

Consider that the packet loss exists, then

is used to modify (14).

3.4 Clock offset estimation

If transmission delay is absent, (16) which is proved by Schenato et al.[4], can be used to update iterative parameter βˆi:

whereρβ∈ (0, 1) is the constant coefficient.

In this paper, the transmission delay is estimated and is used to modify this iterative equation as

3.5 Definition of the proposed protocol

In the proposed protocol, each node broadcasts a time information packet to its neighbours at each iteration.The time information packet has five data members.They are the sender’s IDj, the hardware clockτj(tj), the synchronization parameters αˆitjand βˆjtj, and the neighbour information set.

The neighbour information set has information about at most four neighbours.If a node has more than four neighbours, choose four of them randomly at each iteration.Suppose nodeiis nodej’s neighbour, the neighbour information describes the latest communication that nodejreceives nodei’s broadcast message.It has three data numbers, i.e., neighbour’s IDi, hardware clockτi(ti) and hardware clockτj(ti,j), wheretirepresents the absolute reference time when nodeisends the packet andti,jis absolute reference time when nodejreceives nodei’s packet as shown in Fig.4.

When nodeireceives the time information packet from nodej, it records its hardware clockτi(tj,i) immediately.Then, it updates its iterative parameters due to the following steps.

Step1 Thefirstn1cycles.Nodeiupdatesitsiterative parametersηij,αˆianddijthrough (8),(9),and (15)respectively.

Step 2 The lastn2cycles.Nodeiupdates its iterative parameter βˆithrough (17).

For arbitrary nodei,j, when the protocol starts att0, the process can be described as Algorithm 1.

iτ(Algorithm 1 The proposed consensus time synchronization protocol ˆαi(0) ˆβi(0)1.Initially, = 1, = 0, ηij(0) = 1, dij(0) = 0 or dij(0) is set to the average of delay’s measurements.2.When τj(t) = njT + t0, where positive integer, node j broadcasts its time information packet which includes j, τj(tj), , and the neighbour nformation set.3.When receiving this packet, node i records its hardware clock τi(tj,i).Calculate positive integer ni for t0 + niT ≤i(tj,i) < t0 +(ni+1)T.ˆαi ˆβi nj ∈[1,n1+n2]ˆαi(tj) ˆβj(tj)4.If ni ≤ n1, update ηij, and dij through (8), (9), and 15) respectively; else, update through (17).

3.6 Physical-layer time capture

In this paper, physical layer (PHY-layer) time capture is used to reduce transmission delay.In the process of nodejbroadcasting its time information packet, when a certain byte is transmitted, the timer captures this event and records the hardware time asτj(tj).Then MCU reads this time and adds it to the end of the packet.For receiver nodeiwhen the certain byte is received at PHY-layer, the timer also captures this event and records the hardware time asτi(tj,i).Then MCU gets time information and updates the iterative parameters as shown in Subsection 3.5.

Compared with the traditional method that reads the clock before creating time information packets and records the receive time after receiving the whole packet,the PHY-layer time capture can eliminate the transmission delay in Stage 1 and Stage 5 as shown in Subsection 2.1.This method can also reduce the transmission delay in Stage 2 by removing the time of waiting for the channel to be idle.

For example, the CC2530 device has a timer named Timer 2 which can capture the time when the start-offrame delimiter (SFD) byte in PHY-layer of IEEE 802.15.4 is transmitted or received [14,15].

4.Simulation

4.1 Simulation environment

In this paper, Network Simulator 3 is used as a simulation platform.Suppose the transmission delay except Stage 3 in Subsection 2.2 obeys a Gaussian distribution whose statistical expectation is 3.5 μs and standard deviation is 500 ns.The clock skew also obeys a Gaussian distribution and has four parts per million (ppm) standard deviation.These values above are measured in experiment shown in Section 5.Suppose the network has 90 nodes and they are distributed randomly in a square area whose side is 1 800 m.Before time synchronization protocol starts, nodes’ hardware clock is uniformly distributed betweent0and (t0+ 10 s) wheret0is the start time of time synchronization protocol.t0is set to 0 s and a month(2 592 000 s) respectively in the following simulations.The synchronization period is set to 20 s and the whole protocol lasts for 190 cycles where Step 1 has 60 cycles while Step 2 has 130 cycles.The protocol parameters are set asρα=ρβ= 0.5 andρη=ρd= 0.2 [4].

The network works on IEEE 802.15.4 protocol [15].Some parameters are shown in Table 1.

Table 1 Communication parameters in simulation

The bit error rate (BER) model used in this paper is shown as follows:

where SINR represents signal to interference plus noise ratio.

There is no interference in this simulation and SINR is equal to SNR.Thermal noise is the only noise in this simulation and it only depends on temperature.

The path loss model used in this paper is log distance propagation loss model which is shown as follows:

wheredrepresents the distance between the sender and the receiver.Path loss exponentnis 3.3.The reference distanced0is 8 m and the reference path loss PL(d0) is 58.5 dB.

The proposed protocol in this paper is simulated with different start time and is compared to ATS and WMTS protocol.Mean square error (MSE) of all nodes’ logical clock is commonly used to describe synchronization accuracy [16].However, the unit of MSE is the square of that of time.In this paper, root mean square error (RMSE)is used to avoid this problem.

4.2 Simulation results

As described in Subsection 4.1, all nodes are distributed randomly in a 1 800 m × 1 800 m rectangular area.The following simulation results base on the nodes’ distribution shown in Fig.5.

Fig.5 Distribution of nodes

This simulation compares synchronization accuracy represented by RMSE of nodes’ logical time of the proposed protocol in this paper with ATS and WMTS protocol.Suppose the time synchronization protocol runs at the beginning of WSN established, i.e.,t0= 0 s, and a month later, i.e.,t0= 2 592 000 s.Fig.6 shows simulation result of the different start time above respectively.

Fig.6 Simulation results

As shown in Fig.6, the RMSE of nodes’ logical clocks in this novel protocol is nearly constant in Step 1 because clock offset is not synchronized in this step.Then it decreases fast when Step 2 starts and keeps stable after 2 800 s.When the synchronization ends, the proposed protocol has high synchronization accuracy in less than 2 μs.Compared with ATS protocol whose synchronization error is more than 10 μs and WMTS protocol whose synchronization is approximately 9 μs, the proposed protocol improves the performance obviously.

As shown in Fig.6(b), the synchronization error in ATS and WMTS protocol increases to over 5 ms when time synchronization protocol’s start timet0increases to a month.On the contrary, the performance of this proposed protocol is similar to it in Fig.6(a) whent0is 0.This shows the proposed protocol has stable synchronization accuracy at the different stages of WSN’s lifetime.

5.Experiment

5.1 Experiment platform

The CC2530 MCU whose clock is 32 MHz is used as experiment platform in this paper.Each node which is powered by two 18 650 lithium batteries and AMS1117 voltage regulator contains a CC2530 MCU and an antenna as shown in Fig.7.

Fig.7 Nodes in the experiment

This experiment has 10 nodes which are placed in a 5 × 2 grid network.By adjusting the separation distance and the transmitting power, each node can only receive its adjacent nodes reliably.The two nodes in a diagonal location, such as Node 1 and Node 7, have a packet loss probability of more than 30% even if there is no communication collision.For other nodes, there is only a small probability to communicate correctly.As shown in Fig.8,the black point represents a node and the line between points means the two nodes can communicate reliably.

Fig.8 Network of experiment

An STM32 MCU which is connected to the all 10 nodes and a computer is used to record the nodes’ logical time.The whole experiment system is shown in Fig.9.

The STM32 MCU creates a pulse every 20 s.Each node saves its hardware clockτi, synchronization parameter s αˆiand βˆiinto memory whereiis the node ID through direct memory access (DMA) as soon as it detects the pulse.These data are read and sent to a computer by STM32 MCU after the time synchronization protocol ends.Then, this computer analyses them and shows the result.

Fig.9 Experiment system

The synchronization period is set to 12 s and the whole protocol lasts for 300 cycles where Step 1 has 100 cycles and Step 2 has 200 cycles.The values of protocol parametersρα,ρβ,ρη, andρdare the same to them in simulations.

5.2 Experiment result

All 10 nodes start successively and run time synchronization protocol immediately.Fig.10 shows synchronization accuracy represented by RMSE of nodes’ logical time of the novel protocol in this paper compared to ATS and WMTS protocol.

Fig.10 Synchronization accuracy of experiment

As shown in Fig.10, the result of experiment is similar to that of simulation in Fig.6(a).When the network is a 5 × 2 gird, the error of the proposed protocol can be converged and the synchronization accuracy is approximately 2 μs.The experimental result shows that this proposed protocol has higher synchronization accuracy than that of the ATS and WMTS protocol.

6.Conclusions

The transmission delay and packet loss in WSN are analysed in this paper, whose causes and consequences are derived from the linear clock model.Based on these preliminaries, a consensus time synchronization protocol is proposed.In this protocol, transmission delay is compensated, and the iteration calculation is modified because of packet loss.Moreover, the synchronization processing is divided into two steps to ensure that the accuracy can keep stable even if the WSN has worked for a long time.Simulation and experiment results show that this protocol can control the synchronization error under 2 μs in many application scenarios.Also, it has similar performance for WSN with a variety of different life cycles.