一種基于B+樹航跡態(tài)勢回放系統(tǒng)的設(shè)計與實驗

張 明 杰

(中國電子科學(xué)研究院 北京 100041)

0 引 言

態(tài)勢是指戰(zhàn)場空間中兵力分布和戰(zhàn)場環(huán)境的當(dāng)前狀態(tài)及發(fā)展變化趨勢的總稱[1]。態(tài)勢回放是將指定歷史時間段內(nèi)的態(tài)勢信息(比如探測源探測到的航跡信息、從通信鏈路接收到的航跡信息、戰(zhàn)場元素自身的位置變化信息等)按照時間順序動態(tài)地顯示在計算機(jī)圖形界面上。態(tài)勢回放為相關(guān)人員進(jìn)行態(tài)勢分析提供了一種方便易用的技術(shù)手段，在傳感器探測效能分析、演習(xí)效果評估等方面具有重要的作用。

國外一般將態(tài)勢回放作為事后回顧和分析的基礎(chǔ)內(nèi)容[2-3]。國內(nèi)一些學(xué)者也對態(tài)勢回放技術(shù)進(jìn)行了研究和實現(xiàn)，如基于HLA的態(tài)勢回放系統(tǒng)[4]、基于Skyline態(tài)勢回放系統(tǒng)[5-6]、基于XSimStudio的態(tài)勢回放系統(tǒng)[7]、基于數(shù)據(jù)庫的態(tài)勢回放系統(tǒng)[8]、基于C/S架構(gòu)的態(tài)勢回放系統(tǒng)[9]等。但這些態(tài)勢回放系統(tǒng)大多是對模擬或仿真產(chǎn)生的態(tài)勢數(shù)據(jù)進(jìn)行回放，對真實態(tài)勢數(shù)據(jù)進(jìn)行回放的系統(tǒng)目前并不多見，并且，在數(shù)據(jù)量較大時，存在回放效率不高的問題[3，10]。

B+樹是一種高度平衡樹，是在B樹[11]的基礎(chǔ)上由Knuth實現(xiàn)并由Comer命名的一種索引技術(shù)[12-13]，具有隨機(jī)和順序查詢效率高、更新開銷小、高度自平衡等特點，特別適用于既需要隨機(jī)查找也需要順序查找

的應(yīng)用場景。目前，B+樹已在大數(shù)據(jù)索引[14]、云數(shù)據(jù)索引[15]、數(shù)據(jù)庫[16]等眾多領(lǐng)域得到廣泛應(yīng)用。

本文提出的基于B+樹的態(tài)勢回放系統(tǒng)，以某大型電子信息系統(tǒng)運(yùn)行過程中感知并記錄的真實態(tài)勢數(shù)據(jù)文件作為數(shù)據(jù)源，從中提取態(tài)勢信息(航跡點)，使用B+樹文件對海量的航跡點進(jìn)行組織、查詢，并對航跡點集合進(jìn)行態(tài)勢計算及顯示，實現(xiàn)了真實態(tài)勢數(shù)據(jù)的回放。由于將航跡點作為關(guān)鍵字存儲在B+樹文件中，利用了B+樹隨機(jī)查找和順序讀取數(shù)據(jù)的高效性，使得本文實現(xiàn)的態(tài)勢回放系統(tǒng)具有較高的效率。

1 相關(guān)概念

為了便于對系統(tǒng)工作原理進(jìn)行表述，本節(jié)使用集合論的語言對與態(tài)勢回放相關(guān)的概念和術(shù)語進(jìn)行形式化定義。

1.1 航跡點

航跡點是態(tài)勢回放系統(tǒng)的基本數(shù)據(jù)單元，是包含時間、航跡號、位置等信息的元組。本文將航跡點表示為一個具有五維分量的數(shù)據(jù)單元：

p=〈t,n,x,y,z〉

(1)

式中：p表示航跡點；t∈(表示自然數(shù)集合)代表時間(以公元元年1月1日零時為時間起始點)，單位是ms；n∈代表航跡號；x∈(表示實數(shù)集合)、y∈、z∈，表征航跡點的三維空間坐標(biāo)，單位為m。

p的各組成元素t、n、x、y、z稱為p的分量。

1.2 航跡點之間的基本關(guān)系

