近年来，随着移动自组织网络、空天网络等新兴网络类型的兴起，延迟容忍网络(delay tolerant network，DTN)^[1]成为了网络研究领域中的热点，它是一种为实现异构不稳定网络连接而提出的新型网络架构^[2]。传统的Internet网络是基于TCP/IP协议簇，该协议的有效运行通常基于端到端存在持续连接，以及较低丢包率、较低传输延时等基本假设之上^[3]。然而目前具有无线通信功能的便携智能设备的大量涌现，推动了DTN的发展以及在不同网络中的应用^[4]。如在野生动物研究^[5]、偏远地区网络^[6]、工程项目Wizzy^[7]、TIER^[8]等方面的应用。由于这类网络中节点移动、链路间歇性连接、不存在端到端路径、数据传输延时大^[9]等原因，为完成通信，DTN使用“存储-携带-转发”的机制^[10]。节点接收消息后要根据缓存管理策略存储一定的时间，因此缓存管理策略的设计成为DTN路由机制的关键。

DTN网络不会主动丢弃已存储的消息，除非该消息的生存时间(time to live，TTL)到期。因此采用何种策略确定缓存中消息的丢弃顺序，以释放宝贵的缓存资源成为问题的关键。研究发现，已有的缓存管理算法存在两类问题：1) 算法考虑的消息特性单一，不能够很好地掌握网络环境信息；2) 考虑了多个消息特性的算法在应用阶段为网络带来过大的开销。针对这两类问题，本文提出了一种基于消息特性的MPBBM算法，它主要根据消息副本数以及消息生存时间来确定每条消息的重要度，以此确定该消息被丢弃的先后顺序。

已有的缓存管理算法主要包括DO(drop- oldest)^[12]、SHLI(shortest life time)^[13]及MOFO(most forwarded)^[13]。此类算法的特点是考虑消息的某个单一特性，比较不同消息的特征值，决策消息的替换。优点是计算时间短、空间开销少；缺点是考虑因素单一，性能还有很大提升空间。

目前改进的缓存管理算法有很多。如对消息副本数进行估计的缓存管理EBMP(enhanced buffer management policy)^[14]算法，控制节点消息数量的MDC-SR(message drop control source relay)^[12]算法。

EBMP算法引入了消息的3个特性。该算法能较好地估计消息在网络中的副本数，并对估计的最多副本数的消息进行替换。然而由于需要大量的计算过程，导致节点缓存及网络开销较大、消息延时较长。

MDC-SR算法通过定义节点丢弃消息数的阈值防止出现过多的消息丢弃，这种控制可以减少不必要的消息转发和丢弃。但其阈值的定义并没有数学方法上的依据，在消息大小等条件发生变化的网络环境下，性能将受到很大影响，网络性能不稳定。

ISM(intelligent subsection management)^[15]算法通过引入消息相对存活时间的特性对消息有效性进行分析，而该算法适用于节点分布稠密的网络。

ABMP(area-based buffer management policy)算法^[16]是从网络地理环境考虑，通过估计消息在划分区域中数目以及对节点的运动特性进行分析来决定丢弃消息的丢弃顺序，该算法同样存在计算量较大的问题。

DPMQ(dynamic prediction based multi queue)^[17]丢弃算法是在节点生成3个动态的队列，根据预测的消息交付概率，在不同限定条件下缓存至不同的消息队列。但该算法只能应用于概率路由，适用场景比较局限。本文提出的MPBBM算法在保证较低计算量的基础上，结合消息特性，提高消息的交付率、网络开销等网络性能，并确保该算法能适用于各类基于Epidemic洪泛思想的多副本路由协议。

已有的缓存管理算法中，MOFO在不同网络环境配置下，相比于其他缓存管理算法性能较好，消息的交付率虽然维持在较高水平，但消息的平均

延时较大。针对此问题，本文提出了一种基于消

息特性的缓存管理(message-period-based buffer management，MPBBM)算法。该算法在考虑MOFO算法中消息被转发次数的基础上，引入了消息在网络中的生存时间这一特性。

MPBBM的主要思想是，在节点缓存空间不足以接收新到来的消息时，节点遍历当前缓存中的消息列表。获取缓存中每条消息的生存时间，并获取消息在网络中被转发的次数，将两者进行归一化处理后形成节点中每条消息的MPBBM值：

式中，M_mpbbm表示消息M的MPBBM值；M_age为消息M自创建后在网络中存在的时间；M_fo为消息M被网络中节点转发的总次数。

