Sage Journals: Discover world-class research

Abstract

Time synchronization is a crucial component in wireless sensor networks (WSN), especially for location-aware applications. The precision of time-based localization algorithms is closely related to the accuracy of synchronization. The estimation of synchronization errors in most of the existing time synchronization algorithms is based on some statistical distribution models. However, these models may not be able to accurately describe the synchronization errors due to the uncertainties in clock drift and message delivery delay in synchronization. Considering that the synchronization errors are highly temporally correlated (short-term correlation), in this paper, we present an adaptive linear prediction synchronization (ALPS) scheme for WSN. By applying linear prediction on synchronization errors and adaptively adjusting prediction coefficients based on the difference between the estimated values and the real values, ALPS enhances synchronization accuracy at a relatively low cost. ALPS has been implemented on the Tmote-sky platform. As experiment results demonstrate, compared with RBS and TPSN, ALPS cuts synchronization cost by almost 50% while achieving the same accuracy; compared with DMTS and PulseSync, ALPS reduces the MSE (mean square error) of synchronization errors by 41% and 24%, respectively, with the same cost.

1. Introduction

Time synchronization is one of the key middle-ware components in wireless sensor networks (WSN) [1]. Accurate time synchronization is critical to many tasks in various WSN applications including duty cycling scheduling, data fusion and tracking, and transmission scheduling. Localization is another important application of time synchronization. The accuracy of time synchronization directly influences the precision of localization [2].

Among the existing localization algorithms [3–6], the most accurate localization approaches are ranged-based methods. These methods usually use the time-of-arrival (TOA) [7], time-difference-of-arrival (TDOA) [8, 9], angle-of-arrival (AOA) [10], and received signal strength (RSS) [6] to compute the distances between nodes and anchors and then obtain the location information. Among the above four methods, TOA and TDOA are time-based localization algorithms, which are promising ranging methods due to their high accuracy and low cost. The simulation results [2] demonstrate that the accuracy of the time synchronization is a central issue in time-based localization approaches. Therefore, time synchronization plays a critical role in localization algorithms.

Many time synchronization algorithms have been proposed in recent years. The early time synchronization algorithms, such as RBS [11], TPSN [12], DMTS [13], and FTSP [14], are all based on timestamp exchanges, which are intended to offset the uncertainties of message delivery delay to enhance the synchronization accuracy. On-demand synchronization (ODS) [15] adaptively adjusts the synchronization interval for customized accuracy with minimized communication overhead. Lenzen et al. propose PulseSync [16] which distributes information on clock values as fast as possible and achieves a higher synchronization accuracy than FTSP. Leng and Wu present a synchronization scheme under unknown Gaussian distribution aiming at achieving both low computational complexity and high performance [17]. Leng and Wu also model the WSN synchronization under exponential delays as a linear programming problem and solve it with a novel low-complexity estimator [18]. In [19], a Kalman filter is used to estimate both clock offset and skew. An improvement on [19] by adopting an adaptive multimodel mechanism is presented in [20]. Zheng and Wu present a unified framework to jointly solve time synchronization and localization problems at the same time [2]. Jin et al. study how voltage influences the clock skew and proposes a novel voltage-aware time synchronization (VATS) scheme [21].

Most of existing synchronization schemes assume that the distribution of clock skew and the delivery delay of synchronization packets follow some statistical models (such as Gaussian distribution model in [15, 17, 20, 21], exponential distribution model in [18, 22, 23], and gamma distribution model in [1]). However, the clock drift and message delivery delay are essentially very random and easily affected by some environment factors (such as temperature and voltage). Therefore, it is not easy to describe them accurately through any predetermined model [1, 24]. Moreover, some algorithms need to calibrate the clock skew frequently (such as [11, 14, 20, 22]). However, as [15] demonstrates, frequent clock skew calibration will not only increase the computation and communication overhead, but also may increase the synchronization errors due to the miscalculation of the message delivery delay.

Linear prediction is a mathematical operation where future values of a discrete-time signal are estimated as a linear function of previous samples. In digital signal processing, linear prediction is often called linear predictive coding (LPC) and is widely used in speech coding, digital filter, and wireless channel estimation. Considering that synchronization errors are highly temporally correlated (as Figure 3 shows), in this paper, an adaptive linear predication synchronization (ALPS) scheme for WSN is proposed. To the best of our knowledge, this is the first work which applies linear prediction to the time synchronization in WSN.

