# Genetic Algorithm Based QoS Perception Routing Protocol for VANETs

Authors: Guoan Zhang; Min Wu; Wei Duan; Xinming Huang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

A genetic algorithm (GA) based QoS perception routing protocol (GABR) is proposed to guarantee the quality of service (QoS) influenced by broken links between vehicles and the failure of packets transmission in a vehicular ad hoc network (VANET). With the observation that all improvable paths are probed by the intersection based routing protocol, the genetic GA is utilized to optimize the global available paths which satisfies the QoS requirement. Moreover, by means of the numerical results, it is shown that the proposed scheme is significantly improved compared with protocols of the intersection based routing (IBR) and connectivity aware routing (CAR) in terms of transmission delay and packet loss rate.


---

## Body

## 1. Introduction

Recently, vehicular ad hoc networks (VANETs) has been widely considered as a new class of mobile ad hoc networks since it serves as an important part in intelligent transportation systems (ITS). Following the traffic rules, the vehicles can move along the roads in the VANETs. Specifically, the network topology has shown the ability to dynamically change the diversity of roads, different velocities, and densities of vehicles. With the cooperation of the wireless communication devices, the vehicles can communicate with each other in VANETs [1, 2], which is exhibited as the vehicle to vehicle (V2V) and/or the vehicle to infrastructure communication architectures (V2X).Classically, routing protocols can be classified into two categories: the topology based routing protocols and the routing protocols based on geographical location information. By taking into account the complicated topological structure, for the topology based routing protocol, it makes routing decisions by using the topology information of network, which may lead to the broken links between vehicles. On the other hand, the routing protocols based on geographical location information require data communications to obtain the vehicle positions via global position system (GPS). Based on which, it is clear that the second routing protocol characterizes a superiority for varied VANETs [3, 4]. Unfortunately, even the position based routing protocols have received considerable interest in the VANETs, it is up against many potential challenges, i.e., the latency of real-time capabilities, position accuracy, huge overhead, and increased cost of applications. For instance, in connectivity aware routing protocols, source node explores paths by broadcasting messages to obtain a fixed routing path, which is unable to deal with frequent changes of topology in VANETs [5]. Particularly, considering the real-time road conditions for the intersections selection, the packets delivering in the intersections are dependent on the direction of other vehicles, which causes packets lose for the connectivity of the roads [6]. The improved greedy traffic aware routing protocols (GyTAR) combine the density and direction of vehicles and local street conditions for routing decisions. Without taking the global information into account, it will result in network partitions in the process of delivering packets [7].Due to the improvement of QoS performance [8–10] as the goal of optimizing routing paths, some articles consider to apply genetic algorithms (GAs) to enhance the performance of routing protocols. Reference [11] presented the destination sequenced distance vector routing protocol using GA in VANET, which is a kind of the topology based routing protocol and uses a fitness function to evaluate the solution, then simulation result analysis showed the QoS of DSDV with GA is better than the simple DSDV scheme. The authors in [12] considered the ad hoc on-demand distance vector routing protocol through genetic algorithm, which aims to find the optimal path from the source to destination and increase the throughput of AODV, where the simulation results illustrated that the proposed algorithm significantly improves the QoS compared to the simple one with satisfactory efficiency.In this paper, to further enhance the QoS performance of location based routing protocols in urban environment for VANETs, an efficient GA is applied to optimize the routing path between source and destination nodes. The connectivity model and the delay model are also analyzed to estimate the average delay, where the road segment is divided into several blocks. Moreover, the IBR protocol is also employed to explore possible paths between sources and destinations. Based on that, the proposed genetic algorithm optimizes routing paths which subjects to the fitness function switched by the objective function with parallelism, where an initial population composed of multiple solutions is considered. It is worth noting that the genetic operations, i.e., selection, crossover, and mutation, are disposed with certain probabilities that reinforce the flexibility of the searching process [13, 14]. With this observation, for our proposed GA, the obtained results undergo genetic operations which support the following search. From the numerical results, it is shown that, compared with the IBR and CAR protocols, the proposed GABR protocol scheme outperforms significantly in terms of packets transmission delay and packet loss rate.The rest of this paper is organized as follows. Section2 describes the GABR algorithm. In Section 3, it shows investigation for GABR. Analysis of the QoS model for the proposed scheme is presented in Section 4. Section 5 shows the excellent performance of our proposed scheme compared with the existing works. Section 6 concludes this paper.


## 2. GABR Algorithm

### 2.1. QoS Model

One example of urban street is shown in Figure1, in which four intersections (I1~I4) are considered. Due to the forward delay and connectivity between multiple links on the two-way lane, the road segment model is designed. Therefore, for each road segment, traffic conditions are randomly distributed. In the proposed system, the following assumptions are considered:(i)
On a straight road segment, the lanes between two intersections (Ii,Ij) are located along opposite directions referred as the east and west bound with length L.(ii)
The direction of moving vehicles is eastbound, and the communication range is set asR.(iii)
The vehicles in the two-lane road segment scenarios follow the Poisson distribution [15].(iv)
The vehicle densities for the east and west bound lane are set to beλ1 and λ2, while the average vehicle velocities for two lanes are v1 and v2, respectively.Figure 1
Sample of urban street.In this paper, QoS model is split into two parts: the connectivity model and delay model. Particularly, the road segment is also divided into several rectangular blocks with the length and width of each block asaR, where a=0.7 and two-lane road width is used to accurately analyze the QoS [1].


#### 2.1.1. Connectivity Probability Model

