無線通信中的網(wǎng)絡(luò)編碼技術(shù)*

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

（北京郵電大學(xué) 北京 100876）

無線通信中的網(wǎng)絡(luò)編碼技術(shù)*

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

（北京郵電大學(xué) 北京 100876）

網(wǎng)絡(luò)編碼是一種提高網(wǎng)絡(luò)吞吐量和性能的新技術(shù)，預(yù)計(jì)將成為未來網(wǎng)絡(luò)的一項(xiàng)關(guān)鍵技術(shù)。本文概述了無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼技術(shù)，無線網(wǎng)絡(luò)被認(rèn)為是網(wǎng)絡(luò)編碼最可能得到應(yīng)用的領(lǐng)域之一，網(wǎng)絡(luò)編碼技術(shù)使無線媒質(zhì)的廣播屬性可以得到充分利用，無線網(wǎng)絡(luò)和傳感器網(wǎng)絡(luò)為網(wǎng)絡(luò)編碼的應(yīng)用提供了巨大的機(jī)會(huì)。本文結(jié)合不同無線場(chǎng)景介紹了網(wǎng)絡(luò)編碼的各種編碼方法，包括傳統(tǒng)的網(wǎng)絡(luò)編碼、物理層網(wǎng)絡(luò)編碼、模擬網(wǎng)絡(luò)編碼以及復(fù)數(shù)域網(wǎng)絡(luò)編碼，并對(duì)未來發(fā)展給出了展望。

無線網(wǎng)絡(luò)編碼；數(shù)字網(wǎng)絡(luò)編碼；物理層網(wǎng)絡(luò)編碼；有限域網(wǎng)絡(luò)編碼；復(fù)數(shù)域網(wǎng)絡(luò)編碼

[1]首次引入了網(wǎng)絡(luò)編碼概念，用于衛(wèi)星通信網(wǎng)絡(luò)，在參考文獻(xiàn)[2]中得到完善的發(fā)展，并首次闡述了網(wǎng)絡(luò)編碼相對(duì)于傳統(tǒng)的存儲(chǔ)轉(zhuǎn)發(fā)方式的優(yōu)勢(shì)，這就駁斥了之前的觀點(diǎn)，即在中間節(jié)點(diǎn)只需作數(shù)據(jù)復(fù)制而沒有必要進(jìn)行數(shù)據(jù)處理，參考文獻(xiàn)[3,4]證明了網(wǎng)絡(luò)編碼的構(gòu)造可以分別通過線性組合和有限域來實(shí)現(xiàn)。

參考文獻(xiàn)[2]和[3]研究了多播網(wǎng)絡(luò)的網(wǎng)絡(luò)容量以及涉及割集的容量，描述了多播網(wǎng)絡(luò)的可容許編碼速率區(qū)，證明了網(wǎng)絡(luò)的最大吞吐量可以通過使用編碼來實(shí)現(xiàn)。參考文獻(xiàn)[2]發(fā)展的卷積碼屬于非線性網(wǎng)絡(luò)編碼，適用于多源情況，但是這種非線性碼的復(fù)雜度太大。針對(duì)單源的多播網(wǎng)絡(luò)，Li等人在參考文獻(xiàn)[3]深入研究了線性網(wǎng)絡(luò)編碼。線性編碼是所有最簡(jiǎn)單的編碼方案之一，在線性編碼中，節(jié)點(diǎn)的編碼是采用傳入數(shù)據(jù)的線性組合，即，線性編碼將一組數(shù)據(jù)看作某一特定基本域上的一個(gè)向量，且允許一個(gè)節(jié)點(diǎn)在將一個(gè)向量傳遞之前對(duì)向量應(yīng)用線性變換，證明了每一接收機(jī)的最大流（上限）可以實(shí)現(xiàn)。作者嚴(yán)謹(jǐn)?shù)仃U述了這種多播問題并證明了線性編碼足以實(shí)現(xiàn)最優(yōu)的多播容量，即從源節(jié)點(diǎn)到每一接收節(jié)點(diǎn)的最大流。

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

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

