车联网场景下的移动边缘计算卸载策略

余 翔,刘一勋,石雪琴,王 政

(重庆邮电大学 通信与信息工程学院,重庆 400065)

0 概述

作为移动边缘计算(Mobile Edge Computing,MEC)的典型服务场景[1],车联网(Internet of Vehicles,IoV)为智能交通系统中的车载终端、路侧单元以及行人提供无线通信服务,实现车对车(V2V)、车对基础设施(V2I)、车对行人(V2P)以及车对网络(V2N)的通信[2]。

与传统移动通信中的计算任务不同,在车联网场景中,车载终端会在短时间内生成大量合作感知信息[3]与分布式环境通知消息[4]来合作完成保障道路安全与提高交通效率的车联网安全型业务。由于车载终端的计算任务涉及人身安全,因此对时延有严格的要求,与传统的通信业务相比,其计算任务数量激增且处理优先级更高。

在传统云车系统中,移动云计算虽然极大地提高了资源利用率和计算性能,但由于回程和骨干网络上的传输容量限制以及延迟波动,远离移动车辆的云服务可能使卸载效率大幅降低。配置MEC服务器的车联网架构被认为是一种有效缩短V2I、V2N应用时延的方案[5-6]。此类方案将连接的汽车云扩展到分散的移动基站环境中,使数据和应用能够靠近车辆,实现车载计算任务的实时化处理,减少业务的时延。

计算卸载作为MEC的关键技术之一[7],是MEC系统实现终端业务实时化处理的重要手段[8-9]。实验证明,将任务卸载到MEC上,最多可减少88%的时延[10]。文献[11]在MEC车联网场景下考虑任务执行时延、车辆移动时延以及数据传输时延,设计基于任务时延的效用函数来平衡负载和表现时延满意度,进而提出一种低复杂度的算法用于解决该整数非线性规划问题。文献[12]提出加入MEC服务器减少C-V2X中端到端信令时延的方法。文献[13]设计基于MEC的卸载架构,考虑MEC服务器的资源限制和计算任务的时延容忍,通过引入契约理论设计有效的计算卸载策略,最大限度地提高了MEC服务提供商的利益,增强了车辆的效用。文献[14]研究了车辆边缘网络中的多车辆计算卸载问题,提出一种基于博弈论的车载边缘网络离线算法,其考虑每辆车的卸载策略以求最小化系统总开销。文献[15]研究5G环境中车辆的计算任务卸载问题,从计算任务和通信两个方面对5G网络车辆计算卸载的能量消耗进行建模,并利用人工鱼群算法解决计算卸载能耗最小化问题,但其在边缘车辆网络的计算卸载过程中,未考虑车辆同时并发多个具有不同优先级计算任务的情况。

本文针对MEC车联网计算卸载系统,在MEC服务器计算资源负载不均的限制条件下,提出基于遗传算法的卸载策略。通过对计算任务进行编码,利用遗传算法寻找最优卸载策略,将计算任务卸载至合适的MEC服务器,在保障车载安全型业务优先处理的同时,减小MEC服务器计算资源负载不均对任务完成率的影响。

1 系统模型

本文系统模型如图1所示。假设J个配置MEC服务器的RSU在道路上均匀分布,将MEC服务器记为mecj,j∈{1,2,…,J},C台随机分布的车辆各自携多个计算任务,设共携带N个计算任务,表示为Ltask={b,w,ω,tmax,RL},其中,b表示输入数据的大小,w表示任务计算量,ω是一个可变的参数,表示该计算任务的重要程度,以区分该任务为传统计算任务或车载安全型计算任务,tmax表示任务截止时限,任务处理时延超出时限则表示任务处理失败,RL表示任务所属车载终端所在的MEC服务小区。

图1 MEC车联网系统模型Fig.1 System model of MEC Internet of vehicles

用x表示车载终端将计算任务卸载至MEC服务器的编号,x={0,1,…,J},1～J表示卸载至MEC服务器的编号,x=0表示任务由车载终端处理完成。N个计算任务的卸载策略构成卸载策略向量集X={x1,x2,…,xN}。

1.1 通信模型

车辆移动与通信模型可参考文献[16],车辆与RSU之间的通信是通过LTE-V2I直连的无线链路进行的[17],车辆到RSU的上传链路设定为频率平坦型快衰落的瑞利信道[18]。根据香农公式可以计算出上传链路的数据传输速率为:

(1)

场景中车辆以恒定单方向的速度行驶,车辆Ci的速度用vi表示,车辆的移动性使其与RSU覆盖范围中心之间的距离dl随时间变化,变化规律可用下式表示:

(2)

其中,e表示车辆行驶水平线与RSU的距离,s表示RSU的覆盖范围。

(3)

1.2 计算模型

