考慮韌性的無人機集群自組織區域覆蓋方法

劉 濤, 王沙沙, 張 馳, 白光晗, 陶俊勇

(國防科技大學智能科學學院, 湖南 長沙 410073)

0 引 言

無人機具有體積小、重量輕、隱蔽性強、造價低廉、起降條件簡單等特點,其環境適應性強、生存能力較強,更適合較危險或重復性的工作。而隨著無人機自主化和網絡化通信技術的發展,無人機的運用模式也在不斷發展,單架無人機由于受到探測能力、武器載荷等因素限制,難以完成復雜的任務。無人機集群,類似于蜂群和蟻群,由具備一定自主能力的無人機組成,集群通過無人機之間的實時數據共享、多機組網、協同配合,從而實現整體任務的達成。其中,通信網絡覆蓋是無人機集群的一個典型應用場景,例如災后利用無人機集群建立應急通信網絡[1],戰場提供區域戰地通信[2]等。因此,在任務過程中能否保證良好的通信覆蓋率,對任務的成敗起關鍵作用,無人機集群的通信覆蓋問題也成為一個研究熱點[3-5]。

針對固定翼無人機,其覆蓋主要是指規劃無人機的飛行路徑,實現掃描式覆蓋[6]。而旋翼式無人機能夠保持位置不變進行持續覆蓋,因此本文關注旋翼無人機集群的覆蓋問題,該問題也被稱為無人機編隊的部署問題[7]。文獻[1]針對災后通信基站失去功能的情況,利用遺傳算法對無人機集群進行部署設計,利用無人機充當臨時通信基站,以滿足災區的通信覆蓋要求。該算法屬于集中控制,即在獲取全局信息后集中計算所有無人機的位置。隨著集群規模的增加,集中控制面臨著全局信息獲取難、計算復雜等問題。分布式解決方案成為一個研究熱點,其中基于虛擬力的節點分布式覆蓋算法吸引了諸多研究者。文獻[8]提出了一種虛擬力算法來提高傳感器初始隨機放置后的覆蓋率。但該文章在力的權重系數上沒有給出明確設計,僅假設排斥力權重系數應遠遠大于吸引力權重系數,這使得在不同實驗條件下需多次嘗試以找到合適的權重系數。文獻[9]引入了Sink與Target之間的“引力線”概念,提出了一種基于虛擬力的移動節點精確部署算法,更加關注目標與目標直接的通信中繼,而非區域覆蓋,并且沒有給出虛擬力增益系數的確定方法。文獻[10]在文獻[8]的基礎上假設邊界排斥力和傳感器間的排斥力的權重系數相同,對虛擬力權重系數進行了具體設計,該算法雖然沒有考慮傳感器之間的通信范圍,但仍然可看作是各節點的分布式計算。文獻[11]在半聚集算法[12]的基礎上,提出了一種基于虛擬力場,并且按需部署的無人機自組網算法,該算法同樣未明確給出各虛擬力權重系數的確定方法。除了基于虛擬力的分布式算法,文獻[13]考慮了無人機的感知范圍,提出一種基于相對距離的無人機集群部署算法,但在該研究中,無人機個體除了需要感知范圍內其他無人機的位置信息,還需要實時獲取未被覆蓋區域的位置信息。針對目標區域內有重點關注目標的情況,文獻[14]對布谷鳥算法進行了改進,提出了一種在節點數量較少情況下對監測價值較高區域的重點覆蓋優化的無人機網絡覆蓋優化算法,該算法本身雖然借鑒了分布式理念,但其計算仍需要掌握全局信息。

無人機集群在執行覆蓋任務時,部分無人機可能會出現自身故障、環境擾動、蓄意毀傷等失效情況,導致覆蓋范圍下降,影響任務完成。文獻[10]針對無線傳感器節點故障情況提出了自組織補位算法,該算法要在毀傷故障點附近尋找合適節點集進行“補位”,但該選擇過程被證明是非確定性多項式(non-deterministic polynomial, NP)難問題,且需要集中決策。此外,文獻[10]未考慮恢復過程對覆蓋任務的影響。韌性(也譯為彈性)最早在生物學領域提出[15],隨后在諸如經濟[16-17]、社會[18-19]、工業[20]、軍事[21-22]等多個領域應用。韌性是可靠性的拓展和延伸,是衡量系統對抗擾動并從中恢復的能力,能夠反映系統毀傷及恢復的全過程,對系統設計、優化、崩潰或狀態躍遷預測等都有重要的指導意義[23-26]。目前,對無人機集群的韌性研究逐漸受到關注[27-28],但集群覆蓋問題的研究鮮有涉及無人機發生失效并開展恢復的情況。因此,有必要將韌性因素納入無人機集群通信覆蓋問題的研究。

