面向车联网边缘计算的智能计算迁移研究

莫瑞超，许小龙，何 强，刘 琦，赵庆展

1.南京信息工程大学计算机与软件学院，南京210044

2.斯威本科技大学软件和电子工程学院，墨尔本VIC 3122

3.石河子大学信息科学与技术学院，新疆石河子832003

作为未来智能交通系统的核心组成部分，车联网（internet of vehicles,IoV）的相关理论和应用研究目前正在受到学术界和产业界的广泛关注[1].车联网通过实现车辆和路侧单元（road side unit,RSU）的数据交换，依靠高效的信息交换能力以及其他互动和先进的计算能力，实现了交通管理的效率的提升，并且实现了为车辆提供如交通管理、道路智能预测、多媒体服务访问、道路状况监测等服务[2-4].与此同时，随着各种车辆联网基础通信技术的快速发展，基于成熟的车载自组织网络（vehicular ad-hoc network,VANET）技术的IoV 实现了收集得到的道路交通状况既被用于车辆到车辆（vehicle-to-vehicle,V2V）之间的通信，同时也被用来实现车辆到基础设施（vehicle-to-infrastructure,V2I）之间的信息交互，进而实现传感和整合与城市交通流量有关的重要信息，以缓解城市交通拥堵的情况[5-6].

现如今，车联网的应用需求通常来自三个方面：驾驶的安全性、道路交通运输效率和信息服务[7].因此，为了实现车联网应用的各种需求，连接到车联网的车辆所产生的数据需要得到及时的处理[8].然而，由于车辆自身的计算能力有限，实现这些功能需要对移动的车辆产生的计算密集型车载任务进行计算迁移.对于延迟和可靠性不敏感的娱乐应用程序，传统的基于云的工作方式能够将提供有效且正确的返回结果，从而可以大大提高车辆的信息服务能力[9].而对于驾驶的安全性和道路交通运输效率来说，车载任务对于延迟和可靠性是非常敏感的，特别是在紧急避障的路径规划，道路流量识别等方面，此时如果将车载任务迁移至云数据中心的方法是不合适的，因为云数据中心通常位于远离车辆的位置，将计算密集型的车载任务迁移到云数据中新将会产生很高网络延迟，使得安全或时延敏感的车载任务得不到有效的执行，从而可能会引发交通事故[10].

为了应对上述挑战，能够向车载用户提供丰富资源的边缘计算（edge computing,EC）被引入IoV.边缘计算是一种新兴的计算模式，通过将基于基础设施的云计算资源（如计算、存储、带宽等）扩展到网络边缘，从而为车载用户提供更便利的计算服务[11].与传统云相比，边缘计算的引入大大缩短了车载任务与计算资源之间的物理距离，使得车联网所产生的车载任务能够就近传输到边缘服务器上执行，有效保证了车载任务的执行，特别是在自动驾驶中，将5G 网络和IoV 相结合是合适的[12].此外，5G 网络的应用也会使得边缘服务器也能够为车联网提供超高能效、超可靠的计算服务[13].在5G 网络中，频带高于10 GHz 的毫米波（millimeter wave,mmWave）被用于进行数据传输，从而实现了超高的数据传输速率，相比4G 网络的数据传输速率要高出数个量级[14].此外，由于5G 网络属于超密级型组网方式，基站与基站之间的距离仅有几十米到几百米，因此通过毫米波可以实现基站与车载用户之间的快速数据传输速率[15].

