劉亞群，謝鈞，邢長(zhǎng)友，倪保安

（1.陸軍工程大學(xué)指揮控制工程學(xué)院，江蘇 南京 210007；2.中國(guó)人民解放軍92771 部隊(duì)，山東 青島 250100）

0 引言

無(wú)人機(jī)（UAV,unmanned aerial vehicle）具有快速部署、低成本、易控制、視距通信等特性，已經(jīng)被廣泛應(yīng)用于多個(gè)領(lǐng)域[1-2]。例如，UAV 可以用于情報(bào)偵察、目標(biāo)打擊、信息分發(fā)、電子干擾等[3]，也可以用于實(shí)時(shí)監(jiān)控[4]、交通管理[5]、空中基站[6]、網(wǎng)絡(luò)中繼[7]、數(shù)據(jù)采集[8]、貨物運(yùn)輸[9]、災(zāi)后救援[10]等。

若干年來(lái)，單一的大型無(wú)人機(jī)一直被用于執(zhí)行任務(wù)[11-13]。為了維持與地面基站或空中衛(wèi)星之間的通信，該無(wú)人機(jī)需要配備昂貴且復(fù)雜的硬件[14]。此外，單無(wú)人機(jī)攜帶的資源有限，可能無(wú)法滿足實(shí)際需求。隨著無(wú)人機(jī)制造技術(shù)的發(fā)展以及制造成本的降低，規(guī)?；厣a(chǎn)低成本、高性能的小型或微型無(wú)人機(jī)已經(jīng)成為可能。由于單一無(wú)人機(jī)能力有限，由若干小型或微型無(wú)人機(jī)組成的無(wú)人機(jī)集群開(kāi)始被用于執(zhí)行任務(wù)[15-17]。實(shí)踐表明，相比于單無(wú)人機(jī)系統(tǒng)，多無(wú)人機(jī)系統(tǒng)具有若干優(yōu)勢(shì)[18-20]。例如，在容錯(cuò)性方面，當(dāng)單無(wú)人機(jī)系統(tǒng)出現(xiàn)故障時(shí)，任務(wù)將無(wú)法繼續(xù)執(zhí)行，而在多無(wú)人機(jī)系統(tǒng)中，當(dāng)個(gè)別無(wú)人機(jī)出現(xiàn)故障后，任務(wù)仍可由其他無(wú)人機(jī)繼續(xù)執(zhí)行。在任務(wù)性能方面，與單無(wú)人機(jī)系統(tǒng)相比，多無(wú)人機(jī)系統(tǒng)的覆蓋面積更大，任務(wù)執(zhí)行速度更快。

在多無(wú)人機(jī)系統(tǒng)中，無(wú)人機(jī)之間以及無(wú)人機(jī)與地面基站之間的通信架構(gòu)可以分為2 種[14,21-22]：基于基礎(chǔ)設(shè)施的多無(wú)人機(jī)系統(tǒng)和飛行自組網(wǎng)（FANET,flying ad-hoc network），如圖1 所示。在基于基礎(chǔ)設(shè)施的多無(wú)人機(jī)系統(tǒng)中，所有無(wú)人機(jī)都與地面基站等基礎(chǔ)設(shè)施直接建立連接，無(wú)人機(jī)之間的通信均需要通過(guò)基礎(chǔ)設(shè)施來(lái)實(shí)現(xiàn)。為了維持無(wú)人機(jī)與基礎(chǔ)設(shè)施之間的連接，每個(gè)無(wú)人機(jī)都需要配備復(fù)雜的硬件并且維持較高的發(fā)送功率，無(wú)人機(jī)的移動(dòng)范圍受限。此外，由于無(wú)人機(jī)之間的通信都需要通過(guò)基礎(chǔ)設(shè)施來(lái)實(shí)現(xiàn)，無(wú)人機(jī)之間的通信具有較高時(shí)延。在FANET 中，只有少量無(wú)人機(jī)與基礎(chǔ)設(shè)施直接建立連接，無(wú)人機(jī)之間以及無(wú)人機(jī)與地面基站之間的通信可通過(guò)若干無(wú)人機(jī)中繼實(shí)現(xiàn)，有效解決了基于基礎(chǔ)設(shè)施的多無(wú)人機(jī)系統(tǒng)存在的問(wèn)題。因此，F(xiàn)ANET已成為多無(wú)人機(jī)系統(tǒng)的主要通信架構(gòu)。

圖1 多無(wú)人機(jī)系統(tǒng)通信架構(gòu)

不同于其他自組網(wǎng)，F(xiàn)ANET 具有節(jié)點(diǎn)密度低、移動(dòng)性高、鏈路易中斷等特點(diǎn)，這對(duì)維持FANET的連通性提出了挑戰(zhàn)[18,22]。此外，F(xiàn)ANET 還需要滿足不同應(yīng)用場(chǎng)景下的性能需求。例如，在執(zhí)行災(zāi)后救援任務(wù)時(shí)，無(wú)人機(jī)需要將災(zāi)情信息實(shí)時(shí)傳輸給地面基礎(chǔ)設(shè)施，因此FANET 需要具有較低的通信時(shí)延[23]；在執(zhí)行數(shù)據(jù)收集任務(wù)時(shí)，為加快數(shù)據(jù)收集速度，F(xiàn)ANET 需要具有較高的吞吐量[24]。

根據(jù)FANET 的特點(diǎn)及需求，F(xiàn)ANET 拓?fù)淇刂仆ㄟ^(guò)構(gòu)建和調(diào)整FANET 拓?fù)浣Y(jié)構(gòu)，維持FANET的連通性，并提高FANET 的性能[25]。具體地，F(xiàn)ANET 拓?fù)淇刂扑惴ㄍㄟ^(guò)調(diào)整無(wú)人機(jī)的組網(wǎng)方式、位置、功率等參數(shù)來(lái)生成并動(dòng)態(tài)維護(hù)滿足特定約束且具有較優(yōu)性能的FANET 拓?fù)?。FANET 拓?fù)淇刂扑惴ň哂幸韵绿攸c(diǎn)：1) 在優(yōu)化變量方面，F(xiàn)ANET 拓?fù)淇刂苾?yōu)化的變量主要集中在無(wú)人機(jī)本身，例如，無(wú)人機(jī)之間的組網(wǎng)方式、無(wú)人機(jī)的位置和無(wú)人機(jī)的發(fā)送功率等；2) 在優(yōu)化目標(biāo)方面，F(xiàn)ANET 需要優(yōu)化的性能與其應(yīng)用場(chǎng)景有關(guān)。由于FANET 的應(yīng)用場(chǎng)景非常廣泛，通信性能（如吞吐量、時(shí)延、干擾等）、任務(wù)性能（如覆蓋率等）、能量消耗等均可能成為FANET 拓?fù)淇刂频膬?yōu)化目標(biāo)；3) 在執(zhí)行頻率方面，F(xiàn)ANET 中無(wú)人機(jī)具有高度的移動(dòng)特性，F(xiàn)ANET 拓?fù)淇刂菩枰哳l率動(dòng)態(tài)執(zhí)行。

目前，研究人員已經(jīng)開(kāi)發(fā)出多種FANET 拓?fù)淇刂扑惴?。然而，目前的FANET 綜述還沒(méi)有對(duì)FANET 拓?fù)淇刂扑惴ㄟM(jìn)行全面且詳細(xì)的分析。因此，本文對(duì)FANET 拓?fù)淇刂扑惴ㄟM(jìn)行了全面的綜述，梳理FANET 拓?fù)淇刂扑惴ǖ难芯克悸罚瑸镕ANET 拓?fù)淇刂扑惴ǖ氖褂门c開(kāi)發(fā)提供依據(jù)。本文的主要貢獻(xiàn)總結(jié)如下。

1) 介紹了FANET 的網(wǎng)絡(luò)架構(gòu)，給出了FANET拓?fù)淇刂频难芯靠蚣芎托枨蟆?/p>

2) 基于FANET 拓?fù)淇刂扑惴ㄟm用的網(wǎng)絡(luò)架構(gòu)，提出了一種FANET 拓?fù)淇刂扑惴ǖ姆诸惙椒ā８鶕?jù)每類FANET 拓?fù)淇刂扑惴ǖ奶赜袑傩?，?duì)每類FANET拓?fù)淇刂扑惴ㄟM(jìn)行了全面且詳細(xì)的分析，并通過(guò)對(duì)比總結(jié)了不同算法的特點(diǎn)和優(yōu)缺點(diǎn)，便于研究人員根據(jù)需求選擇合適的FANET 拓?fù)淇刂扑惴ㄒ约伴_(kāi)發(fā)新的FANET 拓?fù)淇刂扑惴ā?/p>

3) 討論了FANET 拓?fù)淇刂扑惴ㄈ悦媾R的挑戰(zhàn)以及未來(lái)的研究方向。

1 相關(guān)工作

本節(jié)梳理了與FANET 和拓?fù)淇刂苾纱笾黝}有關(guān)的綜述，并討論了本文與這些相關(guān)工作的不同之處，以凸顯本文的創(chuàng)新性。

一些文獻(xiàn)已經(jīng)從多個(gè)角度對(duì)FANET 的相關(guān)研究進(jìn)行了總結(jié)。文獻(xiàn)[18]是第一篇有關(guān)FANET 的綜述，它從應(yīng)用場(chǎng)景、設(shè)計(jì)特點(diǎn)、通信協(xié)議、測(cè)試方法等角度對(duì)FANET 進(jìn)行了綜述。文獻(xiàn)[26]總結(jié)了FANET 中的路由協(xié)議。文獻(xiàn)[27]專門(mén)總結(jié)了FANET 中基于集群的路由協(xié)議。文獻(xiàn)[19]總結(jié)了FANET 的特征，并圍繞路由、服務(wù)切換、能量等關(guān)鍵問(wèn)題對(duì)FANET 進(jìn)行了綜述。文獻(xiàn)[21-22,28-30]主要從FANET 特征、應(yīng)用場(chǎng)景、通信架構(gòu)、路由協(xié)議、移動(dòng)性模型和安全性等角度對(duì)FANET 進(jìn)行了全面的綜述。雖然這些文獻(xiàn)已經(jīng)對(duì)FANET 的相關(guān)研究進(jìn)行了全面的綜述，但是它們并沒(méi)有關(guān)注FANET 中的拓?fù)淇刂茊?wèn)題。本文主要對(duì)FANET 拓?fù)淇刂频南嚓P(guān)研究進(jìn)行綜述。

此外，一些文獻(xiàn)對(duì)無(wú)線傳感網(wǎng)（WSN,wireless sensor network）中的拓?fù)淇刂扑惴ㄟM(jìn)行了綜述。在WSN 中，拓?fù)淇刂浦饕ㄟ^(guò)調(diào)整節(jié)點(diǎn)的功率、狀態(tài)等來(lái)維持網(wǎng)絡(luò)連通性、增大網(wǎng)絡(luò)覆蓋范圍、延長(zhǎng)網(wǎng)絡(luò)壽命等。文獻(xiàn)[31]主要從功率調(diào)整、功率模式、聚類和混合4 個(gè)方面討論了WSN 中以節(jié)能為目標(biāo)的拓?fù)淇刂扑惴?。文獻(xiàn)[32]則通過(guò)覆蓋性和連通性2 個(gè)性能指標(biāo)對(duì)WSN 中的拓?fù)淇刂品椒ㄟM(jìn)行綜述。文獻(xiàn)[33]介紹了水下WSN 拓?fù)淇刂频奶匦?、潛力以及挑?zhàn)，并從功率控制、無(wú)線接口模式管理和移動(dòng)輔助3 個(gè)角度對(duì)其拓?fù)淇刂扑惴ㄟM(jìn)行綜述。然而，F(xiàn)ANET 與WSN 之間存在諸多不同，WSN 中的拓?fù)淇刂扑惴o(wú)法有效應(yīng)用于FANET。例如，切換節(jié)點(diǎn)狀態(tài)是WSN 中常用的拓?fù)淇刂萍夹g(shù)，而無(wú)人機(jī)停留在空中需要持續(xù)消耗能量，因此狀態(tài)切換技術(shù)不適用于FANET。

