Practical Link Duration Prediction Model in Vehicular Ad Hoc Networks

Abstract

Link duration prediction is one of the most fundamental problems in vehicular ad hoc networks (VANETs) as it determines the network performance of many vehicular applications. Existing analytical analysis about link duration in both mobile ad hoc network (MANETs) and VANETs is too complicated to be applied in a practical setting. Assuming vehicle's velocity follows the normal distribution, we propose a practical model which considers the distribution of relative velocity, intervehicle distance, and impact of traffic lights to estimate the expected link duration between any pair of connected vehicles. Such model is implemented on each vehicle along with (1) a relative velocity estimation approach and (2) an exponential moving average- (EMA-) based data processing procedure. Furthermore, the proposed model assumes that the events of two consecutive vehicles encountering traffic lights combination are dependent, which make the model more practical. Simulation results show that the link duration model predicts link duration with the average accuracy of 10% and 20% in highway and city scenarios, respectively.

1. Introduction

Vehicular ad hoc networks (VANETs) [1] are considered as an important type of delay tolerant networks (DTN) [2] where vehicles share safety or entertainment-related information between each others via vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communications [3]. To support this vision, the Federal Communication Commission (FCC) in U.S. has approved 75 MHz of spectrum from 5.85 GHz to 5.925 GHz for dedicated short range communications (DSRC) to enhance safety and productivity of transportation systems.

Potential applications of VANETs include road safety [4], traffic monitoring [5], entertainment, and advertisements [6], delivering non-real-time Internet connectivity [7]. To enable these applications, a few important questions need to be answered: Is it possible to predict the link duration between any two connected vehicles? What information are needed on each vehicle to make such prediction? Is is feasible for vehicles to obtain these information in real-time?

The importance of link duration on the network performance in mobile ad hoc networks (MANET) and DTN was intensively studied in the literature [8–10]. Similarly, from simulation results [11], link duration is considered one of the most important QoS metrics in VANET routing. Link duration between two vehicles could significantly affect the stability of a multihop path constructed by a routing protocol, so there has been several works focusing on reliable routing by considering link duration [12, 13].

To model link duration in VANETs, a few analytical works are proposed [14, 15]. However, link duration in VANETs is very complicated and affected by many factors including intervehicle distance, vehicle speed, turning ratios at intersections, influence traffic lights, and signal decay caused by the roadside buildings. Our analysis reveals that the distribution of a vehicle's velocity follows closely the normal distribution; therefore, it is possible to use the distribution of relative speeds, instead of instantaneous velocity, to estimate the expected link duration between vehicles.

We design a practical solution that allows each vehicles to practically estimate the link duration between itself and any other connected vehicles. The main instrument of this work is to approximate the distribution of vehicles’ relative speeds and estimate expected link duration by considering initial intervehicle distance and the impact of traffic light. In addition, we applied the exponential moving average (EMA) method on velocity samples to filter the sudden changes occurring in vehicle velocities. It turns out that each vehicle only needs to collect 10 samples to achieve a relatively accurate link duration estimation.

There are four major contributions of this paper. First, we propose a novel link duration predication (LDP) model for highly dynamic and distributed VANETs so that each vehicle is able to predict link duration in real time. Second, based on LDP model, a practical solution is designed to automatically collect velocity samples on vehicles and accurately estimate the distribution of velocities. Third, LDP does not assume the events of meeting traffic lights for two consecutive vehicles are independent, which is a common assumption in previous works. Fourth, we validate LDP and evaluate its performance in simulations and results show that LDP can accurate predict link duration for VANETs in both highway and city scenarios.

The rest of the paper is organized as follows. Section 2 summarizes the related works. The LDP model and how to estimate the distribution of relative velocities are described in Section 3. In Section 4, we validate the LDP model and evaluate its performance in highway and city scenarios. Finally, we draw conclusions in Section 5.

2. Related Work

There have been some works studying the link duration problem in mobile ad hoc networks. Link duration is defined as the time interval in which two nodes stay within transmission range of each others [16]. It was also discovered in [16] that link duration is determined by the relative speed and active distance between two nodes given the assumption that node movement follows the random way point model.

It was proved in [17] that the random way point model could not provide a steady state where the average speed of nodes consistently decreases over time, and therefore should not be used directly in simulations. In addition, it was shown in [18] that different mobility models had different impacts on link stability in ad hoc networks. Because of the above-mentioned reasons, the authors of [16] extend their work by considering both random way point and random walk models and further investigate the behavior of multihop links in mobile ad hoc networks.

In mobile ad hoc networks, the statistic of multihop path duration was studied in detail [8], that is, how probability density functions vary with parameters including mobility model, relative speeds, number of hops, and communication range. Exponential distribution was found to be a good approximation of path duration distribution for nodes moving at moderate and high velocities. This result suggested an exponential distribution of link duration to be expected in vehicular networks as vehicles are moving with relatively high velocities, which was validated by the experimental results in [19].

In [19], extensive experiments were conducted on thousands of operational taxies in Shanghai, China. It was observed that the distribution of link duration exhibits a light tail such as one of an exponential distribution over a large range of timescales. In fact, before this experimental study, there were some other theoretical works suggesting intercontact time between nodes in ad hoc networks is light tailed through numerical simulations based on the random way point model [20–22].

