Research and Optimization of GPSR Routing Protocol for Vehicular Ad-Hoc Network

Jianming Cui,Liang Ma,Ruirui Wang,Ming Liu

1 School of Information Engineering,Chang’an University,Xi’an 710064,China

2 National Computer Network Emergency Response Technical Team/Coordination Center of China,Beijing 100029,China

*The corresponding author,email:liuming@cert.org.cn

Abstract:Security is one of the most critical issues to Vehicular Ad-hoc Networks(VANETs)since the information transmitted is asynchronous and distributed.Vulnerability and instability are two of the challenges remain to be addressed by the research community and the industry.In this paper,we frst proposed a trust reliability based model and extended the GPSR protocol to TM-GPSR protocol.Then,we improved the LET-GPSR protocol based on the link connection time prediction.On this basis,combined the decision index of the TM-GPSR and LET-GPSR protocols,we proposed the RC-GPSR routing protocol.We built the standard testing platform on the NS2 and SUMO,the average end-to-end delay and packet delivery rate of GPSR protocol and the three updates protocols under different node density,node speed,and malicious node ratio are simulated and evaluated.The results showed that under the same conditions,compared with GPSR protocol,RC-GPSR protocol has a lower average endto-end delay and a higher packet delivery rate,which effectively improves the link stability and security.

Keywords:VANET;GPSR protocol;trust reliability;link connection time

I.INTRODUCTION

According to statistics,by the end of 2021,the number of vehicles in China are exceed 290 million,which brings serious safety problems[1].Vehicular Ad-hoc Network(VANET)is a multi-hop distributed wireless Ad-hoc network,which can improve road traffc safety by establishing communication links between vehicles and roadside units[2].The instability of VANET communication link is one of the important technical issues to be improved.Under the premise of ideal communication distance of 250 meters,when the average speed of vehicles reaches 27.8m/s,the probability of communication link between vehicles being stable is less than 57%[3].It is an effcient method to improve the stability of VANET communication links by improving the routing protocols[4].Trust model is one of the important means to optimize the routing protocols and construct the security of communication link,many achievements applicable for VANET have been proposed[5].These efforts can be divided into two categories:message-based and node-based[6].The former are generally applied to broadcast communication in transportation systems,which evaluates the instant messages based on preset trust degree and with less resources consumption[7].However,due to the mandatory connection requirements of the trust management center,the quality of network service has a signifcant impact on the application and the overall security state[8].The latter are based on real-time trust accumulation and are affected by network quality because there is no trust management center.

In this paper,we focused on the security issues emerged in VANET,and the main contributions are as follows:First,we considered trust reliability and trust initialization of vehicles,introduced the punishment and incentive mechanisms,and established a reasonable set of decision-making indicators,then proposed a trust reliability based model.Based on this model,we extended Greedy Perimeter Stateless Routing(GPSR)protocol to Trust Model-based GPSR(TM-GPSR)protocol,which can solve the security issues such as malicious node cooperative fraud.Then,the link connection time prediction model is introduced to optimize the GPSR protocol,and the Link Expiration Time GPSR(LET-GPSR)protocol is obtained.Finally,comprehensively considered the communication stability and security,we integrated the link connection time prediction model and trust reliability based model to improve the GPSR protocol,then obtained the Reliable and Credible GPSR(RC-GPSR)protocol.By using the NS-2 and SUMO co-simulation platforms,the improved LET-GPSR,TM-GPSR,Reliable and RC-GPSR protocol and the original GPSR routing protocol are simulated.The simulation results shown that the RC-GPSR protocol can effectively improve the link stability and security.

II.OPTIMIZED GPSR PROTOCOL BASED ON TRUST MODEL

2.1 GPSR Protocol

Karp frst proposed the original GPSR protocol,its implementation mainly includes two methods of data forwarding,the former is to fnd the one-hop neighbor node closest to the destination location,and then forward packets to this node.The latter is the supplement of the former,that is,to solve the dilemma of how to carry out data packet forwarding in the area where greedy forwarding fails[9].The advantage of GPSR is that it only needs to store the state of one-hop neighbor nodes,and the routing cost is relatively lower.Moreover,with the increase of network scales,GPSR has stronger scalability compared with traditional routing protocols.Even if the nodes move frequently,GPSR can still quickly fnd alternative routes nodes based on the information of one-hop neighbor nodes.

