一种适用于卫星DTN网络的拥塞控制算法

李静森

(太原学院,山西 太原 030032)

随着航天事业的持续高速发展,卫星网络受到越来越多的重视,因卫星网络通信具有不同于地面有线网络的特点,如通信时延大、链路误码率高、间断连接等特点和DTN网络非常相似,因此卫星网络可以看成一种典型的DTN网络[1],可以使用DTN的一些协议和机制解决卫星网络中的问题,但由于卫星节点的资源有限,使用长期保存数据的方式会导致拥塞。一旦出现拥塞会导致卫星通信的时延变大、误码率增大。

卫星DTN网络即卫星延迟容忍网络中含有大量链路可预测以及运行轨迹具有固定性、周期性的卫星节点,这类节点的特性对解决卫星DTN网络的拥塞问题起了很重要的作用。

本文针对卫星DTN网络采用保管传输易引起节点拥塞和流量过载引起链路拥塞的问题,提出了一种区分链路拥塞和节点拥塞的控制算法DLNC(Distinguish Link and Node Congestion algorithm),该算法考虑到链路连通时间可预测的特性,根据节点空闲比判断链路是否流量过载,并通过连通图判断链路是否拥塞,根据信息、节点的因素判断节点是否发生拥塞;若拥塞则通过该概率图查找保管节点来缓解拥塞,该算法大大降低了丢包率,提高了数据投递率。

1 相关工作

对于DTN的拥塞控制,根据引起中断的原因不同可以分为链路拥塞、节点拥塞和区域级拥塞[2],对于区域级拥塞是一种局部拥塞现象,可以通过链路拥塞和节点拥塞的处理来避免区域级拥塞。

在链路拥塞方面,张国华等人提出了解决DTN在链路能力随时间变化以及链路间歇连接环境下的拥塞控制策略[3],并把拥塞归结为最优化的问题,在链路能力随时间变化方面采用的是凸优化方法,而在链路间歇方面使用的是动态规划以及博弈论方法以此来决定节点是否接收保管传输。针对卫星网络的链路拥塞问题,现已有较好的解决方案如TCP Westwood、Delayed ACK等。

在节点拥塞方面,Burleigh等人提出了一种基于利益模型的被动拥塞控制算法(ACC),该算法根据节点的剩余缓存、信息的优先级以及接收一个消息的风险和收益等本地信息决定是接收还是拒绝信息,并且该算法没有充分使用缓存空间,因此只适合于节点比较小的网络。R.Das在ACC和CM的基础上提出了一种新的使用于DTN的拥塞控制算法(CC),该算法根据信息的优先级、TTL等对节点中的信息进行排序,并通过计算头部拥塞(HLB)情况、节点等级以及丢失概率与设置的门限值的比较决定是接收还是拒绝新到的信息。而Ying an等人针对节点拥塞提出了一种新的拥塞控制算法MACRE[4],该算法根据节点的发送数据的速率和接收数据的速率之差与节点的剩余缓存时间之积的大小来决定是接收还是拒绝新到的数据,该算法通过控制节点发送速率和接收数据的速率来控制拥塞,使节点达到了一种平衡的状态,但该算法忽略了信息的大小、优先级等因素且不适应具有突发性的网络。

2 DLNC算法

卫星DTN网络是拓扑动态变化的网络,但每个卫星的运行轨迹是固定的。为了获取最大的报文投递率,要有针对性的发送信息,即在发送信息时要尽可能快地找到目的节点。

2.1 链路的拥塞控制算法

在卫星DTN网络中,由于卫星通信具有高动态的连接特征,对于在轨道上运行的卫星来说,相互之间的连接可能会因为网络拓扑的动态变化、障碍物的阻挡、大气流的阻碍以及地面站的切换等多种原因造成连接被周期性的中断。但也可能由于卫星通信过程中,某条链路上的负载流量过快引起的链路中断,即链路的拥塞。

定义卫星节点空闲比公式如下:

Lcon=1-U/L

(1)

空闲比是指节点中剩余缓存队列长度与最队列长度的比值。

在文献[5]中,王占伟等人提出在适合的卫星周期T内,通过STK软件,计算T时间内卫星各个节点的链路通断时间图,构建连通图。该连通图的每个元素格式如图1所示,每一个元素代表一条单向可用链路,发送节点表示连接的源节点,接收节点即连接的目的节点,由开始时间和结束时间可以计算出连接的持续时间。卫星DTN网络中的每个节点都含有与其他节点相连的节点的连通图。

发送节点接收节点开始时间结束时间

图1连通图时间图的元素格式图

在文献[6]的基础上,构建了本文仿真模型的连通图。表1是GEO卫星与其中一颗中轨卫星MEO2在2018-3-6到2018-3-7的24个小时内,相通的时间段。

表1 周期T内的连通时间表

