Jie Huo,Xiangming Wen,Luning Liu,Luhan Wang,2,*,Meiling Li,Zhaoming Lu

1 Beijing Laboratory of Advanced Information Networks,and Beijing Key Laboratory of Network System Architecture and Convergence,School of Information and Communication Engineering,Beijing University of Posts and Telecommunications,Beijing 100876,China

2 Witcomm Open Source Communication Research Institute,Beijing 100088,China

3 Taiyuan University of Science and Technology,Taiyuan 030024,China

Abstract: Re-routing system has become an important technology to improve traffic efficiency.The traditional re-routing schemes do not consider the dynamic characteristics of urban traffic,making the planned routes unable to cope with the changing traffic conditions.Based on real-time traffic information,it is challenging to dynamically re-route connected vehicles to alleviate traffic congestion.Moreover,how to obtain global traffic information while reducing communication costs and improving travel efficiency poses a challenge to the re-routing system.To deal with these challenges,this paper proposes CHRT,a clustering-based hybrid re-routing system for traffic congestion avoidance.CHRT develops a multi-layer hybrid architecture.The central server accesses the global view of traffic,and the distributed part is composed of vehicles divided into clusters to reduce latency and communication overhead.Then,a clustering-based priority mechanism is proposed,which sets priorities for clusters based on realtime traffic information to avoid secondary congestion.Furthermore,to plan the optimal routes for vehicles while alleviating global traffic congestion,this paper presents a multi-metric re-routing algorithm.Through extensive simulations based on the SUMO traffic simulator,CHRT reduces vehicle traveling time,fuel consumption,and CO2 emissions compared to other systems.In addition,CHRT globally alleviates traffic congestion and improves traffic efficiency.

Keywords:traffic congestion;dynamic re-routing;intelligent transportation system (ITS); real-time traffic information;VANET

I.INTRODUCTION

The rapid increase of vehicles has led to the decrease of traffic efficiency and frequent traffic accidents in cities,which have brought great threats to people’s life and property safety.On the other hand,traffic congestion not only affects the efficiency of people’s traveling but also causes serious environmental pollution and energy consumption [1].Hence,it is an urgent problem for urban traffic control to relieve road congestion,improve road network capacity,and build an efficient and smooth traffic system.

In recent years,Intelligent Transport System (ITS)has been developed to relieve the traffic pressure[2,3].ITS integrates sensor technology,communication,information control,and the Internet,which can significantly reduce congestion and accidents,improve travel efficiency,and assist traffic deployment and scheduling.As an important part of ITS,Vehicular Ad Hoc Network (VANET) has received extensive attention from academia and industry [4,5].In the VANET,Connected Vehicles (CVs) can make use of sensors equipped on them to realize real-time perception and processing of traffic information such as traffic accidents and road congestion.In order to assist the Traffic Management Center(TMC)in monitoring,controlling,and scheduling traffic,connected vehicles timely disseminate real-time traffic information to vehicles in need or upload it to Road Side Units (RSUs),which can effectively avoid traffic accidents,alleviate traffic congestion and improve the efficiency of travel.

The dynamic re-routing system utilizes the real-time traffic information shared through VANET to alleviate traffic congestion and improve traffic conditions,which has become a core component of ITS [6–9].Based on the technologies of electronics,computers,networks,and communication,the dynamic re-routing system provides CVs with optimal route planning,which combines the origin-destination (OD) pairs of users’ travel and real-time traffic information.Compared with the traditional re-routing scheme,the dynamic re-routing system can make full use of the storage and processing capacity of RSUs and CVs to calculate and update the traffic congestion information in the road network in real-time.In recent years,to alleviate traffic congestion and improve traffic efficiency,a number of dynamic re-routing systems based on V2X have been proposed,which has become the focus of research due to its real-time characteristics.There are two classification methods for dynamic rerouting systems.On the one hand,dynamic re-routing systems can be divided into three types: centralized,distributed and hybrid according to the calculation method and information sharing method of re-routing.On the other hand,in the light of the optimization goal of re-routing,re-routing systems can be divided into single metric and multi-metric.

The route planning of the centralized dynamic rerouting system is completed by TMC,which is responsible for computing tasks and has access to all necessary traffic condition information[10–12].Nevertheless,it is only suitable for small road networks due to the large computing load and delay of information exchange.In the distributed dynamic rerouting system [13–17],the On-board Unit (OBU)equipped on the vehicles calculates the optimal traveling route based on the real-time traffic information received from the VANET.Compared with the centralized dynamic re-routing system,the distributed dynamic re-routing system has the advantage of reducing TMC tasks,facilitating deployment,and having stronger scalability.However,in addition to the complicated and high-cost installation of on-board equipment,the distributed system also has limited ability to obtain global traffic information.Moreover,the hybrid re-routing system [18,19]combines the advantages of centralization and distribution,using the centralized TMC to access the global view of traffic and distributed to reduce latency and communication overhead.However,the existing hybrid re-routing system architecture is relatively simple with two-layer architecture,which is generally an improvement of the centralized or distributed system,and cannot reflect the strengths of the hybrid system,nor can it significantly improve the performance of the transportation system.Furthermore,most of the communication methods in the current hybrid system are V2I communication,with less V2V communication,and the clustering mechanism is not considered,resulting in large communication overhead and a privacy problem of exposing location information.

