面向社区的发布订阅系统重聚集方法及重聚集系统

摘要

本发明公开一种面向社区的发布订阅系统重聚集方法和系统，该方法包括：步骤1，分析客户端网络的消息关联关系，构建客户端通信关系网络；步骤2，应用社区划分方法对客户端通信关系网络进行划分，得到客户端网络中的社区结构；步骤3，对每个社区结构，选取合适的路由节点作为其聚集中心，并将属于这个社区的客户端网络聚集到所述聚集中心，使属于同一社区的客户端网络部署到地理位置较近的路由节点，让占消息总量比例较大的社区内的消息能较快的完成传递，提升订阅系统性能；聚集中心，定义为所述社区在聚集时聚集代价最小的路由节点。

说明书

技术领域

本发明涉及分布式发布订阅系统(Distributed Publish/Subscribe  System)和社区构建，划分和聚集（Community Construction and Division） 技术领域，尤其涉及面向社区的发布订阅系统重聚集方法及系统。

背景技术

在分布式发布订阅系统中，客户端（Client）连接到中间的路由节点 （Router），并通过发送消息与接收其他客户端的消息与之发生关联。消息由 路由节点路由和转发。客户端在连接到中间的路由节点时，通常是随机选择路 由节点连接或者按某种启发式的方式连接。这样的连接方式，通常没有考虑客 户端之间的关系或者只考虑静态的注册信息，使得一些有频繁消息关联的客户 端所连接的路由节点之间相距较远（路由节点之间的路径较长），导致系统中 大量的消息经过多次路由和转发才能到达目的客户端处，中间路由节点的负载 较大，并增加了系统内的消息量，降低了系统效率；而考虑与其他客户端动态 关系的部署方式，会节省消息经过的路由节点个数，进而减少系统内部产生的 消息量和消息通讯的时延，并在一定程度上缓解路由节点间负载不均的情况， 提升系统性能。

现有的一些方法，通过负载均衡算法来均衡系统内部路由节点之间的负 载，或者对注册信息聚类，来提高系统性能。但这些负载均衡或者聚类方法都 将客户端分为消息的发布者和订阅者。但实际应用中，客户端通常既要发出消 息给其他客户端，也同时要从其他客户端处接收消息。例如网络服务，既需要 输入参数，也有输出参数。因而这类客户端往往不能简单划分为消息发布者或 者消息订阅者。但是将这两个结合起来时，客户端的移动既有发送消息带来的 负载影响，也有接收消息带来的负载影响。这个负载的影响，是“两个方向” 的。而现有的算法将发送者和接收者分开后只能考虑“一个方向”的影响。因 而将消息发布者和消息订阅者合并起来时，现有算法具有明显的局限性。另一 类聚类算法通过考虑注册的信息，让接收类似信息的客户端连接到同一个 router上，但这种聚类方法也是将发布者和订阅者分开考虑，没有考虑客户 端同时作为发送者的情况。

发明内容

为解决上述问题，本发明提供了一种面向社区的发布订阅系统重聚集方法 和系统，通过分析客户端之间的网络关系，并应用社区划分和聚集的方法来对 客户端进行重聚集。社区聚集的方法从网络整体上考虑，弥补了将客户端分为 发送者或接收者时从局部信息考虑的不足。

本发明公开一种面向社区的发布订阅系统重聚集方法，包括：

步骤1，分析客户端网络的消息关联关系，构建客户端通信关系网络；

步骤2，应用社区划分方法对客户端通信关系网络进行划分，得到客户端 网络中的社区结构；

步骤3，对每个社区结构，选取合适的路由节点作为其聚集中心，并将属 于这个社区的客户端网络聚集到所述聚集中心，使属于同一社区的客户端网络 部署到地理位置较近的路由节点，让占消息总量比例较大的社区内的消息能较 快的完成传递，提升订阅系统性能；聚集中心，定义为所述社区在聚集时聚集 代价最小的路由节点。

所述的面向社区的发布订阅系统重聚集方法，步骤1还包括：

步骤21，客户端节点的关系网络用有向图G={V,E,W}来表示，其中V 是顶点集，表示所有的客户端节点；E是有向边集，表明存在着消息关联的客 户端节点，W表示边集的权重，为单位时间内两个客户端节点之间的消息量， 表明两个客户端节点之间的消息通信的强度；

