劉亞群，謝鈞，邢長友，倪保安

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

0 引言

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

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

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

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

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

根據(jù)FANET 的特點及需求，F(xiàn)ANET 拓撲控制通過構(gòu)建和調(diào)整FANET 拓撲結(jié)構(gòu)，維持FANET的連通性，并提高FANET 的性能[25]。具體地，F(xiàn)ANET 拓撲控制算法通過調(diào)整無人機的組網(wǎng)方式、位置、功率等參數(shù)來生成并動態(tài)維護滿足特定約束且具有較優(yōu)性能的FANET 拓撲。FANET 拓撲控制算法具有以下特點：1) 在優(yōu)化變量方面，F(xiàn)ANET 拓撲控制優(yōu)化的變量主要集中在無人機本身，例如，無人機之間的組網(wǎng)方式、無人機的位置和無人機的發(fā)送功率等；2) 在優(yōu)化目標方面，F(xiàn)ANET 需要優(yōu)化的性能與其應用場景有關(guān)。由于FANET 的應用場景非常廣泛，通信性能（如吞吐量、時延、干擾等）、任務性能（如覆蓋率等）、能量消耗等均可能成為FANET 拓撲控制的優(yōu)化目標；3) 在執(zhí)行頻率方面，F(xiàn)ANET 中無人機具有高度的移動特性，F(xiàn)ANET 拓撲控制需要高頻率動態(tài)執(zhí)行。

目前，研究人員已經(jīng)開發(fā)出多種FANET 拓撲控制算法。然而，目前的FANET 綜述還沒有對FANET 拓撲控制算法進行全面且詳細的分析。因此，本文對FANET 拓撲控制算法進行了全面的綜述，梳理FANET 拓撲控制算法的研究思路，為FANET 拓撲控制算法的使用與開發(fā)提供依據(jù)。本文的主要貢獻總結(jié)如下。

1) 介紹了FANET 的網(wǎng)絡架構(gòu)，給出了FANET拓撲控制的研究框架和需求。

2) 基于FANET 拓撲控制算法適用的網(wǎng)絡架構(gòu)，提出了一種FANET 拓撲控制算法的分類方法。根據(jù)每類FANET 拓撲控制算法的特有屬性，對每類FANET拓撲控制算法進行了全面且詳細的分析，并通過對比總結(jié)了不同算法的特點和優(yōu)缺點，便于研究人員根據(jù)需求選擇合適的FANET 拓撲控制算法以及開發(fā)新的FANET 拓撲控制算法。

3) 討論了FANET 拓撲控制算法仍面臨的挑戰(zhàn)以及未來的研究方向。

1 相關(guān)工作

本節(jié)梳理了與FANET 和拓撲控制兩大主題有關(guān)的綜述，并討論了本文與這些相關(guān)工作的不同之處，以凸顯本文的創(chuàng)新性。

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

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

目前，有關(guān)FANET 拓撲控制的綜述還相對較少。文獻[34]主要總結(jié)了3 種基于虛擬力的FANET拓撲控制算法，但對目前已經(jīng)出現(xiàn)的大量其他種類的FANET 拓撲控制算法沒有系統(tǒng)分析。文獻[25]基于FANET 拓撲控制算法的執(zhí)行方式和數(shù)學模型對FANET 拓撲控制算法進行了分類，并對FANET拓撲控制算法進行了詳細的分析。然而，在文獻[25]提出的分類方法中，不同種類的算法之間區(qū)分不明顯，每種算法的特有屬性無法體現(xiàn)。此外，文獻[25]僅分析了部分具有代表性的FANET拓撲控制算法，對現(xiàn)有FANET 拓撲控制算法的綜述不夠全面。本文提出了一種全新的FANET 拓撲控制算法的分類方法，并根據(jù)每一類算法的特有屬性，對現(xiàn)有FANET 拓撲控制算法進行了全面的綜述。

