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

引言

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

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

1 系統(tǒng)模型假設(shè)

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

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

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

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

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

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

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

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

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

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

　　基于多QoS規(guī)劃模型進行資源分配和任務(wù)調(diào)度的算法描述如下:

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

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

　　(a)按規(guī)劃進行任務(wù)刻錄;

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

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

　　(d)在調(diào)度周期內(nèi)確認有多少資源可以進行調(diào)度;

　　(e)計入運算結(jié)果;

　　(f)反饋給客戶。

2 基于多維云用戶驅(qū)動QoS網(wǎng)絡(luò)資源調(diào)度

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

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

　　考慮模型的效益函數(shù)，第一維效益函數(shù)，是和費用有關(guān)的：

(1)

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

　　第二維QoS效益函數(shù)是和執(zhí)行時間有關(guān)的：

(2)

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

　　第三維效益函數(shù)代表調(diào)度的可靠性：

　; (3)

　　g：在截止期限內(nèi)完成調(diào)度的任務(wù)數(shù)，f：在截止期限內(nèi)總共提交的任務(wù)數(shù)。

　　任務(wù)的效用函數(shù)是這三部分的加權(quán)函數(shù)：

(4)

　　整個系統(tǒng)的效用函數(shù)

(5)

　　網(wǎng)絡(luò)資源調(diào)度者的目標是在QoS約束下為i進行資源分配，最大化系統(tǒng)效益并滿足：

(6)

　　在經(jīng)濟模型下最大化任務(wù)代理獲得的效用，使用拉格朗日數(shù)學方法求得多維QoS約束的網(wǎng)絡(luò)資源調(diào)度問題的最優(yōu)解：在時間期限內(nèi)，最優(yōu)化任務(wù)代理：

(7)

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

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

　　再利用拉格朗日乘數(shù)法求解在多QoS約束條件下的最優(yōu)解，構(gòu)造以下的輔助函數(shù)：

(8)

　　令，就可以得到最優(yōu)化任務(wù)代理問題的最優(yōu)解，表示任務(wù)代理在約束時間條件下為了最大化系統(tǒng)效益應(yīng)該付出的價值;

　　再來考慮對資源代理的優(yōu)化：且，求約束條件下的最優(yōu)解，構(gòu)造拉格朗日函數(shù)：

(9)

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

3 仿真實驗

3.1 仿真參數(shù)設(shè)置

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

3.2 實驗結(jié)果對比

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

4 結(jié)束語

　　本文對基于經(jīng)濟模型的云網(wǎng)絡(luò)資源調(diào)度問題進行了詳細的介紹，分析了使用經(jīng)濟原則和交易議價的優(yōu)點，認為它能夠更好地適應(yīng)現(xiàn)代網(wǎng)格的發(fā)展。在對網(wǎng)格傳統(tǒng)的調(diào)度算法進行研究的基礎(chǔ)上，根據(jù)現(xiàn)代網(wǎng)格基于市場經(jīng)濟模型進行資源管理的特點，提出了一種基于多維云用戶驅(qū)動QoS網(wǎng)絡(luò)資源調(diào)度算法。通過合適的分組機制有效地降低了經(jīng)濟代價，具有一定的部署價值。

參考文獻：

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

　　[2]胡自林,徐云, 毛濤. 基于效益最優(yōu)的云網(wǎng)絡(luò)資源調(diào)度. 計算機工程與應(yīng)用, 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

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