MARVEL:Multi-Agent Reinforcement Learning for VANET Delay Minimization

Chengyue Lu,Zihan Wang,Wenbo Ding,*,Gang Li,Sicong Liu,Ling Cheng

1 Tsinghua-Berkeley Shenzhen Institute,Tsinghua Shenzhen International Graduate School,Tsinghua University,518055,China

2 Department of Electronic Engineering,Tsinghua University,100084,China

3 Department of Information and Communication Engineering,Xiamen University,361005,China

4 School of Electrical and Information Engineering,University of the Witwatersrand,Johannesburg,2000,South Africa

Abstract:In urban Vehicular Ad hoc Networks(VANETs),high mobility of vehicular environment and frequently changed network topology call for a low delay end-to-end routing algorithm.In this paper,we propose a Multi-Agent Reinforcement Learning(MARL)based decentralized routing scheme,where the inherent similarity between the routing problem in VANET and the MARL problem is exploited.The proposed routing scheme models the interaction between vehicles and the environment as a multi-agent problem in which each vehicle autonomously establishes the communication channel with a neighbor device regardless of the global information.Simulation performed in the 3GPP Manhattan mobility model demonstrates that our proposed decentralized routing algorithm achieves less than 45.8 ms average latency and high stability of 0.05%averaging failure rate with varying vehicle capacities.

Keywords:VANET;multi-agent RL;delay minimization;routing algorithm

I.INTRODUCTION

Rapid urbanization is resulting in a growing vehicle population accompany with an increase in traffic accidents and deterioration of traffic congestion.Under this circumstance,the Intelligent Transportation System(ITS)and Vehicle-to-Everything(V2X)communications have been proposed aiming to relieve traffic pressure[1].As an essential ITS component,the Vehicular Ad hoc Network(VANET)is committed to building a self-organizing,easy to deploy,low cost,and open-structure vehicle communication network[2,3],which has demonstrated a great potential of tackling the above issues.

However,due to the nature of highly dynamic topology,strict delay requirements,high node mobility,etc.,VANET usually suffers from data packet dropouts compared to the traditional Mobile Ad hoc Network(MANET)[2,4,5].Consequently,the routing protocols for MANET,such as ad hoc on-demand distance vector(AODV)[6],Dynamic Source Routing(DSR)[7],optimized link-state protocol(OLSR)[8]and so on,will have significant performance degradation in VANET,especially under highly dynamic vehicle communication scenarios[9].To this end,many efforts have been carried out in routing protocol design for VANETs to achieve better performance[10–12].In general,the VANET routing protocols can be divided into two types,the topology-based and the location-based ones.The topology-based protocols are mainly imitated from MANET but customized for VANET scenarios,for example,Direction AODV(DAODV)by Abediet al.[13],and the Receive On the Most Stable Group-Path(ROMSGP)scheme by Talebet al.[14].Nevertheless,in the context of vehicular communications,especially in traffic safety applications,the high cost of routing establishment usually causes intolerable delays.The location-based ones have emerged to be the popular protocols for VANET due to the additional location and velocity information from the Global Positioning System(GPS),of which classical algorithms such as the Greedy Perimeter Stateless Routing(GPSR)by Karpet al.[15],the Geographic Source Routing(GSR)by Lochertet al.[16]and the Anchor-based Street and Traffic-Aware touting(A-STAR)by Liuet al.[17]are proposed.However,the location-based protocols often experience connection failure in complex road conditions,especially in crossroads.

The traditional routing scheme has high convergence and short response time,whereas it is not practical to design a universal routing protocol.Different VANET routing protocols are required in various deployments.For the large-scale VANET,the network’s dynamic changes are more frequent,and its protocol should be highly adaptable to topology changes and have good scalability.For VANETs with fast node movement speeds and strict delay requirements,their protocols must guarantee low delays.With the development of Machine Learning(ML)and Deep Learning(DL),Tanget al.[18]began their research on MLbased mobility prediction in delay-minimization routing.The ML-based algorithm can achieve relatively low average latency in different traffic flow environments.Then,the Reinforcement Learning(RL)based routing schemes were proposed by C.Wuet al.and F.Liet al.[19,20],where the RL agent training is to obtain optimal responses after observing data from the environment.Because the environment modeling by RL is close to the real world,the RL-based routing algorithms achieve better performance compared with the traditional routing protocols.However,in resource management,single-agent RL is hard to provide a distributed perspective on identifying the resource requirement of each agent[21].Therefore,combine the RL and multi-agent problem,the distributed perspective of Multi-Agent Reinforcement Learning(MARL)makes it more adaptive to the potential decentralized applications such as VANET.

