A Novel Next-Hop Selection Scheme Based on GPSR in VANETs

Abstract

Vehicle ad-hoc networks (VANETs) are becoming the mainstream of network research recently. However, due to the high mobility of vehicles, dynamically changing topology and highly partitioned network, it is a challenge to overcome these shortcomings to guarantee a reliable link and efficient data delivery. In this paper, we present an improved scheme for the selection of next-hop based on greedy perimeter stateless routing (GPSR). The routing decision zone based on the concept which combines node mobility with message forwarding direction is introduced to avoid the node selected as next hop driving away from the neighborhood of the forwarder during communication. Our proposed protocol adaptively sets the size of the routing decision zone in each hop based on the dynamic forward neighbor information, including speed and one-hop transmission delay, and then consequently selects the next hop based on the position information and the routing decision zone. Simulation results show that our algorithm with low-delay performance is effective in some cases.

1 Introduction

Vehicle ad-hoc networks (VANETs) have been proved for its great potential in various application especially enhancement of road safety, the optimization of traffic efficiency and the infotainment services. VANETs are a special type of Mobile ad-hoc networks (MANETs), which use vehicles as mobile nodes, transceivers and routers, including Vehicle-to-Vehicle (V2V) and Vehicle-to-Roadside (V2R) communication modes. However, VANETs have its own characteristics including the extremely dynamic topology, short-lived communication links, variable node density and highly partitioned network [1]. Therefore, it is very challenging to establish an optimal routing protocol in VANETs.

Among the MANETs routing protocols, the geographic routing protocol is now considered to be the most appropriate choice for VANETs [2]. The GPSR [3] protocol is a well-known position-based routing protocol in MANETs, which can minimize the end-to-end hop number and achieve faster data forwarding. GPSR adopts two position-based packet forwarding strategies, one is Greedy Forwarding (GF) and the other is Perimeter Forwarding (PF). In GF, a forwarding node selects its neighbor closest to the destination node as the next hop. If the forwarder encounters a void region, the PF is used to choose the next forward hop by flooding. GPSR protocol requires each node to know its own position through GPS and share it with its one-hop neighbors, besides this each node maintains the knowledge of its one-hop neighbors by periodically exchanging Hello packets.

When GPSR is applied to highway scene in VANETs, it does not perform well in vehicular environment. Since the GF only uses the stored position information to make the routing decision to select the next hop, it tends to select the next-hop node at the border of the communication range. As the node selected as next hop may leave the neighborhood of the forwarder due to its mobility, it has been found that it is prone to link interruption and significantly increases the packet loss rate. Furthermore, additional retransmissions lead to increased delay. Once the GF fails to forward the message, the PF is adopted as the recovery mode. Because of the dynamic topology and uneven distribution of nodes, it is very complicated to construct and traverse the planner graph in VANETs, and the node far away from the destination may be selected, resulting in an increase in delay.

Therefore, we propose an improved algorithm based on GPSR, which introduces the routing decision zone whose size can be calculated based on forward neighbor information of the forwarder along message forwarding direction, including maximum speed, minimum speed and one-hop transmission delay. Our proposed algorithm adaptively adjusts the size of the routing decision zone for each hop to adapt to mobility, and selects the next hop in the shrunk routing decision zone at the cost of communication overhead and hop count. In such network, although the selected hop may not be closer to the destination, it can avoid the selected node driving away from the neighborhood of the forwarder during communication, thereby reducing the packet loss rate and delay. In addition, our proposed algorithm adopts carry-forwarding scheme as the recovery mode instead of perimeter mode. The forwarder encountering a local optimal problem carries the packet until there is a neighbor node that could make a progress toward the destination.

2 Related Work

Several efficient techniques and approaches have been proposed in the literature to enhance the performance of GPSR in vehicular environments. WF-GPSR [4] protocol took into account link reliability, distance and movement direction angle to formulate the weighted function of a next-hop candidate node. DGF-ETX [5] protocol integrated the link quality estimation metric ETX into a multi-metric that considered the distance and direction of the candidate forwarders. DAPBR [6] protocol applied the restricted greedy forwarding approach to select the next hop by considering neighborhood vehicles having a sufficiently dense neighborhood and the least velocity variance compared to its own neighboring vehicles. LAT-GPSR [7] protocol introduced the link available time prediction into the next hop selection of GPSR, instead of simply using the GF algorithm. MAGF [8] protocol presented the concept of motion potential by combining node mobility patterns with node position information for forwarding decisions.

