Semidefinite programming approach for TDOA/GROA based source localization

Yanshen Du,Ping Wei,and Huaguo Zhang

Schoolof Electronic Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China

Semidefinite programming approach for TDOA/GROA based source localization

Yanshen Du*,Ping Wei,and Huaguo Zhang

Schoolof Electronic Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China

Time-differences-of-arrival(TDOA)and gain-ratios-ofarrival(GROA)measurements are used to determine the passive source location.Based on the measurement models,the constrained weighted least squares(CWLS)estimator is presented. Due to the nonconvex nature of the CWLS problem,it is difficult to obtain its globally optimal solution.However,according to the semidefinite relaxation,the CWLS problem can be relaxed as a convex semidefinite programming problem(SDP),which can be solved by using modern convex optimization algorithms.Moreover, this relaxation can be proved to be tight,i.e.,the SDP solves the relaxed CWLS problem,and this hence guarantees the good performance of the proposed method.Furthermore,this method is extended to solve the localization problem with sensor position errors.Simulation results corroborate the theoretical results and the good performance ofthe proposed method.

gain ratios ofarrival(GROA),time difference of arrival (TDOA),localization,constrained weighted leastsquares(CWLS), semidefinite programming problem(SDP).

1.Introduction

The problem of passive source localization has drawn significantattention owing to its importance in many applications such as radar,sonar,wireless sensor network,and microphone arrays[1–5].In general,a number of spatially separated sensors are used to receive the emitted or reflected signal from the source in a passive localization system.Then,time-of-arrival(TOA),time-difference-ofarrival(TDOA),received-signal-strength(RSS)and angleof-arrival(AOA)measurements can be extracted from the signals received by the sensors.Based on these measurements,the source location can be estimated by solving a setof nonlinearequations.

The TDOAbased localization[5–8]and RSS based localization[9–12]have been extensively investigated in the past few decades.However,most of the existing literature concentrates on utilizing only either TDOA information or RSS information.In fact,the TDOA and RSS measurements can be combined to provide a better performance in the localization problem.Cui et al.[13]proposed a 2-D sound source localization problem,where the TDOA and interauralleveldifference(ILD)measurements oftwo sensors are applied together.Lateron,Ho etal.[14]performed a theoreticalstudy on the passive source location problem by using both TDOA and gain-ratios-of-arrival(GROA) measurements.Here,GROA is defined as the ratio of the received signal amplitude at the reference sensor to any other sensor.Ithas been proven in[14]thatthe additional GROA information can be used to improve the accuracy oflocalization.The improvementincreases with the factor c/B,where c is the signal propagation speed and B is the signal bandwidth.Moreover,the two-step weighted least squares(WLS)method was presented in[14]to estimate the source location by using TDOA and GROA measurements.The main concept of the two-step WLS method is to obtain a set of linear equations by introducing a nuisance parameterand solve the subsequentlinear equations in the WLS sense.This method can attain the Cram′er-Rao lower bound(CRLB)at sufficiently low noise levels,but degrade rapidly at high noise levels.Furthermore,extensions of this method in the presence of sensor position errors have been reported in[15,16].In[17],Hao et al. proposed the basic Newton method and Broyden-Fletcher-Goldfarb-Shanno(BFGS)quasi-Newton method,which iteratively linearize the nonlinear WLS problem by Taylorseries expansion.The BFGS method can obtain good performance only when there is a sufficientgood initialguess, which is,however,difficultto be obtained in practice.

Recently,the semidefinite programing relaxation(SDR) technique has been widely used to the localization problem [18–21]due to its favorable performance.In this paper,wepropose an SDR method to solve the TDOA/GROA based source localization problem.Based on the measurement models,the constrained weighted least squares(CWLS) estimator is presented.Then we implement SDR on the CWLS to obtain a convex semidefinite programming problem(SDP),which can be solved efficiently by using modern convex optimization methods such as SDPT3[22] and SeDuMi[23].Moreover,the SDR can be proved to be tight so that the SDP is guaranteed to have the same optimalvalue as the original CWLS problem.This feature guarantees the good performance of the proposed method. Furthermore,the proposed SDR method is extended to the localization case when there are errors in sensor positions. In conclusion,the main contributions of this paper include the following.

(i)An SDR method is proposed to solve the TDOA and GROA based source localization problem by approximating the CWLS problem.

(ii)The proposed SDR is proved to be tight,and hence guarantees the good performance.

(iii)The proposed method is extended to the localization case in the presence of errors in sensor positions.

