無人機輔助移動邊緣計算中的任務卸載算法

李校林，江雨桑*

（1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.重慶郵電大學 通信新技術應用研究中心，重慶 400065）

0 引言

為了滿足用戶多樣化的需求，越來越多的物聯網設備被部署到網絡中，大量設備接入無線網絡并且依靠在線資源處理各種任務。通過核心網絡卸載大量任務，并在中央云服務器上處理會造成網絡流量擁塞，增加延遲。移動邊緣計算（Mobile Edge Computing，MEC）［1］的出現緩解了這些問題，它可以將云計算資源和服務遷移到離終端更近的地方，從而有效降低通信延遲和能耗。

MEC 網絡中，根據應用場景［2］，通常采用兩種卸載模式：部分卸載模式和二進制計算模式。部分卸載模式是計算任務被分為幾個部分，其中一部分在本地計算，其他部分則通過卸載到MEC 服務器來計算。在對計算要求較高的場景中，計算量較低部分可以本地計算，計算量較高部分可以卸載計算。對于二進制卸載模式，計算任務在本地計算或一起卸載計算。例如，在進行信道狀態信息估計時，為確保估計精度［3］，必須將收集到的原始數據樣本作為一個整體進行計算。

雖然MEC 有許多優點，但在現有工作中，MEC 服務器的部署是固定的［4-5］，隨時隨地部署MEC 服務器具有挑戰性。固定基礎設施提供的MEC 服務在通信設施稀疏或發生突發性自然災害的情況下無法有效工作。由于無人機（Unmanned Aerial Vehicle，UAV）靈活機動、易于部署、可快速響應，UAV 輔助MEC［6］系統被引入作為移動用戶的計算服務器。通過在UAV 上的MEC 服務器提供額外的計算資源，能加快終端設備的計算，避免移動用戶頻繁與云通信或將任務上傳到云，從而緩解通信擁塞的問題。但UAV 輔助MEC系統仍存在許多挑戰：如何選擇適當的終端設備調度來最小化所有終端的計算時延；如何在存在環境障礙（樹木或建筑物）的情況下動態選擇合適的通信鏈路；如何實時控制UAV軌跡。因此，動態選擇合適的通信鏈路和實時決策任務卸載比、控制UAV 軌跡在UAV 輔助MEC 系統中非常重要。本文的主要工作包括以下三方面：

1）考慮存在障礙物遮擋情況下的UAV 輔助MEC 系統，建立動態信道下的任務卸載問題模型。在能量約束條件下，以最小化最大處理時延為目標，通過聯合優化終端設備調度、UAV 軌跡和任務卸載比求解。

2）針對上述任務卸載問題，設計了相應的馬爾可夫決策過程（Markov Decision Process，MDP），提出一種基于雙延遲深度確定性策略梯度（Twin Delayed Deep Deterministic policy gradient，TD3）的時延最小化任務卸載算法（TD3 based Task Offloading Algorithm for Delay Minimization，TD3-TOADM）。該算法將MDP 元組作為訓練樣本，在動態信道條件下，實時控制UAV 軌跡和選擇最優任務卸載比。

3）仿真實驗表明，在不同參數和通信條件下，本文算法的表現均優于基于演員-評論家（Actor-Critic，AC）的任務卸載算法、基于深度Q 網絡（Deep Q-Network，DQN）的任務卸載算法和基于深度確定性策略梯度（Deep Deterministic Policy Gradient，DDPG）的任務卸載算法。

1 相關工作

現在的很多研究工作是關于UAV 輔助MEC 中的計算卸載［7］和軌跡控制［8］的。我們根據所提方法及其研究目標將UAV 輔助MEC 文獻分為以下幾種類型：

