無人機移動邊緣計算位置部署與資源分配方案

劉伯陽，楊寧樂，馬 杰,萬奕堯，周繼軍

(1.西安郵電大學 通信與信息工程學院，陜西 西安 710121； 2.北京郵電大學 信息安全中心，北京 100876)

移動邊緣計算(Mobile Edge Computing,MEC)是一項非常有前景的技術(shù)，能夠在網(wǎng)絡(luò)邊緣為用戶提供類似云計算的服務(wù)，從而將用戶從繁重的計算工作中解放出來[1-2]。一般來說，MEC服務(wù)器的部署位置固定，服務(wù)器與用戶之間通信鏈路通常以非視距為主[3-4]，其覆蓋范圍較小。無人機具有機動性高和部署靈活的特點，搭載在無人機上的MEC服務(wù)器與用戶之間通常具備視距鏈路，因此，將MEC服務(wù)器部署在無人機上能夠為地面用戶提供靈活的廣覆蓋服務(wù)[5]。

近年來，無人機輔助的MEC系統(tǒng)受到了越來越多的關(guān)注。文獻[6-7]考慮了無人機同時作為MEC服務(wù)器和中繼節(jié)點為用戶提供服務(wù)的場景，并研究了該場景下無人機與所有用戶總能耗最小問題。文獻[8]通過聯(lián)合優(yōu)化物聯(lián)網(wǎng)設(shè)備的分組以及無人機的服務(wù)順序使無人機的能耗最小化。在文獻[6-8]的基礎(chǔ)上，文獻[9]進一步研究了多無人機協(xié)同場景，并對無人機的空間位置進行優(yōu)化，使用戶與無人機能耗最小。為了提高無人機輔助MEC系統(tǒng)的性能，文獻[10]聯(lián)合優(yōu)化了用戶分組、無人機運行軌跡以及用戶傳輸功率以實現(xiàn)總卸載比特數(shù)最大化。在此基礎(chǔ)上，文獻[11]重點考慮了用戶對時延敏感的場景，通過對無人機的飛行軌跡以及用戶的相關(guān)運行參數(shù)聯(lián)合優(yōu)化，最小化用戶任務(wù)完成時延。為了更有效地評估無人機輔助MEC系統(tǒng)的性能，文獻[12]提出了計算能效的概念并將其定義為用戶計算比特數(shù)與總體能耗的比值。

現(xiàn)有針對無人機輔助的MEC網(wǎng)絡(luò)的研究主要集中在系統(tǒng)如何在計算資源、能耗以及時延約束條件下完成所有用戶的計算任務(wù)等方面。然而，當用戶數(shù)量很大或者用戶任務(wù)計算數(shù)據(jù)量巨大時，考慮無人機能搭載的MEC服務(wù)器重量與體積限制，僅依靠無人機完成所有用戶的計算任務(wù)是不現(xiàn)實的。特別是在物聯(lián)網(wǎng)(Internet of Things,IoT) 場景中，MEC服務(wù)器服務(wù)區(qū)域內(nèi)往往存在大量的接入設(shè)備，并且用戶的位置較為分散，利用無人機為所有用戶提供服務(wù)較為困難。因此，應(yīng)該研究如何合理地優(yōu)化無人機部署位置使其可以服務(wù)盡可能多的地面用戶，即最大化無人機服務(wù)覆蓋范圍，盡可能擴大無人機輔助的MEC網(wǎng)絡(luò)的服務(wù)范圍。

針對以上問題，提出了一種無人機輔助的移動邊緣計算無人機空間部署位置與資源分配優(yōu)化算法，在滿足網(wǎng)絡(luò)計算資源約束與用戶卸載功率約束下，最大化無人機服務(wù)的用戶數(shù)并建立優(yōu)化問題。首先將原始的非凸混合整型優(yōu)化問題松弛為一個連續(xù)非凸優(yōu)化問題，通過固定一些優(yōu)化變量優(yōu)化另外一些優(yōu)化變量進行交替迭代求解。對于過程中建立的非凸子問題，利用連續(xù)凸近似[13]將其轉(zhuǎn)化為凸問題進行求解。最后利用二分法將松弛后的二元整型優(yōu)化變量進行恢復。

1 系統(tǒng)模型