(1) 相等關(guān)系 設(shè)pi與pj(i,j∈)是任意兩個航跡點，若pi與pj的各個組成分量相等，則稱這兩個航跡點相等，否則稱這兩個航跡點不相等。

(2) 大于關(guān)系 設(shè)pi與pj(i,j∈)是兩個航跡點，若pi的任一分量按從左向右的順序大于pj的相應(yīng)分量，則稱航跡點pi大于pj。

(3) 小于關(guān)系 設(shè)pi與pj(i,j∈)為兩個航跡點，若pi的任一分量按從左向右的順序小于pj的相應(yīng)分量，則稱航跡點pi小于pj。

(4) 航跡點之間的距離 航跡點pi與pj之間的距離d定義為：

(2)

(5) 航跡點之間的時間差 航跡點pi與pj之間的時間差Δt定義為：

Δt(pi,pj)=|pi.t-pj.t|

(3)

1.3 有序航跡點集合與同跡關(guān)系

(1) 有序航跡點集合 設(shè)P={pk|k=1,2,…,K;K∈∧K>0}是一個有限的航跡點集合，任意兩個元素pi

(2) 同跡關(guān)系 設(shè)P是一個有序航跡點集合，pi,pj∈P，若pi與pj的航跡號相同，且時間差和距離均不大于相應(yīng)的給定閾值，則稱pi與pj滿足直接同跡關(guān)系DST(Direct Same Track)。形式化表示為：

DST(pi,pj)?(pi.n=pj.n)∧

(Δt(pi,pj)≤Tht)∧(d(pi,pj)≤Thd)

(4)

式中：Tht與Thd是給定的時間閾值和距離閾值。

若在pi與pj之間存在一個長度為l(是正整數(shù))的航跡點列〈pi+a1,pi+a2,…,pi+al〉，使得DST(pi,pi+a1)、DST(pi+a1,pi+a2)、…、DST(pi+al,pj)均成立，則稱pi與pj滿足間接同跡關(guān)系IST(Indirect Same Track)。

直接同跡關(guān)系和間接同跡關(guān)系統(tǒng)稱為同跡關(guān)系ST(Same Track)。容易證明，同跡關(guān)系滿足自反性、對稱性和傳遞性，從而是有序航跡點集合上的等價關(guān)系，可以對有序航跡點集合進(jìn)行劃分，即可使用同跡關(guān)系將有序航跡點集合劃分為若干個互不相交的子集，每個子集作為一條航跡的一個組成部分。

1.4 航 跡

設(shè)P是一個有序航跡點集合，將P中一個滿足同跡關(guān)系的有序航跡點子集及其相關(guān)的特征信息(如航跡號、航跡長度等)的組合，稱作一條航跡tr(Track)。形式化表示為：

tr=〈No,Len,ts,td,Tp〉

(5)

式中：有序航跡點子集Tp={p1,p2,…,pLen}?P，Tp中任意兩個航跡點之間滿足同跡關(guān)系，且任意兩個相鄰航跡點之間滿足直接同跡關(guān)系；No表示航跡號，與Tp中的航跡點的航跡號相同；Len表示航跡的長度，即Tp中元素的個數(shù)；ts、td表示航跡的起止時間，即Tp中第一個航跡點和最后一個航跡點的時間。

1.5 航跡與航跡點匹配

一條航跡tr與一個航跡點p匹配是指tr的最后一個航跡點與p滿足直接同跡關(guān)系。形式化表示為：

Match(tr,p)?DST(tr.Tp.pLen,p)

(6)

式中：tr.Tp.pLen表示航跡tr的有序航跡點集的最后一個元素。

1.6 時間窗

時間窗即一個時間段的別名。形式化表示為：

tw=[tb,te]=[tb,tb+w]

(7)

式中：tw表示時間窗；tb表示時間窗的起始時間；te表示時間窗的終止時間；w表示時間窗的寬度。本文中，tw、tb、w的單位是ms，取值范圍是自然數(shù)集合。

1.7 有序航跡點集合在時間窗內(nèi)的投影

有序航跡點集合P在時間窗tw內(nèi)的投影即P中所有時間值在tw范圍內(nèi)的航跡點的集合。形式化表示為：

proj(P,tw)={p|(p∈P)∧(tw.tb≤p.t≤tw.te)}

(8)

1.8 態(tài) 勢