當(dāng)網(wǎng)絡(luò)編碼用于信息傳輸，其物理實(shí)現(xiàn)將引起信道上的傳輸時(shí)延和節(jié)點(diǎn)上的處理時(shí)延，而目前節(jié)點(diǎn)處理是網(wǎng)絡(luò)上信息傳送總時(shí)延的決定因素，這就要求網(wǎng)絡(luò)編碼的編碼機(jī)制應(yīng)以簡(jiǎn)單和快速的電路來實(shí)現(xiàn)，因此，采用線性映射的網(wǎng)絡(luò)編碼方案特別受到關(guān)注。

以上這些最初的網(wǎng)絡(luò)編碼的研究主要針對(duì)于無損耗的有線網(wǎng)絡(luò)中多播通信的路由問題，而且基本是抽象出無時(shí)延的網(wǎng)絡(luò)模型，但是，這些基礎(chǔ)性的工作，卻為后來的其他應(yīng)用的研究奠定了堅(jiān)實(shí)的理論基礎(chǔ)。

鑒于其普遍適用性和巨大應(yīng)用潛力，網(wǎng)絡(luò)編碼理論已經(jīng)被引入多個(gè)研究領(lǐng)域，諸如信息和編碼理論、網(wǎng)絡(luò)、網(wǎng)絡(luò)恢復(fù)、網(wǎng)絡(luò)監(jiān)控、內(nèi)容分發(fā)、分布式存儲(chǔ)、組合數(shù)學(xué)、交換、無線通信、ad hoc網(wǎng)、復(fù)雜度理論、安全及密碼學(xué)和矩陣?yán)碚摚ㄒ妳⒖嘉墨I(xiàn)[3]和[7]），且網(wǎng)絡(luò)編碼新的應(yīng)用仍在繼續(xù)出現(xiàn)。本文主要面向網(wǎng)絡(luò)編碼在無線通信中的應(yīng)用，介紹其理論和技術(shù)發(fā)展。

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

本文結(jié)構(gòu)如下：第二部分通過一個(gè)簡(jiǎn)單的雙向無線通信環(huán)境，引入網(wǎng)絡(luò)編碼的模型，第三部分介紹各種無線網(wǎng)絡(luò)環(huán)境主流無線網(wǎng)絡(luò)編碼技術(shù)的編碼方案及其應(yīng)用，最后，給出一個(gè)結(jié)論性的總結(jié)和提出面臨的挑戰(zhàn)。

2 系統(tǒng)模型舉例

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

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

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

圖1的雙向3節(jié)點(diǎn)簡(jiǎn)單模型可以推廣到各種其他復(fù)雜的情形。參考文獻(xiàn)[23]研究了4節(jié)點(diǎn)雙向中繼網(wǎng)絡(luò)，如何能夠最優(yōu)地中繼信息的協(xié)議和算法，提出了一種有效地中繼信息的中繼協(xié)議。

圖1 3節(jié)點(diǎn)的無線雙向信息交換的例子

3 技術(shù)發(fā)展和應(yīng)用

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

在無線網(wǎng)絡(luò)中，當(dāng)來自不同發(fā)射機(jī)的信號(hào)自動(dòng)地在無線信道中合成，無線信道為物理層網(wǎng)絡(luò)編碼提供了完美的媒質(zhì)。

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

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

從無線系統(tǒng)的當(dāng)前技術(shù)水平面向?qū)嶋H的基于信息論解決方法的研究過程中，將網(wǎng)絡(luò)編碼概念與無線媒質(zhì)的廣播特性相結(jié)合，是一個(gè)富有意義的技術(shù)步驟。實(shí)際上，運(yùn)用代數(shù)的方法疊加信號(hào)就是散列法的一種變形，這種方法能夠利用無線媒質(zhì)的廣播屬性優(yōu)勢(shì)，而且在實(shí)際實(shí)現(xiàn)中也足夠簡(jiǎn)單可行。某種意義上說，無線網(wǎng)絡(luò)編碼與網(wǎng)絡(luò)信息理論和網(wǎng)絡(luò)算法具有很大的重疊。從實(shí)際應(yīng)用的角度，無線ad hoc和無線傳感器網(wǎng)絡(luò)深受期待而成為首批應(yīng)用網(wǎng)絡(luò)編碼技術(shù)的領(lǐng)域之一，原因是兩者的網(wǎng)絡(luò)環(huán)境下其協(xié)議嚴(yán)格性要求較為寬松。

