1 Introduction

As a special class of Mobile Ad hoc Networks (MAN-ET), VANET [1] displays several specific characteristics [2]. Firstly, the vehicles in VANET are required to move following the road layouts and traffic rules, which make their movements somehow predictable. Secondly, there are frequent network topology changes in VANET environments due to various vehicle densities and speeds in different time frames (rush hours or midnight) and diverse scenarios (remote countries or urban centers). Thirdly, VANET does not require strict power constraints, because vehicles can provide continuous energy by their onboard high-capacity batteries. In addition, VANET supports two kinds of wireless communications: inter-vehicle communications and vehicle-to-RSU (Road Side Unit) communications, which can be extensively applied in road safety, traffic management and driver assistance applications.

Although remarkable advancements in VANET fields have been achieved, there are still a lot of challenges to be addressed, such as scalability, bandwidth limitation, security and privacy, etc. In this paper, we mainly focus on the network routing problems. VANET routing protocols can be classified into different categories which mainly include: topology-based and geographic-based routing protocols. Topology-based routing protocols (for example, TORA [3]) lead to frequent broken links because of rapid topology changes in VANET. Geographic-based routing protocols [4–6] do not need to maintain the complete routing tables, and just utilize the geographic position of neighboring nodes to determine the next forwarding node. Compared to topology-based routing, geographic-based routing has been proved more scalable and efficient for the highly dynamic environments [7, 8]. Nevertheless, the geographic-based routing protocols for VANET still meet various challenges and limitations. GPSR [9] frequently suffers from local optimums and the recovery strategies may not work in urban scenarios due to radio obstacles and high vehicle speed, etc. GSR [10] neglects the traffic information along the route and may suffer from the network partition problems in sparse networks. MMDV [11] and VADD [12] try to alleviate above problems by using historical data, which may miss the accuracy in varying traffic environments.

Based on above discussion and analysis, we propose a new routing protocol IRQV. In this paper, we regard the dynamic route selection with best QoS as an optimization problem, and make use of ACO algorithm to solve this NP (nondeterministic polynomial) problem. Firstly, based on the communicating pairs’ moving direction and the distance to corresponding neighboring intersections, IRQV determines the terminal intersection (TI). Then, utilizing global QoS and derived local QoS, several forward ants are sent to explore available routing paths between two TIs, while backward ants are used to update global QoS and select the optimal route. In the data packets forwarding session, IRQV dynamically chooses the best next intersection for data packets, and when forwarded between two adjacent intersections, data packets make use of a simple but efficient greedy carry-and-forward mechanism [8], which can reduce the effects of individual vehicle movement on routing paths.

Compared with other RREQ-RREP-based (Route Request-Route Reply) or intersection-based routing protocols, our main contributions in IRQV are as follows:

  1. (1)

    The intersection-based routing paths IRQV explores are between terminal intersections instead of end-to-end vehicle communicating pairs. Obviously, the complete routing paths between vehicles are not required to be maintained, as well as different communicating pairs with the same terminal intersections can benefit from already explored paths and directly implement data forwarding. This mechanism can significantly increase the routing paths stability, alleviate link failure effects, reduce redundant routing exploration and relieve channel congestions especially in heavy traffic scenarios.

  2. (2)

    Forward ants of IRQV are sent opportunistically based on local and global QoS rather than blind flooding. This method can shorten network exploration time, decrease instant traffic information effects and avoid network congestion.

  3. (3)

    IRQV makes use of ACO algorithm, so that different communicating pairs can collaborate closely to update latest routing information for communication path segments. As a result, IRQV is better in adaptively choosing routing paths, coping with rapid topology changes and solving large-scale urban scenario challenges.

  4. (4)

    We propose connectivity and transmission delay models of two-lane road segments to estimate local QoS. Compared with historical traffic information and real-time performance parameters obtained by periodic hello packets, our method can decrease operation time, alleviate network congestion and improve QoS accuracy.

The rest of this paper is organized as follows. We introduce the related works in Section 2. Our proposed IRQV routing protocol is described in Section 3. In Section 4, we derive the local connectivity probability and delay models for a two-lane road segment. Section 5 presents the simulation environment and discusses the obtained results. Finally, Section 6 concludes the paper.

2 Related works

In this section, we focus on some reference routing protocols suitable for VANET in urban environments.

GSR [10] is a source-driven and intersection-based routing protocol. Based on a digital map, it calculates the shortest path to the destination vehicles by Dijkstra Algorithm. This shortest routing path consists of a list of successive intersections through which the data packets have to pass to reach the destination vehicles, and the data packets are relayed between two successive intersections using a simple greedy forwarding mechanism. However, as GSR does not take into account the traffic information along the selected path, the data packets forwarding suffers from network partitions and/or congestions.

CAR [13] is a position-based connectivity-aware routing protocol designed specially for inter-vehicle communications in the urban scenarios. When requiring an available routing path to the destination, the source initiates a path discovery process by broadcasting a exploring message, and this message records the velocity vector of the mobile nodes through which it goes. If the velocity vector direction of the current node is different from that of the previous forwarding node, these two nodes are regarded as an anchor pair and are added to the header of the message. When a broadcast message reaches the destination earliest, its passing route is regarded as the available routing path, which is established as a set of intermediate anchor pairs. Obviously, CAR is source-initiated routing and has to keep a complete routing path, which can not cope with the rapid topology changes of VANET, especially in the large-scale urban scenarios. Besides, the broadcasting feature of routing discovery increases redundant overheads and exacerbates network congestions.

Gytar [14] only relies on the local traffic information to dynamically relay data packets but neglects the global traffic quality, so Gytar may come up against extreme network conditions (for example, higher traffic load, massive network holes and so on) in the upcoming data forwarding processes. Obviously, an efficient routing also need to make use of global rather than only local routing information to dynamically and adaptively choose optimal routing paths in large-scale urban scenarios.

SADV [16] utilizes static nodes at road intersections to assist in data packets relaying, so the data packets can then be buffered for a while in the static nodes until a suitable vehicle is available along the best delivery path. Nevertheless, the real-time delay between two adjacent intersections is updated by periodic hello messages, which may exacerbate network congestions, especially in urban environments.

Ant Colony Optimization (ACO) [15] is a powerful optimization algorithm derived from foraging behaviors of ant species in real life. ACO has been successfully applied to a number of different combinatorial optimization problems such as traveling salesman. Because of the scalability, adaptation and parallelism of ACO, this optimization algorithm can also be applied to VANET routing problems [18, 19]. IDRA [17] is an intersection-based routing protocol using ACO, and it establishes the optimal route in an urban environment based on the deduced mathematical delay model. Based on ACO, VACO [18] searches the optimal QoS route in an urban scenario, but the local QoS between neighboring intersections is obtained by periodic hello packets, which increase the network congestions and degrade the final communication performance.

