無人機輔助邊緣計算的能量效率最大化算法設計

吳啟暉，吳偉,2

（1.南京航空航天大學電磁頻譜空間認知動態(tài)系統(tǒng)工信部重點實驗室，江蘇 南京 211106；2.南京郵電大學通信與信息工程學院，江蘇 南京 210003）

1 引言

隨著信息通信技術的高速發(fā)展，人類社會開始進入萬物互聯(lián)的信息時代。智能移動設備的空前普及為許多新型智能應用提供了強大的平臺，與此同時也帶來了諸多新的挑戰(zhàn)。智能化的應用（如人臉識別、交互游戲、自動駕駛等）往往計算任務密集且對時延敏感[1-2]，然而，大多數(shù)移動終端計算能力和電能儲備有限，無法獨立勝任當下需求。移動邊緣計算（MEC,mobile edge computing）通過將云計算[3]和信息技術服務部署到網(wǎng)絡邊緣，提供輔助計算，可有效降低任務處理時延、避免網(wǎng)絡擁塞、提高終端設備電池使用壽命[4]。

近年來，移動邊緣計算被廣泛研究用于提升蜂窩網(wǎng)絡的能量效率、減少時延或最大化網(wǎng)絡運營的系統(tǒng)效用[5]。文獻[2]研究了非線性無線供能的MEC網(wǎng)絡中計算能效最大化問題，在時延受限的情況下，分別對時分多址接入（TDMA,time division multiple access）和非正交多址接入（NOMA,nonorthogonal multiple access）方式下的部分卸載與二元卸載進行了分析比較。針對部署緩存的NOMA異構網(wǎng)絡下的基站用戶匹配及功率分配問題，以最大化緩存收益為目標，對功率資源和用戶調(diào)度進行了合理設計，顯著提升了系統(tǒng)吞吐量和時延等性能。在安全通信方面，針對有惡意竊聽者的情況，文獻[6]引入安全中斷概率度量NOMA MEC 系統(tǒng)的安全性能，以最小化加權和能耗為優(yōu)化準則，設計了最佳的資源分配方法。在此基礎上，文獻[7]進一步探究了在用戶設備能量受限的情況下安全中斷概率最小化問題，并給出了相應的最優(yōu)安全卸載速率和功率分配方案。針對中繼輔助的跨蜂窩移動邊緣計算網(wǎng)絡，文獻[8]提出了一種混合中繼轉發(fā)協(xié)議以實現(xiàn)兩終端設備之間的單向計算結果共享，利用非嚴格塊坐標下降法有效地實現(xiàn)了執(zhí)行時延與網(wǎng)絡能耗之間的均衡。對原始數(shù)據(jù)壓縮后再進行傳輸可有效提升網(wǎng)絡吞吐量，基于此，文獻[9]提出了一種MEC 輔助的計算與中繼方案，以增強點對點通信系統(tǒng)吞吐量，通過對動態(tài)壓縮率和發(fā)送功率進行聯(lián)合優(yōu)化設計，實現(xiàn)了能耗和時延的有效均衡，突破了傳統(tǒng)點對點通信系統(tǒng)的性能瓶頸。

無人機（UAV,unmanned aerial vehicle）輔助的邊緣計算與通信具備可靈活部署、機動性強、視距通信等諸多天然優(yōu)勢。利用無人機的靈活移動特性并給其配備具有一定運算處理能力的計算服務器，可實現(xiàn)對終端設備計算任務的高能效、低時延輔助處理[9-13]。與此同時，無人機輔助的邊緣計算系統(tǒng)也面臨著諸多現(xiàn)實挑戰(zhàn)。無人機能量有限，如何高效地利用有限的通信和計算資源，設計最佳的飛行軌跡，最終以一種高能效的方式快速完成任務的輔助計算和共享，是研究者普遍關注的問題。此外，無人機飛行抖動及方向變化帶來的信號波束實時動態(tài)調(diào)整、多無人機輔助時的無人機與地面用戶動態(tài)關聯(lián)等現(xiàn)實問題都給無人機輔助的邊緣計算帶來不少的挑戰(zhàn)。文獻[9]給無人機配備處理服務器以幫助多個用戶終端設備計算卸載的任務，通過對無人機的飛行軌跡和任務卸載比特劃分進行聯(lián)合優(yōu)化，實現(xiàn)了總的移動計算能耗最小化。進一步地，考慮到終端設備自身儲能的局限性，文獻[10]將無線供能模塊引入無人機設備，在輔助地面終端任務計算的同時利用視距信道對其進行無線供能，相較于傳統(tǒng)的地面基站無線供能更加高效靈活。通過利用交替優(yōu)化算法，在部分卸載和二元卸載這2 種模式下最大化系統(tǒng)的計算速率。在無人機和可利用地面基站同時存在的情況下[12]，無人機在充當移動邊緣計算輔助器的同時可作為空中中繼，將部分計算任務二次卸載到地面基站，以減輕無人機的計算負擔。為實現(xiàn)較高的系統(tǒng)能效，復雜的計算資源調(diào)度、帶寬分配和無人機軌跡優(yōu)化問題必須得到解決。文獻[13]針對部分卸載模式下的多無人輔助邊緣計算，綜合考慮了用戶關聯(lián)、計算頻率、信息傳輸功率、頻譜資源塊、多無人機軌跡等多因素的聯(lián)合設計，以獲得最佳的計算能效。

