網絡編碼關鍵理論問題研究

摘 要：網絡編碼理論是信息論的一個重要突破，已成為眾多領域的研究熱點。歸納已有網絡編碼研究中的關鍵理論問題及其研究成果和研究方法，評述解決方案的優點和不足，最后討論了其發展方向。

關鍵詞：網絡編碼； 網絡信息流； 隨機網絡編碼； 多播； 裝箱

中圖分類號：TP393 文獻標志碼：A 文章編號：1001-3695(2008)08-2260-05

Research on key theoretic problems of network coding

HUANG Jia-qing， TAO Shao-guo， XIONG Zhi-qiang， CHENG Wen-qing

(Hubei Provincial Key Laboratory of Smart Internet Technology， Dept. of Electronics Information Engineering， Huazhong University of

Science Technology，Wuhan 430074， China)

Abstract:Network coding is a significant breakthrough in information theory， it has been researched hot-spots in many areas. This paper summarized key theoretic problems of current network coding as well as its achievements and methodologies， in addition to analyzing pros and cons of those solutions. Finally， it discussed the directions.

Key words：network coding(NC); network information flow; random network coding; multicast; packing

網絡編碼(NC)新理論是21世紀在信息論領域中的一個重要突破。其基本思想是允許網絡中間節點參與編碼。Ahlswede等人^[1]以蝴蝶拓撲(圖1)為例證明該理論可以達到網絡的最大容量：考慮具有單位容量、無時延無環有向圖中，信宿R1和R2能否同時收到2 bit信息。在圖1(a)中，由于鏈路UV的瓶頸只能傳送1 bit，從而R2可以達到2 bit，而R1只能收到1 bit，平均吞吐量為1.5 bit；(b)中采用NC后，UV可傳送a與b的編碼(此處為異或)，兩個信宿通過解碼可以同時收到2 bit信息，達到該網絡的最大容量。

NC理論的劃時代意義在于推翻了獨立的比特不能再被壓縮的經典結論，指出網絡信息流(network information flow)可以被壓縮^[2]，從而可進一步提升網絡吞吐量。NC理論因此也被稱為網絡信息流理論。其主要優點^[3]是提升多播網絡吞吐量、改善網絡負載均衡、節省網絡帶寬消耗、節省無線網絡節點能量消耗、提高網絡鏈路魯棒性；主要缺點是因引入編/解碼而復雜性高、因中間節點可以編/解碼而存在安全問題。限于篇幅不再贅述。本文重點綜述了NC關鍵理論問題最新研究進展，包括NC與路由的比較和統一、降低NC復雜性(最小代價NC)、NC碼構造和多源NC問題研究等。

1數學定義

無向圖G=(V，E)，V為所有節點集合，E為無向鏈路集合；有向圖D=(V，A)，A為有向鏈路集合；S為信源，Ri為信宿，M為信宿集合，記為M={R1，R2，…}，S到某Ri的最大流即其最小截記為CS，Ri，多播情況下S到M中所有節點的最大流記為CS， M=h；有限域為F，其大小記為|F|。

無向圖G中，用C(e)表示鏈路e的最大容量；NC的單會話網絡最大吞吐量記為χ(G) [4]；無向圖中的裝箱參數π(G) ^[4]，表示G中可具有的不相交路徑(edge-disjoint path)性質的多播樹總數，即Steiner裝箱數；無向圖中的連接性參數λ(G)^[4]表示每對節點間最小的鏈路連接數；無向圖中強度參數η(G)^[4]描述剖分的連接性，每個剖分p必須保證含有一個信源或信宿，|p|是剖分中的個數，|Ec|表示每個剖分之間的鏈路集合的個數。若P是所有的剖分集合，則η(G)=minp∈P|Ec|/(|p|-1)。

2 NC與路由比較和統一的關鍵問題研究

1）研究內容 a)NC與路由的性能比較。在提升吞吐量方面NC性能比路由優越的前提條件是什么，能否定量給出提升比率的上限。b)NC與路由的統一。如何將NC和路由統一到新的定理，該定理可用于指導新的網絡系統和設備設計。

