基于復雜網(wǎng)絡的區(qū)域水上交通關鍵船舶識別方法*

文元橋 黃玉宇 周春輝1，，3 隋忠義 張 帆，4

（1. 武漢理工大學國家水運安全工程技術研究中心 武漢430063；2. 武漢理工大學航運學院 武漢430063；3. 武漢理工大學智能交通系統(tǒng)研究中心 武漢430063；4. 武漢理工大學內河航運技術湖北省重點實驗室 武漢430063）

0 引 言

船舶是水上交通的行為主體，對其行為的研究是識別水上交通風險、實施水上交通組織和管控的重要基礎性研究[1]。船舶行為一般是指船舶在駕駛人員的操縱下以航行和避讓為目的所采取的行為方式及其規(guī)律。從國內外的研究現(xiàn)狀來看，對船舶行為的研究主要包括以下幾個方面。

船舶行為特征方面，主要對船舶行為特征進行宏觀分析和微觀分析。宏觀行為分析研究船舶群體在全局尺度下所呈現(xiàn)的運動規(guī)律，通常通過軌跡聚類等方法分析大尺度下的船舶行為特征，胡智輝[2]通過對船舶軌跡進行聚類，得到了船舶的典型運動軌跡；潘家財?shù)萚3]、朱飛翔等[4]分別通過AIS 數(shù)據(jù)挖掘船舶軌跡特征并模擬船舶行為特征的空間分布。宏觀分析主要針對船舶的運動規(guī)律，難以描述船舶行為內在的演化機制，不能實時表達船舶行為的當前狀態(tài)。微觀分析描述的是船舶個體在局部尺度下呈現(xiàn)的船舶行為；王立林等[5]、K.Patroumpas 等[6]通過不同的方法對船舶行為進行識別，但是，其沒有考慮具體場景下的船舶行為、規(guī)則中的船舶行為以及多船行為；因此學者們進行進一步深入的研究。He 等[7]給出了國際海上避碰規(guī)則的量化解析模型，明確定義了船舶的各個會遇局面和會遇階段。Lei[8]提出了1 個名為MT-MAD 的框架并在該框架中定義了船舶活動空間、行為順序和行為特征，提出了基于船舶子軌跡評估的異常檢測算法。

在行為傳播研究方面，Damon[9]于2010年發(fā)表了關于行為傳播的研究成果，引起人們對行為傳播研究的關注。王新華等[10]基于SIRS信息傳播模型提出了1種礦工不安全行為傳播的SIRS模型，分析了不安全行為在礦工之間的傳播機制。劉映森[11]基于弓形蟲傳染病模型建立了車輛異常行為傳播模型，分析了傳播過程的主要影響因素如環(huán)境因素、擴散能力等。陶琳玲[12]通過對復雜網(wǎng)絡及個體行為決策等理論，構建了動態(tài)社會網(wǎng)絡中行為擴散機制演化模型，探討了不同影響因素對社會網(wǎng)絡中行為擴散的影響。

在關鍵點識別研究中，航空、道路等交通領域也有很多相關研究。劉飛等[13]通過建立飛行沖突行為分析網(wǎng)絡，采用復雜網(wǎng)絡節(jié)點中心性算法結合AHP 方法對網(wǎng)絡中節(jié)點的沖突等級進行評估，并有效地識別沖突關鍵點的位置；王斌等[14]將節(jié)點信任度引入PageRank 算法中，構建了1 種關鍵節(jié)點識別算法，有效的識別網(wǎng)絡的關鍵節(jié)點；袁銀國[15]通過構建區(qū)域網(wǎng)絡，使用基于OD 熵的區(qū)域重要性評估方法以及節(jié)點網(wǎng)絡中心性度量指標對每1 個區(qū)域進行重要性評估從而找出排名較高的區(qū)域路網(wǎng)節(jié)點；陳思等[16]結合PageRank 與Warshall 方法建立基于節(jié)點隨機失效下的各階段關鍵節(jié)點識別算法對運輸網(wǎng)絡的關鍵節(jié)點進行識別，得到了較好的識別效果。

