QoS-Aware移动服务选择算法

文摘

移动服务选择的问题,本文给出了一个上下文感知服务选择算法基于遗传算法。在该算法中,一树编码方法、适应度函数和fitness-better策略提出了。树编码模式选择遗传算法支持各种类型的服务组合,例如,序列组成,赞同组合、概率组成、和循环组成。根据编码方法、适应度函数是专门设计的。fitness-better策略使种群进化的方向,避免了退化的人口健康。一些实验分析表明,所提供的服务选择算法可以获得更好的服务组合。

1。介绍

目前,研究服务选择是受欢迎的1,2]。受欢迎的服务和服务功能的同质性导致相同的非功能属性。QoS将对服务组合的选择越来越重要(3]。为用户提供适当的服务,有必要选择基于QoS的服务(4- - - - - -6]。

快速发展的移动计算,计算能力可以用作移动服务(7,8]。组合服务根据用户上下文信息和服务的上下文是非常重要的。用户的上下文信息包括用户的偏好和当前位置。服务的上下文包括地理位置和QoS。

移动服务组合是一个服务发展的动力9,10]。组合服务特定功能,可以分为几个组件(组件服务)。组件功能可以分别通过几个具体的候选服务。同样不可避免的是,服务提供者提供服务与功能和不同的上下文。这些服务可以把成千上万的组合计划和相同的功能和不同的上下文。因此,我们需要根据用户的需求选择大规模服务。基于上下文的服务选择中扮演一个重要的角色在该地区的服务组合。

当前服务的选择通常是基于QoS的服务,忽略了地理位置的服务和用户的位置。上下文信息的用户、服务和个性化的要求是不考虑。

当用户到达某个地方,选择一些合适的服务组合根据用户的喜好,上下文信息的用户的当前位置,上下文信息服务的位置和QoS。

因此,有必要提出移动服务选择算法根据用户的环境和服务。它引入了上下文信息移动服务选择系统。它有更高的精度比传统的选择。

本文提出一种改进遗传算法(IGA)对移动服务组合选择基于上下文信息。首先,描述了一种改进的染色体编码方法。其次,提出了一种适应度函数的基础上改进的编码方法。最后,提供了fitness-better方法加快遗传算法的收敛性。

部分2提供了移动服务选择计算的研究。IGA显示在部分3。部分4是关于模拟。部分5结论指出,下一步。

2。基于上下文的服务选择

QoS是上下文数据的一部分。基于QoS的服务选择一个有吸引力的搜索区域(11- - - - - -13]。会议全球约束(用户的喜好),找到最佳组合服务是服务组合算法选择和组合优化的范围。算法服务组合选择是一个np难问题(14]。

因此,近似算法可以更好地选择算法服务组合。遗传算法是一种基于概率的近似算法随机搜索。它可以克服的局限性(穷举算法和优化组合15]。

文献[16)使用GA和获得次优的解决方案。文献[17)采用GA和建造服务组合模型利用一维染色体编码方式。文献[18)使用GA优化基于QoS的服务组合。在[19),Girardello Michahelles选择最常见的应用程序在分析这些移动应用程序根据用户的当前位置上下文。但本文只考虑位置上下文和应用程序使用,忽略用户的个人喜好。文献[20.)考虑移动用户和企业之间的距离。它认为用户附近的优先服务。用户和服务之间的距离可能会对用户有很大影响。

基于上下文信息服务组合有很多类型,如串行类型、平行型、圆概率类型和类型。因此,需要设计一个合适的编码的遗传算法来满足各种类型的服务组合。随机计算遗传算法确保GA搜索所有解决方案空间的能力,但它也带来了收敛速度慢的问题。一些方法应采取加快遗传算法的收敛速度。

3所示。改进遗传算法

我们提供了一种改进遗传算法(IGA)对移动服务组合选择。它包括一个树遍历编码、适应度函数和fitness-better策略。

3.1。树编码方法

本节显示了一个树编码方法。树服务组合模板的编码。

3.1.1。树模板的服务组合

一些基本服务组合类型,如概率组成、系列组成,并行成分,和循环成分包含在移动服务组合过程。

一种特殊的树形结构可以将服务组合过程。它被称为树组合模板。整个服务组合过程,组件之间的逻辑关系,可以与根节点,提出nonleaf节点和叶节点在这棵树组合模板。图1描述了一个服务组合。

