民航空地通信中的多链路数据分配算法*

余 翔,程士龙,段思睿,王子怡

(重庆邮电大学 通信与信息工程学院,重庆 400065)

0 引 言

通信技术促进着我国民航通信业的迅速发展,据中国民用航空局数据显示,民航市场逐年呈现增长趋势,增加的航空旅客通信业务对维护空地通信的完整性提出了更高的要求。在空地通信过程中不可能只提供一种空地通信服务链路,需要根据用户需求和当前的飞机所处环境自动选择通信链路。

当前民航通信架构主要有两种:一是空对地宽带通信(Air to Ground,ATG),通过地面基站与飞机上的ATG专用设备建立连接,组成ATG链路与地面进行信息交换,但是飞机却不能偏移基站的信号覆盖范围;二是宽带卫星通信,主要使用Ka/Ku频段,覆盖空域广,传输依靠卫星转发,通信距离远[1-2]。但飞机在高速移动状态空地通信链路资源有限,单一类型的空地带宽链路已然不能解决上述问题。为了保证用户良好体验与通信服务质量,多路径传输协议(Multipath TCP,MPTCP)提供了一个不错的解决方案。与常规TCP相比,多路径传输协议是一种适用于异构无线网络和有线互联网的并发传输协议,为了提高用户的服务质量,在异构网络最新的研究中重点在资源的使用分配方面[3-5]。MPTCP能够利用冗余信道资源,可以将吞吐量、传输速率提高到所有链路的总和而未使用像TCP协议所要求的单个信道。与此同时,MPTCP与传统TCP协议向后兼容。

基于多路径网络流量分配方面一直是重要的研究领域[6-7]。现有分配策略[8-10]有基于数据包和基于流的负载分配策略,而每种策略都有自己的特性。Prabhavat等人[11]提出了有效延迟控制负载分配的策略,即最小化在接收端数据重新排序时间以及在传输过程中每条链路的延迟差异,从而减少传输时延。现在研究较多的多路径TCP协议就是以数据流形式在多链路上将流量有效地分配。总之,基于数据包的模型虽然可以减少端到端的延迟,但是无法维持数据包的顺序,这依然为一个严重的问题;基于单个流的模型通常将单个流的数据包分发到相同路径上,很少切换路径,这有助于将数据包重新排序,代价就是巨大的端到端延迟。

本文考虑到民航空地通信中丢包率高、时延大、多链路流量拥塞等特性,提出了多链路数据均衡分配算法。该算法重新估量了在数据传输过程中的有效损失率问题,通过渐进近似的方法,动态调整数据流的分割比率大小,解决了链路拥塞、数据损失率高以及传输时延大等问题。

1 系统模型及公式

为了解决在民航空地通信中较低吞吐量和数据有效丢失等问题,本文提出了MPTCP系统模型的解决方案,如图1所示。本文研究了MPTCP的多条链路端到端通信问题,提出的多链路数据均衡分配方案旨在通过约束端到端数据流的分割比率,把数据流分配给状态良好的链路。数据在本地服务器端被划分为多个子流,每个子流进一步再被划分为多个数据包并缓存在发送区中。在系统模型中,对于数据流分割以及链路选择问题主要在本地服务器端实现,对于接收到的数据重组以及丢包率和带宽等参数的反馈主要由接收端负责。

图1 子流分配系统模型

本文考虑的是空地通信异构覆盖网络,通过配置多个通信链路连接服务器端并将目的地址与源地址进行绑定来实现空地多链路通信。由于通信的多条链路是并行且互不影响的,因此,每条通信链路的有效损失率Πi、可用带宽μi和往返时延TRT等链路参数是互不影响的[12-13]。

首先,假设在发送端需要发送总的数据流大小为s,每条链路上被划分的子流大小为

si=s·φi,i∈(1,2,3,…,p)。

(1)

(2)

(3)

在民航空地通信的过程中,因为通信系统是时变的,则使用状态转移概率对P(φi)进行估计。基于连续时间马尔科夫链的瞬间特性,可以得到链路i的状态转移方程为

(4)

(5)

(6)

由公式(4)～(6)得,在链路i中第k个数据包的状态为B时的概率表示为

(7)

(8)

在民航空地通信的过程中,由于高速的移动性和较长距离地传输会造成数据包传输的逾期问题。文献[16]提出用M/G/1排队时延模型近似逾期损失,而逾期丢包率与端到端数据包传输延迟有关,因此,单条链路上端到端延迟遵循指数分布[17],逾期损失率表示为

(9)

式中:E(·)为期望值;T表示约束逾期时间;E(Di)的值由大量延迟统计数据得到的值。因此文献[17]提出使用一个分数函数来近似子流分配的延时模型:

(10)

(11)

综上,有效损失率可表示为

(12)

最终,正如文献[18]所述,为了消除民航中空地通信之间较大的延迟差异以及拥塞带来的吞吐量问题,本文将多链路P上的数据流分配问题转化成为一个使最大丢失率链路缩小化,在每一次链路更新时总会选出丢失率最高的链路,通过约束条件计算出合理的矢量分割率,基于渐进近似的方法推导其解,得到每条链路的动态数据流分割表达式。

(13)

2 多链路数据流负载均衡分配算法

本文基于实用理论的流量分配方案,把最高有效丢失率链路通过渐进近似的方法最小化[19]。由于在民航空地通信的过程中,不同链路需要接入不同的数据链路网络,飞机高速的移动性伴随而来的也是较高的数据丢失,并且通信网络中也伴随有流量拥塞的问题出现。为了解决出现的问题,引入渐进近似的方法。在所有的链路中,通过将多链路中丢失率最高的链路与丢失率最低的链路逐渐通过控制分割率调整子流分配的大小,使得每条链路的丢失率尽可能近似相同,从整体上拥塞链路负载均衡。

