移动云计算随机任务序列的执行调度

陈思颖 郭跃 胡欢波

摘要：移动云计算是一种将移动互联网与云计算相结合的新技术，用户可将数据的计算和存储等任务调度至云端来改善其移动终端处理能力弱、存储空间小及电池续航时间短等缺点。本文针对关联性的混杂任务序列，建立具有顺序相关性的任务队列模型。针对任务的随机性，在满足任务的平均等待时间要求的前提下，将移动终端对任务处理或调度时产生的能耗作为优化目标，建立连续时间马尔可夫决策过程系统模型。针对模型采用策略迭代算法对其进行求解，以期望寻找到最优策略使之既能满足时间要求又能降低能耗，仿真验证算法的有效性。

关键词：移动云计算；马尔可夫决策模型；任务调度；能耗优化；策略迭代

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）21-0036-04

Abstract：Mobile cloud computing is a new technology that combines mobile internet and cloud computing. To improve mobile terminal's weak processing capabilities， small storage space， and short battery life， users can migrate calculations and storage of data to the cloud..For mutually dependent mixed sequence tasks， a mutually dependent task queue model is established. For the randomness of tasks， a continuous time Markov decision process system model is established. Under the premise of meeting the average waiting time requirement of the task， the energy consumption generated by the mobile terminal during task processing or scheduling is used as an optimization goal. A continuous time Markov decision process system model is established. The model is solved using a strategy iterative algorithm. In order to find the optimal strategy， it can not only satisfy the time requirements but also reduce the energy consumption. The simulation validates the effectiveness of the algorithm.

Key words： Mobile cloud computing；Markov decision process； task scheduling；energy efficiency optimization；strategy iterative algorithm

现如今，世界已经进入了5G时代，落后的单一模式的计算处理已经无法满足人们对于海量数据的无限存储和多类信息的高速处理。而云计算技术正是迎合了人们对于信息处理服务质量高标准的理想需求。移动云计算（Mobile Cloud Computing）是基于云计算技术的一种新兴的移动应用模式，它是将云计算引入移动环境中[4]，是云计算和移动互联网两者结合的产物，它构建了一种“云计算-互联网-移动终端”的构架。

移动云计算主要由移动终端，无线互联网络，和存储云计算资源的云端服务器三部分组成，移动云计算系统的总体架构如图1所示[5]。首先，用户移动终端通过基站（Base Station， BS）或接入点（Access Point， AP）以无线的形式进入通信网络中，在该阶段中移动终端会与基站或者无线接入点（如路由器等）之间进行空中对接，将终端的信息发送给移动网络服务器，服务器将无线资源合理地分配给移动终端，同时网络运营商（如联通，电信等）会对用户信息进行验证以及对业务数据库进行完善。然后，再经过互联网接入云服务供应商提供的云计算资源池中选择合适的资源进行任务处理。其中，云计算服务平台主要包括控制器和數据中心。控制器是云计算的核心，担任着资源管理的角色，它负责对用户任务的接入控制、对资源的调度分配等。存储资源的数据中心会根据控制器的决策合理的对任务进行处理。这里，网络运营商和云供应商可统称为基础设施提供商（Infrastructure Providers， InP），这也体现出了云计算基础设施即服务（ Infrastructure as a service，IaaS）的特点。

1 任务队列模型

如果任务之间存在数据依赖性，那么不同类型任务的执行顺序会受任务之间关联特性的影响，有可能出现某些任务需要等待与之有关联的任务处理完成或者达到某些特定条件后，其自身才会进行处理计算。因此，关联性任务之间的触发条件或影响因素会对系统性能产生较大的影响。

本文主要针对存在顺序相关性约束条件的任务进行研究。假设本地移动终端内有[I]类任务，第i类任务达到本地移动终端的过程服从泊松分布，在本地移动终端和云端服务器中的处理速率服从负指数分布。

考虑到任务之间有一定的执行顺序所以在下文中我们对任务执行调度的触发条件进行了研究，建立任务队列模型，此模型中本地移动终端中对每类任务建立长度为[N]的任务调度队列和长度为[M]的任务缓存队列。