步骤22，两个顶点之间存在一条边表示这两个客户端节点之间存在着消 息通信，边的方向表明从消息从发送者到接收者，为单位时间内两个客户端节 点之间的消息量；

步骤23，通过监控段连入分布式发布订阅系统的一个路由节点上，来收 集分布式发布订阅系统中的所有消息日志，然后通过消息日志获得客户端节点 之间的消息关联关系，构建客户端节点通信关系网络有向图G。

所述的面向社区的发布订阅系统重聚集方法，步骤2还包括：

步骤31，客户端节点通过关联程度聚集，社区内部关联强度大于社区之 间的关联强度。

步骤32，根据社区划分方法，利用一个反映社区内部边的比例，与在连 接概率相同时，随机网络的边的比例的差值，这个差值被定义为模度化，值越 大表明社区结构越明显；

步骤33，通过社区划分方法层次的合并或者拆分来计算使模度化取得峰 值时的社区分割结果，得客户端通信关系网络后，用社区划分方法分割网络， 得到客户端通信关系网络里面的社区结构。

所述的面向社区的发布订阅系统重聚集方法，步骤3还包括：

步骤41，定义聚集中心带来的订阅系统开销，然后建立包含全部集群的 队列，依次处理每个集群，将位于这个集群内的所有社区根据其客户端节点的 比例排序，优先将客户端节点比例较大的社区部署到当前的集群上；

步骤42，如果某个社区之前被部署了，则比较这个社区在当前集群和之 前被部署的集群上的客户端节点比例，如果当前集群上的客户端节点比例更 大，则这个社区被重部署到当前集群；

步骤43，通过迭代过程对聚集中心开销进行折中平衡。

所述的面向社区的发布订阅系统重聚集方法，步骤41中订阅系统开销还 包括：

步骤51，订阅系统中消息经过的路由节点的条数的平均值来定义订阅系 统的性能，

$\left({\Sigma }_{m=1}^M\mathrm{Hop}\left(m\right)\right)/M$

其中m为消息的编号，m∈[1,M]，M为消息总量；

迁移的客户端节点数量越多，重聚集的客户端移动代价也就越大，定义客 户端的移动代价为迁移的客户端节点的数量；

步骤52，目标函数为：

$\mathrm{Min}(\left({\Sigma }_{m=1}^M\mathrm{Hop}\left(m\right)\right)/M)$

s.t.Min(N_movedclient)

其中，N_movedclient为部署过程中位置发生变化的客户端的数量；

步骤53，在定义了重聚集带来的订阅系统开销后，如果聚集在当前拥有 这个社区的客户端节点数量最多的集群时，聚集代价相对于聚集在其他的集群 来说，是最小的。

所述的面向社区的发布订阅系统重聚集方法，步骤43还包括：

步骤61，对客户端节点的客户端通信关系网络进行社区划分；

步骤62，以最小的迁移代价，将社区重聚集到聚集中心，达到社区的物 理聚集；

步骤63，依据订阅系统的性能定义和重聚集代价定义，计算订阅系统性 能的改变和重聚集的代价；

步骤64，用社区划分方法对每个社区再次进行社区划分；

步骤65，重复步骤62和步骤63；如果步骤64的社区划分带来的系统性 能的变化比例大于重聚集的代价的变化比例，则迭代停止，否则重复步骤 64-65。

本发明公开一种面向社区的发布订阅系统重聚集系统，包括：

构建网络模块，用于分析客户端网络的消息关联关系，构建客户端通信关 系网络；

社区划分模块，用于应用社区划分方法对客户端通信关系网络进行划分， 得到客户端网络中的社区结构；

聚集中心模块，用于对每个社区结构，选取合适的路由节点作为其聚集中 心，并将属于这个社区的客户端网络聚集到所述聚集中心，使属于同一社区的 客户端网络部署到地理位置较近的路由节点，让占消息总量比例较大的社区内 的消息能较快的完成传递，提升订阅系统性能；聚集中心，定义为所述社区在 聚集时聚集代价最小的路由节点。

所述的面向社区的发布订阅系统重聚集系统，构建网络模块还包括：

建立有向图模块，用于客户端节点的关系网络用有向图G={V,E,W}来表 示，其中V是顶点集，表示所有的客户端节点；E是有向边集，表明存在着消 息关联的客户端节点，W表示边集的权重，为单位时间内两个客户端节点之间 的消息量，表明两个客户端节点之间的消息通信的强度；两个顶点之间存在一 条边表示这两个客户端节点之间存在着消息通信，边的方向表明从消息从发送 者到接收者，为单位时间内两个客户端节点之间的消息量；通过监控段连入分 布式发布订阅系统的一个路由节点上，来收集分布式发布订阅系统中的所有消 息日志，然后通过消息日志获得客户端节点之间的消息关联关系，构建客户端 节点通信关系网络有向图G。

