# Robust Localization Based on Constrained Total Least Squares in Wireless Sensor Networks

Authors: Qin Mao; Youming Li
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Source localization based on signal strength measurements has become very popular due to its wide applications. This paper focuses on differential received signal strength-based localization with model uncertainties in case of unknown transmit power. The error caused by the measurement noise and the reference power offset and the first-order approximate error generated in the process of DRSS receiving power linearization are merged into the constrained total least square regression matrix equation after linearization. The location optimization problem is formed by minimizing the influence of the errors. Based on the explicit closed form expressions of the first step vector and the second derivative matrix of the optimization problem, an iterative technique based on Newton’s method is proposed. The simulation results show that the root mean square error of the new algorithm is closer to the Cramér–Rao lower bound.


---

## Body

## 1. Introduction

With the rapid development of Internet of things, source localization [1, 2] is the basis and also the most important supporting technology in a wireless sensor network; it is also one of the hottest research directions.A wireless sensor network (WSN) is a kind of distributed network; its terminals are many low-cost sensor nodes. Source localization refers to the technology of determining the location of unknown target nodes through predeployed distributed sensor nodes with known location information. There are four common measurement techniques, time of arrival (TOA) [3], time difference of arrival (TDOA) [4], angle of arrival (AOA) [5], and received signal strength (RSS) [6, 7], and hybrid methods of two or more type of measurement techniques which are mentioned above [8, 9].By using the characteristic that the sound energy attenuation is inversely proportional to the square of the distance from the sound source, Li and Hu in [10] established a RSS model-based target source localization problem and proposed a least square implementation algorithm. Tarrio et al. [11] proposed a weighted least square (WLS) algorithm in which the influence of environmental factors on the sound source intensity is taken into account. In RSS model-based localization methods, the reference power between each anchor node and target node is known. However, in many application environments, the nodes between each anchor node and target node is not fully cooperative, so the assumption for the known reference power is difficult to be satisfied.DRSS is defined as the difference in logarithmic received power levels of a transmitting target at different anchor locations. Compared with the RSS model, the reference power is eliminated in the DRSS model-based method; therefore, DRSS model-based methods attract more attention. Lin et al. [12] proposed a two-step weighted least square method, which assumes the perfect knowledge of the model parameters. Sun et al. [13] discussed the DRSS model problem in the shadowing effects and measurement noise and proposed a WLS algorithm which converts the original localization problem into a quadratic constrained quadratic minimization problem.The least square estimation considers errors only in the observation matrix and adjusts observations in order to make the sum of its residuals minimum, while the total least square estimation considers errors in both the observation matrix and the data matrix, thereby minimizing the errors in both matrices. It is verified that the total least square estimation method is more robust than the least square estimation and has been used in many fields. Gupta and Dokmani [14] proposed a TLS framework for solving the phase retrieval problem when there are errors in the sensing vectors. Yang et al. [15] was based on the constrained total least square (CTLS) technique, and an iterative technique based on Newton’s method is utilized to give a numerical solution.In this paper, we reconsider the DRSS-based location problem and propose a robust estimation method which is based on the constrained total least square technique. In this method, firstly, the error caused by the measurement noise and the reference power offset and the first-order approximate error generated in the process of DRSS receiving power linearization are merged into the total least square regression matrix equation, and the location optimization problem is formed by minimizing the influence of the errors. Based on the explicit expressions of the first step vector and the second derivative matrix of the optimization problem, an optimization implementation algorithm based on Newton’s iteration is designed. Simulation results show that the new method is more robust to measurement noise and the number of anchor nodes than the compared algorithms.The rest of this paper consists of the following parts. In Section2, the DRSS-based source localization model and LS and TLS problem are described. In Section 3, the CTLS algorithm is developed. Simulation results are included in Section 4 to evaluate the performance of the CTLS algorithm. Finally, the conclusions are drawn in Section 5.


## 2. Model Introduction

### 2.1. DRSS-Based Source Localization Model

