基于云計算的流媒體任務調度算法*

楊 戈 ，吳俊言

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

0 引言

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

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

而對于計算機資源管理方面，文獻[7]研究了虛擬云桌面上的動態調度應用，文獻[8]中提出了一種關于網絡感知的計算資源下的對虛擬機的放置算法。

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

1 云計算資源調度模型

云計算中的資源調度可通過以下的模型表示：

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

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

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

2 GAAC 算法

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

2.1 GAAC 算法實現

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

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

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

（1）初始化，首先設定相關參數；

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

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

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

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

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

2.2 GAAC 算法流程

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

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

（1）當tasktime（t）a

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

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

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

圖1 GAAC 算法流程圖

3 仿真實驗

本文運用了云計算的模擬平臺Cloudsim，通過Cloudsim實現云環境的模擬配置，達到異構的云環境。

3.1 軟硬件

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

表1 硬件及軟件配置

3.2 仿真結果

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

表2 仿真實驗參數

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

圖2 任務調度算法對比1

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

圖3 任務調度算法對比2

表3 仿真實驗參數

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

圖4 任務調度算法對比3

表4 仿真實驗參數

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

4 結論

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