Self-Calibration for the Time-of-Arrival Positioning

Self-calibration of time-of-arrival positioning systems is made difficult by the non-linearity of the relevant set of equations. This work applies dimension lifting to this problem. The objective function is extended by an additional dimension to allow the dynamics of the optimization to avoid local minima. Next to the usual numerical optimization, a partially analytical method is suggested, which makes the system of equations overdetermined proportionally to the number of measurements. Results with the lifted objective function are compared to those with the unmodified objective function. For evaluation purposes, the fractions of convergence to local minima are determined, for both synthetic data with random geometrical constellations and real measurements with a reasonable constellation of base stations. It is shown that the lifted objective function provides improved convergence in all cases, often significantly so.

SECTION I. Introduction

Knowledge about the position has always been a key technology for exploring unknown territories. Without reference points like stars or the Earth’s poles, it would not be feasible to cross the ocean. In the last century, more precise and nature-independent base stations have been developed. In some cases, it is necessary to obtain the locations of the base stations just by distance measurements without further measuring equipment. This method receives the name of self-calibration. In the case of the time-of-arrival measurement technique (TOA), it is possible to obtain the geometrical constellation of the base stations only by the distance measurements between the base stations and the transponders [1]–​[3]. Linear approximations are not always reliable due to noise and nonlinear sensor constraints. For this reason, nonlinear optimization algorithms are the method of choice. The main disadvantage of nonlinear optimization algorithms is the possible convergence to a local minimum if the initial estimates are not close to the global minimum [6]. The effect of degrees of freedom on the probability of convergence to local minima during the self-calibrated time of arrival by nonlinear least square optimization is the main aspect of this work. In [17] we demonstrated that an additional degree of freedom can transform the local minimum of the squared TOA objective function with known base station positions to a saddle point. Our approach was inspired by dimension lifting [18], [19]. Dimension lifting introduces an additional dimension to solve a specific problem. The only other known publication that dealt with the effect of degrees of freedom and self-calibration was [20]. In contrast to our work, the topic was about the difference in dimension between the affine subspaces spanned by the relative positions of base stations and transponders. Our approach is to increase the dimensions of the original model by an additional degree of freedom for every unknown base station and tag. We show that the lifted objective functions perform better than the general objective function. The test scenarios are based on real measurements and synthetic data.

This paper is organized as follows. The first section of this article introduces the TOA self-calibration problem, followed by the second section previous work. In the third section of this article our dimension lifting approach is presented. The fourth section is dedicated to the implementation of the modified objective function for the self-calibration problem. The fifth and sixth section demonstrate the performance of our approach by experiments with synthetic and real measurements performed. The results of the experiments are discussed in detail in the last section. The notations used in this article are presented in Tables 1 and 2.

TABLE 1 Notation Used in the Text and in Equations

TABLE 2 Notations Used in the Equations

A. Contribution

This article presents a method to transform the objective function of the TOA in order to reduce the risk of becoming trapped in a local minimum during a nonlinear optimization. In [17], we have proven for time-of-arrival (TOA) that if the positions of the reference stations are known, the dimension lifting transforms the local minimum into a saddle point. This article aims to adopt this approach for the TOA self-calibration with unknown reference station positions. The presented approach is analyzed with synthetic and real TOA measurements, respectively. To our knowledge, no previous researchers have done this before; nor was the linear variable estimation applied inside the nonlinear optimization iteration step for the TOA self-calibration in this article, the so-called partially analytical method.

SECTION II. Related Work

