設備間任務依賴的最佳卸載決策和資源分配

胡 恒，金鳳林*，謝 鈞，俞 璐，黃科瑾，孟繁倫，楊 濤

(1.陸軍工程大學 指揮控制工程學院，江蘇 南京 210007；2.陸軍工程大學 通信工程學院，江蘇 南京 210007；3.31121部隊，江蘇 南京 210018；4.61096部隊，江蘇 南京 210007)

0 引 言

隨著物聯網技術和5G技術的發展，產生的各種新型應用，對網絡的時延和帶寬提出了更高的要求。但由于終端設備的計算和存儲能力的限制，無法處理和存儲如此龐大的數據。因此移動邊緣計算[1]應運而生，MEC能有效解決時延長、能耗高和數據不安全等問題。其中計算卸載技術[2]作為MEC的關鍵技術之一，通過合理的卸載決策和資源分配策略將終端設備上運行的任務卸載到邊緣服務器，能夠減少任務完成時延和設備的能耗，提高設備性能。而通過將D2D技術與MEC結合，可以更進一步降低數據傳輸時延和能耗。

對于計算卸載技術，目前已經出現了很多研究成果。文獻[3]提出了一種低復雜度的啟發式算法來最小化共享頻譜中的任務執行延遲。文獻[4]考慮了具有輔助節點的MEC系統，聯合優化了用戶和輔助節點的計算和通信資源分配，使總能耗降至最低。文獻[5]基于一種低復雜度的算法來降低設備能耗。文獻[6]使用線性規劃的方法解決卸載決策、延遲和能耗聯合優化問題。文獻[7]為了最大程度地減少任務等待時間和能耗，提出了一種啟發式算法，該算法保證了子任務之間的依賴性并提高了任務效率。文獻[8]提出了一種基于Lyapunov優化的低復雜度的動態計算卸載在線算法，獲得了最優的卸載策略。文獻[9]考慮了包含多個忙碌智能設備和多個空閑智能設備的D2D與MEC協作系統，基于塊坐標下降法和凸優化技術的兩階段迭代算法解決卸載決策和資源分配的聯合優化問題，獲得最佳卸載策略和資源分配策略，最小化系統的總能耗。文獻[10]建立了一個具有通信資源和計算資源約束的混合整數非線性問題，開發了一種優化算法來解決此問題。文獻[11-13]同樣考慮了在MEC環境下引入D2D技術進行協作，來考慮任務的卸載情況。

然而以上文獻都僅考慮了單個設備上任務的卸載情況。對于不同設備之間任務具有依賴性的研究非常少，幾乎沒有。實際上，在不同設備上執行的任務通常也是具有相關依賴性的。文獻[14]雖然考慮了MEC系統環境下兩個不同設備之間的任務相關性，但沒有考慮與D2D技術進行協作來優化系統性能。雖然業內也在MEC環境中引入了D2D技術來優化系統性能，但是對于MEC與D2D技術協作網絡環境中不同設備任務之間任務具有相關性的研究，就作者目前所知，還沒有相關文獻對此方面進行研究。因此該文針對此方面，同時在文獻[14]的基礎上進行了研究，聯合優化了設備任務完成時延和能耗，在任務執行時延和設備能耗之間進行權衡，尋找一個平衡點使得系統性能最優。

1 系統模型

1.1 網絡模型

考慮了兩個設備的MEC與D2D協作網絡。圖1為MEC與D2D協作網絡系統模型，其中d1和d2分別表示設備1、設備2與MEC服務器之間的距離，d3表示設備1和設備2之間的距離。

圖1 MEC與D2D協作網絡系統模型

設備1和設備2分別具有m和n個要執行的一系列任務，并將任務之間的依賴關系建模為順序圖，同時對每個設備引入兩個虛擬任務，0為設備的輸入任務，m+1和n+1為輸出任務，如圖2所示。其中設備2的第k個子任務的輸入依賴于設備1第m個任務的輸出和設備2第k-1個任務的輸出。

