Speeding Up the Evaluation of a Mathematical Model for VANETs Using OpenMP - Simulation and Modeling Methodologies, Technologies and Application - page 25

−L when
it collides, since we are assuming that when a vehicle collides it stops instantly at the
point of collision.
Once we have obtained X 1 we can compute p 2 , and recursively we can obtain all the
collision probabilities:

The second term of the sum means that the vehicle cannot cross the position

X i− 1 −L−D s

p i =1 − f ( x ; μ i ,σ ) dx, i =2 ,...,N , (3)

−∞

where

X i− 1 −L + ∞

X i = f ( x ; μ i + D s ,σ ) dx, i =2 ,...,N .

(4)
We want to remark that this model for the collision probabilities is a preliminary approx-
imation and does not describe realistically the collision process. However, the method
to compute the probabilities of the path outcomes is independent of the correctness
or accuracy of the transition probabilities used, and the goal of this paper is to evalu-
ate the benefits of parallelization for this technique to compute the average number of
accidents. An improved model for the transition probabilities can be found in [28].
Let us note how every path in the tree from the root to the leaves leads to a possible
outcome involving every vehicle in the chain. The probability of a particular path is the
product of the transition probabilities that belongs to the path. Since there are multiple
paths that lead to the same final outcome (leaf node in the tree), the probability of that
outcome will be the sum of the probabilities of every path reaching it.
In order to compute the probabilities of the final outcomes, we can construct a
Markov chain whose state diagram is shown in Figure 2 and is based on the previ-
ously discussed probability tree. It is a homogeneous Markov chain with ( N +1)( N +2)
2

x·f ( x ; μ i + D s ,σ ) dx +( X i− 1 −L ) ·

−∞ X i− 1 −L

states,

( S 0 , 0 ,S 1 , 0 ,S 0 , 1 ,..., S N, 0 ,S N− 1 , 1 ,..., S 1 ,N− 1 ,S 0 ,N ) . (5)

The transition matrix P of the resulting Markov chain is a square matrix of dimension
( N +1)( N +2)
2

, which is a sparse matrix, since from each state it is only possible to move
to two of the other subsequent states.
Then, we need to compute the probabilities of going from the initial state to each of
the N +1 final states in N steps, which are given by matrix P N . Therefore, the final
outcome probabilities are the last N +1 entries of the first row of the matrix P N .
Let Π i be the probability of reaching the final outcome with i collided vehicles, that
is, state S i,N−i . We obtain the average of the total number of accidents in the chain
using the weighted sum:

N

N acc = i · Π i . (6)

i =0

Our purpose is to evaluate the functionality of the CCA system depending on the cur-
rent penetration rate of this technology. So that, we have to solve the model assuming