A direct position determination method with combined TDOA and FDOA based on particlefilter

Zhiyu LU,Bin BA,Jinhui WANG,Wencho LI,Dming WANG

aChina National Digital Switching System Engineering&Technological R&D Cente,Zhengzhou 450000,China

bJiuquan Satellite Launch Center,Jiuquan 735000,China

1.Introduction

Target localization is widely used in civil and militaryfields.Localization algorithms have been developed rapidly,among which the traditional two-step algorithm is the most signifi-cant.Under the two-step framework,the signal measurements,such as the Time of Arrival(TOA),1Angle of Arrival(AOA),2,3Time Difference of Arrival(TDOA),4and Frequency Difference of Arrival(FDOA),5should be extractedfirst from the received source signal.Then the target position is estimated by calculating the location equation.Vast literatures have shown that the two-step method has better performance at high Signal-to Noise Ratio(SNR).6,7However,it ignores the intrinsic link between the positioning parameters of the receivers.The signal parameters acquired in thefirst step are not in accordance with the source position found in the second step,leading to the loss of the location information.Furthermore,it is inevitable to involve processing errors in the step by step calculation.Therefore,the two-step method is suboptimal,failing to get the best positioning performance.8Compared with the traditional two-step approach,the DPD algorithm proposed in recent years does not need to estimate the signal parameters or calculate the position step by step,but acquires the source position from the received signals directly based on the maximum likelihood criterion.Because of its better performance,it has become a hot research topic.9–15

Ref.9gives a systematic analysis of the DPD algorithm,and proposes a target approach for single narrowband signal emitter,which proves that the DPD algorithm outperforms the two-step method especially at low SNR.In order to further explore the advantages of DPD algorithm,Refs.10–15give a variety of improved algorithms with the integration of TOA,AOA,etc.,but these algorithms are mainly based onfixed receivers to estimate a narrowband signal emitter.With the increase of signal bandwidth and the wide use of moving receivers,such as aircraft-based,ship-based and vehicle-based platforms,it is urgent to research the DPD algorithms for wideband signal emitters in the moving receiver system.

In this paper,we focus on the location of wideband signal emitters based on moving observation platforms.To this end,the common method partitions the received signal into multiple short-time signal segments,in which the narrowband localization algorithm can still play a role to obtain the position by the joint use of all the signal segments.A DPD algorithm based on Doppler shift received by moving platforms is proposed for narrowband emitters in Ref.16,which is more precise compared with the two-step algorithms.On the basis of Refs.16,17gives a DPD algorithm which is combined with TOA and Doppler shift based on non-coherent summation of short-time signal segments.To further improve the positioning performance,Ref.18proposes an improved DPD algorithm exploiting the coherent summation of multiple short-time signal segments,while solves the problem of phase synchronization error between the receivers and the target to make the algorithm more practical.

In the passive location system,the synchronization is not accurate between the receivers and the target,so the DPD algorithm using delay and Doppler is difficult to get better performance.To solve this problem,Ref.19presents an adaptive DPD algorithm based on TDOA with least mean square(LMS)filtering,achieving good positioning accuracy.Combined with the Doppler information obtained by the moving receiver,a distributed DPD algorithm based on TDOA and FDOA is proposed in Ref.20.But the correlation between the short-time signal segments is not taken into account,so there is still room for the positioning accuracy improvement.Besides,it is very difficult to obtain the analytical solution because of the high nonlinearity of the above DPD algorithms.So in order to obtain the maximum likelihood estimation,the ergodic search method is used,which makes the positioning accuracy reach the CRLB with huge computation load and communication bandwidth.To overcome these problems,novel information technology can be used.For example,the intelligent algorithm21and the cloud computing and storage technology22,23can be used to reduce the computation loads,and the compressive sensing technology24and automatic network management technology25are helpful for reducing the communication bandwidth.Filteriterative algorithm is another method for parameter estimation,such as Extended Kalman Filter(EKF),26Unscented Kalman Filter(UKF)27and Particle Filter(PF),28which has good performance.Especially,the PF algorithm can solve the strong non-linear and non-Gaussian estimation problem,which has been proven in a variety of applications.

