An Efficient Greedy Traffic Aware Routing Scheme for Internet of Vehicles

Belghachi Mohammed and Debab Naouel

Abstract: A new paradigm of VANET has emerged in recent years:Internet of Vehicles(IoV).These networks are formed on the roads and streets between travellers who have relationships,interactions and common social interests.Users of the ese networks exchange information of common interest,for example,traffic jams and dangers on the way.They can also exchange files such as multimedia files.IoV is considered as part of the Internet of Things (IoT) where objects are vehicles,which can create a multitude of services dedicated to the intelligent transportation system.The interest is to permit to all connected vehicles to communicate with each other and/or with a central server,through other vehicles.Vehicle to Vehicle (V2V) communication is the main component,because the services encompassed in the IoV are based on the vehicles in question,such as transmitter,relay and receiver.This work is focusing on designing and developing a Quality of Service (QoS) routing scheme dedicated to IoV networks.Especially,we aim to improve the Greedy Traffic Aware Routing (GyTAR) protocol to support QoS in IoV networks.To evaluate the proposed approach in terms of QoS in the context of IoV networks,the performance metrics such as average end-to-end delay and packet delivery ratio are taken into consideration to analyse the network situation.

Keywords: IoT,IoV,GyTAR,QoS,vehicular traffic density,delay,PDR.

Abbreviations

VANET:Vehicular Ad-Hoc Network

IoT:Internet of Things

IoV:Internet of Vehicles

V2V:Vehicle to Vehicle

V2I:Vehicle to Infrastructure

QoS:Quality of Service

RSU:Road Side Unit

GyTAR:Greedy Traffic Aware Routing

PDR:Packet Delivery Ratio

IFTIS:Infrastructure-Free Traffic Information System

CDP:Cell Density Packet

CBR:Constant Bit Rate

M2M:Machine to Machine

1 Introduction

Today internet knows a new extension with the development of connected objects.Until then,the internet was conceived as the ability of people to communicate at anytime and anywhere;with connected objects,the physical world can now communicate,whether relationships for person-to-person,person-to-object,or objectto-object [Cheng,Cheng,Zhou et al.(2015)].The new era of the IoT has led to the evolution of conventional ad hoc vehicular networks (VANET) towards the IoV paradigm[Gandotra,Jha and Jain (2017)].

The concept of intelligent vehicles has been developed considerably over the last decade.Faced with the emergence of connected vehicles in the automotive industry,many vehicles are equipped with on-board systems,including components to monitor different environmental conditions.The emergence of IoT allows the collection of different types of information from sensors and surrounding systems.The IoT is primarily based on smart objects that work collaboratively and interact instantly with their environments.The emergence of the IoT has opened new perspectives for intelligent transport systems.The concept of IoV of fers an exchange of information between vehicles and any type of surrounding objects (see Fig.1).The new Intelligent Transport Systems (ITS) will use V2V data to improve traffic management,enabling vehicles to communicate with road infrastructure,such as traffic lights or signs.These technologies could help to build more reliable autonomous cars on highways [Liu,Wan and Wang (2016)].

Figure1:IoV architectures

This concept is wider than a VANET which is based on V2V,V2I communication and conventional intelligent transport systems which are mainly based on sensors,cameras throughout the network and remote monitoring centres to detect road traffic anomalies[Huang (2013)].The very fast development of wireless communication technologies has w rought Machine to Machine (M 2M) communication and accelerated the revolution of IoT world in general and intelligent transport systems in particular (see Fig.2).The adoption of IoV architecture is also highly favoured by the development of the smart infrastructure in smart-cities and the adoption of Metropolitan Area Network (MAN).Cellular telecommunications technologies (1G,2G,3G,4G) have also undergone a great evolution in recent years and must play an important role in the IoT and IoV architectures,especially with the advent of 5G technology which will certainly have a primordial role in the evolution of IoV architecture in the coming years.All these performances in terms of communication technologies support the adoption of IoV architecture [Kumar,Vaisla and Sudarshan (2016)].

Figure2:Communication modes in IoV