Although GPSR protocol has great advantages and has been applied,it still has many technical defects to be solved.First of all,although the right-handed rule can ensure data forwarding and avoid routing void,the decision made by the right-handed rule will be somewhat arbitrary,which may cause a large routing burden.Secondly,due to the lack of balanced use of the remaining energy of nodes,it is easy to cause the failure of some routing nodes.Thirdly,the peripheral forwarding mode of GPSR protocol is based on the realtime plane topology,and it needs to be reconstructed before each execution,which has high computational complexity and consumes a lot of energy[5].

Figure 1.Trust model architecture diagram.

However,we still believe that GPSR protocol can play a better role in VANET,that is,a distributed mobile network can be automatically established by forwarding information,control instructions,own status,data packets and other information between vehicles.Therefore,how to make the network stable and reliable communication has become the focus of this feld,that is,how to design a better routing protocol to achieve stable data transmission under the dynamic network has become one of the primary technical issues to be solved by the application of GPSR protocol.

2.2 Reliability Based Trust Model

The architecture of reliability based trust model is in fgure 1.The nodes indicate vehicles and roadside units,which node that is currently looking for the next hop node is called the source node,and the node being searched is called the candidate relay node to be selected.The main work steps are as follows:

·Step 1:Source nodeAtraverses to read the node information in the neighbor table.

·Step 2:Acalculate the direct trust based on local communication history,and requests the trust degree of candidate relay node from the neighbor node and the roadside unit(RSU)within the communication range,and then calculates the indirect trust.Finally,the comprehensive trust is calculated according to the weight aggregation rules.

·Step 3:DetermineCaccording to the decision algorithm.Then,Acommunicates withC.

·Step 4:After the communication,Aevaluates the service quality,and feeds it back to the RSU within the communication range.

2.3 Trust Value Calculation

2.3.1 Direct Trust

Direct trust can be evaluated according to the historical communication data between the source node and the candidate relay node.LetsSiA,Cdenotes thei-th interaction satisfaction degree between nodeAand nodeC,which would decay with time.e-λ(tiA,C-t)is the time attenuation factor,tiA,Crepresents the completion time of thei-th interaction,trepresents the current time andλis the impact factor[10].The calculation process of direct trust is as follows:

·Step 1:Query the historical communication table and read historical communication information.The source nodeAqueries the historical communication table to determine whether there is historical communication with nodeC.If there is no historical communication,the satisfaction degree is 0.If there is,all historical communication completion timeand historical communication satisfaction degreeare read.

·Step 2:Calculate the direct trust of the candidate relay node.Considering the infuence of time and communication times on direct trust,the direct trustfromAto the candidate relay nodeCis obtained.The calculation is equation(1),whereNis the total number of communication times.When there is no communication history,the direct trust of the source node to the candidate relay node is zero.WhenN＞0,it has andN=0,=0.

·Step 3:Calculate the reliability of the direct trust of the candidate relay node.The calculation equation(2)is the direct trust reliability of the source nodeAto the candidate relay nodeC.When the discrete degree of direct trust and historical satisfaction is lower,the reliability of direct trust is higher.When there is no communication history,the reliability is 0.WhenN=0,=0,and whenN＞0,it has

2.3.2 Indirect Trust

When the source node and candidate relay node have communication records,the value calculation of trust will be more reliable.When the source node and the candidate relay node have no communication history,the direct trust is 0,and the indirect trust can be a basis for decision-making.In the trust model of this paper,indirect trust is mainly provided by neighbor nodes and roadside unit(RSU).The calculation process of indirect trust is shown in fgure 2.

The calculation steps of indirect trust are as follows:

·Step 1:Send the request.The source nodeAsends a trust request for the candidate relay nodeCto all neighbor nodes and the roadside unit RSU within the communication range.

·Step 2:Read the data.The neighbor node reads its own communication history table,and reads the completion time and satisfaction degree of all communications between it and the candidate relay nodeC.The RSU queries its own local storage and reads the satisfaction feedback of all communications of the candidate relay nodeC.

