一种新型自适应网络编码协作方案

潘 博， 周武旸

0 引言

用户协作最早是由van der Meulen在1971年提出的[1]。1979年Cover和El Gamal进行了进一步的理论推导，提出多用户编码协作策略[2]。

一个传统的中继结构，主要是由3个部分组成的：源端,中继和目的端。基于这个结构，有许多优秀的中继策略，例如重传，编码协作，空时编码协作等等。大量的研究也表明用户协作策略可以带来性能提升[3]，但这些方案在大规模无线网络环境中都有其无法避免的弊端[4]。而自适应网络编码协作ANCC（Adaptive Network Coded Cooperation）方案[4]利用了跨层设计的思想，将动态的网络结构与低密度奇偶校验码[5]LDPC（Low-density Parity-check）的编码结构[6-7]相结合，在系统容量、中断概率以及性能方面都比传统方案有大幅度的改善[8-9]。

本文从 LDPC的码字性能出发，分析了自适应网络编码协作方案中使用的编码结构 LDGM（Low-density Generator-matrix）[10]，找出了该结构中影响性能的因素。本文提出一种新型自适应网络编码协作方案。该方案利用了在原有自适应网络编码协作方案中浪费的信息，解决了LDGM编码结构的缺陷。性能分析和仿真结果表明，在不增加系统开销的前提下，新方案实现了进一步的性能提升。

1 自适应网络编码协作方案的基本思想

网络编码通过允许中继节点来执行简单的编码业务，提供了新的路由能力，并使网络吐吞量优化成为可能[11-12]。考虑一个一般化的网络模型：两个发送节点向一个共同的接收节点发送数据，发送的数据分别用a和b表示。在发送的过程中，我们有两种基本的方法利用中继节点进行辅助传输以实现性能的提升。第一种方法比较简单，每一个发送节点都有一个中继节点进行辅助，中继节点只是将发送节点发送的数据简单地重复转发。第二种方法，只利用一个中继节点进行辅助，它接收两个发送节点发送的数据并对其进行编码，用ab⊕表示，再将编码后的数据发送给接收节点，这种方法就是网络编码。两种方案都使发送的数据在达到2的分集,但研究表明[12]，第二种方法在一个较少的带宽消耗中实现了更低的中断概率。

自适应网络编码协作方案，正是利用了跨层设计的思想，将上述的网络编码结构引入到了大规模无线网络的用户协作中来。整套方案分为两个阶段：

① 广播阶段：每个用户广播自己的用户信息，同时监听其他用户的信息，并将正确收到的信息保存下来组成自己的备选集；② 中继阶段：每个用户从自己的备选集中随机选出固定数量（用Q来表示）的信息做校验和，然后将得到的校验结果发送给接收端。这里我们假设，接收端知道发送端选择的是哪些用户的信息来做的校验和（例如，可以利用其他带宽传输相关信息给接收端）。这样每次传输过程中，接收端收到的信息比特，可以等效为经过一个全新的码率为1/2的LDPC码编码后的比特。该LDPC码与当前的网络拓扑结构相对应，再用传统的BP（Belief Propagation）算法[5]进行译码，从而实现性能的提升。

可以看到，在上述自适应网络编码协作方案中，利用的LDPC结构是LDGM结构，其校验矩阵由两部分组成，左边的稀疏矩阵P和右边的单位阵I。

2 一种新型自适应网络编码协作方案

基于上述分析，自适应网络编码协作方案，充分利用了LDPC码校验矩阵的稀疏特性。但同时也存在缺陷，主要包括以下两个方面：

① 原有的方案利用了LDGM的编码结构，但此码字结构的右侧是一个单位阵,会造成不可避免的性能损失。译码LDPC的BP迭代算法，可以用式(1)、式(2)式表示：

其中()lvcm 代表在第l次迭代中信息节点传递给校验节点的置信信息，同样的，()lcvm 代表在第l次迭代中校验节点传递给信息节点的置信信息。可以看到式(3)是一个乘式，所以与式(3)相关的每个()lvcm 的正负符号都非常重要，且()lvcm 的绝对值（置信度）较小也会影响整体的逼近速度。所以在 BP算法中 LDPC码的校验矩阵中的列重对码字性能影响很大，而LDGM校验矩阵右侧列重为1的信息节点只有一个校验节点来保护，这会严重影响码字的性能；

