基于节点接触频率的DTN路由算法

黄沁芳

(集美大学 诚毅学院， 福建 厦门 361021)

0 引 言

延迟容忍网络[1-2](Delay Tolerant Network，DTN)是一种具有链路频繁断裂、高延迟、网络拓扑动态变化、节点资源有限等特点的新型网络体系结构。在现实中很多应用领域都属于这类网络，例如车载网络、无线传感网络、救灾现场、野战通信、星际网络等[3]。

与传统网络的端到端的通信机制不同，在DTN中，节点与节点之间并不一定能建立一条稳定可靠地端到端的通信路径，先探路后转发的传统路由方式不再适用，因此DTN中使用的是一种“存储—携带—转发”的路由方式[4]：当一个节点收到消息时，如果没有路径可到达目标节点或其它节点，先将消息保存在缓存中，并且一直携带直到遇到一个可转发消息的节点。转发路径的路由选择可以是随机的，也可以根据节点的历史信息预测。在延迟容忍网络中，由于链路频繁断裂、网络拓扑动态变化等特点，要获得节点的完整信息不是容易的事情，那么消息的传输就变得很难确定。如何有效地将消息转发出去，是DTN路由要解决的问题。

近年来，研究者们已经提出了几种典型的DTN路由算法，其中Epidemic算法[5]是最为经典的算法之一，就是将消息类似病毒的方式传播给网络中所有遇到的节点，直至达到目标节点。Epidemic算法是以不断扩散消息副本的方式将消息传送到目的节点，在某些特定的网络中具有很高的传输成功率和很小的延迟，但它需消耗大量的网络资源，如带宽、缓存、能量等，因此当网络扩大，消息副本数量增加时，其网络性能就会大大降低。

为了控制资源开销，Spray and Wait算法[6]采用将消息副本数量固定一个配额，消息的转发方式分为传播(Spray)和等待(Wait)两个阶段。在消息产生的时候就确定了副本数量为L。在传播阶段，当携带有消息副本的节点与无相同消息的节点相遇时，节点会将携带的消息副本的一半发送给对方节点，自己保留剩余的一半，直到所携带的消息副本数量为1为止；在等待阶段，收到消息的节点等待与目标节点相遇并将消息转发给目标节点。由于消息副本的配额是固定的，副本数量L不会随着网络中节点数的增加而增大，因而有很好的扩展性，有效地控制了开销。

本文基于Spray and Wait算法，提出了基于节点接触频率的有效路由算法(Efficient Routing Based on Inter-contact Frequencies，ERBIF)。该算法根据本节点在网络中与其它节点曾有过的接触频率，动态分配消息副本，接触频率高的节点优先获得消息副本。

1 基于节点接触频率的路由算法

1.1 基本思想

图1 节点接触频率分配示例

在某些DTN网络中，节点的移动频率和范围都很大，节点与节点之间的接触频率也会不一样，那么有些节点与其它节点的接触频率就会比较高。当节点要转发消息时，应先将消息转发给接触频率最高的相邻节点。例如，网络中有如图1所示节点，每个节点都需要维护一张自己与其它节点的接触频率值的数据表，假设节点A要转发消息，根据其接触频率值数据表，与节点A接触频率由高到低的节点依次是B、C、D，那么节点A就将消息副本(数量为L)的一半先转发给节点B，然后再将剩余的消息副本(此时数量为L/2)的一半转发给节点C，再将剩余一半转发给D，直至节点A的消息副本数量减小到1为止。节点B收到消息后，根据其接触频率值数据表按照接触频率由高到低将消息依次转发给节点C、G、F。其它收到消息副本的节点以同样的方法按照自己的接触频率值数据表来转发消息。这样可以很快将缓存的消息发送到目标节点，能降低延迟，节省缓存空间，也有效地防止数据的丢失和溢出。

1.2 节点的接触频率

根据LIAO Yong等[7]给出的一种计算节点间平均接触频率的方法，定义时间单元t内的平均接触频率为fi j=Ci j/t。将此平均接触频率记录在每个节点的接触频率值数据表中，以此来估计一个节点遇到其它节点的概率。数据表中所有频率值按从大到小排列。平均接触频率值越大，遇到相应节点的机会就越高。

由于fi j可以由节点i与节点j的历史相遇信息得到，随着时间的推移，两节点相遇的频率值可以得到逐步更新。从而使得消息副本的转发能够按照当前的节点运动规律进行。但当网络规模很大，节点数很多的时候，对于节点接触频率的预估会变得很复杂，因此，此种机制仅适用于小规模的DTN网络，本文假设在只有两跳的网络中来实现。在简化的只有两跳的虚拟网络中只有源节点、目的节点及邻居节点，从源节点到目的节点可能有m条路径，只需要按照m条路径的节点接触频率值来分配消息副本即可。

1.3 节点间消息副本的分配

Spray and Wait算法将消息副本数量固定一个配额，在源节点就确定了需要转发的消息副本数量。由于DTN网络动态变化，由源节点确定的消息副本数量不一定适合中继节点。在ERBIF算法中，每个节点根据当前所处位置与相邻节点的接触频率来动态选择要转发的消息副本数量。

