Cooperative Inter-vehicle Distance (IVD) estimation algorithms such as Absolute Position Diferencing (APD), Single-Diferencing (SD), and Double-Diferencing (DD) are promising and cost-efective solutions thanks to Global Navigation Satellite System (GNSS) observables. These algorithms directly utilize pseudorange measurements, i.e., the estimated distance between the antennas of satellites orbiting the Earth and the GNSS receiver installed on the vehicle. However, an accurate IVD estimate using these techniques is dependent on exact satellite coordinates, as any GNSS pseudorange requires precise satellite positions. To compute satellite positions, the satellite's distributed navigation message or interpolation methods can be employed. This paper examines the performance of the Lagrange interpolation approach for estimating satellite locations epoch-by-epoch in a real-world experiment in the IVD estimation problem. The experimental results demonstrate that the Lagrange interpolation method performs efectively with sub-centimeter accuracy in the IVD estimation problem. Furthermore, the results indicate that even in a short study duration of 15 minutes, using outdated fixed-satellite positions influences IVD estimation accuracy and causes increased uncertainty.
Autonomous Vehicles (AVs) play a pivotal role in future mobility. It promises several advantages,
including simplified driving, reduced trafic congestion and accidents, increased safety, and
improved energy eficiency of the transportation system [
The global navigation satellite system (GNSS), which estimates the vehicle position from
the pseudorange (an estimate of the distance between a satellite and a GNSS receiver installed
on the vehicle) measurements from several satellites, is the most popular method for vehicle
localization [
Any pseudorange in GNSS requires the computation of the satellite location, and the methodologies for doing so are well-known in the literature [13]. We may use Kepler’s law to determine satellite locations utilizing distributed navigation messages from the satellite, such as RINEX (Receiver Independent Exchange Format) or RTCM (Radio Technical Commission for Maritime Services) [13,14]. To this end, the receiver observation data (e.g., RTCM) should be converted to RINEX format for post-processing and RTKLIB, an open-source program package for GNSS positioning, can be used [15]. Interestingly, using archival data from the International GNSS Service (IGS) [16] is an easy way to use satellite locations in post-processing. However, since IGS data is often provided in 15-minute intervals and we do not have access to satellite positions epoch-by-epoch, several interpolation algorithms have been proposed including Lagrange interpolation [17], Chebyshev polynomial fitting [18], Newton’s divided diference interpolation polynomial [19], and Cubic spline interpolation [19].
According to a comparison study [20] of diferent interpolation techniques for estimating satellite locations, Lagrange interpolation performed well with higher precision. Additionally, it can be used to compute satellite coordinates with only two known satellite positions. The literature [21–23] earlier proposed the application of the Lagrange interpolation algorithm in GNSS orbit interpolation and gave performance evaluations. However, this is based on mathematical and theoretical studies rather than a real-world assessment. The motivation for this investigation stems from the need to evaluate the performance of the Lagrange interpolation approach in a real-world application. In this study, we examine the performance of Lagrange interpolation in cooperative IVD estimation techniques using real-world measurements.
The remainder of this paper is structured as follows. A description of the mathematical
formulation of the GNSS pseudorange measurements and cooperative IVD estimation algorithms
is provided in Section 2. Section 3 is concerned with the methodology used for this study.
A discussion of the estimated IVD based on fixed satellite coordinates and epoch-by-epoch
satellite locations obtained via Lagrange interpolation is presented in Section 4. Finally, Section
2.1. GNSS pseudorange measurement model
The GNSS observables (raw code pseudorange) denoted by , are defined as the estimated
distance between the GNSS receiver installed on vehicle ∈ {1, 2, 3, .., } and a satellite
∈ {1, 2, 3, .., } at any time-step , which are modeled as follows [
5, summarizes the work.
(1) (2) The GNSS receiver installed on each vehicle is able to compute an estimate of its absolute position vector in ECEF coordinates after acquiring and tracking the GNSS signal of at least four satellites. The absolute position diferencing (APD) method calculates the estimated distance between two vehicles at any time-step denoted by ^ () = |→|− () − ()||, i.e. →− ^ () = √︁
( − )2 + ( − )2 + ( − )2 where →− () = [ (), (), ()] and →− () = [ (), (), ()] are the estimated position vectors of vehicle and vehicle obtained at time-step from the GNSS in ECEF coordinates, respectively.
Fig.1 depicts the single diferencing used for the IVD. The SD method estimates the IVD by
subtracting the pseudorange measurements of two vehicles from the same satellite. This
approach can eliminate both the clock imperfect synchronization between the vehicles as well
as the atmospheric delay error. Given that the satellite is suficiently far from vehicles, the
pseudorange measurements from each vehicle toward the satellite are considered to be parallel
(see Fig.1) [
() →−()− →−− () is the Line-Of-Sight (LOS) unit vector from vehicle to satellite wher→e− = →−
‖()− →−− ()‖ , →− () indicates the vehicle distance vector→,−() represents the position vector of the satellite and →− () defines the position vector of the reference vehicle at time-step (see Fig.1 for reference). By considering common visible satellites for the two vehicles and using (3), we can build the following measurement matrix: ⎡Δ 1 ()⎤
⎡ [1]
⎢⎢⎢⎢⎣Δ 2... ()⎥⎥⎥⎥⎦ ≈ ⎢⎢⎢⎣[[2...]]
Δ ()
1⎤
1⎥ [︃→− () ]︃
. ⎥
.. ⎥⎦ Δ ()
1
(4)
(5)
yielding the SD estimates [
In the SD-based algorithm of (5), user clock ofsets and common biases among those measurements are still present. To eliminate these uncertainties and also any other common biases, we can utilize a new GNSS measurement and then compute the diference between the SD estimates obtained from two distinct satellites, say and . This is referred to as the doublediferencing (DD) algorithm and is demonstrated in Fig.2. The DD-based approach assumes that both vehicles can track satellites and at the same time. Hence, we first apply an SD-based algorithm to each vehicle toward the satellites and , denoted by Δ () ∇Δ () = Δ () − Δ () = Δ () + Δ () () = Δ () − where Δ Δ () and Δ () = Δ () − Δ ().
() using the same trigonometric idea of SD, that is illustrated
We can then estimate Δ
in Fig.2 [
Δ () =→[− − →− →]− ()
wher→e− an→d− are computed as in (4). Using (6) is then possible to calculate the distance
and the relative positions of two vehicles. Indeed, using the satellite as a reference, the
solution to the DD-based algorithm according to Fig.2 is given by the matrix form [
∇Δ () is obtained as [11]: and Δ (), respectively, which are obtained from (3). Then, each double diference of such quantities defined by (6) (7) (8) (9) ⎡ ∇Δ 1 () ⎤ ∇Δ ()
⎡ [1 − ] ⎤ ⎢⎢⎣⎢⎢ ∇Δ ...2 () ⎥⎥⎥⎦⎥ ≈ ⎢⎢⎣⎢[[2 − − ... ]] ⎥⎥→− () ⎥ ⎦ Notice that the IVD vecto→r− () is projected in the direction of the diference satellite unitary vector→s− =→− − →− for each DD measurement indicated by ∇Δ (). Assuming four satellites, say , , , and , and considering as the reference satellite, the following system of linear equations derived from (8) can be obtained [11]: ⎡∇Δ ⎤
∇Δ ⎢⎣∇Δ ⎦⎥ = ⎣
⎡ ⎤ ⎡⎤ ⎦ ⎣⎦ = →− ()
→−() − →− () →−() − →− () →− = →||−() − →− ()|| − →||−() − →− ()|| ⎡ ⎤
⎡ ⎤ ⎥ − ⎣ ⎦ = ⎢⎣ ⎦ where→− and→−, , ∈ {, , , } are the satellite position vectors and →− is position vector of the vehicle , all evaluated at the time-step . Notice that 4 is the minimum number of satellites needed to have a solution of the DD-based algorithm, i.e., (known as the geometry matrix) should be non-singular. Usually, if more than 4 satellites are available, a more precise and efective Least Squares solution is adopted.
To evaluate the performance of Lagrange interpolation in a cooperative IVD estimation problem, we used a real-world experiment scenario in which two static outdoor autonomous vehicles (1 and 2) with LOS views toward GNSS satellites are located in the ECEF coordinates, and collected pseudorange measurements from diferent satellites. Fig.3 shows the 15-minute study interval. As shown in this figure, we picked two available known satellite locations from the IGS data on April 26, 2022, at 12:45 and 13:00 UTC. Then, we employed Lagrange interpolation to compute epoch-by-epoch satellite locations for the whole study interval. To this end, we consider ∈ {0, 1, 2, ..., } to be the values of the satellite locations, i.e., = [, , ], in time-step at ∈ {0, 1, 2, ..., }. The first and final known satellite positions are then used as inputs for the Lagrange approach to calculate the approximate value of , denoted by () at any time of as follows [17]: () = 00 + 11 + 22 + ... + = ∑︁ =0 (10)
( − 0)( − 1)...( − − 1)( − +1)...( − ) ( − 0)( − 1)...( − − 1)( − +1)...( − ) Now, by substituting in Eq.10 with {0, 1, 2,..., }, we obtain:
(0) = 0, (1) = 1, ...., () =
According to [17], when dealing with Lagrange interpolation (polynomial fitting) for computing satellite coordinates, we typically have an error (Runge’s phenomenon) in the beginning and ending points of the interpolation. Hence, as proposed in [17], we considered a validity interval for our satellite positioning by ignoring the starting and ending points, i.e., 10% on the data set.
To quantify the performance of the IVD estimation methods in this study, we compute three statistical criteria, including the root mean squared error (RMSE), average distance error (Δ), and average relative error (), which are defined as follows: ⎯ where ^ () indicates the average estimated IVD at time-step by SD- and DD-based algorithms, and represents the number of total epochs during the interval period, which is 250. We assume here that the two autonomous vehicles equipped with the GNSS receivers additionally have a Real-time kinematic (RTK) system that calculates the distance between itself and the broadcasting satellite. Thus, utilizing the RTK data, the average estimated IVD by the APD approach given by Eq.2 is assumed to be the actual ground truth (real distance) between the two vehicles and at time-step and indicated by () which is 3.354 (m) during the study interval. 3.3. Optimal Geometric Satellite Selection Algorithm Employing multi-GNSS systems can enhance positioning accuracy, and using more satellites may gives higher precision in the IVD estimation [12]. However, for the sake of simplicity in analyzing Lagrange interpolation in satellite positioning, we are examining a group of four satellites from the available satellites. To this end, in this study, we use the Maximum Volume Algorithm (MVA) to pick the optimum geometric group of four satellites comprising GPS, GLONASS, Galileo, and BeiDou to use in the SD- and DD-based IVD estimation techniques. The MVA is a four-step heuristic technique based on tetrahedron geometry that consists of the stages listed below [24]: • Step.1: Select the visible satellite 1 with the largest elevation angle relative to the position of the receiver (in our case, ).
of: cos = − 31 as detailed in [24]. • Step.2: Choose the visible satellite 2 having the elevation angle to 1, i.e., 12 , close to 109.47∘ . Notice that this elevation angle is obtained from a simple geometric consideration • Step.3: Pick the visible satellite 3 that maximizes the volume of the tetrahedron Δ = ∑︀=1 | () − ()|
^ = | () − ()|
^ () (14) (15) (16) (17) where and 4.
6 = 1 − 3 [︂ √︀2(1 − 2)(1 + 3)(1 − 23 − 23) + |23| ︂] 2 2 = cos 12 , 2 = sin 12 , 3 = cos 13 , 3 = cos 23 − 23 , 3 = ± √︁ 1 − 23 − 2.
3 Notice that the tetrahedron is formed by 1, 2, 3.
the volume of the tetrahedron • Step.4: Select the satellite 4 from the remaining visible satellites so that it maximizes 1 6 =
() where is the matrix that contains the line-of-sight vectors corresponding to 1, 2, 3,
Best
Category G5-G16-G18-G31 R9-R15-R18-R19 E33-E31-E24-E26 C35-C45-C13-C24
G18-G5-R9-R15 G18-G5-E24-E12 C35-G5-C24-C45 R18-R15-E24-E26 C35-R15-C13-C24 As shown in Fig.4, there are a total of 26 common visible satellites for vehicles 1 and 2 for the study interval depicted in Fig.3. Table.1 shows the results of utilizing the MVA to determine the optimal geometric arrangement of four satellites. In Table.1, we highlighted the final best categories of satellites based on the lowest RMSE, lowest average estimated distance, and lowest relative error on DD/SD algorithms for one-, two-, three-, and four-satellite systems, respectively. Notice that all the values reported in Table 1 are in meters. Finally, as stated in [12], when four satellites are used, there is no significant diference between SD and DD methods, which is also true in our investigation.
To assess the Lagrange interpolation, we investigated the DD/SD IVD estimation algorithm in three situations, including employing satellite locations derived by the Lagrange method and ifxed for 15 minutes at 12:45 and 13:00 UTC. Fig.5 (a) and Fig.5 (b) show the IVD estimate using the DD/SD approach in those three scenarios for one- and three-system satellites, respectively. It is apparent from these figures that DD/SD techniques employing Lagrange interpolation 4.5 4 ) m (3.5 D V I ted 3 a m i ts2.5 E 2 7 6 5 ) (m4 D V Itd3 e a m i ts2 E 1 0 -1 50 50 100
150 Epoch Time (t)
(a) 100
150 Epoch Time (t) (b)
Ground truth Lagrange Interpolation Satellite locations fixed at 12:45 Satellite locations fixed at 13:00 200
250 Ground truth Lagrange Interpolation Satellite locations fixed at 12:45 Satellite locations fixed at 13:00 200 250 and fixed satellite locations at 13:00 UTC are comparable, thus not justifying the increased complexity of the method.
Furthermore, it can be seen from Fig.5 (a) and Fig.5 (b) that computing the IVD at 12:45 UTC has an influence on the IVD estimate accuracy and produces additional uncertainty. More precisely, consider Table.2 and the definition of an absolute accuracy error, i.e., = | () − ^ ()|. When utilizing Lagrange interpolation and fixed satellite coordinates at 12:45 UTC, the absolute error for IVD estimate using DD in one satellite system is 6 cm and 19.1 cm, respectively. Similarly, in a four-satellite system, the error increases from 11.8 cm to 20.1 cm.
In summary, Lagrange interpolation proves to be a suitable choice for determining satellite locations in the context of IVD estimation algorithms based on pseudorange measurements for fully autonomous vehicles when centimeter-level accuracy is crucial and method complexity is not a major concern. Its ability to provide accurate results between Lagrange interpolation and fixed satellite positions makes it a sensible option for achieving high precision in such applications.
This study examined the performance of the Lagrange interpolation method for calculating satellite positions to use in cooperative IVD estimation algorithms in a real-world application using a single 15-minute dataset. The experimental results indicated a well-functioning Lagrange interpolation. Moreover, this study demonstrated that utilizing outdated satellite locations for IVD estimates increases IVD uncertainty from 11.8 cm up to 20.1 cm in four systems of satellites and from 6 cm up to 19.1 cm in one system of satellites, which is crucial for fully autonomous vehicles.
Several future works are planned. First, a comparative study will be investigated to analyze the positions of satellites estimated using Lagrange interpolation in conjunction with broadcast ephemeris, as well as higher-order interpolations of IGS precise orbits. Second, there will be a focus on simulating and assessing the performance of Lagrange interpolation in moving vehicles and for longer study periods exceeding 15 minutes. Finally, as carrier-based techniques are increasingly utilized by mass-market receivers to enhance accuracy, an examination of their applicability to the IVD estimation problem will also be undertaken.
This research was supported by Centro Ricerche Fiat (CRF) and imec–WAVES research group at Ghent University. actions on Intelligent Transportation Systems, vol. 20, no. 2, Feb. 2019, pp. 682-691. doi: 10.1109/TITS.2018.2833438. [7] N. Saeed, W. Ahmad, D. M. S. Bhatti, Localization of vehicular ad-hoc networks with RSS based distance estimation, in: Proceedings of International Conference on Computing, Mathematics and Engineering Technologies (iCoMET), 2018, pp. 1-6. doi: 10.1109/ICOMET.2018.8346313. [8] J. Yin, Q. Wan, S. Yang, K. C. Ho, A Simple and Accurate TDOA-AOA Localization Method Using Two Stations, in: IEEE Signal Processing Letters, vol. 23, no. 1, Jan. 2016, pp. 144-148. doi: 10.1109/LSP.2015.2505138. [9] H. Cao, Y. Wang, J. Bi, S. Xu, M. Si, H. Qi, Indoor positioning method using WiFi RTT based on LOS identification and range calibration, in: ISPRS Int. J. Geo-Inf., vol. 9, no. 11, p. 627, Oct. 2020 [10] J. He, H. C. So, A Hybrid TDOA-Fingerprinting-Based Localization System for LTE Network, in: IEEE Sensors Journal, vol. 20, no. 22, 15 November 2020, pp. 13653-13665. doi: 10.1109/JSEN.2020.3004179. [11] F. de Ponte Müller, E. M. Diaz, B. Kloiber, T. Strang, Bayesian cooperative relative vehicle positioning using pseudorange diferences, in: Proceedings of IEEE/ION Position, Location and Navigation Symposium - PLANS 2014, 2014, pp. 434-444. doi: 10.1109/PLANS.2014.6851401. [12] M. Alijani, A. Steccanella, D. Fontanelli, Cooperative Positioning Algorithms for Estimating Inter-Vehicle Distance Using Multi-GNSS, in: Proceedings of the 2023 IEEE International Instrumentation and Measurement Technology Conference (I2MTC), Kuala Lumpur, Malaysia, 2023, pp. 1-6. doi: 10.1109/I2MTC53148.2023.10176082. [13] P. Misra, P. Enge, Global Positioning System: Signals, Measurement and Performance (Revised 2nd Edition), Revised 2nd Edition Published in 2011, Ganga-Jamuna Press, P.O.
Box 633, Lincoln, MA 01773. [14] URL: https://igs.org/wg/rinex/#documents-formats (Last accessed on April. 21, 2023). [15] URL: https://www.rtklib.com/ (Last accessed on July. 12, 2023) [16] URL: https://igs.org/data/ (Last accessed on April. 21, 2023). [17] M. Horemuz, J. V. Andersson, Polynomial interpolation of GPS satellite coordinates, GPS
Solut (2006) 10: 67–72. doi: 10.1007/s10291-005-0018-0. [18] L. C. Chen, X. L. Jia, Fitting the Broadcast Ephemeris of Navigation Satellites by Chebshev
Approximation, in: Progress in Astronomy, China, Papers 24(2), 167-173 (2006). [19] B. Neta, D. Danielson, J. Clynch, C. Sagovac, Fast interpolation for Global Positioning System (GPS) satellite orbits, in: Proceedings of the AIAA/AAS Astrodynamics Conference, San Diego, CA, July 29-31, 1996. https://doi.org/10.2514/6.1996-3658. [20] W. Jianmin, L. Yabo, Z. Huizhong, M. Tianming, Interpolation Method Research and Precision Analysis of GPS Satellite Position, Journal of Systems Science and Information, vol. 6, no. 3, 2018, pp. 277-288. https://doi.org/10.21078/JSSI-2018-277-12 [21] Y. Zheng, J. Zhang, Satellite Orbit Interpolation Algorithm Analysis for GNSS Terminals, in: Springer Nature Singapore Pte Ltd. 2020, J. Sun et al. (Eds.): CSNC 2020, LNEE 652, pp. 310–321. https://doi.org/10.1007/978-981-15-3715-8-29. [22] H. Tong, H. Sha, G. Zhang, G. Ou, A high-precision and real-time interpolation method for satellite orbit in GNSS, in: J. National Univ. Defense Technol. 2012(34), 59–64,(2012).