如圖1所示，考慮一個無人機輔助的MEC網(wǎng)絡(luò)。該網(wǎng)絡(luò)中，無人機搭載MEC服務(wù)器為K個位置固定的地面用戶提供計算服務(wù)。令κ={1,2,…,K}表示用戶的集合，其中每個用戶都有任務(wù)等待計算。用戶k(k∈κ)的計算任務(wù)可用數(shù)組(Ik,Ck,tk)表示，其中Ik表示用戶k待計算任務(wù)數(shù)據(jù)量的大小，Ck表示用戶k處理1 bit數(shù)據(jù)需要的中央處理器(Central Processing Unit,CPU)周期數(shù)，tk表示用戶k任務(wù)完成期限。與文獻[6]中采取相同的近似，假設(shè)所有用戶任務(wù)的完成期限均等于無人機的懸停時間tk=T。

圖1 系統(tǒng)模型

1.1 坐標與信道模型

采用三維笛卡爾坐標系，令wk=(xk,yk)表示用戶k的水平坐標，所有的用戶都固定在地面上，即其高度均為0。無人機以固定高度H飛行，其中H為保證無人機能夠避開服務(wù)區(qū)域內(nèi)所有障礙物的最低高度。適當?shù)腍可使無人機無需頻繁調(diào)整高度以保證飛行安全，同時也能保證無人機與用戶之間能以較低的傳輸功率通信。無人機的水平坐標為q=(xq,yq)。假設(shè)在無人機與用戶之間具備視距鏈路(根據(jù)文獻[14]中的實地測量，在服務(wù)區(qū)邊長小于等于100 m的空曠環(huán)境中，無人機與用戶之間具有視距鏈路的概率接近于1)。無人機與用戶k之間的信道功率增益[15]可表示為

(1)

其中，β0表示在參考距離為1 m時的信道增益。

1.2 計算和任務(wù)卸載模型

采用部分卸載模型[3]，即假設(shè)用戶的計算任務(wù)可以被分割為兩部分，一部分由用戶自身進行計算，另一部分通過無線鏈路卸載到無人機，由無人機上搭載的MEC服務(wù)器進行計算，計算完成后將計算結(jié)果返回用戶。假設(shè)用戶k的CPU時鐘頻率為fl,k，則用戶在本地計算的比特數(shù)可以表示為

(2)

無人機為用戶k提供服務(wù)是指無人機協(xié)助用戶k在期限內(nèi)完成其計算任務(wù)。令二元變量μk∈{0,1}表示無人機是否為用戶k提供服務(wù)，μk=1表示無人機為用戶k提供服務(wù)，否則μk=0。因此，無人機的覆蓋范圍可以由服務(wù)用戶的數(shù)量衡量。為了避免干擾，用戶與無人機之間采用頻分多址(Frequency Division Multiple Access，F(xiàn)DMA)進行通信。令αk∈[0,1]表示分配給用戶k的頻帶寬度占整個帶寬的比例，用戶k卸載到無人機上的任務(wù)比特數(shù)可以表示為

(3)

其中：B為總體可用帶寬；pk表示用戶k向無人機卸載任務(wù)數(shù)據(jù)時的傳輸功率。無人機接收到用戶卸載的任務(wù)后對任務(wù)數(shù)據(jù)進行計算處理得到輸出結(jié)果，將輸出結(jié)果回傳給相應(yīng)的用戶。考慮到計算結(jié)果所占比特數(shù)往往較小(如人臉識別，只需返回判斷結(jié)果是或者否)，因此，忽略計算結(jié)果回傳帶來的傳輸時延。

2 覆蓋范圍最大化資源分配方案

通過聯(lián)合優(yōu)化用戶CPU工作頻率與傳輸功率、用戶帶寬分配、用戶分組、無人機的CPU時鐘頻率及部署位置最大化MEC服務(wù)器覆蓋范圍。令α=[αk,k∈κ]，f=[fe,k,k∈κ]，p=[pk,k∈κ]和μ=[μk,k∈κ]分別表示用戶帶寬分配、無人機CPU時鐘頻率分配、傳輸功率及用戶分組向量。無人機覆蓋范圍最大化問題如下表示。

s.t.C1ll,k+lo,k≥μkIk

C4μk∈{0,1}

C60≤fu,k,fl,k≤fl,max,0≤pk≤pmax

其中，fl,max、pmax和fu,max分別表示用戶最大CPU時鐘頻率、用戶最大傳輸功率以及無人機搭載的MEC服務(wù)器的最大CPU時鐘頻率。約束條件C1保證所有用戶的計算任務(wù)都能在規(guī)定時間內(nèi)完成，C2保證用戶卸載到無人機的數(shù)據(jù)量能在規(guī)定時間T內(nèi)被無人機計算完畢，C3表示分配給每個用戶的頻譜資源之和不能超過該系統(tǒng)中可用的頻譜資源總量，C4表示無人機是否為用戶k提供服務(wù)，C5-C6約束了無人機的CPU計算頻率與用戶的傳輸功率與CPU時鐘頻率。