·Step 3:The neighbor node and the RSU calculate the degree of trust and reliability.The neighbor nodejuses equation(1)to calculate the direct trustof the candidate relay nodeC,and uses equation(2)to calculate the direct trust reliabilityThe RSU uses equation(3)to calculate its trust valueTRSU,Cfor the candidate relay nodeC.

Figure 2.Motion diagram of nodes on different roads.

Hdenotes the number of times that the satisfaction degree ofCis higher than the thresholdη,Ldenotes the number of times lower thanη,Wdenotes the total number of communications,andξdenotes the adjustment factor.Since RSU has high authority,its reliability is counted as 1.WhenW=0,TRSU,Cwill be 0.6,which means that this node has never communicated with other nodes.For example,when a new node just joins the network,give it an initial trust value of 0.6,and then it has the opportunity to forward general types of messages to enhance their trust value.

When the communication process is completed,the service quality of the relay node is evaluated for satisfaction,and then the identity information,satisfaction degree,communication completion time and other communication information of the relay node are recorded to the communication stored locally on the source node In the history table,the information is fed back to the RSU within the communication range at the same time,and the trust value of the relay node is updated.

·Step 4:Calculate indirect trust.The indirect trustfromAtoCcan be calculated according to the way of dynamic weight combination.The calculation method is shown in equation(4),whereMis the number of neighbor nodes.

whereand the value ofβchanges dynamically with the reliability of the trust value,which is more reasonable than the previous method of fxing the weight value[11].

·Step 5:Calculate the reliability of.When the degree of dispersion between the indirect trust value andandTRSU,Cis lower,the reliability of indirect trust is higher,equation(5)is used to calculate the reliability of indirect trust.

whereand the direct trust and indirect trust are calculated according to the dynamic weight combination to obtain the comprehensive trust.The calculation method is shown in equation(6).

whereand it can be found thatωis also a dynamic weight,which can not only aggregate direct trust and indirect trust more reasonably,but also can take the indirect trust as the trust value of the source node to the target node when the source node and the target node have no history of communication,that is,the target node is newly added to the local area network and the direct trust is 0.The trust value is highly adaptive.

2.4 Optimized GPSR Routing Algorithm

In order to eliminate the interference of malicious nodes in VANET,improve the security of communication,and reduce the communication pressure of nodes with high trust,based on the trust model considering the trust reliability,we propse the Trust Model-based GPSR(TM-GPSR).The calculation of the trust value in the decision index is completed by the trust model described in above subsections.The next hop node of a route is determined by the trust degree and message type.The decision algorithm steps are as follows,

·Step 1:Determine a trust thresholdω,and delete candidate relay nodes whose comprehensive trust is lower thanωfrom the current table.

·Step 2:Redetermine the value of the thresholdμand divide the rest nodes into two sets,the high and general reputation sets.

·Step 3:Messages are divided into two categories based on the importance of forwarding messages:important messages and general messages.

·Step 4:When an important message needs to be forwarded,select a node closest to the destination node in the high-reputation node set as the next hop node;when the forwarded message is a general message,the nodes in the two node sets can be To provide services,a node closest to the destination node is selected as the next hop node in the two node sets.

III.IMPROVED GPRS ROUTING PROTOCOL BASED ON PREDICTION

3.1 Link Connection Time Prediction Model

In the aforementioned model,each node would sharing the observed information about the road it is driving[12],and their position state will be divided into two categories according to whether driving on the same road.On this basis,the nodes on the same road are classifed according to their real-time movement direction and relative speed,and then the corresponding formulas are selected respectively to evaluate the link connection time.Theoretically,the angle between the speed directions of the vehicles on the same straight road will only be 0° and 180°,that is,the direction is the same and the direction is opposite,but due to overtaking,lane change,road curvature and other reasons,it will lead to the pinch,which angle is inconsistent with the theory.If the angles between the motion directions of two nodes is acute,the two nodes are regarded as moving in the same direction,and if it is obtuse,the two nodes are regarded as moving in the reverse direction or in opposite directions.

