# Extended Kalman Filter-Based Approach for Autonomous Synchronization and Ranging in GPS-Denied Environments

Authors: Xiaobo Gu; Weiqiang Tan; Di Zhang; Yudong Lu; Ruidian Zhan
Journal: Complexity
 (2020)

---

## Abstract

Network ranging and clock synchronization based on two-way timing stamps exchange mechanism in complex GPS-denied environments is addressed in this paper. An estimator based on the Extended Kalman filter (EKF) is derived, according to which, the clock skew, clock offset, and ranging information can be jointly estimated. The proposed estimator provides off-line computation by storing the transmitting timing stamps in advance and could be implemented in asymmetrical and asynchronous scenarios. The simulation results show that the proposed estimator achieves a relative good performance than the existed estimators. In addition, a new Bayesian Cramér–Rao Lower Bound (B-CRLB) is derived. Numerous simulation results show that the proposed estimator meets the B-CRLB.


---

## Body

## 1. Introduction

The Unmanned Autonomous System (UAS) [1–3] has become a hotspot in the past decades with the development of technology. In order to carry out unmanned and autonomous missions, the real-time information of positions, velocities, and timing tags of the system agents are required to be collected. A common approach is to deploy Global Positioning System (GPS) receivers on the network members, which is able to provide precise and accurate Positioning, Velocity, and Timing (PVT) service [4]. However, such a design is no longer available in the complex scenarios where GPS service is not sky visible or of low quality: underwater, valley, indoors, and underground. To solve this problem, the fixed anchor nodes with known positions are implemented to substitute for the PVT service of GPS [5–8]. By broadcasting its timing information, the network agents in the certain area could be able to perform relative positioning, motion estimation and cooperative missions by way of Time of Arrival (TOA) [9] and Time Difference of Arrival (TDOA) [10] in complex environments. It is noted that achieving time synchronization among the anchor nodes is the first step to carry out the subsequence missions.Normally, the anchor nodes are of low overall cost, which implies that the on-board oscillators are not highly qualified and the measurement devices are not absolutely accurate. Moreover, the nodes might be affected by the external environmental changes as well. These factors bring a problem that the impacts owing to the relative clock skews and offsets between the clocks could not be ignored [11]. How to correct these errors becomes paramount, especially for the UASs which require all the anchor nodes to provide the synchronized timing tags. Furthermore, power consumption is another important issue for the low-end sensor nodes. Therefore, the message transaction times among the anchor nodes and the message itself should be as few as possible.In order to estimate both clock skew and clock offset under unknown delay, a Maximum Likelihood-like Estimator (MLLE) was derived in [12]. A step further, Leng and Wu proposed a Low Complexity Least Square (LCLS) [13] method which outperforms MLLE. Rajan and van der Veen proposed a Global Least Square (GLS) method [14], which was an extension of the LCLS estimator and had the function of jointly estimating the clock offsets, clock skews, and relative distances in an anchor network or even in an anchorless network [15]. An algorithm based on the alternating direction method of multipliers was proposed in [16], and the simulations results show that it outperforms the distributed least squares algorithm. In addition, Luo and Wu proposed an approach based on Kalman Filter (KF) [17], according to which, the accumulated clock offsets and clock skews were estimated once each pair of forward link and corresponding reverse link was collected. A similar scheme was also proposed in [18], which extended the state estimation model to a clock adjustment approach.To the best of our knowledge, the existed estimators based on two-way timing stamp exchange mechanism and the KF require both the information of the forward and reverse links to difference away the time of flight when performing estimation. This kind of property leads to two problems: one is that there might be a long idle time especially when the time interval between each round transaction is very long and the other problem is that this type of structure could not deal with the circumstance of transaction link loss.The main contribution of this paper is to propose a novel estimator in the context of complex environments, by which the unknown clock skew, clock offset, and propagation delay can be jointly estimated. The proposed estimator adopts EKF to iteratively update the state estimation on clock parameters and ranging measurements. The two-way timing stamp exchange mechanism is implemented as a basic element to establish the communication network. Moreover, for the sake of decreasing the burden on memory, the transmitting time of each node are recorded in advance so that the EKF estimator can provide explicit off-line computation of the estimation error confidence intervals, since these do not depend on the real-time measurements. Unlike the LS-based estimators, which are less than desirable to collect sufficient observations before doing an update in one big calculation, the proposed estimator could perform the updates once a new observation is collected.Notation:⋅k+ stands for ⋅ at time index k+1, diag⋅ denotes a diagonal matrix formed from its vector argument, the transposition is denoted by ⋅T, the matrices are denoted by boldface letters, and IN denotes an identity matrix of size N.