2）研究方法 a)圖論的方法。這是最直接的方法，常采用與吞吐量直接相關的裝箱和強度參數等^[5]。b)代數學(algebra)理論。Koetter等人^[6]于2003年提出將NC問題與多項式方程建立數學聯系，使得討論NC問題又多了一種有力的數學工具。c)線性規劃法^[7]。

2.1 NC與路由的比較

NC理論提出時主要討論有向圖的情況。后續研究顯示，并非所有情況下，NC性能比路由優越。

可按如下分類進行比較：從拓撲方式分為有向圖（又分有環和無環兩種）和無向圖；從傳輸方式^[7]分為單播(unicast， 1-to-1)、廣播(broadcast， 1-to-all)、多播(multicast， 1-to-m)、多源多播(group multicast， m-to-m)、覆蓋層多播(overlay multicast)；從會話個數分為單會話(single-session)和多會話(multi-session)。

若是多會話路由，需考慮會話間的公平性問題^[7]。但對多會話NC，一般僅對本會話中的內容進行網絡編碼，所以采用疊加技術^[8]可將多會話NC轉換為單會話NC問題。本節僅闡述單會話問題。

針對多源多播，可通過引入分別與多個信源相連的超級節點（鏈路容量設為無窮大），將之轉換為單源多播的情況^[7]。雖然可以轉換，但其理論問題已不是單源NC的簡單擴展^[8]，應歸結為多源NC問題。這與單源信息論和多源信息論具有本質區別是一樣的道理。本節僅闡述單源NC問題，多源NC問題詳見第5章。

為定量評估NC和路由的性能，定義編碼增益(coding advantage， CA) [7]，即采用網絡編碼和未采用時的信息速率之比。當CA=1，表明NC沒有提升吞吐量。在無向圖G中，CA可記為χ(G)/π(G)。

下面將從有向圖和無向圖的分類進行比較:

a）有向圖，分為有向無環圖(acyclic)和有向有環圖(cyclic)兩種。對后者采用柵格技術^[8]，即利用類似卷積碼的原理將有向有環網絡拓撲變成具有無限時間序列上有向無環網絡，可將之轉換為前者。若考慮時延的因素，可通過引入D因子（類似電路中時延模塊z-1）到代數學框架中計算即可^[8]。

（a）單會話單播。由圖論中Menger定理(即最大流最小截定理)可得CA=1^[7]。

(b)單會話廣播。由圖論中Edmond定理，相當于生成樹裝箱問題，得CA=1^[7]。

(c)單會話多播。NC理論提出時主要考慮此情況，也是NC研究得最為充分的情況，有著比較明確的結論，即其CA正比于Ω(log|V|)上升，沒有上界^[7]。采用的技術方法是代數學工具^[6]。

（d）單會話覆蓋層多播。也稱為應用層多播，利用應用層上的單播來間接實現IP層的多播。由于實際上是單播，所以可歸結為單會話單播的情形。Chiu等人^[9]指出NC和路由吞吐量的理論上界是一致的，即CA=1。

存在的不足為在一般情況下，即有環和有時延的情況，雖然有柵格等方法可以用，但因情況較為復雜尚無完整的結論。

NC的優勢是與多播緊密聯系的^[9]，如果在基于單播的應用層，網絡編碼是否能發揮提升吞吐量的優勢存在爭論，典型實例是使用隨機NC的微軟Avalanche^[10]和使用路由的BitTorrent（BT）性能之爭。Avalanche相關論文^[10]顯示其性能比BT好兩三倍；Chiu等人^[9]指出兩者在理論上界是一致的，但同時也指出，采用NC的Avalanche存在比BT性能(采用路由)優越的可能性：Avalanche通過隨機系數選取提升了分塊的多樣性，降低了因BT死檔的可能性；其次，BT作為路由也無法達到最大容量（NPC問題）。因Avalanche的實際軟件暫時未公開，目前尚無完全的定論。

b）無向圖。由于鏈路可雙向使用，且任意雙向使用的流量相加不大于鏈路的容量。需考慮整路由、半整路由和小數路由^[4，7]。

（a）單會話單播。采用圖論法得到χ(G)=π(G)=η(G)的關系，即可得CA=1^[4]。

