基于功能脆弱性的空中交通相依網絡流量分配

王興隆，齊雁楠，潘維煌

中國民航大學 空中交通管理學院 天津 300300

安全有序的空中交通系統(tǒng)，依靠機場、航路和管制扇區(qū)網絡協(xié)同運行。在系統(tǒng)內部或外部受到擾動時會引發(fā)脆弱性，造成空中交通延誤，嚴重時還帶來系統(tǒng)安全風險。采用相依網絡理論，識別脆弱源并實施合理航班流量分配，是解決上述問題的一種有效方法。

相依網絡是一種多層復雜網絡，適用于刻畫各層網絡間的影響關系與耦合方式[1]。相依網絡脆弱性是當下的研究熱點，在理論方面，文獻[2]分析在不同空間嵌入與攻擊模式下，網絡性能的變化，并提出了恢復策略；文獻[3]則深入研究了相依網絡的級聯(lián)失效，指出在受到攻擊時容易破壞網絡結構和功能的完整性，引發(fā)網絡脆弱性。相依網絡脆弱性在電力、交通、航空等領域已有初步應用；文獻[4]分析了電力、通信網絡的脆弱性，研究了網絡級聯(lián)失效的閾值，并探索影響網絡脆弱性的關鍵節(jié)點；文獻[5]采用啟發(fā)式算法分析道路網絡交通流模式，分析交通流傳播過程，辨識不同時刻網絡脆弱性；文獻[6-7]建立了空中交通相依網絡模型；文獻[8-9]研究了網絡抗毀性和脆弱性。在流量分配方面，文獻[10-13]研究了軌道交通網絡的客流、列車流的優(yōu)化；文獻[14-16]研究電力網絡的電流控制，實現(xiàn)整個網絡輸送性能最優(yōu)化。在航空領域，空中交通流量管理是一個經典問題[17-19]，模型與算法都有較多研究。近期，文獻[20]提出一種基于航班起飛與計劃到達時間差最小的優(yōu)化策略，綜合考慮航路、容量、航空器速度等多約束條件，建立了航班時刻分配策略；文獻[21] 針對空域擁堵的問題，采用多目標規(guī)劃方法，實施航班地面等待、盤旋、改航等策略；文獻[22] 提出一種控制航班延誤分布、減少聯(lián)程航班延誤的方法，采用混合整數(shù)規(guī)劃優(yōu)化模型解決航路上交通需求與容量平衡問題，實現(xiàn)縮短起飛間隔、減少延誤的目標。

但空中交通脆弱性研究只是剛剛開始，缺乏應用場景，空中交通流量分配是個網絡化、系統(tǒng)化問題，尚未發(fā)現(xiàn)以全局視角、不同網絡層次協(xié)同的方式，采用相依網絡方法進行研究。網絡脆弱性一般分為結構脆弱性和功能脆弱性，本文主要研究空中交通網絡功能脆弱性，在研究脆弱性發(fā)生規(guī)律基礎上，以機場、航路和管制扇區(qū)網絡的流量熵值之和最小為目標，對各層網絡實施流量分配，降低相依網絡脆弱性，使得空中交通流趨于有序。

1 空中交通相依網絡功能脆弱性識別

以空中交通組織為依據(jù)，建立空中交通相依網絡G0，由機場網絡G1、航路網絡G2、管制扇區(qū)網絡G3組成。G1以機場為點，機場間的備降關系為邊；G2以航路點為點，航路的航段為邊；G3以管制扇區(qū)為點，扇區(qū)間航班交接關系為邊。G1與G2的連邊表示飛機的進離場；G1與G3的連邊表示扇區(qū)對機場飛機起降的管制；G2與G3的連邊表示扇區(qū)對飛機航路飛行的管制。

1.1 網絡功能脆弱性指標

空中交通相依網絡節(jié)點在受到擾動而失效后，一方面會造成節(jié)點與邊的連接失效而破壞網絡結構，另一方面也會引起網絡功能的混亂，觸發(fā)網絡功能脆弱性。本文采用文獻[6]中的方法，建立網絡脆弱性的基本特征指標，如表1所示。

表1 網絡功能脆弱性指標

對于不同層網絡流量熵計算中，當網絡中所有節(jié)點的流量不均衡時，網絡流量熵最大；所有節(jié)點的流量均衡時，網絡流量熵最小。為了分析不同層網絡的流量熵，進行歸一化處理：

(1)

