一种基于B+树航迹态势回放系统的设计与实验

张 明 杰

(中国电子科学研究院 北京 100041)

0 引 言

态势是指战场空间中兵力分布和战场环境的当前状态及发展变化趋势的总称[1]。态势回放是将指定历史时间段内的态势信息(比如探测源探测到的航迹信息、从通信链路接收到的航迹信息、战场元素自身的位置变化信息等)按照时间顺序动态地显示在计算机图形界面上。态势回放为相关人员进行态势分析提供了一种方便易用的技术手段，在传感器探测效能分析、演习效果评估等方面具有重要的作用。

国外一般将态势回放作为事后回顾和分析的基础内容[2-3]。国内一些学者也对态势回放技术进行了研究和实现，如基于HLA的态势回放系统[4]、基于Skyline态势回放系统[5-6]、基于XSimStudio的态势回放系统[7]、基于数据库的态势回放系统[8]、基于C/S架构的态势回放系统[9]等。但这些态势回放系统大多是对模拟或仿真产生的态势数据进行回放，对真实态势数据进行回放的系统目前并不多见，并且，在数据量较大时，存在回放效率不高的问题[3，10]。

B+树是一种高度平衡树，是在B树[11]的基础上由Knuth实现并由Comer命名的一种索引技术[12-13]，具有随机和顺序查询效率高、更新开销小、高度自平衡等特点，特别适用于既需要随机查找也需要顺序查找

的应用场景。目前，B+树已在大数据索引[14]、云数据索引[15]、数据库[16]等众多领域得到广泛应用。

本文提出的基于B+树的态势回放系统，以某大型电子信息系统运行过程中感知并记录的真实态势数据文件作为数据源，从中提取态势信息(航迹点)，使用B+树文件对海量的航迹点进行组织、查询，并对航迹点集合进行态势计算及显示，实现了真实态势数据的回放。由于将航迹点作为关键字存储在B+树文件中，利用了B+树随机查找和顺序读取数据的高效性，使得本文实现的态势回放系统具有较高的效率。

1 相关概念

为了便于对系统工作原理进行表述，本节使用集合论的语言对与态势回放相关的概念和术语进行形式化定义。

1.1 航迹点

航迹点是态势回放系统的基本数据单元，是包含时间、航迹号、位置等信息的元组。本文将航迹点表示为一个具有五维分量的数据单元：

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

(1)

式中：p表示航迹点；t∈(表示自然数集合)代表时间(以公元元年1月1日零时为时间起始点)，单位是ms；n∈代表航迹号；x∈(表示实数集合)、y∈、z∈，表征航迹点的三维空间坐标，单位为m。

p的各组成元素t、n、x、y、z称为p的分量。

1.2 航迹点之间的基本关系

(1) 相等关系 设pi与pj(i,j∈)是任意两个航迹点，若pi与pj的各个组成分量相等，则称这两个航迹点相等，否则称这两个航迹点不相等。

(2) 大于关系 设pi与pj(i,j∈)是两个航迹点，若pi的任一分量按从左向右的顺序大于pj的相应分量，则称航迹点pi大于pj。

(3) 小于关系 设pi与pj(i,j∈)为两个航迹点，若pi的任一分量按从左向右的顺序小于pj的相应分量，则称航迹点pi小于pj。

(4) 航迹点之间的距离 航迹点pi与pj之间的距离d定义为：

(2)

(5) 航迹点之间的时间差 航迹点pi与pj之间的时间差Δt定义为：

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

(3)

1.3 有序航迹点集合与同迹关系

(1) 有序航迹点集合 设P={pk|k=1,2,…,K;K∈∧K>0}是一个有限的航迹点集合，任意两个元素pi

(2) 同迹关系 设P是一个有序航迹点集合，pi,pj∈P，若pi与pj的航迹号相同，且时间差和距离均不大于相应的给定阈值，则称pi与pj满足直接同迹关系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(是正整数)的航迹点列〈pi+a1,pi+a2,…,pi+al〉，使得DST(pi,pi+a1)、DST(pi+a1,pi+a2)、…、DST(pi+al,pj)均成立，则称pi与pj满足间接同迹关系IST(Indirect Same Track)。

直接同迹关系和间接同迹关系统称为同迹关系ST(Same Track)。容易证明，同迹关系满足自反性、对称性和传递性，从而是有序航迹点集合上的等价关系，可以对有序航迹点集合进行划分，即可使用同迹关系将有序航迹点集合划分为若干个互不相交的子集，每个子集作为一条航迹的一个组成部分。

