信息重傳與丟包補償的多無人機分布式任務分配方法

曹嚴, 龍騰,2, 孫景亮,2*, 周禹澤

(1.北京理工大學 宇航學院, 北京 100081; 2.北京理工大學重慶創新中心, 重慶 401120)

0 引言

隨著戰爭形態向自主化、智能化方向演進,常規武器難以滿足高精度、高動態、低成本的作戰需求,無人機集群協同作戰具備戰場感知、態勢推理、任務規劃等智能化能力,具備對戰場敵目標群執行高效抵近偵察、多方位自主識別及飽和打擊等3D(Dull, Dirty and Dangerous)任務[1],逐步發展為現代戰爭的重要作戰力量。任務分配技術是支撐無人機集群協同作戰的關鍵技術之一,旨在以收益最大化為目標,綜合考慮任務要求、無人機性能以及作戰環境,為各機指派一定數量及類型的作戰任務,避免己方資源沖突,確保無人機集群多任務的高效執行,體現集群協同的作戰優勢。任務分配方法通常可劃分為集中式與分布式兩類方法。集中式方法依靠中心節點生成任務分配方案,并向集群系統內各機分發分配結果。例如,范博洋等[2]面向協同偵打任務,研究了無人機與無人車的空地協同任務分配問題。但由于絕大多數任務分配問題的NP-hard特性,隨著系統內集群規模的增加,集中式方法獲得可行分配方案的求解耗時也顯著增長。另外由于中心節點的存在,系統抗毀性不足。而分布式任務分配方法通過機間信息交互達成分配方案一致,系統不依賴中心節點且具有良好的可擴展性,是當前的研究熱點。然而,真實戰場環境下機間通信處在非理想狀態,通信丟包等因素會導致分布式任務分配方法的性能降級。

當前圍繞分布式任務分配已開展大量研究工作,其中基于市場競爭機制的方法是主要研究方向之一。在無人機集群典型應用場景中,單個任務的收益計算通常依賴于其他任務執行順序,即任務間存在耦合依賴關系(ID)[3],導致分配問題具有NP-hard特性。Choi等[4]提出了一致性束算法(CBBA),用于求解包含依賴關系的單對多(SR-MT-ID)[3]任務分配問題,算法包含任務包貪心構建和沖突消解兩個階段。HIPC(Hybrid Information and Plan Consensus)[5]和PI(Performance Impact)[6]算法均采用沖突消解的方式在局部各機達成任務分配一致性共識,其中HIPC通過維護全局信息構建任務序列,而PI則是通過直接優化分配問題的目標函數來提供合理的分配方案。此外,組合優化與群智能等相關方法也是分布式任務分配領域的主要研究方向。其中DHBA(Decentralized Hungarian Based Algorithm)[7]是確定性組合優化方法匈牙利算法的分布式形式。分布式群智能方法的代表性研究則包括隨機蟻群優化算法[8]和分布式遺傳算法(DGA)[9]。

然而,現有文獻大多采用簡易模型模擬機間的通信條件。Ismail等[10]為各機在n×n任務空間內建立直徑為n/2的磁盤通信模型。文獻[11]使用全連通網絡拓撲和一字型拓撲對比任務分配方法的性能。Zhao等[6]分別采用一字型、中心輻射型、環型和網狀拓撲模擬不同的通信場景。文獻[5]引入網絡拓撲連通度概念評估HIPC算法的性能。陳璞等[12]面向動態任務分配問題,考慮通信距離與時間延遲等約束,設計局部一致性任務聯盟分配方法。文獻[13]在聯盟組建中進一步考慮航跡效能因素影響,提升任務效能模型真實性。王琳蒙等[14]面向無人機空戰中的信息非完備問題,從攻防博弈建模的角度設計了反向學習的改進麻雀算法,實現了納什均衡。但上述研究并未考慮環境干擾、路徑損耗導致的通信丟包影響。Otte等[15]采用Bernoulli和Gilbert-Elliot通信模型對比研究了通信丟包條件下多種典型拍賣框架的求解性能,該工作探尋了數據丟包下各典型拍賣分配架構的求解特征與規律,對后續研究工作開展具有指導意義。Han等[16]在設計無人機的控制策略時建立了信噪比(SNR)閾值模型,用以描述數據傳輸的質量,若SNR大于閾值則數據接收是可靠的;否則數據出現丟包。Nayak等[17]基于該丟包模型對比了5種典型分布式任務分配方法,揭示了CBBA算法在不同場景下的性能優勢。Carrillo等[18]提出了一種元推理方法,使無人機集群能夠根據機間通信質量自適應地選擇任務分配算法。

