Open AccessArticle

Performance Comparison of Closed-Form Least Squares Algorithms for Hyperbolic 3-D Positioning

Mohamed Khalaf-Allah

Institute of Traffic Telematics, Technische Universität Dresden, 01062 Dresden, Germany

J. Sens. Actuator Netw. 2020, 9(1), 2; https://doi.org/10.3390/jsan9010002

Submission received: 19 November 2019 / Revised: 13 December 2019 / Accepted: 15 December 2019 / Published: 20 December 2019

(This article belongs to the Special Issue Localization in Wireless Sensor Networks)

Download

Browse Figures

Versions Notes

Abstract

An accurate 3-D wireless local positioning system (LPS) is a highly demanded tool for increasing safety in, e.g., emergency response and security operations. An LPS is an attractive approach that can meet stringent requirements and can achieve acceptable accuracies for a long time during extended operations in global navigation satellite system (GNSS)-denied environments. In this work, three closed-form (CF) least squares (LS) algorithms were considered, where two of them were adapted to exploit the knowledge about nuisance parameters for accurate 3-D positioning based on time difference of arrival (TDoA) measurements. The algorithms utilize the single set (SS) of the TDoA measurements, an extended SS (ExSS) of the TDoA measurements, or the full set (FS) of the TDoA measurements, and were denoted, respectively, as the CFSSLS, CFExSSLS, and CFFSLS solutions. The performance of the algorithms was investigated with simulations and real-world measurements, where the wireless system transmitters were placed in a quasi-coplanar arrangement. At moderate to high signal-to-noise ratio (SNR) levels, the CFSSLS solution has the best performance, followed by the CFExSSLS solution and then by the CFFSLS solution. At low SNR levels, the CFFSLS algorithm outperformed the other two algorithms. Both the CFSSLS and CFFSLS solutions estimate nuisance parameters that are utilized in refining the vertical position estimate of the receiver. The CFFSLS solution delivers more accurate refined vertical position estimates since it utilizes more nuisance parameters, i.e., more information. The experimental results confirmed the simulation study in which the CFFSLS algorithm outperformed the other two algorithms, where the experimental environment was dominated by total non-line-of-sight (NLoS) conditions and low SNR levels at the receiver to be located. Therefore, it is recommended to use the FS TDoA measurements for 3-D positioning in bad signal conditions, such as high noise levels and NLoS propagation.

Keywords:

time difference of arrival (TDoA); least squares (LS) algorithms; closed-form (CF) solutions; wireless positioning; local positioning system (LPS); nuisance parameters

1. Introduction

Determining the position of a receiver based on signal measurements from an array of spatially separated transmitters with well-known locations has been, and is still, an important issue in wireless sensor networks, mobile communications, radar, sonar, and global navigation satellite system (GNSS) applications. Position information is also the key enabler for a constantly increasing number of innovative services and applications. New applications increase the demand for positioning systems where the GNSS signals are denied, e.g., indoors. Current local positioning systems (LPSs) may fail to meet the requirements of certain applications such as indoor emergency operations, e.g., fire-fighting, security and military missions, due to the need for a pre-installed radio frequency (RF) infrastructure. The rapid deployment of a portable infrastructure for positioning during emergency operations may not allow us to carry out extensive calibrations and signal characterization in the target environment, in order to optimize positioning algorithms and increase their position solution accuracy.

RF-based LPSs use wireless technologies to estimate the position of the receiver in areas where no GNSS reception is available. Therefore, positioning based on wireless technologies is an active research area. The commonly used signal measurements for positioning, i.e., location-dependent parameters, include time measurements, i.e., time of arrival (ToA), time difference of arrival (TDoA), and round-trip time of flight (RToF), phase measurements, i.e., phase of arrival (PoA) and phase difference of arrival (PDoA), frequency-based measurements, i.e., signal Doppler frequency (SDF) and frequency difference of arrival (FDoA) (also called differential Doppler (DD)), received signal strength (RSS), and angle of arrival (AoA) of the transmitted signal in addition to hybrid signal measurements, e.g., ToA/RSS, ToA/AoA or TDoA/FDoA. Distance information or range between the receiver and the transmitters can be extracted from ToA, TDoA, RToF, PoA, PDoA, and RSS measurements. The nonlinear relationships of these measurements with the receiver’s position render positioning a nontrivial task.

ToA techniques use the signal propagation time to calculate the distance between the transmitter and the receiver, provided the signal propagation speed in the medium is known [1]. Strict synchronization between transmitters and the receiver is required. The TDoA method exploits the difference in signals’ propagation times from different transmitters, measured at the receiver. Synchronization is required only between the transmitters. The positioning accuracy of ToA and TDoA approaches depends on the signal bandwidth and sampling rate at the receiver. The accuracy degrades in non-line-of-sight (NLoS) conditions. RToF measures the round-trip, i.e., transmitter–receiver–transmitter, signal propagation time to estimate the distance. Therefore, only moderate clock synchronization between the transmitters and the receiver is required. RToF estimation accuracy is also affected by the sampling rate and signal bandwidth, but even more severely due to the two-way signal propagation. Moreover, the response delay at the receiver further deteriorates the accuracy [1].

Phase measurement approaches exploit the phase or phase difference of the carrier signal to estimate the distances between the transmitters and the receiver. The transmitted signals are commonly assumed to be purely sinusoidal, having the same frequency and zero phase offset [2]. Line-of-sight (LoS) conditions are required for high positioning accuracy.

Techniques for radio source location based on the Doppler effect include SDF and FDoA approaches. SDF methods [3] estimate the Doppler frequency shifts in received signals from radio sources and can be implemented by a single portable receiver. Spectrum analysis techniques enable the simultaneous localization of multiple radio sources [4]. In FDoA methods [5], the signal of a stationary radio source is intercepted by at least two moving receivers, and the frequency difference between the receivers is measured at several positions along their trajectories in order to determine the radio source location. For accurate FDoA estimates, the receivers’ frequencies have to be precisely synchronized.

The RSS-based approach is a simple, cost-efficient, and widely used method [6]. The actual signal power strength received at the receiver is used to estimate the distance to the transmitter, where the higher the RSS value the smaller the distance. The positioning accuracy is generally poor due to multipath fading and especially in NLoS situations.

AoA-based approaches use antenna arrays [7] at the receiver side. The TDoA at individual elements of the array are calculated to estimate the angle at which the transmitted signal impinges on the receiver. AoA-based positioning provides accurate estimation at small transmitter–receiver distances. With increasing distances and multipath effects, the accuracy deteriorates significantly.

Most positioning systems use the conventional suboptimal two-step approach, in which measurements, i.e., location-dependent parameters, are first extracted from the signals and then used for position determination. On the other hand, direct position determination (DPD) [8,9,10] performs positioning in a single step and without first estimating the location-dependent parameters. However, the DPD often needs to minimize a nonconvex cost function in order to estimate the position, which demands high computational resources.

The focus in this article is on conventional hyperbolic positioning, i.e., TDoA-based positioning, where the position fix is computed from a set of intersecting hyperbolic curves generated by TDoA measurements. A summary of the most popular circular, i.e., ToA-based, and hyperbolic positioning algorithms is presented in ref. [11]. When the positioning algorithm assumes an additive measurement error model, the available approaches include the maximum likelihood (ML) and the least squares (LS) approaches, which are implemented as iterative or non-iterative, i.e., closed-form (CF) algorithms. The nonlinear hyperbolic equations were linearized by using the Taylor series expansion and solved iteratively in [12,13] using the LS estimator (LSE). If the initial guess of the position estimate is not accurate enough, the convergence to the global solution cannot be guaranteed. Gradient-based techniques, such as the quasi-Newton technique [14] and the Gauss–Newton-type Levenberg–Marquardt method [15], have also been used in iterative algorithms. The ML solution to the hyperbolic equations [16] is widely used due to the proven asymptotic consistency and efficiency of the ML estimator (MLE), which requires assumptions about the distribution of measurement errors. However, the iterative algorithm to find the solution is computationally intensive.

In this article, three CF LS algorithms, i.e., closed-form single set least squares (CFSSLS) [17], closed-form extended single set least squares (CFExSSLS), which is based on the direct method (DM) algorithm in ref. [18], and closed-form full set least squares (CFFSLS) [19], are presented to estimate the 3-D position of a receiver using wireless signal TDoA measurements. Two algorithms, namely, CFSSLS and CFFSLS, estimate nuisance parameters. Therefore, both algorithms are extended, according to refs. [19,20], respectively, to benefit from the nuisance parameter information in refining, i.e., minimizing the error in, the vertical position estimates. Moreover, a design parameter is introduced to control the amount of nuisance parameter information to be used. The DM algorithm in ref. [18], which requires exactly five transmitters, is extended to work with an arbitrary number of transmitters, i.e.,

N \geq 5

, in order to obtain an LS position solution called the CFExSSLS algorithm. With coplanar transmitters, only 2-D position estimates can be obtained. To obtain 3-D position estimates, a height sensor might be required, or transmitters have to be placed at enough different heights to create the necessary good geometry for 3-D positioning. Simulations and experiments are carried out to confirm the capacity of the adapted algorithms to obtain 3-D position estimates with coplanar transmitters in challenging wireless signal conditions and without any extra sensors.

