两跳通信中一种含有编码密度信息的Batch 方案

陈 超，王 力，张士兵，李 业

（南通大学 信息科学技术学院，江苏 南通 226019）

两跳中继通信可以作为扩大信息传输范围的关键技术[1]，并且在海域卫星通信[2]、智能化通信[3]和一体化网络[4]中发挥着优势。文献[5]研究了一种基于网络编码（network coding，NC）的两跳通信系统，通过异或编码可以提高两跳通信的效率。但是在使用NC 技术进行通信设计时，要考虑解码成功率和编解码开销。不合理的NC 方案会造成较低的解码成功率和较高的编解码开销[6]，导致通信效率降低。

在现有的编码方案中，通过有限域上的迹函数和2 次剩余理论构造的四重和六重线性码是关于Singleton 界的几乎最佳码[7]。线性码，尤其是随机线性网络编码（random linear network coding，RLNC）可以有效提高多跳通信的信息传输效率[8]，但其编解码开销较大。Batch 编码技术作为RLNC 的一种改进方案[9]，通过减少参与编码的源分组数，增加编码分组的稀疏性，能够提高解码成功率。文献[10-11]通过改变Batch 分组的编码密度实现了编码开销的降低。

现有的解码方式可以基于统计进行，也可以基于矩阵变换进行。基于统计的解码方式，将目的节点接收到的编码分组进行统计，优先解码那些编码方式简单的分组，可以快速完成解码[12]。较为普遍的解码方式是基于矩阵变换进行的，包括子集重叠感知解码方案（overlap-aware algorithms，OA）、高斯消元法（gaussian elimination，GE）和反向传播与遗传结合的解码算法（back propagation and genetic algorithms，BGA）。文献[13]提出的OA 对编码系数矩阵分解后进行对角化，由于编码的稀疏性，可以降低解码开销；文献[14-15]基于传统的高斯消元法进行优化，以减少传输过程中的解码开销；文献[16]通过将反向传播和遗传算法结合进行解码，在复杂的无线通信网络中具有较低的解码开销；文献[17-18]将操作性更好的GE 解码方案运用到车联网，保证“车-车”之间的实时通信；文献[19-20]将高斯消元法应用到多播网络的解码过程中，使解码的复杂度降低。由于GE 方案的易操作性，解码过程可以快速完成。BGA 通过反向传播和遗传算法分散解码复杂度，引入实时解码方式，调整源分组选择的概率，通过非均匀选择促进解码的快速完成，从而降低解码过程中的开销。

为了在控制编解码开销的基础上，进一步提高两跳场景下Batch 方案的解码成功率，本文提出含有编码密度信息的编码方案和分类求值的解码方案。文中的主要工作有：1）构建RLNC 和Batch 方案解码成功的条件，分析参与编码的源分组对解码的影响；2）设计含有编码密度信息的Batch 编码方案，在该编码方案中，编码信息将放置在分组包头，中继节点根据包头的编码信息对不同的编码分组进行筛选，以提高解码成功率；3）设计分类求值的解码方案，在该解码方案中，目的节点根据编码信息对不同分组进行分类，并根据从简到繁的原则进行解码，以降低解码开销；4）采用仿真软件MATLAB，比较和分析本文方案和现有Batch 方案的解码成功率及解码开销。

1 问题建立

一个无线中继通信系统包含源节点、中继节点和目的节点，如图1 所示。在源节点，信息被分成m个源分组，记为si，i=1，2，…，m。当使用RLNC 编码时，所有的源分组都参与编码，其编码输出可表示为

图1 两跳中继通信模型示意图Fig.1 Two-hop communication model

其中：n 表示RLNC 编码分组的个数；a 是来自于有限域GF（q）的编码系数；q 为有限域大小。编码系数在传输过程中一般放置在分组包头。为了方便描述，将式（1）简化为R=A·S，这里A 称作编码系数矩阵，R 称作编码分组矩阵。

设中继节点只进行转发，不进行编码操作，那么在目的节点，解码方式可表示为

当A 的秩为m 时，S 中的元素就可以通过解码得到。如果出现n ＜m 等情况，导致A 的秩小于m，则不能完成解码。由于矩阵求逆的计算量较大，所以A的秩是否为m 只作为解码是否成功的判断标准。在实际解码过程中，目的节点首先将接收到的A 和R 进行矩阵初等变换，使A 除对角线外的其他元素为0（对角化操作）。然后，根据变换后R 中的元素，依次确定S 中的元素。根据文献[9-14]中的定义，将解码过程中需要进行矩阵初等变换的次数称为解码开销。源分组数m 和编码分组数n 都会对解码开销造成影响。因此，可以通过对编解码方案进行设计来降低解码开销。

