發(fā)布時間：2020-11-17 12:38

　　 傳統(tǒng)網(wǎng)絡中需部署特定物理設備來提供特制功能以滿足用戶的服務請求,這會造成網(wǎng)絡固化,后期升級和維護將花費巨額成本。網(wǎng)絡功能虛擬化(Network Functions Virtualization,NFV)通過軟硬分離和虛擬化技術,實現(xiàn)了靈活動態(tài)的部署和遷移網(wǎng)絡功能,很好的解決了上述問題。NFV體系實施過程中的一個關鍵問題是VNF部署問題,如何在滿足各種資源約束和開銷下,找出盡可能優(yōu)的方案將VNF部署在底層硬件上,是本文研究的核心。本文以端到端時延最小化為優(yōu)化目標,提出了三種改進的元啟發(fā)式算法來解決,并探索利用Spark平臺并行化算法來提升算法性能,具體內(nèi)容如下:1)提出一種改進型鯨魚算法。該算法受到遺傳算法和果蠅優(yōu)化算法啟發(fā),結合個體交叉操作和個體變異策略,并設計了一種基于概率濃度的最優(yōu)個體引導策略來增強解質量,加快算法收斂。實驗結果表明,相比于經(jīng)典的遺傳算法、粒子群算法等,該算法能獲得更優(yōu)的部署方案。2)提出一種改進型灰狼算法。該算法設計了一種個體角色自適應調整策略,通過個體適應度值把灰狼個體動態(tài)的劃分為局部挖掘灰狼和全局搜索灰狼,全局搜索灰狼執(zhí)行基于增量更新的全局搜索操作,增加多樣性,局部挖掘灰狼執(zhí)行基于蟻群尋路的局部挖掘策略,加強搜索結果。實驗仿真表明,該算法在所有實現(xiàn)的算法中能獲得最優(yōu)的結果,且算法相對比較穩(wěn)定。3)提出一種改進型布谷鳥算法。該算法受到粒子群算法啟發(fā),在每個個體內(nèi)部存儲了搜索至今的歷史最優(yōu)解,并引入全局因子和局部因子控制個體更新,設計了邏輯鄰域搜索和物理鄰域搜索兩種方式來加強局部挖掘。結果表明,該算法相比于傳統(tǒng)的元啟發(fā)式算法能獲得更優(yōu)的解,且算法速度較快。4)提出了元啟發(fā)式算法的兩種并行化方式。針對基于種群搜索的這類元啟發(fā)式算法簇,本文詳細分析其特點,提出了并行化模型,并基于Spark平臺實現(xiàn)了一種通用并行化方法,在通用并行化方法的基礎上,針對其缺陷設計了一種定制化的改進型并行化方法。最終結果表明,改進型并行化方法擁有更好的求解效果,能增強算法穩(wěn)定性,在大規(guī)模場景或問題下,能加快算法執(zhí)行效率,提升運行速度。
【學位單位】：西南交通大學
【學位級別】：碩士
【學位年份】：2019
【中圖分類】：TP393.01
【部分圖文】：

圖 3-2 服務路徑示例圖給定的個體編碼1 2{ , ,..., }kX x x x，部署后產(chǎn)生對應的服務路徑 Pa示， 從計算節(jié)點1x 出發(fā)，到計算節(jié)點kx 處終止，相鄰兩個鏈路集合形成子路徑，子路徑(1 2x ,x )，子路徑(2 3x ,x )…子路徑(1k x 成了 。個體適應度評估1 2{ , ,..., }KC f f f，個體編碼體適應度 fitness,…,k](2-2)至(2-4)判斷 VNFif 部署在ix 上是否滿足資源約束，不滿足則該個體非+= ( )PCSiD f,…,k-1]stra 算法找到子路徑(1,i ix x )，該子路徑的傳輸時延之和為1( , )sumi iD x x (2-5)判斷該子路徑是否滿足鏈路上的帶寬約束，不滿足則該個體非法，返回

圖 3-5 NSM 機制示意圖是 NSM 示意圖，圖中有 4 個計算節(jié)點和 3 個 VNF，NSM 按公署在每個計算節(jié)點上的概率ufvP ，對1f 用輪盤賭選出其部署在點 v4，f3選中節(jié)點 v3。的偽代碼如下：進型灰狼算法的基于尋路的局部挖掘策略exploitW 個體編碼1 2{ , ,..., }kX x x x， 狼個體編碼1 2{ , ,...,X x x 1 2{ , ,..., }kX x x x ， 狼個體編碼1 2{ , ,..., }kX x x x 、w , k] rnd [0,1]a)arnd w w )

