吴俊，严俊

　　(扬州大学 信息工程学院,江苏 扬州 225127)

      摘要：提出了一种热点区域间节点流传输算法，在该算法中，将节点频繁访问的区域作为热点区域并以热点区域为中心将整个网络环境划分为若干块。节点在热点之间携带数据进行转发从而提高了空闲节点的利用率。最后分析了该路由算法与传统的延时容忍网络路由算法在各方面的性能表现，证明了所提出算法的高效性。

　　关键词：热点区域;延时容忍网络;传输链路;节点流

0引言

　　当前网络服务模型的设计主要基于一些现有的端到端传输理论。这些理论不能应用在一些新兴的网络中，比如在边境监控中大量部署的无线传感器网络、偏远地区的非即时数据传输系统。在上述环境中，由于基础设施的不完善或者出于成本考虑，使用传统的网络连接是不现实的。为了允许上述网络中的节点可以相互通信，延时容忍网络的概念被提出并进行运用。传统的延时容忍网络需要节点存储信息等待下一个节点进行转发，这将浪费大量时间从而增加了延迟。GROSSGLAUSER M的研究工作已经说明通过减少源节点和目标节点之间的跳数可以提升数据的吞吐量从而减少时延［1］。

　　当前的延时容忍网络路由算法存在一个问题，即：当从源节点到目的节点的转发跳数过多时，大量的闲置节点没有被使用，这既造成了资源的浪费，也在无形中增加了数据的传输时延。为了解决这个问题，本文提出了一种热点区域间节点流传输算法，该算法充分利用了延时容忍网络中的大量闲置节点，通过使用热点区域之间的频繁移动节点进行数据转发从而提升了数据的吞吐量，减少了传输时延，并提高了数据传输的成功率。

　　最终通过相关的实验仿真，对该算法的传输时延、通信开销等性能与传统的路由算法进行比较，证明了所提出算法的可行性和高效性。

1延时容忍网络

　　延时容忍网络（Delay Tolerant Network, DTN）的路由是一种虚拟的路由，与传统自组网中的实际的物理路由相比，DTN的路由不需要在信息传输的整个过程中有端到端的连接。延时容忍网络的路由主要是携带存储转发的方式［2-3］。在DTN中做出路由选择的决定并不需要端到端的连接。DTN路由也遭遇一些其他的挑战，比如节点的缓存空间有限、传输成功率低等。正是由于这些传统网络中的一些路由方法比如动态资源路由在DTN中是无效的，DTN的路由选择使用新的模型，包含独立的语句、本地发送指令等［4］。传统的延时容忍网络主要分为以下几种路由方法：

　　（1）概率路由：概率路由使用节点之前的碰撞历史记录来预计未来的碰撞概率。当两个节点再一次相遇时，概率路由提升两个节点的碰撞概率［5-6］。同样的由概率路由发展而来的最大概率路由［7］和最大贡献路由［8］则是由基于发送成功率而形成的存储优先次序拓展而来。

　　（2）社会网络路由：由于携带移动设备的人或设备通常存在一定的社会关系，因此基于社会网络的路由算法［910］探索了社会网络用于延时容忍网络中发送数据包的性能优劣。

　　（3)传染路由：当源节点在它的周围发现有n个邻居节点,且这些邻居节点都在源节点的通信范围之内，源节点将n份数据包拷贝发送给这些邻居节点。然后这些节点携带数据包移动直到目标节点接收到数据包或数据包的生命周期已经结束。

　　（4）散发等待路由：散发等待路由［11］是传染路由的一种改进。相对于传染路由散发等待路由通过设置传输节点数目的上限减少了一定的通信开销从而减少了网络拥塞。

2一种基于热点数据传输方案

　　2.1存在问题及解决方案

　　在延时容忍网络中，一个关键的问题就是高效的路由选择。因此本文集中关注如何通过利用节点的移动能力提升数据吞吐量、减少时延并提高数据传输的成功率。如图1左侧图所示为在传统的DTN路由算法中，源节点1产生数据包并需要将数据包发送到目的节点7、8。它首先由移动节点1携带数据包等待遭遇移动节点2。节点2将数据转发并等待预计碰撞目的节点8的节点3和预计碰撞目的节点7的节点4。由于单一节点碰撞另一节点的概率较低，因此这需要消耗较多的时间等待，从而产生较大的延迟。并且大量的节点移动并没有被利用，这也造成资源的浪费。这里使用一种新的传输方法进行数据的转发。

