An Adaptive Routing Protocol Based on QoS and Vehicular Density in Urban VANETs

Abstract

Multihop data delivery between vehicles is an important technique to support the implementation of vehicular ad hoc networks (VANETs). However, many inherent characteristics of VANETs (e.g., dynamic network topology) bring great challenges to the data delivery. In particular, dynamic topology and intermittent connectivity make it difficult to design an efficient and stable geographic routing protocol for different applications of VANETs. To solve this problem, the paper proposes an adaptive routing protocol based on QoS and vehicular density (ARP-QD) in urban VANETs environments. The basic idea is to find the best path for end-to-end data delivery, which can satisfy diverse QoS requirements by considering hop count and link duration simultaneously. To reduce the network overhead furthermore, ARP-QD adopts an adaptive neighbor discovery algorithm to obtain neighbors’ information based on local vehicular density. In addition, a recovery strategy with carry-and-forward is utilized when the routing path is disrupted. Numerical simulations show that the proposed ARP-QD has higher delivery ratio than two prominent routing protocols in VANETs, without giving large compromise on delivery delay. The adaptivity of ARP-QD is also analyzed.

1. Introduction

With the development of wireless technologies and dedicated short-range communication technologies, vehicular ad hoc networks (VANETs) have been paid increasing attention [1]. In vehicular settings, the availability of navigation system, global positioning system (GPS), and other sensors that can perceive the vehicle speed, location, and other useful information makes it possible to exploit many applications, such as intelligent transportation system (ITS) applications and infotainment applications [2, 3]. ITS applications include cooperative traffic monitoring, traffic control, blind crossing, collision prevention, nearby information services, and real-time detour route computation [4], which have attracted attention from many car manufacturers, research institutes, and national transportation departments. Vehicle communications [5, 6] are the basic foundation of the above applications of VANETs.

Unfortunately, the traditional wireless technologies cannot be applied for VANETs directly, since they have some inherent characteristics, such as dynamic radio environments and frequent topology changes, which cause the network disconnection from time to time. Due to high speeds of vehicular movements, link duration between two vehicles is hard to keep stable for a period of time. As communication relays or information broadcasters, the equipment of road-side-units (RSUs) can help improve the vehicle communications. However, the RSUs usually have high costs. Therefore, the dynamic network topology is the most critical issue in VANETs. In particular, it brings significant challenges for designing an efficient and stable geographic routing protocol.

The existing routing protocols lack the friendly adaptation to diverse QoS requirements of different applications. The objectives of the current routing protocols focus on either the fastest path with the minimum hop count or the most stable path with the longest link duration or connectivity but neglect the adaptive balance of the routing protocol with consideration of path efficiency and path stability. In this paper, we propose an adaptive routing protocol based on QoS and vehicular density (ARP-QD) over urban VANETs. It balances the path efficiency and path stability by an optimal forwarding algorithm and an adaptive neighbor discovery algorithm with friendly adaptation to different QoS requirements and urban VANETs environments. The main intellectual contributions of this paper are summarized as follows.

• (1)

For describing the dynamic link quality in VANETs, we define two new metrics, named product of connectivity and distance (CDP) and segment selection weight (SSW), by considering the hop count and link duration simultaneously.

(2)

We present an optimal forwarding algorithm based on CDP and SSW, which can obtain a qualified path to satisfy the diverse QoS requirements of different applications by balancing the path efficiency and path stability. As an essential part, a quick recovery strategy with carry-and-forward is also provided when the routing path is disrupted.

(3)

To reduce the network overhead and improve resource usage, we propose an adaptive neighbor discovery algorithm to obtain the neighbors’ information based on local vehicular density.

(4)

The extensive simulation results show that the proposed ARP-QD has higher delivery ratio than two prominent routing protocols in VANETs, without giving large compromise on the delivery delay. The adaptivity of ARP-QD is also analyzed.

The remainder of the paper is organized as follows. Section 2 briefly reviews related routing mechanisms proposed in VANETs and details the motivation of this paper. In Section 3, we design two metrics combining hop count and link duration for forwarding optimization. The adaptive neighbor discovery algorithm is also presented as well as the recovery strategy to improve the robustness of ARP-QD. Numerical simulations and the results are analyzed in Section 4. We conclude the paper and list some possible future works in Section 5.

2. Related Works

Generally, path efficiency and path stability are two important criterions in designing routing protocol for VANETs. To achieve high efficiency, the shortest (generally fastest) path with minimum hop count is usually selected as the best path. To pursue high stability, the path with the longest duration is considered as the best candidate. However, most of existing researches focus on either efficiency or stability. We review related works in both directions as follows.

Path Efficiency. One objective of a routing protocol in VANETs is to find an efficient (or a fast) path with the shortest number of hops for data delivery [5, 7–10]. Greedy Perimeter Stateless Routing (GPSR) algorithm uses the positions of routers and a packet's destination to make packet forwarding decisions [7]. It chooses the nearest node to the destination as the next hop within communication range, which will increase the link loss because of high mobility and radio obstacles. Like GPSR, Geographic Source Routing (GSR) [8] is also a position based routing protocol. The weakness of GSR is not flexible to the sparse network, since GSR works on the foundation of end-to-end connectivity. Another similar method of GPSR is Greedy Perimeter Coordinator Routing (GPCR) [9], which assigns the routing decision to the nodes located at the street intersections and uses the greedy forwarding strategy to route the packet path between the street intersections. However, GPCR does not take the link connectivity into consideration to select the best path. An improved Greedy Traffic Aware Routing Protocol (GyTAR) has been presented in [5], which is based on the geographical intersection information to find robust and optimal routes within urban environments. In [10], a two-stage routing algorithm has been presented to find out the practically fastest route to a destination at a given departure time in terms of taxi drivers’ intelligence learned from a large number of historical taxi trajectories.