图1的逻辑计划是一个服务组合的例子。它是建立根据服务组件的逻辑功能。有四个服务组合类型(序列组成,赞同组合、概率组成和循环结构)在图1。

在图1,C1 ~ C7是七个服务组件。C1 ~ C4循环成分和是重复的数字。C2 - C3合作组成。C5 ~ C6概率组成。p1和p2概率值和它们的总和是1。

图2是图的树组合模板吗1。

在图2,圆图标nonleaf节点;组合类型和结构参数保存在那里。矩形图标是叶节点;服务组件和逻辑函数定义。节点CC、LC、PC和SC,分别合作组成、循环组合、组合、概率和系列组成。他们代表组成类型的子树。节点C1 ~ C7这些图是一样的1。他们是服务组件的服务组合。每个服务组件有许多候选人移动服务。例如,c11、c12候选人C1的移动服务,和特定的上下文值(QoS价值观和地理位置)保存在c11、c12。

3.1.2。树遍历编码方法

遗传算法的编码设计直接影响能力和遗传算法的效率。一个简单的遗传算法编码虽然已经展示了其不足用于解决移动服务的选择。一些文献提出了自己的改进方法。

以下是树的染色体编码过程遍历使用编码方法。

第一步是初始化一个指针指向第一个基因位点的染色体在左边。

第二个是遍历树组合模板使用预订基于从左到右的顺序遍历。

第三个是,当遍历到nonleaf节点,组成类型值和结构参数将用于计算。

第四个是,当遍历到一个叶子节点,叶子节点所代表的服务组件将放入当前指针指向的基因位点。那么指针将转移到正确的基因位点。

最后一个是重复以上步骤直到完成模板遍历树。

通过以上步骤,从树上可以获得染色体组合模板。以下是图的染色体2:(C1, C2 + C3, C4)^r、C5和C7(C1, C2 + C3, C4)^rC6, C7

C2 + C3同时运行C2和C3。指数是C1 ~ C4循环号码。每个基因表示服务组合。

两条染色体构建后,一些人(个人服务组合实例)可以生成的。许多候选服务为每个组件有很大的服务组合实例(GA)个体实例。

一些人选择形成遗传算法的初始种群。用户的个人喜好将全球服务组合的约束。通过一些遗传计算,未来一代又一代的人口了,直到获得一个服务组合解决方案。

3.2。健身计算

在遗传算法中,有大量的单个实例。每个人都是一个服务组合的实例。个人的健身价值将影响被选中的概率。适应度函数是遗传算法的核心技术。用户的个人喜好是全球QoS约束在选择个人。全球QoS约束适应度函数的部分。下面是关于如何建立适应度函数。

3.2.1之上。地理位置数据处理

首先,根据用户提供的地理距离的限制,一些不一致的候选服务将会取消。如果用户有特殊地理路径要求,一些不一致的候选服务也将离开。但算法来计算位置数据不属于。

3.2.2。适应度函数

选择规则和用户的个人偏好时需要考虑建立一个适应度函数。这里,适应度函数的设计规则,个人更大的健身价值和个体的选择概率更大。

公式(1)是一个适应度函数,它有两个部分除以一个负号。前部是一个目标函数。它集成了所有QoS属性。剩下的就是一个点球技术约束优化问题。它选择比例个人违反约束到下一代种群。它是关于用户的个人喜好。

在公式(1),N是QoS属性的数量。米是QoS的数量限制。是一个系数和一个经验值。和相对QoS属性的权重值,相对QoS属性的重要性。是一个整合了所有选择定则的一部分QoS属性值。是关于用户的个人喜好或全球约束。公式中的负号(1)是罚函数方法,可以为这些人提供生存概率,侵犯了用户的个人喜好。

有很多种类的QoS测量大小是不同的。如果这些不同的QoS属性数学适应度函数,他们的差异需要消除保证公平影响服务的选择。此外,QoS属性是其他两种类型:一是积极(QoS值越大,影响越好,如声誉),另一个是负面(QoS值越少,越好影响,如价格)。因为有积极QoS和负面同时之一数学适应度函数,它需要使用一些方法来合成两种截然相反的类型。因为以上各种情况下,公式是建

