1.引 言

Google Earth、天地图、OpenStreetMap等网络化地理信息服务系统均提供了在线标注功能，所标注的兴趣点等信息汇集到后台处理中心，进行统一处理与使用[1-2]。目前基础地理信息的动态更新正尝试采用这种方式，构建网络化变化信息标注和报送（简称标报）系统，以实现基于更新网格的变化信息标注、多级有序传递与检核和跨部门、跨地区的现势信息资源共享[3-4]。这种网络化信息标报不同于传统的在线标注，具有内容时空化、传递多层级等特点，对相应的发布/订阅模式提出了新的要求。

发布订阅模式是广域网络中异构应用实体之间的异步、多对多和松耦合的通信模型和交互机制[5]。目前主要是发布事件的名称、类型等属性信息，采用结构化方式表达订阅条件，通过事件匹配，将所满足条件的信息主动传递给感兴趣的订阅者[6]。目前的研究热点主要包括事件语义描述、内容订阅表达、高效匹配算法等，以满足大规模分布式计算的松耦通信需要[7-8]。对地理空间信息的发布订阅来说，曾有学者做过初步的探讨[9-10]，例如文献10针对LBS服务需要，在事件发布时加入了移动设备的空间位置信息，通过R-Tree索引实现基于空间订阅条件的事件匹配[11]。但其仅考虑了点状目标的位置信息和“Within”、“Distance”两种简单空间关系，尚未顾及复杂空间目标及关系的发布与订阅。另一方面，信息传递通过事件匹配和路由算法，在事件代理网络中将发布事件转发给相关的订阅者，但仅限于本簇同级节点之间的传递，没有考虑节点之间可能存在的层级关系，无法进行簇内多级订阅。而对于大规模分布式计算而言，其事件代理网络往往有多个分簇组成，各分簇的信息向总节点传递，但极少顾及分簇之间的跨簇订阅。

为了解决上述问题，本文将空间变化和节点层级纳入事件发布内容，通过构造变化信息标报的内容描述模型、时空订阅条件表达、顾及层级的事件代理网络，以及基于多维索引计数的事件匹配算法，提出了一种顾及有序传递的空间变化标报信息发布订阅模型。

2.顾及层级关系的标报事件表达

发布订阅模型中，发布的信息内容被称为事件[5]。标报事件用多个 “事件头”与“事件体”（即事件内容）的形式进行描述。其中，层级是标报事件中一项重要内容，层级描述的目的是通过标报部门间的从属关系（如“省-市-县”），找出其潜在的层次关系，以满足标报中对层级的需求。然而以前发布/订阅中的事件描述主要考虑结构化的属性信息的描述[7]，无法直接对标报层级间的层次关系表达，不能满足标报发布中的层级的信息描述要求。

语义web在关系表达和转换方面具有优势[15-16]，可以通过对层次关系的语义描述，对发布中的事件属性进行层次语义转换，解决标报事件的层级表达问题。对如式（1）所示的事件e的每个属性名ai和属性值vi进行层次关系语义信息查询，事件ai查询层次关系语义信息的算法如下：

输入：事件

步骤１：i←1；

步骤２：计算ai的哈希值（如图1中的属性A、B、D），由哈希值得到其在层次关系语义列表中的位置（hier_list1中分别找出A、B，hier_list2中找出D），输出列表中从ai所在的下个位置直至表尾的值；

步骤３：i←i+1，若1≤i≤n，进入步骤２，继续查找输出，否则，算法结束。

查询的结果为，，由层次关系转换得到的层次事件结果如下

  （1）

其中，。

图1 层次关系语义信息描述

式（1）即为具有层级关系的标报事件表达式，能够描述具有空间变化和传递层级特征的标报事件发布内容，它为后面的顾及空间和层级的订阅条件扩展以及发布订阅模型构建提供了必要的基础。

3.订阅条件的时空扩展

