一种多云环境下的启发式服务组合方法

卢俊文，崔建峰，郑鹭斌

(厦门理工学院计算机与信息工程学院,福建厦门361024)

一种多云环境下的启发式服务组合方法

卢俊文，崔建峰，郑鹭斌

(厦门理工学院计算机与信息工程学院,福建厦门361024)

提出了一种基于云中心信息的服务组合方法 （service composition based on data center information，SCDC）.SCDC通过贪婪查找方法直到找到所有需要的云服务.SCDC采用3个原则减少服务组合涉及云的数量及减少访问云服务的个数.与ALL Clouds、Smart Clouds、Base Clouds方法对比表明，SCDC在保持访问云的数量最小的同时，减少访问云服务的数量超过20%.

多云环境；服务组合；执行时间；访问服务数量

Web服务技术具有高度的互操作性、跨平台性和松散耦合等优点.然而,单个Web服务提供的功能较为单一,难以满足用户复杂多样的请求,只有通过对已有服务进行组合,才能满足不同用户的多个不同需求［1－2］.Web服务组合技术将多个Web服务进行组合,形成一个功能能满足单个用户的新的服务,以提供更多功能复杂的服务来满足不同用户的复杂需求,同时,也简化了软件的生产过程.Web组合技术也引起了学术界和产业界的广泛关注.云平台具有可扩展性、能规模化提供服务等特点.云计算与Web服务技术的结合,使Web服务于云平台都能更大地发挥各自的作用［3－4］.单个云所能提供的服务有限,通过组合多个云的Web服务,能进一步提高云的效果［2－3］,但多云环境下,服务组合更加复杂.当前,很多文献已经从多个方面对云环境下的服务组合相关技术进行了研究：文献 ［5］通过一个实际例子,描述了如何利用全局模型选择可行的云服务；文献 ［6］提出了可信云服务的定义,并从用户信任预期、安全威胁来源和技术针对的安全目标等角度对可信云服务研究技术的类型进行了划分,并在此基础上,系统地描述了数据存储外包、计算外包、虚拟机外包等典型云服务的安全可信；文献 ［7］以社会学中的人际关系信任模型为基础,提出了一种基于服务消费者的服务满意度评价、推荐者的服务推荐和第三方服务性能反馈的可信度量模型,并在 DLS (dynamic level scheduling)算法基础之上,提出可信动态级调度算法CTDLS(trust-aware dynamic level scheduling algorithm in cloud environment),从而在计算调度级别时考虑服务资源的可信程度；文献［8］探讨了利用Agent实现服务组合的方法,通过Agent的自我重新组织,实现服务组合功能；文献［9］提出了一种满足服务质量约束的网络服务组合机制DSCGOM,包括满足服务质量的组合路径选择机制设计和服务重定向机制设计；文献 ［10］综合考虑集成静态服务组合和动态服务组合的优点,提出了一种在虚拟层面上基于服务簇进行服务组合的思想,并给出了一种基于服务簇的服务组合方法,并进行了验证.

多云环境下的服务组合是NP问题［1］,其服务组合主要涉及到两方面：选择哪些服务及选择云中的相关服务［1－4］.针对多个云环境,一些研究人员也提出了相关的服务组合算法,如 All Clouds［1－2,4］、Base Clouds［1－2,4］、Smart Clouds［1－2,4］、COM2 Clouds［1］等.多云环境下,Web服务组合的挑战主要来自两个方面：1)多个云环境下,如果服务组合涉及的云的数量过多,可能导致Web服务组合的执行时间过长,从而不能完成用户的目标；2)在进行服务组合的时候,需要检测的云服务数量太多,延长了服务组合的组合时间［2－4］.很多时候这两个调度目标具有冲突性,本文采用折中的方式,提出了一种基于云中心信息的服务组合方法,在以上两个方面均得到比较好的结果.

1 系统调度模型

在云环境下,大多数服务组合的研究是针对一个云的情况.单个云制约了服务组合的功能,本文试图研究在多个云环境下的服务组合方法.图1是本文要研究的系统调度模型.

图1 多云环境下的服务组合Fig.1 Service composition under multi鄄cloud

