摘要：本文在云經濟模型的基礎上，提出一種受用戶級QoS驅動的分組調度算法。該算法基于對云QoS的屬性分析，對經濟云現有的DBC調度算法進行了擴展和改進。在滿足任務的截止期限和預算的范圍內，根據任務是否具有高網絡帶寬進行分組。通過把基于用戶專有的QoS的需求加入到常規分組調度算法中，從而形成了一個基于網絡帶寬的分組調度算法。仿真結果顯示：在模擬的云環境下，本文算法擁有較高的吞吐量和任務完成率。

引言

　　目前大多數云計算環境下的調度和資源管理問題一般仍使用傳統形式，即由調度構件如Glbous根據確定的花費函數來決定任務應在哪里執行，但這些花費函數一般都以系統為中心的，難以通過用戶的QoS參數如存取價格、服務傳送時間片等驅動。在經濟管理模型下，不同的系統當然不會花費同樣的價格來存取相同的資源。終端用戶也不一定想要支付最高的價格來獲得最有效的資源利用，而是有可能基于需求、價值、優先權和可供使用的預算協商一個特定的價格^[1]。此外，QoS是一個綜合指標，不同應用的側重不同，在計算密集型任務當中，QoS往往反映資源的運算速度，而在一些數據密集型的任務當中，QoS較多地表示節點之間的帶寬、節點數據的質量等指標^[2]。在經濟學方法中，調度決定不是靜態地由單個調度實體來完成，而是由終端用戶的要求直接驅動^[2]。一個常規的經濟模型，一般關注的是運行應用的軟件和硬件花費，而經濟模型主要對最終用戶的服務收取費用^[3]。在競爭的經濟市場中，基于用戶需求和可供使用資源的交易是主要驅動力。

　　對此，本文提出了一種面向任務交易成本和截止期限的分組任務調度策略。該策略優先選取用戶級具有高網絡帶寬要求的任務進行調度，根據交易價格和平均價格的比較將任務分成兩組，在可用資源列表中對兩組任務分別進行時間優化和花費優化調度。最后測試了本文算法的調度性能。

1 系統模型假設

　　在競爭的經濟市場中，基于用戶需求和可供使用資源的交易是主要驅動力。因此，我們關注的是單個用戶在云中與其它用戶以及云服務提供者和資源擁有者的競爭。

　　云需要合適的資源管理模型使成員有效地共享資源。本文采用計算經濟模型與用戶交互的管理方式，向用戶的任務提供服務質量保證。云環境中的QoS有一系列的規范，包括資源響應時間、可用性、安全性、吞吐量等^[6]。本文選擇在費用(Cost)，期限(Deadline)和任務執行的可靠性(Reliability)這三維QoS約束下調用有限的資源來滿足不同云用戶的請求。調度者和用戶需求被公式化為效用函數、和，分別代表用戶選擇QoS選擇產生的效益，根據每一個效益函數提供定量計算QoS的數學方法。調度問題可以推廣為多個不同長度的任務在多個不同資源上的調度問題。同時約定：

　　(1)進行調度的一組任務是互相獨立，即任務之間沒有通信和數據依賴^[6];

　　(2) 各種資源有不同的處理能力;

　　(3)一個資源在同一時刻只能處理一個任務;

　　(4)一個任務不能同時在兩個資源上處理;

　　(5)任務一旦運行，運行該任務的資源被獨占，只能等到任務完成后，再執行別的任務。

　　對資源的調用要遵從市場經濟模式，當云中有N個任務和M個可用資源時，網絡資源調度策略在N個任務和M個資源之間進行匹配，使得既可以滿足用戶的要求和云資源約束，又可以使完成任務目標代價最優或近似最優^[7]。提出任務的客戶端希望找到能夠滿足用戶要求的資源使任務執行的時間最短而且價格最低^[8]。提供資源的工作端希望自己的資源能夠充分利用，盡量減少空閑資源的時間，提高資源的利用率，增加自己的經濟效益^[9]。

　　假設某一時刻云用戶向系統提交了N個任務，每個任務的長度為Li，用指令數來度量，單位為MI百萬指令，截止期限Deadline以及可以支付的最大預算Budget值(由用戶指定)如下表所示，任務按照長度從大到小的順序進行排序。

