刘晓宏，雷伟斌，刘国永，孙 娟，左钦文

（1.国营第七八五厂，太原 030024；2.北方自动控制技术研究所，太原 030006；3.军事科学院防化研究院，北京 102205）

0 引言

发布/订阅系统是一种使信息生产者和信息消费者以匿名方式进行交互的中间系统。基于内容的发布/订阅模式，与基于主题的发布/订阅模式相比，拥有更强的信息需求表达能力，因此，可以为战场信息分发系统提供更为精准和高效的信息共享能力。事件与订阅的匹配算法是基于内容的发布/订阅系统中重要的研究内容之一。事件的匹配效率，不仅决定了系统的实时性是否能够得到满足，还制约着整个系统的可扩展性［1］，因此，也决定了基于内容的发布/订阅模式在战场信息分发系统中应用的可行性。目前，事件与订阅的高效精确匹配算法已有较多的研究成果［1-3］，但均未考虑用户信息需求与订阅的模糊性问题，因此，并不适合直接应用于战场信息分发系统中。文献［4］研究了在固定的树形拓扑网络中，如何利用订阅约束间的逻辑覆盖关系来减少订阅的转发数量并降低路由节点中维护的订阅数据的规模，但该方法无法适用于战场上动态的无线网络拓扑结构。

本文结合战场应用环境的特点，对基于内容的战场信息分发系统中的高效模糊匹配算法进行研究，充分考虑战场上作战用户对信息需求认识与表达的主观性和模糊性［5］，将模糊集合理论应用于战场信息与用户订阅信息的匹配过程中，以提高匹配结果的合理性，从而保证战场信息分发共享的合理性，并对提高模糊匹配算法效率，降低订阅信息维护成本的方法进行研究，提出一种订阅信息的高效组织模式，即分段完全逻辑覆盖模式，并通过仿真实验对其效率进行验证。

1 基于内容的战场信息分发系统

1.1 战场信息分发系统的概念

以基于内容的发布/订阅技术为基础的战场信息分发系统是一种使发布者和订阅者以匿名方式进行战场信息共享的分布式系统。它由接入战术网络的信息分发代理服务器及客户端组成。每个服务器是一个代理信息分发的节点，每个代理服务器节点为一定数量的本地客户端提供服务，所有分发代理节点形成一个分布式的拓扑结构，如图1 所示。战场信息分发系统是发布/订阅技术在军事上的一个典型应用，同样具有异步、松耦合、透明传输的特点［6］。基于发布/订阅的战场信息分发模式适用需求广泛，但需求用户又不明确的战场信息精准分发共享，如战场通用情报、气象情报、工程情报等战场情报信息以及部分战场态势信息。

图1 战场信息分发系统拓扑示意图

1.2 战场信息分发的流程

战场信息分发的流程如图1 所示，首先作战用户根据自身的信息需求通过订阅客户端向所在的信息分发代理服务器进行订阅，即图1 中的流程①。为保证发布的信息能够准确、及时地分发给相应的订阅用户，各分发代理服务器会实时地同步用户的订阅信息，即流程②。流程③是用户通过发布客户端进行战场信息（事件）发布的过程。流程④是分发代理服务器将用户订阅与事件进行匹配的过程。流程⑤是事件与部分用户订阅匹配成功后，向其进行分发的过程。

由于战场网络多为由无线连接的动态网络，其拓扑结构会随着各网络节点位置的变化而产生变化，因此，无法使用文献［4］中利用订阅约束间的覆盖关系来减少订阅转发数量的订阅路由方法。战场信息分发系统可采用简单路由方法［7］，通过在分发代理网络中广播新增、变更和注销的订阅信息，使得所有代理节点都同步维护着所有用户的订阅信息，因此，发布的事件仅需在其本地的分发代理服务器与用户订阅进行匹配，然后再分发给匹配成功的订阅用户。简单路由方法对网络带宽资源的占用相对较少，但订阅信息的维护成本相对较高，因此，订阅信息的组织模式及维护策略将更加重要，本文将设计一种高效的订阅信息组织模式来解决该问题。

1.3 基于内容的战场信息分发系统模型

