谷曉燕， 陳 亮， 鄧香平

(北京信息科技大學，北京 100000)

0 引言

無人機(Unmanned Aerial Vehicle，UAV)集群因其低成本和靈活可靠的運動方式，在軍用和民用領域得到了多方面的關注，如目標攻擊、應急救援、物流運輸、精準農(nóng)業(yè)等[1-4]。然而，無人機集群在協(xié)同執(zhí)行任務中存在著通信代價高、編隊續(xù)航能力不足等問題，影響無人機編隊的魯棒性。設計均衡多個目標的無人機編隊信息交互拓撲優(yōu)化方法，對于提升無人機編隊通信代價滿意度、規(guī)避脆弱性，以及提高任務執(zhí)行的保障度方面均具有重要意義。

無人機編隊信息交互拓撲中構成的通信鏈路存在著多種通信代價[5]。在通信鏈長方面，WANG等[6]考慮了無人機通信鏈路出現(xiàn)故障時的拓撲構建，但是通信代價僅考慮了距離；董文奇等[7]面向領航-跟隨者無人機編隊考慮了位置誤差對于拓撲和算法的影響；在網(wǎng)絡延遲方面，CHEN等[8]基于圖論探索拓撲的性質(zhì)考慮了在多條通信鏈路遭到破壞時，快速搜索構建新拓撲的方案，但新生成的拓撲沒有考慮端到端的跳數(shù)，存在較高的延遲；LEBLANC等[9]引入離散時間分布式設計框架解決了由延遲和數(shù)據(jù)丟失引起的拓撲不穩(wěn)定性問題；ATEYA等[10]考慮了通信信道上的流量負載和每個無人機節(jié)點上的負載，從編隊穩(wěn)定性的視角引入了能量約束，但沒有與其他通信代價緊密聯(lián)系。國內(nèi)外學者在研究通信鏈長、網(wǎng)絡延遲影響因素、能量均衡及其他不確定因素[11-12]方面均做出了有益的貢獻，但缺乏對影響無人機信息交互拓撲多種因素的綜合優(yōu)化考慮。僅考慮鏈長或編隊整體平均延遲的單一目標，生成的拓撲可能不滿足領航者到末端跟隨者無人機的端到端低延遲要求，進而造成延遲大，存在無人機碰撞的風險。同時，由于編隊中跟隨者無人機扮演角色的不同，能量消耗的速度有所差異。如果沒有考慮集群對能量的分配利用，容易造成能量分配不均，導致編隊中部分無人機能量提前用盡，飛行途中被迫多次變換拓撲的問題，降低了無人機集群的穩(wěn)定性。

由于在無人機編隊控制方法中領航-跟隨者法應用廣泛，故本文研究其編隊信息交互拓撲優(yōu)化方法。建立考慮編隊通信鏈長、網(wǎng)絡延遲影響因素和剩余能量不均衡度的多目標優(yōu)化模型，依據(jù)領航-跟隨者無人機編隊分級的結構特點對人工蜂群算法進行改進，以加快搜索更優(yōu)的信息交互拓撲。

1 無人機編隊拓撲影響因素

1.1 編隊通信鏈長

無人機集群在飛行過程中通過無線信道建立通信，通信鏈路越短，通信所消耗的能量越少，能夠執(zhí)行的任務就會越多[13-14]。將編隊通信鏈長納入信息交互拓撲優(yōu)化所考慮的因素，能夠降低無人機編隊任務執(zhí)行時的通信代價。

1.2 網(wǎng)絡延遲影響因素

只考慮整個編隊的通信總鏈長最小化，領航者無人機到部分跟隨者無人機的通信鏈長仍有可能較大，從而導致部分通信鏈路的延遲較高，進而導致無人機因為接收信息的滯后發(fā)生脫離編隊甚至碰撞的嚴重后果。這是因為總鏈長的最小化并沒有考慮單條通信鏈路最短，有可能造成部分通信鏈路經(jīng)由過多中繼節(jié)點導致通信延遲的增大。