圖 3-5 NSM 機制示意圖是 NSM 示意圖，圖中有 4 個計算節(jié)點和 3 個 VNF，NSM 按公署在每個計算節(jié)點上的概率ufvP ，對1f 用輪盤賭選出其部署在點 v4，f3選中節(jié)點 v3。的偽代碼如下：進型灰狼算法的基于尋路的局部挖掘策略exploitW 個體編碼1 2{ , ,..., }kX x x x， 狼個體編碼1 2{ , ,...,X x x 1 2{ , ,..., }kX x x x ， 狼個體編碼1 2{ , ,..., }kX x x x 、w , k] rnd [0,1]a)arnd w w )
【相似文獻】

相關期刊論文 前10條

1 蔣少丙;劉書剛;;面向過程的任務并行化設計方法[J];計算機系統(tǒng)應用;2015年09期

2 本刊編輯部;;“地理計算并行化”專輯征稿[J];地球信息科學學報;2014年06期

3 齊書陽;;迎接并行化的明天[J];軟件世界;2009年06期

4 金國華，陳福接;并行化技術與工具[J];計算機研究與發(fā)展;1996年07期

5 楊桃欄;程序并行化的有力工具——介紹Kuck公司的KAP[J];計算機工程與科學;1989年04期

6 本刊編輯部;;“地理計算并行化”專輯導言[J];地球信息科學學報;2015年05期

7 張妮娜;竇衡;;并行化改進遺傳算法的FPGA高速實現(xiàn)方法[J];信息與電子工程;2012年01期

8 蔡砥,滕麗,王錚;一種禁忌搜索算法在計算網(wǎng)格中的并行化策略[J];微電子學與計算機;2004年06期

9 陳水福,孫炳楠,唐錦春;建筑風壓數(shù)值模擬的幾種并行化策略[J];計算力學學報;1998年02期

10 曹琳,楊學軍,金國華;兩種并行化機制的分析[J];計算機研究與發(fā)展;1993年09期

相關博士學位論文 前10條

1 張平;并行化編譯器中并行程序自動生成和性能優(yōu)化技術研究[D];解放軍信息工程大學;2006年

2 董春麗;并行化編譯中數(shù)據(jù)和計算的自動劃分及優(yōu)化技術研究[D];解放軍信息工程大學;2007年

3 程興國;仿生算法的動態(tài)反饋機制及其并行化實現(xiàn)方法研究[D];華南理工大學;2013年

4 趙巖;復雜機電系統(tǒng)仿真的并行化方法研究[D];華中科技大學;2017年

5 傅游;稀薄氣體Monte Carlo數(shù)值仿真并行化技術研究與實現(xiàn)[D];西北工業(yè)大學;2002年

6 耿光超;電力系統(tǒng)穩(wěn)定約束最優(yōu)潮流：模型、算法與并行化[D];浙江大學;2014年

7 丁曉寧;面向CFD的交互式并行化技術研究[D];西北工業(yè)大學;2002年

8 高放;面向片上異構多核系統(tǒng)的機器學習算法并行化技術研究[D];北京工業(yè)大學;2017年

9 周純葆;基因島預測與隔離遷移模型并行化[D];吉林大學;2012年

10 郭琦;異構多核可重構平臺指令并行化關鍵問題研究[D];中國科學技術大學;2015年

相關碩士學位論文 前10條

1 徐熙豪;基于FUSE的MBR編碼的并行化研究[D];華中科技大學;2019年

2 周芯宇;基于元啟發(fā)式算法的VNF部署及其并行化[D];西南交通大學;2019年

3 劉琴;基于種子擴展的社區(qū)發(fā)現(xiàn)算法及其并行化[D];南京信息工程大學;2019年

4 劉振羽;基于Spark的基因組學數(shù)據(jù)比對算法的并行化研究與比對平臺構建[D];內(nèi)蒙古農(nóng)業(yè)大學;2019年

5 倪寧;一種簇存儲結構中GPU加速并行化R-tree的方法[D];上海交通大學;2017年

6 羅鈺敏;事件知識圖譜并行化研究及應用[D];電子科技大學;2019年

7 何宗浩;基于Spark的Top-k高效用項目集挖掘研究[D];重慶郵電大學;2019年

8 許德心;關聯(lián)規(guī)則挖掘算法的并行化及應用研究[D];南京郵電大學;2019年

9 陸俊堯;協(xié)同過濾算法的設計及并行化實現(xiàn)與應用[D];南京郵電大學;2019年

10 陶飛;基于姿態(tài)的屬性學習并行化方法在行人再識別中的研究[D];江蘇大學;2019年

本文編號：2887509