一、背景意义：
移动设备资源有限，无法满足如视频处理、实时大数据分析等复杂应用的资源需求，阻碍了此类复杂应用在移动环境下的有效使用。移动云计算（Mobile Cloud Computing）通过将移动设备上的复杂应用划分为多个部分并分配至自身和一个（或多个）服务端设备运行，使得每个设备的可用资源都能满足所分配应用部分的资源需求，以解决移动设备资源不足的问题[1]。如何有效的划分应用是移动云计算领域的重要研究问题，称为应用划分问（Application Partition Problem，APP）。
任务粒度的应用划分问题（Task-grained APP，TAPP）是近几年的研究热点，该问题可描述成：给定移动设备上可表示成有向无环任务图的应用，如何基于该设备的可用设备网络（所有可用设备组成的网络，包括该设备本身）和任务图将所有任务划分成多个不相交集合并分配至网络中多个设备运行，使得某个优化目标最优。现有任务粒度的应用划分问题假设移动云计算环境只有一个包含所有设备的简单网络，而基于社交关系的移动云计算往往是一个包含多个子网的复杂网络：多个设备基于持有人的社交关系组成共享资源网络[1][11]，使得移动云计算网络包含多个基于不同“社交圈”（类似于“QQ 群”和“微信群”）的子网，每个子网都是一个 MDN 且互相交织（某些设备位于多个子网，称为交织设备）。相比于现有简单网络环境下任务粒度的应用划分问题，移动云计算复杂网络环境下任务粒度的应用划分问题更难以优化，具体表现在：（1）网络的复杂性：网络包含多个互相交织的 MDN 子网；（2）设备的不对等性：子网内设备互相可用，不同子网的非交织设备互相不可用。因此，移动云计算复杂网络环境下存在非交织和交织两类设备，非交织设备上的 TAPP 类似于现有 MHD 方式下基于 MDN的 TAPP（称为 MTAPP），而交织设备上的基于 JMDN 的 TAPP（称为 JTAPP）是更为复杂的问题。
二、国内外研究现状：
随着移动云计算的飞速发展，对任务调度这一问题有许多的研究团体。文献[2][3][4]分析了目前的研究现状，以下是结合行业最新研究成果，对相关问题的研究现状进行总结。
对于SDR模式下的任务调度，近年来许多国内外研究学者进行了相关研究，Li和Chen[5]使用DVS设计了一个动态任调度算法（EDTS）,该算法主要考虑的是早移动终端与云频繁的交互中会消耗大量能量，因此，该算法通过自适应调整处理器的电压和频率，优化了任务的执行路径，所以在任务满足约束的情况下，最终总能量消耗是最低的。类似的，Lin等人[6] 提出了一种结合动态电压和频率的复合启发式算法（DVFS）来解决任务调度。这个算法基于任务图，以最小化设备能耗为目标，同时考虑了应用终止时间的约束。Chen等人[7]提出了一种应用卸载动态算法，旨在为移动云计算环境下的任务调度节省时间和能耗。该算法根据程序运行过程中的实时信息，将程序的部分或全部卸载到云端，并利用云计算丰富的计算资源，扩展移动智能终端，从而减少应用的执行时间，降低智能手机的能耗。Saha和Hasan提出了一种将任务熊移动终端迁移到云端的迁移决策算法。首先，该算法确定迁移任务的移动终端的本地服务当前是否可用，如果可用，则确定云中的服务器是否可用，如果它也可用，那么估计在移动设备上执行任务和在云中执行任务所花费的时间，如果在移动设备上执行的时间更短，最后的决定是在移动设备上执行，否则，将任务卸载到云服务器上执行。
Wang 和 Li[12]针对任务粒度的应用划分问题提出了一个动态优化算法，该算法基于应用的任务图，以最小化 CPU 和带宽加权和的综合资源消耗为优化目标，该算法能够根据移动设备的实际可用 CPU 和带宽，动态的将任务在移动设备和服务端设备迁移。实验结果表明，该算法能够较好的适应动态环境，当 CPU 和带宽资源发生改变时，能够即时给出任务的最优迁移方案。Soyata 等[13]设计了一个基于 cloudlet 的应用框架 MOCHA，并基于该框架实现了一个人脸识别应用以验证框架的可用性；框架的核心是一个针对应用划分问题的启发式贪婪算法，考虑通信延迟和 cloudlet（或云）服务器的可用计算资源，以应用反应时间为优化目标，将所有任务划分成两个不相交的集合，一个集合分配至移动设备本地运行，另一集合分配至 cloudlet（或云）服务器执行。模拟实验表明 cloudlet 由于与移动设备距离较近，确实能够有效提高应用的 QoS，同时，提出的贪婪启发式算法的性能也优于随机算法。Balakrishnan 和 Tham[14]不仅考虑了应用在移动云计算环境下的划分问题，还考虑了分配到本地的任务在移动设备多个 CPU 核上的调度问题；论文将应用划分问题模型化为 QAP（Quadratic Assignment Problem）问题，并以最小化移动设备能耗为优化目标提出二阶段遗传算法，第一阶段生成一个任务调度，将任务映射至计算资源，第二阶段通过 DVFS（Dynamic Voltage and Frequency Scaling）技术在不降低优化目标值的情况下降低 CPU 核的频率，进一步减少能耗。类似的，Chen 等[15][16]也使用 DVFS 技术求解应用划分问题，提出基于半马尔科夫决策过程的算法，确定分配至云上的任务、在本地运行的任务及其对应的 CPU 核和各核的频率。实验验证了该算法明显优于一些基准算法。
另外，对于MHD模式下的任务调度，近年来有许多国内外学者对其进行了研究。Verbelen等人[8]针对任务调度问题，提出了三种降低网络中所有设备通信成本的有效算法：基于多层图划分和任务转移邻域的启发式算法MLKL，模拟退火算法SA和混合算法KLSA。其中KLSA是融合了MLKL和SA的混合算法，SA用于全局搜索，MLKL用于局部搜索，因此三种算法中KLSA的性能最好。国内学者Yang[9]等人研究了基于移动设备、cloudlet和云形成MDN的任务调度算法，他们将该应用程序描述为多个任务的工作流，结合应用的实际情况和设备的节能效果，提出了一种高效的启发式算法。算法基于任务工作流逐个考虑任务，若任务在 cloudlet 或云运行都无法减小完工时间，则分配至移动设备；若任cloudlet 运行能有效减少完工时间而且能耗与在云运行差不多，则分配至 cloudlet；若任务在 cloudlet 运行能够大量节约能耗且完工时间没有超过截止日期，则分配至 cloudlet；其他情况则分配至云。实验结果验证了该算法的有效性。Huang等人[10] 研究了具有能量约束的移动云计算的任务调度问题，建立了基于基本任务属性的任务分类模型，并基于任务分类进行任务调度。Kristensen和Bouvin[17]设计并实现了一个应用划分系统 Scavenger，支持将任务粒度的应用划分成多个部分并分配至本地和多个服务端设备执行，以最优化应用的运行时间；Scavenger 的核心是一个基于任务和多个服务端设备 Profile的启发式任务调度算法，该算法能准确评估任务在各设备上的运行时间，并将任务分配至运行时间最短的设备。实验结果表明，该算法能够有效提高移动应用的 QoS，但需要较多数据构造 Profile。
三、立论依据：
考虑上述基于研究现状分析出的主要问题和重要挑战，本项目拟针对移动云计算复杂网络下任务粒度的应用划分问题进行研究，提出针对最小化网络中所有设备能耗的高效应用划分算法：在不同子网中非交织设备互相不可用的前提下，使用启发式策略将应用任务分配至合适的移动设备，能够最小化任务的整体完工时间，同时保证移动设备所消耗的能量满足给定的能量约束。