圖2 不同設備間調用圖模型

該文采用{Li,j,Ii,j,Oi,j}來描述每個設備的每個任務，其中j=1表示設備1，j=2表示設備2。i表示設備上的任務，i=0,1,…,m+1或0,1,…,n+1。Li,j表示任務的計算量，完成任務總共需要的CPU周期，Ii,j表示計算任務的輸入數據的大小，Oi,j表示任務的輸出數據的大小。對于設備1和設備2第0個和最后一個虛擬任務計算量為0。同時對于兩個設備而言，第0個任務輸入數據的大小為0，最后一個任務輸出數據的大小為0。對于設備1和設備2第i個任務的輸入等于上一個任務的輸出：Ii-1,j=Oi-1,j，j={1,2},i=1,2,…,m,m+1或1,…,k-1,k+1,…,n+1。特別的是，對于設備2的第k個任務的輸入依賴于設備2的第k-1個任務和設備1第m個任務的輸出：Ii,2=Oi-1,2+Om,1。該文規定第0個和最后一個虛擬任務只能在本地執行。同時，用ai,j={0,1}表示卸載決策：ai,j=0表示在本地執行，ai,j=1表示在服務器執行。

1.2 通信模型

首先介紹了系統的通信模型。對于每個設備分配帶寬相等的正交信道，用W表示，卸載和上傳設備之間互不干擾。

上傳速率為：

(1)

其中，pi,j表示設備j的發射功率，hi,j表示設備j到邊緣服務器的信道增益，σ2表示設備的噪聲功率。

下載速率為：

(2)

其中，p0表示邊緣服務器的固定發射功率。

設備1與設備2之間的傳輸速率為(設備1第m個任務的輸出與設備2的第k個任務有關)：

(3)

信道增益為：

(4)

其中，g表示天線增益，Fc表示載波頻率，dr表示距離，pl表示路徑損耗指數。

1.3 計算模型

下面給出了執行和傳輸任務的時間和能耗。

本地執行任務i的完成時間為：

(5)

其中，fi,j表示執行任務i的CPU計算能力。

本地完成任務i所損失的能耗為：

(6)

其中，k是取決于芯片架構的有效開關電容參數，是固定常數。

服務器執行任務i的完成時間為：

(7)

其中，f0表示服務器的恒定CPU頻率。

將任務i從設備傳輸到服務器的上傳時間為：

(8)

將任務i從設備傳輸到服務器的傳輸能耗為：

(9)

從服務器返回到設備的下載時間為：

(10)

將任務從設備1傳輸到設備2的傳輸時間為：

(11)

將任務從設備1傳輸到設備2的傳輸能耗為：

(12)

1.4 依賴模型

由于設備1的第m個任務的輸出作為設備2第k個任務的輸入，所以要綜合考慮設備1第m個任務和設備2第k個任務的位置關系：當m任務和k任務都在本地執行時，由于兩設備都支持D2D技術，所以設備之間可以直接通信，有傳輸時延和能耗；當m任務和k任務都在邊緣服務器上執行時，此時沒有時間和能耗的損耗；當m任務在本地執行，k任務在邊緣服務器執行時，此時需要上傳時延和能耗；當m任務在邊緣服務器執行，k任務在本地執行時，此時需要下載時延。

1.5 問題公式化

由以上分析可知，設備1的任務完成時間為：

(13)

(14)

(15)

等待設備2第k-1個任務的輸出時間為：

(16)

設備2的任務完成時間為：

(17)

設備2消耗的能耗為:

(18)

兩個設備總性能指標為：

(19)

(20)

所以問題公式化為以下公式：

s.t.

(21)

s.t.

(22)

2 固定卸載決策的最佳資源分配

問題p(3)的拉格朗日表示為：

(23)

