RSS Localization Algorithm Based on Nonline of Sight Identification for Wireless Sensor Network

Abstract

Localization is a key issue for wireless sensor network. The traditional localization methods achieve high location accuracy using received signal strength (RSS) in line of sight (LOS) environment. But the localization accuracy degrades significantly in nonline of sight (NLOS) environment. So the localization in NLOS environment is one of the most challenging for wireless sensor network. In this paper, we propose an RSS based localization algorithm in NLOS environment. A NLOS identification algorithm is firstly proposed. This algorithm does not need the parameters of the NLOS in prior. Then we correct the NLOS measurements by subtracting the mean of NLOS errors. Finally, the Kalman filter is employed to mitigate the process noise. In simulations, we demonstrate that the proposed algorithm achieves higher localization accuracy compared with other methods.

1. Introduction

The advancement in low-power circuit design, efficient wireless communication, and low cost sensor have made the wireless sensor network (WSN) an appropriate solution for many application requirements [1]. WSN has been developed for many applications such as battle field surveillance, environmental monitoring, and target tracking. The localization problem is one of the most key technologies for WSN [2].

In the sensor network, the beacon nodes have the knowledge of their own location information through global positioning systems (GPS) or human intervention. The remaining nodes (called unknown nodes) have to determine their positions based on anchor nodes. The unknown node localization can be realized by estimating the distance/angle between the beacon node and unknown node. The most common methods of measurement are received signal strength (RSS) [3], time of arrival (TOA) [4], angle of arrival (AOA) [5], and time difference of arrival (TDOA) [6]. TDOA and AOA methods are energy consuming resolution and they require extra hardware. TOA needs the high precision clock to achieve clock synchronization. So the above three methods are not suitable for low configured sensor node. As an inexpensive approach, RSS has established the mathematical model on the basis of path loss attenuation with distance, and it requires relatively lower configuration and energy. So we exploit the RSS method to measure the distance between the beacon node and unknown node. Most of the methods require that the signal travels through the line of sight (LOS) path. If the LOS path cannot be obtained, that is, in the nonline of sight (NLOS) condition, a large localization error is achieved. The NLOS propagation has been known as the major source of localization errors.

The NLOS localization problem can be categorized into two branches: NLOS identification and NLOS mitigation. The principle of the NLOS identification methods attempts to detect the propagation condition of the sensor node. Borras et al. propose a binary hypothesis test method [7] to identify the NLOS measurements. An iterative minimum residual (IMR) method which identifies the NLOS nodes has been proposed [8]. This method can significantly improve the location estimation performance in NLOS environment. Since the IMR method needs a lot of calculation for NLOS identification, a low complexity NLOS identification method which uses minimum subset is proposed [9]. A confidence criterion as the zero mean Gaussian assumption of the innovation is defined in this method in [10]. The pseudo-measured position will satisfy the confidence criterion if it is calculated from LOS environment. Otherwise, the pseudo-measured position is calculated from NLOS environment. Least squares support vector machine classifier [11] is employed to distinguish LOS/NLOS propagation and further mitigate the ranging errors in NLOS conditions. In [12], the propagation delay and signal strength measurements are firstly used to identify the LOS and objective-relative NLOS (strong NLOS). Then the constrained expectation maximum algorithm is employed to identify the LOS and sea-related NLOS (soft NLOS).

When the propagation condition has been identified, the next step is to mitigate the NLOS error and improve the localization accuracy. In [13], a novel linear programming approach is proposed to mitigate the NLOS error for sensor node localization. The LOS measurements are used to define the objective function and the NLOS measurements are used to restrict the feasible region for the linear program. And it shows that the NLOS measurements can be used to improve the localization accuracy without incurring performance degradation due to bias errors. Two iterative algorithms are developed based on expectation maximization criterion and joint maximum a posteriori maximum likelihood estimator [14]. These two algorithms approximate the ideal maximum likelihood estimation of the unknown parameters with low computational complexity. In [15], the expectation of NLOS error is estimated to correct the measurement. The NLOS error is removed by subtracting the expectation of NLOS errors. A redesigned form of the classical multidimensional scaling (MDS) algorithm [16] is proposed to handle the NLOS localization problem. A modified kernel matrix in MDS algorithm is used to allow for both distance and angle information to be processed algebraically and simultaneously. A robust multilateration algorithm [17] is introduced in NLOS environment. This algorithm is robust in comparison with traditional least squares multilateration. However, the performance of this method is severely affected by the number of NLOS measurements.