在公式(2),,,分别是,最小值,平均值,最大的jth QoS属性在所有的服务组合实例。该部门在公式(2)是为了平衡不同大小的QoS属性。

当kth QoS值符合相对QoS极限,的价值是0。或者,公式(3)用于。

在公式(3),和最小和最大的吗k分别th限制条件。是kth QoS的价值。

当使用树编码方法,其计算过程如下个人健身价值。

第一步是初始化一个指针指向第一个基因位点从左到右的染色体。

第二个是根据前序遍历树组合模板遍历顺序。

第三是代表组件由一个原子服务所取代,目前在基因位点,当指针指向一个叶节点遍历。那么指针将被转移到下一个基因位点。

第四个是,当遍历到nonleaf节点,如果所有的孩子叶节点替换为特定的原子服务,包括自己的QoS属性向量,如果孩子nonleaf节点存储集成QoS属性的值向量的子节点,当前nonleaf节点可以使用QoS属性向量中包含子节点以及其组合逻辑存储信息计算集成QoS属性的价值。最后,计算集成QoS属性的值将被存储在nonleaf节点。

最后是重复以上步骤,直到所有的节点树模板遍历。

通过上述步骤,全球所有QoS属性的值的个体获得并存储在树的根节点组合模板。在此基础上,所有个体的适应度值可以使用适应度函数计算。

3.3。Fitness-Better策略

遗传算法是一种随机搜索算法。随机计算使GA搜索所有领域的解决方案。但随机搜索的范围大规模解决方案导致缓慢的收敛情况。遗传算法很难获得一个最优的解决方案。因此,应该使用一些方法来减少随机运行遗传算法。这是一个好方法直接使用一些进化意味着GA。

在遗传算法中,交叉和变异两个进化操作产生新的个体。可能的结果(s)健身这两个操作(是)比他们的父母染色体(s)。为了避免上面的退化情况,fitness-better方法,它能提供直接的每个操作。下面是fitness-better方式。与此同时,为了避免局部最优,个人最高的健身能生存的可能性。每一个进化计算期间,最好的健身将获得。

(每一代突变计算期间),计算过程如下。第一个突变操作之前,mother-chromosome的健身价值保存最好的健身价值的突变(其缩写BestFM)。对于每一个每一个基因位点的突变染色体,健身mother-chromosome及其后代的染色体比较和更好的健身(BetterFM)。然后,BetterFM BestFM而古老。之间的更好的健身BetterFM老BestFM保存新BestFM。mother-chromosome中的所有基因位点突变操作后,最新BestFM是最好的健身价值在这些变异操作。第二个变异操作将使用BestFM作为其初始BestFM,等等。毕竟突变的计算,BestFM将成为最好的健身这种突变计算期间。相对染色体将进入下一代。

()交叉计算期间的每一代,计算过程如下。第一个交叉操作之前,两个母亲染色体保存两个最好的健身价值交叉(他们的缩写BestFC-1和BestFC-2)。

每个交叉操作后,父染色体及其后代染色体的健身价值进行比较。最好的两个健身值将BetterFC-1 BetterFC-2。顶部两个健身值在BetterFC-1、BetterFC-2 BestFC-1, BestFC-2将新的BestFC-1和BestFC-2来取代旧的。毕竟交叉计算在此交叉时期,BestFC-1和BestFC-2将成为最好的两个健身值在此交叉计算周期。相对染色体将进入下一代。

通过以上方式,个人有更好的健康可以得到。新一代会比旧的更好的健康。因此,人口健康将得到改善。在某种程度上,可以加快收敛速度。

4所示。实验分析

本文提出了一种改进的遗传算法。它包括树编码方法、适应度函数和fitness-better方法。通过以上改进,更快的收敛速度和更好的搜索能力将成为可能。下面是一些实验和分析表明IGA具有更好的效率和能力。

为移动服务组合选择,一些实验之间的简单遗传算法(SGA)和IGA为了证明IGA的效果。

IGA使用树编码、适应度函数如公式(1),fitness-better策略。

,SGA采用一维编码方式图3和适应度函数如公式(4)。

在图3C1 ~ C7和c11、c12…这些图是一样的2。一维编码意味着它并不可以代表许多服务组合场景,如概率调用,并行调用顺序激活。

