DTN中基于节点相遇规律的自适应散发等待路由

丁安平　马蓓蕾　王炳庭

1(安徽大学计算智能与信号处理教育部重点实验室　安徽 合肥 230000)2(滁州学院电子电气工程学院　安徽 滁州 239000)



DTN中基于节点相遇规律的自适应散发等待路由

丁安平1马蓓蕾1王炳庭2

1(安徽大学计算智能与信号处理教育部重点实验室安徽 合肥 230000)2(滁州学院电子电气工程学院安徽 滁州 239000)

摘要在容滞网络中，针对散发等待BSW(Binary Spray and Wait)路由协议在转发报文时具有一定的盲目性。提出将每个节点维护的路由信息由一维拓展到二维，并在该基础上研究节点的相遇规律，动态地调整报文转发策略，从而解决当前节点与信宿节点相遇概率较低的问题。实验结果表明，该算法与散发等待路由相比，在降低平均延迟的基础上，能有效改善报文的递交率。

关键词容滞网络路由二维矩阵H相遇规律散发等待

0引言

DTN[1]是一种面向报文的、可靠的、通用的覆盖网络[2]。它由若干区域网络组成，能够实现受限网络之间的通信。与存储-转发的交换方式不同，DTN中报文的交换采用存储-携带-转发[3]的方式进行。中继节点可以携带报文移动，在合适的时刻选择合理的方式转发报文，最终将报文递交到信宿节点。在传统的无线网络传输中，通信的实现要求信源节点和信宿节点之间至少建立一条稳定的连接。而在DTN中，节点无规则地移动，网络拓扑结构动态变化，节点呈现稀疏性分布，彼此之间无法建立稳定的端到端连接，这给DTN路由协议的设计带来了巨大的挑战。

在DTN中，由于节点具有差异性[4,5]，某些节点会频繁相遇，而有些节点较长时间内都不会相遇。因此某些报文能够快速传输到目的节点，而有的还需要通过很多跳的中继转发才能到达目的节点。每个报文均有一个生命周期，中继转发的次数越多，延迟越大，报文因超出生命周期被丢弃的可能性越大。在这期间开销必然也消耗更多，这时合理选择一个中继节点[6]显得尤为重要。尤其是在自然灾害时期，时间就是生命[7]，延迟越大，付出的代价就越大。针对节点的这种特性，本文提出节点的中继能力的概念，建立了一个二维矩阵H来研究节点间的相遇规律，并在此基础上提出了ASW-H路由算法。该路由算法根据节点中继能力的大小来转发报文拷贝数及选择下一跳节点。这种自适应性的散发和转发策略更能够适应网络的动态拓扑结构，从而能够显著提高报文的递交率，降低延迟。

1相关工作

由于DTN中节点通过机会连接最终将报文递交到信宿节点，因此报文被递交到信宿节点的概率较低、延迟较大。为了改善DTN的网络性能，DTN常采用多拷贝机制来增加报文到达信宿节点的概率，减小递交延迟。DTN多拷贝路由中最具代表性的路由协议有：蔓延路由(Epidemic)[8]、概率路由(Prophet)[9]及散发等待路由(Spray and Wait)[10]。

蔓延路由采用洪泛机制，源节点对报文的下一跳节点不做任何限制，而直接将报文转发复制给相遇的节点，提高了递交率，降低了延迟，其代价是网络中存在大量的冗余拷贝，易导致网络拥塞[11]。

在概率路由协议中，每个节点根据历史相遇信息维护一张到网络中其他任何节点的概率表，再根据概率的大小关系来转发报文。该协议能明显减小开销, 但报文的递交率随之降低、延迟增大。

为了更有效地控制开销，有人提出了采用配额的方式对报文拷贝数进行控制的散发等待路由算法。它包括源端散发等待和二分法散发等待。

在源端散发等待路由中，源节点将产生的每个报文的拷贝数初始化为L，每次转发后该报文的拷贝数将减少1。当拷贝数减至1时，源节点将转换为直接传输模式。即所有携带该报文拷贝的节点只有遇到报文的目的节点时才将报文转发出去。而在二分散发等待路由算法中，节点A只要与节点B相遇就会转发n/2个副本。这种算法在保证递交率的同时，有效地降低了开销，但是在中继节点的选择上具有一定的盲目性。