本文引入流量分割率φi参数,作为为每条链路分割数据流大小的参照。在初始时,假设流量分割比率是根据带宽计算的,表示为

(14)

(15)

2)在所有链路中,选择有效损失率最大的Πiworst,1≤iworst≤p,再选择有效损失率最小的Πibest,1≤ibest≤p。

3)通过计算Δφ,使Πiworst和Πibest的端到端有效损失率相等:

Πiworst(φiwosrt-Δφ)=Πibest(φibest+Δφ)。

(16)

每次分割率变化量Δφ可以求得

(17)

式中:μi·(1-πi)表示为当前链路i的无损带宽。

4)为了避免路径iworst上的分割率和路径Πiworst上的过载为负值,所以Δφ必须由

Δφ←min(φiwosrt,Δφ)。

(18)

(19)

Δm-1。

(20)

通过以上的目标函数,可以得到

(21)

可以估计链路有效增量

(22)

由上式可知,通过确定子流分割率分割数据流的目的是最小化不同链路上的损失率的差值来解决数据拥塞的问题。

丢包感知负载均衡分配算法伪代码如下:

1 输入:{μi,ξi}i∈P,D=max(Di),T

2 输出:Si={S*φi}i∈P

3 foreachi∈Pdo

4 初始化Si,TRTi,E(Di),φi

5 while(Si≤μi·(1-πi))&&(E(Di)≤D)&&(Δφ!=0) do

6φi=φi+Δφ//计算数据流S的分割比率

7Si←S*φi

8 更新各个参数TRTi,D=E(Di),φi

9 end

10 重设上述参数Si,TRTi,E(Di)

11 while(Si≤μi(1-πi)) &&(E(Di)≤D)&&(Δ!=0) do

12φi=φi-Δφ//计算数据流S的分割比率

13 更新各个参数TRTi,D=E(Di),φi

14 end

15 确定子流的分配向量

16 end

17 特定的路径间分配

18 找到另一条可用的路径P

19 if(Sp′≤μp′(1-πp′))&&(E(Dp′)≤D)(Δφ!=0) do

20φi=φi+Δφorφi=φi-Δφ

21 end

22 end

因为初始φi被设置成单条链路带宽与多条链路带宽总和的比值,并不是从源点开始计算,当计算一轮后,可能导致计算出分配的分割比率变化量过高问题。为了解决这个问题,在算法中采用了取最小变化量的方式,最终得到按照分割比率分割子流的结果。

3 仿真与分析

本节基于Exata搭建了一个仿真系统架构实验平台,在一台运行Windows10的PC机上进行仿真,如图2所示。通过把Sender端和Receiver端映射到网络里的计算机中,将要发送的数据分配给不同的链路,并添加了多条通信链路。通过将源节点和目标节点都配备多个网络接口,它们之间有不相交的路径,总的带宽可由每条链路带宽聚合而成,并将每条链路的传播时延设置不同的值,如表1所示。

图2 仿真系统架构

表1 多链路通信参数

首先,本文设置了当通信链路仅有两条时,给予需要传输数据流大小分别为7.75 Mb、6.5 Mb、5.25 Mb和4 Mb,并统计了在各个分配算法下的数据重传情况,结果如图3所示。由图中比较可以得出,所提算法在数据重传方面低于其他几种算法。本文是基于有效丢失率进行的选择链路分配,很大程度上减少了数据的损失,避免了数据的重传,所以在数据重传上低于其他算法重传的数量。由于MPTCP对于TCP是友好的,因此在引入基于数据有效损失率作为考虑数据分割的一个标准后,数据重传数量得到了明显的降低。

图3 数据包重传数量

其次,数据从发送端到接收端接收重组数据的平均时延如图4所示,图中展示了所提算法和其他算法时延变化趋势的对比,可见所提数据分配算法性能随着传输的链路的增加而增加。这是由于所提算法更加准确地计算出每条链路的数据丢失率,给链路状态较好的分配较大的子流,给链路状态较差的分配较小的子流,以缓解链路的拥塞问题和有效丢失率问题,并降低了数据在端到端传输过程中连续丢失而导致在接收端产生的重组消耗时间。图5给出了平均丢包损失率随着链路个数的变化趋势。

图4 平均端到端时延

图5 平均丢包率

最后,图6展示了所提算法在丢包率上实时变化情况并与其他算法进行了对比。从图中可以看出,所提算法从整体上看实时丢包率变化表现得更为良好,更趋于平稳和越来越收敛,说明了所提算法的有效性。另外,如表2所示,虽然所提算法PL-ALB在实时丢失率以及时延等方面表现较好,但是在算法时间复杂度上并不是最佳的。这是因为所提算法需要对每条链路进行参数更新,所以产生了大量的运算时间。随着链路个数的增加,算法复杂度也会逐渐增加,这也是本算法需要进行提高和优化的方面。

图6 实时丢包率

表2 算法时间复杂度比较

4 结束语

本文提出了一种丢包感知负载均衡数据分配算法,通过计算每条链路的有效损失率情况,找出最佳和最差链路,求出合适的分割比率,通过循序渐进的方式不断地调整分割比率,最终达到每条链路的有效损失率尽量趋于相同。仿真结果表明,本文所提算法增加了传输的吞吐量,减少了在传输过程中数据丢失的比率和数据重传个数。在未来的工作中,将继续改进拥塞控制和不同路径的能耗问题。