负载约束的C-V2X 车辆缓存节点选择算法

（福建师范大学光电与信息工程学院，福建 福州 350007）

1 引言

随着现代交通和科技的发展，我国汽车行业的需求量日益增长，V2X（vehicle to everything）受到工业界和学术界的广泛关注。高效的V2X 系统开发基于大量可靠功能的传感器，通过在车辆、行人和道路基础设施之间交换关键信息，提供增强的环境感知[1]。为充分利用蜂窝移动通信网络的技术优势，C-V2X（celluar vehicle to everything）应运而生，将车辆与一切事物连接，并向NR-V2X（new radio vehicle to everything）演进，在高度动态的车辆拓扑环境下，实现低时延、高可靠的数据传输。

V2X 融合了车辆和基站之间的蜂窝通信以及车辆之间的直通通信，2 种模式相互补充，实现基站和车辆之间的负载均衡[2]。若将车辆节点作为缓存节点，可通过车辆之间的连接为其他车辆提供数据服务，以降低数据响应时延，减轻基站的负荷，减少因基站切换引起的开销，优化基站通信资源分配。在C-V2X 的演进中，3GPP R14 定义了针对车载通信的mode-3 和mode-4，这2 种模式都支持车辆间直通通信，区别在于mode-3 通过蜂窝网络集中式分配无线资源，而mode-4 由车辆分布式自主选择无线资源。相比之下，mode-3 中基站能获取更完整的网络状态和不同车辆对资源的需求信息，更有效地利用无线资源[3]，因此本文主要研究C-V2X mode-3 下的车辆缓存节点选择问题。城市环境C-V2X 中高度动态的车辆拓扑和车辆负载约束使车辆缓存节点的选择面临挑战。1) 增加缓存节点的覆盖面，则更多的车辆可通过V2V（vehicle to vehicle）从缓存节点获取文件；2) 减少缓存节点数量，以减少指派缓存节点的控制开销和预置缓存文件的带宽开销，并且过多的缓存节点将加剧信道竞争；3) 降低应答冗余，即减少缓存节点对于同一请求的重复应答，以节省带宽开销。因此，合适的缓存节点选择成了亟须解决的问题。

由于车联网本身具有快速的拓扑变化，且车辆节点服务能力有限，现有研究较少利用车辆可获取的移动轨迹信息对链路变化进行预判，同时忽视了节点的服务能力上限以及缓存节点的覆盖性等方面，故车联网中节点筛选的研究尚不完善。本文提出基于负载约束的C-V2X 车辆缓存节点选择算法，主要贡献有以下几个方面。

1) 合理定义节点状态，即状态未定节点、服务邻居节点以及缓存节点，为缓存节点选择奠定重要基础。其中，状态未定节点为初始状态，通过所提算法将所有的状态未定节点转化为服务邻居节点或缓存节点，实现了节点间的无重叠全覆盖；服务邻居节点有别于传统邻居节点的定义，是缓存节点根据每个周期可服务的节点个数上限择优筛选出的邻居节点的子集。

2) 定义链路稳定性度量，并构建预测权重邻接矩阵，从微观层面精确描述未来周期的拓扑关系，并以此筛选缓存节点，使缓存节点及其服务邻居节点的选择更加合理。

3) 根据节点的服务能力的局限性，将节点一个周期内可服务的节点个数上限作为负载约束，提出了在给定拓扑下，无重叠全覆盖的最少缓存节点及其服务邻居节点的选择算法。该算法改进传统的最小支配集筛选算法，结合C-V2X 场景中节点负载约束，以匹配实际节点响应能力，提升了算法的实用性，同时实现了不重叠全覆盖，优化了系统带宽利用率。

4) 将所提算法与穷举算法计算得到的全局最优结果对比，经大量仿真，统计结果表明，所提算法在缓存节点个数和簇平均链路权重均值方面都接近全局最优结果。

5) 将所提算法与k-means 无监督聚类算法、最大连接度算法和CCMP 算法进行对比。所提算法在缓存节点及其服务邻居节点的选择方面更加合理，实现了无重叠全覆盖，请求应答率、重复应答率、缓存源应答次数均值等性能指标均优于对比算法，并且重复应答率恒为零，请求应答率可达理论上界。

2 相关工作

在C-V2X 场景下，V2X 的通信效率及稳定性至关重要，通过V2V 通信可以使整个网络中的系统负荷得到合理的分配，自适应地快速实现车联网业务的高可靠低时延通信[2]。基于D2D（device to device）的缓存策略已经被证明能有效提升网络性能[4-7]，借助于V2V 的C-V2X 车辆缓存也将有利于车辆节点间数据共享，其中车辆缓存节点的选择至关重要。

