Fusion of time of arrival and time difference of arrival for ultra-wideband indoor localization? Juri Sidorenko1,2[0000−0003−0089−967X] , Volker Schatz1 , Norbert Scherer-Negenborn1 , Michael Arens1 , and Urs Hugentobler2 1 Fraunhofer Institute of Optronics, System Technologies and Image Exploitation IOSB, Germany juri.sidorenko@iosb.fraunhofer.de 2 Institute of Astronomical and Physical Geodesy, Technical University of Munich, Germany Abstract. This article presents a time of arrival and time difference of arrival fusion for Decawave ultra-wideband transceivers. The presented techniques combine the time-of-arrival and time-difference-of-arrival mea- surements without losing the advantages of each approach. The precision and accuracy of the distances measured by the Decawave devices depends on three effects: signal power, clock drift, and uncertainty in the hard- ware delay. This article shows how all three effects may be compensated with both measurement techniques. Keywords: Time Of Arrival · Time Difference Of Arrival · Two-Way Ranging. 1 Introduction Localization systems have become indispensable for everyday life. Satellite nav- igation[1, 2] has displaced paper maps and is now essential for the autonomous operation of cars and airplanes. As the requirements of logistics and manufac- turing processes increase, access to precise positional information is becoming a necessity. Depending on the operating conditions for the localization applica- tion, different measurement principles [3–5] and techniques [6–8] are available. Two of the most common measurement techniques are based on the time of ar- rival (TOA) [6] and the time difference of arrival (TDOA) [7]. The measuring equipment is just as important as the measurement technique itself. This article focuses on indoor radio frequency (RF)-based localization systems. In general, indoor positioning applications are a challenge for RF-based localization systems. Reflections can generate interference with the main signal and lead to fading. Compared to narrowband signals, ultra-wideband (UWB) signals are more ro- bust against fading [9, 10]. The Decawave transceiver [11] uses ultra-wideband (UWB) technology and is compliant with the IEEE802.15.4-2011 standard [12]. 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. Depending on the selected center frequency, the ? Fraunhofer Institute of Optronics, System Technologies and Image Exploitation. 2 Juri Sidorenko et al. bandwidth ranges from 500 to 1000 MHz. Various methods for wireless TDOA clock synchronization are presented in [13–15]. One aspect shared by all of them is that they use a fixed and known time interval for the synchronization sig- nal. In our case, the synchronization signal is part of the localization and the time interval does not need to be known. The solution presented here merges TOA and TDOA measurements to increase the number of equations without los- ing the specific advantages of each method. The measurements are provided by Decawave EVK1000 transceivers without additional synchronization hardware. This system can operate in indoor environments due to its ability to deal with fading. The precision and accuracy of the Decawave UWB depend primarily on three factors: the received signal power, the clock drift, and the hardware de- lay. In [16], we showed how the signal power correction curve can be obtained automatically and how the clock drift can be corrected in every measurement. In the present publication, we demonstrate how to apply these corrections for TOA and TDOA localization. 2 Time of arrival Figure 1 illustrates the concept of TWR and the timestamp shift caused by signal power, as well as the error due to hardware delay. In our implementation, the reference station is the initiator. The first message is sent by the reference station with timestamp T1R . The timestamp of the received message at the tag is affected by the signal power, resulting in a timestamp shift of E1 . The same applies to the response message, this time at the reference station. It is important to note that the timestamps T1R and T2T are not affected by the receiving signal power. However, the hardware delay (A,B) must always be considered. The sending delay is assumed to be equal to the receiving  delay. Without  correction, the TWR signal travel time is 0.5· T2R − T1R − T2T − T1T . TR1 TR2 TR1 TR2 E2 A A Reference station Reference station TOA TOA TOA TOA Tag Tag E1 B B TT1 TT2 TT1 T T2 Fig. 1. Left: Effect of the power on the TOA, Right: Effect of the hardware delay on TOA Title Suppressed Due to Excessive Length 3 The values E1 and E2 are deduced from the signal power correction curve. Note that the signal power may affect the tag and the reference station differ- R ently. At lower signal power, the time difference ∆T1,2 increases. In the previous section, we showed that the clock drift can be corrected by three messages. Figure 2 demonstrates how this principle can be adapted for two-way ranging. The last message is used to calculate the clock drift error RT R T C1,3 = ∆T1,3 − ∆T1,3 . Observe that the signal power E1 does not affect the T timestamp difference ∆T1,3 . TR1 TR2 TR3 E2 Reference station TOA TOA Clock drift correction TOA Tag E1 E1 TT1 TT2 TT3 Fig. 2. TWR clock drift correction 3 Time difference of arrival The previous section showed how the clock drift and the hardware offset influence the time-of-arrival position estimate. In this section, we show how to combine TOA with TDOA. Unlike TDOA, two-way ranging (TWR) based on TOA does not require clock synchronization. One approach to synchronizing the TDOA clock is to use an additional signal [3]. This signal is already present in the two-way ranging (TWR) approach, so a combination of both techniques seems natural. This principle is illustrated in figure 4. The effect of the clock drift and the hardware delay on the TDOA can be seen in figure 3. Two-way ranging is performed between the tag and the reference station. The other stations are passive and do not respond to the reference station or tag. The difference between timestamps two and one at each anchor depends on the positions of the reference station and the tag with respect to the anchor. Unlike the TWR application presented earlier, the influence of the signal power and the hardware delay differs in the TDOA application. In the TDOA application, the influence of the hardware delay is assumed to be the same for both timestamps T1S and T2S . Therefore, the TDOA equation 4 Juri Sidorenko et al. TOA TOA Reference station Tag Reference station Tag TDOA TDOA TS1 TS2 TS1 TS2 E3 E4 C C Station N Station N Fig. 3. Left: Effect of power on the TDOA, Right: Effect of the hardware offset on the TDOA is independent of the hardware delay. However, a new offset K appears, repre- senting the delay between the signal of the tag with respect to the signal of the reference station. If both stations send the signal at exactly the same time, this offset K is zero. 4 Two-dimensional position estimation with four stations In this section, the theoretical concepts are verified with real measurements. The first test scenario uses TOA measurements to estimate the unknown position of the tag. In the second test scenario is the position of the tag estimated by the fused measurements of TDOA and TOA. The tests were carried out with a Decawave EVB DW1000. The Decawave supports different message types, which are specified for the discovery phase, ranging phase and final data transmission. Depending on the update rate and the preamble length, each message can vary from 190 s to 3.4 ms. In our experiments, we only used 190 s messages, also called blink messages. The general settings of the Decawave transceivers are listed in table 1. Table 1. Test settings Channel 2 Center Frequency 3993.6 MHz Bandwidth 499.2 MHz Pulse repetition frequency 64 MHz Preamble length 128 Data rate 6.81 Mbps Figure 5 and table 2 show the constellation of the stations. The ground truth data were obtained by laser distance measurement. The position of the Title Suppressed Due to Excessive Length 5 TR1 TR2 TR3 E2 Reference station 2. 3. Clock drift correction 1. TS1 TS2 TS3 1. E3 E4 E3 Station N 2. 3. Clock drift correction Tag E1 E1 TT1 TT2 TT3 Fig. 4. TOA and TDOA clock drift correction tag with identification number (ID) 2 is assumed to be unknown. The other stations are used to estimate the position of this tag. The station identified as the reference station changes during TWR positioning. This is because the distances between the tag and the other stations must be calculated successively for TWR trilateration. Unlike TWR, the reference station remains the same for TDOA; in this example, the reference station is the station with ID 1. This also explains why TDOA is much faster than TWR. Table 2. Position of the stations obtained by laser distance measurements Station ID X-Axis [m] Y-Axis [m] 1 0 0 2 0 1.5134 3 1.27 1.643 4 1.1439 0.0385 Figure 6 shows the results of the TOA and TDOA position estimate of station 2. The mean values of TOA and TDOA differ by 0.0023 m on the x-axis and 0.0006 m on the y-axis. This difference is small, indicating that the assumptions regarding the offset and the clock drift are correct. The deviation between the mean values of the TOA and TDOA measurements and the ground truth data may be explained by uncertainty in the hardware delay and the ground truth data estimate. 6 Juri Sidorenko et al. Fig. 5. Constellation of the stations The following table 4 shows the standard deviation of the precision of the TOA and TDOA position estimates. The y-axis scattering is almost exactly equal for both measurement techniques. On the other hand, the x-axis scattering of TDOA is higher than that of TOA, depicted in Table 3. Table 3. Covariance matrix of the TOA and fused TDOA measurements in m2     0.0023 0.0001 0.0003 0.0001 Cov (T DOA) = Cov(T OA) = 0.0001 0.0007 0.0001 0.0006 This effect is due to the asymmetry of the TDOA, which is actually a fusion of TWR and TDOA. An alternative reference station would change the distri- bution. The compensation of this effect is described in a previous publication [?]. When combined with a filter, highly accurate results can be obtained. The position of the anchors affects the tag localization; better results are obtained with tags that are more centered with respect to the anchors [?]. Table 4. Precision: Standard Deviation in m TOA TDOA X-axis [m] 0.0175 0.0479 Y-axis [m] 0.0249 0.0256 Title Suppressed Due to Excessive Length 7 1.65 TDOA TOA 1.6 Y-Axis [m] 1.55 1.5 1.45 -0.1 -0.05 0 0.05 0.1 0.15 X-Axis [m] Fig. 6. X/Y positions of the TOA and TDOA fused with TOA position estimates The accuracy depends on the true position of the anchors and the offset estimate. This topic will be explained in detail in an upcoming publication. 5 Conclusion This paper introduces a method for TOA and TDOA fusion for Decawave ultra- wideband transceivers, which is able to use clock drift correction and the power correction curve. We showed how wireless clock calibration can be performed for the time difference of arrival using an additional station. The corrected time of arrival and time difference of arrival measurements were combined to increase the number of equations for the time difference of arrival position estimate. References 1. Douglass, D. and Monahan, K.: GPS instant navigation, A practical guide from basics to advanced techniques by kevin monahan. Fine Edge Productions, 1998. 2. Thompson, RB.: Global positioning system, The mathematics of GPS receivers, Mathematics magazine, 1998. 3. Resch, A., Pfeil R., Wegener M., and Stelzer A.: Review of the lpm local positioning measurement system, In 2012 International Conference on Localization and GNSS, pp. 1-5, June 2012. 4. Shen, X., Yang, S., He, J., and Huang, Z.: Improved localization algorithm based on rssi in low power bluetooth network, In 2016 2nd International Conference on Cloud Computing and Internet of Things (CCIOT), pp. 134-137, Oct 2016. 5. Zwirello, L., Schipper, T., Jalilvand, M., and Zwick, T.: Realization limits of impulse- based localization system for large-scale indoor applications, IEEE Transactions on Instrumentation and Measurement, pp. 39-51, Jan 2015. 8 Juri Sidorenko et al. 6. David, L.: A Second Course in Electronic Warfare, Artech House, Boston London, 2004. 7. Zhou, Y., Law, C. L., Guan, Y. L., and Chin, F.: Indoor elliptical localization based on asynchronous uwb range measurement. IEEE Transactions on Instrumentation and Measurement, pp.248-257, Jan 2011. 8. Dotlic, I., Connell, A., Ma, H., Clancy, J., and McLaughlin, M.: Angle of arrival estimation using decawave dw1000 integrated circuits. In 2017 14th Workshop on Positioning, Navigation and Communications (WPNC), pp. 1-6, Oct 2017. 9. Gerrits, J. F. M., Farserotu, J. R., and Long, J. R.: Multipath behavior of fmuwb signals, In 2007 IEEE International Conference on Ultra-Wideband, pp. 162-167, Sept 2007. 10. Saeed, R. A., Khatun, S., Ali, B. M., and M. A. Khazani.: Ultra-wideband (uwb) geolocation in nlos multipath fading environments, In 2005 13th IEEE International Conference on Networks Jointly held with the 2005 IEEE 7th Malaysia International Conf on Communic., volume 2, pp. 6, Nov 2005. 11. Jiménez, Ruiz, A. R. and Seco Granja, F.: Comparing ubisense, bespoon, and decawave uwb location systems: Indoor performance analysis. IEEE Transactions on Instrumentation and Measurement, pp.2106-2117, Aug 2017. 12. Haluza, M. and Vesely, J.: Analysis of signals from the decawave trek1000 wideband positioning system using akrs system, In 2017 International Conference on Military Technologies (ICMT), pp. 424-429, May 2017. 13. McElroy, C., Neirynck, D., and McLaughlin, M.: Comparison of wireless clock synchronization algorithms for indoor location systems. In 2014 IEEE International Conference on Communications Workshops (ICC), pp. 157-162, June 2014. 14. Djaja-Josko, V., and Kolakowski, J.: A new method for wireless synchronization and tdoa error reduction in uwb positioning system. In 2016 21st International Conference on Microwave, Radar and Wireless Communications (MIKON), pp. 1-4, May 2016. 15. Tiemann, J., Eckermann, F., and Wietfeld, C.: Atlas - an open-source tdoabased ultra-wideband localization system. In 2016 International Conference on Indoor Po- sitioning and Indoor Navigation (IPIN), pp. 1-6, Oct 2016. 16. Sidorenko, J., Schatz, V., Scherer-Negenborn, N., Arens, M., and Hugentobler, U.: Decawave uwb clock drift correction and powerself-calibration. Sensors Journal, July 2019. 17. Sidorenko, J., Scherer-Negenborn, N, Arens, M., Michaelsen, E.: Improved linear direct solution for asynchronous radio network localization (rnl). Institute of Navi- gation ION Pacific PNT Meeting, 2017. 18. Salman, N., Maheshwari, H. K., Kemp, A. H., and Ghogho, M.: Effects of anchor placement on mean-crb for localization. In 2011 The 10th IFIP Annual Mediter- ranean Ad Hoc Networking Workshop, pp. 115-118, June 2011.