Optimization of Time Synchronization and Algorithms with TDOA Based Indoor Positioning Technique for Internet of Things

Abstract

To provide high-precision positioning for Internet of Things (IoT) scenarios, we optimize the indoor positioning technique based on Ultra-Wideband (UWB) Time Difference of Arrival (TDOA) equipment. This paper analyzes sources of positioning error and improves the time synchronization algorithm based on the synchronization packet. Then we use the labels of the known position to further optimize the time synchronization performance, and hence improve TDOA measurements. After time synchronization optimization, a Weighted Least Square (WLS) and Taylor coordination algorithm is derived. Experiments show that our optimization reduces the average positioning error from 54.8 cm to 12.6 cm.

1. Introduction

The number of connected devices is increasing rapidly and will soon continue to grow exponentially. Internet of things (IoT) is a hot research topic, including various application scenarios such as smart transportation, smart security, indoor positioning, etc. Therefore, research on indoor positioning and Location-Based Service (LBS) are receiving increasing attention [1,2]. Thanks to the support of edge computing [3], we can achieve an optimized LBS delivery through the reduced end-to-end latency and load on the transport network.

GNSS is a widely used outdoor positioning technology based on traveling time measurement of the arriving signals. It demonstrates high accuracy, good stability and global coverage. One of the key technologies of GNSS is the time synchronization of the signal transmitter and receiver. When the observation error of the arrival time of the electric signal is less than 3 nanoseconds, the positioning accuracy is better than 1 m. However, we cannot directly transplant GNSS technology to indoor positioning [4] because of the complicated indoor environment, signal interference and equipment cost, etc. In recent years, scholars have proposed different technologies for solving indoor positioning problems [5]. In this article, we focus on the ultra-wideband (UWB), which is widely used in Internet of Things scenarios. UWB signal has low power consumption and strong penetration ability, so it can measure and locate things in complex environments. The bandwidth of UWB is generally several GHz, leading to good time resolution. Therefore, the positioning accuracy of UWB can theoretically achieve the centimeter level.

Among UWB positioning techniques, time-based positioning solutions are dominant, including Time of Arrival (TOA) and Time Difference of Arrival (TDOA) methods. In time-based indoor positioning solutions, time synchronization technology is the cornerstone of high-precision positioning [6]. In TOA-based UWB positioning systems, the clock between the label and the base station needs to be synchronized, and the clock between each base station also needs to achieve synchronization. Meanwhile, UWB positioning systems based on TDOA only require clock synchronization to be maintained among the base stations. In UWB positioning technology based on TDOA, there are three schemes for achieving time synchronization:

• Synchronization based on a known reference label. Here, the time difference between the signals from the reference label or mobile label and the two fixed base stations is called the single-difference. The difference between the known reference label and another mobile label is defined as the double-difference, which eliminates the clock differences of both the base stations and the labels. This algorithm is inherited from the GPS double-difference observation algorithm and is very common in pseudo-satellite and Locata indoor positioning [7,8]. Both GPS and Locata have base station (or satellite) transmitting signals, but this time synchronization technology is also suitable for label transmitting signals. It is also used in UWB positioning [9]. However, in a complex and ever-changing indoor environment, it is difficult to observe a reference label with a known position without obstruction in the whole process. In addition, base stations and labels need to have the functions of receiving signals and sending signals, and the transmitter must send signals at specified time intervals, which increases the complexity of the device. Therefore, it is only suitable for large and high-cost projects, and is difficult to expand to popular applications.
• Synchronization based on two-way ranging. In this scheme, both base stations and labels are transceivers. The label (or base station) receives the signal sent by the base station (or label) and forwards it back. After receiving the response signal, the base station (or label) can calculate the distance to the label (or base station) by calculating the time interval between the sent and the rebound signal. Scholars have proposed a scheme to achieve wireless (UWB) clock synchronization by using two-way message exchange [10,11]. The principle of this scheme is simple, and the accuracy is high. However, the base stations and labels must be transceivers. Therefore, the hardware structure of the system is complex, the cost of equipment is high, and the amount of communication is large, and it is difficult to extend it for popular applications, too [12].
• Synchronization based on timestamp [13]. In this method, the master base station uses the physical layer broadcast function to periodically send messages to the slave base stations. The slave base station uses the arrival time of the message as the reference point of its own clock. The broadcast message contains accurate timestamp. Although this method has less anti-interference compared to other methods, the device of this scheme is simple and the communication volume is small, leading it to be widely used in UWB clock synchronization [14].

2. Time Synchronization and Algorithm

