一種自適應無人機集群網(wǎng)絡恢復方法

石運陽，華 翔，張金金

（西安工業(yè)大學電子信息工程學院，西安 710021）

0 引言

無人機集群是由多架無人機組成的一個完整的有機系統(tǒng)，集群內部的無人機通過無線自組織網(wǎng)絡建立連接，構建成一個整體的作戰(zhàn)單元，從而具備在復雜多變環(huán)境中執(zhí)行危險任務的能力。無人機集群在執(zhí)行任務過程中，無人機個體的移動會導致網(wǎng)絡中的鏈路頻繁改變，惡劣環(huán)境的影響也會使得部分節(jié)點失效［1］，這些都會導致集群網(wǎng)絡的間歇連接和動態(tài)拓撲，使得網(wǎng)絡結構受損，降低無人機集群網(wǎng)絡的連通性能，影響集群的正常通信［2］。因此，無人機集群網(wǎng)絡的拓撲修復應當是在網(wǎng)絡出現(xiàn)結構性損傷后，自適應調整局部節(jié)點之間的鏈路，以保證網(wǎng)絡整體的連通性。

目前，通信節(jié)點自適應進行鏈路重選的方法主要有兩種，分別是基于網(wǎng)絡結構特征的鏈路重選機制以及基于網(wǎng)絡負載程度的鏈路重選機制。

基于網(wǎng)絡結構特征的鏈路重選機制是利用幾何方法對集群網(wǎng)絡拓撲結構進行分析。馬學森等［3］針對無線自組網(wǎng)最優(yōu)傳輸路徑問題，提出基于蟻群算法的路徑尋優(yōu)和恢復算法，該算法有效降低了節(jié)點的能量消耗，在出現(xiàn)節(jié)點死亡時可以對最優(yōu)路徑進行快速恢復。姚玉坤等［4］針對自組網(wǎng)網(wǎng)關節(jié)點失效問題，通過馬爾可夫鏈路狀態(tài)預測模型，提出了基于無人機-地面控制站鏈路狀態(tài)預測的網(wǎng)關選擇算法。李玉龍等［5］針對貪婪路由協(xié)議不能準確反映節(jié)點位置的問題，提出了一種基于移動預測和鏈路保持時間的路由協(xié)議MP?GPSR，綜合考慮節(jié)點的移動位置和鏈路保持時間來選擇下一跳，避繞路由空洞，降低了傳統(tǒng)邊界轉發(fā)的路徑冗余。

基于網(wǎng)絡負載的鏈路重選機制是確保無人機節(jié)點能有效傳輸其負載對象。對于隨機路徑移動模型，康巧琴等［6］提出了基于效用值轉發(fā)的路由快速恢復算法。綜合利用網(wǎng)絡時延、節(jié)點效用值和下一跳數(shù)三個指標得到最優(yōu)的下一跳節(jié)點。該算法平均跳數(shù)少、成功概率高、平均時延低。肖軍弼等［7］將SDN 網(wǎng)絡架構引入故障恢復策略，根據(jù)域間域內跳數(shù)、帶寬總量、已使用的鏈路帶寬進行通信代價權值評價，生成域間相交最小的備用路徑。孫明杰等［8］提出了基于蟻群優(yōu)化的路由算法，該算法將蟻群信息素與路由算法相結合，大大減少了路由擁塞和鏈路斷路的情況。

然而，相較于傳統(tǒng)移動自組網(wǎng)，無人機集群自組織網(wǎng)絡節(jié)點之間的相對速度更大，鏈路質量變化也更加頻繁［9］，因此對于無人機集群網(wǎng)絡恢復算法的設計應當著重考慮無人機的移動性和拓撲時變性。傳統(tǒng)的網(wǎng)絡恢復算法可以可靠地尋找下一跳備選節(jié)點，但是在無人機領域會在時效性方面存在一定的不足。因此如何設計出適用于無人機高速動態(tài)拓撲的自組織網(wǎng)絡恢復算法是目前無人機集群網(wǎng)絡研究領域的熱點和難題。

針對以上問題，本文提出一種自適應無人機集群網(wǎng)絡恢復算法。首先，每個無人機節(jié)點利用鯨魚算法優(yōu)化后的灰色滾動模型對節(jié)點之間的通信代價進行預測。然后，當集群中的部分節(jié)點失效后，待恢復節(jié)點通過最短路徑算法和負載均衡算法根據(jù)預測結果找到節(jié)點之間的最短路徑，實現(xiàn)集群網(wǎng)絡的自適應損傷恢復。最后，對算法進行仿真分析，驗證恢復算法的時效性、恢復后網(wǎng)絡的有效性和抗毀性。

1 無人機集群網(wǎng)絡拓撲映射模型