所述的面向社区的发布订阅系统重聚集系统，社区划分模块还包括：

关联强度模块，用于客户端节点通过关联程度聚集，社区内部关联强度大 于社区之间的关联强度。

差值模块，用于根据社区划分方法，利用一个反映社区内部边的比例，与 在连接概率相同时，随机网络的边的比例的差值，这个差值被定义为模度化， 值越大表明社区结构越明显；

社区结构模块，用于通过社区划分方法层次的合并或者拆分来计算使模度 化取得峰值时的社区分割结果，得到客户端通信关系网络后，用社区划分方法 分割网络，得到客户端通信关系网络里面的社区结构。

所述的面向社区的发布订阅系统重聚集系统，聚集中心模块还包括：

系统开销模块，用于定义聚集中心带来的订阅系统开销，然后建立包含全 部集群的队列，依次处理每个集群，将位于这个集群内的所有社区根据其客户 端节点的比例排序，优先将客户端节点比例较大的社区部署到当前的集群上；

部署模块，用于如果某个社区之前被部署了，则比较这个社区在当前集群 和之前被部署的集群上的客户端节点比例，如果当前集群上的客户端节点比例 更大，则这个社区被重部署到当前集群；

迭代模块，用于通过迭代过程对聚集中心开销进行折中平衡。

所述的面向社区的发布订阅系统重聚集系统，系统开销模块还包括：

定义性能模块，用于订阅系统中消息经过的路由节点的条数的平均值来定 义订阅系统的性能，

$\left({\Sigma }_{m=1}^M\mathrm{Hop}\left(m\right)\right)/M$

其中m为消息的编号，m∈[1,M]，M为消息总量；

迁移的客户端节点数量越多，重聚集的客户端移动代价也就越大，定义客 户端的移动代价为迁移的客户端节点的数量；

计算模块，用于目标函数为：

$\mathrm{Min}(\left({\Sigma }_{m=1}^M\mathrm{Hop}\left(m\right)\right)/M)$

s.t.Min(N_movedclient)

其中，N_movedclient为部署过程中位置发生变化的客户端的数量；

定义开销模块，用于在定义了重聚集带来的订阅系统开销后，如果聚集在 当前拥有这个社区的客户端节点数量最多的集群时，聚集代价相对于聚集在其 他的集群来说，是最小的。

所述的面向社区的发布订阅系统重聚集系统，迭代模块还包括：

划分模块，用于对客户端节点的客户端通信关系网络进行社区划分；

物理聚集模块，用于以最小的迁移代价，将社区重聚集到聚集中心，达到 社区的物理聚集；

计算代价模块，用于依据订阅系统的性能定义和重聚集代价定义，计算订 阅系统性能的改变和重聚集的代价；

再次划分模块，用于用社区划分方法对每个社区再次进行社区划分；

变化比例模块，用于重复物理聚集模块和计算代价模块；如果再次划分模 块的社区划分带来的系统性能的变化比例大于重聚集的代价的变化比例，则迭 代停止，否则重复再次划分模块-变化比例模块。

本发明提出的一种面向社区的发布订阅系统重聚集方法及系统的有益效 果为：

第一：提出了在客户端同为消息发送者和消息接收者时，发布订阅系统的 客户端优化部署方式，比现有的只考虑客户端分别为消息发送者或者消息接收 者的客户端聚集算法更通用；

第二：提出了发布订阅系统的客户端通信网络的构建方法；

第三：提出了基于聚集中心的启发式聚集方法，保证在进行社区重聚集时 的客户端移动代价最小。

附图说明

图1为本发明面向社区的发布订阅系统重聚集方法流程图；

图2为本发明客户端的通信网络结构；

图3为本发明客户端网络的社区划分结果；

图4为本发明发布订阅系统的中间路由结构示例；

图5为本发明客户端在发布订阅系统中间路由组织上的初始部署；

图6为本发明社区在发布订阅系统上的初始部署部署；

图7为本发明客户端的社区重聚集部署结果；

图8为本发明面向社区的发布订阅系统重聚集系统流程图。