以上無人機輔助的邊緣計算研究工作都關注于無人機協(xié)助地面終端計算并將結果反饋回地面終端的應用場景。不同于現(xiàn)有的研究工作以及文獻[8]提出的依賴地面固定基站的邊緣計算與結果共享系統(tǒng)，本文考慮了一種如圖1 所示的無人機輔助邊緣計算與結果共享系統(tǒng)，提出了一種兩階段交替優(yōu)化算法以最大化系統(tǒng)能量效率。首先，利用Dinkelbach方法將建模的非線性分式規(guī)劃問題轉換為一類等價的參數(shù)問題。其次，通過對子問題的分析，給出了中央處理單元頻率和數(shù)據(jù)比特量的閉式解。最后，所獲得的解揭示了源節(jié)點選擇卸載與共享自身數(shù)據(jù)和中繼選擇轉發(fā)計算結果的必要條件，以及實現(xiàn)更高能量效率的方法。仿真結果表明，與傳統(tǒng)算法相比，本文所提算法在能量效率方面可獲得高達20 倍的性能提升。

2 系統(tǒng)模型及問題描述

如圖1 所示，考慮一種無人機輔助的邊緣計算與結果共享系統(tǒng)，該系統(tǒng)包含一個源節(jié)點S（位于地面）、一個目的節(jié)點D（位于地面）和一個無人機（位于空中），且均假設它們?yōu)閱翁炀€設備。假設S 和無人機都內(nèi)置有獨立的通信模塊和計算處理單元。部署在室外環(huán)境下的S 捕獲到圖像、自然語言等信號數(shù)據(jù)并將該數(shù)據(jù)的處理結果共享給D。假設S 和D 的位置都是固定的，且因障礙物遮擋的原因，二者之間的直達無線鏈路無法進行有效的信息傳輸[14-15]。另外，小型化低功率的S 在功率和計算能力方面也十分有限。因此，部署空中無人機以輔助S 到D 之間的信息傳輸以及對S 所捕獲數(shù)據(jù)的處理。進一步地，假設采用部分卸載的邊緣計算模式且S 可同時進行數(shù)據(jù)的傳輸和本地計算。與此同時，假設無人機中繼內(nèi)配置一定大小的緩存來存儲等待計算的卸載任務。因信息收發(fā)和任務計算分別在不同功能單元進行，故可同步進行[12]。

圖1 無人機輔助的邊緣計算與結果共享系統(tǒng)

采用三維笛卡爾坐標系，其中S 和D 的三維坐標分別為(0,0,0)和(xd，0，0)，且在有限時長T內(nèi)，無人機的飛行高度固定為H。為便于探究，將有限時長T劃分成N個等長的時隙，則每個時隙的時長，其中τ的值足夠小以至于無人機在每個時隙內(nèi)的坐標保持不變。因此，無人機在時長T內(nèi)的飛行軌跡可表示為三維空間中N個離散坐標點的形式(x[n],y[n],H)，其中n∈Ν,Ν={1,…,N}。進一步地，假設無人機的起始和最終方位可被預先設定，將其分別表示為(x0,y0,H)和(xF,yF,H)。

為簡便起見，假設無人機采用頻分雙工通信模式且各頻段帶寬相等，無人機與地面通信節(jié)點（S和D）之間的無線信道主要為視距信道。因此，在第n個時隙，S 和無人機以及無人機和D 之間的信道增益可分別表示為