要实现基于内容的发布/订阅系统，首先要明确系统的事件模型和订阅模型。不同种类的战场信息，其内容差异较大，若建立统一的战场信息描述模型，事件模型将过于复杂，且存在过多冗余信息。这样的事件模型并不利于提高事件与订阅的匹配效率，因此，可以采用目前的数字化部队标准中定义的格式化数据报文作为系统的事件模型。用户可订阅的内容属性为某一战场信息所有内容属性的一个子集，可采用XML 语言进行组织。基于内容的战场信息分发系统模型如图2 所示。

2 高效模糊匹配算法设计

目前基于内容的发布/订阅系统可以根据事件模型的数据组织方式的不同分为两类，基于Map 的和基于XML 的。在基于Map 的发布/订阅系统中，事件的内容为多个“属性=值”的集合，由多个“属性=值”组成的集合为一个Map，较有影响的原型系统包括Gryphon、SIENA、JEDI 和Rebeca 等［7］。本文中的战场信息分发系统本质上是一个基于Map的发布/订阅系统。在图2 所示的信息分发代理服务器中，格式化报文解码后被处理为多个“属性-值”对的集合，例如（高度3 000 m）。包含用户订阅信息的XML 文档被解析为多个订阅约束的集合Sub={C1，C2…Cn}，订阅约束Ci用一个三元组表示为（属性，谓词，值），例如（高度，≥，500 m）［8］。

图2 基于内容的战场信息分发系统模型

2.1 模糊匹配算法的概念与流程

目前，发布/订阅系统所采用的匹配算法均为严格的精确匹配，即一个事件要么满足一个订阅，要么不满足该订阅。而战场上，作战用户对客观信息需求的认识有很大的主观性，并且信息需求的表达方式也存在一定的限制，因此，用户所表达出的信息需求是模糊的、不精确的。针对该特点，本文设计了一种使匹配更加合理的模糊匹配算法。

模糊匹配算法的基本思想是将用户对某信息内容属性的主观需求看作一个模糊集，而每种战场信息中包含若干可订阅的内容属性，因此，用户对某战场信息的需求是多个模糊集的集合。各模糊集的分布形式根据内容属性的特点并结合专家经验来确定，隶属函数的参数通过用户的实际订阅来确定。事件与订阅的匹配是事件中的多个内容属性与订阅中多个对应的订阅约束的匹配。当有战场信息发布时，通过计算该事件与对应的多个模糊集的隶属度来确定事件是否与用户的订阅匹配成功。在精确匹配算法中，若存在一对事件内容属性与订阅约束匹配失败，则整个事件与订阅的匹配将被判定为匹配失败，而在模糊匹配算法中，部分事件内容属性与订阅约束的匹配结果不会决定整个事件和订阅的匹配结果，而需要综合所有订阅约束与事件内容属性的匹配结果来进行综合判定。

在某战场信息中，不同的内容属性对某一用户来说其重要程度是不同的，如空中目标信息，目标的位置信息要比目标的航向重要，目标的航向要比目标的速度、高度重要，因此，在模糊匹配过程中，不同内容属性的隶属度对整个事件与订阅匹配度的影响程度也是不一样的。内容属性对用户的重要性越大，其在事件与订阅的匹配中所起的作用也应越大，因此，可以先通过层次分析法（AHP）等方法确定某战场信息中各内容属性的相对权重，然后再计算各内容属性隶属度的加权平均数，作为整个事件与用户订阅的匹配度。

综上所述，可将发布的某战场信息与某用户订阅信息的模糊匹配流程总结如下：

1）确定用户订阅中各订阅约束模糊集的隶属函数，设订阅约束Ci的隶属函数为μi（x）；

2）确定该战场信息中各内容属性的权重，设事件中属性Attri的相对权重为ωi；

3）计算事件中各内容属性与对应订阅约束模糊集的隶属度，若事件中内容属性Attri的取值为xi，则Attri在对应订阅约束模糊集中的隶属度为μi（xi）；

4）计算发布事件与该用户订阅的匹配度M；

5）判定发布事件与用户订阅是否匹配成功，若该匹配度M 大于等于用户设定的匹配度阈值M，则可判定事件与该用户的订阅匹配成功，否则就判定为匹配失败。

2.2 高效模糊匹配算法

