# ELDP: Extended Link Duration Prediction Model for Vehicular Networks

Authors: Xiufeng Wang; Chunmeng Wang; Gang Cui; Qing Yang; Xuehai Zhang
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

Link duration between two vehicles is considered an important quality of service metric in designing a network protocol for vehicular networks. There exist many works that study the probability density functions of link duration in a vehicular network given various vehicle mobility models, for example, the random waypoint model. None of them, however, provides a practical solution to estimating the link duration between two vehicles on the road. This is in part because link duration between vehicles is affected by many factors including the distance between vehicles, their turning directions at intersections, and the impact of traffic lights. Considering these factors, we propose the extended link duration prediction (ELDP) model which allows a vehicle to accurately estimate how long it will be connected to another vehicle. The ELDP model does not assume that vehicles follow certain mobility models; instead, it assumes that a vehicle’s velocity follows the Normal distribution. We validate the ELDP model in both highway and city scenarios in simulations. Our detailed simulations illustrate that relative speed between vehicles plays a vital role in accurately predicting link duration in a vehicular network. On the other hand, we find that the turning directions of a vehicle at intersections have subtle impact on the prediction results.


---

## Body

## 1. Introduction

Vehicular ad hoc network (VANET), a special type of mobile ad hoc network (MANET), provides both intervehicle and vehicle-roadside communications via the dedicated short range communications (DSRC). Despite their similarity, VANETs differ from generic MANETs because vehicles’ movements are constrained by urban and/or highway road network topologies. VANETs are able to provide various services, for example, safety message dissemination [1, 2], entertainments [3], location based service [4], dynamic traffic management [5–7], social networking [8], and information recommendation between vehicles [9]. To realize such visionary networks, we proposed several multihop routing protocols for VANETs [10–13]. From the previous works, we realized that a VANET routing protocol’s performance is highly influenced by link duration between vehicles [14]. Specifically, it significantly affects the end-to-end delay, packet loss rate, and throughput of a routing protocol in VANETs.The importance of link duration, regarding network performance, was intensively studied in MANETs and wireless sensor networks [15, 16]. Simulation results [17] also confirmed that link duration is a critical factor in designing a routing protocol for VANETs. To model link duration in a VANET, however, only a few analytical models are presented [18–21]. A model for link duration between vehicles in one-dimensional highway scenarios is first proposed in [22]. More link duration models for city scenarios are then provided in [23–25]. In [26], we propose a link duration prediction (LDP) model that is suitable for both highway and city scenarios. In the above-mentioned works, however, the impact of vehicles turning at intersections is not adequately considered. Besides vehicle turnings, intervehicle distances, vehicle velocities, and traffic lights also affect link duration in a VANET. To obtain a deeper understanding about link duration in a VANET, we first analyze the relative velocities between vehicles. Simulation results reveal that the relative speed of two vehicles closely follows the Normal distribution. Therefore, we propose to use the distribution of relative speeds, instead of instantaneous ones, to estimate link durations between vehicles.We extend the LDP model [26] to the extended link duration prediction (ELDP) model that allows a vehicle to practically estimate link durations between itself and neighboring vehicles. The main instrument of this work is to approximate the distribution of relative speeds between vehicles. After the distribution parameters are estimated, the expected link duration information is computed. While estimating link durations, our model also considers the initial distances between vehicles, their turning directions (at intersections), and the impact of traffic lights. To filter outliers, the ELDP model uses the exponential moving average (EMA) method to process relative velocity samples. According to simulation results, a vehicle only needs the latest five relative speed samples to get an accurate estimation.There are four major contributions of this paper. First, we propose the ELDP model which provides a way for a vehicle to predict, in real time, the link durations between itself and nearby vehicles. Second, we implement the model so that a vehicle can automatically collect velocity samples and accurately estimate the relative velocity distribution. Third, the ELDP model considers the impact of a vehicle’s turning decisions at intersections. Forth, we validate the ELDP model and evaluate its performance in simulations. Results show that ELDP can accurately predict the link duration in a VANET.The rest of the paper is organized as follows. Section2 summaries the related work. The ELDP model is introduced in Section 3 along with the method of accurately estimating the parameters of relative velocity distributions. In Section 4, we validate our model and evaluate its performance in both highway and city scenarios. We draw conclusions in Section 5.


## 2. Related Work

Link duration refers to the time interval during which two nodes are connected in a wireless network. Link duration between nodes in a MANET is determined by many factors, for example, channel conditions, distances, and interference levels. These information keep changing in a MANET, due to time-varying radio environments and node mobility. Wu et al. in [27] investigate the impact of node mobility on link duration in a MANET and develop an analytical framework to model link duration. This model is used to analyze both point-to-point and multipoint link durations. The model is then validated in simulations where node mobility follows the random waypoint mobility model [28], random walk model [29], reference point group mobility [30], and reference velocity group mobility model [31]. Unfortunately, none of these mobility models is applicable in VANETs.Although various mobility models have different impacts on link duration analysis, previous works [32, 33] also show that the link duration in a MANET can be effectively approximated using an exponential distribution. In [18, 19], it is found that an exponential distribution is a good approximation of the link duration in VANETs. However, [20] presents a different result that the probability density function (pdf) of link duration in a VANET is close to the log-Normal function. Yan and Olariu [21] also show that the link in VANETs is a log-Normal function given the following two assumptions: (1) the pdf of intervehicle distance is a log-Normal function and (2) a vehicle’s velocity is deterministic.Because link duration is so important in a MANET, some research works focus on predicting the link duration in a MANET. Although the random waypoint model [28] is widely used, it is clear that different mobility models have different impacts on the link stability in a MANET [34]. For example, Hua and Haas study several path-selection algorithms with different mobility models [35]; however, the algorithms cannot be used to predict link duration in a MANET. Haas and Hua in [36] propose a mobile-projected trajectory algorithm to estimate the residual link lifetime (RLL) between two nodes in a MANET. In [37], Korsnes et al. consider the link age information, that is, how long a link has been up, in estimating the RLL of a link. Then, Hua and Haas propose another RLL-prediction algorithm in [38], based on the Kalman filter approach. All the above-mentioned link lifetime prediction methods cannot be used in VANETs because vehicle movements do not follow any existing mobility models.In [18–21], the pdf of link duration in a VANET is analyzed. Shelly and Babu in [18] study link duration in a VANET by assuming a free-flow traffic state. Nekovee studies the pdf of link duration in a VANET by assuming a constant distance between vehicles and ignoring the impact of vehicle mobility [39]. Later on, he extends the work by considering that a vehicle’s velocity follows the Normal distribution [40]. In [41], an analytical framework for single-hop link duration in a VANET is presented. In [42], it is found that link duration in a VANET can be affected by vehicle movements and channel randomness. Nevertheless, all the above analytical models are not applicable for VANETs in urban scenarios.In a two-dimensional urban scenario, Artimy et al. analyze the network connectivity of a VANET [24]. Based on the cellular automata model, Viriyasitavat et al. provide a comprehensive analytical framework for network connectivity in an urban VANET [23]. Factors such as traffic lights are considered in this model. The events of two consecutive vehicles encountering a traffic light are considered to be independent, which is however not true in reality. Considering intervehicle distances, vehicle speeds, turning ratios at intersections, and traffic lights, Hu et al. [25] propose a discrete Markov process-based model for link duration estimation. In [26], Wang et al. present the LDP model to estimate the link duration in VANETs, in both urban and highway scenarios. Factors such as relative speeds, traffic lights, and distances between vehicles are considered in the LDP model. One limitation of the LDP model is that it focuses on straight roads and cannot be applied in real-world VANETs. To the best of our knowledge, we propose the first model to practically predict the link duration between two vehicles in urban and highway VANETs.Besides analytic results, research works on VANET simulations are also important in the study of link duration. For example, the impact of a traffic light on a vehicle’s movements has been well studied in SUMO—Simulation of Urban Mobility. SUMO is a microscopic, inter- and multimodal, space-continuous, and time-discrete traffic flow simulator [43]. With the proposed Car-Driver model, vehicles in SUMO dynamically change their speeds based on the speed of the leading vehicle (s). That also means a collision-free traffic is simulated in SUMO [44]. Traffic lights in SUMO are modeled based on the junction-based right-of-way rules: that is, only the vehicles facing green signals are allowed to enter intersections. Since it was released in 2002, SUMO has evolved into a full-featured toolkit for vehicular traffic simulation and modeling. SUMO is widely used in studying vehicular communications, optimal route selections, dynamic navigations, and traffic light algorithms [45]. For example, SUMO is used to validate an image-based traffic light control algorithm in [46]. The algorithm in [46] processes images captured by the cameras installed in a road intersection; it then changes the traffic light’s signal based on the queue length of vehicles. Due to legal constraints, the proposed algorithm has to be first tested in simulations before it is applied in a real-world system.In 2012, SUMO was selected as the traffic simulator in the EU FP7 COLOMBO project that aims at delivering a reliable traffic management system for traffic surveillance and advanced traffic light control [47]. According to reports [48, 49], traffic lights play an important role in traffic modeling and traffic management. The importance about how traffic lights affect vehicle movements are completely studied in [48, 49]. For example, it is pointed out that simulation scenario (e.g., a single intersection, corridor, or network) and the road network (e.g., numbers of lanes) are important in modeling a vehicle’s behavior in front of a traffic light. Based on these findings, we propose to consider the impact of traffic lights in our link duration prediction model. The ELDP model complements existing research on traffic simulation because we consider not only the impact of vehicles turning at intersections but also the impact of traffic lights in the model.