## 2. System Model

We consider a fully asynchronous network consisting ofN anchor nodes. Each anchor node deploys an imperfect frequency source, and the clock skews and the clock offsets among the network agents are not identical due to various reasons. The relative distance between each pair of anchor nodes is fixed and unknown.


### 2.1. Clock Model

Since the free-running clock is not ideal owing to various external and internal reasons, the clock error must be taken into consideration. Lett be the global time and ti be the local time of node i, then the relationship between t and ti could be expressed by(1)ti=ωit+ϕi⇔Citi≜t=αiti+βi,where ωi∈ℝ+ and ϕi∈ℝ denote the clock skew and the initial clock offset of node i, respectively, Citi denotes the global time of node i at local time ti, and αi∈ℝ+ and βi∈ℝ are virtual parameters derived from ωi and ϕi. For an autonomous time synchronization system, generally, a real or virtual clock is elected as the reference. Let node 1 be the reference in this paper, that is to say, ω1=1andϕ1=0, which is equivalent to α1=1andβ1=0. Comparing the two equations in (1) and extending to a vector form yields(2)α=1N−1⊘ω,β=−ϕ⊘ω,where ω=ω2,…,ωNT∈ℝ+N−1×1, ϕ=ϕ2,…,ϕNT∈ℝN−1×1, α=α2,…,αNT∈ℝ+N−1×1, and β=β2,…,βNT∈ℝN−1×1.It is worth noting that the clock skew might vary versus time and the clock drift term might not be ignored in some cases. However, the proposed model could be reasonable for a small period of time and has been largely adopted in the network clock synchronization literature.


### 2.2. Ranging Model

The two-way timing stamp exchange mechanism with a centralized scenario, as shown in Figure1, is implemented to realize time synchronization and ranging in this paper. The two nodes are capable of communicating with each other with a master-slave structure. For the kth forward link between node i and node j, two timing stamps {T1,ijk,T2,ijk} are collected by this round of communication, which represent the transmitting time instant and reception time instant, respectively. Similarly, the timing stamps {T3,ijk,T4,ijk} could be collected by the reverse link as well. All the data of two-way communication timing stamps are stored in the center processing unit to preform estimation. The kth forward link and reverse link can be modelled as(3)CjT2,ijk+n1k−CiT1,ijk+n2k=τi,j+n3k,(4)CiT4,ijk+n4k−CjT3,ijk+n5k=τj,i+n6k,where n1k,n2k,n4k,n5k∼N0,σp2} and n3k,n6k∼N0,σq2 are independent aggregate Gaussian noise variables, which originate from measurements and space disturbances, respectively. τi,j denotes the propagation delay between node i and node j. Since the relative positions of the anchor nodes are fixed, the propagation delays of the forward links and reverse links for each pair of master and slave nodes are identical, namely, τi,j=τj,i. It can be seen that the maximum number of direct communication links is L=N!/N−2! when there is a full connection topology. The unknown propagation delay is expressed as τ=τ1,2,…,τ1,N,τ2,3,…,τ2,N,τN−1,N,T∈ℝL/2×1. Substituting (1) into (3) and (4) yields(5)αiT1,ijk=αjT2,ijk−βi+βj−τi,j+αjn1k−αin2k−n3k,(6)αiT4,ijk=αjT3,ijk−βi+βj+τi,j−αin4k+αjn5k+n6k.Figure 1
Two-way timing stamp exchange mechanism between nodei and node j. The solid (dashed) lines denote the forward (reverse) links.Rearranging (5) and (6) yields(7)T2,ijk=αiT1,ijkαj+βiαj−βjαj+τi,jαj−n1k+αin2kαj+n3kαj,(8)T4,ijk=αjT3,ijkαi−βiαi+βjαi+τi,jαi−n4k+αjn5kαi+n6kαi.


### 2.3. Proposed Estimator

