摘  要： 研究了對多播網絡進行網絡編碼的方法，提出了一種基于網絡編碼的應用層多播算法。該算法在計算網絡拓撲時考慮了鏈路的花費。源端和中間節點使用隨機線性編碼方法進行編碼，在目的端進行解碼操作使得目的端能從亂序的信息和部分丟失的信息中恢復出原始數據，提高了網絡的可靠性。通過對ns-2的擴展并進行仿真實驗，結果證明了基于網絡編碼的應用層多播算法是可以提高網絡的吞吐量，并且和網絡中最大的吞吐量比較接近。在信息塊不是很大的情況下，編碼延遲率的增長是在一定的范圍內的。
    關鍵詞： 多播；網絡編碼；吞吐量

    隨著信息技術的不斷發展，各種通信網絡與人們工作生活的各個方面結合得越來越緊密。網絡服務的多樣化以及針對網絡傳輸質量要求的不斷提高，如何提高現有網絡資源的利用率，優化網絡，已成為當今網絡通信研究的重要課題之一。傳統的網絡多播中，網絡節點只對數據分組進行路由或復制，很難達到網絡多播的最大傳播容量。而且多播組上的所有接收者以相同的吞吐量接收數據。這樣如果從源到特定的接收者之間的通道上有一個瓶頸鏈路，則吞吐量將會被這個瓶頸鏈路的容量所限制。
　　2000年，AHLSWEDE R[1]等人提出了網絡編碼，其核心思想是在網絡中的節點采用不加冗余的編碼。利用網絡編碼，網絡節點可以把收到的多個數據包通過一定的編碼手段重新組包再發送到下一節點，接收端收到一定數量的包后通過解碼獲得數據。要對一個任意給定的多播網絡進行網絡編碼，目前已有的方法有2種：一種是由Ralf Koeter等人提出的基于代數結構的網絡編碼方法[2]，這種方法是一種指數時間算法。另外一種重要的網絡編碼方法是由Peter Sanders等人提出的一種多項式時間算法的網絡編碼方法[3]，這種方法相對第一種方法而言不僅算法復雜度簡化了，而且有一個很大的優點，就是在進行從源節點到各個終端節點進行傳輸信息之前，先選好從源節點到各個終端節點的傳輸路徑。因此，在同樣的信息傳輸速率下減小了對網絡資源的占用，同時使網絡編碼變得更簡單。
1 網絡編碼概念
　　網絡中的節點對信息比特流進行一定的操作，如模2加、“與”、“或”等，而不僅僅是對其進行復制轉發，稱之為網絡編碼。在參考文獻[1]中，作者給出了一個多播網絡的例子，采用網絡編碼時，傳輸速率比僅使用路由、轉發時的要快，并且達到了多播網絡的速率上限C=min{ci}(ci從信源s到接收節點ri的最小割最大流值)。LI S Y R[4]等人隨后表明采用線性的網絡編碼在有限大的域中能夠達到速率上限C。圖1(a)為一個單源二接收多播傳輸網絡圖，網絡中邊上標的是鏈路的容量，即1 bit/單位時間。實際網絡中容量為K bit/單位時間的鏈路可拆開成K條容量為1 bit/單位時間的并行鏈路，因此為簡單起見，圖1中的所有鏈路的容量都為1 bit/單位時間。
    假如網絡中的節點只對其收到的信息進行復制轉發，則此網絡多播速率無法達到2 bit/單位時間。因為接收節點3在1個單位時間內只能轉發從節點1和2過來的2個bit中的1個，如果3轉發從1節點過來的信息，則接收節點t1，可以收到2 bit/單位時間，但是接收節點t2，只能收到1 bit/單位時間。假設從源發向節點1的信息bit為b1，從源發向節點2的信息bit為b2。圖1(b)中的節點3將分別從節點1和2過來的信息b₁和b₂進行模2加，然后發向節點4，于是接收節點t1在1個單位時間內收到了b1和b₁+b₂，于是可以通過b₁+(b₁+b₂)=b₂運算來得到b₂，也就是說，接收節點t₁，在1個單位時間內相當于收到了b₁和b₂。同理可以知道接收節點t2在1個單位時間內也相當于收到了b₁和b₂于是圖1(b)的傳送方法達到了多播速率(2 bit/單位時間)。

2 一種基于網絡編碼的應用層多播算法
　　從當前主要的基于網絡編碼的應用層多播算法的比較分析當中可以看到，網絡編碼應用到應用層多播需要知道網絡的拓撲結構。現有的幾種機制都是基于已知的網絡拓撲結構，基于代數的構造方式提供了網絡編碼與應用層多播融合的最基本的模型，它引入了轉移矩陣來描述輸入變量與輸出變量之間的關系，使得對于網絡編碼是怎樣應用到應用層多播這種機制有了更加清晰的概念，但是這種模型對于具體的網絡拓撲沒有展開。而基于多項式時間算法，它運用最小割最大流算法構造網絡拓撲，使得這種拓撲結構能更加有效地傳輸編碼信息。然而，它要求拓撲結構是一個無延時的理想狀態，因此，這種算法求得的網絡最大吞吐量可能是理想狀態的。正是基于以上分析，本文提出了一種基于隨機方式的網絡編碼的應用層多播算法，在考慮鏈路花費的情況下，提高網絡的吞吐率。
2.1 編碼理論
    源端將原始的m個信息流編為一組并編碼成n(n≥m)個大小相等的新信息流；中繼節點對隸屬同組的源端編碼信息流進行重編碼并轉發；目的端收到足夠多的編碼信息流后利用解碼算法恢復出原始信息流。
2.1.1 源端編碼
    采用隨機線性碼[5-6]作為網絡編碼方案，按照產生的先后順序，源端將每m個信息編為一組，記為x₁，x₂，…x_m，并賦予相同的組標識，組標識從0開始遞增，直到增加到某個上限后重新歸零。當源端要發送該組信息時，從有限域F₂^8[7]中選取m個隨機數作為編碼系數g₁，g₂，…g_m，并按照式(1)進行線性編碼，同時將編碼系數和組標識添加到信息頭部。若要產生n個編碼信息Y共需進行n次相同的編碼操作，n 的大小根據網絡狀態決定。
   
2.1.2 中間節點重編碼
    中間節點對一定時間間隔內接收的編碼報文進行存儲，并對具有相同組標識的編碼報文進行重編碼，這樣可以進一步降低編碼信息間的線性相關性，可提高解碼成功概率。假設中間節點R收到k個來自編碼信息Y₁，Y₂，…， 每個信息Yi對應的編碼系數為g_i1，g_i2，…g_im，其中i=1，2，…k。則中間節點R按照式(2)和式(3)重新產生k個新的編碼信息及編碼系數h_i1，h_i2，…h_ik并繼續轉發，其中h是針對從有限域中產生的新的編碼向量k_il與原始向量g_ij的內積。
   
2.1.3 目的端解碼
    當目的端接收到m(或大于m)組編碼數據，就可以采用矩陣轉換的方式恢復出原始的m個信息。假設接收節點接收到的m組數據分別是Y₁，Y₂，…Y_m，則接收節點進一步判斷這m組數據的編碼系數g_i1，g_i2，…g_im，i=1，2，…m的線性相關性，若這m組編碼系數組成的m×m維矩陣滿秩，則可通過公式(4)恢復出原始的m個信息。當目的端接收的編碼數據小于m時，可通過消息反饋機制通知上游節點對緩存的同組編碼數據進行重編碼操作并轉發，直至目的端能恢復出m個原始信息為止。
   