Conclusions drawn from mobile ad hoc network might not be applied to vehicular network (as vehicle's movement does not follow random way point model), so researchers recently started to investigate link duration in VANETs. Nekovee first studied the probability of link duration in VANET by assuming active distances between vehicles are constant and ignoring mobility models of vehicles [23]. Then, he extended the work by assuming vehicles’ velocities follows normal distribution in [24]. In [14], the probability distribution of link duration in VANETs was theoretically studied under the assumptions of a realistic radio transmission model and probability distribution model of intervehicle headway distance.

Assuming free flow traffic state and normal distribution of vehicle's velocity, the impact of vehicle mobility, vehicle density, and transmission range on link duration in VANET is studied in [15]. It was also found from [15] that exponential distribution is a good approximation of link duration pdf. In [25], a discrete Markov process-based model is proposed for link duration by considering the intervehicle distance, vehicle speed, turning ratios in intersections, and traffic lights.

Above-mentioned analytical models for link duration in both MANET and VANET pave the way for predicting link duration in real-time within VANET. To the best of our knowledge, none of existing works proposed a practical design to allow vehicles to dynamically predict the link duration between itself and other connected vehicles. Unlike previous works, we only assume vehicles velocities follow normal distribution and release the assumptions about knowing the distributions of intervehicle distance, traffic flow state, and so forth.

3. Link Duration Predication Model

To accurately predict how long two vehicles are connected, a link duration model must overcome two challenges. $(1)$ It must be resilient to rapid change of vehicle's velocity, and $(2)$ it must be able to handle the impact of traffic light. To address the first challenge, we propose to use the distribution of relative speeds, instead of instantaneous velocities, to estimate the expected link duration between vehicles. For the second issue, we model the arrivals of vehicles at intersections in probability, and then compute the expected delay caused by traffic lights.

3.1. Distribution of Relative Velocity

Since vehicles move with various speeds on road, we first investigate the distribution a vehicle's velocity. As shown in Figure 1, the velocity of a randomly selected vehicle from our simulations closely follows the normal distribution. While looking at the relative velocity of two randomly picked vehicles, we found it also follows normal distribution, as shown in Figure 2.

Figure 1

Mean absolute and relative velocities of two nodes in highway scenarios.

Figure 2

Relative velocity of two randomley picked nodes.

Assume a vehicle's velocity v is a random variable which follows the normal distribution $\mathcal{N}(\mu ,{\sigma }^{\mathrm{2}})$ , then its probability density function (PDF) can be represented as

$$\begin{array}{cc}& f\left(v\right)=\frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi }\sigma }{e}^{-(v-\mu {)}^{\mathrm{2}}/\mathrm{2}{\sigma }^{\mathrm{2}}}.\end{array}$$

(1)

If vehicles’ velocities are independent random variables, then the relative velocity of any two vehicles still follows the normal distribution. Suppose the velocity PDFs of two vehicles are $f(v_{\mathrm{1}})$ ~ $\mathcal{N}({\mu }_{\mathrm{1}},{\sigma }_{\mathrm{1}}^{\mathrm{2}})$ and $f(v_{\mathrm{2}})$ ~ $\mathcal{N}({\mu }_{\mathrm{2}},{\sigma }_{\mathrm{2}}^{\mathrm{2}})$ , respectively. The PDF of relative velocity of these two nodes will be $f(v_{\mathrm{12}})$ ~ $\mathcal{N}({\mu }_{\mathrm{12}},{\sigma }_{\mathrm{12}}^{\mathrm{2}})$ , where $v_{\mathrm{12}}=v_{\mathrm{1}}-v_{\mathrm{2}}$ , ${\mu }_{\mathrm{12}}={\mu }_{\mathrm{1}}-{\mu }_{\mathrm{2}}$ , and ${\sigma }_{\mathrm{12}}^{\mathrm{2}}={\sigma }_{\mathrm{1}}^{\mathrm{2}}+{\sigma }_{\mathrm{2}}^{\mathrm{2}}$ . In reality, vehicles’ velocities might be dependent on each others, for example, a vehicle is following another vehicle. In this case, the PDF of relative velocity needs to be computed differently.

We assume $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ are jointly normally distributed random variables, then $v_{\mathrm{1}}-v_{\mathrm{2}}$ is still normally distributed. This assumption has been verified by simulation results shown in Figure 2. In other words, $v_{\mathrm{1}}-v_{\mathrm{2}}$ forms a multivariate normal distribution $f(v_{\mathrm{12}})$ ~ $\mathcal{N}({\mu }_{\mathrm{12}},{\sigma }_{\mathrm{12}}^{\mathrm{2}})$ , where $v_{\mathrm{12}}=v_{\mathrm{1}}-v_{\mathrm{2}}$ and ${\mu }_{\mathrm{12}}={\mu }_{\mathrm{1}}-{\mu }_{\mathrm{2}}$ . However, the variances are not additive due to the correlation, that is, ${\sigma }_{\mathrm{12}}^{\mathrm{2}}$ becomes

$$\begin{array}{cc}& {\sigma }_{\mathrm{1}}^{\mathrm{2}}+{\sigma }_{\mathrm{2}}^{\mathrm{2}}+\mathrm{2}\rho {\sigma }_{\mathrm{1}}{\sigma }_{\mathrm{2}},\end{array}$$

(2)

where ρ is the correlation between two random variables $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ . In particular, whenever $\rho <\mathrm{0}$ , the variance is less than the sum of the variances of $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ .

