設(shè)備間任務(wù)依賴的最佳卸載決策和資源分配

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

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

0 引 言

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

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

然而以上文獻(xiàn)都僅考慮了單個(gè)設(shè)備上任務(wù)的卸載情況。對(duì)于不同設(shè)備之間任務(wù)具有依賴性的研究非常少，幾乎沒有。實(shí)際上，在不同設(shè)備上執(zhí)行的任務(wù)通常也是具有相關(guān)依賴性的。文獻(xiàn)[14]雖然考慮了MEC系統(tǒng)環(huán)境下兩個(gè)不同設(shè)備之間的任務(wù)相關(guān)性，但沒有考慮與D2D技術(shù)進(jìn)行協(xié)作來優(yōu)化系統(tǒng)性能。雖然業(yè)內(nèi)也在MEC環(huán)境中引入了D2D技術(shù)來優(yōu)化系統(tǒng)性能，但是對(duì)于MEC與D2D技術(shù)協(xié)作網(wǎng)絡(luò)環(huán)境中不同設(shè)備任務(wù)之間任務(wù)具有相關(guān)性的研究，就作者目前所知，還沒有相關(guān)文獻(xiàn)對(duì)此方面進(jìn)行研究。因此該文針對(duì)此方面，同時(shí)在文獻(xiàn)[14]的基礎(chǔ)上進(jìn)行了研究，聯(lián)合優(yōu)化了設(shè)備任務(wù)完成時(shí)延和能耗，在任務(wù)執(zhí)行時(shí)延和設(shè)備能耗之間進(jìn)行權(quán)衡，尋找一個(gè)平衡點(diǎn)使得系統(tǒng)性能最優(yōu)。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

考慮了兩個(gè)設(shè)備的MEC與D2D協(xié)作網(wǎng)絡(luò)。圖1為MEC與D2D協(xié)作網(wǎng)絡(luò)系統(tǒng)模型，其中d1和d2分別表示設(shè)備1、設(shè)備2與MEC服務(wù)器之間的距離，d3表示設(shè)備1和設(shè)備2之間的距離。

圖1 MEC與D2D協(xié)作網(wǎng)絡(luò)系統(tǒng)模型

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

圖2 不同設(shè)備間調(diào)用圖模型

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

1.2 通信模型

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

上傳速率為：

(1)

其中，pi,j表示設(shè)備j的發(fā)射功率，hi,j表示設(shè)備j到邊緣服務(wù)器的信道增益，σ2表示設(shè)備的噪聲功率。

下載速率為：

(2)

其中，p0表示邊緣服務(wù)器的固定發(fā)射功率。

設(shè)備1與設(shè)備2之間的傳輸速率為(設(shè)備1第m個(gè)任務(wù)的輸出與設(shè)備2的第k個(gè)任務(wù)有關(guān))：

(3)

信道增益為：

(4)

其中，g表示天線增益，F(xiàn)c表示載波頻率，dr表示距離，pl表示路徑損耗指數(shù)。

1.3 計(jì)算模型

下面給出了執(zhí)行和傳輸任務(wù)的時(shí)間和能耗。

本地執(zhí)行任務(wù)i的完成時(shí)間為：

(5)

其中，fi,j表示執(zhí)行任務(wù)i的CPU計(jì)算能力。

本地完成任務(wù)i所損失的能耗為：

(6)

其中，k是取決于芯片架構(gòu)的有效開關(guān)電容參數(shù)，是固定常數(shù)。

服務(wù)器執(zhí)行任務(wù)i的完成時(shí)間為：

(7)

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

將任務(wù)i從設(shè)備傳輸?shù)椒?wù)器的上傳時(shí)間為：

(8)

將任務(wù)i從設(shè)備傳輸?shù)椒?wù)器的傳輸能耗為：

(9)

從服務(wù)器返回到設(shè)備的下載時(shí)間為：

(10)

將任務(wù)從設(shè)備1傳輸?shù)皆O(shè)備2的傳輸時(shí)間為：

(11)

將任務(wù)從設(shè)備1傳輸?shù)皆O(shè)備2的傳輸能耗為：

(12)

1.4 依賴模型

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

1.5 問題公式化

由以上分析可知，設(shè)備1的任務(wù)完成時(shí)間為：

(13)

(14)

(15)

等待設(shè)備2第k-1個(gè)任務(wù)的輸出時(shí)間為：

(16)

設(shè)備2的任務(wù)完成時(shí)間為：

(17)

設(shè)備2消耗的能耗為:

(18)

兩個(gè)設(shè)備總性能指標(biāo)為：

(19)

(20)

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

s.t.

(21)

s.t.

(22)

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

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

(23)

其中，λ和μ都是不小于零的表示與相應(yīng)約束相關(guān)聯(lián)的對(duì)偶變量，λ*和μ*表示最佳對(duì)偶變量，則能推導(dǎo)出每個(gè)設(shè)備的最佳CPU頻率和發(fā)射功率的閉合表達(dá)式如下：

(24)

(25)

其中，

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

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

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

2輸出：p*,f*

3 while True:

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

5根據(jù)最佳發(fā)射功率的閉合表達(dá)式(25)計(jì)算pi,j

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

10退出循環(huán)

11 End

3 優(yōu)化卸載決策