However,IoT architecture is facing many challenges,among which we mention:the standardization of exchange and interoperability between different connected objects and the routing,storage and analysis of massive volumes of data from heterogeneous sources.IoV allows the acquisition and processing of large amounts of data from multipurpose geographic areas via intelligent vehicle platforms [Kaiwartya,Abdullah,Cao et al.(2016)].It of fers various categories of services related to road safety for drivers and passenger com fort.Remediating these constraints is the major challenge of IoV.Note that IoV is closely related to the cloud computing environment because it allows putting into practice the concept of intelligent transport systems.There are many challenges to relieve in IoV.One of the typical challenges is the large volume of data to process and store,this volume is generated by the amount of sensors and vehicles on the roads.The problem is

to investigate the availability,reliability and robustness of communications between IoV agents [Mershad,Artail and Gerla (2012)].The dynamic nature of IoV presents communication constraints,namely frequent disconnections which can be an obstacle to the execution of applications in a vehicle.Indeed,some vehicles are sometimes isolated without the possibility of emission and approval for an indefinite period.This situation affects the quality of service of fered by IoV and therefore its usefulness.According to Bilal et al.[Bilal,Khan and Ali (2016)] some obstacles can cause disconnections in IoV such as:

· The high mobility of vehicles and the rapid change of the network topology,

· The low density of vehicles in urban areas and highway,and the absence of Road Side Unit (RSU) terminals,

· The use of cellular networks with limited coverage for communications,

· Network overhead due to the amount of communicating agents in the IoV,and the limited bandwidth,

· The distributed architecture and remote access to services of fered by IoV,

· The heterogeneity of the entities which constitute the IoV,

· The lack of cooperation between IoV agents and certain infrastructures that can be communication relays (because of different security levels for example),

· The complexity and density of the external environment (forest,building etc.).

2 From VANET to IoV

Wireless communication technologies provide opportunities to deploy a large number of applications in a vehicular environment.These applications are particularly dedicated to road users.Applications aimed at improving road safety are the main target of VANETs.Other applications are dedicated to passenger’s com fort.Road safety applications are the main motivation for vehicle networks,although other applications are considered such as traffic management and entertainment.Multi-hop broadcast communication is an important component of such applications,such as road signalling hazard where multihop broadcast is used to report an accident on the road,an animal presence,an object that blocks the road,sudden braking of the vehicle,etc.As the information processed in these applications is very critical and can have an effect on human life,the diffusion must be fast and reliable.However,broadcasting messages over multi-hop have many challenges namely,redundant retransmissions,high channel load,high contention on the communication channel and thus,a high packet loss rate in the case of a dense network,and the problem of disconnection when the network is sparse.In addition,the delay is a critical constraint for road safety applications and the satisfaction of their requirements is very difficult,as there is a compromise between the reliability of the release and the delivery time [Gerla,Lee and Pau (2014)].Unlike other categories of applications,in security applications,the information processed is very critical,which makes delay and reliability the two important metrics that must be taken into account in the development and evaluation of the protocols developed,for these applications.Besides,all nodes in the event area must be notified and should receive the broadcast message.A “perfect”dissemination mechanism is one that delivers the data to all interested nodes in time and with the best use of resources [Satyajeet,Deshmukh and Dorle (2016)].

3 Routing in IoV

The study and the implementation of routing algorithms to ensure connectivity in such networks,in the classical sense of the term,is a complex problem.The environment is dynamic and evolves over time,so the network topology can change frequently.

It is therefore essential that any routing protocol conception address the subsequent issues[Wan,Liu,Shao et al.(2016)]:

· Minimizing the network overloading:there are two other sub-issues in network resource optimization;avoid routing loops and preclude the focusing of traffic in the vicinity of particular nodes or links.

· of fer assistance for predictable multipoint communications:the fact that the paths used to route the data packets can evolve should not affect the good data routing.Eliminating a link for failure or mobility should ideally increase as possible latency time.

· Guarantee best routing:the routing strategy must create optimal paths and be able to take into account different metrics cost (bandwidth,number of links,network resources,etc.).If the building of best paths is a hard problem,keeping these paths can become yet also challenging.The routing strategy must consequently guarantee pr of icient conservation of routes at lowest cost.

· The latency time:the quality of latency and paths should increase while network connectivity increases.

4 GyTAR overview