In terms of optimization goals,several works [20–22]have proposed re-routing systems to solve traffic congestion while reducing traveling time,fuel consumption,or CO2emissions.The single metric system only guarantees the optimal performance under this indicator,and cannot guarantee the performance of the scheme in other indexes,resulting in that the planned route is not necessarily optimal.Hence,multi-metric re-routing systems have been proposed recently,taking into account multiple metrics to determine the best route.However,these systems do not consider the global traffic flow and only aim at the route planning of individual vehicles.Meanwhile,priority is not taken into account when planning the vehicle route,which may cause numerous vehicles to be guided to the same route,leading to secondary congestion.

In order to solve the above problems,we propose a clustering-based hybrid re-routing system for traffic congestion avoidance(CHRT).In the CHRT,the centralized TMC is responsible for balancing global traffic flow,and the distributed part is composed of vehicles divided into clusters,where the priority of clusters is determined according to real-time traffic conditions.Furthermore,we presented a multi-metric re-routing algorithm to plan the optimal route for vehicles while reducing traveling time,fuel consumption,and CO2emissions.Finally,we used the SUMO traffic simulator to perform simulations based on maps of parts of Beijing,China.The simulation results showed that the proposed system can provide CVs with re-routing services based on real-time traffic conditions,which can not only select the optimal traveling route for a single vehicle,but also globally guide the traffic flow to a route with better traffic conditions,effectively reducing traffic congestion and optimizing traffic conditions.

The main contributions of this paper are as follows:

? A multi-layer hybrid architecture:Our proposed multi-layer hybrid TMC-RSU-cluster architecture combines the advantages of centralization and distribution,with centralized TMC and RSU balancing global traffic flow and using distributed clusters to reduce communication overhead.

? A novel clustering-based priority mechanism:We developed a dynamic traffic congestion model and a clustering-based priority mechanism,in which the priority of clusters is determined according to real-time traffic conditions and congestion levels to improve re-routing efficiency and avoid secondary congestion.

? A multi-metric re-routing algorithm:We presented a multi-metric re-routing algorithm to alleviate congestion while reducing vehicle traveling time,fuel consumption,and CO2emissions.It can not only select the optimal route for the vehicles but also improve traffic efficiency on a global scale.

The rest of this paper is organized as follows.Section II summarizes and analyzes related works.Section III explains the architecture and design principles of CHRT.In Section IV,we describe the traffic flow model and CHRT problem formulation.Section V describes the CHRT re-routing algorithm.Section VI evaluates the performance of the proposed system through simulations.Finally,in Section VII,we conclude this paper along with future work.

II.RELATED WORK

In this section,we shall respectively introduce existing works in the following two aspects: real-time traffic information sharing and metrics of route planning in re-routing systems.

2.1 Real-time Traffic Information Sharing in Re-routing Systems

Software-defined vehicular network (SDVN) supports real-time information sharing in the re-routing system from the network.In [23],Zhaoet al.proposed a new network architecture IDT-SDVN,which introduces IDT into networking to realize the iterative update of network solutions in an adaptive manner.The authors in [24]explored the potential of SDVNs from the aspect of routing and studied the design principles of routing schemes.Several works[25,26]use centralized architecture in re-routing systems.In[25],the authors proposed two novel traffic amount prediction models tailored for urban traffic networks based on two distinct microscopic modeling approaches,and then applied the models to construct a centralized active Route Guidance System (RGS).In [26],a virtual path reservation strategy for emergency vehicles to guarantee a fast emergency service delivery was introduced,called SAINT+.Based on the adjusted congestion contribution matrix and protection zones,SAINT+develops an accident area protection scheme to evacuate vehicles in the accident area.However,centralized systems are only suitable for small road networks or emergency services due to the shortcomings of large information sharing delay and large communication overhead.

In distributed systems,information is mainly shared through V2V communication [27,28].The work in[27]proposed a distributed and self-adaptive vehicle routing guidance approach,which was based on a multiagent system inspired by the honey bee foraging behavior,providing drivers safely with routing directions well before each intersection.Linet al.[28]explored a distributed dynamic road decision real-time route guidance scheme to effectively relieve road congestion caused by the sudden increase of vehicles.A few works[29,30]focus on cluster-based routing.In[29],Wuet al.proposed a collaborative learning-based routing scheme for multi-access vehicular edge computing environment to find routes in a proactive manner with a low communication overhead.The work in[30]designed a two-level clustering approach for the content distribution in VANETs,where the two-level clusters employ fuzzy logic-based algorithm and Qlearning algorithm respectively.However,apart from the problems of high installation cost,these works have not solved the problem of the limited ability of distributed systems to obtain global traffic information.