The rest of the paper is organized as follows.Section 2 provides the TDOA and GROAmeasurementmodels.Section 3 presents the proposed SDR method for the localization without and with sensor position errors.Section 4 compares the localization accuracy ofthe proposed method to the two-steps WLS method as wellas CRLB,and Section 5 give the conclusions.

NotationVectors and matrices are denoted by boldface lowercase and boldface uppercase letters,respectively.The i th componentof a vector a is written as a(i),and the i th to j th components of a vector a as a(i:j).The i th row of a matrix A is denoted by A(i,:)and the(i,j)th element of A by A(i,j).The identity matrix of order n is denoted by In.The k×1 zero column vector and the k×n zero matrix are written as 0kand Ok,n,respectively.Given a matrix A,tr(A)means the trace of A,AR0 means A is positive semidefinite and ATmeans the transpose of A.

2.Measurement models

We consider the scenario in 3D space where M sensors at known locations are used to locate an emitting source at position uo= [x0,yo,zo]T.The signals received at the sensors can be mathematically modeled as[14]

where the signal s(t)and the noise ni(t)are assumed to be the zero-mean Gaussian random process and independent of one another.ti1and gi1are the time delay and attenuation of the signalreceived atsensor i with respectto those of the reference sensor 1.

As in the related works found in literature,we assume directline-of-sightpropagation of the source signal to the sensors and there is no multipath reflection.Furthermore, we assume that the propagation is in free space so that the attenuation is proportionalto the distance between the source and the receiving sensor[14].Under these assumptions,the noise-free TDOA and GROA measurements are, respectively,given by

where c is the signalpropagation speed,and

is the true distance between the source and sensor i.For simplicity,we collectin(2)to formthe true TDOAvec-to form the true GROA

Assume that we have the noise TDOA and GROA measurements denoted by t=[t21,t31,...,tM1]Tand g=[g21,g31,...,gM1]T,respectively,which can be described by the additive noise models as

whereΔt=[Δt21,Δt31,...,ΔtM1]TandΔg= [Δg21,Δg31,...,ΔgM1]Tare the TDOA and GROA noise vectors,respectively.Furthermore,we assume that Δt andΔg follow mutual independent Gaussian distribution with zero means and covariance Qt=E[ΔtΔtT], Qg=E[ΔgΔgT],respectively.

For simplicity,multiply t by c to form the measurement vector of range difference of arrival(RDOA)given by

3.Source localization via semidefinite programing

In this section,the new localization methods via SDR are presented.We first consider the case withoutsensor position errors,and then extend the method to the case with sensor position errors.

3.1 Localization without sensor position errors

The noise-free RDOA model(5)is equivalentto

Squaring both sides of(7),and substituting(3)for r andyields

For GROAmeasurements,we have the relationfrom the second equation of(2).According to(7),we get

By collecting allthe equations in(9)and(11),we have

According to(12)and(13),the CWLS estimator can be formulated as

where Q=CoQαCoT.The CWLS estimator(14)is nonconvex and difficult to be solved directly.To handle this difficulty,we borrow the idea from[19]to approximately solve the CWLS problem based on the SDR technique.

Equation(14)can be reformulated as

By denoting Y=yyT,(15)can be equivalently written as

The lastconstraint Y=yyTcan be decomposed into two constraints[24]:

Only the constraint rank(Y)=1 is nonconvex,the objective function and allother constraints are convex.Thus, by dropping the rank-1 constrain,we obtain the following SDP:

which is convex and can be solved very efficiently by using interior-pointmethods[22,23].be an optimalsolution of the problem(18). According to[25],we have

where n=1 is the number of equality constraints in(18). Obviously,we get rankor equiva-=1.That is say,for an optimal solution of(18),the dropped rank constraint from(15)to(18)is always satisfied.This indicates that the proposed SDR is tight,i.e.,?y is justthe optimalsolution ofthe problem(15). Note that the weighting matrix Q in(14)is dependent on the true distance values thatare notknown.For the implementation purpose,we set Q to Qαand apply(18)to produce an initialestimate of u,which is then used to compute Q so thata more accurate u can be obtained by solving(18)again.

3.2 Localization with sensor position errors