To this end,this paper focuses on designing a unicast routing algorithm with minimum delay under the framework of MARL,where the main idea is modeling the decision of router selection for each vehicle as a Markov Decision Process(MDP).Vehicles learn the selection strategy based on the MDP model with an online distributed learning algorithm.The improved versions of Deep Q-Network(DQN)are adopted to solve the multi-agent problem.Specifically,the model design is based on Independent QLearning(IQL)[22],and the converging stability of the proposed algorithm is improved by Deep Double Q-learning Network(DDQN)[23]and the dueling network[24].By modeling the routing problem into the multi-agent problem,all the vehicles and infrastructures are considered as agents that can automatically find an optimal path to minimize communication latency.

The rest of this paper is organized as follows.Section II defines the network model and provides problem formulation.In Section III,we present the modeling and implementation of MARL based routing algorithm.Then,the simulation results are shown in Section IV.Finally,concluding remarks are given in Section V.

II.SYSTEM MODEL

2.1 Network Model

The network model of a communication system including V2I and V2V links in an urban scenario is considered,which simultaneously provides the highspeed communication and the periodic safety messages,as introduced in 3GPP Release 15 for cellular V2X enhancement[25].In this model,M vehicles and N BS/RSUs are planted in the simulation environment.All the BS and RSUs are connected via a wired link.Each vehicle periodically sends packets that not only containing application messages but also include location and velocity information to its neighbors.Moreover,we assume that all the vehicles use transceivers with an identical single antenna and all the packet to be transmitted has the fixed size.When a vehicle transmits packets,it chooses a channel different from the channel occupied by the periodic safety messages to avoid interference.Since the vehicle can select any nearby vehicle or RSU as a router,if one channel is blocked due to excessive interference or distant range,the communication will be re-established via another device.

The uplink transmission rateof vehiclemto RSUyand the downlink transmission rateof RSUyto vehiclenfor V2I communication are defined by

respectively,whereWmandWnare the bandwidth allocated for uplink and downlink.PVdenotes the transmission power of vehicles;PIdenotes the transmission power of RSUs.hm,yandhy,nrepresents the small-scale fading power component,which are related to the frequency and assumed to be an exponential distribution of the unit mean.αm,yandαy,nare the large-scale fading effect which consists of path loss and shadowing.Additionally,σ2represents the power of Additive White Gaussian Noise(AWGN)andIcis the interference in the selected channel.

whereWVis the V2V communication bandwidth,andhm,nandαm,nare the small-scale fading and the largescale fading effects respectively.

2.2 Problem Formulation

In this paper,the urban case evaluation method is shown in Figure 1 We designed a request delivery task,where each vehicle will send a packet with a fixed size to the target vehicle,and the router for this transmission can be selected from other vehicles,Base Station and Road Side Units(BS/RSU).Each vehicle and RSU are indexed toVm∈VandIn∈I,respectively.We denote the number of packets byXand their sizes byZ.

Figure 1.System overview of the urban VANET.

Thetth-hop delayTt,x,ycan be calculated by

whereRI2Iis the wired transmission rate between RSUs,and other notations are in consistent with Section 2.1.

The goal of the routing algorithm is to minimize the overall vehicle service latency that the process can be expressed as the following optimization problem,

whereαt,x,yis a binary variable.Ifαt,x,y=1,it means that thetth-hop vehiclexwill send a packet to vehicley.The first constraint denotes all the packets received by vehiclexin(t −1)th-hop will be sent out at thetthhop.The last two constraints indicate that,at the starting time,source vehicleSmust choose a device as the router,and one packet is sent to the destination vehicleDonly once throughout the simulation.

