無人機(jī)編隊(duì)信息交互拓?fù)涠嗄繕?biāo)優(yōu)化

谷曉燕， 陳 亮， 鄧香平

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

0 引言

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

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

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

1 無人機(jī)編隊(duì)拓?fù)溆绊懸蛩?/h2>

1.1 編隊(duì)通信鏈長(zhǎng)

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

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

只考慮整個(gè)編隊(duì)的通信總鏈長(zhǎng)最小化，領(lǐng)航者無人機(jī)到部分跟隨者無人機(jī)的通信鏈長(zhǎng)仍有可能較大，從而導(dǎo)致部分通信鏈路的延遲較高，進(jìn)而導(dǎo)致無人機(jī)因?yàn)榻邮招畔⒌臏蟀l(fā)生脫離編隊(duì)甚至碰撞的嚴(yán)重后果。這是因?yàn)榭傛滈L(zhǎng)的最小化并沒有考慮單條通信鏈路最短，有可能造成部分通信鏈路經(jīng)由過多中繼節(jié)點(diǎn)導(dǎo)致通信延遲的增大。

本文定義最大延遲為信息交互拓?fù)渲袕念I(lǐng)航者發(fā)送信息到其他跟隨者無人機(jī)接收信息的延遲中最大數(shù)值，用領(lǐng)航者無人機(jī)到末端跟隨者無人機(jī)的最大通信跳數(shù)簡(jiǎn)化表示。同時(shí)，基于復(fù)雜網(wǎng)絡(luò)中的度中心性的概念，將無人機(jī)與其他無人機(jī)建立通信鏈接的總和定義為該無人機(jī)的度中心性的測(cè)度，在拓?fù)渖芍?，通過約束編隊(duì)中無人機(jī)的度中心性來控制通信網(wǎng)絡(luò)中由于鏈接過多導(dǎo)致通信傳輸排隊(duì)從而增大擁塞延遲的情況。

1.3 剩余能量不均衡度

無人機(jī)編隊(duì)中每架無人機(jī)作用不相同，能量消耗速度也不同，不考慮能量消耗情況生成拓?fù)洌赡軙?huì)造成部分剩余能量少的無人機(jī)提前耗盡能量，影響編隊(duì)任務(wù)的執(zhí)行。在拓?fù)渥儞Q中，讓剩余能量多的無人機(jī)承擔(dān)更多的信息中繼功能，將有利于無人機(jī)編隊(duì)的能量消耗保持相對(duì)均衡，從而提高編隊(duì)整體的續(xù)航能力。

因此，本文抽象出鏈接剩余能量的概念，把建立拓?fù)滏溄拥膬杉軣o人機(jī)的剩余能量均值定義為相鄰兩架無人機(jī)鏈接剩余能量?？紤]生成的拓?fù)渲兴墟溄邮Ｓ嗄芰康钠骄导捌錁?biāo)準(zhǔn)差，基于統(tǒng)計(jì)中變異系數(shù)的思想，用鏈接剩余能量的標(biāo)準(zhǔn)差除以鏈接剩余能量的平均值，構(gòu)建剩余能量不均衡度指標(biāo)。剩余能量不均衡度取值越小，說明無人機(jī)編隊(duì)信息交互拓?fù)渲袩o人機(jī)能量分配越均衡。

2 多目標(biāo)優(yōu)化模型構(gòu)建

2.1 變量定義

本文用賦權(quán)有向圖G=(V,L,D)抽象表示無人機(jī)編隊(duì)通信網(wǎng)絡(luò)拓?fù)?，設(shè)置如下變量：

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

2)i，j為編隊(duì)中無人機(jī)的標(biāo)號(hào)，i,j∈{1,2,…,n},i≠j；

3)V為有向圖中節(jié)點(diǎn)的集合，每一個(gè)節(jié)點(diǎn)代表編隊(duì)中的一架無人機(jī)，V={Ui}，Ui代表第i架無人機(jī)；

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

5)D為有向圖中所有弧的權(quán)值的集合，di j為通信鏈接li j的鏈長(zhǎng)，表示編隊(duì)中任意兩架無人機(jī)Ui和Uj之間通信鏈接的長(zhǎng)度，生成的無人機(jī)編隊(duì)信息交互拓?fù)渫ㄐ趴傛滈L(zhǎng)用w表示，即

