Connectivity-Sensed Routing Protocol for Vehicular Ad Hoc Networks: Analysis and Design

Abstract

With the fast development of vehicular ad hoc networks (VANETs), various VANET applications, especially safety and infotainment service, have stronger requirements for reliable network connectivity. Intermittent connectivity has become a thorny problem in VANETs, which causes unreliable vehicle to vehicle (V2V) connection due to high vehicle mobility. In this paper, we have studied the network connectivity using a stochastic analysis model and then we prove average intervehicle distance influences VANET connectivity greatly. Based on our analysis, we propose a connectivity-sensed routing protocol (CSR) for VANETs in urban scenario. CSR utilizes vehicle distribution information collected by intersection infrastructure to help vehicles select a road not only with progress to destination but also with better network connectivity. Moreover, simulation results demonstrate that the CSR protocol achieves much lower end-to-end delay, higher delivery rate, and higher throughput than traditional routing protocols.

1. Introduction

Mobile ad hoc networks (MANETs) are comprised of self-organizing mobile nodes that communicate with each other without a centralized network infrastructure. Vehicular ad hoc networks (VANETs) are special types of MANETs, which promote the improvement of the safety and efficiency of transportation system [1].

In the last few years, we have witnessed a large increase in research and development in this area. Several factors have led to this development, including wide adoption (and subsequent drop in cost) of IEEE 802.11 technologies and the fast development of vehicle manufactures based on information technology.

Although VANETs are similar to the MANETs, VANETs have many unique features. Unlike other general large scale wireless networks [2, 3] which pay more attention to wireless capacity, VANETs face a more serious issue of how to route messages in complex network environment with variation. In VANETs, vehicles travel along a road and communicate with each other and possibly with road-side infrastructure. So the highly dynamic topology, restricted moving patterns, and uneven distribution of vehicles are key features of VANETs. In addition, multihop message transmission communication makes up the bulk of the communications behavior in VANETs. For V2V communications, a central challenge of VANETs is that no communication coordinator can be found to relay the packets. In such networks, intermittent connectivity [4] will be a crucial and inevitable problem which can seriously affect the routing performance.

Based on the above unique characteristics of VANETs and the challenges they bring [5], it has been proven that position-based routing [6] outperforms the traditional topology-based routing. Besides, the intersection-based routing is more suitable to implement in urban scenario and obtains relatively better performance.

Along with the fast development of VANET application, for example, the safety application and infotainment application, more and more promising applications and the cost effectiveness of VANETs constitute major motivations behind increasing interest in such networks. Except for driving the development of VANETs, those applications are calling for more reliable network connectivity as well. The issue of intermittent connectivity becomes rather vital. Therefore, designing specific routing protocols for urban scenario is more and more significant. Many works have been researching on that problem. When intermittent connectivity happens, one of the most adopted repair strategies is carry and forward [7] strategy: a moving vehicle stores the packet when it cannot find its next hop until a valid vehicle appears in its transmission range. Besides, [8] studied the multipath routing scheme, which can also improve the packet delivery to some extent. To further improve the reliability of packets delivering, opportunistic routing [9] strategy was put forward and studied.

All the above solutions are at the cost of two aspects. One is the more resource consumption, because the storing and multipath strategies add further overhead for each vehicle. The other one is the uncontrollable end-to-end delay, because, in the carry and forward strategy, the vehicle storing the packets does not know when to transmit until the next hop is found. Meanwhile, a series of specific intersection-based protocols were proposed to be applied to urban scenario: in Improved Greedy Traffic Aware Routing Protocol (GyTAR) [10], traffic density and road information are taken into consideration as a weighing factor to choose intersection. In GSR [11], the information of selected intersection is included in each packet. To the best of our knowledge, most of the current intersection-based protocols in the literature recognize traffic density as a main factor to choose intersections. In fact, traffic density is not exact and sometimes cannot comprehensively reflect the traffic state, because high vehicle density does not always signify good network connectivity [12], which has intense effects on packet delivering.

In this paper, we focus on discussing the network connectivity from the angle of vehicle distribution and give our way to measure network connectivity. Based on the analysis, we propose a connectivity-sensed routing (CSR) protocol. By simulating our protocols in general urban scenario, we prove that CSR is more efficient compared with protocols which simply consider the traffic density.

Following this introduction, in Section 2, we discuss some related work devoted to the analysis of network connectivity. Besides, Section 2 discusses series of current routing protocols in VANETs. In Section 3, we utilize a stochastic queuing network model to analyze the key factors affecting the network connectivity and present the analysis results. In Sections 4 and 5, we demonstrate our CSR protocol and implement simulations. Section 6 includes conclusion and future work.