The population correlation coefficient ρ between two random variables $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ with expected value ${\mu }_{\mathrm{1}}$ and ${\mu }_{\mathrm{2}}$ and standard deviation ${\sigma }_{\mathrm{1}}$ and ${\sigma }_{\mathrm{2}}$ is defined as

$$\begin{array}{cc}& \rho =\frac{\mathrm{cov}\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)}{{\sigma }_{\mathrm{1}}{\sigma }_{\mathrm{2}}}=\frac{E\left[\left(v_{\mathrm{1}}-{\mu }_{\mathrm{1}}\right)\left(v_{\mathrm{2}}-{\mu }_{\mathrm{2}}\right)\right]}{{\sigma }_{\mathrm{1}}{\sigma }_{\mathrm{2}}},\end{array}$$

(3)

where E is the expected value operator, cov means the covariance between $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ . To compute this value, two cars need share their historical speed information to each others.

As independent scenarios are special cases of the dependent ones, we could conclude that given the velocity PDFs of two vehicles, $\mathcal{N}({\mu }_{\mathrm{1}},{\sigma }_{\mathrm{1}}^{\mathrm{2}})$ and $\mathcal{N}({\mu }_{\mathrm{2}},{\sigma }_{\mathrm{2}}^{\mathrm{2}})$ , their relative velocity still follows the normal distribution:

$$\begin{array}{cc}& f\left(v_{\mathrm{1}}-v_{\mathrm{2}}\right)=\frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi }{\sigma }_{\mathrm{12}}}{e}^{-(v_{\mathrm{1}}-v_{\mathrm{2}}-{\mu }_{\mathrm{12}}{)}^{\mathrm{2}}/\mathrm{2}{\sigma }_{\mathrm{12}}^{\mathrm{2}}},\end{array}$$

(4)

where ${\mu }_{\mathrm{12}}={\mu }_{\mathrm{1}}-{\mu }_{\mathrm{2}}$ and ${\sigma }_{\mathrm{12}}^{\mathrm{2}}$ could be computed from (2).

3.2. Estimation of Relative Velocity

To estimate the distribution of relative velocity of any two cars, we first need to know the velocity distribution parameters ( $\mu ,{\sigma }^{\mathrm{2}}$ ) of any vehicle. To estimate these parameters, each vehicle continuously collects samples of its velocity so that its velocity distribution can be estimated from these samples.

Given a set of velocity samples ( $v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n$ ) measured by a vehicle, we know they are obtained from a normal $\mathcal{N}(\mu ,{\sigma }^{\mathrm{2}})$ population. The standard approach to estimate μ and ${\sigma }^{\mathrm{2}}$ is the maximum likelihood method which maximizes the log-likelihood function $\ln \mathcal{L}(\mu ,{\sigma }^{\mathrm{2}})$ , which can be rewritten as

$$\begin{array}{cc}& -\frac{n}{\mathrm{2}}\ln \left(\mathrm{2}\pi \right)-\frac{n}{\mathrm{2}}\ln {\sigma }^{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{2}{\sigma }^{\mathrm{2}}}{\displaystyle \sum }_{i=\mathrm{1}}^n‍{\left(v_i-\mu \right)}^{\mathrm{2}}.\end{array}$$

(5)

Taking derivatives with respect to μ and ${\sigma }^{\mathrm{2}}$ yields the maximum likelihood estimates:

$$\begin{array}{cc}& \widehat{\mu }=\frac{\mathrm{1}}{n}{\displaystyle \sum }_{i=\mathrm{1}}^n‍v_i,\end{array}$$

(6)

where $\widehat{\mu }$ is the estimated μ. It is also called the sample mean as it is the arithmetic average of all samples. Since $\widehat{\mu }$ is the uniformly minimum variance unbiased (UMVU) estimator, it is distributed normally [26], that is, $\widehat{\mu }\mathrm{\hspace{0.17em}\hspace{0.17em}}$ ~ $\mathcal{N}(\mu ,{\sigma }^{\mathrm{2}}/n)$ . Therefore, the standard error of $\widehat{\mu }$ is proportional to $\sqrt{n}$ , that is, larger the sample sizes, smaller the estimation errors.

To estimate the ${\sigma }^{\mathrm{2}}$ , sample variance $s^{\mathrm{2}}$ is used and its square root s is called the sample standard deviation. Consider

$$\begin{array}{cc}& s^{\mathrm{2}}=\frac{n}{n-\mathrm{1}}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\widehat{\sigma }}^{\mathrm{2}}=\frac{\mathrm{1}}{n-\mathrm{1}}{\displaystyle \sum }_{i=\mathrm{1}}^n‍{\left(v_i-\widehat{\mu }\right)}^{\mathrm{2}},\end{array}$$

(7)

where ${\widehat{\sigma }}^{\mathrm{2}}$ is called the sample variance. Using $s^{\mathrm{2}}$ (instead of ${\widehat{\sigma }}^{\mathrm{2}}$ ) to estimate ${\sigma }^{\mathrm{2}}$ is because $s^{\mathrm{2}}$ is an unbiased estimator while ${\widehat{\sigma }}^{\mathrm{2}}$ is biased [26].

To avoid buffer overflow, only a certain amount of samples are recorded on each vehicle. In fact, a sliding window scheme is adopted on each vehicle so that only the most recent ten samples are considered in estimating parameters μ and σ.

3.3. Principle of Link Duration Prediction

