Road Perception Based Geographical Routing Protocol for Vehicular Ad Hoc Networks

Abstract

Vehicular ad hoc networks (VANETs) are going to be an emerging multihop communication exploit among vehicles to deliver data packets. The special characteristics of vehicular network make the communication link between vehicles unreliable. To handle high mobility and environmental obstacles, most of geographical routing protocols do not consider stable links during packet transmission which lead to higher delay and packet dropping in network. In this paper, we propose road perception based geographical routing protocol named RPGR for VANET. The proposed routing protocol incorporates relative distance, direction, and midrange forwarder node with traffic density to forward the data toward destination in order to improve geographical forwarding between and at the intersections. Simulation results show that the proposed routing protocol performs better as compared to existing solutions.

1. Introduction

Previous researchers consider vehicular ad hoc networks (VANETs) that facilitate ubiquitous connectivity between vehicles and do not rely on expensive network infrastructure. Communication between vehicles and preexisting infrastructure opens up a plethora of different types of promising applications for passengers and drivers [1]. These applications provide safety and comfort and assist drivers to be alert in order to avoid any accident, traffic jam, unseen obstacles, speed violation, internet access, weather information, multimedia services, and so forth [2]. Although being a subclass of mobile ad hoc networks a vehicular network has several unique properties that distinguish it from other ad hoc networks. The most significant differences are high mobility pattern, rapid changing, and dynamic topology which lead to high network partition and disconnectivity in network. However, dynamic topologies are not completely random and movement of nodes is restricted with roads and relatively predictable. The predictability is important factor for link selection but linear topology reduces the possible path redundancy. Another representative characteristic is the impact of obstacles on the communication quality in urban environment in the shapes of trees, buildings, and so forth. Efficient data routing is considered as essential for practicability of these aforementioned applications. One of the main issues in routing protocols is the absence of end-to-end path from source to the destination [3]. To address this diversity many routing protocols employ extensive approaches to flood the network with data packets. The success of routing revolves around various key factors and without an appropriate routing strategy it will continue to be limited.

Analysis of traditional mobile ad hoc routing protocols demonstrates that these protocols are not effective for vehicular networks [4]. One of the main reasons behind these topology based routing protocols (e.g., Ad Hoc on Demand Distance Vector Routing (AODV), Dynamic Source Routing (DSR), and Optimized Link-State Routing (OLSR)) is their route instability due to high velocity of vehicle nodes [5, 6]. Consequently, the routes are frequently broken due to route repair strategy and lead to packets dropping, network overhead, low data delivery ratio, and transmission delay [7]. Geographical routing approaches are offered to forwarding data with the help of neighbor and destination node position without establishing the route. Such examples are Greedy Perimeter Stateless Routing (GPSR) [8], Greedy Perimeter Coordinator Routing (GPCR) [9], and so forth. These protocols offer long distance packet forwarding, which is counted as a departure from long to short distance communication [10], particularly, when the packet carrier node chooses a neighbor node whose distance is short with destination node compared to other neighbor nodes. This leads to greater progress toward the destination. Despite better path stability, these protocols do not perform well especially in urban environment, where they cannot find the next hop or the distance between the source and next neighbor node increases. Furthermore, during packet transmission, the link breaks continuously due to high signal attenuation and the volatile links between vehicle nodes due to high velocity and error prone wireless channels. These problems lead to an increase in signal attenuation rate and packet loss [11], as a result network suffers in terms of packet delivery ratio and network overhead. Thus, it is significant that the routing protocol considers the link quality, direction, density, and some other powerful metrics during packet forwarding toward destination in network.

After a brief discussion, it is clear that routing protocol has to trade-off between vehicular mobility, link quality, and packet progress in multihop routing networks. To overcome these limitations, we propose a road perception geographical routing protocol (RPGR) for packet forwarding with two steps: (1) select an optimal forwarding node, when vehicle is in between two intersections and (2) select the next intersection road when vehicle node is at the intersection. The proposed routing protocol takes routing decisions by road perception metrics such as distance, direction, link quality, and road density, in order to improve the network delay and disconnectivity issues in vehicular urban environment. We carry out NS-2 simulation with SUMO and MOVE to evaluate the performance of the proposed routing protocol and compare it with other existing protocols.

The contribution of this paper is as follows:

• (1)

A directional mid node selection is proposed, in which only mid location node is selected as a forwarder node because the outermost nodes have high probability to exit from transmission range.

(2)

A mechanism is proposed to select next intersection road through link quality and traffic density when relay node is at intersection. Accordingly, we can effectively select the next intersection road for stable data forwarding.

(3)

The proposed routing protocol uses road perception about vehicle direction toward the destination and traffic density at the road to deal with end-to-end delay and data packet loss.

The rest of the paper is organized as follows:

• (i)

  Section 2: existing approaches.

• (ii)

  Section 3: details of basic operation, hypothesis, protocol metrics, flow chart, algorithm, and other components of RPGR.

• (iii)

  Section 4: detailed discussion of the results.

• (iv)

  Section 5: paper conclusion.

2. Related Work

