Total Least Squares Method for Robust Source Localization in Sensor Networks Using TDOA Measurements

Abstract

The TDOA-based source localization problem in sensor networks is considered with sensor node location uncertainty. A total least squares (TLSs) algorithm is developed by a linear closed-form solution for this problem, and the uncertainty of the sensor location is formulated as a perturbation. The sensitivity of the TLS solution is also analyzed. Simulation results show its improved performance against the classic least squares approaches.

1. Introduction

Driven by many practical applications such as environment monitoring, traffic management in intelligent transportation, healthcare for the older and disabled, cyber-physical system (CPS) has emerged as a new advanced system to link the virtual cyber world with the real physical world [1, 2]. Sensor network is crucial to enable CPS by efficient monitoring and understanding the physical world. The main purpose of a sensor network is to monitor an area, including detecting, identifying, localizing, and tracking one or more objects of interest. These networks may be used by the military in surveillance, reconnaissance, and combat scenarios or around the perimeter of a manufacturing plant for intrusion detection. The problem of source localization involves the estimation of the position of a stationary transmitter from multiple noisy sensor measurements, which can be time-of-arrival (TOA), time-difference-of-arrival (TDOA), or angle-of-arrival (AOA) measurements or a combination of them [3–5].

Source localization methods using TDOA measurements locate the source at the intersection of a set of hyperboloids. Finding this intersection is a highly nonlinear problem [6, 7]. Over the years, many iterative numerical algorithms have been proposed for the problem, including the maximum likelihood estimation methods [8, 9] and the constrained optimization methods [10, 11]. In these approaches, linear approximation and iterative numerical techniques have to be used to deal with the nonlinearity of the hyperbolic equations. However, it is difficult to select a good initial guess to avoid a local minimum for them; therefore the convergence to the optimal solution cannot be guaranteed. The closed-form solution methods are widely used since no initial solution guesses are required and have no divergence problem compared with the iterative techniques [12–16]. For real-time application in WSNs, the iterative procedure for iterative algorithm is time consuming while the closed-form method is computational efficient.

The aforementioned approaches need the precise location of sensors. In practice, the receiver locations may not be known exactly. For example, in sensor network applications, the receivers can be with airplanes or unmanned aerial vehicles (UAVs) whose positions and velocities may not be precisely known. Hence, the inaccuracy in receiver locations needs to be taken into account in practical applications which is challenging and difficult as the estimation performance of source location can be very sensitive to the accurate knowledge of the receiver positions and a slight error in a receiver's location can lead to a big error in the source location estimate. In [17], a closed-form solution is proposed that takes the receiver error into account to reduce the estimation error. The proposed solution is computationally efficient and does not have the divergence problem as in the iterative techniques. In [18], the maximum likelihood formulation of source localization problem is given and an efficient convex relaxation for this nonconvex optimization problem is proposed. A formulation for robust source localization in the presence of sensor location errors is also proposed. Both the above methods assume that the measurement noise is Gaussian and characterize the uncertainty by stochastic approach with the perturbation being white and Gaussian.

However, such white and Gaussian assumptions are unrealistic in many practical applications [19–21]. Usually, if the Gaussian assumption are not met, the maximum-likelihood-based results under Gaussian assumption may lead to poor estimation performance, which means that the estimation performance is sensitive to the exact knowledge of the parameters of the system (see, e.g., [22]). These facts motivate us to further research on robust source localization method without any distribution assumption for measurements noise and sensor location error.

In this paper, we will develop a total least squares (TLSs) algorithm for location estimation of a stationary source. TLS is a least squares data modeling technique in which observational errors on both dependent and independent variables are taken into account. The uncertainty of the sensor location is formulated as a perturbation on the given sensor location. The sensitivity of the TLS solution will also be analyzed to show the superiority of our proposed algorithm. Compared with the existing methods which need the Gaussian assumption for both measurements noise and sensor location error, the TLS approach does not depend on any assumed distribution of the noise and errors. Simulation results support the above analysis and show good performance of the proposed method.

The rest of this paper is organized as follows. In Section 2, a linear closed-form solution is given for source localization problem using TDOA measurements. The total least squares method for source localization with sensor location uncertainty is given in Section 3, and the corresponding sensitivity analysis is derived in Section 4. Simulation results are presented in Section 5 to show the improved performance of the proposed method against the classic least squares approaches. Concluding remarks are made in Section 6.

2. A Linear Closed-Form Solution

