無線通信中的網絡編碼技術*

王亨友，彭木根，王文博，鄔賀銓

（北京郵電大學 北京 100876）

無線通信中的網絡編碼技術*

王亨友，彭木根，王文博，鄔賀銓

（北京郵電大學 北京 100876）

網絡編碼是一種提高網絡吞吐量和性能的新技術，預計將成為未來網絡的一項關鍵技術。本文概述了無線網絡中的網絡編碼技術，無線網絡被認為是網絡編碼最可能得到應用的領域之一，網絡編碼技術使無線媒質的廣播屬性可以得到充分利用，無線網絡和傳感器網絡為網絡編碼的應用提供了巨大的機會。本文結合不同無線場景介紹了網絡編碼的各種編碼方法，包括傳統的網絡編碼、物理層網絡編碼、模擬網絡編碼以及復數域網絡編碼，并對未來發展給出了展望。

無線網絡編碼；數字網絡編碼；物理層網絡編碼；有限域網絡編碼；復數域網絡編碼

[1]首次引入了網絡編碼概念，用于衛星通信網絡，在參考文獻[2]中得到完善的發展，并首次闡述了網絡編碼相對于傳統的存儲轉發方式的優勢，這就駁斥了之前的觀點，即在中間節點只需作數據復制而沒有必要進行數據處理，參考文獻[3,4]證明了網絡編碼的構造可以分別通過線性組合和有限域來實現。

參考文獻[2]和[3]研究了多播網絡的網絡容量以及涉及割集的容量，描述了多播網絡的可容許編碼速率區，證明了網絡的最大吞吐量可以通過使用編碼來實現。參考文獻[2]發展的卷積碼屬于非線性網絡編碼，適用于多源情況，但是這種非線性碼的復雜度太大。針對單源的多播網絡，Li等人在參考文獻[3]深入研究了線性網絡編碼。線性編碼是所有最簡單的編碼方案之一，在線性編碼中，節點的編碼是采用傳入數據的線性組合，即，線性編碼將一組數據看作某一特定基本域上的一個向量，且允許一個節點在將一個向量傳遞之前對向量應用線性變換，證明了每一接收機的最大流（上限）可以實現。作者嚴謹地闡述了這種多播問題并證明了線性編碼足以實現最優的多播容量，即從源節點到每一接收節點的最大流。

參考文獻[4]中，Koetter等人深入研究了網絡容量問題，指出網絡編碼是實現網絡容量的重要組成部分，以Li等人對于多播網絡容量的研究為基礎，Koetter等人利用代數方法，將一個給定的網絡信息流問題和一個有限域閉包上的代數變量之間建立起直接的連接，來研究網絡及其容量，將網絡編碼擴展到任意網絡和魯棒性組網問題。對于限定為使用線性網絡編碼的網絡，發現了一個給定網絡上的任意連接的可行性之必要和充分條件，還研究了非各態歷經鏈路失敗的網絡恢復問題，針對多播問題，證明了存在能夠提供最大魯棒性網絡的編碼方法，且無需先于所討論的失敗模式調整網絡，推導出的結果既適用于無時延網絡，也適用于有時延網絡。

由于參考文獻[2]和[3]的工作包含代數的成分，其中前者是卷積碼，后者是線性編碼，因此這種與代數幾何建立起連接的概念，就為直接利用已經發展良好的數學學科之強大理論打開了大門。對于那些限定在使用線性碼的網絡，參考文獻[4]找到了在一個給定網絡上實現任意給定的連接，所需要的必要和充分的條件。使用該構架證明了一個網絡上的多播連接情形呈現出一種非常特殊的結構，使得以多項式時間的驗證成為可行，而且，類似于參考文獻[3]和[4]的結果都表明，線性編碼足以實現任意可行的多播連接。Jaggi等人在參考文獻[5]證明了編碼和解碼能夠以多項式時間實現，參考文獻[6]中，Ho等人提出了隨機網絡碼，其編碼系數的選擇是隨機的。

當網絡編碼用于信息傳輸，其物理實現將引起信道上的傳輸時延和節點上的處理時延，而目前節點處理是網絡上信息傳送總時延的決定因素，這就要求網絡編碼的編碼機制應以簡單和快速的電路來實現，因此，采用線性映射的網絡編碼方案特別受到關注。

以上這些最初的網絡編碼的研究主要針對于無損耗的有線網絡中多播通信的路由問題，而且基本是抽象出無時延的網絡模型，但是，這些基礎性的工作，卻為后來的其他應用的研究奠定了堅實的理論基礎。

鑒于其普遍適用性和巨大應用潛力，網絡編碼理論已經被引入多個研究領域，諸如信息和編碼理論、網絡、網絡恢復、網絡監控、內容分發、分布式存儲、組合數學、交換、無線通信、ad hoc網、復雜度理論、安全及密碼學和矩陣理論（見參考文獻[3]和[7]），且網絡編碼新的應用仍在繼續出現。本文主要面向網絡編碼在無線通信中的應用，介紹其理論和技術發展。

