無人機輔助的服務緩存邊緣計算最優(yōu)計算卸載決策與資源分配

田賢忠,閔 旭,周 璐

(浙江工業(yè)大學 計算機科學與技術學院,杭州 310000)

1 引 言

移動邊緣計算(MEC)是5G技術的核心技術之一,它通過在接入網(wǎng)(如AP、基站等)的邊緣部署服務器,使其更靠近物聯(lián)網(wǎng)設備[1,2].因此,可以有效減少任務的傳輸時延,以及降低了設備的能耗.在MEC系統(tǒng)中,邊緣服務器的部署會對系統(tǒng)性能帶來很大影響.目前,大量研究采用的是靜態(tài)邊緣服務器進行部署.靜態(tài)邊緣服務器的部署,一方面,由于服務器部署的靜態(tài)性,進而服務的覆蓋范圍是有限的,導致在服務范圍以外的區(qū)域不支持任務的卸載;另一方面,如果增加邊緣服務器的部署,即密集地部署邊緣服務器,則會增加成本,不切實際.因此,以無人機輔助的動態(tài)MEC服務器部署方案被納入考慮[3,4].

無人機輔助的MEC服務器部署方案通過把邊緣服務器搭載在無人機上,可以根據(jù)物聯(lián)網(wǎng)設備以及各設備上計算任務的分布情況實現(xiàn)邊緣服務器的動態(tài)部署.目前,大多數(shù)研究都是針對固定高度的無人機位置,換句話說,邊緣服務器的部署只考慮水平位置,而忽略了高度的影響.這會產生其他問題,一方面,無人機的高度會影響邊緣服務器與物聯(lián)網(wǎng)設備的距離,進而影響邊緣計算系統(tǒng)的傳輸延遲和能耗[5];另一方面,考慮到回傳時無人機的波束寬度影響[6],無人機的高度還會影響到其覆蓋范圍.在高度較小時,其覆蓋半徑主要受波束寬度約束,與高度成正比;在高度較大時,在波束寬度內的節(jié)點也可能超出最大傳輸距離,此時的覆蓋半徑主要由傳輸功率決定.針對這一問題,本文考慮無人機的三維空間位置的部署,將其與覆蓋范圍和傳輸能耗相關聯(lián),探索使系統(tǒng)能耗最低的部署方案.

在邊緣計算系統(tǒng)中,服務緩存的概念早已被提出.服務部署是在邊緣服務器中配置相關應用的數(shù)據(jù)庫,使其需要這些服務的計算任務,能夠在邊緣節(jié)點上進行卸載.針對無人機上的服務緩存問題,物聯(lián)網(wǎng)節(jié)點上的任務并不是可以任意地卸載到無人機上進行計算.也就是說,只有緩存了相應的服務框架,對應的節(jié)點任務才可以進行卸載.無人機的位置部署與服務緩存方案形成兩個相互耦合的問題.針對某一無人機而言,其位置決定了可卸載的節(jié)點空間,而不同的服務緩存又影響著無人機的最佳部署.由于無人機上邊緣服務器的存儲資源有限,如何結合無人機的部署位置,合理地在邊緣服務器上緩存服務也是一個值得研究的問題.

針對以上問題,本文研究了無人機的3D部署、服務緩存、計算卸載以及資源分配等因素對邊緣計算系統(tǒng)性能的影響,提出一種利用無人機輔助的服務緩存邊緣計算最優(yōu)計算卸載決策和資源分配策略.此策略利用優(yōu)化無人機的3D位置以及邊緣服務器中服務合理部署,在滿足任務時延約束的情況下通過最優(yōu)計算卸載決策和資源分配達到最小化能量消耗的目的.本文的主要貢獻如下:1)提出了一種無人機輔助和服務緩存場景下,以最小化能量消耗的目標的無人機3D部署、服務緩存、計算卸載以及資源分配方案;2)建立無人機輔助服務緩存的最小化能量消耗的優(yōu)化模型,并采用遺傳算法雙層優(yōu)化方法求解,上層將無人機3D位置和服務緩存方案放入基因編碼,下層先利用貪心的思想確定資源分配,再將問題轉化為整數(shù)線性規(guī)劃問題進行求解.3)通過仿真實驗評估了本文提出的方法對所求解問題的有效性和優(yōu)越性.仿真結果表明,本文提出的算法可以實現(xiàn)時延、服務緩存、計算資源限制下能耗最低的優(yōu)化部署.

本文的其余部分組織如下:第2部分為相關工作;第3部分介紹系統(tǒng)模型;第4部分對問題建模;第5部分描述解決方案;第6部分顯示仿真實驗結果;第7部分是結論.

