车联网中时延感知的依赖任务调度与计算卸载策略

Delay-aware-dependent Task Scheduling and Computation Offloading Strategy for Internet of Vehicles

为了提升车联网对任务依赖型应用的执行响应速度,研究了时延感知的依赖任务调度与计算卸载策略。具体包括以下4个设计要点。首先,基于有向无环图(Directed Acyclic Graph,DAG)构建了车辆端的任务依赖型应用模型,不仅详细表征了每个应用中任务间的依赖关系,还构建了多车多应用场景下的总任务DAG。其次,基于部分卸载模式,设计了综合考虑排队时间、计算时间以及结果传输时间等多时延项的本地计算与卸载模型,进而制定了每个任务的执行等待时间表达式和任务总处理时延最小化优化问题。再次,本着“以更短时间完成更多任务”的设计原则,基于任务依赖性特点,设计了任务的执行时间优先级与等待时间优先级指标。基于此,设计综合考虑2种时间优先级指标的改进异构环境下最早完成时间(Heterogeneous Earliest Finish Time,HEFT)任务调度算法,并获得旨在提升时延性能的最优任务调度顺序。最后,为了获得每个任务的最优卸载决策,构建了任务计算的马尔可夫决策过程,进而设计了基于深度确定性策略梯度(Deep Deterministic Policy Gradient,DDPG)的任务卸载算法,获得了最优的计算卸载决策。在不同的网络设置下进行了仿真试验。研究结果表明,与现有的时延最小化方案相比,所提任务调度与计算卸载方案具有明显的时延性能优势,更适用于对低时延要求较高的车联网环境。

To improve the response speed of task-dependent applications in Internet of Vehicles(IoV),a delay-aware-dependent task scheduling and computational offloading strategy was investigated that included the following three design points.First,a vehicle-side task-dependency application model was constructed based on a directed acyclic graph(DAG),which characterizes in detail the dependencies between tasks in each application while constructing the total task DAG for multi-vehicle multi-application scenarios.Second,a local computational and offloading model was designed based on the partial offloading mode,which considers multiple delay terms such as queuing time,computational time,and result transmission time.Expressions for the execution waiting time and delay minimization optimization problem were also formulated.Third,based on the design principle of“completing more tasks in less time”and the characteristics of task dependency,the execution and waiting time priority indicators of tasks were designed.An improved heterogeneous earliest finish time task scheduling algorithm was then designed that fully considers these time priority indicators.Next,an optimal task scheduling order to improve the delay performance was obtained.Finally,to obtain the optimal offloading decision for each task,a Markov decision process was constructed for task calculation.A task offloading algorithm based on a deep deterministic policy gradient was designed,and the optimal computational offloading decision was obtained.Simulation experiments were conducted under different network settings.Results show that compared with existing delay minimization schemes,the proposed scheme has obvious delay performance advantages and is more suitable for IoV with strict low-delay requirements.