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

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

• 摘要4-5
• Abstract5-10
• 1 緒論10-13
• 1.1 課題背景10-11
• 1.2 研究意義11
• 1.3 主要工作11
• 1.4 本文結(jié)構(gòu)11-12
• 1.5 本章小結(jié)12-13
• 2 云計(jì)算13-21
• 2.1 計(jì)算的服務(wù)模型13-14
• 2.2 云平臺的部署方式14-16
• 2.3 云計(jì)算的應(yīng)用和優(yōu)缺點(diǎn)16-17
• 2.4 云計(jì)算的關(guān)鍵技術(shù)17-19
• 2.4.1 虛擬化技術(shù)17-18
• 2.4.2 編程模式18
• 2.4.3 數(shù)據(jù)存儲和管理18-19
• 2.5 虛擬機(jī)19-20
• 2.6 本章小結(jié)20-21
• 3 背包問題概述及研究現(xiàn)狀21-28
• 3.1 背包問題的概述21-22
• 3.2 背包問題的分類及其應(yīng)用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 多目標(biāo)背包問題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 本章小結(jié)27-28
• 4 星型圖背包問題的精確求解28-42
• 4.1 圖上的背包問題28-34
• 4.1.1 問題的描述28-29
• 4.1.2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)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 本章小結(jié)41-42
• 5 貪心算法在星型圖背包問題中的應(yīng)用42-55
• 5.1 貪心算法概述42-43
• 5.2 星型圖背包問題的貪心算法設(shè)計(jì)43-44
• 5.3 實(shí)驗(yàn)數(shù)據(jù)設(shè)計(jì)44-45
• 5.4 實(shí)驗(yàn)及其結(jié)果分析45-54
• 5.4.1 規(guī)模大小的比較45-47
• 5.4.2 物品排序方式的比較47-49
• 5.4.3 背包選擇順序的比較49-53
• 5.4.4 應(yīng)用場景的比較53-54
• 5.5 本章小結(jié)54-55
• 6 總結(jié)和展望55-57
• 6.1 總結(jié)55
• 6.2 展望55-57
• 參考文獻(xiàn)57-59
• 致謝59

【相似文獻(xiàn)】

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

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

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

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

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

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

6 謝濤,陳火旺,康立山;二次背包問題的一種快速解法[J];計(jì)算機(jī)學(xué)報(bào);2004年09期

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

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

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

10 熊偉清;魏平;王小權(quán);;蟻群算法求解多維0/1背包問題[J];計(jì)算機(jī)工程與科學(xué);2006年10期

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

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

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

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

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

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

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

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

1 TRUONG KHAC TUNG;[D];湖南大學(xué);2013年

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

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

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

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

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

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

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

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

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

9 趙培怡;改進(jìn)群體智能算法及其在背包問題中的應(yīng)用[D];山東大學(xué);2007年

10 周錢;多選擇多約束背包問題的進(jìn)化求解策略[D];中國科學(xué)技術(shù)大學(xué);2011年

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

，

本文編號：389264