In this paper, we propose a novel RSS based localization algorithm in NLOS condition for wireless sensor network. A selective residual test based NLOS identification algorithm is firstly proposed. Then the NLOS measurements are corrected and the position of unknown node is localized. Finally the Kalman filter method is used to mitigate the process noise when the unknown node is moving in the field.

This paper is organized as follows. In Section 2 we introduce range estimation model. The proposed algorithm is presented in Section 3. Some simulation results are presented in Section 4. The conclusions are given in Section 5.

2. Ranging Model

We consider a two-dimensional sensor field, where N beacon nodes and one unknown node exist. The position of beacon nodes is $[x_1,y_1;x_2,y_2;\dots ;x_N,y_N]$ , and the position of unknown node is $[x,y]$ . The true distance between the nth beacon node and unknown node is described as

$$\begin{array}{cc}& d_n=\sqrt{{\left(x_n-x\right)}^{\mathrm{2}}+{\left(y_n-y\right)}^{\mathrm{2}}}.\end{array}$$

(1)

In this paper, we employ the log-normal shadowing model to describe the relationship between the RSS and distance [18, 19]. The beacon node transmits the radio signal to the unknown node. The unknown node measures the RSS. The measured RSS $P{L}_n$ from nth beacon node can be expressed as

$$\begin{array}{cc}& P{L}_n=P{L}_{\mathrm{0}}-\mathrm{10}{n}_{\text{los}/\text{nlos}}\text{lo}{\text{g}}_{\mathrm{10}}\left(\frac{d_m}{d_{\mathrm{0}}}\right)+S_{\text{los}/\text{nlos}},\end{array}$$

(2)

where $P{L}_{\mathrm{0}}$ is the received signal strength at reference distance of $d_0$ meters. $d_0$ is set to be 1 m. $n_{\text{los}}$ and $n_{\text{nlos}}$ are the path loss exponents in LOS and NLOS conditions, respectively, the value within the range from 1.6 to 1.8 in LOS environment and within the range from 4 to 6 in NLOS environment. $S_{\text{los}}~N(\mathrm{0},{\sigma }_{\mathrm{1}}^{\mathrm{2}})$ is the LOS measurement noise modeled as zero mean white Gaussian with variance ${\sigma }_{\mathrm{1}}^{\mathrm{2}}$ . $S_{\text{nlos}}~N({\mu }_{\mathrm{2}},{\sigma }_{\mathrm{2}}^{\mathrm{2}})$ is the measurement noise in NLOS environment, and ${\sigma }_{\mathrm{2}}>{\sigma }_{\mathrm{1}}$ . These parameters could be obtained in an environment through simulation or experiment.

From (1), the estimated range between the nth beacon node and unknown node can be expressed as

$$\begin{array}{l}{\widehat{d}}_n={\mathrm{10}}^{(\mathrm{10}{n}_{\text{los}/\text{nlos}}\text{lo}{\text{g}}_{\mathrm{10}}{d}_m+S_{\text{los}/\text{nlos}})/\mathrm{10}{n}_{\text{los}/\text{nlos}}}\\ \hspace{1em}=d_n·\mathrm{1}{\mathrm{0}}^{S_{\text{los}/\text{nlos}}/\mathrm{10}{n}_{\text{los}/\text{nlos}}}\\ \hspace{1em}=d_n+\left(\mathrm{1}{\mathrm{0}}^{S_{\text{los}/\text{nlos}}/\mathrm{10}{n}_{\text{los}/\text{nlos}}}-\mathrm{1}\right)d_n.\end{array}$$

(3)

We can approximately obtain that [16] $N_{\text{los}}=(\mathrm{1}{\mathrm{0}}^{S_{\text{los}}/\mathrm{10}{n}_{\text{los}}}-\mathrm{1})d_m~N(\mathrm{0},{\sigma }_{\text{los}}^{\mathrm{2}})$ under LOS environment and $N_{\text{nlos}}=(\mathrm{1}{\mathrm{0}}^{S_{\text{nlos}}/\mathrm{10}{n}_{\text{nlos}}}-\mathrm{1})d_m~N({\mu }_{\text{nlos}},{\sigma }_{\text{nlos}}^{\mathrm{2}})$ under NLOS environment.

So the estimated range can be rewritten as

$$\begin{array}{cc}& {\widehat{d}}_n=d_n+N_{\text{los}/\text{nlos}},\end{array}$$

(4)