In summary, this paper tries to improve the time synchronization scheme with timestamp. The improved scheme is called clock synchronization based on synchronization packets. First, a master base station is selected from among the base stations participating in the positioning, and the other base stations are considered slave base stations [15,16]. Then the master base station periodically sends synchronization packets (including the exact synchronization packet transmission time) to the slave base stations to achieve clock synchronization between the base stations.

The positioning equations based on TDOA measurements have nonlinear characteristics. Therefore, we usually need to convert it into a linear system of equations before solving. Friedlander et al. [17], Schsu et al. [18] and Smith et al. [19] all proposed positioning solution algorithms based on Least Square (LS), but the solutions of the above algorithms are suboptimal. The Chan algorithm [20] uses the double least squares algorithm to give a non-iterative closed solution to the positioning equations. When the TDOA measurement error is relatively small, Chan has the best estimation performance. However, with the increase of TDOA measurement error, the performance of Chan algorithm deteriorates rapidly. The Taylor algorithm is an effective method for solving nonlinear equations, and has the characteristics of high accuracy and good robustness [21,22]. When the initial coordinates of the label have a certain level of accuracy, the Taylor algorithm converges quickly. However, if the initial coordinates of the label are inaccurate, the Taylor algorithm may not converge [23].

This article focuses on UWB indoor positioning technology based on time difference of arrival (TDOA). First, the clock synchronization problem is solved, then the residual error is calibrated, and finally the positioning algorithm is optimized.

2.1. Clock Synchronization Modeling

TOA measures the propagation time of the signal from the label to the base station. The one-way observation equation can be expressed as:

$${\Delta t}_j^{A_i}=t^{A_i}-t_j=\frac{\Vert {\overrightarrow{x}}^{A_i}-{\overrightarrow{x}}_j\Vert }{c}+\left({\tau }^{A_i}-{\tau }_j\right)+{\tau }_m^{A_i}+{\Delta \tau }_j^{A_i}$$

(1)

where ${\overrightarrow{x}}^{A_i}$ is the position vector, the superscript ($A_i$) represents the i-th base station, and the subscript (j) represents the j-th label; $\Vert {\overrightarrow{x}}^{A_i}-{\overrightarrow{x}}_j\Vert /c$ is the geometric error term and $c$ is the speed of light; $\left({\tau }^{A_i}-{\tau }_j\right)$ is the clock difference; ${\tau }_m^{A_i}$ is the multipath error term which from both label and base station. $\Delta {\tau }_j^{A_i}$ are the other error items, such as hardware delay, cable delay, transmission medium delay, etc.

The time difference of arrival (TDOA) between two base stations (A1 and A2) to the same label can be expressed as:

$$\Delta t_j^{A_2}-\Delta t_j^{A_1}=\frac{\Vert {\overrightarrow{x}}^{A_2}-{\overrightarrow{x}}_j\Vert -\Vert {\overrightarrow{x}}^{A_1}-{\overrightarrow{x}}_j\Vert }{c}+\left({\tau }^{A_2}-{\tau }^{A_1}\right)+\left({\tau }_m^{A_2}-{\tau }_m^{A_1}\right)+\left(\Delta {\tau }_j^{A_2}-\Delta {\tau }_j^{A_1}\right)$$

(2)

Assuming $\Delta {\tau }^{A_2,A_1}=\left({\tau }^{A_2}-{\tau }^{A_1}\right)+\left({\tau }_m^{A_2}-{\tau }_m^{A_1}\right)+\left(\Delta {\tau }_j^{A_2}-\Delta {\tau }_j^{A_1}\right)$, it is the total error of the TDOA-based positioning scheme. Because the clock difference of the label has been eliminated in the single difference, $\left({\tau }^{A_2}-{\tau }^{A_1}\right)$ is the clock difference between two base stations. When we synchronize the base station clocks, the $\left({\tau }^{A_2}-{\tau }^{A_1}\right)$ represents the synchronization error, it is usually small and is close to a fixed value. $\left({\tau }_m^{A_2}-{\tau }_m^{A_1}\right)$ is the multipath error difference primarily between the two base stations. Multipath errors include extra distance caused by environmental reflections and extra delay in hardware [24]. It is usually at the meter level or more. The base stations are installed at the top of a room with little environmental change, so the multipath error remains relatively unchanged. Therefore, the multipath error difference between two base stations is considered to be a fixed value, which is only affected by the base station. $\left(\Delta {\tau }_j^{A_2}-\Delta {\tau }_j^{A_1}\right)$ is the difference of other error terms. Hardware delay and cable delay are only relevant to the base station. Due to the short indoor propagation distance, the medium delay is small and can be ignored. Therefore, $\left(\Delta {\tau }_j^{A_2}-\Delta {\tau }_j^{A_1}\right)$ is considered to be a fixed value.

