基于NDN的区分调度提升树转发策略研究

鲁 欢，郭永安，陈春玲

(南京邮电大学 计算机学院、软件学院、网络空间安全学院，江苏 南京 210023)

0 引 言

车联网(internet-of-vehicles，IoV)是物联网在智能交通领域里的重要应用，受到了国内外研究人员的广泛关注。车联网通过使用GPS定位卫星、基站和路边的设施来完成车辆和车辆之间，车辆和路边单元(RSU)之间的通信，使车辆之间可以通信，交换数据、信息等，以提供道路安全、娱乐和其他路边服务[1]。车联网相较于一般的网络具有网络拓扑结构变化迅速，车辆之间短暂间歇性连接等特性。TCP/IP体系由于其设计之初的局限性，难以适应车联网快速移动变化的特性，这使基于TCP/IP的车联网面临巨大的挑战。

命名数据网络(named data networking，NDN)[2]是信息中心网络(ICN)[3]多个方案中比较突出的一个，是新一代网络架构。NDN是一种以内容为中心的网络，取代了端到端的通信模式[4]，同时，具有对移动性支持良好、不依赖网络地址和会话连接，多网络寻址等特点，在移动环境下更具优势，且延迟低、扩展性强，使得网络性能增强，给车联网提供了新的可行方案。

在车联网中，尽管基于NDN的车联网能减少移动性的问题，但车辆在网络中的快速移动，有时难以进行有效地通信和节点之间的数据传输[1]。此外，基于NDN的车联网还面临着车辆分布的随机性和不均匀性、RSU设施和无线网络的配置、车辆存储空间不足等问题。因此，文中提出了区分调度提升树转发策略，其目的是为解决网络拥塞、时延较高、缓存命中率不高等问题，提升转发策略的性能，实现更高效的数据转发。

1 NDN及其转发策略

1.1 路由及转发

NDN在功能上对其架构设计进行了分离，分为路由平面和转发平面。路由平面指提供转发数据可选择的转发端口的信息，转发平面根据转发策略从可选择的转发端口中选择合适端口进行转发[5]。NDN中有3种数据结构非常重要，分别为内容仓库(content store，CS)、转发兴趣表(forwarding information base，FIB)以及转发请求表(pending interest table，PIT)。CS保存路由节点的缓存内容；FIB保存了路由节点到达内容服务器的下一跳接口，为数据的转发提供多路径的选择；PIT保存了未得到响应的兴趣包的前缀信息及其到达的接口，以便数据包报文沿途返回[6]。这三个表项与NDN的路由、转发和缓存都有着密切的联系。

车联网中，每个车辆节点都可能同时扮演着三种角色：数据的生产者、搬运者和请求者[7]。随着车辆用户需求的改变，其所对应的角色也随之改变。数据生产者就是数据发布者，生产者根据自身的实际情况，随时准备接收邻居节点的数据请求并给出回应。搬运者的工作就是搬运，在其他节点需要数据时，将其所需数据搬运过去。车辆在行驶的途中，会存储一些数据，当车辆收到广播的数据请求时，如果CS中恰好有对应的数据，则直接搬运数据。数据的消费者既可以是最先发送兴趣包的车辆节点，也可以是曾经搬运过兴趣包的车辆节点。数据消费者推动网络的正常运行。

1.2 转发策略比较分析

目前车联网环境下，在对基于NDN的转发策略研究中，研究的重心主要在提升数据取回效率、降低数据取回时延等方面。根据内容发现方式的不同可以将基于车联网的NDN转发策略分为先应式转发策略、反应式转发策略和机会式转发策略三个方面[5]。