The hybrid re-routing system can reduce communication costs and delay while obtaining global traffic information.In[31],the authors introduced DIVERT,a distributed vehicular re-routing system for congestion avoidance.To make collaborative routing decisions,vehicles exchange messages through vehicular ad hoc networks.DIVERT is a hybrid system because it uses a server and Internet communication to determine an accurate global view of the traffic.Wanget al.[19]presented an original and highly practical vehicle re-routing system to aid drivers in making the most appropriate next road choice to avoid unexpected congestions.The work in[32]developed a dynamic semidistributed and Fog-Cloud based advance route guidance system architecture,called ReFOCUS+.The Re-FOCUS+architecture employs RSUs to calculate road congestion,traveling time,and other traffic-related factors,and then re-routes the vehicles to alleviate traffic congestion in each area.However,ReFOCUS+uses TMC and RSUs to monitor and plan global traffic flow,and uses V2I communication for information sharing rather than clustering vehicles,resulting in large V2I communication overhead.

In this paper,a hybrid architecture based on clustering is proposed to share real-time traffic information.Centralized TMC and RSU can obtain and share global traffic information.Connected vehicles are divided into clusters,which are prioritized and sorted according to real-time traffic conditions.In this way,not only global information can be guaranteed,but also the communication overhead is low.Unlike the TMCRSU-vehicle architecture [32],the multi-layer hybrid TMC-RSU-cluster architecture can reduce the number of times that vehicles report location information and distribute the risk of location information exposure on VANET instead of a single centralized infrastructure.

2.2 Metrics of Route Planning in Re-routing Systems

According to the optimization goal of route planning,the re-routing systems can be divided into single metric and multi-metric.In the single metric re-routing system,the optimization target is only for a single indicator such as traveling time,fuel consumption or CO2emissions.In [20],an effective real-time traffic information sharing mechanism based on a distributed transportation system with road-side units was introduced.Considering current traffic information,the authors presented a method to estimate the traveling time from a source to a destination in the road network,called TTE,which acts as a metric for path planning.Liuet al.[21]developed an energy-efficient dynamic route planning algorithm without starting and stopping for the connected and automated vehicles.The algorithm aims to minimize both time and energy consumption for the route.The idea proposed in[22]exploits the information gathered by road-side units to redirect traffic flows(in terms of vehicles)to less congested roads,with overall system optimization,also in terms of CO2emissions reduction.However,using a single metric in the re-routing system will cause the planned route to perform poorly in other aspects that are not considered.For example,if only plan the route with the shortest traveling time and make a detour when the road is congested,it may increase fuel consumption and CO2emissions.

The multi-metric re-routing system can effectively solve the above problems.The work in[28]presented DEDR,which considers multiple metrics to comprehensively assess traffic conditions so that drivers can determine the optimal route with a preference to these metrics during travel.DEDR can greatly increase traffic efficiency in terms of time efficiency,balancing efficiency,and fuel efficiency.However,DEDR is only for single vehicle re-routing,the global performance is not necessarily optimal.

To make up for the above shortcomings,in this paper,we propose a multi-layer hybrid architecture and multi-metric re-routing algorithm that can not only mitigate traffic congestion,but also effectively reduce traveling time,fuel consumption,and CO2emissions.Moreover,we ensure global traffic information through a multi-layer hybrid architecture and clustering-based priority mechanism.

III.SYSTEM OVERVIEW

The CHRT system architecture is shown in Figure 1,which is a multi-layer hybrid architecture.The architecture mainly includes the following components:

Figure 1.CHRT system architecture.

? Traffic Management Center(TMC):The TMC is a large traffic center[33]with powerful computing and data storage capabilities.TMC collects real-time traffic information based on the information shared by RSU (such as average vehicle speed,road density,etc.) to monitor and manage global traffic conditions.TMC is also responsible for updating and maintaining the Traffic Congestion Matrix(TCM).

? Road-Side Unit (RSU):The RSU is an infrastructure with computing capability located on the roadside.RSU communicates with vehicles through V2I communication and is connected to the Internet.In urban road networks,RSUs are connected through wired or wireless networks.RSU collects real-time traffic information and transmits it to TMC,and is also responsible for disseminating global traffic information to vehicles.

? Cluster:Vehicles traveling within a certain distance of the same road segment are organized into clusters,and the vehicle closest to the center of the road segment is regarded as a cluster head.Cluster and cluster head change with the movement of vehicles.Members in the cluster share information through V2V communication.

? Connected Vehicles (CVs):The vehicles are equipped with OBU,which is designed to achieve V2V communication with other vehicles on the road and V2I communication with RSU at the intersection.OBU records vehicle movement information,such as vehicle ID,vehicle position,real-time speed,etc.At the same time,it has storage and computing capabilities to plan the optimal route based on the congestion matrix.

Figure 2 illustrates the system process.The centralized part of the system architecture includes TMC and RSUs,and the distributed part includes clusters and CVs.Centralized TMC and RSUs access to global traffic information,distributed clusters can reduce latency and communication overhead,while reducing the risk of privacy exposure.The process of the CHRT system is as follows:

Figure 2.System process of CHRT.

1.Urban traffic roads are segmented based on a fixed length.Vehicles traveling on the same road segment and within the DSRC communication range form a cluster.At the beginning of the period,the vehicle broadcasts its information to nearby vehicles,including vehicle ID,location,speed,etc.,to form a cluster and determine the cluster head.

2.The cluster head collects the information reported by members of the cluster to obtain the real-time traffic state of the current segment,such as average speed,vehicle density and accidents.Then the cluster head reports the information to the RSU at the nearby intersection.