將網絡編碼的思想應用到無線網絡環境已經引起了大量的研究興趣，無線網絡編碼已經成為發展最快的研究領域之一，此處簡要概述一些最初的標志性的結論。將網絡編碼與無線通信環境的廣播特性結合在一起以利用后者的優勢，進行這一工作的代表性人物如Wu等人[8]和 Fragouli等人[9]；參考文獻[10]中，Lun等人提出了能量最小化的LP方程；參考文獻[11]中，Eryilmaz等人研究了無線網絡的合理性和時延問題；參考文獻[12]中Zhang等人提出了物理層網絡編碼；參考文獻[13]中Katti等人設計了COPE協議；Dimakis等人在參考文獻 [14]中和Fragouli等人在參考文獻[15]中都做了將網絡編碼應用于傳感器網絡的研究；在參考文獻[16]中Petrovic等人將網絡編碼應用于傳感器網絡中研究非調諧網絡，類似的思想近期已經被應用于傳送網（transportation network）。將無線網絡編碼用作信息論工具的研究工作也得到了發展，例如，在參考文獻[17]中Gowaikar等人研究了無線擦除網絡（wireless erasure network）的容量，Ratnakar等人在參考文獻[18]中研究了確定性信道上的廣播特性，而Avestimehr等人在參考文獻[19，20]中研究了普通確定性信道網絡中廣播和干擾的問題，在參考文獻 [21]中，Sagduyu和Ephremides研究了跨層設計情況下的網絡編碼問題。

本文結構如下：第二部分通過一個簡單的雙向無線通信環境，引入網絡編碼的模型，第三部分介紹各種無線網絡環境主流無線網絡編碼技術的編碼方案及其應用，最后，給出一個結論性的總結和提出面臨的挑戰。

2 系統模型舉例

考慮一個簡單的3節點的無線雙向信息交換的例子，如圖 1所示，Alice（A）和 Bob（B）之間希望互傳信息，其中的傳輸距離超出了發射機的覆蓋范圍，所以不能直接通信，而需要通過一個中繼器（或者稱之為路由器（R））。在傳統的設計中，A傳送包到R，R轉發給B，B傳送包到R，R轉發給A，整個過程需要4個時隙，如圖1（a）所示。

而利用網絡編碼的方法，如參考文獻[13]中所做的那樣，A和B可以分別傳送各自的包給R，R將其做XOR運算，然后以廣播的形式將此編碼過的包A茌B同時發送給A和B，A利用自己的包與編碼的包進行XOR運算，可以恢復出B的包，即A茌B茌A=B；B也以同樣的方式恢復出A發來的包，這個過程利用了網絡中的冗余來壓縮信息，在一個時隙中傳送兩個包，總共以3個時隙完成通信過程，節省了一個時隙，提高了吞吐量，如圖1（b）所示。

Katti等人在參考文獻[13]進一步發展了機會網絡編碼的思想，提高了網絡吞吐量，然而這類傳統網絡編碼的編碼運算是在數字比特流級別完成的，為了進一步減少時隙和提高吞吐量，充分利用無線媒質的廣播屬性，參考文獻[12]和參考文獻[22]分別提出了物理層網絡編碼和模擬網絡編碼的概念仍以雙向通信的情景為例，如圖1（c）所示，A和B同時傳送信號到R，R接收到的將是A和B的混合信號，由于R不能提取出A和B的單獨信息，所以不能像傳統網絡編碼那樣對其進行比特級編碼，因此R僅僅是起到一個中繼的作用，將混合信號轉發給A和B。在物理層網絡編碼方法中，針對節點處具體的調制方式，可以建立某種映射機制，其編碼運算發生在信號級，利用這種映射機制以及節點A和B處各自的信息，在節點A和B解出對方節點發來的信息。而在模擬網絡編碼中，A和B同時向R傳輸信號，R放大接收到的受到互相干擾的混合信號，并廣播的形式發射出去，A接收到信號以后，從中減去已知的自己的信號，從而恢復出B傳輸來的信號，B對接收到的信號做類似的處理，整個過程只需要兩個時隙，從而獲得了更高的吞吐量。具體的過程下面的部分將做更詳細的說明。

圖1的雙向3節點簡單模型可以推廣到各種其他復雜的情形。參考文獻[23]研究了4節點雙向中繼網絡，如何能夠最優地中繼信息的協議和算法，提出了一種有效地中繼信息的中繼協議。

圖1 3節點的無線雙向信息交換的例子

3 技術發展和應用

無線網絡遭受一系列特有的問題，諸如低吞吐量、盲點以及對于移動性支持的不充分等；但是，其另外一些特征諸如媒質的廣播屬性、空間分集以及大量的數據冗余等，又為解決以上問題提出新的設計思想提供了機會。將網絡編碼應用于無線網絡，就是基于這樣的想法。參考文獻[24]對于將網絡編碼用于無線網絡之統一設計范例進行了探討，嘗試通過描述如何處理吞吐量、可靠性、移動性等問題，還討論了將這樣一種設計整合到網絡協議棧的實際挑戰。

在無線網絡中，當來自不同發射機的信號自動地在無線信道中合成，無線信道為物理層網絡編碼提供了完美的媒質。

無線網絡區別于有線網絡的主要特征是傳輸媒質的共享和傳輸信道的時變特性。對于某一節點來說，通過提高發射功率，將最終可以得到足夠大的信號噪聲比，使得信號可以傳送到網絡中的其他每一節點，但是與此同時又會對其他節點產生很明顯的干擾，而且，由于諸如衰落或者節點移動性的原因，信道狀況將隨時間而改變，最后，無線網絡的資源諸如計算功率或者電池壽命往往是有限的（見參考文獻[25]）。

現有的多數網絡協議利用無線媒質建立起點對點的連接，但是并沒有利用無線傳輸的廣播特性，網絡設計已經主要致力于運行的簡單性和可擴展性；另一方面，近期的信息論諸如中繼網絡的研究表明，通過使用適合的編碼方案進行廣播，物理資源可以獲得顯著的節省，然而，所提出的編碼方案諸如隨機散列法（random hashing）等的編碼復雜度太高，而通常這些方案不能夠很好地根據網絡規模進行擴展（見參考文獻[25]）。