先应式转发策略中，节点主动广告所持有数据的前缀信息或位置信息等，网络中的其他节点在收到这些信息后，根据信息更新FIB，并构建更优的传输路径，这会产生较大的广告开销。同时，先应式转发策略本质上采用“拉”方式取回内容，会导致冗余的开销。其中文献[8]提出了一种针对流行内容使用布隆过滤器(bloom filter，BF)广告命名前缀的方案BFR及其改进方案，这是最具代表性的转发策略。由于车辆的快速移动，簇头是短暂的，需要不断地重新选取簇头，转发效率较低。

反应式转发策略按照原路回复的策略转发到网络中，洪泛转发(flooding)[9]是最基本的被动式转发策略，这种方式为每个接口设置绿色、黄色、红色三种状态。路由节点将Interest包转发给前缀匹配成功且接口状态不是红色的接口，但是数量较多，容易引发广播风暴，网络性能随之大幅降低。智能洪泛(smart flooding)[9]是一种改进的洪泛方式，可以在一定程度上缓解网络风暴，但由于节点状态更新滞后，重传次数明显增加。同时，为了找寻更合适的下一跳节点或数据提供者，感知机制被用于转发策略中，如距离感知、位置感知和邻居感知。比较具有代表性的策略有CHANET[10](content-centric mobile ad-hoc networks)、LFBL[11](listen first，broadcast later)与BREB[12](best rout，error broadcast)三种。BRBE是针对CHANET和LFBL改进的转发策略，保持了LFBL转发策略下基于距离的设计思路，同时对CHANET转发策略的三种数据结构进行了整合，增加了路径恢复功能。该策略可以极大地减少数据的转发跳数和相同兴趣的冗余，但是在移动场景下表现较差，会导致超时重传或重新选路。

机会式转发策略采用“存储-携带-转发”模式，不再主动发现内容，而是使用被动发现的形式，避免了泛洪造成的巨大广告开销以及拓扑变化导致的路由失效，但是会产生巨大的传输时延。其中具有代表性的是STIR[13]转发策略和STCR[14]转发策略，STIR转发策略使用了梯度场的概念，根据节点间的时空相关性构建生产者到提供者的梯度场，形成最小延迟的传输路径，从而实现机会路由转发。但此算法面临收敛速度慢的缺陷，导致起始路径的准确性较低。STCR转发策略利用节点间的社会关系作为辅助，通过节点间的新鲜度和相遇频率计算此节点的社会关系，在节点匹配时交换本地社交关系表并更新。但是此转发策略只考虑了单个社区间的路由转发，没有考虑社区间的路由转发。

这三类转发策略普遍存在开销较大、时延较高、网络性能较低、冗余较多等问题，针对这些问题，提出一种区分调度提升树算法，提高网络性能和转发性能。

2 区分调度提升树算法

由于车联网环境网络拓扑变化快且车内节点缓存不足，利用传统的转发策略很难将数据信息快速、及时、准确地转发出去。因此，针对当前转发策略的缺点和问题，提出了一种区分调度提升树算法(diffserv dispatch boosting decision tree，DDBDT)。该算法通过区分服务类型和服务紧急程度，使用调度算法生成优先权队列，训练样本集，使用加权模型操作子决策树生成提升树，选择最优转发接口，实现最优转发。

2.1 区分服务模型

区分服务模型中，逐跳行为主要有加速转发(expedited forwarding，EF)、确保转发(assured forwarding，AF)和尽力而为(best-effort，BE)三种类别[15-16]，三种类型的逐跳行为对于带宽资源的优先权要求依次降低。EF是优先级最高的服务，它要求端口保证该类型的分组能够实现较低时延和防抖，能够保持配置的速率转发出去。AF是优先级次高的服务，属于AF的分组将尽量不被丢弃，基本上保证分组的转发，AF中定义了四个子类和三个分组丢弃优先级，子类数字大的优先级高，分组丢弃优先级低的会优先被丢弃。必要时，AF所占用的带宽资源可以暂时被更高优先级的服务占用。BE是优先级最低的行为，不会提供任何服务质量的保证。

具体车辆服务类型所对应的逐跳行为如表1所示。

