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

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

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

　　還有其他應用如Coded Multicast和LION等方案[3-4]，Coded Multicast通過構建多播組,每個接收者建立2條不相交的路徑到發送者，形成一個冗余的Overlay結構，利用網絡編碼在這個Overlay上傳送數據，從而提高了多播組的吞吐率。LION考慮了P2P網絡中不同節點的帶寬不同，在節點中建立多個Overlay的mesh結構，發送者將分層的數據發送到對應的節點，每個節點根據自己的可用帶寬加入不同數量的mesh，從而提高吞吐率。
3.2 分布式存儲
    網絡編碼也可以用到分布式存儲上。Acedanski[5]等人研究了一個網絡分布式系統中在受限的存儲資源上存儲一個或多個大文件的問題。每個存儲位置選擇一個文件的一部分，而不關心這個文件存放在哪里，希望文件下載器能夠盡可能少地鏈接存儲器而取得整個文件。對比無編碼存儲和基于傳統糾刪編碼的存儲和基于隨機線性編碼的存儲三種策略,其仿真結果表明基于隨機線性碼的分布式存儲策略在無需全局文件服務器參與時,其性能接近集中式全局調度算法。而傳統的基于糾刪編碼則需要中心服務器占據大量的附加存儲空間才能完成參數的恰當選擇。
3.3 無線網絡
    網絡編碼更加適合于無線網絡，在無線網絡中物理信道的廣播特性更能發揮網絡編碼的優勢。下面介紹當前流行的幾種無線網絡中應用網絡編碼的方法。
3.3.1 無線網狀網
    Katti等提出的基于機會的網絡編碼方法(COPE)首次研究了網絡編碼在無線環境中的協議層面上具體實現的問題[6]。在COPE 中, 每個節點編碼組合數據后, 進行基于機會的路由。COPE的主要思想是節點首先對傳輸信道進行偵聽,獲取其鄰居的相關信息，決定進行編碼的機會，并在本地的先入先出FIFO(First Input First Output)緩存結構內進行編碼，然后進行基于機會的路由。COPE協議要求每個節點利用本地信息各自決定哪些數據包需要進行編碼以及如何進行編碼。若節點Vi的發送隊列中的k個數據分組p1,p2,…,pk能一起編碼，構造一個能被下一跳節點正確解碼的數據分組，則必須滿足以下解碼條件：每個參與編碼的數據分組pj的下一跳節點Vj都獲得除pj之外的其他參與編碼的數據分組。
    覃團發等由此提出了一種基于網絡編碼的無線Mesh路由協議，應用馬爾科夫鏈模型，定義了網絡編碼感知的路由判據[7]。代替了傳統的期望傳輸次數(ETX)、期望傳輸時間(ETT)等判據，引入了COPE中的期望資源消耗(ERC)判據，每個節點都維護著一個鏈路緩存用來存儲鏈路的ERC信息。一旦鏈路的ERC信息發生變化，節點重新計算到達其他節點的最優路徑。網絡中的節點根據這一判據作出路由選擇，能增加網絡編碼機會，降低網絡資源消耗，最大化網絡編碼效率。
3.3.2 無線自組織網絡
    無線自組網(Ad-Hoc)是近年來研究較多的一種無線網絡，節點采用對等的、自配置的方式快速組網，具有靈活性高、成本低等特點。但是也有終端受限、帶寬不足等問題。為了解決Ad-Hoc中的網絡吞吐量問題，J.Yuan提出了一種利用網絡編碼優化的流路由方法，以此來提升Ad-Hoc網絡的多播吞吐量[8]。該方法基于一種在網絡層和物理層平衡鏈路帶寬供需的跨層優化策略。J.Yuan等把該問題分解為2個子問題：(1)優化網絡層的多跳路由；(2)優化物理層能量分配。他們提出的是一種跨層優化的策略，該策略分別在網絡層和物理層平衡鏈路帶寬的供需，在這種平衡狀態上，提供了利用網絡編碼優化吞吐量的流路由方法。運用網絡編碼可以在很大程度上提高網絡吞吐量，但是不可避免地會增加網絡的復雜性。
3.3.3 無線傳感器網絡
    由于無線傳感器網絡以數據為中心，非常適合采用網絡編碼來發揮其優勢。MIT 的Petrovic等人提出了一種結合網絡編碼的、對無線信號不進行調制的策略[9]。運用隨機分布式網絡編碼，無線信號可以不經過調制直接進行傳輸且可以達到經過調制后的吞吐量。這樣就能節省大量因為調制而消耗的能量，且可以降低節點的成本。不足之處在于為了防止未經調制的無線窄帶信號可能使節點之間出現不能互相通信的情況，所以要求傳感器網絡保證一定的節點密度。
    采用網絡編碼能獲得網絡組播的最大流限，特別是在帶寬受限的WSNs中，網絡編碼對于增大數據流可以達到理論上限。在WSNs中,數據是通過一跳或者多跳傳輸到目的(sink)節點，網絡編碼充分利用了無線信道傳輸的特性,極大地提高了網絡的吞吐量。網絡編碼還可以提高數據的正確率，在一定數據包受損的情況下，能夠通過解碼還原，因此減小了重傳的次數，從而降低了能耗,提高了系統的容錯性和魯棒性。
3.4 其他應用
    網絡編碼還可以應用到其他網絡環境中，如應用層多播、網絡安全等。應用層多播是指把多播服務從網絡層轉移到應用層作為應用層服務實現。網絡層的多播信息流由路由器轉發，而在應用層多播中則由端主機轉發，端主機具有一定的計算能力，這為網絡編碼提供了良好的環境。網絡編碼還可以應用到信息加密中，由于信息本身就是經過編碼轉換的，因此可以節省額外的加密操作，攻擊者在沒有得到所有編碼信息的前提下，無法還原出原始信息,這為設計新的加密算法提供了新的方法。
    網絡編碼是一個較新的研究領域，它的提出，顛覆了人們對網絡傳輸流認識上的禁錮。越來越多的研究者已經被吸引到這一領域來，理論上的完善和實際應用的探究都取得了一定的進展，線性編碼和非線性編碼已經在數學上得到了證明，編碼時域大小的確定，編碼方案的選擇也被廣泛關注。在無線Mesh網絡中，已經有了具體的應用網絡編碼的算法COPE，并且在此基礎上不斷地被改進。在P2P文件傳輸中也不斷地涌現出新的網絡編碼的應用方案，此外，在網絡安全中，網絡編碼也有用武之地，可以利用信息本身來進行加密，可以有效地提高加密的效率。總之，網絡編碼必將對未來網絡的設計產生深遠的影響。
    本文主要介紹了網絡編碼的理論背景以及網絡編碼的應用方式。總結了網絡編碼的優缺點，對當前的一些網絡編碼在應用方案作了介紹和探討。網絡編碼在以下幾個方面將有進一步研究：網絡編碼在多徑、多源環境下的應用，與其他領域的技術相結合(如編碼與分布式壓縮等)以及如何降低編碼復雜度、提高編碼效率等。
參考文獻
[1]     AHLSWEDE R, CAI N, LI S R, et al. Network information flow[J].IEEE Transactions on Information Theory,2000.
[2]     黃佳慶, 王帥, 陳文清.網絡編碼在P2P網絡中的應用[J].中興通訊技術,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]     覃團發， 廖素蕓，羅會平.支持網絡編碼的無線Mesh網絡路由協議[J].北京郵電大學學報，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.