2.2 網絡拓撲的構造
    本文考慮每個結點的最小花費，采用最小費用最大流方法來構造傳輸拓撲網。最小費用最大流的基本思想：對于通信網絡G(V，E)，節點s，t∈V，從s到t的最大流max flow(s，t)。設有鏈路(i，j)∈E，鏈路容量為b_ij，c_ij是通過鏈路(i，j)傳輸1個單位信息流的費用，求從i到j的最大流f，使得流量的總費用C(f)為最小，即：
   
    最小費用最大流的求解原理綜合了求最大流的原理和求最短路徑的原理，主要依據為：若f是流值為W的所有可行流中費用最小者，而P是關于f的所有可擴充鏈中費用最小的可擴充鏈，則沿P以ε調整f得到的可行流f′是流值為W+ε的所有可行流中費用最小的可行流。如果已知f是流值為W的最小費用流，關鍵是要求出關于f的最小費用的可擴充鏈。所以本算法在原網絡圖G的基礎上構造一個新的賦權有向圖G′(V，E′)，使其頂點與G的相同，并將G中的每條弧變成兩個相反方向的弧。在網絡G′中尋求可行流f的最小費用可擴充鏈，即找到節點i到j的最短路。算法描述：

3 性能評價
    在本實驗中采用最小費用最大流方法來構造傳輸拓撲網，生成由80個節點組成的拓撲結構。每個鏈路的帶寬范圍(1 MB～2 MB)。交換應用層數據信息的大小(1 KB～35 KB)。網絡編碼采用有限域F₂⁸范圍內的隨機線性碼，源端和中間節點進行編碼和重編碼操作，目的端進行解碼操作。所有的仿真實驗在擴展的ns-2平臺上進行，仿真時間為500 s。
    主要從吞吐量和編碼延遲率兩方面考慮該算法的性能。編碼延遲率是所有節點的編碼時間總和與端到端的延遲的比率。不同的信息塊的大小對編碼延遲率的影響也不同，信息塊大小分別是1 KB、10 KB、15 KB。如圖2所示，信息塊越大，每個節點的編碼時間越高，編碼延遲率也相應地偏高，但增加的幅度是有限的，平穩的。網絡編碼的目的是為了達到網絡的最大吞吐量。如圖3所示，與基于多項式時間的網絡編碼的算法比較，二者都比較接近最大吞吐量，但最小費用最大流的吞吐量要小于基于多項式算法達到的吞吐量，因為本方案計算了鏈路的花費，增大了延遲。但通過實驗證明了網絡編碼確實能夠提高網絡的吞吐量。

    網絡編碼的提出從本質上打破了通信網絡中傳統的信息處理方式，目前已是通信網絡研究領域中的一個新的研究熱點。本文提出一種新的基于隨機方式的網絡編碼的應用層多播算法，在計算網絡拓撲考慮了鏈路的花費，源端和中間節點使用隨機線性編碼方法，在目的端進行解碼操作使得目的端能從亂序的信息和部分丟失的信息中恢復出原始數據，提高了網絡的可靠性。通過對ns-2的擴展并進行仿真實驗，結果證明了本文提出的算法可以提高網絡的吞吐量，與網絡中最大的吞吐量比較接近。在信息塊不是很大的情況下，編碼延遲率的增長是在一定的范圍內的。
參考文獻
[1] AHLSWEDE R， CAI N， LI S Y R，et al. Network information flow[J]. IEEE Transactions on Information Theory， 2000，
46：1204-1216.
[2] KOETER R， MEDARD M. Beyond Routing： An algebraic approach to network coding[C]. 2002 IEEE INFOCOM， 2002.
[3] SANDERS P， EGNER S， TOLHUIZEN L. Polynomial time algorithms for network information flow[C]. In 15th ACM Symposium on Parallel Algorithms and Architectures， 2003：286-294.
[4] LI S Y R， YEUNG R W， CAL N. Linear network coding[J]. IEEE Transactions on Information Theory， 2003，49：371-381.
[5] HO T， KARGER D R， MEDARD M， et a1． The benefits of coding over routing in a randomized setting[C]. IEEE International Symposium on Information Theory-Proceedings， 2003：442.
[6] 楊林.一種集成網絡編碼的低軌衛星網絡多徑路由方法[J].中南大學學報(自然科學版)，2007，38(5)：950-955.
[7] WANG Dan， ZHANG Qian， LIU Jiang Chuan． Partial network coding： theory and application for continuous sensor data collection[C]. 2006 14th International Workshop on Quality of Service(IEEE Cat. No. 06EX1425)， 2006：93-101.