In summary,there are still some deficiencies in the existing DPD algorithms when the positioning of wideband signal emitters is executed based on TDOA and FDOA.How to make use of more location information contained in the signal segments to improve positioning accuracy,while avoiding the problem of large computation cost,has tremendous challenge and research merit.To accomplish this target,this paper proposes a DPD algorithm with combined TDOA and FDOA based on particlefilter,using coherent summation of the short-time signal segments to improve positioning accuracy(labeled as PFC-TF DPD).Compared with the existing literatures,the contributions of this paper lie in:

(1)The algorithm proposed in this paper makes full use of the location information contained in the coherency among the signal segments to improve positioning accuracy.The CRLB of the source position is derived,which shows that the positioning accuracy is better compared with the existing algorithms.

(2)One iterative maximum likelihood estimation method based on particlefilter is designed to solve the problem of high computation load,which improves the estimated efficiency.

(3)The influence of different parameters on the positioning performance is analyzed in the simulation part.It is shown that the positioning accuracy of the proposed DPD algorithm is proportional to interception interval of two adjacent signal segments and the number of short-time signals.The above results can be used to provide a reference of the optimal parameter configuration for different application environments.

The rest of the paper is organized as follows.The following section gives the direct positioning model.We derive Maximum Likelihood(ML)estimators based on particlefilter for our DPD algorithm in Section 3 and develop the source position CRLB in Section 4.Section 5 provides the simulation and the result analyses.Finally,Section 6 concludes the paper.

2.Positioning modeling and problem formulation

A stationary source located at o= ［ox，oy］is considered.Lis the number of moving receivers which have been synchronized.The number of short-time signal segments isK,while the interception interval of two adjacent signal segments isT0.The receivers get the signal segment at timetk，k=1，2，...，Kwhen they are located at ul，kwith velocities˙ul，k，l=1，2，...，L.The DPD scenario is shown in Fig.1.

We suppose that the source signal is

wherefcis the carrier frequency ands（t）is the signal envelope.The signal received with thelth receiver in thekth period is

Taking the signal of thefirst receiver as reference,we let

Fig.1 DPD scenario.

and then represent Eq.(2)as

where Δτl1，kand Δvl1，kare TDOA and FDOA respectively as shown in Eqs.(5)and(6),andwl，k（t）is the statistically independent complex Gaussian noises whose probability density function isC（0，σl，k）.

The received source signal would be sampled as

wherec=3×108m/s is the speed of light.Tsis the sampling interval,Nkis the number of samples taken in each signal segment,ntk=tk/Tsis the starting time of thekth segment,Δnl1，k= Δτl1，k/Tsis the discrete representation of TDOA,ejΔvl1，k（ntk+nk）Tsis the coherency item among the signal segments received in the same receiver andcis the light speed.In the PFC-TF DPD algorithm discussed in the following parts,we will use the position information inherent in ejΔvl1，kntkTsto improve location accuracy.

The signals received from all receivers are combined to be fully utilized.Let

and then gk［nk- Δnl1，k］can be expressed as

where 1Nkis aNk×1 vector with all the elements equal to 1.With combined Eqs.(8)–(10),the received signal can be expressed as

With the above notations,the combination of all received signals is

whereE［wwH］= Γ =diag｛Γ1，Γ2，...，Γk，...，ΓK｝ and Γk=E［wkwHk］.Next we will analyze the PFC-TF DPD algorithm in detail based on this signal model.

3.PFC-TF DPD algorithm

Under the positioning model given in Section 2,the PFC-TF DPD algorithm is derived step by step in the following to prove its feasibility.From Eq.(15),the received signal r is a complex Gaussian random vector with mean Hg and covariance Γ.So the Probability Density Function(PDF)can be given by

The Maximum Likelihood Estimator(MLE)of the target can be obtained by Ref.18

It is difficult to obtain the MLE of the target position because of the strong non-linearity in Eq.(17).So the ergodic search method is commonly used in many DPD algorithms,which are poor practical with huge computation load.The particlefilter algorithm has better performance when it is used to solve the strong non-linear estimation.The result can be obtained quickly through iteration procedure,which has been proved in a large number of applications.

The MLE of gkis given by

Therefore,in terms of the Bayesianfiltering problem,drawing the particles according to Eq.(21)moves the weights from timej-1 toj,i.e.,performs the prediction stage and Eq.(28)performs the update stage.

In order to update the particle more stably,we set a strategy that retains the largest weight particle of the previous generation to the next generation.That is

