arXiv:1703.02098v1 [] 6 Mar 2017

The Impact of Road Configuration on V2V-based Cooperative
Localization
Macheng Shen
Department of Naval Architecture
and Marine Engineering
University of Michigan
Ann Arbor, Michigan 48109
Email: macshen@umich.edu

Ding Zhao
Transportation Research Institute
University of Michigan
Ann Arbor, Michigan 48109
Email: zhaoding@umich.edu

Abstract—Cooperative localization with map matching has
been shown to reduce Global Navigation Satellite System
(GNSS) localization error from several meters to sub-meter
level by fusing the GNSS measurements of four vehicles in our
previous work. While further error reduction is expected to be
achievable by increasing the number of vehicles, the quantitative
relationship between the estimation error and the number of
connected vehicles has neither been systematically investigated
nor analytically proved. In this work, a theoretical study is
presented that analytically proves the correlation between the
localization error and the number of connected vehicles in two
cases of practical interest. More specifically, it is shown that,
under the assumption of small non-common error, the expected
square error of the GNSS common error correction is inversely
proportional to the number of vehicles, if the road directions
obey a uniform distribution, or inversely proportional to logarithm of the number of vehicles, if the road directions obey a
Bernoulli distribution. Numerical simulations are conducted to
justify these analytic results. Moreover, the simulation results
show that the aforementioned error decrement rates hold even
when the assumption of small non-common error is violated.

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. 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). CMM has been shown able to improve
Global Navigation Satellite System (GNSS) positioning of
a group of connected vehicles through estimation and correction of the common GNSS localization error. Since the
error caused by atmospheric delay and satellite clock error is
almost the same to all the vehicles in the same area, this
common error can be estimated by matching the vehicle
positioning results to a digital road map, assuming that
all the vehicles travel on lanes. With a properly estimated
common error, the positioning of vehicles can be corrected,
thus improving the localization accuracy. The improvement
would largely depend on the quality of the common error
estimation, which is determined by the CMM algorithm and
the configuration of the road constraints.
Recently, two different CMM algorithms have been devel-

Jing Sun
Department of Naval Architecture
and Marine Engineering
University of Michigan
Ann Arbor, Michigan 48109
Email: jingsun@umich.edu

oped for GNSS common error estimation problem, i.e., a nonBayesian particle-based approach in Rohani et. al. [1] and a
Bayesian approach based on a Rao-Blackwellized Particle
Filter in our previous work [2], [3].
In contrast, the effects of road configuration on the common error estimation have not been reported in open literature. Intuitively, in order to produce a good estimation of the
common error, the road constraints should be rich enough
so that common error in different directions can be detected.
This richness is expected to be enhanced with the number of
vehicles and the diversity of the road directions.
In this work, the correlation between the estimation quality
of the common error and the richness of the road constraints
is quantified analytically. More specifically, the functional
relationships between the mean square error of the common
error estimation and the number of connected vehicles are derived under two different assumptions about road configurations. The results provide a guideline for the implementation
of CMM and a foundation for the development of algorithms
that intelligently select vehicles to include for maximal error
reduction.
In the following sections, details of the derivation of the
error bounds are presented with justification through Monte
Carlo simulations. In Section 2, an analytic expression of
the estimation error as a function of the road configuration and the non-common error is derived. In Section 3,
asymptotic formulas of the expectation of the estimation
error with respect to Gaussian distributed non-common error
are derived for uniformly or Bernoulli distributed road directions. Nonetheless, most of the results are derived under
the assumptions of large number of vehicles and small noncommon error. In Section 4, simulation results are presented
to demonstrate and justify the applicability of the theoretical
results to realistic scenarios where both the number of
connected vehicles and the non-common error are finite. In
Section 5, the contributions and conclusions are summarized.
II. E STIMATION ERROR OF THE COMMON ERROR
In this section, we propose a framework of vehicle positioning within a reference road framework to facilitate
the analytic investigation. The GNSS measurement will be

