面向多目標優化的云計算調度研究綜述*

鄭 爽 呂遐東 陳 杰

（中國艦船研究設計中心 武漢 430000）

1 引言

云計算是并行計算和分布式計算技術等相結合的產物[1～2]。云計算利用互聯網與虛擬機等技術使得云計算資源具有隨時可用、按需服務等特性。云計算用戶可以通過網絡來遠程調用數據中心中的虛擬機來運行應用程序或者存儲數據。云計算使用按需付費的使用模式為用戶提供高效可靈活調整的云計算資源，可以滿足不同應用的各類需求，是目前一種普遍的計算方式。

云計算資源調度[3]是指根據云計算任務與云計算資源的實際情況將任務分配到資源執行且滿足一定要求的一個過程，云環境下的資源調度是一個需要綜合考慮各種情況的復雜性問題。對云服務供應商來說要有效的協調和分配資源，降低成本；對用戶來說首先要滿足服務的質量。云計算的計算資源共享池環境里有著大量資源節點，需要對資源進行合理分配與調度，才能實現海量數據的快速計算。

在優化設計中，要求多個目標達到最優的問題被稱為多目標優化或者多約束問題[4]。多目標優化的云計算調度是在考慮多個調度指標的情況下將任務映射到合適的云計算的資源上的一個過程。

已存在一些相關的云計算調度相關綜述研究文獻，往往只著重于闡述云計算調度中啟發式算法研究，對云計算調度中其他重要因素有所忽略。如：文獻[5]看重不同云環境下云計算任務調度啟發式算法研究與討論。文獻[6]針對云計算任務調度各類啟發式算法優缺點進行了總結歸納。文獻[7]以調度目的為側重點總結歸納了四類調度的啟發式算法策略。文獻[8]也只以云計算任務調度啟發式算法為出發點總結分析了各類方法的基本思想與優缺點。而本文針對云計算整個調度流程進行了梳理，并對常用的一些調度指標體系并進行系統性總結，在算法研究方面不僅總結了經典算法與啟發式算法也闡述了基于強化學習、深度強化學習的新型調度研究，并都選取相關代表文獻進行總結分析。最后，討論面向多目標優化的云計算調度研究中存在的不足和未來研究趨勢，為云計算調度的進一步研究提供參考。

2 體系架構

2.1 云計算基本概念

數據中心：云數據中心其中包括對服務器、存儲、網絡、應用等的虛擬化，使用戶可以按需調用各種資源；其次還有對物理服務器、虛擬服務器以及相關業務的自動化流程管理。數據中心依據服務器性能等的不同分為單一數據中心、多同構數據中心、多異構數據中心。

服務器：服務器是通過虛擬化、集群技術等進行資源整合，通過云端控制平臺按需生成相關主機資源。服務器也可稱之為物理主機，可以自行分配與實行多種網絡功能服務。服務器也可以分為同構與異構。

云計算任務（Task，t）：云計算任務就是云用戶提交的需要用到云計算資源（服務器、網絡設備、存儲等）處理的任務，云計算任務根據任務的特點可以分為一般任務、計算型任務、存儲型任務、內存型任務。

虛擬機（VM）：虛擬機是服務器通過虛擬化技術虛擬表示形式的應用、服務器、存儲和網絡的的一種服務模式，以虛擬機的形式為用戶提供云服務可以減少IT開銷，同時提高效率和敏捷性。虛擬機根據運行內存、CPU核心數、存儲的不同也可以分為同構虛擬機與異構虛擬機，虛擬機對應任務類型也分為通用型、計算型、內存型和存儲型等，這些虛擬機在CPU、內存、操作系統等軟硬件設施上都有所不同。

云用戶：通過云計算服務接口向云服務提供商請求云計算服務的大型企業、小型組織或個人。

云服務提供商：基于云平臺、基礎結構、應用程序、存儲提供云服務服務的公司或者組織。

指標體系：對云計算調度的一種量化評價方案。可以根據調度指標的多少分為單一目標優化和多目標優化指標體系。云計算調度中的典型指標有任務執行時間、系統能耗、系統可用性、系統經濟、負載均衡、資源利用率、安全性等。

指標權重：多目標優化的云計算調度中各各優化指標的的相對比重，權重不僅僅是某一指標所占的百分比，強調的是指標的相對重要程度，傾向于貢獻度或重要性。

目標函數：是云計算調度系統的性能標準，云計算在調度中所追求的目標，通常，這些目標通過量化的指標與權重設置為數學函數的形式。