Assume both absolute and relative velocities follow normal distribution, the link duration between any two connected vehicles could be computed from the expected relative traveling distance between them. We first introduce the prediction model without considering traffic lights, how to compute link duration with traffic lights will be provided in the next section.

We consider the link duration between any two vehicles a random variable T. The distribution of this random variable highly depends on $(1)$ the relative speed v of these two vehicles, $(2)$ initial distance d between them, and $(3)$ their relative moving direction. Because these three factors may change while these two vehicles are connected, the prediction model needs to adaptively adjust prediction rules to compute accurate results.

To determine T's distribution, we first introduce the concept of relative traveling distance L. Suppose two vehicles move in the same direction, if the following vehicle's speed is greater than the front one, L become $R+d$ where R is the communication range. Otherwise, $L=R-d$ . When two vehicles move in different directions, if they are moving away from each other, $L=R-d$ . Otherwise, L is $R+d$ as they move towards each others.

Now we are ready to define the CDF of T as follows:

$$\begin{array}{cc}& F\left(T\right)=P\left(T\le t\right)=P\left(\frac{L}{v}\le t\right)=\mathrm{1}-P\left(v\le \frac{L}{t}\right).\end{array}$$

(8)

Differentiate the above equation by t, the probability distribution function of T is

$$\begin{array}{cc}& f\left(t\right)=\frac{L}{t^{\mathrm{2}}}{f}_v\left(\frac{L}{t}\right).\end{array}$$

(9)

As relative velocity v follows normal distribution, the equation can be rewritten as

$$\begin{array}{cc}& f\left(t\right)=\frac{L}{t^{\mathrm{2}}\sqrt{\mathrm{2}\pi }\sigma }{e}^{-(L/t-\mu {)}^{\mathrm{2}}/\mathrm{2}{\sigma }^{\mathrm{2}}},\end{array}$$

(10)

where μ and σ are the mean and standard deviation of relative speed. Therefore, expected link duration could be computed as follows:

$$\begin{array}{cc}& E\left(T\right)={{\displaystyle \int }}_{\mathrm{0}}^{\infty }‍tf\left(t\right)dt.\end{array}$$

(11)

Because relative velocity v follows normal distribution, we know almost 99% of v fall within the range [ $\mu -\mathrm{4}\sigma ,\mu +\mathrm{4}\sigma$ ]. So we define the minimum and maximum possible relative speeds as $\mu -\mathrm{4}\sigma$ and $\mu +\mathrm{4}\sigma$ , respectively. Therefore, the integration interval could be reduced from [ $\mathrm{0},\infty$ ] to [ $L/(\mu +\mathrm{4}\sigma ),L/(\mu -\mathrm{4}\sigma )$ ]. Finally, the expected link duration is calculated by the following equation:

$$\begin{array}{cc}& E\left(T\right)={{\displaystyle \int }}_{L/(\mu +\mathrm{4}\sigma )}^{L/(\mu -\mathrm{4}\sigma )}‍\frac{L}{t\sqrt{\mathrm{2}\pi }\sigma }{e}^{-(L/t-\mu {)}^{\mathrm{2}}/\mathrm{2}{\sigma }^{\mathrm{2}}}dt.\end{array}$$

(12)

3.4. Impact of Traffic Light on Link Duration Prediction

In the previous section, we assume vehicles are moving freely on road, that is, the impact of traffic light is not considered. Since it is impossible to know exactly whether a vehicle will be proceeding in its original directions or preparing to stop, we model the chance that a vehicle facing red or green signals by probability.

Although some existing works considered the impact of traffic light, they simply assume the events of two consecutive vehicles encountering traffic lights combination are independent, which is different from the real situations [25]. Instead, in our LDP model, we assume these events are not independent and thus makes our model more practical.

It is true that the movings of two vehicles are independent at the traffic lights considering the independent driving behavior in practice; however, the events of two consecutive vehicles encountering traffic lights combination are dependent [25]. In other words, what traffic signal the second car faces is highly dependent upon the traffic signal that the first car encounters. This phenomenon has been observed and modeled in [25]. The probability that two cars $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ facing red traffic lights is defined as [25]

$$\begin{array}{cc}& \mathrm{Pr}\left\{n_{\mathrm{1}}\left(r\right)\right\}·\mathrm{Pr}\left\{n_{\mathrm{2}}\left(r\right)\mid n_{\mathrm{1}}\left(r\right)\right\},\end{array}$$

(13)

where the conditional probability $\mathrm{Pr}\{n_{\mathrm{2}}(r)\mid n_{\mathrm{1}}(r)\}$ can be computed from the relative speed and distance of these two vehicles. It is calculated as

$$\begin{array}{cc}& \mathrm{Pr}\left\{n_{\mathrm{2}}\left(r\right)\mid n_{\mathrm{1}}\left(r\right)\right\}=\mathrm{Pr}\left\{t_r-t_{\mathrm{1}}\ge \frac{L}{{\mu }_{\mathrm{12}}}\right\},\end{array}$$

(14)

where L is the intervehicle distance when $n_{\mathrm{1}}$ arrives the intersection, $L/{\mu }_{\mathrm{12}}$ is the time $n_{\mathrm{2}}$ takes to reach the intersection, $t_r$ is the period of red signal, and $t_{\mathrm{1}}$ is the time when $n_{\mathrm{1}}$ arrives the intersection. So $t_r-t_{\mathrm{1}}$ is the residual duration of red signal after $n_{\mathrm{1}}$ arrives.

