V2X多节点协同分布式卸载策略

曹敦，张应宝，邹电，王进，汤强，冀保峰

（1.长沙理工大学计算机与通信工程学院，湖南 长沙 410114；2.南京邮电大学宽带无线通信与传感网技术教育部重点实验室，江苏 南京 210003；3.河南科技大学信息工程学院，河南 洛阳 471023）

0 引言

在这个万物互联的时代，人工智能和通信技术的快速发展能实现车辆与X（即车、人、网络、基础设施等）的通信[1]，并提升车辆的自动驾驶能力，改善交通运营和服务智能化欠缺的现状。同时新型车载终端的应用也对通信质量和服务智能化要求日益严苛[2-3]。移动边缘计算（MEC,mobile edge computing）的出现能够有效地应对这一挑战。MEC是一种新型通信架构，将具有存储、计算、通信功能的服务平台部署在网络边缘位置，帮助移动终端用户将服务任务就近卸载到边缘节点上，进行协同处理[4-5]，从而减轻通信链路的传输压力，缩短服务的响应时间，减少移动设备的能耗和传输成本[6-7]。MEC 技术作为5G 移动通信中开始应用的一项重要技术，目前受到工业界和学术界的广泛关注[8]。而其在车联网中的应用能提供低时延的计算智能，使用户服务体验[9-10]有质的改变。

车联网服务类型可分为车载安全型、车载增强型和车载娱乐型三大类[11]。服务对时延、数据量、任务复杂度和子任务间耦合度等有不同的要求[12]。根据特征的不同，又可将任务分成不同的类型，如根据时延限制可分为时延敏感型和非时延敏感型，根据任务复杂度可分为计算资源密集型和稀疏型，根据子任务的耦合度分为可分离型和不可分离型[13]。时延敏感型的计算任务对数据的实时性要求极高，而计算密集型任务需要大量的存储资源，但时延要求相对宽松[14]。依据Robertazzi的可分离任务理论[12]，可分离型任务可分成若干任意大小的子任务，每个子任务之间没有依赖关系，可以按照任意顺序进行处理。而车载娱乐型服务中的视觉视频剪辑和动画渲染等任务具有非时延敏感、数据量大、复杂度高、耦合度低的特点。在V2X（vehicle to everything）通信中，利用下沉到车辆及路侧单元的计算资源设计一种任务可拆分、多节点协同的卸载决策，可满足此类服务的服务质量（QoS,quality of service）要求。

然而，任务可拆分、多节点协同的卸载决策需面对一系列问题。在任务执行周期内，车载任务卸载环境是动态不确定的，网络拓扑结构及无线信道状态会快速变化，如何选择在任务执行周期内可用的协同节点是需要解决的问题之一，且考虑协同节点通信和计算资源差异，如何进行任务不等拆分，使任务分布式计算执行时延最小化，以提高信道利用率是需解决的问题之二。本文面对上述2 个问题，提出了一种V2X多节点协同分布式卸载策略。本文主要的研究工作总结如下。

1) 本文构建了V2X 下本地、MEC 和协同车辆多节点协同计算模型，它联合了卸载策略和任务不等拆分问题，通过预测车辆行驶轨迹，将协同卸载问题建模成本地与协同节点分布式计算时间较大值最小化问题。

2) 本文采用博弈论中的纳什均衡来求解上述问题中服务的卸载策略，并将串行卸载问题公式化为带约束的高维非线性优化问题。

3) 在卸载策略确定的情况下，本文采用序列二次规划（SQP,sequential quadratic programming）算法求解上述优化问题，通过拉格朗日函数将原问题转化为二次规划子问题，从而确定任务的不等拆分比例，实现本地与卸载的工作时间均衡。

4) 实验结果表明，本文提出的算法具有良好的效能和优越性。与其他4 种基准算法相比，本文提出的算法能够获得更低的系统时延，并有良好的收敛性。

1 相关工作

国内外学者针对移动边缘计算的任务卸载问题开展了大量的研究。文献[15]研究了静止状态下的用户卸载，考虑到MEC的车载无线网络和计算能力有限的问题，设计了一种无线和计算分配联合优化算法用来求解用户的卸载决策。文献[16]提出了LBB（linearization based branch and bound）和CRI（closest rounding integer）算法分别解决在用户静止和速度恒定状态下的计算卸载策略，考虑到时变信道对任务卸载策略的影响，该研究提出了一种最接近四舍五入算法来解决固定时变频谱效率问题。文献[17]提出了在加速度不变的条件下多用户计算卸载决策，考虑到多个用户设备同时通过无线信道卸载计算任务时的信道干扰问题，设计了一种基于强化学习的进化博弈算法。文献[18]研究了车辆无线网络的移动感知计算卸载，考虑到车辆的随机移动和卸载过程中可能出现的越区切换问题，该研究提出了一种分析模型用来计算卸载决策。文献[19]提出了一种通过建立适用于移动和普适计算场景的三层体系架构来优化用户计算卸载决策的方法。