目前，有關(guān)FANET 拓?fù)淇刂频木C述還相對(duì)較少。文獻(xiàn)[34]主要總結(jié)了3 種基于虛擬力的FANET拓?fù)淇刂扑惴?，但?duì)目前已經(jīng)出現(xiàn)的大量其他種類的FANET 拓?fù)淇刂扑惴](méi)有系統(tǒng)分析。文獻(xiàn)[25]基于FANET 拓?fù)淇刂扑惴ǖ膱?zhí)行方式和數(shù)學(xué)模型對(duì)FANET 拓?fù)淇刂扑惴ㄟM(jìn)行了分類，并對(duì)FANET拓?fù)淇刂扑惴ㄟM(jìn)行了詳細(xì)的分析。然而，在文獻(xiàn)[25]提出的分類方法中，不同種類的算法之間區(qū)分不明顯，每種算法的特有屬性無(wú)法體現(xiàn)。此外，文獻(xiàn)[25]僅分析了部分具有代表性的FANET拓?fù)淇刂扑惴ǎ瑢?duì)現(xiàn)有FANET 拓?fù)淇刂扑惴ǖ木C述不夠全面。本文提出了一種全新的FANET 拓?fù)淇刂扑惴ǖ姆诸惙椒ǎ⒏鶕?jù)每一類算法的特有屬性，對(duì)現(xiàn)有FANET 拓?fù)淇刂扑惴ㄟM(jìn)行了全面的綜述。

2 飛行自組網(wǎng)拓?fù)淇刂聘攀?/h2>

2.1 飛行自組網(wǎng)架構(gòu)

本文將FANET 的架構(gòu)分為3 種：展平式FANET、基于連通支配集（CDS,connected dominating set）的FANET 和基于集群的FANET[35]，如圖2 所示。其中，基于CDS 的FANET 和基于集群的FANET 都屬于分層式FANET。

圖2 FANET 分類

在展平式FANET 中，所有無(wú)人機(jī)都具有相同的角色，各無(wú)人機(jī)在通信過(guò)程中地位平等。在分層式FANET 中，各無(wú)人機(jī)具有不同的角色。具體地，無(wú)人機(jī)可以分為領(lǐng)導(dǎo)者和跟隨者。其中，領(lǐng)導(dǎo)者充當(dāng)跟隨者的匯聚節(jié)點(diǎn)，負(fù)責(zé)將跟隨者發(fā)送的數(shù)據(jù)包轉(zhuǎn)發(fā)至目的地。相較于展平式FANET，分層式FANET 將大多數(shù)轉(zhuǎn)發(fā)操作集中到少量的領(lǐng)導(dǎo)者，在路由設(shè)計(jì)、可擴(kuò)展性、能量效率、時(shí)延等方面更具優(yōu)勢(shì)，因此被廣泛應(yīng)用于大規(guī)模無(wú)人機(jī)網(wǎng)絡(luò)。在基于CDS 的FANET 中，領(lǐng)導(dǎo)者是構(gòu)成CDS 的無(wú)人機(jī)節(jié)點(diǎn)，也被稱為支配節(jié)點(diǎn)，跟隨者是其余的無(wú)人機(jī)節(jié)點(diǎn)，也被稱為被支配節(jié)點(diǎn)。被支配節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時(shí)，會(huì)首先將數(shù)據(jù)包發(fā)送至其支配節(jié)點(diǎn)，然后由支配節(jié)點(diǎn)轉(zhuǎn)發(fā)至目的地。支配節(jié)點(diǎn)之間形成一個(gè)虛擬主干網(wǎng)絡(luò)，承載FANET 的主要流量。在基于集群的FANET 中，所有無(wú)人機(jī)被劃分為若干集群，每個(gè)集群由一個(gè)集群首領(lǐng)和若干集群成員組成。集群首領(lǐng)作為領(lǐng)導(dǎo)者，負(fù)責(zé)管理其集群內(nèi)部的通信。集群成員作為跟隨者，在與其他集群內(nèi)的無(wú)人機(jī)通信時(shí)會(huì)首先將數(shù)據(jù)包發(fā)送至其集群首領(lǐng)，然后由集群首領(lǐng)轉(zhuǎn)發(fā)至目的地。集群首領(lǐng)之間形成一個(gè)虛擬主干網(wǎng)絡(luò)，承載FANET 的主要流量?；贑DS 的FANET 和基于集群的FANET 的目的都是將大量的轉(zhuǎn)發(fā)操作集中于少量的領(lǐng)導(dǎo)者。然而，這兩者之間也存在若干不同：1) 在領(lǐng)導(dǎo)者選擇方面，基于CDS的FANET 的領(lǐng)導(dǎo)者是組成CDS 的支配節(jié)點(diǎn)，而基于集群的FANET的領(lǐng)導(dǎo)者是每個(gè)集群的集群首領(lǐng)；2) 在跟隨者管理方面，基于CDS 的FANET 中的支配節(jié)點(diǎn)負(fù)責(zé)管理其鄰居節(jié)點(diǎn)中的被支配節(jié)點(diǎn)，而基于集群的FANET 中的集群首領(lǐng)負(fù)責(zé)管理其所在集群內(nèi)的所有集群成員；3) 在領(lǐng)導(dǎo)者通信方面，基于CDS 的FANET 中的支配節(jié)點(diǎn)在給定無(wú)人機(jī)通信距離的情況下是連通的，而基于集群的FANET 一般不考慮集群首領(lǐng)的通信距離，默認(rèn)集群首領(lǐng)之間可以互相通信。

2.2 飛行自組網(wǎng)拓?fù)淇刂频难芯靠蚣芎托枨?/h3>

2.2.1研究框架

本文將FANET 拓?fù)淇刂蒲芯靠蚣芊譃槿剑耗Ｐ蜆?gòu)建、算法設(shè)計(jì)及效果評(píng)估，如圖3 所示。在模型構(gòu)建階段，需要根據(jù)FANET 的應(yīng)用場(chǎng)景，確定FANET 的架構(gòu)，設(shè)計(jì)拓?fù)淇刂扑惴ㄐ枰獫M足的約束、優(yōu)化的目標(biāo)以及可調(diào)整的參數(shù)。在算法設(shè)計(jì)階段，需要根據(jù)拓?fù)淇刂频膶?shí)施階段、約束、目標(biāo)以及可調(diào)整的參數(shù)，選擇合適的數(shù)學(xué)工具來(lái)設(shè)計(jì)相應(yīng)的拓?fù)淇刂扑惴ā８鶕?jù)拓?fù)淇刂扑惴ǖ膶?shí)施階段，F(xiàn)ANET 拓?fù)淇刂扑惴煞譃橥負(fù)錁?gòu)建算法和拓?fù)渚S護(hù)算法。其中，拓?fù)錁?gòu)建算法用于在沒(méi)有無(wú)人機(jī)初始位置、發(fā)送功率和連接關(guān)系的情況下，從零開(kāi)始構(gòu)建FANET 拓?fù)?；拓?fù)渚S護(hù)則用于在現(xiàn)有FANET 拓?fù)涞幕A(chǔ)上，通過(guò)調(diào)整相關(guān)變量，進(jìn)一步優(yōu)化FANET 拓?fù)洹Ｗ詈?，在效果評(píng)估階段，需要評(píng)估FANET 拓?fù)淇刂扑惴ǖ男阅埽⑦M(jìn)一步優(yōu)化FANET 拓?fù)淇刂扑惴ā?/p>

圖3 FANET 拓?fù)淇刂蒲芯靠蚣?/p>

2.2.2需求

本文將FANET 拓?fù)淇刂频男枨罂偨Y(jié)如下。

1) 連通性

在FANET 中，連通性指任意一對(duì)無(wú)人機(jī)之間以及任意一個(gè)無(wú)人機(jī)與基礎(chǔ)設(shè)施之間至少存在一條通信路徑。FANET 是一種為實(shí)現(xiàn)無(wú)人機(jī)之間以及無(wú)人機(jī)與基礎(chǔ)設(shè)施之間通信而設(shè)計(jì)的網(wǎng)絡(luò)架構(gòu)，因此連通性是FANET 拓?fù)淇刂谱罨镜囊蟆?/p>

2) 網(wǎng)絡(luò)性能

FANET 的網(wǎng)絡(luò)性能是指無(wú)人機(jī)之間以及無(wú)人機(jī)與地面基站等基礎(chǔ)設(shè)施之間通信的性能。FANET需要優(yōu)化的網(wǎng)絡(luò)性能與其應(yīng)用的場(chǎng)景有關(guān)，因此，F(xiàn)ANET 拓?fù)淇刂菩枰鶕?jù)FANET 的應(yīng)用場(chǎng)景設(shè)計(jì)合適的FANET 拓?fù)?，以滿足特定場(chǎng)景對(duì)FANET 的網(wǎng)絡(luò)性能要求。通常，F(xiàn)ANET 拓?fù)淇刂苾?yōu)化的網(wǎng)絡(luò)性能有鏈路時(shí)延、鏈路吞吐量、無(wú)人機(jī)之間的干擾、負(fù)載均衡等。

3) 任務(wù)性能

FANET 的任務(wù)性能是指各無(wú)人機(jī)執(zhí)行任務(wù)的性能。FANET 需要優(yōu)化的任務(wù)性能同樣與其應(yīng)用的場(chǎng)景有關(guān)，以FANET 輔助地面用戶通信為例，F(xiàn)ANET 拓?fù)淇刂苾?yōu)化的任務(wù)性能有地面用戶覆蓋率、總吞吐量、最小吞吐量等。

4) 容錯(cuò)性

FANET 在任務(wù)執(zhí)行期間可能會(huì)遇到無(wú)人機(jī)故障、障礙物、惡劣天氣等不確定性情況。因此，F(xiàn)ANET 拓?fù)淇刂菩枰O(shè)計(jì)具有容錯(cuò)性的FANET。一方面，在FANET 發(fā)生故障前，F(xiàn)ANET 拓?fù)淇刂瓶梢栽O(shè)計(jì)具有容錯(cuò)性的FANET 拓?fù)?，使FANET 在個(gè)別無(wú)人機(jī)發(fā)生故障后仍能正常運(yùn)行。例如，F(xiàn)ANET 拓?fù)淇刂瓶梢詷?gòu)建具有k（k≥ 2）連通性質(zhì)的FANET 拓?fù)?。另一方面，?dāng)FANET 發(fā)生故障后，F(xiàn)ANET 拓?fù)淇刂铺砑訜o(wú)人機(jī)以及調(diào)整無(wú)人機(jī)的位置恢復(fù)FANET 的正常運(yùn)行[36-37]。

5) 執(zhí)行頻率

FANET 中的無(wú)人機(jī)具有高移動(dòng)性的特點(diǎn)，無(wú)人機(jī)之間的相對(duì)位置頻繁變化。因此，F(xiàn)ANET 拓?fù)淇刂菩枰哳l率動(dòng)態(tài)更新FANET 拓?fù)洌跃S持FANET的性能。為了滿足FANET 拓?fù)淇刂苿?dòng)態(tài)執(zhí)行的需求，F(xiàn)ANET 拓?fù)淇刂菩枰谳^短時(shí)間內(nèi)完成。

6) 執(zhí)行方式

FANET 拓?fù)淇刂扑惴ǖ膱?zhí)行方式分為集中式執(zhí)行和分布式執(zhí)行2 種。其中，集中式執(zhí)行的FANET拓?fù)淇刂扑惴ㄐ枰芍醒肟刂茊卧袌?zhí)行。相比之下，分布式執(zhí)行的拓?fù)淇刂扑惴梢杂筛鳠o(wú)人機(jī)自主執(zhí)行，具有更小的通信開(kāi)銷，算法收斂速度更快，更適合于具有高移動(dòng)性特點(diǎn)的FANET。

7) 能量消耗

無(wú)人機(jī)的能量消耗由通信能量消耗和飛行能量消耗兩部分組成，其中飛行能量消耗遠(yuǎn)大于通信能量消耗，因此FANET 拓?fù)淇刂浦饕紤]無(wú)人機(jī)的飛行能量消耗。根據(jù)文獻(xiàn)[38]，假設(shè)無(wú)人機(jī)的飛行速度恒定為V，飛行時(shí)間為T(mén)，固定翼無(wú)人機(jī)的飛行能量消耗可以表示為

其中，a1和a2是與無(wú)人機(jī)的重量、機(jī)翼面積和空氣密度等因素有關(guān)的常量。旋翼無(wú)人機(jī)的飛行能量消耗可以表示為