在諸多覆蓋算法中,文獻[1]為需要全局信息的集中控制算法,文獻[8-10,11,13-14]均可視作分布式控制算法,其中除文獻[14]以外均是基于虛擬力的方法。但上述方法鮮有綜合考慮以下幾個問題:① 僅依賴于局部信息的完全分布式方法;② 明確給出虛擬力權重的確定方法;③ 考慮任務中無人機個體失效的情況。因此,在現有研究的基礎上,本文旨在充分發揮無人機集群自組織、自恢復的能力,進一步考慮個體失效的情況,提出一種分布式自組織覆蓋方法。本方法引入邊界排斥力、重點區域吸引力、無人機排斥力3種虛擬力并給出其權重因子的確定方法,使無人機在感知周圍信息的情況下自組織地完成區域覆蓋,并適用于包含重點覆蓋區域的情況。此外,通過引入基于韌性的覆蓋關鍵閾值調節機制,使無人機集群在個體失效后能夠快速完成重構和補位。

1 無人機集群自組織覆蓋算法

1.1 基本假設

為對無人機集群覆蓋問題進行簡化,本文基于以下假設:

(1) 所有無人機均可看作具有恒定飛行高度的節點,其覆蓋范圍為Rc(見圖1)。

(2) 所有無人機節點可通過定位系統獲取本身位置信息。

(3) 每個無人機節點具有半徑為Rs感知能力,可以獲取感知范圍內友軍的位置(見圖1)。

(4) 待覆蓋目標區域為二維平面。

(5) 所有無人機節點提前獲知覆蓋區域邊界及重點區域位置信息。

圖1 無人機覆蓋示意圖Fig.1 Schematic diagram of unmanned aerial vehicle coverage

1.2 監視覆蓋區域劃分

如圖1所示,在實際的覆蓋任務中,往往存在著需要重點關注的覆蓋區域,針對這樣的區域,對其覆蓋更應保持連續性,并盡量減少覆蓋盲區。因此當用傳統的覆蓋率表征無人機任務能力時,需進一步考慮重點區域與普通區域的差別。

假設需覆蓋的區域面積為ST,無人機已實現覆蓋的重點區域面積為Sa,已覆蓋的普通區域為Sb,則無人機集群的覆蓋率C計算如下:

(1)

式中:μ為重點區域的權重系數;φ為重點區域在全部需覆蓋區域(普通加重點)內所占比例。因此,覆蓋率C可以表征無人機集群在考慮重點區域下所達到的覆蓋范圍。

1.3 虛擬力設計

虛擬力的概念源于勢場和圓盤堆積理論的結合,前人的研究多將虛擬力設為3種,即節點之間的吸引和排斥力,以及區域邊界對節點的排斥力[8-9]。本文重點考慮目標區域存在重點覆蓋區域的情況,因此將無人機集群中的個體在運動過程中受到的虛擬力分為3種:無人機之間的排斥力;無人機與邊界之間的排斥力;無人機與重點覆蓋范圍中心的吸引力。

1.3.1 無人機之間的排斥力

假設無人機UAVi在t時刻的坐標為(xi(t),yi(t)),感知范圍為Rs,在其感知范圍內存在友軍無人機Γ={s1,s2,…,sκ},其中κ為感知范圍內無人機的數量。任意友軍j∈Γ,t時刻的坐標為(xj(t),yj(t)),可獲取兩無人機之間的距離為

(2)

假設存在一個覆蓋關鍵閾值dth=γ·2Rc,其中0≤γ≤1為關鍵閾值權重,若dij≥dth,則UAVj和UAVi之間沒有作用力發生。若dij

(3)

式中:θji為力的方向,計算如下所示:

(4)

ωu為無人機之間排斥力系數。綜上所述,UAVi所受的合力為

(5)

圖2 無人機節點間的排斥力Fig.2 Repulsive force among unmanned aerial vehicles

1.3.2 無人機與邊界之間的排斥力

(6)

式中:ωb為無人機所受邊界產生排斥力系數。UAVi所受的邊界合力如下所示:

(7)

圖3 無人機受外力分析Fig.3 Analysis of external force on unmanned aerial vehicles

1.3.3 無人機與重點覆蓋區域中心的作用力