態(tài)勢Sit(Situation)特指由有序航跡點集合P依同跡關(guān)系劃分而得的航跡集合。設(shè)P中的航跡點依同跡關(guān)系可劃分為L個子集，則由P產(chǎn)生的態(tài)勢可形式化表示為：

Sit(P)=P/ST={tr1,tr2,…,trL}

(9)

式中：P/ST表示用同跡關(guān)系ST對有序航跡點集合P進(jìn)行劃分。

在時間窗tw內(nèi)由P產(chǎn)生的態(tài)勢，稱為一幀態(tài)勢或態(tài)勢幀。形式化表示為：

Sit(P,tw)=proj(P,tw)/ST={tr1,tr2,…,trLw}

(10)

式中：proj(P,tw)/ST表示用同跡關(guān)系ST對有序航跡點集合P在時間段tw內(nèi)的投影的劃分，Lw表示劃分后形成的航跡的條數(shù)。

與態(tài)勢相關(guān)的說明：(1) 因為一條航跡是滿足某些特性的航跡點集合及其特征描述信息的組合，所以，從本質(zhì)上講，態(tài)勢也可以看作是航跡點的集合；(2) 將有序航跡點集合依同跡關(guān)系進(jìn)行劃分形成航跡集合的過程稱為態(tài)勢計算；(3) 態(tài)勢顯示時，除了顯示航跡點之外，還將屬于同一條航跡的航跡點之間按時間先后順序使用線段連接，以便于進(jìn)行觀察和分析。

2 B+樹及B+樹文件

為了從海量航跡點中查找到指定時間窗內(nèi)的航跡點子集，本文將所有航跡點以B+樹文件的形式進(jìn)行組織，利用B+樹隨機(jī)查找和順序讀取數(shù)據(jù)的高效性，保證回放系統(tǒng)的效率。

本節(jié)參照文獻(xiàn)[17-18]中B+樹的描述，對回放系統(tǒng)使用的以式(1)定義的航跡點作為關(guān)鍵字的B+樹及B+樹文件進(jìn)行介紹。

2.1 B+樹的定義

階數(shù)為M的B+樹要么是空樹，要么是滿足下列特性的M叉樹：

1) 樹中每個節(jié)點至多有M棵子樹。

2) 若根節(jié)點不是葉節(jié)點，則至少有兩棵子樹。

4) 任一節(jié)點的邏輯結(jié)構(gòu)可表示為(n;p0,A0,p1,A1,…,pn-1,An-1;AL,AR)。其中：pi(i=0,1,…,n-1)為航跡點(即關(guān)鍵字)，且pi

5) 所有的葉節(jié)點都出現(xiàn)在同一層次上，且包含了全部航跡點。葉節(jié)點按照航跡點從小到大的順序鏈接，即若當(dāng)前節(jié)點的指針AL、AR非空，則AL指向的節(jié)點中的所有航跡點均小于當(dāng)前節(jié)點的p0，AR指向的節(jié)點中的所有航跡點均大于當(dāng)前節(jié)點的pn-1。

6) 左兄弟節(jié)點指針AL為空的葉節(jié)點，稱為最小葉節(jié)點；右兄弟節(jié)點指針AR為空的葉節(jié)點，稱為最大葉節(jié)點。

7) 從根節(jié)點到某個葉節(jié)點途經(jīng)的節(jié)點集合，稱為一條葉路徑。

上述定義中，以航跡點作為B+樹節(jié)點的關(guān)鍵字，航跡點之間的大小關(guān)系由式(3)和式(4)定義。

2.2 B+樹文件

B+樹文件是在存儲介質(zhì)(如硬盤)上保存的二進(jìn)制數(shù)據(jù)文件，由文件頭和文件體兩部分組成。其邏輯結(jié)構(gòu)如圖1所示。

圖1 B+樹文件邏輯結(jié)構(gòu)圖

文件頭描述文件中保存的B+樹的特征信息，包含的信息項主要有：

1) 階數(shù)M；

2) 航跡點(即關(guān)鍵字)總數(shù)nTrkPtCount(即所有葉節(jié)點中包含的航跡點的個數(shù))；

3) 節(jié)點總數(shù)nNodeCount；

