不同增長機(jī)制下航空網(wǎng)絡(luò)自愈特性

傅超琦，王瑛，李超，孫贇

(空軍工程大學(xué) 裝備管理與安全工程學(xué)院，西安710038)

隨著科技的發(fā)展和社會(huì)的進(jìn)步，中國對(duì)航空運(yùn)輸?shù)男枨蟛粩嘣黾?，航空網(wǎng)絡(luò)的建設(shè)越來越完善，也越來越趨于復(fù)雜。中國航空網(wǎng)絡(luò)(ANC)結(jié)構(gòu)極不均勻［1］，全國范圍內(nèi)存在嚴(yán)重的區(qū)域性差異，與東部相比，西部地區(qū)的航空網(wǎng)絡(luò)還有很大的完善空間。而東部地區(qū)的網(wǎng)絡(luò)結(jié)構(gòu)中，“北上廣”地區(qū)的飛行需求占整個(gè)流量的70%，極度不均勻的流量分布使得航空網(wǎng)絡(luò)存在許多潛在的風(fēng)險(xiǎn)。而且高峰時(shí)段大量的飛行計(jì)劃，也使得那一時(shí)段的航空網(wǎng)絡(luò)變得極其脆弱。同時(shí)，不確定強(qiáng)氣流天氣影響下，區(qū)域的飛行計(jì)劃調(diào)整，可能會(huì)對(duì)整個(gè)航空網(wǎng)絡(luò)都產(chǎn)生影響，很考驗(yàn)網(wǎng)絡(luò)的魯棒特性。

復(fù)雜網(wǎng)絡(luò)［2-3］是在計(jì)算機(jī)科學(xué)取得巨大發(fā)展后的技術(shù)支持下所發(fā)展起來的，是從整體上研究復(fù)雜系統(tǒng)特性的理論方法。復(fù)雜網(wǎng)絡(luò)在眾多領(lǐng)域的應(yīng)用都取得了豐碩的成果［4-8］。其中，也有很多學(xué)者將復(fù)雜網(wǎng)絡(luò)理論與航空航天領(lǐng)域相結(jié)合，通過復(fù)雜網(wǎng)絡(luò)來研究現(xiàn)有航空網(wǎng)絡(luò)在整體規(guī)劃上的魯棒性和演化特性［9-14］。Amara 等［11］的研究證實(shí)了世界航空網(wǎng)(WAN)的小世界屬性。Guimera等［12］揭示了WAN中大度值節(jié)點(diǎn)并不一定是最具影響的節(jié)點(diǎn)，這意味著航空網(wǎng)絡(luò)中的關(guān)鍵位置可能與高度連接的樞紐不一致。Gautreau等［13］從局部動(dòng)力特性方面對(duì)美國航空網(wǎng)絡(luò)的進(jìn)行了研究，并提出了一種動(dòng)態(tài)網(wǎng)絡(luò)模型來研究網(wǎng)絡(luò)的統(tǒng)計(jì)特性。Chi等［14］對(duì)美國航空網(wǎng)絡(luò)的演化特性進(jìn)行了分析，發(fā)現(xiàn)其具有雙冪率分布的特性。Li和Cai［15］對(duì)ANC的統(tǒng)計(jì)特性進(jìn)行了相應(yīng)的研究，揭示了ANC的小世界屬性和每個(gè)機(jī)場的出度與入度的正相關(guān)性，以及其與相鄰機(jī)場度值之間的負(fù)相關(guān)性。Cai等［16］通過對(duì)中國航路網(wǎng)絡(luò)(CARN)的研究發(fā)現(xiàn)其具有與ANC不同的結(jié)構(gòu)特性，且具有同質(zhì)結(jié)構(gòu)的CARN上的飛行流量分布卻是異質(zhì)的。

然而，僅從拓?fù)浣Y(jié)構(gòu)來描述網(wǎng)絡(luò)是不夠準(zhǔn)確的［17］，單純的結(jié)構(gòu)性分析并不能解釋現(xiàn)實(shí)中網(wǎng)絡(luò)大規(guī)模的故障現(xiàn)象，如航班的延誤多數(shù)是受流量的限制，惡劣天氣或襲擊等造成網(wǎng)絡(luò)結(jié)構(gòu)性的破壞往往只占網(wǎng)絡(luò)的小部分，其造成的飛行流量變動(dòng)所引發(fā)的功能性級(jí)聯(lián)失效，才是造成網(wǎng)絡(luò)功能癱瘓的根本原因。無論是電網(wǎng)中的電流、交通網(wǎng)中的車流、信息網(wǎng)中的信息流還是航空網(wǎng)絡(luò)中各節(jié)點(diǎn)的吞吐量及航線上的飛行流量都可以抽象為復(fù)雜網(wǎng)絡(luò)中的能量，能量才是網(wǎng)絡(luò)功能的實(shí)現(xiàn)行式。Barrat等［18］以節(jié)點(diǎn)吞吐量和航距為權(quán)重，分析了動(dòng)態(tài)權(quán)重和空間約束對(duì)航空網(wǎng)絡(luò)演化的影響。Li和Cai［15］以某天的航班數(shù)為基數(shù)研究了CAN的效率與連接緊密度成正比。通過研究網(wǎng)絡(luò)中的能量傳遞規(guī)則可以清楚地了解到整個(gè)復(fù)雜系統(tǒng)中單元之間的能量交互所存在的隱患和不足［19-20］。

