【正文】 路徑的鏈路狀態(tài)，包括衰減鏈路成本參數(shù)和鏈路延時(shí)參數(shù)，使得鏈路為更多的目的節(jié)點(diǎn)所共用。本節(jié)提出的算法作為啟發(fā)式算法的一種，適合運(yùn)用在 P2P等分布式網(wǎng)絡(luò)中，相對(duì)于傳送未編碼原始數(shù)據(jù)塊的傳統(tǒng)分布式內(nèi)容分發(fā)及 P2P對(duì)等通信，通過在由采集節(jié)點(diǎn)、存儲(chǔ)節(jié)點(diǎn)、客戶機(jī)所構(gòu)造的覆蓋網(wǎng)中 Peer之間傳輸經(jīng)過網(wǎng)絡(luò)編碼的數(shù)據(jù)分組，可以有效 提高覆蓋網(wǎng)絡(luò)數(shù)據(jù)吞吐能力。 14 這里，多條不相交的數(shù)據(jù)傳輸路徑的存在使得以往組播進(jìn)行數(shù)據(jù)通信的組播樹演變成組播圖，即由多 棵組播樹的疊加而成。圖 3． 2中，鏈路 m3，U4)就是目的節(jié)點(diǎn) T1和 T2之間的瓶頸鏈路，在節(jié)點(diǎn) U3進(jìn)行網(wǎng)絡(luò)編碼就可以實(shí)現(xiàn)網(wǎng)絡(luò)的最大流傳輸，達(dá)到網(wǎng)絡(luò)的最大容量 2。不相交性保證了對(duì)于發(fā)送至同一個(gè) 目的節(jié)點(diǎn)的不同路徑的數(shù)據(jù)之間不會(huì)存在時(shí)間上的競(jìng)爭(zhēng)，它們之間是線性無關(guān)的。 13 圖 不相交的冗余路徑 (對(duì)于 Tl而言， S． U1． T1和 SU2． U3U4T1分別是 S． T1的兩路不相交路徑 ) 圖 3． 2我們可以看到對(duì)于網(wǎng)絡(luò)中的目的節(jié)點(diǎn) T1存在兩條不相交的路徑通向源節(jié)點(diǎn) S，因此目的節(jié)點(diǎn)能同時(shí)收到多路獨(dú)立數(shù)據(jù)流。但是網(wǎng)絡(luò)編碼不是萬能的，不 是所有的網(wǎng)絡(luò)組播拓?fù)涠寄苁褂?。在分布式拓?fù)渲羞\(yùn)用隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)，即中間節(jié)點(diǎn)對(duì)發(fā)往不同目的節(jié)點(diǎn)的組播數(shù)據(jù)進(jìn)行編碼組合后再轉(zhuǎn)發(fā)，以避開數(shù)據(jù)流對(duì)鏈路的競(jìng)爭(zhēng)沖突，提高組播通信的吞吐量。應(yīng)用層組播是以端系統(tǒng)為基礎(chǔ)的邏輯覆蓋網(wǎng) (overlay work)，不同與以往 m層組播中的路由器節(jié)點(diǎn)，端系統(tǒng)可以提供更為強(qiáng)大的功能，如能夠?qū)?shù)據(jù)進(jìn)行編 碼組合運(yùn)算，這為網(wǎng)絡(luò)編碼在覆蓋網(wǎng)絡(luò)上的應(yīng)用提供了技術(shù)支撐。然而， 從信源到不同信宿之間的最大流經(jīng)過的傳輸路徑可能在網(wǎng)絡(luò)拓?fù)涞逆溌飞闲纬山徊婀蚕礞? 12 路，因此采用傳統(tǒng)的存儲(chǔ)轉(zhuǎn)發(fā)模式即 P組播的方式，無法達(dá)到最大流最小割的理論上限。由前一章可知，網(wǎng)絡(luò)編碼可以實(shí)現(xiàn)網(wǎng)絡(luò)的最大流傳輸。 第二節(jié) 基于網(wǎng)絡(luò)編碼的應(yīng)用層組播路由算法 在日常生活中，我們經(jīng)常要使用到比較大規(guī)模的通信網(wǎng)絡(luò)，我們都希望通信網(wǎng)絡(luò)能為我們提供更為安全、快速的網(wǎng)絡(luò)服務(wù)。例如延時(shí)、延時(shí)抖動(dòng)或者它們的組合。一般通過啟發(fā)式算法求解，典型的啟發(fā)式算法有：MST、 RS、 KMB[31， 321。 此外，還有基于 Steiner樹的問題致力于使組播樹的總代價(jià)最小，這已經(jīng)證明了是圖論中一個(gè) NP． plete問題。如果權(quán)值代表鏈路延時(shí)，則為最小時(shí)延樹。最短路徑樹是從源節(jié)點(diǎn)到所有接收節(jié)點(diǎn)的每條路徑上鏈路權(quán)值之和最小的組播樹。一般來說，組播組用于標(biāo)識(shí)組播轉(zhuǎn)發(fā)時(shí)用的數(shù)據(jù)路徑通常是一棵組播樹。而數(shù)據(jù)拓?fù)渫ǔＪ强刂仆負(fù)涞淖蛹?，它用于?biāo)識(shí)組播轉(zhuǎn)發(fā)時(shí)使用的數(shù)據(jù)路徑。另外，兩個(gè)端系統(tǒng)之間的通信，可能要通過中間 11 其他端系統(tǒng)的轉(zhuǎn)發(fā)來實(shí)現(xiàn)，這也不可避免的造成兩個(gè)通信節(jié)點(diǎn)之間延時(shí)的增加。但從圖 3． 1中可以看出應(yīng)用層組播存在的一些固有問題，如效率不高，多條覆蓋網(wǎng)絡(luò)上的邏輯鏈路可能經(jīng)過物理網(wǎng)絡(luò)的同一鏈路；延遲大，兩 個(gè)節(jié)點(diǎn)之間的通訊可能要通過其它節(jié)點(diǎn)：同步性能差，所有節(jié)點(diǎn)之間很難同步接收數(shù)據(jù)；可能跨越多個(gè)節(jié)點(diǎn)，丟包概率增大。圖 3． 1(b)為應(yīng)用層組播， A發(fā)送兩份相同的數(shù)據(jù)包分別給 B和 C，再由 C復(fù)制一份給 D。 圖 3． 1對(duì) m組播 和應(yīng)用層組播的數(shù)據(jù)傳輸方式進(jìn)行了比較： 10 圖 3． 1 m組播和應(yīng)用層組播的數(shù)據(jù)傳輸方式比較 圖 3． 1中假設(shè) A、 B、 C、 D為四個(gè)端系統(tǒng)主機(jī)， R1， R2為路由器，箭頭方向代表數(shù)據(jù)包的發(fā)送方向。端系統(tǒng)實(shí)現(xiàn)組播業(yè)務(wù)的思想是將組播作為一種疊加的業(yè)務(wù)，實(shí)現(xiàn)為應(yīng)用層的服務(wù)，由此構(gòu)成了應(yīng)用層組播 (application layer multicast) 應(yīng)用層組播是在疊加在 m層之上的用于實(shí)現(xiàn)組播業(yè)務(wù)邏輯的功能性網(wǎng)絡(luò)，應(yīng)用層組播網(wǎng)絡(luò)中的節(jié)點(diǎn)是由組播中的成員主機(jī)構(gòu)成的，并由它們完成數(shù)據(jù)路由、復(fù)制和轉(zhuǎn)發(fā)功能。它的主要優(yōu)點(diǎn)在于它的架構(gòu)，它不需要改變底層網(wǎng)絡(luò)的 結(jié)構(gòu)，可以快速部署所需的網(wǎng)絡(luò)功能。然而口組播增加了網(wǎng)絡(luò)層的復(fù)雜性，而且需要對(duì)現(xiàn)有網(wǎng)絡(luò)的底層設(shè)備進(jìn)行巨大改動(dòng)，因此至今口層組播仍然無法廣泛部署。隨著視頻點(diǎn)播、網(wǎng)絡(luò)電視、遠(yuǎn)程教育等多媒體服務(wù)飛速發(fā)展，中央服務(wù)器的帶寬瓶頸問題日益凸顯，以致集中式的分發(fā)模型逐步向基于 P2P覆蓋網(wǎng)絡(luò) (overlay work)架構(gòu)的分布式結(jié)構(gòu)過渡。采用隨機(jī)網(wǎng)絡(luò)編碼技術(shù)，攻擊者對(duì)接收端收到的其它編碼數(shù)據(jù)無法進(jìn)行預(yù)知和控制，數(shù)據(jù)篡改的影響可以降至最低。 5)信息安全。 4)網(wǎng)絡(luò)管理。 3)無線傳感器網(wǎng)絡(luò)數(shù)據(jù)獲取。 2)應(yīng)用層組播。傳統(tǒng)的分布式內(nèi)容分發(fā)或 P2P對(duì)等通信時(shí)， Peer之間傳送的是未編碼的原始數(shù)據(jù)塊 (block)，諸如 Peer節(jié)點(diǎn)的搜索定位方法、資源分發(fā)與調(diào)度算法優(yōu)化、網(wǎng)絡(luò)負(fù)載平衡以及數(shù)據(jù)分發(fā)路由設(shè)計(jì)等問題都是目前P2P內(nèi)容分發(fā)所面臨的難題。網(wǎng)絡(luò)編碼代表了一種協(xié)同工作的理念，這使得它的應(yīng)用不僅局限于改進(jìn)組播增加網(wǎng)絡(luò)容量，與其它技術(shù)相結(jié)合已經(jīng)應(yīng)用于分布式內(nèi)容存儲(chǔ)與分發(fā)應(yīng)用層組播無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集網(wǎng)絡(luò)管理信息安全等眾多領(lǐng) 域。圖 2． 2(a)中的每個(gè)節(jié)點(diǎn)均以原始格式對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，圖 2． 2∞中的每個(gè)節(jié)點(diǎn)均以網(wǎng)絡(luò)編碼后的格式對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，可以看出，圖 (a)中只能容忍節(jié)點(diǎn) 2或 3中一個(gè)失效或離開，否則系統(tǒng)中的其它節(jié)點(diǎn)就不能剩余節(jié)點(diǎn)中完整地獲取數(shù)據(jù) a、 b、 c、 d；而圈 2． 2(b)中允許任一節(jié)點(diǎn)失效或離 開，其它節(jié)點(diǎn)都能夠自適應(yīng)地做出調(diào)整，重新路由，從剩余的三個(gè)節(jié)點(diǎn)完整地獲取數(shù)據(jù) a、 b、“ d。 四、提高系統(tǒng)的魯棒性和白適應(yīng)性。相比之下，后者可以節(jié)約 10％的系統(tǒng)帶寬。 （ a）網(wǎng)絡(luò)拓補(bǔ)和鏈接容量（ b）傳統(tǒng)傳輸方式（ c）網(wǎng)絡(luò)編碼實(shí)現(xiàn)最大流（ d）負(fù)載平衡 圖 存儲(chǔ)轉(zhuǎn)發(fā)方式與網(wǎng)絡(luò)編碼方式的比較 三、節(jié)約系統(tǒng)帶寬，并有利于負(fù)載平衡。顯然，從 S到 RO=l， 2， 3)的最大流均為4，所以將信息從 S同時(shí)發(fā)送給羈、島和馬時(shí)的最大組播容量也是 4。除了能使得網(wǎng)絡(luò)傳輸達(dá)到組播容量的上限，網(wǎng)絡(luò)編碼的應(yīng)用還可以為系統(tǒng)帶來以下幾方面的益處： 1．提高組播速率，實(shí)現(xiàn)組播最大容量。 二、網(wǎng)絡(luò)編碼的優(yōu)勢(shì) 在傳統(tǒng)的組播通信中，網(wǎng)絡(luò)中的節(jié)點(diǎn)只能存儲(chǔ)轉(zhuǎn)發(fā)所收的數(shù)據(jù)包，當(dāng)信源 s到不同信宿厶之間的最大流經(jīng)過的路徑可能在 G的某些鏈路上形成交叉共享鏈路，進(jìn)而影響共享鏈路之間節(jié)點(diǎn)的數(shù)據(jù)傳輸率，因此采用傳統(tǒng)的存儲(chǔ)轉(zhuǎn)發(fā)模式一般是 不可能達(dá)到最大流最小割定理規(guī)定的組播信息容量上限的。 根據(jù)最大流最小割定理：任何帶發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的網(wǎng)絡(luò)中都存在最大流和最小割，并且最大流的流值等于最小割的容量。對(duì)于包含一個(gè)源節(jié)點(diǎn) s和￡個(gè)匯節(jié)點(diǎn)， V代表頂點(diǎn) (Vcrticc)集合， E代表有向邊 (Edge)集合，用嘞表示邊 (f， j)∈ E的 容量 , ， F表示流經(jīng)邊 (的流量，顯然對(duì)所有。因此，節(jié)點(diǎn)的解碼過程是非常簡(jiǎn)單的，節(jié)點(diǎn)不需要接收指定內(nèi)容的數(shù)據(jù)包，只要接收到足夠數(shù)量的線性無關(guān)的編碼數(shù)據(jù)包，就可以成功恢復(fù)原始數(shù)據(jù)。當(dāng)然 m≥刀并不是充分條件，因?yàn)榉匠讨g有可能出現(xiàn)線性相關(guān)的現(xiàn)象，即編碼向 5 量之間線性相關(guān)。當(dāng)一個(gè)節(jié)點(diǎn)收到 ra個(gè)編碼后的數(shù)據(jù)包后，為了恢復(fù)出萬個(gè)原始數(shù)據(jù)包 ，只需求解以下 方程組： 這是一個(gè)含有刀個(gè)未知數(shù)， m個(gè)方程的線性方程組。假定節(jié)點(diǎn)收到了 m個(gè)信息向量 它對(duì)聊個(gè)信息向量再次編碼 ，生成新的信息向量。x)同時(shí)轉(zhuǎn)發(fā)出去，用于目的節(jié)點(diǎn)對(duì)信息向 量進(jìn)行解碼，恢復(fù)原始信源。組合運(yùn)算的系數(shù) g=(gl，．．．， gn)稱為編碼向量，石稱為信息向量。其中毋就是有限域巧中的元素，它由節(jié)點(diǎn)隨機(jī)產(chǎn)生。 一、編碼過程 假設(shè)一個(gè)或多個(gè)原始信源所發(fā)送的信息由療個(gè)數(shù)據(jù)包 M1，．．．， M^組成，中間節(jié)點(diǎn)可以對(duì)流入其中 的 n個(gè)數(shù)據(jù)包進(jìn)行網(wǎng)絡(luò)編碼，生成 1個(gè)新的數(shù)據(jù)包 x=Σ：。這里需要指出的是，選擇有限域是緣于它的兩條性質(zhì)，其一是有限域中的元素個(gè)數(shù)是有限的，其二是有限域中的元素對(duì)于該有限域所定義的兩種運(yùn)算 (an法和乘法 )是封閉的。 假定流入節(jié)點(diǎn)的每個(gè)數(shù)據(jù)包的包長(zhǎng)度均為￡比特 (較短的數(shù)據(jù)包位數(shù)不夠，在末尾添零補(bǔ)齊 )，如果把這工比特中每連續(xù)的 s比特映射為有限域聰中的一個(gè)元素，那么就可以把這個(gè)數(shù)據(jù)包看成一個(gè)包含∥個(gè)元素的向量。 網(wǎng)絡(luò)編碼是在有限域中進(jìn)行的，主要分為線性和非線性兩種方式。由于網(wǎng)絡(luò)中被傳遞的信息本質(zhì)上就是連續(xù)的比特流，是一系列抽象的代數(shù)符號(hào)，因此信息除了可以被轉(zhuǎn)發(fā)和復(fù)制之外，應(yīng)該還可以進(jìn)行代數(shù)運(yùn)算，網(wǎng)絡(luò)編 碼技術(shù)打破了中間節(jié)點(diǎn)不對(duì)數(shù)據(jù)處理的限制。所謂網(wǎng)絡(luò)編碼，就是指節(jié)點(diǎn)對(duì)輸入的多路信息流進(jìn)行代數(shù)組合運(yùn)算，生成一路或多路新的輸出信息流。但是人們普遍認(rèn)為，中間節(jié)點(diǎn)所進(jìn)行的數(shù)據(jù)處理對(duì)數(shù)據(jù)傳輸過程本身并不會(huì)帶來任何好處。除了數(shù)據(jù)復(fù)制以外，一般來說在網(wǎng)絡(luò)的中間節(jié)點(diǎn)并不需要做任何數(shù)據(jù)處理。最后第五章總結(jié)了全文以及碩士期間的研究工作，并以后工作提出了設(shè)想。第三章在對(duì)比其它傳統(tǒng)組播路由算法的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)編碼提出了新的基于網(wǎng)絡(luò)編碼的分布式應(yīng)用層組播路由算法。第一章中闡述了課題來源、研究目的和意義以及國內(nèi)外本課題研究的現(xiàn)狀?？紤]到應(yīng)用層組播是基于應(yīng)用層端系統(tǒng)之上的，端系