Least Squares based Position Estimator for TDoA

The \(\text{4G}^\text{th}\) and \(\text{5G}^\text{th}\) generation of wireless networks uses time difference of arrival methods to estimate the position of node. The nomenclature of the methods is detailed below. The implementation of Newton Raphson and Gradient Descent optimization methods is inspired from [handbookTDoA].

Table 38 Table-1: TDoA in 4G and 5G Networks

Generation	Method	Measurement	Optimization methods
4G	OTDoA	RSTD	LeastSquares, NewtonRaphson, GradientDescent
5G	DL-TDoA	RSTD	LeastSquares, NewtonRaphson, GradientDescent
5G	UL-TDoA	UL-RTOA	LeastSquares, NewtonRaphson, GradientDescent

In 5G, the ToA estimates suffers from calibration impairments and antenna to base-band delays which propagates in-accuracies in the position estimates. However, the TDoA measurements are computed by taking difference of all ToA measurements with respect to one reference ToA measurement which can cancel the fixed receiver antenna to base-band delay across all the measurements. This makes TDoA measurements more robust to these impairments in comparison to ToA measurements. The major challenges with TDoA based positioning are two.

• Require atleast 4 accurate ToA (3 accurate TDoA) measurements.

• In case reference ToA measurement is NLoS, positioning accuracy degrades significantly.

Hence, TDoA based positioning methods rely on iterative optimization methods. One such optimization method is Gradient Descent (GD) which has low complexity iteration in comparison to Newton Raphson (NR) method but needs more iterations to converge to local/global optima. The comparison between the two methods is shown below:

where N denotes the number of measurements used for positioning and \(N_\text{iterations}\) denotes the number of iterations used by iterative methods.

---

The following code illustrate the way to compute the time difference of arrival (TDoA) using time of arrival (ToA). The TDoA/RSTD measurement is passed to Newton Raphson optimization method to estimate the user equipment (UE) location.

Code example

positionEstimate = LeastSquareTDoA()
# Position Estimation Object:
    # Positioning based on: TDoA
    # Optimization Method: Least Squares
    # ToAe: (Nref,)
    # txPosition: (Nref,3)
tdoa = ToAe[1::] - ToAe[0] # Time difference of arrival/RSTD
rxPositionEstimate, error = positionEstimate(txPosition, tdoa) # Position estimation using TDoA/RSTD

---

The details of input output interface for usage is detailed below.

class toolkit5G.Positioning.LeastSquareTDoA

This modules uses least squares optimization framework to estimate the node location using time difference of arrival (TDoA) measurements.

Parameters:

None

Input:

• refPosition ((\(\text{N}_\text{ref}\), 3), np.number) – Reference locations with respect to whom ToAs are estimated.

• tdoa ((\(\text{N}_\text{ref}-1\),), np.number) – Time difference of arrival estimates with respected to \(\text{N}_\text{ref}\) reference locations.

Output:

• (N, 3), np.number – Position estimate. If the height of all the transmitter is same, then N=2 else N=1.

  • For equiheight transmitters, there exist two estimates of the height of the UE.

  • One above the transmitter and other below it.

  • This phenomenon results in 2 estimate of the position of the UE.

  • However, both these estimates have the same (x, y) co-ordinate.

• np.number – Uncertainty in Position Estimates. The lower the value better the position estimates.

Note

The large value of numIterationPerEpoch improves the optimization performance but increases the complexity of the method.

Note

The large value of numEpochs helps reduce the odds of getting stuck in the local optima but increases the complexity of the method.

Important

The time difference of arrival is computed as \(\{ \Delta \tau_{i,r} = \tau_i - \tau_r\}_{i=0}^{i=\text{N}_\text{ref}-1} s.t. i \neq r\) where \(r\) is the reference measurement used for difference in TDoA. The location of node-r must be the at the first place in refPosition followed by the locations of the remaining nodes from the set \(\zeta = \{i | i \neq r\}_{i=0}^{i=\text{N}_\text{ref}-1}\).

• refPosition[:,0] = location of node-r

• refPosition[:,i] = location of node-\(\zeta[i]\)

Note

The lower value of tolerance improves the optimization performance but increases the complexity of the method. The method iterative longer to reduces the optimization error below the tolerance limit.

Note

The selection of step-size mu plays crucial role in performance of the method. Small step-size results in good performance but requires large number of iteration numIterationPerEpoch to converge. Large step-size improves the convergence rate but are suceptible to local minimas.

Raises:

• ValueError – “[Error-LeastSquareTDoA]: ‘refPosition’ and ‘measurements’ must be an numpy array!”

• ValueError – “[Error-LeastSquareTDoA]: ‘refPosition’ must be an 2D numpy array!”

