基于邻居节点位置的受控传染DTN 路由算法

李建波，由 磊，姜 山，戴晨曲，徐吉兴

(青岛大学信息工程学院，山东 青岛 266071)

1 概述

容迟网络(Delay Tolerant Networks，DTN)是近年来无线网络领域内的一个研究热点，泛指部署在极端环境下由于节点的移动或者能量调度等原因而导致节点间只能间歇性进行通信甚至长时间处于中断状态的一类网络。其概念起源于星际互联网络(Inter Planetary Internet，IPN)，其主要目的是为了将因特网中的协议应用到星际之间的网络互联中。为此，国际互联网研究任务组(Internet Research Task Force，IRTF)专门成立了星际网络研究小组(Inter Planetary Internet Research Group，IPNRG)。星际网络中消息传输的主要问题是长传播时延，其过长的传播时延会导致现有的网络协议失效。非对称的带宽以及低比特率等也都给网络协议设计带来了非常大的困难和挑战。

在2001 年和2002 年，IPN 研究者尝试将IPN 的架构应用于其他一些陆地上的挑战性网络中，如用于发展中国家偏远地区通信和Internet 接入服务的信息网络［1］、湖泊环境下的水声传感器网［2］、野生动物追踪网络以及高速行驶的车辆组成的车辆Ad Hoc网络［3-4］等。这些网络具有间歇连接、时延极高、频繁割裂、非对称数据率、安全性差、较高的误码率与丢包率以及异构互联等特性［5-6］。然而，与IPN 不同的是，陆地上的挑战性网络由于节点的强移动性等特点，其更加强调节点之间连接的频繁中断(disruption)，而IPN 由于节点之间具有极远的距离，其更加强调节点之间传播的高时延(delay)。2004 年，文献［7］提出一种用于此类挑战性网络的架构，自此容迟网络引起了空前的广泛关注。随着相关研究成果不断涌现，容迟网络这一名称逐渐被研究者们接受，并被作为一个兼容各类异构网络的覆盖网络的架构标准［8-9］，目前，容迟网络已经成为网络界最为热门的研究课题之一。

如何做出正确高效的路由选择一直是无线网络领域内的关键技术和主要研究课题。传统的基于TCP/IP 的Internet 路由协议、移动Ad Hoc 网络和无线传感网络的路由协议均假设某一时刻存在一个稳定连通的端到端的通信链路［10］。但是这一假设在容迟网络中不再成立，由于容迟网络中的节点具有高度移动性并且稀疏部署，这将导致容迟网络中的拓扑结构动态变化以及链路时断时续，因此在某个时刻或者某段时间内不存在端到端路径［11］。正是由于传输链路的这种时变性和不确定性使得容迟网络中的路由研究是一项挑战性的课题，因此设计可靠有效的容迟网络路由算法来提高网络连接性、降低能量消耗和时延、增加消息投递率成为容迟网络研究的一个核心问题。容迟网络中的路由算法研究作为一项关键技术成为新一代无线通信网络研究领域备受关注的前沿热点课题。

文献［12］提出的传染病(epidemic)路由算法是基于传染策略的一个代表性算法。文献［13-15］在传染策略上做了改进，如限制最大跳数以及副本数目，对队列中待转发的包进行排序等。文献［16］提出的适用于星际网络的路由算法是基于效用函数进行转发的路由策略的典型代表，它将容迟网络建模为有向多图模型(即将网络建模为多个连通的有向子图，将子图中的有向边表示为节点间链路容量和传输时延的函数)，并提出了FC，MED，ED，EDLQ，EDAQ 和LP 6 个算法。文献［17-19］进一步讨论了基于效用函数进行下一跳选择的路由策略。文献［20］利用社会网络中的集群性(community)概念，采用社区标签(community label)来标识每个节点所属的群体，节点在转发消息时，要么转发给消息目标节点，要么转发给与消息目标节点所处在同一群体的节点。文献［21］区别于文献［20］，其利用节点的相似性(即节点的共同行为特征和兴趣爱好等)和向心性(包括广泛度、中介度和密切度3 种，用来衡量节点与其他节点的联系能力)设计效用函数，并让消息向效用更高的节点进行移交。实验证明，在容迟网络中利用社会网络的概念，能够在保证一定投递率的基础上减少网络负载［22］。

