摘  要: 介紹了網(wǎng)絡(luò)編碼的概念，分析了網(wǎng)絡(luò)編碼的原理及其特點。著重關(guān)注了網(wǎng)絡(luò)編碼的具體應(yīng)用，包括文件下載、無線環(huán)境、分布式存儲等方面。評述了網(wǎng)絡(luò)編碼的最新研究進(jìn)展，并對其發(fā)展趨勢進(jìn)行了展望。
關(guān)鍵詞: 網(wǎng)絡(luò)編碼； P2P下載； 分布式存儲； 無線網(wǎng)絡(luò)

    根據(jù)最大流最小割定理，通信網(wǎng)中端到端的最大信息流是由網(wǎng)絡(luò)有向圖的最小切割決定的。但目前網(wǎng)絡(luò)中無法達(dá)到這一理論的上界，這是因為在網(wǎng)絡(luò)中信息以“流”的方式來處理，原則上一個通信“管道”一次只允許傳輸一個“流”。傳統(tǒng)的觀念中，認(rèn)為在中間節(jié)點對信息進(jìn)行處理于信息傳輸本身沒有任何好處。然而，Ahlswede等人于2000年提出了網(wǎng)絡(luò)編碼的概念[1]，推翻了上述結(jié)論。所謂網(wǎng)絡(luò)編碼，是指中間節(jié)點不僅僅是簡單的存儲轉(zhuǎn)發(fā)，還可以對信息進(jìn)行一定的處理融合，增加單次傳輸?shù)男畔⒘?，提高網(wǎng)絡(luò)的性能。網(wǎng)絡(luò)編碼融合了編碼和路由的概念，給現(xiàn)有的網(wǎng)絡(luò)帶來了革命性的變化，給網(wǎng)絡(luò)結(jié)構(gòu)、路由的設(shè)計帶來了新的設(shè)計思路。
1 網(wǎng)絡(luò)編碼的概念
    最初提出網(wǎng)絡(luò)編碼是用來解決網(wǎng)絡(luò)中組播的最大流問題，即給定一個通信網(wǎng)絡(luò)，以G(V，E)來表示，G是一個有向無環(huán)圖。在組播通信中，需要一個信源S∈V和一組信宿T∈V。要實現(xiàn)組播通信，傳統(tǒng)的路由方式是建立一個或多個組播樹,即建立一棵以發(fā)送者為根節(jié)點、連接所有接收者的多播分發(fā)樹，所要傳輸?shù)男畔⒕驮谶@些事先選好的路徑上傳輸。所以建立組播樹是實現(xiàn)組播的關(guān)鍵，但是一般認(rèn)為組播樹的建立是一個NP問題。通常只是求出其近似解，先采用最大流算法找到信源S與一個信宿T1的最大流路徑，然后再依次尋找與下個信宿T2之間的最大流路徑，這時通常會在原通信網(wǎng)絡(luò)中去掉與T1之間已經(jīng)用過的鏈路的容量。這樣處理是因為傳統(tǒng)路由認(rèn)為網(wǎng)絡(luò)中傳輸?shù)男畔⑹遣荒墀B加的，只能存儲轉(zhuǎn)發(fā)。這樣的組播樹的建立方式就會導(dǎo)致信源S與信宿T2后面的信宿建立的路徑都不是以它們之間的最大流進(jìn)行傳輸?shù)摹６W(wǎng)絡(luò)編碼的提出就是為了解決這個問題，以實現(xiàn)由最大流最小割定理給定的一個通信網(wǎng)絡(luò)的容量上限。為了進(jìn)一步說明網(wǎng)絡(luò)編碼的原理，下面給出一個經(jīng)典的例子。如圖1所示，在這個蝶式網(wǎng)絡(luò)中，每個邊代表一個直接鏈路，每次可以可靠地傳輸一個包。源端S有2個包b1和b2，想要都發(fā)送給t1和t2。在如圖1(a)所示的傳統(tǒng)路由模式中，中間節(jié)點只能對接收到的數(shù)據(jù)包復(fù)制和轉(zhuǎn)發(fā)，即3到4的鏈路每次只能傳輸b1或者b2，這條鏈路不得不使用2次才能達(dá)到目的，節(jié)點t1和t2最后一共收到3個包,平均速率為1.5個包/單位時間；圖1(b)中采用了網(wǎng)絡(luò)編碼，節(jié)點3對數(shù)據(jù)報進(jìn)行了異或處理，將處理后的數(shù)據(jù)包轉(zhuǎn)發(fā)出去，這樣一次傳輸就可以將b1⊕b2傳到節(jié)點4，由于t1和t2已經(jīng)接收到了b1和b2,所以再次進(jìn)行異或操作便可以得到b2和b1。這樣所能達(dá)到的平均速率為2個包/單位時間。從這個例子可以清楚地看到，網(wǎng)絡(luò)編碼能夠提高網(wǎng)絡(luò)吞吐量，保證負(fù)載均衡，減少傳輸次數(shù)，縮短網(wǎng)絡(luò)延時。

    網(wǎng)絡(luò)編碼主要分為以下幾種類型[2]：如果網(wǎng)絡(luò)中所有節(jié)點對其輸入信息進(jìn)行線性操作，則稱之為線性網(wǎng)絡(luò)編碼，反之為非線性編碼；同樣如果網(wǎng)絡(luò)節(jié)點對信息進(jìn)行操作的系數(shù)是隨機(jī)選取的，則為隨機(jī)網(wǎng)絡(luò)編碼，否則為確定網(wǎng)絡(luò)編碼。
