大規(guī)模UAV編隊(duì)信息交互拓?fù)涞姆旨?jí)分布式生成

董文奇，何鋒

北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100083

無人機(jī)(Unmanned Aerial Vehicle，UAV)編隊(duì)飛行是當(dāng)前UAV領(lǐng)域研究的熱點(diǎn)，隨著UAV技術(shù)的不斷發(fā)展，其已逐步被應(yīng)用在目標(biāo)偵察、目標(biāo)跟蹤、目標(biāo)打擊、通信中繼、噴灑農(nóng)藥、空中加油等眾多軍用和民用領(lǐng)域[1]。集群UAV突破了單個(gè)無人機(jī)技術(shù)和性能上的限制，利用自組網(wǎng)技術(shù)組織多種性能不同、功能各異的UAV協(xié)同合作，極大地提高了執(zhí)行任務(wù)的能力和效率[2]。伴隨著UAV集群執(zhí)行的任務(wù)越來越復(fù)雜多樣，編隊(duì)規(guī)模逐漸增大，編隊(duì)內(nèi)部UAV不易同步，編隊(duì)隊(duì)形難以保持，同時(shí)由于UAV自身存在計(jì)算/存儲(chǔ)能力受限、機(jī)載能源有限等特點(diǎn)[3]，UAV編隊(duì)飛行面臨著新的挑戰(zhàn)。因此對(duì)于大規(guī)模UAV集群，如何在保持隊(duì)形的同時(shí)，盡量減少總通信代價(jià)以及提高編隊(duì)續(xù)航能力進(jìn)行UAV編隊(duì)飛行是一個(gè)亟需解決的問題。

UAV編隊(duì)飛行時(shí)，只需要使用部分通信鏈路即可保持隊(duì)形，這部分通信鏈路即為隊(duì)形保持下的信息交互拓?fù)洌峭ㄐ啪W(wǎng)絡(luò)拓?fù)涞囊粋€(gè)子集[4]。按照編隊(duì)結(jié)構(gòu)，多智能體信息交互拓?fù)涞难芯靠纱笾路譃轭I(lǐng)航-跟隨者編隊(duì)、一致性編隊(duì)、剛性編隊(duì)以及持久編隊(duì)4類。針對(duì)領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)涞难芯浚墨I(xiàn)[5]證明了領(lǐng)航-跟隨者控制方法下，UAV編隊(duì)的信息交互拓?fù)涫峭ㄐ啪W(wǎng)絡(luò)拓?fù)涞囊豢糜邢蛏蓸洌辉诖嘶A(chǔ)上，文獻(xiàn)[4]提出了一種集中式基于最小樹形圖(Minimum Cost Arborescence，MCA)的領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)鋬?yōu)化算法。一致性編隊(duì)的主要核心思想是智能體利用與之通信的鄰居智能體的狀態(tài)信息更新自身的狀態(tài)，并最終使所有智能體狀態(tài)達(dá)到一致，比如文獻(xiàn)[6]在動(dòng)態(tài)變化的信息交互拓?fù)浜蜋?quán)重因子條件下，提出了一種新的一致性控制協(xié)議，并將一階系統(tǒng)推廣到n階可控系統(tǒng)。剛性編隊(duì)則通過生成最優(yōu)剛性圖實(shí)現(xiàn)信息交互拓?fù)涞臉?gòu)建[7-8]。持久編隊(duì)信息交互拓?fù)涞膶?shí)現(xiàn)通過對(duì)最優(yōu)剛性圖進(jìn)行有向化操作實(shí)現(xiàn)，文獻(xiàn)[4，9]對(duì)這種思想進(jìn)行了進(jìn)一步擴(kuò)展，分別討論了通過MCA和5種有向化操作生成最優(yōu)持久圖的方法。

對(duì)于領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)涞难芯浚壳爸饕性谛∫?guī)模UAV編隊(duì)，文獻(xiàn)[4]中的大規(guī)模UAV編隊(duì)的規(guī)模也只有16，且僅以通信鏈路長(zhǎng)度衡量通信代價(jià)，并將總通信代價(jià)最小作為單一的優(yōu)化目標(biāo)。分級(jí)分簇結(jié)構(gòu)在擴(kuò)大組網(wǎng)規(guī)模方面有著天然優(yōu)勢(shì)，在無線傳感器網(wǎng)絡(luò)方面應(yīng)用廣泛[10-12]，并已逐步應(yīng)用在UAV領(lǐng)域，但目前仍未發(fā)現(xiàn)有相關(guān)文獻(xiàn)將其應(yīng)用在UAV編隊(duì)信息交互拓?fù)涞难芯可稀?/p>

