空间通信中的一种滑动窗口BATS码传输方案研究

2019-08-29刘晓东卓永宁吕梦昭

载人航天 2019年4期

曾柯,刘晓东,卓永宁*,吕梦昭,王思

(1.电子科技大学通信抗干扰技术重点实验室,成都611731；2.空军装备部,北京100032；3.上海航天技术研究院北京研发中心,北京100048)

1 引言

在人类空间探索中,空间通信数据传输业务对传输的可靠性和时效性有很高的要求,例如在载人航天、卫星对地探测、航天器着陆和对接等任务中,舱室监控视频、航天员身体状态、科学探测数据、控制指令等数据可靠和及时的传输必须得到保证,而空间环境下传输链路的长时延、高误码率、低带宽、多级中继使得传统上依靠反馈确认实现的可靠传输性能大为降低,传输及时性也由于多级中继受到很大限制,需要在编码和通信协议上提出新的方案。

BATS码(分批稀疏码,Batched Sparse Code,BATS)[1-2]是近几年提出的一种结合了喷泉码和网络编码优点的新型编码技术,既有喷泉码无需反馈、适合单向长延时信道的特点,又有网络编码的优点,能够在中继节点进行直接编码,特别适合空间(深空)通信中长延时、多中继、高丢包率的链路特点[2]。与之相比,喷泉码在中继节点上进行译码后再重新编码,或中继节点直接转发,同时在源节点上采用更多的编码冗余以抵抗多级链路的累积丢包,这些都会降低编码效率,增大处理和传输延时。已进行的地面视频传输实验证明,多级链路中的有限长BATS码比有限长喷泉码有更好的传输流畅性、可靠性[2-3]。

BATS码虽然在多中继环境表现出一些优越的性能,但其研究和应用尚处于初级阶段,许多应用还主要针对地面高速数据传输[4-5],如何针对应用环境进一步优化尚未见深入的研究。另一方面,空间通信既要求较高可靠性,又要求较高传输时效性。已有针对无反馈可靠传输的研究[6-8],通常利用数据包的冗余传输保证可靠性,但实际上仍然无法保证数据的快速及时传输。基于此,本文提出一种BATS码的滑动窗口传输方案,相对于一般的窗口连续重叠滑动方式[7-9],利用BATS码中小度值Batch具有更高可解概率的特点,以多个小度值Batch对滑动窗口的非重叠区域进行编码传输,同时将滑动步长改为不等步长,实现对窗口滑动前后的重叠区域和非重叠区域数据的均衡保护,从而较好地解决空间通信中可靠传输与及时传输这一对矛盾,实现较高效率的传输。

2 BATS码基本原理

2.1 BATS码的编码方法

BATS码编解码中具有分批处理(Batch)的概念。假设待编码的数据包数量为K,集合B=(1,…,K)表示所有数据包的集合,将该集合划分为n个子集(可有重叠),子集Bi⊂B,i=1,…,n。每一个集合Bi经编码后得到M个编码数据包,称为一个分批(Batch)。编码后得到的n个Batch表示为X1,X2,…,Xn, 每个 Batch 可表示为式(1)[1]：

其中,令di=|Bi|,即Bi中包含di个原始数据包,称di是BatchXi的度。di(i=1,…,n) 是独立同分布的随机变量,称其分布Ψ=(Ψ1,…,Ψk)为度分布(Degree distribution),即Pr{di=k}=Ψk。Gi是di×M的随机矩阵,称为生成矩阵。理论上,编码后的Batch数目n可以是无限的。BATS码的编码和传输过程如图1所示,生成矩阵Gi处的虚框表示生成的Batch,虚框内的实心方块表示每个Batch内的M个编码数据包。

图1 BATS码的编码和传输过程示意图Fig.1 The encoding and transmission process of BATS code

传输数据包时,由于存在丢包现象,每个Batch到达中间节点的数据包数量可能少于M。中间节点对属于同一Batch的数据包使用网络编码(文献[1]中使用线性随机网络编码),重新产生M个数据包,并转发给下一节点。到达接收端的第i个Batch可表示为式(2)。

式中,Hi是一个M行的随机矩阵,称为传输矩阵。Hi的列数等于第i个Batch到达接收端的数据包的数量。对于不同的分组,该值不一定相同,但一定小于等于M。

2.2 BATS码的解码方法