本文通過分析上述功能脆弱性指標變化率，識別網絡功能脆弱性表現(xiàn)規(guī)律。指標變化率計算為[23]

(2)

式中：Δφ為指標變化率；φ(q)為q比例節(jié)點失效時功能脆弱性指標值；φ(q-1)為q-1比例節(jié)點失效時功能脆弱性指標值。

1.2 功能脆弱性識別方法

在分析空中交通相依網絡功能脆弱性過程中，需要考慮不同層網絡間相互影響關系，采用擾動節(jié)點的方法使其失效。擾動方式分為隨機擾動和蓄意擾動，隨機擾動是從相依網絡中等概率刪除節(jié)點，蓄意擾動則是按節(jié)點的空中交通流量大小將網絡節(jié)點排序(流量相同時等概率)刪除節(jié)點。

為了展示節(jié)點失效如何影響網絡脆弱性，依據(jù)空中交通管理規(guī)則，建立節(jié)點失效對功能脆弱性的影響規(guī)則。

1) 層網絡內的交通流轉移規(guī)則

① G1層網絡節(jié)點失效，其失效節(jié)點的交通流將被轉移至層網絡內相鄰機場節(jié)點。

② G2節(jié)層網絡點失效，其失效節(jié)點交通流被轉移至相鄰航路點。交通流轉移的過程中，受到相連的G3層網絡節(jié)點容量約束，若轉移量超過G3層網絡節(jié)點的容量，則以G3層網絡節(jié)點最大裕度作為交通流轉移最大量。

③ G3層網絡節(jié)點失效，其失效節(jié)點交通流被轉移至相鄰管制扇區(qū)節(jié)點。交通流轉移的過程中，交通流轉移受相連的G2層網絡節(jié)點的容量約束，若轉移量超過航路節(jié)點的容量，則以航路節(jié)點裕度作為交通流轉移最大量。

2) 層網絡間的交通流轉移規(guī)則

① G1層網絡節(jié)點失效，相連的G3層網絡節(jié)點和G2層網絡節(jié)點不發(fā)生交通流轉移。

② G2層網絡節(jié)點失效，相連的G1、G3層網絡節(jié)點發(fā)生交通流轉移。

③ G3層網絡節(jié)點失效，相連的G1、G2層網絡節(jié)點發(fā)生交通流轉移。

節(jié)點裕度為節(jié)點容量與流量的差值。在不同比例節(jié)點失效情況下，分別采用隨機與蓄意2種擾動方式，計算網絡功能脆弱性指標，分析指標變化率。

2 網絡流量協(xié)同分配

空中交通網絡流就是航空器由機場起降、空中沿航路飛行形成的航班流量。當網絡形成持續(xù)大量的航班流量，尤其是流量達到或接近容量時，擾動網絡會造成大范圍航班延誤，網絡功能脆弱性增大。據(jù)此，參照實際運行，對機場、航路、管制扇區(qū)網絡的航班流量進行合理、協(xié)同分配，改善空中交通相依網絡功能脆弱性更具實際意義。在流量熵歸一化的前提下，協(xié)同流量分配的目標是各層網絡流量熵值的和最小，網絡內部交通流更有序。

2.1 目標函數(shù)

空中交通相依網絡流量分配的目標函數(shù)為

(3)

結合實際空中交通流量管理工作，在流量分配過程中對各層網絡的流量進行約束:

0.8tai≤t′ai≤Caia∈1,2,3

(4)

式中：t′ai為Ga層網絡中節(jié)點i在流量分配過程中的流量；tai為Ga層網絡中節(jié)點i的流量；Cai為Ga層網絡中節(jié)點i在流量分配過程中的容量。

在約束條件下，使空中交通相依網絡的3層網絡的流量匹配，同時流量熵值總和最小，此時網絡內部交通流較為有序，具有較強的抗干擾能力，能改進空中交通相依網絡脆弱性。

2.2 求解算法

在網絡節(jié)點數(shù)量較多的情況下，為了產生最優(yōu)解，計算量很大。遺傳算法是一種成熟且通用性強的優(yōu)化算法，約束條件少，具備并行性和全局搜索能力，適合解決組合優(yōu)化問題。流量分配，是在網絡最小總熵值的目標下，根據(jù)約束條件進行各個節(jié)點流量匹配，是典型的組合優(yōu)化問題。本文將網絡總流量熵作為適應度，對遺傳算法進行改進，實現(xiàn)網絡流量分配優(yōu)化。

