一种基于QoS的空间延迟/中断容忍网络拥塞控制方法

时文丰­ 高德云 周华春



一种基于QoS的空间延迟/中断容忍网络拥塞控制方法

时文丰­*高德云 周华春

(北京交通大学电子信息工程学院 北京 100044)

为缓解网络拥塞对空间延迟/中断容忍网络产生的影响，该文提出一种基于QoS的网络拥塞控制算法。该算法包括接触拥塞判断和基于QoS的数据转发两种机制，分别从接触剩余可用容量和节点剩余存储空间两方面对每一段接触的拥塞程度进行预测，将接触划分为不同的拥塞等级。在计算路由时，以整段路径中所包含接触的最高拥塞等级为该路径的拥塞等级，并根据该拥塞等级发送不同优先级的数据。实验表明，基于QoS的拥塞控制算法可以提高低优先级数据的传递率并在节点存储空间不足时降低最高优先级数据的传递时延。

空间延迟容忍网络；拥塞控制；路径拥塞等级；基于QoS的转发

1 引言

延迟容忍网络[1,2](Delay Tolerant Network, DTN)是为应对空间网络频繁的链路中断、较长的端到端时延、高信道误码率等问题而设计的网络协议。该协议将应用层数据分割成紧急(urgent)、标准(standard)、大块(bulk) 3种优先级的束(bundle)作为DTN协议的数据单元，并按此顺序依次发送。DTN协议使用存储转发的策略应对链路中断，当无端到端路径时需将束存储下来等待传输机会，而节点存储空间不足时将造成数据丢失，导致网络拥塞发生。

在空间环境中，节点的运动轨迹可以调度和预知，能够预先获得两个节点间的通信起始和终止时间、传输速率、节点间距离等信息。接触图路由[3,4]将两个节点间的链路信息作为一个“接触”，配置在“接触计划”里，并根据预先配置的接触信息，按照束的最早到达时间计算出合适的路由。

在资源受限的空间DTN中进行拥塞控制至关重要，但是目前关于空间DTN的研究主要集中在路由方面，针对空间网络拥塞控制路由算法的研究还不是很多，且主要单独以存储管理的方式进行[8,9]，处理方式包括根据自身或其他节点的剩余存储状况控制发包速率、转移数据以及选择下一跳节点等，并没有关注空间DTN节点轨迹及通信容量可预知的特点。文献[10]提出的CGR-ETO虽然通过考虑链路排队延时来提高精确性，当链路容量不足时优先转发高优先级数据，但是并没有考虑下一跳节点剩余存储空间小于接触容量的情况，当下一跳节点存储空间不足时将导致数据被丢弃。

根据以上分析，本文提出一种基于QoS的空间延迟容忍网络拥塞控制方法，同时考虑空间节点轨迹可预知的特点与节点的剩余存储空间状况，从接触的剩余可用容量和节点的剩余存储空间两方面设计拥塞控制算法，缓解拥塞对网络性能的影响。

2 基于QoS的拥塞控制算法

基于QoS的拥塞控制算法是一种拥塞避免算法，包括接触拥塞等级判断和基于QoS的数据转发两种机制。

2.1 接触拥塞判断机制

接触拥塞判断机制包括根据接触剩余可用容量做出的接触拥塞判断，根据节点剩余存储空间做出的接触拥塞判断和拥塞信息通告3部分，该机制的实现算法如表1，具体实现方法如下：

(1)以接触剩余可用容量为依据的拥塞判断：首先找出以本地节点为起点的所有接触，每隔1 s对每段接触分别进行判断。将新判断的拥塞等级与之前拥塞等级作对比，检查是否发生变化，如果发生变化则向拥塞通告域内的其他节点通告。

本文使用接触的剩余可用容量占接触剩余容量的比例(Contact Available Capacity Ratio, CACR)作为接触拥塞等级的判断依据：

当剩余可用容量占剩余接触容量的比例小于20%时认为接触发生轻度拥塞，当小于10%时为重度拥塞，当小于0.05%时为完全拥塞，留出0.05%的容量作为束重传、时间不同步等意外情况的开销。

(2)以节点剩余存储空间为依据的拥塞判断：首先从接触计划中找出所有以本地节点为终点的接触，检查节点剩余存储空间是否小于这些接触的剩余容量，如果小于则检测节点的剩余存储空间占衡量基准的比例RNCR(Residual Node Capacity Ratio)。RNCR按下式计算：

当节点剩余存储空间小于接触的剩余容量时，接触真实的可用容量应该以接触终止节点的剩余存储空间来计算，因为当无传输机会时，数据将存储在接触终止节点上，上限则为节点的剩余存储空间。

表1接触拥塞判断机制

