2. 哈尔滨工程大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001;
3. 审计署 计算机技术中心, 北京 100830
2. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China;
3. IT Center, National Audit Office, Beijing 100830, China
随着分布式计算技术的发展,新的计算范型,如网构软件[1]、网络化软件[2]、面向服务的软件系统[3]不断涌现.这类系统的典型特征是:以独立开发商及运营商提供的自治模块如Web服务为基础构成单元,以服务间的按需聚合为主要运行模式,以动态适应、随需演化作为其运行特征.这类系统中的构成元素由传统的软件开发中的类和方法变为粒度更大、结构更复杂的服务及子系统,在不可预测的用户需求驱动下,通过组合和协同形成较大粒度的业务社团,形成错综复杂的交互关系,使得系统的整体行为难以预测和控制.这类服务系统一般没有全局的设计,没有固定的业务目标,每个组成个体为了自身的利益最大化而提供服务.这类系统松散地组合在一起,根据系统外部的刺激(如用户需求)或自身的利益而演化.因此,如何理解和分析这类超大规模复杂系统,就成为必须应对的问题.
目前,对于服务系统的行为分析主要是从个体Web服务或组合服务的角度,采用形式化方法,如Petri网[4]、p演算[5]、进程代数[6]等进行分析,考察服务及其组合的行为兼容性、功能分析、故障诊断等.这些工作大多考察服务个体或组合服务的行为特征,缺乏对服务系统及其所处环境整体的分析.事实上,传统的软件工程方法对于这类超大规模网络化软件系统已经无法适用[7, 8].当系统组成元素达到一定数量级后,就会出现认知复杂性[9]问题,即使是简单的交互关系也会产生涌现现象,从而无法进行有效的分析与管理.例如,Web服务作为服务软件系统的基本构成元素,一般是为同时多个业务流程和需求服务的,这使得服务间会存在多种交互关系,这些关系交织在一起,共同决定了系统的行为及性能.实际业务系统中存在众多互相交织的业务流程,如图1所示.图1中的服务S被多个业务流程使用,在多个用户需求的影响下,其行为很难由单独的业务流程所决定.特别是当服务数目激增时,海量的组合服务间的交互行为越来越复杂,形成一个超大规模复杂系统,无法采用分解的方法进行分析.单独分析任何组合服务流程都没有办法准确判断服务的行为及性能,系统受个体行为拓扑和环境的影响.这种情况下,有必要采用新的手段从整体的角度进行分析.
复杂网络[10, 11, 12]作为研究复杂系统的有力工具,已经在社会分析、生物计算等领域得到了广泛应用.将服务看作网络中的节点,将服务间的组合协作关系看作网络中的边,就可以把面向服务的软件系统看作是一个复杂网络,从而审视系统的整体特性和分析.分析服务交互行为的一个重要手段是对其演化行为进行建模分析,发现其中蕴含的规律.从面向服务的软件系统整体入手,考察系统尺度下的服务个体交互行为及其性能分析.从系统论角度来看,面向服务的软件系统是一个典型的复杂系统,研究其动力学行为具有重要的意义.
为了理解和管理这样一类复杂系统,一个重要的研究问题就是如何去建模和仿真这类自治的复杂系统的动态行为,从而预测实际应用背景下服务间的交互行为.针对上述问题,本文提出一种面向服务的软件系统的生长演化模型,借鉴复杂网络相关建模思路,根据真实Web服务数据及其关键特征对服务执行行为进行模型抽象,构建一种具有优化设计特性的基于服务动态行为的服务网络演化模型.该模型能够刻画服务交互行为拓扑特性生成机理,并可以作为服务交互行为的拓扑产生器,为理解服务系统的行为模式和演变规律提供有意义的研究方法与手段.与以往组合服务优化选取、服务替换等具体问题不同,我们的研究对象是由海量Web服务构成的服务软件系统,而不是面向特定需求的个体组合服务.因此,我们在组合服务选取等“个体”优化方法基础上,总结了4种共性演化特征,建立了服务执行行为演化模型,期望分析当大规模Web服务软件系统上存在大量组合服务共同执行时,会产生何种复杂交互行为,系统的结构会是何种构型.通过对系统整体拓扑形态的分析,可以给出系统整体特性,如性能指标的演化趋势,从而为构建大规模服务软件系统提供指导.
为了避免以往仿真模型脱离实际应用情形的缺点,我们以大规模真实Web服务WSDL数据为基础,通过解析其语法特征提取出方法参数接口,对可能发生的服务交互进行匹配,构建出服务结构网络作为服务执行行为的约束前提.然后,基于服务交互的组合执行、动态重组、择优连接等若干特性,结合服务非功能属性等特征,建立了服务执行行为演化模型.与传统复杂网络演化模型如BA模型[13]相比,我们提出的模型充分考虑了服务交互行为的特点,基于真实We b服务数据的实验也保证了仿真结果的可信性.基于所提出的服务执行行为交互演化模型我们发现:与传统的软件系统的层次性结构有所不同,由自治的Web服务所构成的软件系统具有更强的模块性;与系统中个体服务演化规则如择优连接及动态重组相比,服务结构网络的性质对系统最终形态具有更重要的影响.
本文的主要贡献在于:
(1) 从复杂系统的角度分析了服务软件系统的特征和演化过程,给出了服务择优选择、组合交互、动态重组等行为特征描述.
(2) 基于Web服务选择策略及自适应规则,提出一种新颖的基于复杂网络的服务软件行为演化模型.在大量真实服务数据的基础上,考察了面向服务的软件系统的演化仿真并分析其拓扑特征,与传统软件所构成的软件网络进行了对比,指出面向服务的软件系统特有的特征规律.
(3) 上述模型可作为一个基于真实服务数据的可信的服务执行行为数据仿真生成器,为服务挖掘、服务行为分析等问题提供了数据基础.
本文第1节给出与本文相关的部分工作.第2节给出服务系统演化模型的建模思想,分析并总结服务的行为特征.第3节给出服务行为演化模型.第4节给出仿真实验和对比分析.最后给出结论.
1 相关工作面向服务的软件的核心理念是以SOA为基础架构,在交互的服务资源之间构建松耦合的协同软件体系,通过服务元素交互来实现增值的业务逻辑.对于组合服务的行为,目前主要是从形式化建模的角度展开研究工作.邓水光等人[5]在服务视图概念的基础上给出了Web服务行为兼容性的相关定义,并提出一种基于p演算的服务行为兼容性的判定方法;胡昊等人[14]提出了一种用Petri net对服务行为和服务质量进行统一建模的框架,用于在服务的查找和替换中综合判断服务行为和服务质量的一致性;张良杰等人 [15]研究了用于研究语义Web服务行为的描述及基于功能语义的服务发现.以上研究大多集中在对服务抽象行为和语义分析,缺乏对服务在特定环境下的执行行为的分析,当执行环境发生变化时,容易产生服务性能下降甚至服务失效等问题.因此,另一种方式是基于服务使用日志的行为分析,Gaaloul等人[16]考虑了活动顺序,服务发现依靠表示服务行为关联的图之间的模式匹配.张明卫等人[17]在对服务交互行为挖掘等方面做了部分工作.
对于越来越复杂的软件系统,网络化软件观[3]的提出,使得复杂网络成为分析复杂软件行为规律的有效工具.越来越多的研究者认为:软件系统其实代表了一类人工复杂网络,对其结构和行为的研究应当借鉴复杂系统、图论等研究的相关原理和方法.对此,Myers[18],vaIverde[19]和Moura[20]等人分析了传统软件的拓扑结构,他们以类图、调用关系图作为研究对象,使用有向网络来表示软件系统的结构,发现其结构具有非常明显的“小世界”和“无标度”特征.
对于服务网络,由于缺乏有代表性的实证数据,目前的研究成果还较少.Hyunyoung[21]研究了Web服务所构造的服务网络,通过匹配服务方法参数得到服务网络,也验证了Web服务网络满足“小世界”和“无标度”特性.服务网络相对于软件网络,其计算元素和结构拓扑均有较大的不同,计算元素间的主要关系由继承和依赖转变为服务间的组合.同时,服务间的交互质量和可靠性也相对传统软件具有较大的变化空间.另外,在以往的网络分析中,节点的属性往往被忽视,而单个服务节点自身的属性、动力学行为对整个系统结构的影响是不容忽视的.
2 建模思想一般来说,由Web服务构成的服务软件系统中具有很多不确定性,这主要源于以下几个因素:(1) Web服务通常由不同的运营商运行,因此具有不同的服务质量;(2) 服务软件系统一般面对不确定的用户需求,这会带来不可预知的服务使用模式;(3) Web服务所在的网络环境的性能是不确定的.这些复杂因素综合在一起,使得我们很难分析或预测系统的整体运行状态.为此,我们提出一种面向服务的软件系统的演化模型,希望通过分析系统的关键影响因素,建立系统的行为演化模型,从而分析系统的关键特征,为系统的构建和管理提供指导.
基于服务的软件系统具有复杂程度高、状态/行为混合、用户需求/网络环境动态变化等特点,将服务软件系统建模为复杂网络进行分析是有效的方法.将服务作为节点,服务间的参数匹配关系作为边,可以得到体现服务间潜在调用关系的服务结构网络[21];将服务操作间的执行交互关系作为边,则会得到体现服务执行关系的服务行为网络.这两类网络分别从结构和行为的角度刻画了Web服务之间的交互关系.相关工作[21, 22]对Internet上的大规模真实Web服务的实证研究表明,Web服务网络具有明显的幂律分布特性.而幂律特性源于网络中固有的择优选取特征[10],这种现象在Mashup服务合作网络[22]、Web服务结构网络[21]上均有体现.因此我们认为,服务行为网络应具有以下特征:
(1) 协同交互:个体服务的组合与协同是服务软件系统应用的主要手段,所以服务网络中的交互一般不是孤立的节点间的交互,而是以组合流程的方式,多个节点间相对固定模式的交互.网络的组成元素应是节点的组合链.
(2) 有限约束:服务软件执行过程中存在网络约束和性能约束,对于网络约束来说,服务所处的网络带宽是有限的,而且服务所具有的处理能力是有限的,所以服务节点的并发交互数是有限的.
(3) 偏好依附:在组合服务选取过程中,用户希望选取满足QoS等约束条件的最优服务,因此,组合服务的选取过程可以视为一个网络中的择优寻路过程.从一个节点出发,寻找QoS较大的后继节点进行优先连接,这个过程可以视为节点的偏好依附过程.
(4) 动态环境:服务所处的环境是高度动态的,网络带宽、硬件负载、用户需求都在快速变化,这使得服务软件执行过程中出现服务动态重组、网络动态变化等行为.
以上特征使服务行为网络具有协同交互、有限约束、动态的特点,而目前的演化模型如BA等,主要针对社会网络、基因网络等变化相对较慢的网络,这使得传统演化模型很难适用.
本文给出一种基于服务动态执行特征的服务行为网络演化模型.我们的建模原则基于以下两个基本思路:首先,按照服务之间可能的交互关系给出一个基础的底层拓扑结构,在其上进行服务执行行为的动力学演化;在服务演化过程中,服务个体的动力学行为反过来会影响网络拓扑的结构.所以我们将服务执行过程体现为一种基于设计优化和环境适应的拓扑演化过程,如图2所示.模型首先根据Web服务的WSDL的结构信息,匹配服务接口参数,建立服务间的逻辑交互关系作为服务结构网络,网络中的边代表了服务节点之间可以进行参数交换,具有潜在的调用关系.然后,将服务结构网络作为基本连通性约束,基于服务交互特点进行演化生长,选取若干节点作为初始点,构建服务行为网络.构建过程分为3个阶段:
• 第1阶段首先获取Web服务数据并对其进行清洗和预处理.根据服务的语法信息匹配服务操作参数,建立服务逻辑交互关系,代表服务间可能发生的调用关系.这个由服务逻辑交互关系构成的服务结构网络可作为服务执行演化时服务间调用关系的基本连通性约束.
• 第2阶段是服务交互执行仿真行为建模.将服务结构网络作为基本连通性约束,从初始服务集中选取若干服务作为组合服务起点,按照组合生长、择优连接、约束演化的等特点定义服务网络生长规则,模拟服务执行行为生成服务组合,构建服务行为网络.
• 第3阶段是动态行为演化.服务网络中的节点和边赋予一定的初始容量,如执行时超过其容量限制,则节点暂时失效,组合节点链进行动态择优边重连.结合服务软件系统中服务行为的特点,仿真实现服务动态重组等行为,并对其进行分析.
3 服务行为网络演化模型由服务为基本元素组成的服务软件系统是一个典型的复杂自适应系统[3],我们采用复杂网络建模的方式对其动态执行行为进行研究,给出如下相关定义:
定义1(Web服务). Ws是一组操作的集合,可以抽象为一五元组s=(P,I,O,E,Q),其中,P为使用服务的前提条件,I为该服务的输入参数集,O为输出参数集,Q为服务质量.
定义2(服务结构网络). 将服务视为网络中的节点,将服务间的参数匹配关系视为边,可以得到一个有向网络Gs(WS,R),称为服务结构网络.其中,WS={wij}为节点集,R={rij}为边集.
定义3(服务交互). 服务交互简记为rij,表示业务流程中服务间的交互执行调用产生的活动信息,可以描述为一个六元组的集合li={(wi,wj,ti,tj,r,o)},其中,
• wi表示发起调用的服务;
• wj表示被调用的服务;
• ti记录服务wi发起调用时的时刻,例如02/01/2009:13:08:21;
• tj记录服务wj响应wi调用的时刻;
• r代表服务wi发起交互调用时传送的输入参数;
• o代表服务wj响应调用所返回的输出参数.
上述服务的交互行为是由用户需求驱动的,按照组合流程方式执行.因此下面给出服务协作网络的定义,表示受同一业务需求驱动的服务交互行为组成的网络:
定义4(业务协作子网). 代表由同一业务需求r驱动的服务间的交互行为序列集合,简记为
compositebehavior={rij,rjk,…,rkl},
大量自治的Web服务进行自主聚合和协同合作,就形成了一个具有复杂交互关系的复杂系统,我们称其为服务行为网络.
定义5(服务行为网络). 将服务视为网络中的节点,将服务间的调用行为视为边,可以得到一个有向网络Gb(WS,R,A),称为服务行为网络,如图3(b)所示.其中,节点集WS={wij}为服务集,边集R={rij}为服务调用行为集合,A为三元组{αij,βij,μi},记录了服务行为网络的信息,其中,符号含义分别为
• αij:服务wi与服务wj的历史交互次数;
• βij:服务wi与服务wj在同一业务需求中的调用距离;
• μi:调用服务wi执行的业务流程个数.
服务行为建模的目标是给出服务交互行为演化的规律,因此在对服务网络进行建模之前,需要解决服务的交互匹配问题,也就是那些服务之间可以发生交互行为.基于WSDL文档,服务间是否可以发生交互需要以下两个条件:一是服务的输入/输出参数必须匹配,二是服务前置条件必须满足.值得注意的是,此处所说的服务匹配关系仅代表服务之间可能发生数据交换和调用关系,它们之间是否真正发生实际调用,是由实际执行时的组合服务流程决定的.
我们首先对服务WSDL数据集进行解析,提取其中的操作名、参数名、参数类型等信息,形成服务操作标签特征集;然后,基于相似性对服务操作进行匹配,得到服务逻辑交互关系矩阵.匹配的过程如图4所示.
进行Web服务的关联匹配时,主要考虑操作输入、输出参数的匹配,目前常用的方式是基于字符串匹配及基于本体的方法.鉴于目前缺少全面而完整的Web服务本体数据集,本文借鉴文献[21]的方法,通过计算参数名称和参数类型来判断服务是否有匹配关系.
对于两个Web服务的操作op1及op2,当操作op1及op2满足如下条件时,称这两个操作可以匹配,即可能进行参数交换:
$match(o{{p}_{1}},o{{p}_{2}})=\left\{ \begin{array}{*{35}{l}}
1, & if\sin (op_{1}^{in},op_{2}^{out})>\theta andop_{1}^{in}.type=op_{2}^{out}.type \\
2, & else \\
\end{array} \right.$
(1)
对于名称匹配,采用WordNet中的相似度测量得出参数间的语义相似度,如果名称相似度超过阈值q,那么二者具有参数上的潜在关联,可能发生交互关系.按照以上方式进行服务匹配计算,可以得到服务间的潜在交互调用关系.具体的伪代码如图5所示.
对服务动态行为进行建模需要解决以下问题:(1) 组合服务执行关系如何建立和演化?(2) 如何描述服务间的交互过程及动态重组合等现象?对于第1个问题,相关研究方法如复杂网络生长模型给出了很好的解答.针对复杂网络的演化机理,Barabasi和Albert提出了无标度网络模型[13],用于解释幂律分布的产生机理,其核心思想是增长和择优两个原则.对于服务行为网络,同样存在着以上两种过程,即服务行为网络是变化的,不断有新服务加入和退出;服务之间的组合采用择优原则,这与现有的基于优化的服务选取方法的目标是一致的.
首先,我们采用随机选取的方法选择组合的初始节点.这是因为对于不确定的大量用户需求,组合服务的使用方式有很多可能.因此,对于组合服务的起始点,我们采用随机方式进行选取.另一个重要的问题是如何择优选择服务节点.与BA的抽象网络生长模型不同,服务执行过程中服务节点的属性对于动态生长行为具有重要的影响.选择一个服务节点的择优概率一般与以下因素相关:
(1) 服务交互强度:令ωij表示节点i与节点j的交互强度,即,服务i和服务j的历史交互次数;有些Web服务节点虽然度比较小,但是与其他节点的交换频度即连接强度很大,因此这些节点很有可能更容易被其他节点连接.
(2) 服务质量:度除了与该节点的存在时间有关,还与服务质量等因素相关,即服务质量好的节点更容易在较短时间内获得大量其他服务的连接,甚至很快超过一些老的节点.令QoSj为服务j的QoS指标,依据现有服务实证网络中呈现的“富者愈富”的无标度特性,一般来说,具有较高交互强度的节点和较高QoS节点具有较高的选取概率.
(3) 服务寿命:令agej为节点j的年龄,代表服务j加入网络的时间长短.随着节点年龄的增加,节点逐渐老化,被组合选取的概率降低.
(4) 服务容量:对于每个服务来说,由于受其所在的网络环境和自身硬件能力的限制,对于其承受请求存在上限,当服务负载达到上限时,将降低其择优概率.
本文根据以上服务因素,考虑了用户的需求及服务间的择优选择,给出服务节点i选择服务节点j的择优概率πij为
${{\pi }_{ij}}=\left\{ \begin{array}{*{35}{l}}
\frac{[(1-\tau ){{\omega }_{ij}}/ag{{e}_{j}}+\tau ]Qo{{S}_{j}}}{\sum\limits_{l}{[(1-\tau ){{\omega }_{il}}/ag{{e}_{l}}+\tau ]Qo{{S}_{j}}}} & , & \text{if }adj\_matrix[i][j]=1 \\
0, & \text{if }adj\_matrix[i][j]=0 \\
\end{array} \right.$
(2)
服务交互关系是由用户需求驱动的,我们用参数t来刻画用户选择服务的随机性和有目的的择优性.通过调节概率t,实现了节点交互强度与节点QoS这两个因素在择优选取中对最终自适应概率影响作用的调节.当t=1时,自适应择优和重组概率仅受到节点QoS的影响;当t=0时,自适应择优和重组概率退化为受节点交互强度和节点年龄共同制约.
另一个问题是对服务执行过程的建模.服务执行过程是一个复杂系统的动态演化过程,在这个过程中,通过用户的驱动,组合服务调用相关的服务进行执行.服务的被调用次数不是均匀的,少部分优质服务会得到绝大多数的使用点击.所以,我们采用帕累托幂律分布模拟服务的执行分布.在帕累托分布中,如果X是一个随机变量,则X的概率分布如下面的公式所示:
$P(X>x)={{\left( \frac{x}{{{x}_{\min }}} \right)}^{-k}}$
(3)
$p(x)=\left\{ \begin{array}{*{35}{l}}
0,\text{ if }x<{{x}_{\min }} \\
\frac{kx_{\min }^{k}}{{{x}^{k+1}}},\text{ if }x>{{x}_{\min }} \\
\end{array} \right.$
(4)
对于每个服务来说,由于受其所在的网络环境和自身硬件能力的限制,对于其承受请求存在上限.对此,我们用负载-容量模型来模拟.当服务负载超限时,服务呈现出无响应或超时现象,此时服务计算的方法是进行重选取或替换策略,如图6所示.我们采用重择优生长的方式进行仿真模拟.具体来说,如果当前节点负载超限,那么从上一个节点重新选取后面的服务节点,这个过程和服务替换、服务重选取等方法是等价的.
下面提出Web服务行为演化模型的具体过程:
(1) 根据服务WSDL数据集构建初始网络,从中选取m0个节点、n0条边作为初始服务行为演化网络.在每个时间步内,依概率执行下面步骤中的一个.
(2) 以概率p执行组合增点:随机选择一个行为演化网络中的一个节点v0,依据服务逻辑连通性矩阵,在与该节点连通的所有节点中,根据择优概率选择一个节点v1连接,并将此新节点纳入到服务行为网络中.再以节点v1开始,根据上述择优节点连接规则依次迭代,直到达到要求的组合长度d.
(3) 以概率1-p执行约束增边:在行为网络中,按照帕累托概率分布选择上一步生成的组合节点链l,对其进行执行,增加组合节点间的边连接强度和负载.如果存在节点v的当前负载大于其容量,则将其移出组合链l,并从节点v的前驱结点开始进行重择优选取,节点v的负载随时间进行衰减 .
以上过程直到达到预设的时间长度为止.算法伪代码如图7所示.表1为算法所用参数表.
为了分析服务行为网络的动态演化特性,本文选取QWS[23]及Seekda[24]数据集作为服务行为网络演化模型的实验数据.Seekda是一个Web服务搜索引擎,我们通过网络爬虫收集Seekda搜索引擎中的Web服务WSDL数据3 712条,这些服务分属于2 620个服务提供商提供.QWS是使用WSCE crawler收集的2 507个Web服务数据集.每条服务的QoS信息由11个参数构成.数据集中服务参数由Web service基准检查程序以6天为一个周期测量的数据取平均得到.
由于以上Web服务的WSDL数据由不同开发商提供,其文档质量很难保证,存在WSDL格式不正确、内容缺失等问题.因此,首先依据WSDL规范进行筛选,然后进行以下预处理操作:
(1) 参数信息提取.对数据集中的每个WSDL文档进行解析,提取出服务名及操作,每个操作对应的输入参数(参数名、类型)和输出参数(参数名、类型).
(2) 类型处理.在进行参数匹配时,需要使用参数名和数据类型进行匹配.WSDL文件是由不同的开发者设计的,除基本数据类型外还自定义一些复杂数据类型,采用扁平化操作计算复杂类型之间的相似度,然后进行匹配.
(3) 数据清洗.大约有10%的输出参数,它们被命名为return,result,response等.对于这些名称,在匹配时会由于信息过于模糊造成实际不相同的参数却匹配在了一起.因此,对这些参数的名称根据WSDL的上下文重新确定名称.例如,对于操作名为getAddress的操作,一个输出参数名为result,根据上下文可知:输出的参数实际上是Address,因此将输出参数的名称更改成Address.
4.2 结果与分析在对数据集进行解析、清洗等预处理之后,采用精确匹配方法构建服务逻辑交互矩阵.基于该矩阵进行初始组合选取、初始组合增长、协同演化、自适应重择优等服务行为模拟,生成相应的服务行为网络.为了避免随机性所造成的影响,本文针对每种数据进行100次演化建模,其所得到的平均结果见表2.
从统计结果可以看出:服务行为网络的平均路径长度相对于其网络规模均较小,与按照参数匹配关系生成的服务结构网络和文献[25]获取的软件网络相比,聚集系数与平均路径长度均有所下降,服务行为网络的结构明显稀疏,但仍高于同等规模的随机网络.其中,服务行为网络的平均路径长度分别为2~3之间,而软件执行网络的平均路径长度为5~9之间.这种显著的差异,与服务的执行方式是密切相关的.服务是完成独立功能的自包含的软件模块,服务间的交互方式是由用户驱动的自发组合,因此其行为网络比较松散.而软件网络实现是由代码实现的硬编码耦合,由于软件设计模式和封装复用的原则,其紧密性要比服务软件高,这也验证了服务系统的松耦合特性.比较服务结构网络和服务行为网络的平均度和网络直径可以发现,经过演化后均有所下降.针对这种现象,我们认为,这是由于服务执行的特点所引起的.服务执行过程是一个根据用户需求进行动态连接的过程,但其前提是服务的参数具有匹配关系.所以对于服务执行过程来说,服务间的连接是受用户需求驱动的受限择优的过程,这导致了服务行为网络本质上是基于偏好选择的服务结构网络的子网,其网络聚集程度、平均度、直径的全局拓扑特征均有所改变.服务行为网络的拓扑图及其度分布如图8所示.
在拓扑图中,节点的大小与其度成正比,不同颜色代表不同的度.度分布图中横坐标为度、纵坐标为相应度的节点在网络中的出现频率.从中可以看出,服务行为网络的度分布在双对数坐标下呈现出一种随机化的截尾无标度分布形态.即去掉度较大的一些曲线尾部节点外,网络总体度分布在双对数坐标下呈现近似直线,但其分布范围较散,呈现一种随机化的现象.
进一步观察服务行为网络的出度与入度分布可以发现,二者的幂指数基本类似.而相关文献表明,软件网络的出度与入度分布指数呈现明显差异,并猜想,这是由于软件开发中鼓励重用导致了入度分布的幂指数值较小[18].对于这种差异,我们认为:有可能是由于服务软件中的节点不存在明显的层次结构,大多数的服务流程呈现简单线性形态;同时,由于服务软件的设计原则由传统软件的分层设计重用原则转变为基于用户需求的业务流程驱动的组合设计,这使得除了少数与用户直接交互的服务节点外,大部分服务节点的出度与入度基本相等.这与传统的软件结构具有明显的区别.
图9给出了Seekda和QWS行为网络的聚集系数-度与介数-度分布统计图.从图中可以看出:两个网络的聚集系数-度分布在双对数坐标下基本呈线性关系,与软件网络[26]相比,服务行为网络更类似包层次和类层次网络上的结果.这说明服务行为网络具有明显的模块性,这种模块性可能是由于用户需求驱动所形成的业务聚集社团造成的.观察介数分布可知:服务节点和介数存在正相关性,即,度大的节点其介数也相对较高.这说明,服务行为网络中的关键节点是被频繁调用的服务节点.
概率τ是影响服务节点选择随机性与择优性的重要参数,τ值的不同,决定了网络在生长时选择节点的策略:当τ较小时,网络倾向于按照随机增长的方式进行演化;当τ较大时,网络倾向于按照择优选择进行演化.图10给出了不同的参数τ对服务度分布的影响,可以看出:对于不同的演化生长方式,网络生长后最终的度分布基本一致.但从图11中不同节点的度演化曲线可以看出:对于不同的τ,特定服务节点随时间的度变化具有显著的差异.当τ=1时,服务节点的度升高较快,表明网络此时倾向于进行择优选择;当t=0时,服务节点的度变化较慢,说明此时网络中随机性选择占优.不同的τ值决定了网络中不同节点的度的分配,但整体网络的度分布由于底层约束的限制,而没有明显的区别.此种现象表明:对于服务作为基本模块构成的软件系统,个体服务的特性对于整体性能影响较小.
图12给出了网络平均度与节点数随时间的变化.一个重要的现象是,行为网络规模一般最大达到结构网络的80%左右.这是因为行为网络在生长过程中始终受到底层结构网络的约束,服务间的连接取决于服务参数的匹配关系,这使得某些处于结构网络外围的节点的择优概率极小,很难加入到网络中,当系统演化到一定时间后,系统规模大小基本呈现稳定状态.
为了验证本文提出的模型与真实系统的一致性和可用性,我们在Internet上建立了一个模型系统.基于现有的云计算资源,在Amason EC2,Google App Engine等云计算平台上部署了50个节点,分别位于不同的地理位置,我们选取了一些Web服务在这些节点上模拟运行.我们实现了Web服务的接口,其中的operation方法进行随机延迟以模拟Web服务的计算.系统的拓扑如图13所示,其中,节点颜色代表服务的功能类别,节点大小与服务性能成正比.
本文提出的行为演化模型可根据服务当前的状态预测其未来时刻的预期状态,从而为系统状态预测与故障预警提供支撑.为此,我们分析了实验系统的性能指标.通过向网络中随机注入任务,计算任务的平均排队时间,从而分析网络系统的性能.图14给出了采用行为演化模型预测方法与实际服务系统执行结果的对比.当系统负载较低(任务数<20)及系统负载较高(任务数>80)时,模型的结果与实际系统执行结果符合得很好;当系统负载处于中等水平时,由于随机性的原因,模型预测与实际结果有偏差,但整体趋势一致,说明了模型的有效性.
对自治的复杂协同软件系统的管理和分析,是目前软件开发者和运营者所面临的关键性难题,系统组成规模和构成元素的自治所带来的复杂性问题无法用传统的解构分析方法解决.因此,对系统行为的建模及仿真,就成为了解系统行为及运营特征的重要手段.
本文针对由自治的Web服务构成的软件系统,提出一种Web服务行为演化建模模型.模型以大量真实的Web服务WSDL数据为支撑,从中提取服务间可能存在的数据交换关系作为支撑网络拓扑,然后,根据服务动态交互特点如组合执行、择优选取、动态重组等,综合考虑服务交互结构特征、非功能属性及用户需求变化,给出了一种服务行为网络的建模与演化方法.通过该模型,对现有的服务资源进行了演化分析.结果发现:与传统的软件系统的层次性结构有所不同,由自治的Web服务所构成的软件系统具有更强的模块性;与系统中个体服务演化规则,如择优连接及动态重组相比,服务结构网络的性质对系统最终形态具有更重要的影响.
本文为复杂服务软件系统的管理与分析提供了一个新的研究视角,这一研究方向还有很多需要解决的问题,主要包括:
(1) 目前提出的服务结构网络模型是基于参数匹配原则的,没有考虑进一步的本体与服务信息,下一阶段工作要提出基于本体匹配原则的网络模型;
(2) 完善Web服务行为演化模型,充分考虑服务执行时的行为特征;
(3) 在Web服务行为演化模型的基础上,考察Web服务行为网络的动态执行特性.
[1] | Lü J, Ma XX, Tao XP, Xu F, Hu H. Research and progress on Internetware. Science in China (Series E), 2006,36(10):1037-1080 (in Chinese). |
[2] | Ma YT, He KQ, Li B, Liu J. Empirical study on the characteristics of complex networks in networked software. Ruan Jian Xue Bao/Journal of Software, 2011,22(3):381-407 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3934.htm [doi: 10.3724/SP.J.1001.2011.03934] |
[3] | Yau SS, Ye N, Sarjoughian HS, Huang DZ, Roontiva A, Baydogan MG, Muqsith MA. Toward development of adaptive service-based software systems. IEEE Trans. on Services Computing, 2009,2(3):247-260. [doi: 10.1109/TSC.2009.17] |
[4] | Li XT, Fan YS, Sheng QZ, Maamar Z, Zhu HW. A Petri net approach to analyzing behavioral compatibility and similarity of Web services. IEEE Trans. on Systems, Man, Cybernetics, Part A: Systems and Humans, 2011,41(3):510-521. [doi: 10.1109/TSMCA.20 10.2093884] |
[5] | Deng SG, Li Y, Wu J, Kuang L, Wu ZH. Determination and computation of behavioral compatibility for Web services. Ruan Jian Xue Bao/Journal of Software, 2007,18(12):3001-3014 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/18/3001.htm [doi: 10.1360/jos183001] |
[6] | Xiao FX, Huang ZQ, Cao ZN, Tu LZ, Zhu Y. Unified formal modeling and analyzing both functionality and QoS of Web services composition. Ruan Jian Xue Bao/Journal of Software, 2011,22(11):2698-2715 (in Chinese with English abstract). http://www.jos. org.cn/1000-9825/3902.htm [doi: 10.3724/SP.J.1001.2011.03902] |
[7] | Sommerville I, Cliff D, Calinescu R, Keen J, Kelly T, Kwiatkowska M, McDermid J, Paige R. Large-Scale complex IT systems. Communications of the ACM, 2012,55(7):71-77. [doi: 10.1145/2209249.2209268] |
[8] | Northrop L. Ultra-Large-Scale systems: The software challenge of the future. Technical Report, Pittsburgh: Carnegie Mellon University Software Engineering Institute, 2006. |
[9] | Rushby J. Software verification and system assurance. In: Proc. of the 7th IEEE Int'l Conf. on Software Engineering and Formal Methods. Hanoi: Computer Society Press, 2009. 3-10. [doi: 10.1109/SEFM.2009.39] |
[10] | Barabási AL. Scale-Free networks: A decade and beyond. Science, 2009,325:412-413. [doi: 10.1126/science.1173299] |
[11] | Vespignani A. Modelling dynamical processes in complex socio-technical systems. Nature Physics, 2012,8(1):32-39. [doi: 10.103 8/NPHYS2160] |
[12] | Liu YY, Slotine JJ, Barabási AL. Controllability of complex networks. Nature, 2011,473:167-173. [doi: 10.1038/nature100 11] |
[13] | Barabási AL, Albert R. Emergence of scaling in random networks. Science, 1999,286:509-512. [doi: 10.1126/science.286.5439. 509] |
[14] | Hu H, Yin Q, Lü J. Service behavior and quality consistency in virtualized computing environment. Ruan Jian Xue Bao/Journal of Software, 2007,18(8):1943-1957 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/18/1943.htm [doi: 10.1360/jos181943] |
[15] | Zhang LJ, Li B. Requirements driven dynamic services composition for Web services and grid solutions. Journal of Grid Computing, 2004,2(2):121-140. [doi: 10.1007/s10723-004-4202-1] |
[16] | Gaaloul W, Baïna K, Godart C. Log-Based mining techniques applied to Web service composition reengineering. Service Oriented Computing and Applications, 2008,2(2):93-110. [doi: 10.1007/s11761-008-0023-6] |
[17] | Zhang MW, Wei WJ, Zhang B, Zhang XZ, Zhu ZL. Research on service selection approach based on composite service execution information. Chinese Journal of Computers, 2008,31(8):1398-1411 (in Chinese with English abstract). |
[18] | Myers CR. Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs. Physical Review E, 2003,68:046116. [doi:10.1103/PhysRevE.68.046116] |
[19] | Valverde S, Sole RV. Hierarchical small worlds in software architecture. Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications and Algorithms, 2007,14(S6):1-11. |
[20] | Moura AP, Lai YC, Motter AE. Signatures of small-world and scale-free properties in large computer programs. Physical Review E, 2003,68:017102. [doi: 10.1103/PhysRevE.68.017102] |
[21] | Kil H, Oh SC, Elmacioglu E, Nam W, Lee D. Graph theoretic topological analysis of Web service networks. World Wide Web, 2009,12(3):321-343. [doi: 10.1007/s11280-009-0064-6] |
[22] | Hwang J, Altmann J, Kim K. The structural evolution of the Web 2.0 service network. Online Information Review, 2007,33(6): 1040-1057. [doi: 10.1108/14684520911010990] |
[23] | Al-Masri E, Mahmoud QH. QoS-Based discovery and ranking of Web services. In: Proc. of the 16th IEEE Int'l Conf. on Computer Communications and Networks (ICCCN). Hawaii: Institute of Electrical and Electronics Engineers, 2007. 529-534. [doi: 10.1109/ICCCN.2007.4317873] |
[24] | Seekda Web services search engine. 2013. http://webservices.seekda.com |
[25] | Zhang XZ, Luo S, Yin Y, Zhang B. Analysis on dynamic behavior for open-source software execution network. Computer Science, 2011,38(10a):242-248 (in Chinese with English abstract). |
[26] | He KQ, Ma YT, Liu J, Li B, Peng R. Software Networks. Beijing: Science Press, 2008 (in Chinese). |
[1] | 吕建,马晓星,陶先平,徐锋,胡昊.网构软件的研究与进展.中国科学(E辑),2006,36(10):1037-1080. |
[2] | 马于涛,何克清,李兵,刘婧.网络化软件的复杂网络特性实证.软件学报,2011,22(3):381-407. http://www.jos.org.cn/1000-9825/ 3934.htm [doi: 10.3724/SP.J.1001.2011.03934] |
[5] | 邓水光,李莹,吴健,邝砾,吴朝晖.Web服务行为兼容性的判定与计算.软件学报,2007,18(12):3001-3014. http://www.jos.org.cn/ 1000-9825/18/3001.htm [doi: 10.1360/jos183001] |
[6] | 肖芳雄,黄志球,曹子宁,屠立忠,祝义.Web服务组合功能与QoS的形式化统一建模和分析.软件学报,2011,22(11):2698-2715. http://www.jos.org.cn/1000-9825/3902.htm [doi: 10.3724/SP.J.1001.2011.03902] |
[14] | 胡昊,殷琴,吕建.虚拟计算环境中服务行为与质量的一致性.软件学报,2007,18(8):1943-1957. http://www.jos.org.cn/1000-9825/ 18/1943.htm [doi: 10.1360/jos181943] |
[17] | 张明卫,魏伟杰,张斌,张锡哲,朱志良.基于组合服务执行信息的服务选取方法研究.计算机学报,2008,31(8):1398-1411. |
[25] | 张锡哲,罗实,印莹,张斌.面向软件执行网络的行为拓扑分析研究.计算机科学,2011,38(10a):242-248. |
[26] | 何克清,马于涛,李兵,刘婧,彭蓉.软件网络.北京:科学出版社,2008. |