针对前面所述的面向发布的标报事件，用户需要从中查找感兴趣的内容，而订阅条件表达的实质就是描述对发布事件的订阅兴趣。变化标报中存在时间和空间的订阅需求，因此，本节对能够描述时空特征的订阅条件进行了详细分析。

基于上节中对标报事件的“属性-值”描述，订阅中也应有标报事件的属性，以及属性的取值范围，订阅条件可用如下表达式形式化描述[7]：

（2）

其中，ai表示属性变量；opj表示操作符，opj∈{<,＝,≠,>,∈,LIKE}；cj是订阅取值，为常量。

下面将验证式（2）在变化标报中的应用。例如，要进行PS1(39.945,116.343)范围内1km（即与PS1距离小于1km）的订阅表达，由于式（2）不能描述距离关系，因此无法将其直接应用到空间订阅中。究其原因，式（2）为结构化订阅表达，其中的订阅变量ai和cj都无法进行距离关系表达式扩展。因此需要引入能够表达时空特征的订阅变量，对式（2）所示的订阅条件进行时空扩展。

3.1时空订阅变量的引入

在以往GIS研究中，时空关系主要包括时间关系和空间关系，其中空间关系包括拓扑关系、方向关系和距离关系[14]。本文分别设、、、和为发布（P）和订阅（S）间相应的时刻关系、时段关系、拓扑关系、方向关系和距离关系，作为订阅变量的时空关系表达式，用ASTj表示。时空订阅取值用CSTj表示，采用当前学术界应用较广泛的研究成果，如时间关系应用Allen[17]提出的13种关系，拓扑关系应用Randell[18]等人的RCC法中描述的8种关系，方向关系采用Frank[19]描述的8种关系，距离关系采用N-ary方法[20]（即相关实体的位置属性来得到），它们的取值分别用TIMEINSTANT-R，TIMEPERIOD-R，TOPOLOGY、DIRECTION和DISTANCE表示。时空操作符用OPj表示，OPj∈{>,＝,<}。ASTj与CSTj对应的取值如式（3）所示。

（3）

在引入了时空订阅变量ASTj、OPj和CSTj后，对式（3）进行了时空扩展，形成了如下所示时空订阅条件描述：

  （4）

应用式（4），可以对标报信息的订阅条件进行如下表示。例如本节中的订阅实例：S1=(Dis(PS1),<,1km)，指的是订阅点PS1(39.945,116.343)与要匹配的变化信息（事件）发布点之间距离小于1km的订阅； S2=(Ts,>, 2011-06-22)表示发生是在时间点“2011-06-22”后的订阅；拓扑关系订阅实例：S3=(Tp(Feature1),=,”Meet”)表示与空间要素“Feature1”拓扑关系为“Meet”的订阅。

3.2订阅操作符的扩展

为了使订阅者能够更加方便地定义其订阅条件，订阅操作符Operator选用“<、=、>”三种，其他操作符可以通过运算语义进行扩展。分析可知，时间和属性订阅只需经过Operator的同义关系运算即可，空间订阅则需要经过表达式关系运算，才能实现发布订阅间的属性对应。下面分别对同义关系和表达式关系运算描述和转换进行概述。

1）同义关系运算

订阅中的同义关系运算是指不同的数据类型运算符，只要其运算所表达的语义外延一致，就互为同义关系。例如，“>”与字符串运算符中“包含”同义。

订阅的同义关系运算语义转换过程形式化描述如下：订阅中的ai为变量，对s中的每个操作符opi查询同义关系运算语义信息，查询结果为核心操作符key_opi，得到同义订阅。

2）表达式关系运算

如果订阅条件中有一个属性a1，a1为关系表达式，而事件中有属性a2，且a1经过运算语义转换后为a2 的祖先，则这两者可以匹配，称此时的运算语义为表达式关系运算。