在DTN的网络环境中，当消息的age值单位为秒时，消息的age值增长速度将远高于消息的fo值，因此为将消息的fo值和age值在数量级上进行归一化，对消息的age值取自然对数log(M_age)，利用对数函数的特性使处于不同量纲消息的fo值和age值处于同一数量级。

采用MPBBM算法计算出的M_mpbbm值能反映消息的优先级，值越大，则消息的age值和fo值的归一和的值越大。根据统计规律，在网络中存在时间越长、被转发的次数越多越有可能成功交付，则认为消息的优先级越低。MPBBM算法定义的参数如表 1所示。

表1

表1 MPBBM算法参数表

表1 MPBBM算法参数表 参数名称 参数含义 size 节点新到来的消息的大小 BufferSize 节点缓存空间的总量 FreeBuffer 当前节点剩余缓存空间大小 Msize 消息M的大小 Messages 当前节点缓存中的消息列表 Mmpbbm 消息M的MPBBM值 Mage 消息M在网络中存在的时间值 Mfo 消息M被转发的次数 MAXmpbbm 节点中MPBBM值最大的消息

MPBBM算法在替换消息时，依据每条消息的MPBBM值进行降序排序，该算法认为优先级高的消息为活跃消息，而优先级低的消息为非活跃消息，因此排序的结果为活跃度依次降低的消息队列。表 2为MPBBM算法优先替换非活跃消息的算法伪代码。

表2

表2 MPBBM算法伪代码

表2 MPBBM算法伪代码 Algorithm：MPBBM 语句频度 Begin dropMPBBMMessage(size) If size > BufferSize Exit End if While FreeBuffer < size do： M = getMPBBMMessage(); deleteMessage(M) FreeBuffer += Msize End while End dropMPBBMMessage() Begin message getMPBBMMessage () calculateMPBBMValue() MAXmpbbm= null For M $ \in $Messages do： If MAXmpbbm is null MAXmpbbm = M End if If Mmpbbm> MAXmpbbm MAXmpbbm = M End if End for Return MAXmpbbm End message getMPBBMMessage () Begin calculateMPBBMValue() For M $ \in $Messages do： Mmpbbm = log(Mage) + Mfo End for End calculateMPBBMValue() 1 1 n n n n n n n2 n2 n2 n2 n2 n2 n n2 n2

MPBBM算法考虑了消息的两个特性，即消息在网络中的生存时间和消息被转发的次数，两个参数均能体现消息在网络中的分布情况。消息在网络中的生存时间越长或消息被转发的次数越多，则在网络中可能存在较多的消息副本，替换副本较多的消息将不会对该消息的交付带来过多不良影响，同时为副本数较少的消息提供更多的转发机会。

另在引入新的消息特性时，并没有带来过多额外的存储需求和复杂的计算过程。当节点进行消息替换时，更新消息的age值和fo值，并计算缓存中消息的MPBBM值，不需额外维持消息的MPBBM值列表。MPBBM算法的执行发生在节点间进行消息转发时，由接收消息的节点执行。缓存管理算法是一个循环执行的过程。根据表 2的语句频度计算出该算法的时间复杂度为$T(n) = O({n^2})$，与MOFO的时间复杂度相同。MOFO的空间复杂度为O(1)，由于需要临时存储节点携带的消息的MPBBM值，MPBBM的空间复杂度为O(n)。可见MPBBM没有增加额外的时间复杂度，并且未带来过多的空间复杂度。

本文采用ONE(opportunistie networking environment)^[18]仿真工具，结合典型洪泛算法Epidemic^[19]，对MPBBM与其他缓存管理算法分别进行了仿真和对比分析。仿真中共投放了5组节点模拟行人、车辆的移动，为了充分模拟现实生活的场景，在地图中设置了兴趣点，兴趣点即节点趋于移动到达的目的地，具体的环境参数设置如表 3所示。

表1

表3 仿真参数表

表3 仿真参数表 参数含义 设置 仿真地图大小 4 500 m×3 400 m 仿真时间/s 43 200 节点组中的节点数 40 节点传输速度/ kB×s-1 250 节点通信范围/m 10 节点组数目 5 节点移动模型 ShortestPathMap- BasedMovement 节点路由 EpidemicRouter 节点缓存大小/MB 10 节点停留时间/s 0~120 节点移动速度/m×s-1 0.5~1.5 消息初始剩余生存时间/ min 330 消息产生的时间间隔/s 30~35 产生消息的大小/kb 100~300

本文使用4个性能评价指标：消息交付率、网络开销、平均延时和平均缓存时间。