目前船舶行為的研究大多只行有關行為特征行為規(guī)律方面的研究分析，如異常行為檢測、船舶典型行為如轉向等識別以及通過歷史軌跡進行預測以及航路推薦等；而在關鍵節(jié)點識別方面，只對航空網(wǎng)絡、道路交通網(wǎng)絡進行網(wǎng)絡關鍵節(jié)點識別的研究分析，對水域中的關鍵船舶識別的研究較少，且多數(shù)節(jié)點重要度評估指標為節(jié)點度中心性，對其他節(jié)點中心性指標評估方法研究較少。鑒于此，針對船舶航行過程中船舶行為所產(chǎn)生的行為交互影響現(xiàn)象，基于復雜網(wǎng)絡理論，將船舶作為節(jié)點映射到網(wǎng)絡中，構建面向船舶行為分析的復雜網(wǎng)絡模型（簡稱船舶行為分析網(wǎng)絡），將船舶間的交互關系作為節(jié)點連邊對節(jié)點間的連接關系，通過AHP（analytic hierarchy process）方法構造關鍵點綜合重要性評價指標，通過節(jié)點綜合重要度排序結果，識別船舶航行過程中對區(qū)域水上交通具有潛在威脅的關鍵船舶。

1 面向船舶行為分析的復雜網(wǎng)絡的構建

1.1 行為分析網(wǎng)絡構建

船舶行為在廣義上包括船舶的一般航行行為和船舶的避碰行為，在狹義上一般指船舶在駕駛人員的操縱下以航行和避讓為目的所采取的行為方式及其規(guī)律[17]。所謂船舶行為，指的是船舶在時空間活動過程描述，是指船舶受駕駛員潛在意圖的支配而表現(xiàn)出來的活動，是識別水上交通態(tài)勢[18]的關鍵。船舶行為包含著十分豐富的船舶航行狀態(tài)信息，在水上交通系統(tǒng)中扮演著“顯影劑”的角色，能夠從客觀上反映出當前水上交通的實時狀態(tài)[19]。在進行行為建模時，船舶行為通常被抽象為船舶在航行時所產(chǎn)生的時空軌跡，從中提取出行為的數(shù)據(jù)模型。從行為認知的角度，船舶行為可被視為人類對軌跡的1 種思維上的理解，這種思維除了會關注軌跡本身的運動特征之外，也會綜合考慮航行環(huán)境對船舶的影響，對行為進行認知。船舶在運動過程中與其行駛在其周圍的其他船舶容易產(chǎn)生行為交互影響，構成1 個動態(tài)復雜網(wǎng)絡；而如何通過這一動態(tài)復雜網(wǎng)絡描述船舶間行為交互影響對水上交通狀態(tài)造成的影響，是水上交通監(jiān)管需要重點關注的問題之一。

構建船舶行為分析網(wǎng)絡，是將船舶作為節(jié)點映射到網(wǎng)絡中，同時，船舶節(jié)點間的連邊關系不是單一的根據(jù)船舶間距離遠近或者是船舶間的運動關系判斷，而是結合船舶間的距離以及舶間形成的相互關系判斷船舶節(jié)點間是否存在連邊關系，船舶間的復雜度[20]作為連邊的權重。船舶在航行過程中需要1個隱私空間來保證自身船舶航行安全的需求，本文將其看作船舶的船舶領域[21]。多船船舶領域模型見圖1。

圖1 多船船舶領域模型Fig. 1 Multi-vessel ship domain model

船舶間距離的計算方法見式（1）。

式中:a ，b 為船舶領域的長半軸長與短半軸長。

由式（1）可知，當dij＜1時，船舶j 位于船舶i 的船舶領域內；當1 ＜dij＜ 2 時，船舶j 可能位于船舶i 的船舶領域內，也有可能位于船舶i 的船舶領域外，但此時船舶j 的位置距離船舶i 的船舶領域邊界很近；當dij＞ 2 時，船舶j 位于船舶i 的船舶領域外。當船舶間的位置距離越近，船舶間的行為交互影響的概率也就越高。

船舶運動趨勢示例見圖2，圖2（a）中的船舶形成匯聚的運動趨勢，圖2（b）中的船舶運動趨勢為相離的趨勢。判斷船舶運動趨勢的方法見式（2）。

