# An Efficient TDOA-Based Localization Algorithm without Synchronization between Base Stations

Authors: Sangdeok Kim; Jong-Wha Chong
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

An efficient localization algorithm is proposed by utilizing the time
difference of arrival (TDOA) without synchronization between base stations. Generally, a
TDOA-based localization algorithm requires synchronization between base stations in order to
improve the accuracy of localization. Hence, correlations using wideband signals or wire connections
between base stations have been used to synchronize the base stations; however, these approaches
result in additional operating costs. Thus, the proposed algorithm does not require synchronization
between base stations. The TDOA equations are derived by continuously varying the locations of the
source and the location of a base station. The number of packets necessary for localization is also
reduced. The localization performance of the proposed algorithm is verified with Monte-Carlo
simulations.


---

## Body

## 1. Introduction

Recently, source localization has gained considerable interest for various location-based applications [1], such as missile guidance systems and search systems for missing children. Common localization parameters include the time of arrival (TOA), received signal strength (RSS), and time difference of arrival (TDOA). As discussed in [2], the accuracy of TOA- and TDOA-based localization techniques is better than that of RSS-based localization technique. Moreover, the TOA-based localization technique requires knowledge of the transmission time of the received signal from the transmitter, which is not necessary for TDOA-based localization technique. Thus, we focus on TDOA-based localization technique.The key concept of TDOA-based localization technique is to determine the location of the source by evaluating the difference in arrival time of the signal at spatially separated base stations. To calculate the time difference, the synchronization between the base stations is additionally required by using a synchronization process [3] in practice. The synchronization problem related to TDOA-based localization technique, however, has not been researched before. Previous papers related to TDOA [4, 5] only assume perfect synchronization between base stations. For example, the ranging error is about three meters (i.e., = 10 ns × 3 × 108 m/s). Thus, the localization error is more than three meters according to geometric dilution of precision (GDOP) [6]. In practical applications, the synchronization can be accomplished based on correlation methods using wideband signals or wire connections between base stations. The mismatch between local oscillators of base stations, however, introduces the offsets of carrier frequency and sampling frequency [7].In order to reduce these offsets in localization, symmetric double-sided two-way ranging (SDS-TWR) was proposed in [8]. The SDS-TWR exchanges three packets between a source and a base station; subsequently, two TRW estimates are obtained. Through the average of the two estimates, the sampling frequency offset is decreased. Despite the reduction of the offset, SDS-TWR needs a large number of packets to obtain stable performance [9]. Finally, these packets result in heavy network traffic.To overcome the disadvantage of conventional TDOA-based localization technique, we propose a new TDOA-based localization algorithm based on the mobility of a source. Consecutive locations of a source shed light on feasible TDOA-based localization technique without the synchronization process. Moreover, the proposed algorithm reduces the number of exchanging packets.


## 2. Conventional TDOA Measurement Model

Let thenth base station be located at the point bn≡[xn,yn], where n=1,…,N. The coordinates of the mobile source can be defined as x≡[xs,ys]. Then, in the absence of measurement noise, the estimated distance d^n between the source and nth base station can be modeled as(1)d^n=cTn=x-bn=xs-xn2+ys,m-yn2,where · denotes the L2 norm and Tn is the time (as given by the time at nth base station) at which the transmitted signal from the mobile source is received by the nth base station. The difference of distance between the source and the nth and (n+1)th base stations can be given as(2)d^n+1,n=cTn+1-Tn=dn+1-dn=x-bn+1-x-bn=xs-xn+12+ys-yn+12-xs-xn2+ys-yn2.The conventional TDOA-based localization technique is a problem of solving a set of hyperbolic equations such as (2). The technique, however, requires synchronization between base stations.


## 3. Proposed TDOA Measurement Model