其中，c1和c2是與無(wú)人機(jī)的重量、旋翼速度、旋翼盤(pán)面積、葉片角速度和空氣密度等因素有關(guān)的常數(shù)，q是旋翼葉尖速度，do是機(jī)身阻力比，vo是平均旋翼速度，ρ是空氣密度，s是旋翼密度，A是旋翼盤(pán)面積。由式(1)和式(2)可以看出，在無(wú)人機(jī)飛行速度恒定的情況下，無(wú)人機(jī)的飛行能量消耗主要與無(wú)人機(jī)的飛行時(shí)間有關(guān)，因此FANET 拓?fù)淇刂瓶梢酝ㄟ^(guò)減少無(wú)人機(jī)的飛行距離來(lái)減少飛行時(shí)間，從而減少飛行能量消耗。

2.3 飛行自組網(wǎng)拓?fù)淇刂扑惴ǖ姆诸?/h3>

根據(jù)2.1 節(jié)可知，不同種類的FANET 架構(gòu)具有不同的特點(diǎn)，其拓?fù)淇刂扑惴ㄋ鉀Q的問(wèn)題也有所不同。在展平式FANET 中，拓?fù)淇刂扑惴ㄖ饕鉀Q無(wú)人機(jī)數(shù)量、位置和發(fā)送功率的優(yōu)化問(wèn)題。在基于CDS 的FANET 中，拓?fù)淇刂扑惴ㄖ饕跓o(wú)人機(jī)位置確定的情況下解決CDS 的選擇和維護(hù)問(wèn)題。在基于集群的FANET 中，拓?fù)淇刂扑惴▌t主要解決集群劃分與維護(hù)以及集群首領(lǐng)的選擇與維護(hù)問(wèn)題。由于不同架構(gòu)FANET 中的拓?fù)淇刂扑惴ń鉀Q的問(wèn)題不同，其數(shù)學(xué)模型、原理和計(jì)算方法等也有所不同。因此，本文將FANET 拓?fù)淇刂扑惴ǚ譃? 類：展平式拓?fù)淇刂扑惴?、基于CDS的拓?fù)淇刂扑惴ê突诩旱耐負(fù)淇刂扑惴?，分別應(yīng)用于展平式FANET、基于CDS 的FANET 和基于集群的FANET。此外，本文單獨(dú)設(shè)置了一類基于虛擬力的拓?fù)淇刂扑惴?。該算法假設(shè)每個(gè)無(wú)人機(jī)節(jié)點(diǎn)都會(huì)受到來(lái)自其鄰居節(jié)點(diǎn)、障礙物、任務(wù)目標(biāo)等的虛擬力，每個(gè)無(wú)人機(jī)僅需要根據(jù)其受到的虛擬力的合力自主調(diào)整位置，既可用于展平式FANET，又可用于基于集群的FANET；既可用于FANET 的初始拓?fù)錁?gòu)建，又可用于FANET 的動(dòng)態(tài)拓?fù)渚S護(hù)。因此，基于虛擬力的拓?fù)淇刂扑惴▽?shí)際上可以歸入展平式拓?fù)淇刂扑惴ê突诩旱耐負(fù)淇刂扑惴?。然而，基于虛擬力的拓?fù)淇刂扑惴ㄊ褂昧伺c其他算法完全不同的拓?fù)淇刂品椒?，其分布式的?zhí)行特點(diǎn)非常適合用于控制自組織、高動(dòng)態(tài)的FANET。此外，基于虛擬力的拓?fù)淇刂扑惴ǖ脑O(shè)計(jì)思路簡(jiǎn)單，其吸引力可以確保FANET 的連通性，排斥力可以確保FANET 的覆蓋性，非常適合于在確保動(dòng)態(tài)FANET 連通的前提下覆蓋地面用戶。近年來(lái)，大量文獻(xiàn)使用基于虛擬力的拓?fù)淇刂扑惴▉?lái)滿足FANET 的連通和覆蓋需求?；谝陨咸攸c(diǎn)，本文將基于虛擬力的拓?fù)淇刂扑惴ㄔO(shè)置為單獨(dú)的類別，以便對(duì)此類算法感興趣的讀者對(duì)其有更清晰的認(rèn)識(shí)。由此，F(xiàn)ANET拓?fù)淇刂扑惴梢苑譃? 類，如表1 所示。后續(xù)章節(jié)將根據(jù)每一類拓?fù)淇刂扑惴ㄋ媾R的特定挑戰(zhàn)以及所使用的特定技術(shù)，對(duì)每一類拓?fù)淇刂扑惴ㄟM(jìn)行更細(xì)粒度的分析。

表1 FANET 拓?fù)淇刂扑惴ǚ诸惣皩?duì)比

3 飛行自組網(wǎng)拓?fù)淇刂扑惴ǚ治?/h2>

3.1 展平式拓?fù)淇刂扑惴?/h3>

展平式拓?fù)淇刂扑惴ǖ某Ｒ?jiàn)應(yīng)用場(chǎng)景有3 種，如圖4 所示。在場(chǎng)景1 中，任務(wù)無(wú)人機(jī)的位置由其執(zhí)行的任務(wù)確定，并且任務(wù)無(wú)人機(jī)需要與地面基站或其他任務(wù)無(wú)人機(jī)通信。拓?fù)錁?gòu)建算法通過(guò)求解中繼無(wú)人機(jī)的部署位置，在每個(gè)任務(wù)無(wú)人機(jī)與地面基站之間以及任務(wù)無(wú)人機(jī)之間建立多跳路徑，使每個(gè)任務(wù)無(wú)人機(jī)能夠與地面基站或其他任務(wù)無(wú)人機(jī)通信。在場(chǎng)景2 中，所有無(wú)人機(jī)均可以執(zhí)行偵察、通信覆蓋等任務(wù)或充當(dāng)其他無(wú)人機(jī)之間、無(wú)人機(jī)與地面基站之間通信的中繼。在這一場(chǎng)景中，拓?fù)淇刂扑惴ㄖ饕蠼飧鳠o(wú)人機(jī)的部署位置。一方面，拓?fù)淇刂扑惴ㄐ枰獌?yōu)化各無(wú)人機(jī)執(zhí)行任務(wù)的性能；另一方面，拓?fù)淇刂扑惴ㄐ枰诟鳠o(wú)人機(jī)之間、無(wú)人機(jī)與地面基站之間構(gòu)建多跳通信路徑，優(yōu)化FANET 的網(wǎng)絡(luò)性能。在場(chǎng)景3 中，所有無(wú)人機(jī)的位置已知，此時(shí)拓?fù)淇刂扑惴ㄖ饕ㄟ^(guò)求解無(wú)人機(jī)的發(fā)送功率來(lái)構(gòu)建和維護(hù)FANET 拓?fù)洹?/p>

圖4 展平式拓?fù)淇刂扑惴☉?yīng)用場(chǎng)景

根據(jù)算法的執(zhí)行階段，展平式拓?fù)淇刂扑惴梢赃M(jìn)一步分為2 類：展平式拓?fù)錁?gòu)建算法和展平式拓?fù)渚S護(hù)算法。

3.1.1展平式拓?fù)錁?gòu)建算法

展平式拓?fù)錁?gòu)建算法用于在沒(méi)有無(wú)人機(jī)初始位置、發(fā)送功率和連接關(guān)系等信息的情況下，從零開(kāi)始構(gòu)建展平式FANET 拓?fù)洹?/p>

為了減少場(chǎng)景1 中部署的中繼無(wú)人機(jī)的數(shù)量，文獻(xiàn)[39]介紹了3 種能夠求解中繼無(wú)人機(jī)位置的拓?fù)錁?gòu)建算法：多專用連接（MDC,multiple dedicated connection）算法、貪心算法和分布式自組織無(wú)人機(jī)（DSOD,distributed self-organized drone）算法。MDC算法在每個(gè)任務(wù)無(wú)人機(jī)與地面基站之間等距離地部署若干中繼無(wú)人機(jī)，使每個(gè)任務(wù)無(wú)人機(jī)通過(guò)專門(mén)的中繼無(wú)人機(jī)與地面基站通信。這一算法求得的中繼無(wú)人機(jī)數(shù)量較多且需要集中式執(zhí)行。貪心算法每次選擇距離已有通信路徑最近的未連通的任務(wù)無(wú)人機(jī)，并沿最短路徑部署若干中繼無(wú)人機(jī)，使該未連通的任務(wù)無(wú)人機(jī)能夠與地面基站通信。這一算法求得的無(wú)人機(jī)數(shù)量較少，但是仍需要集中式執(zhí)行。在DSOD 算法中，每個(gè)無(wú)人機(jī)自主決定是否需要額外的中繼無(wú)人機(jī)，并且中繼無(wú)人機(jī)根據(jù)其單跳鄰居信息自主調(diào)整位置以保持連接。此外，中繼無(wú)人機(jī)不斷與附近無(wú)人機(jī)進(jìn)行信息交換，以檢測(cè)是否存在冗余的中繼無(wú)人機(jī)。雖然DSOD 算法求得的無(wú)人機(jī)數(shù)量略高于貪心算法，但是DSOD 算法可以分布式執(zhí)行。為了最小化場(chǎng)景1 中繼無(wú)人機(jī)的數(shù)量，文獻(xiàn)[40]利用求和形式的失真函數(shù)來(lái)表示連通性約束，并用一個(gè)概率成本函數(shù)來(lái)表示容量約束，最終用確定性退火算法來(lái)以集中式的方式求解該問(wèn)題。實(shí)驗(yàn)結(jié)果表明，該算法求得的中繼無(wú)人機(jī)數(shù)量接近最優(yōu)。

此外，在場(chǎng)景1 中，一些文獻(xiàn)還考慮最大化FANET 的網(wǎng)絡(luò)性能。文獻(xiàn)[41-42]在使用罰函數(shù)法將約束優(yōu)化問(wèn)題轉(zhuǎn)換成無(wú)約束優(yōu)化問(wèn)題的基礎(chǔ)上，提出了一種基于粒子群優(yōu)化（PSO,particle swarm optimization）算法的集中式拓?fù)錁?gòu)建算法。實(shí)驗(yàn)結(jié)果表明，與隨機(jī)方案相比，該算法能夠顯著提高FANET的網(wǎng)絡(luò)性能。在場(chǎng)景1 的基礎(chǔ)上，文獻(xiàn)[43-44]均采用了軟件定義網(wǎng)絡(luò)（SDN,software defined network）架構(gòu)，并且都提出了基于PSO 算法的集中式拓?fù)錁?gòu)建算法。在考慮通信距離和安全距離等指標(biāo)的基礎(chǔ)上，文獻(xiàn)[43]考慮了任務(wù)無(wú)人機(jī)之間的路由數(shù)量、路由跳數(shù)、路由距離等指標(biāo)，文獻(xiàn)[44]考慮了連通節(jié)點(diǎn)對(duì)數(shù)量、可替換路由、故障點(diǎn)、橋接鏈路等指標(biāo)，進(jìn)一步優(yōu)化了FANET 的通信性能。

在場(chǎng)景2 中，很多文獻(xiàn)考慮在保證FAENET 連通性的情況下，最大化FANET 的任務(wù)性能。在FANET 為地面用戶提供通信服務(wù)的場(chǎng)景中，為了最大化地面用戶的總吞吐量，文獻(xiàn)[45]將這一問(wèn)題建模為連接最大吞吐量問(wèn)題，并提出了一種具有性能保證的近似算法來(lái)求解地面用戶的接入選擇和各無(wú)人機(jī)的部署位置。文獻(xiàn)[46]則將這一問(wèn)題建模為混合合作競(jìng)爭(zhēng)博弈模型，并提出了一種多智能體深度強(qiáng)化學(xué)習(xí)（MADRL,multi-agent deep reinforcement learning）算法來(lái)求解地面用戶的接入策略和各無(wú)人機(jī)的軌跡。文獻(xiàn)[47]研究了如何在地面用戶概率密度已知的情況下最小化無(wú)人機(jī)與地面用戶之間的平均距離，首先提出了一種用于視距通信場(chǎng)景的分布式部署算法來(lái)控制無(wú)人機(jī)移動(dòng)，隨后討論了如何在非視距通信場(chǎng)景中使用該算法。文獻(xiàn)[48]首先設(shè)計(jì)了一種改進(jìn)的遺傳算法以使用最少數(shù)量的無(wú)人機(jī)為地面用戶提供覆蓋，隨后提出了一種無(wú)人機(jī)重新部署算法以最大程度增加覆蓋用戶的數(shù)量。文獻(xiàn)[49]提出了一種MADRL 算法來(lái)控制無(wú)人機(jī)移動(dòng)，從而同時(shí)最大化平均覆蓋率，最大化覆蓋公平性，最小化無(wú)人機(jī)能耗，并保持多無(wú)人機(jī)網(wǎng)絡(luò)的連通性。