This probability is not a constant and it depends on the time when $n_{\mathrm{1}}$ first arrives the intersection. By assuming events of two consecutive vehicles encountering traffic lights combination are dependent, we refine the proposed link duration prediction model as follows.

When vehicles $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ get close to an intersection, their movements might be significantly affected by the traffic light located in the intersection. As shown in Figure 3, $n_{\mathrm{1}}$ may continue to proceed on the road if faces green signal or stop in front of the traffic light during red signal. Similar situation might occur on vehicle $n_{\mathrm{2}}$ as well. Even if we know what traffic signal a vehicle will have, for example, a red signal, it is impossible to know how long it will be stopped by this signal.

Figure 3

Illustration of the impact of traffic light on vehicles’ movements.

Fortunately, we find the times ( $t_{\mathrm{1}}$ and $t_{\mathrm{2}}$ ) when $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ arrive the intersection are computable values. Based on the time difference between $t_{\mathrm{1}}$ and $t_{\mathrm{2}}$ , we can model what signal and how long a vehicle faces in probability. As shown in Figure 3, $n_{\mathrm{1}}$ is $L_{\mathrm{1}}$ away from the intersection, the expected time of arriving the traffic light $E(t_{\mathrm{1}})$ can be computed from (12) by substituting d for L, so does the $E(t_{\mathrm{2}})$ .

As shown in Figure 4, given the arriving time difference between $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ , we can construct a “dumbbell” with vehicles as the two balls and the length bar indicates $t_{\mathrm{2}}-t_{\mathrm{1}}$ . Then, the dumbbell is randomly put down on a line composed of alternating red and green segments, which present the periods of red and green traffic signals. Since the dumbbell's position on the line follows uniform distribution, the probability of each position will be $(t_{\mathrm{2}}-t_{\mathrm{1}})/(t_g+t_r)$ where $t_g$ and $t_r$ are the red and green signal times. Assume the dumbbell is placed on the line as shown in Figure 4, we can see the first vehicle faces green light and the second one faces red light. In addition, the time period during which the first (second) car faces green (red) light is computable. To compute the expected link duration of a particular scenario, we need to refer to Figure 3.

Figure 4

Illustration of the waiting times of vehicles in front of traffic lights.

We assume vehicles $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ are located on the same side of an intersection, $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ move in the same direction, $n_{\mathrm{1}}$ is in front of $n_{\mathrm{2}}$ , and the mean velocity ${\mu }_{\mathrm{1}}$ is greater than ${\mu }_{\mathrm{2}}$ . In the case shown in Figure 3(a), green light allows both $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ go through the intersection without stopping. Setting $L=R-d$ in (12), the expected link breaking time t is computable.

In the second case Figure 3(b), only $n_{\mathrm{2}}$ stops in front of red signal. It is possible that the link breaks within $(\mathrm{0},t_{\mathrm{21}})$ , $(t_{\mathrm{21}},t_{\mathrm{22}})$ , or $(t_{\mathrm{22}},\infty )$ depending on their relative speed, and so forth. If the link break during $(\mathrm{0},t_{\mathrm{21}})$ , we use $L=R-d$ in (12) to compute the expected link duration time. If link breaking occurs within $(t_{\mathrm{21}},t_{\mathrm{22}})$ , in (12), relative speed v is updated to $v_{\mathrm{1}}$ and $L=R-d^{\prime }$ . Otherwise, link breaks after $t_{\mathrm{22}}$ , we use (12) with $L=R-d^{\mathrm{\prime \prime }}$ to compute the link breaking time.

For the third case shown in Figure 3(c) where only $n_{\mathrm{1}}$ stops in front of red signal, we first need to determine whether the link breaks in $(\mathrm{0},t_{\mathrm{11}})$ , $(t_{\mathrm{12}},\infty )$ . For the first situation, L in (12) is set $R-d$ . For the latter situation, L in (12) is set $R-d^{\prime }$ .

The fourth case shown in Figure 3(d) is more complicated than other cases. As both of these two vehicles are stopped by red traffic light, there are five possible periods in which the link between them could break, that is, ( $\mathrm{0},t_{\mathrm{11}}$ ), $(t_{\mathrm{12}},t_{\mathrm{21}})$ , $(t_{\mathrm{21}},t_{\mathrm{22}})$ , or $(t_{\mathrm{22}},\infty )$ . If the link breaks within a certain time period (e.g. after $t_{\mathrm{22}}$ ), the relative velocity and relative travelling distance should be updated accordingly.

We only discuss the cases where $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ on one side of the intersection, it is possible that $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ are on different sides of the intersection. Also, $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ may move in different directions, $n_{\mathrm{1}}$ might be behind $n_{\mathrm{2}}$ and ${\mu }_{\mathrm{1}}<{\mu }_{\mathrm{2}}$ . For these different cases, similar approach can still be applied in computing link durations. Due to space limit, we do not present them in the paper.

3.5. Link Duration Prediction Process

Based on the link duration prediction model mentioned in previous sections, each vehicle could predict the link duration between itself and any nearby vehicles within its communication range.

