移動(dòng)云計(jì)算環(huán)境下任務(wù)調(diào)度的多目標(biāo)優(yōu)化方法

胡海洋 劉潤華 胡 華

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院 杭州 310018) (復(fù)雜系統(tǒng)建模與仿真教育部重點(diǎn)實(shí)驗(yàn)室(杭州電子科技大學(xué)) 杭州 310018)

移動(dòng)云計(jì)算環(huán)境下任務(wù)調(diào)度的多目標(biāo)優(yōu)化方法

胡海洋 劉潤華 胡 華

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院 杭州 310018) (復(fù)雜系統(tǒng)建模與仿真教育部重點(diǎn)實(shí)驗(yàn)室(杭州電子科技大學(xué)) 杭州 310018)

(huhaiyang@hdu.edu.cn)

移動(dòng)云計(jì)算技術(shù)可幫助移動(dòng)用戶在執(zhí)行工作流任務(wù)時(shí)將一些任務(wù)遷移至云端服務(wù)器執(zhí)行，從而節(jié)省移動(dòng)設(shè)備的電池能耗，并提高計(jì)算能力.傳統(tǒng)研究工作在進(jìn)行移動(dòng)云計(jì)算環(huán)境中的任務(wù)調(diào)度時(shí)缺乏對能耗和運(yùn)行時(shí)間的聯(lián)合優(yōu)化.為了實(shí)現(xiàn)有效的任務(wù)調(diào)度，基于工作流圖中任務(wù)執(zhí)行的先后關(guān)系，分析了采用動(dòng)態(tài)電壓頻率調(diào)節(jié)技術(shù)的移動(dòng)設(shè)備處理器執(zhí)行工作流任務(wù)的運(yùn)行時(shí)間與能耗，并考慮了將任務(wù)通過無線信道遷移到云端服務(wù)器執(zhí)行所需的時(shí)間，給出了能耗與執(zhí)行時(shí)間聯(lián)合優(yōu)化的任務(wù)調(diào)度模型和目標(biāo)方程.提出基于模擬退火算法的任務(wù)調(diào)度方法，分析了算法時(shí)間復(fù)雜度，進(jìn)行了系統(tǒng)性的對比實(shí)驗(yàn)，評估了所提出方法的正確性和有效性.

移動(dòng)云計(jì)算；工作流;任務(wù)調(diào)度；模擬退火；多目標(biāo)優(yōu)化

無線移動(dòng)計(jì)算技術(shù)的普及為跨地域的企業(yè)內(nèi)部工作流管理與移動(dòng)辦公提供了方便：借助于便攜式移動(dòng)計(jì)算設(shè)備，跨地域的各類工作人員可隨時(shí)進(jìn)行靈活的無線移動(dòng)辦公與協(xié)作支持，那些常需要出勤在外的企業(yè)管理與工作人員也能通過各類移動(dòng)計(jì)算設(shè)備及時(shí)進(jìn)入企業(yè)的工作流管理系統(tǒng)中審查日志、調(diào)配資源、交流協(xié)作和完成任務(wù).

盡管智能手機(jī)和無線通信技術(shù)能力在日益進(jìn)步，由于受電池容量、存儲與計(jì)算能力等方面的約束，與傳統(tǒng)服務(wù)器及桌面設(shè)備相比，移動(dòng)計(jì)算設(shè)備的硬件能力仍顯得非常有限[1].當(dāng)執(zhí)行數(shù)據(jù)密集型(data-intensive)或資源密集型(resource-intensive)的計(jì)算任務(wù)時(shí)，很難保證相應(yīng)的服務(wù)質(zhì)量.近年來移動(dòng)云計(jì)算技術(shù)(mobile cloud computing)的出現(xiàn)[2-4]為克服上述困難提供了一個(gè)良好的解決方案：它提供了基于云端資源共享和增強(qiáng)移動(dòng)計(jì)算兩者相統(tǒng)一的平臺[5-7]，可允許計(jì)算任務(wù)、數(shù)據(jù)存儲和海量信息處理被卸載(offloaded)到云端服務(wù)器執(zhí)行以提高服務(wù)的可靠性和可用性，并減少移動(dòng)設(shè)備端能量與計(jì)算資源的消耗.目前許多移動(dòng)應(yīng)用已經(jīng)采用移動(dòng)云計(jì)算技術(shù)來提供增強(qiáng)的移動(dòng)服務(wù)[8-9].

然而，現(xiàn)有面向移動(dòng)云計(jì)算環(huán)境的任務(wù)調(diào)度方法主要針對如何優(yōu)化任務(wù)完成的總時(shí)間[10-13]或者如何優(yōu)化移動(dòng)客戶端的能量消耗[14-17]，很少有研究工作綜合考慮這2方面的聯(lián)合優(yōu)化.本文針對這一多目標(biāo)優(yōu)化問題展開研究，給出調(diào)度模型與目標(biāo)優(yōu)化方程，并設(shè)計(jì)基于模擬退火方法的優(yōu)化算法，來對工作流任務(wù)完成的總時(shí)間和移動(dòng)客戶端能量消耗這2方面進(jìn)行綜合優(yōu)化.

1 相關(guān)工作

工作流任務(wù)調(diào)度問題已得到了廣泛的研究，各種啟發(fā)式算法被相繼提出[10-17].這些工作可分為2類：1)優(yōu)化應(yīng)用程序的總完成時(shí)間[10-13]；2)優(yōu)化整體的能源消耗[14-17].

