Modeling Enhancements in Routing Protocols under Mobility and Scalability Constraints in VANETs

Abstract

This paper presents mathematical framework for calculating transmission probability in IEEE 802.11p based networks at Medium access control (MAC) layer, mathematical framework for calculating energy costs of the chosen routing protocols at network layer, and enhancements in optimized link state routing (OLSR), dynamic source routing, (DSR) and fish-eye state routing (FSR) to tackle delay in vehicular ad hoc networks (VANETs). Besides the enhancements, we analyze ad hoc ondemand distance vector (AODV) along with OLSR, DSR, and FSR as well. To evaluate the effect of our proposed transmission probabilities in the selected routing protocols, we choose network throughput, end-to-end delay (E2ED), and normalized routing load (NRL) as performance metrics. We also investigate the effect of different mobilities as well as scalabilities on the overall efficiency of the enhanced and default versions of the selected protocols. Simulations results which are conducted in NS-2 show that overall DSR-mod outperforms rest of the protocols.

1. Introduction

In order to meet the challenges posed by the new lifestyle, traditional wired networks have been proven as inadequate. Users, physically connected via cables to the network, have restricted mobilities. On the other hand, wireless networks do not face such restrictions. Thus, the latter class of networks offers convenience to the users in different nodes' mobilities and densities as compared to the former class. Mobile ad hoc networks (MANETs) are infrastructureless as well as self-organizing networks of wirelessly connected mobile devices. Vehicular ad hoc networks (VANETs), a sub class of MANETs, can be considered as an intelligent transportation system. The major purpose of VANETs is to provide safety and ease to the travelers. In addition, VANETs are distributed and are self-organizing communication networks made up of multiple autonomous moving vehicles which are associated with high mobilities [1, 2]. Every vehicle is equipped with a VANET device (a node in VANET) [3]. In order to exchange information, these nodes can search out and pass on messages via wireless network [4, 5].

Routing, which begins at neighbour discovery, ends with the discovery of destination. In this process, intermediate nodes may or may not be involved. The number of intermediate nodes depends on the routing protocol, which establishes efficient and connected end-to-end communication routes between source and destination [6]. On the basis of response type, the routing protocols are classified into two categories, reactive and proactive. Protocols that belong to the former category are triggered by the arrival of data demand for calculating routes to the destination in the network. On the other hand, protocols that belong to the latter category, periodically calculate routes (independent of the data demands). In subject of achieving high delivery rates, the routing overhead (i.e., routing load and path latencies) is a major issue. Routing protocols, in this context, are designed in such a way that an optimized solution to this issue is provided.

In this research work, we choose four routing protocols, ad hoc ondemand distance vector (AODV) [7], dynamic source route (DSR) [8], fish-eye state routing (FSR) [9], and optimized link state routing (OLSR) [10]. Among the four selected routing protocols, the former two are reactive whereas the latter two are proactive. We then extend the work [11] and construct of two mathematical frameworks, one at MAC layer to calculate the probabilities of transmission in $\mathrm{802.11}p$ based networks and the other at network layer to calculate the per packet energy cost paid by routing protocols. After briefly analyzing the selected protocols, we enhance their efficiency in terms of throughput, E2ED, and NRL. The enhancements are validated via NS-2 simulations.

2. Background

In this section, we discuss the four selected routing protocols: AODV, DSR, FSR, and OLSR. These are the most widely used protocols. Reactive protocols are well suited for highly mobile scenarios and proactive protocols are designed for static and dense networks. So, we have taken two protocols from reactive class and two from the proactive one.

2.1. AODV

It provides multiple timely routes in the routing table. Instead of repairing the complete end-to-end route, AODV implements local link repair (LLR) mechanism which quickly repairs the broken link. LLR makes AODV robust during highly mobile scenarios.

2.2. DSR