In practice,the receiver locations may not be known exactly.We can only obtain their measurements which canwhereΔsiis the vector of position measurement errors.For simplicity,we combine all the estimations of receiver positions as theand the true position asthen the receiver location error vector isΔβ=In this study,we assumeΔβis zero-mean Gaussian distributed with the covariance matrix E[ΔβΔβT]=Qβ, and is mutually independentwith the TDOA/GROA measurementerrorsΔα.=di1?Δdi1,g oi1=gi1?Δgi1andinto(8)and(10),then applying the firstorder Taylor’s series expansion aroundand neglecting the second-order noise terms,we getAll the equations in (20)can be combined to yield the following matrix form:are,respectively,obtained byin h,G,yo,and Coin(13),andThe i th(i=1,...,M?1)row of

Based on(21),we can obtain the following approximate CWLS estimator of uo:

Comparing(23)with(14),we find thatthese two equations have the same form.Thus,by using the same procedure in Section 3.1,we obtain an SDP which is similar to (18) Denote the optimalsolution of(24)asing(19),we know that rankSDP(24)solves the originalCWLS problem(23).

Note thatwe stilluse the same scheme described in Section 3.1 to obtain the weighting matrix

3.3 Comparison with other methods

Here,we make a comparison between the proposed SDR method with the existing two-step WLS method[14]and BFGS method[17].

The two-step WLS method approximately solves the CWLS problem(14)by using two successive WLSs.The first WLS directly solves(14)by omitting the constraint y(4)=‖y(1:3)and the second WLS refines the solution by taking this constraint into account.This twostep procedure cannot achieve the optimal solution of the CWLS(14),particularly atthe highernoise level.

The BFGS method solves a nonlinear WLS problem which is equivalentwith the CWLS problem(14)by iteratively localsearch.However,due to the nonconvex feature of the nonlinear WLS problem,such a technique requires carefully chosen initial guesses which are near the actual solution.Convergence is notguaranteed and one could end up with a localminimum solution.

In the comparison,the SDP can always produce a global solution since it is a convex problem.Furthermore,as aforementioned,the proposed SDR in this paper is tight, which means that the optimal solution of the SDP is also thatofthe CWLS.In conclusion,we always obtain the optimalsolution of the original CWLS by solving the SDP.

4.Simulation results

This section presents a set of Monte Carlo simulations to corroborate the theoretical development and evaluate the performance of the proposed SDR algorithm by comparing with the two-step WLS methods[14,15]and CRLBs [14,16].The SDPs are solved by using the CVX toolbox [26]with the SeDuMisolver.

An array of six sensors is chosen as the same geometry in[14],and the positions of receivers are listed in Table 1.The TDOA and GROA measurements are generated by adding the zero mean Gaussian noise to the true values. The covariance matrices of TDOA and GROAare assumed to be their CRLBs,respectively,i.e.,Qt=CRLB(t) and Qg=CRLB(g),which have been studied in[14]. We assume that the signal s(t)and noises ni(t)are zeromean Gaussian,and the noise is independent and identically distributed across different sensors,then CRLB(t) and CRLB(g)have the following forms:

SNR is the signalto noise ratio,B is the bandwidth of the source signal and T is the observation period.In the following simulations,we assume that the signal bandwidth B and the observation period T satisfy TB/π=200 000 and the factor c/B is 100 m,where B/πis the sampling frequency in Hz;they are referred to[14].

The performance in terms of the root meandenotes the estimated source position at ensemble k and K=5 000 is the number of ensemble runs.

Table 1 Sensors position

4.1 Localization performance withoutsensor position errors

We consider two localization cases,near-field source localization and far-field source localization.

The first simulation is concerned with near-field source localization.The true position of the source is uo= (80,80,80).Fig.1 shows the RMSEs of position estimation of the proposed method and the two-step WLS method,as wellas the CRLBs with the increase of SNR.It can be seen thatthe two-step WLS estimator departs from the CRLB at SNR about?3 dB,while the proposed SDP method is still close to the CRLB until SNR＜?11 dB. This is because the two-step method inevitably introduces error during the two steps of the approach to the CWLS problem,and this approximate errortends to become larger with the increase of measurement noise.In contrast,the SDP can always find outthe optimalsolution ofthe CWLS.

Fig.1 Comparison of localization accuracy versus SNR for nearfield source localization without sensor position errors,true position uo=(80,80,80)

In Fig.2,the simulation results clearly demonstrate that the biases of the proposed SDP method are significantly smaller than those of the two-step WLS method over the whole SNR range.

Next,we considerthe far-field case,where the true position ofthe source is uo=(4 000,3 800,3 400).The simulation results in terms of estimation RMSEs and biases are shown in Fig.3 and Fig.4,respectively,from which we see that the proposed estimator is superior to the two-step WLS method again.