Wide spectrum of different applications is relying on efficient packet routing to enhance the safety and provide comfortable driving environment. A wide range of routing protocols have been proposed to cope with sparse and highly mobile vehicular network and broadly grouped into different types such as topology, geocast, cluster, and geographical or position based routing protocols. Geographical routing protocols establish revived interest in mobile and vehicular networks [12]. In geographical routing, the packet forwarding decisions are based on position of direct neighbors and destination node. These protocols were primitively designed in 1987 for packet radio networks or for mobile networks [13] and cannot be mapped directly to vehicular networks. One of the main reasons behind this phenomenon is that the movement of vehicles reserved by roads and paths is allowed by the scenario. Because of vehicle density on the roads, the routing protocols must utilize localized information to attain the scalability requirements in the network. As a result, the vehicle nodes forward the packets with the help of local information provided through nearby direct neighbors. This process leads to less control overhead because of the suppression of the vehicle node information of other parts of network.

The Greedy Perimeter Stateless Routing (GPSR) [8] protocol was proposed in 2000 for wireless datagram network. It utilizes the position of vehicles and destination node during the process of packet forwarding. The protocol has two principles for packet forwarding: greedy and perimeter forwarding. The greedy mode is used for the selection of neighbor node which is closer to the destination. If the intermediate node has no other neighbor nodes near the destination node, it enters into local maximum. The local maximum issue in network protocol can be addressed by switching by perimeter mode for recovery. The protocol performance is better in open space scenarios due to less obstacles attributed. On the other hand, in city environment protocol suffered from degradation due to restriction owing to obstacles. The longer paths lead to higher delay and routing loops in network. The successor of GPSR is GPCR [9], proposed in 2005 with the concepts of restricted greedy and perimeter forwarding modes. The concept of restricted greedy mode selects the neighbor node which is the closest distance to the destination. In perimeter mode, the protocol uses right hand rule to forward packets to the next neighbor node and assumes the road traffic as planner graph. GSR [14] integrates geographical routing supported by city maps. In the case of source and destination position, the city map is given. It determines the number of junctions with the help of Dijkstra algorithm to find the shortest possible route toward the destination. Then protocol utilizes greedy approach and packet carrier node to select the candidate node closer to the next intersection. This process continues until the destination is reached or lifetime of packets is expired. The aforementioned protocol did not consider multimetric score function for forwarding.

Another positive step is taken by the authors in [15], by proposing RBVT (road-based using vehicular traffic) routing protocol. The protocol selects the sequence of intersections with high network connectivity with the help of on-board navigation systems. The protocol forwards the data packet between two consecutive junctions on the path and discovers the route reply process similar to CAR (connectivity aware routing) [16] protocol. However, RBVT uses real time vehicular traffic information and it leads to increasing robustness and adaptability to network conditions. The protocol is based on two different types of reactive (RBVT-R) and proactive protocols (RBVT-P). The reactive approach is responsible for route discovery decisions on demand and reports to the source with route reply and list of navigated junctions. Proactive approach maintains and creates the route proactively by the transmission of periodic connectivity packets (CPs). These packets contain the visit of connected road segments and cache the topology that they traverse. Nodes utilize this information to find the shortest path toward destination. In the context of performance, the protocol performance is better than AODV, OLSR, GPSR, and GSR. In addition, the RBVT-P can be feasible for delay-sensitive applications, whereas RBVT-R can be used for high throughput applications. The issue in this protocol is high network overhead due to maintenance and exchange of nonlocal information. The packet header carries the list of junctions, which might lead to scalability issue in the network.

Connectivity aware minimum delay geographic routing protocol (CMGR) [17] was proposed in 2011, to take high connectivity for route selection in sparse network. On the other hand, in dense situations the protocol determines the routes through adequate connectivity and selects route with minimum delay. The hypothesis of protocol is the availability of gateways which are randomly distributed along roadside and connected to IPv6 network. The route discovery messages are used to construct full paths toward gateways and intermediate vehicles attach their location and rebroadcast the discovery messages. The gateway receives several messages from the same vehicle node via different routes and then selects the most appropriate route after the connectivity evaluation. In addition, for every route discovery message gateways send the receiving messages to the source vehicle and then the decision taken by source node about the suitable route based on connectivity evaluation. The protocol continuously checks the routes quality and a great amount of data is forwarded through these favorable routes. As a result, the protocol has higher delay, congestion, and packet dropping issues in such routes. To eliminate the network bottleneck and enhance the network throughput load balancing mechanism is needed [18].

Another geographic stateless routing (GeoSVR) [19] proposes two approaches: OPF (optimal forwarding path) and RF (restricted forwarding). The OPF addresses the local optimum issues in sparse network and RFA solves the impact of unreliable wireless channel issues. The first approach calculates the path through distance to destination and vehicle density for each road and Dijkstra algorithm is applied to find shortest suitable forwarding path with minimum weight. However, in large city maps the performance of Dijkstra algorithm is the worst due to high computational complexity to weighted whole graph to find a connected path. To address this complexity the protocol subtracts a connected subgraph from map according to source and destination positions. The intersections are selected near the source and destination nodes and the rectangle surrounding the subgraph is constructed based on these intersections. At last the optimal forwarding path is used on subgraph, yet the protocol has computational complexities due to vehicular unpredictable environment.

