摘 要： 研究了對多播網(wǎng)絡(luò)進行網(wǎng)絡(luò)編碼的方法，提出了一種基于網(wǎng)絡(luò)編碼的應(yīng)用層多播算法。該算法在計算網(wǎng)絡(luò)拓撲時考慮了鏈路的花費。源端和中間節(jié)點使用隨機線性編碼方法進行編碼，在目的端進行解碼操作使得目的端能從亂序的信息和部分丟失的信息中恢復出原始數(shù)據(jù)，提高了網(wǎng)絡(luò)的可靠性。通過對ns-2的擴展并進行仿真實驗，結(jié)果證明了基于網(wǎng)絡(luò)編碼的應(yīng)用層多播算法是可以提高網(wǎng)絡(luò)的吞吐量，并且和網(wǎng)絡(luò)中最大的吞吐量比較接近。在信息塊不是很大的情況下，編碼延遲率的增長是在一定的范圍內(nèi)的。
關(guān)鍵詞： 多播；網(wǎng)絡(luò)編碼；吞吐量
隨著信息技術(shù)的不斷發(fā)展，各種通信網(wǎng)絡(luò)與人們工作生活的各個方面結(jié)合得越來越緊密。網(wǎng)絡(luò)服務(wù)的多樣化以及針對網(wǎng)絡(luò)傳輸質(zhì)量要求的不斷提高，如何提高現(xiàn)有網(wǎng)絡(luò)資源的利用率，優(yōu)化網(wǎng)絡(luò)，已成為當今網(wǎng)絡(luò)通信研究的重要課題之一。傳統(tǒng)的網(wǎng)絡(luò)多播中，網(wǎng)絡(luò)節(jié)點只對數(shù)據(jù)分組進行路由或復制，很難達到網(wǎng)絡(luò)多播的最大傳播容量。而且多播組上的所有接收者以相同的吞吐量接收數(shù)據(jù)。這樣如果從源到特定的接收者之間的通道上有一個瓶頸鏈路，則吞吐量將會被這個瓶頸鏈路的容量所限制。
2000年，AHLSWEDE R[1]等人提出了網(wǎng)絡(luò)編碼，其核心思想是在網(wǎng)絡(luò)中的節(jié)點采用不加冗余的編碼。利用網(wǎng)絡(luò)編碼，網(wǎng)絡(luò)節(jié)點可以把收到的多個數(shù)據(jù)包通過一定的編碼手段重新組包再發(fā)送到下一節(jié)點，接收端收到一定數(shù)量的包后通過解碼獲得數(shù)據(jù)。要對一個任意給定的多播網(wǎng)絡(luò)進行網(wǎng)絡(luò)編碼，目前已有的方法有2種：一種是由Ralf Koeter等人提出的基于代數(shù)結(jié)構(gòu)的網(wǎng)絡(luò)編碼方法[2]，這種方法是一種指數(shù)時間算法。另外一種重要的網(wǎng)絡(luò)編碼方法是由Peter Sanders等人提出的一種多項式時間算法的網(wǎng)絡(luò)編碼方法[3]，這種方法相對第一種方法而言不僅算法復雜度簡化了，而且有一個很大的優(yōu)點，就是在進行從源節(jié)點到各個終端節(jié)點進行傳輸信息之前，先選好從源節(jié)點到各個終端節(jié)點的傳輸路徑。因此，在同樣的信息傳輸速率下減小了對網(wǎng)絡(luò)資源的占用，同時使網(wǎng)絡(luò)編碼變得更簡單。
1 網(wǎng)絡(luò)編碼概念
網(wǎng)絡(luò)中的節(jié)點對信息比特流進行一定的操作，如模2加、“與”、“或”等，而不僅僅是對其進行復制轉(zhuǎn)發(fā)，稱之為網(wǎng)絡(luò)編碼。在參考文獻[1]中，作者給出了一個多播網(wǎng)絡(luò)的例子，采用網(wǎng)絡(luò)編碼時，傳輸速率比僅使用路由、轉(zhuǎn)發(fā)時的要快，并且達到了多播網(wǎng)絡(luò)的速率上限C=min{ci}(ci從信源s到接收節(jié)點ri的最小割最大流值)。LI S Y R[4]等人隨后表明采用線性的網(wǎng)絡(luò)編碼在有限大的域中能夠達到速率上限C。圖1(a)為一個單源二接收多播傳輸網(wǎng)絡(luò)圖，網(wǎng)絡(luò)中邊上標的是鏈路的容量，即1 bit/單位時間。實際網(wǎng)絡(luò)中容量為K bit/單位時間的鏈路可拆開成K條容量為1 bit/單位時間的并行鏈路，因此為簡單起見，圖1中的所有鏈路的容量都為1 bit/單位時間。
假如網(wǎng)絡(luò)中的節(jié)點只對其收到的信息進行復制轉(zhuǎn)發(fā)，則此網(wǎng)絡(luò)多播速率無法達到2 bit/單位時間。因為接收節(jié)點3在1個單位時間內(nèi)只能轉(zhuǎn)發(fā)從節(jié)點1和2過來的2個bit中的1個，如果3轉(zhuǎn)發(fā)從1節(jié)點過來的信息，則接收節(jié)點t1，可以收到2 bit/單位時間，但是接收節(jié)點t2，只能收到1 bit/單位時間。假設(shè)從源發(fā)向節(jié)點1的信息bit為b1，從源發(fā)向節(jié)點2的信息bit為b2。圖1(b)中的節(jié)點3將分別從節(jié)點1和2過來的信息b1和b2進行模2加，然后發(fā)向節(jié)點4，于是接收節(jié)點t1在1個單位時間內(nèi)收到了b1和b1+b2，于是可以通過b1+(b1+b2)=b2運算來得到b2，也就是說，接收節(jié)點t1，在1個單位時間內(nèi)相當于收到了b1和b2。同理可以知道接收節(jié)點t2在1個單位時間內(nèi)也相當于收到了b1和b2于是圖1(b)的傳送方法達到了多播速率(2 bit/單位時間)。
2 一種基于網(wǎng)絡(luò)編碼的應(yīng)用層多播算法
從當前主要的基于網(wǎng)絡(luò)編碼的應(yīng)用層多播算法的比較分析當中可以看到，網(wǎng)絡(luò)編碼應(yīng)用到應(yīng)用層多播需要知道網(wǎng)絡(luò)的拓撲結(jié)構(gòu)?，F(xiàn)有的幾種機制都是基于已知的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，基于代數(shù)的構(gòu)造方式提供了網(wǎng)絡(luò)編碼與應(yīng)用層多播融合的最基本的模型，它引入了轉(zhuǎn)移矩陣來描述輸入變量與輸出變量之間的關(guān)系，使得對于網(wǎng)絡(luò)編碼是怎樣應(yīng)用到應(yīng)用層多播這種機制有了更加清晰的概念，但是這種模型對于具體的網(wǎng)絡(luò)拓撲沒有展開。而基于多項式時間算法，它運用最小割最大流算法構(gòu)造網(wǎng)絡(luò)拓撲，使得這種拓撲結(jié)構(gòu)能更加有效地傳輸編碼信息。然而，它要求拓撲結(jié)構(gòu)是一個無延時的理想狀態(tài)，因此，這種算法求得的網(wǎng)絡(luò)最大吞吐量可能是理想狀態(tài)的。正是基于以上分析，本文提出了一種基于隨機方式的網(wǎng)絡(luò)編碼的應(yīng)用層多播算法，在考慮鏈路花費的情況下，提高網(wǎng)絡(luò)的吞吐率。
2.1 編碼理論
源端將原始的m個信息流編為一組并編碼成n(n≥m)個大小相等的新信息流；中繼節(jié)點對隸屬同組的源端編碼信息流進行重編碼并轉(zhuǎn)發(fā)；目的端收到足夠多的編碼信息流后利用解碼算法恢復出原始信息流。
2.1.1 源端編碼
采用隨機線性碼[5-6]作為網(wǎng)絡(luò)編碼方案，按照產(chǎn)生的先后順序，源端將每m個信息編為一組，記為x1，x2，…xm，并賦予相同的組標識，組標識從0開始遞增，直到增加到某個上限后重新歸零。當源端要發(fā)送該組信息時，從有限域F28[7]中選取m個隨機數(shù)作為編碼系數(shù)g1，g2，…gm，并按照式(1)進行線性編碼，同時將編碼系數(shù)和組標識添加到信息頭部。若要產(chǎn)生n個編碼信息Y共需進行n次相同的編碼操作，n 的大小根據(jù)網(wǎng)絡(luò)狀態(tài)決定。
2.1.2 中間節(jié)點重編碼
中間節(jié)點對一定時間間隔內(nèi)接收的編碼報文進行存儲，并對具有相同組標識的編碼報文進行重編碼，這樣可以進一步降低編碼信息間的線性相關(guān)性，可提高解碼成功概率。假設(shè)中間節(jié)點R收到k個來自編碼信息Y1，Y2，…， 每個信息Yi對應(yīng)的編碼系數(shù)為gi1，gi2，…gim，其中i=1，2，…k。則中間節(jié)點R按照式(2)和式(3)重新產(chǎn)生k個新的編碼信息及編碼系數(shù)hi1，hi2，…hik并繼續(xù)轉(zhuǎn)發(fā)，其中h是針對從有限域中產(chǎn)生的新的編碼向量kil與原始向量gij的內(nèi)積。
2.1.3 目的端解碼
當目的端接收到m(或大于m)組編碼數(shù)據(jù)，就可以采用矩陣轉(zhuǎn)換的方式恢復出原始的m個信息。假設(shè)接收節(jié)點接收到的m組數(shù)據(jù)分別是Y1，Y2，…Ym，則接收節(jié)點進一步判斷這m組數(shù)據(jù)的編碼系數(shù)gi1，gi2，…gim，i=1，2，…m的線性相關(guān)性，若這m組編碼系數(shù)組成的m×m維矩陣滿秩，則可通過公式(4)恢復出原始的m個信息。當目的端接收的編碼數(shù)據(jù)小于m時，可通過消息反饋機制通知上游節(jié)點對緩存的同組編碼數(shù)據(jù)進行重編碼操作并轉(zhuǎn)發(fā)，直至目的端能恢復出m個原始信息為止。
2.2 網(wǎng)絡(luò)拓撲的構(gòu)造
本文考慮每個結(jié)點的最小花費，采用最小費用最大流方法來構(gòu)造傳輸拓撲網(wǎng)。最小費用最大流的基本思想：對于通信網(wǎng)絡(luò)G(V，E)，節(jié)點s，t∈V，從s到t的最大流max flow(s，t)。設(shè)有鏈路(i，j)∈E，鏈路容量為bij，cij是通過鏈路(i，j)傳輸1個單位信息流的費用，求從i到j(luò)的最大流f，使得流量的總費用C(f)為最小，即：
最小費用最大流的求解原理綜合了求最大流的原理和求最短路徑的原理，主要依據(jù)為：若f是流值為W的所有可行流中費用最小者，而P是關(guān)于f的所有可擴充鏈中費用最小的可擴充鏈，則沿P以ε調(diào)整f得到的可行流f′是流值為W+ε的所有可行流中費用最小的可行流。如果已知f是流值為W的最小費用流，關(guān)鍵是要求出關(guān)于f的最小費用的可擴充鏈。所以本算法在原網(wǎng)絡(luò)圖G的基礎(chǔ)上構(gòu)造一個新的賦權(quán)有向圖G′(V，E′)，使其頂點與G的相同，并將G中的每條弧變成兩個相反方向的弧。在網(wǎng)絡(luò)G′中尋求可行流f的最小費用可擴充鏈，即找到節(jié)點i到j(luò)的最短路。算法描述：
3 性能評價
在本實驗中采用最小費用最大流方法來構(gòu)造傳輸拓撲網(wǎng)，生成由80個節(jié)點組成的拓撲結(jié)構(gòu)。每個鏈路的帶寬范圍(1 MB～2 MB)。交換應(yīng)用層數(shù)據(jù)信息的大小(1 KB～35 KB)。網(wǎng)絡(luò)編碼采用有限域F28范圍內(nèi)的隨機線性碼，源端和中間節(jié)點進行編碼和重編碼操作，目的端進行解碼操作。所有的仿真實驗在擴展的ns-2平臺上進行，仿真時間為500 s。
主要從吞吐量和編碼延遲率兩方面考慮該算法的性能。編碼延遲率是所有節(jié)點的編碼時間總和與端到端的延遲的比率。不同的信息塊的大小對編碼延遲率的影響也不同，信息塊大小分別是1 KB、10 KB、15 KB。如圖2所示，信息塊越大，每個節(jié)點的編碼時間越高，編碼延遲率也相應(yīng)地偏高，但增加的幅度是有限的，平穩(wěn)的。網(wǎng)絡(luò)編碼的目的是為了達到網(wǎng)絡(luò)的最大吞吐量。如圖3所示，與基于多項式時間的網(wǎng)絡(luò)編碼的算法比較，二者都比較接近最大吞吐量，但最小費用最大流的吞吐量要小于基于多項式算法達到的吞吐量，因為本方案計算了鏈路的花費，增大了延遲。但通過實驗證明了網(wǎng)絡(luò)編碼確實能夠提高網(wǎng)絡(luò)的吞吐量。
網(wǎng)絡(luò)編碼的提出從本質(zhì)上打破了通信網(wǎng)絡(luò)中傳統(tǒng)的信息處理方式，目前已是通信網(wǎng)絡(luò)研究領(lǐng)域中的一個新的研究熱點。本文提出一種新的基于隨機方式的網(wǎng)絡(luò)編碼的應(yīng)用層多播算法，在計算網(wǎng)絡(luò)拓撲考慮了鏈路的花費，源端和中間節(jié)點使用隨機線性編碼方法，在目的端進行解碼操作使得目的端能從亂序的信息和部分丟失的信息中恢復出原始數(shù)據(jù)，提高了網(wǎng)絡(luò)的可靠性。通過對ns-2的擴展并進行仿真實驗，結(jié)果證明了本文提出的算法可以提高網(wǎng)絡(luò)的吞吐量，與網(wǎng)絡(luò)中最大的吞吐量比較接近。在信息塊不是很大的情況下，編碼延遲率的增長是在一定的范圍內(nèi)的。
參考文獻
[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] 楊林.一種集成網(wǎng)絡(luò)編碼的低軌衛(wèi)星網(wǎng)絡(luò)多徑路由方法[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.