By combining the clock model and ranging model, a new state estimation model is proposed in this paper. According to this model, the clock error and ranging error could be jointly considered and estimated by the discrete state estimation method.Substituting (2) into (5) and (6) leads to(9)T2,ijk=T1,ijkωjωi−ϕiωjωi+ϕj+τi,jωj−n1k+n2kωjωi+n3kωj,(10)T4,ijk=T3,ijkωiωj−ϕjωiωj+ϕi+τi,jωi−n4k+n5kωiωj+n6kωi.It is worth noting that the transmitting time seriesT1,ijk and T3,ijk are timing tags recorded by the member nodes. For the sake of convenience and building up the discrete time state model, they normally are set as periodic series. In this case, T1,ijk and T3,ijk could be considered as known parameters, and the left sides of (7) and (8) could be considered as observations. The state estimation could be updated once a new observation has been collected. Therefore, this process can be expressed by a nonlinear state estimation model:(11)Xk+=AXk+rk,zk=fkXk+vk,where the unknown state matrix Xk=ω,ϕ,τT∈ℝ2N−2+L/2×1. A=I2N−2+L/2 and vk are white Gaussian, independent random processes with zero mean and covariance matrix ErkrkT=Rk∈ℝ2N−2+L/2×2N−2+L/2 and EvkvkT=Qk∈ℝ1×1. fkXk varies versus the direction of the link. From (9) and (10), we can infer that if the transmission direction is from node i to node j, the observation equation follows (9), otherwise it follows (10). The estimation could be performed by an extended Kalman filter (EKF) in this case. In addition, if the two-way timing stamps exchange mechanism operates between the master and slave, the observation function fkXk can be simplified as T1,ijkωj+ϕj+τi,jωj and T3,ijk/ωj−ϕj/ωj+τi,j, respectively.Based on the discussions above, the proposed EKF estimator is expressed by Algorithm1.Algorithm 1:Proposed EKF estimator.
Require:T1,ij1,T1,ij2,…,T1,ijKi, T3,ij1,T3,ij2,…,T3,ijUi, K∈ℕ, σp, σq,X^0|0, P0|0(1)
m=0(2)
repeat(3)
m=m+1(4)
X^m|m−1=AX^m−1|m−1(5)
Pm|m−1=APm−1|m−1AT+Rm(6)
ifj⟶ithen(7)
zm=T4,iju(8)
fmXm=T3,ijk/ωj−ϕj/ωj+τi,j, if i==1(9)
fmXm=T3,ijkωi/ωj−ϕjωi/ωj+ϕi+τi,jωi, if i!=1(10)
else(11)
zm=T2,iju(12)
fmXm=T1,ijkωj−ϕiωj+ϕj+τi,jωj, if i==1(13)
fmXm=T1,ijkωj/ωi−ϕiωj/ωi+ϕj+τi,jωj, if i!=1(14)
Fm=∂fm/∂Xm|Xm=X^m|m−1(15)
Km=Pm|m−1FmTQm+FmPm∣m−1FmT−1(16)
X^m|m=X^m|m−1+Kmzm−fmX^m|m−1(17)
Pm|m=I−KmFmPmm−1|(18)
end if(19)
untilm=Ki+UiRemark 1 (off-line computation).
Note that the matricesK and Pm|m can be computed off-line; the reason is that they do not depend on the timing stamp data of reception. Therefore, the computation of X^ can be performed very rapidly on the center processing unit. It can be found that one disadvantage of EKF is that it might take a large amount of memories to store the transmission data especially when the data is large, but this problem could be easily solved by setting the transmission time instants periodically.Remark 2 (real-time process).
Compared with the existed LS-based estimators, which need to collect the information with respect to forward links and reverse links as much as possible to improve the estimation accuracy, EKF could update its estimation once there is a new observation of a forward or a reverse link. On the contrary, although the Kalman-filter-based algorithms proposed in [17, 18] are also able to carry out real-time processing, the symmetrical links are required to eliminate the nuisance term. In addition, another advantage owing to not to put any constraint on symmetrical structure is that the update rate could be faster than those symmetrical required algorithms. This kind of feature is paramount especially for the low power consumption systems, such as the sleep wake-up scheduling system.Remark 3 (one-way estimation).
According to (7) and (8), we can infer that the EKF estimator will not lose its entire function even when the transmitting device or receiving device on any node suddenly stops working. For instance, if (10) could not be observed, that is to say, only a series of information with respect to (9) can be used to perform estimation, in this case, the estimation rate and the robustness of the estimator could be improved.


