一種高效的船舶動態數據索引方法

張遠強, 史國友

(1. 大連海事大學 航海學院， 遼寧 大連 116026； 2. 寧波大學 海運學院， 浙江 寧波 315211)

中國沿海和內河4級以上河段的船舶自動識別系統(Automatic Identification System, AIS)網絡已實現覆蓋[1]，這將極大地增加可接收到的AIS數據量。AIS數據具有數據量大、單船更新延遲和整體更新頻繁等3個特性。AIS動態信息的更新時間根據船舶的速度和操縱情況為2～180 s，為保證AIS數據的更新和檢索效率，同時防止數據檢索時發生誤檢和漏檢現象[2]，需建立高效的AIS數據索引機制。

船舶動態數據的檢索，已有部分文獻做過研究，如使用改進的3DR-Tree索引船舶位置的實時數據[3];使用四叉樹算法對船位數據進行檢索[4]，使用MongoDB對船舶實時數據進行檢索[5]。這些方法都是假設船舶動態數據的更新近似于實時的，而忽略位置更新延遲所帶來的誤差。為此，本文采用基于移動數據索引方法構建船舶動態數據索引結構，以減小因時差帶來的檢索誤差問題。

在空間數據檢索方面，最常用的是文獻[6]提出的R-tree方法。R-tree是一個高度平衡樹，使用最小外包矩形組織空間物標。文獻[7]的R*-tree是在R-tree基礎上進行改進的，使用強制插入算法，避免因為節點溢出引起過多分裂。文獻[8]的TPR-tree考慮了物標的速度對檢索的影響，解決了運動物標位置隨時間變化的檢索問題。文獻[9]的TRP*-tree在TPR-tree基礎上對插入算法的代價模型進行了改進，提出更優化的最小外包矩形和查詢區域掃測面積的求解方法，并使用優先插入隊列尋找最優插入節點。本文在結合以上索引方法特點的基礎上，建立適合于AIS數據的索引結構。

1 樹結構

每艘船稱為葉節點，包圍葉節點的矩形稱為非葉節點，非葉節點又被另外一個非葉節點包圍，葉節點與非葉節點統稱為節點。將這種帶有運動和變化特性的外包矩形稱為帶時間參數的外包矩形(Time Parameterized Bounding Rectangle，TPBR)。每個節點都由其TPBR包圍，除根節點外，規定了TPBR包圍節點的上限數M和下限樹m。一個樹結構的平面示意見圖1a)，其中共有O1～O12等12個葉節點，假設TPBR包圍節點數的上限為3、下限為2，則可形成O13～O20等8個TPBR的非葉節點。

對應的結構示意見圖1b)，與TPR*-tree不同的是，由于AIS數據更新較為頻繁，為縮短在刪除節點時的路徑查找時間，增加一個Hash表，用于存儲每艘船存放的節點路徑信息，Hash表的鍵為船舶的MMSI號，值為船舶在樹中的存放路徑Pn(n∈N)。

2 構建索引樹

2.1 坐標轉換

船舶在AIS數據中的位置是以經緯度表示的，為適應TPR*-tree樹的平面坐標系，可將經緯度坐標轉換為墨卡托坐標。假設某船位的經緯度為(φ,λ)，其對應的平面坐標(x,y)為

(1)

式(1)中：r0為基準緯度圈半徑；a為地球橢球長軸半徑；q為等量緯度；e為橢球第一偏心率。

2.2 節點緊致

節點緊致算法是為在執行節點插入和刪除操作時，重新調整節點的外包矩形，使其緊湊的包圍子節點。節點Oi的坐標為(x(t)i-,x(t)i+,y(t)i-,y(t)i+,vxi-,vxi+,vyi-,vyi+)，x為橫坐標軸，y為縱坐標軸，x(t)i-和x(t)i+分別為節點Oi在t時刻的下/上邊界坐標，y(t)i-和y(t)i+分別為節點Oi在t時刻的下/上邊界坐標；vxi-、vxi+、vyi-、vyi+分別表示節點Oi的速度在x軸和y軸上的下/上邊界分量。向東為正，向西為負，向北為正，向南為負。

1) 對于非葉節點，TPBR在各象限的下邊界位置和速度取所有包圍物標的最小值，上邊界位置和速度取所有包圍物標的最大值。

2) 對于葉節點可將x軸和y軸的下/上邊界值設置為相等。