(b)單會話廣播。采用圖論法得到1/2λ(G)≤π(G)=χ(G)=η(G)≤λ(G)的關系，即可得CA=1^[4]。

(c)單會話多播。采用圖論方法得到1/2λ(G)≤π(G)≤χ(G)≤η(G)≤λ(G) 的關系，只要允許半整路由，CA是有限的且其上限為2^[4]。

(d)單會話覆蓋層多播。采用線性規劃法^[7]來解。下面進行詳述。

Li等人^[7]針對上述無向圖的情況提出相應的線性規劃模型：針對單會話多播(包括單播和廣播)提出概念流的線性規劃模型(cFlow) [7]。其中，概念流定義為不爭奪鏈路容量的網絡流。cFlow模型中需加入有向化的約束條件：令a1=uv， a2=vu，C(a1)+C(a2)=C(e)。其中：e∈E。在認為是能發揮NC優勢的均勻二分圖中利用cFlow得到的結論是CA不高于1.125。對多會話多播則采用mFlow模型^[7]，還加入了多會話概念流的約束條件fij(a)≤fi(a)。對覆蓋層多播則采用oFlow模型^[7]，將底層流gij映射到覆蓋層而構成約束條件，并證明了每個線性模型均可在多項式時間內完成^[7]。

從圖2(a)無向圖中可以看到，不使用NC，僅采用半整數路由，其最大容量為1.5 bit(a、b、c均代表0.5 bit)；當采用如圖2(b)所示的任意小數路由，不使用NC的情況最大容量可以達1.875 bit(其中，a、b、c、e、f、g均代表0.25 bit，而1、2、3為0.125 bit)。無向圖中的情況較為復雜因而存在很多研究的空白點。例如是否可以推論：使用任意小數路由，最大容量是否可以繼續增加；多個單播會話且允許小數路由，CA是否還是1；當半整路由改為整路由，CA上限2是否依然成立。

NC的性能與拓撲和多播有緊密聯系，如何找到NC發揮提升性能的閾值點是當前研究的重點和難點之一。

2.2 NC與路由的統一

NC可看成是路由的超集，而研究者希望能將NC和路由統一到一個更高層次的定理。Wu等人^[11]提出了一個統一定理：首先將鏈路分為Steiner鏈路(進入Steiner節點的鏈路)和非Steiner鏈路，總存在線性時不變(linear time-invariant， LTI)網絡編碼方法，即使NC僅在Steiner鏈路上實施仍可達到CS，M。該統一定理的推廣可將Menger定理、Edmond定理和NC統一起來。采用的方法是硬連技術(圖3)，將非Steiner鏈路硬連到前輩節點，同時保持信源到信宿的連接性，其構造算法的復雜性為O(h3|M||E|)。與圖論中的分裂比較類似，其主要區別是后者在分裂后沒有保持連接性。該統一定理存在的不足是僅針對有向圖。

3 降低NC復雜性的關鍵問題研究

NC需要中間節點參與編/解碼。比較路由而言，節點需增加額外計算和存儲要求，增加了節點復雜性，也引入了較大時延。如何在保持NC提升網絡吞吐量優勢的前提下盡量降低NC復雜性（最小代價NC問題），是NC研究的關鍵問題之一。

研究方法有三種：a）圖論最優化(信息流分解法^[12]和簡單網絡法^[13])；b）線性規劃^[14，15]；c）其他方法，如基因算法^[16]和稀疏矩陣法^[17]等。

3.1 代價定義

在保證較大吞吐量和較高的解碼成功率前提下，代價可以分為如下幾種^[15]：參與NC的節點數最小(所需NC節點數理論上界是多少，如何確定執行NC的節點)；NC的操作數最小(指線性組合的操作數)；參與NC的分組數量最小(尤其在光纖通信中參與NC的節點必須要進行光電轉換，這將增加傳輸時延和降低效率)；消耗的資源最小(指CPU資源、內存資源等)、有限域的大小(在F內選取合適的線性運算系數，并對節點輸入信息進行線性疊加，使得每個信宿節點收到編碼信息后能夠通過高斯消元法正確譯碼。|F|越小占內存越小，但|F|過小解碼成功率也會降低，需折中選擇)。