where $N_{\text{los}}$ is the white Gaussian noise, whose distribution is normal probability distribution function $N(\mathrm{0},{\sigma }_{\text{los}}^{\mathrm{2}})$ with zero mean and variance of the measurement noise ${\sigma }_{\text{los}}^{\mathrm{2}}$ . $N_{\text{nlos}}$ is modeled as the nonzero mean Gaussian noise, that is, $N({\mu }_{\text{nlos}},{\sigma }_{\text{nlos}}^{\mathrm{2}})$ .

3. The Proposed Algorithm

In this section, we describe the proposed algorithm in detail. The running processing of the network is as follows. The beacon nodes emit the radio signal in sequence, and the unknown node receives the signal and measures the received signal strength (RSS). The RSS is converted into distance. Then the unknown node identifies the propagation condition. The measurements which contain the NLOS error will be corrected. The unknown node estimates its position using the least square method.

As shown in Figure 1, the propagation condition identification algorithm is proposed. This algorithm consists of two steps: grouping the measurements, Gauss-Newton algorithm based initial estimation, and selective residual test based NLOS identification algorithm. The Gauss-Newton algorithm is used to estimate the initial position of each group. The residual test is employed to identify the propagation condition of beacon node. Then we correct the NLOS measurements and localize the position of unknown node using the least square method. Finally, the Kalman filter method is employed to discard the large process error.

Figure 1

The flowchart of the proposed algorithm.

3.1. Grouping the Measurements

Since the localization in two-dimensional fields needs at least 3 measurements, so measurements are divided into several subgroups. We have $M={\sum }_{i=\mathrm{3}}^N{C}_N^i$ different subgroups of measurements which are used together with the position of the corresponding beacon nodes to localization in the next subsection.

3.2. Gauss-Newton Algorithm Based Initial Estimation

For each subgroup, we employ the Gauss-Newton algorithm based localization method to estimate the initial results. We assume that the measurements are obtained in LOS environment. According to (4), the objective function for initial estimation is established for any subgroup as follows:

$$\begin{array}{cc}& \widehat{\theta }=\arg \underset{\theta }{\max }\hspace{0.17em}p\left(\widehat{d}\hspace{0.17em}|\hspace{0.17em}\theta \right),\end{array}$$

(5)

where $p(·)$ is the likelihood function, $\widehat{d}={[{\widehat{d}}_{\mathrm{1}},{\widehat{d}}_{\mathrm{2}},\dots ,{\widehat{d}}_S]}^T$ is the vector that consists of the estimated ranges between the beacon nodes and unknown node, and S is the number of measurements for the subgroup.

The likelihood function can be expressed as

$$\begin{array}{cc}& p\left(\widehat{d}\hspace{0.17em}|\hspace{0.17em}\theta \right)=\frac{\mathrm{1}}{{{\displaystyle \prod }}_{i=\mathrm{1}}^S{\left(\mathrm{2}\pi {\sigma }_{\text{los}}^{\mathrm{2}}\right)}^{\mathrm{1}/\mathrm{2}}}{e}^{-\left(\mathrm{1}/\mathrm{2}\right){\sum }_{i=\mathrm{1}}^S\left(\mathrm{1}/{\sigma }_{\text{los}}^{\mathrm{2}}\right){({\widehat{d}}_i-d_i(\theta \left)\right)}^{\mathrm{2}}}.\end{array}$$

(6)

The negative log-likelihood function of (5) can be written as

$$\begin{array}{cc}& \widehat{\theta }=\arg \underset{\theta }{\min }J\left(\theta \right),\end{array}$$

(7)

where $J(\theta )={\sum }_{i=\mathrm{1}}^S{({\widehat{d}}_i-d_i(\theta ))}^{\mathrm{2}}={\sum }_{i=\mathrm{1}}^S{({\delta }_i(\theta ))}^{\mathrm{2}}$ .

We can obtain the maximum likelihood parameter estimation of θ by minimizing $J(\theta )$ . The common method for solving nonlinear least squares problem is Newton's method [20]. But it requires the inversion of the full Hessian matrix. In this paper, we employ the Gauss-Newton algorithm to solve this problem [21]. The key step in Gauss-Newton algorithm is to find the tth search direction ${\epsilon }^t$ , and it is defined as

$$\begin{array}{cc}& {\epsilon }^t=-\left(L^T\left({\theta }^t\right)L\left({\theta }^t\right)\right)L^T\left({\theta }^t\right)\mathit{\delta }\left({\theta }^t\right),\end{array}$$

(8)