文献[6]提出的Batch 编码会随机选择d（d

其中n*表示Batch 分组的个数。在解码时，将未参与RLNC 的源分组编码系数设置为0（“非选置零”操作）。可以发现，当适量源分组的编码系数为0时，可以更好地进行编码系数矩阵和编码分组矩阵的对角化，使解码成功率提高，解码开销降低。

基于固定的编码密度（d）进行Batch 编码也可以降低解码开销[10]。但从图2 中发现，第1 个Batch 分组（即B1）含有源分组s1、s2和s3；第2 个Batch 分组（即B2）含有s2和s3；第3 个Batch 分组（即B3）含有s1和s2。通过不同编码密度的Batch 分组可以成功解码s1、s2和s3。根据式（3）和“非选置零”操作可知，此时的编码矩阵中a21和a33等于0。在进行对角化操作时，需要的矩阵初等变化次数，相对于a21和a33不等于0 的情况，有所减少。所以适当调整Batch 分组的编码密度，可以在保证解码成功的同时，降低解码开销。

图2 不同编码密度的Batch 和其包含的源分组Fig.2 Batchs with different encoding densities and its source packets

在对两跳通信的编解码方案进行设计时，本文主要考虑方案的解码成功率和解码开销。综合式（1）～（3）和图2 中的分析，编码密度d 是影响两跳通信中解码成功率和解码开销的关键。目前的Batch 方案采用固定的d 进行编码，可能会导致解码成功率降低。在源分组较多时，OA、GE 和BGA的解码方案的解码效率可能会下降，会导致解码开销增加。因此，需要设计更适用于两跳通信的编解码方案，通过调整编码密度d 来提高解码成功率，并能够在源分组较多时，保持解码的效率，控制解码开销。

2 编解码方案设计

2.1 编码方案

本文设计含有编码密度信息的Batch 编码方式（code-density-information-involved Batch encoding，CDBE），CDBE 分组包含编码密度信息、编码系数和编码后的源分组，如图3 所示。除了解码开销，本方案也考虑到编码开销，文献[6-8]将包头编码信息所占的比特数记为编码开销，所以在本文中，编码密度信息和编码系数所占的比特数为编码开销。设置d 远小于m，这样参与编码的源分组较少，编码系数所占的长度较短，可以控制编码过程中的开销。

图3 CDBE 分组Fig.3 CDBE packet

在进行编码之前，确定d 与编码密度信息的对应关系，需要保证这种对应关系是“单对单”的，并且要求编码密度信息所占的位数尽可能少，这样可以保证CDBE 的编码开销较低。如d 的取值区间为[1，7]，那么在二进制下，编码密度信息和d 的一种对应关系如表1 所示。编码密度信息放置在CDBE分组最前端，以便下游节点可以迅速查看分组的编码情况。编码系数放置在编码密度信息后，能够反映参与CDBE 编码的源分组。中继节点在接收到CDBE 分组时，会查看包头的编码密度信息，当编码密度信息对应的d 较小时，中继节点会将CDBE 分组转发到目的节点；当对应的d 较大时，中继节点会将CDBE 分组暂存，当中继缓存饱和时，会优先向目的节点转发缓存中d 较小的CDBE 分组。这样做的目的是保持CDBE 分组的稀疏性，以提高解码的成功率。整个CDBE 的编码主要过程如图4 所示。

表1 编码密度d 和编码密度信息的对应关系Tab.1 Relations between encoding density dandencoding density information

在图4，源节点阶段，d 的选择服从均匀分布。设d 的区间为[1，k]，那么各值被选中的概率为1/k。在“形成CDBE 分组”时，编码密度信息占用，编码系数占用dlog2q bit。那么CDBE 编码开销可表示为

图4 CDBE 编码过程Fig.4 CDBE encoding

在中继节点阶段，设置dmin用以判断接收到的CDBE 分组是否足够“稀疏”。这样做可以使d 较小的CDBE 分组直接转发到目的节点。当中继节点饱和时，中继节点会将缓存中的编码密度较小的CDBE 分组优先发送，腾出缓存空间以保证源节点发送的CDBE 分组的存储。在本方案中，dmin设置为

在目的节点阶段，需要分析CDBE 分组的解码成功率。按照问题建立中的Batch 编码方式，源节点每次选择d 个源分组进行编码形成CDBE 分组，经过中继节点，转发到目的节点。当目的节点解码不成功时，中继节点会暂停向下游节点发送CDBE 分组，并且会发送一个调整d 的反馈信息分组，当源节点接收到反馈信息分组后，调整d 后进行新的CDBE 分组传输，当中继节点收到信息CDBE 分组后，开始新的一轮CDBE 分组传输。

