The GPSR Routing Protocol in VANETs: Improvements and Analysis

Abstract

One of the most critical problems in VANETs is the frequent link breakage caused by the high velocity of vehicles. Due to the short connection lifetime between vehicles, the communication paths are frequently interrupted during the transmission of data packets between the source and destination vehicles, causing the search for a new route that increases the routing overhead and diminishes the PDR and the throughput. To manage those issues, several routing protocols have been proposed by considering important factors to improve the quality of service in VANETs. The GPSR (Karp and Kung in ACM MobiCom, pp. 243–254, 2000) for Greedy Perimeter Stateless Routing is the most popular position-based protocol. In this paper, we propose three new models to enhance this protocol that guide the selection of the next-hop vehicle based on some important metrics of the participating nodes. We have used a real urban scenario to evaluate the performance of our models, by varying the vehicle density and measuring the percentage of packet delivery ratio, throughput and routing overhead during the transmission of data packets.

1 Introduction

VANETs are considered as a special case of Mobile Ad-Hoc Networks (MANETs); they have many characteristics compared to other class of MANETs. Indeed, due to the high speed of vehicles the network’s topology changes frequently, which affect the connectivity between vehicles that changes regularly. Due to those characteristics, designing an efficient routing protocol to route packets to their final destination is a big challenge.

As mentioned and detailed in [1, 2], routing protocols in VANETs are classified mainly into four types. They are position-based [3], topology-based [4], multicast-based [5] and broadcast-based routing protocols [6]. Researchers believe that position-based routing protocols are the best one in terms of PDR, routing overhead, throughput and scalability [7, 8]. Therefore, we will focus in our work on GPSR routing protocol that is a position-based routing.

In this paper, we suggest three innovative position-based protocols based on GPSR and some important mobility parameters used to improve the classical GPSR in terms of PDR, throughput and routing overhead in VANET scenarios; the proposed protocols are called Density-Velocity-Aware-GPSR (DVA-GPSR), DRL-GPSR for Direction-Route Lifetime aware GPSR and Enhanced GPSR (E-GPSR). To select the next-hop vehicle, the three proposed protocols take into consideration some important factors:

• The speed variation between the target and the next-hop candidate vehicle.

• The vehicles’ direction utilized to calculate the angle direction between the destination’s direction and the next-hop candidate’s direction.

• The lifetime of the route, that is between the current node and its neighbors.

• The density of the next-hop candidate; this metric is utilized to identify the connectivity mode for each path (sparse, medium or dense).

• The distance between the current node and the destination.

The remaining of this paper is organized as follows: in Sect. 2, we describe the classical GPSR protocol. In Sect. 3, we clarify the approach of our proposed protocols. In Sect. 5, we give and evaluate the efficiency of the three proposed protocols compared to the classical GPSR. In the last section, we present the conclusion of this paper.

2 An Overview of the Classical GPSR

GPSR [9] is a routing protocol originally designed for MANET and rapidly adapted to VANET. In this section, we will give a general review on GPSR routing protocol that belongs to the class of position-based protocols. This GPSR protocol uses two approaches to forward packets. The greedy forwarding approach is used to forward packets to the closest neighbor to the destination. When this approach fails, the perimeter-forwarding mode will be applied that is based on the right-hand rule strategy. Those techniques get good results in MANETs. However, in the case of city scenario, the GPSR still suffers from some disadvantages that reduce its performances.

3 The Proposed Enhancements of GPSR

Our three proposed protocols are based on the classical GPSR. Each enhancement necessitates two components: a GPS implemented in all vehicles in order to give the exact vehicle’s position and an On-Board Unit (OBU) equipment used to connect the vehicles. Each proposition consists of many factors, and they are discussed below.

3.1 E-GPSR

The strategy used by E-GPSR is based on three metrics: the speed variation, the distance between the transmitter vehicle and all its neighbors and the density of the current node’s neighbors according to formula (1) and (2), respectively. After that, we use the Eq. (3) to calculate the link weight function for this strategy.