In [4] it was shown that the minimum number of base stations (N) and transponders (M) for the TOA self-calibration in the two-dimensional space are $(M=3, N=3)$ and for the three-dimensional space $(M=4, N=6), (M=5, N=5)$ and $(M=6, N=4)$ [4]. The roles of the base stations and the transponders are interchangeable; hence it does not matter if six base stations and four transponders are used or vice versa. The number of transponders (M) could refer either to a number of seperate physical transponders in fixed locations, or a single physical device that moves to M different locations, or some combination. In [7] and [8] it was proposed to use semidefinite programming (SDP) as an initialization for the maximum likelihood (ML) estimator. Alternatively, non-iterative methods can be used. A two-dimensional non-iterative method was proposed for the case with three transponders and three receivers in [9]. The solution for the three-dimensional case was the subject of the investigation in [10], [11]. The authors provided a non-iterative solution for $(M=5, N=5), (M=6, N=4) (M=10, N=4)$ . In the case of one base station position coinciding with one of the transponders, a closed-form solution was described in [12], [13]. The publication [14] presented non-iterative methods for self-calibration with the minimum configuration using the Groebner basis method and Macaulay2 software. A solution less sensitive to noise is presented based on the use of only low-degree monomials in contrast to methods like the Groebner basis [15]. On the other hand, this method requires a higher number of stations than the minimum number (M = 4, N = 7). Other linear solutions require constraints, like that the distances between the base stations and the transponders are considerably larger than between the base stations [16].

Regarding dimension lifting, our group has previously applied that approach to other aspects of TOA positioning. In [17], we demonstrated that an additional degree of freedom transforms the local minimum of the squared TOA objective function with known and stationary base stations positions to a saddle point. Furthermore, no other local minima appear for non-trivial constellations. This hypothesis was also numerically verified for the TOA objective function [17]. In [23] we showed that in the presence of noise, it is advisable to use the objective function with an additional dimension to provide initial estimates and to use the general objective function Equation without the additional dimension in the next step. The objective function with the additional dimension reduces the risk to converge to a local minimum and the general objective function minimizes the effect of noise, due to the higher ratio between the number of equations to unknown variables.

A. Limitations of the Previous Work

The previous work about the TOA self-calibration is limited to specific conditions like the minimum number of base stations [10], [11], [14] or the requirement that one base station position coinciding with one of the transponders [12], [13]. In [16] the limiting factor is the distance between the base stations. However, with nonlinear constraints are the most approximation methods not applicable. Our dimension lifting approach can be applied on any TOA self-calibration problem, without the need of additional modifications [17].

SECTION III. Time of Arrival Measurement Model

The time-of-arrival (TOA) measurement technique provides distance measurements between base stations and transponders. Customarily, the positions of the base stations are known and the positions of the transponders have to be estimated by triangulation. Self-calibration is concerned with the case where the positions of the base stations are unknown and only the distance measurements between the base stations and the transponders are available. Figure 1 shows three base stations $B_{i}$ and three transponders $T_{j}$ in unknown positions. The distances $d_{i,j}$ between base stations $B_{i}$ and transponders $T_{j}$ are determined through distance measurements. Distances between the base stations $B_{i}$ are unknown. The aim of self-calibration is to obtain the relative coordinates between all base stations.

FIGURE 1.

The figure shown three base stations $B_{i}$ and three transponders $T_{j}$ as circles and squares, respectively. The distance measurements are only possible between the base stations and the transponders. Distance measurements from one specific base station to one specific transponder are represented by black, green and red dashed lines.

A. Mathematical Formulation

The $l_{2}$ norm in the usual objective function is extended by an additional coordinate $\tilde {\lambda _{i}}$ for the base stations and $\lambda _{j}$ for the tags. This means that if the problem is two-dimensional (the tag and the base stations are located on a two-dimensional plane), the objective function is expanded by a third dimension. The approach can be illustrated geometrically by imaging two circles. The both intersection points are the minima, one of them the local minimum and the other the global optimum. If the optimization algorithm starts close to the local minimum and it remains in the two-dimensional plane, it is not able find an alternative path. With the additional dimension, the optimization algorithm is able to move along the intersection line of the spheres from the local minimum to the global optimum. The self-calibration will only use the changing tag position to estimate the unchanging position of the base stations. Every position change of the tag increases the number of equations as well as the number of unknowns $x_{j},y_{j}$ and $z_{j}$ . Since the positions of the base stations are unknown, the constellation can only be determined up to rotation and translation.

