任廣建 朱金福 盧朝陽(yáng)

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

0 引 言

航路網(wǎng)絡(luò)是航空運(yùn)輸?shù)闹饕d體，對(duì)于空中交通的高效性和有序性有重要作用.交通運(yùn)輸網(wǎng)絡(luò)的規(guī)劃研究不僅要從外部指標(biāo)進(jìn)行評(píng)價(jià)，還要分析整體性能.航路網(wǎng)絡(luò)系統(tǒng)作為一個(gè)復(fù)雜系統(tǒng)，其拓?fù)浣Y(jié)構(gòu)特性的研究，為網(wǎng)絡(luò)整體規(guī)劃研究提供了重要理論基礎(chǔ)，而魯棒性是復(fù)雜網(wǎng)絡(luò)系統(tǒng)最基本和最重要的特征之一.

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

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

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

1 相對(duì)熵理論

1.1 相對(duì)熵的概念

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

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

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

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

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

1.2 相對(duì)熵的意義

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

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

(3)

(4)

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

(5)

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

2 航路網(wǎng)絡(luò)相關(guān)參數(shù)

2.1 節(jié)點(diǎn)距離分布

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

(6)

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

整個(gè)網(wǎng)絡(luò)的平均距離L定義為所有節(jié)點(diǎn)對(duì)之間距離的平均值，即

(7)

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

2.2 節(jié)點(diǎn)聚類(lèi)系數(shù)

(8)

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

(9)

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

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

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

(10)

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

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

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

圖2 航路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)受攻擊節(jié)點(diǎn)失效

航路節(jié)點(diǎn)平均距離和聚類(lèi)系數(shù)在相對(duì)熵魯棒模型中的應(yīng)用具有相似性，這里以節(jié)點(diǎn)平均距離為例來(lái)說(shuō)明相對(duì)熵魯棒模型的建立過(guò)程.

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

(11)

由相對(duì)熵理論可得

(12)

DR=D(P‖R)=

(13)

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

4 實(shí)例分析

以上海管制區(qū)域航路運(yùn)輸網(wǎng)絡(luò)為研究對(duì)象,上海區(qū)域航路運(yùn)輸網(wǎng)絡(luò)是中國(guó)最復(fù)雜，最繁忙的航空運(yùn)輸系統(tǒng)之一，因此，研究上海航空運(yùn)輸網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)特性，可以較好的反映當(dāng)前空中運(yùn)行的復(fù)雜情況，有利于進(jìn)一步了解航空運(yùn)輸系統(tǒng)整體特性.上海區(qū)域航路網(wǎng)中大約有218個(gè)航路段，每個(gè)航路段以機(jī)場(chǎng)、導(dǎo)航點(diǎn)和航路交叉點(diǎn)相連接構(gòu)成了航路網(wǎng)絡(luò)圖.以區(qū)域航路段為邊，航路點(diǎn)為節(jié)點(diǎn)構(gòu)成了航路網(wǎng)絡(luò)拓?fù)鋱D，見(jiàn)圖3.

圖3 上海管制區(qū)域航路網(wǎng)絡(luò)圖和拓?fù)鋱D

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

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

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

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

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

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

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

(14)

分別對(duì)隨機(jī)攻擊和故意攻擊后，上海航路的網(wǎng)絡(luò)平均距離和網(wǎng)絡(luò)聚類(lèi)系數(shù)的分析見(jiàn)圖5.

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

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

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

圖6 隨機(jī)攻擊與故意攻擊下的節(jié)點(diǎn)平均距離和聚類(lèi)系數(shù)相對(duì)熵變化

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

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

5 結(jié) 論

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

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

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