基于网络连接性的移动网格任务调度算法

吴香林，蒋 青，张佳星

(1.中国移动通信集团四川有限公司乐山分公司，四川乐山 416000;2.重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065)

随着移动终端技术和网格技术的快速发展，用户在任何地点、任何时间都可以访问全球网络资源，那么将移动终端加入网格系统作为网格资源，形成移动网格［1］。移动资源大多属于便携式移动设备，随网格用户的移动，其网络连接性发生变化。资源移动的网络连接状态会影响任务调度过程中资源的重新分配。现有任务调度技术存在不足［2－3］:移动网格计算资源包括固定设备和移动设备，这些设备的处理能力差异很大;大部分设备不是移动网格的专用处理设备，它们随时有可能处理用户自己的事务，因此在执行网格任务时其处理能力也在动态变化;并且受移动环境的影响，移动终端与通信网络的连接是一种弱连接，即低带宽、长延迟、不稳定和经常性的断开。因此在任务处理过程中还要考虑移动设备的间歇连接性［4］。现有遗传算法［5－7］进行任务调度过程中未考虑移动资源特性，文献［8］表明一个资源节点平均只有28%的时间保持在一个网络连接状态。移动设备的网络连接遭受频繁断连。因此，本文将重点分析移动性和网络连接性对任务调度技术的影响。

1 移动设备移动概率分析

根据已有的移动模型，可以预测行人和车辆的移动速度和方向，但是移动终端在移动网格中移动的概率如何计算未知，因此本文假设移动设备j的移动概率为pj'

式中:n是位置定位检测器在Δt时间内总的定位次数;m是在该短时间内连续两次定位结果不同的次数。式(1)只能判断移动设备j在同一个网格中移动的频繁度，无法判断它是否移出了当前的移动网格。为此引入式(2)计算移动设备移动，但是仍然保留在当前移动网格中的概率为

如果移动设备移出了当前的移动网格，则P″j=0。其中:A事件是移动设备j保留在当前移动网格中;B事件是移动设备移动。为了研究需要，本文取(B/A)的对立事件(即移动设备移出了当前网格和移动设备在当前网格中不移动)的概率为

那么移动设备从当前网格移出到另一个网格中的概率为

Pjout仅考虑移动设备的移动性，未考虑移动设备移出到另一个网格的网络连接性。下文讨论网络的连接性因素对网格任务调度的影响。

2 改进算法的理论分析

调度的目标是最小化应用的时间跨度，也就是在尽可能短的时间内完成任务。约束条件是整个调度期间内所有资源的处理能力总和应大于等于所有任务的负载总和。

任务集合T={t1，t2，…，tn};在一个调度期间内n的值不变。

资源包括固定资源和移动资源，本文重点分析移动资源。假设移动资源集合R={r1，r2，…，rm};其初始状态与网络的连接状态有无连接(不可用)和有连接(可用)两种情况。

任务向量Vt是一个向量(t，r，e)。其中t代表任务;r代表资源;e代表执行时间。根据t和r在时间矩阵EETn×m中查出。任务执行时间矩阵EETn×m，其中每个元素值表示该任务在对应的资源号上执行时间用eij表示。

移动设备的状态分4种:设备开机网络连接、设备开机网络断开、设备关机网络断开、设备关机网络连接(不可能事件)。本文主要考虑手机处于开机状态下，则移动设备只会处于两种状态:连接状态和非连接状态。两者转化概率分别是α和β，其中α是单位时间内移动设备从连接状态转化为非连接状态时的平均发生率，β是单位时间内移动设备从非连接状态转化为连接状态时的平均发生率。

移动终端的连接与非连接状态的状态转移概率矩阵如下

由此可以得出

结合公式(6)和(7)联解得

求解:α=0或α+β=1。其中α=0舍弃，不符合实际情况。则α+β=1。通常情况下，两者转化概率的选取原则是β≥α。根据下文实际场景设置两者的取值分布。

根据上述分析，假设移动设备在同一个网格内的网络连接状态维持不变，移动设备移出当前移动网格并保证下一个选中的移动网格的网络连接状态良好的概率为