為了說明無線網(wǎng)絡(luò)當(dāng)應(yīng)用網(wǎng)絡(luò)編碼技術(shù)所帶來的優(yōu)勢(shì)，可以首先考慮共享無線媒質(zhì)的廣播屬性所能提供的帶寬、傳輸功率、時(shí)延，以及對(duì)于環(huán)境動(dòng)態(tài)改變的適應(yīng)性?；谥T如此類的優(yōu)勢(shì)，下面的部分將討論一系列業(yè)務(wù)模式和網(wǎng)絡(luò)配置示例。MIT的COPE結(jié)論表明，即使當(dāng)編碼運(yùn)算限定在遵循一些額外限制的簡(jiǎn)單二進(jìn)制加法，仍然會(huì)在吞吐量和MAC層協(xié)議的效率等方面獲得增益。

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

3.1 無線ad hoc網(wǎng)絡(luò)的能量問題

無線ad hoc和傳感器網(wǎng)絡(luò)為網(wǎng)絡(luò)編碼的應(yīng)用提供了大量的機(jī)會(huì)，同時(shí)它也面臨大量的問題。

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

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

3.2 無線傳感器網(wǎng)絡(luò)

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

無線傳感器網(wǎng)絡(luò)的實(shí)現(xiàn)和布網(wǎng)要求超低成本和低功率節(jié)點(diǎn)，盡管節(jié)點(diǎn)的數(shù)字子系統(tǒng)仍然遵循摩爾定律，但是有關(guān)模擬組件的性能則沒有這種趨勢(shì)。參考文獻(xiàn)[16]提出了一種將數(shù)字和模擬組件（包括本地振蕩器）完全集成的架構(gòu)，能夠顯著地降低節(jié)點(diǎn)的成本、尺寸和總功耗。盡管這樣的一個(gè)基本架構(gòu)不能提供可靠的標(biāo)準(zhǔn)設(shè)計(jì)的調(diào)整，但是已經(jīng)證明通過使用隨機(jī)網(wǎng)絡(luò)編碼，這類節(jié)點(diǎn)的一個(gè)密集網(wǎng)絡(luò)能夠?qū)崿F(xiàn)吞吐量線性于通信系統(tǒng)中可用信道的數(shù)量；而且可以證明，非調(diào)諧網(wǎng)絡(luò)（這里非調(diào)諧網(wǎng)絡(luò)是指每一個(gè)傳感器從一個(gè)有限的頻率集合中，隨機(jī)選擇一個(gè)頻率用以發(fā)射）與一個(gè)完全協(xié)調(diào)的可調(diào)網(wǎng)絡(luò)的可實(shí)現(xiàn)吞吐量之比近似于1/e。他們的研究利用網(wǎng)絡(luò)編碼來改變這樣一個(gè)事實(shí)即吞吐量等于一個(gè)圖的最大流是可實(shí)現(xiàn)的，即使是在無法事先知道網(wǎng)絡(luò)拓?fù)涞那闆r下，然而，此處的挑戰(zhàn)在于如何發(fā)現(xiàn)對(duì)應(yīng)于該網(wǎng)絡(luò)的隨機(jī)圖的最大流。

3.3 機(jī)會(huì)網(wǎng)絡(luò)編碼

3.3.1 COPE

