新一代無線通信網中的網絡編碼*

范在山1，張祖凡1，吳愛愛1，蔣勁松

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.四川省鼎訊科技有限公司，成都 610041)

1 引 言

網絡編碼的核心思想是網絡中參與傳輸的節點上輸出的數據，可以通過該節點多條輸入上傳輸的數據的某種線性或非線性變換而得到，且參與傳輸的所有節點對數據變換可以保證最終所有接收節點正確恢復出信源所發送的信息。在一定程度上也可以認為它是一種融合了編碼和路由的交換傳輸技術。

在實際應用網絡中，人們為了信息分析、信息安全以及交換的目的，總是要在中間節點進行某種形式的數據處理，而傳統的路由方案并不支持這一需求。2000年，香港中文大學蔡寧、李碩彥和楊偉豪教授首次提出了網絡編碼[1]，推翻了原有路由機制單一復制轉發的傳輸方式，并從理論上分析和驗證了它對通信系統的影響。特別是在無線通信網絡中，基于無線信道的廣播特性，利用相鄰節點間的協作對傳輸數據進行網絡編碼操作，可以在一定程度上節約無線資源[2]；當網絡部分節點或鏈路失效時采用隨機線性網絡編碼[3]，可以在目的節點仍能恢復原始數據，增強網絡的容錯性和魯棒性等。

在下一代移動通信網中，IMT-Advanced系統設計的峰值傳輸速率高達100 Mbit/s～1 Gbit/s，小區平均頻譜效率下行高于3 bit/s·Hz-1,上行高于2 bit/s·Hz-1,小區邊緣頻譜效率不小于1 bit/s·Hz-1,其用戶數量也將比以往的系統高一個數量級。網絡編碼作為下一代移動通信的關鍵技術之一，在一定程度上可節省網絡的資源消耗，提高頻譜資源利用率，并在有限的頻譜資源中盡可能多地傳輸數據，可以增加信道的傳輸容量，完全滿足LTE-A中的技術要求。與此同時，網絡編碼作為未來無線網絡的“綠色技術”之一，在差錯控制[4]、節能[5]、干擾消除、提高網絡安全[6]等方面起著至關重要的作用。

綜上所述，網絡編碼的應用給現有的網絡帶來了革命性的變革，它可以改善網絡性能，改變網絡結構和協議。目前，國內外很多學者和科研機構都致力于網絡編碼的研究工作，從網絡信息流的研究一直到與MIMO技術以及協同技術的結合，不斷地促進了網絡信息論的發展。本文跟蹤了網絡編碼的發展歷程，并根據未來通信網復雜的無線環境評述了今后該領域的研究方向。

2 網絡編碼基本原理及構造方案

網絡編碼的基本特征是在網絡層對傳輸的信息進行智能化處理，包括采用各種編碼策略。因此，當給定一個組播網絡時，如何設計網絡編碼方案實現最大流傳輸是一個很重要的問題[2-4]。目前最常用的是隨機線性網絡編碼策略。

2.1 網絡編碼基本原理

本文將以“蝶型網絡[7]”模型為例，具體闡述網絡編碼的基本原理。如圖1所示，設每一個有向鏈路的容量為1 bit。根據“最大流最小切割定理[1]”，網絡傳輸的最大流為2。圖1(a)表示的是傳統的路由傳輸方案，節點c只有存儲和轉發功能，只能在2 s內依次把信息b1和b2轉發給匯點。圖1(b)表示的是網絡編碼方法，節點c收到b1和b2后進行異或編碼[8]，將b=b1⊕b2傳送到匯點，在接受節點通過異或的加減法定理譯出b1和b2。圖1(a)中從源s到接收節點的最大信息傳輸速率為1.5 bit/s；圖1(b)中,接收節點可以同時恢復出信息b1和b2，其信息流速率為2 bit/s，帶寬利用率提高了33%。網絡編碼使信息在傳輸過程中均勻分布于整個網絡，有效解決了網絡擁塞和傳輸瓶頸問題，從而使網絡負載得到均衡。此外，網絡編碼可以實現基于接收者的組播鏈路失效恢復，從而預防網絡鏈接失效對網絡鏈接的影響，提高網絡的魯棒性[9]。而網絡編碼的吞吐量是傳統編碼的Ωlg|V|倍，其中Ω是信源符號的全空間，|V|表示通信網絡中節點個數[9-10]。由此可知，中間節點c所采用的編碼策略屬于線性網絡編碼方案。另外，在c點還可以采用非線性網絡編碼和隨機線性網絡編碼等方案。