2 網(wǎng)絡(luò)編碼的優(yōu)缺點
    網(wǎng)絡(luò)編碼最初是用來解決網(wǎng)絡(luò)中組播的最大流問題，從而提高組播的吞吐量。隨著研究的深入，其他方面的優(yōu)點也逐漸體現(xiàn)出來。
    (1) 提升網(wǎng)絡(luò)吞吐量。吞吐量的提升是網(wǎng)絡(luò)編碼的主要優(yōu)點，可以在一條鏈路上同時傳送多個信息流，提高了鏈路的利用率。無論是多播還是單播，均勻鏈路還是非均勻鏈路，都能提升其吞吐量。
    (2) 減小傳輸能耗。在無線網(wǎng)絡(luò)中,應(yīng)用網(wǎng)絡(luò)編碼可以減小節(jié)點的能耗。以廣播代替單播，減少發(fā)送的次數(shù)，這在無線傳感器網(wǎng)絡(luò)中有重要的應(yīng)用。
    (3) 均衡網(wǎng)絡(luò)負(fù)載。網(wǎng)絡(luò)編碼可以有效地利用空閑路徑，將網(wǎng)絡(luò)流量分布到更廣泛的網(wǎng)絡(luò)上，進(jìn)行均衡網(wǎng)絡(luò)負(fù)載。這有助于解決網(wǎng)絡(luò)擁塞等問題。
    網(wǎng)絡(luò)編碼還具有魯棒性、自適應(yīng)性、增加傳輸?shù)陌踩缘葍?yōu)點。但是，由于網(wǎng)絡(luò)編碼增加了中間節(jié)點的計算復(fù)雜性，且信息的恢復(fù)需要收到足夠的包，因此網(wǎng)絡(luò)編碼增加了傳輸時延、節(jié)點的額外資源消耗以及信息的同步問題。這對網(wǎng)絡(luò)編碼的應(yīng)用提出了挑戰(zhàn)。
3 網(wǎng)絡(luò)編碼的應(yīng)用
    網(wǎng)絡(luò)編碼的理論提出來已經(jīng)有一段時間了，隨著研究的不斷深入,從有線到無線已經(jīng)有了一些具體的應(yīng)用，下面對網(wǎng)絡(luò)編碼的幾種典型應(yīng)用進(jìn)行介紹。
3.1 P2P下載
  

