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

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

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

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

4、t;</p><p><b>　　殷 洪 海</b></p><p><b>　　指導教師 彭云峰</b></p><p><b>　　教授</b></p><p><b>　　電子科技大學</b></p><p><b>

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

6、<p><b>　　評閱人</b></p><p>　　注 1：注明《國際十進分類法 UDC》的類號。</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>　　獨創(chuàng)性聲明</b></p><p>　　本人聲明所呈交的學位論文是本人在導師指導下進行的研究工</p>

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

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

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

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

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

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

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

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

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

18、境，資源調度，蟻群算法，劣化因子</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>　　本文的組織結構 ................................................................................................ 4</p><p>　　第二章 相關理論 ··········&

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

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

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

40、gt;　　云計算資源調度的特點 .................................................................................... 8</p><p>　　云環(huán)境下資源調度策略的評判指標 ................................................................ 9</p>&

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

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

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

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

45、t;　　投機負載均衡算法 ··································

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

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

48、183;························ 13</p><p>　　輪循調度算法 ······

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

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

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

52、83;············ 14</p><p>　　啟發(fā)式調度算法的研究 .................................................................................. 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ā)式調度算法的比較 ·&#

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

62、················ 19</p><p>　　資源調度算法的局限性及其改進途徑 .......................................................... 19</p><p>

63、;　　典型的資源調度模型 MAP/REDUCE ............................................................... 21</p><p><b>　　IV</b></p><p><b>　　目錄</b></p><p>　　本章小結 ..............

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

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

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

67、3;······························ 23 4.1.2 蟻群算法的特點 ···&

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

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

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

71、···················· 25</p><p>　　基于改進蟻群算法的資源調度策略的設計 .................................................. 30

72、4.2.1 設計劣化因子的預處理機制 ·································

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 設計基于劣化因子蟻群算法的資源調度策略的基本步驟·········

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

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

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

82、...... 38</p><p>　　仿真實驗的說明 .............................................................................................. 38</p><p>　　劣化因子的仿真實驗 ..................................................

83、.................................... 39</p><p>　　改進算法與標準算法的仿真實驗 .................................................................. 44 5.4.1 實驗第一階段 ··········

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

85、83;··················· 45 5.4.2 實驗第二階段 ··············&

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

87、;··············· 48</p><p>　　本章小結 ..................................................................................................

88、........ 53第六章 總結與展望·································&

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

90、;·· 54</p><p>　　總結 .................................................................................................................. 54</p><p>　　展望 ...................................

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

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

93、#183;······························· 56參考文獻···

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

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

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

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

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

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

100、</p><p>　　GCP Graph Coloring Problem 圖形著色問題</p><p>　　GFS Global File System 全局文件系統(tǒng)</p><p>　　HaaS Hardware as a Service 硬件即服務</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 基礎設施即服務</p&

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

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

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

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

106、evel Agreement 服務等級協(xié)議</p><p>　　SQL Structured Query Language 結構查詢語言</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>　　云計算的系統(tǒng)性能和服務質量與資源調度策略的好壞有很大關系。近幾年，</p><p>　　很多云計算的專家對資源的調度問題進行了深入的研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

131、;<b>　　3</b></p><p>　　電子科技大學碩士學位論文</p><p>　　(2) 針對標準蟻群算法的資源調度過程中資源負載不均衡以及資源利用率不高的</p><p>　　問題，設計了劣化因子的預處理機制，并提出了一種基于劣化因子蟻群算法</p><p><b>　　的資源調度策略。</b

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

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

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

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

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

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

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

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

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

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

142、O Eric Schmidt 提出來的，作為互聯(lián)網產</p><p>　　業(yè)的一大革新，云計算模式自從提出以后，業(yè)界各大企業(yè)和科研機構紛紛投入</p><p>　　研究，并搭建屬于自己的云計算平臺。因為各自研究的領域和發(fā)展的目標有所</p><p>　　不同，所以對云計算的定義呈現(xiàn)出百家齊放的局面，但是它們的核心思想都在</p><p>　　

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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