(a)傳統路由傳輸方案

(b)網絡編碼方法

2.2 (非)線性網絡編碼

線性網絡編碼[11]的中心思想是在中間節點對來自不同鏈路的信息流進行線性組合后再轉發，將節點傳送信息線性映射到一個有限域內，實現最大流的信息傳輸[12]。在無環網絡中，通過線性編碼組播傳輸原始數據包的線性組合向量，并在目的節點提取更新編碼系數譯出原始信息。對于有環網絡[13]，引入時間延遲指標，將有環網絡轉化成等價的無環網絡進行編碼。典型的編碼算法有貪婪算法[11]、指數時間算法[14]、多項式時間算法[15]等。相對而言，非線性網絡編碼可以在某些信道或網絡中彌補線性網絡編碼的不足[16]，如在有噪信道中可以有效降低失真，提供更好的網絡性能[17]。

2.3 隨機網絡編碼

隨機網絡編碼[12]就是每個網絡節點獨立地隨機選取一種映射方式將自己接收到的輸入信息映射到相應的輸出鏈路上。通常情況下，該映射方式選取線性映射，即在一個有限域Fq內每個輸入信息流選取相應的加權系數。用此方案進行組播數據時，目的節點可以成功譯碼的概率至少為(1-d/q)η，特別是網絡規模較大時，其中d為接收節點數，η是轉接輸入信號的隨機組合的鏈路數。目前它已被廣泛用于多播[18]、中繼[19]等網絡中，用來提高網絡的傳輸容量、系統吞吐量等性能。此外，還有幾種實用性相對較差的編碼策略，比如代數法[14]、信息流法[20]以及確定性網絡編碼[21]，由于其可擴展性差、運算復雜度高等因素，在網絡編碼中很少被用到。

傳統的網絡編碼中，使用機會調度策略，充分利用延遲時間傳輸數據實現信息流的“匹配”，從而提高網絡吞吐量[12,22]，但是它并不能實現節點的最大吞吐量。在無線網絡中，由于信道的衰落、噪聲、干擾等特性，傳統的編碼方案在分集增益、誤碼率以及系統吞吐量等方面顯示出了它的不足。

3 聯合網絡編碼

本節將從物理層的角度對網絡編碼進行分析，并將其與信道的編譯碼技術[23-29]、糾錯技術[30-31]以及各種傳輸技術相結合，更好地提高系統的吞吐量、數據傳輸速率，并有效地降低誤碼率以及編譯碼的復雜度和時延。

3.1 網絡編碼與信道編譯碼的聯合設計特性

網絡編碼同信道編譯碼結合的基本思想就是利用網絡編碼的冗余支持信道編碼從而獲得好的抗噪聲性能和誤碼率，達到最大信道容量，并充分利用中繼傳輸的額外冗余度獲得分集增益[26]。基于Turbo[28]碼和低密度奇偶校驗碼(LDPC)[32]的聯合編碼被廣泛研究，并在多址中繼信道[26]、時分復用雙向中繼信道[27]以及BSC和加性高斯白噪聲信道(AWGN)[25]中與傳統的網絡編碼方案進行了比較，顯示了聯合編碼在能量消耗、判決檢測以及信道容量和誤碼率方面的優勢，有效降低了編碼的復雜度和由信道噪聲帶來的失真。