车辆缓存节点为其通信范围内的节点提供文件共享服务，也可广义地视为形成车辆簇，以车辆缓存节点为簇头，以被服务节点为簇成员。因此，除缓存节点筛选算法外，成簇以及簇头选择算法可为车辆缓存节点的选择提供重要参考。

利用节点属性构建节点度量值，再通过门限、最值等筛选条件求得簇头并成簇是常见的算法思路。这在无线传感网等节点固定的网络[8-10]以及车联网等节点移动的网络[11-18]中均得到广泛应用。在无线传感网中，由于节点能量有限，节点的剩余能量是着重考虑的因素。Ray 等[8]以节点剩余能量、节点到基站的距离、连续轮数为参数构建节点度量，度量值小于所设定门限的节点为簇头。Qiao 等[9]将节点剩余能量和节点到数据采集中心的距离整合为竞争半径，将该值最大的节点作为簇头，其他节点就近成簇。Saloni 等[10]将区域划分为网格，网格中选择剩余能量最大的节点作为每轮的簇头。多因素加权获得度量值并与门限比较得到簇头并成簇的方法值得借鉴，但是节点移动的网络中节点拓扑结构变化导致所需要考虑的因素有别于固定网络。Gao 等[11]将中断容忍网中每个节点到其他节点可达率的平均概率作为度量值，然后选择度量值排名靠前的若干节点作为簇头。车联网中移动性信息是关键因素之一，尤其是速度。Rawashdeh 等[12]考虑了车联网中节点的速度、位置、节点度和方向等移动信息，将它们整合为适应性度量值，从而选择该值最大的节点成为簇头，并将其通信范围内速度差小于某个门限的节点成簇。Daknou 等[13]以速度最慢的节点作为成簇发起点，将高速公路分区，每个簇中节点以与邻居的距离和速度差作为参数，加权得到适应度度量，度量值最小的节点作为簇头。Farooq等[14]令不同车道的车辆各自成簇，同一车道速度相近的车辆成簇，速度最接近设定门限的节点作为簇头。速度关系本质上体现的是节点间的连接关系，此外，还可以根据节点密度划分出热区，并选择在热区的平均逗留时间更长的节点作为缓存节点[15]，也可以直接研究节点连接关系，并综合其他因素完成簇头筛选和成簇。Alsuhli 等[16]综合考虑节点与邻居的平均距离、速度差、连接度、信道质量、链路持续时间并归一化后加权得到度量值，该度量值越大，越有资格成为簇头，同时还选择了备用簇头，簇头收到入簇请求后，若其簇成员数目未达上限则纳入簇。Qi 等[17]通过分割道路完成初始分簇，只有当两节点链路的持续时间超过给定门限时，才记为有效链路；根据有效链路统计节点的连接度，在连接度大于门限的节点中选择距离RSU（road side unit）最近的节点作为簇头。Cheng 等[18]通过连接预测评估节点间拓扑关系，若节点的邻居节点密度大于门限，则将其设置为核心车辆节点。

尽管车联网拓扑高度动态，但车辆节点之间具有明显的跟随特性，在道路约束下的车辆轨迹也存在规律性，这些都体现在更本质的微观邻接关系中。因此，本文也从节点的连接关系入手，与上述文献不同的是，将节点的属性转化为更本质的链路属性，构建链路稳定性度量，并且采用基于贪婪思想的迭代算法筛选簇头并成簇，而非使用门限或最值选择簇头。这是因为车联网具有高度动态的环境，节点间相对关系复杂多变，难以用绝对门限清晰划分度量值的优劣。

利用优化算法逐步得到优化的节点作为簇头并成簇也是行之有效的手段，还可避免设定门限的缺陷。Shin 等[19]将节点的剩余能量和连接度整合为度量flooding value，通过迭代交替地将节点的该度量值替换为最大和最小邻居度量值，收敛之后根据迭代过程中度量值的规律筛选簇头。针对VANET（vehicular ad-hoc network）动态环境，Fathian 等[20]提出了多目标数据包络分析聚类算法的数学聚类模型和蚁群算法的启发式聚类模型，聚类后将最靠近簇中心位置的节点作为簇头。Ahmad 等[21]引入博弈思想，综合考虑车辆的速度、位置、方向和LTE（long term evolution）链路质量等参数，提出合作利益感知聚类算法，以节点是否接受成为簇头作为策略，最大化整体利益并完成簇头筛选，同时采用轮值簇头机制提升公平性。采用节点集合覆盖理论的算法可以获得精简优化的簇头集合，例如，Liu 等[22]提出基于广义控制集和局部内容流行度的内容中心移动自组网协同缓存方案，根据连接度筛选簇头节点，并将给定多跳范围内的邻居节点纳为簇成员。Liu 等[23]提出基于最小顶点覆盖集理论的静态网络节点选择算法，通过社会化关系的协同缓存来确定缓存点，以解决车辆流动性带来的不连接问题。Li 等[24]考虑用户分布和流量负载的情况，构建了基站和用户之间的二部图，并通过求解最小支配集获得最优传输路径，基站被默认为簇头，与其连接的用户可视为簇成员。