本文采用多拷贝策略增加消息的投递概率，并利用节点的一跳以内的位置信息，基于余弦定理设计路由选择算法，从而实现消息的受控传染。

2 路由设计

2.1 路由思想

大量研究结果表明，在挑战性网络中多拷贝策略是一个有效提高消息投递率的方法［23-24］。然而，这类挑战性网络中的缓存资源以及能耗往往被严格限制，盲目地进行无选择复制会快速耗尽网络资源，从而降低路由性能。目前有很多研究成果，其策略是基于节点效用进行选择复制，以实现受控传染。然而，多数都需要依赖假设可知的拓扑信息或信息分发策略等。在机会网络中，由于拓扑变化的频繁以及高时延链路，维护和更新一张路由表是极其困难的，其原因是频繁的拓扑变化以及高时延会使得拓扑更新信息难以分发，从而降低该类路由算法的实用性。即使能够保证拓扑更新信息到达其他节点，高时延会让信息的时效性减弱，从而导致选路的准确性下降。

从消息的时效性以及易得性方面来考虑，一跳邻居信息较为可靠。首先，节点可以依靠周期性发送广播包以探测其邻居节点，并可在其中包含自身信息以通知其邻居节点。邻居节点可用携带信息的数据包予以响应。一轮探测结束后，该节点和其邻居即可互相获知对方信息。从另一方面讲，当长期未收到来自邻居的探测或响应信息，节点可认为该邻居已不再活跃，可将其从所维护的邻居节点中删除。然而，若维护两跳信息，问题就变得复杂很多。

本文提出基于节点位置信息的受控传染(Location-based Controlled Epidemic，LC-Epidemic)路由算法，并保守假设只有一跳邻居信息可以被实时获得并利用。除此之外，不假设任何已知的关于目的节点的信息，包括目的节点的坐标。为了增大消息的投递率，采用多拷贝策略进行消息洪泛，并利用节点的位置信息，对可用节点进行筛选以实现受控传染。本文算法选择距离较远的节点能够让消息在网络中获得更大的覆盖面积，从而增大消息传递到目的节点的可能性。

2.2 下一跳选择算法

文献［23］中对路由研究进行了总结:(1)实施多副本策略往往能够有效增加投递率;(2)实施多副本策略能够有效降低投递时延;(3)实施多副本策略会增加节点的能耗;(4)实施多副本策略会增加缓存需求可知，在容迟网络中实施多拷贝策略有利有弊，一方面，在网络资源充足的情况下，多副本策略能够有效改善投递率和投递时延;另一方面，在实际情况中，网络中节点的可用缓存以及能量等通常是严格受限的，盲目的进行洪泛策略，会导致网络资源迅速耗尽，带来网络拥塞，从而降低路由性能表现，这就要求路由算法的设计者要考虑每一次复制及转发操作的有效收益，从而合理进行下一跳节点选择。文献［23］中还提出了2 条路由设计准则:(1)节点应该有目标地选择下一跳。在容迟网络中，节点的缓存和能量严格受限。此外，缓存资源可通过删除已存信息或完成投递操作而重新获得，然而能耗却是难以恢复的。这就要求路由设计者应当采取一种合理的下一跳选择策略，并对副本数量做一定限制。(2)节点需要做出有一定风险的选择。在容迟网络中，往往只能在一定程度上预测某节点与目的节点之间的期望接触概率(或在某段时间之内节点的接触概率)，然而实际上与目的节点真正接触的，可能是期望概率较小的节点。因此，设计者在设计下一跳选择算法时，也需考虑在让节点做选择时冒一定风险，即在一定程度上放宽对副本数量的限制。

基于以上2 条准则，本文提出基于节点位置信息的受控传染路由算法LCE。假设节点只能获得一跳以内的邻居节点的位置信息，为了实现高投递率，让节点选择张角最大的2 个邻居节点进行复制，以尽可能增大所投递消息在网络中的覆盖范围。此外，略微放宽对消息副本数量的限制，即每个节点在完成消息复制操作后，仍然保留该消息的拷贝，以便在适当时机重新选择新的中继节点进行传递。