2. Related Works

Network connectivity is a fundamental measure of vehicular ad hoc networks performance. Intuitively, vehicle nodes are responsible for multihop forwarding. In low-connectivity areas, vehicles cannot communicate with each other. How to measure the network connectivity? Researches mainly center on both theoretical analyses and simulations. In [13], connectivity is measured by the expected propagation distance. Reference [14] analyzes the probability for having at least one communication path between two vehicle nodes. The k-connectivity is discussed in [15]. Work [16] presents an analytical framework for determining the connectivity requirements in distributing the traffic information in VANETs. In [17], connectivity is studied as a covering problem using lattice networks as background. Work [18] studies a directed connectivity probability problem and obtains a closed-form polynomial expression of the directed connectivity of square lattice networks.

One typical issue closely related to network connectivity is the intermittent connectivity in real VANETs. Intermittent connectivity happens due to vehicles’ high mobility and unreliable channel quality. In academia, there are several classical schemes proposed to meet the challenge, which can be classified into four types. Routing protocols based on flooding are the simplest strategy, such as epidemic routing [19]. In epidemic routing protocols, random pair-wise exchanges of messages occur among proximate mobile nodes. The epidemic routing trades system bandwidth and buffer space of node for the eventual delivery of a packet. As a result, its overhead is high. The second is the multipath scheme [8] in which the packet is transmitted through several paths. Compared with the flooding based strategy, the multipath scheme has lower overhead and higher throughput. But it is difficult to determine how, when, and where to start a new path. The carry and forward is the mostly utilized strategy. In particular, existing solutions [20, 21] improve the carry and forward strategy according to special demand. Generally, the carry and forward strategy suffers an uncontrolled end-to-end delay. The last one is infrastructure-based [22] scheme in which the infrastructure caches data and waits for a chance to forward. The drawback of this method is the lack of flexibility.

As research continues, the classical intersection-based routing greedy perimeter coordinator routing (GPCR) [23] was proposed. GPCR considers a set of anchors that are overlaid on top of the city map, and it firstly forwards packets to a coordinator located at the intersection and then forwarding decision is made at the intersection. GyTAR, which was mentioned above, rules that when a packet comes to an intersection, the forwarding vehicle (coordinator) calculates the score of each road segment. The road segment with higher density and shorter distance to the destination is assigned a higher score. Then the road segment with the highest score is chosen for packet forwarding. Though the intersection mechanism is adopted, issue of network connectivity is not considered. Unfortunately, intermittent connectivity may happen when packets are forwarded to bad connected segment, which will greatly degrade the routing performance. Even though the use of score calculation is still an inspiring mechanism, to the best of our knowledge, in academia, network connectivity has been studied and used for routing in recent years. Connectivity aware routing (CAR) [24] selects a better path to transmit data packets through the route request and discovery process. By adaptively adjusting the interval of hello message and using Preferred Group Broadcasting (PGB) in data dissemination, CAR keeps a relatively lower overhead. However, CAR mainly focuses on destination location and path maintenance and, as a result, it performs relatively worse in urban scenario than in highway. Moreover, CAR estimates the network connectivity in a distributed method. In this method, each forwarder changes three other packet fields, which are “number of hops,” “average number of neighbors,” and “minimum number of neighbors.” In sections below, we will illustrate that merely the number of neighbors cannot exactly reflect the network connectivity.

In order to adjust to the urban scenario, intersection connectivity aware routing (iCAR) [25] is proposed. In iCAR, real-time information is locally and dynamically calculated at each road, by sending out a control packet (CP) to discover connectivity and collect vehicular traffic information while traversing the road segment. iCAR evaluates the connectivity based on the minimum vehicular density, the one-hop transmission delay, and the number of intermediate forwarders. However, the one-hop transmission delay and the average hops much lie on the channel state [26], while, in complex urban communication scenario, channel state changes so fast that the one-hop delay cannot reflect real-time connectivity. So, in realistic communication scenario of urban VANETs, this method is not so practical.

Based on these issues and facts, we have been studying network connectivity from a new angle which is feasible to guide designing routing protocols. In the following section, an analytical model will be proposed and analyzed. Based on our analyzing results, we propose the CSR protocol.

3. Analytical Model

