Time-of-arrival–based localization algorithm in mixed line-of-sight/non-line-of-sight environments

Abstract

A novel time-of-arrival–based localization algorithm in mixed line-of-sight/non-line-of-sight environments is proposed. First, an optimization problem of target localization in the known distribution of line-of-sight and non-line-of-sight is established, and mixed semi-definite and second-order cone programming techniques are used to transform the original problem into a convex optimization problem which can be solved efficiently. Second, a worst-case robust least squares criterion is used to form an optimization problem of target localization in unknown distribution of line-of-sight and non-line-of-sight, where all links are treated as non-line-of-sight links. This problem is also solved using the similar techniques used in the known distribution of line-of-sight and non-line-of-sight case. Finally, computer simulation results show that the proposed algorithms have better performance in both the known distribution and the unknown distribution of line-of-sight and non-line-of-sight environments.

Introduction

In recent years, localization technology in wireless sensor network has been widely used in many fields such as target tracking, navigation, and communication. A number of localization methods have been proposed based on the characteristic parameters of the received signal and the application environment, including time-of-arrival (TOA), ¹ time-difference-of-arrival (TDOA), ² angle-of-arrival (AOA), ³ received-signal-strength (RSS), ⁴ and hybrid localization methods of various localization techniques.^5,6 These localization methods generally assume that the propagation between the signal source and the sensor is in line-of-sight (LOS). However, obstacles are often impeded in harsh environments such as complex cities or indoors. The direct use of these methods leads to very poor localization accuracy. Therefore, localization problem in mixed LOS/non-line-of-sight (NLOS) environments attracts more attention. ⁷

Chan et al. ⁸ discussed localization problem when the number of LOS/NLOS links is known, and proposed an optimization problem using LOS information. Furthermore, at least three LOS links are needed to ensure the efficiency of the proposed method. Venkatesh and Buehrer ⁹ proposed a linear programming method where the LOS link information is used to construct the objective function, while the NLOS link information is used to form the constraint, and no limitation of three LOS links is needed in this method. All of the above methods are based on a priori distribution information of NLOS links, which is difficult to be obtained in practice. In order to solve this problem, Zhang et al. ¹⁰ proposed a robust second-order cone programming (SOCP) method which is insensitive to NLOS errors and only needs the upper limit of the NLOS errors. In Tomic et al., ¹¹ the problem is transformed into a generalized trust region subproblem (GTRS) framework, which does not require to distinguish between LOS links and NLOS links. Although the problem is non-convex, the dichotomy can solve such problems with low complexity. These two localization methods improve the performance in mixed environments, and it still exists the gap to expected performance.

In this article, we discuss a TOA-based target localization method under the condition of known and unknown distribution of LOS/NLOS, respectively. The original non-convex target localization optimization problem is relaxed as a convex optimization problem which can be efficiently solved using the mixed semi-definite and SOCP techniques. Moreover, a set of weights of paths between target and anchors is introduced in the proposed method, and the penalty parameter is introduced to make the constraint tight. The proposed method improves the localization performance compared with the other methods, which is verified by simulation results. The main contributions of this article are summarized as follows:

1. The optimization problems of target localization in the known and unknown distribution of LOS and NLOS are established, which are transformed into convex optimization problems using the mixed semi-definite and SOCP techniques.

2. The worst-case least squares criterions in both known and unknown distributions of LOS and NLOS environments are proposed to form the optimization problems of target localization with better robustness.

System model and problem formulation

System model

As shown in Figure 1, a two-dimensional (2D) wireless sensor network consists of a target node and $N$ anchor nodes.

Figure 1.

2D wireless sensor network.

Let $\mathit{x},{\mathit{s}}_i\in {\mathit{R}}^2,i=1,\dots ,N$ represent the unknown target node and the ith known anchor node, respectively. The distance measurement between the target node and the ith anchor node in LOS links and NLOS links ¹² is modeled, respectively, as

$$d_i=\Vert \mathit{x}-{\mathit{s}}_i\Vert +n_i,i\in N_{\mathrm{LOS}}$$ (1a)

