淺談網絡編碼技術

摘要:傳統的通信網絡節點只對接收到的信息進行存儲和轉發，扮演著轉發器的角色，但是根據網絡信息流中的最大流最小割理論，沒有理由僅讓網絡節點的功能局限于存儲和轉發。網絡節點可以對多條輸入鏈路上收到的數據信息進行一定的線性或非線性處理，然后再發送出去，在接收節點，通過相應的譯碼運算恢復出信源所發的信息。網絡編碼正是基于這種思想產生的。文中首先講述了網絡編碼的基本原理，在此基礎上介紹了目前網絡編碼在通信網絡中的主要應用。在對網絡編碼有了初步認識的基礎上，對于網絡編碼體現出的優缺點作了總結，并對未來的發展方向進行了分析和展望。

關鍵詞:網絡編碼;吞吐量;P2P;網絡安全

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)26-7383-02

1 網絡編碼概述

2000年，香港中文大學的R.W.Yeung和N.Cai首次提出了網絡編碼，其核心思想是在網絡中參與傳輸的節點，其輸出邊上傳輸的數據可以通過該點多條輸入邊上傳輸的數據的某種線性或非線性變換得到，而參與傳輸的所有節點對數據的變換應保證最終所有接收節點可以正確恢復出信源所發送的信息。

網絡編碼的工作原理是把不同的信息轉化成位數更小的“痕跡”，然后在目標節點進行演繹還原，這樣就不必反復傳輸或者復制全部信息了。痕跡可以在多個中間節點間的多條路徑上反復傳遞，然后再被送往最終的目的端點。它不需要額外的容量和路由—只需把信息的痕跡轉換成位流即可，而這種轉換現有的網絡基礎設施是可以支持的。

2 網絡編碼原理

網絡信息流的最大流最小割定理:對于已知的網絡流圖，信源S到信宿T的流量的最大值w等于其最小割的容量[1]，即max flow(S，T)=min C(S，T)。

對于只有一個信宿的網絡，依靠路由就可以獲得最大流。下面看一個具有兩個信宿的多播網絡，如何獲得網絡多播的最大流，通信網絡如圖1所示。

這是一個單信源兩信宿的網絡，假設每條鏈路無時延無差錯，其中S是源節點，Y和Z是目的節點。圖1(a)給出了每條邊的信息速率均為1bit/每單位時間。由最大流最小割定理容易得出從信源到目的節點的最大流均為2。由此得到信源S可以同時發送2bit信息給t1和t2。圖1(b)給出了一種編碼方案，可以看出，為了從信源節點S同時傳輸2bit信息b1b2到目的節點，則在中間節點3處，必須采用網絡編碼，使輸出邊(3，4)傳輸比特的線性組合為b1+b2(模2加)，那么在目的節點t1和t2處才可分別由b1和b1+(b1+b2)，b2和b2+(b1+b2)恢復出所有信息b1b2。如果按照傳統路由方式，在一個單位時間內將無法把b1b2傳輸給節點t1和t2，這就是網絡編碼的優勢。

3 在通信網絡中的應用

網絡編碼的應用潛力巨大，應用領域涉及無線網絡、P2P系統、網絡安全和分布式文件存儲等網絡的多個方面，本文在此作以歸納。

1) 無線網絡

無線網絡的物理層廣播特性和業務流的雙向性非常適合使用網絡編碼最新的熱點集中于物理層網絡編碼、基于編碼的協作方案設計以及實際編碼協議性能評估等。相對于傳統的合作方案，基于網絡編碼的方案在同等的頻譜效率下可達到更高的分集增益。Katti 等人針對無線網狀網提出了基于機會的網絡編碼協議COPE，并在20個節點的網絡測試床上完成了協議實現。這是首個搭建測試床檢驗實際編碼協議性能的研究，結果表明即使在網絡連接動態變化甚至出現擁塞的情況下，COPE 協議仍能有效支持多路單播流[2]。

2) P2P系統

網絡編碼應用在P2P網絡中主要有以下三個方面的好處:第一，減少了文件的下載時間。在一個大范圍分布式的端到端系統中，找到最優的分組發送時間十分復雜，尤其是主機對于底層網絡拓補知之甚少的情況下更是如此，而使用網絡編碼，網絡拓補和發送先后對文件發送時間的影響將會大大減小。第二，由于編碼后的分組具有多樣性的特點，即使服務器在文件下載過程中離線，或某些網絡節點下載結束后立刻離開，都不會產生太大影響，所以基于網絡編碼的方案與一般的方案相比具有更好的健壯性。第三，與基于轉發的協議相比，基于網絡編碼的協議僅僅在刺激合作機制實現的時候，性能受到一點影響。

