薛慶水 李鳳英

1(上海應(yīng)用技術(shù)大學(xué)計算機(jī)科學(xué)與信息工程學(xué)院 上海 201418)2(上海交通大學(xué)繼續(xù)教育學(xué)院 上海 200240)

0 引 言

由于無線移動通信技術(shù)的發(fā)展，諸如智能手機(jī)的移動設(shè)備在人們的日常生活中變得越來越普及。這些配置有GPS、Wi- Fi、相機(jī)、傳感器以及高性能計算和存儲能力的設(shè)備可以執(zhí)行的應(yīng)用也越來越豐富[1]。而隨著更加復(fù)雜、計算量更大的應(yīng)用類型(如圖像處理、在線游戲、實(shí)時監(jiān)測及社交網(wǎng)絡(luò)等)部署至移動設(shè)備端執(zhí)行，對移動設(shè)備處理能力的要求也越來越高[2]。尤其，對于資源饑餓型和高能耗的復(fù)雜應(yīng)用需求，移動設(shè)備的本地計算能力和電池容量已無法滿足。移動云計算環(huán)境中的任務(wù)遷移技術(shù)成為解決以上問題的一種有效手段[3-4]。該技術(shù)可以將原本執(zhí)行于本地設(shè)備的高能耗應(yīng)用通過無線訪問的方式遷移至功能更強(qiáng)大資源更豐富的云端服務(wù)器上執(zhí)行。但如何在考慮任務(wù)執(zhí)行效率和執(zhí)行帶來的能耗的情況下作出最優(yōu)的遷移決策是必須解決的問題。

相關(guān)研究中，MAUI[5]是一種移動云中改進(jìn)能耗的遷移算法，算法利用整型線性規(guī)化方法求解最優(yōu)遷移決策，但僅僅考慮了能耗優(yōu)化問題。ThinkAir[6]是一種按需的資源分配和卸載模型，所設(shè)計的算法通過一種全局平均值方法估算任務(wù)的執(zhí)行時間，并以此預(yù)測后續(xù)任務(wù)的執(zhí)行時間，僅從能耗方面考慮了遷移決策問題。然而，由于傳輸延時和云端負(fù)載波動的存在，該預(yù)測方法無法適應(yīng)動態(tài)的應(yīng)用行為。文獻(xiàn)[7]設(shè)計了一種上下文感知的遷移決策方法，實(shí)現(xiàn)了移動設(shè)備位置確定狀況下的遷移決策，但該方法仍然忽略了網(wǎng)絡(luò)條件的不確定性，在用戶提交任務(wù)的位置和網(wǎng)絡(luò)帶寬發(fā)生變化時，遷移決策效率很低。

遷移決策中另一個重要問題是任務(wù)執(zhí)行時間的估算[8]。先前的工作多集中在利用歷史數(shù)據(jù)和基于時間均值的預(yù)測方法，然而，用戶應(yīng)用類型的不同、動態(tài)的應(yīng)用行為均使得這類方法無法得到最優(yōu)的預(yù)測準(zhǔn)確性。本文將利用統(tǒng)計回歸的方法估算任務(wù)執(zhí)行時間，捕捉遷移環(huán)境中的動態(tài)行為因素，基于此時間更好地作出任務(wù)遷移決策。

是否進(jìn)行任務(wù)遷移決策需要綜合考慮，任務(wù)在云端執(zhí)行的代價不僅取決于任務(wù)的執(zhí)行時間，還需要考慮其他遷移代價，如當(dāng)前云端的計算負(fù)載、網(wǎng)絡(luò)帶寬條件和需要傳輸?shù)臄?shù)據(jù)量等。以上因素使得任務(wù)執(zhí)行的時間和能耗是非線性相關(guān)的。本文將以更加準(zhǔn)確的任務(wù)執(zhí)行時間預(yù)測方法，在執(zhí)行時間和能耗兩個方面更加均衡地考慮是否進(jìn)行任務(wù)遷移，并對影響遷移決策的重要因素作出討論，最終設(shè)計出在執(zhí)行時間和能耗上作出均衡優(yōu)化的任務(wù)遷移決策。

1 任務(wù)遷移決策問題

1.1 遷移決策模型

