加權(quán)能耗最小化的無人機(jī)輔助移動邊緣計算資源分配策略

李 安 戴龍斌 余禮蘇*② 王 振③

①(南昌大學(xué)信息工程學(xué)院 南昌 330031)

②(中國科學(xué)院計算技術(shù)研究所，計算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室 北京 100190)

③(北京郵電大學(xué)人工智能學(xué)院 北京 100876)

1 引言

隨著物聯(lián)網(wǎng)和5G技術(shù)的發(fā)展，各種新型應(yīng)用不斷涌現(xiàn)，比如目標(biāo)識別、自動駕駛、圖像處理和網(wǎng)絡(luò)游戲等。這些應(yīng)用往往會產(chǎn)生大量需要及時處理的實(shí)時數(shù)據(jù)，而通常大部分此類應(yīng)用的前端物聯(lián)網(wǎng)設(shè)備資源嚴(yán)重受限[1]，這對其計算能力和能耗提出了巨大的挑戰(zhàn)。解決這一挑戰(zhàn)的一種有效的方法是部署邊緣服務(wù)器，通過將計算任務(wù)卸載到移動邊緣計算(Mobile Edge Computing, MEC)服務(wù)器，使計算資源距離設(shè)備更近，并減少設(shè)備的能量消耗[2]。然而是否將計算任務(wù)卸載給邊緣服務(wù)器在很大程度上取決于終端設(shè)備與邊緣服務(wù)器之間的信道。對于基站基礎(chǔ)設(shè)施有限或沒有現(xiàn)有基站的場景(例如，某些偏遠(yuǎn)的山區(qū)或者沙漠地區(qū))使用無人機(jī)(Unmanned Aerial Vehicle, UAV)搭載邊緣服務(wù)器為物聯(lián)網(wǎng)設(shè)備提供數(shù)據(jù)卸載，以降低終端設(shè)備計算能耗是一種很有前景的方案，因?yàn)闊o人機(jī)可以利用其靈活的機(jī)動性獲得良好的空對地視距[3,4]。

現(xiàn)有研究在無人機(jī)作為空中移動基站為地面設(shè)備提供計算服務(wù)方面進(jìn)行了大量的研究[5,6]，以滿足不同的通信目的，比如通信延遲最小化[7]、比特數(shù)計算速率最大化[8]、通信能效最大化[9,10]及通信最小保密率最大化[11]等。然而這些研究并未考慮對系統(tǒng)能耗方面的優(yōu)化，在以最小化能耗為目的的研究中，大致可分為3類：第1類以最小化地面設(shè)備能耗為目的；第2類以最小化無人機(jī)能耗為目的；第3類以最小化無人機(jī)和地面設(shè)備的總能耗為目的。

