基于模拟退火机制的车辆用户移动边缘计算任务卸载新方法

张德干 李 霞* 张 捷 张 婷 龚倡乐

①(天津理工大学天津市智能计算及软件新技术重点实验室 天津 300384)

②(天津体育学院体育经济与管理学院 天津 301617)

③(北京交通大学电子信息工程学院 北京 100044)

1 引言

随着物联网的普及以及物联网技术的不断升级，智能交通的建设也被广为关注，从而衍生出了以车辆自组织网络(Vehicular Ad hoc NETworks,VANET)为代表的移动物联网[1,2]。车联网(Internet Of Vehicles,IOV)主要指的是车载设备通过无线通信的技术，对于所能获得到的所有车辆动态信息进行有效利用，从而在车辆移动的过程中提供各种不同的服务[3]。车联网的特征主要体现在了：能够在车与车之间提供有效的距离保障，帮助用户进行实时导航，通过与其他车辆的实时通信来提高交通运行的效率，以及降低车辆发生碰撞事故的概率[4-6]。

考虑到车联网中对于信息处理的实时性的要求，如果将所有的信息处理都放在云平台去执行，无法满足低延迟以及高质量的服务要求[7-9]。移动边缘计算(Mobile Edge Computing, MEC)技术的出现将云计算和服务扩展到了网络边缘，由于靠近设备本身，保证了信息处理的实时性，提高了数据传输的性能[10-13]。通过采用MEC技术，可以部署边缘服务器等轻量级的基础设施，将云平台的计算任务放在边缘服务器上执行，从而减轻云平台的任务执行压力，给用户带来更高质量的服务。但是如果所有用户将其任务都进行卸载，也会给MEC服务器的计算能力带来很大的压力。任务卸载决策成为实现高效计算卸载关键性问题[14,15]。

在任务卸载策略中，时耗以及能耗是需要着重考虑的两个方面。Oueis等人[16]提出了一种用于小型蜂窝云计算的负载分配方法，但是在多用户场景下的时间消耗上未做过多考虑。通过综合考虑资源的分配以及计算方式，Wei等人[17]提出了贪婪策略的任务卸载算法，但该算法在节约能量的同时容易导致服务器任务堆积而增大时耗。Tran等人[18]分析出任务卸载的目标问题是混合整数非线性规划问题(Mixed Integer Nonlinear Layout Problems, MINLP)，将每个用户的卸载方式从任务完成时间以及设备能耗两方面进行考虑，但是并未与车联网环境下的计算任务特殊性相结合。Kao等人[19]考虑到移动边缘计算当中资源的有限性，结合在线学习的方法来减小任务时延方面的问题，但是在与移动边缘计算技术相结合上需要更进一步对时耗和能耗进行平衡。

本文提出基于模拟退火机制的车辆用户移动边缘计算任务卸载新方法，主要工作如下：(1)通过定义用户的任务计算卸载效用，综合考虑时耗和能耗；(2)结合模拟退火机制，根据当前道路的密集程度对系统卸载效用进行优化，改变用户的卸载决策，选择在本地执行或者卸载到边缘服务器上执行。仿真结果表明，本算法在给定的环境下使所有用户都能得到满足低时延高质量的服务。在减少用户任务计算时间的同时降低了能量消耗。

2 基本原理

2.1 场景模型

如图1所示，场景设置在车辆密集的十字路口，在十字路口有多个路边设备(RoadSide Units, RSU)，并且都配置有MEC服务器，将其看作一个服务器群。周围的车辆(Vehicle)就是移动的用户，用户可以与服务器群中的任意一个进行通信并将任务资源卸载到服务器上。因此，可以将用户以及服务器群进行如下定义：V=(1,2,...,v)，M=(1,2,...,m)，由于将RSU与MEC进行了一一对应，所以均可以用m∈M进行代替。

图1 场景模型

2.2 用户计算任务

2.3 本地执行任务

定义1 本地任务执行时间。

每个计算任务既可以在本地(Local)执行，也可以卸载到边缘服务器上，虽然将任务卸载到边缘服务器会减轻本地计算的消耗，但是相应地，在上传相应任务的时候，会增加耗时以及部分上传的能量消耗。将所有车辆用户的类型进行统一化，用户在本地执行计算的能力是相同的，可以定义为lv[cycles/s]，结合每个任务所需要的计算资源，可以得到，用户v如果在本地执行计算任务Tv，需要的时间如式(1)所示

2.4 任务卸载到边缘服务器

如果将任务上传到服务器，会增加任务时间消耗，主要可以将时间分作传输时间以及在服务器上执行的时间，同时计算任务的执行也会产生能量的消耗。