　　如图1右侧图所示，当数据包从源节点1产生需要发往目的节点7和8时，可以规划路径，分别为热点H1、H2、H5、H7和H1、H2、H5、H8、H9。NodeFlow用从一个热点Hi到热点Hj之间的移动节点表示两个热点之间的数据传输能力。在传输过程中，热点使用距离向量来构建自身的路由表从而指明下一跳的热点。热点之间的传输使用概率路由，然后每个热点根据已经构建的路由表选择到下一个目的热点传输效率高的节点转发数据。这极大地提高了数据转发的成功率并降低了时延。

　　2.2具体实现

　　本文延时容忍网络数据传输系统主要由以下几部分构成：

　　（1）热点的选择

　　选择移动节点频繁访问的地点作为热点，并以热点为中心把整个网络环境划分成若干份。为了选择热点，一个简单的方法就是收集节点的历史访问记录并将访问记录较高的地点作为热点。根据产生的热点构建热点列表。当然在同一个区域内选择节点访问次数最多的点为候选热点。

　　（2）构建路由表

　　在延时容忍网络中，每个热点使用它与其他热点之间的节点流动数量来表示两个热点之间的传输带宽并根据此带宽来估计传输时延。根据预计的时延，路由表指出在传往目的热点过程中的每一个下一跳热点。

　　①传输带宽：在这里用Ntij表示热点i、 j之间的节点数目，那么热点之间的带宽为：

　　其中Bijnew和Bijold分别为更新后的带宽和更新前的带宽。

　　②构建路由表：根据已经产生的链路带宽表，每个热点计算发送大小为W bit数据给邻居热点所需要的时延。假设每个节点的内存为S bit，从热点i到j传输的预计时延为。T是传送W bit数据的时间单位。然后每个热点的路由表根据自身到邻居热点的时延初始化。每个热点使用距离向量协议构建传输过程中指明下一跳热点的完整路由表。并且整个传输过程的时延为D(Hi,Hd)。对于路由表中的每一项，如果目的热点Hd不在i的路由表中，则通过设置下一跳ID为Hj、总共时延为Dij+D(Hi+Hd)将目的热点增加到路由表中。如果目的热点已经存在，则检查是否D(Hi,Hd)≤Dij+D(Hj,Hd),如果是则不改变，否则下一跳ID为Lj，总时延更新为Dij+D(Hj,Hd)。这个过程不断重复直到每个热点最终到达目的热点。

　　（3）预测传输节点

　　由于延时容忍网络依赖于节点的移动转发传送数据，因此选择合适的节点进行转发对整个传输过程是至关重要的。这里根据每个节点对热点的历史访问记录预测节点的下一次传输位置。

　　为了预测节点的传输目标热点，这里使用orderk马尔科夫预测［10］。假设下一次传输与过去的k次传输相关。一个节点的传输历史表示为：

　　TH=Tx1,x2Tx2,x3…Txj－1,xj…Txn－1,xn

　　这里Txj－1,xj表示从热点Hxj－1到Hxj的一次传输。使用X(n－k,n)=Txn－k,xn－k+1…Txn－1,xn表示过去k次连续的传输。因此一个节点每次可能的下一次传输Txn,xn+1的概率如下所示：

　　and

　　这里N(X(·))和N(Allk)表示X(·)的数目和TH中k次连续的传输。然后产生最大概率的传输被选择为预计传输节点。

　　在数据包发送过程中，热点根据自身的路由表选择下一跳热点然后使用预测的节点将数据包转发给下一个热点。本文路由算法分为以下几步：

　　①当源节点产生数据后，将数据包发送给遭遇的第一个热点；

　　②当热点Hi接收数据包后首先检查是否存在节点将数据包直接发送给目的热点。如果存在此节点，则将数据包发送给该节点；

　　③否则，热点Hi检查自身路由表选择合适的下一个热点并将热点ID和预计的总时延附加在数据包上；

　　④热点Hi监测周围节点是否有合适的内存并将数据包发送给访问下一个热点概率最高的节点；

　　⑤当节点遭遇热点Hj后，将数据包存储在热点Hj中，然后重复上述过程选择下一个热点直到最终传送到目的热点。

3性能分析

　　下面使用ONE 模拟器［11］进行一个基于热点传输事件的仿真并将仿真结果与其他传统传输方法进行对比。仿真在赫尔辛基城市地图（ONE模拟器默认地图）上进行，整个仿真区域的范围为10 000 m×5 000 m，网络中共有200个节点，城市地图中存在15个热点区域。数据产生速率为每个节点每30 s产生一条消息，网络中每个节点的移动速度相同，数据包的生命周期设置为1 000 s。数据的大小从10 kb~100 kb随机分配。节点的通信范围为50 m，数据传输速度为50 kb/s。将热点传输方案与传染路由、散发等待路由和先知路由进行对比。为了全面验证热点间节点流传输算法，本文使用数据传输时延、传输成功率以及通信开销作为性能评价指标。