Classic approach: \begin{equation*} \mathbf {t}_{j}=\left ({\begin{array}{c} x_{j}\\ y_{j}\\ z_{j} \end{array}}\right)\quad \mathbf {b}_{i}=\left ({\begin{array}{c} a_{i}\\ b_{i}\\ c_{i} \end{array}}\right)\end{equation*}

Our lifted approach: \begin{equation*} \mathbf {t}_{j}=\left ({\begin{array}{c} x_{j}\\ y_{j}\\ z_{j}\\ \lambda _{j} \end{array}}\right)\quad \mathbf {b}_{i}=\left ({\begin{array}{c} a_{i}\\ b_{i}\\ c_{i}\\ \tilde {\lambda }_{i} \end{array}}\right)\end{equation*}

SECTION IV. Self-Calibration With Dimension Lifting

The TOA self-calibration deals with the case that the positions of the base stations and the transponders are both unknown.

In presence of noise and nonlinear constraints the nonlinear optimization is the solution of choice. The relative coordinates between all base stations can be obtained by minimizing the objective function (equation 1) with non-convex optimization algorithms. It is necessary to keep in mind that the lambda coordinate of the start values must not be zero.

The measurements $d_{i,j}$ are defined as a set of Euclidean distances obtained through two-way ranging between the base stations $B_{i}$ and the transponders $T_{j}$ . With the classic approach, it is very likely that the optimization converges to a local minimum if the initial estimates are far away from the global optimum [6].

It is assumed that the additional dimension of the base stations and the transponders, reduces the risk to converge to a local minimum especially if the initial values for the base station or transponder positions are close to the correct geometrical constellations. The additional dimension is also part of the analytical position estimation in the partially analytical method. \begin{equation*} \mathrm *{argmin}\left ({\sum _{i=1}^{N}\sum _{j=1}^{M}\left [{\left \Vert{ T_{j}-B_{i}}\right \Vert -d_{i,j}}\right]^{2}}\right).\tag{1}\end{equation*}

A. Fully Numerical Method

The first method uses the objective function (1) for the self-calibration. Equation (2) describes the ratio between the number of equations and the unknown dimensions. The ratio must be at least one. The ratio is approaching $\frac {N}{D}$ with $M\to \infty $ . At a certain number of transponders, the change of the ratio becomes very small.\begin{equation*} Ra=\frac {N\cdotp M}{D\left ({N+M}\right)} \tag{2}\end{equation*}

B. Partially Analytical Method

Equivalent to the fully numerical method, the aim of the partially analytical method is to obtain the relative coordinates of the base stations $B_{i}$ . The main difference to the fully numerical method is that now only the base station positions are obtained by nonlinear optimization. The transponder positions are estimated analytically in every iteration step. The analytical solution is obtained by a linear least squares approach [22].

The ratio eq. (3) $Ra$ linearly increases with $M$ . With this method, the ratio increases indefinitely with the number of measurements. \begin{equation*} Ra=\frac {M}{D} \tag{3}\end{equation*}

Figure 2 shows the ratio $Ra$ for the fully numerical method and the partially analytical method. It can be observed that the second method leads to a higher ratio $Ra$ than the first method. With increasing number of base stations is also the ratio $Ra$ higher for the fully numerical method.

FIGURE 2.

Ratio of the fully numerical and the partially analytical method with increasing number of transponders. The yellow line represent the partially analytical method the red line the fully numerical method with four base stations and the blue line the fully numerical method with six base stations.

C. Back Transformation

The lifted objective function for the self-calibration provides the result in the coordinate system with the additional dimension. The back-transformation rotates the result into the original subspace $\lambda =0$ . In Figure 3, a possible result of the self-calibration in $\mathbb {R}^{3}$ space can be observed. The red corners are the positions of the base stations in the coordinate system with the additional dimension $\lambda $ .

FIGURE 3.

The red corners are the base station positions provided by the optimization algorithm. The blue corners are the base station positions after the back transformation in the coordinate system with $\lambda =0$ . $\sigma _{1}$ to $\sigma _{3}$ are the singular values of the SVD, with $\sigma _{3}$ too small to be drawn as an arrow.

1) Back Transformation by SVD

