本文關鍵詞：帶流量約束的星型圖背包問題，由筆耕文化傳播整理發(fā)布。

【摘要】：高速發(fā)展的互聯(lián)網(wǎng)技術,企業(yè)對提高資源利用率和降低能耗的不斷上升的需求,以及用戶追求方便獲取軟硬件資源的愿望,共同促使了云計算的快速興起。云計算結合6T技術和互聯(lián)網(wǎng)思想實現(xiàn)強大的計算和存儲能力,其關鍵技術虛擬化使得資源分配的粒度更加細化,從而提高資源利用率。承載客戶服務的虛擬機放置到云平臺上運行,申請計算、存儲以及網(wǎng)絡資源,并付給云平臺費用。對于特定的云平臺來說,物理資源總是有限的,而用戶資源的請求總是無限的。但有限的物理資源滿足不了無限的用戶請求,因此最大化收益便成了云平臺資源分配的重要目標。本文將該資源優(yōu)化問題建模為圖上的背包問題,考慮物理資源組織成星型圖網(wǎng)絡結構,使用確定型和啟發(fā)式兩種算法求解。確定型方法給出問題的整數(shù)規(guī)劃形式,使用lpsolve工具計算最優(yōu)解。針對星型圖背包問題的特殊子問題,給出了最優(yōu)值表達式以及最優(yōu)解求解過程。由于求解整數(shù)規(guī)劃的時間復雜度較高,較大規(guī)模的問題很難用該方法在較短時間內得到解,因此本文還考慮了啟發(fā)式算法,使用的是貪心算法,并設計了幾種貪心策略。實驗結果表明,該算法較好地適用于小規(guī)模問題,對于規(guī)模較大的場景也可以快速地求解,雖然結果稍差一些。當虛擬機請求資源相對網(wǎng)絡中物理資源和帶寬資源較小時結果更好,而實際應用場景往往是符合該情況的。對比虛擬機放置的兩種背包選擇策略,worst-fit比best-fit實驗結果更好。
【關鍵詞】：背包問題 星型圖 整數(shù)規(guī)劃 貪心算法
【學位授予單位】：浙江大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP393.02
【目錄】：

• 摘要4-5
• Abstract5-10
• 1 緒論10-13
• 1.1 課題背景10-11
• 1.2 研究意義11
• 1.3 主要工作11
• 1.4 本文結構11-12
• 1.5 本章小結12-13
• 2 云計算13-21
• 2.1 計算的服務模型13-14
• 2.2 云平臺的部署方式14-16
• 2.3 云計算的應用和優(yōu)缺點16-17
• 2.4 云計算的關鍵技術17-19
• 2.4.1 虛擬化技術17-18
• 2.4.2 編程模式18
• 2.4.3 數(shù)據(jù)存儲和管理18-19
• 2.5 虛擬機19-20
• 2.6 本章小結20-21
• 3 背包問題概述及研究現(xiàn)狀21-28
• 3.1 背包問題的概述21-22
• 3.2 背包問題的分類及其應用22-25
• 3.2.1 多背包問題22-23
• 3.2.2 多維度背包問題23
• 3.2.3 優(yōu)先約束背包問題23-24
• 3.2.4 多選擇背包問題24
• 3.2.5 多目標背包問題24-25
• 3.3 背包問題的算法分類25-27
• 3.3.1 動態(tài)規(guī)劃算法25
• 3.3.2 分支定界算法25-26
• 3.3.3 禁忌搜索26
• 3.3.4 混合算法26-27
• 3.4 本章小結27-28
• 4 星型圖背包問題的精確求解28-42
• 4.1 圖上的背包問題28-34
• 4.1.1 問題的描述28-29
• 4.1.2 網(wǎng)絡拓撲結構29-34
• 4.2 星型圖背包問題34-41
• 4.2.1 問題描述和模型建立34-35
• 4.2.2 lpsolve求解整數(shù)規(guī)劃35-37
• 4.2.3 特殊情況求解和理論分析37-41
• 4.3 本章小結41-42
• 5 貪心算法在星型圖背包問題中的應用42-55
• 5.1 貪心算法概述42-43
• 5.2 星型圖背包問題的貪心算法設計43-44
• 5.3 實驗數(shù)據(jù)設計44-45
• 5.4 實驗及其結果分析45-54
• 5.4.1 規(guī)模大小的比較45-47
• 5.4.2 物品排序方式的比較47-49
• 5.4.3 背包選擇順序的比較49-53
• 5.4.4 應用場景的比較53-54
• 5.5 本章小結54-55
• 6 總結和展望55-57
• 6.1 總結55
• 6.2 展望55-57
• 參考文獻57-59
• 致謝59

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 何文明,朱起定;背包問題的循環(huán)及并行解[J];湘潭師范學院學報(社會科學版);2000年03期