考慮到分布式任務分配方法依賴機間通信完成分配過程,當分配問題規模上升時,機間通信負載增大。為克服該問題,文獻[11]將CBBA一致性協調階段改進為異步通信方式,減少了機間通信量。Mazdin等[19]提出了時間觸發與事件觸發的信息傳輸機制,可以有效補償通信丟失的信息。符小衛等[20]基于運動狀態估計消解通信時延下的多機任務指派沖突,當局部位置狀態誤差大于給定閾值時,引發間歇通信糾偏機制。文獻[21]在滾動時域框架下根據機間通信距離實時切換信息交互策略,實現了通信距離受限的多機協同探測任務。CA-CBBA(Communication-Aware CBBA)[22]方法采用通信協議與分配算法協同設計的思路來處理消息沖突與帶寬限制。

目前,分布式任務分配領域圍繞通信丟包建模及典型算法對比開展了一定工作,但相關算法的適應性改進設計少有開展。本文面向通信丟包下分布式任務分配方法可靠設計的需求,主要開展以下工作內容:

1)提出了機間信息重傳機制,并在通信丟包條件下分析了該機制對CBBA算法收斂速度提升的效果。

2)提出了丟包估計分布式任務分配(LE-DTA)算法,顯著降低了機間信息重傳機制導致的通信冗余,并證明了算法的收斂性,有效解決了高丟包率、低網絡拓撲連通度下難以可靠、快速實現分布式任務分配的問題。

1 問題建模

本節圍繞戰場中多目標協同抵近偵察任務建立單對多(SR-MT)典型任務分配問題模型及機間通信丟包模型。

1.1 任務分配問題模型

定義I={1,…,Nu}為Nu架同構無人機組成的無人機集合,J={1,…,Nt}為Nt個待偵察目標構成的目標集合。單機按時序先后可對多個目標執行偵察任務,各目標僅需單架無人機抵近偵察。定義分配方案χ={p1,…,pi,…,pn},其中pi表示無人機i∈I的目標執行序列。單機的任務收益與該機目標執行序列相關,任務分配全局目標為最大化各機收益的總和,可表示為

(1)

s.t. |pi|≤Ci

(2)

(3)

(4)

1.2 通信丟包模型

考慮大尺度上無線信號路徑衰落與小尺度上信號多徑衰減效應,非理想通信下信噪比模型可描述為對數正態分布[25],即

(5)

(6)

式中:Θ(i,k)=PT-PL0-10αlg(di,k/d0)-Pbar,di,k為i、k兩機間的距離。定義dhop為無人機間單跳通信距離,無人機僅能與單跳內的鄰機進行信息交互。dhop的計算方式如式(7)所示,當無人機間距離超過dhop時,機間數據傳輸丟包概率近似為1。

(7)

(8)

式中:符號?表示數據從左側無人機可成功傳輸至右側無人機,符號上方為機間傳遞數據包內容,?/則表示傳輸中數據包丟失。

2 機間信息重傳機制

由于丟包模型中存在噪聲干擾項,數據丟包是獨立的隨機概率事件。本文設計機間信息重傳機制,以增加數據傳輸成功的概率,并分析信息重傳對算法收斂迭代次數的影響。以無人機i為例,信息重傳機制描述如下:

在任務分配過程開始前,無人機i首先與他機交互自身位置信息(或將他機位置信息提前裝訂),并結合式(6)依據機間位置關系計算數據傳輸的丟包概率P(i,k),k∈I,k≠i。任務分配過程啟動后,無人機i的數據包發送機制由CBBA原算法的單次發送轉變為基于丟包概率的多次發送。通常兩機間預估丟包概率越大,在單輪迭代中機間所需的信息重傳次數越多。為進一步闡述數據丟包對CBBA算法收斂性的影響,分析信息重傳機制對算法收斂速度提升的優勢,在考慮通信丟包因素的前提下,本文提出如下定理。