The singular value decomposition (SVD) can be used for the back-transformation to the same dimensional space in which the measurements were obtained. In the following, we show how to perform a back transformation from $\mathbb {R}^{3}$ to $\mathbb {R}^{2}$ . In the first step of the back transformation the matrix $Z$ it is filled with the coordinates relative to the center-of-mass coordinates of the base stations $\bar a$ , $\bar b$ and $\bar \lambda $ . \begin{equation*} Z=\left [{\begin{array}{ccc} \left ({a_{1}-\bar a }\right) &\quad \left ({b_{1}-\bar b }\right) &\quad \left ({\lambda _{1}-\bar \lambda }\right)\\ \left ({a_{2}-\bar a }\right) &\quad \left ({b_{2}-\bar b }\right) &\quad \left ({\lambda _{2}-\bar \lambda }\right)\\ \vdots &\quad \vdots &\quad \vdots \\ \left ({a_{N}-\bar a }\right) &\quad \left ({b_{N}-\bar b }\right) &\quad \left ({\lambda _{N}-\bar \lambda }\right) \end{array}}\right]\tag{4}\end{equation*} the next step, the matrix $Z$ is factorized of the form $U\varSigma V^{*}=Z$ . With $U$ as a unitary matrix, $\varSigma $ as a rectangular diagonal matrix with non-negative real numbers on the diagonal and V an unitary matrix. The diagonal entries of $\varSigma $ are known as the singular values $\sigma $ of $Z$ . Figure 3 shows the singular values $\sigma _{1}$ , $\sigma _{2}$ and $\sigma _{3}$ . If all base stations are located on a plane, then the singular value $\sigma _{3}$ is close to zero. A multiplication between the matrix $U$ and $\varSigma $ leads to a position matrix, where the additional dimension $\lambda $ is close to zero. The disadvantage of the SVD is that it is computationally expensive and not able to deal with missing data. Therefore, we present a back transformation approach based on optimization in the next section.

2) Back Transformation by Optimization

We denote rotation matrices by the coordinate directions of the planes in which they act. In $\mathbb R^{3}$ with $(X,Y,\lambda)$ the planes are $(XY,X\lambda,Y\lambda)$ . With the overall rotation matrix $R=R_{XY}\left ({\alpha }\right)\cdot R_{X\lambda }\left ({\beta }\right)\cdot R_{Y\lambda }\left ({\gamma }\right)$ and the position vector $\mathbf {b}_{i}$ the minimization objective function for the rotation becomes: \begin{equation*}\sum _{i=1}^{N}\left [{\mathbf {b}_{i}^{T}\cdot R\cdot e}\right]^{2}\rightarrow \mathrm *{\text{argmin}}~~ \mathbf {b}_{i}=\left ({\begin{array}{c} a_{i}\\ b_{i}\\ \lambda {}_{i} \end{array}}\right)~e=\left ({\begin{array}{c} 0\\ 0\\ 1 \end{array}}\right)\end{equation*}

In the $\mathbb R^{4}$ space we have the dimensions $(X,Y,Z,\lambda)$ and the overall rotation matrix changes to $R=R_{XY}\left ({\alpha }\right)\cdot R_{XZ}\left ({\beta }\right)\cdot R_{X\lambda }\left ({\gamma }\right)\cdot R_{YZ}\left ({\delta }\right)\cdot R_{Y\lambda }\left ({\epsilon }\right)\cdot R_{Z\lambda }\left ({\eta }\right)$ .

The position vector $\mathbf {b}_{i}$ become:

SECTION V. Results With Synthetic Data

The tests were carried out with the MATLAB Levenberg-Marquardt algorithm without noise and bias. The base stations $B_{i}$ , the transponder $T_{j}$ and the initial estimates were randomly generated in a $10\times 10\times 10$ cube. For each $N$ and $M$ , 10,000 constellations were created. The evaluation of the dimension-lifting methods are done by the mean square error between all objects provided by the optimization and the ground truth distances. The evaluation of the improved function has to take the additional dimension $\lambda $ into account.

A. Two-Dimensional Positioning

