一種高效的船舶動態(tài)數(shù)據(jù)索引方法

張遠強, 史國友

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

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

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

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

1 樹結(jié)構(gòu)

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

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

2 構(gòu)建索引樹

2.1 坐標轉(zhuǎn)換

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

(1)

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

2.2 節(jié)點緊致

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

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

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

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

(2)

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

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

(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 插入流程

船舶動態(tài)數(shù)據(jù)庫的節(jié)點插入流程見圖2，具體過程為

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

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

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

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

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

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

2.4 路徑選擇

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

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

(6)

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

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

2.5 節(jié)點刪除

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

3 船舶動態(tài)數(shù)據(jù)檢索

船舶動態(tài)數(shù)據(jù)檢索是指查詢當前或?qū)砟骋粫r刻或時間段內(nèi)出現(xiàn)在查詢位置一定距離范圍內(nèi)的船舶，查詢位置可以是靜態(tài)的，也可以是運動的。本文是在轉(zhuǎn)換的閔可夫斯基和(Transformed Minkowski Sum，TMS)改進算法的基礎上進行判斷[10]。

3.1 船舶動態(tài)數(shù)據(jù)索引流程

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

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坐標變?yōu)?0,0,0,0,0,0,0,0)，Or坐標變?yōu)?-4,-3,-3,-2,20,40,20,40)。

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

(7)

3.2.2閔可夫斯基和求取

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

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

4 性能測試

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

試驗內(nèi)容包括：H試驗，M試驗，檢索精度試驗，與R*-tree和TPR*-tree算法的比較試驗。算法使用C++語言實現(xiàn)。為了保證檢索算法能在大多數(shù)普通電腦上運行，所有的試驗均運行在同一臺普通臺式機上，配置為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數(shù)據(jù)的UI為15～120 s[12]。本文通過統(tǒng)計試驗發(fā)現(xiàn)，在AIS基站信號較好的水域，96%的UI在22 s以內(nèi)，因此，將UI定為22 s。

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

4.2 M試驗

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

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

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

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

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

4.3 檢索精度試驗

本文使用MATLAB程序?qū)⑺写鞍串斍昂较蚝剿偻扑愕綑z索時間位置，再使用distance函數(shù)計算檢索中心與其他所有船舶間的距離，與檢索結(jié)果進行比較。試驗方法是從2～10 n mile每隔2 n mile進行一次檢索，船舶總數(shù)為34 663艘，隨機選取100艘船的船位作為檢索中心，檢索結(jié)果發(fā)現(xiàn)與MATLAB計算結(jié)果基本一致，證明本算法是可靠的。

4.4 比較試驗

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

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

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

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

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

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

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

5 結(jié)束語

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