一种基于最近相遇节点树的DTN 多副本路由算法

许子涵，纪俊维

(北京理工大学信息与电子学院，北京100081)

1 引言

在深空通信等受限网络[1]场景中，节点间由于不稳定的网络拓扑、有限的节点资源、恶劣的链路条件等原因，难以保持稳定的端到端连接。 此时传统的TCP/IP 网络体系将不再适用。 容迟网络[2](Delay Tolerant Networking， DTN)通过在传输层和应用层之间增设了Bundle 层，使用存储-携带-转发机制，以解决受限网络的通信问题。

经典DTN 路由算法根据节点是否已知接触计划等先验知识分为两类[3]：基于先验知识的路由算法与多副本的路由算法。 在深空卫星网络、有确定调度的车载网络中，每一时刻节点间的通信链路状态已知，每个节点根据网络全局先验知识规划路由。 Jain 等[4]根据节点已知关于接触计划、缓存队列、流量需求等先验知识，依次提出了FC(First Contact)、MED(Minimum Expected Delay)、ED(Earliest Delivery)、EDLQ(Earliest Delivery with Local Queueing)、EDAQ(Earliest Delivery with All Queues)、LP(Linear Program)等路由，均为经典基于先验知识的路由算法。 这类算法依赖于先验知识，且多为单副本路由，对网络拓扑突发变化的适应度及消息传输的可靠性较差。 基于多副本的路由算法主要应用于未来月表探测、社群网络、野生动物网络等无法事先规划节点连接计划的场景。 经典基于多副本的路由算法有Epidemic[5]、Spray and Wait[6]、Spray and Focus[7]、Prophet[8]等。 这类算法对网络拓扑的随机变化适应性较好，但需要在网络中发送大量冗余副本，且消息的转发具有一定盲目性，容易造成带宽等网络资源的浪费。 其中，Epidemic 路由[5]采用泛洪的策略。 当网络中某节点与其他节点建立连接时，即可互相转发所有可转发的数据包。 该策略最为简单，却在网络中产生大量副本，造成了节点存储资源的浪费。 在此基础上，Spray and Wait 与Spray and Focus 路由通过一定的策略限制了网络中的副本数量，但数据包的转发仍有一定盲目性，存在无法间接交付问题。 Prophet 算法通过节点历史消息传递情况，计算节点相遇概率，利用节点移动的规律性选择生成更可能递交至目的节点的副本，但缺少对网络中数据包副本总量的控制策略。

在未来月表探测、地球社群网络等DTN 典型应用场景往往具备以下特点：①网络拓扑动态变化且无法准确预知；②节点根据地形、社群属性、探测任务等属性，其运动轨迹具有一定的社区性、规律性；③节点缓存能力、网络资源等均因环境限制而有限，无法适应充满大量冗余副本与无效转发的网络。 因此，该类场景应采用充分利用节点移动规律、冗余副本较少、路由转发具有更高方向性和有效性、基于多副本的路由算法。

针对上述特点，本文设计一种资源受限条件下的Prophet 路由算法(Prophet under Limited Resources，PLR)。 PLR 路 由 算 法 建 立 在 经 典 的Spray and Focus 与Prophet 路由算法融合的基础上，使用了一种最近相遇节点树策略，并修改转发副本数量控制策略，以适应上述类型场景的需求。

2 路由算法

2.1 经典多副本路由算法及缺陷

2.1.1 Spray and Wait 路由算法

在Spray and Wait 路由[6]中，每个数据包共有散射(Spray)和等待(Wait)2 个状态。 若数据包的剩余可复制副本量大于0，则其处于散射状态。 在散射状态下，当携带该数据包的发送节点遇到其他节点时，将产生一个该数据包的副本并转发给接收节点。 该副本的剩余可复制副本量由具体的实现算法决定。 当节点移动模型满足独立同分布时，二分散射等待路由(Binary Spray and Wait routing)的转发副本数量控制策略是最佳的[9]。 即每次转发出当前拥有的一半副本量，并将本地数据包剩余可复制副本量减半。

若数据包的剩余可复制副本量为0，则其处于等待状态。 在等待状态下，发送节点仅在遇到该数据包的最终目的节点时才会将其转发。

2.1.2 Spray and Focus 路由算法

