余雪勇, 朱 燁, 邱禮翔, 朱洪波

(1. 南京郵電大學江蘇省無線通信重點實驗室, 江蘇 南京 210003;2. 南京郵電大學教育部泛在網(wǎng)絡健康服務系統(tǒng)工程研究中心, 江蘇 南京 210003)

0 引 言

隨著物聯(lián)網(wǎng)(internet of things, IoT)技術的發(fā)展,萌生了許多移動端的應用服務,例如增強現(xiàn)實(augmented reality, AR)、音視頻業(yè)務、人臉識別、輕量級的深度學習應用等。這些應用服務往往時延敏感且需要用戶終端具備較強的計算能力。而對于移動用戶的終端設備,其有限的能量和計算能力無法很好的滿足用戶的應用需求。

移動邊緣計算(mobile edge computing, MEC)通過將服務器部署在靠近用戶的邊緣側(cè),使資源受限的用戶終端可以將計算密集型任務卸載到邊緣服務器去執(zhí)行,大大減緩用戶終端的計算壓力。但是,復雜的環(huán)境會帶來高昂的基礎設施部署成本,尤其對于偏遠地區(qū)以及搶險救災類的環(huán)境。

近來,無人機以其在移動性和成本上的優(yōu)勢被應用到無線通信網(wǎng)絡中。但是續(xù)航受限的無人機上執(zhí)行計算密集型任務可能會導致響應時間變慢和大量的能耗,并且還可能對電池壽命造成損害,最終可能影響任務的成功,特別是對于一些實時應用的任務,如森林火災探測或探索無人區(qū)任務。此外,地面用戶與無人機之間的信道條件會直接影響用戶終端與無人機的通信能耗,這就需要根據(jù)用戶終端的位置合理規(guī)劃無人機的飛行軌跡。

基于此,近年來許多學者對無人機輔助邊緣計算問題進行了研究。文獻[9]提出了無人機作為移動cloudlet輔助地面終端執(zhí)行計算密集型任務,通過聯(lián)合優(yōu)化比特分配方案和無人機飛行軌跡,研究了不同的接入條件下終端能耗最小化問題。文獻[10]通過引入二進制變量以確定用戶是否進行卸載(本地計算或卸載計算),充分考慮了服務質(zhì)量(quality of service, QoS),差異化了不同用戶的任務復雜度,以QoS指標和無人機續(xù)航為約束,最大化用戶終端計算卸載的數(shù)據(jù)量。文獻[11]研究了一種具有異構(gòu)云下多用戶MEC系統(tǒng)中的任務卸載。用戶的任務通過無線信道卸載到邊緣云后,可以通過因特網(wǎng)進一步轉(zhuǎn)發(fā)到遠程云?；趧討B(tài)編程提出了一種聯(lián)合優(yōu)化用戶的帶寬資源和計算資源分配的節(jié)能算法,在滿足不同任務的延時標準下最小化用戶設備的總能耗。文獻[12]劃分了無人機通信和計算任務的運動狀態(tài),通信時沿軌跡飛行而計算任務時保持懸停。以時延、無人機能耗以及用戶終端的任務數(shù)據(jù)量為約束,聯(lián)合優(yōu)化比特分配方案和無人機軌跡,最小化用戶終端的能耗。

在上述研究中,存在以下幾點問題。

(1) 無論是全卸載策略,還是二進制卸載策略,用戶終端的任務在同一時刻只能在本地或邊緣側(cè)執(zhí)行,由于終端用戶的本地計算資源不足,任務只在本地進行計算并不合理。同時由于完全卸載產(chǎn)生的延遲問題、帶寬浪費問題以及無人機自身電力有限,數(shù)據(jù)只在無人機邊緣側(cè)進行處理存在較大局限。

(2) 忽略了任務過程中用戶終端本地計算的時延。這可能會導致用戶計算卸載和本地計算不同步完成的后果。

(3) 缺乏對用戶終端與無人機之間信道條件優(yōu)劣的討論。在信道信噪比較差的情況下,不能保證提出的模型與方案仍具備有效性和可靠性。