本文定義最大延遲為信息交互拓撲中從領航者發(fā)送信息到其他跟隨者無人機接收信息的延遲中最大數(shù)值，用領航者無人機到末端跟隨者無人機的最大通信跳數(shù)簡化表示。同時，基于復雜網(wǎng)絡中的度中心性的概念，將無人機與其他無人機建立通信鏈接的總和定義為該無人機的度中心性的測度，在拓撲生成中，通過約束編隊中無人機的度中心性來控制通信網(wǎng)絡中由于鏈接過多導致通信傳輸排隊從而增大擁塞延遲的情況。

1.3 剩余能量不均衡度

無人機編隊中每架無人機作用不相同，能量消耗速度也不同，不考慮能量消耗情況生成拓撲，可能會造成部分剩余能量少的無人機提前耗盡能量，影響編隊任務的執(zhí)行。在拓撲變換中，讓剩余能量多的無人機承擔更多的信息中繼功能，將有利于無人機編隊的能量消耗保持相對均衡，從而提高編隊整體的續(xù)航能力。

因此，本文抽象出鏈接剩余能量的概念，把建立拓撲鏈接的兩架無人機的剩余能量均值定義為相鄰兩架無人機鏈接剩余能量?？紤]生成的拓撲中所有鏈接剩余能量的平均值及其標準差，基于統(tǒng)計中變異系數(shù)的思想，用鏈接剩余能量的標準差除以鏈接剩余能量的平均值，構建剩余能量不均衡度指標。剩余能量不均衡度取值越小，說明無人機編隊信息交互拓撲中無人機能量分配越均衡。

2 多目標優(yōu)化模型構建

2.1 變量定義

本文用賦權有向圖G=(V,L,D)抽象表示無人機編隊通信網(wǎng)絡拓撲，設置如下變量：

1)n為編隊中無人機的數(shù)量；

2)i，j為編隊中無人機的標號，i,j∈{1,2,…,n},i≠j；

3)V為有向圖中節(jié)點的集合，每一個節(jié)點代表編隊中的一架無人機，V={Ui}，Ui代表第i架無人機；

4)L為有向圖中弧的集合，每一條弧代表編隊中兩架無人機的鏈接，L={li j}，li j代表無人機Ui和Uj之間的通信鏈接；

5)D為有向圖中所有弧的權值的集合，di j為通信鏈接li j的鏈長，表示編隊中任意兩架無人機Ui和Uj之間通信鏈接的長度，生成的無人機編隊信息交互拓撲通信總鏈長用w表示，即

(1)

6)X為是否生成通信鏈接決策變量的集合，X={xi j}，xi j表示無人機編隊信息交互拓撲生成的決策變量，即

(2)

7)E為編隊中無人機剩余能量值的集合，E={ei j}，ei表示無人機Ui的剩余能量，ej表示無人機Uj的剩余能量，ei j表示兩架無人機Ui與Uj的平均剩余能量，即

(3)

8)v為無人機編隊剩余能量不均衡度

(4)

(5)

9)H為有向圖中領航者無人機節(jié)點到末端跟隨者無人機節(jié)點的跳數(shù)集合，H={hk}，k為生成的無人機編隊信息交互拓撲中領航者無人機到末端跟隨者無人機的路徑條數(shù)，hk為信息交互拓撲中第k條路徑；h表示k條路徑中的最大通信跳數(shù)；

10)ci為節(jié)點i的度中心性，即

(6)

表示在無人機編隊信息交互拓撲中，無人機Ui與其他n-1架無人機直接發(fā)生通信鏈接的總數(shù);

11)Cd為度中心性的閾值，表示編隊信息交互拓撲中，任一節(jié)點與其他節(jié)點直接相連的最大數(shù)量限制。

2.2 多目標優(yōu)化模型

1) 目標函數(shù)。

編隊通信總鏈長最小目標(f1)表示為

(7)

剩余能量不均衡度最小目標(f2)表示為

(8)

最大網(wǎng)絡延遲影響因素，領航者無人機到末端跟隨者無人機的最大通信跳數(shù)最小目標(f3)表示為

(9)

多目標優(yōu)化函數(shù)可抽象為

(10)

2) 目標滿意度隸屬度函數(shù)。

本文借助隸屬度函數(shù)的思想統(tǒng)一量綱，把各個目標轉化為無量綱的滿意度，從而將多目標問題轉化為對多個目標的滿意度問題，通過滿意度的偏差最小化進行信息交互拓撲優(yōu)化。