In summary, $\Delta {\tau }^{A_2,A_1}$ is the total error difference between two base stations (A2 and A1), which is approximately to a constant. The error calibration method will provide a practical approach to calculate $\Delta {\tau }^{A_2,A_1}$. If the clock deviation of the two base stations is 1 ns [25], then the TDOA measurement value will also have an error of 1 ns, representing a distance error of 30 cm. Therefore, clock synchronization becomes key to ensuring cm level positioning accuracy.

In general, the base station uses a hardware oscillator to generate the time label. Let the C(t) denote the base station clock time. For a perfect clock, $dC\left(t\right)/dt=1$. However, the hardware oscillators all have frequency deviations due to their physical conditions and other factors. It has been found [26] that although the clock frequency is constantly changing, the following formula can be used to approximate the local clock of the base station $i$:

$$C_i\left(t\right)=a_{i}t+b_i$$

(3)

where $a_i$ is the drift rate of the base station clock, $b_i$ is the offset of the base station clock, which represents the difference between local time and real time at the beginning. To compare the local clocks of base station 1 and base station 2, it can be expressed as:

$$C_1\left(t\right)=a_{12}{C}_{12}\left(t\right)+b_{12}$$

(4)

where $a_{12}$ and $b_{12}$ are the relative drift rate and offset between the clocks of base station 1 and base station 2, respectively. There are two requirements for clock synchronization: (1) the rates of change of the clocks are the same; (2) the offset between the clocks is equal to zero. In short, clock synchronization adjusts the clocks of all base stations in a unified network.

In this paper, we first select a master base station among the base stations participating in positioning, and the other base stations are called the slave base stations. Then, the master base station periodically sends synchronization packets to the slave base stations to achieve clock synchronization between the base stations. In this algorithm, the TOA value recorded by the base station clock is converted into the corresponding TOA value of the master base station clock. Among them, the TOA value measured by the master base station does not need to be converted. Finally, the converted TOA value of the slave base station minus the TOA value of the master base station can get the TDOA value after clock synchronization. The process of obtaining the label TDOA value is:

(1)

The master base station sends a synchronization packet $k$ (including the transmission time of the synchronization packet $t_k^{M,S}$) to the slave base station. After receiving the synchronization packet, the slave base station saves $t_k^{M,S}$ and the local time $t_k^{S_i,R}$ at that moment.

(2)

The label sends a positioning packet $m$. After receiving the positioning packet, each base station saves the local time ($t_m^{S_i,R,T}$ or $t_m^{M,R,T}$) at that moment.

(3)

The master base station sends a synchronization packet $k+1$ (including the transmission time of the synchronization packet $t_{k+1}^{M,S}$) to the slave base station. After receiving the synchronization packet, the slave base station saves $t_{k+1}^{M,S}$ and the local time $t_{k+1}^{S_i,R}$ at that moment.

Both $t_k^{S_i,R}$ and $t_{k+1}^{S_i,R}$ reduce the propagation time of the synchronization packet between the master base station and the slave base station. The base station coordinates are known and fixed, so the distance between the master and slave base stations is calculated using the point-to-point distance formula. The distance is divided by the speed of light to obtain the propagation time of the synchronization packet between the master and slave base stations. The specific process is shown in Figure 1.

According to Equation (4), the clock of the master base station $M$ can be expressed by the clock of the slave base station $S_i$:

$$C_M\left(t\right)=a_{M,S_i}{C}_{S_i}\left(t\right)+b_{M,S_i}$$

(5)

where $a_{M,S_i}$ and $b_{M,S_i}$ are the relative drift rate and offset between the clocks of the master and slave base stations, respectively. In the positioning system, the base station is equipped with the same clock, and the indoor environment is roughly the same, and the transmission interval of the synchronization packet is also very small, so $a_{M,S_i}$ and $b_{M,S_i}$ are considered to be fixed values. Therefore, Equation (5) satisfies the nature of a linear function, as shown in Figure 2.

The TOA value recorded by the base station clock is converted into the corresponding TOA value of the master base station clock; the calculation method is as shown in Equation (6):

$$\frac{t_m^{S_i,R,T,M}-t_k^{M,S}}{t_{k+1}^{M,S}-t_k^{M,S}}=\frac{t_m^{S_i,R,T}-t_k^{S_i,R}}{t_{k+1}^{S_i,R}-t_k^{S_i,R}}$$

(6)

Because both $t_m^{S_i,R,T,M}$ and $t_m^{M,R,T}$ are recorded by the master base station, the TDOA value is equal to the TOA value of the base station $t_m^{S_i,R,T,M}$ minus the TOA value of the master base station $t_m^{M,R,T}$.

2.2. Error Calibration Method