Obviously, many routing protocols suffer from inaccurate traffic information (such as historical data or instant real-time information), redundant overhead and high routing exploration time, especially in urban environments. To provide a solution to the aforementioned problems, we propose a new QoS-based routing protocol called IRQV.

Figure 1 illustrates the concept of IRQV. When the source vehicle S initiates data transmission to the destination vehicle D, the terminal intersections (I 1 is S’s terminal intersection T I S and I 4 is D’s terminal intersection T I D ) are firstly selected. Then, IRQV explores the available routing paths from I 1 to I 4 rather than S and D. The explored paths (consisting of a succession of intersections, and shown by the bold dashed lines) are discovered by several forward ants according to the local and global pheromone, which can reduce the opportunity of exploring the routes with the network partitions (I 12→I 11) or heavy channel congestions (I 8→I 9). Backward ants take charge of updating global pheromone and selecting the optimal route, which is the one with the highest global pheromone value (for example, I 1→I 6→I 7→I 8→I 5→I 4). Whereafter, utilizing the updated global pheromone, data packets forwarding between S and D (indicated by the black-arrow-line) is implemented. IRQV uses greedy carry-and-forward algorithm to relay data packets between I 1 and I 6, and when arriving at I 6, data packets are dynamically forwarded to next intersection (I 7 or I 5) based on the latest global pheromone, which may have been updated meanwhile by other the communicating pairs, such as S 2 and D 2.

Fig. 1
figure 1

IRQV routing example

Full size image

3 IRQV routing algorithm

In this section, we describe the IRQV routing algorithm, which is a dynamic intersection-based routing protocol. The objective of IRQV is to find the optimal route with highest QoS, which is evaluated by the combination of two QoS performance parameters namely: connectivity probability and transmission delay (these two parameters are deduced in Section 4). Because ACO algorithm is skilled in addressing such combinatorial nonlinear optimization problem in complex and dynamic systems, IRQV makes use of it to explore the optimal routing path. IRQV mainly consists of three parts: the terminal intersection selection process (TISP), the network exploration process (NEP) and the optimal route selection process (ORSP). In this paper, we assume that each vehicle is equipped with GPS facility, digital map and navigation system, which can help the vehicles find their own geographical position, get traffic information and identify the intersections position. In addition, we assume that each vehicle has access to a location service which can provide the geographical location of the destination. Moreover, a Static Node (SN, such as a Wi-Fi access point) is installed on each intersection to be in charge of relaying packets and storing routing information.

3.1 Terminal intersection selection process

In order to decrease redundant routing explorations, IRQV explores the available routes between two terminal intersections instead of end-to-end communicating pairs. As a consequence, when located on the same or neighboring road segments, different communicating pairs can share the same bone-route (composed of intersections).

We define the source vehicle S or the destination vehicle D as the communicating terminal (CT). In this paper, the moving direction of CT and the distance between CT and its neighboring intersection are used to determine the terminal intersection. A grade is allocated to each candidate intersection i and the one owning the highest grade is regarded as the terminal intersection. The grade expression is given as follows

$$ G\left( i \right) = \chi \cdot \left( {1 - \frac{{d\left( i \right)}}{L}} \right) + \left( {1 - \chi } \right) \cdot Dir\left( i \right) $$
(1)

where L is the current road segment length, \(d\left (i\right )\) means the distance from CT to i, χ denotes a weight parameter (0<χ<1), and \(Dir\left (i\right )\) stands for the CT’s moving direction value, which is given as