其中:Dij與vij= vi- vj分別為船舶i 與船舶j 之間的相對距離矢量和相對速度矢量，通過‖ Dij‖的變化量來描述船舶間的運動趨勢。當dDijdt ＜0 時，2船間相對距離逐漸減小，形成匯聚趨勢；當dDijdt ＞0時，2 船相對距離增大，形成匯聚趨勢；當dDijdt = 0時，2 船間相對距離達到最小值即最小會遇距離（DCPA）。

圖2 船舶運動趨勢示例Fig. 2 Examples of ship movement trends

根據(jù)船舶間的距離及2 船間形成的運動趨勢，當2船為匯聚趨勢，且船舶間的距離dij＜ 2 時或者是2船呈相離趨勢而此時船舶間距離dij＜1時，船舶間存在連邊關系?；诖伴g存在行為交互連邊規(guī)則的判定，抽象出圖1 所示水域內船舶行為分析網(wǎng)絡模型，見圖3。

圖3 圖1場景對應的行為分析網(wǎng)絡Fig. 3 Behavior analysis network corresponding to the scene of Fig. 1

將行為分析網(wǎng)絡的鄰接矩陣表示為A ，aij表示船舶i 與船舶j 之間的連邊，當船舶i 與船舶j 之間的行為交互關系滿足上述連邊規(guī)則判定時，表示船舶i 與船舶j 之間存在連邊，有aij= 1 ，否則aij= 0 ，則圖3所示的網(wǎng)絡鄰接矩陣可表示見式（3）。

1.2 關鍵節(jié)點識別方法

網(wǎng)絡中的關鍵節(jié)點是指對網(wǎng)絡結構變化影響較大的節(jié)點，這些節(jié)點狀態(tài)發(fā)生變化的時候對網(wǎng)絡結構產(chǎn)生較大的影響[22]。同理，在船舶行為分析網(wǎng)絡中，當某一船舶的航行狀態(tài)發(fā)生改變對網(wǎng)絡演變產(chǎn)生較大影響時，該船舶即為船舶行為分析網(wǎng)絡中的關鍵節(jié)點。對于船舶交通監(jiān)管而言，合理調配這些關鍵節(jié)點的船舶能夠保證水上交通安全有序的進行，保證船舶航行的安全。接下來主要是介紹找出這些關鍵節(jié)點的參數(shù)指標與方法。

1.2.1 節(jié)點重要性指標

節(jié)點重要性本文選取節(jié)點的度中心性、介數(shù)中心性，以及緊密中心性3 個指標來研究船舶行為分析網(wǎng)絡中節(jié)點的直接影響力、間接影響力，以及節(jié)點銜接性，節(jié)點重要性指標定義如下。

1） 度中心性。度中心性DCi是衡量某一節(jié)點i在整個網(wǎng)絡中的地位。節(jié)點的度越大，說明該節(jié)點與其他節(jié)點的直接關聯(lián)能力越大。在船舶行為分析網(wǎng)絡中，節(jié)點度中心性就是某船舶在網(wǎng)絡中與其他的船舶存在較多的連邊，其行為改變對網(wǎng)絡所產(chǎn)生的影響越大。節(jié)點度為ki的度中心性計算方式見式（4）～式（5）。

式中:N 為網(wǎng)絡的節(jié)點總數(shù)；aij為船舶i 與船舶j之間的連邊。

2） 介數(shù)中心性。介數(shù)中心性BCi由網(wǎng)絡所有的最短路徑中經(jīng)過節(jié)點i 的最短路徑的數(shù)目來衡量節(jié)點在網(wǎng)絡中作為連接橋梁的中間銜接性的大小。在船舶行為分析網(wǎng)絡中，某船舶節(jié)點的介數(shù)中心性越大，表示越多的船舶會通過該船舶對其他船舶產(chǎn)生行為交互影響，該船舶在網(wǎng)絡中的中樞功能越明顯，對行為傳播的影響越大。節(jié)點度為ki的船舶的介數(shù)中心性計算方式為

式中:Lxy為船舶x 和船舶y 之間的最短路徑個數(shù)；Lxy( i )為船舶x 和船舶y 之間的最短路徑中經(jīng)過船舶i 的個數(shù)。

