# Optimization of Maximum Routing Hop Count Parameter Based on Vehicle Density for VANET

Authors: Zhonghui Pei; Wei Chen; Hongjiang Zheng; Luyao Du
Journal: Mobile Information Systems
 (2020)

---

## Abstract

Vehicular Ad Hoc Network (VANET) is the basic technology of intelligent transportation systems for providing reliable and real-time communications between vehicles and vehicles or roadside units. In order to improve the communication quality of VANET, this paper studies the effects of different maximum routing hop count parameters on the performance of the network under different vehicle densities. We establish the mathematical models of node connectivity probability and the packet delivery ratio by using the Poisson distribution model. And the maximum routing hop count selection algorithm (MRHSA) is proposed based on the theoretical model established in the paper. The simulation experiments and statistical analysis on packet delivery ratio, throughput, and end-to-end delay are performed under the straight road and urban road scenes, supported by the Vehicle in Network Simulation (Veins). The results show that the maximum routing hop count parameter is an important impact factor on the communication quality of the network. It is found that MRSHA proposed in this paper can improve the packet delivery ratio by about 9.1% at most in straight road scenarios, which indicates that MRHSA will contribute to the improvement of the communication quality of VANET.


---

## Body

## 1. Introduction

In recent years, with the rapid development of Intelligent Transportation System (ITS) and unmanned driving technology, Vehicular Ad Hoc Network (VANET) has also received great attention as one of the key technologies [1–3]. VANET can realize real-time and reliable communication that allow vehicles to communicate with one another as well as the surrounding infrastructure (V2V/V2I for short).Due to the high-speed characteristics of vehicle nodes, the network topology of VANET is highly dynamic. Most routing technologies in traditional networks cannot guarantee good communication quality in such a highly dynamic network environment. Many routing schemes have been proposed for the high-dynamic characteristics of VANET and the network requirements in practical applications [4, 5]. According to the information required by routing technology, it can be divided into Topology-Based Routing, Position-Based Routing, Map-Based Routing, and Path-Based Routing. According to the transmission strategy, it can be divided into Unicast Routing Protocols, Multicast Routing Protocols, and Broadcast Routing Protocols [6].Among various routing protocols, the maximum routing hop count is one of the most important parameters, which is closely related to link connectivity, link reliability, and packet delivery ratio. And its importance is particularly prominent in a highly dynamic network environment like VANETs. At present, most research on VANET routing hop count is to optimize routing scheme to minimize routing hop count, maximize routing lifetime, or consider multiple communication performance metrics [7, 8]. However, they rarely study the selection of the maximum routing hop count parameter. The parameter setting of the maximum routing hop count limits the life cycle of the routing packet and determines the maximum number of relay nodes that the routing path passes through. It is worth noting that, even with an optimal routing path selection policy, the maximum routing hop count setting still has a greater impact on the network. Large values may excessively increase routing overhead and network congestion and reduce network packet delivery ratio and reliability. Small values will lead to a lower routing success rate, which will also reduce the packet delivery ratio and reliability of the network [9, 10].The objective of this paper is to propose an optimal maximum routing hop count parameter setting method based on vehicle density, which can provide higher packet delivery ratio and throughput for the Internet of Vehicles (IoV) communication. By establishing the model of node connectivity probability and packet delivery ratio of the maximum routing hop count and vehicle density, the paper analyzes the growth rate of node connectivity probability and the reduction rate of packet delivery ratio caused by the increase of the maximum routing hop count under different vehicle densities. And, on this basis, the algorithm is proposed to find the near-optimal maximum routing hop count according to different vehicle densities.The rest of the paper is organized as follows. Section2 discusses the related work in VANET routing protocols and vehicle density. In Section 3, we propose the node connectivity probability model and the packet delivery ratio model. Section 4 introduces the maximum routing hop count selection algorithm based vehicle density. Simulation results are showed and analyzed in Section 5. Finally, we conclude this paper and suggest future work in Section 6.


## 2. Related Work

Several traditional routing protocols in VANET come from Mobile Ad Hoc Network (MANET), including Ad Hoc On Demand Distance Vector (AODV) routing protocol based on network topology [11] and Greedy Perimeter Stateless Routing (GPSR) based on location information [12]. Reference [13] proposes a hybrid geographic routing protocol, which combines AODV and GPSR. The Geographic Source Routing (GSR) protocol calculates the forwarding path based on the location information of the vehicle on the map [14]. Vehicle-Assisted Data Delivery (VADD) uses predictable vehicle movement paths to calculate packet transmission delays and find the next route to forward packets [15]. It includes three different forwarding protocols: Location First Probe, Direction First Probe, and Hybrid-VADD.Generally, different routing protocols have their own routing hop selection schemes. The AODV routing protocol uses a path with the smallest number of routing hops from the optional routing path to forward, and VADD selects the forwarding path with the lowest latency. Nabil et al. [16] improved Location-Aided Routing (LAR) by using vehicle location information and driving directions and estimated hold time of neighboring vehicles to increase routing lifetime. References [17] proposes a method called Long Lifetime Anypaths (LLA) to provide stable communication paths. It adds a stability index to anypath routing and selects neighboring vehicles with relatively stable distance for forwarding. In [18], robustness is defined as a qualitative QoS parameter of communication links that depends on link lifetime and error rate over the link. Modeling and quantification of link-robustness and route-robustness are carried out in that paper by synthesizing temporal, spatial, and environmental dependencies of the network. And, based on this, a routing selection strategy is proposed. However, from the studies above, we can find that the optimal setting of maximum routing hop count is not considered in the routing process.The density of nodes can make an important impact not only on traditional ad hoc networks but also on VANETs. A great number of studies have been conducted on the relationship between network connectivity and vehicle density [19–22]. Generally speaking, in the environment of high vehicle density, the connectivity probability between nodes is higher with a high network congestion probability. Conversely, the probability of network congestion is lower when the vehicle density is lower, but the connectivity probability between nodes also decreases [23, 24].Historical or real-time acquired vehicle density for routing strategy optimization is also used in some research. Reference [9] proposed Adaptive Connectivity Aware Routing (ACAR) protocol, using historical statistical vehicle density and real-time acquired vehicle density information to optimize the routing strategy to minimize the packet error ratio. An Intelligent Routing Protocol Using Real-Time Traffic Information in Urban Vehicular Environment (IRTIV) is proposed in [25]. It collects real-time traffic density through periodic Hello messages and calculates the weight of the road segment based on traffic density and Dijkstra algorithm and then selects the shortest transmission path with sufficient vehicle connection. However, it is difficult to find a forwarding path when traffic density is low. Wang et al. [26] proposed a Software-Defined Cognitive Routing (SDCoR) for Internet of Vehicles, which uses the software-defined network and reinforcement learning to perceive the environment (the environmental parameters of vehicle density and speed are mainly used in this paper) and designed the Q-learning based Cognitive Routing (QCR) algorithm to choose different routing strategy according to different environments.Compared with the incremental fixed value of AODV and the fixed value of GPSR and VADD, based on the study of routing hops and vehicle density in the existing literature, this paper proposes dynamically adjusting the parameters of the maximum routing hop count of each communication node according to vehicle density. A more detailed comparison is shown in Table1.Table 1
Novel contributions.
Routing protocolMethod to set the maximum routing hop countFor each nodeAODVIncrement from initial value to fixed maximum valueThe same maximum fixed valueGPSRFixed valueThe same valueVADDFixed valueThe same valueNovel contributionsDynamic adjustment according to vehicle densityDepending on vehicle density