## 3. ELDP Model

To accurately estimate how long two vehicles will be connected, a link duration prediction model has to address the following challenges. First, it needs to consider dealing with the impact of vehicles turning at intersections. Second, the model must accommodate the frequent changes in vehicle speeds. Third, the model must be able to handle the impact of traffic lights on the prediction of link durations. In this section, we will illustrate how to address these three technical challenges in detail.


### 3.1. Impact of Vehicles Turning at Intersections

As shown in Figure1(a), we use α to denote the angle from the positive x-axis to a vehicle’s moving direction. Given two vehicles in front of an intersection, we consider the location of one vehicle the origin and then construct a planar coordinate system, as shown in Figure 1(b). Since α
∈
[
0,2
π
], a vehicle can move in any directions in front of an intersection, for example, turning left/right, making a U-turn, and moving straightforward. We use vector v
→ to denote a vehicle’s velocity and v
=
|
v
→
| for the vehicle’s speed.Figure 1
A planar coordinate system for analyzing relative velocity.
(a)
Moving direction of a vehicle
(b)
Relative velocityTo understand link duration between two vehicles at an intersection, we denote their velocities asv
1
→ and v
2
→, respectively. These velocities can be written as (1)
v
1
→
=
v
1
cos
⁡
α
,
v
1
sin
⁡
α
,
v
2
→
=
v
2
cos
⁡
β
,
v
2
sin
⁡
β
.From Figure1(b), we can compute the relative velocity between these two vehicles as l
1
→
=
v
1
→
-
v
2
→: (2)
l
1
→
=
v
1
→
cos
⁡
α
-
v
2
→
cos
⁡
β
,
v
1
→
sin
⁡
α
-
v
2
→
sin
⁡
β
.If we denote B
=
(
v
1
→
cos
⁡
α
-
v
2
→
cos
⁡
β
) and A
=
(
v
1
→
sin
⁡
α
-
v
2
→
sin
⁡
β
), then l
1
→ becomes (
B
,
A
).If we consider the first vehicle (with velocityv
1
→) the reference point, then the other vehicle (with velocity v
2
→) can be considered as moving with a relative velocity (
v
1
→
-
v
2
→
). We are able to create a new coordinate system O
′, from the original O, as shown in Figure 2.Figure 2
A transformed coordinate system.Let us denote the locations of these two vehicles in the original coordinate system as(
x
1
,
y
1
) and (
x
2
,
y
2
). Then, the location of the second vehicle in O
′ will be (
x
2
-
x
1
,
y
2
-
y
1
). As shown in Figure 2, in the coordinate system O
′, we make a vector l
2
→ that is perpendicular to l
1
→. We assume that vectors l
1
→ and l
2
→ intersect at point E, and the distance from O
′ to vector l
1
→ is d
v. We assume that the initial distance between these two vehicles is d. When the vehicles move, this distance may increase or decrease until it is greater than the communication range r. At that time, we assume that the second vehicle moves to point D
0: that is, O
′
D
0
=
r. We are interested in the time interval during which the second vehicle moves from D to D
0. Such time interval will be the link duration of these two vehicles.Becausel
1
→ is perpendicular to l
2
→ and the coordinate of D is (
x
2
-
x
1
,
y
2
-
y
1
), we can compute E’s coordinate as (3)
E
x
=
A
2
x
2
-
x
1
-
A
B
y
2
-
y
1
A
2
+
B
2
,
E
y
=
A
B
x
2
-
x
1
-
B
2
y
2
-
y
1
A
2
+
B
2
.Therefore, the distance from O
′ to l
1
→ is (4)
d
v
=
B
y
2
-
y
1
-
A
x
2
-
x
1
B
2
+
A
2
.In the example shown in Figure2, the distance from D to D
0 will be D
D
0
=
E
D
0
-
E
D, where E
D
0
=
r
2
-
d
v
2 and E
D
=
d
2
-
d
v
2. The value of d is obtained via vehicles sharing their locations to each other. d
v is computed from (4). The value of D
D
0 actually determines the link duration between these two vehicles, so we need to discuss how to compute D
D
0 in detail.In the first case, we haveB
>
0 and A
>
0. This case is illustrated in Figure 3 where there are two possible subcases: (1) D is before E and (2) D is behind E. If the x-coordinate of D is greater than that of E, as shown in Figure 3(a), we have D
D
0
=
E
D
0
-
E
D. Otherwise, as shown in Figure 3(b), we have D
D
0
=
E
D
0
+
E
D.Figure 3
Computation of relative moving distanceD
D
0 when B
>
0 and A
>
0.
(a)
(b)In the second case, we haveB
<
0 and A
>
0, which is illustrated in Figure 4. If the x-coordinate of D is smaller than that of E, as shown in Figure 4(a), we have D
D
0
=
E
D
0
-
E
D. Otherwise, as shown in Figure 4(b), we have D
D
0
=
E
D
0
+
E
D.Figure 4
Computation of relative moving distanceD
D
0 when B
<
0 and A
>
0.
(a)
(b)The third case is illustrated in Figure5, where we have B
<
0 and A
<
0. If the x-coordinate of D is smaller than that of E, as shown in Figure 5(a), we have D
D
0
=
E
D
0
-
E
D. Otherwise, as shown in Figure 5(b), we have D
D
0
=
E
D
0
+
E
D.Figure 5
Computation of relative moving distanceD
D
0 when B
<
0 and A
<
0.
(a)
(b)In the last case, we haveB
>
0 and A
<
0 which is illustrated in Figure 6. If the x-coordinate of D is greater than that of E, as shown in Figure 6(a), we have D
D
0
=
E
D
0
-
E
D. Otherwise, as shown in Figure 6(b), we have D
D
0
=
E
D
0
+
E
D.Figure 6
Computation of relative moving distanceD
D
0 when B
>
0 and A
<
0.
(a)
(b)In summary, whenB
>
0, no matter A
>
0 or not, the computations of D
D
0 are the same. This also applies when B
<
0, that is, how to compute D
D
0 does not change given A
>
0 or A
<
0.


### 3.2. Distribution of Relative Speed

Previous works [18, 40, 50] indicate that the speed of a vehicle generally follows Normal distribution. Let us assume that a vehicle’s speed v follows Normal distribution v
~
N
(
μ
,
σ
2
). Then, the pdf of this random variable v can be written as (5)
f
v
=
1
2
π
σ
e
-
v
-
μ
2
/
2
σ
2
. We proved that the relative speed of two vehicles on a straight road follows Normal distribution as well [26].Given two vehicles, we denote their velocities asv
1
→
=
(
v
1
cos
⁡
α
,
v
1
sin
⁡
α
) and v
2
→
=
(
v
2
cos
⁡
β
,
v
2
sin
⁡
β
), respectively. Then the relative velocity between them is v
12
→
=
(
v
1
→
-
v
2
→
)
=
(
v
1
cos
⁡
α
-
v
2
cos
⁡
β
,
v
1
sin
⁡
α
-
v
2
sin
⁡
β
). Since v
1 and v
2 follow Normal distribution, v
12
=
|
v
12
→
| also follows Normal distribution, where v
12 denotes the relative speed between these two vehicles. The pdf of v
12 can be written as(6)
f
v
12
=
1
2
π
σ
e
-
v
12
-
μ
2
/
2
σ
2
,where μ and σ
2 denote the mean and variance of the relative speed v
12. To estimate these parameters, each vehicle continuously measures its velocity and computes the relative speeds between itself and nearby vehicles. The average relative speed can be estimated as (7)
μ
^
=
1
n
∑
r
=
1
n
v
r
→
, where μ
^ is the estimated μ and |
v
r
→
| are instantaneous relative speeds. μ
^ is also called the sample mean as it is the arithmetic average of all samples. The variance of relative speed can be estimated as (8)
s
2
=
n
n
-
1
σ
^
2
=
1
n
-
1
∑
r
=
1
n
v
r
-
μ
^
2
,where σ
^
2 is called the sample variance. Details of the estimation process could be found in ldp.


### 3.3. Principle of the ELDP Model