文献[20]研究了服务请求车辆发送不可拆分数据包时的平均上行局部时延，该研究利用最接近接收方模型确定单个边缘节点。文献[21]研究了每个用户通过无线多址传输将计算任务卸载到多用户协同计算，考虑到非正交多址接入（NOMA,non-orthogonal multiple access）的共信道干扰和MEC的计算任务均等拆分问题，该研究提出了联合最优任务卸载和资源分配的算法求解卸载决策。文献[22]通过研究多用户多输入多输出预编码和计算资源不等分配方法，提出了一种利用半定松弛法和舍入法优化卸载决策。文献[23]提出了基于多臂强盗理论进行任务的不等拆分策略。文献[24]提出了在动态环境下基于自适应学习的多车辆等分任务卸载策略，该研究以最小化平均卸载时延为目标，提出了一种基于V2V 通信的多车任务卸载系统模型。

综上所述，当前已有的相关研究集中于以下2 个方面：1) 通过建立车辆的不同运动模型，优化用户的卸载决策问题；2) 根据服务任务类型的差异，优化卸载决策问题。当前关于协同卸载策略的研究工作虽然很多，但是聚集在车辆行驶轨迹预测下的不等任务拆分策略还较少。本文研究了V2X多节点协同串行卸载、分布式计算策略，联合优化了卸载决策和任务不等分配比例。

2 系统模型

本文主要考虑高速直行道路场景。因反向行驶车辆相对宿主车辆有较大反向相对速度，停留在宿主车辆通信范围的时间较短，因此协同车辆仅考虑与宿主车辆同向行驶的车辆，并且考虑车辆变道、变加速等行驶行为。为充分利用计算资源和减少卸载计算时延，宿主车辆可以选择部分任务在本地执行，其余任务利用V2X 通信模式卸载到协同节点上协助处理。

2.1 网络模型

网络模型如图1 所示。可提供边缘计算的路侧单元（RSU,road side unit）标记为v0，假设RSU 覆盖范围内有N辆车呈泊松分布，表示为V={v1,v2,…,vi,…,v N},i∈[1,N]。假设车辆内都装有北斗卫星导航系统等定位设备，可以实时获取车辆的轨迹信息[25]。集合V中车辆终端的轨迹信息用集合S表示，，第α辆车在第t时刻的轨迹信息为，其中为速度，为第α辆车的位置坐标。当车辆vi为宿主车辆时，在卸载时延和通信范围的约束下，vi有n∈[0,N]个可选择的协同节点Mi={mi,0,mi,1,…,mi,j,…,mi,n},(i≠ 0,j≠i,j∈[0,n])，其中，mi,j表示宿主车辆vi的第j个协同节点，mi,0=v0表示RSU 可用。协同节点的卸载顺序为Qi,j={qi,0,qi,1,…,qi,j,…,qi,n},(i≠0,j≠i,j∈[0,n])，其中，qi,j表示vi卸载到mi,j的卸载顺序数，qi,j∈ {1,2,…,n+1}，例如qi,j=4 表示mi,j为第4 个执行卸载的协同节点。宿主车辆vi的协同策略可通过协同节点集Mi根据Qi,j排序后获得，表示为Ai=rank(M i,Qi,j)，rank(·) 表示将Mi中元素mi,j按Qi,j中对应元素qi,j的值升序排列。

图1 V2X多节点协同分布式卸载策略网络模型

为了便于阅读，本文中主要变量及含义如表1所示。

表1 主要变量及其含义

2.2 通信模型

本文各节点采用正交频分多址（OFDMA,orthogonality frequency division multiple access）技术接入系统。任务车辆在执行边缘卸载时，通过V2R（vehicle to RSU）、V2V（vehicle to vehicle）通信模式将计算任务卸载到路侧单元和协同车辆。本文假设多协同节点干扰已通过正交频分多址技术消除，且车辆在任务上传时间内无线信道状态保持稳定[23]。不失一般性，假设V2V 通信模式复用V2R 通信模式的上行传输通道。根据香农定律可得，数据的上传速率为

