基于多重虛擬力控制的無人機覆蓋編隊分簇算法

汪鎮濤 李大鵬 丁良輝 楊錦彬

近年來,移動通信網絡的進步加快了無人機（unmanned aerial vehicle,UAV）技術的發展.過去十年中,研究人員在多UAV 的分布式協同控制方面做了許多工作[1].如今,UAV 憑借其易部署、高機動和無人操作等優勢,在各個領域得到了廣泛應用,由多個UAV 組成的FANET 也應運而生.FANET 繼承了自組織網絡靈活性高、動態重構性強、高自主性等優點,既是未來UAV 協同作業的一種重要形式[2],也是時空的一致統一、信息的一致表達和態勢的一致理解[3].現有研究中,一部分工作聚焦于任務規劃,如目標定位、航跡規劃、能耗優化和區域覆蓋等[4-6].另一部分研究則集中在更高層級上,如分布式傳感和協同導航等[7].而在諸多任務應用中,區域覆蓋是一項常見且重要的任務需求,適用于很多場合,如災后區域的通信恢復、電子對抗以及車機協同的偵查路徑規劃[8-9].

區域覆蓋按狀態可分為靜態覆蓋和動態覆蓋.靜態覆蓋是全局的、離線的,通常假定目標區域環境信息不變,規劃出最優解后執行任務,實用性較差.因此,近年來的研究方向逐漸轉向動態覆蓋.動態覆蓋則需依靠UAV 傳感器實時生成周圍環境信息,處理非結構化的環境.因此,動態覆蓋問題更關注移動控制策略的選取.

移動控制方面,文獻[10]提出了隨機路點移動控制策略（random waypoint model,RWP）,UAV 的速度方向在給定的速度區間內隨機選擇（服從均勻分布）.這種策略的優勢是簡單且高可用,但覆蓋率波動幅度較大,且難以保證穩定的高連通性.隨機游走移動策略（random walk,RW）則類似于RWP,不同之處在于它不設置移動的目的地,在設定的運動時間到達后就停止.在此基礎上,衍生出了兩種改進方向,一種基于高覆蓋率進行改進,另一種則基于高連通性.文獻[11]提出一種基于高覆蓋率的移動控制策略（coverage-based model,CVB）,基于虛擬力算法設計了兩重虛擬力來穩定高覆蓋率,但犧牲了連通性,且兩重虛擬力設計過于簡單,沒有考慮完整覆蓋過程,也沒有對區域邊緣處理,仍有優化重疊覆蓋的空間.文獻[12]提出一種基于高連通性的策略（connectivitybased model,CNB）,引入樹型結構維護FANET,將基站視作樹的根節點,通過預測單跳鄰居的未來位置來構建樹.面向連接的移動控制策略更傾向于提高連通性[13],但犧牲了覆蓋率,同時魯棒性較低,在更復雜的FANET 結構下將無法保證高連通性.文獻[14]中考慮了能量約束下的覆蓋問題,并將剩余能量、鄰居數等指標加權后的權值作為節點被跟隨的推薦度.以上研究盡管在連通性上達到了不錯的性能,但均基于網絡沒有斷連等意外的理想情況.在實際應用中,此類策略無法有效提升孤立節點可用性,且犧牲覆蓋率的同時沒有改善魯棒性,仍不適用于FANET結構復雜化的場景.于是又引入了分簇算法來對大規模組網進行管理.

FANET 具有高移速、拓撲變化快、節點密度低的特點[15],一個FANET 往往由多個簇組成并管理.每個簇內分為簇頭（cluster heads,CH）和簇成員（cluster member,CM）兩種節點類型.所有簇頭共同組成骨干路由網絡.FANET 中的主要通信形式為簇間通信和簇內通信.簇間通信由各個簇頭完成,匯聚節點首先將消息廣播到各個簇頭,簇頭間通過骨干網絡進行消息共享與數據同步.簇內通信一般以每個簇為單位,簇內CM 與自己的CH 進行通信.在分簇方面,簇頭除了管理簇成員外,還要維持簇間通信,簇頭選擇的好壞對網絡性能有著直接的影響.文獻[16]提出了最大節點度算法（highest-degree algorithm,HD）,鄰居節點之間通過彼此定期發送消息確認關系,每輪始終選擇最大度節點作為簇頭,簡單高效,但在高速移動的場景下簇頭變換頻繁,浪費節點資源.最小身份標識號（lowest identity document,LID）算法與HD 類似.這類算法在整體上會讓簇的數量減少,并且沒有考慮到網絡移動性[17],當節點高速移動時,簇頭變換頻繁,易導致網絡不穩定.