当前计算迁移的研究主要集中在时延和能耗等方面优化上.具体来说，在能耗方面，文献[16]构建了一种高效节能的基于移动边缘计算的IoV 资源调度框架，主要关注的是基于边缘服务器的RSU 的能源消耗控制问题.在文献[17]中提出了一种在IoV 中基于MEC 的卸载方法，选择合适的MEC 服务器进行任务管理，该方法综合考虑了车辆移动性和计算任务来进行卸载决策.文献[18]研究了多用户雾计算系统中的节能计算卸载方案，根据用户需要、能耗和延迟约束条件来决定是否将任务卸载到附近的雾节点，并且提出了一种基于乘数交替方向（alternating direction multiplier method,ADMM）的分布式算法.文献[19]提出了一种联合优化任务分配决策和MD 的CPU 频率的计算卸载框架，并分别提出了两种基于半定松弛（semidefinite relaxation,SDR）算法作为固定和弹性CPU 频率情况下的解决方案.文献[20]研究了任务缓冲区稳定性约束下的功耗最小化问题，提出了一种基于李雅普诺夫优化的局部执行和计算卸载策略的在线算法.文献[21]研究了多信道无线干扰环境下的多用户计算卸载问题，提出了一种博弈论计算卸载算法作为解决方案，在能耗和计算执行时间方面都有较好的计算卸载性能.而在时间优化方面，文献[22]设计了网络资源和计算资源分配的优化算法，以最小化执行延迟，包括传输时间和计算时间.而在文献[23]中，实现了基于雾计算的IoV 系统中的车辆卸载实时交通管理，旨在最小化车辆计算任务执行的平均响应时间.然后，根据排队理论对基于车辆的雾节点进行建模，得出基于车辆的雾节点可以建模为M/M/1 队列的结论，并且基于此提出了一种求解卸载优化问题的近似方法.此外，文献[24]利用软件定义网络的思想，开发了一种基于迭代的算法来解决计算任务卸载和动态计算资源分配的问题.

虽然目前的相关研究使得车辆边缘计算环境下的计算迁移问题得到了一定的解决，但是当前的研究工作忽略了在进行计算迁移时车载任务的完成时间和边缘设备负载均衡的联合优化问题.因此，本文针对性提出了一种边缘计算环境下面向车联网的智能计算迁移方法，以实现车辆产生的计算迁移问题能够得到有效的解决，在实现车载任务时间能够得到保证的前提下，能够保证边缘设备的负载均衡状态需求.

1 系统模型

本节首先建立了车联网计算迁移模型，然后描述了车载任务在进行迁移后的服务时延模型以及对边缘设备的负载均衡模型，最后描述了本文算法在对车辆产生的车载任务进行计算迁移所期望实现的目标函数.模型中的关键字符如表1所示.

表1 关键字符及描述Table 1 Notations and description

1.1 车联网计算迁移框架

图1为边缘计算环境下面向车联网的计算迁移框架.在该框架中，边缘设备主要有N个宏基站和M个路边单元（roadside unit,RSU）组成，定义集合EN={en1,en2,···,enM}和RSU={rsu1,rsu2,···,rsuM}分别表示为宏基站和路边单元集合.相较于宏基站，在RSU 部署的计算资源规模较少，但所在地理位置距离车辆更近.此外，定义Veh={veh1,veh2,···,vehW}表示为W辆车的集合，且定义Ser={ser1,ser2,···,serW}为车辆vehi所产生的车载计算任务.车载计算任务的属性用三元组seri=(dsi,epti,pi)表示，其中dsi表示任务的规模，epti表示该任务的期望完成时间，pi表示该任务执行所需的处理器时间片数量.

图1 面向车联网边缘计算环境下的智能计算迁移框架Figure 1 Intelligent computing offloading framework for IoV in edge computing

1.2 服务时延模型

在图1所示的车载计算任务迁移过程中，车辆计算任务的主要需求是在期望时间epti内完成.假设在车载计算任务迁移过程中，车辆与边缘设备之间的通信链路保持稳定.此外，在实际的场景中，由于宏基站距离车辆更远，其所能接收的任务数量更多.因此，车载计算任务迁移到宏基站所经过的通信链路的信噪比要低于车载计算任务迁移到RSU 的通信链路信噪比.基于此，假设车辆与RSU 之间的信噪比为snre，车辆与宏基站的通信链路的信噪比为snrm.则车辆vehi产生计算迁移到RSU 过程中的单位带宽数据传输速率可以表示为

假定车辆vehi与RSU 之间的带宽为wvr，则车辆vehi与RSU 的通信时延可以表示为

类似地，车辆vehi的车载计算任务迁移到宏基站过程中的单位带宽数据传输速率可以表示为

假设车辆和宏基站之间的带宽为wvm，则车辆vehi与宏基站的通信时延可以表示为

车载计算任务迁移到边缘设备后所需的执行时间由边缘设备的计算能力所决定.在实际的场景中，宏基站所部署的计算资源规模虽然要大于RSU 所部署的计算资源，但两种情况下边缘设备的数据处理能力是一致的.因此，同一任务在宏基站和RSU 的执行时间的差距可以忽略不记.假定enj在单位时间片能够处理的数据规模为，则seri的处理时延表示为