1) 編碼與初始種群生成

采用明碼編碼方式，將需要分配流量的層網絡節(jié)點形成N元數(shù)組作為染色體λ=(λi)N，第i個節(jié)點分配的流量λi代表染色體基因。其他層根據(jù)流量分配策略分別形成染色體。

以原始流量串作為種子染色體，根據(jù)2.1節(jié)的流量約束條件，對每個流量值進行隨機變化[80%，120%]，生成初始種群P。

2) 遺傳算子

① 選擇。對初始種群P進行隨機排序，為了保留精英且擴大搜索范圍，將隨機排序后的種群進行分組(m個為一組)，留下m條中的最優(yōu)解，其他進行交叉、變異操作。

② 交叉。采用段交叉方式，隨機選擇(m-1個中)2個個體進行配對，隨機設置交叉段，依照概率pc交換2個個體部分染色體，形成新個體。

③ 變異。采用基因段變異操作，隨機選擇(m-1個中)個體按照變異概率pm隨機改變某段基因位的編碼。為了在迭代前期擴大搜索范圍，后期提高精英解保留概率，pm根據(jù)迭代次數(shù)而改變，前期大后期小，其表達式為

pm=(L-Iter)/L

(5)

式中：L為總迭代次數(shù)；Iter為當前迭代次數(shù)。

基于上述遺傳算法，通過改變層網絡節(jié)點流量進行網絡流量協(xié)同分配，具體策略步驟如表2所示。

表2 網絡流量協(xié)同分配策略

3 算例分析

采用中國北京、天津、河北、山西、內蒙古區(qū)域的民航數(shù)據(jù)，構建中國華北空中交通相依網絡，其中，機場網絡G1共計28個機場，79對備降關系；航路網絡G2共計41個航路點，90條航段；管制扇區(qū)網絡G3共計20個扇區(qū)，43條扇區(qū)移交關系，見圖1。結合空中交通相依網絡模型、節(jié)點擾動方式和失效規(guī)則，計算節(jié)點失效后網絡脆弱性指標，分析指標變化率識別脆弱性表現(xiàn)規(guī)律。

3.1 功能脆弱性識別分析

1) 網絡流量熵變化率分析

采用式(1)計算網絡流量熵，利用式(2)分析指標變化率和失效閾值，結果如圖2所示。圖中：R(Gb)=fM(Ga)表示對Ga網絡中的節(jié)點進行擾動， Gb網絡的指標變化。M代表擾動方式，M=R、 D分別表示隨機擾動和蓄意擾動。

圖1 華北空中交通層網絡

圖2(a)表明，G1層網絡節(jié)點隨機擾動，G1流量熵的變化率波動幅度較小，蓄意擾動G1層網絡節(jié)點，G1流量熵的值波動幅度也較小，其他情形也都未引發(fā)網絡的級聯(lián)失效。圖2(b)表明，G2層網絡節(jié)點蓄意擾動，G1的流量熵在擾動節(jié)點為30%熵值有明顯上升，幅度較大，此時G1內部因交通流轉移分配而混亂，網絡節(jié)點間的交通流相互影響，產生級聯(lián)失效現(xiàn)象，其他情形造成G1、G3的熵值的波動，但是并未造成熵值持續(xù)上升，所以沒有引發(fā)網絡的級聯(lián)失效。圖2(c)表明，G3層網絡節(jié)點隨機擾動，G1、G2、G3的流量熵都未出現(xiàn)熵增的持續(xù)上漲，未引發(fā)網絡的級聯(lián)失效；蓄意擾動G3的節(jié)點，10%的節(jié)點擾動比例造成G1的熵值開始大幅度波動，熵值變化很大，網絡的交通流轉移分配造成網絡內部混亂，引發(fā)G1的級聯(lián)失效，其他情形未引發(fā)網絡的級聯(lián)失效。

圖2 網絡流量熵變化率

2) 網絡交通流損失比變化率分析