3.2 基于圖論最優化的方法

1）網絡信息流分解(network information decomposition)法^[12] 按照網絡信息流的共性，將原網絡劃分為一系列子樹圖，該子樹圖中的節點擁有相同的編碼向量，子樹圖中節點的拓撲結構不影響整個系統的多播傳輸，故可將每個子樹看成一個節點來處理。原網絡中每個信宿一定位于h個不同的子樹中，只要包含相同信宿的子樹擁有不同的編碼向量就能保證該信宿最終形成的轉移矩陣滿秩；然后利用圖頂點染色理論，若將每個子樹用一種顏色表示，則只需將包含相同信宿的子樹染成不同的顏色即可。在信源數為2的網絡中有限域大小|F|≤2|M|-7/4+1/2即可使信宿節點成功譯碼。其不足之處是對信源大于2的情況未給出明確的結論。

2）簡單網絡法^[13] 將給定網絡轉換為所有節點度數(入度與出度之和)不超過3的簡單網絡。簡單網絡中參與網絡編碼的節點記為α節點，通過求解α節點的數目，即可確定所需的NC節點數。a）對有向無環網，所需編碼節點數上界為h3|M|2；b）對于有向有環網，所需編碼節點數上界為(2B+1)h3|M|2。其中：B表示去環所需刪除的最少鏈路數。簡單網絡法不足之處是節點數比原網絡擴大了很多，即NC節點數的代價被放大，它求出的最小代價并不等價于原網絡的最小代價。

3.3 基于線性規劃的方法

Lun等人^[14]提出基于最小代價的NC線性規劃模型及其基于線性代價函數和凸代價函數的兩種分布式算法，可兼容一般的路由多播。其主要思路可分為兩步：首先分成最小代價的子圖，然后在該子圖上應用隨機網絡編碼等分布式碼構造算法。

Bhattad等人^[15]提出全新的NC解釋機制。該機制從數學上區分網絡編碼信息流和路由信息流，即給每條鏈路一個向量Xe（該向量包含2|M|-1個元素，每個元素表示由信宿集合M的冪集元素節點對應的流量之和）；然后基于該向量給出信息流的鏈路約束、路由約束和節點約束，由此構造最小代價NC線性規劃模型。該方法的不足之處在于復雜性隨信宿數量的增大而呈指數級增大，不適合在大規模環境中使用。

3.4 其他方法

1）基因法 Kim等人^[16]提出利用遺傳基因理論的有效搜索來減少網絡編碼消耗資源的算法(可支持有環網絡)，但算法屬于半分布式，且遺傳算法需要的參數較多，由此引入的額外計算量還是比較大。

2）稀疏矩陣法 馬冠駿等人^[17]基于稀疏矩陣理論提出一種基于稀疏隨機線性網絡編碼技術的對等網內容分發技術，它較傳統線性隨機編碼在性能上有所改善，但僅降低編碼的復雜性，未能降低解碼復雜性。

多源NC的最小代價問題，可結合多源NC和上述最小代價NC方法來解決。

4 NC碼構造的關鍵問題研究

NC碼構造需解決的主要問題是如何有效求得每條鏈路對應的編碼向量，并運用該編碼向量進行線性操作計算出鏈路上傳輸的信息向量。具體需確定兩個向量^[8]：全局編碼內核fe和局部編碼內核ke。因為線性NC碼具有實現簡單的優點，以下討論若無特別說明，均指線性NC碼。

對網絡某節點T，以T為終點的鏈路集合記為in(T)，以T為起點的鏈路集合記為out(T)。若待傳輸的信息是F中的元素，用長度為ω的行向量表示的消息x記為x∈Fω。每個鏈路e傳輸的信息用f~e(x)表示，從節點T輸入和輸出信息之間的關系可由映射k~e: (f~d(x)，d∈in(T))→f~e(x)惟一確定。其中:e∈out(T)。按照該映射，從信源開始，通過迭代的方法可算出所有鏈路的f~e(x)。

