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

關(guān)鍵詞：網(wǎng)絡(luò)編碼； 構(gòu)造算法； 多項式時間算法； 隨機網(wǎng)絡(luò)編碼

中圖分類號：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 引 言

在傳統(tǒng)的通信網(wǎng)絡(luò)及信息傳輸過程中，中間節(jié)點都只是完成簡單的存儲轉(zhuǎn)發(fā)功能。2000年，R Ahlswede等人在IEEE Transactions on Information Theory上發(fā)表了論文《Network Information Flow》，第一次提出了“網(wǎng)絡(luò)編碼”這一概念，論文證明了在單信源組播網(wǎng)絡(luò)中，使用網(wǎng)絡(luò)編碼可以達到信息傳輸?shù)淖畲罅鹘?，并通過蝴蝶網(wǎng)絡(luò)的例子說明傳統(tǒng)路由無法實現(xiàn)最高的傳輸效率［1］。這篇文章是網(wǎng)絡(luò)編碼理論發(fā)展的開端。

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

1 網(wǎng)絡(luò)編碼的基本原理

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

圖1 “單信源二信宿”蝴蝶網(wǎng)絡(luò)如果是傳統(tǒng)的信息傳輸方式，如圖1(a)所示，鏈路ST→TY和ST→TW→WX→XZ傳送b1，鏈路SU→UZ，和SU→UW→WX→XY傳送b2，信道容量為1的要求約束了鏈路WX，使得鏈路WX無法同時傳輸b1和b2。b1和b2傳輸?shù)焦?jié)點W時，若WX傳輸b1，則b2需要等待b1傳輸完畢才能傳輸，所以在單位時間內(nèi)，信宿Y獲得兩個b1，信宿Z獲得b1和b2，該方式不能夠?qū)崿F(xiàn)最大傳輸容量。如果應用網(wǎng)絡(luò)編碼的思想，則如圖1(b)所示，令節(jié)點W為編碼節(jié)點，b1和b2傳輸?shù)焦?jié)點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，由此，基于網(wǎng)絡(luò)編碼思想的傳輸方式能夠?qū)崿F(xiàn)理論上的最大傳輸容量。

在無環(huán)有向網(wǎng)絡(luò)中，只要存在鏈路瓶頸，就可以利用網(wǎng)絡(luò)編碼來提高其信息傳輸吞吐量。因此，在利用網(wǎng)絡(luò)編碼思想時，應該尋找鏈路瓶頸，選擇適宜的網(wǎng)絡(luò)編碼節(jié)點，應用相關(guān)的網(wǎng)絡(luò)編碼構(gòu)造算法，從而實現(xiàn)理論上網(wǎng)絡(luò)組播的最大傳輸容量。

2 網(wǎng)絡(luò)編碼構(gòu)造算法

為了便于理解，在介紹網(wǎng)絡(luò)編碼構(gòu)造算法之前，先給出以下兩個定義：

定義1：全局編碼向量

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

定義2：系統(tǒng)轉(zhuǎn)移矩陣

如圖2所示，設(shè)X為發(fā)送的信息流向量;Y為接收的信息流向量;ξj為第j條鏈路上傳輸信息流中關(guān)于信源輸出信息流向量的系數(shù)，Mi為第i個節(jié)點對應的系統(tǒng)轉(zhuǎn)移矩陣，即Y=X×Mi，其中Mi=［ξ1，ξ2，…，ξj］T。

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

圖2 一個組播網(wǎng)絡(luò)拓撲圖2.1 指數(shù)時間算法

設(shè)X，Y分別為發(fā)送信息向量和接收信息流向量，M1，M2，…，Mt表示各節(jié)點對應的系統(tǒng)轉(zhuǎn)移矩陣，如果det(M1)×det(M2)×…×det(Mt)≠0，可推得M1，M2，…，Mt均為滿秩，以第i個為例，則由Y=X×Mi可求得，X=Y×M-1i，同理，即所有節(jié)點均能成功譯碼?；谶@種思想，文獻［3］提出了一種指數(shù)時間的網(wǎng)絡(luò)編碼構(gòu)造算法，即指數(shù)時間算法，如圖3所示。該算法先假定各條傳輸鏈路的全局編碼向量依次為(ξ1，ξ2，…，ξn)，然后通過選擇函數(shù)關(guā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 指數(shù)時間算法流程圖對于“單信源n信宿”的無環(huán)有向網(wǎng)絡(luò)，若線性編碼多播(Linear Code Multicast，LCM)的最大理論傳輸容量為c，則在有限域Fq(q=2m，m≥log2(nc+1))中，通過指數(shù)時間算法總能求得各鏈路對應的編碼向量，從而使各信宿節(jié)點能成功譯碼。但是該算法參變量的校驗次數(shù)隨著網(wǎng)絡(luò)規(guī)模成指數(shù)增加。因此，該算法對于大規(guī)模的網(wǎng)絡(luò)不夠?qū)嵱谩?/p>

