一種移動邊緣云計算任務卸載算法

查易藝 袁 燁 李金湖 柳 歡 陳振興 李 進

1(國網江蘇省電力有限公司信息通信分公司 江蘇 南京 210024)

2(江蘇電力信息技術有限公司 江蘇 南京 210024)

3(國網信通億力科技有限責任公司 福建 福州 350003)

4(江蘇大學計算機學院 江蘇 鎮江 212013)

0 引 言

移動智能手機的普及使得諸如面部識別、移動健康監測、增強現實和移動游戲等復雜的交互式應用越來越多地運行于移動設備端[1]。此類應用的執行需要高速的處理資源，從而得到較快的響應時間，提高用戶體驗[2-3]。面對此類需求，移動邊緣云計算及其任務卸載(Task Offloading)技術應運而生[4-5]。應用移動邊緣計算技術，可以將移動用戶設備方復雜的計算任務從移動設備上卸載至資源能力更加強大的邊緣云服務器上執行，借助于邊緣云的資源優勢，得到更快的響應時間，并節省移動設備能耗[6-8]。然而，移動設備與邊緣云間的無線通信環境對于任務卸載性能會產生重要影響[9-10]，且會直接影響到移動用戶設備進行任務卸載的決策。

目前，任務卸載問題已有一些研究。考慮到5G時代移動設備計算需求的巨大增長，文獻[11]為了改善能效，設計了一種基于博弈理論的分布式任務卸載算法。文獻[12]在多信道環境下研究了面向多用戶的計算卸載決策問題，但以上文獻均忽略了信道通信時的干擾問題。為了節省移動設備能耗，滿足應用執行的延時約束，文獻[13]提出了一種基于Lyapunov優化技術的動態卸載算法，能以較低的計算復雜度獲得近似最優解。在大規模移動應用環境下，文獻[14]以最小化平均任務執行延時為目標，研究了多用戶的應用分割與卸載問題，并設計了離線式卸載決策算法。為了解決任務卸載面臨的傳輸延時和能耗問題，文獻[15]設計了一種基于馬爾可夫決策過程的朵云任務卸載算法。然而，由于受限的無線網絡覆蓋問題，朵云環境無法確保服務提供的連續性，無法應用于移動邊緣云中的卸載決策問題。類似地，文獻[16]同樣利用馬爾可夫決策過程對服務遷移的序列卸載決策問題進行了形式化描述，并設計了求解算法。考慮到受限的無線信道數量和通信干擾問題，文獻[17]基于博弈論設計了一種分布式卸載決策算法，文獻[18]聯合考慮通信資源和計算資源分配，設計了迭代式任務卸載算法。

然而，以上方法在其性能和靈活性上有一定限制，算法的復雜性導致其不一定適應于大規模無線網絡環境。移動邊緣云環境下，無線訪問點(基站)通常在多信道環境下，若過多的移動設備同步選擇相同信道進行任務卸載，通信干擾將嚴重影響數據傳輸性能，進而導致任務執行延時增加和移動設備能耗增加。此時，任務卸載將得不償失，即：任務卸載決策必須同步考慮通信資源和計算資源的分配。為了解決此問題，本文將設計基于能效的任務卸載決策算法，并重點解決：1) 考慮能效和延時的情況下，哪些移動用戶任務適合于進行卸載；2) 從全局最優的角度，對于需要進行卸載的任務，如何選擇合適的無線信道進行任務卸載。

1 系統模型與優化目標

移動邊緣云計算(Mobile Edge Computing, MEC)包括三個組成部分：移動邊緣云服務器，無線訪問點AP和移動用戶設備。結構如圖1所示。移動用戶可將本地任務通過Wi-Fi、4G或5G通信方法通過無線訪問點提交至邊緣云服務器執行，即任務卸載。假設N={1,2,…,N}表示移動用戶集合，M={1,2,…,M}表示無線訪問點AP可提供的無線信道集合，且每個移動用戶擁有一個任務執行需求。用戶任務具有兩個屬性，表示為Ti=(Oi,Di)，i=1,2,…,N，其中，Oi表示完成用戶i的任務需要的總CPU周期數，Di表示用戶i任務的數據量。用戶任務Ti可在移動設備上本地執行，也可以通過卸載方式傳輸至邊緣云端執行。