1.4 航 迹

设P是一个有序航迹点集合，将P中一个满足同迹关系的有序航迹点子集及其相关的特征信息(如航迹号、航迹长度等)的组合，称作一条航迹tr(Track)。形式化表示为：

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

(5)

式中：有序航迹点子集Tp={p1,p2,…,pLen}⊆P，Tp中任意两个航迹点之间满足同迹关系，且任意两个相邻航迹点之间满足直接同迹关系；No表示航迹号，与Tp中的航迹点的航迹号相同；Len表示航迹的长度，即Tp中元素的个数；ts、td表示航迹的起止时间，即Tp中第一个航迹点和最后一个航迹点的时间。

1.5 航迹与航迹点匹配

一条航迹tr与一个航迹点p匹配是指tr的最后一个航迹点与p满足直接同迹关系。形式化表示为：

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，取值范围是自然数集合。

1.7 有序航迹点集合在时间窗内的投影

有序航迹点集合P在时间窗tw内的投影即P中所有时间值在tw范围内的航迹点的集合。形式化表示为：

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

(8)

1.8 态 势

态势Sit(Situation)特指由有序航迹点集合P依同迹关系划分而得的航迹集合。设P中的航迹点依同迹关系可划分为L个子集，则由P产生的态势可形式化表示为：

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

(9)

式中：P/ST表示用同迹关系ST对有序航迹点集合P进行划分。

在时间窗tw内由P产生的态势，称为一帧态势或态势帧。形式化表示为：

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

(10)

式中：proj(P,tw)/ST表示用同迹关系ST对有序航迹点集合P在时间段tw内的投影的划分，Lw表示划分后形成的航迹的条数。

与态势相关的说明：(1) 因为一条航迹是满足某些特性的航迹点集合及其特征描述信息的组合，所以，从本质上讲，态势也可以看作是航迹点的集合；(2) 将有序航迹点集合依同迹关系进行划分形成航迹集合的过程称为态势计算；(3) 态势显示时，除了显示航迹点之外，还将属于同一条航迹的航迹点之间按时间先后顺序使用线段连接，以便于进行观察和分析。

2 B+树及B+树文件

为了从海量航迹点中查找到指定时间窗内的航迹点子集，本文将所有航迹点以B+树文件的形式进行组织，利用B+树随机查找和顺序读取数据的高效性，保证回放系统的效率。

本节参照文献[17-18]中B+树的描述，对回放系统使用的以式(1)定义的航迹点作为关键字的B+树及B+树文件进行介绍。

2.1 B+树的定义

阶数为M的B+树要么是空树，要么是满足下列特性的M叉树：

1) 树中每个节点至多有M棵子树。

2) 若根节点不是叶节点，则至少有两棵子树。

4) 任一节点的逻辑结构可表示为(n;p0,A0,p1,A1,…,pn-1,An-1;AL,AR)。其中：pi(i=0,1,…,n-1)为航迹点(即关键字)，且pi

5) 所有的叶节点都出现在同一层次上，且包含了全部航迹点。叶节点按照航迹点从小到大的顺序链接，即若当前节点的指针AL、AR非空，则AL指向的节点中的所有航迹点均小于当前节点的p0，AR指向的节点中的所有航迹点均大于当前节点的pn-1。

6) 左兄弟节点指针AL为空的叶节点，称为最小叶节点；右兄弟节点指针AR为空的叶节点，称为最大叶节点。

7) 从根节点到某个叶节点途经的节点集合，称为一条叶路径。

上述定义中，以航迹点作为B+树节点的关键字，航迹点之间的大小关系由式(3)和式(4)定义。

2.2 B+树文件

B+树文件是在存储介质(如硬盘)上保存的二进制数据文件，由文件头和文件体两部分组成。其逻辑结构如图1所示。

图1 B+树文件逻辑结构图

文件头描述文件中保存的B+树的特征信息，包含的信息项主要有：

1) 阶数M；

2) 航迹点(即关键字)总数nTrkPtCount(即所有叶节点中包含的航迹点的个数)；

3) 节点总数nNodeCount；