證明將信息從無人機i〈η-1〉成功傳遞至i〈η〉所需的迭代次數記為事件Xη,從i〈0〉傳遞至i〈k〉所需的迭代次數記為事件X,則X可被分解為連續發生k次事件Xη。由于事件Xη的期望為E(Xη)=1/(1-p(i〈η-1〉,i〈η〉)),則

(9)

證畢。

(10)

引理3在同步沖突消解框架下,若CBBA算法收益函數滿足DMG條件且機間保持靜態通信網絡拓撲,則各機與SGA算法前n輪分配方案一致所需的迭代次數期望為

即

(11)

(12)

則對于k≤m+1,有

(13)

定理1在同步沖突消解框架下,若CBBA算法收益函數滿足DMG條件且機間保持靜態通信網絡拓撲,則考慮信息重傳機制下的算法收斂迭代次數Ncvg期望為

(14)

由于n的任意性,n=Nt同樣成立,而Nt為算法收斂所需分配的目標數量。另外,根據文獻[4]中的引理3,已生成的分配方案不會在后續迭代中更改。因此,經過

輪迭代,結合信息重傳機制的CBBA算法期望達成收斂。證畢。

定理1描述了考慮信息重傳后CBBA算法收斂迭代次數的期望,則標準CBBA算法在數據丟包下的收斂迭代次數期望可以看作定理1中重傳次數為0的特殊情況,

(15)

3 丟包估計分布式任務分配算法

信息重傳機制可以有效降低數據丟包下CBBA算法的收斂迭代次數,但同時會帶來較大機間通信負載。在確保算法快速收斂的基礎上,為進一步降低機間傳輸信息量,本文提出丟包估計分布式任務分配(LE-DTA)算法。

3.1 算法原理及流程

LE-DTA算法用于估計CBBA算法在機間信息傳輸中的丟包內容。由于收益函數滿足DMG條件,各機在構建任務序列時先加入的目標標書值大于后加入的目標,而沖突消解過程促使各機依據收到的最大標書值更新自身標書列表。在算法啟動初始階段,當含有最大標書值的信息傳播至系統內的全部無人機時,各機形成關于最大標書值及其對應中標無人機的共識,且該分配對(最大標書值與對應中標無人機)在后續迭代過程中保持不變。注意到,雖然各機在信息交互時會將自身任務序列內全部目標及對應中標無人機信息向他機發布,但對本機更新最主要的信息為他機當前最大標書值對應的分配對。因此,若在機間通信數據丟失后本機能準確計算他機當前最大標書值及其對應中標無人機,即可將該估計信息替代丟包信息更新自身標書列表。在下一輪系統內的信息傳播中,各機目標是形成次高標書值及對應中標無人機的共識,上述估計方法仍適用。此過程持續進行,直至所有目標的分配方案在全體無人機內達成一致,算法結束。

完成他機當前最大標書值解算是LE-DTA算法的核心。為實現這一功能,本機需要在本地維護三個列表:b(n)∈(J∪{?})Nu×maxCi,∈和∈INu×Nt,分別表示各機任務包序列、各機預估標書列表及預估中標無人機列表。本機依據b(n)估算他機標書值,并利用與替代丟包數據參與沖突消解過程。無人機k在第n輪迭代中的最大標書估計值表示為其中表示無人機k的任務包序列,而根據可以求得無人機k的目標執行序列

(16)