大部分的研究都沒有考慮過節(jié)點(diǎn)的自恢復(fù)能力［21］。功能性級(jí)聯(lián)失效并不影響網(wǎng)絡(luò)的結(jié)構(gòu)，當(dāng)過載的能量消退時(shí)，節(jié)點(diǎn)將恢復(fù)其網(wǎng)絡(luò)功能。由于航空網(wǎng)絡(luò)結(jié)構(gòu)的無標(biāo)度性及飛行流量的不均勻性［1，9，16］，當(dāng)網(wǎng)絡(luò)受到攻擊或蓄意破壞時(shí)，會(huì)出現(xiàn)流量的大幅度波動(dòng)，導(dǎo)致整個(gè)航空網(wǎng)絡(luò)的短暫癱瘓，但波動(dòng)過后穩(wěn)定后的網(wǎng)絡(luò)中能量流將以新的規(guī)則發(fā)生作用，部分受影響的節(jié)點(diǎn)將進(jìn)行自愈，可自愈的節(jié)點(diǎn)反映的是網(wǎng)絡(luò)應(yīng)對(duì)破壞的彈性恢復(fù)能力。因此，自愈后的網(wǎng)絡(luò)能夠更準(zhǔn)確地反映網(wǎng)絡(luò)的魯棒性。且隨著航空網(wǎng)絡(luò)的發(fā)展，大量新增節(jié)點(diǎn)及航線必然會(huì)通過網(wǎng)絡(luò)結(jié)構(gòu)的改變影響網(wǎng)絡(luò)的特性，怎樣規(guī)劃網(wǎng)絡(luò)的增長機(jī)制能夠更好地在保證網(wǎng)絡(luò)魯棒性的前提下完善網(wǎng)絡(luò)也有待研究。

本文著眼于航空網(wǎng)絡(luò)的恢復(fù)魯棒性，從能量的角度出發(fā)，考慮網(wǎng)絡(luò)的自愈能力來分析整個(gè)網(wǎng)絡(luò)在結(jié)構(gòu)和流量分布上的合理性;并針對(duì)網(wǎng)絡(luò)的生長特性，仿真分析了航空網(wǎng)絡(luò)不同增長機(jī)制可能對(duì)網(wǎng)絡(luò)整體自愈特性的影響。本文真實(shí)網(wǎng)絡(luò)數(shù)據(jù)選擇美國航空網(wǎng)，一是由于其經(jīng)典的復(fù)雜網(wǎng)絡(luò)特性已被許多學(xué)者所研究證實(shí);二是在于其數(shù)據(jù)來源的可靠性與便利性，可從美國官方網(wǎng)站［22］直接下載所得;三是已有的研究表明中國的航空網(wǎng)絡(luò)特性與美國航空網(wǎng)絡(luò)相接近，如雙段冪率及層級(jí)結(jié)構(gòu)等［15，22］，且中國未來的航空網(wǎng)絡(luò)發(fā)展可以借鑒其網(wǎng)絡(luò)規(guī)劃。因此，研究美國航空網(wǎng)絡(luò)不同增長機(jī)制下的自愈特性可以為中國未來完善航空網(wǎng)絡(luò)建設(shè)提供參考。

本文首先對(duì)復(fù)雜網(wǎng)絡(luò)理論在航空方面的研究現(xiàn)狀進(jìn)行了綜述，并介紹了網(wǎng)絡(luò)基本模型及增長機(jī)制;然后依據(jù)網(wǎng)絡(luò)能量流動(dòng)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行了劃分，并對(duì)仿真實(shí)現(xiàn)的算法進(jìn)行了介紹;最后展示了仿真結(jié)果，并分析了其原因和影響。

1 網(wǎng)絡(luò)模型介紹

將機(jī)場抽象為復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)，若兩機(jī)場之間存在飛行安排，則建立連邊表示航線。構(gòu)建圖G=(V，E)表示復(fù)雜網(wǎng)絡(luò)，節(jié)點(diǎn)集合V=(v1，v2，…，vn)為網(wǎng)絡(luò)N個(gè)節(jié)點(diǎn)的集合，連邊集合E=(e1，e2，…，em)∈V×V為網(wǎng)絡(luò) M 條連邊的集合。

1.1 網(wǎng)絡(luò)自愈模型

自愈特性指的是在結(jié)構(gòu)未被損壞，但功能受到影響而失效的情況下，當(dāng)外界因素消失后，功能自主恢復(fù)的特性。網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)反映的是網(wǎng)絡(luò)各節(jié)點(diǎn)的關(guān)聯(lián)關(guān)系，但造成網(wǎng)絡(luò)功能缺失的原因不僅僅只有關(guān)聯(lián)關(guān)系的斷裂。結(jié)構(gòu)未被損壞，但功能受到影響也是網(wǎng)絡(luò)功能失效的重要原因。在航空網(wǎng)絡(luò)中，飛行流量控制是航空網(wǎng)絡(luò)安全的重要因素之一。若將飛行流量看作網(wǎng)絡(luò)中的能量流動(dòng)，網(wǎng)絡(luò)中不恰當(dāng)?shù)哪芰苛鲃?dòng)是造成網(wǎng)絡(luò)功能缺失和網(wǎng)絡(luò)無法自愈的主要原因。最初，Motter與Lai提出了經(jīng)典負(fù)載-容量模型(ML 模型)［23］，以負(fù)載表示各節(jié)點(diǎn)或鏈路上流通的能量，以容量表示節(jié)點(diǎn)或鏈路對(duì)能量的承載能力，當(dāng)負(fù)載超過容量時(shí)，節(jié)點(diǎn)或鏈路失效，負(fù)載的重分配將引起新一輪的節(jié)點(diǎn)失效，從而導(dǎo)致網(wǎng)絡(luò)大面積崩潰。在此之后大量的相關(guān)模型被提出，不僅彌補(bǔ)了ML模型的缺陷也更加細(xì)致地刻畫了真實(shí)世界復(fù)雜系統(tǒng)能量的傳遞規(guī)律。

