用户QoS需求导向的服务演化选择策略

杨真谛 秦江龙,2 李 彤,2* 韩 煦 藏传宇 陈长赓

1(云南大学软件学院 云南 昆明 650091) 2(云南省软件工程重点实验室 云南 昆明 650091)

用户QoS需求导向的服务演化选择策略

杨真谛1秦江龙1,2李 彤1,2*韩 煦1藏传宇1陈长赓1

1(云南大学软件学院 云南 昆明 650091)2(云南省软件工程重点实验室 云南 昆明 650091)

服务型软件以其特有的优点被广泛应用，而面向QoS服务选择问题的解决能更有效地推动服务的普及。组合服务的演化性要求在服务发生演化时，从具有相同功能的候选服务中选择满足用户QoS需求的候选服务。为了在满足用户QoS需求的情况下选择最优的服务，基于遗传算法，提出一种用户QoS需求导向的服务演化选择策略。通过淘汰不满足用户QoS需求的候选服务，快速排除不符合需求的服务，并最终选择符合用户QoS需求的服务组合。实验结果表明，用户QoS需求导向的服务演化选择策略能够较优和较快地解决服务组合选择问题，并保证用户QoS需求，为服务选择提供一种新的方法和思路。

QoS 服务组合 用户QoS需求 遗传算法 服务选择

0 引 言

随着互联网的发展，以及软件即服务模式的流行，互联网服务在教育、商务、企业等不同的领域发挥着不可替代的作用，服务的概念深入人心。一方面，由于服务可能是以不同的方式创建、不同程序语言实现、由不同的供应商提供的，服务的请求需要根据特定的应用背景和需求进行合理的服务组合；另一方面，由于服务组件或基本服务不可能很复杂[1]，不能满足现代企业多样性的应用需求，因此组合服务应运而生[2]。

构造性和演化性是软件的两个基本特性[3]。服务软件也是如此，组合服务也具有演化性。组合服务演化时，应该从候选服务集中选择出满足用户功能性和非功能性需求的候选服务来对组合服务进行演化。服务质量QoS是描述服务非功能性属性的主要评价标准，同时基于QoS的服务选择在服务组合中扮演着相当重要的角色[4-5]。在互联网中，提供相同功能的服务越来越多，但这些服务的QoS值并不相同。与此同时，用户对服务进行演化时的服务QoS要求更为严格。因此，在服务演化时，根据服务的QoS属性来选择满足用户QoS需求的服务策略显得尤为重要。

本文通过服务的QoS模型，将服务演化时面向QoS服务选择的问题转化为求解用户QoS需求导向，多元非线性目标函数组合优化问题，提出了用户QoS需求导向的遗传算法GALUR(Genetic Algorithm Led by User Requirements)。在服务演化时，以用户QoS需求为导向，引入用户QoS需求向量来计算个体适应度，利用用户QoS需求淘汰不满足用户需求的候选服务，从而快速地排除不符合要求的个体，并且能够较快地跳出局部最优解，使种群朝着满足用户的需求方向进化，最终选择出符合用户QoS需求的服务组合。

1 相关研究

基于QoS的服务选择是一个NP难问题[6]，而遗传算法可以有效地解决这类问题[7]。解决此问题的方案有很多，例如文献[8]中提出运用关系矩阵编码方式，克服了一维编码方式表示的局限性；文献[9]描述定义了组合服务并且提出利用遗传算法来解决服务组合问题；文献[10]中提出了一种变异策略，在种群变异阶段提出了自适应变异算子，保证了算法的收敛性；文献[11]中提出了一种数据预处理方法，先为每个抽象服务优选出若干候选服务以减少解空间规模；文献[12]中提出了变权QoS参数，即动态调整变权因子、交叉和变异因子来解决此问题；文献[13]中提出一种遗传算法和果蝇优化算法相结合的方法来解决云平台上的服务组合问题，在选择个体时，提出了一种新的方法，考虑个体间的多样性来防止过早地收敛和跳出局部最优解，利用果蝇优化算法防止在进化过程中丢失具有潜力的个体；文献[14]中提出一种遗传算法和启发式算法结合的方法来解决服务组合问题，引入的启发式算法能够有效地跳出局部最优解。但在组合服务演化时，这些方案均忽视了用户QoS需求在服务选择中的意义，不能够直接在候选服务层面体现用户QoS需求，不能够完全地按照用户QoS需求来选择服务，完成服务演化。