We assume that a mobile source transmits a ranging signal periodically. Additionally, it is reasonable to assume that the initial coordinates are known because many such applications exist (e.g., fireman tracking and missile guidance systems). As an important special case, only two-dimensional location coordinates are considered; however, it is easy to generalize this idea to 3D or multidimensional space.Let thenth base station (BS) be located at the point bn≡[xn,yn], where n=1,…,N. From the assumption of periodic transmission of the localizing signal, the coordinates of the source can be defined as xm≡[xs,m,ys,m], which indicate when the mobile source transmits the mth localizing signal. Likewise, x(m+1)≡[xs,m+1,ys,(m+1)] denotes the transmission of the (m+1)th localizing signal, m=1,…,M. Then, in the absence of TDOA measurement noise, the range difference equation based on the mobility of the source can be given as(3)Km,n=cTm+1,n-Tm,n=dm+1,n-dm,n=xm+1-bn-xm-bn=xs,m+1-xn2+ys,m+1-yn2-xs,m-xn2+ys,m-yn2,where c is the speed of the propagation, Tm,n is the time (as given by the time at nth base station) at which the transmitted signal from the mobile source at the mth position is received by the nth base station.In Figure1, tsync is the synchronization time between the base stations. As shown in Figure 1(a), conventional TDOA is the time difference between T2 and T1. Thus, in the conventional TDOA, only base stations’ clocks need to be synchronized. As shown in Figure 1(b), proposed TDOA is the time difference between Tm,n and T(m+1),n given by time only at one BS. Therefore, proposed TDOA model does not require synchronization process because independent time of each base station is only needed.Figure 1
Comparison of the proposed TDOA to conventional TDOA, (a) conventional TDOA and (b) proposed TDOA.
(a)
(b)


## 4. Proposed Localization Algorithm Using New TDOA Model

Solving the range difference equations is a nonconvex optimization problem. Furthermore, with TDOA noise, the hyperbolae in (3) may not intersect at a single point; that is, (3) is inconsistent. To address this obstacle, we must first linearize the nonlinear equations. By moving the rightmost variable in (3) to the left side and squaring both sides, we find that(4)xs,m+1-xn2+ys,m+1-yn2=Km,n2+2Km,ndm,n+xs,m-xn2+ys,m-yn2.Then, expanding the squares in (4) and rearranging the variables according to the source coordinates generate (5)xs,m+12-2xs,m+1xn+ys,m+12-2ys,m+1yn=Km,n2+2Km,ndm,n+xs,m2-2xs,mxn+ys,m2-2ys,myn.In order to change the nonlinear equation (5) into a linear equation, we subtract (5) for the nth base station from (6) for the (n+1)th base station with the same source coordinates as follows:(6)xs,m+12-2xs,m+1xn+1+ys,m+12-2ys,m+1yn+1=Km,n+12+2Km,n+1dm,n+1+xs,m2-2xs,mxn+1+ys,m2-2ys,myn+1.It follows that(7)2xs,m+1-xs,mxn+1-xn+2ys,m+1-ys,myn+1-yn=Km,n2+2Km,ndm,n-Km,n+12-2Km,n+1dm,n+1.Finally, formulating (7) into matrix form, we have(8)Axm+1=Cm+Axm,where(9)A=2x2-x1y2-y1x3-x1x4-x1x5-x1y3-y1y4-y1y5-y1⋮⋮xN-xN-1yN-yN-1xN+1-xN-1yN+1-yN-1xN+1-xNyN+1-yN,Cm=Km,1Lm,1-Km,2Lm,2Km,1Lm,1-Km,3Lm,3Km,1Lm,1-Km,4Lm,4Km,1Lm,1-Km,5Lm,5⋮Km,N-1Lm,N-1-Km,NLm,NKm,N-1Lm,N-1-Km,N+1Lm,N+1Km,NLm,N-Km,N+1Lm,N+1and x(m+1)=xs,m+1ys,m+1T, xm=xs,mys,mT, and Lm,n=dm,n+d(m+1),n. The superscript T denotes the transpose operation. With the assumption of known initial source coordinates x1, we can calculate L1,n using (10)Lm,n=dm,n+dm+1,n=2dm,n+Km,nsince d1,n=x1-bn can be calculated using the coordinates of both the nth base station bn and the initial source x1. After estimating the second coordinates of the source x2, L2,n can be calculated in the same way.The(m+1)th coordinates of the source can be obtained using the least squares (LS) technique or the total least squares (TLS) technique.


### 4.1. Least Squares Technique

Equation (8) can be rearranged as(11)Axm+1-xm=Cm⟹Axm+1,m=Cm,where x(m+1),m=x(m+1)-xm in order to present noise on the right hand side of the equation. When ΔCm is a zero mean white Gaussian noise vector, we can obtain the LS solution as(12)x^m+1,m=argminxm+1,mΔCm=AHA-1AHCm,where the superscript H denotes the conjugate transpose operation. After estimating the LS solution in (12), the (m+1)th coordinates can be estimated by adding the mth coordinates such that(13)x^LS,m+1=x^m+1,m+xm.