當目標區域中存在重點區域時,引入了另一虛擬力,即重點區域中心對無人機集群的吸引力。在執行任務過程中,無人機集群在目標區域內應主動向重點覆蓋區域靠近,特別是現有集群數量不能完全覆蓋全部區域時。如圖3所示,假設重點覆蓋區域的中心坐標為(xD,yD),則該區域對無人機的吸引力為

(8)

(9)

式中:ωd為重點區域吸引力因子;θid為無人機指向中心坐標為(xD,yD)向量與x軸的夾角。

1.3.4 虛擬力因子的確定

無人機所受虛擬力的各權重系數,ωu,ωb和ωd決定了無人機最終所受合力的大小以及方向。因為邊界產生的排斥力是對稱存在的,且對于所有無人機個體來說均是朝向監控區域中心的,故邊界的排斥力并未對無人機之間的相對距離產生影響。因此,無人機集群的覆蓋范圍主要受無人機之間的作用力以及重點區域中心吸引力的影響。在前人的研究中,假設節點的排斥力遠大于吸引力[8],即ωu?ωd。但實際實驗中發現,僅憑上述條件難以對權重系數進行確定。文獻[10]明確了相關系數,一方面其計算是基于全局所有節點信息,不適用于本文所涉及的分布式算法,另一方面其權重確定過程并未考慮邊界排斥力產生的影響。因此,本文根據覆蓋任務要求與無人機配置,提出虛擬力因子的量化確定方法。

圖4 無人機位置極端情況1Fig.4 Extreme situation 1 of unmanned aerial vehicle location

UAVi與重點區域中心(xD,yD)之間的吸引力大小為

此外,UAVi所受邊界排斥力為

(10)

當把無人機集群看作一個整體時,無人機之間的排斥力是集群的內力,無人機集群整體位置則由無人機所受外力決定,即邊界產生的排斥力和關鍵區域的吸引力。邊界產生的斥力使無人機集群朝覆蓋范圍中心(xU+xL)/2,(yU+yL)/2運動,同時關鍵區域的吸引力使集群朝(xD,yD)運動?？紤]如圖5所示的極端情況,UAVi與重點區域中心(xD,yD)均處于整個覆蓋范圍的邊緣,無人機所受兩個力方向相反。

圖5 無人機位置極端情況2Fig.5 Extreme situation 2 of unmanned aerial vehicle location

(11)

將式(11)代入式(10),有:

(12)

(13)

將式(13)代入式(12),并且Dd?Δ,可得

(14)

因此可設:

(15)

ωb=(Dc+0.5Dd)3

(16)

將式(16)代入式(11)可得

(17)

故可得各虛擬力的權重系數設計如表1所示。

表1 各虛擬力的權重系數設計Table 1 Weight coefficient of each virtual force

1.3.5 虛無人機位置更新

(18)

假設UAVi當前t時刻的位置坐標為(xi(t),yi(t)),無人機的飛行速度為vi,則可更新下一個時刻(t+1)時無人機的位置:

(19)

式中:合力方向與x軸的夾角為θi。

1.4 覆蓋算法

基于所提出的虛擬力,無人機個體在群體中的運動則由感知范圍內其他個體、覆蓋區域邊界以及重點區域中心所共同決定。每個無人機個體依據這些信息不斷調整位置以最終達到覆蓋效果。值得注意的是,本自組織算法是分布式,即無人機只需進行有限的通訊和獲取少量的信息以完成自身的協同運動,針對每個無人機個體,具體算法流程如圖6所示。

步驟 1初始化任務基本參數,包括覆蓋區域坐標(xU,xL,yU,yL)、重點區域中心坐標(xD,yD)、感知半徑Rs、覆蓋半徑Rc及飛行速度為vi。

步驟 2判斷無人機是否進入覆蓋區域,若已進入跳至步驟3,若未進入令ωb=0并跳至步驟3。

步驟 3根據式(5)、式(7)和式(8)計算無人機所受合力Fi。若合力Fi>0,則進行步驟4,否則跳至步驟6。

步驟 4根據式(19)計算無人機下一時刻位置坐標,若該坐標在覆蓋區域邊界內,則按此坐標更新無人機坐標,并跳至步驟6,否則進入步驟5。

步驟 5以(xD,yD)為運動目標確定運動方向θi,根據式(14)更新無人機下一時刻位置坐標,進入步驟6。

步驟 6判斷當前是否停止覆蓋任務,若任務繼續進行則跳至步驟3再次對無人機的位置進行更新。

圖6 無人機個體自組織算法流程圖Fig.6 Flow chart of unmanned aerial vehicle self- organization algorithm