ALPS predicts clock offset based on its historical values. ALPS does not assume the clock offset to follow any particular statistical distribution or need frequent clock skew calibration. As experimental results demonstrate, ALPS has a better performance than DMTS and PulseSync without increasing synchronization cost; ALPS reduces synchronization cost compared to RBS and TPSN while maintaining the same synchronization accuracy.

2. Motivation

In WSN, each node has an independent local clock. Ideally, the clock should satisfy the equation $C (t) = t$ , where t stands for the ideal or reference time. However, due to the influence of voltage, temperature, and other environmental factors, the clock will drift away from the ideal time. The clock model is illustrated in Figure 1. In general, the clock function of node i can be modelled as

\begin{matrix} C_{i} (t) = θ + f \cdot t, \end{matrix}

(1)

where θ and f are clock offset and clock skew, respectively.

Figure 1

Clock model of sensor nodes.

In WSN, offsets exist between clocks of different nodes due to the difference in clock skew and the initial phase. Consider the time synchronization process between node A and node B, where B is the reference node and A is the node to be synchronized, as illustrated in Figure 2. Suppose node B sends a message to node A about its clock reading $T_{B, k}$ at node B's local time $T_{B, k}$ and node A receives node B's message at A's local time $T_{A, k}$ . Then $T_{A, k}$ and $T_{B, k}$ satisfy the following expression:

\begin{matrix} T_{A, k} = f \cdot T_{B, k} + θ + τ, \end{matrix}

(2)

where θ and f are the relative clock offset and skew between node A and node B, respectively. τ is the delay of message transmitted from node B to node A.

Figure 2

Synchronization model.

Figure 3

Synchronization errors over time using a fixed compensation value.

The goal of time synchronization is to make the clocks of node A and node B the same. In (2), there are three parameters, f, θ, and τ to be estimated. For f and τ, most of the synchronization schemes first assume that they follow a particular statistical distribution and then estimate them by some statistical means. For example, the least squares (LS) estimator is applied in [14, 24]. In [18, 23], the parameters are estimated using the maximum likelihood estimator (MLE) and minimum variance unbiased estimator (MVUE), respectively.

However, the delay of the message for synchronization (τ) consists of many components, including send/receive time, access time, transmission/reception time, interrupt time, and encoding/decoding time. Among them, the send/receive time, access time, and interrupt time are nondeterministic. Although the nondeterminacy of the synchronization delay can be reduced by inserting the timestamp into the appropriate place in the packet at the lower layers [13, 14], it can not be eliminated completely. On the other hand, clock skew (f), affected by voltage, temperature, and other environment factors [21], exhibits great randomness and is difficult to be described by any particular statistical model. Moreover, since the randomness of clock skew and synchronization delay are not independent of each other, inappropriate estimation not only can not eliminate the errors, but also introduce new errors [15]. Therefore, there are limitations when using a specific statistical distribution model in time synchronization. Linear prediction, however, as a widely used method in the field of random signal estimation, is independent of any special statistical distribution model. Considering that the clock skew changes slowly and the synchronization error samples exhibit high short-term temporal correlation and periodicity, we adopt adaptive linear prediction as the estimator of the synchronization errors in our synchronization scheme.

3. Algorithm

3.1. Linear Prediction Model

The key idea of linear prediction is that if there is temporal correlation between signal samples, we can use past sample values to predict current and future sample values. The sample to be predicted can be closely approximated as a linear combination of past samples. The prediction coefficients are determined by minimizing a certain function of differences between sample values and predicted values.

In the time synchronization model, if we consider the clock offset caused by both clock skew and the synchronization delay as a single variable $Δ T_{k}$ , $T_{A, k}$ , and $T_{B, k}$ satisfy the following expression:

\begin{matrix} T_{A, k} = T_{B, k} + Δ T_{k}, \end{matrix}

(3)

where

Δ T_{k}

is the sum of clock offset caused by clock skew and transmission delay at the Kth synchronization.