Consider a two-dimensional WSN withN sensors and one unknown source. Assume the locations of the ith sensor and the source are denoted by si∈R2 and x∈R2, respectively. The unknown source collects the RSS measurements from the sensors. The RSS measurement associated with the ith sensor can be expressed as (in dB)
(1)Pi=P0,i−10γlog10x−si2d0+χi,i=1,2,⋯,N,where P0,i is the received power related to the ith anchor node at the reference distance, γ is the path loss exponent, and the shadow effect χi is a Gaussian distributed random variable with zero mean and variance δχ2 and the reference distance d0=1m.Due to some unexpected power surges or system instabilities, we haveP0,i=P0¯+ΔP0,i with P0¯ the nominal transmit power, and we assume that ΔP0,i is a zero-mean Gaussian variable with variance δP02 . In this paper, instead of utilizing RSS measurements, we consider DRSS measurements for localization [16]. Considering the uncertain P0,i, the measurement model of DRSS can be obtained:
(2)Pi,1=−10γlog10x−si2x−s12+ΔP0,i,1+χi,1,i≠1,where Pi,1=Pi−P1 is the received power difference between the Pi and P1, ΔP0,i,1=ΔP0,i−ΔP0,1, and χi,1=χi−χ1 is the corresponding error difference.Although (2) is still nonconvex and nonlinear, the advantages of using DRSS are also obvious. At this time, the P0,i that needs to be estimated disappears. As an important special case, we assume that anchor nodes and target nodes in a two-dimensional plane are also easy to extend to three-dimensional or multidimensional space.


### 2.2. LS and TLS Problem

The total least square method is a generalization of the least square approximation method when the data in both the regression coefficient matrix and data vector is perturbed. When the error follows the zero-mean Gaussian distribution, the least square method is the maximum likelihood estimation of the linear regression model. However, the total least square method is a maximum likelihood estimation for solving overdetermined equations in the error in the variable model. TLS attempts to make the set of equations consistent using correction terms compensating for the noise components present in the regression coefficient matrix and data vector [15].As shown in Figure1, the least square method minimizes the square of the vertical distance from the data point to the fitting line, while the total least square method minimizes the square of the orthogonal distance from the data point to the fitting line. The figure shows that ○ represents the data point [ai, bi], × represents the approximate value, the straight line represents the fitting line, and the dotted line represents the error distance. It can be seen that the LS algorithm in Figure 1(a) only changes the second coordinate vector bi+Δbls in the data [ai, bi], while the TLS algorithm in Figure 1(b) only changes the two coordinate vectors ai+Δatls and bi+Δbtls in [ai, bi].Figure 1
Comparison of least square and total least square fitting.
(a)(b)Table 1
Complexity and average running time of different methods.
MethodCostTime (ms)LS88N+24210.11WLS123N+25730.172-step WLS [12]23N2+3N+17270.45CTLS18N2+37N+640.27


## 2.1. DRSS-Based Source Localization Model

Consider a two-dimensional WSN withN sensors and one unknown source. Assume the locations of the ith sensor and the source are denoted by si∈R2 and x∈R2, respectively. The unknown source collects the RSS measurements from the sensors. The RSS measurement associated with the ith sensor can be expressed as (in dB)
(1)Pi=P0,i−10γlog10x−si2d0+χi,i=1,2,⋯,N,where P0,i is the received power related to the ith anchor node at the reference distance, γ is the path loss exponent, and the shadow effect χi is a Gaussian distributed random variable with zero mean and variance δχ2 and the reference distance d0=1m.Due to some unexpected power surges or system instabilities, we haveP0,i=P0¯+ΔP0,i with P0¯ the nominal transmit power, and we assume that ΔP0,i is a zero-mean Gaussian variable with variance δP02 . In this paper, instead of utilizing RSS measurements, we consider DRSS measurements for localization [16]. Considering the uncertain P0,i, the measurement model of DRSS can be obtained:
(2)Pi,1=−10γlog10x−si2x−s12+ΔP0,i,1+χi,1,i≠1,where Pi,1=Pi−P1 is the received power difference between the Pi and P1, ΔP0,i,1=ΔP0,i−ΔP0,1, and χi,1=χi−χ1 is the corresponding error difference.Although (2) is still nonconvex and nonlinear, the advantages of using DRSS are also obvious. At this time, the P0,i that needs to be estimated disappears. As an important special case, we assume that anchor nodes and target nodes in a two-dimensional plane are also easy to extend to three-dimensional or multidimensional space.