计算任务的处理分为数据传输和数据计算两部分,若任务i进行本地计算,则仅考虑其计算时延而不考虑传输时延。本地任务处理时延的计算公式为:

(4)

其中,eloc表示车载终端的计算能力。对于需要进行卸载的任务,有本地服务器卸载与其他服务器卸载2种情况。

1.2.1 本地服务器卸载

(5)

(6)

(7)

1.2.2 其他服务器卸载

由于当前所在范围MEC服务器的负载较重,车载终端决定将计算任务卸载至其他MEC服务器。MEC服务器之间往往通过光纤等有线链路进行相连。假设在有线链路l上的计算任务平均传输等待时延为tw,则此时任务处理时延的计算公式为:

(8)

其中,a表示计算任务卸载至其他范围MEC服务器的有线链路跳数。

1.2.3 计算资源分配

为保证任务在规定时限内完成且任务不中断,要求计算任务在车辆离开所属MEC小区前完成任务。因此,本地服务器卸载的情况应满足式(9),其他服务器卸载的情况应满足式(10):

(9)

(10)

由此可推导出2种情况下完成计算任务所需计算资源分别为:

(11)

(12)

对所有卸载至mecj服务器的计算任务,申请的总计算资源为:

(13)

本文研究目的是对优先级较高的计算任务优先处理,同时提升全计算任务的完成数量。因此,定义系统效用函数如下:

(14)

其中,α表示计算任务总权重值。

最终计算模型建模为:

max(P)

s.t.

C3:ej

(15)

在式(15)中:约束条件C1表示一个计算任务只能卸载至某一个MEC服务器,不能同时卸载至两个服务器;C2表示计算任务采取二元卸载,只能将整个计算任务卸载至MEC服务器,或者不进行卸载;约束条件C3表示卸载至MEC服务器的计算任务所消耗的计算资源不能超过MEC总的计算资源。

2 基于遗传算法的任务卸载策略

2.1 问题描述

本文将优化问题转化为背包问题,并采用遗传算法[19]来进行求解以满足计算卸载需求。不同的MEC服务器具有不同的计算能力,当计算资源不够的MEC服务器承接大量的计算任务时,不仅无法保障计算任务的完成,而且会导致MEC服务器负载过重影响其他业务的处理。同时随机地对计算任务进行卸载,又会导致在寻找最优计算卸载策略时迭代次数冗长。因此,本文采用基于遗传算法的任务卸载策略(Genetic Algorithm-based Offloading Strategy,GAOS)预留合适的初始染色体,结合贪婪算法寻找每个MEC服务器的最优卸载策略,加速迭代过程。

2.2 编码

本文采用二进制编码,每条染色体的编码为一种卸载策略X,用X(m)表示策略X中m位的取值,X(m)取0或1。为了表示所有计算任务能卸载至所有服务器,编码位数M应满足以下条件:

M≥lbJ

(16)

以[XiMXiM+1XiM+2…X(i+1)M]表示计算任务i的卸载结果,其卸载的MEC服务器编号xi为:

(17)

不超出8个MEC服务器的计算任务策略编码过程如图2所示。

图2 策略编码与MEC服务器的映射Fig.2 Mapping of policy coding to MEC servers

2.3 初始化

初始化遗传算法的相关参数,包括最大的迭代次数I、染色体长度N×M、变异概率pm、交叉概率pc、种群大小ps以及预留种群r。多数遗传算法是随机选择初始种群,GAOS策略则结合了预定义染色体和随机染色体算法进行种群初始化。在预定义染色体过程中,将染色体中权重最高类,即车载安全类的计算任务(ω=ω1)编码设置如下:

(18)

预定义染色体编码算法描述如下:

输入N,ps,Ri,ω1

输出X

for k=1 to ps

for i=1 to N

if xi=Riand ωi=ω1then

else

end for

若共Nc个计算任务被预定义,则剩余(N-Nc)个计算任务的编码随机生成,剩余(r-ps)个种群的染色体编码随机生成,维持种群的随机性。

2.4 解集修复

由式(9)～式(12)可知,当分配给计算任务的计算资源恰好满足时限,则2种情况下消耗的计算资源最小,分别为:

(19)

(20)

本文通过贪婪算法修复解集,对超出服务器j计算资源中的计算任务计算其价值密度dij,如式(21)所示:

(21)

以Nj表示卸载到服务器j的任务编号,找到最小价值密度的计算任务并将其从MEC服务器队列移除,再重新计算消耗的计算资源,重复该步骤,直至所有计算任务消耗的计算资源不超过MEC服务器总的计算资源。解集修复算法描述如下:

输入ps,J,ej,Ej,Nj,dij

输出X

for k=1 to ps

for j=1 to J

if ej>Ejthen