無人機集群編隊在飛行過程中往往是整體朝著一個既定目標進行移動［10］。本文基于復雜網(wǎng)絡理論對無人機集群網(wǎng)絡進行建模，采用圖論方法對其進行抽象，將無人機的節(jié)點與鏈路映射到復雜網(wǎng)絡模型中，考慮了無人機之間信號的功率強度、相對速度以及節(jié)點負載度等因素，將無人機的連通性恢復問題轉化為復雜網(wǎng)絡的邊重連問題。

1.1 集群網(wǎng)絡通信代價權值指標

考慮無人機集群網(wǎng)絡拓撲時變的特點，結合無人機節(jié)點屬性參量因子，由單位時間內無人機之間的通信關系建立無人機集群通信網(wǎng)絡結構模型。將整個無人機通信網(wǎng)絡抽象為圖G(V,E,W)，其中，V(G)表示所有節(jié)點的集合，E(G)表示所有邊的集合，|V|代表節(jié)點的個數(shù)，|E|表示通信鏈路的數(shù)量，根據(jù)單位時間內無人機之間的通信拓撲結構，可以將無人機的鏈路映射到圖G中的連邊e(i,j)。W表示無人機之間通信代價的權重矩陣，wij表示無人機編號i和j的通信代價權值指標，通過歸一化后的信號穩(wěn)定性指標以及鏈路負載度指標參數(shù)確定。

信號穩(wěn)定性與節(jié)點之間的功率強度和相對速度有關。功率強度指標主要通過無人機相互之間Hello消息的信號強度確定。對于節(jié)點i，定義其接收到節(jié)點j的信號功率大小為Pij，根據(jù)自由空間傳播模型，節(jié)點間功率強度計算方法為

式中：Ps為無人機節(jié)點的額定天線功率；Gs、Gr為無人機天線的接收增益參數(shù)和發(fā)射增益參數(shù)；L為信道傳輸路徑損耗的參數(shù)；λ為波長，以上變量均為定值。

無人機之間的相對速度可以根據(jù)多普勒效應計算得到。設f為無人機節(jié)點發(fā)射功率的原頻率，f′為節(jié)點j接收到節(jié)點i的載波頻率，可知由多普勒效應，無論節(jié)點j相對于節(jié)點i遠離或是接近，節(jié)點i和j的相對速度為

結合余弦定理和公式（1）中的自由空間傳播模型，利用節(jié)點之間的功率強度對公式（2）中的三角函數(shù)進行替換，可以推導出節(jié)點i和j的相對速度：

根據(jù)公式（1）和公式（3）分別得到節(jié)點i和j的功率強度和相對速度后，兩個節(jié)點之間的信號穩(wěn)定度LSij就可以根據(jù)以下公式得到：

式中：i與j是對應鏈路兩端的發(fā)送節(jié)點和接收節(jié)點。Pij是節(jié)點i和j間的信號功率強度，vij是節(jié)點i和j的相對移動速度，Ps和vmax分別表示無人機的發(fā)射功率與節(jié)點最大速度。λ和φ分別為功率和速度的權重因子，且λ+φ=1。

Pth為設定的對應鏈路最小閾值，其對應于處在無人機通信邊緣且相對距離恰好為最大通信半徑減去通信時延tde_min的鄰居節(jié)點。設置鏈路最小閾值可以避免節(jié)點選擇生存時間非常短的鏈路。

鏈路負載度指標映射到邊權重時，定義為兩端節(jié)點的負載均值：

通信代價權值代表兩架無人機之間通信困難程度，相對移動速度越快、信號強度越小、鏈路負載程度越高，無人機之間的通信代價就越大。根據(jù)公式（4）和公式（6），信號穩(wěn)定性越大、鏈路負載越小，通信代價越小，因此定義通信代價權值wij為鏈路負載度指標與信號穩(wěn)定性指標的比值：

其中：kLC和kLS分別為鏈路負載度指標和信號穩(wěn)定性指標的權值。可以看出，當信號穩(wěn)定性越高、節(jié)點負載度越小時，節(jié)點i與j之間的通信代價越小；當節(jié)點信號強度低于閾值強度后，通信代價為無限大。

1.2 無人機集群初始網(wǎng)絡拓撲結構

無人機集群系統(tǒng)一般采取密集編隊模式，每個通信個體與最近幾個鄰居進行通信。考慮一個包含n架無人機的無人機集群，假設所有的無人機具有相同的結構和運動能力，無人機的通信半徑為Rm。設定無人機集群中包含一架領航無人機以及n-1 架跟隨無人機，運動方式為參考群組移動模型。領航無人機在接收到上位機的命令后，會沿著任務信息所規(guī)劃的航跡進行飛行，跟隨無人機根據(jù)鄰居節(jié)點自動調整位置，保證每個無人機的運動軌跡與集群整體一致，因此領航無人機無需與集群中所有無人機實時進行數(shù)據(jù)同步，任意一個無人機都可以成為領航節(jié)點，每個無人機只需要與鄰居無人機保持相似的運動軌跡，即可實現(xiàn)集群運動的同步。