接触拥塞等级判断算法： 1 每隔1 s执行以下操作： 2 对于接触计划中每一条接触记录 3 If 接触的起始节点是本地节点 4 If CACR<0.2 5 If CACR<0.1 6 If CACR<0.0005 7 判断接触拥塞等级为完全拥塞 8 Else判断接触拥塞等级为重度拥塞 9 Else 判断接触拥塞等级为轻度拥塞 10 Else 判断接触未发生拥塞 11 If 接触拥塞等级未发生变化 12 检测下一条接触记录 13 Else 生成该接触的拥塞通告，设置生存时间，计算通告域，随后检测下一条接触 14 Else if 接触的终止节点是本地节点 15 If 节点剩余存储空间小于接触剩余容量 16 If RNCR<0.2 17 If RNCR<0.1 18 If RNCR<0.0005 19 判断接触拥塞等级为完全拥塞 20 Else 判断接触拥塞等级为重度 21 Else 判断接触拥塞等级为轻度 22 Else 判断接触未发生拥塞 23 If接触拥塞等级未发生变化 24 检测下一条接触记录 25 Else生成该接触的拥塞通告，设置生存时间，计算通告域，随后检测下一条接触26 Else 检查下一条接触记录27 Else 检查下一条接触记录

当剩余存储空间占比RNCR小于20%时判断接触为轻度拥塞，当RNCR小于10%时判定为重度拥塞，当RNCR小于0.05%时判定为完全拥塞。

(3)拥塞信息通告：当判断到接触拥塞状态变化时，向其他节点发送拥塞信息，并将拥塞通告排入传输队列的首位，保证最高的发送优先级，如果未发现拥塞或拥塞等级未发生变化则不发送任何信息。拥塞通告信息包括接触的起始节点、终止节点、起始时间、终止时间、拥塞判断依据和拥塞等级。

因为有些节点用不到该发生拥塞的接触，如当该接触终止时还未开始使用的接触，这些接触的起始和终止节点将不会使用该接触，因此使用通告域限制通告信息的有用性，避免发往不需要的节点耗费卫星能量等资源。并且将拥塞通告信息的生存时间设置为接触终止时间与发送通告当前时刻的时间差，将生存时间之内无法到达的节点视为无效。通告域定义为{接触计划中满足开始时间小于拥塞接触终止时间的所有接触的开始节点和终止节点}。

2.2基于QoS的数据转发机制

该机制包括接触拥塞信息更新，路径拥塞程度计算和基于QoS的束转发3部分，其实现流程如表2算法所示。

当节点接收到拥塞通告信息时，根据通告信息中的起始节点、终止节点、起始时间、终止时间在接触计划中找到相应接触，更新该接触的拥塞等级。当节点为束计算路由时，首先根据CGR计算出最优路径，然后根据路径中所有接触的拥塞等级来决定该路径的拥塞等级，路径的拥塞程度由路径中接触的最高拥塞等级决定。

根据整条路径的拥塞程度来决定发送束的优先级：首先检查束的目的节点是否为下一跳节点，如果是则所有优先级的束都需要发送；当无拥塞时，发送所有优先级的数据；当路径轻度拥塞时允许前两个优先级的束发送，当重度拥塞时只允许最高优先级的束发送，当完全拥塞时检查接触拥塞判断依据，如果是接触剩余容量不足引起的拥塞则允许最高优先级的束发送，若判断依据为节点存储空间，则为所有束均选择次优路径发送。

表2基于QoS的束转发机制

基于QoS的束转发算法： 1当束到来 2 If 束为拥塞通告信息 3 If 拥塞判断依据为接触剩余容量不足 4 更新以剩余容量为依据的拥塞等级 5 Else 在接触计划中找到相应接触，更新该接触以节点剩余存储空间为依据的拥塞等级 6 Else 7 为束计算路由和路径的拥塞等级8 If 束目的节点是下一跳节点 9 转发该束10 Else if 路径无拥塞 11 转发该束 12 Else if 路径拥塞等级为轻度拥塞 13 If 束优先级为紧急或标准 14 转发该束 15 Else使用次优路径转发 16 Else if路径拥塞等级为重度拥塞 17 If 束优先级为紧急 18 转发该束 19 Else使用次优路径转发 20 Else if路径拥塞等级为完全拥塞 21 If路径拥塞等级判断依据为接触剩余容量不足&&束优先级为紧急 22 转发该束 23 Else 使用次优路径转发

3 性能分析

实验使用我们的基于分离映射机制的空天地一体化网络实验平台完成，拓扑如图1所示。节点1和节点2作为源卫星节点向移动节点MN发送数据，数据首先发送到网关6进行协议转换，星间链路延迟设置为100 ms，链路速率参考文献[11]中的无人机中继场景设置为2 Mbit/s。实验参照铱星系统使用STK[12]仿真了两颗LEO分别在节点稠密与稀疏情况下与地面网关间的接触图，我们将仿真结果简化为表3和表4所示，其中FN, TN分别表示起始、终止节点，FT, TT分别表示起始、终止时间。

