多QoS约束下的PSO 云存储任务调度算法

李 飞，易傅潇，王 浩

（成都信息工程学院 信息安全工程学院，四川 成都610225）

0 引 言

云存储的核心是对大量数据的存储和管理。在数据的存储方面：存储系统数据的有效性和完整性是最受关注的性能指标，因此云存储系统的冗余机制提供了数据在不同节点上的备份功能，也就是其冗余的副本［1］。在数据的管理方面：当用户向服务器发出数据请求时，系统会根据相应的调度策略为用户提供相对最优的数据副本以及路径的选取，调度策略的优劣很大程度上决定了系统的运行处理效率［2］。在云计算中的调度算法相对较为丰富，但云存储在任务调度方面有区别于传统云计算的特点，在已有的对云存储的任务调度算法的研究中，引入了存在矩阵以适应云存储的特点，提出了针对云存储环境的特殊要求，相对于云计算任务来说，由于云计算任务可由云中任意节点提供，但云存储中的节点会出现节点没有任务所需要的数据的情况，引入了存在矩阵 （exist matix，EM）的概念来指示任务和资源节点的对应关系，资源节点通过存在矩阵限制其初始解和解空间，从而使得初始解以及解空间有意义。然而，网络环境是动态变化的，因此，引入网络服务质量QoS （quality of service）参数，动态实时地反映出当前网络的状态，使得在计算的迭代过程中可以根据QoS参数以及相对应的适应度函数来动态调整其影响参数，从而达到了优化算法的作用。同时，可以根据用户对网络QoS的不同需求，使得产生解更趋向于用户的QoS需求。例如部分用户的应用需求仅仅是关注于吞吐量的大小，而其他用户的应用需求可能不一定是追求其最大的吞吐量，而是对其延迟有很高的敏感度，由此可根据不同用户不同应用场景调整其对QoS参数的需求，从而使用户直观地感受到以服务质量为中心的调度策略。

1 云存储任务调度抽象

本文研究的模型前提为 “批调度”模型，即在单位时间内，等待调度的任务数为n，而调度是按照这n 个任务来启动一次调度任务，相类似QoS需求的用户可归集为一组任务集合作为一次调度任务。本文使用以下定义［3，4］：

定义1 用T ＝｛t1，t2，…，tn｝表示一个任务集合，单位时间内该任务集合中等待被调度的任务数为n。

定义2 用N ＝｛n1，n2，…，nm｝表示云存储系统中的节点集合，角标代表节点数量。Ni代表ni节点上的数据资源，特别要指出的是相对于云计算中节点一定能执行计算任务，而云存储系统的节点有可能不能提供用户所请求的数据。

定义3 用V ＝｛v1，v2，…，vn｝表示任务调度向量，即云存储调度方案。角标代表任务长度，n表示任务总数为n，vi表示第i个任务的数据在vi节点上取得。

定义4 用Fv 代表任务调度方案的调度向量函数。它是调度算法的数学模型，不同调度算法的根本区别就在于调度向量函数的不同。

2 多QoS约束下的限制解空间PSO 云存储任务调度算法

2.1 标准PSO 算法及限制PSO 解空间的云存储调度算法

粒子群优化 （particle swarm optimization，PSO），又称微粒群算法，PSO 算法模拟了一个简化的社会模型，而该社会模型是基于群体的，群体中的个体可根据自己以及群体中的最优值来判断进而调整自己或者全局的最优值，实现自适应的优化。PSO 算法中群体被抽象为D 维空间中没有体积及质量的粒子集合［4］。个体粒子中第i个粒子表示为Xi＝（xi1，xi2，…，xiD），通过适应度函数得到该粒子的适应值 （fitness value），粒子在飞行过程中得到的最优位置记为Pi＝（pi1，pi2，…，piD），也称为个体极值pbest，作为个体粒子的飞行经验。群体中所有粒子共同发现的最好位置用符号g 表示，即Pg，也称为全局极值gbest。个体粒子通过自己的飞行经验极值pbest以及全局的飞行经验gbest来更新自己的飞行速度以及位置。粒子i的速度用Vi＝（vi1，vi2，…，viD）表示，对于每一次迭代，它的第d维（1≤d ≤D）以式 （1）、式 （2）更新

