C-V2X车联网中基于模拟退火算法的任务卸载与资源分配

李智，薛建彬

（兰州理工大学 计算机与通信学院，兰州 730050）

0 引言

车联网（Internet of Vehicles，IoV）［1-3］技术是智能交通系统发展的主要支撑技术。IoV 技术以网联车辆为移动感知对象终端，在通信网络中实现多系统间交互，感知道路交通实时状况，使智能交通平台对道路和车辆进行全程实时控制，从而提高交通效率和交通安全性。由于车联网无线通信环境差且网联车辆自身资源受限，所以在传输与处理网联车辆产生具有可分时延敏感特点的大数据流量计算任务过程中，带来了时延抖动、计算能耗与通信系统开销大等问题，目前已被相关专业技术人员密切关注。

为解决上述问题，将具备移动边缘计算（Mobile Edge Computing，MEC）［4-6］功能的边缘MEC 服务器，以C-RAN［7］方式部署在基站附近，可在网络边缘对大数据流量计算任务进行快速卸载和计算，从而降低通信时延、计算能耗及系统开销。目前，基于MEC 的任务卸载和资源分配问题，研究人员纷纷提出了不同观点。刘继军等［8］提出了资源分配与基于博弈论的任务卸载决策联合优化策略，提高了系统总增益。以降低通信时延为目的，谭友钰等［9-10］分别提出了多边缘MEC 服务器协作资源分配方案，与基于MEC 高能效任务卸载决策。Tran等［11］提出了多MEC 服务器启发式联合任务卸载和资源分配策略，从而提高了系统效用。Nguyen等［12］建立了数据冗余模型，充分利用MEC 服务器上的空闲资源对任务进行计算和分配，从而减少了网络带宽消耗。余翔等［13］针对高速公路场景，提出了一种基于行车方向，以车辆为节点进行车辆与车辆、人、网络等间进行通信的环境中，每个车辆根据信道感知结果独立选择传输资源，并保留所选资源供今后使用的算法，对网络资源进行合理分配，提高了资源分组接收率。薛建彬等［14］通过分析任务卸载系统中能量收集状态及用户功率分配状态，提出了一种基于能量收集的系统能效优化方案，提升了系统中用户的能量效率。吴振铨等［15］为解决任务调度问题，提出了一种启发式算法，采用移动设备局部最优卸载策略，降低任务执行延迟。杨天等［16］考虑二进制任务卸载模型，通过联合优化任务执行位置，对基于精英选择策略的遗传算法做出了部分改进，设计了联合卸载决策与资源分配算法，降低了系统成本。Chen等［17］采用博弈论方法，提出了一种基于MEC 的多用户任务计算卸载方案，降低了任务卸载时延。路亚［18］提出一种多移动边缘计算服务器启发式联合任务卸载和资源分配策略，从而最大化系统效用。Hamzah等［19］提出了一种位置感知任务加载策略，减少了任务处理时间及网络时延。以降低系统开销为目的，张海波等［20］提出一种基于Q 学习算法的任务卸载策略；闫伟等［21］提出一种基于自适应遗传算法的任务卸载和资源分配方案。

上述文献关于任务卸载和资源分配问题，研究人员根据不同优化目标，分别提出了不同解决方案，优化了时延、能耗、带宽等指标。但现有研究内容均考虑二进制卸载模型，未考虑IoV 通信环境中实际情况，且任务卸载决策是个多目标优化问题。目前针对任务卸载低时延、低计算能耗和最小化系统开销等要求，现有方案优化效果不佳，应用上还需继续优化。本文设计以蜂窝通信（LTE-V-Cell）［22］为主的LTE-V2X［23-26］车联网通信环境中任务按比例卸载的通信模型，利用模拟退火算法（Simulated Annealing Algorithm，SAA）确定最优卸载比例因子。在上述过程中，将系统开销最小化问题转化为功率和计算资源分配凸优化问题，并用拉格朗日乘子法获取最优解，进一步优化网络系统，从而降低任务传输时延、计算能耗及系统开销，进而提高C-V2X（Cellular Vehicle to Everything）［27］车联网中的通信效率。

1 系统模型

本文建立了LTE-V-Cell 通信模式的C-V2X 车联网通信系统模型，如图1 所示。模型中的设备包含：车辆、基站、路侧单元（Road Side Unit，RSU）以及边缘MEC 服务器。