2 飛行自組網(wǎng)拓撲控制概述

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

2.2 飛行自組網(wǎng)拓撲控制的研究框架和需求

2.2.1研究框架

本文將FANET 拓撲控制研究框架分為三步：模型構(gòu)建、算法設計及效果評估，如圖3 所示。在模型構(gòu)建階段，需要根據(jù)FANET 的應用場景，確定FANET 的架構(gòu)，設計拓撲控制算法需要滿足的約束、優(yōu)化的目標以及可調(diào)整的參數(shù)。在算法設計階段，需要根據(jù)拓撲控制的實施階段、約束、目標以及可調(diào)整的參數(shù)，選擇合適的數(shù)學工具來設計相應的拓撲控制算法。根據(jù)拓撲控制算法的實施階段，F(xiàn)ANET 拓撲控制算法可分為拓撲構(gòu)建算法和拓撲維護算法。其中，拓撲構(gòu)建算法用于在沒有無人機初始位置、發(fā)送功率和連接關(guān)系的情況下，從零開始構(gòu)建FANET 拓撲；拓撲維護則用于在現(xiàn)有FANET 拓撲的基礎上，通過調(diào)整相關(guān)變量，進一步優(yōu)化FANET 拓撲。最后，在效果評估階段，需要評估FANET 拓撲控制算法的性能，并進一步優(yōu)化FANET 拓撲控制算法。

圖3 FANET 拓撲控制研究框架

2.2.2需求

本文將FANET 拓撲控制的需求總結(jié)如下。

1) 連通性

在FANET 中，連通性指任意一對無人機之間以及任意一個無人機與基礎設施之間至少存在一條通信路徑。FANET 是一種為實現(xiàn)無人機之間以及無人機與基礎設施之間通信而設計的網(wǎng)絡架構(gòu)，因此連通性是FANET 拓撲控制最基本的要求。

2) 網(wǎng)絡性能

FANET 的網(wǎng)絡性能是指無人機之間以及無人機與地面基站等基礎設施之間通信的性能。FANET需要優(yōu)化的網(wǎng)絡性能與其應用的場景有關(guān)，因此，F(xiàn)ANET 拓撲控制需要根據(jù)FANET 的應用場景設計合適的FANET 拓撲，以滿足特定場景對FANET 的網(wǎng)絡性能要求。通常，F(xiàn)ANET 拓撲控制優(yōu)化的網(wǎng)絡性能有鏈路時延、鏈路吞吐量、無人機之間的干擾、負載均衡等。

3) 任務性能

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

4) 容錯性

FANET 在任務執(zhí)行期間可能會遇到無人機故障、障礙物、惡劣天氣等不確定性情況。因此，F(xiàn)ANET 拓撲控制需要設計具有容錯性的FANET。一方面，在FANET 發(fā)生故障前，F(xiàn)ANET 拓撲控制可以設計具有容錯性的FANET 拓撲，使FANET 在個別無人機發(fā)生故障后仍能正常運行。例如，F(xiàn)ANET 拓撲控制可以構(gòu)建具有k（k≥ 2）連通性質(zhì)的FANET 拓撲。另一方面，當FANET 發(fā)生故障后，F(xiàn)ANET 拓撲控制添加無人機以及調(diào)整無人機的位置恢復FANET 的正常運行[36-37]。

5) 執(zhí)行頻率

FANET 中的無人機具有高移動性的特點，無人機之間的相對位置頻繁變化。因此，F(xiàn)ANET 拓撲控制需要高頻率動態(tài)更新FANET 拓撲，以維持FANET的性能。為了滿足FANET 拓撲控制動態(tài)執(zhí)行的需求，F(xiàn)ANET 拓撲控制需要在較短時間內(nèi)完成。

6) 執(zhí)行方式

