考慮機場位置與航線流量影響的航空網絡防御資源優化策略

黃海清，甘旭升，蔣旭瑞，吳奇科，孫靜娟

(1.西京學院 理學院，西安 710123)

(2.空軍工程大學 空管領航學院，西安 710051)

(3.解放軍93801部隊 飛行管制室，西安 712200)

0 引 言

隨著航空運輸業的快速發展，我國的航空網絡已逐漸形成并不斷擴張。航空網絡與國家政治、經濟、科技的發展有著緊密聯系，因此，對航空網絡的防御和保障顯得尤為重要。然而現實中的防御資源是有限的，如何利用有限的防御資源使網絡風險最小成為一個重要的研究課題。

航空網絡是典型的復雜網絡，目前，國內外對復雜網絡的抗毀能力、防御能力已經開展了較為深入的研究。防御策略主要包括三類，第一類是通過優化網絡的構成來提高網絡的防御性能，例如A.Beygelzimer等[1]通過加邊的方式來優化網絡結構，并且得出其中四種方式的優劣順序，這種方法以解析推導和計算機仿真結合的方式進行，準確性高、實踐性較強；Wang W X等[2]研究了復雜網絡防御性能的熵優化問題，把網絡面對故障的防御性能優化轉化為度分布熵的優化，優化網絡的度分布指數，增加網絡的異質性，達到提高網絡防御性能的目的。這類方法可以有效增強蓄意攻擊下、尤其是在僅有少量節點被攻擊的情況下的網絡抗毀性，但對于航空網絡來說，其網絡結構基本已經固定，很難對其進行改變，因此不適用于航空網絡。第二類是對網絡進行修復來提高網絡的抗毀性，例如Chi L P等[3]通過對基于度大小攻擊后的網絡以一定概率將節點重連的方式修復網絡，來提高隨機網絡穩定性；程杰等[4]考慮了級聯失效效應影響下的網絡邊失效后的修復模型，以此改善地面交通網絡的魯棒性；A.Kvalbein等[5]針對鏈路故障，基于計算全連通拓撲子圖，提出利用彈性路由層(Resilient Routing Layers)來快速中轉受影響的流量，實現網絡修復。這類方法對于短期內可以快速完成修復的網絡具有一定價值，但是由于環境和條件限制，航空網絡難以實施迅速的調整恢復，因此此類方法也缺乏針對性。最后一類是通過分配一定的防御資源到網絡中來降低網絡的風險,例如楊紅娃等[6]從主動防御角度出發，提出了基于介數加權模型的網絡防御資源優化分配方法，顯著降低了網絡的總風險。這類方法主要應用于無權網絡，在分配資源時沒有考慮邊權對關鍵節點確定、資源分配等的影響。但在航空網絡中，航線流量反映機場與航線在網絡中的重要程度，是必須要考慮的因素。

目前，國內外對航空網絡防御問題的研究較少，可以直接借鑒的成果不多，本文借鑒其他領域的成果，對航空網絡的防御策略進行研究。考慮航空網絡自身的特點，提出一種改進的關鍵節點防御資源優化策略，針對蓄意攻擊，從主動防御的角度出發，將航空網絡防御資源進行細化，并考慮流量、機場位置對資源配置的影響，最后通過模擬退火算法進行求解。

1 防御資源優化分配模型

航空網絡防御資源優化分配的目的是使網絡總風險R最小。

(1)

式中：wi為節點vi對網絡風險的影響程度；ri為節點vi失效后的網絡風險值。

有目的破壞一些高鏈接或高負載的關鍵機場節點對航空網絡來說是致命的。如果關鍵節點比其他次關鍵節點分配更多的資源，航空網絡的防御性能會更好。但是由于現實條件的限制，防御資源總和B是有限的：

(2)

式中：j為防御資源類型。