梁肇彬供述稱：“鄧強(qiáng)是城投公司的董事長，對城投公司及其下屬公司的事務(wù)有決定權(quán)，如果沒有他的同意，我不可能順利借助城投公司下屬的建筑公司的資質(zhì)承建上述工程項目，在工程款支付方面也不可能那么順利。我送錢給鄧強(qiáng)也是為了和他搞好關(guān)系，以后可以繼續(xù)合作，多承接一些工程。”

4) 指向根節(jié)點的指針pRootNode(即根節(jié)點在文件中的位置)；

5) 指向最小葉節(jié)點的指針pMinLeafNode(即最小葉節(jié)點在文件中的位置)；

6) 指向最大葉節(jié)點的指針pMaxLeafNode(即最大葉節(jié)點在文件中的位置)。

文件體保存的是一棵B+樹，即B+樹包含的所有節(jié)點數(shù)據(jù)。每個節(jié)點中的指針表示的是其指向的節(jié)點在文件中的位置。

3 系統(tǒng)的組成、工作流程及關(guān)鍵算法

3.1 系統(tǒng)的組織結(jié)構(gòu)

本文提出的態(tài)勢回放系統(tǒng)由態(tài)勢數(shù)據(jù)文件、數(shù)據(jù)文件對象、航跡點提取器、B+樹文件、B+樹文件對象、回放控制器、顯示組件等幾部分組成，系統(tǒng)運(yùn)行時的組織結(jié)構(gòu)如圖2所示。

圖2 態(tài)勢回放系統(tǒng)組織結(jié)構(gòu)圖

各組成部分的功能簡述如下：

態(tài)勢數(shù)據(jù)文件是指由電子信息系統(tǒng)感知并記錄的、包含有航跡點數(shù)據(jù)的二進(jìn)制文件。由于電子信息系統(tǒng)運(yùn)行的網(wǎng)絡(luò)環(huán)境可能采取無連接的通信協(xié)議，所以不能保證數(shù)據(jù)文件中航跡點的時間值按存儲順序單調(diào)遞增。

數(shù)據(jù)文件對象負(fù)責(zé)從態(tài)勢數(shù)據(jù)文件中將包含航跡點的數(shù)據(jù)報文按存儲順序讀取出來，并將其傳輸給航跡點提取器。

航跡點提取器負(fù)責(zé)從數(shù)據(jù)報文中提取出航跡點。

B+樹文件對象是系統(tǒng)的關(guān)鍵組成部分。負(fù)責(zé)將航跡點寫入B+樹文件、按回放控制器指定的時間窗從B+樹文件中讀取航跡點并將其傳輸給顯示組件。

回放控制器是用戶與系統(tǒng)進(jìn)行交互的界面元素，負(fù)責(zé)創(chuàng)建數(shù)據(jù)文件對象、航跡點提取器、B+樹文件對象、顯示組件等運(yùn)行時內(nèi)存對象。用戶可通過回放控制器界面上的時間控制控件(如滑動控件)控制態(tài)勢的計算與顯示。

顯示組件負(fù)責(zé)態(tài)勢的計算和顯示。

3.2 系統(tǒng)的工作流程

系統(tǒng)的工作流程可以分為兩個階段：第一階段，從態(tài)勢數(shù)據(jù)文件中提取航跡點，形成B+樹文件，稱作回放文件形成階段或態(tài)勢回放預(yù)處理階段；第二階段，基于回放文件進(jìn)行態(tài)勢回放，稱作態(tài)勢回放階段。兩個階段的工作流程敘述如下(為了簡化，未進(jìn)行出錯處理的描述)。

態(tài)勢回放預(yù)處理階段的工作流程為：

1) 用戶通過回放控制器指定態(tài)勢數(shù)據(jù)文件名、欲保存的B+樹文件名；

2) 回放控制器為態(tài)勢數(shù)據(jù)文件創(chuàng)建數(shù)據(jù)文件對象，并創(chuàng)建航跡點提取器及B+樹文件對象；

3) 數(shù)據(jù)文件對象判斷文件讀取是否讀取完畢，若讀取完畢，則轉(zhuǎn)7)；否則，讀取一個數(shù)據(jù)報文；

4) 數(shù)據(jù)文件對象將讀取的數(shù)據(jù)報文傳輸給航跡點提取器；

