计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (2): 286-292.doi: 10.11896/jsjkx.221200069

• 计算机网络 • 上一篇    下一篇

面向高速行驶车辆的在线任务卸载决策算法

丁爽1,2, 曹沐雨1, 何欣1,2   

  1. 1 河南大学软件学院 河南 开封475004
    2 河南智能网络理论与关键技术国际联合实验室 河南 开封475004
  • 收稿日期:2022-12-09 修回日期:2023-04-06 出版日期:2024-02-15 发布日期:2024-02-22
  • 通讯作者: 何欣(hexin@henu.edu.cn)
  • 作者简介:(ds@henu.edu.cn)
  • 基金资助:
    中国博士后科学基金面上资助项目(2020M672217);2022年度河南省重点研发与推广专项(科技攻关)(222102210133);2020年度河南省重大科技专项(201300210400)

Online Task Offloading Decision Algorithm for High-speed Vehicles

DING Shuang1,2, CAO Muyu1, HE Xin1,2   

  1. 1 School of Software,Henan University,Kaifeng,Henan 475004,China
    2 Henan International Joint Laboratory of Intelligent Network Theory and Key Technology,Kaifeng,Henan 475004,China
  • Received:2022-12-09 Revised:2023-04-06 Online:2024-02-15 Published:2024-02-22
  • About author:DING Shuang,born in 1982,associate professor,Ph.D,is a senior member of CCF(No.91019M).Her main research interests include mobile crowd sensing and mobile edge computing.HE Xin,born in 1974,professor,Ph.D supervisor,is a senior member of CCF(No.16041S).His main research intere-sts include computer network and mobile computing.
  • Supported by:
    General Support from China Postdoctoral Science Foundation(2020M672217),2022 Henan Province Key R&D and Promotion Project(Science and Technology Research)(222102210133) and Major Science and Technology Projects of Henan Province in 2020(201300210400).

PDF (PC)

949

摘要： 车载边缘计算中的任务卸载决策主要解决任务何时卸载,以及卸载至哪里执行的问题。车辆的高速行驶会造成卸载接入设备频繁变化,卸载通信链路随时可能中断,这要求车辆一旦获得卸载机会,就必须立即做出卸载决策。现有的卸载决策研究专注于如何最大化任务卸载执行增益,未充分考虑卸载决策时效对卸载策略的影响,导致提出的卸载决策方法的时间复杂度和空间复杂度高,无法用于高速行驶车辆的在线任务卸载决策。为解决上述问题,首先综合考虑卸载决策时效和卸载增益因素的影响,建立高速行驶车辆的任务卸载决策模型,并将其转化为类秘书问题。然后,提出了一种基于加权二部图匹配的在线车载任务卸载决策算法OODA,以协助车辆在依次经过多个异构的边缘服务器时,做出实时的任务卸载决策,并最大化整体卸载执行增益。最后,理论分析OODA算法的竞争比,并采用仿真实验验证该算法的可行性和有效性。

关键词: 车载边缘计算, 任务卸载, 秘书问题, 加权二部图匹配

Abstract: When and where to offloading tasks are the main problems to be solved in the task offloading decision in vehicular edge computing.High speed driving of the vehicle causes frequent changes of offloading access devices,and the offloading communication between the vehicle and the offloading access device may break at any time.This requires that the offloading decision should be made immediately once the vehicle obtains an offloading opportunity.The existing offloading decision research focuses on how to maximize the offloading gain,without fully considering the impact of the timeliness of offloading decision on offloading strategy.As a result,the proposed offloading decision methods have high time and space complexity,and cannot be used for online task offloading decisions of high-speed vehicles.In order to solve the above problems,this paper first comprehensively considers the influence of offloading decision-making timeliness and offloading gain factors,establishes a task offloading decision model for high-speed vehicles,and transforms it into a variation of the secretary problem.Then,an online vehicle task offloading decision algorithm OODA based on weighted bipartite graph matching is proposed to assist the vehicle to make real-time task offloading decisions when passing through multiple heterogeneous edge servers sequentially,and maximize the overall offloading gain.Finally,theoretical analysis shows that the competitive ratio of OODA algorithm is analyzed theoretically.Extensive simulation results show that OODA is feasible and effective.

Key words: Vehicle edge computing, Task offloading, Secretaryproblem, Weighted bipartite graph matching

中图分类号: 

  • TN929.5