其中，λ和μ都是不小于零的表示與相應約束相關聯的對偶變量，λ*和μ*表示最佳對偶變量，則能推導出每個設備的最佳CPU頻率和發射功率的閉合表達式如下：

(24)

(25)

其中，

W(x)表示LambertW函數,應用梯度下降法迭代更新λ和μ，直到滿足一定的停止標準。該方法的偽代碼如算法1所示。由于P(3)是一個固定ai,j的凸問題，梯度下降法保證收斂。

算法1 ：最佳資源分配算法。

1輸入：給定大于0的λ和μ、步長α和精度值pre

2輸出：p*,f*

3 while True:

4根據最佳CPU頻率的閉合表達式(24)計算fi,j

5根據最佳發射功率的閉合表達式(25)計算pi,j

8根據梯度下降算法，分別更新λ和μ的值

10退出循環

11 End

3 優化卸載決策

在第2小節中，給定卸載決策，可以得出最佳資源分配，需要搜索2(m+n)次卸載決策，然后從中選擇最小目標的卸載決策。但是隨著任務m或n的增多，這種遍歷搜索方法是行不通的，復雜度會很高。基于此提出了一種降低復雜度的在線任務卸載算法,可以在多項式時間內獲得最優卸載決策。本節首先證明最優卸載決策具有連續性，然后在此基礎上提出了一種降低復雜度的優化算法。

3.1 一次爬升策略

定理1：假設f0>fpeak，則最優卸載決策具有連續性(如果有任務要卸載)，即對于最優決策，如果設備有任務需要卸載到邊緣服務器，那么在整個任務的執行過程中，任務卸載到邊緣服務器只會發生一次，它被稱為一次爬升策略。

證明：略。

3.2 基于一次爬升策略的在線搜索算法

基于一次爬升策略，提出了低復雜度的在線任務卸載算法。通過此算法不必暴力遍歷所有可行的卸載決策，只需在每個設備上尋找滿足使得設備能耗和時間加權和最小這個指標要求的兩個任務即可。如圖3所示，找到滿足指標要求的兩個任務i和j，然后只需將i和j，以及中間的任務都卸載到邊緣服務器即可。

圖3 一次爬升策略

因此只需尋找這樣兩個任務，使得設備的能耗和時間的加權和η(i,j)最小。這里設定任務i*為入口任務，任務j*為退出任務，i=1,2,…,m,j=1,2,…,n，設備的能耗和時間加權和公式如下：

(26)

其中，eu為傳輸能耗，el為本地能耗，tu為傳輸時間，tc為在服務器上的執行時間，td為下載時間，tl為本地執行時間，βE和βT分別為能耗和時延權重，η(i,j)為加權和，ηmin為最小加權和。

算法2給出了尋找最優的入口任務i*和退出任務j*的算法，初始時，任務全部在本地執行。因此只需要枚舉滿足一次爬政策的卸載決策，而不必遍歷所有2m+n個卸載決策，即只需在每個設備上尋找滿足使得設備能耗和時間加權和最小這個指標要求的兩個任務即可。對于設備1，根據算法2只需搜索m*(1+m)/2個任務組合。類似的，設備2也只需要搜索n*(1+n)/2個任務組合。因此搜索總數[m*(1+m)/2*n*(1+n)/2]，即O(m2*n2)。隨著m或n的增大，基于單爬策略的在線搜索算法的復雜度明顯低于暴力搜索算法。

算法2：在線搜索算法。

1輸入：給定βE，βT值

2輸出：ηmin，i*，j*

3根據加權和公式計算η(1,1)，令ηmin=η(1,1)，i*=1，j*=1

4 Fori<----1 tom:

5 Forj<---itom:

6計算出最優f*和p*，然后計算設備的能耗和完成時間

7根據能耗、時間和加權和公式計算設備的加權和η(i,j)

8 Ifη(i,j)<ηmin:

9ηmin=η(i,j)