② 在现有的自适应网络编码协作方案中，与传统信道编码相同，需要加入额外的比特来制造信息之间的相关性，以帮助恢复由于信道造成失真的信息。但实际上，由于发送端的用户在广播阶段收集备选集信息时，实际已经知道了收集到的信息的具体值，原有方案将这些已知的信息完全浪费掉了。

根据以上两点的分析，我们提出一种新型自适应网络编码协作方案，我们简称为NANCC（New Adaptive Network Coded Cooperation）方案。为了阐明NANCC的基本思想，以5个用户为例，分别把5个用户标识为A，B，C，E，F，他们向共同的接收端D发送数据。首先，每个用户在各自独立的信道中广播自己的数据。与此同时，这些用户也都在监听其他用户广播的信息，并把自己成功收到的其他用户的信息保存下来组成自己的一个备选集。这时，每个用户已经知道了其他用户的信息值。所以在下一个阶段，每个用户不需要再发送新生成的校验值，而可以直接从先前自己收到的备选集中随机选出一部分数据使校验和等于 0。可以看到此方案不需要加入额外的信息来制造相关性，而通过多用户已知的信息，找到了原有发送信息间的相关性。

综上在大规模无线网络的环境中，新型自适应网络编码协作方案表述如下：仍然将整套策略分为两个阶段。① 广播阶段：每个用户广播自己的用户信息，与此同时监听其他用户的信息，并将正确收到的信息保存下来组成自己的备选集；② 中继阶段：每个用户从自己的备选集中随机选出固定数量（我们用Q来表示）的信息使他们的校验和为0。在这里依然假设接收端已知发送端选择的是哪些用户的信息。这样充分利用了各个用户在第一阶段中得到的信息，也有效避免了LDGM校验矩阵右侧列重为1的点对性能的影响。新生成的LDPC结构不再有右侧的单位阵。

3 中断概率与信道容量分析

（1）互信息量

对于瑞利衰落信道来说，互信息量可以表示为：

其中，γ表示信噪比SNR，α表示信道信息，在这里就是复瑞利衰落因子。

原有的自适应网络编码协作方案，最后形成的是1/2码率的LDPC码，所以在计算互信息量时有一个1/2的因子。可以知道在广播阶段一个节点发送的互信息量可表示为，其中,idα表示第i个节点和接收端之间的信道信息。而在中继阶段，由于假设信道间是独立的，且对每个节点的帮助是均等的，所以在中继阶段每个节点获得的信息量是于是总信息量如式(5)所示（单位：b/s/Hz）：

其中，m表示总用户数。

而新型自适应网络编码协作方案不再需要加入冗余比特来制造信息比特间的相关性，所以没有1/2的因子。同上假设新方案的互信息量如式(6)所示（单位：b/s/Hz）：

可以看到，在对等网络的前提下（信道信息近似为独立同分布的变量），式(5)、式(6)两式是近似相等的。于是对于两种方案来说，可达到的信息速率和中断概率也是近似相等的。

（2）可达到的信息速率

基于上述假设，系统平均可实现的速率C就是互信息量的期望（单位：b/s/Hz）。于是：

其中：

（3）中断概率

两者的中断概率我们从定义出发，

可以看到新型自适应网络编码协作方案，相比原有方案，不仅未增加系统开销，同时在系统容量与中断概率方面未造成任何损失。

4 仿真结果

假设有m个用户，通过无线信道向一个公共的接收端发送数据。不失一般性，假设每个用户之间是对等信道，每个用户都以 0.1p= 的概率成功接收到其他用户的信息，而且每个用户与接收端之间都经过一个频率平坦的半静态瑞利衰落信道，用式(10)表示：

其中，α是一个复瑞利衰落因子，而n是一个复加性高斯白噪声。同时在发送过程中使用 BPSK调制方式，所以x∈{- 1 ,1}。假设所有的传输信道之间是相互独立的，同时信道增益是接收端已知而发送端未知的。新方案仍然按1/2码率来计算Eb/No。