Alternatively, (2) can be interpreted as the feasible set of
the common error given the GNSS positioning and the noncommon error. The non-common error is unknown, however,
to the implementation of CMM. Thus, an approximation of
the feasible set by neglecting the non-common error is used
instead of the exact feasible set, which is
Ω = {τ |
= {τ |
= {τ |

N
\

i=1
N
\

i=1
N
\

i=1

gi (xG
i − τ )}
C
N
gi (xL
i + x + x̃i − τ )}

(4)

g̃i (xC + x̃N
i − τ )},

where
Fig. 1. Illustration of the deviation from the lane center (yellow arrow), the
common error (red arrow), the non-common error (black arrow), the lane
center point (blue dot) and the GNSS positioning (red dot)

decomposed into four components and one estimator of the
common error will be formulated and the corresponding
estimation error will be represented as an integral depending
on the non-common error and the road constraints.
The coordinate of GNSS positioning of the i-th vehicle
can be decomposed into superposition of the coordinate of a
point on the corresponding lane center, the deviation of the
vehicle from the lane center (yellow arrows), the common
error (red arrows) and the non-common error (black arrows)
as illustrated in Fig. 1. The blue and red dots represent the
true positions and the GNSS positioning, respectively. This
relationship can be expressed mathematically as
L
D
C
N
xG
i = xi + xi + x + xi , i = 1, 2, ..., N,

C
N
gi (xG
i − x − xi ) < 0.

(2)

In reality, the geometry of the road sides can be so complicated that the constraints cannot be expressed analytically.
But frequently, the road sides can be approximated as straight
lines such as those shown in Fig. 1. In these cases, the
constraint functions gi have simple analytic forms
gi (x) = (x − xL
i ) · ni − w,

(3)

where {·} is the dot product operator, ni is the unit vector
normal to the lane center point towards outside of the road
and w is the half width of the lane.

(5)

g̃i (x) , gi (x + xL
i ) = x · ni − w

(6)

and
A point estimator of the common error can be taken as the
average over the approximate feasible set Ω,
Z
Z
1
C
x̂ =
τ dA, S = dA,
(7)
S
Ω

Ω

where τ is the dummy integration variable and dA is the area
element.
The estimation error of the common error is of practical
interest, which can be evaluated as

(1)

L
where xG
i is the GNSS positioning of the i-th vehicle, xi is
the closet point on the center of the lane from the vehicle,
L
C
xD
i is the deviation of the vehicle coordinates from xi , x is
N
the GNSS common localization error, xi is the GNSS noncommon localization error including receiver noise error and
multipath error and N is the number of connected vehicles.
The fact that all the vehicles travel on the roads can be
expressed as a set of inequalities

D
N
x̃N
i , xi + xi

e = xC − x̂C
Z
1
C
τ dA
=x −
S
Ω
Z
1
=
(xC − τ )dA
S
Ω
Z
1
=
τ ′ dA,
S

(8)

τ ′ = xC − τ,

(9)

Ω′

where
and
Ω′ = {τ ′ |

N
\

′
g̃i (x̃N
i + τ ) < 0}.

(10)

i=1

Eq. (8) and (10) states that the estimation error equals to
the geometric center of the intersection of the road constraints
perturbed by the composite non-common error x̃N
i .
It has been shown by experimental data that the GNSS
non-common error can be well approximated as Gaussian
random variable in [2]. The Safety Pilot dataset collected in
Ann Arbor shows that statistically the deviations from the
lane center also obey Gaussian distribution. As a result, the
composite error x̃N
i is a Gaussian random variable.

The expectation of the square estimation error is of practical interest. In two special cases, analytic approximations
to this expectation valid for large number of vehicles can be
established.
III. A SYMPTOTIC A NALYSIS

FOR THE EXPECTED SQUARE
ERROR