当网络中节点分布较为稀疏时，对于每个节点，其周围同时可用的一跳邻居节点往往较少。若当前周围无可用的邻居节点，将把消息存入节点缓存中进行保管，以等待出现可用连接时进行传递。当可用邻居节点数目小于2 个，可以推测网络中节点的分布可能较稀疏。这意味着节点之间的接触机会非常少。此时，遵循路由算法设计准则中的第(2)条，向这2 个邻居节点都传递消息的拷贝，而不是首先考虑这2 个节点对于投递该消息副本的合适程度。当可用的邻居节点数目大于2 个时，遵循第(1)条准则，对周围所有可用的邻居节点进行选择。其出发点是尽可能选择与当前节点形成张角最大的2 个节点，以实现副本的扩散投递。如图1 所示，节点Ni是当前持有消息的节点，在其传输范围之内共有3 个邻居节点Nj，Nk和Nr，共能形成了C23=3 个可能的夹角，分别记为α(j，k)，α(j，r)，α(k，r)。这里对于节点Ni的任意2 个邻居节点Nj和Nk，利用式(1)计算节点间的夹角:

其中，Vij代表节点Ni与Nj所确定的向量;Vjk代表节点Ni与Nk所确定的向量。

图1 节点Ni与3 个邻居节点之间组成两两夹角的关系

图2 基于夹角与距离的中继节点选择

依据式(2)，以一种折中的方式进行节点选择:

其中，C1 是所有邻居节点中所呈夹角最大的节点对;C2 是所呈夹角次大的节点对。在进行中继节点的选择时，首先考虑节点所呈张角的大小，并用余弦值作为衡量标准，当其差值在ε 内时，则优先考虑距离因素。d(C1)是C1 中的节点对离当前节点x 的距离之和。C1={N_j，N_k}，C2={N_m，N_n}，预设ε=π/18，并利用余弦定理求得cosα(C1)，cosα(C2)。对于距离参数d(C1)及d(C2)计算如下:

最终计算获得f(C1，C2)=C2，即选择Nm，Nn作为下一跳中继节点，向其拷贝消息副本。

算法1 LC-Epidemic 的下一跳选择算法

2.3 LC-Epidemic 路由协议

LC-Epidemic 路由协议的主要工作为:(1)每个节点如何发现其邻居节点，并定期实时维护邻居节点状态;(2)邻居表(即维护邻居节点位置的状态表)的更新方式。

算法2 LC-Epidemic 路由算法

采用链路状态法，令每个节点周期性广播“Hello”探测包，包中包含该节点的坐标信息，用以通知其附近节点，以更新一跳邻居的链路情况。由于下一跳选择只依赖于邻居节点的位置信息，因此链路状态控制信息只在局部交换，不会在整个网络中造成洪泛。算法2 第1 行～第5 行是节点探测其邻居节点的相关操作。节点i 首先更新其一跳邻居表neighborTable，若节点j 不在表目中，则将j 的相关信息添加入表，作为新的条目。否则，由于新到达的消息更具有时效性，用新的信息更新之前所保存的位置信息。此外，为了确保每一个在表中的邻居当前都是活跃的，在更新邻居表时将每条表目的最后一次更新时间与当前时间相比较，若时间差超过一定值，则认为该节点已不再活跃，并从表中删除该节点。当邻居表更新结束后，节点i 会向节点j 发送一条hello_response 消息，其目的是通知邻居节点j 更新操作已结束，并将自己的相关信息通知给j。如算法2 的第6 行～第9 行，当收到hello_response 消息时，接收节点依此更新自己的邻居节点表目，更新方法与收到hello 消息时的方法一样，每个邻居的时效性也将被检查。

第10 行～第28 行是消息转发与处理策略，当某条数据消息(记为data_msg)被节点j 传递给当前节点i 时，由于该此传递意味着节点j 对于节点i 仍然是活跃的，因此节点i 首先更新其邻居表目，以保证维护的邻居信息的准确性。然后节点i 将检查数据消息data_msg 是否已在其队列当中，若已在队列当中，则直接将其丢弃，以避免冗余，并以MSG_DROPPED 信号通知运行的路由进程。若data_msg不在缓存队列中，则将消息入队以等待传递机会到来，如第17 行。第18 行的操作是将消息队列按消息的剩余生存时间TTL 增序排序，以便最先传递TTL 最小的消息，从而一定程度上避免因传递时间的推迟而产生丢包。第19 行将从节点维护的邻居表中读取所有可用邻居节点的信息，并存入可用节点列表AvailableHostsList 中。LCE 算法采用的受控传染策略是，当可用节点的数目小于2 个时，采用传统的传染病算法，以增大消息的并行性。若可用节点的数目大于2 个，为了节省网络中的缓存资源，降低能耗，如第24 行所示，采用算法1，对可用节点列表Available HostsList 进行过滤，筛选出2 个节点传染消息。传递操作结束后，向路由进程返回MSG_SENT 信号。