2 相關工作

對無人機輔助的邊緣計算的研究可分為兩類:單無人機和多無人機.單無人機方面,ZHAN C等人根據(jù)物聯(lián)網(wǎng)設備的任務和能源預算約束,研究了計算卸載和資源分配以及無人機軌跡的聯(lián)合設計,以最大程度地降低無人機的能耗和完成時間[7].ZHANG T等人提出了一種新的優(yōu)化問題公式,旨在通過優(yōu)化位分配,時隙調度,功率分配以及無人機軌跡設計來最大程度地減少總能耗[8].WAN S等人提出了一種基于李雅普諾夫優(yōu)化的在線邊緣處理調度算法[9].在低數(shù)據(jù)速率的情況下,它傾向于降低邊緣處理器的頻率以節(jié)省能源.在高數(shù)據(jù)速率的情況下,它將智能地分配帶寬以進行邊緣數(shù)據(jù)卸載.YU Z等人通過共同優(yōu)化無人機位置,通信和計算資源分配以及任務拆分決策來最小化所有物聯(lián)網(wǎng)設備的服務延遲和無人機能耗的加權總和[10].而LI M等人則通過共同優(yōu)化無人機軌跡,用戶發(fā)射功率和計算負載分配來最大化無人機能源效率[11].這些工作都是從單個無人機進行考慮,并且軌跡設計時默認為固定高度,只進行水平位置的變化.在多無人機方面.YANG L等人為了平衡無人機的負載,提出了基于差分進化的多無人機部署機制,將問題建模為廣義分配問題,然后通過近似最優(yōu)解解決[12].ZHANG J等人在多無人機輔助的MEC系統(tǒng)中提出了計算效率最大化的問題,其中考慮了計算位和能耗.基于部分計算卸載模式,聯(lián)合優(yōu)化了用戶關聯(lián),中央處理器周期頻率,功率和頻譜資源的分配以及無人機的軌跡調度[13].多無人機方向的工作較少,在部署方案中仍未考慮高度的影響,并且,隱含假設均為無人機可處理各種類型的任務.

邊緣節(jié)點緩存服務是減輕背景網(wǎng)絡和中心云負擔的有效途徑.BORST S等人提出了基于流行度的內容分發(fā)網(wǎng)絡分布式緩存算法[14].ZHANG S等人提出了一種以用戶為中心的邊緣緩存機制,其中每個用戶由多個邊緣服務器協(xié)同服務,以優(yōu)化服務延遲[15].YANG P等人設計了位置感知邊緣緩存方案,通過預測內容的流行程度來最大化局部命中率[16].和以往工作不同的是,本文將服務緩存應用于無人機輔助的MEC場景中,這使服務緩存策略更為復雜,是一個具有挑戰(zhàn)性的問題.

前面的工作很少考慮無人機輔助的服務緩存邊緣計算系統(tǒng)的場景.本文將結合5G網(wǎng)絡中的服務部署,考慮波束寬度帶來的高度和覆蓋范圍影響,聯(lián)合優(yōu)化無人機3D部署、服務器服務緩存、卸載策略和資源分配策略,實現(xiàn)系統(tǒng)能耗最低的目標.

3 系統(tǒng)模型

圖1 多無人機輔助的MEC系統(tǒng)Fig.1 Multi-UAV-enabled MEC system

用αk,n表示節(jié)點dk是否連接到無人機un,即ak,n∈{0,1},設定每個物聯(lián)網(wǎng)節(jié)點只能連接到一個無人機,則有:

(1)

用βm,n表示第m種服務是否部署在無人機un,即βk,n∈{0,1},A={a1,a2,…,aM}表示每種服務所需容量大小.由于無人機上服務部署有容量限制,則有:

(2)

其中C為無人機上服務器服務緩存的容量限制.

每一個物聯(lián)網(wǎng)節(jié)點dk都有一個要執(zhí)行的計算密集型任務,這些任務被建模為四元組Wk=(Ck,Fk,tk,λk),4個參數(shù)依次為任務大小、處理一位任務數(shù)據(jù)所需CPU周期數(shù)、處理該任務的最大可容忍時延、任務的服務類型.該任務有兩種操作方式:1)本地計算;2)卸載到緩存了服務λk的無人機上計算.

A.本地計算模型

當任務Wk采用本地計算時,計算時延可表示為:

(3)

其中,fk,0表示節(jié)點dk的本地計算資源.

相應的,用于任務Wk的計算能耗可表示為[17]:

Ek,0=η1(fk,0)v-1CkFk,?k=1,2,…,K

