張蕾，楊冬梅，王潛

（1. 中國自控系統(tǒng)工程有限公司，北京 100026；2. 北京科技大學(xué)計算機與通信工程學(xué)院，北京 100083）

1 引言

無人機因部署方便快捷、機動性強、成本低、具有自組織能力以及靈活可擴展的優(yōu)勢，在民用和軍事中得到廣泛的應(yīng)用。多無人機系統(tǒng)應(yīng)用在大規(guī)模的任務(wù)中，即使在某些無人機出現(xiàn)故障的情況下也能提高成功完成任務(wù)的概率。此外，多無人機系統(tǒng)在各種惡劣的環(huán)境中可以提供不同的服務(wù)。為了保障無人機在執(zhí)行任務(wù)時的可靠性，任務(wù)分配算法在無人機通信時必不可少。在任務(wù)分配過程中需要無人機間相互協(xié)作，及時共享信息并進行適當(dāng)?shù)娜蝿?wù)調(diào)度和安排。因此多無人機任務(wù)分配得到了廣泛的研究和關(guān)注［1，2］。

與此同時，無人機的任務(wù)分配算法面臨著重大困難，設(shè)計多無人機系統(tǒng)并協(xié)同使用它們來實現(xiàn)任務(wù)目標帶來了極大的挑戰(zhàn)和復(fù)雜性［3］。多個任務(wù)的相互依賴性和軌跡優(yōu)化決定了無人機的協(xié)同性能。為了確保無人機之間的依賴性，需要實時協(xié)調(diào)路徑規(guī)劃和任務(wù)分配。因此，計算復(fù)雜度是設(shè)計協(xié)作無人機任務(wù)的重點［4］。無人機需要實時的服務(wù)且在惡劣環(huán)境中運行，必須處理動態(tài)環(huán)境的不確定性和約束，因此須在本地進行計算和決策來達到要求，這增加了多無人機任務(wù)分配的復(fù)雜性。同時，多架無人機會增加碰撞的可能性，任務(wù)分配過程中需考慮其路徑的可行性和高效性。在多無人機環(huán)境中，由于機上的計算資源有限且存在異質(zhì)性，一些無人機資源過剩，一些無人機可能會過載，從而影響任務(wù)的調(diào)度，因此統(tǒng)一負載均衡是任務(wù)分配過程中的困難之一。

無人機的任務(wù)分配是一個組合和優(yōu)化過程，它通過分配單個或多個任務(wù)到不同的無人機來最小化預(yù)期的目標函數(shù)。如果所有任務(wù)都完成且滿足約束，則該任務(wù)分配算法是符合該場景的需求。然而，大多數(shù)現(xiàn)有研究工作只優(yōu)化了少數(shù)約束，忽略了某些實際場景中的因素。在多無人機系統(tǒng)中，因為其結(jié)構(gòu)的異質(zhì)性，會選擇具有不同性能的無人機來處理異構(gòu)任務(wù)。在將任務(wù)分配給無人機時，無人機的性能是一個重要的約束。另一個決定任務(wù)分配效率的關(guān)鍵因素是時間限制。實際環(huán)境中都期望實時完成任務(wù)。在任務(wù)處理期間，環(huán)境中存在的風(fēng)險和不確定性為高效的任務(wù)分配算法帶來一定的困難。因此，為了提升不斷升級的多無人機系統(tǒng)的高效性以及可靠性，任務(wù)分配算法是多無人機系統(tǒng)穩(wěn)定且高效運行的基石。

2 相關(guān)工作

無人機的任務(wù)分配目的是通過分配無人機完成多項任務(wù)來最小化整體成本。一架無人機可以被分配單一或多個任務(wù)。任務(wù)分配算法面臨的問題是計算復(fù)雜性、任務(wù)耦合、問題規(guī)模、時間限制和異質(zhì)性?，F(xiàn)有的研究針對不同的特定應(yīng)用場景設(shè)計了不同的任務(wù)分配算法，大致分為四類：集中式、分布式、仿生和多融合。