圖1 移動邊緣云計算結構

(1)

根據移動設備的CPU能量模型[19]，任務本地執行的能耗可表示為：

(2)

式中：αi、βi、χi均表示CPU能量模型的參數，不同類型和處理能力的CPU擁有不同的取值。

若移動用戶將任務通過無線信道卸載至邊緣云執行，則整個任務執行過程由三個部分組成。

(3)

令ψ=(ψ1,j,ψ2,j,…,ψN,j)表示所有移動用戶的卸載決策解，移動用戶i選擇無線信道j上傳數據的速率計算為：

(4)

(5)

(6)

2) 無線訪問點AP通過高速有線網絡將任務負載數據傳輸至邊緣云服務器，該部分的傳輸延時可忽略不計。

(7)

若任務在邊緣云執行，移動用戶設備需要等待返回結果，此時移動設備的空閑能耗計算為：

(8)

因此，任務卸載至邊緣云執行的總體能耗為：

(9)

任務卸載至邊緣云執行的總時間為：

(10)

為了優化任務卸載執行的能效，需要合理地進行通信資源和計算資源的分配。故任務卸載決策的能效最優化可形式化為：

(11)

約束條件為：

(12)

(13)

(14)

(15)

ψi,j={0,1} ?i∈N,j∈M

(16)

其中：式(12)確保任務卸載執行的能耗應小于或等于任務本地執行能耗；式(13)確保任務卸載執行的時間應小于或等于任務本地執行時間；式(14)確保無線信道的通信質量，為信道設置門限值π可以避免過多的移動用戶方同時訪問同一信道，增加數據沖突；式(15)表明移動用戶僅能選擇訪問一條無線信道；式(16)表明任務僅能在本地執行或邊緣云上執行。

2 能效任務卸載算法

為了求解式(11)的最優化問題，本文設計了一種能效任務卸載算法。算法由兩個部分組成：(1) 決定移動用戶分類和優先級；(2) 根據優先級，移動用戶依次獲得通信資源分配。

2.1 移動用戶分類和優先級確定

根據任務數據量、負載密度、計算能力以及能耗，移動用戶可劃分為兩類。第一種類型的移動用戶為本地執行任務的移動用戶，令Ul表示該類型用戶。當移動用戶單獨占用一個信道時，該移動用戶設備的數據傳輸速率可表示為：

(17)

(18)

換言之，若任務卸載執行的能耗大于本地執行能耗，則移動用戶劃分為第一類用戶Ul。

令Uo表示為第二種類型用戶，為除了第一種類型用戶外的其他用戶。屬于Uo的移動用戶可選擇在本地執行任務或卸載至邊緣云執行，其最終決策取決于信道的通信質量。對于該類型移動用戶，在卸載決策過程中需設置不同的優先級，按其優先級依次作出卸載決策，將優先級定義為：

(19)

算法1為移動用戶分類與優先級確定過程。

算法1移動用戶分類與優先級計算

2. 輸出：移動用戶分類集合Ul和Uo，移動用戶優先級η={ηi},i∈Uo

3. For 移動用戶i=1 toNdo

4. For 信道j=1 toMdo

5. 根據式(17)和式(18)分別計算移動用戶獨占用一條信道時的數據傳輸速率和能耗

7. 移動用戶i歸屬于類型Ul

8. else

9. 移動用戶i歸屬于類型Uo

11. end if

12. end for

2.2 基于拍賣的卸載機制

圖2 拍賣示意圖

傳統的拍賣過程中，資源分配是通過多輪的競標過程確定最終的贏家。然而，這種多輪拍賣并不適用于本文的場景，因為這會導致移動用戶任務執行中過多的等待延時。本文采用單輪拍賣以改進能效，降低任務卸載延時。