The rest of the article is organized as follows. Related work is discussed in Section 2. In Section 3, CF LS algorithms for TDoA-based 3-D positioning are developed. The utilization of nuisance parameters is introduced in order to refine the vertical position estimates when transmitters are placed in a coplanar arrangement. The setup and results of the simulation study and the conducted experiments are presented in Section 4. The findings are then discussed in Section 5 and conclusions are given in Section 6.

2. Related Work

In the following, some useful material has been adopted from ref. [19] and is indicated by citing at the end of the adoption. CF, i.e., analytical, methods were developed to overcome convergence problems, where a nuisance parameter, i.e., the range from the receiver to the master transmitter, is introduced to the set of the linearized equations. CF or analytical solutions are desirable because they usually have fewer computational loads than iterative methods or ML approaches [19]. Moreover, CF algorithms achieve estimation accuracies at acceptable levels, are mathematically simple, robust, and easy to implement for practical real-time applications, where low computational time and memory storage requirements are of high priority to meet imposed power constraints. Another important class of techniques is the DMs, e.g., refs. [21,22,23], which are algebraic, i.e., exact, solutions to the TDoA equations. However, their accuracy depends heavily on the accuracy of the measurements and works with a certain number of equations, i.e., they do not make use of the additional available measurements but the exactly required. Nevertheless, DMs may be desirable since they do not involve any matrix operations. DMs and CF LS algorithms still have two major advantages: They do not need an initial position estimate to run, and they do not require any probabilistic assumptions about the distribution of the measurement errors and therefore can be employed when the precise characterization of measurement errors cannot be determined.

The total number of TDoA measurements that can be generated with N transmitters is

\frac{N (N - 1)}{2}

and is referred to as the full set (FS) measurements [24]. If only measurements with respect to a single master transmitter are considered, they are referred to as the single set (SS) measurements, and their total number is

N - 1

. Any transmitter can be considered as master, and thus, a number of N SSs can be constructed [19]. Any SS represents an independent set of measurements. The FS extends any SS by considering all possible linear combinations of the SS measurements. Thus, the FS also contains only

N - 1

independent measurements, and the remaining ones (constructed by linear combinations) are dependent, i.e., redundant, measurements. When the SS and some extra measurements (less than the FS) are used for the position estimation, the set of measurements is referred to as the extended single set (ExSS).

CF unconstrained and constrained LS solutions using an SS of the TDoA measurements are well described in ref. [17] and can be denoted as CFSSLS solutions. The CFSSLS algorithms developed in refs. [25,26] are called the spherical interpolation (SI) and the linear correction LS (LCLS), respectively. Both algorithms require range measurements which may not be available or may not be accurate enough due to clock synchronization errors, and are, respectively, equivalent to the unconstrained CFSSLS and constrained CFSSLS solutions in ref. [17] that depend only on TDoA measurements, as correctly indicated in ref. [27]. The constrained CFSSLS solution of ref. [17] was repeated in ref. [28] with corrections stated in ref. [29]. The extension of the CFSSLS solution as suggested in ref. [28] yielded an algorithm that utilizes two SSs of TDoA measurements made with respect to two reference transmitters, i.e., the total number of used measurements is

2 (N - 1)

, where only

N - 1

measurements are independent [19]. The DM solution in ref. [21] requires exactly four transmitters and uses an SS of the TDoA measurements, i.e., three independent measurements. The DM solution in ref. [18] uses exactly

N = 5

transmitters and depends on an ExSS, where the number of TDoA measurements used is

(N - 1) + (N - 2) = 7

, i.e.,

N - 1 = 4

independent and

N - 2 = 3

dependent (redundant) measurements. Both DM solutions in refs. [22,23] require exactly four transmitters to work. The method in ref. [22] uses four TDoA measurements; an SS, i.e., three independent measurements, in addition to one dependent measurement from the FS. The algorithm in ref. [23] utilizes five TDoA measurements from two SSs, where one measurement is common to both SSs. The CF LS solution using an FS of the TDoA measurements is introduced in ref. [19] and can be denoted as CFFSLS solution. This CFFSLS algorithm was used in ref. [30] with a data-selective procedure to discard bad measurements.

3. Materials and Methods

Simulations were conducted to investigate the performance of the proposed algorithms in order to better interpret the results of the real measurements. The performance of the algorithms was evaluated in terms of the root mean square error (RMSE) of the 3-D position estimates at a range of signal-to-noise ratio (SNR) levels. Details on the simulation setup and results are presented in Section 4.1 and Section 4.2, respectively. To obtain real-world measurements, a wireless transmitter system was utilized to estimate the position of an indoor passive receiver using TDoA measurements. The system consists of a set of transmitting stations (TSs) located around the target building, user terminals (UTs) or receivers inside the building, and a monitoring and control unit (MCU) for steering the TSs and for broadcasting information to the UTs. TSs broadcast multicarrier navigation signals at 420 with 40 MHz bandwidth. The signal design allows minimizing multipath effects in harsh indoor environments, such as massive multilevel buildings made of concrete, steel, and metal-shielded windows. System architecture, details, and measurement examples are given in ref. [31] and references therein.

The following mathematical treatment is partially adopted from ref. [19] for convenience and is indicated by a citation before the equation. Consider an array of N transmitters located at known positions

a_{i} = [x_{i}, y_{i} {, z_{i}]}^{T}

, in a 3-D Cartesian coordinate system, where i = 1, …, N and

T

is the transpose operator, and a passive receiver, at an unknown position

a_{r} = [x_{r}, y_{r} {, z_{r}]}^{T}

, observing signals radiating from the transmitters. The receiver measures the TDoA of a pair of signals radiated by any pair of transmitters i and j, where

i \neq j

. The TDoA measurement,

τ_{i j}

, is related to the range difference,

d_{i j}

, by the relation:

d_{i j} = c \cdot τ_{i j}

, where c is the known propagation speed of the signal in the medium. Thus,

d_{i j}

is expressed in the error-free case as [19]:

d_{i j} = ‖ a_{j} - a_{r} ‖ - ‖ a_{i} - a_{r} ‖,

(1)

where i = 1, …, N, j = 1, …, N,

i \neq j

, and

‖ \cdot ‖

denotes the Euclidean vector norm. The problem, thus, is to estimate the vector

a_{r}

given a set of

d_{i j}

, i.e.,

τ_{i j}

, noisy measurements and using the known vectors

a_{i}

, which in turn might contain uncertainties.

3.1. Closed-Form Single Set Least Squares Solution

LSE makes no assumptions about the statistical characteristics of the measurement errors and therefore is an attractive alternative if the statistics of measurement errors cannot be determined accurately. Moreover, a CF estimator would be advantageous for practical real-time applications. The LSE minimizes a squared error function called the cost function. In the absence of measurement errors and transmitter position uncertainties, the LSE minimization will yield a zero-cost function. From Equation (1), we can get [19]:

{‖ a_{j} - a_{r} ‖}^{2} = {[d_{i j} + ‖ a_{i} - a_{r} ‖]}^{2} .

(2)

With straightforward algebra, Equation (2) yields [19]:

d_{i j} \cdot ‖ a_{i} - a_{r} ‖ + {[a_{j} - a_{i}]}^{T} \cdot a_{r} = \frac{{‖ a_{j} ‖}^{2} - {‖ a_{i} ‖}^{2} - d_{i j}^{2}}{2} .

(3)

Without loss of generality, the first transmitter is considered as the master transmitter. Thus, Equation (3) is rewritten as [19]:

d_{1 j} \cdot ‖ a_{1} - a_{r} ‖ + {[a_{j} - a_{1}]}^{T} \cdot a_{r} = b_{1 j},

(4)

Where

b_{1 j} = \frac{{‖ a_{j} ‖}^{2} - {‖ a_{1} ‖}^{2} - d_{1 j}^{2}}{2}

and j = 2, …, N. The LSE would minimize a cost function,

f_{c}^{S S}

, which is expressed as [19]:

f_{c}^{S S} = \sum_{j = 2}^{N} {(d_{1 j} \cdot ‖ a_{1} - a_{r} ‖ + {[a_{j} - a_{1}]}^{T} \cdot a_{r} - b_{1 j})}^{2} .

(5)

Equation (4) can be expressed in matrix form as

H_{SS} s_{SS} = b_{SS}

, where [19]:

H_{SS} = [\begin{matrix} \begin{matrix} d_{12} \\ d_{13} \end{matrix} & \begin{matrix} {[a_{2} - a_{1}]}^{T} \\ {[a_{3} - a_{1}]}^{T} \end{matrix} \\ \begin{matrix} ⋮ \\ d_{1 N} \end{matrix} & \begin{matrix} ⋮ \\ {[a_{N} - a_{1}]}^{T} \end{matrix} \end{matrix}],

(6)

b_{SS} = {[\begin{matrix} \begin{matrix} b_{12} & b_{13} \end{matrix} & \begin{matrix} \dots & b_{1 N} \end{matrix} \end{matrix}]}^{T},

(7)

and:

s_{SS} = [\begin{matrix} ‖ a_{1} - a_{r} ‖ \\ a_{r} \end{matrix}] .