根据以上过程,设计链路拥塞算法。算法首先获取节点中的信息的个数以及最多能容纳的信息的个数,得出链路的状况,若链路处于拥塞状态就进行拥塞处理操作,来缓解链路拥塞。算法描述见算法1。

算法1:链路拥塞的控制算法

Input

U:节点能容纳的最小数据的个数。

L:节点中已含有的数据包个数。

Output

Lcon:链路拥塞的程度。

Step:

1)根据式(1)得出当前链路拥塞程度Lcon,并设置拥塞的门限值λ;

2)if(Lcon≤λ) 说明链路流量过载,判断节点是否能通信;

3)if(不能通信)即链路中断,通过查询连通图判断此时该连接是否中断;

4)if(查询是中断)即该次中断是正常中断,由于节点到达了流量过载;

5)while(空闲比>λ) 转移节点中最大的信息到链路拥塞程度不大的邻节点;

6)end while;

7)else 即该中断是由链路拥塞引起的,不断检查节点缓存中剩余时间最短的信息,进行丢弃;

8)else(能通信)进行第5步操作;

9)else 说明链路处于正常状态,接收信息;

10)end else;

11)end if。

2.2 节点拥塞的控制算法

在卫星DTN网络中,由于卫星易中断、通信时延长等特征,造成卫星节点需要长时间保存收到的信息,这易引起节点拥塞。本文针对节点拥塞分为拥塞避免和拥塞控制两部分。

2.2.1拥塞避免处理过程

由于卫星通信的时延较长,若在通信过程中经过的跳数过多会增大时延,对于有N个节点的Ad Hoc网络,平均跳数约为InN,对于卫星DTN网络中,由于节点个数比较少,据此可设定节点跳数的最大门限值公式如(2):

Hmax=In(N)+1

(2)

在DTN网络中,HLB(即头部队列阻塞)是一种很常见的拥塞现象,严重影响了数据的传输速率、延迟和网络的公平性,因此应避免在卫星DTN网络中出现HLB现象。计算HLB的公式如下:

(3)

其中Sd表示与新到bundle的目的地址一致的信息大小之和,S表示节点缓存大小,并设置HLB的门限值为γ(取值0.35),防止节点发生HLB拥塞。

在卫星DTN网络中,可能由于发送速率与接收速率相差过大,易造成瓶颈拥塞丢失大量新到的数据包,针对该问题,本算法通过加权平均速率方式计算节点的发送速率和接收速率,而不是采用节点的瞬时速率,通过瞬时速率与平均速率得出加权速率,速率的计算公式如下:

Rnew=αRcurrent+(1-α)Rmena

(4)

其中Rcurrent表示节点的瞬时速率,Rmean表示节点在新信息到达时速率的平均值,α是影响速率的因素,0≤α<1,若α很接近于零,说明加权速率和平均速率相比变化不大；若α很接近于1,说明加权速率受到瞬时速率的影响很大,考虑到平均速率根据说服性,因此本算法设置α=0.45。

因该算法是在Epidemic Router路由策略下进行的,会产生大量的副本易造成网络拥塞,应该限制副本的数量为M。M的公式如下:

(5)

根据以上计算公式,设计拥塞避免算法,算法首先获取信息的跳数,并尽可能把新到的信息通过查询相邻的节点是否是目的节点的过程把信息尽快地发送出去。再根据HLB、发送速率和接收速率等决定是否接收数据。算法的描述见算法2。

算法2:拥塞避免算法

Input:

N:表示网络中的节点数;

新到的bundle;

Output:

避免拥塞;

Step:

1)根据公式(2)得出跳数的门限值Hmax,if(Hop>Hmax)拒收;

2)else if(新bundle的目的节点就是该节点) 接收;

3)else if(该节点的通信范围内没有目的节点)根据拥塞控制算法,决定拒绝还是接受该bundle;

4)else if(该节点的下一跳节点含有该bundle且是目的节点) 拒收并通知含有该bundle的其它节点删除该bundle;

5)else if(该节点的下一跳节点中含有该bundle的个数超过M时) 拒收;

6)else根据公式(3)计算出HBL值,if(HBL>λ)拒收;

7)else 根据公式(4)计算出Rout,Rin速率,if((Rout-Rin)*Rttl

8)else 拒收;

9)end else;

10)end if。

2.2.2拥塞控制过程

对于新到的数据包,要计算节点被占用缓存的程度,计算公式如下:

(6)

其中m表示信息的大小,fsize表示剩余缓存大小,Bsize是节点的缓存大小,并设定拥塞的门限值为β。

当节点发生拥塞时,该算法并不是直接丢弃过期的信息,而是把节点中权值小的信息转移到保管节点中,从此该保管节点全权管理该信息。权值的计算公式如下:

(7)

