節點攻擊策略下的軍事通信網絡結構優化算法

楊芷柔, 張 虎, 劉 靜, 劉同林

(1. 西安電子科技大學人工智能學院, 陜西 西安 710071; 2. 北京機電工程研究所, 北京 100074)

0 引 言

隨著戰爭形態逐漸向信息化、網絡化快速發展,各體系之間、體系內部各子系統之間及單個作戰個體之間的聯合作戰已經成為現代戰爭的重要發展趨勢。軍事通信網絡作為實現戰場實時、穩定傳遞和收發信息的網絡系統,為提升整體戰斗力提供高速、安全和可靠的底部支撐[1-5]。軍事通信網絡一旦發生故障,其連通性遭到破壞,關鍵的信息流無法正常傳輸,會導致各裝備實體的戰斗力被限制[6-9]。為有效解決這一問題,需提升軍事通信網絡的魯棒性,即當網絡中的某個單元失效后依舊能夠維持網絡結構及功能穩定運行的能力[7, 10-12]。

現代軍事通信網絡單元眾多,內部連接復雜,且層次結構多樣,導致優化問題的搜索空間很大、空間形態復雜。在這種高復雜度的大空間中,由于傳統的借助經驗或基于局部搜索的優化方法缺乏全局的觀點以及有效的智能搜索手段,一方面容易陷入局部最優解,另一方面收斂速度非常慢。作為一種啟發式的全局優化算法,進化優化算法不受解空間的限制,能夠有效地處理傳統優化方法難以解決的復雜優化問題,為軍事通信網絡內部資源重新整合和結構優化問題提供了思路。

為此,本文依據軍事通信網絡的特征,在復雜網絡理論[13-17]指導下,建立了異構節點多層次連接的網絡結構模型,并設計了一種以提升通信網絡魯棒性為目標的進化優化算法,為深入研究軍事通信網絡建模及優化問題提供參考。

1 軍事通信網絡模型構建

1.1 基于復雜網絡的軍事通信網絡模型

在圖論中,網絡可表示為由N個節點的集合V和節點之間M條鏈路的集合E以一定的拓撲結構組成的圖G=(V,E)。其中,節點表示實際網絡中的個體,節點間的鏈路表示節點對之間的特定關系。軍事通信網絡是作戰網絡中的重要組成部分,通過多種通信方式在網絡節點間傳遞信息流。

節點是組成軍事通信網絡結構的基礎。與一般通信網絡相比,軍事通信網絡的節點包括偵查探測類節點、指揮控制類節點和火力打擊類節點,這些節點具有不同的功能屬性,在網絡中扮演著不同的角色[16-19]。針對軍事通信網絡中節點異質性的特征,如果僅用單一節點類型的網絡模型描述,需對網絡進行極大簡化,無法體現軍事通信網絡的特性。因此在描述網絡環境下的節點時,需要表明其屬性類型。

在結構功能方面,鏈路作為節點間傳輸、交互數據信息的通道,為不同屬性的節點之間信息交互提供條件。在屬性功能方面,根據作戰過程中鏈路傳遞的信息流類型,可以確定各類節點間存在指揮控制與協同兩大類關系[20]。其中指揮控制關系應包含逐級指揮關系和跨級指揮關系,形成縱向層次化結構特點;協同關系應包含子系統內部協同關系和子系統間協同關系,形成橫向聯通的特征。雖然網絡中信息有流向,但為了保證指揮決策可以根據行動效果的反饋能得到及時調整,因此本文認為節點間的交互是雙向的,進一步建模為無向鏈路。

1.2 軍事通信網絡結構模型

軍事通信網絡的節點異質性特征表現在功能、結構、層次等方面,而傳統網絡結構模型是以層次化的樹狀圖為骨架。在此樹狀圖中,頂層節點為高級指揮控制類實體,處于重要的地位;連接頂層節點及其子節點的為各級指揮控制類實體;葉子節點為低級指揮控制類實體下具有各種能力的火力打擊實體及偵查探測實體。信息化軍事變革的興起推動傳統的多層次指揮體制轉變為扁平化指揮體制,極大地提高了指揮和決策效率。因此，實際的軍事通信網絡是同時具有樹形骨架和隱含連接的層級結構[21-22],如圖1所示。在隱含連邊添加過程中,越高層級的節點可能有越多的跨級指揮關系和越少的同層協同關系,而越低層級的節點則反之。節點對之間協同連邊的存在概率與節點隸屬層級相關,節點對之間越相近,則協同連邊存在可能性越高。

