# NLOS Mitigation for TOA Location Based on  a Modified Deterministic Model

Authors: Hong Tang; Yongwan Park; Tianshuang Qiu
Journal: Research Letters in Signal Processing
 (2008)

---

## Abstract

Wireless location becomes difficult due to contamination of measured time-of-arrival (TOA) caused by non-line-of-sight. In this letter, TOA measurements seen at base stations are adjusted by scale factors, and a modified deterministic model is built. An effective numerical solution is proposed to resolve the scale factors and mobile position. A simulation comparison of four algorithms indicates that the proposed algorithm outperforms the other three algorithms.


---

## Body

## 1. Introduction

For outdoor
wireless location, most time-of-arrival- (TOA-) based algorithms are derived
from deterministic model. The mobile position is commonly modeled as the
intersection of a set of circles defined by TOA ranges. Non-line-of-sight (NLOS)
propagation is one of the major concerns. The field trials in [1] performed by
Nokia showed that the positive range error due to NLOS is up to a thousand
meters in some channel environments. NLOS is a key problem to improve location
accuracy.In recent years,
very important contributions to the TOA-based location have been made to
compute the mobile position using TOA measurements. And the least-square (LS) criterion
is often used to compute the estimate of mobile position, which is optimal if
the residual follows Gaussian distribution. For example, the “time of arrival
data fusion" based on LS criterion in [2] is a closed-form solution for mobile
position. A constrained nonlinear LS approach was proposed in [3] to minimize
the residual. In [4], the quadric programming technique is used to find the ML
estimation of the mobile position subjected to constraint from the inequalities
introduced due to NLOS propagation. In the range scaling algorithm (RSA) in [5],
the NLOS is mitigated using TOA adjustment by scaling NLOS-corrupted TOA
measurements using factors that are estimated from a constrained nonlinear
optimization process. But RSA is only valid for three base stations (BSs)
scenario, and the optimization process is very complex.In this
letter, scale factors are employed to adjust TOA measurements seen at base
stations, and a modified deterministic model is proposed. An effective solution
is used to resolve the mobile position, which does not require prior knowledge
of NLOS distribution or time-based history measurements.


## 2. Deterministic Model for TOA-Based Location

It is assumed
thatM BSs are involved in the location process. The
TOA-based range measurements are modeled as (1)ri=di+Li+vi,i=1,…,M, where ri is the pseudorange between the ith BS and mobile station (MS), di is the LOS distance, and Li is the excess distance due to NLOS. vi is the sum of other errors caused by system
delay, synchronization error, measurement noise, and so forth. Let the mobile
position be x=[x,y]T, and let the position of the ith BS be xi=[xi,yi]T.
Define ei(x)=ri−∥x−xi∥ as the residual, where ∥⋅∥ denotes the norm operator, and ∥x−xi∥ represents the distance between vectors x and xi. A generalized estimator normally used for TOA in determinate models is(2)x^=argx⁡min⁡∑i∈Sρ(ei), where S is the index set of BSs. ρ(⋅) is an optimal function of the residual. The determinate model in [3] was chosen as minx⁡∑i∈Sαi2ei2, where αi is the weight reflecting the
reliability of the signal received at BS i,
and ρ(⋅) in [6] was selected as a robust function with
more tolerance for outliers. To locate mobile position in presence of NLOS
propagation, an alternative way is to shift view to ei in a modified deterministic model.


## 3. A Modified Deterministic Model and Numerical Solution

