{'fraction_non_alphanumeric': 0.030001692620176032, 'fraction_numerical': 0.01032498307379824, 'mean_word_length': 4.555477197931359, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Impact of Road Configuration in V2V-based Cooperative Localization: Mathematical Analysis and Real-world Evaluation

Cooperative map matching (CMM) uses the Global Navigation Satellite System (GNSS) position information of a group of vehicles to improve the standalone localization accuracy. It has been shown, in our previous work, that the GNSS error can be reduced from several meters to sub-meter level by matching the biased GNSS positioning to a digital map with road constraints. While further error reduction is expected by increasing the number of participating vehicles, fundamental questions on how the vehicle membership within CMM affects the performance of the CMM results need to be addressed to provide guidelines for design and optimization of the vehicle network. This work presents a theoretical study that establishes a framework for quantitative evaluation of the impact of the road constraints on the CMM accuracy. More specifically, a closed-form expression of the CMM error in terms of the road constraints and GNSS error is derived based on a simple CMM rule. The asymptotic decay of the CMM error as the number of vehicles increases is established and justified through numerical simulations. Moreover, it is proved that the CMM error can be minimized if the directions of the roads on which the connected vehicles travel obey a uniform distribution. Finally, the localization accuracy of CMM is evaluated based on the Safety Pilot Model Deployment and Pillar dataset of Ann Arbor traffic flow collected over three years period. The contributions of this work include establishing a theoretical foundation for CMM as well as providing insight and motivation for applications of CMM.


I. INTRODUCTION
Low-cost Global Navigation Satellite Systems (GNSS) are used for most mobile applications, whose localization accuracy are typically in the range of several meters. The limited accuracy of the low-cost GNSS is due to the atmospheric error and satellite error, collectively referred to as the common error, as well as receiver noise and multipath error, referred to as the non-common error.
Enhancement of standalone GNSS has been an active research area in the recent years. Various approaches have been developed, such as sensor fusion ( [1], [2], [3], [4]), cooperative localization ( [5], [6], [7]) and map matching ( [8], [9], [10], [11]). For instance, Liu et al. [1] proposed a novel robust cubature Kalman filter to improve the performance of data fusion with uncertain sensor observations under a GNSS/Dedicated Short Range Communications (DSRC) integrated architecture for cooperative localization. Cruz et al. [5]  vehicle's position that fuses information from smartphone inertial sensors, V2V signal strength measurements, velocity, Global Positioning System (GPS) position and map information. Knoop et al. [11] conducted a test for lane determination with GPS Precise Point Positioning which exploited the fact that most driving is within a lane so as to achieve a decimeter accuracy.
These works present promising improvements on GNSS localization, while most of them utilize additional information from different sources. Improving the localization accuracy of these widespread GNSS without incurring additional hardware and infrastructure costs has motivated recent research activities on Cooperative Map Matching (CMM) [9], [12], [10]. CMM has been shown capable of improving Global Navigation Satellite System (GNSS) positioning of a group of connected vehicles through estimation and correction of the GNSS common localization error. The estimation error for the common localization error, which determines the accuracy of the CMM localization, is hereafter referred to as the CMM error.  Fig. 1 illustrates how error-corrupted GNSS information can be corrected through a naive CMM approach. The GNSS solutions, denoted as red dots, of all the three vehicles are biased away from their true positions, while the biases are highly correlated. Virtual road constraints from the red and the blue vehicles are applied to restrict the positioning of the green vehicle. The underlying assumption for the application of the virtual constraints is that the GNSS positioning biases of the three vehicles are the same. This example manifests the impact of road constraints on the CMM localization.
It is desirable to quantify this impact so that we can estimate the CMM accuracy as well as optimize the vehicular network to achieve maximal error reduction. In our previous conference paper [13], the correlation between the CMM error and the richness of the road constraints is quantified analytically. More specifically, a closed form expression of the CMM error in terms of the road angles as well as the GNSS error is derived based on a simple CMM rule that neglects the probabilistic property of the GNSS error.
In this work, we extend our previous work with a theoretical analysis on the optimal distribution of road directions associated with the vehicles that participate in the CMM and evaluation of the CMM accuracy to data collected in Ann Arbor. These results constitute the theoretical foundation of CMM as well as provide a guideline for the implementation of CMM.
The organization of this paper is described as follows. In Section 2, an analytic expression of CMM as a function of the road configuration and the non-common error is derived. In Section 3, asymptotic formulas of the expectation of the CMM error with respect to Gaussian distributed non-common error are derived for uniformly or Bernoulli distributed road directions. In Section 4, simulation results are presented to demonstrate and justify the applicability of the theoretical results. In Section 5, it is proved that the uniform distribution of road angles associated with participating vehicles is optimal for minimizing the mean square CMM error. In Section 6, the localization accuracy of CMM is evaluated based on the Safety Pilot Model Deployment and Pillar 1 (SPMDP1) dataset collected in Ann Arbor over three years period. In Section 7, the contributions and conclusions are summarized.

II. DERIVATION OF THE CMM ERROR
In this section, we propose a framework of vehicle positioning within a reference road framework to facilitate the analytic investigation.
The following assumptions are essential in our exposition: 1) The GNSS common error is the same for all the connected vehicles within the vehicular network. 2) The road side can be locally approximated as a straight line.
3) The GNSS non-common error is random with Gaussian distribution. 4) The GNSS non-common error is small enough such that the exact expression for the CMM error can be approximated by its first order linearization with respect to the non-common error.
The first assumption is often satisfied as long as the connected vehicles are geographically close to each other, for example, within several miles. The second and the fourth assumptions are made for mathematical convenience. If they are violated, however, the exact expression of the CMM error will still be valid but the asymptotic approximation will be inaccurate. The third assumption has been experimentally verified in [12] under open sky conditions. Consider a network of connected vehicles consisting of N vehicles. The coordinate of GNSS positioning of the ith vehicle, x G i , can be decomposed into a superposition of The fact that all the vehicles travel on the roads can be expressed as a set of inequalities Applying the second assumption, the constraint functions g i have simple analytic forms where {·} is the dot product operator, n i is the unit vector normal to the lane center point towards outside of the road and w is the half width of the lane. The intersection of all the inequalities in (2) can be interpreted as the feasible set of the common error given the GNSS positioning and the non-common error. The non-common error is, however, unknown to the implementation of CMM. Thus, the following approximation of the feasible set by neglecting the non-common error is used instead of the exact feasible set, Eq. (1) has been applied in (4) to derive the second equality from the first one. A point estimator of the common error is taken as the average over the approximate feasible set Ω, where τ is the dummy integration variable and dA is the area element.
The estimation error, that is the difference between the true common error and the estimated common error (referred to as CMM error), is of practical interest, which can be evaluated, where and Eq. (8) and (10) states that the CMM error equals to the geometric center of the intersection of the road constraints perturbed by the composite non-common errorx N i . The expectation of the square CMM error with respect to Gaussian non-common error is of practical interest. In two special cases, analytic approximations to this expectation valid for large number of vehicles can be established.