具体实施方式

下面给出本发明的具体实施方式，结合附图对本发明做出了详细描述。

本发明提供一种分布式发布订阅系统中基于社区的客户端重聚集方法，通 过划分客户端中的社区结构，并将社区结构部署在底层路由节点中地理邻近的 节点上，以降低系统的负载，缩短消息传递时延，提升系统性能。如图1所示， 具体而言，基于社区的客户端重聚集方法包括三个步骤：

1）分析客户端网络的消息关联关系，构建客户端通信关系网络；

2）应用社区划分算法对客户端的通信关系网络进行划分，得到客户端网 络中的社区结构；社区指的是相互之间消息关联强度相对较大的客户端集合， 社区内的消息关联密切，而社区间的消息关联相对较弱；

3）对每个社区，选取合适的路由节点作为其聚集中心，并将属于这个社 区的客户端聚集到这个聚集中心，使属于同一社区的客户端被部署到地理位置 较近的路由节点上，让占消息总量比例较大的社区内的消息能较快的完成传 递，提升系统性能。社区的聚集中心，定义为这个社区在聚集时聚集代价最小 的路由节点。

基于社区的客户端重聚集方法：

（一）客户端节点的通信关系网络构建：

客户端节点的关系网络可以用一个有向图G={V,E,W}来表示，其中V是 顶点集，表示所有的客户端节点；E是有向边集，表明存在着消息关联的客户 端节点。两个顶点之间存在一条边表示这两个客户端节点之间存在着消息通 信。边的方向表明从消息从发送者到接收者。W表示边集的权重，表明两个客 户端节点之间的消息通信的强度。在这里，我们定义权重w为单位时间内两个 客户端节点之间的消息量。

我们通过一个监控段连入分布式发布订阅系统的一个路由节点上，来收集 发布订阅系统中的所有消息日志，然后通过消息日志获得客户端节点之间的消 息关联关系，构建客户端节点通信关系网络有向图G。

在实际运行中，往往客户端节点之间的消息关联强度事先是未知的，并且 在长期的运行过程中，客户端节点之间的关联情况也许会随着时间的推移而发 生改变，但是，在较短的一段时间内，可以认为客户端节点之间的通信关系是 相对稳定的。我们统计在这段时间内客户端节点之间的消息通信情况，来构建 客户端节点之间的关系网络。当通信关系网络发生较大变化时，例如当客户端 节点关系网络发生度的变化的节点比例，超过一个设定的阀值（如30%）时， 我们会对客户端节点进行重新部署。后面的算法会介绍我们的重部署算法是考 虑了系统性能提升和重部署代价的一个折中的，因而当消息关系发生变化时， 新的部署也可以在较小的部署代价内完成。这说明我们的方法是适应动态消息 环境的。

（二）客户端节点通信网络的社区划分

客户端节点网络中的社区结构（community structure）的特点，局部的 看，是节点和社区内的其他节点关联密切，而和社区外的关联程度会小很多； 整体的看，是节点通过关联程度聚集，社区内部关联强度大于社区之间的关联 强度。本发明关注的不是社区划分的算法，因而这里采用当前研究中流行的社 区划分算法来对分割客户端关系网络。当前研究中，Newman在2004年提出来 的基于“模度化”的计算方法，其主要思想是利用一个反映社区内部边的比例， 与在连接概率相同时，随机网络的边的比例的差值。这个差值被定义为模度化， 值越大表明社区结构越明显。Newman的方法具备良好的理论基础，因而被领 域内的研究者认同和追随。在具体实现中，Newman算法通过层次的合并或者 拆分来计算使模度化取得峰值时的社区分割结果。我们在获得客户端节点的关 系网络后，用Newman的算法分割网络，得到关系网络里面的社区结构。

（三）客户端节点基于社区的重聚集

这一步我们也称为客户端节点社区的物理聚集：在划分完社区结构后，将 一个社区内的客户端节点连接到中间路由组织中的物理连接速度较快，或者地 理上较接近的集群节点上。这能带来两个好处：

1）能有效的提高大部分消息的传递速度。社区划分将相互消息关联较强 的客户端节点划分在一个社区内，因此系统中的大部分消息都在社区内的客户 端节点之间。将社区内的客户端节点部署在物理连接较快的节点能提高社区内 的消息的传递速度。