The fact that
NLOS propagation causes positive range error means that the following
inequality holds:(3)ri−∥x−xi∥≥0. In order to change (3) into equality, let βi be the scale factor on the range measurements,
which yields (4)βiri−∥x−xi∥=0. Each βi must be less than or equal to one.
Furthermore, each βi has a lower bound. For example, three BSs are involved
in the location process, as seen in Figure 1. The mobile must lie in the
overlapped region formed by I1,I2, and I3.
Let ηi be the lower bound of βi.
We find that η1=O1I1/r1.
In a similar way, we get η2=O2I2/r2 and η3=O3I3/r3.
Thus, βi must be constrained by (5)ηi≤βi≤1,i=1,…,M.Figure 1
The geometry of three
circles shows the constraints on the scale factors.Defineei′(x)=βiri−∥x−xi∥ as the modified residual in this letter. This residual
will be zero or sufficient small if the scale factors are selected accurately. Thus,
the modified deterministic model is defined as (6)x^=argx⁡min⁡∑i=1M(βiri−∥x−xi∥)2. Subject to (7)ηi≤βi≤1. Let the objective
function which is minimized for TOA location be (8)g(x)=∑i=1M(βiri−∥x−xi∥)2.Clearly, (8)
will be exactly zero with the true scale factors and true position. The
sequential quadratic programming (SQP) technique is employed to study the
performance surface of the objective function. We find that it has many local
minimums in the overlapped region, and these minimums skirt the true mobile
position.Because of the
difficulty in determining a closed-form solution for (8), we propose a numerical
solution to resolve the scale factors and mobile position by the following
steps.(1)
Compute
the lower boundηi for i=1,…,M.(2)
Generate a random variableε over [01] with a predefined distribution. The predefined
distribution of ε is different in different channel environments.
Typically, the channel environments can be classified as open area, mountains,
suburban, urban, and bad urban.(3)
Let the
scale factors equalβi=ηi+(1−ηi)ε for i=1,…,M and compute the mobile position as follows.
Equation (8)
is quadratic about x and y.
Calculate the derivatives with respect to x and y,
and let the derivatives be zero. The estimate of the mobile position is (9)x^=(∑i=1Mei′∥x^−xi∥)−1∑i=1Mxiei′∥x^−xi∥,y^=(∑i=1Mei′∥x^−xi∥)−1∑i=1Myiei′∥x^−xi∥. An interesting result from (9) is that the mobile position estimate
is the linear combinations of the positions of all BSs. The tap weight of each
linear combination is (∑i=1M(ei′/∥x^−xi∥))−1(ei′/∥x^−xi∥).
However, we must note that (9) is not the closed-form solution because ∥x^−xi∥ and ei′ are still functions of x^ and y^.
Following the similar steepest descendent technique as illustrated in [3], the estimate
of mobile position is (10)x^(k+1)=x^(k)−ux∑i=1M(x^(k)−xi)ei′(x^(k))∥x^(k)−xi∥,y^(k+1)=y^(k)−uy∑i=1M(y^(k)−yi)ei′(x^(k))∥x^(k)−xi∥, where ux and uy are the step sizes, and k is the iteration number.(4)
Substitute the scale factorsβi and mobile position estimate [x^,y^] into (8), and calculate the exact value of g(x^,y^).(5)
Repeat
steps, (2)–(4)N times. We get a set of the scale factors Πβ={β1n,β2n,…,βMn,n=1,…,N},
a set of mobile position Πx,y={x^n,y^n,n=1,…,N}, and a set of exact value of objective function ΠJ={gn(x^n,y^n),n=1,…,N}.(6)
Find
the minimumgp(x^p,y^p) in ΠJ,
where p is the index. Then, (x^p,y^p) in Πx,y is the final estimate for mobile position, and {β1p,β2p,…,βMp} in Πβ are the final estimates for scale factors.The random variableε controls the step size of the scale factors
while we search them in solution space. Without any prior knowledge, we apply
the same ε on each scale factor in step (3) to limit the
solution space. In step (6), both the scale factors and the mobile position that minimizes
the objective function are taken as the final estimates. This scheme to select
scale factors is reasonable because it follows the physical meaning of the modified
deterministic model. Clearly, the final estimates cannot make the objective
function exactly zero. But, they can guarantee it to be a relatively small
number. A notable advantage of the numerical process is that compared to the
complex nonlinear optimization processes as illustrated in RSA [5], the
complexity to search the scale factors is reduced. In addition, the proposed
algorithm can be applied to the scenarios of more than three BSs; however,  RSA is difficult to be applied
in these scenarios.


## 4. Simulations

The
simulations are conducted in a cellular network composed of hexagonal cells
with radius of 1000 meters. The mobile station is assumed uniformly distributed
in the central cell. And the mobile position is computed based on TOA
measurements from the six nearest BSs. In scenario 1, the excess rangeLi due to NLOS propagation is modeled as positive
random variables over [0400] meters, generated according to CDSM [5, 7]. To
study the performance in a high NLOS environment, the “reverse” CDSM is used. Without
knowledge of the channel environment, the variable ε in the proposed algorithm is uniformly generated
over [01],
and the number of attempts is 10, that is, N=10.
The range error vi is caused by system delay, synchronization
error, measurement noise and is typically smaller in magnitude than NLOS error.
As an example, vi is modeled as a Gaussian variable with mean
100 meters and variance 30 meters. The performances are compared with the LS
algorithm, that is, “time of arrival data fusion" algorithm in [2], the
algorithm in [3], and the Huber-estimator mentioned in [6]. The root mean
square errors of the four algorithms with the two NLOS models are shown in Figure 2.Figure 2
The root mean square errors
with CDSM and reverse CDSM.In scenario 2, another model
considered is a range-dependent NLOS model [8]. The NLOS error is proportional
to the BS-MS range, that is, the NLOS error for the ith BS is taken to be Li=χdi,
where χ is a proportionality constant. The root mean
square errors with the proportional NLOS model are shown in Figure 3. It is
found that the performance of the other three algorithms degrade greatly with
increasing χ, and the proposed algorithm is robust with χ.Figure 3
The root mean square errors with
range-dependent model.


## 5. Conclusions

A modified
deterministic model with a new residual is built to compute the mobile position.
Due to the difficulty to find a closed-form solution, an effective numerical
solution is proposed to resolve the scale factors and the mobile position. A
simulation comparison among four algorithms is conducted to evaluate their
performance. The results indicate that the proposed algorithm can deal with
NLOS effectively and is simple to be implemented.



---

*Source: 970461-2008-04-24.xml*