梁肇彬供述称：“邓强是城投公司的董事长，对城投公司及其下属公司的事务有决定权，如果没有他的同意，我不可能顺利借助城投公司下属的建筑公司的资质承建上述工程项目，在工程款支付方面也不可能那么顺利。我送钱给邓强也是为了和他搞好关系，以后可以继续合作，多承接一些工程。”

4) 指向根节点的指针pRootNode(即根节点在文件中的位置)；

5) 指向最小叶节点的指针pMinLeafNode(即最小叶节点在文件中的位置)；

6) 指向最大叶节点的指针pMaxLeafNode(即最大叶节点在文件中的位置)。

文件体保存的是一棵B+树，即B+树包含的所有节点数据。每个节点中的指针表示的是其指向的节点在文件中的位置。

3 系统的组成、工作流程及关键算法

3.1 系统的组织结构

本文提出的态势回放系统由态势数据文件、数据文件对象、航迹点提取器、B+树文件、B+树文件对象、回放控制器、显示组件等几部分组成，系统运行时的组织结构如图2所示。

图2 态势回放系统组织结构图

各组成部分的功能简述如下：

态势数据文件是指由电子信息系统感知并记录的、包含有航迹点数据的二进制文件。由于电子信息系统运行的网络环境可能采取无连接的通信协议，所以不能保证数据文件中航迹点的时间值按存储顺序单调递增。

数据文件对象负责从态势数据文件中将包含航迹点的数据报文按存储顺序读取出来，并将其传输给航迹点提取器。

航迹点提取器负责从数据报文中提取出航迹点。

B+树文件对象是系统的关键组成部分。负责将航迹点写入B+树文件、按回放控制器指定的时间窗从B+树文件中读取航迹点并将其传输给显示组件。

回放控制器是用户与系统进行交互的界面元素，负责创建数据文件对象、航迹点提取器、B+树文件对象、显示组件等运行时内存对象。用户可通过回放控制器界面上的时间控制控件(如滑动控件)控制态势的计算与显示。

显示组件负责态势的计算和显示。

3.2 系统的工作流程

系统的工作流程可以分为两个阶段：第一阶段，从态势数据文件中提取航迹点，形成B+树文件，称作回放文件形成阶段或态势回放预处理阶段；第二阶段，基于回放文件进行态势回放，称作态势回放阶段。两个阶段的工作流程叙述如下(为了简化，未进行出错处理的描述)。

态势回放预处理阶段的工作流程为：

1) 用户通过回放控制器指定态势数据文件名、欲保存的B+树文件名；

2) 回放控制器为态势数据文件创建数据文件对象，并创建航迹点提取器及B+树文件对象；

3) 数据文件对象判断文件读取是否读取完毕，若读取完毕，则转7)；否则，读取一个数据报文；

4) 数据文件对象将读取的数据报文传输给航迹点提取器；

5) 航迹点提取器从数据报文中提取航迹点，并将航迹点传输给B+树文件对象；

6) B+树文件对象将航迹点写入B+树文件；转步骤3)；

7) 销毁创建的内存对象，态势回放预处理工作完成。

态势回放阶段的工作流程为：

1) 用户通过回放控制器指定需要进行回放的B+树文件名；

2) 回放控制器为指定的文件创建B+树文件对象；

3) 回放控制器通过B+树文件对象获得态势的起止时间，并设置时间控制控件的范围；

4) 用户通过回放控制器，设置时间窗的宽度及起止时间；

5) B+树文件对象根据时间窗的起止时间，将B+树中在时间窗内的航迹点传输给显示组件；

6) 显示组件基于接收到的航迹点集合进行态势计算(航迹形成算法详见4.2节)和态势显示。

4 关键算法

4.1 航迹点批量插入算法

为了提高态势回放预处理阶段的工作效率，设计并实现了航迹点批量插入算法。该算法在B+树文件对象中实现，用于态势回放预处理阶段的步骤6)。具体描述如下：

算法1航迹点批量插入算法

输入：航迹点集合P。

输出：将P中的航迹点插入B+树文件。

Step1将P中的航迹点按从小到大顺序进行排序，形成有序航迹点集合PT。

Step2将PT整批插入B+树文件中。对于非叶节点，利用节点上的航迹点将PT划分为若干有序子集，把各子集插入该节点的相应子节点；对于叶节点，则将该节点中的航迹点和待插入的航迹点合并排序，形成临时节点。