3） 緊密中心性。緊密中心性CCi根據(jù)節(jié)點與網(wǎng)絡中其他所有節(jié)點的最短距離，可以判斷該節(jié)點在網(wǎng)絡中的位置。行為分析網(wǎng)絡中船舶節(jié)點的緊密中心性越大，表明該船舶在行為分析網(wǎng)絡中所處的位置越靠近中心位置，對網(wǎng)絡結構演變的影響越大。節(jié)點度為ki的緊密中心性計算方式為

式中:lij為以節(jié)點i 為起點，節(jié)點j 為終點的最短路徑所含邊的數(shù)量；N 為網(wǎng)絡的節(jié)點總數(shù)。

1.2.2 基于AHP的節(jié)點綜合重要度評估

考慮不同指標從不同的角度體現(xiàn)節(jié)點在網(wǎng)絡中的重要程度，本文引入基于AHP方法構造節(jié)點綜合重要度評估模型進行節(jié)點綜合重要度評估。節(jié)點度中心性相對于其他2個指標能較好的反映節(jié)點在網(wǎng)絡中的重要程度，其次是介數(shù)中心性，最后是緊密中心性；結果見表1。

可得節(jié)點中心性指標的判斷矩陣M 。

表1 各指標比較結果Tab. 1 Comparison of indicators

計算矩陣M 的最大特征根λmax所相應的特征向量ω ，并進行歸一化處理，得該特征向量的權重向量W =[W1W2W3] =[0 .637 0.258 0.105] 。

為消除所選3個節(jié)點中心性指標之間的數(shù)量級差異，選取最大最小歸一化方法進行處理，如對度中心性處理見式（9）。

同理，對其余指標采取相同的方法進行歸一化處理，最終得到節(jié)點綜合重要度評價結果Pi為Pi= 0.637Dc′i+ 0.258Bc′i+ 0.105Cc′i。

2 關鍵點識別流程

基于上述對行為分析網(wǎng)絡的構建以及關鍵節(jié)點判斷指標與識別方法的介紹，可以了解到通過節(jié)點綜合重要度評價指標能夠識別出水域內的關鍵船舶，具體識別流程見圖4。

船舶行為分析網(wǎng)絡關鍵節(jié)點即水上交通關鍵船舶識別主要分為以下3個步驟。

1） 數(shù)據(jù)獲取。收集當前水域內所有船舶的航行數(shù)據(jù)，如船舶位置，航速，航向，等等。

圖4 關鍵節(jié)點識別流程圖Fig. 4 Flow chart of Key node identification

2） 行為分析網(wǎng)絡構建。根據(jù)獲取的船舶航行數(shù)據(jù)，結合船舶領域與船舶運動趨勢判定船舶行為交互關系，確定節(jié)點間的連接關系與連邊權重，構建行為分析網(wǎng)絡。

3） 關鍵節(jié)點識別。通過結合節(jié)點度中心性、介數(shù)中心性以及緊密中心性所構建的節(jié)點綜合重要度指標，對行為分析網(wǎng)絡中的節(jié)點進行重要度評估，根據(jù)評估結果確定網(wǎng)絡關鍵節(jié)點，進而識別水上交通關鍵船舶。

3 實驗分析

針對上文介紹的關鍵節(jié)點識別方法，設置了仿真實驗與實證分析，以驗證上述方法是否能夠有效識別區(qū)域水上交通關鍵船舶。

3.1 仿真實驗

假設某一水域范圍內分布著不同數(shù)目船舶（船舶數(shù)目設置為10，20，30，50），船舶位置分布服從正態(tài)分布，分析觀察水域中不同船舶數(shù)目情況下相應船舶行為分析網(wǎng)絡中關鍵節(jié)點的分布情況，分析網(wǎng)絡節(jié)點數(shù)目對網(wǎng)絡關鍵節(jié)點識別結果的影響。網(wǎng)絡關鍵節(jié)點識別結果見圖5,其中，黑色圓點為船舶節(jié)點，帶有白色五角星圖案為關鍵節(jié)點。