與分離編碼方案相比，它在中間節點對接收信號分別進行軟檢測估計后再進行軟網絡編碼和軟維特比譯碼，能夠在高速編碼的情況下減少信息損失以保證網絡的信道容量和誤比特率性能。如在AWGN信道[25]中信息流在信道譯碼前進行了組合使得錯誤概率增加，信道容量減小，隨著信噪比的增加而不斷改善，最終近似于傳統的網絡編碼，但是聯合編譯碼的計算復雜度降低了50%。為了降低錯誤概率，在信道編碼階段可以采用卷積碼與H-ARQ[31]結合，在中間節點進行軟結合和檢測，對所接收數據的估計值進行網絡編碼，并廣播到兩個接收節點進行迭代譯碼[27]。

3.2 物理層網絡編碼與信道譯碼的聯合設計

物理層網絡編碼(PNC)[23]主要是針對無線通信系統提出的，它能充分利用無線傳播的信息廣播特性來提高無線網路中的信道容量。無線通信的信息傳輸載體(電磁波)在傳輸過程中會產生干擾而導致信號間的混亂，基于EM信號的相加特性，物理層網絡編碼可以將電磁波信號映射為數據比特流，則干擾就變成了網絡編碼中的算術問題。

在雙向中繼信道中[24]，采用PNC方案并把雙向信道分為多址接入信道和廣播信道。通過多址信道中的映射和線性信道編碼可以分別達到信道容量上限和下限，在信噪比高于5 dB時上下限會重合，與傳統網絡編碼和簡單網絡編碼方案相比物理層網絡編碼的信道容量增益分別為3/2和2。在多跳網絡中，物理層網絡編碼可以分別實現100%和50%的吞吐量增加[23]。

在多址信道中[29]物理層網絡編碼與信道譯碼相結合，利用電磁波的相加特性和Turbo碼與網絡編碼的線性特性直接對網絡編碼的碼字進行估計。如圖2所示，在節點1和3分別進行Turbo編碼和調制，然后再進行相加；而在中間節點進行軟判決檢測得到檢測信號的最大似然比L(*)，再通過Turbo譯碼器得出網絡編碼的估計碼字。與傳統的編碼方案相比，此方案不僅降低了計算的復雜度而且還改善了誤比特率、信道容量和信噪比。此外，在目的節點還可以獲得額外的分集增益，而由于電磁波的相加特性系統的吞吐量也得到了進一步提高。

圖2 物理層網絡編碼與信道編碼聯合設計方案

4 基于MIMO和協作分集技術的網絡編碼

在新一代無線移動通信系統中，面對復雜的無線場景和信道的衰落特性，網絡編碼與無線協作分集技術、MIMO技術相結合，在提高系統吞吐量、信道容量和分集增益等方面具有廣闊的前景。

4.1 基于協作分集技術的網絡編碼

協作分集技術是通過節點間的協作，獲得較大的分集增益，克服無線信道衰落，實現了所謂“虛擬天線陣列”的功能，極大地改善了無線通信系統抗衰落性能，提高了資源效率和系統容量[33]。另外，在協作分集的基礎上進行網絡編碼可以同時獲得分集增益和網絡編碼增益。在考慮只有源節點A和B和目的節點C的模型中，節點A和B互相協作中并將數據包傳輸到目的節點C。發送節點A和B將接收到來自協作節點的信息(中繼信息)，經檢測譯碼后與本地信息相結合(網絡編碼和)。接收節點則根據來自節點A和B中的網絡碼字以及信息的先驗概率進行檢測譯碼，恢復出所需信息[34]。此方案充分利用了網絡資源和分集技術，可獲得相對較低的錯誤概率中斷概率，以及較高的編碼增益，使得數據可以在衰落信道中能夠更好地傳輸。

4.2 基于MIMO的網絡編碼

MIMO技術是利用多個發送和接收天線獲得分集增益，改善信道的多徑衰落特性，提高系統的容量、頻譜利用率以及數據傳輸速率。而網絡編碼(NC)在多徑信道下由于信道的衰落和電磁干擾等，丟包率會很大，這就會導致譯碼器的錯誤譯碼。基于這兩種技術的共同目的和系統的相似性，將網絡編碼和MIMO技術(MIMO-NC)在物理層相結合，通過在不同的包內編碼相同的信息，并利用獲得的冗余度將接收到的能量傳遞給譯碼器，更好地完成檢測譯碼過程，獲得大的信噪比增益，增強系統的魯棒性，降低丟包率和誤比特率。