優(yōu)化問題P1中存在二元優(yōu)化變量所組成的向量μ，導致問題P1是一個難以求解的非凸混合整型優(yōu)化問題。為了能有效地改善這個問題，首先將二元整型變量μk松弛為一個連續(xù)優(yōu)化變量，且有0≤μk≤1。再對問題P1進行求解，最后恢復原始二元優(yōu)化變量。然而，約束條件中存在較多的變量耦合，即使將二元優(yōu)化變量松弛為一個連續(xù)優(yōu)化變量，上述問題仍為一個非凸問題。為了改善這個問題，提出了一個兩階段交替迭代優(yōu)化算法。具體而言，首先，固定無人機的部署坐標q，優(yōu)化用戶與無人機的CPU時鐘頻率向量f、用戶分組向量μ、用戶傳輸功率向量p以及系統(tǒng)帶寬分配向量α；其次，基于第一步優(yōu)化得到的優(yōu)化結(jié)果，對無人機位置進行優(yōu)化。

固定無人機的部署位置后，相應(yīng)的優(yōu)化問題表示為

(4)

s.t.C1—C3,C5—C6，0≤μk≤1

為了處理非凸約束條件C1和C2，首先引入輔助變量zk=αkpk,k∈κ，可得

(5)

需要注意的是，此時無人機的部署位置是固定的，因此根據(jù)式(1)可得，無人機與各用戶之間的信道功率增益也是一個確定的值，則是一個凹函數(shù)。等式右邊是左側(cè)的透視函數(shù)，為凹函數(shù)。故約束條件C1和C2不等號左邊均為凹函數(shù)，可以分別表示為

(6)

(7)

(8)

(9)

其中，αk[n]和zk[n]表示連續(xù)凸近似算法中第n次迭代時的任意可行點。通過將式(7)的凸近似式(8)代入問題P1.1可得

其中：z=[zk]；ε是一個很小的正的常數(shù)，其作用是為了防止在優(yōu)化過程中αk為0。ε很小，其對最優(yōu)解的影響可以忽略不計。P1.1.1是一個凸問題，可利用凸優(yōu)化工具箱對其求解。令Θ[n]=[αk[n],zk[n]]，表示帶寬分配與輔助變量所組成的向量，第n次迭代得到的解為(f*,μ*,Θ*(Θ[n]))。連續(xù)凸近似算法原理如算法1所示。

算法1連續(xù)凸近似算法

步驟1初始化。選擇原始問題的一個可行解，初始化步長因子r∈(0,1]，令k=0。

步驟4設(shè)置k+1→k，返回步驟2。

求解P1.1的具體步驟如算法2所示，步驟2的終止條件為(f*,μ*,Θ[n])收斂到問題P1.1的一個駐點。

算法2求解P1.1的連續(xù)凸近似算法

步驟1初始化。選擇合適步長r[n]∈(0,1]，輸入初始可行向量Θ[0]，令n=0。

步驟2若(f*,μ*,Θ[n])滿足終止條件，則停止，輸出最優(yōu)解(f*,μ*,Θ*)=(f*,μ*,Θ[n])，否則轉(zhuǎn)入下一步。

步驟3從P1.1.1中計算(f*,μ*,Θ*(Θ[n]))。

步驟4Θ[n+1]=Θ[n]+r[n][Θ*(Θ[n])-Θ[n]]。

步驟5令n+1→n，返回步驟2。

對于第二個子問題，需要基于第一步中得到的最優(yōu)解(f*,μ*,Θ*)實現(xiàn)對無人機部署位置的優(yōu)化，相應(yīng)的子優(yōu)化問題可以表示為

(10)

則P1.2第二個約束的一個凸近似可以表示為

(11)

等號右邊是關(guān)于q的凸函數(shù)，同理，其在任意可行點處的一階泰勒展開式均是其全局下界，可表示為

Ψ2,k[n]=2(q[n]-wk)T(q-q[n])+
‖q[n]-wk‖2

(12)

因此，基于式(10)和式(12)，得到了優(yōu)化問題P1.2的一個凸近似，可以表示為

問題P1.2.1是一個凸問題，可以利用凸優(yōu)化工具有效求解。步驟2中，求解子優(yōu)化問題P1.2的具體步驟如算法3所示，步驟2中的終止條件為q[n]收斂到問題P1.2的一個駐點。

算法3求解P1.2的連續(xù)凸近似算法

步驟1初始化。選擇合適步長r[n]∈(0,1]，輸入初始可行點q[0]，令n=0。

步驟2若q[n]滿足終止條件，則停止，輸出最優(yōu)解q*=q[n]，否則轉(zhuǎn)入下一步。

