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

胡 恒, 金鳳林, 謝 鈞, 劉 瑩

(陸軍工程大學 指揮控制工程學院, 南京 210007)

隨著物聯網技術和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]提出的算法復雜度仍然很高, 本文提出的線性搜索算法更進一步的優化了卸載決策, 并且本文將場景擴展到多設備. 因此, 本文在文獻[14]的基礎上進行了進一步的優化研究, 聯合優化了設備任務完成時延和能耗.

本文在第1節中對系統進行了分析, 建立了通信、計算和任務依賴模型. 在第2節中運用凸優化方法得到最佳資源分配. 在第3節中提出了一種降低復雜度的線性搜索算法來優化卸載決策. 最后通過仿真實驗進行性能評估.

1 系統模型

1.1 MEC與D2D協作網絡系統模型

本文考慮了多個設備的MEC與D2D協作網絡.如圖1所示, MEC與D2D協作網絡系統模型. 其中ds和d2分別表示設備S、設備2與MEC服務器之間的距離, 其中,S=1,3,4,···,s, 表示設備1, 設備3, …,設備s,d(S,2)表 示設備1 ,3,4,···,s和設備2之間的距離.

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

設備S和設備2分別具有ms和n個要執行的任務,其中ms表示設備S的第m個任務. 將任務之間的依賴關系建模為順序圖, 對每個設備引入兩個虛擬任務, 0為設備的輸入任務,ms+1和n+1為輸出任務, 如圖2所示. 其中設備2的第k個子任務的輸入依賴于設備S第ms個任務的輸出和設備2第k–1個任務的輸出.

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

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

1.2 通信模型

對于每個設備分配帶寬相等的正交信道, 用W表示, 卸載和上傳設備之間互不干擾:

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

下載速率為:

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

設備S與設備2之間的傳輸速率為:

其中,和分別表示設備S第ms個任務的輸出與設備2的第k個任務都在本地執行時, 設備的發射功率和此時設備間的信道增益.

信道增益為:

其中,g表示天線增益,Fc表示載波頻率,dr表示距離,dr=dS或d2或d(S,2),pl表示路徑損耗指數.

1.3 計算模型

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

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

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

本地完成任務i所消耗的能耗:

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

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

其中,f0表示服務器的恒定CPU頻率.

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

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

由文獻[15]可知式(9)是關于的凸函數.

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

將任務從設備S傳輸到設備2的傳輸時間:

將任務從設備S傳輸到設備2的傳輸能耗:

1.4 依賴模型

由于設備S的第ms個 任務的輸出作為設備2第k個任務的輸入, 所以要綜合考慮設備S第ms個任務和設備2第k個任務的位置關系. 通過綜合分析, 設備S的第ms個任務和設備2的第k個任務的位置關系都有4種:當設備S第ms個 任務和設備2第k個任務都在本地執行時, 第k個任務的輸入依賴于第ms個任務的輸出, 由于兩設備都支持D2D技術, 所以設備之間可以直接通信,設備S不必將第ms個任務的輸出先傳遞到邊緣服務器,然后再又服務器傳遞到設備2, 節省了時間和能耗, 此時只有設備間的傳輸時間和能耗; 當設備S第ms個任務和設備2第k個任務都在服務器上執行時, 此時設備沒有傳輸時間和能耗的損耗; 當第ms個任務在本地執行時, 當第k個任務在服務器上執行時, 由于第k個任務的輸入依賴于第ms個任務的輸出, 此時設備S需要將第ms個任務的輸出傳輸到服務器, 有上傳時延和能耗; 當第ms個 任務在邊緣服務器執行, 第k個任務在本地執行時, 此時設備S需要將第ms個任務的輸出從服務器傳輸到設備2, 此時需要下載時延.

1.5 問題公式化

由以上分析可知, 設備S的任務完成時間為:

由于設備間任務的依賴關系, 在式(14)的最后一行關系式中描述了設備間任務的依賴關系. 當設備S第ms個任務和設備2的第k個任務都在本地執行時, 則設備之間需要傳輸能耗當設備S第ms個任務在本地執行, 而設備2的第k個任務在服務器上執行時, 則需要上傳能因此設備s的能耗為:

由于設備2的第k個任務輸入依賴于設備S的第ms個 任務和設備2第k–1任務的輸出, 當設備S第ms個任務和設備2的第k個任務都在本地執行時, 設備間需要傳輸時間當設備S第ms個任務在服務器執行, 而設備2的第k個任務在本地執行時, 則需要下載時間當設備S第ms個任務在本地執行, 而設備2的第k個任務在服務器上執行時, 則需要上傳時間因此設備2的第k個任務等待設備S的第ms個任務的輸出時間為:

等待設備2第k–1個任務的輸出時間:

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

設備2消耗的能耗為:

設備總性能指標為:

所以問題公式化為式(20):

其中,Ppeak表示設備發射功率的峰值,fpeak表示設備CPU計算能力的峰值. 由式(5), 式(8), 式(11)可知所以式(20)可以轉化為:

由于含有二進制變量ai,j, 所以問題是非凸的, 但當固定ai,j時, 原來的非凸問題就會轉化為關于的凸問題.

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

假設固定ai,j, 則非凸問題P(2) 轉化為關于的凸問題P(3):

問題P(3)的拉格朗日表示為:

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

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

算法1. 固定卸載決策下求解最佳資源分配算法λsλ2 α pre 1. 輸入: 給定大于0的 , , 步長 和精度值p*,f*2. 輸出:3. While True:fi,j 4. 根據最佳CPU頻率的閉合表達式(24)計算pi,j 5. 根據最佳發射功率的閉合表達式(25)計算fi,j pi,j Twait s Twait 2 6. 根據 和 分別計算 , 和目標值t=max{Twait s ,Twait2 }7.λs 8. 根據梯度下降算法, 分別更新 的值|Twait s -Twait2 |＜pre 9. 如果 :10. 退出循環11. End

3 優化卸載決策

在第2節中, 給定卸載決策, 可以得出最佳資源分配, 需要搜索 2m1×n×m3×···×ms次卸載決策, 然后從中選擇最小目標的卸載決策. 但是隨著任務任務的增多, 這種遍歷搜索方法是行不通的, 復雜度會很高. 基于此提出了一種降低復雜度的線性搜索算法, 可以在線性時間內獲得最佳卸載決策.

3.1 一次爬升策略

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

證明: 由于文章篇幅限制, 并且有許多文獻都有證明了一爬策略, 這里就不再證明.

3.2 基于一爬策略的線性搜索算法

在本小節中, 借鑒了文獻[16]的思想, 同時基于一次爬升策略提出了一種低復雜度的線性搜索算法, 來優化卸載決策. 首先根據式(27)證明所有卸載點共享最小加權和點, 然后在找到最小加權和點的基礎上尋找入口任務, 只需將兩點之間的任務包括兩點, 都卸載到服務器, 如圖3所示.

圖3 一次爬升策略

公式如下, 設備有m個任務:

其中, ηi表 示任務i到最小加權和點o的 最佳性能,η(i,o)表示任務從入口任務i到出口任務o的加權和.eu: 傳輸能耗,el: 本地能耗,tu: 上傳時間,tc: 在服務器上的執行時間,td: 下載時間,tl: 本地執行時間, βE和 βT分別代表權重.

定理2. 所有卸載點共享最小加權和點o.

證明: 假設當任務i=j時最小加權和點為o,1≤j≤o≤m, 那么j+1 的最小加權和點也是o.

當i=j, 卸載任務j時:

卸載任務j,j+1時:

卸載任務j,j+1,j+2 , …,o時:

卸載任務j,j+1, …,m時:

因為當i=j時 , 最小加權和點是o, 所以:

當i=j+1, 卸載任務j+1時:

卸載任務j+1,j+2 , …,o時:

卸載任務j+1,j+2 , …,m時 :

當i=j, 最小加權和點為o, 仔細觀察可以得出當i=j+1時 , 最小加權和點也是o, 即:

從而得出所有卸載點共享最小加權和點o, 證畢.

從定理2可知, 只需遍歷i=1就可以找到最小加權和點o, 同時得到此時的最佳性能為η1=η(1,o), 然后根據ηi與ηi-1的關系, 求出η1,···,ηo, 通過式(37)找到入口任務h.

基于定理1和定理2, 可以通過提出的線性搜索算法快速地找到最小加權和點o和入口任務h. 算法2給出了尋找最優的入口任務h和最佳性能點o的算法, 初始時, 任務全部在本地執行. 因此只需要枚舉滿足一次爬政策的卸載決策, 而不必遍歷所有 2m1×n×m3×···×ms個卸載決策. 對于每個設備, 根據算法2首先遍歷m個任務尋找到最佳性能點o, 然后再根據每個卸載點的關系,求出每個卸載點到最佳性能點o的值, 選出最小的作為卸載點, 算法的復雜度為O (m). 其他設備類似. 所以只需O(m1×n×m3×···×ms)的復雜度就可以找到最優的卸載策略. 隨著任務數的增多, 基于單爬策略的線性搜索算法的性能遠遠優于暴力搜索算法, 復雜度更低, 算法2描述如下.

算法2. 低復雜度線性搜索算法η(1,1) ηmin=η(1,1)o 1. 輸入: 根據式(33)計算令 , =1 ho 2. 輸出: ,i m 3. For ←1 to :f* p*4. 根據算法1計算出最優 和5. 然后分別計算設備能耗和時間η(1,i)6. 根據能耗、時間和式(26)計算η(1,i) ηmin 7. If ＜ :ηmin=η(1,i)o=i 8.9. End i o 10. 找到=1時的最小加權和點η1=ηmin 11.j o 12. For ←2 to :ηj ηj-1 ηj 13. 根據 與 的關系公式計算出 的值14. End ηh=max{η1,···,ηo} h 15. 根據公式 選出入口任務

4 實驗評估

在這一節, 將進行數值模擬來評估所提的卸載算法, 關注的性能指標是兩設備的總性能(時延和能耗的加權和最小), 用ETC表示, 其中每個設備的性能用設備完成任務所消耗的能耗和時間的加權和表示, 實驗數據值的大小參考了文獻[14]進行了設置.

圖4為每個設備的任務調用圖, 每個節點代表一個任務, 節點權值為完成此任務的計算量, 邊權值表示輸入和輸出數據的大小. 這里將設備1、設備2和設備3的實際任務數量分別設置為3、4和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),Li,3=[0, 65.5, 86.4, 158.6, 96.6, 0](Mcycles).

圖4 實驗模型和參數

根據第3節列出的信道增益公式, 公式中的一些參數設置為:g=4.11表示天線增益,Fc=915 MHz表示載波頻率,dr表示距離,r=1,2,3,(1,2),(3,2)對于設備1、設備2和設備3到服務器的距離d1、d2、d3的值別為100 m、100 m和100 m.設備1到設備2和設備3到設備2之間的距離d(1,2)、d(3,2)的值分別為10 m和10 m,pl=3表示路徑損耗指數. 這里將每個設備的時間和能耗權重分別設置為0.05, 0.95, 0.1, 0.9, 0.02, 0.98.

在圖5中, 首先進行了本文所提的算法和一爬策略枚舉搜索算法的比較. 通過圖5可以觀察到, 隨著任務數的增多獲得最佳卸載策略所花費的時間, 本文所提算法的性能要優于一爬枚舉搜索算法. 在相同的任務數下, 本文所提的算法獲得最優卸載策略的時間明顯小于一爬策略枚舉搜索算法明.

圖5 兩種算法對比曲線圖