本機預估他機標書值時,需根據當前算法迭代次數與網絡拓撲結構確定被預估對象。若本機i與單跳鄰機k通信出現丟包,則以無人機k為根節點,不包含子節點i的全部關聯節點構成的樹結構定義為i的丟包分支|→k。根據當前算法迭代次數,LE-DTA算法僅需對丟包分支內對應跳數的無人機進行預估,無需對系統內對應跳數的全部無人機進行估計,從而降低算法計算量。考慮圖1中的網絡拓撲結構,以1號 機為例,其單跳鄰機為2號機與5號機,其余為兩跳及以上鄰機。1號機在每輪迭代中僅能與2號機和5號機進行信息交互。不考慮丟包影響下,在第1輪 迭代中,1號機可以獲取2號機及5號機相關信息。在第2輪迭代中,1號機可以間接獲取3、4、6、7號機信息。假設3號機擁有最大標書值,該信息在需要經過算法兩輪迭代傳遞至1號機。若在第1輪迭代中出現丟包致使1號機無法獲取2號機信息,則1號機應采用上述預估方法估計2號機在本輪的標書信息;若1、2號機在第2輪迭代中仍出現丟包現象,則1號機需要估計位于兩跳位置的3、4號機標書值中的最大值。因此,以2號機為根節點,以3、4號機為子節點的樹狀結構構成丟包分支|→2。若在第3、4輪迭代中,1、5號機之間存在數據丟包,則1號機需分別預估丟包分支|→5內的三跳鄰機(8、9號機)與四跳鄰機(10號機)。基于上述設計思路,LE-DTA算法如圖2所示。

圖2 丟包估計分布式任務分配算法偽代碼

LE-DTA算法的具體步驟如下:

步驟1(第1行):參數初始化。J1為算法在第1輪迭代中剩余未分配任務集合。∈為各機預估時間戳。

步驟2(第2～3行):迭代更新。處于Di跳位置的無人機相關信息經過多跳傳播至無人機i后, LE-DTA算法進入新一輪迭代。

步驟4(第6～9行):預估丟包信息。對于每個丟包分支計算所有位于λ跳鄰機的最大標書值并確定對應中標無人機更新該機對應的時間戳其中表示丟包分支內位于λ跳的無人機,tn表示當前時刻。

在實際應用中,LE-DTA算法可以與信息重發機制結合使用,即對于丟包概率較低的情況,采用少量信息重發即可提高信息接收概率;對丟包概率較高的情況,若信息重發后仍導致數據丟包,則采用LE-DTA算法進行估計補償。

3.2 算法收斂性分析

本節分析LE-DTA算法收斂性,提出如下定理:

定理2在同步沖突消解框架下,若收益函數滿足DMG條件且機間保持靜態通信網絡拓撲,則LE-DTA算法能夠確保在機間信息交互存在丟包的情況下收斂,且算法收斂迭代次數上限為Nt。

LE-DTA算法理論上可以適用于任意的丟包概率。特殊地,當機間通信丟包率接近100%時(機間無通信),LE-DTA算法退化至在各機分布式運行SGA算法。

4 仿真分析

本文仿真框架采用ROS Noetic構建,由無人機和通信兩類模塊組成。無人機模塊是獨立進程,分布式任務分配算法在每個無人機模塊中同步執行多次迭代,直至算法滿足收斂條件。各無人機通過通信模塊交換信息,并模擬傳遞的信息是否丟包。仿真實驗的硬件環境是AMD Ryzen 7 3700X, 8-core, 3.59 GHz CPU和16 GB RAM。

在想定Ⅱ中,任務分配問題規模增加至7機與18目標,Ci=18。通信丟包采用1.2節模型模擬,相關參數參考文獻[17]設置為:PL0=40 dBm,d0=30 m,PT=30 dBm,Pbar=5 dBm,μdB=-90 dBm,σdB=7 dBm。除想定Ⅰ中對比的3種算法之外,加入HIPC[5]、PI[6]和DGA[9]等算法參與想定Ⅱ的對比工作,其中HIPC與PI算法的一致性協商階段采用CBBA沖突消解規則[4]實現。對比分析指標包含單機最大通信傳輸量、算法收斂時長與目標函數值(最優性)。由于多種對比算法信息交互內容不一致,設計通信負載指標計算方式如下:

(17)

表1 各算法信息交互內容及包長

參與對比的算法最大迭代次數ζmax設置為1 000次,算法收斂條件設置如下:

{χ(ζ)=χ(ζ-τ),τ=1,2,…,2D}or{ζ≥ζmax}

(18)

式中:χ(ζ)表示算法在第ζ代的分配方案。

4.1 想定Ⅰ

