TDOA-Based Source Collaborative Localization via Semidefinite Relaxation in Sensor Networks

Abstract

The time delay of arrival- (TDOA-) based source localization using a wireless sensor network has been considered in this paper. The maximum likelihood estimate (MLE) is formulated by taking the correlated TDOA noise into account, which is caused by the difference with the TOA of the reference sensor. The global optimal solution is difficult to obtain due to the nonconvex nature of the ML function. We propose an alternative semidefinite programming method, which transforms the original ML problem into a convex one by relaxing nonconvex equalities into convex matrix inequalities. In addition, the source localization algorithm in the presence of sensor location errors and non-line-of-sight (NLOS) observations is developed. Our simulation results demonstrate the potential advantages of the proposed method. Furthermore, the proposed source localization algorithm by taking the NLOS TOA measurements as the constraints of the convex problem can provide a good estimate.

1. Introduction

Source localization using a number of distributed sensors has been extensively studied in the past few years for a wide range of applications such as radar, sonar, and microphone array [1–3]. Recently, tremendous growth in advances of wireless sensor networks (WSNs) has promoted both algorithmic research and application of the source localization in sensor networks [4–6]. Usually, the positions of the sensor nodes are assumed to be known and the spatial location of the source is the parameter to be estimated. Measurements are extracted from the received signals at local sensors and then transmitted to a fusion center where the source position estimation is carried out by fusing the received measurements.

To localize the source, different measurement models are defined based on the information such as time of arrival (TOA) [7–10], time difference of arrival (TDOA) [11–19], angle of arrival (AOA) [20], received signal strength (RSS) [21–23], distance measurement (DM) [16, 24, 25], and a combination of them [26, 27]. Distance measurement is widely employed in the scenario of cooperative localization for sensor networks, for example, sensor node self-localization [4, 28]. However, such a measurement is not applicable in the noncooperative source localization scenario as the distance measurement is difficult to be estimated directly. RSS measurements can be sampled at a much lower rate as the power emitted by a source varies slowly, and the information is easy to obtain by averaging the signal power received at a sensor. However, the RSS measurement is dependent on the signal decay model assumption and is sensitive to the channel environment such as scatter, multipath effect. For AOA measurements, each sensor requires to be equipped with an angle estimation device, for example, multisensor array, acoustic vector sensor in underwater sensor networks. However, the deployment of networked arrays is very expensive and calibration of each array is a problem of its own. Such difficulties make the deployment of large-scaled network very challenging and impractical. In practice, the TOA and TDOA measurements are mostly widely used due to their accuracy and ease to access. In this paper, we will focus on the localization schemes based on TOA/TDOA measurement models.

For TOA-based measurement, it is often assumed that the source and sensors are synchronized perfectly such that the signal propagation time can be exactly known at sensor nodes. However, the TDOA measurements are not available for noncooperative sources, for example, enemy target in a battlefield. One way to tackle this problem is to jointly estimate the initial signal transmission time and the source location by using available TOA measurements and known sensors coordinates [8, 9]. Another alternative method is to utilize the difference of pairwise TOA measurements, that is, TDOA, where the initial transmission time is not required. Although the TDOA measurements are more sensitive to the noise and it is observed that there is a 3 dB performance loss compared with TOA model [8], TDOA measurement has been widely employed in source localization due to its simplicity and robustness.

TDOA-based source localization can be carried out by intersecting the hyperbolic curves corresponding to the different TDOA measurements. Usually, to obtain the source location is difficult due to the highly nonlinear relationship between the unknown parameter and derived measurements. One method to handle this nonlinearity is to use the iterative searching, for example, Gauss-Newton method, to obtain a maximum likelihood (ML) estimate. However, the iteration suffers from the convergence problem: the search can be ended up with a local optimum or a saddle point. In [14], a closed-form solution based on the weighted least-square (LS) was proposed to approximate the MLE by the parameter transformation. However, the estimation bias is large, when the noise-free TOA assumption is violated by heavy measurement noise. Another alternative method based on LS formulation was proposed in [15] to derive a closed-form solution to the ML equation, which changed nonlinear ML equations into linear equations. Also, a special geometry with three sensors on a line was considered. The explicit constrained LS solution for source localization was derived based on both the range and range-difference measurements in [16]. Such LS-based source localization can achieve good estimate when the noise of the range measurement is independent and identically distributed. However, the performance suffers from degradation when the covariance matrix of the range measurement noise is not proportional to the identity matrix (i.e., the range measurement noise is correlated). Note that this source localization algorithm is based on the minimization of LS error. It estimates the source location without requiring the knowledge about the probability distribution of TDOA or range-difference noises. Similarly, this minimization of LS error criterion has been developed in [17, 18]. In [17], two methods called BianSub and BiasRes were proposed to reduce the estimate bias caused by the noise correlation. In [18], the LS optimization problem was transformed into a convex one that can be solved by Lagrange multiplier method.

The original attempt of this paper is to derive the solution (source location estimate) to the ML formulation, which can asymptotically achieve the optimum performance and is usually set as a benchmark for estimation performance [29]. An efficient way to derive the MLE is to utilize convex optimization or semidefinite programming (SDP). The convex optimization algorithm has been widely used in source localizations for RSS model [26], DM model [30], and TOA or TDOA model [8, 11, 19]. The authors of [19] transformed the ML problem into a convex one that is easy to be solved by interior point methods. It is worth mentioning that in [19] all pairwise TDOA measurements are taken into account. Such procedure will lead to higher computational complexity since the number of pairwise TDOA measurements is $\mathcal{O}(N^{\mathrm{2}})$ (N is the number of sensors). For a resource-limited sensor network, higher computational complexity is costly. In order to overcome this shortcoming, the authors in [11] proposed a reduced complexity SDP-based source localization algorithm. The computational complexity is reduced from two respects: $(1)$ a sensor is chosen as the reference one such that only selective differences of TOA are included; $(2)$ the minimax approximation is employed to further reduce the computational complexity. Specifically, SDP inner product and SDP outer product are formulated based on the ${\mathcal{l}}_{\infty }$ norm approximation of the original ${\mathcal{l}}_{\mathrm{2}}$ norm, which is less sensitive to the distribution of the TOA measurement noise. Such an approximation will lead to performance degradation.

Note that these TOA- and TDOA-based source localization algorithms considered only line-of-sight (LOS) connections between the source and sensors. However, in indoor environments or urban areas, there are non-line-of-sight (NLOS) observations resulting from the obstacles (e.g., buildings) in the direct paths of the signal transmission. NLOS connections severely degrade the source localization accuracy, since the obtained TOA measurement is positively biased due to the longer NLOS traveling distance than the true LOS distance [31, 32].

Different approaches have been developed to mitigate the degradation due to NLOS signals. The first approach is the propagation model-based approach, which is based on the distribution of TOA generated from multipath scattering models [33–35]. This approach estimates the LOS TOA from several multipath arrivals (including NLOS arrivals) by matching the statistics of the TOAs with those produced by the scattering models and derives the location estimate according to the LOS TOA measurements. However, the accurate model is difficult to be obtained and the ideal scattering models always mismatch the probability density function (PDF) of the observed measurements due to the time-varying characteristic of the scattering models. The second approach to mitigate the degradation due to NLOS measurements is the “identify and discard” based approach [36, 37]. The source localization procedure is composed of two steps. In the first step, LOS and NLOS measurements are identified by the statistical decision theory [36, 38, 39]. Then these biased NLOS measurements are discarded. The remaining LOS measurements are employed to locate the source position via an MLE or a maximum a posteriori probability estimator [36]. The discarding of the NLOS information leads to performance degradation which can be avoided by the third method, that is, “identify and employ” based approach. Such an approach formulates the source localization problem as an optimization problem by taking the NLOS measurements as a constraint, for example, linear programming [31, 40] and SDP [41, 42], or by jointly considering LOS and NLOS measurements, for example, assigning different weights to LOS and NLOS measurements [43]. The fourth method is the source localization without distinguishing LOS and NLOS in mixed LOS/NLOS environments, where the key point is to design a robust source position estimator via jointly estimating mixture distribution and source position, for example, expectation-maximization (EM) and joint maximum a posteriori-maximum likelihood (JMAP-ML) in [44], adaptive kernel density estimation in [45], and machine learning in [46]. There also exists literature dedicated to the source localization under only NLOS measurements [47–49]. An overview of NLOS identification and error mitigation can be found in [50, 51] and references therein.

In this paper, we develop a new algorithm via semidefinite programming based on the TDOA model. The TDOA measurement errors are assumed to be correlated with each other due to the TOA substraction with that of the reference sensor. The ML formulation based on TDOA model is considered. We develop an efficient convex relaxation for the nonconvex ML formulation. The corresponding source localization algorithm in the presence of sensor location errors is also proposed to examine the sensitivity of the inaccurate sensor location estimation, which deteriorates the accuracy of source localization algorithms [52, 53]. In terms of the LOS/NLOS environments, the “identify and employ” based source localization is considered to handle NLOS biases in this paper. We assume that the NLOS measurement has been identified for ultrawide band (UWB) signals via hypothesis test [54–56]. The main contributions of this work are summarized as follows:

• (i)

An alternative SDP source localization algorithm based on TDOA model with correlated TDOA noises is proposed. The proposed SDP source localization algorithm provides a tradeoff between the localization accuracy and computational complexity compared with the algorithm proposed in [11] and the algorithm in [19].

(ii)

The robust source location estimation in the presence of sensor location errors is developed for the proposed SDP algorithm, where the location estimate is robust against the sensor location errors.

(iii)