• ValueError – “[Error-LeastSquareTDoA]: ‘refPosition’ must be an numpy array of size (nRefnode x 3). refPosition.shape[1] is not equal to 3!”

• ValueError – “[Error-LeastSquareTDoA]: ‘refPosition’ must be an numpy array of size (nRefnode x 3). refPosition.shape[0] should be more than 3 for trilateration!

• ValueError – “[Error-LeastSquareTDoA]: ‘number of refPositions’ must be consistent with number of measurements! refPosition.shape[0] should be equal to tdoa.size+1”

Gradient Descent based Position Estimator for TDoA

Code example

positionEstimate = GradientDescentTDoA(numIterations = 100000, numRepetition = 10,
                                     tolerance = 0.0000000001, stepsize = 0.1)
# Position Estimation Object:
    # Positioning based on: TDoA
    # Optimization Method: Gradient Descent
    # ToAe: (Nref,)
    # txPosition: (Nref,3)
tdoa = ToAe[1::] - ToAe[0] # Time difference of arrival/RSTD
rxPositionEstimate, error = positionEstimate(txPosition, tdoa) # Position estimation using TDoA/RSTD

The input output interface for usage of Gradient Descent algorithm is provided below.

class toolkit5G.Positioning.GradientDescentTDoA(numIterationPerEpoch=10000, numEpochs=10, tolerance=1e-06, stepsize=0.1, isd=100)

This modules uses time difference of arrival (TDoA) measurements to estimate the position of a node based on gradient descent optimization methods.

Parameters:

• numIterationPerEpoch (int) – Number of iteration for gradient descent optimizations. Default value is 10000.

• numEpochs (int) – Number of epoches used in gradient descent optimizations. Default value is 10.

• tolerance (float) – Error tolerance values. The optimization stops when the optimization error reduces below tolerance value.

• stepsize (float) – Optimization step size. The Newton Raphson algorithms iterates using this step-size to converge towards the global solutions.

• isd (float) – Defines the intersite distance (m). Its equal to :math:`2 times ` cell-size.

Input:

• refPosition ((\(\text{N}_\text{ref}\), 3), np.number) – Reference locations with respect to whom ToAs are estimated.

• tdoa ((\(\text{N}_\text{ref}-1\),), np.number) – Time difference of arrival estimates with respected to \(\text{N}_\text{ref}\) reference locations.

Output:

(3,), np.number – Position estimate.

Note

The large value of numIterationPerEpoch improves the optimization performance but increases the complexity of the method.

Note

The large value of numEpochs helps reduce the odds of getting stuck in the local optima but increases the complexity of the method.

Important

The time difference of arrival is computed as \(\{ \Delta \tau_{i,r} = \tau_i - \tau_r\}_{i=0}^{i=\text{N}_\text{ref}-1} s.t. i \neq r\) where \(r\) is the reference measurement used for difference in TDoA. The location of node-r must be the at the first place in refPosition followed by the locations of the remaining nodes from the set \(\zeta = \{i | i \neq r\}_{i=0}^{i=\text{N}_\text{ref}-1}\).

• refPosition[:,0] = location of node-r

• refPosition[:,i] = location of node-\(\zeta[i]\)

Note

The lower value of tolerance improves the optimization performance but increases the complexity of the method. The method iterative longer to reduces the optimization error below the tolerance limit.

Note

The selection of step-size mu plays crucial role in performance of the method. Small step-size results in good performance but requires large number of iteration numIterationPerEpoch to converge. Large step-size improves the convergence rate but are suceptible to local minimas.

Raises:

• ValueError – [Error-GradientDescentTDoA]: ‘refPosition’ and ‘measurements’ must be an numpy array!

• ValueError – [Error-GradientDescentTDoA]: ‘refPosition’ must be an 2D numpy array!

• ValueError – [Error-GradientDescentTDoA]: ‘refPosition’ must be an numpy array of size (nRefnode x 3). refPosition.shape[1] is not equal to 3!

• ValueError – [Error-GradientDescentTDoA]: ‘refPosition’ must be an numpy array of size (nRefnode x 3). refPosition.shape[0] should be more than 3 for trilateration!

• ValueError – [Error-GradientDescentTDoA]: ‘number of refPositions’ must be consistent with number of measurements! refPosition.shape[0] should be equal to tdoa.size+1

• ValueError – [Error-GradientDescentTDoA]: ‘numIterationPerEpoch’ should be a scalar integer!

• ValueError – [Error-GradientDescentTDoA]: ‘numEpochs’ should be a scalar integer!

• ValueError – [Error-GradientDescentTDoA]: ‘tolerance’ should be a scalar number!

• ValueError – [Error-GradientDescentTDoA]: ‘stepsize’ should be a scalar number!