Considering there are many intersections in urban scenario, which will bring complex factors for modeling and analyzing, we take modest simplification in this paper; that is, we use a road segment as our analyzing object. By analyzing our mathematical model, we finally obtain the probability distribution function of the distances between two vehicles and the probability of one vehicle node isolated, which can help us evaluate the connectivity on a certain road and thus provide theoretic foundation for our proposed protocol.

3.1. Distribution of the Intervehicle Distances

We consider a unidirectional road segment of L-meters length. In our assumption, we let a fixed point (observer) stand at an intersection. For vehicles on the road, there are M discrete levels of speeds: $v_i,\hspace{0.17em}\hspace{0.17em}i=\mathrm{1,2},\dots ,M$ ; speeds obey i.i.d. The arrival rate of vehicles with speed $v_i$ seen by observer is ${\lambda }_i$ (in vehicles per second), so the global arrival rate is $\lambda ={\sum }_{i=\mathrm{1}}^M{\lambda }_i$ . Further, we assume that the arrival process is in free flow state, and thus the arrival rate ${\lambda }_i$ obeys the Poisson distribution and is independently identically distributed. So the probability of occurrence of speed $v_i$ is $p_i={\lambda }_i/\lambda$ . Let $X_i$ be the random distance between vehicles with speed $v_i$ ; let $T_i$ be the random interarrival time; obviously, according to the stochastic theory, it obeys the exponential distribution: $P(T_i>t)=e^{-{\lambda }_i·t}$ ; let $X_i=v_i·T_i$ , since the $v_i$ and the $T_i$ are independent of each other, we get

$$\begin{array}{cc}& p\left(X_i>x\right)=p\left(v_i>\frac{x}{T_i}\right)=p\left(T_i>\frac{x}{v_i}\right)=e^{-{\lambda }_{i}x/v_i}.\end{array}$$

(1)

Let X be the random distance between two consecutive vehicles on a certain road segment, so $X=\min \left\{X_{\mathrm{1}},X_{\mathrm{2}},\dots ,X_M\right\}.$ It was observed in [27] that the variable X obeys exponential distribution with parameter $\xi ={\sum }_{i=\mathrm{1}}^M{\lambda }_i/v_i=\lambda ·{\sum }_{i=\mathrm{1}}^M{p}_i/v_i$ ; according to the stochastic process theory, the cumulative distribution function (CDF) of X is

$$\begin{array}{cc}& F_X\left(x\right)=\mathrm{1}-e^{-\xi ·x},x\ge \mathrm{0}.\end{array}$$

(2)

In addition, we let all vehicles have the same fixed transmission range, which is denoted as R (meters).

Here we discuss the parameter $v_i$ . For a certain road segment, such parameter can be obtained by experimental observation. However, in literature, it has been accepted that speed in the free flow traffic state obeys normally distribution. Table 1 shows some typical values of the mean and variance of the vehicles’ speed on a certain road segment. Thus, the probability density function (PDF) of speed can be given by

$$\begin{array}{cc}& f_v\left(v\right)=\frac{\mathrm{1}}{\sigma \times \sqrt{\mathrm{2}\pi }}\times \exp \left(-\frac{{\left(v-\mu \right)}^{\mathrm{2}}}{\mathrm{2}{\sigma }^{\mathrm{2}}}\right),\end{array}$$

(3)

where μ is average speed and σ is standard deviation. To deal with negative or zero speeds, we shall make a truncation to the range of speed, given by

$$\begin{array}{cc}& g_V\left(v\right)=\frac{f_V\left(v\right)}{{\int }_{v_{\mathrm{m}\mathrm{i}\mathrm{n}}}^{v_{\mathrm{m}\mathrm{a}\mathrm{x}}}{f}_V\left(u\right)du}.\end{array}$$

(4)

We let $v_{\mathrm{m}\mathrm{i}\mathrm{n}}=\mu -\mathrm{3}\sigma$ and $v_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mu +\mathrm{3}\sigma$ ; as is known, for the normal curve, the probability of an arbitrary speed lying in the range ( $\mu -\mathrm{3}\sigma$ and $\mu +\mathrm{3}\sigma$ ) is about 99.7%. Therefore, we almost take into considerations almost all speeds and do not lose generality. We bring Gaussian error function $\mathrm{erf}(x)$ and substitute for $f_V(u)$ in (4), and then we get

