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

(西北工業(yè)大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，陜西 西安 710072)

0 引言

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

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

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

1 系統(tǒng)模型

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

圖1 系統(tǒng)模型Fig.1 System model

1.1 通信模型

1.1.1 空地通信

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

(1)

(2)

(3)

(4)

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

(5)

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

1.1.2 空中通信

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

(6)

因此，無人機(jī)v和v′之間的數(shù)據(jù)速率表示為：

(7)

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

1.2 計(jì)算模型

(8)

2 任務(wù)處理過程

復(fù)雜任務(wù)的處理過程包括任務(wù)上傳、任務(wù)劃分及任務(wù)空中通信和計(jì)算、任務(wù)計(jì)算結(jié)果返回3個(gè)步驟。由于計(jì)算結(jié)果的數(shù)據(jù)量遠(yuǎn)小于輸入數(shù)據(jù)，因此忽略結(jié)果返回的時(shí)間和能量成本[13]。

2.1 任務(wù)模型

如圖2所示，典型的子任務(wù)流模型包括線性模型、樹型模型和網(wǎng)狀模型3種，每條有向邊代表子任務(wù)之間的數(shù)據(jù)依賴關(guān)系。

(a) 樹形模型

2.2 任務(wù)處理時(shí)延

用戶i通過空地通信鏈路將任務(wù)上傳到無人機(jī)v的傳輸時(shí)延表示為：

(9)

子任務(wù)si,j的所有前驅(qū)子任務(wù)執(zhí)行完畢后，將前驅(qū)子任務(wù)的輸出數(shù)據(jù)發(fā)送到計(jì)算si,j的無人機(jī)上，si,j才可以開始執(zhí)行。由于子任務(wù)的中間輸出數(shù)據(jù)量小，本文忽略發(fā)送輸出數(shù)據(jù)的時(shí)間。

無人機(jī)v將子任務(wù)si,j傳輸?shù)綗o人機(jī)v′的時(shí)延表示為：

(10)

計(jì)算子任務(wù)si,j的平均服務(wù)時(shí)延表示為：

(11)

考慮到子任務(wù)在無人機(jī)之間的傳輸與其前驅(qū)子任務(wù)的執(zhí)行是同時(shí)執(zhí)行的，定義子任務(wù)的空中通信和計(jì)算時(shí)延為：

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

(12)

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

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

(13)

2.3 無人機(jī)能耗

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

(14)

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

(15)

3 多無人機(jī)協(xié)同部分計(jì)算卸載策略優(yōu)化問題

(16)

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

4 雙層博弈近似計(jì)算卸載策略設(shè)計(jì)

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

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

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

該算法在內(nèi)層博弈中遍歷m個(gè)子任務(wù)，在外層博弈中遍歷n個(gè)子任務(wù)流，經(jīng)過C次迭代，達(dá)到納什均衡狀態(tài)，得到了一個(gè)近似最優(yōu)的卸載策略及其最小的任務(wù)處理時(shí)延。因此，該算法的計(jì)算復(fù)雜度為O(C×m×n)。

5 仿真實(shí)驗(yàn)與結(jié)果分析

本節(jié)對本文提出的雙層博弈近似卸載算法求解面向復(fù)雜任務(wù)的多無人機(jī)協(xié)同計(jì)算資源分配與優(yōu)化問題，并進(jìn)行了仿真。實(shí)驗(yàn)設(shè)計(jì)、實(shí)驗(yàn)結(jié)果及實(shí)驗(yàn)分析如下所示。

5.1 實(shí)驗(yàn)設(shè)計(jì)

考慮在多無人機(jī)空中計(jì)算場景中，地面用戶隨機(jī)分布在1 000×1 000的區(qū)域中，每個(gè)用戶產(chǎn)生一個(gè)具有內(nèi)在數(shù)據(jù)依賴的復(fù)雜任務(wù)。表1給出了仿真實(shí)驗(yàn)的場景設(shè)置和參數(shù)取值。

表1 場景參數(shù)取值Tab.1 Scene parameter values

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

5.2 實(shí)驗(yàn)結(jié)果及分析

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

(a) 任務(wù)處理時(shí)延對比

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

表2 實(shí)驗(yàn)方案設(shè)計(jì)Tab.2 Experiment scheme design

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

(a) 線性模型

圖5 雙層博弈近似計(jì)算卸載算法與已有方案計(jì)算線性任務(wù)得到的每個(gè)子任務(wù)流時(shí)延對比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 結(jié)論

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