FANET 拓撲控制算法的執(zhí)行方式分為集中式執(zhí)行和分布式執(zhí)行2 種。其中，集中式執(zhí)行的FANET拓撲控制算法需要由中央控制單元集中執(zhí)行。相比之下，分布式執(zhí)行的拓撲控制算法可以由各無人機自主執(zhí)行，具有更小的通信開銷，算法收斂速度更快，更適合于具有高移動性特點的FANET。

7) 能量消耗

無人機的能量消耗由通信能量消耗和飛行能量消耗兩部分組成，其中飛行能量消耗遠大于通信能量消耗，因此FANET 拓撲控制主要考慮無人機的飛行能量消耗。根據(jù)文獻[38]，假設無人機的飛行速度恒定為V，飛行時間為T，固定翼無人機的飛行能量消耗可以表示為

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

其中，c1和c2是與無人機的重量、旋翼速度、旋翼盤面積、葉片角速度和空氣密度等因素有關(guān)的常數(shù)，q是旋翼葉尖速度，do是機身阻力比，vo是平均旋翼速度，ρ是空氣密度，s是旋翼密度，A是旋翼盤面積。由式(1)和式(2)可以看出，在無人機飛行速度恒定的情況下，無人機的飛行能量消耗主要與無人機的飛行時間有關(guān)，因此FANET 拓撲控制可以通過減少無人機的飛行距離來減少飛行時間，從而減少飛行能量消耗。

2.3 飛行自組網(wǎng)拓撲控制算法的分類

根據(jù)2.1 節(jié)可知，不同種類的FANET 架構(gòu)具有不同的特點，其拓撲控制算法所解決的問題也有所不同。在展平式FANET 中，拓撲控制算法主要解決無人機數(shù)量、位置和發(fā)送功率的優(yōu)化問題。在基于CDS 的FANET 中，拓撲控制算法主要在無人機位置確定的情況下解決CDS 的選擇和維護問題。在基于集群的FANET 中，拓撲控制算法則主要解決集群劃分與維護以及集群首領的選擇與維護問題。由于不同架構(gòu)FANET 中的拓撲控制算法解決的問題不同，其數(shù)學模型、原理和計算方法等也有所不同。因此，本文將FANET 拓撲控制算法分為3 類：展平式拓撲控制算法、基于CDS的拓撲控制算法和基于集群的拓撲控制算法，分別應用于展平式FANET、基于CDS 的FANET 和基于集群的FANET。此外，本文單獨設置了一類基于虛擬力的拓撲控制算法。該算法假設每個無人機節(jié)點都會受到來自其鄰居節(jié)點、障礙物、任務目標等的虛擬力，每個無人機僅需要根據(jù)其受到的虛擬力的合力自主調(diào)整位置，既可用于展平式FANET，又可用于基于集群的FANET；既可用于FANET 的初始拓撲構(gòu)建，又可用于FANET 的動態(tài)拓撲維護。因此，基于虛擬力的拓撲控制算法實際上可以歸入展平式拓撲控制算法和基于集群的拓撲控制算法。然而，基于虛擬力的拓撲控制算法使用了與其他算法完全不同的拓撲控制方法，其分布式的執(zhí)行特點非常適合用于控制自組織、高動態(tài)的FANET。此外，基于虛擬力的拓撲控制算法的設計思路簡單，其吸引力可以確保FANET 的連通性，排斥力可以確保FANET 的覆蓋性，非常適合于在確保動態(tài)FANET 連通的前提下覆蓋地面用戶。近年來，大量文獻使用基于虛擬力的拓撲控制算法來滿足FANET 的連通和覆蓋需求?；谝陨咸攸c，本文將基于虛擬力的拓撲控制算法設置為單獨的類別，以便對此類算法感興趣的讀者對其有更清晰的認識。由此，F(xiàn)ANET拓撲控制算法可以分為4 類，如表1 所示。后續(xù)章節(jié)將根據(jù)每一類拓撲控制算法所面臨的特定挑戰(zhàn)以及所使用的特定技術(shù)，對每一類拓撲控制算法進行更細粒度的分析。