A stable direction based routing protocol (SDR) [20] proposes the combination of direction and path duration prediction. The protocol selects the nodes with direction only to reduce the frequency of flood requests and select the route based on link duration. The SDR also has discovery mechanism to deal with path expiration in order to decrease end-to-end delay in network. In SDR protocol node broadcasts the RREQ message to add location information with AODV protocol to determine the direction for route discovery. The protocol labels each link with LET considering the link stability and PET (path expiration time) for stable path, where PET is the minimum LET on the path. Basically, the author merges topology and position based ideas to deal with broadcast storm and end-to-end delay issue in VANET. The protocol still suffers network delay and computational complexity due to estimation of LET and maintenance mode.

A connectivity aware intersection based routing protocol (CAIR) [4] proposes the optimal route selection with higher probability of connectivity to address the delay issue in network. The CAIR is an intersection geographical based routing protocol which selects the dynamic intersections with prediction greedy and recovery strategies. The protocol selects the rectangle restricted with ellipse plotted area to find the route. To take connectivity and path delay into consideration, the protocol addresses the disconnection problem in large scale density environment. The directional forwarding approach is used to reduce the average transmission delay with several relays. The protocol also uses on demand position forecasting for next node selection and reduces prediction error. Protocol still suffers local optimum issue in network especially in sparse network.

3. Hypothesis of Protocol

The following assumptions have been made for designing the proposed routing protocol:

• (i)

Vehicles are equipped with satellite based global positioning system (GPS) in order to determine vehicle location and facilitate multihop communication in network.

(ii)

Each vehicle in network determines the position of its neighbor junctions by preloaded digital street level maps.

(iii)

Every vehicle is also aware of vehicular traffic through a simple distribution mechanism for on road traffic estimation and traffic sensors installed beside the junctions.

(iv)

The beacon or hello messages are exchanged to identify the neighbors presence, position, and direction in network.

(v)

The dedicated short range communication (DSRC) standard is used for communication.

(vi)

Maximum forwarding distance is fixed.

3.1. Routing Protocol

In vehicular environment, geographical routing protocols performance is better particularly in warning system applications. Basically in these protocols the packets are forwarded to all the vehicle nodes within specified geographical area which leads to looping and network overhead issues in network [21]. A node has a set of one-hop neighbor nodes within transmission range that checks the optimal forwarding node with different strategies. These vehicle nodes are moving randomly and frequently change their position. Each vehicle node periodically broadcasts the beacon messages to know the mobility characteristics and obtain the information of each other. Therefore, the beacon messages contain the information of current position, time, direction, and speed acquired from GPS [22]. However, due to vehicle speed the nodes may leave the radio transmission range before receiving the transmitted packets which lead to packet loss in network. To improve and better routing decisions, the greedy forwarding approach is used for heterogeneous unevenly random vehicular environment [23]. However, in these conventional greedy routing protocols the source node selects the neighbor node, which is closer to the border of transmission range and destination node in order to forward the packets toward destination. Packet forwarding from source to destination node based on a single metric is not feasible due to frequently changing topology of vehicular networks. Various types of measures affect wireless link quality between vehicle nodes such as stability, forwarding progress, and reliability. Therefore, only considering the shortest path and length of route is not sufficient but the reliability of the paths must also be taken into consideration. To address this issue the proposed protocol utilizes the mid area node instead of the transmission range. Due to different constraints in vehicular network such as high mobility, unreliable channel conditions, and high collision probability, the proposed routing protocol uses mid area node to determine the distance and direction metrics in between intersections. When the relay node is at the intersection curve metric distance and traffic density are used to select the next route toward the destination. The coming sections describe the protocols operations in detail.

3.2. Proposed Routing Protocol Packet Forwarding Example

Before describing the proposed routing protocol, we briefly describe the key idea and rationales behind it. The vehicular environment is highly mobile and dynamic and due to these characteristics the route decision based on one metric is always selected as suboptimal route in network due to unstable quality of route. The proposed geographical routing protocol is working with two modes of operations in network: between intersections and at the intersection that forward the packet with high stability and reliability toward the destination. In case of less vehicles on the roads, protocol used carry and forward mechanism to tackle disconnectivity in network. If node between intersections wants to forward a packet, it searches the closer neighbor with destination than itself. The process also checks the coordinator node, and if the coordinator node is available the protocol starts the intersection based priority operation. If there is no coordinator node available, then it will check distance, direction, and mid region node to forward the packet.

Figure 1 shows the protocol forwarding example, where the source node wants to send the packet toward destination. All vehicles are equipped with global positioning system and digital map to determine vehicles location. If the source node located in between intersections, it incorporates direction and distance and select mid transmission range neighbor node to relay the packet. The midrange vehicles relay the data and whenever it reaches at intersection, the source node checks the curve metric distance toward destination and the traffic density to select optimal route and next intersection toward destination. There are two routes toward destination: low density through intersections 1, 2, and 3 and high density route through intersections 1, 4, and 3. Protocol selects the high density route, that is, 1, 4, and 3 toward destination. Figure 2 shows complete flow chart of proposed RPGR protocol.