設定無人機集群整體以速度v0朝著一個既定目標飛行，在飛行過程中，由于自然因素和無人機自身性能因素，每架無人機速度會在一定范圍內波動，定義無人機i在時刻t的速度為vi(t)，在網(wǎng)絡拓撲模型G(V,E,W)中，任意節(jié)點i的速度為

每個無人機在速度偏離整體速度后都會自適應進行速度調節(jié)，因此在所有時間的速度收斂于v0，可以用以下公式進行描述：

無人機集群運動狀態(tài)如圖2 所示，選定16號節(jié)點為領航節(jié)點，在圖中用黃色標出，其余藍色節(jié)點為跟隨節(jié)點。考慮到節(jié)點之間的通信鏈路為雙向鏈路，因此集群網(wǎng)絡拓撲結構應當具有對稱性，網(wǎng)絡所映射的圖論模型也應當為無向權重圖。無人機與其最近的幾個鄰居節(jié)點建立雙向鏈路，構成如圖2所示的網(wǎng)絡拓撲。

圖2 無人機集群運動方式與初始網(wǎng)絡拓撲

在無人機集群執(zhí)行任務過程中，當無人機集群中節(jié)點數(shù)較多時，節(jié)點因發(fā)生故障而出現(xiàn)失效的情況在所難免。此時，網(wǎng)絡拓撲會因該節(jié)點的移除而發(fā)生改變，進而影響整個網(wǎng)絡的連通性。如圖3（a）所示，如果14號和28號節(jié)點發(fā)生故障，無人機集群網(wǎng)絡映射到圖論中的數(shù)學模型則轉化為圖3（b）。在圖3（b）中，無人機集群網(wǎng)絡內部雖然能夠進行信息交互，但是22號節(jié)點承擔了右下方通信子集與其他節(jié)點之間的通信，如果22 號節(jié)點發(fā)生故障，則無人機集群網(wǎng)絡被分割為兩個不連通的子集，此時，集群內部節(jié)點無法進行信息同步，集群整體的網(wǎng)絡性能發(fā)生了嚴重的下降。因此，本文從節(jié)點移除對網(wǎng)絡連通性造成的影響角度來考慮無人機飛行自組織網(wǎng)絡的連通性維護問題，通過鏈路預測算法與局部拓撲修復算法，實現(xiàn)網(wǎng)絡的連通性恢復。

圖3 節(jié)點發(fā)生故障后網(wǎng)絡拓撲變化圖

2 網(wǎng)絡修復算法

灰色預測是一種能夠針對樣本數(shù)據(jù)量小、數(shù)據(jù)變化不規(guī)律的時間序列進行預測的方法，具有預測速度快、預測擬合度高、參數(shù)估計簡單和預測結果可檢驗等優(yōu)點。本文采用灰色滾動預測算法，對節(jié)點之間的鏈路狀態(tài)信息進行實時預測。但由于灰色預測算法在非線性數(shù)據(jù)序列預測方面存在準確性不足的問題，因此本文利用鯨魚優(yōu)化算法，考慮了“新信息優(yōu)先”原則，對灰色預測算法時間響應函數(shù)的初始值進行改進，提出了鯨魚權值優(yōu)化-灰色滾動（whale optimization algorithm?weight of grey model，WOA?WGM）預測算法。

相較于傳統(tǒng)的灰色預測算法，本文提出的鯨魚權值優(yōu)化-灰色滾動預測算法有效提高了預測的精確度，增加了預測值與樣本數(shù)據(jù)序列之間的關聯(lián)性，并具有良好的非線性時間序列預測能力。此外，通過Dijkstra 算法對局部拓撲恢復路徑進行尋優(yōu)，考慮鏈路負載方差，并通過鯨魚算法對尋優(yōu)后的路徑進行負載均衡處理，實現(xiàn)局部拓撲的最優(yōu)恢復，提高恢復后網(wǎng)絡的魯棒性。

2.1 灰色滾動預測模型

GM（1,1）灰色預測是一種可以對不確定時間序列進行擬合和估計的有效工具，其數(shù)據(jù)樣本空間允許少到4個，非常適合于鏈路質量的快速估計［11］。無人機集群網(wǎng)絡拓撲結構變化頻繁，需要及時對下一時刻的鏈路狀態(tài)進行預測，因此在灰色預測模型中加入時間窗口，不斷去舊值、添新值，保證樣本數(shù)據(jù)的實時性。

設原始時間序列為W(0)={w(0)(1),w(0)(2),…,w(0)(n) }其中w(0)(k)是在時刻k時的數(shù)據(jù)。w(0)的累加生成序列為W(1)={w(1)(1),w(1)(2),…,w(1)(n) },其中對于GM（1,1）預測模型，其灰色微分方程為

式中，z(1)(k)=0.5w(1)(k)+0.5w(1)(k-1),k=2,3,…,n；a和b分別為發(fā)展系數(shù)和灰作用量。將時間序列W(0),W(1)代入公式（10），可以得到如下公式：

將公式（11）轉化為矩陣形式，即可得到：

