基于历史相遇概率的容迟容断网络主动拥塞控制算法

摘要：为了解决容迟容断网络（DTN）由于节点拥塞造成网络阻塞的问题，提出了一种基于历史相遇概率的主动拥塞控制算法。该算法提出了参考概率这一概念，可以通过节点的拥塞程度动态调整参考概率的大小，进而控制消息的转发条件，以达到对节点拥塞的避免与控制作用，并且在网络资源出现空闲时，可以提升空闲资源的利用率，提高整个网络的传输效率。仿真结果表明，该算法提高了整个网络的递交率，降低了负载比率及消息丢失率，在实现主动拥塞控制的同时也提升了网络的传输性能。

关键词：容迟容断网络；概率策略路由；主动拥塞控制；参考概率；动态调整

中图分类号： TP393.07

文献标志码：A

Abstract：

To solve the congestion problem at node in delay tolerant networks， an active congestion control strategy based on historical probability was proposed. The strategy put forward the concept of referenced probability that could be adjusted dynamically by the degree of congestion. Referenced probability would control the forwarding conditions to avoid and control the congestion at node. At the same time the utilization of idle resources and the transmission efficiency of the network would be promoted. The simulation results show that the strategy upgrades delivery ratio of the entire network and reduces the load ratio and message loss rate. As a result， the active congestion control is realized and the transmission performance of the network is enhanced.

Key words： Delay Tolerant Network （DTN）； probability policy routing； active congestion control； referenced probability； dynamic adjustment

0引言

容迟容断网络（Delay Tolerant Network，DTN）网络在2003年，由Fall[1]提出，其基本设计目标是支持具有断续连接、大时延、高误码率等特性的异构网络的互联和互操作。DTN具有与传统网络不同的特性，不能采用传统的方法解决DTN中的问题[2-3]。影响DTN正常运行的关键技术有很多，拥塞控制技术便是其中之一。

DTN拥塞控制根据关注点的不同可分为节点级拥塞、链路级拥塞和区域级拥塞。节点级拥塞控制方法有被动拥塞控制和主动拥塞控制两种，目前对DTN拥塞控制的研究普遍为被动拥塞控制，而主动拥塞控制较少。被动拥塞控制算法以消息丢弃策略为主，主要思想有丢弃排队时间最长（Drop Front，DF）的消息、丢弃最后到达（Drop Last，DL）的消息、丢弃剩余生存时间（Time To Live，TTL）最少（Drop Oldest，DO）的消息、丢弃剩余TTL最多（Drop Youngest，DY）的消息[4-6]。其中性能表现较好的是DF和DO，原因是这两种丢弃策略先丢弃的是在网络中存在时间较长的报文，这种报文在网络中有更多的拷贝，丢弃它们不但控制了拥塞，且对网络的递交性能影响最小[7-8]。节点主动拥塞控制算法有以下几种：1）SenTCP（Sensor Transport Control Protocol）[9]是一种专门为传感器网络设计的开环逐跳拥塞控制协议；2）ESRT（EventtoSink Reliable Transport）[10]采用基于节点的本地缓冲监测的拥塞检测机制，根据网络的当前状态调节节点速率，实现拥塞控制；3）ACC（Autonomous Congestion Control）[11]采用经济价格模型提出了一个基于规则的拥塞控制机制，该方案中每一个路由节点基于可用缓冲、接收一个消息的风险和收益等本地信息，自主决定是否接收消息。以上算法为协议改进，算法较为复杂，在实际应用中很难实现。

本文设计的动态调整参考概率（Dynamically Adjusting Referenced Probability， DARP）主动拥塞控制算法，以历史相遇概率策略路由（Probabilistic Routing Protocol using History of Encounters and Transitivity，PROPHET）算法为基础。PROPHET算法的思想是节点以历史相遇概率作为比较依据，只有当相遇节点的递交概率大于转发节点的递交概率时才对消息转发，即消息只会被转发给那些更有可能向目的节点传递消息的节点。该算法的优点是选择性地转发消息，在节约网络中有限资源的同时，也提高了每次转发的递交效率。在此基础上，DARP算法提出参考概率这一概念，重新定义转发规则，根据节点拥塞程度即节点缓存占用比调整参考概率的大小，以此控制数据的转发，在不影响其他节点传输消息的情况下，实现对局部拥塞节点的主动拥塞控制。同时，本算法还能够在网络资源有所空闲的情况下，提高DTN资源的利用率，实现DTN的高效传输。

3仿真实验与分析

3.1性能指标

DTN技术的应用目的是在恶劣的通信条件下尽可能多地实现数据的传递，因此递交率的高低是评价一种DTN算法最重要的评价指标[12]。负载比率和消息丢失率是检测网络出现拥塞程度的主要指标[13-14]，本文通过3个指标分析算法的性能，分别定义如下。

1）递交率。递交成功的消息数量与总的投递消息数量的比值，是DTN技术最重要的评价指标。

2）负载比率。定义为：

O=成功传输消息的次数-传到目的地消息的个数传到目的地消息的个数

用来描述消息传递的重复率。负载比率越高说明消息传输的重复率越高，网络的效能越低，若负载比率为0，即成功传输消息的次数等于传到目的消息的个数，说明传输效率为100%。

3）消息丢失率。定义为：

D=丢失消息的个数连接开始时传递消息的总个数

消息丢失率表示由于TTL到期及缓存发生拥塞而被丢弃的消息所占的百分比，在相同的网络环境中，由于TTL到期而被丢弃的消息比例相同，因此丢失率可以用来描述网络出现拥塞的程度。

3.2仿真场景设置