Based on the parameters of relative speed distribution andD
D
0, the link duration between any two connected vehicles could be computed. We first introduce the prediction model without considering traffic lights. How to compute link duration with traffic lights will be provided later.We consider the link duration between two vehicles a random variableT. The distribution of T depends on (1) relative speed v, (2) initial distance d between them, and (3) their relative moving direction. Because these factors keep changing when these two vehicles move, the ELDP model needs to adaptively adjust prediction rules in order to compute an accurate result.We first give the cumulative density function (CDF) ofT as follows: (9)
P
T
≤
t
=
P
D
D
0
v
≤
t
=
1
-
P
v
≤
D
D
0
t
,where v is relative speed and D
D
0 is the relative traveling distance between these two vehicles. Differentiating the above equation by t, the pdf of T becomes (10)
f
t
=
D
D
0
t
2
f
v
D
D
0
t
.As the relative speed v follows Normal distribution, the equation can be rewritten as (11)
f
t
=
D
D
0
t
2
2
π
σ
e
-
D
D
0
/
t
-
μ
2
/
2
σ
2
,where μ and σ
2 are the mean and variance of relative speed. Therefore, the expected link duration could be computed as follows: (12)
E
T
=
∫
0
∞
t
f
t
d
t
.Becausev follows Normal distribution, we know that about 99% samples of v fall within the range [μ
-
4
σ, μ
+
4
σ]. Therefore, we can define the minimum and maximum possible relative speeds as μ
-
4
σ and μ
+
4
σ, respectively. The integration interval in (12) can be reduced from [
0
,
∞
) to [
D
D
0
/
(
μ
+
4
σ
)
,
D
D
0
/
(
μ
-
4
σ
)
]. The expected link duration is calculated as (13)
E
T
=
∫
D
D
0
/
μ
+
4
σ
D
D
0
/
μ
-
4
σ
D
D
0
t
2
π
σ
e
-
D
D
0
/
t
-
μ
2
/
2
σ
2
d
t
.The above equation can be used to predict the link duration of two connected vehicles given their relative speed distribution and initial distance. So far, the model only considers the case where there is no traffic light at intersections. It is important to investigate how link duration prediction is affected if vehicles change their moving directions at intersections.In our previous work [26], we addressed this issue by assuming that the events of two consecutive vehicles encountering traffic lights are dependent. In other words, which traffic signal the second vehicle faces depends upon the traffic signal that the first vehicle encounters. This phenomenon was observed and analyzed in [25, 26]. To address this issue, we first compute the probabilities where (1) both vehicles face red signals, (2) the first vehicle faces red signal and the second vehicle faces green signal, (3) both vehicles face green signals, and (4) the first vehicle faces green signal and the second vehicle faces red signal. In each case, we adjust the parameters D
D
0, μ, and σ in (13), accordingly. Finally, the expected link duration of two connected vehicles is computed.


### 3.4. Link Duration Prediction Algorithm

Based on the ELDP model, a vehicle could predict the link durations between itself and any other vehicles. We assume that vehiclesn
i and n
j are connected at a certain time. Based on their relative speed distribution and D
D
0, the time interval during which they are connected can be computed.To reduce prediction error, a sliding window method is adopted on each vehicle: that is, a vehicle only saves its most recent5 velocity samples. It then computes its relative speeds with regard to other vehicles. Because vehicles n
i and n
j are connected, their velocity samples can be shared with each other in their beacon messages. For example, if n
i receives n
j’s 5 most recent velocity samples, it computes their relative velocities as v
i
j
1
→
,
v
i
j
2
→
,
…
,
v
i
j
5
→. Then, the distribution parameters of |
v
i
j
→
| between vehicles n
i and n
j are estimated. In other words, the parameters μ
i
j, σ
i
j of relative speed can be estimated. If vehicles include their locations in beacon messages, relative distance d
i
j between n
i and n
j can be computed, so is D
D
0. Substituting the estimated μ
i
j, σ
i
j, and D
D
0 for μ, σ, and D
D
0 in (13), the expected link duration between n
i and n
j is computed.Furthermore, to address the sudden change of a vehicle’s velocity (due to breaking, overtaking, or turning), the relative speeds need to be preprocessed by the EMA (Exponential Moving Average) method as follows:(14)
V
t
=
α
·
v
t
+
1
-
α
·
V
t
-
1
,where V
t is the processed relative speed at time t and v
t is instantaneous relative speed at time t. Since V
t is a linear combination of relative speed samples v
0 to v
t, and v
0 to v
t follow Normal distribution, V
t also follows Normal distribution. In other words, the proposed model is still applicable on the relative speed samples processed by EMA.The algorithm of computing the expected link duration between vehiclesn
i and n
j is shown in Figure 7. In the flowchart, we define x
D
=
x
i
-
x
j, and x
E
=
(
A
2
x
i
-
x
j
-
A
B
y
i
-
y
j
)
/
A
2
+
B
2. The algorithm starts when two vehicles are connected: that is, each vehicle receives a beacon message from the other. The algorithm first checks if B
>
0, where B
=
(
v
1
→
cos
⁡
α
-
v
2
→
cos
⁡
β
). If B
>
0, it compares x
D and x
E which indicates the relative location between the two vehicles. If x
D
>
x
E, then D
D
0 is E
D
0
-
E
D; otherwise, D
D
0
=
E
D
0
+
E
D. If B
<
0, the algorithm also needs to check whether x
D
≥
x
E. If that is true, D
D
0
=
E
D
0
-
E
D; otherwise, D
D
0
=
E
D
0
+
E
D. After collecting enough samples, the relative speed distribution could be estimated, that is, the parameters of u and σ
2 of relative speed between these two vehicles are known. Finally, the expected link duration between them is computed. The algorithm will stop when these two vehicles are disconnected, which could be identified when the relative distance between them is larger than the communication range, or no beacon message is received for a certain period of time.Figure 7
Flowchart of predicting link duration between vehiclesn
i and n
j.


## 3.1. Impact of Vehicles Turning at Intersections

As shown in Figure1(a), we use α to denote the angle from the positive x-axis to a vehicle’s moving direction. Given two vehicles in front of an intersection, we consider the location of one vehicle the origin and then construct a planar coordinate system, as shown in Figure 1(b). Since α
∈
[
0,2
π
], a vehicle can move in any directions in front of an intersection, for example, turning left/right, making a U-turn, and moving straightforward. We use vector v
→ to denote a vehicle’s velocity and v
=
|
v
→
| for the vehicle’s speed.Figure 1
A planar coordinate system for analyzing relative velocity.
(a)
Moving direction of a vehicle
(b)
Relative velocityTo understand link duration between two vehicles at an intersection, we denote their velocities asv
1
→ and v
2
→, respectively. These velocities can be written as (1)
v
1
→
=
v
1
cos
⁡
α
,
v
1
sin
⁡
α
,
v
2
→
=
v
2
cos
⁡
β
,
v
2
sin
⁡
β
.From Figure1(b), we can compute the relative velocity between these two vehicles as l
1
→
=
v
1
→
-
v
2
→: (2)
l
1
→
=
v
1
→
cos
⁡
α
-
v
2
→
cos
⁡
β
,
v
1
→
sin
⁡
α
-
v
2
→
sin
⁡
β
.If we denote B
=
(
v
1
→
cos
⁡
α
-
v
2
→
cos
⁡
β
) and A
=
(
v
1
→
sin
⁡
α
-
v
2
→
sin
⁡
β
), then l
1
→ becomes (
B
,
A
).If we consider the first vehicle (with velocityv
1
→) the reference point, then the other vehicle (with velocity v
2
→) can be considered as moving with a relative velocity (
v
1
→
-
v
2
→
). We are able to create a new coordinate system O
′, from the original O, as shown in Figure 2.Figure 2
A transformed coordinate system.Let us denote the locations of these two vehicles in the original coordinate system as(
x
1
,
y
1
) and (
x
2
,
y
2
). Then, the location of the second vehicle in O
′ will be (
x
2
-
x
1
,
y
2
-
y
1
). As shown in Figure 2, in the coordinate system O
′, we make a vector l
2
→ that is perpendicular to l
1
→. We assume that vectors l
1
→ and l
2
→ intersect at point E, and the distance from O
′ to vector l
1
→ is d
v. We assume that the initial distance between these two vehicles is d. When the vehicles move, this distance may increase or decrease until it is greater than the communication range r. At that time, we assume that the second vehicle moves to point D
0: that is, O
′
D
0
=
r. We are interested in the time interval during which the second vehicle moves from D to D
0. Such time interval will be the link duration of these two vehicles.Becausel
1
→ is perpendicular to l
2
→ and the coordinate of D is (
x
2
-
x
1
,
y
2
-
y
1
), we can compute E’s coordinate as (3)
E
x
=
A
2
x
2
-
x
1
-
A
B
y
2
-
y
1
A
2
+
B
2
,
E
y
=
A
B
x
2
-
x
1
-
B
2
y
2
-
y
1
A
2
+
B
2
.Therefore, the distance from O
′ to l
1
→ is (4)
d
v
=
B
y
2
-
y
1
-
A
x
2
-
x
1
B
2
+
A
2
.In the example shown in Figure2, the distance from D to D
0 will be D
D
0
=
E
D
0
-
E
D, where E
D
0
=
r
2
-
d
v
2 and E
D
=
d
2
-
d
v
2. The value of d is obtained via vehicles sharing their locations to each other. d
v is computed from (4). The value of D
D
0 actually determines the link duration between these two vehicles, so we need to discuss how to compute D
D
0 in detail.In the first case, we haveB
>
0 and A
>
0. This case is illustrated in Figure 3 where there are two possible subcases: (1) D is before E and (2) D is behind E. If the x-coordinate of D is greater than that of E, as shown in Figure 3(a), we have D
D
0
=
E
D
0
-
E
D. Otherwise, as shown in Figure 3(b), we have D
D
0
=
E
D
0
+
E
D.Figure 3
Computation of relative moving distanceD
D
0 when B
>
0 and A
>
0.
(a)
(b)In the second case, we haveB
<
0 and A
>
0, which is illustrated in Figure 4. If the x-coordinate of D is smaller than that of E, as shown in Figure 4(a), we have D
D
0
=
E
D
0
-
E
D. Otherwise, as shown in Figure 4(b), we have D
D
0
=
E
D
0
+
E
D.Figure 4
Computation of relative moving distanceD
D
0 when B
<
0 and A
>
0.
(a)
(b)The third case is illustrated in Figure5, where we have B
<
0 and A
<
0. If the x-coordinate of D is smaller than that of E, as shown in Figure 5(a), we have D
D
0
=
E
D
0
-
E
D. Otherwise, as shown in Figure 5(b), we have D
D
0
=
E
D
0
+
E
D.Figure 5
Computation of relative moving distanceD
D
0 when B
<
0 and A
<
0.
(a)
(b)In the last case, we haveB
>
0 and A
<
0 which is illustrated in Figure 6. If the x-coordinate of D is greater than that of E, as shown in Figure 6(a), we have D
D
0
=
E
D
0
-
E
D. Otherwise, as shown in Figure 6(b), we have D
D
0
=
E
D
0
+
E
D.Figure 6
Computation of relative moving distanceD
D
0 when B
>
0 and A
<
0.
(a)
(b)In summary, whenB
>
0, no matter A
>
0 or not, the computations of D
D
0 are the same. This also applies when B
<
0, that is, how to compute D
D
0 does not change given A
>
0 or A
<
0.