由于任务处理完成后回传结果的数据量很小，因此在本文中将回传结果所产生的时延忽略不计.此外，由于车载计算任务的迁移的方式有RSU 和宏基站两种情况，则计算任务的服务时延可以表示为

为了评估车载计算任务迁移的有效性，本文通过计算车载计算任务实际服务时延和期望时延的差值来表示计算任务的完成效用值，表示为

1.3 边缘设备负载均衡模型

在进行计算迁移时需要考虑边缘设备的资源使用情况，使边缘设备的计算资源能被合理的使用的同时，也确保边缘设备处于负载均衡状态.目前，边缘计算资源提供商通常将服务器的物理实体虚拟为虚拟机，并以虚拟机的形式为用户提供计算服务.在本节中，为了得到整体的负载均衡状态，将宏基站和RSU 看作是部署不同数量虚拟机的边缘设备来讨论.假定边缘设备enj上部署了k个虚拟机.通过计算边缘设备上的虚拟机占用数量来计算边缘设备的负载均衡方差，并依据此来体现边缘设备的负载均衡状态.

假设执行seri所需的虚拟机数量为occi，则边缘设备的平均资源利用率可以表示为

式中，ωj(seri)判断seri是否运行在该边缘设备的虚拟机上，表示为

此外，表示边缘设备的平均资源使用率，表示为

基于以上分析，边缘设备的负载均衡方差表示为

1.4 目标函数

在对车载计算任务进行迁移的过程中，需要同时考虑任务处理的效用值和边缘设备的负载均衡状态.因此，本文在进行车载计算任务迁移过程中需要实现的优化目标具体表示为

其中，式(12)表示为车载计算任务迁移完成后能够使得任务执行的效用值最大的同时保证边缘设备整体的负载均衡方差最小.式(13)和(14)表示在进行计算迁移时，车载计算任务所需要的虚拟机数量不能超过当前边缘设备所部署虚拟机的数量.式(15)表示在计算迁移时需要保证每一个车载计算任务都能够在期望时间内完成.

2 本文方法

为解决车联网环境下的计算迁移问题，保证车载计算任务能够在期望时间内完成的同时，保证边缘设备处于负载均衡状态，本节首先将计算迁移问题构建为多目标优化问题，而后利用非支配排序遗传算法（non-dominant sorting genetic algorithm,NSGA-II）实现对任务执行时间和边缘设备负载均衡进行联合优化.

2.1 基于NSGA-II 的计算迁移

与传统的遗传算法相比，NSGA-II 对多目标问题的解决方法具有更加高效的全局搜索能力，并且对解决多目标的优化问题有更低的时间和空间复杂度.NSGA-II 迭代求解计算迁移策略的步骤如下：

步骤1编码（Encoding）

在使用遗传算法求解多目标问题时，求解的问题会被编码为染色体实现进化.而在本文中将车载计算任务的迁移策略编码为染色体，染色体中的基因型由计算迁移策略都对应计算迁移后车载计算任务的服务时延以及边缘设备的负载均衡状态构成.经过种群迭代得到的车载计算任务迁移策略被定义为OS={os1,os2,···,osp}，其中P是通过算法迭代所得到的车载计算任务迁移策略的数量.

步骤2交叉（Crossover）

在求解计算迁移问题的过程中，车载计算任务迁移策略的初始种群中的染色体通过两两相互配对后，按照多点交叉的方式交换部分基因形成两个新的个体，从而产生新的车载计算任务迁移策略.NSGA-II 在实现过程中需要按照设定的交叉概率进行两点交叉操作，以加快找到车载计算任务迁移策略的速度.

步骤3突变（Mutation）

与交叉操作功能类似，突变操作也是希望通过将个体染色体编码中的某些基因座上的基因值用该基因座上的其他等位基因来替换，从而为种群构建新的个体也即新的车载计算任务迁移策略，以此增加种群的多样性，同时也能够在一定程度上加速解的收敛速度.

步骤4选择（Selection）