## 2.1. Clock Model

Since the free-running clock is not ideal owing to various external and internal reasons, the clock error must be taken into consideration. Lett be the global time and ti be the local time of node i, then the relationship between t and ti could be expressed by(1)ti=ωit+ϕi⇔Citi≜t=αiti+βi,where ωi∈ℝ+ and ϕi∈ℝ denote the clock skew and the initial clock offset of node i, respectively, Citi denotes the global time of node i at local time ti, and αi∈ℝ+ and βi∈ℝ are virtual parameters derived from ωi and ϕi. For an autonomous time synchronization system, generally, a real or virtual clock is elected as the reference. Let node 1 be the reference in this paper, that is to say, ω1=1andϕ1=0, which is equivalent to α1=1andβ1=0. Comparing the two equations in (1) and extending to a vector form yields(2)α=1N−1⊘ω,β=−ϕ⊘ω,where ω=ω2,…,ωNT∈ℝ+N−1×1, ϕ=ϕ2,…,ϕNT∈ℝN−1×1, α=α2,…,αNT∈ℝ+N−1×1, and β=β2,…,βNT∈ℝN−1×1.It is worth noting that the clock skew might vary versus time and the clock drift term might not be ignored in some cases. However, the proposed model could be reasonable for a small period of time and has been largely adopted in the network clock synchronization literature.


## 2.2. Ranging Model

The two-way timing stamp exchange mechanism with a centralized scenario, as shown in Figure1, is implemented to realize time synchronization and ranging in this paper. The two nodes are capable of communicating with each other with a master-slave structure. For the kth forward link between node i and node j, two timing stamps {T1,ijk,T2,ijk} are collected by this round of communication, which represent the transmitting time instant and reception time instant, respectively. Similarly, the timing stamps {T3,ijk,T4,ijk} could be collected by the reverse link as well. All the data of two-way communication timing stamps are stored in the center processing unit to preform estimation. The kth forward link and reverse link can be modelled as(3)CjT2,ijk+n1k−CiT1,ijk+n2k=τi,j+n3k,(4)CiT4,ijk+n4k−CjT3,ijk+n5k=τj,i+n6k,where n1k,n2k,n4k,n5k∼N0,σp2} and n3k,n6k∼N0,σq2 are independent aggregate Gaussian noise variables, which originate from measurements and space disturbances, respectively. τi,j denotes the propagation delay between node i and node j. Since the relative positions of the anchor nodes are fixed, the propagation delays of the forward links and reverse links for each pair of master and slave nodes are identical, namely, τi,j=τj,i. It can be seen that the maximum number of direct communication links is L=N!/N−2! when there is a full connection topology. The unknown propagation delay is expressed as τ=τ1,2,…,τ1,N,τ2,3,…,τ2,N,τN−1,N,T∈ℝL/2×1. Substituting (1) into (3) and (4) yields(5)αiT1,ijk=αjT2,ijk−βi+βj−τi,j+αjn1k−αin2k−n3k,(6)αiT4,ijk=αjT3,ijk−βi+βj+τi,j−αin4k+αjn5k+n6k.Figure 1
Two-way timing stamp exchange mechanism between nodei and node j. The solid (dashed) lines denote the forward (reverse) links.Rearranging (5) and (6) yields(7)T2,ijk=αiT1,ijkαj+βiαj−βjαj+τi,jαj−n1k+αin2kαj+n3kαj,(8)T4,ijk=αjT3,ijkαi−βiαi+βjαi+τi,jαi−n4k+αjn5kαi+n6kαi.


## 2.3. Proposed Estimator

