Defence Science Journal, Vol. 65, No. 1, January 2015, pp. 70-76, DOI : 10.14429/dsj.65.5474
© 2015, DESIDOC
Received 16 December 2013, revised 19 December 2014, online published 27 February 2015
Range-only Target Localisation using Geometrically Constrained Optimisation
En Fan*, Weixin Xie#, Zongxiang Liu#, and Peng-fei Li!
*Xidian University, Xi’an-710 071, China
#Shenzhen University, Shenzhen-51 8060, China
!Air Defense Forces Academy, Zhengzhou-450 052, China
* E-mail: efan@stu.xidian.edu.cn
The problem of optimal range-only localisation of a single target is of considerable interest in two-dimensional search radar networking. For coping with this problem, a range-only target localisation method using synchronous measurements from radars is presented in the real ellipsoidal earth model. In the relevant radar localisation scenario, geometric relationships between the target and three radars were formed. A set of localisation equations was derived on range error in such a scenario. Using these equations, the localisation task has been formulated as a nonlinear weighted least squares problem that can be performed using the Levenberg-Marquardt (LM) algorithm to provide the optimal estimate of the target’s position. To avoid the double value solutions and to accelerate the convergence speed for the LM algorithm, the initial value was approximately given according to observations from two radars. In addition, the relative validity has been defined to evaluate the performance of the proposed method. The performance of the proposed approach is evaluated using two simulation experiments and a real-test experiment, and it has been found to possess higher localisation accuracy than the other conventional method.
Keywords: Range-only target localisation, target localisation, nonlinear optimisation, Cramer-Rao lower bound, Levenberg-Marquardt algorithm, radar networking, two-dimensional search radar
Two-dimensional (2-D) search radar networking, which is generally utilised in the first line of air defence, has been widely applied in modern airspace control1-3. This fact generally has two reasons: on one hand, 2-D radars are cheaper than three-dimensional (3-D) radars; on the other, single 2-D radar can’t directly determine a target’s position since it is merely able to obtain the range and azimuth without the height of the target. Consequently, it is a valuable task-how to utilise the resources and measurements from multiple 2-D radars to estimate the position of a target. To simplify the description, all radars below denote two-dimensional search radars.
According to the type and working mode of sensors, the target localisation methods mainly form three categories: active localisation using range4-7, passive localisation using azimuth8-11, and combined localisation using both range and azimuth12-15. Moreover, three factors are often taken into consideration in radar networking4,12:
(a) A radar possesses higher precision in range than in azimuth since its emission lobes approximating to spindles have certain widths in the horizontal plane;
(b) Range error has less influence on localisation results than azimuth error in propagation; and
(c) A localisation dead area exists near the baseline between two radars while only two radars are employed to locate a target. For the above reasons, this research utilises three radars and their range for target localisation.
In the traditional localisation methods, only one assumption is given for simplifying the design procedures as one such assumption is, all radars are placed in the same horizontal plane and their north direction is consistent or parallel to each other by ignoring the earth’s curvature. However, these assumptions are often unsatisfied in big scenes due to the wide coverage of radar networks15. The other important information such as the types, performances, working modes, number and geometric distribution of radars are omitted, which is the important consideration in real localisation process. In addition, the least squares estimator and its modified approaches are often applied in various applications for target localisation problems5,7,11,13. Based on the above facts, a range-only target localisation method is presented in this paper. In the proposed method, the localisation model is established using range from three radars in the real ellipsoidal earth model, and the target localisation problem is formulated as a nonlinear weighted least squares problem through a set of localisation equations driven on range error. Then Levenberg-Marquardt (LM) algorithm is applied to solve the localisation equations. At last, two simulation experiments and a real-date experiment were used to show both the validity and feasibility of the proposed method.
Figure 1. Target localisation model.
As shown in Fig. 1, n radars Ri (i = 1, 2,…,n) are placed at the corresponding geographical coordinates (Bi, Li, Hi) in the localisation model, where Bi, Li and Hi denote the longitude, latitude, and height coordinate respectively; and their observations zi = (ri, θi) are received simultaneously, where ri and θi denote the range and azimuth of the target T. Theoretically, n range spheres with each corresponding radius ri and its centre at the position Ri intersect at the point, the target’s position. Hence, at least three radars are required for range-only target localisation in this case. Therefore, three radars and their range information are applied to locate a target in this research.
Taking the earth curvature into consideration, the geographical coordinate (Bi, Li, Hi) of each radar should be converted into the geocentric coordinate (Xi, Yi, Zi):
where Re and re represent the long and short radii of the earth respectively, is the earth eccentricity ratio, and
Under the assume of radars with range error, a set of geometrical equations are derived according to the geometrical relationships between the target and three radars in the localisation model as follow:
where X = (X, Y, Z) is the true geocentric coordinate of the target. In consideration of range error, Eqn (2) can be rewritten in the following formula:
where vi is range error of the i th radar. Based on Eqn (3), the localisation equations are derived as follow:
Furthermore, one can define the objective function in consideration of different influence of each radar’s range error on localisation results as follow:
where σi denotes the standard deviation of range error on the ith radar. As a result, the localisation task can be formulated as a nonlinear weighted least squares problem to provide the optimal estimate such as the minimum value for F(X).
To overcome a nonlinear least square problem, many methods have been developed such as the Newton, Gauss-Newton, and LM algorithm. The LM algorithm has the advantages on both the local convergence property of the Gauss-Newton algorithm and the global convergence property of the gradient descent algorithm, and it is one of the most effective algorithms to solve a nonlinear least square problem with small margins13,16. As a result, the LM algorithm is applied to solve target localisation problems in the following.
3.1 LM Algorithm and the Initial Value of the Target’s Position
3.1.1 The LM algorithm for Solving the Localisation EquationsThe optimal estimate for the target’s position is the value X while F(X) obtains its minimum value. To minimise F(X), the vector is defined as:
Moreover, introducing the diagonal matrix Λ, whose main diagonal elements are , and respectively, the objective function (Eqn(5)) can be rewritten as:
Then define the Jacobi matrix of d(X) at the point X = (X′, Y′, Z′):
Given , i = 1, 2, 3 and the gradient vector for F(X) can be obtained as:
The second derivative matrix (Hesse matrix) for F(X) is:
Setting
And substituting S (X) in Eqn (10), yields the following expression:
To solve Eqn (12) for X, the recursive formularies of the Newton algorithm11 is introduced:
where δk is the kth iterative step length. Due to the large computational complexity on Sk and the possible singularity on in the Newton algorithm, Levenberg and Marquardt utilised the following Equ (15) to replace Eqn (13) for calculating δk 14:
where I stands for the unit matrix, and μk ≥ 0 refers to the control parameter in the iterative process. Consequently, Eqn (14) together with Eqn (15) is called the LM algorithm. The LM algorithm is applied in the proposed method to solve the localisation equations. As a result, the main design procedure of the proposed method is illustrated as Table 1.
Table 1. Design procedure by the proposed method
3.1.2 The Initial Value of the Target’s Position
To avoid double value solutions16 and accelerate the convergence speed for the LM algorithm, the initial value X0 for the proposed method, which is the approximate position of the target T, can be calculated according to the observations zi = (ri, θi) of two radars selected from three radars. Referring to Fig. 2, a local Cartesian coordinate system was constructed, where the position of the radar R1 is as the origin O and x axis is coincident or parallel to the north direction. The position of the radar R2 is denoted as A. In the coordinate system, T1 is the projection of the target T onto the plane xOy. Finally, the coordinate x0 = (x0, y0, z0) of the target T in the local Cartesian coordinate system can be calculated as:
Figure 2. Approximate geometric relations of the target and two radars.
where r0 and θ0 are the magnitude and angle of the vector OA respectively. Consequently, the approximate geocentric coordinate X0 can be given by transforming x0 from the local coordinate system to the geocentric coordinate system.
3.2 Validity Analysis of the Proposed Method
The Cramer-Rao lower bound (CRLB)6,7,12 is the minimum mean square error (MMSE), which the unbiased estimators can reach, and it is normally used as a performance metric for localisation methods. In this paper, the localisation CRLB is driven, and the relative validity is defined as the ratio of MMSE of the proposed method to the CRLB for estimating its localisation results as below.
3.2.1 The CRLB on Localisation Results
Express Z = (X, Y, Z)T as the estimate of the target’s position and ΛZ as the likelihood function of the observation set Z = {ri, i = 1, 2, 3}, which is given as follow:
The CRLB on localisation results is determined in the following formula:
where Xtrue is the true position of the target. The Gaussian density of the range ri is obtained by the following equation:
Then the logarithm likelihood function of the observation set Z can be expressed as:
By substitution of Eqn. (20) into Eqn. (18), PCLRB(X) is simplified as:
Consequently, PCLRB(X) is used to calculate the relative validity of the proposed method.
3.2.2 Relative Validity Analysis of the Proposed Method
The relative validity of the proposed method can be defined as:
Here, acts as the mean square error of the proposed method, and it can be approximately expressed as:
where M is the number of the Monte Carlo simulation runs, and is the estimate of the target’s position for the ith simulation.
Two simulation experiments and a real-test experiment were carried to estimate the performance of the proposed method in comparison with the least squared target localisation (LSTL) method in the paper7. All experiments were conducted using a computer with a dual-core CPU of Intel Pentium 4 2.93 GHz, 1 GB RAM. The program for each experiment was performed using the MathWorks MATLAB 2009a version software.
4.1 Two Simulation Experiments
The detection area, its longitude ranging from 119.0° to 120.0° and its latitude from 39.5° to 40.5°, is equally divided into 21*21 grids. Three radars locate at (119.0°, 39.5°, 0.0 km), (120.0°, 39.5°, 0.0 km) and (119.0°, 40.2°, 0.0 km) respectively. The standard deviation σr of each radar’s range error is 100 m. To intuitively reflect the localisation performance, geometrical dilution of precision (GDOP)17 was applied to describe the 3D geometric distribution of the localisation error:
where σX, σY and σZ are the standard deviations of location errors in direction of X, Y, and Z axes, respectively in the geocentric coordinate system.
Figures 3(a) and 3(b) provide the GDOP of both the proposed method and the CRLB, respectively. Fig. 4 shows the relative validity RECE of the proposed method according to Eqn. (22). As can be seen from Fig. 3, the GDOP of the proposed method is much closed to that of the CRLB. It can be seen from Fig. 4, the values of RECE range from 0.9 to 1.1. Based on the above facts, it verified that, the proposed method can approximate the localisation accuracy of the CRLB.
To compare the proposed method with the LSTL method, six target positions were located at the same longitude 119.5° and latitude 40.0° but for different heights ranging from 6 km to 16 km with equal intervals. Figure 5 shows the root mean-squared errors (RMSE) for the target’s position using two methods for 100 Monte Carlo simulation runs. As is seen from Fig. 5, the RMSE of the proposed method are smaller than the LSTL method. Therefore, due to range with higher precision than azimuth, the LM algorithm can provide good estimates for the target’s position through the establishment of the localisation equations using range in the real ellipsoidal earth model.
Figure 3. GDOP contours by two methods: (a) the proposed method and (b) the CRLB.
Figure 4. Relative validity RECE of the proposed method.
4.2 Real-test Experiment
The real-test experiment was evaluated using real-tracking data, which is generated from of three radars (ID=RI, RII, and RIII) listed in Table 2. The radars are stationed at (119.5150°, 31.75428°, 0.0 km), (119.9560°, 31.96631°, 0.0 km) and (119.5010°, 27.99498°, 0.0 km), respectively. Due to the restricted test condition, the true positions of the targets are unknown. The radar performance parameters are represented as follow: the maximum detection distance 230.0 km, range error 200.0 m and azimuth error 1°. Table 2 lists the localisation results by the proposed method. As can be seen from Table.2, the propose method has good performance in estimate accuracy on the targets’ positions. Therefore, it is verified that the proposed method is feasible to locate a target in real case.
Figure 5. Comparison of localisation error by two methods.
Table 2. Localisation results by the proposed method
In this paper, the characteristics and shortcomings of the traditional target localisation methods in 2-D search radar networking have been analysed. Due to range with higher precision than azimuth for two-dimensional radars, a range-only target localisation method is presented using synchronous measurements from three radars. Considering the real ellipsoid earth model, the equivalent geometric model is introduced in the proposed method. A set of localisation equations is derived on range error in such a scenario. Consequently, the target localisation problem is converted into a nonlinear weighted least squares problem. The LM algorithm is applied to solve the localisation equations and to estimate the target’s position. By giving the initial value approximately, the proposed method is able to avoid the value solutions and accelerate the convergence speed. Furthermore, it can approximate the localisation accuracy of the CRLB through the analysis of the relative validity defined. The simulation results show that the proposed method is effective and has high accuracy, while the real-test result illustrates that the proposed method is feasible.
This work was supported by the National Natural Science Foundation of China (61271107, 61301074), Key Project in the National Science & Technology Pillar Programme (2011BAH24B12), Specialized Research Fund for the Doctoral Programme of Higher Education (20104408120001), Natural Science Foundation of Ministry of Education (S20120100 09417), Shenzhen Basic Research Project (JCYJ20140418095735618), and Defense Advance Research Fund Project (91400C8005001140C80340).
1. Hakl, H.; Davies, E. & Le Roux, W.H. Aircraft height estimation using 2-D radar. Def Sci. J., 2010, 60(1), 100-05. doi:10.14429/dsj.60.116
2. Fan, E.; Xie, W.X. & Liu, Z.X. Manoeuvring target tracking using fuzzy logic-based recursive least squares filter. Eurasip J. Adv. Sig. Pr., 2014, 2014(1), 1-9.
3. Fan, E.; Xie, W.X. & Liu, Z.X. Reliability-weighted nearest neighbour track association in sensor network. Sensor Let., 2014, 12(2), 319-24. doi:10.1166/sl.2014.3274
4. Yan, Z.H.; Deng, Y.X. & Gu, J.C. Three-dimension target positioning using multiple two-coordinate radar systems. J. Air Force Radar Aca. 2003, 17(2), 24-41.
5. Huang, Z. & Lu, J. Total least squares and equilibration algorithm for range difference location. Electron. Letters, 2004, 40(5), 121-22. doi:10.1049/el:20040241
6. Song, X.F.; Willett, P. & Zhou, S.L. On Fisher information reduction for range-only localization with imperfect detection. IEEE Trans. Aerosp. Elect. Syst., 2012, 48(4), 3694-702. doi:10.1109/TAES.2012.6324762
7. Huang, X.J; Han, C.J. & Zhang, T. Three-dimension target location using range information measured by networking radar. Fire Cont. Command Cont., 2005, 30(Sup.), 121-23.
8. Bishop, A.N. & Anderon, B.D.O.; Fidan, B. & Pathirana, P.N. Bearing-only localization using geometrically constrained optimization. IEEE Trans. Aerosp. Electron. Syst., 2009, 45(1), 308-20. doi:10.1109/TAES.2009.4805281
9. Iman, S.; Adrian, N.B. & Brian, D.O.A. Analysis of noise bearing-only network localization. IEEE Trans. Autom. Cont., 2013, 58(1), 247-22. doi:10.1109/TAC.2012.2206693
10. Wang, Z.; Luo, J.A. & Zhang, X.P. A novel location-penalized maximum likelihood estimator for bearing-only target localization. IEEE Trans. Signal Process., 2012, 60(12), 6066-181.
11. Choi, K.H.; Ra, W.S.; Park, S.Y. & Park, J.B. Robust least squares approach to passive target localization using ultrasonic receiver array. IEEE Trans. Ind. Electron., 2014, 61(4), 1992-002. doi:10.1109/TIE.2013.2266076
12. Chen, J.C. & Ding, L.F. Optimum position finding algorithm for multistatic radars. J. Xidian Univ., 1999, 26(4), 397-400.
13. Liu, Q. & Sun, Z.K. Optimal location algorithms in 3D space with bistatic two coordinate radar. Acta Electronica Sinica, 2000, 22(3), 366-72.
14. Lei, Y.; Feng, X.X.; Zhu, C.B. & Li, S.S. Geometric locating fusion algorithm for 2D radar networking. Syst. Eng. Electron., 2011, 33(5), 1151-156.
15. Zhang, Y.; Liu, S.T. & Jia, Z.T. Localization using joint distance and angle information for 3D wireless sensor networks. IEEE Commun. Lett., 2012, 16(6), 809-11. doi:10.1109/LCOMM.2012.041112.112150
16. Liu, G.L. Nonlinear least squares and surveying adjustment. Survey Press, Beijing, 2002.
17. Levanon, N. Lowest GDOP in 2-D scenarios. IEE Proc. Radar Sonar Navig., 2000, 147(3), 149-55. doi:10.1049/ip-rsn:20000322