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

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

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

隨著物聯(lián)網(wǎng)技術(shù)和5G技術(shù)的發(fā)展, 產(chǎn)生的各種新型應(yīng)用, 對網(wǎng)絡(luò)的時(shí)延和帶寬提出了更高的要求. 但由于終端設(shè)備的計(jì)算和存儲能力的限制, 無法處理和存儲如此龐大的數(shù)據(jù). 因此移動邊緣計(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í)延和能耗.

對于計(jì)算卸載技術(shù), 目前已經(jīng)出現(xiàn)了很多研究成果對其進(jì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ù)雜度的動態(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ù)的卸載情況. 對于不同設(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)性能,但是對于MEC與D2D技術(shù)協(xié)作網(wǎng)絡(luò)環(huán)境中不同設(shè)備任務(wù)之間任務(wù)具有相關(guān)性的研究, 就作者目前所知, 還沒有相關(guān)文獻(xiàn)對此方面進(jìn)行研究. 同時(shí), 在優(yōu)化卸載決策方面文獻(xiàn)[14]提出的算法復(fù)雜度仍然很高, 本文提出的線性搜索算法更進(jìn)一步的優(yōu)化了卸載決策, 并且本文將場景擴(kuò)展到多設(shè)備. 因此, 本文在文獻(xiàn)[14]的基礎(chǔ)上進(jìn)行了進(jìn)一步的優(yōu)化研究, 聯(lián)合優(yōu)化了設(shè)備任務(wù)完成時(shí)延和能耗.

本文在第1節(jié)中對系統(tǒng)進(jìn)行了分析, 建立了通信、計(jì)算和任務(wù)依賴模型. 在第2節(jié)中運(yùn)用凸優(yōu)化方法得到最佳資源分配. 在第3節(jié)中提出了一種降低復(fù)雜度的線性搜索算法來優(yōu)化卸載決策. 最后通過仿真實(shí)驗(yàn)進(jìn)行性能評估.

1 系統(tǒng)模型

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

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

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

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

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

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

1.2 通信模型

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

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

下載速率為:

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

設(shè)備S與設(shè)備2之間的傳輸速率為:

其中,和分別表示設(shè)備S第ms個(gè)任務(wù)的輸出與設(shè)備2的第k個(gè)任務(wù)都在本地執(zhí)行時(shí), 設(shè)備的發(fā)射功率和此時(shí)設(shè)備間的信道增益.

信道增益為:

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

1.3 計(jì)算模型

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

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

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

本地完成任務(wù)i所消耗的能耗:

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

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

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

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

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

由文獻(xiàn)[15]可知式(9)是關(guān)于的凸函數(shù).

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

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

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

1.4 依賴模型

由于設(shè)備S的第ms個(gè) 任務(wù)的輸出作為設(shè)備2第k個(gè)任務(wù)的輸入, 所以要綜合考慮設(shè)備S第ms個(gè)任務(wù)和設(shè)備2第k個(gè)任務(wù)的位置關(guān)系. 通過綜合分析, 設(shè)備S的第ms個(gè)任務(wù)和設(shè)備2的第k個(gè)任務(wù)的位置關(guān)系都有4種:當(dāng)設(shè)備S第ms個(gè) 任務(wù)和設(shè)備2第k個(gè)任務(wù)都在本地執(zhí)行時(shí), 第k個(gè)任務(wù)的輸入依賴于第ms個(gè)任務(wù)的輸出, 由于兩設(shè)備都支持D2D技術(shù), 所以設(shè)備之間可以直接通信,設(shè)備S不必將第ms個(gè)任務(wù)的輸出先傳遞到邊緣服務(wù)器,然后再又服務(wù)器傳遞到設(shè)備2, 節(jié)省了時(shí)間和能耗, 此時(shí)只有設(shè)備間的傳輸時(shí)間和能耗; 當(dāng)設(shè)備S第ms個(gè)任務(wù)和設(shè)備2第k個(gè)任務(wù)都在服務(wù)器上執(zhí)行時(shí), 此時(shí)設(shè)備沒有傳輸時(shí)間和能耗的損耗; 當(dāng)?shù)趍s個(gè)任務(wù)在本地執(zhí)行時(shí), 當(dāng)?shù)趉個(gè)任務(wù)在服務(wù)器上執(zhí)行時(shí), 由于第k個(gè)任務(wù)的輸入依賴于第ms個(gè)任務(wù)的輸出, 此時(shí)設(shè)備S需要將第ms個(gè)任務(wù)的輸出傳輸?shù)椒?wù)器, 有上傳時(shí)延和能耗; 當(dāng)?shù)趍s個(gè) 任務(wù)在邊緣服務(wù)器執(zhí)行, 第k個(gè)任務(wù)在本地執(zhí)行時(shí), 此時(shí)設(shè)備S需要將第ms個(gè)任務(wù)的輸出從服務(wù)器傳輸?shù)皆O(shè)備2, 此時(shí)需要下載時(shí)延.