可看出TPBR的位置和大小會隨著時間的變化而變化，在起始時刻時TPBR是包圍節點的最小外包矩形，但之后卻不一定是，這是為保證TPBR在任何時候都能夠包圍所含節點。節點分別沿x軸和y軸的分速度為

(2)

式(2)中：VSOG為船舶航速；VCOG為航向。

假設物標上一次更新時間為t0，因為TPBR的形狀不會收縮，只會增長，所以在TPBR中不能出現早于更新時刻的節點信息。因此，需要在有船舶動態數據更新時，實時地調整對應的TPBR及其所含節點的參數。TPBR包含節點在更新時刻的調整過程為

(3)

式(3)中：tupd為更新時間。TPBR的x(t)-取所有包圍物標的x軸最小值，x(t)+取所有包圍物標的x軸最大值，y(t)-取所有包圍物標的y軸最小值，y(t)+取所有包圍物標的y軸最大值，vx-、vx+、vy-、vy+分別取所有包圍物標速度在x軸和y軸上的最小值和最大值分別為

(4)

(5)

2.3 插入流程

船舶動態數據庫的節點插入流程見圖2，具體過程為

1) 在時間t0收到一艘船舶Oi的位置更新數據，運用式(2)對速度進行分解，設置節點的坐標值，將重插標識符設置為false，執行步驟2)。

2) 調用路徑選擇算法(見2.4節)找出O最適合插入的TPBR路徑，執行節點緊致算法，將插入路徑更新到Hash表中，執行步驟3)。

3) 判斷TPBR包圍的節點數是否超過上限M，如超過則進入步驟4)，如未超過則結束插入。

4) 判斷節點重插標識符，如果為true，跳到步驟6)執行節點分裂算法，否則執行步驟5)選擇重插節點。

5) 抽取30%的影響檢索效率最大的節點，將重插標識符設置為true，對余下的節點執行節點緊致算法，對抽取的節點逐個執行步驟2)。

6) 調用節點分裂算法將節點分裂為兩個新節點，將分裂后的路徑更新到Hash表中，執行節點緊致算法，返回其父節點指針，執行步驟3)。

2.4 路徑選擇

當新數據或更新數據要被插入到樹中時(更新數據需先調用刪除算法對舊數據進行刪除)，系統需選擇最佳插入路徑。為提高檢索命中率，最佳路徑應是在物標插入后，使TPBR在未來一段檢索時間qT的掃描面積增加值最小，稱為最小增加代價衰減。為實現這一目的，路徑選擇算法維護一個優先插入隊列QP，記錄檢驗過的備選插入路徑選項。QP按照增加的代價衰減由小到大的順序進行排序，當所有候選路徑都被檢索后，選擇代價衰減增加最小的路徑。代價衰減增加值等于增加后的代價衰減減去增加前的代價衰減，具體有

ΔA=A(Onew,H)-A(Oold,H)

(6)

式(6)中：H為檢索時間長度，可根據具體情況進行設置；Onew和Oold分別為插入之后的節點和插入之前的節點；A(Onew,H)和A(Oold,H)則表示插入后和插入前節點O在H時間段上的掃描面積；ΔA表示插入前后的掃描面積增加值。

路徑選擇算法示意見圖3。圖3中有6個移動的物標，分別為a、b、c、d、e、f為靜止物標，其余物標速度都為單位時間走10個單元，圍成3個TPBR，分別是i、g、h，虛線表示TPBR在t0時刻的狀態，a(0)、b(0)、c(0)、d(0)、e(0)、f(0)為6個物標在t0時刻的位置。在t0時刻收到一艘新船數據p，假設qT=3，通過式(6)可得插入路徑分別為g、h和i的代價衰減增加值排序隊列QP=[(g,0), (h,0), (i,2 600)], 小括號中的數值為p被插入到相應節點中的代價衰減增加值。由于i的值比g、h的值大，所以無須展開。p的插入并沒有對原有g和h的TPBR有所改變，其代價衰減增加值為0。由于g和h相等，所以需要判斷其下一層節點的代價衰減增加值。如果將p插入g，對于路徑(a,g)和(b,g)的代價衰減增加值分別為1 500和1 800，此時QP={[(h)，0]，[(a，g)，1 500]，[(b，g)，1 800]，[(i)，2 600]}，(a，g)和(b，g)表示完整的節點路徑。如果將p插入h后，QP={[(a，g)，1 500]，[(d，h)，1 500]，[(c，h)，1 500]，[(b，g)，1 800]，[(i)，2 600]}。(a，g)，(d，h)，(c，h)具有相同的代價衰減增加值。在P中選擇最小值作為插入路徑：如果具有2個衰減增加值相等的插入路徑，則選擇掃描面積最小的作為插入路徑；如果掃描面積相等，則隨機選擇。由圖3可知，節點h的掃描面積比g小，因此選擇h作為最佳插入路徑。

