面向復雜任務的多無人機協同計算資源分配與優化

郭鴻志，王宇濤，王佳黛，劉家佳

(西北工業大學 網絡空間安全學院，陜西 西安 710072)

0 引言

在無人機空中計算中，計算卸載與資源分配[1](Computation Offloading and Resource Allocation,CORA)問題的目標是無人機在其性能(尺寸、計算能力、電量等)允許的范圍內，針對地面用戶的任務計算需求，確定各個無人機的任務執行序列，以確保任務的低時延或無人機的低能耗要求。隨著5G的發展和商用，時延敏感且計算密集型的復雜任務大量出現[2]。這些復雜任務包含多個存在數據依賴關系的子任務，需要遵從嚴格的子任務執行時序約束。例如，視頻導航任務涉及圖形、人臉檢測、攝像機預覽和視頻處理，可以劃分為14個依賴的任務[3]。面向原子任務(不可切分)的CORA，通常采用全卸載模式將整個任務卸載到一個無人機上[4-6]。而對于包含多個子任務的復雜任務的CORA，若采用全卸載模式將其全部卸載到一個無人機上計算將會存在兩個問題：第一，一個無人機的性能難以同時滿足所有子任務的計算資源需求，導致任務計算時延延長；第二，該無人機任務執行序列中后續任務的等待時延將被延長。因此，研究面向復雜任務的CORA方法來降低任務處理時延，保證用戶服務質量，具有理論和實際意義。

與全卸載模式相比，將復雜任務劃分為多個子任務，并采用部分卸載模式將子任務卸載到不同的無人機上計算，無人機將以較小的粒度靈活分配子任務需要的資源，從而進一步降低任務處理時延。同時考慮到子任務之間的數據依賴關系，部分卸載模式下需要無人機之間的高效協同。現有面向復雜任務的CORA研究工作存在一定局限性，其中，Ning等人[7]應用增強現實框架將復雜的應用模塊簡化為線性序列模塊，并設計了一個迭代啟發式邊緣計算資源分配算法給出部分卸載策略。該工作只適用于線性模型，未考慮其他幾種典型的任務關聯模型。Zhu等人[8]考慮部分卸載任務的相互依賴性，采用馬爾可夫決策過程求解得到卸載策略。該工作中，地面用戶的所有任務只能通過一個固定的地面接入點上傳到無人機，易產生堵塞，延長任務響應時間；無人機之間只能通過固定順序通信，處理任務不靈活。

基于此，本文構建了面向復雜任務的多無人機空中協同計算模型。在該模型中，復雜任務被表示為3種典型的子任務流模型，并采用部分卸載模式計算。為了降低復雜任務的處理時延，本文針對多無人機協同部分計算策略優化問題采用一種雙層博弈近似計算卸載算法求解。

1 系統模型

多無人機協同計算模型如圖1所示，無人機被劃分為管理無人機和計算無人機。其中，管理無人機負責收集計算無人機的可用資源和數據存儲信息等；計算無人機處理地面用戶的計算任務。在該模型中，任務采用部分卸載模式卸載到無人機計算，且每個計算無人機都維護一個任務執行隊列。計算無人機的信息表示為U={V,F,P,L,N}，其中，V={1，2，…,|V|}代表計算無人機的集合，|V|代表計算無人機的數量，F={f1,f2,…,f|V|}代表無人機的計算能力，P={p1,p2,…,p|V|}代表無人機的發射功率，L={(x1,y1),(x2,y2),…,(x|V|,y|V|)}代表無人機的二維坐標，N={N1,N2,…,N|V|}代表在計算無人機v的覆蓋范圍內的用戶集合。無人機懸停在高度為h的空中，Gk={pk,(xk,yk)}表示用戶k的發射功率和水平坐標。

圖1 系統模型Fig.1 System model

1.1 通信模型

1.1.1 空地通信

本文采用文獻[9-10]中的概率路徑損耗模型建模空地通信。該模型考慮了實際環境中不同發生概率的視距(Line-of-Sight,LoS)和非視距(Non-LoS,NLoS)通信，并定義用戶k與無人機v之間LoS/NLoS通信的概率為：

(1)

(2)

(3)

(4)

因此，用戶k與無人機v之間的空地通信速率可表示為：