Katti等人在參考文獻(xiàn)[13]提出了一種稱作COPE的架構(gòu)，這是用于無線mesh網(wǎng)的一種新架構(gòu)。除了轉(zhuǎn)發(fā)包以外，路由器將來自不同源節(jié)點(diǎn)的包進(jìn)行混合（例如進(jìn)行編碼），用以每一次傳輸?shù)男畔?nèi)容。這種在中間節(jié)點(diǎn)的處理提高了網(wǎng)絡(luò)吞吐量，而設(shè)計(jì)就是基于網(wǎng)絡(luò)編碼理論的。之前的網(wǎng)絡(luò)編碼研究主要偏于理論且多集中于研究多播業(yè)務(wù)，COPE的目標(biāo)是在理論和實(shí)際應(yīng)用之間架起一座橋梁，研究了更普遍的單播業(yè)務(wù)、動(dòng)態(tài)和突發(fā)流，以及在當(dāng)前網(wǎng)絡(luò)協(xié)議棧下融合加入網(wǎng)絡(luò)編碼的實(shí)際問題，設(shè)計(jì)了一個(gè)20節(jié)點(diǎn)的無線網(wǎng)絡(luò)，對(duì)無線網(wǎng)絡(luò)編碼的首次測(cè)試床測(cè)試結(jié)果進(jìn)行了討論和性能評(píng)估，結(jié)果顯示COPE顯著地提高了網(wǎng)絡(luò)吞吐量，一個(gè)3節(jié)點(diǎn)測(cè)試床的初步的試驗(yàn)結(jié)果表明，802.11 mesh網(wǎng)絡(luò)中，相對(duì)于傳統(tǒng)存儲(chǔ)轉(zhuǎn)發(fā)方案，COPE獲得的是幾乎3倍的吞吐量；而由于業(yè)務(wù)模式、擁塞控制水平和傳輸協(xié)議的不同，吞吐量的增益從幾個(gè)百分點(diǎn)到幾十個(gè)百分點(diǎn)不等。

COPE將機(jī)會(huì)算法（opportunistic algorithm）運(yùn)用到網(wǎng)絡(luò)編碼中，每一節(jié)點(diǎn)監(jiān)聽無線媒質(zhì)，借以獲取其鄰近各節(jié)點(diǎn)的狀態(tài)，檢測(cè)編碼機(jī)會(huì)，一旦其接收者能夠解碼，則該節(jié)點(diǎn)進(jìn)行編碼。COPE所處理的情形是，需要提供多個(gè)單播業(yè)務(wù)的無線mesh網(wǎng)，而且沒有網(wǎng)絡(luò)拓?fù)浠蛘邩I(yè)務(wù)模式的中央控制信息。COPE的基本思想就是網(wǎng)絡(luò)編碼處理能夠帶來增益的同時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)仍然可以識(shí)別和利用機(jī)會(huì)。

3.3.2 MORE

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

COPE稱作流間網(wǎng)絡(luò)編碼是因?yàn)榫幋a過程作用在其上的各個(gè)包在它們的下一跳是不同的，所以也就來自不同的流；而MORE稱之為流內(nèi)網(wǎng)絡(luò)編碼是因?yàn)槁酚善魉Y(jié)合的包都流向相同的目標(biāo)節(jié)點(diǎn)參考。MORE應(yīng)用了3種技術(shù)來產(chǎn)生足夠的編碼，以保證路由器能夠很容易地支持高速率，這3種技術(shù)是：只對(duì)新包編碼；對(duì)碼向量編碼；預(yù)編碼。詳細(xì)的描述見參考文獻(xiàn)[26]。

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

MORE是一種獨(dú)立于MAC的機(jī)會(huì)路由協(xié)議，其在將包轉(zhuǎn)發(fā)之前隨機(jī)地混合包，這種隨機(jī)性操作保證了監(jiān)聽到相同傳輸?shù)穆酚善鞑槐剞D(zhuǎn)發(fā)同樣的包，因此MORE不需要專門的調(diào)度機(jī)器來協(xié)調(diào)路由器，從而可以直接運(yùn)行于801.11的頂端。一個(gè)20節(jié)點(diǎn)的無線測(cè)試床上的實(shí)驗(yàn)結(jié)果顯示，MORE的平均單播吞吐量高于ExOR 22%，而當(dāng)具有空間重用機(jī)會(huì)時(shí)，增益更是增大到了45%；對(duì)于多播傳輸?shù)那闆r，MORE的增益隨目標(biāo)節(jié)點(diǎn)數(shù)量的增加而增加，將高于ExOR協(xié)議35%～200%。