where $\mathit{\delta }({\theta }^t)=[{\delta }_{\mathrm{1}}({\theta }^t),{\delta }_{\mathrm{2}}({\theta }^t),\dots ,{\delta }_S({\theta }^t)]$ , ${(L)}_{ij}=\partial {\delta }_i({\theta }^t)/\partial {\theta }_j^t$ .

The steps of this algorithm are defined as follows.

Step 1.

Choose an initial solution ${\theta }^{\mathrm{0}}$ .

Step 2.

Compute the search direction according to (8).

Step 3.

Compute ${\theta }^{t+\mathrm{1}}={\theta }^t+{\epsilon }^t$ .

Step 4.

Repeat Steps 2 and 3 until convergence.

After the iteration, initial estimation for each subgroup can be obtained.

3.3. Selective Residual Test Based NLOS Identification Algorithm

If the propagation condition can be accurately identified, the localization accuracy can be improved significantly. In this subsection, we introduce the selective residual test based NLOS identification algorithm. This algorithm is independent of the statistical model of NLOS error. We assume that more than half of the measurements are obtained in LOS environment. Without loss of generality, we consider a common scenario, where 7 ( $N=7$ ) beacon nodes are randomly deployed in the field. And number of LOS measurements is $D(D\ge 4)$ . We estimate the value of D and identify the LOS measurement through the selective residual test method.

We can obtain 99 ( ${\sum }_{i=\mathrm{3}}^{\mathrm{7}}{C}_{\mathrm{7}}^i=\mathrm{99}$ ) subgroups of the measurements when $N=7$ as described in Section 3.1. The index set of each subgroup is $\{S_h\hspace{0.17em}|\hspace{0.17em}h=\mathrm{1,2}\dots ,\mathrm{99}\}$ . 99 estimated positions for the subgroups can be obtained according to the localization method in Section 3.2, and the estimated position is denoted by $\widehat{\theta }(h)$ , $h=1,\dots ,99$ . $\widehat{\theta }(\mathrm{99})$   is the estimated position from $C_{\mathrm{7}}^{\mathrm{7}}$ subgroup and it is the optimal estimated position in all the estimated positions.

The square of the normalized residuals is defined as follows:

$$\begin{array}{cc}& {\chi }_x^{\mathrm{2}}\left(h\right)=\frac{{\left[\widehat{x}\left(h\right)-\widehat{x}\left(\mathrm{99}\right)\right]}^{\mathrm{2}}}{B_x\left(h\right)},\\ {\chi }_y^{\mathrm{2}}\left(h\right)=\frac{{\left[\widehat{y}\left(h\right)-\widehat{y}\left(\mathrm{99}\right)\right]}^{\mathrm{2}}}{B_y\left(h\right)},\hspace{1em}h=\mathrm{1},\dots ,\mathrm{98},\end{array}$$

(9)

where $B_x(h)$ and $B_y(h)$ are the approximation of the CRLB of $\widehat{\theta }(h)$ .

In order to compute $B_x(h)$ and $B_y(h)$ , we firstly compute the Fisher information matrix as follows:

$$\begin{array}{cc}& I\left(\theta \right)=\frac{\mathrm{1}}{{\sigma }_i^{\mathrm{2}}}\left[\begin{array}{cc}{\displaystyle \sum }_{i\in S_h}\frac{{\left(x-x_i\right)}^{\mathrm{2}}}{d_i^{\mathrm{2}}}& {\displaystyle \sum }_{i\in S_h}\frac{\left(x-x_i\right)\left(y-y_i\right)}{d_i^{\mathrm{2}}}\\ {\displaystyle \sum }_{i\in S_h}\frac{\left(x-x_i\right)\left(y-y_i\right)}{d_i^{\mathrm{2}}}& {\displaystyle \sum }_{i\in S_h}\frac{{\left(y-y_i\right)}^{\mathrm{2}}}{d_i^{\mathrm{2}}}\end{array}\right].\end{array}$$

(10)

Since the true position θ is unknown, we replace $\widehat{\theta }(\mathrm{99})$   with θ in this paper. Then we find the inverse of Fisher information matrix, that is, $I^{-\mathrm{1}}(\theta )$ . The (1,1) and (2,2) elements of $I^{-\mathrm{1}}(\theta )$ are $B_x(h)$ and $B_y(h)$ , respectively.

Since $D=7$ , 7 measurements of beacon nodes are obtained in LOS environment. So

$$\begin{array}{cc}& \frac{\widehat{x}\left(h\right)-\widehat{x}\left(\mathrm{99}\right)}{\sqrt{B_x\left(h\right)}},\hspace{1em}\hspace{1em}\frac{\widehat{y}\left(h\right)-\widehat{y}\left(\mathrm{99}\right)}{\sqrt{B_y\left(h\right)}}\end{array}$$

