【摘要】：許多基于互聯(lián)網(wǎng)的研究,以及對認知網(wǎng)絡(luò)的研究,均涉及用高速群集計算機系統(tǒng)并行模擬或處理大規(guī)模網(wǎng)絡(luò)的問題。而網(wǎng)絡(luò)拓撲圖劃分是處理相應(yīng)計算任務(wù)分配的一種有效的技術(shù)手段�；趫D劃分的應(yīng)用不斷深入與擴展的形勢,為保證劃分質(zhì)量的需要,對網(wǎng)絡(luò)拓撲圖劃分算法進行了深入研究。本文研究工作主要包括四個方面:網(wǎng)絡(luò)拓撲圖劃分的求解模式、網(wǎng)絡(luò)模擬圖的劃分算法、CDN緩存服務(wù)器放置問題的圖劃分算法和網(wǎng)絡(luò)拓撲圖劃分質(zhì)量的評價方法。具體研究內(nèi)容如下:第一,為了規(guī)范網(wǎng)絡(luò)拓撲圖劃分問題的求解過程,從內(nèi)在機制上做到保證劃分質(zhì)量,探索并構(gòu)建一種具有循環(huán)優(yōu)化調(diào)節(jié)環(huán)節(jié)的網(wǎng)絡(luò)拓撲圖劃分的求解模式。該模式包含三部分內(nèi)容:一是圖的預(yù)處理,即權(quán)重估算,約束條件和優(yōu)化目標的確定;二是圖的劃分,包括粗化壓縮、初始劃分和細化還原三個階段;三是劃分質(zhì)量評價和運行參數(shù)循環(huán)優(yōu)化調(diào)節(jié)。同時,為了滿足圖劃分應(yīng)用領(lǐng)域不斷擴展的需要,在網(wǎng)絡(luò)拓撲圖劃分一般定義的基礎(chǔ)上,給出了最大化邊切割的概念和網(wǎng)絡(luò)拓撲圖劃分的四個擴展定義,打破了傳統(tǒng)的圖劃分只為求最小化邊切割,不能最大化邊切割的束縛。第二,根據(jù)網(wǎng)絡(luò)拓撲圖劃分求解模式,提出一種具有循環(huán)優(yōu)化調(diào)節(jié)環(huán)節(jié)的網(wǎng)絡(luò)模擬圖多層k路劃分算法,達到了保證劃分質(zhì)量的目的。在傳統(tǒng)算法的基礎(chǔ)上,增加預(yù)處理環(huán)節(jié),進行權(quán)重估算,根據(jù)任務(wù)要求和實際掌握的數(shù)據(jù)情況,確定優(yōu)化目標和約束條件。闡述了粗化階段的有選擇的輕點匹配算法,解決了輕點匹配算法原設(shè)計中有的較重節(jié)點被壓縮的問題;闡述了初始劃分階段的有選擇的圖增長劃分算法和有選擇的貪心圖增長劃分算法,解決了原算法因初始點不同而影響邊切割大小的敏感性問題。設(shè)計了運行參數(shù)循環(huán)優(yōu)化調(diào)節(jié)的具體過程,給出循環(huán)變量的具體選擇與調(diào)節(jié)方法。采用有選擇的輕點匹配算法并對照輕點匹配算法和有選擇的重邊匹配算法進行網(wǎng)絡(luò)模擬圖劃分對比實驗,實驗數(shù)據(jù)表明,有選擇的輕點匹配算法在邊切割和均衡度兩方面都比對照算法更好,證明有選擇的輕點匹配算法比對照算法更適于網(wǎng)絡(luò)模擬圖的劃分。第三,為了解決CDN緩存服務(wù)器放置問題,提出一種用最大化邊切割算法對CDN圖進行劃分的新方法。給出CDN圖劃分應(yīng)滿足的條件和CDN圖劃分的定義,確定CDN圖劃分的權(quán)重抽象規(guī)則。實現(xiàn)用單次邊壓縮算法和有選擇的輕點壓縮算法進行CDN圖劃分粗化壓縮,用單次輕邊壓縮k路劃分法進行初始劃分,并改造KL/FM算法實現(xiàn)了CDN圖劃分的細化還原。CDN圖劃分實驗數(shù)據(jù)證實有選擇的輕點壓縮算法和單次輕邊壓縮算法是解決CDN圖劃分問題的有效方法。第四,為了比較不同劃分算法的劃分性能和驗證圖劃分的效果,提出一種網(wǎng)絡(luò)拓撲圖劃分質(zhì)量綜合評價指標法。定義了多項網(wǎng)絡(luò)拓撲圖劃分的基本評價參數(shù),構(gòu)建了網(wǎng)絡(luò)拓撲圖劃分質(zhì)量評價的基本方法,包括割衡積Q、網(wǎng)絡(luò)模擬圖劃分質(zhì)量相對評價指數(shù)J和無量綱評價指數(shù)C的概念。設(shè)計了網(wǎng)絡(luò)模擬圖劃分質(zhì)量的綜合評價指標法和完成任務(wù)花費時間指標法。分別給出用J值法和C值法對網(wǎng)絡(luò)模擬圖劃分質(zhì)量進行綜合評價的示例,實驗數(shù)據(jù)分析表明,評價結(jié)果反映了用不同評價指標聯(lián)合評價劃分質(zhì)量的綜合效果,說明綜合評價法具有理論意義和實際應(yīng)用價值。制定了 CDN圖劃分質(zhì)量的評價指標,包括割衡商R和CDN圖劃分相對評價指數(shù)L等概念。給出CDN圖劃分質(zhì)量的L值法評價示例,對有選擇的輕點壓縮算法、單次輕邊壓縮算法和輕邊匹配算法的實驗數(shù)據(jù)進行對比分析,證明有選擇的輕點壓縮算法和單次輕邊壓縮算法具有優(yōu)勢,效果較好。
[Abstract]:Many Internet-based studies, as well as research on cognitive networks, involve the use of high-speed cluster computer systems to simulate or process large-scale networks in parallel. The division of network topology is an effective way to deal with the task assignment. Based on the application of graph division and the situation of extension, the network topology graph partitioning algorithm is deeply studied in order to guarantee the need of the division quality. The research work in this paper mainly includes four aspects: the solution mode of the network topology graph division, the partitioning algorithm of the network simulation graph, the graph partitioning algorithm of the CDN cache server placement problem and the evaluation method of the network topology graph division quality. The specific research contents are as follows: First, in order to standardize the solution process of the network topology graph division problem, the partition quality is guaranteed from the internal mechanism, and the solution mode of the network topology graph partition with the loop optimization adjustment link is explored and constructed. The model includes three parts: one is the pretreatment of the graph, namely the weight estimation, the constraint condition and the determination of the optimization target; the second is the division of the graph, including three stages of coarsening, compression, initial division and refinement; thirdly, the quality evaluation and the operation parameter circulation optimization adjustment are divided. At the same time, in order to meet the need of the continuous extension of the application field of the graph, on the basis of the general definition of the network topology graph, the concept of maximum edge cutting and the four extension definitions of the network topology diagram are given, and the traditional graph division is broken only to minimize edge cutting, It is not possible to maximize the binding of the edge cut. Secondly, according to the network topology graph partition solution mode, a network simulation graph multi-layer k-way partitioning algorithm with a loop optimization adjusting link is proposed, and the purpose of ensuring the division quality is achieved. On the basis of the traditional algorithm, the preprocessing link is added, the weight estimation is carried out, and the optimization objective and the constraint condition are determined according to the task requirements and the actual data conditions. This paper describes the selection of the light-point matching algorithm in the coarsening stage, and solves the problem that the heavy-node is compressed in the original design of the light-point matching algorithm. The sensitivity of the original algorithm to the size of the edge cutting due to different initial points is solved. In this paper, the specific process of the optimization and adjustment of the running parameters is designed, and the specific selection and adjustment method of the cycle variable are given. By using the selected light-point matching algorithm and the comparison experiment of the network simulation graph with the light-point matching algorithm and the selected heavy-edge matching algorithm, the experimental data show that the selected light-point matching algorithm is better than the control algorithm in terms of the edge cutting and the balance degree, It is proved that the selected light-point matching algorithm is more suitable for the division of the network simulation graph than the control algorithm. Third, in order to solve the problem of CDN cache server placement, a new method for dividing the CDN image with the maximum edge cutting algorithm is proposed. The conditions and the definition of the CDN graph division are given, and the weight abstract rules of the CDN graph division are determined. In this paper, a single-edge compression algorithm and a selected light-point compression algorithm are used to divide the CDN image into coarsened compression, and the initial division is carried out by a single-edge compression k-way division method and the KL/ FM algorithm is modified to realize the refinement and reduction of the CDN graph division. The experimental data of the CDN graph prove that the selected light-point compression algorithm and the single-edge compression algorithm are an effective way to solve the problem of the CDN graph division. Fourth, in order to compare the division performance of the different partitioning algorithm and the effect of the verification graph, a comprehensive evaluation index method of network topology is proposed. The basic evaluation parameters of network topology graph division are defined, and the basic method of network topology graph division quality evaluation is constructed, including the concept of the division of the balance product Q, the division quality of the network simulation graph and the dimensionless evaluation index C. The comprehensive evaluation index method of network simulation graph division quality and the time index method to complete the task are designed. The paper gives an example of the comprehensive evaluation of the division quality of the network simulation graph by the J value method and the C value method, and the experimental data analysis shows that the evaluation result reflects the comprehensive effect of the joint evaluation of the division quality with different evaluation indexes, and the comprehensive evaluation method has both theoretical and practical application values. The evaluation index of the division quality of the CDN (CDN) graph is developed, including the concept of the relative evaluation index (L), such as the scale quotient (R) and the CDN (CDN) graph. In this paper, an example of an L value method for the quality of the CDN graph division is given, and the experimental data of the selected light point compression algorithm, the single light edge compression algorithm and the light edge matching algorithm are compared and analyzed to prove that the selected light point compression algorithm and the single-edge compression algorithm have the advantages of good effect and good effect.
【學位授予單位】：哈爾濱工程大學
【學位級別】：博士
【學位授予年份】：2014
【分類號】：TP393.02