集中式任務(wù)分配算法需要中央服務(wù)器從所有無人機收集信息，計算最佳策略并在無人機之間傳遞該信息。中央服務(wù)器可以是一個地面基站，接收來自所有無人機的信息，計算最優(yōu)規(guī)劃，并將規(guī)劃通知所有無人機。在某些情況下，其中一架無人機還可以充當(dāng)服務(wù)器，在集中式任務(wù)分配方案中每個無人機都與中央服務(wù)器進行通信。文獻［5］研究了任務(wù)分配中的決策過程，該過程使用改進的自注意力機制和自適應(yīng)任務(wù)規(guī)劃來提高可靠性。任務(wù)規(guī)劃器管理任務(wù)列表，根據(jù)任務(wù)的信息大小選擇現(xiàn)有的無人機來執(zhí)行任務(wù)。分配任務(wù)后，提交給路徑管理器，路徑管理器為每架無人機規(guī)劃可能的軌跡，UAV 控制器使用這些路徑坐標對多無人機進行控制。

文獻［6］中解決了任務(wù)分配中的優(yōu)化問題。由于時間限制，混合整數(shù)線性規(guī)劃（Mixed Integer Linear Programming，MILP）可以通過向UAV路徑添加時間約束來分配不可行的任務(wù)。它利用離散近似的真實場景，且彈藥對于探索、分類、攻擊和確認摧毀可實現(xiàn)的目標至關(guān)重要。假定有關(guān)目標區(qū)域的信息在無人機群的所有成員之間進行共享，基于MILP的公式由優(yōu)化函數(shù)、變量的上限和下限以及使用變量的約束組成，無人機只允許訪問任何目標兩次以防止循環(huán)，在重新分配發(fā)生之前，無人機可以訪問節(jié)點一次以找到新目標，這有助于避免無人機進入和離開時出現(xiàn)不一致。通過該方法，無人機的飛行路徑會發(fā)生變化，以確保時序約束得到滿足。由于該方法是對真實世界問題的離散表示，因此不符合實際應(yīng)用需求，且需要很高的計算時間，實時性較低。

文獻［7］中提出的改進兩部分狼群搜索（Modified Two-Part Wolf Pack Search，MTWPS）是一種使用圖形組合優(yōu)化模型的任務(wù)分配算法，該方案適用于目標尺寸較大的無人機，使用在線分層規(guī)劃算法解決時間敏感的不確定性問題。MTWPS分配多架無人機依次對目標進行分類、回復(fù)和驗證任務(wù)，使無人機具有不同的飛行高度以避免碰撞。該方法中一架無人機的等待時間取決于其他無人機的性能，這使大規(guī)模任務(wù)的等待時間變得復(fù)雜。

文獻［8］研究了一種用于協(xié)調(diào)自控?zé)o人機以提高多無人機操作的魯棒性和可擴展性的任務(wù)規(guī)劃和任務(wù)分配框架。戰(zhàn)場場景的主要目標是消滅敵方，因此最長任務(wù)時間包括搜索和攻擊。對于攻擊敵人的可能動作，使用了n個agent，每個agent被賦予一個特定的編號用于標識，即agent_id。智能體信息包括位置坐標、能量水平和有效載荷狀態(tài)，且本文假設(shè)敵方并不知道無人機的大小和位置。由于UAV的能量限制，需要一種經(jīng)濟高效的方法來將任務(wù)分配給最佳 UAV集，使用已識別目標的位置、可用代理的位置、可用電池和可用負載來確定每個攻擊行動的成本。但該方法并沒有考慮動態(tài)環(huán)境的不確定性。