Table 3 shows the number of false results for the different methods. With more transponders, the number of equations and the number of unknowns increases. More measurements increase the number of equations but also the number of unknown dimensions ($a_{i}, b_{i}, c_{i}, x_{j}, y_{i}, z_{j},\tilde {\lambda _{i}},\lambda _{j}$ ). The opposite occurs in the partially analytical method. The number of unknown variables does not increase but the ratio $Ra$ increases. Therefore, the results improve with more transponders. The methods with the additional dimension behave differently. The additional dimension has the effect that the number of false results decreases for the lifted partially analytical and the lifted fully numerical method.

TABLE 3 False Convergence Rates for a 2-D Model With Synthetic Data. The False Results Represent an RMS Error Larger Than 0.1 m

B. Three-Dimensional Positioning

In Table 4, it can be seen that for the three-dimensional model, the results have the same characteristics as with two dimensions. The only difference to the two-dimensional example is the higher false rate for the lifted methods. It is likely due to the higher number of unkown variables.

TABLE 4 False Convergence Rates for a 3-D Model With Synthetic Data. The False Results Represent an RMS Error Larger Than 0.1 m

SECTION VI. Results With Real Measurement Data

The following section deals with the previously presented methods applied to real distance measurements. The selected hardware is the EVB1000 system from DecaWave. This system is based on ultra-wideband and complies with the IEEE802.15.4-2011 standard [24]. It supports six frequency bands with center frequencies from 3.5 GHz to 6.5 GHz and data rates of up to 6.8 Mb/s. The bandwidth varies with the selected center frequencies, ranging from 500 up to 1000 MHz. This system is able to operate in time-of-arrival and in time-difference-of-arrival mode. In our case, the time of arrival measurement technique is used with the restriction that measurements of distances between base stations are not performed. Table 5 and Figure 4 show the constellations of the base stations with the identification numbers one to four. The base stations are not changing their positions, only the tag. Distance measurements of the DecaWave transceiver are affected mainly by three parameters, namely the clock drift, the signal power and the antenna delay. The antenna delay can be obtained by self-calibration or with the knowledge about the ground truth distance. This article deals with the effect of an additional dimension on the TOA self-calibration and the following example should be as simple as possible. Therefore, the antenna delay and the other erros have been already corrected for the distance measurements. The ground truth distances have been obtained by a laser distance sensor.

TABLE 5 Coordinates of the Stations

FIGURE 4.

Experimental setup with Decawave UWB. The four UWB base stations with the identification number one to four are mounted on a tripod. The tag is located on the left side in the picture.

In the first test scenario, the position of the transponder changes 23 times. Every distance measurement is based on the mean of 2000 measurements in one position. The standard deviation is around 0.0185 m. Figure 5 shows the constellation of the base stations and the transponder positions. The optimization is repeated 10,000 times, with random initial estimates and the random selection of 12 measurements out of the 23 available measurements, without selecting the same set of measurements twice. In the next test $N=4$ and $M=23$ , all of the 23 available measurements are used for the optimization. The results of the optimization of both test cases are presented in table 6. Similar to the synthetic data, the results of the lifted objective function are better than those of the regular objective function. The false rate is much smaller compared to the synthetic data. The reason is probably that the constellation of the base stations is well suited for self-calibration. It can be observed that similarly to the synthetic data, the number of false results increases with more measurements for the fully numerical method, but decreases for the partially analytical method. The false rate with the regular objective function is about 30 percent and for the lifted objective function is 0.1 percent. In contrast to the synthetic data, the lifted fully numerical method is better than the lifted partially analytical method. This could be due to the fact that the analytical solution is more affected by noise compared to the fully numerical solution. This assumptions is checked by repeating the self-calibration with synthetic distances for the same station configuration and random initial estimates. Table 7 shows the results of the optimization with $N=4$ and $M=12$ with increasing Gaussian noise. It can be observed that the results of the fully numerical and the lifted fully numerical method without noise comes very close to the real measurements, most likely due to the good geometrical constellation. The false result rate of the lifted partially analytical method increases with noise. The noise of the real measurements has a standard deviation of 0.0259 m. Optimizations performed with real and synthetic measurements have similar false rates close to this deviation. For both of the non-lifted methods, a slight improvement can be seen as the noise increases. This could be due to the extra noise “lubricating” the iterative/gradient-descent optimization process.