Suppose the connection time of the link between nodesiandjisti,j,nodejis within the communication rangeRof nodeiat timeti,the distance between the two nodes isdi,j,and the position coordinates of nodeiare{xi,yi},the speed isvi,the position coordinates ofjare〈xi,yi〉and the speed isvj.If nodeiand nodejare on the same road.Under different driving conditions,the link connection time of nodeiand nodejis shown in table 1,otherwise,as shown in fgure 3.whereiandjare the position of the node at the current moment,θiis the angle between the speed of nodejand thex-axis,vican be decomposed into horizontal velocityviandθivertical velocityvisinθi,is the angle between the speed of nodejand thex-axis,vjcan be decomposed into horizontal velocityvjcosθjand vertical velocityvjsinθj,iandjare the positions of nodesiandjafter the movement timeti,j,the coordinates ofiandjare(xi+ti,jvicosθi,yi+tivisinθi)and(xj+ti,jvjcosθj,yi+tivjsinθj),respectively.The square of the distance betweeniandjisd2i,jas in equation(7).

Table 1.Link connection schedule.

Figure 3.Motion diagram of nodes on different roads.

Lets denoteR=di,j,x=xi-xjandy=yi-yj,ΔvHor=vicosθi-vjcosθjandΔvV er=visinθivjsinθj,then equation(8)can be written as

SinceΔis always greater than 0,according to the actual physical meaning,the calculation of link connection timeti,jcan be defned as

whereφ=Δv2Hor+Δv2V erandψ=xΔvV eryΔvHor.

3.2 Routing Algorithm

Based on the link connection time prediction model,the greedy forwarding mode is used to forward data packets,and the link stability of the GPSR protocol is improved to obtain the LET-GPSR(Link Expiration Time GPSR)protocol.The algorithm fow chart of the protocol is shown in fgure 4.

In LET-GPSR protocol,a node periodically updates its position,speed and direction information,and then broadcasts hello packets to interact with other nodes.After other nodes having received the hello packet,the node updates the neighbor node information of its neighbor table.And the nodes which are already in the neighbor table,update their node information according to the information of the latest hello packet.In the same time,the nodes that are not in the neighbor table will be inserted into the end of the neighbor table.For the nodes that existed before but have not received their new hellos,they will be deleted.When a source nodeSneeds to forward a data packet,it checks whether there is a neighbor node in its neighbor table.

If not,it forwards the data packet around.If there are neighbor nodes and the number isN,it frst judge whether there is the destination node in the neighbor node according to the destination node id in the data packet which will be forwarded,then if so,the source node directly forwards the data packet to the destination node,and the communication ends.Otherwise,use functiongetdis()to calculate the distancedD,jbetweenjandDvis the neighbor table,and use functiongetLET()to predict the link connection timerS,jbetween the source nodeSand the neighbor nodej,then use equation(10)and equation(11)to normalizedD,jandtS,jtodNorD,jandtNorS,j,respectively.

Figure 4.Motion diagram of nodes on different roads.

The above calculation is used as one of the criteria for the LET-GPSR routing protocol to determine the next hop node,and the link reliabilityis obtained by aggregatingand.Since the neighboring node is closer to the destination node,the better,and the longer the link connection time is,the better,so the link reliabilityis calculated according to equation(12).Finally,the node with the largestvalue is selected as the next hop node.

3.3 RC-GPSR Routing Protocol

Based on the foregoing work,in this section,we integrate the link connection time prediction model and the trust model to improve the GPSR protocol,the main steps of RC-GPSR(Reliable and Credible GPSR)routing protocol are as follows and the workfow is shown in fgure 5.

·Step 1:Determine a trust thresholdξ,and delete candidate relay nodes whose comprehensive trust is lower than this threshold from the set.

·Step 2:Determine a thresholdμand divide the remaining nodes into two sets,one is a highreputation node set,and the other is a generalreputation node set.

·Step 3:Considering that the messages that need to forward could be the messages related to road driving or other messages,the messages are divided into two categories:important and general.

Figure 5.Implementation process of RC-GPSR protocol.

·Step 4:When an important message needs to be forwarded,select a node with the highest link reliability in the high-reputation node set as the next hop node;when the message to be forwarded is a general message,the nodes in the two node sets can provide services,so in the two node sets,a node with the highest link reliability is selected as the next hop node.

3.4 Complexity Analysis