在縮短工作流應(yīng)用的總完成時(shí)間方面，文獻(xiàn)[10]主要通過任務(wù)優(yōu)先級對異構(gòu)處理器環(huán)境中的應(yīng)用程序?qū)崿F(xiàn)高速的任務(wù)調(diào)度.文獻(xiàn)[11]首先通過快速確定算法進(jìn)行初始化，然后通過迭代方法不斷地改進(jìn)目前的解決方案.文獻(xiàn)[12]采用增量貪心策略并開發(fā)了一個(gè)運(yùn)行系統(tǒng)，它能自適應(yīng)地為移動(dòng)交互感知應(yīng)用程序進(jìn)行任務(wù)卸載和并行執(zhí)行，從而減少應(yīng)用程序的完成時(shí)間.文獻(xiàn)[13]提出了一種方法，可在移動(dòng)設(shè)備和云環(huán)境中的最大吞吐量之間，對數(shù)據(jù)流應(yīng)用的任務(wù)分配問題進(jìn)行優(yōu)化.

在減少總體的能量消耗方面，文獻(xiàn)[14]提出了在執(zhí)行周期性任務(wù)的計(jì)算機(jī)系統(tǒng)中降低能耗并使能耗達(dá)到最少的問題，在該方法中，研究者們假設(shè)任務(wù)的周期是足夠大的，任務(wù)之間的空隙時(shí)間是可以用來降低能耗的.文獻(xiàn)[15]將工作流任務(wù)調(diào)度問題視為一個(gè)最大流最小割的問題來處理，通過優(yōu)化在移動(dòng)設(shè)備和云計(jì)算環(huán)境中執(zhí)行的每個(gè)模塊任務(wù)從而使能量消耗最小化.文獻(xiàn)[16]在文獻(xiàn)[10]的基礎(chǔ)上進(jìn)行了擴(kuò)展，對異構(gòu)處理器環(huán)境中的能源消費(fèi)問題和任務(wù)完成時(shí)間都進(jìn)行了闡述，但文獻(xiàn)[16]中所給的任務(wù)調(diào)度算法不能保證調(diào)度結(jié)果一定都能滿足用戶所給的時(shí)間約束條件.文獻(xiàn)[17]中提出了一種根據(jù)網(wǎng)絡(luò)通信環(huán)境來進(jìn)行簡單直接的卸載策略以減少能源的消耗.

文獻(xiàn)[18]在文獻(xiàn)[16]基礎(chǔ)上，考慮了如何滿足時(shí)間約束條件下來進(jìn)行任務(wù)調(diào)度，并通過動(dòng)態(tài)電壓頻率調(diào)節(jié)(dynamic voltage and frequency scaling，DVFS)來減少任務(wù)之間的空隙時(shí)間從而降低能源消耗，但是該算法中使用到的動(dòng)態(tài)電壓頻率調(diào)節(jié)技術(shù)是離散的，這對能耗減少的效果并不是特別明顯，同時(shí)該算法對如何優(yōu)化工作流任務(wù)的總完成時(shí)間也沒有給出相應(yīng)的算法，僅僅滿足用戶所給的時(shí)間約束條件.

綜上所述，在任務(wù)分配時(shí)，大多數(shù)的任務(wù)分配算法僅考慮在最大截止時(shí)間條件下減少能耗，沒有將完成時(shí)間也作為優(yōu)化的一個(gè)目標(biāo).然而，為了減少能耗，會使得用戶較多地去選擇低功率的處理器或者通過技術(shù)手段動(dòng)態(tài)降低處理器的運(yùn)行功率，這樣使得工作流任務(wù)的總完成時(shí)間相應(yīng)增加.為了解決這樣的多目標(biāo)優(yōu)化問題，本文提出一種基于模擬退火算法的時(shí)間和能耗聯(lián)合優(yōu)化的工作流任務(wù)調(diào)度算法，該算法通過連續(xù)動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)能在滿足完成時(shí)間約束條件情況下使工作流應(yīng)用的完成時(shí)間和能量消耗都得到優(yōu)化，從而減少移動(dòng)設(shè)備的能量消耗并提高工作流應(yīng)用的執(zhí)行速度.

2 移動(dòng)云計(jì)算任務(wù)調(diào)度模型

2.1 問題描述和基本框架

Fig. 1 Application of picture recognition圖1 圖片識別應(yīng)用程序

由于移動(dòng)云計(jì)算技術(shù)可以幫助移動(dòng)用戶將一些工作流計(jì)算任務(wù)遷移至云端服務(wù)器執(zhí)行，從而節(jié)省移動(dòng)設(shè)備的能耗，并提高計(jì)算效率.目前研究者已經(jīng)開始探討如何將移動(dòng)云計(jì)算技術(shù)應(yīng)用到日常工作環(huán)境中，例如物體手勢識別、圖像視頻編輯、自然語言處理等領(lǐng)域[2,17-18].本文現(xiàn)通過一個(gè)具體實(shí)例來闡釋相關(guān)問題.某大型企業(yè)為了提高管理效率、降低運(yùn)營成本，建立了一個(gè)移動(dòng)工作流管理系統(tǒng)，企業(yè)員工可利用移動(dòng)終端設(shè)備進(jìn)入系統(tǒng)中就可以隨時(shí)隨地地辦公.在工作過程中，由于企業(yè)的一些數(shù)據(jù)處理工作較為復(fù)雜，此外一些復(fù)雜任務(wù)的計(jì)算量也較大，員工所攜帶的移動(dòng)設(shè)備硬件能力與電池能耗已經(jīng)不能滿足移動(dòng)辦公的需要.為解決該問題，企業(yè)可搭建一個(gè)基于移動(dòng)云計(jì)算環(huán)境的移動(dòng)辦公系統(tǒng).下面我們通過一個(gè)能耗和任務(wù)執(zhí)行時(shí)間都比較大的圖片識別應(yīng)用來進(jìn)行說明，如圖1所示.該應(yīng)用包括圖片數(shù)字化、色彩提取、形狀提取、邊緣提取、紋理提取、空間提取等一些處理步驟.對于圖片采集和數(shù)字化工作可由移動(dòng)設(shè)備自身完成；而對于色彩提取、形狀提取、紋理提取等工作，由于計(jì)算量較大，則需要上傳到公司的云端服務(wù)器去完成.對于這個(gè)工作流應(yīng)用，我們可以用一個(gè)有向無環(huán)工作流圖(如圖2所示)G=(V,E)來表示，其中每個(gè)節(jié)點(diǎn)vi∈V表示一個(gè)任務(wù)，有向邊e(vi,vj)∈E表示2任務(wù)之間的先后關(guān)系，即只有等vi完成之后vj才可以開始執(zhí)行.