因此，本文将提出一种新的选择服务思路，充分重视用户QoS需求在服务演化选择时的作用，在候选服务的适应度和选择上体现用户的QoS需求，提出了一种在服务演化时，以用户QoS需求为导向的服务选择策略。

2 服务QoS模型

2.1 服务QoS模型

文献[9]对服务QoS的描述如下：

设一个组合服务S需要完成n个功能F，如式(1)所示。若每个功能由一个子服务完成，即S由n个子服务ss组合完成，其中，每个子服务ss具有m个QoS属性。

S= (F1,F2,…,Fn)T=(ss1,ss2,…,ssn)T=

(1)

其中：qij表示第i个子服务的第j个QoS属性值。

本文将涉及到5个QoS属性，故m取值为5。

2.2 QoS属性

本文借鉴文献[15]中的QoS模型，从执行价格、执行期间、声望、成功率和可用性五个方面对服务的QoS属性进行评价，五个QoS属性定义如下：

执行价格：服务每次执行时需要的成本，成本记为qpr；

执行期间：表示请求服务至收到服务结果的时间段，由服务处理请求时间Tprocess和请求与结果传输时间Ttrans组成，执行期间记为qdu，则qdu=Tprocess+Ttrans；

2.3 QoS属性组合

表1 服务组合QoS属性组合函数表

2.4 QoS属性归一化

通过表1计算得出的QoS属性值具有不同的量纲和取值范围，不能有效地统一评价服务，因此，需要对不同的QoS属性进行归一化处理，将取值范围不同的QoS属性值转化成无量纲并且范围都在[0,1]之间的值。有些QoS属性取值越小，表示服务性能越高，属于成本型属性，例如执行价格和执行期间；有些QoS属性取值越大，表示服务评价越高，属于效益型属性，例如声望、成功率和可用性。因此，将两种属性分为两个公式对其归一化，成本型属性用式(2)归一化，效益型属性用式(3)归一化。

(2)

(3)

2.5 QoS属性权重

2.6 用户QoS需求

不同用户对服务有不同的非功能性需求，即QoS需求。为了使组合服务演化后得到的结果严格地符合用户QoS需求，演化向着用户QoS需求的方向进行。定义用户需求向量R=(r1,r2,…,rm)，其中rj∈[0,1]，rj根据用户提出的需求，进行归一化处理得出。

3 用户QoS需求导向的服务选择策略

通过对组合服务候选服务的QoS属性评估与建立模型，将候选服务进行顺序、选择和并行组合。在服务演化时，以用户QoS需求为导向，引入用户QoS需求向量来计算个体适应度，利用用户QoS需求淘汰不满足用户需求的候选服务，从而快速地排除不符合要求的个体，并且能够较快地跳出局部最优解，使种群朝着满足用户的需求方向进化，最终选择出符合用户QoS需求的服务组合。

3.1 适应度函数设计

陈小华：小的个体户活起来还可以，只要对客户要求不大就永远踩不死。一些垂直的领域也有机会，比如绿植全国第一、沙发保养全国第一，然后和一些平台进行合作，但如果说在平台层面，已经基本没有创业机会了。

一般适应度函数只能够单一体现个体在环境中的适应度值，不能够体现用户QoS需求与个体的关系。遗传算法是根据生物进化理论和遗传变异理论提出的一种算法，其主要思想是通过不断地进化，淘汰适应度低的个体，使适应度高的个体存活。根据遗传算法的思想，引入用户QoS需求向量设计适应度函数。