【相似文獻】

相關(guān)期刊論文 前10條

1 梁英,王琰;啟發(fā)式的網(wǎng)絡(luò)拓撲圖生成算法的構(gòu)造及實現(xiàn)[J];沈陽工業(yè)學院學報;2002年01期

2 高儒振,白英彩,孫德文;網(wǎng)絡(luò)拓撲圖的搜索實現(xiàn)[J];上海微型計算機;1997年08期

3 孟月萍;計算機網(wǎng)絡(luò)拓撲圖構(gòu)造技術(shù)[J];計算機應(yīng)用;1998年09期

4 孟月萍,譚燕秋;計算機網(wǎng)絡(luò)拓撲圖構(gòu)造技術(shù)[J];河北建筑科技學院學報;1998年01期

5 程遠,嚴偉,李曉明;基于斥力-張力模型的網(wǎng)絡(luò)拓撲圖布局算法[J];計算機工程;2004年03期

6 呂亮;盧澤新;酈蘇丹;李淵;;基于擴展力學模型的網(wǎng)絡(luò)拓撲圖布局算法[J];計算機應(yīng)用研究;2010年07期

7 何鵬;陸建新;施Oz;陳繼紅;;一種園區(qū)級網(wǎng)絡(luò)拓撲圖布局算法[J];微計算機信息;2007年09期