本文選擇Wang等［24］所建立的負(fù)載模型Li=，模型中節(jié)點(diǎn)負(fù)載L與節(jié)點(diǎn)連接度k緊密相關(guān)，度值k為與該機(jī)場有飛行往來的機(jī)場的數(shù)目，度值越大表明該機(jī)場規(guī)模越大，反映了機(jī)場的連通性越好，工作流量越大，其中負(fù)載參數(shù) θ＞0。Yang等［25］建立的非線性負(fù)載-容量模型為Ci=α +βLi=Li+ΔCi，其中 Ci為節(jié)點(diǎn) i的容量;α 和 β均為非線性容量參數(shù);ΔCi為節(jié)點(diǎn)冗余容量，表示機(jī)場預(yù)留的處理突發(fā)狀況的能力。假設(shè)某個(gè)節(jié)點(diǎn)發(fā)生故障，其負(fù)載將由其相鄰節(jié)點(diǎn)共同承擔(dān)。采用負(fù)載擇優(yōu)分配規(guī)則［24］實(shí)現(xiàn)失效節(jié)點(diǎn)負(fù)載的重分配，其規(guī)則如下:

式中:Γi為失效節(jié)點(diǎn)i的所有相鄰節(jié)點(diǎn)集合。式(1)表明負(fù)載越大的節(jié)點(diǎn)承受的重分配越多。此時(shí)，節(jié)點(diǎn) j所承受的總的轉(zhuǎn)移能量為 ΔLj=為節(jié)點(diǎn)j相鄰的所有失效節(jié)點(diǎn)集合。

當(dāng)網(wǎng)絡(luò)中部分關(guān)鍵點(diǎn)被破壞后，網(wǎng)絡(luò)功能的缺失將在一段時(shí)間內(nèi)造成網(wǎng)絡(luò)中能量的巨大波動(dòng)，從而使得更多的節(jié)點(diǎn)受到牽連造成暫時(shí)的功能失效，網(wǎng)絡(luò)將處于崩潰狀態(tài)。但當(dāng)這一短暫的波動(dòng)期過后，恢復(fù)穩(wěn)定的網(wǎng)絡(luò)將開始自愈。若無外界干擾，自愈的節(jié)點(diǎn)將會(huì)受到其相鄰失效節(jié)點(diǎn)的再次能量沖擊。若節(jié)點(diǎn)j滿足ΔLj≤ΔCj，表明節(jié)點(diǎn)j可以承受其相鄰失效節(jié)點(diǎn)能量沖擊，自愈后不會(huì)再次損壞，能夠恢復(fù)其網(wǎng)絡(luò)功能;反之，則說明節(jié)點(diǎn)j無法自愈，需要額外手段幫助其處理過量的流量。

1.2 航空網(wǎng)絡(luò)增長機(jī)制

網(wǎng)絡(luò)增長機(jī)制［26］是研究復(fù)雜網(wǎng)絡(luò)不容忽略的重要性質(zhì)。據(jù)統(tǒng)計(jì)，目前中國僅1/5城市擁有民用機(jī)場，《中國民用航空發(fā)展第十三個(gè)五年規(guī)劃》規(guī)劃到2020年民用機(jī)場總數(shù)將達(dá)到244個(gè)，其中2010—2020年將新增78個(gè)。網(wǎng)絡(luò)規(guī)模的增長必然帶來結(jié)構(gòu)和功能的改變，不恰當(dāng)?shù)脑鰷p很可能使得新的網(wǎng)絡(luò)結(jié)構(gòu)存在嚴(yán)重缺陷。為了更全面地模擬航空網(wǎng)絡(luò)的生長特性，文獻(xiàn)［18］總結(jié)了航空網(wǎng)絡(luò)增長特點(diǎn)的規(guī)律，結(jié)合《中國民用航空發(fā)展第十三個(gè)五年規(guī)劃》中對(duì)新機(jī)場建設(shè)的需求，本文將網(wǎng)絡(luò)新增節(jié)點(diǎn)分為3個(gè)類型，如圖1所示。

1)隨著城市的發(fā)展，在經(jīng)濟(jì)和政治的需求下，建立城市群相對(duì)應(yīng)的機(jī)場群，為加強(qiáng)城市的運(yùn)輸能力并緩解中心機(jī)場的負(fù)荷，在其周邊另建機(jī)場分擔(dān)客流，這類機(jī)場稱為分流機(jī)場;機(jī)場的規(guī)模與城市的經(jīng)濟(jì)相關(guān)，故中心機(jī)場和分流機(jī)場都屬于大負(fù)載機(jī)場。

圖1 新增節(jié)點(diǎn)類型劃分Fig.1 Classification of new nodes

a)分流機(jī)場與中心機(jī)場距離較近，不設(shè)立飛行安排，如上海浦東與虹橋機(jī)場，北京首都機(jī)場及正在建造的大興國際機(jī)場。

b)對(duì)較為重要的大型機(jī)場，兩機(jī)場均可與其有飛行安排;大型機(jī)場之間客流需求較大，兩機(jī)場共同分擔(dān)更為合理。如上海浦東和虹橋機(jī)場均安排有白云機(jī)場的飛行計(jì)劃。