$$\begin{array}{@{}rcl@{}} \raggedleft Dir\left( i \right) = \left\{ {\begin{array}{ll} 1&{{\textrm{if CT moves towards }}i}\\ 0&{{\text{otherwise}}} \end{array}} \right. \end{array} $$
(2)

3.2 Network exploration process

Once the terminal intersections T I S and T I D are identified for S and D, respectively, S firstly sends a route request packet to T I S to check whether there is available routing information towards T I D . If the routing information exists at T I S and it is not out of date, T I S replies a positive message to S, and then S directly initiates data packets forwarding sessions. Otherwise, S starts to explore the optimal backbone routing path between T I S and T I D utilizing several forward ants.

Forward ants explore the network topology by recording the passing-through intersections’ IDs. When arriving at an intersection i, forward ant k chooses the next intersection j using certain probability \({P_{TI_{D}}^{k}}\left ({i,j} \right )\) based on the local and global QoS. This probability helps in avoiding upcoming road segments with extreme traffic conditions as well as keep the balance between the new routing paths exploration and the prior route exploitation. \({P_{TI_{D}}^{k}}\left ({i,j} \right )\) is expressed as follows

$$ {P_{TI_{D}}^{k}}\left( {i,j} \right) \,=\, \left\{ {\begin{array}{*{20}{l}} {\frac{{{{\left[ {\tau_{TI_{D}} \left( {i,j} \right)} \right]}^{\partial} } \cdot {{\left[ {\eta \left( {i,j} \right)} \right]}^{\beta} }}}{{\sum\limits_{u \in Nb(i)} {{{\left[ {\tau_{TI_{D}} \left( {i,u} \right)} \right]}^{\partial} } \cdot {{\left[ {\eta \left( {i,u} \right)} \right]}^{\beta} }} }}}&{{\textrm{if }}j \in Nb(i)} \\ 0&{{{otherwise}}} \end{array}} \right. $$
(3)

where \({P_{TI_{D}}^{k}}\left ({i,j} \right )\) denotes the probability with which the forward ant k (located at intersection i) chooses the next neighboring intersection j. \(Nb\left (i\right )\) depicts the set of neighboring intersections of i. ∂ and β are weight values. \(\tau _{TI_{D}} \left ({i,j} \right )\) (to be derived in Section 3.3) is the global pheromone that reflects the global QoS of a route from i to T I D when going through j. \(\eta \left ({i,j} \right )\) is the heuristic pheromone indicating the local QoS of the road segment between i and j, which can help forward ant k make use of the latest traffic information and explore new routing paths. \(\eta \left ({i,j} \right )\) is expressed as

$$ \eta \left( {i,j} \right) \!\!= \!\! \left( {1 \!\!- \!\! \varphi } \right){P_{c}}\left( {i,j} \right) \!\!+ \!\! \varphi \frac{{{D_{th}} \!\!- \!\! D\left( {i,j} \right)}}{{{D_{th}}}} \!\!\cdot \!\! \frac{1}{{\left( {1 \!\!+ \!\! Dv\left( {i,j} \right)} \right)}} $$
(4)

where \(D\left ({i,j} \right )\), \(Dv\left ({i,j} \right )\) and \({P_{c}}\left ({i,j} \right )\) denote the transmission delay, delay variance and connectivity probability of the road segment between i and j, respectively. φ is a weight value (0<φ<1). D t h stands for the transmission delay upper threshold, which is used to make the non-dimensional treatment for the quantitative transmission delay. In order to maintain the balance between these two parameters (delay and connectivity probability), we make \(Dv\left ({i,j}\right )\) add 1 to avoid the case of \(Dv\left ({i,j}\right )<1\), which may lead to \(\frac {{{D_{th}} - D\left ({i,j} \right )}}{{{D_{th}}}} \cdot \frac {1}{{Dv\left ({i,j} \right )}} > 1\) and hence decreases the fairness.

Obviously, compared with other blind flooding mechanisms, our network exploration method is beneficial to accelerate routing exploration processes and avoid routing paths with extreme network conditions.

3.3 Optimal route selection process

The optimal route selection process is in charge of updating the global pheromone to set up the optimal route. When forward ants arrive at T I D , the optimal route selection process is initiated.

Backward ants are generated by T I D and then are returned back (using unicast transmission) to S following the reverse paths of the corresponding forward ants. When arriving at the intersection i (coming from the intersection j), a backward ant firstly updates the global QoS from i to T I D . This global QoS can be regarded as the latest global pheromone \({\Delta } {\tau _{T{I_{D}}}}\left ({i,j} \right )\) released by the backward ant. The expression of \({\Delta } {\tau _{T{I_{D}}}}\left ({i,j} \right )\) is given as follows

$$\begin{array}{@{}rcl@{}} \begin{array}{*{20}{l}} {\Delta {\tau_{T{I_{D}}}}\left( {i,j} \right) = }&{\left( {1 - \varphi } \right) \cdot {P_{c}}_{T{I_{D}}}\left( {i,j} \right) + }\\ {}&{\varphi \cdot \frac{{{D_{th}} - {D_{T{I_{D}}}}\left( {i,j} \right)}}{{{D_{th}}}} \cdot \frac{1}{{1 + D{v_{T{I_{D}}}}\left( {i,j} \right)}}} \end{array} \end{array} $$
(5)

where \({{D_{T{I_{D}}}}\left ({i,j} \right )}\), \({D{v_{T{I_{D}}}}\left ({i,j} \right )}\) and \({{P_{c}}_{T{I_{D}}}\left ({i,j} \right )}\) denote the transmission delay, delay variance and connectivity probability of a route from the current intersection i to T I D , respectively, and this route includes the road segment between i and j. These three parameters are collected by the backward ants using the following equations

$$\begin{array}{@{}rcl@{}} \begin{array}{l} {D_{T{I_{D}}}}\left( {i,j} \right) \,=\, D\left( {i,j} \right) + D\left( {j,k} \right) + \cdot \cdot \cdot + D\left( {m,T{I_{D}}} \right)\\ {P_{cT{I_{D}}}}\left( {i,j} \right) \,=\, {P_{c}}\left( {i,j} \right) \cdot {P_{c}}\left( {j,k} \right) \cdot {{ }} \cdot \cdot \cdot {{ }} \cdot {P_{c}}\left( {m,T{I_{D}}} \right)\\ D{v_{T{I_{D}}}}\left( {i,j} \right) \,=\, \frac{{Dv\left( {i,j} \right) + Dv\left( {j,k} \right) + \cdot \cdot \cdot + Dv\left( {m,T{I_{D}}} \right)}}{J} \end{array} \end{array} $$
(6)

where i, j, k,⋅⋅⋅, m are the intermediate intersections that the backward ants pass through, J denotes the number of travelled road segments from i to T I D , \(D\left ({i,j} \right )\), \(Dv\left ({i,j} \right )\) and \({P_{c}}\left ({i,j} \right )\) stand for the transmission delay, delay variance and connectivity probability of the road segment between i and j, respectively, and these three local QoS parameters are derived in Section 4.

In order to avoid the exploration stagnancy of a routing path as well as alleviate the instant value’s effects, we make use of the historical pheromone value and the latest value \({\Delta } {\tau _{T{I_{D}}}}\left ({i,j} \right )\) to update the global pheromone \({\tau _{T{I_{D}}}}\left ({i,j} \right )\), which is expressed as

$$ {\tau_{T{I_{D}}}}\left( {i,j} \right) \leftarrow \left( {1 - {\delta }} \right) \cdot {\tau_{T{I_{D}}}}\left( {i,j} \right) + {\delta } \cdot {\Delta} {\tau_{T{I_{D}}}}\left( {i,j} \right) $$
(7)

where δ is a weight parameter (0<δ<1 ).

Once all backward ants arrive at the source, the route with the maximum value of global pheromone from T I S to T I D is selected as the optimal route.

3.4 Data packet forwarding and route maintenance

IRQV protocol implements two processes for data packets forwarding. When forwarded between two neighboring intersections, data packets make use of a greedy carry-and-forward mechanism, which can alleviate the effects of vehicle movements. When arriving at an intersection, data packets are dynamically forwarded to the next intersection according to the maximum global pheromone from current intersection to the terminal intersection of the destination. Note that this global pheromone can be updated by different communicating pairs, which can indicate their close collaboration and cope with the rapid topology changes in the VANET environments.

Finally, in order to cope with the topology changes and maintain the available routing paths, a new routing exploration

is implemented once the terminal intersections of the source and/or destination change. More formally, Algorithm 1 illustrates the IRQV protocol function.

figure a

4 Analytical local QoS models for road segment

In this section, we propose two local QoS models to express the connectivity probability and transmission delay of a road segment. These two models are used by IRQV (illustrated in Section 3) to derive the global QoS for the dynamic routing selections. Connectivity is a very important network metric, as it plays a key role in the improvement of packet delivery ratio and throughput. However, some full connectivity situations may lead to increased transmission delay, system complication and network congestion. Therefore, a second critical QoS performance parameter for vehicle routing selections is the transmission delay, which indirectly reflects current transmission channels loads, vehicles density and distribution, etc. Hence, in order to obtain accurate and complete local two-lane road segment QoS value, we make use of the combination of the connectivity probability and transmission delay performance parameters. Compared with the real-time QoS performance obtained by constant hello packets transmission between intersections, our method can alleviate channel congestion, save operation time and energy.

4.1 Assumptions

In this section, we clarify some design assumptions as follows.

  1. (1)

    We consider a straight two-lane road segment I i j with length L between two intersections i and j in a city scenario. The two road segment lanes go in opposite directions referred to as the Eastbound and Westbound.

  2. (2)

    We assume that the number of vehicles in the two-lane road segment scenarios follows Poisson Distribution, which has been proved in [20, 21] by Kolmogorov-Smirnov Test. In addition, the vehicle spacing density for the Eastbound lane and Westbound lane is set to λ 1 and λ 2, respectively, and the vehicle velocity for these two lanes is assumed constant and set to v 1 and v 2, respectively.

  3. (3)

    Our channel model is assumed as Rayleigh Fading Channel [22], which is an appropriate model for city radio environments due to the obstacles’ scattering. Beside, the propagation model is selected as Shadowing Model [23], and it is employed to characterize the probabilistic multiple path fading during the radio propagation.

4.2 Connectivity probability model

In a two-lane road segment scenario, the moving vehicles have transient contacts with the ones travelling in opposite direction. These opportunistic contacts can be used to improve connectivity. The connectivity of a road segment is maintained as long as the distance X between any two consecutive vehicles in a direction satisfies X≤R (where R denotes the communication range), or X>R but the vehicles travelling in the opposing direction can bridge this gap. Note that because of the channel fading’s influences and the propagation characteristics of the shadowing model, a packet can not be always transmitted successfully even if the distance between the transmitter and the receiver is less than R. Obviously, the successful packet transmission is totally different from the link connectivity in our models.

It is far difficult to derive an exact connectivity model for a two-lane road due to the complicated vehicle mobility and its continuous nature. In order to capture the connectivity characteristics, as shown in Fig. 2, we divide the road segment into several cells, and two cell size threshold values referred to as 0.5R and R are considered. In the case of cell size c s=0.5R, the maximum vehicles distance in two adjacent cells is R, which definitely guarantees the connectivity among them. When c s=R, the distance of vehicles in consecutive cells may vary within the range 0 and 2R due to the random vehicles location distribution, so the links may be connected or not. Obviously, the case of c s=0.5R is a sufficient but not necessary condition for connectivity. Conversely, the vehicles in adjacent cells are not guaranteed to be always connected when c s=R, which is a necessary but insufficient condition for connectivity.

Fig. 2
figure 2

Vehicle distribution example on a 2-lane road segment

Full size image

Based on above discussion, we set cell size c s=a⋅R (0.5≤a≤1), and let K be a random variable denoting the number of vehicles in an interval a⋅R. According to the assumption, K obviously follows Poisson Distribution and its Probability Mass Function (PMF) is given as

$$ P\left( {K = k} \right) = {{{{\left( {aR\lambda } \right)}^{k}} \cdot {e^{- aR\lambda }}} \mathord{\left/ {\vphantom {{{{\left( {aR\lambda } \right)}^{k}} \cdot {e^{- aR\lambda }}} k}} \right. \kern-\nulldelimiterspace} k}! $$
(8)

where λ denotes the vehicle spacing density on a road segment lane.

Since the distance between any two consecutive vehicles obeys the exponential distribution [20], the probability of a broken link between two vehicles separated by a distance X on the Eastbound lane is labelled as P b and derived as

$$ P_{b}={P\left( {X > R} \right) = {e^{- {\lambda_{1}}R}}} $$
(9)

where λ 1 means the vehicle spacing density on the Eastbound lane.

As shown in Fig. 2, two consecutive vehicles C i and C i+1 on the Eastbound lane are disconnected because of the distance between them x i >R. Making use of the vehicles on the Westbound lane, the broken link between C i and C i+1 can be repaired as long as there is at least one vehicle in each Westbound cell within x i . Obviously, the probability \({P_{f}}\left (i \right )\) that a broken link between C i and C i+1 can be fixable is expressed as

$$\begin{array}{@{}rcl@{}} {P_{f}}\left( i \right) = \left\{ {\begin{array}{*{20}{l}} 1&{{\textrm{if }}{x_{i}} \le R}\\ {{{\left( {1 - P\left( {K = 0} \right)} \right)}^{\left\lfloor {\frac{{{x_{i}}}}{{aR}}} \right\rfloor }}}&{{\textrm{if }}{x_{i}} > R} \end{array}} \right. \end{array} $$
(10)

where \(P\left ({K = 0} \right ) = {e^{- aR{\lambda }}}\) and λ=λ 2, which denotes the vehicle spacing density on the Westbound lane.

Let M be a variable that denotes the number of broken links on the Eastbound lane. Obviously, road segment I i j is is connected if M broken links are completely fixable. The conditional connectivity probability with M broken links \({P_{c|M}}\left ({M = m} \right )\) can be written as

$$\begin{array}{@{}rcl@{}} \begin{array}{ll} &{P_{c|M}}\left( {M = m} \right) = \prod\limits_{i = 1}^{m} {{P_{f}}\left( i \right)} \quad \;\;\;\forall m = 1,...,N - 1\\ &= {\left( {1 - {e^{- aR{\lambda_{2}}}}} \right)^{\sum\limits_{i = 1}^{m} {\left\lfloor {\frac{{{x_{i}}}}{{aR}}} \right\rfloor } }} = {\left( {1 - {e^{- aR{\lambda_{2}}}}} \right)^{\left( {\frac{L}{{aR}} - \frac{{N - 1 - m}}{{aR \cdot {\lambda_{1}}}}} \right)}} \end{array} \end{array} $$
(11)

where N stands for the number of vehicles on the Eastbound lane.

When M=m broken links exist among N−1 links on the Eastbound lane, the Probability Mass Function \({P_{M}}\left ({M = m} \right )\) follows a binomial distribution and is given as

$$ {P_{M}}\left( {M = m} \right) = \left( {\begin{array}{*{20}{c}} {N - 1}\\ m \end{array}} \right){p_{b}^{m}}{\left( {1 - {p_{b}}} \right)^{N - 1 - m}} $$
(12)

∀m=1,...,N−1.

Obviously, in the case of at least one broken link exists on the Eastbound lane (m≥1), the connectivity probability of the road segment is expressed as

$$ {P_{c1}} = \sum\limits_{m = 1}^{N - 1} {{P_{c|M}}\left( {M = m} \right)} \cdot {P_{M}}\left( {M = m} \right) $$
(13)

When there is no broken link on the Eastbound lane, i.e., all cells are occupied by at least one vehicle, the connectivity probability of the road segment can be given as

$$ {P_{c2}} = {\left( {1 - {e^{{\lambda_{1}}aR}}} \right)^{\left\lfloor {\frac{L}{{aR}}} \right\rfloor }} $$
(14)

According to above analysis, the total connectivity probability of a road segment between the intersection i and the intersection j is represented as follows

$$ {P_{c}}\left(i,j\right) = {P_{c1}} + {P_{c2}} $$
(15)

4.3 Transmission delay model

In this section, we derive the multi-hop transmission delay model for a given two-lane road segment. The road traffic statistics and moving vehicles time-series snapshots have demonstrated that vehicles tend to travel in clusters on road scenarios [24]. Obviously, a road segment may be fully connected or not in terms of the scale of the vehicles cluster. If the road segment is fully connected, data packets can be forwarded hop-by-hop, otherwise a forwarding vehicle has to carry the data packets to its neighboring vehicles. According to the discussion in Section 4.2, we divide the road segment into several cells and set cell size c s=a⋅R to investigate the road segment delay model. Our model considers two different cases: the road segment with network partitions (NP) and the road segment with full network connections (NC), which are illustrated in Fig. 3.

Fig. 3
figure 3

Road segment delay analysis model

Full size image

4.3.1 Road segment with network partitions (NP case)

In this case, the road segment is partly connected, as shown in Fig. 3a. An accurate delay model of a road segment is closely related to various network topologies, which are difficult to obtain due to the finite road segment length and complex vehicles movement. In order to derive an accurate road segment transmission delay model, we can expand a finite road segment into an infinite road, which can cover all kinds of network topologies, and then the road segment transmission delay D n p in NP case is deduced as follows

$$ {D_{np}} = L/E\left( {\bar v} \right) $$
(16)

where L denotes the road segment length and \(E\left ({\bar v} \right )\) is defined as the average data packets travelling speed on the road segment, and it will be estimated in Eq. 20.

With the assistance of vehicles on the Westbound lane, there are alternating periods of disconnection and connectivity on the Eastbound lane. In the disconnection phase (dp), data packets are carried by a forwarding vehicle on the Eastbound lane with vehicle speed v 1, until next neighboring vehicle to be connected. In the connection phase (cp), data packets are propagated at wireless transmission speed v 1h o p , which can be represented as follows

$$ {v_{1hop}} = a \cdot R/{t_{p}} $$
(17)

where a⋅R means the 1-hop length and t p indicates the 1-hop transmission delay, which can be deduced in [25]. According to the alternating renewal process theorem [26], the respective long-run probability of data transmission time spent in dp phase and cp phase is given as

$$\begin{array}{@{}rcl@{}} {P_{dp}} &= \frac{{E\left( {{T_{dp}}} \right)}}{{E\left( {{T_{dp}}} \right) + E\left( {{T_{cp}}} \right)}} = \frac{{{{E\left( {{d_{dp}}} \right)} \mathord{\left/ {\vphantom {{E\left( {{d_{dp}}} \right)} {{v_{1}}}}} \right. \kern-\nulldelimiterspace} {{v_{1}}}}}}{{{{E\left( {{d_{dp}}} \right)} \mathord{\left/ {\vphantom {{E\left( {{d_{dp}}} \right)} {{v_{1}}}}} \right. \kern-\nulldelimiterspace} {{v_{1}}}} + {{E\left( {{d_{cp}}} \right)} \mathord{\left/ {\vphantom {{E\left( {{d_{cp}}} \right)} {{v_{1hop}}}}} \right. \kern-\nulldelimiterspace} {{v_{1hop}}}}}} \\ &= \frac{{E\left( {{d_{dp}}} \right){v_{1hop}}}}{{E\left( {{d_{dp}}} \right){v_{1hop}} + E\left( {{d_{cp}}} \right){v_{1}}}} \end{array} $$
(18)
$$\begin{array}{@{}rcl@{}} {P_{cp}} &= \frac{{E\left( {{T_{cp}}} \right)}}{{E\left( {{T_{dp}}} \right) + E\left( {{T_{cp}}} \right)}} = \frac{{{{E\left( {{d_{cp}}} \right)} \mathord{\left/ {\vphantom {{E\left( {{d_{cp}}} \right)} {{v_{1hop}}}}} \right. \kern-\nulldelimiterspace} {{v_{1hop}}}}}}{{{{E\left( {{d_{dp}}} \right)} \mathord{\left/ {\vphantom {{E\left( {{d_{dp}}} \right)} {{v_{1}}}}} \right. \kern-\nulldelimiterspace} {{v_{1}}}} + {{E\left( {{d_{cp}}} \right)} \mathord{\left/ {\vphantom {{E\left( {{d_{cp}}} \right)} {{v_{1hop}}}}} \right. \kern-\nulldelimiterspace} {{v_{1hop}}}}}} \\ &= \frac{{E\left( {{d_{cp}}} \right){v_{1}}}}{{E\left( {{d_{dp}}} \right){v_{1hop}} + E\left( {{d_{cp}}} \right){v_{1}}}} \end{array} $$
(19)

where \(E\left ({{T_{dp}}} \right )\) and \(E\left ({{T_{cp}}} \right )\) denote data transmission time spent in corresponding dp phase and cp phase. In addition, \(E\left ({{d_{dp}}} \right )\) and \(E\left ({{d_{cp}}} \right )\) stand for data transmission distance in dp phase and cp phase, respectively. Substituting Eqs. 18 and 19, the average data packets transmission speed \(E\left ({\bar v} \right )\) can be obtained as follows

$$\begin{array}{@{}rcl@{}} \begin{array}{lll} E\left( {\bar v} \right) &= {v_{1}} \cdot {P_{dp}} + {v_{1hop}} \cdot {P_{cp}}\\ &= \frac{{\left( {E\left( {{d_{dp}}} \right) + E\left( {{d_{cp}}} \right)} \right) \cdot {v_{1}} \cdot {v_{1hop}}}}{{E\left( {{d_{dp}}} \right) \cdot {v_{1hop}} + E\left( {{d_{cp}}} \right) \cdot {v_{1}}}} \end{array} \end{array} $$
(20)

After substituting Eqs. 17 and 20 into Eq. 16, road segment transmission delay can be deduced as follows

$$\begin{array}{@{}rcl@{}} \begin{array}{lll} {D_{np}} = L \cdot \frac{{E\left( {{d_{dp}}} \right) \cdot aR + E\left( {{d_{cp}}} \right) \cdot {v_{1}} \cdot {t_{p}}}}{{\left( {E\left( {{d_{dp}}} \right) + E\left( {{d_{cp}}} \right)} \right){v_{1}} \cdot aR}} \end{array} \end{array} $$
(21)

Finally, as long as \(E\left ({{d_{dp}}} \right )\) and \(E\left ({{d_{cp}}} \right )\) are derived, road segment transmission delay in network partition case D n p can be obtained.

  1. (1)

    Disconnection phase (dp)

    In dp phase, as shown in Fig. 3a, the forwarding vehicle C k and the next consecutive vehicle C k+1 on the Eastbound lane are disconnected due to their distance x>R, so data packets are carried by vehicle C k until the connectivity between C k and cluster-2 is set up, this period is called dp phase of data packets transmission.

    Pattern matching problem [26] is to derive the expected number of trials until meeting consecutive successful results. It is analogous to our problem that investigates the number of cells traversed by C k until \(\left \lfloor {\frac {x}{{aR}}} \right \rfloor \) consecutive cells along the Westbound lane are linked (implying that there is at least one vehicle in each cell). Making use of pattern matching rules, the number of cells n traversed by C k is given as

    $$ E\left( n \right) = \left( {\frac{{1 - {p_{a}}^{x/\left( {aR} \right)}}}{{\left( {1 - {p_{a}}} \right){p_{a}}^{x/\left( {aR} \right)}}} - \frac{x}{{aR}}} \right)\frac{{{v_{1}}}}{{{v_{1}} + {v_{2}}}} $$
    (22)

    where p a =1−e −λ2aR denotes the probability that each cell has at least one vehicle on the Westbound lane.

    Note that the factor \(\frac {{{v_{1}}}}{{{v_{1}} + {v_{2}}}}\) is introduced because the vehicle C k and Cluster-2 move in the opposite direction with v 1 and v 2, respectively, and the number of cells required for C k is consequently reduced.

    We know that the link between C k and C k+1 is broken if at least one cell on the Westbound lane is vacant along the gap x (x>R). The disconnection probability between C k and C k+1 with distance X is given as follows

    $$\begin{array}{@{}rcl@{}} P\left( {{{\bar C}}|X = x} \right) = \left\{ {\begin{array}{*{20}{l}} 0\\ {1 - {p_{a}}^{\left\lfloor {x/aR} \right\rfloor }} \end{array}} \right.\begin{array}{*{20}{c}} {{\textrm{if }}x \le R}\\ {{\textrm{if }}x > R} \end{array} \end{array} $$
    (23)

    Due to the probability density function of the vehicles on the Eastbound lane \({f_{X}}\left (x \right ) = {\lambda _{1}}{e^{- {\lambda _{1}}x}}\), the disconnection probability is expressed as

    $$\begin{array}{@{}rcl@{}} \begin{array}{lll} P\left( {\bar C} \right) &= {\int}_{0}^{\infty} {P\left( {{{\bar C}}|X = x} \right)} \cdot {f_{X}}\left( x \right)dx\\ &= {e^{- {\lambda_{1}}R}} - \frac{{{\lambda_{1}}aR{e^{- {\lambda_{1}}R}}{p_{a}}^{1/a}}}{{{\lambda_{1}}aR - \ln \left( {{p_{a}}} \right)}} \end{array} \end{array} $$
    (24)

    Based on above analysis, the average distance of data transmission in dp phase is given as

    $$\begin{array}{@{}rcl@{}} \begin{array}{lll} {E\left( {{d_{dp}}} \right) = {\int}_{0}^{\infty} {E\left( n \right) \cdot aR} \cdot \frac{{{f_{X}}\left( x \right)P\left( {\bar C|X = x} \right)}}{{P\left( {\bar C} \right)}}dx} \end{array} \end{array} $$
    (25)

    By substituting Eqs. 22, 23 and 24 into Eq. 25, we can deduce the final expression of the carrying distance in dp phase \(E\left ({{d_{dp}}} \right )\).

  2. (2)

    Connection phase (cp)

    In cp phase, vehicles are connected with each other and data packets are transmitted at the speed v 1h o p . The transmission distance in cp phase is composed of two parts. In the first part, consecutive eastbound nodes are connected if the distance between them is not more than R, or even if the distance is greater than R, each westbound cell within the gap is occupied by at least one vehicle, for example, cluster-1 shown in Fig. 3a. In the second part, if the gap in dp phase is repaired by the vehicles on the Westbound lane, the distance of gap x is also traversed by data packets at speed v 1h o p . For instance, as represented in Fig. 3a, with the movement of Cluster-1 and Cluster-2, the two vacant cells between C k and C k+1 will be occupied by the vehicles in Cluster-2, and data packets can then be forwarded hop by hop when going through these two cells.

In the case of the first part, the expected transmission distance between two consecutive vehicles on the Eastbound lane is given as

$$\begin{array}{@{}rcl@{}} \begin{array}{lll} E\left( {X|C} \right) &= {\int}_{0}^{\infty} x {f_{X}}\left( x \right)\frac{{P\left( {C|X =x} \right)}}{{P\left( C \right)}}dx \\ &= {\int}_{0}^{\infty} x {f_{X}}\left( x \right)\frac{{1 - P\left( {\overline C |X = x} \right)}}{{1 - P\left( {\overline C } \right)}}dx \end{array} \end{array} $$
(26)

By substituting Eqs. 23 and 24 into Eq. 26, we can deduce the final expression for \(E\left ({X|C} \right )\).

If y consecutive links on the Eastbound lane are connected, the transmission distance covered is \(y \cdot E\left ({X|C} \right )\), so the expected distance covered in the first part during cp phase \(E\left ({{d_{cp - part1}}} \right )\) is shown as follows

$$\begin{array}{@{}rcl@{}} &E\left( {{d_{cp-part1}}} \right) = \sum\limits_{y = 1}^{\infty} {y \cdot E\left( {X|C} \right)} P{\left( C \right)^{y}}\left( {1 - P\left( C \right)} \right)\\ &= E\left( {X|C} \right)\frac{{P\left( C \right)}}{{1 - P\left( C \right)}} = E\left( {X|C} \right)\frac{{1 - P\left( {\overline C } \right)}}{{P\left( {\overline C } \right)}} \end{array} $$
(27)

In the case of the second part, the average transmission distance equals the gap length between C k and C k+1 on the link disconnection condition. Based on the above analysis, the transmission distance is deduced as follows

$$\begin{array}{@{}rcl@{}} \begin{array}{lll} E\left( {{d_{cp-part2}}} \right) &= E\left( {X|\overline C } \right) \\ &= {\int}_{0}^{\infty} x {f_{X}}\left( x \right)\frac{{P\left( {\overline C |X = x} \right)}}{{P\left( {\overline C } \right)}}dx \end{array} \end{array} $$
(28)

Finally, in terms of the above investigation, the average distance of data transmission in cp phase is given as

$$\begin{array}{@{}rcl@{}} E\left( {{d_{cp}}} \right) = E\left( {{d_{cp - part1}}} \right) + E\left( {{d_{cp - part2}}} \right) \end{array} $$
(29)

When substituting Eq. 26, 27 and 28 into Eq. 29, we can get the full expression of \(E\left ({{d_{cp}}} \right )\). Then based on Eq. 25 and 29, road segment delay in NP case D n p can be deduced by Eq. 21.

4.3.2 Road segment with full network connections (NC case)

In this case, the links of the road segment are totally connected, and the packets can be forwarded from current intersection i to next intersection j using hop by hop greedy algorithm. As shown in Fig. 3b, the cluster length L c l ≥L. Consequently, the transmission delay between i and j in this case can be expressed as follows

$$ {D_{nc}} = {H_{nc}} \cdot {t_{p}} $$
(30)

where \({H_{nc}}= \left \lceil \frac {L}{a\cdot R}\right \rceil \) denotes the hop counts between i and j, and t p means the 1-hop transmission delay.

From the analysis in Sections 4.3.1 and 4.3.2, the average transmission delay between two intersections i and j is given as

$$ D\left(i,j\right) = {D_{np}} \cdot \left( {1 - {P_{c}}\left(i,j\right)} \right)+{D_{nc}} \cdot {P_{c}}\left(i,j\right) $$
(31)

where \(P_{c}\left (i,j\right )\) stands for the road segment connectivity probability (deduced in Eq. 15).

In addition, the transmission delay variance between two intersections i and j is expressed as

$$ Dv\left(i,j\right) \,=\, {D_{nc}}^{2} \cdot {P_{c}}\left(i,j\right) + {D_{np}}^{2} \cdot\left( {1 - {P_{c}}\left(i,j\right)} \right)- {D^{2}}\left(i,j\right) $$
(32)

Finally, using Eq. 4, road segment local QoS can be deduced by the above derived transmission delay, delay variance and connectivity probability.

5 Performance evaluation

In this section, using the network simulator NS-2, we firstly analyze and validate our proposed theoretical models for road segment connectivity and transmission delay, and then compare our routing protocol IRQV with two reference routing protocols: GSR [10] and CAR [13].

5.1 Experimental setup

The simulation scenario we consider is a 7000 m × 7000 m area, which consists of 60 intersections and 103 two-lane road segments. Based on Vehicular Ad Hoc Networks Mobility Simulator (VanetMobiSim [27]), we make use of Intelligent Driver Model with Intersection Management (IDM__IM) to generate the vehicles motion trace. Here we set the vehicle spacing density, vehicles safety time and recalculating movement step time as 0.01 ∼ 0.04 vehicles/m, 2 s and 0.5 s, respectively. Besides, the initial position and moving trip of moving nodes are selected randomly. Moreover, we utilize the IEEE 802.11p at the MAC layer, set the maximum channel transmission rate to 3 Mbps and make the communication range R equal 250 m. Finally, we randomly initiate 300 constant bit rate (CBR) sessions and set the data packet size to 512 Bytes. In our experiments, the simulation time duration is fixed to 6000 seconds and each simulation scenario is repeated 30 times with different seeds to guarantee good confidence intervals for the results. Other simulation parameters are listed in Table 1 and the road layout of the urban scenario is shown in Fig. 4.

Fig. 4
figure 4

Road layout in our vehicular simulation

Full size image
Table 1 Simulation parameters
Full size table

5.2 Road segment connectivity and transmission delay models validation

Figures 5 and Fig. 6 depict the road segment connectivity probability for different communication ranges, cell sizes and vehicle spacing densities. As we expected, these two figures show the corresponding upper and lower thresholds of the road segment connectivity when cell size cs equals R and 0.5R, respectively. When c s=0.7R, the theoretical results are in accordance with the simulation results (95% confidence interval (CI)). Moreover, when increasing the communication range and vehicle spacing density, the connectivity is improved due to the repairs of the road segment network partitions.

Fig. 5
figure 5

Connectivity for different communication ranges R

Full size image
Fig. 6
figure 6

Connectivity for different vehicle spacing densities λ

Full size image

Figure 7 describes the correlations among the road segment transmission delay, communication range and cell size. When c s=0.7R, the analytical and simulation results are in good agreement, and show a small difference of 3.02%. Because of the accuracy of our transmission delay and connectivity models when cell size parameter a=0.7, we set this value in the following simulations. In addition, we observe that when the communication range increases, the road segment transmission delay significantly decreases, as the road segment connectivity is enhanced and the data packets can be transmitted mainly using wireless communications.

Fig. 7
figure 7

Packet delay for different communication ranges R

Full size image

Figure 8 shows the road segment transmission delay as a function of the vehicle speed and road segment length. In this figure, the differences between analytical results and simulation results are only 2.96 % and 3.17 % for the curves with L=1000 m and L=1500 m, respectively. Besides, since we utilize simple greedy carry-and-forward to transmit data packets, when suffering from network partitions, data packets are carried by forwarding vehicles, and as the transmission delay mainly depends on the vehicle speed in this case, the transmission delay on the road segment decreases with the vehicle speed augmentation.

Fig. 8
figure 8

Packet delay for different vehicle speeds v

Full size image

In Fig. 9, the transmission delay on a road segment is given as a function of the vehicle spacing density and the channel transmission rate. We observe that the gap between the theoretical and the simulation results are only about 3.61 % and 2.75 % for the curves with the channel transmission rate 0.1 Mbps and 1 Mbps, respectively. In addition, the transmission delay dramatically decreases in the initial stage when the vehicle spacing density increases, because the wireless network partitions are repaired and more packets can be forwarded by wireless communications. However, higher vehicle spacing density impairs the packets transmission due to the severe channel interference and lower packet successful ratio. As a result, the packets are required to be retransmitted, which makes the transmission delay show a slight increase. Besides, higher channel transmission rate makes the packets be transmitted faster on the wireless channel, and it is beneficial to the delay decrease.

Fig. 9
figure 9

packet delay for different vehicle spacing densities λ

Full size image

According to the above investigations, when c s=0.7R, the difference between theoretical results and average simulation results is within ±4%, which proves the correctness of our proposed analytical models for the road segment performance. Besides, the aforementioned results and analyses confirm the effectiveness of the choice of the connectivity and transmission delay as important parameters to evaluate the QoS of a road segment.

5.3 Routing protocols performance evaluation

5.3.1 QoS weight value analysis

QoS weight value φ controls the balance between the connectivity probability and transmission delay when IRQV chooses available routing paths. Here we carry out simulations by varying φ value to study its influence on IRQV’s paths selection, and the results are indicated in Table 2. We observe that as φ value is increasing, average end-to-end transmission delay is decreasing. The reason is, when φ increases, the paths with lower delay are given more preferences. Obviously, our IRQV can be easily extended to a pure delay-sensitive routing protocol by fixing φ to 1. However, the selected paths with lower delay may show worse packet delivery ratio because of excessive vehicle density, so we set φ=0.5 for the following simulations to optimize the complete routing path performance.

Table 2 IRQV: End-to-end delay for various φ values
Full size table

5.3.2 Average packet delivery ratio analysis

From Fig. 10, we can see that IRQV achieves the highest packet delivery ratio compared with GSR and CAR. There are two main reasons to explain this outcome. Firstly, IRQV dynamically chooses the optimal routing path with the highest communicating QoS based on the connectivity and transmission delay, which make the selected path be with appropriate vehicle density and avoids extreme network congestion. Secondly, IRQV searches available routing paths utilizing ACO algorithm, which makes different communicating pairs cooperate with each other to update latest pheromone immediately and cope with rapid topology changes. However, CAR provides only one complete end-to-end routing path, which is far vulnerable in the VANET environments and causes higher packet loss. GSR only considers the distance to the destination but neglects other available routing information, so some data packets may be dropped when suffering from serious network congestions. This figure also indicates that all protocols experience higher packet delivery ratio with lower vehicle speed and vehicle spacing density. The reasons are as follows, 1) the increase of vehicle speed results in rapid network topology changes, which deteriorates the packet delivery ratio, 2) and when vehicle spacing density rises, network connectivity is better and data packets prefer to be transmitted by wireless communications, so compared with carried by vehicles, these data packets may suffer from more channel fading effects, which lead to worse packet delivery ratio.

Fig. 10
figure 10

End-to-end packet delivery ratio.

Full size image

5.3.3 End-to-end delay analysis

Figure 11 shows the transmission delay variance with vehicle speed of 25 m/s. It clearly represents that the delay variance in IRQV is smaller than the corresponding one for GSR and CAR, so the routing paths selected by IRQV are more stable. This is because, firstly, IRQV takes transmission delay variance into account in the processes of available routes explorations and selections, secondly, the optimal route of IRQV is confirmed on the basis of both local and global communication quality, which is conductive to maintain stable routes and alleviate data packets suffering from extreme traffic conditions, such as the extreme network partitions or heavy congestions.

Fig. 11
figure 11

End-to-end packet delay variance

Full size image

Figure 12 depicts the end-to-end average transmission delay as a function of vehicle density and vehicle speed. This figure shows that IRQV provides the lowest transmission delay compared with both reference routing protocols. By using ACO algorithm, IRQV makes different communicating pairs collaborate with each other to update latest global pheromone, which is profitable to adjust rapid network topology changes and reduce transmission delay. In the case of GSR, data packets are forwarded using the same path because of the shortest-distance path rule, which can not adapt rapid topology changes. CAR is a min-delay routing protocol but can not update routing information in time, so upcoming data packets may suffer from network partitions which result in higher transmission delays. Besides, as we expected, the transmission delay of all routing protocols is inversely proportional to the increase of vehicle spacing density especially in sparse network situations due to the repairs of network holes. Moreover, while vehicle speed rises, average transmission delay decreases because of the carry-and-forward relaying strategy.

Fig. 12
figure 12

End-to-end packet delay

Full size image

For a deeper investigation of the end-to-end delay components, we present them in Fig. 13 for IRQV routing protocol in different vehicle spacing density scenarios. The packet delay in IRQV consists of four parts: the delay of route establishment given by ants for per data packet, the carrying delay when a packet is carried by moving vehicles, the retransmission delay and the delay without retransmission. From this figure, we can see that the ratio of the carrying delay reduces with the increase of vehicle spacing density, while the wireless communication delay ratio (including the retransmission delay and the delay without retransmission) is proportional to the vehicle spacing density. The reason is that higher vehicle spacing density is beneficial to the network partition repairs, which make more data packets be transmitted hop by hop rather than carried by moving vehicles. In addition, the retransmission delay proportion rises with the increase of vehicle spacing density, because higher vehicle spacing density implies that there may be more severe neighboring vehicles’ interference, which exacerbates successful packets transmission and causes more retransmission times. Moreover, the proportion of the route establishment delay for per data packet is almost stable with various vehicle spacing densities and shows a small value.

Fig. 13
figure 13

End-to-end packet delay components of IRQV

Full size image

5.3.4 Overhead analysis

Figure 14 represents the network overhead as a function of vehicle density and vehicle speed. Note that for a fair comparison, we define the overhead as the ratio between the total control packets bytes and the cumulative bytes of successfully received data packets. Compared to CAR and GSR, IRQV shows lower overhead for various vehicle densities and speeds. Based on the latest global pheromone, IRQV protocol dynamically chooses optimal route to forward data packets, which can achieve better packet delivery ratio and thus reduce the overhead. Besides, IRQV makes use of terminal intersection concept to reduce redundant route explorations, which in return reduce the overhead. Figure 14 also indicates that overhead of all protocols increases for higher vehicle densities, because hello control packets occupy an important proportion of the whole overhead, and their number is mainly determined by vehicle spacing density. Furthermore, the three protocols experience higher overhead with the increase of vehicle speed, which can accelerate network topology changes, decline packet delivery ratio and require more control overhead packets for new routing explorations.

Fig. 14
figure 14

Overhead as a function of vehicle spacing density

Full size image

5.3.5 The influence of forward ants number analysis

In this simulation experiment, we set the vehicle spacing density as 0.03 vehicles/m. Here we make use of two parameters: the end-to-end connectivity probability and transmission delay (both of them are used by ants to search the optimal route) to evaluate the normalized QoS. From Table 3, we can see that the QoS is proportional to the forward ants number, because more ants can enhance IRQV’s global exploration ability and find more candidate routing paths, which are beneficial to the optimal route confirmation. However, since the rise of forward ants improves the randomness of routing exploration, the optimal route’s convergence rate is slower and the route establishment time for per communicating pair increases. In addition, when the number of forward ants rises from 35 to 350, the QoS gains a little improvement, but the overhead given by the ants for per successfully received bytes and the route establishment time deteriorate rapidly. Moreover, the QoS is stable when the forward ants number equals 300. Obviously, the number of forward ants plays an important role in the performance of IRQV, and in our previous experiments, we set the forward ants number to 15, which makes IRQV achieve a good balance between the QoS, route establishment time and overhead.

Table 3 The influences of forward ants number
Full size table

6 Conclusion

In this paper, a new intersection-based vehicular routing protocol called IRQV is proposed. We regard the issue of dynamic routing selection with best QoS as an optimization problem, and then utilize ACO algorithm to resolve it. On the basis of local road segment QoS (combination of deduced road segment connectivity probability and transmission delay) and global QoS between two terminal intersections, we utilize forward ants and backward ants to explore available candidate paths, update global pheromone at intersections and confirm optimal route. Data packets are dynamically forwarded to the next intersection according to the updated global pheromone, and greedy carry-and-forward algorithm is used to relay them between two neighboring intersections. The simulation results validate our deduced local road segment models for connectivity and delay, and also indicate that IRQV outperforms the reference protocols (GSR and CAR). As future work, we will further investigate the effects of IRQV weight parameters on the relaying quality of road segments, and also compare ACO performance to other optimization methods.