任務(wù)遷移決策控制參數(shù)包括：計算時間代價、能量需求、云端服務(wù)器的速率以及數(shù)據(jù)傳輸時間，且這些參數(shù)是非線性相關(guān)的。例如：遠(yuǎn)程云端執(zhí)行帶來的時間代價的節(jié)省并不必會由于云端服務(wù)器的速度而增加或減少，這取決于網(wǎng)絡(luò)性能，即帶寬。因此，控制遷移決策的參數(shù)是非線性相關(guān)的，利用線性最優(yōu)化技術(shù)并不適用于該場景，本文將利用Lagrange乘子法[9]的非線性最優(yōu)化方法對之求解。

對于任務(wù)遷移決策，首先需求計算任務(wù)在云端執(zhí)行時的時間代價ft，表示為：

ft(tc)=tc+D/B

(1)

式中：tc為任務(wù)在云端服務(wù)器上的執(zhí)行時間，D為本地設(shè)備與云端服務(wù)器間的數(shù)據(jù)傳輸量，B為可用帶寬。若任務(wù)在本地設(shè)備上的執(zhí)行時間為tm，云端服務(wù)器的處理速率為本地設(shè)備的Sf倍，則任務(wù)在云端服務(wù)器上的執(zhí)行時間計算為tc=tm/Sf。因此，以上代價函數(shù)可重寫為：

ft(tm)=tm/Sf+D/B

(2)

利用Lagrange乘子法計算下式得到的任務(wù)遷移帶來的時間節(jié)省的最小值和最大值：

Ft(tm)=tm-tm/Sf-D/B

(3)

約束條件為：

ft(tm)

(4)

tm/Sf+D/B

(5)

tm>0

(6)

D>0

(7)

Sf≥0

(8)

式(4)表明本地設(shè)備上任務(wù)的執(zhí)行代價需大于云端執(zhí)行代價，該約束可以確保任務(wù)遷移時的執(zhí)行時間可以落入時間代價函數(shù)的最小值與最大值之間，以節(jié)省計算時間；式(5)表明最大延時約束，以確保任務(wù)遷移到云端執(zhí)行的響應(yīng)時間不超過最大延時；式(6)和式(7)是時間的非負(fù)約束；式(8)確保云端服務(wù)器處理速率快于本地設(shè)備。利用Lagrange乘子法求解代價函數(shù)的最小值和最大值，式(4)和式(5)需要合并至微分等式中。則Lagrange乘子法的KKT等式可重寫為：

(9)

λ1×[tm-(tm/Sf+D/B)]=0

(10)

λ2×[Dmax-(tm/Sf+D/B)]=0

(11)

ft(tm)

(12)

tm/Sf+D/B

(13)

λ1,λ2≥0

(14)

Fe(tm)=pm×tm-pi×tm/Sf-pt×D/B

(15)

式中：pm為本地設(shè)備執(zhí)行任務(wù)的平均功耗，pi為本地設(shè)備空閑時的平均功耗，pt為本地設(shè)備的平均發(fā)送與接收功耗。基于代價函數(shù)最大值與最小值的任務(wù)遷移決策過程作如下討論。

1.2 遷移決策討論

計算時間和能量代價函數(shù)的最大值和最小值，本節(jié)引入兩種遷移決策類型：確定型遷移決策和均衡型遷移決策：

1) 確定型遷移決策。該策略中，是否進(jìn)行任務(wù)遷移是確定的，即遷移任務(wù)可以確定的同時節(jié)省時間和能耗，或兩者都不能節(jié)省。若可以同時節(jié)省時間和能耗，則進(jìn)行遷移，否則，不遷移。

2) 均衡型遷移決策。該策略中，進(jìn)行任務(wù)遷移只能優(yōu)化一個指標(biāo)(時間或能耗)，另一指標(biāo)會相應(yīng)降低。此時，需要引入均衡指標(biāo)，該指標(biāo)的定義和計算方法可參見2.1節(jié)。

