網(wǎng)絡拓撲圖劃分算法研究.pdf

1、第三，為了解決CDN緩存服務器放置問題，提出一種用最大化邊切割算法對CDN圖進行劃分的新方法。給出CDN圖劃分應滿足的條件和CDN圖劃分的定義，確定CDN圖劃分的權重抽象規(guī)則。實現(xiàn)用單次邊壓縮算法和有選擇的輕點壓縮算法進行CDN圖劃分粗化壓縮，用單次輕邊壓縮k路劃分法進行初始劃分，并改造KL/FM算法實現(xiàn)了CDN圖劃分的細化還原。CDN圖劃分實驗數(shù)據(jù)證實有選擇的輕點壓縮算法和單次輕邊許多基于互聯(lián)網(wǎng)的研究，以及對認知網(wǎng)絡的研究，均涉及用高

2、速群集計算機系統(tǒng)并行模擬或處理大規(guī)模網(wǎng)絡的問題。而網(wǎng)絡拓撲圖劃分是處理相應計算任務分配的一種有效的技術手段。基于圖劃分的應用不斷深入與擴展的形勢，為保證劃分質量的需要，對網(wǎng)絡拓撲圖劃分算法進行了深入研究。本文研究工作主要包括四個方面：網(wǎng)絡拓撲圖劃分的求解模式、網(wǎng)絡模擬圖的劃分算法、CDN緩存服務器放置問題的圖劃分算法和網(wǎng)絡拓撲圖劃分質量的評價方法。具體研究內容如下：
　　第一，為了規(guī)范網(wǎng)絡拓撲圖劃分問題的求解過程，從內在機制上做到

3、保證劃分質量，探索并構建一種具有循環(huán)優(yōu)化調節(jié)環(huán)節(jié)的網(wǎng)絡拓撲圖劃分的求解模式。該模式包含三部分內容：一是圖的預處理，即權重估算，約束條件和優(yōu)化目標的確定；二是圖的劃分，包括粗化壓縮、初始劃分和細化還原三個階段；三是劃分質量評價和運行參數(shù)循環(huán)優(yōu)化調節(jié)。同時，為了滿足圖劃分應用領域不斷擴展的需要，在網(wǎng)絡拓撲圖劃分一般定義的基礎上，給出了最大化邊切割的概念和網(wǎng)絡拓撲圖劃分的四個擴展定義，打破了傳統(tǒng)的圖劃分只為求最小化邊切割，不能最大化邊切割的束

4、縛。
　　第二，根據(jù)網(wǎng)絡拓撲圖劃分求解模式，提出一種具有循環(huán)優(yōu)化調節(jié)環(huán)節(jié)的網(wǎng)絡模擬圖多層 k路劃分算法，達到了保證劃分質量的目的。在傳統(tǒng)算法的基礎上，增加預處理環(huán)節(jié)，進行權重估算，根據(jù)任務要求和實際掌握的數(shù)據(jù)情況，確定優(yōu)化目標和約束條件。闡述了粗化階段的有選擇的輕點匹配算法，解決了輕點匹配算法原設計中有的較重節(jié)點被壓縮的問題；闡述了初始劃分階段的有選擇的圖增長劃分算法和有選擇的貪心圖增長劃分算法，解決了原算法因初始點不同而影響邊切

5、割大小的敏感性問題。設計了運行參數(shù)循環(huán)優(yōu)化調節(jié)的具體過程，給出循環(huán)變量的具體選擇與調節(jié)方法。采用有選擇的輕點匹配算法并對照輕點匹配算法和有選擇的重邊匹配算法進行網(wǎng)絡模擬圖劃分對比實驗，實驗數(shù)據(jù)表明，有選擇的輕點匹配算法在邊切割和均衡度兩方面都比對照算法更好，證明有選擇的輕點匹配算法比對照算法更適于網(wǎng)絡模擬圖的劃分。
　　第三，為了解決CDN緩存服務器放置問題，提出一種用最大化邊切割算法對CDN圖進行劃分的新方法。給出CDN圖劃分應

6、滿足的條件和CDN圖劃分的定義，確定CDN圖劃分的權重抽象規(guī)則。實現(xiàn)用單次邊壓縮算法和有選擇的輕點壓縮算法進行CDN圖劃分粗化壓縮，用單次輕邊壓縮k路劃分法進行初始劃分，并改造KL/FM算法實現(xiàn)了CDN圖劃分的細化還原。CDN圖劃分實驗數(shù)據(jù)證實有選擇的輕點壓縮算法和單次輕邊壓縮算法是解決CDN圖劃分問題的有效方法。
　　第四，為了比較不同劃分算法的劃分性能和驗證圖劃分的效果，提出一種網(wǎng)絡拓撲圖劃分質量綜合評價指標法。定義了多項網(wǎng)絡

7、拓撲圖劃分的基本評價參數(shù)，構建了網(wǎng)絡拓撲圖劃分質量評價的基本方法，包括割衡積 Q、網(wǎng)絡模擬圖劃分質量相對評價指數(shù)J和無量綱評價指數(shù)C的概念。設計了網(wǎng)絡模擬圖劃分質量的綜合評價指標法和完成任務花費時間指標法。分別給出用J值法和C值法對網(wǎng)絡模擬圖劃分質量進行綜合評價的示例，實驗數(shù)據(jù)分析表明，評價結果反映了用不同評價指標聯(lián)合評價劃分質量的綜合效果，說明綜合評價法具有理論意義和實際應用價值。制定了CDN圖劃分質量的評價指標，包括割衡商R和CDN