基于相對熵理論的航路網絡魯棒性研究*

任廣建 朱金福 盧朝陽

(南京航空航天大學民航學院 南京 211106)

0 引 言

航路網絡是航空運輸的主要載體，對于空中交通的高效性和有序性有重要作用.交通運輸網絡的規劃研究不僅要從外部指標進行評價，還要分析整體性能.航路網絡系統作為一個復雜系統，其拓撲結構特性的研究，為網絡整體規劃研究提供了重要理論基礎，而魯棒性是復雜網絡系統最基本和最重要的特征之一.

在受擾或不確定的情況下，魯棒性是復雜系統抗拒干擾生存的關鍵.魯棒性已經成為交通網絡領域中的熱點問題.文獻[1]研究了無標度網絡在隨機攻擊和蓄意攻擊下的魯棒性，結果表明，無標度網絡在蓄意攻擊下魯棒性較弱，而隨機攻擊時魯棒性較強.文獻[2]利用蒙特卡洛方法估計最短路的分布情況，并以此評估了交通網絡的魯棒性.劉宏鯤等[3]研究了中國城市航空網絡的拓撲結構，并指出中國航空網的小世界特性，進一步分析了網絡的魯棒特性.文獻[4]分析了社交網絡的特性，并對網絡的魯棒中心性進行了研究.航路網絡的穩定性直接影響空中交通管制流量控制的有效性，因此，提高航路的穩定性對于流量管理具有支撐作用.文獻[5]就如何改進航空運輸網絡的結構特性，提高魯棒性進行了深入研究，并給出了改進方案.周漩等[6]利用緊密度和特征向量等結構參數對網絡的魯棒性進行研究，并且得出節點度和介數對網絡魯棒性影響較大.文獻[7]提出利用節點效率來評估復雜網絡的魯棒性，實驗表明，該方法對于大型復合網絡具有良好的效果.賴麗萍[8]分析了軌道交通網絡的特性，并對其魯棒性進行了深入的研究.網絡中節點重要性度量對于網絡魯棒性具有重要意義，度和聚集系數可以有效的度量節點重要性.文獻[9]用一種節點演化級聯失效模型，對網絡脆弱度進行了評估研究，仿真實驗表明，此方法是有效的.Schneider等[10]提出一種減緩網絡攻擊的方法，并證明了其提高網絡魯棒性的可行性.文獻[11]基于魯棒優化問題，對城市交通網絡進行了研究，建立了不確定情況下的城市交通網路魯棒性優化模型，并進行了優化求解.

近年來，熵理論越來越多的被應用到復雜網絡系統中.文獻[12]利用相對熵理論對系統中的決策排序問題進行了研究.Anand等[13]定義了熵的構造特性并指出香農熵結構特性與吉布斯和馮諾依曼熵的關聯性.Xu等[14]提出了一種新的系統度依存熵指標，來描述度與相應特征的關系.文獻[15]利用相對熵原理對中國鐵路拓撲結構的魯棒性進行了研究，對復雜網絡中節點相似度進行了研究，這對于進一步研究網絡的結構特性和魯棒性具有重要意義.

基于以上研究，以相對熵理論為基礎，針對航路網絡受到隨機攻擊和故意攻擊的情況，分析航路節點平均距離和聚類系數的分布變化情況，進而分析計算相對熵的大小，建立相對熵評估模型，來衡量航路網絡魯棒性強弱.

1 相對熵理論

1.1 相對熵的概念

相對熵(relative entropy)，又稱KL散度(kullback leibler divergence, KLD),是描述兩個概率分布P和Q差異的一種方法.

設P(x)和Q(x)是X取值的兩個離散概率分布，則P對Q的相對熵為

D(P‖Q)=∑(P(x)log(P(x)/Q(x))) (1)

對于連續的隨機變量，定義為

相對熵是兩個概率分布P和Q差別的非對稱性的度量，即D(P‖Q)≠D(Q‖P)，因此它并不表示一個真正的度量或者距離.在信息論領域，D(P‖Q)為用概率分布Q來擬合真實分布P時，產生的信息消耗，這里P為真實的概率分布，Q為真實分布的擬合分布.此外，相對熵的值是非負的，即D(P‖Q)≥0.

1.2 相對熵的意義

信息領域中，相對熵是用來度量使用基于Q的編碼來編碼來自P的樣本平均所需的比特個數.特別情況下，P為數據的真實分布，Q為數據的理論分布、模型分布或P的近似分布.