在上述优化方法中，迭代运算是重要的组成部分，快速收敛并减少交互开销至关重要，并且若带宽有限且需要实现全覆盖，相较于其他优化方法，基于最小支配集的方法可以快速计算出簇头。但其缓存节点服务能力有限，每个周期只能服务有限数量的邻居节点，目前研究较少直接考虑该因素。因此，利用交通流规律以及拓扑邻接关系，实现缓存节点和服务邻居节点的筛选有待进一步研究。

针对以上问题，本文提出了基于负载约束的C-V2X 车辆缓存节点选择算法。该算法定义了链路稳定性度量以及3 种节点状态，充分利用车辆轨迹的可预测性，在预测未来周期权重邻接矩阵的基础上，以服务邻居节点上限作为负载约束，完成最小支配集筛选，以最少缓存节点不重叠地覆盖所有节点。所提算法对于C-V2X 的动态拓扑具有较强的自适应性和实效性，在请求应答、重复应答率以及缓存源平均响应次数方面具有显著优势，能有效提高车辆缓存节点的利用率，减轻基站负荷。

3 系统模型及问题描述

3.1 系统模型

本文研究城市环境的C-V2X 缓存文件传输场景，如图1 所示。该场景中，主干道交汇处形成岔路口，每条主干道为双向多车道。设一个通信半径为RB的基站覆盖该路口，其覆盖范围内车辆数为Nveh，总车辆集合为N={n1,n2,…,nNveh}。

图1 城市环境的C-V2X 缓存文件传输场景

假设车辆节点都具有相同的缓存空间，可容纳C个文件。车辆节点既可以发出请求，也可以作为请求响应者。假设车辆内都装有GPS 等定位设备，可以实时获取车辆的轨迹信息并上报给基站。在第t周期，第i∈{1,2,…,Nveh}辆车的轨迹信息定义为，其中，(,)为位置坐标，为速度。设车辆的通信半径为Rveh，每辆车可以从通信范围内的缓存节点获取文件，也可以从所归属的基站获取。

基站作为区域服务者，为覆盖区内车辆节点提供文件服务和资源控制管理，基站通信半径为RB。通过给基站配置存储设备和计算设备，可让基站具备缓存能力和边缘计算能力。基站采用3GPP R14 版本中设定的mode-3 模式管理车辆间通信的无线资源分配，以实现更高效的子载波利用率[3]。车辆节点在基站的集中控制下与缓存源节点通信，获取所需文件。同时，基站在缓存源节点的指派上借鉴底层的半持续调度（SPS,semi-persistent scheduling）机制，即在给定时间段内车辆节点由指定缓存源节点管辖，期间各子帧的数据获取均优先请求该指定缓存节点。这与底层的无线资源SPS 机制匹配，以优化数据分组传输效率。

3.2 问题描述

普通节点会先向自己所连接的缓存节点发起文件请求。当缓存节点已缓存相应文件时，则响应请求；否则用户经一跳或者多跳V2V 链路向基站发出该文件请求，由基站经回程链路获取数据后进行响应。通过回程链路响应将严重增加响应时延，并且城市场景下高密度交通流发出的大量文件请求将导致基站过载，无法同时响应过多文件请求。为了减少通过回程链路的文件响应时延并减轻基站负载，应使车辆节点的请求尽可能由周边车辆缓存节点提供响应，即提高车辆缓存节点的利用率。具体地，应提高车辆节点的请求应答，即提高当前周期所有车辆发送的文件请求中，能被缓存节点响应的请求的比例，该比例越大说明越多的请求能被周边缓存节点响应，对基站负载的分流作用越明显。请求应答比传统的缓存响应率更直接地体现了请求用户成功获取所需文件的效率。

缓存文件流行度估计及分配策略不在本文讨论范围内，设文件流行度服从Zipf 分布[6,25-26]，节点发出的请求也服从该分布，缓存节点缓存最流行的前C个文件[27]。将请求应答最大化问题转化为节点全覆盖问题，即当选择的缓存节点能够覆盖所有普通节点时，每个普通节点总在至少一个缓存节点的通信范围内。那么，从概率意义上，当缓存节点在其缓存空间C的约束下缓存最流行的C个文件时，将实现请求应答的最大化，其理论上限为Zipf 分布CDF（cumulative distribution function）中C对应的值。