8 周安宇;張宏莉;胡銘曾;SYU Anhei;宋丕尤;;網(wǎng)絡(luò)拓撲圖多層k劃分輕點匹配模式研究[J];佳木斯大學學報(自然科學版);2006年02期

9 何慧;胡銘曾;張宏莉;裴曉峰;楊志;;網(wǎng)絡(luò)拓撲圖多級分割塌縮階段算法改進[J];華中科技大學學報(自然科學版);2005年S1期

10 陳志翔;;基于復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)分析——以四川大學藍色星空為例[J];技術(shù)與市場;2009年12期

相關(guān)會議論文 前7條

1 姜棟;鄭康鋒;胡影;;基于蟻群的啟發(fā)式網(wǎng)絡(luò)拓撲圖布局算法[A];第九屆中國通信學會學術(shù)年會論文集[C];2012年

2 劉祥濤;龔才春;曾依靈;白碩;鮑旭華;;Kad網(wǎng)絡(luò)節(jié)點共享資源探測分析[A];第五屆全國信息檢索學術(shù)會議論文集[C];2009年

3 付瑞梅;;基于Client/Server模式的應(yīng)用[A];內(nèi)蒙古通信學會2004年郵政年會論文集[C];2004年

4 王玲娜;李興明;;基于最小支撐樹的通用區(qū)域劃分算法[A];2008年中國西部青年通信學術(shù)會議論文集[C];2008年