　　還有其他應(yīng)用如Coded Multicast和LION等方案[3-4]，Coded Multicast通過構(gòu)建多播組,每個接收者建立2條不相交的路徑到發(fā)送者，形成一個冗余的Overlay結(jié)構(gòu)，利用網(wǎng)絡(luò)編碼在這個Overlay上傳送數(shù)據(jù)，從而提高了多播組的吞吐率。LION考慮了P2P網(wǎng)絡(luò)中不同節(jié)點的帶寬不同，在節(jié)點中建立多個Overlay的mesh結(jié)構(gòu)，發(fā)送者將分層的數(shù)據(jù)發(fā)送到對應(yīng)的節(jié)點，每個節(jié)點根據(jù)自己的可用帶寬加入不同數(shù)量的mesh，從而提高吞吐率。
3.2 分布式存儲
    網(wǎng)絡(luò)編碼也可以用到分布式存儲上。Acedanski[5]等人研究了一個網(wǎng)絡(luò)分布式系統(tǒng)中在受限的存儲資源上存儲一個或多個大文件的問題。每個存儲位置選擇一個文件的一部分，而不關(guān)心這個文件存放在哪里，希望文件下載器能夠盡可能少地鏈接存儲器而取得整個文件。對比無編碼存儲和基于傳統(tǒng)糾刪編碼的存儲和基于隨機(jī)線性編碼的存儲三種策略,其仿真結(jié)果表明基于隨機(jī)線性碼的分布式存儲策略在無需全局文件服務(wù)器參與時,其性能接近集中式全局調(diào)度算法。而傳統(tǒng)的基于糾刪編碼則需要中心服務(wù)器占據(jù)大量的附加存儲空間才能完成參數(shù)的恰當(dāng)選擇。
3.3 無線網(wǎng)絡(luò)
    網(wǎng)絡(luò)編碼更加適合于無線網(wǎng)絡(luò)，在無線網(wǎng)絡(luò)中物理信道的廣播特性更能發(fā)揮網(wǎng)絡(luò)編碼的優(yōu)勢。下面介紹當(dāng)前流行的幾種無線網(wǎng)絡(luò)中應(yīng)用網(wǎng)絡(luò)編碼的方法。
3.3.1 無線網(wǎng)狀網(wǎng)
    Katti等提出的基于機(jī)會的網(wǎng)絡(luò)編碼方法(COPE)首次研究了網(wǎng)絡(luò)編碼在無線環(huán)境中的協(xié)議層面上具體實現(xiàn)的問題[6]。在COPE 中, 每個節(jié)點編碼組合數(shù)據(jù)后, 進(jìn)行基于機(jī)會的路由。COPE的主要思想是節(jié)點首先對傳輸信道進(jìn)行偵聽,獲取其鄰居的相關(guān)信息，決定進(jìn)行編碼的機(jī)會，并在本地的先入先出FIFO(First Input First Output)緩存結(jié)構(gòu)內(nèi)進(jìn)行編碼，然后進(jìn)行基于機(jī)會的路由。COPE協(xié)議要求每個節(jié)點利用本地信息各自決定哪些數(shù)據(jù)包需要進(jìn)行編碼以及如何進(jìn)行編碼。若節(jié)點Vi的發(fā)送隊列中的k個數(shù)據(jù)分組p1,p2,…,pk能一起編碼，構(gòu)造一個能被下一跳節(jié)點正確解碼的數(shù)據(jù)分組，則必須滿足以下解碼條件：每個參與編碼的數(shù)據(jù)分組pj的下一跳節(jié)點Vj都獲得除pj之外的其他參與編碼的數(shù)據(jù)分組。
    覃團(tuán)發(fā)等由此提出了一種基于網(wǎng)絡(luò)編碼的無線Mesh路由協(xié)議，應(yīng)用馬爾科夫鏈模型，定義了網(wǎng)絡(luò)編碼感知的路由判據(jù)[7]。代替了傳統(tǒng)的期望傳輸次數(shù)(ETX)、期望傳輸時間(ETT)等判據(jù)，引入了COPE中的期望資源消耗(ERC)判據(jù)，每個節(jié)點都維護(hù)著一個鏈路緩存用來存儲鏈路的ERC信息。一旦鏈路的ERC信息發(fā)生變化，節(jié)點重新計算到達(dá)其他節(jié)點的最優(yōu)路徑。網(wǎng)絡(luò)中的節(jié)點根據(jù)這一判據(jù)作出路由選擇，能增加網(wǎng)絡(luò)編碼機(jī)會，降低網(wǎng)絡(luò)資源消耗，最大化網(wǎng)絡(luò)編碼效率。