订阅的表达式关系运算语义转换过程形式化描述如下：设订阅，事件。根据s中ai的关系表达式，对事件e的每个属性名aj进行层次关系运算语义信息查询，查询的结果为，由层次关系运算转换得到的订阅。表达式关系运算语义转换过程中的层次关系运算语义信息查询方法采用上节所示的查询方法来实现。

因此，通过前面引入时空订阅变量，并对订阅表达式和订阅取值的时空扩展描述，以及本节中的订阅操作符的层级扩展，应用式（5）可满足变化标报中顾及时空和层级的订阅条件的描述需求。

4.顾及层级的时空发布订阅模型

基于上面的讨论结果，可以构建时空发布订阅模型。模型中的事件和订阅是通过事件代理网络来实现和维护[7]。然而，以往的事件代理网络未考虑节点间存在的层级关系，无法满足变化标报中信息多级有序传递需求。因此，本节对顾及层级的事件代理网络及其网络中的信息传递算法进行分析研究。

4.1 顾及层级的事件代理网络

    发布订阅模型由事件代理网络来维护其事件和订阅，发布者和订阅者同网络中的某个事件代理相连，通过连接的代理发布事件或订阅，事件代理负责事件的匹配与分发，以及订阅条件的路由。模型需要根据事件内容，在网络中寻找一条恰当的路径，使事件低成本、高效和可靠地到达各相关的订阅者，即路由转发问题。订阅要从代理中一步步转发到发布代理；而事件则根据订阅条件一步步转发到给相应订阅需求的代理[7]。事件代理网络及其路由转发的定义如下：

（1）;

（2）Forward(Bi, ej);

其中，Bi表示事件代理，ej表示事件，V={B1, B2, …}表示网络中事件代理的集合，Bin表示事件来源的事件代理，Rc为当前事件代理的路由表，（S, B）是Rc中的路由表项，S是订阅条件，Forward (Bi, ej)表示把事件ej发送到事件代理Bi；表示e与订阅条件S匹配。

为了解决网络中的跨级订阅和传递问题，本节设计了顾及层级的事件代理网络，并将空间变化和标报层级引入到原有的发布订阅中，构建了一种时空发布订阅模型（如图2所示），以满足标报的有序传递需求。模型中，通过对标报事件的形式化描述和标报层级关系转换，实现标报信息的内容发布，解决标报中的层级问题；通过引入时空条件和web语义对订阅表达式扩展，实现了时空订阅。

图2 基于层级事件代理网络的时空发布订阅模型

有了上面的发布订阅模型，对于订阅需求，就可采用事件匹配使事件有序地传递给相关的订阅者。因此，模型还需对多级发布与时空订阅间的事件匹配算法进行研究。

4.2基于多维索引计数的事件匹配

事件匹配的本质是属性值的谓词比较，主要有暴力匹配法、匹配树、计数法等[21]。考虑到标报中时空和多级的特点，本文采用多维索引计数算法进行事件匹配，其思路如图3所示：首先对发布事件进行层次关系语义转换，对标报发布信息中的层级事件进行分解，包含时空关系的订阅条件进行运算语义转换，经过语义转换后的事件信息和订阅条件进入匹配模块；事件匹配利用了多维索引技术，首先对订阅约束、谓词条件建立多层索引，提高查询效率，最后应用计数算法思想根据约束匹配的计数结果来判断订阅匹配状态。

图3 多维索引计数的事件匹配

5.在更新标报中的应用试验

5.1 系统及算法设计

为了验证提出的模型和方法，本课题组以Visual Studio 2010为开发工具，集成Google Maps API，设计实现了更新标报系统中的发布订阅模块。时空发布订阅算法主要的数据结构如图4所示。首先将每个订阅分解为约束, 去除其重复部分, 组成一个多维索引结构，按照其属性名称（name）、操作符（operator）、约束（constraint）逐级建立索引（如图4（1）所示）。为了保持约束和订阅之间的隶属关系，建立了一个约束-订阅映射链表结构(constraint-subs link) (如图4（2）)，每个约束指向一个链表，该链表存储了所有包含此约束的订阅标识。另外为了使用计数算法，本文建立了一个订阅表（如图4（3）），它以订阅标识作为键（key），存储每个订阅所包含的约束的个数（称为目标值），以及当前匹配过程中每个订阅已被满足的约束的个数（称为计数值），当订阅的计数值和目标值相等就说明该订阅匹配成功。

