XMPP分布式数据的访问路径的遗传算法研究

陈双喜 沈权权 吴春民

(1.嘉兴职业技术学院，浙江 嘉兴 314036；2.浙江大学 计算机科学与技术学院，浙江 杭州310000)

0 引言

XMPP(Extensible Messaging and Presence Protocol，可扩展消息与存在协议)是一种基于XML的即时消息协议[1]。它继承了XML灵活性和扩展性，已经应用到其它非IM领域[2]。有学者提议XMPP作为物联网领域的标准协议[3]。也有学者将其应用到分布式数据存储领域，将提供相同数据的服务器放在网络中的不同位置，以减少网络资源的消耗、提供数据的安全性和多用户的QoS(Quality of Service)[4]。但是，在相同服务器资源和网络资源下，不同的访问路径将导致不同的网络状态，会出现服务器负载和网络资源负载不平衡等问题。因此有必要对访问路径优化问题进行探讨。本文将对问题就行分析，建立数学模型，利用遗传算法就行求解。通过模拟实验网络，构建XMPP路径优化服务器，实验验证得出在双目标双约束条件下的不同解[5-6]。

1 问题说明

基于XMPP的分布式数据的访问QoS路径优化的目标是优化网络中数据流的传输路径，实现服务器负载平衡以及网络资源消耗平衡。由于各个数据流占用的服务器资源和网络资源不同，本研究的问题就是将网络中数据流分别重定向到不同服务器的路径优化问题[7]。此外，为了满足网络数据流的路径优化，需建立XMPP路径优化服务器。它将定时收集网络相关信息，进行分析处理后得出在不同约束下的最优路径。如图1所示，模拟了基于XMPP的分布式数据的访问网络的拓扑图。其中包括30条链路 (E0～E29)，30个用户节点(C0～C29)，4 个服务器节点(S0～S3)。

图1 基于XMPP的数据分布式存储网络拓扑图

将访问数据的网络看成一个有向连通图 G(V,E)，其中，V为节点集；E为链路集。节点集V包括：

(1)服务器节点S；

(2)用户访问节点C。

假设G(V,E)中C,S和E的数量分别为m,n,l，用户与各个服务器之间的链路都采用TCP/IP协议获得访问路径[8]，则每个用户有n种可选链路，整个网络就存在nm种可选状态。这里求解的问题就是从这些可选状态中选取一种，以使网络在满足约束条件的情况下整体性能最优，下面给出了它的问题模型。

优化的目标是链路集E服务器负载均衡、网络资源负载均衡。XMPP路径优化服务器收集的信息存储到以下矩阵中：

(1)CR=[cri]m：用户占用服务器资源矩阵，cri表示用户 i占用的服务器资源；

(2)CB=[cbi]m：用户占用网络资源矩阵，cbi表示用户 i占用的网络资源；

(3)SR=[srj]m：服务器资源矩阵，srj表示服务器 j所能提供的最大服务器资源；

(4)EB=[ebk]m：网络资源矩阵，ebk表示链路 k所能提供的最大网络资源；

(5)p=[pi,j]m×n： 链路分布矩阵，pi,j表示用户 i到服务器 j是否链接，若链接pi,j=1，若未链接pi,j=0；

(6)x=[xi]m：决策变量，xi表示用户 i选择的服务器。

将路径优化问题用上面的矩阵数学描述为如下双目标优化问题：

公式(2)中，f1(x)表示各服务器利用率的最大值；f2(x)表示各链路网络资源利用率的最大值。

要实现数据访问的QoS，各用户请求所消耗的网络资源之和必须小于各条链路的网络资源，所消耗的服务器资源之和必须小于各个服务器的资源，则约束条件表示为：

2 问题求解

从上述数学模型可知，问题为一个多目标多约束优化问题，运用遗传算法求解该问题的过程如下：

(1)编码

染色体编码采用x=x1x2x3…xm的形式，基因xi表示用户 i所选择的服务器，因此一条染色体表示一种网络路径状态。基因xi的可选值为服务器的数量，取0到n-1范围内的任意整数。

(2)适应度函数

利用权重系数法，得到适应度的求解公式：