TABLE 6 False Convergence Rates for real 2-D Measurements With a Stationary Transponder. The False Results Represent an RMS Error Larger Than 0.1 m

TABLE 7 False Convergence Rates for Synthetic 2-D Distance Measurements With Noise. The Constellation of the Base Stations and Transponders is Equal to the Table 6. The False Results Represent an RMS Error Larger Than 0.1 m

FIGURE 5.

Constellation of the real base stations and stationary transponders represented by red circles and by blue crosses, respectively.

The number of measurements can be significantly increased by using a moving transponder. This requires a good data filter and outlier detection. Figure 6 shows the path of the transponder in our experiment. In some areas the data is missing due to outlier removal.

FIGURE 6.

Constellation of the real base stations and one moving transponder represented by red circles and by blue crosses, respectively.

Generally, it is advised to filter the raw data before the trilateration. Otherwise, it is possible that the nonlinear process transforms the Gaussian noise to non-Gaussian [25]. The outlier effect has been reduced by pre-filtering of the data. In order to remove outliers was in the first filtering step, a moving average filter with a time frame of 100 measurements used. Every raw measurement with a distance greater than 10 cm from the moving average has been assumed to be an outlier. After the outlier elimination, the remaining raw data was filtered with a moving average filter with a width of 5 values. The higher size of measurements was selected to make the filter less dynamic for the outlier detection. The second filtering was performed with a smaller window size to reduce the risk of over smoothing.

The results can be seen in Figure 7. After filtering, the measurement data was split into different path sections. The number of path sections is equal to the number of transponder positions $M$ . In every optimization test, one measurement of the filtered data from each of the path sections was randomly selected for the optimization.

FIGURE 7.

Filtered distance measurements $d_{i,j}$ between the base stations and transponders. The different colors stands for base stations with the ID one to four.

The results of 10,000 tests can be seen in Table 8. The lifted objective function performed much better than the regular objective function.

TABLE 8 False Convergence Rates for Real 2-D Measurements With a Moving Transponder. The False Results Represent an RMS Error Larger Than 0.1 m

The optimization time depends on the hardware / software environment. With a higher number of dimensions, the computing time also increases. With an Intel Core i7-6600U 2.60 GHz, 16 GB RAM and 80 unknown variables, the optimization with the lifted approach took up to half a second longer. The time difference between the two approaches can be further reduced by parallel optimization.

SECTION VII. Conclusion

In this paper, we have presented a dimension lifting approach to the non-linear optimization for solving the self-calibration problem in time-of-arrival positioning. The objective function has been extended with an additional coordinate for all position vectors. It has been compared to the unmodified objective function with two different optimization methods: using a numerical method to optimize all unknown parameters (fully numerical), and only applying it to the base station positions and determining the tag positions analytically (partially analytical). The lifted objective function has been evaluated with both methods for both synthetically generated random geometrical constellations and real measurements using an ultra-wideband positioning system. The evaluation criterion was the percentage of non-convergence to the known correct solution under varying initial estimates.

In all cases the modified objective function performed better than the conventional one. For synthetic data with arbitrary random geometry, the partially analytical method was superior, with an improvement of a factor between 83 and 560 compared to the unmodified objective function. For noisy measurement data with a reasonable base station constellation, the fully numerical method converged correctly for any initial estimate for a sufficient number of measurements. With the partially analytical method, the improvement compared to the unmodified objective function was between 40 and 96. We conclude that our dimensional lifting approach to TOA self-calibration improves the convergence properties of the objective function considerably. Combined with the partially analytical optimization method, this advantage persists for arbitrary geometrical constellations of base stations, while the fully numerical method can be more robust to noise for reasonable constellations. This approach has already been applied to positioning itself and is worth considering for other non-linear optimization problems that do not lend themselves to linear approximations.