In order to examine how the synchronization errors change with time, we implemented several experiments (lasting 24 hours, with synchronization interval 2 s, 3 groups) on the Tmote-sky platform. In these experiments, we compensated the clock offset with a fixed value $Δ T_{k}$ and recorded all synchronization errors during the testing time. The synchronization errors over time are shown in Figure 3, which is similar to [15]. As Figure 3 demonstrates, in short term (within 30–50 samples), synchronization errors do not vary much (short-term correlation), due to the relatively stable clock skew, where small fluctuations result from rounding in calculation. In long term (interval more than 100–120 samples), synchronization errors become periodical (long-term correlation), due to the effect of varied clock skew. These experiment results demonstrate that the synchronization errors are highly temporally correlated. Therefore, linear prediction, as a simple and widely used prediction method, can be utilized to estimate $Δ T_{k}$ . Also, the prediction coefficients can be adaptively assigned to minimize the MSE of synchronization errors.

The basic idea of linear prediction is that $Δ T_{k}$ can be approximated by its historical values $(Δ T_{k - 1}, Δ T_{k - 2}, \dots)$ . We define two symbols: (i) $\hat{Δ T_{k}}$ , which is the predicted value of $Δ T_{k}$ and (ii) $e_{k}$ , which is the prediction error, that is, the difference between the real value $Δ T_{k}$ and the predicted value $\hat{Δ T_{k}}$ . $Δ T_{k}$ is the real time difference between the master node (node B) and the slave node (node A), where the former value is read in the synchronization packet, and the latter is the local time of the slave node when the synchronization packet arrives. Then, $\hat{Δ T_{k}}$ and $e_{k}$ can be expressed as

\begin{matrix} \hat{Δ T_{k}} = a_{1} Δ T_{k - 1} + \dots + a_{p} Δ T_{k - p} = \sum_{i = 1}^{p} ‍ a_{i} Δ T_{k - i}, \end{matrix}

(4)

\begin{matrix} e_{k} = Δ T_{k} - \hat{Δ T_{k}} = Δ T_{k} - \sum_{i = 1}^{p} ‍ a_{i} Δ T_{k - i}, \end{matrix}

(5)

where

a_{i}

(

i = 1,2, \dots, p

) are the prediction coefficients and p is the prediction order.

3.2. Calculation of the Prediction Coefficient $a_{i}$

We use the synchronization mean square error (MSE) to evaluate the synchronization performance. Smaller MSE indicates higher synchronization accuracy [22]. The $E_{n}$ , which is based on MSE, is defined as follows:

\begin{array}{l} E_{n} = \sum_{n} ‍ e_{k}^{2} = \sum_{n} ‍ {(Δ T_{k} - \hat{Δ T_{k}})}^{2} \\ = \sum_{n} ‍ {(Δ T_{k} - \sum_{i = 1}^{p} ‍ a_{i} Δ T_{k - i})}^{2} . \end{array}

(6)

To minimize $E_{n}$ , set the partial derivative of $E_{n}$ to $a_{i}$ ( $i = 1,2, \dots, p$ ) be zero; that is, $\partial E_{n} / \partial a_{j} = 0$ . Consider

\begin{matrix} 2 \sum_{n} ‍ Δ T_{k} Δ T_{k - j} - 2 \sum_{i = 1}^{p} ‍ a_{i} \sum_{n} ‍ Δ T_{k - i} Δ T_{k - j} = 0, \end{matrix}

(7)

where

j = 1,2, \dots, p

Equation (7) can be further reduced to the following equation:

\begin{matrix} \sum_{n} ‍ Δ T_{k} Δ T_{k - j} = \sum_{i = 1}^{p} ‍ a_{i} \sum_{n} ‍ Δ T_{k - i} Δ T_{k - j} . \end{matrix}

(8)

Apparently, by solving this equation set, we can obtain all the prediction coefficients $a_{i}$ ( $i = 1,2, \dots, p$ ) which minimize $E_{n}$ .

Define $Φ (i, j)$ and $R (j)$ as follows:

\begin{matrix} Φ (i, j) = \sum_{n} ‍ Δ T_{k - i} Δ T_{k - j}, (i, j = 1,2, \dots, p), \\ R (j) = \sum_{n} ‍ Δ T_{k} Δ T_{k - j}, (j = 1,2, \dots, p), \end{matrix}

(9)

where

R (j)

is the autocorrelation function of

Δ T_{k}

Combining (8) and (9) and the properties of the autocorrelation function, we will have

\begin{matrix} \sum_{i = 1}^{p} ‍ a_{i} R (|i - j|) = R (j), (j = 1,2, \dots, p) \end{matrix}