(8)

Note that

H_{SS}

is a

(N - 1) \times 4

matrix,

b_{SS}

is a

(N - 1) \times 1

column vector, and

s_{SS}

is a

4 \times 1

column state vector, where the range

‖ a_{1} - a_{r} ‖

to the master transmitter is a nuisance parameter. The cost function in Equation (5) can, thus, be rewritten using the matrix notation as

f_{c}^{S S} = {‖ H_{SS} s_{SS} - b_{SS} ‖}^{2}

. The unconstrained CFSSLS solution of

s_{SS}

reads [19]:

{\hat{s}}_{SS} = {(H_{SS}^{T} H_{SS})}^{- 1} H_{SS}^{T} b_{SS} .

(9)

and the corresponding estimate of

a_{r}

is given as [19]:

{\hat{a}}_{r} = [\begin{matrix} \begin{matrix} 0 & 1 \end{matrix} & \begin{matrix} 1 & 1 \end{matrix} \end{matrix}] {\hat{s}}_{SS} .

(10)

We originally estimate the

4 \times 1

state vector

s_{SS}

. Therefore, we need at least four independent TDoA measurements with respect to a common master transmitter. That is, at least five transmitters are required in order to obtain a 3-D CF solution [19].

In a practical LPS, transmitters are often installed in coplanar or quasi-coplanar arrangements, see Figure 1. Such an arrangement is a major challenge for accurate 3-D positioning, namely, the vertical component of the 3-D position estimate is of poor accuracy, and therefore, the LPS would be useless for applications requiring accurate 3-D position estimates. The problem can be fixed by utilizing the nuisance parameter of the CFSSLS solution [20], which is the first element in the state vector,

s_{SS}

, in Equation (8).

When coplanar or quasi-coplanar transmitters are used for TDoA measurements at the receiver, the CFSSLS solution of Equation (10) delivers acceptable accuracies for the 2-D, i.e., horizontal, position estimate,

{\hat{x}}_{r}, {\hat{y}}_{r}

, and poor estimates for the vertical position,

{\hat{z}}_{r}

. Using the horizontal position estimate of the receiver,

{\hat{x}}_{r}, {\hat{y}}_{r}

, and the known horizontal coordinates of the first, i.e., master, transmitter,

x_{1}, y_{1}

, the horizontal range from the receiver to the first (master) transmitter,

{\hat{r}}_{1}^{2 D}

, see Figure 2, can be estimated with acceptable accuracy as:

{\hat{r}}_{1}^{2 D} = \sqrt{{(x_{1} - {\hat{x}}_{r})}^{2} + {(y_{1} - {\hat{y}}_{r})}^{2}} .

(11)

The 3-D range from the receiver to the master transmitter,

‖ a_{1} - a_{r} ‖

, i.e., the nuisance parameter, which is the first element in the state vector,

s_{SS}

, in Equation (8), is estimated by the CFSSLS algorithm as

{\hat{s}}_{SS} (1)

and can be denoted as

{\hat{r}}_{1}^{3 D}

, see Figure 2. We can also see from Figure 2 that the difference,

h = z_{r} - z_{1}

, between the vertical position of the receiver (Rx),

z_{r}

, and the vertical position of the master transmitter (Tx),

z_{1}

is estimated as:

\hat{h} = \sqrt{{({\hat{r}}_{1}^{3 D})}^{2} - {({\hat{r}}_{1}^{2 D})}^{2}} .

(12)

Thus, the estimate of the receiver’s vertical position,

{\hat{z}}_{r}

, can be refined by:

{\hat{z}}_{r}^{r e f i n e d} = z_{1} + α \cdot \hat{h},

(13)

where α is a design parameter value, set by the system user, to adjust the amount of information obtained via Equation (12), i.e., the amount of information obtained by the utilization of the nuisance parameter. Thus, full information is included when

α = 1

. When

α = 0

, the vertical position of the receiver is set at the height of the master transmitter, i.e., nuisance parameter information is not included. The steps of the CFSSLS algorithm and the utilization of the nuisance parameter are exhibited in Algorithm 1.

Algorithm 1: The CFSSLS algorithm and refinement of the vertical position estimate.

0. Input: The known transmitters’ coordinates, i.e.,

a_{i} = [x_{i}, y_{i} {, z_{i}]}^{T}

, and the SS range difference measurements, i.e.,

d_{1 j}

, as defined by Equation (4).

1. Compute: The matrix

H_{SS}

and the vector

b_{SS}

as defined by Equations (6) and (7), respectively.

2. Estimate: The state vector

s_{SS}

by LS estimation via Equation (9).

3. CFSSLS Output: The receiver’s 3-D position estimate, i.e.,

{\hat{a}}_{r} = [{\hat{x}}_{r}, {\hat{y}}_{r} {, {\hat{z}}_{r}]}^{T}

, via Equation (10).

4. Estimate: The horizontal range, i.e.,

{\hat{r}}_{1}^{2 D}

, from the receiver to the master transmitter via Equation (11).

5. Estimate: The difference, i.e.,

\hat{h}

, between the vertical positions of the receiver and master transmitter via Equation (12).

6. Refine: The vertical position estimate of the receiver via Equation (13).

7. Output: The final 3-D position estimate of the receiver, i.e.,

{\hat{a}}_{r} = [{\hat{x}}_{r}, {\hat{y}}_{r} {, {\hat{z}}_{r}^{r e f i n e d}]}^{T}

, where

{\hat{x}}_{r}, {\hat{y}}_{r}

were estimated in step 3 and

{\hat{z}}_{r}^{r e f i n e d}

was estimated in step 6.

3.2. Closed-Form Extended Single Set Least Squares Solution

The CF algorithm presented in ref. [18] is essentially based on transforming the hyperbolic equations into a set of vector equations by squaring the set of equations in Equation (1) and then differencing them. It requires a minimum of five transmitters, i.e.,

N = 5

, and uses an SS of the TDoA measurements in addition to extra measurements made by the successive pairs of the rest transmitters, so that the following

(N - 1) + (N - 2) = 7

measurements are used:

d_{21}, d_{31}, d_{41}, d_{51}, d_{32}, d_{43} and d_{54} .

For an arbitrary number of transmitters, i.e.,

N \geq 5

, the simultaneous equations are expressed in algebraic form, see ref. [18] for detailed derivation, as

\begin{matrix} \begin{matrix} a_{11} \cdot x_{r} + a_{12} \cdot y_{r} + a_{13} \cdot z_{r} = b_{1} \\ a_{21} \cdot x_{r} + a_{22} \cdot y_{r} + a_{23} \cdot z_{r} = b_{2} \end{matrix} \\ \begin{matrix} ⋮ \\ a_{(N - 2) 1} \cdot x_{r} + a_{(N - 2) 2} \cdot y_{r} + a_{(N - 2) 3} \cdot z_{r} = b_{N - 2} \end{matrix} \end{matrix}

(14)

where:

\begin{matrix} a_{11} = \frac{2}{d_{21}} (x_{2} - x_{1}) - \frac{2}{d_{31}} (x_{3} - x_{1}) \\ a_{12} = \frac{2}{d_{21}} (y_{2} - y_{1}) - \frac{2}{d_{31}} (y_{3} - y_{1}) \\ a_{13} = \frac{2}{d_{21}} (z_{2} - z_{1}) - \frac{2}{d_{31}} (z_{3} - z_{1}) \\ b_{1} = \frac{1}{d_{21}} (x_{2}^{2} + y_{2}^{2} + z_{2}^{2} - x_{1}^{2} - y_{1}^{2} - z_{1}^{2}) - \frac{1}{d_{31}} (x_{3}^{2} + y_{3}^{2} + z_{3}^{2} - x_{1}^{2} - y_{1}^{2} - z_{1}^{2}) + d_{32} \\ ⋮ \end{matrix}

(15)

The other constants in the set of equations in Expression (14) can be similarly written as in Expression (15). Expression (14) can be put in the matrix form

H_{ExSS} s_{ExSS} = b_{ExSS}

, where

H_{ExSS} = [\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ \begin{matrix} ⋮ \\ a_{(N - 2) 1} \end{matrix} & \begin{matrix} ⋮ \\ a_{(N - 2) 2} \end{matrix} & \begin{matrix} ⋮ \\ a_{(N - 2) 3} \end{matrix} \end{matrix}],

(16)

b_{ExSS} = {[\begin{matrix} \begin{matrix} b_{1} & b_{2} \end{matrix} & \begin{matrix} \dots & b_{N - 2} \end{matrix} \end{matrix}]}^{T},

(17)

and:

s_{ExSS} = a_{r} .

(18)

The dimension of the

H_{ExSS}

matrix is

(N - 2) \times 3

b_{ExSS}

is a

(N - 2) \times 1

column vector and

s_{ExSS}

is a

3 \times 1

column state vector. The matrix notation of the cost function to be minimized by the LSE is given by

f_{c}^{E x S S} = {‖ H_{ExSS} s_{ExSS} - b_{ExSS} ‖}^{2}

. The unconstrained CF LS solution reads

{\hat{a}}_{r} = {(H_{ExSS}^{T} H_{ExSS})}^{- 1} H_{ExSS}^{T} b_{ExSS} .