1）最小化整個系統或移動用戶的能耗。Xiong 等［9］為了減少推進能量，提出UAV 只在特定時間或特定位置提供卸載計算服務。這種方案未有效發揮UAV 靈活機動、易于部署的優勢。Wang 等［10］為了延長UAV 的運行時間和相關網絡壽命，通過聯合區域劃分和UAV 軌跡調度來最小化UAV的總能耗；但該方案不適用于動態場景。

2）最小化任務完成時間。Hu 等［11］采用基于罰雙分解和L0 范數的算法，最小化總處理時間，包括傳輸時間、計算時間和局部計算時間。嵇介曲等［12］提出一種懲罰凹凸過程的算法，求解所有用戶的最大時延總和最小問題；但未考慮實際應用中存在障礙物阻擋的情況。

3）權衡能耗和時延。Zhan 等［13］通過聯合設計UAV 的彈道、完成時間和卸載計算實現了系統的資源分配，最大限度地減少UAV 的能耗和完成時間。Zhang 等［14］考慮隨機用戶數據到達，在隊列穩定和UAV 軌跡約束下最小化長期平均加權和系統能量；但是該方法中的地面用戶是靜態的，在每個時隙中重新計算了從初始位置到目的地的整個軌跡，增加了計算復雜度。近幾年聯合優化方法被學者廣泛研究，由于UAV 的機載能量有限，聯合優化方法的能量消耗和計算速度均過 于苛刻。Chen 等［15］利用深 度強化學習（Deep Reinforcement Learning，DRL）方法控制卸載決策，以提高感知延遲的滿意度和移動用戶的能源消耗。

上述文獻中，大多數使用的UAV-地面信道模型遵循自由空間路徑損耗模型鏈路的確定性視距（Line Of Sight，LoS）信道，這在城市或郊區環境中并不準確。其次，UAV 輔助通信系統中通信條件是時變的，任務卸載問題大多非凸性強，傳統優化算法難以有效解決。最后，廣泛用于學習和優化UAV 輔助MEC 系統各種問題的機器學習算法［16］需要提前提供足夠的數據樣本，對于決策問題是不現實的。相比之下，DRL 由于其本質特征，即從現實環境動態學習采集數據樣本，已經成為解決這一決策問題的有效解決方案。基于上述分析，本文在一個由一架UAV 和多個終端設備組成的UAV輔助MEC 系統的場景下，考慮環境障礙的阻塞、通信條件時變和能量等約束，將非凸任務卸載優化問題定義為MDP 問題，考慮到高維連續動作空間，利用基于雙延遲深度確定性策略梯度的任務卸載算法TD3-TOADM 聯合優化終端設備調度、UAV 軌跡和任務卸載比使計算時延最小化。

2 系統模型

2.1 通信模型

本文考慮一個由M個終端設備和單個UAV 組成的UAV輔助MEC 系統，如圖1 所示。安裝有納米MEC 服務器的UAV 為所有終端設備提供計算和通信服務，終端設備的計算能力有限，每個終端設備卸載部分任務到UAV 計算，剩余任務在本地執行。整個任務卸載過程中產生的時延由終端本地計算時延傳輸時延和UAV 計算時延組成。

圖1 無人機輔助MEC系統的模型Fig.1 Model of UAV-assisted MEC system

UAV 以時分方式向所有終端提供計算服務，整個通信周期T等步長地劃分為N個時隙。假設UAV 和終端設備只能在給定區域內移動，每個時隙內，UAV 在一個固定的位置懸停，然后與其中一個終端建立通信。用二進制指標αm(n) ∈{0，1}來表示UAV 是否為終端提供服務，當UAV 在時隙n為終端提供服務時，αm(n)=1，否則為0。一個時隙內UAV 只能為一個終端提供服務，因此，終端設備調度約束為：

終端設備在該區域內低速隨機移動，在笛卡爾三維坐標系中，時隙n∈{1，2，…，N}時，終端m∈{1，2，…，M}的坐標表示為wm(n)=[xm(n)，ym(n)]T。UAV 保持在固定高度H飛行時，投影在水平面上的坐標為q(n)=[x(n)，y(n)]T，UAV 飛行到新的懸停位置后更新坐標為q(n+1)=[x(n+1)，y(n+1)]T。在每個時隙，UAV 的移動性策略［17］可以表示為：