In this section, we derive the asymptotic decay of the mean
square error with respect to the number of vehicles in two
typical cases of the road configuration, whose examples are
shown in Fig. 2. In the first case, the road configuration is
modeled as cross roads where the roads are either parallel
or orthogonal. In the second case, it is modeled as randomly
oriented roads where the direction angles obey a uniform
distribution.
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 vehicles relative to
the reference frame belong to a set with four elements:
3π
π
}
(11)
θi ∈ {0, , π,
2
2
This case can be viewed as a simplified model for the
urban areas where most roads are orthogonal to each other.
Invoking (8), the square error can be expressed analytically
as
X 2 + X22 + X32 + X42 − 2X1 X3 − 2X2 X4
e2 = 1
, (12)
4
where Xj , j = 1, 2, 3, 4 are the largest projections of the
composite non-common error on each of the four normal
vector:
N
N
Xj = max{x̃N
j1 · nj1 , x̃j2 · nj2 , ..., x̃jN j · njN j }, j = 1, 2, 3, 4.
(13)
Nj , j = 1, 2, 3, 4 are the numbers of vehicles traveling in
each of the four directions.
If all the x̃N
i · ni , i = 1, 2, ...N are independent and
identically distributed, then according to the Fisher-TippettGnedenko theorem [4], the limit distribution of Xj for large
Nj is Gumbel distribution whose cumulative distribution
function is given by

F (Xj ) = exp(−exp(−(Xj − µj )/βj )).

(14)

Moreover, The leading order of the normalization constants
µj and βj are related to the variance of the Gaussian
distribution σ through [5]
q
1
.
(15)
µj ∼ σ 2log(Nj ), βj ∼ σ p
2log(Nj )

Using the property of Gumbel distribution, the expectation
of e2 with respect to Xj can be evaluated:
EX [e2 ] =

4
π2 X 2 1
β + [µ1 − µ3 + γ(β1 − β3 )]2
24 j=1 j
4

1
+ [µ2 − µ4 + γ(β2 − β4 )]2 ,
4

(16)

where γ ≈ 0.5772 is the Euler-Mascheroni constant.
With the assumption that all the four Nj 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
1
1
O( log(N
) and the following two terms are of O( Nj log(N
).
j)
j)
Thus, the leading order asymptotic approximation is
EX [e2 ] ∼

4
1
π2 σ2 X
.
48 j=1 log(Nj )

(17)

B. Uniformly distributed random road directions
In the second case, each direction angle is assumed to be
randomly distributed within [0, 2π). In addition, it is assumed
that the non-common error is small enough such that (8) can
be linearized with respect to the non-common error:
e = e0 + ∆e = e0 +
where

1
e0 =
S0

′

Ω0 = {τ |

Z

C X̃
,
S0

τ ′ dA,

(18)

(19)

Ω0

N
\

g̃i (τ ′ ) < 0},

(20)

i=1

N
N
T
X̃ = [x̃N
1 · n1 , x̃2 · n2 , ..., x̃N · nN ] ,

(21)

and

∂e
.
(22)
∂ X̃
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
2πw
,
(23)
||X̃||∞ ≪
N
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̃ ∼
2
N (0N ×1 , diag(σ12 , σ22 , ..., σN
)), the expectation of the square
error is
1
(24)
EX [e2 ] = e20 + 2 tr(LT C T CL),
S0
C = S0

where L = diag(σ1 , σ2 , ..., σN ) is the Cholesky decomposition of the joint Gaussian covariance matrix.
Eq. (24) is quite useful in practice as it implicitly provides
a measurement of the road configurations. Given any road
configurations specified by e0 and C, the mean square
error can be evaluated. An optimization technique can be
developed to select the best road configuration so as to
optimize the localization accuracy. On the other hand, the
theoretical value of this equation is demonstrated through the
derivation of asymptotic error decrement shown as follows.
As both e0 , S0 and C depends on the road direction angles
θi , EX (e2 ) is also a random variable. It can be shown that

(a) Orthogonal road model

(b) Random road model

Fig. 2. Examples of road configurations that can be modeled by the presented two road angle distributions, images from OpenStreetMap

the expectation of EX (e2 ) with respect to θi , i = 1, 2, ..., N
is of O( N1 ) (See Appendix). More specifically,
2w
1
+ o( )
9N
N

(25)

and
PN
3 i=1 σi2
1
1
T T
+ o( )
Eθ [ 2 tr(L C CL)] =
2
S0
2N
N

(26)

IV. S IMULATION J USTIFICATION
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 e2 . 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 a
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 e2
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.
A. Small non-common error: σ = 0.3 m
Fig. 3 shows the comparison of 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 e2 . 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 the result of the fact that the convergence to the Gumbel
distribution is rather slow [5].
Fig. 4 shows the comparison of the random road angle

Mean Square error (m 2)

Eθ [e20 ] =

2

0.07
0.06

Asymptotic formula
Simulation using Monte Carlo integration
Simulation using Eq. (12)

0.05
0.04
0.03
0.02
10

20
30
40
Number of connected vehicles

50

Fig. 3. Comparison between the asymptotic formula and numerical simulation results on the orthogonal road angle case

case. Fig. 5 shows 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 expected for 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

0.5

1.2
Mean square estimation error (m 2)

Mean sqaure error (m2)

0.6
Asymptotic formula
Simulation using Monte Carlo integration

0.4
0.3
0.2
0.1
0
10

20
30
40
Number of connected vehicles

50

100

0.8

Orthogonal road
Uniformly distributed random road

0.6

0.4

10

20
30
Number of connected vehicles

40

50

Fig. 6. Numerical results of the error decrement in the two cases of road
configuration with large non-common error

dominant directions, the expectation of the error would be
large as the probability that the error cancels out becomes
small.

and simulation result (m2)

Difference between asymptotic formula

Fig. 4. Comparison between the asymptotic formula and numerical simulation results on the uniformly distributed random road angle case

1

10-1

V. CONCLUSIONS

10-2

10-3
10

20
30
40
Number of connected vehicles

50

Fig. 5. Difference between the asymptotic formula and the numerical
simulation result in Figure 3

to generate simulation results because of its simplicity for
implementation.
Fig. 6 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 another point of view from
the mathematical expression (10). The estimation 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
of the error become small. In contrast, if there exists some

In this paper, the impact of road configuration on the
CMM localization accuracy is studied theoretically. The
correlation between the mean square error of the common
error estimation and the number of connected vehicles is
proved analytically and shown through numerical simulation.
The main results and findings are summarized:
1) A closed form expression of the mean square estimation error in terms of the road configuration and the
non-common error is derived for the evaluation of the
impact of road configuration on CMM.
2) The mean square error of the common error estimation
is inversely proportional to the logarithm of the number
of connected vehicles asymptotically if the random
road angles are either parallel or orthogonal.
3) The mean square error of the common error estimation
is inversely proportional to the number of connected
vehicles asymptotically if the road angles obey a uniform distribution.
ACKNOWLEDGMENT
This work is funded by the Mobility Transformation Center
at the University of Michigan. The first two authors, M. Shen
and D. Zhao have equally contributed to this research.
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
θ˜i =
e20