It provides multiple routes in the route cache (like AODV's routing table) along with the promiscuous listening mode. During the highest speeds and highest mobilities, DSR has the low convergence rate because of multiple routes in the route cache.

2.3. FSR

Being proactive (suitable for static topologies) in nature, FSR is suitable for mobile scenarios as compared to static scenarios. It controls the routing overhead with its graded-frequency mechanism.

2.4. OLSR

OLSR is more suitable for static or less dynamic networks. Its distinguished feature, multipoint relay redundancy, provides convergence in high mobility. It is also equipped with periodic updates mechanism to keep the routing tables up to date.

In Table 1, we have summarized the distinguished properties of the four selected protocols.

Table 1

Routing protocols in brief.

Protocol	Key	Route	Next hop	Overhead	Overhead
	parameter	selection	selection	control	reduction
AODV	Repairing links with LLR	Flooding-based route discovery	Hop-by-hop routing	Ring search algorithm	Exp. back-off algorithm and grat. RREPs
DSR	Packet salvaging of route cache	Flooding-based route discovery	Source routing	Ring search algorithm	Exp. back-off algoritm and packet salvaging
FSR	Multiscope routing	DBF algorithm	Hop-by-hop routing	Graded-frequency strategy	Fish-eye technique
OLSR	Multipoint relay selection	Dijkstra's algorithm	Hop-by-hop routing	Broadcast only through selected MPRs	MPRs

3. Related Work and Motivation

In [12], the authors compare and evaluate performance of AODV, DSR, and swarm intelligence based protocols. They perform a variety of simulations for VANETs, characterized by networks' mobility, load, and size. From simulations, the authors conclude that swarm intelligence based protocols show more promising results than AODV and DSR in terms of latency, throughput, data delivery cost, and data delivery ratio.

The work in [13] investigates quality routing link metrics in ad hoc networks. Besides the investigation, the authors propose a new quality routing link metric; Inverse ETX (InvETX), for OLSR protocol. The authors validate their proposed framework in terms of throughput, normalized routing load, and end to end delay. From simulation results, the authors conclude that for achieving high efficiency the frequencies of topological information should be properly adjusted. Similarly, authors in [14] evaluate AODV and OLSR in realistic urban scenarios and study the chosen protocols under different metrics such as vehicles' mobility, density, and data traffic rates. The authors focus on a qualitative assessment of the protocols' applicability in time varying vehicular scenarios.

Authors in [15] analyze dynamic MANET ondemand (DYMO) routing protocol and present a simulation system called cellular automation based vehicular networks (CAVENETs). They use I-dimensional cellular automata for nodes' mobility generation. In order to evaluate the performance of typical ad hoc routing protocols, they combine microsimulation of road traffic and event-driven network simulation. They also analyze protocols of the Internet protocol suite in VANET scenarios with highly accurate mobility models. In their work, they use different parameters of DYMO for a multitude of traffic and communication scenarios to improve the overall performance.

Authors in [16] perform a comprehensive evaluation of mobility impact on IEEE $\mathrm{802.11}p$ MAC performance. This study evaluates packet delivery ratio, throughput, and delay as performance metrics. Their extensive simulation results demonstrate a significant impact of the relative speed on channel access at the MAC layer in IEEE $\mathrm{802.11}p$ based networks. As a solution, the authors provide two dynamic contention window mechanisms to dynamically reassign and reshape the contention window of different access categories. The first mechanism considers the number of nodes for providing priorities, whereas the second one considers nodes' relative speeds for providing channel access priorities.

AODV and OLSR are evaluated in urban scenarios in [17]. By enhancing the HELLO and TC intervals of OLSR, it is observed that enhanced OLSR performs better than AODV in urban environments. Authors select packet delivery ratio (PDR), end-to-end delay (E2ED), and routing packets per data packet (or NRL) as performance metrics for evaluating the performance of the proposed protocol in different scalabilities of the vehicles using probabilistic Nakagami radio propagation model in NS-2. In this paper, we extend the work of [11] and construct a mathematical model to calculate the probabilities of transmission in $\mathrm{802.11}p$ at MAC layer and then evaluate the energy cost paid per packet by routing protocols at network layer. Moreover, we enhance OLSR (in the same way as that in [17]), DSR, and FSR as well. Throughput, E2ED, and NRL are selected as performance metrics for evaluating the performance of the selected routing protocols in VANETs using probabilistic Nakagami radio propagation model NS-2. Nakagami model deals with the radio channels suffering from the fading effects. Regarding its performance and its selection for this work, when it is compared with the shadowing and two-ray ground models, Nakagami model has more configurable parameters, which allow a closer representation of the wireless communication channels. It is capable to handle the channels ranging from the perfect free space channels to the moderate fading channels on highway, even to a dramatically fading channel in urban communities [18].

4. Proposed Work

This section pivots around the following key contributions: (i) mathematical framework for MAC layer transmission probability in $\mathrm{802.11}p$ based networks, (ii) mathematical framework for calculating the energy cost of routing protocols at network layer, and (iii) enhancements in OLSR, DSR, and FSR to tackle delay in VANETs. The following subsections include brief description about the aforementioned contributions.

4.1. Mathematical Framework for MAC Layer Transmission Probability in $802.11p$ Based Networks

$\mathrm{802.11}$ is a child of the IEEE $\mathrm{802}$ family (includes specification about local area network (LAN) technologies). The IEEE $\mathrm{802}$ specifications focus on two OSI layers, data link layer and physical layer. Medium access control (MAC) layer sets rules which specify how to access the medium to send the information of interest. On the other hand, the physical layer incorporates details about transmission and reception of the data. $\mathrm{802.11}$ (base specification) includes specifications about physical layer's frequency hopping spread spectrum (FHSS) and link layer's direct sequence spread spectrum (DSSS). Later versions of IEEE $\mathrm{802.11}$ include $\mathrm{802.11}a$ , $\mathrm{802.11}b$ , $\mathrm{802.11}g$ , and $\mathrm{802.11}p$ . The $\mathrm{802.11}a$ describes physical layer on the basis of orthogonal frequency division multiplexing (OFDM). Similarly, $\mathrm{802.11}b$ deals with high rate DSSS (HR/DSSS) layer, $\mathrm{802.11}g$ exploits OFDM for high speed along backward compatibility with $\mathrm{802.11}b$ , and $\mathrm{802.11}p$ uses p-persistent carrier sense multiple access with collision avoidance (CSMA/CA) to achieve adaptivity between the neighbouring nodes.

The back-off procedure in [19] offers adaptivity between neighbouring nodes because it uses $\mathrm{802.11}p$ . The main content of cognition between p-persistent $\mathrm{802.11}$ and standard IEEE $\mathrm{802.11}p$ protocol is the back-off interval. The back-off interval is binary exponential for the standard protocol, whereas it is geometrically distributed if p-persistent CSMA/CA is considered. If p is the probability of successful transmission for p-persistent CSMA/CA with geometric distribution, then the node stays idle with probability $\mathrm{1}-p$ (i.e., the medium is busy). On the basis of geometrically distributed back-off time, after $n-\mathrm{1}$ failures, the probability of successful transmission is

$$\begin{array}{cc}& P\left(X=n\right)=p{\left(\mathrm{1}-p\right)}^{Z-\mathrm{1}},\hspace{1em}Z=\mathrm{1,2},\mathrm{3},\dots ,\end{array}$$

(1)

where X is the total number of trials for a successful transmission in a contention window ( $\text{CW}$ ). The expected value of X which is used to determine the average $\text{CW}$ size; $\overline{\text{CW}}$ , is calculated in [20] as follows:

$$\begin{array}{cc}& E\left[X\right]={\displaystyle \sum }_{Z=\mathrm{1}}^{\infty }‍Z_p{\left(\mathrm{1}-p\right)}^{n-\mathrm{1}}=\frac{\mathrm{1}}{p},\\ \frac{\overline{\text{CW}}+\mathrm{1}}{\mathrm{2}}=\frac{\mathrm{1}}{p}.\end{array}$$

(2)

If we define $P_s$ as the probability of a successful transmission and $P_c$ as the probability of a collision; $P_s=P\{$ one node tranmists/at least one node has a packet to transmit} and $P_c=P\{$ two nodes tranmist/at least one node has a packet to transmit}. Based on these assumptions, there are several probabilities which are given as follows:

$$\begin{array}{cc}& P\left\{\text{Zero transmissions}\right\}={\left(\mathrm{1}-p\right)}^Q,\\ P\left\{\text{Exatly one transmission}\right\}={\left(\mathrm{1}-p\right)}^{Q\hspace{0.17em}-\mathrm{1}}Qp,\\ P\left\{\text{At least one transmission}\right\}=\mathrm{1}-{\left(\mathrm{1}-p\right)}^Q,\\ P_s=\frac{Qp{\left(\mathrm{1}-p\right)}^Q}{\mathrm{1}-{\left(\mathrm{1}-p\right)}^Q},\\ P_c=\frac{\mathrm{1}-{\left(\mathrm{1}-p\right)}^Q-Qp{\left(\mathrm{1}-p\right)}^{Q\hspace{0.17em}-\mathrm{1}}}{\mathrm{1}-{\left(\mathrm{1}-p\right)}^Q},\end{array}$$

(3)

where Q denotes the number of contending nodes. If ${\tau }_{\text{idle}}$ is the idle time during which none of the nodes transmit, then we can write

$$\begin{array}{cc}& E\left[{\tau }_{\text{idle}}\right]=\frac{\mathrm{1}-{\left(\mathrm{1}-p\right)}^Q-Qp{\left(\mathrm{1}-p\right)}^Q}{Qp{\left(\mathrm{1}-p\right)}^{Q\hspace{0.17em}-\mathrm{1}}}\times \frac{\mathrm{1}-p}{Qp}{\tau }_{\text{slot}},\end{array}$$

(4)

where ${\tau }_{\text{slot}}$ denotes the slot time. Similarly, if ${\tau }_{\text{succ}}$ denotes the time of a successful transmission, then

$$\begin{array}{cc}& E\left[{\tau }_{\text{succ}}\right]=\left({\tau }_{\text{pack}}+{\tau }_{\text{DIFS}}\right){\tau }_{\text{slot}},\end{array}$$

(5)

where ${\tau }_{\text{pack}}$ and ${\tau }_{\text{DIFS}}$ are the packet transmission time and DIFS time, respectively. Now, for ${\tau }_{\text{coll}}$ , the total time of transmission collisions, we can write

$$\begin{array}{cc}& E\left[{\tau }_{\text{coll}}\right]=\frac{\mathrm{1}-{\left(\mathrm{1}-p\right)}^Q-Q_p{\left(\mathrm{1}-p\right)}^Q}{Qp{\left(\mathrm{1}-p\right)}^{Q\hspace{0.17em}-\mathrm{1}}}\left({\tau }_{\text{pack}}+{\tau }_{\text{DIFS}}\right){\tau }_{\text{slot}}.\end{array}$$

(6)

Based on the above definitions, we are now able to define virtual transmission time, ${\tau }_{v\text{-trans}}$ , as the duration between two adjacent successful transmissions according to [20] as follows:

$$\begin{array}{cc}& E\left[{\tau }_{v\text{-trans}}\right]=E\left[{\tau }_{\text{idle}}\right]+E\left[{\tau }_{\text{coll}}\right]+E\left[{\tau }_{\text{succ}}\right].\end{array}$$

(7)

On the bases of constant packet time ${\tau }_{\text{pack}}$ and transmission probabilities, we can write mathematical expression from [19] as

$$\begin{array}{l}E\left[{\tau }_{v\text{-trans}}\right]\\ \hspace{1em}=\frac{\left({\tau }_{\text{pack}}+{\tau }_{\text{DIFS}}\right)-\left({\tau }_{\text{pack}}+{\tau }_{\text{DIFS}}-\mathrm{1}\right)\left(\mathrm{1}-p\right)}{Qp{\left(\mathrm{1}-p\right)}^{Q-\mathrm{1}}}{\tau }_{\text{slot}}.\end{array}$$

(8)

Here it is important to note that the value of ${\tau }_{v\text{-trans}}$ should be minimized for maximum system efficiency in terms of throughput.

4.2. Mathematical Framework for Network Layer Energy Cost Calculation of Routing Protocols

The reactive routing protocols perform two mandatory operations: route discovery ( $\text{RD}$ ) and route maintenance ( $\text{RM}$ ). $\text{RD}$ for the requested destination is triggered by data request from a known destination. In 802.11 based wireless networks, frequent link disconnections due to limited bandwidth as well as limited range of transmission cause route breakages. Thereby, the link layer notifies about the breakage if and only if any of the intermediate nodes does not successfully transmit after the counter for retransmissions expires. Once path is established during $\text{RD}$ , monitoring and repairing are carried out during $\text{RM}$ .

The modelled energy costs of the selected protocols are as follows.

(1) AODV. During $\text{RM}$ , the costs paid for link monitoring as well as other supplementary strategies are protocol dependent. If we consider the case of link breakage then the cost paid is $C_{E\text{-LLR}}$ for AODV.

The $\text{RM}$ cost for AODV is calculated as follows:

$$\begin{array}{cc}& C_{E\text{-RM}}^{\left(\text{AODV}\right)}=C_{E\text{-}l\text{-mon}}+C_{E\text{-LLR}}+{\displaystyle \sum }_{z=\mathrm{0}}^n‍{\left(\text{RERR}\right)}_z.\end{array}$$

(9)

AODV pays link monitoring cost $C_{E\text{-}l\text{-mon}}$ , in the form of HELLO messages as per (9). The $C_{E\text{-}l\text{-mon}}$ computation for AODV as follows:

$$\begin{array}{cc}& C_{E\text{-}l\text{-mon}}=\frac{{\tau }_{\text{link-in-use}}}{{\tau }_{\text{HELLO}\_\text{INTERVAL}}}\times N_{\text{hops-in-route}}.\end{array}$$

(10)

Equation (10) shows that $C_{E\text{-}l\text{-mon}}$ depends upon the link time for active link ${\tau }_{\text{link-in-use}}$ , path length in hops $N_{\text{hops-in-route}}$ , and the time for HELLO interval ${\tau }_{\text{HELLO}\_\text{INTERVAL}}$ . As mentioned earlier a specific route becomes ineffective whenever link breakage occurs due to either limited bandwidth or limited transmission range or both. Different protocols use different strategies for the detection of link breakages. AODV uses HELLO message generation strategy for checking active routes' connectivity. z number of RERRs are needed for broadcast; however, the value of z is protocol as well as application specific. Figure 1 shows the complete flow chart of AODV protocol.

Figure 1

AODV flow chart.

(2) DSR. In DSR (refer to its flow chart in Figure 2), searching routes in route cache (RC) of the nodes is known as RCing. The originator node checks its RC for the requested target before route REQuest (RREQ) is broadcasted. If the search is negative, then the originator node broadcasts an RREQ. Once RREQ is received, intermediate nodes generate grat. RREPs in response to RREQ of the originator node if the intermediate nodes contain route(s) in their RC. RCing is possible because the learned routes due to promiscuous listening mode are stored. Expanding ring search (ERS) method is used for $\text{RD}$ process. Soon after the establishment of successful routes, $\text{RM}$ is initiated (considering reactive protocols). The $\text{RM}$ process is completed in two subphases: link status monitoring ( $\text{LSM}$ ) and route repairing (RR). The former subphase checks the connectivity of those routes which are successfully established during $\text{RD}$ . During $\text{LSM}$ , if link breakages are reported then repairing process is initiated for route during $\text{RR}$ phase which disseminates route error (RERR) message about broken link and route rediscovery for broken route. From [21] the energy cost of RD “ $C_{E\text{-RD}}^{(\text{DSR})}$ ” is computed as follows:

$$\begin{array}{l}{C}_{E\text{-RD}}^{\left(\text{DSR}\right)}\\ =\{\begin{array}{ll}{\displaystyle \sum }_{R_i=\mathrm{1}}^{R_{\max \_\text{limit}}}‍{\left(C_{E\text{-}{R}_i}\right)}_{R_i},\hfill & \text{if no RREP received,}\hfill \\ C_{E\text{-}{R}_{\text{rrep}}},\hfill & \mathrm{\hspace{0.17em}\hspace{0.17em}}\text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{TTL}\left(R_{\text{rrep}}\right)=\mathrm{1},\hfill \\ {\displaystyle \sum }_{R_i=\mathrm{1}}^{R_{\text{rrep}}}‍{\left(C_{E\text{-}{R}_i}\right)}_{R_i},\hfill & \text{otherwise,}\hfill \\ \left\{R_{\text{rrep}}=\mathrm{1,2},\mathrm{3},\dots ,\text{max\_limit}\right\}.\hfill & \hfill \end{array}\end{array}$$

(11)

Figure 2

DSR flow chart.

DSR broadcasts RREQ through different rings: $R_{\mathrm{1}},R_{\mathrm{2}},R_{\mathrm{3}},\dots ,R_{\text{rrep}}$ , using ERS mechanism. Figure 3 shows that this broadcast is stopped when $R_{\text{rrep}}$ generates RREPs.

Figure 3

Route calculation in AODV, DSR, FSR, and OLSR.

In DSR, if a node finds alternative route in its RC due to detection of link breakage then it sends data through this route; otherwise, RC search for alternative route is repeated till it finds active route. This repairing process is called packet salvaging (PSing). If PSing is unsuccessful then source node initiates new RREQ route rediscovery process (RERR message is piggy backed with new RREQ) which is based on $\text{MaxMaintRexmt}$ constraint [8].

(3) FSR. Detailed flow chart of FSR is shown in Figure 4. In order to maintain routing table information and network topology, proactive routing protocols use periodic link status monitoring $(\text{LSM\_Per})$ , triggered route updates $(\text{RU}\_\text{Tri})$ , and periodic routes updates $(\text{RU}\_\mathrm{Per})$ . $\text{LSM\_Per}$ updates link status ( $\text{LS}$ ) information in the network and checks for node connectivity. $\text{RU}\_\mathrm{Per}$ keeps recent routing information across the network. $\text{RU}\_\text{Tri}$ generation triggers LS to change. FSR only generates $\text{LSM}\_\mathrm{Per}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{RU}\_\mathrm{Per}$ because it only implements scope routing (SR).

Figure 4

FSR flow chart.

In order to exchange routing information using SR technique, different scopes are used to disseminate $\text{R}{\text{U}}_{\mathrm{Per}}$ on the basis search diameter which is in direct relation with the number of hops. Association of graded-frequency with each scope reduces overhead due to routing packets. FSR uses InterScope and IntraScope [9]. Figure 3 shows the energy cost for IntraScope, $C_E^{(\text{in})}$ , with $\mathrm{2}$ hops search diameter, and energy cost for $\mathrm{255}$ hops InterScope, $C_E^{\text{out-sco}}$ , respectively. The energy cost of a single packet for FSR $(C_E^{(\text{FSR})})$ is calculated from [22] as

$$\begin{array}{l}{C}_E^{\left(\text{FSR}\right)}={{\displaystyle \int }}_{\mathrm{0}}^{\tau }‍d_{\text{avg}}^{\text{out}}{\displaystyle \sum }_{i=\mathrm{1}}^{N_{\text{out}}-\mathrm{1}}‍{\left(p_{\mathrm{err}}\right)}^{i+\mathrm{1}}{\displaystyle \prod }_{j=\mathrm{1}}^i‍d_f\left[j\right]\\ \hspace{1em}\hspace{1em}\hspace{1em}+d_{\text{avg}}^{\text{in}}{\displaystyle \sum }_{i=\mathrm{1}}^{N_{\text{in}}-\mathrm{1}}‍{\left(p_{\mathrm{err}}\right)}^{i+\mathrm{1}}{\displaystyle \prod }_{j=\mathrm{1}}^i‍d_f\left[j\right].\end{array}$$

(12)

(4) OLSR. OLSR (refer to its flow chart in Figure 5) maintains fresh routes via $\text{RU}\_\text{Tri}$ throughout the network, and at routing layer $\text{LSM}\_\mathrm{Per}$ are sent through HELLO messages. If ${\tau }_{\text{LU}}$ denotes the last update message which is generated during network lifetime then the total energy cost of OLSR, $C_E^{(\text{OLSR})}$ , is formulated as follows:

$$\begin{array}{cc}& C_E^{\left(\text{OLSR}\right)}={{\displaystyle \int }}_{\mathrm{0}}^{{\tau }_{\text{LU}}}‍C_{E\text{-nc}}^{\text{MPR}}+C_{E\text{-}c}^{\text{MPR}}.\end{array}$$

(13)

Figure 5

OLSR flow chart.

Here it is worthy to note that status of MPR causes variation in the transmission interval of routing updates. If the status of MPRs' does not change then default TC interval is used to transmit TC messages (refer to Table 2). The cost of (re)transmissions which are allowed through MPRs is denoted by $C_{E\text{-nc}}^{\text{MPR}}$ , and the cost of update messages dissemination throughout the network is denoted by $C_{E\text{-}c}^{\text{MPR}}$ [22]. Consider

$$\begin{array}{l}{C}_{E\text{-nc}}^{\text{MPR}}=\left(\mathrm{1}-p_c^{\text{MPR}}\right)p_{\mathrm{err}}{d}_{\text{avg}}\\ \hspace{1em}\hspace{1em}\hspace{1em}+d_{\text{avg}}{\displaystyle \sum }_{i=\mathrm{1}}^{h-\mathrm{1}}‍{\left(p_{\mathrm{err}}\right)}^{i+\mathrm{1}}{\displaystyle \prod }_{j=\mathrm{1}}^i‍d_f^{\text{MPR}}\left[j\right],\\ C_{E\text{-}c}^{\text{MPR}}=p_c^{\text{MPR}}{p}_{\mathrm{err}}{d}_{\text{avg}}\\ \hspace{1em}\hspace{1em}\hspace{1em}+d_{\text{avg}}{\displaystyle \sum }_{i=\mathrm{1}}^{h-\mathrm{1}}‍{\left(p_{\mathrm{err}}\right)}^{i+\mathrm{1}}{\displaystyle \prod }_{j=\mathrm{1}}^i‍d_f\left[j\right].\end{array}$$

(14)

Table 2

Default and modified parameters of selected protocols.

Protocol	Parameter	Default value	Modified value
DSR	NonPropagatingRREQ	1	3
	TAP_CACHE_SIZE	1024	256
FSR	IntraScope_Interval	5 s	1 s
	IntreScope_Interval	15 s	3 s
OLSR	HELLO_INTERVAL	2 s	1 s
	TC_INTERVAL	5 s	3 s

Figure 3 shows that the HELLO messages of OLSR are exchanged with neighboring nodes, and TC messages are transmitted throughout the network only via MPRs.

4.3. Enhancing OLSR, DSR, and FSR to Tackle Delay in VANETs

As delay in VANETs, is a critical issue; so, we enhance the selected protocols as follows.

As there is no explicit mechanism for the deletion of stale routes, large value of $\text{TAPE}\_\text{CACHE}\_\text{SIZE}$ means that the $\text{RC}$ stores faulty routes. Decreasing the value of $\text{TAPE}\_\text{CACHE}\_\text{SIZE}$ solves the problem of storing faulty routes. In DSR, we modify $\text{TAPE}\_\text{CACHE}\_\text{SIZE}$ from $\mathrm{1024}$ to $\mathrm{256}$ and $NonPropagating$ RREQ from $\mathrm{1}$ to $\mathrm{3}$ . Therefore, reduction of $\text{TAPE}\_\text{CACHE}\_\text{SIZE}$ values (refer to Table 2) results in fruitful PSing and RCing, and decreases the routing delay as well. The DSR, during $\text{RD}$ , uses ERS mechanism. Moreover, DSR initiates RREQ from NonPropagating RREQ. In ERS, time consumption values and gradual increase of search diameter depend on waiting time and previous TTL value. Thus, increment in NonPropagating RREQ achieves quick search and thus minimizes the searching delay. DSR also implements RCing and PSing mechanisms (due to promiscuous listening mode) for RM and RD, respectively. These enhancements result in fruitful outcome for highly mobile and dense scenarios.

Low convergence is seen due to delayed updates of routing entries in highly mobile networks. As VANET delivers accurate data with better efficiency for low latencies, it is obligatory to aim for reduced delay. To achieve this, the periodic updates for FSR and OLSR are shortened. In FSR, $\text{InterScope}\_\text{Interval}$ and $\text{IntraScope}\_\text{Interval}$ are shortened. Whereas, the intervals: $\text{LS}{\text{M}}_{\mathrm{Per}}$ , $\text{R}{\text{U}}_{\text{Tri}}$ , HELLO INTERVAL, and TC INTERVAL, are reduced in the enhanced OLSR.

5. Performance Evaluation

Performance of the selected protocols, default and enhanced versions, is evaluated and compared in terms of throughput, E2ED, and NRL using NS-2. The simulation parameters are given in Table 3.

Table 3

Common simulation parameters.

Parameter	Value
MAC protocol	802.11p
Area	$\mathrm{1000}\times \mathrm{1000}$   ${\text{m}}^{\mathrm{2}}$
Simulation time	900 Seconds
Data traffic source	CBR of 512 bytes
Mobility model	Nakagami model
Mobility	0, 100, 200, and 400 pause time (s)
Scalability	25, 50, 75, and 100 nodes

5.1. Throughput

Throughput is amount of data successfully transferred from source to destination. AODV checks the route table (RT) with valid time and avoids the usage of invalid routes in routing table. The HELLO messages and LLR enable the protocol to handle highest mobility rates. DSR-orig with the highest speeds/mobilities achieves less throughput values for the following reasons: RC is checked each time for a route request, and RC is not associated with any explicit mechanism to delete stale routes except response to RERR messages. Whereas in AODV, only fresh routes are considered. So, AODV converges better in this situation than DSR-orig. Moreover, mobility breaks those links which generate a storm of RERR messages consuming more bandwidth due to source route dissemination which thus causes more drop rates. As moving vehicles alter the existing established routes, therefore, they demand robust repair mechanism. Due to reactive nature, DSR-orig among the selected routing protocols yields maximum throughput (Figures 6 and 7). For convergence purpose, OLSR-orig uses $\text{RU}\_\text{Tri}$ . On the other hand, FSR-orig only uses $\text{RU}\_\mathrm{Per}$ . Due to these reasons OLSR-orig yields more throughput as compared to FSR-orig. FSR's strange behavior, though it is proactive its throughput is decreasing with decreasing mobility because in low mobilities multiple routes are available in RC. There is lack of any mechanism to delete expired stale routes in FSR-orig, like DSR-orig, or to determine the freshness of routes when multiple routes are available in route cache, like AODV. Throughput of DSR-orig decreases as the number of connections increases and in high mobilities as compared to DSR-mod, as shown in Figures 6(a) and 6(b) and Figures 7(a) and 7(b). DSR-orig does not scale well in high scalabilities because of generation of grat. RREPs which are produced during RD and RM creating broadcast storm. In DSR-mod, we reduce size of RC by modifying $\text{TAP}\_\text{CACHE}\_\text{SIZE}$ (Table 2). This change makes fresh routes available for RCing; thus, remarkable change in throughput value is obtained (Figures 6(c) and 7(c)), where $\mathrm{16}\%$ and $\mathrm{28}\%$ efficiency is achieved by DSR-mod with respect to DSR-orig. In VANETs, FSR-orig behaves worst among all the simulated protocols due to lack of any instant action for link changes (as it uses only periodic operations). After shortening the scope interval in FSR-mod, routing updates are frequently disseminated. Thus, throughput increases $\mathrm{6.5}\%$ and $\mathrm{10.5}\%$ in scalabilities and mobilities scenarios, respectively (refer to Figures 6(c) and 7(c)). Generally, MPRs approach (in OLSR-orig) provides more optimization in high densities; however, conflicting behavior is noticed. Unstable network with high population and dynamicity results in MPRs' redundancy which expands routing updates dissemination throughout the network. Therefore, in VANETs with more number of connections MPRs fail to provide network optimization. In OLSR-mod, reduction in $\text{LSM}$ and $\text{RU}\_\text{Tri}$ intervals make the MPRs' be updated quickly. Thus, its efficiency increases as compared to OLSR-orig (considering high densities and mobilities: Figures 6(c) and 7(c)).

Figure 6

Network throughput: original and enhanced protocols.

Figure 7

Network throughput: original and enhanced protocols.

Reactive protocols attain more throughput than proactive ones in high mobility rates. Reason is obvious, as proactive protocols perform route calculation before data transmission unlike the reactive ones. So, in this case if a data packet is on a calculated route and due to mobility, a link breaks, the respective proactive protocol has to perform route calculation from scratch. RT calculation phase takes place first and then response to data request phase is given, which degrades the performance.

5.2. E2ED

E2ED is the time a packet takes to reach destination from source. We have measured it as the mean of round trip time (RTT) taken by all packets. Figures 8(a), 8(b), and 8(c) show that, among the selected routing protocols, FSR-orig's routing latency is the least, because FSR-orig's routing updates are periodic and independent from topological changes as well as degree of nodes. AODV suffers from maximum E2ED. LLR mechanism is initiated after link breakage detection. The RM phase illustrates that starting of LLR sometimes results in increased path lengths. DSR-orig, due to reactive nature along with PS and RCing, produces highest E2ED while considering scalabilities as well as mobilities. Considering all scalabilities, OLSR-mod has highest delay as compared to the other selected routing protocols. The reason is straight forward; that is, increased number of intermediate hops during high mobilities increases 17 E2ED. In high mobilities, DSR-mod has high E2ED, checking of RC during ERS augments delay, and nonavailability of stale routes. Time-to-live (TTL) value of NonPropagating RREQ in larger number of connections reduces E2ED (Figures 8(a), 8(b) and 8(c)), respectively.

Figure 8

E2ED: original and enhanced protocols.

In FSR-mod, shortening $\text{R}{\text{U}}_{\mathrm{Per}}$ interval (both inner scope and outer scope) means quick routing entries' updates. Therefore, in comparison to FSR-orig E2ED is reduced up to $\mathrm{40}\%$ (Figures 9(a), 9(b), and 9(c)). For OLSR-mod, the routing delay increases at the cost of throughput, because routing exchange messages at shorter interval means that OLSR-mod is more suitable to maintain accurate value of MPRs. On the other hand, quick link breakage detection which is made possible due to shorter HELLO interval $\text{RU}\_\text{Tri}$ ultimately provides more convergence. Therefore, OLSR-mod achieves high efficiency. From simulation results, we deduce that, generally, reactive protocols cause more delay as compared to the proactive ones.

Figure 9

E2ED: original and enhanced protocols.

5.3. NRL

NRL is the number of routing packets transmitted by a routing protocol for a single data packet to be delivered successfully at destination. AODV uses gratuitous RREPs but, due to the use of HELLO messages and local link repair, it causes more routing load than DSR-orig. In DSR-orig, grat. RREPs (generated during RD) are not suitable for highly dynamic and more scalable networks. In highly dynamic conditions, presence of stale routes in RC, the resulted RREPs cause broadcast storm. As the number of connections increases, grat. RREPs are also increased because now a higher number of nodes are generating RREPs during RD (network is now congested). There is no explicit deletion mechanism for stale routes; however the RREPs could be decreased in number by limited generation of these messages.

In DSR-orig ( $\text{TAP}\_\text{CACHE}\_\text{SIZE}=\mathrm{1024}$ ), more faulty routes are stored as compared to DSR-mod ( $\text{TAP}\_\text{CACHE}\_\text{SIZE}=\mathrm{256}$ ) which reduces storage of stale routes. This modification lessens the routing overhead by $-\mathrm{34}\%$ in DSR-orig, as shown in Figures 10(a), 10(b), and 10(c), whereas, in high mobilities ( $\mathrm{0}\hspace{0.17em}\text{s}$ Pause Time), stale routes does not interrupt to halt ERS. Thus, high efficiency of DSR-mod is obtained in terms of throughput; however, the cost paid by DSR-mod is more control packets in number.

Figure 10

NRL: original and enhanced protocols.

Both in FSR-mod and OLSR-mod, shortening update intervals increases the number of control messages (in Figures 10(a) and 10(b)). FSR-mod differs too much from OLSR-mod as compared to FSR-orig. Therefore, OLSR-mod augments routing load up to $\mathrm{8.32}\%$ as compared to OLSR-orig, whereas FSR-mod produces $\mathrm{10}\%$ more control packets as compared to FSR-orig.

One common noticeable behavior of all reactive protocols is that, at high speeds and/or high mobilities, routing overhead is higher as compared to moderate and low mobilities and/or speeds. In response to link breakage, the ondemand protocols disseminate RERR message to inform route request generator about faulty links and prevent usage of invalid routes. As in high dynamic situations, link breakage is frequent, so, more RERR messages are generated resulting in high NRL.

6. Performance Trade-Offs

In this section, we discuss performance trade-offs of the chosen routing protocols, what these protocols achieve, and the price they pay. The following subsections include brief description.

6.1. AODV

In AODV, the dropped packets are minimized in number due to the local HELLO messages broadcast after every 1000 ms. These messages are used to check connectivity of active routes. In case of broken link, LLR is initiated which reduces the chances of packet drop however the routing overhead as well as length of the path is increased which increases path delay. Thus, we conclude that AODV achieves increased throughput (or decreases packet loss fraction (PLF)) at the cost of delay and routing load.

6.2. DSR-orig and DSR-mod

In DSR-orig, an initial search for already learned routes is made (i.e., RC search) for a request. In case of negative search, RREQ messages are generated for desired destination. Due to the fact that RC stores multiple routes for single destination, there are fair enough chances of the presence of routes. So, minimization of the chances of RREQ generation increases the average throughput; however, it increases the delay. Thus, DSR's throughput increases at the cost of delay. $\text{TAPE}\_\text{CACHE}\_\text{SIZE}$ reduction in DSR-mod makes fresh route available (RCing) which causes its throughput to increase. However, in highly mobile conditions the cost paid for increased throughput is more control packets.

6.3. FSR-orig and FSR-mod

Instead of event driven updates, FSR-orig uses P updates for topological information exchange. This mechanism reduces the overhead generated by control messages, however, causing more packets to drop (decreased throughput). Thus, FSR-orig minimizes NRL at the cost of throughput. On the other hand, FSR-mod minimizes E2ED at the cost of routing overhead (refer to discussion of simulation results).

6.4. OLSR-orig and OLSR-mod

Either in the absence of mobility or moderate mobility, the MPR computation is minimal due to which more routing packets are generated. This causes increased throughput as well as least E2ED as compared to the other selected protocols. In order to increase robustness, OLSR-orig sends some control messages in advance which locally increases control traffic. Thus, OLSR-orig decreases average E2ED and increases throughput at the cost of routing overhead. In OLSR-mod, throughput is increased at the cost of E2ED (refer to discussion of simulation results).

7. Conclusion

In this paper, the proposed work has three major categories for the chosen routing protocols. The former two propositions include MAC layer framework for IEEE 802.11p and network layer framework for calculating the energy cost, whereas the latter contribution tackles delay in VANETs by making enhancements in the selected routing protocols. NS-2 based simulation results justify the validity and more efficient performance of our proposed work as compared to the existing work. We also conclude that enhanced DSR achieves $\mathrm{16}\%$ more packet delivery as compared to the other selected protocols for all scalabilities and $\mathrm{28}\%$ more throughput in selected mobilities as compared to the original version of DSR.