從無線系統的當前技術水平面向實際的基于信息論解決方法的研究過程中，將網絡編碼概念與無線媒質的廣播特性相結合，是一個富有意義的技術步驟。實際上，運用代數的方法疊加信號就是散列法的一種變形，這種方法能夠利用無線媒質的廣播屬性優勢，而且在實際實現中也足夠簡單可行。某種意義上說，無線網絡編碼與網絡信息理論和網絡算法具有很大的重疊。從實際應用的角度，無線ad hoc和無線傳感器網絡深受期待而成為首批應用網絡編碼技術的領域之一，原因是兩者的網絡環境下其協議嚴格性要求較為寬松。

為了說明無線網絡當應用網絡編碼技術所帶來的優勢，可以首先考慮共享無線媒質的廣播屬性所能提供的帶寬、傳輸功率、時延，以及對于環境動態改變的適應性。基于諸如此類的優勢，下面的部分將討論一系列業務模式和網絡配置示例。MIT的COPE結論表明，即使當編碼運算限定在遵循一些額外限制的簡單二進制加法，仍然會在吞吐量和MAC層協議的效率等方面獲得增益。

傳統的網絡編碼將接收機端的干擾視為對于系統性能的有害因子，而依靠合適的調度廣播傳輸來減低干擾，這種機制將會在可實現速率方面引起顯著的損耗。參考文獻[12]所提出的物理層網絡編碼是第一次試圖解決這一問題的工作，后來，出現了一種捕捉無線網絡中的信號間交互作用的線性確定性模型，研究表明對于這樣一種模型，能夠實現信息論最大流最小割。

3.1 無線ad hoc網絡的能量問題

無線ad hoc和傳感器網絡為網絡編碼的應用提供了大量的機會，同時它也面臨大量的問題。

在一個網絡中，傳輸一個信息比特所需的最小能量可用以描述最經濟的通信方式，參考文獻[8]中的研究證明了在一個分層無線網絡模型下，一個移動ad hoc網絡多播的最小每比特能量能夠通過解線性規劃問題來解決，最小每比特能量能夠通過利用網絡編碼的方法來得到，與傳統的路由求解方法相比，網絡編碼不僅潛在地可實現更低的每比特能量，還能夠在多項式時間級別發現最優解，這明顯優于構建最小能量多播樹方法求解最優路由解，后者是一種NP hard問題。研究還表明，最小能量多播問題等價于線性的基于邊定價的最小成本問題，這里的價格是對應的物理層廣播鏈路之每比特能量，該參考文獻還研究了使用路由方法的最小能量多播問題。由于定價方案的線性特征，路由選擇之最小每比特能量的實現是通過使用一個單樹，研究給出了利用一個單樹選路的可容許速率區域的表征，而多播路由選擇之最小每比特能量是通過求解一個整數線性規劃來得到。而根據更早期的文獻中Steiner樹的研究結果證明，該整數線性規劃問題的條件放松，能夠理解為使用網絡編碼對于最小能量多播的優化。總之，該文給出了應用網絡編碼和路由進行最小能量多播的一種統一研究。

參考文獻[9]研究了無線ad hoc網絡中利用網絡編碼解決能量效率的問題，研究的情形是網絡中的每一節點都試圖作為向其他節點傳輸信息的源節點。能量效率直接影響電池壽命，它是無線網絡的一個關鍵設計參數。他們提出了一種針對這種情形應用網絡編碼的可實現方法，進行了詳細的理論分析，并籍此提出了一種實際的完全分布式的方法應用于實際的無線ad hoc網絡環境，解決了一些實際問題諸如如何設置轉發因子、如何管理網絡編碼的生成以及傳輸距離的影響，研究中使用了理論分析和包級仿真（packet level simulation）。

3.2 無線傳感器網絡

參考文獻[15]將網絡編碼應用于傳感器網絡的研究，研究表明在網絡拓撲動態變化的無線網絡環境下，網絡編碼具有明顯的增益，其研究限于分布式算法且沒有利用關于網絡環境的反饋信息。作者考慮了動態拓撲的幾種情形，包括廣播信息到網絡的所有節點和收集傳感器測試數據，研究表明在很多此類的情形下，在某些簡化假設下，該問題理論上等價于息票托管問題 （coupon collector problem）的簡單變種，因此，通過應用網絡編碼獲得的增益因子是lg(n)，這里n是節點數，該增益在該作者的另外一篇文章中稱作能量效率。此項研究給出了實際條件下的仿真結果來支持上述結論。

無線傳感器網絡的實現和布網要求超低成本和低功率節點，盡管節點的數字子系統仍然遵循摩爾定律，但是有關模擬組件的性能則沒有這種趨勢。參考文獻[16]提出了一種將數字和模擬組件（包括本地振蕩器）完全集成的架構，能夠顯著地降低節點的成本、尺寸和總功耗。盡管這樣的一個基本架構不能提供可靠的標準設計的調整，但是已經證明通過使用隨機網絡編碼，這類節點的一個密集網絡能夠實現吞吐量線性于通信系統中可用信道的數量；而且可以證明，非調諧網絡（這里非調諧網絡是指每一個傳感器從一個有限的頻率集合中，隨機選擇一個頻率用以發射）與一個完全協調的可調網絡的可實現吞吐量之比近似于1/e。他們的研究利用網絡編碼來改變這樣一個事實即吞吐量等于一個圖的最大流是可實現的，即使是在無法事先知道網絡拓撲的情況下，然而，此處的挑戰在于如何發現對應于該網絡的隨機圖的最大流。

3.3 機會網絡編碼

3.3.1 COPE