2）能有效降低中间路由组织中的路由节点的消息量。集群中物理连接速 度较快的计算节点，往往是通过链路直接连接，或者通过很少的几个路由节点 连接。社区内的客户端节点的物理聚集，使得大部分消息能通过很少的路由节 点完成传递，降低了系统中路由节点处理的消息量。

在将社区内的客户端节点部署到中间路由组织时，有如下的问题需要考 虑：

1）客户端节点从一个连接点部署到另外一个连接点，这个客户端的迁移 会对系统带来移动代价。可以认为，社区在物理上越聚集，系统的性能提升越 好；而移动的客户端节点越多，移动代价越大。一个合理的策略是在系统性能 的提升与迁移带来的代价中取得平衡或折中。

2）划分的社区以及底层的集群都有特定的规模，在部署的时候要尽量在 集群间达到负载均衡，避免某些集群过载而某些集群空载。

为了解决上面的问题，我们提出一个基于聚集中心的启发式算法，在对客 户端节点进行社区重聚集的时候，在尽量提升性能的同时，减小重聚集过程中 的开销，同时达到负载均衡。下面，我们先对一些参数进行介绍，以便于介绍 算法。

算法的目标是以较小的客户端移动代价，尽可能的提高系统性能。消息是 通过底层集群的路由节点转发的。消息经过的路由的跳数越少，消息从发送到 接收的转发时延也越小。因此，我们用系统中消息经过的路由的条数的平均值 来定义系统的性能：

$\left({\Sigma }_{m=1}^M\mathrm{Hop}\left(m\right)\right)/M$

其中m为消息的编号，m∈[1,M]，M为消息总量。

迁移的客户端节点数量越多，重聚集的客户端移动代价也就越大，我们定 义客户端的移动代价为迁移的客户端节点的数量。

因而，算法的目标函数为：

$\mathrm{Min}(\left({\Sigma }_{m=1}^M\mathrm{Hop}\left(m\right)\right)/M)$

s.t.Min(N_movedclient)

其中，N_movedclient为部署过程中位置发生变化的客户端的数量。

在定义了重聚集带来的开销后，我们可以知道，一个社区如果聚集在当前 拥有这个社区的节点数量最多的集群时，聚集代价相对于聚集在其他的集群来 说，是最小的。因而，聚集中心的定义为：在其分布的集群中，拥有这个社区 的客户端节点数量最多的集群为这个社区的聚集中心。

对于一个社区内的客户端节点，在聚集前往往是分散在中间路由组织的各 个集群上。如果将这个社区聚集到这个社区的聚集中心，重聚集的开销是最小 的。但是要注意的是，一个社区在聚集的时候，不能忽视其他社区的聚集中心： 集群的规模有限，某个集群有可能是多个社区的聚集中心，如果这些社区都聚 集到其聚集中心，会造成这个集群的负载过大。因而，我们计算社区分布在各 个集群上的客户端节点数量占这个社区总任务量的比例，然后对这个比例值从 大到小排序，每个社区优先聚集到比例值最大的集群上，也就是这个社区的聚 集中心上，如果聚集中心的负载已经满了，就聚集到比例值第二大的集群上， 如果比例第二大的集群也负载满了，就聚集到比例第三大的集群上，以此类推， 直致比例最小的集群。

算法的具体过程见如下：我们先建立一个包含所有集群的队列Q，然后依 次处理每个集群：对位于这个集群内的所有社区根据其客户端节点的比例排序 （第6行），优先将客户端节点比例较大的社区部署到当前的集群上；如果某 个社区之前被部署了，则比较这个社区在当前集群和之前被部署的集群上的客 户端节点比例，如果当前集群上的客户端节点比例更大，则这个社区被重部署 到当前集群（第10-11行）。这保证了每个社区会优先部署到社区的聚集中心， 如果聚集中心已经过载，则会部署到比例第二大的集群，以此类推。

客户端基于社区的重聚集方法

另外，我们还用一个迭代过程来达到系统性能和重聚集开销的折中平衡： 1）首先对客户端节点的关系网络进行社区划分；2）以最小的迁移代价，将社 区重聚集到它的聚集中心，达到社区的物理聚集；3）依据系统的性能定义和 重聚集代价定义，计算系统性能的改变和重聚集的代价；4）用Newman社区划 分算法对每个社区再次进行社区划分；5）重复步骤2和步骤3；6）如果步骤 4）的社区划分带来的系统性能的变化比例大于重聚集的代价的变化比例，则 迭代停止，否则重复步骤4-6。步骤6的意思是：随着对社区继续进行社区划 分并聚集，系统性能与前一次的部署结果相比会下降，而重聚集的代价也会变 小，在迭代中，如果再划分导致的系统性能下降的比例大于重聚集代价减小的 比例，说明这一步迭代带来的性能的损失更大，因此迭代终止。

