移动云计算复杂网络环境下任务粒度的应用划分和调度方法

The application partition problem (APP) in the mobile cloud computing (MCC) is an important research problem. Building the network based on social relationships enables the MCC to have complex network. We study task-grained APPs in the MCC with complex network, and construct their math models to minimize the power consumption of all the devices. A novel effective meta-heuristic is designed for the global search; a self-adaptive task scheduling algorithm is constructed for the local search, based on a composite neighborhood which integrates both move and swap neighborhoods; a dynamical control policy is introduced to balance the global and the local search and a hybrid application partition algorithm is proposed. A path-based algorithm is constructed to generate feasible task schedules; an algorithm is proposed to mine those task groups which are mobilizable among sub-networks, and a two-level task scheduling algorithm is designed for the optimization among and inside sub-networks; a random perturbation policy is investigated and an effective and efficient application partition algorithm is proposed. The study can be used in the real MCC and have the widespread use to other mobile computing systems with similar complex network, such as the Internet of Things.

应用划分问题是移动云计算领域的一类重要研究问题，基于社交关系组建网络使得移动云计算具有复杂网络的环境。本项目拟研究移动云计算复杂网络环境下任务粒度的应用划分问题，以最小化网络中所有设备能耗为优化目标，建立数学模型。设计高效元启发式算法用于全局搜索，基于任务转移和交换邻域构造复合邻域自适应任务调度算法用于局部搜索，设计平衡全局和局部搜索的动态控制策略并提出混合应用划分算法。构造基于路径的可行任务调度生成算法，设计可跨网移动任务组合的挖掘算法，基于任务组合的转移和交换邻域构造基于网间和网内的双层任务调度算法，设计随机扰动策略并提出高效应用划分算法。本项目的研究成果可应用于实际移动云计算平台并可推广至其他具有复杂网络环境的移动计算系统（如物联网等平台），具有广泛的应用前景、重要的理论价值和实际意义。

移动设备资源有限，无法满足如视频处理、实时大数据分析等复杂应用的资源需求。移动云计算通过将移动设备上的复杂应用划分为多个部分并分配至自身和多个服务端设备运行，使得每个设备的可用资源都能满足所分配应用部分的资源需求，以解决移动设备资源不足的问题。本项目主要研究移动云计算环境下基于两种不同网络环境的应用划分问题（MTAPP和JTAPP）。MTAPP的网络环境中所有设备彼此连通，而JTAPP的网络环境基于设备持有人的社交关系构造，具有社交关系的设备互相连通，而不具备社交关系的设备并不连通。项目组将MTAPP和JTAPP模型化为整数规划问题并分析出它们都是NP难问题。为了求解MTAPP，项目组提出混合元启发式算法ILS-CPSO和ILS-SA，两算法都基于迭代局部搜索算法框架（ILS），前者将带有收敛因子的粒子群优化算法（CPSO）作为局部搜索策略，将邻位交换作为扰动算子；后者将模拟退火算法（SA）作为局部搜索策略，将多对交换作为扰动算子。实验结果表明，ILS-CPSO和ILS-SA分别显著优于CPSO和SA。这说明扰动算子能够有效帮助CPSO和SA在陷入局部优化后跳出局部优化，从而搜索到更好的解。事实上，CPSO和SA都依靠其独特的演化机制具备跳出局部优化的能力，然而，随着算法的演进，其演化机制最终无力帮助其算法跳出局部优化。此时，一种不同于其演化机制的扰动方式却能够有效帮助它们跳出局部优化，这充分说明混合元启发式算法的优势。针对JTAPP，项目组考虑其复杂的网络环境，提出6种可行解生成策略并构造高效启发式算法IRR和IG。IRR和IG充分考虑应用工作流模型的特征，针对不同特征的任务节点采用不同的策略，从而能够保证所有任务在分配时依然保证连通性。因此，当网络中的设备具有足够资源时，IRR和IG能够保证获得可行解。实验结果验证了该结论，而作为比较的经典轮询算法获得可行解的概率不到3%。