Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (2): 286-292.doi: 10.11896/jsjkx.221200069

• Computer Network • Previous Articles     Next Articles

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)

951

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

CLC Number: 

  • 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.
[1] WANG Zhihong, WANG Gaocai, ZHAO Qifei. Multi-objective Optimization of D2D Collaborative MEC Based on Improved NSGA-III [J]. Computer Science, 2024, 51(3): 280-288.
[2] LIN Xinyu, YAO Zewei, HU Shengxi, CHEN Zheyi, CHEN Xing. Task Offloading Algorithm Based on Federated Deep Reinforcement Learning for Internet of Vehicles [J]. Computer Science, 2023, 50(9): 347-356.
[3] LEI Xuemei, LIU Li, WANG Qian. MEC Offloading Model Based on Linear Programming Relaxation [J]. Computer Science, 2023, 50(6A): 211200229-5.
[4] GAO Lixue, CHEN Xin, YIN Bo. Task Offloading Strategy Based on Game Theory in 6G Overlapping Area [J]. Computer Science, 2023, 50(5): 302-312.
[5] PEI Cui, FAN Guisheng, YU Huiqun, YUE Yiming. Auction-based Edge Cloud Deadline-aware Task Offloading Strategy [J]. Computer Science, 2023, 50(4): 241-248.
[6] SHANG Yuye, YUAN Jiabin. Task Offloading Method Based on Cloud-Edge-End Cooperation in Deep Space Environment [J]. Computer Science, 2023, 50(2): 80-88.
[7] XUE Jianbin, WANG Hainiu, GUAN Xiangrui, YU Bowen. Study on Dynamic Task Offloading Scheme Based on MAB in Vehicular Edge Computing Network [J]. Computer Science, 2023, 50(11A): 230200186-9.
[8] WU Chun, CHEN Long, SUN Yifei, WU Jigang. Fairness-aware Service Caching and Task Offloading with Cooperative Mobile Edge Computing [J]. Computer Science, 2023, 50(11A): 230200095-8.
[9] ZHANG Junna, CHEN Jiawei, BAO Xiang, LIU Chunhong, YUAN Peiyan. Cost-minimizing Task Offload Strategy for Mobile Devices Under Service Cache Constraint [J]. Computer Science, 2023, 50(10): 275-281.
[10] LI Meng-fei, MAO Ying-chi, TU Zi-jian, WANG Xuan, XU Shu-fang. Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient [J]. Computer Science, 2022, 49(7): 271-279.
[11] XIE Wan-cheng, LI Bin, DAI Yue-yue. PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing [J]. Computer Science, 2022, 49(6): 3-11.
[12] GAO Yue-hong, CHEN Lu. Survey of Research on Task Offloading in Mobile Edge Computing [J]. Computer Science, 2022, 49(11A): 220400161-7.
[13] WANG Chen-hua, HOU Shou-lu, LIU Xiu-lei. Cost-aware IoT Data Processing in Edge-Cloud Collaborative Computing [J]. Computer Science, 2022, 49(11A): 211000101-7.
[14] LIANG Jun-bin, ZHANG Hai-han, JIANG Chan, WANG Tian-shu. Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing [J]. Computer Science, 2021, 48(7): 316-323.
[15] SONG Hai-ning, JIAO Jian, LIU Yong. Research on Mobile Edge Computing in Expressway [J]. Computer Science, 2021, 48(6A): 383-386.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.