圖1 網絡結構模型示意圖Fig.1 Schematic of network structural model

假設軍事通信網絡總層級為L,網絡結構模型具體生成步驟如下。

步驟 1建立指揮控制關系網絡。生成1個中心節點,節點層級h=1,以第一層的中心節點為父節點,隨機生成3～5個子節點,新節點層級h=2;重復生成新的層級,直至h=L-2,完成指揮控制關系網絡的生成。

步驟 2生成火力打擊類節點。以最末層的指揮控制類節點為父節點,隨機生成3～5個子節點作為火力打擊節點,節點層級h=L-1,完成火力打擊類節點的添加。

步驟 3生成偵查探測類節點。以火力打擊類節點為父節點,隨機生成3～5個子節點作為偵查探測節點,節點層級h=L,完成偵查探測類節點的添加。此時,樹形骨架網絡建立完成。

步驟 4添加隱含連邊。網絡中各節點對之間建立連接關系的概率[21]為

(1)

式中：α和β是可調參數;Dij為兩個節點最近共同父節點的層級;di和dj分別為兩個節點的層級。

由此生成的軍事通信網絡不僅具備一定的信息共享能力,而且還具備相應的協同作戰能力,符合信息化戰爭下軍事通信網絡的構建要求。

2 軍事通信網絡魯棒性度量

2.1 攻擊策略

信息獲取的程度與攻擊網絡策略的選擇密切相關。根據獲取信息完整性的程度,可將攻擊策略分為以下3種:隨機攻擊、惡意攻擊和條件攻擊[23]。3種攻擊策略在本質上都屬于極端性的攻擊方式。從信息掌握程度上而言,隨機攻擊是攻擊者對軍事通信網絡信息完全不了解的情況下采取的打擊操作;惡意攻擊是攻擊者對軍事通信網絡信息完全了解的情況下,根據重要性按照一定的攻擊順序,進而實施的攻擊行為;條件攻擊是在不完全掌握信息的條件下所進行的攻擊。因此,隨機攻擊和惡意攻擊是條件攻擊中兩個極端的特例。根據對軍事通信網絡攻擊對象的不同,又可將上述攻擊策略細分為節點攻擊和鏈路攻擊。

面對多樣的網絡結構,不同的復雜網絡特征參數對節點或鏈路的重要性度量側重點不同,因此網絡抗毀性對網絡特征參數的靈敏度也不同。一般選取度、介數、聚類系數等基本指標作為衡量依據。基于節點度的重要性衡量方法不僅可以凸顯不同層級間的重要性差異,又能描述同層級間的重要性順序,因此本文重點討論按照節點度的惡意攻擊方式,在攻擊時優先選擇當前網絡中較重要的,即度值大的節點,直至軍事通信網絡的連通性完全被破壞。

2.2 魯棒性度量方法

軍事通信網絡的節點或鏈路受到攻擊后,網絡繼續維持正常運轉的能力稱為魯棒性。定量評估網絡魯棒性不僅可以分析當前網絡的性能,還可以為進一步優化網絡結構設計提供依據。為了能夠定量分析節點攻擊策略對軍事通信網絡結構造成的影響,采取最大連通分量度量的方式對網絡的魯棒性進行衡量。當軍事通信網絡受到攻擊后,其拓撲結構發生改變,可分解為多個子圖。對于連通子圖,圖中的任意兩個節點間至少存在一條簡單的連通路徑;對于非連通圖,可將其分解為兩個或兩個以上的連通子圖,其中各個連通子圖中包含節點個數最多的團簇稱為最大連通子圖。最大連通分量的相對值定義為

(2)

式中：N′表示網絡遭受攻擊后最大連通子圖包含的節點數;N表示初始網絡的節點數。

考慮到攻擊是動態且連續的過程,為了持續地評估網絡在某種攻擊策略下的表現,采用復雜網絡中經典且應用廣泛的魯棒性度量方式[24-28],具體數學表達式如下：

(3)