因此，本文在文獻(xiàn)[4]的基礎(chǔ)上，將分級(jí)分簇結(jié)構(gòu)引入信息交互拓?fù)涞难芯恐校瑫r(shí)以提高編隊(duì)續(xù)航能力、減少編隊(duì)總通信代價(jià)作為組合優(yōu)化目標(biāo)，提出了一種分級(jí)分布式信息交互拓?fù)渖伤惴ǎ⑼ㄟ^OMNeT++進(jìn)行算法仿真驗(yàn)證。

本文結(jié)構(gòu)如下：第1節(jié)介紹UAV編隊(duì)信息交互拓?fù)淠Ｐ停坏?節(jié)介紹UAV編隊(duì)信息交互拓?fù)涞纳伤惴ǎ坏?節(jié)通過實(shí)驗(yàn)仿真，從求解時(shí)間、總通信代價(jià)和UAV剩余能量3方面對(duì)本文算法進(jìn)行評(píng)估；第4節(jié)對(duì)本文工作進(jìn)行總結(jié)，并對(duì)下一步工作進(jìn)行展望。

1 信息交互拓?fù)淠Ｐ?/h2>

在UAV編隊(duì)飛行中，常用的編隊(duì)控制方法主要有領(lǐng)航-跟隨者(Leader-Follower)方法、一致性方法、剛性圖方法和持久圖方法等，其中剛性圖方法和持久圖方法均屬于圖論法[13-14]。領(lǐng)航-跟隨者方法是目前多UAV編隊(duì)控制中最常用的方法之一，該方法是將編隊(duì)中的某架無人機(jī)指定為領(lǐng)航者，而其他無人機(jī)作為跟隨者，其具有較強(qiáng)的擴(kuò)展性，且節(jié)約能量、簡(jiǎn)單易行，如圖1所示。

文獻(xiàn)[5]已經(jīng)證明，領(lǐng)航-跟隨者編隊(duì)控制方法對(duì)應(yīng)UAV編隊(duì)的信息交互拓?fù)錇橥ㄐ啪W(wǎng)絡(luò)拓?fù)涞?棵有向生成樹，信息交互拓?fù)浜屯ㄐ啪W(wǎng)絡(luò)拓?fù)渚捎觅x權(quán)有向圖表示。

1.1 圖論基礎(chǔ)

隊(duì)形保持下UAV編隊(duì)的通信網(wǎng)絡(luò)拓?fù)淇捎觅x權(quán)有向圖G=(V,A,W)表示[15]，其中V={vi},i∈{1,2,…,n}，是有向圖的點(diǎn)集合，vi代表UAVi；A={aij},i,j∈{1,2,…,n},i≠j，是有向圖的弧集合，aij代表UAVi和UAVj之間的通信鏈接；W={wij},i,j∈{1,2,…,n},i≠j，是有向圖所有弧的權(quán)值集合，wij代表通信鏈接aij的權(quán)值。信息交互拓?fù)涫峭ㄐ啪W(wǎng)絡(luò)拓?fù)涞囊粋€(gè)子集，即T=(V,A*,W*)?G。

1) 生成樹[16]：給定一個(gè)無向圖G，如果圖G的一個(gè)生成子圖T是一棵樹，則稱T是G的一棵生成樹。

2) 最小生成樹：給定一個(gè)帶權(quán)無向圖G，存在一棵生成樹T，其所有弧的權(quán)值和W(T)最小，則稱T是G的最小生成樹。

有向圖的最小生成樹稱為最小樹形圖，隊(duì)形保持下的信息交互拓?fù)浜屯ㄐ啪W(wǎng)絡(luò)拓?fù)渚捎觅x權(quán)有向圖表示，因此本文基于最小樹形圖設(shè)計(jì)隊(duì)形保持下的信息交互拓?fù)淠Ｐ图吧伤惴ā?/p>

1.2 通信鏈路

編隊(duì)飛行時(shí)，UAV之間采用無線鏈路發(fā)送位置信息以保持隊(duì)形。設(shè)計(jì)UAV編隊(duì)的信息交互拓?fù)渖伤惴〞r(shí)，需要對(duì)通信鏈路的代價(jià)進(jìn)行合理的衡量，現(xiàn)有的信息交互拓?fù)淠Ｐ驮诤饬客ㄐ沛溌反鷥r(jià)時(shí)只單一考慮鏈路長(zhǎng)度，本文在其基礎(chǔ)上同時(shí)考慮了位置誤差的傳遞迭代，為簡(jiǎn)化計(jì)算并對(duì)其進(jìn)行了歸一化：