步驟3從P1.2.1中計算q*(q[n])。

步驟4更新可行點q[n+1]。

q[n+1]=q[n]+r[n][q*(q[n])-q[n]]。

步驟5令n+1→n，返回步驟2。

綜上，將原始非凸優(yōu)化問題P1分解為兩個子優(yōu)化問題P1.1和P1.2進行交替迭代求解，對于每一個子優(yōu)化問題，利用凸優(yōu)化方法獲得各自的最優(yōu)解，求解原始優(yōu)化問題P1的步驟總結(jié)在算法4中。

算法4求解P1的兩階段交替迭代優(yōu)化算法

步驟1初始化。給定q[0]。

步驟2若P1目標函數(shù)值收斂，則結(jié)束。

步驟3利用算法1求解子問題P1.1，獲得最優(yōu)解(f*,μ*,Θ*)，否則轉(zhuǎn)入步驟4。

步驟4基于步驟3中得到的最優(yōu)解(f*,μ*,Θ*)，利用算法2獲得問題P1.2最優(yōu)解q*，返回步驟2。

算法5恢復出二元優(yōu)化變量μ*的二分法

步驟3若P1有解且kup-klow≤1，則μ*[Idex(1:kmid)]=1，μ*[Idex(kmid+1:end)]=0，結(jié)束；否則進入步驟4。

步驟4令

步驟5基于步驟4中得到的μ,利用算法3求解P1，若P1有解，則klow=kmid；若P1無解，則kup=kmid。返回步驟3。

3 性能仿真及分析

針對提出的無人機輔助MEC覆蓋范圍最大化算法進行仿真和性能分析。詳細仿真參數(shù)如表1所示。

表1 仿真參數(shù)

圖2和圖3描述了無人機輔助的MEC網(wǎng)絡(luò)覆蓋性能與用戶輸入數(shù)據(jù)量Ik,k∈(1,2,…,K)的關(guān)系。所有的用戶均勻分布在一個半徑為r0=15 m,圓心為(0,0)的圓上。在假設(shè)條件下，無人機與用戶之間的信道功率增益與其之間的距離有關(guān)。從圖2和圖3中可以看出，在這種用戶分布的場景下，無人機的最優(yōu)部署位置為圓心(0,0)，符合預期設(shè)想。并且由圖3可以看出，隨著任務(wù)輸入數(shù)據(jù)量的增加，服務(wù)的用戶數(shù)降低(由9個降低到5個)，無人機機載邊緣服務(wù)器的計算資源有限，在任務(wù)數(shù)據(jù)量增大時，無法為原有的所有用戶設(shè)備提供服務(wù)，因此，只能降低服務(wù)用戶數(shù)以保證服務(wù)用戶的服務(wù)質(zhì)量。

圖2 Ik=2×104 bits情況下用戶均勻分布時的覆蓋性能

圖3 Ik=2×104 bits情況下用戶均勻分布時的覆蓋性能

比較圖4和圖5可以看出，首先，當用戶分為兩個數(shù)目相同用戶組，分布在兩個不同的地理位置時，無人機的最優(yōu)部署位置接近于兩個用戶組的中點。而當兩個分組用戶數(shù)目不同時，為了服務(wù)盡可能多的用戶，無人機的最優(yōu)部署位置將更靠近用戶數(shù)多的那一邊，并且隨著用戶分布的更密集，無人機服務(wù)的用戶數(shù)將增加。

圖4 用戶均勻分布時的覆蓋性能

圖5 用戶非均勻分布時的覆蓋性能

圖6對所提二分法恢復整型變量的正確性進行驗證，其中橫坐標表示用戶的任務(wù)數(shù)據(jù)量，縱坐標為提供服務(wù)的用戶數(shù)。由圖6可以看出，所提算法可正確恢復,整數(shù)變量，算法有效。同時也可看出隨著用戶待計算任務(wù)量的增加，無人機MEC覆蓋范圍越來越小。

圖6 用戶非均勻分布時的覆蓋性能

4 結(jié)語

針對目前無人機輔助邊緣計算研究較少的服務(wù)覆蓋范圍問題，提出一種無人機輔助的移動邊緣計算無人機部署位置與資源分配優(yōu)化算法。利用連續(xù)凸近似的二階段迭代算法與二分法優(yōu)化無人機部署位置、計算資源以及用戶發(fā)送與計算參數(shù)，無人機服務(wù)用戶數(shù)。仿真結(jié)果表明，當用戶分布均勻時，無人機的最優(yōu)部署位于幾何中心；當用戶分布不均勻時，無人機的最優(yōu)部署傾向于高密度區(qū)域。