接下來, 本文給出了當d1、d2和d(1,2)變化時, 不同算法下設備的性能, 其中設置=0.0 5、=0.1和0.02. 為了進行性能比較, 考慮了3個次優算法作為基準. 第1種算法被稱為所有任務卸載, 其中將3個設備中的所有任務卸載到邊緣邊緣服務器上執行. 對于第2種算法被稱為所有任務本地執行, 3個設備中的所有任務都在本地執行. 此外, 本文將沒有D2D技術支持稱為第3種算法, 也算是文獻[14]算法的一種實現, 其中每個設備最小化自己的性能ETC.

從圖6(a)可以觀察到, 當固定其他距離時, 隨著距離d1越來越大, 本文所提算法要優于另外3種卸載算法, 性能更好. 而任務全部在本地執行算法和本文所提算法性能都沒有變化, 是因為對于任務全部在本地執行算法, 此時設備1的第m個任務與設備2的第k個任務都在本地執行, 而兩個設備都支持D2D技術, 可以直接進行通信, 所以距離d1增大, 對于任務全部在本地執行的性能是沒有影響, 而本文所提的算法獲得的最優卸載決策設備1的任務也都是在本地執行, 所以也不受距離d1變化的影響. 另外兩種算法, 所有任務卸載和無D2D技術支持算法都隨著距離的增大, 性能越來越差, 因為當距離d1增大時, 卸載任務到服務器需要花費更高的傳輸時延和能耗. 同時也可以觀察到, 當服務器和設備距離小于160 m時, 全部卸載算法要優于無D2D技術支持算法, 因為服務器的性能更好, 設備距離服務器更近時, 將任務全部卸載到服務器, 能獲得更短的時延和更低的能耗. 但不管距離如何增大, 本文所提算法都要優于其他算法.

圖6(b)顯示了距離d2變化對設備性能的影響. 從圖中可以觀察到本文所提算法、全部在服務器執行算法和無D2D技術支持算法, 設備ETC性能都隨著距離的增加而增加. 雖然隨著距離的增加, 性能變差, 但是本文所提算法還是優于服務器執行算法和無D2D技術支持算法. 同時從圖中可以觀察到, 當距離小于130 m左右時, 全部卸載算法還要優于無D2D技術支持算法. 而全部在本地執行算法, 總的ETC不變

圖6 與其他算法的對比

圖6(c)顯示了距離d(1,2)變化對設備性能的影響.對于任務全部在本地執行算法和本文所提算法有明顯的影響, 因為此時設備1的第m個任務與設備2的第k個任務都在本地執行, 而兩個設備都支持D2D技術,兩設備可以直接進行通信. 所以隨著距離d(1,2)的增大,任務全部在本地執行算法和本文所提算法性能越來越差, 但本文所提算法還是優于全部在本地執行算法. 另一個方面也可以得出, 當兩設備間距離更近時, 設備間直接通信越節省時間和能耗. 而對于全部卸載算法和無D2D技術支持算法, 由于本次設備1的第m個任務與設備2的第k個任務都在服務器上執行, 所以距離d(1,2)的變化, 對于這兩種算法都不受影響. 類似的當d3和d(3,2)變 化時, 能夠得到與d1和d(1,2)變化時類似圖6(a)和圖6(c)的結果, 這里不再過多敘述.

通過以上對比分析, 本文所提的算法明顯優于其他基準算法, 同時與D2D技術協作可以顯著提高系統的性能.

5 結論與展望

本文研究了MEC與D2D技術協作系統環境下不同設備之間具有任務依賴性的最優的資源分配和優化任務卸載決策問題, 來最小化設備的能耗和任務完成時間的加權和, 為了解決該問題, 提出了一種低復雜度的在線任務卸載算法, 獲得了最優計算卸載策略. 最后通過數值實驗表明, 本文所提的算法明顯優于其他基準算法. 下一步將對多設備多服務器場景進行研究.