为了使计算迁移策略能够保持优良的遗传基因，在对种群迭代过程中需要根据目标函数式(12)及约束函数(13)∼(15)选择当前种群中的个体.能够满足目标函数和约束的个体将会被保留以进行下一次种群迭代.通过选择来保证在求解计算迁移策略的迭代过程中解的性质朝着最优解的方向进化.

2.2 基于MCDM 和TOPSIS 的最优任务迁移策略获取

在种群迭代结束后，车载计算任务对应的迁移策略可能会包含多个，构成了计算任务的迁移策略解集，该解集中所包含的迁移策略是能够满足式(12)∼(14)的.因此，ICOM 需要在该解集中找出一个最优解作为车载计算任务的迁移策略.而为在解集中找出最优的迁移策略，ICOM 借助多目标决策准则（multi-criteria decision making,MCDM）和逼近理想解排序法（technique for order preference by similarity to an ideal solution,TOPSIS）来获取最优解，在选择过程中通过判别评价个体的最优解和最坏解之间的距离来确定排序.若评价个体最接近最优解，离最差解最远，则评价个体为最优解；否则，认为评价个体是最差的.

假定NSGA-II 最终迭代得到的车载计算任务的P个迁移策略集合为OS，每一个迁移策略对应的车载计算任务完成效用值和负载均衡方差值分别表示为β={β1,β2,···,βp}和LD={ld1,ld2,···,ldp}，则策略osi与正理想解的欧氏距离表示为

类似地，策略osi与负理想解的距离可以表示为

由此可以得到osi与正理想解的相对接近度C.而相对接近度的值越大，则表明该策略的总体在车载计算任务完成效用值和负载均衡方差值得联合优化表现会更好，相对接近度表示为

算法ICOM 的求解过程如算法1 所示，ICOM 的整体复杂度主要取决于NSGA-II 中的快速非支配排序和拥挤度计算两部分.假设求解问题的目标数量为Q，种群的规模为N，则快速非支配排序在迭代过程中的时间复杂度为O(QN2).相比于传统的支配排序算法O(QN3)的时间复杂度，NSGA-II 的时间复杂度得到了有效降低.此外，在拥挤度计算的时间复杂度为O(2NlbN).

算法1ICOM 求解过程

输入：车载计算任务seri

输出：seri的最优迁移策略

3 实验评估

3.1 实验环境

本文的仿真实验是在搭载Intel Core i5-9500 处理器和8GB 内存，操作系统为Windows10 的电脑上进行的.实验的其他参数配置见表2所示.

表2 参数配置Table 2 Parameter configuration

3.2 对比方法

在实验过程中，选择Benchmark 和FFD-EP[2]作为对比方法进行对比，两种方法的基本实现思路如下：

1）Benchmark.该计算迁移策略的核心思想是随机为车载计算任务选择迁移策略，当计算节点不能满足车载计算任务的计算需求时会重新为车载计算任务分配计算迁移策略.

2）FFD-EP.在对车载计算任务进行迁移的过程中，首先将当前宏基站和路边单元所剩余的计算资源数按从小到大的排序，随后在序列里面查找能够满足车载计算任务的迁移位置.该方法在执行过程中第一次找到的能够满足车载计算任务的策略就作为该任务的迁移位置.

3.3 车载计算任务完成效用值对比

车载计算任务完成效用值是评价车载计算任务完成的服务质量的重要指标.具体来说，车载计算任务如果能在期望时间内完成，效用值作为期望时间与时间完成时间的差值为正值.所以本文中期望任务的效用值为正且越大越好，当任务数量分别为50、100、150 和200 时，所有车载计算任务的效用值被看作一个整体，体现的也就是所有任务整体的效用值.效用值越大，说明车载计算任务进行的计算迁移使更多的任务在期望时间内完成.如图2所示，在不同车载计算任务数量下，ICOM 所得到的车载计算任务迁移策略能够使得车载计算任务的完成效用值均高于Benchmark 和FFD-EP.

图2 车载计算任务完成效用值对比Figure 2 Comparison of computing task completion utility

3.4 边缘设备平均资源使用率对比

图3 边缘设备平均资源使用率对比Figure 3 Comparison of resource utilization of edge devices