在場(chǎng)景3 中，文獻(xiàn)[50]提出了一種基于關(guān)節(jié)點(diǎn)的離散PSO 算法（AP-DPSO,discrete PSO with articulation point），以構(gòu)建魯棒性高、干擾低以及無(wú)人機(jī)之間鏈路短的FANET 拓?fù)?。為了減少通信開(kāi)銷并實(shí)現(xiàn)分布式控制，該算法首先通過(guò)尋找網(wǎng)絡(luò)中的割點(diǎn)將網(wǎng)絡(luò)劃分為多個(gè)子網(wǎng)絡(luò)。隨后，子網(wǎng)絡(luò)的局部拓?fù)淇刂茊?wèn)題被表述為受度數(shù)約束的最小生成樹(shù)問(wèn)題，對(duì)于該問(wèn)題，每個(gè)無(wú)人機(jī)收集本地拓?fù)湫畔⒉⑹褂秒x散PSO 算法求解自身發(fā)送功率。

展平式拓?fù)錁?gòu)建算法僅用于構(gòu)建初始的FANET 拓?fù)?，因此，此類算法的主要目?biāo)是構(gòu)建可行有效的FANET 拓?fù)?，而不需要過(guò)分關(guān)注算法的執(zhí)行時(shí)間和執(zhí)行方式。由于無(wú)人機(jī)的初始位置、發(fā)送功率和連接關(guān)系等信息未知，展平式拓?fù)錁?gòu)建問(wèn)題通常被構(gòu)建為非凸優(yōu)化問(wèn)題。因此，大多數(shù)展平式拓?fù)錁?gòu)建算法基于啟發(fā)式算法、智能優(yōu)化算法等設(shè)計(jì)。表2 展示了展平式拓?fù)淇刂扑惴ǖ谋容^結(jié)果。

表2 展平式拓?fù)淇刂扑惴ǖ谋容^結(jié)果

展平式拓?fù)錁?gòu)建算法大多在中央控制器中執(zhí)行。在中央控制器中，展平式拓?fù)錁?gòu)建算法可以根據(jù)全局信息來(lái)計(jì)算展平式FANET 的拓?fù)?，并且各無(wú)人機(jī)只需要根據(jù)中央控制器的計(jì)算結(jié)果來(lái)完成FANET 構(gòu)建。因此，展平式拓?fù)錁?gòu)建算法設(shè)計(jì)相對(duì)簡(jiǎn)單，容易執(zhí)行。綜上所述，展平式拓?fù)錁?gòu)建算法主要適用于系統(tǒng)中存在中央控制器的情況下構(gòu)建展平式FANET。當(dāng)各無(wú)人機(jī)分配的資源固定時(shí)（如無(wú)人機(jī)的發(fā)送功率無(wú)法改變），可以設(shè)計(jì)展平式拓?fù)錁?gòu)建算法來(lái)求解各無(wú)人機(jī)的部署位置，進(jìn)而構(gòu)建初始的展平式FANET。當(dāng)各無(wú)人機(jī)的位置固定時(shí)（如無(wú)人機(jī)的位置完全由其執(zhí)行的任務(wù)決定），可以設(shè)計(jì)展平式拓?fù)錁?gòu)建算法來(lái)求解各無(wú)人機(jī)的發(fā)送功率，從而實(shí)現(xiàn)展平式FANET 的構(gòu)建。

在優(yōu)化目標(biāo)方面，現(xiàn)有的文獻(xiàn)大多單方面優(yōu)化無(wú)人機(jī)的數(shù)量、FANET 的任務(wù)性能或FANET 的網(wǎng)絡(luò)性能等。在實(shí)際的FANET 應(yīng)用場(chǎng)景中，F(xiàn)ANET 的若干性能需要同時(shí)優(yōu)化。然而，不同的優(yōu)化目標(biāo)之間存在一定矛盾。例如，優(yōu)化FANET 的任務(wù)性能會(huì)降低其網(wǎng)絡(luò)性能，而優(yōu)化FANET 的網(wǎng)絡(luò)性能則會(huì)降低其任務(wù)性能[34,51]。如何均衡優(yōu)化FANET 的各項(xiàng)性能有待進(jìn)一步研究。一種簡(jiǎn)單的解決思路是根據(jù)實(shí)際需求給各優(yōu)化目標(biāo)設(shè)置不同的權(quán)值，并將各優(yōu)化目標(biāo)的加權(quán)和作為設(shè)計(jì)展平式拓?fù)錁?gòu)建算法的總目標(biāo)。

此外，在優(yōu)化變量方面，無(wú)人機(jī)的位置、功率和分配帶寬等均可影響FANET 的性能。由于各優(yōu)化變量之間相互耦合，一個(gè)變量的變化可能會(huì)影響另一個(gè)變量的優(yōu)化，因此同時(shí)優(yōu)化多個(gè)變量具有較高的復(fù)雜度。為此，可以采用交替優(yōu)化的方法來(lái)交替優(yōu)化各個(gè)變量，并在多次迭代之后求得最終結(jié)果。

3.1.2展平式拓?fù)渚S護(hù)算法

FANET 在執(zhí)行任務(wù)的過(guò)程中，其無(wú)人機(jī)的位置會(huì)根據(jù)需要?jiǎng)討B(tài)變化。為了維持FANET 的性能，F(xiàn)ANET 的拓?fù)浣Y(jié)構(gòu)也需做出相應(yīng)調(diào)整。展平式拓?fù)渚S護(hù)算法主要用于在現(xiàn)有FANET 拓?fù)涞幕A(chǔ)上，通過(guò)調(diào)整相關(guān)變量，更新FANET 拓?fù)?，從而?yōu)化FANET 的性能。

一部分展平式拓?fù)渚S護(hù)算法通過(guò)調(diào)整無(wú)人機(jī)的位置來(lái)更新FANET 拓?fù)?，如圖5(a)所示。當(dāng)任務(wù)無(wú)人機(jī)的位置發(fā)生變化時(shí)，文獻(xiàn)[42]算法3、文獻(xiàn)[51]算法2 和文獻(xiàn)[43]算法2 根據(jù)每個(gè)中繼無(wú)人機(jī)的單跳鄰居信息，使用梯度法來(lái)分布式地調(diào)整每個(gè)中繼無(wú)人機(jī)的位置，從而維持任務(wù)無(wú)人機(jī)與地面基站之間的通信性能。為了在任務(wù)無(wú)人機(jī)的位置發(fā)生變化時(shí)保證任務(wù)無(wú)人機(jī)之間的k連通性并且最小化中繼無(wú)人機(jī)的移動(dòng)距離，文獻(xiàn)[52]首先使用steinerization 方法求出中繼無(wú)人機(jī)的候選部署位置，隨后使用完全二部圖來(lái)表示中繼無(wú)人機(jī)與中繼無(wú)人機(jī)候選部署位置之間的關(guān)系，并根據(jù)中繼無(wú)人機(jī)的當(dāng)前位置與中繼無(wú)人機(jī)的候選部署位置設(shè)置邊的權(quán)重，最后使用Kuhn-Munkres 算法確定該加權(quán)二部圖上的最大加權(quán)匹配，求得每個(gè)中繼無(wú)人機(jī)的部署位置。該算法需要所有無(wú)人機(jī)的位置信息，因此需要集中式執(zhí)行。為了增大FANET 的吞吐量，文獻(xiàn)[24]算法3 在利用罰函數(shù)法將網(wǎng)絡(luò)連通性、無(wú)人機(jī)安全距離、無(wú)人機(jī)單位時(shí)間內(nèi)移動(dòng)的最大距離等約束轉(zhuǎn)化為優(yōu)化目標(biāo)的基礎(chǔ)上，基于PSO 算法來(lái)集中式地求解無(wú)人機(jī)在下一時(shí)刻的位置。

圖5 展平式拓?fù)渚S護(hù)算法

此外，基于功率的拓?fù)渚S護(hù)算法通過(guò)調(diào)整無(wú)人機(jī)的發(fā)送功率來(lái)改變無(wú)人機(jī)的通信范圍，從而更新FANET 拓?fù)洌鐖D5(b)所示。在不具有2-連通性質(zhì)的初始FANET 拓?fù)渖?，局部拓?fù)涔β士刂疲↙TPC,localized topology power control）算法[53]將初始拓?fù)滢D(zhuǎn)化成塊割樹(shù)，并不斷添加長(zhǎng)度最短的邊，最終生成具有2-連通性質(zhì)的FANET 拓?fù)?。在假設(shè)初始FANET 拓?fù)渚哂衚（k≥ 3）連通性質(zhì)，并且所有無(wú)人機(jī)發(fā)送功率相同的基礎(chǔ)上，文獻(xiàn)[24]算法1 采用了一種循環(huán)剪枝機(jī)制，不斷刪除當(dāng)前拓?fù)渲虚L(zhǎng)度最長(zhǎng)的邊，直到生成的拓?fù)渚哂?-連通性質(zhì)，從而求得能夠使FANET 拓?fù)渚哂?-連通性質(zhì)的無(wú)人機(jī)最小發(fā)送功率?？紤]到FANET 的拓?fù)溥B通性、平均傳輸時(shí)延與鏈路損耗，文獻(xiàn)[17]提出了一種基于聯(lián)盟圖博弈的自適應(yīng)拓?fù)淇刂扑惴ǎㄟ^(guò)輪轉(zhuǎn)互操作在不具有2-連通性質(zhì)的初始FANET 拓?fù)渖咸砑舆?，最終實(shí)現(xiàn)拓?fù)溥B通性、平均傳輸時(shí)延與鏈路損耗3 種性能之間的權(quán)衡優(yōu)化。

展平式拓?fù)渚S護(hù)算法主要用于當(dāng)無(wú)人機(jī)位置發(fā)生變化時(shí)，通過(guò)在現(xiàn)有FANET 的基礎(chǔ)上調(diào)整無(wú)人機(jī)的位置或發(fā)送功率，動(dòng)態(tài)更新FANET 拓?fù)?，從而?yōu)化FANET 的性能。具體地，基于位置的拓?fù)渚S護(hù)算法在保持無(wú)人機(jī)發(fā)送功率不變的情況下調(diào)整無(wú)人機(jī)的位置，基于功率的拓?fù)渚S護(hù)算法則在保持無(wú)人機(jī)位置不變的情況下調(diào)整無(wú)人機(jī)的發(fā)送功率。由于展平式拓?fù)渚S護(hù)算法需要高頻率動(dòng)態(tài)運(yùn)行，算法的收斂速度、執(zhí)行方式等都是影響展平式拓?fù)渚S護(hù)算法性能的重要因素。在算法收斂速度方面，啟發(fā)式算法和以梯度法為代表的凸優(yōu)化算法具有較快的算法收斂速度，可以滿足展平式拓?fù)渚S護(hù)算法的需求。與之相比，博弈論算法以及智能優(yōu)化算法等需要通過(guò)多次迭代才能求得最終解，具有較慢的算法收斂速度。在執(zhí)行方式方面，集中式的展平式拓?fù)渚S護(hù)算法需要周期性執(zhí)行，從而周期性地優(yōu)化FANET 的性能。與之相比，分布式的展平式拓?fù)渚S護(hù)算法根據(jù)外部環(huán)境的變化實(shí)時(shí)調(diào)整無(wú)人機(jī)的位置、發(fā)送功率等，從而實(shí)時(shí)維護(hù)FANET 的性能。

展平式拓?fù)渚S護(hù)算法主要適用于在保證當(dāng)前展平式FAENT 服務(wù)盡可能不中斷的情況下，調(diào)整現(xiàn)有的展平式FANET 并提高其性能。當(dāng)系統(tǒng)中存在中央控制器時(shí)（如FANET 采用SDN 架構(gòu)），可以設(shè)計(jì)集中式的展平式拓?fù)渚S護(hù)算法或重新執(zhí)行展平式拓?fù)錁?gòu)建算法，并根據(jù)全局信息調(diào)整展平式FANET 拓?fù)洌@得更優(yōu)的性能。當(dāng)系統(tǒng)中不存在中央控制器時(shí)，需要設(shè)計(jì)分布式的展平式拓?fù)渚S護(hù)算法，使各無(wú)人機(jī)僅根據(jù)其局部信息來(lái)調(diào)整展平式FANET 拓?fù)?。此外，?dāng)各無(wú)人機(jī)分配的資源固定時(shí)（如無(wú)人機(jī)的發(fā)送功率無(wú)法改變），可以設(shè)計(jì)展平式拓?fù)渚S護(hù)算法來(lái)調(diào)整各無(wú)人機(jī)的部署位置，進(jìn)而維護(hù)展平式FANET。當(dāng)各無(wú)人機(jī)的位置由其執(zhí)行的任務(wù)等因素決定時(shí)，則可以設(shè)計(jì)展平式拓?fù)渚S護(hù)算法來(lái)調(diào)整各無(wú)人機(jī)的發(fā)送功率，從而維護(hù)展平式FANET。