在第2小節(jié)中，給定卸載決策，可以得出最佳資源分配，需要搜索2(m+n)次卸載決策，然后從中選擇最小目標(biāo)的卸載決策。但是隨著任務(wù)m或n的增多，這種遍歷搜索方法是行不通的，復(fù)雜度會(huì)很高?；诖颂岢隽艘环N降低復(fù)雜度的在線任務(wù)卸載算法,可以在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)卸載決策。本節(jié)首先證明最優(yōu)卸載決策具有連續(xù)性，然后在此基礎(chǔ)上提出了一種降低復(fù)雜度的優(yōu)化算法。

3.1 一次爬升策略

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

證明：略。

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

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

圖3 一次爬升策略

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

(26)

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

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

算法2：在線搜索算法。

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

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

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

4 Fori<----1 tom:

5 Forj<---itom:

6計(jì)算出最優(yōu)f*和p*，然后計(jì)算設(shè)備的能耗和完成時(shí)間

7根據(jù)能耗、時(shí)間和加權(quán)和公式計(jì)算設(shè)備的加權(quán)和η(i,j)

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

9ηmin=η(i,j)

10i*=i

11j*=j

12 End

13 End

4 實(shí)驗(yàn)評(píng)估

在這一小節(jié)，將進(jìn)行數(shù)值模擬來評(píng)估所提的卸載算法，關(guān)注的性能指標(biāo)是兩設(shè)備的總性能，用ET表示，其中每個(gè)設(shè)備的性能用設(shè)備完成任務(wù)所消耗的能耗和時(shí)間的加權(quán)和表示。為了方便與文獻(xiàn)[14]算法進(jìn)行比較，實(shí)驗(yàn)數(shù)據(jù)值的大小參考文獻(xiàn)[14]進(jìn)行了設(shè)置。接下來，將會(huì)用最優(yōu)卸載算法和文獻(xiàn)[14]中算法進(jìn)行對(duì)比分析。

圖4為每個(gè)設(shè)備的任務(wù)調(diào)用圖，每個(gè)節(jié)點(diǎn)代表一個(gè)任務(wù)，節(jié)點(diǎn)權(quán)值為完成此任務(wù)的計(jì)算量，邊權(quán)值表示輸入和輸出數(shù)據(jù)的大小。這里將設(shè)備的任務(wù)數(shù)量設(shè)置為m=3和n=5，服務(wù)器的發(fā)射功率固定p0為1 W，每個(gè)設(shè)備的發(fā)射功率峰值ppeak為0.1 W，邊緣服務(wù)器的CPU頻率fc和每個(gè)設(shè)備的CPU頻率峰值fpeak分別為1010和108(cycles/s)，噪聲功率σ2為10-7W，k是取決于芯片架構(gòu)的有效開關(guān)電容參數(shù)，是固定常數(shù)，這里設(shè)置為10-26。此外設(shè)置帶寬W為2 MHz，對(duì)于每個(gè)設(shè)備上任務(wù)的計(jì)算量大小設(shè)置為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 實(shí)驗(yàn)?zāi)Ｐ秃蛥?shù)

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

從圖5中的(a)和(b)可以觀察到，當(dāng)固定d3和d2或固定d3和d1時(shí)，隨著d1或d2距離的增大，該文提出的算法要優(yōu)于文獻(xiàn)[14]提出的算法，因?yàn)樵谥С諨2D技術(shù)的MEC系統(tǒng)中，設(shè)備1的第m個(gè)任務(wù)和設(shè)備2的第k個(gè)任務(wù)都在本地執(zhí)行，設(shè)備間之間可以直接通信，避免了在不支持D2D技術(shù)的MEC系統(tǒng)中需要先將任務(wù)卸載到邊緣服務(wù)器，然后從邊緣服務(wù)器下載到設(shè)備2上。所以可以得出支持D2D技術(shù)的MEC系統(tǒng)相比于文獻(xiàn)[14]不支持D2D技術(shù)的MEC系統(tǒng)，節(jié)省了時(shí)間和能耗，系統(tǒng)性能更好

從圖5(c)可以觀察到，當(dāng)d3增大時(shí)，文獻(xiàn)[14]的算法不受d3距離變化的影響,是因?yàn)樵O(shè)備1的第m個(gè)任務(wù)和設(shè)備2的第k個(gè)任務(wù)都在本地執(zhí)行，設(shè)備之間不需直接通信。雖然該文提出的算法受d3的影響，但是通過圖(c)中曲線可以觀察到，在兩設(shè)備間的距離不大于設(shè)備到服務(wù)器之間的距離400 m時(shí)，該文所提的算法還是優(yōu)于文獻(xiàn)[14]所提的算法。而當(dāng)兩設(shè)備間的距離大于400 m時(shí)，任務(wù)卸載到邊緣服務(wù)器上是較好的選擇，因?yàn)檫吘壏?wù)器的性能要比設(shè)備的性能好，將任務(wù)卸載到邊緣服務(wù)器能節(jié)省能耗和時(shí)間?，F(xiàn)實(shí)中也可以知道，當(dāng)設(shè)備間的距離遠(yuǎn)大于設(shè)備到服務(wù)器之間的距離時(shí)，當(dāng)然是卸載到服務(wù)器更好，但當(dāng)設(shè)備間距離較近時(shí)，卸載到設(shè)備是更好的選擇。

(a)

5 結(jié)束語

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