【正文】 她的寶貴意見(jiàn)和幫助我們都非常受用。根據(jù)網(wǎng)絡(luò)編碼的特點(diǎn)，在組播源節(jié)點(diǎn)和網(wǎng)絡(luò)中的每一個(gè)目的節(jié)點(diǎn)之間建立多條不相交的數(shù)據(jù)通信 路徑形成組播圖。這里設(shè)置迭代步長(zhǎng)stepsize=O． 01。對(duì)于 node processor而言，在其中記錄每次循環(huán)迭代值。于是，我們得到下面的最優(yōu)化目標(biāo)及其約束條件 problem()為： 我們的目標(biāo)就是要最大化網(wǎng)絡(luò)源節(jié)點(diǎn)的效用同時(shí)最小整個(gè)網(wǎng)絡(luò)的傳輸代價(jià)。假設(shè) 網(wǎng)絡(luò)中源節(jié)點(diǎn)在向多個(gè)接受能力不同的目的節(jié)點(diǎn)提供數(shù)據(jù)服務(wù)的時(shí)候，網(wǎng)絡(luò)中的最大流根據(jù)網(wǎng)絡(luò)流理論可知是網(wǎng)絡(luò)中各目的節(jié)點(diǎn)最大流的最小值。首先考察一個(gè)一般優(yōu)化問(wèn)題 (42)： 我們將問(wèn)題 (4． 2)稱為原 始問(wèn)題，將滿足所有約束條件的解石稱為原始變量，并且假設(shè) p+是優(yōu)化問(wèn)題 (4． 2)的全局最小值。假設(shè)在網(wǎng)絡(luò)規(guī)模為 100個(gè)節(jié)點(diǎn)的條件下，分區(qū)取 10個(gè)， 20個(gè)，??70個(gè)目的節(jié)點(diǎn)比較三種方法的性能。 19 圖 的節(jié)點(diǎn)數(shù)目變化 圖 36（ b）網(wǎng)絡(luò)端到網(wǎng)絡(luò)延時(shí)隨目的節(jié)點(diǎn)數(shù)目變化 我們提出的路由算法是希望建立多條傳輸路徑來(lái)使得網(wǎng)絡(luò)的傳輸流量逼近圖論中的網(wǎng)絡(luò)最大流。對(duì)于不同的目的節(jié)點(diǎn)，存在瓶頸鏈路 (S， U1)、 (u6， UIO)，只需在節(jié)點(diǎn) S和節(jié)點(diǎn)U6處進(jìn)行網(wǎng)絡(luò)編碼即可解決數(shù)據(jù)碰撞的問(wèn)題。 圖 （ a）第一次尋路算法流程圖 16 圖 （ b）第二場(chǎng)尋路算法流程圖 我們以圖 3． 4(a)所示拓?fù)錇槔齺?lái)說(shuō)明在具體網(wǎng)絡(luò)拓?fù)浣o定下如何為每一個(gè)目的節(jié)點(diǎn)獨(dú)立地建立兩條與 S通信的數(shù)據(jù)傳輸鏈路。此時(shí)，對(duì)于不同目的節(jié)點(diǎn)的路徑之間必然存在鏈路的公用問(wèn)題而產(chǎn)生的瓶頸鏈路，網(wǎng)絡(luò)編碼的引入可以很好的解決瓶頸鏈路的問(wèn)題。 本節(jié)的主要內(nèi)容就是建立一種基于網(wǎng)絡(luò)編碼的啟發(fā)式應(yīng)用層組播路由算法，目的在于利用網(wǎng)絡(luò)編碼技術(shù)在分布式網(wǎng)絡(luò)中建立數(shù)據(jù)分發(fā)拓?fù)涫沟镁W(wǎng)絡(luò)傳輸容量趨于組播容量上限。通常這些問(wèn)題是 NP． Complete的，所以也需要采用啟發(fā)式算法解決。如果所有的鏈路的權(quán)值都表 1，則為最小跳樹(shù)。應(yīng)用層組播的效率比 P組播的效率要低，因?yàn)椴豢杀苊獾臅?huì)有組播路徑重復(fù)的經(jīng)過(guò)同一條底層鏈路，也就必然帶來(lái)冗余的流量，例如在圖 3． 1(b)中 (A， R1)和 (R2， C)這兩條鏈路上有兩個(gè)相同的數(shù)據(jù)包重復(fù)經(jīng)過(guò)同一條底層鏈路，而圖3． 1(a)的口組播則只有一次。如果在疊加網(wǎng)的基礎(chǔ)上實(shí)現(xiàn)組播，可以把組播實(shí)現(xiàn)提高到應(yīng)用層。攻擊者惡意篡改網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)內(nèi)容將直接影響接收端的信息接收，這是目前計(jì)算機(jī)通信網(wǎng)的一個(gè)潛在隱患。而在 Peer之間傳輸經(jīng)過(guò)網(wǎng)絡(luò)編碼的數(shù)據(jù)塊能夠有效解決甚至避免這些問(wèn)題。而且，前者集中使用 了系統(tǒng)中的 5條鏈路，閑置了另外 4條鏈路，導(dǎo)致節(jié)點(diǎn)上的帶寬資源占用情況非常不平衡；而后者均衡地利用了系統(tǒng)中的全部 9條鏈路，很好地平衡了網(wǎng)絡(luò)負(fù)載。 20xx年， R． Li證明了在單個(gè)源節(jié)點(diǎn)向多個(gè)目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)的情況下，應(yīng)用線性網(wǎng)絡(luò)編碼理論，一定能夠達(dá)到網(wǎng)絡(luò)組播容量的上限。雖然編碼向 量之間的線性相關(guān)程度取決于所選取的有限域的大小，但實(shí)驗(yàn)證明即使選擇比較小的有限域，比如 S=8的有限域，編碼向量之間出現(xiàn)線性相關(guān)的概率也是非常小的。編碼完成后，節(jié)點(diǎn)將編碼向量和信息向量 (g39。 于是，從代數(shù)學(xué)的角度來(lái)看，數(shù)據(jù)包之間的編碼運(yùn)算就等同于一系列向量的線性組合，而線性組合所用到的加法和乘法遵循有限域的運(yùn)算法則。 20xx年， R． Ahlswcde首次提出了對(duì)信息進(jìn)行網(wǎng)絡(luò)編碼的思想。第二章闡述了課題研究的基本理論 —— 網(wǎng)絡(luò)編碼的概念和基本原理，包括如何進(jìn)行編碼和解碼，以及網(wǎng)絡(luò)編碼的優(yōu)點(diǎn)和使用范圍。m． Peer Network和 OverlayNetwork等技術(shù)的提 出和發(fā)展對(duì)應(yīng)用層組播的研究也有很大的促進(jìn)作用。組播是現(xiàn)在網(wǎng)絡(luò)研究中的一個(gè)重要課題。在 P組播無(wú)法被全網(wǎng)范圍內(nèi)部署利用的情況下，基于端系統(tǒng)的應(yīng)用層組播應(yīng)運(yùn)而生。這些寬帶多媒體應(yīng)用都對(duì)現(xiàn)有寬帶多媒體網(wǎng)絡(luò)的承載能力提出了挑戰(zhàn)。它的主要思想是：保持 Intemet原有的模型，盡量不改變?cè)瓉?lái)網(wǎng)絡(luò)的體系結(jié)構(gòu)，而主要通過(guò)增加端系統(tǒng)的功能來(lái)實(shí)現(xiàn)組播的功能。考慮到應(yīng)用層組播是基于應(yīng)用層端系統(tǒng)之上的，端系統(tǒng)比傳統(tǒng)的 IP路由器功能更為強(qiáng)大 ，可以在端系統(tǒng)上引入網(wǎng)絡(luò)編碼，將接受到的信息進(jìn)行解碼和編碼可以提高網(wǎng)絡(luò)傳輸?shù)男?。除了?shù)據(jù)復(fù)制以外，一般來(lái)說(shuō)在網(wǎng)絡(luò)的中間節(jié)點(diǎn)并不需要做任何數(shù)據(jù)處理。 網(wǎng)絡(luò)編碼是在有限域中進(jìn)行的，主要分為線性和非線性兩種方式。其中毋就是有限域巧中的元素，它由節(jié)點(diǎn)隨機(jī)產(chǎn)生。當(dāng)一個(gè)節(jié)點(diǎn)收到 ra個(gè)編碼后的數(shù)據(jù)包后，為了恢復(fù)出萬(wàn)個(gè)原始數(shù)據(jù)包 ，只需求解以下 方程組： 這是一個(gè)含有刀個(gè)未知數(shù)， m個(gè)方程的線性方程組。 根據(jù)最大流最小割定理：任何帶發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的網(wǎng)絡(luò)中都存在最大流和最小割，并且最大流的流值等于最小割的容量。 （ 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ù)載平衡。網(wǎng)絡(luò)編碼代表了一種協(xié)同工作的理念，這使得它的應(yīng)用不僅局限于改進(jìn)組播增加網(wǎng)絡(luò)容量，與其它技術(shù)相結(jié)合已經(jīng)應(yīng)用于分布式內(nèi)容存儲(chǔ)與分發(fā)應(yīng)用層組播無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集網(wǎng)絡(luò)管理信息安全等眾多領(lǐng) 域。 4)網(wǎng)絡(luò)管理。然而口組播增加了網(wǎng)絡(luò)層的復(fù)雜性，而且需要對(duì)現(xiàn)有網(wǎng)絡(luò)的底層設(shè)備進(jìn)行巨大改動(dòng)，因此至今口層組播仍然無(wú)法廣泛部署。圖 3． 1(b)為應(yīng)用層組播， A發(fā)送兩份相同的數(shù)據(jù)包分別給 B和 C，再由 C復(fù)制一份給 D。一般來(lái)說(shuō)，組播組用于標(biāo)識(shí)組播轉(zhuǎn)發(fā)時(shí)用的數(shù)據(jù)路徑通常是一棵組播樹(shù)。一般通過(guò)啟發(fā)式算法求解，典型的啟發(fā)式算法有：MST、 RS、 KMB[31， 321。然而， 從信源到不同信宿之間的最大流經(jīng)過(guò)的傳輸路徑可能在網(wǎng)絡(luò)拓?fù)涞逆溌飞闲纬山徊婀蚕礞? 12 路，因此采用傳統(tǒng)的存儲(chǔ)轉(zhuǎn)發(fā)模式即 P組播的方式，無(wú)法達(dá)到最大流最小割的理論上限。 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ù)流。本節(jié)提出的算法作為啟發(fā)式算法的一種，適合運(yùn)用在 P2P等分布式網(wǎng)絡(luò)中，相對(duì)于傳送未編碼原始數(shù)據(jù)塊的傳統(tǒng)分布式內(nèi)容分發(fā)及 P2P對(duì)等通信，通過(guò)在由采集節(jié)點(diǎn)、存儲(chǔ)節(jié)點(diǎn)、客戶機(jī)所構(gòu)造的覆蓋網(wǎng)中 Peer之間傳輸經(jīng)過(guò)網(wǎng)絡(luò)編碼的數(shù)據(jù)分組，可以有效 提高覆蓋網(wǎng)絡(luò)數(shù)據(jù)吞吐能力。因此，對(duì)于新申請(qǐng)加入的目的節(jié)點(diǎn)，它既可以通過(guò)共用組播圖中的其它目的節(jié)點(diǎn)，也可以通過(guò)接入與其鄰接的中間節(jié)點(diǎn)來(lái)加入組播拓?fù)鋱D。考慮到網(wǎng)絡(luò)帶寬的有效增加，新增加的延時(shí)可以忽略。在傳輸大量數(shù)據(jù)的時(shí)候，每一個(gè)目的節(jié)點(diǎn)使用多路徑算法找出能逼近最大流的多 條路徑同時(shí)進(jìn)行傳輸，結(jié)合網(wǎng)絡(luò)編碼技術(shù)使得每一個(gè)目的節(jié)點(diǎn)可以獨(dú)立享用整個(gè)網(wǎng)絡(luò)資源，從而大大提高了網(wǎng)絡(luò)的吞吐量。這是由于凸函數(shù)的極值點(diǎn)自身具有良好的性質(zhì)，即凸函數(shù)在其定義域上的任一極點(diǎn)都是其在定義域上的全局最優(yōu)點(diǎn)，且極值點(diǎn)的集合也是凸集。但是由于網(wǎng)絡(luò)中節(jié)點(diǎn)之間存在的差異，以及分布式網(wǎng)絡(luò)中多個(gè)數(shù)據(jù)源節(jié)點(diǎn)的存在使得網(wǎng)絡(luò)鏈路速率的分配和網(wǎng)絡(luò)傳輸成本之間的矛盾越來(lái)越明顯。 一、最優(yōu)化問(wèn)題闡述 在進(jìn)行信息流組播傳輸時(shí)，我們的目標(biāo)是希望最大化每一個(gè)組播組源節(jié)點(diǎn)的效用，但同時(shí)要以合理的速率傳輸盡可能多的信息。對(duì)于一個(gè)凸的目標(biāo)函 26 數(shù)在一個(gè)線性約束集下，根據(jù)凸函數(shù)最大化問(wèn)題我們可以知道該最優(yōu)化問(wèn)題存在唯一的最優(yōu)解?？梢詫D 4． 2所示的網(wǎng)絡(luò)拓?fù)湟暈閳D 4． 3中的三個(gè)組播組，每一個(gè)組播中有一個(gè)源節(jié)點(diǎn)以及若干中間節(jié)點(diǎn)和目的節(jié)點(diǎn) (組播子網(wǎng) )。圖 4． 6和圖 4． 7分別給出了迭代步長(zhǎng)stepsizeO． 01和可變步長(zhǎng)下的各個(gè)組播源節(jié)點(diǎn)發(fā)送速率的變化。 在這里我要衷心感謝所有在設(shè)計(jì)過(guò)程中給我提供幫助的老師和同學(xué) 首先要感謝鄭老師，在完成畢業(yè)論文的這段時(shí)間里鄭老師給出了許多寶貴的意見(jiàn)和幫助。 35 參考文獻(xiàn) [1] 陳波 .《應(yīng)用層組播的研究與算法實(shí)現(xiàn)》 .計(jì)算機(jī)工程與設(shè)計(jì)， 20xx． [2]．李瑁晟 .《應(yīng)用層組播綜述》 .計(jì)算機(jī)應(yīng)用研究， 20xx． [3]．徐恪 .《高等計(jì)算機(jī)網(wǎng)絡(luò) —— 體系結(jié)構(gòu)、協(xié)議機(jī)制、算法設(shè)計(jì)與路由器技術(shù)》，機(jī)械工業(yè)出版社， 20xx． [4]．謝政，李建平，《網(wǎng)絡(luò)算法與復(fù)雜性理論》，國(guó)防科技大學(xué)出版社， 1995． [5]．李偉，沈長(zhǎng)寧，應(yīng)用層組播協(xié)議的研究，計(jì)算機(jī)工程與應(yīng)用， 20xx． [6]．董慶陽(yáng)，李毓麟，《組播路由綜合優(yōu)化及其算法》，計(jì)算機(jī)學(xué)報(bào)， 20xx． [7]．甘應(yīng)愛(ài) .《運(yùn)籌學(xué)》，清華大學(xué)出版社， 20xx． [8]．鄧先禮 .《最優(yōu)化技術(shù)》，重慶大學(xué)出版社， 1998． [9]．張忠楨 .《凸規(guī)劃》，武漢大學(xué)出版社， 20xx． 。應(yīng)用層組播中的節(jié)點(diǎn)和鏈路只需要根據(jù)自身信息和鄰接節(jié)點(diǎn)及鏈路的狀態(tài)信息進(jìn)行網(wǎng)絡(luò)狀態(tài)的更新從而實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，當(dāng)步長(zhǎng)選擇越小，迭代速率越慢，越能接近最優(yōu)值，這也是符合梯 度算法本身特性的。 第四節(jié) 仿真結(jié)果與分析 我們