如果只將防御資源分配給關鍵節點，其他大量的次關鍵節點的防御性能就會較差。此時對這些節點進行襲擊，容易導致關鍵節點的孤立，也會造成整個網絡的崩潰。如何確定最佳優化分配方案DAj(j=1,2,3)使網絡總風險R最小具有非常重要的意義。

但是在分配的過程中，如何才能準確反映防御資源量與節點脆弱性的關系，如何結合航線流量、機場位置等因素進行資源分配，如何進行優化分配求解？針對上述問題，以下進行具體分析。

1.1 防御資源與節點脆弱性關系

本文研究的航空網絡防御資源主要針對機場節點。如果將防御資源種類全部列出，必然會降低計算效率。故建立機場節點防御資源體系，即人、設備和管理[7-8]。每種防御資源對節點脆弱性的影響都有所差異，因此要針對不同防御資源研究其與節點脆弱性的關系。

通常，對航空網絡節點配置越多的防御資源，節點的防御性能越好。為了表示防御資源量與節點防御性能的關系，W.Al-Mannai等[9]提出了基于線性模型：

(3)

式中：hi為節點vi的脆弱性；DAi為分配到節點vi的防御資源；maxDAi(i=1,2,…,n)為使節點vi達到最高安全性能的防御資源。

但實際情況不是這樣，因為隨著分配的防御資源增多，每單位防御資源對節點脆弱性的影響會不斷減小。因此，采用如式(4)所示的脆弱性減少冪函數模型來替代線性模型。

(4)

式中：DAij為在j類防御資源下節點vi所分到的防御資源；maxDAij為使vi節點達到最高級別安全需要的防御資源；aj(j=1,2,3)為hi對不同防御資源對應的冪指數，每種防御資源的冪指數aj都有所差異。

根據機場節點防御資源體系，由于每種防御資源分配的多少對節點防御能力的影響都不同，例如隨著人力保障資源和設備保障資源的增加，節點脆弱性的變化速度在每個階段都不同。通過咨詢專家與統計數據資料，對三項防御資源量與節點脆弱性指數進行曲線擬合，得到參數a1=2.1,a2=2.5,a3=1.8。

1.2 節點與航空網絡風險關系

機場節點在航空網絡中越重要，它對網絡風險的影響就越大。因此要分析節點與網絡風險的關系，首先要對節點進行排序。目前節點重要度排序方法主要有基于度、介數、中心度、重要度評價矩陣等。本文考慮利用重要度評價矩陣進行排序，它是一種考慮全局和局部重要性的排序方法，對于大型網絡具有理想的計算能力，但它沒有考慮航線流量。為了體現機場位置、航線流量的影響，提出改進后的重要度評價矩陣：

(5)

為了能夠體現機場節點在航線網絡運輸過程中所起的作用，結合航班流量，引入點強

(6)

式中：Ni為節點vi的鄰居節點集；wij為與節點vi直接相連邊的權重，權值越大，說明該機場與周圍機場聯系越緊密，重要性越高。

根據重要度評價矩陣，對所有與機場vi相鄰的機場的重要度貢獻求和，可以得到

(7)

ci反映了節點vi在網絡中本身的價值。重要度評價矩陣充分考慮了節點的位置以及航線流量，比較全面地反映了節點的重要性。

基于風險分析模型[10]，將節點vi失效后的網絡風險定義為ri，即

ri=tihici

(8)

(9)

式中：ti為節點vi受到攻擊的概率；hi為節點vi受到攻擊時性能下降率，配給節點vi較多的防御資源時，hi值相對較小；ci為節點vi受到攻擊后造成的損失；dik為攻擊者到目標機場節點vi的距離。可見攻擊概率與距離成反比，與攻擊效益成正比。

為了深入研究網絡風險，設網絡中有n個關鍵節點，不考慮連邊的風險，得到網絡總風險R為

(10)

式中：wi為節點vi對整個網絡風險的影響值。

本文選擇用節點效率Ei作為航空網絡風險影響值，令wi=Ei。