Katti等人在參考文獻[13]提出了一種稱作COPE的架構，這是用于無線mesh網的一種新架構。除了轉發包以外，路由器將來自不同源節點的包進行混合（例如進行編碼），用以每一次傳輸的信息內容。這種在中間節點的處理提高了網絡吞吐量，而設計就是基于網絡編碼理論的。之前的網絡編碼研究主要偏于理論且多集中于研究多播業務，COPE的目標是在理論和實際應用之間架起一座橋梁，研究了更普遍的單播業務、動態和突發流，以及在當前網絡協議棧下融合加入網絡編碼的實際問題，設計了一個20節點的無線網絡，對無線網絡編碼的首次測試床測試結果進行了討論和性能評估，結果顯示COPE顯著地提高了網絡吞吐量，一個3節點測試床的初步的試驗結果表明，802.11 mesh網絡中，相對于傳統存儲轉發方案，COPE獲得的是幾乎3倍的吞吐量；而由于業務模式、擁塞控制水平和傳輸協議的不同，吞吐量的增益從幾個百分點到幾十個百分點不等。

COPE將機會算法（opportunistic algorithm）運用到網絡編碼中，每一節點監聽無線媒質，借以獲取其鄰近各節點的狀態，檢測編碼機會，一旦其接收者能夠解碼，則該節點進行編碼。COPE所處理的情形是，需要提供多個單播業務的無線mesh網，而且沒有網絡拓撲或者業務模式的中央控制信息。COPE的基本思想就是網絡編碼處理能夠帶來增益的同時，網絡節點仍然可以識別和利用機會。

3.3.2 MORE

COPE解決的是單播問題，而單播問題是WMN的首要和重要業務；但是由于COPE是一種流間（inter-flow）網絡編碼協議，不能適用于全向業務，不能解決盲點（dead spot）問題。相反，另外一種方案MORE是參考文獻[26]提出的一種流內（intra-flow）網絡編碼協議，其作者將機會路由和網絡編碼融合為一個整體的協議，獲得了顯著的性能增益。

COPE稱作流間網絡編碼是因為編碼過程作用在其上的各個包在它們的下一跳是不同的，所以也就來自不同的流；而MORE稱之為流內網絡編碼是因為路由器所結合的包都流向相同的目標節點參考。MORE應用了3種技術來產生足夠的編碼，以保證路由器能夠很容易地支持高速率，這3種技術是：只對新包編碼；對碼向量編碼；預編碼。詳細的描述見參考文獻[26]。

機會路由（opportunistic routing）技術是為了在有損無線鏈路環境下實現高吞吐量而提出的，之前的機會路由協議ExOR，將和路由和MAC層聯系在一起，使得路由器跟媒質的接入必須要有嚴格的調度機制。盡管調度機制可以分配機會增益 （opportunistic gain），但它將丟失掉802.11 MAC層的一些內在的特征，例如，它抑制了空間重用，從而不能充分利用無線媒質的特征；它還消除了分層抽象，使得協議不易于擴展諸如像多播一類的可選業務類型。

MORE是一種獨立于MAC的機會路由協議，其在將包轉發之前隨機地混合包，這種隨機性操作保證了監聽到相同傳輸的路由器不必轉發同樣的包，因此MORE不需要專門的調度機器來協調路由器，從而可以直接運行于801.11的頂端。一個20節點的無線測試床上的實驗結果顯示，MORE的平均單播吞吐量高于ExOR 22%，而當具有空間重用機會時，增益更是增大到了45%；對于多播傳輸的情況，MORE的增益隨目標節點數量的增加而增加，將高于ExOR協議35%～200%。

3.3.3 noCoCo

Scheuermann等人在參考文獻[27]的工作比COPE又跨出了一步，研究了如何以一種更確定的方式構造編碼機會，而同時仍然保留實際意義。他們提出一種跨層方案稱作 noCoCo（near-optimal coordinated coding，近最優協作編碼）方案，該方案將每一跳包調度、網絡編碼和擁塞控制整合為一。noCoCo的主要想法是，在COPE中當有自然出現的編碼機會時進行編碼處理，而傳輸的等級能夠顯著地影響編碼機會的獲取，從而影響編碼增益。利用無線傳輸的路徑分集和廣播特性，作者提出一種有效的多徑路由協議，稱之為 MC2（multipath code casting，多徑編碼傳播），這種設計是基于網絡編碼，無需像先前的機會路由協議那樣需要節點間的協作；而且，這種協議提供了一種統一的架構來處理多徑和非可靠性傳播路徑情形下的數據傳輸。

3.3.4 AdpNC

在參考文獻[28]中，Karande等人研究了當包因遭到破壞而導致的比特錯誤情形下應用網絡編碼的問題。其基本思想是，某些預先設計一定的交換規則，通過這些規則，中繼節點能夠確定在某些特定的時刻，是否應用網絡編碼。針對雙向中繼網絡的信息交換問題，作者提出了一種系統化優化方法來設計一種自適應網絡編碼（AptNC）方案，以更有效地交換互相獨立的信息。其中研究了在中間節點上應用最少量的處理網絡模型，此時網絡編碼函數的效率將依賴于包中觀察到的誤比特率（BER），因此在時變信道條件下，網絡編碼需要進行調整以符合與包所關聯的信道狀態。在該方案下，中間節點對于包的中繼是否應用網絡編碼依賴于接收到的包的受破壞程度，而應用相對應的預先設計的交換規則。對于從802.11b和802.15.4演繹出來的信道模型所做的性能評價顯示，AptNC具有比傳統的轉發和網絡編碼方案非常顯著的性能提高。

3.4 干擾利用的網絡編碼

3.4.1 物理層網絡編碼