(19)

This is referred to as the CFExSSLS estimator. Note that only the unknown position vector of the receiver is estimated without any nuisance parameters. Therefore, this algorithm will deliver horizontal position estimates with acceptable accuracy and poor vertical position estimates if coplanar transmitters are used for 3-D positioning. The steps of the CFExSSLS solution are given in Algorithm 2.

Algorithm 2: The CFSSExLS algorithm.

0. Input: The known transmitters’ coordinates, i.e.,

a_{i} = [x_{i}, y_{i} {, z_{i}]}^{T}

, and the ExSS range difference measurements, i.e.,

d_{i 1}, d_{32}, d_{43}, \dots, and d_{N, N - 1} .

1. Compute: The matrix

H_{ExSS}

and the vector

b_{ExSS}

as defined by Equations (16) and (17), respectively.

2. CFExSSLS Output: The receiver’s 3-D position estimate, i.e.,

{\hat{a}}_{r} = [{\hat{x}}_{r}, {\hat{y}}_{r} {, {\hat{z}}_{r}]}^{T}

, by the LS estimation in Equation (19).

3.3. Closed-Form Full Set Least Squares Solution

The set of measurement equations in the SS case is given in Equation (4). Accordingly, the set of measurement equations in the FS case can be straightforwardly written as [19]:

\begin{matrix} d_{1 j} \cdot ‖ a_{1} - a_{r} ‖ + {[a_{j} - a_{1}]}^{T} \cdot a_{r} = b_{1 j}, j = 2, \dots, N \\ d_{2 j} \cdot ‖ a_{2} - a_{r} ‖ + {[a_{j} - a_{2}]}^{T} \cdot a_{r} = b_{2 j}, j = 3, \dots, N \\ ⋮ \\ d_{N - 1, N} \cdot ‖ a_{N - 1} - a_{r} ‖ + {[a_{N} - a_{N - 1}]}^{T} \cdot a_{r} = b_{N - 1, N} \end{matrix},

(20)

where also without loss of generality, the first, second, … and (N − 1)th transmitters are considered in order as reference transmitters, and the corresponding range difference measurements

d_{i j} = - d_{j i}

are considered only once. Expression (20) can also be written in the matrix form

H_{FS} s_{FS} = b_{FS}

, where [19]:

H_{FS} = [\begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} d_{12} & 0 & \dots \end{matrix} \\ \begin{matrix} d_{13} & ⋮ & \dots \end{matrix} \end{matrix} \\ \begin{matrix} ⋮ \\ \begin{matrix} d_{1 N} & 0 & \dots \end{matrix} \end{matrix} \end{matrix} & \begin{matrix} \begin{matrix} \begin{matrix} \dots & 0 & {[a_{2} - a_{1}]}^{T} \end{matrix} \\ \begin{matrix} \dots & 0 & {[a_{3} - a_{1}]}^{T} \end{matrix} \end{matrix} \\ \begin{matrix} ⋮ \\ \begin{matrix} \dots & 0 & {[a_{N} - a_{1}]}^{T} \end{matrix} \end{matrix} \end{matrix} \\ \begin{matrix} \begin{matrix} \begin{matrix} 0 & d_{23} & 0 \end{matrix} \\ \begin{matrix} 0 & d_{24} & 0 \end{matrix} \end{matrix} \\ \begin{matrix} ⋮ \\ \begin{matrix} 0 & d_{2 N} & 0 \end{matrix} \end{matrix} \end{matrix} & \begin{matrix} \begin{matrix} \begin{matrix} \dots & 0 & {[a_{3} - a_{2}]}^{T} \end{matrix} \\ \begin{matrix} \dots & 0 & {[a_{4} - a_{2}]}^{T} \end{matrix} \end{matrix} \\ \begin{matrix} ⋮ \\ \begin{matrix} \dots & 0 & {[a_{N} - a_{2}]}^{T} \end{matrix} \end{matrix} \end{matrix} \\ \begin{matrix} ⋮ \\ \begin{matrix} 0 & \dots & \dots \end{matrix} \end{matrix} & \begin{matrix} ⋮ \\ \begin{matrix} 0 & d_{N - 1, N} & {[a_{N} - a_{N - 1}]}^{T} \end{matrix} \end{matrix} \end{matrix}],

(21)

b_{F S} = {[\begin{matrix} b_{12} & \begin{matrix} b_{13} & \dots & b_{1 N} \end{matrix} & \begin{matrix} \begin{matrix} b_{23} & b_{24} & \dots \end{matrix} & b_{2 N} & \begin{matrix} \dots & b_{N - 1, N} \end{matrix} \end{matrix} \end{matrix}]}^{T},

(22)

and:

s_{F S} = {[\begin{matrix} \begin{matrix} \begin{matrix} ‖ a_{1} & - & a_{r} ‖ \end{matrix} & \begin{matrix} ‖ a_{2} & - & a_{r} ‖ \end{matrix} \end{matrix} & \dots & \begin{matrix} \begin{matrix} ‖ a_{N - 1} & - & a_{r} ‖ \end{matrix} & a_{r} \end{matrix} \end{matrix}]}^{T} .

(23)

The

H_{FS}

matrix has a dimension of

\frac{N (N - 1)}{2} \times (N + 2)

b_{FS}

is a

\frac{N (N - 1)}{2} \times 1

column vector, and

s_{FS}

is a

(N + 2) \times 1

column state vector. The matrix notation of the cost function to be minimized by the LSE is given as

f_{c}^{F S} = {‖ H_{FS} s_{FS} - b_{FS} ‖}^{2}

, and the unconstrained CFFSLS solution for

s_{FS}

is written as:

{\hat{s}}_{FS} = {(H_{FS}^{T} H_{FS})}^{- 1} H_{FS}^{T} b_{FS} .

(24)

Thus, the estimate of

a_{r}

reads:

{\hat{a}}_{r} = [\begin{matrix} \begin{matrix} 0 & \dots & 0 \end{matrix} & \begin{matrix} 1 & 1 & 1 \end{matrix} \end{matrix}] {\hat{s}}_{FS} .

(25)

Note that the number of nuisance parameters, i.e.,

‖ a_{i} - a_{r} ‖

, where

i = 1, \dots, N - 1

, in the

(N + 2) \times 1

column state vector

s_{FS}

given in Equation (23) increased to

N - 1

nuisance parameters, which are 3-D range estimates to the transmitters that were considered as master transmitters in the

H_{FS}

matrix given in Equation (21), i.e., all transmitters with the indices 1 to

N - 1

[19].

The nuisance parameters can also be exploited to refine the vertical position estimate of the receiver using the TDoA measurements from coplanar or quasi-coplanar transmitters in a similar way to the procedure explained in Section 3.1 for the CFSSLS solution. Using the horizontal position estimate of the receiver,

{\hat{x}}_{r}, {\hat{y}}_{r}

, delivered by the CFFSLS solution, see Equations (24) and (25), and the known horizontal coordinates of the transmitters with the indices 1 to

N - 1

, i.e.,

x_{i}, y_{i}

, where

i = 1, \dots, N - 1

, the horizontal ranges from the receiver to these transmitters,

{\hat{r}}_{i}^{2 D},

can be estimated with acceptable accuracy as:

{\hat{r}}_{i}^{2 D} = \sqrt{{(x_{i} - {\hat{x}}_{r})}^{2} + {(y_{i} - {\hat{y}}_{r})}^{2}} .

(26)

The 3-D ranges from the receiver to these transmitters,

‖ a_{i} - a_{r} ‖

, i.e., the nuisance parameters, which are the first

N - 1

elements in the state vector,

s_{FS}

, in Equation (23), are estimated by the CFFSLS algorithm as

{\hat{s}}_{FS} (i)

i = 1, \dots, N - 1

and can be denoted as

{\hat{r}}_{i}^{3 D}

. The differences,

h_{i} = z_{r} - z_{i}

, between the vertical position of the receiver,

z_{r}

, and the vertical position of the transmitters,

z_{i}

, are estimated as:

{\hat{h}}_{i} = \sqrt{{({\hat{r}}_{i}^{3 D})}^{2} - {({\hat{r}}_{1}^{2 D})}^{2}} .

(27)

We can determine the minimum vertical difference estimate, denoted as

{\hat{h}}_{s e l e c t e d}

, from the difference estimates,

{\hat{h}}_{i}

, according to:

{\hat{h}}_{s e l e c t e d} = \min_{i = 1, \dots, N - 1} ({\hat{h}}_{i}) .

(28)

Using

{\hat{h}}_{s e l e c t e d}

and the vertical position of the corresponding transmitter,

z_{s e l e c t e d}

, the estimate of the receiver’s vertical position,

{\hat{z}}_{r}

, can be refined as:

{\hat{z}}_{r}^{r e f i n e d} = z_{s e l e c t e d} + α \cdot {\hat{h}}_{s e l e c t e d},

(29)

where α is a design parameter value already defined. The steps of the CFFSLS algorithm and the utilization of the nuisance parameters are listed in Algorithm 3.

Algorithm 3: The CFFSLS algorithm and refinement of the vertical position estimate.