求解上述公式，可以得到參數(shù)a和b的最小二乘估計：[a,b]T=(BTB)-1BTY。

對輸入的時間序列建立用于預測的微分方程：

將參數(shù)a和b的預測值代入公式（13），并將w(1)(1)=w(0)(1)作為初始條件代入，得到公式（13）求解后的時間響應函數(shù)：

由此，即可得到k+1時刻的鏈路穩(wěn)定性預測值。

2.2 鯨魚權值優(yōu)化模型

2.2.1 時間響應函數(shù)優(yōu)化策略

經(jīng)典灰色預測的時間響應函數(shù)的初始條件為輸入時間序列的第一個參數(shù)，當進行滾動預測時，會導致對信息的適應能力下降，從而導致灰色預測模型的預測性能降低。針對這個問題，本文通過對時間響應函數(shù)的初始序列進行加權處理，利用鯨魚算法在每次滾動預測時對權值進行尋優(yōu)。經(jīng)典灰色預測時間響應初始條件為w(0)(1)，本文設定新的時間響應函數(shù)初始條件為w(1)(β)，對其進行加權處理，具體為

優(yōu)化后的時間響應函數(shù)為

其中：αn-k(0 <α<1)(k=1,2,…,n)是動態(tài)權重系數(shù)，β(1 ≤β≤n)是時間輸入系數(shù)。

新提出的初始條件也充分考慮了影響模型準確性的歷史信息，由于α滿足0<α<1，因此參數(shù)α次數(shù)越高，權重越小，即k值越大，相應的x(1)(k)加權值越大：

生成系數(shù)α和β的最佳值是通過最小化預測值和實際值之間的平均絕對百分比誤差來計算。為此，優(yōu)化初始條件下的最佳生成系數(shù)由以下目標函數(shù)確定：

2.2.2 鯨魚算法權值尋優(yōu)

逼近目標函數(shù)的最小值有助于獲得權重系數(shù)的最優(yōu)值。由于目標函數(shù)的非線性特性，無法采用常規(guī)方法求解，而智能優(yōu)化算法可以簡單、快速地解決非線性優(yōu)化問題。其中，鯨魚算法收斂速度快、局部搜索能力強，可以快速得到近似最優(yōu)解，因此，本文采用鯨魚優(yōu)化算法對模型參數(shù)進行優(yōu)化，使得該模型的建模誤差減小，進而獲得模型非線性參數(shù)的最優(yōu)值。

鯨魚算法是通過模擬鯨魚捕獲獵物的方式來實現(xiàn)尋優(yōu)，鯨魚算法求解過程主要經(jīng)歷三個階段：搜尋獵物階段、環(huán)繞包圍以及起泡網(wǎng)狩獵［12］。鯨魚算法位置更新方式中，環(huán)繞包圍捕獵和螺旋式路徑捕獵概率p等同，因此位置更新公式為

式中，T表示最大迭代次數(shù)。

在利用鯨魚算法對參數(shù)進行權值尋優(yōu)之前，首先需要設定待求參數(shù)α和β的上界和下界，并對算法參數(shù)進行初始化，然后生成初始鯨魚位置序列，通過三種策略迭代更新鯨魚個體適應度最高的位置，最后，達到最大迭代次數(shù)，輸出最優(yōu)解。具體步驟如下：

第一步：初始化鯨魚算法的參數(shù)r,p,l,b，設置鯨魚算法的種群數(shù)量N、最大迭代次數(shù)T，確定算法的復雜度；

第二步：初始化鯨魚種群位置X={x1,x2,…,xN}，并設置待求參數(shù)α和β的范圍區(qū)間。其中，權重參數(shù)α的范圍為α∈(0,1)，時間輸入系數(shù)β的范圍為β∈[1,n]；

第三步：根據(jù)算法的成本函數(shù)計算鯨魚個體的成本值，選擇成本值最低的鯨魚個體作為最優(yōu)解，鯨魚優(yōu)化算法的成本函數(shù)如下：

第四步：更新鯨魚優(yōu)化算法的參數(shù)；

第五步：根據(jù)公式（19）對鯨魚個體位置進行更新。鯨魚個體位置更新分為三種：搜尋獵物階段、環(huán)繞包圍以及起泡網(wǎng)狩獵。根據(jù)更新的參數(shù)選擇相應的方法進行位置更新，并對鯨魚個體的成本值進行計算，更新最優(yōu)解；

第六步：判斷算法是否達到最大迭代次數(shù)，若未達到，則轉第三步，否則輸出最優(yōu)解作為參數(shù)α和β的最優(yōu)值。

利用鯨魚算法找到最優(yōu)解后，即可確定初始條件的權重參數(shù)和時間參數(shù)的最優(yōu)值，將其代入灰色預測算法，對輸入序列進行預測。在滾動預測過程中，需要不斷對輸入序列去舊值、添新值，并在每次滾動預測過程中，利用鯨魚優(yōu)化算法對新的初始條件進行優(yōu)化，保證數(shù)據(jù)預測的準確性。預測算法全部過程如下：