In short, most of the above researches regard the shortest path, but fail to concern the diverse QoS requirements of different applications. Some applications require more stable path for high delivery ratio, while the link connectivity between the current and farthest neighbor node is always most vulnerable, which may cause shorter link duration than other links. Hence, the above protocols are not suitable for applications which require high delivery ratio.

Path Stability. One of the simple but efficient methods to improve the path stability is to find the next hop with the longest link duration (or the most stable connectivity) [11–15]. A Receive On Most Stable Group-Path (ROMSGP) scheme [11] has been designed to choose the most stable path with the longest link expiration time. However, ROMSGP only broadcasts specific and well-defined packets, which will result in the loss of other packets. The goal of [12, 13] is to find the routing path with the least probability of network disconnection and avoid carry-and-forward delay. However, the links with good connectivity usually have short distance, which makes the selected paths include more hops and therefore brings longer delivery delay. A stable VANETs routing protocol [14] has been proposed to provide fast and reliable message delivery based on the real-time road vehicular density. However, the real-time update of density information incurs a large number of communication overheads, which results in its performance deterioration with the augment of network scale. An intersection-based geographical routing protocol has been proposed in [15], which aims to find the path with high connectivity probability and other QoS constraints.

In a word, all aforementioned researches mainly focus on the link connectivity and make less use of the geographical distance information among vehicles, such that the selected paths may have unnecessary loops, which causes longer delivery delay. Thus, the above protocols are not suitable for the applications which require low delivery delay.

Some researches, like [16, 17], take the link state and hop count into account. In [16], the authors have presented an Optimized Link State Routing (OLSR) algorithm to provide optimal routes. However, the link state is only used to obtain the neighbors’ information and OLSR provides the path with minimum hop count as the best path. Moreover, OLSR is a topology-based routing algorithm, which consumes a large amount of topology control messages. To improve GPSR, [17] uses the vehicle speed and position to find relatively stable links, which is based on the forecast of the speed fluctuations. However, the above works failed to adaptively trade off the path efficiency and path stability for diverse QoS requirements in different scenarios and could not achieve the purpose of friendly communications.

To the best of our knowledge, there is no prior work that has thoroughly researched the adaptive routing protocol which can balance the path efficiency and stability based on diverse QoS requirements of different applications. In this paper, based on the information of intersection location, vehicle speed, and position, we take the hop count and link duration into consideration and propose a novel optimal forwarding algorithm to trade off the path efficiency and stability with friendly adaptation to different QoS requirements of applications. Furthermore, we present an adaptive neighbor discovery algorithm, which exploits different ways to acquire the neighbors’ information according to the local vehicular density. Based on the above two main algorithms, we build the adaptive routing protocol based on QoS and vehicular density (ARP-QD), which has higher delivery ratio and reasonable delivery delay.

3. The Proposed Adaptive Routing Protocol (ARP-QD)

In this section, we first introduce the system model used for urban VANETs. Then we present the optimal forwarding algorithm which adaptively balances the path efficiency and stability based on QoS requirements, as well as the adaptive neighbor discovery algorithm based on the real-time vehicular density. To improve the robustness of ARP-QD, the recovery strategy with carry-and-forward is adopted when the routing path is disrupted. Finally, an example is given to illustrate how the proposed ARP-QD works.

3.1. System Model

As shown in Figure 1, we consider a VANET road environment with intersections and segments within two intersections, which is a typical scenario in urban areas. The circle with the intersection ID inside denotes the intersection. $\overrightarrow{v}$ and $\overrightarrow{p}$ indicate the moving directions of the vehicle and the packet, respectively. The yellow arrow means the moving direction of vehicles on that road segment. The purple arrow with a right angle denotes the candidate path of the packet from the source node S to the destination D. Vehicles move through the segments in the same or opposite direction, while, when moving into the intersection, they will find their neighbors moving in various directions.

Figure 1

System illustration (S: the source node; D: the destination).

Since the RSUs are costly, the paper focuses on the routing protocol for vehicle-to-vehicle (V2V) communications without RSUs. We assume that all vehicles are equipped with onboard navigation system and wireless communication capability as described in [18]. Each vehicle has a digital street map of the area using the onboard navigation system to determine the positions of its neighboring intersections. Meanwhile, it can acquire a landscape of the road environment, including the vehicular velocity and density on each road. The above information can be obtained through the commercialized applications [19]. Furthermore, through the periodic information exchange, each vehicle knows its neighbors’ information including the positions and velocities, which is maintained in its neighbor table. For easy illustration, we assume that all vehicles have the same transmission range. In addition, the location service can make the source node have the knowledge of destination position in real time. The above assumptions are the same as the previous works [4, 20, 21].

3.2. Optimal Forwarding Algorithm

As mentioned above, the real road environment contains two parts: intersections and segments within two intersections. Many vehicles, which are regarded as mobile nodes, move along the road as shown in Figure 1. We aim to find the best path hop by hop from the source node S which creates the packets to the destination D. D can be the nearest Internet gateway or data collection center. Thus, we assume the destinations are always located in the intersections. The proposed ARP-QD is a geographic routing protocol including optimal forwarding decision, adaptive neighbor discovery, and robust route recovery. It selects the whole path hop by hop from S to D, and each sender decides its next hop locally. It is easy to observe that a node traveling in the segment or intersection should use different tactics to calculate the metric to choose the next hop. For a node in the segment, it only chooses its next hop in the parallel directions, while for a node in the intersection it should first choose the next segment and then decide the next hop within the selected segment. Therefore, we define a new metric, that is, product of connectivity and distance (CDP), in two cases, respectively.

3.2.1. Metric Design in the Segment Case