$$\begin{array}{l}{g}_V\left(v\right)\\ =\frac{\mathrm{2}{f}_V\left(v\right)}{\mathrm{erf}\left(\left(v_{\mathrm{m}\mathrm{a}\mathrm{x}}-\mu \right)/\sigma \sqrt{\mathrm{2}}\right)-\mathrm{erf}\left(\left(v_{\mathrm{m}\mathrm{i}\mathrm{n}}-\mu \right)/\sigma \sqrt{\mathrm{2}}\right)},\\ v_{\mathrm{m}\mathrm{i}\mathrm{n}}\le v\le v_{\mathrm{m}\mathrm{a}\mathrm{x}}.\end{array}$$

(5)

Table 1

Relationship between μ and σ.

μ [km/h]	10	15	20	30	45
σ [km/h]	5	7	11	15	30

3.2. Connected Probability Analysis

Hereinafter we will analyze the model and derive the expressions for the connectivity probability, in the condition of free flow. Hereinbefore, we got the expression of average intervehicle distance X with parameter ξ. Now we define the vehicle density as below

$$\begin{array}{cc}& {\rho }_{\text{avg}}=\frac{\mathrm{1}}{E\left[X\right]}=\lambda {{\displaystyle \sum }}_{i=\mathrm{1}}^M\frac{p_i}{v_i}.\end{array}$$

(6)

Let us substitute $E\left[\mathrm{1}/v\right]$ for ${\sum }_{i=\mathrm{1}}^M{p}_i/v_i$ ; then we can get ${\rho }_{\text{avg}}=\lambda ·E\left[\mathrm{1}/v\right]$ ; further, as is assumed, the vehicle speed is distributed as truncated Gaussian PDF; work [14] denotes that

$$\begin{array}{ll}E\left[\frac{\mathrm{1}}{v}\right]& =\frac{\mathrm{2}\lambda /\sqrt{\mathrm{2}\pi }\sigma }{\mathrm{erf}\left(\left(v_{\mathrm{m}\mathrm{a}\mathrm{x}}-\mu \right)/\sigma \sqrt{\mathrm{2}}\right)-\mathrm{e}\mathrm{r}\mathrm{f}\left(v_{\mathrm{m}\mathrm{i}\mathrm{n}}/\sigma \sqrt{\mathrm{2}}\right)}\\ & ·{{\displaystyle \int }}_{v_{\mathrm{m}\mathrm{i}\mathrm{n}}}^{v_{\mathrm{m}\mathrm{a}\mathrm{x}}}\frac{\mathrm{1}}{v}\exp \left(-\left(\frac{v-\mu }{\mathrm{2}{\sigma }^{\mathrm{2}}}\right)\right)dv.\end{array}$$

(7)

As is shown in (7), no closed-form expression is obtained, so it is evaluated by numerical integration. According to the traffic flow theory in steady state, on a certain road segment, we can denote the number of vehicles as

$$\begin{array}{cc}& N_{\text{avg}}=L{\rho }_{\text{avg}}.\end{array}$$

(8)

Hereinbefore, we assumed that all vehicles have fixed transmission distance R, and, also, we obtained the probability distribution function of the random intervehicle distance which is exponentially distributed with parameter ξ. Now we consider the network connectivity from the angle of the relationship between transmission distance and intervehicle distance. According to the above formula, the probability that two consecutive vehicles are connected is equal to the probability that the intervehicle distance is less than transmission distance R; that is

$$\begin{array}{cc}& F_X\left(R\right)={\left.\mathrm{1}-e^{-\xi x}\right|}_{x=R}=\mathrm{1}-e^{-\xi R}=\mathrm{1}-e^{-{\rho }_{\text{avg}}R}.\end{array}$$

(9)

We say that, on a certain road segment, if the network is connected, it should satisfy that arbitrary two consecutive vehicles are connected. Therefore, the connectivity probability is denoted as follows:

$$\begin{array}{cc}& P_C=F_X{\left(R\right)}^{N_{\text{avg}}-\mathrm{1}}={\left(\mathrm{1}-e^{-{\rho }_{\text{avg}}R}\right)}^{N_{\text{avg}}-\mathrm{1}}.\end{array}$$

(10)

The probability that a vehicle is isolated is computed as follows:

$$\begin{array}{cc}& P_{\mathrm{0}}=e^{-{\rho }_{\text{avg}}R}.\end{array}$$

(11)

3.3. Extensive Analysis and Numerical Results