(10)

expressed in matrix form as follows:

\begin{matrix} [\begin{bmatrix} R (0) & R (1) & \dots & R (p - 1) \\ R (1) & R (0) & \dots & R (p - 2) \\ ⋮ & ⋮ & ⋮ & ⋮ \\ R (p - 1) & R (p - 2) & \dots & R (0) \end{bmatrix}] [\begin{bmatrix} a_{1} \\ a_{2} \\ ⋮ \\ a_{p} \end{bmatrix}] = [\begin{bmatrix} R (1) \\ R (2) \\ ⋮ \\ R (p) \end{bmatrix}] . \end{matrix}

(11)

The above is called Yule-Walker equations, where the coefficient matrix is a $p \times p$ Toeplitz matrix in which each descending diagonal from left to right is constant.

We can use Levinson-Durbin recursion algorithm to solve Yule-Walker equations. The Levinson-Durbin recursion algorithm is given as follows [25]. (1)

$E_{0} = R (0)$ , when $i = 0$ .

(2)

Perform recursive calculation with the following formulas:

\begin{matrix} k_{i} = \frac{R (i) - \sum_{j = 1}^{i - 1} ‍ a_{j}^{i - 1} R (i - j)}{E_{i - 1}}, 1 \leq i \leq p, \\ a_{i}^{(i)} = k_{i}, \\ a_{j}^{(i)} = a_{j}^{i - 1} - k_{i} a_{i - j}^{(i - 1)}, 1 \leq j \leq i - 1, \\ E_{i} = (1 - k_{i}^{2}) E_{i - 1} . \end{matrix}

(12)

(3)

$i = i + 1$ . If $i > p$ , then go to (4), or return to (2).

(4)

The final solution is given as follows:

\begin{matrix} a_{j} = a_{j}^{(p)}, 1 \leq j \leq p . \end{matrix}

(13)

3.3. Algorithm Description

ALPS is given as follows. First, a routing tree is established in the network initialization stage, where SINK node acts as its root. SINK node periodically broadcasts synchronization packets, which include timestamp, to the lower levels of the tree. When a child node receives the packet, it extracts the timestamp and calculates the difference (clock offset, which is used as the input of ALPS) between the local clock and the timestamp and rebroadcasts the synchronization packet only with its own local timestamp. Then, the child node calculates the prediction coefficients $a_{i}$ according to previous clock offset samples $Δ T_{k - 1}, Δ T_{k - 2}, \dots, Δ T_{k - p}$ , as Section 3.2 describes. ALPS distributively runs on every node independently. Each node calculates its prediction coefficients based on the measurements of its own clock errors and calibrates its clock independently. For the first p samples, when estimating $Δ T_{k}$ ( $k = p + 1$ ), we just set $a_{i} = 1$ for $i = 1$ and $a_{i} = 0$ for $i = 2, \dots, k - 1$ . Finally, we substitute $a_{i}$ ( $i = 1,2, \dots, p$ ) and $Δ T_{k - 1}, Δ T_{k - 2}, \dots, Δ T_{k - p}$ into (4) to predict $Δ T_{k}$ . $\hat{Δ T_{k}}$ is used to calibrate the child node's local clock, in order to make the clocks between the parent node and the child node relatively synchronized right before the next synchronization cycle.

The method to calculate $\hat{Δ T_{k}}$ at Kth synchronization is given in Algorithm 1.

Algorithm 1: The way to calculate ${\hat{Δ T}}_{k}$ .

Calculate ${\hat{Δ T}}_{k}$

Inputs: $Δ T_{k - 1}, Δ T_{k - 2}, \dots, Δ T_{k - p}$

Output: ${\hat{Δ T}}_{k}$

(1) $Φ  (i, j) = f_{1}  (Δ T_{k - 1}, Δ T_{k - 2}, \dots, Δ T_{k - p})$

(2) $R  (j) = f_{2}  (Δ T_{k - 1}, Δ T_{k - 2}, \dots, Δ T_{k - p})$

(3) $Y - W  (P) = f_{3}  (R  (j), Φ  (i, j))$

(4) $a_{1}, a_{2}, \dots, a_{p} = f_{4}  (L - D  (p))$