c)對(duì)度值較小的機(jī)場，兩機(jī)場分工合作，不重復(fù)設(shè)置飛行安排。小度值機(jī)場客流量較少，分工合作可以更合理地利用分流機(jī)場和中心機(jī)場的職能，減少重疊負(fù)載。

2)為完善航空網(wǎng)絡(luò)，建設(shè)圍繞中心機(jī)場相對(duì)應(yīng)的機(jī)場群，這類機(jī)場參照《中國民用航空發(fā)展第十三個(gè)五年規(guī)劃》稱為續(xù)建機(jī)場，續(xù)建機(jī)場多為中型機(jī)場。

a)續(xù)建機(jī)場的航線安排通常與其自身的經(jīng)濟(jì)、地域和所處機(jī)場群相關(guān)。并沒有明確的航線安排特點(diǎn)，但偏向于中大型機(jī)場。

3)為滿足相對(duì)偏遠(yuǎn)地區(qū)的經(jīng)濟(jì)開發(fā)和旅游需求而建設(shè)的機(jī)場稱為新興機(jī)場。新興機(jī)場成本較低，故多為小型機(jī)場。

a)新興機(jī)場只與少數(shù)機(jī)場之間存在飛行安排;機(jī)場通常成本不高，所以能力有限，且往往依附其相鄰的大機(jī)場。如德宏芒市機(jī)場的客流大部分由昆明長水國際機(jī)場承擔(dān)。

b)新興機(jī)場側(cè)重與較大型的機(jī)場之間設(shè)置飛行安排，與大型機(jī)場的連接可以減少網(wǎng)絡(luò)的最短路徑，方便游客的到達(dá)。

基于此類特性，在抽象的復(fù)雜網(wǎng)絡(luò)中，對(duì)新增節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)按以下規(guī)則來建立:

1)分流節(jié)點(diǎn)

采取擇優(yōu)連接的方式構(gòu)造其拓?fù)涮匦?，連邊數(shù)可根據(jù)不同需求來設(shè)定。同時(shí)，為了減少中心節(jié)點(diǎn)的度值，將與分流節(jié)點(diǎn)連接的節(jié)點(diǎn)集合同中心節(jié)點(diǎn)的相鄰節(jié)點(diǎn)集合進(jìn)行比較，將其中大度值節(jié)點(diǎn)以較小概率同原節(jié)點(diǎn)斷連，以模擬分流機(jī)場的建設(shè)特點(diǎn)b);將度值較小的節(jié)點(diǎn)以較大概率同原節(jié)點(diǎn)斷連，以模擬分流機(jī)場的建設(shè)特點(diǎn)c)。但兩節(jié)點(diǎn)的總負(fù)載將超過了原本中心節(jié)點(diǎn)的負(fù)載以模擬新增機(jī)場所帶來的更高的新需求。

2)續(xù)建節(jié)點(diǎn)

續(xù)建節(jié)點(diǎn)沒有明顯的連接特點(diǎn)，但偏向于與大度值節(jié)點(diǎn)相連，度值規(guī)?？梢愿鶕?jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在中等規(guī)模浮動(dòng)。本文根據(jù)美國航空網(wǎng)絡(luò)的結(jié)構(gòu)特性設(shè)立續(xù)建節(jié)點(diǎn)度值在1～4倍網(wǎng)絡(luò)平均度之間。

3)新興節(jié)點(diǎn)

采取擇優(yōu)連接的方式構(gòu)造其拓?fù)涮匦?，新興機(jī)場規(guī)模較小，故新興節(jié)點(diǎn)的度值設(shè)置為網(wǎng)絡(luò)平均度的一半。

2 結(jié)構(gòu)劃分與算法實(shí)現(xiàn)

2.1 結(jié)構(gòu)劃分

節(jié)點(diǎn)自愈的關(guān)鍵在于其冗余容量能承受其所接收的轉(zhuǎn)移能量。不同的節(jié)點(diǎn)對(duì)能量沖擊有不同的承受能力，每條邊所承載的轉(zhuǎn)移能量也各不相同。同時(shí)，節(jié)點(diǎn)自愈后其對(duì)相鄰失效節(jié)點(diǎn)的轉(zhuǎn)移能量消失，這將減少其相鄰節(jié)點(diǎn)的負(fù)載，有助于其自愈，從而形成新的循環(huán)。所以，自愈過程是一個(gè)動(dòng)態(tài)過程。

圖2 失效網(wǎng)絡(luò)中的網(wǎng)絡(luò)結(jié)構(gòu)分類Fig.2 Classification of network structure in failure networks