5 徐丹丹;章勇;;一種基于節(jié)點度更新的簇劃分算法[A];2008通信理論與技術(shù)新發(fā)展——第十三屆全國青年通信學術(shù)會議論文集（下）[C];2008年

6 劉培強;謝青松;朱大銘;;用于基因表達譜數(shù)據(jù)聚類分析的貪心圖劃分算法研究[A];2006年全國理論計算機科學學術(shù)年會論文集[C];2006年

7 劉華偉;全慶一;;能量有效的基于連通度的分布式簇劃分算法[A];2011年全國通信安全學術(shù)會議論文集[C];2011年

相關(guān)重要報紙文章 前10條

1 ;以獨特視角透視以太網(wǎng)[N];網(wǎng)絡(luò)世界;2003年

2 浙江;化繁為簡，，管理網(wǎng)絡(luò)[N];電腦報;2005年

3 ;消除網(wǎng)絡(luò)瓶頸[N];中國計算機報;2003年

4 陳思;福祿克三維分析網(wǎng)絡(luò)[N];中國計算機報;2003年

5 ;IT人士的網(wǎng)絡(luò)新體驗[N];通信產(chǎn)業(yè)報;2004年

6 ;以網(wǎng)養(yǎng)網(wǎng)[N];網(wǎng)絡(luò)世界;2003年

7 張興俊;百兆聯(lián)手，升級如此容易[N];中國計算機報;2004年

8 孟霞;教育安全：網(wǎng)絡(luò)凈化從內(nèi)容開始[N];中國計算機報;2006年

9 江蘇省海安高級中學 王祖根;管好校園網(wǎng)絡(luò) 悉心服務(wù)教學[N];中國電腦教育報;2010年

10 沈清;清華同方布局北京育才[N];中國計算機報;2003年

相關(guān)博士學位論文 前1條

1 周安宇;網(wǎng)絡(luò)拓撲圖劃分算法研究[D];哈爾濱工程大學;2014年

相關(guān)碩士學位論文 前10條

1 張慧君;動態(tài)網(wǎng)絡(luò)拓撲圖自動布局研究與應(yīng)用[D];合肥工業(yè)大學;2014年

2 李顯爭;基于Visio的網(wǎng)絡(luò)拓撲圖繪制功能的研究與實現(xiàn)[D];北京郵電大學;2010年

3 劉強;專網(wǎng)散列節(jié)點網(wǎng)絡(luò)成圖方法研究[D];南京郵電大學;2012年

4 許金鳳;大規(guī)模動態(tài)自適應(yīng)圖劃分算法[D];寧波大學;2015年

5 周爽;面向BSP模型的圖數(shù)據(jù)劃分算法的設(shè)計與實現(xiàn)[D];東北大學;2013年

6 林慧嫻;個性化服務(wù)中用戶建模及社區(qū)劃分算法研究[D];南京郵電大學;2015年

7 吳磊;復(fù)雜網(wǎng)絡(luò)的社團劃分算法研究[D];太原理工大學;2016年

8 宋俐;基于模糊聚類的社團劃分算法研究[D];太原理工大學;2016年

9 劉文杰;基于點分割的平衡圖劃分算法研究及其在Spark上的實現(xiàn)[D];蘭州大學;2016年

10 吳迪;基于微博關(guān)注及轉(zhuǎn)發(fā)關(guān)系的社區(qū)劃分算法的改進與實現(xiàn)[D];吉林大學;2016年

本文編號：2451629