2.5 節點刪除

有2種情況會調用節點刪除算法，一種是物標丟失，另一種是有更新數據到達時需刪除舊的數據。系統通過保存的船舶插入路徑Hash表定位到刪除位置將節點刪除。另外，在刪除節點時只對插入路徑上的TPBR使用節點緊致算法。其他與TPR*-tree的刪除算法相同。

3 船舶動態數據檢索

船舶動態數據檢索是指查詢當前或將來某一時刻或時間段內出現在查詢位置一定距離范圍內的船舶，查詢位置可以是靜態的，也可以是運動的。本文是在轉換的閔可夫斯基和(Transformed Minkowski Sum，TMS)改進算法的基礎上進行判斷[10]。

3.1 船舶動態數據索引流程

船舶動態數據索引流程見圖4，圖4中實線箭頭為數據流向，虛線箭頭為發起查詢請求。船舶動態數據通過AIS船站經過AIS岸站或衛星站傳輸給AIS解碼服務器，AIS解碼服務器將解碼后的數據發送給數據管理服務器，數據管理服務器利用索引樹構建方法建立索引樹結構，并將船舶動態數據存入數據庫，建立索引樹后的效果見圖5。監控客戶端根據檢索位置的查詢時間和運動速度向數據管理服務器發起查詢一定距離范圍內的船舶請求，對監控船舶5 n mile范圍內的他船進行查詢(見圖6)。數據管理服務器在收到查詢請求后，找到滿足查詢條件的船舶，并使用MMSI號在數據庫中找出船舶的詳細信息返回給監控客戶端。

3.2 距離查詢

3.2.1坐標平移

用(xq,yq)表示本船位置Oq，(xr,yr)表示目標左下或右上角位置Or。假設Oq在t0時刻的坐標為(0, 0, 0, 0,-30,-30,-30,-30)，Or的坐標為(-4, -3, -3, -2, -10, 10, -10, 10)，使用式(4)將Or變換為相對于Oq的運動，此時的Oq坐標變為(0,0,0,0,0,0,0,0)，Or坐標變為(-4,-3,-3,-2,20,40,20,40)。

(i=x-,x+,y-,y+,vx-,vx+,vy-,vy+)

(7)

3.2.2閔可夫斯基和求取

根據閔可夫斯基和定理[11]，Or關于Oq的閔可夫斯基和等于Oq沿著Or的表面滾動一周，Oq中心的軌跡所包圍的區域。這種方法實際上是通過Oq的半徑將Or擴大，將Or關于Oq在t時刻的TMS表示為TMS(Or,Oq,t)。

TMS(Or,Oq,t)在H上可得到一個掃描陰影區(見圖7)。如果掃描陰影區包含坐標原點，則Or與Oq在H相交。反之，不相交。

4 性能測試

本文算法的試驗數據來源于天津海事數據中心，包括動態數據和歷史軌跡數據，覆蓋范圍為(18°N, 104°E)到(43°N, 125°E)。動態數據時間段為2017年5月31日15：38：42—2017年5月31日15：44：42共6 min的數據，接收到的船舶總數為34 662艘。歷史軌跡數據有10萬條。

試驗內容包括：H試驗，M試驗，檢索精度試驗，與R*-tree和TPR*-tree算法的比較試驗。算法使用C++語言實現。為了保證檢索算法能在大多數普通電腦上運行，所有的試驗均運行在同一臺普通臺式機上，配置為Intel Core i5-3570 CPU 3.40 GHz and 4.00 GB RAM。

4.1 H試驗

文獻[8]給出H的最佳取值為H=UI/2+W，UI為物標的更新周期，W為預測檢索時間長度。AIS數據的UI為15～120 s[12]。本文通過統計試驗發現，在AIS基站信號較好的水域，96%的UI在22 s以內，因此，將UI定為22 s。