GyTAR is a geographic routing protocol that dynamically selects junction based on vehicles traffic density and curvemetric distance to the destination in order to find sturdy and reliable routes in the city.The use of digital maps is useful for finding the position of neighbouring junctions.The junction with the highest score is chosen as the next destination junction based on vehicles traffic density and curvemetric distance to the destination.Therefore,it selects the next junction that is most frequented by the vehicles and that is geographically closest to the destination junction.The main idea of GyTAR is to transmit data packets in the network taking into account the real time variation of the car traffic.It is composed of threemain modules according to Sardar et al.[Sardar,Saad and Uzma (2011)] and which are:

· Junction selection mechanism

· Routing between junctions

· Recovery strategy

4.1 Junctions selection mechanism

In GyTAR,junctions where packets must pass to reach the destination are chosen dynamically;one by one while taking into account the real-time variation of vehicular traffic and curvemetric distance from candidate junction to the destination (see Fig.3).In the case of selecting the next junction,the node identifies candidate junctions (neighbourhood junctions) by the use of the digital map,and then assigns a score to each candidate junctions.The junctions with the highest score are chosen as the next junctions Thus,packets travel between the two junctions having higher directional density,the following figure shows an example of junctions’ selection [Jerbi,Senouci,Meraihi et al.(2007)].

For the score assignment to each candidate junction,the following formula is used

· d(pij):the curvemetric distance across the route portion pijbetween junction i and j

· t(pij):the vehicular traffic density across the route portion pijbetween junction i and j

Figure3:Junction selection mechanism

4.2 Routing between junctions

Once the next junction is set,GyTAR uses the improved greedy forwarding strategy.This strategy consists of finding a closer neighbour at the next intersection using predicted positions based on node speed.In GyTAR,each vehicle maintains a neighbourhood table in which it preserves the geographical position of its neighbours,their speed and their direction of movement.

Figure4:Routing between junctions

When the source vehicle needs to transmit the data packets (see Fig.4),it consults its neighbour table to find the new predicted position of the neighbouring vehicles.When the transfer vehicle wishes to transfer the package to the destination junction at time t1,it consults its neighbour table and finds the vehicle (2) which is the closest vehicle to the destination junction and moves in the same direction as the transmitter vehicle as shown in Fig.4.The vehicle (1) also moves in the same direction;it has a higher speed than the vehicle (2).The transmitter vehicle will know from the neighbour’s that the vehicle (1)exceed the vehicle (2) at time t2 it will become the closest vehicle to the destination.Thus,transmitter vehicle will select the vehicle (1) as a next hop.Without the use of the predictive mechanism,the vehicle (4) will be selected as the next hop [Saini,Leleiwi and Saddik (2015)].

4.3 Recovery strategy

GyTAR’s local recovery solution is based on a “Carry and Forward” approach.It consists in keeping the package at the level of the vehicle itself by exploiting its movement.Thus,the package will be transported by the vehicle until it meets a node closer to the destination or it reaches itself the intersection in question.The sending vehicle or an intermediate vehicle in a junction looks for the position of the neighbouring junctions using the map.A score is given to each junction considering the traffic density and the curvemetric distance to the destination [Joy,Rabsatt and Gerla (2018)].The best destination junction (the junction with the highest score) is the geographically closest junction to the destination vehicle having the highest vehicular traffic.GyTAR utilizes Infrastructure-Free Traffic Information System (IFTIS) to estimate the traffic density between two junctions.Vehicles at an intersection forward broadcast a Cell Density Packet (CDP) to collect real-time vehicular density [Alouache,Nguyen,Aliouat et al.(2018)].GyTAR is based on dynamic selection of junction taking into account the traffic density.This selection mechanism requires at each selection the traffic information for each junction (provided by the Cell Density Packet (CDP) messages).In addition,depending on the functioning of GyTAR,the CDP messages broadcasting is executed if and only when if a vehicle passes in a new route,if it is not the case,there is no information about the candidate junction,by therefore,the routing in this case is done without taking into account the vehicular traffic [Kang,Li,Li et al.(2015)].

5 Proposed approach