(5)

式中，BG代表空地通信帶寬，N0代表噪聲功率，INk,v代表干擾功率信號。

1.1.2 空中通信

考慮到無人機懸停高度較高，空中通信主要由LoS鏈路主導，因此采用文獻[11]中的自由空間路徑損失模型，并將無人機v和v′之間的通信路徑損耗表示為：

(6)

因此，無人機v和v′之間的數據速率表示為：

(7)

式中，BA代表空中通信帶寬。

1.2 計算模型

(8)

2 任務處理過程

復雜任務的處理過程包括任務上傳、任務劃分及任務空中通信和計算、任務計算結果返回3個步驟。由于計算結果的數據量遠小于輸入數據，因此忽略結果返回的時間和能量成本[13]。

2.1 任務模型

如圖2所示，典型的子任務流模型包括線性模型、樹型模型和網狀模型3種，每條有向邊代表子任務之間的數據依賴關系。

(a) 樹形模型

2.2 任務處理時延

用戶i通過空地通信鏈路將任務上傳到無人機v的傳輸時延表示為：

(9)

子任務si,j的所有前驅子任務執行完畢后，將前驅子任務的輸出數據發送到計算si,j的無人機上，si,j才可以開始執行。由于子任務的中間輸出數據量小，本文忽略發送輸出數據的時間。

無人機v將子任務si,j傳輸到無人機v′的時延表示為：

(10)

計算子任務si,j的平均服務時延表示為：

(11)

考慮到子任務在無人機之間的傳輸與其前驅子任務的執行是同時執行的，定義子任務的空中通信和計算時延為：

t(si,j)=tcomp(si,j,v)+

(12)

在樹型和網狀模型中，一些子任務是并行執行的。因此，子任務流的處理時延取決于任務上傳時延與該子任務流中最大的空中通信和計算時延之和，表示為：

T(Si)=tG2A(Si,i,v)+max{t(si,j)}。

(13)

2.3 無人機能耗

計算無人機在處理任務過程中的能耗包括懸停能耗、通信能耗和計算能耗[14]。

(14)

式中，ph為最小懸停功率，η為功率效率，ε為無人機的有效開關電容。管理無人機的能耗主要只懸停能耗[15]，可表示為：

(15)

3 多無人機協同部分計算卸載策略優化問題

(16)

約束C1和C2代表任務卸載約束，即每個子任務只能卸載到一個計算無人機上執行；約束C3和C4代表無人機能耗約束，即計算無人機和管理無人機的能耗都不能超過無人機的能量預算e0；約束C5代表任務執行時序約束，即具有數據依賴關系的子任務必須遵守執行順序；約束C6代表任務響應時間約束，即任務需要在指定的最大時間限度Ti內完成。

4 雙層博弈近似計算卸載策略設計

該問題是一個非凸的最小最大化問題，是NP難的[16]。枚舉法可用于求解該問題，但是枚舉法的計算復雜度為O((mn)|V|)，運行時間長，導致其在實際應用中受到限制。因此，本文提出一種雙層博弈近似計算卸載算法。

博弈論被廣泛應用于解決具有不同目標的多個博弈參與者之間的決策問題[17]。多無人機協同部分計算卸載優化問題存在雙層博弈關系，因此本文提出了雙層博弈近似計算卸載算法。在內層博弈中，子任務流中的所有子任務作為博弈參與者，經過有限次博弈找到該子任務流的近似最優計算卸載策略；在外層博弈中，所有子任務流作為博弈參與者，經過有限次博弈找到所有博弈者的近似最優計算卸載策略，最終得到最小的任務處理總時延。具體實現步驟如算法1所示。

算法1 雙層博弈近似計算卸載算法輸入:初始卸載策略X0;輸出:近似最優的任務卸載策略X和最小任務處理總時延Tmin;初始化:需要更新策略的子任務集合Ui,j(t)和子任務流集合Ui(t);1: 從時刻t開始循環:2: 對于集合S中的每一個子任務流Si:3: 對于Si中的每一個子任務Si,j:4: 更改子任務的卸載策略,在滿足任務響應時間和無人機能耗約束的前提下,計算使子任務在時刻t+1處理時延最小的最優卸載策略;5: 將子任務放入Ui,j(t)并存儲其策略;6: ifUi,j(t)不為空then7: if子任務Si,j得到更新機會then8: 更新Si,j的策略以及X;9: endif10: endif11: 計算使子任務流在時刻t+1處理時延最小的最優卸載策略;12: 將子任務流放入Ui(t)并存儲卸載策略;13: ifUi(t)不為空then14: if子任務流Si得到更新機會then15: 更新Si的策略以及X0;16: endif17: endif18:循環結束

