移动网格中任务分组的调度算法研究

罗显兵，吴香林

（1.广州杰赛科技股份有限公司通信规划设计院，重庆 400042;2.重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065）

移动网格中任务分组的调度算法研究

罗显兵1，吴香林2

（1.广州杰赛科技股份有限公司通信规划设计院，重庆 400042;2.重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065）

针对移动网格中任务量大的调度问题，考虑到同一网格域中有限的网格资源且资源的能量受限因素，提高移动网格的任务执行成功率和资源利用率就尤为重要。改进Min-Min算法，首先对大量任务分别按照指数、线性、对数方式进行分组，确定各组任务数，然后再利用移动终端能量受限和Min-Min算法结合的Energy Min-Min算法（即E-mm算法）进行调度。通过仿真验证分析，该改进算法相对于Min-Min算法，提高了任务执行成功率，并且系统负载均衡效果也得到明显改善。

移动网格;E-mm算法;剩余能量;任务分组;任务调度

【本文献信息】罗显兵，吴香林.移动网格中任务分组的调度算法研究［J］.电视技术，2013，37（3）.

随着无线移动通信系统的快速发展，用户可以随时随地访问全球网络资源。它以无缝、透明、安全、有效的方式支持移动用户和共用网格资源，实现了无线技术与网格计算的融合。因此，移动设备被纳入到网格系统中成为网格系统的组成部分，形成移动网格［1］（Mobile Grid）。移动网格最大优势是引入了移动设备。因为移动设备与普通大众有着最直接的联系，因此移动网格更加贴近人们的生活，带来了很多便利，在日常生活中有着广泛的应用。目前将移动设备作为移动网格中的一种资源使用已成为研究热点。

在移动网格中，便携式设备数量显著增长，当大量移动用户发起任务请求时，如何快速有效地调度可用资源，既保证任务执行成功率，又提高可用资源的利用率和平衡系统资源负载，已成为研究过程中的一个非常核心的问题。较好的调度策略需要考虑以下三点［2］:1）每个任务的处理需求;2）根据资源的处理能力设计合理的任务分组机制;3）将分组任务传送到恰当的资源。

尽管移动终端的能量是有限的，但是在执行某一任务期间必须保证能量充足。否则，移动设备就没有足够能量保证任务继续执行完毕，导致任务需要重新被调度。由于计算任务到达的随机性，使得单位时间内到达的任务量时而稀疏，时而密集，而现有的网格计算系统通常是资源长时间处于开启状态，等待计算任务到达，资源处于空闲状态时，其空闲能耗占总能耗的50%～60%［3-4］，这种情况会过度浪费能量，使整个调度系统的吞吐量下降。因此，有必要提供一种移动网格任务调度方法来克服上述缺陷。基于任务分组的E-mm算法。首先，将大量任务进行分组，针对各组任务采用Min-Min算法选取合适“任务—资源”对。其次，判断匹配的最小期望完成时间与对应资源的能量极限时间的关系，选取合适的调度策略进行任务调度。该E-mm调度策略与传统的Min-Min算法相比具有较好的资源负载性和较高的任务执行成功率等优点，与已有的调度算法相比在某些方面具有更优的性能。

1 移动网格的系统结构

随着移动互联网应用的逐渐普及以及移动搜索应用的不断完善，当用户需要查询一些急需信息（如电话号码、地图、公交路线等）时，会越来越倾向于使用移动搜索。移动网格系统结构［5］如图1所示，主要由3个模块组成:固定网格站点，移动终端群，中间件移动网关。

图1 移动网格系统结构图

移动网格中，移动终端有两个用途:一是作为被调度的资源;二是作为提供服务的资源。前者是移动设备去访问网格资源，而后者是把移动设备作为网格资源，从而为其他网格用户提供服务。移动终端，是指不包括笔记本在内的具备有限计算资源的设备。移动终端的体型不断缩小，变得更为小巧和易于携带，而功能却日益强大，服务不断延伸，集通信、视频、阅读等多种功能为一身。但移动终端存在缺陷，具体表现在以下几点:有限的内存和存储资源，通常在2～64 Mbyte之间;计算资源、电池寿命、网络带宽、显示和输入能力是有限的，有多种多样的处理器、操作系统。

2 移动网格的任务调度

任务调度问题实质就是一个由用户提出的N个需要调度的任务和系统中M个可用的资源构成的场景下，把N个任务以最合理的方式匹配到M个可用的资源上，目的是使得任务的总完成时间尽可能小［6］，任务执行成功率高和资源负载均衡效果较好。