線性網絡編碼分為線性多播、線性廣播和線性擴散^[8]。在線性網絡編碼中，每條鏈路e均存在一個對應的全局編碼向量fe，該向量與信源發送的信息流向量（F上的h維信息向量）的內積即為鏈路e上傳輸的信息流。對于任何非信源節點T，均存在一個由其輸入鏈路e的全局編碼向量fe的集合構成的向量空間VT=〈{fe:e∈in(T)}〉。該向量空間可分為如下三類：

a)對于每個max flow(T)≥h的非源節點T，有dim(VT)=h；

b)對于任意非源節點T，有dim(VT)=min{h， max flow(T)}；

c)對于任意非源節點的集合，有dim(〈∪T∈VT〉)=min{h，max flow()}。

滿足條件a）~c）的網絡編碼分別稱為線性多播、線性廣播和線性擴散。顯然條件c)b)a)，即線性擴散一定是線性廣播，線性廣播一定是線性多播；反之則不一定成立。線性廣播說明了通過增加信源發送的信息流向量的維數，可以提升傳輸速率；線性擴散能保證信源節點以互補的形式發送信息流。文獻[8]最先分別給出線性多播、線性廣播和線性擴散的NC碼構造算法，但算法具有指數復雜性。

4.1 確定性NC碼構造算法

Jaggi等人^[18]提出能夠保證轉移矩陣Mt=A(I-F)-1BT滿秩的具有多項式復雜性的集中式算法。其核心步驟包括：a）構造信源S和信宿R∈M之間建立的h條無重合鏈路構成的路徑簇（S，R），記為fR；b）對fR上的鏈路按照拓撲排序，排序后的鏈路可表示為e1，e2，…，en，然后依次求解各鏈路對應的全局編碼內核fe；c）在求解fe時，必須保證對任意接收節點R∈T存在一個包含h條鏈路的集合CR，且這h條鏈路的全局編碼內核Gt={f(e)|e∈CR}是Fh的一個基。當計算完成時所形成的Gt就是轉移矩陣Mt，則信宿t通過Mt就可以譯出信源發出的信息向量。步驟c）為多項式時間算法的核心和重點。多項式時間網絡編碼算法的時間復雜度為O(|E||M|h2)，最壞情況下為O(|E||M|h(h+|M|2))。

4.2 隨機NC碼構造算法

Ho等人^[19]提出了分布式NC碼構造方法——隨機網絡編碼(random network coding，RNC)。該方法基于一種隨機選擇編碼向量的策略：對于除了信宿節點外的所有中間節點，只要在一個足夠大的F上隨機選擇它們輸入鏈路到輸出鏈路的映射，且各節點映射關系的選取是相互獨立的，就能以較高概率使各個信宿節點對應的轉移矩陣Mt滿秩，從而保證各信宿能以較高的概率成功譯碼。圖4是隨機網絡編碼。各個鏈路上的系數向量（全局編碼向量）和信源發送的信息進行同步傳輸，各個系數向量ξ1，ξ2，…，ξn在F中隨機選取，在通過編碼節點時，系數向量根據隨機選取的映射關系進行更新，最終各信宿收到的輸入信息將包含輸入鏈路對應的全局編碼向量和信源發送的信息流，然后采用高斯消元法正確譯碼。Jaggi等人^[18]指出當|F|=216和|E|=28時解碼成功率可達0.996，而Chou等人^[20]指出|F|=28就足夠實際使用了。微軟提出的P2P文件共享系統Avalanche^[10]便是采用RNC的典型應用。

4.3 多速率碼構造算法

多速率是指若信源節點有q種發送速率ω1，ω2，…，ωq（其中：ωmax是發送速率最大值，且maxflow(T)≥ωmax）。對每個非源節點T，設計構造算法使得所有非源節點根據各自的maxflow(T)來接收信息，從而充分利用網絡資源，相當于一種線性廣播^[21]。最經典的多速率算法是利用Jaggi的多項式算法^[18]獲得q個線性多播算法，然后根據需要調整到適合的接收速率。該方法需要緩存過多的信息而不適合實際使用。Fong等人^[21]提出基于線性廣播算法和減矢量(reduction vector)的變速率快速碼構造算法，并得到線性廣播比線性多播的有限域要大，因為線性廣播碼構造算法涉及的節點數多于線性多播。