Fig.2 Comparison of estimation bias versus SNR for near-field source localization without sensor position errors,true position uo=(80,80,80)

Fig.3 Comparison of localization accuracy versus SNR for farfield source localization without sensor position errors,true position uo=(4 000,3 800,3 400)

Fig.4 Comparison of estimation bias versus SNR for far-field source localization without sensor position errors,true position uo=(4 000,3 800,3 400)

4.2 Localization performance with sensor position errors

Here we consider the localization problem with sensor position errors.The true positions of the sensors are the same as those in Table 1.In each Monte Carlo simulation,we assume the measurements of the sensors positions are computed by adding to the true values Gaussian noise with covariance matrix equal to Qβ={8,8,8,2,2,2,10,10,10,6,6,6,5,5,5,3,3,3}.

As in the lastsubsection,we firstconsiderthe near-field case,where the source position is still uo=(80,80,80).=?5 dB.The simulation results in terms of the estimation RMSEs and biases are shown in Fig.5 and Fig.6,respectively.From Fig.5 we see that the two-step WLS method cannotachieve the CRLB accuracy over the whole SNRrange,while the proposed SDP method is close to CRLB when SNR is larger than?11 dB.

Fig.5 Comparison of localization accuracy versus SNR for nearfield source localization with sensor position errors,true position uo=(80,80,80)and=?5 dB

Fig.6 Comparison of estimation bias versus SNR for near-field source localization with sensor position errors,true position uo= (80,80,80)and=?5 dB

Furthermore,Fig.6 shows thatthe estimation biases of the proposed SDP method are invariably lower than those of the two-step WLS method.

Next,we considerthe far-field case,where the source is located at uo=(4 000,3 800,3 400)as the same to the previous subsection.Here,we setdB.Again,we see from Fig.7 and Fig.8 that the SDP method performs much better than the two-step WLS method in terms of both estimation RMSEs and biases.

Fig.7 Comparison of localization accuracy versus SNR for farfield source localization with sensor position errors,true position uo=(4 000,3 800,3 400)and=0 dB

Fig.8 Comparison of estimation bias versus SNR for far-field source localization with sensor position errors,true position uo= (4 000,3 800,3 400)and=0 dB

5.Conclusions

A novelmethod is proposed for TDOA and GROA based localization in this paper.Based on the TDOA and GROA measurements,the CWLS problem is presented.To handle the difficulty thatthe CWLS is nonconvex,we employ the SDR approach to relax the CWLS into an SDP problem.The proposed SDR is proved to be tight.This feature ensures that the SDP can always find the optimalsolution of the relaxed CWLS.Simulation results corroborate that the proposed SDR method significantly outperforms the two-step WLS method for the localization problem with or withoutsensor position errors.

[1]G.C.Carter.Time delay estimation for passive sonar signal processing.IEEE Trans.on Acoustic,Speech and Signal Processing,1981,29(3):463–470.

[2]J.C.Chen,K.Yao,R.E.Hudson.Source localization and beamforming.IEEE SignalProcessing Magazine,2002,19(2): 30–39.

[3]C.Meesookho,U.Mitra,S.Narayanan.On energy-based acoustic source localization for sensor networks.IEEE Trans. on Signal Processing,2008,56(1):365–377.

[4]J.Y.Shen,A.F.Molisch,J.Salmi.Accurate passive location estimation using TOA measurements.IEEE Trans.on Wireless Communication,2012,11(6):2182–2192.

[5]P.Stoica,J.Li.Source localization from range-difference measurements.IEEE Signal Processing Magazine,2006,23(6): 63–66.

[6]B.Friedlander.A passive localization algorithm and its accuracy analysis.IEEE Journal of Oceanic Engineering,1987, 12(1):234–245.

[7]J.Smith,J.Abel.Closed-form least-squares source location estimation from range-difference measurements.IEEE Trans. on Acoustic,Speech and Signal Processing,1987,35(12): 1661–1669.

[8]Y.T.Chan,K.C.Ho.A simple and efficient estimator for hyperbolic location.IEEE Trans.on Signal Processing,1994, 42(8):1905–1915.

[9]Y.H.Hu,D.Li.Energy based collaborative source localization using acoustic micro-sensor array.IEEE Workshop on Multimedia Signal Processing,2002:371–375.

[10]X.H.Sheng,Y.H.Hu.Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensornetworks.IEEE Trans.on SignalProcessing,2005, 53(1):44–53.

[11]H.C.So,L.X.Lin.Linearleastsquares approach foraccurate received signalstrength based source localization.IEEE Trans. on Signal Processing,2011,59(8):4035–4040.