其中，*可为v 或r，vw和rw分别表示V2V 和V2R信道带宽；1p表示上传链路信道衰落因子；p2表示路径损耗因子；li,j表示从vi到mi,j的欧氏距离；0ρ表示通信内部高斯噪声密度；P为发射功率。

2.3 运动模型

本文构建行驶轨迹预测模型，通过t时刻的位置信息预测t+Δt时刻的位置信息。假设本文的行驶轨迹预测模型目标是估计用户短时间 Δt内的移动轨迹。为方便描述，依据车辆行驶方向平行道路建立二维坐标，第α辆车在t+Δt时刻的二维坐标为

由L2 范数可获得第α、β辆车在t+Δt时刻的距离为

即

2.4 计算模型

定义协同节点mi,j被分配的计算任务为其中，Di,j表示任务量大小，表示任务Di,j从vi卸载到mi,j的顺序标签值，表示任务Zi,j所能容忍的最大时延。一些计算任务具有较高的复杂性，无法及时得到计算结果。因此，需要决策Zi,j中在本地及卸载计算的子任务量。

1) 本地计算

2) 卸载计算

卸载计算时延包括传输时延、计算时延和回传时延，因任务完成结果的大小远小于任务的大小，并且考虑到传输的下行（回传）速度远大于上行（传输）速度，所以本文忽略结果回传的时延大小[22,26]，仅考虑上行传输时延和计算时延两部分的影响。

协同节点mi,j的卸载计算时延为

本文研究的是非时延敏感型任务的协同计算，并考虑资源竞争的公平性，宿主车辆使用单信道进行任务串行卸载，同时为提高用户服务质量及无线资源的利用率、最小化系统时延，设计各协同节点接受任务后分布式执行。在卸载过程中，上行传输时间与执行时间存在一段重叠时间。因此卸载部分所用的时间取决于所有协同节点上传时延之和，再加最后被卸载协同节点的计算时延，即

2.5 问题形成

车联网中利用MEC 进行卸载计算，为提高通信及计算资源的利用率，期望最小化任务卸载的计算时延。但任务卸载计算期间，网络拓扑结构及信道质量因车辆的移动发生变化。因此，需预测车辆轨迹，选择时延容限内可用的协同节点，并确定拆分任务方案、卸载节点及任务卸载顺序。需解决的串行卸载、并行计算问题为

因为任务在本地和协同节点分布式执行，所以任务执行总时长取决于本地或协同节点任务执行时长的较大值。约束条件1C 表示任务在本地和协同节点分布式执行的约束边界；C2表示在任务执行期内vi到mi,j之间的相对距离小于或等于通信范围R；C3表示本地和卸载计算任务量之和等于总任务量；C4表示当前协同节点mi,j执行卸载任务的计算时延必须小于还未分配计算任务的协同卸载计算时延之和，其目的在于保证最后一个协同节点将子任务的计算结果回传到宿主车辆后，其余协同节点的计算结果均已完成回传。

3 算法设计

为了解决式(8)描述的优化问题，本文提出了一种协同分布式卸载-SQP 策略（CDOS-SQP,cooperative distributed offloading strategy-SQP）。在CDOS-SQP 中，分别提出了一种基于博弈论的卸载策略和基于SQP 算法[27]的任务分配方法，前者确定计算任务的卸载策略集Ai，而后者根据Ai确定任务不等拆分集iD。

3.1 基于博弈论的卸载机制

本节确定宿主车辆协同卸载时可用的mi,j，可通过卸载顺序集Qi,j获得协同策略集Ai来解决此问题。

在宿主车辆和协同节点的不断移动下，确定车辆vi为宿主车辆时的协同节点集Mi的准则是：在任务执行期内协同车辆始终处于宿主车辆的通信范围R内。本文应用博弈论中的重复剔除严格劣战略来获得Mi。

使用博弈论中的重复剔除严格劣战略，将t+tΔ 时刻车辆间的距离大于通信范围R定义为劣战略，终止条件为此时刻集合Mi中不包含劣战略。从而确定从t时刻到时刻始终处于R范围内的协同节点集Mi。下面使用博弈论中的纳什均衡来确定最优卸载顺序集

首先，定义mi,j的为宿主车辆vi卸载到的上传时延及在mi,j的计算时延之和，即

然后，使用博弈论中的纳什均衡来确定协同节点执行任务的卸载顺序。策略博弈[28]Γ涉及3 个要素，分别为参与者Mi、策略Qi以及效用函数Ui，具体说明如下。

