容迟网络中基于节点间相遇概率的路由算法

李广强 何佳

摘  要： 容迟网络DTN （Delay Tolerant Network）是物联网中的一种新型的计算机网络，该网络中的源节点和目的节点之间可能并不总是存在完整的端到端的通信链路。DTN间歇连接的特点对设计有效路由算法是巨大的挑战。文章在原有Epidemic和Prophet路由算法的基础上，提出了一种改进的基于节点间相遇概率的路由算法RAEPBN（Routing Algorithm Based on Encounter Probability Between Nodes），并详细介绍了该算法的路由建立过程。仿真结果表明，与现有的Epidemic和Prophet路由算法相比，RAEPBN在投递率、平均时延和网络开销上的性能均最优。

关键词： 容迟网络; 路由算法; 节点间相遇概率; ACK确认机制

中图分类号：TP312          文献标识码：A     文章编号：1006-8228（2021）01-33-04

A routing algorithm based on the probability of encounter between nodes

in delay-tolerant network

Li Guangqiang， He Jia

（Air Force EarlyWarning Academy， Wuhan， Hubei 430019， China）

Abstract： Delay Tolerant Network （DTN） is a new type of computer network in the Internet of Things. In DTN， a complete end-to-end communication link between the source node and the destination node may not always be available. The intermittent connection characteristics of DTN make the design of an effective routing algorithm face a huge challenge. Based on the original Epidemic and Prophet routing algorithms， this paper proposes an improved routing algorithm based on the encounter probability between nodes RAEPBN （Routing Algorithm Based on Encounter Probability Between Nodes）， and introduces the routing establishment process of the algorithm in detail. The simulation results show that RAEPBN has the best performance in delivery rate， average delay， and network overhead， compared with the existing Epidemic and Prophet routing algorithms.

Key words： Delay Tolerant Network; routing algorithm; encounter probability between nodes; acknowledge mechanism

0 引言

DTN（Delay Tolerant Network）[1-2]是一種源节点和目的节点间不存在稳定端到端的通信链路，利用节点移动带来的相遇机会进行通信的自组织网络。DTN间歇连接的特征使其可以在挑战性的环境中使用，这一特征也导致了较长的传输延迟，难以符合TCP/IP网络的基本要求[3]。因此，传统的路由算法，即使是MANET路由协议也不能应用于容迟网络中[4]。

为了支持间歇连接，DTN路由采用“存储—携带—转发”方式把消息发送到目的节点[5]。如果节点由于间断连接而不能立即发送消息，则需要将消息存储在缓冲区中，直到节点有机会将消息转发出去。近年来，国内外研究学者提出了许多路由算法以解决DTN的固有特性。Epidemic算法是一种典型的基于洪泛策略的路由算法，该算法将消息发送给所有的相遇节点。在缓存资源充足的场景中，Epidemic[6]的路由算法性能最好，然而现实的应用场景中，节点的缓存资源都是有限的。Prophet[7]路由算法利用相遇历史和传递性提出了一种基于概率估计的路由算法，节点仅将消息转发给与目的节点相遇概率高的邻居节点。为了减小网络开销，Spray and wait[8]路由算法对源节点消息的最大拷贝数进行了限制。尽管以往的研究表明DTN的各种举措都具有良好的性能，但它们也存在一些缺点。首先，Epidemic路由算法基于泛洪的策略非常浪费网络资源。其次，Prophet在同一时刻将消息转发给多个与目的节点相遇概率更高的邻居节点，这将引起消息在一些局部范围内存在多个冗余的消息副本，增加了不必要的网络开销。Spray and wait已经被证明是一个有效的方法，但该方法没有将已经成功传递到目的节点的消息进行删除，可能会导致网络中的一些节点仍然试图继续将这些被成功传递的消息投递到目的节点。

为了解决上述问题，文本提出了一种基于节点间相遇概率的路由算法RAEPBN（An Routing Algorithm Based on Encounter Probability Between Nodes）。当节点在同一时刻有多个连接机会时，RAEPBN算法将比较所有相遇节点与目的节点间的相遇概率，仅将消息转发给与目的节点相遇概率最高的邻居节点，从而避免消息在某一局部区域内存在过多的冗余副本，以减少不必要的网络开销。增加了ACK确认机制，即当某个消息被成功投递到目的节点后，RAEPBN算法会生成对应的ACK确认消息，并将该确认消息传播到网络中，其他节点在收到此ACK确认消息之后，检查自身的缓存中是否存在这条已经被成功投递的消息，如果存在则将此条已经被成功投递的消息从缓存中删除，以避免不必要的消息转发。

1 基于节点间相遇概率的路由算法

1.1 网络模型

