1）研究背景和立论依据
随着移动互联网的飞速发展，移动设备已经渗透到人们工作生活的方方面面，移动设备不再局限于智能手机和平板电脑等通讯设备，已经拓展到汽车中控、电视盒、智能机器人、智能家居、无线传感器等诸多可以使用移动网络的设备。因此移动设备的“移动”概念不再局限于设备是可以移动的，而是设备可以使用移动网络进行连接与数据交换[1]。然而相比于传统的服务器或者桌面设备，移动设备由于其自身特点，在多个方面存在不足之处，主要体现在：
(1) 资源：移动设备的处理性能、存储空间和电池容量与传统设备相比仍存在较大差距，无法满足大规模、长时间的计算密集型的移动应用的性能需求；
(2) 网络：移动设备经由AP、通信基站或卫星链路接入移动网络，可能会造成移动设备间进行数据传输时造成延迟；
(3) 安全性：移动设备上存储了过多的敏感信息，与传统的服务器和桌面设备相比较，安全防护策略不足。
为了突破移动设备处理性能、存储空间和电池容量等方面的限制，为移动用户提供更丰富的移动服务和更高的服务质量(Quality of Service, QoS)[2]，将云计算的计算和服务模式引入移动环境，移动云计算(Mobile Cloud Computing, MCC)因此作为一种新的模式。移动云计算一般可以定义为移动设备通过移动网络，以按需、可扩展的方式从云端获取所需的基础设施、平台、软件等资源或者信息服务的使用与交付模式[3]。根据移动云计算的定义，移动云计算的一般架构如图1.1所示。
面对日益复杂的移动应用程序，移动设备由于资源有限，无法满足如视频处理、实时大数据分析等计算密集型移动应用程序的对于处理性能的需求，阻碍了此类应用在移动环境下的有效使用。通过将移动应用划分为多个任务，并借助移动云计算强大的计算能力，将部分或者全部任务迁移到云端上执行，使得每个移动设备的可用资源能满足所分配任务的资源需求，增强了移动设备的处理性能，降低了能量的消耗，解决了移动设备性能不足的问题。移动云计算提供的基于远端资源共享和增强移动计算二者相统一的平台，提高了移动应用的运行效率，提高移动应用服务的可靠性和可用性的同时，减少移动设备端的资源与能量的消耗[4]。
图 1.1 移动云计算架构
- 研究现状
移动云计算任务调度问题是组合优化问题，已被证明是一个NP难问题[5][6]，通常无法在多项式时间内求解。NP难问题是计算复杂度理论中难度较大的一类问题，只有通过穷举法找出解空间中所有的可能解，逐一验证其是否满足约束条件，才能获得稳定的最优解。任务调度问题的解空间通常是指数级规模的，穷举法的代价及其昂贵，所消耗的时间和成本通常难以承担，会极大拖累整体的效率，很少应用于实际领域内的应用问题中。研究者开始转变思路，寻找一种逼近最优解的方法，并忽略解空间中其他可能的路径，成为了提升任务调度问题求解性能的关键[7]。