為了最小化地面設(shè)備和無人機的功耗，文獻［9］研究了無人機輔助移動邊緣計算系統(tǒng)的任務(wù)分配和資源分配。該方法通過結(jié)合優(yōu)化軌跡、適當(dāng)?shù)娜蝿?wù)分配和資源分配，使物聯(lián)網(wǎng)設(shè)備和無人機的能量最小化；采用塊連續(xù)上界最小化來解決所提出的系統(tǒng)強加的非凸結(jié)構(gòu)。但該方法使用單架無人機，增加了任務(wù)失敗的風(fēng)險。

文獻［10］中基于動態(tài)編程（Dynamic Programming，DP）的合作任務(wù)分配研究無人機之間的合作與協(xié)調(diào)，依賴武器目標分配（其中武器被分配給目標以優(yōu)化任務(wù)分配），采用兩步DP近似方法。一步法負責(zé)快速生成合作解，兩步法以盡可能減少計算時間從而生成最優(yōu)解。但該方法的計算時間隨著目標數(shù)量的增加而增長，且忽略了真實復(fù)雜環(huán)境的不確定性。

由于通信開銷限制、魯棒性問題和可擴展性，集中式任務(wù)分配對無人機群是不適用的。一旦無人機數(shù)量增加，計算開銷變大，集中式算法的性能最大化就會被限制。在這種情況下，分布式方法有助于最大限度地減少這些問題。分布式任務(wù)分配算法主要針對任務(wù)以及無人機間的對應(yīng)耦合關(guān)系［11］。然而，去中心化算法需要協(xié)作來提高整體性能［12］，其中需要無人機交換大量環(huán)境信息、現(xiàn)有狀態(tài)和未來狀態(tài)，由此造成的大規(guī)模數(shù)據(jù)傳輸增加了無人機間存在威脅的可能性。文獻［13］中提出的基于共識的捆綁算法考慮無沖突任務(wù)分配，以解決兩個UAV操作復(fù)雜性，即UAV飛行過程中的無碰撞路徑和擾動行為。該方法擴展CBBA（Consensus-Based Bundle Algorithm）以解決障礙并減輕擾動，從而以最小的計算負載降低算法對噪聲的敏感性。但該方法可能無法發(fā)現(xiàn)所有目標，且存在動態(tài)威脅和不確定性。

仿生算法起源于根據(jù)生物處理問題的分析能力模仿生物行為。該類算法將生物的行為抽象化，并采用高效的的搜索算法收斂至最優(yōu)值。進化算法是用于尋找最優(yōu)解的隨 機方法，已經(jīng)被應(yīng)用于各種優(yōu)化問題［14］。 受生物有機體本性的激勵，個體為了生存而學(xué)習(xí)和適應(yīng)環(huán)境狀況，適應(yīng)度函數(shù)在每次迭代中評估并決定哪些個體適合下一代。文獻［15］采用最早可用時間（Earliest Available Time，EAT）與粒子群優(yōu)化（Particle Swarm Optimization algorithm，PSO）相結(jié)合的方法解決室內(nèi)無人機建模困難的問題，并以最短的計算時間找到最優(yōu)方案。無人機在飛行過程中可以承擔(dān)多項任務(wù)，調(diào)度器為無人機分配任務(wù)，對每架無人機執(zhí)行任務(wù)的時間、飛行路徑、懸停時間、等待時間、充電時間等進行規(guī)劃。但該方法允許單個無人機在特定時間占據(jù)一個位置，忽略了障礙物。

文獻［16］受農(nóng)民收獲能力的影響提出了多架無人機的任務(wù)分配，以最小可能相鄰距離為指針，快速解決多任務(wù)的最優(yōu)分配。文中每個必須摧毀的目標都需要各種彈藥，并據(jù)此建立了異構(gòu)無人機的協(xié)同任務(wù)分配模型，考慮了三種不同類型的任務(wù)集，即偵察攻擊和評估，并指定無人機的負載任務(wù)集。根據(jù)兩個三元組之間的幾何關(guān)系，即完全摧毀目標所需的彈藥和無人機裝載該彈藥的能力，決定任務(wù)是否完全執(zhí)行。該方法沒有考慮實際戰(zhàn)場的約束，忽略了動態(tài)環(huán)境中可能出現(xiàn)的威脅和不確定性。