3.3.2 無線自組織網(wǎng)絡(luò)
    無線自組網(wǎng)(Ad-Hoc)是近年來研究較多的一種無線網(wǎng)絡(luò)，節(jié)點采用對等的、自配置的方式快速組網(wǎng)，具有靈活性高、成本低等特點。但是也有終端受限、帶寬不足等問題。為了解決Ad-Hoc中的網(wǎng)絡(luò)吞吐量問題，J.Yuan提出了一種利用網(wǎng)絡(luò)編碼優(yōu)化的流路由方法，以此來提升Ad-Hoc網(wǎng)絡(luò)的多播吞吐量[8]。該方法基于一種在網(wǎng)絡(luò)層和物理層平衡鏈路帶寬供需的跨層優(yōu)化策略。J.Yuan等把該問題分解為2個子問題：(1)優(yōu)化網(wǎng)絡(luò)層的多跳路由；(2)優(yōu)化物理層能量分配。他們提出的是一種跨層優(yōu)化的策略，該策略分別在網(wǎng)絡(luò)層和物理層平衡鏈路帶寬的供需，在這種平衡狀態(tài)上，提供了利用網(wǎng)絡(luò)編碼優(yōu)化吞吐量的流路由方法。運(yùn)用網(wǎng)絡(luò)編碼可以在很大程度上提高網(wǎng)絡(luò)吞吐量，但是不可避免地會增加網(wǎng)絡(luò)的復(fù)雜性。
3.3.3 無線傳感器網(wǎng)絡(luò)
    由于無線傳感器網(wǎng)絡(luò)以數(shù)據(jù)為中心，非常適合采用網(wǎng)絡(luò)編碼來發(fā)揮其優(yōu)勢。MIT 的Petrovic等人提出了一種結(jié)合網(wǎng)絡(luò)編碼的、對無線信號不進(jìn)行調(diào)制的策略[9]。運(yùn)用隨機(jī)分布式網(wǎng)絡(luò)編碼，無線信號可以不經(jīng)過調(diào)制直接進(jìn)行傳輸且可以達(dá)到經(jīng)過調(diào)制后的吞吐量。這樣就能節(jié)省大量因為調(diào)制而消耗的能量，且可以降低節(jié)點的成本。不足之處在于為了防止未經(jīng)調(diào)制的無線窄帶信號可能使節(jié)點之間出現(xiàn)不能互相通信的情況，所以要求傳感器網(wǎng)絡(luò)保證一定的節(jié)點密度。
    采用網(wǎng)絡(luò)編碼能獲得網(wǎng)絡(luò)組播的最大流限，特別是在帶寬受限的WSNs中，網(wǎng)絡(luò)編碼對于增大數(shù)據(jù)流可以達(dá)到理論上限。在WSNs中,數(shù)據(jù)是通過一跳或者多跳傳輸?shù)侥康?sink)節(jié)點，網(wǎng)絡(luò)編碼充分利用了無線信道傳輸?shù)奶匦?極大地提高了網(wǎng)絡(luò)的吞吐量。網(wǎng)絡(luò)編碼還可以提高數(shù)據(jù)的正確率，在一定數(shù)據(jù)包受損的情況下，能夠通過解碼還原，因此減小了重傳的次數(shù)，從而降低了能耗,提高了系統(tǒng)的容錯性和魯棒性。