2 基于韌性的無人機集群覆蓋

2.1 集群韌性指標

無人機集群在執行覆蓋任務時,其韌性可以定義為集群遭到擾動(例如個體故障、外界毀傷等)時,能夠快速恢復任務區域的覆蓋率,保障覆蓋任務順利執行的能力。韌性作為集群系統一種能力的表征,需要對其進行度量?，F有韌性度量方法已有很多研究[25,29-31],而無人機集群覆蓋具有明顯的任務特性,例如,任務要求在規定時間內保障區域覆蓋率達到一定程度。因此本文利用文獻[25]中面向任務的系統韌性指標對無人機集群覆蓋能力的韌性進行評估。其計算指標如下所示:

R(T)=βR0(T)+(1-β)R1(T)

(20)

式中:R(T)為T時刻系統的綜合韌性,參數0≤β≤1,為韌性側重因子。R0(T)為系統任務時間韌性,R1(T)為系統任務性能韌性,其計算公式如下:

(21)

2.2 集群的自組織恢復行為

集群的自組織行為機制使得個體能夠根據所感知的周邊情況對自身行為做出相應改變,而正是這樣的機制使得無人機具有自重構、自恢復能力。以所提自組織覆蓋算法為例,當個體感知周邊無人機距離小于覆蓋關鍵閾值dth時,排斥力的作用會使得個體相互原理以保障合適的覆蓋重疊。當個體感知周邊無人機距離大于dth時,雖然個體之間并沒有作用力產生,但重點區域的吸引力會使個體朝重點區域靠近,在此過程中,個體之間的距離會隨之減小并接近dth。

當無人機集群由隨機分布狀態到自組織完成區域覆蓋后,無人機個體仍然基于此自組織算法實時根據感知范圍內局部信息進行調整。如圖7所示,在任務初始階段,無人機在吸引力、排斥力的作用下,自發地朝覆蓋區域各處運動,并最終保持相對穩定的覆蓋效果。當無人機個體遭遇自身故障或外界擾動導致失去功能時,其覆蓋范圍內會出現“空洞”,此時集群的覆蓋率會降低。隨后無人機個體基于自組織行為規則,逐步將“空洞”補位填充,特別是將重點區域內的空缺進行填補,因此整個集群的覆蓋率得到提高,從而體現了無人機集群在自組織覆蓋算法下的韌性。

圖7 集群自組織恢復過程Fig.7 Self-organizing recovery process of swarm

2.3 考慮失效的集群覆蓋算法

由第2.2節可知,無人機集群通過本文提出的覆蓋算法可實現毀傷下的自組織恢復,但反映韌性高低的一個重要方面是系統恢復的快慢程度。能否快速對毀傷無人機造成的空缺,特別是重點區域內的空缺進行填補,將直接影響集群韌性的高低。

圖8 覆蓋關鍵閾值調節過程圖Fig.8 Coverage critical threshold adjustment process

將上述覆蓋關鍵閾值調節機制與所提自組織覆蓋算法相結合即可得到基于韌性的無人機集群覆蓋算法,其流程如圖9所示。在個體無人機每次執行自組織覆蓋算法位置更新之前,無人機個體判斷集群是否遭遇毀傷,若發生毀傷,則通過覆蓋關鍵閾值調節機制對dth的大小進行調整,以進一步改變自組織覆蓋算法位置更新結果。最終使無人機在遭到毀傷時,盡快完成重點區域內的空洞補缺,隨后再避免無人機過度緊湊,擴大外圍覆蓋范圍。

圖9 韌性自組織覆蓋算法流程Fig.9 Flow chart of resilient self-organizing coverage algorithm

3 仿真實驗分析

在完成無人機集群自組織覆蓋算法及韌性策略之后,為驗證算法有效性,分別開展了重點區域覆蓋、集群數量與關鍵閾值靈敏度以及集群韌性3個方面的仿真實驗,所有實驗采用多智能體仿真技術,并基于Anylogic平臺開展。

3.1 重點區域覆蓋

第1類實驗是驗證算法是否能正確引導無人機集群進行重點區域覆蓋。將重點覆蓋區域中心設置在整個目標區域的不同位置,整體目標區域范圍為1 200 m×1 200 m,無人機個數為25個,覆蓋半徑Rc=80 m,感知半徑Rs=400 m,結果如圖10所示。由圖10可以看出,無論重點覆蓋區域的中心位于整個目標區域的哪個位置,本文所提出的算法都可以較好地引導無人機集群在數量較少無法對整體目標區域覆蓋的情況下完成對重點區域的覆蓋。