4.4 部分NC碼構造問題

常規NC碼構造沒有考慮中間節點的緩存大小，當中間節點的緩存大小大于分塊總數，就存在超時過期的問題。Wang等人^[22]提出部分網絡編碼(partial network coding， PNC)的碼構造方法可以在不解碼的情況下刪除過期的組合。設中間節點緩存大小為B，原始文件分塊為N，常規的線性編碼組合為fi=∑N-1j=0βj×cj。其中：β=(β0，β1，…，βN-1)為系數向量；cj為原始文件分塊。采用PNC，編碼的形式是P={f|f=∑N-1i=N-k-1βi×ci，k∈(0，N-1)}，可以構成一個上三角系數矩陣。由于一般情況下B

上述碼構造算法研究均針對有向網絡，對無向網絡一般情況下的擴展尚需研究。對最小NC的碼構造問題，可以結合最小NC的方法和上述NC碼構造方法加以解決。

5 多源NC的關鍵問題研究

多源NC可看做是多用戶經典信息論的一個新分支，后者本身存在很多空白領域和未完全解；其次，多源NC不是單源NC的簡單擴充^[8]，即使是單源NC也有很多未定論的東西。可見多源NC具有較大研究難度。

5.1 多源NC信息可達速率區域的問題

多源NC信息可達速率區域的問題也是多用戶信息論的經典問題，主要求熵函數中兩個基本參量^[8]，即內界和外界，分別記為Γn和Γn。

研究方法包括：a)類似于信息論的聯合典型序列^[8]，可參見經典的信息論；b）疊加 [8]法，即對不同信源獨立進行編碼，但得到的結論是次優的；c）對內界的研究采用了線性規劃的方法^[23，24]，但未能證明是否緊致；d）對外界的研究采用信宿分解技術^[24]，將信宿按照其接收到源信息的相同個數來復制，該技術在單源NC中可以得到緊致的結論，但在多源NC中能否得到緊致尚未證明。其不足之處在于僅給出基于有向無環圖的結論，并且能否得到緊致的結論是開放問題。

5.2 多源NC和分布式信源編碼聯合及分離問題

1）聯合的問題 重點研究分布式相關信源的聯合編碼問題，因為相關信源存在信息壓縮的問題，在實際(如無線傳感器)中有較大應用價值^[25]。Ho等人^[26]采用代數學方法討論相關信源編碼和NC聯合編碼的問題，給出有時延和無時延的數學模型，得到相關信源下錯誤概率的上界。由于采用RNC的技術，算法是分布式的，但具有聯合編碼復雜性較高的缺點。

2）分離的問題 研究信源編碼和網絡編碼分開編碼與聯合編碼的性能保持一致的條件，其意義在于可以分別獨立地設計最優信源編碼和最優網絡編碼而互不影響，而且最終效果仍是最優，因而提升設計效率。Ramamoorthy等人^[27]討論將多源NC與Slepian-Wolf結合的問題，指出雙源情況下只要當鏈路容量足夠大時，總可保證流分成路由流和編碼流。因此雙信源雙信宿的分離定理總能成立，但更一般的結論尚需完善。

5.3 多源NC碼的構造算法

多源NC碼構造可以分為多源多播和多源單播兩大類，主要解決不同源發出的信息在同一個網絡中勢必互相影響的問題。Wu Yun-nan^[28]提出針對多源多播情況下的一種基于標簽的虛擬管道方案，可以實現無污染的碼構造方法，即每個鏈路被分成打了標簽的虛擬管道，每個標簽是多源的子集，然后引用代數學框架加以解決。對多源單播的情況，就簡化為經典資源劃分的方法；不足之處在于僅針對有向無環圖。

在有向有環的情況下，Harvey等人^[29]研究了多源多匯的因果性問題，但僅討論比較簡單的情況。由于多源間的干擾，使得單源下NC達到最大容量條件變得復雜，多源之間的干擾問題^[30]也是多源NC研究的重點和難點。以上結論多是針對有向無環圖的情況，更一般的情況尚存在許多空白。