At a certain time, suppose vehicles $n_i$ and $n_j$ is connected. Based on the velocity distributions of $v_i$ and $v_j$ and the relative distance between $n_i$ and $n_j$ , the link duration between these two cars could be estimated. Suppose the sliding window size on each car is 10, then vehicle $n_j$ saves its most recent 10 velocity samples ( $v_{j\mathrm{1}},v_{j\mathrm{2}},\dots ,v_{j\mathrm{10}}$ ). These 10 velocity samples will then be broadcasted to nearby vehicles in the next beacon period. Since vehicle $n_i$ is within $n_j$ 's range, these velocity samples will be received on $n_i$ . Comparing to its own velocity samples, $n_i$ can compute the relative velocities ( $v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_{\mathrm{10}}$ ), where $v_l=v_{il}-v_{jl},l=\mathrm{1,2},\dots ,\mathrm{10}$ . From ( $v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_{\mathrm{10}}$ ), the distribution of relative velocity between vehicles $n_i$ and $n_j$ can be estimated according to (6) and (7). Within each beacon message, a vehicle will also include its location information, so the initial relative distance $L_{ij}$ between $n_i$ and $n_j$ can be computed as well. Substituting the estimated ${\mu }_{ij}$ , ${\sigma }_{ij}$ and $L_{ij}$ for μ, σ and L in (12), the expected link duration time between $n_i$ and $n_j$ is computed.

A vehicle's speed may drastically decrease due to a sudden break of font cars or increase if it overtakes another car. Such sudden changes in relative velocity could trigger a large change in link duration prediction results. To avoid such issue, we preprocess a vehicle's velocity by adopting the EMA (Exponential Moving Average) method. Consider

$$\begin{array}{cc}& V_l=\alpha ·v_l+\left(\mathrm{1}-\alpha \right)·V_{l-\mathrm{1}},\end{array}$$

(15)

where $V_l$ is the processed velocity at time l and $v_l$ is the vehicle's instantaneous velocity at time l. Since $V_l$ is the linear combination of the velocity samples from time $\mathrm{0}$ to l, and $v_{\mathrm{0}}$ to $v_l$ follow normal distribution, $V_l$ also follows normal distribution. In other words, the proposed prediction model is still applicable on velocity samples processed by EMA.

The process of predicting link duration between vehicles $n_i$ and $n_j$ is shown in Figure 5.

Figure 5

Flowchart of predicting link duration between vehicles $n_i$ and $n_j$ .

When vehicle $n_i$ receives a beacon message sent from $n_j$ , it first checks whether $n_j$ is moving in the same direction as it does. If $n_j$ is moving in the same direction, their average relative speed will be ${\mu }_i-{\mu }_j$ ; otherwise, it is ${\mu }_i+{\mu }_j$ . In some special cases, the values of ${\mu }_i-{\mu }_j$ and ${\mu }_i+{\mu }_j$ may be very small, for example, $n_i$ and $n_j$ stop in front of a traffic light (in city scenarios). In these cases, it is impossible to accurately predict link duration because expected link duration goes to infinity as relative speed approaches to zero. Therefore, we skip the prediction step when relative speed is less than a threshold ${\mu }_t$ and reuse the previous prediction results. The threshold parameter ${\mu }_t$ is adjustable and set as 1 m/s in our experiments.

4. Evaluations of the LDP Model

Because mobility model of vehicles in VANETs is an important factor affecting the accuracy of the LDP model, we generated vehicles’ movements by VanetMobiSim [27] whose mobility patterns have been validated against TSIS-CORSIM, a well-known and validated traffic generator. The VanetMobiSim features new realistic automotive motion models at both macroscopic and microscopic levels and also supports traffic lights, lane changes, and speed regulations.

While predicting the link duration between two connected vehicles, LDP considers two major factors: distribution of relative speed and traffic lights. To evaluate the performance of LDP, we construct two scenarios to reflect the impacts of the above two factors. First, in highway scenarios where vehicles move with relatively stable speeds, we evaluate how distributions of relative speed will affect the model's accuracy. Second, in city scenarios where vehicles frequently change their speeds due to traffic lights, we evaluate how traffic light will affect the model. In both highway and city scenarios, the relative moving direction between two vehicles also significantly affect LDP's performance. When two vehicles move towards (away from) each others, the relative distance between them keeps decreasing (increasing), and thus LDP can accurately predict the link duration between them. However, when two vehicles move in the same direction, the following vehicle may or may not overtake the leading vehicle, resulting in inaccuracy in prediction results.

4.1. Highway Scenarios

In VanetMobiSim, we deployed 100 vehicles on a 5000 m-long four-lane divided highway. The maximum and minimum vehicle velocities are set as 18 m/s and 34 m/s, respectively. The acceleration and deceleration factors are configured as 3 m/s² and 3 m/s², respectively. Details of the simulation setup are listed in Table 1. To understand how relative moving direction will affect the LDP model, we group vehicle pairs in two categories: $(1)$ vehicles moving in different directions, and $(2)$ vehicles moving in the same direction. At every second, each vehicle collects its own and neighbors’ speeds and computes their relative speeds and distances. Then, based on these parameters and the model introduced in Section 3, a predicted link duration is computed. From tracefiles, we can easily find the link breaking time of any pair of connected vehicles, which will be serving as the ground truth.

Table 1

Simulation setup parameters in highway scenarios.

Length	5000 m
$$V_{\max }$$	34 m/s
$$V_{\min }$$	18 m/s
a	3 m/s2
b	2 m/s2
Number of lanes	4
Communication range	250 m
Simulation time	300 s

4.1.1. Same Moving Direction on Highway

