01.12.2017  Research  Ausgabe 1/2017 Open Access
Link residual lifetimebased next hop selection scheme for vehicular ad hoc networks
1 Introduction
Vehicular Ad Hoc Networks (VANETs), an integral component of intelligent transportation systems (ITS), are aimed to provide support for road safety, traffic management and comfort applications by enabling communication in two distinct modes: vehicletovehicle (V2V) and vehicletoinfrastructure (V2I) [
1]. Since the nodes in VANETs (i.e., vehicles with onboard units) move with very high speed, the network topology is highly dynamic and consequently the intervehicle communication links will be highly unstable or may even become disconnected frequently. A route that is established between a sourcedestination pair through a sequence of road segments will cease to be invalid when at least one communication link along the route fails. Hence, it is very important and desirable for the routing algorithm to choose an optimal route consisting of highly reliable links in the network [
2].
Generally, routing within a road segment is performed using a greedy forwarding approach in which the tagged node carrying a data packet will select a vehicle from among its neighboring set that is closer to destination or the next junction, for forwarding the data packet. The greedy forwarding approach is continued until the next junction or the destination is reached. Geographic routing, which is the preferred means of routing in VANETs, also employs greedy forwarding approach [
3]. Adoption of greedy forwarding reduces the number of hops for a packet to move from the source to the destination leading to a decrease of endtoend delay experienced by the packet. However, greedy forwarding does not take into account the quality and reliability of the link that is chosen for forwarding the packet. In VANETs, since the established link may become highly unreliable from time to time, the probability of packet transmission failure may become very high when greedy forwarding is employed. This in turn can result in more retransmissions leading to reduction of the network throughput and significant increase of endtoend delay.
Anzeige
The mean link lifetime is defined as the mean time period for which two vehicles are within the communication range of each other, while the residual lifetime of an existing link is defined as the time duration from the current time until the time the link breaks. Both these quantities have direct impact on many performance metrics such as route reliability, packet delivery ratio, throughput, and endtoend delay of the network. Accurate knowledge of mean link lifetime and the residual lifetime of existing links will aid the design of reliability based routing protocols to improve the routing performance, and to achieve the desired network performance.
In this paper, we propose a method for the selection of next hop forwarding node in VANETs that improves the reliability of communication links along the path from source to destination. In the proposed method, a packetcarrying vehicular node (i.e., source vehicle) selects a forwarding vehicle from a given set of candidate vehicles by estimating the residual lifetime of the corresponding individual communication links. We present an algorithm to predict the link residual lifetime in VANETs by making use of Kalman filter based prediction technique. The proposed method relies on predicting the relative location and speed of vehicular nodes using Kalman filter. Once the estimates for the residual lifetimes of all the probable onehop links are available, a vehicle belonging to the forwarding set that result in maximum value for the link residual lifetime is chosen as the forwarding vehicle. Simulation results reveal that the proposed scheme significantly improves the packet delivery ratio. The rest of the paper is organized as follows: In the Section
2, we briefly describe the related work. The system model employed for the analysis is presented in Section
3.1. In Section
3.2, we describe a procedure for the prediction of link residual lifetime based on Kalman filter. In Section
3.3, we present the residual lifetime based approach for packet forwarding. The simulation results are presented in Section
4, and finally, the paper is concluded in Section
5.
2 Related work
Several papers have recently appeared that deal with the design of reliable routing protocols for VANETs [
4–
20]. In [
4], Taleb et al. describe a reliable routing protocol in which vehicles are grouped according to their velocity vectors and, the routing algorithm dynamically searches for the most stable route that includes only hops from the same group of vehicles. S. Wan et al. [
5] propose a reliable routing protocol for V2I networks on rural highways based on prediction of link lifetime. However, the proposed protocol requires the exchange of a large number of route request (RREQ) and route reply (RREP) packets. Namboodiri et al. [
6] describe a routing algorithm, specifically tailored to the mobile gateway scenario, that predicts how long a route will last and creates a new route before the failure of the existing route. In [
7], Menouar et al. describe a routing algorithm, that can predict the future coordinates of a vehicle and build new stable routes. In [
8], the same authors propose a movement predictionbased routing (MOPR) in which each vehicle estimates the link stability for each neighboring vehicle before selecting the next hop for data forwarding. In the above mentioned papers, the link lifetime is computed by assuming vehicle speed to be a constant. Sofra et al. [
9] discuss an algorithm capable of finding reliable routes in VANETs. In [
10], Rao et al. present a protocol called GPSRL, an improved version of greedy perimeter stateless routing (GPSR) protocol that takes into account the link lifetime to ensure reliable routing. However, the author assumes vehicle velocity to be a constant for finding the link lifetime. In [
11], Eiza et al. propose a reliable routing protocol known as AODVR by incorporating link reliability metric in the original AODV routing protocol. In [
12], Niu et al. describes a QoS routing algorithm based on the AODV protocol and a criterion for link reliability. In [
13], Yu et al. present a routing procedure, AODVVANET, that use vehicle’s movement information in the route discovery process. Notice that protocols described in [
11–
13] are based on AODV. Recently several studies have reported that, topology based routing schemes such as AODV performs badly in VANETs, as compared to the geographic routing protocols [
3].
In [
14], Eiza and Ni propose a reliable routing algorithm that exploits the evolving characteristics of VANETs on highway. Naumov et al. in [
15], propose connectivity aware routing (CAR), which adapts to current network conditions to find a route with sufficient connectivity, so as to maximize the chance of successful packet delivery. In [
16], Boukerche et al. describe a routing approach for providing QoS in VANETs in which the link reliability is estimated based on exchange of beacons among vehicles. Shelly et al. [
17] propose an enhancement for the wellknown GPSR protocol, which exploits information about link reliability for the selection of forwarding node. In [
18], Yu et al. propose a routing protocol for VANETs based on vehicle density so as to provide fast and reliable message delivery. In [
19], Cai et al. propose a link state aware geographic opportunistic (LSGO) routing protocol, in which the forwarding nodes are selected based on their geographic location and the link quality. Here, the link quality is expressed in terms of a metric known as expected transmission count (ETX), which is the expected number of data transmissions required to send a packet over the sourcedestination link. However, the computation of ETX involves exchange of Hello packets across each link, leading to significant increase in the overhead. Further, ETX is computed by considering transmission of Hello packets during a window of
w seconds (s), leading to higher endtoend delay. Wang et al. [
20] propose a Stochastic Minimumhops Forwarding Routing (SMFR) algorithm for VANETs with heterogeneous types of vehicles that minimizes the number of hops to the destination. However, the work reported in [
20] does not consider link reliability for the selection of endtoend route. Since VANETs are poised to support critical road safety related applications in a highly dynamic environment, communication reliability along the endtoend route is of prime importance as compared to other design criterion such as the number of hops along the route, as investigated in [
20]. Accordingly, it is desirable for the routing protocol to consider link reliability when vehicles are chosen for forwarding the packet.
Anzeige
When routing in VANETs is considered, the main disadvantage of the traditional greedy forwarding method is that next hop selection procedure does not consider the quality and reliability of the resulting link. While the source vehicle forwards the data packet to the vehicle closest to the destination node under traditional greedy forwarding, it is very important to consider the residual lifetime of the link formed by the source vehicle and the selected onehop neighbor. This is because, if the residual lifetime of the newly formed link is very low, the probability of packet transmission failure is very high that will lead to more retransmissions and deterioration of the network throughput. In this paper, we investigate the problem of improving communication reliability when a source vehicle selects next hop nodes for data forwarding. We propose a method for the selection of reliable onehop neighbor based on the residual lifetime of the corresponding communication link. To meet this objective, we present an algorithm to predict the residual lifetime of links in VANETs by making use of Kalman filter based prediction technique. In this case, a source vehicle tries to predict the residual lifetime of onehop links to all the available neighbor vehicles. The neighbor with maximum value for the link residual lifetime is chosen as the nexthop forwarding vehicle. Kalman filter is a recursive filter that can be used to estimate the state of a linear dynamic system from a series of noisy measurements [
21]. A major advantage of Kalman filter is that they can quickly and efficiently compute estimates and can be used for both state estimation and prediction. Kalman filter is a convenient tool for online realtime processing of data. The optimal estimate is derived by the Kalman filter based on minimizing the mean square error [
22]. Due to the simplicity and robust nature of the Kalman filter, they are extensively used for velocity and location prediction techniques in ad hoc networks [
23–
25].
3 Proposed method
In this section, we describe the procedure for the selection of nexthop forwarding vehicle that relies on estimates of link residual lifetime. We begin this section by introducing the system model employed throughout the paper and then describe the residual lifetime estimation procedure. This is followed by a description of the proposed method for the next hop selection.
3.1 System model
We consider a scenario in which vehicles move on a straight lane highway and drivers can drive independent of the other vehicles on the highway. Further, we assume all the vehicles to move in the same direction as shown in Fig.
1. We make use of vehicle’s effective transmission range
R
_{ eff } for the analysis of residual lifetime. Under the distance dependent path loss model, the received power at distance
d away from a given transmitter is given by
P
_{ r }(
d)=
P
_{ t }
β(
d
_{0}/
d)
^{ α } where
α is the path loss exponent;
d
_{0} is a reference distance close to the transmitter; and
P
_{ t } is the transmit power of the node. Here
β=(
G
_{ T }
G
_{ R }
λ
^{2})/(2
π
d
_{0})
^{2} where
G
_{ T } and
G
_{ R }, respectively, represent the gain of transmitting and receiving antennas (assumed to be equal to 1) and
λ is the wavelength. The received power at distance
d by embedding the effect of path loss, shadowing and multipath fading can be written as [
26]:
$$\begin{array}{@{}rcl@{}} P_{r}(d) &=& P_{t} + 10{log}_{10}\beta  10\alpha {log}_{10}(d/d_{0})\\ && 10{log}_{10}E\left[\chi^{2}\right]  \psi_{s} \end{array} $$
(1)
×
where 10
log
_{10}
E[
χ
^{2}] is the average power due to multipath fading in dB and
ψ
_{ s } is a log normal distributed random variable with mean zero and variance
\(\sigma _{s}^{2}\). The Outage probability at distance
d,
P
_{ out }(
P
_{ min },
d) is defined as the probability that the received power at a given distance
d,P
_{ r }(
d) falls below
P
_{ min }. Thus the outage probability is given by
$$\begin{array}{*{20}l} P_{out}\left(P_{min},d\right) &= P\left(P_{r}(d)\preceq P_{min}\right) \\ &= 1  Q \Big[{\vphantom{\left.\left.10\alpha {log}_{10}(d/d_{0}) 10{log}_{10}E[\chi^{2}]\right) \right)/{\sigma_{s}}}}\left(P_{min}\left(P_{t} + 10{log}_{10}\beta\right.\right.\\ &\quad\left.\left.10\alpha {log}_{10}(d/d_{0}) 10{log}_{10}E\left[\chi^{2}\right]\right) \right)/{\sigma_{s}}\Big] \end{array} $$
(2)
where
Q[.] is the Q function. The probability that the received power at distance
R
_{ eff } is greater than the minimum required threshold (
P
_{ min }), is given by:
$$ {\begin{aligned} &P\left(P_{r}\left(R_{eff}\right)\succeq P_{min}\right)\\ &= Q\left[\frac {P_{min}\left(P_{t} + 10{log}_{10}\beta  10\alpha {log}_{10}\left(R_{eff}/d_{0}\right)  10{log}_{10}E\left[\chi^{2}\right]\right)}{\sigma_{s}}\right] \end{aligned}} $$
(3)
We define
R
_{ eff } as the distance at which the above probability is equal to 0.99. Assuming the reference distance for antenna far field
d
_{0} to be 1 m, we have:
$$\begin{array}{@{}rcl@{}} R_{eff} = 10^{\frac{2.33\sigma_{s} + P_{t}  P_{min} + 10{log}_{10}\beta 10{log}_{10}E\left[\chi^{2}\right]}{10\alpha}} \end{array} $$
(4)
To describe the mobility of vehicles on the highway, we consider time as partitioned into small equal length time steps of Δ
t time duration, with each time epoch represented as
t
_{ k }=Δ
t+
t
_{ k−1};
k=1,2..
n. The vehicles are assumed to move according to a GaussMarkov (GM) mobility model [
27]. In this case, vehicle speed at any time slot is a function of its previous speed, i.e; the model incorporates temporal variation of vehicle speed. The degree of temporal dependency is determined by the parameter
τ, known as time correlation factor. By adjusting
τ, we can generate various mobility scenarios for the vehicles on the highway. Let
v
_{ Ak } and
v
_{ Bk }, respectively, be the speed of vehicles A and B at the
k
^{ th } instant of time. Then, at the (
k+1)
^{ th } instant, the speed is computed as:
$$ v_{Ak+1}=\tau v_{Ak} + (1\tau)\mu_{A} + \sqrt{1\tau^{2}}~y_{Ak} $$
$$ v_{Bk+1}=\tau v_{Bk} + (1\tau)\mu_{B} + \sqrt{1\tau^{2}}~y_{Bk} $$
(5)
In (
5),
μ
_{ A } and
μ
_{ B } are the mean speed of vehicles
A and
B, respectively. For the single lane case, we consider
μ
_{ A }=
μ
_{ B }=
μ. Further,
y
_{ Ak } and
y
_{ Bk } are independent, uncorrelated and stationary Gaussian random variables with zero mean and standard deviation
σ, where
σ is the standard deviation of
v
_{ Ak } and
v
_{ Bk } [
27]. Further,
τ represents the time correlation factor of the speed which is in the range of 0≤
τ≤1. In other words,
τ shows how much the speed varies between two consecutive epochs. When
τ=0, the time correlation disappears and the vehicle speed becomes a Gaussian random variable. When the GaussMarkov model has strong memory, i.e;
τ=1, the vehicle speed at time slot
t is exactly same as its previous speed, which is equivalent to a fluidflow model. The degree of randomness in the speed is adjusted by the parameter
τ. As
τ increases, the current speed is more likely to be influenced by its previous speed. The Gauss Markov mobility model can thus be used to represent different mobility scenarios in VANETs. Since both the vehicles are assumed to be moving in the same direction, the relative speed between the two vehicles at the (
k+1)
^{ th } instant is calculated as follows:
$$\begin{array}{*{20}l} v_{Rk+1}&=v_{Ak+1}v_{Bk+1} \\ &= \tau\left(v_{Ak}  v_{Bk}\right) + \sqrt{1\tau^{2}}\left(y_{Ak}  y_{Bk}\right) \end{array} $$
(6)
Define
v
_{ Rk }=
v
_{ Ak }−
v
_{ Bk } and
y
_{ Rk }=(
y
_{ Ak }−
y
_{ Bk }),
k=1,…
n. Notice that {
y
_{ Rk }} represent independent Gaussian random variables with zero mean and standard deviation
\(\sigma _{v_{R}}=\sqrt {2}\sigma \). Thus, the relative speed at the (
k+1)
^{ th } instant of time can be expressed as:
$$ v_{Rk+1}=\tau v_{Rk} + \sqrt{1\tau^{2}}y_{Rk} $$
(7)
3.2 Residual lifetime prediction using Kalman filter
The Kalman filter is a recursive filter that can be used to estimate the state of a linear dynamic system from a series of noisy measurements [
21]. Consider two vehicles
A and
B moving in the network as shown in Fig.
2. Even though both A and B move according to the GaussMarkov mobility model, for simplicity, we assume that the vehicle A is static and the vehicle B moves with the relative speed as defined in the Eq. (
7). Further, we assume that the vehicle A is placed at the origin (0,0) of the Cartesian system. Since we consider straight line highway scenario for the analysis, the coordinate
y has no importance. Whenever vehicle B is within the coordinates (−
R
_{ eff },0) and (
R
_{ eff },0), we say that the link between vehicles
A and
B is alive. When vehicle B enters the communication range of vehicle A, the latter receives beacon message and predicts the distance travelled by the vehicle B and the relative speed, by using Kalman filter. The predicted location and relative speed results are used to find the estimate for residual lifetime.
×
The Kalman filter recursively predicts the state variable at each time step
t
_{ k }: the
x coordinate of the vehicular node B i.e the distance travelled by the node B. Thus the process equations used to predict the state of the system at a given time instant
k+1 are defined as follows:
$$\begin{array}{@{}rcl@{}} v_{Rk+1}=\tau v_{Rk} + \sqrt{1\tau^{2}}y_{Rk} \\ x_{k+1}=x_{k} + \varDelta t v_{Rk} + y_{xk} \end{array} $$
(8)
Here,
x
_{ k+1} and
x
_{ k } are the location of vehicle B at the (
k+1)
^{ th } and
k
^{ th } time duration, respectively;
v
_{ Rk+1} and
v
_{ Rk } are the relative speed between the two vehicles at the (
k+1)
^{ th } and
k
^{ th } time duration, respectively;
y
_{ xk } is the process noise which is assumed to be Gaussian with zero mean and standard deviation
σ
_{ x }. Thus, the process equation can be written in matrix form as:
$$\begin{array}{@{}rcl@{}} \left[\begin{array}{c} v_{Rk+1}\\ x_{k+1} \end{array}\right] = \left[\begin{array}{cc} \tau & 0 \\ \varDelta t & 1 \end{array}\right] \left[\begin{array}{c} v_{Rk} \\[0.3em] x_{k} \end{array}\right] + \left[\begin{array}{c} \sqrt{1\tau^{2}}y_{Rk} \\ y_{xk} \end{array}\right] \end{array} $$
(9)
Notice that Eq. (
9) represents the general form of the process equation given by
X
_{ k+1}=
AX
_{ k }+
w
_{ k }, where
X
_{ k+1} is the state vector which describes dynamic behaviour of the system at (
k+1)
^{ th } instance of time,
A is the state transition matrix at time
k;
w
_{ k } is the system error which is assumed to be Gaussian with mean zero and covariance matrix
Q. For starting the Kalman filter recursive steps, the process noise covariance matrix
Q must be known which can be obtained as
$$\begin{array}{*{20}l} Q &= E\left[w_{k}w_{k}^{\ast}\right] \\ &= \left[\begin{array}{cc} (1\tau)^{2} \sigma_{Rk} & 0 \\ 0 & \sigma_{xk} \end{array}\right] \end{array} $$
(10)
where
^{∗} corresponds to complex conjugate. In the measurement update stage, we adjust estimation of the unknown state
X
_{ k } based on the measurement values
Z
_{ k }. Here, the position and the speed of the neighboring vehicles are obtained from the beacon messages at the vehicular node A. The measurement equation at the
k
^{ th } instant of time is
Z
_{ k }=
HX
_{ k }+
u
_{ k }, where
Z
_{ k } is the measurement vector,
H is the measurement matrix and
u
_{ k } is the measurement noise which is also Gaussian with zero mean and covariance matrix
R. From the measurement equation, the measurement matrix and covariance matrix
R are given by [
25]
$$ H= \left[\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right] ; R= \left[\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right] $$
(11)
In Kalman filter, the recursive estimate of
X
_{ k } is based on the measurement values of
Z
_{ k } up to the time instant
k. Let
\(\hat {X}_{k/k1}\) be the a priori estimate of
X
_{ k } and
\(\hat {X}_{k/k}\) be its posteriori estimate. Further, let
P
_{ k/k−1} and
P
_{ k/k } respectively be the apriori and the posteriori error covariance matrices. For the Kalman filter, the estimation begins with no prior measurements. So, the initial state is fixed without any condition as follows
$$ \hat{X}_{0/1}=0 $$
(12)
For the recursive steps to start in Kalman filter, we need the knowledge of apriori error covariance matrix
P
_{ k/k−1}. The initial values for
P
_{ k/k−1}, i.e; when
k=0, is taken in such a way that the diagonal elements are very high and non diagonal elements are fixed at zero. Thus, initial value of
P
_{ k/k−1} at
k=0 is given by [
25]
$$ P_{0/1}= \left[\begin{array}{cc} 1000 & 0 \\ 0 & 1000 \end{array}\right] $$
(13)
Once the initial a priori estimates are obtained, then posteriori estimate and posteriori error covariance matrix can be calculated. The posteriori estimate
\(\hat {X}_{k/k}\) is given by [
25]:
$$ \hat{X}_{k/k}=\hat{X}_{k/k1} + K_{k}\left(Z_{k}H\hat{X}_{k/k1}\right) $$
(14)
where
K
_{ k } is the Kalman gain given by [
25]:
$$ K_{k}=P_{k/k1}H^{T}\left({HP}_{k/k1}H^{T} + R\right)^{1} $$
(15)
With the Kalman gain
K
_{ k } and a priori error covariance matrix defined, the posteriori error covariance matrix can be determined as [
25]:
$$ P_{k/k}=\left(IK_{k}H\right)P_{k/k1} $$
(16)
Then onestep ahead estimate and one step ahead error covariance matrix are given by [
22,
25]:
$$ \hat{X}_{k+1/k}=A\hat{X}_{k/k} $$
$$ P_{k+1/k} = {AP}_{k/k}A^{T}+Q $$
(17)
Based on Eqs. (
14–
17), recursive steps for the one step prediction of the location of vehicle B and the relative speed can be done.
Next, we describe the prediction of residual lifetime using the information obtained from the Kalman filter prediction method. As mentioned earlier, the residual lifetime of a link at a given instant of time is defined as the remaining amount of time during which two vehicles are within the transmission range of each other. Once the measurement value
Z
_{ k } is obtained from the beacon messages, this information is used to predict the residual lifetime of the link formed by the vehicle A and B in the (
k+1)
^{ th } time duration. Figure
3 shows the algorithm for calculating the link residual lifetime. Here, vehicle B moves with a relative speed as we described earlier. Its location and relative speed with respect to A at a particular instant of time
k+1 is predicted by using the Kalman filter available at
A. So, the predicted residual lifetime at (
k+1)
^{ th } time instant is given by
$$ \widehat{RLT}_{k+1} = \frac{R_{eff}s~\hat{x}_{k+1}}{\left\hat{v}_{Rk+1}\right} $$
(18)
×
where
R
_{ eff } is the effective transmission range;
\(\hat {x}_{k+1}\) and
\(\hat {v}_{Rk+1}\) are the predicted relative position and the relative speed of vehicle B with respect to A obtained from the Kalman filter prediction and
s is given by
$$\begin{array}{@{}rcl@{}} s=\left\{ \begin{array}{lll} 1 &{\phantom{;v_{Rk}}}&;v_{Rk+1}> 0 \\ 1 & &;v_{Rk+1}< 0 \\ \end{array}\right. \end{array} $$
(19)
3.3 Nexthop selection based on link residual lifetime
In this subsection, we describe the proposed method for nexthop selection that relies on the prediction algorithm discussed previously. It is assumed that all the vehicles possess GPS facility to know their location and speed. Each vehicle generates a beacon for every Δ
t time duration which contains the information of its location coordinates and speed. From the beacon message, a vehicle will get the measurement values from each neighbor node. A tagged vehicle, on receiving the beacon message from a node, can perform the onestep ahead prediction of the location and relative speed of the particular node, from which the residual lifetime of the corresponding link can be calculated. The tagged vehicle then forms the neighbor list by including all the onehop neighbors, their ID’s and the residual lifetime of the corresponding links. Since the tagged vehicle receives the beacon from its one hop neighbors for every Δ
t time duration, the entries in the neighbor list would get updated periodically for every Δ
t time duration. The neighbor list also gets updated when a new vehicle enters the effective transmission range of the tagged vehicle or when the tagged vehicle fails to receive beacon from a node in the neighbor list.
Figure
4 shows how the forwarding will happen in the proposed protocol. On receiving a packet, the tagged node will check whether the received one is a beacon or a data packet. If it is a beacon, it will be used to modify the neighbor list. When the tagged node receives a data packet, it has to find the next hop forwarding node. The tagged node will immediately refer the neighbor list. The forwarding node is selected in such a way that the corresponding link has maximum residual lifetime. If two or more such nodes are available, then the node closer to the destination is chosen, as the forwarding node. Since the nexthop forwarding node is selected based on residual lifetime, the probability of link breakage is reduced as compared to a greedy selection and hence the proposed scheme can improve the communication reliability. In the next section, we present the results of our implementation of the proposed method.
×
4 Simulation results
In this section, we present the results of our investigation. Initially, we perform a detailed simulation study using Matlab tool to find the
R
_{ eff } of a vehicular node for a given set of parameters such as transmit power, path loss exponent etc. We simulate a realistic channel environment with lognormal shadow fading and Rayleigh distribution for the multipath fading model, and measure the
R
_{ eff } for various channel conditions. It is observed that the
R
_{ eff } is significantly affected by path loss exponent, shadow fading standard deviation and multipath fading. Later, we use these values of
R
_{ eff } for the computation of residual lifetime of the communication links.
We evaluate the performance of proposed packet forwarding strategy and compare the results against that of conventional greedy forwarding approach. We use the Network Simulator 2.33 (NS2.33) to conduct simulation experiments [
28]. Our simulation has two components: a mobility simulator and a wireless network simulator, which are connected by trace files that specify the vehicle mobility during simulation. A realistic vehicular mobility scenario is generated by using MOVE (mobility model generator for vehicular networks) [
29] built on top of SUMO (simulation of urban mobility) [
30], which is an open source microtraffic simulation package. We simulate a 2 KM long highway in which 75 vehicles are kept uniformly distributed. Each vehicle is assigned a random speed chosen from a Gaussian distribution with mean
μ=20
m/
s and standard deviation of
σ=5
m/
s initially. Then, we analyse the network for each beacon interval (i.e; Δ
t s). The individual movement of the vehicles are based on GaussMarkov mobility model where the speed is updated for each Δ
t time duration. Accordingly, the position of the vehicles are also updated for each Δ
t s. The values of Δ
t and the time correlation factor
τ is fixed for each simulations. The mobility trace file from MOVE contains information about realistic vehicle movements (such as their location, speed and direction), which can be fed into discrete event simulators for network simulation. We record the trace files corresponding to vehicle mobility from SUMO, convert these to NS2compatible files using MOVE and use them for network simulation using NS 2.33. Each node in the network simulation represents one vehicle of the mobility simulations, moving according to the represented vehicles movement history in the trace file. In our simulations, IEEE 802.11e EDCA has been assumed as the MAC protocol and the implementation of EDCA in NS2 from the TKN group in Technical University of Berlin has been used [
31]. Currently, IEEE 802.11p draft amendments have been proposed as the PHY and MAC protocols for VANETs [
32]. IEEE 802.11p MAC uses 802.11e EDCA scheme with some modifications; while the physical layer is similar to that of the IEEE 802.11a standard. For the current simulations, even though IEEE 802.11 EDCA protocol has been used, we have not simulated multiple queues for different access categories (ACs) at each node. Instead, we assume each node to implement one queue only, i.e., each node handles one AC and single type of traffic only and we assume nodes to be always saturated; i.e., there is always a packet ready for transmission at the MAC layer of the node. The minimum contention window has been set as equal to 15 while its maximum value has been chosen as 255. Further, we use some of the parameters of IEEE 802.11p for simulations as given in Table
1 [
31,
33].
Packet size

512 (variable)

MAC header

272 bits

PHY header

128 bits

ACK

240 bits

Channel bit rate

2 Mbps

Propagation delay

2
μs

Slot time

50
μs

SIFS

28
μs

DIFS

128
μs

Simulation time

200 s

Cw
_{ min }

15

Cw
_{ max }

255

Propagation model

Tworay

Simulation

2 km long

Area/topology

Linear highway

MAC protocol

IEEE 802.11e EDCA

Each vehicle transmits its location and speed information to its neighbor vehicles through the beacons, which are transmitted every Δ
t time duration. On receiving this beacon, a tagged vehicle will calculate the relative position and relative speed with the neighboring nodes, which forms the measurement data for the Kalman filter. In the simulations, every tagged vehicle predicts the residual lifetime of the link formed with every other node that enters the communication range of the tagged vehicle. We consider the data traffic to be constant bit rate (CBR) that is attached to each source vehicle to generate packets of fixed size. We further assume user datagram protocol (UDP) as the transport layer protocol for the simulation studies. A total of 10 sourcedestination pairs are identified in the simulation which generate packets of size 512 bytes for every 0.25 s (we consider the case of variable packet size as well). Total time duration for the simulation is set as 200 s. The source vehicle will start generating the data packet after the first 10 s of the simulation time and stops generating the data packet at 150 s. For each simulation experiment, the sender/receiver node pairs are randomly selected.
We evaluate the performance of the prediction algorithm in terms of prediction inaccuracy which is defined as follows:
$$ \eta_{k+1} = \frac{\left{RLT}_{k+1}  \widehat{RLT}_{k+1}\right}{RLT_{k+1}} $$
(20)
where
RLT
_{ k+1} and
\(\widehat {RLT}_{k+1}\), respectively, are actual residual lifetime and predicted residual lifetime at a particular instance of time
k+1. We plot the histogram of the prediction inaccuracy of residual lifetime after sorting the sample values. Figure
5 shows the CDF of prediction inaccuracy for different values of Δ
t (i.e., beacon interval) with time correlation selected as
τ=0.9. The results show that when the value of Δ
t is 0.6
s or lesser, 70
% of all predictions have an inaccuracy of less than 20
%. When the value of Δ
t increases, the number of measurement values will be reduced, which results in reduction of accuracy of the prediction. Figure
6 shows the CDF of prediction inaccuracy for different values of time correlation factor
τ, for a fixed value of Δ
t=0.6
s. When the value of
τ is 0.8 and 0.9, more than 60
% of all prediction have prediction inaccuracy of less than 20
%. The time correlation factor
τ shows how much the speed of the nodes varies for each Δ
t time duration. When
τ=1, the node will not change its speed for each Δ
t time duration, i.e., constant speed movement and when the value of
τ=0, the speed of nodes in an epoch does not depend upon its past speed, i.e., the speed is highly random. Thus, when
τ is reduced, the randomness in the speed between the epoch increases resulting in an increase of prediction inaccuracy.
×
×
The time correlation factor
τ can be used to model the operation of VANETs in three different traffic flow conditions: uncongested (i.e, free flow traffic state with low vehicle density), near capacity (i.e., vehicle density takes intermediate values) and congested state (i.e., high values for the vehicle density). Higher values of
τ results in negligible temporal variations in the vehicle speed, which represents an uncongested highway scenario where drivers can drive independent of other vehicles. However, in the uncongested highway scenario, there would be deterioration of link lifetime because of frequent disconnections and nonavailability of neighbor nodes for forwarding the packets. When time correlation factor is less, the vehicle speed would exhibit very high temporal variations and this is equivalent to a congested traffic state. We have selected
τ to be equal to 0.9 for some of our simulation experiments so that the performance of the protocol can be studied for a free flow traffic state. The beacon interval determines the frequency with which measurement values are taken for the prediction. It has been observed that, beacon interval Δ
t has strong influence on accuracy of residual link lifetime prediction as shown in Fig.
6. When Δ
t is reduced, more measurement values would be available, resulting in accurate prediction at the cost of an increase in complexity. For some of our simulation experiments, we have chosen Δ
t=0.6.
Figure
7 shows the prediction inaccuracy of the residual lifetime for different values of normalized time interval and for different values of time correlation parameter
τ. We define the normalised time as the ratio between the estimated residual time to total lifetime of the link. During the initial time periods when the link is formed, the predicted residual lifetime has less accuracy and at later stages as the measurement values increases the correction and prediction process of the Kalman filter reduces the prediction inaccuracy. At the same time with the decrease of time correlation parameter
τ from 0.9 to 0.7, the randomness of the speed between the epoch duration increases resulting in the reduction of prediction inaccuracy.
×
We consider the following performance metrics for the evaluation of the proposed protocol.
Packet delivery ratio (PDR): this quantity is the ratio of average number of successfully received data packets at the destination vehicle to the number of packets generated by the source.
Average endtoend (E2E) delay: this is the time interval between receiving and sending time for a packet for a source to destination pair averaged over all such pairs. Here, the data packets that are successfully delivered to destinations are only considered for the calculation.
We investigate the impact of packet size on the performance of the two forwarding strategies in VANETs. The packet delivery ratio is analysed for different values of packet size from 512 to 3072 bytes in Fig.
8 and average endtoend delay is plotted against different values of packet size in Fig.
9. As the packet size increases, there is reduction in packet delivery ratio for both the routing protocols. The larger packets may be fragmented and these fragmented data packet can be lost during a link failure, resulting in the failure of the entire packet. Even though the PDR of both the protocols is degraded when the packet size increases, the PDR reduction is less for the proposed residual lifetime based routing as compared to greedy forwarding, since in the proposed method, one hop neighbor is selected based on maximum residual lifetime which reduces the link breakage. Similar results can be observed in Fig.
9 as well. When the link failures occur, fragmented smaller size packets will be lost affecting the delivery of the original packet. Hence in conventional greedy forwarding, endtoend delay increases as the packet size exceeds the fragmentation threshold. In the case of proposed residual lifetime based routing, since the forwarding nodes are selected based on link residual lifetime, there is high probability that all the fragments of a larger packet will be successfully delivered. Accordingly, the delay performance of residual lifetimebased routing is not affected significantly by varying packet size. However, we find that the endtoend delay for the link residual lifetime based next hop selection and forwarding method is higher than that of the conventional greedy forwarding approach. In link residual lifetime based next hop selection method, the forwarding node is selected in such a way that the newly formed link has maximum residual lifetime. Accordingly in the proposed method, the next hop forwarding vehicle selected need not be the one closest to the destination. This procedure is continued till the data packet reaches the destination. The immediate consequence of this approach is that the data packet may be required to travel more number of hops to reach the destination as compared to the conventional greedy forwarding procedure in which nodes closer to the destination are always selected for forwarding the packets. Since the proposed scheme requires more number of hops, the data packets would suffer higher endtoend as compared to the greedy forwarding protocol.
×
×
Figures
10 and
11, respectively, show the packet delivery ratio and average endtoend delay for different values of Δ
t or beacon arrival time (since we assume that always one beacon is obtained in each Δ
t time duration). When the value of Δ
t increases, the number of measurement values will be reduced which result in reduction of accuracy of the predicted value. This will result in reduction of packet delivery ratio. The average endtoend delay for different values of beacon interval for both the protocol is shown in Fig.
11. Here the size of the data packet is 512 bytes and the time correlation factor is 0.9. As the beacon interval is increased, the endtoend delay increases owing to the increase in prediction inaccuracy as mentioned earlier. At the same time, the proposed method leads to higher delay as compared to greedy forwarding, owing to higher number of hops to the destination in the former case.
×
×
In Fig.
12, we plot the packet delivery ratio by varying the time correlation factor
τ. Here, we keep the size of data packet to be 512 bytes and the beacon interval to be 0.6 s. The time correlation factor
τ shows the randomness of the speed between each Δ
t time duration. With high value of correlation factor, the randomness of the speed will be less or the time variation of the speed will become more smooth. Alternately, when
τ is reduced, the randomness in the speed between the epochs increases resulting in an increase of prediction inaccuracy. When
τ is comparatively smaller, the prediction accuracy gets affected leading to deterioration of the PDR. In this case, the endtoend delay, also gets affected badly as shown in Fig.
13, since inaccurate prediction of residual lifetime results in link failures.
×
×
In Figs.
14 and
15, we evaluate the performance of the proposed scheme when the path loss exponent
α is varied. As
α increases, the effective transmission range decreases. This leads to deterioration of PDR and an increase of endtoend delay. As effective transmission range decreases, the number of hops increases resulting in higher endtoend delay. However, the proposed method shows significant improvement in terms of PDR and endtoend delay as compared to greedy forwarding.
×
×
In Fig.
16, we plot the packet delivery ratio by varying the average speed of vehicles. We fix the time correlation factor
τ=0.9 and the size of data packet to be 512 bytes. When the average speed of the vehicles increases, the network topology get changed frequently resulting in the reduction of packet delivery ratio. In residual lifetimebased forwarding, since the forwarding node is chosen based on link residual lifetime, the probability of link breakages reduces, leading to higher packet delivery ratio. Figure
17 shows the impact of average speed on endtoend delay for the greedy forwarding and residual lifetime based forwarding. For both the forwarding schemes, the endtoend delay increases with the increase of average speed, since the network becomes more dynamic in nature and chances of occurrence of link breakages increase. The greedy forwarding selects the node closest to the destination than node having maximum residual lifetime, which results in lower endtoend delay for greedy forwarding than the residual lifetime based forwarding.
×
×
In Figs.
18 and
19, we compare the performance of the proposed residual lifetimebased scheme against that of LSGO [
19], AODVR [
11], GPSRR [
17], and MOPRGPSR [
8]. Figure
18 shows the comparison results for the packet delivery ratio of the network for all the above mentioned scheme. We select two distinct values for the average speed of vehicles
μ=20 and 30
m/
s. We set the packet size to be 512 bytes, pathloss exponent
α=3 and vehicle density 0.038 veh/m. The simulation results show that our proposed scheme has the highest packet delivery ratio. The topology based routing protocol, AODVR gives the lowest packet delivery ratio compared to all other scheme under consideration, since AODVR requires the exchange of several route requests and route reply messages which are not suitable for high mobility applications like VANETs. LSGO scheme requires involvement of exchange of Hello packets and ACK packets for the computation of the ETX metric. This also increases the overhead. In residual lifetime based forwarding, a one step ahead prediction of position and speed of the vehicles are performed based on which the residual lifetime is calculated for selecting appropriate forwarding node, which results in higher packet delivery ratio. In the case of MOPRGPSR, the packet delivery ratio is higher than the AODVR, since the link lifetime is estimated before selecting the next hop for data forwarding. But the assumption taken here is the speed of the vehicles is a deterministic quantity which is not a real scenario for VANETs. Figure
19 shows the comparison results for the endtoend delay for all the above mentioned scheme for two distinct average speed values. We set the packet size to be 512 bytes, pathloss exponent
α=3 and vehicle density to 0.038 veh/m. AODVR protocol incurs the highest delay compared to other protocols under consideration owing to the exchange of RREQ and RREP route request packets. In LSGO, for computing the ETX metric, control packets need to be exchanged between the nodes leading to significant increase of endtoend delay. The packet delivery ratio is analysed for different values of vehicle density in Fig.
20, for residual lifetime based forwarding and GPSRR. Here we keep the mean speed as 20
m/
s, packet size as 512 bytes and pathloss exponent
α=3. In GPSRR, the forwarding node is selected from among a set of nodes whose reliability factor is greater than a given threshold. Though the protocol works well in a higher density scenario, the performance will be degraded when the vehicle density reduces since the probability of finding a forward vehicle with reliability factor greater than the given threshold reduces. It is observed that the performance of the proposed residual lifetimebased forwarding scheme is not affected significantly by the vehicle density. This is because, in the proposed scheme a forwarding node will surely be chosen from among the available links based on the residual lifetime criterion.
×
×
×
Even though the paper provides results for a unidirectional scenario alone, the results presented in this paper are valid for multilane unidirectional highways as well. This is because, the transmission range of a vehicle is usually much greater than the highway width and a vehicle can always communicate with any other vehicle located within its range [
34]. Consider a scenario where two vehicles denoted
A and
B of equal transmission range
R move along two distinct lanes in a multilane highway of width
L. If vehicle
A intends to transmit a message to vehicle
B along the direction of the highway, it must use a larger transmission range
R
^{′}. In other words, if destination vehicle is on a different lane (i.e., interlane transmissions), the transmission range of vehicle
A must be
R
^{′}, which is slightly larger than
R. However, the standard highway’s lane width is approximately 3.6
m, and the vehicle transmission range can be increased to 500
m or so as suggested by the dedicated shortrange communication (DSRC) Standard [
32]. Therefore, the difference between
R and
R
^{′} is negligible. So, the scenario consisting of two vehicles travelling in the same direction on multiple lanes along a multilane highway can be considered as equivalent to both of them moving on the same lane. These vehicles can communicate with each other if they are in the transmission range of each other. This means that highway width does not introduce major changes in the calculations. However, vehicles moving on different lanes will have different mean speeds (i.e., dynamic range of their speeds could be different). This should be considered in the problem formulation. Further, the results can be immediately extended for the bidirectional scenario as well. When the vehicles are assumed to move in the same direction, the relative speed among a pair of vehicles is calculated as the difference of their individual speed and is given by Eq. (
6). In the bidirectional scenario, the relative speed among a pair of vehicles would be the sum of their speed. Appropriate changes have to be made in the measurement equations accordingly.
5 Conclusions
In this paper, we have proposed a new scheme for the selection of next hop link based on knowledge of link residual lifetime. We assumed vehicle speed to follow the Gauss Markov mobility model and the notion of effective transmission range was considered for the analysis and evaluation. We have also described a method for the prediction of residual lifetime using Kalman filter. The proposed next hop selection method ensures that links with maximum residual lifetime is chosen for forwarding the data packet. Through extensive simulation results, we have showed that the proposed selection scheme is superior to conventional method of greedy forwarding. Even though the endtoend delay was observed to be slightly higher for the proposed scheme, significant empowerment in communication reliability (i.e; expressed as PDR) was obtained, as compared to greedy forwarding.
Competing interests
The authors declare that they have no competing interests.
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (
http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.