Web服务工作流路由模型构造及QoS优化
胡春华1，彭昆湘2，刘济波1，刘安丰3
(1. 湖南商学院 计算机与电子工程学院，湖南 长沙，410205；
2. 湖南信息职业技术学院 教务处，湖南 长沙，410200；
3. 中南大学 信息科学与工程学院，湖南 长沙，410083)
摘 要：
摘 要：针对服务工作流的路由构造与优化问题，提出一种服务工作流的路由模型(Workflow route model, WRM)。该模型将功能相同的服务复本聚集成一类服务集合，每类服务集合采用聚合树的方式组织，同时，依据工作流之间的路由组合关系形成路由构造图，在此基础上提出一种基于QoS的工作流路由算法，在服务动态变化时能满足不同应用的多维QoS需求。实验结果表明：该模型能较好地组织服务资源；路由算法综合多维QoS目标优化，可在多项式时间内计算出较佳的工作流路径，适合于分布式环境中服务工作流的构造与协作。
关键词：
中图分类号：TP393 文献标识码：A 文章编号：1672-7207(2009)04-1040-07
Construction services workflow route model and QoS optimization
HU Chun-hua1, PENG Kun-xiang2, LIU Ji-bo1, LIU An-feng3
(1. School of Computer and Electronic Engineering, Hunan University of Commerce, Changsha 410205, China;
2. Teaching Affair Office, Hunan College of Information, Changsha 410200, China;
3. School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: The service workflow’s route structure and optimized question were studied, and one kind of service workflows route model (Workflow route model, WRM) was proposed. The same function service duplicate was the accumulated kind of service set in the model, and each kind of service set was organized by the spanning tree. The route combination relations based on the workflows formed the route constructional drawing, and one kind of QoS routing algorithm was proposed. When service dynamically changes, the algorithm can satisfy the different multi-dimensional QoS application demands. The results show that, compared with other structural models and algorithms through the computer simulation, the model organizes the service resources well, and the route algorithm can synthesize the multi-dimensional QoS goal optimization, which can calculate a good workflow way in the multinomial time. The structure and cooperation suit the service workflow demand in the distributed environment.
Key words: service workflow; route model; multi-quality of service; optimization
随着电子商务的日益复杂和跨企业协作的不断发展，Web服务工作流因能支持松散耦合的分布式信息集成，在Web服务组合领域得到了有效应用[1]，使得基于Web服务的工作流得到了工业界和学术界的广泛重视，但目前还有许多基本问题亟待解决。如：
a. 缺乏较好的服务工作流路由模型[2]。网络中服务虽然丰富，但缺少一种有效的服务组织模型，导致用户难以利用这些丰富的Web服务。其主要原因在于，各服务提供者提供的Web服务往往是动态生成，且又随时消失，导致服务提供者很难将自己的服务在全球范围内广播而让用户知道该服务的存在；用户通过各种搜索平台得到的服务往往存在过时的信息，真实的Web服务早已消失[3-4]。实际上，尽管服务网络上Web服务失效非常频繁，但对整个服务网络来讲，其平均无故障时间很长，从而，建立一种有效服务组织模型，有助于屏蔽服务物理上动态变化的影响，可以保证Web服务的可用性。
b. 服务工作流由一系列有机组成的Web服务构成，然而，如何从大量功能相同(相似)的Web服务中选出一组服务，使得服务工作流具有良好的服务质量、较高的用户满意度也需亟待解决[5]。
c. 服务路由还存在不少困难，如：服务路由是在服务覆盖网下的工作流最佳路径选择过程，但目前还没有一种能组织起服务路由的覆盖网络，因而，其服务路由还缺乏实施基础。其次，服务路由的选择需要基于一定的标准，QoS作为一个可以衡量服务质量的概念，从用户方的角度包含了费用、时间等非功能属性[3, 6]；而对服务提供方来说希望获得最大的收益，能够提供尽可能多的服务，希望做到负载均衡等系统性能。目前，对于服务工作流(甚至服务组合)执行路径的选择往往偏重于特定系统或者特定的状况，还没有一种普适性的类似于IP路由不依赖于特定公司的工作流路由模型[7-8]。
针对以上问题，本文作者提出一种支持服务工作流的路由模型的层次结构，包括服务登记层、服务形成层2个层次；在路由模型的基础上，将服务的路由选择算法作为系统的有机组成模块，以满足不同应用的多维QoS要求。
1 服务工作流路由模型
网络中Web服务资源异常丰富，且同时存在大量功能相同或相近，QoS差异很大的服务，本文中，Web服务工作流以及其各参数的定义见文献[9]。
这里提出基于Web服务工作流的服务组织多层结构模型能起2个方面的作用：一是对服务的有效组织，在服务有效组织的基础上，基于QoS的工作流路径选择就可以在对服务充分掌握的基础上进行QoS优化；二是工作流路由模型由聚合树组织同类服务，聚合树之间依据工作流逻辑模型组合而成，实际上起到了一种与逻辑工作流相映射的实际服务实例，使得用户逻辑定义的工作流结构很容易映射为实际工作流，该结构模型也与文献[9-10]中的结构模型类似。
综上所述，Web服务工作流路由模型(Workflow route model, WRM)主要由2个部分组成(见图1)：服务登记中心(Service enrol central, SEC)和服务工作流形成场景(Workflow forming scene, WFS)。
图1 Web服务工作流路由模型
Fig.1 Route model of Web services workflow
1.1 服务登记中心(SEC)
SEC主要起到查找Web服务的作用，胡春华等[9-10]提出了一种与DNS类似的主动分布式Web服务注册系统，本文在其基础上改进，利用与DNS类似的服务登记中心(SEC)，服务提供者直接向SEC注册来完成Web服务的登记，同时，本文采用一种聚合图的方式来组织工作流所对应的服务，因此，在服务的组织上，并不让每一个服务供者直接向SEC注册，由于服务的动态产生与消失现象比DNS系统的复杂，因此，直接运用与DNS类似的注册方法使服务的动态性信息的维护性不高，系统的负载压力大。在此，对于1棵聚合树来说，选中其中1个作为中心节点，由其来负责整棵树与SRS的服务信息维护，这样，对于广域网中的一类服务只需要1个节点与SRS交互就可以了，大大减少了服务信息维护的负载压力，为了保持聚合树的鲁棒性，对中心节点采用冗余的方法。
1.2 服务工作流形成场景
对于互联网中某类功能相同或者相似、QoS各异的服务通过文献[9]中设定的方法形成1棵Web服务聚合树，对于每棵树存在1个中心节点和准中心节点，它们负责树中所有信息的维护，同时，与SEC间存在一个定时的查询动作，以便让SEC知道该聚合树还“活着”，它由中心节点在交互时将树内信息报告给SEC；同时，依据工作流逻辑模式关系，将服务间的“上下游”对应的聚合树之间关联起来，形成服务聚合图场景，如图1所示。这样，执行路径的选择可以在工作流逻辑模式的指引和服务聚合图的交互作用下得到。
可见，服务工作流的路由模型代表了实际工作流逻辑结构相对应的实际服务实例组合场景，建立了一种将工作流逻辑变成简单服务实例的映射关系，实现了工作流服务的选择(路由)成为服务的有机组成模块，从而使得构造普适性的Web服务工作流成为可能，提高了工作流组合过程的有效性。
2 基于QoS的工作流路由
2.1 基于QoS的工作流路由问题与计算
基于QoS的工作流路由问题相对于IP路由来说比较复杂。其主要原因是IP路由是一种单路径的寻优过程，而工作流路由具有多种控制结构，这是工作流的本质所在，必须在路由中得到完整反映。
基于QoS优化的工作流路由问题就是寻找一条较优的满足用户工作流逻辑结构的实际服务实例的执行路径[12]。由于不同的服务质量指标在工作流路径中具有不同的性质，有的具有相加性，如执行时间、执行费用等，而有些指标具有相乘性，如可用性指标；而且不同的服务指标在不同的控制过程中其计算的性质也不相同，例如执行时间在顺序控制关系中满足相加性，而在并行关系中取最大值。正因为其QoS优化的复杂性，虽然有不少工作流QoS优化的研究，但大部分简化了问题处理的复杂性，却不能客观地反映工作流的真实情况[3, 5]。为此，本文提出一种计算的新方法，采用逻辑结构与工作流路由模型相结合的方法，工作流逻辑结构反映了工作流总体结构特征，而路由模型反映了具体实例的选择，两者结合实现了从总体结构到微观实例选择的QoS优化。本文中，QoS的选取与文献[9]中的类似，采用与用户服务相关程度较高的参数，如计算能力、费用、执行时间、可用性和信誉度等非功能参数，分别用QoS(cap), QoS(cost), QoS(time), QoS(ava)及QoS(rep)等表示。
这里通过算法1来分析在服务工作流的不同逻辑控制关系和不同服务质量指标的计算方法；给出这5种服务质量指标在6种不同控制关系中的计算方法。工作流的6种控制关系见文献[9]，对整个工作流服务质量可以反复调用算法1来计算。当然，对于其他服务质量指标也可以进行类似的计算。
算法1 服务工作流服务质量指标计算方法：
begin
for each 
∈CL do //对于控制关系
switch(parse()) { //控制关系不同计算方法不同
case sequence: //顺序关系
QoS(cap)=min(QoS(cap)pre, QoS(cap)next);
//选取路径中上下游间计算能力最小的，
即瓶颈
QoS(cost)= QoS(cost)pre+QoS(cost)next;//
费用相加
QoS(time)= QoS(time)pre+QoS(time)next; //
时间相加
QoS(ava) = QoS(ava)pre
QoS(ava)next;//
可用度相乘
QoS(rep) = QoS(rep)preQoS(rep)next; //
信誉度相乘
case while: //循环关系
QoS(cap)=min(QoS(cap)pre, QoS(cap)next);
QoS(cost)= QoS(cost)pre+QoS(cost)next;
QoS(time)= QoS(time)pre+QoS(time)next;
QoS(ava) = QoS(ava)preQoS(ava)next;
QoS(rep) = QoS(rep)preQoS(rep)next;
//循环关系与顺序关系基本同，pre表示循环前的服务
case switch: //选择关系
QoS(cap)=QoS(cap)true;
//选取服务的计算能力
QoS(cost)= QoS(cost)true;
QoS(time)= QoS(time)true;
QoS(ava) = QoS(ava)true t;
QoS(rep) = QoS(rep)true;
case flow: //并行关系
QoS(cap)=min(QoS(cap)1, …, QoS(cap)n);
//选取并行路径中计算能力最小的
QoS(cap)=QoS(cap)1+…+QoS(cap)n);
//并行路径中所有费用相加
QoS(time)=min(QoS(time)1, …, QoS(time)n);
//选取并行路径中执行时间最长的
QoS(ava)=min(QoS(ava)1, …, QoS(ava)n);
//选取并行路径中可用度最小的
QoS(rep)=min(QoS(rep)1, …, QoS(rep)n);
//选取并行路径中信誉最小的
case pick: //事件选择
与switch关系类似;
case 
: //优先关系
与switch关系类似;
end
end
在给出了工作流控制结构的QoS指标计算方法后，下面再给出完整的工作流QoS优化算法，采用基于用户可定制的线性规划方法。
2.2 基于多维QoS的服务工作流路由算法
可以证明，即使是IP路由中的多维(二维以上)QoS优化问题是NP-complete问题，因而，对于多维QoS工作流路由来说也是NP-complete问题。但在实际中，用户只需要得到自己偏好的工作流路径即 可，并不需要“最优”的工作流路径，因此，本文采用的多维QoS优化是基于用户偏好的多目标线性规划方法。
问题的目标：假设在系统QoS优化的选择目标中，决策空间X(x1, …, xn)T分别对应服务能力、费用、执行时间、可用性、可信度等，由f1(x), …, fp(x)目标函数分别代表QoS优化调度的目标函数，如服务能力最大、费用函数最小、可用性函数最大等。通常，希望在QoS上的可行集(Q1, Q2, …, Qn)上得到满足以下目标的优化目标：
min f1(X), min f2(X), max f3(X)。 (1)
由于式(1)中的max函数可以通过转换化为min函数，因此，加权法的一般形式是：
。 (2)
其中：fj(x)≥εj；j=1, …, p；x∈X；Wi为根据调度目标给定的一组权值，它反映了请求对每个优化目标的权重。为适合不同用户不同的QoS偏好，本文要求用户在对系统提交工作流逻辑结构模式时，也确定不同QoS目标的优化权重，而用户的工作流逻辑结构与QoS目标的优化权重都可以采用通用的XML语言描述，用户定义后就可以向系统提交请求，然后，得到“最佳”的工作流路径。
基于多维QoS优化的工作流路由算法的基本思想是：用户通过分析工作流逻辑结构以及多维QoS的优化权重Wi后向路由模型提交，路由模型接到工作流路由请求后，首先依据工作流的开始服务参数在SRS中查找与之对应的服务聚合树，再根据式(2)，在此服务聚合树中选取1个“最佳”的服务实例，此服务实例即为工作流的第1个服务实例。然后，在逻辑工作流结构的指引下，依次遍历服务聚合图。由于服务聚合图是逻辑结构到实际服务实例的映射，但服务聚合图中可能包含了用户没有定义的工作流路径，而工作流逻辑结构也可能限定了某些路径必须经过(或者不能经过)的指定节点，因此，在用户定义的工作逻辑结构的指引下，沿着服务聚合图进行遍历，在遍历过程中选择最优的工作流路径，直到最后一个服务选取后，服务工作流路径便完成。
从上面的算法思路可以看出，本文的工作流路由模型具有良好的用户可定制性，即用户可以采用通用的XML语言定制个性化的工作流路径。这种定制包含2个方面：
a. 用户可以从工作流的QoS偏好进行定制，例如：若用户对执行时间不敏感，而对费用较敏感，则在给出权重系数时，对费用的权重系数相对大些；
b. 用户可以对执行路径进行定制。如保密性较高的用户可以明确规定执行路径不能经过保密性不高的区域，或者商业竞争对手所在区域，这样，用户可以在逻辑工作流模型中明确用deny, allow和force等关键词后面指出约束的对象。
以上2个方面在本文的路由模型中很容易实现，只需要在从逻辑到服务实例的映射中去掉受限的服务即可。
工作流路由算法及其所用数据结构为：
Stuct link {
Link *next; //指向路由的下游节点
Link *parallel; //指向分支的路由节点
} *Link；
struct Route-link {
float capa; //工作流的最小计算能力
float cost; //工作流的总费用
float time; //完成工作流的最早执行时间
float ava; //工作流的可用度
float rep; //工作流路径的总信誉度
Link *firstLink; //选取的工作流路径
} *Route-Link;
在算法的执行中需要2个堆栈，堆栈的作用非常明显。分析工作流的逻辑结构可以得知，工作流由几种基本控制结构形成，可以用“( )”以及控制符和服务类型来表示工作流逻辑结构，可用如例1所示逻辑结构表示。所以，在路由的运算推进中，可以设定有优先级，用这些堆栈来控制工作流控制运算符间的优先级关系。
算法的基本流程是：根据工作流的逻辑结构，向前推进来求解QoS优化路径，每推进逻辑结构中的1个服务类，则依据QoS优化算法从相应的聚合树中求得对应的最优服务实例。而每推进1个控制结构符，便与控制结构符堆栈顶元素比较优先级，若优先级小，则放入控制结构符堆栈，否则，将服务实例堆栈的服务进行QoS计算。直到堆栈都为空为止，这样，QoS优化路径便被求出。
算法2 基于多维QoS工作流路由算法。
Initialization:
{
Route-Link R;
R->cap=0;
R->cost=0;
R->time=0;
R->ava=0;
R->rep=0;
CurrentNext=R->firstLink；
// CurrentNext为当前处理指针
R->firstLink->next=NULL; //初始路径节点为空,
R->firstLink-> parallel =NULL;
InitStack(CONTROL);
//初始控制符栈CONTROL为空；
//控制符还包括”( )”
PUSH(CONTROL，“#”)；//虚设1个栈底符
InitStack(SERVER); //初始服务栈SERVER为空；
}
for each element in 工作流逻辑结构 do {
if (element
CONTROL) {
PUSH(SERVER, element);
Else
Switch(priror(GetTop(CONTROL),element) {
Case ‘<’: PUSH(CONTROL element); break;
Case ‘=’: POP(CONTROL,control); break;
Case ‘>’: POP(CONTROL,c);
POP(SERVER,ele[ ]);
//将所有服务堆栈的服务弹至数组ele[ ]中
procedure-map(ele[ ],control, R, CurrentNext);
//调用过程计算路径
break;
}
retrun R; //R返回1条最佳的工作流路径
}
/*以上步骤是针对工作流逻辑结构进行计算，下面的过程是映射到具体服务实例的计算*/
Processing procedure-map (ele[ ], control,
R, CurrentNext)
{
step 1 for each ele {
step1.1通过SRS或者路由模型得到对应的聚合树；聚合树的每个服务都是此ele的服务实例；
step 1.2 用式(2)计算得到聚合树内最优的服务实例WS;
}
step 2 每1个ele[ ]都得到1个服务实例WS形成数组WS[ ]；
step 3 根据控制符control，依据算法1计算得到各QoS参数，并给工作流路径R的各参数赋值；
//计算得工作流路径的服务质量指标
step 4 Switch(control) { //依据控制关系给工作流路径赋值
case sequence: CurrentNext->firstLink=WS[0]；
CurrentNext= WS[0]；
case while: CurrentNext->firstLink=WS[0]；
CurrentNext= WS[0]；
case switch: CurrentNext->firstLink=WS[ ]；
CurrentNext= WS[ ]；
//当前指针指向所选择的节点
case pick: CurrentNext->firstLink=WS[ ]；
CurrentNext= WS[ ]；
//当前指针指向所选择的节点
case : CurrentNext->firstLink=WS[ ]；
CurrentNext= WS[ ]；
//当前指针指向所选择的节点
case flow: CurrentNext->firstLink=WS[0]；
CurrentNext-> parallel=WS[1, …, n];
//当前指针指向所选择的节点，并行分支指向并行节点
} //计算得到路径所经过的服务实例节点
}
3 实验结果与分析
为了更深入地阐明所提出的调度模型及算法的意义和作用，搭建了Web服务组合管理调度的原型系统SWES[11]。同时，工作流技术被认为是服务组合技术的一种具体方式[9-12]，因此，本文选取的对比系统是与本文类似的服务组合系统[13]。在对比中，用文献[13]中Spidernet的服务组合成功率作为工作流的成功率。
动态服务情况下Spidernet和WRM执行成功率的对比结果见图2。从图2可以看出，在服务动态产生与消失比较频繁的情况下，由于本文的工作流路模型对服务进行了很好的组织，因此，服务的动态产生与消失对本文的模型影响较小，优势较明显。
图2 动态服务情况下执行成功率对比
Fig.2 Comparison of success radio under dynamic services
本文的模型能够较好地处理新服务的加入，新服务由于刚加入系统，负载较小，其处理能力大，因此，服务路径选取的机会多，但其他系统基本没有这样的规律。图3表示的是当不同比例的新服务实例加入到系统中，经过多长时间后，工作流路径中新服务实例占整个新服务实例达到50%的时间。其时间越小，表示QoS优化能力越强。图3中，时间的定义是：每批次发出10个工作流申请，每批次算1个时间单位。从图3可以看出，大约在第5批次，新服务比例达到50%。
图3 50%新服务下工作流执行时间
Fig.3 Workflow executing time under news services 50%
增加服务实例数的执行时间对比结果见图4。可见，在增大网络的规模的同时，也增加服务实例数，网络的规模对系统的影响也不大，这说明本文提出的模型具有很好的扩展性。
1—Spidernet; 2—WRM
图4 增加服务实例数的执行时间对比
Fig.4 Comparison of executing time under increase service instances number
从算法2可容易得出服务节点数与边数，时间复杂度为O(n+e)。图5所示为服务工作流路由算法的执行时间，可见，在网络规模一定的情况下，单纯增加服务的数目，对算法所需时间几乎没有影响。
1—Spidernet; 2—WRM
图5 不同服务实例下工作流路径查找时间
Fig.5 Path executing time under different numbers of
service instances
4 结 论
a. 对服务资源依据工作流关系进行了较好的组织，形成了与用户自定义工作流逻辑结构相对应的物理服务实例结构，使得从用户的逻辑工作流结构很容易映射到实际的物理服务实例。
b. 服务工作流路由模型主要由服务登记中心和服务组合形成场景2部分组成，形成场景又依据工作流关系形成服务聚合图的方式来组织Web服务。
c. 由于路由算法是在工作流逻辑结构的指引下，从工作流模式到服务实例的映射过程，提供了用户可定制的工作方式，又可提供用户偏好的QoS，并能够充分利用网络上第三方提供的Web服务。
d. Web服务工作流路由模型及QoS优化方法可以为普适性的服务计算提供较高服务质量和较高用户满意度的服务。
参考文献：
[1] Papazoglou M P, Georgakopoulos D. Service-oriented computing[J]. Communications of the ACM, 2003, 6(10): 25-65.
[2] Danilo A, Barbara P. Adaptive service composition in flexible processes[J]. IEEE Transactions on Software Engineering, 2007, 33(6): 369-384.
[3] Jorge C, Aamit S, John M. Quality of service for workflows and web service processes[J]. Journal of Web Semantics, 2004, 1(3): 281-308.
[4] Gao X, Yang J, Papazolou M P. The capability matching of Web services[C]//Proceedings of IEEE international Symposium on Multimedia Software Engineering. New York: IEEE Computer Society, 2002: 56-63.
[5] Zeng L Z, Boualem B, Anne H H, et al. QoS-aware middle ware for Web Services composition[J]. IEEE Transactions on Software Engineering, 2004, 30(5): 311-327.
[6] 刘安丰, 陈志刚, 陆静波, 等. 网格环境中一种有效的Web服务资源组织机制[J]. 计算机研究与发展, 2004, 41(12): 2141-2147.
LIU An-feng, CHEN Zhi-gang, LU Jing-bo, et al. An effective organizing mechanism for Web services resource in grids[J]. Journal of Computer Research and Development, 2004, 41(12): 2141-2147.
[7] Yang S J. Design issues and performance improvements in routing strategy on the internet workflow[J]. International Journal of Network Management, 2003, 13(5): 59-374.
[8] Liu Y T, Anene H H, Zeng L Z. QoS computation and policing in dynamic Web service selection//Proceedings of the WWW 2004. New York: ACM Press, 2004: 66-73.
[9] 胡春华, 吴 敏, 刘国平, 等. 基于服务生成图的Web服务工作流可用性研究[J]. 计算机工程, 2006, 32(23): 30-33.
HU Chun-hua, WU Min, LIU Guo-ping, et al. Research on availability of Web service workflow based on service spanning graph[J]. Computer Engineering, 2006, 32(23): 30-33.
[10] Seungh H H, Yu C K. Implemention of a bandwidth allocation scheme in a token-passing fieldbus network[J]. IEEE Transactions on Instrumentation and Measurement, 2002, 51(2): 246-251.
[11] 胡春华, 吴 敏, 谢 勍, 等. SWES: 基于QoS的服务工作流调度性能评价系统[J]. 中南大学学报: 自然科学版, 2007, 38(5): 962-969.
HU Chun-hua, WU Min, XIE Qing, et al. SWES: performance evaluation system for Web service workflow on QoS[J]. Journal of Central South University: Science and Technology, 2007, 38(5): 962-969.
[12] WANG Pu-wei, JIN Zhi, LIU Lin, et al. Building toward capability specifications of Web services based on an environment ontology[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(4): 547-561.
[13] Gu X, Nahrstedt K, Yu B. Spidernet: An integrated peer-to-peer service composition framework[C]//Proceedings 13th IEEE International Symposium on High-Performance Distributed Computing (HPDC-13). Honolulu, USA: IEEE Press, 2004: 110-119 . .
收稿日期：2008-10-15；修回日期：2009-01-20
基金项目：中国博士后科学基金资助项目(20080440988)；湖南省自然科学基金资助项目(09JJ4030)；中南大学博士后科学基金资助项目(2008年)
通信作者：胡春华(1973-)，男，湖南新化人，博士，副教授，从事Web服务工作流、支持跨企业协同等研究；电话：0731-88688270；E-mail: huchunhua777@163.com