其中w1,w2分别表示两个目标函数的权重，每一组权重对应一个解，调节权重值可以得到Pareto最优解集[7]。实际应用中需要根据网络情况来选定一组权重值，从而获得对应的解作为路径优化的目标。

(3)群体设定

为了使得群体能够覆盖基因的所有可能取值，种群的规模H与数据库服务器的数量n有关：

其中，α为种群规模系数，α>1。

(4)选择

采用最优复制与比例选择相结合的方法进行选择操作。在每一代进化过程中，保留h个当前最优的个体不参与交叉、变异等遗传操作，直接将它们复制到下一代群体中。

其余个体在下一代群体中生存的数目N计算如下：

其中，h为最优个体保留数量；Fr为个体r的适应度值。

(5)交叉

采用随机取交叉点的方式，选取多个交叉点就行交叉操作。随机交叉点的取值范围为0到m-1。

(6)变异

采用随机取数的方式获取变异点，取值范围为0到m-1；在变异点处采用随机取值的方式完成基因的变异。变异的基因值取值范围为0到n-1。变异的概率为MRandom。

(7)终止条件

在一定代数内没有更优解出现时将自动终止，公式(7)作为解的终止条件函数。

算法的C#总体实现过程如下：

3 实验模拟及结果

从图1的模拟环境可知m=30,n=4,l=30。服务器S0～S3的资源矩阵SR=(30,20,40,30)，其他参数如表 1、表 2所示。

表1 网络链路提供的网络资源

设置遗传算法的参数为：种群规模系数α=3；最优个体保留数量 h=1，交叉点数量CP=4；变异率 MRadom=0.03。 以模拟环境为基础，用 C#编程，改变w1,w2的值，在迭代次数都小于60次的情况下收敛，表3为计算结果。

表3中列出5种权重条件下的各链路与服务器之间的关系。各服务器的利用率和各链路网络资源的利用率，如图2、图3所示。

表2 用户所需网络资源和服务器资源

表3 在不同条件下的结果

图3 网络资源利用率

如图2、图3所示，当w1=0时（N2），网络资源利用率高，利用率都超过60%，部分达到堵塞现象；当w2=0时（N1），服务器负载的变化很大，利用率超过 70%；当 w1=0.5，w2=0.5 时(N2)，数据库服务器利用率集中在40%左右，网络资源利用率在40%到60%左右；当w1，w2权重分配就行随机发配时(N4，N5)，数据库服务器和网络资源利用率处在30%到70%之间。

4 总结

为了提高XMPP网络分布式数据库数据访问效率必须进行路径优化。本文从多目标优化角度运用遗传算法处理这个问题，给出了满足QoS多约束前提下的路径优化的算法模型与实现过程。实验结果表明本算法在不同权重系数下可以收敛于各个指标的最优值，实现路径的多目标组合优化。有待研究的内容：

(1)如何提高算法的执行效率。初步想法通过改变编码方式（如格雷码），研究执行效率；

(2)引入更多约束条件，使之更符合实践需求；

(3)建立物理实验环境，就行实验研究。

［1］P.Saint-Andre，Ed.Extensible Messaging and Presence Protocol(XMPP)：Core.http://www.faqs.org/rfcs/rfc3920.txt[OL].

［2］黄剑.基于XMPP的端到端连接建立机制的研究与实现[D].国防科学技术大学，2009.

［3］张卫，张峻峰，罗长寿.XMPP应用于物联网通讯协议的研究[J].中国农学通报，2012，28（09）：289-292.

［4］张丽，曲攀.自组织覆盖网络QoS组播动态路径优化研究[J].计算机工程与应用，2013，3（24）：83-87.

［5］Liu Junli，Chen Shuangxi,Mao Jie.Genetic algorithm study on the university course timetabling problem[R].2012 IEEE International Conference on Cyber Technology in Automation，Control， andIntelligent Systems(CYBER).Bangkok,Thailand.2012：179-182.

［6］Chang Wook Ahn,R.S.Ramakrishna.A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations[J].IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION Jun，2002：566-579.

［7］惠雯，尹浩，林闯，杨扬.内容分发网络请求路径研究[J].计算机科学，2012，2（12）：1-7.

［8］陶英华，韩英伟，刘剑.TCP/IP协议解析（上）[J].中国有线电视，2005，16（24）：1574-1577.