BATS码常用的解码方法是置信传输(Belief Propagation,BP)解码。经过编码和传输之后,接收端收到的信息是BatchYi(i=1,…,n),数据包头信息中包含的传输矩阵H,以及通过收发端协商得到的生成矩阵G。于是,解码器可使用的解码信息是 (Yi,GiHi)(i=1,…,n),解码即相当于求解线性方程组。对于一个 Batch,当秩 rank(GH)等于这个Batch包含的原始数据包数目(即Batch的度)时,该Batch可解,对应的原始数据包称为可解的数据包。显然,当一个Batch中包含的原始信息包的数量较少时,传输中的丢包对其影响较小,该Batch有更高的可解概率。

BP解码包含多次迭代,每次迭代时,选择一个可解数据包,将其带入与之关联且不可解的Batch中。带入后,该数据包被标记已解,此时不可解的Batch可能会变得可解,然后进入下一次迭代。当没有任何可解的数据包时,解码结束。

当BP解码无法进行下去时,还可通过高斯消去法对剩余的Batch进行解码,即BP-GE算法[4]。

2.3 传输性能与Batch度分布的设计

实际应用中,源信息包和BATS编码包数量有限,因此是有限长BATS码。我们希望传输尽量少的编码包就能完全恢复原始信息包。与喷泉码类似,有限长BATS码是否可译以及其传输效率与Batch的度分布有很大关系。由于Batch在传输中出现随机的丢包,对应到传输矩阵H中是随机的列矢量丢失,而BATS码是否可译取决于矩阵GH的秩,因此好的度分布需要基于传输矩阵H的秩的分布情况进行设计。令：

称矢量h=[h1,h2,…,hM]为H的秩分布。秩分布反应出数据包从源节点到目的节点之间链路的随机丢包情况。

发送端Batch度分布在设计时,直接获取适应信道丢包情况的最优Batch度分布是一个较为困难的问题。文献[1]、[4]证明,最优度分布可通过渐进优化的方法来得到。首先通过求解一个有限长BATS码的可达编码率的线性最优化问题,来获得一个初始的度分布：

式(4)中可达编码率θ=K/n,为优化的目标函数,n为Batch的数量。Ψ为Batch的度分布,D是最大度值,x是取值在[0,1]间的离散参数。函数Ω(x,Ψ,h)由下式给定：

由式(5)获得的初始度分布基础上,通过迭代贪心算法[4],获得性能更好的度分布值,贪心算法的具体步骤为：

1)找到一个初始度分布Ψ(0)；

2)找到一个或多个可能好于初始度分布的新度分布Ψ(1)；

3)计算译码失败概率,选择性能最好的度分布,并重复步骤2、3。

文献[4]中寻找新的度分布使用下述扰动方法：

其中δ是一个很小的实数值,ed-1是一个某一元素为1、其他元素为0的d维矢量。

3 滑动窗口BATS码传输方案

3.1 传统滑动窗口传输方案分析

滑动窗口是一种在流媒体传输中用于提高传输可靠性的方法,在喷泉码、RS纠删码(Reed Solomon,RS码)传输中获得了广泛的研究[7-9]。其基本方法如图2所示。

将需要传输的数据分为长度为L的分段,称为一个窗口。对窗口W1内的数据进行编码传输,然后将窗口的起点向后移动S个符号,称为滑动S步长,然后将该起点以后的新窗口W2内的L个符号进行编码传输。图2中的P为前后两个窗口的重叠部分。

图2 基本滑动窗口传输Fig.2 The basic sliding window transmission

上述窗口滑动方法是一种重叠滑动,以数据的冗余传输实现对窗口滑动前后重叠部分的增强保护,这部分数据的传输可靠性高于不重叠部分。如果窗口连续滑动,则将出现更多的数据重叠,其中对不同重叠程度的数据保护程度也不同。例如当滑动步长S小于重叠部分P的长度时,如果连续重叠滑动,则可能出现部分数据有三重重叠,导致部分数据被过度保护,而其他部分保护的程度较低或没有保护,如图3所示。如果对所有数据连续采用这种方式进行滑动,将会导致较多的不必要数据冗余,同时也会造成窗口滑动太慢,数据传输耗时过长。

图3 窗口连续滑动造成的不同重叠区域P2：二重重叠,P3：三重重叠Fig.3 The overlapping field of a data section caused by consecutive sliding window transmission P2： Double overlapped part P3：Triple overlapped part

3.2 均衡保护的滑动窗口BATS码传输方案