3.RSU uses real-time traffic information reported by cluster heads to calculate the density of road vehicles in the covered area so as to judge the congestion.When the vehicle density exceeds the threshold,the current road is considered congested,and then the congestion information will be reported to TMC.

4.TMC determines the congestion affected zone according to the degree of traffic congestion.The clusters in the congested zone are prioritized based on real-time traffic state and global traffic information.At the same time,the TMC updates TCM.Afterwards,the TMC sends the priority information and the updated TCM to the RSUs in the congested zone.

5.The RSU disseminates the congestion message and the updated TCM to the cluster heads and informs their priority.The cluster heads broadcast the congestion message,and the vehicles in the cluster carry out new route planning based on the TCM.The cluster with the highest priority first performs route planning.Then,the cluster head collects the re-routing information of the vehicles in the cluster to generate Re-routing Traffic Congestion Matrix (RRM),and sends it to the next priority cluster head and RSU.It should be noted that when the distance between adjacent cluster heads is longer than the DSRC communication range,the congestion information is forwarded by the RSU.

6.The cluster head periodically reports the vehicle density,and only when the road vehicle density is over the threshold will the new route planning be carried out.The cluster heads are constantly changing as the vehicles move.When the traffic flow is low,RSUs are responsible for sending real-time traffic information to the vehicles that are not in the cluster.

It is important to note that CHRT only re-routes vehicles directly affected by congestion,as this is sufficient to improve the planning of optimal routes for vehicles and alleviate congestion.Furthermore,this can reduce the vehicle’s re-routing frequency,thus reducing computing and communication overhead.

IV.PROBLEM FORMULATION

In this section,we first describe the traffic flow model that we propose.Then,we present the clusteringbased priority mechanism and multi-metric for rerouting.The traffic flow model described in Section 4.1 is used to determine whether congestion occurs.If the road is congested,clusters are prioritized as described in Section 4.2,and then the re-routing is carried out according to the priority.Section 4.3 explains the multi-metric for route planning.To ease understanding,the frequently used notations are summarized in Table 1.

Table 1.Parameters and symbols summary.

We first model the road network as a weighted directed graph denoted byG=(V,E,L,D).HereV={...,vi,vj,···}is a set of vertices indicating the road intersections,andis a set of directed edges,each of which connects two vertices.is length of edges.is density of each edge in the road network.

4.1 Traffic Flow Model

This section describes the traffic flow model that we propose based on real-time traffic conditions.Ψevi,vj(T)is defined as the traffic flow of edgeevi,vjat timeT,whereTis the re-routing period of CHRT.Then the traffic flow ofevi,vjatT+1 can be formulated as:

where(T+1) is the flow that will enter edgeevi,vjatT+ 1,and(T+ 1) is the flow that will leaveevi,vjatT+ 1.cvkis defined as the vehicle that is likely to enterevi,vjat timeT+1,which is traveling on the upstream of roadevi,vjat timeT.Andvcvkrepresents the speed of vehiclecvk.Then the time that vehiclecvkwill enter the road(i.e.,the vehicle will travel to the intersectionvi)can be calculated aswhereis the distance from the vehiclecvkto the intersectionvi.The indicator factorμcvkis defined to indicate whether vehiclecvkwill pull intoevi,vjwithin periodT.If the traveling time to the intersection,then the value ofμcvkis 1.

Similarly,cvmis denoted as the vehicle that is likely to departevi,vjat timeT+ 1,that is,travel to the road downstream ofevi,vjat timeT+ 1.The time when the vehiclecvmdepartsevi,vj,which is the time when the vehicle travels to the intersectionvj,can be expressed aswhereis the distance from the vehiclecvmto the intersectionvj.The departing indicator factor is defined asσcvm,when,the value ofσcvmis 1.

Therefore,the flow density ofevi,vjat timeT+1 can be expressed as:

Then,the road traffic capacity ofevi,vjcan be calcalated as:

wherelevi,vjis the length of edgeevi,vj,andlanesevi,vjis defined as the number of lanes onevi,vj.lcvandlgapare the average length of vehicles and the distance between vehicles,respectively.

Based on the traffic flow model and real-time traffic conditions,the traffic flow in the next period can be predicted.If the road is predicted to be congested,CHRT will take different measures according to the degree of congestion.The degree of traffic congestion is divided into four levels,namely no congestion,light congestion,mild congestion,and heavy congestion.First,the definition of the congestion index is given as follows.

Definition 1. Congestion Index.The congestion index CI represents the road congestion threshold.According to the degree of traffic congestion,we use CIl to denote the light congestion index,CIm to the mild congestion index,and CIh to the heavy congestion index.