為了解決此問題,考慮多重指標的加權分簇算法[18]（weighted clustering algorithm,WCA）隨之被提出.通過給不同的度量指標分配不同的權重,有傾向性地進行自適應分簇,選擇權重最小的UAV 作為簇頭[18].這類分簇算法有效降低了簇頭切換率,提高了簇結構的穩定性,實現了負載均衡.但無法根據移動趨勢維護、更新簇,不適用于結構快速變化的動態場景.由于節點的移動性會對分簇性能造成較大影響,一些基于移動性的預測分簇算法也隨之被提出,文獻[19-20]分別通過引入字典樹和預測節點運動狀態,提出一類基于移動性的預測分簇算法,有效解決了動態場景對分簇性能的影響.但以上優化僅針對分簇性能,雖然部分研究同時考慮了連通性,但忽略了優化覆蓋率.原因在于覆蓋率和連通性是一對矛盾指標.在區域覆蓋問題上,當下研究的重點聚焦在如何讓一個大規模的無人機組網能夠移動到目標區域,在擴大覆蓋率的同時,保持一定的網絡連通性.

在此基礎上,結合移動控制和分簇算法,文獻[21]提出一種基于移動控制的分簇算法（mobility control based clustering,MOOC）,同時考慮了覆蓋效率和連通性,但移動控制策略是類似文獻[11]的二重虛擬力策略,力的結構設計過于簡單,對環境適應度較低,也沒有考慮UAV 層級以及所處環境位置對虛擬力的影響.

現階段對于覆蓋任務的研究仍存在以下問題：移動策略上,大多只考慮了覆蓋率或連通性其中一項指標；虛擬力算法的設計過于簡單,沒有考慮邊緣震蕩和孤立節點問題；對大規模UAV 組網沒有詳細分層.分簇算法上,主要優化了分簇性能,部分考慮了連通性,但忽略了最大化覆蓋率；節點的高移動性始終被當作影響分簇性能的不利因素來處理.最后,以上研究局限于覆蓋任務過程中的某個階段,均沒有對覆蓋任務的全過程進行劃分和對完整流程分析.

針對以上問題,本文提出了一種基于多重虛擬力控制的編隊分簇算法.研究工作的主要貢獻有以下幾點：

1）設計了一種基于多重虛擬力的移動控制策略（mobile control strategy based on multiple virtual forces,MVFS）.基于leader-follower 對UAV 進行分層,將覆蓋任務的完整過程分為3 個階段,設計了四重虛擬力,通過力的輸入改變和組合,MVFS 會在不同的階段對不同類型的UAV 節點產生不同的合力.此外還考慮了區域邊緣震蕩的影響,在保證了連通性的同時,又能提高區域覆蓋率.

2）提出了一種基于MVFS 的編隊分簇算法（mobile-based clustering algorithm,MBCA）.將UAV 的高移動性當作維持連通和擴大覆蓋的有利條件.在任務執行時出現斷連、重疊等問題后,可以依靠UAV的高機動性迅速恢復網絡.MBCA 在提高覆蓋和連通性能的同時,相比于傳統分簇算法,也提高了分簇性能.此算法也適用于靜態網絡.

3）結合移動控制分簇算法提供了一個完整的覆蓋任務流程,同時包含靜態覆蓋和動態覆蓋場景.在先前的研究中,UAV 往往初始部署在目標區域內,本文則將UAV 部署在與目標區域A 完全不重疊的區域B 上,更具實用性.同時上文提出的算法可以部署在任務執行的全過程.

1 系統模型與問題描述

區域覆蓋任務的定義如下,N 架UAV 構成集合Q={Q1,Q2,…QN}被隨機部署在初始區域A.目標區域B 位于A 的東北方向,兩塊區域完全不重疊.表1 列出了系統中主要的參數.

表1 主要參數Table 1 Main parameters

區域覆蓋任務要解決的問題是在維持高網絡連通性的情況下,最大化FANET 的整體覆蓋率.假設FANET 中t 時刻孤立節點的數量為,t 時刻的網絡連通性定義為：.假設覆蓋區域面積為A,FANET 理想覆蓋總面積為,理想最大覆蓋率定義為.

