基于粒子群算法的Web服务组合研究

第３４卷　第５期　计算机工程　２００８年３月　Ｖｏ１．３４　Ｎｏ．５　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｍａｒｃｈ　２００８　・网络与通信・　文章缩号ｔ　１００１１－－３４２８（２００８）０５－－０１０４－－０３—　＿＿　■———　ｉ　丽　基于粒子群算法的Ｗｅｂ服务组合研究　刘莉平１，２　９陈志刚１，２　９刘爱心　（１．中南大学软件学院，长沙４１００８３；２．中南大学信息科学与工程学院，长沙４１００８３）　摘要：针对现有服务组合中ＱｏＳ优化的不足，该文提出一种基于粒子群算法的解决ＱｏＳ动态服务组合算法。通过对服务组合的业务逻　辑与服务实例进行合理编码，重新定义粒子的位置、速度与“加”运算，利用粒子群算法的智能优化原理以及局部与全局优化信息加快粒　子群的搜索速度，使其能够快速地得到一组满足约束条件的ｐａｒｅｔｏ优化的服务组合。实验结果证明了算法的可行性和有效性。　关蝴：Ｗｅｂ服务组合；服务选取；粒子群算法；Ｐａｒｅｔｏ优化　Ｒｅｓｅａｒｃｈ　０ｎ　Ｗｅｂ　Ｓｅｒｖｉｃｅｓ　Ｃｏｍｐｏｓｉｔｉｏｎ　Ｂａｓｅｄ　０ｎ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ＬＩＵ　Ｌｉ．ｐｉｎｇ　，ＣＨＥＮ　Ｚｈｉ・ｇａｎｇ　，一，ＬＩＵ　Ａｉ．ｘｉｎ２　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，Ｃｅｎｔｒａｌ　Ｓｏｕｔｈ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ　４１００８３；　２．Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｅｎｔｒｌａ　Ｓｏｕｔｈ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ　４１００８３）　［Ａｂｓｔｒａ￣］Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ｎａ　ｉｍｐｒｏｖｅｄ　ｌａｇｏｒｉｈｔｍ　ｂａｓｅｄ　ｏｎ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ，ｗｈｉｃｈ　ｉｓ　ｔＯ　ｒｅｓｏｌｖｅ　ｄｙｎａｍｉｃ　Ｗｅｂ　Ｓｅｒｖｉｃｅｓ　ｓｅｌｅｃｔｉｏｎ　ｗｉｈｔ　ＱｏＳ　ｏｐｔｉｍａｌ　ｉｎ　ｗｅｂ　Ｓｅｒｖｉｃｅｓ　ｃｏｍｐｏｓｉｔｉｏｎ．Ｔｈｅ　ｅｓｓｅｎｃｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｔｈａｔ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｄｙｎａｍｉｃ　ｗｅｂ　Ｓｅｒｖｉｃｅ　ｓｅｌｅｃｔｉｏｎ　ｗｉｈｔ　ＱｏＳ　ｏｐｔｉｍａｌ　ｉｓ　ｒｔｎａｓｆｏｒｍｅｄ　ｉｎｔｏ　ａ　ｍｕｌｉｔ—ｏｂｊｅｃｔｉｖｅ　ｓｅｒｖｉｃｅｓ　ｃｏｍｐｏｓｉｔｉｏｎ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｗｉｈｔ　ＱｏＳ　ｃｏｎｓｔｒａｉｎｔｓ．Ｔｈｅ　ｈｔｅｏｒｙ　ｏｆ　ｉｎｔｅｌｌｉｇｅｎｔ　ｏｐｔｉｉｍｚａｔｉｏｎ　ｏｆ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｉｍｚａｔｉｏｎ　ｌａｇｏｒｉｔｈｍ　ｉｓ　ｕｔｉｌｉｚｅｄ　ｔｏ　ｐｒｏｄｕｃｅ　ａ　ｓｅｔ　ｏｆ　ｏｐｔｉｍａｌ　Ｐａｒｅｔｏ　ｓｅｒｖｉｃｅｓ　ｃｏｍｐｏｓｉｔｉｏｎ　ｐｒｏｃｅｓｓ　ｗｉｔｈ　ｃｏｎｓｔｒａｉｎｔ　ｐｒｉｎｃｉｐｌｅ　ｂｙ　ａｃｃｅｌｅｒａｔｉｎｇ　ｇｌｏｂａｌ　ａｎｄ　ｄｅｔａｉｌ　ｓｅａｒｃ￣ｎｇ　ｓｐｅｅｄ　ｂａｓｅｄ　ｏｎ　ｄｅｃｉｄｉｎｇ　ＰＳＯ　ｓｔａｔｅ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｉｎｄｉｃａｔｅ　ｈｔｅ　ｆｅａｓｉｂｉｌｉｔｙ　ｎａｄ　ｅｆｉｆｃｉｅｎｃｙ　ｏｆ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ．　［Ｋｅｙ　ｗｏｒｄｓｌ　ｗｅｂ　Ｓｅｖｒｉｃｅｓ　ｃｏｍｐｏｓｉｉｔｏｎ；ｓｅｖｒｉｃｅｓ　ｓｅｌｅｃｉｔｏｎ；ｐａｒｉｔｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｉｍｚａｉｔｏｎ；Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　１概述　题。目前，服务动态组合的基本目标是针对不同的应用，从　近年来Ｗｅｂ　Ｓｅｒｖｉｃｅｓ作为一种新技术广受关注。Ｗｅｂ　候选服务集合中选择一组服务，使得其ＱｏＳ达到Ｐａｒｅｔｏ最优。　Ｓｅｒｖｉｃｅｓ中的接口定义语言ＷＳＤＬｏ］和内容传输格式ＳＯＡＰ　Ｊ　２服务组合基本模型　已经成为Ｗ３Ｃ的草案和建议标准。然而，在实际应用中，单　本文所采用的服务组合模型为通用的服务覆盖网　Ｊ，其　个Ｗｅｂ服务通常无法满足复杂应用的需求。因此，如何集成　对应互联网的实际场景如图２所示。在互联网中每一个服务　单一服务形成功能更强大的服务组合从而满足不同用户的复　提供节点提供一个或多个服务，如图２的节点　提供　５和　杂应用已成为一个新的研究热点。服务组合广义上可以分为　７两个服务，这样形成服务覆盖网。　手工组合、半自动组合和自动组合　Ｊ。在Ｗｅｂ环境中，服务　是经常变化的，手工组合的方式并不能满足实际的应用需求，　而完全智能化的自动组合方式是一个非常复杂的过程，因此，　很多关于服务组合的应用和研究工作都侧重于半自动方　式　】。半自动服务组合方式首先由业务人员根据特定的行业　背景，建立适合具体应用需求的通用服务组合业务模型，服　务组合业务模型由多个服务节点组成，各服务节点包含功能　需求描述，但不指定具体的服务调用实例，如图１所示。　圈２服务曩董阿络　服务覆盖网中的每个提供服务的节点具有不同的资源能　力，可作如下定义：　％：Ｓｅｌｅｃｔ　ｓ：Ｓｔａｒｔ　Ｅ：Ｅｎｄ三：ｐａｒａｌｌｅｌ　定义１系统中每个提供服务的节点　拥有的有效多维　圈１服务组合业务鳍构　资源为　＝（，　，，　“，ｒｍ　），ＶＥ｛１＂－提供服务的节点数），表　在Ｗｅｂ环境中，满足相同功能需求而具有不同ＱｏＳ参数　基金项目：国家自然科学基金资助项目（６０５７３１２７）　（如执行时间、费用、可靠性等）的Ｗｅｂ服务实例存在多个，　作者倚介：刘莉平（１９７１－－），女，博士研究生，主研方向：网格计算，　如何从中选择满足各服务节点功能需求的具体服务，形成一　面向服务计算；陈志刚，教授、博士；刘爱心，高级工程师　个可执行的服务链来完成用户的需求称为服务动态组合问　收稿日期：２００７—０３－１０　Ｅ－ｍａｉｌ：ｃｓｕｌｉｕ＠１６３．ｃｏｍ　一１Ｏ４一　维普资讯 http://www.cqvip.com