(5) ${\hat{Δ T}}_{k} = f_{5}  (Δ T_{k - 1}, Δ T_{k - 2}, \dots, Δ T_{k - p}, a_{1}, a_{_{2}}, \dots, a_{p})$

ALPS is described as follows. (1)

The child node maintains a FIFO queue which consists of p registers. The previous p clock offset samples are put into the registers by the order of $Δ T_{k - p}, \dots, Δ T_{k - 2}, Δ T_{k - 1}$ .

(2)

With (9), $Φ (i, j)$ and the autocorrelation function $R (j)$ of clock offsets can be calculated.

(3)

With $Φ (i, j)$ and $R (j)$ , Yule-Walker equations can be created.

(4)

Using Levinson-Durbin iterative algorithm, calculate the prediction coefficients $a_{1}, a_{2}, \dots, a_{p}$ .

(5)

Calculate the next clock offset $\hat{Δ T_{k}}$ by (4).

(6)

Use $\hat{Δ T_{k}}$ for local clock calibration.

(7)

When the next synchronization packet arrives, calculate $Δ T_{k}$ by (3) according to the node's local time and the timestamp which is extracted from the synchronization packet.

(8)

Insert $Δ T_{k}$ at the end of FIFO queue, and go back to step (2).

The complexity of ALPS algorithm is analyzed as follows. The most complex part of ALPS is the Levinson-Durbin algorithm. Within the Levinson-Durbin algorithm, the most complicated calculation is resolving the $k_{i}$ , which requires a nested loop with complexity $O (p^{2})$ , where p is the prediction order. Therefore, the complexity of the whole ALPS is $O (p^{2})$ .

4. Performance Evaluation

To evaluate the performance of ALPS, we implemented it in a real testbed, as shown in Figure 4. In our experiments, we adopt CTP (collection tree protocol, commonly used in WSN), as the routing algorithm on the nodes. Each node looks for a parent node to be synchronized and transfers data packets to the SINK node hop by hop through this data collection tree, thus forming a tree-based topology. The target hardware platform is Tmote-sky node, and the software platform is Contiki, an open source lightweight embedded operating system widely used in WSN. The Tmote-sky node features an MSP430 MCU and a CC2420 radio transceiver, and the clock frequency is 32768 Hz. In the following experiments, we synchronize the local time generated by the 32768 Hz clock. Thus, one clock tick is equal to 1/32768 s. The Tmote-sky supports complicated calculations and has the ability to store plenty of external data. These advantages of Tmote-sky facilitate the ALPS implementation.

Figure 4

Indoor testbed.

In order to obtain the clock readings of parent nodes and their children nodes at the same time, a pulse signal was sent periodically to these nodes. The nodes recorded and output their clock readings upon receiving the pulse signal. In this way, we can periodically sample the clocks of the synchronization nodes to be tested.

The experimental scenario is a multihop wireless sensor network. The default experiment configuration parameters are given in Table 1.

Table 1

Experimental configuration.

Synchronization model	Master-slave
Number of tests	10
Duration	24 hrs
Prediction order	3
Number of node pairs	40
Largest hops	7
Synchronization interval	2 s
Skew range	±30 ppm
Synchronization packet length	20 bytes

The experiment is based on tree topology network. Since we are more concerned with the synchronization errors between parent nodes and children nodes, we have only analyzed synchronization performance among parent nodes and their children nodes. The analysis of the synchronization errors for the whole network will be in our future work.

4.1. Prediction Order P

From analysis in Section 3.1, we know that synchronization accuracy is highly related to the prediction order p. So we explore the relationship between the MSE $E_{n}$ and p by experiment. For every value of p within range 1–7, we determine $E_{n}$ with each test lasting 24 hours and identify the relationship between $E_{n}$ and p as shown in Figure 5.

Figure 5

Relationship between MSE of synchronization errors $E_{n}$ and prediction order p.

As Figure 5 demonstrates, $E_{n}$ declines quickly as p increases when p is small. When $p \geq 3$ , the decrease of $E_{n}$ becomes slow with the increase of p and gradually becomes trivial. Considering the limited computing capability of nodes, we have to strike for a balance between the prediction error and the computational complexity. Since $E_{n}$ changes slightly as p increases when p is bigger than 3 and the computational complexity is proportional to the square of p, we set p as 3. When p is 3, the number of calculations and operations of ALPS is quite limited. Moreover, our hardware platform T-more sky supports complicated calculations and has an external flash with a capacity of 1024 KB for external data storage. Therefore, the ALPS is applicable in our hardware platform.