3 仿真实验与结果分析

通过实验仿真，将LC-Epidemic 与Epidemic，Binary Spray ＆ Wait，FirstContact 3 个算法进行比较，分析相关算法的性能。主要衡量指标有成功传输的数据包个数、平均投递时延，端到端平均跳数以及网络开销等。仿真平台是容迟网络环境模拟器ONE(Opportunistic Enviroment Evaluator)［25］。

3.1 LC-Epidemic 路由协议

ONE 模拟器是芬兰赫尔辛基理工大学开发的一款基于Java 的机会网络模拟工具，其核心为一个离散事件模拟器。支持移动模型的扩展以及利用真实数据集进行仿真，其模块划分清晰且便于功能扩展，并支持利用脚本配置模拟环境，受到网络研究界的广泛认可。本文中基于Random Walk 移动模型，对LC-Epidemic 以及其他3 种算法进行模拟，3 种算法介绍如下:

(1)Epidemic［12］。传染病算法，尝试最大化消耗网络资源，任意一对节点相遇时，2 个节点都会检查对方所持有的消息，并接受对方传送的自己未持有的消息。在网络资源充足时，该算法具有最高的投递率和最低的平均投递时延。

(2)Binary Spray ＆ Wait［14］。该算法给每条消息设定一个剩余可分发副本数L，当2 个节点相遇时，对于L ＞1 的消息，将复制份副本给对方，自己持有剩余的份副本。当L=1 时，使用Direct Delivery 策略［11］，即只有遇到消息的目的节点才进行传递。

(3)FirstContact［16］。该算法是单拷贝算法，即当前节点成功转发消息后，会缓存中删除该消息，避免再次转发。转发策略是将消息拷贝转发给该节点最先遇到的下一节点。

主要评估指标有:

(1)消息投递率

(2)平均时延

(3)网络开销

(4)平均跳数

模拟实验中，网络环境的详细参数设定如表1所示。

表1 模拟参数

3.2 仿真结果分析

3.2.1 消息生成的时间间隔

图3 比较了在改变消息产生的间隔时间时，4 种算法对应的4 项评估指标的变化。如图3(a)所示，由于LC-Epidemic 是基于洪泛算法，其目的是最大化副本数量以增加投递率，因此能达到与Epidemic相当的较高的消息投递率;First Contact 算法取得次之的较低投递率;Binary Spray ＆Wait 算法的投递率最低。在网络资源充足的情况下，多副本能够改善路由算法的表现。因此，基于洪泛的路由算法会有较为理想的投递率，FirstContact 虽能够及时利用节点间每一次接触机会，但由于其只维护一个消息副本，因此无并行性，使其投递率大大低于基于洪泛的2 个多副本算法。Binary Spray ＆ Wait 虽是多副本算法，但其对副本的总量做了限制，此外在算法的Wait 阶段，消息只能进行一跳直接传递，然而在Random Walk 模型下，某些节点之间直接接触的机会可能为0，因此有大量消息无法传递，其投递率最低。当消息的产生间隔时间很小时，网络中的消息数量很多，此时由于节点的缓存资源受限，会降低基于洪泛的LC-Epidemic 以及Epidemic 的性能表现。但在本文设定的模拟环境下仍远高于限制副本数量和跳数的Binary Spray ＆ Wait 算法。总体上，LCEpidemic 和Epidemic 的投递率比FirstContact 约高25%，比Binary Spray ＆Wait 约高60%。

图3(b)比较了4 种算法的端到端平均时延，Epidemic 无疑具有最低的端到端平均时延，因为其最大化利用了所有网络可用资源。LC-Epidemic 的平均时延比Epidemic 约高4 倍，但仍然低于其他2 种算法。与图3(a)类似，消息产生间隔小于20 s时，由于缓存资源受限，Binary Spray ＆ Wait 和FirstContact 的表现要好于基于洪泛的Epidemic 以及LC-Epidemic 算法。随着消息产生间隔的持续增大，固定时间内的副本数量不断减少，Epidemic 和LC-Epidemic 的消息端到端平均时延迅速下降，当消息产生间隔时间大于30 s 时，节点的缓存已不再是限制路由性能表现的瓶颈因素。Epidemic 和LCEpidemic 与其他2 种算法一样，其端到端平均时延趋于稳定。比较4 种路由算法，FirstContact 的平均时延比BinarySpray ＆Wait 约低22%，且在图3(a)中其投递率比Binary Spray ＆Wait 高，因此综合投递率和平均时延来看，其表现胜过Binary Spray ＆Wait。