We randomly select two vehicles moving in the same direction and plot their mean velocities over time in Figure 6. From this figure, we can see that the mean velocities of these two vehicles do not change over time, so does mean relative velocity between them. Figure 7 indicates that vehicles in highway scenarios move with stable velocities.

Figure 6

Mean absolute and relative velocities of two nodes in highway scenarios.

Figure 7

Standard deviation of absolute and relative velocities of two nodes in highway scenarios.

Since there is no traffic light on highway, LDP can accurately predict the link duration between these two vehicles. As shown in Figure 8, these two vehicles connect to each others at the $\mathrm{1}\text{st}$ second and disconnect at the $\mathrm{46}\text{th}$ second. The predicted and real link duration are very close to each other, indicating LDP provides accurate prediction results. We further define the prediction error as the difference between predicated and real link duration times divided by the real link duration time. The CDF of LDP's prediction error is shown in Figure 9, which indicates that LDP's errors are less than 10% for more than 85% of the predictions.

Figure 8

Link duration of two randomly selected nodes in highway scenarios.

Figure 9

CDF of predication errors in highway scenarios.

Furthermore, we randomly select 10 pairs of vehicles moving in the same direction and plot the average prediction error of LDP for these 10 pairs in Figure 10. As we can see, most average prediction errors are around 10%, which are accurate enough to support most applications.

Figure 10

Mean predication errors of 10 randomly selected nodes in highway scenarios.

4.1.2. Opposite Moving Directions on Highway

If two vehicles move in the same direction, their relative distance might increase or decrease depending on their relative speed, that is, the larger the relative speed, the longer the relative distance. However, in cases where vehicles are moving (away from each others) on different directions, their relative distance will keep increasing, which makes the link duration prediction model more accurate. When they are moving towards each others, their relative speed will keep reducing till zero and start increasing continuously.

To validate the predication accuracy of LDP, two vehicles moving in opposite directions are randomly selected from the simulations. The mean and standard deviation of their absolute and relative velocities are plotted in Figures 11 and 12. From these figures, we could see that the second car's velocity significantly changes after 6 s but the first car moves with a relatively constant speed.

Figure 11

Mean absolute and relative velocities of two nodes moving in different directions in highway scenarios.

Figure 12

Standard deviation of absolute and relative velocities of two nodes moving in different direction in highway scenarios.

As these two vehicles move away from each other, their relative distance keeps increasing. As shown in Figure 13, these two vehicles are connected for a shorter period of time comparing to the cases where two cars move in the same direction. This is because their relative distance rapidly increases and quickly they are out of communication range. Because the predicted and real link duration are close to each others, we further plot the CDF of LDP's prediction error in Figure 14. As we can see, the maximum error is only 5% and around 60% of results have errors less than 1%.

Figure 13

Link duration of two nodes moving in different directions in highway scenarios.

Figure 14

CDF of predication errors in highway scenarios.

We randomly select other 9 pairs of vehicles moving in different directions. Together with the above-analyzed pair, we plot the average prediction errors of these 10-pair vehicles in Figure 15. The overall prediction errors of vehicles moving in different directions are less than those moving in the same direction. That also means LDP could more accurately predict link duration for vehicles moving towards or away from each others.

Figure 15

Mean predication errors of 10 pairs of nodes moving in different directions in highway scenarios.

4.2. City Scenario

Predicting link duration of two vehicles moving in city scenarios is a challenging problem as it is difficult to predict what type of traffic signal a vehicle will face. To simulate a simplified city scenario, simulation parameters in VanetMobiSim are configure as listed in Table 2. In the simulation, two 1000 m road segments are connected at an interaction with a traffic light of 36 s red signal and 36 s green signal. There is a total of 70 vehicles deployed on these two road segments. Based their moving directions, vehicle pairs are classified into two groups: $(1)$ these moving in the same direction and $(2)$ on different directions.

Table 2

Simulation setup parameters in city scenarios.

Length	2000 m
$$V_{\max }$$	14 m/s
$$V_{\min }$$	5 m/s
a	3 m/s2
b	3 m/s2
Number of lanes	4
Period of traffic light	72 s
Communication range	250 m
Simulation time	500 s

4.2.1. Same Moving Direction in City Scenario

Figure 16 plots the predicted and real link duration of a randomly chosen pair of vehicles which move in the same direction in the city scenario. From this figure, we can see that the prediction errors become smaller as the simulation time increases. When these two cars are initially connected at the 1st second, the prediction error is around 20%. This is because the relative distance and velocity of these two cars change drastically during the time period [ $0,45$ ], not even mention the impact of traffic lights. When the time gets closer to 45 s, the uncertainty in the prediction results reduces, so do the prediction errors.

Figure 16

Link duration of two randomly selected nodes in city scenarios.

To understand the fluctuation of data in Figure 16, we further plot the absolute and relative velocities of these two vehicles in Figure 17. While the first vehicle $n_{\mathrm{1}}$ moves with a relatively constant speed, the second vehicle $n_{\mathrm{2}}$ starts with a speed of 0 m/s (stops in front of the traffic light), then increases linearly to about 12 m/s, and finally moves with this speed. As a result, the relative speed between these two vehicles changes differently in the following three time intervals: [0, 15), [15, 25), and [25, 45). During the time interval [0, 11), $n_{\mathrm{2}}$ stops in front of the traffic light, and $n_{\mathrm{1}}$ moves towards $n_{\mathrm{2}}$ , thus, their relative distance decreases. In this case, the predicted distance will be $R+d$ in (12). At time 11 s, $n_{\mathrm{2}}$ starts to move and the relative distance between $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ increases slowly. Since we do not know what traffic signal $n_{\mathrm{1}}$ will be facing, the expected link duration suddenly drops at 14 s. From 15 s to 21 s, the relative distance between $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ keeps decreasing. After 22 s, the velocity of $n_{\mathrm{2}}$ becomes larger than $n_{\mathrm{1}}$ , that is, the relative distance between $n_{\mathrm{1}}$ and $n_{\mathrm{2}}$ starts increasing again. In this case, the predicted distance in (12) will be set as $R-d$ . After 25 s, since there is no need to change the predicted distance and relative speed becomes stable, the prediction error becomes very small.