According to the above analysis,the computation load is mainly concentrated in Eq.(27),whose total computation cost is

The DPD algorithm based on ergodic search dividesNgrids in the target region,so the total computation cost is approximate toNDC.

The convergence accuracy of the proposed algorithm is related to the signal length,SNR,and the number of receivers.The convergence rate is related to the initial value and the number of particles.Thus,it is difficult to give a theoretical suggestion on the number of iterations when so many parameters are dealt with.In this paper,in order to simplify the calculation,afixed iteration number and particle number are set without affecting thefinal location results according to many experiments,so the total computation cost of the PFC-TF DPD algorithm is approximate toMJDC.Thus,the ratio of computation load is

The simulation part will prove thatMJwill be far less thanN,but the location accuracy is almost not decreased.In order to show the algorithm architecture more clearly based on the principle derived in this section,a possible implementation of the PFC-TF DPD algorithm is in Table 1.

4.Cramer-Rao lower bound

In this section,we are interested in the CRLB for estimation of the source position to further analyze the positioning performance of the PFC-TF DPD algorithm proposed in this paper.We define that the vector η is composed of the real-part of g,the imaginary-part of g,and the target parameters o.That is

Table 1 Implementation of PFC-TF DPD algorithm.

The receive signal is

According to Ref.18,the Fisher Information Matrix(FIM)of η is given by

Combining Eqs.(35)–(43),we can express Jηas

According to the partitioned matrix inversion formula,the FIM of o can be expressed as

CRLB can be obtained by the inverse of the Fisher Information Matrix matrix,so CRLBois

5.Simulations

In order to test the performance of the PFC-TF DPD algorithm,computer simulations are conducted in this section.Compared with the DPD algorithm based on Doppler shift(labeled with NC-F DPD)and the DPD algorithm with combined TDOA and FDOA based on non-coherent summation of short-time signal segments(labeled with NC-TF DPD),the positioning accuracy and CRLB will be analyzed.It is assumed that the target is located at o= ［0，0］in a 2-D plane.The number of receivers isL=4.The number of short-time signal segments isK=10.All parameters of the receivers are shown in Table 2.

We adopt the Gaussian random signal with zero mean and unit variance as the source signal.The simulated nominal signal carrier frequency isfc=300 MHz.The sampling interval isTs=2×10-5s.The interception interval of two adjacent signal segments isT0=0.01 s.The duration of every shorttime signal isT=1 ms.The number of samples isNk=50.The interesting region is ［-1000，1000］m.

To compare the location performance of different algorithms,in thefirst experiment,the cost functions of the candidate source positions with 1 m interval are evaluated at SNR=20 dB.The results are shown in Fig.2.In order to show the result clearly,the 3D plots and their top views are given,in whichxaxis andyaxis are the position coordinates,and z axis is the cost function value normalized by the maximum.It can be seen from Fig.2(a)and(b)that,although the SNR is very high,the NC-F DPD algorithm exhibits a curvature of large radius around the real source location.It is difficult to obtain accuracy estimation.Once the SNR is decreased,the location performance will decline rapidly.Fig.2(c)and(d)show that there is a curvature of smallradius around the true source position,which improves the estimation accuracy compared with NC-F DPD algorithm.Fig.2(e)and(f)demonstrate the effectiveness of the PFC-TF DPD algorithm with the sharper peak around the true source position,which will bring higherlocation accuracy.The simulation results are consistent with the theoretical derivation,showing that the use of the location information contained in the coherency among the signal segments is significative,which is expected.

Table 2 Parameters of receivers.

Fig.2 Evaluation of cost functions of source location estimators for each algorithm.

Fig.3 Convergence of particles.

In order to verify the computational performance of the PFC-TF algorithm,in the second experiment,with the iteration increasing,the convergence of particles and thefiltering error are shown in Figs.3 and 4 respectively under the conditions of SNR=20 dB andT0=0.01 s.The number of particles isM=50 and the number of iteration isJ=50.As can be seen from Fig.3,with the iteration increasing,the particlesflow toward the target position and eventually converge to the real position.Fig.4 shows that thefiltering error is shaking more seriously at the beginning,but after a short adjustment,the error is tiny and tends to be stable,which proves the good performance in the convergent speed.According to the simulation conditions,the ratio in Eq.(32)is λ =2.5×10-3,that is,the computation load of PFC-TF algorithm decreases by nearly 3 orders of magnitude compared with that of the DPD algorithms based on ergodic search,indicating a signifi-cant increase in computing efficiency.

