随着汽车制造业和物联网的快速发展，许多新兴应用和技术应运而生。这些应用在处理相关数据时，需要大量的存储和计算资源，这对通信网络服务质量提出了更高的要求。车联网（IoV，Internet-of-Vehicles）是以车内网、车际网及车载移动网络为基础的大型网络。然而，现有的车联网无法满足新型车载应用的需求，为此引入了移动边缘计算（MEC，Mobile Edge Computing）技术。MEC将强大的计算和存储能力从远程云推向网络边缘，从而实现低延迟的效果，并能减少带宽的消耗。目前，许多学者致力于将车辆网络集成到MEC中^[1-2]，从而形成了车辆边缘计算（VEC，Vehicle Edge Computing）的新模式。灵活的移动边缘机制可以应用于智能交通系统、传感器系统^[3]、铁路信息系统^[4]、铁路通信系统^[5]等领域。

基于MEC的车联网是近年来的研究热点。在计算任务卸载的过程中，车辆的移动性会造成卸载任务频繁中断，难以满足时延敏感型任务的要求^[6]。而由于边缘计算环境中的设备和服务器资源异构性较大^[7]，需要根据任务特性和设备状态进行资源分配^[8]。此外，边缘环境中设备状态和网络状况随时可能变化，需要在动态变化的环境下作出合适的卸载决策^[9]。车辆的无规则移动和车速的动态变化也会使得计算任务卸载调度方案的复杂性显著提升。

计算卸载一直以来都得到了广泛的关注和研究。文献[10]提出了一种用于车载网路的基于云的移动边缘计算卸载框架，设计了一种预测模式传输方案；文献[11]提出了一种涉及路边单元（RSU，Road Side Unit）和车辆的合作下载机制，考虑了不同的车辆角色；文献[12]研究了软件定义的车联网络中的延迟容忍数据缓存和任务计算；文献[13]讨论了如何将计算任务从移动设备卸载到边缘服务器，以降低移动设备的计算负载和延迟；文献[14]研究了多信道无线干扰环境下移动边缘云计算的多用户计算卸载问题；文献[15]提出了一个用于提高任务执行效率的分布式多跳任务卸载决策模型，将卸载问题建模为带约束的广义分配模型进行求解，但并未优化能耗。计算卸载决定了任务是在本地执行还是在边缘执行，两者拥有不同的计算能耗，计算密集型任务从移动设备迁移到附近的 MEC服务器时还需要考虑无线传输的能耗^[16]。目前，对车联网计算卸载的研究还存在许多局限性，比如未涉及时延和能耗成本的同时优化。

基于以上问题，本文研究车辆边缘计算的通信和计算模型，在考虑每个车辆应用的任务时延限制下，构建多目标优化目标函数，以达到时延和能耗成本最小化的目的。参考非支配排序遗传思想，通过引入交叉变异、非支配排序、拥挤度排序等技术，提出了多目标任务卸载算法，最后通过实验验证了其性能。

1   模型构建

1.1   通信和计算系统模型

构建车辆边缘计算的通信和计算模型。考虑一段长直道路，按RSU划分区域，有N个区域的集合$R=\left\{{r}_{1},\;{r}_{2},\;\cdots ,\;{r}_{N}\right\}$。有M辆车的集合$V=\left\{{v}_{1},\;{v}_{2},\;\cdots ,\;{v}_{M}\right\}$ ，每个车辆都有一个任务，每个任务用三元组表示：${T}_{i}=\left\{{d}_{i},\;{C}_{i},\;{t}_{i}^{\max}\right\}$。其中，${d}_{i}$表示任务${T}_{i}$的大小；${C}_{i}$表示计算任务所需的CPU指令周期数；${t}_{i}^{\max}$表示任务所能接受的最大时间延迟。

用 ${x}_{i}^{k}$ 表示任务 ${T}_{i}$ 在在区域 $k$ 本地卸载的比例，${y}_{i}^{k}$ 表示在RSU卸载的比例，$(1-{x}_{i}^{k}-{y}_{i}^{k})$ 表示在基站卸载的比例。

（1）任务${T}_{i}$在区域$k$本地计算时间为

式（1）中，${f}_{i}$ 为车辆本地的本地计算能力。

（2）任务 ${T}_{i}$ 在区域 $k$ 本地计算能耗为

式（2）中，$P_i$为车辆i的传输功率。

（3）任务 ${T}_{i}$ 在区域 $k$ 卸载到路边单元的计算时间为

式（3）中，${S}_{i}^{r}$ 为车辆和RSU之间的无线通信速率；${f}_{k}^{r}$ 为路边单元 r_k 的计算能力。

（4）任务 ${T}_{i}$ 在区域 $k$ 卸载到路边单元上的计算能耗为

式（4）中，${P}_{k}^{r}$ 为路边单元的功率。

（5）任务 ${T}_{i}$ 在区域 $k$ 卸载到基站的基站计算时间为