現(xiàn)有的文獻(xiàn)大多以集中式的方式實(shí)現(xiàn)展平式FANET 的拓?fù)渚S護(hù)，無(wú)法實(shí)時(shí)維護(hù)FANET 的性能。因此，如何以分布式的方式優(yōu)化FANET 的性能有待進(jìn)一步研究。為此，可以考慮各無(wú)人機(jī)在維持已有通信鏈路的基礎(chǔ)上，分布式調(diào)整其位置或發(fā)送功率，從而優(yōu)化展平式FANET 的性能。

此外，現(xiàn)有文獻(xiàn)大多在外界環(huán)境變化之后進(jìn)行展平式FANET 的拓?fù)渚S護(hù)，具有一定的滯后性。為解決這一問(wèn)題，可以考慮預(yù)測(cè)外界環(huán)境的變化（例如，在FANET 為地面用戶提供通信服務(wù)的場(chǎng)景中預(yù)測(cè)地面用戶的位置變化情況），并根據(jù)預(yù)測(cè)的外界環(huán)境的變化情況來(lái)維護(hù)展平式FANET 拓?fù)鋄54]。

3.2 基于CDS 的拓?fù)淇刂扑惴?/h3>

基于CDS 的拓?fù)淇刂扑惴ㄖ饕跓o(wú)人機(jī)位置已知的情況下構(gòu)建和維護(hù)CDS 來(lái)實(shí)現(xiàn)對(duì)FANET 的拓?fù)淇刂?，其?yīng)用場(chǎng)景如圖6 所示。例如，當(dāng)多無(wú)人機(jī)在執(zhí)行野火監(jiān)控、信息采集、野外救援等任務(wù)時(shí)，各無(wú)人機(jī)的位置由其執(zhí)行的任務(wù)而決定。此時(shí)，基于CDS 的拓?fù)淇刂扑惴ㄍㄟ^(guò)構(gòu)建和維護(hù)CDS，將絕大多數(shù)轉(zhuǎn)發(fā)操作集中于少量的支配節(jié)點(diǎn)，從而完成FANET 拓?fù)淇刂啤?/p>

圖6 基于CDS 的拓?fù)淇刂扑惴ǖ膽?yīng)用場(chǎng)景

根據(jù)算法的執(zhí)行階段，基于CDS 的拓?fù)淇刂扑惴梢苑譃? 類：CDS 構(gòu)建算法和CDS 維護(hù)算法。

3.2.1CDS 構(gòu)建算法

CDS 構(gòu)建算法主要用于在FANET 中構(gòu)建初始的CDS。由于CDS 的構(gòu)建問(wèn)題是一個(gè)NP 完全問(wèn)題，現(xiàn)有CDS 構(gòu)建算法大多采用啟發(fā)式或近似的方法來(lái)構(gòu)建基于CDS 的FANET。

在啟發(fā)式算法方面，文獻(xiàn)[24]算法2 首先基于最小生成樹(shù)算法生成CDS 候選集，然后基于頁(yè)面排名算法來(lái)構(gòu)建最小CDS。文獻(xiàn)[55]算法1 基于最小生成樹(shù)算法生成CDS 候選集，并將具有最大能量的CDS 作為初始的CDS。

在近似算法方面，文獻(xiàn)[56]提出了3 種具有多項(xiàng)式時(shí)間復(fù)雜度的近似CDS 構(gòu)建算法，其中，前2 種算法用于一般圖，后一種算法用于有界度圖?？紤]到FANET 的拓?fù)渥儞Q頻繁，文獻(xiàn)[57]認(rèn)為FANET中CDS 形成的虛擬主干網(wǎng)絡(luò)需要具備一定的容錯(cuò)能力。為此，文獻(xiàn)[57]提出了一種分布式k連通支配集（DKCDS,distributedkCDS）算法，該算法首先構(gòu)建CDS，隨后根據(jù)最大獨(dú)立集理論構(gòu)建k連通支配集。

實(shí)際上，由于CDS 構(gòu)建算法難以優(yōu)化FANET的任務(wù)性能和網(wǎng)絡(luò)性能，CDS 構(gòu)建算法在FANET的應(yīng)用相對(duì)較少，而在WSN[58-59]、移動(dòng)自組網(wǎng)（MANET,mobile ad-hoc network）[60]、車輛自組網(wǎng)（VANET,vehicle ad-hoc network）[61-62]等無(wú)線網(wǎng)絡(luò)中已經(jīng)得到了廣泛的應(yīng)用。這些算法可以較容易地移植到FANET 當(dāng)中，感興趣的讀者可以查閱相關(guān)文獻(xiàn)，以便更好地理解CDS 構(gòu)建算法。

在FANET 中構(gòu)建CDS 的主要目的是將大多數(shù)轉(zhuǎn)發(fā)操作集中到少量支配節(jié)點(diǎn)，從而簡(jiǎn)化FANET的路由問(wèn)題。支配節(jié)點(diǎn)的數(shù)量越少，轉(zhuǎn)發(fā)操作越集中，F(xiàn)ANET 的路由越簡(jiǎn)單。考慮到FANET 的不確定性，構(gòu)建具有容錯(cuò)性的CDS 能夠確保FANET 在其中個(gè)別無(wú)人機(jī)節(jié)點(diǎn)發(fā)生故障后仍能正常運(yùn)行。此外，考慮到支配無(wú)人機(jī)節(jié)點(diǎn)承載的轉(zhuǎn)發(fā)任務(wù)更多，其能量消耗更快。因此，使用能量最大的CDS 作為初始CDS 可以延長(zhǎng)FANET 的生存時(shí)間。從算法設(shè)計(jì)、通信復(fù)雜度和時(shí)間復(fù)雜度等角度來(lái)看，啟發(fā)式CDS 構(gòu)建算法的設(shè)計(jì)相對(duì)容易，但其無(wú)法提供算法通信和時(shí)間復(fù)雜度的理論保證。與啟發(fā)式算法相比，近似算法可以提供算法通信和時(shí)間復(fù)雜度的理論保證，但其設(shè)計(jì)難度較高。表3 展示了基于CDS的拓?fù)淇刂扑惴ǖ谋容^結(jié)果。

表3 基于CDS 的拓?fù)淇刂扑惴ǖ谋容^結(jié)果

根據(jù)CDS 構(gòu)建算法的特點(diǎn)，CDS 構(gòu)建算法主要適用于在執(zhí)行大規(guī)模數(shù)據(jù)傳輸任務(wù)的FANET（如利用FANET 從地面物聯(lián)網(wǎng)設(shè)備收集數(shù)據(jù)）中構(gòu)建CDS，從而提高FANET 的傳輸效率。目前的CDS構(gòu)建算法大多采用了集中式的構(gòu)建方法，其中，啟發(fā)式的CDS 構(gòu)建算法設(shè)計(jì)簡(jiǎn)單，易于理解，因此適合對(duì)相關(guān)數(shù)學(xué)理論研究不太深入的初級(jí)研究者設(shè)計(jì)。近似CDS 構(gòu)建算法設(shè)計(jì)復(fù)雜，但能提供性能的理論保證，適合對(duì)相關(guān)數(shù)學(xué)理論研究較為深入的高級(jí)研究者設(shè)計(jì)。

CDS 構(gòu)建算法構(gòu)建的CDS 將大多數(shù)轉(zhuǎn)發(fā)操作集中到少量的支配節(jié)點(diǎn)，支配節(jié)點(diǎn)的能量消耗明顯高于被支配節(jié)點(diǎn)。為此，在設(shè)計(jì)CDS 構(gòu)建算法時(shí)需要考慮無(wú)人機(jī)的能量消耗問(wèn)題，從而延長(zhǎng)FANET的生存時(shí)間。一種可能的解決思路是將無(wú)人機(jī)的剩余能量作為評(píng)價(jià)無(wú)人機(jī)重要性的指標(biāo)之一，并設(shè)計(jì)算法使重要性高的無(wú)人機(jī)成為支配節(jié)點(diǎn)的可能性更高。此外，現(xiàn)有的CDS 構(gòu)建算法在構(gòu)建CDS 時(shí)大多沒(méi)有考慮端到端時(shí)延、丟包率等傳統(tǒng)網(wǎng)絡(luò)性能。為此，可以考慮將鏈路的網(wǎng)絡(luò)性能作為鏈路的權(quán)重，并設(shè)計(jì)算法構(gòu)建鏈路總權(quán)重較低的CDS。

此外，現(xiàn)有的CDS 構(gòu)建算法大多在無(wú)人機(jī)位置、功率等固定的基礎(chǔ)上構(gòu)建CDS?？梢钥紤]將調(diào)整無(wú)人機(jī)的位置、功率等與CDS 構(gòu)建結(jié)合起來(lái)，在滿足FANET 任務(wù)性能約束的情況下，進(jìn)一步優(yōu)化FANET 的網(wǎng)絡(luò)性能。

3.2.2CDS 維護(hù)算法

由于FANET 的高度動(dòng)態(tài)性，CDS 構(gòu)建算法構(gòu)建的CDS 無(wú)法保證永久有效。此時(shí)，如果使用CDS構(gòu)建算法重構(gòu)CDS，可能會(huì)產(chǎn)生較高的拓?fù)淇刂瞥杀尽Ｔ谶@一背景下，CDS 維護(hù)算法主要用于動(dòng)態(tài)更新FANET 中的CDS，最小化CDS 更新的成本。

文獻(xiàn)[55]算法2 在使用基于最小生成樹(shù)的啟發(fā)式CDS 構(gòu)建算法生成CDS 候選集的基礎(chǔ)上，使用馬爾可夫模型預(yù)測(cè)即將斷開(kāi)的鏈路，并在CDS 候選集中找到一個(gè)與當(dāng)前CDS 最相似的CDS 作為下一時(shí)刻的CDS。文獻(xiàn)[63]考慮了一種特殊的CDS 維護(hù)場(chǎng)景。在該場(chǎng)景中，部分無(wú)人機(jī)會(huì)根據(jù)任務(wù)需要而改變自己的位置，其他無(wú)人機(jī)通過(guò)調(diào)整位置來(lái)實(shí)現(xiàn)CDS 維護(hù)。此外，一些無(wú)人機(jī)節(jié)點(diǎn)（如網(wǎng)關(guān)無(wú)人機(jī)）需要始終作為CDS 中的支配節(jié)點(diǎn)。為了解決該問(wèn)題，文獻(xiàn)[63]首先提出了一種啟發(fā)式方法來(lái)確定需要移動(dòng)的無(wú)人機(jī)節(jié)點(diǎn)，隨后采用了一種級(jí)聯(lián)方法來(lái)確定無(wú)人機(jī)節(jié)點(diǎn)的移動(dòng)位置。

文獻(xiàn)[64]提出了一種近似自適應(yīng)最小d連通支配集（AMDC,adaptive minimaldCDS）算法，用于動(dòng)態(tài)維護(hù)FANET 中的d跳CDS。該算法首先使用一種近似算法來(lái)維持最小d跳支配集，然后加入額外的節(jié)點(diǎn)來(lái)連接得到的d跳支配集以形成d跳CDS，最后使用頂樹(shù)數(shù)據(jù)結(jié)構(gòu)求得最小d跳CDS。

在優(yōu)化目標(biāo)方面，更新節(jié)點(diǎn)數(shù)量可以反映算法的通信開(kāi)銷，因此CDS 維護(hù)算法可通過(guò)最小化更新節(jié)點(diǎn)的數(shù)量來(lái)最小化通信開(kāi)銷。此外，當(dāng)CDS維護(hù)算法通過(guò)調(diào)整無(wú)人機(jī)位置來(lái)維護(hù)CDS 時(shí)，CDS維護(hù)算法可以通過(guò)最小化無(wú)人機(jī)的移動(dòng)距離，以盡快完成拓?fù)渚S護(hù)并減少無(wú)人機(jī)的能量消耗。在執(zhí)行方式方面，分布式的執(zhí)行方式更適合于CDS 維護(hù)算法，但分布式CDS 維護(hù)算法具有較高的通信開(kāi)銷。