The proposed source localization algorithm is extended to the case that there are NLOS connections between the source and sensors for TOA measurements by taking the NLOS TOA measurements as the constraints of the optimization problem. The simulation results show that such source localization scheme can improve the performance compared with the source localization algorithm with only the LOS TOA measurements.

(iv)

The performance of the proposed SDP with sensor location errors and without errors is examined by Monte Carlo simulations to show the effectiveness of the proposed algorithm in comparison to the existing methods.

In addition, the performance of source localization is compared with existing source localization algorithms including ML and SDP algorithm [19] and SDP algorithm with minimax approximation [11]. Also, the Cramér-Rao lower bound (CRLB) is included in the simulations.

We organize the remainder of this paper as follows. Section 2 describes TDOA model with correlated noise and formulates ML problem. Section 3 presents the proposed SDP source localization algorithm by semidefinite relaxation. In Section 4, source localization in the presence of sensor location errors is formulated. The NLOS case is considered in Section 5. The simulations results are given in Section 6. Section 7 concludes the paper.

Throughout this paper, we shall use the following mathematical notations: $(·{)}^T$ denotes the transpose of a matrix or a vector; $\mathrm{Tr}(·)$ denote the trace of a square matrix; $‖·‖$ denotes the Euclidean norm of a vector; $\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{g}(·)$ denotes the diagonal matrix with the given vector on the main diagonal; ${\mathbf{0}}_{m\times n}$ denotes the zero matrix with m rows and n columns; ${\mathbf{1}}_m$ denotes the $m\times \mathrm{1}$ column vector with all entries being 1s; ${\mathbf{I}}_m$ denotes the $m\times m$ identity matrix; $\mathbf{A}⪰\mathbf{B}$ means $\mathbf{A}-\mathbf{B}$ is positive semidefinite.

2. Problem Statement

Consider a sensor network with N sensor nodes arbitrarily deployed at m-dimensional surveillance region (with $m=\mathrm{2}$ or $\mathrm{3}$ ). The sensor positions ${\mathbf{x}}_i\in {\mathbb{R}}^m$ , for $i=\mathrm{1},\dots ,N$ , are assumed to be known and fixed. The TOA measurements are extracted by a matched filter at each sensor node and transmitted to a data fusion center (DFC) where the source location $\mathbf{y}\in {\mathbb{R}}^m$ is estimated. Figure 1 depicts such a source cooperative localization system. Here, we assume that all sensor nodes' clocks are ideally synchronized but are unsynchronized with the source's clock. The TOA measurement $t_i$ from the common source at the ith sensor is

$$\begin{array}{cc}& t_i=\frac{\mathrm{1}}{c}‖{\mathbf{x}}_i-\mathbf{y}‖+t_{\mathrm{0}}+{\omega }_i,\hspace{1em}i=\mathrm{1,2},\dots ,N,\end{array}$$

(1)

where $t_{\mathrm{0}}$ is the unknown time instant at which the signal is transmitted and c is the speed of signal transmission. ${\omega }_i$ is the independent and identically distributed Gaussian noise with zero-mean and variance ${\eta }^{\mathrm{2}}={\sigma }^{\mathrm{2}}/c^{\mathrm{2}}$ . ${\sigma }^{\mathrm{2}}$ is the variance of the distance measurement. The joint conditional probability density function of the TOA measurement $\mathbf{t}=[t_{\mathrm{1}},t_{\mathrm{2}},\dots ,t_N{]}^T$ is

$$\begin{array}{cc}& f\left(\mathbf{t}\hspace{0.17em}|\hspace{0.17em}\mathbf{y},t_{\mathrm{0}},{\eta }^{\mathrm{2}}\right)={\left(\mathrm{2}\pi {\eta }^{\mathrm{2}}\right)}^{-N/\mathrm{2}}\mathrm{e}\mathrm{x}\mathrm{p}\left(-\frac{\mathrm{1}}{\mathrm{2}{\eta }^{\mathrm{2}}}{\displaystyle \sum }_{i=\mathrm{1}}^N{\left(t_i-\frac{\mathrm{1}}{c}‖{\mathbf{x}}_i-\mathbf{y}‖-t_{\mathrm{0}}\right)}^{\mathrm{2}}\right).\end{array}$$

(2)

Consequently, the MLE of y for TOA measurement can be obtained as

$$\begin{array}{cc}& \widehat{\mathbf{y}}=\underset{\mathbf{y},t_{\mathrm{0}}}{\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}}{\displaystyle \sum }_{i=\mathrm{1}}^N{\left(t_i-\frac{\mathrm{1}}{c}‖{\mathbf{x}}_i-\mathbf{y}‖-t_{\mathrm{0}}\right)}^{\mathrm{2}}.\end{array}$$

(3)

Generally, the variance ${\eta }^{\mathrm{2}}$ is assumed to be known. ML formulation (3) is nonconvex and the estimate is easily converged to a local minimum with iterative algorithms.

Figure 1

A block diagram of the source localization in sensor networks.

In order to eliminate the unknown parameter $t_{\mathrm{0}}$ that is not related to the source position, reference sensor r is selected. The TDOA between the ith sensor and the reference sensor can be addressed as

$$\begin{array}{cc}& \Delta t_i=\frac{\mathrm{1}}{c}\left(‖{\mathbf{x}}_i-\mathbf{y}‖-‖{\mathbf{x}}_r-\mathbf{y}‖\right)+\underset{n_i}{\underbrace{{\omega }_i-{\omega }_r}},\end{array}$$

(4)

where $i=\mathrm{1,2},\dots ,r-\mathrm{1},r+\mathrm{1},\dots ,N$ . Note that the noises $n_i={\omega }_i-{\omega }_r$ are correlated with each other due to the common term ${\omega }_r$ . The covariance matrix of the noise vector $\mathbf{n}={\left[n_{\mathrm{1}},n_{\mathrm{2}},\dots ,n_{r-\mathrm{1}},n_{r+\mathrm{1}},\dots ,n_N\right]}^T$ is

$$\begin{array}{cc}& Q={\eta }^{\mathrm{2}}\left[\begin{array}{cccc}\mathrm{2}& \mathrm{1}& \cdots & \mathrm{1}\\ \mathrm{1}& \mathrm{2}& \cdots & \mathrm{1}\\ ⋮& \ddots & ⋮& \\ \mathrm{1}& \mathrm{1}& \cdots & \mathrm{2}\end{array}\right].\end{array}$$

(5)

By introducing auxiliary variables

$$\begin{array}{cc}& {\tau }_i=\frac{\mathrm{1}}{c}‖{\mathbf{x}}_i-\mathbf{y}‖,\hspace{1em}\mathrm{1}\le i\le N,\\ \mathbf{h}={\left[{\tau }_{\mathrm{1}},{\tau }_{\mathrm{2}},\dots ,{\tau }_r,\dots ,{\tau }_N\right]}^T,\\ \Delta \mathbf{t}={\left[\Delta t_{\mathrm{1}},\Delta t_{\mathrm{2}},\dots ,\Delta t_{r-\mathrm{1}},\Delta t_{r+\mathrm{1}},\dots ,\Delta t_N\right]}^T,\end{array}$$

(6)

(4) can be written in a matrix form by

$$\begin{array}{cc}& \Delta \mathbf{t}=U\mathbf{h}+\mathbf{n}\mathbf{,}\end{array}$$

(7)

where

$$\begin{array}{cc}& U=\left[\begin{array}{ccc}{\mathbf{I}}_{r-\mathrm{1}}& -{\mathbf{1}}_{r-\mathrm{1}}& {\mathbf{0}}_{\left(r-\mathrm{1}\right)\times \left(N-r\right)}\\ {\mathbf{0}}_{\left(N-r\right)\times \left(r-\mathrm{1}\right)}& -{\mathbf{1}}_{N-r}& {\mathbf{I}}_{N-r}\end{array}\right].\end{array}$$

(8)

Note that (7) is a linear function of the auxiliary variable h. The joint conditional probability density function of the TDOA measurements is

$$\begin{array}{cc}& f\left(\Delta \mathbf{t}\hspace{0.17em}|\hspace{0.17em}\mathbf{y},{\eta }^{\mathrm{2}}\right)=\frac{\mathrm{1}}{{\left(\mathrm{2}\pi \right)}^{\left(N-\mathrm{1}\right)/\mathrm{2}}{\left|Q\right|}^{\mathrm{1}/\mathrm{2}}}\mathrm{e}\mathrm{x}\mathrm{p}\left(-\frac{\mathrm{1}}{\mathrm{2}}{\left(\Delta \mathbf{t}-U\mathbf{h}\right)}^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\mathbf{h}\right)\right).\end{array}$$

(9)

Then, the MLE of y can be written as

$$\begin{array}{cc}& \widehat{\mathbf{y}}=\underset{\mathbf{y},\mathbf{h}}{\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}}\left\{{\left(\Delta \mathbf{t}-U\mathbf{h}\right)}^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\mathbf{h}\right)\right\},\end{array}$$

(10)

where Q and U are given as (5) and (8), respectively.

3. Semidefinite Relaxation Based on TDOA

For ML formulation (10), the objective function is a nonconvex function of the unknown y. In [19], a semidefinite relaxation method was used to convert the ML estimation problem into a convex problem, where all pairwise TDOA measurements are considered. Such a procedure leads to higher computational complexity, since the number of TDOA measurements is $N(N-\mathrm{1})/\mathrm{2}$ . Besides, a solution was provided by assuming independent noise among the TDOA measurements [19]. The authors in [11] derived the source location estimate based on correlated noise by using $l_{\infty }$ approximation. Such an approximation leads to reduced computational complexity. However, its performance is worse than the original TDOA ML estimate. Here, we propose an alternative SDP source localization scheme according to the TDOA measurements with correlated noises, which provides a tradeoff between the localization accuracy and computational complexity.