利用式(2)對網絡最大連通度變化率進行分析，結果如圖3所示。圖3(a)表明，G1層網絡節(jié)點隨機或蓄意擾動，G1沒有出現(xiàn)級聯(lián)失效現(xiàn)象。隨機擾動G2層網絡節(jié)點，擾動比例達5%時，G2的交通流損失開始快速增長，損失量迅速達200%，此時G2內部出現(xiàn)級聯(lián)失效現(xiàn)象，擾動比例達10%，G1的交通流損失達到1000%，網絡內出現(xiàn)了級聯(lián)失效現(xiàn)象。其他情形都未引發(fā)網絡的級聯(lián)失效。由圖3(b)可知，隨機擾動G3層網絡節(jié)點，G2網絡在節(jié)點擾動比例達10%時，網絡的交通流損失值快速達到247%，此時G2網絡產生級聯(lián)失效現(xiàn)象；G3層網絡節(jié)點的隨機擾動比例達15%時，G1的交通流損失值快速達到184%，此時G1產生級聯(lián)失效現(xiàn)象，其他情形都未引發(fā)網絡的級聯(lián)失效。

圖3 網絡交通流損失比變化率

綜上，網絡功能脆弱性表現(xiàn)規(guī)律為：擾動G1的交通流，3層網絡并未表現(xiàn)出相應的脆弱性；隨機擾動G2、G3的交通流，G1、G2都會表現(xiàn)出脆弱性，說明G1、G2更容易受到擾動的影響，但蓄意擾動下各網絡并未表現(xiàn)脆弱性。

3.2 層網絡流量分配

采用2.2節(jié)中的分配算法，產生初始種群個數(shù)100個，總迭代次數(shù)10 000次，為了防止快速收斂，取pc為固定值0.8，適應度變化曲線見圖4。

1) 對空中交通相依網絡的G1進行交通流量分配，在目標函數(shù)與約束條件下，機場網絡的各節(jié)點流量分配見表3，節(jié)點編號對應圖1(a)。

圖4 各層網絡流量優(yōu)化適應度

G1網絡交通流量分配中，網絡的流量熵值和由分配前的8.602 7降為分配后的8.283 3。結合空中交通系統(tǒng)運行實際，對G1的節(jié)點的流量在約束范圍內進行分配，使空中交通相依網絡的3個層網絡間的流量熵值總和最小，網絡趨于有序，在各種干擾下仍能擁有較好的抗擾動能力，機場網絡的流量分配能降低網絡的脆弱性。

2) 對空中交通相依網絡的G2進行交通流量分配，在目標函數(shù)與約束條件下，航路網絡的各節(jié)點流量分配見表4，節(jié)點編號對應圖1(b)。

表3 G1流量分配

表4 G2流量分配

G2網絡交通流量分配中，網絡的流量熵值和由分配前的8.602 7降為分配后的8.445 3。與機場網絡的流量協(xié)調分配比較分析，航路網絡的流量協(xié)調分配的總熵值比機場網絡總熵稍大，說明對航路進行流量協(xié)調分配對空中交通系統(tǒng)的交通流的有序性的改善不如機場網絡明顯。

3) 對空中交通相依網絡的G3進行交通流量分配，在目標函數(shù)與約束條件下，管制扇區(qū)網絡的各節(jié)點流量分配如表5所示，節(jié)點編號對應圖1(c)。

G3網絡交通流量分配中，網絡的流量熵值和由分配前的8.602 7降為分配后的8.552 3。空中交通相依網絡的管制扇區(qū)網絡的流量協(xié)調分配對空中交通相依網絡的流量有序性改善不如機場網絡、航路網絡的流量協(xié)調分配效果明顯。

由實驗結論可知，對3層網絡進行流量分配可降低空中交通相依網絡的流量熵，改善網絡的交通流的效率，降低網絡的脆弱性。其中，對機場網絡進行相應的流量協(xié)同分配的效果最明顯。

表5 G3流量分配

4 結 論

本文對空中交通相依網絡的脆弱性進行識別，分析影響網絡的脆弱性表現(xiàn)的敏感因素；結合運行實際建立空中交通3層網絡流量協(xié)同分配模型，采用改進的遺傳算法進行求解，通過優(yōu)化交通流來降低網絡功能脆弱性。

1) 擾動各層網絡節(jié)點，蓄意擾動G2、G3 對各網絡功能影響大，網絡在功能上趨向于混亂，呈現(xiàn)出網絡的脆弱性。

2) 擾動各層網絡的交通流，對G1、G2影響較大，說明與管制扇區(qū)相比，機場與航路更快達到實際運行的容量，在各種干擾下也較容易表現(xiàn)出網絡的功能脆弱性。

3) 通過對G1的各節(jié)點的交通流重新分配，對優(yōu)化網絡各節(jié)點的負載與容量間的制約關系，能夠有效降低網絡功能脆弱性。