Nonlinear programming-based ranging optimization for three-dimensional indoor time of arrival localization

Abstract

The distribution of ranging errors of time of arrival techniques fails to satisfy zero means and equal variances. It is one of the major causations of position error of least square–based localization algorithm. The optimization of time of arrival ranging is defined as a nonlinear programming problem. Then, time of arrival ranging error model and geometric constraints are used to define the initial values, objective functions, and constraints of nonlinear programming, as well as to detect line of sight and nonline of sight. A three-dimensional localization algorithm of an indoor time of arrival–based positioning is proposed based on least square and the optimization algorithm. The performance of the ranging and localization accuracies is evaluated by simulation and field testing. Results show that the optimized ranging error successfully satisfies zero mean value and equal variances. Furthermore, the ranging and localization accuracies are significantly improved.

Keywords

Time of arrival indoor positioning three-dimensional localization nonlinear programming least square

Introduction

Location information is one of the most important attributes of an object. Many important areas of human civilization, such as transportation, military, logistics, security, resource exploration, and natural environment protection, have a strong demand for the exact location information of the target. With global positioning system (GPS) as a representative, the rapid development of satellite-based positioning technology has played an important role in promoting location-based services in the outdoor environment. However, in indoor environments, such as buildings, mines, and tunnels, satellite-based positioning techniques are not available because the reference satellite signal energy is severely weakened by the building material or ground shield to the receiving threshold.¹ Thus, the target localization in indoor environments requires a solution to nonsatellite-based positioning technology.

Wireless localization technologies are effective indoor positioning methods. It can be widely used in the military, security, firefighting, process industry, health care, intelligent home, and other fields. Commonly used wireless positioning technologies include received signal strength (RSS), time of arrival (TOA), time different of arrival (TDOA), and angle of arrival (AOA). Among these methods, TOA which is based on the ultra-wide band (UWB) communication has drawn much attention due to its high ranging accuracy.

Similar to the other wireless indoor positioning technologies, TOA also suffers from nonline of sight (NLOS), which is considered to be the most important factor affecting the ranging and positioning accuracy. Therefore, the ranging and positioning accuracy improvement in NLOS condition has been the most popular research topic in TOA-based indoor positioning. The improvement in NLOS distance measurement can be classified as identification and mitigation. NLOS identification typically employs the characteristics of ranging and other measurable radio frequency (RF) signal parameters, to distinguish LOS and NLOS conditions.^2–4 Previous studies have shown that the accuracy of LOS/NLOS identification can achieve up to 92%.³ The most used RF chips with TOA measurement ability in industries are DW1000 chips, which are released by Decawave, and NanoLOC chips, which are released by Nanotron. Both these two RF chips provided the measurement of some RF signal parameters for LOS/NLOS identification, such as RSS and P_FP.^5,6 These providers also recommend LOS/NLOS recognition algorithms for their chips. Therefore, the result of NLOS identification can be used to mitigate the measured distance and improve the localization accuracy. The other approaches of NLOS mitigation are not based on NLOS identification. Such approaches include Kalman filter,⁷ redundant range estimates,⁸ environmental geometrical constrains,⁹ and so on. The detailed overviews of NLOS identification and mitigation are shown in Khodjaev et al.¹⁰

The localization algorithm is another important factor that affects the positioning accuracy. The basic indoor TOA positioning algorithms include Taylor series–based estimation,^11,12 geometric relations–based algorithm,^13,14 maximum likelihood estimation,^14,15 and least square (LS).^16–19 Some improved localization algorithms, which are based on these basic ones, were proposed in the existing literatures to reduce the effect of large ranging error caused by NLOS. LS is one of the most popular algorithms adopted TOA-based indoor positioning due to its low computational complexity. Park and Chang¹⁶ proposed an LOS/NLOS TOA source localization algorithm that utilizes the weighted least squares (WLS). However, the exact choice of the weighted value directly affects the positioning accuracy, and the exact weighting value is difficult to obtain. Wang et al.¹⁹ proposed an optimizing reference selection criterion for the hybrid TOA/RSS LLS localization technique, which considers the measured ranges and the information on their coarse variances. With the incensement of the data dimension, the complexity of the algorithm becomes an important challenge, and the LS localization algorithm is the most commonly used algorithm in three-dimensional (3D) TOA localization.²⁰ The assumptions of the mean value and equal variances must be satisfied to apply LS.²¹ However, in the realistic indoor environment, the distribution of distance measurement error cannot satisfy zero mean value and equal variances because of the effect of multipath and NLOS.²² Therefore, the LS algorithm cannot obtain the optimal estimation result. Consequently, the localization system cannot achieve the highest accuracy based on LS square and the original measured distances. However, to the best of our knowledge, this mismatch was not considered in most of the existing literature of TOA-based indoor positioning.

In this article, an optimization algorithm based on nonlinear programming (NLP) is presented to optimize the distance estimation and tune the ranging error distribution to satisfy zero mean value and equal variance, thereby solving the mismatch problem. The proposed algorithm organized the key parameters of the NLP based on the features of TOA-based indoor positioning, including TOA ranging error model, NLOS identification, and geometric constraint (GC). Then, we applied the optimized distances to improve the localization accuracy of LS in 3D positioning. The performance of the distance optimization and localization is verified by simulation and field testing. The results show that the optimized ranging error successfully satisfied zero mean value and equal variances. Furthermore, the ranging and localization accuracies are significantly improved.