定义3 任务传输时间。

在车联网中，主要采用了短程通信技术，提供车辆以及基础设备之间的双向短程通信[22]。在专用短程通信技术(Dedicated Short Range Communications, DSRC)体系结构中，每辆车上备有车载设备(On-Board Unit, OBU)，相当于移动终端设备，具有一定的数据处理能力，同时，在马路上还部署了相应的路边单元RSU，为车辆提供数据访问服务[9,23]。

DSRC的底层技术主要是采用了正交频分复用(Orthogonal Frequency Division Multiplexing,OFDM)的技术[24,25]。如果只使用1个信道来传输信号将造成资源浪费的情况，因此OFDM将信道划分成了若干个正交的子信道用于传输。另外，正交频分多址(Orthogonal Frequency Division Multiple Access, OFDMA)技术如图2所示，作为OFDM的演进，利用OFDM对信道进行子载波化后，在部分子载波上加载传输数据，从而用户可以选择信道条件较好的子通道来进行数据传输，可以保证各个子载波都被对应信道较优的用户使用，获得了频率上的分集增益。

图2 OFDM与OFDMA工作模式对比

假设将带宽B划分成N个相同的子频带，则每个大小为，W=B/N(Hz)，在车联网通信网络的物理层中，结合OFDM技术，划分出了7个10 MHz的子信道用于传输，因此可以看作每个服务器有7条子信道。

综上所述，当用户选择将计算任务卸载到边缘服务器执行时，将消耗的总时间为

3 用户任务卸载效用

结合之前的规定，可以得到如下的约束：

(1)车辆用户在任务执行方式的选择上，可以考虑在本地执行或者是传输到边缘服务器上；

(2)同一个边缘服务器可以同时处理多个用户的计算任务；

(3)在范围内可以选择某个边缘服务器的任一子频带进行数据的传输；

(4)如果用户选择将计算任务卸载到某服务器，但是当前服务器因为负载过多导致用户卸载效用过低时，则不执行任务卸载。

对式(13)进行扩展后，可以做出如式(14)的公式

4 算法描述

4.1 模拟退火机制的相关定义

模拟退火是一种启发式的算法，同时也是一种贪心算法，不同的是，在搜索的过程中，由于引入了随机因素，因此在迭代更新可行解时，会有一定的概率去接受一个比当前值要差的元素，因此模拟退火算法是可以跳出局部最优解，从而求得全局最优解[26]。在本文做出如下定义：

定义6 初始温度T0，模拟退火算法开始的温度，在本文将用户车辆的数量看作初始温度，即

T0=V。

定义7 降温系数α，根据文献，采用指数式的下降方式，因此有T(n+1)=αT(n) ，α为降温系数，取值为0.8～0.99[27]。

定义8 终止温度，如果在若干次迭代的情况下没有可以更新的状态，或者达到了设定的终止温度，则认为退火完成。

定义9 降温概率，假设当前状态为f(n)，在下一时刻状态变为f(n+1)， 则定义系统由f(n)变为f(n+1)的概率为

4.2 初始卸载策略

在满足定义的卸载约束条件的情况下，根据式(12)选择满足自身卸载效用最大的方式执行任务，以此来得到初始卸载策略，即初始温度。变量符号及含义见表1。初始卸载策略算法如表2所示。

表1 变量符号及含义

表2 生成初始温度(算法1)

4.3 状态转换机制

状态转换就是在满足设定的约束的条件下，用户选择计算任务执行方式的集合，通过随机概率，改变用户的计算任务执行方式，即是否执行卸载以及选择卸载的子频带，来建立新的卸载策略。

4.4 基于模拟退火机制的边缘计算任务卸载算法

综上所述，本节所提基于模拟退火机制的边缘计算任务卸载算法(Task Offloading algorithm with MEC based on Simulated Annealing,TOSA)的执行步骤如下：

(1)根据边缘服务器的通信范围，得到处于通信范围内的车辆用户数量，得到初始温度；

(2)根据式(12)，结合定义的用户卸载约束，通过算法1构建用户卸载的初始策略，并根据式(15)计算出初始的系统卸载效用；

(3)若没有达到设定的终止温度，在规定的迭代次数范围内，通过表3所示的算法2，获得新的卸载策略，再根据式(15)计算出新的系统卸载效用；

表3 状态转换(算法2)

(4)通过对比本次及上次系统卸载效用的值，如果大于上次系统卸载效用，则接受此次卸载策略，并更新函数的当前解，否则根据式(16)得到降温概率p，并产生一个均匀分布的随机数，如果p大于随机数，则接受卸载策略，否则放弃此次卸载策略；