FANET 在初始化基本分簇后,匯聚節點開始以固定速度向目標區域移動,帶動整個網絡移動.到達設定時長后,匯聚節點停止移動,與其連接的各個簇繼續部署,直到覆蓋任務結束.連通后的UAV 彼此可以傳遞自己的狀態信息（包含速度,位置,方向等）.UAV 運動的動力學模型定義如下：

pi是UAV Qi的位置信息,vi是Qi的速度,ui是的Qi加速度.UAV Qi的速度方向表示為.

假設每個UAV 能夠探測到以自身為中心的半徑為RC的圓形區域.UAV 彼此的最大通信距離為RT,若彼此間距離超過了RT,就無法通信.不失一般性,假設RC＞2RT.根據文獻[22]中推導,傳感器之間通信距離至少為傳感器探測距離的2 倍,是保證有效范圍內完全覆蓋的同時保持網絡連通的充分必要條件.這個定理保證了研究重心始終在覆蓋問題上.

2 MBCA

MBCA 由MVFS 和編隊分簇兩個模塊組成.算法架構如圖1 所示.本文將一個由A 到B 的區域覆蓋任務按時間點分為3 個階段：初始化部署、動態覆蓋和半靜態覆蓋.MBCA 作用于覆蓋任務的3 個階段.3 個階段定義如下：

圖1 算法架構圖Fig.1 Architecture diagram of algorithm

1）初始化部署：所有UAV 保持靜止,執行MBCA 進行初始分簇,構建初始拓撲結構.

2）動態覆蓋：匯聚節點以固定速度移動,所有節點受MVFS 策略控制,選擇跟隨目標移動.

3）半靜態覆蓋：匯聚節點到達指定目標地點后停止移動,MVFS 策略轉為半靜態模式,其余節點受到的虛擬力策略發生變化,持續移動直到任務結束.在每個離散的時間步里,網絡根據MVFS 策略整體移動后,都會執行MBCA 算法對整個網絡進行重新維護,維持簇結構.

2.1 MVFS

本節引入虛擬力算法,設計了4 類不同的虛擬力,并以這4 類力為基礎,設計了MVFS,包含動態模式策略和半靜態模式策略,應用于覆蓋任務中兩個不同階段.針對不同時段FANET 的狀態,MVFS 可以靈活切換控制策略.

2.1.1 MVFS 的動態模式策略

動態模式下,FANET 中包括匯聚節點在內的所有節點都是運動的.網絡中的節點會在3 類虛擬力的影響下以領航跟隨策略為框架進行移動,分別是鄰居間的動態力、側向力以及區域邊緣力.為了防止UAV 之間距離過近,導致重疊覆蓋降低覆蓋效率,同時又考慮到距離過遠產生斷連,定義一種動態力,當實際距離小于設定期望距離時,表現為斥力,大于期望距離時,表現為引力.Qi作為跟隨者,Qj作為領航者,受到的動態力定義為：

dij是Qi和Qj之間的歐式距離.α∈(0,1],αR 是設定的期望距離.R 為輸入變量,對于節點在網絡中所擔任的位置不同,R 會賦予不同的值.當實際距離大于期望距離時,,表現為引力,方向從Qi指向Qj,kT是引力系數,假設引力方向為正方向.當dij＜αR 時,表現為斥力,方向相反,kR是斥力系數.文獻[23]給出了斥力系數與引力系數的關系

并與不同參數進行了覆蓋率上的對比,驗證了這種關系的可行性.其中,m 和n 為目標矩形區域的邊長,則根據覆蓋任務對重疊覆蓋的容忍程度自由設定.Qj跟隨的領航者的選取將在分簇算法中詳細介紹.

當引力與斥力合力恰好為0 時,此時UAV 受力平衡,基于引力和斥力的傳統虛擬力算法此時會陷入局部最優,節點不再移動.通常增加額外的力即可跳出這種情況,但代價是增加了算法復雜度.后文設計了3 種全新的虛擬力,除了可以降低陷入此種局部最優的概率,還能進一步提升覆蓋率.此外,動態力的引入只能解決跟隨者和領航者之間的重疊與斷連問題,由于匯聚節點運動的方向始終不變,整體網絡的運動趨勢會與匯聚節點的方向保持一致,這會導致跟隨者之間發生重疊問題.為此,引入第2 類虛擬力即側向力,定義為：