定义式(4)为适应度函数。在计算候选服务的QoS属性值之前，定义式(5)，利用示性函数表示候选服务的QoS属性是否满足用户的需求，只有当候选服务的每一个QoS属性满足用户QoS需求时，示性函数为1，其他情况则为0。对满足需求的候选服务计算其加权后的QoS属性值，再将每个候选服务的QoS属性值按照顺序、选择和并行结构的相应计算公式计算，得到组合服务S的适应度函数值。这样就能够将用户QoS需求体现到每一个候选服务的适应度计算中，不符合用户QoS需求的个体则会表现出低适应度，在选择时被淘汰，满足需求的个体继续存活，使种群朝着满足用户QoS需求方向进化。

(4)

(5)

3.2 选择函数设计

一般的选择函数只是负责从群体中选择出具有最高适应度的个体，没有将用户QoS需求引入选择过程，不能够在选择中体现用户QoS需求。为改进这一问题，在选择函数中将用户需求与轮盘赌选择法相结合，采用用户QoS需求导向的轮盘赌选择法，即每个个体被选择概率由个体的适应度与当代所有满足用户QoS需求个体的适应度共同决定。定义式(6)为个体被选择概率函数。

(6)

由于引入了用户的QoS需求，因此在选择的时候，能够快速地将不满足用户QoS需求的个体淘汰，满足需求的个体继续存活到下一代，使种群朝着满足用户QoS需求方向进化。

3.3 编码方式

采用二进制编码方式，将能够完成相同功能F对应的具有不同QoS属性的子服务ss的唯一标识用二进制的方式进行编码。功能Fn的候选子服务集合记为Fn_CS={ss1,ss2,…,ssn}，其中，ss1的唯一标识为1，故可编码为0000 0001；ss2的唯一标识为2，故可编码为0000 0010；以此类推。因此，如果服务S需要完成两个功能，并且每个功能选择了标识为1的候选子服务进行组合，则S对应的二进制编码为：0000 0001, 0000 0001。

3.4 变异与交叉

变异和交叉能够增大种群的随机多样性，使种群能够向更多方向进化，从而得到不同适应度的解。变异方法选择随机位置变异，利用变异率与种群大小来决定变异个体的数量，确定变异个体后，随机选择基因位来进行变异。交叉方法选择两点交叉，交叉率与种群大小决定通过交叉取代种群个体的数量，然后随机选择两个位置进行交叉。

4 实验结果及分析

为了检验用户需求导向的服务演化选择策略的有效性，将该方法(GALUR)与传统的没有用户需求导向的遗传算法在不同结构组合的情况下分别进行实验，对解集的适应度和算法执行时间进行对比和分析。无论哪种仿真对比，都采用相同的软硬件环境，即中央处理器为酷睿 I7-2.4 GHz，内存8 GB，操作系统为Windows 10，开发语言为Java，IDE为IntelliJ IDEA2016.2的实验环境；所有实验的运行数据采用相同数据，并且多次测量取平均值。由于本文只涉及了5种QoS属性值，因此，为每个候选子服务随机生成在一定范围内取值的五个不同的属性值；为了消除不同权重对结果的影响，取每个QoS属性权重相同，即W=(0.2,0.2,0.2,0.2,0.2)；为了消除不同用户QoS需求对结果的影响，取每个用户QoS需求相同，即R=(0.5,0.5,0.5,0.5,0.5)；初始种群数为10；变异率和交叉率为0.5。

4.1 顺序结构组合下的适应度和执行时间对比

当子服务顺序结构组合时，可以从图1中看出，GALUR策略选择的解均优于传统策略选择出的解，并且随着进化代数的增长，两者选出解的适应度也在增长。但传统策略在10 000代的时候收敛于一个比较低的适应度，并且不能够跳出局部最优解，而采用GALUR策略得到适应度随着进化代数的增长呈递增趋势，能够得到一个较优的解。由图2可知，GALUR策略执行时间一直低于传统的选择策略。

图1 顺序结构适应度比较图

图2 顺序结构执行时间比较图

4.2 选择结构组合下的适应度和执行时间对比