ERROR
In this section, the expected square error is derived with two different road configurations. The road configuration is specified by the driving directions of all the roads along which the participating vehicles travel.

A. Orthogonal road directions
In the first case, it is assumed that each road is parallel to one of the two orthogonal axes of the global reference frame. As a result, the direction angles θ of the roads relative to the reference frame belong to a set with four elements. Without loss of generality, we define the reference frame to be aligned with the road directions, such that the angles of driving direction This case can be viewed as a simplified model for the urban areas where most roads are orthogonal.
Invoking (8), the square error can be expressed analytically as where X j , j = 1, 2, 3, 4 are the largest projections of the composite non-common error on each of the four normal vector: If all the composite non-common error,x N i , i = 1, 2, ...N , is independent and identically distributed, then according to the Fisher-Tippett-Gnedenko theorem [14], the limit distribution of X j for large N j is Gumbel distribution whose cumulative distribution function is given by Moreover, with the third assumption, The leading order of the normalization constants µ j and β j are related to the variance of the Gaussian distribution σ through [15] Using the property of Gumbel distribution, the expectation of e 2 with respect to X j can be evaluated: where γ ≈ 0.5772 is the Euler-Mascheroni constant.
Considering the case that all the four N j are large number of the same order and using the asymptotic formulas (15), it can be readily shown that the first term in (16) is of O( 1 log(Nj ) ) and the following two terms are of O( 1 Nj log(Nj ) ). Thus, the leading order asymptotic approximation is .