kC是側向力系數,β∈(0,1],βD 是Qi和Qj之間期望側向距離,dve 是跟隨者與領航者之間的實際側向距離.D 是輸入變量.的方向垂直于Qj的速度方向.側向力的設置讓Qi在跟隨Qj的同時,控制Qi的側向移動,使隊形有效展開,擴大覆蓋率的同時沒有破壞原本網絡的連通性.

第3 類虛擬力為邊緣力,來自于目標區域4 個邊緣產生的虛擬勢場,主要作用于半靜態覆蓋過程中.在MVFS 動態模式下,僅僅作用于孤立節點.定義如下

以往研究中對于失聯節點的處理方式都是保持上一狀態的速度方向運動,直到再次連上FANET.這種方案缺少可靠性,一旦上一狀態的方向出現偏差就可能導致節點永久失聯.邊緣力針對移動過程中失聯的孤立節點進行吸引,即便方向出現偏差,也能讓孤立節點調整回正確的方向,增加了恢復連接的可能性.

因此,在動態模式下,UAV Qi所受到的合力如圖2 所示,定義為：

圖2 動態模式下Qi 受力Fig.2 Force analysis of Qi in dynamic mode

R 和D 都是自變量,根據UAV 在網絡中擔任的角色不同,有不同的取值.UAV 動力學模型的控制輸入通過合力Fi構建：

動態模式的策略重心在于盡可能保證節點連通,在此基礎上擴大覆蓋率.值得一提的是,盡管這只是區域覆蓋任務中的一個過渡階段,但是在此階段進行覆蓋性能的優化是有必要的,在MVFS 控制下,匯聚節點到達目標點懸停后,整個網絡就已經保證了一定的覆蓋率,在此基礎上進行進一步覆蓋,效率上將超出其他方案.

2.1.2 MVFS 的半靜態模式

半靜態模式處理的是移動覆蓋任務中的第3 階段.此時匯聚節點到達目標區域保持懸停,剩余節點繼續移動.此時網絡中除匯聚節點外,所有節點受到4 類虛擬力影響：包括動態力、側向力、邊緣力以及橫向力.由于匯聚節點停止移動的時刻,無法保證各個節點之間距離到達設定期望距離,處于FANET 中的節點仍然需要匹配領航者進行移動,所以在半靜態模式下,動態力與側向力定義與前文保持一致,邊緣力的定義將發生一定改變.構成的矩形區域B 表示為AreaB.半靜態模式下的邊緣力定義如下：

當Qi移動出區域邊緣時,邊緣力表現為引力,隨距離的減小而減小.當Qi處于區域內部時,邊緣力表現為斥力.

第4 類虛擬力是作用于CM 的橫向力.第2 類側向力是基于領航者速度方向進行的調整,只能最低限度地保證同簇的CM 之間不會產生一定的重疊,而鄰簇之間的CM 仍然有重疊的可能.橫向力的引入可以同時解決這兩項重疊問題.另外,考慮到在動態模式中UAV 網絡可能會出現相對頻繁的拓撲變換,所以沒有在動態模式中直接引入橫向力.UAV Qi受到鄰居CM Qj的橫向力的定義如下：

其中,kR是橫向力系數,γL 是CM 之間期望距離,,此處L=2RC.作用在Qi上的橫向力方向由Qj指向Qi.Qi會受到所有鄰居施加的橫向力,合成后即為受到的總橫向力.Qi的鄰居集定義為：,Qi受到橫向力定義為

在半靜態模式下,Qi最終所受合力如圖3 所示,定義為：

圖3 半靜態模式下Qi 受力Fig.3 Force analysis of Qi in semi static mode

對于自變量R 與D,將在分簇算法中根據Qi的類型,賦予不同的值.

2.2 編隊分簇算法

以MVFS 作為移動控制策略,本節設計了編隊分簇算法.主要分為3 個模塊：簇的建立,簇的移動以及簇的維護模塊.簇的建立過程與傳統分簇算法類似,重點是選出簇頭.簇的移動將根據節點類型的不同（ON,CH,CM）,分為3 種控制策略.簇的維護過程則是基于連通性,對出簇、入簇的節點進行管理.每個CH 維護各自的子簇表,包含簇內的CM 信息以及簇的規模.

2.2.1 簇的建立/選舉