　　（1）通信开销对比：图2和图3比较了在节点内存和数据包的大小变化情况下几种不同的路由方法的通信开销，在相同的数据包大小和数据传输率下，先知路由的通信开销最小，而基于热点路由的通信开销稍大于先知路由，而传染路由产生最大的通信开销。同时随着节点内存的增加，热点路由的通信开销增加比较缓慢。由此可见，基于热点路由在减少通信开销方面有较好的表现，并且不随节点内存变化而产生较大影响。

　　（2）传输成功率：图4和图5展示了在节点的内存和数据包的大小变化情况下4种不同的路由方法的传输成功率。由图可知，在设定的生命周期内传染路由的传输成功率最高，其次是热点路由。根据仿真的输出结果可知，热点路由的表现已经优于散发等待路由。当节点的内存上升时，传输成功率也随之上升。同样可以看出，当数据包大小不断上升，这几种方法的传输成功率开始下降。这可以说明延时容忍网络对数据包的大小有一定要求。

　　（3）平均传输时延：图6和图7说明了测试中使用这4种不同的路由方法的平均时延。可以观察到，基于热点路由的平均时延大于传染路由但小于散发等待路由，而先知路由则产生了最高的传输时延。

　　通过以上仿真可以看出，不管在哪种条件下，热点路由在通信开销成功率和传输时延方面都可以取得较好的表现，在各方面可以取得一个平衡。

4结束语

　　本文提出了一种基于热点区域间节点流进行数据传输的路由算法。该算法充分利用热点区域间大量频繁移动的节点进行数据传输，提升了通信链路的数据吞吐量，减少了因不存在合适转发节点而导致的大量等待时间。仿真实验结果表明，与传统的延时容忍网络路由选择算法相比，本文提出的算法在传输时延和通信开销方面有着较均衡的表现。

　　同时，仿真结果也表明，如果过多的节点参与数据传输就会产生一定的网络拥堵，将导致网络链路负载加重，进而产生网络拥塞等问题，因此提出合适的通信链路负载均衡策略是本文的后续工作。

       参考文献

　　［1］ LINDGREN A, DORIA A, SCHELN O.Probabilistic routing in intermittently connected networks［J］. Mobile Computing and Communications Review, 2003,7(3):1920.

　　［2］ LI F, WU J. MOPS: providing contentbased service in disruptiontolerant networks［C］. In Proc. IEEE ICDCS, 2009: 526533.

　　［3］ DALY E M, HAAHR M. Social network analysis for routing in disconnected delaytolerant MANETs［C］. In Proc. ACM MobiHoc, 2007: 3240.

　　［4］ BURGESS J, GALLAGHER B, JENSEN D, et al. MaxProp:routing for vehiclebased disruptiontolerant networks［C］. In Proc. of INFOCOM, 2006:111.

　　［5］ BALASUBRAMANIAN A, LEVINE B N, VENKATARAMANI A. DTN routing as a resource allocation problem［C］. In Proc. of SIGCOMM, 2007,37(4):373384.

　　［6］ LEE K, YI Y, JEONG J, et al. MaxContribution: On optimal resource allocation in delay tolerant networks［C］.In Proc. of INFOCOM, 2010,14(3):11361144.

　　［7］ HUI P, CROWCROFT J, YONEKI E. Bubble rap: socialbased forwarding in delay tolerant networks［C］. In Proc. of MobiHoc, 2008,10(11):15761589.

　　［8］ DALY E M, HAAHR M. Social network analysis for routing in disconnected delaytolerant manets［C］. In Proc. of MobiHoc, 2007:3240.

　　［9］ YONEKI E, HUI P, CHAN S, et al. A socioaware overlay for publish/subscribe communication in delay tolerant networks［C］. In Proc.of MSWiM, 2007:225234.

　　［10］ COSTA P, MASCOLO C, MUSOLESI M, et al. Sociallyaware routing for publishsubscribe in delaytolerant mobile ad hoc networks［J］.IEEE JSAC, 2008，26（5）：748760.

　　［11］ KERANEN A, OTT J, KARKKAINEN T. The ONE simulator for DTN protocol evaluation［C］. Proceedings of the 2nd International Conference on Simulation Tools and Techniques,Rome,2009:110.