假设网络中一共有n个节点，G=（V，E）表示网络拓扑图，V={vi |1≤i≤n}表示网络中节点的集合，E是图G上的边的集合。网络中的每个消息mk都有一个唯一标识符（mk.ID）。当一个节点生成一个新的消息mk时，将预先分配其对应的目标节点vk和生存周期。如果消息的生存周期過期，该消息将被丢弃。节点vi有一个汇总矢量属性SVi，用来记录节点vi缓存中待投递的消息。当节点vi与其他节点相遇时，节点vi选择与目的节点相遇概率最大的邻居节点vl作为中继节点。如图1所示，节点vi将汇总矢量SVi发送给与目的节点相遇概率最大的邻居节点vl，[SVl]表示与目的节点相遇概率最大的邻居节点vl缓存中没有的消息，邻居节点vl执行SVi与[SVl]间的逻辑与运算得到汇总矢量SV，即存储在节点vi缓存中且节点vl没有的消息。然后邻居节点vl向节点vi请求这些消息，最终节点vi将节点vl请求的消息发送给vl。

1.2 相遇概率的计算与更新

网络环境是相对不可预测性的，但人的移动性不是完全随机的，如果节点vi过去经常遇到节点vj，未来节点vi与节点vj很可能还会再次遇到。本文利用Prophet路由算法定义的相遇概率来反映任意两个节点间的相遇概率，如果两个节点经常相遇，那么就可以认为他们之间成功投递消息的概率更高。当两个节点相遇时，根据相遇概率决定是否将消息转发给另一个节点。相遇概率的计算包括以下三个部分。

⑴ 更新：若两个节点经常相遇，那么他们未来再次相遇的可能性更高。因此，当节点vi遇到节点vj时，相遇概率应按照⑴进行更新。其中，Pinit为初始化常数，[P（i，j）old]表示此次更新前节点vi与节点vj的相遇概率。

[P（i，j）=P（i，j）old+（1-P（i，j）old）×Pinit]   ⑴

⑵ 衰退：如果一对节点在一段时间后没有相遇，那么未来它们彼此之间成功投递消息的可能性较小，因此节点间的相遇概率必须有衰退的过程。公式⑵给出了相遇概率是如何衰退的。其中，[γ∈][0，1]为老化常数，k为自相遇概率最后一次衰退以来所经过的时间单位数。

[P（i，j）=P（i，j）old?γk]  ⑵

⑶ 传递：如果节点vi经常遇到节点vk，而节点vk又和节点vj经常相遇，那么节点vk可能是一个较好的中继节点。因此，节点间的相遇概率也具有传递性，公式⑶给出了传递性是如何影响节点间的相遇概率的。其中，β是一个常数，其决定了传递性对节点间相遇概率的影响比重。

[P（i，j）=P（i，j）old+（1-P（i，j）old）?P（i，k）?P（k，j）?β]   ⑶

1.3 RAEPBN路由算法

由于大多数现有的路由算法在同一时刻可能会将消息转发给多个邻居节点，而这多个邻居节点的位置相距较近，这将导致消息在某些局部范围内存在过多的冗余副本，增加了不必要的网络开销。因此本小节提出了一种改进的基于节点间相遇概率的路由算法RAEPBN。在RAEPBN算法中，当携带消息的节点在某一时刻有多个连接机会时，该节点仅将消息转发给与目的节点相遇概率最高的邻居节点，从而降低了路由算法的网络开销。其次，为了提高缓存资源的利用率，RAEPBN路由算法利用ACK确认机制通知网络中的节点删除已经被成功投递到目的节点的消息。具体地说，每个节点有一个ACKmesID列表属性，当某个节点将消息成功投递到目的节点后，该节点会将消息ID添加到自身的ACKmesID列表中，当任意两个节点相遇时，它们互相交换彼此的ACKmesID列表，并将对方ACKmesID列表中包含的而自身ACKmesID列表中没有的消息ID加入到自身的ACKmesID列表中，若节点缓存中存在消息的ID在ACKmesID列表中，则从缓存中将这些消息删除。

当某个节点vi在某一时刻有多个邻居时，节点vi遍历缓存中的所有消息m，并获取消息m的目的节点vd。然后遍历节点vi的所有连接机会con，并获取连接的邻居节点vj，同时，更新节点vi与节点vj间的相遇概率P（i，j），节点vi和节点vj交换彼此的ACKmesID列表， 然后基于ACKmesID列表将自身缓存中已经被成功投递的消息删除。若节点vj是消息m的目的节点，则节点vi将消息直接转发给邻居节点vj;否则筛选出与目的节点vd相遇概率更高的邻居节点，并将消息转发给该邻居节点。

2 仿真实验分析

2.1 仿真设置