1) 通信鏈路的長(zhǎng)度[17]：一般情況下，UAV之間的通信距離越短，UAV所消耗的能量就越少，對(duì)應(yīng)通信鏈路的代價(jià)越小。

UAVi和UAVj之間的距離用dij表示，代表鏈路的距離代價(jià)，則

(1)

式中：(xi,yi)為UAVi的位置坐標(biāo)；(xj,yj)為UAVj的位置坐標(biāo)。

對(duì)其進(jìn)行歸一化處理：

(2)

式中：dsafe為UAV之間的安全距離[18]，小于安全距離UAV之間將有發(fā)生碰撞的危險(xiǎn)；drange為UAV之間的最大通信距離。

將通信鏈路長(zhǎng)度作為衡量指標(biāo)進(jìn)行信息交互拓?fù)涞膬?yōu)化，得到的信息交互拓?fù)淇梢员M量降低UAV編隊(duì)保持隊(duì)形時(shí)的能量消耗。

2) 位置誤差的傳遞迭代[19]：在領(lǐng)航-跟隨者編隊(duì)中，存在位置誤差的傳遞迭代，越靠后的UAV與領(lǐng)航者之間存在的位置誤差越大，因此對(duì)應(yīng)通信鏈路的代價(jià)就越大。

領(lǐng)航-跟隨者編隊(duì)中，領(lǐng)航者的下級(jí)在接收到位置信息時(shí)，會(huì)以此作為其跟隨目標(biāo)，由于端到端延遲的存在導(dǎo)致下級(jí)節(jié)點(diǎn)實(shí)際位置與此時(shí)的理論位置存在一定誤差；它繼續(xù)將自身位置信息向下傳，經(jīng)過迭代就形成了位置誤差的傳遞。由于位置誤差的傳遞迭代，越遠(yuǎn)離領(lǐng)航者的通信鏈路的代價(jià)越大。因此本文根據(jù)遠(yuǎn)離領(lǐng)航者的程度，首先賦予無人機(jī)一個(gè)誤差系數(shù)，用f表示，越遠(yuǎn)離領(lǐng)航者的UAV的誤差系數(shù)越大，圖2中各無人機(jī)的誤差系數(shù)如表1所示。

表1 無人機(jī)誤差系數(shù)fi

劃分編隊(duì)中UAV誤差系數(shù)時(shí)以某一UAV為中心，該UAV的誤差系數(shù)為0，半徑為r圓形范圍內(nèi)的UAV誤差系數(shù)為1，r～2r圓環(huán)范圍內(nèi)的UAV誤差系數(shù)為2，以此類推。本文分級(jí)分簇結(jié)構(gòu)中，二級(jí)領(lǐng)航者以一級(jí)領(lǐng)航者為中心，簇內(nèi)節(jié)點(diǎn)以二級(jí)領(lǐng)航者為中心。

有向通信鏈路的誤差代價(jià)用起點(diǎn)無人機(jī)的誤差系數(shù)表征，如圖2所示，可以看出通信鏈路的誤差代價(jià)與鏈路長(zhǎng)度無關(guān)，與遠(yuǎn)離領(lǐng)航者的程度有關(guān)。

圖2 無人機(jī)誤差系數(shù)劃分示意圖

綜上所述，通信鏈路aij的誤差代價(jià)fij取決于發(fā)送UAV，即

fij=fi

(3)

對(duì)其進(jìn)行歸一化處理：

(4)

式中：fmax為能夠保持隊(duì)形的最大誤差系數(shù)。

將位置誤差的傳遞迭代作為衡量指標(biāo)進(jìn)行信息交互拓?fù)涞膬?yōu)化，得到的信息交互拓?fù)淇梢员ＷCUAV編隊(duì)隊(duì)形盡量接近預(yù)期隊(duì)形。

綜合以上兩方面，通信鏈路aij的權(quán)值wij表示為

wij=αdDij+αcFij

(5)

式中：αd、αc分別為距離權(quán)重系數(shù)和誤差權(quán)重系數(shù)，并且

αd+αc=1

(6)