消息交付率为最终交付的消息数与产生的消息数的比值；网络开销为未成功交付的消息数与成功交付的消息数之比；平均延时为消息从产生到成功递交到目的节点的消息的延时平均值；平均缓存时间为所有消息在网络中占用缓存时间的平均值^[11]。

图 1显示了消息大小变化时，各缓存管理算法的性能表现。

图 1

图 1 消息大小对缓存管理算法性能的影响

如图 1a、图 1b所示，不同缓存管理下的Epidemic路由协议消息交付率、网络开销普遍降低。MPBBM算法的消息交付率一直保持最高，消息交付率相比MOFO算法平均提高8.14%，网络开销平均值降低了9.82%，同与MOFO算法性能表现相近的SHLI算法相比，MPBBM算法消息交付率平均高出11.22%，网络开销平均值降低10.42%。EBMP和DO算法性能较差，其中DO算法的传输成功率最低，数据波动较小，说明消息大小对DO算法的消息交付率的影响不大。EBMP算法网络开销最大，原因是在该仿真环境下，应用EBMP算法缓存管理算法的Epidemic协议时，参与网络中被中继传输的消息数量远大于应用其他缓存管理算法的情况，且传输成功消息的数量更低，导致网络开销远大于应用其他它缓存管理算法时的网络开销。

由图 1c所示，MOFO算法的平均延时最大，MPBBM相比MOFO算法，平均延时降低了31.59%，且消息越大时，平均延时比MOFO算法下降的越快，说明MPBBM算法缓存管理算法使得消息传输具有更好的实时性，但MPBBM算法的平均延时略高于SHLI算法，通过分析仿真实验数据发现，采用MPBBM算法缓存管理算法的Epidemic协议仿真时中继转发的消息数量更多，需要消耗额外的时间，而且MPBBM算法中涉及的计算过程也要比SHLI算法额外消耗一定的时间。

如图 1d所示，MPBBM算法的平均缓存时间比MOFO算法平均增长了7.53%，通过分析仿真实验数据发现，MPBBM算法丢弃消息的数量与MOFO算法相比有所减少，也相应地降低了网络开销。DO算法的平均缓存时间最大，平均缓存时间过大，说明消息占用缓存时间过长，会造成转发消息数量减少，降低消息转发成功率。

图 2显示了节点缓存大小变化时，各缓存管理算法的性能表现。

图 2

图 2 节点缓存大小对缓存管理算法性能的影响

由图可知，MPBBM算法的消息交付率最高。与MOFO算法相比，MPBBM算法的消息交付率平均增长了7.57%，网络开销平均降低了10.97%，平均延时显著降低了44.06%。然而MPBBM算法的平均缓存时间与MOFO算法相比平均提高了5.36%，可见MPBBM算法没有带来过多额外的平均缓存时间，且适当地减少了消息的过度丢弃，相应地降低了网络开销。

图 3

图 3 消息产生频率对缓存管理算法性能的影响

图 3显示了消息产生频率变化时，各缓存管理算法的性能表现。与MOFO算法相比，MPBBM算法的消息交付率提高了4.93%，网络开销平均降低了3.34%，平均延时减少了29.10%。然而MPBBM算法与MOFO算法相比平均缓存时间平均提高了6.67%，说明在保证消息交付率、降低网络开销和平均延时的同时，未过度占用节点缓存。

图 4显示了节点通信范围变化时，各缓存管理算法的性能表现。

图 4

图 4 节点通信范围对缓存管理算法性能的影响

图 4中，MPBBM算法持续保持较高的消息交付率。与MOFO算法相比，MPBBM算法平均提升了5.49%，网络开销平均降低了5.41%，平均延时平均降低了47.74%。然而平均缓存平均提高了8.50%，表明MPBBM算法在提升其他性能的同时，不过度地带来额外的缓存时间，不会过度损耗节点的缓存资源。

本文结合Epidemic路由协议，提出了一种基于消息特性的缓存管理MPBBM算法。该算法结合了消息在节点缓存中存在的时间及消息转发次数两个特征值，能够较好地估计消息在网络中的分布情况。该算法的时间复杂度$T(n) = O({n^2})$，空间复杂度为$O(n)$。与MOFO算法相比，MPBBM算法没有增加时间复杂度，也未带来过多的空间复杂度。通过仿真发现，在不同消息大小、消息产生频率、节点缓存大小、节点通信范围的影响下，MPBBM算法明显优于其他缓存管理算法，显著地降低了消息的延时，在提高消息交付率的同时降低了网络开销。它适用于网络区域中消息较小的场景，并可适应消息产生较为频繁的网络。如何进一步降低该算法平均缓存时间是下一步工作方向之一。