3) 網絡安全

中繼節點對編碼數據的惡意修改可能會導致網絡編碼使用受限甚至不可用1 消除拜占庭敵手影響一直是網絡編碼安全應用研究中備受關注的問題。有人提出一種用散列函數檢測拜占庭敵手的方法。Jaggi進一步給出了一種多項式復雜度的分布式算法，在可糾正敵手錯誤的前提下，同時達到最優組播速率，該方法無需對編碼節點添加新的功能，對無線和有線網絡均適用。Krohn 等人提出一種基于同態散列函數的方法用于檢測被修改的編碼分組，但該方法需要將計算好的散列值預先通過其他通道分發給所有節點，因此該方法具有一定的局限性。有人利用橢圓曲線算法給出了一種適用于網絡編碼的簽名方案，除了可檢測被修改的分組，還加入了對數據的身份認證功能[3]。

4) 分布式文件存儲

分布式文件存儲是網絡編碼又一個應用熱點。Acedanski 等人研究了在多個存儲資源受限的節點間進行分布式文件存儲的問題，比較了無編碼存儲、基于糾刪碼存儲和采用隨機線性碼存儲3 種策略，仿真結果表明，基于隨機線性碼的分布式存儲策略，在無需全局文件服務器的參與時，其性能接近集中式全局調度算法。

4 主要優缺點簡述

網絡編碼最初是為使多播傳輸達到理論上的最大傳輸容量，從而能取得較路由多播更好的網絡吞吐量。隨著研究的深入，網絡編碼在均衡網絡負載、提升帶寬利用率等方面的優點逐漸凸現。

4.1 提升網絡吞吐量

無論是均勻鏈路還是非均勻鏈路，網絡編碼均能夠獲得更高的多播容量，而且對于節點平均數越大，網絡編碼在網絡吞吐量上的優勢越明顯。從理論上可證明:如果Ω為信源節點的符號空間，∣V∣為通信網絡中的節點數目，則對于每條鏈路都是單位容量的通信網絡，基于網絡編碼的多播的吞吐量是路由多播的Ω(㏒∣V∣)倍[4]。

4.2 均衡網絡負載

網絡編碼多播可有效利用除多播樹路徑外其它的網絡鏈路，可將網絡流量分布于更廣泛的網絡上，從而均衡網絡負載。圖2(a)所示的通信網絡，其各鏈路容量為2。圖2(b)表示的是基于多播樹的路由多播，為使各個信宿節點達到最大傳輸容量，該多播共使用SU、UX、UY、SW和WZ等共5條鏈路，且每條鏈路上傳輸的可行流為2;圖2(c)表示的是基于網絡編碼的多播，假定信源節點S對發送至鏈路SV的信息進行模二加操作，則鏈路SV、VX和VZ上傳輸的信息均為a⊕b，最終信宿X，Y和Z均能同時收到a和b。容易看出，圖2(c)所示的網絡編碼多播所用的傳輸鏈路為9條，比圖2(b)的多播樹傳輸要多4條鏈路，即利用了更廣泛的通信鏈路，因此均衡了網絡負載。網絡編碼的這種特性，有助于解決網絡擁塞等問題。

4.3 提高帶寬利用率

在圖2(b)中的路由多播中，為了使得信宿X，Y和Z能夠同時收到2個單位的信息，共使用了5條通信鏈路，每條鏈路傳輸可行流為2，因此其消耗的總帶寬為:5×2=10。在圖2(c)表示的網絡編碼多播中，共使用了9條鏈路，每條鏈路傳輸可行流為1，其消耗總帶寬為:9×1=9，因此帶寬消耗節省了10%，提高了網絡帶寬利用率。

雖然網絡編碼優點突出，但運用網絡編碼增加了計算的復雜性，而且網路節點需要緩存足夠的輸入信息，因此編碼操作增加了傳輸時延和節點的額外的I/O、CPU消耗。一些學者對網絡編碼的綜合性能進行了初步的研究和探討。統計數據表明，即使應用最有效的隨機網絡編碼，其編碼和譯碼的時間也不容忽視。此外，應用網絡編碼還存在同步問題，這主要是由于信宿節點必須等待收到足夠的編碼信息，才能開始譯碼.同步問題給在實時系統中應用網絡編碼提出了挑戰[5]。

