基于自组织算法的发布/订阅系统的研究

董 飚

(南京工业职业技术学院 计算机与软件学院，江苏 南京 210023)

基于自组织算法的发布/订阅系统的研究

董 飚

(南京工业职业技术学院 计算机与软件学院，江苏 南京 210023)

通过重组织覆盖网络拓扑结构，提出了一种高效的发布/订阅系统。自组织算法把匹配相同事件的事件代理直接相连来实现重组织拓扑结构。结果表明，由于减少了事件发布过程中的事件代理的数量，从而降低了系统开销。

发布/订阅；覆盖网络；自组织

目前，许多分布式系统采用基于发布/订阅(Publish/Subscribe，简称P/S)的架构。发布者是信息的生产者，订阅者是信息的消费者。事件是信息的载体，发布者产生事件，订阅者消费事件，他们通过订阅语言描述消费的事件类型。发布者和订阅者通常分布在网络不同的节点上，因此P/S系统本质上是由事件代理框架构成的网络，事件代理负责事件的匹配和路由。P/S系统如图1所示。

图1 发布/订阅系统模型

图1中Pi表示发布者，Ci表示订阅者，Bi表示订阅者，虚线矩形表示事件通知服务。事件通知服务充当发布者和订阅者间的媒介，由一组互连的事件代理组成。相邻的事件代理之间通过接口(或称链路)相连，和发布者相连的事件代理称为发布结点，和订阅者相连的事件代理称为订阅结点，其它路由器称为内部结点。发布者从它的发布结点发布事件，订阅结点把通告传递给订阅者。图中Bi分别表示发布结点、订阅结点和内部结点，通常，不予区分，均称之为代理。

P/S系统可以分为两大类：基于主题的P/S系统，如TIB/Rendezvous，SCRIBE和BAYEUX等；基于内容的P/S系统，如SIENA，JEDI，HERMERS，Gryphon和REBECA等[1-3]。基于主题的P/S系统通过一组预先定义的主题来交换信息，每一个主题代表了不同的多对多的逻辑通道。基于内容的P/S系统更适合灵活地订阅相关的信息，每个信息项的组合可以看成一个动态逻辑通道。由于这种系统要建立和维护数量巨大的组播树，因此，实现高效的基于组播树的事件传播是不可行的[4]。目前，基于主题和基于内容的P/S系统都是基于静态环境下的覆盖网络，主要考虑如何设计事件分发算法，避免在事件分发过程中出现泛洪现象[5]。与上述系统相比，本文提出了在动态重组织覆盖网络结构环境下的一个协同、互补的自组织算法，同时把P/S系统重组织的开销控制在一个合理的范围，具体考虑三方面的内容：

ZK13-02-03

(1) 定义两个代理之间的相似度；

(2) 只利用本地代理中的信息，自组织覆盖网络的拓扑结构；

(3) 在不破坏初始网络拓扑结构特性，如带宽、网络延时等度量的同时，把P/S系统重组织的开销控制在一个合理的范围。

1 自组织覆盖网络

本文重组织覆盖网络的基本思想是：在覆盖网络中创建代理聚集。创建代理聚集的依据是在最近的一段未来时间，代理聚集中的代理有相同的订阅目标。在这种情况下，一个事件沿一条路径到各代理，而不是沿多条路径来分发事件到目标代理。

图2所示为P1发布事件e的过程，箭头表示事件e在覆盖网络中发布的方向，有两个订阅者B9和B5订阅事件e。在最小开销的情况下，事件e到达B9和B5共需6跳。

图2 P1发布事件e到B9和B5

图3所示为假设B9和B5属于同一个代理聚集，B9和B5直接相连，事件e到达B9和B5只需3跳。

图3 P1由代理聚集发布事件e

定义1(事件) 事件e由一组属性集合{a1，…，an}组成。其中，属性是一个三元组，type指属性的数据类型，其属于一组预先规定的原始数据类型，可以是一般的编程语言所支持的类型，如int，bool，float，string等简单数据类型，或者是由简单数据类型构成的复合数据类型，如数组、集合等。name是属性的名称，它是一个string类型。value是属性的值，它的值域就是该属性的数据类型所能表示的范围。