Step3若临时节点中包含的航迹点个数NL不大于B+树的阶数M，则将临时节点写入文件，完成节点更新；否则，将临时节点分裂为NL/M个节点，并把这些节点的指针和最小关键字插入父节点；若父节点需要分裂，则继续向上分裂，直到无需分裂为止。

Step4根据更新节点及新建节点的情况，修改B+树文件头。

该算法在一般情况下，相对于每次只插入一个航迹点的算法，可大大提高系统的性能，缩短回放预处理的时间。算法性能的具体分析请参阅文献[20]。

4.2 航迹形成算法

为了有效地将某个时间窗内的航迹点集合形成航迹集合(即态势帧)，本文提出了基于航迹表的航迹形成算法，描述如下：

算法2航迹形成算法

输入：航迹点集合P。

输出：航迹表TR。

Step1初始化TR为空。

Step2顺序扫描P中的所有航迹点pi(i=0,1,…,N-1)，N为P中元素的个数。

Step3将TR中的航迹与pi进行匹配。若匹配不成功，则新建一个航迹tr，插入航迹表TR中；若某个航迹tr与pi匹配成功，则使用pi的信息修改pi，比如将航迹长度加1、更改航迹的终止时间、使用pi代替最后一个航迹点等。

航迹形成算法在显示组件中实现。该算法空间复杂度为O(N)，时间复杂度在一般情况下为O(N2)，若对航迹表中的元素进行排序，则时间复杂度可改善为O(Nlog2N)。

5 系统实现及实验

5.1 运行环境

在通用的个人台式计算机上，使用Visual Studio 2010的C++语言对系统进行了实现(背景地图使用第三方软件)。

台式计算机的详细配置信息为如下：

台式计算机型号：Dell XPS 8300。

操作系统：Windows XP Professional with SP3。

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

内存：4 GB，南亚易胜DDR3，1.333 GHz。

硬盘：西部数据WDC WD10EALX-759BA1，容量1 TB，每分钟7 200转。

显卡：独立显卡，ATI Radeon HD 6700 Series。

5.2 系统性能评价指标

为了对态势回放系统的性能进行评价，本文提出了绘点数据率的概念，即一帧态势所含的航迹点数与绘制该帧态势的核心代码运行所需时间的比值，单位为点/s。绘制一帧态势的核心代码完成的功能主要包括：(1) B+树文件对象根据时间控制器给定的时间窗起止时间，从B+树的根节点(驻留在硬盘上)到叶节点进行搜索，找到起始时间对应的叶节点的位置；(2) 从起始时间对应的叶节点开始，到终止时间对应的叶节点为止，顺序访问各叶节点中的在起止时间范围内的航迹点，并将这些航迹点传输给显示组件进行态势计算和显示。

5.3 系统运行实验

系统运行时，将B+树文件的阶数设置为256，航迹点批量插入算法的航迹点集合的个数设置为1 024，即在B+树文件的形成过程中，每次最多向其中插入1 024个航迹点。态势回放时时间窗宽度为100 s。

系统运行的图形界面如图3所示，用户可通过态势回放控制器上的滑动条控件改变时间窗的起止时间，实现态势动态显示。

图3 态势回放系统运行界面图

态势回放预处理阶段，对某大型电子信息系统在某年运行过程中记录的态势数据文件集进行处理，形成B+树文件，B+树文件中的航迹点个数超过1.2亿(具体数字为126 259 363)。

态势回放阶段，绘点数据率约为20万点/s，即每一秒可完成约20万个航迹点及航迹点连线的绘制。假设一条航迹的长度为1 000点，则一秒内可完成约2 000条航迹的绘制。该结果表明本文提出的态势回放系统具有较高的性能。

6 结 语

本文首先对与态势回放相关的概念和术语进行了形式化定义；然后描述了系统的组织架构、工作流程及关键算法；最后提出了绘点数据率的概念用于衡量系统的运行性能，实验结果显示了系统进行态势回放的高效性。

在该系统的基础上，拟继续在以下几个方面开展下一步的研究工作：

(1) 优化内部组件。对大数据索引技术进行研究和开发，以提高数据存储组件的空间利用率和查找效率。

(2) 拓展新的应用方向。比如接入通信网络，在线实时接收态势数据进行存储和回放；可通过对数据存储组件的并发访问控制技术的研发进行实现。

(3) 作为算法研究和实验的平台。可将航迹融合、目标识别等算法集成到回放系统中，对算法的执行效果进行检验和评估，以促进相关算法的研究和改善。