By combining the clock model and ranging model, a new state estimation model is proposed in this paper. According to this model, the clock error and ranging error could be jointly considered and estimated by the discrete state estimation method.Substituting (2) into (5) and (6) leads to(9)T2,ijk=T1,ijkωjωi−ϕiωjωi+ϕj+τi,jωj−n1k+n2kωjωi+n3kωj,(10)T4,ijk=T3,ijkωiωj−ϕjωiωj+ϕi+τi,jωi−n4k+n5kωiωj+n6kωi.It is worth noting that the transmitting time seriesT1,ijk and T3,ijk are timing tags recorded by the member nodes. For the sake of convenience and building up the discrete time state model, they normally are set as periodic series. In this case, T1,ijk and T3,ijk could be considered as known parameters, and the left sides of (7) and (8) could be considered as observations. The state estimation could be updated once a new observation has been collected. Therefore, this process can be expressed by a nonlinear state estimation model:(11)Xk+=AXk+rk,zk=fkXk+vk,where the unknown state matrix Xk=ω,ϕ,τT∈ℝ2N−2+L/2×1. A=I2N−2+L/2 and vk are white Gaussian, independent random processes with zero mean and covariance matrix ErkrkT=Rk∈ℝ2N−2+L/2×2N−2+L/2 and EvkvkT=Qk∈ℝ1×1. fkXk varies versus the direction of the link. From (9) and (10), we can infer that if the transmission direction is from node i to node j, the observation equation follows (9), otherwise it follows (10). The estimation could be performed by an extended Kalman filter (EKF) in this case. In addition, if the two-way timing stamps exchange mechanism operates between the master and slave, the observation function fkXk can be simplified as T1,ijkωj+ϕj+τi,jωj and T3,ijk/ωj−ϕj/ωj+τi,j, respectively.Based on the discussions above, the proposed EKF estimator is expressed by Algorithm1.Algorithm 1:Proposed EKF estimator.
Require:T1,ij1,T1,ij2,…,T1,ijKi, T3,ij1,T3,ij2,…,T3,ijUi, K∈ℕ, σp, σq,X^0|0, P0|0(1)
m=0(2)
repeat(3)
m=m+1(4)
X^m|m−1=AX^m−1|m−1(5)
Pm|m−1=APm−1|m−1AT+Rm(6)
ifj⟶ithen(7)
zm=T4,iju(8)
fmXm=T3,ijk/ωj−ϕj/ωj+τi,j, if i==1(9)
fmXm=T3,ijkωi/ωj−ϕjωi/ωj+ϕi+τi,jωi, if i!=1(10)
else(11)
zm=T2,iju(12)
fmXm=T1,ijkωj−ϕiωj+ϕj+τi,jωj, if i==1(13)
fmXm=T1,ijkωj/ωi−ϕiωj/ωi+ϕj+τi,jωj, if i!=1(14)
Fm=∂fm/∂Xm|Xm=X^m|m−1(15)
Km=Pm|m−1FmTQm+FmPm∣m−1FmT−1(16)
X^m|m=X^m|m−1+Kmzm−fmX^m|m−1(17)
Pm|m=I−KmFmPmm−1|(18)
end if(19)
untilm=Ki+UiRemark 1 (off-line computation).
Note that the matricesK and Pm|m can be computed off-line; the reason is that they do not depend on the timing stamp data of reception. Therefore, the computation of X^ can be performed very rapidly on the center processing unit. It can be found that one disadvantage of EKF is that it might take a large amount of memories to store the transmission data especially when the data is large, but this problem could be easily solved by setting the transmission time instants periodically.Remark 2 (real-time process).
Compared with the existed LS-based estimators, which need to collect the information with respect to forward links and reverse links as much as possible to improve the estimation accuracy, EKF could update its estimation once there is a new observation of a forward or a reverse link. On the contrary, although the Kalman-filter-based algorithms proposed in [17, 18] are also able to carry out real-time processing, the symmetrical links are required to eliminate the nuisance term. In addition, another advantage owing to not to put any constraint on symmetrical structure is that the update rate could be faster than those symmetrical required algorithms. This kind of feature is paramount especially for the low power consumption systems, such as the sleep wake-up scheduling system.Remark 3 (one-way estimation).
According to (7) and (8), we can infer that the EKF estimator will not lose its entire function even when the transmitting device or receiving device on any node suddenly stops working. For instance, if (10) could not be observed, that is to say, only a series of information with respect to (9) can be used to perform estimation, in this case, the estimation rate and the robustness of the estimator could be improved.


## 3. Bayesian Cramér–Rao Lower Bound