圖1顯示了基于時間代價函數(shù)和能量代價函數(shù)最大值和最小值的場景下的確定遷移區(qū)域和均衡遷移區(qū)域。(a)中，兩個代價函數(shù)最值區(qū)域是完全包含在內(nèi)的，即全覆蓋，這表明屬于該區(qū)域的執(zhí)行時間可以通過任務(wù)遷移同時節(jié)省執(zhí)行時間和執(zhí)行能耗。圖中的非全覆蓋區(qū)域中進(jìn)行任務(wù)遷移僅將節(jié)省執(zhí)行時間或能耗(圖中為節(jié)省能耗)。(b)中，時間代價和能耗代價是局部覆蓋的。左側(cè)的均衡區(qū)域表明可以進(jìn)行能量節(jié)省，但執(zhí)行時間會增加，反之亦然。類似地，(c)表示的場景是僅能優(yōu)化時間或能量一個指標(biāo)，因?yàn)闀r間代價和能量代價無完全覆蓋區(qū)域。同時，在所有情形中，最值以外的區(qū)域均無法優(yōu)化時間和能量指標(biāo)。

(a) 全覆蓋 (b) 局部覆蓋 (c) 末覆蓋圖1 決策區(qū)域

當(dāng)任務(wù)需要開始執(zhí)行時，需要決定其期望時間，并將之與代價函數(shù)中tm的最大值與最小值進(jìn)行比較，根據(jù)該值在圖1中所處的區(qū)域作出遷移決策。

2 任務(wù)執(zhí)行時間估算

對于計算密集型任而言，任務(wù)是否進(jìn)行遷移，與任務(wù)在本地設(shè)備上的執(zhí)行時間tm估算相關(guān)。算法將利用統(tǒng)計回歸方法[10]估算tm。將任務(wù)的執(zhí)行時間tm建立為一個隨機(jī)變量模型，表示為：

tm=m(X)+ζ

(16)

式中：m(X)為模型參數(shù)的函數(shù)，如用戶輸入?yún)?shù)等，ζ為影響任務(wù)執(zhí)行時間的未建模參數(shù)的殘數(shù)因子。該模型中，預(yù)測任務(wù)執(zhí)行時間的目標(biāo)是在給定參數(shù)矢量X的情況下獲得m(X)和ζ的估算。

(17)

式中：Wi(X)為權(quán)重函數(shù)，ti為執(zhí)行時間的第i個觀測值。權(quán)重函數(shù)的設(shè)計思路為：越接近于當(dāng)前條件的觀測值分配越高權(quán)重，反之亦然。同時，統(tǒng)計回歸法利用下式計算ζ的估算值：

(18)

圖2顯示了在CADA模型下利用統(tǒng)計回歸法得到的任務(wù)執(zhí)行時間的估算值的預(yù)測性能。可以看到，在用戶任務(wù)輸入和網(wǎng)絡(luò)條件動態(tài)變化的情況下，平均執(zhí)行時間的預(yù)測方法并不能很好地捕捉到執(zhí)行時間的準(zhǔn)確性。而統(tǒng)計回歸方法可以適應(yīng)于應(yīng)用行為的動態(tài)變化，這有助于任務(wù)遷移決策的準(zhǔn)確制定。

圖2 預(yù)測準(zhǔn)確性

2.1 基于均衡性能的遷移決策

圖1表明，執(zhí)行時間tm的估算可能落入均衡區(qū)域，此時執(zhí)行時間或執(zhí)行能量可以得到節(jié)省。令G1和G2分別表示任務(wù)遷移時在時間和能量上的增益-損失比率，分別表示為：

(19)

(20)

式中：em為本地設(shè)備執(zhí)行任務(wù)時的設(shè)備能耗，定義為：

em=pm×tm

(21)

fe(tm)為任務(wù)遷移至云端執(zhí)行時能量代價，定義為：

(22)

結(jié)合以上兩個因素，均衡指標(biāo)定義為：

G=(1-α)×G1+α×G2

(23)

式中：α為權(quán)重因子，表示對于能量和時間的均衡偏好，且0≤α≤1。α值取決于移動設(shè)備的剩余能量。因此，當(dāng)移動設(shè)備的電池能量充足時，將分配最大的權(quán)重值以節(jié)省執(zhí)行時間，而隨著移動設(shè)備電量的降低，α值也將隨之降低。令Dloc表示均衡區(qū)域內(nèi)任務(wù)的執(zhí)行位置，其值的判定決策為：

(24)

式中：Gth為預(yù)定義的門限值，取決于應(yīng)用任務(wù)的QoS需求?？梢钥闯?，α和Gth兩個參數(shù)的取值決定了用戶在執(zhí)行時間和能量間的取舍與妥協(xié)。