B. Uniformly distributed random road directions
In the second case, each direction angle is assumed to be randomly distributed within [0, 2π). Due to the fourth assumption, Eq. (8) can be linearized with respect to the noncommon error: where and C is a 2 × N matrix whose components are related to the geometric quantities of the road constraints.
The condition under which the linearization (18) is valid is where w is the half width of the lane. With the assumption that each non-common error obeys independent Gaussian distribution with zero mean, i.e.,X ∼ N (0 N ×1 , diag(σ 2 1 , σ 2 2 , ..., σ 2 N )), the expectation of the square error is where L = diag(σ 1 , σ 2 , ..., σ N ) is the Cholesky decomposition of the joint Gaussian covariance matrix.
As both e 0 , S 0 and C depends on the road direction angles θ i , E X (e 2 ) is also a random variable. It can be shown that the expectation of E X (e 2 ) with respect to and

IV. SIMULATION VERIFICATION
In this section, simulation results are presented to justify the validity of the asymptotic formulas derived in Section 3. The expectations are calculated by averaging over 5000 samples of e 2 . Each sample value for the orthogonal road case is calculated through two approaches. One approach is the analytic formula (12), and the other approach is an importance sampling Monte Carlo integration where the proposal distribution is a two-dimensional uniform distribution. Besides, the number of vehicles in each direction is the same. For the uniformly random road angle case, each sample value of e 2 is calculated by the Monte Carlo integration. The number of samples to implement each Monte Carlo integration is 10000. The road half width is w = 2 m in the simulation.  Figure 3. Comparison between the asymptotic formula and numerical simulation results in the orthogonal road angle case Fig. 3 shows the comparison in the orthogonal road case. The asymptotic formula is in good agreement with the numerical results as the number of vehicles increases. The results using the two numerical approaches are also different, which should be caused by the random error resulted from the Monte Carlo integration used to calculate e 2 . Therefore, the one that uses (8) is expected to be closer to the underlying true expectation. Compared with this result, the asymptotic formula slightly overestimates the error. This difference may be resulted from the fact that the convergence to the Gumbel distribution is rather slow [15].  Figure 4. Comparison between the asymptotic formula and numerical simulation results in the uniformly distributed random road angle case Fig. 4 shows the comparison in the random road angle case as well as the corresponding difference between the asymptotic formula and the simulation results using Monte Carlo integration. The difference reaches its minimum around N = 25 ∼ 30 and increases with the further increase of N . This result can be attributed to the following two reasons. First, the asymptotic formula is derived for large N . As a result, the difference at small N should be significant. Second, the linearization (18) based on the small non-common error assumption (23) eventually becomes invalid for fixed σ and increasing N .