Spray and Focus 路由算法[7]将Spray and Wait 算法中的等待阶段改为Focus 阶段，并为每个节点增设1 个效用值属性。 节点的效用值可用该节点与目的节点的最近相遇时间来衡量。 当一个数据包的剩余可复制副本量为0 时进入Focus阶段。 此时该节点在遇到效用值更高的节点时，将以单副本路由的方式将该副本转发给其他节点，本节点将不再保留该副本。

2.1.3 Prophet 路由算法

Prophet 算法[8]为每个节点定义了一个新的属性递交概率P(a，b)(P(a，b)∈[0，1] )，P(a，b)即表示节点a可以与节点b建立连接、通信的概率。假设网络中共有N个节点，则每个节点均维护一个N-1 维的递交概率向量，表示该节点与网络中其他任意节点的递交概率。 初始状态下，每个节点的递交概率向量值初始化为Pinit(Pinit∈(0，1] )，并按照以下规则更新：

当节点a与节点b相遇且建立了通信连接时，节点a至节点b的递交概率按式(1)增加，其中P(a，b)old表示相遇前的递交概率。

若2 个节点在一段时间内始终没有相遇并建立通信连接，则这2 个节点间的递交概率按式(2)减少。

式中，γ∈(0，1) 为衰减常数，k是两节点递交概率上次更新至今的单位时间。 若节点a与节点b之间的递交概率较大，且节点b与节点c之间的递交概率也较大，那么节点a与节点c之间的递交概率很有可能也会较大，这是递交概率的传递性。 据此，在节点a与节点b相遇时，除了更新P(a，b)，还需更新节点a递交概率向量中的其他值。 以P(a，c)为例，其应按式(3)更新。

式中，β∈[0，1] 是传递常数，决定了传递性对递交概率的影响程度。 基于上述递交概率向量模型，在两节点建立连接后，Prophet 路由仅将数据包副本转发给具有更大递交概率的节点。

2.1.4 无法间接交付问题

传统的Spray and Wait 路由等待阶段与Spray and Focus 路由的Focus 阶段中，存在着无法间接交付问题，主要体现在2 种情况中。 第1 种情况受转发策略影响。 如图1 所示，实线表示两节点互在通信范围中且存在可用链路。 此时，节点a携带着1 个目的节点为节点d，剩余可复制副本量为0 的数据包。 若其处于等待阶段，仅当节点a与节点d有直接通信机会时，该数据包才会被转发出。 若其处于Focus 阶段，根据各类效用值计算算法，该数据包可能会被转发给节点e。 例如当采用与目的节点的最近相遇时间作为节点效用值时，若节点e刚与节点d断开连接移动至图1所示位置，则节点e的效用值将大于节点b的效用值。 在这两种状态下，该数据包均无法由节点b、c转发至节点d，而将继续在网络中占用存储资源，并增大了该数据包递交延迟。

另一种无法间接交付的情景是网络中产生拥塞时。 图1 中若节点b的缓存已不够接收该数据包副本，根据上述路由算法，节点b将无法作为一个中继节点转发该数据包。

图1 无法间接交付的链式节点分布Fig.1 Chained node distribution that cannot be delivered indirectly

2.2 PLR 路由算法

针对上述无法间接交付问题，本文提出一种基于最近相遇节点树的PLR 路由算法。 PLR 路由算法首先将Prophet 路由与Spray and Focus 路由进行合并。 具体地，在Prophet 路由基础上，为每个数据包引入剩余可复制副本数量这一属性。仅当同时满足Prophet 路由中的传递概率约束与Spray and Focus 路由中的剩余可复制副本数量约束时，数据包才会被复制并转发。 在Focus 阶段，使用Prophet 计算的递交概率作为节点效用值。接着，针对无法间接交付问题，提出最近相遇节点树机制，使每个节点可获取当前时刻网络中通过多跳与本节点通信的节点信息。 最后，采用基于递交概率的转发副本数量控制策略，提高存储资源利用率。

2.2.1 最近相遇节点树的结构

每个节点均维护着1 个最近相遇节点树，树根为该节点自身。 每个子节点均由最近相遇过的节点编号与定时器两部分组成。 定时器的值初始化设置为ms(m ＞0)。 当m＝0 时，该定时器所对应的子节点及其子树将从最近相遇节点树中被移除。 例如m＝5， 节点a在8 s 前与节点b通信，在4 s 前与节点c通信，在3 s 前与节点d通信，在1 s 前与节点e通信，则节点a中所维护的最近相遇节点树如图2 所示。

2.2.2 最近相遇节点树的更新