由圖5可見，當網(wǎng)絡節(jié)點數(shù)較小時，網(wǎng)絡中節(jié)點的連接較為分散；隨著節(jié)點數(shù)目的增加，節(jié)點之間的相互連接增多，逐漸形成復雜的網(wǎng)絡，但網(wǎng)絡也沒有形成完全連接。同時可以發(fā)現(xiàn)，不論網(wǎng)絡節(jié)點數(shù)目大小，網(wǎng)絡中關鍵節(jié)點的位置基本上保持在網(wǎng)絡的中心位置，網(wǎng)絡中節(jié)點連接越復雜的位置，關鍵節(jié)點越多。當船舶數(shù)量發(fā)生變化時，行為分析網(wǎng)絡的關鍵節(jié)點位置分布會發(fā)生變化；在船舶運動過程中，隨著船舶位置的變化，船舶間的行為交互關系網(wǎng)絡的關鍵節(jié)點也在不斷變化，使得網(wǎng)絡結構也隨之發(fā)生變化，網(wǎng)絡的關鍵節(jié)點分布也會發(fā)生變化。

圖5 不同節(jié)點數(shù)的網(wǎng)絡關鍵節(jié)點識別Fig. 5 Identification of network key nodes with different number of nodes

3.2 實證分析

為驗證關鍵節(jié)點識別方法是否適用于實際場景，截取鎮(zhèn)江大港水域中某一時間段內船舶航行過程來進行實驗分析，實驗開始時刻船舶航行狀態(tài)圖及所構成的行為分析網(wǎng)絡見圖6。結合圖6（a），可知使用船舶mmsi作為節(jié)點標簽時，容易出現(xiàn)行為分析網(wǎng)絡中節(jié)點標簽重疊的情況，因此對所采用的實驗數(shù)據(jù)中出現(xiàn)的船舶進行重新編號，見圖6（b）。

圖6 船舶航行狀態(tài)圖與船舶行為分析網(wǎng)絡圖Fig. 6 Ship navigation status diagram and ship behavior analysis network diagram

表2 與表3 分別給出了船舶運動過程開始時刻與結束時刻下水域中所形成的行為分析網(wǎng)絡中所有節(jié)點的度中心性、介數(shù)中心性和緊密中心性以及節(jié)點綜合評價指標的評價結果。對比2個節(jié)點綜合評價結果表，可以看出節(jié)點度中心性相較其他2 個節(jié)點中心性指標的評價結果更加穩(wěn)定，能夠反映出該指標在船舶行為分析網(wǎng)絡中具有較好的評估效果。但節(jié)點度中心性指標主要考慮節(jié)點間的連接關系，同時也缺乏了對節(jié)點間連接的緊密程度以及節(jié)點在網(wǎng)絡中的位置方面的考慮，因此還需要根據(jù)節(jié)點的綜合評價指標對關鍵節(jié)點進行節(jié)點綜合重要度的最終判斷。

表2 開始時刻的節(jié)點綜合重要度評價Tab. 2 Evaluation of the comprehensive importance of nodes at the star time

行為分析網(wǎng)絡的關鍵船舶識別結果見圖7，其中黑色圓點為船舶節(jié)點，黑色五角星節(jié)點為關鍵船舶。 從圖7（a）中可以看出，節(jié)點7（mmsi 為413778336）的綜合評價是所有節(jié)點評估結果中最高的，可以看到其周圍船舶數(shù)量較多，所處的位置交通狀態(tài)最為復雜，需要重點關注。同樣，從圖7（b）中可以看出節(jié)點綜合評價指標最高的船舶節(jié)點28（mmsi為413882404）周圍還分布著2個距其較近的網(wǎng)絡關鍵節(jié)點，且該節(jié)點周圍船舶較為聚集，對整個船舶行為分析網(wǎng)絡中船舶的航行安全威脅較高。