結(jié)合非交叉型分級(jí)分簇結(jié)構(gòu)，本文將整個(gè)UAV編隊(duì)的信息交互拓?fù)渖蓡栴}分解為若干小編隊(duì)的信息交互拓?fù)渖蓡栴}，在各個(gè)簇首上分布式執(zhí)行。隊(duì)形保持下分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)的信息交互拓?fù)渚W(wǎng)絡(luò)模型如圖3所示，簇內(nèi)與簇間均采用領(lǐng)航-跟隨者編隊(duì)，一級(jí)領(lǐng)航者沿規(guī)劃路線飛行，二級(jí)領(lǐng)航者跟隨一級(jí)領(lǐng)航者飛行，簇內(nèi)成員跟隨二級(jí)領(lǐng)航者飛行，形成了分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)。

圖3 隊(duì)形保持下分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)渚W(wǎng)絡(luò)模型

2 信息交互拓?fù)渖伤惴?/h2>

現(xiàn)有的信息交互拓?fù)渖伤惴ň窒抻谛∫?guī)模UAV編隊(duì)，且優(yōu)化目標(biāo)單一。本文在其基礎(chǔ)上，結(jié)合分級(jí)分簇結(jié)構(gòu)，同時(shí)以提高編隊(duì)續(xù)航能力和減少編隊(duì)總通信代價(jià)為組合優(yōu)化目標(biāo)，提出了一種基于MCA的分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)渖伤惴āＳ捎诒疚牡男畔⒔换ネ負(fù)淠Ｐ筒捎昧朔旨?jí)分簇結(jié)構(gòu)，因此需分別構(gòu)建簇間信息交互拓?fù)渑c簇內(nèi)信息交互拓?fù)洹?/p>

分級(jí)分簇結(jié)構(gòu)中簇群、簇首集合分別采用符號(hào)C、H表示，其中簇群i可表示為

(7)

簇首集合H可表示為

H={h1,h2,…,hi,…,hNc}

(8)

式中：hi表示簇群i的簇首，編隊(duì)一級(jí)領(lǐng)航者用L表示，且L∈H。

2.1 編隊(duì)續(xù)航能力

為提高UAV編隊(duì)整體續(xù)航能力，本文采取了根據(jù)UAV剩余能量周期性更新簇首的方法，以均衡網(wǎng)絡(luò)能量。

UAV剩余能量根據(jù)式(9)計(jì)算：

Ea=Eb-ER-ET-EM

(9)

式中：Eb為上一周期UAV的剩余能量；Ea為本周期UAV的剩余能量：ER為本周期UAV接收消息消耗的能量；ET為本周期UAV發(fā)送消息消耗的能量；EM為本周期UAV移動(dòng)消耗的能量。

假設(shè)UAV單次接收消息消耗能量為Er，單次發(fā)送消息消耗能量為Et，UAV移動(dòng)單位距離消耗能量為Em，簇首更新周期為t，時(shí)間t內(nèi)發(fā)送消息次數(shù)為MT，時(shí)間t內(nèi)接收消息次數(shù)為MR，時(shí)間t內(nèi)移動(dòng)的距離為s，則

(10)

2.2 總體通信代價(jià)

非交叉型分級(jí)分簇結(jié)構(gòu)下，為保證總體通信代價(jià)最小，須分別計(jì)算簇內(nèi)通信網(wǎng)絡(luò)拓?fù)浜痛亻g通信網(wǎng)絡(luò)拓?fù)涞淖钚湫螆D構(gòu)建信息交互拓?fù)洹?/p>

證明：UAV編隊(duì)的通信網(wǎng)絡(luò)拓?fù)錇镚={Gi∪GH},i∈{1,2,…,Nc}，若T的總體通信代價(jià)不是最小的，則存在T′，使得W(T′)

根據(jù)以上兩個(gè)優(yōu)化目標(biāo)提出的分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)涞纳伤惴鞒倘鐖D4所示。算法主要包括位置信息發(fā)送、信息交互拓?fù)溆?jì)算、拓?fù)湫畔l(fā)送以及簇首重新選舉4個(gè)步驟。

圖4 基于最小樹形圖的分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)渖伤惴?/p>

本算法在分簇完成的基礎(chǔ)上進(jìn)行，輸入簇的個(gè)數(shù)以及各個(gè)簇的成員數(shù)并初始化隊(duì)形。

步驟1位置信息發(fā)送，下級(jí)節(jié)點(diǎn)向上級(jí)節(jié)點(diǎn)發(fā)送位置信息。