The Cramér–Rao lower bound on the estimation error states(12)EX^−XX^−XT≥J−1,where J is the Fisher information matrix, which obeys the recursion [19]:(13)Jk+1=Dk22−Dk12TJk+Dk11−1Dk12,where(14)Dk11=E−∂2∂Xk∂TXklogpXk+|Xk,(15)Dk12=E−∂2∂Xk∂TXk+logpXk+|Xk,(16)Dk22=E−∂2∂Xk+∂TXk+logpXk+|Xk+E−∂2∂Xk+∂TXk+logpzk+|Xk+.From (11), it follows that(17)−logpXk+|Xk=c1+12Xk+−AXkT⋅R−1Xk+−AXk,(18)−logpzk+|Xk+=c2+12zk+−fk+X^k+T⋅Q−1zk+−fk+X^k+,where c1 and c2 are constants. A straightforward calculation of (14)–(18) leads to Dk11=ATR−1A, Dk12=−ATR−1, and Dk22=R−1+∂fk+X^k+/∂X^k+TQ−1∂fk+X^k+/∂X^k+. Hence, (13) can be written as(19)Jk+1=R−1+∂fk+X^k+∂X^k+TQ−1∂fk+X^k+∂X^k+−R−1TAJk+ATR−1A−1ATR−1.Applying the matrix inversion lemma, (19) can be further simplified as(20)Jk+1=R+AJk−1AT−1+∂fk+X^k+∂X^k+TQ−1∂fk+X^k+∂X^k+.The inverse of the Fisher information matrix forθ could be written as [20](21)I−1θ=J−1.


## 4. Simulations

In this section, we provide a scenario with asynchronous links to evaluate the performance of the EKF estimator. The number of the nodesN = 10, and each node is capable of performing two-way communications with the other nodes. All the member nodes are assumed to be visible during the signal transaction process. The locations of the member nodes are uniformly distributed variables in the region of 1km×1km. The propagation speed is the speed of light. The clock skew and clock offset of the slave nodes are randomly distributed in the range 0.9998,1.0002 and −2,2s, respectively. The transmission time interval for both forward links and reverse links is 5 s, and the reverse links always transmit backwards by 3 s. The noise standard deviations σp=1×10−3 and σq=1×10−3. The Root Mean Square Error (RMSE) is adopted as the performance metric. All the given results are averaged over 10,000 Monte Carlo runs.In order to investigate the performance of the proposed method, the conventional Kalman estimator based on the traditional clock model and the iterative form of LCLS are compared in this section. Figure2 shows the RMSEs of the unknown parameters by applying different estimators. As shown in the figure, the iterative LCLS achieve the best performance than the other estimators. The proposed EKF converges at a slower rate than the conventional KF, but performs relatively better on the estimation precision after a long iteration time. Compared with the other two estimators, the precision degradation of the EKF originates from the nonlinear process of the observation equation, and it could be improved by omitting a virtual parameter transforming process. However, the proposed EKF estimator has its own superiorities mentioned in Section 2, namely, its update rate is two times faster than the other estimators and it frees the restriction on the symmetrical structure. Meanwhile, it is able to provide off-line computation.Figure 2
RMSEs of the estimated clock skewωj (a), offset ϕj (b), and propagation delay τi,j (c) with respect to the number of iterations.
(a)(b)(c)Furthermore, the performances of the estimators for varying noise deviation are presented in Figure3. The deviation of the time markers and propagation disturbance are set in the range [−88, −70] dB seconds. It is noted that the meter level accuracies could be achieved by the proposed EKF estimator when the Signal-to-Noise Ratio (SNR) is high. In addition, the proposed estimator is able to carry out range estimation directly, which is coupled with the estimation process of clock parameter tracking.Figure 3
RMSEs of the estimated clock skewωj (a), offset ϕj (b), and propagation delay τi,j (c) with respect to the varying noise deviations.
(a)(b)(c)


## 5. Conclusion

In this work, the problem of joint clock synchronization and ranging for UAS in a complex GPS-denied environment is addressed. The proposed EKF estimator is shown to achieve nearly the same performance compared with the existed Kalman-filter-based estimator, but can provide off-line computations. By comparing its performance bounds with the B-CRLB, it has been found that although the EKF estimator suffers performance degradation, it is capable of estimating the clock skew even in the context of one-way communication and updating the estimates faster than the existed estimators. Furthermore, it has the function of estimating the unknown propagation delay between each node. Future research directions include the extension of recursive joint clock synchronization and localization estimation in anchorless networks.



---

*Source: 8836584-2020-12-19.xml*