[1]ESKANDARIAN A,WU C X,SUN C Y.Research Advancesand Challenges of Autonomous and Connected Ground Vehicles [J].IEEE Transactions on Intelligent Transportation Systems,2021,22(2):683-711.
[2]SHI W S,SUN H,CAO J,et al.Edge Computing-An Emerging Computing Model for the lnternet of Everything Era [J].Journal of Computer Research and Development,2017,54(5):907-924.
[3]FAN Y F,YUAN S,CAI Y,et al.Deep Reinforcement Lear-ning-based Collaborative Computation Offloading Scheme in Vehicular Edge Computing [J].Computer Science,2021,48(5):270-276.
[4]GU B,ZHOU Z Y.Task Offloading in Vehicular Mobile Edge Computing:A Matching-Theoretic Framework [J].IEEE Vehicular Technology Magazine,2019,14(3):100-106.
[5]LI C,LIU F G,WANG B,et al.Dependency-Aware VehicularTask Scheduling Policy for Tracking Service VEC Networks [J].IEEE Transactions on Intelligent Vehicles,2023,8(3):2400-2414.
[6]ZHAN W H,LUO C B,WANG J,et al.Deep-Reinforcement-Learning-Based Offloading Scheduling for Vehicular Edge Computing [J].IEEE Internet of Things Journal,2020,7(6):5449-5465.
[7]WANG Y P,LANG P,TIAN D X,et al.A Game-Based Computation Offloading Method in Vehicular Multiaccess Edge Computing Networks [J].IEEE Internet of Things Journal,2020,7(6):4987-4996.
[8]DAI P L,HU K W,WU X,et al.Asynchronous Deep Reinforcement Learning for Data-Driven Task Offloading in MEC-Empowered Vehicular Networks[C]//IEEE INFOCOM 2021－IEEE Conference on Computer Communications.Vancouver,BC,Ca-nada:IEEE,2021:1-10.
[9]DAI P L,LIU K,WU X,et al.A Learning Algorithm for Real-Time Service in Vehicular Networks with Mobile-Edge Computing[C]//2019 IEEE International Conference on Communications(ICC).Shanghai,China:IEEE,2019:1-6.
[10]DUAN X T,ZHOU Y K,TIAN D X,et al.Weighted Energy-Efficiency Maximization for a UAV-Assisted Multiplatoon Mobile-Edge Computing System [J].IEEE Internet of Things Journal,2022,9(19):18208-18220.
[11]NING Z L,DONG P R,WANG X J,et al.Deep ReinforcementLearning for Intelligent Internet of Vehicles:An Energy-Efficient Computational Offloading Scheme [J].IEEE Transactions on Cognitive Communications and Networking,2019,5(4):1060-1072.
[12]PREATER J.On Multiple Choice Secretary Problems [J].Mathematics of Operations Research,1994,19(3):597-602.
[13]KORULA N,PAL M.Algorithms for Secretary Problems onGraphs and Hypergraphs[C]//International Colloquium on Automata,Languages and Programming.Berlin,Heidelberg:Springer,2008:508-520.
[14]HU J T,WANG G C,XU X T.Task Migration Strategy with Energy Optimization in Mobile Edge Computing [J].Computer Science,2020,47(6):260-265.
[15]KESSELHEIM T,RADKE K,TÖNNIS A,et al.An optimalonline algorithm for weighted bipartite matching and extensions to combinatorial auctions[C]//European symposium on algorithms.Berlin,Heidelberg:Springer,2013:589-600.
[16]REIFFENHAUSER R.An optimal truthful mechanism for the online weighted bipartite matching problem[C]//Proceedings of the Thirtieth Annual ACM－SIAM Symposium on Discrete Algorithms.San Diego California:Society for Industrial and Applied Mathematics,2019:1982-1993.
[17]TONG Y X,SHE J Y,DING B,et al.Online mobile micro-task allocation in spatial crowdsourcing[C]//2016 IEEE 32nd International Conference on Data Engineering(ICDE).Helsinki,Finland:IEEE,2016:49-60.
[18]ZHAO G M,XU H L,ZHAO Y M,et al.Offloading tasks with dependency and service caching in mobile edge computing[J].IEEE Transactions on Parallel and Distributed Systems,2021,32(11):2777-2792.
[19]CAI L F,WEI X L,XING C Y,et al.Failure-resilient DAG Task Rescheduling in Edge Computing [J].Computer Science,2021,48(10):334-342.
[20]XU C,ZHENG G Y,ZHAO X W.Energy-minimization task offloading and resource allocation for mobile edge computing in NOMA heterogeneous networks[J].IEEE Transactions on Vehicular Technology,2020,69(12):16001-16016.
[21]BORODIN A,EL-YANIV R.Online computation and competitive analysis[M].Cambridge University Press,2005:23-29.
[22]PATRO S,SAHU K.Normalization:A preprocessing stage[J].International Advanced Research Journal in Science,Engineering and Technology,2015,2(3):20-22.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发