楊 戈 ，吳俊言

（1.北京師范大學珠海分校 智能多媒體技術(shù)重點實驗室，廣東 珠海 519087；2.北京大學深圳研究生院 深圳物聯(lián)網(wǎng)智能感知技術(shù)工程實驗室，廣東 深圳 518055）

0 引言

隨著計算機時代的發(fā)展，用戶的基數(shù)正在不斷擴大，而對應的在線視頻的量級也正逐步擴展，為解決點對點的在線視頻的服務器的速度和帶寬問題，以及大量的視頻資源帶來服務器計算負載問題，增加其負載而帶來了“云計算”[1]。

云計算分為3 層，分別是IaaS（基礎(chǔ)設(shè)施即服務）、Paas（平臺即服務）和SaaS（軟件即服務）[2]。儲存資源管理是計算機資源管理的一部分，側(cè)重于計算機的節(jié)點的高效性和節(jié)點的整體負載均衡。無論是一般的云計算，還是快速發(fā)展的移動云計算，云增效模式是最常見的云計算模式[3]。因而在云計算方面，最主要研究的是計算機資源、負載均衡的實現(xiàn)和任務調(diào)度的分配等方面。在任務調(diào)度方面，文獻[4]提出了一種面向多目標的兩階段任務調(diào)度算法，具有讓任務匹配最小時間資源的偏好，重調(diào)度階段，實現(xiàn)負載均衡；文獻[5]提出了針對P2P（對等網(wǎng)絡，即對等計算機網(wǎng)絡）結(jié)構(gòu)上的用數(shù)據(jù)副本來進行管理，從而提高數(shù)據(jù)訪問的效率和系統(tǒng)容錯功能。文獻[6]中提出了一種基于任務調(diào)度的模板策略，通過任務集合求出任務量模版，并依據(jù)模板對調(diào)度算法進行任務調(diào)度的TTS（基于模板的任務調(diào)度策略）策略。該算法從全局的角度計算出調(diào)度模板，有目標地實現(xiàn)了調(diào)度同時充分考慮了通信開銷。

而對于計算機資源管理方面，文獻[7]研究了虛擬云桌面上的動態(tài)調(diào)度應用，文獻[8]中提出了一種關(guān)于網(wǎng)絡感知的計算資源下的對虛擬機的放置算法。

本文在針對于云計算任務調(diào)度的基礎(chǔ)上提了一種貪心蟻群算法（Greedy And Ant Colony Algorithm，GAAC），它避免了貪心算法在任務數(shù)較大情況下的搜索能力不足及局部搜索能力低下，以及蟻群算法在初始階段的搜索能力低下的缺點，同時充分考慮了在全局情況下的云計算的流媒體任務調(diào)度。

1 云計算資源調(diào)度模型

云計算中的資源調(diào)度可通過以下的模型表示：

式中，fi（yi）表示效率函數(shù)。為了能夠達到云計算的資源調(diào)度的優(yōu)化要求，要求云計算資源調(diào)度所消耗資源的為最小值即mini

∑fi（yi），其花費、時間和能量三方面達到最小值。C（i，j）表示任務i在資源j的花費，E（i，j）表示任務i在資源j的能量消耗，T（i，j）表示任務i在資源j的時間消耗。

式中，yi表示完成任務i的所需要的資源總和其中表示的是任務i 和虛擬機j 之間的關(guān)系。本文主要從時間消耗最小上解決云計算的效率優(yōu)化問題。

2 GAAC 算法

GAAC 算法是在現(xiàn)今的任務調(diào)度貪心算法的后期融入了蟻群算法的特點。GAAC 算法同時具有貪心算法任務量較少時，負載均衡，能實現(xiàn)較好的局部優(yōu)化和蟻群算法任務量較多時具有的學習機制和迭代優(yōu)化的特點，即GAAC 算法同時具備了貪心算法和蟻群算法的原理特點。

2.1 GAAC 算法實現(xiàn)

對于其中的貪心算法，學者們對任務調(diào)度及貪心算法進行了大量的研究[9-12]。而在文獻[6]中，貪心法則為：按物品的價值大小排序，選擇剩下的容量最大的背包，裝最大件的物品，直到所有的背包都裝滿物品為止。將該方法類比到云計算的任務調(diào)度問題下，提出貪心算法下的任務調(diào)度優(yōu)化方法。

而對應于云計算調(diào)度，則是進行任務和虛擬機排序，按照虛擬機執(zhí)行任務的能力和速度按大到小進行排序，然后再按照任務的大小同時進行排序，檢索最大的任務在哪個虛擬機運行得最快，然后完成分配，再進行下一個任務的分配，依次類推直到任務分發(fā)完畢。

