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

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

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

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

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

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

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

1 系統模型

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

圖1 系統模型

1.1 坐標與信道模型

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

(1)

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

1.2 計算和任務卸載模型

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

(2)

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

(3)

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

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

通過聯合優化用戶CPU工作頻率與傳輸功率、用戶帶寬分配、用戶分組、無人機的CPU時鐘頻率及部署位置最大化MEC服務器覆蓋范圍。令α=[α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服務器的最大CPU時鐘頻率。約束條件C1保證所有用戶的計算任務都能在規定時間內完成，C2保證用戶卸載到無人機的數據量能在規定時間T內被無人機計算完畢，C3表示分配給每個用戶的頻譜資源之和不能超過該系統中可用的頻譜資源總量，C4表示無人機是否為用戶k提供服務，C5-C6約束了無人機的CPU計算頻率與用戶的傳輸功率與CPU時鐘頻率。

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

固定無人機的部署位置后，相應的優化問題表示為

(4)

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

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

(5)

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

(6)

(7)

(8)

(9)

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

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

算法1連續凸近似算法

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

步驟4設置k+1→k，返回步驟2。

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

算法2求解P1.1的連續凸近似算法

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

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

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

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

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

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

(10)

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

(11)

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

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

(12)

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

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

算法3求解P1.2的連續凸近似算法

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

步驟2若q[n]滿足終止條件，則停止，輸出最優解q*=q[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。

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

算法4求解P1的兩階段交替迭代優化算法

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

步驟2若P1目標函數值收斂，則結束。

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

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

算法5恢復出二元優化變量μ*的二分法

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

步驟4令

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

3 性能仿真及分析

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

表1 仿真參數

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

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

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

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

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

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

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

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

4 結語

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