0. Input: The known transmitters’ coordinates, i.e.,

a_{i} = [x_{i}, y_{i} {, z_{i}]}^{T}

, and the FS range difference measurements, i.e.,

d_{1 j}, d_{2 j}, \dots, and d_{N - 1, N}

, as defined by the set of equations in (20).

1. Compute: The matrix

H_{FS}

and the vector

b_{FS}

as defined by Equations (21) and (22), respectively.

2. Estimate: The state vector

s_{FS}

by LS estimation via Equation (24).

3. CFFSLS Output: The receiver’s 3-D position estimate, i.e.,

{\hat{a}}_{r} = [{\hat{x}}_{r}, {\hat{y}}_{r} {, {\hat{z}}_{r}]}^{T}

, via Equation (25).

4. Estimate: The horizontal ranges, i.e.,

{\hat{r}}_{i}^{2 D}

, from the receiver to the transmitters

i = 1, \dots, N - 1

via Equation (26).

5. Estimate: The differences, i.e.,

{\hat{h}}_{i}

, between the vertical positions of the receiver and transmitters

i = 1, \dots, N - 1

via Equation (27).

6. Find: The minimum vertical difference estimate, i.e.,

{\hat{h}}_{s e l e c t e d}

, via Equation (28).

7. Refine: The vertical position estimate of the receiver via Equation (29).

8. Output: The final 3-D position estimate of the receiver, i.e.,

{\hat{a}}_{r} = [{\hat{x}}_{r}, {\hat{y}}_{r} {, {\hat{z}}_{r}^{r e f i n e d}]}^{T}

, where

{\hat{x}}_{r}, {\hat{y}}_{r}

were estimate in step 3 and

{\hat{z}}_{r}^{r e f i n e d}

was estimated in step 7.

4. Results

4.1. Simulation Setup

Computer simulations were conducted using MATLAB to evaluate the performance of the proposed TDoA-based CF LS algorithms in terms of the RMSE at a range of SNR levels from −5 to 40 dB. The range difference measurement was simulated as true value,

d_{i j}

, where

i \neq j

, added with error. The error has two components: A constant bias (positive or negative), b, and a zero-mean Gaussian noise. The SNR of any range difference signal is defined as [32]:

S N R = 10 l o g \frac{d_{i j}^{2}}{σ_{i}^{2}} [dB] .

(30)

Thus, the variance of the Gaussian noise,

σ_{i}^{2}

, is computed as [32]:

σ_{i}^{2} = \frac{d_{i j}^{2}}{10^{S N R / 10}} .

(31)

The constant bias is defined as:

b = \pm 0.1 \cdot d_{i j}^{2} .

(32)

A seven-transmitter geometry, listed in Table 1, was considered to resemble the experimental transmitters’ geometrical arrangement in order to get representative simulation results. The receiver was placed at 160, 50, and 6 m. The layout of the receiver and transmitters is shown in Figure 3.

Five error input conditions were considered: noise only, positive bias only, noise plus positive bias, negative bias only, and noise plus negative bias. The statistical result of 10,000 independent runs in each error input condition was considered for the RMSE performance, except in the bias only error input conditions, where only a single simulation run was necessary since the bias was constant over the range of considered SNR levels, and therefore, the root square error (RSE) of the position estimate is obtained. The RMSE performance was separated into the horizontal, i.e., xy, and the vertical, i.e., z, spaces, and were, respectively, defined as:

x y R M S E = \sqrt{\frac{1}{n} \sum_{i = 1}^{n} [{(x_{r} - {\hat{x}}_{r}^{i})}^{2} + {(y_{r} - {\hat{y}}_{r}^{i})}^{2}]}

(33)

and:

z R M S E = \sqrt{\frac{1}{n} \sum_{i = 1}^{n} [{(z_{r} - {\hat{z}}_{r}^{i})}^{2}]},

(34)

where n is the number of simulation runs. Thus, the overall 3-D RMSE, i.e., xyz RMSE, is defined as:

x y z R M S E = \sqrt{\frac{1}{n} \sum_{i = 1}^{n} [{(x_{r} - {\hat{x}}_{r}^{i})}^{2} + {(y_{r} - {\hat{y}}_{r}^{i})}^{2} + {(z_{r} - {\hat{z}}_{r}^{i})}^{2}]} .

(35)

4.2. Simulation Results

4.2.1. Noise Only Results

Figure 4 plots the xy RMSE of the CFSSLS, CFExSSLS, and CFFSLS solutions versus the SNR. We see that the CFSSLS algorithm performed best followed by the CFExSSLS algorithm at high SNR levels. The CFSSLS algorithm utilizes only the independent measurements, i.e., all noises appear just once, unlike the CFExSSLS algorithm that also utilizes some dependent measurements, and therefore, some noises affect more than once and increase the overall estimation error. The CFFSLS algorithm performance seems to be insensitive to noise, as shown by its almost constant accuracy over the range of SNR levels. Here, noises affect several times, positively and negatively, through propagation into the extra dependent measurements utilized in the algorithm. The performance of the CFExSSLS algorithm deteriorates rapidly below the 10 dB SNR level, while the CFSSLS solution accuracy starts to decrease below the 5 dB SNR level. At very high noise levels, below 5 dB, the CFFSLS algorithm delivers the best possible solution. The insensitivity of the CFFSLS solution to noise indicates the upper bound on the horizontal position accuracy attainable at high noise levels, which is the case in environments that are challenging to wireless signals. Figure 5 shows a similar trend in the vertical space. However, the vertical position estimates of the three algorithms in their original formulation are useless due to the quasi-coplanar arrangement of the involved transmitters; thus, only the horizontal position estimates can be accepted.

Figure 6 shows the z RMSE of the CFSSLS and CFFSLS algorithms when the nuisance parameters are utilized to refine the vertical position estimates as explained in Section 3.1 and Section 3.3. The CFExSSLS solution does not estimate any nuisance parameters to be utilized in a similar procedure. The accuracy of the vertical position estimates was reduced to a couple of meters. The accuracy of the CFSSLS refined solution ranged between about 2.10 and 3.35 m, and that of the CFFSLS refined solution between 1.50 and 2.50 m. The better accuracy was generally obtained at lower SNR levels, especially for the CFSSLS solution, while the less accurate estimates of the CFFSLS solution were obtained in the 10 to 20 dB SNR levels. The accuracy of the CFFSLS solution decreases slightly after 0 dB to reach less than 2.5 m at 15 dB and then starts again to increase to an almost constant accuracy of less than 2 m at SNR ≥ 30 dB. Both algorithms deliver similar accuracies between about 8 and 15 dB. However, the accuracy differences over the range of SNR levels are still not greatly significant, they are less than 1.5 and 1 m for the CFSSLS and CFFSLS solutions, respectively, and depend on the geometry of receiver and transmitters. The CFFSLS algorithm delivered more accurate refined vertical position estimates due to the utilization of more nuisance parameters, which is equivalent to the utilization of more information.

4.2.2. Positive Bias Only Results

From Figure 7, we see that in the case of positive bias only measurement errors, the CFSSLS algorithm delivers the most accurate horizontal position estimate. This result is consistent since all biases contribute to the CFSSLS solution only once, unlike the CFExSSLS and CFFSLS solutions, where bias errors contribute more than once due to the utilization of extra dependent measurements beyond the SS independent set of TDoA measurements. It would further be expected that the horizontal positioning accuracy of the CFExSSLS solution has to be higher than that of the CFFSLS solution, since it utilizes fewer dependent measurements. However, as can be seen from Figure 7, the horizontal positioning accuracy of both the CFExSSLS and CFFSLS algorithms are identical, indicating the canceling-out of some bias effects when using the FS of TDoA measurements, resulting in the identical horizontal accuracy of the CFExSSLS and CFFSLS solutions. A similar and more obvious trend for the vertical positioning accuracy is seen from Figure 8, despite the fact that these vertical position estimates are useless due to the quasi-coplanar arrangement of the transmitters. The most accurate vertical position estimate is obtained by the CFSSLS algorithm followed by the CFExSSLS algorithm and then by the CFFSLS algorithm. No canceling-out of bias errors in the FS TDoA equations obviously appeared in the vertical, i.e., one-dimensional, space. Figure 9 confirms again that the accuracy of the CFFSLS refined vertical position estimate is higher than that of the CFSSLS result, since more nuisance parameters are utilized by the CFFSLS algorithm to refine the vertical position estimate. The accuracies of the CFFSLS and CFSSLS refined vertical position estimates are 0.30 and less than 1.10 m, respectively.

4.2.3. Noise Plus Positive Bias Results

