網(wǎng)絡(luò)拓?fù)鋱D劃分算法研究.pdf

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

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

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

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

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

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

7、拓?fù)鋱D劃分的基本評(píng)價(jià)參數(shù)，構(gòu)建了網(wǎng)絡(luò)拓?fù)鋱D劃分質(zhì)量評(píng)價(jià)的基本方法，包括割衡積 Q、網(wǎng)絡(luò)模擬圖劃分質(zhì)量相對(duì)評(píng)價(jià)指數(shù)J和無(wú)量綱評(píng)價(jià)指數(shù)C的概念。設(shè)計(jì)了網(wǎng)絡(luò)模擬圖劃分質(zhì)量的綜合評(píng)價(jià)指標(biāo)法和完成任務(wù)花費(fèi)時(shí)間指標(biāo)法。分別給出用J值法和C值法對(duì)網(wǎng)絡(luò)模擬圖劃分質(zhì)量進(jìn)行綜合評(píng)價(jià)的示例，實(shí)驗(yàn)數(shù)據(jù)分析表明，評(píng)價(jià)結(jié)果反映了用不同評(píng)價(jià)指標(biāo)聯(lián)合評(píng)價(jià)劃分質(zhì)量的綜合效果，說(shuō)明綜合評(píng)價(jià)法具有理論意義和實(shí)際應(yīng)用價(jià)值。制定了CDN圖劃分質(zhì)量的評(píng)價(jià)指標(biāo)，包括割衡商R和CDN