移動Ad Hoc云中任務卸載的聯合優化策略

胡 楊，韓嘉偉，張志紅，李 軍，劉 暢，曾祥豹，李小飛，王音心

(1.中電科技集團重慶聲光電有限公司，重慶 401332；2.中國電子科技集團公司第二十六研究所，重慶 400060；3.重慶郵電大學 移動通信技術重慶市重點實驗室，重慶 400065)

0 引言

隨著智能手機、平板電腦等移動終端在生活中的廣泛普及，人們從互聯網獲取信息的方式已從傳統的臺式電腦終端逐漸轉移至移動終端。由中國互聯網信息中心發布的《第41次中國互聯網絡發展狀況統計報告》顯示，截至2017年12月，我國手機網民規模達7.72億，且使用移動手機上網的比例高達97.5%，超過了60.1%的臺式電腦上網比例[l]。在互聯網用戶服務需求日益多樣化的趨勢下，移動終端還需依賴更強大的網絡資源和技術平臺才可提供更多、更強健的服務，因此，科研人員提出了移動云計算(MCC)[2-3]的概念，將傳統云計算(CC)技術和理念融合到移動互聯網的服務領域中，利用云端強大的處理和存儲能力來減輕移動設備端的負載，以提升整個服務體系的處理能力與服務能力。但在實際生活中，移動終端用戶往往找不到可用的云基礎設施，不能保證隨時隨地的接入情況，而且由于服務器距離太遠，任務遷移也會面臨著高網絡延遲和通信成本的問題。因此，科研人員基于移動云計算的思想，提出了移動Ad Hoc云計算[4-5]的概念并受到了廣泛關注。

在移動Ad Hoc云中人們關注的兩個重要指標是：任務卸載過程中產生的系統能量消耗[6]和任務卸載時延[7]。任務卸載過程中產生的系統能量消耗，包括在任務提交和計算結果返回階段產生的通信能耗，以及在代理終端執行處理過程中產生的計算能耗。所述能耗大小直接影響到移動設備的電池續航能力，該問題對由資源(如內存、CPU)受限且電池容量小的移動設備所組成的移動Ad Hoc云的影響尤為明顯，如果不能處理好任務卸載過程中的能耗問題，將會影響到云系統的續航能力，降低系統的服務性能。在任務卸載中存在數據傳輸及任務處理時延，雖然相對傳統移動云計算，移動Ad Hoc云在任務時延上具有很大的優勢，但由于網絡中存在多個性能差異的移動設備，而且每個設備間的無線網絡環境也各不相同，因此，在客戶端卸載任務時，每個代理終端產生的時延也不盡相同。對于云游戲、云感知等時延敏感性的實時性任務[8]，如果時延過大，將會嚴重影響到移動Ad Hoc云的服務質量(QOS)，從而降低客戶服務體驗。對于文件壓縮、圖像處理等非時延敏感性任務，則可以適當放寬對時延的要求。總之，對于任何計算任務，時延總是越小越好。

本文在移動Ad Hoc云任務卸載的過程中，提出了一種降低系統能耗與任務時延的聯合優化算法(JOECD)，解決了客戶端計算任務恰當選擇代理終端問題。

1 系統模型

圖1 任務卸載系統模型

移動Ad Hoc云計算系統任務卸載模型如圖1所示，客戶端在網絡中發現一系列合適的代理終端并向其卸載自身計算任務，代理終端利用自身的可用資源為客戶端進行服務，并把執行完成后的任務返回給客戶端[9]。不失一般性，假設網絡中存在兩種無線通信方式，即WiFi與蜂窩網絡。眾所周知，WiFi的通信成本普遍低于蜂窩網絡，而通信速率普遍高于蜂窩網絡，因此，在任務卸載的過程中優先選擇使用WiFi進行通信。如果代理終端移出了WiFi的通信范圍，則客戶端自動切換為蜂窩網絡繼續通信。

