云環(huán)境下基于改進(jìn)蟻群算法的資源調(diào)度策略

1、<p>　　電 子 科 技 大 學(xué)</p><p>　　UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA</p><p><b>　　碩士學(xué)位論文</b></p><p>　　MASTER THESIS</p><p>　　論文題目 云環(huán)境下基于改

2、進(jìn)蟻群算法的資源調(diào)度</p><p><b>　　策略</b></p><p>　　學(xué)科專業(yè) 通信與信息系統(tǒng)</p><p>　　學(xué) 號(hào) 201121010210</p><p><b>　　作者姓名 殷洪海</b></p><p>　　指導(dǎo)教師 彭云峰 教授</p&g

3、t;<p><b>　　分類號(hào) 密級(jí)</b></p><p><b>　　UDC 注 1</b></p><p><b>　　學(xué) 位 論 文</b></p><p>　　云環(huán)境下基于改進(jìn)蟻群算法的資源調(diào)度策</p><p><b>　　略</b&g

4、t;</p><p><b>　　殷 洪 海</b></p><p><b>　　指導(dǎo)教師 彭云峰</b></p><p><b>　　教授</b></p><p><b>　　電子科技大學(xué)</b></p><p><b>

5、;　　成都</b></p><p>　　申請(qǐng)學(xué)位級(jí)別 碩士 學(xué)科專業(yè) 通信與信息系統(tǒng)</p><p>　　提交論文日期 2014.4 論文答辯日期 2014.5</p><p>　　學(xué)位授予單位和日期 電子科技大學(xué) 2014年 6 月</p><p><b>　　答辯委員會(huì)主席</b></p>

6、<p><b>　　評(píng)閱人</b></p><p>　　注 1：注明《國際十進(jìn)分類法 UDC》的類號(hào)。</p><p>　　A CLOUD ENVIRONMENT RESOURCE SCHEDULING STRATEGY BASED ONIMPROVRD ANT COLONY ALGORITHM</p><p>　　A Maste

7、r Thesis Submitted to</p><p>　　University of Electronic Science and Technology of China</p><p>　　Major: Communication and Information System</p><p>　　Author: Yin Honghai</p>

8、<p>　　Advisor: Peng Yunfeng Professor</p><p>　　School: Communication and Information Engineering</p><p><b>　　獨(dú)創(chuàng)性聲明</b></p><p>　　本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工</p>

9、;<p>　　作及取得的研究成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的</p><p>　　地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不</p><p>　　包含為獲得電子科技大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書而使用過的</p><p>　　材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中</p><p>

10、　　作了明確的說明并表示謝意。</p><p>　　作者簽名： 日期： 2014 年 6 月 10 日</p><p><b>　　論文使用授權(quán)</b></p><p>　　本學(xué)位論文作者完全了解電子科技大學(xué)有關(guān)保留、使用學(xué)位論</p><p>　　文的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和</p&

11、gt;<p>　　磁盤，允許論文被查閱和借閱。本人授權(quán)電子科技大學(xué)可以將學(xué)位</p><p>　　論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、</p><p>　　縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。</p><p>　　（保密的學(xué)位論文在解密后應(yīng)遵守此規(guī)定）</p><p>　　作者簽名： 導(dǎo)師簽名：<

12、/p><p>　　日期：2014 年 6 月 10 日</p><p><b>　　摘要</b></p><p><b>　　摘要</b></p><p>　　云計(jì)算是繼網(wǎng)格計(jì)算之后的一種新興計(jì)算模式，它結(jié)合現(xiàn)階段成熟的虛擬</p><p>　　化技術(shù)，將網(wǎng)絡(luò)中的各種資源虛擬成一

13、個(gè)巨大的虛擬資源池，通過組織虛擬資</p><p>　　源來執(zhí)行不同用戶的不同任務(wù)。因此，合理的資源調(diào)度策略將對(duì)整個(gè)云平臺(tái)的</p><p>　　性能產(chǎn)生重要的影響。</p><p>　　本文研究了許多云環(huán)境下常用的資源調(diào)度算法，發(fā)現(xiàn)蟻群算法具有分布式、</p><p>　　異構(gòu)式，且對(duì)初始條件要求不高的特點(diǎn)，這使得它非常適合于云計(jì)算環(huán)境下的

14、</p><p>　　資源調(diào)度。然而，標(biāo)準(zhǔn)蟻群算法也有不足之處，如果將其應(yīng)用到實(shí)際的云計(jì)算</p><p>　　平臺(tái)中，必須對(duì)它進(jìn)行改進(jìn)。針對(duì)標(biāo)準(zhǔn)蟻群算法的資源調(diào)度過程中，總伴隨著</p><p>　　資源節(jié)點(diǎn)負(fù)載不均衡以及資源利用率不高的問題，本文創(chuàng)新性地設(shè)計(jì)了劣化因</p><p>　　子的預(yù)處理機(jī)制，并提出了一種基于改進(jìn)蟻群算法的資源調(diào)

15、度策略。</p><p>　　本文設(shè)計(jì)了一種動(dòng)態(tài)的、折中的方法來求解劣化因子的取值范圍，主要考</p><p>　　慮到兩方面：第一，云環(huán)境下的資源調(diào)度具有動(dòng)態(tài)性的特點(diǎn)，即隨時(shí)會(huì)有新的</p><p>　　節(jié)點(diǎn)加入云中，也有某些節(jié)點(diǎn)由于某些原因選擇退出；第二，劣化因子的值不</p><p>　　能夠太大，也不能太小。所謂動(dòng)態(tài)，就是針對(duì)不同的調(diào)