CDS 維護(hù)算法主要適用于在保證當(dāng)前基于CDS 的FAENT 服務(wù)盡可能不中斷的情況下，維護(hù)FANET 中的CDS 并提高其性能。當(dāng)系統(tǒng)中存在中央控制器時(shí)（如FANET 采用SDN 架構(gòu)），可以設(shè)計(jì)集中式的CDS 維護(hù)算法或者重新執(zhí)行CDS 構(gòu)建算法，根據(jù)全局信息維護(hù)CDS，降低實(shí)現(xiàn)難度。當(dāng)系統(tǒng)中不存在中央控制器時(shí)，需要設(shè)計(jì)分布式的CDS 維護(hù)算法，使各無(wú)人機(jī)僅根據(jù)其局部信息來(lái)維護(hù)CDS。

大多CDS 維護(hù)算法采用集中式的方法來(lái)實(shí)現(xiàn)CDS 維護(hù)，這不適用于無(wú)人機(jī)位置動(dòng)態(tài)變化的FANET。少量CDS 維護(hù)算法雖然采用了分布式實(shí)現(xiàn)方式，但具有較高的通信開(kāi)銷。以上問(wèn)題也導(dǎo)致CDS 維護(hù)算法目前在FANET 中應(yīng)用較少。在未來(lái)，如何設(shè)計(jì)具有較低通信開(kāi)銷的分布式CDS 維護(hù)算法有待進(jìn)一步研究，且具有一定難度。對(duì)于這一問(wèn)題，可以考慮令各無(wú)人機(jī)分布式地調(diào)整各自的位置、功率等，從而維持已有的CDS 并優(yōu)化FANET的性能。

此外，基于CDS 的FANET 中的支配節(jié)點(diǎn)具有較高的重要性。支配節(jié)點(diǎn)一旦損壞，整個(gè)FANET將無(wú)法繼續(xù)運(yùn)行。為此，需要考慮如何在支配節(jié)點(diǎn)損壞后快速形成新的CDS。一種可能的解決思路是給各支配節(jié)點(diǎn)選擇備份節(jié)點(diǎn)，在支配節(jié)點(diǎn)故障后令備份節(jié)點(diǎn)代替故障的支配節(jié)點(diǎn)成為新的支配節(jié)點(diǎn)。

3.3 基于集群的拓?fù)淇刂扑惴?/h3>

基于集群的拓?fù)淇刂扑惴ㄖ饕跓o(wú)人機(jī)位置已知的情況下通過(guò)集群劃分和首領(lǐng)選擇來(lái)實(shí)現(xiàn)對(duì)FANET 的拓?fù)淇刂?，其?yīng)用場(chǎng)景如圖7 所示?；诩旱耐?fù)淇刂扑惴ㄅc基于CDS 的拓?fù)淇刂扑惴ǖ膽?yīng)用場(chǎng)景較類似，但其構(gòu)建出的基于集群的FANET 與基于CDS 的FANET 具有不同的特點(diǎn)（詳見(jiàn)2.1 節(jié)）。

圖7 基于集群的拓?fù)淇刂扑惴ǖ膽?yīng)用場(chǎng)景

根據(jù)算法的執(zhí)行階段，本文將基于集群的拓?fù)淇刂扑惴ǚ譃榧簶?gòu)建算法和集群維護(hù)算法。其中，集群構(gòu)建算法負(fù)責(zé)進(jìn)行集群劃分和集群首領(lǐng)選擇，從而形成初始的FANET 拓?fù)?；集群維護(hù)算法則通過(guò)更新集群首領(lǐng)以及集群成員來(lái)維護(hù)FANET 拓?fù)洹?/p>

3.3.1集群構(gòu)建算法

文獻(xiàn)[65]提出了一種集群控制方法來(lái)應(yīng)對(duì)FANET 中無(wú)人機(jī)高移動(dòng)性帶來(lái)的挑戰(zhàn)。在集群劃分和首領(lǐng)選擇方面，該方法首先根據(jù)FANET 執(zhí)行的任務(wù)確定最佳集群數(shù)量，隨后使用k均值算法將所有無(wú)人機(jī)劃分為k個(gè)集群，并選擇每個(gè)集群的中心無(wú)人機(jī)作為集群首領(lǐng)。

文獻(xiàn)[66]使用集群控制方法來(lái)解決FANET 中無(wú)人機(jī)能量有限和高移動(dòng)性問(wèn)題。在集群劃分方面，該方法首先通過(guò)暴力求解法求得最佳集群數(shù)量，隨后使用k均值算法將FANET 中的無(wú)人機(jī)聚類為k個(gè)集群。在首領(lǐng)選擇方面，每個(gè)集群中適應(yīng)度最高的無(wú)人機(jī)被選為集群首領(lǐng)，以延長(zhǎng)集群壽命并平衡網(wǎng)絡(luò)流量。適應(yīng)度計(jì)算式為

其中，EnergyResidual表示無(wú)人機(jī)的剩余能量，dist 表示無(wú)人機(jī)與集群內(nèi)其他無(wú)人機(jī)的距離之和，Ddiff用于平衡集群之間的負(fù)載，w1、w2和w3表示各變量所占的權(quán)重。

文獻(xiàn)[67]提出了一種集群控制方法來(lái)解決FANET 中的無(wú)人機(jī)高移動(dòng)性和拓?fù)鋭?dòng)態(tài)變化問(wèn)題。在集群劃分方面，該方法使用了一種改進(jìn)的k均值算法來(lái)劃分初始無(wú)人機(jī)集群。在首領(lǐng)選擇方面，考慮到無(wú)人機(jī)高移動(dòng)性和拓?fù)鋭?dòng)態(tài)變化，使用以下適應(yīng)度函數(shù)來(lái)選擇集群首領(lǐng)

文獻(xiàn)[68]提出了一種集群控制算法和一種路徑規(guī)劃算法來(lái)解決FANET 中無(wú)人機(jī)能量有限、移動(dòng)性高的問(wèn)題，下面重點(diǎn)分析其集群控制算法。該算法使用監(jiān)督學(xué)習(xí)和單層感知器學(xué)習(xí)規(guī)則來(lái)訓(xùn)練集群首領(lǐng)選擇系統(tǒng)，集群首領(lǐng)選擇系統(tǒng)以無(wú)人機(jī)剩余能量、無(wú)人機(jī)之間的平均距離和無(wú)人機(jī)的度數(shù)3 項(xiàng)指標(biāo)為依據(jù)選擇集群首領(lǐng)。

文獻(xiàn)[69]提出了一種集群控制方法來(lái)解決FANET 中的動(dòng)態(tài)拓?fù)浜蜔o(wú)人機(jī)能量有限的問(wèn)題。在集群首領(lǐng)選擇和集群劃分方面，各無(wú)人機(jī)根據(jù)自身的熒光素含量（與該無(wú)人機(jī)和鄰居無(wú)人機(jī)之間的距離有關(guān)）以及剩余能量來(lái)計(jì)算自己的適應(yīng)度。隨后，各無(wú)人機(jī)向其鄰居無(wú)人機(jī)發(fā)送自己的適應(yīng)度并接受鄰居無(wú)人機(jī)發(fā)送的適應(yīng)度。如果該無(wú)人機(jī)在其鄰居無(wú)人機(jī)中具有最高的適應(yīng)度，則該無(wú)人機(jī)向其鄰居無(wú)人機(jī)宣布自己為集群首領(lǐng)；否則，該無(wú)人機(jī)將鄰居無(wú)人機(jī)中適應(yīng)度最高的無(wú)人機(jī)作為集群首領(lǐng)，而自己成為集群成員。當(dāng)集群形成后，各集群成員根據(jù)集群首領(lǐng)的位置變化情況來(lái)調(diào)整自己的位置。

文獻(xiàn)[70]首先提出了一種基于混合灰狼優(yōu)化算法的高能效、無(wú)范圍的定位算法，然后提出了一種集中式的集群構(gòu)建方法。在集群劃分方面，該文獻(xiàn)首先通過(guò)數(shù)學(xué)分析求得最優(yōu)集群數(shù)量，使無(wú)人機(jī)向地面基站傳輸數(shù)據(jù)消耗的能量最少。隨后使用混合灰狼優(yōu)化算法來(lái)尋找每個(gè)集群的中心點(diǎn)，從而將各無(wú)人機(jī)劃分到各個(gè)集群。在集群首領(lǐng)選擇方面，該文獻(xiàn)根據(jù)集群內(nèi)無(wú)人機(jī)之間的距離、鄰居數(shù)量和無(wú)人機(jī)的剩余能量來(lái)計(jì)算每個(gè)無(wú)人機(jī)的適應(yīng)度，每個(gè)集群中適應(yīng)度最高的無(wú)人機(jī)成為該集群的集群首領(lǐng)。在集群間的數(shù)據(jù)傳輸方面，該文獻(xiàn)構(gòu)建了一個(gè)基于最小生成樹(shù)的虛擬主干網(wǎng)絡(luò)，從而以最小跳數(shù)進(jìn)行集群間的數(shù)據(jù)傳輸。由于該文獻(xiàn)提出的是集中式的集群構(gòu)建方法，這一方法需要首先獲取各無(wú)人機(jī)的位置、剩余能量等信息，并根據(jù)收集的信息在某一中央控制器中求得集群首領(lǐng)選擇和集群劃分結(jié)果，隨后中央控制器將計(jì)算結(jié)果發(fā)送給各無(wú)人機(jī)。

文獻(xiàn)[71]提出了一種集中式的集群控制方法來(lái)解決FANET 中的路由和安全問(wèn)題。在集群首領(lǐng)選擇和集群劃分方面，該方法根據(jù)無(wú)人機(jī)的剩余能量、聲譽(yù)、運(yùn)行時(shí)間、交易數(shù)量、移動(dòng)性和連通性等指標(biāo)，使用改進(jìn)的人工蜂群算法選擇集群首領(lǐng)。隨后，剩余無(wú)人機(jī)加入其鄰居的集群首領(lǐng)所在的集群，完成集群劃分。此外，該方法使用區(qū)塊鏈技術(shù)來(lái)保護(hù)路由數(shù)據(jù)。該文獻(xiàn)提出的集群首領(lǐng)選擇方法需要以集中式的方式運(yùn)行，因此這一方法需要首先獲取各無(wú)人機(jī)的位置、剩余能量、聲譽(yù)和運(yùn)行時(shí)間等信息，并根據(jù)收集的信息在某一中央控制器中求得集群首領(lǐng)選擇結(jié)果，隨后中央控制器將計(jì)算結(jié)果發(fā)送給各無(wú)人機(jī)。

為了使FANET 能夠滿足緊急通信的需求，文獻(xiàn)[72]提出了一種基于PSO 算法的集群控制方法。在集群劃分方面，該方法通過(guò)計(jì)算與相鄰無(wú)人機(jī)的歐氏距離來(lái)獲得最近的節(jié)點(diǎn)對(duì)，具有最近鄰居距離的無(wú)人機(jī)被劃分到同一個(gè)集群中，以節(jié)省數(shù)據(jù)傳輸過(guò)程中的能量消耗并延長(zhǎng)鏈路生存時(shí)間。在集群首領(lǐng)選擇方面，該方法根據(jù)無(wú)人機(jī)之間的平均距離、無(wú)人機(jī)與地面基站的平均距離以及無(wú)人機(jī)的剩余能量等指標(biāo)，使用PSO 算法選擇集群首領(lǐng)。該文獻(xiàn)提出的集群首領(lǐng)選擇方法和集群劃分方法均需要以集中式的方式運(yùn)行，因此這一方法需要首先獲取各無(wú)人機(jī)的位置、速度、剩余能量等信息，并根據(jù)收集的信息在某一中央控制器中求得集群首領(lǐng)選擇和集群劃分結(jié)果，隨后中央控制器將計(jì)算結(jié)果發(fā)送給各無(wú)人機(jī)。

文獻(xiàn)[73]考慮了一種特殊的FANET 場(chǎng)景。在該場(chǎng)景中，無(wú)人機(jī)分為若干組，只有同一組的無(wú)人機(jī)之間需要互相通信。為此，作者提出了一種聯(lián)盟博弈論框架，基于無(wú)人機(jī)的移動(dòng)性信息，在集群大小和集群直徑約束下，以分布式方式將無(wú)人機(jī)劃分為若干聯(lián)盟，從而最小化無(wú)人機(jī)之間的通信時(shí)延。