MIMO-NC方案[35]包括兩個階段：

(1)編碼過程：每個節點將緩存器中的信息單元進行網絡編碼，產生編碼包。這些編碼包是Galois符號序列，通過轉換調制進行發送；

(2)譯碼過程：在接收端將收到的矢量(數據包)存入緩存器并更新和提取相應的編碼系數，最終通過軟譯碼方案恢復出原始信息。

其編譯碼流程如圖3所示，其中x1，x2，x3，…，xp是由源節點傳輸到網絡中的信息單元(IUs)，gnp為編碼系數，{bn,1，bn,2，…，bn,8}是一個Galois符號dn所對應的一個調制后的矢量sn，y1,y2,…,yN是在不同的時間接收端所接收的來自不同信源的編碼包。

圖3 MIMO-NC編譯碼流程圖

為了獲得高于網絡編碼的分集和編碼增益，在編碼階段可以采用兩個網絡編碼器，有兩個生成系數矩陣G1和G2，它們編碼相同的信息，編碼包的頭部存儲編碼系數，且這些編碼包是Galois符號序列，通過轉換和QPSK調制，兩個編碼器產生的符號序列分別作為實部和虛部再通過調制發送出去。高分集增益的獲得是以傳輸速率的降低為代價的。譯碼階段采用自適應MIMO-NC技術，就是為了降低錯誤概率，改善傳輸速率[36]，但復雜度有所增加。

MIMO技術與網絡編碼的結合是一種新型技術，在各種無線傳播環境下，它充分利用網絡編碼提供的冗余度和MIMO技術的高分集增益提高系統性能，為未來的網絡編碼和基于網絡編碼的數據傳輸方面的研究鋪平了道路。

5 網絡編碼的進一步發展方向

網絡編碼作為通信網絡中的信息處理和傳輸理論研究的重大突破，具有重要的理論價值和廣闊的應用前景，已被認為是LTE-A的關鍵技術之一。新一代寬帶無線移動通信網的網絡架構是一個復雜、多元化的架構，這一方面體現在網絡層次/基本構架方面，另一方面也體現在包括復雜的無線場景/傳播環境和混合的無線小區結構等。如何在新的環境下提高系統吞吐量和信道容量，降低傳輸誤碼率等，是目前的研究熱點問題。LTE-A中采用MIMO分集技術，改善信道的特性，抑制衰落，并在物理層通過與網絡編碼的結合改善了系統的傳輸性能。為此，可以在MIMO-NC的基礎上從以下幾個方面進一步研究適合于新一代寬帶無線移動通信網的網絡編碼技術：

(1)結合多輸入多輸出天線，研究不同無線場景/傳播環境研究網絡編碼。充分研究無線場景/傳播環境對網絡中數據流傳輸的影響，研究有效的譯碼算法，特別是研究網絡編碼中最小代價函數問題，從而反演研究低復雜度、低時延的網絡編碼；

(2)研究基于不同無線場景/傳播環境和協作技術的網絡編碼。研究基于MIMO或協作技術的物理層網絡編碼和信道編碼的聯合設計算法和方案，尋求低復雜度、更小代價函數的網絡編碼算法。為了節省傳輸能量的消耗需要對編碼節點以及傳輸路徑選擇，采用最短路徑進行傳輸；

(3)結合無線傳播特性，尤其是考慮無線傳播過程的遮擋物而引起的信道特性的變化，從而導致網絡容量的變化。考慮將無線信道中的障礙物等作為無線傳輸中的一個節點，利用網絡最大流定理，進行網絡編碼研究，特別是研究這些“節點”對傳輸過程中的數據速率的影響，同時引入分布式編碼技術，研究網絡信道容量最大化問題，從而有效利用網絡帶寬，提高系統吞吐量等。