其中，β0表示在基準距離d0=1情況下的信道功率增益，dsr和drd分別表示S 與無人機和無人機與D之間的距離。在快衰落信道模型下，系統(tǒng)涉及的無線信道在時長T內(nèi)保持穩(wěn)定狀態(tài)。

假設S 所獲取的原始數(shù)據(jù)逐位獨立且可按任意比例進行拆分以便并行處理。據(jù)此，S 可采用如下2 種方法協(xié)作的方式完成數(shù)據(jù)處理結果的共享：1)S在本地完成部分原始數(shù)據(jù)的計算處理，然后在無人機中繼的輔助下將計算結果發(fā)送給D；2)S 將余下的原始數(shù)據(jù)卸載到無人機，無人機進行輔助計算處理并將結果發(fā)送給D。進一步地，假設方法1)中S的計算時延和無人機的譯碼時延分別為一個時隙，方法2)中無人機的計算準備時延和計算處理時延也分別為一個時隙。

2.1 本地計算與結果共享

1) S 本地計算

捕獲到原始數(shù)據(jù)之后，S 同步執(zhí)行任務的本地計算和卸載。針對本地計算，令C表示執(zhí)行單位比特計算任務所需的CPU 循環(huán)次數(shù)，ρ∈(0,1)表示數(shù)據(jù)壓縮率。為高效利用有限的能量資源，S 采用動態(tài)電壓和頻率縮放技術以自適應地控制計算能量消耗。將S在第n時刻的CPU頻率表示為fs[n]循環(huán)每秒。因此，在第n時刻S 計算的任務比特量和相應的能耗[6]分別為

其中，γs表示S 依賴于芯片結構的有效電容系數(shù)。

2) 無人機中繼輔助S 到D 的計算結果共享

隨著本地計算的進行，S 在無人機中繼的輔助下將計算結果共享給D。令[n]表示第n時刻S發(fā)送出去的數(shù)據(jù)比特數(shù)，于是可以得到第n時刻S相應的信息傳輸能耗[16]為

通過分析易知，在第n時刻，S 只能發(fā)送或共享那些已被本地計算處理的數(shù)據(jù)，因此，有信息因果性約束為

2.2 任務卸載與結果共享

1) S 將計算任務卸載到無人機

2) 無人機輔助計算并將處理結果發(fā)送給D

接收到S 發(fā)來的任務數(shù)據(jù)，無人機首先對其進行計算處理，然后再將計算結果轉發(fā)給D。假設無人機也采用動態(tài)電壓和頻率縮放技術以自適應地控制自身計算頻率，且令fr[n]表示第n時刻的CPU頻率。于是，第n時刻無人機計算的任務數(shù)據(jù)比特量和相應的能耗可分別表示為

其中，γr表示無人機依賴于芯片結構的有效電容系數(shù)。令表示第n時刻無人機轉發(fā)到D 的數(shù)據(jù)比特量，則相應的傳輸能耗為

由分析可知，在每個時隙，無人機只能計算已接收到的來自S 的任務數(shù)據(jù)，且轉發(fā)出去的數(shù)據(jù)量不得多于無人機經(jīng)自身計算處理產(chǎn)生的數(shù)據(jù)量。因此，有信息因果性約束為

其中，式(16)右邊的項為無人機在n? 2個時隙內(nèi)計算出的數(shù)據(jù)結果比特量。顯然，考慮到處理時延的存在，S 在最后2 個時隙不應該卸載任務給無人機，無人機在第一個和最后一個時隙不執(zhí)行任務計算，且無人機在最開始的2 個時隙無計算結果轉發(fā)到D。因此，有和。

類似地，基于以上分析，可將該方法下S 成功分享的數(shù)據(jù)比特量和相應的能量消耗分別表示為

此外，無人機的飛行能耗較大且會受其自身飛行軌跡的影響。為簡便起見，可將無人機飛行能耗建模為關于飛行速度的二次函數(shù)，表示為

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

考慮到源節(jié)點S 和無人機通常是功率受限的，如何提高它們的工作能效一直備受關注。因此，本文從整個系統(tǒng)的角度出發(fā)，通過對計算資源、通信資源和無人機軌跡進行聯(lián)合優(yōu)化，以實現(xiàn)系統(tǒng)能量效率最大化。本文的系統(tǒng)能效定義為總分享數(shù)據(jù)比特與系統(tǒng)總能耗的比值，即其中，式(22)表示在有限時長T內(nèi)，S 分享的數(shù)據(jù)比特量不少于最低閾值Imin；式(23)～式(26)為2.1 節(jié)和2.2 節(jié)中給出的信息因果性約束；式(27)～式(32)保證了優(yōu)化變量的非負性；式(33)～式(35)為無人機的移動性約束，包含無人機的初始和最終方位以及飛行速度，Vmax代表無人機的最大飛行速度。

