积分商城

最新搜索： 解压缩软件 UCD3138 iar Smith 购买积分 注册表
您现在的位置是：首页 > 技术资料 > 基于时序约束分解的QoS感知的Web服务组合
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

基于时序约束分解的QoS感知的Web服务组合

更新时间：2019-12-24 08:15:10 大小：2M 上传用户：zhiyao6查看TA发布的资源 标签：QoS感知Web服务 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

基于时序约束的QoS感知的Web服务组合(TC-QSC)问题是在考虑时序约束的基础上寻找满足QoS约束或效用最大化的Web服务组合问题,受到了越来越多的关注.本文提出了一种时序约束分解方法,把施加于整个或部分工作流的时序约束分解为施加于每个活动的局部时序约束,从而将TC-QSC问题转换为一般的QoS感知的Web服务组合(QSC)问题,并通过过滤不满足局部时序约束的候选服务,一定程度上减小原问题的规模.这种时序约束分解过程主要依赖于工作流及其涉及的活动,而与各活动的候选服务关联不大,复杂度较低.实验测试了该方法的效果与时间开销,验证了其对于局部优选算法的必要性.


部分文件列表

文件名 大小
基于时序约束分解的QoS感知的Web服务组合.pdf 2M

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）
5
Vol． 45 No． 5  
May 2017  
第
期
电
子
学
报
2017  
5
ACTA ELECTRONICA SINICA  
年
月
QoS  
Web  
服务组合  
基于时序约束分解的  
感知的  
1，2  
3
2
， ，  
叶恒舟 李陶深 关云慧  
( 1．  
，
广西大学电气工程学院 广西南宁  
530004; 2．  
，
桂林理工大学信息科学与工程学院 广西桂林  
541000;  
3．  
，
广西大学信息与工程学院 广西南宁  
530004)  
:
QoS  
Web  
( TC QSC)  
－
QoS  
问题是在考虑时序约束的基础上寻找满足  
摘
要
基于时序约束的  
Web  
感知的  
服务组合  
，
．
，
约束或效用最大化的  
或部分工作流的时序约束分解为施加于每个活动的局部时序约束 从而将  
Web ( QSC)  
服务组合问题 受到了越来越多的关注 本文提出了一种时序约束分解方法 把施加于整个  
，
TC QSC QoS  
问题转换为一般的  
－
感知的  
，
，
．
服务组合  
问题 并通过过滤不满足局部时序约束的候选服务 一定程度上减小原问题的规模 这种时序约  
， ， ．  
束分解过程主要依赖于工作流及其涉及的活动 而与各活动的候选服务关联不大 复杂度较低 实验测试了该方法的  
，
效果与时间开销 验证了其对于局部优选算法的必要性  
．
:
;
; QoS ; Web  
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
时序约束 约束分解  
感知  
服务组合 贪心算法  
0372-2112 ( 2017) 05-1150-08  
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 05． 018  
:
TP393  
:
A
:
文章编号  
文献标识码  
电子学报  
QoS-Aware Web Service Composition Based on  
Temporal Constraints Decomposition  
1，2  
3
2
YE Heng-zhou ，LI Tao-shen ，GUAN Yun-hui  
( 1． College of Electrical Engineering，Guangxi University，Nanning，Guangxi 530004，China;  
2． College of Information Science and Engineering，Guilin University of Technology，Guilin，Guangxi 541000，China;  
3． College of Information and Engineering，Guangxi University，Nanning，Guangxi 530004，China)  
Abstract: The problem of Temporal Constraints based QoS-aware web Service Composition ( TC QSC) is becom-  
－
ing increasingly critical in recent years． Its objective is to select the Web service composition which maximizes the QoS utili-  
ty while preserving QoS constraints and temporal constraints． This paper proposes a temporal constraints decomposition  
method that formulates the TC QSC problem into a general QoS-aware Web service composition ( QSC) problem by means  
－
of decomposing the temporal constraints imposed on the whole or part of the workflow to a set of local temporal constraints  
for each activity． So the problem scale is reduced by filtering out those candidate web services violating local temporal con-  
straints． The temporal constraints decomposition process is mainly dependent on the workflow and activities involved in it，  
while it has little to do with the candidate services． Therefore，its complexity is lower． The experiments have demonstrated  
the effectiveness and time cost of the proposed method and verify its necessity to local selection algorithm．  
Key words: temporal constraint; constraint decomposition; QoS-aware; Web service composition; greedy algorithm  
．
于后一类  
1
引言  
［3］  
QSC  
NP  
，
简单的全局搜索算法  
一般  
问题是  
难的  
，
近年来 很多研究致力于解决  
QoS  
Web  
服
感知的  
．
将导致指数级的时间复杂度 基于贪心策略的局部优  
［4 ～ 6，15］  
( QoS-aware Web service composition，QSC)  
务组合  
优化问  
，
具有很好的时空性能 但不能保证全局约  
选策略  
． : ，  
题 这些研究可分为两类 一类认为工作流是未知的 需  
．
束 另一类研究将  
QSC  
，
问题建模为一个已知模型 如整  
［1，2］  
［7］  
;
要探究服务之间的依赖关系  
另一类认为工作流已  
( ILP )  
、
数 线 性 规 划  
多 维 多 选 择 背 包 问 题  
［3 ～ 14］  
［6］  
［3］  
，
知 重点关注服务的优化选择问题  
．
本文的研究属  
( MMKP)  
、
( MILP)  
，
等 这些模型  
混合整数线性规划  
: 2015-10-20;  
: 2016-05-06;  
:
责任编辑 蓝红杰  
收稿日期  
修回日期  
:
基金项目 国家自然科学基金  
( No． 51365010) ;  
( No． 2014GXNSFBA118269)  
广西自然科学基金  
1151  
5
:
叶恒舟 基于时序约束分解的  
QoS  
Web  
感知的 服务组合  
第
期
．
的求解仍面临着指数级时间复杂度的挑战 进化类算  
［8 ～ 12，16］  
( 、  
法 如遗传算法 粒子群算法  
)
也广泛应用于求  
QSC  
， ，  
问题 这类算法适应性强 容易满足全局约束  
，
解
， 、  
可平衡时间开销与优化效果 但存在收敛速度慢 稳定  
．
性不强等缺点  
，
为了兼顾局部优选和全局统筹的优点 采用全局  
QoS  
约束分解以降低时间复杂度成为了一种有效的选  
2
工作流模型  
． ［13］ QoS  
择 文献 先将全局 约束分解为满足用户偏好  
，
的局部约束 然后利用局部最优策略寻找合适的组合  
，
一个组合服务可由工作流描述 而一个工作流由  
， ，  
服务 但其不能保证全局约束 也不能直接支持复杂  
．
，
一些活动及模式构成 在工作流中 一个活动代表具有  
QoS Web ，  
服务 这组服务称为该  
． ［14］ QoS  
工作流 文献 采用遗传算法来求解 约束分解  
、
相同功能 不同  
的一组  
( QCD)  
，
模型 以确定每个活动的每个  
QoS  
属性参考  
;
活动的候选服务集 模式用于描述活动之间的依赖关  
，
值 在进行局部选择时选择与这些参考值最为接近的  
， :  
系 比较常见的模式有 顺序  
( SEQ) 、  
并发  
( AND) 、  
选择  
［3］  
， ，  
候选服务 该方法支持复杂工作流 因采用遗传算法  
，
( XOR)  
．
本文所讨论的工作流是比较常见的一类工  
作流 它们由这三种模式经过有限次连接与嵌套而成  
1) ．  
， ． ［17］  
效率偏低 也不能保证全局约束 文献 也基于分  
，
， ，  
解思想 但它分解的不是约束而是全局效用 是通过  
(
见定义  
寻找全局效用与局部效用之间的关联逐步调整局部  
1
SEQ、AND  
XOR  
，
中的任意一种  
定义  
设⊙为  
或
， ．  
选择方 案 来 实 现 的 体 现 的 是 一 种 贪 心 策 略 文 献  
:
工作流可以递归定义如下  
［18］  
提出了一种把全局  
QoS  
约束分解为局部约束的  
( 1)  
A 、A  
1
， A  
是活动 则  
A
⊙
2
;
是工作流  
若
2
1
，
，
模型 并采用了一种改进的遗传算法求解该模型 但  
该文只讨论了模型的优化目标而没有讨论相关约束  
( 2)  
A
、F  
，
是工作流 则  
A
F
F
及
若
是活动  
⊙
1
1
1
1
1
A
;
是工作流  
⊙
1
， 9  
条件 其实验也仅针对包含 个活动的给定工作流  
．
( 3)  
F 、F  
1
， F  
是工作流 则  
F
⊙
2
;
是工作流  
若
2
1
，
比较而言 本文所采用的时序约束分解  
( TCD)  
模型建  
( 4)  
F 、F  
1
， F  
是工作流 且  
F ，  
的一部分 则称  
2
若
是
2
1
、 、  
立在包含顺序 并发 选择等模式的常见工作流之上  
，
F
F
．
的子工作流  
是
1
2
，
其目标是获取每个活动应满足的时序约束 并使每个  
1 ， F T  
由定义 可知 一个工作流 可与一棵二叉树 对  
活动满足时序约束的候选服务的个数尽量多且分布  
， F ， F  
应 叶子节点为 涉及的各个活动 非叶子节点为 涉  
， ，  
均衡 并保证当局部约束得到满足时 全局约束也一  
， F ，  
及的各个模式 各个子树代表 的一个子工作流 树根  
．
定可以满足  
在一些业务流程中会带有各种时序约束  
( A1 A10  
分别  
F．  
为
［19，20］  
．
如
，
显然 我们可以得到以下两个性质  
:
1
图
所描述的某电子产品的研发流程  
到
( 1) T F ，v  
设 是 对应的一棵二叉树  
T
为
的一个非  
( v． rc)  
均
“ ”、“ ”、“ ”、“  
代表 需求分析 主板设计 外设设计 硬件测  
， v  
叶子节点 则 的左子树  
( v． lc)  
v
和 的右子树  
”、“  
”、“  
”、“ ”、  
升级现有软件  
试
软件系统分析  
软件外包  
;
不为空  
“
”、“  
重构软件 软件测试  
”、“ ”)  
软硬件集成测试 可能存  
( 2)  
T
F
，r  
T
为 中叶子节  
设
是
对应的一棵二叉树  
: “  
在如下时序约束 整个研发时间不超过  
12  
，
个月 软硬  
，s  
T
， r  
中非叶子节点的个数 则  
F
为 中涉及  
点的个数  
为
4 ， 1  
件开发的时间不超过 个月 主板设计时间不超过 个  
， r = s + 1．  
的活动个数 且  
， ”．  
月 且应在软件系统设计之前完成 这些约束可符号  
，F F ，  
通常 的时序约束施加于 的各个子工作流 因  
: t( 1 14)  
－
12，t( 2 13)  
－
4，t( 3 3)  
－
1，t( 6  
≤
化为  
12)  
≤
≤
F
T ， t( v)  
的时序约束施加于 的各个节点 用 ≤τ 表  
v
此
－
3，  
其中  
t( i j)  
－
i j  
表示完成从 到 之间的流程需要  
≤
T
v ． 1  
的节点 应满足的时序约束 例如图 所示的工作  
示
．
的时间 尽管  
QoS  
，
也把服务的响应时间作为考虑对象  
2 ，  
流可以用图 所示的二叉树表示 相应的时序约束可表  
，
但它仅包含一条全局约束 而时序约束往往是覆盖全  
t( v19)  
12，t( v15)  
4，t ( v1)  
1，t ( v14)  
≤
示为  
3．  
≤
≤
≤
，
局及部分的多个约束 因此一些研究关注于时序约束  
．
［21］  
［22，23］  
、
这些研究除了关注时间本体  
时序约束描述  
等
3
TCD  
模型  
，
基础理 论 外 更 多 的 是 关 注 时 序 约 束 的 兼 容 性 验  
［19，20，23 ～ 26］  
TCD  
F
的思想是将施加于 的各个子工作流上的时  
， ．  
而很少考虑时序约束的服务组合问题 本  
证
，
序约束分解为针对各个活动的时序约束 再从各个活  
QSC  
，
问题 采用  
TCD  
方法把  
文的目标综合时序约束与  
，
动中除去不满足时序约束的候选服务 从而将  
TC QSC  
－
TC QSC  
－
QSC  
．
问题转化为一般的  
问题  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号