本文在开源的ONE仿真平台上，对提出的RAEPBN路由算法进行了仿真，并将该算法与Epidemi和Prophet路由算法在不同的缓存和生存周期下进行了对比。详细的参数设置如表1所示。

2.2 仿真实验结果分析

2.2.1 不同缓存下各算法的性能比较

图2对比了Epidemic、Prophet和RAEPBN三种路由算法的性能。从图2（a）中可以看出，RAEPBN路由算法的投递率最高。这是因为RAEPBN路由算法在有多个连接机会时仅将消息转发给与目的节点相遇概率最高的邻居节点，避免了消息在某一局部区域内存在过多的冗余副本。图2（a）显示各算法的投递率都随着缓存的增加而增加，这是由于节点的缓存越大，所能携带的消息也就越多，由于缓存资源有限导致消息被丢弃的情况逐渐缓解。图2（b）展示了各算法的平均时延。从图2可以看出，RAEPBN算法的平均时延总体上最优，且当缓存越大时，RAEPBN算法在平均时延上的优势越明显。从图2（c）中可以看出RAEPBN路由算法的网络开销最低。这是因为在RAEPBN路由算法中，节点将消息成功投递到目的节点后，会生成对应的ACK确认消息，并将ACK确认消息传播到网络中，其他收到该确认消息的节点会从缓存中将此条被成功投递到目的节点的消息删除。

2.2.2 不同TTL下各算法的路由性能

图3对比了Epidemic、Prophet和RAEPBN三种路由算法在不同生存周期下的投递率。从图3（a）中可以观察到RAEPBN路由算法的投递率最高。当生存周期大于200分钟时，Epidemic和Prophet路由算法的投递率都呈现下降的趨势，这是因为当生存周期增加，消息能在节点的缓存中存储更长的时间，但是节点的缓存是有限的，许多消息将会由于节点缓存溢出而被丢弃。从图3（b）中可以看出RAEPBN路由算法的平均时延最低。图3（c）显示了RAEPBN路由算法的网络开销最低，且随着生存周期的增加，RAEPBN路由算法在网络开销上的优势更明显。

3 结束语

本文提出了一种基于节点间相遇概率的路由算法RAEPBN。在RAEPBN算法中，若某个节点在同一时刻有多个连接机会时，该节点仅选择与目的节点相遇概率最高的邻居节点作为中继节点，而不是将消息转发给所有与目的节点相遇的邻居节点，以避免消息在某一局部区域内存在过多的冗余副本。此外，为了降低网络开销，增加了ACK确认机制，若某条消息被成功投递到目的节点，RAEPBN算法就生成对应的ACK确认消息以通知网络中的其他节点删除此条已经被成功投递的消息，从而避免了不必要的消息副本的转发。由于节点的缓存资源是有限的，未来我们将进一步改进ACK确认消息的转发方式，以进一步提高路由算法的性能。并且搭建一个真实的DTN仿真环境，以进一步验证所提出的路由算法的性能。

参考文献（References）：

[1] Rosas E，Garay F，Hidalgo N.Context-aware self-adaptive

routing for delay tolerant network in disaster scenarios[J]. Ad Hoc Networks，2020.102：102095

[2] Rashidi L， Entezari-Maleki R ， Chatzopoulos D， et al.

Performance Evaluation of Epidemic Content Retrieval in DTNs With Restricted Mobility[J].IEEE Transactions on Network and Service Management，2019：701-714

[3] Spyropoulos T， Rais R N B， Turletti T， et al. Routing for

disruption tolerant networks： taxonomy and design[J]. Wireless networks，2010.16（8）：2349-2370

[4] Boukerche A， Turgut B， Aydin N， et al. Routing protocols

in ad hoc networks： A survey[J]. Computer networks， 2011.55（13）：3032-3080

[5] Zhang Z. Routing in intermittently connected mobile ad hoc

networks and delay tolerant networks： overview and challenges[J].IEEE Communications Surveys & Tutorials，2006.8（1）：24-37

[6] A. Vahdat and D. Becker， Epidemic routing for partially-

connected adhoc networks， Technical Report CS-2000-06，Duke University，2000.

[7] Lindgren A， Doria A， Schelén O. Probabilistic routing in

intermittently connected networks[J]. ACM SIGMOBILE mobile computing and communications review，2003.7（3）：19-20

[8] Spyropoulos T， Psounis K， Raghavendra C S. Spray and

wait： an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking，2005：252-259

收稿日期：2020-08-14

作者简介：李广强（1978-），男，山西太谷人，硕士研究生，讲师，主要研究方向：模拟训练仿真建模分析与研究。

通讯作者：何佳（1991-），女，湖北孝感人，硕士研究生，助教，主要研究方向：模拟训练仿真建模分析与研究。