日新月异的科技创新推动着行业变革不断向前发展^[1], 车联网作为交通领域中转型升级的重要一环, 正逐步向智能网联方向迈进^[2]. 在实时感知交互的驾驶场景中, 车载智能应用软件将产生大量的任务数据, 算力需求与日俱增^[3].

云端拥有丰富的计算资源, 将数据上传至数据中心后经过集群计算返回结果, 能以极快的速度实现相应数据的处理^[4]. 增强现实、互动直播、智能制造等新型业务对时延和网络带宽有着强烈诉求. 如果将这些数据都通过核心网传输到远程云端处理, 仅数据的传输就会导致很高的时延^[5], 核心网络的带宽也难以支持大量的数据传送, 一旦骨干网出现拥塞会导致数据传输极其不稳定^[6]. 而边缘计算(mobile edge computing, MEC)关注局部业务^[7], 能满足实时性需求, 计算方式也面向本地化, 将其应用到车联网领域可有助于解决智能驾驶在交通信息获取和数据处理上所面临的难题^[8].

在计算密集的通信场景中, 若所有用户都进行边缘迁移将导致额外的网络负载压力, 因而合理的任务调度策略会深刻影响着MEC系统的稳定性. 当边缘侧处理的时间过长时, 业务质量也会相应地降低. 文献[9]将MEC服务器之间的协作卸载视为马尔科夫决策过程, 为了最小化任务卸载时延, 提出带有自适应权重采样机制的Actor-Critic算法以及一种离线集中训练分布式执行框架来优化协作卸载策略. 文献[10]考虑到交通动态和不同车联网应用的异构需求, 根据不同的时延特性对任务分类, 利用近端策略优化算法获得连续的动作空间并求解最佳优先动态因子, 以最大化提高系统吞吐量. 关于任务属性的卸载研究中, 文献[11]通过对车辆任务属性的多个维度展开分析, 设计了一种基于广义Benders分解和重构线性化的两阶段启发式迭代算法, 以决定本地执行、卸载至RSU或者协作车辆处理. 文献[12]为解决任务多样性以及车辆移动性导致的用户通信质量问题, 提出了一种基于移动感知计算效率的任务卸载和资源分配方案, 旨在权衡计算时间和能耗之间的关系. 文献[13]将车辆任务划分成多个子任务, 以最小化系统中所有任务的平均时延为优化目标, 提出了一种基于蚁群优化算法的卸载方案, 其中在信息素矩阵的初始化中考虑了基站负载和用户与基站之间的距离两个因素.

在协调不同层级的资源调度方面也有不少研究. 为了保证高速移动车联网场景中的延时、能耗和支付成本需求, 文献[14]在云-边-端三层架构中利用基于多智能体的匈牙利算法解决二部图最大匹配问题下的动态任务卸载问题. 文献[15]将请求车辆、边缘服务器和云中心之间的竞争与合作建模为 Stackelberg 博弈问题, 基于反向归纳法获得请求车辆的最优任务分配, 同时基于遗传算法来寻找边缘服务器和云端的最优定价方案. 在资源分配和计算处理方面, 文献[16]设计了一种基于Takagi-Sugeno模糊神经网络和博弈论的任务卸载方案, 在预测到未来交通流量后, RSU根据结果进行实时负载均衡, 进而利用博弈论得到最佳卸载策略. 为满足车联网中低时延、高可靠的用户需求, 文献[17]构建了一个结合用户关联、子信道和功率分配的资源优化目标函数, 并以多种时延作为约束条件, 提出了一种低复杂度的用户关联方法. 文献[18]在小蜂窝基站协作计算框架下, 联合用户关联、信道分配和多部分协作任务卸载3个优化问题, 设计了一种基于遗传和深度确定性策略梯度的计算卸载方案.

但是现有研究大多未对任务准入控制展开深入研究, 因此在边缘服务器资源受限的前提下, 针对并发性计算任务, 如何高效地提升系统服务质量成为本研究的主要内容. 重点结合二分搜索法和拉格朗日乘子法求得功率控制和计算资源的最优分配, 同时联合多种优化策略的鲸鱼优化算法来制定最佳卸载决策.

1 系统模型 1.1 网络模型

基于MEC的车联网架构如图1所示, 该系统由基站、邻近部署的MEC服务器以及智能车辆组成. 考虑在城区道路中的任务密集区域, 低速行驶的车辆可以通过无线通信来请求任务卸载. 由于基站只提供通信功能, 而部署在路侧单元的MEC服务器通过有线链路与基站相连, 从而能处理相关的实时业务. 假定不同用户在传输数据时采用OFDM复用技术, 即用户通过若干个正交的子信道来发送数据信号. 任务卸载时设定为准静态信道模型, 信道在卸载周期内保持恒定, 但在不同计算任务的卸载周期间允许发生变化.