（1）多维索引结构        （2） 约束-订阅映射链表    （3）订阅结构

图4 事件匹配的数据结构

算法借鉴了文档匹配中的计数算法思想[10]，从第一阶段得到的集合中选择那些其所有约束都被满足的订阅，就得到了最终结果。下面是其的详细步骤：第一阶段对事件的每个属性，根据其类型及其所支持的比较符， 查找匹配的约束；当比较符是比较运算符或者逻辑运算符，如“=”、“<”、“>”时, 直接通过哈希表查找；对于空间和时间表达式，如“Tp”、“Dis”，需要首先计算空间和时间约束，如式（1），继而从列表CL中查找匹配的约束；然后根据约束-订阅映射链表查找到该约束所属于的订阅链表中的订阅，标记该约束匹配的结果。算法复杂度为：，其中︱e︱代表事件e的属性个数,︱opi︱代表e的第i个属性的类型Ti所支持的比较符的个数，searchij代表在约束列表中的搜索代价。在第二阶段，对于每个匹配成功的约束查找其隶属的订阅，给订阅的计数值加1，如果订阅的计数值和目标值相等，则订阅匹配。算法复杂度为，是第一阶段得到的匹配约束的个数，Nc代表匹配成功的订阅所包含约束的平均个数，是比较和归并的代价。

5.2 系统实现

图5 为基于本文模型和方法的地形要素变化信息标报中发布订阅典型应用图示。图7中“标报信息地图可视化”是用户发布的空间事件在地图中的显示；图7中显示了两种订阅方式实例，其中，“属性订阅”是对标报中属性相关信息的订阅，比如“变化类型”、“部门层级”、“标报用户”、“兴趣点名称”等；“空间订阅”是对标报中空间相关信息的订阅，图中实现了某标报点（39.947968,116.347628）1km范围内标报信息的订阅，订阅表达式为 “S1=(Dis(“39.947968,116.347628”),<,1km)”，事件匹配过程中需要计算Dis（P, “39.947968,116.347628”）的值，计算结果小于1km的标报符合订阅条件；“订阅列表”是订阅文件在IE浏览器中的显示列表，当有符合属性和空间订阅条件的事件发布时，“订阅列表”中某条订阅会按照事先设置好的时间定时更新，点击新的更新可进入图７中“标报信息地图可视化”界面，进行事件查看。

图5 地形要素变化信息标报系统中的发布订阅实现图

    从实验结果可以看出，应用本文提出的时空发布订阅模型，发布的标报信息能够在地图上可视化显示，并且可以进行图属查询和编辑；订阅方面，不仅能够实现诸如“变化类型”等属性订阅，还能完成不同级别（如市级、县级）用户间的跨层订阅，同时，也实现了包括时间和空间条件的订阅，较好的满足了更新标报对发布订阅在时空和层级方面的需求。

6.结束语

针对网络环境下标报信息有序传递的需求，以及当前发布订阅（Pub／Sub）未考虑时空变化和层级特征等问题，本文在信息描述方面考虑了变化标报特征，提出了面向发布的标报内容描述模型；引入时空订阅变量和运算语义对传统订阅表达式进行扩展，实现了订阅中的时空特征表达；构建了顾及层级的事件代理网络，基于多维索引计数思想完成了发布信息与订阅条件的匹配，从而提出了一种顾及层级和时空特征的发布订阅模型。

