網絡編碼構造算法研究

摘 要：網絡編碼是通信網絡中信息傳輸技術的一個重大突破，其核心思想就是利用路由器的智能化功能，允許網絡中間節點對傳輸信息進行編碼，從而提高網絡傳輸效率。該文通過“蝶形網絡”來分析網絡編碼的基本原理，并歸納現有網絡編碼的基本構造算法及其優缺點，最后討論網絡編碼構造算法的進一步發展方向。

關鍵詞：網絡編碼； 構造算法； 多項式時間算法； 隨機網絡編碼

中圖分類號：TN915-34文獻標識碼：A文章編號：1004-373X(2011)19-0011-04

Research on Construction Algorithm of Network Coding

CHEN Hai-yong1， ZHU Shi-bing2， LI Chang-qing3

(1.Department of Postgraduate， Institute of Command Technology of Equipment， Beijing 101416， China;

2. Department of Training， Institute of Command Technology of Equipment， Beijing 101416， China;

3.Department of The Informational Equipment， Institute of Command Technology of Equipment， Beijing 101416， China)

Abstract： Network coding is an important breakthrough of the information transmission technology in communication network， whose main idea is using the intelligentized function of router and encoding the transmit information by the intermediate node of network to improve the efficiency of network transmission. An example about \"papilionaceous net\" is proposed to analyze the basic theory of network coding， the basic construction algorithm， advantages and shortages of network coding are summarized， and the further development direction of this algorithm is discussed.

Keywords： network coding; construction algorithm; multinomial time algorithm; random network coding

收稿日期：2011-04-11

0 引 言

在傳統的通信網絡及信息傳輸過程中，中間節點都只是完成簡單的存儲轉發功能。2000年，R Ahlswede等人在IEEE Transactions on Information Theory上發表了論文《Network Information Flow》，第一次提出了“網絡編碼”這一概念，論文證明了在單信源組播網絡中，使用網絡編碼可以達到信息傳輸的最大流界，并通過蝴蝶網絡的例子說明傳統路由無法實現最高的傳輸效率［1］。這篇文章是網絡編碼理論發展的開端。

網絡編碼是一種基于網絡層的編碼技術，核心思想就是盡量利用路由器的智能化功能，將傳統的路由器中對數據包先接收再轉發的處理模式提升到允許對接收到的數據包進行組合、編碼等一系列的智能化處理，然后再轉發出去［2］。

1 網絡編碼的基本原理

在研究網絡編碼的過程中，為了能夠給大家一個直觀的印象，能夠更深入地了解網絡編碼的概念，下面將通過著名的“蝶形網絡”進行分析。假定有一個(如圖1所示)通信網絡，它擁有單個信源和2個接收節點，假設每條鏈路都無時延和無差錯，且信道容量為1，即單位時間內可以傳輸一個單位信息量(例如1 b)。圖中，S是信源節點；Y和Z是信宿節點；T，U，W，X是中間節點。源節點S要同時向兩個信宿節點Y和Z發送組播信息。根據圖論的“最大流最小割”定理，該多播的最大理論傳輸容量為2，即理論上信宿Y和Z能夠同時收到信源S發出的2個單位的信息，也就是說能同時收到b1和b2。

圖1 “單信源二信宿”蝴蝶網絡如果是傳統的信息傳輸方式，如圖1(a)所示，鏈路ST→TY和ST→TW→WX→XZ傳送b1，鏈路SU→UZ，和SU→UW→WX→XY傳送b2，信道容量為1的要求約束了鏈路WX，使得鏈路WX無法同時傳輸b1和b2。b1和b2傳輸到節點W時，若WX傳輸b1，則b2需要等待b1傳輸完畢才能傳輸，所以在單位時間內，信宿Y獲得兩個b1，信宿Z獲得b1和b2，該方式不能夠實現最大傳輸容量。如果應用網絡編碼的思想，則如圖1(b)所示，令節點W為編碼節點，b1和b2傳輸到節點W時，W對接收到的b1和b2進行編碼，壓縮傳輸信息流，從而，使得鏈路ST→TY和SU→UZ分別給信宿Y和Z傳輸b1和b2，鏈路WX→XY和WX→XZ給信宿Y和Z傳輸b1⊕b2，Y收到b1和b1⊕b2后，通過譯碼操作b1(b1⊕b2)就能解出b2，因此，信宿Y同時收到了b1和b2。同理，信宿Z也同時收到b1(通過譯碼操作b2(b1⊕b2))和b2，由此，基于網絡編碼思想的傳輸方式能夠實現理論上的最大傳輸容量。