在簇的建立階段,核心是簇頭的選舉.每個孤立節點周期性給通信范圍內的其他孤立節點發送hello報文,其他節點收到后返回確認消息,建立鄰居關系.鄰居之間可以彼此交換狀態信息（包括自身位置、速度、方向）.一段時間之后,所有節點中擁有最大度的節點向自己的鄰居廣播CH-hello 報文,宣布自己成為CH 節點,該節點的鄰居在收到CH-hello 報文后,更新鄰居列表,計算自身與收到消息的CH 之間的距離,選擇距離最近的CH,返回CH-confirm 消息確認加入此簇,如果CH 沒有收到確認消息,將在鄰居表中刪除此節點.CH 如果收到了另一個CH 發送的CH-hello 報文,也可根據簇規模的大小選擇放棄CH身份,合并入鄰簇.在覆蓋任務執行的任意時刻,都可以觸發CH 選舉的功能,為孤立節點建立子簇.

2.2.2 簇內移動控制

簇內CM 將受到動態力、側向力與邊緣力.所有子簇的CH 與CM 構成簇內移動控制的所有成員.子簇內所有CM 的移動以領航跟隨法為框架,使用MVFS 策略進行移動.每個CM 作為跟隨者,所在簇的CH 作為CM 共同的跟隨者.在多跳模式下,CM 也可以跟隨下一跳到CH 的CM 節點.CM 的控制目標是減少彼此和CH 之間的重疊覆蓋,同時保持和CH的連接.

基于MVFS 策略,子簇內每個CM 所受合力為

2.2.3 簇間移動控制

簇間CH 將受到4 類力.所有CH 與匯聚節點構成簇間移動控制的所有成員.為了保持連通性,多個子簇之間需要通過匯聚節點進行同步和信息傳遞.以往的分簇算法中,往往假設匯聚節點具有強大的性能,所有網絡中的節點都能以單跳或多跳的傳輸方式與匯聚節點通信[23].為了保持高連通性,匯聚節點的通信距離往往被設定為一個很大的值.這種集中式的計算方法不具備高可用性.大量信息處理會使匯聚節點負載增加.一旦匯聚節點出現宕機,其余網絡節點不具備接管匯聚節點職責的能力.

針對這些問題,對匯聚節點采用了一種自適應調整通信距離的方法,以均衡負載,提高可用性.匯聚節點的初始通信距離與其余CH 節點相同,如果在此距離內探測到任意CH,則與這些CH 建立鄰居關系,并完成同步,其余未被探測到的CH 通過多跳傳輸與直連的CH 通信,完成與匯聚節點的間接通信.當匯聚節點無法探測到CH 時,會周期性地調整自己的通信距離,再發送鄰居請求,直到連接上任意CH節點.這種自適應調整大大降低了對匯聚節點的性能要求,同時,在匯聚節點宕機后,CH 節點能夠立刻接管匯聚節點的職能.因此,CH 將依據跟隨節點的不同而被分為兩類：直接與匯聚節點建立鄰居關系的直連CH 與通過多跳通信間接跟隨的多跳CH.直連CH 作為跟隨者直接跟隨匯聚節點,形成sink-CH 的領航跟隨模式,多跳CH 跟隨距離自己最近的直連CH,形成CH-CH 的跟隨模式.在移動層面上,可以將每個CH 的移動看作整個子簇的移動,匯聚節點與所有CH 同時也構成一個大的子簇,匯聚節點是所有CH 的簇頭,CH 直接或間接跟隨匯聚節點產生移動,如圖4 所示.

圖4 簇間移動結構Fig.4 Inter-cluster mobility structure

簇間移動策略也類似于簇內移動,但由于簇結構會隨節點的移動而不斷變化,且CH 存在合并的情況,處于CH-CH 模式的CH 如果傳入固定的最大通信距離,已經固定的節點將對其余節點的移動產生主導作用,從而導致移動節點最終只分布在固定節點周圍,導致另一種局部最優.對此,采用一種預測通信距離的方法來跳出局部最優,在這種情況下,CH將受預測距離主導,移動相對Sink 這一固定節點更遠的位置,實現全局覆蓋.假設UAV 的連接狀態集表示為,分別代表連接和斷連狀態.作為CH 的UAV Qi在t 時刻與匯聚節點的連接狀態用表示,.可以使用一種基于預測的移動通信距離來估計CH 之間的通信距離,定義如下：

2.2.4 簇外移動控制