In order to further illustrate the performance of PFC-TF DPD algorithm,in the third experiment,we shall contrast the localization performance of each algorithm with their CRLBs.The CRLB and RMSE of each algorithm,as a function of SNR,are achieved across 50 Monte-Carlo simulation experiments,and shown in Fig.5.It can be seen that,with the increase of SNR,the performance of each algorithm is improved,but the PFC-TF DPD algorithm is significantly better than the NC-TF DPD algorithm and NC-F DPD algorithm,which proves that the location information contained in the coherency can effectively improve positioning accuracy.The performance of PFC-TF DPD algorithm remains close to the CRLB,especially at high SNRs it coincides with the CRLB.Combined with the results of Fig.6,we can get that our algorithm is more computationally efficient and more precise for weak signals than the conventional approach,which demonstrates the utility and practicability of the method.

The performance development of each algorithm with the increase ofK,the number of short-time signals,is given in Fig.7 under the conditions of SNR=10 dB andT0=0.01 s.It can be seen that all algorithms have a performance improvement with the increase ofK.But compared with the NC-TF DPD algorithm and NC-F DPD algorithm,the performance of PFC-TF DPD algorithm is improved significantly.In addition,the PFC-TF DPD algorithm has better performance whenKis small,which means that the positioning efficiency is improved.

In the last experiment,we examine the performance of each algorithm versusT0,the interception interval of two adjacent signal segments,under the conditions of SNR=10 dB andK=10.The results are shown in Fig.6.It can be seen that the performance of NC-F DPD algorithm and NC-TF DPD algorithm are not changed for better because of their independence of the variableT0,while the performance of PFC-TF DPD algorithm is improved asT0increases.In addition,the localization accuracy of the PFC-TF DPD algorithm is always close to its CRLB,resulting in excellent performance.But whenT0＜0.001 s,due to the fact that the time interval is too short,there is no extra location information contained in the coherency,so the PFC-TF algorithm has the same performance as NC-TF algorithm.

Fig.4 Filtering error with iteration increasing.

Fig.5 Estimation accuracy of each algorithm as a function of SNR.

Fig.6 Estimation accuracy of each algorithm as a function of T0.

Fig.7 Estimation accuracy of each algorithm as a function of K.

As can be seen from the above simulation results,the PFCTF DPD algorithm proposed in this paper has excellent performance.Compared with the NC-TF DPD algorithm,it uses the correlation information among the signal segments,which solves the problem of huge computation load.Under the same conditions,the proposed algorithm obtains better estimations with less number of short-time signals,which makes the algorithm more practical.

6.Conclusions

(1)We conducted a comprehensive study on the DPD algorithm.The PFC-TF DPD algorithm is proposed,which acquires extra target position information through the correlation information among the signal segments to get better positioning performance.The CRLB of the source position is derived,which shows that the positioning accuracy is better compared with the existing algorithms.

(2)One iterative maximum likelihood estimation method based on particlefilter is designed to solve the problem of high computation load.Simulation results show that the proposed method can get better location performance than other DPD algorithms under low SNR,making it full of practical value.

(3)The algorithm can be used in many multi-sensor cooperative location scenarios,such as double-star position system,Unmanned Aerial Vehicle(UAV)-based formation system and ship-based formation system,tofinish the job of target reconnaissance,search,rescue,and so on.

Acknowledgement

This study was supported by the National Natural Science Foundation of China(No.61401513).

1.Oh D,Kim S,Yoon SH.Two-dimensional ESPRIT-like shiftinvariant TOA estimation algorithm using multi-band chirp signals robust to carrier frequency offset.IEEE Trans Wireless Commun2013;12(7):3130–9.

2.Yan F,Jin M,Qiao X.Low-complexity DOA estimation based on compressed MUSIC and its performance analysis.IEEE Trans Signal Process2013;61(8):1915–30.

3.Ba B,Liu GC,Li T,Lin YC,Wang Y.Joint for time of arrival and direction of arrival estimation algorithm based on the subspace of extended hadamard product.Acta Phys Sin2015;64(7):384–92[Chinese].

4.Lu ZY,Wang DM,Wang JH,Wang Y.A tracking algorithm based on orthogonal cubature Kalmanfilter with TDOA and FDOA.Acta Phys Sin2015;64(15):25–32[Chinese].