2.1 任务分组

若移动网格有N个相互独立的任务可以表示为任务集T={t1，t2，…，tN}。为了便于分析问题，假设移动网格环境下提交的任务为元任务［7］。当大量任务中若有多个任务同时抢占相同的网格资源时，就会发生冲突，引起阻塞，阻塞会影响网络的调度性能。针对上述问题，采用任务分组策略，分组后不同优先级任务发生冲突时，为了尽量保证网络的QoS，则需要尽量保证高优先级任务的调度的成功率，而阻塞低优先级任务的调度。

移动网格系统在不同应用场景中，各优先级任务的数量分配都是不确定的，因此需要用不同的数学模型为其分配每个优先级组别的任务，并进行相应分析。本文对优先级的划分使用了3种不同数学函数分析研究，对3种方式分组后系统的性能进行了比较，分析了在不同的移动网格环境下，使用哪种优先级划分方式对系统的QoS较好，并进行了仿真说明。

线性函数方式为

指数函数方式为

对数函数方式为

式中:n=1∶8（分组等级号），GN为n号分组等级任务数，设定具体的a，b，k参数，可以得到对应的优先级分组中的任务数。通过对运用以上3种优先级划分后，任务执行成功率、资源负载等性能进行分析，得出3种方式分别适合的移动网格调度环境。

2.2 Min-Min任务调度算法

Min-Min调度算法是一种简单快速、高效的算法。该算法调度流程如图2所示。首先，输入任务数和资源数，由未执行的任务构成集合T，可用资源构成集合M，对于集合T中的每个任务计算其在所有可用资源集M上的期望完成时间，得到期望矩阵为ECT。然后，选择每个任务的最小期望完成时间构成集合ECT={Min0＜j＜k（ct（ti，mj），ti∈T）};从ECT中选择最小完成时间的任务和相应资源进行匹配。最后，从T中删除该任务重复上述操作直到集合T为空。该算法最大的缺点是资源的负载严重不均衡。

图2 Min-Min算法的调度流程

2.3 E-mm任务调度算法

任务分配给资源之前，首先确定该资源是否有足够的能量来执行此任务。只有当移动资源能量充足时，才把任务分配给该移动资源执行。假设资源与网格系统断开连接时消耗很少的能量，可以忽略不计，那么移动资源通常处于空闲和任务执行状态。电池可用剩余能量是决定电池运行时间的主要因素。电源法是国家信息产业部为通信行业电池容量选择而规定的方法。

式中:Q为电池组容量;I为电池组电流;K为电池保险系数（取1.25）;T为电池放电时间（单位为h）;H为电池放电系数;A为电池温度系数（1/c）;P为电源的标称容量（单位为V·A）;Umin为电池组最低电压;Pf为电源的功率因子;q为放电容量系数。

电池的能量是指电池在一定条件下，对外做功所能输出的电能，通常用W表示。实际能量是指电池放电过程中实际放出的能量，在数值上等于实际容量与平均输出电压的乘积，即

式中:Umax为终端充电满是的最大电压值;Umin为终端放电至某一极限的最小电压值。

式中:tj

in表示资源处于网络连接状态下接收第j个任务的原始数据所需的时间;tji表示资源i计算第j个任务需要的时间;tj

out表示资源处于网络连接状态下发送第j个任务的输出结果数据所需的时间;Wiavai表示资源i可用剩余能量。

根据式（9）和式（10）计算移动设备的最大可持续时间和任务执行的成功率。Pbusy，Pidle，Ncom和Nall分别表示移动终端处于执行、空闲状态的功率消耗、任务执行完成数和总任务数。

根据上式（11）判断资源的持续时间是否满足该任务执行不受能量的影响。反之，则导致任务执行失败。本文研究根据调查统计移动终端的电池容量一般是3 000～4 500 mAh，当终端处于空闲状态时电流为50～80 mA，处于忙时的电流为120～150 mA。

3 仿真与分析

假设场景是同一网格域中的资源数选取为350，任务数从500以步长为200递增到2 500。根据以上3种分组策略将任务数分组后和未分组时，分别采用Min-Min算法和E-mm算法进行仿真，对任务执行成功率进行比较，得到4种情况的任务执行成功率，如图3所示。

图3 不同任务数下任务分组策略的成功率比较

从图3分析，可得出随着任务数的递增，两种算法的成功率都有所下降。随着任务成功执行，消耗了移动资源的能量。因为移动资源的能量有限，无法承担过大的任务量，所以任务数越多，执行成功率越低。针对分组策略详细分析如下，如选取资源数为350，任务数为1 500。按照上述3种分组方式，将任务分为8个组，得到各组的任务数如图4所示。