假設系統中存在M個客戶端(C)需要卸載任務，且每個客戶端的任務量不同，第i個客戶端Ci的任務量為Wi，在任務來臨時卸載至代理終端，默認每個客戶端僅存在一個計算任務。同時，假設系統中存在N個代理終端(A)可共享資源，第j個代理終端Aj的最大可用資源量為Qj，當用戶卸載的任務處理完成后返回結果給客戶端。假設系統中的所有移動設備上可用的整體資源及剩余電池能量都足以運行每個獨立的計算任務，即任何計算任務都可以選擇卸載至網絡中任意其他代理終端進行處理。因此，當客戶端在進行任務卸載時，需根據代理終端的屬性決策出如何選擇代理終端進行任務卸載，以達到優化系統能耗和時延的目的。當客戶端Ci中的計算任務到達時，Ci會在系統中尋求足夠的資源來處理自身的計算任務，在任務卸載的過程中會產生相應的能量消耗及時延。

基于上述假設，對移動Ad Hoc云在任務卸載過程中涉及到系統能耗及任務時延進行建模，并由此推導出目標函數。

1.1 計算能耗

在任務卸載過程中，系統能耗包括在移動設備上處理計算任務所產生的計算能耗，以及在數據傳輸過程中產生的通信能耗。其中，計算能耗與計算任務量及當前終端的處理能力有關，因此，客戶端Ci在任務卸載中產生的總計算能耗ei為

(1)

1.2 通信能耗

(2)

(3)

為了便于分析，假設在Aj將任務處理后得到的結果數據大小為客戶端Ci提交數據的ρ倍(0<ρ≤1)，因此，結果回傳階段在WiFi和蜂窩中傳輸的數據量如下：

(4)

(5)

因此，在卸載任務至代理終端的過程中產生的通信能耗為

(6)

式中：bcell為蜂窩的網絡帶寬；2為單位時間的通信能耗。

因此，Ci在任務卸載過程中所產生的總通信能耗為

(7)

式中上角com表示通信。

為了便于討論，本文假設所有移動設備在能耗方面都是同性質的。對于所有設備都使用同樣的單位時間能耗λ1與λ2，用于通信的能量總量一般高于用于計算處理的能量[9]，即λ1<λ2。

1.3 任務時延模型

類似于通信能耗，如果將客戶端Ci的計算任務卸載至代理終端Aj，則卸載計算任務所產生的任務時延可表示為數據傳輸產生的傳輸時間及任務處理所產生的計算時間之和，即

(8)

因此，客戶端Ci在任務卸載過程中所產生的任務時延為

(9)

1.4 優化問題

使下式最小

(10)

目標函數需要滿足:

(11)

(12)

xij≥0j=1,…,N

(13)

值得注意的是，通常需要根據具體情況的不同對任務延遲和系統能耗進行綜合權衡[11]。在上述目標函數中，我們使用權重參數γ進行靈活配置。例如，如果移動設備電池性能問題并不用嚴重，或者當前客戶端的計算任務對延遲非常敏感，則可以將γ設置得盡可能小。在這種情況下，優化問題變為盡量使任務時延最小化以降低對能耗的關注度。然而，如果能耗是移動設備的主要關注點，而任務延遲是可以容忍的，則γ可以設置得足夠大。

2 系統能耗與任務時延的聯合優化算法

在移動Ad Hoc云中，客戶端在卸載一些計算密集型任務過程中不僅會產生相應的傳輸能耗與計算能耗，而且還會產生一定的任務時延。為了降低系統能耗與減小任務時延，本節提出了一種運用在移動Ad Hoc云中，基于系統能耗與任務時延的聯合優化 (JOECD)算法。

2.1 算法具體流程

當每一個客戶端的計算任務來臨時，都會執行JOECD算法，主要流程如圖2所示。

(14)

圖2 JOECD算法流程圖

為更清晰地展現客戶端進行任務決策并卸載的過程，在算法1)中對JOECD算法進行了詳細的設計：

輸入參數：客戶端卸載任務量W,代理終端最大可用資源量Q,單位時間的計算能耗λ1，單位時間的通信能耗λ2,WiFi的網絡帶寬bwf,蜂窩的網絡帶寬bcell,客戶端個數M，代理終端個數N。