式（5）中，${S}_{i}^{b}$ 为车辆和基站之间的无线通信速率；${f}_{k}^{b}$ 为基站的计算能力。

（6）任务 ${T}_{i}$ 在区域 $k$ 卸载到基站的计算能耗为

式（6）中，${P}_{k}^{b}$ 为基站的功率。

1.2   多目标优化目标函数

定义求和目标函数：求和M个车辆在N个区域中时间T和能耗成本E分别为

最小化系统和能耗的多目标优化目标函数为

式（10）代表比例值总是在[0,1]范围内；式（11）代表每个车辆在一个时隙内并行卸载，在本地卸载或在RSU上进行卸载的比例值之和在0到1之间；式（12）代表每个任务的时延约束不能超过任务所能接受的最大时间延迟。

2   算法设计

2.1   多目标任务卸载算法思路

本文参考非支配排序遗传算法（ NSGA-II，Non-dominated Sorting Genetic Algorithm-II）^[17]思想求解上述联合优化问题，通过引入交叉变异、非支配排序、拥挤度排序等技术，提出了本文的多目标任务卸载算法（MOTOA，Multi-Objective Task Offloading Algorithm）。

本文采用实数编码对计算卸载方案进行编码。表1给出了用于边缘服务器的计算卸载方案的编码示例。

表  1  编码示例

卸载比例	${x}_{1}^{1}$	${x}_{1}^{2}$	${x}_{2}^{1}$	${x}_{2}^{2}$	${y}_{1}^{1}$	${y}_{2}^{1}$	${y}_{1}^{2}$	${y}_{2}^{2}$
卸载比例值	0.40	0.13	0.05	0.17	0.20	0.55	0.11	0.22

下载: 导出CSV 

| 显示表格

本例中有2个区域和2个任务。第1个区域本地计算了第1个任务40%的结果（即${x}_{1}^{1}= 0.40$）；第一个区域RSU上的边缘服务器计算了第1个任务20%的结果（即${y}_{1}^{1}= 0.20$）；第2个区域本地计算了第2个任务的17%的结果（即${x}_{2}^{2}= 0.17$）；第2个区域的RSU上的边缘服务器计算了第2个任务的22%（即${y}_{2}^{2}= 0.22$）。接着，使用交叉变异生成子代种群，再借助非支配排序和拥挤度排序，更新种群。此外，在非支配排序中，将时延与能耗的倒数作为个体适应度以进行排序。

2.2   具体步骤

本文提出的MOTOA具体步骤如下：

（1）根据编码基因，随机生成满足约束的第1代种群${P}_{1}$，个体数为$n$，设置迭代次数$\lambda$，${F}_{0}=\varnothing$；

（2）当迭代次数小于等于$\lambda$时，执行步骤（3），否则执行步骤（8）；

（3）对于第$g$次迭代，对${P}_{g}$进行交叉变异生成子代种群，去掉不满足约束的个体，获得${Q}_{g}$；

（4）令${R}_{g}={{P}_{g}\cup Q}_{g}$，并对${R}_{g}$使用非支配排序得到分层结果（${F}_{1},\;{F}_{2},\;\cdots ,\;{F}_{l}$） ，非支配排序执行过程中，以时延与能耗的倒数作为个体适应度；

（5）将分层依次合并，直到正好有$n$个或正好超过$n$个个体，并且合并之前已经对这些分层进行了拥挤度排序，得到合并后种群 ${S}_{g}$；

（6）如果${|S}_{g}|=n$，则${P}_{g+1}=$ ${S}_{g}$；如果${|S}_{g}| > n$，则去掉超过部分，因为已经进行过拥挤度排序，去掉的都是拥挤度小的较差个体；

（7）返回步骤（2）；

（8）迭代结束，令$P={P}_{\mathrm{\lambda }+1}$，返回最终结果$P$。

根据文献[17]，NSGA-II的时间复杂度为$O\left(m{n}^{2}\right)$，其中，$m$代表优化目标个数；$n$代表种群个体数量。本文为双目标优化，且迭代$\lambda$次，因此，MOTOA的时间复杂度为$O\left(2\lambda {n}^{2}\right)=O\left(\lambda {n}^{2}\right)$。

3   仿真实验

在车联网多目标任务卸载场景中，对本文提出的MOTOA的各项性能进行评估。

3.1   实验参数设定

设任务的数据量大小为3 ~ 8 kB，任务的时延限制为2 ~ 5 ms。实验采用50个最大交通流量为1000的城市中心区域车联网多目标卸载场景。每3个区域共用一个基站。实验所采用的参数如表2所示。

表  2  实验参数