(5)根据降温系数，调整当前温度，重复执行步骤(2)-步骤(4)；

(6)当达到终止温度或者规定的迭代次数，终止退火，此时得到的用户卸载效用即是函数的最优解。边缘计算卸载算法如表4所示。

表4 基于模拟退火机制的边缘计算任务卸载算法(算法3)

5 算法测试仿真与分析

5.1 测试仿真环境设置

本实验使用了MATLAB平台，对本文设置的算法TOSA进行测试。通过对比在不同时间段(即不同车流量环境)，不同数量的服务器以及不同大小的计算任务3个方面进行考虑，并与其他任务卸载方法进行对比，实验证明，TOSA算法在时耗和能耗方面都有一定的提升。环境变量设置如表5所示。

表5 仿真参数

5.2 实验结果与分析

图3和图4为在用户对于时耗和能耗的选择偏好不同情况下(即权重λ1,λ2的选择)将计算任务卸载到MEC服务器上执行的情况。根据图3可以得出，随着用户对于时耗偏好的增加，平均每个用户在执行计算任务时所消耗的时间均有所下降，并且车流量越大，计算时间下降得越明显。这是因为在低车流量的场景下，MEC服务器的工作负载并不大，因此用户将计算任务卸载到MEC服务器上执行时不会产生过大的拥塞，因此每个用户的任务计算执行时间改善并不明显。但是随着车流量的增大，如果所有用户都将任务卸载到MEC服务器上去执行，同样会给边缘服务器带来巨大的负载，而且会导致计算任务的阻塞，增加任务计算时间。在用户执行计算任务时如果更加偏向于选择更短的时耗的情况下，TOSA算法会调整用户卸载效用的计算权值，改变部分用户的卸载决策，因此优化了用户的任务计算时间。从图3可知，在高车流量场景下，当用户对于时间的偏好到达最大值时，平均每个用户的任务计算时间下降了72%。

图3 不同时耗偏好下任务计算时间

图4是时耗偏好值不同情况下用户能效消耗示意图，可以看出随着用户对于时间偏好的增加，用户的任务执行能耗均增加了，在车流量较大的环境下，用户能量消耗增大得越明显。这是因为在低车流量的场景下，大部分用户都选择将计算任务卸载到MEC服务器上去执行，并不会产生较大的任务执行能耗，而只有传输的能耗。另外，当用户的时耗偏好值加大，TOSA会更加关注任务计算的时间，即减小能耗的权值，因此在任务卸载的决策上会选择时耗更小的方案，如将任务放在本地执行，导致任务执行的能耗会加大。在车流量较大的情况下，MEC服务器有较大的负载，所以为了降低时耗，将有更多任务在本地执行，因此能量消耗增加更明显。

图4 不同时耗偏好下任务能量消耗

图5、图6以及图7是在不用数量的MEC服务器情况下，用户通过TOSA、贪婪算法任务卸载(Select Maximum Saved Energy First, SMSEF)以及使用局部搜索算法优化任务卸载(Local Search Optimization algorithm, LSO)将计算任务进行卸载的时耗、能耗以及用户卸载效用的对比图。

图5是在两种车流量环境下，不同MEC服务器数量的用户执行计算任务的能耗示意图，由图可知，因为SMSEF主要从用户的计算任务能量消耗上进行了优化，会尽可能地选择将任务卸载到MEC服务器上，因此用户自身的能量消耗并不大。但是本文所提出的TOSA算法以及LSO算法综合考虑了计算任务执行的时耗以及能耗两个方面，因此能量消耗相对较高，在车流量较大的环境下，TOSA,LSO以及SMSEF算法的用户能量消耗均有明显增大。另外，随着MEC服务器数量的增加，3种算法在能量消耗上都有所降低。在MEC服务器数量达到最大值时，TOSA算法相比于LSO算法能耗降低了45%。

图5 不同MEC服务器数量下能耗对比图

图6是在两种车流量环境下任务计算时间对比图，从中可以看出，随着MEC服务器数量的增加，有更多的计算任务可以卸载到MEC服务器上执行，因此时耗均有所降低。其中SMSEF算法从用户能耗方面考虑会尽可能将任务卸载到MEC服务器上执行，因此当服务器数量不多的时候会带来任务阻塞，导致任务计算时间加长，其中在车流量较大的环境下表现更为明显，本文提出的TOSA算法随着MEC服务器数量的增加，任务计算时间总体下降24%，比SMSEF算法低约55%，比LSO算法低约33%。

图6 不同MEC服务器数量下时耗对比图