在無環有向網絡中，只要存在鏈路瓶頸，就可以利用網絡編碼來提高其信息傳輸吞吐量。因此，在利用網絡編碼思想時，應該尋找鏈路瓶頸，選擇適宜的網絡編碼節點，應用相關的網絡編碼構造算法，從而實現理論上網絡組播的最大傳輸容量。

2 網絡編碼構造算法

為了便于理解，在介紹網絡編碼構造算法之前，先給出以下兩個定義：

定義1：全局編碼向量

如圖2所示，設X=［x1，x2…，xn］為信源S輸出的n維信息流向量;Zj為第j條鏈路上傳輸的信息流向量;Zj為第j條鏈路上傳輸信息流中關于信源輸出信息流向量的系數，則Zj=ξjXT，則ξTj稱為第j條鏈路的全局編碼向量。

定義2：系統轉移矩陣

如圖2所示，設X為發送的信息流向量;Y為接收的信息流向量;ξj為第j條鏈路上傳輸信息流中關于信源輸出信息流向量的系數，Mi為第i個節點對應的系統轉移矩陣，即Y=X×Mi，其中Mi=［ξ1，ξ2，…，ξj］T。

網絡編碼構造算法解決的主要問題是如何有效求得每條鏈路對應的全局編碼向量，并運用該全局編碼向量進行線性操作，計算出鏈路上傳輸的信息向量。編碼算法的復雜性是衡量網絡編碼能否有效實現的重要依據。網絡編碼構造算法應根據實際的網絡拓撲結構來具體分析。在前期的研究中，人們提出了線性網絡編碼、代數網絡編碼以及隨機網絡編碼等方法。典型的算法包括指數時間算法［3］、多項式時間算法［4］、隨機網絡編碼算法［5］和貪婪算法［6］等。

圖2 一個組播網絡拓撲圖2.1 指數時間算法

設X，Y分別為發送信息向量和接收信息流向量，M1，M2，…，Mt表示各節點對應的系統轉移矩陣，如果det(M1)×det(M2)×…×det(Mt)≠0，可推得M1，M2，…，Mt均為滿秩，以第i個為例，則由Y=X×Mi可求得，X=Y×M-1i，同理，即所有節點均能成功譯碼?；谶@種思想，文獻［3］提出了一種指數時間的網絡編碼構造算法，即指數時間算法，如圖3所示。該算法先假定各條傳輸鏈路的全局編碼向量依次為(ξ1，ξ2，…，ξn)，然后通過選擇函數關系f，f(ξ1，ξ2，…，ξn)=det(M1)×det(M2)×…×det(Mt)≠0，尋找當中一個f(ξ1，ξ2，…，ξn)≠0的點(ξ1，ξ2，…，ξn)，即把該點(ξ1，ξ2，…，ξn)作為各條傳輸鏈路的全局編碼向量。

圖3 指數時間算法流程圖對于“單信源n信宿”的無環有向網絡，若線性編碼多播(Linear Code Multicast，LCM)的最大理論傳輸容量為c，則在有限域Fq(q=2m，m≥log2(nc+1))中，通過指數時間算法總能求得各鏈路對應的編碼向量，從而使各信宿節點能成功譯碼。但是該算法參變量的校驗次數隨著網絡規模成指數增加。因此，該算法對于大規模的網絡不夠實用。

2.2 多項式時間算法

P.Sander等人提出另一個能夠保證轉移矩陣Mt=A(I-F)-1BT滿秩的集中式算法，即多項式時間算法。該算法是線性網絡編碼的快速實現，其目標是在盡可能小的有限域Fq上快速尋找編碼向量。該算法首次將計算復雜性局限在多項式時間范圍內，極大提高了網絡編碼的實用性。

多項式時間算法是一種確定性算法，它的主要步驟包括：

(1) 構造信源S到各個信宿t的鏈路群；

(2) 按照拓撲結構排序，鏈路排序后為e1，e2，…，en；

(3) 選擇各鏈路系數，使得各鏈路群(S，t)的全局編碼向量都能夠形成一個基，從而確保最終形成的轉移矩陣Mt滿秩；

(4) 各信宿根據接收到的信息流和轉移矩陣Mt即可譯出信源發送的信息向量，X=Y×M-1t。

根據多項式時間算法的特性，該算法適合應用于小規模網絡和大規模骨干網等固定網絡拓撲結構。

2.3 隨機網絡編碼算法