In this section, we evaluate the model by extensive simulations. As is assumed before, in free flow state, no intersections are considered temporarily. What we simulate is a 2 km uninterrupted road segment without traffic lights. Our simulation tool is Matlab. In the simulation, we set the vehicles arriving rates as 0.2 vehicles/sec and 0.5 vehicles/sec in a Poisson process. Vehicle speed is chosen from a Gaussian sequence. Then we have such an analogy: the arrival rate has the same distribution as that in a queuing system, and the vehicle speed has the same distribution as the service rate in a queuing system; according to Little's law, we attain the following expression

$$\begin{array}{cc}& N_{\text{avg}}=\frac{\lambda }{v}.\end{array}$$

(12)

To understand the relationship between vehicle arrival rate λ and the vehicle density of the road, we can refer to Figure 1. In Figure 1, the vehicle speed is set as 10, 15, 20, and 30 km/hour, respectively. As the vehicle arrival rate increases, the vehicle density increases in a linear fashion and the higher vehicle speed corresponds to the lower slope. The result shows that, under the same arrival rate λ, vehicle density on a low-speed road segment is usually higher than that on a high-speed road segment. The curve plotted in Figure 2 expresses that as the transmission range increases, the probability of an arbitrary vehicle being isolated decreases. In Figure 3, we evaluated the network connectivity against transmission range for different values of vehicle arrival rate. As is shown, the connectivity increases as transmission range R increases; in addition, for a fixed transmission range, the higher λ, the better connectivity. It is because the higher λ corresponds to a higher vehicle density on a road segment, which leads to a higher $N_{\text{avg}}$ and thus the network connectivity is better.

Figure 1

Vehicle density versus vehicle arrival rate.

Figure 2

Isolated probability versus average distance.

Figure 3

Connectivity probability versus average distance.

In real VANETs, if an application has a high requirement for connectivity, we can increase the transmission power to enlarge the transmission range; thus we can get a higher connectivity. However, a larger range will cost more energy and will partly cause interference to the nearby vehicles.

3.4. Extend to Two-Way Road Mode

In our above analysis, we used a simplified traffic model in which vehicles move on a unidirectional road. Can the results obtained be used in a two-way scenario? In fact, for the two-way streets, the traffic of different directions are independent and a superposition can be made: $\lambda ={\lambda }_{\text{left}}+{\lambda }_{\text{right}}$ , where ${\lambda }_{\text{left}}$ and ${\lambda }_{\text{right}}$ are the traffic flows in the left-to-right and right-to-left directions, respectively.

In two-way model, the distance of adjacent nodes is still denoted by Euclidean distance in plane, which is shown in Figure 4. Consequently, with all speeds in both directions taken into consideration, (1) can still be used. In this way, all the studies done in the previous work can be adopted. Either unidirectional or bidirectional communication in VANETs, average distance is a key factor influencing network connectivity. We will investigate the two-way model in more detail in our future work.

Figure 4

Illustration of intervehicle distance in two-way scenario.

4. CSR Protocol

CSR is an intersection-based protocol. Different from those traditional intersection-based protocols, CSR takes advantages of computing power and tries to guarantee that the forwarder selects a road segment which not only brings progress to the destination, but also is with better connectivity. In this section, we will introduce our proposed CSR protocol in detail. Then we implement simulations by NS2 [28] and VanetMobisim [29].

4.1. Problem Statement

Nodes in VANETs move in specific patterns which are restricted to roads and, as a result, they are not distributed evenly any more. Traditional geographic routing protocols which only consider distance progress and vehicle density will suffer serious intermittent connectivity and will fail to deliver the packets in such a case. Figure 5 shows such network situation. The red path indicates the message routing path of GPCR and GPSR. The vehicles V1 and V2 cannot find the next hop within transmission range and finally the packets will be dropped. Traditional routing protocols face great challenges. Driven by the need to tackle such a problem, we propose CSR protocol.

Figure 5

Illustration of the routing problem in VANETs.

4.2. Assumption

Along with the development of computer technology and embed system, the vehicle equipment is competent to execute high-speed calculation. Thus, more completed parameters can be taken into consideration in order to design a better-performing routing protocol.

4.2.1. Hardware

We assume that current technology can satisfy those hardware and software requirements on communication. That is, all vehicles are equipped with communication devices for wireless communication. Besides, vehicles are also equipped with GPS devices for positioning.

4.2.2. Negligible Vehicle Movement

Message propagation is instantaneous with respect to vehicle movement, and this assumption is supported by experiments in [30]. In that work, it takes 110 ms to transmit a message of 73 bytes with a device whose transmission rate is 3.6 kb/s. If the transmission range is 500 m, then a message can propagate as far as 5000 m for 10 hops, about 1.1 s. During that short time, the vehicles’ flowing in and out of a certain road segment can be ignored.

