Gradient Descent 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 40 Table-1: TDoA in 4G and 5G Networks

Generation

Method

Measurement

Optimization methods

4G

OTDoA

RSTD

NewtonRaphson, GradientDescent

5G

DL-TDoA

RSTD

NewtonRaphson, GradientDescent

5G

UL-TDoA

UL-RTOA

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.

  • No close-form optimization method for estimating the nodes location.

    • High complexity.

  • 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:

Table 41 Table-2: Performance comparison between Gradient Descent and Newton Raphson algorithm.

Method

Per iteration complexity

Convergence

Utility

Gradient Descent

\(\text{N}\)

Slow

Low power, low cost

Newton Raphson

\(\text{N}^2\)

Fast

Low latency

where N denotes the number of measurements used for positioning.

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 = GradientDescentTDoA(numIterations = 100000, numRepetition = 10,
                                     tolerance = 0.0000000001, stepsize = 0.1)
# Position Estimation Object:
    # Positioning based on: TDoA
    # Optimization Method: Gradient Descent
tdoa = ToAe[1::] - ToAe[0] # Time difference of arrival/RSTD
rxPositionEstimate = 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)[source]

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 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: Gradient Descent
tdoa = ToAe[1::] - ToAe[0] # Time difference of arrival/RSTD
rxPositionEstimate = 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)[source]

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. 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-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.