1) 参与者。宿主车辆vi的n+1 个参与博弈的协同节点集Mi。

3) 效用函数。当vi的协同节点集Mi选择其串行卸载顺序集为Qi,j时的代价函数为定义如式(11)所示。每个协同节点都希望选择最优卸载顺序获得最大效用。

纳什均衡是指博弈中每个参与者都确信在其他参与者策略给定的情况下，自己选择了最优策略，从而使自己效用最大化。具体描述介绍如下。

算法1使用基于博弈论的卸载决策求解卸载策略集Ai

3.2 基于SQP 算法的任务分配

本节研究协同卸载下任务不等拆分集iD。现已通过卸载机制计算出Ai，已知式(8)中的约束条件C2仅影响策略集合Ai，则在本节计算需确立集合Di中任务的不等拆分比例，使任务执行时延Tvec最小化时不考虑约束条件C2。由于集合Di中任务可在本地和协同节点并行计算，因此将式(8)转化为本地和卸载这两类并行执行时间差值ΔTvec最小化问题，即

因为协同策略集Ai中有多个协同节点，所以任务不等拆分时按照协同节点数将其拆分成多份不等任务，即式(12)的优化问题可描述为带约束条件高维非线性优化函数问题。SQP 算法是求解此类最有效的优化算法之一，具有收敛性较好、边界搜索能力强、计算效率高等优点。本文采用SQP 算法求解式(12)的优化目标问题。

优化问题的数学模型简化为

其中，X为Rn中的一个非空多面体子集，即任务不等拆分集Di；ΔTvec(X)为优化目标函数，ΔTvec越接近0，分布式执行程度越高，Tvec越小；约束条件中，优化变量X取值范围的最大值为，最小值为0；h(X)为式(12)中C2描述的等式约束；g(X)为式(12)中C3描述的不等式约束；Rn表示数值取自实数空间，因此可将式(12)中的优化目标函数问题转化成求解式(13)，拉格朗日函数为

其中，1λ和2λ为约束函数的加权因子。

在kX点根据二阶泰勒公式近似展开为

其中，Sk为优化问题的搜索方向；[B] 为拟牛顿法近似构造的海塞矩阵，符号∇为梯度。拉格朗日函数的一阶导数为

函数g(X)在Xk点展开的二阶泰勒近似式为

活动三：寻找能量传递的规律。教师引导学生结合书本102页的知识，用彩色木棒标识出主图中能量的流动途径。此部分在高中会详细学习，为了降低难度，教师提供下列提示：

等式约束h(X)=0在Xk点展开的二阶泰勒近似式为

将式(15)～式(18)联合计算代入式(12)，经过整理得二次规划子问题为

求解上述二次规划子问题[29]，得到搜索方向Sk，沿搜索方向进行一维搜索，∂k为第k次搜索的下降方向Sk的最优步长，利用Wolfe 步长规则获取，按照式(20)进行迭代更新，最终得到原问题的最优解为

其中，[B] 为Lagrange 函数的Hessian 矩阵正定拟牛顿近似，并通过稠密半定牛顿近似法 BFGS（Broyden-Fletcher-Goldfarb-Shanno）进行计算，作为不断更新的校正矩阵，搜索方向迭代更新矩阵Bk是的近似，更新式为

其中，Bk为n阶对称正定矩阵。

本文使用SQP 算法，利用拟牛顿法（变尺度法）来近似构造海塞（Hessian）矩阵[B]，以建立二次规划子问题式(19)，又称约束变尺度法。通过求解二次规划子问题得到迭代的搜索方向Sk，沿搜索方向进行一维搜索，找到迭代的步长 ∂k，利用式(21)更新修正Bk+1，最后按照迭代式(20)最终得到问题的最优解Di，式(14)～式(21)为SQP的一般方法。伪代码如算法2 所示。

算法2基于SQP 算法求解任务不等拆分集Di

4 仿真结果及性能分析

本节将评估所提算法在车辆移动下，通过SQP算法将任务不等拆分后在分布式协同执行下的性能。使用各种度量来评估性能，如系统总时延、迭代次数，本文还研究了算法在不同参数设置下性能的表现。

4.1 仿真设置

