胡海洋 劉潤華 胡 華

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

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

胡海洋 劉潤華 胡 華

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

(huhaiyang@hdu.edu.cn)

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

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

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

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

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

1 相關(guān)工作

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

在縮短工作流應(yīng)用的總完成時間方面，文獻(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ā)了一個運行系統(tǒng)，它能自適應(yīng)地為移動交互感知應(yīng)用程序進(jìn)行任務(wù)卸載和并行執(zhí)行，從而減少應(yīng)用程序的完成時間.文獻(xiàn)[13]提出了一種方法，可在移動設(shè)備和云環(huán)境中的最大吞吐量之間，對數(shù)據(jù)流應(yīng)用的任務(wù)分配問題進(jìn)行優(yōu)化.

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

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

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

2 移動云計算任務(wù)調(diào)度模型

2.1 問題描述和基本框架

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

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

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

一個工作流由N個任務(wù)節(jié)點組成，一般情況下，N不會超過100，比如在計算機(jī)視覺應(yīng)用程序中，N的范圍就是10～30.在給定的工作流任務(wù)圖中，沒有任何前驅(qū)節(jié)點的任務(wù)節(jié)點為開始任務(wù)，沒有任何后續(xù)節(jié)點的任務(wù)節(jié)點為結(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中各個任務(wù)在移動設(shè)備處理器以及在云端服務(wù)器的處理時間如表1所示:

Table 1 Completed Time of Each Task

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

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

Table 2 Definitions of Notations

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

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

(1)

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

(2)

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

(3)

2.3 能源消耗

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

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

(4)

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

(5)

3 算法設(shè)計

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

3.1 算法框架

基于物理中固體物質(zhì)的退火過程與一般優(yōu)化問題之間具有一定的相似性，模擬退火算法[19-20]已被證明是一種適合求解大規(guī)模組合優(yōu)化問題的通用且有效的近似算法.對于組合優(yōu)化問題來說,解空間的每一點都代表一個具有不同目標(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è)備的能源消耗這2方面的加權(quán)值作為適應(yīng)度目標(biāo)函數(shù)，則可將本文中的移動云計算環(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í)行時刻為startT(vi),則由式(3)可得其實際完成時間為

(6)

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

(7)

這樣整個工作流的總完成時間可以表示為

(8)

則根據(jù)式(5)和式(8),執(zhí)行時間與能耗的聯(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)計算每個任務(wù)的最小電壓變化率,再在此基礎(chǔ)上隨機(jī)產(chǎn)生任務(wù)的電壓變化率集RATIO={rat(vi)}，接著初始化N個任務(wù)的順序為ORDER={ord(vi)|ord(vi)=i,1≤i≤N},最后計算總能耗ETotal、運行時間TTotal以及目標(biāo)函數(shù)值F.下面給出INIT_VAR算法的執(zhí)行過程：

算法1. INIT_VAR算法.

輸入：任務(wù)數(shù)N、移動設(shè)備的處理器數(shù)M、任務(wù)在云端服務(wù)器運行時間集TC={tc(vi)}、任務(wù)遷移到云端服務(wù)器運行時移動設(shè)備能耗集EC={ec(vi)}、任務(wù)在移動設(shè)備的運行時間集TMK={tmk(vi,k)};任務(wù)在移動設(shè)備運行的能耗集EMK={emk(vi,k)}、截止時間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)計算ratmin(vi)；

IF(loc(vi)≠M+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)計算目標(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可通過如下過程計算得到：找出vi在k處的全部前驅(qū)任務(wù)中的最大執(zhí)行次序值x1，找到vi在k處的全部后續(xù)任務(wù)中的最小執(zhí)行次序值x2，則R1區(qū)間為(x1，x2).在區(qū)間R1上隨機(jī)選擇vi的某個執(zhí)行次列位s1；然后遍歷R1中所有其他執(zhí)行次列上的當(dāng)前任務(wù)，對每個任務(wù)vj，分析其在k處上的可執(zhí)行的次序區(qū)間R2，分析R2與R1的交集Rcross，若Rcross≠?，則表示vi與vj可互選，則將vj的執(zhí)行次序位加入集合RA中，最終從可互換的執(zhí)行序列集RA中隨機(jī)選擇一個序列位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+1)

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