In order to study the exact connectivity model for a two-lane road as shown in Figure2, the distance X between two consecutive vehicles on the eastbound lane is compared with R. By this way, the link between two consecutive vehicles is connected and packets are delivered directly with the condition X≤R; otherwise, the packets are out of scope which can not be forwarded directly. Owing to the cooperation of the auxiliary vehicle in the westbound block, the broken link is possible to be repaired regarding X.Figure 2
Distribution of road vehicles.Without loss of generality, further assume thatK is a random variable denoting the number of vehicles in each block which follows the Poisson distribution with Probability Mass Function (PMF) as(1)PK=k=aRλke-aRλk!,where λ denotes the vehicle density on a road segment lane. Since the distance between any two consecutive vehicles obeys the exponential distribution [16], the corresponding probability of a broken link between two vehicles on the eastbound lane can be expressed as(2)Pb=PX>R=e-λ1Rwith λ1 as the vehicle density on eastbound lane.


#### 2.1.2. Transmission Delay Model

Following traffic rules in the urban environment, vehicles move into clusters, where the link between two consecutive vehicles is connected in each cluster. On account of the cluster size, there are two kind situations of vehicles moving:(i)
Road segment with partly connected (PC): as shown in Figure3, packets can be forwarded to the furthest vehicles within communication range as next-hop node by utilizing greedy algorithm on the connected road segment. On the contrary, packets on the broken segment can use carry-forward mechanism.(ii)
Road segment with absolutely connected (AC): as shown in Figure4, packets can be delivered by hop to hop with greedy algorithm between two intersections.Figure 3
Road segment with partly connected.Figure 4
Road segment with absolutely connected.


## 2.1. QoS Model

One example of urban street is shown in Figure1, in which four intersections (I1~I4) are considered. Due to the forward delay and connectivity between multiple links on the two-way lane, the road segment model is designed. Therefore, for each road segment, traffic conditions are randomly distributed. In the proposed system, the following assumptions are considered:(i)
On a straight road segment, the lanes between two intersections (Ii,Ij) are located along opposite directions referred as the east and west bound with length L.(ii)
The direction of moving vehicles is eastbound, and the communication range is set asR.(iii)
The vehicles in the two-lane road segment scenarios follow the Poisson distribution [15].(iv)
The vehicle densities for the east and west bound lane are set to beλ1 and λ2, while the average vehicle velocities for two lanes are v1 and v2, respectively.Figure 1
Sample of urban street.In this paper, QoS model is split into two parts: the connectivity model and delay model. Particularly, the road segment is also divided into several rectangular blocks with the length and width of each block asaR, where a=0.7 and two-lane road width is used to accurately analyze the QoS [1].


### 2.1.1. Connectivity Probability Model

In order to study the exact connectivity model for a two-lane road as shown in Figure2, the distance X between two consecutive vehicles on the eastbound lane is compared with R. By this way, the link between two consecutive vehicles is connected and packets are delivered directly with the condition X≤R; otherwise, the packets are out of scope which can not be forwarded directly. Owing to the cooperation of the auxiliary vehicle in the westbound block, the broken link is possible to be repaired regarding X.Figure 2
Distribution of road vehicles.Without loss of generality, further assume thatK is a random variable denoting the number of vehicles in each block which follows the Poisson distribution with Probability Mass Function (PMF) as(1)PK=k=aRλke-aRλk!,where λ denotes the vehicle density on a road segment lane. Since the distance between any two consecutive vehicles obeys the exponential distribution [16], the corresponding probability of a broken link between two vehicles on the eastbound lane can be expressed as(2)Pb=PX>R=e-λ1Rwith λ1 as the vehicle density on eastbound lane.


### 2.1.2. Transmission Delay Model

Following traffic rules in the urban environment, vehicles move into clusters, where the link between two consecutive vehicles is connected in each cluster. On account of the cluster size, there are two kind situations of vehicles moving:(i)
Road segment with partly connected (PC): as shown in Figure3, packets can be forwarded to the furthest vehicles within communication range as next-hop node by utilizing greedy algorithm on the connected road segment. On the contrary, packets on the broken segment can use carry-forward mechanism.(ii)
Road segment with absolutely connected (AC): as shown in Figure4, packets can be delivered by hop to hop with greedy algorithm between two intersections.Figure 3
Road segment with partly connected.Figure 4
Road segment with absolutely connected.


## 2.1.1. Connectivity Probability Model

In order to study the exact connectivity model for a two-lane road as shown in Figure2, the distance X between two consecutive vehicles on the eastbound lane is compared with R. By this way, the link between two consecutive vehicles is connected and packets are delivered directly with the condition X≤R; otherwise, the packets are out of scope which can not be forwarded directly. Owing to the cooperation of the auxiliary vehicle in the westbound block, the broken link is possible to be repaired regarding X.Figure 2
Distribution of road vehicles.Without loss of generality, further assume thatK is a random variable denoting the number of vehicles in each block which follows the Poisson distribution with Probability Mass Function (PMF) as(1)PK=k=aRλke-aRλk!,where λ denotes the vehicle density on a road segment lane. Since the distance between any two consecutive vehicles obeys the exponential distribution [16], the corresponding probability of a broken link between two vehicles on the eastbound lane can be expressed as(2)Pb=PX>R=e-λ1Rwith λ1 as the vehicle density on eastbound lane.


## 2.1.2. Transmission Delay Model

Following traffic rules in the urban environment, vehicles move into clusters, where the link between two consecutive vehicles is connected in each cluster. On account of the cluster size, there are two kind situations of vehicles moving:(i)
Road segment with partly connected (PC): as shown in Figure3, packets can be forwarded to the furthest vehicles within communication range as next-hop node by utilizing greedy algorithm on the connected road segment. On the contrary, packets on the broken segment can use carry-forward mechanism.(ii)
Road segment with absolutely connected (AC): as shown in Figure4, packets can be delivered by hop to hop with greedy algorithm between two intersections.Figure 3
Road segment with partly connected.Figure 4
Road segment with absolutely connected.


## 3. Details of the GABR Protocol

### 3.1. Genetic Algorithm

