时变信道下线性网络分批稀疏码秩分布研究

王士恒，刘恒，唐林，苏金领，张瑞琦

（1. 西南交通大学信息编码与传输省重点实验室，四川 成都 611756；2. 现代交通通信与传感网络国家级国际联合研究中心，四川 成都 611756;3. 中国电子科技集团第三十研究所，四川 成都 610031）

0 引言

在无线网络中，从源节点到宿节点之间的直接链路往往是不可达的，因此多跳的通信方式变得十分重要。在多跳通信网络中，部分节点作为网络中间节点通过逐跳转发的方式将接收的数据包传输到宿节点。由于噪声、干扰或者信道失真等影响，在多跳网络中传输的数据包仍然可能以一定概率出现丢包的现象，此时可使用网络编码[1]处理丢包问题。

作为多跳网络中的一种新型信道编码方案，同时也是传统随机线性网络编码（random linear network coding, RLNC）[2]的加强型方案，分批稀疏（batched sparse，BATS）码是一种能够在丢包网络中改进网络性能的编码方案[3]。分批稀疏码提供了一个两段式编码框架，源节点处的外码（喷泉码的矩阵形式）在理论上可以生成无限数量的批次数据包（batch），而内码（采用线性网络编码）则在网络中间节点处对属于同一个批次的数据包进行再次编码。分批稀疏码适用于任何允许在中间节点上进行线性网络编码的网络。由于端到端的操作为线性编码，因此分批稀疏码对动态网络拓扑和丢包具有鲁棒性。此外，分批稀疏码可以在较小的有限域下运行，相比之下，现有的随机线性网络编码虽然可以使网络吞吐量达到网络容量[4-5]，但也需要较大的场大小去保证传输矩阵为满秩。分批稀疏码解决了基于块的方法的顺序调度的反馈问题：由于无速率的特性，批次的顺序调度不需要反馈。同时，分批稀疏码解决了基于喷泉码的方法的度分布问题，因为分批稀疏码的内码不会改变批次的度值[3]。

与传统的随机线性网络编码相比，分批稀疏码能够显著降低编码开销和译码复杂度[6]，同时由于不再需要为每个数据包发送ACK/NACK 反馈信息，分批稀疏码的无速率特性还能明显简化传输协议[7]。另外，分批稀疏码在网络中间节点仅需要进行有限域运算，因此BATS 码适用于网络中间节点存储空间有限、数据传输量巨大且对时延敏感的数据传输场景[6]。同时，对不同的5G应用场景[8]，如增强型移动宽带（enhanced mobile broadband，eMBB），结合丢包率、时延等性能指标要求以及节点处理能力，也可以有针对性地设计相应的分析稀疏码传输协议。

目前，国内外诸多学者在许多方面对BATS码进行了研究与优化。Yang 等[9]首先提出了一种简单的支持分批稀疏码的网络协议，称为BATS-Pro-0，该协议由上到下将信息传输的框架分为应用层、传输层、网络层、链路层和物理层，演示了如何使用分批稀疏码在网络中进行通信，并为后续的研究提供了一个最基本的协议。

由于秩分布决定了数据传输的最大可达速率，因此秩分布是在分析分批稀疏码性能时的一个十分重要的参数，目前已有相关文献研究了分批稀疏码在不同网络拓扑和结构下的秩分布。Yang 等[7]基于BATS-Pro-0 协议，研究分析了RLNC 重编码作为内码编码方案时分批稀疏码的归一化秩期望，并提出了一个批的秩在网络中的每个节点上形成一个马尔可夫链[7]，推导得到删除信道下RLNC 重编码的最大可达速率，即在批次数足够大的情况下，该速率会收敛到一个常数，该数值只随丢包率变化。之后Yang 等[7]对RLNC 重编码进行改进，提出系统重编码作为内码编码的方案并分析其秩分布。该方案在批次数足够大的情况下与RLNC 重编码的最大可达速率相同，但在批次数较小时有着更明显的优势。作为一种新的编码技术，其在计算开销和重编码时延上都要低于RLNC 重编码，同时在相同节点上的秩期望也更大，因此，以系统重编码作为分批稀疏码的内码会获得较RLNC 重编码更优的性能。同时根据线性重编码，Yin 等[10]提出了自适应重编码方案，Yang 等[7]提出了一个批在下一跳上的秩期望，Yue 等[6]在此基础上研究了两种能够应用于工业互联网上行链路的分布式分批稀疏码的秩期望。

网络编码可分为确定网络编码和随机网络编码。为了能够设计出高效的确定网络编码，通常需要获取信道状态的相关信息[11]。而随机线性网络编码达到较高的编码增益的代价是较高的编码开销[12]。为了降低编码开销，各种稀疏随机线性网络编码方案被提出[13-16]。