Zhang等人[12]提出了一種物理層網絡編碼（physical layer network coding，PNC），研究了白高斯噪聲（AWGN）雙向中繼信道下，將疊加的電磁信號映射為簡單的有限域（2n）上的數字比特流的加性運算。Zhang等人研究了雙向中繼信道中兩個節點間的雙向傳輸，兩節點中間有一個中繼節點。傳統的網絡編碼設法避免在同一時間進行多個傳輸以防止干擾，與傳統網絡編碼方案將干擾作為負面因素處理而刻意避免所不同的是，Zhang等人的工作嘗試將干擾加以利用，以提高吞吐量性能，他們將網絡編碼概念應用于物理層，從而使得無線自組織網（wireless ad hoc）中無線傳輸的廣播特性真正成為了提高容量的一個優勢。通常在傳統的網絡編碼中，編碼運算只發生在比特級別，應用于那些已經正確接收的比特；與之相反，PNC將干擾變為編碼運算的一個組成部分，它是通過在節點間協調傳輸，并將電磁信號的疊加映射為GF(2n)域上的數字比特流的加法。參考文獻[12]中的結果顯示，與傳統的轉發機制和直接的網絡編碼相比，當應用PNC，一個雙向中繼信道的容量分別增加100%和50%。

3.4.2 模擬網絡編碼

之前的多數網絡編碼研究工作，其編碼的線性組合都是作用在有限域上，參考文獻[12]所做的工作是第一次將網絡編碼應用于物理層，而Katti等人則在參考文獻[22]引入了模擬網絡編碼（analog network coding，AlgNC）的概念，之所以稱作模擬網絡編碼是因為混合的是信號而不是比特。AlgNC同樣把干擾作為有益因素，設法有選擇地讓某些發送方互相干擾，路由器轉發的是受到干擾的信號而不是包，目標節點接收機首先校正信道畸變，然后能夠將對應于已知包的信號消除，前提是接收機知道它所需要的包所收到的干擾包的內容。

在理論上，AlgNC方案也能夠使一個雙向中繼網絡的容量吞吐量加倍，原因是所需的時隙減半。軟件無線電（software radio）測試床的結果表明，相對于傳統的無線路由和數字網絡編碼，吞吐量分別增加了70%和30%；而且，AlgNC有助于解決鏈路拓撲中的隱藏終端（hidden terminal）問題，無論是對單向鏈路還是雙向鏈路。但是，沒有進行同步的假設，也沒有通過導頻（pilot）做同步處理，甚至沒有利用包之間的不完整重疊進行同步，甚至它還能夠處理不同的信道之間所引入的相移。

PNC和AlgNC方案中存在的一個問題就是兩者都依賴于調制方式，目前為止兩者都沒有構造出一種獨立于調制方式的方案，而且PNC對于同步還非常敏感。但是，有關物理層網絡編碼的這些工作有助于激發對于將無線廣播特性融入網絡編碼的更深入的研究。

3.4.3 復數域網絡編碼

先前的網絡編碼研究主要應用于有限域，因此編碼主要是在比特級的運算，而將網絡編碼應用于其他域的研究已經引起了廣泛的興趣。2008年初，Wang和Giannakis在參考文獻 [29]中引入了復數域網絡編碼 （complex field network coding，CFNC），研究了衰落信道的性能。CFNC概念的引入，使得在物理層的符號級運算成為必要，而與有限域網絡編碼（Galois field network coding，GFNC）相比，在無線網絡環境條件下，CFNC是一種更好的選擇。CFNC的動機是，通過利用多用戶檢測，基于中繼的多源協作通信能夠實現空間分集增益，并提高覆蓋和有效的最大似然比解調。Wang等人采用預編碼的方法來對抗多徑衰落，為網絡編碼的應用提供保障。參考文獻[29]指出，對于一個具有源個數為NS、中繼個數為NR和一個目標節點的中繼協同網絡，CFNC總是能夠提供每源每時隙1/2符號的吞吐量，而GFNC的吞吐量僅僅是1/(NS+NR)，傳統中繼的吞吐量則僅僅是1/(NS+(NR+1))。如所期望，不論SNR和星座尺寸如何，CFNC都能夠實現完全分集。

3.5 網絡編碼概念與其他技術的融合

在參考文獻[30]中，Fasolo等人將MIMO技術與網絡編碼技術結合，利用空間增益和網絡編碼增益，針對衰落信道和包丟失問題，獲得了比單純應用傳統網絡編碼技術魯棒性更好的系統。參考文獻[31]同樣研究了MIMO網絡編碼，基于的是Alamouti開環空時塊碼（STBC），針對的是一個3節點中繼網絡。與目前多數的研究工作關注于3節點中繼模型所不同，參考文獻[23]研究了4節點雙向中繼信道模型，這種模型下多增加了一跳（hop），因此兩個中繼扮演了中間編碼節點的角色。作者設計了一個預消除協議，并使用了模擬網絡編碼技術，但是使用的是無噪聲信道模型假設。在參考文獻[32]的工作中，Khirallah等人將擴頻（spread spectrum）和物理層網絡編碼融合在一起，提出了網絡擴頻編碼（network spread coding，NSC）以改進傳統標準擴頻碼的性能。作者使用了完全補碼（complete complementary code，CC碼）作為擴頻碼，原因是 CC碼的理想相關特性使得與標準擴頻碼相比，NSC顯示出顯著的競爭力。通過所設計的NSC編碼方案，在AWGN和衰落信道中，均獲得了更低的復雜度和更低的干擾等級，節省了大量的帶寬。

將網絡編碼的概念與其他的無線技術結合起來，可以根據某一方面的需要，優化無線網絡的性能，近期的諸如此類研究工作包括與多天線技術的結合、與擴展頻譜技術的結合等，詳見參考文獻[23，30～33]。

3.5.1 與多天線技術的結合