資源分配中，結合資源和競標者給出的價格信息，移動用戶可以決定哪條信道成為拍賣贏家，并確定最終的資源交易價格bj。因此，此時的最優化問題即可轉換為拍賣問題，ψi,j表示拍賣結果，ψi,j=0表示無拍賣贏家，ψi,j=1表示信道j贏得拍賣。而算法目標也相應地可轉化為是最大化移動用戶的效用，形式化為：

(20)

為了確定拍賣贏家和資源分配關系，首先需要計算拍賣參與者的競標密度并對其排序。對于給定的無線信道，無線信道可根據其競標密度進行降序排列。對于移動用戶，最低的競標密度即表示最優的通信質量。定義作為賣方的信道的競標密度為：

(21)

移動用戶向賣方支付的最終交易價格為bj，即為贏家無線信道發送的競標價格。此時，移動用戶的效用函數為：

(22)

若移動用戶沒有參與拍賣，其效用值為0。換言之，若ψi,j=0，則U=0。而作為賣方的無線信道的效用函數可表示為：

(23)

若無線信道沒有贏得拍賣，則ψi,j=0，顯然其效用也為0。

拍賣過程如算法2所示。

算法2基于拍賣的任務卸載決策算法

1. 輸入：分類移動用戶Ul和Uo，及優先級η

2. 輸出：移動用戶的卸載決策解ψ=(ψ1,j,ψ2,j,…,ψN,j)

3. 設置臨時集合U’o=Uo

4. whileU’o≠

5. 選擇移動用戶i,i=argmax{ηi}i,i∈Uo}

6. for 信道j=1 toM

8. ifπj>0 then

9. 根據二元組(bj,sj)計算信道j的競標密度bdj(式(21))

10. 設置競標密度bd={bdj}

11. whilebd≠

12. 選擇信道j,j=argmin{bdj}j

14.ψi,j=1

//更新信道門限值

16. else

17.ψi,j=0

18. end if

19.bd=bdj

//計算競標密度時將信道j移出集合bd

20. end while

21. else

22.ψi,j=0

23. end if

24. end for

25.U’o=U’oi

//移出信道j，更新第二種類型移動用戶

26. end while

3 實驗分析

通過仿真實驗評估算法性能，選擇基于競爭的博弈卸載算法GOCA[20]、基于用戶滿意度的卸載算法USOA[21]以及本地執行算法LA作為對比算法。GOCA將任務卸載問題建立了任務執行期限和信道速率約束的競爭博弈模型，在競爭有限的通信資源的同時，最小化能耗，通過一種基于納什均衡的方式得到了移動用戶的卸載決策解。USOA引入一種效用函數，根據系統吞吐量、能耗以及執行延時描述的用戶滿意度進行最優的通信資源選擇，并最終得到其卸載決策解。LA選擇將所有任務均在本地設備上執行，以此衡量任務卸載執行的優勢。選取平均能耗、延時和移動用戶設備上的系統吞吐量作為性能評估指標。

3.1 實驗環境搭建

在MATLAB環境中搭建以下實驗環境：無線訪問點AP的覆蓋半徑設置為2 km，并擁有4條無線信道，信道帶寬設置為1 MHz，信道噪聲功率σ2=-100 dBm，路徑衰減因子設置為2。若干移動用戶設備隨機分布無線訪問點的覆蓋區域中，邊緣云服務器位于無線訪問點附近。實驗利用四種類型的移動設備進行仿真分析，包括Galaxy Note、Galaxy Note2、Nexus S和Galaxy Nexus，不同的移動設備其CPU處理能力均不相同，相關參數配置如表1所示。實驗將隨機選擇若干臺移動設備部署于無線訪問點附近，且每臺移動設備均有一個任務執行需求。任務類型包括面部識別、病毒掃描、在線游戲和虛擬現實等。每臺移動設備上隨機分配一種任務類型，不同類型的移動設備處理不同類型任務時具有不同的處理能力和速度，對應參數配置如表2所示，包括負載密度、數據大小及分配的處理能力。