所有孤立節點構成簇外移動控制的主要成員.由于孤立節點在當前時刻不在網絡內,所以無法直接跟隨CH.因此,孤立節點的跟隨目標分為3 種情況：1）ON 可以直接與匯聚節點連接.直接跟隨匯聚節點；2）ON 無法與匯聚節點連接,ON 查詢自己的鄰居列表,隨機選擇一個節點作為領航者跟隨；3）ON 沒有鄰居,找不到節點跟隨.當ON Qi跟隨Qj時,UAV 間的通信距離為RT,最大橫向距離為2RC,所受合力與式（13）相同.如果ON 沒有鄰居可跟隨,則只受到邊緣力影響.在網絡延遲,電波干擾,環境氣候因素以及節點陷入由受力平衡導致的局部最優狀況下,原本的CM 都會退化為孤立節點.對這些斷連的,不再受到FANET 控制的孤立節點進行簇外控制,將有效幫助ON 回歸FANET,重新搜索移動路徑.

2.2.5 簇的維護

UAV 的移動建立在網絡分層的基礎上,而UAV的高機動性會破壞網絡的拓撲結構,降低連接性能.因此,要在每次移動后對UAV 網絡拓撲結構進行維護,維護完畢后,再次調用分簇算法將剩余ON 建立子簇.在維護階段,各CH 會周期性向自己的CM 發送CH-alive 請求,收到的CM 回復CM-response,在設定的重發次數到達后,CH 將未收到回復的CM 從自己的簇列表中刪除.

因UAV 移動特性而移動到CH 連接范圍內的孤立節點,會向CH 發送申請入簇的請求,CH 確認后將ON 添加到簇列表中.同時,各個CM 具有仲裁機制,當CM 在移動過程中同時收到數個CH 廣播的請求時,CM 不會立刻回復原CH,而是計算自身與數個CH 之間的距離,最后選擇距離最近的CH 回復.原CH 在請求超時后會自動將該CM 從簇列表刪除.當子簇的CH 統計自身簇規模Cs為0 時,將自動放棄CH 身份,降為ON.CH 之間交換的信息中包括簇規模Cs,當相鄰的兩簇規模相差較大時,較大簇CH 會向小簇發送merge 請求,請求合并.

3 仿真與評估

本章將根據仿真結果分析本文所提出的基于多重虛擬力控制的編隊分簇算法在區域覆蓋場景下的性能.考慮到算法的移動性,此章將對比其他移動控制策略,從覆蓋效率和連通性兩項指標進行對比.仿真的目標區域是覆蓋一個1 000*1 000 的矩形區域A,所有UAV 初始隨機部署在與A互不重疊的矩形區域B,每架UAV 之間的最大通信距離RT=120 m,覆蓋半徑RC=50 m.運動過程中,匯聚節點以固定速度15 m/s 進行移動.相關系數設定為α=β=0.9,kt=1,kC=1.5,k=0.8,δ=1,k=0.8.其他參數設定見表2.算法仿真偽代碼見表3.

表2 仿真參數Table 2 Simulation parameters

表3 仿真偽代碼Table 3 Simulation pseudocode

3.1 覆蓋效率和連通性

針對UAV 的移動性,本節對比的移動控制策略有如下4 種：1）隨機路點（RWP）移動策略；2）基于覆蓋（CVB）的移動策略；3）基于連通（CNB）的移動策略；4）基于移動控制（MOOC）的策略.所對比的各項性能指標如下：

* 覆蓋效率：所有UAV 覆蓋區域占目標區域面積的比例；

* 覆蓋率變化：仿真過程中每一個時間點所對應的覆蓋效率,代表了覆蓋速度；

* 連通性：所有最終連通節點對數與最大可能連通對數的比值,當所有節點構成連通圖時,連通性為1；

* 連通性變化：仿真過程中每一個時間點所對應的連通性.

如圖5 和圖6 所示,在覆蓋率上,MBCA 分別比RWP,MOOC 和CNB 高出28.1%,51.3%和143.2%.面向覆蓋的算法盡管在覆蓋性能上稍高于本文提出的算法,但忽略了連通性,面向覆蓋的算法在連通性上只有0.2.而MBCA 在保證較高覆蓋率的同時,連通性也能穩定保持在0.9 以上.

圖5 不同節點數的覆蓋率Fig.5 Coverage rate of different number of nodes

圖6 150 節點的覆蓋率變化Fig.6 Coverage rate variation for 150 nodes