2.2 α值的取值討論

由于能量節(jié)省的需求會隨著設(shè)備電量的降低發(fā)生變化，設(shè)置固定的α值而不考慮移動設(shè)備的剩余電量顯然是不切實(shí)際的。算法設(shè)計了一種自適應(yīng)的策略根據(jù)現(xiàn)實(shí)場景設(shè)置α值。首先，定義兩個變量b和cf，0≤b≤1表示本地設(shè)備剩余能量的占比，cf表示臨界因子，代表移動設(shè)備的剩余電量是否處于臨界狀態(tài)。例如：若移動設(shè)備剩余25%的電量，隨著即進(jìn)入臨界狀態(tài)，則臨界因子cf=0.25。臨界因子的定義方式為：

(25)

式中：β和γ表示兩個常量，β=1，γ=2。式(25)表明，若α值增加，即均衡指標(biāo)中能量因子的權(quán)重將線性增加，由于移動設(shè)備的剩余能量未處于臨界狀態(tài)時，設(shè)備電量將降低。一旦電量進(jìn)入臨界狀態(tài)，α值將隨著電量的降低而呈指數(shù)級增加，此時需要給予能量節(jié)省更高的權(quán)重。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)配置與基準(zhǔn)函數(shù)

如表1所示配置了本地設(shè)備和云端服務(wù)器兩種任務(wù)執(zhí)行環(huán)境，本地設(shè)備與云端的通信連接通過WiFi網(wǎng)絡(luò)進(jìn)行連接。仿真環(huán)境為MATLAB，執(zhí)行的目標(biāo)應(yīng)用考慮利用兩種類型：大量計算和少量數(shù)據(jù)傳輸應(yīng)用類型HCLD和大量計算和大量數(shù)據(jù)傳輸應(yīng)用類型HCHD。前者的測試應(yīng)用為N皇后問題求解，該應(yīng)用在本地設(shè)備上求解需要消耗大量時間，而數(shù)據(jù)傳輸量則較少。后者的測試應(yīng)用為面部識別應(yīng)用，該應(yīng)用以圖像作為輸入，不僅計算復(fù)雜，計算量大，且數(shù)據(jù)傳輸密集，需要遷移至云端服務(wù)器執(zhí)行。

表1 設(shè)備配置

3.2 性能指標(biāo)

1) 平均執(zhí)行時間。單個任務(wù)的執(zhí)行時間為任務(wù)提交至返回結(jié)果間的時間差，所有個體任務(wù)的執(zhí)行時間之和與任務(wù)數(shù)量之商即為平均執(zhí)行時間。

2) 平均能耗。所有個體任務(wù)的執(zhí)行能耗之和與任務(wù)數(shù)量之商即為平均能耗。

3) 預(yù)測準(zhǔn)確性。任務(wù)在執(zhí)行時間上的預(yù)測準(zhǔn)確性通過比較算法預(yù)測的任務(wù)執(zhí)行時間期望值與任務(wù)的實(shí)際執(zhí)行時間得到。若任務(wù)的預(yù)測執(zhí)行時間為tp，實(shí)際執(zhí)行時間為ta，則預(yù)測準(zhǔn)確性定義為：

(26)

4) 計算時間節(jié)省。任務(wù)在本地執(zhí)行的時間與在云端服務(wù)器上執(zhí)行時間的差值即為計算時間的節(jié)省。

3.3 實(shí)驗(yàn)結(jié)果

1) 皇后數(shù)量的影響。圖3是執(zhí)行N皇后應(yīng)用時皇后數(shù)量對于算法在平均執(zhí)行時間和能耗上的影響。圖3的左側(cè)坐標(biāo)值表明本文算法比對比算法節(jié)省了更多的計算時間，這是由于算法利用統(tǒng)計回歸考慮了用戶行為的動態(tài)性，優(yōu)于另外兩種算法的均值估算方法。

圖3 皇后數(shù)量對執(zhí)行時間和能耗的影響