表1 FANET 拓撲控制算法分類及對比

3 飛行自組網(wǎng)拓撲控制算法分析

3.1 展平式拓撲控制算法

展平式拓撲控制算法的常見應用場景有3 種，如圖4 所示。在場景1 中，任務無人機的位置由其執(zhí)行的任務確定，并且任務無人機需要與地面基站或其他任務無人機通信。拓撲構(gòu)建算法通過求解中繼無人機的部署位置，在每個任務無人機與地面基站之間以及任務無人機之間建立多跳路徑，使每個任務無人機能夠與地面基站或其他任務無人機通信。在場景2 中，所有無人機均可以執(zhí)行偵察、通信覆蓋等任務或充當其他無人機之間、無人機與地面基站之間通信的中繼。在這一場景中，拓撲控制算法主要求解各無人機的部署位置。一方面，拓撲控制算法需要優(yōu)化各無人機執(zhí)行任務的性能；另一方面，拓撲控制算法需要在各無人機之間、無人機與地面基站之間構(gòu)建多跳通信路徑，優(yōu)化FANET 的網(wǎng)絡性能。在場景3 中，所有無人機的位置已知，此時拓撲控制算法主要通過求解無人機的發(fā)送功率來構(gòu)建和維護FANET 拓撲。

圖4 展平式拓撲控制算法應用場景

根據(jù)算法的執(zhí)行階段，展平式拓撲控制算法可以進一步分為2 類：展平式拓撲構(gòu)建算法和展平式拓撲維護算法。

3.1.1展平式拓撲構(gòu)建算法

展平式拓撲構(gòu)建算法用于在沒有無人機初始位置、發(fā)送功率和連接關(guān)系等信息的情況下，從零開始構(gòu)建展平式FANET 拓撲。

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

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

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

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

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

表2 展平式拓撲控制算法的比較結(jié)果

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

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

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

3.1.2展平式拓撲維護算法

FANET 在執(zhí)行任務的過程中，其無人機的位置會根據(jù)需要動態(tài)變化。為了維持FANET 的性能，F(xiàn)ANET 的拓撲結(jié)構(gòu)也需做出相應調(diào)整。展平式拓撲維護算法主要用于在現(xiàn)有FANET 拓撲的基礎上，通過調(diào)整相關(guān)變量，更新FANET 拓撲，從而優(yōu)化FANET 的性能。

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

圖5 展平式拓撲維護算法

此外，基于功率的拓撲維護算法通過調(diào)整無人機的發(fā)送功率來改變無人機的通信范圍，從而更新FANET 拓撲，如圖5(b)所示。在不具有2-連通性質(zhì)的初始FANET 拓撲上，局部拓撲功率控制（LTPC,localized topology power control）算法[53]將初始拓撲轉(zhuǎn)化成塊割樹，并不斷添加長度最短的邊，最終生成具有2-連通性質(zhì)的FANET 拓撲。在假設初始FANET 拓撲具有k（k≥ 3）連通性質(zhì)，并且所有無人機發(fā)送功率相同的基礎上，文獻[24]算法1 采用了一種循環(huán)剪枝機制，不斷刪除當前拓撲中長度最長的邊，直到生成的拓撲具有2-連通性質(zhì)，從而求得能夠使FANET 拓撲具有2-連通性質(zhì)的無人機最小發(fā)送功率?？紤]到FANET 的拓撲連通性、平均傳輸時延與鏈路損耗，文獻[17]提出了一種基于聯(lián)盟圖博弈的自適應拓撲控制算法，通過輪轉(zhuǎn)互操作在不具有2-連通性質(zhì)的初始FANET 拓撲上添加邊，最終實現(xiàn)拓撲連通性、平均傳輸時延與鏈路損耗3 種性能之間的權(quán)衡優(yōu)化。

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

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

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

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

