李 靖，任丽芳，王文剑,3

(1.山西大学 计算机与信息技术学院 山西 太原 030006；2.山西财经大学 信息学院 山西 太原 030006；3.山西大学 计算智能与中文信息处理教育部重点实验室 山西 太原 030006)

0 引言

随着云计算和移动互联网的结合，用户可以在移动环境中随时随地使用智能手机等终端设备访问网络中的云端服务[1]。由于越来越多的服务提供商进入网络服务市场，导致同一功能的任务可以由越来越多的服务实现，然而这些服务通常具有不同的服务质量(quality of service, QoS)，如响应时间、价格、吞吐量、可靠性等。网络服务的功能简单、门类繁多、属性各异，用户需要从数量巨大、QoS迥异的服务中选择适用的组件服务，并进一步实现服务组合以完成较为复杂的业务[2]。因此，如何快速找到QoS最优的组合服务成为亟须解决的问题。传统的服务选择方法是对每个任务选择QoS最优的服务，但在移动环境中，用户要调用服务时既需要考虑初始信息(例如用户所处位置、调用时刻以及设备类型)，又需要考虑用户的移动性，这导致服务选择变得更加困难。移动环境中用户的位置不固定，且响应时间属性受用户移动的影响较大，使得响应时间感知的移动服务组合方法研究成为移动服务计算领域的一个重要方向。近年来，已经有很多研究致力于解决QoS感知的服务组合问题[3]，大致可分为全局最优方法和局部最优方法两类。全局最优方法是从所有的服务组合中找到最优的组合服务，其典型方法是将满足用户QoS约束的服务组合问题建模为一个整数规划问题[4]，但这类方法求解难度很大，因此最常用的是局部最优方法，即选择最优的组件服务进行组合。……