基于相對熵理論的航路網(wǎng)絡魯棒性研究*

任廣建 朱金福 盧朝陽

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

0 引 言

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

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

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

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

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)

對于連續(xù)的隨機變量，定義為

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

1.2 相對熵的意義

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

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

(3)

(4)

由于對數(shù)函數(shù)為上凸函數(shù)，因此

(5)

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

2 航路網(wǎng)絡相關參數(shù)

2.1 節(jié)點距離分布

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

(6)

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

整個網(wǎng)絡的平均距離L定義為所有節(jié)點對之間距離的平均值，即

(7)

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

2.2 節(jié)點聚類系數(shù)

(8)

聚類系數(shù)的幾何意義為

(9)

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

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

整個網(wǎng)絡的聚類系數(shù)C就是所有節(jié)點i的聚類系數(shù)Ci的平均值，即

(10)

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

3 航路網(wǎng)絡魯棒性相對熵模型

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

圖2 航路網(wǎng)絡拓撲結構受攻擊節(jié)點失效

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

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

(11)

由相對熵理論可得

(12)

DR=D(P‖R)=

(13)

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

4 實例分析

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

圖3 上海管制區(qū)域航路網(wǎng)絡圖和拓撲圖

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

圖4 上海航路網(wǎng)絡節(jié)點平均距離和聚類系數(shù)分布

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

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

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

表2 網(wǎng)絡遭受攻擊時，不同節(jié)點失效比例情況下的節(jié)點聚類系數(shù)分布

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

(14)

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

圖5 隨機攻擊與故意攻擊下的網(wǎng)絡平均距離和聚類系數(shù)變化情況

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

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

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

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

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

5 結 論

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

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

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