Figure 17

Mean absolute and relative velocities of two nodes in city scenarios.

From the above analysis, we can see that the stability of vehicle's speed is very important to the accuracy of LDP. As shown in Figure 18, the huge fluctuations of $n_{\mathrm{2}}$ 's speeds cause large deviations in relative speeds, resulting in large errors in predicted results. We also plot the CDF of errors for all prediction results in Figure 19. We find that about 60% predictions have errors less than 20%.

Figure 18

Standard deviation of absolute and relative velocities of two nodes in city scenarios.

Figure 19

CDF of predication errors in city scenarios.

To evaluate LDP's performance for vehicles moving in the same direction in city scenarios, we pick 9 more pairs of vehicles and plot their prediction errors in Figure 20. As we can see from this figure, most of the average prediction errors are around 20%. There are some results containing errors as large as 80%, which are caused mainly by two reasons: $(1)$ staying too long in front the traffic light and $(2)$ rapid velocity changes. The first reason is more harmful because no useful speed information could be collected from vehicles stopping in front of the traffic light. We suggest that the LDP model should be used for moving vehicles instead of stationary ones. As we are interested in link duration prediction for highly dynamic vehicular networks, assuming vehicles moving on road is reasonable.

Figure 20

Mean predication errors of 10 randomly selected nodes in city scenarios.

4.2.2. Different Moving Directions in City Scenario

When two vehicles move in different directions, the link duration is easier to predict compared to those moving in the same direction.

The absolute and relative speeds of two randomly chosen vehicles (moving on different directions) are shown in Figure 21. We also plot the standard deviation of their absolute and relative velocities in Figure 22. As they are moving away from each other, the relative speed is actually the sum of their absolute speeds. After 35 s, the second vehicle's speed becomes zero, that is, it stops in front of the traffic light.

Figure 21

Mean absolute and relative velocities of two nodes moving in different directions in city scenarios.

Figure 22

Standard deviation of absolute and relative velocities of two nodes moving in different directions in city scenarios.

For these two vehicles, we plot the predicted and real link duration values in Figure 23 and the CDF of prediction errors in Figure 24. From Figure 23, we can see that the predicted results closely follow the real ones with little fluctuations. Figure 24 indicates around 75% of predictions have errors less than 20%.

Figure 23

Link duration of two nodes moving in different directions in city scenarios.

Figure 24

CDF of predication errors in city scenarios.

Besides this pair of vehicles, we randomly select 9 more pair of vehicles, of which each pair moves in different directions. The overall prediction errors of these 10 pairs of vehicles are plotted in Figure 25. As we expected, the average errors in Figure 25 are smaller than those in Figure 20. These results again support our conclusion that LDP can more accurately predict link duration for vehicles moving in different directions.

Figure 25

Mean predication errors of 10 pairs of nodes moving in different directions in city scenarios.

4.3. Numerical Analysis of LDP

To understand how the LDP model performs with different parameters, we plot predicated link duration with different μ, σ, and L in Figure 26. In the figure, $\mu \in (\mathrm{0,20})$ and $\sigma \in (\mathrm{0,5})$ ; L is set as $\mathrm{50}$  m, $\mathrm{100}$  m, $\mathrm{150}$  m, and $\mathrm{200}$  m. We can see from the figure that, when L and σ are fixed, link duration increases as μ decreases. Particularly, when $\mu \in (\mathrm{0,10})$ , link duration changes drastically. When μ and L are fixed, link duration increases as σ decreases. When σ approaches to zero, the changes of link duration are significant. If μ and σ do not change, link duration increases when L increases. When $\mu >\mathrm{10}$ , the changes of link duration are negligible no matter how σ and L change. We also discover that μ affects link duration more significantly than other two parameters.

Figure 26

Impacts of μ, σ, and L on the link duration predictions.

5. Conclusion

A novel link duration prediction model is proposed for VANETs leveraging the distribution of relative speed instead of instantaneous velocity. Besides relative speed, the model considers intervehicle distance and the impact of traffic light in predicting link duration. Based on the model, a practical solution is designed so that a vehicle can dynamically estimate the link lifetimes between itself and any connected vehicles. Among all parameters, average relative speed is the most important factor affecting link duration; therefore, accurately estimating this parameter becomes extremely important. To avoid the influence of sudden velocity changes, we applied EMA on collected velocity samples to filter outliers.

Simulation results show that the LDP model is suitable and practical for accurately predicting link duration in VANETs. Particularly, more accurate predictions are achieved in highway scenarios where vehicles moving in different directions. Because each vehicle only needs to collect and share 10 latest velocity samples to its neighbors, the overhead of the proposed work is small. We plan to further validate the LDP model by real-world dataset and extend the model by considering vehicles turning at intersections.