16、度場(chǎng)景動(dòng)態(tài)地選取劣化</p><p>　　因子的取值范圍；所謂折中，就是首先設(shè)置中間值 0.5，然后在 0.5 附近交替地</p><p>　　設(shè)置較大值和較小值，以求得劣化因子的取值范圍。</p><p>　　本文借助 VC++6.0 平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，并利用 MATLAB 對(duì)仿真數(shù)據(jù)進(jìn)行</p><p>　　分析。仿真實(shí)驗(yàn)分成兩個(gè)步驟：第

17、一步是劣化因子的仿真；第二步是改進(jìn)算法</p><p>　　與標(biāo)準(zhǔn)蟻群算法的仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，在劣化因子的取值范圍內(nèi)，基于</p><p>　　改進(jìn)蟻群算法的資源調(diào)度策略具有更好的負(fù)載均衡度以及更好的資源利用率，</p><p>　　并且改進(jìn)的蟻群算法縮短了任務(wù)執(zhí)行的平均時(shí)間，且具有更強(qiáng)的全局搜索能力。</p><p>　　關(guān)鍵詞：云環(huán)

18、境，資源調(diào)度，蟻群算法，劣化因子</p><p><b>　　I</b></p><p><b>　　Abstract</b></p><p><b>　　Abstract</b></p><p>　　Cloud computing is an emerging computi

19、ng model developed with grid</p><p>　　computing, which combined the existing mature virtualization technology, virtualizing</p><p>　　various resources of network into a huge virtual resource poo

20、l, to perform different</p><p>　　tasks of different users by organizing virtual resources. Therefore, a reasonable</p><p>　　resource scheduling strategy will have a major impact on the performan

21、ce of the entire</p><p>　　cloud platform.</p><p>　　This paper studied a lot of scheduling algorithms in cloud computing environment,and ant colony algorithm has the characteristics of distribut

22、ion, heterogeneity and lowdemand for the initial conditions, which makes it very suitable for resource schedulingin cloud computing environment. However, the standard ant colony algorithm also hasshortcomings. If the

23、algorithm will apply to the actual cloud platform, we must improveit Due to the problems that it always accompanied that the load of res</p><p>　　This paper designs a dynamic, eclectic method in the process

24、 of solving the scopeof cracking factors, mainly considering two aspects: first, the cloud resource schedulinghas dynamic characteristics, i.e. there will be a new node into the cloud at any time, andsome nodes out fo

25、r some reason; Second, the value of degradation factors can't be toobig or too small So-called dynamic, is aimed at different scenarios to dynamically selectthe value range of degradation factors; So-called eclecti

26、c, i</p><p>　　firstly, then alternately set bigger and smaller values near 0.5 to ensure the valuerange of degradation factors.</p><p>　　In this paper, do the simulation experiment with the aid

27、 of VC + + 6.0 platform,and analysis the simulation datas through MATLAB. Simulation experiment is dividedinto two steps: the first step is degradation factors simulation; the second step is theimproved algorithm and

28、the standard ant colony algorithm simulation The experimentalresults show that within the scope of the value of degradation factor, the resource</p><p><b>　　II</b></p><p><b>　

29、　Abstract</b></p><p>　　scheduling strategy based on improved ant colony algorithm has better load balance and</p><p>　　better resource utilization, at the same time, improved ant colony al

30、gorithm shortens the</p><p>　　average time of task execution and has the stronger ability of global searching.</p><p>　　Keywords: Cloud environment, Resource scheduling, Ant colony algorithm, Cr

31、acking</p><p><b>　　factors</b></p><p><b>　　III</b></p><p><b>　　目錄</b></p><p><b>　　目錄</b></p><p>　　第一章 緒論 &#

32、183;····································

33、····································

34、3;·········1</p><p>　　本文的研究背景及意義 .................................................................................... 1</p><p>　　研究現(xiàn)狀 ...............

35、............................................................................................. 2</p><p>　　本文主要的研究工作 ........................................................................................ 3&l

36、t;/p><p>　　本文的組織結(jié)構(gòu) ................................................................................................ 4</p><p>　　第二章 相關(guān)理論 ··········&

37、#183;····································

38、;······························6</p><p>　　云計(jì)算的背景 ........

39、............................................................................................ 6</p><p>　　云環(huán)境下的資源調(diào)度的相關(guān)概念 .................................................................... 7</p><p&

40、gt;　　云計(jì)算資源調(diào)度的特點(diǎn) .................................................................................... 8</p><p>　　云環(huán)境下資源調(diào)度策略的評(píng)判指標(biāo) ................................................................ 9</p>&

41、lt;p>　　本章小結(jié) .......................................................................................................... 10</p><p>　　第三章 云環(huán)境下常用的資源調(diào)度算法研究·········

42、································· 11</p><p&g

43、t;　　傳統(tǒng)的調(diào)度算法研究 ...................................................................................... 11</p><p>　　Min-Min 算法和 Max-Min 算法············

44、································· 11</p><p&g

45、t;　　投機(jī)負(fù)載均衡算法 ··································

46、83;························· 13</p><p>　　Sufferage 算法 ····

47、3;····································&#

48、183;························ 13</p><p>　　輪循調(diào)度算法 ······

49、83;····································&

50、#183;······················ 14</p><p>　　傳統(tǒng)調(diào)度算法的比較 ········

51、;····································

52、83;············ 14</p><p>　　啟發(fā)式調(diào)度算法的研究 .................................................................................. 15</p><p>　　

53、遺傳算法 ····································

54、;···································· 15

55、 3.2.2 粒子群算法 ··································&#

56、183;·································· 17 3.2.3 模

57、擬退火算法 ···································

58、3;······························ 17 3.2.4 蟻群算法 ···

59、3;····································&#

60、183;······························· 19 3.2.5 啟發(fā)式調(diào)度算法的比較 ·&#

61、183;····································

62、················ 19</p><p>　　資源調(diào)度算法的局限性及其改進(jìn)途徑 .......................................................... 19</p><p>