步驟2信息交互拓?fù)溆?jì)算，判斷hi是否為一級(jí)領(lǐng)航者，一級(jí)領(lǐng)航者需同時(shí)構(gòu)建簇間通信網(wǎng)絡(luò)拓?fù)浜痛貎?nèi)通信網(wǎng)絡(luò)拓?fù)洌?jí)領(lǐng)航者即普通簇首只需構(gòu)建簇內(nèi)通信網(wǎng)絡(luò)拓?fù)洌?jì)算通信網(wǎng)絡(luò)拓?fù)涞淖钚湫螆D。

步驟3拓?fù)湫畔l(fā)送，一級(jí)領(lǐng)航者將簇間拓?fù)湫畔l(fā)送給二級(jí)領(lǐng)航者，簇首(包括一級(jí)領(lǐng)航者和二級(jí)領(lǐng)航者)將簇內(nèi)拓?fù)湫畔l(fā)送給簇內(nèi)成員，構(gòu)建UAV編隊(duì)信息交互拓?fù)洹?/p>

步驟4簇首重新選舉，時(shí)間間隔t后根據(jù)式(9) 和式(10)計(jì)算UAV的剩余能量并更新簇首，若簇首集合H改變需重新計(jì)算信息交互拓?fù)洌粑锤淖儎t信息交互拓?fù)洳蛔儭?/p>

上述算法將降低總通信代價(jià)和提高編隊(duì)續(xù)航能力作為組合優(yōu)化目標(biāo)，分步完成。首先，將通信鏈路長(zhǎng)度、位置誤差的傳遞迭代作為衡量鏈路通信代價(jià)的指標(biāo)，并通過計(jì)算簇內(nèi)、簇間通信網(wǎng)絡(luò)拓?fù)涞淖钚湫螆D實(shí)現(xiàn)減少編隊(duì)總通信代價(jià)的目標(biāo)。分級(jí)分簇網(wǎng)絡(luò)結(jié)構(gòu)中，簇首除了維持拓?fù)渫猓€需要收集下級(jí)節(jié)點(diǎn)的信息并計(jì)算拓?fù)洌虼伺c普通節(jié)點(diǎn)相比，航行相同距離簇首消耗的能量更多；在上述算法中，通過根據(jù)UAV剩余能量周期性更新簇首的方法均衡網(wǎng)絡(luò)中無人機(jī)的能量，實(shí)現(xiàn)提高編隊(duì)續(xù)航能力的目標(biāo)。另外，由于本文算法考慮到位置誤差的傳遞迭代，采用分級(jí)分簇結(jié)構(gòu)分別構(gòu)建簇內(nèi)、簇間信息交互拓?fù)洌ㄟ^分布式計(jì)算達(dá)到大規(guī)模編隊(duì)下隊(duì)形保持的目的。

3 算法效能評(píng)估

3.1 算法評(píng)價(jià)

UAV編隊(duì)飛行時(shí)，信息交互拓?fù)渖伤惴ㄐ枘軌蚩焖夙憫?yīng)，以保證編隊(duì)內(nèi)UAV在到達(dá)預(yù)定位置后迅速構(gòu)建拓?fù)洌乐拱l(fā)生碰撞甚至損毀，因此信息交互拓?fù)渖伤惴ǖ那蠼鈺r(shí)間是一個(gè)重要的評(píng)價(jià)標(biāo)準(zhǔn)。另外，針對(duì)本文算法的兩個(gè)優(yōu)化目標(biāo)，分別以編隊(duì)內(nèi)UAV剩余能量和信息交互拓?fù)涞目偼ㄐ糯鷥r(jià)作為評(píng)價(jià)標(biāo)準(zhǔn)。

3.2 實(shí)驗(yàn)仿真

利用OMNeT++平臺(tái)搭建大規(guī)模UAV編隊(duì)飛行場(chǎng)景，假設(shè)每架UAV的通信范圍為1 500 m[20]，UAV之間的安全距離為200 m[21]，并且在飛行過程中均不會(huì)發(fā)生任何故障。

編隊(duì)規(guī)模為40時(shí)，采用本文算法生成的分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)的信息交互拓?fù)淙鐖D5所示，其中紅色節(jié)點(diǎn)為一級(jí)領(lǐng)航者，藍(lán)色節(jié)點(diǎn)為二級(jí)領(lǐng)航者，其間連線構(gòu)成簇間信息交互拓?fù)洌痪G色節(jié)點(diǎn)為簇內(nèi)節(jié)點(diǎn)，其與各自簇首之間的連線構(gòu)成簇內(nèi)信息交互拓?fù)洹１３窒嗤庩?duì)隊(duì)形，傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)的信息交互拓?fù)淙鐖D6所示，紅色節(jié)點(diǎn)為領(lǐng)航者，綠色節(jié)點(diǎn)為普通節(jié)點(diǎn)。