文獻［17］中介紹了無人機在基于障礙物的環(huán)境中的協(xié)作任務(wù)分配，采用基于蟻群優(yōu)化匈牙利算法相結(jié)合的方法應(yīng)用于無人機編隊?？紤]戰(zhàn)場環(huán)境，無人機從不同位置飛行，搜索該區(qū)域的目標并將其摧毀。該方法只關(guān)注飛行長度而忽略了任務(wù)分配的其他約束，使解決方案不切實際。

為了滿足無人機應(yīng)用的要求，有研究采用了兩種或多種任務(wù)分配算法融合的方法。文獻［18］提出使用移動邊緣計算（Mobile Edge Computing，MEC）為資源受限無人機提供計算服務(wù)的節(jié)能多無人機任務(wù)分配。基于功率大小、無人機的現(xiàn)有計算資源，該研究制定了任務(wù)分配、設(shè)備耦合關(guān)系和計算資源分配最小化目標函數(shù)，以最大限度地減少能量消耗。該問題首先分解為三個子問題，并使用迭代塊坐標下降算法求解。文獻［19］研究了單個無人機輔助的MEC無人機在目標區(qū)域周圍漫游以作為服務(wù)器提供幫助。由于基于單個無人機的系統(tǒng)的性能和穩(wěn)定性受到限制，因此，該方法通過控制多無人機系統(tǒng)中設(shè)備和資源分配變量的關(guān)聯(lián)，改進且滿足能量、計算能力和任務(wù)完成的約束。但該方法會受到來自其他無人機移動設(shè)備的小區(qū)間干擾。

3 系統(tǒng)模型

3.1 網(wǎng)絡(luò)模型

如圖1所示，本文研究了一種多無人機輔助邊緣計算系統(tǒng)。假設(shè)K架無人機組成一個無人機集群，為地面用戶終端提供邊緣計算服務(wù)，其中無人機集群表示為K={1，2，…，k}。考慮在無人機集群網(wǎng)絡(luò)覆蓋下，有N個地面用戶設(shè)備?？紤]每個用戶都有一個計算密集型的任務(wù)需要處理?？紤]到地面用戶自身的計算能力較弱，為了提高計算效率和節(jié)省能耗，地面用戶將任務(wù)卸載到無人機上進行計算處理。在本研究中，考慮用戶任務(wù)是不可拆分的，即用戶任務(wù)要么卸載到無人機，要么在用戶設(shè)備本地上處理。

圖1 系統(tǒng)模型

為了更加貼合現(xiàn)實場景，采用三維笛卡爾坐標系表示無人機和地面用戶的位置。無人機的坐標位置可以表示為

其中，xi表示地面用戶的水平x軸坐標位置，yi表示地面用戶的水平y(tǒng)軸坐標位置。在本研究中，考慮無人機在服務(wù)期間，位置不發(fā)生變化。同時，無人機的位置信息對于地面用戶都是已知的。

在本研究中，考慮地面用戶設(shè)備將任務(wù)卸載無人機上計算需要支付相應(yīng)的費用。對于無人機而言，用戶任務(wù)i的收益等于用戶支付的費用減去任務(wù)計算成本，計算方式表示為

其中，Pij表示用戶i支付給無人機j的計算費用，Cij表示無人機j執(zhí)行任務(wù)i的計算成本。需要注意的是，不同的無人機的計算費用是不同的。對于任務(wù)的計算成本，我們考慮兩個方面：計算能耗和存儲能耗。

3.2 任務(wù)模型

我們使用四元組Ti=(Di，fi，F(xiàn)i，Li)表示用戶計算任務(wù)，其中D表示用戶計算任務(wù)的大小，f表示計算任務(wù)i的計算密度，F(xiàn)表示用戶計算任務(wù)i所需要的計算資源，L表示用戶卸載任務(wù)所產(chǎn)生的收益。為了有效利用計算資源，我們考慮無人機上都采用動態(tài)電壓和頻率縮放技術(shù)，能夠為調(diào)整CPU的計算頻率自適應(yīng)地控制計算資源?？紤]無人機的計算資源是有限，所以用戶任務(wù)卸載到無人機j上需要滿足計算資源約束：