在參考文獻[30]中，將MIMO技術應用于網絡編碼，以利用包合成過程所內在的空間分集特性。實際上，網絡編碼和MIMO解決的是類似的問題，即根據給定的一個接收樣本向量，解碼傳輸符號（symbol）向量。根據這一觀察結果，提出一種新的NC編解碼方法，其基本思想是將網絡編碼功能移向物理層以便聯合進行NC解碼和MIMO檢測，從而獲得兩種方法的優勢。理論分析和仿真結果證明，在克服衰落和包丟失性能方面，這種MIMO_NC系統比傳統的網絡編碼具有更好的魯棒性。

參考文獻[31]中研究了一個中繼配備多個天線的雙向通信系統，證明了當中繼不知道下行信道狀態信息的情況下，通過在中繼上增加天線所獲得的優勢，只能通過使用解碼轉發（decode and forward，DF）來得到，而不能通過放大轉發（amplify and forward，AF）得到；當同時應用發射分集和無線網絡編碼時，得到了很顯著的增益，此外還證明了如何在中繼進行天線選擇才能夠提高這種系統的性能，研究結果顯示如果中繼知道下行信道狀態信息，則相對于簡單的天線選擇方案，網絡編碼可能不會提供額外的增益。

3.5.2 與擴頻技術的結合

參考文獻[32]將網絡編碼與擴展頻譜技術相結合。無線ad hoc和P2P網絡上的數據流面對的是諸如干擾級別、衰落、噪聲等問題，這些問題限制了實時多媒體應用，降低這些影響的一種典型方法是應用擴展頻譜技術，該技術通常會導致難以接受的對于帶寬的需求增長；另一方面，網絡編碼是作為一種降低帶寬需求的有效方法而提出來的。基于這種思想提出了一種基于完全補碼（CC碼）的方案，稱之為NSC，將擴頻技術和網絡編碼技術結合起來。NSC具有對于噪聲和干擾的魯棒性，同時又降低了對于帶寬的需求。與傳統的擴頻方案相比，不管是AWGN還是衰落信道，所提出的兩種實際的NSC設計表現出了富于競爭力的更好性能，具有更低的復雜度，同時節省了大量的帶寬。

3.5.3 多載波信道與多址信道的協同

在參考文獻[33]中，Zhang和Li將網絡編碼的應用延伸到多信道無線系統，研究了基于OFDMA的802.16無線城域網（WMAN），其方法是應用了他們提出的編碼已知的子載波分配機制 （coding aware subcarrier assignment mechanism）。多信道網絡編碼是通過將具有相似大小信噪比SNR的子載波進行編碼，利用了下行鏈路子載波之間的信道增益的分集，結果顯示吞吐量能夠真正得到提高。

正交頻分多址已經應用于寬帶接入技術如802.16無線城域網，由于下行子載波間信道增益的分集性，從之前的研究已經知道，子載波的動態分配能夠顯著地提高OFDMA系統的整體性能，表現在功率效率和鏈路吞吐量等方面。之前大量的研究工作關注于OFDMA下行鏈路的聯合子載波分配和資源（比特和功率）分配，在參考文獻[33]中，對于基于OFDMA的無線網絡的上行和下行鏈路，采用跨層設計的方法，提出一種結合網絡編碼方法的子載波分配算法。其中，將最大速率分配問題構造為一種混合整數線性規劃，推導出一種多項式時間探索式方法來近似求解。通過將具有相似大小信噪比SNR的子載波進行編碼，利用了下行鏈路子載波之間的信道增益的分集，結果顯示吞吐量能夠真正得到提高。利用網絡編碼，將可以分配相同的子載波到不同的下行鏈路，而又不致引起任何的干擾。因此，結合網絡編碼的分配方案可觀地提高了帶寬效率，增加了網絡層吞吐量。研究顯示，這種探索式方法得到的總的網絡吞吐量可與最優解相比擬，而僅僅在公平性方面有輕微的損失；而且，結合網絡編碼的子載波分配機制同樣可以應用于其他的多信道無線系統。

近來，協同分集（cooperative diversity）受到大量的關注，作為一種低成本技術用以克服多徑衰落和提高傳輸可靠性，但是，由于中繼傳輸要消耗額外的帶寬資源，之前的很多協同協議遭受各態歷經容量的損失，為此在參考文獻[34]中，Ding提出了一種上行鏈路中將網絡編碼技術與協調分集結合在一起，以利用網絡編碼技術能夠提高系統吞吐量的能力。通過應用一種分布式的中繼選擇策略，有效地利用了多徑傳播的動態屬性。同樣的，使用了兩種信息論度量耗損和多徑容量來支持所提傳輸方案的性能評價，分析結果顯示出與蒙特卡羅仿真很一致的結論，這表明，與其他對應的方案相比，所提出的協議能夠同時實現更好的系統魯棒性和更大的系統吞吐量。

Ding在參考文獻[35]研究了應用物理層網絡編碼的情況下，如何保持分集的問題。PNC證明了能夠顯著提高AWGN信道無線網絡的吞吐量，但是當PNC應用到多徑信道時將會帶來很多問題，因為多徑信道的情形要求每一發射機端的振幅和相位補償，而相位補償需要準確的分布式相位跟蹤，振幅補償則更為復雜，因為會引起系統的效率降低，從而導致分集的消失，即使是在完美的信道估計實現的情況下也可能會如此。Ding等人提出的一種系統來避免這些問題，通過在網絡體系更高一級——物理層對PNC技術的認定，進行分布式中繼選擇。由于這樣得到的方案能夠實現一種分集選擇，所以稱之為分集網絡編碼（network coding with diversity，NUD）。為便于性能評價，研究了兩種信息論量度，即耗損 （outage）和各態歷經容量（ergodic capacity）。理論分析和仿真結果表明，與對應的方案相比，所提出的協議能夠實現更魯棒的性能和更好的系統吞吐量。最后，將所提出的網絡編碼延伸到協同多址信道，得到一種新的協同協議，獲得比已經存在的傳輸方案更好的耗損參數和更大的各態歷經容量。