定义2(相似度) 对于一段给定的时间，设mi是与代理Bi匹配的最后Qi个事件的一组属性的集合，代理Bi和Bj之间的相似度：

其中SBj是存储在代理Bj上的订阅的集合，M(e，s)表示事件e与订阅s匹配。

ai，j是一个概率，表明一个事件如果与代理Bi的订阅相匹配，那么，该事件与代理Bj的订阅匹配的概率，反之，也成立。当ai，j接近1时，表明几乎所有最后的Qi个事件同时与代理Bj和Bj的订阅相匹配。如果ai，j=0，表明代理Bj和Bj是断开的，或者最后Qi个与代理Bj的订阅匹配的事件不能与代理Bj的订阅匹配。ai，j只与已匹配的过去的事件有相，并且随着事件和订阅的变化而动态调整，不需要先期的知识。

2 自组织算法

代理B的兴趣域是B的订阅表中所有订阅的并集，记为Z(B)。与链接l相连接的所有代理的兴趣域的并集，称为链接l的兴趣域，记为Z(l)。在P/S系统中，当代理Bi通过链接li，j收到一个事件e后，完成两项工作：

(1) 把事件e与其订阅表匹配。

(2) 如果e与Z(li，k)(k≠j)匹配，通过所有li，k(k≠j)向前分发事件e，这确保事件e只经过一些能引导该事件到达订阅该事件的代理的链接。

自组织算法的目标是：设在覆盖网络中两个代理Bi和Bl，它们之间没有直接相连。若Bi到Bl的路径上存在一条链接lp，q，使得ai，l>ap，q，则在Bi和Bl之间建立一条链接li，j，而且，为了保持覆盖网络是无环的结构，自组织算法必须断开链接lp，q。自组织算法分为4个阶段：触发阶段、发现代理阶段、断开链接阶段和修复覆盖网络阶段。

(1) 触发阶段。对于代理Bi的每一条链接，激活条件AC(Bi，j)：ai，j(mi)>ai，j，其中ai，j(mi)是mi中与Z(li，j)匹配的事件数除以Q。用来计算ai，j的集合Z(Bj)是Z(li，j)的子集，能被直接推导，不需要在Bi和Bj之间互换任何消息。代理B每接收到δ个事件，自组织算法被触发执行，代理B检测AC(Bi，j)，如果AC(Bi，j)=false，那么，自组织算法结束运行；否则，代理执行自组织算法的代理发现过程。

(2) 发现代理阶段。设元组(broker_id，weight)，令HS(Bx，By)=<(Bx,0)(Bx+1),w(lx,x+1)),…,(By,w(ly-1,y))>表示连接代理Bx和By的一个跳序列。代理Bi通过它的一条链接发送请求消息DREQ，该消息包括mi的一个HS。由Bi发出的包括DREQ消息的跳序列的初始值是{(Bi，0)}。DREQ消息随着mi的大小和HS的长度增大。

当一个代理Bj在它的一条链接lk，j上接收到DREQ，Bj完成三件工作：①计算ai，j；②在HS中加入(Bj，w(lj，k))；③计算向前分发事件的条件FP：∃lj，h≠lj，k：ai，j(mi)>ai，j。如果FP为真，表示链接lj，h后存在代理，该代理与Bi的相似度大于ai，j，那么，代理Bj把DREQ发送到链接lj，h。如果不存在链接使得FP为真，那么，代理Bj沿着HS的路径返回给Bi一个回答消息DREP。

(3) 断开链接阶段。这一阶段的任务是选择一条用来在修复覆盖网络阶段断开的链接ltd。这阶段的工作过程如下：设DREP是沿着li，j发出的对DREQ消息的回答，该回答消息包含Bl，这里的Bl与Bi有最大的相似度，DREP存储HS(Bi，Bl)。lnew表示在Bi和Bl之间创建的一条链接。如果all=0∧ali=0；不能创建链接lnew，因为Bi和Bl间没有可用的链接。否则，有两种情况：①all>0∧ali>0：表示为Bi和Bl之间有可用的链接，因此，可以在它们之间建立新的链接。②all=0∧ali>0(或者all>0∧ali=0)；ltd是Bl-1与Bl之间的链接(ltd是Bi与Bi+1之间的链接)。