Figure 10 plots the xy RMSE of the CFSSLS, CFExSSLS, and CFFSLS solutions when simulated measurements are corrupted by noise and positive bias. At high SNR levels, the best performance is obtained by the CFSSLS algorithm, as expected, and both the CFExSSLS and CFFSLS solutions are identical, in accordance with the results from Figure 7, as long as measurement errors are dominated by positive bias. The CFFSLS solution is almost insensitive to the noise level and outperforms the CFSSLS solution at high noise levels, i.e., below 5 dB. The z RMSE trend, shown in Figure 11, is similar to that in the noise-only case plotted in Figure 5. At high SNR levels, the CFSSLS algorithm performs best and is followed by the CFExSSLS algorithm. As the noise level increases, the CFFSLS solution outperforms the CFExSSLS and CFSSLS below 15 and 5 dB, respectively. We repeat again that all these vertical position estimates are useless for 3-D applications due to the quasi-coplanar arrangement of the transmitters. The z RMSE of the refined vertical position estimates of the CFSSLS and CFFSLS algorithms are plotted in Figure 12. The CFFSLS solution outperforms the CFSSLS solution due to the utilization of more nuisance parameters. The vertical position estimates are accurate enough for many 3-D applications.

4.2.4. Negative Bias Only Results

From Figure 13, we see that the CFExSSLS algorithm performs much better than the CFFSLS algorithm and approaches the performance of the CFSSLS solution in horizontal space, xy, unlike with positive bias only errors, see Figure 7, in which the CFExSSLS estimation approaches towards the CFFSLS solution, where both have identical performance. Figure 14 shows that the vertical positioning performance of the CFExSSLS algorithm is better than the other two solutions. When comparing Figure 13 with Figure 7 and Figure 14 with Figure 8, it seems that negative bias errors enhance the horizontal and vertical positioning performance of the CFExSSLS algorithm, while the relative performances of the CFSSLS and CFFSLS algorithms are not greatly affected. Figure 15 shows that the accuracy of the CFSSLS refined vertical position estimation is slightly better than that of the CFFSLS solution, i.e., it reverses the result in Figure 9, which indicates that negative bias errors degrade the advantage of using more nuisance parameters.

4.2.5. Noise Plus Negative Bias Results

Figure 16 plots the xy RMSE of the CFSSLS, CFExSSLS, and CFFSLS solutions when simulated measurements are corrupted by noise and negative bias. At high SNR levels, the best performance is obtained by the CFSSLS algorithm and the CFExSSLS solution approaches the CFSSLS solution very tightly when measurement errors are dominated by negative bias, which is a result obtained in the previous subsection, see Figure 13. The constant performance of the CFFSLS algorithm outperforms the CFExSSLS and CFFSLS solutions below the 15 and 5 dB SNR levels, respectively. The z RMSE performance in Figure 17, despite its uselessness for 3-D positioning, shows that at high SNR levels, the CFExSSLS algorithm performs better than the other two solutions, a result obtained from Figure 14. The performances of the CFExSSLS and CFSSLS solutions deteriorate further also below the 15 and 5 dB SNR levels, respectively. The z RMSE of refined vertical position estimates of the CFSSLS and CFFSLS algorithms are always below 2.5 m as depicted in Figure 18.

4.3. Experimental Setup and Results

Real-world TDoA measurements were obtained in a multilevel massive building of 66.25 m length and 11.94 m width, see Figure 19. The test building is made of 60 cm thick reinforced concrete with metal shielded windows. Seven transmitters were installed outside the building, see Figure 20, and a test receiver indoors observed the TDoA of the transmitted signal at eight reference test positions. The layout of the receiver test positions and the transmitters is illustrated in Figure 21. The coordinates of the transmitters and the test receiver positions are listed in Table 1 and Table 2, respectively. Table 2 also includes the number of TDoA measurement epochs (runs) at each receiver test position. This total NLoS situation and the material properties of the test building are extremely challenging to wireless signals when used for positioning. NLoS bias errors and high-level noise are expected in this experimental scenario. Figure 22 shows the error of the SS range difference measurements at the eight receiver test positions, and Figure 23 illustrates the histograms of these measurement errors. From both figures, we can see that the measurement errors are a mix of positive and negative biases added to non-uniform noises and some outliers. The mean errors of these SS measurements at the test positions are listed in Table 3.

Table 4 lists the RMSE of the horizontal, vertical, and overall 3-D positioning performance of the CFSSLS, CFExSSLS, and CFFSLS algorithms. The horizontal positioning accuracies of the CFSSLS, CFExSSLS, and CFFSLS solutions were, respectively, 3.57, 2.91, and 2.90 m. As mentioned before, the vertical position estimates without refinement are useless. The refined vertical positioning of both the CFSSLS and CFFSLS solution were similar, i.e., 2.59 and 2.61 m, respectively. Thus, the overall 3-D positioning accuracy of the CFFSLS algorithm, i.e., 3.90 m, is higher than the accuracy of the CFSSLS algorithm, i.e., 4.41 m, during the experiments, in which total NLoS conditions and low SNR levels prevailed.

5. Discussion

There are no positioning algorithms that best fit in all environments, situations, and wireless signal conditions. Positioning algorithms are usually developed for certain special cases because real environments are complex, and the geometries of receivers and transmitters are quite variable [11]. Despite improvements in wireless, hardware, and software technologies, the development of low-cost and high-accuracy positioning systems is still a challenging task. Therefore, new positioning systems and approaches will be developed in the next few years since the current technology has not yet matured.

The experimental testing and evaluation of any indoor positioning system is a difficult task due to the need for a network deployment and for testing in several types of buildings [33]. If a particular system is intended to be widely deployed, specific testing and evaluation in expected deployment environments may make sense. However, the repeatability of tests in the same environment is difficult to achieve because it is almost impossible to repeat the same environmental and signal conditions. Therefore, measures should be developed in order to create almost constant testing and evaluation conditions, in order to maximize repeatability and enable objective and fair performance comparisons. Repeatability can easily be achieved by simulations. However, simulation may not always be able to exactly resemble the varying conditions of the real world.

As previously indicated in ref. [19], the TDoA-based positioning technique has increasing practical and theoretical importance in a wide range of applications. The TDoA measurements used in CF parametric estimation also depend on some nuisance parameters. The question of whether it is advantageous to exploit the knowledge about the nuisance parameters was addressed. Knowledge about the nuisance parameters is equivalent to having a more precise probabilistic model [34] for the stochastic connection between the TDoA measurements and the receiver’s position. Thus, it contributes to uncertainty and estimation error reduction. The optimal exploitation of the knowledge about nuisance parameters or the contribution of this knowledge to theoretical lower bounds, e.g., the Cramer–Rao lower bound (CRLB), on the estimation errors are issues that still need further research efforts [19]. The system designer often wants to know in advance the best an estimator can perform as a check against available designs in certain situations. The CRLB provides a benchmark for the best positioning accuracy for any unbiased estimator, e.g., the CFSSLS estimator. Both the CFExSSLS and CFFSLS are biased estimators since they use dependent TDoA measurements. If perfect knowledge of the real world is available, the CFSSLS estimator can deliver the best performance. However, an estimator designed to approach the CRLB is not robust if the estimator is not perfectly matched to the real world. The CRLB provides no indication of what to do to achieve the predicted performance in the presence of uncertainty. Therefore, the practical meaning of the CRLB is no other than to say that the designer must have perfect knowledge about the real world to obtain small estimation errors. Investigating the performance of estimators given some level of uncertainty yields the best an estimator can do. In this regard, a CRLB lacks a practical meaning, because it assumes that even smaller errors can be achieved, but without providing any indications of how to attain the predicted performance given the present level of uncertainty. Therefore, the CRLB might not always represent an objective to achieve when designing a practical estimator.

When simulated TDoA measurements were only corrupted by noise, the best position estimates were obtained by the CFSSLS, CFExSSLS, and CFFSLS solutions (ordered from best to worst), respectively, at moderate to high SNR levels. At low SNR levels, i.e., high noise levels, the CFFSLS algorithm delivers the best estimates. The CFFSLS algorithm is a biased solution, where noises contribute many times in different combinations leading to cancel-out effects, which are indicated by the constant accuracy, i.e., steady-state behavior, over the range of investigated SNR levels. The CFSSLS and CFFSLS algorithms can refine the vertical position estimate if they utilize the nuisance parameters. Generally, the CFFSLS solution delivers more accurate refined vertical position estimates as it utilizes more nuisance parameters, i.e., more information, than the CFSSLS solution.

When only positive bias errors were present in the simulated TDoA measurements, the most accurate position estimates were obtained by the CFSSLS, CFExSSLS, and CFFSLS solutions (ordered from more to less accurate), respectively. In the horizontal space, using the FS TDoA measurements cancels out some bias effects and renders the CFExSSLS and CFFSLS solutions identical. The refined vertical position estimate of the CFFSLS algorithm is more accurate than that of the CFSSLS algorithm due to the utilization of more nuisance parameters.

The results of the two error input conditions, noise only and positive bias only, were consistently combined when simulated TDoA measurement errors were corrupted by noise and positive bias. The best performance is obtained by the CFSSLS algorithm followed by the CFExSSLS algorithm and then by the CFFSLS algorithm at moderate to high SNR levels. Both the CFExSSLS and CFFSLS horizontal position estimates are identical at high SNR levels. The CFFSLS solution is insensitive to the SNR level and, therefore, outperforms the other two solutions at low SNR, i.e., high noise, levels. The refined vertical position estimates of the CFFSLS solution is more accurate due to the utilization of more nuisance parameters.