文獻(xiàn)[74]提出了一種FANET 集群控制方法來(lái)解決無(wú)人機(jī)的高移動(dòng)性問(wèn)題。首先，每個(gè)無(wú)人機(jī)根據(jù)以下適應(yīng)度函數(shù)來(lái)計(jì)算自己的適應(yīng)值

其中，λi表示無(wú)人機(jī)的平均安全度，與該無(wú)人機(jī)和其鄰居無(wú)人機(jī)之間的距離有關(guān)；ER,i表示無(wú)人機(jī)的剩余能量；σi表示移動(dòng)感知因子，與該無(wú)人機(jī)的速度以及其鄰居無(wú)人機(jī)的速度有關(guān)；w1、w2和w3表示各變量所占的權(quán)重。隨后，在其單跳鄰居中具有最小適應(yīng)值的無(wú)人機(jī)成為集群首領(lǐng)，并且集群首領(lǐng)的鄰居變成它的集群成員。

為了在時(shí)延約束下最大化無(wú)人機(jī)的覆蓋性能，文獻(xiàn)[75]提出了一種基于貪心思想的集群控制算法。首先，該算法通過(guò)添加或刪除單個(gè)集群首領(lǐng)的方式來(lái)確定最終的集群首領(lǐng)，隨后，其余無(wú)人機(jī)選擇與其時(shí)延最小的集群首領(lǐng)并加入該集群。

在集群劃分方面，無(wú)人機(jī)之間的距離、集群內(nèi)無(wú)人機(jī)的數(shù)量和集群直徑等指標(biāo)是主要的劃分依據(jù)。距離相近的無(wú)人機(jī)被劃分到同一集群能夠減少集群的空間大小，從而降低無(wú)人機(jī)之間的通信時(shí)延。各集群中包含相似數(shù)量的無(wú)人機(jī)以及具有相似的直徑，可以平衡各集群產(chǎn)生的負(fù)載，提高數(shù)據(jù)的傳輸成功率。在集群首領(lǐng)選擇方面，無(wú)人機(jī)的剩余能量、無(wú)人機(jī)之間的距離、無(wú)人機(jī)到地面基站的距離、無(wú)人機(jī)之間的相對(duì)速度、節(jié)點(diǎn)的度等指標(biāo)是主要的參考依據(jù)。選擇剩余能量多的無(wú)人機(jī)作為集群首領(lǐng)可以平衡各無(wú)人機(jī)的能量，延長(zhǎng)FANET 的生存時(shí)間。無(wú)人機(jī)之間的距離主要影響無(wú)人機(jī)之間的通信時(shí)延，無(wú)人機(jī)到地面基站的距離主要影響集群首領(lǐng)到地面基站的通信時(shí)延，無(wú)人機(jī)之間的相對(duì)速度主要影響集群首領(lǐng)的生存時(shí)間，節(jié)點(diǎn)的度則主要影響集群之間的負(fù)載均衡。

基于集群的FANET 在可擴(kuò)展性、可靠性、數(shù)據(jù)收集、能量效率和時(shí)延等方面更具優(yōu)勢(shì)，因此集群構(gòu)建算法主要適用于在執(zhí)行大規(guī)模數(shù)據(jù)傳輸任務(wù)的FANET（如利用FANET 從地面物聯(lián)網(wǎng)設(shè)備收集數(shù)據(jù)）中劃分集群并為各個(gè)集群選擇集群首領(lǐng)，從而提高FANET 的數(shù)據(jù)傳輸效率。與CDS 構(gòu)建算法不同，集群構(gòu)建算法沒(méi)有嚴(yán)格設(shè)定每個(gè)無(wú)人機(jī)的通信范圍，因此集群構(gòu)建算法更適用于無(wú)人機(jī)通信范圍（由無(wú)人機(jī)的發(fā)送功率決定）可靈活調(diào)整的場(chǎng)景。

大多集群構(gòu)建算法在進(jìn)行集群首領(lǐng)選擇和集群劃分時(shí)僅考慮了同一集群中集群首領(lǐng)和集群成員之間的通信性能，而沒(méi)有考慮不同集群中集群首領(lǐng)之間進(jìn)行通信的性能。為此，需要將不同集群中集群首領(lǐng)之間的通信性能作為集群首領(lǐng)選擇和集群劃分的依據(jù)，從而優(yōu)化FANET 的整體性能。此外，大多數(shù)集群構(gòu)建算法大多在無(wú)人機(jī)位置、功率等固定的基礎(chǔ)上進(jìn)行集群首領(lǐng)選擇和集群劃分?？梢钥紤]將調(diào)整無(wú)人機(jī)的位置、功率等與集群構(gòu)建結(jié)合起來(lái)，在滿足FANET 任務(wù)性能約束的情況下，進(jìn)一步優(yōu)化FANET 的網(wǎng)絡(luò)性能。

3.3.2集群維護(hù)算法

文獻(xiàn)[65]根據(jù)集群首領(lǐng)與鄰居的平均相對(duì)速度、集群首領(lǐng)與鄰居的相對(duì)位置以及地面基站與集群間無(wú)人機(jī)的平均距離3 項(xiàng)指標(biāo)在每個(gè)集群中選擇一個(gè)備用集群首領(lǐng)。當(dāng)某個(gè)集群首領(lǐng)離開(kāi)FANET 時(shí)，其備用集群首領(lǐng)成為新的集群首領(lǐng)。在文獻(xiàn)[66]中，當(dāng)FANET 中不在集群中的無(wú)人機(jī)占到20%以上時(shí)，重新執(zhí)行集群劃分和集群首領(lǐng)選擇。在文獻(xiàn)[67]中，如果集群首領(lǐng)離開(kāi)集群，則在該集群中重新選擇集群首領(lǐng)，集群首領(lǐng)根據(jù)無(wú)人機(jī)的剩余能量來(lái)管理集群成員。在文獻(xiàn)[69]中，集群首領(lǐng)將剩余能量大于或等于閾值的集群成員繼續(xù)作為其集群成員，而將剩余能量低于閾值的無(wú)人機(jī)作為死亡節(jié)點(diǎn)，不再作為其集群成員。

選擇備用集群首領(lǐng)代替離開(kāi)的集群首領(lǐng)以及重新選擇集群首領(lǐng)是維護(hù)集群首領(lǐng)的常用方式，而能量指標(biāo)是維護(hù)集群成員的主要依據(jù)。由于各無(wú)人機(jī)的位置頻繁變化，集群維護(hù)算法需要高頻率執(zhí)行。因此，選擇備用集群首領(lǐng)比重新選擇集群首領(lǐng)更適合于基于集群的拓?fù)淇刂扑惴ā?/p>

集群維護(hù)算法主要適用于在保證當(dāng)前基于集群的FAENT 服務(wù)盡可能不中斷的情況下，維護(hù)FANET 中的集群并提高其性能。當(dāng)系統(tǒng)中存在中央控制器時(shí)（如FANET 采用SDN 架構(gòu)），可以重新選擇集群首領(lǐng)或重新進(jìn)行集群劃分；當(dāng)系統(tǒng)中不存在中央控制器時(shí)，需要設(shè)計(jì)分布式的集群維護(hù)算法，使各無(wú)人機(jī)僅根據(jù)其局部信息來(lái)確定自己的角色以及加入或離開(kāi)集群。

現(xiàn)有集群維護(hù)算法主要通過(guò)選擇備用集群首領(lǐng)或者重選集群首領(lǐng)來(lái)完成集群維護(hù)，其思路局限于集群首領(lǐng)的選擇方面。可以進(jìn)一步考慮以動(dòng)態(tài)更新集群數(shù)量、集群成員加入其他集群等方式來(lái)實(shí)現(xiàn)集群維護(hù)。此外，現(xiàn)有集群維護(hù)算法主要在集群首領(lǐng)離開(kāi)后進(jìn)行集群維護(hù)，因此可以考慮在集群首領(lǐng)能量不足、網(wǎng)絡(luò)性能不佳等情況下主動(dòng)進(jìn)行集群維護(hù)。

3.4 基于虛擬力的拓?fù)淇刂扑惴?/h3>

基于虛擬力的拓?fù)淇刂扑惴ㄊ且环N分布式拓?fù)淇刂扑惴?，該算法假設(shè)每個(gè)無(wú)人機(jī)節(jié)點(diǎn)都會(huì)受到來(lái)自其鄰居節(jié)點(diǎn)、障礙物、任務(wù)目標(biāo)等的虛擬力，該虛擬力的大小通常和無(wú)人機(jī)與鄰居節(jié)點(diǎn)、障礙物、任務(wù)目標(biāo)之間的距離有關(guān)。由此，每個(gè)無(wú)人機(jī)僅需要根據(jù)其受到的來(lái)自鄰居無(wú)人機(jī)、障礙物、任務(wù)目標(biāo)等的虛擬力的合力自主調(diào)整位置。

本文將基于虛擬力的拓?fù)淇刂扑惴ㄖ械奶摂M力分為4 類：吸引力、排斥力、障礙避免力和任務(wù)力，如圖8 所示。這4 種力分別用于實(shí)現(xiàn)以下4 個(gè)目標(biāo)：1) 各無(wú)人機(jī)能夠保證網(wǎng)絡(luò)的連通性以進(jìn)行信息交換；2) 無(wú)人機(jī)之間能夠保證期望的距離，避免發(fā)生碰撞；3) 無(wú)人機(jī)能夠繞過(guò)障礙物；4) 無(wú)人機(jī)集群能完成既定的任務(wù)。下面，本文將根據(jù)虛擬力的種類及其實(shí)現(xiàn)的目標(biāo)對(duì)基于虛擬力的拓?fù)淇刂扑惴ㄟM(jìn)行詳細(xì)的分析。

圖8 虛擬力種類

在無(wú)人機(jī)作為空中基站為地面用戶提供服務(wù)的場(chǎng)景中，文獻(xiàn)[77]提出了一種分布式運(yùn)動(dòng)控制算法，使每個(gè)無(wú)人機(jī)能夠自主運(yùn)動(dòng)并按需覆蓋地面用戶。為了維持無(wú)人機(jī)網(wǎng)絡(luò)的連通性，該算法中的吸引力控制無(wú)人機(jī)向熱點(diǎn)區(qū)域中心運(yùn)動(dòng)。受萬(wàn)有引力定律啟發(fā)，吸引力的計(jì)算式為

其中，di是無(wú)人機(jī)到熱點(diǎn)以及2 個(gè)相鄰熱點(diǎn)之間連線的距離，是由熱點(diǎn)重要性決定的吸引力因子。受胡克定律啟發(fā)，使無(wú)人機(jī)之間能夠保證期望距離的排斥力的計(jì)算式為

其中，Kr是排斥力因子，dij是無(wú)人機(jī)i和無(wú)人機(jī)j之間的距離，Ropt是無(wú)人機(jī)之間的期望距離。此外，根據(jù)萬(wàn)有引力定律，障礙避免力的計(jì)算式為

其中，dsafe是無(wú)人機(jī)到障礙物的安全距離，dobs是無(wú)人機(jī)和障礙物之間的實(shí)際距離。最后，根據(jù)萬(wàn)有引力定律，引導(dǎo)無(wú)人機(jī)接近地面用戶的任務(wù)力的計(jì)算式為

其中，ka為任務(wù)力因子，due為無(wú)人機(jī)與地面用戶之間的距離，Rs為無(wú)人機(jī)的感應(yīng)范圍。最終，無(wú)人機(jī)受到的虛擬力合力為

文獻(xiàn)[78]提出了一種基于虛擬力的拓?fù)淇刂扑惴?，可用于在基于集群的FANET 中控制集群成員跟隨集群首領(lǐng)移動(dòng)，且控制整個(gè)FANET 完成區(qū)域覆蓋任務(wù)。維持網(wǎng)絡(luò)連通性的吸引力和保持無(wú)人機(jī)距離的排斥力由同一計(jì)算式給出

其中，kT≥ 0，α∈[0,1]，dij是無(wú)人機(jī)i和無(wú)人機(jī)j之間的距離，αR是無(wú)人機(jī)之間的期望距離，eij是無(wú)人機(jī)i和無(wú)人機(jī)j的單位方向向量。為了減少無(wú)人機(jī)之間的重復(fù)覆蓋區(qū)域，無(wú)人機(jī)受到的任務(wù)力的計(jì)算式為

