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

Online Task Offloading Decision Algorithm for High-speed Vehicles

作　　者：丁爽[1,2] 曹沐雨 何欣 DING Shuang;CAO Muyu;HE Xin(School of Software,Henan University,Kaifeng,Henan 475004,China;Henan International Joint Laboratory of Intelligent Network Theory and Key Technology,Kaifeng,Henan 475004,China)

机构地区：[1]河南大学软件学院,河南开封475004 [2]河南智能网络理论与关键技术国际联合实验室,河南开封475004

出　　处：《计算机科学》2024年第2期286-292,共7页Computer Science

基　　金：中国博士后科学基金面上资助项目(2020M672217);2022年度河南省重点研发与推广专项(科技攻关)(222102210133);2020年度河南省重大科技专项(201300210400)。

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

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

分 类 号：TN929.5[电子电信—通信与信息系统]