## 3. System Model

This section first introduces the multihop VANET system architecture and then establishes the theoretical models of node connection probability and packet delivery ratio.


### 3.1. Multihop VANET System

VANET is a high-dynamic large-scale network, including communication vehicles and roadside units (RSU). The communication modes include V2V and V2I. At present, most of the communication standards of VANET are single-hop communication. While simplifying the network topology, it also reduces the utilization of network resources and increases the cost of network construction. Multihop communication is an inevitable trend of VANET development. The multihop VANET system architecture is shown in Figure1, in which the roadside units can be regarded as small communication base stations and the vehicles can be regarded as a large number of mobile communication terminals.Figure 1
Multihop VANET system architecture.The advantages of multihop communication in VANET are reflected in two aspects. One is for V2I communication, and the other is for V2V communication. For the layout of RSU, if only single-hop communication is allowed, its layout density is required to be high. The two RSUs must be seamlessly connected to ensure that all vehicles are covered by the communication range of RSUs. However, if multihop communication is allowed, the layout density of the RSU can be relatively reduced. For example, theVA in Figure 1 is not within the communication range of RSU1 but can communicate with RSU1 through communication between VA and VE. On the other hand, for V2V communication, if the destination node is not within the communication range of the source node, single-hop communication cannot be completed, but multihop communication is possible.The setting of the maximum routing hop count parameter is of great significance in multihop VANET. Larger value usually increases the probability of connection between vehicle nodes, but it also increases the routing overhead and packet collision probability of the network. For example, in Figure1, the source node VS needs to establish a communication link with the destination node VD. If the maximum routing hop count parameter is set to 1, the communication link cannot be established between the two nodes because the distance x between the two nodes is greater than the node communication distance R. When the maximum routing hop count parameter is set to 2, a possible communication link VS ⟶ VA ⟶ VD can be established. When it is set to 3, four possible communication links can be established, one of which is 2-hop communication: VS ⟶ VA ⟶ VD, and the other 3 possible communication links are 3-hop communication: VS ⟶ VA ⟶ VC ⟶ VD, VS ⟶ VB ⟶ VA ⟶ VD, and VS ⟶ VB ⟶ VC ⟶ VD. It can be seen intuitively that the appropriate value of the maximum routing hop count can increase the possibility of establishing a communication link. But this usually also increases the possibility of data packet collisions because large routing hops mean that more data packets will be transmitted in the network. Therefore, we can increase the connection probability of the communication link by setting an appropriate maximum route hop value on the basis of not increasing network conflicts as much as possible; that is, find the balance between the connection probability and the collision probability.


### 3.2. Node Connectivity Probability Model