式中：N表示初始網絡的節點數;S(Q)表示移除Q個節點后剩余網絡最大連通分量的相對值;1/N為歸一化因子,使不同規模網絡的魯棒性可以進行比較。在同一種攻擊策略下,網絡魯棒性指標R值越大,則表示網絡在此種攻擊策略下表現越穩定,反之,網絡表現越脆弱。R的范圍為[0, 0.5]。

3 軍事通信網絡魯棒性優化算法

3.1 進化優化算法設計

信息化技術的發展使得軍事通信網絡功能及業務不斷擴充,導致網絡規模不斷增長,網絡結構也日益復雜。進化算法模擬自然界的生物進化機制,是一種不依賴于梯度信息且具有并行特征的算法,可以有效地解決大規模網絡的優化問題。對軍事通信網絡結構及功能的改進和完善是基于作戰需求和資源約束等條件的,可以尋求各裝備實體間的最佳匹配,從而實現軍事通信網絡整體價值最大化的目標。從拓撲結構角度而言,主要是通過調整網絡中的連接關系,達到提高網絡魯棒性的目的[29]。由于鏈路的屬性由兩側節點的屬性決定,在調整連接關系過程中鏈路的屬性可能會發生改變,因此這里只考慮鏈路的結構屬性。在實際網絡的優化問題中,調整網絡連接的代價遠小于增加節點或鏈路數目的代價。因此,本文在設計優化算法中對已有的網絡結構模型進行調整時,不改變網絡中各裝備實體的度,即網絡的度分布保持不變。

進化算法基本要素包含:編碼、種群初始化、適應度函數設計、遺傳操作設計等,其流程圖如圖2所示。

圖2 網絡魯棒性進化優化算法流程圖Fig.2 Flow chart of evolutionary optimization algorithm for network robustness

3.2 編碼和種群初始化

網絡結構優化問題包含了網絡內部的連接信息,而鄰接矩陣中的元素表示對應行列編號節點對之間的連接情況。因此采用二進制編碼,用鄰接矩陣表示一條染色體,而每條染色體代表解空間的一個網絡。

在種群初始化操作中,原始網絡為已有的軍事通信網絡結構G0,初始種群中剩余網絡的生成需要對該原始網絡進行M次隨機邊交換操作,具體操作如圖3所示。在左邊的原始網絡中隨機選擇兩條邊,圖中用粗線標記,進行一次邊交換操作后得到右側的新網絡。在邊交換操作過程中需要保證網絡的連通性和度分布不變。

圖3 邊交換操作說明Fig.3 Explanation of link swap operation

3.3 交叉算子

(4)

(5)

(6)

(7)

圖4 交叉算子實例Fig.4 Example for the crossover operator

3.4 局部搜索算子、適應度函數及選擇算子

完成交叉操作后,在父代和子代種群中選擇一個較優個體以概率pl進行局部搜索操作,通過簡單的邊交換操作得到適應度值更高的個體。將被選中進行局部搜索的網絡記為G,對G中的每條鏈路進行隨機邊交換操作得到新個體G*,分別計算個體G和G*的適應度值,若G*更優,則接受當前個體。

適應度函數值的大小決定了個體在遺傳操作中的生存能力,對應于求解網絡優化問題,則和優化目標函數相關。調整軍事通信網絡結構,以提升軍事通信網絡魯棒性為目標。相應的,魯棒性R(式(3))可作為評價個體優劣的標準,即目標函數。魯棒性越高的個體表現越好,進入下一代種群的幾率越大。

選擇算子采用二元錦標賽選擇方法,相比于輪盤賭選擇策略,不需要將個體適應度值轉化為累積概率。二元錦標賽選擇策略會每次從父代和子代種群中,分別挑選一個未被選擇的個體進行比較,選擇較優個體進入下一代種群,直至新種群規模達到原來的種群規模。

4 實驗及結果分析

在節點攻擊策略下軍事通信網絡的魯棒性優化實驗中,創建的無權無向網絡在整個網絡結構中各節點對之間均有連通路徑,不存在孤立節點。利用軍事通信網絡結構模型構建方法,設定網絡節點總層級L=4,網絡模型參數α=6,β=3,由此生成規模分別為N=38和N=100的軍事通信網絡。初始軍事通信網絡性能參數計算結果如表1所示。

表1 初始軍事通信網絡性能參數