63、;　　典型的資源調(diào)度模型 MAP/REDUCE ............................................................... 21</p><p><b>　　IV</b></p><p><b>　　目錄</b></p><p>　　本章小結(jié) ..............

64、............................................................................................ 22第四章 基于劣化因子蟻群算法的資源調(diào)度策略·················&

65、#183;·················· 23</p><p>　　基于蟻群算法的 TSP 數(shù)學(xué)模型.................................................................

66、..... 23 4.1.1 蟻群算法的原理 ································

67、3;······························ 23 4.1.2 蟻群算法的特點(diǎn) ···&

68、#183;····································

69、;······················· 25 4.1.3 TSP 數(shù)學(xué)模型··········&#

70、183;····································

71、···················· 25</p><p>　　基于改進(jìn)蟻群算法的資源調(diào)度策略的設(shè)計(jì) .................................................. 30

72、4.2.1 設(shè)計(jì)劣化因子的預(yù)處理機(jī)制 ·································

73、83;·············· 31 4.2.1.1 劣化因子的引入 ··················

74、3;····································&#

75、183;·· 31 4.2.1.2 可行性分析 ·······························

76、;································· 31 4.2.1.3 劣化因子的選取

77、····································

78、3;····················· 32 4.2.2 設(shè)計(jì)基于劣化因子蟻群算法的資源調(diào)度策略的基本步驟·········

79、83;·· 34</p><p>　　本章小結(jié) .......................................................................................................... 37第五章 實(shí)驗(yàn)仿真與數(shù)據(jù)分析········

80、83;····································&

81、#183;·············· 38</p><p>　　實(shí)驗(yàn)環(huán)境 ....................................................................................................

82、...... 38</p><p>　　仿真實(shí)驗(yàn)的說明 .............................................................................................. 38</p><p>　　劣化因子的仿真實(shí)驗(yàn) ..................................................

83、.................................... 39</p><p>　　改進(jìn)算法與標(biāo)準(zhǔn)算法的仿真實(shí)驗(yàn) .................................................................. 44 5.4.1 實(shí)驗(yàn)第一階段 ··········

84、;····································

85、83;··················· 45 5.4.2 實(shí)驗(yàn)第二階段 ··············&

86、#183;····································

87、;··············· 48</p><p>　　本章小結(jié) ..................................................................................................

88、........ 53第六章 總結(jié)與展望·································&

89、#183;····································

90、;·· 54</p><p>　　總結(jié) .................................................................................................................. 54</p><p>　　展望 ...................................

91、............................................................................... 54致謝······················

92、83;····································&

93、#183;······························· 56參考文獻(xiàn)···

94、83;····································&

95、#183;····································

96、;········ 57攻碩期間的研究成果··························&#

97、183;····································

98、······· 61</p><p><b>　　V</b></p><p><b>　　縮略語對(duì)照表</b></p><p><b>　　縮略語對(duì)照表</b></p><p>　　縮略語 英文全稱 中文釋義

99、</p><p>　　ACA Ant Colony Algorithm 蟻群算法</p><p>　　API Application Programming Interface 應(yīng)用程序接口</p><p>　　GA Genetic Algorithm 遺傳算法</p><p>　　GAE Google App Engine 谷歌應(yīng)用程序引擎

100、</p><p>　　GCP Graph Coloring Problem 圖形著色問題</p><p>　　GFS Global File System 全局文件系統(tǒng)</p><p>　　HaaS Hardware as a Service 硬件即服務(wù)</p><p>　　HDF Hadoop Distributed File System

101、 Hadoop 文件系統(tǒng)</p><p>　　HTTP Hyper Text Transfer Protocol 超文本傳輸協(xié)議</p><p>　　HTTPS Hyper Text Transfer Protocol Secure 安全超文本傳輸協(xié)議</p><p>　　IaaS Infrastructure as a Service 基礎(chǔ)設(shè)施即服務(wù)</p&

102、gt;<p>　　IEEE Institute of Electrical and Electronic Engineers 電氣與電子工程協(xié)會(huì)</p><p>　　IIS Internet Information Server 互聯(lián)網(wǎng)信息服務(wù)</p><p>　　IT Information Technology 信息技術(shù)</p><p>　　JSS

103、P Job Shopping Scheduling Problem 作業(yè)車間調(diào)度問題</p><p>　　Min-Min Minimum-Minimum completion time 最小最小算法</p><p>　　OLB Opportunistic Load Balancing 投機(jī)的負(fù)載平衡</p><p>　　OS Operating System 操作系

104、統(tǒng)</p><p>　　PaaS Platform as a Service 平臺(tái)即服務(wù)</p><p>　　PC Personal Computer 個(gè)人電腦 PDA Personal Digital Assistant 個(gè)人數(shù)字處理PSO Particle Swarm Optimization 粒子群優(yōu)化算法QoS Quality of Service 服務(wù)質(zhì)量RR Round

105、Robin 輪循算法 SA Simulate Annealing 模擬退火</p><p><b>　　VI</b></p><p><b>　　縮略語對(duì)照表</b></p><p>　　SaaS Software as a Service 軟件即服務(wù)</p><p>　　SLA Service-l

106、evel Agreement 服務(wù)等級(jí)協(xié)議</p><p>　　SQL Structured Query Language 結(jié)構(gòu)查詢語言</p><p>　　TSP Traveling Salesman Problem 旅行商問題</p><p>　　VRP Vehicle Routing Problem 車輛路徑問題</p><p><

107、;b>　　VII</b></p><p><b>　　第一章 緒論</b></p><p><b>　　第一章 緒論</b></p><p>　　云計(jì)算的系統(tǒng)性能和服務(wù)質(zhì)量與資源調(diào)度策略的好壞有很大關(guān)系。近幾年，</p><p>　　很多云計(jì)算的專家對(duì)資源的調(diào)度問題進(jìn)行了深入的研究

