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