考慮到用戶將任務(wù)卸載到無人機上執(zhí)行，無人機會產(chǎn)生相應(yīng)的計算成本。無人機的計算能耗表示為

其中，κ表示能耗系數(shù)。同時，考慮無人機的存儲能耗，可以表示為

術(shù)前準備也一改傳統(tǒng)的方式，以往術(shù)前3天進流食或半流食、禁食12小時、禁飲8小時、3天給預(yù)防用藥、進行常規(guī)灌腸，現(xiàn)在術(shù)前12小時進流食或半流食、禁食6小時、禁飲2小時、術(shù)前30分鐘給預(yù)防用藥、肺部手術(shù)不鼓勵灌腸（食管手術(shù)根據(jù)情況選擇性灌腸）。

其中，e表示存儲能耗系數(shù)。

綜上分析，任務(wù)i在無人機j上的計算成本C可以表示為

地面用戶卸載任務(wù)獲得的收益為

其中，g為傳輸成本系數(shù)，lij表示用戶i和無人機j的距離。

3.3 問題制定

我們考慮將無人機與用戶任務(wù)之間關(guān)系轉(zhuǎn)化為一個映射矩陣。其中表示用戶i選擇將任務(wù)卸載到無人機j上；反之，用戶i不將任務(wù)卸載到無人機j上。

綜上所述，本文考慮以無人機平均收益最大化的任務(wù)分配模型：

其中，約束1表示任務(wù)卸載約束，也就是說每個計算任務(wù)只能在一架無人機上執(zhí)行；約束2表示無人機的計算資源約束，其中表示無人機j的最大計算資源大?。患s束3表示無人機的存儲資源約束，其中表示無人機j的最大存儲資源大小。

4 任務(wù)分配算法

針對多無人機輔助邊緣計算的任務(wù)分配問題，本文設(shè)計了一種基于拍賣的任務(wù)分配算法。拍賣算法在所提出算法中，我們考慮無人機作為資源擁有方，在拍賣過程中作為資源出售者。用戶任務(wù)的作為計算資源需求方，在拍賣過程中作為資源購買者。換句話說，地面用戶通過向無人機購買計算資源完成自身的計算任務(wù)。本文所提的基于拍賣的任務(wù)分配算法主要包括兩個過程：用戶投標和無人機的任務(wù)匹配。

4.1 用戶投標策略

在用戶投標階段，每個地面用戶已知無人機位置信息和相應(yīng)的資源信息。在投標過程中，每個用戶根據(jù)每架無人機的資源狀態(tài)和位置信息選擇無人機。考慮到用戶將任務(wù)卸載到無人機會產(chǎn)生相應(yīng)的傳輸成本，所以我們定義了用戶選擇規(guī)則，主要包括用戶的傳輸成本和無人機的剩余可用資源，計算方式如下：

其中，g為傳輸成本系數(shù)，lij表示用戶i和無人機j的距離，uj表示無人機的剩余資源?？梢杂^察到，傳輸成本隨著距離的增加而增加。

基于無人機的資源狀態(tài)信息和用戶的傳輸成本，用戶會選擇傳輸成本最小且資源豐富的無人機作為卸載對象。對于用戶而言，上述的投標策略都是最符合自身效用的。

4.2 無人機的任務(wù)匹配

在無人機與任務(wù)匹配階段開始前，所有用戶需要選擇相應(yīng)的無人機完成投標。無人機的任務(wù)匹配階段主要是無人機根據(jù)自身的目標選擇合適的任務(wù)進行執(zhí)行。

