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 sensors. When an unknown target emits an
acoustic or a radio signal, its position can be localized with mul-
tiple sensors using the time difference of arrival (TDOA) informa-
tion. In this paper, we consider the maximum likelihood formula-
tion of this target localization problem and provide efficient convex
relaxations for this nonconvex optimization problem. We also pro-
pose a formulation for robust target localization in the presence of
sensor location errors. Two Cramer-Rao bounds are derived cor-
responding to situations with and without sensor node location er-
rors. Simulation results confirm the efficiency and superior per-
formance of the convex relaxation approach as compared to the
existing least squares based approach when large sensor node lo-
cation errors are present.
Index Terms—Convex optimization, sensor networks, target lo-
calization.
I. INTRODUCTION
L
OCALIZING targets is a classical topic in radar and sonar
research. With the recent advances in distributed and col-
laborative signal processing, sensor networks have become
an attractive platform for target localization [1], especially
for surveillance purposes. In this paper, we consider target
localization using a network of passive sensors (i.e., sensors
which do not transmit probing signals). Such problems arise
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 ar-
rival (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 those at the sensors are assumed to be synchronized so that
the TOA information can be locally obtained at each sensor using
Manuscript received February 28, 2008; accepted January 24, 2009. First pub-
lished 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 presented at the 2008 IEEE Radar Confer-
ence, 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 60672127, by the 111 Project under Grant B08038, and by the Spe-
cial 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 Ser-
vices Networks (ISN Lab), Xidian University, Xi’an, China 710071 (e-mail:
yang001@xidian.edu.cn; wanggang198412@163.com).
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; see for example the GPS application [20]. In con-
trast, the TDOA approach relies on the time differences of arrival
at different sensors, so there is no need for the sensor clocks to
be synchronized with that of the target. Indeed, assuming clock
synchronization across sensors, we can readily estimate the dif-
ferences of signal arrival times, i.e., the TDOA information, by
cross correlating the signal samples recorded at different sensor
nodes. When the signal propagation channels are line-of-sight,
this TDOA information depends directly on the target location
relative to the sensor locations. When the sensor locations are
known, the TDOA information can be used to estimate the lo-
cation of the target. In the AOA approach, each sensor node is
equipped with an antenna array which can be used to estimate the
angle of arrival of the target signal. With multiple AOA estimates
from different sensor locations, it is possible to determine the lo-
cation of the target. However, since installing an antenna array
receiver on each sensor node can be costly, target localization
in a sensor network using AOA is less practical. In this paper,
we consider the TDOA approach for target localization.
A related sensor localization problem has been studied exten-
sively in the literature [15]–[17] whereby estimates of internode
distances between pairs of sensors are used to determine the lo-
cations of all unknown sensors. This formulation is well suited
for situations whereby a team of sensors collaborate for the pur-
pose of self-localization using TOA information. However, for
the problem of estimating the location of an uncooperative target
using passive sensors, we cannot obtain the distance information
between the target and sensor nodes. In this case, the internode
distance based formulation is no longer appropriate, and we are
naturally led to the TDOA approach.
In principle, target localization using TDOA can be realized
by intersecting the hyperbolas corresponding to the difference of
distances from the target to various sensor 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 based on least squares approximation which is quite
sensitive to the error in sensor locations. It has been observed [8]
that a slight error in sensor receiver locations can lead to a large
error in target location estimate. In practice, the sensor receiver
locations may not be known exactly. For instance, when a sensor
network is deployed in a surveillance area with sensor nodes
randomly distributed, it is difficult to know the exact locations
of all the sensor nodes even if high quality GPS is available.
This means that sensor node location errors must be taken into
account in the practical target localization process.
1053-587X/$25.00 © 2009 IEEE