Fig. 2 Directed acyclic graph of the workflow圖2 工作流的有向無環(huán)圖

一個(gè)工作流由N個(gè)任務(wù)節(jié)點(diǎn)組成，一般情況下，N不會超過100，比如在計(jì)算機(jī)視覺應(yīng)用程序中，N的范圍就是10～30.在給定的工作流任務(wù)圖中，沒有任何前驅(qū)節(jié)點(diǎn)的任務(wù)節(jié)點(diǎn)為開始任務(wù)，沒有任何后續(xù)節(jié)點(diǎn)的任務(wù)節(jié)點(diǎn)為結(jié)束任務(wù).如圖2所示，任務(wù)v1是開始任務(wù)，任務(wù)v10是結(jié)束任務(wù)；此外，其他一些工作流任務(wù)可以有前驅(qū)任務(wù)和后續(xù)任務(wù)(例如，對于任務(wù)v5來說，v1是它的前驅(qū)，v9是它的后續(xù)).基于文獻(xiàn)[18]，我們給出圖2中各個(gè)任務(wù)在移動(dòng)設(shè)備處理器以及在云端服務(wù)器的處理時(shí)間如表1所示:

Table 1 Completed Time of Each Task

表1表示10個(gè)任務(wù)分別在3個(gè)處理器上的完成時(shí)間(表示為Tcore1,Tcore2,Tcore3)以及任務(wù)被遷移到云端服務(wù)器處理所需的發(fā)送時(shí)間ts(vi)、執(zhí)行時(shí)間tc(vi)和接收時(shí)間tr(vi)，由于在云端可以高效地進(jìn)行任務(wù)處理，任務(wù)在云端的處理時(shí)間統(tǒng)一為3 s，發(fā)送任務(wù)到云端和從云端接收運(yùn)行結(jié)果的時(shí)間都統(tǒng)一為1 s.

為了便于理解，我們總結(jié)了本文的主要符號及其含義如表2所示:

Table 2 Definitions of Notations

2.2 任務(wù)執(zhí)行時(shí)間

設(shè)移動(dòng)設(shè)備含有M個(gè)異構(gòu)處理器，每個(gè)處理器都可進(jìn)行動(dòng)態(tài)電壓頻率調(diào)節(jié)[18]，即在不同頻率下對應(yīng)有不同的電壓.若用fmax(k)表示任務(wù)在第k個(gè)處理器上執(zhí)行時(shí)的最大電壓頻率，則任務(wù)vi運(yùn)行時(shí)的實(shí)際電壓f(vi,k)可由電壓變化率rat(vi)控制，即f(vi,k)=fmax(k)×rat(vi)，并且rat(vi)∈[ratmin(vi),1]，這里ratmin(vi)由式(1)確定：

(1)

其中,TL表示任務(wù)vi給定的截止時(shí)間，TM表示平均每個(gè)任務(wù)的理論最小完成時(shí)間：

(2)

其中，tc(vi)表示在云端服務(wù)器上運(yùn)行任務(wù)vi所需的執(zhí)行時(shí)間，包括將vi通過無線網(wǎng)絡(luò)發(fā)送到云端服務(wù)器上所需時(shí)間、任務(wù)vi在云端服務(wù)器執(zhí)行所需時(shí)間以及將執(zhí)行處理后的任務(wù)結(jié)果通過無線網(wǎng)絡(luò)返回到移動(dòng)設(shè)備上所需時(shí)間這3部分；tmk(vi,k)為移動(dòng)設(shè)備的第k個(gè)處理器上運(yùn)行任務(wù)vi所需的執(zhí)行時(shí)間，若采用DVFS調(diào)節(jié)，則任務(wù)vi在第k個(gè)處理器上的實(shí)際運(yùn)行時(shí)間為tmk(vi,k)rat(vi).綜合考慮這2方面情況，則任務(wù)vi的實(shí)際執(zhí)行所需時(shí)間為

(3)

2.3 能源消耗

在任務(wù)調(diào)度優(yōu)化過程中，一方面需要縮短工作流任務(wù)的總完成時(shí)間，另一方面也需要考慮工作流任務(wù)執(zhí)行過程中移動(dòng)設(shè)備的能源消耗.

設(shè)emk(vi,k)為無DVFS調(diào)節(jié)時(shí)任務(wù)vi在第k個(gè)處理器上執(zhí)行的能耗；若vi執(zhí)行時(shí)，處理器上的電壓變化率為rat(vi)，則vi執(zhí)行時(shí)的實(shí)際能源消耗為

(4)

則整個(gè)工作流G=(V,E)執(zhí)行時(shí)移動(dòng)設(shè)備所需的總能源消耗可以表示為

(5)

3 算法設(shè)計(jì)

本文提出一種基于模擬退火算法的任務(wù)調(diào)度策略SA-DVSA算法，來解決工作流任務(wù)調(diào)度的能耗與執(zhí)行時(shí)間優(yōu)化問題，算法分為3個(gè)步驟：初始化可行解、改變參數(shù)可行解和新變量取舍的判斷.我們將會分析加入了連續(xù)動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)后對結(jié)果的影響，并在實(shí)驗(yàn)部分對SA-DVSA算法與其他相關(guān)工作進(jìn)行比較.

3.1 算法框架

