張遠(yuǎn)強(qiáng), 史國友

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

中國沿海和內(nèi)河4級以上河段的船舶自動識別系統(tǒng)(Automatic Identification System, AIS)網(wǎng)絡(luò)已實(shí)現(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ù)索引機(jī)制。

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

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

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

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

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

2 構(gòu)建索引樹

2.1 坐標(biāo)轉(zhuǎn)換

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

(1)

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

2.2 節(jié)點(diǎn)緊致

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

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

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

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

(2)

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

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

(3)

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

(4)

(5)

2.3 插入流程

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

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

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

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

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

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

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

2.4 路徑選擇

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

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

(6)

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

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

2.5 節(jié)點(diǎn)刪除

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

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

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

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

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

3.2 距離查詢

3.2.1坐標(biāo)平移

用(xq,yq)表示本船位置Oq，(xr,yr)表示目標(biāo)左下或右上角位置Or。假設(shè)Oq在t0時刻的坐標(biāo)為(0, 0, 0, 0,-30,-30,-30,-30)，Or的坐標(biāo)為(-4, -3, -3, -2, -10, 10, -10, 10)，使用式(4)將Or變換為相對于Oq的運(yùn)動，此時的Oq坐標(biāo)變?yōu)?0,0,0,0,0,0,0,0)，Or坐標(biāo)變?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關(guān)于Oq的閔可夫斯基和等于Oq沿著Or的表面滾動一周，Oq中心的軌跡所包圍的區(qū)域。這種方法實(shí)際上是通過Oq的半徑將Or擴(kuò)大，將Or關(guān)于Oq在t時刻的TMS表示為TMS(Or,Oq,t)。

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

4 性能測試

本文算法的試驗(yàn)數(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萬條。

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

4.1 H試驗(yàn)

文獻(xiàn)[8]給出H的最佳取值為H=UI/2+W，UI為物標(biāo)的更新周期，W為預(yù)測檢索時間長度。AIS數(shù)據(jù)的UI為15～120 s[12]。本文通過統(tǒng)計(jì)試驗(yàn)發(fā)現(xiàn)，在AIS基站信號較好的水域，96%的UI在22 s以內(nèi)，因此，將UI定為22 s。

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

4.2 M試驗(yàn)

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

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

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

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

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

4.3 檢索精度試驗(yàn)

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

4.4 比較試驗(yàn)

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

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

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

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

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

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

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

5 結(jié)束語

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