## 2.2. LS and TLS Problem

The total least square method is a generalization of the least square approximation method when the data in both the regression coefficient matrix and data vector is perturbed. When the error follows the zero-mean Gaussian distribution, the least square method is the maximum likelihood estimation of the linear regression model. However, the total least square method is a maximum likelihood estimation for solving overdetermined equations in the error in the variable model. TLS attempts to make the set of equations consistent using correction terms compensating for the noise components present in the regression coefficient matrix and data vector [15].As shown in Figure1, the least square method minimizes the square of the vertical distance from the data point to the fitting line, while the total least square method minimizes the square of the orthogonal distance from the data point to the fitting line. The figure shows that ○ represents the data point [ai, bi], × represents the approximate value, the straight line represents the fitting line, and the dotted line represents the error distance. It can be seen that the LS algorithm in Figure 1(a) only changes the second coordinate vector bi+Δbls in the data [ai, bi], while the TLS algorithm in Figure 1(b) only changes the two coordinate vectors ai+Δatls and bi+Δbtls in [ai, bi].Figure 1
Comparison of least square and total least square fitting.
(a)(b)Table 1
Complexity and average running time of different methods.
MethodCostTime (ms)LS88N+24210.11WLS123N+25730.172-step WLS [12]23N2+3N+17270.45CTLS18N2+37N+640.27


## 3. Location Algorithm Development