(4)

其中,η1為有效電容開關,v為正常數(shù).

B.MEC計算模型

當任務Wk采用計算卸載方式時,任務首先傳輸?shù)綗o人機上,并在其服務器上進行計算,計算結束后,結果再返回給物聯(lián)網(wǎng)節(jié)點.假設每個無人機配備一個定向天線,用θ表示天線的半功率波束寬度.下行鏈路時,相對于主瓣增益,主瓣外可忽略不計.無人機的覆蓋半徑Rn與無人機高度hn、天線半功率波束寬度相關[6],有:

(5)

對于節(jié)點dk,與無人機un的水平距離可表示為:

?k=1,2,…,K,n=1,2,…,N

(6)

顯然,如果節(jié)點dk要將任務卸載至無人機un,節(jié)點dk必須在無人機un的覆蓋范圍內,該約束可表示為:

C3:αk,nLk,n≤Rn,?k=1,2,…,K,n=1,2,…,N

(7)

任務卸載還受服務緩存的影響,有以下約束:

C4:αk,n≤βλk,n,?k=1,2,…,K,n=1,2,…,N

(8)

只有當βλk,n=1,即無人機un緩存了服務λk,節(jié)點dk才能將任務卸載,即αk,n才能取1.

節(jié)點dk與無人機un之間上行鏈路傳輸速率由下式給出[18]:

?k=1,2,…,K,n=1,2,…,N

(9)

其中B為信道帶寬,P為每個節(jié)點的發(fā)射功率,β0為參考距離處的信道功率增益,G0為正常數(shù),N0為噪聲功率譜密度.

在此卸載場景中,由于下行結果數(shù)據(jù)相對較少,本文忽略回傳時間.節(jié)點dk卸載到無人機un所需總時延可表示為:

(10)

其中,fk,n表示無人機un分配給節(jié)點dk的計算資源.考慮節(jié)點的傳輸能耗和服務器的計算能耗.節(jié)點的傳輸能耗等于節(jié)點的發(fā)射功率乘以傳輸時間,故有:

(11)

對應的服務器計算能耗,根據(jù)文獻[19]為:

(12)

4 問題建模

如圖1所示的場景,本文需要解決如下幾個問題:

在滿足任務時延要求得前提下,物聯(lián)網(wǎng)設備中的任務是在本地計算還是上傳給無人機上的邊緣服務器計算?

在計算總資源確定的條件下,如何給各物聯(lián)網(wǎng)設備分配合適的計算資源?

如何部署無人機的3D位置,使得整個邊緣計算系統(tǒng)性能最佳?

在服務器存儲資源有限的約束下,如何合理部署服務緩存?

本文以系統(tǒng)的能耗為優(yōu)化目標,包括本地計算能耗和MEC計算模型下相關能耗.通過需要聯(lián)合優(yōu)化無人機的3D部署、服務緩存、任務分配、計算資源分配,以最小化系統(tǒng)能耗.該問題可表述為:

(13)

C3:αk,nLk,n≤Rn,?k=1,2,…,K,n=1,2,…,N

C4:αk,n≤βλk,n,?k=1,2,…,K,n=1,2,…,N

C5:αk,0Tk,0≤tk,?k=1,2,…,K

C6:αk,nTk,n≤tk,?k=1,2,…,K,n=1,2,…,N

其中,參數(shù)μ用于調整服務器計算能耗所占比重,由于服務器的能量補充相對容易,可考慮降低服務器能耗的重要程度.約束C5、C6為每個任務的時延限制.C7是指服務器的最大計算資源約束,卸載到同一架無人機服務器上的節(jié)點所分配的計算資源之和不能超過fmax.

5 解決方案

顯然,在第4節(jié)中提出的問題是NP-hard的,并且該問題是非凸非線性的.傳統(tǒng)的優(yōu)化方法不好解決,基于種群的啟發(fā)式搜索算法具有很好解決這一問題的潛力.將目標變量編碼到種群的基因序列中是一種自然的想法,然而,本文需要優(yōu)化無人機和服務的部署、卸載決策、資源分配,決策變量的數(shù)量隨著無人機個數(shù)和節(jié)點個數(shù)的增加而增加.在本文中考慮了大量的物聯(lián)網(wǎng)節(jié)點,這對遺傳算法而言是一個大規(guī)模最佳化問題[20].