其中：v(n) ∈[0，vmax]表示飛行速度；tfly是固定的UAV 飛行時間；θ(n) ∈[0，2π]表示UAV 在x-y平面相對于x軸的水平方向。除此之外，UAV 飛行消耗的能量［11］表示為：

其中G表示飛機的載荷。

在UAV 輔助MEC 系統中，UAV 和終端設備之間的通信鏈路由視距信道主導，信道建模采用了自由空間路徑損耗模型。假設UAV 與終端通信時為準靜態場景，終端和UAV 在計算卸載期間保持不變。則在時隙n時UAV 和終端m的平均信道增益［12］可以建模為：

其中：β表示參考距離1 m 時的信道增益；dm(n)表示終端m與UAV 的歐氏距離；H表示UAV 的飛行高度。

考慮到UAV 和終端之間可能會有障礙物的阻擋，終端m在時隙n時的無線傳輸速率可以表示為：

其中：B表示傳輸帶寬；σ2表示高斯白噪聲功率；P表示終端在上行鏈路的傳輸功率；pNLOS表示非視距條件下的傳輸損耗；bm(n)表示在時隙n時UAV 與終端m之間是否有障礙物阻擋（bm(n)為1 表示有阻擋，為0 表示無阻擋）。

研究中常用無線傳輸速率公式可參考文獻［18］。考慮到實際應用中存在阻礙物遮擋產生傳輸損耗的可能，本文使用文獻［19］中的微波技術，將非視距條件下的傳輸損耗添加到公式中表示障礙物對UAV 通信的影響。當UAV 和被服務終端有阻擋時會產生傳輸損耗，傳輸速率下降，無阻擋時與常用公式相同。

2.2 計算模型

本文中的UAV 輔助MEC 系統采用部分卸載模式，定義cm(n)為終端m在時隙n卸載到UAV 上的計算任務比例，1 -cm(n)為在本地計算的任務比例。

1）本地計算。

計算任務在終端本地執行時，終端m在時隙n的本地執行時延表示為：

其中：Dm(n)表示終端m計算任務的大小；C表示處理1 bit 任務所需的CPU 周期；fm表示終端m的計算能力，單位是每秒CPU 的圈數。

2）卸載到UAV 計算。

由于MEC 服務器處理后的計算結果非常小，可以忽略不計，所以本文不考慮下行鏈路的發送延遲。UAV 服務器的處理時延可分為兩部分，首先是終端m在時隙n將任務卸載到UAV 的傳輸時延，可表示為：

其次是服務器計算產生的時延，表達式如式（10）：

其中：fUAV表示UAV 的計算能力。此時UAV 計算任務產生的能量消耗為：

其中：κ為芯片結構對CPU 處理的影響因子，κ=10-27。

2.3 問題建模

在本文提出的UAV 輔助MEC 系統中，目的是在離散變量和能量消耗的約束下，聯合優化終端設備調度、UAV 軌跡和任務卸載比，以最小化所有終端的最大時延之和。綜上，優化問題建模為：

其中：E表示UAV 電池容量；式（13）～（14）是約束終端和UAV 只能在給定區域移動；式（15）表示無線信道中的阻塞情況；式（16）表示任務卸載比；式（17）～（18）是保證調度一個設備在時隙n進行計算；式（19）是指UAV 要在整個通信周期完成所有計算任務；式（20）是確保UAV 飛行和卸載計算在所有時隙消耗的能量不超過最大電池容量。

3 算法設計