In this section, based on the DRSS measurement model, the measurement errorsχi,1 and the reference power errors ΔP0,i,1 in the regression coefficients matrix are considered; (2) can be transformed into
(3)x−si22⋅Pi,1′−ΔPi,1′=x−s122,where Pi,1′=10Pi,1/5γ and ΔPi,1′ can consist of ΔP0,i,1 and χi,1 by utilizing Taylor’s formula, i.e., ΔPi,1′≈Pi,1′⋅ln10⋅ΔP0,i,1+χi,1/5γ. Then, unfold the Euclidean norm in (3).
(4)2s1Tx−2Pi,1′−ΔPi,1′siTx+Pi,1′−ΔPi,1′−1x22=s122−si22Pi,1′−ΔPi,1′.It can be written in matrix form as shown in(5)AX=b,where A=A0+ΔA, b=b0+Δb,
(6)X=xx22,A0=⋮⋮2s1T−2Pi,1′siTPi,1′−1⋮⋮,b0=⋮s122−si22Pi,1′⋮,ΔA=⋮⋮2ΔPi,1′siT−ΔPi,1′⋮⋮,Δb=⋮si22ΔPi,1′⋮.In such a case, due to the noise components in matrixA and b, (5) is usually inconsistent. However, in an ideal situation, DRSS measurements are free of noise. We have
(7)A0X=b0.The standard LS solution which will be used as an initial value in the proposed iteration algorithm is(8)x0=argminX∧AX∧−bTAX∧−b=ATA−1ATb.The superscriptT represents the transposition of the matrix. It is worth noting that both matrix A and vector b have errors ΔA and Δb, which do not meet LS expectations. In DRSS models, matrix ΔA and vector Δb are caused by ΔPi,1′. Thus, ΔA and Δb are correlated evidently. The algebraic correlation relationship between them could be taken into account. Therefore, the CTLS technique is very suitable for this situation compared with the TLS technique. The CTLS technique suppresses the perturbation of the matrix; i.e., the CTLS technique is closer to the undisturbed subspace. Next, we will expand the process of the CTLS location algorithm. From (5) and (7),
(9)AX−b=ΔAX−Δb=Gn,where
(10)G=−x−s2220−x−s322⋱0−x−sN22,n=ΔP2,1′ΔP3,1′⋮ΔPN,1′.Now, the CTLS algorithm could be formulated as [17]
(11)minn,θn22s.t.AX−b=Gn.The error vector is expressed as(12)n=G−1AX−b.By substituting (12) into (11), we minimize the objective function and rewrite it as the objective function n2 with target node location X as the independent variable.
(13)FX=AX−bTGGT−1AX−b.In this way, the original CTLS problem (11) is transformed into the following unconstrained optimization problem:
(14)minXAX−bTGGT−1AX−b.In the following, we provide an iterative implementation algorithm based on Newton’s method for solving problem (14). From (5), we know that X is a vector composed of x and x22; FX can be expressed as Fx.
(15)FX=AX−bTGGT−1AX−b=A2x+A3x22−bTGGT−1A2x+A3x22−b=Fx.Among them,A2A3=A and A2 and A3 represent the first two columns and the last column of matrix A, respectively. It can be found that Fx is still a nonlinear function after transformation. Numerical algorithms may be adopted to solve these nonlinear equations. One widely used numerical method is Newton’s method. We expand the algorithm process of Newton’s method. Firstly, the second-order Taylor series expansion of Fx can be expressed as
(16)Fx≈Fx0+x−x0T∂Fx0∂x+12x−x0T∂2Fx0∂x∂xTx−x0.The necessary condition for minimizingFx is that ∂Fx/∂x=0.
(17)∂Fx∂x=α+Ψx−x0=0,where α=∂Fx0/∂x and Ψ=∂2Fx0/∂x∂xT; we will calculate α and Ψ to obtain numerical solution. For simplicity of expression, using β=A2x+A3xTx−b, μ=GGT−1β is an intermediate variable. It can be obtained by deriving x from Fx.
(18)∂Fx∂x=∂βT∂xμ+βT∂μ∂x=2Θμ−22x−2siμTG1GTμ,where Θ=A2T+2xA3T and G1=IN−1. And then, derive xT from ∂Fx/∂x.
(19)∂∂xT∂Fx∂x=4A3TμI2+2ΘΦΘT−22x−2siμTΩΦΘT+2ΘΦΩμ2x−2siT+22x−2si2x−2siTμTΩΦΩ−G1G1Tμ,where Φ=GGT−1 and Ω=G1GT+GG1T; we need to meet the demand.
(20)α=∂F∂xx=x0,Ψ=∂2F∂x∂xTx=x0.If the second derivative of the objective function is continuous, then the objective function has second-order convergence, and Newton’s method can be used to give the solution.(21)x=x0−Ψ−1α.The advantage of Newton’s method is that it is accurate enough after iteration. However, the convergence of iteration cannot be guaranteed. In DRSS-based localization problems, it is easy to check whether the above convergence converges or not. After each iteration, the Frobenius norm of the correction vector is calculated and compared with the previous step. After several iterations, if the ratio to the estimator is much smaller than the estimator, the process is converging. If a good initial point is chosen, there will be less nonconvergence.In summary, the proposed CTLS process is basically as follows.Algorithm 1: Prototype of the proposed estimator.
1.Initialization: Calculate the initial pointx0;2.Loop: Solve Ψ, α by using the (20);Let k =0; Using thexk+1=xk−Ψ−1α to calculate the updated valuexk+1;Ifxk+1−xk≤ξ, continue. Otherwise go to back to Loop;Returnxk+1;


## 4. Simulation Results