如圖7 和圖8 所示,在網絡連通性上,MBCA 分別比CVB 和RWP 高出231.4%和21.8%.面向覆蓋的算法和隨機路點算法的連通性都會隨時間衰減.MOOC 由于使用了MBCA 類似的虛擬力和最大通信距離進行分簇控制,較好地保證了移動過程中的高連通性.面向連通的算法盡管在連通性上保證了網絡連通（連通性為1）,但在覆蓋率上大大不如MBCA.

圖7 不同節點數的連通性Fig.7 Network connectivity for different number of nodes

圖8 150 節點的連通性變化Fig.8 Connectivity variation for 150 nodes

從仿真結果來看,網絡連通性和區域覆蓋率這兩個指標是相互制約相互矛盾的.面向覆蓋的算法在達到很高覆蓋率的同時,連通性幾乎完全丟失,而面向連通的算法盡管能維持1 的穩定網絡連通,但在覆蓋率上捉襟見肘.其他算法在本文的場景下也很難同時滿足兩項指標要求.MBCA 是在權衡這兩項指標后,在保持相對穩定連通的同時,達到相對較高的覆蓋率.

3.2 分簇性能

針對UAV 網絡結構的分簇性能,本節對比的分簇算法為：1）最大連通度（HD）分簇算法；2）基于移動預測（MP）的分簇算法.所對比的各項性能指標如下：

* 分簇數：仿真過程中的平均分簇數量/簇頭數量；

* 孤立節點數：仿真過程中的平均孤立節點數；

* 簇頭持續時間：節點成為簇頭并保持的平均時間；

* 簇成員持續時間：節點成為簇成員并保持在該簇的平均時間.

如圖9 和圖10 所示,MBCA 產生的分簇數量少于其他分簇算法,較少的分簇數量不但易于網絡拓撲管理,也能相對減少整個網絡的能量消耗.同時,MBCA 的平均孤立節點數也小于10,低于HD 和MP的孤立節點數.如圖11 和圖12 所示,由于引入了移動控制進行分簇,在簇頭持續時間上,MBCA 高出HD 和MP 各793.9%和679.1%,在簇成員持續時間上,則各自高出107.1%和79.9%.這是因為在HD 和MP 中節點的隨機移動引起簇結構頻繁變化,難以保證持續時間.從仿真結果看,在分簇性能上,本文所提算法優于其他兩種分簇算法.

圖9 不同節點數的分簇數Fig.9 Number of CHs for different number of nodes

圖10 不同節點數的孤立節點數Fig.10 Number of ONs for different number of nodes

圖11 簇頭平均持續時間Fig.11 Average duration of CHs

圖12 簇成員平均持續時間Fig.12 Average duration of CHs members

3.3 重構性能

由于在離散的時間點下,每次簇計算出下一步移動路徑后,都要對簇進行重構：調整節點入簇和離簇,以及簇合并與解體.在100、150 和200 節點數量的情況下,圖13 展示了在每一個時間節點,簇重構所花費的單位重構時間,圖14 展示了在每一個時間點內,重構耗時占單位時間耗時的百分比.通過仿真圖所示,在3 種不同節點的情況下,重構耗時范圍分別為[0.001 8,0.017],[0.003 8,0.017],[0.006,0.027].平均耗時分別為0.006 2 s,0.009 9 s,0.016 s.假設在每一個時間點,UAV 移動后都對簇進行維護重構,那么重構耗時占單位時間的百分比范圍分別為[1.04%,5.63%],[1.64%,6.69%],[2.34%,8.47%].即使在200 節點的大規模網絡下,重構耗時占比不會超過10%,實時性較好.

圖13 單位重構時間Fig.13 Reconstruction time of unit

圖14 重構耗時比Fig.14 Reconstruction time-consuming ratio

4 結論

本文提出了MBCA,用于完成UAV 集群場景下點到點的區域覆蓋任務.該算法同時考慮了覆蓋性能和網絡連通性.利用移動控制策略來提高前敘的兩項指標.結合移動控制、分簇算法提供了一個相對完整的覆蓋任務流程分析,同時包含了靜態覆蓋和動態覆蓋的場景.根據本文仿真結果所示,在完整區域覆蓋的場景下,本文提出的算法在覆蓋效率上比面向連接和隨機路徑算法高出143.2%和28.1%.同時網絡連通性為0.95,比面向覆蓋的算法高出231.4%.同時,對于分簇性能,在簇頭持續時間上超出傳統分簇算法793.9%.仿真結果表明,MBCA 在有效提高覆蓋效率的同時,能保證相對穩定的連通性,在分簇性能上也優于其他算法.