BATS码是将数据分批编码,有限长BATS码的编码长度固定,不同分批的BATS码可以进行联合译码。根据前面BATS码编译码过程分析,可知BATS码中度值较小的Batch具有更高的可解概率。基于此特点,可以实现一种均衡保护滑动窗口传输中重叠与非重叠数据的传输方案。流程如下：

1)发送方首先根据链路情况得到秩分布,并根据秩分布得到一个期望秩rankexpt,设定每个Batch的尺寸M大于rankexpt；

2)发送方建立一个长度为L的发送窗口,根据窗口长度及秩分布,通过求解式(1)中的渐进优化问题得到Batch的度分布、编码率和每个窗口需发送的编码包数量；

3)每次发送时,根据Batch度分布随机选取一个度值Degree。如果Degree的数值小于rankexpt,则在窗口未重叠区域中顺序选择Degree个数据,进行Batch编码并发送；如果Degree值大于rankexpt,则在当前整个窗口中随机选择Degree个数据形成Batch编码并发送。当本窗口中所有编码数据包数量达到第2步中确定的编码包数量时,本窗口中的数据停止发送；

4)将窗口进行滑动：当本窗口数据发送完毕后,如果本窗口还未与其他窗口发生重叠,则只顺序滑动所有小度值Batch的度值之和的长度；如果本窗口与前一窗口已发生重叠(即是一个已经滑动的窗口),则前移一个完整的窗口长度,从本窗口结束位置后重新选择L个新数据作为新的窗口,开始第3、4步的发送流程,直至数据发送完毕。

上述数据发送过程见图4。图中第一个窗口为W1,该窗口中的数据发送时,如果随机选择的度值小于rankexpt,则顺序选择窗口中前面的Degree个数据进行编码发送,如果超过或等于rankexpt,则在整个窗口内随机选择Degree个数据进行编码发送,这一过程重复直到所发送的编码数据包数量达到第2步确定的编码包数量；随后窗口滑动所有小度值之和的步长S1,成为窗口W2。在W2中的数据发送时,当选择的度值小于rankexpt值时,从W2与W1重叠的部分P1之后的数据中顺序选择Degree个数进行编码发送；当选择的Degree值大于rankexpt时,则在整个W2窗口中随机选择数据进行编码发送,直到整个W2中的编码数据包数量达到要求。然后,选择新的数据形成新窗口W3,重复上述过程。上述过程中,两个窗口重叠的部分P1、P3得到冗余发送的保护,增大了译码成功的概率；未被重叠窗口覆盖的数据S1、S2、S3、S4,由于采用小度值进行编码,也具有较高的译码成功概率,因此,所有编码数据都得到了较高的译码成功率,从而提高了数据传输的可靠性。

图4 均衡保护的滑动窗口传输方式Fig.4 Sliding window transmission with balanced protection mode

3.3 Batch度分布优化算法

分析上述策略,数据包的发送效率和发送速度取决于整体Batch度分布。假设数据包总数为1024,窗口长度wnd_len为256,通信链路为互相独立的多跳链路,链路长度为2,每一跳的丢包率p为0.2,取M=16,链路拓扑如图5所示。

通过2项式分布拟合,得到的秩分布如图6所示。其中秩期望值rankexpt的值为12.87。基于上述秩分布,通过求解前述式(4)关于编码率的优化问题得到的度分布如图7所示。

根据上述策略,每次选取的度值小于rankexpt的概率较小,最后将会导致窗口移动速率过慢。这种情况可能在优化问题式(4)的求解中经常出现。因此,本文提出一种基于贪心算法的窗口滑动度分布生成算法,用以提高小度值的选择概率。算法描述如下：

图5 中继链路拓扑Fig.5 The topology of multi-relay transmission

图6 矩阵GH的秩分布Fig.6 The rank distribution of GH

图7 求解(4)式优化问题得到的BATS码分批Batch的度分布Fig.7 The distribution of Batch degree obtained by solving the optimization problem of formula(4)

loop_times//定义迭代次数adjust_value//定义每次调整的度分布值fori=1：loop_times//循环loop_times次计算给定度下的译码失败概率；

If本次译码失败概率在可接受范围内随机从度分布中挑一个大于rankexpt的度数减去adjust_value；

再随机从度分布中挑一个小于rankexpt的度数加上adjust_value；

else

break；

end if

end for