As shown in fgure 4 and fgure 5,we can assume that under normal conditions,the number of nodes in an open network isV,the number of nodes within the selected transmission area isVik,wherekis the number of divided transmission areas andiis the node number,then the average time complexity of the above algorithms will not exceedO(k×V×vik),so the time complexity of peripheral forwarding would be a constantC.On this basis,within a selected region,the computational complexity of each node transmitting probabilistic events isO(vik×vik).

Therefore,it can be seen from the above analysis that the improvement of GPSR protocol does not increase the computational complexity in theory,and objectively still inherits the related advantages of GPSR protocol.In fact,the improved protocol can effectively reduce the number of information forwarding hops,and achieve the purpose of shortening the calculation time and reducing node energy consumption.

IV.EXPERIMENT AND RESULTS

4.1 Comparison Schemes and Metrics

We adopt NS-2.35 and SUMO-0.32.0 to construct the original GPSR,LET-GPSR,TM-GPSR and RC-GPSR protocols in different variable settings,and use two sets of parameter setting schemes,that is,the proportion of malicious nodes was fxed frst,and the performance under different node speed and density Settings was analyzed.Then the speed and density of nodes are fxed to analyze the performance under different proportions of malicious nodes.Specifc as follows:

·Packet Delivery Ratio(PDR)can be denoted as:

Among them,Nsendrepresents the total number of data packets sent by the application layer of the source node,andNrecrepresents the number of data packets received by the destination node.

·Average End to End Delay(E2D)can be denoted as:

whichNrecis the number of data packets received by the destination node,andΔTiis the time difference between the receiving time and the sending time of thei-th data packet.

4.2 Experimental Setting

Since the movement of vehicles are restricted by roads and have certain movement rules,we adopt a random map of 1000m×1500mon OpenStreetMap,as shown in fgure 6.In order to simulate the real situation,vehicle,traffc lights are randomly and evenly distributed on the lanes in the map,and the driving mode can be selected according to the road conditions,and will wait when encountering traffc lights[13].

Figure 6.Map topology of a certain area.

Table 2.Simulation parameters configuration.

The main experimental parameters are in table 2.In order to test the impact of different node density scenarios on routing performance,the number of nodes is set to 20,40,60,80 and 100,respectively.The maximum speed of the node is set to 5m/s,10m/s,15m/s,20m/sand 25m/s,respectively,to test the infuence of the speed of different nodes on the routing performance.Protocol of the physical layer and the MAC layer use the IEEE 802.11p standard,and the communication range of all nodes is controlled to be 250mby modifying the transmit power and receive power of the physical layer.

4.3 Numerical Results and Analysis

Consdering the malicious nodes,the variables that affect routing performance include node density,node speed,and proportion of malicious nodes.Therefore,the experiment is divided into 3 scenarios:

·Fixed malicious node ratio and node speed.

·Fixed malicious node ratio and node density.

·Fixed node density and node speed.

In order to simulate the malicious nodes and their behaviors,the malicious behaviors are written in the source code of the protocol,and then the nodes are confgured as malicious nodes through Tcl scripts.

Figure 7.The impact of node density changes on PDR(10%malicious nodes).

4.3.1 Fixed Malicious Node Ratio and Node Speed

In this scenario,the proportion of malicious nodes fxed at 10% and the node speed set to 20m/s,PDR and E2D of the four routing protocols were verifed when the number of nodes is 20,40,60,80 and 100,respectively.The average results of different routing protocols is shown in fgure 7.Affected by the malicious nodes,packet delivery rate of LET-GPSR protocol,which only maintains link stability,decreases slightly.RC-GPSR protocol with the trust model can detect and exclude malicious nodes,its packet delivery rate is relatively more stable,which is not much different from the case of no malicious nodes.

The E2D performance of different routing protocols in this scenario is shown in fgure 8.When the nodes are sparse,the average end-to-end delay difference of the routing protocols is not very obvious.When the node density increases,the role of the trust model becomes more and more signifcant.Although the calculation time of RC-GPSR protocol is larger than that of other protocols,its routing algorithm can ensure that data packets are effciently and safely sent to the destination node.However,other protocols cannot guarantee the stability or security of the communication link and have a higher retransmission rate,so the delay is higher than that of the RC-GPSR protocol.

Figure 8.The impact of changes in node density on E2D(10%malicious nodes).

Figure 9.The impact of node speed changes on PDR(10%malicious nodes).

