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

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.

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 × 10⁸ 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 the nth base station be located at the point $b_{n} \equiv [x_{n}, y_{n}]$ , where $n = 1, \dots, N$ . The coordinates of the mobile source can be defined as $x \equiv [x_{s}, y_{s}]$ . Then, in the absence of measurement noise, the estimated distance ${\hat{d}}_{n}$ between the source and nth base station can be modeled as

\begin{matrix} {\hat{d}}_{n} = c T_{n} = ‖x - b_{n}‖ = \sqrt{{(x_{s} - x_{n})}^{2} + {(y_{s, m} - y_{n})}^{2}}, \end{matrix}

(1)

where

‖\cdot‖

denotes the L2 norm and

T_{n}

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

\begin{array}{l} {\hat{d}}_{n + 1, n} = c (T_{n + 1} - T_{n}) \\ = d_{n + 1} - d_{n} \\ = ‖x - b_{n + 1}‖ - ‖x - b_{n}‖ \\ = \sqrt{{(x_{s} - x_{n + 1})}^{2} + {(y_{s} - y_{n + 1})}^{2}} \\ - \sqrt{{(x_{s} - x_{n})}^{2} + {(y_{s} - y_{n})}^{2}} . \end{array}

(2)

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 the nth base station (BS) be located at the point $b_{n} \equiv [x_{n}, y_{n}]$ , where $n = 1, \dots, N$ . From the assumption of periodic transmission of the localizing signal, the coordinates of the source can be defined as $x_{m} \equiv [x_{s, m}, y_{s, m}]$ , which indicate when the mobile source transmits the mth localizing signal. Likewise, $x_{(m + 1)} \equiv [x_{s, (m + 1)}, y_{s, (m + 1)}]$ denotes the transmission of the $(m + 1)$ th localizing signal, $m = 1, \dots, M$ . Then, in the absence of TDOA measurement noise, the range difference equation based on the mobility of the source can be given as

\begin{array}{l} K_{m, n} = c (T_{(m + 1), n} - T_{m, n}) \\ = d_{(m + 1), n} - d_{m, n} \\ = ‖x_{(m + 1)} - b_{n}‖ - ‖x_{m} - b_{n}‖ \\ = \sqrt{{(x_{s, (m + 1)} - x_{n})}^{2} + {(y_{s, (m + 1)} - y_{n})}^{2}} \\ - \sqrt{{(x_{s, m} - x_{n})}^{2} + {(y_{s, m} - y_{n})}^{2}}, \end{array}

(3)

where c is the speed of the propagation,