在单MEC服务器-多车辆场景中, 智能车辆以城区车速随机行驶在边缘服务器的通信覆盖范围内, 所有车辆的集合表示为$ u = \{ 1, 2, \cdots, U\} $. 假定在某一时刻t, 单服务器范围内的用户u都有一个并发性计算任务需要处理, 定义为二元组$ T_{{\rm{ask}}}(u) = \{ D_u, C_u\} $, 其中, $ D_u $表示传输数据的大小, $ C_u $表示完成任务所需的CPU周期数. 本文考虑的是完全卸载方案, 即任务都是不可再分, 仅能被当成整体进行处理. 令$ x_u \in \{ 0, 1\} $表示用户u的卸载决策, 当$ x_u = 1 $时表示用户u选择将任务卸载至MEC服务器执行, 否则, 任务在本地执行计算.

1.2 计算模型 1.2.1 本地计算

智能车辆本身拥有定量的异构存储和计算资源, 当用户决定在本地执行任务时, 令$ f_u^l $表示车辆u的本地计算能力(CPU周期数), 则本地执行任务的计算时延$ t_u^l{\kern 1pt} $为:

$ t_u^l = \frac{{{C_u}}}{{f_u^l}} $

(1)

由文献[19]可知, 本地执行时的能量消耗为:

$ E_u^l = \kappa {(f_u^l)^2}{C_u} $

(2)

其中, 能耗系数$\kappa $是与车辆芯片结构相关的常数.

1.2.2 MEC服务器计算

当车辆u选择任务卸载到边缘侧执行时, 用户会将计算任务经由无线网络上传至服务节点, MEC服务器为其分配合理的计算资源f_u以便进行及时处理.

由于大量并发性的车辆计算任务需要同时进行卸载判决, 当任务数尚未到达最大准入数时均可选择卸载至MEC服务器或者车载计算单元执行, 但是一旦达到最大连接数时边缘侧必须适时做出组合决断, 选择最符合系统效益的方案来进行卸载, 因而任务的等待时延暂不做考虑, 即不存在任务等待队列.

令t_MEC表示为MEC服务器执行任务的所需时延. 考虑到回传结果的数据量较小, 其回传时延可忽略不计, 因此MEC服务器在执行卸载时, 任务处理时延可以表示为:

$ {t_{{\rm{MEC}}}} = t_{{\rm{up}}}^u({p_u}) + t_{{\rm{exe}}}^u({f_u}) $

(3)

其中, $t_{{\rm{up}}}^u({p_u})$表示任务上传至边缘侧所需时延, $t_{{\rm{exe}}}^u({f_u})$表示边缘服务器计算所需的时延, 并有如下计算公式:

$ t_{{\rm{up}}}^u({p_u}) = \frac{{{D_u}}}{{{R_u}({p_u})}} $

(4)

$ t_{{\rm{exe}}}^u({f_u}) = \frac{{{C_u}}}{{{f_u}}} $

(5)

式(4)中由香农公式可得到数据的传输速率为$ {R_u}({p_u}) = W{\log _2}\left(1 + \dfrac{{{p_u}{h_u}}}{{{N_0}}}\right) $. 其中, W为正交子信道传输带宽, p_u为车辆u的发射功率, h_u为上行链路的信道增益, ${h_u} = 140.7 + 36.7{\rm{log}}_{10}(d)$, d为车辆与所属MEC服务器之间的通信距离, N₀为噪声功率.

用户u选择路端处理任务时, 车载终端仅在传输过程中产生能耗. 因此在边缘节点执行时, 对用户而言, 该能耗E_MEC计算公式如下:

$ {E_{{\rm{MEC}}}} = {p_u}t_{{\rm{up}}}^u({p_u}) = \frac{{{p_u}{D_u}}}{{W{{\log }_2}\left(1 + \dfrac{{{p_u}{h_u}}}{{{N_0}}}\right)}} $

(6)

由式(6)可以看出, 在某一特定时刻下车辆位置固定, 传输信道增益和噪声功率均为定值, 卸载能耗的计算将与传输功率息息相关. 由于不同用户对系统时延和能耗的偏好不同, 这将导致卸载决策存在一定差异, 因此在最大功率限制范围内, 如何根据具体的偏好权重来适时调整发射功率, 做出最优的卸载判决将是一个重点研究问题.

1.2.3 效用函数

考虑到用户的卸载决策为0-1变量, 因此任务处理时延和能耗的综合表达式可以描述如下:

$ {t_u} = (1 - {x_u})t_u^l + {x_u}{t_{{\rm{MEC}}}} $

(7)

$ {E_u} = (1 - {x_u})E_u^l + {x_u}{E_{{\rm{MEC}}}} $

(8)

在车联网MEC系统中, 用户的使用感受主要由其车载任务的执行完成时间以及终端设备的能量消耗来表征. 在计算密集场景中, 为了衡量用户对于不同时延和能耗偏好下的驾驶体验, 将用户u的任务卸载整体效用定义为:

$ {J_u} = {x_u}\left(\beta _u^t\frac{{t_u^l - {t_{{\rm{MEC}}}}}}{{t_u^l}} + \beta _u^e\frac{{E_u^l - {E_{{\rm{MEC}}}}}}{{E_u^l}}\right) $

(9)

其中, $\;\beta _u^t, \; \beta _u^e$分别表示用户u对时延和能耗的偏好比重, $\;\beta _u^t, \; \beta _u^e \in [0, 1]$, 且$ \;\beta _u^t + \beta _u^e = 1 $. 当用户对于时延要求更高时, 适当加大该权重数值, 反之亦然. 卸载效用的数值越高, 意味着越来越多的用户从边缘网络中获益, 从而避免终端设备产生过重的计算开销.

2 问题分析 2.1 系统效用最大化

由于车载终端在计算能力和资源存储等方面存在不足, 每辆车都会以一定的概率将计算任务迁移至MEC服务器. 在给定卸载策略X、传输功率P和计算资源分配F后, 定义车辆u处理任务的总效用由式(10)给出:

$ J(X, P, F) = \sum\limits_{u \in U} {{J_u}} $

(10)

因此, 以联合优化动态资源分配和计算卸载决策(joint dynamic resource allocation and task offloading, JDRATO)使得系统效用最大化的问题可以表述如下:

$ \left\{\begin{gathered} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \mathop {\max }\limits_{X, P, F} J(X, P, F) \\ {\rm{s.t.}}\left\{\begin{gathered} {\rm{C}}1: {x_u} \in \{ 0, 1\} \qquad\quad\;\;\; \forall u \in U \\ {\rm{C}}2: 0 \leqslant {p_u} \leqslant p_u^{\max }\qquad \forall u \in U \\ {\rm{C}}3: {f_u} \gt 0 \qquad\qquad\quad\; \forall u \in S \\ {\rm{C}}4: \sum\limits_{u \in S} {{f_u}} \leqslant {f_0} \\ {\rm{C}}5: \sum\limits_{u = 1}^G {{x_u}} \leqslant M \\ \end{gathered}\right. \end{gathered}\right. $

(11)

其中, $ S = \{ u = 1, \cdots, G\left| {{x_u} = 1} \right.\} $表示卸载用户集合, f₀为单MEC服务器的最大计算资源, M为单MEC服务器在同时刻最多能容纳的用户数目. C1表示移动车辆只能选择本地执行或卸载至边缘服务器, C2表示发射功率不得超过最大允许功率, C3和C4表示分配给需要卸载任务车辆的计算资源必须大于0且不得超过总计算资源, C5表示同时准入用户数目不得超过最大允许阈值.

2.2 问题分解

在JDRATO问题中, 卸载决策与通信、计算资源的分发策略相互耦合, 在特定的任务调度方案下会匹配得到相应的传输功率和计算资源. 此外, 由于卸载决策X是0-1整数变量, 并且资源分配F、P是连续变量, 因此原优化问题为混合整数非线性规划, 属于NP-hard问题, 找到最优解通常需要指数时间级的计算复杂度, 难以在多项式时间内完成. 因此, 为了能够求解JDRATO问题, 需要将其分解为两个相关的子问题.

(1)针对特定卸载决策, 如何分配通信和计算资源.

(2)基于资源优化结果, 如何制定最优卸载策略.

基于上述考虑, 可以将原问题改写为:

$ \begin{gathered} \mathop {\max }\limits_X (\mathop {\max }\limits_{P, F} J(\hat X, P, F)) {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{C}}1 - {\rm{C}}5 \end{gathered} $

(12)

注意, 此时对卸载决策和资源分配的约束已经在分解过程中彼此解耦. 因此, JDRATO问题可以完全分解为如下两个小问题: 第1个为联合无线和计算资源的分派问题, 即RA子问题; 第2个为给定资源分配方案后的任务卸载决策问题, 即TO子问题.

RA子问题重新表述为式(13):

$ {J^*}(X) = \mathop {\max }\limits_{P, F} J(\hat X, P, F){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{C2 - C4}} $

(13)

TO子问题可以重写为式(14):

$ \mathop {\max }\limits_X {J^*}(X){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{C}}1, \; {\rm{C}}5 $

(14)

在选定已满足约束C2、C3和C4的可行任务卸载决策X的情况下, 原目标函数可以重写为:

$ J(X, P, F) = \sum\limits_{u \in S} {(\beta _u^t + \beta _u^e)} - V(X, P, F) $

(15)

其中, $ V(X, P, F) = \displaystyle\sum\limits_{u \in S} \left(\dfrac{{\beta _u^t{t_u}}}{{t_u^l}} + \dfrac{{\beta _u^e{E_u}}}{{E_u^l}}\right) $.

观察到式(15)的表达式第1项对于特定卸载决策是恒定的, 而$ V(X, P, F) $可以被视为卸载用户集合的总卸载开销. 因此, 将式(13)改写为最小化总卸载开销的问题, 即:

$ \mathop {\min }\limits_{P, F} V(X, P, F){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{C}}2 - {\rm{C}}4 $

(16)

将时延和能耗的计算公式代入计算可得到式(17):

$ V(X, P, F) = \sum\limits_{u \in S} {\frac{{{\phi _u} + {\varphi _u}{p_u}}}{{{{\log }_2}\left(1 + \dfrac{{{p_u}{h_u}}}{{{N_0}}}\right)}}} + \sum\limits_{u \in S} {\frac{{{\eta _u}}}{{{f_u}}}} $

(17)

其中, $ {\phi _u} = \dfrac{{\beta _u^t{D_u}}}{{t_u^lW}} $, $ {\varphi _u} = \dfrac{{\beta _u^e{D_u}}}{{E_u^lW}} $, $ {\eta _u} = \beta _u^tf_u^l $.

观察式(17)可以看出, 第1项只含有发射功率的变量, 属于上行功率控制的优化问题; 第2项只含有计算资源的变量, 属于计算资源分配的优化问题.

3 资源分配及卸载决策求解 3.1 上行功率控制

不同的系统时延和能耗偏好会产生不同的卸载决策, 而卸载能耗又与发射功率密切联系, 因此需要进行适当的功率控制. 对于移动车辆来说, 上行功率问题能细化为式(18):

$ \mathop {\min }\limits_{{p_u}} f(p{}_u){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{C}}2 $

(18)

其中, $ f({p_u}) = \dfrac{{{\phi _u} + {\varphi _u}{p_u}}}{{{{\log }_2}\left(1 + \dfrac{{{p_u}{h_u}}}{{{N_0}}}\right)}} $.

由于$ f(p{}_u) $二次可微, 利用导数理论知识, 对原函数进行一阶和二阶求导分别得到式(19)和式(20):

$ f'({p_u}) = \frac{{{\varphi _u}{{\log }_2}{\Lambda _u} - [{h_u}/({N_0}\ln 2)]({\Gamma _u}/{\Lambda _u})}}{{\log _2^2({\Lambda _u})}} $

(19)

$ \begin{split} & f''({p_u}) =\\ & \frac{{({h_u}/{N_0})[({h_u}{\Gamma _u}/{N_0} - 2{\varphi _u}{\Lambda _u}){{\log }_2}{\Lambda _u} + 2{h_u}{\Gamma _u}/({N_0}\ln 2)]}}{{(\ln 2)\Lambda _u^2\log _2^3{\Lambda _u}}} \end{split} $

(20)

其中, 为简化表达式, ${\Gamma _u} = {\phi _u} + {\varphi _u}{p_u} , \; {\Lambda _u} = 1 + {h_u}{p_u}/{N_0}$.

观察二阶导数, 在其定义域内该数值并非总为正数, 因此原函数为非凸函数. 假定在x₀处, 原函数一阶导为0, 可令其分子为0, 即满足:

$ \Omega ({x_0}) = {\varphi _u}{\log _2}\left(1 + \frac{{{x_0}{h_u}}}{{{N_0}}}\right) - \frac{{[{h_u}/({N_0}\ln 2)]({\phi _u} + {\varphi _u}{x_0})}}{{1 + {h_u}{x_0}/{N_0}}} = 0 $

(21)

同时将该点代入二阶求导式(20)中可得$ f''({x_0}) \geqslant 0 $. 根据拟凸函数的二阶导数判定条件, 原函数为拟凸函数, 因此在定义域内存在极小值. 注意到在可行域内, 对变量为$ p{}_u $的表达式(21)求导可得:

$ \Omega '({p_u}) = \frac{{{{({h_u}/{N_0})}^2}({\phi _u} + {\varphi _u}{p_u})}}{{(\ln 2){{(1 + {h_u}{p_u}/{N_0})}^2}}} \gt 0 $

(22)

可以看出, 在以$ {p_u} = 0 $为起点的区间内, 该函数为广义增函数, 同时在左端点处有:

$ \Omega (0) = - \frac{{{h_u}{\phi _u}}}{{{N_0}\ln 2}} \lt 0 $

(23)

结合上述推理过程, 可在初始区间$ [0, p_u^{\max }] $内使用二分搜索法, 并且在每步迭代计算中求解凸可行性问题, 最终在满足收敛准则条件下计算出满足式(21)的最优解, 由此可以得到上行链路的最优功率分配.

3.2 计算资源分配

由于边缘节点的计算、存储等资源有限, 在大规模的并行计算任务面前难以维持系统的稳定性, 因而需要优化资源配置问题. 该分配问题可重新表述如下:

$ \mathop {\min }\limits_{{f_u}} {\kern 1pt} {\kern 1pt} g({f_u}){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{C}}3,\; {\rm{C}}4 $

(24)

其中, $ g({f_u}) = \displaystyle\sum\limits_{u \in S} {\dfrac{{\beta _u^tf_u^l}}{{{f_u}}}} $.

应当注意到此定义域为凸集, 对$ g({f_u}) $求二阶偏导得到Hessian矩阵, 即:

$ \left\{\begin{gathered} \frac{{{\partial ^2}g({f_u})}}{{\partial {f_u}\partial {f_{u'}}}} = 0, \;\;\;\;\qquad\quad \forall u \ne u' \\ \frac{{{\partial ^2}g({f_u})}}{{\partial f_u^2}} = \frac{{2\beta _u^t f_u^l}}{{f_u^3}} \gt 0, \; 其他 \\ \end{gathered} \right.$

(25)

由于该海森阵严格正对角化, 为正定矩阵, 所以$ g({f_u}) $为凸函数. 在C3和C4约束条件下的拉格朗日函数表达式为:

$ L({f_u}, {\lambda _1}, {\lambda _2}) = \sum\limits_{u \in S} {\frac{{\beta _u^tf_u^l}}{{{f_u}}} + } {\lambda _{\text{1}}}( - {f_u}) + {\lambda _{\text{2}}}\left(\sum\limits_{u \in S} {{f_u}} - {f_0}\right) $

(26)

其中, $ {\lambda _1}, {\lambda _2} $分别为C3和C4相对应的拉格朗日乘子且$ {\lambda _1}, {\lambda _2} \geqslant 0 $. 紧接着, 利用Karush-Kuhn-Tucker (KKT)相关知识来求解, 经理论推导后可求得最优计算资源分配如下:

$ f_u^* = \frac{{{f_0}\sqrt {\beta _u^tf_u^l} }}{{\displaystyle\sum\limits_{u \in S} {\sqrt {\beta _u^tf_u^l} } }} $

(27)

3.3 卸载决策优化

在得到最优发射功率和计算资源分配方案后, 最终的卸载决策问题转化为:

$ {J^*}(X) = \sum\limits_{u \in S} {(\beta _u^t + \beta _u^e)} - \sum\limits_{u \in S} {f(p_u^*)} - g(f_u^*){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{C}}1, {\rm{C}}5{\kern 1pt} {\kern 1pt} {\kern 1pt} $

(28)

对于此类0-1整数规划问题, 如果采用精确算法求解则需要遍历整个搜索空间, 容易产生组合爆炸现象, 难以在多项式时间内寻找到最优解决方案. 相反, 受生物群体社会性生活方式启发而演化得到的群体智能优化算法, 通过模仿动物群体之间以一种合作方式来交流和互换信息, 能够以良好的并行性和自主探索性更快地解决复杂优化问题.

借鉴生物群体行为规律的寻优过程, 选定鲸鱼优化算法(whale optimization algorithm, WOA)^[20]来制定卸载决策. WOA采用随机或最佳搜索代理来模拟捕猎行为, 并使用螺旋来模拟座头鲸的泡泡网攻击机制^[21], 主要分为3步: 收缩包围、螺旋气泡网捕食和随机搜索. 其中, 座头鲸有50%的可能性在收缩包围机制和螺旋模型之间进行选择. 该算法具有机制简单、参数少、寻优能力强等优点. 但是, 基本鲸鱼优化算法存在收敛速度慢、求解精度低、容易陷入局部最优等缺点, 为此提出融合多种策略的鲸鱼优化算法(multiple strategy WOA, MSWOA), 使之更适合于求解组合优化问题.

3.3.1 适应度评价

适应度评价机制可以用来衡量种群生活中个体的搜索优势, 考虑到在卸载决策问题中存在最大准入用户数目的约束, 因此结合罚函数的优化理论, 将式(28)转化为无约束最小化问题, 得到式(29)的适应度函数. 在可行域范围内, 适应度值越小意味着系统效用越高.

$ {\textit{fitness}} = - \sum\limits_{u \in S} {{J_u}} ({x_u}, {\hat p_u}, {\hat f_u}) + \mu \cdot {h^2}(x) $

(29)

其中, $ h(x) = \max \left\{ 0, \displaystyle\sum\limits_{u = 1}^G {{x_u}} - M\right\} $, μ为罚因子, 一般取值为10¹³–10¹⁵.

3.3.2 收敛因子调整

基本算法中的收敛因子a以线性速率下降, 不能很好地反映种群变化情况, 如果在探索阶段不能够及时发现种群最优解, 那么在利用阶段就会加速进入局部最优状态, 影响寻优精度. 为弥补这一缺陷, 需要采用非线性变换手段来解决. 基于此种考虑, 可以采用如式(30)所示的收敛因子来提升算法性能, 该因子的整体收敛速度表现相对比较平缓, 能在较长时间内达到全局搜索能力, 从而降低种群中最优个体对其余个体的影响.

$ a(t) = 2 - 2{\left(\frac{{{T_{\max }} - t}}{{{T_{\max }}}}\right)^\alpha } $

(30)

其中, T_max、t分别为最大迭代次数和当前迭代次数, α为非线性调整参数, 取值一般为大于1的整数.

基于上述变化, $A = 2ar_1 - a, \; C = 2r_2$ (r₁和r₂为[0, 1]的随机值)也会相应地做出调整.

3.3.3 自适应权重

经典算法在求解后期容易陷入局部最优, 会降低种群多样性. 为平衡探索和利用阶段的寻优能力, 采用一种呈指数变化趋势的自适应权重策略. 在算法前期, 较大的权重易于提升开发的全局搜索性能, 保证合适的搜索范围; 随着迭代次数的不断增加, 在靠近最优解时, 权重值会以指数形式减小, 使算法的局部寻优能力大幅提升. 自适应权重表达式如式(31)所示:

$ \omega = {{\rm{e}}^{ - 5{{(\frac{t}{{{T_{\max }}}})}^2}}} $

(31)

由此, 螺旋更新阶段($ p \geqslant 0.5{\kern 1pt} $)的位置计算公式如下:

$ X(t + 1) = \omega {\kern 1pt} {X^*}(t) + {{\rm{e}}^{bl}}\cos (2{\text{π}} l){\kern 1pt} D $

(32)

其中, $ D = \left| { {X^*}({{t}}) - X(t)} \right| $.

3.3.4 游走策略

为了克服算法早熟弊端以及扩大最优解的搜索空间, 采用两种游走策略来增加随机性, 提高算法的全局寻优能力.

(1)三角形游走策略

在搜寻猎物阶段(即$ p \lt 0.5且\left|A\right|\geqslant \text{1} $), 座头鲸会随机选择鲸鱼代理进行位置更新, 从而逐渐搜索到猎物.此时不需要直接靠近食物, 而是以三角形方式在周围进行游走. 在得到随机参考代理和猎物之间的距离$ {L_1} $后, 随机选取游走的步长范围$ {L_2} $, 以$ \delta $为行进方向, 由式(36)获得游走所得到的位置与食物之间的距离 h.

$ {L_1} = \left| {C \cdot {X_{{\rm{rand}}}}(t) - X(t)} \right| $

(33)

$ {L_2} = {L_1} \cdot {l_1} $

(34)

$ \delta = 2{\text{π}} {l_2} $

(35)

$ h = L_1^2 + L_2^2 - 2{L_1}{L_2}\cos (\delta ) $

(36)

$ X(t + 1) = {X_{{\rm{rand}}}}(t) + A \cdot h $

(37)

其中, $ {l_1} $、$ {l_2} $分别为[0, 1]之间的随机数.

(2) Levy飞行游走策略

在收缩包围阶段(即$ p \lt 0.5且\left|A\right| \lt \text{1} $), 除了利用自适应权重对最优个体动态加权外, 还引入莱维飞行策略来增加局部探索能力. Levy飞行通过长步与短步相互交替的走位来提供高质量的随机因子, 具体计算方式如式(39)所示.

$ X(t + 1) = \omega {X^*}(t) + A \cdot l \cdot L{\text{e}}vy(\beta ) $

(38)

$ \left\{\begin{split} & Levy(\beta ) = \frac{u}{{{{\left| v \right|}^{\frac{1}{\beta }}}}} \\ & u \sim N(0, \sigma _u^2){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} v \sim N(0, \sigma _v^2){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \\ & {\sigma _u} = {\left[ {\frac{{\Gamma (1 + \beta )\sin \left(\dfrac{{{\text{π}} \beta }}{2}\right)}}{{\Gamma \left(\dfrac{{1 + \beta }}{2}\right){2^{\frac{{\beta - 1}}{2}}}\beta }}} \right]^{\frac{1}{\beta }}} \\ & {\sigma _v} = 1 \end{split} \right.$

(39)

其中, l为莱维飞行步长收缩因子, β是莱维飞行控制参数, 在[0, 2]之间随机取值.

根据上述改进方法, 经过多策略融合后的鲸鱼优化算法综合表达式如下:

$ X(t+1)=\left\{\begin{array}{l} \omega {X}^{*}(t)+{{\rm{e}}}^{bl}\mathrm{cos}(2 {\text{π}} l)D, \quad p\geqslant 0.5\\ {X}_{{\rm{rand}}}(t)+A\cdot h, \qquad\qquad\; p \lt 0.5且\left|A\right|\geqslant \text{1}\\ \omega {X}^{*}(t)+A\cdot l\cdot Levy(\beta ) , \quad p \lt 0.5且\left|A\right| \lt \text{1}\end{array} \right.$

(40)

3.3.5 传递函数映射

传统WOA算法主要针对连续函数优化问题, 其搜索空间值域是连续数值, 而在二进制卸载决策中, 将个体每一维的位置都必须限定为0或者1, 因而原算法并不能直接用来求解. 但是, 传递函数可以实现从连续域向离散域的空间变换, 即由传递函数来计算原始位置所对应的的概率值来决定转换后的位置上取值为0或者1. Mirjalili等人在文献[22]中提出了多个传递函数, 并且将其分为两族: S型和V型. 利用S型函数将鲸鱼搜索代理的连续位置转换成离散的概率表达式如下所示.

$ S({X_{ti}}) = \frac{1}{{1 + {{\rm{e}}^{ - {X_{ti}}}}}} $

(41)

传递函数值会映射在区间[0, 1]内, 对于靠近最优解的代理位置, 其传递函数所计算出的概率数值会比较高, 因而取1的可能性也更大, 反之亦然. 由此, 更新规则设定如下.

$ {X}_{ti}=\left\{\begin{array}{l}1,\quad S({X}_{ti}) \gt rand\\ 0,\quad 其他\end{array} \right.$

(42)

S型传递函数会强迫个体选择0或1, 容易使搜索过程陷入局部最优. 相反, V型函数通过鼓励偏离最优解的个体保持原有选择, 以及允许接近最优解的个体翻转其选择, 以此来扩大搜索空间的范围, 从而弥补了S型传递函数的缺陷. 本文选定的V型传递函数见式(43):

$ V({X_{ti}}) = \left| {\frac{2}{\text{π} }\arctan \left(\frac{{\text{π} } }{2}{X_{ti}}\right)} \right| $

(43)

对应映射的更新规则如式(44)所示:

$ {X}_{ti}(t+1)=\left\{\begin{array}{l}{X}_{ti}(t), \qquad\;\; V[{X}_{ti}(t)] \gt rand\\ [{X}_{ti}(t)]^{-1}, \quad 其他\end{array} \right.$

(44)

其中, $ {[{X_{ti}}(t)]^{ - 1}}{\kern 1pt} $表示对搜索代理的每一个变量值取反.

3.3.6 算法流程

基于MEC的车联网系统中, 所有车辆任务的卸载决策矩阵X均看做一个鲸鱼搜索代理. 在每一次种群迭代过程中, 对选择卸载至边缘服务器(即所在位置取1)的矩阵子元素进行计算资源分配, 同时计算适应度找出最优卸载策略. 总体算法流程如算法1所示.

算法1. 基于多策略鲸鱼优化算法的计算卸载方案

输入: 种群规模K; 车辆数目N; 最大迭代次数$\scriptstyle {T_{\max }} $; 停止准则$\scriptstyle \varepsilon $

输出: 最优位置$\scriptstyle {X^*}(t) $; 最优计算资源分配F; 系统效用J

1. 初始化

2. 　随机生成N维鲸鱼搜索代理的位置$\scriptstyle {X_i} \; ( i = 1, \cdots, K)$;

3.　 t=0;

4. 　根据式(27)分配卸载任务的计算资源;

5. 　根据式(29)计算搜索代理的适应度;

6. 　记录个体极值和群体极值;

7. $\scriptstyle {\rm{while} } \; t < { {T}_{\max } } \; {\rm{or}} \; \left| \frac{ { {X}^{*} }(t)-{ {X}^{*} }(t-1)}{ { {X}^{*} }(t-1)} \right| > \varepsilon$

8. repeat

9.　 for k=1:K do

10.　　 根据式(30)更新a;

11. 　　更新A、C、D, 在[0, 1]范围内随机生成p;

12. 　　if p<0.5 then

13. 　　　if $\scriptstyle \left| A \right| \lt 1 $ then

14.　　　　 根据式(38)和式(44)更新$\scriptstyle X(t) $;

15.　　　 else

16. 　　　　根据式(37)和式(44)更新$\scriptstyle X(t) $;

17. 　　　end if

18. 　　else

19. 　　　根据式(32)和式(44)更新$\scriptstyle X(t) $;

20. 　　end if

21. 　end for

22. 　计算种群适应度;

23. 　更新最优位置$\scriptstyle {X^*}(t) $;

24.　 根据式(10)得到系统效用J;

25.　 t=t+1;

26. end while

4 仿真分析 4.1 参数设置

在城区道路上, 考虑单MEC服务器-多用户的车联网场景, 假定在某时刻每辆车都有并发性的计算任务需要处理, 此时车辆随机处于其所属边缘服务器的覆盖范围内. 具体通信参数和算法参数分别如表1和表2所示.

4.2 结果分析

本节利用Matlab R2018a仿真平台来进行实验对比, 为验证本文所提的多策略鲸鱼优化算法(MSWOA)性能, 引入文献[23]中所提WOAWC作为基准方案, 该算法在随机寻找食物过程中利用柯西逆累积分布函数对鲸鱼位置信息进行变异, 以及在包围捕食阶段通过正弦函数的自适应权重方法改进了WOA的局部搜索能力.

4.2.1 不同通信条件下的系统效用

图2给出了系统效用与移动车辆数目之间的关系. 3种不同算法下的系统效用都明显呈现上升趋势, 这是因为MEC服务器拥有丰富的计算资源, 终端设备数量越多, 更多的车辆会倾向于将工作负载迁移至边缘节点来完成, 从而获取更优质的服务体验. 与此同时, 本文所提算法在与基准方案对比中都表现出更优异的性能, 特别在车辆数达到30以后系统效用迅速攀升, 究其原因是多种策略的融合使得搜索空间不断扩大, 种群多样性得到增强, 从而提高了算法的寻优能力.

图3是不同最大准入用户数目下系统效用的对比图. 由图3可知, 最开始时3种算法的系统效用几乎持平; 但随着允许准入数量的增加, MSWOA算法下的效益获得快速提升. 一方面, 系统允许接纳更多的用户卸载任务至边缘侧, 使设备自身的计算资源得以释放出来, 系统双方也由于不断进行通信提高了网络吞吐量, 因而能提供更优质的需求服务; 另一方面, MSWOA算法经过多元化的代理搜索, 在解空间不断尝试新的组合优化方案, 能挖掘出潜在的收益机会.

图4反映的是在不同最大发射功率下系统效用的变化情况. 整体变化都较为平缓, 没有过于急剧的陡降现象发生. 由于车载终端会根据特定的时延能耗偏重来调节自身的发射功率, 从而提高网络的服务质量. 而当智能车辆的最优上行功率确定后, 系统车辆数和同时刻准入用户数均为固定数值, 不同并发组合方式下的效用计算会出现些许变化, 因而会有所波动.

4.2.2 不同任务属性下的系统效用

本节针对任务的传输量和计算量两个属性展开对比研究, 不同传输数据量和任务计算量会对系统卸载收益产生不同的反应.

图5表现的是传输数据大小对系统效用的影响. 数据任务在迁移至边缘服务器时, 智能终端会因无线通信而产生能量损耗, 当数据量不断增加时, 该数值会不停地变大, 系统效用也随之减小. 3种算法中, 由于WOA和WOAWC都较容易出现早熟现象, 会受到局部最优解的影响而放弃探索出新的卸载组合策略, 因而效用看起来并不高.

图6是3种算法在不同数据计算量下的系统效应对比图. 由于计算任务卸载至MEC服务器后, 处理数据所消耗的计算资源由边缘侧来承担, 由此缓解了终端资源紧俏的困境. 考虑到用户自身所消耗能量主要来自于传输过程, 在同样的数据传输量条件下, 越高的计算量移交至路侧会极大地降低智能设备的执行总代价, 从而为用户提供更优质的需求服务.

4.2.3 不同用户偏好下的系统效用

在影响系统效用的众多因素中, 不同用户对于时延和能耗的偏重也是值得深切关注的, 其对比结果如图7所示. 从图7可以觉察出, 在时延偏好从0.2逐渐升高到0.8的过程中, 系统效用逐渐下降且最后达到相对稳定状态. 对时延的偏好增加意味着对系统服务实时响应的要求会更为严格, 部分计算任务最终会决定在本地执行, 因而效用不高; 反观能耗偏重的增加会明显提高效用值, 这是因为当用户对时延不太敏感时, 会大概率选择由边缘计算节点来辅助执行任务, 从而改善了用户体验.

4.2.4 不同转移函数下的系统效用

图8中表现的是在位置更新时S型和V型传递函数对于系统效用的性能影响. 由于V型传递函数并不会像S型函数一样强制性地迫使搜索代理改变相应变量取值为0或1, 换句话说, 当代理变量所处位置将使适应度值较低时, V型函数会鼓励其停留在其当前位置, 即并不需要强迫发生转变, 或者说当使得适应度值较高时, 它们也允许代理变量切换到其补充位置, 即增加了个体选择的可能性, 从而在维持最优解的同时能更大程度地探索出新的卸载组合.

5 总结

在单MEC服务器资源受限的情况下, 针对并发性计算任务, 如何合理地分配网络资源以及制定卸载决策是车联网边缘计算中需要关注的重点. 本文首先利用二分法和拉格朗日乘子法得到最佳功率控制和计算资源分配的优化方案; 然后提出包含调整收敛因子、自适应惯性权重、游走策略的鲸鱼优化算法, 为约束最大准入用户数目, 在适应度评价中引入了罚函数方法, 最后采用V型传递函数来处理0-1卸载问题. 由于本文考虑的是在特定时刻单MEC服务器-多车辆情形下的并发性任务的卸载控制问题, 而如何协调端-边-云三层计算资源来解决高并发流量下的任务调度问题是未来的研究内容.