ELSE

rat(vi)1.0;

ENDIF

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

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

FOR eachs2∈R1DO

IF(s2≠s1)

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

計算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)一步計算確定.在ACC_NEW_VAR算法中，設(shè)新可行解所對應(yīng)的目標(biāo)函數(shù)值為F′，若F′rand()：若成立，則采用新的可行解F′，否則保留當(dāng)前解F，這里tempk表示當(dāng)前迭代第k次時的退火溫度.下面給出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′計算新的目標(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)算法，它從一個較高的初始溫度開始，在舊解基礎(chǔ)上隨機(jī)改變某個任務(wù)執(zhí)行的位置和電壓，并在滿足任務(wù)執(zhí)行關(guān)系的情況下，隨機(jī)交換2個任務(wù)的順序，伴隨溫度的不斷下降重復(fù)抽樣過程，直至得到問題的優(yōu)化解，算法主要分以下4步： 1)計算得到每個任務(wù)在各個移動設(shè)備處理器上電壓變化率的取值范圍；2)初始化可行解，計算得到適應(yīng)度函數(shù)值F，并作為當(dāng)前最優(yōu)值；3)根據(jù)當(dāng)前變量值隨機(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、移動設(shè)備的處理器數(shù)M、任務(wù)在云端運行時間集TC={tc(vi)}、任務(wù)在云端運行能耗集EC={ec(vi)}、任務(wù)在移動設(shè)備的運行時間集TMK={tmk(vi,k)};任務(wù)在移動設(shè)備運行的能耗集EMK={emk(vi,k)}、截止時間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)計算得到總能耗ETotal;

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

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

ENDIF

IF(F

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

ENDIF

ENDFOR

temptemp×λ;

ENDWHILE

RETURNLOC*,RATIO*,ORDER*.

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

4 實 驗

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

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

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

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

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

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

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

下面基于2.1節(jié)中所給的工作流圖來測試3種算法的調(diào)度結(jié)果，整個應(yīng)用程序的總完成時間不能超過限制時間30 s(即TL≤32 s).移動設(shè)備有3個處理器，每個處理器在最大電壓頻率下能耗分別為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é)果，總完成時間TTotal=26 s，總能耗ETotal=23J.圖7是采用沒有加入連續(xù)動態(tài)電壓技術(shù)的MCC-SA算法調(diào)度分配的結(jié)果，此時TTotal=26 s，ETotal=22J，該算法雖然在執(zhí)行時間上與DVFS算法的結(jié)果一樣，但是所需能耗有所減少.SA-DVSA算法調(diào)度結(jié)果如圖8所示，TTotal=23.03 s，ETotal=19.47J，對比DVFS算法、MCC-SA算法，其在總完成時間和總能耗方面的效果都更好.

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

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

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

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

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

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

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

5 結(jié) 論

任務(wù)調(diào)度是工作流系統(tǒng)管理中的重要研究內(nèi)容，在移動云計算環(huán)境中進(jìn)行任務(wù)調(diào)度時，一個重要問題就是如何制定調(diào)度策略使任務(wù)完成時間和能耗達(dá)到最小.以往的研究中主要都集中在如何降低能耗的問題上，對能耗和時間的聯(lián)合優(yōu)化研究得很少.本文所提的SA-DVSA算法對這2個目標(biāo)進(jìn)行聯(lián)合優(yōu)化，并通過實驗驗證了該方法比文獻(xiàn)中的DVFS算法在任務(wù)完成時間以及能耗問題都有了進(jìn)步.在今后的工作中，本文將嘗試設(shè)計其他啟發(fā)式算法與模擬退火算法相結(jié)合來解決移動云計算的任務(wù)調(diào)度問題，并綜合考慮能耗、時間、安全等多方面因素[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)整時間約束的方法[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é)基金項目(61572162,61272188);南京大學(xué)計算機(jī)軟件新技術(shù)國家重點實驗室開放基金項目(KFKT2014B15);江蘇省自然科學(xué)基金項目(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