Two seemingly contradictory, yet related, objectives of routing performance exist: improving the path efficiency with less hop count and improving the path stability with longer link duration. In general, the longer the link distance is, the smaller the hop count is. In contrast, the shorter the link distance is, the more stable the link is. We aim to design a novel metric for selecting the best next hop on the road segment, which can balance the requirements of the path efficiency and stability. We first consider the one lane case and later show that the case of multiple lanes has the same result. In the one-lane case, we just consider that all vehicles drive in the same direction, and the result in the opposite direction can be easily induced in the same way. To formally design the metric, that is, CDP, the notations used in the following analysis are described in Notations.

We regard a neighbor node n with $\text{P}{\text{L}}_n<\text{P}{\text{L}}_s$ as a candidate neighbor. Note that the path length means the distance along the selected roads.

First, we discuss the case of one lane. As depicted in Figure 2(a), we can obtain

$$\begin{array}{cc}& R_n+L_n=R.\end{array}$$

(1)

Since $\text{P}{\text{L}}_n<\text{P}{\text{L}}_s$ ,

$$\begin{array}{cc}& R_n=\text{P}{\text{L}}_s-\text{P}{\text{L}}_n>\mathrm{0}.\end{array}$$

(2)

It can be observed that the neighbor node n, which is closest to the destination, has the largest $R_n$ .

Figure 2

Road segment illustration.

We define $T_n$ in (3) to denote the link connection duration time between candidate neighbor node n and the sender s:

$$\begin{array}{cc}& T_n=\left\{\begin{array}{cc}\frac{L_n}{\left(v_n-v_s\right)},\hfill & v_n>v_s,\hfill \\ K,\hfill & v_n=v_s,\hfill \\ \frac{\left(\mathrm{2}R-L_n\right)}{\left(v_s-v_n\right)},\hfill & v_n<v_s,\hfill \end{array}\right.\end{array}$$

(3)

where K is a default constant set by the VANETs system. In order to improve the path efficiency and stability, we prefer to choose the neighbor node with the largest product of $T_n$ and $R_n$ as the next hop. Hence, the basic CDP of a neighbor node n is defined as

$$\begin{array}{cc}& \text{CD}{\text{P}}_n^b=R_n{T}_n=\left\{\begin{array}{cc}\frac{R_n{L}_n}{\left(v_n-v_s\right)},\hfill & v_n>v_s,\hfill \\ R_{n}K,\hfill & v_n=v_s,\hfill \\ \frac{R_n\left(\mathrm{2}R-L_n\right)}{\left(v_s-v_n\right)},\hfill & v_n<v_s.\hfill \end{array}\right.\end{array}$$

(4)

As we can see, the CDP value depends on the relative speed and distance between the sender s and candidate neighbor node n. Indeed, for a given lane with some nodes, the CDP function combines the factors of the distance from n to s and the link connection duration. Since larger $R_n$ means less hop count and larger $T_n$ means longer link duration, larger CDP is preferred. The node with the largest CDP among the candidates is selected to be the next hop. Figure 2(a) shows an example of vehicles driving on one lane. In this scenario, once the sender s obtains the information of neighbors’ positions and velocities, it computes the CDP value of each neighboring vehicle. Considering its path length to the destination and the link duration with s, neighboring vehicle 1 (i.e., node 1) is assumed to get the maximum value of CDP. It is then chosen as the next hop. Note that if there are multiple neighbor nodes with the same largest CDP, s will randomly pick up one as the next hop.

Then, we will discuss the case of multiple lanes as depicted in Figure 2(b). The relation is changed as shown in the following:

$$\begin{array}{cc}& Q_n+L_n=\sqrt{R^{\mathrm{2}}-{\left(kl\right)}^{\mathrm{2}}}.\end{array}$$

(5)

Here it is assumed that a sender s drives in lane $\mathrm{2}$ and the candidate neighbor node n drives in lane $k+\mathrm{2}$ , where k indicates the number of interval lanes. Although transmission range R is more than 100 m, l is usually less than 3 m. We can get $Q_n\approx R_n$ and $\sqrt{R^{\mathrm{2}}-(kl{)}^{\mathrm{2}}}\approx R$ . Consequently, (5) can be simplified to

$$\begin{array}{cc}& R_n+L_n\approx R.\end{array}$$

(6)

No matter where the vehicles drive in one lane or multiple lanes, their basic CDP can be calculated by (4).

Next, we modify the definition of CDP to satisfy diverse QoS requirements of different applications. In this paper, two prominent QoS requirements, that is, delivery delay and delivery ratio, are considered. For real-time applications such as video on demand, which require high priority on delivery delay, they need to find the efficient path with minimum hop count, while, for other applications such as file transmissions, which require the reliable transmission with high delivery ratio, they need to find the stable path with longest link duration. We use adaptive factors α and β to represent diverse QoS requirements of different applications, where α implies the priority weight of hop count, while β means the importance of link duration under the condition of $\alpha +\beta =\mathrm{1}$ . To friendly adapt to diverse QoS requirements of different applications, α and β will be set according to the application requirements on delivery delay and delivery ratio. It is easily obtained that the larger α makes higher priority on delivery delay, which requires finding a path with smaller hop count. Therefore, the advanced CDP is defined as

$$\begin{array}{cc}& \text{CD}{\text{P}}_n^a=R_n^{\alpha }{T}_n^{\beta }=\left\{\begin{array}{cc}{R}_n^{\alpha }·{\left(\frac{L_n}{\left(v_n-v_s\right)}\right)}^{\beta },\hfill & v_n>v_s,\hfill \\ R_n^{\alpha }{K}^{\beta },\hfill & v_n=v_s,\hfill \\ R_n^{\alpha }·{\left(\frac{\left(\mathrm{2}R-L_n\right)}{\left(v_s-v_n\right)}\right)}^{\beta },\hfill & v_n<v_s.\hfill \end{array}\right.\end{array}$$

(7)

From (1) and (7), we can obtain an optimal value of $\text{CD}{\text{P}}_n^a$ among different neighbors.

ARP-QD will select the one with the maximum $\text{CD}{\text{P}}_n^a$ among all candidate neighbor nodes as the best next hop. In conclusion, using the metric $\text{CD}{\text{P}}_n^a$ defined in (7), ARP-QD can friendly adapt to diverse QoS requirements when packets are delivered on the segment areas.

3.2.2. Metric Design in the Intersection Case

This part discusses how to design a new metric expression for the best next hop selection in the intersection by taking hop count and link duration into consideration. There are two stages for the sender in the intersection to choose the best next hop. First, the sender needs to choose which segment the packet will be delivered. Then, based on the selected segment, the sender computes the best next hop located in that segment.

Segment Selection. Obviously, the segment selection for a sender in the intersection is to find the best next intersection. Candidate intersections are defined as the adjacent intersections whose path lengths are shorter than the current intersection. The mobile vehicles moving along the roads are formalized to form a mobile ad hoc vehicular network. To find an efficient routing path, we prefer to choose the connected one. The reason is that the disconnection brings in the vehicle carrying the packet until it connects to another vehicle, but the vehicle's moving speed is significantly slower than that of wireless communications. Thus, we aim to find the next intersection which is connected to the current intersection through these mobile nodes. We define a binary parameter, named $U_j$ , to indicate the connectivity of intersection j. $U_j=\mathrm{1}$ means that the intersection j is connected with the current intersection. Otherwise, $U_j=\mathrm{0}$ . The formal expression can be illustrated as follows:

$$\begin{array}{cc}& U_j=\left\{\begin{array}{cc}\mathrm{1},\hfill & j\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{can}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{be}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{connected},\hfill \\ \mathrm{0},\hfill & j\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{cannot}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{be}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{connected}.\hfill \end{array}\right.\end{array}$$

(8)

With the precondition of intersection connectivity, we aim to combine the hop count and link duration time into the metric design. On the one hand, we want to choose the path with the shortest path length, which means minimum hop count. On the other hand, in order to choose the next hop with long link duration, we tend to choose the neighbors in the same moving direction as the sender. Hence we prefer to select the segment with smaller θ, which is the angle between candidate segment and movement direction of the current sender. Based on the above analysis, we define a metric, named segment selection weight (SSW), to select the best next intersection. The SSW of the intersection j is

$$\begin{array}{cc}& \text{SS}{\text{W}}_j=\alpha \frac{\text{P}{\text{L}}_{sj}}{\text{PL}}+\beta \frac{(\mathrm{1}-\cos \theta )}{\mathrm{2}}+\left[\mathrm{1}-U_j\right],\end{array}$$

(9)

where $\text{P}{\text{L}}_{sj}$ indicates the path length of packet delivery from the sender s to the destination through the intersection j. $\text{PL}$ is the summed length of paths through all candidate intersections, formally shown as $\text{PL}=\sum ‍\text{P}{\text{L}}_{sj}$ , where j represents the ID of candidate intersections. $\text{P}{\text{L}}_{sj}$ is divided by $\text{PL}$ for normalization. For the sender in a given intersection, $\text{PL}$ is fixed and the path with smaller $\text{P}{\text{L}}_{sj}$ is preferred. In order to satisfy diverse QoS requirements of different applications, we also use the adaptive factors α and β to represent the weight of hop count and link duration, respectively, in (9). ARP-QD will select the one with the minimum SSW among all candidate intersections as the best next intersection.

Next Hop Selection. Once the next segment is selected, the direction of packet delivery is determined. In the following we give the process to select the next hop among the selected segments, which can be classified into two cases.

• (1)

$\theta =\mathrm{0}$ : in this case, the sender's moving direction is the same as the next hop's. Hence, we can use the same method to select the best next hop as that used in the segment case.

(2)

$\theta \ne \mathrm{0}$ : in this case, $R_n+L_n\ne R$ . We need to obtain new CDP equations. As shown in Figure 3, we assume that both the sender s and the candidate neighbor node n are moving in constant speed, which are noted as $v_s$ and $v_n$ , respectively. Using the cosine law, we can obtain the equation as follows:

$$\begin{array}{cc}& R^{\mathrm{2}}={\left(R_n+v_n{T}_n\right)}^{\mathrm{2}}+{\left(v_s{T}_n\right)}^{\mathrm{2}}-\mathrm{2}{v}_s{T}_n\left(R_n+v_n{T}_n\right)\cos \theta .\end{array}$$

(10)

Figure 3

Intersections illustration.

From (10), we can compute $T_n$ as follows:

$$\begin{array}{l}{T}_n=\frac{R_n(v_s\cos \theta -v_n)}{v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta }\\ \hspace{1em}+\frac{\sqrt{R^{\mathrm{2}}\left(v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta \right)-R_n^{\mathrm{2}}{v}_s^{\mathrm{2}}{\sin }^{\mathrm{2}}\theta }}{v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta },\end{array}$$

(11)

where $R_n$ is the Euclidean distance from the sender s to its candidate neighbor n and θ is the angle between candidate segment and movement direction of the current sender. Hence, the basic CDP is defined as

$$\begin{array}{l}\text{CD}{\text{P}}_n^b=R_n\\ \hspace{1em}·\left(\frac{R_n(v_s\cos \theta -v_n)}{v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta }\phantom{\frac{\sqrt{R^{\mathrm{2}}(v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta )-R_n^{\mathrm{2}}{v}_s^{\mathrm{2}}{\sin }^{\mathrm{2}}\theta }}{v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta }}\right.\\ \phantom{ppppp}\left.+\frac{\sqrt{R^{\mathrm{2}}\left(v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta \right)-R_n^{\mathrm{2}}{v}_s^{\mathrm{2}}{\sin }^{\mathrm{2}}\theta }}{v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta }\right).\end{array}$$

(12)

Accordingly, the advanced CDP is obtained as

$$\begin{array}{l}\text{CD}{\text{P}}_n^a=R_n^{\alpha }\\ \hspace{1em}·\left(\frac{R_n(v_s\cos \theta -v_n)}{v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta }\phantom{\frac{\sqrt{R^{\mathrm{2}}(v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta )-R_n^{\mathrm{2}}{v}_s^{\mathrm{2}}{\sin }^{\mathrm{2}}\theta }}{v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta }}\right.\\ \phantom{ppppp}{\left.+\frac{\sqrt{R^{\mathrm{2}}\left(v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta \right)-R_n^{\mathrm{2}}{v}_s^{\mathrm{2}}{\sin }^{\mathrm{2}}\theta }}{v_n^{\mathrm{2}}+v_s^{\mathrm{2}}-\mathrm{2}{v}_n{v}_s\cos \theta }\right)}^{\beta }.\end{array}$$

(13)

The sender s chooses its candidate neighbor with the maximum $\text{CD}{\text{P}}_n^a$ in (13) as the best next hop, which is located in the selected segment.

3.2.3. Optimal Forwarding Algorithm

In this part, we present a novel optimal forwarding algorithm, as described in Algorithm 1, to choose the best next hop for multihop packet delivery. The best next hop is selected from the sender's neighbor list, which is obtained by neighbor discovery algorithm (described in Section 3.3). Note that neighbor list contains the information of neighbors’ IDs and $\text{CD}{\text{P}}_n^a$ values, while neighbor table is composed of neighbors’ IDs, velocities, and positions. Each $\text{CD}{\text{P}}_n^a$ value in the neighbor list is computed by (7) or (13) using the information in the neighbor table. As mentioned above, there are two cases to analyze the next hop selection. On the one hand, when the sender s is moving along a road segment, it will choose the candidate neighbor with the maximum $\text{CD}{\text{P}}_n^a$ value, from its neighbor list, as the best next hop. On the other hand, when s approaches an intersection, it needs to firstly find the best next intersection with the minimum SSW and then choose the best next hop located in the selected segment.

Algorithm 1: The optimal forwarding algorithm.

Input: The information of sender s and destination D

Output: The next hop of the delivered packet

(1) if  s approaches the intersection then

(2)  Broadcast a beacon packet with CP_REQ to each candidate intersection and active the Time 1 (expired time).

(3)  repeat

(4)   Receive responding packets with CP_REP and neighbors' information

(5)  until Timer 1 expires

(6)  if  s receives a responding packet with CP_REP and neighbor's information from intersection j  then

(7)    $$U_j=\mathit{1}$$ .

(8)  else

(9)    $$U_j=\mathit{0}$$

(10)     Compute SSW of each candidate intersection.

(11)      Select the next intersection with the minimum SSW.

(12)     Select the next hop with the maximum $$\text{CD}{\text{P}}_n^a$$ based on (7) or (13).

(13) else

(14)     Choose the next hop with the maximum $$\text{CD}{\text{P}}_n^a$$ according to (7).

To find the best next intersection (or segment), s needs to get the information of which intersection is connected with the current intersection. Hence, s broadcasts a beacon packet, which contains a connectivity probe request ( $\text{CP}\_\text{REQ}$ ) and its own information as shown in Figure 4. $\text{CP}\_\text{REQ}$ includes the current intersection ID, source and destination of the data, request time, and expired time. It is used to probe the connectivity of each candidate intersection, which is indicated by $U_j$ . If a candidate intersection j is connected to the current intersection by mobile nodes (i.e., vehicles) moving between the current intersection and candidate intersection j, the sender s will receive a responding packet from its neighbor node before the expired time; then $U_j=1$ ; otherwise $U_j=0$ . The responding packet contains a connectivity probe reply ( $\text{CP}\_\text{REP}$ ) and neighbor's information as shown in Figure 4. $\text{CP}\_\text{REP}$ includes the candidate intersection ID, source and destination of the data, reply time, and expired time. Neighbor's information includes its ID, velocity, and position used for calculation of SSW and $\text{CD}{\text{P}}_n^a$ . The beacon will be dropped if the expired time is over. Based on the received responding packets, s calculates values of SSW according to (9) for all candidate intersections and then picks out the candidate intersection with the minimum SSW as the next intersection. Thus, the next delivery segment is selected accordingly. Finally, to find the best next hop, s chooses the candidate neighbor with the maximum $\text{CD}{\text{P}}_n^a$ value as the best next hop from its neighbor list.

Figure 4

Packet format.

3.3. Adaptive Neighbor Discovery Algorithm

The neighbor list of each node is updated at fixed intervals to keep neighbors’ information in real time, which is the precondition of the optimal forwarding algorithm. Vehicular density has a tremendous impact on the network performance, and high density incurs serious congestions during the update process of neighbors’ information. In other words, heavy periodic beacons for neighbor discovery will decrease the average throughput of network, which causes negative influence on the end-to-end data delivery. In this section, we aim to design an adaptive neighbor discovery algorithm based on the vehicular density to obtain the neighbor list.

The proposed neighbor discovery algorithm can adaptively reduce the communication overhead according to the local vehicular density, which is defined as the number of nodes in transmission range of node i, denoted as $d_l$ . We set a density threshold $d_{\text{th}}$ to evaluate the local vehicular density $d_l$ . The basic principle of the adaptive neighbor discovery algorithm is to choose a centralized way to discover neighbors and update neighbor list when $d_l$ is lower than $d_{\text{th}}$ , while using a distributed fashion on the opposite. The detailed process of neighbor discovery is illustrated in Algorithm 2.

Algorithm 2: The adaptive neighbor discovery algorithm.

Input: The local vehicular density $$d_l$$ of node i, the vehicular density threshold $$d_{\text{th}}$$

Output: The neighbor list of node i

(1) if   $$d_l<d_{\text{th}}$$   then

(2)  Use the centralized way to obtain the neighbor list of node i based on $$\text{CD}{\text{P}}_n^a$$ .

(3) else

(4)  Use the distributed way to obtain the neighbor list of node i based on $$\text{CD}{\text{P}}_n^a$$ .

In the centralized way, node i first broadcasts a start beacon to request all neighbors’ information. Next each neighbor answers to the beacon with the information of its own position and velocity. Based on the neighbors’ information of positions and velocities, node i can compute $\text{CD}{\text{P}}_n^a$ value of each neighbor n by (7) or (13). Thus the neighbor table and neighbor list of node i are updated. The optimal forwarding algorithm will select the best next hop from this neighbor list, as mentioned in Section 3.2. Since the destination of all neighbors’ answers is node i, they adopt distributed coordination function in IEEE 802.11 to avoid the transmission collision. Request to send (RTS) and clear to send (CTS) control frames are used to reserve channel bandwidth and to minimize the amount of wasted bandwidth when collision occurs [22]. Since $d_l$ is lower than $d_{\text{th}}$ , such a centralized way for neighbor discovery will not result in heavy communication overheads.

In the distributed fashion, we propose a receiver-based approach for neighbor discovery. Node i broadcasts a start beacon that informs its neighbors about its position and velocity. Each receiver computes its own $\text{CD}{\text{P}}_n^a$ value by (7) or (13). In order to reduce the communication overhead, it can only answer to the beacon after a waiting time based on its $\text{CD}{\text{P}}_n^a$ value by a uniform rule as defined in the following:

$$\begin{array}{cc}& T_n=\frac{T^{\mathrm{\ast }}}{\text{CD}{\text{P}}_n^a},\end{array}$$

(14)

where $T^{\mathrm{\ast }}$ , set by the VANETs system, is a time parameter to control the relation between $\text{CD}{\text{P}}_n^a$ value and waiting time of receiver n. n means the node which can receive the start beacon from node i, which is node i's neighbor. The waiting time of neighbor n is inverse correlation with the value of $\text{CD}{\text{P}}_n^a$ calculated by (7) or (13). It is easily observed that the neighbor with the maximum $\text{CD}{\text{P}}_n^a$ has the smallest waiting time; therefore it will answer to node i at the first time. Once node i hears this answer, it will broadcast a stop message to all neighbors to terminate the current neighbor discovery. Thus the neighbor list of node i will have only one node. If node i has not received any answers before the expired time, its neighbor list will be empty at current time. The optimal forwarding algorithm will select the best next hop from this neighbor list, as mentioned in Section 3.2. Since $d_l$ is higher than $d_{\text{th}}$ , such a distributed way for neighbor discovery will significantly reduce the communication overheads.

This adaptive neighbor discovery algorithm requires each node to previously know the local vehicular density, which is easily to be obtained by the current commercial applications [19], as mentioned before. Intuitively, this adaptive approach will increase the average data delivery ratio by reducing the communication overheads during the neighbor discovery in dense networks, while decreasing the delay by reducing the waiting time in sparse networks.

Remark. The adaptive neighbor discovery algorithm still works when the update of neighbor list is triggered by the forwarding event.

3.4. Routing Path Recovery Strategy

In the dynamic wireless environment, it is inevitable that the routing path fails or breaks. Once a selected link breaks, a local recovery procedure takes place. To improve the robustness of ARP-QD, the adopted recovery strategy is based on the idea of carry-and-forward [23]. The sender which detects the broken link will explore the one-hop neighbors to find a backup link. If the sender has no one-hop neighbor, it will carry the packet until another node moves into its transmission range to transfer the packet. Furthermore, such a carry-and-forward strategy guarantees loop-free routing and avoids endlessly forwarding loop by marking the previous hops.

3.5. A Walk-Through Example

The whole ARP-QD contains the two main novel algorithms proposed above: optimal forwarding algorithm and adaptive neighbor discovery algorithm. In order to improve the robustness of ARP-QD, the carry-and-forward strategy for routing path recovery is also complemented. We use the following example, depicted in Figure 5, to illustrate how ARP-QD works. According to the QoS requirement of certain application, the adaptation factors α and β are set for computation of $\text{CD}{\text{P}}_n^a$ and $\text{SS}{\text{W}}_j$ . With the help of onboard GPS, navigation system, and digital map, the source node S can obtain the position of destination. The dotted parallel lines denote the transmission range of the source node S. We assume all nodes have the same transmission range.

• (1)

The source node is in the segment area, and the local vehicular density around S is smaller than the certain density threshold $d_{\text{th}}$ . Thus, S exploits the centralized way to discover neighbors and compute the $\text{CD}{\text{P}}_n^a$ value of each candidate neighbor. After collecting the $\text{CD}{\text{P}}_n^a$ information, S chooses the one with maximum $\text{CD}{\text{P}}_n^a$ as the best next hop, which is $s_{\mathrm{1}}$ in this case. For the same way, $s_{\mathrm{2}}$ is selected to be the best next hop of $s_{\mathrm{1}}$ .

(2)

The sender $s_{\mathrm{2}}$ approaches the intersection $I_{\mathrm{5}}$ . First, $s_{\mathrm{2}}$ needs to choose the best next intersection with the minimum value of SSW. $s_{\mathrm{2}}$ broadcasts a beacon with $\text{CP}\_\text{REQ}$ to request the information of connectivity from the current intersection to all candidate intersections. It aims to find the intersection with the shortest path length $\text{P}{\text{L}}_{sj}$ , the least direction change angle θ, and the connectivity with the current intersection. In this example, when $s_{\mathrm{2}}$ traveling to $I_{\mathrm{2}}$ arrives at $I_{\mathrm{5}}$ , it has two candidate intersections, that is, $I_{\mathrm{4}}$ and $I_{\mathrm{8}}$ . Note that $\overrightarrow{v}$ and $\overrightarrow{p}$ are the moving directions of sender $s_{\mathrm{2}}$ and the delivered packet, respectively. $s_{\mathrm{2}}$ computes $\text{SS}{\text{W}}_{\mathrm{4}}$ and $\text{SS}{\text{W}}_{\mathrm{8}}$ according to (9). It is easy to get that $U_{\mathrm{4}}=\mathrm{1}$ and $U_{\mathrm{8}}=\mathrm{0}$ because there are no vehicles between intersections $I_{\mathrm{5}}$ and $I_{\mathrm{8}}$ . Hence, $s_{\mathrm{2}}$ chooses $I_{\mathrm{4}}$ with the minimum SSW as its next intersection. Next, $s_{\mathrm{2}}$ selects its best next hop. Assume that the local vehicular density of $s_{\mathrm{2}}$ is smaller than the density threshold $d_{\text{th}}$ . $s_{\mathrm{2}}$ uses the centralized way to compute the $\text{CD}{\text{P}}_n^a$ values of candidate neighbors located in the selected segment. Assuming that $s_{\mathrm{3}}$ has the maximum $\text{CD}{\text{P}}_n^a$ , it is selected to be the next hop.

(3)

The local vehicular density of $s_{\mathrm{3}}$ is higher than the density threshold $d_{\text{th}}$ ; therefore $s_{\mathrm{3}}$ adapts to the distributed fashion to discover neighbors. $s_{\mathrm{3}}$ broadcasts a start beacon to inform its neighbors about its position and velocity. Each neighbor which received the beacon will compute its unique waiting time for sending answer to $s_{\mathrm{3}}$ based on (14). In this case, we assume $s_{\mathrm{4}}$ is the one which first replies and then $s_{\mathrm{4}}$ is selected to be the best next hop of $s_{\mathrm{3}}$ .

(4)

If the link fails when $s_{\mathrm{4}}$ is sending packets, the recovery mode of routing path is active. $s_{\mathrm{4}}$ will notice its neighbors and find a backup link from its current neighbors. If $s_{\mathrm{4}}$ has no neighbor to deliver packets, it will carry them until some appropriate nodes move into its transmission range. The following process of packet forwarding is the same as the above illustrated until the packet is delivered to its destination D.

Figure 5

A walk-through example.

4. Performance Evaluation

To evaluate the performance of the proposed ARP-QD, we simulate the protocol on a variety of data transmission rates and network densities. To compare the performance of ARP-QD with the previous works in VANETs routing, we also simulate basic GPSR [7], which aims to find a path with minimum hop count, and ROMSGP [11] which can guarantee a high level of stable communication to some extent. Note that most of geographic VANET routing protocols are based on GPSR with little differences in essence. ROMSGP is a classical stable VANET routing protocol for comparison.

4.1. Simulation Environment

We simulate ARP-QD in the vehicle traffic model using the standard NS2 simulator [24], which offers full simulation of the IEEE 802.11 physical and MAC layers. In our simulation, network size is set to be $\mathrm{50}$ , $\mathrm{100}$ , $\mathrm{150}$ , $\mathrm{200}$ , and $\mathrm{250}$ nodes with 802.11 WaveLAN radios. The assumptions are that all vehicles have the same transmission range of 250 m and all packets have the same size of $\mathrm{512}$ bytes. We simulate $\mathrm{20}$ constant bit rate (CBR) traffic flows to destinations, and sources and destinations are picked up randomly. The transmission rate of each CBR flow is set to be $\mathrm{0.5}$ , $\mathrm{1.0}$ , $\mathrm{1.5}$ , $\mathrm{2.0}$ , $\mathrm{2.5}$ , and 3.0 packets per second (p/s). Each simulation lasts for $\mathrm{1000}$ seconds. Table 1 summarizes the key parameters in the simulation.

Table 1

Simulation parameters.

Parameter	Value
Number of lanes	2
Number of nodes	50, 100, 150, 200, 250
Velocity	10–30 m/s
Simulation duration	1000 s
Simulation area	10 × 10 km2
Channel capacity	2 Mbps
Wireless communication range	250 m
Mac protocol	802.11 DCF
Beacon interval	0.5 s
Data packet size	512 bytes
CBR rate	0.5, 1.0, 1.5, 2.0, 2.5, 3.0 p/s
Routing protocol	ARP-QD, GPSR, ROMSGP

4.2. Mobility Model

The mobility model has a great impact on the studied protocol behavior in the simulation and the corresponding results [25]. For evaluating protocol performance accurately in such a complex and dynamic vehicular environment, we use VanetMobiSim [25] to initially place nodes uniformly at random and generate the random movement of the nodes within a $\mathrm{10}\times \mathrm{10}\hspace{0.17em}\text{k}{\text{m}}^{\mathrm{2}}$ rectangular region with a maximum speed of 30 m/s. Figure 5 shows the simulation scenario, including 9 intersections and 12 road segments. We assume that a road segment composes two lanes without traffic signals. When a node approaches the intersection, it will randomly choose a road segment to turn its direction without pause.

4.3. Simulation Results

We focus mainly on the performance of delivery ratio and delivery delay in the simulation. (1) Delivery ratio is measured as the ratio of the number of successfully delivered data packets to the total number of transmitted data packets. The packet will be dropped when it fails to be delivered, without retransmission rule. (2) Delivery delay is measured as the average time elapsed from sending the packet by the source node to receiving it by the destination. Without loss of generality, we first fix the adaptive weigh factors $(\alpha ,\beta )$ at (0.5,0.5) to evaluate the impact of transmission rate and network density. Next, we fix the transmission rate at 1.5 p/s and the number of nodes at $\mathrm{150}$ to observe the impact of adaptive weight factors α and β.

4.3.1. Delivery Ratio

The number of nodes is set to $\mathrm{150}$ when we study the impact of transmission rate, while the transmission rate is fixed at 1.5 p/s when we focus on the impact of network density. Figures 6 and 7 show the delivery ratio with respect to varied transmission rate and the number of nodes, respectively. The two figures show that the proposed ARP-QD has higher delivery ratio compared with that of GPSR and ROMSGP in all cases. The reason is that ARP-QD considers the whole path based on the SSW metric, while GPSR works on the vehicle-by-vehicle forwarding and ROMSGP makes the vehicles with the same moving direction into groups, which only considers the local segment, rather than the whole path. Another reason is that the adaptive neighbor discovery algorithm reduces the communication overheads. Furthermore, from Figure 6 we can see that the delivery ratio of ARP-QD does not change much as the transmission rate is increased, while that of GPSR and ROMSGP deteriorates. This comes from the fact that the routing paths found by ARP-QD are more tolerant to the high network load due to the adaptive neighbor discovery algorithm. The main reason is that the adaptive neighbor discovery algorithm largely reduces the beacon cost to require neighbors’ information, which reserves more bandwidth for data delivery. Thus, the network load is still tolerable when the transmission rate rises up to 3.0 p/s. From Figure 7 we can observe that the delivery ratio increases with the rise of the number of nodes but decreases when the number of nodes goes up to $\mathrm{200}$ . The reason is that before the number of nodes reaches $\mathrm{150}$ or other values less than 200, the increased network density becomes higher than the density threshold and the enhanced connectivity and the reduced communication overheads during the neighbor discovery procedure improve the delivery ratio. With the continuous increase of node density, the overheads increase for updating all nodes’ neighbor list. Thus the performance of delivery ratio diminishes.

Figure 6

Delivery ratio versus transmission rate.

Figure 7

Delivery ratio versus the number of nodes.

4.3.2. Delivery Delay

As shown in Figure 8, the delay of ARP-QD is the same as that of GPSR but is lower than that of ROMSGP at lower transmission rate. That is because the collisions are rare to happen when the transmission rate is lower and ROMSGP tends to choose the path with more hops for stability. However, when the transmission rate increases, the performance of ARP-QD deteriorates in terms of delivery delay. That is because high transmission rate makes the sender fail to find a backup neighbor quickly; when the link breaks, the time of carry-and-forward procedure prolongs the delivery delay. In brief, ARP-QD is not suitable for the applications with high QoS requirement on delivery delay when the network load is higher. Figure 9 shows that the delay of all protocols decreases along with the increase of the number of nodes. The reason is that packets can be delivered quickly with less caching time when the network density is high. Moreover, ARP-QD only has little difference on the delivery delay compared with the other two protocols when the number of nodes increases, which means ARP-QD does not give high compromise on the delivery delay.

Figure 8

Delivery delay versus transmission rate.

Figure 9

Delivery delay versus the number of nodes.

4.3.3. The Impact of Adaptive Factor α

In order to evaluate the impact of weight factors α and β for different QoS requirements, we obtain the simulation results of delivery ratio and delivery delay when α increases from $\mathrm{0.1}$ to $\mathrm{0.9}$ with the interval of $\mathrm{0.2}$ . In Figures 10 and 11 where the transmission rate is set to 1.5 p/s, the four curves represent different number of nodes. In Figures 12 and 13 where the number of nodes is set to $\mathrm{150}$ , the six curves represent different transmission rate.

Figure 10

Delivery ratio versus α.

Figure 11

Delivery delay versus α.

Figure 12

Delivery ratio versus α.

Figure 13

Delivery delay versus α.

From Figures 10, 11, 12, and 13, we can draw the conclusion that the delivery ratio declines, while the delivery delay goes down along with the increase of α. That is because the link efficiency has larger weight and the link stability has smaller weight accordingly when the factor α is increased. The link has more probability to break down along with the rise of α; thus the delivery ratio turns worse. At the same time, the number of hops for each path is decreased with the higher requirements on link efficiency; thus the delivery delay is improved. In addition, from Figure 12, we can observe that the delivery ratio of ARP-QD does not vary much when the transmission rate changes, which is the same as that observed in Figure 6. Figure 13 shows that the delivery delay of ARP-QD varies much when the network density changes as analyzed in Figure 8. These results show that the weight factor α can adaptively satisfy the diverse QoS requirements of different applications.

5. Conclusion

In this paper, the proposed adaptive routing protocol based on QoS and vehicular density (ARP-QD) is capable of finding a fast and reliable path for end-to-end data delivery within urban VANETs environments according to diverse QoS requirements of different applications. To reduce the communication overheads furthermore, ARP-QD adopts the adaptive fashion to obtain the neighbors’ information based on local vehicular density and recovers quickly when the routes are disrupted. Numerical simulations showed that ARP-QD has a higher delivery ratio than GPSR and ROMSGP, without giving large compromise on the delivery delay. In the future, we shall take the real data trace into consideraion to validate ARP-QD protocol and combine the link correlations to estimate link quality.