108、，同時(shí)提出了各類調(diào)度</p><p>　　策略，這使得云計(jì)算能夠不斷地發(fā)展和完善。</p><p>　　本文的研究背景及意義</p><p>　　隨著信息產(chǎn)業(yè)的高速發(fā)展，計(jì)算機(jī)迅速地深入到人們的生活、工作、學(xué)習(xí)</p><p>　　等各方面，雖然計(jì)算機(jī)不斷地更新?lián)Q代，但是傳統(tǒng)的計(jì)算模式已經(jīng)無法滿足人</p><p>　

109、　們對(duì)計(jì)算機(jī)能力的需求。網(wǎng)格計(jì)算的出現(xiàn)緩解了這種危機(jī)，但是由于其發(fā)展遇</p><p>　　到了很多問題，還是未能實(shí)現(xiàn)大規(guī)模的商業(yè)化。</p><p>　　因此，更先進(jìn)的云計(jì)算出現(xiàn)了。云計(jì)算是一種通過互聯(lián)網(wǎng)技術(shù)，把地域上</p><p>　　分布異構(gòu)的計(jì)算機(jī)、存儲(chǔ)系統(tǒng)、終端設(shè)備等各種資源組織起來，并實(shí)現(xiàn)資源共</p><p>　　享的高性能計(jì)

110、算，作為網(wǎng)格計(jì)算的商業(yè)化實(shí)現(xiàn)[1]，云計(jì)算蘊(yùn)藏著巨大的商業(yè)價(jià)值，</p><p>　　通過網(wǎng)絡(luò)將眾多資源配置較低的計(jì)算機(jī)資源整合成一個(gè)擁有超強(qiáng)能力的云計(jì)算</p><p>　　平臺(tái)，并利用平臺(tái)的三層服務(wù)模式把這種超強(qiáng)的能力傳遞給用戶終端。云計(jì)算</p><p>　　的核心理念就是提供高可靠性、高可用性、靈活的、彈性的服務(wù)，而實(shí)現(xiàn)這種</p><p

111、>　　理念最關(guān)鍵的技術(shù)就是資源調(diào)度技術(shù)。</p><p>　　目前，運(yùn)用于資源調(diào)度技術(shù)的算法有許多，比如：Max-Min 算法、Min-Min</p><p>　　算法、輪循算法、遺傳算法、蟻群算法等等。論文選取蟻群算法作為資源調(diào)度</p><p>　　的輔助算法，主要考慮到以下三個(gè)方面：首先，蟻群算法具有很強(qiáng)的分布性和</p><p>

112、;　　并行性；其次，蟻群算法采用了正反饋機(jī)制，加快了進(jìn)化的過程；最后，蟻群</p><p>　　算法具備較好的魯棒性，對(duì)初始路徑要求不高，并且在運(yùn)行過程當(dāng)中不需要人</p><p>　　工的干預(yù)。因此，蟻群算法非常適合于復(fù)雜云環(huán)境下的資源調(diào)度。</p><p>　　然而，蟻群算法也存在不足之處：算法容易收斂于局部最優(yōu)解而導(dǎo)致搜索</p><p&g

113、t;　　過早停滯；搜索時(shí)間過長(zhǎng)，中間變量不斷在局部最優(yōu)解與全局最優(yōu)解間反復(fù)。</p><p>　　如果將算法應(yīng)用到實(shí)際的云計(jì)算平臺(tái)中，必須對(duì)其進(jìn)行改進(jìn)。目前，對(duì)蟻群算</p><p>　　法進(jìn)行改進(jìn)的途徑不外乎兩種：第一種是，在蟻群算法的基礎(chǔ)上加入信任機(jī)制、</p><p>　　QoS、優(yōu)先級(jí)等約束條件，克服蟻群算法本身的一些缺陷；第二種是，將蟻群算</p&g

114、t;<p>　　法與其它的基礎(chǔ)調(diào)度算法相融合，用其它算法的優(yōu)勢(shì)去彌補(bǔ)蟻群算法的不足。</p><p><b>　　1</b></p><p>　　電子科技大學(xué)碩士學(xué)位論文</p><p>　　本文在標(biāo)準(zhǔn)蟻群算法的基礎(chǔ)上，創(chuàng)新性地設(shè)計(jì)了劣化因子的預(yù)處理機(jī)制，顯然</p><p>　　采用的是第一種改進(jìn)途徑。&

115、lt;/p><p>　　判定云環(huán)境下資源調(diào)度策略好壞的評(píng)論指標(biāo)主要有負(fù)載均衡、最優(yōu)跨度、</p><p>　　經(jīng)濟(jì)原則、用戶的服務(wù)質(zhì)量 QoS 等。現(xiàn)有的資源調(diào)度技術(shù)無法滿足所有的評(píng)判</p><p>　　指標(biāo)，研究者們?cè)谠O(shè)計(jì)資源調(diào)度策略時(shí)，往往只需考慮各自的設(shè)計(jì)宗旨。本文</p><p>　　提出的基于改進(jìn)蟻群算法的資源調(diào)度策略，旨在改善資源調(diào)

116、度過程中資源節(jié)點(diǎn)</p><p>　　的負(fù)載均衡度及資源利用率。</p><p><b>　　研究現(xiàn)狀</b></p><p>　　亞馬遜、谷歌、IBM、微軟和其它大型公司是云計(jì)算的先驅(qū)者，為推動(dòng)云</p><p>　　計(jì)算的發(fā)展發(fā)揮著無比重要的作用。由于各自應(yīng)用的范疇和發(fā)展的目標(biāo)有所不</p><p