首先，本文系统模型中各设备的作用介绍如下：

1）基站。基站具备无线接入控制功能，可对空中接口Uu 进行合理管理，同时可控制资源分配与调度。

2）边缘MEC 服务器。边缘MEC 服务器以C-RAN 方式部署在基站附近，将基带资源、硬件协作化等进行集中化处理，实现协作式车辆与实时云计算结构的网络边缘处理模式，降低网络通信时延。

3）RSU 和车辆。RSU 处于基站和车辆之间，车辆可和RSU 进行通信。RSU 将任务传输到边缘MEC 服务器上进行任务卸载和计算处理，即RSU 为车辆和边缘MEC 服务器间数据通信提供全方位服务。

其次，将计算任务初步建模介绍如下：本文定义在道路上均匀部署了m个边缘MEC 服务器和n个车辆，所有边缘MEC 服务器部署集合可表示为M={Mm|m∈N+}，车辆节点部署集合可表示为N={Vn|n∈N+}。假设所有车辆均服从泊松分布，则网络通信系统中第i个边缘服务器下的第j个车辆，每次在某时刻可产生一个可分割待处理的密集型任务，将其表示为：其中，为车辆产生的任务数据量；为计算任务时CPU 周期数；为处理任务时可容忍的最大约束时延；为任务的价值量，任务的重要程度定义为值越大说明任务越重要。

最后，定义任务卸载比例因子如下：考虑将任务部分卸载到本地、部分卸载到边缘MEC 服务器上，形成任务本地和边缘MEC 服务器协同卸载模型。定义任务卸载到边缘MEC服务器上的比例因子为；任务卸载到本地的比例因子为1 -，且0 ≤≤1。

2 计算模型

本文将任务卸载方式分成两个部分：其一，任务卸载到本地；其二，任务卸载到边缘MEC 服务器上。

2.1 本地卸载时延与能耗计算模型

其中：k为能量常量因子，由车辆自身芯片结构决定大小。

2.2 边缘MEC服务器卸载时延与能耗计算模型

任务经边缘MEC 服务器卸载需经过三个步骤：1）任务上传至边缘MEC 服务器；2）任务在边缘MEC 服务器上执行计算；3）边缘MEC 服务器将任务计算结果回传给车辆。在此过程中产生相应的任务传输时延、任务执行计算时延、任务回传时延。但由于任务经过边缘MEC 服务器一系列卸载计算处理后，将当时结果回传给车辆的任务数据量将远远小于原始任务数据量，因此忽略下行链路任务的回传时延。下面将对任务卸载到边缘MEC 服务器卸载的时延与能耗计算模型进行详细介绍。

基于时分多址接入（Time-Division Multiple Access，TDMA）或正交频分多址接入（Orthogonal Frequency Division Multiple Access，OFDMA）的多用户MEC 系统，设计控制卸载数据大小和时间或子信道分配的最佳策略，可最小化卸载时延与系统能耗［28-29］。当车辆节点和RSU 进行通信时，本文采用OFDMA 的多用户MEC 系统，即每个车辆节点可在通信系统中与RSU 通过独立信道进行信息传输，则任务卸载在边缘MEC 服务器上的传输速率rMi，Vj可根据香农公式定义为：

其中：fMi，Vj为边缘MEC 服务器分配给车辆的计算资源。

3 问题描述

通过上述分析，考虑到C-V2X 车联网中诸多应用对时延、计算能耗及系统开销要求非常高，本文利用时延权衡因子ζ和能耗权衡因子1 -ζ形成系统开销最小化目标，使车辆在最大网络带宽限度内进行任务卸载和资源分配。将系统开销f(C)定义为任务卸载到本地的开销与任务卸载到边缘MEC 服务器的开销之和。

其中，任务卸载到本地的开销和任务卸载到边缘MEC服务器开销分别表示为：

本文采用组合优化技术优化系统开销最小化目标，则目标函数表示为：

式（10）表示给定任务卸载比例因子的取值范围；式（11）表示车辆到边缘MEC 服务器上的传输功率不能超过车辆最大传输功率；式（12）表示任务卸载到边缘MEC 服务器上可分配资源为非负数；式（13）表示给任务卸载分配的可计算资源大小不能超过边缘MEC 服务器自身资源；式（14）表示所有车辆通信带宽之和不可超过网络带宽B。