第一步：采用實際觀測值w(0)(1),w(0)(2),…,w(0)(c)作為灰色滾動預測算法的輸入數(shù)據(jù)。根據(jù)上述成本函數(shù)，使用鯨魚優(yōu)化算法計算參數(shù)α和β。由此可以獲得預測數(shù)據(jù)

第三步：重復上述步驟，直到預測出所有剩余數(shù)據(jù)點。

2.3 Dijkstra和鯨魚優(yōu)化網(wǎng)絡拓撲修復算法

本文設計的網(wǎng)絡拓撲恢復算法將網(wǎng)絡結構和網(wǎng)絡負載都納入考量。針對網(wǎng)絡結構，通過預測后的通信代價矩陣，選擇通信代價最小的鏈路進行重建，這樣有助于網(wǎng)絡整體的可靠性。但是，僅考慮通信代價進行拓撲修復可能會導致少量鏈路的負載過大，從而引起整個網(wǎng)絡的傳輸性能下降，因此網(wǎng)絡恢復算法應當能夠在最小通信代價的基礎上對拓撲進行負載均衡處理，優(yōu)化集群網(wǎng)絡內部的鏈路數(shù)量于鏈路負載，保證集群內部信息能夠進行有效傳輸?shù)耐瑫r對拓撲結構進行改善。考慮到無人機移動速度快、通信鏈路質量變化頻繁的特點，對局部拓撲恢復尋優(yōu)的問題很難采用某種解析方法去解決，而鯨魚算法可以在有限計算時間內尋找優(yōu)化問題的最優(yōu)解或者次優(yōu)解，因此本文提出將Dijks?tra 算法［13］和鯨魚優(yōu)化算法相結合，來對網(wǎng)絡拓撲進行修復。

使用本文預測算法預測得到鏈路權值后，需要對備選節(jié)點進行篩選，選擇合適的節(jié)點建立新的鏈路。首先通過Dijkstra 算法尋找通信代價最小的鏈路，核心思想是選定一個起始節(jié)點和目的節(jié)點，其余待恢復節(jié)點為必經(jīng)節(jié)點，利用基于回溯法的Dijkstra 算法尋找起始節(jié)點與目標節(jié)點之間的最佳路徑。如圖4所示，虛線代表預測的鏈路，實線雙箭頭代表節(jié)點之間存在雙向穩(wěn)定鏈路，在當前時刻，節(jié)點Z失效，節(jié)點X與節(jié)點Y 鏈路斷開，對這兩個節(jié)點執(zhí)行網(wǎng)絡恢復策略。

圖4 無人機節(jié)點鏈路重選示意圖

根據(jù)公式（6）可知：通信代價越高，節(jié)點之間的相對速度和距離就越大，因此取通信代價最小的路徑作為最優(yōu)恢復路徑。設節(jié)點X 到節(jié)點Y 的路徑邊集為EXY，則X 到Y 的最小通信代價路徑為

由公式（9）可以計算無人機鏈路負載權值，要實現(xiàn)無人機恢復后的局部拓撲負載優(yōu)化，本文通過計算恢復后拓撲負載的方差來衡量鏈路負載均勻度：

其中：LCe代表局部拓撲中無人機鏈路e的負載權值；N代表無人機局部拓撲的鏈路數(shù)目；AVG代表局部拓撲的負載權值均值，由以下公式確定：

綜合考慮無人機的通信代價E和鏈路負載均勻度D，對于局部拓撲Gpart，將以無人機網(wǎng)絡中的通信代價E和負載均勻度D作為目標函數(shù)，通過權重k來均衡無人機，使得在架構成本和負載均衡之間做出權衡，最終設計方案應使得目標函數(shù)盡可能小，即拓撲設計方案的成本更低，負載更均衡：

根據(jù)無人機拓撲恢復的目標函數(shù)，結合無人機網(wǎng)絡中對于鏈路的相關約束，可以得到以下無人機拓撲恢復方法的目標函數(shù)：

將上述優(yōu)化目標函數(shù)代入到鯨魚算法中進行尋優(yōu)，設置鯨魚算法的成本函數(shù)為

根據(jù)算法的成本函數(shù)，計算鯨魚個體的成本值，以成本值最低的鯨魚個體作為當前的最優(yōu)解，并通過收縮包圍、螺旋運動和隨機游走三種方式，對鯨魚算法的參數(shù)選擇相應的方法進行位置更新，并對鯨魚個體的成本值進行計算，更新最優(yōu)解，最終實現(xiàn)對無人機局部的拓撲恢復。

3 實驗結果與仿真分析

3.1 實驗參數(shù)設置

本實驗通過Python 仿真平臺進行算法的仿真，并對本文提出的WOA?WGM 預測算法進行仿真分析，以驗證不同網(wǎng)絡損傷類型下集群網(wǎng)絡的生存能力和抗毀能力。具體的仿真參數(shù)設置如表1所示。

表1 仿真參數(shù)設置