5) 航跡點提取器從數(shù)據(jù)報文中提取航跡點，并將航跡點傳輸給B+樹文件對象；

6) B+樹文件對象將航跡點寫入B+樹文件；轉(zhuǎn)步驟3)；

7) 銷毀創(chuàng)建的內(nèi)存對象，態(tài)勢回放預(yù)處理工作完成。

態(tài)勢回放階段的工作流程為：

1) 用戶通過回放控制器指定需要進(jìn)行回放的B+樹文件名；

2) 回放控制器為指定的文件創(chuàng)建B+樹文件對象；

3) 回放控制器通過B+樹文件對象獲得態(tài)勢的起止時間，并設(shè)置時間控制控件的范圍；

4) 用戶通過回放控制器，設(shè)置時間窗的寬度及起止時間；

5) B+樹文件對象根據(jù)時間窗的起止時間，將B+樹中在時間窗內(nèi)的航跡點傳輸給顯示組件；

6) 顯示組件基于接收到的航跡點集合進(jìn)行態(tài)勢計算(航跡形成算法詳見4.2節(jié))和態(tài)勢顯示。

4 關(guān)鍵算法

4.1 航跡點批量插入算法

為了提高態(tài)勢回放預(yù)處理階段的工作效率，設(shè)計并實現(xiàn)了航跡點批量插入算法。該算法在B+樹文件對象中實現(xiàn)，用于態(tài)勢回放預(yù)處理階段的步驟6)。具體描述如下：

算法1航跡點批量插入算法

輸入：航跡點集合P。

輸出：將P中的航跡點插入B+樹文件。

Step1將P中的航跡點按從小到大順序進(jìn)行排序，形成有序航跡點集合PT。

Step2將PT整批插入B+樹文件中。對于非葉節(jié)點，利用節(jié)點上的航跡點將PT劃分為若干有序子集，把各子集插入該節(jié)點的相應(yīng)子節(jié)點；對于葉節(jié)點，則將該節(jié)點中的航跡點和待插入的航跡點合并排序，形成臨時節(jié)點。

Step3若臨時節(jié)點中包含的航跡點個數(shù)NL不大于B+樹的階數(shù)M，則將臨時節(jié)點寫入文件，完成節(jié)點更新；否則，將臨時節(jié)點分裂為NL/M個節(jié)點，并把這些節(jié)點的指針和最小關(guān)鍵字插入父節(jié)點；若父節(jié)點需要分裂，則繼續(xù)向上分裂，直到無需分裂為止。

Step4根據(jù)更新節(jié)點及新建節(jié)點的情況，修改B+樹文件頭。

該算法在一般情況下，相對于每次只插入一個航跡點的算法，可大大提高系統(tǒng)的性能，縮短回放預(yù)處理的時間。算法性能的具體分析請參閱文獻(xiàn)[20]。

4.2 航跡形成算法

為了有效地將某個時間窗內(nèi)的航跡點集合形成航跡集合(即態(tài)勢幀)，本文提出了基于航跡表的航跡形成算法，描述如下：

算法2航跡形成算法

輸入：航跡點集合P。

輸出：航跡表TR。

Step1初始化TR為空。

Step2順序掃描P中的所有航跡點pi(i=0,1,…,N-1)，N為P中元素的個數(shù)。

Step3將TR中的航跡與pi進(jìn)行匹配。若匹配不成功，則新建一個航跡tr，插入航跡表TR中；若某個航跡tr與pi匹配成功，則使用pi的信息修改pi，比如將航跡長度加1、更改航跡的終止時間、使用pi代替最后一個航跡點等。

航跡形成算法在顯示組件中實現(xiàn)。該算法空間復(fù)雜度為O(N)，時間復(fù)雜度在一般情況下為O(N2)，若對航跡表中的元素進(jìn)行排序，則時間復(fù)雜度可改善為O(Nlog2N)。

5 系統(tǒng)實現(xiàn)及實驗

5.1 運(yùn)行環(huán)境

在通用的個人臺式計算機(jī)上，使用Visual Studio 2010的C++語言對系統(tǒng)進(jìn)行了實現(xiàn)(背景地圖使用第三方軟件)。

臺式計算機(jī)的詳細(xì)配置信息為如下：

臺式計算機(jī)型號：Dell XPS 8300。

操作系統(tǒng)：Windows XP Professional with SP3。