考慮4種網絡拓撲結構:一字型、中心輻射型、環型及全連通型,機間通信單跳距離為900 m,無人機位置如表2所示,其中代數連通度為網絡拓撲對應Laplace矩陣L的次小特征值λ2(L)。

表2 不同拓撲下無人機位置(想定Ⅰ)

從拓撲連通關系上,全連通型拓撲連通度最高,其代數連通度為4,網絡直徑D為1,表明理想通信下各機僅需一輪迭代即可將信息傳播至系統內他機;環型與中心輻射型拓撲代數連通度分別為2和1,低于全連通拓撲;一字型拓撲代數連通度約為0.59,網絡直徑為3,表明理想通信下某機發出的信息最多需要3輪迭代才能傳播至系統內各機。考慮丟包因素,信息傳播所需算法實際迭代次數高于理想通信條件。分別在多種丟包概率下開展蒙特卡洛數值仿真實驗,指標統計均值如圖3、圖4所示。

圖3 通信傳輸量對比結果(想定Ⅰ)

圖4 收斂耗時對比結果(想定Ⅰ)

當丟包率較高(P=0.9或P=0.7)時,RS-CBBA相較于標準CBBA算法具有更快的收斂速度。表明信息重傳機制可以顯著降低信息丟包概率,縮短算法收斂周期。但RS-CBBA通信傳輸量較大,在代數連通度較高的拓撲(環型、全連通型)中,其通信傳輸量顯著高于標準CBBA算法。LE-DTA算法在高丟包率下收斂耗時接近RS-CBBA,且具備更小的通信量。隨著網絡拓撲連通度的降低,LE-DTA算法的性能優勢更為顯著。在一字型拓撲內,當P=0.9 時,LE-DTA算法通信量較CBBA與RS-CBBA分別降低96.9%與89.2%,收斂速度較CBBA與RS-CBBA分別提升97.7%與26.4%。LE-DTA算法在P<0.9情況下收斂耗時略高于RS-CBBA,這是因為LE-DTA需要在局部維護b(n)、和列表以預估他機丟包信息,從而增加了部分計算量。另外,隨丟包概率降低,RS-CBBA和LE-DTA算法在通信量和收斂速度上優勢逐漸減小,這是因為兩者主要圍繞丟包進行改進設計,丟包出現概率越小,兩者越接近標準CBBA算法。

4.2 想定Ⅱ

在想定Ⅱ中,問題規模增加至7機與18個目標,參與對比的分布式任務分配算法增加至6種(CBBA、RS-CBBA、LE-DTA、HIPC、PI與DGA)。無人機位置在([0 m, 3 000 m], [0 m, 3 000 m])的區域內隨機生成。在不同路徑損耗系數α下開展數值仿真實驗,α越大,表明外界干擾越強,機間單跳通信距離越短,相同距離下丟包概率越高。繪制仿真對比箱線圖,如圖5所示。

圖5 算法性能對比結果(想定Ⅱ)

在通信負載方面,當外界干擾較強時,LE-DTA算法具有最小通信傳輸量。當α=4.0時,LE-DTA算法通信傳輸量均值為5.8×104bit,相對于CBBA、RS-CBBA、HIPC、PI、DGA等算法分別降低64.6%、79.9%、51.2%、50.2%、14.9%;當α=5.0時,LE-DTA算法通信傳輸量均值為9.1×104bit,相對于上述對比算法分別降低94.3%、91.3%、74.3%、95.2%、92.4%,表明LE-DTA算法在強干擾環境下能夠節省大量通信資源,且干擾越強,LE-DTA通信負載上的優勢越明顯。統計α=5.0時的通信負載數據標準差,其中LE-DTA為2.0×104bit,相對于上述對比算法分別降低98.4%、96.4%、93.6%、98.8%、98.3%,表明LE-DTA算法在強干擾環境下通信負載的穩定性最優。其余算法統計數據在強干擾環境下出現較大波動的原因在于無人機位置的隨機性,當某兩機距離較遠時機間信息丟包概率高,算法需要經過多輪迭代才能實現機間信息的有效交互。相反,當機間距離近時算法可以快速收斂。RS-CBBA算法通過增加信息重傳次數提升機間信息交互成功率,機間距離的隨機性同樣造成較高的通信傳輸量標準差。而各機運行LE-DTA算法時在局部通過補償可以有效估計丟失的傳輸信息。因此,LE-DTA算法通信負載在強干擾丟包環境中始終維持在較低水平。