通過對(duì)已有文獻(xiàn)的學(xué)習(xí)和思考，本文發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)負(fù)載及容量之間可劃分為2種類型的相互作用關(guān)系。圖2(a)是一種非耦合結(jié)構(gòu)，節(jié)點(diǎn)上的數(shù)字表示該節(jié)點(diǎn)抵御能量沖擊的冗余容量;有向邊eij上的數(shù)字表示節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的能量。從這個(gè)結(jié)構(gòu)可以看到，出事時(shí)只有節(jié)點(diǎn)A的冗余容量能夠承受相鄰失效節(jié)點(diǎn)的能量沖擊，滿足自愈條件。當(dāng)節(jié)點(diǎn)A自愈后，其對(duì)節(jié)點(diǎn)B和D的轉(zhuǎn)移能量eAB和eAD則消失，此時(shí)，節(jié)點(diǎn)B接收的轉(zhuǎn)移能量也小于其冗余容量，使得節(jié)點(diǎn)B在此時(shí)也可以實(shí)現(xiàn)自愈，當(dāng)由節(jié)點(diǎn)B造成的轉(zhuǎn)移能量eBC和eBD也消失時(shí)，節(jié)點(diǎn)C和D也可滿足自愈條件。該結(jié)構(gòu)中的失效節(jié)點(diǎn)會(huì)以A—B—C—D或A—B—D—C順序自愈，從而恢復(fù)網(wǎng)絡(luò)功能;因此，這種能夠?qū)崿F(xiàn)自恢復(fù)的非耦合結(jié)構(gòu)稱為自愈結(jié)構(gòu)。圖2(b)的結(jié)構(gòu)形式稱為耦合結(jié)構(gòu)，結(jié)構(gòu)內(nèi)各節(jié)點(diǎn)的相互耦合作用形成了一個(gè)閉循環(huán)，使得該結(jié)構(gòu)內(nèi)的任何一個(gè)節(jié)點(diǎn)被修復(fù)時(shí)，都會(huì)由于轉(zhuǎn)移能量大于冗余容量而發(fā)生二次失效;因此，該結(jié)構(gòu)不具有自愈特性。耦合結(jié)構(gòu)的存在說明網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)的負(fù)載及容量之間不匹配，在網(wǎng)絡(luò)設(shè)計(jì)時(shí)應(yīng)盡量避免出現(xiàn)耦合結(jié)構(gòu)。

2.2 算法實(shí)現(xiàn)

為了能夠在仿真過程中模擬自愈過程，本文根據(jù)網(wǎng)絡(luò)的自愈特性提出了以下算法流程:

步驟1 將失效節(jié)點(diǎn)及其相應(yīng)鏈路關(guān)系抽取出來構(gòu)建失效網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)是由單個(gè)節(jié)點(diǎn)遭受攻擊后的級(jí)聯(lián)失效造成的崩潰時(shí)，起始失效網(wǎng)絡(luò)也是連通網(wǎng)絡(luò)。假設(shè)整個(gè)失效網(wǎng)絡(luò)中的失效節(jié)點(diǎn)總數(shù)為S。

步驟2 依次計(jì)算每個(gè)節(jié)點(diǎn)遭受的重分配負(fù)載，當(dāng)節(jié)點(diǎn)i滿足ΔLi≤ΔCi，轉(zhuǎn)到步驟3。如果所有節(jié)點(diǎn)都不滿足上述自愈條件，說明網(wǎng)絡(luò)中只存在與圖2(b)相似的耦合結(jié)構(gòu)，則自愈過程結(jié)束。

步驟3 節(jié)點(diǎn)滿足自愈條件，自愈后從失效網(wǎng)絡(luò)中移除節(jié)點(diǎn)i及其連邊(見圖3)。此時(shí)，失效網(wǎng)絡(luò)的結(jié)構(gòu)發(fā)生變化，重返步驟1。

圖3 自愈流程圖Fig.3 Self-healing flowchart

3 仿真驗(yàn)證與分析

3.1 網(wǎng)絡(luò)自愈特性分析

已有的研究表明，大部分的真實(shí)網(wǎng)絡(luò)都具有BA網(wǎng)絡(luò)的冪率分布特性［26］。為了驗(yàn)證算法的有效性及普適性，構(gòu)建節(jié)點(diǎn)總數(shù)為N=500，平均度為〈k〉≈4的無標(biāo)度網(wǎng)絡(luò)模型。文獻(xiàn)［24］已經(jīng)證明當(dāng)網(wǎng)絡(luò)具有最強(qiáng)魯棒性時(shí)，負(fù)載參數(shù)要求滿足θ=1。對(duì)容量參數(shù) α(固定 β=1.0)和 β(固定α=2.5)的影響分別進(jìn)行仿真計(jì)算。定義自愈后的網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模和初始網(wǎng)絡(luò)規(guī)模的比值為網(wǎng)絡(luò)恢復(fù)魯棒性，記為D，表達(dá)式為

式中:No為網(wǎng)絡(luò)最初的失效節(jié)點(diǎn)數(shù);Nr為網(wǎng)絡(luò)失效后進(jìn)行自愈的節(jié)點(diǎn)數(shù);Nf為無法自恢復(fù)的失效節(jié)點(diǎn)數(shù)目。

假設(shè)失效網(wǎng)絡(luò)為構(gòu)建的整個(gè)BA網(wǎng)絡(luò)，即初始時(shí)滿足No=N=S，運(yùn)用2.2節(jié)算法對(duì)失效網(wǎng)絡(luò)的自愈過程進(jìn)行仿真，每個(gè)值都是20個(gè)獨(dú)立網(wǎng)絡(luò)下計(jì)算所得平均值，其自愈能力和效果如圖4所示。