## 3.2. Distribution of Relative Speed

Previous works [18, 40, 50] indicate that the speed of a vehicle generally follows Normal distribution. Let us assume that a vehicle’s speed v follows Normal distribution v
~
N
(
μ
,
σ
2
). Then, the pdf of this random variable v can be written as (5)
f
v
=
1
2
π
σ
e
-
v
-
μ
2
/
2
σ
2
. We proved that the relative speed of two vehicles on a straight road follows Normal distribution as well [26].Given two vehicles, we denote their velocities asv
1
→
=
(
v
1
cos
⁡
α
,
v
1
sin
⁡
α
) and v
2
→
=
(
v
2
cos
⁡
β
,
v
2
sin
⁡
β
), respectively. Then the relative velocity between them is v
12
→
=
(
v
1
→
-
v
2
→
)
=
(
v
1
cos
⁡
α
-
v
2
cos
⁡
β
,
v
1
sin
⁡
α
-
v
2
sin
⁡
β
). Since v
1 and v
2 follow Normal distribution, v
12
=
|
v
12
→
| also follows Normal distribution, where v
12 denotes the relative speed between these two vehicles. The pdf of v
12 can be written as(6)
f
v
12
=
1
2
π
σ
e
-
v
12
-
μ
2
/
2
σ
2
,where μ and σ
2 denote the mean and variance of the relative speed v
12. To estimate these parameters, each vehicle continuously measures its velocity and computes the relative speeds between itself and nearby vehicles. The average relative speed can be estimated as (7)
μ
^
=
1
n
∑
r
=
1
n
v
r
→
, where μ
^ is the estimated μ and |
v
r
→
| are instantaneous relative speeds. μ
^ is also called the sample mean as it is the arithmetic average of all samples. The variance of relative speed can be estimated as (8)
s
2
=
n
n
-
1
σ
^
2
=
1
n
-
1
∑
r
=
1
n
v
r
-
μ
^
2
,where σ
^
2 is called the sample variance. Details of the estimation process could be found in ldp.


## 3.3. Principle of the ELDP Model

Based on the parameters of relative speed distribution andD
D
0, the link duration between any two connected vehicles could be computed. We first introduce the prediction model without considering traffic lights. How to compute link duration with traffic lights will be provided later.We consider the link duration between two vehicles a random variableT. The distribution of T depends on (1) relative speed v, (2) initial distance d between them, and (3) their relative moving direction. Because these factors keep changing when these two vehicles move, the ELDP model needs to adaptively adjust prediction rules in order to compute an accurate result.We first give the cumulative density function (CDF) ofT as follows: (9)
P
T
≤
t
=
P
D
D
0
v
≤
t
=
1
-
P
v
≤
D
D
0
t
,where v is relative speed and D
D
0 is the relative traveling distance between these two vehicles. Differentiating the above equation by t, the pdf of T becomes (10)
f
t
=
D
D
0
t
2
f
v
D
D
0
t
.As the relative speed v follows Normal distribution, the equation can be rewritten as (11)
f
t
=
D
D
0
t
2
2
π
σ
e
-
D
D
0
/
t
-
μ
2
/
2
σ
2
,where μ and σ
2 are the mean and variance of relative speed. Therefore, the expected link duration could be computed as follows: (12)
E
T
=
∫
0
∞
t
f
t
d
t
.Becausev follows Normal distribution, we know that about 99% samples of v fall within the range [μ
-
4
σ, μ
+
4
σ]. Therefore, we can define the minimum and maximum possible relative speeds as μ
-
4
σ and μ
+
4
σ, respectively. The integration interval in (12) can be reduced from [
0
,
∞
) to [
D
D
0
/
(
μ
+
4
σ
)
,
D
D
0
/
(
μ
-
4
σ
)
]. The expected link duration is calculated as (13)
E
T
=
∫
D
D
0
/
μ
+
4
σ
D
D
0
/
μ
-
4
σ
D
D
0
t
2
π
σ
e
-
D
D
0
/
t
-
μ
2
/
2
σ
2
d
t
.The above equation can be used to predict the link duration of two connected vehicles given their relative speed distribution and initial distance. So far, the model only considers the case where there is no traffic light at intersections. It is important to investigate how link duration prediction is affected if vehicles change their moving directions at intersections.In our previous work [26], we addressed this issue by assuming that the events of two consecutive vehicles encountering traffic lights are dependent. In other words, which traffic signal the second vehicle faces depends upon the traffic signal that the first vehicle encounters. This phenomenon was observed and analyzed in [25, 26]. To address this issue, we first compute the probabilities where (1) both vehicles face red signals, (2) the first vehicle faces red signal and the second vehicle faces green signal, (3) both vehicles face green signals, and (4) the first vehicle faces green signal and the second vehicle faces red signal. In each case, we adjust the parameters D
D
0, μ, and σ in (13), accordingly. Finally, the expected link duration of two connected vehicles is computed.


## 3.4. Link Duration Prediction Algorithm

Based on the ELDP model, a vehicle could predict the link durations between itself and any other vehicles. We assume that vehiclesn
i and n
j are connected at a certain time. Based on their relative speed distribution and D
D
0, the time interval during which they are connected can be computed.To reduce prediction error, a sliding window method is adopted on each vehicle: that is, a vehicle only saves its most recent5 velocity samples. It then computes its relative speeds with regard to other vehicles. Because vehicles n
i and n
j are connected, their velocity samples can be shared with each other in their beacon messages. For example, if n
i receives n
j’s 5 most recent velocity samples, it computes their relative velocities as v
i
j
1
→
,
v
i
j
2
→
,
…
,
v
i
j
5
→. Then, the distribution parameters of |
v
i
j
→
| between vehicles n
i and n
j are estimated. In other words, the parameters μ
i
j, σ
i
j of relative speed can be estimated. If vehicles include their locations in beacon messages, relative distance d
i
j between n
i and n
j can be computed, so is D
D
0. Substituting the estimated μ
i
j, σ
i
j, and D
D
0 for μ, σ, and D
D
0 in (13), the expected link duration between n
i and n
j is computed.Furthermore, to address the sudden change of a vehicle’s velocity (due to breaking, overtaking, or turning), the relative speeds need to be preprocessed by the EMA (Exponential Moving Average) method as follows:(14)
V
t
=
α
·
v
t
+
1
-
α
·
V
t
-
1
,where V
t is the processed relative speed at time t and v
t is instantaneous relative speed at time t. Since V
t is a linear combination of relative speed samples v
0 to v
t, and v
0 to v
t follow Normal distribution, V
t also follows Normal distribution. In other words, the proposed model is still applicable on the relative speed samples processed by EMA.The algorithm of computing the expected link duration between vehiclesn
i and n
j is shown in Figure 7. In the flowchart, we define x
D
=
x
i
-
x
j, and x
E
=
(
A
2
x
i
-
x
j
-
A
B
y
i
-
y
j
)
/
A
2
+
B
2. The algorithm starts when two vehicles are connected: that is, each vehicle receives a beacon message from the other. The algorithm first checks if B
>
0, where B
=
(
v
1
→
cos
⁡
α
-
v
2
→
cos
⁡
β
). If B
>
0, it compares x
D and x
E which indicates the relative location between the two vehicles. If x
D
>
x
E, then D
D
0 is E
D
0
-
E
D; otherwise, D
D
0
=
E
D
0
+
E
D. If B
<
0, the algorithm also needs to check whether x
D
≥
x
E. If that is true, D
D
0
=
E
D
0
-
E
D; otherwise, D
D
0
=
E
D
0
+
E
D. After collecting enough samples, the relative speed distribution could be estimated, that is, the parameters of u and σ
2 of relative speed between these two vehicles are known. Finally, the expected link duration between them is computed. The algorithm will stop when these two vehicles are disconnected, which could be identified when the relative distance between them is larger than the communication range, or no beacon message is received for a certain period of time.Figure 7
Flowchart of predicting link duration between vehiclesn
i and n
j.