(11)

is approximate standard normal distribution, that is, $N(\mathrm{0,1})$ . Therefore, (9) obey an approximate central Chi square ( ${\chi }^2$ ) distribution of one degree of freedom. However, due to estimated bias that will exist in $\widehat{\theta }(\mathrm{99})$   and some of $\widehat{\theta }(h)$ in NLOS environment, (9) will obey noncentral Chi square distribution when the measurements contain the NLOS error.

According to [22], we set the threshold $\text{TH}=2.71$ . Since ${\chi }_x^{\mathrm{2}}(h)$ obeys an approximate central Chi square distribution of one degree of freedom, the empirical probability and theoretical probability are 0.02 and 0.07, respectively, when ${\chi }_x^{\mathrm{2}}(h)>\mathrm{2.71}$ . In order to prevent misjudgment caused by excessive restrictions, we select the theoretical probability to identify the LOS measurements. When $D=7$ , the percentage of ${\chi }_x^{\mathrm{2}}(k)>\text{TH}$ should be less than or equal to 7%. If the percentage of ${\chi }_x^{\mathrm{2}}(k)>\text{TH}$ is larger than 7%, it means at least one measurement consists of NLOS error and $D<7$ . ${\chi }_y^{\mathrm{2}}(h)$ is analyzed in the same way.

We set number of ${\chi }_x^{\mathrm{2}}(h)>\text{TH}$ and ${\chi }_y^{\mathrm{2}}(h)>\text{TH}$ to l. If $l\le \mathrm{0.07}\times \mathrm{98}\times \mathrm{2}\approx \mathrm{14}$ , then $D=7$ . Otherwise at least one measurement consists of NLOS error when $l>\mathrm{14}$ . Then we should identify the condition of $D=6$ .

3.3.1. Identify If $D=6$

We construct 7-measurement set $\{Z_m\hspace{0.17em}|\hspace{0.17em}m=\mathrm{1,2},\dots ,7\}$ which consists of 6 measurements values in each set to identify if $D=6$ . So we can obtain ${\sum }_{i=\mathrm{3}}^{\mathrm{6}}{C}_{\mathrm{6}}^i=\mathrm{42}$ estimated positions $\widehat{\theta }(h)$ , $h=\mathrm{1},\dots ,\mathrm{42}$ , according to the localization method in Section 3.2. ${\chi }_x^{\mathrm{2}}(h)$ and ${\chi }_y^{\mathrm{2}}(h)$ can be obtained according to (9). We can identify if $D=6$ according to the following two steps.

Step 1.

If $l\le \mathrm{0.07}\times \mathrm{41}\times \mathrm{2}\approx \mathrm{6}$ , then $D=6$ . If more than one set satisfy $l\le \mathrm{6}$ , then the measurements in the set which owns the minimum value l are obtained in LOS environment; that is, the six measurements are LOS propagation.

Step 2.

If $l>6$ in all the sets, then $D<6$ . And at least one measurement in the set contains the NLOS error. The set which owns the maximum value l is denoted by $Z_i$ . The measurement which does not exist in $Z_i$ is identified as LOS measurement and adds this measurement to LOS set ${\delta }_a$ . The set which owns the minimum value l is denoted by $Z_j$ . The measurement which does not exist in $Z_j$ is identified as NLOS measurement and adds this measurement to NLOS set ${\delta }_b$ . According to this step, we can identify 2 propagation conditions in 7 measurements.

3.3.2. Identify if $D=5$

Since 2 propagation conditions have been identified in the 7 measurements, then we identify if $D=5$ . We firstly construct $C_{\mathrm{5}}^{\mathrm{4}}=\mathrm{5}$ -measurement set $\{Z_m\hspace{0.17em}|\hspace{0.17em}m=\mathrm{1,2},\dots ,5\}$ which consists of 4 measurements values in each set. So we can obtain ${\sum }_{i=\mathrm{3}}^{\mathrm{5}}{C}_{\mathrm{5}}^i=\mathrm{16}$ estimated positions $\widehat{\theta }(h),h=\mathrm{1},\dots ,\mathrm{16}$ , according to the localization method in Section 3.2. ${\chi }_x^{\mathrm{2}}(h)$ and ${\chi }_y^{\mathrm{2}}(h)$ can be obtained according to (9). Finally we identify if $D=5$ according to Steps 1 and 2 in Section 3.3.1.