考慮到用戶投標過程中會存在多個用戶的投標策略相同，也就是多個用戶選擇同一架無人機執(zhí)行任務(wù)。在這種情況下，選擇權(quán)發(fā)生改變，不再是用戶選擇無人機，而是無人機根據(jù)自身的目標作為相應(yīng)的選擇。因此，我們定義了計算任務(wù)性價比作為無人機的選擇規(guī)則，計算方式如下：

其中，w1和w2表示權(quán)重系數(shù)。從式（12）可以看出，無人機根據(jù)計算任務(wù)性價比選擇用戶任務(wù)時，不僅考慮了用戶的支付費用，還考慮了用戶計算任務(wù)的資源大小。

基于上述分析，當(dāng)多個用戶的投標策略相同時，相應(yīng)的無人機進行反向選擇。無人機計算每個用戶的計算任務(wù)性價比，選擇最優(yōu)的用戶與之匹配。

4.3 算法流程

本文所提的基于拍賣的任務(wù)分配算法過程如下所示。

Step 1：初始化參數(shù)，包括用戶任務(wù)參數(shù)和無人機相關(guān)參數(shù)。

Step 2：用戶根據(jù)投標策略選擇無人機。

Step 3：無人機根據(jù)匹配規(guī)則選擇用戶。

Step 4：重復(fù)Step2和Step3，直到所有用戶的計算任務(wù)完成匹配。

Step 5：輸出結(jié)果。

5 實驗仿真結(jié)果與分析

為了進一步分析本文所提出算法的性能，我們進行了相關(guān)實驗仿真?？紤]網(wǎng)絡(luò)范圍大小等于100 m×100 m，用戶和無人機隨機分布在服務(wù)范圍內(nèi)。假設(shè)無人機數(shù)量為3，飛行高度等于10 m，每架無人機的計算資源等于20 GHz，存儲資源等于10 GB，計算費用10。每個用戶的計算任務(wù)大小為［1 MB，5 MB］，計算密度等于［400，1 000］，計算資源需求等于［0.1 GHz，0.5 GHz］，計算收益等于［80，100］。具體實驗結(jié)果如圖2所示。

圖2 不同用戶數(shù)量下的無人機平均收益

為了進一步比較分析本文所提算法的優(yōu)劣性，我們考慮與不同投標策略的任務(wù)分配方案進行比較分析，主要包括：只考慮無人機距離的投標方案和只考慮無人機資源大小的任務(wù)分配方案。觀察圖2可知，隨著用戶任務(wù)數(shù)量的增加，本文所提算法得到的無人機平均收益高于其他競標策略。本文所提算法能夠?qū)崿F(xiàn)用戶計算任務(wù)的有效分配，平衡用戶與用戶之間的競爭關(guān)系，保證每個無人機的收益，以獲得較好的總體性能。

由圖3可以看出，本文所提的拍賣算法，在不同用戶任務(wù)數(shù)量下能夠讓用戶取得較高的收益。這是因為在用戶競標過程中，不僅考慮了無人機的資源狀態(tài)還考慮任務(wù)的計算費用。同時，結(jié)合圖2進行分析可知，本文所提算法不僅能夠保障用戶的收益，還能保障無人機的計算收益。

圖3 不同用戶數(shù)量下的用戶平均收益

6 結(jié)論

無人機技術(shù)的發(fā)展為地面物聯(lián)網(wǎng)設(shè)備的任務(wù)處理提供了一種新的解決方案。與固定的地面基站相比，無人機具有易于部署、成本低、機動性強的特點，能夠有效地接近地面物聯(lián)網(wǎng)設(shè)備。在本文中，我們的目標是設(shè)計一個多架無人機輔助的邊緣計算系統(tǒng)，為地面用戶設(shè)備提供計算服務(wù)覆蓋，從實現(xiàn)收益最大化。我們引入了動態(tài)拍賣算法來尋找用戶任務(wù)的最優(yōu)分配策略，并保障無人機的計算收益。最后，通過仿真結(jié)果驗證了該算法的有效性和優(yōu)越性。