ONE（Opportunistic Network Environment）仿真平台是基于Java的离散事件仿真器，是专门针对DTN协议框架而设计的，可以实现移动模型、各种算法及应用协议的仿真。本文采用ONE仿真平台进行实验。

仿真模拟场景采用ONE中默认场景，模拟区域大小为4500m×3400m，由126个节点组成。节点共分为3组，根据3组节点的特点不同分别进行设置。第1组为行人步行节点，速度为0.5～1.5m/s，节点80个；第2组为汽车行驶节点，速度为2.7～13.9m/s，节点40个；第3组为有轨电车行驶节点，速度为7～10m/s，节点6个。参数C的最大值H、最小值L分别取值1.1，0.8。默认仿真参数如表1所示。

以上实验表明，无论是在节点缓存不同或是仿真时间不同的情况下，针对不同算法，DARP主动拥塞控制算法对DTN的消息递交率、负载比率及消息丢失率各性能指标都有所改善。这说明本文提出的DARP算法对网络资源合理地进行了分配，起到了良好的拥塞控制作用，在主动避免拥塞发生的同时也提高了网络的传输效率，且适用范围较广。

4结语

本文在概率策略路由PROPHET算法的基础上，通过参考概率这一概念提出了DARP主动拥塞控制算法，重新定义了数据的转发策略，对DTN中的资源合理分配。本文算法在不同DTN传输的条件下，均能通过控制转发条件合理地对网络资源进行分配，且保持稳定，有效地实现节点拥塞控制。在网络资源空闲时，DARP算法对资源充分利用，提升节点缓存的利用率及网络对消息的传输性能；在网络资源不足时，合理利用有限资源，减缓节点的拥塞程度，进而实现整个网络的拥塞控制。实验结果表明，在不同条件下，DARP算法在递交率、负载比率及消息丢失率3个重要性能指标上都表现出良好性能，总体增强了DTN的综合传输性能。下一步将继续研究针对其他路由算法的主动拥塞控制方法。

参考文献：

[1]FALL K. A delaytolerant network architecture for challenged Internets [C]// Proceedings of the 2003 Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications. New York： ACM Press， 2003： 27-34.

[2]FAN X， WANG M. Delaytolerant network routing algorithm based on energy restriction and history information [J]. Transactions of Beijing Institute of Technology， 2009， 29（4）： 332-335.（樊秀梅，王明媚.基于能量约束和历史信息的容迟网络路由算法[J].北京理工大学学报，2009，29（4）：332-335.）

[3]SU J， HU Q， ZHAO B， et al. Routing techniques on delay/disruption tolerant networks [J]. Journal of Software， 2010， 21（1）： 119-132.（苏金树，胡乔林，赵宝康，等.容延容断网络路由技术[J].软件学报，2010，21（1）：119-132.）

[4]ZHANG X L， NEGLIA G， KUROSE J， et al. Performance modeling of epidemic routing [J]. The International Journal of Computer and Telecommunications Networking， 2007， 51（10）： 2867-2891.

[5]KRIFA A， BARAKA C， SPYROPOULOS T. Optimal buffer management policies for delay tolerant networks [C]// SECON08： Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor， Mesh and Ad Hoc Communications and Networks. Washington， DC： IEEE Computer Society， 2008： 260-268.

[6]LINDGREN A， PHANSE K S. Evaluation of queuing policies and forwarding strategies for routing in intermittently connected networks [C]// Proceedings of the First International Conference on Communication System Software and Middleware. Washington， DC： IEEE Computer Society， 2006： 1-10.

[7]WANG G， XU Z， LI X. Congestion control strategy based on quality of message in DTN [J]. Computer Engineering and Applications， 2012， 48（9）： 74-77.（王贵竹，徐正欢，李晓峰.DTN中依据报文质量的拥塞控制策略[J].计算机工程与应用，2012，48（9）：74-77.）

[8]LIU Q， PAN Y， LI Y， et al. Congestion control strategy based on copy rate in DTN [J]. Journal of Beijing University of Posts and Telecommunications， 2010， 33（4）： 88-92.（刘期烈，潘英俊，李云，等.延迟容忍网络中基于复制率的拥塞控制算法[J].北京邮电大学学报，2010，33（4）：88-92.）

[9]WANG C， SOHRABY K. SenTCP： a hopbyhop congestion control protocol for wireless sensor networks [C]// INFOCOM 2005： Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway， NJ： IEEE Press， 2005： 1003-1016.

[10]AKAN O B， AKYILDIZ I F. ESRT： eventtosink reliable transport in wireless sensor networks [J]. IEEE/ACM Transactions on Networking， 2005， 13（10）： 1003-1016.

[11]BURLEIGH S， JENNINGS E， SCHOOLCRAFF J. Autonomous congestion control for an interplanetary Internet [EB/OL]. [20130830]. http：//arc.aiaa.org/doi/pdf/10.2514/6.20065970.

[12]FAN X， SHAN Z， ZHANG B， et al. Stateofart of the architecture and techniques for delaytolerant networks [J]. Acta Electronica Sinica， 2008， 36（1）： 161-170.（樊秀梅，单志广，张宝贤，等.容迟网络体系结构及其关键技术研究[J].电子学报，2008，36（1）：161-170.）

[13]KARENOS K， KALOGERAKI V， KRISHNAMURTHY S V. Clusterbased congestion control for supporting multiple classes of traffic in sensor networks [J]. ACM Transactions on Sensor Networks， 2008， 4（1）： 107-114.

[14]IYER Y G， GANDHAM S， VENKATESAN S. STCP： a generic transport layer protocol for wireless sensor networks [C]// Proceedings of the 2005 IEEE International Conference on Computer Communications and Networks. Piscataway， NJ： IEEE Press， 2005： 449-454.