示节点　提供的资源维数为ｍ维，第ｆ维的资源为ｒ　，如　ＣＰＵ大小、内存、Ｉ／Ｏ等节点处理能力的资源量。　定义２一个Ｗｅｂ服务可以用下面的表达式（１）来描述：　ＷＳｉ＝（　Ｏｉ，Ｒｅｓｌ，ＯｏＳｉ）　（１）　子迄今为止搜索的最好位置记为Ｐｆ＝　Ｐ　…　ｄ），整个粒子　迄今为止搜索到的最好位置记为Ｐｇ＝ｆ　Ｐ　Ｐ　…，Ｐｇｄ）。对于每　个粒子，其第ｄ维（１≤ｄ≤Ｄ）根据如下等式变化：　一其中，ＷＳｉ是Ｗｅｂ服务的名字；　是该服务的输入集合，０ｆ　ｒ　＝ｗｘＶ￣ｄ＋ｃ１．ｒｌＸ（￣ｘ　）＋ｃ２．　×（％一　）　Ｊ　＝　Ｉ　＝一　是该服务的输出集合。ＱｏＳｉ是表示服务ＷＳｌ在服务质量参数　上的约束，对于服务ＷＳｉ的共有服务质量维数ａｆ＝　．　，　ｑｉ，２，…，ｑｉ，ｋ　Ｊ，对于服务ＷＳＩ存在最小可接受的服务质量级别　ｑｉ““＝（　““，　２ｍｌｎ，…，吼Ｋｍｉｌ１），Ｒｅｓ　是表征服务执行需要系统　资源的情况，对于服务Ｈ　言，假定要使其具有服务质量Ｑ　，　有映射函数，是服务Ｈ　得到服务质量Ｑｆ时所需系统资源大　小，　ａｊ）＝　（ｑｆ１，ｑｆ２，…，ｑｊｋ））＝ｒ／＝｛ｒ　ｆ，ｒ２　“，　ｆ　Ｊ，其中，ｒ，　表示服务Ｈ　得到服务质量Ｑｆ所需的资源向量，一　表示服务　ｉｆ　ｉｆ　＞　＜一　（２）　Ｌ　Ｘ＿ｄ＝Ｘｌｄ＋ｖｉｄ　其中，ｒｌ，ｒ２是介于【０，１】之间的随机数；Ｃ１，Ｃ２是加速度系数；　ｗ是惯量因子；Ｖｍ　是常数，限制了速度的最大值，由用户　设定。　３．２粒子群思想和模型　基于粒子群思想的服务组合算法从多目标优化的角度出　ＷＳｉ在得到服务质量为Ｑｆ在第１维资源上所需的资源量。　定义３服务组合业务图（Ｓｅｒｖｉｃｅｓ　Ｃｏｍｐｏｓｉｔｉｏｎ　Ｂｕｓｉｎｅｓｓ　Ｇｒａｐｈ，ＳＣＢＧ）：依据服务组合的业务逻辑关系确定的各服务　类型间相互关系的组合图，如图２所示。在服务组合业务逻　辑图中的服务是指一种服务的类型，而不是具体的服务实例。　用二元组可以描述为ＷＣＬ＝（Ｈ，ｍ　，ｃｃ），其中：　ｏｄｅｌ＝｛　，　，…，　｝为服务类型的集合，　，　，…，　表　示服务组合的Ⅳ个参与的服务类型；　ｃｃ　Ｗｍ０ｄｅｌ　ｘｇｘＨ，ｍ　ｌ为组合控制的集合，控制结构运算　符矿定义为从Ｈ，ｍ　ｌ到Ｈ，ｍ涮的控制转换关系，ＷｆｌＶＩＣ定义　的４种基本模型Ｌ５　为：顺序，选择，并行，循环。　定义４服务组合实例图：将服务覆盖网中的实际服务　实例依据定义３的服务组合业务逻辑图组成如图３所示的服　务组合实例图。　／　／　、、　囊　ｐ　／，＿、　．　＼　｜　。＼１－　／　Ｃ　圈３　Ｉｔ务姐合实倒　定义ｓ服务组合的多约束条件下多目标最优：对于服　务组合业务逻辑图，存在多个从源到终点的组合路径，依次　从服务组合实例图中选取合适的服务形成所有可能的服务组　合，存在ｋ（ｋ≥２）个约束条件ｃ　（ｆ＝１，２，…，ｋ），如执行时间、执　行代价不高于（低于）某个值，同时，每一条从源点　到目的　点　的服务组合Ｐ具有ｍ（ｍ≥２）个非负的性能度量准则　，　，１，…，，州，Ｐ为多约束条件下多目标最优非劣路径，当且仅当　ＶＰ　（尸　ＣＰ），在Ｐ和Ｐ　均满足约束ｃ　的条件下，对于所有的　度量准则均使得　（ｐ）　＝　（ｐ　），且至少存在一个目标ｆ满足　．　（ｐ）　．　（ｐ　）。其中，　和＞－分别表示度量准则之间的不劣于　和优于关系。　３基于粒子群算法的ｗｅｂ服务组合　３．１基本ＰＳＯ　粒子群算法由Ｋｅｎｎｅｄｙ　Ｊ等在１９９５年提出，是一种基于　迭代的进化计算方法　Ｊ。基本ＰＳＯ公式如式（２）所示。设搜索　空间是Ｄ维的，粒子群中第ｉ个粒子的位置用ＸＦ（　１　ｆ２’…，　）　表示，第ｆ个粒子的速度表示为Ｖｉ＝（Ｙｉｌ，Ｙｆ２’…，Ｖｉ１ａ）。第ｉ个粒　发，搜索服务集合中　和Ｅ之间满足所有约束条件的一组多　目标Ｐａｒｅｔｏ非劣解。基本思想是：首先产生一定数目的粒子　群，每一个服务组合流程编码为一个粒子，每一个粒子利用　本身信息、局部较优信息和全局较优信息３个信息，产生具　有更高目标准则值的新粒子。这一过程不断进行，实现在解　空间的并行全局搜索；算法停止时，得到一组粒子集合，对　应了多条收敛于Ｐａｒｅｔｏ优化或近似优化路径的组合集。算法　流程见算法１。　算法１　（１）Ｉｎｉｔｉａｌｉｚｅ　ｐａｒｔｉｃｌｅ—ｓｗａｒｍ　ＰＳ／／初始化粒子群　（２）ＤＯ　（３）　ｆｏｒ　ｉ＝ｌ　ｔｏ　ｐａｒｔｉｃｌｅ＿ｓｗａｒｍ＿Ｓｉｚｅ　（４）　ｃａｌｃｕｌａｔｅ　ｔｈｅ　ｆｉｔｎｅｓｓ　ｖａｌｕｅ　ｆ（ｘ１）ｏｆ　ｔｈｅ　ｉｔｈ　ｐａｒｔｉｃｌｅ　（５）　ｉｆ　ｆ（ｘ１）＞ｆ（ｐｉ）ｔｈｅｎ　ｐｉ＝ｘｉ　（６）ｐｇ＝ｍａｘ（Ｐ１）　（７）　ｆｏｒ　ｄ＝ｌ　ｔｏ　ＤｉｍｅｎｓｉｏｎＳｉｚｅ　（８）　Ｖｌｄ＝ｗ×Ｖｉｄ＋ｃｌ×ｒｌ×（ｐｉｄ－Ｖｉｄ）＋ｃ２×ｒ２×（ｐｇｄ－Ｖｉｄ）　（９）Ｘｉｄ－－Ｘｉｄ＇［＇Ｖｉｄ　（１０）　Ｖｉｄ＝Ｖｍａｘ　ｉｆ　Ｖｉｄ＞Ｖｍａ＾　（１１）　Ｖｌｄ－－－Ｖｍａｘ　ｉｆ　Ｖｉｄ＜－Ｖｍａｘ　（１２）　Ｎｅｘｔ　ｄ　（１３）Ｎｅｘｔｉ　（１４）Ｗｈｉｌｅ　ｔｅｒｍｉｎａｔｉｏｎ　ｃｒｉｔｅｒｉｏｎ　ｉｓ　ｍｅｔ　３．３服务组合算法的设计与分析　３．３．１　编码策略　首先对图２中的各个服务节点按顺序编号；其次，增加　虚拟服务　和Ｅ作为服务组合的起点和终点，ＳＣＢＧ中节点　的个数为粒子的Ｄ维，因为每一个给定的服务组合所包含的　服务节点数目相同，所以采用整数定长编码的方式，将组合　路径映射为粒子空间中的个体；粒子体中第１个和最后一个　粒子位置总是ＳＣＢＧ图中的顶点　和Ｅ，取值为－１，粒子位　置的每一维的值是ＳＣＢＧ图中相应位置对应的某一服务实例　的编号，如果对应位置的服务不在组合路径中，则取０。　假设粒子Ｘｉ＝　ｍＸｆ２’－．．，　）表示服务组合路径的一个解，　其中，Ｄ为ＳＣＢＧ图中顶点的个数，其编号是从上到下，从　左到右编号；Ｘｆ　和Ｘ／Ｄ的取值是－１，其他墨，的取值为０或者　服务实例的编号（正的整数）。　例如，对于图２中的服务业务逻辑图对应的粒子编码如　下所示：ｘ（一１，０，２，０，０，５，０，０，９，一１）表示一条经过第２号、第５号、　第９号服务实例的组合路径。　３．３．２初始组合粒子群集的生成　本文利用随机方法产生一组满足约束条件的从　到　的　维普资讯 http://www.cqvip.com