3.2 基于CDS 的拓撲控制算法

基于CDS 的拓撲控制算法主要在無人機位置已知的情況下構(gòu)建和維護CDS 來實現(xiàn)對FANET 的拓撲控制，其應用場景如圖6 所示。例如，當多無人機在執(zhí)行野火監(jiān)控、信息采集、野外救援等任務時，各無人機的位置由其執(zhí)行的任務而決定。此時，基于CDS 的拓撲控制算法通過構(gòu)建和維護CDS，將絕大多數(shù)轉(zhuǎn)發(fā)操作集中于少量的支配節(jié)點，從而完成FANET 拓撲控制。

圖6 基于CDS 的拓撲控制算法的應用場景

根據(jù)算法的執(zhí)行階段，基于CDS 的拓撲控制算法可以分為2 類：CDS 構(gòu)建算法和CDS 維護算法。

3.2.1CDS 構(gòu)建算法

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

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

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

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

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

表3 基于CDS 的拓撲控制算法的比較結(jié)果

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

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

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

3.2.2CDS 維護算法

由于FANET 的高度動態(tài)性，CDS 構(gòu)建算法構(gòu)建的CDS 無法保證永久有效。此時，如果使用CDS構(gòu)建算法重構(gòu)CDS，可能會產(chǎn)生較高的拓撲控制成本。在這一背景下，CDS 維護算法主要用于動態(tài)更新FANET 中的CDS，最小化CDS 更新的成本。

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

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

在優(yōu)化目標方面，更新節(jié)點數(shù)量可以反映算法的通信開銷，因此CDS 維護算法可通過最小化更新節(jié)點的數(shù)量來最小化通信開銷。此外，當CDS維護算法通過調(diào)整無人機位置來維護CDS 時，CDS維護算法可以通過最小化無人機的移動距離，以盡快完成拓撲維護并減少無人機的能量消耗。在執(zhí)行方式方面，分布式的執(zhí)行方式更適合于CDS 維護算法，但分布式CDS 維護算法具有較高的通信開銷。

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

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

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

3.3 基于集群的拓撲控制算法

基于集群的拓撲控制算法主要在無人機位置已知的情況下通過集群劃分和首領選擇來實現(xiàn)對FANET 的拓撲控制，其應用場景如圖7 所示?；诩旱耐負淇刂扑惴ㄅc基于CDS 的拓撲控制算法的應用場景較類似，但其構(gòu)建出的基于集群的FANET 與基于CDS 的FANET 具有不同的特點（詳見2.1 節(jié)）。

圖7 基于集群的拓撲控制算法的應用場景

根據(jù)算法的執(zhí)行階段，本文將基于集群的拓撲控制算法分為集群構(gòu)建算法和集群維護算法。其中，集群構(gòu)建算法負責進行集群劃分和集群首領選擇，從而形成初始的FANET 拓撲；集群維護算法則通過更新集群首領以及集群成員來維護FANET 拓撲。

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

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

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

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

文獻[67]提出了一種集群控制方法來解決FANET 中的無人機高移動性和拓撲動態(tài)變化問題。在集群劃分方面，該方法使用了一種改進的k均值算法來劃分初始無人機集群。在首領選擇方面，考慮到無人機高移動性和拓撲動態(tài)變化，使用以下適應度函數(shù)來選擇集群首領

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

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

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

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

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

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

文獻[74]提出了一種FANET 集群控制方法來解決無人機的高移動性問題。首先，每個無人機根據(jù)以下適應度函數(shù)來計算自己的適應值

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

為了在時延約束下最大化無人機的覆蓋性能，文獻[75]提出了一種基于貪心思想的集群控制算法。首先，該算法通過添加或刪除單個集群首領的方式來確定最終的集群首領，隨后，其余無人機選擇與其時延最小的集群首領并加入該集群。

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

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

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

3.3.2集群維護算法

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