多云环境 (multiple cloud environment, MCE)由多个云组成,每个云中包括多个服务集,每个服务集中的元素有多个服务单元.如图1,具有6个云中心(C1～C6),C1中就有4个服务集.假设S1包含3个服务单元(S1～S3),则len(S1)＝3.每个用户通过用户接口提交组合服务要求,而每个云通过向MCE中心(multi-cloud management center)报告服务信息.Cloud manager和Service manager共同工作完成服务组合功能.Cloud manager主要完成对云的管理工作,Service manager主要完成对服务的管理工作.云管理,服务管理,多云管理中心,三者通过互相交互,完成信息各自管理工作,并互相反馈信息.

2 调度算法

假设多云环境如下：MC＝｛C1,C2,…,CMCN｝,每个多云环境包含MCN个云；SF＝｛S1,S2,…, SSN｝,总共有SN个服务；SFN＝｛SF1,SF2,…,SFSN｝为每个服务的长度,即每个服务包含子服务的数量；R＝｛SFR1,SFR2,…,SFRSFRN｝,用户组合服务要求,假设用户服务要求的的服务按照子服务长度按从大到小降序排练.

多云环境下的服务组合,其目标有2个：1)最小化访问云的数量；2)最小化检查的服务数量,本文采用贪婪算法完成调度目标［1－2,4］.贪婪算法 (又称贪心算法)是指在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,它所做出的是在某种意义上的局部最优解.具体到本文的调度环境,算法总试图使当前某个云中所有服务被分配,或者某个服务组合所需要的所有服务全部获得.为实现这两个目标,笔者提出一种启发式算法SCDC(service composition based on data-center information)如下：

算法：SCDC()

算法SCDC主要包含3个原则：1)如果一个云中所有服务都包含在一个服务组合要求之内,那么选择这个云中所有服务,如果有多个云满足这个要求,那么选择包含子服务数量最多的云；2)如果一个服务组合要求中所有服务都在一个云中,那么选择这个云,如果有多个云满足这个要求,那么选择包含子服务总的数量最小的云；3)如果没有满足条件1)和2),那么选择包含服务组合要求最多的云,如果有多个云满足这个要求,那么选择包含总的子服务最小的云.三条原则用以确保系统完成两大目标：最小化拟合所涉及的云的数量ACC(average number of combined clouds)及最小化组合算法所访问的服务数量AEC(average number of examined services).

SCDC算法描述如下：rid是服务组合要求的唯一标志,SFRrid表示对应的服务要求.行4计算在云中而不在SFRrid中包含子服务的数量；行5计算在SFRrid而不在云中Ccid总的子服务数量；行6计算SFRrid与Ccid相同子服务数量；行8czero(lenl)判断数组lenl中是否有值为0的元素；行9～19是执行第一条原则,选择符合条件且具有最大子服务数量的云,并分配云中所有服务；行22～32是执行第二条原则,选择包含所有服务组合要求中服务的云,分配服务并更新服务组合需求；行36～38是执行第三条原则,如果没有云能满足第一、二条原则,选择包含SFRrid中服务最多的云,若有多个云满足这个条件,选择总的子服务数量最小的云.

3 模拟实验

模拟实验环境如下：每个服务文件包含子服务的数量为 ［1,10］之间随机整数,随机产生5个服务组合要求,每个服务组合要求最多包含5个子服务组合；每次随机产生5个MCE,每个MCE包含8个云,这些云包含的服务也有随机数产生.分析结果为5个MCE中的平均值,都是采用Matlab 2014对算法进行模拟.

本文将SCDC算法与ALL Clouds、Base Clouds、Smart Clouds进行对比.图2是不同服务组合要求在5个MCE中的AEC,x轴表示各个服务组合需求,y轴表示AEC.总体上,除R1外,SCDC具有最小的ACC.图3是4种方法对不同的服务组合需求的AEC,x轴是4种方法,y轴是AEC.其中, SCDC与其他方法对比,AEC至少减少了20%.