表1 服务类型的具体逐跳行为

同时，根据服务的紧急程度从高到低分为一级(Ⅰ级)、二级(Ⅱ级)、三级(Ⅲ级)和四级(Ⅳ级)。同等类型下的服务，高紧急度的服务可以具有更高的优先权，可以进行前插操作，插入到低优先级服务之前，让紧急程度高的服务更快速地被访问和处理，实现服务的及时响应和带宽的合理配置使用。

2.2 加权循环调度算法

加权循环调度算法(weighted round robin，WRR)[14]将不同服务类型、不同紧急程度的数据包进行分类，放在不同的优先级队列中。相较于低优先级队列服务，WRR算法会优先操作高优先级队列服务，但是，在所有优先权队列服务后通过轮询的方式进行队列调度，解决了PQ(priority queue)队列中低优先级队列可能饿死的情况。轮询采用的方式是允许高优先级队列发送多个数据包，同时，给予高优先级队列更高的访问次数，让其享受更多的带宽资源。WRR调度算法适用于大小固定的兴趣包或差异不大的网络。具体示意图如图1所示。WRR算法中，服务会采用先进先出的策略进入不同的优先级队列中，之后进入队列的服务，会比较服务的紧急程度，根据服务的紧急程度进行插队服务，紧急程度高的服务可以插入到紧急程度低的服务之前，从而更快被访问，提供更高效的服务。

图1 WRR算法

2.3 提升树

提升树(boosting decision tree)是集成学习中的一个重要方法，是将弱分类器线性相加组装成一个强分类器。提升树是以决策树为基树的提升方法，采用加法模型和前向分步算法，损失函数使用平方误差函数[17]。文中的提升树采用4种属性信息：端口平均时延、端口PI计数、数据的热度值、兴趣包的类别。RTT描述的是兴趣包转出到数据包返回的往返时间，可以了解端口的拥塞情况和时延。PI计数描述端口中已转发但待返回的兴趣包和数据包的个数，PI的数量反映了节点的拥塞情况。热度描述的是此兴趣包的请求频率，反映了这段时间内用户的需求。高热度的数据请求频率高，数据可能缓存在附近的节点，请求数据所需要的时延、跳数都会相应减少，反映了端口内的缓存情况。不同类别的数据对于网络延时、拥塞、性能、开销等方面的要求是不一样的，兴趣包的类别可以在一定程度上反映数据的分布情况和端口的选择情况。具体提升树流程如图2所示。文中对训练集集合分别随机选择属性权重，使用权重处理样本，计算损失函数，根据损失函数和样本生成子决策树；依据损失函数更新下一个属性权重，生成带权重的样本，继而生成另一个子决策树，通过迭代生成所有子决策树，采用加法模型操作子决策树生成提升树。

图2 提升树流程

2.4 区分调度提升树流程

根据上述研究可得，区分调度提升树执行过程如下所示：

算法：DDBDT算法

输入：兴趣包集合I

输出：兴趣包集合I所对应的转发端口P

步骤1：兴趣包进入端口，进行CS和PIT查询，CS匹配成功，则直接传回数据包；PIT匹配成功，则在PIT中记录下请求端口并丢弃此兴趣包；

步骤2：区分服务类型和紧急度，兴趣包I选择EF、AF、BE服务类型和紧急程度；

步骤3：兴趣包I根据类型进入相对应优先权队列，执行队列调度算法；

步骤4：生成提升树，选择转发端口进行数据转发。

DDBDT算法的具体工作流程如图3所示。

图3 DDBDT流程

当节点收到兴趣包后，先进行CS和PIT查询匹配，若CS匹配成功，则直接返回数据包；若未匹配上CS，则查询PIT，若PIT中存在表项，说明已有相同请求在处理，则丢弃兴趣包并记录兴趣包来源。之后，对兴趣包的服务类型和紧急程度进行分类，进入相对应的EF、AF、BE优先权队列，使用WRR队列调度算法进行出队操作，依据属性信息对样本进行训练，生成提升树，选择最优端口进行数据转发。