最近相遇节点树将被包含在Hello 包中被广播给通信范围内的节点。 当接收节点收到了其他发送节点广播的Hello 包时，接收节点将根据收到的信息更新本节点的最近相遇节点树。 更新分2 步：

图2 节点a 的最近相遇节点树Fig.2 Recently encountered node tree in node a

1)树的插入操作。 若接收节点维护的最近相遇节点树中已包含具有发送节点编号的深度为2 的子节点，则该子节点的原有子树将被删除，并将Hello 包中发送节点的最近相遇节点树作为该子节点的子树插入，且该子节点的定时器重置为m。 若接收节点维护的最近相遇节点树不包含具有发送节点编号的子节点，则Hello 包中发送节点的最近相遇节点树将作为根节点的子树插入接收节点的最近相遇节点树。

2)剪枝操作。 当接收节点的最近相遇节点树中存在2 个或2 个以上具有相同节点编号的子节点时，若其中1 个子节点a的深度大于另1 子节点b，且其定时器剩余时间小于子节点b，则子节点a及其子树将被删除。 对应的含义为接收节点删除了到达某一节点的多条路径中，需要经过更长的跳数、更旧的连通信息的路径。 至此，最近相遇节点树完成了一次更新。

具体地，以一个例子演示最近相遇节点树的更新过程。 发送节点a与接收节点b的最近相遇节点树如图3 所示。 当两节点相遇时，将互相发送并接收到包含对方最近相遇节点树的Hello包。 假设定时器默认时间m＝5， 现关注接收节点b中最近相遇节点树的更新情况。

首先，节点b检查其维护的最近相遇节点树中是否存在某个子节点包含节点a的节点编号。不难发现，有一个深度为2 的子节点的节点编号为节点a，故移除该子节点原有的子树，并将Hello 包中的节点a的最近相遇节点树直接插入，并重置该子节点的定时器为m。 此时接收节点b中的最近相遇节点树如图4 所示。

图3 更新前的最近相遇节点树Fig.3 Recently encountered node tree before updating

图4 插入操作后节点b 的最近相遇节点树Fig.4 Recently encountered node tree in node b after inserting

其次，将对该树进行剪枝。 包含节点编号d和e的子节点在树中均出现了2 次。 首先比较2个拥有节点编号d的子节点，其中深度为2 的节点相比深度为3 的节点同时满足具有更小的深度、定时器剩余时间更长2 个条件，故将该深度为3 的子节点及其子树删除。 然后再比较2 个拥有节点编号e的子节点，其中深度更小的节点的定时器剩余时间更短，不同时满足2 个剪枝条件，故这2 个节点保留。 剪枝完成后的最近相遇节点树如图5 所示。

2.2.3 转发副本数量控制策略

假设当前节点携带了某条消息的M个副本，在与中继节点建立了通信链路后，将其中N个副本转发给中继节点，则N的数量如式(4)所示。

图5 剪枝操作后节点b 的最近相遇节点树Fig.5 Recently encountered node tree in node b after pruning

其中，条件1 为中继节点的递交概率大于2倍的当前节点递交概率，且当前节点的剩余缓存容量不足10%。 此时当前节点的缓存区容量即将耗尽，且遇到了递交概率远大于自身的节点，故当前节点将所有副本发送给中继节点。 这样既缓解了当前节点的缓存区占用情况，也保证了该消息的递交成功率不减少。 同时当前节点不保留副本的措施，也避免了递交概率极小的节点长期携带该消息副本，既无法对数据包的递交起到实质性的作用，在数据包完成递交后又难以接收到该消息的反馈包清除网络中残余副本，长期无效地占用缓存资源。

条件2 为中继节点递交概率大于2 倍的当前节点递交概率，且当前节点的剩余缓存容量大于10%。 此时当前节点发送当前剩余副本的3/4 给中继节点，自己保存1/4 副本。 即将更多的副本发送给递交概率远大于当前节点的中继节点，且因自身缓存区剩余量足够，当前节点也仍携带少量副本等待转发机会，增大该数据包总的递交概率。

在满足转发条件的其他情况下，当前节点每次转发剩余副本的一半给中继节点，并保存一半的副本，该条件下转发副本数量控制策略与二分散射等待路由算法相同。

2.2.4 PLR 路由算法实现

为了防止因拥塞而导致无法间接交付问题，规定在每个节点预留出一个数据包最大可能的缓存大小，专门用于对目的节点在最近相遇节点树上的数据包进行接收与快速转发。

综上所述，PLR 路由转发算法流程如图6 所示。