6 結束語

本文歸納NC關鍵理論問題研究內容和成果，分類評述相應解決方案和存在的不足。下面討論發展方向：

a)多源NC問題研究。作為多用戶信息論新分支的多源NC存在許多研究空白，其進展將對網絡通信產生深遠影響。NC的Workshop會議都是將多源NC列為首要的研究方向。由于雙源NC是多源NC的基礎，當前一個研究熱點在于雙源NC與分布式信源編碼的聯合和分離問題。多源NC的容量區域問題是開放問題。

b)最小代價NC問題研究。如何減少NC引入的復雜性以保持NC帶來的優勢，是NC的重要研究方向。包括：(a)異構環境下^[31]的最小代價NC，如何在保證較大吞吐量的同時，使弱計算能力的設備不被NC的編/解碼所影響是很關鍵的問題；(b)實時環境下的最小代價NC，如何降低復雜性以降低因編/解碼帶來的額外時延而將NC應用到實時，也是最小代價的重要研究方向，尤其是對NC在流媒體中的應用具有重要實際意義^{[32，33]}；（c)最小代價NC的理論緊致上界問題等都是開放問題。

c)NC與信源編碼、信道編碼聯合與分離問題研究。研究聯合編碼帶來的好處以及分離定理成立的條件，首先要解決的是NC和信源編碼聯合與分離、NC和信道編碼聯合與分離問題?，F在一個研究熱點是NC與Slepian-Wolf的聯合和分離問題。

d)NC安全問題研究。因NC允許中間節點參與編碼，可能存在惡意中間節點添加垃圾信息或破壞信息，從而導致信宿永遠無法正確解碼的嚴重問題。簡單的數字簽名技術無法解決該問題^[10]，針對NC的合適安全機制是NC走向實用化的重要方向。

e)非線性NC問題^[8]。這是亟待開發的領域，可能可以有效降低NC的復雜性，如F域的大小等。該方向的進展一定會帶來驚喜的研究成果。

參考文獻：

[1]AHLSWEDE R， CAI Ning， LI S R， et al. Network information flow[J]. IEEE Trans on Information Theory， 2000，44(4): 1204-1216.

[2]LI S R， YEUNG R W， CAI Ning. Linear network coding[J]. IEEE Trans on Information Theory， 2003， 49(2):371-381.

[3]康巧燕，孟相如，王建峰. 網絡編碼對組播通信的性能改善[J]. 計算機工程與應用， 2007，43(3):150-152，163.

[4]LI Zong-peng， LI Bao-chun. Network coding in undirected networks[C]//Proc of the 38th Annual Conference on Information Science and Systems. Princeton:IEEE Press， 2004:257-262.

[5]WU Yun-nan， CHOU P A， JAIN K. A comparison of network coding and tree packing[C]//Proc of IEEE International Symposium on Information Theory. Chicago:IEEE， 2004.

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

[7]LI Zong-peng， LI Bao-chun， JIANG Dan， et al. On achieving optimal throughput with network coding[C]//Proc of the 24th Annual Joint Conference of IEEE Computer and Communications Societies. Miami:IEEE， 2005:2184-2194.

[8]YEUNG R W， LI S Y R， CAI Ning， et al. Network coding theory[M].Hanover: NOW Publishers Inc， 2006.

[9]CHIU D，YEUNG R W，HUANG Jia-qing， et al. Can network co-ding help in P2P networks[C]//Proc of the 4th International Symposium on Modeling and Optimization in Mobile， Ad hoc and Wireless Networks. Boston:IEEE， 2006:1-5.

[10]GKANTSIDIS C， RODRIGUEZ P R. Network coding for large scale content distribution[C]//Proc of the 24th Annual Joint Conference of IEEE Computer and Communications Societies. Miami:IEEE， 2005: 2235-2245.

[11]WU Yun-nan， JAIN K， KUNG S Y. A unification of network coding and tree-packing(routing) theorems[J]. IEEE Trans on Information Theory， 2006，52(6):2398-2409.

[12]FRAGOULI C， SOLJANIN E. Information flow decomposition for network coding[J]. IEEE Trans on Information Theory， 2006，52(3): 829-848.