117、>　　同，這些公司對(duì)云計(jì)算的定義也各不相同，但是都存在著如何充分利用資源的</p><p>　　問題。關(guān)于云計(jì)算環(huán)境下的資源調(diào)度，一種是不考慮任務(wù)之間及節(jié)點(diǎn)之間的關(guān)</p><p>　　系，且調(diào)度的效果是可以預(yù)測(cè)的靜態(tài)調(diào)度；另一種是充分考慮任務(wù)之間和節(jié)點(diǎn)</p><p>　　之間的關(guān)系，且調(diào)度效果是動(dòng)態(tài)變化的不可預(yù)知的動(dòng)態(tài)調(diào)度。前者易于實(shí)現(xiàn)，</p>

118、;<p>　　但調(diào)度的效果不佳；后者實(shí)現(xiàn)起來比較復(fù)雜，但是調(diào)度更合理、效果更明顯。</p><p>　　由于云計(jì)算資源調(diào)度的動(dòng)態(tài)性質(zhì)，現(xiàn)階段普遍采用動(dòng)態(tài)調(diào)度的方式。不管進(jìn)行</p><p>　　哪種類型的資源調(diào)度，最終的目的都是為了合理有效地利用云計(jì)算資源。</p><p>　　從現(xiàn)有的云計(jì)算資源調(diào)度技術(shù)來看，大部分資源調(diào)度策略都有各自的側(cè)重</

119、p><p>　　點(diǎn)。其中，Xin Lu 和 Zilong Gu[3]提出了一種自適應(yīng)負(fù)載的云資源調(diào)度模式，該</p><p>　　模式為每一個(gè)服務(wù)器集群配置一個(gè)集群控制器，實(shí)時(shí)監(jiān)測(cè)資源節(jié)點(diǎn)虛擬機(jī)的性</p><p>　　能參數(shù)是否超過預(yù)先規(guī)定的閾值，當(dāng)超過臨界值時(shí)，基于蟻群算法快速收斂的</p><p>　　優(yōu)點(diǎn)找出鄰近閑置的節(jié)點(diǎn)，并承擔(dān)一部分的

120、負(fù)載，仿真實(shí)驗(yàn)表明該模式滿足云</p><p>　　資源調(diào)度中負(fù)載不斷變化的要求，并且在一定程度上改善了資源的利用率。</p><p>　　Jianhua Gu 等人[4]提出了一種基于遺傳算法的資源調(diào)度策略，考慮到歷史數(shù)據(jù)和</p><p>　　當(dāng)前系統(tǒng)的狀態(tài)，提前估算該計(jì)算節(jié)點(diǎn)所需要的虛擬機(jī)資源對(duì)系統(tǒng)產(chǎn)生的影響，</p><p>　　選擇

121、一種影響最小的方式，從而解決了傳統(tǒng)算法調(diào)度帶來的負(fù)載不均衡和高遷</p><p>　　移成本的問題，很好地實(shí)現(xiàn)了負(fù)載均衡和合理的資源利用率。Zhengqiu Yang 等</p><p>　　人[5]提出了一種基于粒子群算法的蟻群優(yōu)化算法，更快更合理地分配資源，保證</p><p>　　了用戶任務(wù)盡快完成，并且遵守了用戶與商家簽訂的 SLA 協(xié)議。史欽，袁平鵬<

122、;/p><p>　　[6]提出了基于蟻群算法的網(wǎng)格任務(wù)調(diào)度算法，利用信息素來反映節(jié)點(diǎn)的處理能力，</p><p>　　并通過信息素?fù)]發(fā)和賞罰機(jī)制來淘汰劣質(zhì)解，從而得到優(yōu)良的資源節(jié)點(diǎn)。劉萬</p><p><b>　　2</b></p><p><b>　　第一章 緒論</b></p>&l

123、t;p>　　軍等人[7]對(duì)粒子群算法進(jìn)行改進(jìn)，同時(shí)結(jié)合連續(xù)雙向拍賣機(jī)制，提出了一種云環(huán)</p><p>　　境下的資源調(diào)度策略，借助 CLOUDSIM 平臺(tái)進(jìn)行仿真，結(jié)果證明了該調(diào)度策略</p><p>　　的 有 效 性 并 且 能 夠 有 效 地 改 善 資 源 節(jié) 點(diǎn) 的 執(zhí) 行 效 率 。 劉 永 等 人 [8] 結(jié) 合</p><p>　　Map/R

124、educe 編程模型，提出一種基于蟻群算法的資源調(diào)度策略，并利用最小化</p><p>　　遷移策略實(shí)時(shí)動(dòng)態(tài)地遷移資源節(jié)點(diǎn)，從而保證了用戶的服務(wù)需求且達(dá)到了節(jié)能</p><p>　　的目的。胡睿[9]為云計(jì)算提供商研究出一種利潤(rùn)驅(qū)動(dòng)的資源調(diào)度策略，能夠保證</p><p>　　用戶在遵守服務(wù)等級(jí)協(xié)定的前提下，達(dá)到降低虛擬資源租賃費(fèi)用的目的。四川</p>

125、<p>　　大學(xué)的李建鋒[10]在深入研究谷歌公司的 Map/Reduce 編程框架的基礎(chǔ)之上，提出</p><p>　　了一種基于改進(jìn)遺傳算法的資源調(diào)度策略，該策略增加了一個(gè)適應(yīng)度函數(shù)來進(jìn)</p><p>　　行種群的選擇，實(shí)驗(yàn)證明改調(diào)度策略提高了任務(wù)的執(zhí)行效率。新疆大學(xué)的呂良</p><p>　　干[11]深入研究了云環(huán)境下的資源調(diào)度過程，提出了一種