由信息論的知識可知，給定一個字符集的概率分布，就可以設計一種編碼，使得表示該字符集組成的字符串平均需要的比特數最少.假定，該字符集為X，對于x∈X，其出現概率為P(x)，這時最優編碼平均需要的比特數等于這個字符集的熵：

(3)

(4)

由于對數函數為上凸函數，因此

(5)

由式(5)可知，相對熵始終是大于等于0的，并且只有當兩個分布相同時，相對熵等于0.相對熵可以衡量兩個隨機分布之間的距離，當兩個分布越相近時，相對熵的值越小；兩個分布的差別增大時，相對熵的值也會增大.所以，相對熵可以比較事物分布的相似度，評估事物變化的相對大小.本文利用相對熵的理論對航路網絡在受擾情況下的魯棒性進行分析.

2 航路網絡相關參數

2.1 節點距離分布

對于航路網絡G=(N,E).式中：N為節點數；E為節點邊數，網絡平均距離是途徑的平均邊數量(每條邊長度為1).本文考慮單個節點到其他所有節點的平均距離分布情況，即節點i到節點j(i≠j,j∈N)的途徑邊數，為

(6)

式中：Li(i=1,2,…,N)為第i節點的平均距離；dij為節點i與節點j之間的距離.

整個網絡的平均距離L定義為所有節點對之間距離的平均值，即

(7)

當網絡受到攻擊節點被刪除時，節點的平均距離就會發生變化，變化的相對大小可以作為衡量航路網絡魯棒性的指標.

2.2 節點聚類系數

(8)

聚類系數的幾何意義為

(9)

與節點i相連的三元組是指包含節點i的三個節點，并且至少存在從節點i到其他兩個節點的兩條邊，見圖1.

圖1 以節點i為頂點之一的三元組的兩種可能形式

整個網絡的聚類系數C就是所有節點i的聚類系數Ci的平均值，即

(10)

航路網絡受到攻擊時，有的節點被刪除，進而與其相連的邊也被刪除，因此，節點的聚類系數會發生變化.節點聚類系數變化幅度大小可用于衡量網絡的魯棒性.

3 航路網絡魯棒性相對熵模型

魯棒性用以表征控制系統對特性或參數擾動的不敏感性，即系統的抗干擾能力.這里用以表征航路網路受到攻擊時，結構特性發生變化的程度，航路網絡所呈現的后果，即航路網絡抗干擾性.這里航路網絡受到攻擊刪除節點的方式為兩種，見圖2.

圖2 航路網絡拓撲結構受攻擊節點失效

航路節點平均距離和聚類系數在相對熵魯棒模型中的應用具有相似性，這里以節點平均距離為例來說明相對熵魯棒模型的建立過程.

令航路節點平均距離分布在[Lmin,Lmax]范圍內，把該區間平均分成m段，原始網絡節點平均距離值落在每個區間內的概率為P(xi)=pi(i=1,2,…,m)；當網絡受到隨機攻擊時，隨機刪除一定的節點，這時網絡節點平均距離值落在每個區間內的概率為Q(xi)=qi(i=1,2,…,m)；網絡受到基于度故意攻擊時，刪除度較大的節點，這時網絡節點平均距離值落在每個區間內的概率為R(xi)=ri(1=1,2,…,m).則隨機變量x的分布律為

(11)

由相對熵理論可得

(12)

DR=D(P‖R)=

(13)

比較兩個相對熵值可知，當DQ>DR時，隨機攻擊對航路網絡的影響較大，網絡魯棒性在故意攻擊下要比在隨機攻擊下保持的要好；當DR>DQ時，故意攻擊對航路網絡的影響較大，魯棒性在隨機攻擊下的保持度要好于故意攻擊情況.特別的，當DQ=DR時，這說明航路網絡在受到隨機攻擊和故意攻擊時，結構特性受影響程度相同，兩種攻擊對網絡魯棒特性的影響基本是一樣的.

4 實例分析

以上海管制區域航路運輸網絡為研究對象,上海區域航路運輸網絡是中國最復雜，最繁忙的航空運輸系統之一，因此，研究上海航空運輸網絡系統結構特性，可以較好的反映當前空中運行的復雜情況，有利于進一步了解航空運輸系統整體特性.上海區域航路網中大約有218個航路段，每個航路段以機場、導航點和航路交叉點相連接構成了航路網絡圖.以區域航路段為邊，航路點為節點構成了航路網絡拓撲圖，見圖3.

圖3 上海管制區域航路網絡圖和拓撲圖

