【正文】 信獲得數(shù)據(jù)，進(jìn)一步提高網(wǎng)絡(luò)資源利用，達(dá)到提高網(wǎng)絡(luò)容量的目的： 3)考慮到啟發(fā)式算法不能達(dá)到網(wǎng)絡(luò)使用的最優(yōu)，而傳統(tǒng)的優(yōu)化算法集中式的優(yōu)化方式達(dá)到網(wǎng)絡(luò)最優(yōu)的同時(shí)，需要掌握網(wǎng)絡(luò)的全局狀態(tài)信息，很難應(yīng)用于大規(guī)模 P2P的分布式網(wǎng)絡(luò)中。 圖 44組播源節(jié)點(diǎn)速率變化圖 (固定步長 stepsize==O． 01) 圖 4． 5給出了迭代過程中目標(biāo)函數(shù)值的變化情況，在源節(jié)點(diǎn)速率穩(wěn)定以后，目標(biāo)函數(shù)值也隨之穩(wěn)定得到。 28 圖 41算法流程圖 在分布式網(wǎng)絡(luò)中，我們假設(shè)的節(jié)點(diǎn)和鏈路 processor則是按照以下方式對于接收的數(shù)據(jù)進(jìn)行處理和更新的： 從上面的算法，我們可以看出利用次梯度迭代算法對我們的目標(biāo)函數(shù)求解，是～個(gè)分布式的，不需要全局信息，能很好的使用與大型網(wǎng)絡(luò)，并且由于源節(jié)點(diǎn)可以提供可伸縮的數(shù)據(jù)流速率，可以應(yīng)用于大規(guī)模異構(gòu)網(wǎng)絡(luò)中。網(wǎng)絡(luò)流平衡約束條件和鏈路帶寬容量約束條件分別由式 (4． 9． 2)和式 (4． 94)來表示。當(dāng)源節(jié)點(diǎn)以最小的最大流進(jìn)行數(shù)據(jù)傳輸?shù)脑?，勢必很多目的?jié)點(diǎn)的資源會被浪費(fèi)。于是，引入對偶變量允∈ R”和 y∈ R7釋放不等式約束和等式約束，可以得到下面的拉格朗日函數(shù)： 拉格朗日乘子五和匕被稱為對偶變量。從圖 3． 8(a)和圖 3． 8(b)，同樣可以發(fā)現(xiàn)多路徑的方式在增加少量延時(shí)的代價(jià)下，大大提高了整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)流量，從而提高了網(wǎng)絡(luò)服務(wù)質(zhì)量，增加了網(wǎng)絡(luò)帶寬。然而在建立多條傳輸路徑后，隨之而來的網(wǎng)絡(luò)延時(shí)問題將會被擴(kuò)大，下面的仿真給出了目的節(jié)點(diǎn)在盡可能多建立到源節(jié)點(diǎn)的路徑情況下形成的組播圖與只建立兩條路傳輸路徑 (即冗余度為 2)的組播圖以及單路徑組播樹之間的性能比較。 17 圖 具體圖例說明 第三節(jié) 實(shí)驗(yàn)仿真和結(jié)果分析 考慮到 DDSP(目的驅(qū)動的最短路徑樹算法 )[361作為一種基本的目的驅(qū)動型組播路由樹算法，這里選它是被用來做算法比較。圖 3． 4(a)表示的是數(shù)據(jù)分組在源節(jié)點(diǎn)處被采集，初始化時(shí)，組播拓?fù)鋱D中只有源節(jié)點(diǎn)，其他目的節(jié)點(diǎn)并未加入組播組。圖 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。在分布式拓?fù)渲羞\(yùn)用隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)，即中間節(jié)點(diǎn)對發(fā)往不同目的節(jié)點(diǎn)的組播數(shù)據(jù)進(jìn)行編碼組合后再轉(zhuǎn)發(fā)，以避開數(shù)據(jù)流對鏈路的競爭沖突，提高組播通信的吞吐量。 第二節(jié) 基于網(wǎng)絡(luò)編碼的應(yīng)用層組播路由算法 在日常生活中，我們經(jīng)常要使用到比較大規(guī)模的通信網(wǎng)絡(luò)，我們都希望通信網(wǎng)絡(luò)能為我們提供更為安全、快速的網(wǎng)絡(luò)服務(wù)。如果權(quán)值代表鏈路延時(shí)，則為最小時(shí)延樹。另外，兩個(gè)端系統(tǒng)之間的通信，可能要通過中間 11 其他端系統(tǒng)的轉(zhuǎn)發(fā)來實(shí)現(xiàn)，這也不可避免的造成兩個(gè)通信節(jié)點(diǎn)之間延時(shí)的增加。端系統(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ā)功能。采用隨機(jī)網(wǎng)絡(luò)編碼技術(shù)，攻擊者對接收端收到的其它編碼數(shù)據(jù)無法進(jìn)行預(yù)知和控制，數(shù)據(jù)篡改的影響可以降至最低。 2)應(yīng)用層組播。 四、提高系統(tǒng)的魯棒性和白適應(yīng)性。除了能使得網(wǎng)絡(luò)傳輸達(dá)到組播容量的上限，網(wǎng)絡(luò)編碼的應(yīng)用還可以為系統(tǒng)帶來以下幾方面的益處： 1．提高組播速率，實(shí)現(xiàn)組播最大容量。因此，節(jié)點(diǎn)的解碼過程是非常簡單的，節(jié)點(diǎn)不需要接收指定內(nèi)容的數(shù)據(jù)包，只要接收到足夠數(shù)量的線性無關(guān)的編碼數(shù)據(jù)包，就可以成功恢復(fù)原始數(shù)據(jù)。x)同時(shí)轉(zhuǎn)發(fā)出去，用于目的節(jié)點(diǎn)對信息向 量進(jìn)行解碼，恢復(fù)原始信源。這里需要指出的是，選擇有限域是緣于它的兩條性質(zhì)，其一是有限域中的元素個(gè)數(shù)是有限的，其二是有限域中的元素對于該有限域所定義的兩種運(yùn)算 (an法和乘法 )是封閉的。所謂網(wǎng)絡(luò)編碼，就是指節(jié)點(diǎn)對輸入的多路信息流進(jìn)行代數(shù)組合運(yùn)算，生成一路或多路新的輸出信息流。第三章在對比其它傳統(tǒng)組播路由算法的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)編碼提出了新的基于網(wǎng)絡(luò)編碼的分布式應(yīng)用層組播路由算法。但是，上海大學(xué)碩士學(xué)位論文端系統(tǒng)的穩(wěn)定性一般不如專用網(wǎng)絡(luò)設(shè)備， 2 并且應(yīng)用層組播在帶寬利用效率及網(wǎng)絡(luò)延遲方面也無法和 P組播相比。組播通信的基本出發(fā)點(diǎn)是：在同時(shí)存在多個(gè)接收者時(shí)，通過合并重復(fù)信息的傳輸來達(dá)到減少帶寬浪費(fèi)和降低服務(wù)器處理負(fù)擔(dān)的目的。與傳統(tǒng)路由節(jié)點(diǎn)只能對數(shù)據(jù)進(jìn)行復(fù)制和轉(zhuǎn)發(fā)不同，應(yīng)用層組播中的端系統(tǒng)可以對接收到的數(shù)據(jù)進(jìn)行運(yùn)算操作 (如線性運(yùn)算 )。 第二節(jié) 課題研究的目的和意義 隨著寬帶多媒體網(wǎng)絡(luò)的不斷發(fā)展，各種寬帶網(wǎng)絡(luò)應(yīng)用層出不窮，例如：數(shù)字電視、視頻會議、數(shù)據(jù)和資料分發(fā)、網(wǎng)絡(luò)音頻應(yīng)用、網(wǎng)絡(luò)視頻應(yīng)用、多媒體遠(yuǎn)程教育等。研究人員反思口層組播體系存在的問題后，在 20xx年提出了應(yīng)用層組播。 網(wǎng)絡(luò)編碼的思想在 20xx年由 R． Ahlswede首次提出，我們發(fā)現(xiàn)網(wǎng)絡(luò)編碼可以大大提高網(wǎng)絡(luò)的傳輸能力和傳輸可靠，其理論創(chuàng)新具有普遍意義，應(yīng)用前景十分廣闊。 3 第二章 網(wǎng)絡(luò)編碼 第一節(jié) 網(wǎng)絡(luò)編碼原理 在現(xiàn)有的通信網(wǎng)絡(luò)中，信息傳輸都是由源節(jié)點(diǎn)經(jīng)過中間節(jié)點(diǎn)，以存儲轉(zhuǎn)發(fā)的方式傳送到目的節(jié)點(diǎn)的。它允許中間節(jié)點(diǎn)對接收到的信息進(jìn)行編碼，并將接收到的多個(gè)數(shù)據(jù)包按照某種特定算法重新組合再發(fā)送出去。g， M’。 這里 代表與 相對應(yīng)的編碼向量，二者滿足 二、解碼過程 在線性編碼下，運(yùn)用乘法和加法運(yùn)算，使得從節(jié)點(diǎn)發(fā)送出來的數(shù)據(jù)為一系列線性組合，便于解碼。而且，對有向圖 G上任意節(jié)點(diǎn)即流入中間節(jié)點(diǎn) f的數(shù)據(jù)總量等于流出節(jié)點(diǎn) f的數(shù)據(jù)總量。然而從圖 2． 1(b) 6 可以看出，存儲轉(zhuǎn)發(fā)模式下的單組播最大速率僅為 2，圖 2． 1(c)顯示在部分節(jié)點(diǎn)上進(jìn)行網(wǎng) 絡(luò)編碼能夠提高組播速率至 4，實(shí)現(xiàn)組播最大容量。 7 圖 第三節(jié) 絡(luò)編碼的應(yīng)用 網(wǎng)絡(luò)編碼將原先分立于物理層和網(wǎng)絡(luò)層的兩個(gè)核心概念 —— 編碼和路由有機(jī)的融為一體，徹底改變了路由器只能對信息進(jìn)行存儲轉(zhuǎn)發(fā)的傳統(tǒng)模式，建立起一種全新的網(wǎng)絡(luò)體系結(jié)構(gòu)及信息編碼和傳輸模式。在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的數(shù)據(jù)存儲能力十分有限，如何將這些節(jié)點(diǎn)采集的信息在最小代價(jià)、最小能耗、最大容量等約束下發(fā)送給存儲節(jié)點(diǎn)是當(dāng)前網(wǎng)絡(luò)編 8 碼在無線通信領(lǐng)域的一個(gè)新課題。 IP層組播是面向組通信應(yīng)用的，被認(rèn)為是大規(guī)模數(shù)據(jù)分發(fā)的最佳方法。圖 3． 1(a)為 IP組播， A為網(wǎng)絡(luò)中的源節(jié)點(diǎn)，數(shù)據(jù)包從 A發(fā)到 R1，再由 R1轉(zhuǎn)發(fā)給 B和 R2， R2再將收到的數(shù)據(jù)包轉(zhuǎn)發(fā)給 C和 D。數(shù)據(jù)拓?fù)渥鳛閼?yīng)用層組播協(xié)議的重要組成部分，即組播中文件數(shù)據(jù)的如何路由是本文討論的重點(diǎn)。如果組播樹包含了樹中所有節(jié)點(diǎn)， Stoner樹問題轉(zhuǎn)化為最小生成樹問題。網(wǎng)絡(luò)信息理論的研究指出：在組播通信中，每個(gè)接收節(jié)點(diǎn)可以以網(wǎng)絡(luò)拓?fù)渲行旁窗l(fā)送點(diǎn)與信宿接收點(diǎn)之間的最大流容量進(jìn)行信息傳遞。應(yīng)用層組播要結(jié)合網(wǎng)絡(luò)編碼技術(shù)，在路由選擇方面必須滿足兩個(gè)條件： (1)網(wǎng)絡(luò)中存在冗余的路徑； (2)具有相同目的節(jié)點(diǎn)的路徑之間不能存在共用的路徑。 二、一種基于網(wǎng)絡(luò)編碼的應(yīng)用層組播路由算法和分析 為了使應(yīng)用層多播的整體性能盡可能逼近口多播性能，在本節(jié)中，我們設(shè)計(jì)了一種基于網(wǎng)絡(luò)編碼的應(yīng)用層組播路由算法，它是面向異構(gòu)化接入不同類型客戶機(jī)的應(yīng)用層覆蓋網(wǎng)絡(luò)組播路由算法，并且充分考慮因網(wǎng)絡(luò)編碼的構(gòu)造采用多路徑方法。目的節(jié)點(diǎn)除了作為數(shù)據(jù)接收者，同樣可以作為中間節(jié)點(diǎn)完成對數(shù)據(jù)的存貯、處理和轉(zhuǎn)發(fā)功能。從圖中可以明顯得到，加入了網(wǎng)絡(luò)編碼的具有冗余度的組播圖可以有效地提高網(wǎng)絡(luò)的吞吐量，同時(shí)的網(wǎng)絡(luò)延時(shí)增加量卻不大。假設(shè)網(wǎng)絡(luò)的目的節(jié)點(diǎn)為 10，在不同的網(wǎng)絡(luò)規(guī)模中，源節(jié)點(diǎn)向各個(gè)目的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸，通過圖 3． 7(a)可以發(fā)現(xiàn)通過建立多條路徑的方法，網(wǎng)絡(luò)的端到端的流量大大提高，而網(wǎng)絡(luò)的延時(shí)相比之下也有一定提高 (圖 3． 70)所示 )。 凸優(yōu)化問題是非線性優(yōu)化中非常重要的一種類型，它對于實(shí)際優(yōu)化問題的求解有著非常重要的作用，受到了廣泛關(guān)注。 第二節(jié) 基于網(wǎng)絡(luò)編碼的應(yīng)用層 組播最優(yōu)化 網(wǎng)絡(luò)編碼的采用可以使得網(wǎng)絡(luò)以最大流方式進(jìn)行數(shù)據(jù)傳輸，網(wǎng)絡(luò)中的節(jié)點(diǎn)的功能也得到擴(kuò)大。本節(jié)在此基礎(chǔ)上 考慮如何網(wǎng)絡(luò)優(yōu)化，即在網(wǎng)絡(luò)容量的約束下確定各源節(jié)點(diǎn)的發(fā)送速率和每條鏈路上的流量大小，使得整個(gè)網(wǎng)絡(luò)的源節(jié)點(diǎn)效用最大而流量代價(jià)達(dá)到最優(yōu)?？紤]到這里假設(shè)的代價(jià)函數(shù)是凸的且連續(xù)遞增的，對應(yīng)的每一條鏈路單位流量通過產(chǎn)生的代價(jià)， 同時(shí)也為一個(gè)凹函數(shù)。對于網(wǎng)絡(luò)的任意兩節(jié)點(diǎn)間的鏈路都有單位流量成本和鏈路容量兩個(gè)網(wǎng)絡(luò)參數(shù) (前面一個(gè)參數(shù)為單位代價(jià)，后面一 29 個(gè)參數(shù)為為鏈路容量 )。在實(shí)際網(wǎng)絡(luò)中，端系統(tǒng)用戶可以根據(jù)自身情況隨時(shí)調(diào)整迭代計(jì)算的步長，在計(jì)算初可以選擇大的步長值快速逼近最優(yōu)值，此后可以使用遞減的步長進(jìn)行計(jì)算以求達(dá)到最優(yōu)值。 34 致 謝 經(jīng)過近兩個(gè)月的努力，終于順利完成了