4.2. Comparison with DMTS and PulseSync

Delay measurement time synchronization (DMTS) [13] is based on the estimation of all delays involved in time synchronization message transfer path, and the delay is calculated by the length and the transmission rate of synchronization packet. PulseSync [16] is presented to reduce the global synchronization errors by making the synchronization messages disseminated as fast as possible. And the clock skew is estimated by least-squares linear regression (LSLR) on eight data points (8LR). In our experiments, we evaluate DMTS, PulseSync, and ALPS algorithms on the same platform, the Tmote-sky platform.

To compare ALPS with DMTS and PulseSync, we implemented these algorithms into the testbed in three experiments. In each experiment, the SINK node periodically broadcasts synchronization messages to the whole network, and the other nodes receive the synchronization messages and run DMTS, PulseSync, and ALPS, respectively, and calibrate their clocks to be synchronized with the SINK.

Figure 6 plots the histogram of the synchronization errors of the DMTS, PulseSync, and ALPS algorithms, and the results are also summarized in Table 2. As shown in Table 2, the MSE of ALPS declines by 41% and 24%, respectively, compared with DMTS and PulseSync. This is because DMTS compensates the random synchronization delay with a fixed value, while PulseSync and ALPS use the historical data points to estimate the current synchronization error. The difference between PulseSync and ALPS is analyzed as follows. PulseSync uses eight data points (8LR) where the weights of all sample points are equal for estimation. Therefore, the degree of freedom (DOF) of PulseSync is only two (clock offset and skew) although it has eight data points. On the other hand, the prediction coefficients in ALPS are not equal and adaptively change with time (as shown in Section 3.2), so the DOF of ALPS is equal to the prediction order p. In this experiment, p is 3.

Table 2

Statistics of synchronization errors.

	DMTS	PulseSync	ALPS
Average error (μs)	31.34	25.26	19.33
Mean square error (μs)	40.22	31.37	23.76
Percentage of time error less than or equal to average error	45	52	63

Figure 6

Histogram of synchronization errors.

In short, PulseSync uses eight samples with the DOF as two. However, although ALPS only uses three data points, its DOF is three. Apparently, the efficiency of ALPS is higher than PulseSync.

Figure 7 depicts the synchronization errors of PulseSync and ALPS along the timeline for 1000 samples (2 s per sample). Compared with Figure 3 (without prediction), we can find that in ALPS the variance of errors is smaller, and the outliers are less and are more stable.

Figure 7

Synchronization errors of PulseSync and ALPS over time.

Through analysis on data of synchronization errors, we can get error distribution falling in different ranges. As demonstrated by Figure 8, the error distribution of ALPS is more concentrated than DMTS and PulseSync; hence the MSE of ALPS is also smaller than DMTS and PulseSync. 85% and 75% of the errors in ALPS and PulseSync fall in $\pm 1$ clocktick, respectively, whereas almost 100% of the errors in APLS fall in $\pm 3$ clocktick. This indicates that the distribution of synchronization errors in ALPS is more concentrated and falls in a smaller range ( $\pm 1$ clocktick) with a larger probability.

Figure 8

Probability of synchronization errors falling into different ranges.

4.3. Synchronization Cost

Since the synchronization cost is highly correlated with the amount of the synchronization packets (assume the transceiver is turned off when no message is sent or received), we take the number of synchronization packets to represent the synchronization cost.

Considering the scenario where one reference node and n nodes to be synchronized are within a single broadcast domain, the synchronization cost of different schemes is given in Table 3. In RBS, K denotes the number of reference broadcasts. As K increases, the synchronization error goes down while the energy consumption goes up. According to [12], the average synchronization errors of RBS and TPSN are 29.13 μs and 16.9 μs, respectively. The average synchronization error of ALPS is 19.33 μs. As Table 3 demonstrates, ALPS has a big advantage in synchronization cost, which is at least half of both RBS and TPSN. Although ALPS, PulseSync, and DMTS share the same synchronization cost, as shown in Table 2, ALPS has a better performance than PulseSync and DMTS in terms of both average and MSE of synchronization errors.

Table 3

Comparison of synchronization cost.

	ALPS	PulseSync	DMTS	RBS	TPSN