針對編隊通信鏈長最小目標f1，構造目標滿意度的隸屬度函數(shù)s1。設下限a1為用Prim或Kruskal算法求出的最小生成樹弧的權值和，即計算的最小通信總鏈長，上限b1為初始編隊通信鏈長。編隊通信鏈長滿意度的隸屬度函數(shù)s1(x)表示為

(11)

式中，w(x)表示生成的無人機編隊信息交互拓撲的通信總鏈長，x為拓撲優(yōu)化的決策變量。

針對剩余能量不均衡度最小目標f2，構造目標滿意度的隸屬度函數(shù)s2。設下限a2為0，此狀態(tài)下無人機編隊剩余能量不均衡度達到最小，上限b2為初始編隊剩余能量不均衡度。編隊剩余能量不均衡度的隸屬度函數(shù)s2(x)表示為

(12)

式中，v(x)表示生成的無人機編隊信息交互拓撲的剩余能量不均衡度。

針對最大通信跳數(shù)最小目標f3，構造目標滿意度的隸屬度函數(shù)s3。領航者到末端跟隨者無人機的最小跳數(shù)為1，即領航者與所有跟隨者無人機都直接生成通信鏈接，這種狀態(tài)下無人機編隊通信鏈路最大跳數(shù)最小，因此設下限a3為1。上限b3為初始編隊領航者無人機到末端跟隨者無人機的最大跳數(shù)。編隊最大跳數(shù)最小化目標滿意度的隸屬度函數(shù)s3(x)表示為

(13)

式中，h(x)表示生成的無人機編隊信息交互拓撲最大跳數(shù)的最小值。

(14)

3) 約束條件。

為了避免通信傳輸排隊擁塞，任意無人機Ui的度中心性ci不能大于閾值Cd，即

(15)

無人機與其他無人機建立通信鏈路的總和作為度中心性的測度，通過設置度中心性約束條件來控制通信網(wǎng)絡中數(shù)據(jù)傳輸?shù)呐抨爭淼难舆t。

另外，由于編隊中任意兩架無人機Ui和Uj之間最多只存在1條單向的通信鏈路，不構成環(huán)路，無人機編隊信息交互拓撲為1棵有向生成樹。樹中弧的數(shù)量為n-1，即鏈接的數(shù)量恰好為n-1

(16)

3 改進的人工蜂群算法

人工蜂群(Artificial Bee Colony，ABC)算法是一種群智能優(yōu)化算法，具有算法控制參數(shù)少、魯棒性強，能夠調(diào)節(jié)局部搜索和全局搜索的比例，且不易陷入局部最優(yōu)的特點[15]。領航-跟隨者法是將編隊中的某一架無人機作為領航者，其他無人機作為跟隨者，無人機編隊信息交互拓撲可以抽象為在滿足特定目標和約束條件下通信網(wǎng)絡拓撲的一個子集。對于由n架無人機組成的編隊，解為n-1維向量，而且由于決策變量取值為0或1，解也具有多維離散的性質(zhì)。本文設計離散人工蜂群算法，以適應無人機編隊信息交互拓撲優(yōu)化問題的求解，提高算法的效率。

領航-跟隨者無人機編隊的信息交互拓撲可以用1棵生成樹來表示，存在多條支鏈，具有分級的特點。鄰接矩陣用來表示一個信息交互拓撲。通過判斷連通圖算法，生成m棵用鄰接矩陣表示的生成樹，并存儲為外部文檔T，T={T1,T2,…,Tm}。設置R只引領蜂，R≤m，并從外部文檔中挑選與引領蜂數(shù)量相同的生成樹作為初始蜜源。一個蜜源代表一種無人機編隊拓撲，蜜源被采集的最大次數(shù)設為l，最大迭代次數(shù)設為Q。采用自然數(shù)編碼的方式來表示編隊的結構，并采用基于生成樹的逆轉搜索(TOS)算子。TOS算子是在已有生成樹的基礎上，在距離根節(jié)點不同跳數(shù)的鏈路中，結合逆轉算子，變換子節(jié)點位置，從而構成新的生成樹。引領蜂在蜜源的附近通過TOS算子生成一個候選蜜源，跟隨蜂依據(jù)蜜源的適應度來選擇更好的蜜源進行進一步的搜索，適應度函數(shù)表示為

(17)