基于物理中固體物質(zhì)的退火過程與一般優(yōu)化問題之間具有一定的相似性，模擬退火算法[19-20]已被證明是一種適合求解大規(guī)模組合優(yōu)化問題的通用且有效的近似算法.對于組合優(yōu)化問題來說,解空間的每一點(diǎn)都代表一個(gè)具有不同目標(biāo)函數(shù)值的解，而優(yōu)化過程就是在解空間尋找函數(shù)最小解的過程.若把函數(shù)看成能量函數(shù)，把控制參數(shù)視為溫度，解空間作為狀態(tài)空間，那么模擬退火算法尋找基態(tài)的過程就可被是為求解目標(biāo)函數(shù)極小值的優(yōu)化過程，算法流程圖[19]如圖3所示.

Fig. 3 Framework of the simulated annealing algorithm圖3 模擬退火算法框架圖

將任務(wù)的處理位置、執(zhí)行順序、處理器電壓變化率作為變量，而工作流任務(wù)執(zhí)行的總完成時(shí)間與移動(dòng)設(shè)備的能源消耗這2方面的加權(quán)值作為適應(yīng)度目標(biāo)函數(shù)，則可將本文中的移動(dòng)云計(jì)算環(huán)境中工作流任務(wù)調(diào)度優(yōu)化問題轉(zhuǎn)化成組合優(yōu)化問題.對于這類組合優(yōu)化問題，我們可以根據(jù)適應(yīng)度函數(shù)，通過模擬退火算法迭代得到變量的最優(yōu)值.下面給出變量的定義：1)LOC={loc(vi)}表示各工作流任務(wù)執(zhí)行位置的集合，其中l(wèi)oc(vi)=k(1≤k≤M+1)表示任務(wù)vi被執(zhí)行的位置：即若k

設(shè)任務(wù)vi的開始執(zhí)行時(shí)刻為startT(vi),則由式(3)可得其實(shí)際完成時(shí)間為

(6)

vi的開始執(zhí)行時(shí)刻startT(vi)由2方面因素決定：1)其前驅(qū)任務(wù)節(jié)點(diǎn)的最遲完成時(shí)刻； 2)其所在移動(dòng)設(shè)備處理器或云端服務(wù)器上排序在前的那些任務(wù)的最遲完成時(shí)刻.這樣，startT(vi)可遞歸地用AFT(vj)(vj≠vi)表示為

(7)

這樣整個(gè)工作流的總完成時(shí)間可以表示為

(8)

則根據(jù)式(5)和式(8),執(zhí)行時(shí)間與能耗的聯(lián)合優(yōu)化目標(biāo)函數(shù)可表示為

(9)

3.2 初始化可行解

在本文的算法中，初始化解是隨機(jī)生成的.INIT_VAR算法先隨機(jī)產(chǎn)生工作流任務(wù)被處理的位置集LOC={loc(vi),loc(v2),…,loc(vN)}，然后根據(jù)式(1)和式(2)計(jì)算每個(gè)任務(wù)的最小電壓變化率,再在此基礎(chǔ)上隨機(jī)產(chǎn)生任務(wù)的電壓變化率集RATIO={rat(vi)}，接著初始化N個(gè)任務(wù)的順序?yàn)镺RDER={ord(vi)|ord(vi)=i,1≤i≤N},最后計(jì)算總能耗ETotal、運(yùn)行時(shí)間TTotal以及目標(biāo)函數(shù)值F.下面給出INIT_VAR算法的執(zhí)行過程：

算法1. INIT_VAR算法.

輸入：任務(wù)數(shù)N、移動(dòng)設(shè)備的處理器數(shù)M、任務(wù)在云端服務(wù)器運(yùn)行時(shí)間集TC={tc(vi)}、任務(wù)遷移到云端服務(wù)器運(yùn)行時(shí)移動(dòng)設(shè)備能耗集EC={ec(vi)}、任務(wù)在移動(dòng)設(shè)備的運(yùn)行時(shí)間集TMK={tmk(vi,k)};任務(wù)在移動(dòng)設(shè)備運(yùn)行的能耗集EMK={emk(vi,k)}、截止時(shí)間TL;

輸出：任務(wù)處理初始位置集LOC、初始電壓變化率集RATIO、初始任務(wù)執(zhí)行順序集ORDER.

隨機(jī)生成處理位置集LOC{loc(vi)},其中l(wèi)oc(vi)=random(1,M+1);

FOR eachvi∈VDO

根據(jù)式(1)、式(2)計(jì)算ratmin(vi)；

IF(loc(vi)≠M(fèi)+1)

rat(vi)random(ratmin(vi)，1);

ELSE

rat(vi)1.0;

ENDIF

將rat(vi)加入集合RATIO中;

ENDFOR

生成初始任務(wù)執(zhí)行順序集ORDER{ord(vi)},其中ord(vi)=i;

根據(jù)式(5)、式(8)和式(9)計(jì)算目標(biāo)函數(shù)值F.

3.3 改變參數(shù)可行解算法

CHANGE_VAR算法將隨機(jī)改變?nèi)蝿?wù)vi執(zhí)行所在的位置及電壓.在改變執(zhí)行位置的過程中，隨機(jī)選擇某處理器或云端服務(wù)器位置k,得到k處的任務(wù)vi可被執(zhí)行的次序區(qū)間R1.R1可通過如下過程計(jì)算得到：找出vi在k處的全部前驅(qū)任務(wù)中的最大執(zhí)行次序值x1，找到vi在k處的全部后續(xù)任務(wù)中的最小執(zhí)行次序值x2，則R1區(qū)間為(x1，x2).在區(qū)間R1上隨機(jī)選擇vi的某個(gè)執(zhí)行次列位s1；然后遍歷R1中所有其他執(zhí)行次列上的當(dāng)前任務(wù)，對每個(gè)任務(wù)vj，分析其在k處上的可執(zhí)行的次序區(qū)間R2，分析R2與R1的交集Rcross，若Rcross≠?，則表示vi與vj可互選，則將vj的執(zhí)行次序位加入集合RA中，最終從可互換的執(zhí)行序列集RA中隨機(jī)選擇一個(gè)序列位s2，交換s1和s2上的執(zhí)行任務(wù),從而得到新的可行解LOC′,RATIO′,ORDER′和目標(biāo)函數(shù)值F′.下面給出CHANGE_VAR算法的執(zhí)行過程：

