多無(wú)人機(jī)輔助移動(dòng)邊緣計(jì)算中的軌跡優(yōu)化

江 雪,趙 亮

(1.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院,江蘇 南京 210003;2.杭州昊舜視訊科技有限公司,浙江 杭州 311100)

0 引 言

隨著信息相關(guān)技術(shù)的飛速發(fā)展,智能化的應(yīng)用越來(lái)越普及,大量密集的計(jì)算任務(wù)使得移動(dòng)終端的帶電量和計(jì)算能力都無(wú)法滿足人們?nèi)找嬖鲩L(zhǎng)的需求。移動(dòng)邊緣計(jì)算(mobile edge computing,MEC)[1-2]應(yīng)運(yùn)而生,它通過(guò)將計(jì)算任務(wù)卸載到邊緣服務(wù)器,可以有效地提高終端設(shè)備電池的使用壽命,降低整個(gè)網(wǎng)絡(luò)的時(shí)延。另外一方面,無(wú)人機(jī)[3](unmanned aerial vehicle,UAV)由于其靈活性高、機(jī)動(dòng)性強(qiáng)、成本低、可靠性高、操作簡(jiǎn)單等優(yōu)點(diǎn),被廣泛應(yīng)用于邊緣計(jì)算網(wǎng)絡(luò)中。即使是在地理位置復(fù)雜的區(qū)域,無(wú)人機(jī)也可以實(shí)現(xiàn)高效快速的部署,較好地解決應(yīng)急通信的需要。目前關(guān)于無(wú)人機(jī)應(yīng)用于移動(dòng)邊緣計(jì)算的研究主要集中在以下三個(gè)方面:一是無(wú)人機(jī)作為空中數(shù)據(jù)中繼[4-6],為遠(yuǎn)距離的用戶提供可靠的無(wú)線連接。二是無(wú)人機(jī)作為飛行的無(wú)線接入點(diǎn),用于物聯(lián)網(wǎng)中用戶設(shè)備的數(shù)據(jù)收集與分發(fā)[7]。三是無(wú)人機(jī)作為移動(dòng)基站通信[8],可以為蜂窩網(wǎng)絡(luò)提供有效補(bǔ)充。不論是無(wú)人機(jī)的哪種應(yīng)用,無(wú)人機(jī)的飛行軌跡都會(huì)直接影響邊緣計(jì)算網(wǎng)絡(luò)的能耗、時(shí)延和計(jì)算效率等關(guān)鍵性能,因此,無(wú)人機(jī)的軌跡問(wèn)題研究是近幾年學(xué)術(shù)界和工業(yè)界研究的熱點(diǎn)。