1.5 問題公式化

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

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

由于設(shè)備2的第k個(gè)任務(wù)輸入依賴于設(shè)備S的第ms個(gè) 任務(wù)和設(shè)備2第k–1任務(wù)的輸出, 當(dāng)設(shè)備S第ms個(gè)任務(wù)和設(shè)備2的第k個(gè)任務(wù)都在本地執(zhí)行時(shí), 設(shè)備間需要傳輸時(shí)間當(dāng)設(shè)備S第ms個(gè)任務(wù)在服務(wù)器執(zhí)行, 而設(shè)備2的第k個(gè)任務(wù)在本地執(zhí)行時(shí), 則需要下載時(shí)間當(dāng)設(shè)備S第ms個(gè)任務(wù)在本地執(zhí)行, 而設(shè)備2的第k個(gè)任務(wù)在服務(wù)器上執(zhí)行時(shí), 則需要上傳時(shí)間因此設(shè)備2的第k個(gè)任務(wù)等待設(shè)備S的第ms個(gè)任務(wù)的輸出時(shí)間為:

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

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

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

設(shè)備總性能指標(biāo)為:

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

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

由于含有二進(jìn)制變量ai,j, 所以問題是非凸的, 但當(dāng)固定ai,j時(shí), 原來的非凸問題就會轉(zhuǎn)化為關(guān)于的凸問題.

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

假設(shè)固定ai,j, 則非凸問題P(2) 轉(zhuǎn)化為關(guān)于的凸問題P(3):

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

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

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

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

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

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

3.1 一次爬升策略

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

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

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

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

圖3 一次爬升策略

公式如下, 設(shè)備有m個(gè)任務(wù):

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

定理2. 所有卸載點(diǎn)共享最小加權(quán)和點(diǎn)o.

證明: 假設(shè)當(dāng)任務(wù)i=j時(shí)最小加權(quán)和點(diǎn)為o,1≤j≤o≤m, 那么j+1 的最小加權(quán)和點(diǎn)也是o.

當(dāng)i=j, 卸載任務(wù)j時(shí):

卸載任務(wù)j,j+1時(shí):

卸載任務(wù)j,j+1,j+2 , …,o時(shí):

卸載任務(wù)j,j+1, …,m時(shí):

因?yàn)楫?dāng)i=j時(shí) , 最小加權(quán)和點(diǎn)是o, 所以:

當(dāng)i=j+1, 卸載任務(wù)j+1時(shí):

卸載任務(wù)j+1,j+2 , …,o時(shí):

卸載任務(wù)j+1,j+2 , …,m時(shí) :

當(dāng)i=j, 最小加權(quán)和點(diǎn)為o, 仔細(xì)觀察可以得出當(dāng)i=j+1時(shí) , 最小加權(quán)和點(diǎn)也是o, 即:

從而得出所有卸載點(diǎn)共享最小加權(quán)和點(diǎn)o, 證畢.

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

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

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

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

在這一節(jié), 將進(jìn)行數(shù)值模擬來評估所提的卸載算法, 關(guān)注的性能指標(biāo)是兩設(shè)備的總性能(時(shí)延和能耗的加權(quán)和最小), 用ETC表示, 其中每個(gè)設(shè)備的性能用設(shè)備完成任務(wù)所消耗的能耗和時(shí)間的加權(quán)和表示, 實(shí)驗(yàn)數(shù)據(jù)值的大小參考了文獻(xiàn)[14]進(jìn)行了設(shè)置.

圖4為每個(gè)設(shè)備的任務(wù)調(diào)用圖, 每個(gè)節(jié)點(diǎn)代表一個(gè)任務(wù), 節(jié)點(diǎn)權(quán)值為完成此任務(wù)的計(jì)算量, 邊權(quán)值表示輸入和輸出數(shù)據(jù)的大小. 這里將設(shè)備1、設(shè)備2和設(shè)備3的實(shí)際任務(wù)數(shù)量分別設(shè)置為3、4和5, 每個(gè)設(shè)備引入了兩個(gè)虛擬任務(wù). 服務(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. 對于每個(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),Li,3=[0, 65.5, 86.4, 158.6, 96.6, 0](Mcycles).

圖4 實(shí)驗(yàn)?zāi)Ｐ秃蛥?shù)

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

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

圖5 兩種算法對比曲線圖

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

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

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

圖6 與其他算法的對比

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

通過以上對比分析, 本文所提的算法明顯優(yōu)于其他基準(zhǔn)算法, 同時(shí)與D2D技術(shù)協(xié)作可以顯著提高系統(tǒng)的性能.

5 結(jié)論與展望

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