(4) 修复覆盖网络阶段。设lnew=li，j，ltd=lp，q，为了避免网络被划分，或者变成有环的结构，必须确保在断开ltd时，HS(Bi，Bl)中的其他链接不被断开。我们用锁机制来实现：Bi沿着朝向Bl的路径上的代理发一条LOCK消息，这条路径上的代理B执行下面的算法：

① 当通过链接l接到一条LOCK消息。分三种情况：如果l没有锁，并且B≠Bl，则锁住l，并且把LOCK消息分发到指向Bl的路径上的下一个代理。如果l没有锁，并且B=Bl，则锁住l，并且把ACK消息分发到指向Bl的路径上的下一个代理。如果l被锁，或者Bl经过HS(Bi，Bl)不再可达，则向Bi发送NACK消息。

② 当接收到一条ACK消息。B向指向Bl的路径上的下一个代理发送ACK消息。

③ 当接收到一条NACK消息。分两种情况：如果B≠Bl，在这条链接上移除LOCK，并且向指向Bl的路径上的下一个代理发送NACK消息。如果B=Bl，则停止自组织算法。

3 仿真实验

仿真实验估计自组织算法的性能和可用性，我们基于SIENA实现了自组织算法。事件的匹配率EP定义为一个事件与代理匹配的概率。实验中事件服从均匀分布，覆盖网络中有300个代理，设置五个场景Si(EP)(1≤i≤5)，分别为S1(1.7%)，S2(5.4)，S3(10.1)，S4(24.5)，S5(50.9)。图4所示为在事件服从均匀分布的情况下，覆盖网络中代理重组织的数量。

图4 在事件服从均匀分布的情况下，代理重组织的数量

从图4可见，重组织代理的数量被控制在可接受的范围，表明了自组织算法的可用性。

4 结论

高效率的P/S系统是目前重要的研究方向，自组织算法通过衡量代理之间的相似度，只利用本地代理中的信息，在不破坏初始网络拓扑结构特性的前提下，把P/S系统自组织的开销控制在一个合理的范围。

[1]Jokela P，Zahemszky A，Esteve Rothenberg C，et al.LIPSIN：line speed publish/subscribe inter-networking[C]//ACM SIGCOMM Computer Communication Review.ACM，2009，39(4)：195-206.

[2]Fotiou N，Trossen D，Polyzos G C.Illustrating a publish-subscribe internet architecture[J].Telecommunication Systems，2012，51(4)：233-245.

[3]Lagutin D，Visala K，Tarkoma S.Publish/Subscribe for Internet：PSIRP Perspective[C]//Future Internet Assembly.2010：75-84.

[4]董飚，陈金辉，阮峰，等.基于P2P网络的大规模发布/订阅系统[J].信息与控制，2009，38(5)：513-518.

[5]郑啸，罗军舟，曹玖新，等.基于发布/订阅机制的Web服务QoS信息分发模型[J].计算机研究与发展，2010(06)：1088-1097.

(责任编辑 周晓芸)

ResearchonPublish/SubscribeSystemBasedonSelf-OrganizingAlgorithm

DONGBiao

(NanjingInstituteofIndustryTechnology，Nanjing210023，China)

In this paper we propose an efficient publish/subscribe system by reorganizing the overlay network topology.This reorganization is done through a self-organizing algorithm executed by event brokers whose aim is to directly connect，through overlay links，pairs of brokers matching same events.The results show that the number of brokers involved in an event dissemination decreases，thus，reducing its cost.

publish/subscribe； overlay networks； self-organization

2013-11-10

董飚(1969-)，男，南京工业职业技术学院副教授，工学博士，研究方向：分布式计算，传感器网络软件技术。

TP393.2

A

1671-4644(2014)02-0036-04