6 結束語

網絡編碼作為一項新興技術，從理論到實際應用都還處在不斷完善和豐富的階段。本文重點討論了網絡編碼的優缺點和發展現狀。隨著更多學者對該領域的深入研究，網絡編碼技術在新一代無線移動通信網中將起到關鍵性的作用。上述問題的深入研究必將促進網絡編碼理論和應用的發展，從而推動網絡信息論乃至整個通信網絡的發展。

參考文獻：

[1] Ahlswede R, Cai N, Li S-Y, et al. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46(4):1024-1216.

[2] Widmer J,Fragouli C, Le Boudec,et al. Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding[C]//Proceedings of Workshop on Network Coding,Theory,and Application(NetCod 2005). Riva del Garda,Itlay:[s.n.],2005.

[3] Ho Tracy, Medard M,Ralf K,et al. A Random Linear Network Coding Approach to Multicast [J]. IEEE Transactions on Information Theory, 2006, 52(10):4413-4430.

[4] Cai Ning, Yeung R W. Network Coding and Error Correction[C]//Proceedings of Workshop on Information Theory.[S.l.]:IEEE,2002: 119-122.

[5] Wang Suyu, Gao Xuejuan,Zhuo Li. Survey of network coding and its benefits in energy saving over wireless sensor networks [C] //Proceedings of 7th International Conference on Information, Communications and Signal Processing(ICICS 2009).[S.l.]:IEEE,2009:1-5.

[6] Cai Ning, Yeung R W. Secure Network Coding[C]//Proceedings of IEEE International Symposium on Information Theory(ISIT2002).Lausanne,Switzerland:IEEE,2002:323.

[7] Yang Min,Yang Yuanyuan. A Linear Inter-Session Network Coding Scheme for Multicast [C] //Proceedings of the 7th IEEE International Symposium on Network Computing and Applications.[S.l.]:IEEE,2008:117-184.

[8] Sachin Katti, Hariharan Rahul, Wenjun Hu, et al. XORs in The Air: Practical Wireless Network Coding [J]. IEEE/ACM Transactions on Networking,2008,16(3):497-510.

[9] Ho T,Karger D,Medard M,et a1. The benefits of coding over routing in a randomized setting[C]//Proceedings of IEEE International Symposium on Information Theory (ISIT '04). Chicago, IL:IEEE,2003:442-447.

[10] Keshavarz-Haddadt A,Riedi R.Bounds on the Benefit of Network Coding:Throughput and Energy Saving in Wireless Networks[C]//Proceedings of the 27th Conference on Computer Communications.Phoenix,AZ:IEEE,2008:376-384.

[11] Li S-Y R, Yeung R W,Cai N. Linear Network Coding [J]. IEEE Transactions on Information Theory,2003,49(2):371-381.

[12] 樊平毅. 網絡信息論 [M]. 北京：清華大學出版社，2009:109-146.

FAN Ping-yi.Network Information Theory[M].Beijing:Tsinghua University Press,2009: 109-146.(in Chinese)

[13] Wang Liang, Huang Jiaqing,Li Hui. Applying Network Coding to Cyclic Networks [C]// Proceedings of the 28th IEEE International Conference on Computer Communications Workshops. NJ, USA:IEEE,2009:321-322.

[14] Koeter R,Medard M. An Algebraic Approach to Network Coding [J].IEEE/ACM Transactions on Networking,2003,11(5):782-795.

[15] Sanders P,Egner S,Tolhuizen L. Polynomial time algorithms for network information flow[C]//Proceedings of 15th Annual ACM Symposium on Parallel Algorithms and Architectures.San Diego,California,USA:ACM,2003:286-294.

[16] Dougherty R, Freiling C, Zeger K. Insufficiency of linear coding in network information flow [J].IEEE Transactions on Information Theory, 2005, 5l(8):2745-2759.

[17] Joda R， Lahouti F. Nonlinear network code design for the multiple access relay channel [C]//Proceedings of the 24th Biennial Symposium on Communications.Kingston,Ontario,Canada:IEEE,2008:13-16.