### 4.2. Total Least Squares Technique

Alternatively, the TLS technique can be applied to the estimation of the(m+1)th source coordinates. Note that when A is noisy like Cm, the LS solution is no longer optimal from a statistical point of view as it undergoes bias and increased covariance due to the accumulation of noise errors in AHA. Thus, before the application of the TLS technique, the noise terms on the right hand side of (8) should be incorporated into the left-hand side in (8) as follows:(14)A~x~m+1=C~m⟹Acm,1xm+11=Acm,2xm1,where cm,1=Km,2Lm,2,Km,3Lm,3,…,Km,NLm,N,Km,N+1Lm,N+1,Km,N+1Lm,N+1T and cm,2=Km,1Lm,1,Km,1Lm,1,…,Km,N-1Lm,N-1,Km,N-1Lm,N-1,Km,NLm,NT. In order to estimate the (m+1)th coordinates, A~ and C~m can be regarded as the noise corrupted data vector and data matrix, respectively. Hence, when ΔA~ and ΔC~m represent a zero mean white Gaussian noise vector and matrix, respectively, the noisy data vector and matrix can be expressed as(15)A~=A~0+ΔA~,C~m=C~m,0+ΔC~m.The TLS solution can be provided by perturbing A~ and C~m to correct the noise in A~ and C~m while maintaining the minimum sum of the squares of the Frobenius norm. Formally, the TLS solution can be derived as(16)x^TLS=argminx~m+1ΔDF2subjecttoD+ΔDx~m+1-1=0,where D=A~C~m and ΔD=ΔA~ΔC~m. Then, x^TLS,(m+1) can be obtained from the first two rows of the estimated x^TLS. The solution to (15) can be derived using Lagrange multipliers or the singular value decomposition (SVD) of D as in [10].For example, let the SVD ofD be D=UΣVH, where U and V are unitary matrices and Σ is a diagonal matrix. Then, x^TLS is obtained from(17)x^TLS=DHD-σL+12I†DHC~m,where the superscript † denotes the pseudoinverse operation and L is the column length of the matrix A in [10].


## 4.1. Least Squares Technique

Equation (8) can be rearranged as(11)Axm+1-xm=Cm⟹Axm+1,m=Cm,where x(m+1),m=x(m+1)-xm in order to present noise on the right hand side of the equation. When ΔCm is a zero mean white Gaussian noise vector, we can obtain the LS solution as(12)x^m+1,m=argminxm+1,mΔCm=AHA-1AHCm,where the superscript H denotes the conjugate transpose operation. After estimating the LS solution in (12), the (m+1)th coordinates can be estimated by adding the mth coordinates such that(13)x^LS,m+1=x^m+1,m+xm.


## 4.2. Total Least Squares Technique

Alternatively, the TLS technique can be applied to the estimation of the(m+1)th source coordinates. Note that when A is noisy like Cm, the LS solution is no longer optimal from a statistical point of view as it undergoes bias and increased covariance due to the accumulation of noise errors in AHA. Thus, before the application of the TLS technique, the noise terms on the right hand side of (8) should be incorporated into the left-hand side in (8) as follows:(14)A~x~m+1=C~m⟹Acm,1xm+11=Acm,2xm1,where cm,1=Km,2Lm,2,Km,3Lm,3,…,Km,NLm,N,Km,N+1Lm,N+1,Km,N+1Lm,N+1T and cm,2=Km,1Lm,1,Km,1Lm,1,…,Km,N-1Lm,N-1,Km,N-1Lm,N-1,Km,NLm,NT. In order to estimate the (m+1)th coordinates, A~ and C~m can be regarded as the noise corrupted data vector and data matrix, respectively. Hence, when ΔA~ and ΔC~m represent a zero mean white Gaussian noise vector and matrix, respectively, the noisy data vector and matrix can be expressed as(15)A~=A~0+ΔA~,C~m=C~m,0+ΔC~m.The TLS solution can be provided by perturbing A~ and C~m to correct the noise in A~ and C~m while maintaining the minimum sum of the squares of the Frobenius norm. Formally, the TLS solution can be derived as(16)x^TLS=argminx~m+1ΔDF2subjecttoD+ΔDx~m+1-1=0,where D=A~C~m and ΔD=ΔA~ΔC~m. Then, x^TLS,(m+1) can be obtained from the first two rows of the estimated x^TLS. The solution to (15) can be derived using Lagrange multipliers or the singular value decomposition (SVD) of D as in [10].For example, let the SVD ofD be D=UΣVH, where U and V are unitary matrices and Σ is a diagonal matrix. Then, x^TLS is obtained from(17)x^TLS=DHD-σL+12I†DHC~m,where the superscript † denotes the pseudoinverse operation and L is the column length of the matrix A in [10].