Light congestion index can be formulated asCIl=,whereNlis the road density when the congestion index isCIl.When the congestion index ofevi,vjis,it is considered that no congestion has occurred,and the traffic flow at this time can be regarded as free flow,whereCIevi,vj=Similarly,the mild and heavy congestion index can be defined asrespectively.Whenthe road is regarded as lightly congested.If the road is moderately congested,that is,CIm < CIevi,vj ≤CIh,only vehicles with difficult route change are allowed to pass.The above vehicles refer to vehicles that are traveling on or about to enter the congested road.Besides,vehicles in the affected congestion zone are re-routed.If the road is heavily congested,the road will be temporarily closed and vehicles in the congested zone will be re-routed,at this timeCIevi,vj > CIh.A vehicle is allowed to pass only if it is traveling upstream of the congested road and the congested road is the only way to reach the destination.It should be noted that the congested zone here refers to the road affected by congestion,whichs is determined by the TMC based on the degree of traffic congestion.In this paper,the congested zone with mild congestion includes roads that are located upstream of a congested section and are no more than two intersections from the congested road.And the congested zone with heavy congestion includes roads that are located upstream of a congested section and are no more than three intersections away from the road.The dynamic congestion control algorithm will be elaborated in Section 5.1.

In order to efficiently disseminate real-time traffic information and congestion messages,TCM is proposed to indicate traffic conditions,which can be expressed as:

wherenis the number of intersections,that is,the number of vertices of the road network,so TCM is ann×ndimensional matrix.Andwevi,vj(T) is the weight ofevi,vj,which is the ratio of the road flow to the maximum capacity of the road.wevi,vj(T)can be calculated as follows:

TMC updates and maintains TMC periodically.If congestion occurs,TMC determines the congestion range and transmits TCM to facilitate vehicles planning for new routes.

4.2 Cluster Priority

To obtain global traffic information and avoid secondary congestion during congestion,we propose a clustering-based priority mechanism.The following section introduces how TMC sets priorities when congestion occurs and how the clusters plan the routes based on the assigned priority.is defined as the cluster traveling on the road segmentkonevi,vj,andis the cluster head of,which is the vehicle closest to the center of the segmentk.

The cluster with the highest priority performs planning route first.Clusters with low priority can obtain the route planning information of the clusters with high priority,so that the global traffic information can be accessed without V2I communication.The priority of a cluster is related to the distance from the cluster head to the congested road,the density of vehicles on the current road,and the average speed of the vehicles in the cluster.Therefore,the congestion distance indexTI,the road density indexDI,and the cluster average speed indexSIare defined to represent the above factors,respectively.

Definition 2. Congestion Distance Index.The congested road is denoted as CR,and the distance from the cluster head to the congested road as distCR()

Definition 3. Road Density Index.The road density index indicates the current road density of vehicles.The road density index DI of can be formulated as:

whereΨevi,vj represents the traffic flow of the road where the cluster is located,and is the maximum capacity of evi,vj.

Definition 4. Cluster Average Speed Index.The cluster average speed index SI denotes the average speed of vehicles in the cluster.The SI of the cluster can be modeled as:

where,is the average speed of calcu-lated by the cluster head,which is obtained from the collected speed information of members in the cluster,and vmax(evi,vj)is the maximum permissible speed of evi,vj.

Therefore,the priority indexCPIof clustercan be expressed as:

According to the clustering-based priority mechanism,the cluster head will collect the new route information of the members in the cluster after re-routing for the cluster with high priority.Then the cluster head transmits information to the cluster head with the next priority.Hence,how to effectively carry out route information statistics and transmission has become a challenge.To solve this challenge,based on the TCM in the previous section,we propose the Rerouting Traffic Congestion Matrix.The RRM of the cluster with prioritypccan be formulated as:

whererevi,vj(pc)is the sum of the number of vehicles that includesevi,vjin the new routes in the cluster with prioritypc.revi,vj(pc)can be calculated as follows:

whereNumrepresents the number of vehicles in the cluster andθevi,vj(cvk)is an indicator factor.Ifevi,vjis in the new route planned by vehiclecvk,then the value ofθevi,vj(cvk)is 1.

After the cluster head with the next priority receives the TCM sent by the TMC and the RRM sent by the cluster head with previous priority,it disseminates them to the members of the cluster.Similarly,after the members in the cluster plan the new routes,the cluster head collects information and updates the RRM to continue transmission to the next priority.In this way,global traffic information can be obtained without reporting the re-routing information to TMC.

4.3 Multiple Metrics for Re-routing

After receiving the re-routing information,TCM and RRM,the vehicle will plan the optimal route.In this paper,a multi-metric re-routing algorithm is proposed,which mainly considers three metrics: traveling time,fuel consumption and CO2emissions.This section describes the multiple metrics for re-routing.

The estimation of traveling time is based on the Greenshield model[34],which considers the relationship between speed and density.Several researches[31,19,35]have used this model extensively,and have proved through experience that the model can describe the relatively low-density speed-density relationship well.The Greenshield model takes into account the linear relationship between the estimated average speed of each road and the traffic density [35],which is shown as follows:

where,vmax(evi,vj)denotes the maximum permissible speed of·lanesevi,vjis the maximum capacity of the road,and Ψevi,vjis the traffic flow.The traveling time is estimated according to the average speed:

Therefore,the total traveling time from the origin to the destination can be expressed as:

Multiple models in the literature can be used to estimate fuel consumption and CO2emissions.The EMIT model [36]is one of them which is widely accepted.The model supports a variety of emissions,including CO2,CO,hydrocarbons (HC) and nitrous oxide(NOx).So we can use it to make advance estimates of fuel consumption and CO2emissions.Fuel consumption and emissions are calculated based on acceleration and deceleration as well as chemical interactions through catalytic converters [37].The following formula is used to calculate the total traction power demand onPtract:

where:

v: vehicle speed(m/s),

a: vehicle acceleration(m/s2),

A: rolling resistance term(kW/m/s),

B: speed correction to rolling resistance term(kW/(m/s)2),

C: air drag resistance term(kW/(m/s)3),

M: vehicle’s mass(kg),

g: gravitational constant(9.81m/s2),

?: road grade(degrees).

Based on the value ofPtract,fuel consumption and CO2emission can be calculated as follows:

where the values ofα,β,δ,ζandα′are shown in Table 2.Eq.(18)and(19)are calibrated using ordinary least square linear regressions[36].

Table 2.Default values of all coefficients in EMIT model.

Considering the above three factors comprehensively,the weight ofevi,vjcan be modeled as:

whereηTT,γFC,andλTPare the weighting factors of traveling time,fuel consumption and CO2emissions respectively.And the values of the three weighting factors add up to 1.The important thing to note here is that normalization is required when calculating the weight.The initial values ofηTT,γFC,andλTPare equal,and the vehicle can individually change the value of the weighting factor to meet its own needs.In this way,CHRT allows CVs to make personalized choices while balancing the global traffic flow.

V.CONGESTION CONTROL AND REROUTING ALGORITHM

In CHRT,TMC dynamically monitors and controls real-time traffic conditions.If the road is congested,TMC will be responsible for maintaining the TCM and setting priorities for clusters.Afterwards,re-routing will be conducted based on the priority to alleviate traffic congestion.This section introduces the dynamic congestion control algorithm and the priority based re-routing algorithm.The performance of the two algorithms will be evaluated in Section VI.

Algorithm 1.Dynamic congestion control algorithm.Input: The road network G=(V,E,L,D)1: BEGIN 2: Initialization: TCM W =?3: for all edges in network do 4: TMC estimates the next period flow Ψevi,vj(T +1)by using Eq.(4)5: CIevi,vj =Ψevi,vj(T +1)/Cmaxevi,vj 6: if CIevi,vj >CIlightevi,vj then 7: RSU broadcast the density of evi,vj 8: if CIevi,vj >CImildevi,vj then 9: if CIevi,vj >CIheavyevi,vj then 10: the congested road is temporarily closed 11: end if 12: TMC updates W 13: TMC determines congested zone based on CIevi,vj 14: for all clusters in the congested zone do 15: Calculate the priority of the cluster ckevi,vj by using Eq.(11)16: end for 17: Sort the priority of clusters 18: TMC sends W and priority to RSU 19: end if 20: end if 21: end for 22: Update the real-time traffic information 23: END

5.1 Dynamic Congestion Control

In order to effectively detect and control traffic congestion,we propose a dynamic congestion control algorithm.The algorithm is run by the TMC terminal and determines the priority of clusters based on the clusterbased priority mechanism described in Section 4.1 and 4.2.Specifically,when the road is congested,TMC calculates and sorts the priority of each cluster according to the real-time traffic conditions to dynamically control the traffic congestion.

Algorithm 1 describes the dynamic congestion control algorithm.For all edges in the road network,TMC calculates the traffic flow of the next period using Eq.(4) and then obtains their congestion index(Lines 4-5).If the congestion indexCIevi,vj > CIl,the RSU broadcasts road density to alert vehicles(Line 7).IfCIevi,vj > CIh,that is,the road is in a state of heavy congestion,the congested road will be temporarily closed to alleviate the congestion (Lines 9-11).WhenCIevi,vj > CIm,TMC first updates TCM and determines the congested zone based onCIevi,vj(Lines 12-13),depending on whether it is mild congestion or heavy congestion.Then,TMC calculates the priority of clusters in the congested zone (Lines 14-16).TMC sorts the priority of the clusters,and disseminates the updated TCM and priority order to RSU(Lines 17-18).Finally,real-time traffic information is updated periodically(Line 22).

5.2 Priority Based Re-routing

Through the dynamic congestion control algorithm,TMC can obtain real-time traffic information.When congestion occurs,TMC will determine the congestion zone and the priority of clusters within the zone,as described in Algorithm 1.According to the priorities of the clusters calculated by Algorithm 1,the cluster with the highest priority first plans routes.The Dijkstra algorithm is employed to plan vehicle route,in which the weight of each road is calculated by the method described in Section 4.3.Then the cluster head collects route information and sends it to the cluster head with the next priority.Algorithm 2 describes a priority based re-routing algorithm.For clusters with prioritypcin the congested zone,the cluster head first broadcasts the updated TCM and RRM(Line 2).The members of the cluster calculate the road weight and use the Dijkstra algorithm to plan routes based on TCM and RRM (Lines 3-7).Then,members in the cluster report the information on new routes to the cluster head (Line 8).After the cluster head receives the new route information,it calculates and updates the RRM(Lines 10-13).Finally,the cluster head disseminates the updated RRMR(pc)to the cluster head with the next prioritypc+1(Line 14).