M.Medard提出了一種更為普通的分布式網絡編碼的實現方法，即隨機網絡編碼(Random Network Coding，RNC)。該方法基于一種隨機選擇編碼向量的策略，對于除了信宿節點外的所有中間節點，只要在一個足夠大的有限域Fq上隨機選擇它們輸入鏈路到輸出鏈路的映射，而且各節點映射關系的選取是相互獨立的，就能以較高概率使各個信宿節點對應的系統轉移矩陣Mt滿秩，即各信宿節點能以較高的概率成功譯碼。

圖4表示的是隨機網絡編碼，各個鏈路上的系數向量(全局編碼向量)和信源發送的信息進行同步傳輸，各個系數向量ξ1，ξ2，…，ξn在有限域Fq中隨機選取，在通過編碼節點時，系數向量根據隨機選取的映射關系進行更新，最終的各信宿節點收到的輸入信息將包含輸入鏈路對應的全局編碼向量和信源發送的信息流。解碼時，各信宿節點根據接收到的全局編碼向量，形成一個解碼矩陣，依次累計排列，解碼矩陣會經過等價變換成行階梯型，最終變成行最簡型。最初，解碼矩陣為空，當信宿接收到一個已編碼的信息流和其鏈路對應的全局編碼向量時，將該全局編碼向量放入解碼矩陣中。隨后，若接收到某一個信息流對應的全局編碼向量如果可以增加矩陣的秩，則稱之為信息更新流；如果所收到的是非信息更新流，它可以通過等價變換變為零，從而可以忽略。當解碼矩陣變換成最簡型后，方程組得解，即解碼成功。

隨機網絡編碼與多項式時間算法總能保證成功譯碼不同，在隨機網絡編碼中，雖然不能確保最終形成的解碼矩陣滿秩，但由于是隨機選擇編碼向量，那么只要所選擇的編碼符號域足夠大，總可以保證接收節點以較高概率成功譯出信源發送的信息。理論上可證明，當符號域大小為q=216時，任何接收節點均可以至少以概率99.6%成功譯碼［7］。另外，它的復雜性與確定性算法相比要低得多，更容易實現，而且99%以上的譯碼成功率也足以滿足一般需求。再次，隨機網絡編碼是網絡編碼的分布式實現，無需事先獲知整個網絡的拓撲信息，尤其適用于拓撲結構動態變化或者大規模的網絡。對于存在網絡節點和鏈路失效的網絡，隨機網絡編碼可以利用整個網絡的剩余容量來獲得網絡的最佳容量，從而提高多播傳輸的魯棒性。最后，由于在傳輸過程中，隨機網絡編碼同步傳輸了信息流和其對應的全局編碼向量，所以在安全保密工作方面還有待進一步提高防范，加強措施。

圖4 隨機網絡編碼因此，隨機網絡編碼具有重要的理論價值和應用價值，得到了廣泛的關注和應用，微軟提出的P2P文件共享系統Avalanche便是基于RNC的典型應用［8］。

2.4 通用LCM算法

LCM能夠實現的最大理論容量為各信宿節點最大流的最小值，即h=min max flow(ti)，ti∈T。然而，文獻［9］證明了一個更理想的多播容量上限：LCM可以實現信宿節點各自的最大流，即h=max flow(ti)，ti∈T，并稱這樣的線性編碼多播為“通用LCM”(Generic LCM)。顯然“通用LCM”可以實現多速率的網絡編碼，能夠取得比LCM更好的多播傳輸速率和網絡吞吐量。文獻［9］給出了無環有向網絡中實現“通用LCM”的貪婪算法和啟發式算法，但由于計算量大，實現過程過于復雜，因此并不實用。但該文作為對多速率網絡編碼的首次探索，仍具有重要的借鑒意義。

網絡編碼最根本的目標就是通過壓縮網絡傳輸信息流，從而提高傳輸吞吐量，但是不影響信宿最終接收到的信息量。根據實際網絡拓撲結構的具體分析，為了做到充分發揮網絡編碼各構造算法的實際優勢，達到真正實現網絡編碼技術的優化。因此，選擇適當的網絡編碼節點和相應的網絡編碼構造算法是一項非常重要的內容。

3 網絡編碼構造算法的研究發展方向