(

θi+1 − θi
θ1 − θN + 2π

for i = 1, 2, ...N − 1
for i = N

|

(27)

can be expressed in terms of the geometric quantities:
e20

PN
˜
( i=1 23 w3 tan( θ2i )cos(θi ))2
=
S02
PN 2 3
˜
( i=1 3 w tan( θ2i )sin(θi ))2
+
S02
P
˜
N
4w2 i=1 tan2 ( θ2i )
=
9
π2
PN PN
θ˜j
θ˜
4w2 i=1 j=1 tan( 2i )tan( 2 )cos(θj − θi )
+
9
π2
+ Higher Order T erms

(28)

√π
N

θ˜i N
θ˜i
θ˜i
) − ( )2 ] (1 − )N −1 dθ˜i |
2
2
π
π
0
Z √π ˜
˜i
N θi
θ
N
( )4 (1 − )N −1 dθ˜i
<
2 π
π
0
Z √π ˜
N θi
θ˜i
N
π2
( )2 (1 − )N −1 dθ˜i
<
4N 0
2 π
π
1
= O( 3 ).
N
Z π2
θ˜i N
θ˜i
tan2 ( ) (1 − )N −1 dθ˜i |
|
2 π
π
√π
N
Z π2
θ˜i
N
(1 − )N −1 dθ˜i
<
π
π
√π
Z