4.3. Design Solution

In CSR protocol, we design a new method for an intersection forwarder to weigh the different intersections. As has mentioned above, [11] presents an intersection-based protocol GyTAR; it gives a score formula $S\left(i\right)=\alpha \times f\left(T_i\right)+\beta \times g\left(D_i\right)$ , where $T_i$ is traffic density and $D_i$ is the curve metric distance (adjusted with road topology). Let us analyze the situation in Figure 5; we can obviously find that though traffic density on segments R1 and R3 is higher than that in segment R4, according to most intersection protocols in which traffic density and distance are major measuring factors in this case, the source car will choose I2 or I3 as its temporary destination and will forward data packet to vehicles on relevant segments. However, we can see that the distribution of vehicles is more uneven, which will cause intermittent connectivity. In our protocol, network connectivity is taken into consideration. Though traffic density in R4 is lower, the advantages in network community render segment R4 chosen. Therefore the packets will be successfully delivered following the red path.

4.4. Collection of the Vehicle Geographic Information

As has been discussed above, a forwarder located at an intersection needs to evaluate connectivity of adjacent roads by utilizing the vehicle geographic information. In CSR, such information is broadcasted by the infrastructure located at the intersection. Naturally, there is a question how to collect that vehicle geographic information. In academia, there are studies [25, 31] utilizing on-the-fly process to collect the information including average number of neighbors and one-hop delay. There are two reasons why we do not use it. The first one is timeliness. When a vehicle arrives at an intersection, the information it obtains is probably from some time ago because the network quality also frequently changes. Second, the on-the-fly collection process needs an extra overhead, which will not only burden the network, but also incur an increase of collision probability, especially when raising the sending rate of on-the-fly packet to improve the timeliness.

In CSR, we assume this problem is treated by other highly real-time technical methods, for example, by electronic eyes which have been equipped at intersections combined with image processing, road sensors, or infrastructure affording relay in the future 5G [32].

4.5. Packet Format Design

In Figures 6 and 7, PI means the packet ID, T means the time starting sending this packet, and PT means the packet type.

Figure 6

Notification message format.

Figure 7

Beacon packet format.

In Figure 6, for the notification message broadcasted by the intersection infrastructure, RI is the road ID and VP is the vehicle position.

Particularly, in Figure 7, beacon packet contains MA (My Address, i.e., the current vehicle address), DA (Destination Address), and DI (Destination ID). The address is expressed by x coordinate and y coordinate in planar areas.

Considering that too much payload will increase the burden of network, CSR restrains hello packet to a smaller size as possible. As a result, beacon period is able to be set to less than 1 s short and, thus, the geographic information will be more up-to-date. Infrastructures located at intersections can give needed geographical location information. How can these packets be used in CSR? In the following we will give a detailed description.

4.6. Working Mode

According to the current vehicle's different position, CSR works in two modes: segment mode and intersection mode.

4.6.1. Segment Mode

When a packet travels on a road segment, the segment mode will work. In this mode, a forwarding vehicle transmits a data packet to its neighbor as far as possible. Such a method is called greedy scheme; though this scheme is not a standard so far, it is really adopted by the literature. If the forwarding vehicle does not have an available next hop, carry and forward strategy will be used as a repairing strategy. As is shown in Figure 9, node A will forward the packet to node B, which is the farthest neighbor of A.

4.6.2. Intersection Mode

If a data packet travels at an intersection; that is, a vehicle receives a data packet and finds itself at an intersection, then the CSR protocol goes into intersection mode. We call the vehicle that is in charge of selecting intersections and forwarding packets a coordinator. In this mode, the coordinator sends request to the intersection for notification message; the intersection then sends notification message which contains needed information to the coordinator. Then the coordinator will calculate cost of all the adjacent intersections; the intersection with the smallest cost will be selected as the next temporary destination, and then the vehicle node at the intersection forwards data packets to its neighbor which is on that segment; Figure 10 illustrates such a situation. Particularly, in order to avoid the occurrence of routing loop, CSR increases the cost of the current segment to a large degree. By this way, packets will not be forwarded back to the current segment again. Thus, issues of routing loop will be averted. How to select a proper segment? In the following part, we will describe our designed intersection selecting scheme, called MMC.

4.6.3. MMC (Minimum Mean Cost) Selecting Scheme