图3(c)比较了4 种算法的网络开销。从图3(a)、图3(b)中的分析可知，在消息产生间隔小于30 s时，缓存资源是路由性能表现的瓶颈因素，然而此时LC-Epidemic 的网络开销约只有Epidemic 的55%。综合图3(a)～3(c)来看，在缓存资源受限的情况下，LC-Epidemic 能够保证和Epidemic 投递率几乎持平的情况下，降低一半的网络负载，代价是具有比Epidemic 高的平均时延。对于不刻意强调消息投递时延的容迟网络应用，可以用LC-Epidemic 替代Epidemic，以节省网络资源开销，相比传统的Epidemic 对消息副本的盲目复制，LC-Epidemic 基于节点分布及相对位置选择下一跳，因此其路由策略更有针对性。Binary Spray ＆Wait 和FirstContact 算法，前者是多拷贝算法，但限制了消息副本的数目和最大跳数，后者虽未对最大跳数做限制，但每条消息在网络中最多只有一份拷贝，因此两者的网络开销较低。综合来看，两者在投递率和平均时延2 项指标上，表现都差于基于洪泛的Epidemic 和LCEpidemic，这在一定程度上限制了其应用价值。

图3 消息产生时间间隔与消息投递率、平均时延、网络开销以及平均跳数的关系

图3(d)比较了Epidemic，LC-Epidemic 以及FirstContact 的端到端平均跳数。之所以不加入Binary Spray ＆ Wait 算法进行比较，是因为其已限制了副本的最大跳数，而其他3 种算法对此均无限制。可以看出，FirstContact 具有最高的平均跳数，原因是其相比Epidemic 和LC-Epidemic，只在网络中维护消息的一份拷贝，因此该消息常需要多跳才能将副本传输到目的节点。该结果与图3(b)中分析的结果相吻合，由于跳数较大，因此其平均时延也远高于Epidemic 和LCEpidemic。LC-Epidemic 的平均跳数只比Epidemic 略高，其原因是LC-Epidemic 是受控洪泛，在一定程度上控制消息副本数目，进而控制网络资源的利用，以换来更低的网络开销。

综合图3(a)～图3(d)来看，LC-Epidemic 在投递率和平均跳数2 项指标上都接近于最优的Epidemic，其网络开销比传统Epidemic 算法低一半，若不刻意强调端到端时延，可以用LC-Epidemic 算法代替Epidemic。在节点移动速度较低的网络场景下，Binary Spray ＆ Wait 以及FirstContact 的表现不甚理想，FirstContact 在投递率、投递时延以及网络开销三方面都要优于Binary Spray ＆ Wait。

3.2.2 节点缓冲区大小

图4 比较了在改变节点的缓存大小时，4 种算法对应的4 项评估指标的变化。如图4(a)所示，只有当节点缓存小于2.5 MB 时，才会成为限制FirstContact 和Binary Spray ＆ Wait 投递率的瓶颈因素。缓存低于30 MB 时，LC-Epidemic 的投递率一直略高于Epidemic，最后与Epidemic 几乎持平，维持在接近1.0，这验证了基于一跳邻居实现受控传染的策略能有效改善网络资源的利用率。在缓存资源大于8 MB 时，LC-Epidemic 的投递率高于Binary Spray ＆ Wait 和First Contact。与图3(a)中的结果类似，FirstContact 的投递率仍远高于Binary Spray ＆ Wait。由此推断，在节点位置相对稳定的环境下，不适宜对副本的最大跳数做限制。综合来看，基于洪泛的Epidemic 和LC-Epidemic 在投递率方面，性能表现胜过其余2 个算法。

图4 节点缓冲区大小与消息投递率、平均时延、网络开销以及平均跳数的关系