公式(4)使用绝对排斥技术拒绝QoS违反约束条件的个体声称由用户。

相同参数的算法,包括相同的人口规模,单点突变和变异概率0.1和0.7单点交叉和交叉概率。

的编码方式、适应度函数和发展政策相比,气体之间的不同点。

这两个算法相比面临相同的组合数据的移动服务选择,包括相同数量的组件和相同的QoS属性为每个候选服务。所有QoS值和全局限制一些QoS属性随机。

相同的数据包括10 - 30候选服务为每个服务组件和6为每个服务QoS数据。简化表示服务包括身份证号码和一些QoS数据。

4.1。实验分析收敛

GA收敛速度与代数量,得到一个最终的解决方案。停止一代数越少,收敛速度越快。

为了证实是否IGA减少停止代数量,SGA和IGA运行100次,分别。有些结果数据显示在图4。

从图4500代之前,SGA并不收敛,对450代之前IGA是稳定的。原因是SGA的随机搜索方法。相比之下,IGA提高收敛速度通过以上fitness-better方式降低遗传算法的随机性。IGA得到移动服务选择的最终结果在更短的时间内,比SGA更快收敛速度。此外,IGA可以获得比SGA更高的适应性。原因是患者更好的健身可以生存在交叉和变异操作。

IGA的贡献之一是,它可以快速和稳定地选择最优组合从大量的候选计划计划。

4.2。实验分析对搜索

搜索功能是可以找到更好的解决方案。它可以测量通过个人最后选择的健身价值。上面的健身公式的基础上,健康值比例为遗传算法的搜索能力。

IGA采用了树的编码方式和适应度函数特殊以及fitness-better手段提高其搜索能力。为了测试它们,SGA和IGA运行100次。一些最后的个人得救了的最大值。表1是实验数据的一部分。

在表1,比SGA IGA获得较大的最后的健身价值。也就是说,比SGA IGA可能会得到更好的解决方案。结果表明,IGA比SGA更好的搜索能力。使用fitness-better方法,个人有更好的健身将有更大的机会进入下一代。较低的个人健身有较少机会参与下一代进化。相比之下,个体具有较高的健身价值确定SGA中求生存。SGA很难得到更好和更好的健康。

5。结论

这是不可避免的,大量的候选服务具有相同的功能和不同的非功能属性(主要指QoS属性)存在。如何快速从巨大的候选人的选择一个移动服务组合来满足用户的需求变得日益紧迫。

本文提出一种基于遗传算法的移动服务选择算法。遗传算法的改进包括树编码方法和一个健身计算方法基于新的编码方法。为了弥补缺乏遗传算法的进化方向,fitness-better方式使用在交叉和变异操作。在结果中,个人可以选择更好的健身和可以提高收敛速度。

通过上述实验,IGA被证实的能力和效率。这是一个很好的解决方案移动服务组合选择。

乔治亚州的一个不足是它的局部收敛能力。有必要结合遗传算法和局部搜索算法,可以弥补遗传算法的局部搜索能力21]。因此,未来的研究将遗传算法和局部优化算法的混合算法。

相互竞争的利益

作者宣称没有利益冲突有关的出版。

确认

这项工作是由中国国家自然科学基金(没有。61132001);国家973项目(没有。2013 cb329102);中国国家高新技术研发项目和计划(863计划)资助。2013 aa102301。

引用