為了對本文提出的網(wǎng)絡恢復算法進行仿真評估，本文選取BA 無標度網(wǎng)絡算法以及LPN（link prediction based on neighbors）一跳鄰居鏈路預測算法這兩個經(jīng)典恢復算法對比分析網(wǎng)絡恢復性能。在BA 網(wǎng)絡修復算法中，需要進行連通性修復的節(jié)點會自發(fā)尋找通信范圍內重要度最高的節(jié)點進行邊重連，修復后的網(wǎng)絡具備一定的無標度網(wǎng)絡特性。LPN 網(wǎng)絡算法會對每個節(jié)點的通信代價矩陣［9］進行預測，根據(jù)預測結果，選擇鏈路權值最好的節(jié)點進行重連，實現(xiàn)網(wǎng)絡的連通性恢復。在仿真實驗中，首先分析本文網(wǎng)絡恢復算法在集群最大速度不同的情況下恢復網(wǎng)絡連通性所用的時間，驗證本文算法的時效性；其次，驗證無人機集群網(wǎng)絡在隨機失效下的網(wǎng)絡恢復能力，驗證算法恢復后網(wǎng)絡的生存性；最后，評估蓄意攻擊下無人機集群網(wǎng)絡的恢復能力，驗證恢復后網(wǎng)絡的抗毀性。

3.2 仿真實例分析

根據(jù)以上介紹的仿真環(huán)境及參數(shù)設置，對無人機集群整體位置進行仿真模擬，每個無人機參考領航節(jié)點，以速度v0+vrand在區(qū)域內部進行飛行。每個無人機與自身若干相鄰節(jié)點建立鏈路，組成網(wǎng)絡的初始拓撲結構。在進行了13次飛行仿真后，得到如圖5所示的網(wǎng)絡拓撲結構。

圖5 無人機集群網(wǎng)絡拓撲結構

在13 次仿真過程中，每個無人機通過與鄰居節(jié)點進行信息共享，根據(jù)自身與鄰居節(jié)點的信號功率強度、相對速度和負載程度計算出對應的通信代價權值wij。集群中的無人機根據(jù)權值生成集群網(wǎng)絡的通信代價矩陣W，以預測窗口大小為基準代入多個時刻的歷史樣本數(shù)據(jù)，通過WOA?WGM 算法預測得出通信代價的預測矩陣,如圖6所示。

圖6 通信代價預測矩陣

其中：A1,A2,…,A30代表無人機節(jié)點編號，inf代表無人機節(jié)點之間不存在通信鏈路。

采用表1的參數(shù)進行仿真實驗，隨機產生失效節(jié)點ID。設集群網(wǎng)絡中的失效節(jié)點集合為FN，則集群網(wǎng)絡中拓撲結構受到影響的無人機節(jié)點向其鄰居節(jié)點發(fā)送網(wǎng)絡恢復請求，集群內部通過信息共享得到待修復節(jié)點集合RN。集合FN和RN包含的節(jié)點如下所示：

節(jié)點編號為14、22、28 的無人機失效后，集群網(wǎng)絡拓撲結構如圖7所示。在圖中，綠色節(jié)點代表連通性受影響節(jié)點集合RN，紅色節(jié)點代表失效節(jié)點集合FN，陰影部分表示需要對該部分的局部拓撲結構進行修復。

當節(jié)點A14,A22,A28失效后，集合RN中的節(jié)點按序依次尋找最短路徑。集合中的待恢復節(jié)點根據(jù)通信代價矩陣預測值,通過最小通信代價路徑算法遍歷出待恢復節(jié)點之間的路徑，以此實現(xiàn)網(wǎng)絡局部拓撲結構的修復，結果如表2所示，通過最小通信代價修復后的拓撲圖如圖8所示，通過修復算法找到節(jié)點之間的最小通信代價路徑用點線表示。

表2 節(jié)點之間最短路徑表

圖8 最短路徑拓撲修復圖

利用最小通信代價算法進行了初步修復后，需要繼續(xù)對其進行負載優(yōu)化。在實驗中，假設每個無人機都向鄰居節(jié)點發(fā)送長度為1 幀的數(shù)據(jù)，長度為256 byte，周期為4 ms。經(jīng)過仿真實驗，比較了直接尋找最小通信代價方案和優(yōu)化設計方案，得到了鏈路數(shù)、負載均值和負載方差的對比數(shù)據(jù)，如表3 所示。拓撲修復圖如圖9所示，圖中待修復節(jié)點根據(jù)最短路徑對局部拓撲結構進行修復，避免因節(jié)點失效造成網(wǎng)絡整體重新進行拓撲重構。同時，本文算法提出的網(wǎng)絡修復方案在鏈路數(shù)量上進行了一定的優(yōu)化，網(wǎng)絡體系代價有了明顯的降低，負載更加均勻，提高了集群網(wǎng)絡的魯棒性和健壯性。

表3 仿真對比結果