图2所示的是客户端的通信网络的一个例子：其中有27个客户端，编号 为1-27；从节点1到节点3之间的箭头及箭头上的数字7，表明1号客户端和 3号客户端之间的消息关联是从1到3，消息量为7。这个通信关系是从发布 订阅系统中的消息通信日志构建出来的。

在获得客户端通信网络的结构后，我们用Newman社区划分算法对客户端 通信网络进行社区划分。图3所示的是图2的客户端通信网络的社区划分结果。 每个椭圆内的客户端节点表示一个社区，这里面共有4个社区。我们把1号客 户端到6号客户端所在的社区称为社区a，包含6个客户端节点。把7号客户 端到15号客户端所在的社区称为社区b，包含9个客户端节点；把16号客户 端到20号客户端所在的社区称为社区c，包含5个客户端节点；把21号客户 端到27号客户端所在的社区称为社区d，包含7个客户端节点。

图4所示的是分布式发布订阅系统中的中间路由组织结构，由3个集群组 成，每个集群用椭圆表示。我们分别称为集群1，集群2，和集群3。每个集 群由一定数量的路由节点组成。

图5所示的是客户端节点在发布订阅系统的中间路由组织上的初始部署 情况。可以看到，社区a在集群2上有1个，在集群3上有5个；社区b在集 群1上有3个，在集群2上有4个，在集群3上有2个，社区c在集群1上有 1个，在集群2上有2个，在集群3上有2个，社区d在集群1上有3个，在 集群2上有4个。我们以集群为索引，对每个集群上的社区的部署情况进行排 序，得到图7所示的结果。

在图6上对客户端节点运行客户端基于社区聚集的算法，流程如下：

1.将所有的集群放入一个待处理的集群队列；

2.依次处理集群队列中的每个集群：

对集群1，社区d在集群1内的比例最大，因而将社区d部署在集群1上； 至此集群1的负载已满，不再处理社区d后面的社区（社区b和社区c）；

对集群2，社区d在集群2内的比例最大，且大于社区d在集群1中的比 例，因而将社区d重新部署在集群2上，集群1上没有社区部署，负载为空， 因而放入待处理的集群队列中；至此集群2的负载已满，不再处理社区d后面 的社区（社区b，社区c，社区a）；

对集群3，社区a在集群3上的比例最大，因而将社区a部署在集群3上； 考虑到社区a的大小和集群的整体负载，还可继续部署其他社区；继续处理集 群3上的其他社区，将社区c部署在集群3上；至此集群3的负载已满，不在 处理社区c后面的社区（社区b）；

对于在2.2中重新放入集群队列的集群1，因为集群1上的社区d已经被 部署在集群2上（社区d在集群2上的比例更大），继续考虑社区d后面的社 区b，社区b还没被部署，因而被部署在集群1上；

没有需要再处理的集群，算法结束。

算法运行后的客户端部署结果如图6所示。可以看到，每个社区都优先考 虑聚集在其聚集中心（社区d先被预部署到集群1，后被部署到集群2），如果 当聚集中心已被其他社区占据，且负载已满（例如，社区b没有被部署到集群 2），则这个社区会被部署到比例第二大的集群上（社区b被部署到集群1上）。

如图8所示，本发明公开一种面向社区的发布订阅系统重聚系统，包括：

构建网络模块10，用于分析客户端网络的消息关联关系，构建客户端通 信关系网络；

社区划分模块20，用于应用社区划分方法对客户端通信关系网络进行划 分，得到客户端网络中的社区结构；

聚集中心模块30，用于对每个社区结构，选取合适的路由节点作为其聚 集中心，并将属于这个社区的客户端网络聚集到所述聚集中心，使属于同一社 区的客户端网络部署到地理位置较近的路由节点，让占消息总量比例较大的社 区内的消息能较快的完成传递，提升订阅系统性能；聚集中心，定义为所述社 区在聚集时聚集代价最小的路由节点。

所述的面向社区的发布订阅系统重聚集系统，构建网络模块还包括：

