LSBPSO 算法在磁盘负载均衡问题中的应用

计算机工程ComputerEngineering•人工智能及识别技术• 文章编号：1000—3428(2009)04—0201—03文献标识码：A 中图分类号：TP301.6LSBPSO算法在磁盘负载均衡问题中的应用葛洪伟，宋超(江南大学信息工程学院，无锡214122)摘要：将基于水平集的粒子优化算法(LSBPSO)应用于磁盘负载均衡问题中，利用LSBPSO的快速收敛性动态调整分条技术下逻辑磁盘和物理磁盘的映射关系。提出一种新的逻辑磁盘热度预测方法，对物理磁盘的热度的表示方法进行扩充。实验表明，LBPSO能较好地解决分条技术下的磁盘负载问题，收敛速度较快。关键词：粒子群优化算法；磁盘负载；分条技术ApplicationofLSBPSOinDiskLoadBalanceProblemGEHong-wei,SONGChao(SchoolofInformationEngineering,SouthernYangtzeUniversity,Wuxi214122)【Abstract】ThispaperusesLevel-Set-BasedParticleSwarmOptimizion(LSBPSO)tosolvetheproblemofdiskloadbalance.Thecharacteristicofconvergenceofthealgorithmswiftlyadjuststhemappingbetweenlogicdiskandphysicdiskwhichusesthetechniqueofdiskstriping.Itrefersanewmethodtoforecastthehotoflogicdiskandaddsthecontentofexpressionofhotofphysicdisk.Simulationshowsthatthealgorithmisefficientanddefective.【Keywords】ParticleSwarmOptimization(PSO);diskload;techniqueofdiskstriping1概述 速地映射到物理磁盘，使每个物理磁盘的热度相当(物理磁盘当今社会对信息的需求越来越多，围绕信息存储和分配产生的问题随之增多，其中以磁盘负载均衡问题尤为突出。如何使信息均衡地分布在各个物理磁盘上从而更大程度地发挥每个磁盘的效能成为目前的一大研究热点。文献［1-3］利用遗传算法解决磁盘负载问题，但由于遗传算法本身所具有的缺点：优化能力与初始解有关，容易出现停滞甚至倒退现象，收敛性能差，因此局限了遗传算法的发挥。粒子群优化算法(ParticleSwarmOptimization,PSO)作为人工智能的经典算法，凭借收敛速度快、参数设置少等优点，已被应用于很多领域。本文将基于水平集的粒子群优化算法(Level-Set-BasedParticleSwarmOptimizion,LSBPSO)应用到磁盘负载均衡中，特别是基于分条技术的磁盘负载中，实验证明，与遗传算法相比，该算法在解决磁盘负载问题的运行时间以及收敛速度方面具有一定的优势。磁盘负载均衡磁盘负载均衡问题负载均衡是一种以扩展现有设备和服务器带宽增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性的技术。磁盘负载均衡是一类以提高磁盘的利用率，使每个磁盘充分发挥性能的技术和方法。磁盘分条技术磁盘分条也称为磁盘交叉，是将多个磁盘地址空间合成一个在主机看来是单独、统一的空间，其实现主要通过一种循环的方法在磁盘上分配连续的逻辑磁盘数据单元(称为分条单元)。分条技术下磁盘负载均衡需要解决的问题目前，负载均衡主要存在以下3个问题：(1)如何对每个逻辑磁盘的热度进行预测。(2)根据某一算法使各逻辑磁盘快的热度由映射到其上的逻辑磁盘热度相加得到)。(3)如何合理地安排每个物理磁盘中逻辑磁盘的映射位置，充分发挥系统的性能(对于同一个物理磁盘，离磁盘轴心越近的部分，其数据传输率越高)。其中，问题(1)、问题(2)是磁盘负载均衡的关键也是本文研究的内容。对于问题(3)，文献［4］已经给出了一个较好的解决方案。磁盘阵列热度表示逻辑磁盘热度表示逻辑磁盘的热度往往包括可预测热度和不可预测热度。文献［2］利用最佳时间跨度T提岀了一种逻辑磁盘热度和物理磁盘热度的动态表示方式。本文利用文件管理中常用的建立时间戳的方法对逻辑磁盘的热度进行估计。设逻辑磁盘有M个，物理磁盘有N个，LH,ie［1,M］表示第i个逻辑磁盘的热度，通过下式对LH在时刻t进行预测：LHt(t)=(1-d)x 1 +dxLHi-1) (1)kxSk=11(vi+1-vi)其中，LH(t-1)表示LH,在t-1时刻即当前的热度值；k表示时间戳的长度；1xU=1(Vi+1-Vi)表示在时间段k内访问逻k辑磁盘LH：的时间间隔的平均长度；de［0,1］。由式(1)可以看岀，对LHt的预测与一个时间段内访问它的次数有关，也与当前LH有关，而k和d可由实验得到。物理磁盘热度表示文献［2-3］把物理磁盘热度看成是映射到它的逻辑磁盘热作者简介：葛洪伟(1967-)，男,畐燉授，主研方向：人工智能与模式识别，图像处理，嵌入式系统；宋超，硕士研究生收稿日期：2008-07-21E-mail:songchao1983512@163.com度之和，假设把逻辑磁盘/到逻辑磁盘k映射物理磁盘/,则物理磁盘i的热度表示为TOC\o"1-5"\h\zPHi=ZLHj ⑵为式(2)乘上系数，则时刻/物理磁盘的热度可表示为N/M1PHi(t)=(ZLH(i」)+j(t))x ⑶jT CiPi其中，ie[1,N]；C表示磁盘P的容量；Pi的值与磁盘Pi的本身的I/O和处理能力有关，不同磁盘对应的处理和负载能力是不同的。这样表示物理磁盘热度更加合理。模型的建立根据2.3节中的问题(2)建立如下的模型：设有逻辑磁盘M个，物理磁盘N个，t时刻逻辑磁盘的预测值为LH；(t),ie[1,M]物理磁盘的预测值为PH(t),1Nie[1,N]，PH(t)=-ZPH(t)，则找出一种物理磁盘和逻辑Ni磁盘的映射关系，使各个物理磁盘热度的方差最小：1Nb(t)=后¥PH,(t)-PH(t))2 (4)LSBPSO算法本文的LSBPSO是对原PSO算法的一种改进，通过引进选择机制和变异过程，简化了进化过程。算法过程如下：初始化种群X={X”X2，,X„}。计算种群中各个个体的适应度。利用水平集选出进化粒子。计算各粒子适应度的均值：7=Z也，并将高于均值和低于均值的个体分成2类：i=1nXa,Xb，显然每一代的最佳值X*eX。。在高于均值的个体Xa中继续计算适应度的均值，又把X。中个体分成2类：X。,X，显然，X*eX。。X。-X*中的个体以及在X-X*中以轮盘法选择岀的个体共同组成了一个有n-1个粒子的种群。对选出的粒子按照以下方程进化：xikd+1=rxxikd+Pxrand()x(pgd-xikd) (5)变异。以解空间的中点为界，分别计算进化之后粒子的分布情况，随机选择粒子，根据中点左右两侧的粒子分布状况，对选择的粒子进行变异，若左侧粒子密度大，则往右侧变异，否则，往左侧变异。进化后的粒子以及最优的粒子组成新的一代。如果达到进化代数，则退出；否则，转(1)。标准PSO与LSBPSO关于SphereModel函数的对比实验结果如图1所示。实验表明，LSBPSO在收敛速度上有很大的优势，本文把此算法应用于实时性高的磁盘负载问题中。5基于LSBPSO的磁盘均衡实现5.1编码表示PSO算法求解最优化问题时最常用的编码是实数编码,但由于本文所提问题的特殊性，因此采用向量编码，即设有M个物理磁盘，N个逻辑磁盘(M/N=k,keZ)，LSBPSO中每一个粒子的初始位置对应一个解向量：(x1,x2,L,xM,xM+1,L,x2M,x2M+1,L,x(k-1)M,x(k-1)M+1,L,xN)其中，x,ie[1,M]表示逻辑磁盘号。例如有2个物理磁盘、4个逻辑磁盘，初始解向量为(1,3,4,2)，表明映射到物理磁盘1号的是逻辑磁盘1号、3号，而映射到物理磁盘2号的是逻辑磁盘4号、2号。这样根据解向量排序的不同，可以得到关于物理磁盘和逻辑磁盘的不同映射。选择策略选择策略是保留每一代中适应度最优的1/4，剩下的3/4的个体利用“轮盘法”策略从上一代中选择得到，使适应度小的个体也有被选到的可能，从而加快整个算法的收敛速度。进化过程由于本问题是一个一对多的组合优化问题，，利用式(5)对粒子进行进化显然不符合题意，因此需要通过以下步骤得到下一代粒子：(1)取整x，=\_rxx^d_|+|_P"⑹d()x(Pgd-X爲)_|(6)(2)规范化x"=入一xmin(maxmin1)+1(7)xmax-xmin其中，x=(x1,x；,…,x；,…,xN)；xmax=max&,x；,…,xi,…,xN)；Xmin=min(x1,x；,…,x；,…,Xn)；max,min分别为解向量的最大值、最小值。(3)去除非法解按顺序从小到大根据逻辑磁盘号对向量x”进行扫描，保留X”中第1次与逻辑磁盘号相同的数字和与其对应的位置，X”中剩余的部分置为0。统计扫描过后逻辑盘号在X”中没有的号码，把这些号码随机放入X”中置为0的位上，由此得到合法解。例如，经过上面2步有x"=(1,3,3,225)，经过逻辑磁盘的扫描有x”=(13,0,2,0,5)，对应的逻辑磁盘4,6没有分配。这时统计各物理磁盘热度，根据热度按概率P分配逻辑磁盘。未分配逻辑磁盘1„被物理磁盘Pm选中的概率为PQ,J)=泸P”)〜"心Zhot(Pi)血心1其中，hot(*)表示磁盘热度。由此得xk+1=(1,3,4,2,6,5)，由此得到了下一代。变异策略完成对某一粒子的进化后，随机选取粒子中的2个位置la,lb，计算两者所对应的逻辑磁盘的热度LH,。,LHlb以及la,lb分别属于的物理磁盘的热度PHla,PHlb。如果LHia<LHbPHla<PHlb或Hla>LHbPHla>PHlb，则交换la,lb所对应的逻辑磁盘号J。,L»。这种变异不会产生非法解。适应函数适应函数是评价每个进化粒子适应度的依据，可采用每个物理磁盘热度的统计方差b(t)作为算法的适应函数。6实验与分析为了验证新算法处理磁盘负载问题的效能，进行了仿真实验。实验平台为：CPU为IntelP42.6GHz;内存为256MB;操作系统为WindowsXP;在Matlab7.0平台上进行。6.1LSBPSO的收敛性为了检验LSBPSO算法的收敛性，使用表1所示的实验数据，将LSBPSO与文献［1-2啲遗传算法进行比较，其结果如表2所示。表1各逻辑磁盘及相应的热度值逻辑磁盘号磁盘热度逻辑磁盘号磁盘热度11.23133.9022.10142.1031.13151.1344.30163.8153.02173.2262.41182.0274.82194.7184.24203.3493.51212.40105.01224.23113.22233.22122.35241.13表2LSBPSO与遗传算法的收敛性比较算法5代10代20代40代文献［1］的算法0.43740.43740.43740.2509文献［2］的算法0.40350.40350.20770.2077LSBPSO0.05280.02580.02580.0130实验要求把24个逻辑磁盘根据热度分配给6个物理磁盘。对3种算法均初始化50个粒子。虽然遗传算法采取进化后保优策略可以保证收敛到最优［5］，但文献［1-2］分别运用了循环交叉和矩阵交叉的方法，这2种交叉对父代的修改幅度较大，算法一开始类似于一种盲目搜索，不容易快速收敛甚至岀现了停滞的现象，而LSBPSO在运行了10代后，热度方差b(t)比前2种算法小得多，显示岀快速收敛性。LSBPSO的实时性磁盘负载问题对实时性要求很高，CPU运行时间的长短是衡量算法实时性的标志。由于文献［3］的遗传算法是文献［1-2］算法的总结和改进，因此本文仅对比了文献［3］的算法与LSBPSO。选取20个、40个、60个、80个和100个逻辑磁盘以及5个物理磁盘，在［0,5］中随机产生各逻辑磁盘的热度,初始化50个粒子，通过大量实验,统计获取符合b(t)<0.5解的CPU运行时间，比较结果如图2所示。由图2可以看岀，当逻辑磁盘较少时，LSBPSO的效率和实时性较高，而随着逻辑磁盘数的增加，LSBPSO所用CPU运行时间的增加量变得越来越多，算法速度优势降低。这可能与粒子群算法在离散过程中由进化方程所产生的冗余解［6］随逻辑磁盘数的增加(上接第200页)方法相比，人脸机器识别更加友好、直接，因此，具有广泛的应用前景。下一步的研究重点是在人脸识别效率上做进一步改进。参考文献LeeDD,SeungHS.LearningthePartsofObjectsbyNon-negativeMatrixFactorization[J].Nature,1999,401(10):788-791.LiStanZ,HouXinwen,ZhangHongjian,etal.LearningSpatiallyLocalized,Part-basedRepresentation[C]//Proc.ofIEEEConf.onComputerVisionandPatternRecognition.Hawaii,USA:[s.n.],2001.FengTao,LiStanZ,ShumHeung-Yeung,etal.LocalNon-negativeMatrixFactorizationasaVisualRepresentation[C]//Proc.ofthe2nd而增加有关，处理这些冗余解必然要花去大量的CPU运行时间。此外，变异算子单一也是原因之一。如何较好地解决这个问题是今后的研究方向。7结束语本文把LSBPSO算法应用到磁盘负载均衡中，在逻辑磁盘的热度预测中利用文件管理中的预测方法，在物理磁盘热度的表示中增加了物理磁盘本身的特性，建立了优化模型。在算法实现过程中针对本问题的特殊性提岀了一种向量编码，利用变异算子提高算法寻优能力。实验证明，本算法效能优于遗传算法，但如何进一步提高算法的效能，特别是在逻辑磁盘增多时，是下一步要研究的问题。参考文献［1］ ZomayaAY,MemberS,YeeHI.TheObservationsonUsingGeneticAlgorithmsforDynamicLoadBalancing［J］.IEEETransitionsonParallelandDistributiveSystems,2001,12(9):899-911.［2］ 董欢庆,李战怀.基于遗传算法的RAID磁盘阵列中磁盘负载均衡方法［J］.计算机工程与应用,2003,39(16):41-43.［3］ 倪云竹,吕光宏,黄彦辉.用遗传算法解决基于分条技术的磁盘负载均衡问题［J］.计算机学报,2006,29(11):1995-2001.［4］ 谢长生,刘艳,李怀阳,等.基于分条单元热度的RAID数据分布优化［J］.计算机科学,2006,33(