其中：w 为惯性权重（inertia weight），代表粒子的惯性行为，w 越大全局寻优能力越强，但局部寻优能力降低，w 越小则相反。c1和c2为加速常量（acceleration constants），分别代表粒子个体自己的认知和对群体经验的学习能力。Rand（）和Rand（）为两个随机值，其取值范围在［0，1］中变化［5］。

标准PSO 算法在应用到云存储环境中时，由于云计算任务可由云中任意节点提供但云存储中的节点会出现节点没有任务所需要的数据的情况，并且在云存储中这种情况应该作为常态处理，而PSO 算法初始化参数的随机产生和每一轮的更新都没有考虑到云存储的这一特性，所以标准PSO 算法会出现对云存储任务无效的解，且这种无效解的随机性较大。

限制PSO 解空间的云存储调度算法引入了存在矩阵的概念［6］。EM 是一个n＊m 的矩阵，n表示调度任务，m 表示云存储系统中的节点数目。矩阵中的元素代表了该任务是否存在，例如元素eij代表任务i 所需的数据节点是否在j上，0和1分别代表无和有。云存储中的资源列表用于生成该存在矩阵。资源列表是云存储节点与数据块的映射表。由于云系统中对数据安全以及冗余的需求，同样的一块数据会存在于多个而并非全部的云存储节点上，所以矩阵中的调度任务向量ni的行中会出现多个1的情况。

其改进在于：

（1）PSO 的初始化的解是由存在矩阵产生，而非传统PSO 算法的随机产生，这样保证了初始化解的有效性。

（2）PSO 算法会根据式 （1）、式 （2）进行迭代，每次迭代的结果会根据存在矩阵进行对迭代解的检测，判断其是否符合存在矩阵，如果不符合则产生一个新的解，并且满足存在矩阵的限制条件。

（3）如果算法陷入了局部的最优解时，传统算法会随机产生新的解，但这个解的有效性是未知的，而该算法会在存在矩阵中产生新的解，保证其解的有效性。

2.2 多QoS约束下的限制解空间PSO 云存储任务调度算法

存在矩阵解决了PSO 的初始化解不再随机产生，而是根据资源列表生成存在矩阵。同时在迭代的过程中也会在存在矩阵中进行验证，防止了无效解的产生。但是由于其未考虑到网络状态的变化，所以其不能通过网络状态的实时更新从而根据当前网络状态得到最优值。

通过多QoS参数作为当前网络状态的度量定义QN 是一个n＊n 的矩阵，n 表示云存储系统中的节点数目，Qij代表节点i到节点j 的QoS状态信息，包括带宽、时延、抖动的信息。

2.2.1 QoS参数的应用

本文研究的重点放在多QoS约束下的根据不同用户或应用场景对多QoS敏感度不同，符合用户或应用场景需求的最小代价选路问题［8，9］。云存储网络节点的集合可以建模为一个无向加权图G（V，E），其中V 是代表所有云存储的节点。E是物理上或者逻辑上代表链接节点的所有的边。每一组链路有三组权重BandWith、Delay、Jetter分别对应可用带宽，延迟和抖动。

路径P（s，d）为任务节点以及数据节点之间的链路，且节点之间有多条链路可以到达，M ∈V 代表云存储节点与任务节点间最短路径的节点集合，一条链路上的总时延取P（s，d）链路上所有经过路径的链路时延之和［10，11］

在QoS向量中链路P（s，d）上的总时延定义为从路径上起点到终点上的最小值

树的抖动定义为从源节点到终节点路径上延迟的平均值差值

式中：delay＿avg——从源节点到终节点的延迟的平均值。

链路的瓶颈带宽被定义为T 中链路的最小带宽

链路的开销被定义为该链路上边的开销之和。CostT（s，M）引用参考STP协议中1Gbit／s的宽带链路的STP开销与bandwidth之间的关系进行设定。