3.1. SDP Source Localization Algorithm

In our work, the ith TDOA measurement is obtained by taking the difference of the TOA between the ith sensor and the reference one. Taking into account correlated noises of the TDOA measurement, the MLE problem is transformed into a convex one by relaxing the nonconvex equalities.

The objective function of the ML formulation in (10) can be rewritten as

$$\begin{array}{cc}& {\left(\Delta \mathbf{t}-U\mathbf{h}\right)}^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\mathbf{h}\right)=\mathrm{T}\mathrm{r}\left\{Q^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\mathbf{h}\right){\left(\Delta \mathbf{t}-U\mathbf{h}\right)}^T\right\}.\end{array}$$

(11)

In order to write this objective function as a linear function of the unknown parameters, the auxiliary variable $\mathbf{H}=\mathbf{h}{\mathbf{h}}^T$ is introduced. Equation (11) can be further written as

$$\begin{array}{cc}& \mathrm{Tr}\left\{Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\mathbf{h}\Delta {\mathbf{t}}^T+U\mathbf{H}{U}^T\right)\right\}.\end{array}$$

(12)

Clearly, this objective function is a linear function of both H and h. By using (12), ML formulation (10) can be written as the following optimization problem:

$$\begin{array}{cc}& \underset{\mathbf{H},\mathbf{h},\mathbf{Y},\mathbf{y}}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mathrm{T}\mathrm{r}\left\{Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\mathbf{h}\Delta {\mathbf{t}}^T+U\mathbf{H}{U}^T\right)\right\}\\ \mathrm{s}.\mathrm{t}.\hspace{1em}{\tau }_i=\frac{\mathrm{1}}{c}‖{\mathbf{x}}_i-\mathbf{y}‖,\hspace{1em}i=\mathrm{1,2},\dots ,N,\\ \hspace{1em}\mathbf{h}={\left[{\tau }_{\mathrm{1}},{\tau }_{\mathrm{2}},\dots ,{\tau }_N\right]}^T,\hspace{0.17em}\hspace{0.17em}\mathbf{H}=\mathbf{h}{\mathbf{h}}^T.\end{array}$$

(13)

Notice that the optimization problem described in (13) is still nonconvex as the constraints ${\tau }_i=(\mathrm{1}/c)‖{\mathbf{x}}_i-\mathbf{y}‖$ and $\mathbf{H}=\mathbf{h}{\mathbf{h}}^T$ are nonconvex. Hence, it is still difficult to obtain the solution. Next, our work is to relax the nonconvex constraints into convex constraints. By using the matrix notation H, the constraint ${\tau }_i=(\mathrm{1}/c)‖{\mathbf{x}}_i-\mathbf{y}‖$ can be written as

$$\begin{array}{cc}& {\mathbf{H}}_{ii}={\tau }_i^{\mathrm{2}}=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left({\mathbf{y}}^T\mathbf{y}-\mathrm{2}{\mathbf{x}}_i^T\mathbf{y}+{\mathbf{x}}_i{\mathbf{x}}_i^T\right)=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left(\mathrm{T}\mathrm{r}\left(\mathbf{Y}\right)-\mathrm{2}{\mathbf{x}}_i^T\mathbf{y}+{\mathbf{x}}_i{\mathbf{x}}_i^T\right),\\ \hspace{1em}\mathbf{Y}=\mathbf{y}{\mathbf{y}}^T,\hspace{0.17em}\hspace{0.17em}\mathbf{H}=\mathbf{h}{\mathbf{h}}^T.\end{array}$$

(14)

Note that these constraints ( $\mathbf{Y}=\mathbf{y}{\mathbf{y}}^T$ and $\mathbf{H}=\mathbf{h}{\mathbf{h}}^T$ ) are still nonconvex; the solution remains difficult. The semidefinite relaxation is employed such that these two equalities can be relaxed into convex inequalities, $\mathbf{Y}⪰\mathbf{y}{\mathbf{y}}^T$ and $\mathbf{H}⪰\mathbf{h}{\mathbf{h}}^T$ . Further, these inequalities can be written as linear matrix inequalities:

$$\begin{array}{cc}& \left[\begin{array}{cc}\mathbf{Y}& \mathbf{y}\\ {\mathbf{y}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\\ \left[\begin{array}{cc}\mathbf{H}& \mathbf{h}\\ {\mathbf{h}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0}.\end{array}$$

(15)

Combining all the constraints, we now have transformed the ML problem into a convex optimization problem:

$$\begin{array}{cc}& \underset{\mathbf{H},\mathbf{h},\mathbf{y}}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mathrm{T}\mathrm{r}\left\{Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\mathbf{h}\Delta {\mathbf{t}}^T+U\mathbf{H}{U}^T\right)\right\}\\ \mathrm{s}.\mathrm{t}.\hspace{1em}{\mathbf{H}}_{ii}=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left(\mathrm{T}\mathrm{r}\left(\mathbf{Y}\right)-\mathrm{2}{\mathbf{x}}_i^T\mathbf{y}+{‖{\mathbf{x}}_i‖}^{\mathrm{2}}\right),\\ \hspace{1em}i=\mathrm{1,2},\dots ,N,\\ \hspace{1em}\left[\begin{array}{cc}\mathbf{Y}& \mathbf{y}\\ {\mathbf{y}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\hspace{0.17em}\hspace{0.17em}\left[\begin{array}{cc}\mathbf{H}& \mathbf{h}\\ {\mathbf{h}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0}.\end{array}$$

(16)

The global optimal solution to the unknown source position y can be derived by interior point methods such as SeDumi [57].

Note that convex optimization formulation (16) is still prone to ambiguous solution, as the value $\Delta r_i-c{\tau }_i+c{\tau }_r$ for $i=\mathrm{1},\dots ,r-\mathrm{1},r+\mathrm{1},\dots ,N$ , which is the main component of objective function (16) in the form of matrix expansion, will not change when the source is located at hyperbolic curve with sensor i and reference sensor r as its focus points (see Figure 2). Thus, to avoid such an ambiguity, a penalty term is added into the objective function. Such a technique has been employed in previous work [8]. For the proposed TDOA-based SDP algorithm, extra penalty $\beta {\sum }_{i=\mathrm{1}}^N‍{\sum }_{j=\mathrm{1}}^N‍{\mathbf{H}}_{ij}$ is added, and optimization problem (16) is transformed into

$$\begin{array}{cc}& \underset{\mathbf{H},\mathbf{h},\mathbf{y}}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mathrm{T}\mathrm{r}\left\{Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\mathbf{h}\Delta {\mathbf{t}}^T+U\mathbf{H}{U}^T\right)\right\}+\beta {\displaystyle \sum }_{i=\mathrm{1}}^N\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^N{\mathbf{H}}_{ij}\\ \mathrm{s}.\mathrm{t}.\hspace{1em}{\mathbf{H}}_{ii}=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left(\mathrm{T}\mathrm{r}\left(\mathbf{Y}\right)-\mathrm{2}{\mathbf{x}}_i^T\mathbf{y}+{‖{\mathbf{x}}_i‖}^{\mathrm{2}}\right),\\ \hspace{1em}i,j=\mathrm{1,2},\dots ,N,\\ \hspace{1em}\left[\begin{array}{cc}\mathbf{Y}& \mathbf{y}\\ {\mathbf{y}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\hspace{0.17em}\hspace{0.17em}\left[\begin{array}{cc}\mathbf{H}& \mathbf{h}\\ {\mathbf{h}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\end{array}$$

(17)

where $\beta \ge \mathrm{0}$ is a constant for penalization. As will be shown in Section 6, for larger $\mathrm{1}/{\sigma }^{\mathrm{2}}$ , this transformation can lead to better performance than the case with $\beta =\mathrm{0}$ . Problem (17) can also be solved by interior point methods, and the source position estimate $\widehat{\mathbf{y}}$ is derived.

Figure 2

The description of the ambiguity of convex formulation (16).

3.2. The Expansion of the SDP Source Localization Algorithm

In the above work, we derive the TDOA measurements by subtracting the TOA of the reference sensor. As such, $N-\mathrm{1}$ TDOA measurements are utilized for source localization. Here, we extend our proposed SDP source localization to the scenario, where all pairwise TDOA measurements are included. However, there is a difference between the proposed SDP algorithm and the one proposed in [19], where the TDOA noises are assumed to be independent of each other.

The TDOA between the ith sensor and the jth sensor can be written as

$$\begin{array}{cc}& \Delta t_{ij}=\frac{\mathrm{1}}{c}\left(‖{\mathbf{x}}_i-\mathbf{y}‖-‖{\mathbf{x}}_j-\mathbf{y}‖\right)+\underset{{\delta }_{ij}}{\underbrace{{\omega }_i-{\omega }_j}},\end{array}$$

(18)

where ${\delta }_{ij}={\omega }_i-{\omega }_j$ denotes the correlated noise and $i,j=\mathrm{1},\dots ,N$ , $i<j$ . It can be written as a matrix form:

$$\begin{array}{cc}& \Delta {\mathbf{t}}^{\prime }=U^{\prime }\mathbf{h}+\mathit{\delta },\end{array}$$

(19)

where

$$\begin{array}{cc}& {\tau }_i=\frac{\mathrm{1}}{c}‖{\mathbf{x}}_i-\mathbf{y}‖,\hspace{1em}\mathrm{1}\le i\le N,\\ \mathbf{h}={\left[{\tau }_{\mathrm{1}},{\tau }_{\mathrm{2}},\dots ,{\tau }_r,\dots ,{\tau }_N\right]}^T,\\ \Delta {\mathbf{t}}^{\prime }={\left[\Delta t_{\mathrm{12}},\dots ,\Delta t_{\mathrm{1}N},\Delta t_{\mathrm{23}},\dots ,\Delta t_{\mathrm{2}N},\dots ,\Delta t_{N-\mathrm{1},N}\right]}^T,\\ \mathit{\delta }={\left[{\delta }_{\mathrm{12}},\dots ,{\delta }_{\mathrm{1}N},{\delta }_{\mathrm{23}},\dots ,{\delta }_{\mathrm{2}N},\dots ,{\delta }_{N-\mathrm{1},N}\right]}^T,\\ U^{\prime }=\left[\begin{array}{cccccc}\mathrm{1}& -\mathrm{1}& \mathrm{0}& \cdots & \mathrm{0}& \mathrm{0}\\ \mathrm{1}& \mathrm{0}& -\mathrm{1}& \cdots & \mathrm{0}& \mathrm{0}\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ \mathrm{1}& \mathrm{0}& \mathrm{0}& \cdots & \mathrm{0}& -\mathrm{1}\\ \mathrm{0}& \mathrm{1}& -\mathrm{1}& \cdots & \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \ddots & \mathrm{0}& -\mathrm{1}\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \cdots & \mathrm{1}& -\mathrm{1}\end{array}\right].\end{array}$$

(20)

The covariance matrix $Q^{\prime }$ of the noise vector δ can be given as

$$\begin{array}{cc}& {\left[Q^{\prime }\right]}_{uv}=\left\{\begin{array}{cc}\mathrm{2}{\eta }^{\mathrm{2}}\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{u}_{\mathrm{1}}=v_{\mathrm{1}},\hspace{0.17em}\hspace{0.17em}{u}_{\mathrm{2}}=v_{\mathrm{2}},\hfill \\ {\eta }^{\mathrm{2}}\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{u}_{\mathrm{1}}=v_{\mathrm{1}},\hspace{0.17em}\hspace{0.17em}{u}_{\mathrm{2}}\ne v_{\mathrm{2}},\hfill \\ -{\eta }^{\mathrm{2}}\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{u}_{\mathrm{1}}=v_{\mathrm{2}},\hspace{0.17em}\hspace{0.17em}{u}_{\mathrm{2}}\ne v_{\mathrm{1}},\hfill \\ -{\eta }^{\mathrm{2}}\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{u}_{\mathrm{2}}=v_{\mathrm{1}},\hspace{0.17em}\hspace{0.17em}{u}_{\mathrm{1}}\ne v_{\mathrm{2}},\hfill \\ {\eta }^{\mathrm{2}}\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{u}_{\mathrm{2}}=v_{\mathrm{2}},\hspace{0.17em}\hspace{0.17em}{u}_{\mathrm{1}}\ne v_{\mathrm{1}},\hfill \\ \mathrm{0}\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},\hfill \end{array}\right.\end{array}$$

(21)

where $u_{\mathrm{1}}\hspace{0.17em}\hspace{0.17em}(v_{\mathrm{1}})$ is the index of i for $i=\mathrm{1},\dots ,N$ and $u_{\mathrm{2}}\hspace{0.17em}\hspace{0.17em}(v_{\mathrm{2}})$ is the index of j for $j=\mathrm{1},\dots ,N\hspace{0.17em}\hspace{0.17em}(i<j)$ .

We can see that the formulation (in (7)), where all the pairwise TDOA measurements are included, is similar to the formulation (in (19)). The similar convex optimization problem to (17) can be derived. Thus, the solution to the expansion algorithm by taking all the pairwise TDOA measurements is derived by solving the convex optimization problem via interior methods.

4. Robust Source Localization with Sensor Location Errors

In previous sections, we assume that sensor locations are known precisely; that is, ${\mathbf{x}}_i$ is accurately known. However, since sensors are arbitrarily deployed in a surveillance region, it is difficult to obtain the accurate locations of all sensors in practice, particularly in the scenario where sensor self-localization is needed but the GPS signal is not available, for example, underwater acoustic sensor networks. In this section, we give a source localization method that is robust against the sensor location errors.

For sensor location uncertainty, we define ${\tilde{\mathbf{x}}}_i={\mathbf{x}}_i+{\mathbf{\xi }}_i$ as the estimated sensor location. ${\mathbf{x}}_i$ is the true sensor location whereas ${\mathbf{\xi }}_i\in {\mathbb{R}}^m$ is the location error with the constraint $‖{\mathbf{\xi }}_i‖\le ϵ$ . By using the first-order Taylor expansion of $‖{\mathbf{x}}_i-\mathbf{y}‖$ , TOA measurement $t_i$ in the presence of sensor location errors can be represented as

$$\begin{array}{cc}& t_i=\frac{\mathrm{1}}{c}‖{\tilde{\mathbf{x}}}_i-\mathbf{y}‖-\frac{{\mathbf{\xi }}_i^T\left({\tilde{\mathbf{x}}}_{\mathrm{i}}-\mathbf{y}\right)}{c‖{\tilde{\mathbf{x}}}_i-\mathbf{y}‖}+t_{\mathrm{0}}+{\omega }_i+o\left(‖{\mathbf{\xi }}_i‖\right).\end{array}$$

(22)

Define

$$\begin{array}{cc}& {\delta }_i=\frac{{\mathbf{\xi }}_i^T\left({\tilde{\mathbf{x}}}_i-\mathbf{y}\right)}{c‖{\tilde{\mathbf{x}}}_i-\mathbf{y}‖},\\ \mathit{\delta }={\left[{\delta }_{\mathrm{1}},{\delta }_{\mathrm{2}},\dots ,{\delta }_N\right]}^T.\end{array}$$

(23)

We have the following constraint:

$$\begin{array}{cc}& {{\delta }_i}^{\mathrm{2}}=\frac{{\mathbf{\xi }}_i^T\left({\tilde{\mathbf{x}}}_i-\mathbf{y}\right){\mathbf{\xi }}_i^T\left({\tilde{\mathbf{x}}}_i-\mathbf{y}\right)}{c^{\mathrm{2}}{‖{\tilde{\mathbf{x}}}_i-\mathbf{y}‖}^{\mathrm{2}}}\le \frac{{\mathbf{\xi }}_i^T{\mathbf{\xi }}_i{\left({\tilde{\mathbf{x}}}_i-\mathbf{y}\right)}^T\left({\tilde{\mathbf{x}}}_i-\mathbf{y}\right)}{c^{\mathrm{2}}{‖\left({\tilde{\mathbf{x}}}_i-\mathbf{y}\right)‖}^{\mathrm{2}}}=\frac{{\mathbf{\xi }}_i^T{\mathbf{\xi }}_i}{c^{\mathrm{2}}},\end{array}$$

(24)

which can be expressed as $\left|{\delta }_i\right|\le ‖{\mathbf{\xi }}_i‖/c$ . For the set δ , the constraint is $‖\mathit{\delta }‖\le ϵ\sqrt{N}/c$ . Next, we consider the source localization with sensor location errors by minimizing the worst case of the objective function.

Under the sensor location uncertainty, the noisy TDOA measurement is

$$\begin{array}{cc}& \Delta t_i=t_i-t_r\approx \frac{\mathrm{1}}{c}\left(‖{\tilde{\mathbf{x}}}_i-\mathbf{y}‖-‖{\tilde{\mathbf{x}}}_r-\mathbf{y}‖\right)-\left({\delta }_i-{\delta }_r\right)+\underset{n_i}{\underbrace{{\omega }_i-{\omega }_r}}.\end{array}$$

(25)

It can be written as a matrix form:

$$\begin{array}{cc}& \Delta \mathbf{t}=U\left(\tilde{\mathbf{h}}+\mathit{\delta }\right)+\mathbf{n}\mathbf{,}\end{array}$$

(26)

where

$$\begin{array}{cc}& \tilde{\mathbf{h}}={\left[{\tilde{\tau }}_{\mathrm{1}},{\tilde{\tau }}_{\mathrm{2}},\dots ,{\tilde{\tau }}_N\right]}^T,\\ {\tilde{\tau }}_i=\frac{\mathrm{1}}{c}‖{\tilde{\mathbf{x}}}_i-\mathbf{y}‖,\end{array}$$

(27)

U is given as (8), and $\mathbf{n}~\mathcal{N}\left({\mathbf{0}}_{N-\mathrm{1}\times \mathrm{1}},Q\right)$ . Q is the covariance matrix of correlated noise n, which is given as (5). Thus, the source localization problem with sensor location errors can be modified as

$$\begin{array}{cc}& \underset{\mathbf{y}\text{,}\tilde{\mathbf{h}}}{\min }\underset{‖\mathit{\delta }‖\le ϵ\sqrt{N}/c}{\max }\left\{{\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}+U\mathit{\delta }\right)}^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}+U\mathit{\delta }\right)\right\}.\end{array}$$

(28)

Similar to the original SDP source localization, optimization problem (28) can be equivalently written as an epigraph form [58]:

$$\begin{array}{cc}& \underset{\mathbf{y},\tilde{\mathbf{h}},\mu }{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mu \\ \mathrm{s}.\mathrm{t}.\hspace{1em}{\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}+U\mathit{\delta }\right)}^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}+U\mathit{\delta }\right)\le \mu \\ \hspace{1em}\text{for\hspace{0.17em}\hspace{0.17em}}‖\mathit{\delta }‖\le ϵ\frac{\sqrt{N}}{c},\\ \hspace{1em}{\tilde{\tau }}_i=\frac{\mathrm{1}}{c}‖{\tilde{\mathbf{x}}}_i-\mathbf{y}‖,\hspace{1em}i=\mathrm{1,2},\dots ,N.\end{array}$$

(29)

Note that the objective function is a linear function of μ. However, the constraints are nonconvex. In order to transform the constraints into convex function of unknown parameters, we write the first constraint as

$$\begin{array}{cc}& \mathrm{Tr}\left[Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\tilde{\mathbf{h}}\Delta {\mathbf{t}}^T+U\tilde{\mathbf{h}}{\tilde{\mathbf{h}}}^T{U}^T\right)\right]+\mathrm{2}{\left(U\mathit{\delta }\right)}^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}\right)+{\left(U\mathit{\delta }\right)}^T{Q}^{-\mathrm{1}}\left(U\mathit{\delta }\right)\le \mu \end{array}$$