## 5. Comparison of Network Traffic

Table1 shows the number of packets used for each TDOA-based algorithm for each localization. These algorithms locate the mobile source using different ranging techniques. As the number of base stations increases to improve the localization performance, the number of packets that are transported between a base station and the mobile source also generally increases. Yet, when the number of base stations increases in the proposed algorithm, the number of packets does not increase because the mobile source transmits only one common packet to all the base stations. Consequently, the proposed algorithm mitigates the burden of network traffic.Table 1
The number of packets for different TDOA-based localization algorithms.
Localization algorithm
Localization algorithm using TWR
Localization algorithm using SDS-TWR
Proposed localization algorithm
Number of packets
2
N
4
N
1


## 6. Simulation Results

In this section, the localization performance of the proposed algorithm is verified via Monte-Carlo simulations. The initial mobile source is located at[xs,1,ys,1]=[0,0]. The additive noise in the TDOA is assumed to be zero mean, independent Gaussian distribution, and variance is σ2 for each base station. In all simulations, the clock offsetis set as in [11], that is, 20 ppm. All the base stations are uniformly distributed on a circle, and the coordinates of the nth base station can be given as bn=[xn,yn]=[R×cos⁡(2πn/N),R×sin(2πn/N)], where R is the radius of the circle.Figure2 compares the mean square range errors (MSREs) of the proposed algorithms using LS and TLS with conventional TDOA localization algorithm in [12] versus 10log⁡10⁡(1/σ2) from 1000 independent realizations. The MSRE is defined as E[xs,m-x^s,m2+ys,m-y^s,m2]. Here, N was chosen as six and sixteen in order to investigate definite differences in the localization performance. The number of transmissions, M, is set to 60. The MSRE of the proposed LS was found to be inferior to that of the proposed TLS localization algorithm because the (m+1)th coordinates of the mobile source were estimated using the mth estimated coordinates of the previous LS algorithm. Thus, the estimated error is accumulated, and it shows the saturation of the MSREs. However, when we applied the TLS technique to solve (8), the localization performance was enhanced since the TLS technique has more error reduction effect than its LS counterpart.Figure 2
Comparisons of MSREs for different TDOA localization algorithms.Note that conventional TDOA-based localization algorithms assume a perfect synchronization between the base stations and the mobile source. Yet, perfect synchronization is difficult to obtain in practical applications. Accordingly, an additional process using a correlation based on wideband signals should be provided for synchronization between base stations. Moreover, this additional synchronization process should be implemented periodically to prevent losing the synchronization due to the clock drift of the base stations.Without the synchronization process, the TOA between the mobile source and a base station should be obtained before the calculation of the TDOA. In particular, there are two general techniques for estimating the TOA. One is two-way ranging (TWR) and the other is SDS-TWR. These two techniques do not require a synchronization process, making them suitable for comparison with the proposed algorithm. Note that TWR is easily influenced by clock drift, while SDS-TWR is robust to clock drift because it averages out the effect of the clock drift using twice the number of packets compared to TWR.Figure3 provides the improved performance of the proposed localization algorithm versus the number of base stations for various M. Overall, as the number of base stations increased, the localization performance improved; however, the localization performance degraded for large M. Nevertheless, the localization performance was still satisfactory at M=300.Figure 3
MSREs of the proposed algorithm versus the number of base stations for variousM.


## 7. Conclusion

A TDOA-based localization algorithm that does not employ a synchronization process is proposed. The performance of the proposed algorithm was enhanced by using a TLS technique. Moreover, the proposed algorithm can be applied to fast-moving mobile source tracking because it requires only one packet per localization of the mobile source.



---

*Source: 832351-2015-08-13.xml*