初始组合路径集。具体过程见算法２，设初始粒子群规模为Ⅳ，　Ｃｏｎｓｔｒ（ＰＳ）表示从集合Ｐｓ中选取满足约束的组合路径；　ＲａｎｄＳ（Ｓ，　表示利用随机方法选择ｓ到　的一条路径。　算法２　ｐａｒｔｉｃｌｅ—ｓｗａｒｍ　ＰＳ　Ｂｅｇｉｎ　（１）ＰＳ　０　（２）ｗｈｉｌｅ（ＩＰＳＩ＜Ｎ）　（３）ＰＳ，－ＰＳ　Ｕ　Ｃｏｎｓｔｒ（ＲａｎｄＳ（Ｓ，Ｔ））　（４）Ｇｏｔｏ（２）　（５）Ｏｕｔｐｕｔ　ＰＳ　Ｅｎｄ　３．３．３粒子适应值计算　．　本文中采用加权综合的方法来求适应值。　对于每一条组合路径用ｆ￣Ｃｘ），ＬＣｘ），．・、　∽分别代表对ＱｏＳ　因素ＱｏＳ（ａ￣），ＯｏＳ（ｏ　），ＱｏＳ（　），ＱｏＳ（　）等进行ＱｏＳ计算的　函数。希望在ＱｏＳ上得到满足以下目标的优化目标：　，（　）＝Ｆ（ｍａｘｆｌ（ｘ），ｍｉｎｆ２（ｘ），ｍｉｎｆ３（ｘ），ｍａｘｆ４（ｘ），ｍａｘｆｓ（ｘ））　（３）　由于式（３）中的ｍａｘ函数可以通过转换化为ｍｉｎ函数，因　此用加权法求得每一条组合路径的综合服务质量函数为　，（　）＝ｎｆｉｎ∑　（　）≥ａ　，　∈Ｘ　（４）　３．３．４粒子的运算规则　至此，算法１中只有第８行和第９行还没有定义。第８　行、第９行的作用分别是计算粒子的飞行速度和更新粒子的　位置，更新粒子位置采用“加”运算。本文的策略是将粒子　的飞行速度　定义为服务质量的值。粒子位置的更新就是将　服务替换为与此服务质量最接近的服务实例，因此“加法”　（＋）的定义为将粒子墨的第Ｄ维位置更换为与　服务质量最　接近的服务实例。下面通过一个实例来说明。　在图１中，假设在计算前　的值为０．３５，并取　Ｗ，　１，ｒｌ，ｐｍ，６＇２，ｒ２分别是０．２，０．４，０．５，０．２３，０．１２，０．２５，则计算　出新的　的值为０．３６，则说明粒子在对第Ｄ类服务的选取　ＱｏＳ高的服务实例。粕＝ｘｉｄ＋　的计算用式（５）完成：　ｘｉｄ＝ｆ（（，（　）＋ｖｉｄ））　（５）　式（５）中的，函数是计算出　ｄ所对应的服务实例的ＱｏＳ，计　算出值为５１３６，７函数是求得与ＱｏＳ值最接近的服务实例，　为ｓ８，与，是反函数。　４实验分析　４．１实验场ＩＩ设置　实验环境为１００　Ｍｂ／ｓ局域网，微机配置为Ｐｅｎｔｉｕｍ　４，　２．５２　ＧＨｚ／５１２　ＭＢ，Ｗｉｎｄｏｗｓ　２００３　Ｓｅｒｖｅｒ／ＸＰ，用Ｊａｖａ实现。　实验所用服务组合业务模型如图１所示，模型中每一类服务　节点对应实际中的一组服务实例集合，共有９种服务（ｗｓ　，　ＷＳ２，…，ＷＳ９）。每一个服务实例由一个线程来模拟。各个服　务群中服务的ＱｏＳ参数采用随机方法在一定范围内生成，参　数取值范围设定为０　ｓ＜Ｔｉｍｅ　６０　Ｓ，Ｏ＜Ｃｏｓｔ≤１００，Ｏ＜Ｒｅｐｕｔｅ＜．　１０，Ｏ＜Ｒｅｌｉａｂｌｅ＜１，最小信誉等级为２，最小可靠性为０．１。　４１２算法ｊ－｜数设置　根据３．３．１节算法编码，得到如下所示的服务组合模型的　粒子编码实例的形式：　Ｉ＝　Ｉ　！　ｌ　ｌ　　ｌ鲍Ｉ　２　Ｉ型　２　Ｉ　！　！Ｉ　２　ｌ：：！Ｉ　其中，Ｓｃ（１ｉ）表示服务节点１对应的服务集合ＳＣｉ（ｉ∈ＵＩ１≤　Ｊ≤８））中所选具体服务的编号为ｉ。　对于图１所示的组合业务模型，共有２条组合路径。　一１０６＿一　第１条是选择（ｓ—ｗｓ２一Ⅵ　５一Ⅵ　８一Ｅ），其ＱｏＳ指标的计算　公式如式（６）所示，第２条是（ｓ—ｗｓ１一（（Ⅵ　一Ⅵ　６一Ｅ），　（Ⅵ皤４一Ⅵ　７一Ｅ））），其计算公式如式（７）所示。　）　ｔｚ＋ｔｓ＋ｔｓ　五（　Ｇ　Ｇ　（６）　ｌ　㈨＝ＲｅＰ２ｘＲｅｐ５ｘＰｅｐｓ　Ｌ－工㈨＝Ｒｅｌ２ｘｇｅ／￣×忍　ｒ．　（　＝‘＋ｍａｘ（（ｔ３＋　），（ｔ４＋　））　ｊ　㈨　ｑ＋ｃ３＋ｃ，＋ｃｏ＋ｃ７　（７）　ｆ３（ｘ）＝Ｒｅｐ￣ｘｒｆｌｎ（（Ｒｅｐ３ｘＲｅｐ６），（Ｒｅｐ４ｘＲｅｐ７））　ｌ　（　＝蹦Ｘｒｌｉｆｎ（（Ｒｅｌ３ｘＲｅｌ６），（Ｒｅｌ４ｘＲｅＬ，））　迭代次数　圈４算法的执行时问　实验还对线性规划法、采用服务个数为粒子维数的编码　算法以及本的算法的效率进行了比较。分别给定有１００，１５０，　２００，２５０，３００个服务实例情况。它们达到最优解ＱｏＳ指标相　差在２％以内所需要的时间如图５所示。　服务规模　圈５不同算法执行时间的比较　５结束语　本文提出的基于粒子群算法的服务组合算法，对于构建　基于互联网的复杂组合服务的应用具有一定意义。进一步的　工作是根据服务组合的具体实际，进行基于ＰＳＯ算法的优化　与改进。　（下转第１１２页）　维普资讯 http://www.cqvip.com