3 实验结果及分析

3.1 实验设置

考虑车联网节点的高移动性、间歇连续性，通过道路交通模拟软件SUMO来获取特定道路场景下汽车的移动情况，从而反映真实的实验数据。图4选取仙林大学城附近的一段交通道路，运用SUMO软件生成的道路交通图，设置了道路的车辆的流量和移动速度等多种信息。选取的道路交通图是真实路段，有双向单车道，有单向车道，也有双向四车道。节点运动速度在40 km/h～80 km/h，初始位置是随机分布的，内容请求者每秒发送一个请求，仿真时间为200 s。同时，该文采用基于NS-3的NDN模拟器ndnSIM，这是一个开源网络仿真平台，通过该平台完成对NDN转发策略性能的仿真和评估。

图4 仿真道路交通图

3.2 实验结果及分析

该文选取经典的智能泛洪转发策略、BRBE转发策略作为对比策略，选取的评价指标有：

平均时延:从兴趣包的发出到数据包的返回经过的时间。

兴趣包满足率:成功返回数据包的所对应的数据包的数量和实验中全部兴趣包的数量之间的比例。

兴趣包满足率与节点数目的关系如图5所示。

图5 兴趣包满足率

图5中，DDBDT转发策略随着节点数目的增多兴趣包满足率不断上升。当节点数目在40个时，DDBDT兴趣包满足率比智能泛洪转发策略高5.2%，比BREB转发策略高3.5%；而节点数目达到80个时，DDBDT兴趣包满足率比智能泛洪转发策略高8.9%，比BREB转发策略高5.1%。

随着节点数目的增加，网络的连通性更加完善，兴趣包满足率也随之增加。智能泛洪转发需要广播大量节点以寻找目标节点，因此在节点数目较低时兴趣包满足率较高，但随着节点数目的增加，需要广播的节点太多，兴趣包满足率最低。车辆的快速移动导致车辆间距离不断改变，BREB转发策略会导致重传，兴趣包满足率也相对较低。区分调度提升树算法先对服务进行区分，更加具有针对性，同时决策选择最优转发接口，兴趣包满足率较高。

平均时延与节点数目的关系如图6所示。

图6 平均时延

图6中，DDBDT转发策略相较于Smart Flooding转发策略在节点数目为40个时，平均时延低了10.9 ms；在节点数目为80个时，平均时延低了25 ms。DDBDT转发策略在节点数目为40个时，平均时延相较于BREB转发策略低了9.3 ms，在节点数目为80个时，DDBDT转发策略相较于BREB转发策略平均时延低了14.6 ms。

平均时延随着节点数目的增加而不断增加，智能泛洪转发策略的节点状态更新滞后，重传次数明显，需要耗费大量的时延。BREB转发策略没有充分使用节点中的缓存数据，同时在车辆快速移动环境下，距离的迅速改变，会导致重传和重新选路，会产生较大的时延，该文提出的区分调度提升树算法根据兴趣包的内容、端口的实际状况、端口内的缓存选择最优的转发接口，只产生较小的时延。

4 结束语

文中阐述了NDN在车联网环境中发展的局限性以及NDN转发策略研究的重要性，车联网环境下车辆的快速移动，车辆间连接的不稳定性，NDN转发策略存在时延较高、没有充分利用节点内缓存等缺点，提出了一种区分调度提升树算法。在ndnSIM平台对该算法和两种典型转发策略进行仿真实验，实验表明区分调度提升树算法具有更高的兴趣包满足率和更低的时延。

文中对转发策略的时延、兴趣包满足率进行对比，在此基础上，笔者将考虑将丢包率、冗余性、跳数等指标进行进一步的考量，同时将进一步优化算法，使其在车辆网环境下有更好的性能。