Typically,the problemP1is NP-hard as it is an integer programming problem where vehicles’ location and the fading effect are updated in each step.To solve this problem,we propose an MARL based routing scheme.

III.MARL BASED ROUTING SCHEME

The proposed MARL scheme is to address the V2X routing problem illustrated in Figure 1.First,the observation space was designed to accommodate the environment.Then,followed by the standard action space configuration,our carefully designed reward policy is proposed to respond promptly.Here,the interaction between agents and the routing environment is depicted in Figure 2.

Figure 2.Structure of agents’ interaction in the routing environment.

After modeling the routing problem into the RL interface,we combine the two state-of-the-art methods,Dueling DQN and DDQN[23,24],to solve the overestimation problem and speed up the convergence in the nature DQN[26].Since it is inapplicable to deploy centralized RL in the VENET,we introduce the multiagent strategy to fit the real scenario better.At the end of this section,the implementation of the MARLbased routing algorithm is elaborated.

3.1 Observation Space

We define the states based on three factors,overall latencyT,safety messages,and the local channel information.The safety messages are obtained from neighbor vehicles,which contain positionPk,speedVk,and directionDk.And the local channel information includes channel interferences from other V2V transmittersαk,k′,and from the RSUsαk,y(for allk/=k′,k∈Vandy∈I).As a result,the observation space for the vehiclekis integrated as

3.2 Action Space

A vehicle that carries a packet needs to select another vehicle or RSU as the router.Therefore,the action function can be designed as

3.3 Reward Design

The design of the reward function will directly affect the performance of the model.If we simply design the reward function as a time-dependent reward,when the destination vehicle receives the packet.The delayed reward will cause two problems.One is the huge time consumption in exploratory work,and the other is the difficulty in addressing the credit assignment problem.To achieve an accurate and real-time reward function,we design the reward function with three phases:

whereα,β,λandkare parameters set manually,R represents the transmission range anddis()is the operator of calculating the Euclidean distance.The first phase means the agent will get a time-dependent reward when the packet transmits to the destination vehicle.The second phase indicates that if thetth-hop is successful,the reward will depend on how much the distance change before and after transmission and the third one shows the penalty of transmission failure.

3.4 Learning Algorithm

In the proposed learning algorithm,we firstly use DQN to feed the RL model.Then,two improved methods,DDQN and Dueling DQN are adopted to boost up convergence.Finally,the proposed MARL based routing algorithm by incorporating the RL and multi-agent model is described.

DQNis a combination ofQ-Learning and Deep Neural Network(DNN),which can learn control strategies directly from high-dimensional raw data.In classicQ-Learning,theQvalues of each state-action pair are store inQ-table.However,the high dimensional state and action space in the real application make theQ-table update problem can only be approximately addressed by converting into a function fitting problem.In the following formula,theQfunction approximates the optimalQvalue by updating the parameter

wheresandαdenote the state and action respectively,andθis the parameter matrix that updates in each learning step.Moreover,Q∗is the bestQfunction.The input of DNN is the original data(state),and the output is value evaluation(Qvalue)corresponding to each action.The function of DNN in DQN is to fit theQ-table in the high-dimensional continuous space.And optimized by supervised learning.DQN determines the loss function based on theQ-Learning updating formula:

whereλis the discount rate,s′andα′is the next state and the next action respectively.And the DQN’s loss function is:

whereθ′is the periodical updating targetQnetwork weights.The introduction of the targetQnet not only reduce the correlation between the primaryQvalue and the targetQvalue simultaneously but also improved the algorithm stability.Another improvement of DQN fromQ-Learning is the experience replay,mainly used to solve correlation and non-static distribution problems.Specifically,it stores the transfer samples(s,a,r,s′)obtained from the interaction between each time step agent and the environment into the playback memory unit and then randomly fetch samples for training.

DDQNis proposed by Hasseltet al.[23],who proved that classic DQN tends to overestimate theQvalue of action,and the estimation error will be magnified with the increasing of action space.If the overestimation is non-uniform,it will cause theQvalue of a suboptimal action to exceed the optimalQvalue,and the optimal policy will never be found.The DDQN modify the generation mode of the targetQvalue to be learned as the following equation:

The next state’s optimal action is found within the primaryQnet,and then resorting targetQNet to find theQvalue of the action to form the targetQvalue.Therefore,the maximum value in the targetQnet is unnecessary,which avoids selecting the overestimated suboptimal action.

Dueling DQNis a competitive network model of DQN proposed by Wanget al.[24].The network divides the abstract features extracted by DNN into two branches,one branch represents the state value functionV(s;θ),and another represents the action advantage functionA(s,a;θ)of the dependent state and the added value of selecting an action.Eventually,these two branches are combined to yield theQvalue for each action as the following equation:In this way,each action’s dominant function in this state can be independent of the order.The range ofQvalue can be reduced,redundant degrees of freedom can be removed,and the algorithm’s stability gets improved.

The multi-agent modeldesign is based on the IQL[22],which addressed the difficulty of deploying centralized RL algorithms in VANET routing.To be specific,all vehicles share the sameQnetwork parameters in centralized RL model,so that the input dimension is too large to converge the model.Also,the input design makes it impossible for heterogeneous updating.Therefore,in the real application,the centralized large scale algorithm is not ready to deploy[27].However,in the multi-agent setting,our model assumes only one packet will be transferred from one source vehicle to one destination vehicle at each iteration in the learning stage.The vehicle carrying the packet will choose a neighborhood within the transmission range as a router until the destination vehicle completes receiving the packet.Otherwise,links will break when the distance between the sender and receiver exceeds the transmission distance.In our algorithm,each training step senderkobserves the current state and fed it to the primaryQnet to choose the best action which achieves the highestQvalue with the∊-greedy strategy.The∊-greedy strategy is a soft policy,meaning that the best action will be chosen with probability 1−∊and probability∊for a random action.After interacting with the environment,the current state,action,reward,and the next state are stored in the replay memory as a transition tuple,i.e.,.Then,a mini-batch of experiences will be sampled randomly to update the primaryQnet parameters with the Adaptive Moment Estimation(Adam)[28]gradient-descent method.Many optimizer algorithms are evaluated and compared in[29],which concludes that Adam is the best choice overall.At the end of each episode,the targetQnet parameters will be updated as a primaryQnet copy.In summary,the whole process of our training procedure is shown in Algorithm 1.

3.5 Algorithm Complexity

According to algorithms 6.3 and 6.4 in[30],the time complexity order of DNN is O(n2)both in forward and backward propagation.Since the input space of the algorithm isKfor MARL andK2for the centralized RL method.The time complexity order of the MARL method is O(K2)and centralized RL is O(K4)in one hop.Therefore,the MARL method is less timeconsuming than the centralized RL methods and this method is suitable for delay-sensitive applications.

Algorithm 1.The proposed MARL-based routing algorithm.1:Start environment simulator and generating vehicles 2:Initialize network parameters randomly for all agents 3:for each episode do 4:Update large-scale fading and vehicles information 5:for each step do 6:Observe O(k)t 7:Choose an action A(k)t according to the ∊-greedy strategy 8:Act A(k)t and observe the reward Rt 9:Update channel small-scale fading 10:Observe O(k)t+1 11:StoreO(k)t,A(k)t,Rt,O(k)t+1into reply memory M 12:Compute remain packet size Z 13:if Z ≤0 then 14:Change sender k 15:end if 16:Select mini-batches samples from M 17:Calculate the loss L,defined in Equation(11–14)18:Update primary Q net parameters with ▽L using Adam optimizer 19:end for 20:Update target Q net parameters 21:end for

IV.SIMULATION RESULTS

To evaluate the MARL-based VANET routing algorithm’s performance,we built a simulation environment based on the Manhattan case defined in Annex A of 3GPP TR 36.885[31].The annex regulating vehicle User Equipment(UE)drop,RSU deployment,and mobility model,which contains the specification of road grid,simulation area size,vehicle density,and the magnitude of vehicle speed.Simulation parameters setting,which refers to Lianget al.’s[32]works,are summarized in Table 1,and channel models for two types of wireless links are listed in Table 2.

Table 1.Simulation parameters[31].

Table 2.Simulation parameters[31,33].