空间网络使用NASA开发的DTN实现软件ION-3.3.1[13]，我们在软件中加入了基于QoS的拥塞控制算法实现模块，并在实验中与CGR-ETO[10]算法进行了比较，分别对比了接触剩余可用容量和节点剩余存储空间以及不同接触拥塞等级判断参数对传输性能的影响。使用束传递率反映网络丢包情况，使用束传递时延反映网络的传输效率。

3.1 接触剩余可用容量对传输性能的影响

因为在源节点发送数据时，卫星网络中也同时存在其他节点发送的数据，我们在网络中流量大小不同时分析接触剩余可用容量不足情况下拥塞控制算法的性能。

(1)不同网络流量下拥塞控制对传输性能的影响：实验接触图如表3所示，节点1和节点2每3 s向MN发送紧急、标准和大块优先级的束各一个，大小为200 kB，我们将节点3通往节点1和节点2的数据视为网络中流量，使用网络中流量占用链路带宽比例作为变量。

图 1 实验拓扑

图2所示为网络中流量占用链路带宽比对束传递率的影响曲线，图中urg-cc, std-cc, bulk-cc, avg-cc曲线分别代表使用拥塞控制算法时紧急、标准、大块束和平均的传递率曲线，urg, std, bulk, avg为无拥塞控制算法时(CGR-ETO)3种优先级束和平均的传递率曲线。从图2中可以看出当使用拥塞控制算法时，随着网络中流量占用链路带宽比的增加，平均传递率可以提高10%~25%，对大块束传递率最高可以提高近40%，对标准束最高可以提升20%。图3为不同网络中流量占用链路带宽比对传递时延的影响曲线，对比标准和大块曲线可以发现使用拥塞控制时传递时延增加，而无拥塞控制算法时，由于大量的大块和标准束丢失，发送的数据变少，传递时延反而小于使用拥塞控制算法的情况。

(2)拥塞判断参数对网络性能的影响：我们对轻度拥塞和重度拥塞判断参数的不同设置情况进行了分析。实验使用(1)中发包方式，网络中流量占用带宽比例设置为90%。

图5和图6分别为接触容量参数对束传递率和传递时延的影响图，可以看出轻度拥塞判断参数的增大带来大块束传递率的小幅提升，但是其传递时延也会增加。重度拥塞判断参数的增加同样会带来大块束传递率的提升，并使得标准束以及平均传递时延增加。我们使用平均传递时延作为性能指标，选择平均传递时延最小的一组参数作为拥塞控制算法的参数设置，即0.2/0.1，表示轻拥塞判断参数为0.2，重度拥塞判断参数为0.1。

通过以上对比分析得出，当接触剩余容量不足时，QoS拥塞控制算法可以提高大块和标准优先级束的传递率，但带来了时延上的增加。

3.2 节点剩余存储空间对传输性能的影响

实验使用表4所示接触图，模拟节点稀疏场景。该场景下发送节点没有到达目的节点的直接路径，数据必须暂时缓存在中间节点。实验使用3.1节中发包方式，束大小设置为100 kB，使用中间节点3的存储空间作为变量。

图4和图8分别为存储空间对传递率和传递时延的影响曲线，通过对比可以看出当无拥塞控制算法时，随着存储空间的减小，3种优先级束的传递率均发生大幅下降，而使用拥塞控制算法时可以极大提升传递率，3种束的传递率均接近1。同时基于QoS的拥塞控制可以降低紧急束的传递时延，且随着存储空间的减小，降低的趋势更加明显。但大块束的传递时延反而会增加，对标准束则无明显影响。

同样我们分析了节点存储空间不足情况下不同接触拥塞等级判断参数对传输性能的影响，我们将拥塞判断参数分别设置为图7中6种不同情况。

图7所示为存储空间参数对束传递时延的影响图，通过对比可以看出当重度拥塞判断参数不变时，轻度拥塞判断参数的增加带来大块束的传递时延和平均传递时延的增加，当轻度拥塞判断参数不变时，重度拥塞判断参数的变大将导致大块和标准束的传递时延以及平均传递时延增加。当选择参数0.2/0.1时，3种优先级束的平均传递时延最小，在拥塞控制算法中我们使用轻度拥塞判断参数为0.2，重度判断参数为0.1作为算法设计的标准。

通过以上对比可以得出，当节点剩余存储空间不足时，QoS拥塞控制算法不仅可以提高束的传递率，而且可以降低紧急束的传递时延。

表3稠密接触图参数

FN1122435 TN4335666 FT310113103101310 TT600300300600600300600

表4稀疏接触图参数

