陈清秋，朱 琦
(南京邮电大学 江苏省无线通信重点实验室，江苏 南京 210003)
随着智能交通系统(ITS)的发展，司机和乘客不仅需要交通信息，还需要更多其他内容(例如车内娱乐和移动广告)，这给车载网络造成了很大的压力[1-2]。边缘缓存是在系统的边缘部署缓存，在车载网络中引入边缘缓存技术，将内容缓存在路边单元和车辆中，可以减少从远程内容服务商获取内容的概率，有效地降低内容获取时延，缓解车载网络的压力[3-5]。
目前对于车载网络中的缓存已有一些研究，文献[6]根据路边停放的车辆与沿路行驶的车辆可以形成一个车辆社交区域，提出了一种车辆社交网络中的内容分发策略，该策略中路边停放的车辆与移动车辆一起分发内容，以减少内容下载延迟。在文献[7]中，作者考虑到不同区域的内容流行度的多样性，提出了一种内容流行度预测的线性模型，根据内容流行度的预测结果进行内容的缓存。文献[8]在车辆内容网络的架构下提出了一种基于交叉熵的边缘缓存策略，将内容缓存在路边单元中，以动态地适应内容的流行度变化。文献[9]提出了一种基于移动性预测的协作缓存策略，该策略中通过移动车辆过去的轨迹来预测车辆到达不同热区域的概率，在热区域停留时间较长的车辆优先被选为缓存节点，以此来为其他车辆提供更好的服务。
文献[10]根据服务质量要求和有限的回程容量，提出了一种路边单元放置策略，该策略将宏基站与路边单元联合起来，对文件传输服务和路边单元布置开销综合考虑，能够在满足文件传输服务要求的前提下实现最低路边单元布置开销。以上对车载网络中缓存策略的研究都没有采用车辆分簇的方法。
车辆分簇在车载网络中的应用可以提高通信链路的稳定性，减少车辆之间通信的干扰。文献[11]提出了一种适用于高速公路场景下的车辆分簇方法，该方法考虑了相邻车辆之间的速度差，以形成相对稳定的车辆分簇。
在文献[12]中，作者提出了一种新的基于权重的分簇方法，该方法考虑一个簇中有两个簇头，分别是主簇头和从簇头，当主簇头不再适合管理车辆分簇的时候，从簇头会取代主簇头来进行簇内的信息分发，以此来提高车辆分簇的稳定性。文献[13]提出了一种基于分簇的协作缓存方案，该方案中每个簇中包含一个簇头和一个备份节点，簇头负责维护簇内缓存信息和节点信息，备份节点用于提高系统性能和簇内信息的可用性，降低获取内容的时延和开销。文献[14]提出了一种基于分簇的车载内容网络(VCN)中的协作缓存算法，该算法综合考虑了车辆的缓存容量和车辆分簇的全局缓存状态，在满足缓存容量限制的前提下可以有效地降低平均累积网络成本。文献[15]基于双向高速公路情景，提出了一种基于分簇的路边单元和移动车辆协作缓存策略，该策略中路边单元对其覆盖范围之内的车辆进行统一缓存调度，提高了在路边单元覆盖范围之外车辆间通过V2V通信完成内容交付的成功率。
以上车辆分簇方法中簇间通信是通过V2V方式进行的，而在不相邻的簇之间进行多跳通信会带来很高的通信时延和成本。该文提出了一种基于车辆分簇的协作缓存策略，相邻簇间通信通过V2V方式进行，不相邻簇间通信以路边单元作为中继。首先根据车辆的速度和位置以及邻居车辆的数目对车辆进行分簇，移动车辆发出内容请求，按照簇头-相邻簇-RSU-不相邻簇的顺序进行内容搜索，当找到本地缓存内容时，按原传输路径将内容返回请求车辆。由于移动车辆和路边单元的缓存容量是有限的，该文设计了一种基于蚁群算法(ACO)的缓存放置算法，可以充分利用有限的缓存空间，对缓存内容进行协同分配，实现内容请求时延和成本的联合最小化。通过仿真分析，该算法拥有很好的性能。
系统模型如图1所示。
一条长度为10 km的单向道路上均匀分布着NR个RSU，随机分布着NV个移动车辆，每个RSU的缓存容量为SRSU，每个车辆的缓存容量为SV。移动车辆首先进行分簇，随后在请求内容时，可以通过V2V和V2R两种方式进行。移动车辆先向簇头请求内容，如果簇头没有缓存内容，则向RSU和其他簇发出请求，车辆与不相邻簇之间进行通信时，需要以RSU作为中继。当RSU和移动车辆都没有缓存请求内容时，则需要从远程内容服务商获取内容。
1.1 内容请求和缓存模型
车辆请求内容的流行度遵循齐夫分布[16]，则内容q(q∈{1,2,…,Q})的请求概率为：
(1)
其中，s为齐夫分布的参数，eq为内容q请求次数的排序。参数s越大，表明受欢迎内容出现的概率越高，相应内容请求频率就会越高，这些内容被缓存的概率也会越高。
在RSURi(i∈{1,2,…,NR})覆盖范围下,车辆分成NC个簇。在第i个RSU覆盖范围下，第j(j∈{1,2,…,NC})个簇内的第k(k∈{1,2,…,n})辆车表示为Vi,j,k，其中Vi,j,1为簇头，其余车辆为簇成员。移动车辆发出内容请求时，首先向簇头Vi,j,1发出请求信息，Vi,j,1检查本地缓存内容，如果有则直接将内容q返回请求车辆中。若簇头没有缓存内容q，会将请求转发给相邻簇的簇头Vi,o,1，如果Vi,o,1缓存有内容q，则将内容返回给簇头Vi,j,1，簇头再将内容发送给请求车辆。若本簇簇头和相邻簇头都没有缓存内容q，Vi,j,1会将请求信息转发给RSU，如果RSU缓存有请求内容，则将内容返回，否则将会转发请求信息至与j不相邻的簇中。需要注意，簇头与不相邻的簇进行通信，必须要以RSU作为中继。这里考虑到不相邻簇头之间进行通信，如果以V2V方式直接进行，需要多跳通信，会产生更高的时延和资源浪费，并且通信链路很不稳定。若通过RSU中继通信，可以降低内容请求时延，提高车辆在RSU覆盖范围内的内容交付成功率。
1.2 时延分析
车载网络中，网络拓扑变化快，系统对时延的变化十分敏感。在文中场景下，不同的内容获取方式会产生不同的请求时延[17-19]，假设请求内容为q，内容q的大小为sq。当移动车辆从簇头获得请求内容时，只需要在车辆和簇头之间建立通信连接，此时的内容获取时延为：
(2)
(3)
(4)
(5)
两个簇头之间的通信不受簇成员之间的影响。当移动车辆从RSU获取内容时，需要在移动车辆、簇头和RSU之间建立通信连接，内容从路边单元传输到簇头，再经簇头传回请求车辆，此时的内容请求时延为：
(6)
(7)
(8)
表示第j个簇内的车辆Vi,j,k从不相邻的p簇中获取内容。
1.3 成本分析
内容请求过程中，成本分为两个方面，一个是内容缓存成本，一个是内容传输成本。给定RSU的存储容量为SRSU，车辆的存储容量为SV，初始缓存内容大小分别为CRSU和CV，应满足约束条件CRSU≤SRSU，CV≤SV。车辆缓存内容成本为CSV,RSU缓存成本为CSR，且CSV CC=CRSU·CSR+CV·CSV (9) 传输成本方面，RSU传输一个内容q的传输成本为CRR，车辆传输一个内容q的传输成本为CVV，且CVV CT=CqR·CRR+CqV·CVV (10) 成本为内容缓存成本和传输成本之和。 C=CC+CT (11) 内容请求时延是评判系统性能的重要因素，它可以直接反映出设计系统模型的好坏。同样，缓存成本也是评估系统性能好坏的一个标准。因此，该文同时考虑了时延和成本，目标是实现成本和时延的联合最小化，以获得最优的缓存策略。对于缓存放置方案而言，应综合考虑缓存成本、内容获取时延和缓存内容的多样性。为了避免缓存冗余，该文规定同一个内容q不能被重复缓存，即在所有的RSU和移动车辆的缓存过程中，内容q只能被缓存一次。定义一个缓存放置矩阵AQ,NC+1，其中a=1表示缓存内容q，a=0表示不缓存。考虑到有限的缓存容量，目标函数可以表示为： s.t.:a:,:={0,1} (12) 在(12)中，前两个约束条件表示内容不能被重复缓存，后两个约束是缓存容量约束，表示每个节点缓存的内容大小不能大于本身的缓存容量。 本节中给出基于车辆分簇的协作缓存算法。首先，为了车辆通信的稳定，该文给出一种基于权重的分簇方法(WCA)对车辆进行分簇。而问题P1是一个多目标优化问题，该文设计了一种基于蚁群算法的缓存放置算法对其进行求解。 在车载自组织网络初始状态下，每辆车都处于独立状态，随后通过选择簇头来划分不同的簇，该文采用基于权重的分簇方法[20]来进行分簇。考虑到车辆周围的邻居车辆数量N、车辆与邻居的平均距离d、车辆与邻居车辆的速度差总和vd三个因素。车辆周围的邻居车辆数量表示车辆通信范围内的其他车辆数目，车辆与邻居的平均距离表示该车辆与其通信范围内其他车辆的平均欧氏距离，移动车辆的邻居车辆越多、与邻居车辆的平均距离越小，说明该车辆越适合被选为簇头。车辆与邻居车辆的速度差可以用来评估分簇的稳定性，簇头与簇成员之间速度越接近，说明簇成员在簇内的时间越长，通信的成功率也就越高。所以车辆与邻居的速度差总和越小，说明该车辆越适合被选为簇头。根据以上的分析，将权重定义为： (13) 其中，w1,w2,w3为各个影响因素的加权因子。 w1+w2+w3=1 (14) 车辆与邻居车辆的平均距离为： (15) 其中，x1和xk表示车辆V1和Vk的横坐标，y1和yk表示车辆V1和Vk的纵坐标。 车辆与邻居车辆的速度差之和为： (16) 其中，v1和vk是车辆V1和Vk的速度，vd表示车辆V1与邻居车辆的速度差之和。由于车辆的移动性，簇头和簇成员的状态可能会发生改变，随之会出现簇的切换和簇的合并，具体过程如下： (1)簇的切换：簇成员可能会移动到其他簇的覆盖范围内，此时，它可以接收到两个簇头的权重信息，通过比较两个簇头的权重大小，车辆可以选择继续留在本簇还是成为另一个簇的簇成员。 (2)簇的合并：两个簇头有可能进入彼此的覆盖范围内，此时，簇头之间会比较彼此的权重大小，权重小的簇头会向簇成员发送信息，使簇成员回到独立状态，随后进行重新分簇。 车辆进行分簇时，选择权重w最大的车辆作为簇头(CH)，随后簇头将自己的权重作为信息发送给邻居车辆，邻居车辆对比自身的权重和簇头的权重，若比其小，则加入本簇，自身从独立状态变成簇成员(CM)。为了限制每个簇的大小，该文给定一个阈值θ，当簇成员数量等于θ时，本簇达到饱和状态，不再接收独立车辆的进入，具体算法如算法1所示。 算法1：分簇算法。 输入：移动车辆[1,2,…,n] 输出：分簇结果 1.随机生成n个移动车辆，根据通信范围确定邻居车辆数N 2.fori= 1:n 3.forj= 1:n&j～=i 4.根据式(15)和式(16)计算车辆与邻居的平均距离和速度差之和 5.根据式(14)计算车辆的权重 6.ifwi>wj 7.车辆i成为簇头，车辆j成为簇成员 8.簇内车辆数目达到阈值θ时，停止分簇 9.endif 10.endfor 11.endfor 12.完成分簇 问题P1是一个多目标优化问题，蚁群算法[21]是一种启发式全局优化算法，可以很好地解决多目标优化问题，所以该文提出了一种基于蚁群算法的缓存放置算法来解决问题P1。蚁群算法是一种模拟蚂蚁觅食的优化算法，蚂蚁在运动过程中，会在经过的路径上释放信息素，在运动过程中，蚂蚁可以感知周围信息素的强弱，以此来引导自己的行进方向。较短路径上的蚂蚁释放的信息素较多，随着时间的推移，较短路径上累积的信息素浓度越来越高，更多的蚂蚁通过感知选择该路径。这是一种正反馈现象，最终，蚂蚁会聚集在最优路径上，通过最短的路径到达食物源。 假设有b只蚂蚁，每只蚂蚁都可以构建一种缓存放置方案。第t次迭代的信息素为τb(t)，则第t+1次迭代的信息素τb(t+1)为： τb(t+1)=(1-ρ)·τb(t)+χb (17) 其中，ρ是信息素衰减系数，1-ρ表示迭代一次后信息素挥发情况，χb为第b只蚂蚁构建的缓存放置方案留下的信息素，定义为第b种放置方案下时延和成本加权和的倒数，以此来评估该方案的性能，χb越大表明该方案下系统性能越好，χb可以表示为： (18) 可以看出，放置方案得到的时延和成本越小，该方案累积的信息素就越多。在蚁群算法中除了信息素，还有一个重要因素是启发式信息α，α越大表示该路径越有可能成为最优路径。文中α越大表示缓存放置方案越有可能成为最优方案，α可表示为： (19) 其中β(b)定义如下，β(b)越小表示内容更加均匀地缓存在移动车辆和RSU中。 (20) 蚂蚁会根据转移概率来选择缓存放置方案，转移概率与信息素和启发式信息有关，其计算公式为： (21) 其中，u和v代表了信息素和启发式信息对选择放置方案的影响。根据文献[22]的研究结果，该文将u,v设置为1和5，信息素挥发因子ρ设置为0.5。 在选择缓存放置方案时，每个蚂蚁可以构建一种缓存放置方案，然后计算每个方案的时延和成本，根据结果计算信息素和启发式信息，随后可以得到下一次蚂蚁构建每种方案的概率，重复以上步骤直到找出时延和成本最小的缓存放置方案，具体算法如算法2所示。 算法2：基于蚁群算法的缓存放置算法。 输入:系统模型参数 输出:缓存放置方案 1.forb= 1:NA 2.forq= 1:Q 3.初始化缓存放置方案 4.根据第一节中的时延成本分析计算T(b)和C(b) 5.根据式(19)和式(20)计算τb和αb 6.根据式(21)计算P(b) 7.构建新缓存放置方案 8.更新信息素 9.根据式(18)找出性能最好的方案 本节进行仿真分析，仿真参数设置如下[23-24]：带宽设置为10 MHz，车辆和RSU的发射功率分别为25 dBm和50 dBm，噪声功率为-114 dBm。在缓存方面，将CSR和CSV设置为0.5和0.3，CRR和CVV分别设置为0.8和0.5，WT和WC均设置为0.5，远程内容服务商的传输成本为1.5，内容q的大小为2 Mb，总成本表示时延和成本的加权和，总缓存容量表示RSU和簇头的总容量，缓存命中率表示RSU和簇头中缓存有移动车辆所请求内容的概率。图2表示算法的收敛性，可以看出，在迭代12次左右时，算法达到收敛。 为了评估文中转发策略的性能，将其与文献[25]中的转发策略进行对比。从图3可以看出，采用文中转发策略得到的总成本更低，这是因为文献[25]中簇头之间只能通过V2V方式进行通信，两个不相邻的簇头进行通信则需要多跳V2V，这会产生更高的内容请求时延和传输成本。而在文中转发策略中，不相邻的簇头之间以RSU作为中继进行通信，可以有效降低传输时延和成本，故总成本更低。为了进一步研究系统模型参数对系统性能的影响，以下针对具体参数进行仿真分析。 图4表示总成本和总缓存容量、齐夫参数s之间的关系，内容数Q设置为20。当总缓存容量固定时，随着s的增大，受欢迎内容出现的概率就越高，受欢迎内容被缓存在RSU和簇头中的概率也就越高，这降低了车辆需要从远程内容服务商获取内容的概率，减少了内容获取时延和传输成本，故总成本也随之降低。当齐夫参数s固定时，增加总缓存容量，簇头和RSU中可以缓存更多内容，本地缓存成本会有所增加，但内容获取时延和传输成本会大大降低，故总成本会降低。 图5表示总成本和总缓存容量、内容数之间的关系，齐夫参数s设置为0.7。当总缓存容量固定时，随着内容数的增加，总成本也随之增大，这是因为簇头和RSU中缓存的内容数是固定的，此时增加总内容数，车辆有更高的概率需要从远程内容服务商获取内容，而从内容服务商获取内容需要更高的请求时延和传输成本，总成本也就随之增加。当内容数固定时，随着总缓存容量的增加，RSU和簇头中缓存的内容随之增加，缓存成本会略微增大，而车辆有更高的概率从簇头和RSU中获取内容，内容的请求时延和传输成本会随之降低，总成本也随之减少。 图6表示缓存命中率与总缓存容量、齐夫参数s之间的关系，内容总数Q设置为20。当总缓存容量固定时，随着s的变大，受欢迎内容出现的概率就越高，受欢迎内容被缓存的概率也就越高，移动车辆越有可能从RSU和簇头中获取内容，所以缓存命中率会随之 提高。当齐夫参数s固定时，随着总缓存容量的增加，簇头和RSU中可以缓存更多内容，移动车辆有更高概率从中获取请求内容，缓存命中率也随之提高。 图7表示缓存命中率和总缓存容量、内容数之间的关系，齐夫参数s设置为0.7。当总缓存容量固定时，随着内容总数的增加，缓存命中率不断降低，这是因为簇头和RSU中缓存的内容数是固定的，此时增加总的内容数，车辆需要从远程内容服务商获取内容，降低了车辆从本地获取内容的概率，缓存命中率也随之降低。 为了充分利用车载网络中的缓存资源，降低内容请求时延和缓存成本，该文提出了一种基于车辆分簇的协作缓存策略。具体来说，为了车辆通信的稳定性，首先对车辆进行分簇，随后在内容请求过程中，车辆可以从簇头和路边单元中获取内容，不同的内容获取方式有着不同的时延，为了使时延和成本联合最小化，设计了一种基于蚁群算法的缓存放置算法对其进行求解，得到了最优缓存放置方案，最后通过仿真证明该算法具有很好的性能。在未来的工作中，将进一步研究地面和空中缓存节点之间的协作，以进一步提高系统性能。1.4 问题建模
2.1 分簇算法
2.2 基于蚁群算法的缓存放置算法