One-Dimensional Search Location Algorithm Based on TDOA

1. Introduction

Multi-node cooperative vibration source localization has been extensively used not only in important target monitoring and intrusion control, but also in military surveillance and battlefield reconnaissance [1-2]. The localization algorithms of vibration source mainly include localization based on time difference of arrival (TDOA) and vibration intensity [3]. The localization algorithm based on signal intensity is not complicated and has good real-time, but it has low localization accuracy [4], So the localization algorithm based on delay difference has attracted more and more attention.

There are many studies on localization algorithms based on TDOA. It is mainly divided into two categories: one is the localization algorithm of the target search function. The method requires a traversal search of the localization space, and the amount of operation is large. The maximum likelihood estimation method and spherical interpolation method are commonly used. The second is that the nonlinear equation is directly solved to obtain the required coordinates, according to the deployment of the sensor. The unconstrained one-dimensional extremum methods for solving nonlinear equations mainly include: golden section method, advance-retreat method, Newton method, etc. Unconstrained multidimensional extremum methods mainly include: pattern search method, fastest descent method, quasi-Newton method, and so on.

The prior information about TDOA measurement error is needed to provide for Chan algorithm [5]. The performance of the algorithm is significantly decreased, when TDOA noise is non-Gauss random variable, or the mean value is not zero in the actual channel environment [6]. Taylor series expansion algorithm [7] can achieve better performance in the most environments, but the algorithm is a recursive algorithm and it is not possible to provide the explicit expression. In addition, an initial estimated position is close to the target is needed to improve the convergence probability of Taylor algorithm. It is impossible to judge in advance, if there is no convergence, and the calculation amount of Taylor series expansion is relatively large [8]. The calculation process of Fang algorithm [9] is simple and clear. In practical application, the ambiguity in the estimated location value can be removed by the relevant information. The optimal solution based on TDOA data can be gotten by Fang algorithm. However, the algorithm has a large amount of computation and poor real-time performance of localization, when the time delay estimation error is large, the equation of localization will appear a fuzzy solution, or even no solution [10].

In order to solve these problems and improve real-time performance and accuracy of target system, the localization algorithm based on one dimensional search variable is proposed in this paper. The concept of search algorithm is introduced in this algorithm. The distance [TeX:] $$d_{1}$$ between the single sensor and the vibration target is as a search variable, and [TeX:] $$d_{1}$$ is set to increase from zero by the certain step length. The corresponding source coordinate [TeX:] $$(\widehat{x}, \hat{y})$$ is concluded. The corresponding distance difference is found by the estimated source coordinates, when the difference value between the estimated distance difference and the actual distance difference is less than the given precision. The search will be terminated, then the estimated coordinates [TeX:] $$(\widehat{x}, \hat{y})$$ is the location of the target.

2. Localization Algorithm based on TDOA

TDOA is essentially the distance difference between target and two sensors. The distance difference between any point on the hyperbolic line and two focal points is the constant by the definition of hyperbolic line. Therefore, the time difference of collected signals from two sensors is known. The hyperbolic line of two sensors as the focus point can be determined by the time difference, and the target is on the hyperbolic line. In a two-dimensional plane, two time-differences can be obtained by three sensors, then two pairs of hyperbolic line can be determined. The target is on one of two pairs of hyperbolic intersection point. The target location is determined by combining the direction information [11]. Therefore, the localization based on TDOA is also called the hyperbolic localization. The localization model diagram as shown in Fig. 1.

[TeX:] $$S_{1}, S_{2}$$ and [TeX:] $$S_{3}$$ are three vibration sensors. As mentioned above, a hyperbolic line is determined by [TeX:] $$S_{1}$$ and [TeX:] $$S_{2}$$, and another hyperbolic line is determined by [TeX:] $$S_{2}$$ and [TeX:] $$S_{3}$$. One of the intersection points is the target location. [TeX:] $$d_{1}, d_{2}$$ and [TeX:] $$d_{3}$$ are the distances between the target and the three sensors respectively in Fig. 1.

The positions of sensors are [TeX:] $$\left(x_{i}, y_{i}\right)$$, [TeX:] $$i=1,2,3$$. The target position is [TeX:] $$(x, y)$$. The first sensor is set as a reference point, then the hyperbolic equation is:

(1)

[TeX:] $$\sqrt{\left(x_{i}-x\right)^{2}+\left(y_{i}-y\right)^{2}}-\sqrt{\left(x_{1}-x\right)^{2}+\left(y_{1}-y\right)^{2}}=v \tau_{i 1}=d_{i 1}$$