It is well known that GA is a random search method based on the evolution rule of biology (survival of the fittest), which was first proposed byJ. Holland in 1975 to optimize the complete NP problems [17]. The genetic algorithm imitates the process of natural selection (NS), in which NS means a central concept of evolution: some organisms have traits that will make it more likely that the organism survives long enough to reproduce. It is likely that these traits will be passed on to the next generation, which is also named survival of the fittest. For a simple description, genetic algorithm can be seen as a simulation in which a population of abstract representations (called chromosomes or the phenotype of the genome, after their biological counterparts) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem. Since that genetic algorithms are randomized search and optimization techniques guided by the principles of evolution and natural genetics, having a large amount of implicit parallelism. Therefore, genetic algorithms are part of the broader class of evolutionary algorithms that can be applied to the optimization of complex algorithms, the training of text classification systems, and the evolution of intelligent artificial agents in stochastic environments. With these observations, genetic algorithms perform search in complex, large, and multimodal landscapes and provide near-optimal solutions for objective or fitness function of an optimization problem.Figure5 depicts the basic module process of GA [18], which is illustrated in detail as follows:(i)
The first step to develop a GA for an optimization problem is to represent it. Therefore, the solution is in the form of a string of bits which consists of the same number of element.(ii)
An initial population is normally generated randomly which should be spread over enough of the search space to represent as wide a variety of solutions as possible.(iii)
The selection allows strings to be copied for possible inclusion in the next generation, where the standard for the selection is that of the fitness of all individuals.(iv)
The crossover is applied to two chromosomes and creates two new chromosomes by selecting a random position.(v)
Selection and crossover alone can generate a staggering amount of differing strings.(vi)
The stopping criterion can be set by the number of evolution cycles, the amount of variation of individuals between different generations, or a predefined value of fitness.Figure 5
Basic module process of GA.


### 3.2. Routing Exploration

In this paper, the proposed protocol is based on IBR with GA, and vehicles are equipped with GPS and navigation system. Adopting traffic information to predict the vehicle moving direction, GABR protocol selects the next-hop intersection dynamically. Meanwhile, vehicles utilize carry-forward strategy to deliver packets on the road segment. The proposed routing exploration integrates locating destinations with finding connected paths between source and destination. It means that, to gather the available information along the routes, the source vehicle broadcasts the request packets to the destination. After receiving the request packets, accordingly, the destination confirms the best routing path which will be replied to the source.


### 3.3. Genetic Operations

In this subsection, the main flow chart of our proposed routing algorithm with GA is introduced as shown in Figure6. To begin with, all improvable paths are probed by IBR. Subsequently, genetic algorithm is utilized in the global optimization of available paths to acquire the path with optimal QoS. All available paths are optimized by GA repeatedly with five steps to find optimal QoS path, which are shown as follows.Figure 6
Flow chart of GABR protocol.(a)Code: a given route between the source and destination nodes is equal to an individual, i.e., the serial number sequence of intersections of the route is a chromosome, which can be encoded directly. Therefore, this coding scheme avoids the route circulation due to that the variation length of the chromosome and the total numbers are less than the amount of intersections.(b)Initialize the population: according to the route selection strategy based on IBR, G paths are explored as an initial population and with the corresponding size.(c)Selection: the pros and cons of individuals depend on the fitness value in GA, where the fitness value represents the QoS performance. With the increasing fitness, the QoS performance should be also correspondingly improved. An individual has more fitness value, which means that the individual is excellent and the corresponding path is optimal. Therefore, the fitness function can be expressed as follows:(3)S=αPn+βDnth,where Pn and Dnth denote the connectivity probability and average delay of n-th individual and α and β are weight parameters with α,β∈0,1, respectively.In this step, we propose to combine the optimal strategical selection and roulette wheel selection to rank all paths. Before each pair of chromosome crossing, the optimal individual replaces the worst one and becomes an offspring individual according to the fitness value. Then, the rest of the population uses the roulette wheel method, where the individual with higher fitness value is selected by greater probability.(d)Crossover: crossover operator is used to exchange the subpath of two individuals. As shown in Figure 7, P1 and P2 paths are selected as parents. These alternative crossing positions should be randomly selected as the crossing sites, which are both in parents. Remarkably, two new offspring, P1′ and P2′, take shapes after exchanging all nodes and the crossing site.Figure 7
Example of crossover.(e)Mutation: mutation operator is applied to the randomly select the solution P from the population, which is with small random changes in the solution. We further consider that the node ni selected randomly from P for mutation is called mutation node. The operation details in Figure 8 can be summarized as follows.Figure 8
Example of mutation.Step 1.
Select a nodenj from the neighbors of mutation node ni.Step 2.
Generate two random paths (r1,r2) from the source node to node nj and from node nj to destination node, respectively.Step 3.
If there is a duplication nodes inr1, r2, discard the path, and do not perform mutation on it; otherwise, these two routes are connected with each other to form a new mutated chromosome P′.Step 4.
Repeat the process of the selection, crossover, and mutation until reaching the maximum number of iterations or the route paths are optimized.


## 3.1. Genetic Algorithm

It is well known that GA is a random search method based on the evolution rule of biology (survival of the fittest), which was first proposed byJ. Holland in 1975 to optimize the complete NP problems [17]. The genetic algorithm imitates the process of natural selection (NS), in which NS means a central concept of evolution: some organisms have traits that will make it more likely that the organism survives long enough to reproduce. It is likely that these traits will be passed on to the next generation, which is also named survival of the fittest. For a simple description, genetic algorithm can be seen as a simulation in which a population of abstract representations (called chromosomes or the phenotype of the genome, after their biological counterparts) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem. Since that genetic algorithms are randomized search and optimization techniques guided by the principles of evolution and natural genetics, having a large amount of implicit parallelism. Therefore, genetic algorithms are part of the broader class of evolutionary algorithms that can be applied to the optimization of complex algorithms, the training of text classification systems, and the evolution of intelligent artificial agents in stochastic environments. With these observations, genetic algorithms perform search in complex, large, and multimodal landscapes and provide near-optimal solutions for objective or fitness function of an optimization problem.Figure5 depicts the basic module process of GA [18], which is illustrated in detail as follows:(i)
The first step to develop a GA for an optimization problem is to represent it. Therefore, the solution is in the form of a string of bits which consists of the same number of element.(ii)
An initial population is normally generated randomly which should be spread over enough of the search space to represent as wide a variety of solutions as possible.(iii)
The selection allows strings to be copied for possible inclusion in the next generation, where the standard for the selection is that of the fitness of all individuals.(iv)
The crossover is applied to two chromosomes and creates two new chromosomes by selecting a random position.(v)
Selection and crossover alone can generate a staggering amount of differing strings.(vi)
The stopping criterion can be set by the number of evolution cycles, the amount of variation of individuals between different generations, or a predefined value of fitness.Figure 5
Basic module process of GA.