In the Eq. (3) the d_i is the density of the next-hop candidate i; the use of this metric reduces the bad influence of sparse connectivity problem. The node that has more neighbors increases the probability of being selected as the next hop. Therefore, we take into account the inverse of di (1/d_i) in LWF1.

$$S_{{{\text{id}}}} = \left| {S_{{\text{i}}} - S_{{\text{d}}} } \right|$$

(1)

where S_i and S_d signify, respectively, the speed of the neighbor vehicle called i and the speed of the destination vehicle.

$$D_{{\text{id }}} = \sqrt {\left( {y_{i} - y_{d} } \right)^{2} + \left( {x_{i} - x_{d} } \right)^{2} }$$

(2)

where (x_i, y_i) signifies the neighbors’ location called i and (x_d, y_d) denotes the location of the destination vehicle.

$${\text{LWF}}1 = \alpha *D_{{{\text{id}}}} + \beta *\left( {\frac{1}{{d_{{\text{i}}} }}} \right) + \theta *S_{{{\text{id}}}}$$

(3)

where α + β + θ = 1.

3.2 DVA-GPSR

The strategy adopted by DVA-GPSR is based on four factors. The new metric is the angle direction between the transmitter vehicle and the destination vehicle. In fact, if two vehicles communicate with each other and have the same direction, the link is more stable. To calculate the angle direction, we use the Eq. (8) and the Eq. (9) will be used to calculate the link weight function (LWF), where α + β + θ + γ = 1.

In Eqs. (4), (5), (6) and (7), iV and dV are, respectively, the velocity of the next-hop candidate and the velocity of the destination.

$$a = {\text{iV}}\,.\,x*{\text{dV}}\,.\,x$$

(4)

$$b = {\text{iV}}\,.\,x*{\text{dV}}.y$$

(5)

$$c = {\text{iV}}\,.\,x^{2} *{\text{dV}}\,.\,x^{2}$$

(6)

$$d = {\text{iV}}\,.\,y^{2} *{\text{dV}}\,.\,y^{2}$$

(7)

$$\varphi_{{{\text{id}}}} = \cos^{ - 1} \left( {\frac{{\left( {a + b} \right)}}{{\left( {\sqrt c *\sqrt d } \right)}}} \right)$$

(8)

$${\text{LWF}}_{2} = {\text{LWF}}_{1} + \gamma *\varphi_{{{\text{id}}}}$$

(9)

In case of E-GPSR and DVA-GPSR, the source vehicle calculated the LWF for all its neighbors. Then, the node that has the smaller value of the LWF will be chosen as a next hop. The DVA-GPSR is already simulated under a highway scenario and gives good results in terms of PDR, throughput and routing overhead [10].

3.3 DRL-GPSR

In DRL-GPSR (Direction-Route Lifetime aware GPSR), we use a new metric called route lifetime in addition to the angle direction metric to select the next-hop node. When a vehicle wants to send a packet to a destination node, it first calculates how long each of its neighbors could communicate with the current node, then compares the results and chooses the longer route lifetime; the current vehicle also needs to calculate the angle between its neighbors and the destination node and then chooses the smaller one.

The duration that two nodes will remain neighbors can be predicted as follows: Let two nodes i and j be within the transmission range of each other. Let (x_i, y_i) and (x_j, y_j) be the coordinates of the vehicles i and j, respectively. Let v_i and v_j be the velocities and φ_i and φ_j, where (0 ≤ φ_i, φ_j < 2π), indicate the direction of the vehicles i and j, respectively. RL_ij is the interval of time the two nodes j and i will stay connected. To calculate RL_ij, we use the following equation:

$${\text{RL}}_{{{\text{ij}}}} = \frac{{ - \left( {ab + cd} \right) + \sqrt {\left( {a^{2} + c^{2} } \right)r^{2} - \left( {ad - bc} \right)^{2} } }}{{a^{2} + c^{2} }}$$

(10)

where

a = v_i cos φ_i−v_j cos φ_j; b = x_i−x_j; c = v_i sin φ_i−v_j sin φ_j; and d = y_i−y_j.

At the last stage, we calculate the LWF for this strategy according to Eq. (11). We have calculated the route lifetime between the current node and its neighbors, and the angle direction between the destination and the neighbors of the current node.

$${\text{LWF}}_{3} = {{\alpha *1} \mathord{\left/ {\vphantom {{\alpha *1} {{\text{RL}}_{{{\text{ij}}}} + \beta *\varphi_{{{\text{id}}}} }}} \right. \kern-\nulldelimiterspace} {{\text{RL}}_{{{\text{ij}}}} + \beta *\varphi_{{{\text{id}}}} }}$$

(11)

where α + β = 1.

4 Simulation and Results Analysis

In the simulation, the NS3 and SUMO have been used as a network and traffic simulator. Moreover, the simulation was done based on a real map of Oujda city, taken from the Web site of Open Street Map. The simulation settings are presented in Table 1.

Table 1 Simulation parameters

4.1 PDR

Figure 1 shows the PDR of our proposed protocols by varying the density of vehicles. The DVA-GPSR and DRL-GPSR protocols show better performance than GPSR and have the highest value augmented up to 31.2% by increasing the number of vehicles. However, the E-GPSR and GPSR have the lowest values decreased down to 24%.

Fig. 1

Values of PDR by varying the number of nodes

4.2 Throughput

The graphs in Fig. 2 prove that our protocols have the best performance compared to the classical GPSR in terms of throughput by varying the density of vehicles in the route. Indeed, the throughput in case of DVA-GPSR and DRL-GPSR is increased up to 6.38 kbps thanks to the use of the mentioned factors in the previous section, which decrease the issue of connection loss so the lifetime of routes is increased.

Fig. 2

Throughput by varying the number of nodes

4.3 Routing Overhead

The graphs in Fig. 3 present the routing overhead for the proposed routing protocols compared to the classical GPSR. Indeed, the three new protocols prove better performance and generate low routing overhead than the traditional GPSR that achieves 29%.

Fig. 3

Routing overhead by varying the number of nodes

5 Conclusion

In this paper, we have suggested three innovative techniques to enhance the traditional GPSR protocol to be more suitable and convenient to vehicular networks. We have used SUMO and NS3 as traffic simulator and network simulator to demonstrate the quality of the proposed routing protocols, and we have used a real urban environment city that is a part of Oujda (street of El-Quds). The results of the simulation demonstrate that our protocols outperform the traditional GPSR protocol in terms of packet delivery ratio, the routing overhead and the throughput.

In E-GPSR, the strategy is based on three metrics: the distance between the target and the source vehicle, the density of the neighbors of the current vehicle that reduces the issues of void area and the speed variation between the target and the relaying candidate vehicle that reduces the effects of the high speed of vehicles that lead to the high dynamic topology and the connection damage problem. However, the connection could break quickly if two vehicles have the small variation speed with two different direction that prove the importance of including the direction in the second protocol.

In DVA-GPSR protocol, the problems caused by the frequent link breakage will be reduced compared to the standard GPSR and E-GPSR. Actually, in this protocol the angle direction metric is the new and the most important metric used for selecting a group of vehicles that move toward the target vehicle.

In DRL-GPSR, we use a new metric called route lifetime in addition to the angle direction metric to select the next-hop node. To conclude this paper and based on the discussion mentioned above, we confirm that the angle direction and the route lifetime parameters are the most important factors used to enhance the performance of the standard GPSR in urban environment in VANETs.

As a future work, we aim to simulate the three proposed strategies in other complicated urban scenarios and highway environment.