图4(b)比较了当缓存容量变化时，4 种算法端到端平均时延的变化。当节点缓存容量较小时，4 种算法都具有较低的端到端平均时延。其原因是计算端到端平均时延的统计样本为所有已完成传递的消息，由于受缓存大小限制，只有那些能够被快速投递的消息才会被统计，其他许多消息都被节点丢弃，如图4(a)所示，此时4 种算法的投递率都很低。随着节点缓存的增加，这种严重丢包的情况渐渐缓解，当缓存容量达到5 MB 时4 种算法的平均时延都已攀升到最高点。在节点缓存容量从0.5 MB 增加到5 MB的这个过程中，所有算法的消息投递率都是在增长的，且当缓存容量为5 MB 时Binary Spray ＆Wait 以及FirstContact 的投递率也达到最大，此时缓存不再是Binary Spray ＆ Wait 以及FirstContact 性能表现的约束因素，即继续增大缓存容量不会对这2 个算法的性能表现产生很大影响。体现在图4(b)中，随着缓存容量的继续增大，Spray ＆ Wait 和FirstContact 的平均时延保持恒定。基于洪泛策略的Epidemic 和受控传染策略的LC-Epidemic，平均时延随着节点缓存的继续增大而逐渐降低。至缓存容量增大到30 MB 时趋于稳定，这与图4(a)投递率的稳定点相同。此时Epidemic 具有最低的端到端平均时延，LC-Epidemic 次之，结果类似于图3(b)。

图4(c)比较了4 种算法网络开销的变化。由于Binary Spray ＆ Wait 以及FirstContact 最大副本数量受限，两者在缓存容量小于10 MB 时，具有远低于Epidemic 和LC-Epidemic 的网络开销。如图4(a)所示，此时FirstContact 的消息投递率高于Epidemic 及LC-Epidemic，可知在缓存资源紧张时，多副本策略会降低路由性能。然而 LC-Epidemic 比传统的Epidemic 的网络开销约低50%，数据曲线走势与图3(c)相似。

图4(d)比较了Epidemic，LC-Epidemic 以及FirstContact 3 种算法的平均跳数，Binary Spray ＆Wait 仍不参与比较。FirstContact 具有最高的平均跳数，Epidemic 的平均跳数最低，而LC-Epidemic 完成消息投递所需的平均跳数只比Epidemic 略高，比FirstContact 要低很多。理由与分析图3(d)相同。

综合图4(a)～图4(d)来看，在缓存资源稀缺时，宜采用单副本算法，如FirstContact;因为此时洪泛策略往往会让网络资源迅速耗尽，从而降低路由性能表现。然而FirstContact 这种盲目转发策略，使得完成消息传递所需的平均跳数过大。如果要将跳数控制在一定范围内，则宜采用受控传染策略的路由算法LC-Epidemic，降低网络开销。通过图3 以及图4 可知，LC-Epidemic 基于节点位置的下一跳选择算法能够有效的控制网络中消息副本数量，从而降低负载，并且能够获得与Epidemic 几乎持平的投递率，在一定程度上可以代替盲目的洪泛策略。

3.2.3 消息生命周期

图5 在改变消息的生命周期(Time to Live，TTL)的情况下，比较了4 种算法的消息投递率以及平均时延的变化。如图5(a)所示，当TTL 小于50 min时，Epidemic 和LC-Epidemic 的投递率远高于Binary Spray ＆Wait 以及First Contact，其原因在于当消息生命周期受限时，Epidemic 和LC-Epidemic能够有效地利用快速增加消息并行性的洪泛策略，及时完成消息的投递，且图3(b)与图4(b)已说明当缓存资源不是瓶颈时，Epidemic 和LC-Epidemic具有比Binary Spray ＆Wait 以及FirstContact 低得多的平均时延。然而随着TTL 的增大，前两者的投递率不断下降，而后两者的投递率却保持攀升，其原因是过大的TTL，会导致当使用洪泛策略时节点缓存中消息副本积压，从而造成丢包，降低消息投递率。而TTL 的延长，恰好弥补了Binary Spray ＆Wait 以及FirstContact 平均投递时延过长的不足，从而增加消息投递率。在本文实验中，当消息生命周期大于250 min时，所有4 种算法的投递率都趋于稳定，Binary Spray ＆ Wait 和FirstContact 要明显优于其他2 个洪泛算法。可知，当消息TTL 较长时，宜采用严格控制副本数量的路由算法，摒弃洪泛。然而当TTL 较 短 时，Binary Spray ＆ Wait 以 及First Contact 的表现相比Epidemic 和LC-Epidemic 差很多。