而GAAC 算法在任務量較大的后期則是具備仿生原理，它依據(jù)螞蟻群尋找食物的原則而模擬而成的一種最短路徑的智能算法[13]，而其具體步驟如下：

（1）初始化，首先設(shè)定相關(guān)參數(shù)；

（2）將m 個螞蟻隨機放在各個食物上，每個食物至多分布一個螞蟻，并將m 修改禁忌表Jk；

（3）所有螞蟻根據(jù)概率轉(zhuǎn)換公式和選擇下一食物，并將該元素（食物）移動到該螞蟻個體的禁忌表中；

（4）所有螞蟻遍歷完n 個食物后在所經(jīng)過的路徑上根據(jù)信息更新公式更新所有信息素，并記錄本次迭代過程重點最優(yōu)路徑和最優(yōu)路徑長度；

（5）清空禁忌列表Jk，重復步驟（3）和（4），直到每一個螞蟻都完成Nmax次遍歷所有食物，最后輸出的路徑為最優(yōu)路徑。

而對應在任務調(diào)度中則是將食物替換成云計算中的各個節(jié)點的虛擬機，而其螞蟻獲得的路徑則是對應任務分配給虛擬機的分法，而螞蟻獲得的路徑的長度，則為分配好后所花費的總時間。算法通過其中的學習機制，不斷迭代從而找到任務調(diào)度中的最短路徑，進而實現(xiàn)路徑的最優(yōu)化。

2.2 GAAC 算法流程

由于蟻群算法的受信息素引導，需要較多次數(shù)的學習和迭代，才能形成較好的優(yōu)化，對應在任務調(diào)度算法上則需要較多的任務量。而在起初階段，由于任務數(shù)（對應蟻群中的食物點）較少，正反饋的尚不健全，無法形成良好的學習機制，從而無法得到較優(yōu)解。相反，貪心算法由于不具備學習機制，在前期所耗時較少，但在后期任務數(shù)較大時，由于學習機制的缺失，優(yōu)化效果較差，而GAAC 算法正是將這兩種算法融合形成的新算法。

設(shè)貪心算法所完成的時間為tasktime（t）a，蟻群算法所完成的時間為tasktime（t）b。通過比較可以得出兩種算法在云任務的實現(xiàn)時間，則判斷tasktime（t）a=tasktime（t）b=γ所對應的任務數(shù)值，求得大約為：

（1）當tasktime（t）a

①將任務按由大到小的順序降序排列（MI），并將虛擬機按按小到大升序排列（MIPS），所消耗的時間為T，它們之間滿足公式：T=MI/MIPS。

②將最后一列對應的虛擬機分配給矩陣中行號為0的任務。

（2）tasktime（t）a>tasktime（t）b，此時即采用蟻群算法，其路徑概率的選擇和信息素更新選擇如下：

圖1 GAAC 算法流程圖

3 仿真實驗

本文運用了云計算的模擬平臺Cloudsim，通過Cloudsim實現(xiàn)云環(huán)境的模擬配置，達到異構(gòu)的云環(huán)境。

3.1 軟硬件

實驗使用的物理機和硬軟件配置如表1 所示。

表1 硬件及軟件配置

3.2 仿真結(jié)果

通過修改Datacenterbroker 類加入了自定義的多任務狀態(tài)的貪心算法和GAAC 算法，并在里面寫入了傳統(tǒng)的輪轉(zhuǎn)算法進行對比，進行仿真對比分析，仿真實驗參數(shù)如表2 所示。

表2 仿真實驗參數(shù)

圖2 顯示了異構(gòu)平臺下，虛擬機數(shù)為5 個時，任務個數(shù)由0 個增加到2 500 個時，GAAC 算法與貪心算法、輪轉(zhuǎn)算法和蟻群算法的任務集合完成時間的對比。由于輪轉(zhuǎn)算法的優(yōu)化效果較差，因此其耗時明顯較多于貪心算法和GAAC 算法。從圖中可看出在任務個數(shù)大于500時4 種算法的差異，貪心算法的用時和GAAC 算法重合，原因是在γ 小于1 000 時，GAAC 算法采用的是貪心算法的原理，但是GAAC 算法的用時明顯少于蟻群算法和輪轉(zhuǎn)算法。但隨著任務個數(shù)的增加，貪心算法和GAAC算法的用時明顯開始減少，而至任務數(shù)約為1 000 時，GAAC 算法的用時開始明顯比貪心算法少。其原因是γ大于1 000 時，GAAC 算法采用的是蟻群算法的原理，在迭代學習次數(shù)較大，訓練集較大，訓練時間較長的情況下進行，由于迭代學習的原因，此時的任務調(diào)度實現(xiàn)了更好的優(yōu)化，因此相對應的用時更少。而蟻群算法和GAAC 算法在約為1 000 個任務之后時間幾乎一致，但由于任務具有隨機性設(shè)置的原因，示例圖中的時間上仍有些許的不吻合。但GAAC 算法總體的任務調(diào)度時間少于貪心算法和輪轉(zhuǎn)算法，且在前期也優(yōu)于蟻群算法。即GAAC 從總體的任務優(yōu)化效果而言，相對優(yōu)于輪轉(zhuǎn)算法、貪心算法和蟻群算法。