　　初始狀態下云系統中存在的M個可用資源的處理速度以及各個資源的性能開銷參數列表如下，其中Vi表示每個資源的處理速度，Ci表示資源R每百萬條指令的執行開銷(Cost/MI)。資源按照處理速度從大到小的順序進行排序。新資源因為還未分配任務，所以它的任務列表為空;若某一資源的任務列表不為空，則稱這個資源是舊的。將所有到達的任務分配給新資源，若此時沒有新資源可用則將任務分配給舊資源。初始時刻，全部資源都是新的，把長度最大的任務T0分配給處理速度最快的資源R0，計算執行的時間和開銷是否超出了用戶可以承受的Deadline和Budget，如果未超過則將T0加入R0的任務列表，否則考慮下一個可用的新資源。同時將該資源從新資源列表中刪除，加入舊資源列表，并將其標志為舊資源，反復進行此過程，直到全部的任務都被調度或調度失敗。調度的目標是找到能夠在期望的執行時間內完成工作任務、而且所付出的費用相對比較廉價的資源，即時間和費用是最優的^[10]。

　　基于多QoS規劃模型進行資源分配和任務調度的算法描述如下:

　　(1)隨時接收客戶端的資源申請(客戶端申請中給出了資源需求);

　　(2)在每一個長度為T的時間段內開始執行以下算法步驟：

　　(a)按規劃進行任務刻錄;

　　(b)用戶需求為調度范疇，進行資源調度比對;

　　(c)按最佳匹配原則進行匹配;

　　(d)在調度周期內確認有多少資源可以進行調度;

　　(e)計入運算結果;

　　(f)反饋給客戶。

2 基于多維云用戶驅動QoS網絡資源調度

　　在一個三維的QoS模型空間中對此調度問題進行研究。模型空間由運行費用(C)，截止期限(D)和可靠性(R)構成。其中C代表花費Cost，執行云任務時的花費包括處理計算資源和網絡(傳輸帶寬)資源的花費;D代表截止期限Deadline：處理云任務的全部時間;R代表可靠性Reliability：完成任務的概率。

　　云任務i可以使用資源代理j的計算資源：(表示資源的處理時間)，如果j的計算能力為Cj，則相應的資源分配約束條件為 。i執的時間上限。任務代理i支付給計算資源代理j的報酬為，那么代表了第j個計算資源代理完成所有任務獲得的全部報酬。

　　考慮模型的效益函數，第一維效益函數，是和費用有關的：

(1)

：資源預算，是i為獲得計算資源付出的總代價;表示第一維QoS的權重。

　　第二維QoS效益函數是和執行時間有關的：

(2)

T_i是i的執行截止時間;b_in是完成第n個工作需要的計算資源數量;D代表延遲時間;代表分配到第二維QoS的權重;

　　第三維效益函數代表調度的可靠性：

　; (3)

　　g：在截止期限內完成調度的任務數，f：在截止期限內總共提交的任務數。

　　任務的效用函數是這三部分的加權函數：

(4)

　　整個系統的效用函數

(5)

　　網絡資源調度者的目標是在QoS約束下為i進行資源分配，最大化系統效益并滿足：

(6)

　　在經濟模型下最大化任務代理獲得的效用，使用拉格朗日數學方法求得多維QoS約束的網絡資源調度問題的最優解：在時間期限內，最優化任務代理：

(7)

　　在資源市場上，計算資源作為資源供應者，考慮到任務代理愿意付出的代價，試圖最大化它們的收益：。這樣，云資源供應者的最優化問題可被公式化為，且

　　由以上對QoS進行量化的效益函數表達式可知，完成時間和花費QoS是負QoS參數，其它屬性的QoS參數是正QoS參數。所謂的負QoS參數是指QoS值越大，其效益函數值越小，正QoS參數是指QoS值越大，其效益函數值越大，見圖1。

　　再利用拉格朗日乘數法求解在多QoS約束條件下的最優解，構造以下的輔助函數：

(8)