算法2. CHANGE_VAR算法.

輸入：任務(wù)處理位置集LOC、電壓變化率集RATIO、任務(wù)執(zhí)行順序集ORDER;

輸出：更新后的任務(wù)處理位置集LOC′、電壓變化率RATIO′、新任務(wù)順序ORDER′.

LOC′LOC;RATIO′RATIO;ORDER′ORDER;

從任務(wù)集V中隨機(jī)選取任務(wù)vi;

隨機(jī)選取任務(wù)新的處理位置k，loc(vi)k;

IF(k≠M(fèi)+1)

rat(vi)random(ratmin(vi)，1);

ELSE

rat(vi)1.0;

ENDIF

計(jì)算vi處理位置k上的可執(zhí)行次序區(qū)間R1；

在R1中隨機(jī)選擇可執(zhí)行序列位s1,ord(vi)s1;

FOR eachs2∈R1DO

IF(s2≠s1)

獲取s2上所對應(yīng)的執(zhí)行任務(wù)vj；

計(jì)算vj在處理位置k上的可執(zhí)行次序區(qū)間R2；

令RcrossR1∩R2;

ENDIF

IF(Rcross≠?)

RARA∪{s2};

ENDIF

ENDFOR

IF(RA≠?)

從RA中隨機(jī)選取序列位s2,獲取s2上所對應(yīng)的執(zhí)行任務(wù)vj;

交換ORDER中vi與vj的執(zhí)行序列;

ENDIF

3.4 變量值取舍算法

通過改變參數(shù)可行解算法得到了新可行解，新可行解是否被接受為當(dāng)前最優(yōu)解需要進(jìn)一步計(jì)算確定.在ACC_NEW_VAR算法中，設(shè)新可行解所對應(yīng)的目標(biāo)函數(shù)值為F′，若F′rand()：若成立，則采用新的可行解F′，否則保留當(dāng)前解F，這里tempk表示當(dāng)前迭代第k次時(shí)的退火溫度.下面給出ACC_NEW_VAR 算法的執(zhí)行過程：

算法3. ACC_NEW_VAR算法.

輸入：任務(wù)處理位置集LOC、電壓變化率集RATIO、任務(wù)執(zhí)行順序集ORDER、更新后的任務(wù)處理位置集LOC′、電壓比例RATIO′、新任務(wù)順序ORDER′;

輸出：True或False.

令LOC,RATIO,ORDER所對應(yīng)的當(dāng)前目標(biāo)函數(shù)值為F;

根據(jù)LOC′,RATIO′,ORDER′計(jì)算新的目標(biāo)函數(shù)值F′;

ΔFF′-F;

IF(ΔF>0)

IF(e(F-F′)tempk≤rand())

RETURN False;

ENDIF

ENDIF

RETURN True.

3.5 算法流程

SA-DVSA算法是基于迭代求解策略的一種隨機(jī)尋優(yōu)算法，它從一個(gè)較高的初始溫度開始，在舊解基礎(chǔ)上隨機(jī)改變某個(gè)任務(wù)執(zhí)行的位置和電壓，并在滿足任務(wù)執(zhí)行關(guān)系的情況下，隨機(jī)交換2個(gè)任務(wù)的順序，伴隨溫度的不斷下降重復(fù)抽樣過程，直至得到問題的優(yōu)化解，算法主要分以下4步： 1)計(jì)算得到每個(gè)任務(wù)在各個(gè)移動(dòng)設(shè)備處理器上電壓變化率的取值范圍；2)初始化可行解，計(jì)算得到適應(yīng)度函數(shù)值F，并作為當(dāng)前最優(yōu)值；3)根據(jù)當(dāng)前變量值隨機(jī)得到新的變量值，計(jì)算新變量值對應(yīng)的適應(yīng)度函數(shù)值F′，判斷是否接受；4)在同一溫度下求解并取舍新變量若干次，之后進(jìn)行退溫操作tempi+1=λ×tempi(λ為溫度下降率)，直至溫度小于給定值閾值β.基于模擬退火算法的工作流任務(wù)調(diào)度SA-DVSA算法執(zhí)行過程如下：

算法4. SA-DVSA 算法.

輸入：工作流圖G=V,E、任務(wù)數(shù)N、移動(dòng)設(shè)備的處理器數(shù)M、任務(wù)在云端運(yùn)行時(shí)間集TC={tc(vi)}、任務(wù)在云端運(yùn)行能耗集EC={ec(vi)}、任務(wù)在移動(dòng)設(shè)備的運(yùn)行時(shí)間集TMK={tmk(vi,k)};任務(wù)在移動(dòng)設(shè)備運(yùn)行的能耗集EMK={emk(vi,k)}、截止時(shí)間TL;

調(diào)用算法INIT_VAR(N,M,TC,EC,TMK,EMK,TL);

tempnum×N×M;*初始化溫度,num為同一溫度下求解并取舍新變量的次數(shù)*

F*+∞,LOC*?,ORD*?,RATIO*?;

WHILEtemp>βdo

FORi=1 tonumDO

調(diào)用算法CHANGE_VAR(LOC,RATIO,ORDER)，獲取新解LOC′,RATIO′,ORDER′;

IF(ACC_NEW_VAR(LOC,RATIO,ORDER,LOC′,RATIO′,ORDER′)= True)

LOC=LOC′,RATIO=RATIO′,ORDER=ORDER′;

根據(jù)式(5)計(jì)算得到總能耗ETotal;

根據(jù)式(8)計(jì)算得到任務(wù)總完成時(shí)間TTotal;

根據(jù)式(9)計(jì)算目標(biāo)函數(shù)值F；