目前，针对散发等待路由如何选择中继节点以及散发的副本数，国内外研究者做了大量的研究，并取得了较好的结果。可是如果两个相遇的节点，其与信宿节点相遇的概率均较低，就很难提高报文的递交率。这时我们将每个节点维护的路由信息从传统的一维拓展到二维，建立一个二维矩阵H，并在此基础上研究节点的相遇规律。

在现实世界中，网络内节点的相遇均有一定的规律性[11]。有些节点会频繁相遇，而有些节点可能很长一段时间内都不会相遇，这时合理选择一个中继节点显得尤为重要。本文提出了一种基于节点相遇规律的自适应散发等待路由算法(ASW-H)。该算法充分利用节点的相遇规律来动态地调整报文转发的方向及副本数，更能够适应网络的动态拓扑结构，从而解决当前节点与信宿节点相遇概率较低的难题。在降低平均延迟的基础上，有效改善报文的递交率。

2一种自适应散发等待路由

在DTN中，节点的相遇均呈现一定的规律性。一个节点在最近一段时间内可能会遇到若干个节点，而这若干个节点又会分别与其他节点相遇，因此可以利用一个二维矩阵来反映节点间的这种相遇规律。该二维矩阵比传统协议中的一维路由表更能反映节点间的相遇规律。当节点运动时，实时更新该矩阵以反映最新的相遇信息。通过该二维矩阵分析两两节点之间直接相遇与间接相遇的可能性，以期解决当前节点与信宿节点相遇概率较低时的路由选择难题。

定义节点中继能力的大小为Pr，它由两个参数来衡量，一个是直接相遇能力值，即本节点直接与目的节点相遇的能力值Prd；另一个是间接相遇能力值，即此节点与目的节点通过一跳中转间接相遇的能力值Pri。本文利用每个节点维护的一个二维矩阵H来反映节点间的相遇规律，计算节点中继能力值，选择最优中继节点及具体的散发份数。

2.1矩阵H的建立和更新

节点A建立一个m+1行m列的矩阵HA，如下所示。第一行表示最近与A相遇的m个节点的ID号，删去矩阵HA第一行后的每一列分别用来记录与第一行每个节点最近相遇的其他m个节点的ID号。如A11最近遇到的m个节点为A21，A31,…,Am+1m。

为了维持最新的节点分布状态，每个节点需要实时地更新矩阵。例如节点A更新过程如下：首先，假设节点A1j是最早与节点A相遇的节点，节点A将从矩阵HA中删除节点A1j(1≤j≤m)所在的那一列。其次，假设节点B在最近分别遇到节点B11，B12,…,.B1m，节点A获得节点B的这些信息，并将B的这些信息添加到矩阵HA中，更新后的矩阵如下所示。

2.2中继能力的计算

假设目的节点D在矩阵HA的第一行中出现的次数为n，而出现在删去矩阵HA第一行后的矩阵的每一列的次数为ni。节点A的Prd和Pri分别计算如下：

(1)

(2)

结合式(1)、式(2)，可以得到节点中继能力的计算公式，如式(3)所示，其中参数a用来平衡Prd与Pri在Pr中所占的比例。

(3)

2.3路由过程

当两个节点相遇时，节点首先更新各自维护的矩阵和节点中继能力的大小，然后彼此交换各自的节点中继能力值，最后根据中继能力大小的比值关系来动态地散发报文拷贝数。

随着节点在网络中不断散发报文，报文的拷贝数将不断减小。当报文的拷贝数为1时，节点将转换为直接传输模式。

3仿真

3.1仿真参数设置

本文使用开源仿真工具ONE进行仿真。仿真场景为芬兰首都赫尔辛基地图，大小为4500 m×3400 m，共放置了126个节点，这些节点被分成了6个组。报文产生间隔为10到20秒，报文的大小为50 k到100 k之间。具体参数如表1所示。

表1　仿真参数设置

在上述仿真环境下，比较Epidemic、BSW、Prophet及本文所提出的ASW-H路由算法在报文递交率、网络开销率及平均延迟上随时间的变化情况。

3.2结果与分析

从图1可以明显地看出ASW-H路由算法在整个仿真期间的递交率一直高于其他三种路由算法。这是因为ASW-H算法将传统的一维路由表拓展成二维的矩阵，不仅考虑了两个节点直接相遇的可能性，还分析了两个节点间是否存在更好的中间节点。这种协议算法更能够适应现实网络状况的变化，从而避免了BSW散发报文的盲目性。

图1　递交率随时间的变化