[tan2 (

(33)

(34)

N

1
1
= (1 − √ )N − ( )N .
2
N

As
1
1
lim N 2 (1 − √ )N = lim N 4 ((1 − )N )N
N
→∞
N
N
= lim N 4 e−N = 0,

N →∞

The probability distribution of θ˜i can be derived:

(35)

N →∞

θ˜i
N
p(θ̃i ) = (1 − )N −1 , 0 ≤ θ˜i ≤ π.
π
π

(29)

Accurate to the leading order:
N
X
˜
˜
4w2
4w2 N
2 θi
2 θi
tan
(
E
[
E
[tan
(
)]
=
)]
θ
θ
9π 2
2
9π 2
2
i=1
(30)
The expectation in (30) can be calculated:

Eθ [e20 ] =

Z π
θ˜i N
θ˜i
θ˜i
tan2 ( ) (1 − )N −1 dθ˜i
Eθ [tan ( )] =
2
2 π
π
0
Z √π ˜
˜
N θi
θi
N
( )2 (1 − )N −1 dθ˜i
=
2 π
π
0
Z √π
˜i N
˜i
N
θ
θ˜i
θ
[tan2 ( ) − ( )2 ] (1 − )N −1 dθ˜i
+
2
2
π
π
0
Z π2
˜i N
˜i
θ
θ
+
tan2 ( ) (1 − )N −1 dθ˜i
2 π
π
√π
N
Z π
θ˜i N
θ˜i
tan2 ( ) (1 − )N −1 dθ˜i .
+
π
2 π
π
2
(31)
The first term after the last equality in (31) can be
integrated analytically and shown that
2

Z

0

√π
N

(

θ˜i
π2
θ˜i 2 N
.
)
(1 − )N −1 dθ˜i ∼
2 π
π
2N 2

(32)

The remaining three term will be shown as o( N12 ) terms:

it follows that
Z π2
θ˜i N
θ˜i
1
tan2 ( ) (1 − )N −1 dθ˜i = o( 2 ).
2 π
π
N
√π
N
Z π
θ˜i N
θ˜i
tan2 ( ) (1 − )N −1 dθ˜i |
|
π
2 π
π
2
Z π
˜
θi
N
(1 − )N −3 dθ˜i
<
π
π
π
Z 2π
N 1 N −3 ˜
N 1
1
<
( )
dθi = ( )N −3 = o( 2 ).
π
π 2
2 2
N
2
Eθ [
=

(37)

1
1
tr(LT C T CL)] = Eθ̃ [ 2 tr(LT C T CL)]
S02
S0

N
X
2σi2 (Eθ̃ [tan2 ( θ̃2i )] + E 2 [tan( θ̃2i ])
θ̃

π2

i=1

=

(36)

3

PN

2
i=1 σi
2
2N

+ o(

+ H.O.T. (38)

1
).
N
R EFERENCES

[1] M. Rohani, D. Gingras and D. Gruyer.,“A Novel Approach for Improved
Vehicular Positioning Using Cooperative Map Matching and Dynamic
Base Station DGPS Concept,” in IEEE Transactions on Intelligent
Transportation Systems , vol. 17, no. 1, pp. 230-239, Jan. 2016.
[2] M. Shen, D. Zhao, J. Sun and H. Peng “Improving Localization
Accuracy in Connected Vehicle Networks Using Rao-Blackwellized
Particle Filters: Theory, Simulations, and Experiments.” submitted to
IEEE Transactions on Intelligent Transportation Systems.
[3] M. Shen, D. Zhao, and J. Sun, “Enhancement of Low-cost GNSS
Localization in Connected Vehicle Networks Using Rao-Blackwellized
Particle Filters.” In IEEE 19th International Conference on Intelligent
Transportation Systems, pp. 834-840, Nov. 2016.
[4] B. Basrak, “Fisher-Tippett Theorem.” International Encyclopedia of
Statistical Science, Springer Berlin Heidelberg, 2011: pp. 525-526.
[5] D. H. Aron and H. N. Nagaraja, “Order statistics.” John Wiley & Sons,
Inc., 1981: pp. 297.