在稀疏性降低时，编码系数和编码后的源分组长度变短，CDBE 分组的长度会变短。根据文献[9]可知，编码分组长度变短时，分组在传输过程中的丢包率会降低，传输的可靠性会提高。

当目的节点收到的编码系数构成的编码矩阵ACDBE的秩为m，解码成功。ACDBE可表示为

其中An*表示目的节点接收的第n*个CDBE 分组的编码系数向量。An*中的每个非零元素（编码系数）都有与其对应的源分组，如式（6）所示，设A1中的元素为auv，当A1中的a12非零时，可以确定第1 个CDBE分组中含有源分组s2。每个CDBE 分组含有不同源分组（编码系数）数的概率分布为

其中：Ele（An*）表示An*中非零元素的个数；dn*表示目的节点收到的第n*个CDBE 分组含有源分组（编码系数）的个数。

当目的节点收到A1时，ACDBE的秩定会增加1，即

其中r（ACDBE）表示ACDBE的秩。当目的节点收到A2时，r（ACDBE）的变化需要分情况讨论。设A1和A2的编码密度分别为d1和d2。

1）A1和A2含有的源分组没有重合。

A1和A2中源分组没有重合的一种可能情况为

在这种情况下，d1=d2=2，第1 个CDBE 分组含有源分组s1和s2，第2 个CDBE 分组含有源分组s3和s4。A1和A2之间没有重合的源分组。

当d1和d2确定后，A1和A2含有的源分组没有重合的概率可表示为

此时，r（ACDBE）会增加1。

2）A1和A2含有的源分组存在重合。

A1和A2中源分组存在重合的一种可能情况为

在这种情况下，d1=d2=2，第1 个CDBE 分组含有s1和s2，第2 个CDBE 分组含有s2和s4，重合的源分组为s2。

设A1和A2含有的源分组重合个数为dsup，dsup∈[1，min（d1，d2）]。由于没有外界因素干扰，所以各种重合情况出现的概率相等。那么A1和A2重合的源分组数为dsup的概率表示为

当dsup

在计算解码成功率时，首先，通过式（7）计算每次收到CDBE 分组中源分组数可能出现的情况。以源分组数m 为5，d∈[1，4]举例，每次收到的CDBE分组中源分组数的概率分布如表2 所示。然后，通过式（10）和（12）可以计算出CDBE 分组之间完全不重合和只有部分重合的概率，以此得到r（ACDBE）的变化情况。最后，计算收到nmax个CDBE 分组后解码成功的概率，这里的nmax表示目的节点最多能接收到的CDBE 分组数。实际操作中发现，这样计算解码成功率太过复杂，可以使用解码失败率反推出解码成功率。

表2 源分组数m 为5，d∈[1，4]的CDBE 分组中源分组数的概率分布Tab.2 Probability distribution of the number of source packets in the CDBE when m=5 and d∈[1，4]

当新收到的CDBE 分组所含源分组数不同时，r（ACDBE）必会增加，这是编码成功的要素之一。当新收到的多个CDBE 分组所含的源分组完全重合，使r（ACDBE）保持不变，可能会导致解码失败。在d 确定时，新收到的CDBE 分组使r（ACDBE）保持不变的概率为

然后根据二项分布的原理，以nmax=m 为例，通过反推法可以得到解码成功率为

2.2 解码方案

解码方案是基于目的节点收到nmax个CDBE分组解码成功（r（ACDBE）=m）的前提下设计的，此时ACDBE是nmax行m 列的矩阵。目前，解码的主要过程就是将ACDBE对角化。需要将ACDBE等效转化为

其中：x 是非零数；ACDBE非对角线区域的元素为0。这种方法只涉及矩阵的行列初等变换，操作简单。但是，每次行（列）变换都涉及m（nmax）个元素，当m（nmax）较大时，解码开销可能较大。为了进一步降低解码开销，本文提出一种分类求值解码方式（classification and evaluation decoding，CED）。CED分为2 个步骤，即分类和求值。

1）分类 目的节点将编码密度（d）相同的CDBE 分组归为一类，同类分组中的编码系数和编码后的源分组分别存放到Di和Ri中，其中Di表示d=i 的同类CDBE 分组编码系数矩阵（如果2 个CDBE 分组所含的源分组完全相同，则随机保留1个），Ri表示d=i 的同类CDBE 分组中编码后的源分组矩阵。