图6 PLR 路由转发算法流程图Fig.6 Flow chart of PLR routing algorithm

3 仿真结果

3.1 仿真参数设置

本文使用基于NS-3 的DTN 仿真软件[10]，选取了社区移动模型[11]，对PLR 路由算法及其他经典路由算法(Epidemic[5]、Spray and Wait[6]、Spray and Focus[7]、Prophet[8])进行仿真与比较。NS-3 是一款强大的网络仿真库，社区移动模型是一类经典的节点运动有一定规律性的网络移动模型。 仿真场景参数设置如表1 所示。 该参数下的社区移动模型网络可模拟深空网络、野生动物网络、城市物联网等场景。

Prophet 路由中计算递交概率向量时的各参数如表2 所示。

3.2 缓存平均占用量分析

缓存平均占用量指每个节点在仿真中每1 s缓存占用量的平均值，用来衡量该路由算法对存储资源的依赖性。 仿真结果如图7 所示。

表1 仿真参数设置Table 1 Settings of simulation parameters

表2 算法参数设置Table 2 Settings of algorithm parameters

图7 不同路由算法的缓存平均占用量Fig.7 Average buffer occupancy of different routing algorithms

Epidemic 路由对数据包副本数量没有限制，占用的节点缓存资源最多，容易导致网络拥塞，从而使数据包超时、丢弃。 Spray and Wait 与Spray and Focus 路由限制了网络中数据包副本的数量。Prophet 路由给转发限定了条件，除非遇到具有更大概率完成递交的节点，否则不产生新的副本。故这3 个路由算法对节点缓存资源的使用相对较少。 PLR 路由在这些限制副本数量策略的基础上，通过最近相遇节点树与在每个节点预留一块缓存的策略，保证了经过多跳可完成递交的数据包可有效利用节点缓存完成转发，故其需要节点存储携带的数据包更少，占用的缓存资源最少。

由图7 可知，当单个节点存储能力大于14 MB时，PLR 路由对节点缓存资源的使用量趋于饱和。 节点更强的缓存能力将不再对PLR 路由有明显的增益效果，这也符合PLR 路由适用于节点缓存资源受限场景的特点。

3.3 递交率分析

递交率指成功送达至目的节点的数据包数量与计划发送的数据包总数之比，是衡量路由算法有效性最直接的指标。 仿真结果如图8 所示。

图8 不同路由算法的递交率 Fig.8 Delivery rate of different routing algorithms

由图8 可知，在节点缓存能力不同的仿真中，PLR 路由的递交率均最高，Epidemic 路由的递交率均最低。 尤其是节点缓存能力小于等于14 MB时，PLR 路由对节点缓存资源的使用尚未饱和，此时它的性能明显优于其他路由算法。

3.4 网络有效开销比分析

网络有效开销比指最终递交至目的节点的副本被转发次数之和与网络中所有副本被转发次数之和的比值，用来衡量该路由算法对带宽等通信资源的有效利用率。 仿真结果如图9 所示。

由图9 可知，每种路由算法在节点最大缓存容量不同的网络中所呈现出的网络有效开销比基本一致。 其中，Epidemic、Spray and Wait、Spray and Focus 算法的转发均存在一定的盲目性，故网络中的很多转发并不能对数据包的递交起到直接作用，故网络有效开销比均较低。 而Prophet 与PLR 路由算法对转发均有较严格的要求。 在保证较高的网络有效开销比同时，PLR 算法仍为多副本路由算法，网络中仍有一定数量的副本以保证该路由的可靠性。 PLR 路由算法较高的网络有效开销比也使它更加适用于网络带宽、功率等资源受限的场景。

图9 不同路由算法的网络有效开销比Fig.9 Effective cost ratio of network of different routing algorithms

综上可知，在该类仿真场景中，PLR 路由算法的缓存平均占用量、递交率、网络有效开销比等网络性能均优于其他经典的多副本路由算法。

4 结论

本文提出的最近相遇节点树机制及基于此机制的PLR 路由算法，解决了DTN 网络中经典多副本路由算法下的无法间接交付问题。 在具有网络拓扑无法准确预知、节点运动有一定社群性或规律性、节点缓存能力与网络资源受限等特点的DTN 典型应用场景中，如未来月表探测、地球社群网络等，PLR 路由算法的递交率、缓存平均占用量、网络有效开销比等性能比传统的Epidemic、Spray and Wait、Spray and Focus、Prophet 算法有所提升，达到了更好的网络性能。