5 未來發展方向

經過多年的快速發展，基于網絡編碼的新理論和新應用不斷涌現，可以說，網絡編碼正給現有網絡帶來變革性的變化。但從研究的深度來看，仍處于探索階段，還存在一些尚未解決的問題或者尚未探索的領域。網絡編碼未來的發展方向主要體現在以下幾個方面:

1) 網絡編碼理論的進一步完善?，F有的網絡編碼理論研究主要集中于單源組播網絡的線性網絡編碼，針對多源組播網絡和非組播網絡的網絡編碼理論研究還遠不夠深入，如何利用非線性網絡編碼優化網絡性能，也是未來一個重要的研究方向。

2) 網絡編碼與其他相關領域的技術的融合。包括網絡編碼和信源編碼Slepian2Wolf 的聯合設計與優化、網絡編碼與信道編碼和調制技術的進一步結合以及網絡編碼與多描述分層編碼的結合等，都是值得關注的方向。

3) 降低網絡編碼的復雜度。網絡編碼對網絡性能的提升伴隨著設計和實現復雜度的增加，綜合考慮性能增益和網絡開銷，實現最小代價的網絡編碼是將來需要深入研究的問題[6]。

4) 網絡編碼在實際網絡和復雜流量條件下的性能改進。網絡編碼在無線網絡和P2P系統中具有廣闊的應用前景。目前涉及實際網絡編碼系統的性能分析和評估的研究還較少。針對實際網絡的拓補結構，結合IP路由技術、交叉層設計思想以及優化理論，實現編碼感知的高效路由和調度算法將成為今后研究的重點問題。此外，在流量動態變化的真實網絡中，具有可變速率的網絡編碼技術也將是值得關注的研究方向[7]。

6 結束語

網絡編碼理論是網絡通信研究領域中的一項重要突破，自從首次提出以來，已迅速發展成一個重要的研究范疇，并對信息論、編碼、通信網絡、網絡交換理論、無線通信、計算機科學、密碼學、運籌學、矩陣理論等領域帶來了深遠影響。網絡編碼已成為現今世界各地一流大學及工業實驗室最熱門的研究領域之一，也是眾多國際研討會的熱門議題。網絡編碼帶給網絡應用一場模式革命。幾年前，微軟以網絡編碼作為核心技術開發出“雪崩”(Avalanche)原型軟件。“雪崩”對于P2P通信的大規模內容分發而言，傳送速度可高出BT(BitTorrent)20%~30%。由于P2P通信占互聯網帶寬的60%以上，所以研究人員估計，未來十年，網絡編碼技術將會產生巨大影響，從計算機通信、無線通信到其他各類通信，都會廣泛地采用網絡編碼。

參考文獻:

[1] 楊行峻，鄭君里.人工神經網絡與盲信號處理[M].北京:清華大學出版社，2003.

[2] 陶少國，黃佳慶，楊宗凱，等.網絡編碼研究綜述[J].小型微型計算機系統.2008，29(4):583-589.

[3] 楊林，鄭剛，胡曉.網絡編碼的研究進展[J].計算機研究與發展，2008，45(3):400-407.

[4] Ho T，Karger D，Medard M，et al.The benefits of coding over routing in a randomized setting[C].Yokohama，Japan:IEEE International Symposium on Information Theory，2003:442.

[5] Tomislav Nad.Promblems with network coding in overlay networks[EB/OL].http://zoo.cs.yale.edu/class/cs490/04-05a.

[6] Lun D S， Ratnakar N， Medard M，et al.Minimum-cost multicast over coded packet networks[J].IEEE Trans on Information Theory，2006，52(6):2608-2623

[7] Fong S L， Yeung R W.Variable-rate linear nerwork coding[C].Chengdu:IEEE Information Theory Workshop，2006.

[8] 彭鐵光.基于多播的網絡編碼研究[J].電腦與信息技術，2008，16(3):23-24.

[9] 崔凱，王麗.網絡編碼技術及其在通信網絡中的應用[J].黑龍江科技信息，2007(4)，46.

[10] 付琳，付志雄.網絡編碼研究[J].科技資訊，2007(7).