3.3.3 noCoCo

Scheuermann等人在參考文獻(xiàn)[27]的工作比COPE又跨出了一步，研究了如何以一種更確定的方式構(gòu)造編碼機(jī)會(huì)，而同時(shí)仍然保留實(shí)際意義。他們提出一種跨層方案稱作 noCoCo（near-optimal coordinated coding，近最優(yōu)協(xié)作編碼）方案，該方案將每一跳包調(diào)度、網(wǎng)絡(luò)編碼和擁塞控制整合為一。noCoCo的主要想法是，在COPE中當(dāng)有自然出現(xiàn)的編碼機(jī)會(huì)時(shí)進(jìn)行編碼處理，而傳輸?shù)牡燃?jí)能夠顯著地影響編碼機(jī)會(huì)的獲取，從而影響編碼增益。利用無線傳輸?shù)穆窂椒旨蛷V播特性，作者提出一種有效的多徑路由協(xié)議，稱之為 MC2（multipath code casting，多徑編碼傳播），這種設(shè)計(jì)是基于網(wǎng)絡(luò)編碼，無需像先前的機(jī)會(huì)路由協(xié)議那樣需要節(jié)點(diǎn)間的協(xié)作；而且，這種協(xié)議提供了一種統(tǒng)一的架構(gòu)來處理多徑和非可靠性傳播路徑情形下的數(shù)據(jù)傳輸。

3.3.4 AdpNC

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

3.4 干擾利用的網(wǎng)絡(luò)編碼

3.4.1 物理層網(wǎng)絡(luò)編碼

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

3.4.2 模擬網(wǎng)絡(luò)編碼

之前的多數(shù)網(wǎng)絡(luò)編碼研究工作，其編碼的線性組合都是作用在有限域上，參考文獻(xiàn)[12]所做的工作是第一次將網(wǎng)絡(luò)編碼應(yīng)用于物理層，而Katti等人則在參考文獻(xiàn)[22]引入了模擬網(wǎng)絡(luò)編碼（analog network coding，AlgNC）的概念，之所以稱作模擬網(wǎng)絡(luò)編碼是因?yàn)榛旌系氖切盘?hào)而不是比特。AlgNC同樣把干擾作為有益因素，設(shè)法有選擇地讓某些發(fā)送方互相干擾，路由器轉(zhuǎn)發(fā)的是受到干擾的信號(hào)而不是包，目標(biāo)節(jié)點(diǎn)接收機(jī)首先校正信道畸變，然后能夠?qū)?duì)應(yīng)于已知包的信號(hào)消除，前提是接收機(jī)知道它所需要的包所收到的干擾包的內(nèi)容。