Sehat 等[17]分析了稀疏矩阵秩的概率分布，指出稀疏网络编码的提出正是为了解决牺牲通信负载而造成的巨大计算复杂度的问题。Li 等[18]也研究了稀疏随机线性网络编码传输矩阵非奇异的概率。此外，Li 等[19]分析了稀疏随机线性网络编码译码失败概率，将求解译码失败概率问题转换为随机传输矩阵秩分布问题，而该问题同样可以通过矩阵零模式来解决，得到秩分布的上限和下限，进而可以得到译码失败概率。

然而上述文献的研究都基于时不变信道，即假定各条链路上的丢包率均为常数。正如前文所述，分批稀疏码是一种多跳信道编码机制，该机制不仅能够应用在固定节点上，同样也适用于移动节点。而在节点移动的场景下，链路的丢包率将很难保持恒定不变。本文作者在文献[20]中提出了时变信道下的分批稀疏码传输模型，讨论了网络中间节点使用RLNC 重编码时，分批稀疏码在时变信道下的秩分布，在该信道下，各链路上的丢包率假定为随机变量而不是固定值。基于此，本文进一步对时变信道下分批稀疏码的秩分布展开研究，重点研究了链路丢包率服从有限区间正态分布时的秩分布且阶数k为任意值时，RLNC和系统重编码的归一化秩期望的通用闭合解。

1 分批稀疏码

1.1 外码编码

分批稀疏码是随机线性网络编码的加强型方案，该编码方案分为外部和内码两部分。外码在源节点处生成批Xi，一个包含M个已编码数据包的批通常利用K个输入数据包的子集生成，即：

其中，M列矩阵Gi是第i个批的生成矩阵，而Bi则是K个输入数据包的一个子集。令dgi表示第i个批的度，即批中原始数据包的个数。一般情况下，批的度为一个随机数，其服从的随机分布称为度分布，度分布是在设计分批稀疏码外码时的一个十分重要的参数。

1.2 内码编码

内码编码是指在网络中间节点将接收的属于同一个批的数据包进行重编码，将得到的编码数据包转发至下一节点。

分批稀疏码的内码通常采用随机线性网络编码的重编码方案，该方案有较大的计算开销和重编码时延。

文献[7]提出了基于系统重编码（systematic recoding）的内码方案。作为一种新的编码技术，系统重编码在计算开销和重编码时延上都要低于RLNC 重编码，同时在相同节点上的秩期望也更大，因此，以系统重编码作为分批稀疏码的内码会获得比RLNC 重编码更优的性能。在系统重编码的内码方案中，假设网络中间节点接收k*个属于同一个批的数据包，r是k*个数据包中线性无关数据包的数量。令M'表示系统重编码生成并转发至下一节点的数据包数量。系统重编码按照如下步骤进行。

步骤1 从接收的数据包中选择r个线性无关的数据包作为重编码数据包的一部分。

步骤2 从步骤1 选择的r个线性无关的数据包中使用随机线性网络编码生成 'M-r个编码数据包。

链路间的丢包率可建模为对角矩阵E，其中，对角线元素为0 的概率对应链路上的丢包率ε。中间节点的系统重编码矩阵为Φ，其中Φ的前r列构成一个单位矩阵，后 'M-r列中的元素在有限域内随机取值[3]。因此，第n个节点收到的数据包Y为：

2 时变信道下的归一化秩期望分析

2.1 时不变信道下的归一化秩分布

文献[7]讨论了在时不变信道下基于线性重编码的分批稀疏码的归一化秩分布。在一个长度为l的线性网络中，其中R0表示源节点，Rl表示宿节点。令πn,n= 0,1,… ,l表示一个批在第n个节点处的秩分布，其是一个含M+1 个元素的向量，且一个批在节点Rn,n= 0,1,… ,l处的秩形成一个马尔可夫链。假设P表示重编码时该马尔可夫链的概率转移矩阵，因为数据包在传输过程中，其转移矩阵H的秩不可能增大，所以P为下三角矩阵。若所有节点使用相同的重编码方案生成M个数据包发送至下一节点，则：

并有π0[M] = 1。因此要计算在第n个节点Rn处的秩分布πn，仅需要计算概率转移矩阵P。设宿节点lR接收r个数据包，则其归一化秩期望可表示为：

2.2 时变信道下的归一化秩分布

式（13）表明，若要计算节点nR的秩，需要结合具体的重编码方案与概率密度分布函数进行分析，因此，本文将基于不同的信道条件以及不同重编码方式对线性网络中的分批稀疏码秩分布进行分析。

