基于動態拍賣的多無人機任務分配算法

張蕾，楊冬梅，王潛

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

1 引言

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

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

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

2 相關工作

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

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

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

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

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

為了最小化地面設備和無人機的功耗，文獻［9］研究了無人機輔助移動邊緣計算系統的任務分配和資源分配。該方法通過結合優化軌跡、適當的任務分配和資源分配，使物聯網設備和無人機的能量最小化；采用塊連續上界最小化來解決所提出的系統強加的非凸結構。但該方法使用單架無人機，增加了任務失敗的風險。

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

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

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

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

文獻［17］中介紹了無人機在基于障礙物的環境中的協作任務分配，采用基于蟻群優化匈牙利算法相結合的方法應用于無人機編隊。考慮戰場環境，無人機從不同位置飛行，搜索該區域的目標并將其摧毀。該方法只關注飛行長度而忽略了任務分配的其他約束，使解決方案不切實際。

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

3 系統模型

3.1 網絡模型

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

圖1 系統模型

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

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

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

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

3.2 任務模型

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

考慮到用戶將任務卸載到無人機上執行，無人機會產生相應的計算成本。無人機的計算能耗表示為

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

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

其中，e表示存儲能耗系數。

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

地面用戶卸載任務獲得的收益為

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

3.3 問題制定

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

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

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

4 任務分配算法

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

4.1 用戶投標策略

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

其中，g為傳輸成本系數，lij表示用戶i和無人機j的距離，uj表示無人機的剩余資源。可以觀察到，傳輸成本隨著距離的增加而增加。

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

4.2 無人機的任務匹配

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

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

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

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

4.3 算法流程

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

Step 1：初始化參數，包括用戶任務參數和無人機相關參數。

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

Step 3：無人機根據匹配規則選擇用戶。

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

Step 5：輸出結果。

5 實驗仿真結果與分析

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

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

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

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

圖3 不同用戶數量下的用戶平均收益

6 結論

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