IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 7, JULY 2009
2775
Efficient Convex Relaxation Methods for Robust Target Localization by a Sensor Network Using Time Differences of Arrivals
清炒生菜Kehu Yang, Member, IEEE, Gang Wang, and Zhi-Quan Luo, Fellow, IEEE
Abstract—We consider the problem of target localization by a network of passive nsors. When an unknown target emits an acoustic or a radio signal, its position can be localized with multiple nsors using the time difference of arrival (TDOA) information. In this paper, we consider the maximum likelihood formulation of this target localization problem and provide efficient convex relaxations for this nonconvex optimization problem. We also propo a formulation for robust target localization in the prence of nsor location errors. Two Cramer-Rao bounds are derived corresponding to situations with and without nsor node location errors. Simulation results confirm the efficiency and superior performance of the convex relaxation approach as compared to the existing least squares bad approach when large nsor node location errors are prent. Index Terms—Convex optimization, nsor networks, target localization.
I. INTRODUCTION OCALIZING targets is a classical topic in radar and sonar rearch. With the recent advances in distributed and collaborative signal processing, nsor networks have become an attractive platform for target localization [1], especially for surveillance purpos. In this paper, we consider target localization using a network of passive nsors (i.e., nsors which do not transmit probing signals). Such problems ari naturally in both civilian and military applications whenever a signal-emitting (or reflecting) target is to be localized. In practice, targets can be localized using either the time of arrival (TOA) [9], the time difference of arrival (TDOA) [3], [6], the angle of arrival (AOA) information [7], or a combination of the three. In the TOA approach [2], [5], the local clock at the target and tho at the nsors are assumed to be synchronized so that the TOA information can be locally obtained at each nsor using
L
Manuscript received February 28, 2008; accepted January 24, 2009. First published March 10, 2009; current version published June 17, 2009. The associate editor coordinating the review of this paper and approving it for publication was Dr. Zhi Tian. Part of this work was prented at the 2008 IEEE Radar Conference, Rome, Italy, May 26–30, 2008. The work of K. Yang and G. Wang was supported in part by the National Natural Science Foundation of China (NSFC) under Grant 6067212
7, by the 111 Project under Grant B08038, and by the Special Fund for Key Laboratories under Grant ISN02080004. The work of Z.-Q. Luo was supported in part by the National Science Foundation under Grant DMS-0610037 and by the USDOD ARMY under Grant W911NF-05-1-0567. K. Yang and G. Wang are with the State Key Laboratories of Integrated Services Networks (ISN Lab), Xidian University, Xi’an, China 710071 (e-mail: yang001@; ). Z.-Q. Luo is with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: luozq@ece. umn.edu). Digital Object Identifier 10.1109/TSP.2009.2016891
time stamps; e for example the GPS application [20]. In contrast, the TDOA approach relies on the time differences of arrival at different nsors, so there is no need for the nsor clocks to be synchronized with that of the target. Indeed, assuming clock synchronization across nsors, we can readily estimate the differences of signal arrival times, i.e., the TDOA information, by cross correlating the signal samples recorded at different nsor nodes. When the signal propagation channels are line-of-sight, this TDOA information depends directly on the target location relative to the nsor locations. When the nsor locations are known, the TDOA information can be ud to estimate the location of the target. In the AOA approach, each nsor node is equipped with an ante
nna array which can be ud to estimate the angle of arrival of the target signal. With multiple AOA estimates from different nsor locations, it is possible to determine the location of the target. However, since installing an antenna array receiver on each nsor node can be costly, target localization in a nsor network using AOA is less practical. In this paper, we consider the TDOA approach for target localization. A related nsor localization problem has been studied extensively in the literature [15]–[17] whereby estimates of internode distances between pairs of nsors are ud to determine the locations of all unknown nsors. This formulation is well suited for situations whereby a team of nsors collaborate for the purpo of lf-localization using TOA information. However, for the problem of estimating the location of an uncooperative target using passive nsors, we cannot obtain the distance information between the target and nsor nodes. In this ca, the internode distance bad formulation is no longer appropriate, and we are naturally led to the TDOA approach. In principle, target localization using TDOA can be realized by intercting the hyperbolas corresponding to the difference of distances from the target to various nsor nodes. In this paper, we consider a maximum likelihood formulation of the target localization problem. Since the resulting estimation problem is nonlinear and nonconvex, the existing approach [6], [8] for this problem is bad on least squares approximation which is quite nsitive to the error in nsor locations. It has been obrved [8] that a slight error in nsor receiver locations can lead to a large
error in target location estimate. In practice, the nsor receiver locations may not be known exactly. For instance, when a nsor network is deployed in a surveillance area with nsor nodes randomly distributed, it is difficult to know the exact locations of all the nsor nodes even if high quality GPS is available. This means that nsor node location errors must be taken into account in the practical target localization process.
1053-587X/$25.00 © 2009 IEEE
Authorized licend u limited to: XIDIAN UNIVERSITY. Downloaded on October 20, 2009 at 05:26 from IEEE Xplore. Restrictions apply.
2776
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 7, JULY 2009
The robust estimation problem of this kind can be formulated using the optimum worst-ca performance criterion. Indeed, veral robust signal processing problems have been formulated in this manner and later successfully transformed into either a convex cond-order cone program (SOCP), or a midefinite program (SDP) [13]–[15], [18]. For instance, the convex SOCP approach
has been successfully applied to robust adaptive beamforming [13] in the prence of array gain errors. In this paper, we consider a maximum likelihood formulation of the target localization problem in the prence of nsor node location errors, and propo veral convex relaxations for this problem and provide finite convex conic reformulations. The latter can be solved efficiently by modern interior point methods [14]. The paper consists of six ctions. Section II prents the target localization using SOCP and SDP relaxation in the abnce of node location errors. In Section III, robust localization in the prence of node location errors is formulated. Section IV gives the Cramer-Rao Bound (CRB) analysis for the cas with and without node location errors. The simulation results are given in Section V. Section IV concludes the paper. II. PROBLEM FORMULATION Consider a scenario whereby a network of passive nsors collaborate to localize an unknown target. The locations of the nsor nodes are assumed to be known (possibly inexactly). In the ensuing mathematical formulation, we adopt the following notations: is the signal propagation delay from the target to is the location of the unknown the th nsor node; emitter to be estimated; is the th column of , true , location of th nsor node; is the th column of estimated (or presumed) location of th nsor node; is the is the number of nsor nodes; is the th speed of light; column of , location error of th nsor node; and is the bound of nsor location errors. Define (1) where (2) Also, we define (3) Assuming line-of-sight signal propagation, the TDOA measurement can be denot
ed by (4) , and is the measurement noi. If where the measurement noi is independent Gaussian with zero mean, then the maximum likelihood formulation of the target localization problem can be directly formulated as (5)
A. Localization With TDOA Using Second-Order Cone Programming (SOCP) Relaxation The maximum likelihood target localization (5) is a nonlinear optimization problem. Due to nonconvexity, it is difficult to solve. We now pursue a convex relaxation via SOCP . Intro, denoted ducing some auxiliary variables , the localization problem of (5) can be by equivalently written as
(6) We can relax the equality constraints in (6) as inequality constraints, yielding the following SOCP formulation:
(7) where is a small positive constant for penalization. Notice that, without the penalty term, the above SOCP relaxation (7) would be ill-pod since adding a constant to all would not change the objective value, while the constraints could all be satisfied for any choice of , as long as ’s are chon to be sufficiently large. It should be noted that (7) suffers from a convex hull problem: the optimal solution of the SOCP relaxation problem (7) always lies in the convex hull of the nsor nodes. When the target is located in the convex hull of the obrving nsor nodes, then the target c
an be correctly localized. However, when the target lies outside of the convex hull of nsor nodes, target localization using (7) can fail. Unfortunately, this means that the above SOCP relaxation cannot be ud to localize an aerial target with a network of nsors deployed on the ground. However, the SOCP formulation (7) can be ud for lf-localization of randomly distributed nsor nodes as long as a few anchor nodes equipped with GPS are prent in the outskirts of the network. Similar convex hull problem has also been obrved in a related formulation of nsor localization problem using interdistance information between nsor nodes [16]. B. Localization Using SDP Relaxation We now pursue an alternative SDP relaxation which can avoid the convex hull problem. Denote the objective function of (6) as and notice that (8) where
(9) (10)
Authorized licend u limited to: XIDIAN UNIVERSITY. Downloaded on October 20, 2009 at 05:26 from IEEE Xplore. Restrictions apply.
YANG et al.: EFFICIENT CONVEX RELAXATION METHODS
军长夫人太调皮
2777
人类群星闪耀时读后感. . . . . . . . . . . . .. .
..
.
..
.廉洁格言
. . . .. .. . . . . . . (12) (13) (11)
The optimization problem (6) can be cast into the following SDP:
.. ..
. .
. .
The dimension of is . According to (8), the objective function of (6) can be written as
(20) where is a positive constant for penalization. Notice that suitable penalty constant is often need
ed for the above SDP to have a good solution. Suitable is often chon such that the minimum of the minimized primal objective function can be reached, which is suitable to the penalty constant in the subquent formulations. The formulation (20) can be easily extended to the ca where i.i.d. TDOA measurements are available. Assume a total of in (4) are that measurement nois jointly Gaussian with zero mean. Then the maximum likelihood estimation of can be formulated as
(14) where
(15) It is obvious that is midefinite, i.e., can be reprented as . The constraint
(21) where (16) where is the 3 3 identity matrix, and (17) Moreover, by Cauchy-Schwartz inequality, we have time , and the matrices , is the covariance matrix of the measurement noi, denotes the measure vector at are defined by (22) where . To facilitate convex relaxation, we rewrite the objective function of (21) as
(18) where (19) with Using the above relations and the following relaxations: defined by (24) where (25)
Authorized licend u limited to: XIDIAN UNIVERSITY. Downloaded on October 20, 2009 at 05:26 from IEEE Xplore. Restrictions apply.
(23)
2778
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 7, JULY 2009
(26)
According to (1), we e that . Using the above firstorder approximation, (29) can be reformulated as
(27) Notice that if the measurement nois are uncorrelated across time and space, then we can replace in (25)–(27) by
(30) where the nsor location errors are constrained in a box. Tho constraints make the above robust formulation difficult to solve. To facilitate numerical optimization, we replace the box with an ellipsoid constraint constraint , so that (30) can be written as
It will be en in Section V that multiple TDOA measurements can improve the estimation performance. III. ROBUST LOCALIZATION IN THE PRESENCE OF SENSOR LOCATION ERRORS The target localization methods prented in the previous ction require accurate estimates of ns
or locations. Unfortunately, the latter is difficult to obtain in practice. In this ction, we prent a robust target localization method which explicitly accounts for the possible errors in nsor locations. Assuming that the TDOA measurement nois are independent Gaussian samples, the maximum likelihood estimation (MLE) of the target location in the prence of nsor location errors is performed with the log-likelihood function (ignoring a constant term) in the similar form to (23) given by
(31) This can be further reprented by
(32) The constraint (33) can be written as
(28) where is defined by (10), and is by (24). The robust target localization by maximizing the worst-ca likelihood function leads to the following formulation
(34) which is equivalent to the implication
(29) where Taylor expansion, is defined by (1). Using the first-order can be reprented as (35) can be written in matrix form by
奖学金评定标准(35)
(36) Let where
(37)
Authorized licend u limited to: XIDIAN UNIVERSITY. Downloaded on October 20, 2009 at 05:26 from IEEE Xplore. Restrictions apply.
YANG et al.: EFFICIENT CONVEX RELAXATION METHODS竞天择
2779
By the S-procedure in control theory [14], the implication (35) such that holds if and only if there exists a (38) Define (39) Using (38) and following the similar derivation for (20), we can relax (31) as the following SDP:
Since
忍者电影
, it follows: (44)扶持政策
so that (45) where (46) (47) Hence, we have the following Cramér–Rao bound (CRB) of the variance
of the target location estimate : (48) where matrix denotes the vector by the diagonal elements of (Matlab notation).
B. Cramér–Rao Bound of Joint Target and Node Location Estimation As is known, the location information of nsor nodes in nsor networks are usually not exactly known and are often estimated via physical layer lf-localization methods of the nsor network, for example, such as the SOCP localization method discusd in Section II. For clarity, we will call the node location estimates “node location obrvations.” Under the assumption that the TDOA measurement nois and the node location obrvations are independent Gaussian samples, the log-likelihood function of the joint target and node location estimation is given by
(40) where is a positive constant for penalization, and should be chon according to the size of the nsor location error, e Procedure 2 in Section V. IV. CRB A. Cramér–Rao Bound of Target Location Estimation With Exactly Known Sensor Node Locations Assume that the nsor node locations are exactly known. With multiple independent TDOA measurements, the log-likelihood function of the target location estimation (after ignoring the constant term) is given by (21)
(49) is defined by (10), and and ( and are defined in Section II), is the covariance matrix of the node l
ocation obrvation vector , is the th location obrvation of all the corresponding nodes, is the number of node location obrvations. For the and worst ca, is often assumed, where is the variance of the coordinate error of the node locations. Define (50) and is replaced by . The Fisher information matrix of the log-likelihood function of (49) is defined by where
(41) The corresponding Fisher information matrix [19] is defined by (42) where
(43)
(51)
Authorized licend u limited to: XIDIAN UNIVERSITY. Downloaded on October 20, 2009 at 05:26 from IEEE Xplore. Restrictions apply.
