基于订阅匹配树的发布订阅系统高效内容匹配的关键技术研究

Publish/Subscribe system based on content is often applied in a distributed environment, and the system must resolve the problem of efficient content matching. The efficiency of matching structure and algorithm is the key issue for content publish/subscribe systems.The main research of this proposal is designing a efficient subscription match tree structure(Submatree) and framework(DISCOPS) for distributed content publish/subscribe sysems. In this framework, we model a predicate in each subscription filter as an interval and published content value as a data point. Given the model, matching content value against predicates can be seen as a stabbing query of point against inteals and reducing the complexcity of matching operation. Based on the Submatree, we will research the interval division and Submatree maintaining which is based on cost model.Using the subscrition match tree and the associated techniques which we proposed, we can construct a efficient distribued content Publish/Subscribe system which can significantly outperform two counterpart with low cost and fast forwarding.

基于内容的发布订阅系统已广泛地应用于开发大规模分布式系统，高效的基于内容的发布订阅系统必须要解决高效的匹配问题，在这种系统中匹配结构和匹配算法的设计是一个关键问题。本课题的主要研究工作是：针对基于内容的发布订阅系统如何设计一种高效的匹配树结构- - 订阅匹配树（Submatree），将订阅过滤器中的一个谓词建模为一个区间间隔，将发布的事件值建模为一个数据点,用订阅匹配树索引所有的订阅间隔，从而将发布内容与订阅过滤器中谓词的匹配问题转换成一个数据点在区间上的刺查询问题，降低匹配操作的复杂度；基于订阅匹配树，进一步研究基于成本模型的间隔划分和Submatree的合并等算法，构建一个高效的基于内容的分布式发布订阅系统架构- - DISCOPS，使该系统架构具有较高的匹配效率，较少的网络通信流量和较低的传输延迟。

匹配结构和匹配算法的设计是实现高效的基于内容的发布订阅系统时需要解决的关键问题，本课题主要进行分布式发布订阅系统中高效内容匹配的关键技术研究，包括匹配树结构的设计与构建、订阅区间的划分、匹配算法以及基于内容的分布式发布订阅系统架构的设计等。主要研究成果包括：. 1）针对分布式环境，本课题从数据模型、基本订阅匹配结构、订阅过程和发布过程四个组成部分定义了一个能够进行高效内容匹配的基于内容的发布订阅系统架构—DISCOPS。该系统架构能够将发布者所发布的内容和订阅者所指定的选择谓词进行高效匹配，并能减少网络通信流量，保持较低的传输延迟。. 2）在DISCOPS中，我们把消息组织成若干个<属性，值>对，把订阅者针对事件属性指定的选择谓词作为订阅过滤器，将订阅过滤器中的每一个谓词建模成一个区间间隔，而将事件值建模成一个数据点。然后，将属性Ai上的所有订阅间隔部署在本课题提出的一棵平衡四叉树的订阅匹配结构（QuTREE）,从而将发布内容与订阅过滤器中谓词的匹配问题转换成判断一个数据点是否在区间上的问题，进而简化匹配操作的复杂度，提高匹配效率。. 3）为了解决QuTREE上注册较长的订阅间隔导致出现非平衡工作负荷和超负荷的节点问题，本课题实现了一种基于黄金分割法的订阅间隔树区间划分算法(IDAGSM) ，从而能有效的平衡开销，避免节点超载。. 4）在DISCOPS中，如果为每一个属性构建一棵QuTREE，会导致更多的内容拷贝，增加网络流量；如果仅构建一棵多维QuTREE，又会遇到 “维灾”问题。为了控制系统构建订阅匹配树QuTREE的数量，降低实现复杂度，本课题设计实现了一个QuTREE合并机制。. 5）为了能较好的解决分布式发布订阅系统中节点在移动网络环境下信息传递的问题，本课题还提出了一种基于辐射社区的机会网络模型，并实现了一种基于辐射社区的分组转发算法。. 以面向分布式环境构建高效的基于内容的发布订阅系统为目标，研究如何构建一个高效的CBPS系统框架，实现快速匹配算法，减少网络通信流量等的成果，具有一定的理论和实际意义。.