圖10 不同重點區域中心無人機集群覆蓋情況Fig.10 Coverage of unmanned aerial vehicle swarm in different key areas

3.2 集群數量與關鍵閾值靈敏度

圖11 n=20時集群覆蓋情況Fig.11 Swarm coverage with n=20

圖12 n=30時集群覆蓋情況Fig.12 Swarm coverage with n=30

圖13 n=40時集群覆蓋情況Fig.13 Swarm coverage with n=40

圖14 n=50時集群覆蓋情況Fig.14 Swarm coverage with n=50

圖15 無人機數量和不同關鍵閾值覆蓋率大小Fig.15 Number of unmanned aerial vehicles and different critical threshold coverage sizes

3.3 考慮個體失效的集群韌性評估對比

當集群數量分別為20,30,40,50時,各進行20次實驗,并在任務結束時,根據第2.1節中的韌性指標計算集群韌性,其中將各時刻下覆蓋率作為系統的性能指標Q(t),實驗參數如表2所示。實驗結果如圖16所示,無論集群規模如何,所提算法的平均韌性均要高于方式N,并且方式P的穩定性更強,即多次實驗下,集群的韌性偏差不明顯,而方式N的恢復效果具有較強的隨機性。當無人機數量較少時,本身覆蓋率已經不高,而且由于個數數量較少,個體之間的虛擬力相對也較少,所以遭到毀傷后,兩種方式的恢復差距不大。與之相對應的,當無人機數量增多時,無人機之間的作用力也隨之增加,此時所提算法能幫助集群更加快速、穩定的恢復。

表2 實驗參數表Table 2 Parameters in experiments

圖16 不同集群規模下兩種模式的韌性Fig.16 Resilience of two modes in different swarm scales

當無人機集群數量為40,兩種模式下單次實驗覆蓋率隨時間變化的過程如圖17所示。當毀傷發生后,兩種模式均開始恢復,并最終能恢復到相類似的覆蓋率。但在恢復過程中,韌性策略模式能夠更快速補充重點區域產生的空缺,使覆蓋率能夠快速回升。而過度收縮同樣會減小覆蓋率。因此,在聚集一段時間后再次恢復覆蓋關鍵閾值(時刻130),使集群以更合適的間距進行覆蓋。因此變閾值模式下集群的韌性達到0.881,而常規模式下系統韌性只有0.71。

圖17 n=40時兩種模式下單次實驗覆蓋率隨時間變化過程Fig.17 Variation process of single test coverage over time in two modes with n=40

3.4 毀傷規模與無人機集群韌性

參考第3.3節集群覆蓋仿真實驗參數,以無人機集群數量n=40為例,考慮無人機集群遭遇毀傷時,失效無人機規模不同對集群執行覆蓋任務得影響。由無人機失效規模為2架為起始,逐漸增加失效個數,直至最大失效個數為10架。每種失效規模各開展20次仿真實驗,記錄其韌性的均值。

實驗結果如圖18所示,隨著失效規模的增加,兩種恢復策略下的韌性值均會下降,但本文所提算法(方式P)的韌性均優于方式N。此外,在方式P下,毀傷規模達到7時韌性會顯著下降,而在方式N下,毀傷規模達到6即發生顯著韌性下降。韌性的顯著下降代表著實驗中,存在多次集群恢復后未達到任務要求覆蓋率。當毀傷規模大于等于9架時,兩恢復模式均處于低位,且基本不變。這是由于剩余無人機的數量無論怎樣分布,均已無法達到任務要求。

圖18 n=40時無人機韌性隨毀傷程度變化Fig.18 Resilience of unmanned aerial vehicles varies with degree of damage with n=40

4 結束語

本文針對空域目標區域覆蓋中存在重點區域的場景,提出了一種基于虛擬力的無人機集群自組織空域覆蓋算法。無人機個體通過感知周圍個體的位置,調節自身的運動以達到目標區域覆蓋,特別是重點區域的偏向覆蓋效果。通過分析集群的自組織行為,設計了一種覆蓋關鍵閾值調節機制,以提高集群在執行覆蓋任務過程中遭遇毀傷后的恢復能力。仿真實驗以面向任務的韌性指標度量無人機集群的恢復能力,實驗結論表明所提出的算法相比一般自組織覆蓋算法具有更強的韌性。后續將進一步考慮關鍵閾值變更大小、恢復時間以及集群毀傷比例之間的關系,研究其最優化參數確定方法。