2.2 云計算調度架構

云計算調度架構如圖1所示，在云計算調度架構中，云用戶直接面對的是虛擬機，而虛擬機必須部署到服務器上才有能力來處理云任務，真正解決問題的還是實際的物理資源，所以云計算調度是一個二級的調度，即在滿足一定調度指標的前提下，根據調度策略將任務分配到虛擬機上執行的任務調度[9]和將虛擬機部署到物理位置相同或分隔、資源同構或異構的服務器上的資源調度[10]兩個調度過程。

圖1 多目標優化的云計算調度架構

2.3 多目標優化的資源調度運行過程

云環境下的多目標優化調度需要從實際需求出發選擇恰當的調度指標，調度指標可以選擇一個或者多個，然后為每個指標定權重來構成調度的目標函數。通過這樣的方式將多目標求解問題轉換為單一目標函數最優化問題。然后調度策略生成器獲取任務管理器與虛擬資源管理器中的信息結合云計算調度的指標評價體系通過調度算法來生成一個符合需求的調度策略或者說調度的方案。再按照生成的方案將云用戶的任務提交到資源上運行，運行完成后將結果返回給云用戶。

3 主要研究方面

3.1 云計算調度優化指標體系

在多目標優化的云計算調度問題上需要面對的指標是有很多的，為了得到用戶和云服務提供商滿意的調度結果，就需要從眾多的調度指標中挑選出一定量的能充分代表需求的指標來構造一個指標體系。例如基于利益相關視角的多維QoS云資源調度方法[11]以云任務執行時間、云任務最終完成時間、云系統能耗、云系統可用性、云系統經濟五個調度指標構成了一個基于利益相關的指標體系。面向服務可靠性的云資源調度方法[12]以服務器負載均衡作為調度指標體系設置了一個面向服務可靠性的指標體系。云環境下綠色任務調度策略[13]以系統性能作為指標體系設置了一個面向綠色云計算的調度體系。

云環境下的調度是要考慮單一或者多個指標最優化的復雜問題，需要從實際需求出發選擇恰當的調度指標來構成一個多目標優化指標體系。根據實際需求出發，云計算相關調度指標體系可以分為面向性能的指標體系、面向經濟的指標體系與面向綠色節能的指標體系。

目前尚無專門論文來面向多目標優化的云計算指標體系進行研究，本文根據不同論文的優化側重點不同將相同類型優化體系進行了一定匯總。現階段多目標優化的云計算調度指標體系研究成果較少，評價指標的設置沒有一個科學的方法進行對比分析，需要進一步進行評價指標在數學方面的研究。

3.2 云計算調度優化指標權重確定方法

設置云計算調度指標體系之后，就需要依據各指標權重與云計算調度指標體系來確定調度的目標函數。在多目標優化的云計算調度中，各指標的相對重要性（權重）的確定是一個關鍵。其特點就在于指標與指標間的矛盾性，而解決矛盾性的就是依靠合理的給各指標設置權重來解決。對各指標的賦權的合理與否，直接確定到分析結論的可靠性，目前多目標優化的權重確定方法主要有主觀定權法、專家評價法、層次分析法、熵權法、相關系數法等。但目前多目標優化的云計算調度中相關文獻中定權重主要還為主觀設置各指標權重。例如，文獻[20]給時間、安全、費用、可靠性指標應用主觀定權重（0.4，0.2，0.2，0.2）。文獻[21]給執行時間、負載應用主觀定權重為（1，1）。僅有極個別利用層次分析法來為各指標設置權重。例如，文獻[22]應用層次分析法給執行時間、服務延遲成本、成本、運行能耗定權重為（0.39，0.07，0.375，0.165）。

表2 典型定權方法

目前在多目標優化的云計算調度研究中設置多目標權重的方法都非常原始，且絕大多數只看重在固定權重方式下調度結果的優劣，沒有考慮到權重賦值的合理與否也與調度的結果好壞有著直接的影響，未來的多目標優化的云計算調度權重設置中應該對權重的具體值設置進行多次實驗驗證，找到一個最優的權重賦值方案。

3.3 云計算傳統資源調度方法

在對云計算調度問題解決方法發探索中，人們首先想到的是針對一個目標然后不惜一切代價將該目標優化到極限，例如。在云計算任務調度方面的研究首先出現了一些簡單但是很經典的調度策略。MCT（最小完成時間）[23]、先來先服務、Round Robin 調度[24]、貪婪策略調度[25]、Min-Min調度[26]和Max-Min調度[27]等。