CPU：英特爾第二代酷睿i5-2310，主頻2.9 GHz，四核。

內(nèi)存：4 GB，南亞易勝DDR3，1.333 GHz。

硬盤：西部數(shù)據(jù)WDC WD10EALX-759BA1，容量1 TB，每分鐘7 200轉(zhuǎn)。

顯卡：獨立顯卡，ATI Radeon HD 6700 Series。

5.2 系統(tǒng)性能評價指標(biāo)

為了對態(tài)勢回放系統(tǒng)的性能進(jìn)行評價，本文提出了繪點數(shù)據(jù)率的概念，即一幀態(tài)勢所含的航跡點數(shù)與繪制該幀態(tài)勢的核心代碼運(yùn)行所需時間的比值，單位為點/s。繪制一幀態(tài)勢的核心代碼完成的功能主要包括：(1) B+樹文件對象根據(jù)時間控制器給定的時間窗起止時間，從B+樹的根節(jié)點(駐留在硬盤上)到葉節(jié)點進(jìn)行搜索，找到起始時間對應(yīng)的葉節(jié)點的位置；(2) 從起始時間對應(yīng)的葉節(jié)點開始，到終止時間對應(yīng)的葉節(jié)點為止，順序訪問各葉節(jié)點中的在起止時間范圍內(nèi)的航跡點，并將這些航跡點傳輸給顯示組件進(jìn)行態(tài)勢計算和顯示。

5.3 系統(tǒng)運(yùn)行實驗

系統(tǒng)運(yùn)行時，將B+樹文件的階數(shù)設(shè)置為256，航跡點批量插入算法的航跡點集合的個數(shù)設(shè)置為1 024，即在B+樹文件的形成過程中，每次最多向其中插入1 024個航跡點。態(tài)勢回放時時間窗寬度為100 s。

系統(tǒng)運(yùn)行的圖形界面如圖3所示，用戶可通過態(tài)勢回放控制器上的滑動條控件改變時間窗的起止時間，實現(xiàn)態(tài)勢動態(tài)顯示。

圖3 態(tài)勢回放系統(tǒng)運(yùn)行界面圖

態(tài)勢回放預(yù)處理階段，對某大型電子信息系統(tǒng)在某年運(yùn)行過程中記錄的態(tài)勢數(shù)據(jù)文件集進(jìn)行處理，形成B+樹文件，B+樹文件中的航跡點個數(shù)超過1.2億(具體數(shù)字為126 259 363)。

態(tài)勢回放階段，繪點數(shù)據(jù)率約為20萬點/s，即每一秒可完成約20萬個航跡點及航跡點連線的繪制。假設(shè)一條航跡的長度為1 000點，則一秒內(nèi)可完成約2 000條航跡的繪制。該結(jié)果表明本文提出的態(tài)勢回放系統(tǒng)具有較高的性能。

6 結(jié) 語

本文首先對與態(tài)勢回放相關(guān)的概念和術(shù)語進(jìn)行了形式化定義；然后描述了系統(tǒng)的組織架構(gòu)、工作流程及關(guān)鍵算法；最后提出了繪點數(shù)據(jù)率的概念用于衡量系統(tǒng)的運(yùn)行性能，實驗結(jié)果顯示了系統(tǒng)進(jìn)行態(tài)勢回放的高效性。

在該系統(tǒng)的基礎(chǔ)上，擬繼續(xù)在以下幾個方面開展下一步的研究工作：

(1) 優(yōu)化內(nèi)部組件。對大數(shù)據(jù)索引技術(shù)進(jìn)行研究和開發(fā)，以提高數(shù)據(jù)存儲組件的空間利用率和查找效率。

(2) 拓展新的應(yīng)用方向。比如接入通信網(wǎng)絡(luò)，在線實時接收態(tài)勢數(shù)據(jù)進(jìn)行存儲和回放；可通過對數(shù)據(jù)存儲組件的并發(fā)訪問控制技術(shù)的研發(fā)進(jìn)行實現(xiàn)。

(3) 作為算法研究和實驗的平臺?？蓪⒑桔E融合、目標(biāo)識別等算法集成到回放系統(tǒng)中，對算法的執(zhí)行效果進(jìn)行檢驗和評估，以促進(jìn)相關(guān)算法的研究和改善。