Repeat these steps until all the propagation conditions of the measurements are identified. The flowchart of the selective residual test based NLOS identification algorithm is described in Figure 2.

Figure 2

The flowchart of the selective residual test based NLOS identification algorithm.

3.4. Measurements Correction and Least Square Localization

After identifying the propagation conditions, we can obtain the LOS measurements set ${\delta }_a=[{\widehat{d}}_{\text{los},\mathrm{1}}\hspace{0.5em}{\widehat{d}}_{\text{los},\mathrm{2}}\hspace{0.5em}\cdots \hspace{0.5em}{\widehat{d}}_{\text{los},a}]$ and their corresponding positions of beacon node are denoted by $[x_{\mathrm{1}}^{\prime },y_{\mathrm{1}}^{\prime };x_{\mathrm{2}}^{\prime },y_{\mathrm{2}}^{\prime },\dots ,x_a^{\prime },y_a^{\prime }]$ . The NLOS measurement set ${\delta }_b=[{\widehat{d}}_{\text{nlos},a+\mathrm{1}}\hspace{0.5em}{\widehat{d}}_{\text{nlos},a+\mathrm{2}}\hspace{0.5em}\cdots \hspace{0.5em}{\widehat{d}}_{\text{nlos},N}]$ and their corresponding positions of beacon node are denoted by $[x_{a+\mathrm{1}}^{\prime },y_{a+\mathrm{1}}^{\prime };x_{a+\mathrm{2}}^{\prime },y_{a+\mathrm{2}}^{\prime },\dots ,x_N^{\prime },y_N^{\prime }]$ . Then the NLOS measurements which contain the NLOS error are corrected by subtracting the mean of NLOS errors:

$$\begin{array}{cc}& {\tilde{d}}_{\text{nlos},i}={\widehat{d}}_{\text{nlos},i}-{\mu }_{\text{nlos}},\hspace{1em}i=a+\mathrm{1},a+\mathrm{2},\dots ,N.\end{array}$$

(12)

We establish the following equation set:

$$\begin{array}{cc}& {\left(x_{\mathrm{1}}^{\prime }-\widehat{x}\right)}^{\mathrm{2}}+{\left(y_{\mathrm{1}}^{\prime }-\widehat{y}\right)}^{\mathrm{2}}={\left({\widehat{d}}_{\text{los},\mathrm{1}}\right)}^{\mathrm{2}}\\ ⋮\\ {\left(x_a^{\prime }-\widehat{x}\right)}^{\mathrm{2}}+{\left(y_a^{\prime }-\widehat{y}\right)}^{\mathrm{2}}={\left({\widehat{d}}_{\text{los},a}\right)}^{\mathrm{2}}\\ {\left(x_{a+\mathrm{1}}^{\prime }-\widehat{x}\right)}^{\mathrm{2}}+{\left(y_{a+\mathrm{1}}^{\prime }-\widehat{y}\right)}^{\mathrm{2}}={\left({\tilde{d}}_{\text{nlos},a+\mathrm{1}}\right)}^{\mathrm{2}}\\ ⋮\\ {\left(x_N^{\prime }-\widehat{x}\right)}^{\mathrm{2}}+{\left(y_N^{\prime }-\widehat{y}\right)}^{\mathrm{2}}={\left({\tilde{d}}_{\text{nlos},N}\right)}^{\mathrm{2}}.\end{array}$$

(13)

The linear equation $AY=B$ represents the above equation, where A and B are given by