從表1中可以看出,當前生成的網絡內部各裝備實體間連接交互較多,因此網絡的平均路徑長度較短,說明網絡結構模型構建方法較為合理。為直觀對比優化前后的網絡結構,利用Pajek軟件繪制了原始軍事通信網絡的拓撲結構圖。網絡拓撲結構及度分布如圖5和圖6所示。圖5中橙色、黃色、綠色和棕色分別代表層級1～層級4的節點,節點的大小與節點度正相關,同層級內的鏈路用軍藍色高亮顯示,不同層級之間的鏈路用淺灰色表示。

圖5 原始網絡拓撲結構Fig.5 Topology structure of original network

圖6 網絡度分布Fig.6 Degree distribution of network

在利用進化算法對軍事通信網絡魯棒性進行優化時,主要參數的取值為:種群規模Ω=20,交叉概率pc=0.8,局部搜索概率pl=0.5,以最大進化代數tmax=150作為程序終止的條件。同時,為了驗證算法的有效性,采用爬山法作為對比算法,在同樣的迭代次數下對比二者的最終結果。

爬山法是一種完全貪婪算法,從當前解的臨近解空間選擇一個更優解作為當前解,如此循環直到搜索到一個局部最優解。爬山法實現簡單,但容易陷入局部最優解。

按照節點度對原始網絡進行惡意攻擊,分別采用爬山法和本文提出的進化優化算法對圖5中的網絡結構進行優化,在優化過程中進化代數與適應度的關系如圖7所示,在面臨攻擊時的網絡表現情況對比如圖8所示。在圖7和圖8中,上半部分為38節點網絡的優化效果,下半部分為100節點網絡的優化效果。最大連通分量的相對值曲線與坐標軸圍成的面積越大,表示網絡遭受攻擊后表現越穩定,魯棒性越好。從圖7和圖8可以看出,與傳統爬山法的優化效果相比,本文提出的進化優化算法可以更顯著地提升軍事通信網絡的魯棒性。

圖7 適應度值演化曲線Fig.7 Evolution curve of fitness value

圖8 優化前后攻擊效果對比Fig.8 Attack effect comparison before and after optimization

平均路徑長度表示網絡中任意節點對之間距離的平均值,是衡量軍事通信網絡信息傳輸時效性的重要性能參數[30]。對優化前后軍事通信網絡的平均路徑長度進行計算,結果如表2所示。與一般網絡的優化結果相反,調整網絡內部連接關系后反而增加了軍事通信網絡的平均路徑長度。為了進一步分析上述結果產生的原因,以優化前后的網絡拓撲結構為例,對軍事通信網絡內部各層級之間的連接情況進行統計分析,具體對比數據如表3和表4所示,左側表示優化前，右側表示優化后。

表2 優化前后的網絡平均路徑長度

表3 38節點網絡層級間鏈路數對比

表4 100節點網絡層級間鏈路數對比

從表3和表4可以看出,相比于優化前軍事通信網絡內部層級的連接情況,經過優化的網絡減少了不同層級間的鏈路數,加強了隸屬于不同分支的同層內部的連接強度,使得同類裝備實體間的連接關系更為緊密,共享交互的通信協作性也更為明顯。

優化效果可由網絡拓撲結構圖直觀體現,優化后的軍事通信網絡拓撲結構如圖9所示。與圖5中的原始網絡拓撲結構相比,經過優化的網絡結構中,表示同層級內部連接的高亮鏈路明顯增多。

圖9 優化后的網絡拓撲結構Fig.9 Topology structure of optimized network

5 結 論

軍事通信網絡的優化是一類復雜的問題,也是信息化條件下研究體系作戰效能的重要內容。本文基于復雜網絡視角深入分析了軍事通信網絡的特征與連接機制,建立了軍事通信網絡結構模型,以魯棒性指標為網絡性能測度,研究了節點攻擊策略對網絡性能的影響,通過設計的進化算法對軍事通信網絡結構優化問題進行研究,得到了相應的結論,驗證了算法的合理性和有效性。本文的研究結果對軍事通信網絡的性能優化問題具有一定的參考價值。但是,本文僅考慮了針對節點的惡意攻擊策略,實際的攻擊對象還應包含鏈路且攻擊策略也是多樣的,這些內容在日后的研究中將逐步深入。