本文研究的是航空網絡中關鍵節點受到攻擊時，比如“節點失效”時，對整個網絡風險的影響，以便就此優化分配防御資源，對攻擊者的位置和方向并不關心，僅需設置統一常數值即可。

1.3 防御資源優化分配

設分配給所有機場節點的防御資源總量為

(11)

式中：Bj為j類防御資源，表示Bj不能讓所有節點的防御性能都最高。

要想使所有節點的網絡風險總和最小，就要尋求一種對B的最優分配方案DAj={DA1j,DA2j,…,DAnj}(j=1,2,3)，從而達到對網絡最好的防御和保護效果[11]。

由式(7)～式(10)式可得網絡的總風險：

(12)

防御資源的優化分配，其目的是使網絡的總風險值最小，故將優化的目標函數設為

(13)

約束條件為

(14)

約束條件表示所有節點分配得到的防御資源總和不大于總防御資源，每個節點分配到的防御資源不大于其自身最高級別的安全所需的防御資源。

需要說明的是，在航空網絡構建中，機場位置、航線流量不僅影響主干網絡，也影響著區域網絡。主干網絡具有優化航線結構、合理配置資源、增強關鍵節點防御能力等多重功效；區域網絡具有明顯的區域特性，提供一定區域內各機場之間以及和主要機場的連接任務，可以看作是主干網絡的補充。在航空網絡防御資源優化過程中，主干網絡與區域網絡分別單獨生成，最終將兩者合并，從而確定最終的航空網絡，進而統一按照優化策略去配置防御資源。

2 模擬退火算法求解

模擬退火算法是一種通用隨機搜索算法，源于對固體退火過程的直接簡單模擬[12-13]。為了找出滿足目標函數(式(13))和約束條件(式(14))的最優分配解方案，可考慮航空網絡中防御資源實際，利用模擬退火算法的優勢在可行解空間中隨機搜索。

為了便于模擬退火算法求解，先對n個節點V={v1,v2,…,vn}按照重要度進行排序，記為{v1,v2,…,vn}順序。則模擬退火算法的具體實現步驟如下：

輸入：關鍵節點組成的航空網絡帶權鄰接矩陣，maxDAij，總防御資源Bj(j=1,2,3)。

輸出：防御資源分配方案DAij，網絡總風險R。

Step2：賦值初始溫度T0=Tmax。

Step3：循環初值num=1；用floyd算法[14]求出dik、Ei、ci，并由初始解求出目標函數值R。

Step4：對當前最優解進行交換操作，產生一個新的最優解，計算目標函數，得到兩次目標函數的增量Δ。

Step5：確定是否接受新產生的最優解(Metropolis規則[15])。如果Δ<0，新的解為當前最優解，否則以概率P=exp(-Δ/T0) 接受新的解為當前最優解。

Step6：判斷num，當num小于終止步數時，num=num+1，回到第Step3，否則進行降溫，使T0=a·T0，其中0

Step7：若m次降溫后最優解未改善或降溫到給定的閥值，則轉至Step8；否則轉至Step3。

Step8：若防御資源已分配完，則輸出當前最優解，計算結束；否則，進行二次分配，即再從剩余的防御資源中依次抽取防御資源隨機分配給節點vi(i=1,2, …,n)。

Step9:當剩余的防御資源分配完后，轉至Step1重新執行新的模擬退火。但此時模擬退火只對第二次新分配的防御資源進行交換操作，第一次模擬退火的分配結果只參與式(8)中的運算。

3 實驗分析

3.1 算例驗證

為了驗證算法的有效性，本文采用隨機生成網絡，并對邊進行賦權，以此作為關鍵節點防御資源優化算例，網絡拓撲圖如圖1所示(圖中正體數字為節點編號，斜體數字為邊權值)。仿真時涉及的參數設定為：初始溫度T0=100，終止溫度Tmin=0.01，溫度下降系數a=0.9，循環次數num=1 000。

圖1 隨機生成加權網絡拓撲