## 4. Performance Analysis

Because vehicle mobility significantly affects ELDP’s accuracy, we simulate vehicle movements via the VISSIM simulator [51]. This simulator is widely used to simulate realistic automotive motions at a microscopic level. VISSIM provides a toolkit for transportation simulations, a user-friendly graphic user interface. It is not only able to simulate large-scale vehicular networks, but also supports traffic lights, lane changes, and speed regulations.In the simulations, we consider both highway and city scenarios to evaluate ELDP’s performance. To evaluate the performance of ELDP, we focus on the cases where vehicles encounter intersections and make turns in both highway and city scenarios. The cases where vehicles move without changing directions were completely evaluated in our previous work [26]. In the simulations, we note that the relative direction of two vehicles significantly affects the ELDP’s performance: that is, when two vehicles move towards (away from) each other, the relative distance between them keeps decreasing (increasing), which will change the rules in ELDP in predicting link durations.


### 4.1. Highway Scenario

The simulation configuration parameters for highway scenarios are listed in Table1. We first analyze many trace files generated by the VISSIM and divide vehicles into two groups. In the first group, there are two vehicles that connect to each other and move in the same direction. In this group, one vehicle turns and changes its moving direction from 0 to α
<
π
/
2. In the second group, two connected vehicles move in opposite directions and one vehicle makes turns. At every time stamp, we compute the relative speed, relative angle, relative distance between these two vehicles, and their relative traveling distance D
D
0. These values are then fed into the ELDP model to estimate link durations. For each pair of connected vehicles, the ELDP model is applied several times to estimate their link durations. From the trace files, we identify the time instances when two vehicles connect and disconnect, so the time differences are considered the ground truth.Table 1
Simulation setup parameters in highway scenarios.
Length
6000 m
Width
3.5 m
Traffic flow
500 vehicles/hr
Velocity
58–110 km/hr
Number of lanes per direction
2
Communication range
300 m
Simulation time
1000 s


#### 4.1.1. Moving in the Same Direction

We first study the ELDP’s performance on two vehicles moving in the same direction. We are interested in the cases where one vehicle turns and the other does not. We randomly select a pair of vehicles and plot the mean of their relative speed in Figure8(a). As we can see, the two vehicles are connected at the 1
st second. The mean of their relative speed keeps unchanged until 80
th second when one vehicle changes its moving direction. After that, the relative speed keeps increasing and the variation of relative speed increases as well. It can be seen in Figure 8(b) that the standard deviation of relative speed is very large after 80
th second.Figure 8
One vehicle turns and the other one keeps moving in a highway scenario. After the turning, two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)We compare the predicted link durations and the ground truth in Figure8(c). We can see that the estimated results from ELDP match the ground truth very well, indicating ELDP is an accurate model. To obtain a deeper understanding of the ELDP’s performance, we further plot the CDF of prediction errors in Figure 8(d). We also randomly select 10 pairs of vehicles and plot the mean prediction errors in Figure 8(e). From Figure 8(d), we find more than 85
% prediction results containing errors less than 10
%. Figure 8(e) reveals that most prediction errors are less than 5
%.


#### 4.1.2. Moving in Opposite Directions

We then look at the cases where two vehicles move in opposite directions. Similarly, we only select the cases where one vehicle turns and the other does not. We randomly select a pair of vehicles and plot the mean and standard deviation of their relative speed in Figures9(a) and 9(b), respectively. From the figures, we find that the relative speed keeps decreasing but decreases faster after the 7
s. This is because, before 7
s, the two vehicles move (away from each other) in opposite directions. After 7
s, one vehicle turns and suddenly their relative speed decreases faster. After 16
s, these two vehicles are disconnected.Figure 9
One vehicle turns and the other one keeps moving in a highway scenario. After the turning, two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)We further plot the predicted link durations and the ground truth in Figure9(c). We can see that the estimated results from ELDP are very close to the ground truth. We also plot the CDF of prediction errors and the mean prediction errors of 10 randomly selected pairs of vehicles in Figures 9(d) and 9(e), respectively. From Figure 9(d), we find more than 88
% prediction results containing errors less than 4
%. Figure 9(e) indicates that the error of 90
% prediction results are less than 4
%.Overall, simulation results illustrate that ELDP works better for vehicles moving in opposite directions. In addition, a vehicle making turns on highways does not drastically affect ELDP’s performance. We conclude that the turning angle of a vehicle is not an influential factor in ELDP.


### 4.2. City Scenario

It is challenging to accurately predict the link duration between two vehicles in a city scenario. This is mainly because it is difficult, if not impossible, to predict what traffic signal a vehicle will face in front of an intersection. Besides, vehicles can make turns at intersections, which makes the link duration prediction a nontrivial problem. To realistically simulate vehicle movements in city scenarios, we configure the VISSIM simulator based on the parameters given in Table2.Table 2
Simulation setup parameters in city scenarios.
Length
10000 m
Width
3.5 m
Traffic flow
300 vehicles/hr
Velocity
0–60 km/hr
Number of lanes per direction
3
Communication range
300 m
Green signal
30 s
Red signal
67 m
Left green signal
20 s
Left red signal
77 s
Yellow signal
3 s
Simulation time
1000 s
Size of intersection
50 m × 50 mBased on the trajectories of vehicles at an intersection, we categorize connected vehicles into three groups: (1) one vehicle moves straightforward and the other makes a left/right turn, (2) one vehicle turns left and the other turns right, and (3) both turn to the same direction. After turns, the two vehicles may move in the same direction, in opposite directions, or with a relative angle ofα.


#### 4.2.1. Moving Forward versus Making Turns

Here, we are interested in pairs of connected vehicles: one moves straightforward and the other turns to left/right. We divide these vehicles into three groups. After turns, (1) both vehicles move in the same direction, (2) both move in opposite directions, and (3) the relative moving direction of them isα
=
π
/
2.Moving in the Same Direction.For the first case where two vehicles move in the same direction, we randomly pick a pair of vehicles and plot the predicted and real link durations in Figure 10(c). We can see that these two vehicles connect for about 30
s, and the error of predicted link durations decreases as the time increases. We also find that the predicted errors before 13
s are large. This is because the first vehicle faces a red signal at an intersection at time 13
s, and the other vehicle makes a turn. Therefore, the relative speeds within [
0
s
,
13
s
] change drastically. After 13
s, because we accurately predict relative speeds, the predicted errors reduce. Before the intersection, the second vehicle moves toward the first one, so their relative distance decreases. After that, the rules of calculating D
D
0 change as the values of B and A are different.Figure 10
One vehicle turns and the other one keeps moving in a city scenario. After the turning, two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)To understand the fluctuation in data in Figure10(c), we further plot in Figure 10(b) how relative speed changes over time. This figure indicates that, during [
10
s
,
17
s
], the first vehicle stops in front of an intersection and the second one turns. This can be confirmed in Figure 10(a) that shows the mean of relative speeds. During [
8
s
,
21
s
], the mean of relative speeds decreases linearly because the first vehicle stops in front of the intersection. Except for this period, the fluctuation of relative speeds is very small, leading to a small prediction error. From the above analysis, we conclude that stable relative speeds yield accurate prediction results.We also plot the CDF of error and the mean errors of 10 randomly selected pairs of vehicles in Figures10(d) and 10(e). In Figure 10(d), more than 80
% prediction results contain errors less than 10
%. Figure 10(e) illustrates that the errors of 80
% prediction results are less than 10
%.Moving in Opposite Directions. For this case, vehicles move in opposite directions after one vehicle turns at an intersection. In Figure 11(a), we provide the predicted and actual link durations of a pair of randomly selected vehicles. The first vehicle faces a red signal at 12
s; it then stops at the intersection. Around this time, we can see that its velocity varies a lot. When the second vehicle turns at the intersection, due to the impact of the traffic light, the relative distance and relative speed change drastically. The predicted errors increase when vehicles are around the intersection. The average relative speed and its variation are shown in Figures 11(a) and 11(b). From Figure 11(b), we see that the mean of relative speed changes drastically during [
0
s
,
12
s
) because the first vehicle stops in front of the intersection. During [
12
s
,
31
s
), however, the relative speed increases gradually because the first vehicle starts to move.Figure 11
One vehicle turns and the other one keeps moving in a city scenario. After the turning, two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)Similarly, we plot Figures11(d) and 11(e). From these figures, we find more than 72
% prediction results containing errors less than 10
%, and the errors of 90
% prediction results are less than 10
%.Moving Directions with a Certain Angle. For the last case, we are interested in two vehicles moving with a relative angle α, after one vehicle turns at an intersection. We first plot the mean and standard deviation of their relative speed in Figures 12(a) and 12(b). The two figures help us to understand what happened when they are approaching the intersection. We plot the predicted and real link durations in Figure 12(c). We can see that the predicted errors are very small no matter whether a vehicle turns at the intersection or not. We also plot the prediction error CDF and the mean errors of 10 randomly selected pairs of vehicles in Figures 12(d) and 12(e).Figure 12
One vehicle turns and the other one keeps moving in a city scenario. After the turning, the relative moving direction of them is denoted asα.
(a)
(b)
(c)
(d)
(e)In summary, for a pair of vehicles where one moves straightforward and the other turns at an intersection, ELDP can accurately (with an error<
10
%) predicte their link durations.


