Vehicular clouds (VCs) are modern platforms for processing of
computation-intensive tasks over vehicles. Such tasks are often represented as
directed acyclic graphs (DAGs) consisting of interdependent vertices/subtasks
and directed edges. In this paper, we propose a graph neural network-augmented
deep reinforcement learning scheme (GA-DRL) for scheduling DAG tasks over
dynamic VCs. In doing so, we first model the VC-assisted DAG task scheduling as
a Markov decision process. We then adopt a multi-head graph attention network
(GAT) to extract the features of DAG subtasks. Our developed GAT enables a
two-way aggregation of the topological information in a DAG task by
simultaneously considering predecessors and successors of each subtask. We
further introduce non-uniform DAG neighborhood sampling through codifying the
scheduling priority of different subtasks, which makes our developed GAT
generalizable to completely unseen DAG task topologies. Finally, we augment GAT
into a double deep Q-network learning module to conduct subtask-to-vehicle
assignment according to the extracted features of subtasks, while considering
the dynamics and heterogeneity of the vehicles in VCs. Through simulating
various DAG tasks under real-world movement traces of vehicles, we demonstrate
that GA-DRL outperforms existing benchmarks in terms of DAG task completion
time.

本文提出了一种基于图神经网络和深度强化学习的车联网环境下 DAG 任务调度方案，通过采用多头注意力网络，对 DAG 子任务进行特征提取，同时考虑了任务拓扑结构和车辆动态特征，通过模拟实验表明该方案在完成 DAG 任务时间方面优于现有基准。