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