In Section 3 we have analyzed issues on network connectivity. In our analysis, we get a conclusion that when the average distance between two adjacent vehicles obeys exponential distribution according to the probability theory, the mean and deviation exponential distribution both equal $\xi ={\sum }_{i=\mathrm{1}}^M{\lambda }_i/v_i=\lambda {\sum }_{i=\mathrm{1}}^M{p}_i/v_i$ . Now we consider such two aspects; (1) speed distribution has been ruled as normal distribution. (2) The SUM eliminates the individual variation of speed. Therefore we deem that a larger ξ corresponds to a larger λ. We have demonstrated that when other parameters remain constant, a larger λ leads to better network connectivity. Thus in our protocol, we design the cost function as follows:

$$\begin{array}{cc}& C_i=a\ast f\left(D_{i\text{dis}}\right)+\phi \left(\rho \right)\ast g\left(X_{i\text{avgdis}}\right),\end{array}$$

(13)

where $D_{i\text{dis}}$ indicates the distance from the middle of the $i_{\text{th}}$ segment to the destination and $X_{i\text{avgdis}}$ indicates the average distance of adjacent vehicles on the $i_{\text{th}}$ segment and it is calculated in the local coordinator. Particularly, $\phi \left(\rho \right)$ is a weight, which is a function of ρ (traffic density). ρ is also obtained by the intersection infrastructure. Further, by letting the $\phi \left(\rho \right)$ monotonously decrease against ρ, we can flexibly and properly adjust the weight. Figure 8 reflects such a special situation. Though the average adjacent vehicle distance in R2 is lower than that of R1, the traffic density is too low in R2. If packets are forwarded to this R2, intermittent connectivity will happen and data packets will not be delivered successfully.

Figure 8

Special situation.

Figure 9

Illustration of segment mode.

Figure 10

Illustration of intersection mode.

In contrast, R1 has a relatively better network condition. In such a special situation, vehicle density becomes a factor that cannot be neglected. CSR protocol considers this certain situation and can flexibly suit for it.

4.6.4. Routing Error Recovery Strategy

CSR carries out greedy forward strategy in road segment. When packets reach an intersection, CSR goes into intersection mode. By using MMC scheme, the forwarder (coordinator) selects a minimum-cost segment and packet.

There are some probabilities that CSR may be stuck into bad conditions and encounter routing error.

First, though CSR chooses a relatively better connected segment, it is inevitable that first, on the fly of packets on road segments, a gap between two vehicles may occur, and when the gap is as big as the transmission range, the current vehicle will lose the available next hop. Second, when packets arrive at the intersection, cost of each road segment will be calculated and packets will be forwarded to one direction. However, the MMC scheme just selects thus a road segment without considering whether the vehicles on the selected road segment are within the forwarder's transmission range. The above two cases result in routing error. To deal with the routing error, CSR takes the following measures as recovery strategy.

(1) Improved Carry and Forward Scheme. Improved carry and forward is based on time out algorithm. For a vehicle moving on the road segment, while having no available next hop, it will carry out the carry and forward strategy once receiving a packet (as a forwarder). In this scheme, the current vehicle stores the message and sets a timer T. At the same time, the current vehicle continues to receive and store packets. By periodically checking whether it finds a neighbor in the transmission range, the current vehicle finally either gets a chance to transmit or drops packets when time is out. To reduce extra overhead, CSR does not carry out broadcast announcement when this algorithm is over. Of course, to some extent, it is at the risk that more packets continue to arrive to this vehicle and get stuck.

(2) Suboptimal Segment Algorithm. To deal with the second error condition, there are two solutions. A simple and easy solution is selecting a second least cost segment. If packets still cannot enter the selected segment, carry and forward strategy will be adopted. Thus the forwarding vehicle goes into segment mode.

On the whole, CSR is different from those routing protocols which require each vehicle to use special beacons to record intersections and estimation of road state. That is, CSR utilizes a centralized message distribution mechanism (supported by the intersection infrastructure) to obtain road state information. Compared with a complete decentralized mechanism, to a certain extent, this kind of mechanism reduces collision in V2V communication.

5. Performance Evaluation

Typically, as previously mentioned, GPCR and GyTAR are both effective and widely-used VANET routing for urban scenario. Considering that CSR is designed for urban scenario, therefore, in this article, we compare the performance of CSR with GPCR and GyTAR to demonstrate the ability of CSR to accomplish good performance. The simulation configuration is presented in Table 2.

Table 2

Simulation configuration.