４实例　前面的分析已表明，采用时间距离并不能有效地减少网　（４）计算距离　根据式（５）和式（８）可计算得到各网页间的距离，见表１。　从表１中可看到，Ａ，Ｂ和Ｄ两两之间的距离都小于它们与ｃ　页组簇后ＨＴＴＰ／１．１持续连接所带来的额外开销。为了与之比　较，这里仍使用该例子中的数据，并使用本文提出的方法来　衡量网页间的距离。　根据前文的叙述，计算网页间距离的步骤如下：　（１）构建超链关系图和计算一步转移概率矩阵　根据条件可得到各网页间（包括ＥＮＤ）的超链关系图和各　网页间的（一步）状态转移图，如图２所示。　Ａ　１０　Ａ　１　之间的距离。故一般的聚类算法都会将Ａ，Ｂ和Ｄ归为一簇，　将Ｃ归为另一簇。这与前面分析得出的结论一致。　表１基于马尔可夫链灼罔页问灼甩离　５结束语　—　～　～　本文提出了一种基于马尔可夫链的衡量网页间距离的方　法，该方法不仅考虑了用户访问的时间相关性还考虑了用户　／　的访问路径。实例表明，与基于时间相关性的衡量网页间距　图２　罔页问灼超链关系和状态转移　离的方法相比，采用该方法能更有效地减少网页组簇后　ＨＴＴＰ／１．１持续连接所带来的额外开销。　用状态０表示ＥＮＤ，用状态１，２，３和４分别表示网页　Ａ，Ｂ，Ｃ和Ｄ，那么一步状态转移矩阵为　参考文献　１　Ｏ　Ｏ　Ｏ　Ｏ　［１］Ｙａｎｇ　Ｃｈｕｓｉｎｇ，Ｌｕｏ　Ｍｏｎｙａｎ．Ａ　Ｃｏｎｔｅｎｔ　Ｐｌａｃｅｍｅｎｔ　ａｎｄ　Ｍａｎａｇｅｍｅｎｔ　Ｏ　Ｏ　１　Ｏ　Ｏ　Ｓｙｓｔｅｍ　ｆｏｒ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｗｅｂ—ｓｅｒｖｅｒ　Ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｐ＝１　Ｏ　Ｏ　Ｏ　Ｏ．２５　０．７５　２０ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔｉｎｇ　Ｓｙｓｔｅｍｓ．　１　Ｏ　Ｏ　Ｏ　Ｏ　（６）　Ｔａｉｐｅｉ，Ｔａｉｗａｎ，Ｃｈｉｎａ：Ｉｓ．ｎ．］，２０００：６９１－６９８．　１　Ｏ　Ｏ　Ｏ　Ｏ　［２］Ｃｈｅｎ　Ｙａｎ，Ｑｉｕ　Ｌｉｌｉ，Ｃｈｅｎ　Ｗｅｉｙｕ，ｅｔ　ａ１．Ｃｌｕｓｔｅｒｉｎｇ　Ｗｅｂ　Ｃｏｎｔｅｎｔ　ｆｏｒ　（２）设置转移概率最大步数及加权系数　Ｅｆｉｆｃｉｅｎｔ　Ｒｅｐｌｉｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１０ｔｈ　Ｉｎｔｅｍａｔｉｏｎａｌ　根据条件，平均会话长度为（３ｘ１０＋２ｘ３０）／４０＝２．２５，因　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｔｗｏｒｋ　Ｐｒｏｔｏｃｏｌｓ．ＩＳ．１．】：ＩＥＥＥ　Ｐｒｅｓｓ，２００２：　此，ｌ＝ｒ２．２５１—１＝２，　＝２／３，　以＝１／３。　１６５—１７４．　（３）计算关联转移概率矩阵和关联程度矩阵　［３］Ｎｇ　Ｃ　Ｐ，Ｗａｎｇ　Ｃｈｏ—ｌｉ．Ｄｏｃｕｍｅｎｔ　Ｄｉｓｔｒｉｂｕｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｌｏａｄ　根据定义１，　Ｂａｌａｎｃｉｎｇ　ｏｎ　ａｎ　Ｅｘｔｅｎｓｉｂｌｅ　Ｗｅｂ　Ｓｅｒｖｅｒ　Ａｒｃｈｉｔｅｃｔｕｒｅ［Ｃ］／／　ｒＰｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１ｓｔ　１ＥＥＥ／ＡＣＭ　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　ｔｒａｎｓｆｅｒ＝　Ｐ。　＋　Ｐ牡　＝２　ｘＰ＋｛×ＰｘＰ＝　Ｃｌｕｓｔｅｒ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　ｈｔｅ　Ｇｒｉｄ．ＩＳ．１．］：ＩＥＥＥ　Ｐｒｅｓｓ，２００１：１４０—１４７．　１　Ｏ　Ｏ　Ｏ　Ｏ　［４］Ｓｕ　Ｚｈｏｎｇ，Ｙａｎｇ　Ｑｉａｎｇ，Ｚｈａｎｇ　Ｈｏｎｇｊｉａｎｇ，ｅｔ　ａ１．Ｃｏｒｒｅｌａｔｉｏｎ—ｂａｓｅｄ　Ｏ　Ｏ　０．６６６７　０．０８３３　０．２５　（７）　Ｗｅｂ—ｄｏｃｕｍｅｎｔ　Ｃｌｕｓｔｅｒｉｎｇ　ｆｏｒ　Ａｄａｐｔｉｖｅ　Ｗｅｂ—ｉｎｔｅｒｆａｃｅ　Ｄｅｓｉｇｎ［Ｊ］．　０．３３３３　Ｏ　Ｏ　Ｏ．１６６７　０．５　１　Ｏ　Ｏ　Ｏ　Ｏ　Ｋｎｏｗｌｅｄｇｅ　ｎａｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，２００２，４（２）：１５１—１６７．　１　Ｏ　Ｏ　０　０　［５］Ｓｈｏｕ—Ｈｓｕａｎ　Ｓｔｅｐｈｅｎ　Ｈｕａｎｇ，Ｒｏｄｒｉｇｕｅｚ　Ｃ　Ｈ　Ｍ，Ｔｏｒｒｅｒｏ　Ｊ　Ｕ　Ｑ，ｅｔ　ａ１．　Ｅｘｐｌｏｒｉｎｇ　Ｓｉｍｉｌａｒｉｔｙ　Ａｍｏｎｇ　Ｗｅｂ　Ｐａｇｅｓ　Ｕｓｉｎｇ　ｔｈｅ　Ｈｙｐｅｒｌｉｎｋ　根据定义２，　ｒｅｌａｔｅ：＝—ｒｔａｎｓｆｅｒ＋　ｔｒａｎｓｆｅｒＴ　Ｓｔｒｕｃｔｕｒｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　２　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ：Ｃｏｄｉｎｇ　ａｎｄ　Ｃｏｍｐｕｔｉｎｇ．ＩＳ．１．］：ＩＥＥＥ　Ｐｒｅｓｓ　１　＋Ｏ　Ｏ．１６６７　０．５　０．５一　２００４：３４４—３４８．　Ｏ　Ｏ　０．３３３３　０．０４１７　０．１２５　［６］Ｊｅｈ　Ｇ　Ｗｉｄｏｍ　Ｊ．ＳｉｍＲａｎｋ：ａ　Ｍｅａｓｕｒｅ　ｏｆ　Ｓｔｒｕｃｔｕｒａｌ—ｃｏｎｔｅｘｔ　０．１６７　０．３３３３　０　０．０８３３　０．２５　（８）　Ｏ．５　０．０４１７　０．０８３３　０　０　Ｓｉｍｉｌａｒｉｔｙ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　８ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｏ．５　０．１２５　０．２５．０　０　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．ＩＳ．１．］：　ＡＣＭ　Ｐｒｅｓｓ．２００２：５３８—５４３．　（上接第１０６页）　’　参考文献　ｏｆ　ｈｔｅ　１８ｔｈ　Ｉｎｔ’ｌ　Ｃｏｎｆ．ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｓａｎ　Ｊｏｓｅ：ＩＥＥＥ　Ｐｒｅｓｓ，　［１］ＷＳＤＬ．Ｗｅｂ　Ｓｅｒｖｉｃｅｓ　Ｄｅｓｃｒｉｐｔｉｏｎ　Ｌａｎｇｕａｇｅ　１．１．Ｗ３Ｃ　Ｎｏｔｅ［Ｚ］．　２００２：２９７—３０８．　ｆ２００１—０９—０９）．ｈｔｔｐ：＃ｗｗｗ．ｗ３．０ｒｇ／ＴＲ／ｗｓｄ１．　［５］Ｚｅｎｇ　Ｌｉａｎｇｚｈａｏ，Ｂｅｎａｔａｌｌａｈ　Ｂ，Ｄｕｍａｓ　Ｍ．Ｑｕａｌｉｔｙ　Ｄｒｉｖｅｎ　Ｗｅｂ　［２］ＳＯＡＲ　Ｓｉｍｐｌｅ　Ｏｂｊｅｃｔ　Ａｃｃｅｓｓ　Ｐｒｏｔｏｃｏｌ　１．２．Ｗ３Ｃ　Ｒｅｃｏｍｍｅｎ—　Ｓｅｒｖｉｃｅ　Ｃｏｍｐｏｓｉｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅⅥ，ⅥｒＷ’０３．Ｂｕｄａｐｅｓｔ：ＡＣＭ　ｄａｔｉｏｎ［Ｚ］．ｆ２００３—０３—０３）．ｈｔｔｐ：＃ｗｗｗ．ｗ３．ｏｒｇ／ＴＲ／ｓｏａｐ．　Ｐｒｅｓｓ，２００３：４１　１－４２１．　［３］Ｓｈａｌｉｌ　Ｍ，Ｗａｌｋｅｒ　Ｄ　Ｗ　Ｇｒａｙ　Ｗ　Ａ．Ａ　Ｆｒａｍｅｗｏｒｋ　ｆｏｒ　Ａｕｔｏｍａｔｅｄ　［６］金海，陈汉华，吕志鹏，等．ＣＧＳＰ作业管理器合成服务的ＱｏＳ　Ｓｅｒｖｉｃｅ　Ｃｏｍｐｏｓｉｉｔｏｎ　ｉｎ　Ｓｅｒｖｉｃｅ—ｏｒｉｅｎｔｅｄ　Ａｒｃｈｉｔｅｃｔｕｒｅｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ　优化模型及求解［Ｊ】．计算机学报，２００５，２８（４）：５７８—５８８．　ｔｈｅ　ＥＳＷＳ’０４．Ｈｅｒａｋｌｉｏｎ，Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００４：２６９—２８３．　［７］Ｋｅｎｎｅｄｙ　Ｊ，Ｅｂｅｒｈａｒｔ　Ｒ　Ｃ．Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　［４］Ｂｅｎａｍｌｌａｈ　Ｂ，Ｄｕｍａｓ　Ｍ，Ｓｈｅｎｇ　Ｑ　ｚ，ｅｔ　ａ１．Ｄｅｃｌａｒａｔｉｖｅ　Ｃｏｍｐｏｓｉｉｔｏｎ　ｈｔｅ　ＩＥＥＥ　Ｃｏｎｆ．ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ．Ｐｅｒｔｈ：ＩＥＥＥ　Ｐｒｅｓｓ，１９９５：　ｎａｄ　Ｐｅｅｒ－ｔｏ—ｐｅｅｒ　Ｐｒｏｖｉｓｉｏｎｉｎｇ　ｏｆ　Ｄｙｎａｍｉｃ　Ｗｅｂ　Ｓｅｒｖｉｃｅｓ［Ｃ］／／Ｐｒｏｃ．　】９４２一】９４８．