图5 消息生命周期与消息投递率、平均时延的关系

图5(b)比较了4 种算法的平均时延，随着TTL的增大，所有4 个算法的平均时延都增大。此外，除了FirstContact 具有很长的平均时延之外，其他3 种算法的平均时延都相差甚小。LC-Epidemic 一直保持最低的平均时延，优于其他3 种算法。比较图5(a)与图5(b)可知，在TTL 较大时，宜采用Binary Spray ＆ Wait 算法，以在保证投递率的基础上获得较低的平均时延。然而，当TTL 较小时，则宜采用基于洪泛的LC-Epidemic 算法。

3.3 LC-Epidemic 路由分析

综合仿真结果来看，由于LC-Epidemic 本质是基于Epidemic 的算法，因此其路由表现与Epidemic 较接近。与传统的Epidemic 不同的是，LC-Epidemic 将节点分布及节点相对位置等信息纳入考虑之中，在传递消息时控制消息的副本数量，从而实现基于节点位置的受控洪泛路由。综合仿真结果分析，当消息的TTL 较短时，不宜对消息的副本数量做过于严格的限制。这也是本文设计算法时，基于传染病路由策略的初衷。从仿真结果看，LCEpidemic 的优化策略，其原理虽简单，但确有一定成效，由于在DTN 多变的网络环境中，收集实时有效的网络拓扑信息非常困难，因此此时基于一跳位置信息的策略显得更为实用。此外，在仿真程序设计过程中，所有节点都是以对等方式工作的，因此网络的自组特性没有被破坏，LCEpidemic 正适用于时延较高的自组网络场景，特别是在TTL 较短的情况下。

4 结束语

在容迟网络中，网络的频繁割裂和间歇性连接，以及节点的移动性使得路由问题变得更加富有挑战性。路由策略的优劣在一定程度上依赖于对网络拓扑信息的掌握，然而在这类挑战性网络中，很难获得准确且具有时效性的网络拓扑信息。本文研究如何利用一跳以内节点的位置信息进行下一跳节点选择，从而一定程度上控制洪泛策略的副本数量，在保持较高投递率以及较低的端到端平均时延的基础上降低网络开销。基于余弦定理，设计了下一跳节点选择算法，尽可能使消息扩张投递，增大消息在整个网络中的覆盖面积，从而提高路由性能表现。此外，给出了LC-Epidemic 协议的详细描述，利用链路状态法维护一跳邻居信息，从而实时更新邻居表，维护可用节点队列。

本文 对Epidemic，Binary Spray ＆ Wait，First-Contact 以及本文提出的LC-Epidemic 4 种路由算法进行大量仿真模拟。实验结果表明，LC-Epidemic 的消息投递率逼近于传统的Epidemic 算法，然而其网络开销却只有后者的50%。在消息TTL 较短的情况下，只要节点的缓存资源不过小，Epidemic 以及LC-Epidemic 在投递率以及投递时延方面明显好于Binary Spray ＆Wait 以及FirstContact 算法。然而当消息的TTL 较大时，基于洪泛策略的路由算法难以获得较好的表现。总之，多副本策略是解决容迟网络中路由问题的一项基本且有效的手段，下一步研究将侧重于依赖节点的移动模型以及移动方向进行路由算法的设计，并结合本文提出的基于邻居节点位置的方法进行更有效的下一跳选择，从而实现受控传染。此外，考虑引入受控节点对消息进行定向传输，从而增大消息传递率并降低平均传递时延，这种方案虽然会在一定程度上破坏网络的自组特性，然而若使用得当，将会大大增加网络的连通性，从而有助于设计更灵活的路由算法。最后，考虑到目前存储器的容量飞速增加以及成本迅速降低的趋势，下一步将研究具有大缓存容量的节点路由问题，由于目前电池技术的限制，节点能耗更有可能成为容迟网络中影响路由性能表现的主要因素，未来工作的重点将集中于此。

［1］Demmer M，Fall K.DTLSR:Delay Tolerant Routing for Developing Regions ［C］//Proceedings of 2007 Workshop on Networked Systems for Developing Regions.New York，USA:ACM Press，2007.

［2］Guo Zheng，Wang Bing，Cui Junhong.Generic Prediction Assisted Single-copy Routing in Underwater Delay Tolerant Sensor Networks［J］.Ad Hoc Networks，2013，11(3):1136-1149.