(30)

for $\parallel \mathit{\delta }\parallel \le ϵ\sqrt{N}/c$ . This inequality constraint is equivalent to the following implicit expression:

$$\begin{array}{cc}& ‖\mathit{\delta }‖\le ϵ\frac{\sqrt{N}}{c}⟹\mathrm{Tr}\left[Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\tilde{\mathbf{h}}\Delta {\mathbf{t}}^T+U\tilde{\mathbf{h}}{\tilde{\mathbf{h}}}^T{U}^T\right)\right]+\mathrm{2}{\left(U\mathit{\delta }\right)}^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}\right)+{\left(U\mathit{\delta }\right)}^T{Q}^{-\mathrm{1}}\left(U\mathit{\delta }\right)\le \mu ,\end{array}$$

(31)

where $A\Rightarrow B$ means that B holds under condition A. Further, we can write the above implication in matrix forms as

$$\begin{array}{cc}& {\left[\begin{array}{c}\mathit{\delta }\\ \mathrm{1}\end{array}\right]}^T\left[\begin{array}{cc}{\mathbf{I}}_N& {\mathbf{0}}_{N\times \mathrm{1}}\\ {\mathbf{0}}_{\mathrm{1}\times N}& -\frac{N{ϵ}^{\mathrm{2}}}{c^{\mathrm{2}}}\end{array}\right]\left[\begin{array}{c}\mathit{\delta }\\ \mathrm{1}\end{array}\right]\le \mathrm{0}⟹{\left[\begin{array}{c}\mathit{\delta }\\ \mathrm{1}\end{array}\right]}^T\left[\begin{array}{cc}G& F\\ F^T& \phi -\mu \end{array}\right]\left[\begin{array}{c}\mathit{\delta }\\ \mathrm{1}\end{array}\right]\le \mathrm{0},\end{array}$$

(32)

where

$$\begin{array}{cc}& G=U^T{Q}^{-\mathrm{1}}U,\\ F=U^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}\right),\\ \phi =\mathrm{Tr}\left[Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\tilde{\mathbf{h}}\Delta {\mathbf{t}}^T+U\tilde{\mathbf{H}}{U}^T\right)\right],\\ \tilde{\mathbf{H}}=\tilde{\mathbf{h}}{\tilde{\mathbf{h}}}^T.\end{array}$$

(33)

According to the S-procedure [58], formulation (32) holds if and only if there exists $\lambda \ge \mathrm{0}$ such that

$$\begin{array}{cc}& \left[\begin{array}{cc}G& F\\ F^T& \phi -\mu \end{array}\right]⪯\lambda \left[\begin{array}{cc}{\mathbf{I}}_N& {\mathbf{0}}_{N\times \mathrm{1}}\\ {\mathbf{0}}_{\mathrm{1}\times N}& -\frac{N{ϵ}^{\mathrm{2}}}{c^{\mathrm{2}}}\end{array}\right].\end{array}$$

(34)

Note that φ is a linear function of both $\tilde{\mathbf{h}}$ and $\tilde{\mathbf{H}}$ . Constraint (34) is convex. By using the equality constraint $\tilde{\mathbf{H}}=\tilde{\mathbf{h}}{\tilde{\mathbf{h}}}^T$ , the second constraint in (29) ${\tilde{\tau }}_i=(\mathrm{1}/c)‖{\mathbf{x}}_i-\mathbf{y}‖$ can be written as

$$\begin{array}{cc}& {\tilde{\mathbf{H}}}_{ii}=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left(\mathrm{T}\mathrm{r}\left(\mathbf{Y}\right)-\mathrm{2}{\tilde{\mathbf{x}}}_i^T\mathbf{y}+{‖{\tilde{\mathbf{x}}}_i‖}^{\mathrm{2}}\right),\end{array}$$

(35)

where $\mathbf{Y}=\mathbf{y}{\mathbf{y}}^T$ . Combining all the constraints, the TDOA-based source localization with sensor location errors can be written as the following optimization problem:

$$\begin{array}{cc}& \underset{\mathbf{y},\mathbf{Y},\tilde{\mathbf{h}},\tilde{\mathbf{H}},\lambda }{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mu \\ \mathrm{s}.\mathrm{t}.\hspace{1em}\left[\begin{array}{cc}G& F\\ F^T& \phi -\mu \end{array}\right]⪯\lambda \left[\begin{array}{cc}{\mathbf{I}}_N& {\mathbf{0}}_{N\times \mathrm{1}}\\ {\mathbf{0}}_{\mathrm{1}\times N}& -\frac{N{ϵ}^{\mathrm{2}}}{c^{\mathrm{2}}}\end{array}\right],\\ \hspace{1em}G=U^T{Q}^{-\mathrm{1}}U,\\ \hspace{1em}\phi =\mathrm{T}\mathrm{r}\left[Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\tilde{\mathbf{h}}\Delta {\mathbf{t}}^T+U\tilde{\mathbf{H}}{U}^T\right)\right],\\ \hspace{1em}F=U^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}\right),\\ \hspace{1em}\tilde{\mathbf{H}}=\tilde{\mathbf{h}}{\tilde{\mathbf{h}}}^T,\hspace{0.17em}\hspace{0.17em}\mathbf{Y}=\mathbf{y}{\mathbf{y}}^T,\\ \hspace{1em}{\tilde{\mathbf{H}}}_{ii}=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left(\mathrm{T}\mathrm{r}\left(\mathbf{Y}\right)-\mathrm{2}{\tilde{\mathbf{x}}}_i^T\mathbf{y}+{‖{\tilde{\mathbf{x}}}_i‖}^{\mathrm{2}}\right),\\ \hspace{1em}\lambda \ge \mathrm{0},\hspace{0.17em}\hspace{0.17em}i=\mathrm{1,2},\dots ,N.\end{array}$$

(36)

Similar to (17), the equality constraints $\tilde{\mathbf{H}}=\tilde{\mathbf{h}}{\tilde{\mathbf{h}}}^T$ and $\mathbf{Y}=\mathbf{y}{\mathbf{y}}^T$ can be relaxed into