## 3.2. Routing Exploration

In this paper, the proposed protocol is based on IBR with GA, and vehicles are equipped with GPS and navigation system. Adopting traffic information to predict the vehicle moving direction, GABR protocol selects the next-hop intersection dynamically. Meanwhile, vehicles utilize carry-forward strategy to deliver packets on the road segment. The proposed routing exploration integrates locating destinations with finding connected paths between source and destination. It means that, to gather the available information along the routes, the source vehicle broadcasts the request packets to the destination. After receiving the request packets, accordingly, the destination confirms the best routing path which will be replied to the source.


## 3.3. Genetic Operations

In this subsection, the main flow chart of our proposed routing algorithm with GA is introduced as shown in Figure6. To begin with, all improvable paths are probed by IBR. Subsequently, genetic algorithm is utilized in the global optimization of available paths to acquire the path with optimal QoS. All available paths are optimized by GA repeatedly with five steps to find optimal QoS path, which are shown as follows.Figure 6
Flow chart of GABR protocol.(a)Code: a given route between the source and destination nodes is equal to an individual, i.e., the serial number sequence of intersections of the route is a chromosome, which can be encoded directly. Therefore, this coding scheme avoids the route circulation due to that the variation length of the chromosome and the total numbers are less than the amount of intersections.(b)Initialize the population: according to the route selection strategy based on IBR, G paths are explored as an initial population and with the corresponding size.(c)Selection: the pros and cons of individuals depend on the fitness value in GA, where the fitness value represents the QoS performance. With the increasing fitness, the QoS performance should be also correspondingly improved. An individual has more fitness value, which means that the individual is excellent and the corresponding path is optimal. Therefore, the fitness function can be expressed as follows:(3)S=αPn+βDnth,where Pn and Dnth denote the connectivity probability and average delay of n-th individual and α and β are weight parameters with α,β∈0,1, respectively.In this step, we propose to combine the optimal strategical selection and roulette wheel selection to rank all paths. Before each pair of chromosome crossing, the optimal individual replaces the worst one and becomes an offspring individual according to the fitness value. Then, the rest of the population uses the roulette wheel method, where the individual with higher fitness value is selected by greater probability.(d)Crossover: crossover operator is used to exchange the subpath of two individuals. As shown in Figure 7, P1 and P2 paths are selected as parents. These alternative crossing positions should be randomly selected as the crossing sites, which are both in parents. Remarkably, two new offspring, P1′ and P2′, take shapes after exchanging all nodes and the crossing site.Figure 7
Example of crossover.(e)Mutation: mutation operator is applied to the randomly select the solution P from the population, which is with small random changes in the solution. We further consider that the node ni selected randomly from P for mutation is called mutation node. The operation details in Figure 8 can be summarized as follows.Figure 8
Example of mutation.Step 1.
Select a nodenj from the neighbors of mutation node ni.Step 2.
Generate two random paths (r1,r2) from the source node to node nj and from node nj to destination node, respectively.Step 3.
If there is a duplication nodes inr1, r2, discard the path, and do not perform mutation on it; otherwise, these two routes are connected with each other to form a new mutated chromosome P′.Step 4.
Repeat the process of the selection, crossover, and mutation until reaching the maximum number of iterations or the route paths are optimized.


## 4. Analysis of QoS Model

In this section, in order to characterize the superiority of our proposed scheme, we analyze the performance of the proposed scenario in terms of the connectivity probability and the transmission delay.


### 4.1. Analysis of Connectivity Probability

As shown in Figure2, two consecutive vehicles Ve and Ve+1 on the eastbound lane are disconnected due to the distance x>R. Using the vehicles on the opposite lane, the broken link between Ve and Ve+1 can be repaired by the vehicles (Vw,Vw+1). Clearly, the corresponding probability for a broken link between Ve and Ve+1 can be expressed as(4)Ξj=1,ifxi≤R,1-PK=0xi/aR,ifxi>R,where PK=0=e-aRλ with λ=λ2 denotes the vehicle density on the westbound lane. Denote that M is the number of broken links on the eastbound lane, and the road segment Iij is connected if broken links are completely fixable. For m=1,2,…,N-1, the conditional connectivity probability Pc∣MM=m can be written as(5)Pc∣MM=m=∏i=1mPfi=1-e-aRλ2Σi=1mxi/aR=1-e-aRλ2L/aR-N-1-m/aRλ1,where N stands for the number of vehicles on the eastbound lane.WhenM=m broken links exist among N-1 links on the lane, the Probability Mass Function PMM=m follows the binomial distribution which is given as(6)PMM=m=N-1mPbm1-pbN-1-m.From (6), it is easy to see that, for the case of at least one broken link existing on the eastbound lane (m≥1), the connectivity probability of the road segment can be expressed as(7)Pc1=∑m=1N-1Pc∣MM=mPMM=m.On the other hand, 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 is given as(8)Pc2i,j=1-eaRλ1L/aR.Based on the above analysis, the total connectivity probability of a road segment between the intersection i and the intersection j can be finally represented as(9)Pc1i,j=Pc1+Pc2.


### 4.2. Analysis of Transmission Delay

In this section, the transmission delay of PC and AC will be analyzed which have been mentioned in Section2.