The idea of this work is focusing on designing and developing a QoS routing scheme dedicated to IoV networks.Especially,we aim to improve the GyTAR protocol to support QoS in IoV networks.In GyTAR,the diffusion of CDP messages is done if and only if a vehicle enters a new route,if it is not the case;no information is broadcasted.To palliate this disadvantage,we propose a mechanism for broadcasting hello messages periodically.This type of message provides information on the state of the route in the network.It is generated at regular intervals,conventionally;each vehicle broadcast periodically hello message.This message contains the position,speed,direction and route of the transmitting vehicle.Due to these messages,each vehicle creates a local view of its neighbourhood.The vehicle can also predict and anticipate accident or congestion situations.Each vehicle is therefore known from its direct neighbourhood.The main objective of our approach is to propose an improvement of the formula (1) of calculation of the score by taking into consideration other metrics.

5.1 Calculation of relative metrics

The quality factors of a protocol or a routing technique are reflected by performance measurements of the ese techniques and are usually the result of particular metrics measurements.These metrics serve as support for promoting one technique over others.The quality of service is generally based on a number of parameters, of different natures,whose purpose is to specify the needs of users towards service providers.For this purpose,in order to guarantee the quality of service,the network of fers a set of services previously determined and allocated to the users satisfying certain QoS criteria with respect to the end-to-end connection in terms of delay,bandwidth,probability of loss of packets and jitter.For values estimation of relative metric,curvemetric distance and traffic density refer to Belghachi et al.[Belghachi and Feham (2018)].For others metrics delay and packet delivery ratios are calculated as follows:

5.1.1 Delay

The message delivery delay is one of the most relevant metrics,especially for delaysensitive applications that require low latency.It is defined as the transmission time of a message from a forwarding vehicle to the destination.This delay included;(1) the propagation delays on the various links of the e routing path and (2) the processing delays at the level of the relay nodes.Knowing that a radio signal propagates in a vacuum at the speed of light,propagation delays can be neglected.Most routing solutions,aimed at delay reduction,try to build the routing path with the minimum number of relay nodes by favouring the more remote nodes to relay the message.The delay can be affected by several parameters;the state of the environment in termsoftraffic,collisions and mobility.

Here,we let TS (pij) n be the time instant of a packet n sent by the junction i,and TR (pij)n denotes the time instant of this packet received at the junction j.The forwarding delay of this packet across the route portion pijbetween junctions i and j can be simply expressed by:

In order to reduce the influence of instantaneous delay values,we use temporal discussions and the average delay in a given time interval T which is expressed as:

where NPrevindicates the number of received packets during T.

5.1.2 Packet delivery ratio

Packet delivery ratio is defined as the quotient between the number of well-received packets and the total number of packets generated by a sender to a particular recipient.A metric that is inversely proportional to it is the packet loss rate.This metric is an indicator of the effectiveness of the e technique of access to the channel and the dissemination of messages.It is influenced by the distance between transmitter and receiver,the communication density,and the size of the packets in circulation on the shared channel (if the size of the payload is large,this payload will be spread over a set of packets,hence the increase in communication density).This is a metric that is highly sensitive to the state of the radio link,if the risk of breaking links is high;the packet delivery ratio is low.We can express it as follows:

where NPsndand NPrevindicate the number of sent and received packets at the corresponding junctions during the time interval T,respectively.NPsnd=PR·T,where PR represents the packet rate sent periodically.The immediate QoS metrics are not accurate and cannot meet with the rapid topology changes in dynamic networks.Therefore,we get the overall characteristics of quality of service metrics based on instantaneous and momentous values,and then we use the following equations to obtain more stable simulations of the e quality of service in a route portions.

where δ is a weight value (0＜δ＜1),which regulates the performing of the latest calculated values.Ds(pij),T(pij),D(pij) and PDR(pij) denote the mean values of the e curvemetric distance,traffic density,delay and packet delivery ratio of the road portion,pij,respectively,ds(pij),t(pij),d(pij) and pdr(pij) and denote the instantaneous values of the e corresponding QoS metrics.It is important to note that the evaluation of all measure requires time synchronizing between adjacent junctions.This duration synchronization problem can be readily remedied by using integrated GPS installations that can of fer the same global time reference.

5.2 Calculation of the score

The new score value is calculated by the following formula:

α,β,γ and θ:used as weighting factors,for the curvemetric distance,vehicular traffic,delay and packet delivery ratio respectively (with α+β+γ+θ=1)