In Eq. (1), v is the spread speed of seismic signal; [TeX:] $$\tau_{i 1}$$ is the received signal time difference between sensor [TeX:] $$S_{i}$$ and [TeX:] $$S_{1}$$; [TeX:] $$d_{i 1}$$ is the distance difference between the target and sensors [TeX:] $$S_{i}$$ and [TeX:] $$S_{1}$$. The two given equations are solved, and the target location [TeX:] $$(x, y)$$ can be estimated.

The time difference is obtained by time delay estimation. How to calculate the target location quickly and effectively is the key to implementation of a localization system. Eq. (2) is obtained by [TeX:] $$d_{i 1}=d_{i}-d_{1}$$:

(2)

[TeX:] $$d_{i}^{2}=\left(d_{i 1}+d_{1}\right)^{2}$$

According to Eqs. (1) and (2), Eq. (3) is obtained:

(3)

[TeX:] $$d_{i 1}^{2}+2 d_{i 1} d_{1}=x_{i}^{2}+y_{i}^{2}-2 x_{i 1} x-2 y_{i 1} y-x_{1}^{2}-y_{1}^{2}$$

In Eq. (3), [TeX:] $$x_{i 1}=x_{i}-x_{1}, y_{i 1}=y_{i}-y_{1}$$. From this, the two linear equations about [TeX:] $$x, y$$ and [TeX:] $$d_{1}$$ are obtained, and [TeX:] $$d_{1}$$ is unknown.

By the above analysis, the equations are ascertained from Eq. (3), and [TeX:] $$(x, y)$$ is solved to make sure target location.

3. One-Dimensional Search Location Algorithm

3.1 Fang Algorithm

Fang algorithm [12] is the analytical expression of localization algorithm based TDOA. The method of solving hyperbolic localization model is as follows:

First, a sensor coordinate system is determined. There are three sensors in the hyperbolic location estimation by using Fang algorithm, they are respectively: the first sensor [TeX:] $$(0,0)$$, the second sensor [TeX:] $$\left(x_{2}, 0\right)$$, the third sensor [TeX:] $$\left(x_{3}, y_{3}\right)$$. It is known by the sensor coordinates:

(4)

[TeX:] $$d_{1}=\sqrt{\left(x_{1}-x\right)^{2}+\left(y_{1}-y\right)^{2}}=\sqrt{x^{2}+y^{2}}$$

(5)