通过分析发现，上述模糊匹配方法需要逐用户、逐属性地计算事件与所有用户订阅的匹配度，然后才能最终判定出事件与哪些用户的订阅匹配成功。当战场信息分发系统的规模较大，用户的订阅数量较多时，模糊匹配算法的时间效率将大大降低，战场信息分发的及时性将难以保证，因此，需要一种在不降低模糊匹配算法合理性的同时，又能有效提高其匹配效率的方法。

提高匹配效率的一种思路是缩小与事件进行模糊匹配的订阅范围，即通过已有的精确匹配算法快速地筛选出一部分有可能与发布事件匹配成功的用户订阅，只通过模糊匹配算法计算这一小部分订阅信息与发布事件的匹配度。如图3 所示，S0为所有用户的订阅，S2假设为能够与发布事件匹配成功的用户订阅，则集合S1即经精确匹配快速筛选出的用户订阅，只将S1中的订阅与事件进行模糊匹配，这样既保证了匹配的合理性，又提高了匹配的效率。

图3 用户订阅的集合关系

为实现上述快速、精确的匹配，需要将用户的原始订阅进行模糊预处理。在确定了用户订阅约束模糊集的隶属函数后，取某一较小的隶属度数值作为隶属度模糊阈值，将该阈值对应的订阅约束值作为该用户新的订阅约束值进行精确匹配。如图4 所示，设某战场信息中包含内容属性A，由某用户的订阅确定了图中的隶属度函数曲线，某用户对属性A的实际订阅为区间［a，b］。取隶属度0.3 作为模糊阈值，则属性A 的订阅范围经模糊预处理后变为区间［a0，b0］。对所有用户订阅信息的所有可订阅属性进行上述模糊预处理后，再与发布事件进行快速的精确匹配，所得匹配结果即为图4 中的集合S1。

图4 用户订阅的模糊预处理过程

通过上述分析可知，所有用户订阅均需要和发布事件进行一次精确匹配，才能筛选出一部分用户订阅与发布事件进行模糊匹配，因此，事件与订阅进行精确匹配的效率同样制约着整个模糊匹配算法的效率。提高精确匹配算法效率的基本思路是优化用户订阅信息的组织结构，减少匹配过程中对相同订阅约束的判断次数，以此提高匹配的时间效率［3］。

2.3 订阅约束间的逻辑覆盖关系

不同的用户可能会通过相同的内容属性来订阅同一种战场信息，因此，订阅集合中会存在订阅约束之间的逻辑覆盖关系。例如，用户a 和用户b 均通过高度属性订阅了同一战场信息，其中Cai=（高度，≥，5 000 m），Cbj=（高度，≥，10 000 m），则订阅约束Cai和Cbj之间就存在逻辑上的覆盖关系，即发布事件中的高度属性满足约束Cbj时，就必然满足约束Cai。由于Cbj是Cai成立的充分条件，因此，可以通过设计特定的数据结构，充分利用约束间的逻辑覆盖关系来减少不必要的比较操作。例如，可合并相同的订阅约束并用数组将约束值按大小顺序排列，然后使用二分法进行查找，当找到第一个与事件属性值匹配成功的订阅约束值后，就可以确定所有订阅约束值的匹配结果了。

为利用上述订阅约束间的逻辑覆盖关系，并提高订阅信息的查找效率，建立如图5 所示的多级索引结构，其中关系运算符索引指向的是用户所订阅的信息内容属性约束值［9］。为组织大量的订阅约束值，可考虑的数据结构包括顺序存储结构（如数组、队列），链式存储结构（如链表、二叉树）。

图5 用户订阅信息的数据结构

2.4 匹配算法中订阅信息组织模式的设计