Firstly, consider the relationships between node connectivity probability and maximum routing hop count (and vehicle density) in special scenarios. As shown in Figure2, in a straight road with a length of L, the distance between the source node V0 and the destination node Vn is x, and the vehicle communication model is set to a Unit-disk model with a communication range of R, where R < x < 2R.Figure 2
Vehicle connectivity coordinates.A Cartesian coordinate system is established with the source nodeV0 as the coordinate origin. Since the road width is short compared to the vehicle communication distance, the influence of the road width is ignored here.According to the Unit-disk model, assuming that the communication radius of the vehicle isR, communication can be established as long as the distance between the two vehicles is less than R. The probability that communication can be established between two nodes can be expressed as(1)gd=1,d≤R,0,d>R,where d is the distance between the two nodes.For the convenience of analysis, it is assumed that the traffic flow distribution is subject to a Poisson distribution with a vehicle density ofλ vehicles/kilometer [27]. Then the probability that there are k vehicles distributed on the road with length x is(2)fk,x=λxkexp−λxk!,k>0,e−λx,k=0.According to the Poisson distribution model, there areλL vehicles in the section with length L, and there are λx vehicles between the source node and the destination node. Let K(R) be the number of vehicles located on the section with length R; then the probability of having at least one vehicle in R range is(3)PKR>0=1−PKR=0=1−e−λR.The vehicles in Figure2 are numbered V0 to Vn from left to right. Vi represents the ith vehicle node. Let the distance between neighbor nodes in the communication link be di; then di = Vi − Vi−1; that is, the distance between the ith vehicle and the (i − 1)th vehicle is di. Among the vehicles V0 to Vn, di is greater than R only when there is no vehicle node in the section of length R. Therefore, according to (2), Pdi>R=e−λR. To ensure that the neighbor nodes can communicate, di < R is required, that is, at least one vehicle in the length R section. The probability of di < R is(4)Pdi<R=1−Pdi>R=1−e−λR.Leth be the routing hop count of communication link and let fh=i be the connectivity probability between the source node V0 and destination node Vn when the routing hop count equals i and let xi be the coordinate position of the relay node of the ith hop (the distance between the node of the ith hop and V0), and xi < x, as shown in Figure 2. Then we can get(5)fh=1=0,fh=2=1−e−λ2R−x,fh=3=1−e−λR1−e−λ2R−x+x1,…fh=i=1−e−λRi−21−e−λ2R−x+xi−2.Similarly, the connectivity probability in the general scenario can be obtained as follows.Whenx/R<1(6)fh=i=1,i=1,1−e−λx+∑j=1i−1λxjexp−λxj!,i>1.Whenx/R>1(7)fh=i=0,i<xr,1−e−λRi−2+1−e−λ2R−x+xi−2,i≥xr.LetH be the maximum routing hop count set by the node; then the connection probability between the source node VS and the destination node VD when H = j is(8)PconH=j=∑i=1i=jfh=i.It is easy to see that the larger the value of the maximum routing hop count (or the greater the vehicle density), the greater the connection probability between the nodes.


### 3.3. Packet Delivery Ratio Model

Packet delivery ratio refers to the ratio of the total number of successfully received packets to the total number of packets sent in the network, which can reflect the network communication quality intuitively. There are two main reasons for packet transmission failures: data collisions and physical layer data errors.Assume that each vehicle node transmits a data packet with an average probabilityτ in each packet duration (the continuous transmission time of a data packet). In practical applications, each vehicle usually has a different probability of packet transmission per packet duration. Here, we only consider τ as an approximate average:(9)τ=smeanTmean⋅Hmean,where smean is the average packet duration, Tmean is the average packet interval, and Hmean is the average maximum routing hop count.Let the interference radius of the node beR; then 2λR vehicles exist in the bidirectional range 2R under the condition that the vehicle density is λ. Therefore, there are two cases where no collision occurs within the same packet duration. One is that only one node in range R sends data packets and no other nodes send data packets. The other case is that all nodes in range R do not send data packets. The probability of the first situation is τ1−τ2λR−1, and the probability of the other situation is 1−τ2λR. Then the probability that the same packet duration does not collide within the radius R is(10)Pn=1−τ2λR+τ1−τ2λR−1=1−τ+τ⋅1−τ2λR−1=1−τ2λR−1.Then, the single-hop collision probability isPc=1−Pn=1−1−τ2λR−1. Any one-hop communication collision in multihop communication is regarded as a collision of communication. Since the collision probability of each hop transmission is an independent probability event, the collision probability of h-hops is(11)Pc∗=1−1−Pch=1−1−τh2λR−1.From [28], the SINR in the DSRC/IEEE 802.11p physical environment can be expressed as(12)SINR=α⋅10log10CN+∑I,where α is the attenuation factor added in consideration of the effect of the cyclic prefix attached to each OFDM symbol, and here α = 0.8. N is the background noise and ∑I is the sum of the surrounding vehicle interference.Assuming that the BPSK modulation method is used, its bit error rate (BER) can be expressed as(13)Pb=Q2⋅SINR,where Q=0.5−0.5×erf2/2 and erf⋅ is the error function. Then, for a data frame of length L bits, the frame error rate (FER) is Pf=1−1−PbL. Considering the data retransmission mechanism of the link layer, the frame error rate can be corrected to(14)Pf∗=1−∑i=0M1−PfPfi,where M is the number of retransmissions. Assuming that each packet consists of t frames, the physical layer transmission single-hop packet error rate is PERphy=1−1−Pf∗t. Then, for a routing link with hop count h, the physical layer transmission packet error rate is(15)PERphy∗=1−∏i=1h1−PERphyi.Therefore, considering the data collision probability and the packet error rate of the physical layer transmission, according to (11) and (15), the packet delivery ratio can be expressed as(16)Psuccess=1−Pc∗1−PERphy∗.For the connection probability model, it can be seen from (8) that it is a summation mathematical probability model; that is, for a large maximum routing hop count, its connection probability includes the cumulative value of the connection probability of the smaller routing hop count. For example, when H = 4, the connection probability includes the summation of the connection probability of H = 1, 2, 3, 4. Therefore, the greater the value of the maximum routing hop count, the greater the node connection probability. For the packet delivery ratio model, it can be seen from (16) that its relationship with the maximum routing hop count consists of two parts. The first part is the packet collision probability. Equation (11) shows that its relationship with the number of routing hops is an exponentially increasing function. The second part is the physical layer packet error rate, which can be seen from (15) as an incremental multiplication mathematical model. Therefore, the greater the value of the maximum routing hop count, the smaller the success ratio of packet transmission.Through the established theoretical model, the influence of vehicle density and maximum routing hop count on communication quality can be relatively intuitively reflected. Large maximum routing hop count and high vehicle density can not only increase the probability of connection between nodes, but also increase the transmission failure ratio of packets. This allows different maximum routing hop count to be set for different vehicle densities, which provides a theoretical basis for further optimization of the routing algorithm.


## 3.1. Multihop VANET System