[TeX:] $$\left\{\begin{array}{l} x_{i 1}=x_{i}-x_{1}=x_{i} \\ y_{i 1}=y_{i}-y_{1}=y_{i} \end{array}\right.$$

According to the sensor coordinate, Eq. (4) is substituted into Eq. (3). It is described as follows:

(6)

[TeX:] $$\left\{\begin{array}{c} -2 d_{21} d_{1}=d_{21}^{2}-x_{2}^{2}+2 x_{2} x \\ -2 d_{31} d_{1}=d_{31}^{2}-\left(x_{3}^{2}+y_{3}^{2}\right)+2 x_{3} x+2 y_{3} y \end{array}\right.$$

The two equations are done division, then [TeX:] $$d_{1}$$ can be eliminated. Eq. (7) is obtained after reducing:

(7)

[TeX:] $$y=g \times x+h$$

In Eq. (7), [TeX:] $$g=\left[\frac{d_{31} x_{2}}{d_{21}}-x_{3}\right] / y_{3}$$, and [TeX:] $$h=\left[x_{3}^{2}+y_{3}^{2}-d_{31}^{2}+d_{31} \times\left(1-\left(\frac{x_{2}}{d_{21}}\right)^{2}\right)\right] / 2 y_{3}$$. Eqs. (7) and (4) are substituted into Eq. (6), then Eq. (8) is obtained:

(8)

[TeX:] $$a x^{2}+b x+c=0$$

In Eq. (8):

[TeX:] $$a=-\left(\left(1-\left(\frac{x_{2}}{d_{21}}\right)^{2}\right)+g^{2}\right)$$

[TeX:] $$b=x_{2} \times\left(1-\left(\frac{x_{2}}{r_{21}}\right)^{2}\right)-2 g \times h, c=\left(\frac{d_{21}^{2}}{4}\right) \times\left(\left(1-\left(\frac{x_{2}}{d_{21}}\right)^{2}\right)\right)^{2}-h^{2}$$

Eq. (8) is solved, then [TeX:] $$x=\frac{-b \pm \sqrt{b^{2}-4 a c}}{2 a}$$ can be obtained. According to simulation experiments of some literatures [10-12], the identified target location [TeX:] $$x=\frac{-b+\sqrt{b^{2}-4 a c}}{2 a}$$ is usually beyond the detection range of sensors, so it is given up. Therefore, the horizontal axis can be determined for the target and [TeX:] $$x=\frac{-b-\sqrt{b^{2}-4 a c}}{2 a}$$, and the target location can be calculated when the horizontal axis is substituted into the Eq. (7).

3.2 One-Dimensional Search Location Algorithm

It can be known from the previous analysis that the quadratic equation which the target is built based on the hyperbolic positioning model by the algebraic operation in Fang algorithm. Then the target coordinate is determined by solving the equation. Its calculation process is simple and clear, and it is not need priori information about the target. The performance is stable, when the precision of time delay estimation is higher. However, there is a large amount of computation in Fang algorithm, and the real- time performance of Fang algorithm is bad, in addition its time delay estimation error is large. The localization equation will appear the fuzzy solution, and there may even be no solution. For example, there is no solution to Eq. (8) when [TeX:] $$b^{2}-4 a c<0$$. Therefore, Fang algorithm has great limitations in practice.

In order to improve the system target localization accuracy and real-time performance, a localization algorithm based on one dimensional search variables is proposed in this paper.

Eq. (3) can be simplified as follows:

(9)

[TeX:] $$\left\{\begin{array}{c} x_{i 1} x+y_{i 1} y+d_{i 1} d_{1}=b_{i 1} \\ b_{i 1}=0.5\left(x_{i}^{2}+y_{i}^{2}-x_{1}^{2}-y_{1}^{2}-d_{i 1}^{2}\right) \end{array}\right.$$

Suppose there are four sensors to detect the vibration signals. According to layout law of the squares array, the coordinates of the sensor [TeX:] $$S_{1}, S_{2}, S_{3}$$ and [TeX:] $$S_{4}$$, respectively are set [TeX:] $$(0,0),(L, 0),(0, L)$$, and [TeX:] $$(L, L)$$, then the coordinates is substituted into the Eq. (9), Eq. (10) is obtained:

(10)

[TeX:] $$\left\{\begin{array}{c} L x+d_{21} d_{1}=0.5\left(L^{2}-d_{21}^{2}\right) \\ L y+d_{31} d_{1}=0.5\left(L^{2}-d_{31}^{2}\right) \\ L(x+y)+d_{41} d_{1}=0.5\left(2 L^{2}-d_{41}^{2}\right) \end{array}\right.$$

Eq. (10) can be simplified as follows:

(11)

[TeX:] $$\left\{\begin{array}{l} x=\frac{L^{2}-d_{21}^{2}-2 d_{21} d_{1}}{2 L} \\ y=\frac{L^{2}-d_{31}^{2}-2 d_{31} d_{1}}{2 L} \end{array}\right.$$

If [TeX:] $$d_{1}$$ is regarded as a new variable, Eq. (11) can be regarded as the linear equations about the three variables [TeX:] $$x, y$$ and [TeX:] $$d_{1}$$. The concept of search algorithm is introduced. [TeX:] $$d_{1}$$ is as search variable. The vibration target location is searched by changing the value of [TeX:] $$d_{1}$$ in two-dimensional plane.

Due to [TeX:] $$d_{i 1}=v \Delta \tau_{i 1}$$, the time difference [TeX:] $$\Delta \tau_{i 1}$$ can be determined through time delay estimation. Therefore, [TeX:] $$x$$ and [TeX:] $$y$$ may be defined as the function of [TeX:] $$d_{1}$$which can be seen from Eq. (11). If [TeX:] $$d_{1}$$is as search variable, it is increased from zero to [TeX:] $$\hat{d}_{1}$$ by the certain step length. [TeX:] $$\hat{d}_{1}$$ is substituted into Eq. (11), and the corresponding source coordinates [TeX:] $$(\hat{x}, \hat{y})$$ can be obtained. Then the corresponding distance difference [TeX:] $$\hat{d}_{21}$$and [TeX:] $$\hat{d}_{31}$$can be solved from the source coordinate. The search process will be terminated if [TeX:] $$\varepsilon=\left|\hat{d}_{21}-d_{21}\right|+\left|\hat{d}_{31}-d_{31}\right|$$ is less than the given precision [TeX:] $$\varepsilon_{0}$$. The coordinates [TeX:] $$(\hat{x}, \hat{y})$$ is the estimate coordinates of the target at the moment.

In practice the performance of algorithm is great influenced by the step length of search variable. If the search step length is defined larger, the algorithm converges fast, but the localization accuracy will decline. If the search step length is defined smaller, the localization accuracy be improved, but the convergence speed of algorithm will be slow. In this paper in order to reduce influence of the search step length to performance of algorithm, first the rough position of the target is estimated by larger search step length. And then smaller step length is used to do more accurate search for the target location eventually.

4. Performance Analysis

4.1 Localization Accuracy Comparison

To test and compare localization performance of the algorithm, we have taken the walk vibration signals for example, the improved Fang algorithm, the improved Taylor algorithm [12] and the improved Newton algorithm [13] have been carried on the contrast experiment.

The four sensors, [TeX:] $$S_{0}, S_{1}, S_{2}$$, and [TeX:] $$S_{3}$$, in node localization system are set, and the coordinates of the sensors is [TeX:] $$(0,0),(100,100),(100,0)$$, and [TeX:] $$(0,100)$$, respectively. The initial position [TeX:] $$(x,y)$$ of the vibration source target is [TeX:] $$(100,30)$$. The first sensor coordinate is origin position. The error standard deviation is set from 0 to 100 ms. There are 25 different [TeX:] $$\sigma_{n}$$, and each with an interval of 4 m. For each [TeX:] $$\sigma_{n}$$, one hundred simulation experiments of localization had been performed, and the mean value of the running results is calculated. The larger search length is 10 cm, and the initial value of search variables is obtained. The small search length is 1 cm, and the target location estimation results are shown in Fig. 2.

Fig. 2(a) is the different location estimates on the horizontal axis to the improved Taylor, the improved Fang and the improved Newton. Fig. 2(b) is the different location estimates on the vertical axis to three algorithms. The horizontal axis is the standard deviation of time delay error, and its unit is millisecond. The vertical axis is average results, and its unit is second.

It can be seen from the simulation results: the improved Fang algorithm has more accurate location than others. When the error deviation is increased, the measurement error of three algorithms increases. But the improved Fang algorithm is less affected than others, so it is more stable.

4.2 Field Comparison Experiment

To verify validity of the location algorithm based on one dimensional search variables, the method has been proofed in the field experiments. The experiment has been carried out by using the single node sensor array for target location, the distribution of the sensors is as shown in Fig. 3. The hollow circles represent the location of the sensor array in Fig. 3. The solid circle represents the location of the object. The straight line represents the motion trajectory of the target.

The target has been done the line motion along. One dimensional search localization algorithm based on TDOA in this paper is used to locate target. The rough position of target is searched firstly by 10 cm search step length. The initial value of search variables is obtained according to Eq. (4), then the precise location of target is determined by 1 cm search length. The target location estimation results are shown in Fig. 4.

It can be seen from Fig. 4 that the distance between goal and the sensor array center is closer, and the localization accuracy is higher than other algorithms. The error of target position estimation is basically in the range of 0.5 m. The experimental results show that the localization accuracy of the proposed algorithm is higher, and the localization accuracy has reached requirement of the system.

4.3 Estimation Error Comparison

The localization accuracies of the three algorithms are evaluated by the location of mean square error (MSE). Usually the indexes of measuring localization accuracy include MSE, root mean square error (RMSE), and geometric accuracy attenuation factor (GDOP), etc. RMSE is the evaluation index of this algorithm. In two-dimensional localization algorithm, MSE and RMSE with the formation type:

[TeX:] $$(x, y)$$ is actual target coordinates location of vibration source; [TeX:] $$(\hat{x}, \hat{y})$$ is estimated coordinates location of the vibration source. The estimation error of the three algorithms is compared. The simulation result is shown in Fig. 5.

As can be seen from Fig. 5, when several algorithms have the same error, RMSE of the improved Fang is significantly lower than others. In other word, the accuracy degree of localization is significantly higher

than the others. when these algorithms are both affected by the error standard deviation, the improved Taylor is inferior to the improved Fang. when error standard deviation σ increases, the localization performance of the three algorithms are all down. The algorithms may even be without solution. But it can be seen from the simulation result that the improved Fang algorithm still keep high localization accuracy, in the case of large measurement errors compared with other algorithms.

5. Conclusions

The localization equation of Fang algorithm often cannot accurately locate target in practical application. In order to solve the problem, one dimensional search localization algorithm based on TDOA is put forward in this paper. The concept of search is introduced in the algorithm, and the distance between the target source and any single sensor is used as the search variables. The search of target location is implemented by changing value of the variable search in the two-dimensional plane. Experiment results show that the search step length all has great influence on performance of the algorithm. The larger search step length estimates rough location of the target. The smaller step length is used to do precise search for the target location eventually. The amount of calculation is reduced by using this method, at the same time speed and accuracy are all improved.

Acknowledgement

This paper is supported by the National Natural Science Foundation of China (No. 61271147 and 61402529), the National Key Research and Development Program of China (No. 2017YFB0503000 and WJ20182A020020-1), and the Natural Science Basic Research Plan in Shanxi Province of China (No. 2020JM-361).