在對船舶進行檢索時，既要保證AIS的W不宜過長，又要保證不會發生過多船舶丟失的現象。W在30～360 s的檢索試驗(見圖8)。具體是每插入5 000艘船，對最后插入的100艘船舶執行距離為10 n mile的檢索試驗，直到將34 663艘船全部插入。由圖可知，W對檢索時間影響較小。本文在后續試驗中將W設置為360 s，則H=371 s。

4.2 M試驗

通過觀察不同M的取值對插入時間的影響，m取為40%M(見圖9)。取M為4～40中的8個值，統計插入時間。試驗發現，當M>40時，插入時間明顯增長，因此對于M>40的值沒有在圖上標出。試驗使用10萬條歷史數據，每插入1萬條數據記錄一次時間間隔?？芍?，當M=10時的插入耗時最小，且隨著M的增加插入耗時增長。

M為4～150時，檢索距離為1 n mile的幾個具有代表性的檢索時間試驗結果(見圖10)。由圖10可知，M=150最好，其次是M=10或15。檢索距離r在2～10 n mile時，檢索時間的變化曲線圖(見圖11)。由圖11可知，隨著檢索距離增大，所需檢索時間雖有所增加，但增幅較小。以上兩試驗的檢索方法同W對檢索時間的影響試驗。

綜合以上5個試驗，當H<371 s，M=10時的插入和檢索效率總體最優。

1) 分析H在短時間內對檢索時間影響不大的原因，主要是船舶航速相對于其他交通工具要慢，因此，H在差異不大的情況下，不會增加過多檢索到的節點。同時，由于船舶航向和航速相對穩定，可將預測時間相應增長，以增加對未來形式判斷的效果。

2)M對插入和檢索時間的影響較大，尤其是插入時間，分析原因主要是AIS更新數據量較大，船舶分布范圍較廣，較小的M可形成較小的TPBR，減少插入計算量和檢索節點數，但太小時反而會增加插入和檢索代價。

4.3 檢索精度試驗

本文使用MATLAB程序將所有船舶按當前航向航速推算到檢索時間位置，再使用distance函數計算檢索中心與其他所有船舶間的距離，與檢索結果進行比較。試驗方法是從2～10 n mile每隔2 n mile進行一次檢索，船舶總數為34 663艘，隨機選取100艘船的船位作為檢索中心，檢索結果發現與MATLAB計算結果基本一致，證明本算法是可靠的。

4.4 比較試驗

將本文算法與R*-tree，TPR*-tree在插入時間、檢索時間和檢索精度等3個方面進行比較試驗。

1) 插入時間比較是用相同的數據分別插入到3種算法中，比較插入時間。

2) 檢索時間比較是比較在同等條件下進行相同次數檢索所需的檢索時間。

3) 檢索精度比較是分別將3種算法的檢索結果與MATLAB計算結果進行比較。

插入時間比較結果見圖12。由圖12可知本算法的插入時間與R*-tree相當，與TPR*-tree相比，有較大幅度的降低，主要原因是本算法使用一個Hash表存儲船舶數據在TPR*-tree中的節點位置，提高了船舶數據的更新效率。本算法平均處理每條AIS數據約需3.2 ms。據統計，目前中國沿海每秒能接收到的AIS數據約為250條，因此，本算法可保證數據得到及時處理。

距離檢索時間與R*-tree，TPR*-tree的窗口檢索時間比較結果見圖13，3種算法的檢索速度相當。但R*-tree，TPR*-tree只有窗口檢索，本算法既可進行窗口查詢，也可進行距離查詢。

對3種算法執行100次檢索，將結果與MATLAB計算結果進行比較發現，本算法與TPR*-tree的檢索結果一樣，但R*-tree的誤檢率(誤檢次數除以檢索次數)和漏檢率(漏檢次數除以檢索次數)分別為20%和22%。從試驗來看，如果要追求精確的檢索結果，必須在建立的索引結構中考慮AIS數據的更新延遲時間和船舶速度。

5 結束語

本文基于TPR*-tree建立一種AIS動態數據的索引機制，使用Hash表存儲船舶在索引樹中的節點位置，使用經改進的TMS算法對動態數據進行距離檢索。試驗證明，本文所述的檢索結構能快速地對船舶動態數據進行插入和檢索，且檢索結果準確，適用于對分布范圍廣闊、數據量大的AIS動態數據進行查詢。