在以最小化地面設(shè)備能耗為目的的研究中，文獻(xiàn)[12]通過對無人機(jī)軌跡、任務(wù)數(shù)據(jù)和計算資源的分配來最小化最大地面設(shè)備能耗。文獻(xiàn)[13]通過聯(lián)合優(yōu)化資源分配和卸載策略將數(shù)據(jù)卸載到無人機(jī)上以最大限度地減少地面設(shè)備的能耗。然而這些研究主要關(guān)注的是地面設(shè)備的能耗最小化問題，并未考慮無人機(jī)能耗的優(yōu)化。而無人機(jī)能耗直接關(guān)系到任務(wù)執(zhí)行時間的長短。在以最小化無人機(jī)能耗為目的的研究中，文獻(xiàn)[14]以計算卸載、資源分配和無人機(jī)軌跡作為聯(lián)合優(yōu)化設(shè)計方案，最小化無人機(jī)能耗和完成時間，同時還給出了無人機(jī)能耗和完成時間之間進(jìn)行權(quán)衡的帕累托最優(yōu)解。文獻(xiàn)[15]研究了具有無線充電技術(shù)的無人機(jī)輔助MEC系統(tǒng)，其中無人機(jī)上裝備了能量發(fā)射器，可以為地面設(shè)備提供能量補(bǔ)充。并通過聯(lián)合優(yōu)化MEC服務(wù)器的計算頻率資源、設(shè)備卸載數(shù)據(jù)量、無人機(jī)的發(fā)射功率及軌跡，使無人機(jī)整體能耗最小化。文獻(xiàn)[16]研究了固定翼和旋翼無人機(jī)向地面終端提供通信和服務(wù)的MEC系統(tǒng)，通過聯(lián)合優(yōu)化無人機(jī)的3維軌跡和任務(wù)緩存策略來最小化無人機(jī)整體能耗。然而這些研究主要關(guān)注無人機(jī)整體能量最小化問題，并沒有考慮終端設(shè)備的能耗優(yōu)化。在以最小化無人機(jī)和地面設(shè)備的總能耗為目的的研究中，文獻(xiàn)[17]研究了基于非正交多址接入(Non-Orthogonal Multiple Access,NOMA)的無人機(jī)輔助MEC系統(tǒng)，研究了最小化多無人機(jī)和地面設(shè)備的加權(quán)能耗。然而文獻(xiàn)[17]并未考慮卸載數(shù)據(jù)在無人機(jī)上的處理延時約束，而且其所采用的無人機(jī)推動力能耗模型缺乏通用性。文獻(xiàn)[18]在以無人機(jī)作為中繼的場景下，研究了無人機(jī)輔助地面設(shè)備將任務(wù)數(shù)據(jù)卸載到地面基站的MEC系統(tǒng)，通過優(yōu)化數(shù)據(jù)比特分配、時隙分配、功率分配及無人機(jī)軌跡規(guī)劃使無人機(jī)和通信的加權(quán)能耗最小化。雖然這些研究考慮了系統(tǒng)的加權(quán)能耗，但是其并沒研究權(quán)重因子會給無人機(jī)能耗和地面設(shè)備能耗帶來怎樣的影響，這些文獻(xiàn)主要關(guān)注如何去最小化加權(quán)能耗，而沒有關(guān)注權(quán)重因子對系統(tǒng)能耗的影響趨勢。

本文主要的研究貢獻(xiàn)如下：

(1)本文結(jié)合旋翼無人機(jī)飛行能耗模型，提出在給定的任務(wù)完成時間內(nèi)最小化無人機(jī)能耗和地面設(shè)備能耗的加權(quán)和問題。通過聯(lián)合優(yōu)化無人機(jī)軌跡、資源分配來最終解決本文所提出的問題，使系統(tǒng)的加權(quán)能耗最小化。此外，還對無人機(jī)能耗與地面設(shè)備能耗進(jìn)行折中考慮，通過改變權(quán)重因子的大小，給出了無人機(jī)能耗和設(shè)備能耗之間的Pareto最優(yōu)曲線。

(2)所提問題是非凸的，難以直接解決。針對該非凸問題，提出一個基于交替優(yōu)化算法的兩階段迭代算法來解決該非凸問題。第1階段在給定地面設(shè)備的卸載功率下，利用連續(xù)凸逼近方法將子非凸問題變?yōu)橥箚栴}，以求解無人機(jī)軌跡規(guī)劃、CPU頻率資源分配及卸載時間分配；第2階段求解地面設(shè)備的卸載功率分配。

2 系統(tǒng)模型

考慮如圖1所示的無線通信場景，搭載MEC計算服務(wù)器的UAV為地面的K個不同設(shè)備提供計算服務(wù)，其中k∈K,K={1,2,...,K},K表示地面設(shè)備集合，并假設(shè)K個設(shè)備的位置是固定已知的。不失一般性，考慮一個3維歐幾里得空間，并將任務(wù)完成時間T均勻離散化為N個時隙，第n個時隙的時間間隔可表示為τn=T/N， 其中n∈N,N={1,2,...,N}，且時隙τn足夠小以保證無人機(jī)的位置在每個時隙內(nèi)可以被認(rèn)為是固定不變的[13]。因此，無人機(jī)在第n個時隙內(nèi)的位置可以表示為qn=[xn,yn,H]，其中xn,yn表示無人機(jī)的水平位置，H表示無人機(jī)固定飛行高度。第k個地面設(shè)備的位置表示為uk=[xk,yk]。在每個時隙n內(nèi)，K地面設(shè)備采用時分多址接入(Time Division Multiple Access, TDMA)無人機(jī)，以避免不同地面設(shè)備之間的干擾[14]。且在每個時隙內(nèi)采用TDMA接入方式能給地面設(shè)備提供更多的卸載機(jī)會以減小設(shè)備間的接入競爭。考慮到實(shí)際應(yīng)用中無人機(jī)在完成任務(wù)后需要前往附近的基站進(jìn)行能量補(bǔ)充。可令無人機(jī)起始位置分別為qI和qF，并且無人機(jī)在飛行過程中的最大速度為Vmax。因此無人機(jī)移動性需要滿足的約束可表示為