在理論上，AlgNC方案也能夠使一個(gè)雙向中繼網(wǎng)絡(luò)的容量吞吐量加倍，原因是所需的時(shí)隙減半。軟件無線電（software radio）測(cè)試床的結(jié)果表明，相對(duì)于傳統(tǒng)的無線路由和數(shù)字網(wǎng)絡(luò)編碼，吞吐量分別增加了70%和30%；而且，AlgNC有助于解決鏈路拓?fù)渲械碾[藏終端（hidden terminal）問題，無論是對(duì)單向鏈路還是雙向鏈路。但是，沒有進(jìn)行同步的假設(shè)，也沒有通過導(dǎo)頻（pilot）做同步處理，甚至沒有利用包之間的不完整重疊進(jìn)行同步，甚至它還能夠處理不同的信道之間所引入的相移。

PNC和AlgNC方案中存在的一個(gè)問題就是兩者都依賴于調(diào)制方式，目前為止兩者都沒有構(gòu)造出一種獨(dú)立于調(diào)制方式的方案，而且PNC對(duì)于同步還非常敏感。但是，有關(guān)物理層網(wǎng)絡(luò)編碼的這些工作有助于激發(fā)對(duì)于將無線廣播特性融入網(wǎng)絡(luò)編碼的更深入的研究。

3.4.3 復(fù)數(shù)域網(wǎng)絡(luò)編碼

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

3.5 網(wǎng)絡(luò)編碼概念與其他技術(shù)的融合

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

將網(wǎng)絡(luò)編碼的概念與其他的無線技術(shù)結(jié)合起來，可以根據(jù)某一方面的需要，優(yōu)化無線網(wǎng)絡(luò)的性能，近期的諸如此類研究工作包括與多天線技術(shù)的結(jié)合、與擴(kuò)展頻譜技術(shù)的結(jié)合等，詳見參考文獻(xiàn)[23，30～33]。

3.5.1 與多天線技術(shù)的結(jié)合

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

參考文獻(xiàn)[31]中研究了一個(gè)中繼配備多個(gè)天線的雙向通信系統(tǒng)，證明了當(dāng)中繼不知道下行信道狀態(tài)信息的情況下，通過在中繼上增加天線所獲得的優(yōu)勢(shì)，只能通過使用解碼轉(zhuǎn)發(fā)（decode and forward，DF）來得到，而不能通過放大轉(zhuǎn)發(fā)（amplify and forward，AF）得到；當(dāng)同時(shí)應(yīng)用發(fā)射分集和無線網(wǎng)絡(luò)編碼時(shí)，得到了很顯著的增益，此外還證明了如何在中繼進(jìn)行天線選擇才能夠提高這種系統(tǒng)的性能，研究結(jié)果顯示如果中繼知道下行信道狀態(tài)信息，則相對(duì)于簡(jiǎn)單的天線選擇方案，網(wǎng)絡(luò)編碼可能不會(huì)提供額外的增益。

3.5.2 與擴(kuò)頻技術(shù)的結(jié)合

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

3.5.3 多載波信道與多址信道的協(xié)同

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

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

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

Ding在參考文獻(xiàn)[35]研究了應(yīng)用物理層網(wǎng)絡(luò)編碼的情況下，如何保持分集的問題。PNC證明了能夠顯著提高AWGN信道無線網(wǎng)絡(luò)的吞吐量，但是當(dāng)PNC應(yīng)用到多徑信道時(shí)將會(huì)帶來很多問題，因?yàn)槎鄰叫诺赖那樾我竺恳话l(fā)射機(jī)端的振幅和相位補(bǔ)償，而相位補(bǔ)償需要準(zhǔn)確的分布式相位跟蹤，振幅補(bǔ)償則更為復(fù)雜，因?yàn)闀?huì)引起系統(tǒng)的效率降低，從而導(dǎo)致分集的消失，即使是在完美的信道估計(jì)實(shí)現(xiàn)的情況下也可能會(huì)如此。Ding等人提出的一種系統(tǒng)來避免這些問題，通過在網(wǎng)絡(luò)體系更高一級(jí)——物理層對(duì)PNC技術(shù)的認(rèn)定，進(jìn)行分布式中繼選擇。由于這樣得到的方案能夠?qū)崿F(xiàn)一種分集選擇，所以稱之為分集網(wǎng)絡(luò)編碼（network coding with diversity，NUD）。為便于性能評(píng)價(jià)，研究了兩種信息論量度，即耗損 （outage）和各態(tài)歷經(jīng)容量（ergodic capacity）。理論分析和仿真結(jié)果表明，與對(duì)應(yīng)的方案相比，所提出的協(xié)議能夠?qū)崿F(xiàn)更魯棒的性能和更好的系統(tǒng)吞吐量。最后，將所提出的網(wǎng)絡(luò)編碼延伸到協(xié)同多址信道，得到一種新的協(xié)同協(xié)議，獲得比已經(jīng)存在的傳輸方案更好的耗損參數(shù)和更大的各態(tài)歷經(jīng)容量。

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