The remainder of this article is presented as follows: section “Problem analysis” provides the mismatch problem analysis. Section “Nonlinear programming model for measured distance optimization” introduces the nonlinear programming model of TOA distance measurement value optimization. Section “Localization algorithm” elaborates the overall solution of the localization algorithm. Section “Simulation” introduces the performance evaluation based on simulation. In section “Field testing,” optimization algorithm was validated with experimental data and analysis. Section “Conclusion” concludes this article.

Problem analysis

LS and its premise hypothesis

Gauss–Markov theorem reveals that the best unbiased linear estimator of the regression coefficient is the minimum variance estimate in the linear regression model in the zero mean value and equation variance condition.

Assuming that the target node measures distance with $n$ reference nodes in the one process of localization; the actual coordinates of the target node is $(x, y)$ , the coordinate set of reference nodes is ${(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})}$ , and the distance between the target node and the reference node is ${d_{1}, d_{2}, \dots, d_{n}}$ . The following are the nonlinear equations

{\begin{matrix} {(x_{1} - x)}^{2} + {(y_{1} - y)}^{2} & = & d_{1}^{2} \\ ⋮ & ⋮ \\ {(x_{n} - x)}^{2} + {(y_{n} - y)}^{2} & = & d_{n}^{2} \end{matrix}

(1)

After the simplification of the equation, these nonlinear equations can be transformed into a linear equation, as follows

AX = b

(2)

where

\begin{matrix} A = [\begin{matrix} 2 (x_{1} - x_{n}) & \dots & 2 (y_{1} - y_{n}) \\ ⋮ & ⋮ \\ 2 (x_{n - 1} - x_{n}) & \dots & 2 (y_{n - 1} - y_{n}) \end{matrix}] \\ b = [\begin{matrix} x_{1}^{2} - x_{n}^{2} + y_{1}^{2} - y_{n}^{2} + d_{n}^{2} - d_{1}^{2} \\ ⋮ \\ x_{1}^{2} - x_{n}^{2} + y_{1}^{2} - y_{n}^{2} + d_{n}^{2} - d_{1}^{2} \end{matrix}] \\ X = [\begin{matrix} x \\ y \end{matrix}] \end{matrix}

These equations indicate that localization based on distances can be defined as a linear regression problem. Therefore, if the ranging error satisfies zero mean and equal variance, the optimal unbiased estimator is the LS estimator. Then, the results of the LS localization algorithm can be obtained by the following formula

\hat{X} = {(A^{T} A)}^{- 1} A^{T} b

(3)

where $\hat{X} = {[\begin{matrix} \hat{x} & \hat{y} \end{matrix}]}^{T}$ is the estimated coordinate of the target node.

Characteristics of indoor TOA ranging error

TOA is a method that estimates the distance by measuring the propagation time of wireless signal. The principle of TOA ranging is shown in Figure 1.^4,5 $T_{1}$ denotes the time that Device A sends the “Ranging data” pulse, $T_{2}$ is the time Device B receives “Ranging data” pulse, $T_{3}$ is the time Device B sends “Acknowledgment (ACK)” pulse, and $T_{4}$ is the time Device A receives “ACK” pulse. Device A and Device B measure $t_{round A}$ and $t_{r e ply B}$ by their local timer. The formula for calculating the distance between the devices is as follows

\begin{matrix} {\hat{d}}_{AB} = t_{p} \times C = \frac{t_{round A} - t_{reply B}}{2} \times C \\ = \frac{(T_{4} - T_{1}) - (T_{3} - T_{2})}{2} \times C \end{matrix}

(4)

where $C = 3 \times 10^{8} m / s$ .

Figure 1.

Principle of TOA ranging.⁷

TOA ranging error is derived from two different sources, as follows: pulse detection error caused by the hardware ( $ε_{d}$ ) and pulse shift error caused by the indoor wireless channel. Typically, the pulse shift error is much larger than the detection error. As shown in Figure 2, the line of sight (LOS) transmission and NLOS transmissions are two typical scenarios of TOA ranging. In the LOS scenario, there is no obstacle between the transmitter and the receiver, and the ranging error is mainly caused by multipath. In the NLOS scenario, there is a block between the transmitter and the receiver, and the main ranging error is derived from the channel condition of the undetectable direct path (UDP). Therefore, the pulse shift error can be classified as the multipath and UDP errors, defined as follows:

Multipath error ( $ε_{m}$ ) is derived from the peak shift caused by the combination of the first detectable path (FDP) and its adjacent paths.

UDP error ( $ε_{u}$ ) is derived from the concept that FDP is not direct path (DP).

Figure 2.

LOS and NLOS scenarios.⁷

According to the above analysis, indoor TOA ranging error can be divided into two cases

e_{TOA} = {\begin{matrix} \begin{matrix} e_{LOS}, & s = LOS \end{matrix} \\ \begin{matrix} e_{NLOS}, & s = NLOS \end{matrix} \end{matrix}

(5)

where

{\begin{matrix} e_{LOS} = ε_{d} + ε_{m} \\ e_{NLOS} = ε_{d} + ε_{m} + ε_{u} \end{matrix}

Previous studies have shown $ε_{d}$ , $ε_{m}$ , and $ε_{u}$ are in accord with normal distribution. Thus, $e_{LOS}$ and $e_{NLOS}$ are also in accord with normal distribution. And the mean variance have the following characteristics

{\begin{matrix} μ_{LOS} = μ_{d} + μ_{m} > 0 \\ μ_{NLOS} = μ_{d} + μ_{m} + μ_{u} > μ_{LOS} \end{matrix}

(6)

{\begin{matrix} σ_{LOS}^{2} = σ_{d}^{2} + σ_{m}^{2} \\ σ_{NLOS}^{2} = σ_{d}^{2} + σ_{m}^{2} + σ_{u}^{2} > σ_{LOS}^{2} \end{matrix}

(7)

Challenges in indoor TOA localization based on LS

Challenge 1

The mismatch between the distribution of ranging error and the Gauss–Markov hypothesis:

The analysis in section “LS and its premise hypothesis” shows that the LS localization algorithm is the best unbiased estimation only if the TOA ranging errors are zero mean and equal variance. However, according to formulas (6) and (7), the distribution of the actual TOA ranging error cannot satisfy the following assumptions:

In the LOS or the NLOS scenario, the mean of the ranging error is greater than 0; thus, it does not satisfy the zero mean assumption.

The ranging error cannot easily satisfy the equal variance assumption given the difference between the variances of LOS and NLOS ranging errors.

Challenge 2

The analysis in section “Characteristics of indoor TOA ranging error” shows that the large ranging error of TOA measurement is mainly caused by NLOS, which frequently appears in indoor areas. Evidently, NLOS is the main challenge to achieve high localization accuracy in TOA-based indoor positioning. It is also a challenge of the LS-based localization algorithm.

Nonlinear programming model for measured distance optimization

This article proposes a new algorithm based on multiconstrained nonlinear programming to optimize the original distances and solve the mismatch problem. The optimization process of nonlinear programming is to approach the objective function by iterating from the initial value under the constrained condition until the convergence condition is satisfied. Except the optimization algorithm, the key factors that affect the performance of nonlinear programming include the following: (1) initial value, (2) constrained conditions, and (3) objective function. The initial value specifies the starting point of the iteration. Thus, the initial value should be set to be close to the true value but not as a random value. The objective function specifies the optimum solution and determines the iterative direction of the optimization algorithm. It should be set according to the problem. Typically, nonlinear LS optimization objective function is used for indoor positioning. Therefore, the definition of initial value, constrained condition, and objective function can be regarded as modeling the nonlinear programming problem. Thus, we provide the definition of initial value, constrained condition, and objective function according to the features of TOA-based indoor positioning.

Initial value

The distributions of LOS and NLOS ranging errors can be defined as follows

{\begin{matrix} e_{LOS} \in N (μ_{LOS}, σ_{LOS}^{2}) \\ e_{NLOS} \in N (μ_{NLOS}, σ_{NLOS}^{2}) \end{matrix}

(8)

According to equation (8), $e_{LOS} - μ_{LOS}$ and $e_{NLOS} - μ_{NLOS}$ fit the Gaussian distribution with mean value of 0

{\begin{matrix} e_{LOS} - μ_{LOS} \in N (0, σ_{LOS}^{2}) \\ e_{NLOS} - μ_{NLOS} \in N (0, σ_{NLOS}^{2}) \end{matrix}

(9)

We name the actual distance between the target and the base station as $d$ and the measured distance between the target and the base station as $\hat{d}$ . The random variable is defined as follows

{\hat{d}}_{sub - mean} = {\begin{matrix} \begin{matrix} \hat{d} - μ_{LOS}, & s = LOS \end{matrix} \\ \begin{matrix} \hat{d} - μ_{NLOS}, & s = NLOS \end{matrix} \end{matrix}

(10)

where $s$ is the measurement scenario, the error of ${\hat{d}}_{sub - mean}$ is as follows

\begin{matrix} e_{sub - mean} & = {\hat{d}}_{sub - mean} - d \\ = {\begin{matrix} \begin{matrix} e_{LOS} - μ_{LOS}, & s = LOS \end{matrix} \\ \begin{matrix} e_{NLOS} - μ_{NLOS}, & s = NLOS \end{matrix} \end{matrix} \end{matrix}

(11)

$e_{sub - mean}$ can also be confirmed to Gaussian distribution with the mean value of 0

e_{sub - mean} \in N (0, σ_{sub - mean}^{2})

(12)

σ_{sub - mean}^{2} = p^{2} σ_{LOS}^{2} + {(1 - p)}^{2} σ_{NLOS}^{2}

(13)

where $p$ is the probability of LOS and $1 - p$ is the probability of NLOS.

Assuming that $\hat{D}$ is the set of measured distances. ${\hat{D}}_{sub - mean}$ can be obtained by subtracting the corresponding mean value for each range value. ${\hat{D}}_{sub - mean}$ is used as the initial value of the nonlinear programming to solve the problem on the ranging error that does not satisfy zero expectation and equal variances. $μ_{LOS}$ and $μ_{NLOS}$ , which are used as the parameters of the algorithm, can be obtained by statistical LOS/NLOS ranging experiment based on a large number of TOA measurement in the field.

Objective function

The objective function is selected as the nonlinear LS optimization objective function. The optimization error is defined as follows

ε_{i} = d_{i}^{'} - d_{sub - mean - i}

(14)

where $d_{i}^{'}$ is the ith optimized distance and $d_{sub - mean - i}$ is the ith initial value of ${\hat{D}}_{sub - mean}$ . Then, the objective function of nonlinear LS can be defined as

min J (ε) = \sum_{i = 1}^{n} ε_{i}^{2}

(15)

Constrained conditions

The constrained conditions include the interval of distance, the Cayley–Menger determinant, and the law of tetrahedron:

1. The interval constrain of distance. The $3 σ$ law of Gaussian distribution is used to set the interval of distance. As defined in $3 σ$ law, the variable of normal distribution belongs to the interval of $(μ + 3 σ, μ - 3 σ)$ with the probability of 99.7%. The $3 σ$ law states that the ranging error of LOS and NLOS can be considered as follows

{\begin{matrix} e_{LOS} \in (μ_{LOS} - 3 σ_{LOS}, μ_{LOS} + 3 σ_{LOS}) \\ e_{NLOS} \in (μ_{NLOS} - 3 σ_{NLOS}, μ_{NLOS} + 3 σ_{NLOS}) \end{matrix}

(16)

Therefore, the interval of the true distance $d$ can be approximately defined as

\hat{d} \in {\begin{matrix} \begin{matrix} (\hat{d} - μ_{LOS} - 3 σ_{LOS}, \hat{d} - μ_{LOS} + 3 σ_{LOS}), & s = LOS \end{matrix} \\ \begin{matrix} (\hat{d} - μ_{NLOS} - 3 σ_{NLOS}, \hat{d} - μ_{NLOS} + 3 σ_{NLOS}), & s = NLOS \end{matrix} \end{matrix}

(17)

Further converted to

\hat{d} \in {\begin{matrix} \begin{matrix} ({\hat{d}}_{sub - mean} - 3 σ_{LOS}, {\hat{d}}_{sub - mean} + 3 σ_{LOS}), & s = LOS \end{matrix} \\ \begin{matrix} ({\hat{d}}_{sub - mean} - 3 σ_{NLOS}, {\hat{d}}_{sub - mean} + 3 σ_{NLOS}), & s = NLOS \end{matrix} \end{matrix}

(18)

The interval constrain of $d$ can be transferred into the scope of the constraint of $ε$ based on the definition of $ε$ in formula (14), as follows

I (ε) = {\begin{matrix} \begin{matrix} ε \in (- 3 σ_{LOS}, 3 σ_{LOS}), & s = LOS \end{matrix} \\ \begin{matrix} ε \in (- 3 σ_{NLOS}, 3 σ_{NLOS}), & s = NLOS \end{matrix} \end{matrix}

(19)

The $σ_{LOS}$ and $σ_{NLOS}$ in the above formulas can also be obtained by statistical LOS/NLOS ranging experiment based on a large number of TOA measurements in the field.

2. Cayley–Menger determinant constraint. In the theory of distance geometry, the Cayley–Menger determinant can be used to deal with the Euler distance geometry problem.

Definition

In the m-dimensional Euclidean space, given that two sets of n points are composed of ${p_{1}, p_{2}, \dots, p_{n}}$ and ${q_{1}, q_{2}, \dots, q_{n}}$ , respectively, the following matrix can be defined as the Cayley–Menger matrix for two point sets²³

\begin{matrix} M (p_{1}, p_{2}, \dots, p_{n}; q_{1}, q_{2}, \dots, q_{n}) \\ \overset{Δ}{=} (\begin{matrix} d^{2} (p_{1}, q_{1}) & d^{2} (p_{1}, q_{2}) & \dots & d^{2} (p_{1}, q_{n}) & 1 \\ d^{2} (p_{2}, q_{1}) & d^{2} (p_{2}, q_{2}) & \dots & d^{2} (p_{2}, q_{n}) & 1 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ d^{2} (p_{n}, q_{1}) & d^{2} (p_{n}, q_{2}) & \dots & d^{2} (p_{n}, q_{n}) & 1 \\ 1 & 1 & \dots & 1 & 0 \end{matrix}) \end{matrix}

(20)

where $d (p_{i}, q_{j})$ is the Euclidean distance between point $p_{i}$ and $q_{j}$ , $i, j \in (1, 2, \dots, n)$ .

Theorem

If $n \geq m + 2$ , then in m-dimensional space to any fixed point set ${p_{1}, p_{2}, \dots, p_{n}}$ , the following exists

\det (M (p_{1}, p_{2}, \dots, p_{n}; p_{1}, p_{2}, \dots, p_{n})) = 0

It means that the distance between the n points in the m-dimensional space is not isolated from each other but satisfies the relation in the upper form. Therefore, in three-dimensional space, when the number of nodes $n \geq 5$ (with at least four base stations), the following formula can be defined

\begin{matrix} \det (M (p_{1}, p_{2}, \dots, p_{k}, p_{0}; p_{1}, p_{2}, \dots, p_{k}, p_{0})) = 0 \\ \overset{Δ}{=} | \begin{matrix} 0 \\ d^{2} (p_{1}, p_{1}) \\ ⋮ \\ d^{2} (p_{k}, p_{1}) \\ d^{2} (p_{0}, p_{1}) \\ 1 \end{matrix} \begin{matrix} d^{2} (p_{1}, p_{2}) \\ 0 \\ ⋮ \\ d^{2} (p_{1}, p_{2}) \\ d^{2} (p_{0}, p_{2}) \\ 1 \end{matrix} \begin{matrix} \dots \\ ⋱ \\ \dots \\ \dots \\ \dots \end{matrix} \begin{matrix} d^{2} (p_{1}, p_{k}) \\ ⋮ \\ 0 \\ d^{2} (p_{0}, p_{k}) \\ 1 \end{matrix} \begin{matrix} d^{2} (p_{1}, p_{0}) \\ ⋮ \\ d^{2} (p_{k}, p_{0}) \\ 0 \\ 1 \end{matrix} \begin{matrix} 1 \\ ⋮ \\ 1 \\ 1 \\ 0 \end{matrix} | \end{matrix}

(21)

where $k \geq 4$ , $p_{1}, p_{2}, \dots, p_{k}$ are the positions of base stations, and $p_{0}$ is the position of the target node. Therefore, the following can be obtained

\begin{matrix} G (ε) = \det (M (p_{1}, p_{2}, . . ., p_{k}, p_{0}; p_{1}, p_{2}, . . ., p_{k}, p_{0})) \\ \overset{Δ}{=} | \begin{matrix} 0 \\ d_{21}^{2} \\ ⋮ \\ d_{k 1}^{2} \\ {({\hat{d}}_{01}, ε_{01})}^{2} \\ 1 \end{matrix} \begin{matrix} d_{12}^{2} \\ 0 \\ ⋮ \\ d_{k 2}^{2} \\ {({\hat{d}}_{02}, ε_{02})}^{2} \\ 1 \end{matrix} \begin{matrix} \dots \\ ⋱ \\ \dots \\ \dots \\ \dots \end{matrix} \begin{matrix} d_{1 k}^{2} \\ ⋮ \\ 0 \\ {({\hat{d}}_{0 k}, ε_{0 k})}^{2} \\ 1 \end{matrix} \begin{matrix} {({\hat{d}}_{10}, ε_{10})}^{2} \\ ⋮ \\ {({\hat{d}}_{k 0}, ε_{k 0})}^{2} \\ 0 \\ 1 \end{matrix} \begin{matrix} 1 \\ ⋮ \\ 1 \\ 1 \\ 0 \end{matrix} | = 0 \end{matrix}

(22)

where $d_{ij}, i, j \neq 0$ is the distance between two base stations.

3. Tetrahedral constraints.

Theorem

As shown in Figure 3, the necessary and sufficient conditions of six edges to form a tetrahedron²⁴ is

\begin{matrix} \begin{matrix} F (a, a', b, b', c, c') \\ = a^{2} a'^{2} (- a^{2} - a'^{2} + b^{2} + b'^{2} + c^{2} + c'^{2}) \\ + b^{2} b'^{2} (a^{2} + a'^{2} - b^{2} - b'^{2} + c^{2} + c'^{2}) \\ + c^{2} c'^{2} (a^{2} + a'^{2} + b^{2} + b'^{2} - c^{2} - c'^{2}) \\ - (a^{2} b^{2} c^{2} + a^{2} b'^{2} c'^{2} + a'^{2} b^{2} c'^{2} + a'^{2} b'^{2} c^{2}) \end{matrix} & > 0 \end{matrix}

(23)

Figure 3.

Sketch map of tetrahedron.

In 3D positioning system, the target node and any three base stations can form a tetrahedron. Assuming $p_{1}, p_{2}, and p_{3}$ are the base stations, then

\begin{matrix} F (p_{0}, p_{1}, p_{2}, p_{3}) \\ = d_{13}^{2} d_{02}^{2} (- d_{13}^{2} - d_{02}^{2} + d_{23}^{2} + d_{01}^{2} + d_{12}^{2} + d_{03}^{2}) \\ + d_{23}^{2} d_{01}^{2} (d_{13}^{2} + d_{02}^{2} - d_{23}^{2} - d_{01}^{2} + d_{12}^{2} + d_{03}^{2}) \\ + d_{12}^{2} d_{03}^{2} (d_{13}^{2} + d_{02}^{2} + d_{23}^{2} + d_{01}^{2} - d_{12}^{2} - d_{03}^{2}) \end{matrix}

(24)

When formula (6) is introduced into the upper formula, the tetrahedron constraint can be obtained

\begin{matrix} F_{1} (ε) & = F (p_{0}, p_{1}, p_{2}, p_{3}) \\ = d_{13}^{2} {({\hat{d}}_{02} - ε_{02})}^{2} [\begin{matrix} - d_{13}^{2} - {({\hat{d}}_{02} - ε_{02})}^{2} + d_{23}^{2} + {({\hat{d}}_{01} - ε_{01})}^{2} \\ + d_{12}^{2} + {({\hat{d}}_{03} - ε_{03})}^{2} \end{matrix}] \\ + d_{23}^{2} {({\hat{d}}_{01} - ε_{01})}^{2} [\begin{matrix} d_{13}^{2} + {({\hat{d}}_{02} - ε_{02})}^{2} \\ - d_{23}^{2} - {({\hat{d}}_{01} - ε_{01})}^{2} + d_{12}^{2} + {({\hat{d}}_{03} - ε_{03})}^{2} \end{matrix}] \\ + d_{12}^{2} {({\hat{d}}_{03} - ε_{03})}^{2} [\begin{matrix} d_{13}^{2} \\ + {({\hat{d}}_{02} - ε_{02})}^{2} + d_{23}^{2} + {({\hat{d}}_{01} - ε_{01})}^{2} - d_{12}^{2} - {({\hat{d}}_{03} - ε_{03})}^{2} \end{matrix}] \end{matrix}

(25)

Similarly, we can obtain the tetrahedral constraints $F_{k} (ε)$ for the other based stations, where $k = 1, 2, \dots, C_{n}^{3}$ , and n is the number of base stations.

Localization algorithm

The entire solution of the localization algorithm is shown in Figure 4, including the following three steps:

Step 1. The measurement scenario of each distance is detected by the LOS/NLOS recognition algorithm. The input of the algorithm is a set of distance values and a set of LOS/NLOS parameters (e.g. $RSS$ , $P_{FP}$ , and $τ_{RMS_delay}$ ). The output of the algorithm is $(\hat{D}, S)$ , and $S$ is a set of measured scenes.

Step 2. The ranging value is optimized by the nonlinear programming algorithm. The input value of the algorithm is $(\hat{D}, S)$ and the base station coordinates set $BS$ . The parameters of the algorithm are $μ_{LOS}$ , $σ_{LOS}$ , $μ_{NLOS}$ , and $σ_{NLOS}$ . The output of the algorithm is a set of distance values $D^{'}$ . According to $(\hat{D}, S)$ , $μ_{LOS}$ , and $μ_{NLOS}$ , the initial value of the nonlinear programming is set to ${\hat{d}}_{sub - mean}$ and the optimal objective function of the algorithm is set to $min J (ε)$ . According to $S$ , $σ_{LOS}$ , and $σ_{NLOS}$ , the constraint $I (ε)$ can be calculated. According to ${\hat{d}}_{sub - mean}$ and $BS$ , the Cayley–Menger determinant constraints and the tetrahedral constraints are constructed.

Step 3. The coordinates of the target node are calculated by LS algorithm. The input of the algorithm is $D^{'}$ and $BS$ , the output of the algorithm is the calculated coordinates for target node $(\hat{x}, \hat{y}, \hat{z})$ .

Figure 4.

Schematic diagram of the localization algorithm.

Simulation

Performances

The distribution of the ranging and localization errors is evaluated by simulation to verify whether the proposed algorithm can solve the problem of distribution mismatch and improve the ranging and localization accuracies. The performance of the proposed algorithm is compared with the other algorithm to show the improvement. For the validation of ranging accuracy, the distribution of the proposed algorithm, which is named as NLP with geometric constrain and LOS/NLOS detection (LND; NLP with GC and LND in Figure 6), was compared with the original ranging error (measured data in Figure 6), the ranging error of NLP with the GC (NLP with GC in Figure 6), the ranging error of NLOS mitigation algorithms proposed in Heidari et al.³ (NLOS mitigation 1 in Figure 6) and Marano et al.²⁵ (NLOS mitigation 2 in Figure 6). For validation of localization accuracy, the distribution of localization error of the proposed algorithm (LS + NLP with GC and LND in Figure 7) was compared with LS, LS and NLP with GC (LS + NLP with GC in Figure 7), Taylor series estimation (Taylor in Figure 7), LS based on NLOS mitigation (LS + NLOS mitigation 1 in Figure 7).

Simulation settings

The simulation setting of this article includes the realization of the positioning algorithm, the distance measurement error model, and distance measurement scenarios. In the realization of localization algorithm, LOS/NLOS recognition algorithm based on RSS, which is proposed in Wann and Chin,⁴ and the sequential quadratic programming (SQP) are used to implement the LND and nonlinear programming, respectively.²⁶ In the aspect of distance measurement error, this article adopts a typical range error model proposed in Alavi and Pahlavan,²⁷ with the bandwidth of 500 MHz. The model is based on the statistical data obtained in the actual office environment and has a high similarity with the ranging error distribution of the actual system. In addition, given that the RSS parameter is used in the LOS/NLOS recognition algorithm, an RSS value is generated for each set of ranging values through the IEEE802.15.4a standard UWB channel model.²⁸ For the simulation of measurement scenario, 100 m × 100 m × 100 m space is selected. In total, four base stations with the coordinates of (0, 0, 0), (100, 100, 0), (100, 0, 100), and (0, 100, 100) are established. The coordinates of the target nodes in the positioning are randomly generated, and a total of 1000 positioning experiments are performed, including a total of 4000 ranging values. The probability of NLOS is 32%.²⁸

Results and analysis

Distance measurement error. Figure 5(a)–(c) shows the distribution of distance error of original measured data, the distance error of NLP with GC, and the proposed algorithm (NLP with GC and LND), respectively. As shown in Figure 5(c), the range error distribution of the proposed algorithm fits Gaussian distribution effectively, and the mean value mostly equals to 0. On the contrary, the original ranging error is clearly unable to satisfy the assumption of zero mean and the same variance. The ranging error of GC based on the nonlinear programming algorithm is optimized but still does not satisfy the assumption of zero mean. Figure 6 shows the cumulative error probability of the five ranging errors. A total of 50% error of the proposed algorithm is 0, and the distribution curves of the two regions (>0 and <0) are basically the same, whereas the other four ranging error distributions cannot satisfy these characteristics. Figures 5 and 6 show that the proposed algorithm can optimize the distance measurement error to satisfy the distribution characteristics of zero mean and same variance. Table 1 shows the mean and variance statistics of the five ranging errors. It shows that the mean and variance of the distance measurement error after the proposed optimization are superior to the other four ranging errors.

Positioning error. Figure 7 shows the cumulative probability distribution curve of the positioning errors of the five positioning algorithms. Table 2 shows the mean and variance of the localization errors. Figure 7 and Table 2 show that the localization accuracy of the proposed algorithm (LS + NLP with GC and LND) is higher than that of the other algorithms.

Figure 5.

Distance error probability distribution comparison in simulation.

Figure 6.

Comparison of cumulative error probability distribution curves in simulation.

Table 1.

Comparison of mean and variance of range error in simulation.

	Measured error	NLP with GC	NLOS mitigation 1	NLOS mitigation 2	The proposed method
Mean (m)	0.75	0.25	0.02	–0.03	0.01
Variance (m²)	0.87	0.72	0.54	0.76	0.4

NLP: nonlinear programming; NLOS: nonline of sight; GC: geometric constraint.

Figure 7.

Comparison of cumulative probability distribution curves in simulation.

Table 2.

Comparison of mean and variance of positioning error in simulation.

	LS	LS + NLP with GC	Taylor	LS + NLOS mitigation 1	The proposed method
Mean (m)	1.43	1.38	1.57	1.1	0.99
Variance (m²)	0.75	0.74	0.91	0.52	0.39

LS: least square; NLP: nonlinear programming; NLOS: nonline of sight; GC: geometric constraint.

According to the comparisons of ranging error and localization error, the NLOS mitigation–based algorithm and the proposed solution achieved much higher accuracy than the others. It is mainly because of that both these two kinds of algorithms can significantly improve the ranging accuracy and also make the distance measurement error to satisfy the distribution characteristics of zero mean and same variance.

Field testing

Settings

Filed testing was performed with a realistic UWB-TOA-based indoor positioning system, which is developed based on DW1000. The testing scenario is shown in Figure 8. In total, four base stations were deployed in a hall (10 m × 17 m × 4 m) located in the office building of School of Computer and Communication Engineering, University of Science and Technology Beijing. In this test, the NLOS condition was mainly caused by the human body and the pillar between the target node and the base stations. A total of 1549 localization cases were conducted. A total of 6196 measured distances and 1549 measured coordinates were obtained for the statistic of ranging accuracy and localization accuracy, respectively.

Figure 8.

Measurement scenario of field testing.

Results and analysis

Similar to the result of simulation, the range error distribution of the proposed algorithm fits the Gaussian distribution effectively, and the mean values are mostly equal to 0, as shown in Figure 9(c). The other two algorithms are evidently unable to satisfy the assumption of zero mean and the same variance, as shown in Figure 9(a) and (b). Figure 10 shows the comparison of cumulative distribution of these five ranging errors. Table 3 compares the means and variances of the ranging errors. Figure 11 and Table 4 show the comparison between the performances of the localization errors. Similar to the simulation, the proposed solution still achieves the best accuracy in all the comparisons of field testing. However, the performance of NLOS mitigation–based solution in field testing is significantly lower than that in the simulation because the distribution of realistic ranging error is much more complex than that of simulation. Thus, the NLOS mitigation algorithms cannot estimate the ranging error accurately. The performance of the proposed algorithm in field testing is still close to that in the simulation because of the comprehensive effect of NLP algorithm and the appropriate setting of initial value, objective function, and constrained conditions. The performance comparison of field testing further indicates the necessity of matching the distribution of ranging error to Gauss–Markov theorem for LS-based indoor positioning.

Figure 9.

Distance error probability distribution comparison in field testing.

Figure 10.

Comparison of cumulative error probability distribution curves in field testing.

Figure 11.

Comparison of cumulative probability distribution curves in field testing.

Table 3.

Comparison of mean and variance of range error in field testing.

	Measured error	NLP with GC	NLOS mitigation 1	NLOS mitigation 2	The proposed method
Mean (m)	1.13	0.86	–0.21	0.45	0.04
Variance (m²)	0.67	0.37	0.50	0.58	0.35

NLP: nonlinear programming; NLOS: nonline of sight; GC: geometric constraint.

Table 4.

Comparison of mean and variance of positioning error in field testing.

	LS	LS + NLP with GC	Taylor	LS + NLOS mitigation 1	The proposed method
Mean (m)	5.41	3.22	3.61	4.16	1.28
Variance (m²)	45.44	0.96	0.88	11.17	1.25

LS: least square; NLP: nonlinear programming; NLOS: nonline of sight; GC: geometric constraint.

Conclusion

The LS algorithm is one of the commonly used algorithms in the 3D indoor TOA positioning. The biggest challenge of applying the LS algorithm in the indoor TOA positioning is that ranging error cannot satisfy the Gauss–Markov theorem, the prerequisite of which is the optimal unbiased estimation.

A range value optimization algorithm based on nonlinear programming is proposed to solve the problem on ranging error distribution that does not satisfy the zero mean and equal variance and further improve the ranging accuracy. The distance optimization is defined as an NLP problem by setting the initial value, objective function, and constrained condition according to the feature of TOA-based indoor 3D localization. Finally, the overall solution of 3D indoor TOA positioning based on the LS and nonlinear program is determined. Simulation results and field testing show that through the proposed optimization algorithm, the mismatch problem of ranging error can be successfully solved. Furthermore, the ranging and the positioning accuracies are significantly improved. The proposed method can also be applied to two-dimensional (2D) localization scenarios.

Footnotes

Academic Editor: Qi Han

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (NSFC) project no. 61671056, Beijing Natural Science Foundation project no.4152036, and Tianjin Major Science and Technology project no. 16ZXCXSF00150.

References

Amundson

Koutsoukos

. A survey on localization for mobile wireless sensor network: Mobile entity localization and tracking in GPS-less environments. Berlin: Springer, 2009, pp.235–254.

Heidari

Akgul

Pahlavan

. Identification of the absence of direct path in TOA-based indoor localization systems. Int J Wirel Inf Netw 2008; 15(3–4): 117–127.

Heidari

Alsindi

Pahlavan

. UDP identification and error mitigation in toa-based indoor localization systems using neural network architecture. IEEE T Wirel Commun 2009; 8(7): 3597–3607.

Wann

Chin

. Hybrid TOA/RSSI wireless location with unconstrained nonlinear optimization for indoor UWB channels. In: 2007 IEEE wireless communications and networking conference, Kowloon, China, 11–15 March 2007, pp.3940–3945. New York: IEEE.

Decawave. DW1000 Datasheet V2, https://www.decawave.com/sites/default/files/resources/DW1000-Datasheet-V2.11.pdf, 2014.

Nanotron. nanoLOC TRX Transceiver (NA5TR1) datasheet, http://data.leocom.kr/datasheets/107593_73752.pdf, 2006.

Jie

Geng

Liu

et al . CC-KF: enhanced TOA performance in multipath and NLOS indoor extreme environment. IEEE Sens J 2014; 14(11): 3766–3774.

Casas

Marco

Guerrero

et al . Robust estimator for non-line-of-sight error mitigation in indoor localization. EURASIP J Appl Sig Proc 2006; 2006: 043429.

Sayed

Tarighat

Khajehnouri

. Network-based wireless location: challenges faced in developing techniques for accurate wireless location information. IEEE Sig Proc Mag 2005; 22(4): 24–40.

10.

Khodjaev

Park

Malik

. Survey of NLOS identification and error mitigation problems in UWB-based positioning algorithms for dense environments. Ann Telecomm 2009; 65: 301–311.

11.

Shuai

Dong

W-S

. Localization algorithms for asynchronous time difference of arrival positioning systems. EURASIP J Wireless Comm Netw 2017; 2017: 64.

12.

Kosuge

Koga

Miyazaki

et al . Performance of time sum of arrival based location system by Taylor-Series Estimation. IEICE Trans 2016; 99: 966–975.

13.

Rao

NSV

Sahni

. A computational geometry method for DTOA triangulation. In: International conference on information fusion, Quebec, Canada, 9–12 July 2007, pp.1–7. New York: IEEE.

14.

Jie

Qin

Qianxiong

et al . Modeling ranging error of indoor TOA-based position system based on receive signal strength. Int Sens Netw 2013; 13(4): 162–172.

15.

Arias-De-Reyna

Mengali

. A maximum likelihood UWB localization algorithm exploiting knowledge of the service area layout. Wirel Pers Commun 2013; 69(4): 1413–1426.

16.

Park

C-H

Chang

J-H

. TOA source localization based on weighted least square estimator in LOS/NLOS mixture environments. International J of Distrib Sens N. Epub ahead of print 1 December 2016. DOI: 10.1177/1550147716683827.

17.

Park

C-H

Chang

J-H

. Robust time-of-arrival source localization employing error covariance of sample mean and sample median in line-of-sight/non-line-of-sight mixture environments. EURASIP J Adv Sig Pr 2016; 2016: 89.

18.

Liang

Liao

Lee

. Localization algorithm based on improved weighted centroid in wireless sensor networks. J Netw 2014; 9(1): 183–189.

19.

Wang

Zheng

Wiemeler

et al . Reference selection for hybrid TOA/RSS linear least square localization. In: 2013 IEEE 78th vehicular technology conference (VTC Fall), Las Vegas, NV, 2–5 September 2013, pp.1–5. New York: IEEE.

20.

Chu

Ganz

. A UWB-based 3D location system for indoor environments. In: 2nd international conference on broadband networks, Boston, MA, 3–7 October 2005, pp.1147–1155. New York: IEEE.

21.

Ivanov

. Asymptotic expansions related to the least square estimator. In: Ivanov

(ed.) Asymptotic Theory of Nonlinear Regression. Berlin: Springer, 1997, pp.155–250.

22.

Akgul

. Modeling the behavior of multipath components pertinent to indoor geolocation. Worecester, MA: Worcester Polytechnic Institute, 2010.

23.

Cao

Anderson

BDO

Morse

. Sensor network localization with imprecise distances. Systems Control Lett 2006; 55(11): 887–893.

24.

Geng

Pahlavan

. Toward accurate human tracking: Modelling time-of-arrival for Wireless Wearable Sensors in multipath environment. IEEE Sens J 2014; 14(11): 3996–4006.

25.

Marano

Gifford

Wymeersch

et al . NLOS identification and mitigation for localization based on UWB experimental data. IEEE J Sel Area Comm 2010; 28(7): 1026–1035.

26.

Boggs

. Sequential quadratic programming. Acta Numer 1996; 4: 1–52.

27.

Alavi

Pahlavan

. Modeling of the TOA based distance measurement error using UWB indoor radio measurements. IEEE Comm Lett 2006; 10(4): 275–277.

28.

Ghassemzadeh

Tarokh

. The ultra-wideband indoor path loss model. Report IEEE P802.15–02/277r1-SG3a, July 2002. Florham Park, NJ: AT&T Labs.