圖1 系統(tǒng)模型

假設(shè)無人機(jī)與地面設(shè)備之間的通信信道為視距傳輸(Line Of Sight, LOS)鏈路[3]，而且由于無人機(jī)移動性而產(chǎn)生的多普勒效應(yīng)可以由接收機(jī)端完全補(bǔ)償。因此，對于每個時隙n，無人機(jī)和地面設(shè)備之間的信道功率增益可以表示為

其中，β0表示在基準(zhǔn)距離等于1 m情況下的信道功率增益。那么在第n個時隙內(nèi)第k個地面設(shè)備與無人機(jī)之間的信息速率表示為

其中，B表示信道帶寬(H z)，γkn=Pknβ0/σ2,Pkn表示第k地面設(shè)備第n時 隙的卸載功率，σ2表示無人機(jī)處的噪聲功率。本文主要參數(shù)及其含義如表1所示，在本文中| |·||表示歐氏范數(shù)，粗體小寫字母表示向量。

腦型脂肪栓塞綜合征可表現(xiàn)為頭痛、煩躁不安、失眠、易怒、譫妄甚至昏迷、復(fù)視、去大腦強(qiáng)直、偏癱，也可伴有嘔吐、尿失禁及自主神經(jīng)功能紊亂，常早期出現(xiàn)病理反射，腦脂肪栓塞呈彌漫性時較少出現(xiàn)定位體征［2,3,5］。累及中樞神經(jīng)系統(tǒng)的FES病例常伴有瘀點(diǎn)性皮疹、發(fā)熱、心動過速及低血壓，但肺動脈高壓的癥狀或體征反而較少。FES可能成為術(shù)后患者出現(xiàn)中樞神經(jīng)系統(tǒng)癥狀（如意識障礙等）的原因之一。

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

3 能耗模型

在整個任務(wù)的完成過程中，系統(tǒng)能耗由任務(wù)卸載能耗、任務(wù)執(zhí)行能耗和無人機(jī)飛行能耗組成。

假設(shè)第k個地面設(shè)備所需要處理的數(shù)據(jù)大小為Ik，而每個地面設(shè)備在給定的時間內(nèi)不能單獨(dú)完成任務(wù)，因?yàn)槊總€地面設(shè)備的計算能力和電池容量非常有限，所以地面設(shè)備不得不將部分?jǐn)?shù)據(jù)卸載到具有強(qiáng)大計算能力的MEC服務(wù)器上處理。并假設(shè)所有地面設(shè)備都采用部分卸載模式[15]，這意味著地面設(shè)備將會把數(shù)據(jù)分成兩部分，一部分在地面設(shè)備本地進(jìn)行計算，另一部分將會卸載到無人機(jī)MEC服務(wù)器上進(jìn)行計算。在每個時隙內(nèi)，本地設(shè)備CPU的計算頻率可能是不同的，并且假設(shè)地面設(shè)備都是單核的CPU，每個地面設(shè)備的CPU最大頻率均為fmax， 因此第n個時隙內(nèi)地面設(shè)備的CPU計算頻率應(yīng)滿足約束fkn ≤fmax,n ∈N,k ∈K。同時無人機(jī)上MEC服務(wù)器是也單核的CPU，其最大頻率為，那么在第n個時隙內(nèi)無人機(jī)分配給第k個地面設(shè)備的計算頻率為fu,kn，因此無人機(jī)上CPU頻率需要滿約束