In addition to clock synchronization, there are multipath effects, hardware delays, media delays, and other errors in the positioning process. Therefore, this paper proposes an error processing scheme based on the calibration method, which uses the labels at known locations to determine the error value and stores it in the local server. Then in the following positioning steps, the error value is used to compensate the TDOA value to reduce the positioning error.

In the calibration method, first, a label $S$ (fixed and known coordinates) is required for error measurement. To better explain the error calibration method, a single positioning unit is extracted in the positioning system, as shown in Figure 3.

The time difference $t_s^{A_i}$ between the base station $A_i$ and the label $S$ is

$$t_S^{A_i}=\frac{R_S^{A_i}+l^{A_i}}{c}+{\tau }^{A_i}-{\tau }_S$$

(7)

where $R_S^{A_i}$ is the distance between the base station $A_i$ and the label $S$. $l^{A_i}$ is the total error of a single positioning (expressed in the form of length). ${\tau }_S$ is the clock difference of the label $S$ clock during the period when it sends the signal. ${\tau }^{A_i}$ is the clock difference of the base station $A_i$ clock during the period when it receives the signal. The TDOA value of the same positioning signal measured by base stations $A_2$ and $A_1$ is expressed in the form of length:

$$\Delta R_S^{A_2,A_1}=R_S^{A_2}-R_S^{A_1}+c\left({\tau }^{A_2}-{\tau }^{A_1}\right)+\left(l^{A_2}-l^{A_1}\right)$$

(8)

which is the difference between the base station $A_2$ and $A_1$ for the same positioning signal of the label, so the label clock difference term is eliminated. ${\tau }^{A_2}-{\tau }^{A_1}$ is the clock difference between base stations $A_2$ and $A_1$ when they receive the label $S$ signal. The base station has already performed clock synchronization, so ${\tau }^{A_2}-{\tau }^{A_1}$ is eliminated and the remaining is small and classified into $\Delta l^{A_{i_2-i_1}}$, which can be ignored. Therefore, Equation (8) can be simplified as:

$$\Delta R_S^{A_2,A_1}=\left(R_S^{A_2}-R_S^{A_1}\right)+\Delta l^{A_2,A_1}$$

(9)

where $\Delta l^{A_2,A_1}=l^{A_2}-l^{A_1}$ represents the difference between the total error (including the clock residual item, multipath error, and other errors) between the base stations $A_2$ and $A_1$ when calculating the TDOA value of the same label. It is known from Chapter 2.1 that $\Delta {\tau }^{A_2,A_1}$ is also the difference between the total errors (including the clock residual item, multipath error, and other errors) of the two base stations. Please note that $\Delta l^{A_2,A_1}$ is the length expression of relative total error, and $\Delta {\tau }^{A_2,A_1}$ is the time expression of relative total error, so that $\Delta l^{A_2,A_1}=\Delta {\tau }^{A_2,A_1}\ast c$. The positioning algorithm based on TDOA uses the distance difference to construct a system of equations to achieve the positioning function. Therefore, converting $\Delta {\tau }^{A_2,A_1}$ to $\Delta l^{A_2,A_1}$ and storing it in the local server will reduce the actual positioning error. From Equation (9), we can get:

$$\Delta l^{A_2,A_1}=\Delta R_S^{A_2,A_1}-\left(R_S^{A_2}-R_S^{A_1}\right)$$

(10)

where $\Delta R_S^{A_2,A_1}$ is an observation measurement, which can be obtained by multiplying $\Delta t_S^{A_2,A_1}$ and the speed of light. $\Delta t_S^{A_2,A_1}$ represents the TDOA value measured by the base stations $A_2$ and $A_1$. $\left(R_S^{A_2}-R_S^{A_1}\right)$ is the difference between the base station $A_2$ and $A_1$ from the label $S$. In the error processing, the positions of the set base station and the label are both known and fixed, so $\left(R_S^{A_2}-R_S^{A_1}\right)$ can be calculated by the point-to-point distance formula.

In summary, $\Delta l^{A_2,A_1}$ can be calculated using Equation (10). To measure the error calibration value more accurately, this article changes the position of the label many times to form redundant measurements. Then, the best error calibration value is calculated by taking the average of the error calibration values, and storing it in the local server, before finally applying it in actual positioning to reduce the positioning error.

2.3. WLS and Taylor Cooperating Algorithm

Based on the error calibration, this paper proposes a Weighted Least Square (WLS) and Taylor collaborative positioning algorithm based on error calibration, which uses WLS to estimate the initial value of the label and uses the Taylor algorithm to determine the label coordinates. The error calibration value is used to compensate the TDOA value of WLS equations and Taylor algorithm.