本文采用V2X多节点分布式卸载策略，定义的道路场景如图1 所示。在车辆数一定的情况下，道路上车辆服从泊松分布，主要实验参数如表2 所示。为了获得方法的一般性能，本文采用蒙特卡罗方法进行了1 000 次仿真，获得平均性能以衡量方法的性能。车辆在直道上行驶的最大速度符合高速公路最大安全速度及车辆间安全行驶速度的规定，初始速度随机在60 km/h 至最大速度之间选择，并在单次仿真过程中保持不变。后述实验过程中在没有特殊说明情况下，均采用表2 中实验参数[30]。

表2 主要实验参数

4.2 仿真结果及分析

本节说明使用上述及本文所提协同卸载模型，分别改变任务量、上传功率、车辆密度和车辆初始速度范围，获得系统总时延，比较分析CDOS-SQP的优越性。

车辆总数N固定为25 辆，任务量与系统时延关系如图2 所示。随着计算任务量增加，本文所提CDOS-SQP的系统时延均低于对比策略。在任务量最大时，CDOS-SQP 策略系统时延相对最劣对比策略减少67%，相对最优对比策略减少8%。当计算任务量较大时，CDOS-SQP的系统时延显著优于对比策略，并且随着计算任务量的增加，CDOS-SQP增长速度相比其他策略较缓。造成上述结果的原因是，随着计算任务量的不断增加，系统的最优策略会倾向于在边缘侧和本地联合计算。而CDOS-SQP 相比对比策略可选择协同节点数最多，因此CDOS-SQP的优势随着计算任务量的增加更加明显。

图2 任务量与系统时延关系

计算任务量固定为50 MB，上传功率与系统时延关系如图3 所示。从图3 中可以看出，策略只需在本地计算，所以上传功率对的系统时延大小并无影响，而其余策略的任务卸载执行时延随着上传功率的增大而减小。这是因为宿主车辆上传功率增加会提高信噪比，从而增加信道容量，使采用边缘卸载的策略上传时延减小。同时CDOS-SQP 相比对比策略可用的协同节点数最多，且多协同节点采用分布式卸载策略并计算任务，其系统时延是最小的。通过实验对比可知，本文策略优于对比策略。

图3 上传功率与系统时延关系

相同计算任务下车辆密度的变化对系统时延的影响如图4 所示。从图4 可知，除外，其余策略随着车辆密度的增加，系统时延不断减小。造成上述现象的原因是：策略任务仅在本地执行，车辆密度的变化对其没有影响；而在其他卸载策略中，随着车辆密度的不断增大，可用的协同节点也随着增多，由式(1)～式(6)可知，节点间欧氏距离越小，上传时延也将越小，因此随车密度增加，系统总时延减少。而CDOS-SQP 可用的协同节点最多，因此表现最优。

图4 车辆密度与系统时延关系

车辆密度为20 辆，总任务量为50 MB，车辆初始速度变化范围与系统时延的关系如图5 所示。结果表明，随着初始速度变化范围的增加，计算任务的系统时延不断增大。从图5 中可看出，车辆的运动速度对没有产生影响，而对的结果会产生较大的波动。因为当车辆初始速度变化范围越大时，宿主车辆与协同节点的连通时间将越短，使可用的协同节点数也将越少。所以对于和算法而言，全部任务只进行卸载计算影响最明显。CDOS-SQP 性能最优的原因是，同时采用本地和协同节点分布式执行，并且可利用多协同节点进行并行计算执行。

图5 车辆初始速度变化范围与时延关系

图6给出了不同参数条件下迭代次数与收敛性的变化关系，展示了SQP 算法在不同参数下解决式(13)所示优化问题的迭代次数。通过图6 可知，当迭代34 次后实验结果趋于平稳，即趋于目标函数的最优解。随着迭代次数的增加，SQP 算法得到目标函数的值越来越接近满足约束条件的最优解。这表明SQP 算法解决式(13)所示优化问题，具有迭代次数较少、收敛性较好的优点。

图6 迭代次数与收敛性的变化关系

5 结束语

本文对可拆分任务的V2X多节点分布式卸载策略进行研究。考虑车辆行驶轨迹和最大时延约束，建立了基于博弈论的卸载策略和基于SQP算法的任务分配模型。利用博弈论中的重复剔除严格劣战略和纳什均衡确定出协同策略集；将原问题转换为带约束的高维非线性优化问题，根据SQP 算法将该问题转换为求解二次规划子问题，利用拉格朗日和BFGS 方法得到最优解，并分析了算法的收敛性。仿真结果表明，本文所提CDOS-SQP 具有较好的收敛性和优越性。下一步的工作将研究更普遍的道路结构（如弯道、十字路口等多结构复杂道路场景）和考虑更精准的行驶轨迹预测的协同卸载问题。