2）求值 设Si表示在R1～Ri解码过程中已经成功求出的源分组矩阵。求值的主要过程如图5 所示。在第I 步中，令d=1，可以通过D1和R1依次确定S1中的元素。由于D1是局部的编码系数矩阵，同时每行（列）只有1 个非零元素，所以矩阵的对角化相对简单。当第Ⅰ步完成后，S1含有部分已经解码成功的源分组。在第Ⅱ步中，令d=2，由于编码系数与源分组的对应关系，D2中的编码系数可以反映R2含有的源分组，查看S1与R2未解码的源分组之间是否存在相交，如果存在相交，则将S1中已经解码成功的源分组带入进行第Ⅱ步的解码；否则，进行第Ⅲ步。以此方式逐步推进，当求值过程进行到d=k 结束时，整个解码过程完成。需要注意的是，CED 解码可能出现一种特殊情况，在d=k 之前，没有完成Di（i=1，2，…，k-1）中的源分组解码。此时，相比于子集重叠感知解码[10]和高斯消去法[11]，文献[15]中BGA 方案解码开销较低，可以作为这种极限情况的紧急应对策略。不过，本方案中设置中继节点对不同编码密度的CDBE 分组进行了筛选，可以抑制这种特殊情况的发生。

图5 CED 的求解实例Fig.5 An example of solving in CED

3 数值仿真与分析

本文采用MATLAB 对两跳场景下CDBE 的解码成功率和CED 解码开销进行仿真。在仿真解码成功率时，将CDBE 与不同Batch 方案[6]进行比较。在仿真解码开销时，将CED 与OA[10]、GE[11]和BGA[12]进行比较。设置源分组数m∈[100，1 000]，nmax=m，k∈[1，4]，q=256，中继缓存为10 个CDBE 分组，编码密度信息与d 的对应关系如表3 所示。

表3 当k∈[1，4]时，编码密度d 和编码密度信息的对应关系Tab.3 Relations between encoding density d and encoding density information when k∈[1，4]

图6 示意了CDBE 与不同Batch 编码方案在源节点发送不同数目源分组时的解码成功率比较。从图6 中可知，无论如何调整d 值，Batch 的解码成功率都低于CDBE。这是由于CDBE 会优先发送将有益于解码完成的分组。相比于d 较小的Batch方案，CDBE 能够提高目的节点接收不同编码密度分组的概率，便于目的节点的解码；相比于d 较大的Batch方案，CDBE 可以减少发送含有相同源分组的编码分组的概率，增加解码成功率。因此，当d∈[1，4]时，CDBE 方案的解码成功率要比同样编码密度下的Batch 方案高。

图6 CDBE 和Batch 编码的解码成功率比较Fig.6 Comparison of decoding success rate of CDBE and Batch

图7 中单位编码开销的解码成功率（decoding success rate per encoding cost，DC）反映编码开销对解码成功的积极影响，计算方法是解码成功率除以编码开销。DC 值越大，编码开销越有助于解码成功。从图中可知，CDBE 方案的DC 值大于其他Batch 方案，这是由于CDBE 分组中编码密度信息占用的空间不大，同时中继节点会暂存编码密度较大的分组，这也使得转发的CDBE 分组编码密度普遍较小，即编码开销小。从图6 和7 中可以看出，CDBE 方案的解码成功率要优于其他Batch 方案15%以上。

图7 CDBE 和Batch 单位编码开销的解码成功率比较Fig.7 Comparison of decoding success rate per encoding cost of CDBE and Batch

图8 是CED、GE、OA 和BGA 4 种解码方案的开销比较。随着源分组增多，解码的维度增加，CED、GE、OA 和BGA 对应的解码开销都会增加。但是相比于其他3 种解码方案，CED 开销增长幅度较小。这是由于CED 解码遵循从简到繁的原则，通过编码密度（d）较小的编码分组优先解码，为之后的解码减少了计算量。OA 和GE 直接使用矩阵的初等变化进行解码，操作简单，但随着源分组的个数增加，所需要进行的矩阵初等变换会导致较高的解码开销。BGA 使用误差反向传播和遗传算法将解码开销分散，但是随着需要解码的分组变多，非均匀的选择方式，会导致部分源分组无法解码，分散处理的效率下降，导致解码开销增加的幅度大于CED。

图8 CED、GE、OA 和BGA 方案的解码开销比较Fig.8 Comparison of decoding cost of CED，GE，OA and BGA

4 结论

本文提出的CDBE 编码和CED 解码方案可以有效解决两跳通信的解码成功率和开销的问题。CDBE 编码方案将编码信息放置于分组包头，中继节点根据包头信息对不同编码密度的分组进行筛选，能有效减少转发过程中的编码开销，提高解码成功率。相比于GE、OA 和BGA，CED 解码方案通过对不同编码密度的CDBE 分组进行分类和求解，能够降低解码开销。与此同时，虽然编码密度信息和编码系数占用的空间有限，但仍需要进行合理的设计，否则会降低CDBE 分组在物理层传输的有效性。