126、改善資源節(jié)點(diǎn)負(fù)載的調(diào)</p><p>　　度算法，結(jié)果表明該算法達(dá)到了較高的資源負(fù)載均衡度的目的，同時(shí)也減少了</p><p>　　任務(wù)的執(zhí)行時(shí)間，滿足了用戶的需求。浙江師范大學(xué)的王梅[12]針對(duì)目前云計(jì)算</p><p>　　平臺(tái)中能源消耗的嚴(yán)重性，深入地剖析了云計(jì)算的虛擬機(jī)遷移技術(shù)，提出了一</p><p>　　種以負(fù)載均衡和減少網(wǎng)絡(luò)傳輸

127、消耗為目的的虛擬機(jī)遷移策略，仿真實(shí)現(xiàn)表明該</p><p>　　策略不僅能提高資源的利用率，同時(shí)能有效地解決數(shù)據(jù)中心能耗的問題，具有</p><p>　　很高的應(yīng)用價(jià)值。武漢紡織大學(xué)的宋坤芳[13]提出了一種云環(huán)境下基于蟻群優(yōu)化</p><p>　　算法的資源調(diào)度策略，利用螞蟻之間相互協(xié)調(diào)的行為機(jī)制尋找云環(huán)境中的優(yōu)質(zhì)</p><p>　　資源

128、節(jié)點(diǎn)，結(jié)果證明，該算法與一般的調(diào)度算法相比，具有更高效的調(diào)度性能</p><p>　　和更好的負(fù)載均衡。Linan Zhu 等人[43]詳細(xì)地分析和設(shè)計(jì)了云環(huán)境下資源調(diào)度的</p><p>　　具體實(shí)現(xiàn)，借助 CLOUDSIM 模擬器進(jìn)行仿真，實(shí)驗(yàn)表明，在資源節(jié)點(diǎn)的分配和</p><p>　　負(fù)載平衡方面，蟻群算法比傳統(tǒng)算法具有更好的性能。</p>&

129、lt;p><b>　　本文主要的研究工作</b></p><p>　　本文深入分析了云環(huán)境下基于蟻群算法的資源調(diào)度問題，結(jié)合劣化因子的</p><p>　　預(yù)處理機(jī)制，設(shè)計(jì)了一種云環(huán)境下的資源調(diào)度策略，并借助 VC++6.0 平臺(tái)進(jìn)行</p><p>　　仿真實(shí)驗(yàn)，具體的工作分為以下三個(gè)方面：</p><p>　　

130、(1) 深入研究了云計(jì)算環(huán)境下的資源調(diào)度問題，并分析了云環(huán)境下資源調(diào)度的相</p><p>　　關(guān)概念、特點(diǎn)及調(diào)度策略的評(píng)判指標(biāo)；系統(tǒng)地研究了云計(jì)算環(huán)境下常用的資</p><p>　　源調(diào)度算法，并分析了這些資源調(diào)度算法的優(yōu)缺點(diǎn)，提出了改進(jìn)調(diào)度算法的</p><p>　　兩種途徑，分析了 Map/Reduce 調(diào)度的巧妙之處。</p><p>

131、;<b>　　3</b></p><p>　　電子科技大學(xué)碩士學(xué)位論文</p><p>　　(2) 針對(duì)標(biāo)準(zhǔn)蟻群算法的資源調(diào)度過程中資源負(fù)載不均衡以及資源利用率不高的</p><p>　　問題，設(shè)計(jì)了劣化因子的預(yù)處理機(jī)制，并提出了一種基于劣化因子蟻群算法</p><p><b>　　的資源調(diào)度策略。</b

132、></p><p>　　(3) 借助 VC++6.0 的仿真平臺(tái)，進(jìn)行了兩方面的仿真實(shí)驗(yàn)。一方面是劣化因子的</p><p>　　仿真實(shí)驗(yàn)；另一方面是兩種資源調(diào)度策略的仿真實(shí)驗(yàn)。同時(shí)對(duì)實(shí)驗(yàn)的數(shù)據(jù)進(jìn)</p><p><b>　　行詳細(xì)分析。</b></p><p>　　論文的創(chuàng)新工作主要有兩點(diǎn)：第一，針對(duì)基于標(biāo)準(zhǔn)蟻群

133、算法的資源調(diào)度過</p><p>　　程中，總伴隨著資源節(jié)點(diǎn)的負(fù)載不均衡以及資源利用率不高的問題，創(chuàng)新性地</p><p>　　設(shè)計(jì)了劣化因子的預(yù)處理機(jī)制，提出了一種基于改進(jìn)蟻群算法的資源調(diào)度策略；</p><p>　　第二，考慮到云環(huán)境下的資源調(diào)度具有動(dòng)態(tài)性的特點(diǎn)以及劣化因子值不能太大</p><p>　　或太小的實(shí)際情況，設(shè)計(jì)了一種動(dòng)態(tài)的

134、、折中的方法來求解劣化因子的取值范</p><p><b>　　圍。</b></p><p><b>　　本文的組織結(jié)構(gòu)</b></p><p>　　本文具體的章節(jié)安排情況如下：</p><p>　　第一章為緒論部分。深入研究了云計(jì)算的相關(guān)概念，闡述了將蟻群算法作</p><p&

135、gt;　　為輔助算法的原因及論文研究的意義，分析了云計(jì)算資源調(diào)度的相關(guān)文獻(xiàn)，最</p><p>　　后提出了論文的主要研究工作。</p><p>　　第二章為云環(huán)境下資源調(diào)度的相關(guān)理論。指出了云計(jì)算環(huán)境下資源調(diào)度問</p><p>　　題在云計(jì)算平臺(tái)中的重要性，分析了資源調(diào)度的相關(guān)概念、特點(diǎn)及其評(píng)判指標(biāo)。</p><p>　　第三章是云環(huán)境下