#### 4.2.1. Road Segment with Partly Connected (PC)

From Figure3, the road segment transmission delay Dnp is given as(10)Dnp=LEv¯,where L and Ev¯ denote the road segment length and the average data packets transmission speed on the road segment, respectively.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, data packets are carried by a forwarding vehicle with vehicle speedv1 until next neighboring vehicle to be connected. In the connection phase, data packets are propagated at wireless transmission speed v1,hop, which can be represented as(11)v1,hop=aRtp,where tp is the one-hop transmission delay [19].Referring to the alternating renewal process theorem as shown in [20], the long-run probability of data transmission time spent in disconnected phase is given as(12)Pd,p=Td,pTd,p+Tc,p=11+dc,pv1/dd,pv1,hop,where Td,p, Tc,p, and dd,p, dc,p, respectively, indicate the data packets travelling time and the distances in the disconnected and connected phases. For the connected phase, the probability is deduced as(13)Pc,p=Tc,pTd,p+Tc,p=11+dd,pv1,hop/dc,pv1.Comprehensivizing (11), (12), and (13), we have(14)Ev¯=v1Pd,p+v1,hopPc,p=dd,p+dc,pv1v1,hopdd,pv1,hop+dc,pv1.Further substituting (14) back into (13), the road segment transmission delay can be obtained as(15)Dn,p=Ldd,paR+dc,pv1tpdd,p+dc,pv1aR.(a) Disconnected Phase.As shown in Figure 3, the forwarding vehicle Vk and the next consecutive vehicle Vk+1 on the eastbound lane are disconnected due to the distance x>R. With this observation, the data packets are carried by vehicle Vk until the connectivity between Vk and the neighbor vehicle is set up.The corresponding distance on the westbound lane betweenVk and Vk+1 is connected, i.e., x/aR consecutive blocks are occupied by at least one vehicle. Therefore, the number of blocks traversed by Vk is given as(16)En=1-pax/aR1-papax/aR-xaRv1v1+v2,where pa=1-e-aRλ2 denotes the probability that each block has at least one vehicle on the westbound lane.The link betweenVk and Vk+1 is broken if at least one block on the westbound lane is vacant along the gap x, for x>R. The disconnection probability between Vk and Vk+1 is given as follows:(17)PC¯∣X=x==0,ifx≤R,1-pax/aR,ifx>R.Noting that the probability density function (PDF) of the vehicles on the eastbound lane fX(x)=λ1e-λ1x, the disconnection probability can be expressed as(18)PC¯=∫0∞PC¯∣X=xfXxdx.Based on which, the average distance of data transmission in disconnected phase is given as(19)dd,p=∫0∞aREnfXxPC¯∣X=xPC¯.Substituting (16)–(18) back into (19), the final expression of dd,p can be obtained.(b) Connected Phase. In the connected phase, vehicles are connected with each other and data packets are transmitted at the speed v1,hop. The transmission distance is divided into two parts.In the first part, as shown in Figure3, consecutive eastbound vehicles are connected if the distance between them is no more than R, and/or even if the distance is greater than R, each westbound block within the distance is occupied by at least one vehicle. In this case, the expected transmission distance between two consecutive vehicles on the eastbound lane is obtained as(20)dd,p=∫0∞aREnfXxPC¯∣X=xPC¯.If y, which is a slack value, consecutive links on the eastbound lane are connected, the transmission distance covered is y·EX∣C. Therefore, the average transmission distance is shown as follows:(21)dd,p,1=∑y=1∞yEX∣CPCy1-PC=EX∣CPC1-PC=EX∣C1-PC¯PC¯.In the second equality, if the gap in the disconnected phase is repaired by the vehicles on the westbound lane successfully, the distance is also traversed by data packets with the speed v1,hop. As shown in Figure 3, with the movement of vehicles, the vacant blocks between VK and VK+1 will be occupied by the vehicles in connected situation 2, and data packets can then be forwarded hop by hop when going through these blocks. Meanwhile, the average distance between VK and VK+1 is deduced as(22)dc,p,1=EX∣C¯=∫0∞xfXxPC¯∣X=xPC¯.Particularly, in terms of the above investigation, the average distance of data transmission in partly connected phase is obtained as(23)dc,p=dc,p,1+dc,p,2.Substituting (21) and (22) back into (24), dc,p can be deduced and the road segment delay can be finally obtained from (15), (19), and (24).


#### 4.2.2. Road Segment with Absolutely Connected (AC)

As shown in Figure4, all links are connected and data packets are delivered by hop and hop greedy algorithm, so the transmission delay between adjacent intersections i and j is given as(24)Dnc=Hnctp,where Hnc=L/aR and tp present the number of hops in the road segment and the transmission delay of one hop, respectively. According to above analysis, the average transmission delay between two adjacent intersections i and j is deduced as follows:(25)Di,j=Dnp1-Pci,j+DncPci,j,where Pc(i,j) means the connectivity probability of the road segment.Figures9–11 show the impact of communication range, the number of vehicles, and vehicles speed on the average transmission delay on the road segment, respectively. As shown in Figure 9, the average delay is given as a function of communication range and the vehicle density in a two-lane scenario. In this scenario, the vehicle speed v1=10 m/s and v2=25 m/s, the road segment length L=2000 m, and vehicle density λ1=λ2=λ, respectively. With vehicle density λ1=0.01,0.02,0.03,0.04 vehicles/m, we can deduce these rules as follows: (1) increased communication range has low average delay with the constant vehicle density; (2) high vehicle density has low average delay with the fixed communication range. In Figure 10, the average delay is shown as a function of the number of vehicles and length of road segment. In this scenario, communication range R=200 m, vehicle speed v1=10 m/s, v2=25 m/s, respectively, and road segment length L=1000,1500,2000,2500 m. These curves show that longer road segment length gets high average delay in the terms of the fixed number of vehicles and that more vehicles have lower average delay with the same road segment length. As shown in Figure 11, the average delay is given as a function of vehicle speed and vehicle density. In this scenario, road segment length L=2000 m, communication range R=200 m, and vehicle density λ1=λ2=λ=0.01,0.02,0.03, and 0.04 vehicles/m, respectively. From the figure, we observe that the fast vehicles have lower average delay with the same vehicle density and that more vehicles get low average delay in two-lane road segment with the same vehicle speed. In addition, it also shows the variation trend between the average delay and different variables.Figure 9
Average delay of road segments for different communication rangesR.Figure 10
Average delay of road segments for different numbers of vehicles.Figure 11
Average delay of road segments for different vehicle speeds.