5.Wang G,Li YM,Ansari N.A semidefinite relaxation method for source localization using TDOA and FDOA measurements.IEEE Trans Veh Technol2013;62(2):853–5.

6.Ho KC,Chan YT.Geolocation of a known altitude object from TDOA and FDOA measurements.IEEE Trans Aerosp Electron Syst1997;33(3):770–83.

7.Chan YT,Ho KC.Joint time-scale and TDOA estimation:analysis and fast approximation.IEEE Trans Signal Process2005;53(8):2625–34.

8.Bosse J,Ferre′ol A,Larzabal P.Performance analysis of passive localization strategies:direct one step approach versus 2 steps approach.IEEE Statistical signal processing(SSP)workshop;2011.p.701–4.

9.Weiss AJ.Direct position determination of narrowband radio frequency transmitters.IEEESignalProcessLett2004;11(5):513–7.

10.Weiss AJ,Amar A.Direct position determination of multiple radio signals.EURASIP J Adv Signal Process2005;1:37–49.

11.Amar A,Weiss AJ.Direct position determination in the presence of model errors-known waveforms.Digital Signal Process2006;16(1):52–83.

12.Shalom OB,Weiss AJ.Direct positioning of stationary targets using MIMO radar.Signal Process2011;91(10):2345–58.

13.Reuven AM,Weiss AJ.Direct position determination of cyclostationary signals.Signal Process2009;89(12):2448–64.

14.Naresh V,Steven K,Quan D.TDOA based direct positioning maximum likelihood estimator and the Cramer-Rao Bound.IEEE Trans Aerosp Electron Syst2014;50(3):1616–46.

15.Tom T,Weiss AJ.High resolution direct position determination of radio frequency sources.IEEE Signal Process Lett2016;23(2):192–7.

16.Amar A,Weiss AJ.Localization of narrowband radio emitters based on Doppler frequency shifts.IEEE Trans Signal Process2008;56(11):5500–8.

17.Weiss AJ.Direct geolocation of wideband emitters based on delay and Doppler.IEEE Trans Signal Process2011;59(6):2513–21.

18.Li JZ,Yang L,Guo FC.Coherent summation of multiple shorttime signals for direct positioning of a wideband source based on delay and Doppler.Digital Signal Process2015;48:58–70.

19.Zhong S,Xia W,He Z.Adaptive direct position determination of emitters based on time differences of arrival.IEEE China summit&international conference on signal and information processing;2013 July 6–10;Beijing,China.Piscataway:IEEE Press;2013.p.230–4.

20.Pourhomayoun M,Fowler M.Distributed computation for direct position determination emitter location.IEEE Trans Aerosp Electron Syst2014;50(4):2878–89.

21.Xue Y,Jiang J,Zhao B,Ma T.A self-adaptive artificial bee colony algorithm based on global best for global optimization.Soft Comput2017;8:1–18.

22.Shen J,Shen J,Chen XF,Huang XY,Susilo W.An efficient public auditing protocol with novel dynamic structure for cloud data.IEEE Trans Inf Foren Secur2016;12(10):2402–15.

23.Fu ZJ,Ren K,Shu J,Sun XM,Huang FX.Enabling personalized search over encrypted outsourced data with efficiency improvement.IEEE Trans Parallel Distrib Syst2016;27(9):2546–59.

24.Sun YJ,Gu FH.Compressive sensing of piezoelectric sensor response signal for phased array structural health monitoring.Int J Sensor Networks2017;23(4):258–64.

25.Qu ZG,Keeney J,Robitzsch S,Zaman F,Wang XJ.Multilevel pattern mining architecture for automatic network monitoring in heterogeneous wireless communication networks.China Commun2016;13(7):108–16.

26.Luo L,Tian ZS,Chen JY.Algorithm of EKF positioning and tracking.J Chongqing Univ Posts Telecommun(Nat Sci Ed)2009;21(1):50–5[Chinese].

27.Liu Y,Wang H,Hou CH.UKF based nonlinearfiltering using minimum entropy criterion.IEEE Trans Signal Process2013;61(20):4988–99.

28.Gustafsson F.Particlefilter theory and practice with positioning applications.IEEE Aerosp Electron Syst Mag2010;25(7):53–82.