在采用简单事件路由方法的战场信息分发系统中，为提高内容匹配的时间效率并降低订阅信息的维护成本，需要对用户订阅信息的组织模式进行设计［10-14］。以顺序存储结构存储用户订阅信息为例，所有谓词约束均为小于等于约束，则利用约束间的逻辑覆盖关系可以将用户订阅的约束值组织为如图6 所示的3 种形式。图6（a）为简单的逻辑覆盖模式，其中Vi 为按升序排列的约束值，下面对应的Ui 为订阅中约束值是Vi 的用户。当进行匹配时，对Vi 进行二分查找，查找到大于等于属性值Ei 的约束值v 后，对v 后面的用户进行遍历即可得到匹配结果。图6 模式（b）是对图6（a）的改进，将约束值大于等于Vi 的所有用户放到Vi 的用户队列中。当进行匹配时，只需进行二分查找即可得到匹配结果，省去了遍历后面用户的操作，可以有效地提高匹配的时间效率。但这种完全逻辑覆盖模式的空间复杂度极差，空间复杂度为O（n2），并且订阅维护的效率也很低，不具备实用性。

对图6 模式（b）进行改进，得到图6（c）所示的分段完全逻辑覆盖模式。在图6 模式（c）中约束值在整体上是无序的，但在分段区间内是有序的，每个分段区间内部采用完全逻辑覆盖模式。当进行匹配时，对每个区间分别进行二分查找操作，将各个分段区间内的匹配结果合在一起即为最终匹配的结果。这种模式下，设分段空间的大小为N，则匹配的时间复杂度为O（logN*n/N+n）=O（n），空间复杂度为O（1/2（N*（N+1））*（n/N））=O（n），订阅约束值插入的时间复杂度为O（logN+N）=常数阶。采用空值代替的方法，订阅约束值删除操作的时间复杂度也是常数阶。3 种模式的对比如表1 所示。

表1 3 种模式性能对比

图6 小于等于约束中约束值的组织模式

3 实验验证与分析

实验程序所运行的计算机采用Windows XP Professional sp3 操作系统，CPU 为Intel Core Quad Q9400 2.66 GHz，内存为2 G DDR3。实验程序使用C++语言在VC++6.0 上编写。以拥有3 个可订阅属性的某信息作为事件来模拟其发布和订阅的过程，假设订阅约束均为一元谓词约束，并采用vector 容器来组织用户的约束值。订阅约束值由Box-Muller方法产生的符合正态分布的随机数进行模拟。3 个属性的订阅约束值的分布分别为N（500，100），N（1 000，300），N（1 500，500），并以3 个正态分布的均值作为发布的事件，即Event={500，1 000，1 500}。

实验结果如图7～图9 所示，其中3 种模式的匹配效率和订阅维护效率的实验结果如图7 和图8所示，其中模式c 的分段区间N 为1 000。实验所得结果和表1 中时间复杂度的理论分析结果一致，对比可知，模式c 是一种最优方案。在采用简单事件路由方法的战场信息分发系统中，模式c 在保证较高匹配效率的同时，还能够有效控制和降低分发代理节点维护订阅信息的成本。

图7 3 种模式匹配效率对比

图8 3 种模式订阅维护效率对比

图9为采用模式c 的匹配算法中不同的订阅数据规模情况下，分段区间大小N 与匹配时间之间的关系。从曲线变化的规律可以看出是一种负指数函数的规律，且不同的用户规模所对应的最优分段区间大小是不同的，为保证较高的匹配效率，应随着订阅数据规模的增加适当增加分段区间N 的大小。

图9 匹配时间与分段区间大小的关系

模式c 中分段区间N 的取值应根据系统的规模（用户数量、可订阅信息数量和每种信息平均可订阅属性的数量）和信息分发服务器内存的大小来选择合适的值。设订阅用户的数量为n，可订阅的信息的数量为M，信息中平均可订阅的属性数量为A，分段区间大小为N，用户标识Ui 占用的内存大小为T，则该订阅结构占用的内存大小G 满足下式

4 结论

本文首先针对战场信息分发的需求，设计了基于内容的战场信息分发系统模型，然后考虑到战场上作战用户对信息需求认识与表达的主观性和模糊性，利用模糊集理论，并结合精确匹配算法，设计了高效模糊匹配算法的思想与流程，最后为提高匹配算法的时间效率，并降低订阅信息的维护成本，设计了组织订阅信息的分段完全逻辑覆盖模式，并通过实验验证了该模式设计的合理性。该高效模糊匹配算法，能够同时保证战场信息分发系统内容匹配的合理性与高效性，算法中战场信息内容属性的隶属函数的确定等内容有待进一步研究。