136、常用的資源調(diào)度算法的研究。系統(tǒng)地研究了云計(jì)算環(huán)境</p><p>　　下常用的資源調(diào)度算法，分析了這些資源調(diào)度算法的優(yōu)缺點(diǎn)，提出了改進(jìn)調(diào)度</p><p>　　算法的兩種途徑，并分析了 Map/Reduce 調(diào)度的巧妙之處。</p><p>　　第四章是基于改進(jìn)蟻群算法的資源調(diào)度策略的設(shè)計(jì)，是論文的核心部分。</p><p>　　首先進(jìn)一步研

137、究了蟻群算法的相關(guān)概念，分析了利用蟻群算法求解 TSP 問題的</p><p>　　數(shù)學(xué)模型，然后通過類比的方式構(gòu)建出利用劣化因子蟻群算法求解資源調(diào)度問</p><p>　　題的數(shù)學(xué)模型，針對(duì)標(biāo)準(zhǔn)蟻群算法容易陷入局部最優(yōu)的不足，設(shè)計(jì)了劣化因子</p><p>　　的預(yù)處理機(jī)制，詳細(xì)地分析了劣化因子的可行性，并采用一種動(dòng)態(tài)的、折中的</p><p&

138、gt;　　方式求解劣化因子的取值范圍，最后利用求解到的數(shù)學(xué)模型，同時(shí)結(jié)合劣化因</p><p>　　子的預(yù)處理機(jī)制，提出了一種基于劣化因子蟻群算法的資源調(diào)度策略，并給出</p><p>　　了具體的步驟及對(duì)應(yīng)的流程圖。</p><p><b>　　4</b></p><p><b>　　第一章 緒論</b

139、></p><p>　　第五章為論文的仿真實(shí)驗(yàn)與數(shù)據(jù)分析。借助 VC++6.0 來模擬云環(huán)境下資源</p><p>　　的調(diào)度過程，并利用 MATLAB 對(duì)模擬得出的數(shù)據(jù)進(jìn)行分析。仿真實(shí)驗(yàn)分成兩個(gè)</p><p>　　步驟：第一步是劣化因子的仿真實(shí)驗(yàn)；第二步是改進(jìn)算法與標(biāo)準(zhǔn)蟻群算法的仿</p><p>　　真實(shí)驗(yàn)，后者又分成兩個(gè)實(shí)驗(yàn)階段

140、。仿真結(jié)果表明，有劣化因子的資源調(diào)度策</p><p>　　略具有更好的負(fù)載均衡度以及更好的資源利用率，同時(shí)改進(jìn)的蟻群算法縮短了</p><p>　　任務(wù)執(zhí)行的平均時(shí)間，具有更強(qiáng)的全局搜索能力。</p><p>　　第六章是本文結(jié)束語部分。總結(jié)全文，并提出論文有待改進(jìn)的地方和下一</p><p><b>　　步的研究工作。</

141、b></p><p><b>　　5</b></p><p>　　電子科技大學(xué)碩士學(xué)位論文</p><p><b>　　第二章 相關(guān)理論</b></p><p><b>　　云計(jì)算的背景</b></p><p>　　云計(jì)算的概念最先是由谷歌的 CE

142、O Eric Schmidt 提出來的，作為互聯(lián)網(wǎng)產(chǎn)</p><p>　　業(yè)的一大革新，云計(jì)算模式自從提出以后，業(yè)界各大企業(yè)和科研機(jī)構(gòu)紛紛投入</p><p>　　研究，并搭建屬于自己的云計(jì)算平臺(tái)。因?yàn)楦髯匝芯康念I(lǐng)域和發(fā)展的目標(biāo)有所</p><p>　　不同，所以對(duì)云計(jì)算的定義呈現(xiàn)出百家齊放的局面，但是它們的核心思想都在</p><p>　　

143、于：云計(jì)算通過互聯(lián)網(wǎng)將各種 IT 資源整合成一個(gè)規(guī)模巨大的虛擬資源池，并屏</p><p>　　蔽底層的細(xì)節(jié)；云計(jì)算用戶只需一個(gè)簡(jiǎn)單的云計(jì)算終端設(shè)備(比如：PC、PDA、</p><p>　　平板電腦、智能手機(jī)等)就可以輕松地訪問云服務(wù)，并對(duì)資源的使用情況收取一</p><p>　　定的費(fèi)用，因此節(jié)約了大量的社會(huì)資源。云計(jì)算平臺(tái)里的虛擬資源池如圖 2-1 所<

144、/p><p><b>　　示。</b></p><p>　　圖 2-1 云計(jì)算的虛擬資源池[8]</p><p>　　如圖 2-2 所示，云計(jì)算的核心服務(wù)通常分為三個(gè)子層：</p><p>　　(1) 基礎(chǔ)設(shè)施即服務(wù)(IaaS)。處于服務(wù)結(jié)構(gòu)的最底層，向用戶提供一種基礎(chǔ)服務(wù)，</p><p>　　比如

145、計(jì)算機(jī)內(nèi)存、磁盤、輸入輸出設(shè)備、網(wǎng)絡(luò)等硬件資源，因此有時(shí)又被稱</p><p>　　為硬件即服務(wù)(HaaS)。目前流行的 IaaS 提供商包括：亞馬遜的 EC2[15]、</p><p>　　Rackspace Cloud、Storage 等。</p><p>　　(2) 平臺(tái)即服務(wù)(PaaS)。處于基礎(chǔ)設(shè)施即服務(wù)和軟件即服務(wù)之間，向用戶提供應(yīng)</p>

146、<p>　　用程序的部署與管理服務(wù)。目前流行的 PaaS 提供商包括： Google App</p><p>　　Engine[16]、VMware、Cloud Foundry 以及 800APP 等。</p><p><b>　　6</b></p><p><b>　　第二章 相關(guān)理論</b></p&g