該算法在內層博弈中遍歷m個子任務，在外層博弈中遍歷n個子任務流，經過C次迭代，達到納什均衡狀態，得到了一個近似最優的卸載策略及其最小的任務處理時延。因此，該算法的計算復雜度為O(C×m×n)。

5 仿真實驗與結果分析

本節對本文提出的雙層博弈近似卸載算法求解面向復雜任務的多無人機協同計算資源分配與優化問題，并進行了仿真。實驗設計、實驗結果及實驗分析如下所示。

5.1 實驗設計

考慮在多無人機空中計算場景中，地面用戶隨機分布在1 000×1 000的區域中，每個用戶產生一個具有內在數據依賴的復雜任務。表1給出了仿真實驗的場景設置和參數取值。

表1 場景參數取值Tab.1 Scene parameter values

基于表1設定的參數取值進行兩組對比實驗，一是對比驗證雙層博弈近似計算卸載算法的有效性和高效率；二是通過對比不同的方案得到的任務總處理時延以及單個任務的處理時延，驗證雙層博弈近似計算卸載算法在降低時延方面的性能。

5.2 實驗結果及分析

為了評價雙層博弈近似計算卸載算法的有效性和高效率，圖3將該算法得到的任務處理總延遲和運行時間分別與窮舉搜索法(得到最優解)進行比較。從圖3(a)中可知，雙層博弈近似計算卸載算法得到的任務處理時延略高于窮舉法，說明雙層博弈近似計算卸載算法可以找到問題的近似最優解，證明該算法是有效的。圖3(b)的運行時間對比結果驗證了雙層博弈近似計算卸載算法的計算復雜度更低。因此，窮舉搜索法雖然可以得到最優解，但是在處理較大規模的問題時運行時間過長。雙層博弈近似計算卸載算法可以快速處理中等規模甚至大規模的實際問題。

(a) 任務處理時延對比

為了驗證雙層博弈近似計算卸載算法在降低任務處理延遲方面的性能，設計實驗將其與兩種已有方案進行對比。具體設計如表2中實驗方案設計所示，方案一[18]未考慮多無人機協同和部分卸載模式，方案二[19]只考慮了多無人機協同，但未考慮部分卸載模式，而雙層博弈近似計算卸載算法同時考慮了多無人機協同和部分卸載模式。

表2 實驗方案設計Tab.2 Experiment scheme design

由圖4可知，雙層博弈近似計算卸載算法得到的線性模型、樹型模型和網狀模型任務的處理時延都低于其他兩種方案。圖5中雙層博弈近似計算卸載算法得到的每個子任務流的時延相較于方案一更趨于穩定，相較于方案二時延更低。因此，雙層博弈近似計算卸載算法在降低任務處理時延方面具有更好的性能，能夠有效降低任務處理時延，合理利用無人機資源，實現無人機負載均衡。

(a) 線性模型

圖5 雙層博弈近似計算卸載算法與已有方案計算線性任務得到的每個子任務流時延對比Fig.5 Comparison of each subtask-flow’s processing delay with linear model between two-layer game-theoretic approximation computation offloading algorithm and existing schemes

6 結論

本文針對具有內在關聯特性的復雜任務，研究了面向復雜任務的多無人機協同部分計算卸載策略優化問題。其中，無人機進行角色劃分，通過各角色及角色之間的協同為地面用戶提供計算服務。在任務執行時序、任務響應時間、任務卸載和無人機能耗約束下，通過優化子任務的部分卸載策略最小化任務處理時延。為求解該非凸優化問題，本文提出了一個雙層博弈近似計算卸載算法求解得到任務的近似最優計算卸載策略。仿真結果驗證了該算法的有效性和低計算復雜度，且相較于已有的解決方案，該算法在降低任務處理時延方面具有更好的性能。