B. Large non-common error: σ = 1 m
The analytic results shown in Section 3 do not apply to the large non-common error case because the approximate feasible set described by (4) may be an empty set. Nonetheless, this problem can be addressed by assigning a weight to each hypothesis of the common error according to its compatibility with the road constraints. The weighted road map approach proposed by Rohani et. al. is applied to generate simulation results because of its simplicity for implementation. Fig. 5 shows the error decrement in the two different cases of road configuration when the non-common error variance is large. As can be observed from the figure, the slope of the decrement curve in the uniformly distributed road case is steeper than that corresponding to the orthogonal road case. This result is expected from intuition as in the former case, the road angles are more diverse, thereby, providing more constraints to correct the GNSS bias. This can also be understood from the mathematical expression (8). The CMM error is equal to the deviation of the geometric center enclosed by the road constraints. As the directions of the road angles become diverse, there is a large probability that the error in different directions cancels out. As a result, the expectation  The expectation of the mean error is insufficient to describe the full distribution of the error. The distribution of the error is obtained approximately by Monte Carlo simulation. For the number of vehicles ranging from 10 to 20, 10000 samples of road angles are drawn from the uniform distribution and the corresponding mean square CMM error is evaluated and sorted into increasing order shown in Fig. 6. As the number of vehicles increases, not only the average error decreases but also the probability of a significant error become small as indicated by the sharp tails of the distribution.

V. OPTIMALITY OF THE UNIFORM DISTRIBUTION
From the asymptotic analysis in Section 3, it is clear that the distribution of the road directions has a significant impact on the mean CMM error.
In this section, the following theorem is proved, which quantifies the impact of the road direction distribution on the mean CMM error: Theorem 1. Let the direction angles corresponding to all the connected vehicles be random variables that are independent from each other, obeying the same continuous distribution p(θ), θ ∈ [0, 2π), then the uniform distribution p(θ) = 1 2π is a local minimizer of the mean square CMM error (24) in the space of continuous distributions, as the number of connected vehicles N − → ∞.
Proof. Considering an arbitrary continuous distribution of the road angle p(θ), θ ∈ [0, 2π), the periodic condition should be satisfied, as θ = 0 and θ = 2π represent the same angle. This periodicity motivates the following Fourier series expansion, with where the integer m is the summation index, the asterisk denotes the complex conjugate and i = √ −1 is the imaginary unit. The constant term 1 2π ensures that the normalization condition is satisfied.
In the limiting case that N − → ∞, the leading order term of the square CMM error e 2 0 due to deviation of the geometric center can be approximated as whereθ i is the difference between two adjacent angles θ i+1 and θ i as defined in the appendix. In order to derive the expectation of e 2 0 , the distribution ofθ i denoted as f (θ i ; N, p(θ i )) will be considered first. f (θ i ; N, p(θ i )) is a nearest neighbor distribution, which satisfies the following integral equation [16], where the dependence on the parameters N and p(θ i ) will be omitted hereafter.
Together with the normalization condition, the solution to The number of vehicles N and the local density of the road angles p(θ i ) appear as parameters in the distribution. As the product N p(θ i ) increases, the angles distributed around θ i become dense, thus increasing the probability of small differential angleθ i . The expectation ofθ i Combining (30) and (33), the expectation of e 2 0 can be derived as follows, The summation in (34) can be interpreted as an integration as the number of the vehicles N goes to infinity, The Fourier expansion of 1 p 2 (θ) can be obtained and expressed in terms of the Fourier coefficients of p(θ), assuming the deviation from the uniform distribution is infinitesimal, Substituting (36) into (35), Substituting (37) into (34), By taking C m = 0, m ∈ Z + , which corresponds to p(θ) = 1 2π (uniform distribution), the expectation of the square error E[e 2 0 ] is minimized and (25) is also recovered.