式中，fr表示第r個蜜源的適應度值，即第r個可行解的質(zhì)量,r=1,2，…,R。

當引領蜂和跟隨蜂搜索一定次數(shù)后，如果沒有搜索出更好的蜜源，則會轉化為偵察蜂，隨機從外部文檔中挑選生成樹產(chǎn)生一個新解，并進行無人機編隊拓撲滿意度偏差值的計算。在進行局部搜索時，依據(jù)當前較好的拓撲變換出質(zhì)量更好的拓撲，快速找到滿意度偏差更小的拓撲，并經(jīng)過進一步迭代計算得到最優(yōu)解。

算法流程如圖1所示。

圖1 改進人工蜂群算法流程圖Fig.1 Flow chart of the improved artificial bee colony algorithm

4 算例分析

4.1 數(shù)據(jù)來源及算法設置

引用文獻[5]中的16架無人機的隊形、距離設置方法，將2架無人機的左右間距設為600 m，前后間距設為500 m，以0～1的數(shù)值表示各無人機的剩余能量。為了探尋本文提出的多目標優(yōu)化模型效果，將人工蜂群算法的蜂群種群大小設置為100，雇傭蜂和非雇傭蜂的比例均為50%，度中心性約束設為3，各目標之間的權重假設相同。

只考慮鏈長，基于最小生成樹求解的信息交互拓撲如圖2所示。

圖2 最小生成樹算法求解信息交互拓撲圖Fig.2 Information interaction topology map solved by minimum spanning tree algorithm

考慮多目標，基于改進人工蜂群算法求解的信息交互拓撲如圖3所示。無人機之間連線上的數(shù)據(jù)表示無人機之間的通信鏈長，括號內(nèi)第1位數(shù)字表示無人機標號，其中設U1為領航者無人機，設U2～U16為跟隨者無人機,第2位數(shù)字表示無人機的剩余能量。本文提出的算法求解的信息交互拓撲與基于最小生成樹算法求解的信息交互拓撲相比，最大網(wǎng)絡延遲影響因素減少33.3%，剩余能量不均衡度減小12.4%，而編隊鏈長僅增加13.6%。

圖3 改進人工蜂群算法求解信息交互拓撲圖Fig.3 Information interaction topology map solved by improved artificial bee colony algorithm

4.2 不同度中心性約束的對比

為對比分析不同度中心性限制對各目標偏差值的影響，使用相同數(shù)據(jù)源，度中心性分別設為3和4，隨機運行10次，每次迭代次數(shù)設為500，計算不同度中心性約束下的結果如圖4所示。

圖4 不同度中心性偏差對比圖Fig.4 Comparison chart of degree centrality deviations

偏差值越小,說明算法運算的結果越好，從圖4可以看出，以度中心性為4作為約束計算的總偏差要小于以度中心性為3作為約束計算的結果，說明在無人機編隊中，無人機的通信能力越強，生成的信息交互拓撲多目標綜合評價越好，符合實際的情況。從單個因素來看，各因素求解的結果有跳躍的情況，但從整體上來看，求解結果穩(wěn)定，說明本文提出的算法能夠均衡多個維度的影響因素，是從整體上進行的優(yōu)化。統(tǒng)計10次運行結果的平均值，在度中心性為4的情況下，相比最小生成樹算法求解的信息交互拓撲，本文提出的模型求解結果，在編隊總鏈長僅增加16.7%時，最大網(wǎng)絡延遲影響因素能夠減少45%，剩余能量不均衡度還能夠減小7.3%。

5 結論

本文綜合考慮了通信鏈長、網(wǎng)絡延遲影響因素、剩余能量不均衡度等對于無人機協(xié)同執(zhí)行任務具有重要意義的要素，優(yōu)化了無人機編隊拓撲。構建的滿意度隸屬度函數(shù)能夠綜合多個目標為無量綱的偏差值。多目標規(guī)劃能夠均衡考慮各個目標，結果表明，在通信鏈長增加幅度不大的情況下，網(wǎng)絡延遲較大幅度地減少，能量消耗也更加均勻，整體上能夠提高編隊的續(xù)航能力。改進的人工蜂群算法，對無人機信息交互拓撲具有更好的尋優(yōu)能力，能夠尋找到綜合質(zhì)量更好的信息交互拓撲。