#### 4.2.2. Making Different Turns

For those connected vehicles that make different turns at an intersection, we divide them into three groups. After they turn at an intersection, they move (1) in the same direction, (2) in opposite directions, and (3) withα
=
π
/
2 relative direction.For the first case, we randomly select a pair of vehicles and plot the mean of their relative speed in Figure13(a), the standard deviation of their relative speed in Figure 13(b), and the predicted and real link durations in Figure 13(c). We find that, even with a large fluctuation in the relative speeds, the predicted error is small and acceptable. We plot the prediction error CDF of this pair of vehicles and the mean errors of 10 randomly selected pairs of vehicles in Figures 13(d) and 13(e). We find that 75
% of predicted errors are smaller than 20
%.Figure 13
Two vehicles make different turns in city scenarios. After turning, these two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)For the second case, we pick two vehicles and plot the mean of their relative speed in Figure14(a), the standard deviation of their relative speed in Figure 14(b), and the predicted and real link durations in Figure 14(c). Because the second vehicle arrives at and leaves the intersection at 6
s and 26
s, respectively, the relative speed changes drastically during [
0
s
,
6
s
] and [
26
s
,
40
s
]. That is why, the predicted errors during these two periods are very large. We plot the prediction error CDF of this pair of vehicles and the mean prediction errors of 10 randomly selected pairs of vehicles in Figures 14(d) and 14(e). Figure 14(d) tells us that 66
% of predicted errors are smaller than 40
%.Figure 14
Two vehicles make different turns in city scenarios. After turning, these two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)For the third case, two connected vehicles are randomly selected. We have the mean of relative speed in Figure15(a), the standard deviation of relative speed in Figure 15(b), and the predicted and real link durations in Figure 15(c). We further plot the prediction error CDF of this pair of vehicles in Figure 15(d). We randomly select other 10 pairs of vehicles and show their mean prediction errors in Figure 15(e). From these figures, we conclude that 76
% of predicted errors are less than 20
%.Figure 15
Two vehicles make different turns in city scenarios. After turning, the moving directions of these two vehicles have a certain angle.
(a)
(b)
(c)
(d)
(e)


#### 4.2.3. Making the Same Turn

Now we are looking at the cases where two vehicles make the same turn (either left or right) at an intersection. Again, we divide the vehicles into two groups. After turns, both vehicle (1) move in the same direction and (2) in opposite directions. Note that it is impossible to have two vehicles moving on directions with a relative angle because they turn to the same direction.For the first case, we speculate that the prediction error will be large because both vehicles turn at the intersection. We pick two vehicles, of this type, which connect to each other for302
s. We first plot the mean and standard deviation of relative speed in Figures 16(a) and 16(b). We note that the first vehicle faces a red signal and stops at the intersection during [
131
s
,
141
s
]; it starts to turn at 144
s. The second vehicle follows the first one and turns during [
144
s
,
149
s
]. Due to the impact of a red signal, the relative speed between them changes drastically during this period. The predicted errors of ELDP are large, which can be seen in Figure 16(c). We then plot the prediction error CDF of this pair of vehicles in Figure 16(d). This figure shows that 90
% of predicted errors are smaller than 27
%. We further randomly select 10 pairs of vehicles and show the mean prediction errors in Figure 16(e). Figure 16(e) indicates that most errors are less than 27
%.Figure 16
Two vehicles make same turns in city scenarios. After turning, these two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)For a pair of randomly selected vehicles in the second case, we plot the mean of their relative speed in Figure17(a), the standard deviation of relative speed in Figure 17(b), and the predicted and real link durations in Figure 17(c). We can see that these two vehicles are connected during [
1
s
,
20
s
], and the prediction errors are small. We plot the prediction error CDF of this pair of vehicles and the prediction errors of 10 pairs of randomly selected vehicles in Figures 17(d) and 17(e). From Figure 17(d), we can see that 80
% of predicted errors are smaller than 15
%.Figure 17
Two vehicles make same turns in city scenarios. After turning, these two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)


## 4.1. Highway Scenario

The simulation configuration parameters for highway scenarios are listed in Table1. We first analyze many trace files generated by the VISSIM and divide vehicles into two groups. In the first group, there are two vehicles that connect to each other and move in the same direction. In this group, one vehicle turns and changes its moving direction from 0 to α
<
π
/
2. In the second group, two connected vehicles move in opposite directions and one vehicle makes turns. At every time stamp, we compute the relative speed, relative angle, relative distance between these two vehicles, and their relative traveling distance D
D
0. These values are then fed into the ELDP model to estimate link durations. For each pair of connected vehicles, the ELDP model is applied several times to estimate their link durations. From the trace files, we identify the time instances when two vehicles connect and disconnect, so the time differences are considered the ground truth.Table 1
Simulation setup parameters in highway scenarios.
Length
6000 m
Width
3.5 m
Traffic flow
500 vehicles/hr
Velocity
58–110 km/hr
Number of lanes per direction
2
Communication range
300 m
Simulation time
1000 s


### 4.1.1. Moving in the Same Direction

We first study the ELDP’s performance on two vehicles moving in the same direction. We are interested in the cases where one vehicle turns and the other does not. We randomly select a pair of vehicles and plot the mean of their relative speed in Figure8(a). As we can see, the two vehicles are connected at the 1
st second. The mean of their relative speed keeps unchanged until 80
th second when one vehicle changes its moving direction. After that, the relative speed keeps increasing and the variation of relative speed increases as well. It can be seen in Figure 8(b) that the standard deviation of relative speed is very large after 80
th second.Figure 8
One vehicle turns and the other one keeps moving in a highway scenario. After the turning, two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)We compare the predicted link durations and the ground truth in Figure8(c). We can see that the estimated results from ELDP match the ground truth very well, indicating ELDP is an accurate model. To obtain a deeper understanding of the ELDP’s performance, we further plot the CDF of prediction errors in Figure 8(d). We also randomly select 10 pairs of vehicles and plot the mean prediction errors in Figure 8(e). From Figure 8(d), we find more than 85
% prediction results containing errors less than 10
%. Figure 8(e) reveals that most prediction errors are less than 5
%.


### 4.1.2. Moving in Opposite Directions

We then look at the cases where two vehicles move in opposite directions. Similarly, we only select the cases where one vehicle turns and the other does not. We randomly select a pair of vehicles and plot the mean and standard deviation of their relative speed in Figures9(a) and 9(b), respectively. From the figures, we find that the relative speed keeps decreasing but decreases faster after the 7
s. This is because, before 7
s, the two vehicles move (away from each other) in opposite directions. After 7
s, one vehicle turns and suddenly their relative speed decreases faster. After 16
s, these two vehicles are disconnected.Figure 9
One vehicle turns and the other one keeps moving in a highway scenario. After the turning, two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)We further plot the predicted link durations and the ground truth in Figure9(c). We can see that the estimated results from ELDP are very close to the ground truth. We also plot the CDF of prediction errors and the mean prediction errors of 10 randomly selected pairs of vehicles in Figures 9(d) and 9(e), respectively. From Figure 9(d), we find more than 88
% prediction results containing errors less than 4
%. Figure 9(e) indicates that the error of 90
% prediction results are less than 4
%.Overall, simulation results illustrate that ELDP works better for vehicles moving in opposite directions. In addition, a vehicle making turns on highways does not drastically affect ELDP’s performance. We conclude that the turning angle of a vehicle is not an influential factor in ELDP.


## 4.1.1. Moving in the Same Direction

We first study the ELDP’s performance on two vehicles moving in the same direction. We are interested in the cases where one vehicle turns and the other does not. We randomly select a pair of vehicles and plot the mean of their relative speed in Figure8(a). As we can see, the two vehicles are connected at the 1
st second. The mean of their relative speed keeps unchanged until 80
th second when one vehicle changes its moving direction. After that, the relative speed keeps increasing and the variation of relative speed increases as well. It can be seen in Figure 8(b) that the standard deviation of relative speed is very large after 80
th second.Figure 8
One vehicle turns and the other one keeps moving in a highway scenario. After the turning, two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)We compare the predicted link durations and the ground truth in Figure8(c). We can see that the estimated results from ELDP match the ground truth very well, indicating ELDP is an accurate model. To obtain a deeper understanding of the ELDP’s performance, we further plot the CDF of prediction errors in Figure 8(d). We also randomly select 10 pairs of vehicles and plot the mean prediction errors in Figure 8(e). From Figure 8(d), we find more than 85
% prediction results containing errors less than 10
%. Figure 8(e) reveals that most prediction errors are less than 5
%.


## 4.1.2. Moving in Opposite Directions