研究表明，本文所提出的模型和方法为发布订阅技术为相关GIS的设计与开发提供了一条新的思路，能够满足网络化更新标报所具有的时空、层级等特点对发布订阅模式提出的新需求。下一步的工作是针对复合事件和复合订阅等复杂情况下，如何扩展表达发布订阅模型，及其匹配算法的优化等。还要继续完善顾及时空信息的发布订阅模型，为这类应用系统开发和工程化应用提供技术支撑。

参考文献

[1] M. Haklay,A. Singleton,C. Parker. Web Mapping 2.0: The Neogeography of the GeoWeb. Geography Compass, 2008, 2(6): 2011–2039

[2] Elwood, S.. Grassroots groups as stakeholders in spatial data infrastructures: Challenges and opportunities for local data development and sharing. International Journal of Geographic Information Science, 2007(22): 71–90.

[3] 王家耀,孙庆辉,吴明光,成毅.面向智能空间信息服务的网格GIS节点构建[J].武汉大学学报(信息科学版),2009(1):1-6

[4] 邢汉发.面向更新的网络化空间标报模型研究[J].测绘学报,2014,43(8):880

[5] 马建刚,黄涛,汪锦岭,徐罡,叶丹.面向大规模分布式计算发布订阅系统核心技术[J]. 软件学报, 2006,(01) :134-147

[6] 胡昔祥.面向大规模分布式计算的发布/订阅系统[J].浙江大学学报(工学版), 2008,(05):736-741

[7] 薛小平,张思东.基于内容的发布订阅系统路由算法[J].电子学报.2008(5):953-960

[8] 朱金奇,刘明,龚海刚,陈贵海,许富龙,宋超.延迟容忍传感器网络中面向发布/订阅系统的事件传输.软件学报,2010,21(8):1954-1967

[9] Bauer M, Rothermel K. Towards the observation of spatial events in distributed location-aware systems", Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops, 2002, pp. 581-582

[10] Aasman J. Unification of Geospatial Reasoning Temporal Logic Social Network Analysis in Event-Based Systems. DEBS 2008, July 1-4, Rome, Italy

[11] Chen, X., Chen, Y. & Rao, F. (2003) "An efficient spatial publish/subscribe system for intelligent location-based services", Proceedings of the 2nd international Workshop on Distributed Event-Based Systems, San Diego, California, June 08, 2003

[12] 陈军,林艳,刘万增,周晓光.面向更新的空间目标快照差分类与形式化描述[J],测绘学报,2012 (2):108-114.

[13] 邢汉发,陈军,李长辉,周晓光.参数化的空间实体变化分类方法[J].中南大学学报(自然科学版),2014,45(2):495-500.

[14] Zhou X G, Chen J, Zhan F B, et al. A Euler number-based topological computation model for land parcel database updating[J]. International Journal of Geographical Information Science, 2013 (ahead-of-print): 1-23

[15] 汪锦岭,金蓓弘,李京,邵丹华.基于本体的发布/订阅系统的数据模型和匹配算法[J].软件学报, 2005,(09):253-259

[16] 李德仁,崔巍.地理本体与空间信息多级网格[J].测绘学报,2006(5):143-148.

[17] J. F. Allen. Maintaining Knowledge About Temporal Intervals. Communications of the ACM.1983(26):832-843.

[18] D. Randell, Z. Cui, and A. Cohn. A Spatial Logic Based on Regions and Connection". In Proc. 3rd Int. Conf. on Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo , 1992:165-176

[19] A. Frank. Qualitative Spatial Reasoning: Cardinal Directions as an Example. In International Journal of Geographic Information Systems. 1996 (3):269-290

[20] N. Noy and B. Rector. Defining N-ary Relations on the Semantic Web. W3C Working Group Note 12, April 2006

[21] 薛涛,冯博琴,李波,董剑.基于内容的发布订阅系统中快速匹配算法的研究[J].小型微型计算机系统, 2006,(03):529-533