[13]LANGBERG M， SPRINTSON A， BRUCK J. The encoding complexity of network coding[J]. IEEE Trans on Information Theory， 2006，52(6):2386-2397.

[14]LUN D S， RATNAKAR N， KOETTER R， et al. Achieving minimum-cost multicast: a decentralized approach based on network co-ding[C]//Proc of the 24th Annual Joint Conference of IEEE Compu-ter and Communications Societies. Miami:IEEE，2005: 1607-1617.

[15]BHATTAD K， RATNAKAR N， KOETTER R，et al. Minimal network coding for multicast[C]//Proc of International Symposium on Information Theory. 2005:1730-1734.

[16]KIM M， MEDARD M， AGGARWAL V， et al.Evolutionary approaches to minimizing network coding resources.[C]// Proc of the 26th IEEE International Conference on Computer Commumications. Anchorage: IEEE， 2007:1991-1999.

[17]馬冠駿，許胤龍，林明宏，等. 基于網絡編碼的P2P內容分發性能分析[J]. 中國科學技術大學學報， 2006， 36(11): 1237-1240.

[18]JAGGI S， SANDERS P， CHOU P A， et al. Polynomial time algorithms for multicast network code construction[J]. IEEE Trans on Information Theory， 2005， 51(6): 1973-1982.

[19]HO T， MEDARD M， KOETTER R， et al. A random linear network coding approach to multicast[J]. IEEE Trans on Information Theo-ry， 2006， 52(10): 4413-4430.

[20]CHOU P A， WU Yun-nan， JAIN K. Practical network coding[C]// Proc of the 41st Allerton Conference on Communication， Control， and Computing. Monticello: Kluwer， 2003.

[21]FONG S L， YEUNG R W. Variable-rate linear network coding[C]// Proc of IEEE Information Theory Workshop. 2006:409-412.

[22]WANG Dan， ZHANG Qian， LIU Jiang-chuan. Partial network co-ding: theory and application for continuous sensor data collection[C]//Proc of the 14th IEEE International Workshop on Quality of Service. 2006:93-101.

[23]YAN Xi-jin， ZHANG Zhen， YANG Jun. Explicit inner and outer bounds for multi-source multi-sink network coding[C]//Proc of IEEE International Symposium on Intormation Theory， 2006:54-58.

[24]YAN Xi-jin， YANG Jun， ZHANG Zhen. An outer bound for multisource multisink network coding with minimum cost consideration[J]. IEEE Trans on Information Theory， 2006， 52(6): 2373-2385.

[25]BARROS J， SERVETTO S D. Network information flow with correlated sources[J]. IEEE Trans on Information Theory， 2006， 52(1): 155-170.

[26]HO T， MEDARD M， EFFROS M， et al. Network coding for correlated sources[C]//Proc of Conference on Information Science and Systems. 2004.

[27]RAMAMOORTHY A， JAIN K， CHOU P A， et al. Separating distri-buted source coding from network coding[J]. IEEE Trans on Information Theory，2006， 52(6): 2785-2795.

[28]WU Yun-nan. On constructive multi-source network coding[C]//Proc of IEEE International Symposium on Intromation Theory.2006:1349-1353.

[29]HARVEY N J A， KLEINBERG R， NAIR C， et al. A “chicken egg” network coding problem[C]//Proc ofIEEE International Symposium on Intormation Theory， 2007.

[30]CAI Kai， FAN Ping-yi. Link decomposition of network coding[C]// Proc of the Asia-Pacific Conference on Communications.2006:1-5.

[31]SUNDARAM N， RAMANATHAN P， BANERJEE S. Multirate media streaming using network coding[C]//Proc of the 43rd Allerton Conference on Communication， Control， and Computing. Monticello: Kluwer， 2005.

[32]CHI Hui-cheng， ZHANG Qian. Deadline-aware network coding for video on demand service over P2P networks[J]. Journal of Zhejiang University: Science A， 2006，7(5):755-763.

[33]劉亞杰，竇文華. 基于網絡編碼的P2P 流媒體[J]. 計算機工程與科學，2006，28(19):33-34，38.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文