為了解決上述問題,本文研究了一種以最小化用戶終端計算和卸載能耗為目標無人機輔助的邊緣計算系統(tǒng),對地面終端計算資源進行合理分配,從而實現(xiàn)終端能耗的最小化,對用戶持續(xù)在線有著一定的意義。因此本文為了實現(xiàn)這一優(yōu)化策略,主要作出的貢獻如下。

(1) 在MEC系統(tǒng)中建立了無人機的軌跡設計和終端用戶任務卸載策略模型。為了解決完全本地計算或全卸載的弊端,對于用戶終端任務可分割的場景,針對計算卸載策略,本文采用部分卸載策略,即用戶終端在計算卸載的同時,保留一部分任務在本地進行計算。同時考慮了系統(tǒng)中的時延需求,解決了用戶計算卸載和本地計算不同步問題。

(2) 將逐次凸優(yōu)化技術和塊坐標下降算法進行結(jié)合,提出了一種基于塊坐標下降的兩步迭代算法。同時對算法的復雜度進行分析,并通過仿真結(jié)果進一步進行驗證。

(3) 對不同的信道條件下的用戶終端能耗進行討論。分析了不同的信道條件下本文的所提出的卸載策略對終端用戶能耗的優(yōu)化效果。

1 系統(tǒng)模型

無人機輔助多用戶邊緣計算系統(tǒng)如圖1所示,由安裝MEC服務器的無人機和地面(=1,2,…,)個用戶終端組成。其中,每個用戶終端都具備一定的計算能力,滿足本地執(zhí)行簡單任務的需求。相對地,無人機搭載服務器具備更強的計算能力,能夠快速完成計算密集型任務,為用戶終端提供邊緣計算服務。在飛行過程中同步執(zhí)行卸載任務。

圖1 無人機輔助多用戶邊緣計算系統(tǒng)Fig.1 Unmanned aerial vehicle aided with multi-user edge computing system

假設所有用戶終端的任務均在時長內(nèi)完成。利用三維歐幾里德坐標表示的方法,可以分別表示出用戶終端和無人機的具體位置。用戶終端分布在平面上,第個用戶終端的位置可表示為如下形式:

=(,,0),∈{1,2,…,}

(1)

式中:和分別表示第個用戶終端在平面上的橫坐標和縱坐標。

假設無人機中存儲了所有用戶終端的位置信息,并以固定高度在空中飛行,其瞬時位置可以表示為如下形式:

()=((),(),),0≤≤

(2)

無人機從起點出發(fā)沿飛行軌跡向終點飛去,為沿途的用戶終端提供邊緣計算服務,由此無人機起始和結(jié)束的位置需要滿足如下約束:

(3)

將時長等分為個時長為的時間幀:

(4)

由于每幀的時長都足夠小,每一幀中無人機的位置可以近似看作不變。藉此,連續(xù)的無人機軌跡可以離散為幀的無人機位置的集合。于是,式(2)和式(3)可以進一步表示為如下形式:

[]=([],[],),∈{1,2,…,}

(5)

(6)

已知第幀的無人機位置,可以表示出第幀無人機的速度[],并規(guī)定飛行速度的上限值:

(7)

假設通信中多普勒頻移可以被接收端補償,信道質(zhì)量取決于無人機和用戶的之間的鏈路,由于無人機鏈路都為視距鏈路,即信道增益服從自由空間損耗模型。則在第幀的用戶終端與無人機之間的平均信道增益[]可以表示為如下形式:

(8)

式中:[]指第幀的用戶終端與無人機之間的歐氏距離;指在參考距離為1 m時,傳輸功率為1 W時的接收功率。

1.1 計算卸載模型

為了避免用戶終端在卸載過程中相互干擾,采用時分多址(time division multiple access, TDMA)協(xié)議,將每幀的時長Δ等分成份,并預分配給各個用戶終端進行上行的計算卸載和下行的下載計算結(jié)果,以保證各用戶的卸載時隙獨立。由于MEC服務器計算得到的結(jié)果數(shù)據(jù)量很小,一般可以忽略用戶終端下載結(jié)果所花費的通信時延,用Δ表示第幀用戶終端計算卸載的時長。