Zhang等人在參考文獻[36]研究了兩個源節點S1和S2，通過一個中繼節點R進行信息交換的雙向中繼信道（TWRC），其中R在同一個時隙接收來自S1和S2的疊加信號，然后在下一個時隙放大并轉發給S1和S2，應用模擬網絡編碼，S1和S2從接收到的信號中消除所謂的自干擾信號，然后解出所需的信息。假設S1和S2都配備有單天線，R配備有多天線，分析了基于模擬網絡編碼，在中繼R采用線性處理（波束賦形）的TWRC信道的容量區，容量區包含了當S1、S2和R為給定發射功率時，S1和S2的所有可實現雙向速率對，給出了最優中繼波束賦形結構以及一種基于凸優化技術的有效算法來計算最優波束賦形矩陣，同時也給出了一種低復雜度的次優中繼波束賦形方案，比較了其可實現速率與最優方案下的容量。

4 無線網絡編碼研究面臨的挑戰

網絡編碼的部署需要用到各種資源，諸如同步和可靠性機制，需要網絡節點的功能平衡，諸如有限域運算或其他域的運算以及存儲能力。

或許更為重要的是，需要設計新的協議和架構，或者為無線網絡調整已有的基礎網絡，以便使得網絡編碼功能得以實現。在哪一層實現網絡編碼功能，網絡編碼能夠支持什么類型的鏈接，應該布置什么樣的編碼機制，構成了目前網絡協議和架構設計中的研究課題。

其他挑戰包括如何支持某些特殊應用的需求。例如，實時應用，諸如音頻和視頻，可能在吞吐量和時延方面對于QoS有嚴格的需求。通常這些因素是互相沖突的，要通過網絡編碼實現最優的吞吐量，對于包的個數n值很大的情況，可能需要網絡節點混合n個包；另一方面，為了解碼源信息，一個節點可能需要收集n個包，這將導致難以承受的時延。如何很好地平衡這些需求，可能必須需要跨層設計的方法。

另外，一些功能上的問題，諸如調度和路由，也需要考慮周到。例如，對于支持多個單播任務的一個網絡，目前還沒有搞清楚跨越不同任務的信息能夠混合到怎樣的程度，以及在何等級別上廣播傳輸能夠進行調度。

目前為止，無線網絡編碼的研究基本停留在理論模型上，而缺乏一般性的和實用模型的編碼方法。具體地說，網絡編碼應用于實際的無線環境面臨的挑戰分兩方面：一是大多數現有的無線網絡編碼需要很多的不切實際的假設，例如，物理層網絡編碼需要完全的相位/時間同步、功率控制和發射機與接收機兩端都必須是信道狀態信息可知，特別地，完全的相位同步假設是最困難的，因為由信道和收發機硬件引起的相位漂移是隨機的，這就要求必須有一個閉環的控制方案；另外一個挑戰是，無線網絡編碼的實際編碼方法和解碼方法的研究還沒有引起足夠多的注意，例如，接收信息的線性組合是線性網絡編碼的主要思想，然而，如何應用線性網絡編碼到無線網絡，且做到性能的魯棒性和保證好的解碼時延性能，是一個有待解決的問題。

參考文獻

1 Yeung R W,Zhang Z.Distributed source coding for satellite communications.IEEE Transactions on Information Theory,1999(IT-45):1111～1120

2 Ahlswede R,Cai N,Yeung R W.Network information flow.IEEE Transactions on Information Theory,2000 (IT-46):1204～1216

3 Li S Y R,Yeung R W,Cai N.Linear network coding.IEEE Transactions on Information Theory,2003,49(2):371～381

4 Koetter R,Medard M.An algebraic approach to network coding.IEEE-Acm Transactions on Networking,2003,11(5):782～795

5 Jaggi S,Sandrs P,Chou P A,et al.Polynomial time algorithms for multicast network code construction.IEEE Transactions on Information Theory,2005,51(6):1973～1982

6 Ho T,Medard M,Koetter R,et al.A random linear network coding approach to multicast.IEEE Transactions on Information Theory,2006,52(10):4413～4430

7 Fragouli C, Soljanin E. Network coding fundamentals.Foundations and Trends in Networking,2007,2(1):1～133

8 Wu Y N,Chou P A,Kung S Y.Minimum-energy multicast in mobile ad hoc networks using network coding. IEEE Transactions on Communications,2005,53(11):1906～1918

9 Fragouli C,Widmer J,Le Boudec J Y.A network coding approach to energy efficient broadcasting:from theory to practice.In:25th IEEE International Conference on Computer Communications,April 2006

10 Lun D S.Efficient operation OD coded packet networks.PhD thesis,Massachusetts Institute of Technology,June 2006

11 Eryilmaz A,Ozdaglar A,Medard M.On delay performance gains from network coding.In:Proc 40th Annual Conference on Information Sciences and Systems,Princeton,NJ,March 2006

12 Zhang S,Liew S,Lam P.Physical layer network coding.In:ACM MobiCom 2006,Los Angeles,Sept 2006

13 Katti S,Rahul H,Hu W,et al.XORs in the air:practical wirelessnetwork coding.Computer Communication Review,2006,36(4):243～254