圖4(a1)和(b1)為BA網(wǎng)絡(luò)的自愈特性隨容量系數(shù)變化下的恢復(fù)魯棒性趨勢。從圖中可以看出，BA網(wǎng)絡(luò)擁有非常好自愈能力，其網(wǎng)絡(luò)恢復(fù)魯棒性指標(biāo)均超過0.95，且隨容量系數(shù)的增加而增加。仿真結(jié)果說明BA網(wǎng)絡(luò)在受到大振蕩導(dǎo)致網(wǎng)絡(luò)崩潰之后，大部分節(jié)點(diǎn)都可以進(jìn)行自愈而無需采取額外措施。其原因在于BA網(wǎng)絡(luò)度分布具有冪率特性:BA網(wǎng)絡(luò)中大部分的節(jié)點(diǎn)度值較小，只有極少數(shù)的節(jié)點(diǎn)具有極大的度值;而度值與負(fù)載的正相關(guān)性和負(fù)載重分配規(guī)則的馬太效應(yīng)使得度值較小的節(jié)點(diǎn)受到能量沖擊也較小，所以更容易滿足自愈條件;相反，度值越大的節(jié)點(diǎn)其受到的能量沖擊也越大，所以越難自愈，但由于大度值數(shù)目極少，所以BA網(wǎng)絡(luò)的大部分節(jié)點(diǎn)都可自愈，只有極少數(shù)節(jié)點(diǎn)形成了耦合結(jié)構(gòu)，需要采取額外手段。圖4(a2)和(b2)為自愈過程結(jié)束后，網(wǎng)絡(luò)中所有未能自愈節(jié)點(diǎn)度值的平均值，其中 Ψ為失效節(jié)點(diǎn)集合?？梢钥闯鯧值遠(yuǎn)大于網(wǎng)絡(luò)的平均度〈k〉≈4，說明不能自愈的節(jié)點(diǎn)主要為度值較大的節(jié)點(diǎn)。BA網(wǎng)絡(luò)的冪率特性使得網(wǎng)絡(luò)具有魯邦脆弱性，即由于節(jié)點(diǎn)度值的冪率分布特性，大部分節(jié)點(diǎn)的度值較小，只有極少部分的節(jié)點(diǎn)擁有極大的度值，使得BA網(wǎng)絡(luò)對(duì)隨機(jī)攻擊具有很好的魯棒性，但對(duì)蓄意攻擊卻極其脆弱。結(jié)合恢復(fù)魯棒性指標(biāo)，可以認(rèn)為BA網(wǎng)絡(luò)不僅具有魯棒脆弱性，其脆弱之后也具有極高的恢復(fù)魯棒性。

圖4 BA網(wǎng)絡(luò)自愈特性與容量參數(shù)Fig.4 BA network self-healing characteristics versus capacity parameters

圖5 美國航空網(wǎng)絡(luò)自愈特性與容量參數(shù)Fig.5 American aviation network self-healing characteristics versus capacity parameters

圖5 (a1)和(b1)為美國航空網(wǎng)絡(luò)的自愈特性隨容量系數(shù)變化下的恢復(fù)魯棒性趨勢。美國航空網(wǎng)絡(luò)具有332個(gè)節(jié)點(diǎn)，2 126條邊，即平均每個(gè)機(jī)場和 12個(gè)機(jī)場有飛行安排。池麗平［27］研究得出美國航空網(wǎng)與BA網(wǎng)絡(luò)具有一定的差異性，但都具有冪率特性，且有較強(qiáng)的容錯(cuò)能力和較差的抗攻擊能力。仿真結(jié)果表明美國航空網(wǎng)絡(luò)也具有較強(qiáng)的恢復(fù)魯棒性，其中接近80%的機(jī)場能夠?qū)崿F(xiàn)功能自愈。圖5(a2)和(b2)說明大度值節(jié)點(diǎn)更加容易形成耦合結(jié)構(gòu)，不易進(jìn)行自恢復(fù)，從側(cè)面也反映了度值較大的節(jié)點(diǎn)的脆弱性，不僅受到攻擊時(shí)容易引起網(wǎng)絡(luò)的級(jí)聯(lián)崩潰，而且癱瘓后也難以自愈。所以重點(diǎn)保護(hù)度值較大節(jié)點(diǎn)是提高網(wǎng)絡(luò)安全的一種簡單但有效的方法。雖然整個(gè)網(wǎng)絡(luò)中有近八成的節(jié)點(diǎn)能夠在能量沖擊后通過自愈而恢復(fù)功能，但如果將無法自愈的節(jié)點(diǎn)從網(wǎng)絡(luò)中移除，網(wǎng)絡(luò)仍然會(huì)分崩離析，這也間接說明耦合結(jié)構(gòu)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)整體上具有較大的影響。

3.2 網(wǎng)絡(luò)增長機(jī)制下自愈特性分析

網(wǎng)絡(luò)的增長必將使得原網(wǎng)絡(luò)的結(jié)構(gòu)發(fā)生變化，而網(wǎng)絡(luò)中一個(gè)小的缺陷很容易被網(wǎng)絡(luò)錯(cuò)綜復(fù)雜的耦合關(guān)系所放大，從而造成嚴(yán)重的損失。以美國航空網(wǎng)絡(luò)為基礎(chǔ)，對(duì)其生長條件下的自愈特性進(jìn)行研究。通常作為分流機(jī)場而建設(shè)的機(jī)場類別需求較少，假設(shè)只對(duì)前1%的大機(jī)場(度值大于100的節(jié)點(diǎn))進(jìn)行分流機(jī)場增建，建設(shè)數(shù)量分別為1、2和3所機(jī)場;根據(jù)相應(yīng)的建設(shè)需求，續(xù)建機(jī)場的增建數(shù)量分別選擇10、20和30;新興機(jī)場選擇5、10和15來進(jìn)行仿真分析。根據(jù)2.2節(jié)的增長規(guī)則對(duì)網(wǎng)絡(luò)進(jìn)行構(gòu)建。由于網(wǎng)絡(luò)增長規(guī)模的不同，以恢復(fù)魯棒性作為評(píng)估指標(biāo)不能準(zhǔn)確地說明網(wǎng)絡(luò)自愈能力的變化，因此選擇網(wǎng)絡(luò)中未自愈節(jié)點(diǎn)的規(guī)模作為評(píng)估標(biāo)準(zhǔn)。為了得到隨機(jī)連接的統(tǒng)計(jì)特性，每個(gè)數(shù)據(jù)都是計(jì)算20個(gè)獨(dú)立網(wǎng)絡(luò)后所得平均值，雖存在誤差，但能在一定程度上反映相關(guān)趨勢。仿真結(jié)果如圖6所示。