通过这种方式生成的滑窗度分布见图8。由图8可见,小度值(小于12)的概率大大提高了,这将有利于提高数据整体的发送速度,提高数据发送效率。

图8 经过调整的适于滑动传输的BATS码分批Batch的度分布Fig.8 Adjusted distribution of Batch degree suitable for sliding window transmission

4 仿真分析

仿真具体场景为三点两跳链路,每一跳的丢包率p在效率仿真中设为0.2,在可靠性仿真中设为可变,源数据包总数为1024,链路无反馈。为了比较有无滑窗和不同滑窗方式的传输性能,对比以下4种策略：

1)编码方式采用经典喷泉码,即LT码(Luby Transform,LT码),采用有限码长,译码方式为高斯消元GE译码算法,对原始数据顺序分段编码发送(即分段之间无重叠),分段长度256,每分段编码包长度480。本策略模拟无滑窗的LT喷泉码传输；

2)编码方式为BATS码,译码方式采用BP译码算法,有限域大小为Fq=256,采用对原始数据顺序分段编码发送,分段之间无重叠,Batch尺寸为M=16,分段长度为256,每分段编码包长度为480,其Batch度分布为图7所示的度分布。本策略模拟无滑窗的BATS码传输；

3)编码方式为BATS码,译码方式采用BP译码算法,有限域大小为Fq=256,发送策略采用顺序重叠滑动方式(即图3中的发送方式),Batch尺寸为M=16,编码包的窗口长度为480。本策略模拟传统的连续重叠滑窗BATS码传输；

4)编码方式为BATS码,译码方式采用BP译码算法,有限域大小为Fq=256,发送策略采用本文提出的均衡滑动方式,Batch尺寸为M=16,每窗口中源码包数量为256,每窗口发送编码包数量480,采用图8所示的度分布。本策略模拟本文提出的均衡保护滑窗BATS码传输。

图9是数据成功恢复比例随发送数据包数量的变化情况。从图9可以看到,在成功恢复率方面,滑动窗口方式的成功恢复率均高于无滑窗方式。无滑窗方式时,当发送相同数量的数据包时,BATS码的成功恢复率高于LT码,当达到100%恢复率时,LT码约需发送2500个数据包,而BATS码需要发送约2300个数据包；采用滑动窗口的两种BATS码方式中,均衡保护滑窗的成功恢复率都高于连续滑窗的成功恢复率,且随着发送的数据包数量增多,这种优势越来越大。当数据包达到100%恢复率时,连续滑动BATS码方式约需传送1980个数据包,而均衡滑动BATS码约需发送1750个数据包。

图9 不同传输策略下的数据成功恢复比例Fig.9 The data recover rate of different transmission schemes

图10是实时发送效率的变化情况,此处实时发送效率定义为：实时发送效率=正确接收的数据比特数/发送编码比特数。从图10可以看到,无滑窗方式由于成功解码的过程大部分集中在分段的末尾,因此实时能力波动较大,且一直在一个较低的水平；连续重叠滑窗方式由于滑动窗口的特性,保证了数据的实时传输性能,将实时性能维持在一个平衡的状态,但其传输效率指标并不是很高；均衡保护滑窗方式相对无滑窗方式以及连续重叠滑窗方式来说,不仅结合了滑动窗口的特性保证了实时性能的稳定,同时利用双段窗的特性提升了数据传输效率,将实时传输效率一直维持在一个相对较高的水平,这说明本文的发送策略有较高的效率,从而也具有较高的时效性。从图10也可以看到,在稳定状态下,均衡保护滑窗方式的效率约为60%,相对于连续重叠滑窗方式的约50%,提高了约20%。

图10 不同滑动方式下的实时发送效率Fig.10 The real time transmission efficiency of different sliding window modes

图11是在不同的信道丢包率下,发送固定数据包数量情况下的数据恢复成功率。图中发送的编码数据包数量固定为2700。从图11可见,不同传输方案在不同丢包率情况下的成功恢复率也不同,该指标可反映各方案的传输可靠性。图中当链路丢包率低于0.3时,各传输方案都可以成功恢复数据,但当丢包率达到0.4以上时,无滑窗方式的成功恢复率很快下降至0,而滑窗方式还可以维持在较高水平。其中连续滑窗方式的成功恢复率水平略高于均衡保护方式,这表明均衡保护滑窗方式的可靠性虽低于连续重叠滑窗方式,但仍然维持在较高的水平,可适用于最大丢包率达到0.4的情况。