一種自適應(yīng)無人機集群網(wǎng)絡(luò)恢復(fù)方法

石運陽，華 翔，張金金

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

0 引言

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

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

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

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

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

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

1 無人機集群網(wǎng)絡(luò)拓?fù)溆成淠Ｐ?/h2>

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

1.1 集群網(wǎng)絡(luò)通信代價權(quán)值指標(biāo)

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

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

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

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

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

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

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

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

鏈路負(fù)載度指標(biāo)映射到邊權(quán)重時，定義為兩端節(jié)點的負(fù)載均值：

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

其中：kLC和kLS分別為鏈路負(fù)載度指標(biāo)和信號穩(wěn)定性指標(biāo)的權(quán)值?？梢钥闯?，當(dāng)信號穩(wěn)定性越高、節(jié)點負(fù)載度越小時，節(jié)點i與j之間的通信代價越??；當(dāng)節(jié)點信號強度低于閾值強度后，通信代價為無限大。

1.2 無人機集群初始網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

設(shè)定無人機集群整體以速度v0朝著一個既定目標(biāo)飛行，在飛行過程中，由于自然因素和無人機自身性能因素，每架無人機速度會在一定范圍內(nèi)波動，定義無人機i在時刻t的速度為vi(t)，在網(wǎng)絡(luò)拓?fù)淠Ｐ虶(V,E,W)中，任意節(jié)點i的速度為

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

無人機集群運動狀態(tài)如圖2 所示，選定16號節(jié)點為領(lǐng)航節(jié)點，在圖中用黃色標(biāo)出，其余藍(lán)色節(jié)點為跟隨節(jié)點。考慮到節(jié)點之間的通信鏈路為雙向鏈路，因此集群網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)應(yīng)當(dāng)具有對稱性，網(wǎng)絡(luò)所映射的圖論模型也應(yīng)當(dāng)為無向權(quán)重圖。無人機與其最近的幾個鄰居節(jié)點建立雙向鏈路，構(gòu)成如圖2所示的網(wǎng)絡(luò)拓?fù)洹?/p>

圖2 無人機集群運動方式與初始網(wǎng)絡(luò)拓?fù)?/p>

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

圖3 節(jié)點發(fā)生故障后網(wǎng)絡(luò)拓?fù)渥兓瘓D

2 網(wǎng)絡(luò)修復(fù)算法

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

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

2.1 灰色滾動預(yù)測模型

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

設(shè)原始時間序列為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）預(yù)測模型，其灰色微分方程為

式中，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）轉(zhuǎn)化為矩陣形式，即可得到：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 Dijkstra和鯨魚優(yōu)化網(wǎng)絡(luò)拓?fù)湫迯?fù)算法

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

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

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

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

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

其中：LCe代表局部拓?fù)渲袩o人機鏈路e的負(fù)載權(quán)值；N代表無人機局部拓?fù)涞逆溌窋?shù)目；AVG代表局部拓?fù)涞呢?fù)載權(quán)值均值，由以下公式確定：

綜合考慮無人機的通信代價E和鏈路負(fù)載均勻度D，對于局部拓?fù)銰part，將以無人機網(wǎng)絡(luò)中的通信代價E和負(fù)載均勻度D作為目標(biāo)函數(shù)，通過權(quán)重k來均衡無人機，使得在架構(gòu)成本和負(fù)載均衡之間做出權(quán)衡，最終設(shè)計方案應(yīng)使得目標(biāo)函數(shù)盡可能小，即拓?fù)湓O(shè)計方案的成本更低，負(fù)載更均衡：

根據(jù)無人機拓?fù)浠謴?fù)的目標(biāo)函數(shù)，結(jié)合無人機網(wǎng)絡(luò)中對于鏈路的相關(guān)約束，可以得到以下無人機拓?fù)浠謴?fù)方法的目標(biāo)函數(shù)：

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

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

3 實驗結(jié)果與仿真分析

3.1 實驗參數(shù)設(shè)置

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

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

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

3.2 仿真實例分析

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

圖5 無人機集群網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

圖6 通信代價預(yù)測矩陣

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

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

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

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

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

圖8 最短路徑拓?fù)湫迯?fù)圖

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

表3 仿真對比結(jié)果

圖9 WOA?WGM 實現(xiàn)無人機集群網(wǎng)絡(luò)拓?fù)湫迯?fù)

3.3 網(wǎng)絡(luò)恢復(fù)時效性分析

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

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

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

3.4 網(wǎng)絡(luò)恢復(fù)生存性分析

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

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

對于帶權(quán)無向圖，平均路徑長度與邊權(quán)值相關(guān)，平均路徑長度L表達(dá)式如下：

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

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

圖11 無人機集群網(wǎng)絡(luò)生存性指標(biāo)

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

3.5 網(wǎng)絡(luò)恢復(fù)抗毀性分析

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

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

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

圖12 無人機集群網(wǎng)絡(luò)抗毀性指標(biāo)

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

4 結(jié)語

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