圖4的左側(cè)坐標(biāo)值表明，文獻(xiàn)[6]利用的全局均值方法而不考慮動態(tài)的用戶行為和網(wǎng)絡(luò)條件，是無法適應(yīng)于動態(tài)的用戶行為的。而采用局部均值方法的文獻(xiàn)[7]考慮了設(shè)備位置，可以一定程度地在確定場景中增加預(yù)測準(zhǔn)確性。圖3的右側(cè)坐標(biāo)值是N皇后問題的能耗情況。結(jié)果表明，本文算法為移動設(shè)備節(jié)省了最多能耗，由于算法可以考慮用戶動態(tài)行為，因此更加準(zhǔn)確地預(yù)測任務(wù)執(zhí)行時間。另外，算法利用Largrange乘子優(yōu)化技術(shù)可以考慮能耗的節(jié)省，并維持QoS需求，以更好的均衡性能進(jìn)行任務(wù)遷移。個別情況下，文獻(xiàn)[7]比本文算法節(jié)省更多能耗，這表明非準(zhǔn)確的預(yù)測方法對于遷移任務(wù)決策在個別情況下也是可行的。

圖4 皇后數(shù)量對預(yù)測準(zhǔn)確性和節(jié)省時間的影響

圖4的右側(cè)坐標(biāo)值表明，一些情況下，本文算法和文獻(xiàn)[7]得到的計算時間節(jié)省是相近的，這是由于兩種算法都作了準(zhǔn)確的任務(wù)遷移決策，即若輸入應(yīng)用的皇后數(shù)量較多，兩種算法均會選擇遷移任務(wù)至云端從而節(jié)省應(yīng)用的計算時間。而文獻(xiàn)[6]以均值時間作為遷移決策的依據(jù)，導(dǎo)致任務(wù)遷移是不確定的，從而節(jié)省時間有可能沒有前兩種算法多。

2) 圖像大小的影響。圖5是執(zhí)行面部識別應(yīng)用時圖像大小對于算法在平均執(zhí)行時間和能耗上的影響?？梢钥吹?，由于通過統(tǒng)計回歸方法考慮了用戶輸入應(yīng)用的變化行為，本文算法得到的平均執(zhí)行時間是最小的。而對于能耗，像面部識別這類數(shù)據(jù)密集型應(yīng)用，其傳輸能耗在總能耗中占據(jù)極大分量。即使進(jìn)行任務(wù)遷移，傳輸能耗也必須考慮在內(nèi)。因此，遷移決策必須同步考慮傳輸時間和計算時間。由于統(tǒng)計回歸估算的任務(wù)執(zhí)行時間更加準(zhǔn)確，本文算法同樣得到了更多的能耗節(jié)省。而算法中利用均衡要素考慮，算法還同時維持了計算時間的指標(biāo)。

圖5 圖像大小對執(zhí)行時間和能耗的影響

圖6是預(yù)測準(zhǔn)確性和所節(jié)省的計算時間狀況。如前所述，均值估算方法未考慮動態(tài)變化的用戶行為和網(wǎng)絡(luò)條件，導(dǎo)致文獻(xiàn)[6]得到預(yù)測準(zhǔn)確性較差。本文算法則在所有大小圖像下均得到了90%以上的預(yù)測準(zhǔn)確性，說明本文算法具有很好的適應(yīng)性。在節(jié)省時間方面，圖像較小時，算法間的差距并不大，但圖像增大后，執(zhí)行時間的預(yù)測準(zhǔn)確性對于節(jié)省時間越來越具有影響，但本文算法始終維持較好性能表現(xiàn)。

圖6 圖像大小對預(yù)測準(zhǔn)確性和節(jié)省時間的影響

