Signal Processing Algorithm for Precise Railway Navigation by FMCW Radio Frequency Identification Mikhail V. Ronkin1 , Alexey A. Kalmykov1 , Viktor S. Nagovicin2 , and Alexander P. Buinosov2 1 Ural Federal University, Yekaterinburg, Russia 2 Ural State University of Railway Transport, Yekaterinburg, Russian Federation MVRonkin@gmail.com Abstract. The paper deals with the problem of railway navigation accu- racy increasing by using active radio frequency identification and FMCW signals. The new algorithm for signal processing in this case is presented. The proposed algorithm uses the phase based time delay difference esti- mation method, which was proposed by authors in early works. In addi- tion, an algorithm for the elimination of corresponding phase ambiguities and Doppler shifts is proposed for the task solution. The main advan- tages of the proposed approach consists in increasing the information content of the measurement and i.e. increasing accuracy of navigation. The results obtained by the numerical simulation shows the effectiveness of the presented solution for the considered task. Keywords: signal processing, railway navigation, RFID navigation, ra- dio frequency identification, FMCW signals, active radio frequency iden- tification 1 Introduction The navigation problem of the railway transport is one of the most actual nav- igation tasks up to date. Particularly, this task is important for the high-speed railroads and in the case of determination of the exact time when the train arrives to certain points on the railroad track [1]. For instance, the navigation problem appear in the task of determination the braking distance to railway stations. In this case, it is necessary to estimate accurately the distance and speed of train. Frequently, the GNSS methods (such as GPS or GLANAS) are applied for the rail navigation [1]. However, such methods give large error in coordinate determi- nation, particularly, in the case of high-speed rail transport. The other methods of navigation that proposed in the literature include navigation by identification of railroad steel part, optical methods or using the georadar [2]. One of the most perspective method of navigation is based on the radio fre- quency identification of the rail transport (RFID) by RFID tag [3]. The principle of it work consists in the emitting of radio waves by train and it receiving and 53 re-emitting on changed frequency by RFID tag which is placed in the certain points on the rail road. The distance to the tag is determined by means of the time delay estimation of the signal. Additionally to this Doppler Effect can es- timate the train velocity. The main advantage the RFID navigation method is it high noise immunity even in the case of complex interference environment as could has place to be in the rail stations. As it was mention above, the task of determination the train position by RFID method can be reduced to the problem of high accuracy estimation of time delay between the emitted and received signal. Within this, the received signal can be written as amplitude-modulated superposition of valuable signal and signal-like interferences on the white Gaussian noise background. The pre- liminary analysis shows that the condition of the task corresponds to the short- range radar area. One of most perspective methods to the described problem solution consists in using linear frequency modulated continuous wave (FMCW) signal and the heterodyne scheme of it processing [4]. The principle of the heterodyne scheme work consists in simultaneously emit- ting and receiving quasi FMCW signal, which processed by the heterodyne. The obtained low frequency signal is so called beat signal, which contains informa- tion of the delay in its frequency and initial phase. As a rule, only a frequency is measured. There are two peculiarities of using the method in RFID systems. The first one consists in using two generators with different initial frequency one for the emitting signal and one for receiving. The second one is the necessary taking in to account the Doppler frequency shift effect [4]. The main advantages the FMCW approach in the considered task are decreased requirements to the power of navigation systems and possibility to use both the frequency and phase for the delay measuring delay that increase accuracy in comparison with traditionally used impulse based systems [4, 5]. In the previous works, the we proposed the method for time delay difference estimation, where the joint information of the initial phase and frequency of the beat signal was used [5, 6]. The designed method is based on the approxima- tion of the signal phase to time relation by the weighted minimum least square method [5, 6, 7]. The proposed estimator provides higher information content of measurement in comparison to the separate measurements of initial phase and frequency [5, 6]. In [7], it was sown that such estimators can be performed by algorithm with computational complexity ∼ N , where N is the sample size of beat signal [7]. The designed estimator was researched to be used in time delay difference estimation in radar level measurement [8] and in ultrasonic clamp-on flow meters [6]. The present work is devoted to investigation the features of using the proposed estimator in the task of the railway navigation by FMCW radio frequency identification. 2 Problem formulation The block scheme of railway navigation by the FMCW radio frequency identifi- cation system is shown on the Fig.1. The principle of its work consists in emitting 54 a FMCW signal S1 with initial frequency f1 by the corresponding generator 1 which is placed on a train, its receiving by RFID tag 2 which is placed on the rail track. RFID tag re-emit the received wave S2 on a changed frequency f2 . The signal received by a train has the delay τ , which corresponds to the distance between the tag and train. The received FMCW signal is processed by hetero- dyne scheme 3, which contains FMCW generator with frequency f2. The CPU 4 performs the beat signal processing and control of scheme work. Fig. 1. Block-scheme of FMCW radio frequency identification system. The model of the beat signal, which obtained by the proposed scheme (see Fig.1), can be written as amplitude modulated superposition of the valuable and signal-like interference signals on the white Gaussian noise background. The nature of the mentioned interference signals is connected with reflecting of the re-emitted wave, for instance, from the train parts or other parasitic objects. Due to this the main part of such signals can be filtered, and its amplitude would be smaller than for main tone, and hence, signal to interference (SIR) ratio is supposed to be high enough. In additional, it can be supposed that signal to noise (SNR) ratio is sufficiently high, when tag is near train. The described model of beat signal of FMCW radio frequency identification system can be written as follows: s(t) = A(ωAM ) exp [j(ωb (τ )t + θb (τ ))] + z(t) + spar , (1) A(ωAM ) > |spar |, A(ωAM ) > |z(t)|, where s(t) is the beat signal; A(ωAM ) is the modulated amplitude; ωb (τ ) and θb (τ ) are the beat frequency and initial phase; τ is the measured delay; spar is the interference signal influence; z(t) is the white Gaussian noises. For the FMCW signal ωb (τ ) and θb (τ ) can be given as: ωb (τ ) = 2πτ ∆f /Tm , θb (τ ) ∼ = 2πτ f0 , (2) where f0 is the initial frequency; ∆f is the frequency deviation; Tm is the period of modulation. 55 The expression for θb (τ ) in (2) is the approximation of initial phase expression for the case when 2πf0  ωb (τ ) and initial phase fluctuations are negligible. The last assumption is due to the straight wave propagation between the emitter and receiver. As it was shown in papers [5, 6] the time delay difference of two signals like (1) can be estimated by the following expression PN −1 n=0 Wτ (n)|s(n)|args(n) ∆τ = PN −1 2 , (3) n=0 Wτ (n)|s(n)| where s(n) = s1 (n)s∗2 (n), s1 (n) and s2 (n) are the signals which delay difference is estimated; ∆τ the estimated delay difference; N the sample size; Wτ (n) is weight coefficient: Wτ (n) = 2π[∆f n/N + f0 ]. (4) Equation (3) corresponds to the Gauss-Markov theorem for ∆τ as phase ar- gument. Thus, proposed estimator provides asymptotically effective and asymp- totically unbiased estimation, which variance attains the Cramer-Rao low bound (CRLBτ ) of delays as parameters of signals (because ∆τ corresponds to the full signal phase). The described CRLBτ value in several times smaller than for es- timators of delay by frequency and initial phase parameters [5]. Also in paper [8] it was shown that the bias of time delay difference estimation by (3) in the case of interferences in several times smaller than for corresponded estimators of ∆τ by beat frequency and initial phase as parameters. There are two restrictions for applying the described estimator (3) in the considered task of rail road navigation. The first one consists in the Doppler Effect. The second one consists in the fact that the estimator has limited range of unambiguously values ∆τmax < 1/2f0 , (5) where ∆τmax is maximum value of unambiguously range. However as it will be shown below, both restrictions can be overcome. 3 Doppler effect elimination The Doppler frequency shift of the beat signal, which is connected with reflection from moving object due to the shift of initial frequency of FMCW signal can be expressed as fd = 2v cos α/λ0 , (6) where fd is the Doppler frequency shift, α is the angle between direction of wave patch and direction of velocity of object; v is the object velocity, λ0 is the wave length As a rule in FMCW radars the Doppler shift of beat frequency compensated by using so called symmetry FMCW law, which contains two parts with growing 56 frequency and with decreasing one. In this case the beat frequency for the first part is ∆f τ /Tm − fd and for the decreasing part is ∆f τ /Tm + fd . Thus in average term fd will be eliminated. The illustrations of symmetric FMCW law of frequency to time relation for emitted signal, for delayed signal without Doppler shift and with Doppler shift are shown on Fig.2. Fig. 2. Illustrations of symmetric FMCW law of frequency to time relation for emitted signal (1), for delayed signal without Doppler shift (2) and with Doppler shift (3) In the case of symmetric FMCW law the main tone of beat signal can be written as follow: s± (t) = |s|exp[2πj((∆f τ /Tm ± fd )n/fs + (f0 ± fd )τ )] = (7) = |s|exp[jWτ (n)τ ] exp [±j2πfd (n/fs + τ )], where sign ± depends on the part of FMCW low (increasing or decreasing part); s± (n) is the beat signal for one part of FMCW law; fs is the sampling frequency of beat signal. Expressions (7) can be combined in the following two samples, one of which has not contained Doppler shift and the second one is the function of Doppler frequency: sτ (n) = s+ s∗− = exp [i2Wτ (n)τ ], (8) sd (n) = s+ s− = exp [i2Wd (n)fd ], where sτ is the function of delay (without Doppler shift); sd is the function of Doppler frequency; Wd (n) is the weight coefficient Wd (n) = 2π(n/fs + τ ) ∼ = 2πn/fs . (9) The values of sτ delay and sd frequency of samples (8) can be estimated by proposed method (3) as follows: PN −1 n=0 Wτ (n)|sτ (n)|argsτ (n) τ= PN −1 , (10) 2 n=0 Wτ2 (n)|sτ (n)| 57 PN −1 n=0 Wd (n)|sd (n)|args(n) fd = PN −1 , 2 n=0 Wd2 (n)|sd (n)| where arg is the operation of taking the complex value argument. With regard to the expression (10) the following should be noted. The area of unambiguous values of τ estimations by sτ sample has limit value 1/4f0 . The estimator of fd by sd sample has area of unambiguous value up to the 1/2τ , however in practice this value cannot be reached. Analysis of Wd (n) expression shown that estimator of fd corresponds to the proposed in [7] estimator of beat signal frequency. In addition, it should be noted that velocity of train can be estimated as by fd value by measuring ∆τ between two samples sτ . However, a detailed study of this issue is beyond the scope of this article. 4 The phase based delay estimation algorithm As it was mentioned above one of the main obstacles to apply estimator (3) for absolute value time delay measurements consists in the condition (5), which restricts the range of unambiguously values. However, the condition (5) can be satisfied if delay is measured relatively to the delayed reference signal. The difference of the reference signal delay with the measured signal delay should be less than it require by equation (5). Such reference signal can be set with coarsely measured value of delay. The reference signal delay can be calculated as τint = f ix[τcoarse /τmax ]τmax , (11) where τint is the delay of reference signal; f ix[] is the integer part; τmax is the value of (5); τcoarse is the coarse measured value. The proposed method of reference signal creation with delay (8) provides unambiguous measurement of delay τ of signal (8) by estimator (3) if τint − τ < 1/4f0 . As an algorithm for the coarse delay estimation we suggest to use estimator of beat frequency of FMCW signals which was proposed by us in paper [7]: PN −1 Pn ∗ fs n=1 n|R(n)| j=1 argR(j)R (j − 1) fcoarse = PN −1 2 , (12) 2π n=1 n |R(n)| where R(n) is the autocorrelation function of sτ ; fcoarse is the coarse beat fre- quency, which corresponds to the τcoarse value. The block scheme of the proposed algorithm absolute time delay estimation by method (3) is shown on the Fig. 3. The analysis of algorithm Fig. 3 shows that if delay value τcoarse is calculated by (12) than computational complexity of the algorithm has following order: O(τ ) = O(R) + O(τcoarse ) + O(∆τ ) ≈ 2(M + 2 log2 N + 2)N (13) where N is the sample size; M is the number of non-linear operations as arg s(n) = arctan [Im(s(n)/Re(s(n)]; O(τcoarse ) is the order of computational complexity 58 Fig. 3. The block-scheme of the proposed algorithm for absolute time delay estimation values by estimator (3) of τcoarse obtaining; O(∆τ ) is the order of computational complexity of ∆τ ob- taining; O(R) is the computational complexity of calculation autocorrelation function. In the considered conditions O(τcoarse ) is the order of computational com- plexity of algorithm (12) ( O(τcoarse ) ≈ M N , see [7]); O(∆τ ) is the order of computational complexity of expression (3) (O(∆τ ) ≈ M N ); O(R) is the order of computational complexity of autocorrelation sample calculation. The auto- correlation sample obtaining can be performed as R(n) = f f t−1 [f f t(s, 2N )], where F F T and F F T −1 are the direct and inverse fast Fourier transforms by 2N numbers; R(n) is the autocorrelation function with sample size N (O(R) = 4N log2 2N = 4(N + 1) log2 N ). For expression (12) it should be noted that the modern computational sys- tems provide hardware division. The arctan value can be calculated by the Remez algorithm as Im[s(n)] arg s(n) = arctan = (14) Re[s(n)] = ((−0.0464s2 (n) + 0.159)s2 (n) − 0.327)s3 (n) + s(n) 59 . The computational complexity of (14) has order M = O(7). For instance, the computational complexity for 512 samples has order O(N = 512) ∼ = 1.5 · 215 . The algorithm Fig 3, allows one to estimate an absolute values of delay as delay difference without restriction (5). However, in the case of absolute value estimation the assumption about absent of phase fluctuation should be adopted or phase shift should be taken into account. The assumption made above is valid in the considered task due to the straight wave propagation between emitter of RFID and receiver on train. In addition, if the coarse value is known a-priori or predicted by velocity value and distance value measured before, the algorithm in Fig.3 can be implemented on-line. 5 The interference influence estimation Expression (3) in the presence of one interference signal (see (1)) with delay τ2 and amplitude A2 gives biased estimation in the case of finite parameters values. Following to the solutions given in [5, 7] the bias can be expressed as PN −1 A2 n=0 Wτ (n)sinWτ τ21 A2 cos 2πf0 τ21 δτ ∼ = PN −1 2 ≈ 2 τ [f + ∆f /2]2 . (15) A1 n=0 Wτ (n) A 1 4π 21 0 where δτ is the bias value; A1 , A2 are the amplitudes of valuable and interference signals; τ21 is the delay difference between delays of valuable and interference signals. The relation of bias value (15) to bias value of estimator (12) (which was given in [7]) can be written as follow: δτ ω ∼ [f0 + ∆f /2]2 cos 2π∆f τ21 =3 , (16) δτ ∆f 2 cos 2πf0 τ21 where δτ ω is the bias value of delay estimated by (12). Figure 4 shows the relations of bias values of delay estimation the τ21 , nor- malized on the τ1 , the relations, which are given for bias values, obtained by algorithm Fig. 3 (prop.τ ) and for algorithm (12) (prop.f ). The delay of valu- able signal set as 1, amplitudes relation A2 /A1 = 0.1, initial frequency set 100, deviation 50. All values are given in relative units without loss of investigation generality. In additional, on Fig.5 shows the relations of biases for the analyzed algorithms (δτ ω /δτ ) with the τ21 /τ1 values, which obtained by numerical exper- iment and calculated by (16). The results in Figs. 4 and 5 prove the conclusions made above about advan- tages of proposed estimator (3). The deviation of calculated value behavior of δτ ω /δτ to numerically obtained one can be explained by the inaccuracy of the introduced assumptions. However, expression (16) allows one to approximately (i.e. in average) determine the main regularities. For instance, in the case of small τ21 value the δτ ω /δτ relation reach 20 times in the simulated conditions. In additional, it should be noted, that the variance of proposed estimator (3) 60 Fig. 4. Relations of bias values δτ , δτ ω % of delay estimation to τ21 values, normalized on τ1 , the relations given for bias values, obtained by algorithm on Fig. 3 (prop.τ ) and for algorithm (12) (prop.f ). lower than for frequency based delay estimator (9) in several times as it was shown in [5]. The relation has follow expression: [f0 + ∆f /2]2 CRLBτ ≈ 12 CRLBf , (17) ∆f 2 where CRLBτ and CRLBf are the CRLB values of delay estimation variance by τ or f as parameters respectively. For instance in the case when f0 = 2∆f CRLBτ = 75CRLBf . 6 Conclusion The carried analysis of the precise railway navigation by the radio frequency identification allows one to make follow conclusions. It was proved the advan- tages of using FMCW signals and heterodyne scheme in the navigation systems. The designed algorithm of time delay estimation provides accuracy (bias and variance) in several times smaller than for traditionally used frequency based delay estimators. The algorithm is based on the time delay difference estimation method of beat signals, which consists in the approximation of full phase to time relation. The method was proposed by us in the previous works. The mentioned above advantages of the proposed approach can be explained by increased infor- mation contains in estimation of beat signal frequency and initial phase jointly as function of delay. For instance, in the considered example the bias of measured delay smaller by 20 times and the variance smaller by 75 times in comparison with frequency based estimator. For the presented algorithm the method for Doppler shift elimination is proposed. In additional, the Doppler frequency can be estimated separately. The computational complexity of the proposed algo- rithm allows one to implement it on the contemporary microcontroller devices. 61 Fig. 5. Relations of biases for analyzed algorithms(δτ ω /δτ ) to the τ21 /τ1 values ob- tained by numerical experiment (δτ ω /δτ )num and calculated by (16) (δτ ω /δτ )teor References 1. Presti L.L. Sabina S.: GNSS for Rail Transportation: Challenges and Opportuni- ties. Springer (2018) 2. Kim K., Seol S., Kong S.H.: High-speed Train Navigation System based on Multi- sensor Data Fusion and Map Matching Algorithm. International Journal of Control, Automation, and Systems, Vol. 13, No. 3, 503–512 (2015) 3. Bank J., Pachano M., Thompson L, Hanny D.: RFID applied. Willey (2007) 4. Atayants B.A., Davydochkin V.M., Ezerskiy V.V., et al.: Precision systems of FMCW short-range radar for industrial applications. ARTECH HOUSE USA (2014) 5. Ronkin M.V., Kalmykov A.A.: Investigation of the time delay difference estima- tor for FMCW signals. Proceedings of the 2nd International Workshop on Radio Electronics & Information Technologies (REIT 2 2017), 90–99 (2017), http://ceur- ws.org/Vol-200 6. Ronkin M.V., Kalmykov A.A.: A FMCW - Interferometry approach for ultrasonic flow meters. 2018 Ural Symposium on Biomedical Engineering, Radioelectronics and Information Technology (USBEREIT), 237-240 (2018) 7. Ronkin M.V., Kalmykov A.A.: Phase based frequency estimator for short range FMCW radar systems. 2018 Ural Symposium on Biomedical Engineering, Radio- electronics and Information Technology (USBEREIT), 367–370 (2018) 8. Ronkin M.V., Kalmykov A.A.: On precision measurements of small distance changes in FMCW radar level gauges. AMITA (in publish), (2018)