問題P1 是一個復雜的非凸優(yōu)化問題，現(xiàn)有的凸優(yōu)化技術無法直接對其進行求解?；诖耍疚氖紫瓤紤]對問題P1 進行變換處理；然后，將其拆解為2 個子問題分別優(yōu)化，即給定無人機軌跡下的計算資源和通信資源優(yōu)化和給定計算資源和通信資源下的無人機軌跡優(yōu)化；最后，基于各自獲得的解，結合兩階段迭代算法對計算資源、通信資源和無人機軌跡進行交替優(yōu)化。

3 能效最大化迭代算法

注意到優(yōu)化問題P1 中的約束項關于各組優(yōu)化變量是可分離的，并且數(shù)據(jù)比特量（包含、）與無人機軌跡這兩組變量之間存在非線性耦合關系。因此，本文將優(yōu)化變量分成兩塊，即(Ψ[n],Φ[n])和(u[n])，然后利用塊坐標下降法來對兩塊變量分別進行優(yōu)化。

在使用塊坐標下降法之前，本文首先采用Dinkelbach[2]方法對式(21)中非凸的分式結構目標函數(shù)進行處理，以獲得一種等價變換形式，使問題P1 更易于求解。具體如引理1 所示。

引理1根據(jù)Dinkelbach 方法，當且僅當式(36)成立時，可獲得問題P1 的最優(yōu)解。

其中，η*表示η的最大值。

證明證明過程請見文獻[17]。

根據(jù)引理1，問題P1 可被等價轉換為如式(37)所示的參數(shù)優(yōu)化問題，表示為問題P2。

其中，η為一非負參數(shù)。為求解問題P2，首先需在給定η值的情況下求解問題P2，然后利用獲得的ηCSE值對η進行更新，重復上述2 個步驟，直到式(36)滿足等號條件。相應的算法細節(jié)將在3.2 節(jié)中提及。

3.1 通信與計算資源分配

將問題P1 改寫成P2 之后，可采用塊坐標下降法對其進行求解?；谧兞糠謮K優(yōu)化的思想，可將問題P2 拆分成2 個獨立的子問題。首先考慮第一個子問題：給定無人機軌跡下的計算與通信資源優(yōu)化。該問題形式為

其中，f1(η)=I(1)+I(2)?η(E(1)+E(2))，源節(jié)點S的計算頻率fs[n]和無人機中繼的計算頻率fr[n]為待優(yōu)化的計算資源，源節(jié)點S 的卸載數(shù)據(jù)比特量和傳輸數(shù)據(jù)比特量以及無人機中繼的轉發(fā)數(shù)據(jù)比特量為待優(yōu)化的通信資源。易知，問題P2.1 為標準的凸優(yōu)化問題。然而，為洞悉最優(yōu)解的數(shù)學結構，以給出更加直觀的方案設計指導，本文考慮引入拉格朗日對偶法求解問題P2.1。令λ≥ 0表示與約束式(22)相應的對偶變量，問題P2.1 的部分拉格朗日表達式可寫為

關于式(41)中的最優(yōu)解，有如下結果。

定理1給定對偶變量取值的情況下，利用標準的拉格朗日方法和KKT（Karush-Kuhn-Tucker）條件，可獲得式(41)中優(yōu)化變量的最優(yōu)閉式解析式為

3.2 無人機軌跡優(yōu)化

已知通信與計算資源分配，無人機軌跡優(yōu)化問題可表示為

最后，可將通信資源、計算資源和無人機軌跡聯(lián)合優(yōu)化的能效最大化兩階段交替優(yōu)化方法歸納如下。1) 確定（給定）參數(shù)η的取值；2) 利用定理1 和定理2，計算給定無人機軌跡下的通信與計算資源分配；3) 基于問題P2.2 獲得給定通信與計算資源分配下的無人機軌跡優(yōu)化；4) 交替循環(huán)執(zhí)行步驟 2)與步驟 3)直至迭代終止；5) 利用更新η的值，并返回步驟1)重新執(zhí)行全部步驟，直至滿足終止條件；6) 輸出最優(yōu)的優(yōu)化變量值和相應的能量效率值ηCSE=η*。

4 仿真與分析