However, these aforementioned protocols required additional complex calculations to get the next hop after obtaining the relevant neighborhood information. To simplify the complexity of the next hop selection and improve the performance of GPSR, our proposed algorithm selects the next hop based on the position information and the routing decision zone, and obtains the corresponding information of the next hop directly from the Hello packet. Our proposed approach dynamically recalculates the size of the routing decision zone in each hop, overcoming the problem that the node selected as next hop may leave the neighborhood of the forwarder due to mobility. Furthermore, we adopt carry-forwarding as a recovery strategy.

3 Proposed Method

3.1 Network Scenario

We consider a pure V2V network scenario without any infrastructure in a straight unidirectional and uninterrupted one-way vehicle traffic highway, as shown in Fig. 1. The highway has one entrance and exit in the opposite direction. While sending a message from the source vehicle to the destination vehicle, a routing path needs to be established in a multi-hop manner.

Fig. 1.

Network scenario

Certain assumptions are made for our proposed algorithm, all vehicle nodes use $R$ as their effective communication range and are equipped with GPS for positioning. The destination node is known by default. The direction of the message forwarding is assumed to be the same as the direction in which the vehicle moves. It is assumed that each vehicle has independently assigned a random speed based on the Uniform distribution, and each vehicle maintains its randomly assigned speed while it is on the highway. Besides this, any vehicle $n_{i}$ can generate self-related information, including vehicle $ID_{i}$, speed $v_{i}$ and position coordinates $\left( {x_{i} ,y_{i} } \right)$.

We take the position of node $n_{i}$ as a reference, along the direction of vehicle movement, the one-hop neighbor in front of it is called the forward neighbor, contrarily termed as the backward neighbor. During message forwarding process, the forwarder usually makes routing decisions based on the forward neighbor information of each hop to achieve efficient and fast forwarding. $S.\;neighbour$ is used to distinguish between forward and backward neighbors as follows:

$$ S.\;neighbour = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {forward\;neighbour} \hfill \\ {0,} \hfill & {backward\;neighbour} \hfill \\ \end{array} } \right. $$

4 Algorithm Design

In this paper, the one-hop communication range along message forwarding direction is defined as the routing query zone, whereas the forward neighbor spatial distribution range of the auxiliary routing decision is defined as the routing decision zone, and the duration of a packet received from one node to another is defined as one-hop delay. The main purpose of the proposed algorithm is to select a relatively stable next hop by reducing the occurrence of the selected node moving out of the neighborhood of the forwarder, aiming to design a novel forwarding scheme for next hop selection in VANETs.

The idea of proposed algorithm is illustrated in Fig. 2. Where $n_{0}$ represents the number of forward neighbors, $n^{\prime}$ represents the number of vehicles located inside the boundary of communication range, depending on the number of lanes. In addition to that, $v_{f\_\hbox{max} }$ and $v_{f\_\hbox{min} }$ respectively represent the maximum speed and minimum speed of the forward neighbor node, and $t_{delay}$ is one-hop delay of the packet. $S.\;existence = 1$ indicates that the forward neighbor node exists in the routing decision zone, and the recovery mode basically adopts carry-forwarding mechanism.

Fig. 2.

Design idea of proposed algorithm

Firstly, an information query is initiated by the forwarding node at the beginning of each hop, and then one-hop neighbor list is established, and the routing decision zone is adaptively set based on forward neighborhood information, including $v_{f\_\hbox{max} }$, $v_{f\_\hbox{min} }$ and $t_{delay}$. Secondly, the next hop is selected in the routing decision zone. Thirdly, the packet forwarding process is performed on the selected next hop.

4.1 Implementation Steps of Proposed Algorithm

Getting 1-Hop Neighbor Information.

Every vehicle periodically sends a Hello packet to its neighboring vehicles, which carry following information such as position, vehicle ID, velocity of itself, and the timestamp attached to packet sending time. The purpose of the Hello packet is to get routing information of neighbor nodes, and its format is presented in Fig. 3.

Fig. 3.

The format of a packet

When the forwarder initiates an information query request, the $query$ packet is sent by the broadcast method within its communication range. The node that receives the $query$ packet for the first time sends a $reply$ packet to the forwarder, otherwise the $query$ packet is dropped. The format of the $query$ packet and the $reply$ packet have been shown in Fig. 3. Thus, the forwarder can establish a one-hop neighbor list based on these received $reply$ packets, and then get complete information about its one-hop neighbor nodes. The forwarder can extract information about the forward neighbor from the list, including $n_{0}$, $v_{f\_\hbox{max} }$, $v_{f\_\hbox{min} }$ and one-hop delay.