3) 網(wǎng)絡(luò)條件的影響。無線網(wǎng)絡(luò)的動態(tài)行為對于是否進(jìn)行任務(wù)遷移具有重要影響。較差的網(wǎng)絡(luò)條件會導(dǎo)致過多的數(shù)據(jù)重傳，進(jìn)而導(dǎo)致響應(yīng)時間和能耗的增加。文獻(xiàn)[7]假定任務(wù)執(zhí)行條件是不變的，包括移動設(shè)備位置的不變和任務(wù)執(zhí)行時間的不變。而本文算法則是在不斷的云端負(fù)載更新和網(wǎng)絡(luò)條件更新下進(jìn)行的，此時作出的遷移決策更有說服力。圖7的左側(cè)坐標(biāo)值是網(wǎng)絡(luò)帶寬對于執(zhí)行面部識別應(yīng)用時對計算時間節(jié)省的影響。由于面部識別需要大量傳輸數(shù)據(jù)至云端，網(wǎng)絡(luò)帶寬的可用性對于是否進(jìn)行任務(wù)遷移具有關(guān)鍵影響。可以看到，圖像越大，節(jié)省時間越多，而在網(wǎng)絡(luò)條件較差時(網(wǎng)絡(luò)帶寬較小)，圖像大小對于節(jié)省時間的影響也越大。網(wǎng)絡(luò)條件變好后，越大的圖像越能節(jié)省時間，這是由于此時在傳輸過程中的時間變少，而云端執(zhí)行任務(wù)比本地設(shè)備執(zhí)行更快。圖7的右側(cè)坐標(biāo)值是網(wǎng)絡(luò)帶寬對于執(zhí)行N皇后應(yīng)用時對計算時間節(jié)省的影響?？梢钥吹剑瑘?zhí)行該類應(yīng)用在節(jié)省時間上的影響比面部識別應(yīng)用要小，由于此應(yīng)用的數(shù)據(jù)傳輸量更小。只要網(wǎng)絡(luò)帶寬條件不是太差，進(jìn)行任務(wù)遷移執(zhí)行此類應(yīng)用將是更有利的。圖中結(jié)果還表明，皇后數(shù)量越多，節(jié)省時間更多。

圖7 網(wǎng)絡(luò)帶寬的影響

4) 云端負(fù)載的影響。本部分討論進(jìn)行任務(wù)遷移時云端負(fù)載狀況對于計算時間節(jié)省的影響。云端自有負(fù)載隨機(jī)生成，若更多的應(yīng)用執(zhí)行在云端，則分配給遷移任務(wù)的計算能力會相應(yīng)下降。動態(tài)的云端計算負(fù)載對遷移任務(wù)的響應(yīng)時間具有重要影響，云端負(fù)載越小，表明加速因子Sf越大，任務(wù)的響應(yīng)越快。圖8的左側(cè)坐標(biāo)值表明不同的云端負(fù)載狀況對于面部識別應(yīng)用的計算時間節(jié)省的影響。由于面部識別應(yīng)用需要向云端發(fā)送圖片，無線發(fā)送與接收數(shù)據(jù)的時間較多。因此，加速因子至少需在某個最小值上以遷移所需傳輸時間。多數(shù)情況下，該最小值約為2。同時，圖像像素越大時，數(shù)據(jù)傳輸時間越長，反之亦然，此時需要更大的加速因子才能加速數(shù)據(jù)傳送。圖中結(jié)果還表明，圖像像素越大，計算時間節(jié)省越多。圖8的右側(cè)坐標(biāo)值表明不同的云端負(fù)載狀況對于N皇后應(yīng)用的計算時間節(jié)省的影響。由于該應(yīng)用發(fā)生的數(shù)據(jù)傳輸量較少，故發(fā)送和接收數(shù)據(jù)的時間并不會對應(yīng)用的響應(yīng)時間產(chǎn)生明顯影響。同時，皇后越多，計算時間節(jié)省越多，這是由于能力更強(qiáng)大的云端以更快的速度求解了輸入問題。

圖8 云端處理性能的影響

4 結(jié) 語

為了作出移動云計算任務(wù)遷移的最優(yōu)決策，提出了一種均衡任務(wù)遷移決策算法。首先，算法將任務(wù)遷移決策問題建立為Lagrange乘子的非線性優(yōu)化模型，模型同步考慮了任務(wù)遷移后的執(zhí)行時間代價和執(zhí)行能耗代價。然后，為了更準(zhǔn)確地求解遷移決策，設(shè)計了一種考慮用戶應(yīng)用動態(tài)行為的統(tǒng)計回歸模型進(jìn)行任務(wù)執(zhí)行時間的估算，從而獲得時間-能耗均衡性能的任務(wù)遷移決策。利用兩種不同類型的應(yīng)用實(shí)例對算法進(jìn)行了仿真測試。結(jié)果表明，對比基準(zhǔn)算法，所設(shè)計的算法在平均執(zhí)行時間、執(zhí)行能耗、預(yù)測準(zhǔn)確性等方面均表現(xiàn)出一定優(yōu)勢。