VANET is a high-dynamic large-scale network, including communication vehicles and roadside units (RSU). The communication modes include V2V and V2I. At present, most of the communication standards of VANET are single-hop communication. While simplifying the network topology, it also reduces the utilization of network resources and increases the cost of network construction. Multihop communication is an inevitable trend of VANET development. The multihop VANET system architecture is shown in Figure1, in which the roadside units can be regarded as small communication base stations and the vehicles can be regarded as a large number of mobile communication terminals.Figure 1
Multihop VANET system architecture.The advantages of multihop communication in VANET are reflected in two aspects. One is for V2I communication, and the other is for V2V communication. For the layout of RSU, if only single-hop communication is allowed, its layout density is required to be high. The two RSUs must be seamlessly connected to ensure that all vehicles are covered by the communication range of RSUs. However, if multihop communication is allowed, the layout density of the RSU can be relatively reduced. For example, theVA in Figure 1 is not within the communication range of RSU1 but can communicate with RSU1 through communication between VA and VE. On the other hand, for V2V communication, if the destination node is not within the communication range of the source node, single-hop communication cannot be completed, but multihop communication is possible.The setting of the maximum routing hop count parameter is of great significance in multihop VANET. Larger value usually increases the probability of connection between vehicle nodes, but it also increases the routing overhead and packet collision probability of the network. For example, in Figure1, the source node VS needs to establish a communication link with the destination node VD. If the maximum routing hop count parameter is set to 1, the communication link cannot be established between the two nodes because the distance x between the two nodes is greater than the node communication distance R. When the maximum routing hop count parameter is set to 2, a possible communication link VS ⟶ VA ⟶ VD can be established. When it is set to 3, four possible communication links can be established, one of which is 2-hop communication: VS ⟶ VA ⟶ VD, and the other 3 possible communication links are 3-hop communication: VS ⟶ VA ⟶ VC ⟶ VD, VS ⟶ VB ⟶ VA ⟶ VD, and VS ⟶ VB ⟶ VC ⟶ VD. It can be seen intuitively that the appropriate value of the maximum routing hop count can increase the possibility of establishing a communication link. But this usually also increases the possibility of data packet collisions because large routing hops mean that more data packets will be transmitted in the network. Therefore, we can increase the connection probability of the communication link by setting an appropriate maximum route hop value on the basis of not increasing network conflicts as much as possible; that is, find the balance between the connection probability and the collision probability.


## 3.2. Node Connectivity Probability Model

Firstly, consider the relationships between node connectivity probability and maximum routing hop count (and vehicle density) in special scenarios. As shown in Figure2, in a straight road with a length of L, the distance between the source node V0 and the destination node Vn is x, and the vehicle communication model is set to a Unit-disk model with a communication range of R, where R < x < 2R.Figure 2
Vehicle connectivity coordinates.A Cartesian coordinate system is established with the source nodeV0 as the coordinate origin. Since the road width is short compared to the vehicle communication distance, the influence of the road width is ignored here.According to the Unit-disk model, assuming that the communication radius of the vehicle isR, communication can be established as long as the distance between the two vehicles is less than R. The probability that communication can be established between two nodes can be expressed as(1)gd=1,d≤R,0,d>R,where d is the distance between the two nodes.For the convenience of analysis, it is assumed that the traffic flow distribution is subject to a Poisson distribution with a vehicle density ofλ vehicles/kilometer [27]. Then the probability that there are k vehicles distributed on the road with length x is(2)fk,x=λxkexp−λxk!,k>0,e−λx,k=0.According to the Poisson distribution model, there areλL vehicles in the section with length L, and there are λx vehicles between the source node and the destination node. Let K(R) be the number of vehicles located on the section with length R; then the probability of having at least one vehicle in R range is(3)PKR>0=1−PKR=0=1−e−λR.The vehicles in Figure2 are numbered V0 to Vn from left to right. Vi represents the ith vehicle node. Let the distance between neighbor nodes in the communication link be di; then di = Vi − Vi−1; that is, the distance between the ith vehicle and the (i − 1)th vehicle is di. Among the vehicles V0 to Vn, di is greater than R only when there is no vehicle node in the section of length R. Therefore, according to (2), Pdi>R=e−λR. To ensure that the neighbor nodes can communicate, di < R is required, that is, at least one vehicle in the length R section. The probability of di < R is(4)Pdi<R=1−Pdi>R=1−e−λR.Leth be the routing hop count of communication link and let fh=i be the connectivity probability between the source node V0 and destination node Vn when the routing hop count equals i and let xi be the coordinate position of the relay node of the ith hop (the distance between the node of the ith hop and V0), and xi < x, as shown in Figure 2. Then we can get(5)fh=1=0,fh=2=1−e−λ2R−x,fh=3=1−e−λR1−e−λ2R−x+x1,…fh=i=1−e−λRi−21−e−λ2R−x+xi−2.Similarly, the connectivity probability in the general scenario can be obtained as follows.Whenx/R<1(6)fh=i=1,i=1,1−e−λx+∑j=1i−1λxjexp−λxj!,i>1.Whenx/R>1(7)fh=i=0,i<xr,1−e−λRi−2+1−e−λ2R−x+xi−2,i≥xr.LetH be the maximum routing hop count set by the node; then the connection probability between the source node VS and the destination node VD when H = j is(8)PconH=j=∑i=1i=jfh=i.It is easy to see that the larger the value of the maximum routing hop count (or the greater the vehicle density), the greater the connection probability between the nodes.


## 3.3. Packet Delivery Ratio Model