本節(jié)使用MATLAB 工具對所提算法進行仿真，并采用與現(xiàn)有方案對比的方式評價本文所提算法的性能。表1 給出了實驗仿真中使用到的一些基本參數(shù)。

表1 實驗仿真參數(shù)

圖2 給出了不同分享數(shù)據(jù)比特閾值Imin下的無人機飛行軌跡，分別為Imin=0.5 ×104Mbit、Imin=1.0 ×104Mbit、Imin=1.5 ×104Mbit 和Imin=2.0×1 04Mbit這4 種不同的情況。由仿真結果可以發(fā)現(xiàn)，無人機傾向于靠近并在余下的時間里低速徘徊于源節(jié)點S和目的節(jié)點D 之間的中間點位置。這表明，無人機在源節(jié)點S和目的節(jié)點D的中間位置區(qū)間飛行可保證在完成協(xié)助計算和數(shù)據(jù)轉發(fā)任務的同時盡可能地減少系統(tǒng)的總能耗，進而獲得相對更高的能量效率。對比4 種不同情況的飛行軌跡可以進一步發(fā)現(xiàn)，隨著所需分享數(shù)據(jù)比特數(shù)的增加，無人機越發(fā)傾向于徘徊在源節(jié)點S 和目的節(jié)點D 的中間更小位置區(qū)域，以盡可能地降低自身飛行能耗，將更多的能量用于輔助計算和數(shù)據(jù)轉發(fā)。在相同基準信道功率增益β0的情況下，中間點位置可保證信道hsr[n]與信道hrd[n]之間的差異最小。無人機傾向于在源節(jié)點S 和目的節(jié)點D 的中間點位置徘徊，這一現(xiàn)象表明，兩個信道之間的差異越小，越有利于數(shù)據(jù)的快速轉發(fā)，待分享和處理的數(shù)據(jù)量越大，對二者信道之間的差異要求則越嚴格。

圖2 不同分享數(shù)據(jù)比特閾值下的無人機飛行軌跡

圖3 給出了3 種不同方案下系統(tǒng)能量效率隨分享數(shù)據(jù)比特閾值變化的曲線。隨著Imin的增加，系統(tǒng)能量效率呈遞減趨勢。由式(5)、式(7)和式(14)可知，數(shù)據(jù)的傳輸（轉發(fā)）能耗與數(shù)據(jù)量呈指數(shù)關系，分享數(shù)據(jù)量的線性增長將導致傳輸（轉發(fā)）能耗的指數(shù)級增長。因此能量效率隨著Imin的增加而顯著下降。在地面基站方案[8]中，本文將基站位置設定在（1 000,0,0）的方位。全卸載方案[11]指的是源節(jié)點S 對原始數(shù)據(jù)不做任何的計算處理，直接將數(shù)據(jù)全部卸載到無人機，無人機進行輔助計算并將結果轉發(fā)給目的節(jié)點D。3 種方案對比顯示，本文所提無人機輔助的部分卸載方案具有更好的能量效率性能，這凸顯了無人機作為空中移動中繼以及部分卸載方式的靈活性帶來的好處。

圖3 不同方案下系統(tǒng)能量效率隨閾值 Imin的變化曲線

圖4 給出了Imin=1.0 ×104Mbit 時本文所提算法的收斂情況。仿真圖反映的是能量效率η的取值更新過程。任意選取3 種不同的初始化參數(shù)η0，本文所提算法均可在有限的迭代次數(shù)內(nèi)實現(xiàn)快速收斂，具有較好的收斂性。

圖4 本文所提算法收斂變化曲線

5 結束語

本文考慮了一種無人機輔助的邊緣計算與結果共享系統(tǒng)，利用Dinkelbach 方法和兩階段交替優(yōu)化，獲得了系統(tǒng)能量效率最大化的最優(yōu)無人機軌跡設計以及通信和計算資源分配。仿真結果顯示了所提算法比現(xiàn)有方案具有更佳的能量效率性能和收斂性能。值得注意的是，本文所提優(yōu)化框架和分析方法可適用于處理無線通信信號處理領域中出現(xiàn)的一類變量耦合分式規(guī)劃相關問題。后續(xù)的研究中，可進一步考慮多個目的接收端的應用場景，同時引入非正交多址接入以提高資源利用效率，還可以考慮引入多個無人機進行輔助，以提供更高質量的通信與計算服務。此外，移動邊緣計算場景下的任務數(shù)據(jù)卸載安全性也是非常值得關注的問題。