4 优化模型

本文目标函数优化问题属于卸载比例因子、传输功率、计算资源分配多个目标优化的困难问题，求解难度非常大，因此将系统开销最小化问题进行拆分并逐一求解。由于任务部分卸载和二进制卸载模型相比，前者需要考虑子任务先后处理的顺序问题，所以任务部分卸载时需设置任务处理优先程度，对于优先程度较高的任务优先处理，对于优先程度较低或不重要的任务，可上传至蜂窝网络云平台进行远处理。

4.1 任务处理优先程度

由于不同车辆用户需求不同，从而产生的计算任务属性也大不相同，且边缘MEC 服务器自身资源受限。在同一时刻，某一边缘MEC 服务器不能在该协同域内，对所有车辆节点产生的可分时延敏感型任务同时进行卸载计算。

针对可分时延敏感型任务需求，本文用任务处理优先程度来确定车辆节点产生的计算任务是否为可分时延敏感型计算任务。针对任务处理优先程度，设置了任务处理优先程度阈值，用来表示。其中，定义可分时延敏感型计算任务处理优先程度大于等于该阈值，可进行本地和边缘协同卸载计算；而小于该阈值的计算任务视为任务处理优先程度低或不重要任务，可将其上传至蜂窝网络云服务器中进行处理，避免网络通信拥堵。该过程将在SAA 伪代码中体现。

上述任务优先程度定义为在某时刻，受任务处理最大可容忍约束时延条件限制，任务优先处理的程度。本文用任务重要程度和任务处理最大可容忍约束时延来定义任务处理优先程度，则构建任务处理优先程度的数学模型为：

其中：ϕ为任务重要程度的权衡因子；1 -ϕ为最大约束时延的权衡因子，且ϕ∈[0，1]，可通过熵值法求解。

4.2 基于模拟退火算法的任务卸载

根据任务处理优先程度，将优先卸载的任务，按照一定比例卸载至本地和边缘MEC 服务器进行任务卸载处理；同时优化卸载比例因子，使得任务按照最优卸载比例因子卸载到本地和边缘MEC 服务器。本文采用模拟退火算法优化卸载比例因子。该算法的原理是模拟固体从加热状态到冷却整个过程中状态的变化情况，从而解决与固体物质退火过程相似的一般组合优化问题。随着温度不断降低，结合车辆泊松分布的概率，在最优卸载比例因子解空间中随机搜索系统开销最小化的全局卸载比例因子最优解，从而解决本文方案中的困难问题。该算法只与初始最高温度、最小温度以及退火次数有关。

模拟退火算法实现步骤如下：

1）输入初始化参数。参数包括计算迭代次数、初始最高温度以及终止温度等。将初始温度T=T0设置为一个较高的值，一般情况设置为1 000，且呈衰减状态。内循环迭代次数最大一般设置为50。随机给定一个初始解，同时也是算法迭代的起点，最终计算目标函数值

2）内部循环迭代次数依次递增，如Lk=1，2，…，50，重复第3）步到第5）步。

其中，第5）步中的终止条件一般情况下会定义为：当连续若干个新解都没有被接受时，则算法终止。通过以上算法步骤可以看出，此过程是基于Metropolis 准则在某个最佳温度下搜索最优解，从理论上看，要经过无数次迭代才搜索出最优解，但实际上定义一个最大可迭代次数即可搜索出最优解。

4.3 资源分配

为了保证任务经过边缘MEC 服务器成功卸载计算，且在通信过程中不会发生信息中断现象，车辆任务卸载时延需小于或等于网联车辆节点在当前所属协同域内的停留时间。其中，网联车辆节点在当前所属协同域内的停留时间由车辆移动速度来决定。在这样的条件限制下，可获得最佳功率和计算资源。

在资源分配问题中，由于车辆传输功率和计算资源之间不存在相互约束因子，因而不能进行联合优化，因此可将资源分配问题拆分成最优任务卸载比例因子下对传输功率和计算资源各自优化的两个问题。

4.3.1 功率优化

通过对资源分配问题进行分解，可将式（17）中功率优化问题表示为：