在进行车载计算任务迁移时，需要保证边缘设备的资源得到有效利用.在本文中，边缘设备的资源使用率的值越大，则表明边缘设备的资源被利用得更加充分.如图3所示，在车载计算任务数量较少时，车载计算任务所需要的计算资源不会很多，导致边缘设备的资源使用率较低.但随着车载计算任务的不断增多，对计算资源的需求也在不断增加，从而导致边缘设备的资源使用率处于总体上升的状态.相比于Benchmark 和FFD-EP，ICOM 在对不同数量的任务进行迁移后，边缘设备的资源使用率表现更好.

3.5 边缘设备负载均衡对比

负载均衡作为计算任务迁移策略的一个重要评价指标：一方面，当部署的边缘设备的计算资源总体保持负载均衡时能够保证计算资源得到最大限度的利用；另一方面，当边缘设备总体的负载保持均衡状态时，能够保证各边缘设备都能够处于稳定的工作状态，降低边缘设备由于过载而出现宕机的概率.在本文中，负载平衡方差的值越小则表示各边缘设备负载均衡状态越好.如图4所示，随着车辆产生的计算任务数量的不断增加，在经Benchmark、FFDEP 和ICOM 对车载计算任务分配迁移策略之后，边缘设备的负载均衡方差值也在随之增长，主要是由于任务数量的增加，导致边缘设备中更多的计算资源被占用.与Benchmark 和FFDEP 相比，ICOM 在求解时将边缘设备的总体负载均衡状态作为一个指标而不断迭代，而其他两种方法在求解过程中并未考虑边缘设备的总体的负载均衡状态，只是尽可能将计算任务迁移到有效的边缘设备上.因此，ICOM 所求解的迁移策略使得边缘设备的负载均衡方差值更小.

图4 边缘设备负载均衡方差对比Figure 4 Comparison of load balance variance of edge devices

3.6 车载计算任务迁移成功率对比

车载计算任务效用值评估是对所有任务进行的整体评价.为了进一步展示ICOM 的性能，本文用车载计算任务的迁移成功率来体现计算任务迁移策略的有效性.如表2所示，随着任务数量的不断增加，车载计算任务迁移成功率由于计算资源的不断被消耗而导致Benchmark 和FFD-EP 得到的迁移策略无效，导致车载计算任务不能够在期望时间内完成.相比这两种对比方法，ICOM 在求解计算迁移问题时将车载计算任务的期望完成时间作为车载计算任务一个约束条件来进行迭代，使每一个车载计算任务都能够在期望时间内完成.

3.7 边缘设备占用数量对比

如图5所示，随着任务数量的不断增加，Benchmark、FFD-EP 和ICOM 对不同数量的车载计算任务进行计算迁移时，所占用的边缘设备的数量也在不断增加.相比于Benchmark 和FFD-EP，ICOM 在对不同数量车载计算任务进行迁移的过程中所占用的边缘设备数量是最少的，结合上述边缘设备的平均资源利用率来看，ICOM 能够保证边缘设备的资源使用率最大的同时也能够降低边缘设备的占用数量，避免过多边缘设备资源的不合理使用.

表3 车载计算任务迁移成功率对比Table 3 Comparison of the success rate of task offloading %

图5 边缘设备占用数量对比Figure 5 Comparison of the number of edge devices occupied

3.8 车载计算任务迁移算法求解时间消耗对比

如表4所示，随着任务数量的不断增加，Benchmark、FFD-EP 和ICOM 对不同数量的车载计算任务进行计算迁移时，不同算法的求解时间也在不断增加.总体上看，相比于Benchmark 和FFD-EP，ICOM 在对不同数量车载计算任务进行迁移的过程中所产生的时间消耗相对较少.

表4 车载计算任务迁移算法求解时间消耗对比Table 4 Comparison of the time consumption for task offloading with different algorithms s

4 结 语

本文为了保证车辆产生的计算任务在期望的时间内得到解决，提出了一种智能计算迁移算法ICOM.该方法能够对车辆所产生的车载计算任务进行有效迁移，保证车载计算任务能够在期望的时间内完成，提升车载用户的服务体验.与此同时，在对车载计算任务进行迁移的过程中能够有效保证边缘设备的负载均衡状态.大量的实验证明了ICOM 的有效性.在未来的工作中，期望能够在此基础上考虑车载计算任务的数据隐私问题，以保护车载用户的隐私.