(1) 任務(wù)卸載能耗：由于所有地面設(shè)備在每個時隙內(nèi)采用TDMA方式接入無人機(jī)，所以在每個時隙內(nèi)K個地面設(shè)備將依次接入無人機(jī)，其數(shù)據(jù)卸載過程如圖2所示，其中wkn表示第k個地面設(shè)備第n個時隙的卸載時間，所以第n個 時隙內(nèi)K個地面設(shè)備的卸載時間之和需要滿足的約束[14,17]為

圖2 數(shù)據(jù)比特卸載協(xié)議示例

所以在第n個時隙內(nèi)K個地面設(shè)備的卸載能耗之和可以表示為

注意，在任務(wù)的卸載過程中，考慮到地面設(shè)備數(shù)據(jù)的發(fā)送延時，第n個時隙卸載的數(shù)據(jù)將會在無人機(jī)上第n+1個時隙內(nèi)計算，所以，第1個時隙內(nèi)無人機(jī)不執(zhí)行數(shù)據(jù)的計算，而在最后第N個時隙內(nèi)，地面設(shè)備將會停止向無人機(jī)發(fā)送數(shù)據(jù)。

(2) 任務(wù)執(zhí)行的能量消耗：假設(shè)地面設(shè)備和無人機(jī)上MEC服務(wù)器的CPU都采用動態(tài)電壓和頻率縮放技術(shù)以自適應(yīng)地控制自身計算頻率[11]。那么所有地面設(shè)備在本地計算所消耗的能量和在無人機(jī)上計算消耗的能量[18]分別為

(3) 無人機(jī)飛行能耗：本文采用旋翼無人機(jī)搭載MEC服務(wù)器。通過將無人機(jī)飛行時間離散化，無人機(jī)推進(jìn)能耗模型[19]可表示為

本文的工作主要集中在無人機(jī)輔助MEC系統(tǒng)的加權(quán)能耗優(yōu)化。為此，忽略了數(shù)據(jù)從無人機(jī)邊緣服務(wù)器下傳的過程，因?yàn)樵跓o人機(jī)上處理后的數(shù)據(jù)大小與原始任務(wù)數(shù)據(jù)大小相比通常是可以忽略不計的[12–18]，而且忽略下載過程能夠簡化系統(tǒng)模型而不明顯影響系統(tǒng)的能耗。

4 優(yōu)化問題描述

無人機(jī)能耗和地面設(shè)備總能耗分別表示為

考慮到地面設(shè)備能耗相比于無人機(jī)能耗非常小，所以需要對地面設(shè)備能耗增加權(quán)重因子，以此來平衡無人機(jī)能耗和地面設(shè)備能耗之間的關(guān)系。而且無人機(jī)作為基礎(chǔ)設(shè)施的一部分，通常攜帶較大的電池，而且可以更頻繁地充電[17]。相比之下，地面設(shè)備的任務(wù)卸載和執(zhí)行耗費(fèi)了自身相當(dāng)多的電池能量。因此，在優(yōu)化過程中需要權(quán)重因子來調(diào)整不同部分的優(yōu)先級，以達(dá)到無人機(jī)能耗與地面設(shè)備能耗的折中考慮。所以總的優(yōu)化目標(biāo)可以表示為

其中，Etotal表示無人機(jī)能耗和地面設(shè)備能耗的加權(quán)和，ω表示權(quán)重因子，用來平衡無人機(jī)能耗與地面設(shè)備能耗。相應(yīng)的優(yōu)化問題建模為