ENDIF

IF(F

F*F,LOC*LOC,RATIO*RATIO,ORDER*ORDER;

ENDIF

ENDFOR

temptemp×λ;

ENDWHILE

RETURNLOC*,RATIO*,ORDER*.

現(xiàn)在分析一下該算法的時(shí)間復(fù)雜度.SA-DVSA算法外循環(huán)的迭代次數(shù)為logλ(β(num×N×M))(其中λ代表溫度下降率，β表示最終溫度，N表示任務(wù)總數(shù)，M表示移動(dòng)設(shè)備的處理器總數(shù))，時(shí)間復(fù)雜度約為O(logλ(M×N))且M

4 實(shí) 驗(yàn)

本文實(shí)驗(yàn)主要是基于2.1節(jié)中的工作流圖示例(如圖2所示)和隨機(jī)產(chǎn)生的工作流圖來與文獻(xiàn)[18]中已有的DVFS算法，及沒有采用DVFS技術(shù)的MCC-SA算法進(jìn)行對比實(shí)驗(yàn)來得出結(jié)論，進(jìn)而分析和評價(jià)本文所提出的SA-DVSA算法的效率.實(shí)驗(yàn)采用的仿真工具為MATLAB R2014a，計(jì)算環(huán)境為：Intel?CoreTMi7-4790 CPU@3.60 GHz，內(nèi)存8 GB，運(yùn)行在64位Windows7系統(tǒng)中.

由于文獻(xiàn)[18]中的動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)用到的是固定參數(shù)值，這樣不利于尋找一個(gè)最優(yōu)的參數(shù)從而使得可行解空間利用率達(dá)到最大，所以我們設(shè)計(jì)SA-DVSA算法時(shí)從目標(biāo)函數(shù)中迭代尋找較優(yōu)參數(shù)，這樣以滿足能耗與時(shí)間的多目標(biāo)優(yōu)化問題.在適應(yīng)度函數(shù)F=α×TTotal+(1-α)×ETotal中，α為權(quán)重因子，α取值范圍為0～1，為了得到α的有效取值，在實(shí)驗(yàn)時(shí)，我們以內(nèi)核數(shù)量為3、隨機(jī)生成的10個(gè)任務(wù)關(guān)系圖為實(shí)驗(yàn)對象，得出α在不同取值時(shí)所對應(yīng)的能耗和完成時(shí)間，結(jié)果如圖4所示.

Fig. 4 Values of weight α圖4 權(quán)重因子α的實(shí)驗(yàn)圖

從圖4可以看出，當(dāng)α=0時(shí)，即只考慮優(yōu)化時(shí)間，不考慮能耗問題，這時(shí)任務(wù)的完成時(shí)間最短，能耗最大;當(dāng)α=0.3時(shí)，能耗明顯減少，并且之后基本趨于穩(wěn)定，此時(shí)任務(wù)完成時(shí)間相對于α=0時(shí)有所增加，但增值不是很多，α在0.3～0.7這段值之間，能耗和時(shí)間都基本趨于穩(wěn)定;當(dāng)α=1時(shí)，此時(shí)能源消耗最少，但任務(wù)完成時(shí)間劇增.因此，α的有效取值范圍在0.3～0.7之間，最優(yōu)取值為0.35，在后面的實(shí)驗(yàn)中α的取值都為0.35.

使用SA-DVSA算法進(jìn)行任務(wù)調(diào)度實(shí)驗(yàn)時(shí)，算法過程中的迭代次數(shù)性能圖如圖5所示.

從圖5中可以看出，在最開始迭代的時(shí)候，時(shí)間和能耗的波動(dòng)都比較大，但整體的趨勢是降低的，當(dāng)次數(shù)迭代到800左右時(shí)2個(gè)值都逐漸趨于平穩(wěn)，當(dāng)次數(shù)達(dá)到1 100時(shí)2個(gè)值都達(dá)到了最優(yōu)解.

Fig. 5 Number of iterations圖5 實(shí)驗(yàn)迭代次數(shù)圖

下面基于2.1節(jié)中所給的工作流圖來測試3種算法的調(diào)度結(jié)果，整個(gè)應(yīng)用程序的總完成時(shí)間不能超過限制時(shí)間30 s(即TL≤32 s).移動(dòng)設(shè)備有3個(gè)處理器，每個(gè)處理器在最大電壓頻率下能耗分別為P1=1J,P2=2J,P3=4J.DVFS算法、MCC-SA算法和SA-DVSA算法調(diào)度結(jié)果分別如圖6～8所示.

Fig. 6 Scheduling under DVFS algorithm圖6 DVFS算法調(diào)度分配結(jié)果

圖6是用DVFS算法調(diào)度分配的結(jié)果，總完成時(shí)間TTotal=26 s，總能耗ETotal=23J.圖7是采用沒有加入連續(xù)動(dòng)態(tài)電壓技術(shù)的MCC-SA算法調(diào)度分配的結(jié)果，此時(shí)TTotal=26 s，ETotal=22J，該算法雖然在執(zhí)行時(shí)間上與DVFS算法的結(jié)果一樣，但是所需能耗有所減少.SA-DVSA算法調(diào)度結(jié)果如圖8所示，TTotal=23.03 s，ETotal=19.47J，對比DVFS算法、MCC-SA算法，其在總完成時(shí)間和總能耗方面的效果都更好.

Fig. 7 Scheduling under MCC-SA algorithm圖7 MCC-SA算法調(diào)度分配結(jié)果

Fig. 8 Scheduling under SA-DVSA algorithm圖8 SA-DVSA算法調(diào)度分配結(jié)果