当子服务选择结构组合时，可以从图3中看出，GALUR策略在第1 000代时选择出的解劣于传统策略的解，但是随着进化代数的增加，适应度的增长比传统策略更加迅速，在第4 000代到第6 000代的时候，GALUR收敛到一个适应度，过了第6 000代后，传统策略也开始收敛。而GALUR策略经过2 000代的进化，成功地跳出了之前收敛到的局部最优解并继续增长，9 000代后收敛到一个比传统策略更优的解，传统策略经过4 000代进化并没有跳出局部最优解。并且由图4可知，GALUR策略执行时间一直低于传统的选择策略。

图3 选择结构适应度比较图

图4 选择结构执行时间比较图

4.3 并行结构组合下的适应度和执行时间对比

当子服务并行结构组合时，可以从图5中得出GALUR策略在第1 000代的时候得到的解比传统策略得到的适应度低。但随后逐渐上升，从第2 000代开始，适应度相近，传统策略在4 000代开始平稳，经过3 000代进化以后跳出局部最优解，适应度有小幅度提升，然后开始收敛。而GALUR策略第6 000代进入平稳阶段，经过1 000代的进化，适应度开始提升，在第8 000代开始收敛。由此看来GALUR策略得到的解要优于传统策略得到的解，同时由图6可知，GALUR策略执行时间一直低于传统的选择策略。

图5 并行结构适应度比较图

图6 并行结构执行时间比较图

4.4 实验结果分析

通过三组实验，我们将从两个方面来分析这两种选择策略。

在适应度方面来看，GALUR策略在子服务顺序组合时得到的适应度一直高于传统的策略。在选择和并行组合时得到的适应度，虽然前期与传统策略得到的适应度相近，但最后GALUR策略能够收敛到优于传统策略的解。从图中可以看出，传统策略低于GALUR策略是因为传统策略不能迅速地跳出局部最优解，而GALUR策略在计算个体适应度时，引入了用户QoS需求作为导向，淘汰不满足需求的候选服务，能够快速地跳出局部最优解，得到更好的个体。

在执行时间方面来看，GALUR策略引入用户QoS需求作为导向，逐代快速地淘汰不满足需求的子服务，减少了每代需要考虑的候选服务数量，有效地降低算法执行的时间。

通过三组实验得到结论，GALUR选择策略在顺序、选择和并行结构组合中得到的适应度较高，同时花费的时间较短，因此，GALUR选择策略能够较优和较快地解决服务组合选择问题。

5 结 语

随着软件即服务模式的流行，服务型软件以其特有的优点被广泛应用，而面向QoS服务选择问题的有效解决能更有效推动服务的普及，使服务由一种技术转化为真正可以为人们使用的工具。人们提出许多方案来解决基于QoS的服务选择问题，其中基于遗传算法的解决方案是一种新颖的全局优化解决方案[6,17]。在组合服务演化时，这些策略几乎都忽视了用户QoS需求，只能选择出适应度最高的候选服务，并不能够得到满足用户QoS需求的候选服务。还有一些策略，虽然考虑了用户需求，但只是在最终组合以后考虑到用户的需求，并没有将用户需求渗入到候选服务层面，不能够完全体现用户的QoS需求。在深入研究服务组合和遗传算法的基础上，本文提出了一种用户QoS需求导向的服务演化选择策略，为服务选择策略提供了一种新的方法和思路。该算法采用二进制编码方式，并在个体适应度的计算和选择中，引入用户需求向量，在进化的过程中，能够快速地淘汰不满足需求的候选服务。在组合服务演化时，考虑了用户的非功能性需求，使服务选择能充分的反映用户QoS需求，提高了服务在演化时选择的质量和效率，为服务选择提供了一种新的方法和思路。

[1] 岳昆,王晓玲,周傲英.Web服务核心支撑技术:研究综述[J].软件学报,2004,15(3):428-442.

[2] Chen M,Wang Z.An Approach for Web Services Composition Based on QoS and Discrete Particle Swarm Optimization[C]//Eighth Acis International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/distributed Computing,2007:37-41.