$$d_i=\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i+n_i,i\in N_{\mathrm{NLOS}}$$ (1b)

where $\parallel \mathit{x}-{\mathit{s}}_i\parallel$ is the true distance between the target node and the ith anchor node; $N_{\mathrm{LOS}}$ and $N_{\mathrm{NLOS}}$ are the number of LOS links and NLOS links, respectively; $n_i$ is the measurement of the Gaussian distribution, obeying the mean zero and variance $\sigma$ ; $b_i$ is the NLOS deviation in the NLOS link, which obeys the uniform distribution in the range of $[0,\rho ]$ ; and $d_i$ is the measurement distance between the anchor node and the target node. We assume $b_i>>n_i$ , and the magnitude of the NLOS deviation is a given constant, that is, $b_i<b_{\max }$ .

Problem formulation

Squaring both sides of equations (1a) and (1b), respectively, to obtain

$$d_i^2=\Vert \mathit{x}-{\mathit{s}}_i{\Vert }^2+2n_i\Vert \mathit{x}-{\mathit{s}}_i\Vert +{n_i}^2,i\in N_{\mathrm{LOS}}$$ (2a)

$$d_i^2={(\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i)}^2+2n_i(\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i)+{n_i}^2,i\in N_{\mathrm{NLOS}}$$ (2b)

The high-order term $n_i^2$ is rounded off, and the approximate expression of $n_i$ is obtained as