圖9 WOA?WGM 實現(xiàn)無人機集群網(wǎng)絡拓撲修復

3.3 網(wǎng)絡恢復時效性分析

網(wǎng)絡恢復時效性分析是指在無人機集群網(wǎng)絡受到損傷后，恢復網(wǎng)絡的連通性所需要的時間。圖10中分別表示了不同速度與損傷情況下，本文算法與BA 算法和LPN 算法恢復網(wǎng)絡的時效性對比，為消除可能存在的隨機誤差，采集的實驗數(shù)據(jù)均為進行10次仿真后求得的平均值。

圖10 無人機集群網(wǎng)絡恢復算法時效性對比

在圖10（a）中，設定無人機集群在3 個節(jié)點失效的情況下，不同算法在不同的速度恢復網(wǎng)絡連通性所需的時間，可以看出，在無人機集群最大速度小于10 m/s 時，經(jīng)典BA 算法和LPN算法由于其計算復雜度低，可以很快找到合適的鏈路進行拓撲修復。而隨著無人機的最大移動速度增大，三種恢復算法耗時均存在不同程度的增加，BA 算法和LPN 算法增加最為明顯，這是因為隨著無人機移動速度的增加，節(jié)點之間的信號強度和相對速度變化越頻繁，BA 算法由于沒有預測機制，在恢復網(wǎng)絡連通性時需要不斷試錯，LPN 算法雖然可以對鄰居節(jié)點的鏈路進行預測，但是預測結果精確度不足，且不能對多跳鏈路進行預測，難以實現(xiàn)整個集群網(wǎng)絡的連通性恢復。在圖10（b）中，設定無人機集群在15 m/s 的最大速度下，不同算法在損失不同數(shù)量的節(jié)點修復網(wǎng)絡拓撲所需的時間，同樣，經(jīng)典BA 算法和LPN 算法都隨著失效規(guī)模的增大，恢復耗時急劇增加，而本文算法由于加入了改進的預測機制和多節(jié)點路徑恢復機制，對下一時刻的無人機速度和鏈路距離進行了預判，對于速度的變化較為敏感，能夠使無人機在高速移動時選擇到高穩(wěn)定鏈路，從而減少了不必要的路由開銷，實現(xiàn)網(wǎng)絡連通性的快速恢復。

3.4 網(wǎng)絡恢復生存性分析

網(wǎng)絡恢復生存性是指無人機集群網(wǎng)絡恢復算法在節(jié)點隨機失效情況下，恢復網(wǎng)絡連通性的能力。本文通過網(wǎng)絡最大連通度和平均路徑長度比例對網(wǎng)絡性能進行分析［14］。

網(wǎng)絡最大連通度G表示最大連通子圖節(jié)點數(shù)占總節(jié)點數(shù)的比例，表達式為

對于帶權無向圖，平均路徑長度與邊權值相關，平均路徑長度L表達式如下：

則平均路徑長度比例L*為受到影響后集群平均路徑長度與初始平均路徑長度的比值：

在仿真實驗中，隨機選擇集群中的無人機失效，分析無人機集群在不同失效規(guī)模下使用不同算法恢復后網(wǎng)絡的生存性。結果如圖11 所示。圖11（a）為網(wǎng)絡最大連通度隨失效規(guī)模變化的曲線，可以看出，在失效比例小于0.4 時，BA 算法集群內部的最大連通度要高于LPN 算法，這是由于BA 恢復算法選取度值最大節(jié)點實現(xiàn)邊重連，恢復后的網(wǎng)絡相較于LPN 算法能夠更好地保證網(wǎng)絡整體連通性。LPN 算法由于優(yōu)先選取通信代價最小的鏈路實現(xiàn)邊重連，因此容易陷入局部最優(yōu)而忽略集群整體的連通性能，導致集群內部被分割為多個不連通的子集，降低網(wǎng)絡的連通性。而本文算法考慮了所有網(wǎng)絡拓撲受到影響的節(jié)點之間的連通性恢復，因此在網(wǎng)絡拓撲連通性恢復過程中，節(jié)點在失效比例小于0.5 時，能夠一直保持集群內部的連通性不受影響，即使在網(wǎng)絡大規(guī)模失效，本文算法在網(wǎng)絡整體的連通性能恢復上也更優(yōu)于BA 算法和LPN算法。

圖11 無人機集群網(wǎng)絡生存性指標