FN1122435 TN4335666 FT31011310610310610 TT600300300600900600900

图2网络中流量对传递率的影响     图3网络中流量对传递时延的影响     图4 存储空间对传递率的影响

图5 接触容量参数对传递率的影响    图6 接触容量参数对传递时延的影响    图7 存储空间参数对传递时延的影响

图8存储空间对传递时延的影响

4 结束语

本文利用空间网络节点轨迹可预知的特点，提出一种基于QoS的拥塞控制算法，从接触的剩余可用容量和节点的剩余存储空间两个方面对接触进行拥塞预测，通过路径中每段接触的拥塞预期得到整段路径的拥塞等级，并根据该等级决定路径中允许发送的束的优先级，实验表明当接触剩余可用容量不足引起网络拥塞时，基于QoS的拥塞控制算法可以提高大块和标准优先级束的传递率，当节点剩余存储空间不足时，可以提高束的传递率，并降低紧急束的传递时延。

[1] CERF V, BURLEIGH S, HOOKE A,Delay-tolerant networking architecture[S]. IETF RFC 4838, 2007.

[2] SCOTT K L and BURLEIGH S. Bundle protocol specification[S]. IETF RFC 5050, 2007.

[3] ARANITI G, BEZIRGIANNIDIS N, BIRRANE E,Contact graph routing in DTN space networks: overview, enhancements and performance[J].,2015, 53(3): 38-46.

[4] BURLEIGH S. Contact graph routing[S]. IETF Internet, draft-burleigh-dtnrg-cgr-00, 2010.

[5] BEZIRGIANNIDIS N, TSAPELI F, DIAMANTOPOULOS S,Towards flexibility and accuracy in space DTN Communications[C]. Proceedings of the 8th ACM MobiCom Workshop on Challenged Networks, Miami, Florida, USA, 2013: 43-48.

[6] FRAIRE J and FINOCHIETTO J M. Routing-aware fair contact plan design for predictable delay tolerant networks[J]., 2015, 25(Part B): 303-313.

[7] FRAIRE J and FINOCHIETTO J M. Design challenges in contact plans for disruption-tolerant satellite networks[J].,2015, 53(5): 163-169.

[8] SILVA A P, BURLEIGH S, HIRATA C M,. A survey on congestion control for delay and disruption tolerant networks[J]., 2015, 25(Part B): 480-494.

[9] RASHID S, AYUB Q, and ABDULLAH A H. Reactive weight based buffer management policy for DTN routing protocols[J]., 2015, 80(3): 993-1010.

[10] BEZIRGIANNIDIS N, CAINI C, and PADALINO M D D,. Contact graph routing enhancements for delay tolerant space communications[C]. Proceedings of IEEE 2014 7th Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications Workshop (ASMS/SPSC), New York, USA, 2014: 17-23.

[11] IVANCIC W D and SULLIVAN D V. Delivery of Unmanned Aerial Vehicle DATA[M]. USA, National Aeronautics and Space Administration, Glenn Research Center, 2011: 1-6.

[12] Satellite Tool Kit (STK)[OL]. http://www.agi.com/ products/stk/, 2016.

[13] Interplanetary Overlay Network (ION) [OL]. https:// sourceforge.net/projects/ion-dtn/, 2015.

QoS Based Congestion Control for Space Delay/Disruption Tolerant Networks

SHI Wenfeng GAO Deyun ZHOU Huachun

(,,100044,)

In order to alleviate the influence of network congestion in space delay/disruption tolerant networks, a QoS based congestion control algorithm is proposed in this paper. The algorithm consists of contact congestion forecasting scheme and QoS based data forwarding scheme. The contacts are divided into different congestion levels according to their residual available capacity and nodes’ storage resource. The congestion level of forwarding path calculated by routing is decided by the highest congestion level of contacts consisted in the path and different priority data will be forwarded according to the path congestion level. Experiment shows that QoS based algorithm could improve the transmission rate of data with lower priority and reduce the delivery delay of highest priority data when the node storage space is insufficient.

Space delay tolerant network; Congestion control; Path congestion level; QoS based forwarding

TP393

A

1009-5896(2016)11-2982-05

10.11999/JEIT160140

2016-01-29；改回日期：2016-07-04；

2016-09-08

时文丰 14111038@bjtu.edu.cn

国家863计划(2015AA015702)，国家自然科学基金 (61271202)，国家973计划(2013CB329101)

The National 863 Program of China (2015AA015702), The National Natural Science Foundation of China (61271202), The National 973 Program of China (2013CB329101)

时文丰： 男，1990生，博士生，研究方向为延迟容忍网络、空天地一体化网络.

高德云： 男，1973年生，教授，研究方向为传感器网络、车载网络.

周华春： 男，1965年生，教授，研究方向为未来网络、空天地一体化网络.