网络编码在无线通信网络中的应用

基金项目：国家自然科学基金资助项目(60502046)；国家高技术研究发展计划(“863”计划)资助项目(2007AA01Z215)

    2000年，文献[1]首次将编码的通信方式引入到网络通信，即网络节点对多条输入链路上收到的数据信息进行一定的线性或非线性处理(网络编码)，同时证明了在单点对多点的网络通信中，通过节点编码的方式可使信息传输速率达到网络的最大流量，这一发现为网络通信带来了根本性的变革。

    研究显示，网络编码是可以逼近网络容量理论传输极限的有效方法，具有确定拓扑的有线网络的网络编码受到了广泛关注。由于无线链路的不可靠性和物理层广播特性非常适合采用网络编码，无线网络环境应该是网络编码首先被应用的领域。目前，基于网络编码的中继技术、协作分集技术以及网络编码和信道编码的联合设计技术，已经引起了人们的广泛关注，有了大量的研究成果。

1 网络编码在中继网络中的应用

1.1 异或运算
    中继节点通过对接收到的数据进行异或(XOR)运算完成信息合并，实现中继节点的数据压缩，这是网络编码技术应用于无线通信网络的最直接的一种形式。文献[2]和[3]研究了Two-way中继网络环境下的基于XOR运算的信息交换，文献[4]和[5]研究了基于网络编码的无线Mesh网演示平台。

1.2 置信传播算法
    网络编码应用于无线中继网络[6]的另一种形式是采用软信息合并，如图1(a)所示的无线中继网络模型，信源节点S1、S2到中继节点R的信道存在噪声和信号衰落。中继节点R采用置信传播算法计算网络编码信息(即异或结果)的对数似然比(LLR)，并发送到目的节点，如图1(b)所示。假设信源S1和S2和是两个独立的二进制随机信源，具有相同的0、1分布，信道为高斯信道，且从信源到中继节点的两个信道状态相同，从信源到目的节点两个信道状态也相同。采用卷积编码对信息进行编码，中继节点R需进行如下操作：

    首先，中继节点采用BCJR算法对信源信息进行译码，得到其LLR；

    然后，对信源S2码字的LLR信息进行交织操作，减少目的节点D接收到的3个不同信息之间的依赖性；信息的LLR值。

    图1(b)中，u1和u2分别表示信源S1和S2信道编码器的输入信息，x1和x2分别表示信源S1和S2信道编码器的输出编码信息。NSR表示信源到中继节点链路上的噪声。中继节点采用BCJR算法分别对信源S1和S2编码信息进行译码，得到其LLR值L 1和L 2。对L 2进行交织操作，且与L 1进行异或运算，得到x1?茌x'2的LLR。NSD表示信源到目的节点链路上的噪声，NRD表示中继节点到目的节点上的噪声。y1和y2分别表示目的节点接收到的来自信源S1和S2的信息，而yR表示目的节点接收到的来自中继节点R的信息。

    如果中继信道条件很差，上述译码器成为两个独立的卷积译码器；否则，当中继信道条件和网络编码信息的LLR很好时，该译码器成为一个简单的Turbo码译码器。

1.3 复数域网络编码
    在大规模网络中，传统中继方式降低了频谱的有效性，为进一步提高网络吞吐量，文献[7]提出了复数域网络编码(CFNC)的概念，不仅能够获得1/2符号/信源/时隙(Sym/S/TS)的吞吐量，还可获得完全分集增益。另一方面，CFNC还可实现多个信源之间的信息交换。

    首先考虑如图2所示的(2,1,1)无线中继网络，每个节点有一根天线，两个信源S1和S2直接或者通过中继节点R向目的节点D发送信息。

    传统的中继传输方案如图2(a)所示，网络吞吐量为1/4Sym/S/TS。由于目的节点两次接收到信息x1和x2，该中继传输方案获得了2阶分集增益。

    图2(b)给出了基于有限域网络编码的协作传输模型，中继节点在前两个时隙对信息x1和x2进行检测得到x1和x2，在时隙3将有限域上的编码符号x1?茌x2发送给目的节点D。基于有限域网络编码的吞吐量为1/3Sym/S/TS，可获得2阶分集增益。

    基于CFNC的协作传输方案如图2(c)所示。在时隙1，中继节点R同时接收来自信源S1和S2的信号θ1 x1和θ2 x2，系数θ1和θ2属于复数域。在时隙2，中继节点将估计信息x1和x2进行复数域上的合并，发送信号θ1x1+θ2x2。文献[7]分析表明，在无线中继网络采用CFNC不仅可获得1/2Sym/S/TS的吞吐量，还可以获得满分集增益