輸出參數:系統能耗E，任務時延D。

2)l=l+1；

3)for 每一個代理終端j=1∶N；

4)根據式(10)計算Sij；

5)end for；

9)根據式(1)，(7)，(9)計算Ei與Di；

10)更新可用資源量Q(l)；

11)將Ci從集合C中移除；

12)else；

13)任務卸載失敗，Ei=0，Di=0；

14)end if；

16)返回步驟2)；

17)end if；

18)返回E，D。

2.2 復雜度分析

算法復雜度是衡量算法優劣的一個指標[12]，本文提出的任務卸載決策算法的復雜度為O(MN2)。

如上所述，該算法是根據客戶端的數量一輪一輪進行的，首先分析算法中第l輪決策中的復雜度，如算法1)所示，它主要包括以下步驟：

a.計算Si。對于客戶端Ci，需對網絡中所有的代理終端，即A中所有元素通過式(14)都計算一次Sij以得到Si，這個步驟的復雜度為O(N)。

根據上述分析，第l輪決策中的復雜度為平方階，即O(N2)。由于系統中存在M個客戶端，因此，在算法中這個決策步驟會執行M次，因此，本文提出的任務卸載決策算法的復雜度可表示為O(MN2)。

3 仿真與性能分析

為了對本文提出的系統能耗與任務時延的聯合優化算法進行性能評估，將JOECD與文獻[2]中提出的移動云計算(MCC)方案在系統能耗與任務時延上進行對比。在MCC方案中，客戶端通過宣布一個總的回報以激勵代理卸載資源，并將回報與資源卸載量進行迭代至雙方收益最大化。由此可知，MCC方案中并沒有對系統能耗與任務時延進行控制。

3.1 參數設置

3.2 性能分析

圖3 系統能耗與客戶端數量之間關系

由圖3可知，當客戶端數量從1增加到10時，兩種方案的系統能耗都隨著客戶端數量的增加而增加，這是因為當云系統中計算資源充足時，卸載更多的任務會導致更多的計算能耗和通信能耗。在到達的任務量較少時，由于系統內資源充足，JOECD算法通過任務卸載決策算法可選擇當前系統中能耗與任務時延最低的代理終端進行任務卸載，而移動云計算(MCC)方案則更關注系統收益以及資源利用方面，從而盡可能選擇任務卸載過程中系統收益最高及通信成本最低的代理終端。因此，JOECD算法在能耗方面的表現優于MCC方案。但當客戶端增多時，由于系統中的總計算資源有限，導致了在JOECD算法中無更多的代理終端進行選擇，從而不得不選擇能耗與時延較高的代理進行任務卸載。因此，在客戶端數量較多時，JOECD算法在系統能耗上的表現會與MCC方案趨于接近。

圖4給出JOECD算法與MCC方案在任務時延上的差異。由圖可看出，任務時延隨著云系統內客戶端的數量增加而增加，這是由于任務數量越多且每個任務的分配過程都會產生時延，故而造成的總時延升高。當云系統內的任務數量增加時，云系統內的可用計算資源逐漸變得不再充足，此時JOECD算法中新的客戶端已無機會選擇時延表現更優的代理終端，只能選擇時延較高的代理滿足任務需求；而在MCC方案中，即使存在代理間的資源動態調整，但因為云系統內總的資源量受限，剩余資源不能滿足到達的任務總量要求。因此，在客戶端數量較高時，兩種方案在任務時延趨于接近。

圖4 任務時延與客戶端數量之間關系

4 結束語

本文綜合考慮了移動Ad Hoc云任務分配過程中系統能耗與任務時延問題，提出了任務卸載過程中基于系統能耗與任務時延的聯合優化算法。該算法對任務卸載過程中會產生的計算能耗、通信能耗及卸載時延進行建模并提出了優化目標問題。通過預估處理對每個客戶端的需要卸載任務進行卸載決策，以達到減小系統能耗和任務時延的目的。