(9)

式中:是具有零均值的加性高斯白噪聲的功率譜密度,單位為dBm/Hz。

1.2 本地計算模型

(10)

式中:指的是任務每比特數(shù)據(jù)需要CPU運行的周期頻率數(shù),用于表示用戶終端任務的復雜度;表示用戶終端本地處理器的有效開關電容;表示用戶終端本地CPU的主頻(即CPU的時鐘頻率),用于描述本地計算能力。

由上述條件,可以表示出在TDMA方式下用戶終端在個時隙內(nèi)完成本地計算所需要的時間。由于所有任務必須在時長內(nèi)完成,用戶終端本地計算也需要在時長內(nèi)結(jié)束,應滿足如下約束:

(11)

1.3 無人機能耗模型

(12)

無人機在邊緣計算的同時保持飛行狀態(tài),考慮文獻[12]中的飛行能耗模型,假設無人機每一幀的飛行能量僅依賴于速度,故在第幀飛行產(chǎn)生的推進能耗[]為

(13)

式中:=05Δ,表示無人機的質(zhì)量(包括其載重)。

1.4 目標問題

假設用戶終端的任務可以被分割,計算任務可以分配到用戶本地和無人機MEC服務器上執(zhí)行。本文采用部分卸載策略,聯(lián)合優(yōu)化用戶終端本地計算的任務量、計算卸載的任務量以及無人機的軌跡以最小化用戶終端的能耗。

基于上述的模型,用戶終端的能耗問題可以描述為問題P1:

s.t.

(14)

在問題P1中,C1規(guī)定了無人機的能量上限,表示無人機的總能量;C2保證了所有用戶終端的任務都能在時長內(nèi)被完成,表示各個用戶終端的任務數(shù)據(jù)量;C3保證了用戶終端本地計算能夠在時長內(nèi)結(jié)束;C4保證了在任意一幀內(nèi)用戶終端的任務量都是非負的;C5規(guī)定了無人機飛行軌跡的起點和終點;C6限制了無人機飛行的速度。

2 優(yōu)化過程

由于問題P1的目標函數(shù)存在兩個優(yōu)化變量的耦合且約束條件C1非凸,問題P1具有非凸性。對于非凸問題,因為其復雜程度過高,往往難以利用傳統(tǒng)凸優(yōu)化技術直接求解。文獻[15]提出了一種塊坐標下降法。其在解決優(yōu)化問題時,一次只更新一個或幾個變量塊,相對于一次更新所有的變量塊的復雜度要低的多?；谶@種思想,本文采用了一種基于塊坐標下降的兩步迭代優(yōu)化算法對問題P1進行求解。

首先,需要將目標問題P1分解成兩個凸的子問題。其次,依次通過凸優(yōu)化算法對子問題進行求解。最后,基于塊坐標下降法進行全局優(yōu)化,求解用戶終端能耗的最小值。

(15)

式中：

(16)

依此,問題P1與如下形式等價:

s.t.C1,C2,C3,C4,C5,C6

(17)

問題P1實質(zhì)上由兩個子問題組成,分別是用戶終端任務量的分配問題和無人機的軌跡優(yōu)化問題。

2.1 用戶終端任務量的分配問題

固定無人機的初始軌跡[],則問題P1轉(zhuǎn)變成一個以用戶終端本地計算的任務量和計算卸載的任務量為優(yōu)化變量,最小化用戶終端能耗的問題。由于目標函數(shù)中初始軌跡[]在該子問題中為一常數(shù),可以將問題P1最小值問題等價改寫成求解如下的問題:

s.t.C1,C2,C3,C4

(18)

2.2 無人機的軌跡優(yōu)化問題

(19)

問題P1.2的目標函數(shù)是關于[]的凸函數(shù),且限制條件也是凸的,因此問題P1.2是一個凸問題。對于問題P1.2,同樣可以利用CVX工具,通過標準凸優(yōu)化算法進行求解,得到第幀無人機最優(yōu)的位置[]。