针对节点全覆盖问题，在本文的系统中，假设基站作为区域服务者具有宏观调控的功能，可获取覆盖区域内所有车辆节点的轨迹信息。基站将根据第t周期车辆轨迹信息，预测第t+1 周期的车辆位置，从而生成预测权重邻接矩阵

其中，链路的权重表示第t+1 周期车辆节点i和j之间链路稳定性度量的值。

基站利用预测的Wt+1，采用缓存节点选择算法计算缓存节点集合Mt+1={m1,m2,…,mNM}，其节点个数为NM。为减少基站配置及管理缓存节点的开销，并且减少缓存节点之间信道竞争，应使满足最优性能时，选择的缓存节点个数最少，则目标函数为

对于任一缓存节点mk,k∈{1,2,…,NM}，在给定数据帧长和数据传输速率的条件下，其每个周期的服务能力有限，设最多只能响应Nmax个邻居节点的请求，则将该约束称为负载约束。因此，所研究的问题转化为负载约束下的节点全覆盖问题，即缓存节点mk将在其通信半径范围内所有节点中选择不多于Nmax个节点作为服务邻居节点。将缓存节点mk的q个服务邻居节点集合记为

这些缓存节点可以覆盖基站管辖范围内其他所有普通节点，即缓存节点集合t+1M 与所有缓存节点的服务邻居节点集合的并集等于N，表示为

为提高系统带宽利用率，应减少重复应答率。重复应答率即多个缓存节点重复响应同一请求的比例。因此，令每个普通节点只与一个缓存节点建立连接，以实现无重复响应，即一个普通节点在同一周期内对一份文件的请求不会同时被2 个以上的缓存节点响应。因此，所研究的问题进一步转化为在负载约束和无重叠覆盖约束下，以最少的缓存节点实现节点全覆盖问题，即任意2 个缓存节点mk和mu的邻居集合的交集为空，表示为

另外，每个缓存节点及其服务邻居节点构成一个簇，缓存节点为簇头，服务邻居节点为簇成员。为提高簇稳定性和传输可靠性，在确保每个普通节点能且仅能被一个缓存节点覆盖的前提下，每个缓存节点选择其覆盖范围内链路权重大的节点作为服务邻居节点。缓存节点选择的服务邻居节点应使簇平均链路权重最大化，因此，所研究的问题转化为在负载约束和无重叠覆盖约束下，以最少的缓存节点实现簇平均链路权重最大化的节点全覆盖问题。设缓存节点mk的最优邻居集合为，对应的簇平均链路权重为，则目标函数为

式(6)表示每个缓存节点应选择最优邻居，以使簇平均链路权重的期望最大化。

综上所述，可构建待优化的目标函数，如式(7)所示。

该优化问题具有NP-hard 性质，在高度动态的车辆拓扑环境下，为满足低时延的传输要求，求解最优解将导致算法复杂度和计算时延恶化，因此，本文借鉴贪婪思想，提出负载约束下的最小支配集算法，快速计算可行次优解。仿真表明，所提算法的缓存节点个数和簇平均链路权重接近穷举法计算的最优结果。

4 算法流程及关键步骤

以车辆节点轨迹信息为基础，以最小化缓存节点个数以及最大化簇平均链路权重的期望为目标，采用负载约束的最小支配集算法，实现车辆节点的全覆盖。首先，基站收集当前周期内所有节点的行驶信息，以预测得到所覆盖的范围内下一周期的拓扑；然后，定义链路稳定性度量，以构建预测权重邻接矩阵；最后，根据预测权重邻接矩阵实现下个周期的缓存节点选择。

4.1 链路稳定性度量

定义链路稳定性度量,∀i,j∈[1,Nveh]表示在第t周期车辆节点i和j之间归一化通信距离容差和归一化链路持续时间的加权和。在第t周期，设车辆节点i和j在相互的通信范围内且距离为，车辆节点的通信半径为Rveh，则通信距离容差为Rveh-，从而可得归一化通信距离容差为

其中，dmin表示在安全距离限制下的两车最小距离。该值越大说明两车距离越近，相同遮挡条件下的信道质量越好，并且在两车的车速均不变时，链路持续时间越长。当车间距大于或等于车辆通信半径时，两车通信距离容差均视为0，即无法通信。