選擇備用集群首領代替離開的集群首領以及重新選擇集群首領是維護集群首領的常用方式，而能量指標是維護集群成員的主要依據(jù)。由于各無人機的位置頻繁變化，集群維護算法需要高頻率執(zhí)行。因此，選擇備用集群首領比重新選擇集群首領更適合于基于集群的拓撲控制算法。

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

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

3.4 基于虛擬力的拓撲控制算法

基于虛擬力的拓撲控制算法是一種分布式拓撲控制算法，該算法假設每個無人機節(jié)點都會受到來自其鄰居節(jié)點、障礙物、任務目標等的虛擬力，該虛擬力的大小通常和無人機與鄰居節(jié)點、障礙物、任務目標之間的距離有關(guān)。由此，每個無人機僅需要根據(jù)其受到的來自鄰居無人機、障礙物、任務目標等的虛擬力的合力自主調(diào)整位置。

本文將基于虛擬力的拓撲控制算法中的虛擬力分為4 類：吸引力、排斥力、障礙避免力和任務力，如圖8 所示。這4 種力分別用于實現(xiàn)以下4 個目標：1) 各無人機能夠保證網(wǎng)絡的連通性以進行信息交換；2) 無人機之間能夠保證期望的距離，避免發(fā)生碰撞；3) 無人機能夠繞過障礙物；4) 無人機集群能完成既定的任務。下面，本文將根據(jù)虛擬力的種類及其實現(xiàn)的目標對基于虛擬力的拓撲控制算法進行詳細的分析。

圖8 虛擬力種類

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

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

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

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

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

文獻[78]提出了一種基于虛擬力的拓撲控制算法，可用于在基于集群的FANET 中控制集群成員跟隨集群首領移動，且控制整個FANET 完成區(qū)域覆蓋任務。維持網(wǎng)絡連通性的吸引力和保持無人機距離的排斥力由同一計算式給出

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

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

在空中無人機為地面孤立用戶提供多跳中繼服務的場景中，文獻[79]提出了一種基于虛擬彈簧模型的拓撲控制算法。鏈路的通信質(zhì)量可以用鏈路預算表示為

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

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

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

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

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

表4 基于虛擬力的拓撲控制算法的比較結(jié)果

目前，基于虛擬力的拓撲控制算法主要適用于多個無人機以自組織的方式形成FANET 來為地面設備提供通信覆蓋服務（例如，在災難救援場景中，自組織的FANET 作為空中基站為災區(qū)用戶提供通信服務）。此外，基于虛擬力的拓撲控制算法還可用于保持無人機之間的分層結(jié)構(gòu)或特定隊形。

基于虛擬力的拓撲控制算法重點關(guān)注FANET的連通性和覆蓋性能。在網(wǎng)絡性能方面，基于虛擬力的拓撲控制算法可以保證FANET 的連通性，但不關(guān)注時延、丟包率等性能的優(yōu)化。在任務性能方面，基于虛擬力的拓撲控制算法可以實現(xiàn)FANET對目標區(qū)域或目標用戶的覆蓋，但不關(guān)注用戶吞吐量等通信質(zhì)量的優(yōu)化。針對基于虛擬力的拓撲控制算法存在的不足，一方面，可以考慮在設計虛擬力時引入端到端時延、用戶吞吐量等指標，使端到端時延、用戶吞吐量等指標影響無人機所受到的虛擬力大小。另一方面，可以考慮將基于虛擬力的拓撲控制算法與其他種類的拓撲控制算法相結(jié)合（例如，在利用基于虛擬力的拓撲控制算法滿足FANET 的連通和覆蓋需求后，各無人機進一步調(diào)整自己的位置，從而在維護網(wǎng)絡連通性的前提下進一步優(yōu)化FAENT 的端到端時延等網(wǎng)絡性能以及用戶吞吐量等任務性能），實現(xiàn)不同種類算法之間的優(yōu)勢互補。

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