2.2 多項式時間算法

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

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

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

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

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

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

根據(jù)多項式時間算法的特性，該算法適合應用于小規(guī)模網(wǎng)絡(luò)和大規(guī)模骨干網(wǎng)等固定網(wǎng)絡(luò)拓撲結(jié)構(gòu)。

2.3 隨機網(wǎng)絡(luò)編碼算法

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

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

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

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

2.4 通用LCM算法

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

網(wǎng)絡(luò)編碼最根本的目標就是通過壓縮網(wǎng)絡(luò)傳輸信息流，從而提高傳輸吞吐量，但是不影響信宿最終接收到的信息量。根據(jù)實際網(wǎng)絡(luò)拓撲結(jié)構(gòu)的具體分析，為了做到充分發(fā)揮網(wǎng)絡(luò)編碼各構(gòu)造算法的實際優(yōu)勢，達到真正實現(xiàn)網(wǎng)絡(luò)編碼技術(shù)的優(yōu)化。因此，選擇適當?shù)木W(wǎng)絡(luò)編碼節(jié)點和相應的網(wǎng)絡(luò)編碼構(gòu)造算法是一項非常重要的內(nèi)容。

3 網(wǎng)絡(luò)編碼構(gòu)造算法的研究發(fā)展方向

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

(1) 網(wǎng)絡(luò)編碼構(gòu)造算法的具體應用實現(xiàn)

當前已經(jīng)給出了很多網(wǎng)絡(luò)編碼構(gòu)造算法的具體方法，有集中式線性網(wǎng)絡(luò)編碼算法和分布式隨機網(wǎng)絡(luò)編碼算法。但是要在實際具體網(wǎng)絡(luò)環(huán)境中實現(xiàn)，還需要考慮具體算法的優(yōu)缺點和實際網(wǎng)絡(luò)拓撲結(jié)構(gòu)，一般考慮如何對集中式和分布式兩種極端方法進行折衷，充分發(fā)揮各自算法的優(yōu)點，從而提升整個網(wǎng)絡(luò)的性能。

(2) 非線性網(wǎng)絡(luò)編碼構(gòu)造算法的研究

當前線性網(wǎng)絡(luò)編碼能夠?qū)崿F(xiàn)多播傳輸?shù)睦碚撟畲罅?，并提出了幾種實現(xiàn)LCM的有效方法，如多項式時間算法和隨機網(wǎng)絡(luò)編碼算法等。但是關(guān)于非線性網(wǎng)絡(luò)編碼算法的性能特征，目前在這方面的研究還沒有涉足。一般而言，非線性編碼無論是從系統(tǒng)建模，還是算法求解等方面，均表現(xiàn)出較高的要求和難度。非線性網(wǎng)絡(luò)編碼構(gòu)造算法延伸的安全網(wǎng)絡(luò)應用也必然是未來的研究方向之一。

(3) 降低網(wǎng)絡(luò)編碼構(gòu)造算法的復雜性

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

(4) 考慮網(wǎng)絡(luò)編碼構(gòu)造算法在有環(huán)網(wǎng)絡(luò)的應用

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

從以上網(wǎng)絡(luò)編碼構(gòu)造算法的發(fā)展趨勢可以看出，網(wǎng)絡(luò)編碼構(gòu)造算法以理論為基礎(chǔ)，更注重實際應用；以特例為參考，更強調(diào)普適性；以指導性出發(fā)，更考慮效率和性能。

4 結(jié) 語

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

參 考 文 獻

［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］ 樊平毅.網(wǎng)絡(luò)信息論［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］ 陶少國，黃佳慶，楊宗凱，等.網(wǎng)絡(luò)編碼研究綜述［J］.小型微型計算機系統(tǒng)，2008，29(4):583-592.