1514 IEEE SENSORS JOURNAL, VOL. 13, NO. 5, MAY 2013
New Semidefinite Relaxation Method for Acoustic
Energy-Based Source Localization
Gang Wang, Youming Li, and Rangding Wang
Abstract—The acoustic energy-based source localization prob-
lem is addressed. Based on the noisy acoustic energy measure-
ments, we obtain a nonlinear and non-convex weighted least
squares (WLS) formulation for this problem, whose globally
optimal solution is hardly obtained without a good initial esti-
mate. To overcome this difficulty, we first transform the original
measurement model to obtain an approximate WLS formulation,
and then employ the semidefinite relaxation (SDR) technique
to obtain a semidefinite programming (SDP), which can be
solved very efficiently. The SDP solution is further refined using
the conventional Gaussian randomization procedure. Moreover,
we propose an alternating estimation procedure to handle the
localization problem when the decay factor is unknown. Simu-
lation results show that the proposed SDR method significantly
outperforms the existing methods.
Index Terms—Acoustic energy, semidefinite relaxation, sensor
network, source localization, weighted least squares.
I. INTRODUCTION
S
OURCE localization has received much attention since it
has found many applications in radar, sonar, microphone
arrays, and others [1]. The source is usually located using time-
of-arrival (TOA) [2]– [5], time-difference-of-arrival (TDOA)
[5]–[8], received-signal-strength [9], [10], or acoustic energy
measurements [11]– [18], which are collected by various
wireless networks. In the past few years, acoustic energy
based localization has been extensively studied due to its
low cost and easy implementation, compared with TOA and
TDOA based localization. In practice, the acoustic energy
measurements can be utilized to passively locate a source in
a small region.
The research on energy based source localization starts
from 2003. In [11], Li and Hu proposed an acoustic energy
decay model, which is verified in the real-field experiment.
According to this model, the quadratic elimination (QE)
method was proposed. In [12], the maximum likelihood (ML)
formulation for the multiple-source localization problem was
studied. The ML problem is solved using local search meth-
ods, which, however, are quite time-consuming and may be
Manuscript received June 29, 2012; revised December 13, 2012; accepted
December 20, 2012. Date of publication December 28, 2012; date of current
version March 26, 2013. This work was supported in part by the National
Natural Science Foundation of China under Grant 61201099 and Grant
61071119, the Program for Ningbo Municipal Technology Innovation Team
under Grant 2011B81002, and the K. C. Wong Magna Fund in Ningbo
University. The associate editor coordinating the review of this paper and
approving it for publication was Dr. Ashish Pandharipande.
The authors are with the College of Information Science and Engineering,
Ningbo University, Ningbo 315211, China (e-mail: wanggang@nbu.edu.cn;
liyouming@nbu.edu.cn; wangrangding@nbu.edu.cn).
Color versions of one or more of the figures in this paper are available
online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/JSEN.2012.2237026
trapped into local minima. The local convergence problem
may also occur in the normalized incremental subgradient
(NIS) algorithm presented in [13]. In [14], a projection-onto-
convex-sets (POCS) method with distributed implementation
was proposed, which converges to the global optimum. This
method is very computationally efficient, however, it suffers
from the convex hull problem. Therefore, the POCS method
is not suitable for localization in ad hoc networks in which
the sensor geometry is not fixed. More recently, two different
two-stage closed-form weighted least squares (WLS) meth-
ods [15], [16] were proposed. These methods have a low
computational complexity and superior performance over the
QE method. However, since the second-order noise terms are
neglected in these methods, the performance of the two-stage
WLS methods will quickly get worse when the noise becomes
large. In [17] and [18], we proposed a semidefinite relaxation
(SDR) method, which shows superior performance over the
existing methods at high noise levels.
In this paper, we propose a new SDR method that is different
from the one in [18]. The contributions of this paper include
the following.
1) We theoretically show the tightness of the proposed SDR
formulation.
2) We show that the proposed SDR method has better
performance than the existing methods, including the
SDR method in [18].
3) We propose an alternating estimation procedure to
jointly estimate the source location and the decay factor
when the decay factor is unknown.
According to the transformed model, we transform the
original measurement model and obtain an approximate WLS
(AWLS) formulation, which is different from that in [18]. To
facilitate SDR, we simplify the problem by further approxi-
mating the weights. After that, we perform SDR to obtain a
semidefinite programming (SDP). Similar to [18], we derive
two different formulations of SDP, which can provide the same
estimate of the source location. For the cases that the SDR is
not tight, the standard Gaussian randomization procedure is
applied to further improve the estimation accuracy.
In practice, the decay factor is usually estimated in the
system calibration process, in which large amount of training
data is required. This would lead to high computational cost
and heavy communication overhead. Furthermore, the problem
is even more serious if the environment is time-varying. Hence,
joint estimation of the source location and the decay factor is
of great importance. In this paper, for the first time, we study
the localization problem when the decay factor is unknown.
We propose an alternating estimation procedure to jointly
1530-437X/$31.00 © 2012 IEEE