當前，F(xiàn)ANET 拓撲控制仍處于發(fā)展階段。本節(jié)討論并總結(jié)了FANET 拓撲控制仍面臨的挑戰(zhàn)以及未來的研究方向。

1) 通信鏈路頻繁中斷

現(xiàn)有的FANET 拓撲控制算法大多假設無人機之間以及無人機與地面基站之間能夠維持穩(wěn)定的通信。而在真實的FANET 中，無人機密度較低且具有高度的動態(tài)性和不確定性，因此無人機之間以及無人機與地面基站之間的通信鏈路頻繁中斷。在無人機通信鏈路間歇性連接的場景中，設計一種有效的FANET 拓撲控制算法是一項艱巨且具有實際意義的任務。

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

FANET 中的無人機具有高度的動態(tài)性和不確定性，相應地，F(xiàn)ANET 拓撲控制算法需要高頻率動態(tài)執(zhí)行以實時更新FANET 拓撲，從而維持FANET的性能。FANET 拓撲控制算法的高頻率動態(tài)執(zhí)行對算法的收斂時間、通信開銷、實現(xiàn)的性能等方面提出了嚴格的要求。然而，目前只有少量FANET 拓撲控制算法能夠滿足高頻率動態(tài)執(zhí)行的要求，有待于進一步研究開發(fā)。

3) 評估工具

FANET 拓撲控制的相關(guān)研究在仿真實驗中使用了多種不同的仿真工具，例如，NS-2、OPNET、OMNET++、MATLAB 等。然而，這些仿真工具在3D 場景、通信信道和移動模型等方面的建模還不能很好地支持FANET 的特殊要求。為了有效地評估FANET 拓撲控制算法的性能，需要開發(fā)一種支持FANET 特性的仿真工具。

4) 安全問題

FANET 的拓撲結(jié)構(gòu)是一種重要的網(wǎng)絡資產(chǎn)，且嚴重影響FANET 的安全性。例如，當使用分層式FANET 執(zhí)行偵察等任務時，根據(jù)FANET 的拓撲結(jié)構(gòu)，敵方能夠輕易地識別出其中的領導者無人機。此時，敵方僅需破壞乃至劫持少量的領導者無人機，就可對我方的FANET 造成嚴重損害。因此，在具有安全性需求的場景中，F(xiàn)ANET 拓撲控制算法需要生成能夠隱藏無人機相關(guān)信息的FANET 拓撲。

5) 任務性能和通信性能

FANET 的任務性能需求和通信性能需求之間通常是矛盾的[34,51]，而大多數(shù)FANET 拓撲控制算法沒有考慮這一特性。為此，F(xiàn)ANET 拓撲控制算法生成的FANET 必須同時滿足FANET 的任務性能需求和通信性能需求，實現(xiàn)FANET 任務性能和通信性能之間的平衡。

6) 故障恢復

現(xiàn)有的FANET 拓撲控制算法主要通過生成具有容錯性的FANET 拓撲來應對FANET 發(fā)生的故障，而不是在FANET 發(fā)生故障后快速恢復有效的FANET 拓撲。事實上，具有容錯性的FANET 拓撲只能應對FANET中極少數(shù)無人機發(fā)生故障的情況，因此，在FANET 部分無人機發(fā)生故障后快速恢復有效的FANET 拓撲更符合實際的需求，相關(guān)的FANET 拓撲控制算法也需要進一步研究。

5 結(jié)束語

本文對現(xiàn)有的FANET 拓撲控制研究進行了綜述。首先，分析了相關(guān)綜述的不足，并指出了本文的貢獻。隨后，介紹了FANET 的網(wǎng)絡架構(gòu)以及FANET 拓撲控制的研究框架和需求和分類方法。之后，對每一類FANET 拓撲控制算法都進行了詳細的分析。最后，總結(jié)了FANET 拓撲控制仍需解決的問題以及未來的研究方向。