Assume that sensor i is located at point $S_{i} = {x_{i}, y_{i}, z_{i}}$ . Denote the unknown source location by $S = {x, y, z}$ . Let c be the signal propagation speed and N the number of sensor nodes distributed in the network. A reference node, denoted as $S_{0}$ , exists in the field. We define the distance from the source to sensor i as $D_{i}$ . The TDOA that we derive from the data, $τ_{0 i}$ , for each sensor node $i \in [1, N]$ relative to the reference sensor $S_{0}$ is

\begin{matrix} τ_{0 i} = \frac{1}{c} ‖ S - S_{0} ‖ - \frac{1}{c} ‖ S - S_{i} ‖ = \frac{1}{c} (D_{0} - D_{i}) . \end{matrix}

(1)

Denote the distance difference of arrival (DDOA) data for the ith sensor as

\begin{matrix} d_{0 i} = τ_{0 i} \times c = D_{0} - D_{i} . \end{matrix}

(2)

We have

\begin{matrix} D_{0}^{2} - D_{i}^{2} & = {‖ S - S_{0} ‖}^{2} - {‖ S - S_{i} ‖}^{2}, \\ = {(x - x_{0})}^{2} + {(y - y_{0})}^{2} + {(z - z_{0})}^{2}, \\ - ({(x - x_{i})}^{2} + {(y - y_{i})}^{2} + {(z - z_{i})}^{2}), \\ = x_{0}^{2} - x_{i}^{2} + 2 x (x_{i} - x_{0}) + y_{0}^{2} - y_{i}^{2} + 2 y (y_{i} - y_{0}), \\ + z_{0}^{2} - z_{i}^{2} + 2 z (z_{i} - z_{0}), \\ = D_{0}^{2} - {(D_{0} - d_{0 i})}^{2}, \\ = 2 D_{0} d_{0 i} - d_{0 i}^{2} . \end{matrix}

(3)

Group all the known terms together and denote

\begin{matrix} b_{i} = \frac{1}{2} [x_{0}^{2} - x_{i}^{2} + y_{0}^{2} - y_{i}^{2} + z_{0}^{2} - z_{i}^{2} + d_{0 i}^{2}] \end{matrix} .

(4)

Rearranging and substituting give

\begin{matrix} (x_{0} - x_{i}) x + (y_{0} - y_{i}) y + (z_{0} - z_{i}) z + d_{0 i} D_{0} = b_{i}, \end{matrix}

(5)

which is a linear model for unknown parameters

x, y, z

, and

D_{0}

. Stacking the N sensor measurements, we have the linear system in matrix form

\begin{matrix} A X = b, \end{matrix}

(6)

where