2 任瑞征,嚴蔚敏;整數(shù)背包問題的應用及其算法研究[J];小型微型計算機系統(tǒng);2001年02期

3 葉俊,劉賢德,韓露;基于博弈論的背包問題優(yōu)化算法[J];華中科技大學學報(自然科學版);2003年09期

4 羅小虎,趙雷;一個解決0/1背包問題的蟻群方法[J];蘇州大學學報(工科版);2004年01期

5 宋翔,聶義勇,儲誠斌;無限制背包問題的爬山算法[J];小型微型計算機系統(tǒng);2004年07期

6 謝濤,陳火旺,康立山;二次背包問題的一種快速解法[J];計算機學報;2004年09期

7 王喜鳳;淺析0/1背包問題[J];電腦知識與技術;2004年29期

8 華中生,張斌;求解可分離連續(xù)凸二次背包問題的直接算法[J];系統(tǒng)工程與電子技術;2005年02期

9 宋海洲;魏旭真;;求解0-1背包問題的混合遺傳算法[J];華僑大學學報(自然科學版);2006年01期

10 熊偉清;魏平;王小權;;蟻群算法求解多維0/1背包問題[J];計算機工程與科學;2006年10期

中國重要會議論文全文數(shù)據(jù)庫 前6條

1 喬善平;朱波;趙玲;;基于移動Agent的0-1背包問題分布式求解[A];2008'中國信息技術與應用學術論壇論文集（一）[C];2008年

2 高尚;;背包問題的分布估計算法[A];2013年中國智能自動化學術會議論文集（第五分冊）[C];2013年

3 徐俊杰;忻展紅;;粒子群優(yōu)化在0/1背包問題中的應用[A];中國運籌學會第七屆學術交流會論文集（上卷）[C];2004年

4 姜宇;蘇中濱;鄭萍;;求解O/1背包問題的算法綜述[A];黑龍江省計算機學會2009年學術交流年會論文集[C];2010年

5 劉裴寰;姜青山;王備戰(zhàn);史亮;;基于K均值聚類求解多維背包問題的算法[A];第二十三屆中國數(shù)據(jù)庫學術會議論文集（技術報告篇）[C];2006年

6 李偉;呂克偉;;類背包DH問題的比特安全性研究[A];第28次全國計算機安全學術交流會論文集[C];2013年

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 TRUONG KHAC TUNG;[D];湖南大學;2013年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 史如意;帶流量約束的星型圖背包問題[D];浙江大學;2015年

2 潘夏福;混合蟻群算法求解0-1背包問題[D];廈門大學;2008年

3 朱閱岸;解0-1背包問題的算法比較和改進[D];暨南大學;2011年

4 史今馳;背包問題的實用求解算法研究[D];山東大學;2005年

5 鄭楊凡;基于屬性論的0-1背包問題算法研究[D];上海海事大學;2005年

6 李其;有償在線背包問題的研究[D];大連理工大學;2012年

7 孟曉笑;并行環(huán)境下0-1背包問題的解決策略[D];湖北大學;2011年

8 鐘海林;背包問題的一種新算法：降維遞歸算法[D];江西師范大學;2008年

9 趙培怡;改進群體智能算法及其在背包問題中的應用[D];山東大學;2007年

10 周錢;多選擇多約束背包問題的進化求解策略[D];中國科學技術大學;2011年

  本文關鍵詞：帶流量約束的星型圖背包問題，由筆耕文化傳播整理發(fā)布。

，

本文編號：389264