$$n_i\approx \frac{d_i^2-{\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2}{2\Vert \mathit{x}-{\mathit{s}}_i\Vert },i\in N_{\mathrm{LOS}}$$ (3a)

$$n_i\approx \frac{d_i^2-{(\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i)}^2}{2(\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i)},i\in N_{\mathrm{NLOS}}$$ (3b)

Using the least squares criterion in LOS links and the worst-case robust least squares (RLS) criterion in NLOS links, the localization problem can be transformed into the following problem

$$\begin{array}{c}{min}_{\mathit{x}}\sum _{i\in N_{\mathrm{LOS}}}{\left(\frac{d_i^2-{\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2}{2\Vert \mathit{x}-{\mathit{s}}_i\Vert }\right)}^2\hfill \\ +\sum _{i\in N_{\mathrm{NLOS}}}\underset{b_i}{max}{\left(\frac{d_i^2-{(\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i)}^2}{2\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i}\right)}^2\hfill \end{array}$$ (4)

where “ $\parallel ·\parallel$ ” is the Euclidean norm. Problem (4) is nonlinear and non-convex, and it is difficult to be solved directly. Therefore, the efficient method will be proposed in the next section.

NLOS localization algorithm

Target localization in known LOS/NLOS link case

In the case of the known number and specific distribution of LOS/NLOS links, in order to improve the localization accuracy, it is necessary to make full use of this information.

Let $f(b_i)=\frac{d_i^2-{(\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i)}^2}{2(\Vert \mathit{x}-{\mathit{s}}_i\Vert +b_i)}$ , problem (4) can be transformed into the following problem

$$\begin{array}{c}{min}_{\mathit{x}}\sum _{i\in N_{\mathrm{LOS}}}{\left(\frac{d_i^2-{\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2}{2\Vert \mathit{x}-{\mathit{s}}_i\Vert }\right)}^2+\sum _{i\in N_{\mathrm{NLOS}}}\underset{b_i}{max}{\left|f\left(b_i\right)\right|}^2\hfill \end{array}$$ (5)

Since $f(b_i)$ is monotonically decreasing on $[0,\rho ]$

$$\underset{b_i}{max}\left|f\left(b_i\right)\right|=max\{\left|f\left(0\right)\right|,\left|f\left(b_{\max }\right)\right|\}$$ (6)

Problem (6) is converted into the problem

$$\underset{\mathit{x}}{min}\sum _{i\in N_{\mathrm{LOS}}}{\left(\frac{d_i^2-{\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2}{2\Vert \mathit{x}-{\mathit{s}}_i\Vert }\right)}^2+\sum _{i\in N_{\mathrm{NLOS}}}\underset{b_i}{max}\{{\left|f\left(0\right)\right|}^2,{\left|f\left(b_{\max }\right)\right|}^2\}$$ (7)

Problem (7) is a non-convex problem and difficult to solve, and the auxiliary variable $t$ is introduced. Problem (7) is obtained as

$$\begin{array}{c}\underset{\mathit{x},\mathit{t}}{min}\sum _{i=1}^N{t}_i\hfill \\ \mathrm{s}.\mathrm{t}.{\left(\frac{d_i^2-{\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2}{2\Vert \mathit{x}-{\mathit{s}}_i\Vert }\right)}^2\le t_i,i\in N_{\mathrm{LOS}}\hfill \end{array}$$ (8a)

$${\left|f\left(0\right)\right|}^2\le t_i,i\in N_{\mathrm{NLOS}}$$ (8b)

$${\left|f\left(\rho \right)\right|}^2\le t_i,i\in N_{\mathrm{NLOS}}$$ (8c)

where

$$\begin{array}{c}{\left|f\left(0\right)\right|}^2=\frac{{(d_i^2-{\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2)}^2}{4{\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2}\mathrm{and}\hfill \\ {\left|f\left(\rho \right)\right|}^2=\frac{{(d_i^2-{\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2-{\rho }^2-2\rho {\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2)}^2}{4({\Vert \mathit{x}-{\mathit{s}}_i\Vert }^2+2\rho \Vert \mathit{x}-{\mathit{s}}_i\Vert +{\rho }^2)}\hfill \end{array}$$

While the constraints in problem (8) are non-convex, the auxiliary variables $h_i=\parallel \mathit{x}-{\mathit{s}}_i{\parallel }^2$ and $r_i=\parallel \mathit{x}-{\mathit{s}}_i\parallel$ are introduced. Problem (8) is transformed into the following problem

$$\begin{array}{c}\underset{\mathit{x},\mathit{t},\mathit{h},\mathit{r}}{min}\sum _{i=1}^N{t}_i\hfill \\ \mathrm{s}.\mathrm{t}.\frac{{(d_i^2-h_i)}^2}{4h_i}\le t_i\hfill \end{array}$$ (9a)

$$\frac{{(d_i^2-h_i-{\rho }^2-2\rho r_i)}^2}{4(h_i+2\rho r_i+{\rho }^2)}\le t_i,i\in N_{\mathrm{NLOS}}$$ (9b)

$$h_i=\Vert \mathit{x}-{\mathit{s}}_i{\Vert }^2$$ (9c)

$$r_i=\Vert \mathit{x}-{\mathit{s}}_i\Vert$$ (9d)

Problem (9) is still a non-convex problem, (9a), (9b), and (9c) are relaxed by the convex relaxation technique, respectively, to obtain the following formula

$$\Vert \left[\begin{array}{c}2(d_i^2-h_i)\hfill \\ \multicolumn{1}{c}{h_i-4t_i}\end{array}\right]\Vert \le h_i+4t_i$$ (10a)

$$\begin{array}{c}\Vert \left[\begin{array}{c}2(d_i^2-h_i{\rho }^2-2\rho r_i)\hfill \\ \multicolumn{1}{c}{(h_i+2\rho r_i+{\rho }^2)-4t_i}\end{array}\right]\Vert \hfill \\ \le (h_i+2\rho r_i+{\rho }^2)+4t_i,i\in N_{\mathrm{NLOS}}\hfill \end{array}$$ (10b)

$$h_i={\left[\begin{array}{c}{\mathit{s}}_i\hfill \\ \multicolumn{1}{c}{-1}\end{array}\right]}^T\left[\begin{array}{cc}{\mathit{I}}_2\hfill & \mathit{x}\hfill \\ \multicolumn{1}{c}{\mathit{x}}& z\hfill \end{array}\right]\left[\begin{array}{c}{\mathit{s}}_i\hfill \\ \multicolumn{1}{c}{-1}\end{array}\right]$$ (10c)

$$\left[\begin{array}{cc}{\mathit{I}}_2\hfill & \mathit{x}\hfill \\ \multicolumn{1}{c}{\mathit{x}}& z\hfill \end{array}\right]\ge 0$$ (10d)

where $z$ is a constant.

A set of weights $\omega$ is introduced in the objective function to reduce the influence of the NLOS links on the localization result. So, problem (9) is described as the following problem

$$\begin{array}{c}\underset{\mathit{x},\mathit{t},\mathit{h},\mathit{r},z}{min}\sum _{i=1}^N{\omega }_i{t}_i\hfill \\ \mathrm{s}.\mathrm{t}.\left(9\mathrm{d}\right),\left(10\mathrm{a}\right)-\left(10\mathrm{d}\right)\hfill \end{array}$$ (11)

where

$$w_i=\{\begin{array}{cc}\frac{d_i}{\sum d_i},\hfill & i\in N_{\mathrm{NLOS}}\hfill \\ \multicolumn{1}{c}{1,}& i\in N_{\mathrm{LOS}}\hfill \end{array}$$

Although problem (11) is a convex problem, penalty parameters and constraints are introduced to further improve performance. In the following optimal objective function, the term ${{\mu }_i}^2$ is introduced for the penalty function approximation; the penalty constraint ${d_i}^2+{\mu }_i\ge h_i$ is formed using equation (1) and ${\mu }_i\ge 0$ . Problem (11) is described as the following problem

$$\begin{array}{c}\underset{\mathit{x},\mathit{t},\mathit{h},\mathit{r},z}{min}\sum _{i=1}^N{\omega }_i{t}_i+\sum _{i=1}^N{{\mu }_i}^2\hfill \\ \mathrm{s}.\mathrm{t}.{d_i}^2+{\mu }_i\ge h_i\hfill \end{array}$$ (12a)

$$\begin{array}{c}{\mu }_i\ge 0\hfill \\ \left(9\mathrm{d}\right),\left(10\mathrm{a}\right)-\left(10\mathrm{d}\right)\hfill \end{array}$$ (12b)

Problem (12) is a convex optimization problem that can be solved by the ConVeX (CVX) toolbox. The algorithm proposed in this section is denoted as Mix-K.

Target localization in unknown LOS/NLOS link case

In this section, we consider the target localization when the number and the specific distribution of LOS/NLOS links are unknown, and all the links are treated as NLOS links. In this case, problem (4) is simplified to the following problem

$$\underset{\mathit{x}}{min}\sum _{i=1}^N\underset{b_i}{max}{\left|f\left(b_i\right)\right|}^2$$ (13)

Problem (13) is a non-convex problem and difficult to solve, and can be transformed into the problem using the similar auxiliary variable technique as discussed in section “Target localization in known LOS/NLOS link case”

$$\begin{array}{c}\underset{\mathit{x},\mathit{t},\mathit{h},\mathit{r}}{min}\sum _{i=1}^N{t}_i\hfill \\ \mathrm{s}.\mathrm{t}.\Vert \left[\begin{array}{c}2(d_i^2-h_i)\hfill \\ \multicolumn{1}{c}{h_i-4t_i}\end{array}\right]\Vert \le h_i+4t_i\hfill \end{array}$$ (14a)

$$\Vert \left[\begin{array}{c}2(d_i^2-h_i{\rho }^2-2\rho r_i)\hfill \\ \multicolumn{1}{c}{(h_i+2\rho r_i+{\rho }^2)-4t_i}\end{array}\right]\Vert \le (h_i+2\rho r_i+{\rho }^2)+4t_i$$ (14b)

$$h_i={\left[\begin{array}{c}{\mathit{s}}_i\hfill \\ \multicolumn{1}{c}{-1}\end{array}\right]}^T\left[\begin{array}{cc}{\mathit{I}}_2\hfill & \mathit{x}\hfill \\ \multicolumn{1}{c}{\mathit{x}}& z\hfill \end{array}\right]\left[\begin{array}{c}{\mathit{s}}_i\hfill \\ \multicolumn{1}{c}{-1}\end{array}\right]$$ (14c)

$$\left[\begin{array}{cc}{\mathit{I}}_2\hfill & \mathit{x}\hfill \\ \multicolumn{1}{c}{\mathit{x}}& z\hfill \end{array}\right]\ge 0$$ (14d)

$$r_i^2=h_i$$ (14e)

The constraint in (14e) is still non-convex, which is relaxed as $r_i^2\le h_i$ , and the penalty term ${\mu }_i\ge 0$ is introduced to obtain ${d_i}^2+{\mu }_i\ge h_i$ . Based on these processing parameters, we obtain the following problem

$$\begin{array}{c}\underset{\mathit{x},\mathit{t},\mathit{h},\mathit{r},z}{min}\sum _{i=1}^N{t}_i+\sum _{i=1}^N{{\mu }_i}^2\hfill \\ \mathrm{s}.\mathrm{t}.\Vert \left[\begin{array}{c}2(d_i^2-h_i)\hfill \\ \multicolumn{1}{c}{h_i-4t_i}\end{array}\right]\Vert \le h_i+4t_i\hfill \end{array}$$ (15a)

$$\Vert \left[\begin{array}{c}2(d_i^2-h_i{\rho }^2-2\rho r_i)\hfill \\ \multicolumn{1}{c}{(h_i+2\rho r_i+{\rho }^2)-4t_i}\end{array}\right]\Vert \le (h_i+2\rho r_i+{\rho }^2)+4t_i$$ (15b)

$$h_i={\left[\begin{array}{c}{\mathit{s}}_i\hfill \\ \multicolumn{1}{c}{-1}\end{array}\right]}^T\left[\begin{array}{cc}{\mathit{I}}_2\hfill & \mathit{x}\hfill \\ \multicolumn{1}{c}{\mathit{x}}& z\hfill \end{array}\right]\left[\begin{array}{c}{\mathit{s}}_i\hfill \\ \multicolumn{1}{c}{-1}\end{array}\right]$$ (15c)

$$\left[\begin{array}{cc}{\mathit{I}}_2\hfill & \mathit{x}\hfill \\ \multicolumn{1}{c}{\mathit{x}}& z\hfill \end{array}\right]\ge 0$$ (15d)

$$r_i^2\le h_i$$ (15e)

$${d_i}^2+{\mu }_i\ge h_i$$ (15f)

$${\mu }_i\ge 0$$ (15g)

Problem (15) is a convex optimization problem that can be solved by the CVX toolbox. The algorithm proposed in this section is denoted as Mix-U.

Simulation results

In this section, Monte Carlo simulation results are provided to compare the performance of the proposed method with R-SOCP, ¹⁰ R-weighted least squares (WLS), ¹¹ LS-K, and LS-U methods, where the simple nonlinear least squares algorithm with only LOS links is denoted as LS-K and the simple nonlinear least squares algorithm with all LOS/NLOS links is denoted as LS-U. The Cramér–Rao lower bound (CRLB) of the known LOS/NLOS link ¹³ distributions is denoted as CRLB-K. The target node and the anchor nodes are randomly chosen from an area of size 20 m × 20 m. The number of anchor nodes is $N=8$ , and the maximum NLOS deviation amplitude is $\rho =5\mathrm{m}$ . The root mean square error (RMSE) is defined as follows to evaluate the localization performance of the discussed methods

$$\mathrm{RMSE}=\sqrt{\frac{1}{\mathrm{Mc}}\sum _{i=1}^{\mathrm{Mc}}{\Vert \mathit{x}-\tilde{\mathit{x}}\Vert }^2}$$ (16)

where $\mathrm{Mc}=10,000$ is the number of Monte Carlo simulation runs, and $\tilde{\mathit{x}}$ is the estimate of the true target node $\mathit{x}$ in the ith Monte Carlo simulation run.

Figure 2 shows the RMSE versus different standard deviations of noise when the number of NLOS links $N_{\mathrm{NLOS}}=4$ . It is naturally observed that the RMSE increases with increase noise level for all the discussed methods. Furthermore, it is also observed that the proposed two methods yield smaller RMSE values than the R-SOCP and R-WLS methods, and the RMSE of the Mix-K method is the closest to CRLB-K than the other discussed methods in higher noise case.

Figure 2.

RMSE versus different standard deviations of noise when $N=8,N_{\mathrm{NLOS}}=4,\mathrm{and}\rho =5\mathrm{m}$ .

Figure 3 shows the RMSE versus different numbers of NLOS links when the standard deviation of noise is 0.6 m. It is observed that the RMSE of the Mix-K, Mix-U, LS-K, and R-SOCP methods increase with the number of NLOS links, while the RMSE of the R-WLS method decreases with the number of NLOS links. This difference is due to the fact that all links are treated as NLOS links, which subtract the term $b_{\max }/2$ in the R-WLS method. Furthermore, a large error is introduced for all LOS links when the number of NLOS links is small, while the error is reduced when the number of NLOS links is large. Therefore, the simulation result reveals the RMSE difference between R-WLS and the other three methods. The figure also shows that the performance of the proposed Mix-K and Mix-U methods is obviously better than that of the other methods when the number of NLOS links is small. It is known that the closed form of the CRLB is obtained when the LOS/NLOS link distributions are known in advance and at least three LOS links are needed; however, no theoretical result of CRLB is obtained when the LOS/NLOS links are unknown. Therefore, CRLB-K and LS-K have values when the number of NLOS links is between 2 and 5 as three LOS links are known in this case.

Figure 3.

RMSE versus different numbers of NLOS links when $N=8,{\sigma }_i=0.6\mathrm{m},\mathrm{and}\rho =5\mathrm{m}$ .

Figure 4 shows the RMSE versus different $b_{\max }$ when ${\sigma }_i=0.6\mathrm{m}$ and $N_{\mathrm{NLOS}}=4$ . It is observed that the RMSE of the Mix-K, Mix-U, LS-U, and R-WLS methods increases with the $b_{\max }$ , while the RMSE of the R-SOCP method decreases with the $b_{\max }$ . Furthermore, the RMSE of CRLB-K and LS-K remains unchanged, as they are only related to LOS links. Therefore, the localization performance of the Mix-K method is the closest to CRLB-K than the other methods.

Figure 4.

RMSE versus different $b_{\max }$ when $N=8,{\sigma }_i=0.6\mathrm{m},\mathrm{and}{N}_{\mathrm{NLOS}}=4$ .

Figure 5 shows the cumulative distribution function (CDF) versus different estimation errors when the number of NLOS links $N_{\mathrm{NLOS}}=4$ and the standard deviation of noise is 0.6 m. When the CDF reaches 90%, it is observed that the estimation error of the five methods R-WLS, R-SOCP, LS-K, Mix-K, and Mix-U is, respectively, 6.58, 14.19, 9.25, 3.83, and 5.37 m. These results show that the overall CDF of the Mix-K is better than that of the other methods, and the estimation error of Mix-K method is reduced by 10.36 m when compared to the R-SOCP method.

Figure 5.

CDF versus different estimation errors when $N=8,N_{\mathrm{NLOS}}=4,{\sigma }_i=0.6\mathrm{m},\mathrm{and}\rho =5\mathrm{m}$ .

Conclusion

This article investigates the problem of target localization using TOA in known and unknown LOS/NLOS distributions in mixed LOS/NLOS environments. The optimization problem of estimating target location in two cases is proposed, respectively. The derived non-convex target localization problem is then relaxed to a convex target localization problem, and the method is proposed in the case of known and unknown LOS/NLOS distribution, respectively. Computer simulation results confirm the effectiveness of the proposed method in mixed LOS/NLOS environments.