2.3 全局優(yōu)化和復雜度分析

基于子問題P1.1和P1.2得到的最優(yōu)解,利用塊坐標下降法進行全局優(yōu)化。具體過程如算法1所示。

算法 1 基于塊坐標下降的兩步迭代優(yōu)化算法輸入:初始賦值,定義精度閾值ε輸出:目標問題的次優(yōu)解步驟 1 初始化無人機的軌跡qn[0],初始迭代變?yōu)閕=0;步驟 2 開始循環(huán)迭代;步驟 3 固定qn[i],求解問題P1.1,得到llock,n[i+1]和lulk,n[i+1];步驟 4 固定llock,n[i+1]和lulk,n[i+1],求解問題P1.2,得到qn[i+1];步驟 5 將llock,n[i+1]、lulk,n[i+1]和qn[i+1]代入目標函數(shù),得到F[i+1];步驟 6 更新i=i+1,返回步驟2;步驟 7 直至用戶終端能耗值F[i]收斂,收斂條件F[i]-F[i-1]<ε。

3 性能分析

在這一部分中,通過大量的數(shù)值實驗驗證了本文所采用的基于兩步迭代的塊坐標下降法的有效性。利用Matlab R2019a進行仿真實驗,實驗設備為Dell OptiPlex 7070 MFF,CPU為Intel Core i5-9500T,內(nèi)存為16.0 GB。所采用的算法收斂閾值設置為10。

3.1 環(huán)境設置

除了上述預設參數(shù)外,其他的相關參數(shù)如表1所示。

表1 仿真參數(shù)

本文參考文獻[9,21-22]中的仿真場景,將所提的節(jié)能卸載策略與其他基準方案進行了性能比較?；鶞史桨钢饕ㄒ韵?種。

(1) 不進行優(yōu)化。由于在時長T內(nèi)用戶終端只靠本地計算完成不了任務,此方案中用戶終端默認采用全卸載的策略,且在每個時間幀內(nèi),用戶終端計算卸載的任務數(shù)據(jù)量都相同。另外,無人機的初始軌跡為起點到終點的一條直線,保持勻速飛行。

(2) 只對任務量的分配進行優(yōu)化。保持無人機的勻速飛行的軌跡不變,優(yōu)化每個時隙用戶終端本地計算的任務量和計算卸載的任務量。

(3) 只對無人機的軌跡優(yōu)化。保持計算卸載任務量的分配方案不變,優(yōu)化無人機的飛行軌跡。

3.2 結(jié)果分析

3.2.1 算法的迭代分析

圖2為=0.5 s時,用戶終端能耗的優(yōu)化過程,動態(tài)的展示了迭代優(yōu)化過程中用戶終端能耗的變化情況。由算法1可知,基于塊坐標下降的兩步迭代優(yōu)化算法的終止條件為前后兩次迭代的用戶終端能耗差值小于閾值。如圖2所示,橫坐標表示迭代次數(shù),縱坐標表示用戶終端的能耗?？梢园l(fā)現(xiàn),在第1次迭代的過程中,用戶終端能耗急劇降低。在第2～4次迭代的過程中,用戶終端能耗緩慢下降,并趨于平穩(wěn)。在第4次迭代之后,用戶終端能耗的數(shù)值不再發(fā)生改變,進入收斂狀態(tài)。從整個收斂過程中可以發(fā)現(xiàn),基于塊坐標下降的兩步迭代優(yōu)化算法特點在于能夠?qū)崿F(xiàn)用戶終端能耗的快速下降,并在幾次迭代內(nèi)就達到數(shù)值收斂,證明所提算法的收斂速度極快,具備實用意義。

圖2 用戶終端能耗的優(yōu)化過程Fig.2 Optimization process for energy consumption of user terminal

3.2.2 無人機的軌跡分析

圖3為無人機的飛行軌跡圖。無人機的初始軌跡為一條起點到終點間隔均勻的直線,對應了初始設定中無人機以勻速沿直線飛行。

