# Comparing Digital Phase-Locked Loop and Kalman Filter for Clock Tracking in Ultrawideband Location System

Authors: Qian Gao; Chong Shen; Kun Zhang
Journal: Journal of Electrical and Computer Engineering
 (2018)

---

## Abstract

For timing and synchronization system, digital phase-locked loop (DPLL) and Kalman filter all have been widely used as the clock tracking and clock correction schemes for the similar structure and properties. This paper compares the two schemes used for ultrawideband (UWB) location system. The improved Kalman filter is more immune to interference.


---

## Body

## 1. Introduction

Impulse radio ultrawideband (IR-UWB) [1] is considered to be promising for indoor location. To estimate the tags location using time difference of arrival- (TDOA-) based localization, the anchors’ local clocks are required to be fully synchronized with each other [2], but the anchors’ clocks are varied with the running time and temperature drift [3]. The anchors must be synchronized periodically [4]. The location system is as Figure 1 shows. There are four anchors: anchor 1 is selected as the reference anchor and the other three anchors are the passive anchors. The reference anchor sends the clock synchronization packets to its passive anchor, which are represented by the orange lines in Figure 1. The clock synchronization algorithm (Algorithm 1) that we used is one-way message dissemination [5]. The clock variance between the passive anchor’s local clock and its reference anchor is tracked. The data’s arrival time from tag to anchors is corrected for the same time base between the reference and passive anchors. Then the TDOA algorithm effectively gets the tag’s location. So how to track the clock variance between reference-passive anchors is important for UWB location.Algorithm 1
P = A ∗ P ∗ t r a n s A + Q; J = 1 / R + H ∗ P ∗ t r a n s H; O M = measuredError ∗ J ∗ measuredError; if (OM > threshold) && (counter > 20), outlier = 1; measuredError = 0.0; outlier_counter = outlier_counter + 1; if outlier_counter > 8, outlier_counter = 0; counter = 0; end x 0 = x _ 0 + d t; EstimatedTime(i)=x0; else K = P ∗ t r a n s ( H ) ∗ i n v H ∗ P ∗ t r a n s H + R; x = x + K ∗ measuredError;Figure 1
IR-UWB location system diagram.Traditionally, we model the clock time as a continuous function of clock skew (frequency difference)γ and the clock offset (phase difference) θ [6].(1)Cmt=t,Cst=γ·t+θ,where Cmt denotes a reference clock of the sending anchor and Cst denotes the local clock of the receiving anchor. In digital clocks, time is recorded by counting the number of periods of a repeating clock signal. At each rising clock edge of the periodic signal, an integer time counter is incremented.The main problem of network synchronization is to resolve the observed time in (1). The algorithms considered here use a one-way message dissemination approach at the level of discrete clock ticks.Suppose that the anchors all have the features of transmitting and receiving the clock check packets (CCP) with the time stamps, and the initial master anchor transmits a CCP with periodT, as shown in Figure 2. In the jth round of broadcast message, reference anchor broadcasts a synchronization message CCP at T1,j and the passive anchor records its time T2,j at the reception of that message. Δj denotes the interval between receiving a signal and the following initial local clock tick caused by the clock offset. According to [5], the timing model of the jth broadcast message is given by(2)T2,j≈γ·T1,j+θ+ψj,where ψj is the random variable delay in the transmission.Figure 2
Space-time of reference-passive anchors.The clock tracking is implemented with the main “process” function taking two inputs: (1) The slave anchor CCP receiving time with its time base. (2) The master anchor CCP transmitting time with its time base and the CCP time of flight (TOF).According to Figure3, the clock tracking process uses CCP receiving time and CCP transmitting time and the best estimated time between the master unit and the slave unit. If given the master and slave anchors’ (X,Y,Z) coordinates, the CCP TOF will be obtained by dividing the distance by the speed. At last, clock tracking process draws the real relative clock offset and the best estimated relative clock offset between master and slave units. Digital phase-locked loop (DPLL) and Kalman filter both have been widely used as the clock tracking and clock correction schemes for the similar structure and properties. This paper compares the two schemes used for UWB location system.Figure 3
The relative clock variation by clock tracking.


## 2. Digital Phase-Locked Loop