Figure 1

Road perception based geographical routing protocol (RPGR) operation between intersections and at intersection.

Figure 2

Flow chart of RPGR.

3.3. Routing Metrics between Intersection

3.3.1. Distance and Direction

The distance and direction are considered to be very important parameters, because in transmission range of vehicle node there is a possibility that two nodes are very close to each other or they are separated through a distance of maximum radio range. The shorter distance of vehicle nodes leads to high number of hops and nearest nodes can generate higher interface in network [24]. If source node selects the closer node with maximum radio range, the probability of link failure increases because of high signal attenuation of unreliable wireless channels. The selection of outermost and extreme end of transmission range nodes may have higher probability to exit from radio range and drop the packets. The proposed protocol addresses this issue by giving mid priority to the node by calculating the distance parameter. The mid priority significantly improves the reliability of packet forwarding in error prone wireless channels and the mid distance node has more choices compared to outermost nodes. Longer distance from source node leads to higher packet error and delay in the wireless channel among vehicles [25]. The GPS already provides the vehicle node position in network, and Pythagoras theorem (1) is used to determine the distance between source node and neighbor node as shown in Figure 3, where the positions of two vehicle nodes S and R are $\left(x_1,y_1\right)$ and $\left(x_2,y_2\right)$ , respectively. Whenever node R receives the RREQ message from node S, it will calculate distance between S and R

$$\begin{array}{cc}& \text{Distance}=\sqrt{{\left(x_2-x_1\right)}^2+{\left(y_2-y_1\right)}^2}.\end{array}$$

(1)

The sender vehicle node selects the next forwarding hop, where direction is closest to the source and destination straight line which moves in the same direction for stable packet forwarding. The vehicle nodes direction is constrained by the roads and in straight highway scenarios, vehicles are moving in the same or opposite direction. But in realistic urban environment, the direction vectors are always parallel to each other. Thus, the proposed protocol uses this great deal to select stable routes toward destination. In Figure 4, when the source node intends to route the data packet toward the destination, it sends the packet from its directional neighbor node toward the destination node. The straight line shows the direction between source and destination whereas arrow line represents the direction of source and its neighbor nodes.

Figure 3

Distance calculation of source and its receiver or neighbor node.

Figure 4

Area of shaded region ( $S_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}=M_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}+B_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}$ ).

Having the distance and direction toward the destination determined, the mid region node is selected to forward the data packet. The source node calculates the mid distance next hop as follows.

3.3.2. Finding Mid Region Node for Next Hop Node

The mid region node covers the maximum distance and transmission range and has more opportunities to forward the data packets compared to border nodes. The border nodes have higher probability to exit from transmission range especially highly mobile vehicular ad hoc network environment. Therefore, we have considered an area that is in the mid transmission range of source node. The mid area region is shown in Figure 4.

In Figure 4, the source node has predefined maximum transmission range (R) and the shaded area ( $S_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}$ ) in transmission range divided into two parts, mid ( $M_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}$ ) and border area ( $B_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}$ ) of transmission range. The mid area node can be selected from shaded area ( $M_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}$ ) because the area is located in mid transmission range toward destination. Improved greedy approach is used to select a next forwarder and mid area node from shaded area ( $S_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}$ ). The mid area is also known as interaction area with other neighbors within ${\mathrm{R}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{u}\mathrm{s}}_1$ , and others with ${\mathrm{R}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{u}\mathrm{s}}_2$ . The shaded area $S_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}$ can be calculated as

$$\begin{array}{cc}& S_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}=M_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}+B_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}},\end{array}$$

(2)

where

$$\begin{array}{cc}& M_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}={\mathrm{R}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{u}\mathrm{s}}_1^2·{\alpha }_1-\frac{{\mathrm{R}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{u}\mathrm{s}}_1^2·\sin \left(2{\alpha }_1\right)}{2},\\ B_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}={\mathrm{R}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{u}\mathrm{s}}_1^2·{\alpha }_2-\frac{{\mathrm{R}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{u}\mathrm{s}}_2^2·\sin \left(2{\alpha }_2\right)}{2}.\end{array}$$

(3)

As shown in Figure 4, the line between source node and destination node is the bisector of angle 90° ( ${\alpha }_1={45}^{°}$ ); therefore area of shaded region, $S_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}$ , is

$$\begin{array}{cc}& S_{\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}}={\mathrm{R}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{u}\mathrm{s}}_1^2\left[\frac{\pi -2}{4}\right]+{\mathrm{R}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{u}\mathrm{s}}_2^2\left[{\alpha }_2-\frac{\sin \left(2{\alpha }_2\right)}{2}\right].\end{array}$$

(4)

The shaded area is a combination of two arcs, one with Radius₁ and the other with Radius₂, and the value of ${\alpha }_2$ depends on the transmission range Radius₁ and the distance between source and destination node.

If source node does not find mid area node in region with specified time interval, then it will select closest node with destination within transmission range to forward the packet.

3.4. Routing Metrics at Intersection