但是在將單一目標最優化過程中可能會在其他因素上付出比較大的代價。隨著科學的進步，此類問題求解方法的增加，人們開始考慮解決多目標同時得到優化的問題。

隨著可以實現多目標優化的啟發式算法的不斷成熟，越來越多的研究人員把將基于生物啟發的遺傳算法、獅子算法、帝國競爭算法等和基于群體智能的蟻群算法、粒子群算法、貓群算法、魚群算法等引入到云計算調度中，這類算法的思想[8]在于：解決多目標優化問題時，給出一個在滿足約束條件的情況下，基于多目標優化的一個優解。可能這個解有時不是這個解空間中的最優解，但是是盡量滿足調度指標的極優解。

表3 經典調度策略

表4 經典啟發式算法

圖2 啟發式算法一般流程

各個啟發式方法都有其優缺點，單獨用來做云計算調度的算法都有其缺陷，有些研究人員就針對某一算法的缺項進行專門優化，設計了一系列改進型的啟發式算法。例如，改進差分進化算法、改進遺傳算法、改進粒子群、改進蟻群等。也有研究人員就將其中算法進行兩兩組合，利用算法之間優勢互補來設計新的組合算法，例如利用遺傳算法（GA）在迭代前期尋優速度快，蟻群算法（ACO）進化后期搜索速度快，求解效率高的的特點設計的GA-ACO優化算法。還有基于布谷鳥搜索（CS）和粒子群優化（PSO）兩種算法相結合提出的多目標布谷鳥粒子群優化算法（MO-CPSO）等。

3.4 云計算新型資源調度方法

傳統算法策略的最優解在特定的條件下才能獲得，面對越來越復雜的云計算環境，其通用性不強，并且容易在多目標求解的過程中陷入局部最優解，從而無法得到全局最優解。針對這些問題就有研究人員將強化學習[36]、深度強化學習[37]等新興技術應用到云計算調度中來探索最優的調度策略。

這類新型的云計算資源調度方法在機制上與傳統啟發式算法有很大的不同，例如強化學習（Reinforcement Learning，RL）作為一種無模型的學習方法，其是通過不斷試錯機制來探索解決問題的最優解。在多目標優化的云計算資源調度問題上可以通過不斷試錯的機制來得到多目標優化的云計算資源調度問題的最優解。深度學習具有很強大的特征提取的能力，在多目標優化的云計算資源調度問題上可以通過學習到的特征來進行優化調度。所以在云調度求解上二者也有著很好的性能表現，其次也可以將二者結合起來構成深度強化學習算法來充分利用二者的優勢。

表5 改進啟發式算法

表6 新型資源調度方法

4 結語

云計算通過虛擬化技術將各種資源整合起來形成資源池，并將大量云用戶提交的任務分配到資源節點上運行，使各個用戶都能按需獲取計算資源、存儲資源和各種軟件服務。目前，多目標優化的云計算調度主要研究方向集中在調度算法上，多目標優化的云計算調度算法主要為啟發式算法、改進的啟發式算法。很少有將強化學習、深度學習等新型方法應用到多目標優化的云計算調度中來。其次，目前關于多目標的云計算調度的調度指標權重設置也處于一個很原始的狀態，現有關于多目標的云計算調度研究的權重設置方式多為主觀設置權重，僅有極個別利用層次分析法設置指標權重，但具體情況下權重如何設置，設置之后效果有何變化，也無研究人員專門研究此內容。

隨著云計算平臺的資源異構化、作業的多樣化、服務質量的嚴格化，云服務提供商現在多傾向于使用大規模數據中心下的多用戶多隊列多虛擬機集群的服務模式。面對復雜多變的云環境，傳統啟發式算法其通用性不強的缺點漸漸顯露了出來，未來云調度算法的研究應該從改進啟發式算法轉移到將強化學習、深度學習這類通用性更強的方法改進應用到多目標優化的云計算調度上來。調度指標的權重設計也應該嘗試采用更多的數學分析的方法，例如模糊法、模糊層次分析法等。也可以嘗試在調度過程中設計權重自適應調整的機制。

總之，一個優秀的多目標優化的云計算調度需要根據任務與資源的不確定性來靈活的采取調度策略，在盡可能綜合考慮更多的調度指標下，提高云計算服務質量。