移动设备经过一段时间后仍然保留在当前移动网格中并且处于网络连接状态下的概率为

移动设备移动后进入下一个移动网格并且处于网络断开状态的概率为

移动设备经过一段时间后仍然保留在当前移动网格中并且处于网络断开状态下的概率为

移动网格任务调度中，需要考虑移动网格的移动性和移动设备的网络连接状态影响的数据传输时间。如果移动设备执行任务时断开了连接，其上运行的任务就被终止等待重新调度。假设理想情况下网络处于连接状态，传输数据需要的时间为t，那么实际Pconn传输数据的时间为gc(t)，在Pdisc传输数据时间为gd(t)，其中β－1为网络恢复连接的平均等待时间。那么

若不考虑终端的移动性并且终端在同一个移动网格中的连接性不变，则在移动设备j传输数据的平均时间结合上式(8)和式(14)得出

假设twj表示在资源j上执行的等待时间，则调度一个任务i在资源j上的时间Tijall为

基于移动设备移动性考虑，在t时刻移动设备j传输数据的平均时间结合上式(8)和(14)得出gmj(t)为

假设twj表示在资源j上的等待时间，则调度一个任务i在资源j上的时间Tijmall为

为了获得最优的任务调度方案，本文采用具有全局搜索能力强、速度快的启发式算法，如遗传算法来实现，提高移动网格任务执行分析效率。

3 仿真结果与分析

3.1 遗传算法的优势分析

假设在同一个移动网格中，移动资源的能量充足，不考虑其移动性和终端的网络一直处于连接状态(完全理想状态下)。固定任务数和资源数，通过采用两种不同的调度算法如Min－Min算法和GA算法分析比较单个任务的执行时间和各个资源的负载分布状况。

首先，引入遗传算法需要设置一些参数。假设任务数为100个，资源数为10个，变异概率为0.1，分析交叉概率的变化时，要保证适应度函数平稳变化，因此选取交叉概率为0.8。任务执行过程中，数据通信输入和输出的时间设置为1 s，一个任务的期望执行时间随机设为20 s左右。

其次，通过搭建仿真场景，假设任务一旦被调度都是一次性执行成功，那么分别采用两种算法进行仿真验证，得出各个资源的负载分配和单个任务调度完成的总时间分布如下图1和图2所示。

图1 两种算法的资源负载比较

图2 两算法单个任务调度跨度时间

最后，分析图1可见，采用遗传算法资源的负载均衡效果优于Min－Min算法。分析图2可见，在同一个移动网格中，资源位置固定并且网络的连接性不改变时，固定资源数为10个，任务数逐渐增加。当任务数较小时，Min－Min算法执行任务速度较快。随着任务数增多，Min－Min算法对单个资源的负载情况较重。每次选取最小时间的任务在对应的资源上执行，会出现单个任务的等待时间，导致资源浪费或是资源负载不均衡的现象，从而迫使后续任务执行时间增加。但是采用遗传算法，在同样场景下这一现象会得到明显改善。通过仿真验证，当任务数逐渐增加时，遗传算法对缩短任务的等待时间，实现单个任务时间最小化调度的优势很显著。

进一步分析上述场景，在同一个移动网格中，固定资源数改变任务数。分析两种不同的调度算法对任务调度总时间的影响。通过仿真验证得出随着任务数的增加两种算法的任务调度总时间分布如图3所示。

图3 任务数增加，两种算法总执行时间

从图3中可以得出，当任务数和资源数比较接近时，两种算法的调度总时间几乎一致。但是随着任务数逐渐增加，遗传算法的任务总跨度时间会有极大的缩短，而Min－Min算法资源负载分布不均衡导致产生了大量的等待时间，导致了任务总跨度时间偏长。鉴于上述对比分析，本文后续将对遗传算法进行改进探讨。

3.2 改进算法的验证和分析

假设移动设备在不同的网格中，有不同的网络连接概率，同时考虑其移动性，采用遗传算法对引入移动性和网络连接因子的前后两种状况进行分析，比较引入前后对任务调度时间和资源负载情况的影响。

