1 武汉大学 计算机学院, 湖北 武汉 430072;
2 软件工程国家重点实验室(武汉大学), 湖北 武汉 430072;
3 湖北科技学院 计算机科学与技术学院, 湖北 咸宁 437100;
4 武汉大学 国际软件学院, 湖北 武汉 430072

收稿时间:2014-08-01;修改时间:2014-10-14

基金项目:国家重点基础研究发展计划(973)(2014CB340401); 国家自然科学基金(61273216, 61202031); 湖北省重大科技创新计划(2013AAA020)

作者简介：杨荣(1980－),男,湖北巴东人,博士生,讲师,CCF 学生会员,主要研究领域为服务计算,软件工程.
李兵(1969－),男,博士,教授,博士生导师,CCF 高级会员,主要研究领域为复杂网络,服务计算,软件工程,人工智能.

通讯作者：李兵, E-mail: bingli@whu.edu.cn, http://libingteam.com/

摘要 ：近年来,自适应软件是软件工程领域的研究热点.研究者们从不同角度对如何促进和提高软件系统的自适应进行了大量研究,有的以体系结构为中心研究软件的自适应,有的则从需求的角度进行研究.但是,从软件系统的流程片段自适应重用的角度来研究软件自适应,类似的研究工作还很少.借鉴软件控制论中的思想来研究流程片段的自适应重用,基于受控的Markov链模型来探讨流程片段的最优查询策略.提出了针对流程片段查询特殊应用环境下的CMC(controlled Markov chain)模型,并对该模型进行了优化处理.基于逐次最小二乘法,进一步提出了流程自适应查询策略,该策略充分利用流程片段的历史查询信息,通过在线参数调整,能够帮助查询人员及时调整和优化查询策略.Matlab环境下的仿真实验和真实流程数据集下的实验,共同验证了该模型和算法的有效性和可行性.

关键词 ： 自适应软件; 流程片段重用 Markov链

Study on Strategy of Adaptive Process Fragments Reusing

1 School of Computer, Wuhan University, Wuhan 430072, China;
2 State Key Laboratory of Software Engineering (Wuhan University), Wuhan 430072, China;
3 College of Computer Science and Technology, Hubei University of Science and Technology, Xianning 437100, China;
4 International School of Software, Wuhan University, Wuhan 430072, China

Corresponding author:

Abstract : Recent research on the self-adaptive software is one of the new focuses in the field of software engineering. The researchers pay more attention on how to improve the adaptation of software from different angles. While some focus on the architecture information, others pay more attention to the requirement. However as of now, there is little work about the process fragments reuse in self-adaptive software. This paper employs the idea of software cybernetics to study the process fragments reuse, and searches the optimal query method based on the model of controlled Markov chain. Firstly, a CMC model in the context of process fragments query is proposed, followed by subsequent optimizations. Then, a self-adaptive query strategy is addressed based on the iterative least square method. With the on-line parameter adjustment, this strategy utilizes the history of process fragment query to help people adjust strategies. The experiments in the context of Matlab and real process dataset validate the efficiency and feasibility of the model and algorithm presented in this paper.

Key words : self-adaptive software; process fragments reuse; Markov chain 有不少学者从不同角度对自适应系统进行了定义:有学者提出,自适应软件是一类能够在运行过程中实时收集系统的各种变化信息,并根据预定义的策略,在适当时候能够自我调整的特殊软件 ^[ 2 ];也有学者将自适应当作系统的一种能力,即,软件系统可以动态响应环境变化的能力,并自我调节以提高系统的性能 ^{[ 3 ]} ;有的学者认为,自适应软件能够评估自身的行为,当评估结果表明系统目前的行为不能达到期望的目标,或者需要实现更好的功能或性能时,软件必须自我调整自身的行为 ^{[ 4 ]} .