建立有向图模块，用于客户端节点的关系网络用有向图G={V,E,W}来表 示，其中V是顶点集，表示所有的客户端节点；E是有向边集，表明存在着消 息关联的客户端节点，W表示边集的权重，为单位时间内两个客户端节点之间 的消息量，表明两个客户端节点之间的消息通信的强度；两个顶点之间存在一 条边表示这两个客户端节点之间存在着消息通信，边的方向表明从消息从发送 者到接收者，为单位时间内两个客户端节点之间的消息量；通过监控段连入分 布式发布订阅系统的一个路由节点上，来收集分布式发布订阅系统中的所有消 息日志，然后通过消息日志获得客户端节点之间的消息关联关系，构建客户端 节点通信关系网络有向图G。

所述的面向社区的发布订阅系统重聚集系统，社区划分模块还包括：

关联强度模块，用于客户端节点通过关联程度聚集，社区内部关联强度大 于社区之间的关联强度。

差值模块，用于根据社区划分方法，利用一个反映社区内部边的比例，与 在连接概率相同时，随机网络的边的比例的差值，这个差值被定义为模度化， 值越大表明社区结构越明显；

社区结构模块，用于通过社区划分方法层次的合并或者拆分来计算使模度 化取得峰值时的社区分割结果，得到客户端通信关系网络后，用社区划分方法 分割网络，得到客户端通信关系网络里面的社区结构。

所述的面向社区的发布订阅系统重聚集系统，聚集中心模块还包括：

系统开销模块，用于定义聚集中心带来的订阅系统开销，然后建立包含全 部集群的队列，依次处理每个集群，将位于这个集群内的所有社区根据其客户 端节点的比例排序，优先将客户端节点比例较大的社区部署到当前的集群上；

部署模块，用于如果某个社区之前被部署了，则比较这个社区在当前集群 和之前被部署的集群上的客户端节点比例，如果当前集群上的客户端节点比例 更大，则这个社区被重部署到当前集群；

迭代模块，用于通过迭代过程对聚集中心开销进行折中平衡。

所述的面向社区的发布订阅系统重聚集系统，系统开销模块还包括：

定义性能模块，用于订阅系统中消息经过的路由节点的条数的平均值来定 义订阅系统的性能，

$\left({\Sigma }_{m=1}^M\mathrm{Hop}\left(m\right)\right)/M$

其中m为消息的编号，m∈[1,M]，M为消息总量；

迁移的客户端节点数量越多，重聚集的客户端移动代价也就越大，定义客 户端的移动代价为迁移的客户端节点的数量；

计算模块，用于目标函数为：

$\mathrm{Min}(\left({\Sigma }_{m=1}^M\mathrm{Hop}\left(m\right)\right)/M)$

s.t.Min(N_movedclient)

其中，N_movedclient为部署过程中位置发生变化的客户端的数量；

定义开销模块，用于在定义了重聚集带来的订阅系统开销后，如果聚集在 当前拥有这个社区的客户端节点数量最多的集群时，聚集代价相对于聚集在其 他的集群来说，是最小的。

所述的面向社区的发布订阅系统重聚集系统，迭代模块还包括：

划分模块，用于对客户端节点的客户端通信关系网络进行社区划分；

物理聚集模块，用于以最小的迁移代价，将社区重聚集到聚集中心，达到 社区的物理聚集；

计算代价模块，用于依据订阅系统的性能定义和重聚集代价定义，计算订 阅系统性能的改变和重聚集的代价；

再次划分模块，用于用社区划分方法对每个社区再次进行社区划分；

变化比例模块，用于重复物理聚集模块和计算代价模块；如果再次划分模 块的社区划分带来的系统性能的变化比例大于重聚集的代价的变化比例，则迭 代停止，否则重复再次划分模块-变化比例模块。

本发明提出一种分布式环境下发布订阅系统中基于社区重聚集的客户端 部署方法，。

第一：提出了在客户端同为消息发送者和消息接收者时，发布订阅系统的 客户端优化部署方式，比现有的只考虑客户端分别为消息发送者或者消息接收 者的客户端聚集算法更通用。

第二：提出了发布订阅系统的客户端通信网络的构建方法。

第三：提出了基于聚集中心的启发式聚集算法，保证在执行社区重聚集时 的代价最小。

本领域的技术人员在不脱离权利要求书确定的本发明的精神和范围的条 件下，还可以对以上内容进行各种各样的修改。因此本发明的范围并不仅限于 以上的说明，而是由权利要求书的范围来确定的。