参数	值
$\mathrm{车}\mathrm{辆}i\mathrm{的}\mathrm{传}\mathrm{输}\mathrm{功}\mathrm{率}{P}_{i}$	40 dBm
任务${T}_{i}$的大小${d}_{i}$	3～8 kB
任务${T}_{i}$所能接受的最大时间延迟${t}_{i}^{max}$	2～5 ms
车辆$i$本地的计算能力${f}_{i}$	200～1000 MIPS
区域$k$路边单元的计算能力${f}_{k}^{r}$	800～2000 MIPS
区域$k$基站的计算能力${f}_{k}^{b}$	2000～4000 MIPS

下载: 导出CSV 

| 显示表格

3.2   实验结果

本节通过仿真实验对MOTOA的执行时间、总能耗、任务满足自身时延限制的比例及传输系统吞吐量进行评估，并与以下4个对比算法进行比较。

（1）本地计算：任务只利用车辆本地的计算能力处理计算任务，不将任务卸载到其他服务器计算。

（2）边缘服务器计算：车辆任务只利用车辆所在区域RSU的边缘服务器进行任务卸载计算，不利用车辆本地和基站的计算能力。

（3）NGTO（Non-Cooperative Game Task Offloading）：文献[18]提出的一种基于非合作博弈的高效任务卸载方案，其中，卸载决策通过博弈论方法由MEC服务器或远程云服务器做出。

（4）MOO（Multi-Objective Optimization）：文献[19]提出的一种多目标优化算法，在考虑截止期限约束的同时，根据延迟和能量目标优化车联网中的任务卸载过程。

3.2.1   执行时间

不同方案下执行时间的对比如图1所示。

图  1  不同方案的任务执行时间比较

下载: 全尺寸图片 幻灯片

随着车辆任务的增加，MOTOA增长最慢，执行时间也最小。此外，当任务数量较多时，MOTOA的性能与本地计算、边缘服务器计算方案出现差距。与其他算法相比，MOTOA的时延平均减少了近32%。MOO方案也是一种优秀的多目标任务卸载算法，利用贪心思想以降低时延，根据当前状态选择最优的决策，但与本方案仍存在差距。在NGTO方案中，每个车辆都只考虑自己的利益，从而导致一些车辆可能被过度利用，其时延仍大于MOTOA。

3.2.2   总能耗

不同方案下的总能耗比较如图2 所示。

图  2  不同方案的能耗比较

下载: 全尺寸图片 幻灯片

与本地计算、边缘服务器计算方案相比，MOTOA具有明显优势，实现了总能耗最低，最多可降低约28%能耗。此外，当任务数量为10、20、30和40时，本文算法的性能优于本地计算方案。当任务数量达到50，MOTOA的性能与本地计算基本持平，这是因为任务被卸载到不同的目的地，导致传输能耗增加，但性能是在可以接受的范围内。与MOO和NGTO算法相比，本文方案在能耗方面也更有优势。

3.2.3   任务满足自身时延限制的比例

不同方案下任务满足自身时延限制的比例如图3所示。

图  3  不同方案下任务满足自身时延限制的比例

下载: 全尺寸图片 幻灯片

实际任务可能对时延是敏感的，本文研究不同方案下的任务是否满足其时延限制，从图3可以看出，与本地计算、边缘服务器计算和其他算法相比，MOTOA基本满足所有任务自身的时延限制，性能更优。因为没有足够的计算资源，本地计算方案无法满足大多任务的时延限制要求。此外，当任务数量过多时，仅靠车辆和RSU的计算能力可能无法处理过多的任务，所以满足任务时延限制率将降低。MOO方案是基于贪心的角度求解，初始能较好满足任务时延限制，但随着需要处理的任务数据量增多，因为只关注整体时间的最优，没有确保每个任务可以在自身时延限制内完成，其满足任务时延限制的比率降低。NGTO方案中每个车辆用户更多关注自身的利益，故其满足任务时延限制的比率也将降低。

3.2.4   传输系统吞吐量

不同方案下传输系统吞吐量比较如图4所示。

图  4  不同方案下传输系统吞吐量比较

下载: 全尺寸图片 幻灯片

可知，随着任务数量的逐渐增多，每种任务卸载方案传输系统吞吐量都有所增加。MOO和NGTO方案的总体吞吐量也高于本地计算和边缘服务器计算方案，但本文方案的吞吐量相较于另外4种算法明显较高，相较于只在本地计算，其吞吐量增加了2倍，相较于将任务只卸载到边缘服务器计算，传输系统吞吐量增加了将近1倍。这是因为MOTOA算法充分利用了计算资源。

4   结束语

本文在车载边缘的场景下考虑车联网中的多目标任务卸载调度优化问题。考虑通信资源和计算资源，针对动态的车联网环境，借助非支配排序遗传算法，提出多目标任务卸载算法。通过仿真实验对本文算法的各项性能进行了评估，结果表明，该算法可有效降低系统的时延和损耗。

下一步还可以考虑V2V通信和不同路边单元之间的合作，通过车辆和车辆之间的通信完成协作计算。另外，可以将路边单元划分为不同的协作集群，在不同集群之间考虑路边单元的协作。