Accepted Manuscript Title: An Improved Localization Algorithm of Taylor Series Expansion Search Target Author: Yanli Chu Luyao He Fan Yao PII: DOI: Reference:
S0030-4026(16)30534-4 http://dx.doi.org/doi:10.1016/j.ijleo.2016.05.084 IJLEO 57710
To appear in: Received date: Accepted date:
Please cite this article as: Yanli Chu, Luyao He, Fan Yao, An Improved Localization Algorithm of Taylor Series Expansion Search Target, Optik - International Journal for Light and Electron Optics http://dx.doi.org/10.1016/j.ijleo.2016.05.084 This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.
An Improved Localization Algorithm of Taylor Series Expansion Search Target Yanli Chu 1,2,*,Luyao He1
1.School of Marine Science and Technology, Northwestern Polytechnical University, Xi’an 710086,China; 2. Department of Information Engineering, University of CAPF, Xi’an 710086,China;
Abstract: Due to the real-time positioning, mobility and complexity by environmental goals control, reasonable, efficient determination of the measured time delay difference accuracy has been plagued researchers question. Aiming at this problem, this paper proposes a method to estimate the error signal delay discrimination based on characteristic parameters, using the method of Taylor series expansion location algorithms are search initial and end condition was improved. The experiment proves that this algorithm has high precision, strong robustness etc.
Key words：Gross time delay error；Taylor Series Expansion；Sensor’s credible degree；Positioning accuracy
1. Introduction Vibration source localization technology has been widely used in bridge monitoring, regional monitoring, environmental monitoring and other fields. Typically, vibration source positioning technology include positioning based on the vibration strength and TDOA (Time difference of arrival) .As the positioning technology algorithm based on signal strength is simple and good real-time, but its positioning accuracy is not high, the time difference positioning technology has become one of the hot spots in this field. The Bayesian estimation is sensitive to the prior probability, and the data processing accuracy and complexity of the algorithm has some shortcomings[3-4]. Chan algorithm uses the least squares method to solve equations for position, with the increase of TDOA measurement errors, the algorithm performance declined rapidly. The algorithm of Taylor series expansion search has high accuracy. The algorithm is simple, robust, and it also has other characteristics, so it is widely used in engineering. In addition, in the traditional sense of the vibration, while measuring the difference of delay, due to environmental complexity and frequent sources of interference, leading measure of consistency is poor, even gross error, once an error occurs and the probability of coarse surge. The emergence of the gross error seriously affect search algorithm accuracy and convergence rate. So for vibration targeting location, the discrimination of time delay error becomes very necessary. The initial search coordinates and the search end condition are the main factors in effect the precision and speed of Taylor search algorithm. This paper proposes a method to estimate the error signal delay discrimination based on characteristic parameters, use the method to determine the reliability of each sensor, then find the initial position of the source through the three high reliability sensors, and improve the search iteration end conditions based on the reliability of sensor, final by using Taylor series expansion method to further locate the source of vibration. The experimental data show that the algorithm can effectively improve the robustness of the Taylor series expansion search and location accuracy.
2.Time delay error estimation based on Characteristic parameters Characteristic analysis is one of the key technology of the signal process. In the multi-node cooperative localization, the received signal quality of each sensor is usually described by the signal characteristic parameters. Rational and efficient signal process method can be extracted to reflect the characteristics of the target information in a whole view, provide reliable evidence to support the determination of signal quality. In fact, the same local oscillator, the signal of each sensor (such as zero-crossing rate, spectral width, the spectral density, etc.) has a strong similarity at the same time, it can be used to distinguish the merits of the respective signals received by the sensor by comparing the size of the parameter deviates which from the center of the signal characteristic values, and to determine the reliability of the sensor. Suppose there are n sensors, signal feature of each sensor has m characteristic parameters, si ( j ) is the j-th characteristic parameters of the i-th sensor, the mean of the j-th Characteristic parameters (parameters of reference) for N sensors can be described as follow:
si ( j )
1 n 1 si ( j) n i 0
The definition of the i-th sensor on the Characteristic parameters of the generalized Euclidean distance: di ( j ) si ( j ) si ( j )
Where i 0,1,..., n 1, it said that characteristic parameters si ( j ) of the i-th sensor deviates from the features of the reference value. For convenience of analysis comparing the deviation distance of different characteristic parameters, the normalized deviation distance is obtained by the normalization processing for type (1).
di ( j ) min di ( j ) max di ( j ) min di ( j )
So the m characteristic parameters normalized distance sum i of the i th sensor is : m 1
i ij , j 0,1 m 1 j 0
i 1 i / i
i is normalized processing, n
i / i i 0
It is get the m characteristic parameters normalized distance sum i of the i th sensor. Set: n
i 1 i / i
The physical meaning of gray correlation degree i is the credibility of the sensors, obviously, the greater its value, indicating that the signal characteristic parameters of the sensor closer to the center of the reference feature value, namely the signal quality is better，the time delay difference ascertain is the more accurate.
3. Taylor series expansion algorithm based on the reliability of sensors 3.1 The classic Taylor series expansion search algorithm The basic idea of Taylor series expansion search is that in the search of initial coordinates, the nonlinear equation into a linear problem , and then search by the certain step length starting from the initial coordinates, until satisfy the search end conditions, finally obtaining the optimal solution. The vibratory source localization figure is shown Figure 1.
Set n receiving sensors to participate in the target location, their coordinates is Bi ( xi , yi ) （i=0，1 ，2，…，n-1）, the distance between the vibratory source and the i receiving sensor is …，n-1). Assume that the spread speed of vibration signal is the constant c, between
is the time difference
the vibratory source to the i receiving sensor and the 0 receiving sensor,
is the distance
the vibratory source to the i receiving sensor and the 0 receiving sensor, there is
ri 0 ri r0 . Set
the distance difference sequence
of the actual measuring multi-sensor is
ri 0 r1 ,0 r 2,0. . . r,
Can be set up n - 1 positioning equation is:
ri 0 c i 0 ri r0
xi x0 x yi y0 y ri,0r0 si
1 2 x yi 2 x02 y02 ri,02 2 i
2 2 x x0 y y0 ， ri x xi y yi ，i =1，2，…n-1。
Taylor series expansion algorithm is that in the selected initial value x(0) , y(0) , the nonlinear problem is linearized processing, and (10) is a nonlinear system of equations, the solution of the equations becomes nonlinear optimization problem unconstrained conditions. Taylor series expansion of equation (10) and ignore the second order above component, are:
H P In type(11),
r1,0 (r1 r0 ) x ， r2,0 (r2 r0 ) H y rN ,0 (rN r0 )
( x1 x) ( x2 x) r1 r2 ， ( x x ) ( x x ) 1 3 r1 r3 P ( x1 x) ( xN x) r1 rN
（11） ( y1 y )
( y2 y )
r2 i =1，2，…，n-1。 ( y y) ( y1 y ) 3 r1 r3 ( yN y ) ( y1 y ) r1 rN r1
x , y can be calculated by the type(11);
x(k 1) x(k ) x y(k 1) y (k ) y in it , k is the search step number, k 1, 2,... 。
Construct the error sum function: n 1
ri r0 c i 0
Set is distance differential accumulation sum , the end conditions of search algorithm is . Among them, meets the minimum error of the search accuracy requirement.
4 The improvement of Taylor series expansion algorithm 4.1 The improvement of initial coordinate The key of Taylor series expansion algorithm is the choice of search initial value, if the search initial value is far from the goal, after the hyperbolic equation is linearized, the error produced by the nonlinear transformation to the linear is big near the target coordinates, the error is bound to affect the positioning accuracy, even without the most optimal solution would happen; At the same time the search initial value has important influence to search convergence rate.
Literature  using the least square method to estimate the initial coordinates, the method is as follows: in equation (10), freely take two equation, the use of Fang algorithm find out the solution, a total of k=C2n-1 set of the solution, and then using the least squares and the final solution as Taylor iterative initial value. There are two main shortcomings of this method, one is that algorithm is complicated, large amount of calculation when the number of sensors is large; the other is that it does not consider the credibility of the sensors during the process of calculation, when the system error is large or gross time delay error is existed, the calculation accuracy of the initial coordinate is poor. In this paper, the determine method of the initial coordinate is as follows: (1) selection and extract the sensor signal characteristic parameters (such as the zero rate, duration of vibration, power spectrum, etc.). (2) according to the type (4) to calculate the reliability of each sensor. (3) select the credibility of the two equations from n - 1 equations and solve, obtain the optimal estimate coordinates of the source vibration x(0) , y(0) .
4.2 The improvement of the search end condition The end conditions of the literature   as follows: n 1
ri r0 c i 0
Type (13) does not take into account the credibility of the time delay difference, it takes for that all of the time delay difference are credible. When each sensor signal quality is better, the search results more accurate; Because of the complexity of the environment and the frequent outside interference, the interference degree of each sensors will be difference, near the target location search, the influence of the sensor of time delay differential to the accumulation error is big, Especially the emergence of gross error will make the search results deviate or gravely deviates from the real target location, appear even without solution. In this paper, the end conditions is n 1
i ri r0 c i 0
In it, i is the i-th sensor reliability, it is calculated by (4). In type (14) , it adds the sensor reliability, considers the credibility of time delay difference, and enhanced the accuracy of the end condition.
4.3 Improve the Taylor series expansion of positioning search algorithm process The improved Taylor series expansion of positioning search algorithm is as shown in figure 2.
5 Experimental Results and Analysis 5.1 Robustness comparing To test and compare the positioning performance of the algorithm, we take the walk vibration signals for example, and carry on the contrast experiment of the algorithm. There are five sensors components composed in the cross array, the coordinates of the receiving sensor are B1(0，0)，B2(100，0)，B3(0，100) ，B4(-100， 0)，B5(0，-100)。 Set the initial position ( x, y) of the vibration source target is
the sampling rate is 1 kHZ, the
sampling window is 2 second, for simplicity, the signal characteristics of this algorithm only use the zero rate. The first sensor coordinate is origin position, set the standard error of error 4ms ,a total of 25 different
n is from zero to 100ms, interval is
n , for each n to do 100 time location simulation experiments and the operation
result calculating mean, its results are shown in figure 3. Figure 3(a) is the location estimate value under different n on the vertical axis for Taylor algorithm and the improved Taylor series expansion of positioning algorithm, Figure 3(b) is the
location estimate value under
different n on the horizontal axis for two algorithms. Abscissa in Figure 3 is the error standard deviation n , the unit is ms, vertical axis is results average, the unit is m. Can be seen from the simulation result: The improved Taylor algorithm is more accurate positioning than Taylor algorithm; With the increment of error standard deviation n , the measurement error of improved Taylor algorithm and Taylor algorithm are bigger and bigger, but the improved Taylor algorithm is more smaller float than Taylor algorithm, so it is more stable; when the error standard deviation is greater than 40ms , the measurement results and the real value goal difference is bigger for Taylor algorithm, the error is bigger and bigger; But the error of TDOA is more and more big, the improved Taylor algorithm can keep basic flat, still can more accurately calculate the true target location.
5.2 Positioning accuracy comparison Below through the positioning of the mean square error (MSE) to evaluate these two positioning accuracy of the algorithm. Usually the indexes of measure positioning accurate degree include the mean square error (MSE), root mean square error (RMSE) and geometric accuracy attenuation factor (GDOP), etc. RMSE is as the evaluation index of this algorithm. In two-dimensional localization estimate, MSE and RMSE with the formation type: 2 2 2 2 MSE E x xˆ y yˆ ， RMSE E x xˆ y yˆ
x, y is the actual target
coordinates location of the vibration source,
xˆ, yˆ is the estimation
coordinates location of the vibration source. The simulation result is shown in figure 4, the algorithm A is the improving the Taylor series expansion of localization algorithm, algorithm B is the original Taylor series expansion algorithm. By the above figure can see, in the error phase at the same time, RMSE of the improve the Taylor series expansion of
localization algorithm is significantly lower than the original Taylor series expansion algorithm,
namely the stability of the positioning to be significantly higher than the original Taylor series expansion algorithms .The algorithm B is far less than the algorithm A when they are both affected by the error standard deviation, and with the increment of error standard deviation
the positioning performance of the two
algorithm are both down, and may even appear without solution, but the simulation can see that the improved Taylor series expansion of localization algorithm still keep high localization accuracy in the case of large measurement errors compared with other algorithms.
6 Conclusion Localization algorithm proposed in this paper, the sensor reliability is obtained by distinguishing
characteristic parameters and the gross error is rejected. On the one hand, this algorithm solve the initial value problem of the Taylor series expansion search algorithm, on the other hand, according to the reliability sensors to improve the search end condition and improve the location accuracy and robustness of the algorithm. This algorithm is adapted to the multi-sensor system, the more the received signal of sensor the better its performance, otherwise, its advantage is not obvious.
References  James J. Caffery, Jr. A new approach to the geometry of TDOA location[J]. IEEE Transactions on VTC, 2000, 4(9):1943-1949  DING Gui-lan, LIU Zhen-fu An all-fiberoptoc accelerometer based on compliant cylinder[J] Acta Optica Sinica ,2002,22(3):340-343.  Feng Lijie, Fan Yao. Target Identification Study of Multi-Sensor Based on D-S Evidence Theory Characteristics[J] Science & Technology Review, ,2014:32(15):32-36  Feng Lijie, Fan Yao. Taylor’s Series expansion search vibratory source localization algorithm based on the gross error gray discriminant[J]. Journal of Northwest Normal University, 2014,11：49-53  Zhang Jian-wu, Tang Bing, Qin Feng. Application of Chan Location Algorithm in 3–Dimensional Space Location [J].Computer Simulation, ，2009,1：323-326 FOY W H 。 .Position-location solutions by taylor series estimation[J].IEEE Trans on Aerosp Electron Syst,1976,AES-12(3):187-194.  Deng Ju Long. Gray system theory teaching [M] • Wuhan: Huazhong University Press, 1990: 24-60 Chan Y T, Ho K C.A simple and efficient estimator for hyperbolic location [J]. IEEE Trans on Signa Processing,1994,42(8):905-1915.  Xing Cuiliu, Chen Jianmin. Analysis on Positioning Accuracy of TDOA Passive Location by Multi-tation[J]. Radio Engineering, 2012, 42 (2):32-34.  Yanglin
Sun Zhong kang. TDOA Passive Location and Accuracy Analysis[J]. Journal of National
University of Defense Technology, 1998,20(2):49-53
Fig.1 Vibratory Source Localization
Calculate the sensor reliability
Choose the highest three the reliability of sensors to determine the initial value
i ri r0 c i 0 i 3
x k 1 x k x y k 1 y k y
Fig.2 Localization algorithm flow chart
(b) Fig.3 Robustness of two kinds of algorithm
Fig.4 Positioning mean square error of two s localization algorithms