［3］Pereira P R，Casaca A，Rodrigues J J P C，et al.From Delay-tolerant Networks to Vehicular Delay-tolerant Networks ［J］.IEEE Communications Surveys ＆Tutorials，14(4)，2012:1166-1182.

［4］Soares V N G J，Rodrigues J J P C，Farahmand F.GeoSpray:A Geographic Routing Protocol for Vehicular Delay-tolerant Networks［J］.Information Fusion，2014，15:102-113.

［5］Cao Y.Routing in Delay/Disruption Tolerant Networks:A Taxonomy，Survey and Challenges ［J］.IEEE Communications Surveys ＆ Tutorials，2012，15 (2):654-677.

［6］张 龙，周贤伟，王建萍，等.容迟与容断网络中的路由协议［J］.软件学报，2010，21(10):2254-2572.

［7］Fall K.A Delay-tolerant Network Architecture for Challenged Internets［C］//Proceedings of SIGCOMM'03.New York，USA:ACM Press，2003:27-34.

［8］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.

［9］樊秀梅，单志广，张宝贤，等.容迟网络体系结构及其关键技术研究［J］.电子学报，2008，36(1):161-170.

［10］Zhang Zhensheng.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.

［11］Ott J.Delay Tolerance and the Future Internet［C］//Proceedings of WPMC'08.［S.l.］:IEEE Press，2008.

［12］Vahdat A，Becker D.Epidemic Routing for Partially Connected Ad Hoc Networks［D］.Durham，USA:Duke University，2000.

［13］Grossglauser M，Tse D N C.Mobility Increases the Capacity of Ad Hoc Wireless Networks［J］.IEEE/ACM Trans.on Networking，2002，10(4):477-486.

［14］Spyropoulos T，Psounis K，Raghavendra C S.Spray and Wait:An Efficient Routing Scheme for Intermittently Connected Mobile Networks［C］//Proceedings of 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking.New York，USA:ACM Press，2005:252-259.

［15］Spyropoulos T，Psounis K，Raghavendra C.Spray and Focus:Efficient Mobility-assisted Routing for Heterogeneous and Correlated Mobility［C］//Proceedings of the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshop.White Plains，USA:IEEE Press，2007:79-85.

［16］Jain S，Fall K，Patra R.Routing in a Delay Tolerant Network［J］.ACM SIGCOMM Computer Communication Review，2004，34(4):145-158.

［17］Erramilli V，Crovella M.Delegation Forwarding［C］//Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，USA:ACM Press，2008:251-260.

［18］Liu C，Wu J.On Multicopy Opportunistic Forwarding Protocols in Nondeterministic Delay Tolerant Networks［J］.IEEE Trans.on Parallel and Distribution Systems，2012，23(6):1121-1128.

［19］Hui P，Crowcroft J.How Small Labels Create Big Improvements［C］//Proceedings of the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshops.［S.l.］:IEEE Press，2006:65-70.

［20］Daly E M，Haahr M.Social Network Analysis for Routing in Disconnected Delay-tolerant MANETs［C］//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，USA:ACM Press，2007:32-40.

［21］Zhu Y，Xu B，Shi X.A Survey of Social-based Routing in Delay Tolerant Networks:Positive and Negative Social Effects［J］.IEEE Communications Surveys ＆Tutorials，2013，15(1):387-401.

［22］Mangrulkar R，Atique M.Routing Protocol for Delay Tolerant Network:A Survey and Comparison［C］//Proceedings of 2010 IEEE International Conference on Communication Control and Computing Technologies.［S.l.］:IEEE Press，2010:210-215.

［23］Psaras I，Wang N，Tafazolli R.Six Years Since First DTN Papers:Is There a Clear Target?［C］//Proceedings of Extreme-Com'09.［S.l.］:IEEE Press，2009.

［24］Li Y，Hui P.Performance Evaluation of Routing Schemes for Energy-constrained Delay Tolerant Networks［C］//Proceedings of 2011 IEEE International Conference on Communications.［S.l.］:IEEE Press，2011:1-5.

［25］Keränen A，Ott J，Kärkkäinen T.The One Simulator for DTN Protocol Evaluation［C］//Proceedings of the 2nd International Conference on Simulation Tools and Techniques.［S.l.］:IEEE Press，2009:55-60.