為此,本文提出了一種基于遺傳算法框架的雙層優(yōu)化算法(Optimization algorithm of placement of UAV and service based on genetic algorithm,OAP)來解決這個問題.首先,僅將無人機3D位置、服務部署方案編碼于染色體中;其次,根據(jù)每一確定的染色體,即確定的無人機3D位置和服務部署方案,在內層利用線性規(guī)劃方法確定物聯(lián)網(wǎng)節(jié)點的卸載策略和無人機的資源分配;然后在外層進行染色體的選擇、交叉和變異等種群操作,確定無人機3D位置、服務部署方案.

5.1 染色體編碼

本文采用二進制編碼對變量lun和βm,n進行編碼,每一個基因片段對應無人機的3D位置部署和無人機服務器上的服務部署.如圖2所示,共有N個基因片段,與無人機數(shù)量相對應.在每一個片段中,前3個變量為無人機的3D坐標,轉換為二進制編碼所占位數(shù)與精度相關,后續(xù)M位為服務部署,分別代表對應服務是否部署在無人機服務器上.假定位置部署每個參數(shù)占用length個位,而βm,n∈{0,1},因此,每一條染色體長度為N×(M+3length).

圖2 染色體編碼Fig.2 Chromosome coding

5.2 卸載策略與資源分配求解

由于目標函數(shù)是最小化問題,本文將優(yōu)化目標能耗的倒數(shù)作為適應度函數(shù).在目標函數(shù)中,無人機的3D位置部署和服務器的服務部署已由染色體確定,因此,可將優(yōu)化問題轉化為:

(14)

通過觀察目標函數(shù)(14),可以發(fā)現(xiàn),無論是本地計算還是卸載到無人機,所需的計算能耗與分配的計算資源成正比.因此,在卸載策略確定的情況下,可以在滿足時延約束的條件下,盡可能少地分配計算資源.若節(jié)點dk進行本地計算(即αk,0=1),由公式(3)和約束C5可以得到:

(15)

若節(jié)點dk將任務卸載到無人機un進行計算(即αk,n=1),由公式(10)和約束C6可以得到:

(16)

為了使目標能耗最小,可以在不等式(14)、(15)中取等號,從而可求得最優(yōu)的資源分配策略.

在此基礎上,可以將優(yōu)化問題轉化為:

s.t.C1,C3,C4,C7

(17)

易知該問題為線性規(guī)劃問題,本文采用分支定界法進行求解.為了應對出現(xiàn)少數(shù)節(jié)點沒有可行計算方案的情況,本文將其設置為按照本地最大計算資源進行計算,最終計算能耗以其十倍作為懲罰并計入目標值.

5.3 無人機位置與服務部署求解

5.2中求得的是針對某一確定的染色體的最優(yōu)計算卸載與資源分配策略,即在無人機位置與服務部署確定的情況下的最優(yōu)計算卸載與資源分配策略.進一步,通過染色體的選擇、交叉和變異等操作,實現(xiàn)最優(yōu)無人機位置以及緩存服務部署.在執(zhí)行選擇操作時,采用適應度比例算法計算選擇概率.在該方法中,各個個體被選擇的概率和其適應度值成比例.選擇方法采用基本的輪盤賭選擇策略.在此方法中先按個體的選擇概率產生一個輪盤,輪盤每個區(qū)的角度與個體的選擇概率成比例,然后產生一個隨機數(shù),它落入輪盤的哪個區(qū)域就選擇相應的個體交叉.染色體的交叉僅發(fā)生的等位基因上.例如:片段1只能和片段1進行交換.交叉概率由參數(shù)pc控制.突變是指染色體某位發(fā)生0和1的翻轉,突變概率由參數(shù)pm控制.算法流程如表1所示.

表1 算法流程Table 1 Algorithm steps

通過交叉和變異產生的新個體可能不滿足服務器服務緩存容量的要求,因此,在選擇操作時,根據(jù)公式(2)確定其是否滿足約束并去除不符合約束的個體.然后再進行選擇操作.

6 性能分析

在這一部分,本文使用MATLAB r2020a進行仿真實驗,以驗證所提出算法的有效性.

6.1 實驗設置

在表2中給出了無人機輔助MEC系統(tǒng)的參數(shù)設置[21].

表2 參數(shù)設置Table 2 Parameter settings

假定系統(tǒng)在一定寬度的正方形區(qū)域運行工作.為了比較不同算法的性能,本文從不同角度對3種算法進行了對比:

1)其他條件一定時,對比節(jié)點數(shù)不同時各算法的性能.

2)其他條件一定時,對比無人機數(shù)不同時各算法的性能.

3)改變無人機的最大計算資源,對比系統(tǒng)性能.

4)無人機平均緩存服務數(shù)對性能的影響.

為了從能耗的角度評價所提出算法OAP的性能,設計了兩種對比方案.