Times of sending	n	n	n	$K (n + 1)$	$2 n$
Times of receiving	n	n	n	$K (n + 1)$	$2 n$

We also compare PulseSync and ALPS in resource consumption. PulseSync uses LSLR to estimate the clock skew, and a typical LSLR needs a single loop with complexity $O (l)$ , where l is the number of historical data points used in LSLR. However, as Section 3.3 analyzed, the complexity of ALPS is $O (p^{2})$ , where p is the prediction order. In our scheme, l and p are equal to 8 and 3, respectively. Compared with PulseSync, ALPS needs a little more computational complexity. This is the price ALPS has to pay for a higher performance. However, we think the tradeoff is definitely acceptable since the complexity only increases by 12.5%.

In summary, ALPS performs the same as RBS and TPSN in synchronization accuracy with a less cost and performs better than PulseSync and DMTS at a similar expense. Therefore, when both performance and cost are taken into consideration, APLS performs better than the other four synchronization schemes.

5. Conclusion

Considering the high temporal correlation of time synchronization errors, this paper proposes ALPS, a synchronization scheme based on adaptive linear prediction. Through linear prediction on the clock offset and adaptively adjusting prediction coefficients, ALPS improves synchronization accuracy without increasing synchronization costs. Experiments on the Tmote-sky platform indicate that ALPS cuts synchronization cost by at least half compared with RBS and TPSN without sacrificing accuracy and performs better than DMTS and PulseSync with the same cost. The MSE of synchronization errors in ALPS declines by 41% and 24% compared to DMTS and PulseSync, respectively.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This work was supported by the National Science & Technology Pillar Program during the 12th Five-Year Plan Period (no. 2012BAJ24B01).

References

Y.-C.

Chaudhari

Serpedin

Clock synchronization of wireless sensor networks

IEEE Signal Processing Magazine 2011 28 1 124 138

10.1109/MSP.2010.938757

2-s2.0-78650452886

Zheng

Y.-C.

Joint time synchronization and localization of an unknown node in wireless sensor networks

IEEE Transactions on Signal Processing 2010 58 3, part 1 1309 1320

10.1109/TSP.2009.2032990

MR2758013

2-s2.0-78650438637

Wang

Gao

Wang

Jin

Time-of-flight-based radio tomography for device free localization

IEEE Transactions on Wireless Communications 2013 12 5 2355 2365

10.1109/twc.2013.040213.121001

2-s2.0-84878708896

Zhong

Msp: multi-sequence positioning of wireless sensor nodes

Proceedings of the 5th ACM International Conference on Embedded Networked Sensor Systems (SenSys ′07)

November 2007

Association for Computing Machinery

15 28

10.1145/1322263.1322266

2-s2.0-51349120589

Wang

Gao

Cheng

Wang

Robust device-free wireless localization based on differential RSS measurements

IEEE Transactions on Industrial Electronics 2013 60 12 5943 5952

10.1109/tie.2012.2228145

2-s2.0-84880052782

Wang

Fang

Chen

Yang

Xing

Cai

LCS: compressive sensing based device-free localization for multiple targets in sensor networks

Proceedings of the 32nd IEEE Conference on Computer Communications (INFOCOM ′13)

April 2013

Turin, Italy

145 149

10.1109/infcom.2013.6566752

2-s2.0-84883117300

Cheung

K. W.

H. C.

W.-K.

Chan

Y. T.

Least squares algorithms for time-of-arrival-based mobile location

IEEE Transactions on Signal Processing 2004 52 4 1121 1128

10.1109/TSP.2004.823465

MR2055420

2-s2.0-1842533429

Huang

Benesty

Elko

G. W.

Mersereau

R. M.

Real-time passive source localization: a practical linear-correction least-squares approach

IEEE Transactions on Speech and Audio Processing 2001 9 8 943 956

10.1109/89.966097

2-s2.0-0035510568

Jiang

Yang

Analysis of positioning error for two-dimensional location system

Mathematical Problems in Engineering 2013 2013 8

163958

10.1155/2013/163958

2-s2.0-84890031524

10.

Niculescu

Nath

Ad hoc positioning system (APS) using AOA

Proceedings of the IEEE Societies 22nd Annual Joint Conference of the IEEE Computer and Communications (INFOCOM ′03)

2003

IEEE

1734 1743