Packet delivery ratio refers to the ratio of the total number of successfully received packets to the total number of packets sent in the network, which can reflect the network communication quality intuitively. There are two main reasons for packet transmission failures: data collisions and physical layer data errors.Assume that each vehicle node transmits a data packet with an average probabilityτ in each packet duration (the continuous transmission time of a data packet). In practical applications, each vehicle usually has a different probability of packet transmission per packet duration. Here, we only consider τ as an approximate average:(9)τ=smeanTmean⋅Hmean,where smean is the average packet duration, Tmean is the average packet interval, and Hmean is the average maximum routing hop count.Let the interference radius of the node beR; then 2λR vehicles exist in the bidirectional range 2R under the condition that the vehicle density is λ. Therefore, there are two cases where no collision occurs within the same packet duration. One is that only one node in range R sends data packets and no other nodes send data packets. The other case is that all nodes in range R do not send data packets. The probability of the first situation is τ1−τ2λR−1, and the probability of the other situation is 1−τ2λR. Then the probability that the same packet duration does not collide within the radius R is(10)Pn=1−τ2λR+τ1−τ2λR−1=1−τ+τ⋅1−τ2λR−1=1−τ2λR−1.Then, the single-hop collision probability isPc=1−Pn=1−1−τ2λR−1. Any one-hop communication collision in multihop communication is regarded as a collision of communication. Since the collision probability of each hop transmission is an independent probability event, the collision probability of h-hops is(11)Pc∗=1−1−Pch=1−1−τh2λR−1.From [28], the SINR in the DSRC/IEEE 802.11p physical environment can be expressed as(12)SINR=α⋅10log10CN+∑I,where α is the attenuation factor added in consideration of the effect of the cyclic prefix attached to each OFDM symbol, and here α = 0.8. N is the background noise and ∑I is the sum of the surrounding vehicle interference.Assuming that the BPSK modulation method is used, its bit error rate (BER) can be expressed as(13)Pb=Q2⋅SINR,where Q=0.5−0.5×erf2/2 and erf⋅ is the error function. Then, for a data frame of length L bits, the frame error rate (FER) is Pf=1−1−PbL. Considering the data retransmission mechanism of the link layer, the frame error rate can be corrected to(14)Pf∗=1−∑i=0M1−PfPfi,where M is the number of retransmissions. Assuming that each packet consists of t frames, the physical layer transmission single-hop packet error rate is PERphy=1−1−Pf∗t. Then, for a routing link with hop count h, the physical layer transmission packet error rate is(15)PERphy∗=1−∏i=1h1−PERphyi.Therefore, considering the data collision probability and the packet error rate of the physical layer transmission, according to (11) and (15), the packet delivery ratio can be expressed as(16)Psuccess=1−Pc∗1−PERphy∗.For the connection probability model, it can be seen from (8) that it is a summation mathematical probability model; that is, for a large maximum routing hop count, its connection probability includes the cumulative value of the connection probability of the smaller routing hop count. For example, when H = 4, the connection probability includes the summation of the connection probability of H = 1, 2, 3, 4. Therefore, the greater the value of the maximum routing hop count, the greater the node connection probability. For the packet delivery ratio model, it can be seen from (16) that its relationship with the maximum routing hop count consists of two parts. The first part is the packet collision probability. Equation (11) shows that its relationship with the number of routing hops is an exponentially increasing function. The second part is the physical layer packet error rate, which can be seen from (15) as an incremental multiplication mathematical model. Therefore, the greater the value of the maximum routing hop count, the smaller the success ratio of packet transmission.Through the established theoretical model, the influence of vehicle density and maximum routing hop count on communication quality can be relatively intuitively reflected. Large maximum routing hop count and high vehicle density can not only increase the probability of connection between nodes, but also increase the transmission failure ratio of packets. This allows different maximum routing hop count to be set for different vehicle densities, which provides a theoretical basis for further optimization of the routing algorithm.


## 4. Maximum Routing Hop Count Selection Algorithm-Based Vehicle Density

According to the node connectivity probability model and the packet delivery ratio model proposed in the previous section, this section proposes the maximum routing hop count selection algorithm based vehicle density (MRHSA).From (7) and (8), the growth rate of node connectivity probability with the increase of maximum routing hop count is calculated as follows:(17)Growthj=PconH=j−PconH=j−1PconH=j−1=fh=j∑i=2j−1fh=i.Let the exponential term−λ2R−x+xi−2 in (7) take its approximate mean value X and substitute it into the above formula:(18)Growthj=1−e−λRj−2∑i=2j−11−e−λRi−2.The impact of the increase in the routing hop count on the packet delivery ratio is mainly to increase the collision probability of the data packet but does not affect the transmission of the channel. Therefore, we only consider the probability of packet collision here. According to (16), the packet delivery ratio model is simplified to(19)Psuccess=1−Pc∗.From the above formula, the reduction rate of the packet delivery ratio as the routing hop count increases can be calculated:(20)Reductionj=PsuccessH=j−PsuccessH=j−1PsuccessH=j−1=1−1−τ2λR−1.As in the GPSR, it is assumed that the position coordinates of the source vehicle and the destination vehicle can be acquired. Vehicle density can be obtained from beacon messages or obtained from historical statistics [29].(1)
The Euclidean distance is calculated from the locations of the source and destination vehicles, and then the minimum initial valueHmin=x/R of the maximum routing hop count is calculated. See line 5 of Algorithm 1.(2)
To simplify the calculation, when the destination node is within the communication range of the source node (x < R), the maximum routing hop count is set to 2. In theory, one-hop communication is more reliable in the communication range. Setting the value to 2 here is mainly to prevent the vehicle from being at the maximum edge of the communication range. See lines 6 to 7 of Algorithm 1.(3)
When the vehicle density is less than 1 vehicle/km, the maximum routing hop count is set to the maximum achievable value in the range of distancex; that is, Hmin+λx. See lines 9 to 10 of Algorithm 1.(4)
WithHmin as the initial value, the node connectivity probability and the packet delivery ratio are iteratively calculated until the growth rate of the connectivity probability is less than the rate of decline rate of the packet delivery ratio. After the iterative calculation is completed, the value of H is returned. See lines 11 to 17 of Algorithm 1 where σ in line 16 is the weighting factor to balance the preference for packet delivery ratio and connection probability and its value range is (0-1).Algorithm 1: MRHSA: maximum routing hop count selection algorithm.
(1)
Notations;(2)
XS: source vehicle location; XD: destination vehicle location; λ: vehicle density;(3)
τ: average packet transmission probability. H: output of maximum routing hop count(4)
Initialization;(5)
x = sqrt (XS − XD)2; Hmin=x/R; H = Hmin;(6)
ifHmin<=  1 then(7)
returnH = 2;(8)
else then(9)
if (λ < 1) then(10)
returnH = Hmin+λx;(11)
else then(12)
repeat(13)
calculatePcon (H) and Psuccess (H) with (8) and (19);(14)
calculate Growth (H) and Reduction (H) with (18) and (20);(15)
H++;(16)
untilσ ∗ Growth (H) >= (1 − σ) ∗ Reduction (H)(17)
returnH;(18)
end if(19)
end ifThe process of the MRHSA is described in detail in Algorithm1. This algorithm consumes insignificant computing power because the number of iterations is limited (mostly less than 20).