Digital phase-locked loop (DPLL) is a digital closed-loop automatic control system that can follow the frequency and phase of the input signals [7, 8]. For UWB location system, we consider a second-order DPLL based on ZC-DPLL, as Figure 4 shows.Figure 4
DPLL structure block diagram.Assume thats(t) is the input signal, n(t) is zero mean additive white Gaussian noise, and T0 is the input signal clock period without correction. The input signal s(t) with n(t) is sampled at tk by digital clock to output the loop phase error zk. Ignore the impact of the quantizer; the sequence zk directly comes into the digital filter; by smoothing, the digital filter outputs a more reliable correcting sequence yk to digital clock: yk=Dzzk. The second-order z operator function is(3)Dz=G1+G21-z-1-1,where G1 and G2 are the loop gain factors. Assume that the loop gains of second-order DPLL are K0f and K1f, respectively.(4)yk=K0fzk+K1f∑i=0kzi.In DPLL, correction signalyk is used to control the next period: Tk+1=T0-yk. Adjust Tk until the loop into the locked state Tk is the sample interval: Tk=tk-tk-1,k=1,2,….The sampling timetk is deduced:(5)t^k+1=t^k+T0+K0fzk+K1f∑i=0kzi.


## 3. Kalman Filter

Kalman filter is the solution by the minimum mean square error (MMSE) of the optimal linear filtering [9, 10]. It estimates the current signal value according to the previous estimation and a recent observation data. In the concrete implementation process, the (k+1)th period clock skew and clock drift of the master-slave clock is estimated according to the kth sync cycle information. T is the clock synchronization period; Uθ,k and Uγ,k are the correction of the clock skew and clock offset at the kth clock period, respectively. θk and γk are the kT clock skew and clock offset, respectively. At the moment of (k+1)T, the clock relations between the adjacent clock periods are(6)θk+1=θk-Uθ,k+γk-Uγ,kT+ωθ,kγk+1=γk-Uγ,k+ωγ,where ωθ,k is the clock skew variance and ωγ,k is the clock offset variance. Assume that ωk=ωθ,kωγ,kT; its additive covariance matrix is Q. We define the vector and matrix as follows:(7)xk=θk;γkT,uk=Uθ,k;Uγ,kT.Kalman filter equations by iteration are as follows.(1) Estimation (8) x ^ k + 1 ∣ k = A x k + B u k ,where A=1T01, B=-1-T0-1, xk is the state to be estimated, and uk is the input control vector.(2) MMSE Matrix of the Estimation (9) P k + 1 ∣ k = A P k A T + Q ,where Pk is the MMSE matrix of the estimated xk.(3) Kalman Filter Gain Matrix (10) K k + 1 = P k + 1 ∣ k H k + 1 T R k + 1 + H k + 1 P k + 1 ∣ k H k + 1 T - 1 ,where Rk+1 is the covariance matrix of the observation noise and the measurement matrix Hk+1 is a unit matrix.(4) Correction (11) x ^ k + 1 = x ^ k + 1 ∣ k + K k + 1 z k + 1 - H k + 1 x ^ k + 1 ∣ k .(5) MMSE Matrix (12) P k + 1 = 1 - K k + 1 P k + 1 ∣ k .After Kalman filtering, the correction isx^k+1=[θ^k+1;γ^k+1]T at the (k+1)th clock period. uk+1=x^k+1 is set to make up for the clock skew and clock offset. So the slave anchor’s clock base will make up to the same clock base when the tag’s data arrives.Relative to DPLL, we defineXk=[xk;xk] and define the Kalman gain vector as Kk=[K0k;K1k]. P0=T02/120;0T02fΔk2, where T02/12 is the variance of the initial phase X0; EX02=T02fΔk2;fΔk2=EfΔ/f02 is the normalized variance values of fΔ with zero average distribution. The error is zk=xk-x^k∣k-1+nk=yk-HX^k∣k-1.According to (4)–(7), as k=0,1,2,…, we will get(13)x^k+1=x^k+K0kzk∑i=0kK1izi.Comparing (5) and (13), the recursive types are very similar. The Kalman filter structure is depicted in Figure 5.Figure 5
Kalman filter structure block diagram.


## 4. Comparison and Analysis