As shown in Equation (11), the distance between the base station $A_i\left(x^{A_i},y^{A_i}\right)$ and the label $T\left(x,y\right)$ is:

$$R_T^{A_i}=\sqrt{{\left(x^{A_i}-x\right)}^2+{\left(y^{A_i}-y\right)}^2}$$

(11)

Equation (10) can be transformed into:

$$\begin{gathered} \Delta R_T^{A_i,A_1}=\left(R_T^{A_i}-R_T^{A_1}\right)+\Delta l^{A_i,A_1} \\ {R}_T^{A_i}=\left(\Delta R_T^{A_i,A_1}-\Delta l^{A_i,A_1}\right)+R_T^{A_1} \end{gathered}$$

(12)

where $\Delta R_T^{A_i,A_1}$ is the distance difference corresponding to the original TDOA value of the base stations $A_i$ and $A_1$ receiving the label $T$ signal, which can be obtained by multiplying the direct observation (TDOA value) and the speed of light. $\Delta l^{A_i,A_1}$ is the error calibration value of base stations $A_i$ and $A_1$, as measured in advance using the error calibration method. $\left(R_T^{A_i}-R_T^{A_1}\right)$ contains the coordinates of the label $T$, which is the unknown quantity to be solved.

Set the base station $A_1$ as the main base station, and transform Equation (11) to obtain:

$$\begin{array}{c}\left(x^{A_i}-x^{A_1}\right)x+\left(y^{A_i}-y^{A_1}\right)y\hfill \\ =\frac{1}{2}\left({\left(R_T^{A_1}\right)}^2-{\left(R_T^{A_i}\right)}^2\right)+\frac{1}{2}\left({\left(x^{A_i}\right)}^2+{\left(y^{A_i}\right)}^2-{\left(x^{A_1}\right)}^2-{\left(y^{A_1}\right)}^2\right)\hfill \end{array}$$

(13)

where $i=2, 3, 4$ and Equation (13) is a general expression of the geometric distance squared difference in two-dimensional space. Substituting Equation (12a) into Equation (13) gives:

$$\begin{array}{l}(x^{A_i}-x^{A_1})x+(y^{A_i}-y^{A_1})y+(\Delta R_T^{A_i,A_1}-\Delta l^{A_i,A_1})R_T^{A_1}=\\ -\frac{1}{2}{\left(\Delta R_T^{A_i,A_1}-\Delta l^{A_{\mathrm{i}},A_1}\right)}^2+\frac{1}{2}({\left(x^{A_i}\right)}^2+{\left(y^{A_i}\right)}^2-{\left(x^{A_1}\right)}^2-{\left(y^{A_1}\right)}^2)\end{array}$$

(14)

Let $\mathit{A}=\left[\begin{array}{ccc}{x}^{A_2}-x^{A_1}& y^{A_2}-y^{A_1}& \Delta R_T^{A_2,A_1}-\Delta l^{A_2,A_1}\\ x^{A_3}-x^{A_1}& y^{A_3}-y^{A_1}& \Delta R_T^{A_3,A_1}-\Delta l^{A_3,A_1}\\ x^{A_4}-x^{A_1}& y^{A_4}-y^{A_1}& \Delta R_T^{A_4,A_1}-\Delta l^{A_4,A_1}\end{array}\right]$, $\Delta \mathit{R}=-\frac{1}{2}\left[\begin{array}{c}{\left(\Delta R_T^{A_2,A_1}-\Delta l^{A_2,A_1}\right)}^2\\ {\left(\Delta R_T^{A_3,A_1}-\Delta l^{A_3,A_1}\right)}^2\\ {\left(\Delta R_T^{A_4,A_1}-\Delta l^{A_4,A_1}\right)}^2\end{array}\right]$, ${\mathit{P}}_T=\left[\begin{array}{c}x\\ y\\ R_T^{A_1}\end{array}\right]$, $\mathit{\lambda }=\frac{1}{2}\left[\begin{array}{c}{\left(x^{A_2}\right)}^2+{\left(y^{A_2}\right)}^2-{\left(x^{A_1}\right)}^2+{\left(y^{A_1}\right)}^2\\ {\left(x^{A_3}\right)}^2+{\left(y^{A_3}\right)}^2-{\left(x^{A_1}\right)}^2+{\left(y^{A_1}\right)}^2\\ {\left(x^{A_4}\right)}^2+{\left(y^{A_4}\right)}^2-{\left(x^{A_1}\right)}^2+{\left(y^{A_1}\right)}^2\end{array}\right]$.

In conclusion, we get

$$\mathit{A}{\mathit{P}}_T=\Delta \mathit{R}+\mathit{\lambda }$$

(15)

To reduce the impact of TDOA measurement errors on the positioning results, Equation (15) adds a covariance matrix. After matrix transformation, we get:

$${\mathit{P}}_T={\left({\mathit{A}}^T{\mathit{Q}}^{-1}\mathit{A}\right)}^{-1}{\mathit{A}}^T{\mathit{Q}}^{-1}\left(\Delta \mathit{R}+\mathit{\lambda }\right)$$

(16)

where $\mathit{A}$ and $\mathit{\lambda }$ are known, and $\Delta \mathit{R}$ is the observation matrix after precalibrated propagation delays are corrected. $\mathit{Q}$ is the covariance matrix of observation. Equation (16) can calculate the label coordinates $\left(x_0,y_0\right)$ and $R_T^{A_1}$.

Equation (16) is a system of equations based on WLS, with small calculation amount and fast speed. When the positioning is in a complex environment such as NLOS, the measurement accuracy of the label TDOA value will be reduced. However, after the error calibration of the TDOA value, the calculation result of Equation (16) can still roughly reflect the true position of the label. Therefore, the solution based on the WLS equation system can meet the requirements of the initial coordinates of the Taylor algorithm. The Taylor algorithm adjusts the label coordinates through the local WLS solution. It has high precision and good stability, but it has a strong dependence on the selection of the label initial coordinates. In summary, this paper proposes a WLS and Taylor collaborative positioning algorithm based on error calibration.

The standard Taylor algorithm is expressed as Equation (17) [27].

$$\mathit{h}=\mathit{G}\mathit{\Delta }+\mathit{\epsilon }$$

(17)

Let, $\mathit{\Delta }=\left[\begin{array}{c}\Delta x\\ \Delta y\end{array}\right]$, $\mathit{G}=\left[\begin{array}{cc}\frac{\left(x^{A_1}-x\right)}{R_T^{A_1}}-\frac{\left(x^{A_2}-x\right)}{R_T^{A_2}}& \frac{\left(y^{A_1}-y\right)}{R_T^{A_1}}-\frac{\left(y^{A_2}-y\right)}{R_T^{A_2}}\\ \frac{\left(x^{A_1}-x\right)}{R_T^{A_1}}-\frac{\left(x^{A_3}-x\right)}{R_T^{A_3}}& \frac{\left(y^{A_1}-y\right)}{R_T^{A_1}}-\frac{\left(y^{A_3}-y\right)}{R_T^{A_3}}\\ \frac{\left(x^{A_1}-x\right)}{R_T^{A_1}}-\frac{\left(x^{A_4}-x\right)}{R_T^{A_4}}& \frac{\left(y^{A_1}-y\right)}{R_T^{A_1}}-\frac{\left(y^{A_4}-y\right)}{R_T^{A_4}}\end{array}\right]$, $\mathit{h}=\left[\begin{array}{c}\Delta R_T^{A_{2,}{A}_1}-\left(R_T^{A_2}-R_T^{A_1}\right)\\ \Delta R_T^{A_{3,}{A}_1}-\left(R_T^{A_3}-R_T^{A_1}\right)\\ \Delta R_T^{A_{4,}{A}_1}-\left(R_T^{A_4}-R_T^{A_1}\right)\end{array}\right]$.

After compensating the TDOA value with error calibration, $h$ in Equation (17) becomes $\mathit{H}$, $\mathit{H}=\left[\begin{array}{c}\Delta R_T^{A_{2,}{A}_1}-\Delta l^{A_2,A_1}-\left(R_T^{A_2}-R_T^{A_1}\right)\\ \Delta R_T^{A_{3,}{A}_1}-\Delta l^{A_3,A_1}-\left(R_T^{A_3}-R_T^{A_1}\right)\\ \Delta R_T^{A_{4,}{A}_1}-\Delta l^{A_4,A_1}-\left(R_T^{A_4}-R_T^{A_1}\right)\end{array}\right]$. Then, using WLS to process the formula, we can get the improved Taylor algorithm expression:

$$\mathit{\Delta }={\left({\mathit{G}}^T{\mathit{Q}}^{-1}\mathit{G}\right)}^{-1}{\mathit{G}}^T{\mathit{Q}}^{-1}\mathit{H}$$

(18)

where $\mathit{Q}$ is the covariance matrix of observation.

3. Experimental Verification

3.1. Experimental Environment

To illustrate the effectiveness of the error-calibrated WLS and Taylor collaborative algorithm (WLS-Taylor) in real indoor scenarios, experiments were needed. The experimental equipment came from Jiangsu Tangen Technology Co., Ltd. The experimental area was approximately 7 m long and 6 m wide, and was located on the fourth floor of a building of the East China Normal University, being a typical meeting-room environment including one table, chairs, one projector, cabinets, pendent lamps, etc. The experimental environment is shown in Figure 4, with Figure 4a giving the plan of the experimental area, and Figure 4b,c giving the real experimental area.