[18] Dong Nguyen,Tuan Tran, Thinh Nguyen,et al. Wireless Broadcasting Using Network Coding [J]. IEEE Transactions on Vehicular Technology, 2009,58(2):914-925.

[19] Pu Wei,Lu Chong,Li Shi-peng, et al. Continuous Network Coding in Wireless Relay Networks [C]//Proceedings of the 27th Conference on Computer Communications(IEEE INFOCOM). Phoenix, AZ:IEEE,2008:1526-1534.

[20] Fragouli C,Soljanin E. Information flow decomposition for network coding [J].IEEE Transactions on Information Theory,2006,52(3):829-848.

[21] Fragouli C,Soljanin E. Decentralized network coding [C]//Proceedings of IEEE Information Theory Workshop.[S.l.]:IEEE,2004: 310-314.

[22] Fasolo E,Rossi M,Widmer J,et al. On MAC Scheduling and Packet Combination Strategies for Practical Random Network Coding [C]//Proceedings of IEEE International Conference on Communications. Glasgow, UK:IEEE,2007:3582-3589.

[23] Zhang S, Liew S, Lam P. Physical layer network coding[C]//Proceedings of ACM International Conference on Mobile Computing and Networking(MobiCom’06).Los Angeles,CA,USA:ACM,2006: 358-365.

[24] Popovski P,Yomo H. Physical Network Coding in Two-Way Wireless Relay Channels[C]//Proceedings of IEEE International Conference on Communications.[S.l.]:IEEE,2007: 707-712.

[25] Zhang Shengli,Zhu Yu，Liew Soung-Chang，et al. Joint Design of Network Coding and Channel Decoding for Wireless Network[C]//Proceedings of IEEE Wireless Communications and Networking Conference.[S.l.]:IEEE,2007: 779-784.

[26] Hausl C， Dupraz P. Joint Network-Channel Coding for the Multiple-Access Relay Channel[C]//Proceedings of the 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communication and Networks.[S.l.]:IEEE,2006: 817-822.

[27] Hausl C,Hagenauer J. Iterative Network and Channel Decoding for the Two-Way Relay Channel[C]//Proceedings of IEEE International Conference on Communications. [S.l.]:IEEE,2006: 1568-1573.

[28] Zhao B,Valenti M C. Distributed turbo coded diversity for the relay channel [J]. Electronic Letters, 2003, 39(10):786-787.

[29] Ao Zhan,Chen He. Joint Design of Channel Coding and Physical Network Coding for Wireless Networks[C]//Proceedings of International Conference on Neural Networks and Signal Processing. [S.l.]:IEEE,2008:512-516.

[30] Silva D,Kschischang F R.Adversarial Error Correction for Network Coding:Models and Metrics[C]// Proceedings of the 46th Annual Allerton Conference on Communication,Control,and Computing.[S.l.]:IEEE,2008:1246-1253.

[31] Dong Nguyen, Tuan Tran, Bose B, et al. Hybrid ARQ-Random Network Coding for Wireless Media Streaming[C]// Proceedings of the 2th International Conference on Communications and Electronics (ICCE). [S.l.]:IEEE,2008:115-120.

[32] 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.

[33] Hunter T E,Nosratinia A. Diversity through Coded Cooperation [J].IEEE Transactions on Wireless Communications,2006,5(2):283-289.

[34] Lei Xiao,Fuja T,Kliewer J,et al. A Network Coding Approach to Cooperative Diversity[J]. IEEE Transaction on Information Theory, 2007,53(10):3714-3722.

[35] Fasolo E,Rossetto F,Zorzi M. Network Coding meets MIMO[C]//Proceedings of the Fourth Workshop on Network Coding,Theory and Applications.[S.l.]:IEEE,2008:1-6.

[36] Fasolo E， Rossetto F, Zorzi M. On encoding and rate adaptation for MIMO-NC [C]// Proceedings of the 3rd International Symposium on Communications, Control, and Signal Processing. [S.l.]:IEEE,2008: 741-746.