上述優化問題是一個混合整數非凸性問題，并且，在所考慮的場景中，系統狀態的復雜性高，計算任務卸載決策需要連續動作空間的支持。采用傳統的優化方法難以解決上述問題。DRL 已被證明是處理高維連續空間［20］復雜控制問題的有效方法。因此，本章提出一個基于DRL 的方案解決優化問題。強化學習（Reinforcement Learning，RL）是一種具有自學習能力并能做出最佳決策的算法，它考慮了agent 與其環境之間交互的例子，旨在學習最大化回報的策略。RL可以用來解決定義為四元組(S，A，P，R)的MDP 問題，其中：S為狀態空間，A為動作空間，P為狀態轉移概率，R為獎勵函數。每時隙在給定狀態s∈S的情況下，agent 選擇與其策略π：S→P(A)相關的行動a∈A，并獲得獎勵r∈R。MDP 的目標是找到一個能夠最大化預期累積收益Rn=表示折扣因子）的最優策略。DRL可以被認為是RL 的“深度”版，它使用多個深度神經網絡（Deep Neural Network，DNN）作 為Q 值函數Q(s，a)=E[(Rn|s，a)]的逼近器，Q(s，a)是在狀態s中執行操作a時的預期收益。

3.1 構建MDP

為了能夠應用DRL 方法解決優化問題，本文將原問題重新表述為MDP 結構。UAV 輔助MEC 系統中計算卸載問題的狀態、行為和獎勵如下：

1）狀態空間。在本文的UAV 輔助MEC 系統中，狀態空間由M個終端、UAV 及其環境共同確定。時隙n時狀態空間表示為sn={W(n)，bm(n)，q(n)，D(n)，Dr(n)，Er(n)}，其 中：W(n)={w1(n)，w2(n)，…，wM(n)}表示被UAV 服務的終端m的位置；q(n) 表 示UAV 的位置；bm(n)={b1(n)，b2(n)，…，bM(n)}表示終端m的信號是否被障礙物阻擋；D(n)={D1(n)，D2(n)，…，DM(n)}表示終端m隨機生成的任務大小；Dr(n)表示系統在整個時間段內需要完成的剩余任務的大小；Er(n)表示UAV 剩余的電量。

2）動作空間。agent 根據系統當前狀態和觀察到的環境，選擇待服務的終端m、時隙n時任務卸載比、UAV 飛行角和UAV 飛行速度。因此，系統動作集可以表示為：an={m(n)，cm(n)，v(n)，θ(n)}，其中：m(n) ∈[0，k]表示終端設備調度的 動作變 量，如 果m(n)=0，m=1；m(n) ≠0，m=是向上取整符號。在連續的動作空間內，UAV 的飛行角度、飛行速度和任務卸載比能夠被精確優化。通過聯合優化動作空間內的4 個變量，系統計算卸載的時延能最小化。

3）獎勵函數。本文目標是在保證能量消耗的前提下，最大限度地降低任務計算卸載的時延。因此，每個動作的目的是最小化最大計算時延，系統獎勵應該與最大計算時延負相關，其定義為：

當執行動作an后，計算時延越小獲得的獎勵越大，就越會向期望的方向發展。

3.2 基于TD3的任務卸載算法

根據3.1 節構建的MDP 問題，考慮到任務卸載優化問題的高維連續動作空間，提出基于TD3［20］的任務卸載算法TD3-TOADM，如圖2 所示。TD3 算法包括一個權重為φ的Actor網絡和兩個權重為θ1和θ2的Critic 網絡，這兩個Citict 網絡可以解決Q 值的高估問題，獲得更好的學習效果。因此，TD3算法能更穩定地求解本文的優化問題。此外，為提高學習穩定性，TD3 采用了權重為φ′的Actor target 網絡和權重為和的Critic target 網絡。

圖2 TD3-TOADM網絡框架Fig.2 TD3-TOADM algorithm network framework