目前無(wú)人機(jī)輔助移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)中針對(duì)無(wú)人機(jī)飛行軌跡優(yōu)化算法的研究大部分都集中在以能耗最小化為目標(biāo)。文獻(xiàn)[9]在滿足用戶服務(wù)需求的限制條件下,聯(lián)合優(yōu)化用戶發(fā)送功率、計(jì)算卸載策略等設(shè)計(jì)基于能耗最小化的無(wú)人機(jī)軌跡優(yōu)化算法。文獻(xiàn)[10]在滿足無(wú)人機(jī)飛行速度的限制條件下,通過(guò)最大最小化地面設(shè)備可收集能量,設(shè)計(jì)無(wú)人機(jī)的最優(yōu)飛行軌跡。文獻(xiàn)[11]考慮用戶和無(wú)人機(jī)之間的上行和下行通信鏈路,在正交和非正交接入的兩種模式下,以加權(quán)最小化無(wú)人機(jī)和設(shè)備的能耗為目標(biāo),聯(lián)合設(shè)計(jì)計(jì)算資源分配策略和無(wú)人機(jī)最優(yōu)軌跡。文獻(xiàn)[12]通過(guò)強(qiáng)化學(xué)習(xí)和分簇的方法設(shè)計(jì)基于能耗最小化的無(wú)人機(jī)軌跡優(yōu)化算法。文獻(xiàn)[13]在滿足用戶服務(wù)需求的條件下,最大化能量效率,即最大化卸載總數(shù)據(jù)量比總能耗,聯(lián)合優(yōu)化無(wú)人機(jī)的飛行軌跡、用戶的發(fā)送功率和計(jì)算卸載策略。文獻(xiàn)[14]通過(guò)辛普森法和遺傳算法求解基于能耗最小化的無(wú)人機(jī)軌跡優(yōu)化算法。文獻(xiàn)[15]通過(guò)加權(quán)方式最小化無(wú)人機(jī)能耗和地面設(shè)備能耗,優(yōu)化資源分配策略和無(wú)人機(jī)飛行軌跡。文獻(xiàn)[16]在滿足設(shè)備服務(wù)質(zhì)量要求和可用計(jì)算資源的條件下,聯(lián)合優(yōu)化任務(wù)卸載策略、資源分配策略以及無(wú)人機(jī)的飛行時(shí)間,提出基于無(wú)人機(jī)飛行能耗和計(jì)算能耗最小化的軌跡優(yōu)化算法。上述大部分無(wú)人機(jī)輔助邊緣計(jì)算網(wǎng)絡(luò)的研究都是針對(duì)網(wǎng)絡(luò)中只有一架無(wú)人機(jī)優(yōu)化其軌跡路徑提高網(wǎng)絡(luò)整體性能,而實(shí)際的移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)中,情況復(fù)雜,許多情況下需要多架無(wú)人機(jī)協(xié)同[17-18]工作完成任務(wù),提高工作效率和優(yōu)化網(wǎng)絡(luò)整體性能?；诖?該文主要以能耗最小化為目標(biāo),在滿足無(wú)人機(jī)機(jī)械特性的條件下,同時(shí)考慮多架無(wú)人機(jī)之間需滿足防碰撞的約束條件,協(xié)同優(yōu)化多架無(wú)人機(jī)的飛行軌跡。

1 系統(tǒng)模型

考慮多架無(wú)人機(jī)輔助的移動(dòng)邊緣計(jì)算網(wǎng)絡(luò),網(wǎng)絡(luò)中有K(k=1,2,…,K)架無(wú)人機(jī)為U(u=1,2,…,U)個(gè)地面設(shè)備提供服務(wù),每個(gè)地面設(shè)備卸載部分任務(wù)給某架無(wú)人機(jī),本地執(zhí)行剩余任務(wù)。此外,每個(gè)地面設(shè)備只能卸載任務(wù)給某一架無(wú)人機(jī),每架無(wú)人機(jī)可以接收多個(gè)地面設(shè)備的卸載任務(wù),如圖1所示。

圖1 多無(wú)人機(jī)輔助移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)模型

每架無(wú)人機(jī)已知所有在水平地面設(shè)備的笛卡爾位置坐標(biāo)。其中,第u個(gè)設(shè)備的位置可以表示為:

Ou=[xu,yu]T,u=1,2,…,U

(1)

另外一方面,無(wú)人機(jī)在固定高度H的平面飛行,其飛行的時(shí)間周期為Tf秒,Tf秒被劃分為T個(gè)等長(zhǎng)時(shí)隙,其位置可以表示為:

ck(t)=[xk(t),yk(t),H]T,0≤t≤T

(2)

該文主要考慮視距(line of sight,LoS)信道和非視距(non-line-of-sight,NLoS)信道[17]。在時(shí)隙t,第k架UAV和第u個(gè)地面設(shè)備在LoS信道的連通概率可以表示為:

(3)

(4)

進(jìn)一步可得,在時(shí)隙t,第k架無(wú)人機(jī)與第u個(gè)地面設(shè)備之間的路徑損耗系數(shù)[17]為:

第k架無(wú)人機(jī)和第u個(gè)地面設(shè)備在時(shí)隙t的信道功率增益[17]可以表示為:

(6)

由于LoS鏈路的中斷概率比NLoS鏈路高很多,在時(shí)隙t,第u個(gè)地面設(shè)備向第k架無(wú)人機(jī)卸載任務(wù)時(shí)的數(shù)據(jù)率可以表示為:

(7)

1.1 通信模型

(8)

(9)

1.2 無(wú)人機(jī)模型

該文假設(shè)每架無(wú)人機(jī)在每個(gè)時(shí)隙的速度為恒定值vk(t),無(wú)人機(jī)的速度受到最大速度Vmax的約束,需滿足如下約束條件:

(10)

其中,δ=Tf/T表示每個(gè)時(shí)隙的長(zhǎng)度。

為了確保所有無(wú)人機(jī)可以為地面設(shè)備提供穩(wěn)定可靠的服務(wù),假設(shè)每架無(wú)人機(jī)飛行一個(gè)時(shí)間周期Tf后都需要回到最初的位置充電,即需要滿足:

ck(1)=ck(T)

(11)

另外一方面,多架無(wú)人機(jī)在同一水平面飛行執(zhí)行任務(wù),每架無(wú)人機(jī)之間還需要保持一個(gè)最小安全飛行距離dmin以避免發(fā)生碰撞,因此需滿足:

‖ci(t)-cj(t)‖≥dmin,?i,j=1,2,…,K;i≠j

(12)

無(wú)人機(jī)飛行需要消耗的能量主要與其重量和飛行距離有關(guān)。因此在每個(gè)時(shí)隙,無(wú)人機(jī)的飛行能耗[9]可以表示為:

(13)

其中,Υ表示無(wú)人機(jī)的有效載荷。

2 優(yōu)化問(wèn)題建模

無(wú)人機(jī)輔助邊緣計(jì)算網(wǎng)絡(luò)中,無(wú)人機(jī)的能耗遠(yuǎn)大于地面設(shè)備的能耗,無(wú)人機(jī)的能耗[15]主要由以下幾個(gè)部分組成:與地面設(shè)備之間通信的能耗、接收地面設(shè)備卸載任務(wù)的能耗、執(zhí)行接收卸載任務(wù)的計(jì)算能耗和飛行能耗。其中,接收地面設(shè)備卸載任務(wù)的能耗和飛行能耗受到無(wú)人機(jī)飛行軌跡的影響最大,因此主要考慮接收卸載計(jì)算任務(wù)的能耗和飛行能耗。根據(jù)上述分析,可以建立如下優(yōu)化問(wèn)題:

(14)

(a)

(b)

ck(1)=ck(T)

(c)

(d)

‖ci(t)-cj(t)‖≥dmin,?i≠j

(e)

優(yōu)化問(wèn)題(14)中的式(a)和(b)對(duì)應(yīng)地面設(shè)備和無(wú)人機(jī)之間的卸載決策參數(shù)值的約束條件。(c)、(d)和(e)對(duì)應(yīng)無(wú)人機(jī)飛行軌跡的約束條件。

3 優(yōu)化問(wèn)題求解

可以看出,由于優(yōu)化問(wèn)題(14)為非線性的優(yōu)化問(wèn)題,同時(shí)其對(duì)應(yīng)的約束條件非凸,所以該優(yōu)化問(wèn)題很難求解?；谖墨I(xiàn)[9]中的交替最小化算法,將優(yōu)化問(wèn)題(14)拆分為2個(gè)子優(yōu)化問(wèn)題:(1)給定k架無(wú)人機(jī)飛行軌跡的條件下求解卸載決策參數(shù)的問(wèn)題;(2)給定卸載決策參數(shù)的條件下求解多無(wú)人機(jī)的最優(yōu)飛行軌跡的問(wèn)題。

3.1 卸載決策參數(shù)求解

(15)

(16)

優(yōu)化問(wèn)題(14)可以轉(zhuǎn)化為如下等價(jià)形式:

(17)

另外一方面,約束條件(a)和(b)可以轉(zhuǎn)化為:

(18)

(19)

3.2 多無(wú)人機(jī)飛行軌跡求解

(20)

求解K架無(wú)人機(jī)的最優(yōu)飛行軌跡,對(duì)應(yīng)的約束條件為(c)、(d)和(e)。其中,約束條件(e)非凸,導(dǎo)致優(yōu)化問(wèn)題(20)無(wú)法求解,基于文獻(xiàn)[20],采用連續(xù)凸優(yōu)化 (successive convex optimization, SCA)的方法轉(zhuǎn)化約束條件(e),因此對(duì)于任意給定的(ci(t))n和(cj(t))n的一階泰勒展開(kāi)式[20],有如下不等式成立:

‖ci(t)-cj(t)‖2≥-‖(ci(t))n-(cj(t))n‖2+

2((ci(t))n-(cj(t))n)T((ci(t))-(cj(t)))

(21)

其中,n為迭代步數(shù)。

根據(jù)上述分析,約束條件(e)可以轉(zhuǎn)化為:

(dmin)2≤-‖(ci(t))n-(cj(t))n‖2+

2((ci(t))n-(cj(t))n)T((ci(t))-

(cj(t)))

(22)

即:

((ci(t))n-(cj(t))n)T((ci(t))-(cj(t)))≥

(dmin)2+‖(ci(t))n-(cj(t))n‖2

(23)

另外一方面,為了簡(jiǎn)化求解過(guò)程,由優(yōu)化問(wèn)題(20)可以看,第k架無(wú)人機(jī)在時(shí)隙t的坐標(biāo)位置只與它前一個(gè)時(shí)隙t-1的位置有關(guān),可以將優(yōu)化問(wèn)題(20)分解為T-1個(gè)子優(yōu)化問(wèn)題求解,逐步求解{c1(1)…ck(1)},{c1(2)…ck(2)},…,{c1(T-1)…ck(T-1)},對(duì)應(yīng)需求解的子優(yōu)化問(wèn)題如下:

(24)

其中,t=1,2,…,T-1。

4 仿真結(jié)果及分析

在本節(jié),通過(guò)MATLAB中的CVX來(lái)驗(yàn)算所提無(wú)人機(jī)軌跡優(yōu)化算法的性能?？紤]D×D的平面區(qū)域,K架無(wú)人機(jī)飛行在恒定的高度H=10 m,其中U個(gè)地面設(shè)備隨機(jī)分布在區(qū)域內(nèi),并且所有無(wú)人機(jī)都已知所有地面設(shè)備的位置。實(shí)驗(yàn)中系統(tǒng)參數(shù)設(shè)置如表1所示。

表1 系統(tǒng)參數(shù)設(shè)置

續(xù)表1

實(shí)驗(yàn)主要考慮K=2和K=4兩種情況分析UAV的飛行軌跡。當(dāng)K=2時(shí),2架UAV的起始位置分別為:(0,0)、(D,D)。當(dāng)K=4時(shí),4架UAV的起始位置分別為:(0,0)、(0,D)、(D,D)、(D,0)。

圖2和圖3分別展示了在網(wǎng)絡(luò)中分別有2架和4架無(wú)人機(jī)時(shí),不同數(shù)量地面設(shè)備條件下的無(wú)人機(jī)的飛行軌跡。由圖可以看出,隨著地面設(shè)備數(shù)量的增大,分布在區(qū)域中的范圍變廣,無(wú)人機(jī)的飛行距離也會(huì)相應(yīng)變遠(yuǎn),盡量地靠近設(shè)備,接收并完成卸載的任務(wù)。

圖2 K=2時(shí),不同數(shù)量地面設(shè)備U={8,10,16} 對(duì)應(yīng)的飛行軌跡

圖3 K=4時(shí),不同數(shù)量地面設(shè)備U={8,12,20} 對(duì)應(yīng)的飛行軌跡