Simulation parameter	Configuration
Traffic model	10 CBR connection
Queue strategy	FIFO
Data packet size	512 bytes
Data traffic generation interval	2 s
Transmission speed	10 kbps
Beacon message interval	0.5 s
Mobility model	IDM-IM
Vehicle velocity	0~20 m/s
Transmission range	150 m
Intersection number	10
Road number	24
Map size	2500 ∗ 1500 m2
MAC mechanism	802.11p
PHY mechanism	Two-ray ground reflection
Simulation time	150 s

5.1. End-to-End Delay

Figures 11 and 12 evaluate the end-to-end delay performance. Since carry and forward strategy leads to uncontrolled end-to-end delay, we did not evaluate end-to-end delay performance of the protocols with this strategy. Generally, the end-to-end delay takes a rising trend as the traffic density increases. That is, because more vehicle nodes lead to more collisions in mac layer, packets will be retransmitted and queuing length increases. When vehicle speed rises, end-to-end delay nearly stays the same. CSR protocol also improves the performance of end-to-end delay. It is observed that when the vehicle number is 60, for GyTAR, the end-to-end delay is 48.9 ms; in contrast, for CSR protocol, the delay decreases to 28.48 ms.

Figure 11

End-to-end delay versus number of nodes.

Figure 12

End-to-end delay versus vehicle speed.

5.2. Packet Delivery Ratio

In Figure 13, we evaluate the delivery ratio of the three protocols. In general, the delivery ratio increases as the number of vehicles increases. The GPCR performs worst among these protocols, because the next intersection is chosen without considering any road state information in GPCR. GyTAR is better than GPCR since it takes the traffic density into consideration. The proposed protocol performs best with our intersection selection scheme. Furthermore, Figure 14 depicts the performance of the packet delivery ratio verifying with the vehicle speed. The number of nodes is set to 60. We observe that the delivery ratio of our protocol is nearly 8% higher than GyTAR. Moreover, when the recovery strategy is adopted, the packet delivery ratio almost increases by 10%.

Figure 13

Delivery ratio versus number of nodes.

Figure 14

Delivery ratio versus vehicle speed.

5.3. Network Throughput

Figure 15 compares the performance of network throughput. CSR achieves 1.5–2 kbps higher network throughput than GPCR and 0.5–1.5 kbps higher than GyTAR. When the transmission speed is 10 kbps, CSR nearly increases throughput by 10%–20% of the transmission capability.

Figure 15

Network throughput versus number of nodes.

5.4. Routing Efficiency

Routing efficiency is defined as the total number of packets sent into the network for every successfully delivered data packet. In other words, it is the ratio of the total number of sent packets (including beacon and data messages) over the total number of successfully received data packets. Following this definition, a higher curve in the figure indicates a higher routing overhead. The beacon packets make up the majority of the routing overhead because every node sends beacon messages periodically, for example, 0.5 s. Thus, it will greatly influence the routing efficiency. When the number of vehicles increases, the network connectivity gets better, and more packets will be delivered to the destination. As a result, the overall routing overhead decreases. As the number of vehicles keeps increasing, the delivery ratio begins to drop. Thus, the curve slightly rises, just as shown in Figure 16. In our simulations, the beacon frequencies for all protocols are the same. The total number of sent packets per successfully received data packet in CSR is 2.3%–3.6% higher than that in GyTAR, which indicates that CSR has a relatively higher routing overhead than GyTAR. That is, CSR achieves higher throughput at the cost of a moderately increase routing overhead.

Figure 16

Routing efficiency versus number of nodes.

6. Conclusion and Future Work

Many researchers study the network connectivity in VANETs, but few of them utilize the results to design protocols. We believe that network connectivity is a significant guidance to improve the routing protocol. Driven by the need for improving reliability of information transmission in urban VANETs, we present a stochastic analysis model to analyze the connectivity. The results unveil the fact that average distance of adjacent vehicles is a key factor impacting the connectivity. The proposed CSR protocol takes the network connectivity into consideration with the assistance of intersection infrastructure. Simulation results demonstrate that CSR achieves nearly 50% lower end-to-end delay and nearly 20% higher delivery ratio than traditional intersection-based routing protocols. Besides, CSR obtains 20–30% higher throughput at the cost of a moderately higher routing overhead. Further, when the number of vehicles increases, overhead of CSR tends to decrease to an acceptable level. CSR can be effective for transportation system where promptness is highly needed.

As future work, we will use an improved model which contains bidirectional road and channel fading in physical layer to obtain a more comprehensive result; further, new communication architecture in the 5G will be considered to be introduced to CSR to optimize the information collection process.