图4 任务数为1 500时，各组的任务数

本文ps1，ps2分别代表Min-Min算法和E-mm算法的任务执行成功率。分别针对不同的分组策略采用Min-Min算法和E-mm算法，分别仿真分析得到不同分组模式下，任务执行的总时间跨度如图5～图8所示。

针对上述对数分组，任务数为1 500，资源数为350，ps1=0.81，ps2=0.99时，仿真验证该系统中两种算法下的各个资源上的负载情况如图9所示。综合上述分析，当任务数较少时，任务不分组和分组的优越性不是很明显。随着任务数的增加，将任务数进行分组调度的优越性就很明显，使得系统的高优先级任务调度成功率大幅提高和执行时间缩短，但是牺牲了低优先级任务大量的等待时间，来提高高优先级的任务执行成功率。其中在任务量较大的环境下，对数分组策略是最佳选择。

图9 对数分组时，两种算法的资源负载

4 结论

通过对移动网格中任务量大时的调度算法进行研究，考虑移动网格中移动终端能量约束的任务调度方式，结合移动网格中移动终端的特点改进经典的Min-Min调度算法。根据任务量大小，先对任务进行分组和分别计算移动终端可用剩余能量的持续时间。通过能量与电流间的转化关系计算出各个资源的可用时间，优先选择高优先级的任务匹配可用资源参与调度，尽量减少由于资源能量受限对系统任务调度所产生的影响。通过仿真验证总执行时间、资源利用率、任务执行成功率等评价指标，说明在此环境下E-mm算法优于传统的Min-Min算法。采用E-mm算法后系统能够获得较好的负载均衡性能，任务执行成功率也得到提高。

:

［1］LITKE A，SKOUTAS D，VARVARIGOU T.Mobile grid computing:changes and challenges of resource management in a mobile grid environment［EB/OL］.［2012-06-15］.http://www.akogrimo.org/modulesfe0a.pdf?name=UpDownload&req=getit&lid=28.

［2］徐慧媛，袁捷.网格应用中基于动态分组的调度策略［J］.计算机应用与软件，2006，11（23）:58-59.

［3］KANSAL A，ZHAO F.Fine-grained energy profiling for power-aware application design［J］.Sigmetrics Performance Evaluation Review，2008，36（2）:26-31.

［4］COSTA G D，GELAS J P，GEORGIOU Y，et al.The green-net framework:energy efficiency in large scale distributed systems［C］//Proc.IEEE International Symposium on Parallel and Distributed Processing，2009.Rome:IEEE Computer Society，2009:1-8.

［5］都志辉，陈渝，刘鹏.网格计算［M］.北京:清华大学出版社，2002.

［6］吴高峰，蒋玉明.基于QoS改进的Min-Min网格调度算法［J］.微计算机信息，2009，25（9）:110-112.

［7］曹怀虎，余镇危，徐寿林.网格环境中任务调度算法的研究［J］.计算机工程与应用，2004（5）:87-88.

Study of Grouping Tasks Scheduling Algorithm in Mobile Grid

LUO Xianbing1，WU Xianglin2

（1.Institute of Communication Planning and Design，GCI Science＆Technology Co.，Ltd.，Chongqing 400042，China;2.Chongqing Key Lab of Mobile Communications Technology，Chongqing University of Post and Communications（CUPT），Chongqing 400065，China）

Aiming at the large amount of the mobile terminals task scheduling problem in mobile grid，considering the limited mobile resource and its energy limited（the small-capacity battery）factors at the same grid domain，it’s important to improve the task execution success ratio and the utilization rate of resources particularly.To improve Min-Min algorithm，first according to the exp，linear，log function，it divides a large number of tasks into groups to determine the respective number of tasks，and then proposes Energy Min-Min algorithm（E-mm algorithm），which is combined the mobile terminal energy restriction with Min-Min algorithm for task scheduling.Through the simulation analysis，the modified algorithm is much better than the Min-Min algorithm，which improves the success rate of task execution，and the system load balancing effect is improved obviously.

mobile grid;E-mm algorithm;remaining energy;task grouping;task scheduling

TN949.6

A

罗显兵（1979— ），学士，主要从事无线系统网络咨询规划设计、网络优化相关工作;

吴香林（1987— ），女，硕士，主要研究移动通信及移动网格。

责任编辑:任健男

2012－09－19