关于自适应软件系统的研究,主要包括支撑自适应系统的基础理论和开发技术两个方面的研究工作.为了方便进行自适应研究,很多学者借鉴控制理论 ^{[ 5 , 6 ]} 中的概念和方法 ^[7-10] .Kokar等学者将控制理论作为分析和设计自适应软件系统的数学基础 ^{[ 7 ]} .根据传统控制理论的思想,我们可以将自适应系统分为两部分,即,系统自身和环境.软件所处的环境是一个动态的生态系统,它的行为可看成是它以前的状态、作用于它的动作和时间的函数.系统自身通过不断地选择和调整动作来满足用户或系统设定的目标.Cheng等人提出,可以学习控制工程,特别是反馈控制中的思想来研究自适应系统 ^{[ 8 ]} ,他们将反馈循环分为4个阶段:收集、分析、决策和动作,并深入分析了每个阶段必须考虑的问题和可能面临的挑战.总结现有以控制论为理论基础的自适应系统研究,我们可以将软件系统当作一个“运行-收集-反馈-决策-调整-再运行”的循环过程.虽然基于“收集-反馈-控制”可以构成一个完整的反馈和控制回路,但是,目前的自适应系统研究还不够成熟,要形成稳定的框架体系结构还有很长的路要走 ^{[ 2 ]} .同时,关于自适应系统的开发技术方面,学者们提出了基于模型、反射式中间件、体系结构和Agent等技术.但是现有的研究工作还存在很多局限性,比如软件实体抽象、自适应逻辑表达等方面的局限性.

本文从另外一个角度来探讨软件的自适应问题,即,关于软件系统中的流程片段重用问题.现代网络等技术的发展,为不同组织的人们共同解决同一问题提供了契机.服务计算(service-oriented computing,简称SOC)广泛采用Web服务来解决企业或组织之间的互操作性和动态协作性问题.伴随着云计算和物联网的兴起,我们正进入一个“万事皆服务”的信息时代.但在实际应用中,单个服务通常不能满足要求,必须将多个服务个性化地组合起来,形成满足复杂功能的服务流程.服务流程不仅是协调服务和资源的手段,它也是一种可共享、可复用的解决问题的知识.在科学、商业等领域,服务流程的成功应用实践,都证明了共享和复用服务流程的重要性.比如,英国的e-Science计划致力于人类疾病基因科学研究,该计划通过服务流程实现了科学家群体之间的共享并促进了科学的发展 ^{[ 11 ]} .使用已有的流程知识,并考虑自身需要快速构建服务流程,已成为增强企业敏捷性和竞争力的重要途径.很多大的企业集成软件提供商(如SAP)将一些常用的流程片段抽取出来,并保存在流程库中,这样可以提高定制组合业务流程的效率 ^{[ 12 ]} .本文研究的流程片段重用,其应用场景类似于文献 ^{[ 12 ]} ,用以解决如何从流程库中进行流程片段的最优重用查询问题.

本文采用受控Markov链(controlled Markov chain,简称CMC)来建模流程片段查询策略,并设计出一个自适应流程片段重用模型,研究如何以最小的期望成本检测并找到满足要求的可重用服务流程片段.本文借鉴软件控制论的思想对制约条件进行一系列转换,提出一种资源约束的受控Markov链模型,该模型具有很好的性能.根据该模型,设计人员能够高效且低成本地找出可重用流程片段,该片段能够满足指定的功能要求.

为了利用流程片段的历史使用记录信息,再通过在线参数估计对重用策略进行在线调整,以构造流程片段的自适应重用策略.

本文第1节通过一个流程模型引出我们的研究问题,即,关于流程片段任意粒度的重用查询问题.第2节建模CMC流程片段重用模型.第3节构造CMC自适应流程片段查询策略.第4节为实验分析.第5节为相关工作介绍.第6节总结全文并提出未来的工作.

1 启发性流程实例

我们首先通过一个流程片段实例,引出本文的研究动机. 图 1 为一个“一日游”服务流程,通过该服务过程,能够帮助旅行者合理地、划算地安排行程.该服务流程包括天气查询服务、景点搜索、自行车租赁、汽车租赁和旅行代理这5个功能服务.为了简洁起见,分别用 S ₁ , S ₂ , S ₃ , S ₄ 和 S ₅ 表示.不失一般性,仅仅考虑每个功能服务的输入和输出.根据5个服务之间的输入/输出依赖关系,可以构建该服务流程的依赖图.