OAP-H:考慮到無人機高度的影響,在算法OAP-H中,本文固定無人機高度為100m[12].相對于OAP的3D部署來說,OAP-H只用考慮無人機的平面坐標.

OAP-C:考慮到3D空間自由探索的復雜性,在算法OAP-C中,先用K均值聚類算法對場景中節(jié)點進行聚類,確定無人機的平面坐標.在高度這一因素上,與原算法保持一致,在[50,200]的范圍內自由可變.

6.2 結果分析

首先考慮節(jié)點數(shù)對性能的影響.設定場景寬度為500m,N=5,平均服務緩存數(shù)為4,fmax在不同K值下均充足,μ=1,K從100到500.從圖3可以看到,3種算法的能耗都隨著K值的增加不斷升高,而算法OAP始終優(yōu)于另外兩種算法.隨著K的增大,系統(tǒng)本身的能耗是增加的趨勢;由于覆蓋半徑和服務緩存的限制,會有更多的節(jié)點不能被無人機所服務,也就有更多的任務進行本地計算,而OAP算法能更優(yōu)地對節(jié)點進行覆蓋提供服務,使目標值最低.

圖3 節(jié)點數(shù)的影響Fig.3 Impact of the number of nodes

無人機數(shù)量對性能的影響.設定場景寬度為500m,K=300,平均服務緩存數(shù)為4,fmax在不同N值下均充足,μ=1,N從1到10.從圖4可以看到,3種算法的能耗都隨著N值的增加不斷降低,而算法OAP始終優(yōu)于另外兩種算法.可以看到,在無人機數(shù)1-4時,OAP和OAP-C能耗下降較快,在5-10時兩者能量消耗已趨于平穩(wěn),這是因為隨著無人機數(shù)量的增加到5及以上時,無人機對場景中節(jié)點的覆蓋比較全面,再增加無人機不能再提升其覆蓋程度.而算法OAP-H在無人機數(shù)到10及以上才實現(xiàn)對區(qū)域內節(jié)點的基本覆蓋.在無人機數(shù)較小時,算法OAP展現(xiàn)除了明顯的優(yōu)勢.

圖4 無人機數(shù)的影響Fig.4 Impact of the number of UAV

服務器計算資源的影響.設定場景寬度為500m,K=300,N=5,平均服務緩存數(shù)為4,μ=1,fmax從0到18GHz.從圖5可以看到,隨著計算資源的增加,系統(tǒng)能耗不斷減少.在0-10GHz,無人機受計算資源限制,不能為覆蓋區(qū)域內的節(jié)點提供充足的服務,更多的節(jié)點選擇本地計算,導致能耗較大.當計算資源超出10GHz,資源較為充足,繼續(xù)增加資源卻沒有服務更多的節(jié)點可服務,能耗逐漸平穩(wěn).值得注意的是,服務器計算資源為0時,即所有任務都在本地計算,總體能耗遠高于有足夠資源時的3種算法,也說明了算法的有效性.

圖5 計算資源的影響Fig.5 Impact of computation resource

平均服務緩存數(shù)的影響.無人機的服務緩存與其能否為某一節(jié)點提供服務相關.設定區(qū)域寬度為500m,K=100,N=5,,fmax在不同情況下均充足,μ=1,平均服務緩存數(shù)從1到5,如圖6所示.服務緩存數(shù)的增加,意味著在無人機覆蓋區(qū)域內有更多類型的節(jié)點可以選擇卸載,達到能耗降低的效果.特別是平均服務數(shù)為5時,這和服務種類數(shù)M相同,表明區(qū)域內的各服務類型節(jié)點均可選擇卸載,能耗達到最低.此外,圖6中仍然顯示了算法OAP較其余兩者更為優(yōu)越.

圖6 服務數(shù)的影響Fig.6 Impact of the number of service

7 總 結

邊緣計算為計算密集型、時延敏感型任務提供了新的解決思路,而無人機技術解決了固定基站在復雜環(huán)境面臨的困境.本文針對多無人機輔助的服務緩存MEC系統(tǒng),以最小化能耗為目標,用遺傳算法框架求解無人機的3D部署和服務器上的服務部署,用貪心的思想確定資源分配,用整數(shù)線性規(guī)劃求解卸載策略.此外,在仿真實驗中,設計了復雜程度更低、性能較優(yōu)的OAP-C算法.最后,仿真結果驗證了算法的有效性和優(yōu)越性.在未來的研究中,我們將關注無人機輔助MEC場景中的時延優(yōu)化、動態(tài)調整部署、無人機軌跡優(yōu)化等相關內容.