$$\begin{array}{cc}& \left[\begin{array}{cc}\mathbf{Y}& \mathbf{y}\\ {\mathbf{y}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\\ \left[\begin{array}{cc}\tilde{\mathbf{H}}& \tilde{\mathbf{h}}\\ {\tilde{\mathbf{h}}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0}.\end{array}$$

(37)

Thus, we have the following TDOA-based source localization algorithm with the penalty term:

$$\begin{array}{cc}& \underset{\mathbf{y},\mathbf{Y},\tilde{\mathbf{h}},\tilde{\mathbf{H}},\lambda }{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mu +\beta {\displaystyle \sum }_{i=\mathrm{1}}^N{\displaystyle \sum }_{j=\mathrm{1}}^N{\tilde{\mathbf{H}}}_{ij}\\ \mathrm{s}.\mathrm{t}.\hspace{1em}\left[\begin{array}{cc}G& F\\ F^T& \phi -\mu \end{array}\right]⪯\lambda \left[\begin{array}{cc}{\mathbf{I}}_N& {\mathbf{0}}_{N\times \mathrm{1}}\\ {\mathbf{0}}_{\mathrm{1}\times N}& -\frac{N{ϵ}^{\mathrm{2}}}{c^{\mathrm{2}}}\end{array}\right],\\ \hspace{1em}\phi =\mathrm{Tr}\left[Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\tilde{\mathbf{h}}\Delta {\mathbf{t}}^T+U\tilde{\mathbf{H}}{U}^T\right)\right],\\ \hspace{1em}F=U^T{Q}^{-\mathrm{1}}\left(\Delta \mathbf{t}-U\tilde{\mathbf{h}}\right),\\ \hspace{1em}{\tilde{\mathbf{H}}}_{ii}=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left(\mathrm{T}\mathrm{r}\left(\mathbf{Y}\right)-\mathrm{2}{\tilde{\mathbf{x}}}_i^T\mathbf{y}+{‖{\tilde{\mathbf{x}}}_i‖}^{\mathrm{2}}\right),\\ \hspace{1em}\left[\begin{array}{cc}\mathbf{Y}& \mathbf{y}\\ {\mathbf{y}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\hspace{0.17em}\hspace{0.17em}\left[\begin{array}{cc}\tilde{\mathbf{H}}& \tilde{\mathbf{h}}\\ {\tilde{\mathbf{h}}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\\ \hspace{1em}\lambda \ge \mathrm{0},\hspace{0.17em}\hspace{0.17em}i,j=\mathrm{1,2},\dots ,N,\end{array}$$

(38)

where $\beta \ge \mathrm{0}$ is a constant for penalization. Using the SDP solver SeDumi [57], we can obtain the source position estimate $\widehat{\mathbf{y}}$ in the presence of sensor location errors.

5. Source Localization under LOS/NLOS Environments

In previous sections, we have developed an alternative SDP-based source localization scheme by employing TOA measurements. Also, the robust source localization against sensor location errors is given. Note that the TOA measurements derived by the match-filter at sensors are based on the LOS connections between the source and the sensors. However, in dense multipath propagation environments (e.g., indoor or urban areas), the LOS paths between the source and the sensors are obstructed. Thus, the NLOS range measurement is much larger than the LOS range one. It was observed that the NLOS bias errors of the range measurements are much larger than the range measurement errors of the LOS scenarios [32]. In this paper, we present a source localization scheme that effectively takes both LOS and NLOS TOA measurements into account. A convex optimization problem is formulated, where the LOS measurements are used to formulate the objective function whereas the NLOS measurements are used to formulated the constraint. To begin, here, we state our assumptions:

• (1)

The M NLOS TOA measurements in all the $M+N$ TOA measurements have been identified by the statistical decision theory, for example, energy detection [38], joint received signal strength and TOA-based statistical NLOS identification [39].

(2)

The NLOS bias errors of the range measurements are much larger than the range measurement errors of the LOS scenarios; that is, $b_k$ (for $k=\mathrm{1},\dots ,M$ ) is typically much larger than the TOA measurement noise ${\omega }_{Nk}$ .

We make no further assumption on the distribution of $b_k$ .

The TOA measurement with NLOS connection between the source and sensor k is

$$\begin{array}{cc}& t_{Nk}=\frac{\mathrm{1}}{c}‖{\mathbf{x}}_{Nk}-\mathbf{y}‖+t_{\mathrm{0}}+{\omega }_{Nk}+b_k,\hspace{1em}k=\mathrm{1,2},\dots ,M,\end{array}$$

(39)

where $\mathbf{y}\in {\mathbb{R}}^m$ is the source location that needs to be estimated; ${\mathbf{x}}_{Nk}\in {\mathbb{R}}^m$ (for $k=\mathrm{1},\dots ,M$ ) is the location of the kth sensor with NLOS connection between the source and itself; M is the number of NLOS TOA measurements, which can be derived by the NLOS identification method for TOA measurements; $b_k$ (for $k=\mathrm{1},\dots ,M$ ) is the NLOS bias error, which is always positive (i.e., $b_k>\mathrm{0}$ ). Similarly to the TOA measurement with the LOS connection, here, the sensor r with the LOS connection is also chosen as the reference sensor. The TDOA between the kth sensor with the NLOS connection and the reference sensor r with the LOS connection can be given as

$$\begin{array}{cc}& \Delta t_{Nk}=t_{Nk}-t_r=\frac{\mathrm{1}}{c}\left(‖{\mathbf{x}}_{Nk}-\mathbf{y}‖-‖{\mathbf{x}}_r-\mathbf{y}‖\right)+{\omega }_{Nk}-{\omega }_r+b_k.\end{array}$$

(40)

Note that if the NLOS bias error is much larger than the TOA measurement noise, for example,

$$\begin{array}{cc}& b_k\ge \mathrm{2}·\underset{i=\mathrm{1},\dots ,N,\hspace{0.17em}k=\mathrm{1},\dots ,M}{\max }\left\{\left|{\omega }_i\right|,\left|{\omega }_{Nk}\right|\right\},\end{array}$$

(41)

the term ${\omega }_{Nk}-{\omega }_r+b_k$ is positively biased. Thus, we have the following inequality constraint:

$$\begin{array}{cc}& \frac{\mathrm{1}}{c}\left(‖{\mathbf{x}}_{Nk}-\mathbf{y}‖-‖{\mathbf{x}}_r-\mathbf{y}‖\right)\le \Delta t_{Nk}.\end{array}$$

(42)

Similar to the source localization algorithm in [31], here, we make no assumption of the statistic characteristics for the NLOS bias error. And inequality constraint (42) holds under inequation (41). Such a condition is always satisfied, since the NLOS distance is much larger than the true LOS distance.

Based on assumption (1), the LOS TOA measurements are used to formulate the objective function, whereas the NLOS TOA measurements are used to formulate additional constraints of the original source localization optimization problem in (17). Thus, we have

$$\begin{array}{cc}& \underset{\mathbf{H},\mathbf{h},\mathbf{y}}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mathrm{Tr}\left\{Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\mathbf{h}\Delta {\mathbf{t}}^T+U\mathbf{H}{U}^T\right)\right\}+\beta {\displaystyle \sum }_{i=\mathrm{1}}^N\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^N{\mathbf{H}}_{ij}\\ \mathrm{s}.\mathrm{t}.\hspace{1em}{\mathbf{H}}_{ii}=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left(\mathrm{T}\mathrm{r}\left(\mathbf{Y}\right)-\mathrm{2}{\mathbf{x}}_i^T\mathbf{y}+{‖{\mathbf{x}}_i‖}^{\mathrm{2}}\right),\\ \hspace{1em}\left[\begin{array}{cc}\mathbf{Y}& \mathbf{y}\\ {\mathbf{y}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\hspace{0.17em}\hspace{0.17em}\left[\begin{array}{cc}\mathbf{H}& \mathbf{h}\\ {\mathbf{h}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\\ \hspace{1em}\frac{\mathrm{1}}{c}\left(‖{\mathbf{x}}_{Nk}-\mathbf{y}‖-‖{\mathbf{x}}_r-\mathbf{y}‖\right)\le \Delta t_{Nk},\\ \hspace{1em}i,j=\mathrm{1,2},\dots ,N,\hspace{0.17em}\hspace{0.17em}k=\mathrm{1},\dots ,M.\end{array}$$

(43)

The inequality constraint is nonconvex. By using the equation ${\tau }_r=(\mathrm{1}/c)(‖{\mathbf{x}}_r-\mathbf{y}‖)$ , the nonconvex inequality can be written as

$$\begin{array}{cc}& \frac{\mathrm{1}}{c}‖{\mathbf{x}}_{Nk}-\mathbf{y}‖\le \frac{\mathrm{1}}{c}‖{\mathbf{x}}_r-\mathbf{y}‖+\Delta t_{Nk}={\tau }_r+\Delta t_{Nk}.\end{array}$$

(44)

Taking square of (44) and expanding it, we have

$$\begin{array}{cc}& -\mathrm{2}\left({\mathbf{x}}_{Nk}^T+{\mathbf{x}}_r^T\right)\mathbf{y}-\mathrm{2}{c}^{\mathrm{2}}\Delta t_{Nk}{\tau }_r\le c^{\mathrm{2}}\Delta t_{Nk}^{\mathrm{2}}-{‖{\mathbf{x}}_{Nk}‖}^{\mathrm{2}}+{‖{\mathbf{x}}_r‖}^{\mathrm{2}},\end{array}$$

(45)

where ${\tau }_r$ is the rth element of the vector h; that is, ${\mathbf{h}}_r={\tau }_r$ . Note that this inequality is convex. Combining all of the convex constraints, we have the following optimization problem with M NLOS connections between the source and the sensors:

$$\begin{array}{cc}& \underset{\mathbf{H},\mathbf{h},\mathbf{y}}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mathrm{T}\mathrm{r}\left\{Q^{-\mathrm{1}}\left(\Delta \mathbf{t}\Delta {\mathbf{t}}^T-\mathrm{2}U\mathbf{h}\Delta {\mathbf{t}}^T+U\mathbf{H}{U}^T\right)\right\}+\beta {\displaystyle \sum }_{i=\mathrm{1}}^N{\displaystyle \sum }_{j=\mathrm{1}}^N{\mathbf{H}}_{ij}\\ \mathrm{s}.\mathrm{t}.\hspace{1em}{\mathbf{H}}_{ii}=\frac{\mathrm{1}}{c^{\mathrm{2}}}\left(\mathrm{T}\mathrm{r}\left(\mathbf{Y}\right)-\mathrm{2}{\mathbf{x}}_i^T\mathbf{y}+{‖{\mathbf{x}}_i‖}^{\mathrm{2}}\right),\\ \hspace{1em}\left[\begin{array}{cc}\mathbf{Y}& \mathbf{y}\\ {\mathbf{y}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\hspace{0.17em}\hspace{0.17em}\left[\begin{array}{cc}\mathbf{H}& \mathbf{h}\\ {\mathbf{h}}^T& \mathrm{1}\end{array}\right]⪰\mathrm{0},\\ \hspace{1em}-\mathrm{2}\left({\mathbf{x}}_{Nk}^T+{\mathbf{x}}_r^T\right)\mathbf{y}-\mathrm{2}{c}^{\mathrm{2}}\Delta t_{Nk}{\mathbf{h}}_r\le c^{\mathrm{2}}\Delta t_{Nk}^{\mathrm{2}}-{‖{\mathbf{x}}_{Nk}‖}^{\mathrm{2}}+{‖{\mathbf{x}}_r‖}^{\mathrm{2}},\\ \hspace{1em}i,j=\mathrm{1,2},\dots ,N,\hspace{0.17em}\hspace{0.17em}k=\mathrm{1},\dots ,M,\end{array}$$

(46)

where $\beta \ge \mathrm{0}$ is a constant for penalization. Similarly, the source position estimate under the LOS/NLOS environment can be derived by solving the convex optimization problem (46) via SDP solver SeDumi [57].

6. Simulation Results

In this section, we provide several examples to demonstrate the performance of the proposed TDOA-based SDP algorithm in comparison with the other TDOA-based algorithms. Also, the performance of the proposed source localization algorithm in the presence of sensor location errors and under LOS/NLOS environment is examined. Recall that the “TDOA-based min-max algorithm (labeled as MMA)” in [11] estimates the source location based on the minimax approximation of the original ML problem. Specifically, two source localization algorithms (SDP-I and SDP-O) have been given, and the simulation results have shown that the SDP-I algorithm outperforms the SDP-O. Thus, in this paper we label indiscriminately SDO-I as MMA and only compare the SDP-I algorithm with our proposed algorithm. The solution of TDOA-based ML formulation (9) is also included in the simulation, which is solved by the MATLAB routine fmincon. The TDOA-based SDP algorithm using all pairwise measurements in [19] is denoted by “AM” here.

In the simulation, eight sensors in a 2-dimensional area are deployed at

$$\begin{array}{cc}& x_{\mathrm{1}}={\left[\mathrm{40},-\mathrm{40}\right]}^T,\\ x_{\mathrm{2}}=\left[\mathrm{40},-\mathrm{40}\right],\\ x_{\mathrm{3}}={\left[-\mathrm{40,40}\right]}^T,\\ x_{\mathrm{4}}={\left[-\mathrm{40},-\mathrm{40}\right]}^T,\\ x_{\mathrm{5}}={\left[\mathrm{40,0}\right]}^T,\\ x_{\mathrm{6}}={\left[\mathrm{0,40}\right]}^T,\\ x_{\mathrm{7}}={\left[-\mathrm{40,0}\right]}^T,\\ x_{\mathrm{8}}={\left[\mathrm{0,40}\right]}^T.\end{array}$$

(47)

The performance is evaluated in terms of the root-mean-square error (RMSE) of the source position, which is defined as

$$\begin{array}{cc}& \mathrm{R}\mathrm{M}\mathrm{S}\mathrm{E}=\sqrt{{\displaystyle \sum }_{m=\mathrm{1}}^M\frac{{‖{\widehat{\mathbf{y}}}_m-{\mathbf{y}}_t‖}^{\mathrm{2}}}{M}},\end{array}$$

(48)

where ${\widehat{\mathbf{y}}}_m$ is the estimate of the source position in the mth Monte Carlo (MC) simulation and M is the number of the MC. In this paper, we set $M=\mathrm{1000}$ . The initial transmission time instant $t_0$ is randomly chosen with a uniform distribution over $[\mathrm{0,50}]$ .

Example 1.

In order to illustrate the importance of the penalty term in (17), this example examines the performance for different penalty factor β including $\beta =\mathrm{0}$ . The results are given in Figures 3 and 4, where the source is located at $\mathbf{y}=[\mathrm{20,30}{]}^T$ and $\mathbf{y}=[\mathrm{120,150}{]}^T$ , respectively. The locations of the eight sensors are given as (47). The case with $\beta \approx \mathrm{0}$ , that is, optimization problem (16), is also considered. The TOA measurements only with LOS connections between the source and sensors are considered. We can see that the optimal penalty factor is dependent on the source location as well as $\mathrm{1}/{\sigma }^{\mathrm{2}}$ . When the source is inside the convex hull of sensors, β can be chosen between $\mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$ and $\mathrm{1}{\mathrm{0}}^{-\mathrm{3}}$ for $\mathrm{1}/{\sigma }^{\mathrm{2}}=\mathrm{30,40,50}$  dB. When the source is outside the convex hull of sensors, β can be chosen between $\mathrm{1}{\mathrm{0}}^{-\mathrm{5}}$ and $\mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$ . We will use this selection criterion of the penalty factor in the next examples.

Figure 3

Comparison of different penalty constant for the proposed SDP algorithms when the source is inside the convex hull of the sensor nodes $(\mathbf{y}=[\mathrm{20,30}{]}^T)$ .

Figure 4

Comparison of different penalty constant for the proposed SDP algorithms when the source is outside the convex hull of the sensor nodes $(\mathbf{y}=[\mathrm{120,150}{]}^T)$ .

Example 2.

In this example, we compare the performance of the proposed TDOA-based SDP algorithm and MMA to examine the sensitivity of the selection of reference sensor. For the MMA, the authors in [11] have proved that better performance can be achieved by choosing the reference sensor with the median TOA measurement criterion. The locations of the eight sensors are also given as (47). The source is located at $\mathbf{y}=[\mathrm{20,30}{]}^T$ , which is inside the convex hull formed by sensors. The penalty factor β is set to $\mathrm{1}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$ . We assume that the sensor locations are error-free. Similar to Example 1, only the LOS TOA measurements are considered in this example. The performance comparison of MMA and the proposed SDP algorithm under different reference sensors is given in Figure 5. It can be observed that the proposed SDP algorithm is more robust against different selections of the reference node compared with the MMA. Moreover, when $r=\mathrm{5}$ is chosen as the reference node, the localization error is larger than that of $r=\mathrm{3}$ especially at low $\mathrm{1}/{\sigma }^{\mathrm{2}}$ ( $\mathrm{1}/{\sigma }^{\mathrm{2}}\le \mathrm{5}$  dB). The proposed SDP algorithm significantly outperforms the MMA in terms of RMSE, regardless of the selection of the reference node. Specifically, there is a 5 dB enhancement in terms of $\mathrm{1}/{\sigma }^{\mathrm{2}}$ for the proposed SDP algorithm compared with the MMA.

Figure 5

Comparison of MMA and the proposed SDP algorithm with different reference nodes r. The source is located at $\mathbf{y}=[\mathrm{20,30}{]}^T$ , which is inside the convex hull of the sensor nodes.

Example 3.

To examine the sensitivity of selection of the reference node when the source is located outside the convex hull formed by sensors, the performance of MMA and the proposed SDP algorithm is compared. The source is located at $\mathbf{y}=[\mathrm{120,150}{]}^T$ . The locations of the eight sensors are given as (47). The penalty factor β is set to $\mathrm{1}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{5}}$ . Also, the sensor locations are assumed to be error-free and only LOS measurements are considered. The performance comparison of the two TDOA-based source localization methods is given in Figure 6. Similar to the results of Example 2, the proposed SDP algorithm is less sensitive to the selection of the reference node compared with the MMA. Thus, we randomly select the reference node for the proposed SDP algorithm in the next examples.

Figure 6

Comparison of MMA and the proposed SDP algorithm with different reference nodes r. The source is located at $\mathbf{y}=[\mathrm{120,150}{]}^T$ , which is outside the convex hull of the sensor nodes.

By comparing the results in Figures 5 and 6, we can find that the MMA source localization algorithm for the case where the source is located outside the convex hull formed by sensors is more sensitive to the selection of the reference node compared with the one for the case where the source is located inside the convex hull. Moreover, we also observe that the selection of the reference node based on the median TOA measurement (i.e., $r=\mathrm{3}$ for both of the two cases) is suitable for both the inside and outside cases.

Example 4.

Here, several source localization algorithms including the proposed SDP, MMA, ML, and AM are compared. The estimation results are given in Figure 7. The source is located at $\mathbf{y}=[\mathrm{30,10}{]}^T$ , which is inside the convex hull of the sensors. The Cramér-Rao low bound (CRLB) [11] is also presented in the simulation. For the ML formulation, the initial value of the searching algorithm is set to be the ground truth of the source position. The AM algorithm proposed in [19], which includes $N(N-\mathrm{1})/\mathrm{2}$ pairwise TDOA measurements and neglects the correlated noise induced by the preprocessing through subtraction, is also compared. Furthermore, we also extend our proposed SDP algorithm to the scenario that includes $N(N-\mathrm{1})/\mathrm{2}$ pairwise TDOA measurements. The noises are assumed to be correlated. Here, we label such an algorithm as “SDP-proposed, AM”.

From the results, we can see that ML in this scenario provides the best performance. The proposed SDP algorithm performs better than MMA. The reason for this is that MMA is a minimax approximation of the ML formulation. Such an approximation can lead to performance loss. The performances of the AM and the proposed SDP algorithms are very close to each other, and both of them give a good estimation, especially at high $\mathrm{1}/{\sigma }^{\mathrm{2}}$ (over $\mathrm{30}$  dB). However, the good estimation of the AM algorithm is derived at the expense of high computational complexity as all the pairwise TDOA measurements are employed. We can also observe that the proposed SDP algorithm with $N-\mathrm{1}$ TDOA measurements provides a better estimate compared with the AM algorithm proposed in [19] and the MMA proposed in [11]. The performances of the extended SDP algorithm with $N(N-\mathrm{1})/\mathrm{2}$ TDOA measurements labeled as SDP-proposed, AM and the proposed SDP algorithm with $N-\mathrm{1}$ TDOA measurements labeled as SDP-proposed are very close to each other. Both of these two proposed algorithms outperform the AM algorithm. Furthermore, the increase of the number of TDOA measurements (from $N-\mathrm{1}$ to $N(N-\mathrm{1})/\mathrm{2}$ ) does not significantly provide the performance improvement for the proposed SDP algorithm. That is, the proposed SDP algorithm provides comparable performance with the extended SDP algorithm.

To illustrate the computational cost of the AM algorithm, we give a comparison of the average CPU time in Table 1. All the results are obtained by using an Intel core i5-4200U PC with 1.60 GHz CPU and 8 G RAM. For ML, the true source location is considered as the initial point and two different MATLAB iterative methods are employed. The small one is the time of the MATLAB routine fmincon, whereas the large one is the time of the MATLAB routine GlobalSearch. From the results, we can see that our proposed SDP algorithm requires moderate CPU time compared with MMA and AM algorithm. Thus, the proposed SDP source localization algorithm provides a tradeoff between the localization accuracy and computational complexity compared with AM algorithm and MMA.

Table 1

Average CPU computational time per estimation for different source localization algorithms.

Algorithm	Average CPU estimation time (ms)
ML	27.51/523.01
AM	438.53
MMA	265.20
Proposed SDP	327.60

Figure 7

Comparison of MMA, ML algorithm, and the proposed SDP algorithm with reference nodes $r=\mathrm{6}$ and the AM algorithm when the source is inside the convex hull of the sensor nodes $(\mathbf{y}=[\mathrm{30,10}{]}^T)$ .

Example 5.

In this example, the sensors are also placed at the locations given by (47), and we position the source at $\mathbf{y}=[\mathrm{100,80}{]}^T$ , which is outside the convex hull of sensors. The performance comparison of the above source localization algorithms is given in Figure 8. It can be seen that the performances of AM and the proposed SDP algorithms are very close to each other. Also, the performance of these two algorithms is very close to the CRLB under most of the range of $\mathrm{1}/{\sigma }^{\mathrm{2}}$ (from 0 dB to 30 dB). Both the AM and the proposed SDP algorithms outperform the ML algorithm since the cost function of ML formulation is nonconvex and it is easy to trap into the local minima. Similar to the result of Example 3, both the proposed SDP and AM generate better performance than the MMA. Both the proposed SDP algorithm and the extended SDP algorithm provide better estimate than the MMA. Also, the performance of the two algorithm is very close to the CRLB when the source is located outside the convex hull formed by sensors.

Figure 8

Comparison of MMA, ML algorithm, and the proposed SDP algorithm with reference nodes $r=\mathrm{6}$ and the AM algorithm when the source is outside the convex hull of the sensor nodes $(\mathbf{y}=[\mathrm{100,80}{]}^T)$ .

Example 6.

Here, we test the source estimation performance under given sensors location errors. The results are given in Figures 9 and 10. The source is located in $\mathbf{y}=[\mathrm{25,10}{]}^T$ and $\mathbf{y}=[\mathrm{100,80}{]}^T$ , respectively. In this example, ${\sigma }_s$ is defined as the location error variance of the sensor node. For each dimension of sensor position z, we generate sensor node location error according to the truncated Gaussian distribution in the interval $\left|z\right|\le {\sigma }_s/\sqrt{\alpha }$ ; its PDF is given by

$$\begin{array}{cc}& f\left(z\right)=\left\{\begin{array}{cc}\frac{\left(\sqrt{\alpha }/\sqrt{\mathrm{2}\pi }{\sigma }_s\right)\mathrm{e}\mathrm{x}\mathrm{p}\left(-\alpha z^{\mathrm{2}}/\mathrm{2}{\sigma }_s^{\mathrm{2}}\right)}{\mathrm{2}\Phi \left(\sqrt{\alpha }\right)-\mathrm{1}}\hfill & \left|z\right|\le \frac{{\sigma }_s}{\sqrt{\alpha }},\hfill \\ \mathrm{0}\hfill & \left|z\right|>\frac{{\sigma }_s}{\sqrt{\alpha }},\hfill \end{array}\right.\end{array}$$

(49)

where $\Phi (x)={\int }_{-\infty }^x‍(\mathrm{1}/\sqrt{\mathrm{2}\pi })\mathrm{e}\mathrm{x}\mathrm{p}\left(\left(\mathrm{1}/\mathrm{2}\right){\upsilon }^{\mathrm{2}}\right)d\upsilon$ is the cumulative distribution function of the standard norm distribution and α is the factor to make the position error variable ${‖{\mathbf{\xi }}_i‖}^2$ lie at the interval ${‖{\mathbf{\xi }}_i‖}^2\le {\sigma }_s^{\mathrm{2}}$ . For 2-dimension sensor nodes, $\alpha =\mathrm{2}$ . We consider ${\sigma }_s=\mathrm{0}$ , ${\sigma }_s=\mathrm{0.5}$ , ${\sigma }_s=\mathrm{1}$ , and ${\sigma }_s=\mathrm{2}$ in Figures 7 and 8. ${\sigma }_s=\mathrm{0}$ means that the sensors self-localization is error-free. Due to the random characteristic of sensor location errors, the RMSE of estimation in the presence of sensor location errors is defined as

$$\begin{array}{cc}& \mathrm{R}\mathrm{M}\mathrm{S}{\mathrm{E}}_e=\sqrt{{\displaystyle \sum }_{k=\mathrm{1}}^K\hspace{0.17em}{\displaystyle \sum }_{m=\mathrm{1}}^M\frac{{‖{\widehat{\mathbf{y}}}_{mk}-{\mathbf{y}}_r‖}^{\mathrm{2}}}{MK}},\end{array}$$

(50)

where K is the number of the MC runs in terms of different sensor self-localization results and M is the number of the MC runs in terms of different noises. In this example, we set $K=\mathrm{500}$ and $M=\mathrm{500}$ .

Figure 9

Source location estimation in the presence of sensors self-localization errors. The source is inside the convex hull of the sensor nodes $(\mathbf{y}=[\mathrm{25,10}{]}^T)$ . The penalty factor is $\beta =\mathrm{5.0}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$ .

Figure 10

Source location estimation in the presence of sensors self-localization errors. The source is outside the convex hull of the sensor nodes $(\mathbf{y}=[\mathrm{100,80}{]}^T)$ . The penalty factor is $\beta =\mathrm{1.0}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{5}}$ .

It can be seen from the results that the proposed SDP algorithm without sensor location error provides the best performance. As the error variance of sensors self-localization increases, the performance of the proposed SDP algorithm degrades. There is a performance upper bound of the source localization for the case where the fixed source location is both inside and outside the convex hull of sensor nodes.

Example 7.

In previous examples, the proposed SDP algorithm is compared with the mentioned algorithms under LOS connections between the source and the sensors. However, this is a very unrealistic situation. In this example, the performance analysis under both LOS and NLOS connections by solving convex problem (46) is carried out. We label the algorithm as “SDP, LOS/NLOS”. We also give the performance of the proposed SDP algorithm only with LOS connections (i.e., the scenario where NLOS TDOA components are discarded is included). We label the algorithm with such a scenario as “SDP, only LOS”. Furthermore, the performance of the SDP algorithm by taking all of the TDOA measurements (including both LOS and NLOS measurements) as LOS measurements is considered. We label the algorithm with such a scenario as “SDP”.

In this example, the sensors are randomly distributed at 2-dimensional region $\mathrm{40}\times \mathrm{40}$  m². The source is also randomly located at such an area. The penalty factor β is set to $\mathrm{1}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$ . The sensor locations are assumed to be error-free. There are 8 sensors to be used to estimate the source location. $M=\mathrm{2}$ sensors are assumed to generate NLOS TOA measurements, which have been identified by the hypothesis test. $N=\mathrm{6}$ sensors are assumed to generate LOS TOA measurements. Note that, in Section 6, we make no assumptions about the statistical distribution of the NLOS TOA bias errors. For the purpose of simulation, we assume that the bias errors are uniformly distributed; $b_k~\mathcal{B}(\mathrm{0},B)$ [31]. Here, we set $B=\mathrm{2}$  s and the number of MC $M=\mathrm{5000}$ . Figure 11 gives the simulation results.

Figure 11

Source location estimation under LOS/NLOS environments. The sensors are randomly distributed at 2-dimensional region $\mathrm{40}\times \mathrm{40}$  m². The penalty factor is $\beta =\mathrm{1.0}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$ .

It can be observed that the proposed SDP source localization algorithm under LOS/NLOS environments, that is, the solution of problem (46), can provide accurate source location estimate under both LOS and NLOS connections between the source and the sensors. The performance of the proposed SDP algorithm under LOS/NLOS environments is better than the SDP algorithm with only LOS TOA measurements. This is because the proposed algorithm employs all of the information from the sensors, which includes the NLOS measurements, whereas the SDP algorithm discards the NLOS information. Furthermore, we can see that the original SDP algorithm by taking both LOS and NLOS measurements as LOS ones suffers performance degradations in most of the range of $\mathrm{1}/{\sigma }^{\mathrm{2}}$ ( $\mathrm{1}/{\sigma }^{\mathrm{2}}\ge \mathrm{10}$  dB). However, there is an exception. When $\mathrm{1}/{\sigma }^{\mathrm{2}}\le \mathrm{5}$  dB, the original SDP algorithm by taking all of TOA measurements as LOS ones outperforms both the SDP algorithm under LOS/NLOS environments and the SDP algorithm with only LOS measurements. One reason for this is that the same treatment of both LOS and NLOS measurements is reasonable when the LOS TOA measurement errors are larger than or equal to the NLOS bias errors under low $\mathrm{1}/{\sigma }^{\mathrm{2}}$ .

From the above simulations, we can derive the following conclusion:

• (1)

Our proposed SDP algorithm provides a robust estimate in terms of the selection of the reference sensor compared with the MMA.

(2)

The proposed SDP algorithm outperforms the MMA and provides comparable performance with the extended SDP algorithm, which gives a good estimate at the expense of high computational complexity.

(3)

There is a performance upper bound for the robust source localization against sensor location errors when $\mathrm{1}/{\sigma }^{\mathrm{2}}$ increases.

(4)

The proposed SDP algorithm under both LOS and NLOS environments provides a better estimate compared with the SDP algorithm by taking all of measurements as LOS ones and the SDP algorithm with discarding NLOS information.

7. Conclusion

In this paper, we investigate the problem of TDOA-based source localization in sensor networks. Based on the correlated TDOA noise measurements, we propose an alternative convex optimization formulation for the ML problem. The robust source localization algorithm in the presence of sensor location errors is also given. Furthermore, the LOS/NLOS environments are considered by taking the NLOS measurements as several constraints of the convex optimization problem. Simulation results show that the proposed TDOA-based SDP algorithm provides superior estimation, especially for the case where the source is located outside the convex hull of sensors. Also, the SDP algorithm works well with low sensitivity of selection of the reference node of the TDOA measurements. The proposed SDP algorithm under both LOS and NLOS environments provides a better estimation compared with the one by discarding the NLOS measurements. However, the proposed SDP source localization algorithm considers the estimate without the communication errors between the sensors and the fusion center, which can deteriorate the performance. The source localization algorithm taking the communication errors into account will be studied in our future work.