KRATKI ZNANSTVENI PRISPEVKI B How Time-of-departure Knowledge relates to Time-of-arrival localization accuracy? Matija Rezan1, Fabio Ricciato1 1 Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, Večna pot 113, 1000 Ljubljana matija.nezan@fni.uni-lj.si Izvleček Razvitih in preizkušenih je bilo že mnogo sistemov za lokalizacijo, vendar večina študij analizira le zmogljivosti konkretnih sistemov, medtem ko jih malo preuči vplive osnovnih predpostavk sistema. V tem članku analiziramo točnost metod lokalizacije vira, ki temeljijo na meritvah časa prihoda s strani sodelujočih sider. Ogledamo si tri različne modele: enega z znanim in dva z neznanim časom odhoda signala. Naša analiza temelji na elipsoidih, ki predstavljajo Cramer-Raovo mejo za vsak model. Tako pridobimo vpogled v geometrijske lastnosti modelov. Analiza razkrije, da je vpliv poznavanja časa odhoda zelo velik zunaj konveksne ovojnice sider, znotraj pa skromen. Rezultati kažejo, da je mogoče določene lastnosti zasnove z gotovostjo zamenjati za večjo točnost, med tem ko drugih ni mogoče. Ključne besede: Cramer-Raova meja, lokalizacija, čas prihoda, čas odhoda. Abstract Many localization systems have been developed and tested. However, most works only analyze the performance of the concrete systems in question. Few examine the effects of the underlying system assumptions. In this paper, we analyze the accuracy of source localization methods based on time-of-arrival (ToA) measurements from a set of cooperating receivers (anchors). We examine three different system models, one with and two without the knowledge of the time-of-departure (ToD) of the signal. Our analysis is based on Cramer-Rao Bound (CRB) ellipsoids for each model. We use these to provide insight into the geometric properties of the models. The analysis reveals that the impact of ToD knowledge on the achievable accuracy is very large outside the convex hull of the anchors, but only modest inside. The presented results show that certain system design choices can be reliably traded for batter accuracy, while others cannot. Keywords: Cramer-Rao Bound (CRB), localization, time-of-Arrival, time-of-Departure. 1 INTRODUCTION AND MOTIVATIONS All time-based localization methods require the measurement of the Time-of-Arrival (ToA) of signals by one or more receiving nodes. The primary factor determining the localization precision is the measurement noise. Therefore, from an engineering point of view, ToA should be measured as precisely as possible using more or less advanced signal processing methods in the receiver hardware, firmware or software layer [Calvo-Palomino et al., 2018]. We can consider certain other features of the system to be optional. One such feature is node clock synchronization: if node clocks are left unsynchronized, localization can still be performed by estimating (and correcting for) the clock error terms during the ToA data processing and location estimation phases [Ricciato et al., 2018, Wu and Gu, 2017, Nagy et al., 2011]. Another prominent optional system feature is knowledge of the transmission time, hereafter called Time- of-Departure (ToD). Like with clock errors, if ToD is unknown we can treat it as a nuisance variable to be estimated jointly with the position variables. Time-of-Departure knowledge can translate into higher precision, but comes at the cost of additional engineering burden in terms of ToD control. On the other hand, systems with unknown ToD require the 2019 - številka 3 - letnik XXVII uporabna INFORMATIKA 115 Matija Rezar, Fabio Ricciato: How Time-of-departure Knowledge realtes to Time-of-arrival localization accuracy deployment of one additional anchor to ensure that the problem is identifiable. The choice between localization systems that rely on ToD knowledge, and those that do not, is therefore a matter of engineering trade-offs between costs and benefits. Most previous work on localization skips this engineering question and directly assumes a particular system model, either with or without ToD knowledge. In this paper we take a step back and study the impact of ToD knowledge on the final estimation accuracy. To do so, we consider different system models, both with and without ToD knowledge, and qualitatively assess their achievable precision. Our analysis is based on general properties of the time-based localization problem, not bound to a specific radio technology or particular scenario. We resort to theoretical results from estimation theory to produce concrete recommendations for the engineers designing localization systems. A key finding is that the additional precision gain brought by ToD knowledge is modest if the source node is located within the anchors' convex hull, indicating that there is a design trade-off between ToD knowledge and anchor topology. The rest of the document is organized as follows. Related work is summarized in Sec. 2. In Sec. 3 we define three different system models. The Cramer-Rao Bounds (CRB) and their relations are described in Sec. 4. Graphical interpretation and geometric considerations are presented in Sec. 5. Finally, we draw conclusions and implications for practical system engineering in Sec. 6. 2 RELATED WORK The use of CRB for the analysis of localization precision is well-established. Previous papers have derived the CRB for different system models, with ToD knowledge and without. Shen et al. [Shen et al., 2010, Shen and Win, 2010] provide a detailed treatise on the topic of known-ToD localization, including the notion of the Equivalent Fisher Information Matrix (EFIM), which is a method of comparing models with different numbers of parameters. In [Ricciato et al., 2018] the authors analyzed systems without ToD knowledge. They derived the CRB and used it as a reference to assess estimation performances in a sample scenario. Huang et al. [Huang et al., 2015] show that knowledge of noise characteristics affects the CRB. They come to the conclusion that heteroscedastic noise may in fact aid localization, provided that the hete-roscedasticity can be modeled accurately. Their work reinforces the idea that a properly conducted theoretical analysis of CRB can provide insight to steer the practical design of real-world systems. In this paper we use EFIM to analyze the effect of model assumptions on the result. Cramer-Rao bounds are a good approximation of the accuracy that can be achieved by Maximum Likelihood Estimators (MLE) in practice [Ricciato et al., 2018, Musicki et al., 2010]. It is also a good approximation for non-gaussian noise [Ricciato et al., 2018]. This gives practical interest to the analysis of the theoretical CRB. 3 SYSTEM MODELS Our scenario comprises two types of nodes: a transmitter in an unknown position (source) and several receivers in fixed known locations (anchors). For each incoming packet, every anchor measures the ToA, i.e., the reception timestamp. The anchors cooperate in the localization process and share the ToA measurements with a central unit in charge of the computation. We consider three different packet transmission patterns: (i) known transmission times (known ToD); (ii) periodic transmissions with unknown starting time; and (iii) unknown transmission times (unknown ToD). In all scenarios we account for packet loss, i.e., we do not require each packet to be received by all anchors. We assume that signal propagation occurs over li-ne-of-sight (LoS) paths between transmitter and receiver. We consider a three-dimensional Euclidean space, but for the sake of simplicity we assume that the vertical component of the source position is known. Therefore we have a planar problem (two unknown variables) embedded in a 3D Euclidean space1. This choice simplifies the analysis and the graphical presentation of the results without jeopardizing the key insights. In our models, the ToA measurement error variance is constant and does not depend on the distance between transmitter and receiver. The measurement errors are independent and identically distributed 1 Note that the full three-dimensional specification (as opposed to purely two-dimensional) is relevant to the measurment of angles, as seen in Figure 1. In two dimensions the two represented angles would be complementary, whereas in three dimensions the two angles are not directly related. 168 uporabna INFORMATIKA 2019 - številka 4 - letnik XXVII Matija Rezar, Fabio Ricciato: How Time-of-departure Knowledge realtes to Time-of-arrival localization accuracy with a Gaussian distribution. This assumption is coherent with empirical evidence from real-world ToA measurements, when received signals have a high Signal-to-Noise Ratio (SNR)[Calvo-Palomino et al., 2018]. Modeling equations for our models are: 1 rnm = Tm + c HP - &n\\ + £ ' meaning that the ToA rnm of packet m 1. e .M at anchor n I.e.N is the sum of transmission time Tm (ToD), the propagation time along the direct path from the source position p = (px, py) to the anchor position an, with propagation speed c, and the measurement error E, which has zero mean and constant (possibly unknown) variance. Depending on the transmission pattern we define three model variants: ■ Model-0 - All transmission times Tm are known, and only the position variables px, py need to be estimated. ■ Model-1 - The transmission times are perfectly periodic with known period T starting from an unknown time t1, i.e., they can be expressed as Tm= T1 + (m - 1) * T . ■ Model-2 - All transmission times t1, . . . , tm are unknown and present M nuisance variables in the model. 4 CRAMER-RAO BOUND The CRB represents a lower bound on the Mean Squared-Error (MSE) of any unbiased estimator [Kay, 1993]. For multivariate estimators, the CRB provides a lower bound on the estimation error covariance. The CRBs depend on the angles between the source-anchor vectors and the basis vectors, as shown in Figure 1. The effects can be split into two components. The first is "axial diversity", which describes how much offset anchors have on each axis, relative to the offset on the other axes. This means that the further from a given axis anchors are, the more accurate the estimate on that axis can be. Interestingly, the direction (positive or negative) of the offset does not matter. The second component is "angular diversity", i.e., how much variety there is in the angles between different anchors, as seen from the source. Similarly to axial diversity this translates to offsets. However, in this case the direction does matter: bigger variety of offsets, i.e., both positive and negative offsets, translates to more accurate estimations. Axial diversity affects both known and unknown ToD models, while angular diversity affects only the unknown ToD models. We can show that C(2) > C(1) > C(0), following Lo-ewner order [Horn and Johnson, 2012] (where CB is the CRB for model i), by proving that the differences between the EFIMs are positive semi-definite. We can do this by employing the Sylvester criterion and the Schur complement [Horn and Johnson, 2012]. This means that the errors of Model-0 can be on average smaller than those of Model-1, which can be, in turn, smaller than those of Model-2. 2019 - številka 4 - letnik XXVII upora uporabna INFORMATIKA 171 Matija Rezar, Fabio Ricciato: How Time-of-departure Knowledge realtes to Time-of-arrival localization accuracy 195 190 185 >> 180 175 170 165 s* ;/ y y y/ / y A \ s \ V // s vi S s 230 240 250 X 260 Model - Model-O -- Model-1 Model-2 270 (c) Location C (d) Anchor positions (squares) and source test locations (dots). Figure 2: Comparison of CRB confidence ellipses for moderate packet loss ploss = 0,25. Models 1 and 2 behave similarly to Model-0 inside the convex hull, but depart distinctly outside it 5 GRAPHICAL INTERPRETATION We start by considering a simple layout with four anchor nodes arranged as shown in Figure 2d. We assume a moderate level of packet loss probability equal to ploss = 0.25. For analysis, we consider the three different test locations labeled A, B and C in Figure 2d. The confidence ellipses that represent the CRBs as covariance matrices of a multivariate normal distribution are plotted in Figures 2a to 2c for the three model variants for all test locations. It is clear that the models are strictly ordered resulting in the inclusion of their respective confidence ellipses. The smallest confidence ellipses are obtained in test location A, well inside the convex hull of the anchors, while the ellipses get larger for all models in test location B (note the different scale of Figure 168 uporabna INFORMATIKA 2b). As soon as the source node moves outside the convex hull, the confidence ellipses for Model-1 and Model-2 stretch, and get dramatically larger, while the enlargement remains contained for Model-0. To better illustrate the change confidence ellipses for a regular grid of different locations are plotted in Figures 3a and 3b for Model-0 and Model-2, respectively. In Figure 3a we can see the behavior of CRB for Model-0. The CRB is the lowest and most circular in the middle, where the anchors have high axial offset, and worsens as the source moves away. After leaving the convex hull, the CRB stretches along the angular direction: when moving to the right (positive x direction), the ellipses enlarge vertically, because the anchors have less axial offset along the y axis than on the x axis. 2019 - številka 4 - letnik XXVII Matija Rezar, Fabio Ricciato: How Time-of-departure Knowledge realtes to Time-of-arrival localization accuracy (a) Model-0 CRB (known ToD). (b) Model-2 CRB (unknown ToD). Figure 3: CRB ellipses (magnified for readability). Line color proportional to CRB trace. The CRB is similar inside the convex hull, but differs wildly outside it. We can see the effect of angular diversity in Figure 3b. Inside the convex hull, the angles' contributions tend to cancel out, leading to CRB behavior similar to that of Model-0. Upon leaving the convex hull we start losing angular diversity. Moving in the positive x direction in Figure 3b, the angular diversity on the x axis drops very quickly, because all anchors are on the same side, relative to the source, resulting in low diversity and therefore loss of precision in that direction. On the y axis, however, the diversity fades much slower. The effect is that the direction (or angle in polar coordinates) of the source can be estimated much better than the distance (range). For an intuitive interpretation, consider that from the perspective of a single receiver, we cannot discriminate between (i) the source being further away and (ii) the packet transmission occurring at an earlier time. In other words, there is an ambiguity between transmission time (ToD) and distance, resulting in the elongation of the ellipse in the radial direction, as can be seen in Figure 3b. In contrast, Model-0 (Figure 3a) does not suffer from that problem. 6 CONCLUSIONS Most studies of localization systems focus on one system and do not examine the effects of basic system assumptions on the achievable accuracy. We showed how one property, transmission time knowledge, affects this. From the analysis presented in this work we can draw recommendations for real-world system engineering. First, we have found that ToD knowledge only brings a large gain in localization accuracy outside the anchors' convex hull. Therefore, we may waive the transmission time measurement, if we can ensure that the area of interest remains inside the convex hull. Second, when the source lies outside the convex hull and ToD is unknown, we can still achieve a good estimation of the source azimuth, but not of the range. However, this might suffice whenever the range information can be obtained by other (prior) data or is not critical to the application, reducing both cost and complexity. REFERENCES [1] [Calvo-Palomino et al., 2018] Calvo-Palomino, R. et al. (2018). Nanosecond-Precision Time-of-Arrival Esti- mation for Aircraft Signals with Low-Cost SDR Receivers. In 17th ACM/ IEEE IPSN, Porto. [2] [Horn and Johnson, 2012] Horn, R. and Johnson, C. (2012). Matrix analysis. Cambridge Press, 2nd edition. [Huang et al., 2015] Huang, B. et al. (2015). TDOA-Based Source Localization With Distance-Dependent [3] Noises. IEEE Trans. on Wireless Comm., 14(1). [4] [Kay, 1993] Kay, S. M. (1993). Fundamentals of statistical signal processing. Prentice Hall signal processing series. Prentice-Hall. [5] [Musicki et al., 2010] Musicki, D. et al. (2010). Mobile Emitter Geolocation and Tracking Using TDOA and FDOA Measurements. IEEE Trans. on Signal Processing, 58(3). [6] [Nagy et al., 2011] Nagy, A. et al. (2011). Time-based localisation in unsynchronized wireless LAN for industrial automation 2019 - številka 4 - letnik XXVII uporabna INFORMATIKA 171 Matija Rezar, Fabio Ricciato: How Time-of-departure Knowledge realtes to Time-of-arrival localization accuracy systems. In IEEE ETFA. [7] [Ricciato et al., 2018] Ricciato, F. et al. (2018). Position and Velocity Estimation of a Non-cooperative Source From Asynchronous Packet Arrival Time Measurements. IEEE Trans. on Mobile Computing, 17(9). [8] [Shen et al., 2010] Shen, Y. et al. (2010). Fundamental Limits of Wideband Localization— Part II: Coopera- tive Networks. IEEE Trans. on Information Theory, 56(10). [9] [Shen and Win, 2010] Shen, Y. and Win, M. Z. (2010). Fundamental Limits of Wideband Localization— Part I: A General Framework. IEEE Trans. on Information Theory, 56(10). [10] [Wu and Gu, 2017] Wu, X. and Gu, Z. (2017). A joint time synchronization and localization method without known clock parameters. Pervasive and Mobile Computing, 37. ■ Matija Rezar studied at the Faculty of Computer and Information Science at University of Ljubljana, where he received a Master's degree in 2016 and enrolled into the PhD programme in 2017. He is currently also employed there as a researcher in the area of localization and Bayesian statistics. ■ Fabio Ricciato graduated in Electrical Engineering (1999) and received a PhD in Information and Commu- nication Technologies (2003) from University La Sapienza, Italy. Between 2004 and 2017 he worked in telecommunications research across different institutions. He worked as research manager at the Telecom- munications Research Center Vienna and at the Austrian Institute of Technology, leading medium size research units of up to 45 researchers. He has served as assistant professor in Italy (Faculty of Engineering at University of Salento) and as associate professor in Slovenia (Faculty of Computer Science at University of Ljubljana) teaching various subjects in the telecommunications field, from networking to signal processing, including traffic monitoring and radio-based localisation. He has recently joined Eurostat, the statistical office of the European Union. His current interests revolve around applications of statistics, privacy-preserving computation methods and analysis of mobile phone network data. 168 uporabna INFORMATIKA 2019 - številka 4 - letnik XXVII