When the data is forwarded between intersections and reached at the intersection node, it calculates the traffic density and direction toward the destination in order to select next forwarder node and route. At the intersection the node looks for the position of neighbor junctions and curve metric distance to the destination using the map. The curve metric refers to the distance measured when following the geometric shape of road. The junction node decides the next route based on vehicular direction, highest traffic density, and geographically closest junction. To select the next junction node, the position of adjacent junctions is used through digital map. The optimal next junction has highest weight value with directional traffic density and a junction closer to the destination.

As we can see, the proposed routing protocol operation at intersection is based on two factors: shortest distance to the destination, directional traffic density. For the first factor, RPGR computes distance to the destination and prefers shortest distance to the destination.

The weight of path selection as the vehicle distance from the delivery node to destination is as follows:

$$\begin{array}{cc}& {\mathrm{D}\mathrm{i}\mathrm{s}}_{\left(wv\right)}=\max \left[\log \left(\frac{{\mathrm{C}\mathrm{D}}_{\left(s,d\right)}}{{\mathrm{C}\mathrm{D}}_{\left(j,d\right)}}\right),0.1\right].\end{array}$$

(5)

In (5), the ${\mathrm{D}\mathrm{i}\mathrm{s}}_{(wv)}$ shows the distance with weight value and ${\mathrm{C}\mathrm{D}}_{(s,d)}$ shows the curve metric distance from source node to destination and ${\mathrm{C}\mathrm{D}}_{(j,d)}$ presents the curve metric distance from current junction to destination.

In (6), the ${\mathrm{D}\mathrm{i}\mathrm{r}}_{wv}$ (direction weight value) with link quality (LQ) factor is calculated between direction of travel vehicle $\overrightarrow{D_n}$ and direction of packet transmission $\overrightarrow{D_{\mathrm{p}\mathrm{t}}}$ . The link quality measures by optimal transmission range of neighbor nodes

$$\begin{array}{cc}& {\mathrm{D}\mathrm{i}\mathrm{r}}_{wv}=\left[\mathrm{L}\mathrm{Q}\left(\overrightarrow{D_n},\overrightarrow{D_{\mathrm{p}\mathrm{t}}}\right)\right].\end{array}$$

(6)

Once the vehicle receives a packet, it calculates the weight score of each neighboring junction in real time traffic density ( ${\mathrm{T}\mathrm{D}}_{wv}$ ), with average number of vehicles ( $N_{\mathrm{a}\mathrm{v}\mathrm{g}}$ ) and constant degree of connectivity ( $N_{\mathrm{c}\mathrm{o}\mathrm{n}}$ ) within a cell and closeness of the candidate intersection to the destination point $D_c$ . For traffic density estimation protocol calculates the average number of vehicles ( $N_{\mathrm{a}\mathrm{v}\mathrm{g}}$ ). The degree of connectivity ( $N_{\mathrm{c}\mathrm{o}\mathrm{n}}$ ) calculates the ideal degree to ensure end-to-end connectivity. Thus, $N_{\mathrm{a}\mathrm{v}\mathrm{g}}/N_{\mathrm{c}\mathrm{o}\mathrm{n}}$ determines the whole road density. The $D_c$ shows the proximity of the candidate junction to the destination point, as shown in (8)

$$\begin{array}{cc}& {\mathrm{T}\mathrm{D}}_{wv}=\left[1-D_c\right]+\left[\min \left(\frac{N_{\mathrm{a}\mathrm{v}\mathrm{g}}}{N_{\mathrm{c}\mathrm{o}\mathrm{n}}},1\right)\right].\end{array}$$

(7)

β, γ, δ are used for weighting factors for distance, direction, and traffic density, respectively, with $(\beta +\gamma +\delta =1)$ .

Hence, based on the above analysis, (8) defines the weighting score of the next intersection (score (NI))

$$\begin{array}{cc}& \mathrm{S}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\left(\mathrm{N}\mathrm{I}\right)=\beta \max \left[\log \left(\frac{{\mathrm{C}\mathrm{D}}_{\left(s,d\right)}}{{\mathrm{C}\mathrm{D}}_{\left(j,d\right)}}\right),0.1\right]+\gamma \left[\mathrm{L}\mathrm{Q}\left(\overrightarrow{D_n},\overrightarrow{D_{\mathrm{p}\mathrm{t}}}\right)\right]+\delta \left[1-D_c\right]+\left[\min \left(\frac{N_{\mathrm{a}\mathrm{v}\mathrm{g}}}{N_{\mathrm{c}\mathrm{o}\mathrm{n}}},1\right)\right].\end{array}$$

(8)

As we can see the above equation is based on three factors.

The first factor ${\mathrm{D}\mathrm{i}\mathrm{s}}_{(wv)}$ is to measure the distance to the destination in road length. The shorter distance is preferred toward the destination. The second factor ${\mathrm{D}\mathrm{i}\mathrm{r}}_{wv}$ measures the vehicle direction with link quality factor between travel vehicle and packet transmission. The last factor is the traffic density ${\mathrm{T}\mathrm{D}}_{wv}$ between the current and potential intersection. Well balanced higher density road is selected. See Algorithm 1.