為了便于計算，優化分配時，只考慮一種防御資源，且總量為10 000，maxDAij(i=1,2,…,16;j=1)如表1所示。經實驗仿真，得到各節點的防御資源量如表1所示。R1為在本文算法進行防御資源分配后的網絡風險；R2為在運用文獻[6] 方法分配下的網絡風險。

從表1可以看出：節點4, 11, 14, 16為主要關鍵節點，它們分配的防御資源也相對較多；通過對比2, 3號節點，可以發現，在其他條件同等水平的情況下，邊權值較大的2號節點獲得的防御資源相對更多；對比1, 12號節點，在其他條件同等水平情況下，更接近網絡中心的12號節點獲得更多的資源。表明本文算法有效地考慮了網絡邊權和節點位置。同樣分配10 000個單位的防御資源，本文的分配算法使網絡風險從不考慮邊權、節點位置的7 050降低到6 153[6]，降低了12.7%。

表1 隨機網絡拓撲的各節點優化分配結果

3.2 算例分析

實驗中，對2016年5月全國199個彼此開通航線的機場(一個城市多個機場合并)一周內飛行班次進行統計，實驗數據從http:∥www.qunar.com網站獲取。得到關于機場與機場之間航班數矩陣M=(aij)199×199，這里將航班數作為航線流量，即邊權，從而得到關于中國航空網絡的一個鄰接矩陣A=(aij)n×n。假設三項防御資源中每項防御資源量為2 000，根據本文優化算法，得到各個機場節點的防御資源量，如表2所示(取前12個機場節點)。模擬退火仿真時涉及的參數設定為：初始溫度T0=100，終止溫度Tmin=0.01，溫度下降系數a=0.9，循環次數num=1 200。maxDAij(i=1,2,…,12;j=1,2,3) 在表2中給出。

表2 12個機場節點防御資源分配結果

從表2可以看出：運用本文提出的航空網絡防御資源優化策略進行資源分配，從防御資源量分布的情況來看，北、上、廣三個城市分配所得防御資源量相對于其他城市較多，而它們的航線流量也是最大的；西安地處航空網絡中心，分配到的防御資源量也較多。顯然，航線流量和機場位置是防御資源配置時需要考慮的重要因素，本文算法能夠很好地結合這些因素。

航空網絡防御資源平均分配方法，文獻[6]所提分配方法以及本文方法的對比如圖2所示。

圖2 三種方法效果對比

從圖2可以看出：文獻[6]方法在對資源進行優化分配后網絡風險從平均分配的5 012降到了4 583，降低了8.6%；而運用本文算法得出的網絡總風險為R1=3 662，相比于不考慮航線流量和機場位置的文獻[6]，顯著降低了網絡風險值，較平均分配下降26.9%，表明本文提出的防御資源優化分配模型具有明顯的優越性，在航空網絡應用方面具有較高價值；此外，不同防御資源的優化分配方案都有所差異，這是每種防御資源與網絡脆弱性的關系決定的，但總體來說，分配方案具有很大的相似性。

4 結 論

(1) 本文對三種防御資源進行了區分，并提出利用邊權、重要度評價矩陣、接近度等指標評價節點的重要性，考慮了以往航空網絡防御資源優化研究中忽略的影響因素，從而更全面、更科學地排序節點的重要度，是對航空網絡節點評價指標的一種新的嘗試和補充。

(2) 在對網絡節點的重要度進行正確排序的基礎上，分析了節點脆弱性與網絡風險之間的關系，并采用模擬退火算法求解風險最小前提下各節點配置的防御資源量，實驗驗證了本文方法的可行性和可靠性，可為網絡防御資源優化分配提供科學的技術支撐，也為下一步研究航空網絡防御策略奠定了基礎。

(3) 以機場或者導航點為節點，以航線航路作為邊的網絡，尚無法準確描述實際的航空網絡。后續工作還需深入探究機場網絡、航路網絡和管制網絡等不同層次網絡的防御資源優化分配問題。