一種均衡的移動云計算任務遷移決策算法

薛慶水 李鳳英

1(上海應用技術大學計算機科學與信息工程學院 上海 201418)2(上海交通大學繼續教育學院 上海 200240)

0 引 言

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

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

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

是否進行任務遷移決策需要綜合考慮，任務在云端執行的代價不僅取決于任務的執行時間，還需要考慮其他遷移代價，如當前云端的計算負載、網絡帶寬條件和需要傳輸的數據量等。以上因素使得任務執行的時間和能耗是非線性相關的。本文將以更加準確的任務執行時間預測方法，在執行時間和能耗兩個方面更加均衡地考慮是否進行任務遷移，并對影響遷移決策的重要因素作出討論，最終設計出在執行時間和能耗上作出均衡優化的任務遷移決策。

1 任務遷移決策問題

1.1 遷移決策模型

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

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

ft(tc)=tc+D/B

(1)

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

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

(2)

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

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)表明本地設備上任務的執行代價需大于云端執行代價，該約束可以確保任務遷移時的執行時間可以落入時間代價函數的最小值與最大值之間，以節省計算時間；式(5)表明最大延時約束，以確保任務遷移到云端執行的響應時間不超過最大延時；式(6)和式(7)是時間的非負約束；式(8)確保云端服務器處理速率快于本地設備。利用Lagrange乘子法求解代價函數的最小值和最大值，式(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為本地設備執行任務的平均功耗，pi為本地設備空閑時的平均功耗，pt為本地設備的平均發送與接收功耗。基于代價函數最大值與最小值的任務遷移決策過程作如下討論。

1.2 遷移決策討論

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

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

2) 均衡型遷移決策。該策略中，進行任務遷移只能優化一個指標(時間或能耗)，另一指標會相應降低。此時，需要引入均衡指標，該指標的定義和計算方法可參見2.1節。

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

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

當任務需要開始執行時，需要決定其期望時間，并將之與代價函數中tm的最大值與最小值進行比較，根據該值在圖1中所處的區域作出遷移決策。

2 任務執行時間估算

對于計算密集型任而言，任務是否進行遷移，與任務在本地設備上的執行時間tm估算相關。算法將利用統計回歸方法[10]估算tm。將任務的執行時間tm建立為一個隨機變量模型，表示為：

tm=m(X)+ζ

(16)

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

(17)

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

(18)

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

圖2 預測準確性

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

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

(19)

(20)

式中：em為本地設備執行任務時的設備能耗，定義為：

em=pm×tm

(21)

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

(22)

結合以上兩個因素，均衡指標定義為：

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

(23)

式中：α為權重因子，表示對于能量和時間的均衡偏好，且0≤α≤1。α值取決于移動設備的剩余能量。因此，當移動設備的電池能量充足時，將分配最大的權重值以節省執行時間，而隨著移動設備電量的降低，α值也將隨之降低。令Dloc表示均衡區域內任務的執行位置，其值的判定決策為：

(24)

式中：Gth為預定義的門限值，取決于應用任務的QoS需求。可以看出，α和Gth兩個參數的取值決定了用戶在執行時間和能量間的取舍與妥協。

2.2 α值的取值討論

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

(25)

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

3 仿真實驗

3.1 實驗配置與基準函數

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

表1 設備配置

3.2 性能指標

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

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

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

(26)

4) 計算時間節省。任務在本地執行的時間與在云端服務器上執行時間的差值即為計算時間的節省。

3.3 實驗結果

1) 皇后數量的影響。圖3是執行N皇后應用時皇后數量對于算法在平均執行時間和能耗上的影響。圖3的左側坐標值表明本文算法比對比算法節省了更多的計算時間，這是由于算法利用統計回歸考慮了用戶行為的動態性，優于另外兩種算法的均值估算方法。

圖3 皇后數量對執行時間和能耗的影響

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

圖4 皇后數量對預測準確性和節省時間的影響

圖4的右側坐標值表明，一些情況下，本文算法和文獻[7]得到的計算時間節省是相近的，這是由于兩種算法都作了準確的任務遷移決策，即若輸入應用的皇后數量較多，兩種算法均會選擇遷移任務至云端從而節省應用的計算時間。而文獻[6]以均值時間作為遷移決策的依據，導致任務遷移是不確定的，從而節省時間有可能沒有前兩種算法多。

2) 圖像大小的影響。圖5是執行面部識別應用時圖像大小對于算法在平均執行時間和能耗上的影響。可以看到，由于通過統計回歸方法考慮了用戶輸入應用的變化行為，本文算法得到的平均執行時間是最小的。而對于能耗，像面部識別這類數據密集型應用，其傳輸能耗在總能耗中占據極大分量。即使進行任務遷移，傳輸能耗也必須考慮在內。因此，遷移決策必須同步考慮傳輸時間和計算時間。由于統計回歸估算的任務執行時間更加準確，本文算法同樣得到了更多的能耗節省。而算法中利用均衡要素考慮，算法還同時維持了計算時間的指標。

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

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

圖6 圖像大小對預測準確性和節省時間的影響

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

圖7 網絡帶寬的影響

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

圖8 云端處理性能的影響

4 結 語

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