• ValueError – [Error-GradientDescentTDoA]: ‘isd’ should be a scalar number!

• ValueError – [Error-GradientDescentTDoA]: ‘refPosition’ and ‘measurements’ must be an numpy array!

---

Newton Raphson based Position Estimator for TDoA

The following code snippet illustrate the way to compute the time difference of arrival (TDoA) using time of arrival (ToA). The TDoA/RSTD measurement is passed to Newton Raphson optimization method to estimate the user equipment (UE) location.

Code example

positionEstimate = NewtonRaphsonTDoA(numIterations = 100000, numRepetition = 10,
                                     tolerance = 0.0000000001, stepsize = 0.1)
# Position Estimation Object:
    # Positioning based on: TDoA
    # Optimization Method: Newton Raphson
    # ToAe: (Nref,)
    # txPosition: (Nref,3)
tdoa = ToAe[1::] - ToAe[0] # Time difference of arrival/RSTD
rxPositionEstimate, error = positionEstimate(txPosition, tdoa) # Position estimation using TDoA/RSTD

---

The details of input output interface for usage is detailed below.

class toolkit5G.Positioning.NewtonRaphsonTDoA(numIterationPerEpoch=10000, numEpochs=10, tolerance=1e-06, stepsize=0.1, isd=100)

This module uses time difference of arrival (TDoA) measurements to estimate the position of a node based on Newton Raphson optimization methods.

Parameters:

• numIterationPerEpoch (int) – Number of iteration for gradient descent optimizations for every epoch. Default value is 10000.

• numEpochs (int) – Number of epoches used in gradient descent optimizations. Every epoch starts with a random initialization which helps in overcoming the local minima. Default value is 10.

• tolerance (float) – Error tolerance values. The optimization stops when the optimization error reduces below tolerance value.

• stepsize (float) – Optimization step size. The Newton Raphson algorithms iterates using this step-size to converge towards the global solutions.

• isd (float) – Defines the intersite distance (m). Its equal to :math:`2 times ` cell-size.

Input:

• refPosition ((\(\text{N}_\text{ref}\), 3), np.number) – Reference locations (in meters) with respect to whom ToAs are estimated.

• tdoa ((\(\text{N}_\text{ref}-1\),), np.number) – Time difference of arrival estimates (in seconds) with respected to \(\text{N}_\text{ref}\) reference locations.

Output:

(3,), np.number – return the estimate of the position.

Note

The large value of numIterationPerEpoch improves the optimization performance but increases the complexity of the method.

Note

The large value of numEpochs helps reduce the odds of getting stuck in the local optima but increases the complexity of the method.

Important

The time difference of arrival is computed as \(\{ \Delta \tau_{i,r} = \tau_i - \tau_r\}_{i=0}^{i=\text{N}_\text{ref}-1} s.t. i \neq r\) where \(r\) is the reference measurement used for difference in TDoA. The location of node-r must be the at the first place in refPosition followed by the locations of the remaining nodes from the set \(\zeta = \{i | i \neq r\}_{i=0}^{i=\text{N}_\text{ref}-1}\).

• refPosition[:,0] = location of node-r

• refPosition[:,i] = location of node-\(\zeta[i]\)

Note

The lower value of tolerance improves the optimization performance but increases the complexity of the method. The method iterative longer to reduces the optimization error below the tolerance limit.

Note

The selection of step-size mu plays crucial role in performance of the method. Small step-size results in good performance but requires large number of iteration numIterationPerEpoch to converge. Large step-size improves the convergence rate but are suceptible to local minimas.

Raises:

• ValueError – [Error-NewtonRaphsonTDoA]: ‘refPosition’ and ‘measurements’ must be an numpy array!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘refPosition’ must be an 2D numpy array!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘refPosition’ must be an numpy array of size (nRefnode x 3). refPosition.shape[1] is not equal to 3!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘refPosition’ must be an numpy array of size (nRefnode x 3). refPosition.shape[0] should be more than 3 for trilateration!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘number of refPositions’ must be consistent with number of measurements! refPosition.shape[0] should be equal to tdoa.size+1

• ValueError – [Error-NewtonRaphsonTDoA]: ‘numIterationPerEpoch’ should be a scalar integer!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘numEpochs’ should be a scalar integer!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘tolerance’ should be a scalar number!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘stepsize’ should be a scalar number!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘isd’ should be a scalar number!

• ValueError – [Error-NewtonRaphsonTDoA]: ‘refPosition’ and ‘measurements’ must be an numpy array!

References:

[handbookTDoA]

So, H. C., and RMB Reza Zekavat. “Handbook of position location: Theory, practice and advances.” The Oxford Handbook of Innovation. No. 2. Wiley-IEEE Press, 2011. 23-34.