$$\begin{array}{cc}& A=\mathrm{2}\left[\begin{array}{cc}\left(x_{\mathrm{1}}^{\prime }-x_{\mathrm{2}}^{\prime }\right)& \left(y_{\mathrm{1}}^{\prime }-y_{\mathrm{2}}^{\prime }\right)\\ \left(x_{\mathrm{1}}^{\prime }-x_{\mathrm{3}}^{\prime }\right)& \left(y_{\mathrm{1}}^{\prime }-y_{\mathrm{3}}^{\prime }\right)\\ ⋮& ⋮\\ \left(x_{\mathrm{1}}^{\prime }-x_N^{\prime }\right)& \left(y_{\mathrm{1}}^{\prime }-y_N^{\prime }\right)\end{array}\right],\\ B=\left[\begin{array}{c}{\left({\widehat{d}}_{\text{los},\mathrm{2}}\right)}^{\mathrm{2}}-{\left({\widehat{d}}_{\text{los},\mathrm{1}}\right)}^{\mathrm{2}}-\left(x_{\mathrm{2}}^{\prime \mathrm{2}}+y_{\mathrm{2}}^{\prime \mathrm{2}}\right)+\left(x_{\mathrm{1}}^{\prime \mathrm{2}}+y_{\mathrm{1}}^{\prime \mathrm{2}}\right)\\ {\left({\widehat{d}}_{\text{los},\mathrm{3}}\right)}^{\mathrm{2}}-{\left({\widehat{d}}_{\text{los},\mathrm{1}}\right)}^{\mathrm{2}}-\left(x_{\mathrm{3}}^{\prime \mathrm{2}}+y_{\mathrm{3}}^{\prime \mathrm{2}}\right)+\left(x_{\mathrm{1}}^{\prime \mathrm{2}}+y_{\mathrm{1}}^{\prime \mathrm{2}}\right)\\ ⋮\\ {\left({\tilde{d}}_{\text{nlos},N}\right)}^{\mathrm{2}}-{\left({\widehat{d}}_{\text{los},\mathrm{1}}\right)}^{\mathrm{2}}-\left(x_N^{\prime \mathrm{2}}+y_N^{\prime \mathrm{2}}\right)+\left(x_{\mathrm{1}}^{\prime \mathrm{2}}+y_{\mathrm{1}}^{\prime \mathrm{2}}\right)\end{array}\right].\end{array}$$

(14)

The estimated position of robot can be obtained as follows:

$$\begin{array}{cc}& \widehat{Y}={\left(A^{T}A\right)}^{-\mathrm{1}}{A}^{T}B.\end{array}$$

(15)

3.5. Kalman Filter

The state equation can be expressed as follows [23, 24]:

$$\begin{array}{cc}& X\left(k\right)=F\left(\Delta t\right)X\left(k-\mathrm{1}\right)+w\left(k-\mathrm{1}\right),\end{array}$$

(16)

where $X(k-1)$ and $X(k)$ are the state vector at time $k-1$ and k, respectively. Let the state vector be $X(k)={[\widehat{x}(k),\widehat{y}(k),\dot{\widehat{x}}(k),\dot{\widehat{y}}(k)]}^T$ ; $[x(k),y(k)]$ represents the estimated position of unknown node according to Section 3.4 at time k. $[\dot{\widehat{x}}(k),\dot{\widehat{y}}(k)]$ denotes the velocity of unknown node. $w(k-1)$ is the process noise and follows zero mean independently and identically distributed Gaussian with variance ${\sigma }_w^{\mathrm{2}}$ . Consider

$$\begin{array}{cc}& F\left(\Delta t\right)=\left[\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \Delta t& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \Delta t\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right],\end{array}$$

(17)

where $\Delta t=\mathrm{1}$ is the sample period.

The measurement equation can be expressed as follows:

$$\begin{array}{cc}& Z\left(k\right)=\widehat{Y}\left(k\right).\end{array}$$

(18)

We can obtain the predicted state and prediction covariance as follows:

$$\begin{array}{cc}& \widehat{X}\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right)=F\left(\Delta t\right)\widehat{X}\left(k-\mathrm{1}\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right),\\ P\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right)=F\left(\Delta t\right)P\left(k-\mathrm{1}\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right)F^T\left(\Delta t\right)+{\sigma }_w^{\mathrm{2}},\\ \widehat{Z}\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right)=G\widehat{X}\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right),\\ \gamma \left(k\right)=Z\left(k\right)-\widehat{Z}\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right),\end{array}$$

(19)

where $\widehat{X}$ represents the estimate of state vector X, $\widehat{X}(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1})$ is the predicted state estimate of state vector, $\widehat{X}(k-\mathrm{1}\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1})$ is the state estimate at the time $k-1$ , $P(k-\mathrm{1}\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1})$ and $P(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1})$ are the estimate and predicted covariance at the time $k-1$ , respectively, and $\widehat{Z}(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1})$ is a priori state estimate of measurement $Z(k)$ . Consider

$$\begin{array}{cc}& G=\left[\begin{array}{c}\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\\ \begin{array}{cccc}\mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}\end{array}\end{array}\right].\end{array}$$

(20)

Then we can obtain the updated state estimate and updated estimate covariance as follows:

$$\begin{array}{cc}& S\left(k\right)=GP\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right)G_{}^T+Q,\\ K\left(k\right)=P\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right)G_{}^T{S}_{}^{-\mathrm{1}}\left(k\right),\\ \widehat{X}\left(k\hspace{0.17em}|\hspace{0.17em}k\right)=\widehat{X}\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right)+K\left(k\right)\gamma \left(k\right),\\ P\left(k\hspace{0.17em}|\hspace{0.17em}k\right)=P\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right)-K\left(k\right)GP\left(k\hspace{0.17em}|\hspace{0.17em}k-\mathrm{1}\right),\end{array}$$

(21)

where Q is the covariance matrix of measurement error.

The estimated position of unknown node in Kalman filter at time k is expressed as

$$\begin{array}{cc}& \tilde{X}\left(k\right)=G\widehat{X}\left(k\hspace{0.17em}|\hspace{0.17em}k\right),\end{array}$$

(22)

where $\tilde{X}(k)={[\tilde{x}(k),\tilde{y}(k)]}^T$ .

4. Simulation Results

In this section, we discuss the performance of the proposed NLOS identification based localization algorithm (NILA). Simulation results were obtained using MATLAB v7.1. Let us consider a scenario consisting of N beacon nodes deployed in an 80 m × 80 m space. And the obstacles are randomly deployed. The measurement noise is modeled as Gaussian distribution random variables. We compared the proposed method with the traditional Kalman filter (KF) and particle filter (PF). Table 1 presents the default parameter values in the experiments. In order to evaluate the localization accuracy of the localization methods, the following equation is used as the rule of accuracy:

$$\begin{array}{l}\text{localization}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{error}\\ \hspace{1em}\hspace{1em}=\sqrt{\frac{\mathrm{1}}{N_{t}K}{\displaystyle \sum }_{i=\mathrm{1}}^{N_t}{\displaystyle \sum }_{k=\mathrm{1}}^K{\left({\tilde{x}}_i\left(k\right)-x\right)}^{\mathrm{2}}+{\left({\tilde{y}}_i\left(k\right)-y\right)}^{\mathrm{2}}},\end{array}$$

(23)

where $[{\tilde{x}}_i(k),{\tilde{y}}_i(k)]$ is the estimated position of unknown node at time k in ith trail. $[x,y]$ is the true position of unknown node.

Table 1

Default parameter values.

Parameters	Default values
Number of sensor nodes $(M)$	7
Number of NLOS measurements	3
Standard variance of LOS noise $({\sigma }_{\text{los}})$	1 m
Mean of the NLOS noise $({\mu }_{\text{nlos}})$	3 m
Standard variance of NLOS noise $({\sigma }_{\text{nlos}})$	5 m

Figure 3 shows the localization results in one trial. It can be observed that the proposed algorithm could localize the unknown accuracy in LOS/NLOS mixed environments. In Figure 4, the detailed localization errors in each sample point are given. We can see that the proposed method has better performance in comparison with KF and PF methods in most of the sample points.

Figure 3

Example of the localization results in one trial.

Figure 4

The localization errors in each sample point.

Figure 5 shows the relationship between the localization error and the standard variance of LOS noise. It is obvious that the localization error increases with the increment of standard variance of LOS noise. The NILA has higher localization accuracy than KF and PF, about 45.66% and 19.07%, respectively. So the localization accuracy of NILA is improved significantly in comparison with the other two methods.

Figure 5

The localization errors versus the standard variance of LOS noise.

Figure 6 shows the impact of mean of NLOS noise on the localization error. The results show that the mean of NLOS noise has a significant impact on KF and PF methods. The proposed NILA method has 31.35% higher localization accuracy than PF. Figure 7 shows the relationship between the localization error and the standard variance of NLOS noise. It is observed that the localization errors of all methods increase as the value of standard variance increases. And the proposed NILA owns the best performance in localization error when compared with other methods.

Figure 6

The localization errors versus the mean of NLOS noise.

Figure 7

The localization errors versus the standard variance of NLOS noise.

As shown in Figure 8, the localization accuracy will be greatly improved with the increasing number of beacon nodes. The localization errors of KF and PF decrease rapidly as the number of beacon nodes increases. On the whole, the proposed NILA owns higher localization accuracy than other compared methods.

Figure 8

The localization errors versus the number of beacon nodes.

5. Conclusion

In this paper, we proposed a RSS based localization algorithm to handle the problem of simultaneously localizing the unknown node in LOS/NLOS environments. The proposed method could identify the propagation conditions of the beacon nodes. And the measurements which contain the NLOS error are corrected. Finally, the Kalman filter is used to mitigate the process noise. We compared the proposed algorithm with traditional Kalman filter and particle filter. The simulation results show that the proposed algorithm achieves higher localization accuracy and outperforms other methods.