The simulations showed that negative bias only errors generally favored the CFExSSLS algorithm more than the other two solutions. In the horizontal space, the CFSSLS algorithm performed best and closely followed by the CFExSS solution. In the vertical space, the CFExSSLS algorithm was less affected than the other two algorithms. Negative biases also did not favor the utilization of more nuisance parameters for refining the vertical position estimation. The accuracy of the CFSSLS refined vertical position estimation is slightly better than that of the CFFSLS solution. Similar conclusions also apply when noise is added to negative bias errors.

The experimental measurement errors contained a mix of the error conditions studied in the simulations. The CFFSLS algorithm had a better performance in the RMSE sense, since total NLoS conditions and non-uniform SNR levels prevailed during the experiments.

Thus, the concept of obtaining useful receiver’s vertical position estimates by the utilization of nuisance parameters in the coplanar transmitters’ setting was proved. However, a comprehensive evaluation of the approach is still needed, by repeating the experiments many times on different days and in several test buildings with different characteristics, in order to meet the recommendations provided in ref. [33].

6. Conclusions

It was demonstrated with simulations and experiments that with quasi-coplanar arrangement of transmitters and at moderate to high SNR levels, the CFSSLS solution had the best performance, followed by the CFExSSLS solution and then by the CFFSLS solution. At low SNR levels, the CFFSLS algorithm outperformed the other two algorithms. Both the CFSSLS and CFFSLS solutions estimate nuisance parameters. It was also demonstrated that the exploitation of these parameters was useful, in accordance with intuition, to significantly increase, i.e., refine, the accuracy of the receiver’s vertical position estimates. This study invites for more specific investigations to test and evaluate the presented approaches for potential positioning applications, in order to demonstrate that more conclusive results may be found for certain sets of error conditions, since different sets of error conditions seem to favor one algorithm over the other. Therefore, more research is needed to further develop and test the proposed ideas in a wider range of environments and error conditions.

Funding

This research received no external funding.

Acknowledgments

Open Access Funding by the Publication Fund of the TU Dresden.

Conflicts of Interest

The author declares no conflict of interest.

Abbreviations

AoA	Angle of Arrival
CF	Closed-Form
CFExSSLS	Closed-Form Extended Single Set Least Squares
CFFSLS	Closed-Form Full Set Least Squares
CFSSLS	Closed-Form Single Set Least Squares
CRLB	Cramer–Rao Lower Bound
DM	Direct Method
DPD	Direct Position Determination
ExSS	Extended Single Set
FS	Full Set
GNSS	Global Navigation Satellite System
LCLS	Linear Correction Least Squares
LoS	Line-of-Sight
LPS	Local Positioning Systems
LS	Least Squares
LSE	Least Squares Estimation or Estimator
MCU	Monitoring and Control Unit
ML	Maximum Likelihood
MLE	Maximum Likelihood Estimator
NLoS	Non-Line-of-Sight
PDoA	Phase Difference of Arrival
PoA	Phase of Arrival
RF	Radio Frequency
RMSE	Root Mean Square Error
RSE	Root Square Error
RSS	Received Signal Strength
RToF	Round-Trip Time of Flight
SI	Spherical Interpolation
SNR	Signal-To-Noise Ratio
SS	Single Set
ToA	Time of Arrival
TDoA	Time Difference of Arrival
TS	Transmitting Station
UT	User Terminal

References

Dargie, W.; Poellabauer, C. Fundamentals of Wireless Sensor Networks: Theory and Practice; John Wiley & Sons: New York, NY, USA, 2010. [Google Scholar]
Zafari, F.; Gkelias, A.; Leung, K. A Survey of Indoor Localization Systems and Technologies. arXiv 2019, arXiv:1709.01015v3. [Google Scholar] [CrossRef] [Green Version]
Kelner, J.M.; Ziolkowski, C.; Nowosielski, L.; Wnuk, M.T. Localization of emission source in urban environment based on the Doppler effect. In Proceedings of the 2016 IEEE 83rd Vehicular Technology Conference (VTC Spring), Nanjing, China, 15–18 May 2016; pp. 1–5. [Google Scholar]
Gajewski, P.; Ziółkowski, C.; Kelner, J.M. Using SDF method for simultaneous location of multiple radio transmitters. In Proceedings of the 19th International Conference on Microwaves, Radar & Wireless Communications (MIKON-2012), Warsaw, Poland, 21–223 May 2012; Volume 2, pp. 634–637. [Google Scholar]
Amar, A.; Weiss, A.J. Localization of narrowband radio emitters based on Doppler frequency shifts. IEEE Trans. Signal Process. 2008, 56, 5500–5508. [Google Scholar] [CrossRef]
Yang, Z.; Zhou, Z.; Liu, Y. From RSSI to CSI: Indoor localization via channel response. ACM Comput. Surv. 2013, 46, 25. [Google Scholar] [CrossRef]
Xiong, J.; Jamieson, K. ArrayTrack: A fine-grained indoor location system. In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), Lombard, IL, USA, 2–5 April 2013; pp. 71–84. [Google Scholar]
Amar, A.; Weiss, A.J. Direct position determination in the presence of model errors—Known waveforms. Digit. Signal Process. 2006, 16, 52–83. [Google Scholar] [CrossRef]
Qin, T.; Li, L.; Ba, B.; Wang, D. A fast ML-based single-step localization method using EM algorithm based on time delay and Doppler shift for a far-field scenario. Sensors 2018, 18, 4139. [Google Scholar] [CrossRef] [PubMed] [Green Version]
Tzoreff, E.; Weiss, A.J. Expectation-maximization algorithm for direct position determination. Signal Process. 2017, 133, 32–39. [Google Scholar] [CrossRef]
Li, X.; Deng, Z.D.; Rauchenstein, L.T.; Carlson, T.J. Contributed Review: Source-localization algorithms and applications using time of arrival and time difference of arrival measurements. Rev. Sci. Instrum. 2016, 87, 921–960. [Google Scholar] [CrossRef]
Foy, W. Position-location solutions by Taylor-series estimation. IEEE Trans. Aerosp. Electron. Syst. 1976, 12, 187–194. [Google Scholar] [CrossRef]
Torrieri, D. Statistical theory of passive location systems. IEEE Trans. Aerosp. Electron. Syst. 1984, 20, 183–197. [Google Scholar] [CrossRef] [Green Version]
Fletcher, R.; Powell, M. A rapidly convergent descent method for minimization. Comput. J. 1963, 6, 163–168. [Google Scholar] [CrossRef]
Marquardt, D. Algorithm for least-squares estimation of nonlinear parameters. SIAM J. Appl. Math. 1963, 11, 431–441. [Google Scholar] [CrossRef]
Chen, J.; Hudson, R.; Yao, K. Maximum-likelihood source localization at unknown sensor location estimation for wideband signals in the near-field. IEEE Trans. Signal Process. 2002, 50, 1843–1854. [Google Scholar] [CrossRef]
Stoica, P.; Li, J. Source localization from range-difference measurements. IEEE Signal Process. Mag. 2006, 23, 63–65. [Google Scholar] [CrossRef]
Bakhoum, E. Closed-Form Solution of Hyperbolic Geolocation Equations. IEEE Trans. Aerosp. Electron. Syst. 2006, 42, 1396–1404. [Google Scholar] [CrossRef]
Khalaf-Allah, M. An extended closed-form least-squares solution for three-dimensional hyperbolic geolocation. In Proceedings of the 2014 IEEE Symposium on Industrial Electronics Applications (ISIEA), Kota Kinabalu, Malaysia, 28 September–1 October 2014; pp. 7–11. [Google Scholar]
Khalaf-Allah, M.; Qaisar, S.U. Nuisance Parameter Exploitation for Accurate 3D Hyperbolic Geolocation—Field Results. In Proceedings of the International Radar Symposium (IRS-2013), Dresden, Germany, 19–21 January 2013; pp. 1025–1030. [Google Scholar]
Kleusberg, A. Die direkte Lösung des räumlichen Hyperbelschnitts. Z. Für Vermess. 1994, 119, 188–192. [Google Scholar]
Bucher, R.; Misra, D. A Synthesizable VHDL Model of the Exact Solution for Three-dimensional Hyperbolic Positioning System. VLSI Des. 2002, 15, 507–520. [Google Scholar] [CrossRef] [Green Version]
Yua, K.; Montilleta, J.-P.; Rabbachina, A.; Cheonga, P.; Oppermanna, I. UWB Location and tracking for wireless embedded networks. Signal Process. 2006, 86, 2153–2171. [Google Scholar] [CrossRef]
So, H.; Chan, Y.; Chan, F. Closed-Form Formulae for Time-Difference-of-Arrival Estimation. IEEE Trans. Signal Process. 2008, 56, 2614–2620. [Google Scholar] [CrossRef] [Green Version]
Smith, J.; Abel, J. Closed-form least-squares source location estimation from range difference measurements. IEEE Trans. Acoust. Speech Signal Process. 1987, 35, 1661–1669. [Google Scholar] [CrossRef]
Huang, Y.; Benesty, J.; Elko, G.; Mersereau, R. Real-time passive source localization: A practical linear-correction least-squares approach. IEEE Trans. Speech Audio Process. 2001, 9, 943–956. [Google Scholar] [CrossRef]
Wei, H.-W.; Ye, S.-F. Comments on “A Linear Closed-Form Algorithm for Source Localization From Time-Difference of Arrival”. IEEE Signal Process. Lett. 2008, 15, 895. [Google Scholar] [CrossRef]
Gillette, M.; Silverman, H. A linear closed-form algorithm for source localization from time-differences of arrival. IEEE Signal Process. Lett. 2008, 15, 1–4. [Google Scholar] [CrossRef]
Kim, B. Comments on “A Linear Closed-Form Algorithm for Source Localization From Time-Difference of Arrival”. IEEE Signal Process. Lett. 2008, 15, 900. [Google Scholar] [CrossRef]
Apolinário, J.A.; Yazdanpanah, H.; Nascimento, A.S.; de Campos, M.L.R. A Data-selective LS Solution to TDOA-based Source Localization. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Brighton, UK, 12–17 May 2019; pp. 4400–4404. [Google Scholar]
Schmitz-Peiffer, A.; Nuckelt, A.; Middendorf, M.; Burazanis, M. A new Navigation System for Indoor Positioning (InLite). In Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Zürich, Switzerland, 15–17 September 2010. [Google Scholar]
Wu, P.; Su, S.; Zuo, Z.; Guo, X.; Sun, B.; Wen, X. Time Difference of Arrival (TDoA) Localization Combining Weighted Least Squares and Firefly Algorithm. Sensors 2019, 19, 2554. [Google Scholar] [CrossRef] [Green Version]
Joint Technical Committee ISO/IEC JTC 1. Automatic identification and data capture techniques. In Information Technology—Real Time Locating Systems—Test and Evaluation of Localization and Tracking Systems; ISO/IEC 18305, International Standard, 1st ed.; Information technology, Subcommittee SC 31; ISO/IEC: Geneva, Switzerland, 2016. [Google Scholar]
Beyerer, J. Is it useful to know a nuisance parameter? Signal Process. 1998, 68, 107–110. [Google Scholar] [CrossRef]