算法1 總結了解決任務卸載優化問題的TD3-TOADM，該DRL 算法不需要提前提供足夠的數據樣本。算法具體流程如下：首先，初始化6 個神經網絡的權重參數和經驗緩存。在每一回合（對優化問題的一次求解），UAV 根據Actor online網絡πφ(s)和隨機噪聲ε選擇行動。UAV 執行動作后將獲得獎勵rn和下一個狀態sn+1以及狀態轉移樣本(sn，an，sn+1，rn)。為了穩定訓練過程并提高樣本效率，UAV 將狀態轉移信息(sn，an，sn+1，rn)存儲在經驗緩存區R中作為訓練online 網絡的數據集，然后從經驗緩存中隨機抽取大小為Bs的狀態轉移信息數據(sj，aj，，rj)作為Actor online 網絡、Critic online 網絡的一個小批量訓練數據。當經驗緩存已滿時，算法采用以下的方式來更新經驗緩存：首先找出經驗緩存中獎勵值最小的狀態轉移信息數據，若該數據的獎勵值小于新數據的獎勵值，則用新數據替代這個數據；否則新數據替代經驗緩存中最舊的數據。通過將sj輸入Actor online 網絡生成策略πφ(sj)，UAV 可以使用策略梯度法更新Actor online 網絡的權重：

此外，為防止在Q值的窄峰上過度擬合，將隨機噪聲ε添加到Actor target 網絡中，這樣可以實現更平滑的狀態動作值估計。修改后的目標動作如下：

然后可以獲得目標動作值：

根據策略πφ(sj)，兩個Critic target 網絡將通過最小化損失函數L(θi)執行梯度下降來更新權重θi，同時獲得兩個Q 值Qθ1(sj，πφ(sj))和Qθ2(sj，πφ(sj))。L(θi)定義為：

接下來，根據式（22）和（25），UAV 可以使用以下等式更新3 個online 網絡的權重：

其中：αa和αc為學習率，UAV 每d個時隙更新Actor online網絡。

最后，為了穩定訓練過程，通過復制相應online 網絡的權重，UAV 根據式（27）～（28）更新3 個target 網絡的權重：

其中：τ為軟更新系數。

算法1 基于TD3 的任務卸載算法TD3-TOADM。

用式（26）更新Actor online網絡。

根據式（28）更新3個target網絡的權重。

4 仿真實驗和結果分析

4.1 仿真環境以及參數設置

仿真實驗使用Python3.7 和TensorFlow1 框架在Anaconda 平臺上模擬系統環境，設置了1 個UAV 和4 個地面終端設備隨機分布在一個100 m × 100 m 正方形區域的模型，對UAV 軌跡、終端設備調度和任務卸載方案進行仿真，實現了TD3-TOADM 任務卸載算法。仿真中的其他參數主要參考文獻［12］，如表1 所示。

表1 主要參數設置Tab.1 Main parameter setting

4.2 結果分析

首先對算法中重要的超參數折扣因子γ進行分析，γ取適當的值將提高訓練后策略的最終性能。為確定γ值，設算法網絡參數學習率αa=0.001，αc=0.002，經驗緩存大小為104，批學習大小Bs為64。γ分別取0.001、0.5 和0.9，它對算法性能的影響如圖3 所示。結果表明，γ=0.001 時，計算卸載策略性能最佳、時延最小，故本文實驗將γ設置為0.001。

圖4 展示了UAV 在任務大小為100 Mb 和60 Mb 情況下的卸載軌跡。為了反映UAV 位置變化對計算時延的影響，每個時隙對軌跡進行采樣繪制UAV 軌跡，可以觀察到，隨著任務大小的增加，UAV 飛得更靠近距離遠的終端，從而有助于建立高質量的鏈路，進一步減少卸載時間。

圖4 任務大小不同時的UAV軌跡Fig.4 Trajectory of UAV with different task sizes