(1)

6)X為是否生成通信鏈接決策變量的集合，X={xi j}，xi j表示無人機(jī)編隊(duì)信息交互拓?fù)渖傻臎Q策變量，即

(2)

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

(3)

8)v為無人機(jī)編隊(duì)剩余能量不均衡度

(4)

(5)

9)H為有向圖中領(lǐng)航者無人機(jī)節(jié)點(diǎn)到末端跟隨者無人機(jī)節(jié)點(diǎn)的跳數(shù)集合，H={hk}，k為生成的無人機(jī)編隊(duì)信息交互拓?fù)渲蓄I(lǐng)航者無人機(jī)到末端跟隨者無人機(jī)的路徑條數(shù)，hk為信息交互拓?fù)渲械趉條路徑；h表示k條路徑中的最大通信跳數(shù)；

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

(6)

表示在無人機(jī)編隊(duì)信息交互拓?fù)渲校瑹o人機(jī)Ui與其他n-1架無人機(jī)直接發(fā)生通信鏈接的總數(shù);

11)Cd為度中心性的閾值，表示編隊(duì)信息交互拓?fù)渲校我还?jié)點(diǎn)與其他節(jié)點(diǎn)直接相連的最大數(shù)量限制。

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

1) 目標(biāo)函數(shù)。

編隊(duì)通信總鏈長(zhǎng)最小目標(biāo)(f1)表示為

(7)

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

(8)

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

(9)

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

(10)

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

本文借助隸屬度函數(shù)的思想統(tǒng)一量綱，把各個(gè)目標(biāo)轉(zhuǎn)化為無量綱的滿意度，從而將多目標(biāo)問題轉(zhuǎn)化為對(duì)多個(gè)目標(biāo)的滿意度問題，通過滿意度的偏差最小化進(jìn)行信息交互拓?fù)鋬?yōu)化。

針對(duì)編隊(duì)通信鏈長(zhǎng)最小目標(biāo)f1，構(gòu)造目標(biāo)滿意度的隸屬度函數(shù)s1。設(shè)下限a1為用Prim或Kruskal算法求出的最小生成樹弧的權(quán)值和，即計(jì)算的最小通信總鏈長(zhǎng)，上限b1為初始編隊(duì)通信鏈長(zhǎng)。編隊(duì)通信鏈長(zhǎng)滿意度的隸屬度函數(shù)s1(x)表示為

(11)

式中，w(x)表示生成的無人機(jī)編隊(duì)信息交互拓?fù)涞耐ㄐ趴傛滈L(zhǎng)，x為拓?fù)鋬?yōu)化的決策變量。

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

(12)

式中，v(x)表示生成的無人機(jī)編隊(duì)信息交互拓?fù)涞氖Ｓ嗄芰坎痪舛取?/p>

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

(13)

式中，h(x)表示生成的無人機(jī)編隊(duì)信息交互拓?fù)渥畲筇鴶?shù)的最小值。

(14)

3) 約束條件。

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

(15)

無人機(jī)與其他無人機(jī)建立通信鏈路的總和作為度中心性的測(cè)度，通過設(shè)置度中心性約束條件來控制通信網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)呐抨?duì)帶來的延遲。

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

(16)

3 改進(jìn)的人工蜂群算法

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