where Ds (yij),T (yij),PDR (yij) and D (yij) denote the curvemetric distance,the traffic density,the packet delivery ratio and the delay for the yijroute from junction i to the destination when passing through junction j.Manifestly,compared to other blind flood mechanisms,our network exploration method is beneficial in accelerating routing exploration processes and avoiding low quality routing paths.

6 Results and discussion

In this section,we examine the performance assessment of our approach.For comparison purposes,we have also implemented the original and improved version of GyTAR protocol in urban environment.The simulations were made taking into consideration as much as possible realistic conditions using the simulator used for most of the simulations in CARLINK is the combination of the traffic simulator VanetMobiSim and the network simulator ns-2.Each simulated scenario is repeated several times with different date to ensure good confidence intervals for the results,simulation parameters are listed in Tab.1.To evaluate the proposed approach in terms of QoS in the context of IoV networks,the performance metrics such as average end-to-end delay and packet delivery ratio are taken into consideration to analyse the network situation.

Table1:Simulation setup parameters

Average packet delivery ratio,Vehicular traffic rate and Average end-to-end delay are selected as indicators for the simulation.The final measurement result is the average of the simulation testing values.The simulation results are shown in Fig.5.to Fig.7.

6.1 Packet delivery ratio

Fig.5 Illustrates the packet delivery ratio according to the vehicles density.We observe that the packet delivery ratio for GyTAR and the modified version of GyTAR increases continuously according to the number of vehicles.The results obtained confirm that PDR by the modified version of GyTAR is higher compared to GyTAR.Looking at the graph,we notice that the PDR varies in the same way for the two protocols.This may be because of the intermediate nodes that cooperate in transmitting packets to final destination.From the Fig.5,it can be seen that the success rate of the modified version of GyTAR is better compared to the original GyTAR.This can be explained by the fact that modified GyTAR uses the vehicular traffic information better than original GyTAR.

Through the use of vehicular traffic information,relay nodes are more likely to find the next hop which leads to increasing the probability of reaching the final destination.We can say that the success rate is relatively related to the rate of use of vehicular traffic which is shown later.

6.2 Vehicular traffic rate used

Fig.6 Shows the utilization of the vehicular traffic rate according to the number of vehicles.The modified version of GyTAR shows a high vehicular traffic rate compared to the original version of GyTAR.It can reach 97% with a density of 100 vehicles for the modified version of GyTAR,however;in the original version it reaches only 66%.This is due to the periodic broadcast of the hello messages which increases the use of information of the vehicular traffic on the other hand in the original version.The diffusion of the hello messages is limited by the event of change of the road.

Figure6:Vehicular traffic rate used vs. Network density

6.3 End-to-end delay

From the graph shown in Fig.7.It is clear that the end-to-end delay of modified GyTAR is minimized in a continuous manner compared to that of original GyTAR.

Figure7:End-to-end delay vs. Network density

7 Conclusion and perspectives

The simulation results indicate that the improved GyTAR routing protocol exhibits good performance in the same simulation scenarios.Velocity and density are considered when selecting the next hop node,reduce significantly routing overhead,improve delivery ratio and decrease end-to-end delay.

The performance of the proposed approach and the relevance of derived QoS mathematical models have been evaluated by a series of simulations implementing realistic scenarios.Thorough analysis has shown the best performance of the proposed approach in terms of signaling,delay and packet delivery rates compared to the original version of the GyTAR protocol.The analysis also showed the consequence of different protocol parameters on global performing.As the perspectives of the e presented work;we will evaluate our approach in more realistic scenarios,especially in the urban area with high vehicle density and buildings.Additionally,we can consider integrating the security aspect to our approach,because security in IoT environments is a big challenge,given the high number of information exchanges,the diversity and openness of the e used communication technologies.Particularly,security is a complex for the IoV context.This complexity comes from the particular context of IoV which is characterized by the high mobility of vehicles,and the dynamicity of telecommunication topologies.

Declarations

Competing interests:The authors declare that they have no competing interests.

Funding:This study was funded by the authors’ own funding.

Authors’ contributions:The authors proposed an approach focused on designing and developing QoS aware routing protocol for IoV network,while improving its performance.Many performance metrics are considered to evaluate the QoS in IoV networks:Such as average End-to-End delay and packet delivery ratio are used to analyse the network situation.

Acknowledgments:This study is realized at the University of Tahri Mohamed Bechar.The views expressed are those of the authors.