We used TDOA in the UWB positioning system for the experiment. The system included a hardware and a software component that supported clock synchronization and multiple label access. As shown in Figure 4, the location system had four base stations, of which one was the master base station and three were slave base stations [28].

In the experiment, we preliminarily selected some test points, and sequentially placed the bracket that was used to hold the label at those points. Then, we collected approximately 3000 sets of data without interruption, where the signal of the label was sent at a frequency of 32 Hz. Finally, different algorithms were used to calculate the estimated coordinates of the labels to achieve a controlled experiment. The actual position of the label is measured by an infrared rangefinder, the estimated coordinates were calculated by different algorithms. Afterwards, we calculated the root mean square error between the actual position and the estimated coordinates and the mean of the RMSE (root mean square error) for 3000 data sets which recorded as the positioning error at that point.

3.2. Accuracy Evaluation

The average root mean square error between the actual position and the estimated position is used to measure the positioning error of the algorithm.

$$\overline{e}=\frac{1}{N_p}{\displaystyle \sum _{i=1}^{Np}}\sqrt{\frac{1}{N_t}{\displaystyle \sum _{t=1}^{Nt}}{e}_i^2\left(t\right)}=\frac{1}{N_p}{\displaystyle \sum _{i=1}^{Np}}\sqrt{\frac{1}{N_t}{\displaystyle \sum _{t=1}^{Nt}}\Vert P_i\left(t\right)-{\widehat{P}}_i{\left(t\right)\Vert }^2}$$

(19)

where $P_i\left(t\right)$ represents the actual position of the i-th test point; ${\widehat{P}}_i\left(t\right)$ represents the estimated position based on the t-th sampling value of the i-th test point; $N_t$ and $N_p$, respectively, represent the sampling number and the testing number of the test point.

3.3. Results Analysis and Discussion

To verify the validity of the WLS-Taylor algorithm, we compared it with the Chan and Taylor (Chan–Taylor) algorithm [29] using TDOA values with and without error calibration.

In the Chan–Taylor algorithm, the output of the Chan algorithm is the initial input of the Taylor algorithm. Then, the Taylor algorithm is sequentially iterted to adjust the coordinates of the label until the sum of the absolute values of the label coordinate change is less than the threshold, outputting the final estimated coordinates of the label.

In the Chan–Taylor algorithm, an extra weighted least squares operation is added to further decrease the perturbation errors of Initial coordinates. In the WLS-Taylor algorithm, we directly used the initial coordinates as the initial value of the Taylor algorithm. The reason for this change is that for the Chan–Taylor algorithm, the primary purpose of the Chan algorithm also meets this requirement, and the calculation amount is smaller than the Chan algorithm because one WLS operation is removed.

The WLS-Taylor algorithm with error calibration uses a pre-calibrated value of error to compensate for the measured TDOA values in the WLS-based equation set and the Taylor algorithm. The results of the WLS-based set of equations were used as the initial values for Taylor and the same calculation of C-T algorithm, allowing us to find the coordinates of the label.

3.3.1. Experimental Analysis of Time Synchronization

We calculated the difference (absolute value) between the 3000 sets of labeled TDOA measurements and the true value to evaluate the performance of the clock synchronization method based on the synchronization package. The TDOA measurement value was obtained by Equation (6). The real TDOA value acquisition is divided into three steps. At first, we calculated the actual distance between the label coordinates and the coordinates of each base station. Second, the distance from the slave base station to the label minus the distance from the master base station to the label was calculated. Third, by dividing by the speed of light, we finally obtained the real TDOA value. Because it is the same system, the base station has the same hardware construction. The clock deviation (absolute value) between one slave base station and the master base station is listed here, and the results are shown in Figure 5.

As shown in Figure 5, the TDOA error is about 1.26 ns when CDF = 90%, and 0.48 ns when CDF = 50%. It can be seen that this synchronization approach is effective.

3.3.2. Experimental Analysis of the WLS-Taylor Algorithm

As shown in Figure 4, the test points are around the table, and we selected one of them as the error calibration point and stored the error scale quantification of the room in local server. The other test points in the room use the error scale quantification for error processing.

In experiments to verify the validity of the WLS-Taylor algorithm, neither the Chan–Taylor algorithm nor the WLS-Taylor algorithm compensated for TDOA values using error scales. The experiment used nine test points to evaluate algorithm performance, except for one error calibration point. The Cumulative Distribution Function (CDF) curves, which are able to completely describe the probability distribution of a real random variable for the positioning results, are shown in Figure 6.