表1 移動設備類型及參數

表2 任務類型及參數

3.2 實驗結果

圖3為四種算法的移動設備的平均能耗結果，移動設備數量選擇200、400、600、800、1 000進行結果觀察。可以看到，本地執行算法LA的平均能耗約為22.1 J，其他三種基于任務卸載的算法得到的能耗均小于LA，說明任務卸載可以帶來能效的優化。在200個移動設備情況下，三種卸載算法的能耗分別為6.42、6.5和6.95。隨著移動設備數量的逐步增加，平均能耗分別增加至11、12.6和14.5 J，這是由于此時過多的移動設備同步選擇訪問相同的無線信道進行任務卸載，進而導致了過多的信道沖突。由信道速率的計算公式可知，過多的信道沖突會降低信道通信質量和計算卸載的數據傳輸速率。因此，在1 000個移動設備情況下，會有越來越多的用戶選擇本地執行方法，進而導致平均能耗逐漸增加。總體來說，本文算法可節省約56%的能耗。而在三種基于卸載的算法中，本文算法也具有一定的優勢，原因在于基于拍賣機制的任務卸載決策方法是以更長周期的方式得到任務卸載決策，以更加合理的方式在滿足用戶質量需求的情況下為移動用戶分配通信資源。同時，在移動設備相對較少時，能耗節省效果也更加明顯。隨著移動設備數量的顯著增加，由于負載擁塞，本文算法性能有所下降，但仍優于GOCA和USOA。

圖3 平均能耗

圖4為移動用戶執行任務的平均延時情況。本地執行算法的平均延時約為27.5 s，在移動設備數為200時，另外三種算法的平均延時分別約為14.6、14.7和15.5 s。比較本地執行算法，卸載算法至少可節省約45.6%的延時。在1 000個移動設備情況下，四種算法得到的延時分別為19.6、20.06、20.84和27.5 s。本文算法依然是所有算法所用延時最少的。

圖4 平均延時

圖5為三種任務卸載算法的移動設備上吞吐量的變化情況，由于LA算法僅在本地進行任務執行，無需進行數據傳輸，其吞吐量始終為0。從結果可以看出，盡管本文算法在初始情況下吞吐量更低，但隨著移動設備的增加，其吞吐量下降的趨勢要慢于對比算法，最終超過對比算法。隨著移動設備數的增加，相應的信道通信干擾也將增加。相應地，數據傳輸速率有所下降，導致卸載能耗高于本地執行能耗。因此，更多的移動設備將傾向于采用本地執行策略取代任務卸載。總體來說，本文算法在大規模移動設備的測試中得到的吞吐量高于兩種對比算法。

圖5 平均吞吐量

綜合仿真實驗來看，在無線訪問點及其無線信道數量固定的情況下，可以支持仿真實驗環境設置的不同規模移動設備量的任務執行與卸載需求。但在有限的無線信道條件下，勢必會導致任務執行延時和平均能耗的增加，以及平均吞吐量的降低。原因在于：移動設備量越多，負載將出現擁塞，信道爭用將越劇烈，數據傳輸時間勢必變長，相應傳輸能耗也將增加，單位時間內系統完成的任務量則相應減少。在實際應用環境中，單個無線訪問點在其覆蓋范圍內所能支持的移動設備數量則與訪問點自身的處理能力和支持的無線信道數量相關。

4 結 語

為了優化移動設備的能耗，本文基于移動邊緣云計算環境提出了一種基于能效的任務卸載決策算法。算法綜合考慮信道干擾、任務本地執行延時以及執行能耗，將任務卸載決策問題形式化為0-1非線性整數規劃問題。為求解該問題，設計了移動用戶分類和優先級確定機制，利用拍賣理論求解了任務卸載決策，并確定了所選任務卸載信道。仿真實驗表明，在能耗、延時以及吞吐量三個指標上，本文算法均優于對比算法。