其中，C1表示地面設(shè)備卸載時間約束，C2表示每個時隙內(nèi)在本地和無人機(jī)上計算處理的總數(shù)據(jù)量Dkn。約束C3表示要求第k個地面設(shè)備所有時隙計算處理的數(shù)據(jù)量之和要大于等于給定的任務(wù)數(shù)據(jù)，C4, C5是無人機(jī)和地面設(shè)備的CPU計算頻率資源約束，C6是因果約束，第n個時隙地面設(shè)備卸載到無人機(jī)上的數(shù)據(jù)大于等于第n+1個時隙無人機(jī)上處理的數(shù)據(jù)，這樣做的目是保證無人機(jī)上處理的數(shù)據(jù)大小不超過無人機(jī)接收的數(shù)據(jù)大小，同時可以讓無人機(jī)的處理延時在一個時隙以內(nèi)。相比文獻(xiàn)[14,17]在此約束上進(jìn)行了求和，這將導(dǎo)致不能保證延時在一個時隙以內(nèi)。C7～C9是無人機(jī)軌跡的約束，C10表示第1個時隙無人機(jī)上不執(zhí)行計算，C11表示地面設(shè)備最后一個時隙不進(jìn)行數(shù)據(jù)的卸載。C12, C13表示地面設(shè)備卸載功率約束，C14～C16為非負(fù)約束。

問題P1是非凸問題，現(xiàn)有的凸優(yōu)化技術(shù)無法對其直接求解。針對這一問題，本文先將其分解為兩個子問題，然后通過一個基于交替優(yōu)化的兩階段迭代算法來求解原問題的次優(yōu)解。第1階段，在給定地面設(shè)備的卸載功率下，求解無人機(jī)軌跡規(guī)劃、CPU頻率資源分配及卸載時間分配；第2階段，基于第1階段獲得的解求解地面設(shè)備卸載功率的分配。

5 優(yōu)化問題求解

第1階段，P1的子問題為CPU頻率資源分配、卸載時間分配和無人機(jī)軌跡優(yōu)化，其中卸載功率Pkn是固定的。第1階段子問題表述為

因此，無人機(jī)飛行能耗可重寫為

對式(17)利用泰勒展開，問題P2的約束C6可轉(zhuǎn)換為

引入松弛變量后，問題P2中約束C6轉(zhuǎn)化為式(18)，不難看出式(18)為凸約束。在固定Pkn下，非凸問題P2通過引入松弛變量un,ykn轉(zhuǎn)化的近似凸問題為

其中，約束C17, C18要求松弛變量非負(fù)。

因?yàn)镻3是一個凸優(yōu)化問題，所以可以利用MATLAB中的CVX工具箱來求解[17]。

第2階段求解卸載功率分配?；诘?階段子問題獲得的解，作為第2階段子問題的初值。第2階段優(yōu)化問題表述為

其中， C1′為因果約束，相對于原問題P1中的約束C6。

注意到問題P4的目標(biāo)函數(shù)和約束條件都是凸的，所以該問題可直接由CVX工具箱求解。當(dāng)?shù)?階段問題P4求解后，將得到的卸載功率作為給定值返回到問題P3，以求解第1階段問題。如此交替迭代優(yōu)化直到收斂到給定的精度。具體的兩階段資源分配策略如表2算法1所示。

表2 算法1：基于交替優(yōu)化算法的兩階段資源分配策略

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

本節(jié)給出仿真結(jié)果，以評估所提出算法的有效性?？紤]一個無人機(jī)輔助的MEC系統(tǒng)為隨機(jī)分布在一個矩形區(qū)域內(nèi)5個地面設(shè)備提供計算服務(wù)。具體參數(shù)設(shè)置如表3所示。

表3 仿真參數(shù)值

圖3表示不同權(quán)重因子下無人機(jī)的飛行軌跡，可以明顯看出權(quán)重因子對軌跡的影響。當(dāng)權(quán)重因子由小變大時無人機(jī)的軌跡將會逐漸靠近地面設(shè)備，這是因?yàn)楫?dāng)權(quán)重因子增大時，加權(quán)下的地面設(shè)備能耗在總的系統(tǒng)加權(quán)能耗中占比增大，所以無人機(jī)將會靠近地面設(shè)備，以減少地面設(shè)備的能量消耗。

圖3 不同權(quán)重因子下無人機(jī)的飛行軌跡