从图2可以看出，BSW和ASW-H的平均延迟明显低于Epidemic和Prophet，而ASW-H的平均延迟略低于BSW。这是由于ASW-H根据节点的相遇规律，动态地调整报文转发的方向及副本数，使得报文快速到达目的节点。

图2　平均延迟随时间的变化

从图3可以看出,在前9 ks的时间里，ASW-H的平均开销率略高于Prophet，但到了9 ks以后，ASW-H的平均开销率逐渐低于Prophet。这是因为ASW-H更能动态适应网络的现状来转发报文拷贝数及选择下一跳节点。ASW-H的平均开销率高于二分散发等待路由算法，这是因为ASW-H通过了更多的中继节点的转发，牺牲开销以换取递交率的提升。

图3　开销率随时间的变化

4结语

本文将每个节点维护的路由信息由一维拓展到二维，通过二维矩阵来反映节点之间的关系，动态地调整报文转发的方向及副本数，从而解决了当前节点与信宿节点相遇概率较低的难题。仿真结果显示，本文提出的ASW-H算法更能动态地适应现实的网络状况，从而提高了递交率，降低了延迟。

在算法复杂度方面，本文的ASW-H算法跟其他路由相比要复杂一些。未来的工作主要考虑在降低复杂度的同时能够更进一步提高报文递交率，降低延迟和开销。

参考文献

[1] Hisamatsu Tsuyoshi,Asaeda Hitoshi.Adaptive Overlay Network for High-Bandwidth Streaming[J].Journal of Information Processing,2012,20(1):154-166.

[2] Ryohei Dou,Akihiro Fujihara,Hiroyoshi Miwa.Algorithms for the Base Node Location Problem in the Virtual Segment Method in Store-carry-forward Routing Schemes[C]//Intelligent Networking and Collaborative Systems,Thessaloniki,2010:374-379.

[3] Yahui Wu,Su Deng,Hongbin Huang.Information spreading in Delay Tolerant Networks based on nodes’ behaviors[C]//Communications in Nonlinear Science and Numerical Simulation,2014:2406-2413.

[4] 刘唐,彭舰,杨进.异构延迟容忍移动传感器网络中基于转发概率的数据传输[J].软件学报,2013,24(2):215-229.

[5] Rong Geng,Meisi Tang,Xianghong Jiang.Spray and Wait Routing Based on Relay-Probability in DTN[J].Journal of Northeastern University,2012,33(12):1698-1701.

[6] 段卓君,王小明,李成博.基于DTN的地震紧急救援通信系统研究[J].计算机应用与软件,2014,31(1):111-116.

[7] 窦飞,高永智.DTN中蔓延路由协议拥塞控制方案研究[J].现代电子技术,2010,327(16):169-171.

[8] 朱桂明,郭得科,金士尧.基于副本复制Bloom Filter的P2P概率路由算法[J].软件学报,2011,22(4):773-781.

[9] 张迪,王贵竹.DTN中概率选择的散发等待路由[J].通信技术,2010,43(5):145-147.

[10] 王朕,王新华.ISM:新一代绿色机会网络设备的缓存管理策略[J].计算机应用与软件,2011,28(11):193-198.

[11] 任伟,董育宁,赵海涛.一种改进的基于地理位置的无线Mesh网络路由协议[J].南京邮电大学学报,2012,32(1):75-83.

AN ADAPTIVE BINARY SPRAY AND WAIT ROUTING ALGORITHM BASED ON NODE ENCOUNTER LAW IN DTN

Ding Anping1Ma Beilei1Wang Bingting2

1(MinistryofEducationKeyLabofIC&SP,AnhuiUniversity,Hefei230000,Anhui,China)2(SchoolofElectronicandElectricalEngineering,ChuzhouUniversity,Chuzhou239000,Anhui,China)

AbstractIn delay-tolerant networking (DTN), Binary Spray and Wait (BSW) routing protocol has a certain blindness when forwarding messages. To deal with this issue, we propose to expand the routing information maintained by each node from one dimension to two dimensions, and study on this basis the encounter law of nodes as well as adjust dynamically the messages forwarding strategy, thereby solve the problem of low encounter possibility of current nodes and the destination nodes. Experimental results show that the proposed algorithm can effectively enhance message delivery rate on the basis of reducing the average latency compared with BSW routing.

KeywordsDelay-tolerant networkingRoutingTwo-dimensional matrix HEncounter lawBSW

收稿日期：2014-09-13。丁安平，硕士生，主研领域：容滞网络路由算法。马蓓蕾，硕士生。王炳庭，讲师。

中图分类号TP3

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.031