從圖7可以看出，在MCC-SA算法中，任務(wù)8～9之間存在1 s的時(shí)間空閑，為了更好地利用這部分時(shí)間，在滿足各個(gè)任務(wù)的開始和完成時(shí)間范圍內(nèi)，我們可以通過降低電壓增加任務(wù)處理時(shí)間來降低能耗：例如在圖8中，任務(wù)3在處理器1上用最大電壓的完成時(shí)間是6 s，即在時(shí)間為11 s的時(shí)候任務(wù)3結(jié)束；任務(wù)3完成之后執(zhí)行任務(wù)7，但是任務(wù)7的開始時(shí)間是15 s，11～15 s之間存在4 s時(shí)間段的空隙，這時(shí)降低處理器電壓頻率，使得任務(wù)3的完成時(shí)間延長為14.687 s，這樣既可以降低處理器的能耗，也可以得到任務(wù)3完成時(shí)間不超過15 s的調(diào)度策略，顯然這種任務(wù)調(diào)度策略是更加優(yōu)化的.

綜上所述，可以看出本文提出的SA-DVSA算法無論是在完成時(shí)間上還是在能源消耗上都比DVFS算法及MCC-SA算法都要更好.

為了進(jìn)一步證明本文算法的有效性，下面將通過隨機(jī)產(chǎn)生的具有50～100個(gè)不同任務(wù)節(jié)點(diǎn)的工作流圖來進(jìn)行對比實(shí)驗(yàn)(移動(dòng)設(shè)備的處理器數(shù)M=3).3種算法各自任務(wù)完成時(shí)間和能源消耗情況如圖9所示：

Fig. 9 Energy consumption and completed time with number of tasks changing where M=3圖9 任務(wù)數(shù)與時(shí)間能耗關(guān)系圖(M=3)

圖9(a)顯示當(dāng)任務(wù)個(gè)數(shù)變化時(shí)3種算法下各自的移動(dòng)設(shè)備能耗,圖9(b)表示3種算法在任務(wù)個(gè)數(shù)不同時(shí)與任務(wù)完成時(shí)間的關(guān)系.從圖9中可以觀察到，SA-DVSA算法無論是在任務(wù)完成時(shí)間上還是能耗上都比DVFS算法和MCC-SA算法要好.隨著任務(wù)節(jié)點(diǎn)個(gè)數(shù)的增加，任務(wù)完成時(shí)間和能耗都隨之增加，但是節(jié)點(diǎn)個(gè)數(shù)增加到一定數(shù)量之后，SA-DVSA算法的性能明顯優(yōu)于DVFS算法和MCC-SA算法，所以，SA-DVSA算法在大規(guī)模的任務(wù)節(jié)點(diǎn)數(shù)中有更好的優(yōu)勢.

在圖10的實(shí)驗(yàn)中，我們將移動(dòng)設(shè)備的處理器數(shù)設(shè)為M=6，每個(gè)處理器在最大電壓頻率下能耗分別為P1=1J，P2=2J，P3=4J，P4=8J，P5=16J，P6=32J.從圖10中可以得出和圖9中相似的結(jié)論.此外，從圖9和圖10中可以觀察到，當(dāng)移動(dòng)設(shè)備的處理器數(shù)M增加時(shí)，任務(wù)完成時(shí)間相應(yīng)減少了，但是能耗卻增加了，這是因?yàn)楫?dāng)移動(dòng)設(shè)備有了更強(qiáng)計(jì)算能力的處理器，許多任務(wù)將被調(diào)度到上面執(zhí)行，這樣工作流任務(wù)執(zhí)行所需的總能耗也將隨之增多.

Fig. 10 Energy consumption and completed time with number of tasks changing where M=6圖10 任務(wù)數(shù)與時(shí)間能耗關(guān)系圖(M=6)

5 結(jié) 論

任務(wù)調(diào)度是工作流系統(tǒng)管理中的重要研究內(nèi)容，在移動(dòng)云計(jì)算環(huán)境中進(jìn)行任務(wù)調(diào)度時(shí)，一個(gè)重要問題就是如何制定調(diào)度策略使任務(wù)完成時(shí)間和能耗達(dá)到最小.以往的研究中主要都集中在如何降低能耗的問題上，對能耗和時(shí)間的聯(lián)合優(yōu)化研究得很少.本文所提的SA-DVSA算法對這2個(gè)目標(biāo)進(jìn)行聯(lián)合優(yōu)化，并通過實(shí)驗(yàn)驗(yàn)證了該方法比文獻(xiàn)中的DVFS算法在任務(wù)完成時(shí)間以及能耗問題都有了進(jìn)步.在今后的工作中，本文將嘗試設(shè)計(jì)其他啟發(fā)式算法與模擬退火算法相結(jié)合來解決移動(dòng)云計(jì)算的任務(wù)調(diào)度問題，并綜合考慮能耗、時(shí)間、安全等多方面因素[21]，這些有待于進(jìn)一步的努力.

[1]Chen Shuang, Wang Yanzhi, Pedram M. A semi-markovian decision process based control method for offloading tasks from mobile devices to the cloud[C]Proc of the 2013 Int Conf on Global Communications. Piscataway, NJ: IEEE, 2013: 2885-2890

[2]Deng Shuiguang, Huang Longtao, Taheri J, et al. Computation offloading for service workflow in mobile cloud computing[J]. IEEE Trans on Parallel and Distributed Systems, 2015, 26(2): 3317-3329

[3]Khan A, Ahirwar K. Mobile cloud computing as a future of mobile multimedia database[J]. International Journal of Computer Science and Communication, 2011, 2(1): 219-221

[4]Miettinen A P, Nurminen J K. Energy efficiency of mobile clients in cloud computing[C]Proc of the USENIX Int Conf on Hot Topics in Cloud Computing. Berkeley, CA: USENIX Association, 2010: 14-21

[5]Mavroeidakos T, Michalas A, Vergados D. Security architecture based on defense in depth for cloud computing environment[C]Proc of the 2016 IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2016: 334-339

[6]Sarbazi H, Zomaya A. Large Scale Network-Centric Distributed Systems[M]. Piscataway, NJ: IEEE, 2014