设置任务数为100个，资源数为10个，交叉概率为0.8，变异概率为0.1。根据式(9)移动设备的网络连接性由连接状态转化为断开状态的概率α服从泊松分布。搭建仿真环境，得到各个资源在执行单个任务过程中网络连接性发生转化的概率分布如图4所示。可见资源网络开始处于连接到断开的概率较小，则反之概率较大。但是某些特殊场合会存在执行任务时网络突然失效的现象，所以需要考虑网络连接性对任务调度的影响。

图4 网络连接性状态改变的概率分布

针对实际网络连接不稳定和理想状态网络一直处于连接的情况，采用不同算法进行分析。得出两种情况的资源负载分布如图5所示，可见资源负载是不一致的。因为在实际情况中由于移动设备自身的网络不稳定等特点，使得任务和资源按照理想状态下的分配方式无法执行，需要重新选择资源。所以当某一个移动网格的网络比较稳定时，则该网格中移动设备执行任务的次数偏高，就出现某个网格中的资源负载量过大。

图5 不同网络环境下的负载图

为了体现两种情况下任务执行顺序是不一致的特性，本文在调度的过程中计算个体选择概率值，根据概率值大小选取任务执行的顺序。为了便于观察，设置任务数为50个，其他参数保持不变，进行仿真验证，两种情况的任务执行顺序如图6所示。

图6 不同场景的任务执行顺序比较

最后，进一步考虑移动性和网络连接性，固定资源数和任务数。分别在理想状态下与实际场景下，采用标准遗传调度算法进行分析。对采用遗传算法与不采用调度算法进行随机选择调度的情况都进行了对比，分析3种状态下对任务调度总时间的影响。通过仿真验证3种情况下任务调度总时间分布如图7所示。分析图7在实际场景下未采用调度算法比采用遗传算法的任务执行时间长，实际场景网络连接不稳定状态比理想状态下的任务执行时间长。这是因为在实际情况下任务执行过程中网络频繁断连，造成部分任务多次被调度的时间浪费;又如在网络全连接状态下，移动终端不必考虑选择网络的时间，也节约了一部分时间。因此理想状态下任务调度总时间最少。

图7 任务调度总时间的比较

4 结束语

本文首先对所持便携式移动资源的网格用户的移动概率进行了理论推导。其次对资源在移动网格中的网络断连性进行了分析，提出了基于移动性和网络断连性的算法。仿真结果表明，在理想状态下，遗传算法比Min－Min算法较适合本文所设场景。基于移动性和连接性的算法在实际场景中能提高资源利用率和任务执行成功率，更加精确任务调度的时间，提高用户的满意度。

:

［1］VAITHIYA S S，BHANU S M.Scheduling tasks in mobile grid environment using mobility based resource prediction［C］//Proc.lst Intemational Conference on Parallel Distributed and Grid Computing(PDGC2010).Solan:［s.n.］，2010:89－94.

［2］杜丽娟，余镇危.移动网格发展研究［J］.计算机工程与设计，2010，31(6):1166－1169.

［3］PARK S M，KO Y B，KIM J H.Disconnected operation service in mobile grid computing［C］//Proc.1st International Conference on Service Oriented Computing(ICSOC’2003).Trento，Italy:Springer，2003:499－513.

［4］刘宴兵，陈杰，熊仕勇.基于QoS相似度的网格任务调度算法［J］.重庆邮电大学学报:自然科学版，2009，21(3):416－420.

［5］PRABHU S，KUMAR N V.Multi－objective optimization based on genetic algorithm in grid scheduling［J］.Int J Adv Res Technol，2011，1(1):54－58.

［6］CHIN S H，SUH T，YU H C.Genetic algorithm based scheduling method for efficiency and reliability in mobile grid［C］//Proc.the 4th International Conference on IEEE Trans.Parallel and Distributed Systems.［S.l.］:IEEE Press，2009:928－934.

［7］刘慧婷，姜晓涛，陈健.基于遗传算法的网格任务调度方法研究［J］.计算机技术与发展，2012，22(4):69－76.

［8］XU Haiyan.Research for new modified adaptive genetic algorithm［C］//Proc.World Automation Congress(WAC).［S.l.］:IEEE Press，2012:1－4.