1. 美国Soltani、p·马丁和k . Elgazzar”QuARAM推荐:案例推理IaaS服务选择,”《云计算和自主计算国际会议(ICCAC 14),页220 - 226,伦敦,英国,2014年9月。视图:出版商的网站|谷歌学术搜索
2. 曹j . x g . Wang, y,“动态云服务选择在多重云计算,使用一种自适应学习机制”系统和软件杂志》上卷,100年,第210 - 195页,2015年。视图:出版商的网站|谷歌学术搜索
3. m . Rajeswari g . Sambasivam n,巴拉Saleem岜沙,m . t . Vengattaraman和p . Dhavachelvan”评价和分析各种web服务组合方法基于QoS的因素,”沙特国王大学计算机与信息科学杂志》上,26卷,不。1,第152 - 143页,2014。视图:出版商的网站|谷歌学术搜索
4. l .吴杨绍明。关铭刘,S.-J。刘:“多策略QoS-aware服务选择与排序模型,”侗学报/在通讯》杂志上,33卷,不。1,第147 - 141页,2012。视图:出版商的网站|谷歌学术搜索
5. h . y .郑j .杨w·l·赵et al .,“QoS分析基于概率QoS的web服务组合”学报》第九届国际会议上面向服务的计算帕福斯,页47 - 61年,塞浦路斯,2011年12月。视图:谷歌学术搜索
6. j·l . Chen Yang, l·张,“基于时间的QoS web服务建模和预测,”面向服务的计算:9日国际会议,2011年ICSOC帕福斯,塞浦路斯,2011年12月5 - 8日诉讼卷,7084在计算机科学的课堂讲稿施普林格,页532 - 540年,柏林,德国,2011年。视图:出版商的网站|谷歌学术搜索
7. b . s . d .雪b . d . Wu Cheng x俏,和j·陈,“移动终端用户业务流程个性化,”中国通信,12卷,不。12日,1 - 12,2015页。视图:出版商的网站|谷歌学术搜索
8. 你和y . f .黄”向高效、安全的访问控制系统为移动云计算,“中国通信,12卷,不。12日,43-52,2015页。视图:出版商的网站|谷歌学术搜索
9. g·a·g·Llinas和r . Nagi”网络和算法选择的配套服务,”IEEE服务计算,8卷,不。1,第91 - 79页,2015。视图:出版商的网站|谷歌学术搜索
10. 吴x k, y, b . Cheng j.y. Wu和j·陈,“复合服务提供方法基于小说在移动ad hoc网络节点模型,”中国通信,11卷,不。4、130 - 142年,2014页。视图:出版商的网站|谷歌学术搜索
11. z Rehman, o·k·侯赛因,f·k·侯赛因,“平行云服务选择和排名基于QoS的历史,”国际期刊的并行编程,42卷,不。5,820 - 852年,2014页。视图:出版商的网站|谷歌学术搜索
12. 问:吴、李z y阴,h .曾“在移动云计算自适应服务选择方法中国通信,9卷,不。12日,46-55,2012页。视图:谷歌学术搜索
13. 问:太阳,w . b . Wang和h .邹”服务选择方法基于availability-aware移动ad hoc网络,”中国通信,8卷,不。1,第94 - 87页,2011。视图:谷歌学术搜索
14. g . Canfora m·d·五r·埃斯波西托et al .,“QoS-aware服务组合、一个轻量级的方法”第二届国际会议在面向服务的计算(ICSOC ' 04),页36-47,纽约,纽约,美国,2004年。视图:谷歌学术搜索
15. m·斯和l . m . Patnaik”遗传算法:一项调查,”电脑,27卷,不。6,17-26,1994页。视图:出版商的网站|谷歌学术搜索
16. t . Yu, y,林和k . j .,“高效算法用于web服务选择与端到端QoS约束,“ACM在网上交易,1卷,不。1,1-26,2007页。视图:谷歌学术搜索
17. g . Canfora m . Dipenta, r·埃斯波西托”QoS-aware服务组合的方法基于遗传算法”《遗传与进化计算会议华盛顿特区,页1069 - 1075,美国2005年。视图:谷歌学术搜索
18. c·w·张,j .旷l . c, b . Cheng和z z张“遗传算法与动态阻止全球QoS-driven web服务标准重新规划选择,”信息,15卷,不。2、689 - 698年,2012页。视图:谷歌学术搜索
19. a . Girardello和f . Michahelles AppAware:哪些移动应用热”《人机交互与移动设备和服务(MobileHCI 10)ACM出版社,页2010 - 431年,纽约,纽约,美国,2010年。视图:谷歌学术搜索
20. W.-S。杨,H.-C。程,J.-B。Dia”,位置感知移动购物环境,推荐系统”专家系统与应用程序,34卷,不。1,第445 - 437页,2008。视图:出版商的网站|谷歌学术搜索
21. 美国x太阳和j .赵“decomposition-based方法与全球的QoS保证,服务组合”信息科学卷,199年,第153 - 138页,2012年。视图:出版商的网站|谷歌学术搜索

版权

版权©2016 Chengwen Zhang et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。