2.3 有限区间正态分布

在时变信道中，链路上的丢包率总是分布在有限区间，因此本文假设ε服从有限区间正态分布，其概率密度分布函数fk(ε)为：

其中，k、a和μ分别表示有限区间正态分布的阶数、有限区间半区间长度和有限区间的均值。有限区间正态分布概率密度函数如图1 所示，可见不同阶数k所对应的曲线。

图1 有限区间正态分布概率密度函数

当有限区间正态分布的阶数为0 时，概率密度函数为：

2.4 时变信道下RLNC 重编码的归一化秩期望

文献[20]研究了有限区间正态分布阶数为0和1 时，RLNC 重编码在时变信道下的秩分布并推导了闭合解。本节将阶数从0 和1 推广到更具有一般性的自然数k，讨论任意阶数下RLNC 重编码在时变信道下的秩分布及其闭合解。

假设一个节点接收一个秩为i的批，且采用系统重编码作为内码编码方案生成M个编码数据包并发送到下一节点，对于0 ≤j≤i≤M,有：

式（20）和式（21）所示的结果与文献[20]中的一致。

2.5 时变信道下系统重编码的归一化秩期望

基于文献[20]所述的RLNC 重编码在时变信道下的秩分布研究思路，本节讨论采用系统重编码作为内码时，分批稀疏码在时变信道下的归一化秩期望，并推导求解出k在任意值下，归一化秩期望的闭合解。

当有限区间正态分布的阶数为0 时，将k=0代入式（30），有：

3 仿真结果与分析

本节基于蒙特卡洛仿真对以上结论的数值分析的结论进行验证，数值计算与仿真参数见表1。

表1 数值计算与仿真参数

图2～图5 分别是有限区间正态分布的阶数为0、1、2 和3 时基于系统重编码的分批稀疏码归一化秩期望仿真结果。可以看出，随着网络长度的增加，归一化秩期望逐渐减小，且数值分析结果与蒙特卡洛仿真结果完全吻合。此外，对比图2～图5 可以发现，当基域qm、批大小M和网络长度L相同时，有限区间正态分布阶数越大，系统重编码的归一化秩期望越大。如当qm=256、M= 32、L= 20 时，k= 3 对应的重编码方案具有更高的归一化秩期望。

图2 k = 0 时基于系统重编码的分批稀疏码归一化秩期望

图5 k = 3 时基于系统重编码的分批稀疏码归一化秩期望

为了比较时变信道下基于系统重编码与基于RLNC 重编码的归一化秩期望，图6～图9 给出了当有限区间正态分布阶数k= 0、1、2 和3 时基于RLNC 重编码的分批稀疏码归一化秩期望，其中数值计算的结果根据式（19）计算所得，其结果与蒙特卡洛仿真相吻合。此外，对比图2 与图6、图3与图7、图4 与图8、图5 与图9，可以发现当qm、M和L较小时，基于系统重编码的分批稀疏码比基于RLNC 重编码的分批稀疏码具有更好的归一化秩期望；当基域mq较大时，基于系统重编码的分批稀疏码与基于RLNC 重编码的分批稀疏码具有近乎一致的性能。因此，若基域mq较小时，使用系统重编码来传输数据具有更好的性能。

图3 k = 1 时基于系统重编码的分批稀疏码归一化秩期望

图4 k = 2 时基于系统重编码的分批稀疏码归一化秩期望

图6 k = 0 时基于RLNC 重编码的分批稀疏码归一化秩期望

图7 k = 1 时基于RLNC 重编码的分批稀疏码归一化秩期望

图8 k = 2 时基于RLNC 重编码的分批稀疏码归一化秩期望

图9 k = 3 时基于RLNC 重编码的分批稀疏码归一化秩期望

4 结束语

本文分析了在时变信道下基于系统重编码的分批稀疏码秩分布，通过将信道链路上的丢包率建模成随机变量，得到了时变信道下秩分布的通用表达式，同时，本文进一步研究了链路丢包率服从有限区间正态分布时的秩分布且阶数k为任意值时，RLNC 和系统重编码的归一化秩期望的通用闭合解。随后通过蒙特卡洛仿真，验证了该闭合解的正确性与通用性。本文的研究均基于多跳线性网络模型，在实际生产生活中，无线网络的模型会更加多样。因此，对于更贴近实际生活的诸多非线性网络环境下，分批稀疏码在时变信道下的秩分布也同样具有研究价值，后续可进一步进行理论分析，探讨线性网络下的诸多结论和性质是否同样适用于其他非线性网络模型。