一種新型自適應網絡編碼協作方案

潘 博， 周武旸

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.