圖5 分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)?αc=0.2)

圖6 傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)?αc=0.2)

1) 求解時(shí)間

算法的時(shí)間開銷主要取決于位置信息發(fā)送與拓?fù)湫畔l(fā)送兩個(gè)步驟。消息的端到端延遲包括傳輸延遲、傳播延遲以及排隊(duì)延遲，傳播延遲正比于兩節(jié)點(diǎn)之間的距離；在位置信息發(fā)送步驟中，下級(jí)節(jié)點(diǎn)同時(shí)向上級(jí)節(jié)點(diǎn)發(fā)送位置信息，消息長(zhǎng)度固定即傳輸延遲相同；消息在接收節(jié)點(diǎn)處存在排隊(duì)延遲，如圖7所示。而在拓?fù)湫畔l(fā)送步驟中，拓?fù)湎⒌拈L(zhǎng)度正比于下級(jí)節(jié)點(diǎn)的數(shù)量，即傳輸延遲正比于下級(jí)節(jié)點(diǎn)的數(shù)量；消息在發(fā)送節(jié)點(diǎn)處存在排隊(duì)延遲，如圖8所示。兩個(gè)步驟的時(shí)間開銷均隨著下級(jí)節(jié)點(diǎn)數(shù)量的增多而增大。

圖7 位置信息發(fā)送步驟上級(jí)節(jié)點(diǎn)接收隊(duì)列

圖8 拓?fù)湫畔l(fā)送步驟上級(jí)節(jié)點(diǎn)發(fā)送隊(duì)列

分級(jí)分布式領(lǐng)航-跟隨者結(jié)構(gòu)采用分級(jí)分簇結(jié)構(gòu)，簇首構(gòu)建簇內(nèi)信息交互拓?fù)洌湎录?jí)節(jié)點(diǎn)數(shù)量即該簇群的成員節(jié)點(diǎn)數(shù)量；一級(jí)領(lǐng)航者構(gòu)建簇間信息交互拓?fù)洌湎录?jí)節(jié)點(diǎn)數(shù)量即二級(jí)領(lǐng)航者的數(shù)量，所以分級(jí)分布式領(lǐng)航-跟隨者結(jié)構(gòu)信息交互拓?fù)涞那蠼鈺r(shí)間與各個(gè)簇群的規(guī)模以及簇群的數(shù)量正相關(guān)；而在傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)中，信息交互拓?fù)涞那蠼鈺r(shí)間與整個(gè)編隊(duì)的規(guī)模正相關(guān)。因此小規(guī)模編隊(duì)時(shí)兩種編隊(duì)結(jié)構(gòu)信息交互拓?fù)涞那蠼鈺r(shí)間相差較小，而隨著編隊(duì)規(guī)模的增大，分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)結(jié)構(gòu)的優(yōu)勢(shì)會(huì)逐漸顯著。

通過實(shí)驗(yàn)對(duì)比不同編隊(duì)規(guī)模下分級(jí)分布式領(lǐng)航-跟隨者、傳統(tǒng)領(lǐng)航-跟隨者兩種編隊(duì)結(jié)構(gòu)信息交互拓?fù)涞那蠼鈺r(shí)間，如圖9所示。其中相關(guān)參數(shù)如表2所示。

表2 求解時(shí)間對(duì)比實(shí)驗(yàn)的相關(guān)參數(shù)

從圖9中可以看出，20～80架無人機(jī)幾種規(guī)模下分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)涞那蠼鈺r(shí)間均小于傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)，求解效率分別約提高74%、85%、170%和250%，而當(dāng)編隊(duì)規(guī)模為100時(shí)，傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)由于位置誤差的傳遞迭代已不能保持原有隊(duì)形。

圖9 兩種編隊(duì)結(jié)構(gòu)信息交互拓?fù)淝蠼鈺r(shí)間對(duì)比