We then look at the cases where two vehicles move in opposite directions. Similarly, we only select the cases where one vehicle turns and the other does not. We randomly select a pair of vehicles and plot the mean and standard deviation of their relative speed in Figures9(a) and 9(b), respectively. From the figures, we find that the relative speed keeps decreasing but decreases faster after the 7
s. This is because, before 7
s, the two vehicles move (away from each other) in opposite directions. After 7
s, one vehicle turns and suddenly their relative speed decreases faster. After 16
s, these two vehicles are disconnected.Figure 9
One vehicle turns and the other one keeps moving in a highway scenario. After the turning, two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)We further plot the predicted link durations and the ground truth in Figure9(c). We can see that the estimated results from ELDP are very close to the ground truth. We also plot the CDF of prediction errors and the mean prediction errors of 10 randomly selected pairs of vehicles in Figures 9(d) and 9(e), respectively. From Figure 9(d), we find more than 88
% prediction results containing errors less than 4
%. Figure 9(e) indicates that the error of 90
% prediction results are less than 4
%.Overall, simulation results illustrate that ELDP works better for vehicles moving in opposite directions. In addition, a vehicle making turns on highways does not drastically affect ELDP’s performance. We conclude that the turning angle of a vehicle is not an influential factor in ELDP.


## 4.2. City Scenario

It is challenging to accurately predict the link duration between two vehicles in a city scenario. This is mainly because it is difficult, if not impossible, to predict what traffic signal a vehicle will face in front of an intersection. Besides, vehicles can make turns at intersections, which makes the link duration prediction a nontrivial problem. To realistically simulate vehicle movements in city scenarios, we configure the VISSIM simulator based on the parameters given in Table2.Table 2
Simulation setup parameters in city scenarios.
Length
10000 m
Width
3.5 m
Traffic flow
300 vehicles/hr
Velocity
0–60 km/hr
Number of lanes per direction
3
Communication range
300 m
Green signal
30 s
Red signal
67 m
Left green signal
20 s
Left red signal
77 s
Yellow signal
3 s
Simulation time
1000 s
Size of intersection
50 m × 50 mBased on the trajectories of vehicles at an intersection, we categorize connected vehicles into three groups: (1) one vehicle moves straightforward and the other makes a left/right turn, (2) one vehicle turns left and the other turns right, and (3) both turn to the same direction. After turns, the two vehicles may move in the same direction, in opposite directions, or with a relative angle ofα.


### 4.2.1. Moving Forward versus Making Turns

Here, we are interested in pairs of connected vehicles: one moves straightforward and the other turns to left/right. We divide these vehicles into three groups. After turns, (1) both vehicles move in the same direction, (2) both move in opposite directions, and (3) the relative moving direction of them isα
=
π
/
2.Moving in the Same Direction.For the first case where two vehicles move in the same direction, we randomly pick a pair of vehicles and plot the predicted and real link durations in Figure 10(c). We can see that these two vehicles connect for about 30
s, and the error of predicted link durations decreases as the time increases. We also find that the predicted errors before 13
s are large. This is because the first vehicle faces a red signal at an intersection at time 13
s, and the other vehicle makes a turn. Therefore, the relative speeds within [
0
s
,
13
s
] change drastically. After 13
s, because we accurately predict relative speeds, the predicted errors reduce. Before the intersection, the second vehicle moves toward the first one, so their relative distance decreases. After that, the rules of calculating D
D
0 change as the values of B and A are different.Figure 10
One vehicle turns and the other one keeps moving in a city scenario. After the turning, two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)To understand the fluctuation in data in Figure10(c), we further plot in Figure 10(b) how relative speed changes over time. This figure indicates that, during [
10
s
,
17
s
], the first vehicle stops in front of an intersection and the second one turns. This can be confirmed in Figure 10(a) that shows the mean of relative speeds. During [
8
s
,
21
s
], the mean of relative speeds decreases linearly because the first vehicle stops in front of the intersection. Except for this period, the fluctuation of relative speeds is very small, leading to a small prediction error. From the above analysis, we conclude that stable relative speeds yield accurate prediction results.We also plot the CDF of error and the mean errors of 10 randomly selected pairs of vehicles in Figures10(d) and 10(e). In Figure 10(d), more than 80
% prediction results contain errors less than 10
%. Figure 10(e) illustrates that the errors of 80
% prediction results are less than 10
%.Moving in Opposite Directions. For this case, vehicles move in opposite directions after one vehicle turns at an intersection. In Figure 11(a), we provide the predicted and actual link durations of a pair of randomly selected vehicles. The first vehicle faces a red signal at 12
s; it then stops at the intersection. Around this time, we can see that its velocity varies a lot. When the second vehicle turns at the intersection, due to the impact of the traffic light, the relative distance and relative speed change drastically. The predicted errors increase when vehicles are around the intersection. The average relative speed and its variation are shown in Figures 11(a) and 11(b). From Figure 11(b), we see that the mean of relative speed changes drastically during [
0
s
,
12
s
) because the first vehicle stops in front of the intersection. During [
12
s
,
31
s
), however, the relative speed increases gradually because the first vehicle starts to move.Figure 11
One vehicle turns and the other one keeps moving in a city scenario. After the turning, two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)Similarly, we plot Figures11(d) and 11(e). From these figures, we find more than 72
% prediction results containing errors less than 10
%, and the errors of 90
% prediction results are less than 10
%.Moving Directions with a Certain Angle. For the last case, we are interested in two vehicles moving with a relative angle α, after one vehicle turns at an intersection. We first plot the mean and standard deviation of their relative speed in Figures 12(a) and 12(b). The two figures help us to understand what happened when they are approaching the intersection. We plot the predicted and real link durations in Figure 12(c). We can see that the predicted errors are very small no matter whether a vehicle turns at the intersection or not. We also plot the prediction error CDF and the mean errors of 10 randomly selected pairs of vehicles in Figures 12(d) and 12(e).Figure 12
One vehicle turns and the other one keeps moving in a city scenario. After the turning, the relative moving direction of them is denoted asα.
(a)
(b)
(c)
(d)
(e)In summary, for a pair of vehicles where one moves straightforward and the other turns at an intersection, ELDP can accurately (with an error<
10
%) predicte their link durations.


### 4.2.2. Making Different Turns

For those connected vehicles that make different turns at an intersection, we divide them into three groups. After they turn at an intersection, they move (1) in the same direction, (2) in opposite directions, and (3) withα
=
π
/
2 relative direction.For the first case, we randomly select a pair of vehicles and plot the mean of their relative speed in Figure13(a), the standard deviation of their relative speed in Figure 13(b), and the predicted and real link durations in Figure 13(c). We find that, even with a large fluctuation in the relative speeds, the predicted error is small and acceptable. We plot the prediction error CDF of this pair of vehicles and the mean errors of 10 randomly selected pairs of vehicles in Figures 13(d) and 13(e). We find that 75
% of predicted errors are smaller than 20
%.Figure 13
Two vehicles make different turns in city scenarios. After turning, these two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)For the second case, we pick two vehicles and plot the mean of their relative speed in Figure14(a), the standard deviation of their relative speed in Figure 14(b), and the predicted and real link durations in Figure 14(c). Because the second vehicle arrives at and leaves the intersection at 6
s and 26
s, respectively, the relative speed changes drastically during [
0
s
,
6
s
] and [
26
s
,
40
s
]. That is why, the predicted errors during these two periods are very large. We plot the prediction error CDF of this pair of vehicles and the mean prediction errors of 10 randomly selected pairs of vehicles in Figures 14(d) and 14(e). Figure 14(d) tells us that 66
% of predicted errors are smaller than 40
%.Figure 14
Two vehicles make different turns in city scenarios. After turning, these two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)For the third case, two connected vehicles are randomly selected. We have the mean of relative speed in Figure15(a), the standard deviation of relative speed in Figure 15(b), and the predicted and real link durations in Figure 15(c). We further plot the prediction error CDF of this pair of vehicles in Figure 15(d). We randomly select other 10 pairs of vehicles and show their mean prediction errors in Figure 15(e). From these figures, we conclude that 76
% of predicted errors are less than 20
%.Figure 15
Two vehicles make different turns in city scenarios. After turning, the moving directions of these two vehicles have a certain angle.
(a)
(b)
(c)
(d)
(e)


### 4.2.3. Making the Same Turn

Now we are looking at the cases where two vehicles make the same turn (either left or right) at an intersection. Again, we divide the vehicles into two groups. After turns, both vehicle (1) move in the same direction and (2) in opposite directions. Note that it is impossible to have two vehicles moving on directions with a relative angle because they turn to the same direction.For the first case, we speculate that the prediction error will be large because both vehicles turn at the intersection. We pick two vehicles, of this type, which connect to each other for302
s. We first plot the mean and standard deviation of relative speed in Figures 16(a) and 16(b). We note that the first vehicle faces a red signal and stops at the intersection during [
131
s
,
141
s
]; it starts to turn at 144
s. The second vehicle follows the first one and turns during [
144
s
,
149
s
]. Due to the impact of a red signal, the relative speed between them changes drastically during this period. The predicted errors of ELDP are large, which can be seen in Figure 16(c). We then plot the prediction error CDF of this pair of vehicles in Figure 16(d). This figure shows that 90
% of predicted errors are smaller than 27
%. We further randomly select 10 pairs of vehicles and show the mean prediction errors in Figure 16(e). Figure 16(e) indicates that most errors are less than 27
%.Figure 16
Two vehicles make same turns in city scenarios. After turning, these two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)For a pair of randomly selected vehicles in the second case, we plot the mean of their relative speed in Figure17(a), the standard deviation of relative speed in Figure 17(b), and the predicted and real link durations in Figure 17(c). We can see that these two vehicles are connected during [
1
s
,
20
s
], and the prediction errors are small. We plot the prediction error CDF of this pair of vehicles and the prediction errors of 10 pairs of randomly selected vehicles in Figures 17(d) and 17(e). From Figure 17(d), we can see that 80
% of predicted errors are smaller than 15
%.Figure 17
Two vehicles make same turns in city scenarios. After turning, these two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)