1.4 信道编码和网络编码联合设计
    上述几种方案重点研究了网络编码应用于无线中继网络的实现方法，但Effros等人在随机线性编码讨论中，指出很多情况下，需要考虑信道编码和网络编码的联合设计。目前，信道编码和网络编码联合设计方案主要有嵌套编码[8-9]和混合编码[10-12]两种形式。

    嵌套编码的基本思想是在中继节点分别对收到的信息进行编码，将编码得到的数据进行异或运算后发送出去，这等价于利用多个独立子码构成一个超码。文献[8]和文献[9]提出了采用嵌套码来实现网络编码和信道编码联合设计的思想。

    针对两个源节点、一个中继节点和一个目的节点的无线通信网络结构，文献[10]和文献[11]提出在中继节点采用混合编码方式实现联合网络信道编码的方案，如图3(a)所示。相应地，图3(b)给出了采用分离信道和网络编码的中继节点编码框图。文献[12]针对一个源节点，一个中继节点和一个目的节点的无线通信网络，提出了一种双层LDPC编码方案。

2 网络编码在多用户协作通信网络中的研究
    2006年，文献[13]在WCNC会议上首次提出了基于网络编码协作分集的概念，分别在两个系统模型中考虑网络编码协作分集：分布式天线系统(DAS)和多用户协作通信网络。研究结果表明，与传统的DAS相比，基于网络编码的DAS具有更好的分集性能，且具有更低的硬件损耗和更高的频谱效率。在多用户协作通信情况下，采用网络编码能获得更高的分集增益。

2.1 基于网络编码的自适应译码转发协作传输方案
    在网络编码自适应译码转发协作传输(NC-AdDF)方案中[14]，若用户成功译码其协作伙伴的信息，在第二个阶段将自己的信息和协作伙伴的信息进行网络编码，并将编码后的信息发送给目的节点；否则，直接将自己的信息发送给目的节点。

    图4给出了NC-AdDF网络模型，用户A和B分别向目的节点D广播信息XA和XB。

    用户A在第一个阶段传输XA，在第二个阶段传输XA?茌XB或者XA (依赖用户A是否成功译码用户B的信息)。同理，用户B也分别在两个阶段传输XB和XA?茌XB或者XB。对NC-AdDF的中断概率的分析表明，NC-AdDF相对于点对点传输具有更低的中断概率。当信源到目的节点的链路具有较高信噪比(SNR)或者信息传输在第一个阶段分配较大功率时，用户将获得更低的中断概率，改善系统性能。