圖3 無人機的飛行軌跡Fig.3 Trajectory of unmanned aerial vehicle

而優(yōu)化后的飛行軌跡則是一條向用戶終端2傾斜的外凸曲線,表明進行優(yōu)化后無人機傾向于靠近用戶終端2,提供計算卸載服務。從各用戶終端計算任務的初始設定不難發(fā)現(xiàn),任務量>>,復雜度>>,用戶終端2的任務相較其他兩者難度處理更大,卸載需求更明顯,因此無人機傾向于在若干個時隙內(nèi)靠近用戶終端2,進行小范圍的盤旋飛行。

323 用戶終端的計算卸載分析

圖4為=0.5 s時,優(yōu)化后用戶終端在不同時隙計算卸載數(shù)據(jù)量和本地計算數(shù)據(jù)量的變化曲線。由于在本實驗中,用戶終端設置的特點為低功耗和性能受限,因此本地計算的能耗開銷很低。如圖4(a)所示,用戶終端傾向于利用本地算力,以較低的計算能耗處理一部分計算任務,因此,用戶終端本地計算的數(shù)據(jù)量是一條直線,在每個時隙都根據(jù)自身性能處理盡可能多的本地處理任務。

圖4 用戶終端的計算卸載過程Fig.4 Calculation uninstall process of user terminal

圖4(b)展示了用戶終端如何分配剩余的任務數(shù)據(jù)量進行計算卸載。結(jié)合圖3可以發(fā)現(xiàn),在無人機靠近某個用戶終端時,其計算卸載的數(shù)據(jù)量會處于一個高點。特別的,用戶終端2在第33個時隙到第40個時隙之間持續(xù)以較大的數(shù)據(jù)量進行計算卸載,這正好對應了圖3中無人機的優(yōu)化軌跡靠近用戶終端2,且在其附近懸停了這段時間。

3.2.4 用戶終端的能耗分析

圖5給出了信噪比SNR=-5 dB的信道條件較差環(huán)境下,用戶終端在不同優(yōu)化方案下的整體能耗表現(xiàn)。如圖5所示,隨著任務時間的增加,用戶終端的能耗呈下降的趨勢。這是因為在TDMA的方案下,越大,用戶終端上行的卸載時隙的時長就越長,相鄰時隙間無人機的位置變化就越小,這意味著通信距離的改變也就越小,這節(jié)省了用戶終端計算卸載的通信能耗。

圖5 用戶終端的能耗(SNR=-5 dB)Fig.5 Energy consumption of user terminal (SNR=-5 dB)

其次,可以發(fā)現(xiàn)用戶終端的能耗下降的速度逐漸變緩,近乎收斂于某一個值。這是因為當任務時間足夠長的情況下,本地和無人機的處理器有足夠的時間進行性能的釋放。而在信道惡劣的環(huán)境中,通信的能耗開銷高于本地計算的能耗開銷,這使得用戶終端會任務時間內(nèi)優(yōu)先選擇本地計算,對于在時長內(nèi)完成不了的任務,再選擇計算卸載。因此用戶終端的能耗會隨著時長的增大逐漸收斂至統(tǒng)一。

此外,對比各方案的優(yōu)化效果可以發(fā)現(xiàn),優(yōu)化任務量的分配對用戶終端的能耗有顯著的節(jié)能效果,且隨著時長的增大,優(yōu)化效果進一步提升。特別的,當=5 s時,優(yōu)化任務量分配(73.16 J)的方案相較于不優(yōu)化(184.09 J)的方案,能耗降低了60.26%。原因與用戶終端的能耗下降速度變緩相似。受到信道條件的影響,計算卸載帶來的通信能耗劇增,超過了本地計算的能耗開銷,任務量的分配在此時的作用尤為明顯。隨著時長的增加,會進一步將任務量分配到本地,以節(jié)省能源。

