• 微信
  • 抖音

基于BPSO-IRS算法的智能值守机器人资源调度方法研究论文

理工论文 7℃ 0
SCI发表中的作者贡献度评估与署名规则

  关键词:机器人,配电站运维,云调度

  0引言

基于BPSO-IRS算法的智能值守机器人资源调度方法研究论文

  随着中国发展速度的不断增长,城市工业化程度不断提升,对中国电力建设提出了更高的要求。近些年中国电力工业的极速扩张,尤其是电网规模的快速扩张,带动了中国基础电力设备的发展与应用。其中中置式开关柜在远距离高压输送电与高压设备工厂中是不可缺少的电器元件,由于其工作工况多为高压、通流、密闭环境状态,很容易产生高温、损坏,造成严重的后果。截止到2019年,全国国家电网系统中正在运营的中置式开关柜大约为900 000面,且每年正在以7.8%的速率进行增长[1]。而在近些年的电力设备检测中,10 kV的高压开关柜由于发热而导致的故障问题就占据了42.3%[2],这些故障对于用电安全和稳定造成了严重的影响,每一次大规模的停电问题都会造成严重的经济损失。

  配电站数量庞大且地域分布广泛,云机器人可以解决在空间距离较远但执行标准统一的配电站运维操作。云计算[3]首先在Google在2006年搜索引擎会议中首次提出,它融合了传统计算机与网络技术,能够实现物理硬件资源虚拟化、负载均匀化、分布式存储和并行计算的功能。云机器人是由James Kuffner教授[4]首次提出,他将云计算与传统的机器人控制相结合,将机器人的控制数据传入到云端,在云端服务器进行计算从而实现远距离的数据处理与指令传输。借助云端强大计算能力为机器人进行统一的服务,不仅可以降低机器人成本,同时还有助于机器人之间的数据共享,实现知识复用提高工作效率。

  为满足云机器需求,在云端需要创建服务类虚拟机(简称RVM),同时需要选择合适的物理机(简称PM)来初始放置。本文主要研究云端RVM创建时的资源调度问题,即如何在RVM创建时在PM上进行合理的放置,包括初始放置和增量放置。以优化系统负载均衡、各类资源利用率均衡以系统能耗为目标。针对问题并进行建模然后提出了BPSO-IRS调度算法来对问题进行求解,最后设计仿真实验,对比OpenStack原生的LFF调度算法,对BPSO-IRS算法有效性进行验证。

  1工作环境及云机器人资源调度

  配电站数量众多且彼此之间相互独立,工作场景大多数位于室内,如图1所示。同时配电站拥有规范的操作要求,任何检修操作都有着明确的作业票规定,这些为机器人代替人工完成检修降低了难度。目前在电网智能配电站建设中,已经采用机器人代替人工完成部分巡视工作。

  虚拟机调度优化目标主要包括提高SLA服务质量、物理机资源利用率,实现物理负载均衡以及降低系统能耗等[5]。调度算法主要包括传统优化算法、基于启发式算法及其变种或者混合的优化算法[6]。Dong等[7]描述了一种基于有限物理资源的虚拟机调度策略,其目的是减少活动主机的数量,虚拟机调度策略被抽象为装箱问题;Xi[8]通过启发式算法解决线性规划问题来处理虚拟机资源调度问题,显著降低服务器电源消耗;Verm[9]提出了启发式装箱算法解决动态虚拟机调度问题,但是该算法在某些方面无法满足SLA要求;高永强等[10]采用多目标蚁群算法作用于多目标任务流,提高了虚拟机资源调度过程中物理机资源利用率,但没有考虑负载均衡的问题。

  2资源调度分析与数学模型搭建
       2.1资源调度问题

  配电站值守机器人面向对象为在大区域配电站多个机器人之间的运维操作,在机器人请求运维要求后,在云端为机器人创建服务实例,在服务完成后,需要将实例删除,以免在待机状态下造成资源浪费。此外,考虑到存在多个配电站机器人在进行巡检任务的同时,有些机器人需要开展计划性开关操作任务的情形,要求云机器人系统在云端已存在多RVM实例的情况下根据某机器人服务请求增量创建RVM。与初始创建RVM进行放置相同,增量创建放置也需要进行合理调度,避免某物理机出现过载导致云端实例大规模迁移,造成系统的不稳定。如何在RVM创建时对资源进行合理的调度,将RVM合理的分配在PM上,实现RVM与PM之间最优映射,对服务器资源负载均衡,资源利用率均衡以及降低能耗有重要意义。

  RVM创建时放置过程类似于将多个球放置在不同容纳盒。每台PM为盒子而RVM为球体。既不能将所有小球都放在一个盒子里,也不能完全平均分配,造成资源的浪费。无论是RVM初始化创建还是增量创建,都需要根据合理的调度算法进行放置,调度算法需要考虑的因素有很多,如系统的负载均衡、资源利用率、能耗等。

  2.2 OpenStack框架调度算法

  OpenStack[11]框架有自身的虚拟机调度算法,由No‐va-schedule实现虚拟机的放置,分为两个主要步骤:过滤和称重。过滤指将一些硬件标准如CPU使用率、磁盘使用量、内存等要素进行评比,将不满足标准的主机进行淘汰;称重指对过滤之后满足要求的主机对内存剩余量机型权重计算,并将计算之后的结果进行排序,将新增的RVM放置到权重最小的PM中。

  OpenStack自带的虚拟机调度策略虽然可以满足实际的使用需求,但是考虑因素单一,剩余的内存越多越容易成为虚拟机放置的对象,很容易造成其他资源的浪费,因此需要对调度算法中的权重模型进行重新设计。

  2.3模型搭建

  2.3.1系统均衡负载模型

  对于云端PM服务器,每个服务器之间的资源使用率越相近,代表服务器集群负载越均衡,系统更加稳定。将每个PM上的各种资源按照一定的权重进行相加,用来表示每个PM服务器的负载,然后求取所有PM负载的标准差用来表示集群负载的均衡。将PM负载标准差减小则系统整体的均衡性越强。

  每一个PM资源包含CPU、内存、带宽以及磁盘,而磁盘现在的计算机都很充足,因此模型对前3个资源使用情况进行模型构建,数学表达式为:

  式中:Rj为j号PM上各类资源消耗的总和;w、w、w分别为j号PM上对应CPU消耗、内存消耗、带宽消耗相对于总消耗的权重系数,权重系数的大小根据PM上该类资源消耗程度的不同而定,比如CPU使用率高则相应的权重系数较大,在调度算法中可以调整该值的大小;指所有PM资源消耗的总和的平均值;Rb即模型结果,PM集群负载的标准差,表示系统负载均衡情况。

  2.3.2资源利用率均衡模型

  实际的使用情况一台PM机器中可能会存在CPU使用率接近满载,但内存使用率将近过半的情况,为了保证每台PM上的各类资源使用率保持均衡,避免出现木桶效应。本模型初步考虑将CPU与内存使用率纳入模型考虑范畴。为了方便计算,将单台PM资源利用率均衡指数用如下所示:

  式中:u、u分别为j号PM对应的CPU和内存利用率;uj为二者的平均值。利用数学均值定理求取该PM的资源利用率均衡指数ubj,表示只有当CPU利用率资源利用率u与内存利用率u相等时,资源均衡指数取得最小值1,否则资源均衡指数越大,即两类资源利用率相差越大,说明该PM资源消耗不均衡。将所有PM的资源利用率均衡指数相加取平均,即可得到集群资源利用率均衡模型:

  式中:即模型结果,资源利用率均衡指数,表示服务器集群CPU和内存利用率均衡情况。

  2.3.3系统能耗模型

  根据研究表明,PM能耗与CPU使用率正相关且相关性最高。使用CPU使用率来做PM耗能的增长系数,所以可以得到每台PM的能耗公式:

  式中:pj为j号PM的能耗功率;pmax为该PM满载时的峰值功率,pmin为休眠时的功率,两者可以从服务器供应商提供的产品手册获得;u为该PM的CPU利用率。

  由于pmin通常为pmax的70%,故式(4)可以化pj=(0.3×u+0.7)pmax。

  求实际能耗功率pj与峰值能耗功率pmax的比值,即可表示每台PM的能耗情况,然后求出每台PM的能耗情况并相加取平均得到集群总体能耗模型:

  式中:即模型结果,系统能消指数,表示服务器集群能源消耗情况。

  3 BPSO-IRS算法介绍与资源调度流程

  在2.3节中提出了负载均衡模型、资源利用率均衡模型以及能源消耗模型3大优化目标,针对不同的优化目标有不同的数学模型。结合3种模型实现每个RVM在PM集群上合理的映射,目标函数为:

  minf=k 1×Rb+k2×b+k3×(6)

  式中:k 1、k2、k3分别为每个优化目标的权重系数,三者和为1。根据不同场景调整不同的权重系数。

  本文结合初始放置与增量放置问题,提出了BPSO-IRS算法解决RVM分配问题。分配流程如图2所示。

  针对不同方式的放置情况,采用不同的放置调度算法进行求解。

  对于初始放置情况提出了基于粒子群算法——BPSO[11](Binary-PSO)的放置调度算法;增量放置情形,提出了基于IRS[12](Incremental Resource Scheduling)的放置调度算法。由于不同放置情形下PM集群可用资源消耗情况不同,所以在不同算法执行过程中,需要选择合适的目标函数进行优化。

  3.1基于BPSO的RVM初始放置调度算法

  3.1.1 BPOS算法

  RAM资源分配问题属于多项式非确定性问题,使用传统的求解策略耗费时间长、求解结果准确度差。近些年利用启发式算法解决解决NP难题越来越成熟,常见的启发式算法包括遗传算法(GA)[13]、蚁群算法(ACO)[14]、模拟退火算法(SAA)[15]、粒子群算法(PSO)[16]等,其中粒子群算法相较于其他的算法原理简单、容易实现且控制参数较少,因此对于计算机硬件要求较低,符合本文中的项目需求。

  由于本文采用多约束条件优化目标的方式,所以先对RVM在PM中的放置问题进行数学描述表达。设定共有n个RVM,m个PM,xij代表编号为i的RVM与编号为j的PM之间的映射,当xij=1时表示该i号RVM与j号PM映射成功,xij=0时表示映射不成功。所有RVM与PM之间的全部可能映射可表示为:

  用19、17m、19、1分别表示编号为/的RVM的CPU、内存、磁盘和带宽;用p严、p”、pj、p分别表示PM的CPU、内存、磁盘和带宽。约束条件为每个RVM只能映射一个PM,同时PM上所有RVM的资源消耗不能超过PM所包含的资源量。

  由于映射矩阵X中均为0或者1,所以在借鉴遗传算法时,显然标准的粒子群算法无法满足需求。因此需要借鉴遗传法采用二进制编码种群的思想,采用基于标准粒子群算法的改进算法BPSO算法。

  在BPSO算法中,每个粒子的位置矩阵都采用二进制进行表示,算法每次迭代更新就是对每个值进行0、1变换来实现粒子迭代的运动,粒子的速度则表示迭代中对粒子位置变换的概率。在BPSO算法中,每次迭代过程都需要将单个粒子的位置代入根据优化目标函数得到的适应度函数中得到对应位置的适应度值,记录每次迭代过后粒子个体历史最优适应度值对应的位置P。,以及粒子群整体中最大适应度值对应的位置Pw,通过P和Pw来综合计算每次迭代过程中需要更新的速度。因此得到BPSO算法的速度公式:

  式中:v。为粒子速度;r和r₂均为[0,1]范围内的随机数;x为粒子当前位置。

  在BPSO算法中,速度表示为位置更新的概率,所以需要将速度限制在0,1]范围内,因此需要是用神经网络中的Sigmoid激活函数进来实现速度实数到指定区间的映射,如下式所示:

  这样就可以保证粒子迭代中的速限制在0、1之间,同时位置的选取为0或1。

  3.1.2 BPSO算法调度流程

  在基于BPSO算法进行调度问题求解时,需要完成粒子的编码、粒子位置与速度初始化和适应度函数的设计。

  (1)粒子的编码

  在BPSO算法中,将每一种RVM群的分配方案表示为一个粒子,粒子位置为之前提到的映射矩阵X。

  (2)粒子位置与速度的初始化

  粒子位置即矩阵X,由系统随机生成。粒子的初始速度在速度限制范围内随机取值,Vj=Vmin+rand()(Vmax-Vmin)。其中,Vmox、Vmm为算法规定的粒子速度最大值和最小值。

  (3)适应度函数

  在数学模型搭建部分提出了针对BPSO算法设计的评价函数minf=k,xR+kxī+kxE在初始放置时,资源较为丰富,为保证系统整体的均衡性,将k、k、k据设置为1/3。基于目标优化函数设计算法适应度函数,此处取目标函数的倒数作为适应度函数,则适应度函数越大,目标函数越小,说明粒子的位置越优,表示该配置方案具有良好的综合性能,不断迭代计算每种粒子对应的适应度函数直到迭代结束得到全局最优解。在迭代过程中,因为RVM初始放置问题具有约束条件,即每个RVM只能映射一个PM,PM上所有RVM的资源消耗不能超过PM所包含的资源量,故将不满足约束条件的粒子位置对应的适应度函数设置为0,这样算法迭代结束后得到的最优解必然满足约束条件。

  3.2基于IRS的RVM增量调度算法

  在实际运行下,存在已有RVM无法满足需求,需要另行增加RVM的情况,所以问题转换为RVM增量放置问题,需要合理调度实现最优放置。在增量放置上主要的关注点是PM个体的资源利用率是否均衡。因此增量调度目标函数minf=k,xR。+kxú+kxE。取k=k;=0,k=1.算法主要分为两步:第一步构建PM集群可分配资源,并且实时对PM集群进行更新;第二步当一个或者多个RVM请求资源调度进行增量放置时,PM集群应该面向优化资源利用率均衡合理的为RVM分配资源。

  3.2.1构建PM集群可分配资源

  PM集群可分配资源定义为Б={F。/1≤q≤Q},其中F表示物理机PM,中计算资源q的剩余量。当RVM服务被部署或者服务完成被删除后,需要及时更新集合中相应资源空闲资源量。

  算法输入为RVM;、PMj,以及两者之间的部署标记Xi,输出为PM;上可分配资源[根据部署标记x。对集合F进行更新,如果x,=1,则说明RVM,部署在PM上,则万需要减去对应消耗种类的资源量,如果xy=0,则说明RVM,服务任务结束即将进行删除,则F需要增加对应释放种类的资源量。

  3.2.2 RVM增量放置分配资源

  将需要增量建造的RVM放置在一个集合中,该集合定义为I={l/1s psP},为需要创造的个数选择合适的PM来将集合中的RVM进行放置,其方法流程图如下:

  算法的输入为某一时刻请求增量创建的RVM集合,算法的输出是增量创建时PM的资源分配方案。在该方法中,为了降低资源调度的时间,首先将RVM集合I按照需求资源总量进行递减排序。然后对集合I中每一个RVM进行放置,放置时首先在正在运行中的PM集合中寻找剩余资源满足分配的主机,然后根据上节资源利用率均衡模型中的计算公式,计算假设放置在满足分配要求的PM上时,这些PM的资源利用率均衡值,最后按照优化资源利用率均衡的目标,将该RVM放置在值最小的PM上,如果未找到剩余资源满足分配的PM,则给该RVM分配具有最小资源总量的空闲PM。在放置完成后,更新每个PM的可分配资源集合。

  4仿真实验
       4.1实验准备

  实验环境配置:使用Eclipse 4.3.0开发平台,Java开发工具为JDK 1.7,仿真工具为Cloudsim 4.0,操作系统为Windows 10(64bit)。Cloudsim仿真平台具有优秀的底层设计,被广泛的应用于云计算调度实验,并且由于开源的特点,便于进行二次开发。因为本文使用到的云计算平台为OpenStack,故为了验证BPSO-IRS算法的优越性,将其对比OpenStack自带的LFF算法(剩余内存算法)进行仿真实验。

  将物理机CPU利用率100%时的满载耗电功率为250 W,则可以得到休眠功率为175 W。物理机的个数固定为30,虚拟机个数分别取30、50、70、90、110、130、150,共设计7组实验,且设定每组实验中取虚拟机总数量的80%以初始放置方式进行放置,而剩余的20%以增量放置方式进行放置,在进行算法求解之后,得到该组实验最终的虚拟机放置方案及相应的优化模型指标。

  将BPSO-IRS算法中BPSO算法部分的待定参数设置为:迭代次数100,粒子群规模为100,粒子最大速度为2,最小速度为1。

  4.2结果分析

  仿真实验从4个方面进行对比:算法求解时间、负载均衡指标、资源利用率均衡指标以及能耗指标。如图3所示,图中蓝线为BPSO-IRS算法,黄线为UFF算法,由图可知,与OpenStack原生的LFF算法相比,BPSO-IRS算法在解决RVM创建时资源调度问题时,得到最优值用时更短,且求解结果在负载均衡度以及资源利用率均衡度方面均表现较好,故该算法经验证更具有优越性。

  5结束语

  本文针对RVM实例创建时在PM上如何进行资源调度实现RVM最优放置的问题进行了研究。首先分析配电站机器人实际工作场景,RVM创建时存在两种不同放置情形:初始放置和增量放置,接着对放置问题进行了数学描述和优化目标模型搭建,得到放置问题目标函数,然后提出了BP‐SO-IRS算法来对问题进行求解,以PM集群上是否已存在RVM判断当前放置为哪种放置情形,对于初始放置情形,基于BPSO算法进行调度,对于增量放置情形,基于IRS算法进行调度,最终得到RVM与PM之间的最优映射方案及优化模型指标,最后基于Cloudsim仿真平台,对比OpenStack原生的LFF调度算法,对BPSO-IRS算法的优越性进行验证。

  参考文献:

  [1]陈舒丽.Z科技公司智能过温监测及预警装置商业计划书[D].成都:电子科技大学,2022.

  [2]唐卫.户外高压隔离开关机械闭锁的常见故障分析[J].红水河,2015,34(4):84-86.

  [3]郭梓晗,庄一能,王宝,等.配电站云机器人任务流的调度策略[J].机械设计与研究,2022,38(1):72-77.

  [4]林伟伟,齐德昱.云计算资源调度研究综述[J].计算机科学,2012,39(10):6-7.

  [5]Kumar M,Sharma S C,Goel A,et al.A comprehensive survey for scheduling techniques in cloud computing[J].Journal of Network and Computer Applications,2019,143.

  [6]Dong J,Jin X,Wang H,et al.Energy-saving virtual machine place‐ment in Cloud data centers.In:Proceedings of the 13th IEEE/ACM International Symposium on Cluster,Cloud and Grid Com‐puting(CCGrid).2013,618–624.

  [7]Xie R,Jia X,Kan Y,et al.Energy Saving Virtual Machine Alloca‐tion in Cloud Computing[C]//IEEE International Conference on Distributed Computing Systems Workshops.IEEE,2013.

  [8]Verma A,Ahuja P,Neogi A.pMapper:Power and Migration Cost Aware Application Placement in Virtualized Systems[J].Acm/ifip/usenix International Conference on Middleware,2008.

  [9]Gao Y,Guan H,Qi Z,et al.A multi-objective ant colony system al‐gorithm for virtual machine placement in cloud computing[J].Journal of Computer&System Sciences,2013,79(8):1230-1242.

  [10]Holland J H,Reitman J S.Cognitive Systems Based On Adap‐tive Algorithms[J].Pattern-Directed Inference Systems,1978:313-329.

  [11]曹海平.基于OpenStack的云计算平台设计与实现[J].信息记录材料,2023,24(4)13-1295.

  [12]刘建华,杨荣华,孙水华.离散二进制粒子群算法分析[J].南京大学学报:自然科学版,2011,47(5):11.

  [13]罗佳俊,代海波,王保云,等.基于IRS辅助的异构网络中超可靠低时延通信波束成形算法设计[J].电子与信息学报,2022,44(7):2289-2298.

  [14]Stutzle M.Ant Colony Optimization[M].Bradford Company,2004.

  [15]Kirkpatrick S,Gelatt C D,Vecchi M P.Optimization by Simulat‐ed Annealing SE-New Series[J].1983,220(4598):671-680.

  [16]Kennedy J,Eberhart R.ParticleSwarm Optimization[C]//ICNN95-international Conference on Neural Networks.IEEE,1995.

  [17]曲鹏举.改进粒子群算法在柔性作业加工时间问题研究[J].机械与电子,2023,41(1):3-6,12.

学术期刊发表-留言咨询

免费咨询 高端品质服务 专业学术顾问为您解答!