其中，kC＞ 0，β∈[0,1]，dij是無(wú)人機(jī)i和無(wú)人機(jī)j之間的橫向距離，D是無(wú)人機(jī)之間的最大橫向感應(yīng)范圍，是無(wú)人機(jī)j到無(wú)人機(jī)i的垂直單位方向向量。最終，如果無(wú)人機(jī)i跟隨無(wú)人機(jī)j，則無(wú)人機(jī)i受到的虛擬力合力為

在空中無(wú)人機(jī)為地面孤立用戶提供多跳中繼服務(wù)的場(chǎng)景中，文獻(xiàn)[79]提出了一種基于虛擬彈簧模型的拓?fù)淇刂扑惴?。鏈路的通信質(zhì)量可以用鏈路預(yù)算表示為

其中，LBreq表示鏈路請(qǐng)求的預(yù)算，α表示傳播衰減指數(shù)，k的值與鏈路類型有關(guān)。該虛擬力可同時(shí)用于保持網(wǎng)絡(luò)連通性、維持無(wú)人機(jī)之間的距離以及滿足FANET 對(duì)通信性能的需求。文獻(xiàn)[80]也使用了類似的方法。

此外，一些文獻(xiàn)使用勢(shì)能來(lái)反映無(wú)人機(jī)受到的虛擬力。在分層式FANET 中，文獻(xiàn)[81]提出了一種分層式無(wú)人機(jī)群控制算法，用于保持網(wǎng)絡(luò)的連通性，并避免無(wú)人機(jī)之間發(fā)生碰撞。首先，為了使跟隨者與其領(lǐng)導(dǎo)者之間的距離處于安全距離范圍內(nèi)，跟隨者會(huì)受到來(lái)自其領(lǐng)導(dǎo)者的吸引力或排斥力，其對(duì)應(yīng)的勢(shì)能函數(shù)為

其中，r1表示最小安全距離，r2表示最大安全距離，diL表示跟隨者與領(lǐng)導(dǎo)者之間的距離。此外，為了避免無(wú)人機(jī)之間發(fā)生碰撞，無(wú)人機(jī)會(huì)受到與其距離較近的無(wú)人機(jī)的排斥力，其對(duì)應(yīng)的勢(shì)能函數(shù)為

其中，Ti表示與無(wú)人機(jī)i的距離小于最小安全距離的無(wú)人機(jī)集合，dij表示無(wú)人機(jī)i和無(wú)人機(jī)j之間的距離。式(21)和式(22)中的勢(shì)能函數(shù)實(shí)際上是遵循胡克定律的彈性力勢(shì)能函數(shù)。無(wú)人機(jī)需要通過(guò)移動(dòng)，盡量將自身受到的勢(shì)能之和降低為零。

基于虛擬力的拓?fù)淇刂扑惴ㄊ且环N分布式的FANET 拓?fù)淇刂扑惴?。在通信開(kāi)銷方面，每個(gè)無(wú)人機(jī)僅需根據(jù)其鄰居節(jié)點(diǎn)的相關(guān)信息來(lái)自主調(diào)整位置，通信開(kāi)銷小。此外，此類算法可以有效地滿足FANET 在連通性、碰撞避免、障礙物避免和任務(wù)執(zhí)行等方面的需求。此類算法的虛擬力及其對(duì)應(yīng)勢(shì)能的設(shè)計(jì)大多受現(xiàn)有物理模型啟發(fā)，例如胡克定律、萬(wàn)有引力定律等。其中，基于胡克定律的虛擬力的大小隨實(shí)際距離與設(shè)定距離之差線性變化，因此，該虛擬力主要用于將2 個(gè)無(wú)人機(jī)之間的距離或者一個(gè)無(wú)人機(jī)與目標(biāo)位置之間的距離維持在設(shè)定值。此外，基于萬(wàn)有引力定律的虛擬力的大小隨距離減小而迅速增大。因此，基于萬(wàn)有引力定律的虛擬力主要用于無(wú)人機(jī)飛往多個(gè)候選位置（或節(jié)點(diǎn)）中的一個(gè)位置（或節(jié)點(diǎn)），以及避免無(wú)人機(jī)碰撞。在設(shè)計(jì)基于虛擬力的拓?fù)淇刂扑惴〞r(shí)，本文需要FANET 的實(shí)際應(yīng)用需求來(lái)設(shè)計(jì)合理的虛擬力。表4 展示了基于虛擬力的拓?fù)淇刂扑惴ǖ谋容^結(jié)果。

表4 基于虛擬力的拓?fù)淇刂扑惴ǖ谋容^結(jié)果

目前，基于虛擬力的拓?fù)淇刂扑惴ㄖ饕m用于多個(gè)無(wú)人機(jī)以自組織的方式形成FANET 來(lái)為地面設(shè)備提供通信覆蓋服務(wù)（例如，在災(zāi)難救援場(chǎng)景中，自組織的FANET 作為空中基站為災(zāi)區(qū)用戶提供通信服務(wù)）。此外，基于虛擬力的拓?fù)淇刂扑惴ㄟ€可用于保持無(wú)人機(jī)之間的分層結(jié)構(gòu)或特定隊(duì)形。

基于虛擬力的拓?fù)淇刂扑惴ㄖ攸c(diǎn)關(guān)注FANET的連通性和覆蓋性能。在網(wǎng)絡(luò)性能方面，基于虛擬力的拓?fù)淇刂扑惴梢员ＷCFANET 的連通性，但不關(guān)注時(shí)延、丟包率等性能的優(yōu)化。在任務(wù)性能方面，基于虛擬力的拓?fù)淇刂扑惴梢詫?shí)現(xiàn)FANET對(duì)目標(biāo)區(qū)域或目標(biāo)用戶的覆蓋，但不關(guān)注用戶吞吐量等通信質(zhì)量的優(yōu)化。針對(duì)基于虛擬力的拓?fù)淇刂扑惴ù嬖诘牟蛔?，一方面，可以考慮在設(shè)計(jì)虛擬力時(shí)引入端到端時(shí)延、用戶吞吐量等指標(biāo)，使端到端時(shí)延、用戶吞吐量等指標(biāo)影響無(wú)人機(jī)所受到的虛擬力大小。另一方面，可以考慮將基于虛擬力的拓?fù)淇刂扑惴ㄅc其他種類的拓?fù)淇刂扑惴ㄏ嘟Y(jié)合（例如，在利用基于虛擬力的拓?fù)淇刂扑惴M足FANET 的連通和覆蓋需求后，各無(wú)人機(jī)進(jìn)一步調(diào)整自己的位置，從而在維護(hù)網(wǎng)絡(luò)連通性的前提下進(jìn)一步優(yōu)化FAENT 的端到端時(shí)延等網(wǎng)絡(luò)性能以及用戶吞吐量等任務(wù)性能），實(shí)現(xiàn)不同種類算法之間的優(yōu)勢(shì)互補(bǔ)。

4 挑戰(zhàn)和未來(lái)研究方向

當(dāng)前，F(xiàn)ANET 拓?fù)淇刂迫蕴幱诎l(fā)展階段。本節(jié)討論并總結(jié)了FANET 拓?fù)淇刂迫悦媾R的挑戰(zhàn)以及未來(lái)的研究方向。

1) 通信鏈路頻繁中斷

現(xiàn)有的FANET 拓?fù)淇刂扑惴ù蠖嗉僭O(shè)無(wú)人機(jī)之間以及無(wú)人機(jī)與地面基站之間能夠維持穩(wěn)定的通信。而在真實(shí)的FANET 中，無(wú)人機(jī)密度較低且具有高度的動(dòng)態(tài)性和不確定性，因此無(wú)人機(jī)之間以及無(wú)人機(jī)與地面基站之間的通信鏈路頻繁中斷。在無(wú)人機(jī)通信鏈路間歇性連接的場(chǎng)景中，設(shè)計(jì)一種有效的FANET 拓?fù)淇刂扑惴ㄊ且豁?xiàng)艱巨且具有實(shí)際意義的任務(wù)。

2) 高頻率動(dòng)態(tài)執(zhí)行

FANET 中的無(wú)人機(jī)具有高度的動(dòng)態(tài)性和不確定性，相應(yīng)地，F(xiàn)ANET 拓?fù)淇刂扑惴ㄐ枰哳l率動(dòng)態(tài)執(zhí)行以實(shí)時(shí)更新FANET 拓?fù)?，從而維持FANET的性能。FANET 拓?fù)淇刂扑惴ǖ母哳l率動(dòng)態(tài)執(zhí)行對(duì)算法的收斂時(shí)間、通信開(kāi)銷、實(shí)現(xiàn)的性能等方面提出了嚴(yán)格的要求。然而，目前只有少量FANET 拓?fù)淇刂扑惴軌驖M足高頻率動(dòng)態(tài)執(zhí)行的要求，有待于進(jìn)一步研究開(kāi)發(fā)。

3) 評(píng)估工具

FANET 拓?fù)淇刂频南嚓P(guān)研究在仿真實(shí)驗(yàn)中使用了多種不同的仿真工具，例如，NS-2、OPNET、OMNET++、MATLAB 等。然而，這些仿真工具在3D 場(chǎng)景、通信信道和移動(dòng)模型等方面的建模還不能很好地支持FANET 的特殊要求。為了有效地評(píng)估FANET 拓?fù)淇刂扑惴ǖ男阅?，需要開(kāi)發(fā)一種支持FANET 特性的仿真工具。

4) 安全問(wèn)題

FANET 的拓?fù)浣Y(jié)構(gòu)是一種重要的網(wǎng)絡(luò)資產(chǎn)，且嚴(yán)重影響FANET 的安全性。例如，當(dāng)使用分層式FANET 執(zhí)行偵察等任務(wù)時(shí)，根據(jù)FANET 的拓?fù)浣Y(jié)構(gòu)，敵方能夠輕易地識(shí)別出其中的領(lǐng)導(dǎo)者無(wú)人機(jī)。此時(shí)，敵方僅需破壞乃至劫持少量的領(lǐng)導(dǎo)者無(wú)人機(jī)，就可對(duì)我方的FANET 造成嚴(yán)重?fù)p害。因此，在具有安全性需求的場(chǎng)景中，F(xiàn)ANET 拓?fù)淇刂扑惴ㄐ枰赡軌螂[藏?zé)o人機(jī)相關(guān)信息的FANET 拓?fù)洹?/p>

5) 任務(wù)性能和通信性能

FANET 的任務(wù)性能需求和通信性能需求之間通常是矛盾的[34,51]，而大多數(shù)FANET 拓?fù)淇刂扑惴](méi)有考慮這一特性。為此，F(xiàn)ANET 拓?fù)淇刂扑惴ㄉ傻腇ANET 必須同時(shí)滿足FANET 的任務(wù)性能需求和通信性能需求，實(shí)現(xiàn)FANET 任務(wù)性能和通信性能之間的平衡。

6) 故障恢復(fù)

現(xiàn)有的FANET 拓?fù)淇刂扑惴ㄖ饕ㄟ^(guò)生成具有容錯(cuò)性的FANET 拓?fù)鋪?lái)應(yīng)對(duì)FANET 發(fā)生的故障，而不是在FANET 發(fā)生故障后快速恢復(fù)有效的FANET 拓?fù)洹Ｊ聦?shí)上，具有容錯(cuò)性的FANET 拓?fù)渲荒軕?yīng)對(duì)FANET中極少數(shù)無(wú)人機(jī)發(fā)生故障的情況，因此，在FANET 部分無(wú)人機(jī)發(fā)生故障后快速恢復(fù)有效的FANET 拓?fù)涓蠈?shí)際的需求，相關(guān)的FANET 拓?fù)淇刂扑惴ㄒ残枰M(jìn)一步研究。

5 結(jié)束語(yǔ)

本文對(duì)現(xiàn)有的FANET 拓?fù)淇刂蒲芯窟M(jìn)行了綜述。首先，分析了相關(guān)綜述的不足，并指出了本文的貢獻(xiàn)。隨后，介紹了FANET 的網(wǎng)絡(luò)架構(gòu)以及FANET 拓?fù)淇刂频难芯靠蚣芎托枨蠛头诸惙椒?。之后，?duì)每一類FANET 拓?fù)淇刂扑惴ǘ歼M(jìn)行了詳細(xì)的分析。最后，總結(jié)了FANET 拓?fù)淇刂迫孕杞鉀Q的問(wèn)題以及未來(lái)的研究方向。