圖4和圖5分別展示了在網(wǎng)絡(luò)中有2架和4架無(wú)人機(jī)時(shí),不同無(wú)人機(jī)最大飛行速度約束下的無(wú)人機(jī)的飛行軌跡。由圖可以看出,隨著無(wú)人機(jī)最大飛行速度的上限值越來(lái)越大,無(wú)人機(jī)單步的可飛行距離越遠(yuǎn),以便可以覆蓋更廣闊的區(qū)域。

圖4 K=2時(shí),不同無(wú)人機(jī)最大飛行速度V= {6,8,10}對(duì)應(yīng)的飛行軌跡

圖5 K=4時(shí),不同無(wú)人機(jī)最大飛行速度V= {4,6,8}對(duì)應(yīng)的飛行軌跡

圖6和圖7分別展示了在網(wǎng)絡(luò)中有2架和4架無(wú)人機(jī)時(shí),無(wú)人機(jī)在不同飛行時(shí)隙下的飛行軌跡。由圖可以看出,隨著無(wú)人機(jī)飛行時(shí)隙的增大,在總飛行周期時(shí)間固定的情況下,無(wú)人機(jī)的單步飛行距離在變短。

圖6 K=2時(shí),不同無(wú)人機(jī)飛行時(shí)隙T={5,8} 對(duì)應(yīng)的飛行軌跡

圖7 K=4時(shí),不同無(wú)人機(jī)飛行時(shí)隙T={5,8} 對(duì)應(yīng)的飛行軌跡

圖8和圖9分別展示了在網(wǎng)絡(luò)中有2架和4架無(wú)人機(jī)時(shí),不同能耗權(quán)重因子條件下無(wú)人機(jī)的飛行軌跡。由圖可以看出,卸載能耗的加權(quán)因子越大,無(wú)人機(jī)越接近地面設(shè)備的位置。飛行能耗的權(quán)重因子越大,無(wú)人機(jī)的單步步長(zhǎng)越小,這是由于UAV的飛行能耗主要和無(wú)人機(jī)飛行距離有關(guān),而UAV的卸載能耗主要和無(wú)人機(jī)與設(shè)備之間的距離有關(guān)。

圖8 K=2時(shí),不同能耗權(quán)重因子對(duì)應(yīng)的飛行軌跡

圖9 K=4時(shí),不同能耗權(quán)重因子對(duì)應(yīng)的飛行軌跡

圖10分別展示了在網(wǎng)絡(luò)中有2架和4架無(wú)人機(jī)時(shí),在不同能量權(quán)重因子的條件下無(wú)人機(jī)的飛行能耗和卸載能耗的關(guān)系。由圖可以看出,隨著無(wú)人機(jī)飛行能耗權(quán)重增加,無(wú)人機(jī)對(duì)應(yīng)的飛行能耗有所增加。隨著無(wú)人機(jī)卸載能耗的權(quán)重因子增加,無(wú)人機(jī)對(duì)應(yīng)的卸載能耗有所增加。

圖10 不同權(quán)重因子對(duì)應(yīng)的能耗關(guān)系

5 結(jié)束語(yǔ)

研究了多無(wú)人機(jī)輔助移動(dòng)邊緣計(jì)算系統(tǒng),在滿足無(wú)人機(jī)機(jī)械特性和多架無(wú)人機(jī)碰撞避免的條件下,以能耗最小化為目標(biāo),優(yōu)化多無(wú)人機(jī)的飛行軌跡。為了解決非線性的優(yōu)化問(wèn)題和非凸的約束條件,引入輔助變量及轉(zhuǎn)換優(yōu)化問(wèn)題為多個(gè)子優(yōu)化問(wèn)題求解。仿真結(jié)果驗(yàn)證了所提算法在得到多架無(wú)人機(jī)較優(yōu)的飛行軌跡的同時(shí),還明顯改善了能耗。