針對(duì)分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)，一般來說，簇群規(guī)模大于簇群數(shù)量，此時(shí)信息交互拓?fù)涞那蠼鈺r(shí)間取決于簇群規(guī)模，簇群規(guī)模越大其求解時(shí)間越大；而當(dāng)簇群規(guī)模小于簇群數(shù)量時(shí)，信息交互拓?fù)涞那蠼鈺r(shí)間取決于簇群數(shù)量，簇群越多其求解時(shí)間越大。因此分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)結(jié)構(gòu)下，為使信息交互拓?fù)淝蠼鈺r(shí)間最小，在給定編隊(duì)規(guī)模的前提下應(yīng)盡量使簇群數(shù)量與簇內(nèi)UAV數(shù)量相當(dāng)。

2) 總通信代價(jià)

分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)采用分級(jí)分簇結(jié)構(gòu)，需分別構(gòu)建簇內(nèi)、簇間通信網(wǎng)絡(luò)拓?fù)洌鐖D10(a) 所示。與傳統(tǒng)結(jié)構(gòu)相比，簇群的存在使得在構(gòu)建通信網(wǎng)絡(luò)拓?fù)鋾r(shí)舍棄了一部分通信鏈路(圖10(b)中綠色通信鏈路)。

本文算法在鏈路通信代價(jià)的衡量上同時(shí)考慮了鏈路長(zhǎng)度以及位置誤差的傳遞，并引入了距離權(quán)重系數(shù)αd以及誤差權(quán)重系數(shù)αc。當(dāng)αd=1.0時(shí)，即只用鏈路長(zhǎng)度衡量鏈路通信代價(jià)時(shí)，分級(jí)分簇結(jié)構(gòu)由于舍棄了一部分通信鏈路，信息交互拓?fù)淇偼ㄐ糯鷥r(jià)很可能高于傳統(tǒng)結(jié)構(gòu)；而當(dāng)鏈路的通信代價(jià)同時(shí)考慮鏈路長(zhǎng)度和位置誤差的傳遞迭代時(shí)，分級(jí)分簇結(jié)構(gòu)中位置誤差僅僅在簇內(nèi)或者簇首間傳遞，而傳統(tǒng)結(jié)構(gòu)在整個(gè)編隊(duì)中傳遞(圖10 中數(shù)字為鏈路誤差代價(jià))。此時(shí)伴隨著αc的增大，分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)在總通信代價(jià)上會(huì)明顯優(yōu)于傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)。

圖10 兩種編隊(duì)結(jié)構(gòu)通信網(wǎng)絡(luò)拓?fù)涫疽鈭D

通過實(shí)驗(yàn)對(duì)比不同距離權(quán)重系數(shù)下分級(jí)分布式領(lǐng)航-跟隨者、傳統(tǒng)領(lǐng)航-跟隨者兩種編隊(duì)結(jié)構(gòu)信息交互拓?fù)涞目偼ㄐ糯鷥r(jià)，如圖11所示。其中相關(guān)參數(shù)如表3所示。

表3 總通信代價(jià)對(duì)比實(shí)驗(yàn)相關(guān)參數(shù)

從圖11中可以看出，在αd=1.0時(shí)，此時(shí)通信鏈路權(quán)重的衡量只考慮了長(zhǎng)度，本文分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)的總通信代價(jià)高于傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)，這是由于分級(jí)分簇結(jié)構(gòu)舍棄了通信網(wǎng)絡(luò)拓?fù)渲械囊徊糠滞ㄐ沛溌罚欢讦羋=0.8,0.6,0.4 時(shí)，通信鏈路權(quán)重考慮了位置誤差的傳遞迭代，此時(shí)分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)的總通信代價(jià)低于傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)，對(duì)于傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)，由于位置誤差的傳遞迭代，當(dāng)編隊(duì)規(guī)模足夠大時(shí)編隊(duì)隊(duì)形將難以保持。UAV編隊(duì)飛行時(shí)，αd參數(shù)的選取需要在通信代價(jià)和隊(duì)形保持之間進(jìn)行權(quán)衡。

圖11 兩種編隊(duì)結(jié)構(gòu)信息交互拓?fù)淇偼ㄐ糯鷥r(jià)對(duì)比

3) UAV剩余能量

本文算法的分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)采取了分級(jí)分簇結(jié)構(gòu)，與傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)相比在以下兩個(gè)方面均衡了網(wǎng)絡(luò)能耗：① 信息交互拓?fù)涞挠?jì)算在各個(gè)簇首上分布式執(zhí)行，相當(dāng)于各個(gè)簇首共同分擔(dān)領(lǐng)航者的工作，避免出現(xiàn)領(lǐng)航者能耗過快的情況；② 可通過周期性選取簇首，進(jìn)一步均衡網(wǎng)絡(luò)能耗，以提高編隊(duì)續(xù)航能力。