## 5. Simulation and Results

This section presents the simulation and analysis results of the MRHSA in the AODV routing protocol under the Vehicle in Network Simulation (Veins). The MRHSA was evaluated in terms of average packet delivery ratio, throughput, and average end-to-end delay.


### 5.1. Simulation Setup

The Veins simulation platform integrates the OMNET++ network simulator and the SUMO road traffic simulator to provide an open source simulation architecture for VANET simulation [30]. This section first establishes a two-way four-lane straight road simulation scene with a length of 5 km, which can also be used to represent highway scenes. Because the vehicle density distribution on the straight road is simple, it can intuitively reflect the influence of the maximum routing hop count parameter on the communication index under different vehicle densities. Then the simulation experiment is extended to the general urban scene, and the real-time simulation data of the urban road area of 2500 m × 2500 m is analyzed. This paper focuses on the impact of the maximum routing hop count and vehicle density on communication indicators in the same road environment. The environmental differences between straight road scenes and urban road scenes can be further studied in further work.As shown in Table2, the physical layer and mac layer of the simulation parameters use the 802.11p standard, the network layer uses the AODV routing protocol, and the application layer uses the UdpApp protocol. The vehicle speed in the urban area is set to 30–60 km/h, and the vehicle speed in the high-speed public area is set to 60–200 km/h. In order to simulate a real vehicle model, four different vehicle types are set in the SUMO environment, including different settings for parameters such as maximum vehicle speed, vehicle acceleration, vehicle deceleration, vehicle length, following model, and driver behavior. In addition, the simulation time of the straight road scene is set to 300 s, and the simulation time of the urban scene is set to 600 s.Table 2
Simulation parameters.
ParametersValuePhysical/Mac layerIEEE802.11pNetwork layerAODVApplication layerUdpAppSimulation areaStraight road/urbanMaximum vehicle speed30–200 km/hSimulation time300 s/600 sAccording to the Wireless Access in Vehicular Environment (WAVE) standard file, the main parameters of the physical layer and the MAC layer are shown in Table3. The communication range of each vehicle node is set to 300 m and the bitrate is 6 Mbps. For the MAC layer, each access time slot is set to 16 μs, the maximum queue length is set to 14, and the maximum number of repeated accesses is set to 7.Table 3
Main IEEE802.11p parameters.
ParametersValueTransmission range300 mCarrier frequency5.9 GHzBitrate6 MbpsTransmitter power20 mWThermal noise power−110 dBmA slot time16μsQueue length14Retry limit7The application layer periodically transmits a packet at a random time of (0–5)s after the vehicle enters the road, and the transmission interval is (3–8)s. The transmission destination address is randomly selected from existing vehicle nodes in the road. Both the address and the packet are in Ipv4 format. The size of each packet is 512 bytes. In order to achieve a reproducible randomness experimental study, the same set of data in the same scenario uses the same random number seed, and the average of the data of four different random number seeds is taken as the final simulation data.


### 5.2. Simulation Results