在算法時效性方面,RS-CBBA算法具有最短的收斂耗時。當α=4.0時,RS-CBBA算法收斂耗時均值為10.1 s,相較于CBBA、LE-DTA、HIPC、PI、DGA等算法分別降低73.4%、55.5%、82.3%、55.6%、93.3%;當α=5.0時,RS-CBBA算法收斂耗時均值為27.7 s,相較于上述對比算法分別降低89.9%、12.3%、83.1%、91.7%、92.7%。結果表明,隨著外界干擾的增強,RS-CBBA算法時效性優勢顯著。原因在于,RS-CBBA算法旨在利用機間通信資源換取更短的收斂時間。因此,在實際應用中需要在通信資源與算法耗時之間權衡。另外,RS-CBBA算法中信息重傳次數的選取同樣會影響算法性能,合理地選擇重傳次數能夠有效降低冗余的通信負載。LE-DTA算法在α=5.0時收斂耗時均值與RS-CBBA算法接近,耗時標準差3.9 s低于RS-CBBA標準差11.8 s,結合通信負載指標的分析結果,表明LE-DTA算法在強干擾下具有良好的收斂性及穩定性,進一步印證了3.2節算法的收斂特性分析。

在算法最優性方面,各算法目標函數值整體接近,由于仿真實驗的隨機性而存在一定差異。表明針對式(1)的分布式任務分配問題,CBBA、HIPC、PI及DGA算法的求解最優性近似。另外,隨著外界干擾增加,各算法求解最優性并未降低,表明針對靜態分布式任務分配問題,通信丟包因素不影響算法的求解最優性,但較高的通信丟包率會顯著增加算法的耗時及通信量。

注意到,當α=3.0時,LE-DTA與RS-CBBA算法較標準CBBA算法優勢并不明顯。這是因為路徑損耗系數較低,機間形成的網絡拓撲結構連通度較高,可能存在多條路徑將任務信息由系統內某架機傳播至另一架無人機。因此,某兩機間通信發生丟包對整體信息傳播影響不大。仿真結果所呈現的規律與想定I中環型或全連通拓撲類似。在α=5.0時,機間有效通信距離縮短,隨機分布的無人機組成的機間通信網絡拓撲連通度較低,信息傳播通路減少,進而導致丟包對分布式任務分配算法收斂影響放大。此時,LE-DTA與RS-CBBA算法所呈現的性能優勢與想定I中的一字型和中心輻射型拓撲仿真結果類似。

綜上,在通信丟包環境下,信息重傳機制可以有效提升CBBA算法收斂速度,但可能造成通信冗余。而LE-DTA算法通過估計補償丟包信息,在確保算法收斂的前提下可以有效降低機間傳輸通信量。仿真結果表明,該算法在高丟包率及低網絡連通度場景上具有明顯的性能優勢。

5 結論

本文考慮通信丟包對分布式任務分配算法影響,提出了機間信息重傳機制,并分析了重傳機制對CBBA算法收斂速度上的影響。為進一步降低機間通信負載,結合信息補償提出了丟包估計分布式任務分配算法,并證明了該算法能夠理論收斂至與集中式方法SGA相同的分配方案。

選取多種典型分布式任務分配算法參與對比,以通信傳輸量及算法收斂耗時為主要指標開展數值仿真實驗。實驗結果表明:信息重傳機制可以有效提升CBBA在通信丟包環境下的算法收斂速度,但存在通信冗余;LE-DTA算法具備在較短時間內以更少的機間通信量獲得分配方案的能力,且隨著通信丟包概率的增加,機間通信網絡拓撲連通度降低,LE-DTA算法的優勢更為顯著。

當前研究雖然在一定程度上提升了算法收斂效率,但仍難以滿足實時的在線應用。后續研究將重點圍繞動態場景設計分布式任務分配算法,確保在通信丟包環境下算法具備秒級及亞秒級解算能力。