在一个服务流程系统中,对于每个组件服务 C _i ,假设有 n _i 个候选服务去实现它,表示为 ${C_i} = (c_1^i,c_2^i,...,c_{{n_i}}^i).$假设${S_P} = (c_{{j_1}}^1,c_{{j_2}}^2,...,c_{{j_m}}^m)$代表一个具体的组合流程,它能够满足给定的抽象流程ACP的功能要求,其中,每个 $c_{{j_i}}^i$都是 C _i 中的一个元素.所有的组合方案形成一个组合流程空间 S =( C ₁ x C ₂ x … x C _m ).在本文的研究中,不失一般性,假设在流程库中包含任意长度的流程片段.对于每个服务流程,都具有相同类型的QoS属性,比如响应时间、吞吐 量等.用一个向量 A =( a ₁ , a ₂ ,…, a _L )描述流程的 L 个属性. $F:(c_{{j_1}}^1,c_{{j_2}}^2,...,c_{{j_m}}^m) \to {S_P}$用来定义关于流程中候选服务属 性的汇聚函数,通过该函数可以获得关于流程的属性值,并通过这些值可以定义条件约束.

用户在提出流程查询请求时,都会附带一些QoS约束.假设用 R 定义由 p 个属性组成的QoS属性约束向量, R 中的每个元素由一个三元组 á a _r , op _r , bound _r ñ 构成,其中, a _r 表示第 r 维QoS属性, op _r 是比较操作符(比如>,<,≤, ≥,=), bound _r 是QoS约束的边界值.定义一组约束函数向量, ${F_R} = \langle f_1^R,f_2^R,...,f_i^R,...,f_p^R\rangle $, 其中,$f_i^R$表示第 i 个约束属性的汇聚函数.用 R _i 定义由 $f_i^R$计算出的值,则对于一个流程 S _P Î S ,它的约束值向量定义为 V _R = V _R ( S _P )=( R ₁ , R ₂ ,…, R _i ,…, R _p ).因此,通过比较流程片段 S _P 的每项QoS值 R _i 及其对应的边界约束值 bound _i ,可以验证 S _P 是否满足给定的属性约束条件.

2.2CMC流程片段查询模型

关于服务流程片段重用,为了后面建模简单,通过以下模型描述可以构建CMC流程片段重用模型.

1) 在搜索流程片段时,要用到一些资源,比如CPU、内存等,假设总共有 X ₀ 单位数目的可用资源.

2) 假设所有的流程片段都存放在一个库中,即流程库.对于每一个具体的流程片段查询请求,由于功能已经确定,因此总共的满足该功能要求的流程片段总个数一定,假设为 N ( N 可以任意大).很显然,查询人员开始不清楚满足要求的流程片段数量,不可能在一次查询中搜索到所有的流程片段,而且这样做也极大地浪费了资源.只有随着不断地查询,在拥有了一定规模的使用历史记录时,满足特定要求的流程片段数目才大概可以确定.假设每次搜索到的流程数目为一个期望值 n ( n ≤ N ).

3) 对于库中的每个流程片段 spf ,它或者没有被搜索到,或者被查询出但未被使用过,或者被查询出且存在使用历史记录,则 spf 的3个状态可如下表示:

查询不可能搜索到所有满足功能约束的流程片段.每次搜索到的流程片段数目期望值为 n ,剩下的 N - n 个流程片段在这次查询中被查询出的概率很小,因此可当作一个小概率事件而不予考虑,则 t 时刻的整体流程重用状 态可重新描述为${\zeta _t} = (spf_t^1,spf_t^2,...,spf_t^n,{X_t}).$

5) 为了查询出可被重用的流程片段,需要很多的决策.假设总共有 q +2个不同的决策,定义决策集为 D ={1, 2,…, q , q +1, q +2},其中,决策1~ q 用于查询流程,即,有 q 个查询用例;决策 q +1用以初始化,并开始查询;当所有查询资源用完,或查询出的流程片段集合已经完全达到功能要求并满足属性约束时,决策 q +2用于退出查询过程. 在任何时刻,调用任何一个决策 D _t 都会消耗$Cos{t_{{\zeta _t}}}({D_t})$代价的资源,有如下定义:

$Q = \left[ {\begin{array}{*{20}{c}} {\rho _1^1}&{\rho _1^2}&{...}&{\rho _1^n}\\ {\rho _2^1}&{\rho _2^2}&{...}&{\rho _2^n}\\ \vdots & \vdots &{...}& \vdots \\ {\rho _q^1}&{\rho _q^2}&{...}&{\rho _q^n} \end{array}} \right]$