4 無線網(wǎng)絡(luò)編碼研究面臨的挑戰(zhàn)

網(wǎng)絡(luò)編碼的部署需要用到各種資源，諸如同步和可靠性機(jī)制，需要網(wǎng)絡(luò)節(jié)點(diǎn)的功能平衡，諸如有限域運(yùn)算或其他域的運(yùn)算以及存儲(chǔ)能力。

或許更為重要的是，需要設(shè)計(jì)新的協(xié)議和架構(gòu)，或者為無線網(wǎng)絡(luò)調(diào)整已有的基礎(chǔ)網(wǎng)絡(luò)，以便使得網(wǎng)絡(luò)編碼功能得以實(shí)現(xiàn)。在哪一層實(shí)現(xiàn)網(wǎng)絡(luò)編碼功能，網(wǎng)絡(luò)編碼能夠支持什么類型的鏈接，應(yīng)該布置什么樣的編碼機(jī)制，構(gòu)成了目前網(wǎng)絡(luò)協(xié)議和架構(gòu)設(shè)計(jì)中的研究課題。

其他挑戰(zhàn)包括如何支持某些特殊應(yīng)用的需求。例如，實(shí)時(shí)應(yīng)用，諸如音頻和視頻，可能在吞吐量和時(shí)延方面對(duì)于QoS有嚴(yán)格的需求。通常這些因素是互相沖突的，要通過網(wǎng)絡(luò)編碼實(shí)現(xiàn)最優(yōu)的吞吐量，對(duì)于包的個(gè)數(shù)n值很大的情況，可能需要網(wǎng)絡(luò)節(jié)點(diǎn)混合n個(gè)包；另一方面，為了解碼源信息，一個(gè)節(jié)點(diǎn)可能需要收集n個(gè)包，這將導(dǎo)致難以承受的時(shí)延。如何很好地平衡這些需求，可能必須需要跨層設(shè)計(jì)的方法。

另外，一些功能上的問題，諸如調(diào)度和路由，也需要考慮周到。例如，對(duì)于支持多個(gè)單播任務(wù)的一個(gè)網(wǎng)絡(luò)，目前還沒有搞清楚跨越不同任務(wù)的信息能夠混合到怎樣的程度，以及在何等級(jí)別上廣播傳輸能夠進(jìn)行調(diào)度。

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

參考文獻(xià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）

* 國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61072058），國(guó)家科技重大專項(xiàng)資助項(xiàng)目（No.2010ZX03003-003-01）

1 引言

傳統(tǒng)的通信網(wǎng)絡(luò)中，信息流從源節(jié)點(diǎn)發(fā)出，各級(jí)中間節(jié)點(diǎn)進(jìn)行存儲(chǔ)轉(zhuǎn)發(fā)，最后到達(dá)目標(biāo)節(jié)點(diǎn)。網(wǎng)絡(luò)編碼概念的提出改變了這一觀念，賦予了中間節(jié)點(diǎn)信息處理和運(yùn)算的功能，理論上顯著提高了網(wǎng)絡(luò)的吞吐量。

王亨友，北京郵電大學(xué)在讀博士生，師從鄔賀銓院士，研究方向?yàn)橄乱淮鷮拵б苿?dòng)通信系統(tǒng)的網(wǎng)絡(luò)編碼技術(shù)；彭木根，北京郵電大學(xué)副教授，碩士生導(dǎo)師，博士，研究方向?yàn)闊o線信號(hào)處理及寬帶無線網(wǎng)絡(luò)技術(shù)；王文博，北京郵電大學(xué)教授，博士生導(dǎo)師，博士，研究方向?yàn)闊o線通信技術(shù)及無線寬帶網(wǎng)絡(luò)；鄔賀銓，中國(guó)工程院院士，中國(guó)工程院副院長(zhǎng)，國(guó)家科委“863”計(jì)劃通信技術(shù)主題專家組組長(zhǎng)，工業(yè)和信息化部電信科學(xué)技術(shù)研究院副院長(zhǎng)兼總工程師。