Hop表示节点中信息所经过的跳数,m表示信息的大小,fsize表示节点剩余缓存的大小,Rttl表示信息的剩余生存时间,Tttl表示信息的生存时间。

保管节点就是该节点的邻节点,关于该保管节点的选择,通过与连接图相同的方式,构建连接概率图,记为G,连接概率图中G的各个元素格式如图2所示,邻节点表示在源节点的通信范围内所有能够通信的节点,目的节点是消息的目的接单。连接概率代表目的节点与邻节点在周期T中持续时间之和与周期T的比较值,值越大表示在周期T中通信的时间越大,即相遇的概率越大。在每个节点上都定义了G,在选择邻节点时,就根据概率值的大小来选择要保存转移信息的节点,即保管节点。一旦保管节点接收了数据,该数据就有保管节点全权代为管理。通过连接概率图G,能够很好地反应节点的移动性。

邻节点目的节点连接概率

拥塞控制的算法描述如下:

算法3:拥塞控制算法

Input:

新到的bundle;

Output:

缓解拥塞;

Step:

1)根据公式(6)计算出节点拥塞程度,if(Ncon<β)接收;

2)else 根据公式(7)计算每个bundle的权值if(该bundle的权值<该节点中所有bundle权值)拒收;

3)else 把权值最小的信息转移到保管节点中;

4)end if。

3 仿真与性能评价

3.1 仿真平台与仿真环境

本文采用是ONE1.5仿真软件,这是一款专门为DTN网络所设计的软件,由于本软件不支持卫星网络,为了能很好地模拟卫星的运行,本文通过STK软件把卫星的运行轨迹导出,并把卫星运行轨迹中的经纬度转化为平面地图上的x和y轴数据，并在OpenJUMP中编辑、定义,真实显示卫星在二维图中的运行轨迹。

本文设计了一个三层卫星模型,仿真的模拟场景如图3所示,部分仿真参数配置如表2所示。该场景包括一个高轨卫星(GEO)、两颗中轨卫星(MEO1、MEO2)、三颗低轨卫星(LEO1、LEO2、LEO3)、三个位于喀什、北京、拉萨的地面站。卫星是发送数据的源节点,地面站是接收数据的目的节点。

图3 仿真模拟场景图

表2 部分仿真参数配置

3.2 结果分析

本文在传染路由(ER,Epidemic Routing)下,对DLNC、DO、CC和MACRE四种拥塞控制算法进行了仿真验证,分析了四种算法的数据投递率、丢包率、平均开销和平均时延。

3.2.1数据传输率与丢包率

图4是在相同的仿真时间下四种拥塞控制算法的报文投递率、丢包率的对比分析。由图4可知,DLNC算法的投递率、丢包率优于其他三种算法,由于ER会产生大量的副本易引起拥塞, 其中DO算法是丢弃过期的数据包,因卫星DTN网络中易中断、长时延会导致过期的数据包增加,使丢包率增加、投递率降低, MACRE根据数据的发送速率与接收速率决定接收还是丢弃数据包,因卫星网络的数据发送具有突发性,易造成大量数据包丢失,而CC算法虽提高了投递率,但其丢包率相比较大。

图4 报文投递率与丢包率的比较图

3.2.2网络开销

图5是在相同的仿真时间下四种拥塞控制算法的平均开销对比分析,由图5可知,DLNC算法的平均开销优于DO、CC两种算法,而差于MACRE算法,其中O算法中数据包经过了多次转发而成功到达目的节点的数据包很少,MACRE算法通过节点的转发速率与发送速率相比转发数据,尽量使发送速率与转发速率达到平横状态,因此大大降低了网络开销,DLNC算法虽考虑了发送速率与转发速率,但只是用于拥塞避免,没有使两者达到平衡状态。 因此与MACRE算法相比,网络开销较大。

图5 网络开销比较图

3.2.3平均时延

图6是在相同的仿真时间下四种拥塞控制算法的平均时延对比分析,DLNC算法考虑到了数据的重要性,不会直接丢弃过期的数据,因此会有大量数据等待,造成排队时延过大,增大了平均时延。

4 结束语

通过分析卫星DTN网络中发生拥塞的现象,把拥塞情况分为链路拥塞、节点拥塞。针对这两种拥塞,本文提出了一种区分链路拥塞与节点拥塞的控制算法DLNC。首先,该算法针对不同的拥塞情况,采取了不同的策略,并综合考虑了信息大小、TTL、HLB、跳数以及节点的缓存、发送速率与接收速率等因素来解决了拥塞问题;然后,在ONE仿真软件下,在ER路由策略环境下,通过该算法与已有的三种算法DO、CC、MACRE在报文投递率、丢包率、网络开销、平均时延四个方面的比较表明,DLNC更能很好地解决卫星DTN网络的拥塞问题,有更好的投递性能和丢包率性能。

图6 平均时延比较图