10i*=i

11j*=j

12 End

13 End

4 實驗評估

在這一小節，將進行數值模擬來評估所提的卸載算法，關注的性能指標是兩設備的總性能，用ET表示，其中每個設備的性能用設備完成任務所消耗的能耗和時間的加權和表示。為了方便與文獻[14]算法進行比較，實驗數據值的大小參考文獻[14]進行了設置。接下來，將會用最優卸載算法和文獻[14]中算法進行對比分析。

圖4為每個設備的任務調用圖，每個節點代表一個任務，節點權值為完成此任務的計算量，邊權值表示輸入和輸出數據的大小。這里將設備的任務數量設置為m=3和n=5，服務器的發射功率固定p0為1 W，每個設備的發射功率峰值ppeak為0.1 W，邊緣服務器的CPU頻率fc和每個設備的CPU頻率峰值fpeak分別為1010和108(cycles/s)，噪聲功率σ2為10-7W，k是取決于芯片架構的有效開關電容參數，是固定常數，這里設置為10-26。此外設置帶寬W為2 MHz，對于每個設備上任務的計算量大小設置為Li,1=[0，65.5，40,3，96.6，0](Mcycles)，Li,2=[0，70.8，95.3，86.4，18.6，158.6，0](Mcycles)。

圖4 實驗模型和參數

接下將與文獻[14]算法下的系統性能做比較。在此次實驗中由于文獻[14]與本實驗的最優卸載決策：設備1的第m個任務和設備2的第k個任務都是在邊緣服務器執行，所以為了更好地對比最優算法和文獻[14]中的算法，這里采用了相同的次優卸載決策，此決策中設備1的第m個任務和設備2的第k個任務都是在本地執行，這樣能更直觀地觀察有無D2D技術支持系統性能的優劣。

從圖5中的(a)和(b)可以觀察到，當固定d3和d2或固定d3和d1時，隨著d1或d2距離的增大，該文提出的算法要優于文獻[14]提出的算法，因為在支持D2D技術的MEC系統中，設備1的第m個任務和設備2的第k個任務都在本地執行，設備間之間可以直接通信，避免了在不支持D2D技術的MEC系統中需要先將任務卸載到邊緣服務器，然后從邊緣服務器下載到設備2上。所以可以得出支持D2D技術的MEC系統相比于文獻[14]不支持D2D技術的MEC系統，節省了時間和能耗，系統性能更好

從圖5(c)可以觀察到，當d3增大時，文獻[14]的算法不受d3距離變化的影響,是因為設備1的第m個任務和設備2的第k個任務都在本地執行，設備之間不需直接通信。雖然該文提出的算法受d3的影響，但是通過圖(c)中曲線可以觀察到，在兩設備間的距離不大于設備到服務器之間的距離400 m時，該文所提的算法還是優于文獻[14]所提的算法。而當兩設備間的距離大于400 m時，任務卸載到邊緣服務器上是較好的選擇，因為邊緣服務器的性能要比設備的性能好，將任務卸載到邊緣服務器能節省能耗和時間。現實中也可以知道，當設備間的距離遠大于設備到服務器之間的距離時，當然是卸載到服務器更好，但當設備間距離較近時，卸載到設備是更好的選擇。

(a)

5 結束語

該文研究了MEC與D2D技術協作系統環境下不同設備之間具有任務依賴性的最優的資源分配和優化任務卸載決策問題。為了最小化設備的能耗和任務完成時間的加權和，首先固定卸載決策，推導出卸載發射功率和本地CPU頻率的閉合表達式，運用凸優化方法求解出該問題的最優解，得到最佳資源分配策略。然后證明了最優卸載決策遵循一次爬升策略，在此基礎上提出了一種降低復雜度的在線任務卸載算法，通過該算法獲得了最優卸載決策。通過數值實驗表明，提出的最優卸載策略明顯優于其他算法。