Figure 1. Coplanar transmitters’ arrangement of a local positioning system (LPS).

Figure 2. Geometry of the receiver (Rx) relative to the master transmitter (Tx).

Figure 3. Layout of the receiver (red star) and transmitters (black diamonds) in the conducted simulations.

Figure 4. Horizontal root mean square error (RMSE) (left) and corresponding error bars (right) of the closed-form single set least squares (CFSSLS), closed-form extended single set least squares (CFExSSLS) and closed-form full set least squares (CFFSLS) algorithms with noise only measurement errors.

Figure 5. Vertical RMSE (left) and corresponding error bars (right) of the CFSSLS, CFExSSLS and CFFSLS algorithms with noise only measurement errors.

Figure 6. Refined vertical RMSE (left) and corresponding error bars (right) of the CFSSLS and CFFSLS algorithms with noise only measurement errors.

Figure 7. Horizontal root square error (RSE) of the CFSSLS, CFExSSLS and CFFSLS algorithms with positive bias only measurement errors.

Figure 8. Vertical root square error (RSE) of the CFSSLS, CFExSSLS and CFFSLS algorithms with positive bias only measurement errors.

Figure 9. Refined vertical root square error (RSE) of the CFSSLS and CFFSLS algorithms with positive bias only measurement errors.

Figure 10. Horizontal RMSE (left) and corresponding error bars (right) of the CFSSLS, CFExSSLS and CFFSLS algorithms with noise plus bias measurement errors.

Figure 11. Vertical RMSE (left) and corresponding error bars (right) of the CFSSLS, CFExSSLS and CFFSLS algorithms with noise plus bias measurement errors.

Figure 12. Refined vertical RMSE (left) and corresponding error bars (right) of the CFSSLS and CFFSLS algorithms with noise plus bias measurement errors.

Figure 13. Horizontal root square error (RSE) of the CFSSLS, CFExSSLS and CFFSLS algorithms with negative bias only measurement errors.

Figure 14. Vertical root square error (RSE) of the CFSSLS, CFExSSLS and CFFSLS algorithms with negative bias only measurement errors.

Figure 15. Refined vertical root square error (RSE) of the CFSSLS and CFFSLS algorithms with negative bias only measurement errors.

Figure 16. Horizontal RMSE (left) and corresponding error bars (right) of the CFSSLS, CFExSSLS and CFFSLS algorithms with noise plus negative bias measurement errors.

Figure 17. Vertical RMSE (left) and corresponding error bars (right) of the CFSSLS, CFExSSLS and CFFSLS algorithms with noise plus negative bias measurement errors.

Figure 18. Refined vertical RMSE (left) and corresponding error bars (right) of the CFSSLS and CFFSLS algorithms with noise plus negative bias measurement errors.

Figure 19. Front and back views of the test building.

Figure 20. Transmitters during setup and deployment outside the test building.

Figure 21. Layout of the receiver test positions (red star as the starting position and red circles) and transmitters (black diamonds) in the experiments.

Figure 22. Errors of the single set (SS) range difference measurements at the eight receiver test positions.

Figure 23. Histograms of the SS range difference measurement errors at the eight receiver test positions.

Table 1. The 3-D coordinates of the seven transmitters used in simulations and experiments.

Transmitter	x (m)	y (m)	z (m)
Tx 1	184.44	50.00	1.61
Tx 2	180.66	30.76	1.72
Tx 3	160.05	30.84	1.82
Tx 4	139.61	30.54	1.78
Tx 5	139.11	67.49	1.88
Tx 6	159.96	67.72	1.68
Tx 7	184.60	67.53	1.62

Table 2. The 3-D coordinates of the eight receivers’ test positions.

Test Position	x (m)	y (m)	z (m)	Number of Measurement Epochs
Pos 1	160.24	45.76	5.95	97
Pos 2	159.79	47.73	5.94	98
Pos 3	159.70	50.29	5.94	96
Pos 4	164.21	47.42	4.56	44
Pos 5	164.32	46.12	7.85	26
Pos 6	160.41	51.87	9.22	90
Pos 7	160.15	48.35	9.23	86
Pos 8	159.65	45.81	9.23	95
				Total = 632

Table 3. Rounded mean errors (m) of the SS range difference measurements at the eight receiver test positions.

Test Position	d₁₂	d₁₃	d₁₄	d₁₅	d₁₆	d₁₇
Pos 1	1.66	0.82	1.98	−1.82	0.62	−5.80
Pos 2	1.46	−0.27	−0.85	−2.10	−1.81	−9.42
Pos 3	−3.72	−2.18	−4.96	−3.41	−1.96	−7.47
Pos 4	5.80	5.67	6.27	−0.93	−1.25	0.67
Pos 5	2.14	4.84	4.10	15.26	4.11	2.59
Pos 6	0.98	0.12	−5.57	0.93	−2.11	1.00
Pos 7	3.40	2.79	−3.88	0.58	2.45	−4.11
Pos 8	−0.97	4.74	−0.20	−3.29	2.04	−4.43

Table 4. Horizontal, vertical, refined vertical, and refined 3-D RMSE of the investigated algorithms in the experiments.

Algorithm	xy RMSE (m)	z RMSE (m)	z RMSE Refined (m)	xyz RMSE Refined (m)
CFSSLS	3.57	557.11	2.59	4.41
CFExSSLS	2.91	534.10	-	-
CFFSLS	2.90	317.48	2.61	3.90

© 2019 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Khalaf-Allah, M. Performance Comparison of Closed-Form Least Squares Algorithms for Hyperbolic 3-D Positioning. J. Sens. Actuator Netw. 2020, 9, 2. https://doi.org/10.3390/jsan9010002

AMA Style

Khalaf-Allah M. Performance Comparison of Closed-Form Least Squares Algorithms for Hyperbolic 3-D Positioning. Journal of Sensor and Actuator Networks. 2020; 9(1):2. https://doi.org/10.3390/jsan9010002

Chicago/Turabian Style

Khalaf-Allah, Mohamed. 2020. "Performance Comparison of Closed-Form Least Squares Algorithms for Hyperbolic 3-D Positioning" Journal of Sensor and Actuator Networks 9, no. 1: 2. https://doi.org/10.3390/jsan9010002

APA Style

Khalaf-Allah, M. (2020). Performance Comparison of Closed-Form Least Squares Algorithms for Hyperbolic 3-D Positioning. Journal of Sensor and Actuator Networks, 9(1), 2. https://doi.org/10.3390/jsan9010002

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Performance Comparison of Closed-Form Least Squares Algorithms for Hyperbolic 3-D Positioning

Abstract

1. Introduction

2. Related Work

3. Materials and Methods

3.1. Closed-Form Single Set Least Squares Solution

3.2. Closed-Form Extended Single Set Least Squares Solution

3.3. Closed-Form Full Set Least Squares Solution

4. Results

4.1. Simulation Setup

4.2. Simulation Results

4.2.1. Noise Only Results

4.2.2. Positive Bias Only Results

4.2.3. Noise Plus Positive Bias Results

4.2.4. Negative Bias Only Results

4.2.5. Noise Plus Negative Bias Results

4.3. Experimental Setup and Results

5. Discussion

6. Conclusions

Funding

Acknowledgments

Conflicts of Interest

Abbreviations

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI