【正文】 Problem(411)為 Problem(49)在加入網(wǎng)絡編碼后的變形， Problem(411)1拘對偶問題 Dual： 利用分布式的次梯度算法來求解我們優(yōu)化問題，可以知道，使用迭代算法求解非線性最優(yōu)化問題的關(guān)鍵在于，如何構(gòu)造每一次的搜索方向和確定適當?shù)牟介L。 圖 46組播源節(jié)點速率變化圖 (同定步長 stcpsize=O． 005) 32 圖 47組播源節(jié)點速率變化圖 (不固定步長 stepsize=O． 01／ k) 33 結(jié)論 隨著互聯(lián)網(wǎng)上的大規(guī)模媒體存儲 與發(fā)布的不斷發(fā)展，多媒體技術(shù)的廣泛使用，如遠程會議、網(wǎng)絡視頻和音頻廣播，這些新媒體服務對網(wǎng)絡帶寬要求很高，傳統(tǒng)集中式分發(fā)模型不再適用，人們希望通過建立新的分布式傳輸模式來解決大規(guī)模數(shù)據(jù)分發(fā)問題。所以再次感謝老師。 31 圖 45仿真結(jié)果 (固定步長 stepsize=O． 01) 為了分析步長選擇對我們算法收斂性的影響，我們還選擇了其他步長進行比較。約束條件 (4． 9． 3)表示，對于任一條鏈路 O，力上流向任一目的節(jié)點的信息流應該小于該條鏈路實際流量，這是由于 (f， jf)上可能被多個組播組和目的節(jié)點所共用。這樣，我們可以得到原始問題 (4． 2) 24 的對偶函數(shù) (4． 4) 假設 P’是優(yōu)化 IhJ題 (4． 2)的最優(yōu)值，對于任何名≥ 0和 I，可以得到： 對偶函數(shù) g(A， y)是一個凸函數(shù)，可以看作是關(guān)于變量名和 y的極小值函數(shù)。 20 考慮到每一個目的節(jié)點的實際接受數(shù)據(jù)的處理能力，我們設置網(wǎng)絡中目的節(jié)點入度最大值為 5。當目的節(jié)點申請加入組播組，則按照圖 3． 3流程的 7個步驟為其建立兩條互不相交的路徑。 一、冗余路徑 考慮到網(wǎng)絡編碼在提高網(wǎng)絡的吞吐量方面的優(yōu)點，為了進一步改善應用層組播的性能，從而我們引入了網(wǎng)絡編碼技術(shù)。最小生成樹是指覆蓋所有組成員且權(quán)值最小的組播樹。因為不再依靠網(wǎng)絡層路由器來實現(xiàn)，所以不需要任何網(wǎng)絡底層架構(gòu)的改變，只需改變端系統(tǒng)，便于實現(xiàn)和推廣。 P2P技術(shù)與覆蓋網(wǎng)絡 (overlay work)的發(fā)展，將組播功能從 P層擴展到了應用層，在 P2P應用層組播系統(tǒng)中， Peer節(jié)點對流經(jīng)的數(shù)據(jù)除了進行存儲轉(zhuǎn)發(fā)外，如果 還可以進行額外的網(wǎng)絡編碼處理，將可以在很大程度上改善應用層組播性能，提高覆蓋網(wǎng)絡數(shù)據(jù)吞吐能力。圖 2． 1(a)給出了網(wǎng)絡拓撲結(jié)構(gòu)及不同鏈路的容量，其中 S是信源，墨、恐和恐是三個不同的信宿。網(wǎng)絡編碼可以對編碼的數(shù)據(jù)包重復進行編碼，換言之，節(jié)點可以對收到的已編碼的信息向量進行再次編碼。在傳統(tǒng)的網(wǎng)絡中，大量存在的中間節(jié)點只能對接收到的數(shù)據(jù)進行路由、復制和轉(zhuǎn)發(fā)，這對于有限的網(wǎng)絡資源是嚴重浪費。另外，應用層組播中的系統(tǒng)框架和很多細節(jié)技術(shù)也還在研究當中。利用網(wǎng)絡編碼，端系統(tǒng)對收到的數(shù)據(jù)進行組合編碼，從而有效地利用網(wǎng)絡帶寬，增加網(wǎng)絡容量。而由于口組播在傳輸技術(shù)和管理上存在嚴重的問題，主要是口組播需要路由器維護組播通信的狀態(tài)信息，增加了網(wǎng)絡的復雜性并嚴重 約束網(wǎng)絡組播的擴展，其次網(wǎng)絡的可靠性、擁塞控制、流量控制、安全性無法得到保障，另外由于 P地址空間有限，無法滿足眾多應用的需求，因此目前 IP組播沒有在 Inter中得到普遍采用 [21。最后第五章總結(jié)了全文以及碩士期間的研究工作，并以后工作提出了設想。 一、編碼過程 假設一個或多個原始信源所發(fā)送的信息由療個數(shù)據(jù)包 M1，．．．， M^組成，中間節(jié)點可以對流入其中 的 n個數(shù)據(jù)包進行網(wǎng)絡編碼，生成 1個新的數(shù)據(jù)包 x=Σ：。對于包含一個源節(jié)點 s和￡個匯節(jié)點， V代表頂點 (Vcrticc)集合， E代表有向邊 (Edge)集合，用嘞表示邊 (f， j)∈ E的 容量 , ， F表示流經(jīng)邊 (的流量，顯然對所有。圖 2． 2(a)中的每個節(jié)點均以原始格式對數(shù)據(jù)進行存儲，圖 2． 2∞中的每個節(jié)點均以網(wǎng)絡編碼后的格式對數(shù)據(jù)進行存儲，可以看出，圖 (a)中只能容忍節(jié)點 2或 3中一個失效或離開，否則系統(tǒng)中的其它節(jié)點就不能剩余節(jié)點中完整地獲取數(shù)據(jù) a、 b、 c、 d；而圈 2． 2(b)中允許任一節(jié)點失效或離 開，其它節(jié)點都能夠自適應地做出調(diào)整，重新路由，從剩余的三個節(jié)點完整地獲取數(shù)據(jù) a、 b、“ d。隨著視頻點播、網(wǎng)絡電視、遠程教育等多媒體服務飛速發(fā)展，中央服務器的帶寬瓶頸問題日益凸顯，以致集中式的分發(fā)模型逐步向基于 P2P覆蓋網(wǎng)絡 (overlay work)架構(gòu)的分布式結(jié)構(gòu)過渡。而數(shù)據(jù)拓撲通常是控制拓撲的子集，它用于標識組播轉(zhuǎn)發(fā)時使用的數(shù)據(jù)路徑。由前一章可知，網(wǎng)絡編碼可以實現(xiàn)網(wǎng)絡的最大流傳輸。 14 這里，多條不相交的數(shù)據(jù)傳輸路徑的存在使得以往組播進行數(shù)據(jù)通信的組播樹演變成組播圖，即由多 棵組播樹的疊加而成。首先假設網(wǎng)絡中節(jié)點數(shù)目發(fā)生變化，圖 3． 5(a)和圖 3． 5(b)給出了兩者間網(wǎng)絡帶寬和平均延時方面的比較。另外，如果優(yōu)化目標是求凹函數(shù)的最大值，并且同樣滿足約束條件都是凸 集，這樣的問題同樣也是凸優(yōu)化問題。 第三節(jié) 基于網(wǎng)絡編碼的應用層組播凈效用最優(yōu)化 在提高網(wǎng)絡端到端吞吐量時，為了克服應用層組播中的帶寬瓶頸問題，我們將網(wǎng)絡編碼技術(shù)引入到組播通信組里，在瓶頸鏈路使用網(wǎng)絡編碼解決數(shù)據(jù)碰撞問 25 題，從而提出了第三章的應用層組播路由算法。 第四節(jié) 仿真結(jié)果與分析 我們以圖 4． 2所示的網(wǎng)絡結(jié)構(gòu)作為仿真模型，其中 S1． S3為網(wǎng)絡中的三個源節(jié)點， T1． T2為目的節(jié)點， N1N4為中間節(jié)點。應用層組播中的節(jié)點和鏈路只需要根據(jù)自身信息和鄰接節(jié)點及鏈路的狀態(tài)信息進行網(wǎng)絡狀態(tài)的更新從而實現(xiàn)網(wǎng)絡優(yōu)化。 在這里我要衷心感謝所有在設計過程中給我提供幫助的老師和同學 首先要感謝鄭老師，在完成畢業(yè)論文的這段時間里鄭老師給出了許多寶貴的意見和幫助?？梢詫D 4． 2所示的網(wǎng)絡拓撲視為圖 4． 3中的三個組播組，每一個組播中有一個源節(jié)點以及若干中間節(jié)點和目的節(jié)點 (組播子網(wǎng) )。 一、最優(yōu)化問題闡述 在進行信息流組播傳輸時，我們的目標是希望最大化每一個組播組源節(jié)點的效用，但同時要以合理的速率傳輸盡可能多的信息。這是由于凸函數(shù)的極值點自身具有良好的性質(zhì)，即凸函數(shù)在其定義域上的任一極點都是其在定義域上的全局最優(yōu)點，且極值點的集合也是凸集?？紤]到網(wǎng)絡帶寬的有效增加，新增加的延時可以忽略。本節(jié)提出的算法作為啟發(fā)式算法的一種，適合運用在 P2P等分布式網(wǎng)絡中，相對于傳送未編碼原始數(shù)據(jù)塊的傳統(tǒng)分布式內(nèi)容分發(fā)及 P2P對等通信，通過在由采集節(jié)點、存儲節(jié)點、客戶機所構(gòu)造的覆蓋網(wǎng)中 Peer之間傳輸經(jīng)過網(wǎng)絡編碼的數(shù)據(jù)分組，可以有效 提高覆蓋網(wǎng)絡數(shù)據(jù)吞吐能力。然而， 從信源到不同信宿之間的最大流經(jīng)過的傳輸路徑可能在網(wǎng)絡拓撲的鏈路上形成交叉共享鏈 12 路，因此采用傳統(tǒng)的存儲轉(zhuǎn)發(fā)模式即 P組播的方式，無法達到最大流最小割的理論上限。一般來說，組播組用于標識組播轉(zhuǎn)發(fā)時用的數(shù)據(jù)路徑通常是一棵組播樹。然而口組播增加了網(wǎng)絡層的復雜性，而且需要對現(xiàn)有網(wǎng)絡的底層設備進行巨大改動，因此至今口層組播仍然無法廣泛部署。網(wǎng)絡編碼代表了一種協(xié)同工作的理念，這使得它的應用不僅局限于改進組播增加網(wǎng)絡容量，與其它技術(shù)相結(jié)合已經(jīng)應用于分布式內(nèi)容存儲與分發(fā)應用層組播無線傳感器網(wǎng)絡數(shù)據(jù)采集網(wǎng)絡管理信息安全等眾多領 域。 根據(jù)最大流最小割定理：任何帶發(fā)送節(jié)點和接收節(jié)點的網(wǎng)絡中都存在最大流和最小割，并且最大流的流值等于最小割的容量。其中毋就是有限域巧中的元素，它由節(jié)點隨機產(chǎn)生。除了數(shù)據(jù)復制以外，一般來說在網(wǎng)絡的中間節(jié)點并不需要做任何數(shù)據(jù)處理。它的主要思想是：保持 Intemet原有的模型，盡量不改變原來網(wǎng)絡的體系結(jié)構(gòu)，而主要通過增加端系統(tǒng)的功能來實現(xiàn)組播的功能。在 P組播無法被全網(wǎng)范圍內(nèi)部署利用的情況下，基于端系統(tǒng)的應用層組播應運而生。m． Peer Network和 OverlayNetwork等技術(shù)的提 出和發(fā)展對應用層組播的研究也有很大的促進作用。 20xx年， R． Ahlswcde首次提出了對信息進行網(wǎng)絡編碼的思想。編碼完成后，節(jié)點將編碼向量和信息向量 (g39。 20xx年， R． Li證明了在單個源節(jié)點向多個目的節(jié)點發(fā)送數(shù)據(jù)的情況下，應用線性網(wǎng)絡編碼理論，一定能夠達到網(wǎng)絡組播容量的上限。而在 Peer之間傳輸經(jīng)過網(wǎng)絡編碼的數(shù)據(jù)塊能夠有效解決甚至避免這些問題。如果在疊加網(wǎng)的基礎上實現(xiàn)組播，可以把組播實現(xiàn)提高到應用層。如果所有的鏈路的權(quán)值都表 1，則為最小跳樹。 本節(jié)的主要內(nèi)容就是建立一種基于網(wǎng)絡編碼的啟發(fā)式應用層組播路由算法，目的在于利用網(wǎng)絡編碼技術(shù)在分布式網(wǎng)絡中建立數(shù)據(jù)分發(fā)拓撲使得網(wǎng)絡傳輸容量趨于組播容量上限。 圖 （ a）第一次尋路算法流程圖 16 圖 （ b）第二場尋路算法流程圖 我們以圖 3． 4(a)所示拓撲為例來說明在具體網(wǎng)絡拓撲給定下如何為每一個目的節(jié)點獨立地建立兩條與 S通信的數(shù)據(jù)傳輸鏈路。 19