带延迟带宽约束的QoS选路问题可以被描述如下：已给定的网络图G，一个源任务节点s，云存储节点到任务节点链路节点集合M，延迟，抖动延迟和带宽约束分别为Dmax，Dj和Dmin。 并通过 DelayP（s，d）、JitterP（s，M）、BandwidthP（s，M）并且符合以下条件：

（1）链路P（s，d）为任务节点到数据节点的最短路径；

（2）云存储任务的请求源节点是S；

（3）所有的数据节点都在云存储节点V 中，且受存在矩阵约束；

（4）数据源树必须满足以下的多QoS约束：

端到端的延迟要求

抖动延迟约束

给QoS保证的带宽

2.2.2 适应度函数

PSO 的每一次迭代都会被评估计算。在QoS调度问题上每一次迭代被一个适应度函数所驱动，这个适应度函数根据粒子对减少链路的花费来评估粒子进化的质量［11］。适应度函数的定义如下

式中：k1和k2——惩罚系数，惩罚系数的值决定了惩罚程度。

多QoS约束下的存在矩阵的PSO 调度算法如下：

（1）设置迭代的次数Li＝0，由存在矩阵代替随机的初始解生成V0；

（2）While Li≤MaxLi；

（4）由适应度函数f（P（s，M））得到fi；

（5）当适应度函数fi未到达阀值时，break，输出Vi；

（6）Li＝Li＋1；

（7）根据PSO 算法得到迭代一轮后的Vnew；

（8）将Vnew与存在矩阵做匹配，如果不匹配则重新生成Vnew；

（9）将得到的数据节点与多QoS矩阵做对比，对要求的Dmax，Dj和Dmin做匹配，如果不满足用户所提出的QoS限制则按重新生成Vnew，如果连续10次没有生成满足条件的Vnew，则使用第十次生成的Vnew；

（10）End While

3 实验和分析

3.1 实验环境和实验参数

由于网络环境的不同对实验结果的影响比较大，而又要兼顾与现有调度算法的比较，所以采取了将网络拓扑的节点分别设置为10，20，40，80，160.存在矩阵实时的分配产生。网络环境的设置如下：各链路的带宽在 ［100，1000］之间随机分布，单位为兆 （M）。延迟在 ［0，5］之间随机分布，单位为毫秒 （ms）。

实验默认的最大迭代次数为100 次，调度向量中含有10个任务。为得到一般性实验结果，对于以上每种网络大小环境的测试数为10次，所需记录的实验数据有 “运行时间”与 “QoS满足率”，“运行时间”能够直观表达算法之间的性能差异， “多QoS满足率”表示了算法在多QoS约束下的优化程度，以上数据均取得10次测试的平均值。

3.2 实验结果分析

图1分别代表了限制PSO 解空间的云存储调度算法、多QoS约束下的限制解空间PSO 云存储任务调度算法在相同实验环境下的实验结果。表1、表2为运行参数。从表中实验数据可以看到多QoS约束下的限制解空间PSO 云存储任务调度算法，在运行时间上与前者算法近似，这是因为虽然后者算法在QoS保障上较优，但在迭代过程中，当得不到满足多QoS 约束的条件时，会重新计算得到新的Vnew，虽然不能超过10次重新计算的限制，但仍然增加了算法在运行时间上的开销，从而使得算法在运行时间上没有特别大的优势。而在QoS的满足率方面，其优势就较为明显。在多QoS约束条件Dmax＝20，Dj＝10，Costmax＝40下，限制解空间PSO 算法在迭代过程中随着节点数目的增多，网络情况复杂程度增加，多QoS满足率下降的较为明显，当节点数目增至160 时，仅有26%符合QoS的要求，QoS平均满足率为33%。而在多QoS约束下的迭代由于考虑到了每一轮迭代的结果均要满足多QoS的需求，所以结果相对于需求值不会有太大的偏离，当节点数目到达160时多QoS 的满足率能够达到38%，QoS 平均满足率为45.6%。通过图1对两组数据的对比，直观展现了二者之间QoS满足率之间的对比。因此，虽然在运行时间和执行次数上两者之间差距不大，但是多QoS优化算法在试行中有更好的满足率，更能够体现网络的实际状况，从而满足不同用户及应用对于网络的不同需求，提高用户直观的网络服务质量。