147、t;<p>　　(3) 軟件即服務(wù)(SaaS)。處于服務(wù)結(jié)構(gòu)的最頂層，向用戶提供一種應(yīng)用軟件服務(wù)。</p><p>　　這種模式的軟件不同于傳統(tǒng)的軟件，用戶使用起來更靈活方便。Salesforce</p><p>　　是提供 SaaS 應(yīng)用服務(wù)的最有名的公司，此外還有 IBM Lotus Live、Google</p><p>　　在線文件處理服務(wù)、C

148、isco 公司的 WebEx、Zoho 在線辦公服務(wù) 等。</p><p><b>　　SaaS</b></p><p><b>　　PaaS</b></p><p><b>　　IaaS</b></p><p>　　圖 2-2 云計(jì)算的服務(wù)層次模型</p>&l

149、t;p>　　盡管三個(gè)層次應(yīng)用服務(wù)的側(cè)重點(diǎn)各不相同，但是從技術(shù)的角度而言，在解</p><p>　　決資源調(diào)度的問題上，都希望能夠充分利用互聯(lián)網(wǎng)資源，達(dá)到最優(yōu)調(diào)度的目的。</p><p>　　比如，紐約時(shí)報(bào)曾經(jīng)利用成百上千臺(tái)亞馬遜 EC2 實(shí)例，在經(jīng)過不到兩天的時(shí)間，</p><p>　　完成了 TB 級(jí)文檔數(shù)據(jù)的處理，因此， EC2 服務(wù)器必須采取合理的資源調(diào)

150、度策</p><p>　　略來保障虛擬機(jī)的充分利用，否則處理完這些數(shù)據(jù)將要花費(fèi)數(shù)天甚至數(shù)月的時(shí)</p><p>　　間。又如 GAE 允許用戶在其基礎(chǔ)設(shè)施上直接部署和運(yùn)行自己開發(fā)的程序，免去</p><p>　　了用戶對(duì)服務(wù)器運(yùn)維的開銷。</p><p>　　云環(huán)境下的資源調(diào)度的相關(guān)概念</p><p>　　云計(jì)算是由

151、網(wǎng)格計(jì)算發(fā)展而來的，因此，云環(huán)境下的資源調(diào)度借鑒了網(wǎng)格</p><p>　　環(huán)境下的資源調(diào)度，但是它也有自身質(zhì)的飛躍，比如采用了成熟的虛擬機(jī)技術(shù)，</p><p>　　將互聯(lián)網(wǎng)上的各種 IT 資源組織成一個(gè)巨型的虛擬資源池，用戶不必將任務(wù)提交</p><p>　　到某個(gè)具體的物理節(jié)點(diǎn)上執(zhí)行，而是通過虛擬資源池的統(tǒng)一調(diào)度，將所需的虛</p><p&

152、gt;　　擬機(jī)資源通過封閉的服務(wù)包形式分配給用戶。如此以來，用戶根本不用關(guān)心底</p><p>　　層的細(xì)節(jié)，使用也更方便。</p><p><b>　　7</b></p><p>　　電子科技大學(xué)碩士學(xué)位論文</p><p>　　云計(jì)算環(huán)境下的資源調(diào)度就是利用分布式計(jì)算的原理將一個(gè)較大的用戶任</p>&

153、lt;p>　　務(wù)劃分成若干個(gè)粒度較小的子任務(wù)，然后通過一定的資源調(diào)度策略將所有的子</p><p>　　任務(wù)映射到最佳的虛擬機(jī)資源節(jié)點(diǎn)上執(zhí)行，最后將所有子任務(wù)的處理情況匯總，</p><p>　　反饋給用戶。具體的執(zhí)行過程如圖 2-3 所示。</p><p><b>　　用戶任務(wù)</b></p><p><b

154、>　　劃分</b></p><p>　　子任 子任 ? 子任</p><p>　　務(wù) 1 務(wù) 2 務(wù) n</p><p><b>　　子任務(wù)生成模塊</b></p><p><b>　　任務(wù)-資源匹配</b></p><p><b>　　資源調(diào)度策

155、略</b></p><p><b>　　調(diào)度模塊</b></p><p><b>　　子任務(wù)映射</b></p><p><b>　　任務(wù)執(zhí)行</b></p><p><b>　　資源管理中心</b></p><p>　

156、　圖 2-3 云環(huán)境下資源調(diào)度的模型</p><p>　　云計(jì)算資源調(diào)度的特點(diǎn)</p><p>　　從前面的理論我們了解到，云計(jì)算通過互聯(lián)網(wǎng)技術(shù)將各種 IT 資源整合成一</p><p>　　個(gè)巨大的虛擬資源池，且云計(jì)算平臺(tái)的每個(gè)服務(wù)子層都面臨著資源的調(diào)度問題。</p><p>　　因此，在云計(jì)算的研究和應(yīng)用過程中，一個(gè)良好的資源調(diào)度策略直接

157、影響著云</p><p><b>　　8</b></p><p><b>　　第二章 相關(guān)理論</b></p><p>　　服務(wù)的資源的利用率、用戶的滿意程度、運(yùn)營的成本等方方面面。云計(jì)算環(huán)境</p><p>　　下的資源調(diào)度主要具有以下三個(gè)方面的特點(diǎn)：</p><p>　　

158、(1) 通用性。由于云計(jì)算平臺(tái)提供給用戶的虛擬機(jī)資源都是統(tǒng)一封裝好的，且這</p><p>　　些虛擬機(jī)的網(wǎng)絡(luò)帶寬、服務(wù)器配置、專業(yè)的技術(shù)支持和其它方面都是未知的，</p><p>　　他們可以相同，也可以存在差異，所以云環(huán)境下的資源調(diào)度在面向同構(gòu)和異</p><p>　　構(gòu)的云平臺(tái)時(shí)，必須具有更好的通用性。</p><p>　　(2) 動(dòng)態(tài)