Algorithm 1

(a) Between Intersections

Notations

FV: forwarding vehicle

SMV: set of mid-region vehicle (potential next forwarder vehicle)

DV: destination vehicle

SV: source vehicle

NHV: next hop vehicle

SNV: set of one hop neighbor vehicle

ICF: a flag for determine the packet carrier node is at the intersection or between intersections

α: angle used for mid-region area calculation

$t_i$ : wait for random time

Input

Process

 ( $\mathit{1}$ )    Initialization

      FV = SV

      SMV = ϕ

      NHV = ϕ

      SNV = ϕ

      α = 90°

 ( $\mathit{2}$ )    SNV = {neighbor of forwarding vehicle}

 ( $\mathit{3}$ )    if (DV ∈ SNV) then

             Send the packet to original destination vehicle

             exit

 ( $\mathit{4}$ )    else

 ( $\mathit{5}$ )    if ICF = 0 then

      while (SMV == $\mathit{\varphi }$ )

             (a) Determine the segment area using (2)

             (b) SMV = {Vehicles in mid area}

             (c) If SMV == ϕ and α < 90°

               $\alpha =a+\mathit{10}$

              else

                $t_i$ (wait for random time)

               α = 50°

      end while

 ( $\mathit{7}$ )     else

(b) At the Intersection

 ( $\mathit{8}$ )    if ICF = 1 then (node is at intersection)

             (a) Determine the curvmetric distance from source node to destination and from current junction to

                destination, (5)

             (b) Determine the direction with link quality, (6)

             (c) Determine the traffic density, (7)

 ( $\mathit{9}$ )    Select the next intersection with weighting score

 ( $\mathit{10}$ ) transmit the packet to NHV and NHV = FV

   end if

   end if

 ( $\mathit{11}$ ) Exit

4. Performance Evaluation

This section is based on two parts. The first part presents the simulation scenario, related parameters, and performance evaluation. The second part discusses the simulation results and evaluation of road perception geographical routing protocol (RPGR) against CMGR, GeoSVR, and SDR.

4.1. Simulation Scenario

To analyze and validate the proposed routing protocol, the network simulator NS-2.34 [26] on Linux platform is used with model mobility generator for vehicular networks (MOVE). The mobility generator is used for realistic vehicular movement generation in the urban environment. MOVE is based on open Simulation of Urban Mobility (SUMO) simulator. It is an open source microtraffic time-discrete vehicular traffic generator package [27]. MOVE has two modules for a vehicular environment called vehicle movement editor and road map editor. The road map editor gives essential features of roads such as number of lanes, roads, junctions, traffic lights setup. Vehicle editor is used to set the speed of vehicles, number of vehicles, probability of right or left turning, and so forth. To set all required parameters in two editors, the trace file is generated by MOVE and directly used in NS-2. The vehicles are travelling with a speed of 40–70 km/h. The experiments are restricted in a 3,968 × 1,251 m rectangular area of Chicago city, with 370 road segments and 124 intersections extracted from the US Census Bureau, TIGER/Line database [28]. The vehicular density is set with 100 to 350 nodes and each vehicle generates beacon message of 0.5 s intervals. The packet size is set with 512 bytes, 2 Mb/s data rate, and 300 m transmission range, where these parameters are suggested by various studies such as [15, 29]. The IEEE 802.11b standard is used to analyze the proposed protocol [30]. Further, Nakagami radio propagation model is used for physical layer to compute the fading features of wireless channels among vehicles [31]. Many researchers recommend this model due to a more realistic output data realistic with real time mobile communication environment [32]. Nakagami model has one of the best features, where each signal component has its own received signal strength for multipath routing from source toward destination with different medium propagation features. We also set the medium fading intensity for urban environment. The total of 20 simulations is running and each simulation has 500 s time with 95% confidence intervals. Table 1 presents the summarized simulation parameters based on previous realistic studies [25, 33]. Figure 5 shows the fragmented city map of Chicago city used in SUMO simulation snapshots.

Table 1

Simulation parameters.

Parameters	Value
Network simulator	NS-2
Mobility model	SUMO-MOVE
Simulation area	3,968 × 1,251
Simulation time	500 s
Propagation model	Nakagami
Traffic density	100 to 350
Vehicle velocity	25–50 km/h
Transmission range	300 m
MAC protocol	IEEE 802.11b DCF
Data packet size	512 bytes
Channel bandwidth	3 Mbps
Maximum packet generation rate	6 packets/second
Maximum number of source nodes	12
Weighting factors $(\beta +\gamma +\delta )$	(0.01, 0.01, 0.01)

Figure 5

Fragmented city map of Chicago city used in SUMO simulation.