T_{m, 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 Figure 1, $t_{sync}$ is the synchronization time between the base stations. As shown in Figure 1(a), conventional TDOA is the time difference between $T_{2}$ and $T_{1}$ . 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 $T_{m, 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.

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

\begin{array}{l} {(x_{s, (m + 1)} - x_{n})}^{2} + {(y_{s, (m + 1)} - y_{n})}^{2} \\ = {(K_{m, n})}^{2} + 2 K_{m, n} d_{m, n} + {(x_{s, m} - x_{n})}^{2} + {(y_{s, m} - y_{n})}^{2} . \end{array}

(4)

Then, expanding the squares in (4) and rearranging the variables according to the source coordinates generate

\begin{array}{l} {(x_{s, (m + 1)})}^{2} - 2 x_{s, (m + 1)} x_{n} + {(y_{s, (m + 1)})}^{2} - 2 y_{s, (m + 1)} y_{n} \\ = {(K_{m, n})}^{2} + 2 K_{m, n} d_{m, n} + {(x_{s, m})}^{2} \\ - 2 x_{s, m} x_{n} + {(y_{s, m})}^{2} - 2 y_{s, m} y_{n} . \end{array}

(5)

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:

\begin{array}{l} {(x_{s, (m + 1)})}^{2} - 2 x_{s, (m + 1)} x_{(n + 1)} + {(y_{s, (m + 1)})}^{2} - 2 y_{s, (m + 1)} y_{(n + 1)} \\ = {(K_{m, (n + 1)})}^{2} + 2 K_{m, (n + 1)} d_{m, (n + 1)} + {(x_{s, m})}^{2} \\ - 2 x_{s, m} x_{(n + 1)} + {(y_{s, m})}^{2} - 2 y_{s, m} y_{(n + 1)} . \end{array}

(6)

It follows that

\begin{array}{l} 2 (x_{s, (m + 1)} - x_{s, m}) (x_{(n + 1)} - x_{n}) \\ + 2 (y_{s, (m + 1)} - y_{s, m}) (y_{(n + 1)} - y_{n}) \\ = {(K_{m, n})}^{2} + 2 K_{m, n} d_{m, n} - {(K_{m, (n + 1)})}^{2} - 2 K_{m, (n + 1)} d_{m, (n + 1)} . \end{array}

(7)

Finally, formulating (7) into matrix form, we have

\begin{matrix} A x_{(m + 1)} = C_{m} + A x_{m}, \end{matrix}

(8)

where

\begin{matrix} A = 2 [\begin{bmatrix} (x_{2} - x_{1}) & (y_{2} - y_{1}) \\ \begin{matrix} (x_{3} - x_{1}) \\ (x_{4} - x_{1}) \\ (x_{5} - x_{1}) \end{matrix} & \begin{matrix} (y_{3} - y_{1}) \\ (y_{4} - y_{1}) \\ (y_{5} - y_{1}) \end{matrix} \\ ⋮ & ⋮ \\ (x_{N} - x_{(N - 1)}) & (y_{N} - y_{(N - 1)}) \\ (x_{(N + 1)} - x_{(N - 1)}) & (y_{(N + 1)} - y_{(N - 1)}) \\ (x_{(N + 1)} - x_{N}) & (y_{(N + 1)} - y_{N}) \end{bmatrix}], \\ C_{m} = [\begin{bmatrix} K_{m, 1} L_{m, 1} - K_{m, 2} L_{m, 2} \\ \begin{matrix} K_{m, 1} L_{m, 1} - K_{m, 3} L_{m, 3} \\ K_{m, 1} L_{m, 1} - K_{m, 4} L_{m, 4} \\ K_{m, 1} L_{m, 1} - K_{m, 5} L_{m, 5} \end{matrix} \\ ⋮ \\ K_{m, (N - 1)} L_{m, (N - 1)} - K_{m, N} L_{m, N} \\ K_{m, (N - 1)} L_{m, (N - 1)} - K_{m, (N + 1)} L_{m, (N + 1)} \\ K_{m, N} L_{m, N} - K_{m, (N + 1)} L_{m, (N + 1)} \end{bmatrix}] \end{matrix}

(9)

and

x_{(m + 1)} = {[\begin{bmatrix} x_{s, (m + 1)} & y_{s, (m + 1)} \end{bmatrix}]}^{T}

x_{m} = {[\begin{bmatrix} x_{s, m} & y_{s, m} \end{bmatrix}]}^{T}

, and

L_{m, n} = d_{m, n} + d_{(m + 1), n}

. The superscript T denotes the transpose operation. With the assumption of known initial source coordinates

x_{1}

, we can calculate

L_{1, n}

using

\begin{matrix} L_{m, n} = d_{m, n} + d_{(m + 1), n} = 2 d_{m, n} + K_{m, n} \end{matrix}

(10)

since

d_{1, n} = ‖x_{1} - b_{n}‖

can be calculated using the coordinates of both the nth base station

b_{n}

and the initial source

x_{1}

. After estimating the second coordinates of the source

x_{2}

L_{2, 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

\begin{matrix} A (x_{(m + 1)} - x_{m}) = C_{m} ⟹ A x_{(m + 1), m} = C_{m}, \end{matrix}

(11)

where

x_{(m + 1), m} = x_{(m + 1)} - x_{m}

in order to present noise on the right hand side of the equation. When

Δ C_{m}

is a zero mean white Gaussian noise vector, we can obtain the LS solution as

\begin{matrix} {\hat{x}}_{(m + 1), m} = \underset{x_{(m + 1), m}}{argmin} ‖Δ C_{m}‖ = {(A^{H} A)}^{- 1} A^{H} C_{m}, \end{matrix}

(12)

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

\begin{matrix} {\hat{x}}_{LS, (m + 1)} = {\hat{x}}_{(m + 1), m} + x_{m} . \end{matrix}

(13)

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 $C_{m}$ , 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 $A^{H} A$ . 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:

\begin{matrix} \tilde{A} {\tilde{x}}_{(m + 1)} = {\tilde{C}}_{m} ⟹ [\begin{bmatrix} A & c_{m, 1} \end{bmatrix}] [\begin{bmatrix} x_{(m + 1)} \\ 1 \end{bmatrix}] = [\begin{bmatrix} A & c_{m, 2} \end{bmatrix}] [\begin{bmatrix} x_{m} \\ 1 \end{bmatrix}], \end{matrix}

(14)

where

c_{m, 1} = {[K_{m, 2} L_{m, 2}, K_{m, 3} L_{m, 3}, \dots, K_{m, N} L_{m, N}, K_{m, (N + 1)} L_{m, (N + 1)}, K_{m, (N + 1)} L_{m, (N + 1)}]}^{T}

and

c_{m, 2} = {[K_{m, 1} L_{m, 1}, K_{m, 1} L_{m, 1}, \dots, K_{m, (N - 1)} L_{m, (N - 1)}, K_{m, (N - 1)} L_{m, (N - 1)}, K_{m, N} L_{m, N}]}^{T}

. In order to estimate the

(m + 1)

th coordinates,

\tilde{A}

and

{\tilde{C}}_{m}

can be regarded as the noise corrupted data vector and data matrix, respectively. Hence, when

Δ \tilde{A}

and

Δ {\tilde{C}}_{m}

represent a zero mean white Gaussian noise vector and matrix, respectively, the noisy data vector and matrix can be expressed as

\begin{matrix} \tilde{A} = {\tilde{A}}_{0} + Δ \tilde{A}, {\tilde{C}}_{m} = {\tilde{C}}_{m, 0} + Δ {\tilde{C}}_{m} . \end{matrix}

(15)

The TLS solution can be provided by perturbing

\tilde{A}

and

{\tilde{C}}_{m}

to correct the noise in

\tilde{A}

and

{\tilde{C}}_{m}

while maintaining the minimum sum of the squares of the Frobenius norm. Formally, the TLS solution can be derived as

\begin{matrix} {\hat{x}}_{TLS} = \underset{{\tilde{x}}_{(m + 1)}}{argmin} {‖Δ D‖}_{F}^{2} subject to [D + Δ D] [\begin{bmatrix} {\tilde{x}}_{(m + 1)} \\ - 1 \end{bmatrix}] = 0, \end{matrix}

(16)

where

D = [\begin{bmatrix} \tilde{A} & {\tilde{C}}_{m} \end{bmatrix}]

and

Δ D = [\begin{bmatrix} Δ \tilde{A} & Δ {\tilde{C}}_{m} \end{bmatrix}]

. Then,

{\hat{x}}_{TLS, (m + 1)}

can be obtained from the first two rows of the estimated

{\hat{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 of D be $D = U Σ V^{H}$ , where U and V are unitary matrices and Σ is a diagonal matrix. Then, ${\hat{x}}_{TLS}$ is obtained from

\begin{matrix} {\hat{x}}_{TLS} = {(D^{H} D - σ_{L + 1}^{2} I)}^{†} D^{H} {\tilde{C}}_{m}, \end{matrix}

(17)

where the superscript † denotes the pseudoinverse operation and L is the column length of the matrix A in [10].

5. Comparison of Network Traffic

Table 1 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 $[x_{s, 1}, y_{s, 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 $b_{n} = [x_{n}, y_{n}] = [R \times \cos (2 π n / N), R \times \sin (2 π n / N)]$ , where R is the radius of the circle.

Figure 2 compares the mean square range errors (MSREs) of the proposed algorithms using LS and TLS with conventional TDOA localization algorithm in [12] versus $10 \log_{10} (1 / σ^{2})$ from 1000 independent realizations. The MSRE is defined as $E [{(x_{s, m} - {\hat{x}}_{s, m})}^{2} + {(y_{s, m} - {\hat{y}}_{s, m})}^{2}]$ . 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.

Figure 3 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 various M.

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.

Footnotes

Conflict of Interests

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

References

Gezici

Poor

H. V.

Position estimation via ultra-wide-band signals

Proceedings of the IEEE 2009 97 2 386 403

2-s2.0-62949170134

10.1109/JPROC.2008.2008840

Yang

Sun

Constrained total least-squares location algorithm using time-difference-of-arrival measurements

IEEE Transactions on Vehicular Technology 2010 59 3 1558 1562

10.1109/TVT.2009.2037509

2-s2.0-77949725975

Y.-C.

Chaudhari

Serpedin

Clock synchronization of wireless sensor networks

IEEE Signal Processing Magazine 2011 28 1 124 138

2-s2.0-78650452886

10.1109/msp.2010.938757

Gezici

Tian

Giannakis

G. B.

Kobayashi

Molisch

A. F.

Poor

H. V.

Sahinoglu

Localization via ultra-wideband radios: a look at positioning aspects of future sensor networks

IEEE Signal Processing Magazine 2005 22 4 70 84

2-s2.0-22544486275

10.1109/msp.2005.1458289

Fang

B. T.

Simple solutions for hyperbolic and related position fixes

IEEE Transactions on Aerospace and Electronic Systems 1990 26 5 748 753

2-s2.0-0025492025

10.1109/7.102710

Sharp

Guo

Y. J.

GDOP analysis for positioning system design

IEEE Transactions on Vehicular Technology 2009 58 7 3371 3382

10.1109/TVT.2009.2017270

2-s2.0-69549105982

Jang

S. H.

Kim

Y. S.

Yoon

S. H.

Chong

J. W.

SNR enhancement algorithm using multiple chirp symbols with clock drift for accurate ranging

ETRI Journal 2011 33 6 841 848

2-s2.0-82655179975

10.4218/etrij.11.0111.0013

IEEE Computer Society IEEE Std. 802.15.4a-2007 2007

Schwalowsky

Trsek

Exel

Kerö

System integration of an IEEE 802.11 based TDoA localization system

Proceedings of the 4th IEEE Symposium on Precision Clock Synchronization for Measurement Control and Communication (ISPCS '10)

October 2010

Portsmouth, NH, USA

55 60

10.1109/ispcs.2010.5609762

2-s2.0-78650185180

10.

Rahman

M. D.

K.-B.

Total least squares approach for frequency estimation using linear prediction

IEEE Transactions on Acoustics, Speech and Signal Processing 1987 35 10 1440 1454

10.1109/tassp.1987.1165059

11.

IEEE 802.15.4a-2007

Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (WPANs); Amendment 1: Add Alternate PHYs

2007

12.

Chan

Y. T.

K. C.

Simple and efficient estimator for hyperbolic location

IEEE Transactions on Signal Processing 1994 42 8 1905 1915

10.1109/78.301830

2-s2.0-0028484308