領(lǐng)航-跟隨者無人機(jī)編隊(duì)的信息交互拓?fù)淇梢杂?棵生成樹來表示，存在多條支鏈，具有分級(jí)的特點(diǎn)。鄰接矩陣用來表示一個(gè)信息交互拓?fù)洹Ｍㄟ^判斷連通圖算法，生成m棵用鄰接矩陣表示的生成樹，并存儲(chǔ)為外部文檔T，T={T1,T2,…,Tm}。設(shè)置R只引領(lǐng)蜂，R≤m，并從外部文檔中挑選與引領(lǐng)蜂數(shù)量相同的生成樹作為初始蜜源。一個(gè)蜜源代表一種無人機(jī)編隊(duì)拓?fù)洌墼幢徊杉淖畲蟠螖?shù)設(shè)為l，最大迭代次數(shù)設(shè)為Q。采用自然數(shù)編碼的方式來表示編隊(duì)的結(jié)構(gòu)，并采用基于生成樹的逆轉(zhuǎn)搜索(TOS)算子。TOS算子是在已有生成樹的基礎(chǔ)上，在距離根節(jié)點(diǎn)不同跳數(shù)的鏈路中，結(jié)合逆轉(zhuǎn)算子，變換子節(jié)點(diǎn)位置，從而構(gòu)成新的生成樹。引領(lǐng)蜂在蜜源的附近通過TOS算子生成一個(gè)候選蜜源，跟隨蜂依據(jù)蜜源的適應(yīng)度來選擇更好的蜜源進(jìn)行進(jìn)一步的搜索，適應(yīng)度函數(shù)表示為

(17)

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

當(dāng)引領(lǐng)蜂和跟隨蜂搜索一定次數(shù)后，如果沒有搜索出更好的蜜源，則會(huì)轉(zhuǎn)化為偵察蜂，隨機(jī)從外部文檔中挑選生成樹產(chǎn)生一個(gè)新解，并進(jìn)行無人機(jī)編隊(duì)拓?fù)錆M意度偏差值的計(jì)算。在進(jìn)行局部搜索時(shí)，依據(jù)當(dāng)前較好的拓?fù)渥儞Q出質(zhì)量更好的拓?fù)洌焖僬业綕M意度偏差更小的拓?fù)?，并?jīng)過進(jìn)一步迭代計(jì)算得到最優(yōu)解。

算法流程如圖1所示。

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

4 算例分析

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

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

只考慮鏈長(zhǎng)，基于最小生成樹求解的信息交互拓?fù)淙鐖D2所示。

圖2 最小生成樹算法求解信息交互拓?fù)鋱DFig.2 Information interaction topology map solved by minimum spanning tree algorithm

考慮多目標(biāo)，基于改進(jìn)人工蜂群算法求解的信息交互拓?fù)淙鐖D3所示。無人機(jī)之間連線上的數(shù)據(jù)表示無人機(jī)之間的通信鏈長(zhǎng)，括號(hào)內(nèi)第1位數(shù)字表示無人機(jī)標(biāo)號(hào)，其中設(shè)U1為領(lǐng)航者無人機(jī)，設(shè)U2～U16為跟隨者無人機(jī),第2位數(shù)字表示無人機(jī)的剩余能量。本文提出的算法求解的信息交互拓?fù)渑c基于最小生成樹算法求解的信息交互拓?fù)湎啾龋畲缶W(wǎng)絡(luò)延遲影響因素減少33.3%，剩余能量不均衡度減小12.4%，而編隊(duì)鏈長(zhǎng)僅增加13.6%。

圖3 改進(jìn)人工蜂群算法求解信息交互拓?fù)鋱DFig.3 Information interaction topology map solved by improved artificial bee colony algorithm

4.2 不同度中心性約束的對(duì)比

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

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

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

5 結(jié)論

本文綜合考慮了通信鏈長(zhǎng)、網(wǎng)絡(luò)延遲影響因素、剩余能量不均衡度等對(duì)于無人機(jī)協(xié)同執(zhí)行任務(wù)具有重要意義的要素，優(yōu)化了無人機(jī)編隊(duì)拓?fù)洹?gòu)建的滿意度隸屬度函數(shù)能夠綜合多個(gè)目標(biāo)為無量綱的偏差值。多目標(biāo)規(guī)劃能夠均衡考慮各個(gè)目標(biāo)，結(jié)果表明，在通信鏈長(zhǎng)增加幅度不大的情況下，網(wǎng)絡(luò)延遲較大幅度地減少，能量消耗也更加均勻，整體上能夠提高編隊(duì)的續(xù)航能力。改進(jìn)的人工蜂群算法，對(duì)無人機(jī)信息交互拓?fù)渚哂懈玫膶?yōu)能力，能夠?qū)ふ业骄C合質(zhì)量更好的信息交互拓?fù)洹?/p>