而信道條件較好的情況下,如圖6所示,在信噪比SNR=20 dB時,優(yōu)化無人機的飛行軌跡則會有顯著的效果。特別的,當=5 s時,優(yōu)化無人機飛行軌跡的方案實現(xiàn)了能耗降低53.21%。這是因為無人機與用戶終端之間的距離會直接影響到用戶終端計算卸載的通信能耗。而信道條件良好的情況下,計算卸載的通信能耗得到了極大的改善,此時保證距離合適的視距信道就顯得格外重要。

圖6 用戶終端的能耗(SNR=20 dB)Fig.6 Energy consumption of user terminal (SNR=20 dB)

最后,無論信道條件的優(yōu)劣,本文提出的基于聯(lián)合優(yōu)化的節(jié)能卸載策略都取得了良好的性能表現(xiàn)。相較于其他3種基準方案,進一步降低了用戶終端的能耗,且隨著時長的增大,優(yōu)化效果越發(fā)明顯。

如圖5所示,在信噪比SNR=-5 dB,=5 s時,聯(lián)合優(yōu)化(21.80 J)較不優(yōu)化(184.09 J)、優(yōu)化任務量分配(73.16 J)和優(yōu)化無人機軌跡(86.14 J)這3種基準方案,用戶終端的能耗分別降低了88.16%、70.20%和74.69%,相較于文獻[9]中同場景下優(yōu)化方案移動終端總能耗降低了20.1%。

如圖6所示,在信噪比SNR=20 dB,=5 s時,聯(lián)合優(yōu)化(0.1330 J)較不優(yōu)化(0.5822 J)、優(yōu)化任務量分配(0.4394 J)和優(yōu)化無人機軌跡(0.2724 J)這3種基準方案,用戶終端的能耗分別降低了77.16%、69.73%和51.17%,相較于文獻[9]中同場景下優(yōu)化方案移動終端能耗降低了10.3%。

3.2.5 任務執(zhí)行過程的分析

圖7為聯(lián)合優(yōu)化方案下用戶終端在不同時隙累計執(zhí)行的任務數(shù)據(jù)量示意圖,展示了用戶終端在不同時隙累計執(zhí)行的任務數(shù)據(jù)量。3個用戶終端的任務數(shù)據(jù)量分別為8 Mbits,12 Mbits,4 Mbits。從圖中可以明顯看出,在時隙=20時,用戶累計執(zhí)行的任務數(shù)據(jù)量變化率明顯變快,這是由于隨著優(yōu)化算法的迭代,逐漸趨于收斂,這時無人機會更快的更新位置實現(xiàn)用戶數(shù)據(jù)的高效卸載。

圖7 用戶終端累計執(zhí)行的任務數(shù)據(jù)量Fig.7 Cumulative amount of task data performed by user terminal

在當時隙=50時,所有用戶終端均完成了所有計算任務。因此,聯(lián)合優(yōu)化的方案不會對用戶終端在時長內(nèi)完成任務產(chǎn)生影響,同時也可證明所采用的算法具有較快的收斂性。

綜上,聯(lián)合優(yōu)化用戶終端本地計算的任務量、計算卸載的任務量以及無人機的軌跡的節(jié)能卸載策略能夠有效的、可靠的降低用戶終端的能耗。

4 結(jié)束語

本文構(gòu)建了一種無人機輔助邊緣計算系統(tǒng),利用無人機搭載邊緣服務器以增強地面移動用戶終端設備的計算能力。針對用戶終端能耗受限的問題,提出了基于塊坐標下降的兩步迭代優(yōu)化算法,聯(lián)合優(yōu)化用戶終端本地計算的任務量、計算卸載的任務量以及無人機的軌跡,實現(xiàn)了用戶終端能耗最小化的目標。實驗結(jié)果表明,無論信道條件優(yōu)劣,基于塊坐標下降的兩步迭代優(yōu)化算法都能在保證用戶終端完成任務的同時,有效的降低用戶終端的能耗,達到節(jié)能的效果。下一步將考慮計算密集型任務下移動用戶對于低時延的要求,改進計算卸載的策略,以達到用戶終端能耗與系統(tǒng)時延之間的均衡。