设周期间隔为Δt，车辆节点i和j在第t周期中，将相互处于对方覆盖范围内的时间长度定义为链路持续时间，该值由轨迹预测确定[28]。由于链路持续时间每周期更新，当值大于周期间隔时，将链路持续时间的上限设为Δt，再将其对周期间隔进行归一化，得到归一化链路持续时间为

链路持续时间越长，说明两车的拓扑关系越稳定，但并不意味着两车之间的信道质量越好，链路稳定性还要考虑两车之间的传输距离、遮挡情况以及干扰等。本文着重研究缓存节点选择，将链路稳定性度量简化为归一化通信距离容差和归一化链路持续时间的加权和，即

其中，ρ∈[ 0,1]为加权因子。基站根据第t周期的轨迹信息完成第t+1 周期的轨迹预测并计算，以此作为链路权重，并根据式(1)得到Wt+1。

4.2 基于负载约束的最小支配集算法

针对预测权重邻接矩阵t1+W，定义3 种节点的状态，即状态未定节点、服务邻居节点以及缓存节点，分别对应状态标志位0、1、2，从而可构建第t+1 周期的节点标志位向量为

所有节点状态标志位均初始化为0，根据预测权重邻接矩阵计算每个节点连接状态未定节点的连接度，即该节点通信覆盖范围内连接的状态未定节点的个数。在服务邻居个数上限Nmax（即负载约束）下，综合考虑节点连接度和链路稳定性度量，筛选最少的缓存节点t+1M 构成最小支配集，并择优筛选各缓存节点的服务邻居节点，实现无重叠的全覆盖，并最大化簇平均链路权重均值，即最优化式(7)的目标函数。具体步骤如算法1 所示。

算法1基于负载约束的最小支配集算法

在上述算法中，与传统的连接度定义不同，算法中定义的连接度Zi（i∈{1,2,…,Nveh}）是指节点连接状态未定节点的个数。使用重新定义的连接度，可以避免不完全覆盖，并且算法执行过程中着重处理未被覆盖的节点，从而提高算法效率。

在缓存节点选择方面，优先考虑Zi=0 的孤立节点，将其设置为缓存节点，一方面可以获取自身所需的文件，另一方面还可以作为携带转发的锚点。其次，考虑Zi=1 的节点，因为这些节点的邻居节点有且仅有一个，借鉴传统最小支配集的构建规则，将其邻居节点置为缓存节点。若多个节点的连接度为1，则优先处理链路权重大的节点，因为这些节点能由邻居节点提供更稳定的数据传输，提高数据传输成功率。在没有Zi=0,1的节点时选择连接度最大的节点作为缓存节点，借鉴贪婪思想，最大程度地完成节点覆盖。

在服务邻居节点选择方面，由于数据帧大小有限，每个缓存节点同一个周期只能为Nmax个邻居节点提供服务。在筛选邻居节点的过程中，优先选择Zi较小的邻居节点是为了解决节点全覆盖性，因为Zi较大的邻居节点被其他缓存节点选择为服务邻居节点的可能性更大。考虑缓存节点与邻居节点链路权重在该邻居节点所有链路权重中的排序位次，是为了判断缓存节点对于该邻居节点的重要性以及链路的稳定性。

例如，假设有{1,2,3,4,5,6,7}共7 个节点，其拓扑关系及链路权重如图2(a)所示，设Nmax=3，则根据所提算法执行缓存节点及其服务邻居节点的筛选，具体过程如下。

1) 将连接度为0 的孤立节点设置为缓存节点，本例中无孤立节点，可跳过此步骤。

2) 处理连接度为1 的节点，即当某节点的邻居节点只有一个时，则考虑将该节点的邻居节点设置为缓存节点。如图2(a)所示，节点3 的连接度为1，其邻居节点有且仅有节点2，因此将节点2 设为缓存节点，节点3 纳入节点2 的服务邻居节点集合。

3) 由于Nmax=3，缓存节点2 还可以在剩余的邻居节点{1,4,5}中选择2 个节点作为服务邻居节点。其中，连接状态未定节点的度最小的是节点5，因此将其纳入节点2 的服务邻居节点集合。

4) 对于节点1 和节点4，链路1—2 在节点1的所有链路从大到小的排序中位次为2，链路2—4在节点4 的链路排序位次为1，因此，将节点4 纳入节点2 的服务邻居节点集合。至此，完成缓存节点2 的服务邻居节点筛选，即节点{3,4,5}。

5) 剩余的状态未定节点为节点{1,6,7}，其中节点6 连接状态未定节点的度最大，因此将其选为缓存节点。其邻居节点个数为2，即节点{1,7}，该值小于Nmax，因此，均纳入节点6 的服务邻居节点集合。对应结果如图2(b)所示。