During the simulation, the vehicle density is controlled by controlling the vehicle depart rateλ of each lane (the probability of departing the vehicle per second, taking the value 0-1). The corresponding values of λ and vehicle density for the straight road scenario are shown in Table 4.Table 4
Vehicle density.
λVehicle density (vehicle / km)0.13.60.39.10.514.10.722.71.031.2Figure3 shows the packet delivery ratio for different vehicle densities and different maximum routing hop count. MRHSA dynamically adjusts the maximum routing hop count based on vehicle density, with the rest set to a fixed value. It can be seen that the maximum routing hop count set to 20 in the experiment for the straight road scenario is too large for the packet delivery ratio because its packet delivery ratio is smaller than the packet delivery ratio of maximum routing hop count of 10 when the vehicle depart rate is 0.1–1.0. The performance of packet delivery ratio with a maximum routing hop count of 5 gradually improves with the increase of vehicle density, and its performance at the vehicle depart rates of 0.7 and 1.0 exceeds the performance of the maximum routing hop count of 10. This verifies the theory in the third section that when the vehicle density is low, the larger maximum routing hop count can increase the packet delivery ratio by increasing the connection probability; but when the vehicle density is high, the larger maximum routing hop count will reduce the packet delivery ratio by increasing the data collision probability.Figure 3
Packet delivery ratio under straight road scenes.The whole performance of the MRHSA algorithm presented in the previous section is better than setting the maximum routing hop count to a fixed value. During the simulation, MRHSA improved the packet delivery ratio by about 9.1% at most. As the vehicle density increases, the spacing between the MRHSA curve and other curves increases, which indicates that MRHSA has a more obvious optimization effect on packet delivery ratio when vehicle density is large. It can also be observed that, as the vehicle density increases, the value of the packet delivery ratio decreases overall. This is because we set all the vehicle nodes to send messages periodically during the simulation process. As the density of vehicles increases, the number of packets transmitted in the network increases, and the collision probability of packets increases.As shown in Figure4, the throughput performance of MRHSA is optimal, and, as the vehicle density increases, the optimization effect of MRHSA on throughput is gradually enhanced. The throughput for maximum routing hop count of 10 or 20 is higher than the throughput for maximum routing hop count of 5 at λ = 0.1 to 0.5, but their throughput growth rate is lower than the latter after λ > 0.5. The increase of vehicle density and maximum routing hop count can increase the number of packets in the network and thus increase the network throughput. However, when the vehicle density and the maximum routing hop count are both large, serious data collisions will occur, which will reduce the growth rate of throughput.Figure 4
Throughput under straight road scenes.As shown in Figure5, the end-to-end delay increases overall as the vehicle density and maximum routing hop count increase. This is mainly caused by two aspects: one is the increase of delay caused by the increase of average routing hops; the other is the increase of access delay caused by data congestion. The end-to-end delay curve of MRHSA fluctuates greatly, which is related to the average routing hops in the actual transmission process. According to different vehicle densities, MRHSA algorithm provides the possibility of larger forwarding hops on the premise of minimizing unnecessary congestion. It should be noted that this paper does not optimize for the end-to-end delay, only analyzing its relationship with the maximum routing hop count and vehicle density.Figure 5
End-to-end delay under straight road scenes.The density of vehicles in urban scenes is difficult to control accurately during the simulation, so we recorded the number of real-time vehicles in the simulation to analyze the real-time data of the simulation process, as shown in Figure6. Since the amount of data in real-time simulation is too large, we have done a window batch average and exponential moving average processing for the packet delivery ratio for the convenience of observation, as shown in Figure 7.Figure 6
The number of real-time vehicles under urban road scenes.Figure 7
Packet delivery ratio under urban road scenes.Before about 280s, that is, when the number of vehicles is less than 190, the larger the maximum routing hop count is, the better the packet delivery ratio will be. After that, the packet delivery ratio with a maximum routing hop count of 10 is better than the packet delivery ratio with a maximum routing hop count of 20. When the number of vehicles reaches the maximum between 330s and 450s, all packet delivery ratio curves decrease with a large slope, except for the packet delivery ratio curve with the maximum routing hop count of 5. Because the packet delivery ratio with a maximum routing hop count of 5 is originally small, and it causes less data collision when the vehicle density is very large. Except for the first 50 seconds, MRHSA's performance is always optimal. In the first 50 seconds of the simulation, the number of vehicles is small and the position of the vehicle entering the simulation area is scattered, so accurate vehicle density cannot be obtained.Real-time throughput data have a large value range, so we recorded the average throughput per 100 seconds for the convenience of observation, as shown in Figure8. Real-time end-to-end delay data fluctuate greatly with time; so also for ease of observation, the end-to-end delay data are averaged per 100 seconds, as shown in Figure 9. As can be seen from the figure, the relationships between the maximum routing hop count and throughput (and end-to-end delay) under urban road scenes are similar to the straight road scenes.Figure 8
Throughput under urban road scenes.Figure 9
End-to-end delay under urban road scenes.


## 5.1. Simulation Setup

The Veins simulation platform integrates the OMNET++ network simulator and the SUMO road traffic simulator to provide an open source simulation architecture for VANET simulation [30]. This section first establishes a two-way four-lane straight road simulation scene with a length of 5 km, which can also be used to represent highway scenes. Because the vehicle density distribution on the straight road is simple, it can intuitively reflect the influence of the maximum routing hop count parameter on the communication index under different vehicle densities. Then the simulation experiment is extended to the general urban scene, and the real-time simulation data of the urban road area of 2500 m × 2500 m is analyzed. This paper focuses on the impact of the maximum routing hop count and vehicle density on communication indicators in the same road environment. The environmental differences between straight road scenes and urban road scenes can be further studied in further work.As shown in Table2, the physical layer and mac layer of the simulation parameters use the 802.11p standard, the network layer uses the AODV routing protocol, and the application layer uses the UdpApp protocol. The vehicle speed in the urban area is set to 30–60 km/h, and the vehicle speed in the high-speed public area is set to 60–200 km/h. In order to simulate a real vehicle model, four different vehicle types are set in the SUMO environment, including different settings for parameters such as maximum vehicle speed, vehicle acceleration, vehicle deceleration, vehicle length, following model, and driver behavior. In addition, the simulation time of the straight road scene is set to 300 s, and the simulation time of the urban scene is set to 600 s.Table 2
Simulation parameters.
ParametersValuePhysical/Mac layerIEEE802.11pNetwork layerAODVApplication layerUdpAppSimulation areaStraight road/urbanMaximum vehicle speed30–200 km/hSimulation time300 s/600 sAccording to the Wireless Access in Vehicular Environment (WAVE) standard file, the main parameters of the physical layer and the MAC layer are shown in Table3. The communication range of each vehicle node is set to 300 m and the bitrate is 6 Mbps. For the MAC layer, each access time slot is set to 16 μs, the maximum queue length is set to 14, and the maximum number of repeated accesses is set to 7.Table 3
Main IEEE802.11p parameters.
ParametersValueTransmission range300 mCarrier frequency5.9 GHzBitrate6 MbpsTransmitter power20 mWThermal noise power−110 dBmA slot time16μsQueue length14Retry limit7The application layer periodically transmits a packet at a random time of (0–5)s after the vehicle enters the road, and the transmission interval is (3–8)s. The transmission destination address is randomly selected from existing vehicle nodes in the road. Both the address and the packet are in Ipv4 format. The size of each packet is 512 bytes. In order to achieve a reproducible randomness experimental study, the same set of data in the same scenario uses the same random number seed, and the average of the data of four different random number seeds is taken as the final simulation data.


## 5.2. Simulation Results

