【正文】 源節(jié)點(diǎn)的傳輸路徑；步驟4：目的節(jié)點(diǎn)和源節(jié)點(diǎn)之間的傳輸路徑建立完成后，優(yōu)化更新新加入組播圖的所有路徑的鏈路狀態(tài)，包括衰減鏈路成本參數(shù)和鏈路延時(shí)參數(shù)，使得鏈路為更多的目的節(jié)點(diǎn)所共用：步驟5：根據(jù)鏈路的狀態(tài)，為同一目的節(jié)點(diǎn)建立第二條數(shù)據(jù)分發(fā)路徑，選擇鏈路不在第一條路徑上，并且能夠使傳輸時(shí)延達(dá)到最小的鄰接節(jié)點(diǎn)作為其父節(jié)點(diǎn)；步驟6：所選定的父節(jié)點(diǎn)如果是組播圖中的源節(jié)點(diǎn)，則執(zhí)行步驟7，否則繼續(xù)執(zhí)行步驟5，直至完整建立好一條通往源節(jié)點(diǎn)的傳輸路徑；步驟7：第二條傳輸路徑建立完成后，優(yōu)化更新新加入組播圖的所有路徑的鏈路狀態(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ù)吞吐能力。這里，多條不相交的數(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í)間上的競爭，它們之間是線性無關(guān)的。 不相交的冗余路徑(對(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ì)鏈路的競爭沖突，提高組播通信的吞吐量。應(yīng)用層組播是以端系統(tǒng)為基礎(chǔ)的邏輯覆蓋網(wǎng)(overlay network)，不同與以往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ù)涞逆溌飞闲纬山徊婀蚕礞溌?，因此采用傳統(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)之間的通信，可能要通過中間其他端系統(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)行了比較：圖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 network)架構(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ù)載平衡三、節(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)勢在傳統(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(xiàn)表示流經(jīng)邊(的流量，顯然對(duì)所有。因此，節(jié)點(diǎ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)象，即編碼向量之間線性相關(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=Σ：。這里需要指出的是，選擇有限域是