for i=1 to Nj

if dij=min(dij) then

ej=ej-emin(dij)

until ej≤Ej

end for

end if

end for

2.5 适应度函数构造

适应度函数的构造是解决本文优化问题的关键,其目标函数如式(15)所示。因此,给出适应度函数的计算公式为:

(22)

2.6 选择操作

根据选择概率选择染色体,将上述个体作为第一代,采用正比于适应度的轮盘赌随机选择方式,设个体的适应度为fi,则i被选中的概率为:

(23)

对于初始化后的种群,计算每条染色体的适应度值及其被选择的概率进行比较,剔除概率最低的染色体,选择概率最大的染色体进行复制,代替被剔除掉的染色体。

2.7 交叉操作

本文采用一点交叉方式,交叉概率为Pc,具体操作是在个体串中随机设定一个交叉点,实行交叉时,该点前或后两个个体的部分结构进行互换,并生成两个新个体。

2.8 变异操作

对于本文优化问题,变异操作就是将染色体的变异位1变为0,0变为1,其他位都保持不变,变异概率为Pc。因此,选择一个变异位进行变异,再计算其适应度是否大于或等于其原来的适应度,若不是则重新选择变异位进行变异。

3 仿真结果分析

本节通过仿真结果来验证GAOS策略的性能。模拟一个拥有3个MEC服务器的车联网计算卸载系统,采用与文献[20]相同的比较方式,将GAOS与以下卸载方案进行比较:

1)ALL-Local策略:所有计算任务放在本地执行。

2)Random策略:所有计算任务随机卸载至MEC服务器,根据卸载车载终端数平均分配计算资源。

3)ALL-MEC策略:所有车载终端进行任务卸载,MEC服务器根据剩余计算资源对计算任务平均分配计算资源。

仿真参数如表1所示,车载安全型计算任务参数如表2所示。

表1 仿真参数Table 1 Simulation parameters

表2 车载安全型计算任务参数Table 2 Parameters of safety on-board computing task

首先验证GAOS策略的迭代次数对任务完成率的影响,任务完成率表示为成功计算的计算任务占总计算任务的比例。本文通过多次重复实验,研究不同车载终端数C下迭代次数对任务完成率的影响。由图3可以看出,GAOS策略均可在有效次迭代后达到平稳。

图3 迭代次数对任务完成率的影响Fig.3 Influence of iterations number on task completion rate

本文通过重复实验,研究用户在不同卸载方案下车载安全型计算任务(ω=ω1)的成功处理比例。由图4可以看出,为取得最大系统效用函数值,GAOS策略在卸载过程中,将更多优先级高的任务卸载至MEC服务器。与未对优先级任务做处理的Random策略以及ALL-MEC策略相比,分别提高了约30%和50%的车载安全型计算任务成功处理数量。

图4 不同卸载方案下车载安全型计算任务完成数量Fig.4 Number of completed safety on-board computing tasks of different offloading schemes

定义参数v为MEC服务器负载不均程度因子:

(24)

在固定车载终端数为50的情况下,研究MEC服务器的负载不均程度对任务完成率的影响。由图5可以看出,ALL-MEC策略以及Random策略会因MEC服务器负载不均而无法保证计算任务完成率。GAOS策略在对决策方案进行迭代时,对负载严重的MEC服务器减少了计算任务的卸载,对负载较轻的MEC服务器增加了计算任务的卸载,以达到负载均衡的效果,相较于其他策略,其受MEC服务器负载不均的情况影响较小。

图5 负载不均程度对任务完成率的影响Fig.5 Influence of load unevenness degree on task completion rate

可以看出,GAOS策略能够在有限次的迭代后收敛,得到较优的卸载策略。通过与传统计算卸载策略的实验对比可知,GAOS策略在具有各种多优先级计算任务的车联网场景下,与可以卸载更多数量的车载安全型计算任务至边缘服务器,符合实际车联网场景下车载安全性业务的处理要求。同时其在迭代的过程中将更多的计算任务卸载至具有更多计算资源的边缘服务器,而对计算资源较少的边缘服务器减少计算任务的卸载,实现了边缘服务器负载均衡。

4 结束语

本文提出基于遗传算法的任务卸载策略GAOS,用于在负载不均的多MEC服务器车联网中寻找最优卸载策略,其能够在有限次迭代后收敛,满足实际车联网场景下车载安全性业务的处理要求。仿真结果表明,在车联网环境车载计算任务不断增加的情况下,GAOS可实现边缘服务器负载均衡,任务成功处理数量较Random和ALL-MEC策略分别增加了约30%和50%。下一步将设计部分卸载策略,将车载计算任务合理拆分一部分至MEC服务器,一部分则留在本地,从而在结合MEC服务的同时充分利用本地的计算资源。