14 Dimakis A G,Prabhakaran V,Ramchandran K.Ubiquitous accessto distributed datain large-scalenet works through decentralized erasurecodes.In:Symposium on Information Processing in Sensor Networks (IPSN'05),Los Angeles,California,USA,April 2005

15 Fragouli C,Widmer J,Le Boudec J Y.On the benefits of network coding for wireless applications.In:4th International Symposium on Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks,April 2006

16 Petrovic D,Ramchandran K,Rabaey J.Overcoming untuned radios in wireless networks with network coding.IEEE Transactions on Information Theory,2006,52(6):2649～2657

17 Gowaikar R,Dana A F,Boudec J-Y L.On the capacity of wireless erasure networks.In:Proceeding of the 2007 IEEE International Symposium on Information Theory, Chicago,Illinois,June-July 2004

18 Ratnakar N,Kramer G.The multicast capacity of acyclic,deterministic,relaynetworkswith nointerference.Network Coding Workshop,Italy,April 2005

19 Avestimehr S,Diggavi S,Tse D H C,A deterministic model for wireless relay networks and its capacity.Information Theory Workshop,Lake Tahoe,September 2007

20 Avestimehr S,Diggavi S,Tse D H C.Wirelessnet work information flow.In:Proceedings of Allert on Conference on Communication,Control,and Computing,Illinois,September 2007

21 Sagduyu Y E,Ephremides A.Joint scheduling and wireless network coding.In:Proc First Workshop on Network Coding,Theory,and Applications,Riva del Garda,Italy,April,2005

22 Katti S,Gollakota S,Katabi D.Embracing wireless interference:analog network coding.Computer Communication Review,2007,37(4):397～408

23 Kuek S K,Yuen C,Chin W H.Four-node relay network with bi-directional traffic employing wireless network coding with precancellation.In:IEEE 67th Vehicular Technology Conference-Spring,Singapore,May 2008

24 Fragouli C,Katabi D,Markopoulou A,et al.Wireless network coding: opportunities & challenges. In: IEEE Military Communications Conference,Orlando,Florida,USA,Oct 2007

25 FragouliC,Soljanin E.Network coding applications.In:Foundations and Trends in Networking,2007,2(2)

26 Chachulski S,Jennings M,Katti S,et al.Trading structure for randomness in wireless opportunistic routing. Computer Communication Review,2007,37(4):169～180

27 Scheuermann B,Hu W,Crowcroft J.Near-optimal coordinated coding in wireless multihop networks.In:CoNext'07,New York,USA,2007

28 Karande S S,Misra K,Ilyas M U,et al.Adaptive network coding with noisy packets.In:41st Annual Conference on Information Sciences and Systems,Baltimore,MD,March 2007

29 Wang T R,Giannakis G B.Complex field network coding for multiuser cooperative communications.IEEE Journal on Selected Areas in Communications,2008,26(3):561～571

30 Fasolo E,Rossetto F,Zorzi M.Network coding meets MIMO.In:Fourth Workshop on Network Coding,Theory,and Applications,Hong Kong,China,January 2008

31 Yuen C,Chin W H,Guan Y L,et al.Bi-directional multi-antenna relay communications with wireless network coding.In:IEEE 67th Vehicular Technology Conference-Spring,Singapore,May 2008

32 Khirallah C,et al.Network spread coding.In:Fourth Workshop on Network Coding,Theory,and Applications,Hong Kong,China,January 2008

33 Zhang X Y,Li B C.Joint network coding and subcarrier assignmentin OFDMA-based wirelessnet works.In:Fourth Workshop on Network Coding,Theory,and Applications,Hong Kong,China,January 2008

34 Ding Z G,Leung K K,Goeckel D L,et al.A new form of network coded cooperative transmission for multiple access channels.In:IEEE Military Communications Conference,San Diego,California,November 2008

35 Ding Z G,Leung K K,Goeckel D L,et al.On the study of network coding with diversity.IEEE Transactions on Wireless Communications,2009,8(3):1247～1259

36 Zhang R,Liang Y C,Chai C C,et al.Optimal beam forming for two-way multi-antenna relay channel with analogue network coding.IEEE Journal on Selected Areas in Communications,2009,27(5):699～712

Network Coding Technology in Wireless Network

Wang Hengyou,Pen Mugen,Wang Wenbo,Wu Hequan
(BUPT,Beijing 100876,China)

Network coding is a novel technique to improve network throughput and performance.It is expected to be a key technology for networks of future.This paper gives a survey on the network coding applicated in wireless networks which is considerd to be one of the most likely applications of network coding.Network coding allows to take advantage of the broadcasting nature of the shared wireless medium.Wireless networks and sensor networks provide opportunities for the application of network coding.In this paper,we introduce several network coding and corresponding encoding strategies under different scenarios.These include traditional network coding,physical layer network coding,analogue network coding and complex field network coding as well.We also give remarks on wireless network coding in the future.

wireless network coding,digital network coding,physical layer network coding,finite field network coding,complex field network coding

2010-07-09）

* 國家自然科學基金資助項目（No.61072058），國家科技重大專項資助項目（No.2010ZX03003-003-01）

1 引言

傳統的通信網絡中，信息流從源節點發出，各級中間節點進行存儲轉發，最后到達目標節點。網絡編碼概念的提出改變了這一觀念，賦予了中間節點信息處理和運算的功能，理論上顯著提高了網絡的吞吐量。

王亨友，北京郵電大學在讀博士生，師從鄔賀銓院士，研究方向為下一代寬帶移動通信系統的網絡編碼技術；彭木根，北京郵電大學副教授，碩士生導師，博士，研究方向為無線信號處理及寬帶無線網絡技術；王文博，北京郵電大學教授，博士生導師，博士，研究方向為無線通信技術及無線寬帶網絡；鄔賀銓，中國工程院院士，中國工程院副院長，國家科委“863”計劃通信技術主題專家組組長，工業和信息化部電信科學技術研究院副院長兼總工程師。