In this section, Monte Carlo simulations have been provided to evaluate the performance of the proposed algorithm DRSS-based CTLS location algorithm by comparing with WLS and 2-step WLS algorithm which implicitly exploit the relationship between the extra variable and source location [12]. And WLS method is a method of whitening noise term based on the LS method.The root mean square error (RMSE) is used to evaluate the performance of the mentioned method, which is defined as(22)RMSE=1Mc∑i=1Mcsi−si∧2,where Mc is the number of Monte Carlo runs, si∧ is the estimate of the ith real target location si, and Mc=3000 is used in the following simulation.Scenario 1. In this scenario, we consider one target and ten anchor nodes, the target nodes are randomly distributed in a square area of 100×100m2, the anchor node placement is shown in Figure 2, and their locations are 50,50, −26,30, −8,40, 16,18, 36,6, 24,−36, −12,−24, −20,0, 15,−15, and −30,−40. Because it is well known that the location accuracy is affected by the reciprocal position of the target and anchor sensors, if we randomly set the position of anchor nodes, there will be a minimum probability that two anchor nodes are too close, so the mentioned methods will produce extreme outliers, thus affecting the evaluation of the performance. So we just considered the scenario where the anchor sensors were fixed. Meanwhile, the path loss exponent is 4, and the noise which consists of measurement noise and the reference power error follows the zero-mean Gaussian distribution ΔPi,1′∼N0,δ2. The noise variation range is 0,4.Figure 2
Anchor node placement.Figure3 shows the RMSE versus the noise variation. As the noise standard deviation increases, several algorithms show an upward trend, which is in line with our expectations. Compared with several methods with similar complexity, it can be found that the performance of the CTLS algorithm is slightly better than that of the two-step weighted least square method (2-step WLS) in [12] especially in the case of small error, and it is closer to the Cramér–Rao lower bound. However, once when the error is larger, this kind of low complexity algorithm cannot compare with the current popular algorithm, such as SDP method, but we observe that CTLS is more robust to noise than other methods which have similar complexity.Figure 3
Performance comparison of different estimators under different noise conditions.Scenario 2. In this scenario, we consider one target and several anchor nodes, the target nodes are randomly distributed in a square area of 100×100m2, and take the scenario 1’s anchor node location in turn. The path loss exponent is 4, and the noise follows the zero-mean Gaussian distribution ΔPi,1′∼N0,0.1.Figure4 shows the RMSE versus the number of anchor nodes. It can be known that under the same error condition, that is, δ2=0.1, by comparing the root mean square error obtained by CTLS and other methods, it can be found that when the number of anchor nodes N is 10, the performance of CTLS is significantly better than that of other methods. When the number of anchor nodes decreases, CTLS still maintains advantages over other methods.Figure 4
Performance comparison of different estimators under different numbers of anchor nodes.We now calculate the computational complexity of the different methods [18] as Table 1 shows. It is easy to derive that the complexity of the LS and WLS is Od2N where d presents the dimension. As for the 2-step WLS and CTLS, their complexity is Od2N2 considering that the extra cost mainly comes from the step in (21). The algorithms have been implemented in MATLAB R2016a on a computer (processor 2.3 GHz Intel Core i7, memory 8 GB 1600 MHz DDR3).


## 5. Conclusions

In practical applications, the localization algorithm needs to have sufficient accuracy and easy-to-implement characteristics. In this paper, we propose a DRSS-based CTLS algorithm. The error caused by the measurement noise and the reference power offset and the first-order approximate error generated in the process of DRSS receiving power linearization are merged into the constrained total least square regression matrix equation after linearization. The location optimization problem is formed by minimizing the influence of the errors. Based on the explicit closed form expressions of the first step vector and the second derivative matrix of the optimization problem, an iterative technique based on Newton’s method is proposed. The simulation results show that CTLS has better localization accuracy than other least square methods, so it will be more accurate in wide range of applications.When further considering the more complicated situation, due to the complexity and change of the environment, including the uncertain or completely unknown anchor node location, the uncertain and completely unknown path loss exponent is the research direction worthy of extension and attempt.



---

*Source: 4101571-2022-03-14.xml*