## 4.1. Analysis of Connectivity Probability

As shown in Figure2, two consecutive vehicles Ve and Ve+1 on the eastbound lane are disconnected due to the distance x>R. Using the vehicles on the opposite lane, the broken link between Ve and Ve+1 can be repaired by the vehicles (Vw,Vw+1). Clearly, the corresponding probability for a broken link between Ve and Ve+1 can be expressed as(4)Ξj=1,ifxi≤R,1-PK=0xi/aR,ifxi>R,where PK=0=e-aRλ with λ=λ2 denotes the vehicle density on the westbound lane. Denote that M is the number of broken links on the eastbound lane, and the road segment Iij is connected if broken links are completely fixable. For m=1,2,…,N-1, the conditional connectivity probability Pc∣MM=m can be written as(5)Pc∣MM=m=∏i=1mPfi=1-e-aRλ2Σi=1mxi/aR=1-e-aRλ2L/aR-N-1-m/aRλ1,where N stands for the number of vehicles on the eastbound lane.WhenM=m broken links exist among N-1 links on the lane, the Probability Mass Function PMM=m follows the binomial distribution which is given as(6)PMM=m=N-1mPbm1-pbN-1-m.From (6), it is easy to see that, for the case of at least one broken link existing on the eastbound lane (m≥1), the connectivity probability of the road segment can be expressed as(7)Pc1=∑m=1N-1Pc∣MM=mPMM=m.On the other hand, 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 is given as(8)Pc2i,j=1-eaRλ1L/aR.Based on the above analysis, the total connectivity probability of a road segment between the intersection i and the intersection j can be finally represented as(9)Pc1i,j=Pc1+Pc2.


## 4.2. Analysis of Transmission Delay

In this section, the transmission delay of PC and AC will be analyzed which have been mentioned in Section2.


### 4.2.1. Road Segment with Partly Connected (PC)

From Figure3, the road segment transmission delay Dnp is given as(10)Dnp=LEv¯,where L and Ev¯ denote the road segment length and the average data packets transmission speed on the road segment, respectively.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, data packets are carried by a forwarding vehicle with vehicle speedv1 until next neighboring vehicle to be connected. In the connection phase, data packets are propagated at wireless transmission speed v1,hop, which can be represented as(11)v1,hop=aRtp,where tp is the one-hop transmission delay [19].Referring to the alternating renewal process theorem as shown in [20], the long-run probability of data transmission time spent in disconnected phase is given as(12)Pd,p=Td,pTd,p+Tc,p=11+dc,pv1/dd,pv1,hop,where Td,p, Tc,p, and dd,p, dc,p, respectively, indicate the data packets travelling time and the distances in the disconnected and connected phases. For the connected phase, the probability is deduced as(13)Pc,p=Tc,pTd,p+Tc,p=11+dd,pv1,hop/dc,pv1.Comprehensivizing (11), (12), and (13), we have(14)Ev¯=v1Pd,p+v1,hopPc,p=dd,p+dc,pv1v1,hopdd,pv1,hop+dc,pv1.Further substituting (14) back into (13), the road segment transmission delay can be obtained as(15)Dn,p=Ldd,paR+dc,pv1tpdd,p+dc,pv1aR.(a) Disconnected Phase.As shown in Figure 3, the forwarding vehicle Vk and the next consecutive vehicle Vk+1 on the eastbound lane are disconnected due to the distance x>R. With this observation, the data packets are carried by vehicle Vk until the connectivity between Vk and the neighbor vehicle is set up.The corresponding distance on the westbound lane betweenVk and Vk+1 is connected, i.e., x/aR consecutive blocks are occupied by at least one vehicle. Therefore, the number of blocks traversed by Vk is given as(16)En=1-pax/aR1-papax/aR-xaRv1v1+v2,where pa=1-e-aRλ2 denotes the probability that each block has at least one vehicle on the westbound lane.The link betweenVk and Vk+1 is broken if at least one block on the westbound lane is vacant along the gap x, for x>R. The disconnection probability between Vk and Vk+1 is given as follows:(17)PC¯∣X=x==0,ifx≤R,1-pax/aR,ifx>R.Noting that the probability density function (PDF) of the vehicles on the eastbound lane fX(x)=λ1e-λ1x, the disconnection probability can be expressed as(18)PC¯=∫0∞PC¯∣X=xfXxdx.Based on which, the average distance of data transmission in disconnected phase is given as(19)dd,p=∫0∞aREnfXxPC¯∣X=xPC¯.Substituting (16)–(18) back into (19), the final expression of dd,p can be obtained.(b) Connected Phase. In the connected phase, vehicles are connected with each other and data packets are transmitted at the speed v1,hop. The transmission distance is divided into two parts.In the first part, as shown in Figure3, consecutive eastbound vehicles are connected if the distance between them is no more than R, and/or even if the distance is greater than R, each westbound block within the distance is occupied by at least one vehicle. In this case, the expected transmission distance between two consecutive vehicles on the eastbound lane is obtained as(20)dd,p=∫0∞aREnfXxPC¯∣X=xPC¯.If y, which is a slack value, consecutive links on the eastbound lane are connected, the transmission distance covered is y·EX∣C. Therefore, the average transmission distance is shown as follows:(21)dd,p,1=∑y=1∞yEX∣CPCy1-PC=EX∣CPC1-PC=EX∣C1-PC¯PC¯.In the second equality, if the gap in the disconnected phase is repaired by the vehicles on the westbound lane successfully, the distance is also traversed by data packets with the speed v1,hop. As shown in Figure 3, with the movement of vehicles, the vacant blocks between VK and VK+1 will be occupied by the vehicles in connected situation 2, and data packets can then be forwarded hop by hop when going through these blocks. Meanwhile, the average distance between VK and VK+1 is deduced as(22)dc,p,1=EX∣C¯=∫0∞xfXxPC¯∣X=xPC¯.Particularly, in terms of the above investigation, the average distance of data transmission in partly connected phase is obtained as(23)dc,p=dc,p,1+dc,p,2.Substituting (21) and (22) back into (24), dc,p can be deduced and the road segment delay can be finally obtained from (15), (19), and (24).