圖4比較了本文提出的基于交替優(yōu)化算法的兩階段資源分配策略與固定功率、固定軌跡、最小化無人機(jī)能耗3種基準(zhǔn)方案比較的Pareto最優(yōu)曲線。從圖4可以看出，與固定軌跡優(yōu)化相比，當(dāng)所消耗的無人機(jī)能量相同時，基于交替優(yōu)化算法的兩階段資源分配策略消耗的地面設(shè)備能量更少。同時與固定功率優(yōu)化和最小化無人機(jī)能耗方案[14]相比，當(dāng)無人機(jī)能耗小于4.1×104J時，兩階段資源分配策略和這兩種方案所消耗的地面設(shè)備能量相近，而當(dāng)無人機(jī)能耗大于4.1×104J時，兩階段資源分配策略所消耗的地面設(shè)備能量將大幅低于這兩種方案。綜上所述，在消耗相同的無人機(jī)能耗下，通過對地面設(shè)備和無人機(jī)能耗的加權(quán)優(yōu)化可以很大程度地降低地面設(shè)備的能耗。同時也可以看出在相同的地面設(shè)備能量需求下，本文提出的兩階段資源分配策略所消耗的無人機(jī)能量最低。

圖4 不同優(yōu)化方案下無人機(jī)能耗與地面設(shè)備能耗的關(guān)系

圖5比較了在權(quán)重因子相同時不同方案下地面設(shè)備能耗的大小關(guān)系，可以看出本文提出的兩階段資源分配策略在降低地面設(shè)備能耗方面要優(yōu)于其他方案。同時可以看出所提算法能夠較快地收斂。

圖5 在ω = 200時不同優(yōu)化方案下地面設(shè)備能耗的大小

圖6表示每個時隙不同地面設(shè)備的卸載時間分配，圖7表示每個時隙無人機(jī)分配給不同地面設(shè)備的計算頻率分配。結(jié)合圖6、圖7可以看出每個地面設(shè)備的卸載時間和其對應(yīng)在無人機(jī)上分配的計算頻率幾乎是同步的，這也驗(yàn)證了數(shù)據(jù)在無人機(jī)上的處理延時不超過一個時隙。而且從圖中可以看出每個地面設(shè)備只在無人機(jī)靠近的時候才增大自身的卸載時間，而當(dāng)無人機(jī)遠(yuǎn)離時，地面設(shè)備將會減少卸載時間。相應(yīng)的無人機(jī)將會在靠近地面設(shè)備時，因?yàn)槭盏降臄?shù)據(jù)量增加而提高無人機(jī)上分配給地面設(shè)備的計算頻率。

圖6 在ω = 200,T = 80 s時地面設(shè)備在不同時隙內(nèi)的卸載時間

圖7 在ω = 200,T = 80 s時無人機(jī)分配給地面設(shè)備的計算頻率

7 結(jié)束語

本文研究了基于加權(quán)能耗最小化的無人機(jī)輔助移動邊緣計算系統(tǒng)的最優(yōu)資源分配問題。通過聯(lián)合優(yōu)化無人機(jī)軌跡以及資源分配最小化無人機(jī)能耗和地面設(shè)備能耗的加權(quán)和。并通過改變權(quán)重因子來得到無人機(jī)能耗與地面設(shè)備能耗的Pareto最優(yōu)曲線。由于所求優(yōu)化問題是非凸的，難以求解，因此本文通過基于交替優(yōu)化的兩階段迭代算法來找到原問題的次優(yōu)解。仿真結(jié)果表明所提出的基于交替優(yōu)化的兩階段資源分配策略在降低系統(tǒng)能耗方面優(yōu)于固定功率、固定軌跡和最小化無人機(jī)能耗的基準(zhǔn)方案，而且可通過改變權(quán)重因子來極大地減少地面設(shè)備的能耗，這在一些地面設(shè)備能量不足的偏遠(yuǎn)地區(qū)對其地面設(shè)備能耗的節(jié)省是有意義的。下一步將在本文的基礎(chǔ)上考慮被服務(wù)的區(qū)域存在大量需要進(jìn)行數(shù)據(jù)卸載的物聯(lián)網(wǎng)設(shè)備，此時單個無人機(jī)由于有限的計算資源，同時又難以靠近區(qū)域內(nèi)的每個設(shè)備進(jìn)行協(xié)助計算而導(dǎo)致不能完成任務(wù)的情況下，考慮多無人機(jī)協(xié)助區(qū)域內(nèi)地面設(shè)備數(shù)據(jù)的計算。