圖2 任務調(diào)度算法對比1

針對表3 仿真實驗參數(shù)，圖3 顯示了異構(gòu)平臺下，虛擬機數(shù)為50 個，任務個數(shù)由0 個增加到2 500 個時，GAAC 算法與貪心算法、輪轉(zhuǎn)算法和蟻群算法的任務集合完成時間的對比。此時可以看出，γ 所對應的值約為800，在γ 小于800 時，GAAC 算法采用的是貪心算法的原理，相對于蟻群算法，其優(yōu)化效果大約為40%，而相對于輪轉(zhuǎn)算法其優(yōu)化效果大約為22%，這是由于GAAC算法前期采用的是現(xiàn)今的貪心算法，其在任務數(shù)較少時，能有較好的局部優(yōu)化效果，而蟻群由于迭代和學習機制尚未健全，因此其時間優(yōu)化相對較差于輪轉(zhuǎn)算法和貪心算法；而在γ 大于800 時，由于具有蟻群算法的學習和迭代機制的原因，GAAC 算法和蟻群算法接近吻合，但由于每次任務的隨機性，并沒有重合在一起。GAAC算法由于在現(xiàn)今的貪心算法中融入了采用了蟻群算法的原理，在γ 大于800 時，相對于現(xiàn)今的貪心算法優(yōu)化效果大概為33%?？梢钥闯鯣AAC 算法在總體上相對于貪心算法和輪轉(zhuǎn)算法的優(yōu)化效果更好。

圖3 任務調(diào)度算法對比2

表3 仿真實驗參數(shù)

針對表4 仿真實驗參數(shù)，圖4 所示為虛擬機個數(shù)為100 個時任務調(diào)度算法的對比，此時的γ 值約為900，在γ 小于900 時，GAAC 算法相對于輪轉(zhuǎn)算法其優(yōu)化效果大約為20%，對于蟻群算法其優(yōu)化效果大約為34%；而在γ 大于900 時，GAAC 算法相對于貪心算法，其優(yōu)化效果大約為25%。

圖4 任務調(diào)度算法對比3

表4 仿真實驗參數(shù)

隨著任務數(shù)的增大優(yōu)化的時間在不斷擴大，這是因為隨著算法學習與迭代次數(shù)的增大，其優(yōu)化結(jié)果越來越傾向于局部最優(yōu)。即是用GAAC 算法進行云計算任務調(diào)度時，考慮了以任務執(zhí)行時間為優(yōu)化目標，同時也考慮以負載均衡為優(yōu)化目標，從而通過局部最優(yōu)實現(xiàn)全局最優(yōu)而實現(xiàn)了任務調(diào)度的時間和負載的均衡，達到了云計算中的任務調(diào)度優(yōu)化的效果。

4 結(jié)論

優(yōu)化的任務調(diào)度算法能高效地提升云計算的性能，從而大大提升云計算的算力、用戶響應時間等[14]。本文是基于模擬的Cloudsim 云計算環(huán)境通過對現(xiàn)有的兩種較常用的云計算算法進行不同的任務時間數(shù)的比較，并將由于不同任務數(shù)這兩種算法所具有的不同優(yōu)點結(jié)合而形成了新的GAAC 算法，可以看出GAAC 算法實現(xiàn)了基本的時間優(yōu)化和初步的負載平衡，并解決了蟻群算法任務數(shù)較低、學習次數(shù)較低而導致的優(yōu)化效果較差和Greedy 算法后期由于沒有迭代機制而優(yōu)化效率較差的問題。但是GAAC 后期，由于學習機制和大量的訓練的原因會導致計算開銷大，并容易陷入局部優(yōu)化、過早收斂而非全局最優(yōu)化的結(jié)果。而現(xiàn)今對于云計算的任務調(diào)度算法有諸如ACO、遺傳、退火算法和兩種或多種算法之間的融合實現(xiàn)優(yōu)化，其能更好地優(yōu)化其云計算中局部最優(yōu)和過早收斂的問題。而在云計算中，諸如云平臺中數(shù)據(jù)遷移的開銷、引入安全性約束條件、服務間資源、資源共享等問題的提出和解決，都將再進一步地優(yōu)化現(xiàn)今的云計算算法，從而實現(xiàn)更好的算力，降低用戶響應時間等問題，這些都需對云計算的任務調(diào)度算法進一步完善和改進。