According to the above descriptions about Kalman filter and DPLL, we compare the two schemes for UWB indoor location. In DPLL, correction sequences as the output of the signal through digital filtering control the digital clock period until the loop is locked. Kalman filter also abstracts the needed signal through the feedback loop, which uses the former data to estimate the current data. The two schemes use the errorzk through gain factor K to find the optimal estimation. By comparing (5) and (13), we just need to adjust gain factor K so as to get the similar results.We define the passive anchor clock variance error between the real clock variance and the optimal estimated clock variance asek=xk-x^k∣k-1. Using the reference-passive anchors data backhaul sending time, data receiving time, and the optimal estimated time with the data flight time, the location engine in the server will calculate the relative clock offset variance.The paper uses Matlab for simulation. Assume that the anchors’ coordinates are anchor1 (1.1,1.17,1.93) and anchor2 (11.3,1.17,1.21). The TOF of the reference anchor1 to the passive anchor2 is TOF1,2=0.000000034123193 s. For second-order DPLL, variable loop gains with lower bounds K0f=0.2, K1f=0.05, Eb/N0=10.6 dB, σn2/T02=σ^n2/T02=0.001, and fΔ/f0=0.1. The clock synchronization period is 150 ms. The measurement noise variance is 3e-12; the process noise variance is 5e-12. Alternatively, a more complex multistage in-lock and out-of-lock detection algorithm may be employed, which trades off acquisition, tracking, and false lock performance according to the system requirements. Such tradeoff issues are beyond the scope of this paper [11, 12].As Figure6 shows, the green line is the clock variance difference by Kalman filter and the black line is that by DPLL. They all tend to be stable over time, but the properties of Kalman filter are significantly better than those of DPLL. Kalman filter requires shorter capture time and smaller error.Figure 6
The difference between estimated time and real time.By the theory of hypothesis, in order to give sufficient information for the DPLL to stay locked for continued real-time location system operation with good performance (including coping with a certain packet error/loss rate), we need to send the clock synchronization message more frequently than for Kalman filter. It reduces the air-occupancy needed for clock synchronization messages, which allows more air-time for receiving blink messages. This essentially increases the system tag capacity, especially in the lower data rate and longer preamble modes.


## 5. Improved Algorithms on Kalman Filter

As stated above, Kalman filter is better for clock synchronization indoor UWB location system. Its calculation is based on such an assumption: all measurements are composed of the real signal and additive Gaussian noise. If these assumptions are correct, Kalman filter will effectively get signal from the measurements containing noise. But if the reference anchor’s clock check packets collide with tag’s data packets with TOA or some other mistake challenges in [13], the assumptions are incorrect. Kalman filter will treat the collision or mistake as credible clock variance data, and it calculates by these data. And Kalman filter itself is a kind of low-pass filter; its response and correcting speed are slower. Therefore, the errors generated by the collision will for a long time seriously degrade the performance of the clock synchronization algorithm.This paper proposes a method of monitoring and avoiding the wrong of collisions. Kalman filter gain is as (10) shows, defining an information matrix J as(14)J=Rk+1+Hk+1Pk+1∣kHk+1T-1.J is used to represent the difference between estimated clock error and actual clock error. This information will be used to prompt how well the current input fits the current state of filter.(15)OMk+1=x^k+1-xk+1∗J∗x^k+1-xk+1.If the OM (outlier metric) rises above a preset threshold which is an empirical value, the current input is untrusted. The improved Kalman filter does not update current state but discards this data directly to avoid error packet having a big impact for filter output.In Figures7 and 8, the blue lines are the real clock offsets and the red lines are the estimated clock offset by Kalman filter. We set a big data mistake at 150 s; the estimated clock offset is unable to keep pace with the real clock offset and up and down shocks with Kalman filter in Figure 7. With the resolution of the trustless input, the estimated clock offset is smooth in Figure 8. By comparing Figures 7 and 8, it is clearly seen that the improved Kalman filter enhances the capacity of resisting disturbance.Figure 7
The relative clock offset with big disturbance by Kalman filter.Figure 8
The relative clock offset with big disturbance by improved Kalman filter.


## 6. Conclusion

We have compared DPLL and Kalman filter for UWB indoor location network clock synchronization, and the analysis results show that Kalman filter copes better with clock errors and has better lock performance. And the improved Kalman filter is more immune to interference as the simulation results show.



---

*Source: 5873239-2018-04-18.xml*