During the simulation, the vehicle density is controlled by controlling the vehicle depart rateλ of each lane (the probability of departing the vehicle per second, taking the value 0-1). The corresponding values of λ and vehicle density for the straight road scenario are shown in Table 4.Table 4
Vehicle density.
λVehicle density (vehicle / km)0.13.60.39.10.514.10.722.71.031.2Figure3 shows the packet delivery ratio for different vehicle densities and different maximum routing hop count. MRHSA dynamically adjusts the maximum routing hop count based on vehicle density, with the rest set to a fixed value. It can be seen that the maximum routing hop count set to 20 in the experiment for the straight road scenario is too large for the packet delivery ratio because its packet delivery ratio is smaller than the packet delivery ratio of maximum routing hop count of 10 when the vehicle depart rate is 0.1–1.0. The performance of packet delivery ratio with a maximum routing hop count of 5 gradually improves with the increase of vehicle density, and its performance at the vehicle depart rates of 0.7 and 1.0 exceeds the performance of the maximum routing hop count of 10. This verifies the theory in the third section that when the vehicle density is low, the larger maximum routing hop count can increase the packet delivery ratio by increasing the connection probability; but when the vehicle density is high, the larger maximum routing hop count will reduce the packet delivery ratio by increasing the data collision probability.Figure 3
Packet delivery ratio under straight road scenes.The whole performance of the MRHSA algorithm presented in the previous section is better than setting the maximum routing hop count to a fixed value. During the simulation, MRHSA improved the packet delivery ratio by about 9.1% at most. As the vehicle density increases, the spacing between the MRHSA curve and other curves increases, which indicates that MRHSA has a more obvious optimization effect on packet delivery ratio when vehicle density is large. It can also be observed that, as the vehicle density increases, the value of the packet delivery ratio decreases overall. This is because we set all the vehicle nodes to send messages periodically during the simulation process. As the density of vehicles increases, the number of packets transmitted in the network increases, and the collision probability of packets increases.As shown in Figure4, the throughput performance of MRHSA is optimal, and, as the vehicle density increases, the optimization effect of MRHSA on throughput is gradually enhanced. The throughput for maximum routing hop count of 10 or 20 is higher than the throughput for maximum routing hop count of 5 at λ = 0.1 to 0.5, but their throughput growth rate is lower than the latter after λ > 0.5. The increase of vehicle density and maximum routing hop count can increase the number of packets in the network and thus increase the network throughput. However, when the vehicle density and the maximum routing hop count are both large, serious data collisions will occur, which will reduce the growth rate of throughput.Figure 4
Throughput under straight road scenes.As shown in Figure5, the end-to-end delay increases overall as the vehicle density and maximum routing hop count increase. This is mainly caused by two aspects: one is the increase of delay caused by the increase of average routing hops; the other is the increase of access delay caused by data congestion. The end-to-end delay curve of MRHSA fluctuates greatly, which is related to the average routing hops in the actual transmission process. According to different vehicle densities, MRHSA algorithm provides the possibility of larger forwarding hops on the premise of minimizing unnecessary congestion. It should be noted that this paper does not optimize for the end-to-end delay, only analyzing its relationship with the maximum routing hop count and vehicle density.Figure 5
End-to-end delay under straight road scenes.The density of vehicles in urban scenes is difficult to control accurately during the simulation, so we recorded the number of real-time vehicles in the simulation to analyze the real-time data of the simulation process, as shown in Figure6. Since the amount of data in real-time simulation is too large, we have done a window batch average and exponential moving average processing for the packet delivery ratio for the convenience of observation, as shown in Figure 7.Figure 6
The number of real-time vehicles under urban road scenes.Figure 7
Packet delivery ratio under urban road scenes.Before about 280s, that is, when the number of vehicles is less than 190, the larger the maximum routing hop count is, the better the packet delivery ratio will be. After that, the packet delivery ratio with a maximum routing hop count of 10 is better than the packet delivery ratio with a maximum routing hop count of 20. When the number of vehicles reaches the maximum between 330s and 450s, all packet delivery ratio curves decrease with a large slope, except for the packet delivery ratio curve with the maximum routing hop count of 5. Because the packet delivery ratio with a maximum routing hop count of 5 is originally small, and it causes less data collision when the vehicle density is very large. Except for the first 50 seconds, MRHSA's performance is always optimal. In the first 50 seconds of the simulation, the number of vehicles is small and the position of the vehicle entering the simulation area is scattered, so accurate vehicle density cannot be obtained.Real-time throughput data have a large value range, so we recorded the average throughput per 100 seconds for the convenience of observation, as shown in Figure8. Real-time end-to-end delay data fluctuate greatly with time; so also for ease of observation, the end-to-end delay data are averaged per 100 seconds, as shown in Figure 9. As can be seen from the figure, the relationships between the maximum routing hop count and throughput (and end-to-end delay) under urban road scenes are similar to the straight road scenes.Figure 8
Throughput under urban road scenes.Figure 9
End-to-end delay under urban road scenes.


## 6. Conclusions

The effects of choosing different maximum routing hop count parameters on network performance under different vehicle densities are studied in this paper. Firstly, the connectivity probability model and the packet delivery ratio model related to the maximum routing hop count and vehicle density are established. Then, on the basis of the theoretical model established in this paper, MRHSA is proposed. Through simulation experiments on straight road scenes and urban scenes, we verify that the larger maximum routing hop count will reduce network performance when the vehicle density is high. Meanwhile, the improvement of network performance by MRHSA algorithm is also evaluated. MRHSA has a more obvious optimization effect on packet delivery ratio and throughput when vehicle density is large. In the straight road scenario, MRHSA can improve the packet delivery ratio by about 9.1% at most. In the future work, the MRHSA algorithm can be integrated into the routing strategy to further improve the transmission performance of the network.



---

*Source: 2741648-2020-06-10.xml*