图1 QoS满足率的比较

表1 限制解空间PSO 算法

表2 多QoS约束下的限制解空间PSO 云存储任务调度算法

4 结束语

本文对云存储任务调度算法进行了研究，探讨了PSO调度算法在云存储系统调度中的问题，同时引入了前人针对云存储系统的改进，即任务和资源节点的关系矩阵：存在矩阵。通过存在矩阵的引入，排除了对于云存储任务无效的解，PSO 算法的迭代次数以及运行时间效率有了极大的提高，但这种提高是在理想的网络环境中所得到的值，在真实网络环境中，用户对于所需的云存储资源有不同的需求，通过QoS的约束，使得算法所产生的解更趋向于用户对于资源的QoS需求，仿真结果表明，在本文所提出的QoS需求下，QoS满足率有了明显的提高。

下一步研究方向在于抽象出云存储节点资源分布的特性，结合多QoS的特性进行更进一步的改进，使得算法在达到最优解的收敛时间以及QoS的满足率上有更进一步的提高。

［1］FENG Guofu，LI Wenzhong，ZHANG Jincheng，et al.Replica distribution for search size minimization in unstructured overlay ［J］.Chinese Journal of Computers，2011，34 （4）：628－635 （in Chinese）.［冯国富，李文忠，张金城，等.无结构覆盖网络中面向搜索范围最小化的副本分布 ［J］.计算机学报，2011，34 （4）：628－635.］

［2］Lin G，Dasmalchi G，Zhu J.Cloud computing and IT as a service：Opportunities and challenges ［C］／／IEEE International Conference on Web Services.IEEE，2008.

［3］JIN J，Rothrock L，Mcdermott PL.Using the analytic hierarchy process to examine judgment consistency in a complex multiattribute task ［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2010，40 （5）：1105－1115.

［4］LEI Binghan，HE Jun，HE Xiang，et al.Grid load schedule algorithm based on QoS［J］.Computer Engineering，2009，35 （24）：96－98（in Chinese）.［雷炳翰，何军，何翔，等.基于QoS的网格负载调度算法［J］.计算机工程，2009，35 （24）：96－98.］

［5］Pedersen MEH，Chipperfield AJ.Simplifying particle swarm optimization ［J］.Applied Soft Computing，2010，10 （2）：618－628.

［6］WANG Juan，LI Fei，ZHANG Luqiao.Task scheduling algorithm in cloud storage system using PSO with limited solution domain ［J］.Application Research of Computers，2013，30（1）：127－129 （in Chinese）.［王娟，李飞，张路桥.限制解空间的PSO 云存储任务调度算法 ［J］.计算机应用研究，2013，30 （1）：127－129.］

［7］Wang H，Meng X，Li S.A tree－based particle swarm optimization for multicast routing ［J］.Computer Networks，2010，54 （15）：2775－2786.

［8］Lin N，Yang T，Song L.A new QoS multicast routing algorithm for MPLS－TE ［C］／／International Conference on Measuring Technology and Mechatronics Automation.IEEE，2010：192－195.

［9］Yang P，Huang B.GA based QoS multicast routing algorithm in mobile ad hoc network［C］／／International Seminar on Future Bio－Medical Information Engineering.IEEE，2008：247－250.

［10］Li X，Ning Q，Jun－Ya Z.An improved GA for QoS multicast routing algorithm ［C］／／Control and Decision Conferenc.IEEE，2008：393－396.

［11］Xi－hong C，Shao－wei L，Jiao G.Study on QoS multicast routing based on ACO－PSO algorithm ［C］／／International Conference on Intelligent Computation Technology and Automation.IEEE，2010：534－537.