The two proposed algorithms reflect the strengths of a multi-layer hybrid architecture,in which TMC dynamically controls traffic congestion and clusters re-route based on priority.Moreover,the clusteringbased priority mechanism also avoids the occurrence of secondary congestion.

Algorithm 2.Priority based re-routing algorithm.Input: The priority set P =■p1,···,p|C|■1: for all pc in P do 2: Cluster head chkevi,vj broadcast TCM and RRM 3: for all vehicle in ckevi,vj do 4: for all i,j in E do 5: Calculate H(evi,vj)by using Eq.(20)6: end for 7: Plan new route based on Dijkstra algorithm 8: Report the new route to chkevi,vj 9: end for 10: for all i,j in R(pc)do 11: Calculate revi,vj(pc)by using Eq.(13)12: end for 13: Update RRM R(pc)14: Send R(pc) to the cluster head of the next priority pc+1 15: end for

VI.PERFORMANCE EVALUATION

Extensive simulations have been conducted to evaluate our proposed clustering-based hybrid re-routing system for traffic congestion avoidance.In this section,we first introduce the simulation settings,then describe the obtained results.

6.1 Simulation Setup

We used SUMO(Simulation of Urban MObility)[38],an open source traffic simulation,to perform simulation campaigns.TraCI [39]is a traffic control interface,which currently supports multiple mainstream languages,such as python.We utilized TraCI to obtain the data in the SUMO traffic simulation environment,and modify and control it in real-time.The performance evaluation was conducted based on a simplified version of a partial traffic map of Beijing,China.The road network includes 48 roads,each with 2 or 3 lanes.The maximum road speed is 20 m/s.Each intersection is installed with RSU,a total of 16 RSUs.The DSRC coverage area is 500 m.The routes are randomly generated,including the origin,destination,and traveling route.In order to simulate actual traffic conditions,the traffic flow on specific roads is increased to simulate the traffic flow at peak time.The simulation timeis 1800 seconds.

6.2 Results and Analysis

We compare our proposed system with the following systems.

?DIVERT[31]:A distributed vehicular re-routing system for congestion avoidance,which has greatly improved performance compared to the no re-routing case.Different from the system we propose,DIVERT mainly uses V2V communication and does not divide the vehicles into clusters.

?CDRGS[25]:A centralized real-time urban traffic dynamic route guidance system that can provide proactive route guidance.CDRGS reduces average traveling time by up to 70%compared to providing reactive one.In CDRGS,the vehicle’routes are planned by the centralized infrastructure.However,the route planning is completed by vehicle in our proposed system.

?NRT:No re-routing system.In the event of congestion,vehicles will continue to travel on the previous route.NRT is used to show the importance of re-routing and serves as a baseline for comparison with other systems.

We first evaluate the performance of the proposed system by changing the congestion index threshold.The evaluation indicators are traveling time,fuel consumption,and CO2emissions.Here,we set different thresholds for mild congestion indexCImand heavy congestion indexCIh.Table 3 describes the performance of the system with various thresholds,in which the threshold of mild congestion index is set as 0.55,0.5,and 0.45 respectively,and the threshold of heavy congestion index is set as 0.8,0.75,and 0.7 respectively.The evaluation indicators in the table are all average values,that is,the average cost for each vehicle to complete the route.Increasing the threshold will trigger re-routing only when the road becomes more congested.However,a too low threshold leads to rerouting when the road congestion is not serious,which will increase the cost of the vehicle and cause the system performance to deteriorate.Since the heavy congestion threshold and the mild congestion threshold are related to each other,and the optimal value is different in different road networks.It is not possible to change a single value but change both values together to select the value with the best performance.According to the simulation results,whenCImis 0.45 andCIhis 0.7,the system performance is the best.In other words,the traveling time,fuel consumption,and CO2emissions are the least.Therefore,in the following simulation,the mild congestion index and heavy congestion index will be set according to the best value of the performance mentioned above.

Table 3.The impact of congestion index on system performance.

Figure 3 displays the performance of CHRT in terms of traveling time,fuel consumption,and CO2emissions compared to other systems.In the CHRT’s simulation,the weighting factors of traveling time,fuel consumption,and CO2emissions are set to 0.33 respectively.From Figure 3a,it is seen that the average traveling time of our proposed system CHRT is the shortest in scenarios with different numbers of vehicles.The reason is that we classify the degree of congestion and take different measures for different congestion conditions,effectively reducing the traveling time.Figure 3b and Figure 3c respectively show the average fuel consumption and average CO2emissions of different systems.Similarly,it can be seen from the figures that the average fuel consumption and CO2emissions of CHRT are the lowest among the four systems.This is because we have proposed a multi-metric re-routing system that reduces fuel consumption and CO2emissions while reducing traveling time,which not only enhances the user experience but also is more economical and environmentally friendly.Compared with other systems,it is found that CHRT performs better.

Figure 3.The system performance of CHRT in comparison with other systems.