图2 基于负载约束的最小支配集算法案例

5 仿真分析

5.1 仿真场景及参数设置

通过对市区中心某十字路口早高峰实地考察，仿真场景设定为双向六车道的单个十字路口，每条支路长度为1 km，总面积为2 km×2 km，车流量在交通灯作用下呈现波动上升趋势，如图3 所示。设定仿真软件SUMO（simulation of urban mobility）的参数，从而生成交通流数据，即提取以十字路口为圆心、以500 m 为半径的车辆轨迹，再采用NS3（network simulator）完成算法性能的分析和评估，关键仿真参数如表1 所示。

基站的服务范围为500 m，车辆之间的通信半径为50 m。可请求的文件种类总数为20，后续将评估每车的缓存空间分别为1、3、5 时的性能，且所有车辆的缓存空间保持一致。文件流行度服从Zipf 分布，节点请求也服从Zipf 分布。此外，缓存节点可以发出请求，且可以被自身响应，每个缓存节点缓存最流行的前C个文件。C-V2X mode-3 参数设定中，设子载波带宽为180 kHz，噪声功率为-113 dBm，数据传输率为1 Mbit/s[3]。信道采用Winner+B1 城市场景模式[29]。为匹配车辆间通信半径设定，发射功率设为10 dBm，并限定数据分组到达率容限为90%。

图3 仿真场景

表1 关键仿真参数

为了评估算法的性能，将所提算法（下文简称NmaxMDS 算法）与穷举法、CCMP 算法[6]、k-means无监督聚类算法（下文简称k-means 算法）[30]、最大连接度算法（下文简称MaxDegree 算法）[31]进行对比。

5.2 性能指标

将本文所提算法与穷举法对比，通过大量随机拓扑的仿真并统计，以验证筛选出的缓存节点个数和簇平均链路权重均值接近全局最优解的程度。其中，缓存节点个数的准确性通过给定拓扑下，本文所提算法与穷举法计算的最优缓存节点个数差值，即缓存节点个数偏差的分布衡量；同理，簇平均链路权重均值也通过与最优结果偏差的均值和标准差衡量。

此外，将所提算法与3 种代表性算法的缓存节点选择部分进行比较，由于这些对比算法并不以节点的全覆盖作为首要优化目标，因此所比较的性能指标不同于上述与穷举法比较的情况，而主要衡量缓存节点的利用率以及为基站负载分流的程度，所采用的具体性能指标如下。

1) 请求应答率。定义为一个周期内，所有普通节点发出的文件请求中，能被车辆缓存节点响应的请求占据所有请求的比例。该指标反映的是缓存节点为基站分担负载的程度，其值越大说明越少的文件请求需要从基站获得响应，即基站负荷越小。同时，该指标还能体现缓存分布的合理性和多样性。另外，为了更清晰体现该指标性能差异，本节将直观地比较所提算法与对比算法请求应答率差值，差值越大说明所提算法的优势越明显。

2) 重复应答率。定义为一个周期内，被缓存源应答的请求中，同时被多个缓存源应答的请求的比例。该指标体现了缓存分布的冗余度，当节点的请求同时被多个缓存节点响应时，将导致响应冗余和带宽浪费。

3) 缓存节点应答次数均值。定义为一个周期内，每个缓存节点平均的响应次数。其值越大，说明平均意义下，缓存节点能够为越多普通节点提供文件共享。该指标体现了缓存节点选择的合理性，同时也侧面反映了分担基站负载的程度。

5.3 NmaxMDS 算法与穷举法的性能比较

穷举法采用遍历尝试的方式。缓存节点个数以1为初始值逐步增加，并且每个缓存节点遍历尝试所有不超过Nmax个邻居的邻居节点组合，直至找到可实现无重叠全覆盖的最少的缓存节点个数，并且每个缓存节点的服务邻居节点个数不超过Nmax。随着缓存节点个数的增加，穷举法需要尝试的缓存节点组合以及缓存节点的服务邻居组合增量巨大，但总节点数过少无法体现算法间性能优劣，因此设节点总数为4～9，服务邻居个数上限分别为2 和3。为减少随机误差，每组参数均重复执行300 次后计算统计平均值。