### 4.2.2. Road Segment with Absolutely Connected (AC)

As shown in Figure4, all links are connected and data packets are delivered by hop and hop greedy algorithm, so the transmission delay between adjacent intersections i and j is given as(24)Dnc=Hnctp,where Hnc=L/aR and tp present the number of hops in the road segment and the transmission delay of one hop, respectively. According to above analysis, the average transmission delay between two adjacent intersections i and j is deduced as follows:(25)Di,j=Dnp1-Pci,j+DncPci,j,where Pc(i,j) means the connectivity probability of the road segment.Figures9–11 show the impact of communication range, the number of vehicles, and vehicles speed on the average transmission delay on the road segment, respectively. As shown in Figure 9, the average delay is given as a function of communication range and the vehicle density in a two-lane scenario. In this scenario, the vehicle speed v1=10 m/s and v2=25 m/s, the road segment length L=2000 m, and vehicle density λ1=λ2=λ, respectively. With vehicle density λ1=0.01,0.02,0.03,0.04 vehicles/m, we can deduce these rules as follows: (1) increased communication range has low average delay with the constant vehicle density; (2) high vehicle density has low average delay with the fixed communication range. In Figure 10, the average delay is shown as a function of the number of vehicles and length of road segment. In this scenario, communication range R=200 m, vehicle speed v1=10 m/s, v2=25 m/s, respectively, and road segment length L=1000,1500,2000,2500 m. These curves show that longer road segment length gets high average delay in the terms of the fixed number of vehicles and that more vehicles have lower average delay with the same road segment length. As shown in Figure 11, the average delay is given as a function of vehicle speed and vehicle density. In this scenario, road segment length L=2000 m, communication range R=200 m, and vehicle density λ1=λ2=λ=0.01,0.02,0.03, and 0.04 vehicles/m, respectively. From the figure, we observe that the fast vehicles have lower average delay with the same vehicle density and that more vehicles get low average delay in two-lane road segment with the same vehicle speed. In addition, it also shows the variation trend between the average delay and different variables.Figure 9
Average delay of road segments for different communication rangesR.Figure 10
Average delay of road segments for different numbers of vehicles.Figure 11
Average delay of road segments for different vehicle speeds.


## 4.2.1. Road Segment with Partly Connected (PC)

From Figure3, the road segment transmission delay Dnp is given as(10)Dnp=LEv¯,where L and Ev¯ denote the road segment length and the average data packets transmission speed on the road segment, respectively.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, data packets are carried by a forwarding vehicle with vehicle speedv1 until next neighboring vehicle to be connected. In the connection phase, data packets are propagated at wireless transmission speed v1,hop, which can be represented as(11)v1,hop=aRtp,where tp is the one-hop transmission delay [19].Referring to the alternating renewal process theorem as shown in [20], the long-run probability of data transmission time spent in disconnected phase is given as(12)Pd,p=Td,pTd,p+Tc,p=11+dc,pv1/dd,pv1,hop,where Td,p, Tc,p, and dd,p, dc,p, respectively, indicate the data packets travelling time and the distances in the disconnected and connected phases. For the connected phase, the probability is deduced as(13)Pc,p=Tc,pTd,p+Tc,p=11+dd,pv1,hop/dc,pv1.Comprehensivizing (11), (12), and (13), we have(14)Ev¯=v1Pd,p+v1,hopPc,p=dd,p+dc,pv1v1,hopdd,pv1,hop+dc,pv1.Further substituting (14) back into (13), the road segment transmission delay can be obtained as(15)Dn,p=Ldd,paR+dc,pv1tpdd,p+dc,pv1aR.(a) Disconnected Phase.As shown in Figure 3, the forwarding vehicle Vk and the next consecutive vehicle Vk+1 on the eastbound lane are disconnected due to the distance x>R. With this observation, the data packets are carried by vehicle Vk until the connectivity between Vk and the neighbor vehicle is set up.The corresponding distance on the westbound lane betweenVk and Vk+1 is connected, i.e., x/aR consecutive blocks are occupied by at least one vehicle. Therefore, the number of blocks traversed by Vk is given as(16)En=1-pax/aR1-papax/aR-xaRv1v1+v2,where pa=1-e-aRλ2 denotes the probability that each block has at least one vehicle on the westbound lane.The link betweenVk and Vk+1 is broken if at least one block on the westbound lane is vacant along the gap x, for x>R. The disconnection probability between Vk and Vk+1 is given as follows:(17)PC¯∣X=x==0,ifx≤R,1-pax/aR,ifx>R.Noting that the probability density function (PDF) of the vehicles on the eastbound lane fX(x)=λ1e-λ1x, the disconnection probability can be expressed as(18)PC¯=∫0∞PC¯∣X=xfXxdx.Based on which, the average distance of data transmission in disconnected phase is given as(19)dd,p=∫0∞aREnfXxPC¯∣X=xPC¯.Substituting (16)–(18) back into (19), the final expression of dd,p can be obtained.(b) Connected Phase. In the connected phase, vehicles are connected with each other and data packets are transmitted at the speed v1,hop. The transmission distance is divided into two parts.In the first part, as shown in Figure3, consecutive eastbound vehicles are connected if the distance between them is no more than R, and/or even if the distance is greater than R, each westbound block within the distance is occupied by at least one vehicle. In this case, the expected transmission distance between two consecutive vehicles on the eastbound lane is obtained as(20)dd,p=∫0∞aREnfXxPC¯∣X=xPC¯.If y, which is a slack value, consecutive links on the eastbound lane are connected, the transmission distance covered is y·EX∣C. Therefore, the average transmission distance is shown as follows:(21)dd,p,1=∑y=1∞yEX∣CPCy1-PC=EX∣CPC1-PC=EX∣C1-PC¯PC¯.In the second equality, if the gap in the disconnected phase is repaired by the vehicles on the westbound lane successfully, the distance is also traversed by data packets with the speed v1,hop. As shown in Figure 3, with the movement of vehicles, the vacant blocks between VK and VK+1 will be occupied by the vehicles in connected situation 2, and data packets can then be forwarded hop by hop when going through these blocks. Meanwhile, the average distance between VK and VK+1 is deduced as(22)dc,p,1=EX∣C¯=∫0∞xfXxPC¯∣X=xPC¯.Particularly, in terms of the above investigation, the average distance of data transmission in partly connected phase is obtained as(23)dc,p=dc,p,1+dc,p,2.Substituting (21) and (22) back into (24), dc,p can be deduced and the road segment delay can be finally obtained from (15), (19), and (24).