性能图线如图1所示，假设m=1000。本文提出的方法，即NANCC，相比原有的方案，即ANCC，性能有大幅度的提升。ANCC在Q=7的情况下，误比特率为 1 0-4时就出现了误码平台，且从趋势上看 Q越小，平台出现得越早。而NANCC在Q=3的情况下，误比特率为 1 0-5时都未出现误码平台。另一方面，以Q=4的新方案的LDPC结构与Q=9的原有方案的 LDGM 结构为例相对比，在误码率为 1 0-5时就有近5 dB的性能提升。（由于接收端已知信道信息，所以隐含有3 dB左右的性能提升，并未超过香农限）。这是因为在LDGM结构中，校验矩阵右侧的单位阵所对应的信息节点，严重影响了校验矩阵左侧所对应的信息节点的逼近速度，导致可能在迭代次数达到上限的前提下仍然不能计算出正确的置信度，从而使性能严重下降。而NANCC有效地提高了逼近速度，很好地解决了这个问题。

如图2所示，比较了在m=1000和m=2000时的性能。可以看到，NANCC，在增多用户数的情况下性能有显著的提升，以Q=4的NANCC来说，在高信噪比下有近1 dB的性能提升，而对于ANCC提升相当有限且同样很早出现误码平台。这是由于两种方案都无法避免LDPC矩阵中环的存在，增多用户使短环存在的可能性大大降低，性能实现提升。而对于原有方案，因为影响性能最重要的因素已经不是环的存在，而是校验矩阵右侧列重为1的点，增多用户无法消除其过早出现误码平台的问题。所以对于大规模无线网络环境来说，新型自适应网络编码协作方案，更为适合。

图1 用户数为1000的条件下协作方案的整体性能

图2 用户数分别是1000与2000时适应网络编码的性能比较

5 结语

在大规模无线网络环境下，本文提出了一种新型自适应网络编码协作方案。此方案充分利用了在中继过程中各个用户得到的信息，找到了发送信息之间的相关性，从而避免了原方案校验矩阵中列重为1的部分，改善了LDPC码的校验矩阵结构。分析与仿真结果表明，新方案没有增加任何的系统开销，且在中断概率与系统容量保持不变的前提下，实现了性能的大幅度提升。同时，也可以看到用户越多新方案的性能提升越明显，所以相比原有方案，新方案更适合于大规模的无线网络。

[1] van der Meulen E C. Three-terminal Communication Channels[J].USA：[s.n.], 1971：120-154.

[2] Cover T M, El Gamal A A. Capacity Theorems for the Relaychannel[J]. IEEE Trans. Inf. Theory, 1979(IT-25)：572-584.

[3] Hunter T E, Nosratinia A. Cooperation Diversity Through Coding[C].USA：IEEE, 2002：220-221.

[4] Bao X, Li J.Adaptive Network Coded Cooperation(ANCC) for Wireless Relay Networks： Matching Code-on-Graph with Network-on-Graph[J].IEEE Trans on Wireless Communications,2008,7(02)：574-583.

[5] Gallager R G.Low Density Parity-Check Codes[M]. Cambridge：MIT Press, 1963.

[6] 龚莉萍,陈云榕,胡凯.LDPC编译码技术研究[J]. 通信技术,2009,42(07)：10-12.

[7] 韩辉,周武旸,董桂强,等. 一种改进的LDPC码译码算法[J]. 通信技术, 2009,42(11)：214-216.

[8] Bao X, Li J. Matching Code-on-graph with Networks-on-graph：Adaptive Network Coding for Wireless Relay Networks[C].USA：[s.n.],2005：114-117.

[9] Bao X, Li J.An Information Theoretic Analysis for Adaptivenetwork-coded-cooperation (ANCC) in Wireless Relay Networks[J]. In Proc. IEEE Intl. Symp. Inf. Theory, 2008(02)：574-583.

[10] Garcia Frias J, Wei Zhong. Approaching Shannon Performance by Iterative Decoding of Linear Codes with Low Density Generator Matrix[J]. IEEE Commun. Letters, 2003,7(06)：266-268.

[11] Ahlswede R, Cai N, Li S Y R,et al.Network Information Flow[C].USA：IEEE,2000：1204-1216.

[12] Koetter R,edard M M.An Algebraic Approach to Network Coding[J]. IEEE,2003,11(05)：782-795.