图4 反映了不同的拓扑节点总个数和不同Nmax约束下，NmaxMDS 算法和穷举法的缓存节点个数的比较。统计2 种算法得到缓存节点个数差值出现的次数，再除以总的仿真重复执行次数，即可得到各缓存节点个数偏差占比。从图4 中可以看出，在不同的节点总数和Nmax约束下，缓存节点个数偏差占比趋于稳定，无偏差比例平均值为95.61%。随着节点个数增多，缓存节点个数偏差占比没有显著差异变化。NmaxMDS算法最终的缓存节点个数较大程度上与穷举法吻合，有偏差的比例平均值仅为4.39%，且仅比穷举法的缓存节点个数多一个，但显然NmaxMDS 算法的时间复杂度远小于穷举法。

图4 缓存节点个数比较

在不同节点个数且不同Nmax约束下，NmaxMDS算法和穷举法之间的簇平均链路权重均值偏差如图5所示。从图5 可以看出，NmaxMDS 算法的簇平均链路权重均值比穷举法平均约小11.88%，平均标准差约为8.08%。这是由于为了适应C-V2X 低时延的需求，NmaxMDS 算法采用贪婪思想的思想，以牺牲准确度为代价，提高执行速度，但NmaxMDS 算法所得结果较接近穷举法的最佳结果。

5.4 NmaxMDS 算法与其他缓存节点选择算法的性能比较

图6 呈现了不同周期下，NmaxMDS 算法和MaxDegree 算法、CCMP 算法以及k-means 算法之间的性能比较，其中设C=5，Nmax=3，并且为减少随机误差，各算法重复执行300 次后计算统计平均值。

图5 簇平均链路权重均值偏差

从图6(a)可以看出，NmaxMDS 算法的请求应答率均值保持在58.70%，标准差为1.07%。图6(a)中的理论值由相同参数设定下，Zipf 分布的CDF计算得到，即文件种类数为20、最流行的前5 个文件的CDF 值为59.32%，NmaxMDS 算法与之偏差约为0.62%。这是由于非理想信道导致的分组丢失引起部分性能损失。NmaxMDS 算法中每个节点均有且仅有一个缓存节点管辖，且缓存节点存储最流行的前5 个文件，只要请求这5 个文件必然获得响应，因此理论上可达请求应答率的理论值。其他3种算法随着周期的增多都呈现波动且略微下降的趋势，这是因为在如图3(b)所示的车流量波动上升作用下，由于不完全覆盖导致更多的节点无法从缓存节点获得所需文件。CCMP 算法和k-means 算法的请求应答在0.37～0.46 波动，且k-means 算法略优于CCMP 算法。CCMP 算法在进行缓存节点选择时，考虑了对于节点轨迹的预测和节点在热区的逗留时长，未考虑节点的覆盖面。k-means 算法中，设各周期的K值与NmaxMDS 算法的缓存节点个数对应一致，虽然该算法也考虑了链路稳定性度量，但对缓存节点的筛选不够完善。MaxDegree 算法的请求应答最低，且在0.17～0.35 波动，这是因为在进行缓存节点选择时，仅根据节点的连接度进行选择，虽然连接度大的节点可以覆盖更多节点，但是对于节点的服务能力没有进行适度考虑，容易造成大量的覆盖冗余，也导致了覆盖不完全。NmaxMDS算法综合考虑连接度、负载约束和链路稳定性，提升了缓存节点的请求应答，提升网络的服务性能。

图6 不同周期下算法性能分析

图6(b)显示了4 种算法的重复应答率。3 种对比算法在考虑节点分配成簇的情况下没有考虑节点本身的负载约束，因此一个节点可能会被多个簇头共同覆盖，从而导致了较高的重复应答率。其中，MaxDegree 算法的全覆盖性不佳，导致了其重复应答率比例较低，其波动一方面由拓扑的随机性引起，另一方面由于车流量的起伏变化导致。NmaxMDS 算法在服务邻居节点个数上限约束下，实现了无重叠覆盖，因此该性能指标恒等于0，可以降低缓存节点之间的信道竞争，减少冗余响应所耗费的带宽资源。