## 4.2.2. Road Segment with Absolutely Connected (AC)

As shown in Figure4, all links are connected and data packets are delivered by hop and hop greedy algorithm, so the transmission delay between adjacent intersections i and j is given as(24)Dnc=Hnctp,where Hnc=L/aR and tp present the number of hops in the road segment and the transmission delay of one hop, respectively. According to above analysis, the average transmission delay between two adjacent intersections i and j is deduced as follows:(25)Di,j=Dnp1-Pci,j+DncPci,j,where Pc(i,j) means the connectivity probability of the road segment.Figures9–11 show the impact of communication range, the number of vehicles, and vehicles speed on the average transmission delay on the road segment, respectively. As shown in Figure 9, the average delay is given as a function of communication range and the vehicle density in a two-lane scenario. In this scenario, the vehicle speed v1=10 m/s and v2=25 m/s, the road segment length L=2000 m, and vehicle density λ1=λ2=λ, respectively. With vehicle density λ1=0.01,0.02,0.03,0.04 vehicles/m, we can deduce these rules as follows: (1) increased communication range has low average delay with the constant vehicle density; (2) high vehicle density has low average delay with the fixed communication range. In Figure 10, the average delay is shown as a function of the number of vehicles and length of road segment. In this scenario, communication range R=200 m, vehicle speed v1=10 m/s, v2=25 m/s, respectively, and road segment length L=1000,1500,2000,2500 m. These curves show that longer road segment length gets high average delay in the terms of the fixed number of vehicles and that more vehicles have lower average delay with the same road segment length. As shown in Figure 11, the average delay is given as a function of vehicle speed and vehicle density. In this scenario, road segment length L=2000 m, communication range R=200 m, and vehicle density λ1=λ2=λ=0.01,0.02,0.03, and 0.04 vehicles/m, respectively. From the figure, we observe that the fast vehicles have lower average delay with the same vehicle density and that more vehicles get low average delay in two-lane road segment with the same vehicle speed. In addition, it also shows the variation trend between the average delay and different variables.Figure 9
Average delay of road segments for different communication rangesR.Figure 10
Average delay of road segments for different numbers of vehicles.Figure 11
Average delay of road segments for different vehicle speeds.


## 5. Simulation Results

In this section, we examine the performance of our proposed GABR protocol with IBR and CAR [5], where the simulation scenario is urban road, and simulation parameters are given in Table 1.Table 1
Settings of simulation parameters.
Parameters Value Road segment length 2000 m Road width 6 m Communication range 200 m Vehicle velocity 10–25 m/s Iterations 100 Crossover operator 0.4–0.99 Mutation operator 0.0001–0.1 mFigure12 depicts the average transmission delay as a function of communication range. The figure shows that GABR provides the lowest transmission delay compared with IBR and CAR. In the case of CAR, which cannot adopt rapid topology changes, it results in slow packets transmission. IBR is based on intersection routing protocol but cannot consider vehicles density, which results in high transmission delay. The proposed routing protocol divides the road into several blocks and analyzes average delay by considering the connectivity, and it can utilize GA to find the optimal route paths.Figure 12
Packet delay.Figure13 shows that the packets delivery ratio as a function of number of vehicles on the road segment. It is found that more vehicles can significantly reduce the loss of packets. It is clear that the GABR provides better performance of delivering packets when compared with the other two protocols. Specifically, GABR obtains real-time traffic information, divides roads into several blocks, and analyzes road connectivity to select next-hop intersection dynamically. Moreover, the proposed scheme uses GA to optimize routes for successful delivery of packets. In the case of IBR, packets may be lost because of ignoring road connectivity. It is pointed out that CAR is based on source node routing protocol but cannot deal with protean topology changes, which results frequent loss of packets.Figure 13
Packet delivery ratio.


## 6. Conclusions

In this paper, a genetic algorithm based QoS perception routing protocol, namely, GABR is proposed for VANETs, where each improvable path is probed by IBR protocol and road segments are divided into several blocks. In our proposed scheme, vehicles between two adjacent intersections utilized greedy carry-forward algorithm to deliver packets. In addition, genetic algorithm is employed to find the path with optimal QoS in the global available paths. The simulation results validated that GABR protocol is superior to the IBR and CAR protocols in terms of packets transmission delay and the packet loss rate. However, it is worth noting that our proposed scheme is complex to program in GA, and the speed of searching is slower. In our future work, we will focus on combining genetic algorithm with other heuristic bionic algorithms to speed up the optimization.



---

*Source: 3897857-2018-06-11.xml*