PILOT DATA
In this section, the localization accuracy of CMM, using the Safety Pilot program data that were collected in Ann Arbor over three years time period, will be evaluated based on (24).
The average square error E θ [E X [e 2 0 ]], which is a measurement of localization accuracy, depends on the distribution of the road angles and the number of connected vehicles. These two components vary spatially due to the limited communication radius. It would be sufficient for the evaluation of the localization accuracy at any point if the locations and the road angles of all the vehicles were given. As a result, the root mean ] is a functional of the joint distribution of all the vehicle locations and the road angles as well as a function of the location on the map,  Θ)) and the total number of vehicles N varies with time. For example, N will be large at daytime and small at midnight. In order to evaluate J(x) at some given time, e.g., from 8 a.m. to 9 a.m., it is required to estimate the distribution p(x v , Θ)) and the number of vehicles N from historical data. The SPMDP1 dataset [17], which records a 3-year history of the locations and driving angles of 3000 vehicles in Ann Arbor, is used to estimate the distribution as well as the total number of vehicles, assuming that the recorded vehicles comprise 3% of the total vehicle population in Ann Arbor. Examples of the temporal distribution of the recorded vehicles are shown in Fig. 7. On weekdays, there are two peaks at 8 a.m. and 5 p.m., respectively. On weekends and holidays, there are only one peak appearing at 2 p.m.. At midnight, the number of recorded vehicles significantly drops down. This sparsity of vehicles might lead to a significantly biased estimation of the vehicle spatial distribution. In order to reduce this bias, the spatial distribution is obtained by averaging over every day's distribution at the same hour or by averaging over the 24 hours within a day.
The spatial distributions of vehicles over two successive weekdays are shown in Fig. 8. These two distributions looks similar, which indicates the bias due to vehicle sparsity has been mitigated through the averaging.
After an unbiased estimation of the vehicle locations and the road angles distribution has been obtained, samples of (x v , Θ) are drawn, and J(x) is approximated as the average performance over the sample realizations.
The average root mean square CMM error with its 1 − σ bound at the different time within a day is plotted in Fig.  9. The communication radius is assumed to be 1 mile and Figure 8. Vehicle density distribution on two successive weekdays; Red: dense; Green: medium; Blue: sparse the non-common error variance is assumed to be a constant 0.5 m 2 . As expected, the CMM error is large at midnight due to the lack of connected vehicles. The variance of the error is also large which means that the performance of CMM is unstable if the number of connected vehicles is inadequate. In contrast, both the performance and the stability of the performance are much better during the daytime when there is a sufficient number of vehicles connected. Fig. 9 also shows the spatial distribution of the CMM error, with blue indicating a small error, red indicating a large error and black indicating inadequate vehicles for robust localization. In the central area where the vehicles are concentrated and the road angles are diverse, the CMM error is much smaller compared to the marginal area.
Similarly, the average root mean square CMM error on different days of a week is shown in Fig. 10, and that on different months of a year is shown in Fig. 11.
The means and variances plotted in Fig. 10-11 are listed in the Appendix.
VII. CONCLUSIONS In this paper, the impact of road configuration on the CMM localization accuracy is studied theoretically, which is then used to evaluate the CMM accuracy in real world. The key findings and contributions in this paper are summarized as follow: 1) A closed form expression of the CMM error in terms of the road angles and GNSS error is derived based on a simple CMM rule, based on which the asymptotic decay of the CMM error is established analytically. 2) The uniform distribution of the road angles is the optimal distribution that minimizes the CMM error on average.
3) The CMM error in Ann Arbor is predicted based on actual traffic flow data collected in the SPMDP1 dataset. APPENDIX The detail with respect to the derivation of (25) and (26) is presented here.
The direction angles of the roads are denoted by [θ 1 , θ 2 , ..., θ N ]. Without loss of generality, it is assumed that 0 ≤ θ 1 ≤ θ 2 ≤ ... ≤ θ N ≤ 2π. The increments of the angles are defined as e 2 0 can be expressed in terms of the geometric quantities: The probability distribution ofθ i can be derived: Accurate to the leading order:    The expectation in (30) can be calculated: The first term after the last equality in (31) can be integrated analytically and shown that The remaining three term will be shown as o( 1 N 2 ) terms: As lim N →∞ it follows that (51)