移动终端会对任务进行处理，以此来判断不同类型的任务之间是否存在着某种依赖关系：如果这些任务之间是独立运行的则直接将其都放入如图2所示的各自的任务调度队列中，这样本地移动终端可以对每类任务调度队列中队首所指向的任务进行调度处理；但是，如果到达的某类任务与其他种类的任务有关联存在着顺序关系：1）当此类任务在本地移动终端的调度队列处于满队状态时，进入此类任务的缓存队列进行等待，当执行条件触发时此类任务的调度队列有任务被调度处理，使此类任务的缓存队列中的任务进入自身的调度队列继续等待调度执行。2）当此类任务在本地移动终端的调度队列处于未满状态时，任务直接进入调度队列等待执行条件的触发。在本文中为了方便分析我们假设在[I]类任务中第[i]类任务的调度執行是第j类任务进行调度执行的触发条件。

2 连续时间马尔可夫决策过程任务调度模型

如图2所示的多类任务队列的系统模型中根据任务达到的随机特性，我们可以建立连续时间马尔科夫决策过程模型[51]如下所示：

在模型中我们将任务到达本地移动终端或任务被服务完成离开服务器的这些时间点定义为决策时刻（decision time），而相应的调度控制决策被称为行动（actions）。

2.1 状态空间

2.2 行动空间

在系统中当有任务到达或者被服务完成离开时，本地移动终端会对其自身内的任务进行调度控制决策。考虑到实际生活中终端运行时可能会达到最大负载，结合所设计的带有有限长度的队列系统模型，用[d=di（s）]表示第[i]类任务在当前状态下的行动。

接下来，考虑到任务在本地移动终端和云端服务器中服务的速率来自处理器的本身，所以可知任务在以上两者中的处理速不变。针对不同任务的到达率进行变化，对模型进行求解，如图4所示。从图4可以看出针对不同的到达率，任务的平均等待调度时间（蓝线），处理任务的平均花费能耗代价（绿线）和最终的优化目标（红线）其三者的运动曲线都向上移动即最终的稳定状态值增大。

实验对不同的任务调度策略进行仿真以做出对比性。如图5所示为在不同策略下调度任务时，随着任务的到达率的变化的代价效果图的比较。由图可看出本文所采用的算法最优 。

5 总结

本文针对关联性的混杂任务序列，建立具有顺序相关性的任务队列模型。针对任务的随机性，在满足任务的平均等待时间要求的前提下，将移动终端对任务理或调度时产生的能耗作为优化目标，建立连续时间马尔可夫决策过程系统模型。针对模型采用策略迭代算法对其进行求解，以期望寻找到最优策略使之既能满足时间要求又能降低能耗，仿真验证算法的有效性。

参考文献：

[1] 崔勇，宋健，缪葱葱，等. 移动云计算研究进展与趋势[J].计算机学报，2017，40（2）：273-295.

[2] Huang D， Wu H. Mobile Cloud Computing：Foundations and Service Models[M]. 2018.

[3] Dinh H T， Lee C， Niyato D， et al. A survey of mobile cloudcomputing： architecture， applications， and approaches[J].Wireless Communications & Mobile Computing， 2013， 13（18）：15871611.

[4] 江琦， 路改香， 唐昊，等. 智能电网弹性响应时间业务需求的接入控制 [J]. 控制与决策， 2014（7）：1311-1315.

[5] 江琦， 唐昊， 奚宏生. 无线多媒体接入网高能效的自适应载频开启控制 [J]. 系统科学与数学， 2014， 34（12）：1517-1526.

[6] Shahzad H， Szymanski T H. A dynamic programming offloading algorithm for mobile cloud computing[C]. Electrical and Computer Engineering， IEEE， 2016.

[7] Basu S， Pattnaik P K. A consistency preservation based approach for data-intensive cloud computing environment[C]. International Conference on Computing， Communication and Networking Technology ， IEEE Computer Society， 2017：1-5.

[8] Huang D， Wang P， Niyato D. A Dynamic offloading algorithm for mobile computing [J]. IEEE Transactions on Wireless Communications， 2012， 11（6）：1991-1995.

[9] 陆凤山. 排队论及其应用[M].湖南：湖南科学技术出版社，1984.

【通联编辑：王力】