圖6(a)反映的是增加不同數(shù)量的分流機(jī)場后，新網(wǎng)絡(luò)的自愈能力。Nf越大說明網(wǎng)絡(luò)的自愈能力越差。從圖中曲線可以看出，分流機(jī)場的增加會(huì)降低整個(gè)航空網(wǎng)絡(luò)的自愈能力，且增加的分流機(jī)場越多，航空網(wǎng)絡(luò)的自愈能力越差。圖6(b)反映的是增加不同數(shù)量的續(xù)建機(jī)場對(duì)網(wǎng)絡(luò)自愈能力的影響。續(xù)建機(jī)場對(duì)網(wǎng)絡(luò)的自愈能力帶來的負(fù)擔(dān)超過了分流機(jī)場，這是由于續(xù)建機(jī)場的續(xù)建規(guī)模遠(yuǎn)大于分流機(jī)場所導(dǎo)致的，相同擴(kuò)建數(shù)量的前提下分流機(jī)場的影響力更大。這兩類新增機(jī)場都具有較大的連接需求，新增航線使拓?fù)浣Y(jié)構(gòu)很容易形成新的耦合結(jié)構(gòu)，使得整個(gè)航空網(wǎng)絡(luò)的恢復(fù)魯棒性降低。圖6(c)反映的是增加不同數(shù)量的新興機(jī)場對(duì)網(wǎng)絡(luò)自愈能力的影響。圖中曲線很明顯地反映出新興機(jī)場的增建對(duì)網(wǎng)絡(luò)的自愈能力影響微弱，并沒有對(duì)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的自愈帶來太大影響。新增建的機(jī)場自身也具有良好的自愈能力，但對(duì)原本就未能自愈的節(jié)點(diǎn)也未能減緩其壓力?？傮w而言，在現(xiàn)有網(wǎng)絡(luò)的基礎(chǔ)上，增加新興節(jié)點(diǎn)以完善航空網(wǎng)絡(luò)不會(huì)存在降低網(wǎng)絡(luò)自愈能力的風(fēng)險(xiǎn)。但要構(gòu)建機(jī)場群，在各機(jī)場之間開通更多的航線，增加網(wǎng)絡(luò)密度，將會(huì)削弱網(wǎng)絡(luò)整體的自恢復(fù)能力。

圖6 美國航空網(wǎng)絡(luò)不同增長機(jī)制下自愈特性與容量參數(shù)的關(guān)系Fig.6 Relationship between self-healing characteristics and capacity parameters under different growth rules of American aviation network

4 結(jié)論

本文運(yùn)用復(fù)雜網(wǎng)絡(luò)理論對(duì)美國航空網(wǎng)絡(luò)不同增長機(jī)制下的恢復(fù)魯棒性進(jìn)行了研究，得出以下結(jié)論:

1)美國航空網(wǎng)絡(luò)中大部分的機(jī)場在受到級(jí)聯(lián)失效影響下具有功能自愈能力。

2)少數(shù)大負(fù)載機(jī)場，由于其易形成耦合結(jié)構(gòu)而無法實(shí)現(xiàn)自愈，對(duì)網(wǎng)絡(luò)整體結(jié)構(gòu)的穩(wěn)定性影響非常大。

3)為完善航空網(wǎng)絡(luò)而建立的機(jī)場群，由于其較大的連接需求，加大了網(wǎng)絡(luò)區(qū)域密度，復(fù)雜了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，降低了網(wǎng)絡(luò)的自恢復(fù)能力。

4)新興機(jī)場這一類小型機(jī)場的增加不會(huì)影響網(wǎng)絡(luò)整體的自愈能力。

技術(shù)的進(jìn)步和經(jīng)濟(jì)的增長使得航空網(wǎng)絡(luò)的發(fā)展步入正軌，其重要地位決定該方向的研究仍會(huì)是一個(gè)長期且艱巨的過程。本文簡化了航空網(wǎng)絡(luò)的許多特性，用有向加權(quán)網(wǎng)絡(luò)能夠更準(zhǔn)確地描繪航空網(wǎng)絡(luò)的特性;結(jié)合鐵路網(wǎng)等的相依網(wǎng)絡(luò)模型則能更精細(xì)地刻畫現(xiàn)實(shí)中的客流動(dòng)向，進(jìn)而更加準(zhǔn)確地反映出機(jī)場的建設(shè)需求及影響;在后續(xù)的研究中將逐步完善模型，以便更貼近客觀現(xiàn)實(shí)?？傮w而言，本文的研究結(jié)果可以為中國航空發(fā)展規(guī)劃提供一定的理論支持。

［1］莫輝輝，王姣娥.復(fù)雜交通網(wǎng)絡(luò):結(jié)構(gòu)、過程與機(jī)理［M］.北京:經(jīng)濟(jì)管理出版社，2012:121-151.MO H H，WANG J E.Complex transport network:Structure，process＆ mechanism［M］.Beijing:Economy and Management Press，2012:121-151(in Chinese).