Then map is used as an input in MOVE to incorporate further information in the map. Afterwards the trace files and other configurations have been generated to analyze RPGR protocol. To evaluate the proposed routing protocol, we implemented three routing protocols CMGR [17], GeoSVR [19], and SDR [20] with known traffic model and simulation setup. These routing protocols are used as a benchmark for comparison purposes. There are many reasons to adopt CMGR, GeoSVR, and SDR for comparison such as all belonging to geographical routing, being designed for urban environment, and using multirouting metrics. Firstly, the CMGR adopts continuously changing network status by high connectivity and minimum delay in sparse and dense networks to select the route. In addition, the CMGR was designed for urban environment with multirouting metrics such as connectivity, minimum delay. The GeoSVR is geographical stateless routing protocol. It adopts vehicle density on every road to avoid sparse connectivity. The third protocol SDR uses direction and path duration prediction to select next hop in network. The proposed RPGR also uses midrange node, link quality, and direction as routing metrics to select next hop or route in network. The performance of the proposed routing protocol is evaluated by packet delivery ratio, end-to-end delay, average path length, and different data packet sizes. The elaborate description of these metrics is as follows:

• (i)

Packet delivery ratio (PDR) is defined as fraction of successfully received data packets at the destination over the total sending packets from source side. This metric shows the ability of routing protocol to successfully transmit data from source to destination in network.

(ii)

The end-to-end delay is defined as total time of transferring data from source node to destination. Basically the packet delay is a sum of sending buffer, retransmission, medium access delay due to interface queue, propagation delay, and relay election delay.

(iii)

The average path length is defined as an average number of nodes during transmission of data packets between source and destination. This metric also demonstrates the path quality.

4.2. Simulation Results

The proposed routing protocol is evaluated with different parameters. By varying the different parameters, various experiments are conducted such as the impact of density, vehicle velocity, different number of source nodes in network, and different data packet sizes. The comparison study is based on the proposed routing protocol and state of the art of the existing three geographical routing protocols.

4.2.1. Traffic Density Analysis

The simulation results show the positive traffic density analysis of RPGR compared to other state of the art routing protocols. In these experiments, the vehicle traffic varies from 100 to 350 nodes. Figure 1 shows that RPGR outperforms in terms of data delivery in medium and dense environment compared with other state-of-the-art routing protocols.

In most of the results, we observed that there is a decrease in data delivery ratio as the data traffic increases. The results of packet delivery ratio in Figure 6(a) present a low performance of RPGR when traffic densities are low but still better than other protocols. The performance of CMGR is low because of its discovery mechanism to construct a full path toward gateway and intermediate vehicles attach their location and rebroadcast the discovery messages. The GeoSVR performance is better than CMGR with 150 vehicle nodes because of its distance and traffic density metrics. The Dijkstra algorithm is used to find the shortest optimal path with minimum weight. The DSR protocol performance is not better than CMGR and GeoSVR, because of its path duration prediction metric. SDR is a combination of topology, geographical routing protocol, and RREQ message with location information to determine the direction of route discovery. When the traffic density is low, the wireless links between the source and selected next hop will be weak and sometimes out of transmission range which leads to fewer packets' forwarding toward the destination. The RPGR performance is better even with less traffic density because it uses midrange node for the next forwarding candidate with direction metric where at the intersection the traffic density is taken into account. Figure 6(b) shows the packet delivery ratio with 250 vehicle nodes in network. The trend in this graph is better for PDR compared with 150 nodes, because more vehicle nodes in network cover large sections of the map and transmission range. The RPGR routing protocol performance is better with 250 nodes and much higher compared to sparse network with 150 nodes. When the node density increases, the shortest path along the roads becomes more likely to have enough nodes and the packet delivery ratio automatically increases. With 250 nodes the GeoSVR performance is better than CMGR and SDR, simply because GeoSVR finds the shortest path in network compared to SDR and CMGR. The SDR performance is not better than CMGR at the start but when the network will stabilize, it is closer to CMGR. In the last graph, Figure 6(c), the vehicle nodes are set to 350 and RPGR performance is better compared to less density in network. With increasing nodes in network, the CMGR lags behind the SDR and GeoSVR, since CMGR continuously checks the routes quality. A great amount of data is forwarded through these favorable routes leading to packet dropping, delay, and congestion issues in dense situations. The RPGR performance is better because of its direction and real time traffic density metrics.

Figure 6

Average delivery ratio of CMGR, GeoSVR, SDR, and RPGR in network with 15 flows and node densities: (a) 150 nodes, (b) 250 nodes, and (c) 350 nodes.

4.2.2. Average Delay

Figure 7 shows that road perception geographical routing (RPGR) has the smallest average delay compared to other state of the art routing protocols. The proposed routing protocol selects the mid area forwarding node and curve metric distance with high traffic density route. On the other hand, the performance of SDR is also better compared to CMGR and GeoSVR, due to SDR selection of nodes which is based on direction only. This is to reduce the frequency of flooding and select route based on link duration. The SDR discovery mechanism with path expiration also help reduce end-to-end delay in network. The CMGR protocol average delay increases due to route discovery messages to construct the full path toward destination. The gateway receives several messages from the same vehicle for further decision that leads to high delay in network. In Figure 7(b) the average delay for RPGR consistency remains, whereas the average delay of CMGR, GeoSVR, and SDR increases with the increase of density. The average delay of CMGR continuously increases because it continuously checks the routes quality and a great amount of data is sent through these favorable routes. The GeoSVR performance is better than CMGR because of its Dijkstra algorithm but it still suffers because of computational complexity to weighted whole graph in order to find a connected path in network. The SDR performance is better than MGR and GeoSVR, because of its directional path duration prediction and discovery mechanism which deals with path expiration in order to decrease end-to-end delay in network. The results with 350 nodes in Figure 7(c) show the proposed protocol performs better compared to state of the art protocols. The RPGR performance is better in high density situations because of its density metric and midrange vehicle node selection. Other protocols still suffer when roads are more congested.