10.1109/INFCOM.2003.1209196

11.

Elson

Girod

Estrin

Fine-grained network time synchronization using reference broadcasts

ACM SIGOPS Operating Systems Review 2002 36 SI 147 163

10.1145/844128.844143

12.

Ganeriwal

Kumar

Srivastava

M. B.

Timing-sync protocol for sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys ′03)

November 2003

ACM

138 149

2-s2.0-11244272924

13.

Ping

Delay measurement time synchronization for wireless sensor networks

2003 IRB-TR-03-013

Intel Research Berkeley Lab

14.

Maróti

Kusy

Simon

Lédeczi

Á.

The flooding time synchronization protocol

Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys ′04)

November 2004

ACM

39 49

2-s2.0-27644533289

15.

Zhong

Chen

On-demand time synchronization with predictable accuracy

Proceedings of the IEEE INFOCOM

April 2011

Shanghai, China

IEEE

2480 2488

10.1109/infcom.2011.5935071

2-s2.0-79960850151

16.

Lenzen

Sommer

Wattenhofer

Optimal clock synchronization in networks

Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (SenSys ′09)

November 2009

Berkeley, Calif, USA

225 238

10.1145/1644038.1644061

2-s2.0-74549148191

17.

Leng

Y.-C.

On clock synchronization algorithms for wireless sensor networks under unknown delay

IEEE Transactions on Vehicular Technology 2010 59 1 182 190

10.1109/TVT.2009.2028147

2-s2.0-76849095540

18.

Leng

Y.-C.

Low-complexity maximum-likelihood estimator for clock synchronization of wireless sensor nodes under exponential delays

IEEE Transactions on Signal Processing 2011 59 10 4860 4870

10.1109/TSP.2011.2160857

MR2882988

2-s2.0-80052891363

19.

Hamilton

B. R.

Zhao

ACES: Adaptive clock estimation and synchronization using Kalman filtering

Proceedings of the 14th Annual International Conference on Mobile Computing and Networking, (MobiCom ′08)

September 2008

152 162

10.1145/1409944.1409963

2-s2.0-60149107534

20.

Yang

Pan

Cai

Adaptive clock skew estimation with interactive multi-model kalman filters for sensor networks

Proceedings of the IEEE International Conference on Communications (ICC ′10)

May 2010

IEEE

1 5

10.1109/icc.2010.5502549

2-s2.0-77955358783

21.

Jin

Fang

Chen

Yang

Liu

Yin

Voltage-aware time synchronization for wireless sensor networks

International Journal of Distributed Sensor Networks 2014 2014 13

285265

10.1155/2014/285265

22.

Leng

Y.-C.

On joint synchronization of clock offset and skew for Wireless Sensor Networks under exponential delay

Proceedings of the IEEE International Symposium on Circuits and Systems: Nano-Bio Circuit Fabrics and Systems (ISCAS ′10)

June 2010

IEEE

461 464

10.1109/iscas.2010.5537647

2-s2.0-77956007097

23.

Jeske

D. R.

On maximum-likelihood estimation of clock offset

IEEE Transactions on Communications 2005 53 1 53 54

10.1109/tcomm.2004.840668

2-s2.0-14044261222

24.

Chen

Zhang

Chen

H.-H.

Sun

Feedback-based clock synchronization in wireless sensor networks: a control theoretic approach

IEEE Transactions on Vehicular Technology 2010 59 6 2963 2973

10.1109/tvt.2010.2049869

2-s2.0-77954597619

25.

Castiglioni

Levinson-durbin algorithm

Encyclopedia of Biostatistics 2005

John Wiley & Sons

Time Synchronization for Wireless Sensor Networks Using Adaptive Linear Prediction

Abstract

1. Introduction

2. Motivation

3. Algorithm

3.1. Linear Prediction Model

3.2. Calculation of the Prediction Coefficient a i

3.3. Algorithm Description

Algorithm 1: The way to calculate Δ T ^ k .

4. Performance Evaluation

4.1. Prediction Order P

4.2. Comparison with DMTS and PulseSync

4.3. Synchronization Cost

5. Conclusion

Footnotes

Conflict of Interests

Acknowledgment

References

3.2. Calculation of the Prediction Coefficient $a_{i}$

Algorithm 1: The way to calculate ${\hat{Δ T}}_{k}$ .