【正文】 的：3)考慮到啟發(fā)式算法不能達到網(wǎng)絡(luò)使用的最優(yōu)，而傳統(tǒng)的優(yōu)化算法集中式的優(yōu)化方式達到網(wǎng)絡(luò)最優(yōu)的同時，需要掌握網(wǎng)絡(luò)的全局狀態(tài)信息，很難應(yīng)用于大規(guī)模P2P的分布式網(wǎng)絡(luò)中。圖4．6和圖4．7分別給出了迭代步長stepsizeO．01和可變步長下的各個組播源節(jié)點發(fā)送速率的變化。圖44組播源節(jié)點速率變化圖(固定步長stepsize==O．01)圖4．5給出了迭代過程中目標(biāo)函數(shù)值的變化情況，在源節(jié)點速率穩(wěn)定以后，目標(biāo)函數(shù)值也隨之穩(wěn)定得到?？梢詫D4．2所示的網(wǎng)絡(luò)拓撲視為圖4．3中的三個組播組，每一個組播中有一個源節(jié)點以及若干中間節(jié)點和目的節(jié)點(組播子網(wǎng))。圖41算法流程圖在分布式網(wǎng)絡(luò)中，我們假設(shè)的節(jié)點和鏈路processor則是按照以下方式對于接收的數(shù)據(jù)進行處理和更新的：從上面的算法，我們可以看出利用次梯度迭代算法對我們的目標(biāo)函數(shù)求解，是～個分布式的，不需要全局信息，能很好的使用與大型網(wǎng)絡(luò)，并且由于源節(jié)點可以提供可伸縮的數(shù)據(jù)流速率，可以應(yīng)用于大規(guī)模異構(gòu)網(wǎng)絡(luò)中。對于一個凸的目標(biāo)函數(shù)在一個線性約束集下，根據(jù)凸函數(shù)最大化問題我們可以知道該最優(yōu)化問題存在唯一的最優(yōu)解。網(wǎng)絡(luò)流平衡約束條件和鏈路帶寬容量約束條件分別由式(4．9．2)和式(4．94)來表示。一、最優(yōu)化問題闡述在進行信息流組播傳輸時，我們的目標(biāo)是希望最大化每一個組播組源節(jié)點的效用，但同時要以合理的速率傳輸盡可能多的信息。當(dāng)源節(jié)點以最小的最大流進行數(shù)據(jù)傳輸?shù)脑?，勢必很多目的?jié)點的資源會被浪費。但是由于網(wǎng)絡(luò)中節(jié)點之間存在的差異，以及分布式網(wǎng)絡(luò)中多個數(shù)據(jù)源節(jié)點的存在使得網(wǎng)絡(luò)鏈路速率的分配和網(wǎng)絡(luò)傳輸成本之間的矛盾越來越明顯。于是，引入對偶變量允∈R”和y∈R7釋放不等式約束和等式約束，可以得到下面的拉格朗日函數(shù)：拉格朗日乘子五和匕被稱為對偶變量。這是由于凸函數(shù)的極值點自身具有良好的性質(zhì)，即凸函數(shù)在其定義域上的任一極點都是其在定義域上的全局最優(yōu)點，且極值點的集合也是凸集。從圖3．8(a)和圖3．8(b)，同樣可以發(fā)現(xiàn)多路徑的方式在增加少量延時的代價下，大大提高了整個網(wǎng)絡(luò)的數(shù)據(jù)流量，從而提高了網(wǎng)絡(luò)服務(wù)質(zhì)量，增加了網(wǎng)絡(luò)帶寬。在傳輸大量數(shù)據(jù)的時候，每一個目的節(jié)點使用多路徑算法找出能逼近最大流的多條路徑同時進行傳輸，結(jié)合網(wǎng)絡(luò)編碼技術(shù)使得每一個目的節(jié)點可以獨立享用整個網(wǎng)絡(luò)資源，從而大大提高了網(wǎng)絡(luò)的吞吐量。然而在建立多條傳輸路徑后，隨之而來的網(wǎng)絡(luò)延時問題將會被擴大，下面的仿真給出了目的節(jié)點在盡可能多建立到源節(jié)點的路徑情況下形成的組播圖與只建立兩條路傳輸路徑(即冗余度為2)的組播圖以及單路徑組播樹之間的性能比較?？紤]到網(wǎng)絡(luò)帶寬的有效增加，新增加的延時可以忽略。 具體圖例說明第三節(jié) 實驗仿真和結(jié)果分析考慮到DDSP(目的驅(qū)動的最短路徑樹算法)[361作為一種基本的目的驅(qū)動型組播路由樹算法，這里選它是被用來做算法比較。因此，對于新申請加入的目的節(jié)點，它既可以通過共用組播圖中的其它目的節(jié)點，也可以通過接入與其鄰接的中間節(jié)點來加入組播拓撲圖。圖3．4(a)表示的是數(shù)據(jù)分組在源節(jié)點處被采集，初始化時，組播拓撲圖中只有源節(jié)點，其他目的節(jié)點并未加入組播組。本節(jié)提出的算法作為啟發(fā)式算法的一種，適合運用在P2P等分布式網(wǎng)絡(luò)中，相對于傳送未編碼原始數(shù)據(jù)塊的傳統(tǒng)分布式內(nèi)容分發(fā)及P2P對等通信，通過在由采集節(jié)點、存儲節(jié)點、客戶機所構(gòu)造的覆蓋網(wǎng)中Peer之間傳輸經(jīng)過網(wǎng)絡(luò)編碼的數(shù)據(jù)分組，可以有效提高覆蓋網(wǎng)絡(luò)數(shù)據(jù)吞吐能力。圖3．2中，鏈路m3，U4)就是目的節(jié)點T1和T2之間的瓶頸鏈路，在節(jié)點U3進行網(wǎng)絡(luò)編碼就可以實現(xiàn)網(wǎng)絡(luò)的最大流傳輸，達到網(wǎng)絡(luò)的最大容量2。 不相交的冗余路徑(對于Tl而言，S．U1．T1和SU2．U3U4T1分別是S．T1的兩路不相交路徑)圖3．2我們可以看到對于網(wǎng)絡(luò)中的目的節(jié)點T1存在兩條不相交的路徑通向源節(jié)點S，因此目的節(jié)點能同時收到多路獨立數(shù)據(jù)流。在分布式拓撲中運用隨機線性網(wǎng)絡(luò)編碼技術(shù)，即中間節(jié)點對發(fā)往不同目的節(jié)點的組播數(shù)據(jù)進行編碼組合后再轉(zhuǎn)發(fā)，以避開數(shù)據(jù)流對鏈路的競爭沖突，提高組播通信的吞吐量。然而，從信源到不同信宿之間的最大流經(jīng)過的傳輸路徑可能在網(wǎng)絡(luò)拓撲的鏈路上形成交叉共享鏈路，因此采用傳統(tǒng)的存儲轉(zhuǎn)發(fā)模式即P組播的方式，無法達到最大流最小割的理論上限。第二節(jié) 基于網(wǎng)絡(luò)編碼的應(yīng)用層組播路由算法在日常生活中，我們經(jīng)常要使用到比較大規(guī)模的通信網(wǎng)絡(luò)，我們都希望通信網(wǎng)絡(luò)能為我們提供更為安全、快速的網(wǎng)絡(luò)服務(wù)。一般通過啟發(fā)式算法求解，典型的啟發(fā)式算法有：MST、RS、KMB[31，321。如果權(quán)值代表鏈路延時，則為最小時延樹。一般來說，組播組用于標(biāo)識組播轉(zhuǎn)發(fā)時用的數(shù)據(jù)路徑通常是一棵組播樹。另外，兩個端系統(tǒng)之間的通信，可能要通過中間其他端系統(tǒng)的轉(zhuǎn)發(fā)來實現(xiàn)，這也不可避免的造成兩個通信節(jié)點之間延時的增加。圖3．1(b)為應(yīng)用層組播，A發(fā)送兩份相同的數(shù)據(jù)包分別給B和C，再由C復(fù)制一份給D。端系統(tǒng)實現(xiàn)組播業(yè)務(wù)的思想是將組播作為一種疊加的業(yè)務(wù)，實現(xiàn)為應(yīng)用層的服務(wù)，由此構(gòu)成了應(yīng)用層組播(application layer multicast)應(yīng)用層組播是在疊加在m層之上的用于實現(xiàn)組播業(yè)務(wù)邏輯的功能性網(wǎng)絡(luò)，應(yīng)用層組播網(wǎng)絡(luò)中的節(jié)點是由組播中的成員主機構(gòu)成的，并由它們完成數(shù)據(jù)路由、復(fù)制和轉(zhuǎn)發(fā)功能。然而口組播增加了網(wǎng)絡(luò)層的復(fù)雜性，而且需要對現(xiàn)有網(wǎng)絡(luò)的底層設(shè)備進行巨大改動，因此至今口層組播仍然無法廣泛部署。采用隨機網(wǎng)絡(luò)編碼技術(shù)，攻擊者對接收端收到的其它編碼數(shù)據(jù)無法進行預(yù)知和控制，數(shù)據(jù)篡改的影響可以降至最低。4)網(wǎng)絡(luò)管理。2)應(yīng)用層組播。網(wǎng)絡(luò)編碼代表了一種協(xié)同工作的理念，這使得它的應(yīng)用不僅局限于改進組播增加網(wǎng)絡(luò)容量，與其它技術(shù)相結(jié)合已經(jīng)應(yīng)用于分布式內(nèi)容存儲與分發(fā)應(yīng)用層組播無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集網(wǎng)絡(luò)管理信息安全等眾多領(lǐng)域。四、提高系統(tǒng)的魯棒性和白適應(yīng)性。（a）網(wǎng)絡(luò)拓補和鏈接容量（b）傳統(tǒng)傳輸方式（c）網(wǎng)絡(luò)編碼實現(xiàn)最大流（d）負載平衡三、節(jié)約系統(tǒng)帶寬，并有利于負載平衡。除了能使得網(wǎng)絡(luò)傳輸達到組播容量的上限，網(wǎng)絡(luò)編碼的應(yīng)用還可以為系統(tǒng)帶來以下幾方面的益處：1．提高組播速率，實現(xiàn)組播最大容量。根據(jù)最大流最小割定理：任何帶發(fā)送節(jié)點和接收節(jié)點的網(wǎng)絡(luò)中都存在最大流和最小割，并且最大流的流值等于最小割的容量。因此，節(jié)點的解碼過程是非常簡單的，節(jié)點不需要接收指定內(nèi)容的數(shù)據(jù)包，只要接收到足夠數(shù)量的線性無關(guān)的編碼數(shù)據(jù)包，就可以成功恢復(fù)原始數(shù)據(jù)。當(dāng)一個節(jié)點收到ra個編碼后的數(shù)據(jù)包后，為了恢復(fù)出萬個原始數(shù)據(jù)包，只需求解以下方程組： 這是一個含有刀個未知數(shù)，m個方程的線性方程組。x)同時轉(zhuǎn)發(fā)出去，用于目的節(jié)點對信息向量進行解碼，恢復(fù)原始信源。其中毋就是有限域巧中的元素，它由節(jié)點隨機產(chǎn)生。這里需要指出的是，選擇有限域是緣于它的兩條性質(zhì)，其一是有限域中的元素個數(shù)是有限的，其二是有限域中的元素對于該有限域所定義的兩種運算(an法和乘法)是封閉的。網(wǎng)絡(luò)編碼是在有限域中進行的，主要分為線性和非線性兩種方式。所謂網(wǎng)絡(luò)編碼，就是指節(jié)點對輸入的多路信息流進行代數(shù)組合運算，生成一路或多路新的輸出信息流。除了數(shù)據(jù)復(fù)制以外，一般來說在網(wǎng)絡(luò)的中間節(jié)點并不需要做任何數(shù)據(jù)處理。第三章在對比其它傳統(tǒng)組播路由算法的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)編碼提出了新的基于網(wǎng)絡(luò)編碼的分布式應(yīng)用層組播路由算法?？紤]到應(yīng)用層組播是基于應(yīng)用層端系統(tǒng)之上的，端系統(tǒng)比傳統(tǒng)的IP路由器功能更為強大，可以在端系統(tǒng)上引入網(wǎng)絡(luò)編碼，將接受到的信息進行解碼和編碼可以提高網(wǎng)絡(luò)傳輸?shù)男?。但是，上海大學(xué)碩士學(xué)位論文端系統(tǒng)的穩(wěn)定性一般不如專用網(wǎng)絡(luò)設(shè)備，并且應(yīng)用層組播在帶寬利用效率及網(wǎng)絡(luò)延遲方面也無法和P組播相比。它的主要思想是：保持Intemet原有的模型，盡量不改變原來網(wǎng)絡(luò)的體系結(jié)構(gòu)，而主要通過增加端系統(tǒng)的功能來實現(xiàn)組播的功能。組播通信的基本出發(fā)點是：在同時存在多個接收者時，通過合并重復(fù)信息的傳輸來達到減少帶寬浪費和降低服務(wù)器處理負擔(dān)的目的。這