网络中节点的中心性[8]是节点重要性的度量。例如在社会网络中，中心性高的人比较活跃，接触其他人的频率也较高。同样的，中心性高的节点也维持了更多和网络中其它节点的接触，从而有更多和其它节点通信的机会。当两个节点相遇时，接触频率高的节点自然将获得较多的消息副本。

假定有N个节点的DTN网络中，源节点产生的消息副本数量为L。当携带消息副本的节点A遇到节点B，如果节点B携带相同的消息，则不转发；如果节点B没有此消息，则根据接触频率值数据表，找出A、B两节点的接触频率fAB，根据fAB值在数据表中排列的顺序号(假设为m，m≥1)，则节点A向节点B转发消息副本数量为L/2m。fAB在数据表中值最大，则m=1；排第二时，m=2；以此类推。节点B也按类似的方式将消息副本转发出去，直至消息副本最终到达目的节点。

2 仿真结果及分析

本文使用ONE仿真软件作为实验模拟平台，版本1.5.0。采用RWP移动模型，在相同场景下，对本文提出的ERBIF算法和Epidemic以及Spray and Wait算法的性能进行对比，并用以下3个参数进行性能评估：

1)传输率：目的节点成功接受到的消息数量与源节点产生的消息总数之比;

2)传输延迟：消息到达目的节点所耗费的平均时间;

3)传输次数：消息从源节点到目的节点传输的总次数。

网络的仿真环境：800 m×800 m的网络中，随机分布25个节点，节点的移动速度在0.5～2.0 m/s范围内，并且在0～120 s区间中随机确定暂停时间，每个节点的移动范围为30 m，缓存空间为5 MB。消息产生的时间间隔为20～30 s之间，每个消息大小为512 KB。

图2 传输率随时间的变化

从图2可以看出，随着时间推移，3种算法的传输率逐渐趋于一致，增长幅度也趋于平缓。Epidemic算法和Spray and Wait算法对于消息的转发是随机的，随着时间的增长，所需缓存增加，丢弃的数据也会增加，而ERBIF算法依据节点的接触频率，消息的转发机会变多，其传输率也会有所提高。相对其它两种算法而言，ERBIF算法的传输率也略高。

从图3可以看出，随着时间增长，3种算法的传输延迟也会逐渐增大。如果节点间的接触频率高，那么消息的转发速度也会变快，基于接触频率的ERBIF算法能够以更大的机会，以更快的速度将消息转发到目的节点，因此它的传输延迟会略低于Epidemic算法和Spray and Wait算法。

图4反映了ERBIF、Epidemic和Spray and Wait 3种算法消耗网络资源的情况，随着时间增加，传输次数不断增加，其消耗的带宽、能量和缓存也越来越多。Epidemic算法由于没有限制消息副本的数量，消息的转发是随机的，因此其传输次数最多；有固定消息副本配额的Spray and Wait算法传输次数相对较少。而ERBIF算法，由于消息副本数量是固定一个配额，且按节点间接触频率大小，以最大机会到达目的节点来转发消息，因此其传输次数也是最少的。

图3 传输延迟随时间的变化 图4 传输次数随时间的变化

3 结束语

在Epidemic算法和Spray and Wait算法的基础上，本文引入了一种基于接触频率的路由算法。通过统计节点与节点之间在某一时间段内的接触频率值，根据所有频率值大小来动态分配转发消息副本的顺序和数量。仿真结果显示，在有限的网络资源，网络规模不大的情况下，这种基于节点的接触频率来转发消息的算法，能较好地提高DTN网络的性能，有效地节约资源，降低延迟。

[参考文献]

[1] FALL K.A delay-tolerant network architecture for challenged internets[C]//Proceedings of SIGCOMM.New York:ACM Press,2003:27-34.

[2] 肖明军,黄刘生.容迟网络路由算法[J].计算机研究与发展,2009,46(7):1065-1073.

[3] 陈晨,高新波.一种无线传感器网络移动性支持自适应MAC协议[J].西安电子科技大学学报:自然科学版，2010,37(2):279-284.

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

[5] VAHDAT A,BECKER D.Epidemic routing for partially connected ad hoc networks.Duke Technical Report CS-2000-06[R].Dur-ham:Duke University,2000.

[6] SPYROPOULOS T,PSOUNIS K,RAGHAVENDRA C S.Spray and Wait:An efficient routing scheme for intermittently connect-ed mobile networks[C]//Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking.Philadelphia,Pennsylvania,USA,2005:252-259.

[7] LIAO Yong,TAN Kun.Estimation based Erasure-coding Routing in Delay Tolerant Networks[C]//Proceeding of the 2006 International Conference on Wireless Communication and Mobile Computing.British Columbia:Vancouver,2006:557-562.

[8] DALY E M,HAAHR M.Social network analysis for information flow in disconnected delay-tolerant MANETs[J].IEEE Trans on Mobile Computing,2009,8(5):606-621.