Figure 7

Average delay of CMGR, GeoSVR, SDR, and RPGR in network with 15 flows and node densities: (a) 150 nodes, (b) 250 nodes, and (c) 350 nodes.

4.2.3. Average Path Length

Figure 8 presents the relationship between hop count and vehicular traffic density in medium fading channel condition. In order to compare the average path length of RPGR with state of the art routing protocols, we observe that the routed packets through RPGR need less hop toward destination as compared to state of the art routing protocols. The one reason for this better performance is due to midrange hop selection with direction toward the destination in network. In Figure 8(a) the average path length of GeoSVR and SDR is almost near to the proposed routing protocol due to their shortest path and direction metrics. When we increase the traffic density up to 250 nodes, Figure 8(b), we observe that the RPGR average path length is better than state of the art protocols. The CMGR routing protocol has more hop count compared to GeoSVR and SDR because of its link quality over forward progress on roads. The SDR protocol uses the shortest path in network which is better than CMGR and GeoSVR. In the case of 350 vehicle nodes (Figure 8(c)), the performance of RPGR, GeoSVR, and SDR in terms of average path length presents less difference. In high density the source nodes always check their neighbor node with their own metrics by looking at the optimal forwarding nodes and check all their neighbors. The longer path lengths do not necessary translate, as expected, the worst performance. On the contrary better forwarding nodes lead to better performance. The proposed RPGR still has better average path length compared to state of the art routing protocols.

Figure 8

Averagehop count of CMGR, GeoSVR, SDR, and RPGR in network with 15 flows and with different node densities: (a) 150 nodes, (b) 250 nodes, and (c) 350 nodes.

4.2.4. Analysis of Packet Size

In our final simulations, in order to present the effect of data packet size, we conducted experiments with 200 vehicle nodes by changing the packet size from 256 to 2,048 bytes in network. Figure 9 illustrates the effect of packet size of the proposed RPGR routing protocol with state of the art CMGR, GeoSVR, and SDR routing protocols. As expected, the trend of proposed routing protocol shows the best performance in network whenever we increase the packet size. This degradation refers to the larger packet size that leads to the higher bandwidth consumption and high saturation in wireless channel. As shown in Figure 9(a), the packet delivery ratio for all protocols decreases due to huge traffic load with large packet size which finally leads to high packet loss. However, the performance of RPGR is larger with other protocols, particularly when the data packets are fragmented during transmission. If the fragmentation is lost the whole packet will be useless and cause a failure of packet delivery ratio in network. In this case the routing protocol determines other candidate vehicles which cause the overhead control and consume more bandwidth.

Figure 9

Effect of varying data packet size on the performance of RPGR and GeoSVR, SDR, and CMGR protocols. (a) Packet delivery ratio. (b) Average packet delay. (c) Average path length.

The second experiment in Figure 9(b) plots the average delay of proposed RPGR protocol with other state of the art routing protocols and based on the results in the presence of different packet sizes, the RPGR delay is lesser than the other. On the other hand, the SDR protocol delay is better than CMGR and GeoSVR. The CMGR protocol packet delay is high compared to other protocols due to the loss of some high latency in data packets. The last experiment in Figure 9(c) plots the node count with different packet sizes in network. The SDR and the proposed RPRG average path length are almost similar compared to other protocols. The reason of this similarity is direction metric toward destination.

The proposed road perception geographical routing (RPGR) performance is better in the presence of different traffic density and packet sizes in the network. The protocol determines the mid area node by checking the distance of neighbor nodes and direction toward the destination. This mid area selection gives advantage to handle high mobility and frequently changing topologies in vehicular networks. When the candidate node at the intersection protocol checks the curve metric distance toward destination and high density route, it calculates the optimal route to forward the packet. Proposed routing protocol is well defined as an efficient routing scheme for urban environment to surpass the data in network. Different results show better performance of the proposed protocol compared to other state of the art routing protocols.

5. Conclusion

This paper has presented the road perception geographical routing protocol (RPGR) for packet forwarding in VANET for urban based environment. The protocol takes advantage of the road layout to fulfill the requirement of efficient routing. The RPGR considers distance, direction, and mid region node to reactively select the next intersection. Whenever the forwarder node is at the intersection, curve metric direction and high traffic density are rechecked and forward the data toward destination in the network. The performance of the proposed routing protocol has been analyzed in simulation with three existing CMGR, GeoSVR, and SDR routing protocols. The results show better performance of RPGR in terms of packet delivery ratio, average packet delay, and average path length with different vehicle density and packet size. The results also prove that the proposed protocol is a realistic solution for urban area.