[12]R.W.Ouyang,A.K.S.Wong,C.T.Lea.Received signal strength-based wireless localization via semidefinite programming:non-cooperative and cooperative schemes.IEEE Trans. on Vehicular Technology,2010,59(3):1307–1318.

[13]W.W.Cui,Z.G.Cao,J.Q.Jian.Dual-microphone source location method in 2-D space.Proc.of the IEEE International Conference on Acoustic,Speech and Signal Processing,2006: 845–848.

[14]K.C.Ho,M.Sun.Passive source localization using time differences of arrival and gain ratios of arrival.IEEE Trans.on Signal Processing,2008,56(2):464–477.

[15]B.J.Hao,Z.Li,J.B.Si,et al.Passive multiple disjoint sources localization using TDOAs and GROAs in the presence ofsensor location uncertainties.Proc.of the IEEE InternationalConference on Communications,2012:47–52.

[16]B.J.Hao,Z.Li,Y.M.Ren,et al.On the Cramer-Rao boundof multiple sources localization using RDOAs and GROAs in the presence ofsensorlocation uncertainties.Proc.ofthe IEEE Wireless Communication Network,2012:3117–3122.

[17]B.J.Hao,Z.Li.BFGS quasi-Newton location algorithm using TDOAs and GROAs.Journal of Systems Engineering and Electronics,2013,24(3):341–348.

[18]P.Biswas,T.C.Lian,T.C.Wang,etal.Semidefinite programming based algorithms for sensor network localization.ACM Trans.on Sensor Networking,2006,2(2):188–220.

[19]G.Wang,Y.M.Li,N.Ansari.A semidefinite relaxation method for source localization using TDOA and FDOA measurements.IEEE Trans.on Vehicular Technology,2013,62(2): 853–862.

[20]K.Yang,G.Wang,Z.Q.Luo.Efficient convex relaxation methods for robusttargetlocalization by a sensor network using time differences of arrivals.IEEE Trans.on Signal Processing,2009,57(7):2775–2784.

[21]Y.S.Du,P.Wei,W.C.Li,etal.Doppler shift based target localization using semidefinite relaxation.IEICE Trans.on Fundamentals ofElectronics,Communications and Computer Sciences,2014,E97-A(1):397–400.

[22]R.H.T¨uut¨unc¨u,K.C.Toh,M.J.Todd.Solving semidefinite quadratic-linear programs using SDPT3.Mathematical Programming,2003,95(2):189–217.

[23]J.F.Sturm.Using SeDuMi 1.02,a Matlab toolbox for optimization over symmetric cones.Optimization Methods and Software,1999,11(1):625–653.

[24]S.Boyd,L.Vandenberghe.Convex optimization.New York: Cambridge University Press,2004.

[25]A.I.Barvinok.Problems of distance geometry and convex properties of quadratic maps.Discrete Computational Geometry,1995,13(1):189–202.

[26]M.Grant,S.Boyd,Y.Ye.CVX:Matlab software for disciplined convex programming,2008.

Biographies

Yanshen Duwas born in 1988.He received his B.E.degree in electrical engineering from Southwest University,Chongqing,China,in 2009.He is currently working toward his Ph.D.degree in the School of Electronic Engineering,University of Electronic Science and Technology of China, Chengdu,China.His research interests include array signalprocessing and source localization.

E-mail:duyanshen@hotmail.com

Ping Weiwas born in 1966.He received his B.S. and M.S.degrees both in the electronic engineering from Beijing Institute of Technology in 1986 and 1989,respectively.He received his Ph.D.degree in communication and electronic system from the University of Electronic Science and Technology of China(UESTC)in 1996.He is now a professor in the Schoolof Electronic Engineering of UESTC. His research interests include spectral analysis,array signal processing, electronic surveillance,and communication signalprocessing.

E-mail:pwei@uestc.edu.cn

Huaguo Zhangwas born in 1979.He received his Ph.D.degree in signal and information processing from University of Electronic Science and Technology of China in 2011.Now he is an associate professor in the School of Electronic Engineering of University of Electronic Science and Technology of China.His research interests include noncooperative communication signal processing and array signal processing.

E-mail:uestczhg@163.com

10.1109/JSEE.2015.00075

Manuscript received April 10,2014.

*Corresponding author.

This work was supported by the National Natural Science Foundation of China(61201282)and the Science and Technology on Communication Information Security Control Laboratory Foundation (9140C130304120C13064).