現(xiàn)用編隊(duì)中UAV剩余能量的標(biāo)準(zhǔn)差來衡量網(wǎng)絡(luò)能耗的均衡程度，通過實(shí)驗(yàn)進(jìn)行仿真驗(yàn)證，相關(guān)參數(shù)如表4所示。

表4 剩余能量對(duì)比實(shí)驗(yàn)相關(guān)參數(shù)

圖12是仿真時(shí)間10 s和20 s時(shí)兩種編隊(duì)結(jié)構(gòu)UAV剩余能量的分布折線圖，從圖中可以看出本文分級(jí)分布式領(lǐng)航-跟隨者結(jié)構(gòu)中UAV剩余能量的分布更為均勻，標(biāo)準(zhǔn)差分別為1 006.463 293和3 109.960 689，而傳統(tǒng)領(lǐng)航-跟隨者結(jié)構(gòu)UAV剩余能量的標(biāo)準(zhǔn)差分別為1 363.489和4 472.05。

圖12 兩種編隊(duì)結(jié)構(gòu)中UAV剩余能量分布折線圖

4 結(jié) 論

本文提出的基于最小樹形圖的分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)信息交互拓?fù)渖伤惴ǎ渚W(wǎng)絡(luò)模型引入了分級(jí)分簇結(jié)構(gòu)，更適應(yīng)于大規(guī)模UAV編隊(duì)。算法的仿真結(jié)果表明：

1) 在編隊(duì)規(guī)模為20～80時(shí)，分級(jí)分布式領(lǐng)航-跟隨者編隊(duì)的求解時(shí)間均低于傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)的求解時(shí)間，且隨著編隊(duì)規(guī)模增大，本文算法優(yōu)勢(shì)將更加顯著。

2) 在通信鏈路代價(jià)只考慮鏈路長(zhǎng)度的情況下，本文算法由于采用了分級(jí)分簇結(jié)構(gòu)，總通信代價(jià)高于傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)；在通信鏈路代價(jià)同時(shí)考慮位置誤差的傳遞迭代時(shí)，本文算法的總通信代價(jià)明顯低于傳統(tǒng)領(lǐng)航-跟隨者編隊(duì)。

3) 本文算法通過周期性更新簇首，相同時(shí)間后編隊(duì)中UAV剩余能量標(biāo)準(zhǔn)差更小，反映了網(wǎng)絡(luò)能耗更加均衡，可有效提高編隊(duì)整體續(xù)航能力。

進(jìn)一步考慮UAV損毀以及通信鏈路中斷等突發(fā)情況下本文方法的適應(yīng)性，在本文算法中UAV編隊(duì)的信息交互拓?fù)湫柽M(jìn)行周期性更新，當(dāng)發(fā)生UAV損毀或者通信鏈路中斷時(shí)，信息交互拓?fù)鋾?huì)及時(shí)進(jìn)行再生成，但還是需要進(jìn)一步考慮反應(yīng)速度以及再生成代價(jià)等方面的影響。反應(yīng)速度方面，突發(fā)情況下編隊(duì)的信息交互拓?fù)鋺?yīng)及時(shí)進(jìn)行再生成，同時(shí)再生成時(shí)間應(yīng)盡量小，否則可能發(fā)生更嚴(yán)重的碰撞事故；再生成代價(jià)方面，不同的突發(fā)情況對(duì)信息交互拓?fù)洚a(chǎn)生的影響不同，比如簇內(nèi)通信鏈路中斷僅影響簇內(nèi)信息交互拓?fù)洌亻g通信鏈路中斷僅影響簇間信息交互拓?fù)洌藭r(shí)往往不需要進(jìn)行整個(gè)信息交互拓?fù)涞脑偕伞１疚姆椒ㄓ捎诓捎昧朔旨?jí)分簇結(jié)構(gòu)，可根據(jù)突發(fā)情況的類型，僅針對(duì)某個(gè)簇內(nèi)的信息交互拓?fù)浠蛘叽亻g信息交互拓?fù)溥M(jìn)行再生成，再生成效率更高，代價(jià)更小。綜上所述，本文算法經(jīng)過反應(yīng)速度等方面的完善可以適應(yīng)突發(fā)情況下的信息交互拓?fù)鋬?yōu)化生成，突發(fā)情況下算法的適應(yīng)性將是后續(xù)進(jìn)一步研究的方向。