Setting the Size of the Routing Decision Zone.

In the GF scheme, the size of the routing query zone is the same as the size of the routing decision zone, as shown in Fig. 4(a). It is prone to select the boundary node as the next hop based on the expired routing information. The selected next hop is invalid if it satisfies the following two conditions: (1) After the boundary node successfully sends the $reply$ packet to the forwarder, it instantly moves out of the communication range of the forwarder. (2) When the forwarder sends a message to the selected next hop, the selected node moves outside the communication range of the forwarder during that period.

Fig. 4.

Comparison of two forwarding schemes

It can be noted that an invalid relay node can easily interrupt the communication link between the forwarder and the selected next hop, resulting in packet loss, which tends to increase delay due to its retransmission. To avoid selecting an invalid relay node, the forwarder should appropriately shrink the size of the routing decision zone in the routing query zone along the data forwarding direction, as shown in Fig. 4(b). Although selecting the next hop in the shrunk routing decision zone may increase the hop count, it can avoid the selected node moving away from the neighborhood of the current forwarder and greatly enhance the probability of receiving messages.

Moreover, if the size of the routing decision zone is set extensively large, once the selected relay node moves too fast, it may head out of the communication range of the forwarder during communication, and cannot efficiently ensure reliable message forwarding. Correspondingly, if the size of the routing decision zone is set extensively small, although the message can be reliably forwarded, it will result in an excessive increase in the number of hops, which may increase the probability of packet loss. Therefore, it is obligatory to dynamically set the size of the routing decision zone based on the dynamic forward information.

To reasonably set the size of the routing decision zone in each hop, we define a critical zone $r_{0}$ ($r_{0} \in \left[ {r_{\hbox{min} ,\;} r_{\hbox{max} } } \right]$) for the forwarding node at the edge of $R$, as shown in Fig. 4(b). From the instant when a node is selected as the next hop to the instant when the selected relay successfully receives the message, the selected relay node just arrives at the communication boundary of the forwarding node. In this section, we also investigated and calculated $r_{0}$ value, as shown below.

We assume that a forwarding node $n_{f}$ has a neighbor node $n_{x}$ moving to the communication boundary, and node $n_{f}$ and node $n_{x}$ happen to be in a critical connection state within $\Delta t$ time. In this case, node $n_{x}$ becomes the critical node, and the displacement that node $n_{x}$ covered at speed $v_{x}$ in $\Delta t$ time is taken as the critical value $r_{0}$, and $r_{0} = \Delta t \cdot v_{x}$. The time when node $n_{x}$ receives the $query$ packet from node $n_{f}$ is denoted as $t_{1}$, and the time when node $n_{x}$ receives the message from node $n_{f}$ is denoted as $t_{2}$. Therefore, we get $\Delta t = t_{2} - t_{1}$.

The duration from node $n_{x}$ receiving the $query$ packet to node $n_{f}$ receiving the $reply$ packet is the one-hop delay of the reply, which is denoted as $t_{one - hop\_reply}$. Node $n_{f}$ receives the $reply$ packet from node $n_{x}$, and then node $n_{f}$ sends a message to node $n_{x}$ until node $n_{x}$ receives the message from node $n_{f}$. The duration of the process is called the one-hop delay of the message, which is denoted as $t_{{one - hop\_\text{message}}}$.

Based on the above analysis, we obtain:

$$ \begin{array}{*{20}l} {\Delta t = t_{2} - t_{1} } \hfill \\ {\;\;\;\; = t_{one - hop\_reply} + t_{{one - hop\_\text{message}}} } \hfill \\ \end{array} $$

(1)

Then:

$$ r_{0} = \Delta t \cdot v_{x} = \left( {t_{one - hop\_reply} + t_{{one - hop\_\text{message}}} } \right) \cdot v_{x} ,\;v_{x} \in \left[ {v_{f\_\hbox{max} } ,\;v_{f\_\hbox{min} } } \right] $$

(2)

When $v_{x} = v_{f\_\hbox{max} }$, $r_{\hbox{max} } = \left( {t_{one - hop\_reply} + t_{{one - hop\_\text{message}}} } \right) \cdot v_{f\_\hbox{max} }$

When $v_{x} = v_{f\_\hbox{min} }$, $r_{\hbox{min} } = \left( {t_{one - hop\_reply} + t_{{one - hop\_\text{message}}} } \right) \cdot v_{f\_\hbox{min} }$

We can get the range of the size of the routing decision zone $\left( {R - r_{0} } \right)$ as follows:

$$ \left( {R - r_{0} } \right)_{\hbox{max} } = R - r_{\hbox{min} } $$

(3)

$$ \left( {R - r_{0} } \right)_{\hbox{min} } = R - r_{\hbox{max} } $$

(4)

In each hop, the size of the routing decision zone is adaptively estimated as follows:

$$ R - r_{0} = \left( {R - r_{0} } \right)_{\hbox{min} } + \left( {1 - \beta } \right) \cdot \left[ {\left( {R - r_{0} } \right)_{\hbox{max} } - \left( {R - r_{0} } \right)_{\hbox{min} } } \right] $$

(5)

Where the value of $\beta$ determines the size of the routing decision zone. If the value is 0, $\left( {R - r_{0} } \right)$ will be $\left( {R - r_{0} } \right)_{\hbox{max} }$. If the value is 1, $\left( {R - r_{0} } \right)$ will be $\left( {R - r_{0} } \right)_{\hbox{min} }$. However, when all vehicles on this segment make a uniform linear at the same speed $v_{x}$, we can get $\left( {R - r_{0} } \right)_{\hbox{max} } = \left( {R - r_{0} } \right)_{\hbox{min} }$. Thus, the size of the routing decision zone is as follows:

$$ R - r_{0} = R - \Delta t \cdot v_{x} $$

(6)

After determining the size of the routing decision zone, and making a reasonable trade-off between the communication overhead and the hop count, the forwarder selects the node closest to the destination as the next hop in the shrunk routing decision zone based on the position information, which can avoid the selected node driving away from the communication range of the forwarder during communication. If the forwarder cannot find a node closer to the destination than itself, it carries the packet until it encounters a neighbor node that may be heading towards the destination. Then repeat the process until the message is successfully forwarded to the destination node.

5 Analysis and Simulation Results

In this paper, we use MATLAB R2014a as a simulation platform to evaluate the performance of our proposed algorithm. We compare the performance of our proposed protocol with the GPSR in the same simulation environment. The setting of the simulation scenario is described in Table 1. Furthermore, we set $\beta$ as 0.5, one hop delay as 0.1 s, and here we ignore the delay of electromagnetic wave propagation in the air. However, variations in vehicle speed results in frequent link changes and error-prone transmissions, which may increase delay. To analyze the impact of vehicle speed on the end-to-end delay, we assume all vehicles on this segment make a uniform linear at the same speed, and the number of vehicles is set to moderately 55.

Table 1. Parameter setting in simulations

The simulation results in Fig. 5 depict that the delay of our proposed algorithm remains relatively stable, while the delay of GPSR increases with the increase of vehicle density. However, the increase in vehicular density ultimately increases the chance of packet collisions, and GPSR has a higher probability to select an invalid relay, which may result in an increase in packet loss and delay. Furthermore the proposed algorithm selects the next hop in the shrunk routing decision zone can avoid selection of an invalid relay as much as possible, hence the average delay is expected to reduce compared to GPSR. When the vehicle density is small, the forwarder in the proposed algorithm cannot find any node as the next hop to deliver data packet in the shrunk routing decision zone, which will result in much bigger delay. Therefore, the average end-to-end delay of our proposed algorithm is better than GPSR in a relatively dense vehicle scene.

Fig. 5.

Impact of the number of vehicles on the average end-to-end delay.

The simulation results in Fig. 6 show that the delay of our proposed algorithm is smaller than GPSR. On one hand, the increase of vehicle speed increases the probability of occurrence of the void region, which may increase the average delay. On the other hand, with the increase of vehicle speed, the next-hop selected in GPSR has a higher probability of leaving the communication range of the forwarder because of its high speed, thus it certainly increases chances of packet loss and extra delay of retransmissions. The proposed algorithm selects the next hop in the shrunk routing decision zone, which can reduce the probability of occurrence of this phenomenon. However, the proposed algorithm sacrifices the hop-count as a compromise to gain stable links, and the delay increases with the increase of vehicle speed.

Fig. 6.

Impact of vehicle speed on the average end-to-end delay

6 Conclusion

In this paper, a novel next-hop selection scheme based on GPSR is proposed, which adaptively sets the size of the routing decision zone based on the information of the dynamic forward neighbor in each hop, including speed and one-hop delay. Then, we consider position information and the routing decision zone to select the next hop, which reduces the chance of the selected node moving out of the effective communication range of the forwarder during communication. Simulation results indicate that the performance of our proposed protocol performs better than GPSR in some cases.