结合时耗和能耗两方面，图7展示了3种算法的计算任务卸载效用。由图可以看出，当MEC数量较少时，低车流量环境下SMSEF算法由于只考虑了能量的消耗，所以任务卸载效用远低于TOSA算法和LSO算法，高车流量环境下，SMSEF算法因为只考虑了能量消耗而忽略的时间消耗，根据式(12)-式(15)可以得到在这种情况下任务卸载效用小于0，即并不适合进行任务卸载。随着MEC服务器数量的增加，3种算法的任务卸载效用均有所提高，其中本文所提出的TOSA算法综合考虑了时耗和能耗两方面，因此在任务卸载效用上表现优于其他两种算法，在车流量较大的环境下表现更加明显。在服务器数量达到最大时，任务卸载效用比LSO算法高40%，比SMSEF算法高29%。

图7 不同MEC服务器数量下用户任务卸载效用对比图

图8、图9、图10是在不同车流量的情况下，3种算法对两个大小的计算任务的卸载决策比较，且认为用户在时耗与能耗的偏好值是相同的，即λ1=λ2=1/2。从图8可以看出，在MEC服务器数量固定的情况下，随着车流量和计算任务大小的增大，3种算法在任务计算时间上均增大，当计算任务大小增加时，SMSEF算法的任务计算时间明显加剧。这是因为SMSEF将大量任务卸载到MEC服务器上执行，造成了计算任务的时耗加大。在达到最大车流量时，TOSA算法的时耗比LSO算法低7.8%，比SMSEF算法低60%。

图8 不同车流量下时耗对比图

图9展示了车流量对于用户能量消耗的影响。用户的能量消耗随着车流量的增加而增加，在均匀考虑时耗和能耗偏好值的情况下，TOSA算法会将用户的计算任务选择在本地执行，因此加大了用户的能量消耗。但是在最大车流量时，TOSA算法的能量消耗比LSO算法低21%。

图9 不同车流量下能耗对比图

综合任务计算时间以及用户能量消耗，图10展示了车流量对于用户卸载效用的影响。在仿真实验中，3种算法的用户卸载效用随着车流量环境的改变均有所增大，但是面对较大计算任务时用户卸载效用略微低于小型计算任务，这也说明了MEC服务器主要适用于处理计算量不大的任务。当使用SMSEF算法处理较大计算量任务时，根据图8所示任务计算时间过大，因此综合对比下任务卸载效用小于0不适合进行任务卸载，相比之下，其中TOSA算法的卸载效用表现最佳。当处于中等车流量的环境时，LSO算法的卸载效用相比于TOSA算法和SMSEF算法表现欠佳，但是当车流量继续增加时，SMSEF算法的用户卸载效用明显下降约68%，LSO算法的用户卸载效用下降约22%，TOSA算法的用户卸载效用相对稳定。图11描述了1 d时间长度内车流量统计图。

图10 不同车流量下用户卸载效用对比图

图11 1 d时间长度内车流量统计图

图12和图13是根据1 d时间长度内车流量统计图，结合对车辆用户的时耗和能耗偏好值，选取λ1=0.3 ，λ2=0.7 (更偏向于能耗)和λ1=0.7 ，λ2=0.3(更偏向于时耗)进行对比得到的3种算法1 d内任务计算时间及任务能量消耗对比图。

图12是在1 d时间长度内3种算法在不同偏好值情况下任务计算时间示意图。由此可知，随着1 d内车流量的变化，任务计算时间处于先升后降的趋势，其中SMSEF算法没有考虑时间消耗的问题，所以总体高于其他两种算法，且不稳定变化较大。另外，本文提出的TOSA算法在1 d时间内的任务计算时间均优于LSO算法，在卸载决策偏向于时耗的情况下(λ1=0.7)，TOSA算法的平均任务计算时间比LSO算法低约12%。

图12 1 d时间长度内任务计算时间对比图

图13是在不同偏好值情况下，1 d时间长度内3种算法的用户能量消耗示意图。可以看出TOSA以及LSO算法在高车流量的时间段能量消耗更高，这是因为车流量较大时，部分计算任务会直接在本地执行，因此增加了能量的消耗，当决策偏向于能耗时(λ1=0.3)能量消耗有所下降，TOSA算法的平均用户能量消耗比LSO算法低约42%。

6 结束语

本文提出一种基于模拟退火机制的车辆用户移动边缘计算任务卸载新方法，在车流量密集的十字路口环境下，通过定义用户卸载效用，综合考虑用户在执行计算任务时的能耗以及时耗两个方面，并利用模拟退火算法对用户卸载效用进行优化，得到不同时间段，即不同车流量环境且符合用户偏好的任务卸载决策。实验证明TOSA算法可以有效的优化用户的任务卸载决策，改善任务的能量消耗以及计算时间。