图6(c)显示了4 种算法的缓存源应答次数均值。从图6(c)可以看出，MaxDegree 算法的缓存源应答次数均值最小，波动区间位于0.7～1.4 次/缓存节点，CCMP 算法和k-means 算法变化趋势和值都较为接近，且随着周期变化均呈逐步上升趋势，在仿真周期末期趋于平缓，达到约1.5 次/缓存节点。算法随着周期变化，缓存应答次数均值明显上升且相对于其他算法的优势逐步增大，仿真周期末期趋于平缓，达到约2.2 次/缓存节点。MaxDegree 算法只考虑了缓存节点可连接节点的数量，忽视了其服务能力，造成了节点的不完全覆盖，也出现较多的重叠覆盖，从而降低了缓存应答次数均值。CCMP算法和k-means 算法均从成簇的角度以逗留时长和链路稳定性度量等为性能进行簇头及其邻居的筛选，故减少了部分冗余响应，但是全覆盖性仍不足。NmaxMDS 算法除了对车辆轨迹进行提前预测外，在分簇阶段也从微观本质上考虑链路的连接实质，提高了缓存节点的应答次数，减轻了基站负担。具体地，在仿真周期初期，车辆密度较小，孤立节点以及连接度低的节点较多，因此有较多的节点无法相互提供文件共享，从而导致缓存应答次数较小，且与对比算法差距不大。随着车辆密度增加，链路资源逐渐增多，更合理的缓存节点及其服务邻居节点的选择逐步突显了NmaxMDS 算法的优势。而在仿真周期末期车辆密集，缓存节点的服务能力趋于饱和，因此缓存应答次数趋于平缓，但NmaxMDS算法仍然保持较大优势。

图7 反映了3 种对比算法与NmaxMDS 算法在不同车辆缓存空间条件下的请求应答率差值，其中设Nmax=3，C=5,10,15。从图7 可以看出，该差值均大于零，即NmaxMDS 算法的请求应答率性能在不同车辆缓存空间下均优于对比算法，并且随着车辆缓存空间的增加，优势更加明显。当缓存空间为5 时，NmaxMDS 算法与MaxDegree 算法、CCMP 算法和k-means 算法的差值中位数分别为0.32、0.18 和0.17。当缓存空间增加到15 时，对应的差值中位数增加到0.49、0.28 和0.26。因为更大的缓存空间意味着能存储更多文件，普通节点能够以更大概率从缓存节点获取文件。缓存节点的全覆盖性越好，请求应答率就越高，并且每个缓存节点更大的缓存空间更加突显了NmaxMDS 算法在全覆盖性方面的优势。

图7 不同车辆缓存空间的请求应答率差值

NmaxMDS 算法与3 种对比算法在请求应答率差值的75%分位点和25%分位点的变化趋势与中位数类似，但在这2 个分位点之间的间距方面，与MaxDegree 算法差值的间距最大，k-means 算法的间距次之，CCMP 算法的间距最小。在NmaxMDS算法中，每个普通节点都与一个缓存节点连接，保持接近理论值的请求应答率，2 个分位点的间距越大说明算法效果的稳定性受节点密度和分布的影响越大，其性能的波动明显。

图8 呈现了NmaxMDS 算法与3 种对比算法在不同服务邻居节点上限约束下的请求应答率差值，其中，C=5，Nmax=1,3,5。从图8 可以看出，请求应答率差值均大于零，说明NmaxMDS 算法优于各对比算法。随着Nmax增加，NmaxMDS 与3 种对比算法的请求应答率差值逐渐减小。这是因为每个缓存节点可服务更多的邻居节点时，普通节点可选择的缓存节点更多。对于每个缓存节点的服务邻居节点的准确筛选的要求降低，弱化了各算法之间的性能差距。

随着Nmax增加，NmaxMDS 算法与MaxDegree算法的差值最大，中位数分别是0.37、0.32 和0.29；与CCMP 算法的差值次之，中位数分别是0.31、0.18和0.11；与k-means 算法的差值最小，中位数分别为0.30、0.17 和0.09。这是因为MaxDegree 算法仅从连接度考虑，CCMP 算法从热区逗留时间角度考虑了车辆密集程度，而k-means 算法从位置和链路的角度综合考虑，所以k-means 考虑因素更周全，与NmaxMDS 算法的性能差距更小。

图8 不同服务邻居节点上限的请求应答率差值比较

6 结束语

在城市环境下，C-V2X 车辆拓扑快速变化且传输时延要求较高，车辆缓存节点通过V2V 传输可降低数据传输时延，减轻基站负荷。本文提出NmaxMDS 算法解决缓存节点及其服务邻居节点的选择问题，定义链路稳定性度量并构建预测权重邻接矩阵；构建最小化缓存节点个数以及最大化簇平均链路权重均值的目标函数；定义3 种节点状态，在缓存节点负载约束下，求解车辆拓扑的最小支配集，实现无重叠的节点全覆盖。仿真结果表明，所提算法得到的缓存节点个数和簇平均链路权重均值接近穷举法计算的全局最优结果；在请求应答率、重复应答率和缓存源应答次数等方面均优于对比算法，并且重复应答率恒为零，请求应答率可达理论上界，证明了所提算法可有效提升缓存节点利用率，减轻基站负荷。

在后续工作中，考虑适度地在缓存节点之间引入重叠覆盖，并利用缓存节点间的协作关系，进一步提升缓存节点的请求应答。