經過多年的研究發展，網絡編碼構造算法涌現了一些新思路和新方法，本文第二節也給出了幾種典型算法理論實現的具體步驟和優缺點。但是從當前網絡編碼構造算法的研究深度來看，目前網絡編碼構造算法的研究還處于一種探索階段，還有一些沒有解決的問題和未探索的領域。因此，網絡編碼構造算法的研究還需不斷深入，根據目前的研究現狀和相關學者的預測，對網絡編碼構造算法的研究發展趨勢將從以下幾個方面進行展望。

(1) 網絡編碼構造算法的具體應用實現

當前已經給出了很多網絡編碼構造算法的具體方法，有集中式線性網絡編碼算法和分布式隨機網絡編碼算法。但是要在實際具體網絡環境中實現，還需要考慮具體算法的優缺點和實際網絡拓撲結構，一般考慮如何對集中式和分布式兩種極端方法進行折衷，充分發揮各自算法的優點，從而提升整個網絡的性能。

(2) 非線性網絡編碼構造算法的研究

當前線性網絡編碼能夠實現多播傳輸的理論最大流，并提出了幾種實現LCM的有效方法，如多項式時間算法和隨機網絡編碼算法等。但是關于非線性網絡編碼算法的性能特征，目前在這方面的研究還沒有涉足。一般而言，非線性編碼無論是從系統建模，還是算法求解等方面，均表現出較高的要求和難度。非線性網絡編碼構造算法延伸的安全網絡應用也必然是未來的研究方向之一。

(3) 降低網絡編碼構造算法的復雜性

采用網絡編碼可以在很大程度上提高網絡性能，理論上具有很高的實用指導性，但在具體設計和實現上的復雜性不容忽視。如何在不顯著增加網絡開銷的情況下，包括節點的能耗，算法編譯碼的復雜度以及排隊等待時間等，綜合考慮效率和性能；如何實現最小代價的網絡編碼等問題是將來需要進行深入研究的方向。研究降低網絡編碼構造算法的復雜性，實現最小代價的網絡編碼，具有重要的理論意義和實用價值。

(4) 考慮網絡編碼構造算法在有環網絡的應用

目前研究考慮的網絡編碼構造算法，在應用上主要還是基于無環有向網絡，對于有環網絡應用考慮得較少。但是現有具體的實際網絡往往是一種有環的，針對實際要求，可以先將有環網絡看作是一個無環無時延的有向網絡，然后考慮每個節點的時延，給其設定延遲因子，從而將有環網絡分解為無環無時延有向網絡中多級延遲來進行綜合考慮。如何針對具體網絡拓撲結構設定延遲因子以及對無環無時延有向網絡中多級延遲的綜合考慮還有待進一步深入研究。因此，考慮有環網絡的網絡編碼構造算法具有很強的實用意義和價值。

從以上網絡編碼構造算法的發展趨勢可以看出，網絡編碼構造算法以理論為基礎，更注重實際應用；以特例為參考，更強調普適性；以指導性出發，更考慮效率和性能。

4 結 語

網絡編碼構造算法是網絡編碼具體應用的基礎和靈魂。本文歸納了網絡編碼的基本構造算法，分別介紹了指數時間算法、多項式時間算法和隨機網絡編碼算法的基本編譯碼過程以及具體應用的優缺點。最后對網絡編碼構造算法的下一步方向進行了展望。

參 考 文 獻

［1］ AHLSWEDE Rudolf， CAI Ning， LI Shuo-Yen Robert， et al. Network information flow [J] IEEE Trans. on Inform. Theory， 2000，46(4): 1204-1216.

［2］ 樊平毅.網絡信息論［M］.北京：清華大學出版社，2009.

［3］ KOETER R，MEDARD M. An algebraic approach to network coding [J] IEEE/ACM Trans. on Networking， 2003，11(5): 782-795.

［4］ SANDERS P， EGNER S， TOLHUIZEN L. Polynomial time algorithms for network information flow [C] [S.l.]: Proc.15th ACM Symposium on Parallel Algorithms and Architectures， 2003.

［5］ 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.

［6］ ZOSIN Leonid， KHULLER Samir. On directed steiner trees [C] 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002). [S.l.]: [s.n.]， 2002: 59-63.

［7］ HO T， MEDARD M， SHI J， et al.On randomized network coding [C] [S.l.]: Proceedings of 41st Annual Allerton Conference on Communication， Control and Computing， 2003.

［8］ GKANTSIDIS C， RODRIGUEZ P R. Network coding for large scale content distribution [M] [S.l.]: Microsoft Research，2004.

［9］ LI S-Y R，YEUNG R W. Linear network coding [J]IEEE Trans.on Inform. Theory， 2000， 46: 1204-1216.

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