3.4 其他應(yīng)用
    網(wǎng)絡(luò)編碼還可以應(yīng)用到其他網(wǎng)絡(luò)環(huán)境中，如應(yīng)用層多播、網(wǎng)絡(luò)安全等。應(yīng)用層多播是指把多播服務(wù)從網(wǎng)絡(luò)層轉(zhuǎn)移到應(yīng)用層作為應(yīng)用層服務(wù)實現(xiàn)。網(wǎng)絡(luò)層的多播信息流由路由器轉(zhuǎn)發(fā)，而在應(yīng)用層多播中則由端主機(jī)轉(zhuǎn)發(fā)，端主機(jī)具有一定的計算能力，這為網(wǎng)絡(luò)編碼提供了良好的環(huán)境。網(wǎng)絡(luò)編碼還可以應(yīng)用到信息加密中，由于信息本身就是經(jīng)過編碼轉(zhuǎn)換的，因此可以節(jié)省額外的加密操作，攻擊者在沒有得到所有編碼信息的前提下，無法還原出原始信息,這為設(shè)計新的加密算法提供了新的方法。
    網(wǎng)絡(luò)編碼是一個較新的研究領(lǐng)域，它的提出，顛覆了人們對網(wǎng)絡(luò)傳輸流認(rèn)識上的禁錮。越來越多的研究者已經(jīng)被吸引到這一領(lǐng)域來，理論上的完善和實際應(yīng)用的探究都取得了一定的進(jìn)展，線性編碼和非線性編碼已經(jīng)在數(shù)學(xué)上得到了證明，編碼時域大小的確定，編碼方案的選擇也被廣泛關(guān)注。在無線Mesh網(wǎng)絡(luò)中，已經(jīng)有了具體的應(yīng)用網(wǎng)絡(luò)編碼的算法COPE，并且在此基礎(chǔ)上不斷地被改進(jìn)。在P2P文件傳輸中也不斷地涌現(xiàn)出新的網(wǎng)絡(luò)編碼的應(yīng)用方案，此外，在網(wǎng)絡(luò)安全中，網(wǎng)絡(luò)編碼也有用武之地，可以利用信息本身來進(jìn)行加密，可以有效地提高加密的效率?？傊?，網(wǎng)絡(luò)編碼必將對未來網(wǎng)絡(luò)的設(shè)計產(chǎn)生深遠(yuǎn)的影響。
    本文主要介紹了網(wǎng)絡(luò)編碼的理論背景以及網(wǎng)絡(luò)編碼的應(yīng)用方式?？偨Y(jié)了網(wǎng)絡(luò)編碼的優(yōu)缺點，對當(dāng)前的一些網(wǎng)絡(luò)編碼在應(yīng)用方案作了介紹和探討。網(wǎng)絡(luò)編碼在以下幾個方面將有進(jìn)一步研究：網(wǎng)絡(luò)編碼在多徑、多源環(huán)境下的應(yīng)用，與其他領(lǐng)域的技術(shù)相結(jié)合(如編碼與分布式壓縮等)以及如何降低編碼復(fù)雜度、提高編碼效率等。
參考文獻(xiàn)
[1]     AHLSWEDE R, CAI N, LI S R, et al. Network information flow[J].IEEE Transactions on Information Theory,2000.
[2]     黃佳慶, 王帥, 陳文清.網(wǎng)絡(luò)編碼在P2P網(wǎng)絡(luò)中的應(yīng)用[J].中興通訊技術(shù),2009,15(1):37-39.
[3]    ZHU Ying, LI Bao Chun, GUO Jiang. Multicast with network coding in application layer overlay networks[J]. IEEE    Journal of Selected Arears in Communications. 2004, 22(1):107-119.
[4]     ZHAO Jin, YANG Fan, ZHANG Qian, et al.LION:layered overlay multicast with network coding[C]. IEEE Transactions on Multimedia. 2006,8(5):1021-1025.
[5]     ACEDANSKI S, DEB S, MEDARD M, et al. How good  is random linear coding based distributed network storage[C]. The 1st Workshop on Network Coding, Theoryand Applications. 2005.
[6]    KATTI S, KATABI D, WENDJUN H, et al. The importance of being opportunistic: Practical network coding for  wireless environments[C]. 43rd Annual Allert on Conference on Communication, Control and Computing. Monticello: University of Illinois, 2005:134-144.
[7]     覃團(tuán)發(fā)， 廖素蕓，羅會平.支持網(wǎng)絡(luò)編碼的無線Mesh網(wǎng)絡(luò)路由協(xié)議[J].北京郵電大學(xué)學(xué)報，2009，32(1)：16-18.
[8]     YUAN Jun, LI Zong Peng, YU Wei, et al. A cross-layer  optimization framework for multicast in multi-hop wireless networks[C]. Proc. of First International Conference of  Wireless Internet(WICON),Budapest,Hungary,2005:47-54.
[9] PETROVIC D, RAMCHANDRAN K, RABAEY J. Coding  for sensor networks using untuned radios[C]. IEEE 6th Workshop on Signal Processing Advances in Wireless  Communications, 2005:1093-1097.