图4是不同服务组合要求在5个MCE中的ACC,x轴是5个服务组合需求,y轴是ACC.除R2外,SCDC基本具有最小值.图5是4种方法的ACC,x轴是4种服务组合方法,y轴是5个MCE中的ACC.其中,SCDC具有最小值,All Clouds具有最小值,Base Clouds与Smart Clouds的ACEC值没有太大差别.

图2 每个MCE环境中AECFig.2 Average AEC in MCE

图3 各个方法的AECFig.3 AEC of different methods

图4 每个MCE环境中ACCFig.4 Average ACC in MCE

图5 各个方法的ACCFig.5 ACC of different methods

4 结语

本文研究了服务存在于多个云环境下的服务组合问题,提出一种服务组合算法.SCDC采用贪婪算法,试图减少访问云和检测云服务的数量,在此基础之上,确立了3条调度原则.并与Smart Clouds,All Clouds及Base Clouds对比,模拟实验表明,本文提出的算法不但能减少服务组合所需的云的数量,而且能减少服务组合过程中所查找的服务数量.但是,当前算法并未考虑服务的价格,在考虑价格的情况下,如何既满足组合服务的性能要求,又能满足组合服务的预算要求,是笔者下一步需要考虑的问题.

［1］HEBA K，ABEER A，CARLENE C，et al.A combinatorial optimization algorithm for multiple cloud service composition［J］.Computers＆Electrical Engineering，2015，42：107-113.

［2］YU Q，CHEN L，LI B.Ant colony optimization applied to web service compositions in cloud computing［J］.Computers＆Electrical Engineering，2015，41：18-27.

［3］ZOU G B，GAN Y L，ZHENG J X，et al.Service composition and user modeling for personalized recommendation in cloud computing［C］//International Conference on Computing，Communication and Networking Technologies.Hefei：CCV，2014：11-13.

［4］ZOU G B，CHEN Y X，XIANG Y，et al.AI planning and combinatorial optimization for Web service composition in cloud computing［C］//Proceedings of Annual International Conference on Cloud Computing and Virtualization. Singapore：CCV，2010：28-35.

［5］TANG C L，LIU J Q.Selecting a trusted cloud service provider for your SaaS program［J］.Computers＆Security，2015，50：60-73.

［6］丁滟，王怀民，史佩昌，等.可信云服务 ［J］.计算机学报，2015，38（1）：178-190.

［7］曹洁，曾国荪，姜火文，等.云环境下服务信任感知的可信动态级调度方法 ［J］.通信学报，2014，35（11）：39-48.

［8］GUTIERREZ-GARCIA J O，SIM K M.Self-organizing agents for service composition in cloud computing［C］//2nd IEEE International Conference on Cloud Computing Technology and Science.Indianapolis：IEEE，2010：59-66.

［9］罗娟，周峰，李仁发.基于分布式OSGi的动态服务组合算法 ［J］.计算机研究与发展，2014，51（2）：420-428.

［10］吴洪越，杜玉越.一种基于逻辑petri网的Web服务簇组合方法 ［J］.计算机学报，2015，38（1）：204-217.

A Heuristic Service Composition under Multi－Cloud Environment

LU Jun-wen，CUI Jian-feng，ZHENG Lu-bin
（School of Computer＆Information Engineering，Xiamen University of Technology，Xiamen 361024，China）

In the paper，we propose SCDC，a service composition based on data center information under MCE.SCDC finds the service candidate by greedy search and follows three principles to reduce the number of evaluated Clouds and the number of related Cloud services.Comparing to All Clouds，Smart Clouds，Base Clouds，SCDC has a minimum in the number of evaluated Clouds，at the same time，it reduces the number of evaluated Cloud services more than 20%to other methods.

multiple cloud environment；service composition；execution time；number of examined services

TP31

A

1673－4432（2015）05－0075－05

（责任编辑 雨 松）

2015－09－07

2015－09－25

国家网络化支撑软件国际科技合作基地开放课题 (NSS1403)；福建省自然科学基金项目 (2013J05103)；厦门理工学院对外科技合作专项项目 (201401500)

卢俊文 (1981－),男,实验师,硕士,研究方向为嵌入式系统、网格计算.E-mail：jwlu＠xmut. edu.cn