\begin{gathered} A = [\begin{bmatrix} x_{0} - x_{1} & y_{0} - y_{1} & z_{0} - z_{1} & d_{01} \\ x_{0} - x_{2} & y_{0} - y_{2} & z_{0} - z_{2} & d_{02} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ x_{0} - x_{N} & y_{0} - y_{N} & z_{0} - z_{N} & d_{0 N} \end{bmatrix}], \\ X = [\begin{bmatrix} x \\ y \\ z \\ D_{0} \end{bmatrix}], b = [\begin{bmatrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{N} \end{bmatrix}] . \end{gathered}

(7)

When the location of sensor nodes can be precisely known and the TDOA measurements are noise-free, linear system (6) is compatible. The solution is unique while the data matrix A is of full rank.

In [16], a noise ɛ is considered at the right side of (6):

\begin{matrix} A X = b + ɛ . \end{matrix}

(8)

The least squares (LSs) problem seeks to

\begin{matrix} minimize : ‖ b - b_{ls} ‖, \\ subject to : b_{ls} \in R (A), \end{matrix}

(9)

where

ℛ (A)

denote the vector space spanned by the column vector of matrix A. Once a minimizing

b_{ls}

is found, then any X satisfying

A X = b_{ls}

is called an LS solution and

b - b_{ls}

the corresponding LS correction. The unique LS solution can be obtained while the data matrix A is of full rank:

\begin{matrix} X_{ls} = {(A^{T} A)}^{- 1} A^{T} b . \end{matrix}

(10)

The ordinary LS problem amounts to perturbing the observation vector b by a minimum amount $b - A X_{l s}$ . The underlying assumption is that errors only occur in the vector b and that the matrix A is exactly known. However, the TDOA measurements always have noise, that is, $d_{0 i}$ is perturbed by a noise. Hence, both sides of (5) have perturbation according to term $d_{0 i}$ . Besides, in practice, the receiver locations may not be known exactly. As a result, the inaccuracy in receiver locations needs to be taken into account in practical environments. Therefore, considering only the perturbation at the right side of (6) is not enough. We should consider the perturbations at both sides.

3. Total Least Squares Solution

The definition of the total least squares method is motivated by the asymmetry of the least squares method that b is corrected while A is not. Provided that both A and b are given data, it is reasonable to treat them symmetrically. One important application of TLS problem is parameter estimation in errors-in-variables models, that is, considering the measurements in A [23, 24]. We assume that the m measurement in $\tilde{A}$ and $\tilde{b}$ by

\begin{matrix} \tilde{A} X = \tilde{b}, \end{matrix}

(11)

where

\tilde{A} = A + Δ A

\tilde{b} = b + Δ b

, and

A X = b

, is compatible. The total least squares (TLSs) problem seeks to

\begin{matrix} minimize : {‖ [\tilde{A}; \tilde{b}] - [A_{tls}; b_{tls}] ‖}_{F}, \\ subject to : b_{tls} \in R (A_{tls}), \end{matrix}

(12)

where

{∥ \cdot ∥}_{F}

denotes the Frobenius norm of matrix A, that is,

\begin{matrix} {‖ A ‖}_{F} = \sqrt{\sum_{i = 1}^{m} \sum_{j}^{n} {| a_{i j} |}^{2}} = \sqrt{trace (A^{T} A)} . \end{matrix}

(13)

Once a minimizing

[A_{tls}; b_{tls}]

is found, then any X satisfying

A_{tls} X = b_{tls}

is called a TLS solution and

[\tilde{A}; \tilde{b}] - [A_{tls}; b_{tls}]

the corresponding TLS correction [25].

When A is of full rank, the closed-form expression of the basic TLS solution can be obtained as the following:

\begin{matrix} X_{tls} = {({\tilde{A}}^{T} \tilde{A} - σ_{n + 1}^{2} I)}^{- 1} {\tilde{A}}^{T} \tilde{b}, \end{matrix}

(14)

where

σ_{n + 1}

is the smallest singular value of

[A; b]

. It can be proved that the TLS solution

X_{tls}

estimates the true parameter

A^{+} b

consistently, that is, X_tls converges to the solution of

A X = b

as the number of measurements tends to infinity, where

A^{+}

denotes the Moore-Penrose pseudoinverse of matrix A. This property of TLS estimates does not depend on any assumed distribution of the errors. Note that the LS estimates are inconsistent in this case.

In the following, the algorithm computation complexity is analyzed by considering the number of floating-point operations (FLOPS). The calculation of FLOPS is briefly described as follows: additions and multiplications count as one FLOP each. Adding matrices of sizes $m \times n$ requires $m n$ FLOPS. Multiplying matrices of sizes $m \times k$ and $k \times p$ requires $m n k$ FLOPS. Matrix inverse of size $n \times n$ requires $n^{3}$ FLOPS. Singular value decomposition of matrix with size $n \times m$ requires $n m^{2}$ FLOPS. The computation overhead of three closed-form algorithms is investigated, that is, least squares (LSs) method in [16], two-stage weighted least squares (WLSs) method in [17] and the proposed TLS method. For N-deployed nodes and p dimension of source location parameter, the numbers of FLOPS in the LS, WLS, and the proposed TLS algorithms are $(2 p + 3) (p + 1) N + {(p + 1)}^{3}$ , $(2 p + 3) (2 p + 2) N + 2 {(p + 1)}^{3}$ , and $(2 p + 5) (p + 2) N + {(p + 2)}^{2} (p + 3)$ , respectively. It is to show that LS method is the most computationally efficient, whereas WLS method is two-stage least square and TLS method has singular value decomposition for matrix. It is clear that they all have comparable computation complexity $𝒪 (N)$ since $p = 3$ or $p = 4$ for source localization problem.

4. Sensitivity Properties of the Solution

In this section, we will first examine how perturbations in A and b affect the solution X. In this analysis the condition number of the matrix A plays a significant role. The following definition generalizes the condition number of a square nonsingular matrix [26].

Definition 1.

Let $A \in ℛ^{m \times n}$ have rank r. The condition number of A is

\begin{matrix} κ (A) = ‖ A ‖ \cdot ‖ A^{+} ‖ = \frac{σ_{1}}{σ_{r}}, \end{matrix}

(15)

where

σ_{1}, σ_{2}, \dots, σ_{r}

are the singular values of A by decreasing order.

Matrices with small condition numbers are said to be well conditioned while the ones with large condition numbers are said to be ill-conditioned. Analyzing the effect of perturbation on the solution of linear system $A X = b$ , we introduce the following lemma [27].

Lemma 1.

If $rank (\tilde{A}) = rank (A)$ and $∥ Δ A ∥ ∥ A^{+} ∥ < 1$ , then

\begin{matrix} ‖ {\tilde{A}}^{+} ‖ \leq \frac{‖ A^{+} ‖}{1 - ‖ A^{+} ‖ ‖ Δ A ‖} . \end{matrix}

(16)

Theorem 1.

Denote $X_{ls} = A^{+} b$ as the LS solution of unperturbed system $A X = b$ , and ${\tilde{X}}_{ls} = {\tilde{A}}^{+} \tilde{b}$ is the LS solution of perturbed system $\tilde{A} X = \tilde{b}$ with $\tilde{A} = A + Δ A$ , $\tilde{b} = b + Δ b$ . One further assumes that $∥ Δ A ∥ \leq ɛ ∥ A ∥$ , $∥ Δ b ∥ \leq ɛ ∥ b ∥$ , $κ (A) = κ$ . Then, one has

\begin{matrix} \frac{‖ {\tilde{X}}_{ls} - X_{ls} ‖}{‖ X_{ls} ‖} = O (ɛ κ) . \end{matrix}

(17)

Proof.

Noting that A and $\tilde{A}$ are full rank and $(I - A A^{+}) b = 0$ since $b \in ℛ (A)$ , we have

\begin{matrix} {\tilde{X}}_{ls} - X_{ls} & = {\tilde{A}}^{+} \tilde{b} - A^{+} b \\ = {\tilde{A}}^{+} (b + Δ b) - A^{+} b \\ = {\tilde{A}}^{+} Δ b + ({\tilde{A}}^{+} - A^{+}) b \\ = {\tilde{A}}^{+} Δ b + ({\tilde{A}}^{+} + {\tilde{A}}^{+} A A^{+} - {\tilde{A}}^{+} A A^{+} - A^{+}) b \\ = {\tilde{A}}^{+} Δ b + ({\tilde{A}}^{+} + {\tilde{A}}^{+} A A^{+} - {\tilde{A}}^{+} A A^{+} - {\tilde{A}}^{+} \tilde{A} A^{+}) b \\ = {\tilde{A}}^{+} Δ b + {\tilde{A}}^{+} (I - A A^{+}) b - {\tilde{A}}^{+} (\tilde{A} - A) A^{+} b \\ = {\tilde{A}}^{+} Δ b - {\tilde{A}}^{+} Δ A X_{ls} . \end{matrix}

(18)

Therefore,

∥ {\tilde{X}}_{ls} - X_{ls} ∥ = ∥ {\tilde{A}}^{+} Δ b - {\tilde{A}}^{+} Δ A X_{ls} ∥

. Dividing by

∥ X_{ls} ∥

at both sides, we have

\begin{matrix} \frac{‖ {\tilde{X}}_{ls} - X_{ls} ‖}{‖ X_{ls} ‖} & = \frac{‖ {\tilde{A}}^{+} Δ b - {\tilde{A}}^{+} Δ A X_{ls} ‖}{‖ X_{ls} ‖} \\ \leq \frac{{\tilde{A}}^{+} Δ b}{‖ X_{ls} ‖} + ‖ {\tilde{A}}^{+} Δ A ‖ \\ \leq ‖ {\tilde{A}}^{+} ‖ (\frac{‖ Δ b ‖}{‖ X_{ls} ‖} + ‖ Δ A ‖) \\ \leq ‖ {\tilde{A}}^{+} ‖ (\frac{ɛ ‖ b ‖}{‖ X_{ls} ‖} + ɛ ‖ A ‖) \\ \leq \frac{‖ A^{+} ‖}{1 - ‖ A^{+} ‖ ‖ Δ A ‖} (\frac{ɛ ‖ b ‖}{‖ X_{ls} ‖} + ɛ ‖ A ‖) \\ \leq \frac{‖ A^{+} ‖}{1 - ‖ A^{+} ‖ ɛ ‖ A ‖} (\frac{ɛ ‖ b ‖}{‖ X_{ls} ‖} + ɛ ‖ A ‖) \\ = \frac{1}{1 - ɛ κ} (\frac{ɛ ‖ A^{+} ‖ ‖ b ‖}{‖ A^{+} b ‖} + ɛ κ) \\ = \frac{1}{1 - ɛ κ} (\frac{ɛ ‖ A^{+} ‖ ‖ A A^{+} b ‖}{‖ A^{+} b ‖} + ɛ κ) \\ \leq \frac{1}{1 - ɛ κ} (\frac{ɛ ‖ A^{+} ‖ ‖ A ‖ ‖ A^{+} b ‖}{‖ A^{+} b ‖} + ɛ κ) \\ = \frac{2 ɛ κ}{1 - ɛ κ} = O (ɛ κ) . \end{matrix}

(19)

From the theorem we can see that, only when the perturbations are sufficiently small, the LS solution is a good estimator of the true solution of $A X = b$ .

Additionally, we will show when the TLS solution has better performance than the LS solution for the perturbed model $\tilde{A} X \approx \tilde{b}$ . Denote the singular value decomposition (SVD) of A by

\begin{matrix} A = U Σ V^{T}, \end{matrix}

(20)

where

\begin{matrix} U & = [u_{1}, u_{2}^{'}, \dots, u_{m}], U^{'} \in R^{m}, U^{T} U = I_{m}, \\ V & = [v_{1}, v_{2}^{'}, \dots, v_{n}], V^{'} \in R^{n}, V^{T} V = I_{n}, \\ Σ & = diag (σ_{1}, σ_{2}, \dots, σ_{n}) \in R^{m \times n}, σ_{1} \geq σ_{2} \geq \dots \geq σ_{n} \geq 0, \end{matrix}

(21)

denote the singular value decomposition (SVD) of

\tilde{A}

\begin{matrix} A + Δ A = \tilde{A} = U^{'} Σ^{'} V^{' T}, \end{matrix}

(22)

where

\begin{matrix} U' & = [u_{1}^{'}, u_{2}^{'}, \dots, u_{m}^{'}], U^{'} \in R^{m}, {U^{'}}^{T} U^{'} = I_{m}, \\ V' & = [v_{1}^{'}, v_{2}^{'}, \dots, v_{n}^{'}], V^{'} \in R^{n}, {V^{'}}^{T} V^{'} = I_{n}, \\ Σ' & = diag (σ_{1}^{'}, σ_{2}^{'}, \dots, σ_{n}^{'}) \in R^{m \times n}, \\ σ_{1}^{'} \geq σ_{2}^{'} \geq \dots \geq σ_{n}^{'} \geq 0, \end{matrix}

(23)

and denote the SVD of

[\tilde{A}; \tilde{b}]

\begin{matrix} [A + Δ A; b + Δ b, \tilde{A}; \tilde{b}] = \tilde{U} \tilde{Σ} {\tilde{V}}^{T}, \end{matrix}

(24)

where

\begin{matrix} \tilde{U} & = [{\tilde{u}}_{1}, {\tilde{u}}_{2}, \dots, {\tilde{u}}_{m}], \tilde{U} \in R^{m}, {\tilde{U}}^{T} \tilde{U} = I_{m}, \\ \tilde{V} & = [{\tilde{v}}_{1}, {\tilde{v}}_{2}, \dots, {\tilde{v}}_{n}], \tilde{V} \in R^{(n + 1)}, {\tilde{V}}^{T} \tilde{V} = I_{n + 1}, \\ \tilde{Σ} & = diag ({\tilde{σ}}_{1}, {\tilde{σ}}_{2}, \dots, {\tilde{σ}}_{n}, {\tilde{σ}}_{n + 1}) \in R^{m \times n + 1}, \\ {\tilde{σ}}_{1} \geq {\tilde{σ}}_{2} \geq \dots \geq {\tilde{σ}}_{(n + 1)} \geq 0 . \end{matrix}

(25)

The accuracy of TLS and LS solutions related to the perturbation effects on singular values and associated singular subspaces [23]. Several papers have analyzed the bounds on the perturbation effects related to singular subspaces [28–30]. The most interesting results for sensitivity analysis of TLS solution are given in [30].

Definition 2.

Denote two subspaces as L and M. For any unitary invariant norm, the distance between two subspaces is defined as the sine of the largest canonical angle

\begin{matrix} dist (L, M) = ‖ \sin Θ (L, M) ‖ = ‖ (I - P_{M}) P_{L} ‖, \end{matrix}

(26)

where

P_{M}

and

P_{L}

are the projection operators [29, 30].

Theorem 2.

Let the SVD of $A \in ℛ^{m \times n}, m \geq n$ , be given by (20), $rank (A) = r$ . Add perturbations $Δ A$ to A, and let SVD of $\tilde{A}$ be given by (22). If $σ_{r}^{'} - σ_{r + 1} > 0$ , then

\begin{matrix} dist (R (A), R (\tilde{A})) \leq \frac{‖ Δ A ‖}{σ_{r}^{'} - σ_{r + 1}} . \end{matrix}

(27)

Theorem 2 is a special case of the generalized $\sin θ$ -theorem in [30].

Recall the perturbed system $\tilde{A} X \approx \tilde{b}$ ; LS projects $\tilde{A}$ and $\tilde{b}$ into the singular subspaces

\begin{matrix} L (u_{1}^{'}, u_{2}^{'}, \dots, u_{m}^{'}) = R (\tilde{A}), \end{matrix}

(28)

while the TLS projects

\tilde{A}

and

\tilde{b}

into the singular subspaces

\begin{matrix} L ({\tilde{u}}_{1}, {\tilde{u}}_{2}, \dots, {\tilde{u}}_{m}) = R ([\tilde{A}; \tilde{b}]) . \end{matrix}

(29)

Furthermore, the real source location

X \in ℛ (A)

, since

A X = b

. Therefore, it is important to analyze the distance between

ℛ (\tilde{A})

ℛ ([\tilde{A}; \tilde{b}])

and

ℛ (A)

. Assumeing that A and

\tilde{A}

have full rank, we can obtain the following corollary according to Theorem 2.

Corollary 1.

One has

\begin{gathered} dist (R (A), R (\tilde{A})) \leq \frac{‖ Δ A ‖}{σ_{n}^{'}}, \\ dist (R (A), R ([\tilde{A}; \tilde{b}])) \leq \frac{‖ Δ A ‖}{{\tilde{σ}}_{n}} . \end{gathered} \begin{matrix}  \end{matrix}

(30)

The interlacing theorem (see [31]) implies that

\begin{matrix} σ_{1}^{'} \geq {\tilde{σ}}_{1} \geq \dots \geq σ_{n}^{'} \geq {\tilde{σ}}_{n} . \end{matrix}

(31)

Therefore,

\begin{matrix} \frac{‖ Δ A ‖}{{\tilde{σ}}_{n}} \leq \frac{‖ Δ A ‖}{σ_{n}^{'}} . \end{matrix}

(32)

From Corollary 1 we can see that the upper bound of the distance between

ℛ (\tilde{A})

and

ℛ (A)

is smaller than the upper bound of distance between

ℛ ([\tilde{A}; \tilde{b}])

and

ℛ (A)

. This implies that the TLS solution is expected to be closer to its corresponding unperturbed subspace. Hence, the TLS solution is expected to be more accurate than the LS solution.

5. Simulations

5.1. Simulation Setup

In this section, simulations are carried out to show the effectiveness of the proposed method. Two scenarios are investigated for their effects on localization performance, including Gaussian distribution and truncated Gaussian distribution for measurement noise and sensor node location error. In our simulation, unless otherwise specified, sensors are randomly deployed in a $5000 m \times 5000 m$ area with uniform distribution. An example is shown in Figure 1, where 30 nodes are uniformly distributed. The source is denoted as a triangle with red and the reference node is denoted as a square in blue. The exact location of the reference node can be known.

Figure 1

Simulation scenario.

In order to show the improved performance of our proposed method with the existing closed-form method, we investigate LS method in [16] and WLS method in [17]. Root mean square error (RMSE) is used as the criterion for localization performance. The following simulations are performed with 500 Monte Carlo trials. In all figures, the red solid line with square, black dash line with circle, and blue dotted dash line with triangle represent the results of TLS, WLS, and LS solutions, respectively.

5.2. Gaussian Case

In this case, we consider the Gaussian distribution for both measurement noise and sensor node location error. The effect on estimation performance for different measurement noise variance value is investigated. Measurement noise variance $(σ_{n})$ is changed in the range 10–100. The variance of perturbation $(σ_{p})$ is set to be a constant number 25. The localization performance variation with noise variance is depicted in Figure 2. As noise variance increases, localization performance degrades in all LS, WLS, and TLS algorithms. The TLS algorithm outperforms the LS and WLS algorithms.

Figure 2

Localization errors versus noise variance (Gaussian case).

In the second simulation, the effect on estimation performance with different variance of perturbation is investigated. The variance of perturbation is set to be varied from 10 to 100 and sensors are deployed uniformly. The measurement noise variance is set to be 50. The localization performance variation with variance of perturbation is depicted in Figure 3. The TLS algorithm outperforms the LS and WLS significantly with high-level variance of perturbation.

Figure 3

Localization errors versus perturbation variance (Gaussian case).

The estimation performance of three algorithms is also investigated with different numbers of deployed nodes. Figure 4 shows the RMSEs versus the number of nodes. Fifty nodes are uniformly generated in the field. Localization starts by using five randomly selected nodes for each algorithm, followed by adding more nodes of five in a group until all fifty nodes are used. The number of FLOPS is considered to evaluate the algorithm computational complexity with variation of the number of nodes. Results are given in Figure 5 with 2-dimensional source location parameter and 5–50 nodes. It can be seen that LS required the fewest FLOPS while TLS required the most FLOPS with SVD of matrix. Although the estimation performance is improved with more nodes for all algorithms, the computation overhead is also increased. t is to show that LS method is the most computationally efficient, whereas WLS method is two-stage least square method and TLS method has singular value decomposition for matrix.

Figure 4

Localization errors versus number of nodes (Gaussian case).

Figure 5

Computation cost versus number of nodes.

5.3. Truncated Gaussian Case

Since the white and Gaussian assumptions are unrealistic in many applications, we consider the truncated Gaussian distribution for both measurement noise and sensor node location error in this case. Let X be a random variable with zero mean Gaussian distribution truncated in the interval $x \leq α σ$ ; its probability density function (pdf) is given by

p (x) = {\begin{cases} \frac{b}{\sqrt{2 p i} σ} (\exp \frac{- x^{2}}{2 σ^{2}} - \exp \frac{- {(α x)}^{2}}{2 σ^{2}}), & | x | \leq α σ, \\ 0, & | x | \geq α σ, \end{cases}

(33)

where b is a normalizing constant,

σ^{2}

is the variance, and α is the factor to extend the interval that the random variable X lies at.

Compared with the Gaussian case, similar results can be obtained and are shown in Figures 6, 7, and 8. The estimation performance for the WLS algorithm distinctly degrades significantly. This is because the weight matrix for this WLS method is calculated according to the Gaussian assumption for the measurements noise and sensor node location error. The proposed TLS algorithm still maintains good estimation performance.

Figure 6

Localization errors versus noise variance (truncated Gaussian case).

Figure 7

Localization errors versus perturbation variance (truncated Gaussian case).

Figure 8

Localization errors versus number of nodes (truncated Gaussian case).

6. Conclusions

In this paper, the TDOA model for source localization in sensor networks has been considered. The total least squares (TLSs) algorithm has been developed for location estimation of a stationary source with sensor location uncertainty in which the uncertainty of the sensor location has been formulated as a perturbation. The sensitivity of the TLS solution has also been analyzed to show the advantages of our proposed algorithm. Compared with the existing methods which need the Gaussian assumption for both measurements noise and sensor location error, the TLS approach does not depend on any assumed distribution of the noise and errors. Simulation results show the superior performance of the proposed method.

References

Hande

Yunus

Cem

Wireless healthcare monitoring with RFID-enhanced video sensor networks

International Journal of Distributed Sensor Networks 2010 2010 10

10.1155/2010/473037

473037

Xia

Dong

Sun

Network qos management in cyber-physical systems

Proceedings of the International Conference on Embedded Software and Systems Symposia (ICESS '08)

2008

IEEE

302 307

Chan

Hang

Ching

Exact and approximate maximum likelihood localization algorithms

IEEE Transactions on Vehicular Technology 2006 55 1 10 16

2-s2.0-32144457161

10.1109/TVT.2005.861162

Weinstein

Optimal source localization and tracking from passive array measurements

IEEE Transactions on Acoustics, Speech, and Signal Processing 1982 30 1 69 76

2-s2.0-0020090422

Schmidt

R. O.

Multiple emitter location and signal parameter estimation

IEEE Transactions on Antennas and Propagation 1986 34 3 276 280

2-s2.0-0022683359

Chen

Yao

Hudson

Source localization and beamforming

IEEE Signal Processing Magazine 2002 19 2 30 39

2-s2.0-0036504132

10.1109/79.985676

Huang

Benesty

Elko

Mersereati

Real-time passive source localization: a practical linear-correction least-squares approach

IEEE Transactions on Speech and Audio Processing 2001 9 8 943 956

2-s2.0-0035510568

10.1109/89.966097

Hahn

Tretter

Optimum processing for delay-vector estimation in passive signal arrays

IEEE Transactions on Information Theory 1973 19 5 608 614

2-s2.0-0015662189

Wax

Kailath

Optimum localization of multiple sources by passive arrays

IEEE Transactions on Acoustics, Speech, and Signal Processing 1983 31 5 1210 1218

2-s2.0-0020834101

10.

Cheung

Chan

A constrained least squares approach to mobile positioning: algorithms and optimality

Eurasip Journal on Applied Signal Processing 2006 2006 23

2-s2.0-33746582376

10.1155/ASP/2006/20858

20858

11.

Yang

Sun

Constrained total least-squares location algorithm using time-difference-of-arrival measurements

IEEE Transactions on Vehicular Technology 2010 59 3 1558 1562

2-s2.0-77949725975

10.1109/TVT.2009.2037509

5342476

12.

Friedlander

A passive localization algorithm and its accurancy analysis

IEEE Journal of Oceanic Engineering 1987 12 1 234 245

2-s2.0-0023254499

13.

Schau

H. C.

Robinson

A. Z.

“Passive source localization employing intersecting spherical surfaces from time-of-arrivaldifferences

IEEE Transactions on Acoustics, Speech, and Signal Processing 1987 35 8 1223 1225

2-s2.0-0023400148

14.

Smith

J. O.

Abel

J. S.

Closed-form least-squares source location estimation from range-difference measurements

IEEE Transactions on Acoustics, Speech, and Signal Processing 1987 35 12 1661 1669

2-s2.0-0023532499

15.

Chan

Y. T.

K. C.

Simple and efficient estimator for hyperbolic location

IEEE Transactions on Signal Processing 1994 42 8 1905 1915

2-s2.0-0028484308

10.1109/78.301830

16.

Gillette

M. D.

Silverman

H. F.

A linear closed-form algorithm for source localization from time-differences of arrival

IEEE Signal Processing Letters 2008 15 1 4

2-s2.0-67650179905

10.1109/LSP.2007.910324

17.

K. C.

Kovavisaruch

Source localization using TDOA and FDOA measurements in the presence of receiver location errors: analysis and solution

IEEE Transactions on Signal Processing 2007 55 2 684 696

2-s2.0-33847648428

10.1109/TSP.2006.885744

18.

Yang

Wang

Luo

Z. Q.

Efficient convex relaxation methods for robust target localization by a sensor network using time differences of arrivals

IEEE Transactions on Signal Processing 2009 57 7 2775 2784

2-s2.0-67650169434

10.1109/TSP.2009.2016891

19.

Kay

Fundamentals of Statistical Signal Processing: Estimation Theory 1993

Prentice Hall

20.

Renaux

Forster

Boyer

Larzabal

Unconditional maximum likelihood performance at finite number of samples and high signal-to-noise ratio

IEEE Transactions on Signal Processing 2007 55 5 2358 2364

2-s2.0-34247862091

10.1109/TSP.2007.893205

21.

Mada

K. K.

H. C.

Iyengar

S. S.

Efficient and robust EM algorithm for multiple wideband source localization

IEEE Transactions on Vehicular Technology 2009 58 6 3071 3075

2-s2.0-67549083452

10.1109/TVT.2009.2012495

22.

Theodor

Shaked

de Souza

C. E.

A game theory approach to robust discrete-time

H^{\infty}

-estimation

IEEE Transactions on Signal Processing 1994 42 6 1486 1495

2-s2.0-0028447708

10.1109/78.286964

23.

van Huffel

Vandewalle

The Total Least Squares Problem: Computational Aspects and Analysis 1991

Society for Industrial Mathematics

24.

Zhang

Matrix Analysis and Application 2004

Tsinghua University Press and Springer

25.

Markovsky

van Huffel

Overview of total least-squares methods

Signal Processing 2007 87 10 2283 2302

2-s2.0-34249825770

10.1016/j.sigpro.2007.04.004

26.

Golub

van Loan

Matrix Computations 1996

Baltimore, Md, USA

Johns Hopkins University Press

27.

Wedin

Perturbation theory for pseudo-inverses

BIT Numerical Mathematics 1973 13 2 217 232

2-s2.0-0000195992

10.1007/BF01933494

28.

Stewart

Error and perturbation bounds for subspaces associated with certain eigenvalue problems

SIAM Review 1973 15 4 727 764

29.

Davis

Kahan

W. M.

The rotation of eigenvectors by a perturbation. III

SIAM Journal on Numerical Analysis 1970 7 1 1 46

2-s2.0-0014751986

30.

Wedin

Perturbation bounds in connection with singular value decomposition

BIT 1972 12 1 99 111

2-s2.0-0002790288

10.1007/BF01932678

31.

Thompson

R. C.

Principal submatrices IX: interlacing inequalities for singular values of submatrices

Linear Algebra and Its Applications 1972 5 1 1 12

2-s2.0-0002103280