[7]Singh B, Dhawan S, Arora A, et al. A view of cloud computing[J]. Communications of the ACM, 2013, 53(4): 50-58

[8]Patra B, Roy S, Chowdhury C. A framework for energy efficient and flexible offloading scheme for handheld devices[C]Proc of the IEEE Int Conf on Advanced Networks and Telecommunications Systems. Piscataway, NJ: IEEE, 2015: 1-6

[9]Kumar K, Liu Jibang, Lu Yunhang, et al. A survey of computation offloading for mobile systems[J]. Mobile Networks and Applications, 2013, 18(1): 129-140

[10]Balamurugan M, Akila V. Effective processor selection on heterogeneous computing[C]Proc of the 2016 Int Conf on Science Technology Engineering and Management. Piscataway, NJ: IEEE, 2016: 13-16

[11]Feng Bailong, Gao Jing. Distributed parallel Needleman-Wunsch algorithm on heterogeneous cluster system[C]Proc of the 2015 Int Conf on Network and Information Systems for Computers. Piscataway, NJ: IEEE, 2015: 12-18

[12]Ra M, Sheth A, Mummert L, et al. Odessa: Enabling interactive perception applications on mobile devices[C]Proc of the 9th Int Conf on Mobile Systems, Applications, and Services. New York: ACM, 2011: 43-56

[13]Yang Lei, Cao Jiannong, Yuan Yin, et al. A framework for partitioning and execution of data stream applications in mobile cloud computing[C]Proc of the 5th Int Conf on Cloud Computing. Piscataway, NJ: IEEE, 2012: 794-802

[14]Terzopoulos G, Karatza H. Dynamic voltage scaling scheduling on power-aware clusters under power constraints[C]Proc of the 17th Int Conf on Distributed Simulation and Real Time Applications. New York: ACM, 2013: 72-78

[15]Saravanan S, Venkatachalam V. Advance MapReduce task scheduling algorithm using mobile cloud multimedia services architecture[C]Proc of the 6th Int Conf on Advanced Computing. Piscataway, NJ: IEEE, 2014: 21-25

[16]Deshmukh N, Deorankar A. Minimizing energy consumption in transmission efficient wireless sensor network[C]Proc of the Int Conf on Advances in Electrical, Electronics, Information, Communication and Bio-Informatics. Piscataway, NJ: IEEE, 2016: 475-479

[17]Kumar K, Lu Yunhang. Cloud computing for mobile users can offloading computation save energy[J]. Computer, 2010, 43(4): 51-56

[18]Lin Xue, Wang Yanzhi, Xie Qing, et al. Task scheduling with dynamic voltage and frequency scaling for energy minimization in the mobile cloud computing environment[J]. IEEE Trans on Services Computing, 2015, 8(2): 175-186

[19]Davis L. Genetic Algorithms and Simulated Annealing: An Overview[M]. San Francisco, CA: Morgan Kaufmann, 1987

[20]Fleming P, Pashkevich A, Fleming P, et al. Computer aided control system design using a multiobjective optimization approach[C]Proc of the Int Conf on Control. Piscataway, NJ: IEEE, 1985: 17-26

[21]Han Rui, Liu Yingbo, Wen Lijie, et al. A probabilistic approach to analyze and adjust time constraints in workflow management system[J]. Journal of Computer Research and Development, 2010, 47(1): 157-163 (in Chinese)(韓銳, 劉英博, 聞立杰, 等. 工作流管理系統(tǒng)中一種概率性分析和調(diào)整時(shí)間約束的方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2010,47(1): 157-163)

Hu Haiyang, born in 1977. PhD and professor. His main research interests include workflow system and parallel computing.

Liu Runhua, born in 1990. Master. Her main research interests include workflow system and business process management.

Hu Hua, born in 1964. Professor and PhD supervisor. His main research interests include workflow system and database theory.

Multi-Objective Optimization for Task Scheduling in Mobile Cloud Computing

Hu Haiyang, Liu Runhua, and Hu Hua

(CollegeofComputerScience,HangzhouDianziUniversity,Hangzhou310018) (KeyLaboratoryofComplexSystemsModelingandSimulation(HangzhouDianziUniversity),MinistryofEducation,Hangzhou310018)

Mobile cloud computing provides effective help for mobile users to migrate their workflow tasks to cloud servers for executing due to the mobile device’s limited hardware capability and battery energy carried. When scheduling workflow tasks between mobile devices and cloud servers, it needs to consider both the energy consumed by the mobile device and the total amount of time needed for the workflow application. Traditional methods for scheduling workflow tasks in mobile cloud computing usually address only one of two issues: saving energy consumption or minimizing the time needed. They fail to provide methods for jointly optimizing the time and energy consumption at the same time. Based on the relations of workflow tasks, the time needed in the workflow application is computed due to the tasks scheduling between the cloud servers and the mobile devices that use the technique of dynamic voltage and frequency scaling. The energy consumption for executing tasks on the cloud server and mobile devices are modeled and computed. The scheduling scheme and objective function for jointly optimizing the time needed and energy consumption are proposed. Algorithms based on the simulated annealing are designed for the mobile devices. Their time complexities are analyzed. Extensive experiments are conducted for comparing the proposed methods with other research works, and the experimental results demonstrate the correctness and effectiveness of our approaches.

mobile cloud computing; workflow; task scheduling; simulated annealing; multi-objective optimization

2016-10-24；

2017-02-06

國家自然科學(xué)基金項(xiàng)目(61572162,61272188);南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目(KFKT2014B15);江蘇省自然科學(xué)基金項(xiàng)目(BK20131277) This work was supported by the National Natural Science Foundation of China(61572162, 61272188), the Foundation of State Key Laboratory for Novel Software Technology of Nanjing University (KFKT2014B15), and the Natural Science Foundation of Jiangsu Province of China(BK20131277).

TP311