劉伯陽(yáng)，楊寧樂(lè)，馬 杰,萬(wàn)奕堯，周繼軍

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

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

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

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

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

1 系統(tǒng)模型

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

圖1 系統(tǒng)模型

1.1 坐標(biāo)與信道模型

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

(1)

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

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

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

(2)

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

(3)

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

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

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

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

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

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

(4)

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

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

(5)

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

(6)

(7)

(8)

(9)

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

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

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

步驟1初始化。選擇原始問(wèn)題的一個(gè)可行解，初始化步長(zhǎng)因子r∈(0,1]，令k=0。

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

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

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

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

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

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

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

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

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

(10)

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

(11)

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

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

(12)

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

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

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

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

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

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

步驟4更新可行點(diǎn)q[n+1]。

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

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

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

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

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

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

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

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

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

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

步驟4令

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

3 性能仿真及分析

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

表1 仿真參數(shù)

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

圖2 Ik=2×104 bits情況下用戶(hù)均勻分布時(shí)的覆蓋性能

圖3 Ik=2×104 bits情況下用戶(hù)均勻分布時(shí)的覆蓋性能

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

圖4 用戶(hù)均勻分布時(shí)的覆蓋性能

圖5 用戶(hù)非均勻分布時(shí)的覆蓋性能

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

圖6 用戶(hù)非均勻分布時(shí)的覆蓋性能

4 結(jié)語(yǔ)

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