车联网中基于联邦深度强化学习的任务卸载算法.pdf

h t t p:/ww wj s j k x c o mD O I:/j s j k x 到稿日期:返修日期:基金项目:国家自然科学基金();福建省自然科学基金杰青项目(J )T h i sw o r kw a ss u p p o r t e db y t h eN a t i o n a lN a t u r a l S c i e n c eF o u n d a t i o no fC h i n a()a n dN a t u r a l S c i e n c eF o u n d a t i o no fF u j i a nP r o v i n c e f o rD i s t i n g u i s h e dY o u n gS c h o l a r s(J )通信作者:陈星(c h e n x i n g f z u e d u c n)车联网中基于联邦深度强化学习的任务卸载算法林欣郁姚泽玮胡晟熙陈哲毅陈星福州大学计算机与大数据学院福州 福建省网络计算与智能信息处理重点实验室福州 (l i n x y c o m)摘要随着车联网应用服务体系日益丰富,计算资源有限的车辆难以处理这些计算密集和时延敏感的车联网应用.计算卸载作为移动边缘计算中的一种关键技术可以解决这一难题.对于车联网中动态的多车辆多路侧单元的任务卸载环境,提出了一种基于联邦深度强化学习的任务卸载算法.该算法将每辆车都看作是智能体,采用联邦学习的框架训练各智能体,各智能体分布式决策卸载方案,以最小化系统的平均响应时间.设置评估实验,在多种动态变化的场景下对提出的算法的性能进行对比分析.实验结果显示,提出的算法求解出的系统平均响应时间短于基于规则的算法和多智能体深度强化学习算法,接近于理想方案,且求解时间远短于理想方案.实验结果表明,所提算法能够在可接受的算法执行时间内求解出接近于理想方案的系统平均响应时间.关键词:边缘计算;任务卸载;车联网;深度强化学习;联邦学习中图法分类号T P T a s kO f f l o a d i n gA l g o r i t h mB a s e do nF e d e r a t e dD e e pR e i n f o r c e m e n tL e a r n i n gf o r I n t e r n e t o fV e h i c l e sL I NX i n y u,YA OZ e w e i,HUS h e n g x i,CHE NZ h e y i a n dCHE NX i n gC o l l e g eo fC o m p u t e ra n dD a t aS c i e n c e,F u z h o uU n i v e r s i t y,F u z h o u ,C h i n aF u j i a nP r o v i n c i a lK e yL a b o r a t o r yo fN e t w o r k i n gC o m p u t i n ga n dI n t e l l i g e n t I n f o r m a t i o nP r o c e s s i n g,F u z h o u ,C h i n aA b s t r a c t W i t ht h er a p i dd e v e l o p m e n to f t h es e r v i c es y s t e mo f I n t e r n e to fV e h i c l e sa p p l i c a t i o n s,v e h i c l e sw i t hl i m i t e dc o m p u t a t i o n a l r e s o u r c e sh a v ed i f f i c u l t y i nh a n d l i n gt h e s ec o m p u t a t i o n i n t e n s i v ea n dl a t e n c y s e n s i t i v ea p p l i c a t i o n s A sak e yt e c h n i q u ei nm o b i l ee d g ec o m p u t i n g,t a s ko f f l o a d i n gc a na d d r e s st h ec h a l l e n g e S p e c i a l l y,at a s ko f f l o a d i n ga l g o r i t h mb a s e do nf e d e r a t e dd e e pr e i n f o r c e m e n t l e a r n i n g(T O F D R L)i sp r o p o s e df o rd y n a m i cm u l t i v e h i c l em u l t i r o a d s i d e u n i t(m u l t i R S U)t a s ko f f l o a d i n ge n v i r o n m e n t i nI n t e r n e to fV e h i c l e s E a c hv e h i c l e i sc o n s i d e r e da sa na g e n t,a n daf e d e r a t e dl e a r n i n gf r a m e w o r ki su s e dt ot r a i ne a c ha g e n t E a c ha g e n tm a k e sd i s t r i b u t e dd e c i s i o n s,a i m i n gt om i n i m i z et h ea v e r a g es y s t e mr e s p o n s et i m e E v a l u a t i o ne x p e r i m e n t sa r es e tu pt oc o m p a r ea n da n a l y z e t h ep e r f o r m a n c eo f t h ep r o p o s e da l g o r i t h mu n d e rav a r i e t yo fd y n a m i c a l l yc h a n g i n gs c e n a r i o s S i m u l a t i o nr e s u l t ss h o wt h a t t h e a v e r a g e r e s p o n s e t i m eo f s y s t e ms o l v e db y t h ep r o p o s e da l g o r i t h mi s s h o r t e r t h a nt h a t o f t h e r u l e b a s e da l g o r i t h ma n dt h em u l t i a g e n td e e pr e i n f o r c e m e n tl e a r n i n ga l g o r i t h m,c l o s et ot h ei d e a ls c h e m e,a n di t ss o l u t i o nt i m ei sm u c hs h o r t e r t h a nt h e i d e a l s o l u t i o n E x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h a t t h ep r o p o s e da l g o r i t h mi sa b l et os o l v ea na v e r a g es y s t e mr e s p o n s e t i m ew h i c h i sc l o s e t ot h e i d e a l s o l u t i o nw i t h i na na c c e p t a b l ee x e c u t i o nt i m e K e y w o r d s M o b i l ee d g ec o m p u t i n g,T a s ko f f l o a d i n g,I n t e r n e to fV e h i c l e s,D e e pr e i n f o r c e m e n t l e a r n i n g,F e d e r a t e d l e a r n i n g引言随着我国车联网产业的发展,智能汽车越来越普及,为了满足人们的需求,车联网应用服务体系日益丰富,常见的车联网应用有智能语音助手、自动驾驶、增强现实等.这些应用通常具有计算密集和时延敏感的特征,而车辆端的计算资源通常是有限的,难以在时延约束下完成这些计算密集型任务.移动边缘计算(M o b i l eE d g eC o m p u t i n g,ME C)是一种正在不断发展的新兴计算范式,它在移动云计算(M o b i l eC l o u dC o m p u t i n g,MC C)的基础上,将计算资源从距离用户遥远的云端转移到距离用户更近的边缘,为用户提供高性能和低时延的服务,其可以作为处理计算密集和时延敏感型任务的一种解决方法.近年来,有许多工作将ME C应用到车联网场景中,对计算密集和时延敏感的车联网应用进行处理 .计算卸载是ME C中的一个关键特性,如果总是将任务都卸载到边缘,则容易造成边缘端过载,浪费车辆端的计算资源,并且需要耗费额外的传输时延,造成任务响应时间的延长,从而不能达到最优的系统平均响应时间,甚至无法满足任务的时延约束.因此,将任务或其子任务卸载到哪个计算节点,以平衡计算资源的利用和通信成本,从而达到最短的系统平均响应时间是目前面临的挑战.由于环境具有动态变化性,任务卸载问题通常可以建模为一 个 混 合 整 数 非 线 性 规 划 问 题,它 是 一 个N P难(N P H a r d)的优化问题,现有的研究工作广泛使用粒子群优化算法(P a r t i c l eS w a r m O p t i m i z a t i o n,P S O)、遗传算法(G e n e t i cA l g o r i t h m,GA)等启发式算法进行求解 .启发式算法通常能获得一个较好的近似最优解,但它是在线算法,运行时决策需要较长的求解时间,不满足车联网应用对时延敏感的要求.近年来,已有文献表明ME C中的任务卸载可以被抽象成马尔可夫决策过程(M a r k o vD e c i s i o nP r o c e s s,MD P).强化学习(R e i n f o r c e m e n tL e a r n i n g,R L)的数学理论基础是MD P,并且它是一种离线算法,运行时决策只需要很短的求解时间,通常能满足车联网应用对时延敏感的要求.但是,传统的强化学习无法适应巨大的状态空间和动作空间.随着深度学习(D e e pL e a r n i n g,D L)的发展,近年来有许多研究将深度学习应用在强化学习中,提出了深度强化学习(D e e pR e i n f o r c e m e n tL e a r n i n g,D R L)的概念,并将其应用在ME C中的任务卸载问题,.为了符合现实情况,本文不局限于单设备的任务卸载,而是考虑了多设备同时卸载的场景.在多设备同时卸载的场景中,现有方法常在边缘进行集中式调度 ,这需要非常大的状态空间.本文利用了车辆在系统中是分散的特性,使用分布式方