本文選擇將排名前5位的船舶節(jié)點識別為行為分析網(wǎng)絡的關鍵節(jié)點。這些關鍵節(jié)點位置的船舶對水域中船舶航行安全的威脅程度較高。此外，可以將這些關鍵船舶作為重點監(jiān)管對象，能夠保證水上交通安全有序的進行。這些關鍵船舶往往位于船舶行為分析網(wǎng)絡的核心部位，同時與其周圍多艘船舶之間存在關聯(lián)。所以交通監(jiān)管人員需要對該位置的船舶進行重點關注。通過船舶行為分析網(wǎng)絡的構建，避免了對水域內所有船舶進行重復判斷，降低了交通監(jiān)管人員或者船舶駕駛員進行水域內交通安全態(tài)勢判斷的復雜程度。特別是對關鍵船舶節(jié)點的識別，能夠提供更精確的交通安全態(tài)勢信息，協(xié)助監(jiān)管人員和駕駛員針對不同的情況作出合理的行為響應。

表3 結束時刻的節(jié)點綜合重要度評價Tab. 3 Evaluation of comprehensive importance of nodes at the end time

圖7 不同時刻關鍵節(jié)點標識Fig. 7 Key node identification at different moments

將開始時刻下節(jié)點度中心性節(jié)點重要性評價結果與節(jié)點綜合重要度評價結果進行對比分析，對比結果見表4?？梢钥闯觯?種方法的排序結果基本一致，僅個別節(jié)點的排序結果出現(xiàn)差異。根據(jù)上文以排序結果前5 的節(jié)點作為關鍵節(jié)點的假設，將排序結果每5個節(jié)點為1組進行對比，可以看出其中重要度等級排序結果出現(xiàn)較大差異的節(jié)點分別為6，11，12，31，產(chǎn)生該差異的原因主要是由于本文所采用的研究方法不僅考慮了節(jié)點的節(jié)點度，同時也考慮了節(jié)點在網(wǎng)絡中所處的位置與其與網(wǎng)絡中各節(jié)點間的連接關系，較為全面地考慮了節(jié)點在網(wǎng)絡中的重要性。除去排序結果差異較大的節(jié)點，2種方法的分析結果中排序結果相同的節(jié)點數(shù)占節(jié)點總數(shù)的比例達到77.8%。對比出現(xiàn)差異的節(jié)點可以發(fā)現(xiàn)，通過節(jié)點綜合重要度來識別關鍵船舶節(jié)點，比單純使用節(jié)點度死別的方法考慮因素更多，更為全面的考慮了周圍航行環(huán)境在船舶航行過程中的不同影響。例如，對比節(jié)點6與節(jié)點11，雖然二者節(jié)點度中心性指標相同，但由于節(jié)點6 在網(wǎng)絡中所處的位置是網(wǎng)絡中2 個社團（網(wǎng)絡中節(jié)點之間相互連接較為緊密的小團體）中間，即處于連接2個社團的位置，故節(jié)點6在整個船舶行為分析網(wǎng)絡中應承擔著更為重要的網(wǎng)絡連接功能。因此，節(jié)點6 的重要度等級應高于節(jié)點11的重要度等級。

而對比相同排序級別的節(jié)點，本文所采用的方法得出的結果更為細致，即根據(jù)節(jié)點綜合重要度，可以在同一重要度等級中識別出更為關鍵的節(jié)點。綜上，本文所采用方法得出的結果，相對而言能較全面地說明節(jié)點在行為分析網(wǎng)絡中的重要性，且所得數(shù)據(jù)更為精確。

4 結束語

本文對區(qū)域水上交通關鍵船舶識別進行了研究，基于復雜網(wǎng)絡分析和AHP方法分別建立了船舶行為分析網(wǎng)絡和節(jié)點綜合重要度評估方法，對網(wǎng)絡中的節(jié)點進行節(jié)點重要度評估，找出網(wǎng)絡中的關鍵節(jié)點。經(jīng)過仿真實驗與實證分析證明，該方法能夠將綜合節(jié)點性質指標識別網(wǎng)絡的關鍵節(jié)點，并能夠對船舶行為分析網(wǎng)絡的關鍵船舶進行識別。同時對比分析結果驗證，與單一節(jié)點度指標進行節(jié)點重要度評價相比，節(jié)點綜合重要度綜合考慮節(jié)點的各項指標，其評價結果更為全面。但研究并未考慮水域中其他因素對網(wǎng)絡的影響，在后續(xù)的研究中可以考慮水域中其他因素對關鍵船舶識別的影響。

表4 開始時刻2 種分析結果比較Tab. 4 Comparison between two analytical results at the start time