2.2 一种新的适用于协作分集的网络编码算法
    基于有限域中信道码字的代数迭加(网络编码)思想，文献[15]提出了一种适用于协作分集的网络编码算法。图5给出了两用户进行协作分集的系统模型。两个用户A和B互为协作伙伴，向目的节点D协作传输数据包，每个用户传输局部信息与中继信息的代数和(网络编码和)，用户A和用户B根据各自的不同先验信息分别对得到的码字进行译码。目的节点D根据来自两个用户的码字进行迭代译码。

    与非协作分集方案相比，协作分集方案用户需要向其协作伙伴传输局部信息，这就导致了更高的码率或者更低的发送功率，从而会引起相对较高的差错概率，使得用户A和B链路上数据包的差错概率PA,B增加，降低了协作通信成功的概率。文献[15]提出一种新的适用于协作分集的网络编码算法。用户传输局部信息与中继信息的网络编码和，并根据已有的不同先验信息对得到的码字进行译码，目的节点根据来自两个用户的码字进行迭代译码。

    表1中表示在时隙t 传输的用户A的局部信息向量，表示用户A在相同的时隙内传输的中继信息向量。类似地，对于用户B也可以定义局部信息向量和中继信息向量。C A(t )和C B(t )分别表示用户A和B在时隙t 发送的n比特码字，GL和GR分别表示局部信息比特和中继信息比特的码字生成矩阵，而且码字速率的大小都为k /n。

    用户节点上的编码操作：用户A和B的操作基本一致，下面以以用户A为例进行说明。在时隙t，假定用户A成功译码中继用户B的信息，则用户A首先交织产生中继信息，将用户A局部信息的码字和用户A中继信息的码字进行异或(XOR)操作，生成码字C A(t)=iLA(t)

    上述伪随机交织可确保用户B的目的节点译码器向用户A的节点译码器提供的外信息与其获得的其他信息相互独立，有利于目的节点的迭代译码操作。

    如果用户A没有成功译码，用户A只对局部信息向量进行编码
    节点上的译码操作(目的节点D对进行译码)：根据上述编码方案，码字C A(t )和C B(t )中均带有信息，即以局部信息存在于码字C A(t )中，以中继信息存在于C B(t)中。C A(t)和C B(t )存在如下4种组合结构：
    (1)C A(t)=GL，C B(t)=GL，此时C A(t)和C B(t)只包含了局部信息，利用GL的译码器对进行译码操作。

    (2)C A(t)=GL?茌GR，C B(t)=GL，是交织后的中继信息。可从C B(t -1)获得的关于的外信息作为的先验信息，并使用最大后验概率译码对进行译码。

    (3)C A(t )=iGL，C B(t )=GL?茌GR。可在C A(t )和C B(t )的译码器之间进行迭代译码，交换关于和=π()的外信息。

    (4)C A(t )=GL?茌GR，C B(t )=GL?茌GR，采用矩阵G=[GL GR]T的软输入-软输出译码器进行迭代译码。由于=π()已经被实现，从C B(t -1)获得的外信息作为先验信息处理C A(t)，用0作为先验信息译码。C A(t)和C B(t)的软判决译码器交换关于的外信息。

    用户B含有中继信息时，可利用C B(t )和C A(t +1)对数据包进行译码操作，并可迭代译码扩展到多个码字来改善译码性能。以译码为例，除了包含的两个码字C A(t)和C B(t)进行迭代译码，还可以利用码字C A(t+1)和C B(t+1)，基本原理如图6所示。

    对非合作传输、时分多址合作传输、基于信号迭加的合作传输以及提出的网络编码合作传输4种方案比较可知，几种合作分集方案在高SNR时具有相同的错误曲线斜率，但网络编码合作传输的优势更明显。

3 结束语
    网络编码作为通信网络中的信息处理和传输理论研究的重大突破，具有重要的理论价值和广阔的应用前景，已被认为是下一代网络关键技术之一。将网络编码技术应用到无线通信系统中能进一步提高网络吞吐量、节省传输能量、增强鲁棒性和安全性。但也存在着如下尚未解决的问题，也是未来的研究方向：

    网络编码算法设计。目前已提出了很多网络编码算法，有集中式算法、分布式算法、线性以及分布式编码算法。由于实际分集网络采用网络编码，需要考虑同步、节点开销等问题，设计适用于协作分集的网络编码算法将成为一个非常有意义的研究方向。

    降低网络编码的计算复杂度。采用网络编码提高网络吞吐量的同时，增加了网络节点的编码操作，提高了其设计和实现的复杂度。如何在协作网络不显著增加节点开销的情况下，实现有效的网络编码协作分集处理，将有待于进一步的研究。

    频率选择性衰落信道下的分集性能研究。目前考虑网络编码在协作分集中的应用，一般都假设信道是平衰落的，但在实际移动通信系统中，信道往往是频率选择性衰落的，这种信道环境下基于网络编码的协作分集将成为一个研究热点。

