基于動(dòng)態(tài)拍賣的多無人機(jī)任務(wù)分配算法

張蕾，楊冬梅，王潛

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

1 引言

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

3 系統(tǒng)模型

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

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

圖1 系統(tǒng)模型

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

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

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

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

3.2 任務(wù)模型

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

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

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

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

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

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

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

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

3.3 問題制定

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

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

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

4 任務(wù)分配算法

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

4.1 用戶投標(biāo)策略

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

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

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

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

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

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

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

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

4.3 算法流程

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

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

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

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

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

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

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

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

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

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

由圖3可以看出，本文所提的拍賣算法，在不同用戶任務(wù)數(shù)量下能夠讓用戶取得較高的收益。這是因?yàn)樵谟脩舾倶?biāo)過程中，不僅考慮了無人機(jī)的資源狀態(tài)還考慮任務(wù)的計(jì)算費(fèi)用。同時(shí)，結(jié)合圖2進(jìn)行分析可知，本文所提算法不僅能夠保障用戶的收益，還能保障無人機(jī)的計(jì)算收益。

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

6 結(jié)論

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