Figure 4 visually shows the traffic flow distribution of CHRT in comparison with other systems,where each square represents a road,here are 12 horizontal roads.The darker the color,the more the traffic flow.In Figure 4a,the second road is severely congested but other roads have very few vehicles.The reason is that there is no dynamic re-routing based on real-time traffic information.When the traffic flow is large,the vehicles still travel along the original route,making it difficult to alleviate the congestion.Figure 4b and Figure 4c plot the CDRGS and DIVERT traffic flow distributions respectively.It can be seen that the traffic flow distribution is relatively concentrated,mainly on congested roads,with fewer vehicles on other roads.From Figure 4d,it is easy to see that the CHRT road flow distribution is more uniform.This is because we propose a clustering-based priority mechanism and congestion index in the CHRT.Through the clustering-based priority mechanism,vehicles can obtain a global traffic flow view without frequent communication with the RSU,which reflects the performance of Algorithm 1 and 2.At the same time,setting thresholds for different levels of congestion can take measures earlier,make rational use of road capacity,and distribute the traffic more evenly.Therefore,CHRT can effectively balance the global traffic flow and perform better than other systems.

Figure 4.The traffic flow distribution of CHRT in comparison with other systems.

Figure 5 illustrates the system throughput of different systems,where the number of vehicles is 2500.System throughput refers to the number of vehicles that reach the destination in the system.As shown in Figure 5,the system throughput gradually increases with time.The reason is that as the simulation progresses,the vehicles gradually reach their destinations.It can be seen from Figure 5 that the NRT system has the lowest throughput,while DIVERT and CDRGS alleviate traffic congestion to a certain extent and increase throughput.The system throughput of the CHRT we propose is always at the maximum irrespective of the simulation time,indicating that CHRT effectively relieves congestion and the number of vehicles arriving at the destination is the largest.According to the results,it is demonstrated that compared with other schemes our proposed CHRT has better performance in terms of system throughput,thereby improving travel efficiency.

Figure 5.System throughput comparison of four different systems.

Figure 6 shows the density of the congested road in different systems,where congested road refer to the most congested road in the road network during peak hours based on actual traffic conditions.Compared with the NRT scheme without re-routing,the density of congested road in DIVERT,CDRGS,and CHRT is decreased.It can be seen that the CHRT we propose always has the least density of the congested road during the simulation time,which greatly reduces the number of vehicles and alleviates road congestion.This is because we have proposed a congestion index and graded it,so that measures can be taken against congestion earlier.The curve of the density first drops and then remains relatively stable,because road congestion has been controlled to a light degree of congestion.Due to the impact of traffic lights at the intersection,vehicles temporarily stopped traveling,and the density fluctuated up and down.The simulation results show that our proposed CHRT effectively reduces the density of the congested road and has better performance than other systems.

Figure 6.Comparison of the density of congested road in four different systems.

In order to show the performance of CHRT in terms of communication overhead,we evaluate the average number of messages in V2I communication for different systems,as shown in Figure 7.Since most of the congestion has been alleviated in the front part of the simulation,the simulation time is set to 800s here.It can be seen from Figure 7 that the average number of V2I messages in our proposed CHRT is the smallest in three scenarios.Compared with other systems,the number of V2I messages is greatly reduced.This is because we propose a multi-layered hybrid architecture and develop a clustering-based priority mechanism and algorithm.The vehicle does not need to communicate with the RSU to disseminate global traffic information,reducing the number of V2I messages.Since V2I communication only occurs between the RSU and the cluster head or vehicles that do not form a cluster,the V2I communication overhead performance of CHRT is more significant when the number of vehicles is large.More use of V2V communication and reduction of V2I communication reduces the risk of location information exposure,as the central server is more vulnerable to privacy exposure.Therefore,we can see from the simulation results that our proposed system can not only alleviate traffic congestion and improve users’ travel efficiency,but also reduce the risk of exposure of location information and protect users’privacy.

Figure 7.Comparison of the average number of V2I messages in three different systems.

VII.CONCLUSION

In this paper,we introduced CHRT,a clustering-based hybrid re-routing system,which dynamically re-routes vehicles based on real-time traffic information.Combining the advantages of centralization and distribution,TMC in CHRT accesses the global view of traffic flow,and distributed clusters are used to reduce communication overhead.In order to improve the efficiency of re-routing,we developed a clustering-based priority mechanism,which sets different priorities for different clusters according to the traffic congestion situation,avoiding the occurrence of secondary congestion.Then,we proposed a multi-metric re-routing algorithm to alleviate traffic congestion while planning the optimal routes for vehicles,reducing travel costs.Finally,extensive simulations show that,compared to other schemes,CHRT not only reduces vehicle traveling time,fuel consumption,and CO2emissions,but also globally alleviates traffic congestion and improves traffic efficiency.

In the future,we will predict the trajectories of vehicles and study the impact of future vehicle trajectories.The traffic flow for a period of time in the future is estimated based on the future trajectory.Moreover,we are also interested in traffic signal control schemes in order to schedule traffic lights globally for the re-routing system.We will continue to improve the algorithm taking into account the influence of future trajectories and traffic lights,and perform global optimization in the traffic network.

ACKNOWLEDGEMENT

This work was partially supported by the National Key R＆D Program of China under Grant 2019YFB1803301,the Key Research and Development Program of Shanxi under Grant 201903D121117,Beijing Nova Program of Science and Technology under Grant Z191100001119028,and the National Natural Science Foundation of China under Grant 62001320.