4 参考文献
[1] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.
[2] LARSSON P, JOHANSSON N, SUNELL K E. Coded bi-directional relaying [C] //Proceedings of 5th Scandinavian Workshop on Wireless Ad-hoc Networks (ADHOC'05), May 3-4, 2005, Stockholm, Sweden.
[3] WU Y, CHOU P A, KUNG S Y. Information exchange in wireless networks with network coding and physical-layer broadcast [C]//Proceedings of the 2005 Conference on Information Sciences and Systems, Mar16-18, 2005, Baltimore, MD,USA.
[4] KATTI S, KATABI D, HU W, et al. The importance of being opportunistic: practical network coding for wireless environments [C]//Proceedings of 43st Annual Allerton Conference on Communication, Control, and Computing, Sep 29-30, 2005, Monticello, IL,USA.
[5] KATTI S, RAHUL H, HU W, et al. XORs in the air: practical wireless network coding [C]// Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '06), Sep 11-15, 2006, Pisa, Italy. New York, NY, USA: ACM. 2007: 243-254.
[6] YANG S, KOETTER R. Network coding over a noisy relay: a belief propagation approach. [C]//Proceedings of 2007 IEEE International Symposium on Information Theory (ISIT 2007), Jul 24-29, 2007, Nice, France. Los Alamitis, CA, USA: IEEE Computer Society, 2007: 801-804.
[7] WANG T, GIANNAKIS G B. Complex field network coding for multiuser cooperative communications[J]. IEEE Journal on Selected Areas in Communications, 2008, 26(3): 561-571.
[8] HAUSL C, SCHRECKENBACH F, OIKONOMIDIS I. Iterative network and channel decoding on a tanner graph [C]//Proceedings of 43st Annual Allerton Conference on Communication, Control, and Computing, Sep 29-30, 2005, Monticello, IL,USA .
[9] XUE F, SANDHU S. PHY-layer network coding for broadcast channel with side information [C]//Proceedings of IEEE Information Theory Workshop (ITW’07), Sep 2-6, 2007, Lake Tahoe, CA, USA. 2007: 108-113.
[10] HAUSL C, DUPRAZ P. Joint network-channel coding for the multiple access relay channel [C]//Proceedings of Sensor and Ad Hoc Communications and Networks(SECOH'06):Vol 3, Sep 28, 2006: 817-822.
[11] NGUYEN H T, NGUYEN H H, LE-NGOC T. A joint network-channel coding scheme for relayed-based communications [C] //Proceedings of Canadian Conference on Electrical and Computer Engineering(CCECE’07): Apr 22-26, 2007, Vancouver, Canada. 2007: 904-907.
[12] RAZAGHI P, YU W. Bilayer low-density parity-check codes for decode-and-forward in relay channels[J]. IEEE Transaction on Information Theory, 2007, 53(10): 3723-3739.
[13] CHEN Y, KISHORE S, LI J. Wireless diversity through network coding[J]. (WCNC’06), Proceedings of 2006 IEEE Wireless Communications and Networkings Conference (WCNC’06): Vol 3, Apr 3-6, 2006, Las Vegas, Nv, USA New York, NY, USA: IEEE, 2006: 1681-1686.
[14] WOLDEGEBREAL D H, KARL H. Network-coding-based adaptive decode and forward cooperative transmission in a wireless network: outage analysis[EB/OL]. [2008-11-17]. http://typo3.cs.uni-paderborn.de/fileadmin/Informatik/
AG-Karl/Pubs/dereje-EW07-NC-AdDF.pdf.
[15] XIAO L, FUJA T, KLIEWER J, et al. A network coding approach to cooperative diversity[J]. IEEE Transactions on Information Theory, 2007, 53(10): 3714-3722.

收稿日期：2008-11-17

[摘要] 网络编码是一种可以逼近网络容量传输理论极限的有效方法，在无线网络环境中有着广泛的应用前景。在无线中继网络中采用网络编码技术，可以使中继节点同时为多个用户转发数据，从而获得较高的转发效率。网络编码在无线中继网络中的典型应用方案包括噪声中继采用置信传播算法实现网络编码，复数域网络编码算法以及信道编码和网络编码联合设计方法，它们均可在获得较高网络吞吐量的同时实现完全分集。在多用户协作通信网络中采用网络编码技术，可获得更高的分集增益以及更低的符号错误概率。

[关键词] 网络编码；无线中继网络；协作通信

[Abstract] As one of the effective methods to approach the network capacity, the network coding technique has received wide attention in the wireless networks. In wireless relay networks, message from several source nodes can be relayed simultaneously via the network coding technique. The three typical application schemes, including belief propagation algorithm over a noisy relay to complete network coding, complex field network coding and joint network-channel coding, can achieve higher throughput and full diversity gain. Compared with conventional cooperative diversity schemes, multi-user cooperation through network coding can attain higher diversity gain and lower symbol error probability.

[Keywords] network coding; wireless relay network; cooperative communications