　　令，就可以得到最優化任務代理問題的最優解，表示任務代理在約束時間條件下為了最大化系統效益應該付出的價值;

　　再來考慮對資源代理的優化：且，求約束條件下的最優解，構造拉格朗日函數：

(9)

　　令，可以求得計算資源代理優化問題的最優解，表示計算資源代理作為資源供應者，為了最大化它的收入希望分配給任務代理的的單元個數。

3 仿真實驗

3.1 仿真參數設置

　　本文采用NS2仿真平臺進行仿真實驗，詳細仿真結果如表2所示。

3.2 實驗結果對比

　　圖 2、圖3顯示了本文算法與DBC算法在完成任務效率上的比較。依圖2可知，滿足要求的任務個數隨著deadline的增加而增加，但DBC算法的deadline增加到2400以后，完成的任務個數保持在一個數值不再增加，這是因為完成的任務已經用完了用戶提供的budget，增加deadline的值對任務的完成數沒有影響，這符合計算經濟網格中的交易原則;在期限固定的情況下，隨著預算的增加，對于任務的完成情況，本文都比傳統DBC優化算法有一些提高，說明本文算法提高了截止期限內的任務完成率(任務的可靠性)。由圖3可知，滿足要求的任務個數隨著budget的增加而增加，但是本文算法的提升速度更快，這是由于本文算法采用拉格朗日計算方式，在Dealine固定的時候，能夠更有效地提高資源調度效率，從而在一定截止時間內完成的任務數更多。

4 結束語

　　本文對基于經濟模型的云網絡資源調度問題進行了詳細的介紹，分析了使用經濟原則和交易議價的優點，認為它能夠更好地適應現代網格的發展。在對網格傳統的調度算法進行研究的基礎上，根據現代網格基于市場經濟模型進行資源管理的特點，提出了一種基于多維云用戶驅動QoS網絡資源調度算法。通過合適的分組機制有效地降低了經濟代價，具有一定的部署價值。

參考文獻：

　　[1]Gounder V, Prakash R, Abu-Amara H. Micheline data miming: date and techniques[C]. Wireless Communications and Systems, 2014: 1-6

　　[2]胡自林,徐云, 毛濤. 基于效益最優的云網絡資源調度. 計算機工程與應用, 2014, 7: 69-70

　　[3]Ngai EWT,Hu Y.The application of data mining techniques in financial fraud detection :A classification framework and an academic review of literature[J]. Decision Support System, 2011, 50(3):559-569

　　[4]Thelwall ,Wilkinson D.Data mining emotion in social network communication:Gender differences in MySpace[J].Journal of the American Society for Information Society for Information Science and Technology, 2010, 61(1):190-199

　　[5]lcala-Fdez J.KEEL Data-Mining Software Tool:Data Set Repositoty ,Integration of Algorithms and Experimental Analysis Framework[J].Journal of Multiple -Valued Logic $Soft Computing,2011,12(17):204-209

　　[6]Bal M.Rough Sets Theory as Symbolic Data Mining Method:An Application on Complete Decision Table[J].information Sciences Letters,2013,2(1):111-116.

　　[7]Yang K,Shahabi C.An efficient k nearest neighbor search for multivariate time series[M].Information and Computation,2013: 65-98

　　[8]JolliffeD, Tran T, Nguyen T. Data mining network coding [J]. IEEE Trans. on Vehicular Technology, 2009, 58(2): 914-925

　　[9]Ester P, Sander S.A key efficient way of data mining techniques[C]. Michine and Systems，2014.:74-79

　　[10]Foster I, Kesselman C. Globus: A Metacomputing Infrastructure Toolkit. Intl J. Supercomputer Applications.1997, 11(2):115 - 128

　　[11]LEE W.A data mining framework for constructing features and models for instrusion detection systems[D]. New York Computer Science Department of Columbia University，2012: 33-76

　　[12]Wang W,Yang J. A statistical information grid approach to spatial data mining[C]. Proc Int Conf Very Large Databases，1997:186-195

本文來源于中國科技期刊《電子產品世界》2016年第1期第41頁，歡迎您寫論文時引用，并注明出處。