[3] 杨芙清.软件工程技术发展思索[J].软件学报,2005,16(1):1-7.

[4] Menasce D A.QoS issues in Web services[J].Internet Computing IEEE,2002,6(6):72-75.

[5] Menasce D A.Composing Web services:a QoS view [J].IEEE Internet Computing,2004,8(6):88-90.

[6] Canfora G,Dipenta M,Esposito R,et al.A lightweight approach for QoS-aware service composition[C]//Proceedings of the 2nd International Conference on Service Oriented Computing.New York,2004:232-239.

[7] Rojas I,Gonzalez J,Pomares H,et al.Statistical analysis of the main parameters involved in the design of a genetic algorithm[J].IEEE Transactions on Systems Man & Cybernetics Part C,2002,32(1):31-37.

[8] 张成文,苏森,陈俊亮.基于遗传算法的QoS感知的Web服务选择[J].计算机学报,2006,29(7):1029-1037.

[9] 毛一梅,乐嘉锦.基于遗传算法的Web服务组合优化[J].计算机应用与软件,2008,25(11):199-201.

[10] 董元元,倪宏,邓浩江,等.QoS全局最优化的服务选择策略[J].小型微型计算机系统,2011,32(3):455-459.

[11] 叶恒舟,关云慧.基于局部选择和遗传算法的QoS感知的服务组合方法[J].小型微型计算机系统,2016,37(7):1389-1392.

[12] 吴青林,周天宏.基于服务质量的动态Web服务组合方法研究[J].计算机应用与软件,2016,33(5):20-23.

[13] Seghir F,Khababa A.A hybrid approach using genetic and fruit fly optimization algorithms for QoS-aware cloud service composition[J].Journal of Intelligent Manufacturing,2016:1-20.

[14] Shahrokh P,Safi-Esfahani F.QoS-based web service composition applying an improved genetic algorithm (IGA) method[J].International Journal of Enterprise Information Systems,2016,12(3):60-77.

[15] Zeng L,Benatallah B,Ngu A H H,et al.QoS-aware middleware for Web services composition[J].IEEE Transactions on Software Engineering,2004,30(5):311-327.

[16] Saaty T L.Analytic hierarchy process[M]//Encyclopedia of Biostatistics,2001:19-28.

[17] Zhang L J,Li B,Chao T,et al.On demand Web services-based business process composition[C]//IEEE International Conference on Systems,Man and Cybernetics.IEEE,2003,4:4057-4064.

ASTRATEGYFORSERVICESELECTIONINTHEEVOLUTIONOFSERVICESBASEDONQOSUSERREQUIREMENT

Yang Zhendi1Qin Jianglong1,2Li Tong1,2*Han Xü1Zang Chuanyu1Chen Changgeng1

1(CollegeofSoftware,YunnanUniversity,Kunming650091,Yunnan,China)2(KeyLaboratoryforSoftwareEngineeringofYunnanProvince,Kunming650091,Yunnan,China)

The widely use of service software with its unique advantages has promoted through the effective solution of QoS service selection problem. The evolution of composition services requires that select the candidate services which meet the user QoS requirement from the set of the same functional services during the evolution. In order to satisfy the user’s QoS requirement and select the optimal services, we propose a user QoS requirement oriented service evolution selection strategy based on genetic algorithm. By eliminating candidate services that do not meet user QoS requirements and quickly excluding services that do not meet requirements, a service portfolio that meets the user’s QoS needs is ultimately selected. The experimental results show that the user QoS demand oriented service evolution selection strategy can solve the problem of service composition selection better and faster, and guarantee the user’s QoS requirement. It provides a new method and thinking for service selection.

QoS Services composition User QoS requirement Genetic algorithm Service selection

2016-12-21。国家自然科学基金项目(61379032)。杨真谛，硕士，主研领域：软件工程，软件演化，软件过程。秦江龙，教授。李彤，教授。韩煦，硕士。藏传宇，硕士。陈长赓，硕士。

TP3

A

10.3969/j.issn.1000-386x.2017.12.016