圖3b)中三角形為度較大的節點，該節點對航路結構特性影響較大，航路受到隨機攻擊時度大的節點不一定會受影響，而故意攻擊時往往從度較大的節點開始.因此，隨機攻擊和故意攻擊可以反映網絡系統不同的魯棒特性.通過對上海航路結構特性數據的計算與分析，可得到該航路網絡的節點平均距離分布和節點聚類系數分布情況，見圖4.

圖4 上海航路網絡節點平均距離和聚類系數分布

對于上海航路網絡分別進行節點隨機攻擊和節點按度大小攻擊，由此相應的節點失效后，對剩余航路網絡的節點平均距離進行計算和統計分析見表1.

表1 網絡遭受攻擊時，不同節點失效比例情況下的節點平均距離分布

上海航路網絡遭受不同比例的隨機攻擊和故意攻擊后，各個節點的聚類系數分布情況見表2.

表2 網絡遭受攻擊時，不同節點失效比例情況下的節點聚類系數分布

基于相對熵原理，分別對航路網絡遭受隨機和故意攻擊下，計算相應的相對熵值.這里以航路有5%節點遭受攻擊失效時，節點平均距離變化情況為例來說明相對熵理論的應用.令pi為原始航路網絡的節點平均距離分布，qi為航路網絡遭受隨機攻擊時節點的平均距離分布，ri為航路網絡遭受故意攻擊時節點的平均距離分布.航路網遭受隨機和故意攻擊時節點平均距離的分布律為

(14)

分別對隨機攻擊和故意攻擊后，上海航路的網絡平均距離和網絡聚類系數的分析見圖5.

圖5 隨機攻擊與故意攻擊下的網絡平均距離和聚類系數變化情況

由圖5a)可知，上海航路網絡遭受攻擊時，隨著節點失效比例的增加，網絡平均距離不斷增加，其中故意攻擊時，網絡平均距離的增長幅度較大且變化速度較快，這時網絡魯棒性較弱.由圖5b)可知，網絡聚類系數隨著節點失效比例的增加而減小，其中，故意攻擊時，網絡聚類系數呈快速下降趨勢，而隨機攻擊時，變化趨勢比較緩和，說明隨機攻擊的網絡魯棒性要強于故意攻擊.

在兩種攻擊情況下，對節點平均距離和節點聚類系數的相對熵進行計算和分析，可知該航路網絡參數的相對熵變化情況見圖6.

圖6 隨機攻擊與故意攻擊下的節點平均距離和聚類系數相對熵變化

由圖6a)可知，上海航路網絡的節點平均距離隨著遭受攻擊節點比例的增加，相對熵變化幅度也逐漸增大.其中，遭受隨機攻擊時，航路節點平均距離相對熵呈現緩慢增長趨勢；遭受故意攻擊時，航路節點平均距離相對熵增長幅度較快.航路網絡遭受故意攻擊時，節點平均距離相對熵變化幅度大于遭受隨機攻擊時，這說明故意攻擊對航路網絡節點平均距離的影響大于隨機攻擊.由圖6b)可知，航路網絡的節點聚類系數隨著遭受攻擊節點比例的增加，相對熵也不斷增大.而且，遭受隨機攻擊時，航路聚類系數相對熵變化比較緩慢；遭受故意攻擊時，航路節點聚類系數相對熵呈快速變化趨勢.航路網絡遭受故意攻擊時，節點聚類系數相對熵變化幅度大于遭受隨機攻擊時，這說明故意攻擊對航路網絡節點聚類系數的影響大于隨機攻擊.

總體而言，上海航路網絡遭受故意攻擊時，網絡節點參數的相對熵變化值要大于隨機攻擊，且變化速度也較快.因此，上海航路網絡遭受故意攻擊時，航路結構特性變化較大，即抗干擾能力較差，魯棒性較弱；遭受隨機攻擊時，航路特性在一定的范圍內保持較好，且結構受損程度呈緩慢趨勢，這時魯棒性較好.

5 結 論

1) 航路網絡遭受基于度的故意攻擊時，節點平均距離和聚類系數的相對熵都較大且隨節點失效比例的增大而呈快速變化趨勢，這時航路網絡表現出較弱的魯棒性.

2) 遭受隨機攻擊時，相關參數的相對熵都較小且隨節點失效比例的增大而呈緩慢變化趨勢，航路網絡表現出較強的魯棒性.

同時，也驗證了基于相對熵航路網絡魯棒性分析模型的有效性和適用性.因此，航路網絡中度較大的航路節點，對于航空運輸的安全性、暢通性和高效性具有重要意義，為了提高航空運輸效率減少延誤應重點關注度大的航路點.