［2］ NEWMAN M E J.Networks:An introduction［M］.Oxford:Oxford University Press，2010:741-743.

［3］ CHEN G R，WANG X F，LI X.Introduction to complex networks:Models，structures and dynamics［M］.Beijing:Higher Education Press，2012:3-13.

［4］鄭嘯，陳建平，邵佳麗，等.基于復(fù)雜網(wǎng)絡(luò)理論的北京公交網(wǎng)絡(luò)拓?fù)湫再|(zhì)分析［J］.物理學(xué)報(bào)，2012，61(19):95-105.ZHENG X，CHEN J P，SHAO J L，et al.Analysis on topological properties of Beijing urban public transit based on complex network theory［J］.Acta Physica Sinica，2012，61(19):95-105(in Chinese).

［5］ REN T，WANG Y F，LIU M M，et al.Analysis of robustness of urban bus network［J］.Chinese Physics B，2016，25(2):1-12.

［6］蔡君，余順爭.一種有效提高無標(biāo)度網(wǎng)絡(luò)負(fù)載容量的管理策略［J］.物理學(xué)報(bào)，2013，62(5):058901.CAI J，YU S Z.An efficient management strategy for enhancing traffic capacity in scale-free networks［J］.Acta Physica Sinica，2013，62(5):058901(in Chinese).

［7］ LIU H R，DONG M R，YIN R R，et al.Cascading failure in the wireless sensor scale-free networks［J］.Chinese Physics B，2015，24(5):293-299.

［8］ WANG X，WANG Y，ZHU L，et al.A novel approach to characterize information radiation in complex networks［J］.Physica A Statistical Mechanics ＆ Its Applications，2016，452(1-3):95-105.

［9］ BARRAT A，BARTHELEMY M，VESPIGNANI A，et al.The architecture of complex weighted networks:Measurements and models［J］.Proceedings of the National Academy of Sciences of the United States of America，2003，101(11):3747.

［10］ COLIZZA V，BARRAT A，BARTHELEMY M，et al.Prediction and predictability of global epidemics:The role of the airline transportation network［J］.Proceedings of the National Academy of Sciences of the United States of America，2015，103(7):2015-2020.

［11］ AMARA L A N，SCALA A，BARTHELEMY M，et al.Classes of small-world networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2000，97(21):11149-11152.

［12］ GUIMERA R，MOSSA S，TURTSCHI A，et al.Structure and efficiency of the world-wide airport network［J］.Polymers ＆ Polymer Composites，2003，11(4):7794-7799.

［13］ GAUTREAU A，BARRAT A，BARTHELEMY M，et al.Microdynamics in stationary complex networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2009，106(22):8847-8852.

［14］ CHI L P，WANG R，SU H，et al.Structural properties of US flight network［J］.Chinese Physics Letters，2003，20(8):1393-1396.

［15］ LI W，CAI X.Statistical analysis of airport network of China［J］.Physical Review E Statistical Nonlinear ＆ Soft Matter Physics，2004，69(2):046106.

［16］ CAI K Q，ZHANG J，DU W B，et al.Analysis of the Chinese air route network as a complex network［J］.Chinese Physics B，2012，21(2):596-602.

［17］ NAKASHIMA S，MITANI T，SENZAKI J，et al.Characterization and modeling of weighted networks［J］.Physica A Statistical Mechanics ＆ Its Applications，2005，346(1-2):34-43.

［18］ BARRAT A，BARTHELEMY M，VESPIGNANI A.The effects of spatial constraints on the evolution of weighted complex networks［J］.Journal of Statistical Mechanics:Theory and Experiment，2005(5):799-803.

［19］ CHEN S M，XUI Y F，NIE S.Robustness of network controllability in cascading failure［J］.Physica A Statistical Mechanics ＆Its Applications，2017，471(1):536-539.

［20］ WANG J W.Robustness of complex networks with the local protection strategy against cascading failure［J］.Safety Science，2013，53:219-225.

［21］ MAJDANDZIC A，PODOBNIK B，BULDYREV S V，et al.Spontaneous recovery in dynamical networks［J］.Nature Physics，2014，10(1):34-38.

［22］劉宏鯤，周濤.中國城市航空網(wǎng)絡(luò)的實(shí)證研究與分析［J］.物理學(xué)報(bào)，2007，56(l):106-112.LIU H K，ZHOU T.Empirical study of Chinese city airline network［J］.Acta Physica Sinica，2007，56(l):106-112(in Chinese).

［23］ MOTTER A E，LAI Y C.Cascade-based attacks on complex networks［J］.Physical Review E，2002，66(6):065102.

［24］ WANG J W，RONG L L，ZHANG L，et al.Attack vulnerability of scale-free networks due to cascading failures［J］.Physica A Statistical Mechanics ＆ Its Applications，2008，387(26):6671-6678.

［25］ YANG R，WANG W X，LAI Y C，et al.Optimal weighting scheme for suppressing cascades and traffic congestion in complex networks［J］.Physical Review E Statistical Nonlinear ＆Soft Matter Physics，2009，79(2Pt2):026112.

［26］ BARABASI A L，ALBERT R.Emergence of scaling in random networks［J］.Science，1999，286(5439):509-512.

［27］池麗平.遭襲復(fù)雜網(wǎng)絡(luò)的修復(fù)策略與關(guān)聯(lián)特性研究［D］.武漢:華中師范大學(xué)，2006:58-69.CHI L P.On the repair strategy and correlation properties of complex networks under attacks［D］.Wuhan:Central China Normal University，2006:58-69(in Chinese).