4.3.2 Fixed Malicious Node Ratio and Node Density

In this scenario,with the proportion of malicious nodes fxed at 10% and the number of nodes set to 60,PDR and E2D of the four routing protocols were verifed when the maximum node speed is 5m/s,10m/s,15m/s,20m/sand 25m/srespectively.Then the average of the results of ten experiments will be calculated in each type of node speed.

The PDR performance of different routing protocols is shown in fgure 9,as the speed of nodes increases and the network topology changes faster,the packet delivery rate of the RC-GPSR protocol is slightly reduced,while GPSR is signifcantly reduced.The changes of the packet delivery rate of LET-GPSR and TM-GPSR are equivalent.Because the link stability has a greater impact on routing performance when the proportion of malicious nodes is constant and the speed is faster,the packet delivery rate of the LETGPSR protocol is slightly better than that of the TMGPSR protocol when the speed is high.

Figure 10.The impact of node speed changes on E2D(10%malicious nodes).

The E2D performance of different routing protocols in this scenario is shown in fgure 10.When the node speed is small,the network topology changes slowly and the link is relatively stable.Therefore,in the case of malicious nodes,the TM-GPSR protocol has the lowest latency,and the RC-GPSR protocol is the highest.When the node speed increases,the delay of the RC-GPSR protocol increases less.

Seen from the above four results graphs,which are compared with the routing performance in a malicious node environment,the performances of GPSR and LET-GPSR protocols that not consider the trust model are reduced due to the infuence of malicious nodes,while the performance of the RC-GPSR protocol,which considers the trust model and the link stability,does not change much.

4.3.3 Fixed Node Density and Node Speed

In this scenario,we set the number of nodes to 60,the node speed is fxed at 20m/s,PDR and E2D of the four routing protocols were verifed when the proportion of malicious nodes is 0,5%,10%,15%and 20%respectively.In this scenario,the changes of PDR and E2D of different routing protocols with the proportion of malicious nodes are shown in fgure 11 and fgure 12.

Figure 11. The impact of node density change on PDR(malicious nodes proportion change).

Figure 12. The impact of node density change on E2D(malicious nodes proportion change).

In the case of the same node density and speed,the main factor that affects the packet delivery rate is the proportion of malicious nodes.It can be found that,as the proportion of malicious nodes increases,The packet delivery rate of the data packets is declining and the average of end-to-end delay is rising for the GPSR protocol and LET-GPSR protocol which are the trustless models,while the packet delivery rate and average end-to-end delay of the TM-GPSR protocol and RC-GPSR protocol with trust model are less affected by the proportion of malicious nodes.

The trust model is diffcult to completely exclude attacks from malicious nodes when the proportion of malicious nodes is high,so the delivery rate will also decrease.Among them,because RC-GPSR not only calculates the link reliability to ensure the stability of the link,but also calculates the comprehensive trust value of the node to be selected to ensure the security of communication,so its changes of the packet arrival rate and the average of end-to-end delay are small and the routing performance is relatively stable.

V.CONCLUSION

Aiming at the communication security problem caused by malicious nodes,a trust reliability based model is proposed,and then TM-GPSR protocol which can effectively exclude malicious nodes is improved.In addition,in order to improve the stability of the communication link,the GPSR protocol is improved based on the link connection time prediction,and the LETGPSR protocol is obtained.On this basis,we comprehensively analyzed the link stability and communication security,fuzed the link connectivity time prediction to the trust reliability based model,and then obtained the RC-GPSR protocol,and built the experimental testing bench.The simulation results indicated that compared with GPSR,the proposed LET-GPSR,TM-GPSR and RC-GPSR protocol,in particular,RCGPSR protocol has higher packet delivery rate and lower average end-to-end delay,and is less affected by the proportion of malicious nodes,node speed and node density,it demonstrated good link stability and security and has a good application prospect.However,it can be found that the current studies are all carried out under ideal conditions,facing the randomness characteristics of actual roads,vehicles and links,how to stably adapt the proposed protocols,optimize their performance for different application scenarios and improve their universality are the core issues that need to be paid attention to in the next stage.

ACKNOWLEDGEMENT

This work is fnancially supported by the National Natural Science Foundation of China(No.62106060).