為驗證TD3-TOADM 的有效性和優越性，本文選取3 種任務卸載算法在相同的應用場景下進行仿真對比：第一種是基于AC 的任務卸載算法，它可以解決連續動作空間問題；第二種是基于DQN 的任務卸載算法，這是傳統的基于離散動作空間的DRL 算法；第三種是基于DDPG 的任務卸載算法，該算法是近年各類研究中經常使用的先進DRL 算法。圖5展示了計算任務大小為100 Mb 時，不同算法下時延隨訓練次數變化的情況。從圖中可以看出，隨著迭代次數的增加，AC 算法難以收斂，而DQN 算法、DDPG 算法和TD3-TOADM都可以收斂。因為AC 算法存在著Actor 網絡和Critic 網絡同時更新的問題，在某些情況下可能不收斂。而其他3 種算法有雙網絡結構（評價網絡和目標網絡），能找到最優的行動策略后收斂。在各算法收斂后，TD3-TOADM 得到的時延為59.59，DDPG 算法得到的時延為64.93，DQN 算法得到的時延為92.33，TD3-TOADM 得到的計算時延減小了8.2%以上。

圖5 不同算法的收斂性對比Fig.5 Comparison of convergence of different algorithms

在滿足UAV 電池容量約束下，本文將AC 算法、DQN 算法、DDPG 算法、TD3-TOADM 得到的計算卸載時延作為評價標準。圖6 展示了各算法在不同任務大小、終端數量和飛行時間下的計算時延。由圖6 可知，對于相同的任務大小、終端數量和飛行時間，TD3-TOADM 的時延在4 種算法中始終最低。以圖6（a）為例，當任務大小為60 Mb 時，DDPG 算法的時延為39，DQN 的時延為73，TD3-TOADM 的計算時延減小了23%以上。隨著終端數和飛行時間的增加，AC 算法和DQN 算法的時延波動較大，DDPG 算法波動較小，TD3-TOADM 趨于平穩。這是因為DQN 算法輸出動作取值范圍差異較大。因此，當樣本作為訓練DNN 的輸入時，DNN可能傾向于輸出更大的值。DDPG 算法和TD3-TOADM 的Actor 網絡輸出多維動作，能確保DNN 的輸入數據都在［0，1］范圍內，保證其收斂性和穩定性。

為研究終端計算能力對系統進行卸載任務的影響，圖7分別測試了在不同終端計算能力（fm)下，TD3-TOADM 計算卸載產生的時延和任務卸載比。可以發現，終端計算能力較小時，本文優化方案優化后的處理延遲要高于終端計算能力較高時的處理時延。另一方面，從圖7（b）中能看出當終端的計算能力較大時，系統的平均任務卸載比較小，終端更傾向于在本地執行任務。終端計算能力越小，系統的數據處理越慢，導致本地執行和卸載之間的最大時延越大。這說明任務卸載比是對連續動作控制系統延遲影響較大的因子。

圖7 TD3-TOADM的終端計算能力對比Fig.7 Comparison of terminal computing power of TD3-TOADM

上述實驗對比結果表明，本文TD3-TOADM 的表現均優于對比的3 種卸載算法，具有較好的收斂性和魯棒性。因此，TD3-TOADM 能夠聯合優化終端設備調度、UAV 軌跡和任務卸載比后得到相對較小的最大處理時延。

5 結語

本文研究了在一個通信周期內，同時服務于多個用戶的UAV 輔助MEC 系統中的任務卸載問題。為解決計算任務卸載產生的時延過大的問題，提出一種基于DRL 的任務卸載算法TD3-TOADM 學習和優化計算任務卸載。該算法以計算任務大小、終端和UAV 位置等為輸入，在電池容量等約束下，連續自適應學習調整計算卸載策略，對多個目標進行優化，通過聯合優化終端設備調度、UAV 軌跡和任務卸載比以最小化計算時延。仿真實驗結果表明，本文的TD3-TOADM任務卸載算法在處理時延方面有較好的性能。在未來的研究中，將會考慮多UAV 等復雜場景下的MEC 任務卸載問題。