上面概率矩阵中的每一行对应一个决策的查询概率向量,即,$\rho _i^j$表示第 i 个决策查询到第 j 个流程片段的概 率.用 f _t 表示 t 时刻是否搜索到一个满足功能要求和约束的流程片段,对于 f _t ,可以有下面的状态概率计算公式:

$P\{ {f_t} = 1|{D_i} = i\} = \sum\limits_{k = 1}^n {\rho _i^k} ,P\{ {f_t} = 0|{D_i} = i\} = 1 - \sum\limits_{k = 1}^n {\rho _i^k} $ 7) 为了加快搜索速度,除了原始的流程库以外,另外构建一个流程库,用来存放新近被使用或使用频率比较高的流程片段.因此对每个查询请求,优先在该新建库中查询.采用该策略能够加快流程查询速度,因为在一个公司内部,其核心业务流程或操作最频繁的工作流程基本上固定了,类似于经典的二八定律.在状态 z _t 下,采用的查询决策如果找出了一个以前未被搜索出的流程片段,因为该流程会被存入新建库中,则下次搜索速度就提高了.虽然本次查询会花费一定的代价,但却节省了以后查询的成本.从这个意义上说,可以认为,本次查询采用决策 D _t 查询出流程 spf 会产生一定的代价折扣,或者说本次查询减少了一定的代价,表示为 y _spf ( D _t | z _t )>0.决策 q +1和 q +2不会产生代价折扣.

通过前面的假设和定义,当用户提出某个流程查询请求,采用不同的查询决策进行搜索,经多次反复,最终,查询系统或者成功返回(找到满足功能约束和属性约束的流程片段),或者查询失败,即,没有满足要求的流程片段.我们将查询时间离散化,即,每次查询作为一次独立的个体,令 G 为查询系统返回的时间,则有如下等式成立:

${X_0} = {n_1} \times Cos{t_1} + Cos{t_2} + {X_r} + \sum\nolimits_{t = 0}^r {[Cos{t_{{\zeta _t}}}({D_t}) - {\chi _{{D_t}}}{\psi _{spf}}({D_t}|{\zeta _t})]} $ ${\chi _{{D_t}}}({D_t} = i) = \left\{ {\begin{array}{*{20}{l}} {\sum\nolimits_{k = 1}^n {\rho _i^ksign(spf_t^k - 2)sign( - spf_t^k),{\rm{ }}i = 1,2,...,q} }\\ {0,{\rm{ }}i = q + 1,q + 2} \end{array}} \right.$ 其中, Ð 表示从查询系统启动到查询结束,所采用的所有查询策略,这些策略一起构成了针对某个用户请求的查 询方案.${\Phi _D}({X_0})$表示查询过程结束时, Ð 产生的代价总折扣.在前面定义的基础上,公式(10)就构建成了流程片段查询的CMC模型.本文的研究目的是要找到一个整体查询方案 Ð ,使代价总折扣${\Phi _D}({X_0})$最大,这样的查询方案 就能以最低的、最划算的成本代价查询到既满足功能要求,也满足非功能属性要求的流程片段.

3CMC自适应重用流程片段查询策略

在第2节我们建模了一个CMC流程片段查询策略模型,本节将通过对模型的优化,进一步提出一个自适应流程查询策略模型.

3.1 查询决策优化

公式(10)对采用某个整体查询方案后所产生的代价总折扣进行了定义.根据CMC理论 ^{[ 13 ]} 可知:存在一个确定性静态查询策略,使得${\Phi _D}({X_0})$最大.令 И ( z )是状态 z 的价值函数,本文的最优查询方案就是在此价值函数基础上进行选择的.

定理 1 . 根据前面的模型1)~模型7),有:

其中,$Cost_{{\zeta _t}}^*(i) = - \sum\limits_\eta {{p_{\zeta \eta }}(i){\psi _{spf}}(i|\delta )} ,{p_{\zeta \eta }}(i) = P\{ \eta |\zeta ,{D_t} = i\} = \sum\nolimits_{k = 1}^n {\rho _i^k} $为从状态 z 转换到 h 的概率,$\zeta _{t + 1}^j$表示采用查询决策 D _t 查询到某个流程片段 spf 时状态 z _t 的下一状态,而$\zeta _{t + 1}^j$表示 D _t 没有查询到流程片段时 z _t 的下一状态.

通过定理1,可以得出:在任何时刻的查询决策选择,都应满足定理1中的价值约束;对每个流程查询请求,最后获得的整体查询方案,都是对查询决策集的一个选择和排列过程.