Our network in the routing scheme has three fully connected hidden layers,and the number of neurons in each layer is 2048,512,and 128,respectively.We utilize the rectified linear unit(ReLU),f(x)=max(0,x),as the activation function.The∊-greedy policy is used to avoid overfitting during evaluation[26],and Adam[28]optimizer is used for training with a learning rate of 0.001.The small-scale fading effect is changed in 1 ms,and the large-scale fading effect and the position of vehicles are updated every 100 ms.

Moreover,we compare the proposed RL-based routing algorithms with three classic centralized routing protocols AODV[6],DAODV[13]and GPSR[15].The evaluation of these five methods is performed by 10000 simulations in each different vehicle number setting.Figure 3 shows the average delays of centralized RL algorithm,AODV protocol,DAODV protocol,GPSR protocol,and our proposed MARL-based routing scheme in different vehicle densities.It is worth noting that the centralized RL algorithm has an average delay of over 100 ms when the number of vehicles reaches 50.Compared to the rest algorithms,the proposed MARL-based scheme achieves both lower latency and higher stability.It can be observed that the MARL-based scheme keeps a steady 45.8 ms average delay regardless of the traffic volume variations.In contrast,the average delay of AODV,DAODV,and GPSR protocol rises with the increase in vehicles.From the simulation results,the MARL-based routing scheme outperforms 6%-14%of AODV(3.9 ms-7.5 ms),4%-10%of the DAODV(2.8 ms-5.2 ms),and 1%-12%of the GPSR(0.5 ms-6.0 ms).

Figure 3.Average delay of the centralized RL algorithm,DAODV protocol,AODV protocol,GPSR protocol,and our proposed MARL scheme with varying number of vehicles.

Figure 4.Failed packet ratio with the various number of vehicles.

Figure 4 illustrates the ratio of dropout packets in different vehicle capacities under three routing schemes.The centralized RL algorithm suffers an intolerable dropout rate hence not presented in the figure.The proposed MARL routing scheme achievesan overall failed packet ratio of 0.05 %.Our method performs an order of magnitude less dropout rate than the other two algorithms in low vehicle density(less than 80 vehicles in the simulation environment).We believed that in a sparse vehicle distribution,the link between vehicles has a higher probability of breaking;however,the proposed MARL-base method learns mobility patterns which enabled better target estimation.

Figure 5.Communication type distribution of three algorithms(a.AODV,b.DAODV,c.GPSR,and,d.MARL-based algorithm)with a different number of vehicles setting.

To further explain the reason that the proposed MARL-based routing scheme outperforms the AODV,DAODV,and GPSR protocols in delay and stability,we analyze the portion of V2I and V2V links in three methods under different vehicles number settings,as depicted in Figure 5.The ratio of high-performance V2I channel usage in the MARL-based algorithm is higher than the others,and keeps relatively consistent with the increase of participate vehicles.This indicates that the MARL-based algorithm tends to maximize the usage of high-quality communication resources,therefore exhibiting low delay and high stability despite the increase of vehicles.

V.CONCLUTION

This paper has proposed a decentralized routing algorithm for VANET to minimize the network delay under the MARL framework.An innovative input state and reward function were carefully designed for DQN to reduce the overall latency and the dropout rate,especially in low vehicle density.The proposed method was compared with AODV and DAODV protocols in the 3GPP Manhattan mobility model.The simulation results show that the routing delay of the proposed algorithm is robust to the vehicle amount change,and it has a distinctive low failure rate in sparse vehicle distribution scene compared with others.To summarize,this work presented an efficient and intelligent routing approach for vehicle communication,which expect to empower a variety of low latency services to the vehicle network,especially to notify the traffic emergency.

ACKNOWLEDGEMENT

The authors wish to thank Dr.Le Liang,who gave valuable suggestions that helped design the RL model and simulation environment.The authors also would like to thank the support from Mr.Jin Sima,for the guidance of mathematical derivation.This work is supported by the National Science Foundation of China under grant No.61901403,61790551,and 61925106,Youth Innovation Fund of Xiamen No.3502Z20206039 and Tsinghua-Foshan Innovation Special Fund(TFISF)No.2020THFS0109.