通过对传输功率最小化函数凸优化分析，可将传输功率优化目标函数重新改写：

此时新优化目标函数式（20）为凸优化问题，用拉格朗日乘子法进行求解。拉格朗日乘子法可将难解的NP-hard 问题中相关约束条件吸收到目标函数中去，使得目标函数保持线性关系并求最优解。

根据式（20）凸优化问题构建拉格朗日函数为：

其中：β为目标函数约束条件式（11）中相对应的拉格朗日乘子，且β≥0。

利用KKT（Karush-Kuhn-Tucker）条件求解式（21）在处取极值时的充分必要条件，可得：

根据KKT 条件可得最优解为：

4.3.2 计算资源优化

通过对资源分配问题进行分解，将式（17）中计算资源优化问题表示为：

根据式（25）凸优化问题构建该优化函数的拉格朗日函数为：

其中：λ为目标函数约束条件式（12）中相对应的拉格朗日乘子；而μ是目标函数约束条件式（13）中相对应的拉格朗日乘子，且λ≥0，μ≥0。

利用KKT 条件求解式（25）在处取极值时的充分必要条件，求得最优解，Vj为：

4.4 SAA伪代码

5 仿真实验与结果分析

考虑1 个RSU 和1 个边缘MEC 服务器可形成1 个协同域，则多个RSU、边缘MEC 服务器与多个车辆节点可构成多个协同域覆盖道路通信场景。在该场景中某时刻下，一个车辆节点可产生一个计算任务，因此任务数和车辆节点数目相同。为了简化仿真，将车辆节点数目设定为40，而将边缘MEC 服务器和RSU 各设定为5个，从而搭建MEC 仿真场景。任务数据量为（400～1 200）KB；任务计算CPU 周期数为（0.2～1.0）GHz；车辆本地卸载计算能力为1 GHz；能量系数k=1 × 10-26；网络带宽B为20 MHz；链路增益由路径损耗生成，如下所示：

其中：噪声功率σ2为-100 dBm；边缘MEC 服务器自身资源fMEC为20 GHz；时延因子ζ为0.2；初始温度T0为1 000°，温度衰减系数α为0.95，衰减系数值越大降温越慢，导致迭代次数增加但会找到全局最优解。

图8 为迭代次数与系统开销之间的关系图。由图8 可知，本文所提模拟退火算法和基于Q-学习卸载策略均可经过多次迭代，达到系统开销最小化目标。其中，基于Q-学习卸载策略在迭代过程中存在局部最优解，使系统开销收敛速度较慢，且最终优化目标效果不佳。本文算法经过多次迭代可迅速达到系统开销最小化目标，且收敛速度快。由图8 可得基于Q-学习卸载策略和本文算法的平均系统开销分别为：196.567 0、76.741 6。综上所述可得：1）本文算法比基于Q-学习卸载策略的系统开销降低了60.96%；2）相较于基于Q-学习卸载策略，本文算法可更快实现LTE-V-Cell 车联网通信系统中系统开销最小化目标，本文算法可加速收敛且优化效果最佳。

6 结语

智能交通成为当今智慧城市交通发展的关键技术，未来汽车工业在智慧城市的推动发展中，对网联车辆通信方面高带宽、低时延、高可靠等要求会越来越高，这些要求是目前MEC 技术与车联网技术融合发展的关键研究目标。由于本文方案考虑到车联网中实际情况，采用任务比例卸载计算模型，利用搜索全局最优解的模拟退火算法，将任务按照最佳比例协同卸载在本地和边缘MEC 服务器，同时实现在LTE-V-Cell 车联网通信系统中，对资源统一调度与分配，最小化时延、计算能耗及系统开销，进而实现时延敏感型大数据流量的快速处理、共享和交互，给车辆用户提供最佳的服务体验，可有效降低事故发生，提高交通效率，确保本文研究与现实车联网环境中的运行情况更加贴切，从而达到更高的资源利用，综上所述本文方案最佳、最有效。下一步将考虑现实环境中，若在RSU 覆盖范围之外存在计算能力更强的车辆节点时，大数据流量任务还会进行细分，则车辆节点间可进行协同通信；同时也将考虑在任务卸载过程中，会存在多协同域间通信覆盖或迁移现象，在下一步的研究中将引入网络切换技术，实现更高的技术实用性。