圖11（b）為平均路徑長度比例隨失效規(guī)模的變化曲線，當節(jié)點失效比例小于0.2 時，BA 網(wǎng)絡恢復算法所平均路徑長度比例優(yōu)于LPN 算法，這也驗證了BA 算法在執(zhí)行恢復策略時，能夠使得網(wǎng)絡中連通性下降的節(jié)點自動在通信范圍內選擇連通度最高的節(jié)點實現(xiàn)網(wǎng)絡重連，網(wǎng)絡整體的連通性更好。然而當節(jié)點失效比例超過0.2時，BA 算法的平均路徑長度比例大幅降低，可以看出，當隨機失效作用到關鍵節(jié)點時，BA 算法所恢復的集群網(wǎng)絡連通性會受到很大影響，網(wǎng)絡中出現(xiàn)大量分割的連通子集，導致網(wǎng)絡整體的生存性下降。本文算法相較于BA 算法和LPN 算法，平均路徑長度比例下降更為平緩，在不同失效規(guī)模的情況下均優(yōu)于傳統(tǒng)的BA 算法和LPN 算法。綜合最大連通度和平均路徑長度比例，算法能夠盡力維持網(wǎng)絡整體的連通性，且平均路徑長度比例在60%以上，此時網(wǎng)絡處于相對可靠的狀態(tài)，這是因為本文提出的算法在網(wǎng)絡出現(xiàn)損傷后，會及時修復所有連通度下降節(jié)點之間的網(wǎng)絡拓撲，補償損失的節(jié)點連通路徑。

3.5 網(wǎng)絡恢復抗毀性分析

網(wǎng)絡抗毀性分析是無人機集群網(wǎng)絡在遭到惡意攻擊作用下，集群內部保持連通性能的能力。在仿真實驗中，通過選取無人機集群網(wǎng)絡中節(jié)點度值較大的節(jié)點進行失效仿真，分析網(wǎng)絡恢復算法在不同失效規(guī)模下使用不同算法恢復后網(wǎng)絡的抗毀性。結果如圖12所示。

分析圖12（a）中網(wǎng)絡最大連通度隨失效規(guī)模變化的曲線，可以看出BA 算法的網(wǎng)絡性能恢復能力是三種恢復算法中性能最差的，這是由于BA 算法恢復后的網(wǎng)絡具有一定的無標度網(wǎng)絡特性，在隨機失效時具有良好的魯棒性，但是對于蓄意攻擊是脆弱的。LPN 算法雖然相較于BA算法在面對蓄意攻擊時具有更好的恢復性能，但是網(wǎng)絡最大連通度還是出現(xiàn)了大幅下降，難以維持集群整體連通性。本文算法在失效比例小于0.5 時，依然能夠維持集群整體的連通性，且在失效規(guī)模繼續(xù)增加時，最大連通度下降曲線較為平緩，優(yōu)于傳統(tǒng)的BA算法和LPN算法。

從圖12（b）可以看出，BA 算法和LPN 算法在面對蓄意攻擊時，平均路徑長度比例在較小的失效規(guī)模下發(fā)生了急劇下降，網(wǎng)絡整體已經(jīng)處于多個不連通子集狀態(tài)。而本文算法可以對通信代價實時預測，快速選擇合適的節(jié)點建立鏈路，同時通過最小通信代價策略初步對缺失鏈路進行恢復，并通過負載均衡策略對鏈路進行優(yōu)化，因此從圖中可以看出，不同失效規(guī)模下，平均路徑長度變化較為平緩，不會由于新增鏈路造成網(wǎng)絡平均路徑長度發(fā)生急劇變化，實現(xiàn)了無人機集群網(wǎng)絡的有效恢復，減少了不必要的冗余鏈路，保證了網(wǎng)絡的可靠性。

圖12 無人機集群網(wǎng)絡抗毀性指標

結合圖11 和圖12 中的數(shù)據(jù)，本文提出的網(wǎng)絡恢復算法在隨機失效和蓄意攻擊下相較于傳統(tǒng)的網(wǎng)絡恢復算法能夠更好地維護網(wǎng)絡性能，并且在失效比例不超過0.5 的情況下，能夠穩(wěn)定地維持集群整體的連通性。在節(jié)點失效比例在0.5 至0.7 時，集群網(wǎng)絡內部大范圍節(jié)點都已失效，本文提出的算法在最大連通度和平均路徑長度比例方面都明顯優(yōu)于BA 算法和LPN 算法，表明本文算法在集群遭到大規(guī)模損傷時仍然能夠盡力維持集群中的極大連通子集，提高網(wǎng)絡的生存性和抗毀性。

4 結語

針對高動態(tài)拓撲下無人機節(jié)點失效造成的網(wǎng)絡性能和可靠性下降的問題，本文根據(jù)信號穩(wěn)定度指標和鏈路負載度指標計算無人機之間的通信代價，構建無人機集群網(wǎng)絡通信模型，并通過鯨魚權值優(yōu)化-灰色滾動鏈路預測算法對通信代價指標進行預測，降低了無人機高速移動對修復算法實時性的影響，最后利用最短路徑算法和負載均衡算法，實現(xiàn)了網(wǎng)絡連通性恢復并優(yōu)化了網(wǎng)絡恢復后的拓撲結構。實驗結果表明，該方法在無人機集群網(wǎng)絡出現(xiàn)節(jié)點失效時可以快速進行拓撲重構，恢復通信節(jié)點之間的鏈路連接，實現(xiàn)網(wǎng)絡連通性恢復，并使恢復后的網(wǎng)絡具有良好的生存性和抗毀性。