【正文】 信組里，在瓶頸鏈路使用網(wǎng)絡(luò)編碼解決數(shù)據(jù)碰撞問題，從而提出了第三章的應(yīng)用層組播路由算法。本節(jié)在此基礎(chǔ)上考慮如何網(wǎng)絡(luò)優(yōu)化，即在網(wǎng)絡(luò)容量的約束下確定各源節(jié)點的發(fā)送速率和每條鏈路上的流量大小，使得整個網(wǎng)絡(luò)的源節(jié)點效用最大而流量代價達到最優(yōu)。一、最優(yōu)化問題闡述在進行信息流組播傳輸時，我們的目標(biāo)是希望最大化每一個組播組源節(jié)點的效用，但同時要以合理的速率傳輸盡可能多的信息。所謂合理即是要考慮整個網(wǎng)絡(luò)中所有目的節(jié)點的接收能力，并且整個網(wǎng)絡(luò)的傳輸代價要盡可能的小。對于網(wǎng)絡(luò)中的任一組播組m，這里用硝』表示在組播組m中，鏈路(f，j)上發(fā)送至目的節(jié)點t的信息流速率。于是，我們得到下面的最優(yōu)化目標(biāo)及其約束條件problem()為：我們的目標(biāo)就是要最大化網(wǎng)絡(luò)源節(jié)點的效用同時最小整個網(wǎng)絡(luò)的傳輸代價。網(wǎng)絡(luò)流平衡約束條件和鏈路帶寬容量約束條件分別由式(4．9．2)和式(4．94)來表示。約束條件(4．9．3)表示，對于任一條鏈路O，力上流向任一目的節(jié)點的信息流應(yīng)該小于該條鏈路實際流量，這是由于(f，jf)上可能被多個組播組和目的節(jié)點所共用。二、解決方案對上面提出來的優(yōu)化目標(biāo)，我們希望能尋找分布式的算法從而可以應(yīng)用于大規(guī)模分布式網(wǎng)絡(luò)中?？紤]到這里假設(shè)的代價函數(shù)是凸的且連續(xù)遞增的，對應(yīng)的每一條鏈路單位流量通過產(chǎn)生的代價，同時也為一個凹函數(shù)。對于一個凸的目標(biāo)函數(shù)在一個線性約束集下，根據(jù)凸函數(shù)最大化問題我們可以知道該最優(yōu)化問題存在唯一的最優(yōu)解。為了尋找一個分布式的算法來求解，首先考慮上述問題的對偶，并釋放流平衡約束和鏈路容量約束，于是上式的拉格朗日對偶函數(shù)可表示為：負數(shù)也是凹函數(shù)，它們的線性組合亦為凹函數(shù))上式存在唯一的最優(yōu)解，則對應(yīng)于變量寶和聲、以及拉格朗日乘子多和互應(yīng)該滿足條件：Problem(411)為Problem(49)在加入網(wǎng)絡(luò)編碼后的變形，Problem(411)1拘對偶問題Dual：利用分布式的次梯度算法來求解我們優(yōu)化問題，可以知道，使用迭代算法求解非線性最優(yōu)化問題的關(guān)鍵在于，如何構(gòu)造每一次的搜索方向和確定適當(dāng)?shù)牟介L。我們可以利用primal—dual算法求解優(yōu)化問題Problem(4．11). 我們假設(shè)在網(wǎng)絡(luò)節(jié)點和鏈路上均設(shè)置相應(yīng)的processor。對于node processor而言，在其中記錄每次循環(huán)迭代值。圖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ò)中。如果在這里我們加入了網(wǎng)絡(luò)編碼，又可以在一定程度上提高網(wǎng)絡(luò)的吞吐量。第四節(jié) 仿真結(jié)果與分析我們以圖4．2所示的網(wǎng)絡(luò)結(jié)構(gòu)作為仿真模型，其中S1．S3為網(wǎng)絡(luò)中的三個源節(jié)點，T1．T2為目的節(jié)點，N1N4為中間節(jié)點。對于網(wǎng)絡(luò)的任意兩節(jié)點間的鏈路都有單位流量成本和鏈路容量兩個網(wǎng)絡(luò)參數(shù)(前面一個參數(shù)為單位代價，后面一個參數(shù)為為鏈路容量)?？梢詫D4．2所示的網(wǎng)絡(luò)拓撲視為圖4．3中的三個組播組，每一個組播中有一個源節(jié)點以及若干中間節(jié)點和目的節(jié)點(組播子網(wǎng))。圖42 網(wǎng)絡(luò)拓撲圖圖43 三個組播子圖圖4．4給出了用次梯度迭代算法計算出來的每個組播組源節(jié)點發(fā)送速率(圖4．3所示的三個組播組)。從圖中可以看出，在迭代50次以后，各個組播組的源節(jié)點可以達到各自組播速率的穩(wěn)定值，即出度帶寬的上限。這里設(shè)置迭代步長stepsize=O．01。圖44組播源節(jié)點速率變化圖(固定步長stepsize==O．01)圖4．5給出了迭代過程中目標(biāo)函數(shù)值的變化情況，在源節(jié)點速率穩(wěn)定以后，目標(biāo)函數(shù)值也隨之穩(wěn)定得到。圖45仿真結(jié)果(固定步長stepsize=O．01)為了分析步長選擇對我們算法收斂性的影響，我們還選擇了其他步長進行比較。實驗結(jié)果發(fā)現(xiàn)，當(dāng)步長選擇越小，迭代速率越慢，越能接近最優(yōu)值，這也是符合梯度算法本身特性的。在實際網(wǎng)絡(luò)中，端系統(tǒng)用戶可以根據(jù)自身情況隨時調(diào)整迭代計算的步長，在計算初可以選擇大的步長值快速逼近最優(yōu)值，此后可以使用遞減的步長進行計算以求達到最優(yōu)值。圖4．6和圖4．7分別給出了迭代步長stepsizeO．01和可變步長下的各個組播源節(jié)點發(fā)送速率的變化。圖46組播源節(jié)點速率變化圖(同定步長stcpsize=O．005)圖47組播源節(jié)點速率變化圖(不固定步長stepsize=O．01／k)結(jié)論隨著互聯(lián)網(wǎng)上的大規(guī)模媒體存儲與發(fā)布的不斷發(fā)展，多媒體技術(shù)的廣泛使用，如遠程會議、網(wǎng)絡(luò)視頻和音頻廣播，這些新媒體服務(wù)對網(wǎng)絡(luò)帶寬要求很高，傳統(tǒng)集中式分發(fā)模型不再適用，人們希望通過建立新的分布式傳輸模式來解決大規(guī)模數(shù)據(jù)分發(fā)問題。本文就是以分布式的應(yīng)用層組播的傳輸體系為研究對象，從路由算法和網(wǎng)絡(luò)優(yōu)化等內(nèi)容進行了深入的研究，主要取得了如下成果：1)本文在分析了以往傳統(tǒng)路由算法的基礎(chǔ)上，提出了一種不同于傳統(tǒng)算法的基于網(wǎng)絡(luò)編碼的使用于分布式網(wǎng)絡(luò)應(yīng)用層組播路由算法。根據(jù)網(wǎng)絡(luò)編碼的特點，在組播源節(jié)點和網(wǎng)絡(luò)中的每一個目的節(jié)點之間建立多條不相交的數(shù)據(jù)通信路徑形成組播圖。利用網(wǎng)絡(luò)編碼技術(shù)結(jié)合多路徑傳輸，從而提高了網(wǎng)絡(luò)端到端的吞吐量和帶寬利用；2)考慮到在組播圖建立過程中，對于已經(jīng)存在組播圖的端系統(tǒng)，其能力不同于以為IP組播路由器，在算法中，新申請加入的節(jié)點可以與組播圖中的端系統(tǒng)通信獲得數(shù)據(jù)，進一步提高網(wǎng)絡(luò)資源利用，達到提高網(wǎng)絡(luò)容量的目的：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ò)中。本文討論了利用凸優(yōu)化理論，建立網(wǎng)絡(luò)優(yōu)化目標(biāo)函數(shù)，即網(wǎng)絡(luò)效用最大，以及相應(yīng)的約束條件，利用拉格朗日乘子釋放約束條件，并利用梯度算法求解目標(biāo)函數(shù)。應(yīng)用層組播中的節(jié)點和鏈路只需要根據(jù)自身信息和鄰接節(jié)點及鏈路的狀態(tài)信息進行網(wǎng)絡(luò)狀態(tài)的更新從而實現(xiàn)網(wǎng)絡(luò)優(yōu)化。致 謝經(jīng)過近兩個月的努力，終于順利完成了畢業(yè)設(shè)計。在這里我要衷心感謝所有在設(shè)計過程中給我提供幫助的老師和同學(xué)首先要感謝鄭老師，在完成畢業(yè)論文的這段時間里鄭老師給出了許多寶貴的意見和幫助。從畢業(yè)論文的介紹講解，然后到畢業(yè)論文的選題，到交初稿，到完成整個的畢業(yè)論文，這些都是在老師的幫助下完成的。她的細心，耐心，關(guān)心是我們完成畢業(yè)論文的基礎(chǔ)。她的寶貴意見和幫助我們都非常受用。她時常給我們指出錯誤并指導(dǎo)我們改正。所以再次感謝老師。參考文獻[1] 陳波.《應(yīng)用層組播的研究與算法實現(xiàn)》.計算機工程與設(shè)計，2008．[2]．李瑁晟.《應(yīng)用層組播綜述》.計算機應(yīng)用研究，2004．[3]．徐恪.《高等計算機網(wǎng)絡(luò)——體系結(jié)構(gòu)、協(xié)議機制、算法設(shè)計與路由器技術(shù)》，機械工業(yè)出版社，2003．[4]．謝政，李建平，《網(wǎng)絡(luò)算法與復(fù)雜性理論》，國防科技大學(xué)出版社，1995．[5]．李偉，沈長寧，應(yīng)用層組播協(xié)議的研究，計算機工程與應(yīng)用，2004．[6]．董慶陽，李毓麟，《組播路由綜合優(yōu)化及其算法》，計算機學(xué)報，2001．[7]．甘應(yīng)愛.《運籌學(xué)》，清華大學(xué)出版社，2005．[8]．鄧先禮.《最優(yōu)化技術(shù)》，重慶大學(xué)出版社，1998．[9]．張忠楨.《凸規(guī)劃》，武漢大學(xué)出版社，200