## 4.2.1. Moving Forward versus Making Turns

Here, we are interested in pairs of connected vehicles: one moves straightforward and the other turns to left/right. We divide these vehicles into three groups. After turns, (1) both vehicles move in the same direction, (2) both move in opposite directions, and (3) the relative moving direction of them isα
=
π
/
2.Moving in the Same Direction.For the first case where two vehicles move in the same direction, we randomly pick a pair of vehicles and plot the predicted and real link durations in Figure 10(c). We can see that these two vehicles connect for about 30
s, and the error of predicted link durations decreases as the time increases. We also find that the predicted errors before 13
s are large. This is because the first vehicle faces a red signal at an intersection at time 13
s, and the other vehicle makes a turn. Therefore, the relative speeds within [
0
s
,
13
s
] change drastically. After 13
s, because we accurately predict relative speeds, the predicted errors reduce. Before the intersection, the second vehicle moves toward the first one, so their relative distance decreases. After that, the rules of calculating D
D
0 change as the values of B and A are different.Figure 10
One vehicle turns and the other one keeps moving in a city scenario. After the turning, two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)To understand the fluctuation in data in Figure10(c), we further plot in Figure 10(b) how relative speed changes over time. This figure indicates that, during [
10
s
,
17
s
], the first vehicle stops in front of an intersection and the second one turns. This can be confirmed in Figure 10(a) that shows the mean of relative speeds. During [
8
s
,
21
s
], the mean of relative speeds decreases linearly because the first vehicle stops in front of the intersection. Except for this period, the fluctuation of relative speeds is very small, leading to a small prediction error. From the above analysis, we conclude that stable relative speeds yield accurate prediction results.We also plot the CDF of error and the mean errors of 10 randomly selected pairs of vehicles in Figures10(d) and 10(e). In Figure 10(d), more than 80
% prediction results contain errors less than 10
%. Figure 10(e) illustrates that the errors of 80
% prediction results are less than 10
%.Moving in Opposite Directions. For this case, vehicles move in opposite directions after one vehicle turns at an intersection. In Figure 11(a), we provide the predicted and actual link durations of a pair of randomly selected vehicles. The first vehicle faces a red signal at 12
s; it then stops at the intersection. Around this time, we can see that its velocity varies a lot. When the second vehicle turns at the intersection, due to the impact of the traffic light, the relative distance and relative speed change drastically. The predicted errors increase when vehicles are around the intersection. The average relative speed and its variation are shown in Figures 11(a) and 11(b). From Figure 11(b), we see that the mean of relative speed changes drastically during [
0
s
,
12
s
) because the first vehicle stops in front of the intersection. During [
12
s
,
31
s
), however, the relative speed increases gradually because the first vehicle starts to move.Figure 11
One vehicle turns and the other one keeps moving in a city scenario. After the turning, two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)Similarly, we plot Figures11(d) and 11(e). From these figures, we find more than 72
% prediction results containing errors less than 10
%, and the errors of 90
% prediction results are less than 10
%.Moving Directions with a Certain Angle. For the last case, we are interested in two vehicles moving with a relative angle α, after one vehicle turns at an intersection. We first plot the mean and standard deviation of their relative speed in Figures 12(a) and 12(b). The two figures help us to understand what happened when they are approaching the intersection. We plot the predicted and real link durations in Figure 12(c). We can see that the predicted errors are very small no matter whether a vehicle turns at the intersection or not. We also plot the prediction error CDF and the mean errors of 10 randomly selected pairs of vehicles in Figures 12(d) and 12(e).Figure 12
One vehicle turns and the other one keeps moving in a city scenario. After the turning, the relative moving direction of them is denoted asα.
(a)
(b)
(c)
(d)
(e)In summary, for a pair of vehicles where one moves straightforward and the other turns at an intersection, ELDP can accurately (with an error<
10
%) predicte their link durations.


## 4.2.2. Making Different Turns

For those connected vehicles that make different turns at an intersection, we divide them into three groups. After they turn at an intersection, they move (1) in the same direction, (2) in opposite directions, and (3) withα
=
π
/
2 relative direction.For the first case, we randomly select a pair of vehicles and plot the mean of their relative speed in Figure13(a), the standard deviation of their relative speed in Figure 13(b), and the predicted and real link durations in Figure 13(c). We find that, even with a large fluctuation in the relative speeds, the predicted error is small and acceptable. We plot the prediction error CDF of this pair of vehicles and the mean errors of 10 randomly selected pairs of vehicles in Figures 13(d) and 13(e). We find that 75
% of predicted errors are smaller than 20
%.Figure 13
Two vehicles make different turns in city scenarios. After turning, these two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)For the second case, we pick two vehicles and plot the mean of their relative speed in Figure14(a), the standard deviation of their relative speed in Figure 14(b), and the predicted and real link durations in Figure 14(c). Because the second vehicle arrives at and leaves the intersection at 6
s and 26
s, respectively, the relative speed changes drastically during [
0
s
,
6
s
] and [
26
s
,
40
s
]. That is why, the predicted errors during these two periods are very large. We plot the prediction error CDF of this pair of vehicles and the mean prediction errors of 10 randomly selected pairs of vehicles in Figures 14(d) and 14(e). Figure 14(d) tells us that 66
% of predicted errors are smaller than 40
%.Figure 14
Two vehicles make different turns in city scenarios. After turning, these two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)For the third case, two connected vehicles are randomly selected. We have the mean of relative speed in Figure15(a), the standard deviation of relative speed in Figure 15(b), and the predicted and real link durations in Figure 15(c). We further plot the prediction error CDF of this pair of vehicles in Figure 15(d). We randomly select other 10 pairs of vehicles and show their mean prediction errors in Figure 15(e). From these figures, we conclude that 76
% of predicted errors are less than 20
%.Figure 15
Two vehicles make different turns in city scenarios. After turning, the moving directions of these two vehicles have a certain angle.
(a)
(b)
(c)
(d)
(e)


## 4.2.3. Making the Same Turn

Now we are looking at the cases where two vehicles make the same turn (either left or right) at an intersection. Again, we divide the vehicles into two groups. After turns, both vehicle (1) move in the same direction and (2) in opposite directions. Note that it is impossible to have two vehicles moving on directions with a relative angle because they turn to the same direction.For the first case, we speculate that the prediction error will be large because both vehicles turn at the intersection. We pick two vehicles, of this type, which connect to each other for302
s. We first plot the mean and standard deviation of relative speed in Figures 16(a) and 16(b). We note that the first vehicle faces a red signal and stops at the intersection during [
131
s
,
141
s
]; it starts to turn at 144
s. The second vehicle follows the first one and turns during [
144
s
,
149
s
]. Due to the impact of a red signal, the relative speed between them changes drastically during this period. The predicted errors of ELDP are large, which can be seen in Figure 16(c). We then plot the prediction error CDF of this pair of vehicles in Figure 16(d). This figure shows that 90
% of predicted errors are smaller than 27
%. We further randomly select 10 pairs of vehicles and show the mean prediction errors in Figure 16(e). Figure 16(e) indicates that most errors are less than 27
%.Figure 16
Two vehicles make same turns in city scenarios. After turning, these two vehicles move in the same direction.
(a)
(b)
(c)
(d)
(e)For a pair of randomly selected vehicles in the second case, we plot the mean of their relative speed in Figure17(a), the standard deviation of relative speed in Figure 17(b), and the predicted and real link durations in Figure 17(c). We can see that these two vehicles are connected during [
1
s
,
20
s
], and the prediction errors are small. We plot the prediction error CDF of this pair of vehicles and the prediction errors of 10 pairs of randomly selected vehicles in Figures 17(d) and 17(e). From Figure 17(d), we can see that 80
% of predicted errors are smaller than 15
%.Figure 17
Two vehicles make same turns in city scenarios. After turning, these two vehicles move in opposite directions.
(a)
(b)
(c)
(d)
(e)


## 5. Conclusions

The LDP model is extended to the ELDP model, leveraging the distribution of relative speeds, instead of instantaneous ones. Besides relative speeds, the model also considers intervehicle distance, the impact of traffic lights, and vehicles turning at intersections, in predicting link durations. Based on the model, a practical solution is implemented so that a vehicle can dynamically estimate the link durations between itself and any connected vehicles. Among all parameters, the mean of relative speed is the most important one, so accurately estimating this parameter becomes extremely critical. To eliminate the impact of sudden velocity changes, we apply the EMA method on relative speed samples so that outlier samples are filtered. Intensive simulation results show that the ELDP model is suitable and practical for accurately predicting link durations in VANETs. Particularly, a higher accuracy of prediction is achieved in the highway scenario where two vehicles move in opposite directions. Because a vehicle only needs to collect and share its latest five velocity samples, the overhead of proposed work is subtle. The extended model can be used to accurately predict link duration of any two vehicles in both highway and city scenarios. We plan to further validate the ELDP model against real-world datasets.



---

*Source: 5767569-2016-04-11.xml*