延迟容忍网络(delay tolerant network, DTN)是一种在源节点和目标节点之间难以形成稳定的端到端连接链路、利用节点移动带来的相遇机会进行通信的自组织网络[1].正是由于DTN的这种通信特点，其采用“存储-携带-转发”的路由机制[2]，消息由中间节点携带并随其移动，直至到达目标节点.DTN适用于大传输时延、间歇性连接、高误码率的极限通信环境，在灾难应急[3]、车载网络[4]、星际网络[5]、手持设备组网[6]等领域具有广泛的应用前景，并将成为未来普适计算和泛在网络的重要接入技术.因此DTN被认为是实现“无处不在的网络”的一项关键技术，具有重要的研究意义.
在DTN路由算法中，SaW(spray and wait)[7]算法能够在控制消息副本的前提下实现消息的高效投递.该算法在Spray(喷射)阶段采用对称分配消息副本数，在Wait(等待)阶段进行消息的被动传输.文献[7]证明了在独立同分布的节点移动模型中SaW算法是最优的，但是在大多数情况下并不存在严格的独立同分布移动模型，因此SaW算法仍然有较大的改进空间.
目前对SaW算法的改进主要体现在3个方面：1)在Spray阶段筛选中继节点，根据效用函数选择高效的候选节点作为下一跳，有利于提高消息投递率[8]；2)在Spray阶段喷射适当比例的副本，根据不同节点的质量和表现，分配不同的副本数量，使副本快速扩散，有效传递[9-10]；3)改进Wait阶段的传输策略[11].然而，目前大多数SaW改进算法只是根据其中的1个或2个方面进行研究，很少考虑将这3个方面综合起来对SaW进行改进，性能提高并不明显.
基于以上分析，本文将中继节点选择、自适应分配消息副本数量以及Wait阶段的改进综合考虑进来，提出一种基于节点综合性能的自适应喷射等待路由算法(adaptive spray and wait routing algorithm based on comprehensive performance of node, CPN-ASW).主要贡献有5个方面：
1) 定义了节点相似度来反映节点运动轨迹的相似程度，利用节点相似度控制消息转发条件，避免消息在运动轨迹相似的节点间传输，网络开销增大，投递率无明显变化情况的发生.
2) 引入节点活跃度概念来反映节点与其他节点的相遇能力，从而将较多的消息副本分配给活跃度高的节点，使消息能够在短时间内扩散至较多的节点上.另外，采用划分等长的时间窗口来更加准确地估计节点活跃度.
3) 结合节点活跃度和剩余缓存，提出节点相对效用值的概念.根据节点间的相对效用值自适应分配消息副本数，给活跃度高、剩余缓存多的节点分配更多的消息副本，使消息在网络中扩散得更广，进而提高消息到达目标节点的可能性.
4) 在Spray阶段提出基于节点相似度和节点相对效用值的喷射策略，使在副本受限的情况下，消息得到有效扩散.
5) 在Wait阶段充分利用节点间的相遇机会，提出基于节点投递预测值的主动转发策略，进一步降低传输时延.
1 相关工作
目前，在DTN的研究中，路由算法主要分为单拷贝路由协议和多拷贝路由协议.典型的单拷贝路由协议有Direct Delivery[12]和First Contact[12].这2种路由协议网络开销小，但是传输时延很高，且消息成功到达目标节点的概率很低.多拷贝路由协议中最具代表性路由协议有Epidemic[13]和Prophet[14].Epidemic是一种洪泛式路由算法，携带消息的节点向遇到的每一个节点都复制消息，其在网络资源较充足的条件下投递率较高，且传输时延低，但是在真实的网络场景中，网络资源往往受限，其盲目复制会导致网络开销巨大，最终降低网络性能；Prophet算法利用节点间相遇历史信息和传递性定义一个投递预测值指标来描述节点之间成功传输消息的概率，每当2个节点相遇时，选择到达目标节点投递预测值更高的节点作为消息中继节点，但是Prophet本质上仍是消息复制路由，相比Epidemic网络开销明显减小，但由于进行中继节点筛选，消息到达目标节点时延较大.
为了将Epidemic算法消息投递的高效性与单副本直接传输的简洁性相结合，相关研究者提出了SaW路由算法.该路由算法由Spray和Wait这2个阶段组成，消息产生后，通过初始化消息副本数量来显示消息转发次数.SaW算法采用了2种模式，即Binary和非Binary模式.Binary模式下，在Spray阶段，携带某消息副本数大于1的节点向遇到的未缓存该消息的节点转发此消息一半副本，自身保留剩下的消息副本；当节点中某消息副本数为1时，节点转入Wait阶段，消息以Direct Delivery的方式进行传输，即携带消息的节点直至遇到目标节点才将消息转发出去.Binary SaW可应用于多类场景中，其综合性能要高于Epidemic和Prophet.该算法适用于节点均等分布、运动随机的延迟容忍网络，然而在真实的网络环境中，节点运动不完全随机，且节点将消息传输到目标节点的能力是不同的，因此，SaW算法在Spray阶段的对称分配副本数是不灵活的，并且在Wait阶段的被动传输会进一步增加传输时延.针对SaW算法的主要弊端，目前国内外研究者已在SaW的改进上取得了一些成果.
文献[8]对Prophet算法中定义的投递预测值做了进一步改进，节点间的投递预测值不仅考虑相遇次数，还结合了节点间的连接时间.在Spray阶段根据消息到目标节点的投递预测值筛选中继节点，Wait阶段同样执行此操作，直至消息到达目标节点.文献[9]结合节点的投递预测值和节点相似度作为节点效用值，按照此效用值自适应分配副本数.文献[10]提出基于节点历史相遇信息的路由算法EBR，该算法直接根据节点活跃度自适应地分配消息副本数，将更多的消息副本分配给活跃度更高的节点.文献[15]提出一种基于节点社会性的喷雾等待路由协议BSW-SN，该算法在Spray阶段根据节点的移动模式和节点对消息的转发效能来优化对中继节点的选择，然后按照节点的活跃度自适应分配消息副本数.文献[16]提出一种基于节点质量度的路由算法QoN-ASW，在Spray阶段考虑节点的质量度作为消息副本分配的依据；在Wait阶段将消息转发给到目标节点投递预测值更高的中继节点，从而减少消息传输时延.文献[17]提出基于相遇概率的喷射等待路由算法PBSW，在Spray阶段选择与目标节点相遇概率更高的相遇节点作为中继节点，然后根据两者与目标节点的相遇概率分配适当比例的消息副本.然而，上述文献只是从筛选中继节点、灵活分配消息副本数、改进Wait阶段传输策略中的1个或2个方面进行改进，从而改进策略不够全面.
基于以上分析，本文综合考虑中继节点选择、自适应分配消息副本数量、改进Wait阶段传输策略这3个方面，提出一种基于节点综合性能的自适应喷射等待路由算法CPN-ASW.该算法在Spray阶段根据节点间的相似程度是否超过给定阈值而采用不同的中继节点选择策略，考虑相遇节点间的活跃度和剩余缓存作为节点的相对效用值，当节点间的相似程度小于给定阈值，直接根据节点的相对效用值自适应地分配消息副本数，否则，选择合适的中继节点后再根据节点相对效用值分配消息副本数；进一步为充分利用节点间的相遇机会，在Wait阶段将副本数为1的消息转发给到目标节点投递预测值更高的中继节点.
2 问题模型
2.1 网络模型
假设网络中包含n个节点，G=(V,E)为网络拓扑图，V={vi|1≤i≤n}表示网络中的节点集合，E为定义在G上的边集，代表节点对之间的连接.每个节点vi维护一个历史相遇节点集合Ei={vj|ni,j≠0}，该集合记录从仿真开始节点vi遇到过的每个节点.当节点vi和vj进入到彼此的通信范围内，vi检测Ei中是否包含节点vj，若节点vj不包含在Ei中，则节点vi将vj添加到Ei中，并且将Ei中的ni,j值加1；若节点已包含在Ei中，说明两节点曾经相遇过，此时只将Ei中的ni,j加1.
2.2 节点相似度
我们在大多数的DTN应用场景中，具有通信功能的移动设备大多是由人类随身携带的，人类的移动模式不是完全随机的，他们会表现出一定的社会特征.例如，如果2个人拥有1个或者多个共同的朋友，那么这2个人成为熟人的可能性很高，这种现象称为“聚类”，即这2个人的运动轨迹相似.如果消息在运动轨迹相似的节点间转发，那么在增大网络开销的同时，对提高投递率并没有实质性的帮助.因此，在本文中提出节点相似度的概念来表示节点间运动轨迹的相似程度，如果2个节点间的相似度高，则需提高消息转发条件，进而减少不必要的转发次数.
定义1. 节点相似度.节点vi与节点vj间的相似度是指节点vi和节点vj的历史相遇节点集合中拥有的共同历史相遇节点的个数与这2个节点中较大历史相遇节点集合中节点个数的比值，记为SD(i,j)，其表示为
(1)
如果SD(i,j)越大，即节点间的相似度越高，意味着节点vi和节点vj的运动范围和接触节点越相似.
2.3 节点活跃度
在DTN中，活跃的节点能够快速传递消息，使消息在较短的时间内扩散至较多的节点上，从而提高投递率，降低传输时延.然而，DTN中网络拓扑结构频繁变化，节点相遇其他节点的能力在较长的仿真时间内可能波动比较大，因此，本文中通过划分等长的时间窗口来更加准确估计节点活跃度，每当1个时间窗口到期，就更新节点活跃度.节点活跃度反映了节点向网络中扩散消息的能力.
假设节点vi当前运动时刻位于第k+1个时间窗口内，在第k+1个时间窗口内相遇节点的数量是未知的，本文通过历史k个时间窗口算出的活跃度估计vi在当前时间窗口内的活跃度.
定义2. 节点活跃度.节点vi的活跃度是指vi在当前时间窗口相遇其他节点的能力，记为
其表示为
(2)
其中，
就是预估节点vi在第k+1个时间窗口内遇到的不同节点的数量；k表示节点vi经历完整时间窗口的数量；
表示最近1个完整时间窗口内节点vi遇到不同节点的数量，每当1个时间窗口到期，就清0，开始重新统计新的时间窗口内相遇节点的数量；
表示从仿真开始至第k-1个时间窗口到期更新后节点vi的活跃度.当k=1时，即节点vi经历过第1个完整时间窗口，此时节点vi在第k+1个时间窗口内的活跃度直接表示为在第1个时间窗口内所遇到的不同节点的数量；当k>1时，节点vi在第k+1个时间窗口内的活跃度表示为从仿真开始到第k-1个时间窗口到期更新的和由第k个窗口内计算得出的的加权和，其中α为活跃度平滑因子.
2.4 节点相对效用值
为了使CPN-ASW的Spray阶段副本分配更具有合理性，本文根据节点间的相对效用值对副本进行分配.节点的活跃度越高，则未来遇到目标节点的可能性越大，则给活跃度高的节点分配更多的消息副本，这会造成活跃度高的节点易发生缓存溢出的情况，造成消息丢包次数较多，反而没有体现出活跃度高的节点能使消息在网络中快速扩散的优势.为了缓解活跃度高的节点上的拥塞程度，则同时将节点剩余缓存作为消息副本分配的依据，如果节点很活跃，但是剩余缓存已不足，则避免将较多的消息副本分配给此节点，防止节点频繁拥塞导致消息丢包次数明显增加，从而使较多的消息副本不能被有效传递.因此本文综合利用节点的活跃度和剩余缓存，来体现节点相对效用值的高低.节点的活跃度越高，剩余缓存越多，其相对效用值越高,得到的转发该消息的次数越多.
定义3. 节点相对效用值.当节点vi和节点vj在第k+1个时间窗口内相遇时，节点vi的相对效用值记为Ui，其计算为
(3)
其中，w∈(0,1)是相对效用值参数，和FBi与
和FBj分别表示节点vi和节点vj在第k+1个时间窗口内相遇时的活跃度和剩余缓存大小.
2.5 节点投递预测值
在DTN中，节点运动并非完全随机.如果节点vi和vj在过去的时间内接触比较频繁，那么未来它们的相遇概率也会比较高.Prophet路由算法正是基于历史预测策略的代表.该算法利用节点间的相遇历史信息和传递性来定义投递预测值(delivery probability)，利用投递预测值来描述节点间的相遇概率.当节点vi和vj相遇时，只有vj到消息目标节点的投递预测值更高时，vi才将消息传输给vj，通过这种有选择地复制消息副本，有效地降低网络开销.
假如用P(i,j)来表示节点和节点间的投递预测值，P(i,j)的计算分为3个过程：更新、衰减和传递性.
1) 更新.当节点vi和vj相遇并建立连接时，更新投递预测值：
P(i,j)=P(i,j) old+(1-P(i,j) old)×Pinit,
(4)
其中，P(i,j)表示节点vi和vj间的历史投递预测值，Pinit∈[0,1]是初始化常量.
2) 衰减.当节点vi和vj在一段时间内没有遇到彼此，对投递预测值进行衰减：
P(i,j)=P(i,j) old×yc,
(5)
其中，y表示衰减因子，c表示节点vi和vj从上次相遇到目前为止所经历的时间块的个数.
3) 传递性.节点投递预测值也具有传递性，根据观察，如果节点vi经常遇到节点vj，而节点vj经常遇到节点vh，那么对目标节点为节点vi的消息而言，节点vh可能是一个很好的中继节点.这种传递性如何投递预测值P(i,h)：
P(i,h)=P(i,h) old+(1-P(i,h) old)×
P(i,j)×P(j,h)×β .
(6)
3 CPN-ASW路由算法
基于节点综合性能的自适应喷射等待路由算法CPN-ASW分为Spray和Wait这2个阶段.在Spray阶段，提出基于节点相似度和节点相对效用值的喷射策略；在Wait阶段，提出基于节点投递预测值的主动转发策略.
3.1 Spray阶段
在真实的DTN应用场景中，大量的移动设备通过人来携带，人的行为具有很强的社会性.例如，拥有相同兴趣爱好的人通常会聚集在一起，即这些人的运动轨迹相似.在副本受限的情况下，应提高消息在相似度高的节点间的转发条件，避免网络开销增大，投递率却无明显提高情况的出现.另外，不同种类的节点缓存、移动速度不尽相同，因此承担消息转发任务的能力也有高低.在本文中通过定义节点相对效用值来描述节点转发消息的能力，给相对效用值高的节点分配更多的消息副本，有利于消息得到有效扩散.
基于以上分析，本节提出一种基于节点相似度和节点相对效用值的喷射策略.根据节点相似度是否超过阈值采用不同的中继节点选择策略，确定好中继节点后，按照节点相对效用值分配消息副本数量.具体喷射策略如下.
当节点vi和节点vj相遇时，若节点vj不携带vi持有消息ml，节点vi向节点vj分配消息ml副本数量的步骤为：
1) 判断节点vj是否是目标节点，若是，则节点vi直接将消息的一个副本传递给vj，同时删除该消息;否则，执行步骤2)或步骤3).
2) 若节点间的相似度SD(i,j)≥τ,说明这2个节点相遇节点集合高度重叠，此时为减少消息在运动范围大致重叠且相对效用值相差不大的节点间的转发次数，若满足：
Uj>Ui+Uth×SD(i,j),
(7)
则节点vi确定节点vj为中继节点；否则，vi等待与目标节点或其他节点相遇.其中，τ为相似度阈值，Uth为效用参数.
若转发条件满足式(7)，根据节点vi和节点vj的相对效用值按比例分配消息副本数，设节点vi中的消息ml副本数为Li old(ml)，分配给节点vj的消息副本数Ljnew(ml)为
Lj new(ml)=
Uj×Li old(ml)
.
(8)
节点vi自身保留消息ml副本数Li new(ml)为
Li new(ml)=Li old(ml)-Lj new(ml).
(9)
3) 若节点间的相似度SD(i,j)<τ，说明这2个节点的运动范围相似性较小，此时为了消息的传播范围更广，直接按照节点相对效用值在节点间按比例分配消息副本数，分配给vj的消息ml副本数Ljnew(ml)如式(8)所示，节点vi剩余消息ml副本数Li new(ml)如式(9)所示.
当节点vi和节点vj相遇，vi向vj分配消息副本过程如算法1所示：
算法1. Spray阶段算法.
输入：节点vi和节点vj相遇；
输出：vi即将发送给vj的副本数大于1的消息集合MforwardList.
① 节点间相互交换变量
② 根据式(1)更新SD(i,j)；
③ 根据式(3)计算Ui,Uj；
④ FOR ∀ml∈viand ml∉vj
⑤ IF Li old(ml)>1 THEN
⑥ vd=ml.destination；
⑦ IF vd==vjTHEN
⑧ 节点vi将消息ml转发给vj；
⑨ 节点vi删除消息ml；
⑩ continue；
ELSE IF SD(i,j)≥τ THEN
IF Uj>Ui+Uth×SD(i,j) THEN
Lj new(ml)=
Uj×Li old(ml)
；
Li new(ml)=Li old(ml)-Lj new(ml)；
END IF
ELSE
Lj new(ml)=Uj×Li old(ml)；
Li new(ml)=Li old(ml)-Lj new(ml)；
END IF
IF Ljnew(ml)≠0 THEN
MforwardList.add(ml,Ljnew(ml))；
END IF
IF Linew(ml)==0 THEN
节点vi删除消息ml；
END IF
END IF
END FOR
将MforwardList中的消息按剩余生存时间从大到小排序；
将MforwardList中的消息转发给节点vj.
算法1中，行⑦～⑩表示当相遇节点vj是消息目标节点时，直接将消息转发给vj并删除节点vi中此消息；行～表示当节点vi和节点vj相似度大于阈值时，筛选合适中继节点后再按照节点相对效用值计算分配消息副本数；行～表示vi和vj的相似度未超过阈值，直接按照节点相对效用值计算在节点间分配消息副本数；行～表示将符合条件的消息添加到MforwardList中；行～表示按照消息剩余生存时间从大到小的顺序将MforwardList中消息转发给vj.
假设网络中的消息总数为M，在算法1中，主要时间消耗在行④～，时间复杂度为O(M)，因此，该算法的时间复杂度为O(M).
3.2 Wait阶段
在传统的SaW路由算法中，当节点所携带的某个消息的副本数为1时，进入到Wait阶段，该阶段存在弊端：节点携带消息直到遇到目标节点才将消息转发出去，没有充分利用节点间的相遇机会.
基于上述分析，本节提出基于节点投递预测值的主动转发策略.在Wait阶段利用Prophet路由算法中的投递预测值来描述节点间成功传输消息的概率，当节点vi中持有相遇节点vj中没有的消息时，以相遇节点vj的缓存占用比来调节阈值大小，只有节点vj到消息目标节点的投递预测值大于节点vi到消息目标节点的投递预测值，并且两者到消息目标节点的投递预测值区分度大于给定阈值时，节点vi才将消息ml转发给相遇节点vj.
当节点vi中的消息ml只剩下一个消息副本时，与未缓存消息ml的节点vj相遇，若满足：
P(j,d)>P(i,d)+Pth×OBj,
(10)
则节点vi将该消息转发给节点vj.其中，P(i,d)和P(j,d)分别表示节点vi和节点vj将消息ml成功投递到目标节点vd的概率;Pth∈[0,1]为预设参数;OBj为相遇节点vj的缓存占用率.在转发过程中通过利用相遇节点vj的缓存占用比来调节节点间的投递预测值区分度，一方面避免消息在投递概率近似的节点间转发，另一方面随着相遇节点vj的缓存占用率不断增大，转发条件越来越高，从而降低网络开销，较大程度上避免了拥塞情况的出现.
在Wait阶段，节点vi和节点vj相遇时，节点vi执行的消息转发过程如算法2所示：
算法2. Wait阶段算法.
输入：节点vi和节点vj相遇；
输出：vi即将发送给vj的副本数为1的消息集合SforwardList.
① 根据式(4)更新P(i,j)；
② 节点间相互交换变量OBi,OBj；
③ FOR ∀ml∈viand ml∉vj
④ IF Li old(ml)==1 THEN
⑤ vd=ml.destination；
⑥ IF vd==vjTHEN
⑦ 节点vi将消息ml转发给vj；
⑧ 节点vi删除消息ml；
⑨ continue；
⑩ ELSE IF P(j,d)>P(i,d)+Pth×OBj
THEN
SforwardList.add(ml,1)；
节点vi删除消息ml；
END IF
END IF
END FOR
将SforwardList中的消息按剩余生存时间从大到小排序；
将SforwardList中的消息转发给节点vj.
算法2中，行⑥～⑨表示当节点vj是消息目标节点时，直接将消息转发给vj并删除节点vi中此消息；行⑩～表示当节点vj不是消息目标节点时，只有满足式(10)才将消息转发给vj，同时vi删除此消息；行～表示按照消息剩余生存时间从大到小的顺序将SforwardList中消息转发给vj.
4 仿真结果与分析
4.1 仿真环境配置
实验采用ONE[18]仿真平台，将CPN-ASW与Epidemic，SaW，EBR，PBSW在相同实验环境下进行对比.仿真采用ONE自带的赫尔辛基市地图作为移动场景，大小为4 500 m×3 400 m，节点数量设置为126个，共分为3类节点：行人、出租车、有轨电车.其中行人组80个节点，出租车组40个节点，这2组按照基于地图路线的最短路径模型移动，有轨电车组共6个节点，按照基于地图的固定路线模型移动.具体的仿真参数设置如表1所示，其他参数采用ONE平台自带的默认设置.对于初始常量Pinit、传递因子β、衰减参数y这3个参数设置可参考文献[14]中设定的值，取Pinit=0.75,β=0.25,y=0.98.
Table 1 Simulation Parameters
表1 仿真参数
参数值仿真时间∕s43200消息生存周期∕min250节点缓存大小∕MB12消息产生间隔∕s25～35消息大小∕MB0.5～1消息初始副本数16传输速率∕Kbps250传输范围∕m10τ0.8Uth0.1Pth0.5α0.8w0.3
4.2 评价指标
1) 投递率
投递率=成功投递到目标节点的消息数量/网络中源节点产生的消息数量.
2) 平均时延
平均时延=网络中所有被成功投递的消息从源节点产生开始到目标节点完整接收到所经过的平均时间.
3) 网络开销
网络开销.冗余的中继转发次数/成功投递到目标节点的消息数量.
4) 平均跳数
平均跳数.网络中所有被成功投递的消息从源节点产生开始到目标节点完整接收到所经过的平均跳数.
4.3 参数设置实验
4.3.1 活跃度平滑因子α设置
α的取值对CPN-ASW算法的实验效果影响较大，在表1参数设置条件下更改α取值，综合考虑投递率和平均时延，α=0.8时实验效果最佳.如图1所示:
Fig. 1 Performance comparison of CPN-ASW under different α
图1 CPN-ASW在α不同取值下的性能比较
从图1(a)中可以观察到，α=0.6时投递率最高，根据Markov预测法[19]，任何事件可通过其目前的状况来预测该事件将来各个时刻(或时期)的变动状况.由此可知近期活跃度高的节点在未来一段时间内也将延续较高的活跃性.当α取值偏重于最近1个完整时间窗口活跃度时，更能准确预测节点在未来一段时间的活跃度.但是同时观察图1(b)，α=0.6时投递率最高，此时平均时延也最高.所以综合考虑投递率和平均时延，α=0.8时投递率比α=0.6时要略低，但平均时延有了明显的改善，所以本文中α=0.8时实验效果最佳.
4.3.2 相对效用值参数w设置
w的取值直接影响消息副本分配数量的合理性，本文通过在w不同取值下的投递率变化，得出w=0.3时投递率最高，如图2所示:
Fig. 2 Delivery ratio of CPN-ASW under different w
图2 CPN-ASW在w不同取值下的消息投递率比较
4.4 算法比较及分析
为了验证CPN-ASW算法的高效性，进行了2组仿真实验，在不同的消息生存周期(TTL)、不同的节点缓存大小下对这5种算法在消息投递率、平均时延、网络开销、平均跳数这4个方面进行评估.实验结果表明CPN-ASW在提高消息投递率、控制网络开销、降低平均时延方面效果显著.
1) 不同消息生存周期
在4.1节的环境配置下，改变消息生存周期，对比各种算法在不同消息生存周期下消息投递率(如图3所示)、平均时延(如图4所示)、网络开销(如图5所示)、平均跳数(如图6所示)这4个方面的变化情况.
Fig. 3 Delivery ratio under different TTL
图3 不同消息生存周期下的投递率
图3显示了各种算法在不同消息生存周期下消息投递率的变化情况.其中CPN-ASW算法的投递率最高，相比Epidemic平均提高了58.55%，相比SaW平均提高了3.60%，相比EBR平均提高了1.20%，相比PBSW平均提高了11.22%.这主要归结于2个原因：1)CPN-ASW算法在Spray阶段根据节点间相似程度是否超过阈值而采用不同的中继节点选择策略，并根据节点间相对效用值实现自适应分配消息副本数，避免消息的盲目转发；2)在Wait阶段实现消息主动转发，选择到目标节点投递预测值更高的中继节点进行转发.同时从实验结果可以看出，Epidemic算法的投递率远低于其他算法，并且曲线呈现下降趋势，这是因为此算法没有限制消息副本的最大拷贝数，随着消息生存周期的增加，消息在有限缓存中驻留时间更长，盲目洪泛易导致网络中挤压大量消息副本，引起网络拥塞，消息投递率反而下降.
图4评估了各个算法平均时延的变化情况.5种算法的平均时延随着消息生存周期的增加大体上呈现增长态势，因为增加生存周期使原来在短时间内不能到达目标节点的消息能被成功投递.其中CPN-ASW的平均时延最小，相比SaW下降了4.44%，相比EBR下降2.08%，相比PBSW下降9.67%.这主要是因为CPN-ASW算法在Wait阶段实现了消息主动转发，选择更优的中继节点进行传输，加快了消息到达目标节点的速度.Epidemic算法采用洪泛机制，过多的复制消息容易使网络陷入拥塞，故平均时延相比其他算法来说是最大的.
Fig. 4 Average delay under different TTL
图4 不同消息生存周期下的平均时延
图5比较各个路由算法的网络开销.由于SaW，EBR，PBSW，CPN-ASW均在一开始限制了消息副本拷贝数，也就是限制了转发次数，故网络开销远低于Epidemic算法.CPN-ASW算法网络开销相对SaW平均下降17.71%，这是因为相对SaW算法在Spray阶段盲目转发，CPN-ASW算法在Spray阶段避免消息在运动范围相似的节点间转发，在一定程度上减少了不必要的中继转发次数，在Wait阶段自适应控制转发条件，最终网络开销较小.从图5中还可看出，PBSW算法的网络开销最小，其原因主要体现在2个方面：1)Spray阶段只将消息转发给与目的节点相遇概率更高的节点，从而消息转发次数受到限制；2)在Wait阶段没有任何优化策略，直到与目的节点相遇时才将消息转发出去，不存在冗余的中继转发次数.
Fig. 5 Overhead ratio under different TTL
图5 不同消息生存周期下的网络开销
图6比较了各个算法的平均跳数.其中CPN-ASW相对SaW平均跳数下降4.22%，主要原因在于CPN-ASW在Spray阶段当节点间运动范围高度相似时选择更优的中继节点分配消息副本数，在Wait阶段虽然进行主动转发，但是自适应控制转发条件，最终平均跳数还是明显低于SaW.其中PBSW的平均跳数最低，有2个原因：1)Spray阶段对中继节点的选择更为苛刻，只给到目的节点投递预测值更高的中继节点分配消息副本；2)Wait阶段被动等待，直到遇到目的节点才进行消息投递.
Fig. 6 Average hop under different TTL
图6 不同消息生存周期下的平均跳数
总体来看，在不同的消息生存周期下，CPN-ASW相比其他4种算法均表现出较高的投递率和较低的平均时延.并且在网络开销和平均跳数方面较SaW也表现出明显的优势.PBSW算法虽然在网络开销和平均跳数方面表现最优，但是相对于其他3种限制消息副本数的算法(SaW，EBR，CPN-ASW)来说，投递率和平均时延方面均表现出明显的劣势.另外也可看出，Epidemic算法性能最差，说明在资源受限的真实场景中，洪泛式的转发算法并不能取得良好的效果.
2) 不同节点缓存大小
在不同节点缓存大小下，比较和分析各个算法在消息投递率(如图7所示)、平均时延(如图8所示)、网络开销(如图9所示)、平均跳数(如图10所示)这4个方面的变化情况.
图7显示了各个算法在不同节点缓存下消息投递率的变化情况.5种算法的投递率都随着节点缓存的增加而提高，这是因为节点缓存越大，其所能携带的消息数量也越多，由于网络拥塞导致的丢包情况会逐渐缓解，其中CPN-ASW算法的投递率最高，相比Epidemic平均提高了67.07%，相比SaW平均提高了5.28%，相比EBR平均提高了2.55%，相比PBSW平均提高了9.12%.
Fig. 7 Delivery ratio under different buffer sizes
图7 不同缓存大小下的投递率
图8比较了各个算法的平均时延.CPN-ASW的平均时延相比PBSW平均下降10.26%.从图8中还可观察到，在节点缓存小于12 MB时，CPN-ASW的平均时延略大于SaW；当节点缓存超过12 MB，CPN-ASW的平均时延开始小于SaW的时延.这是由于CPN-ASW在Spray阶段是按照节点间的相对效用值分配消息副本数，相对效用值综合考虑节点活跃度和节点剩余缓存，当节点缓存本身较小时，节点的缓存利用率一直都很高，相对效用值中活跃度因素的重要性更为突出，活跃度高的节点易形成拥塞，消息丢包次数变多，需要经过更多的转发次数才能到达目标节点，传输时延较大；随着节点缓存的增加，活跃度高的节点上拥塞情况得到缓解，再加上CPN-ASW在Wait阶段选择更优的中继节点进行转发，最终CPN-ASW在平均时延方面的优越性得到体现.
Fig. 8 Average delay under different buffer sizes
图8 不同缓存大小下的平均时延
Fig. 9 Overhead ratio under different buffer sizes
图9 不同缓存大小下的网络开销
图9显示的是网络开销随节点缓存的变化情况.当节点缓存逐渐增加，5种算法的网络开销都逐渐下降，这是因为缓存空间越小，节点就越有可能因为缓存占满采用消息丢弃策略，使消息经过较多的转发次数才能到达目标节点.其中CPN-ASW的网络开销较Epidemic平均下降了69.55%，较SaW平均下降了17.99%.此外，通过观察图9可知，Epidemic算法的网络开销随着缓存的增加而急速下降，这表明此算法适用于资源充足的网络，在缓存较充足时能有效降低网络开销，发挥出较好的效果.
图10比较各个算法的平均跳数.其中PBSW的平均跳数最低，CPN-ASW平均跳数和EBR算法大致相同，CPN-ASW的平均跳数相对Epidemic平均下降了17.36%，相对SaW平均下降了2.50%.这说明了CPN-ASW算法采用的中继节点选择的合理性.
Fig. 10 Average hop under different buffer sizes
图10 不同缓存大小下的平均跳数
总体来看，在5种算法中，在不同节点缓存大小下，CPN-ASW算法消息投递率最高，当缓存较充足时平均时延最小，且在网络开销和平均跳数方面也表现优越且稳定.
5 结束语
本文针对DTN长时延、间歇性连接等特点，提出一种基于节点综合性能的喷射等待路由算法CPN-ASW.该算法在Spray阶段根据节点间相似度是否超过给定阈值采用不同中继节点选择策略，并按照节点相对效用值自适应分配消息副本数；在Wait阶段将消息转发给到目标节点投递预测值更高的中继节点.由对比算法分析得出，本文提出算法能够有效提高消息投递率，控制网络开销和降低平均时延.
然而，从实验中也可观察到，CPN-ASW算法相对于传统SaW来说，在节点缓存较小时平均时延较高.为进一步降低平均时延，设置一种有效的缓存管理策略是下一步研究工作的重点.
作者贡献声明：崔建群负责提出研究选题、优化论文；孙佳悦负责设计算法、设计实验并开展实验分析；常亚楠负责设计论文框架；余东海、邬尧负责调研整理文献、协助论文实验；吴黎兵负责提出指导意见并修改论文.
[1]Xiao Mingjun, Huang Liusheng. Delay-tolerant network routing algorithm[J]. Journal of Computer Research and Development, 2009, 47(7): 1065-1073 (in Chinese)(肖明军, 黄刘生. 容迟网络路由算法[J]. 计算机研究与发展, 2009, 47(7): 1065-1073)
[2]Wang Hezhe, Wang Huiqiang, Zhu Jinmei, et al. OCIGM:An optimized control information generation method for DTN routing[J]. Journal of Beijing University of Posts and Telecommunications, 2017, 40(1): 79-83 (in Chinese)(王贺哲, 王慧强, 朱金美, 等. OCIGM: 面向 DTN 路由的优化控制信息生成方法[J]. 北京邮电大学学报, 2017, 40(1): 79-83)
[3]Trono E M, Fujimoto M, Suwa H, et al. Generating pedestrian maps of disaster areas through ad-hoc deployment of computing resources across a DTN[J]. Computer Communications, 2017, 100(1): 129-142
[4]Cuka M, Shinko I, Spaho E, et al. A simulation system based on ONE and SUMO simulators: Performance evaluation of different vehicular DTN routing protocols[J]. Journal of High Speed Networks, 2017, 23(1): 59-66
[5]Tornell S M, Calafate C T, Cano J C, et al. DTN protocols for vehicular networks: An application oriented overview[J]. IEEE Communications Surveys & Tutorials, 2015, 17(2): 868-887
[6]Xiao Mingjun, Wu Jie, Huang Liusheng. Community-aware opportunistic routing in mobile social networks[J]. IEEE Transactions on Computers, 2014, 63(7): 1682-1695
[7]Spyropoulos T, Psounis K, Raghavendra C S. Spray and wait: An efficient routing scheme for intermittently connected mobile networks[C] //Proc of ACM SIGCOMM Workshop on Delay-Tolerant Networking. New York: ACM, 2005: 252-259
[8]Yu Chen, Tu Zhongqiu, Yao Dezhong, et al. Probabilistic routing algorithm based on contact duration and message redundancy in delay tolerant network[J]. International Journal of Communication Systems, 2016, 29(16): 2416-2426
[9]Li Jianbo, Jiang Shan, Song Youmei, et al. A multi-scheme adaptive routing algorithm based on spray and wait for delay tolerant networks[J]. International Journal on Smart Sensing and Intelligent Systems, 2015, 8(4): 2136-2158
[10]Nelson S C, Bakht M, Kravets R. Encounter-based routing in DTNs[C] //Proc of IEEE INFOCOM. Piscataway, NJ: IEEE, 2009: 846-854
[11]Spyropoulos T, Psounis K, Raghavendra C S. Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility[C] //Proc of the 5th Annual IEEE Int Conf on Pervasive Computing and Communications Workshops. Piscataway, NJ: IEEE, 2007: 79-85
[12]Jones E P C, Li L, Schmidtke J K, et al. Practical routing in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(8): 943-959
[13]Vahdat A, Becker D. Epidemic routing for partially connected ad hoc networks[R]. Durham, North Carolina: Duke University, 2000
[14]Lindgren A, Doria A, Schelen O. Probabilistic routing in intermittently connected networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19-20
[15]Zhao Yuhong, Yin Zili, Zhang Xiaolin. Spray and wait routing protocol of node sociality in opportunistic network[J]. Computer Simulation, 2018, 35(7): 231-236 (in Chinese)(赵宇红, 尹自立, 张晓琳. 基于节点社会性的机会网络喷雾等待路由协议[J]. 计算机仿真, 2018, 35(7): 231-236)
[16]Cui Jianqun, Cao Shuqin, Chang Yanan, et al. An adaptive spray and wait routing algorithm based on quality of node in delay tolerant network[J]. IEEE Access, 2019, 7: 35274-35286
[17]Kim E H, Nam J C, Choi J I, et al. Probability-based spray and wait protocol in delay tolerant networks[C] //Proc of Int Conf on Information Networking. Los Alamitos, CA: IEEE Computer Society, 2014: 412-416
[18]Keränen A, Ott J, Kärkkäinen T.The ONE simulator for DTN protocol evaluation[C/OL] //Proc of the 2nd Int Conf on Simulation Tools and Techniques. New York: ACM, 2009 [2020-06-01]. https://dl.acm.org/doi/pdf/10.4108/ICST.SIMUTOOLS2009.5674
[19]Zhang Yang, Wang Xiaoming, Lin Yaguang, et al.Message forwarding strategy based on Markov decision process in opportunistic networks[J]. Journal of Frontiers of Computer Science & Technology, 2016, 10(1): 82-92 (in Chinese)(张杨, 王小明, 林亚光, 等. 基于马尔可夫决策过程的机会网络转发策略[J]. 计算机科学与探索, 2016, 10(1): 82-92)