定理 2 . 当$\min \{ Cos{t_{{\zeta _t}}}(1),Cos{t_{{\zeta _t}}}(2),...,Cos{t_{{\zeta _t}}}(q)\} \le {X_t}$时,则有如下查询策略:

$D_{{\zeta _t}}^* = \mathop {\arg \min }\limits_{1 \le i \le q} \{ Cost_{{\zeta _t}}^*(i) + \chi _i^*H(\zeta _{t + 1}^j) + (1 - \chi _i^*)H(\zeta _{t + 1}^{j'})\} $ 该策略即为针对查询过程中一系列约束条件的限制而得出的优化流程片段查询策略,它能够使得代价总 折扣${\Phi _D}({X_0})$最大.但在具体实施过程中,必须明确每个查询决策搜索到每个流程片段的概率,即要已知$\rho _i^k$的 值,也就是要确定第6)条中定义的矩阵 Q .很显然,要求出 Q ,必须依赖于历史查询记录信息.因此,在公式(12)的基础上引入一个参数估计和调整模块,充分利用历史信息来对查询概率进行在线估计和调整,从而构造出一个流程片段自适应查询策略.

3.2 基于逐次最小二乘法的自适应流程查询策略

利用最小二乘法可以方便地求得未知的数据,并使得这些求得的数据与实际数据之间误差的平方和为最小 ^{[ 14 ]} .本文采用逐次最小二乘法来不断地获得未知流程片段的查询概率,该方法充分利用历史查询记录信息.将所有查询用例的查询情况构造成一个向量 W =( r ₁ , r ₂ ,…, r _q ).其中, r _i 表示采用查询决策 i 时,它能查询到满足用户需求的某个流程片段或集合的概率.对于一个流程片段 spf ,本文在考虑查询概率时只考虑两种状态,即: spf 处于原始流程库中时被查询到的概率( spf 在某个时间点还未被查询到),或者 spf 处于新建库中被查询到的概率( spf 在以前搜索中被查询到,且存入了新建库中).对于原始库中的流程片段,假设初始时候它们的查询概率一样,这个等概率估计值会随着后面的查询不断被更新,直至趋向于各自的真实值.假设在某个时刻 z _t ,对于用户提出的某个功能需求 Я ,查询系统从新建库中找出 n ₀ 个(假设总共有 N ₀ 个与 Я 匹配的流程片段)与 Я 匹配的流程片段,则对 r _i 有下面的等式: ${\rho _i} = \sum\limits_{k = 1}^n {\rho _i^k} = (n - {n_0}) \times \rho _i^ \circ + \sum\limits_{k = 1}^{{n_0}} {\rho _i^k} $ 其中,1≤ i ≤ q ,$\rho _i^ \circ $为存储于原始库中的流程片段的等概率值.为了计算方便,假设已将新建库中 n ₀ 个流程片段 通过排序移到编号从1到第 n ₀ 的位置.根据逐次最小二乘法,可以对 W 进行在线估计.在公式(13)中,有两组未知 变量,即$\rho _i^k$和$\rho _i^ \circ $,有: $\left. \begin{array}{r} \rho _i^k = \frac{{{n_0}}}{{{N_0}}},k = 1,2,...,{n_0}\\ \mathop {\rho _i^ \circ }\limits^ \wedge = \frac{{\mathop {{\rho _i}}\limits^ \wedge {\rm{ }} - \left( {\mathop {\sum\limits_{k = 1}^{{n_0}} {\rho _i^k} }\limits^ \wedge } \right)}}{{n - {n_0}}} \end{array} \right\}$ 这样,在最优流程片段查询策略(10)的基础上,再融入基于逐次最小二乘法的参数估计调整模块,便得到了本文的自适应流程查询策略.该流程查询策略方案很好地利用了历史流程片段查询信息来推断未知流程片段的查询信息.在软件系统中,该算法思想能够对设计者重用流程片段提供方法论的指导作用,并对流程片段的重用质量提供理论保障.自适应流程片段查询整体算法思想如 图 2 所示.

4 实验分析

本节将通过两组实验来验证本文提出的自适应流程查询策略的有效性和可行性:首先,通过一组仿真实验验证其性能;然后,通过在真实流程数据环境下的查询实验,检验融入了本文提出的自适应查询策略以后对流程片段的查询会有怎样的性能影响.

4.1 仿真实验

本文首先用Matlab对流程片段自适应查询策略进行仿真.设开始有40单位数目的可用资源,即 X ₀ =40;有20个流程查询策略用例,即 D ={1,2,…,18,19,20};设每次查询能够搜索到的流程片段数目期望值为8,即 n =8,表 示为一个集合{ a ₁ , a ₂ ,…, a ₈ },令查询它们所花费成本的均值分别为${\mu _{{a_1}}} = 3,{\mu _{{a_2}}} = 5,{\mu _{{a_3}}} = 4,{\mu _{{a_4}}} = 6,{\mu _{{a_5}}} = 8,{\mu _{{a_6}}} = 2,{\mu _{{a_7}}} = 11,{\mu _{{a_8}}} = 4$;假设前18个查询用例产生的代价相等,即,$Cos{t_{{\zeta _t}}}(1) = Cos{t_{{\zeta _t}}}(2) = ... = Cos{t_{{\zeta _t}}}(18) = 5.$

本文采用一个随机流程片段查询算法与上面提出的自适应流程查询算法比较,即,随机查询算法每次从查询用例集 D 中随机地选择查询用例.根据 图 2 ,在自适应查询算法中,采用逐次最小二乘法,根据查询返回的结果对流程片段的查询概率进行在线估计.在实验中,对两种查询算法独立地各自仿真了100次, 表 1 列出了前15次的仿真结果以及所有100次得出的平均值和标准差( 表 1 中最后两列).

在 表 1 中: Re ( i )和 Ae ( i )分别为第 i 次仿真实验中的随机查询算法和自适应查询算法所用的查询用例数; Rp ( i )和 Ap ( i )分别为第 i 次仿真实验中的随机查询算法和自适应查询算法搜索到的流程片段数; Rd ( i )和 Ad ( i )分别为第 i 次仿真实验中的随机查询算法和自适应查询算法产生的代价总折扣; Mean 和 s 分别代表平均值和标准差.从 表 1 可以得出:整体上来看,自适应查询算法比随机算法要多用一些查询用例,但是自适应算法能够搜索出更多的满足需求的流程片段.而且非常有意义的是,自适应算法能够获得更大的代价折扣.从 表 1 还可看出,自适应算法每项指标的标准差都小于随机算法的标准差,这说明自适应算法的稳定性更好.

序号	i															Mean	s
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Re ( i )	9	12	10	7	12	5	11	14	10	9	13	11	9	12	8	10.6	2.36
Ae ( i )	13	15	9	13	14	10	11	11	13	12	10	14	11	10	11	12.9	1.82
Rp ( i )	3	6	2	6	2	3	6	5	1	5	6	4	4	4	3	4.3	1.67
Ap ( i )	8	8	5	4	2	6	7	6	5	7	6	6	6	4	5	6.2	1.53
Rd ( i )	16	19	14	27	14	14	13	14	19	16	29	19	13	29	30	19.6	6.52
Ad ( i )	29	22	25	28	32	25	32	34	24	22	26	26	28	30	21	28.5	3.88

4.2 真实数据集下流程查询实验

在上一节,我们通过仿真实验验证了本文提出的自适应流程查询算法的可行性和有效性,这一节通过真实流程数据下的实验进一步补充验证.首先,利用2009年的Web服务竞赛数据产生工具(Web service challenge testset generator)CTG ¹ (http://ws-challenge.georgetown.edu/wsc09/software.html)生成了一个包含400 000个流程片段的数据集,其中每个流程片段所包含的每个服务都拥有5~10个输入和输出参数.我们抽取出每个服务的两个QoS属性,即response time和throughput(产生出的每个数据中已经包含这两个属性值).在实验中,将用到几个变量:用 AP 表示流程片段数目;用 AS 表示一个流程片段查询要求返回的流程片段中所包含的服务数目, AR 表示这些服务之间的关系.本节所有的实验用Java实现,且硬件为一台配置为Intel(R) Core(TM) i5 CPU 760,2.80 GHz,4 GB RAM running Windows 7 (64-bit)的机器.

据我们所知,目前关于流程片段重用的研究工作还很少,尤其是关于任意粒度的流程片段重用的研究更少.本文的研究工作(用SCKY-A表示)建立在我们以前的研究工作(用SCKY表示) ^{[ 15 ]} 基础之上(即,在SCKY框架之上融入本文的自适应模块),因此,实验中结合考虑以前的研究,同时与跟我们研究最类似的VGI ^{[ 16 ]} 进行比较.在实现时,我们规定:SCKY,SCKY-A和VGI能搜索出的流程片段数目期望值为20;当SCKY-A搜索到某个从未被查询到的片段时,以代价补偿变量随机产生的值进行补偿,其均值为4、标准差为1;总共有60个单位数目的可用资源;对于SCKY-A,每次实验时,以均值为5、标注差为2仿真出20个查询用例,仿真出的每个值表示查询用例的成本消耗;每次查询,随机产生出用户的QoS约束值.

第1组实验为有效性评估实验.在该组实验中,考虑两种问题规模下的查询串,即: AS =5且 AR =4和 AS =12且 AR =11两种规模的查询串.该组实验我们考虑流程片段的精确查找,即:搜索出的满足条件的流程片段,不仅在长度上与查询串相等,而且结果串中每个位置上服务的功能必须与查询串中对应位置上要求的功能完全一致.我们分析每个流程片段查询在不同流程数量规模下(即 AP 变化),3种算法各自需要的查询时间(即响应时间, response time). 图 3 为该组实验的实验结果. 图 3 (a)和 图 3 (b)都得出一致的结论:给定一个用户的查询请求,随着 AP 的不断增长,即,从100K增加到400K,3种算法查询所需时间都不断增长;但是我们提出的两种算法(SCKY和SCKY-A)所花费的时间要远远小于VGI所花费的时间,我们的这两种算法都能在80ms以内返回结果;SCKY-A算法由于加入了在线参数调整,因此比SCKY要多花费一点时间,但从图中可以看出,这个多花费的成本非常小,由我们的实验数据发现,它们之间的差距仅在5ms左右.另外,从 图 3 也看出:问题规模越复杂(即, AS 的值从5变到12),所需查询时间也会更长一点.

第2组实验为精确度评估实验.在这组实验中,我们仍然考虑流程片段的精确匹配,实验的数据集规模为400K,即,我们取上面第1组实验中数据最大的那个流程片段库.当查询串的复杂度不同时(即, AS 的值以步长1从6增加到12),我们分析SCKY和SCKY-A两种算法的精确度性能.对于 AS 的每个取值,我们变换查询需求,并对两种算法对应地各做100次实验,然后计算出各自满足用户需求的次数,最后与总次数100的比值就是我们要求的实验值. 图 4 为两种算法的实验结果对比图,从图中可以看出:虽然两种算法的精确度都比较高,都在80%以上,但在SCKY基础上,加入了本文提出的自适应调整模块而构造出的SCKY-A有明显更高的精确度,且SCKY-A比SCKY要相对地优4%.不过,查询串的复杂度会对这两种算法的精度有一定的影响,从图中也可看出:随着 AS 的增大,两种算法的精确度会相对降低;但整体上,SCKY-A的性能要稳定些.

5 相关工作

本文借鉴软件控制论中的思想 ^{[ 17 ]} 来解决流程片段的重用问题,即,采用受控Markov链CMC方法来建模流程片段的自适应重用模型.软件测试在整个软件开发周期中的地位非常重要,在学术界也有大量关于软件测试的研究,其中,利用CMC模型来研究软件的自适应测试取得了很好的成果.在文献 ^{[ 18 ]} 中,详细分析了软件控制论在软件测试中的可行性和有效性,同时,它也对测试中的部分条件进行了特殊化处理,即:这里所说的受控特性,比如被测软件包含的缺陷数一定等.而文献 ^{[ 19 ]} 则更具体地提出了一个测试资源约束下的模型,并促进了自适应软件测试的研究发展.文献 ^{[ 20 ]} 则提出:对不同的缺陷,检测到的概率不一样.本文正是在综合这些研究工作精华的基础上,提出用CMC方法来分析流程片段重用中的最优查询策略问题.而且,我们的流程片段重用问题与软件测试问题也有很多相似的地方,比如:一个软件版本中所含有的缺陷数是一定的,同样,对于流程库中满足某个流程片段查询请求的流程片段数目也是一定的;每个缺陷被发现的概率是不一样的,同样,每个流程片段被搜索到的概率也是不同的;每次软件测试不可能找出所有的缺陷,同样,我们也没有必要对每个流程查询请求,去在流程库中找出所有匹配的片段,而且这样做查询效率将非常低下.我们采用查询策略搜索出最优的片段或片段集合;随着软件版本的更新,将会引入新的缺陷,同样,随着网上Web服务的不断加入,我们也将获得新的满足特定应用的流程片段;对于软件测试,测试人员要考虑到测试成本和资源,同样,我们重用流程片段也要考虑代价.正是这些软件测试和流程片段重用之间的共同点,激发了我们借鉴软件测试中的思想来研究流程重用中的问题,同时也说明我们用CMC模型来解决流程重用是可行的.

本文要解决的问题是寻找最优流程片段重用策略,但是关于任意粒度的流程片段重用研究却很少.将一个大的流程碎片化是重用流程片段中一个非常关键的技术,有大量研究关于如何劈开和描述流程片段.例如: Schumm ^{[ 21 ]} 研究了使用流程片段库在跨企业合作和应用集成中的潜在影响;Vanhatalo ^{[ 22 ]} 将流程模型分解成单入单出的片段(single-entry-single-exit,简称SESE),并用遗传算法对每个片段独立分析;而在文献 ^{[ 23 ]} 中,作者用形式化的方法将流程片段表示成不同的片段知识,并能对这些片段模型进行自由组合.但是这些工作都没有考虑如何搜索流程片段和如何提高流程查询的精度,他们主要关注过程中的复杂控制逻辑问题.本文不仅解决了流程片段的高速搜索问题,而且通过一个自适应的参数调整模块,能够充分利用历史查询记录信息,从而能够经济地对流程片段进行搜索并重用.

同时,关于任意粒度流程片段重用研究,我们与文献 ^{[ 16 ]} 中的工作最相近,即VGI.文献 ^{[ 16 ]} 对服务过程片段建立可变粒度索引的SSM-Tree,并在此基础上进行搜索查询.但该工作存在节点度大小瓶颈的缺陷,而且也未考虑流程片段的QoS属性以及概率查询.在我们以前的工作 ^{[ 15 ]} 中,即SCKY,我们借鉴自然语言中的Cocke- Kasami-Younger(CKY)算法思想来进行任意粒度大小的流程片段重用查询.SCKY考虑了精确查询、模糊查询以及概率查询,文献 ^{[ 15 ]} 中的实验也证明了SCKY性能比文献 ^{[ 16 ]} 中的VGI更优.本文在SCKY的基础上,从另外一个视角,即,借鉴软件控制论中的思想来研究流程片段的重用问题(SCKY-A).该工作充分考虑了用户的历史查询记录信息,并结合逐次最小二乘法来进行流程片段的自适应查询.在SCKY框架之上融入本文前面阐述的自适应模块,便构成了本文的基本框架.

本文的研究工作是对自适应软件系统研究的一个很好的补充,在一个业务复杂的软件系统中,如果我们能够很好地对业务流程进行重用,并能有效地重用任意粒度大小的流程片段,这将对整个软件的自适应性有重要的促进意义.关于自适应软件系统的研究,本文开始部分已有介绍,这里不再赘述.

6 结束语

本文借鉴软件控制论中的思想来研究流程片段的自适应重用问题,即,用受控的Markov链模型(CMC模型)来寻找流程片段的最优查询策略.经过一系列制约条件的约束和假设,提出了针对流程片段查询特殊应用环境下的CMC模型,并对该模型进行了优化处理.基于逐次最小二乘法,本文进一步提出了一个流程自适应查询策略,该策略充分利用流程历史查询记录信息,通过在线参数调整,能够帮助查询人员及时调整和优化查询策略.实验部分,首先通过Matlab环境下的仿真实验验证了本文模型的有效性和可行性;然后,真实流程数据环境下的实验更进一步验证了该自适应流程查询策略模型的有效性和高精确性.通过实验数据也可得出:基于在线参数调整的该自适应流程查询策略所需的额外时间成本很低,但却能够获得一个可观的精确度性能提高.

下一步的工作是继续优化该自适应流程查询策略算法,同时对本文的模型和算法进行扩展,使其能够更好地融入到流程片段任意粒度大小的重用环境里.

致谢 作者衷心感谢审稿专家提出的宝贵意见,感谢NASAC 2014大会上专家们的意见和建议.