It can be seen from Figure 6 that the positioning accuracy of the WLS-Taylor algorithm is close to that of the Chan–Taylor algorithm. The specific positioning results are shown in

Table 1. Experimental results table of the C-T algorithm and the W-T algorithm.

Algorithm	Max (cm)	Min (cm)	Mean (cm)	Standard Deviation (cm)
Chan–Taylor	88.7	35.7	54.8	9.3
WLS-Taylor	78.8	34.9	55.2	9.2

.

As shown in Table 1, the positioning error of the Chan–Taylor algorithm ranged from 35.7 cm to 88.7 cm, with an average positioning error of 54.8 cm and a standard deviation of 9.3 cm, and the WLS-Taylor algorithm ranged from 34.9 cm to 78.8 cm, with an average positioning error of 55.15 cm and a standard deviation of 9.2 cm. This shows that the use of the WLS-Taylor algorithm can reduce the computational complexity while ensuring the accuracy and stability of the final result.

3.3.3. Experimental Analysis of Error Calibration

To confirm the effectiveness of the error calibration, the TDOA error with error calibration between one slave base station and the master base station was compared with that without error calibration, as shown in Figure 7.

The experiment was based on clock synchronization, as shown in Figure 7; when CDF = 90%, the blue curve is about 0.97 ns, and the green curve is about 1.26 ns, which is an improvement by 23% when using the error calibration. The CDF curve proves the effectiveness of the error calibration.

The green curve in Figure 8 is the result of using the WLS-Taylor algorithm to calculate the estimated coordinates of the label directly without any treatment of the TDOA value; the red curve in Figure 8 is the result of using the error scale to quantitatively compensate the TDOA value and then using the WLS-Taylor algorithm to calculate the estimated coordinates of the label. The error scale quantification and TDOA measurement values are directly added to the algorithm as new TDOA values, and no internal changes are made to the algorithm. Except for 1 error calibration points, the experiment used 9 other test points to evaluate the performance of the algorithm. The CDF curves of the positioning results are shown in Figure 8.

It can be seen from Figure 8 that when CDF = 90%, the positioning accuracy of the W-T algorithm without the use of error calibration is about 67.3 cm; the positioning accuracy of the C-T algorithm with the use of error calibration is about 21.8 cm. It can be seen that the error calibration method improved the positioning accuracy by 67.6%. The specific positioning results are shown in

Table 2. Experimental result table of error calibration method.

Algorithm	Max (cm)	Min (cm)	Mean (cm)	Standard Deviation (cm)
WLS-Taylor without error calibration	78.8	34.9	55.2	9.2
WLS-Taylor with error calibration	30.7	0.1	12.6	7.4

.

As shown in Table 2, the positioning error of the WLS-Taylor algorithm without error calibration ranged from 34.9 cm to 78.8 cm, with a mean positioning error of 55.2 cm and a standard deviation of 9.2 cm, and the positioning error of the WLS-Taylor algorithm with error calibration ranged from 0.1 cm to 30.7 cm, with a mean positioning error of 12.6 cm and a standard deviation of 7.4 cm. Using the standard deviation to measure the stability of the positioning algorithm, it can be seen that the stability of the WLS-Taylor algorithm improved by 19.6% after using the error calibration method.

4. Conclusion

Focusing on the problem that indoor positioning is difficult to achieve high-precision positioning, this paper studied the UWB indoor positioning scheme based on TDOA. The core part was clock synchronization, error calibration and collaborative positioning. With respect to clock deviation between the base stations of UWB positioning system, this paper first proposed a clock synchronization algorithm based on synchronization packets. Then this paper analyzed the principle and error source of TDOA positioning algorithm, and the use of labels with known positions to pre-calibrate errors such as hardware delay and multipath. The error calibration value is stored in the local server to compensate the TDOA measurement value in the actual positioning. Finally, this paper proposed a WLS and Taylor collaborative positioning algorithm based on error calibration. First, the error calibration value is used to compensate the TDOA value, then WLS is used to estimate the initial coordinates of the label and the Taylor algorithm is used to determine the label coordinates.

To obtain a more accurate TDOA value, the clock synchronization method in this paper sends a synchronization packet with a small period. In the next step, algorithms such as Kalman filtering can be introduced to track the clock deviation to reduce the frequency of synchronization packets. This method reduces the calculation load, production cost and volume of the mobile terminal (label), without laying a large number of additional hardware equipment, and without changing the existing hardware equipment, completely relying on software for implementation, strong operability, and easy for popular applications. It has great advantages and business prospects in the indoor positioning application environment where the manager application is the main management for multiple users. In addition, the calibration algorithm has a weakening effect on the multipath effect, but it still has a greater impact on the positioning accuracy and needs further study.