基于集群协作的云雾混合计算资源分配和负载均衡策略.pdf
《基于集群协作的云雾混合计算资源分配和负载均衡策略.pdf》由会员分享,可在线阅读,更多相关《基于集群协作的云雾混合计算资源分配和负载均衡策略.pdf(9页珍藏版)》请在咨信网上搜索。
1、基于集群协作的云雾混合计算资源分配和负载均衡策略杨守义*成昊泽党亚萍(郑州大学信息工程学院郑州450001)摘要:针对物联网(IoT)中智能应用快速增长导致的移动网络数据拥塞问题,该文构建了一种基于雾集群协作的云雾混合计算模型,在考虑集群负载均衡的同时引入权重因子以平衡计算时延和能耗,最终实现系统时延能耗加权和最小。为了解决该混合整数非线性规划问题,将原问题分解后采用库恩塔克(KKT)条件和二分搜索迭代法对资源配置进行优化,提出一种基于分支定界的开销最小化卸载算法(BB-OMOA)获得最优卸载决策。仿真结果表明,集群协作模式显著提高了系统负载均衡度,且所提策略在不同参数条件下明显优于其他基准方
2、案。关键词:雾计算;集群;资源分配;负载均衡;分支定界中图分类号:TN929.5文献标识码:A文章编号:1009-5896(2023)07-2423-09DOI:10.11999/JEIT220719Resource Allocation and Load Balancing Strategy in Cloud-fog HybridComputing Based on Cluster-collaborationYANGShouyiCHENGHaozeDANGYaping(School of Information Engineering,Zhengzhou University,Zhengzh
3、ou 450001,China)Abstract:ConsideringtheproblemofdatacongestioninmobilenetworkscausedbytherapidgrowthofsmartapplicationsinInternetofThings(IoT),acloud-foghybridcomputingmodelbasedoncluster-collaborationisconstructed.Theclusterloadbalancingisconsideredwhileintroducingweightingfactorstobalancethecomput
4、ationallatencyandenergyconsumption,andfinallytheminimumweightedsumofsystemlatencyandenergyconsumptionisachieved.Inordertosolvethismixedintegernonlinearprogrammingproblem,theoriginalproblemisdecomposedtooptimizetheresourceallocationusingKarush-Kuhn-Tucker(KKT)conditionandbisectionsearchiterativemetho
5、d.ThenanOverheadMinimizationOffloadingAlgorithmbasedonBranchandBrand(BB-OMOA)isproposedtoobtaintheoptimaloffloadingdecision.Simulationresultsshowthatthecluster-collaborationmodelimprovessignificantlythesystemloadbalancingdegreeandtheproposedstrategyoutperformssignificantlyotherbenchmarkschemes.Key w
6、ords:FogComputing(FC);Cluster;Resourceallocation;Loadbalancing;Branchbrand1 引言当今社会科技革命和产业变革突飞猛进,物联网(InternetofThings,IoT)的飞速发展催生了数以亿计的移动智能应用,例如自动驾驶、增强现实、视频业务等1,2。由于有限的计算能力和电池容量,用户的移动设备无法满足这些智能应用的计算需求3。移动云计算(MobileCloudComputing,MCC)将本地计算任务卸载到远程云服务器中以扩展移动设备的计算能力4。但受限于主干链路的容量限制和网络波动,MCC常会导致额外的传输延迟和能量损
7、耗,这严重降低了卸载效率5。因此雾计算(FogComputing,FC)作为云计算的延伸应运而生,它既具备较强的计算存储能力又更靠近终端层网络,缓解核心网络压力的同时极大地提高了服务质量(QualityofService,QoS)和资源利用率6。在面临交通拥堵、大型集会等场景时,由于移动用户计算任务的区域性激增,会导致局部网络拥塞和服务器过载,从而产生额外的丢包率和计算时延,甚至出现服务器单点失效现象7。而服务器集收稿日期:2022-06-01;改回日期:2022-10-14;网络出版:2022-10-19*通信作者:杨守义基金项目:国家重点研发计划跨政府合作专项(2016YFE0118400
8、),河南省自然科学基金(202300410482),郑州市重大科技创新专项(2019CXZX0037)FoundationItems:TheNationalKeyR&DProgramIntergovern-mentalCooperationSpecialProject(2016YFE0118400),TheNat-uralScienceFoundationofHenanProvince(202300410482),ZhengzhouMajorScienceandTechnologyInnovationSpecial(2019CXZX0037)第45卷第7期电子与信息学报Vol.45No.720
9、23年7月JournalofElectronics&InformationTechnologyJul.2023群技术可以在付出较低成本的情况下获得在性能、可靠性、灵活性方面的较高收益,任务调度则是集群系统中的核心问题。如何有效规划任务调度策略和资源管理,既维持整体系统的负载均衡又保证用户时延和能耗最小化,这也是本文研究的重点之一。近年来,已有许多学者对云雾系统中的卸载决策和资源分配问题进行了研究。文献8研究了基于雾计算的软件定义嵌入式系统,设计了一种结合系统存储容量的任务调度策略,尽量减少用户计算任务的完成时间。文献9考虑了雾服务提供商的成本,在执行时间阈值和用户优先级的约束下讨论了时延最小化
10、问题。文献10提出效用函数和功耗的加权和问题,结合了交替方向乘子法和近端最小化算法将全局问题分解为多个子问题,实现了系统目标函数最小。文献11研究了雾环境下负载均衡的动态资源分配问题,通过静态资源分配和动态服务调度实现了雾计算系统的负载均衡。文献12研究了云边网络中时间能耗加权和最小化问题,提出两种算法分别优化计算频率、发射功率以及匹配策略,实现了系统效用函数最小化。但是,上述研究主要集中在传统云雾场景下对单因素或双因素的优化,均未考虑利用集群技术及集群间的协作模式解决计算任务区域性激增时多用户多节点的时延、能耗和负载均衡综合问题。针对上述问题,本文贡献如下。(1)在3层云雾混合计算模型中,通
11、过联合优化计算资源、通信资源和任务调度策略,提出了SLEC(SystemLatency-EnergyCost)最小化问题。在硬约束条件下,通过集群协作模式实现负载均衡的同时满足系统时延和能耗加权和最小化。(2)由于各变量的复杂耦合,上述问题是一个混合整数非线性规划问题,无法直接求解。首先将原问题进行分解,经理论证明后通过库恩塔克(Karush-Kuhn-Tucker,KKT)条件和二分搜索迭代法分别优化计算和通信资源分配。然后提出基于分支定界的开销最小化卸载算法来寻找最优的任务调度策略。最终通过迭代资源分配结果和卸载决策达到全局最优解,实现最小化系统时延能耗加权和。(3)实验结果表明,本文所提
12、集群协作架构与传统计算方案相比具有显著优势,本文所提算法能够获得更低的时延和能耗,具有良好的收敛性。2 系统模型本文提出一个基于集群协作的云雾混合计算模型,如图1所示由3层网络架构组成。UU=1,2,.,UNN=1,2,.,N其中终端用户层包含 个用户,由表示。个具有计算和存储能力的分布式雾集群共同构成雾层,表示为。每个雾集群Nd(FogCluster,FC)由负载控制器(LoadController,LC)和多个具有计算存储能力的网络边缘设备(如路由器、微基站、智能车辆、交换机等)构成。每个FC都有一个覆盖区域,用户层被个FC完全覆盖且覆盖区域彼此没有重叠。集中式云服务器 构成云层,它通过广
13、域网(WideAreaNetwork,WAN)与雾层中各个FC形成稳定的双向链路。雾集群协作(FogClusterCollaboration,FCC)指的是当本集群计算任务负载过大时将部分任务通过LC迁移至另一集群进行协作并行计算,此模式有利于实现全局负载均衡。LC能够收集全局信息并且负责接收和转发计算任务,各集群中的LC端到端链接形成算力调节网络,从而实现FCC模式。假设云雾混合计算架构在任务迁移过程中是准静态模式13,且传输时的信道状态和网络拓扑结构是固定的。2.1 计算模型u UAppuuAppu=Lu,CuLuCu定义用户的计算任务为,各用户的任务之间不存在依赖性且计算任务是不可分割的
14、。用户 的任务属性由数组对表示为,其中(bit)代表任务数据量,包含任务类别和指令代码等参数,(megacycle)代表完成此任务需要的CPU周期数。u(1)本地计算模型:指计算任务在用户端由移动设备自行处理。各用户具有不同的计算能力,用户 在本地计算的时间为Tlu=Cuflu(1)Plu=l(flu)Pluu根据文献1,14,移动设备CPU的功耗是关于计算频率的超线性函数,表示为,为用户 的本地计算功耗,本文中 取2。所以用户在本地计算的能耗为Elu=Plu Tlu=lfluCu(2)图1基于集群协作的云雾混合计算模型2424电子与信息学报第45卷fluull=106其中,表示移动设备 的计
15、算能力。是设备能量转换系数,本文中设置。dnFnun(2)卸载计算模型:卸载计算包含雾计算和云计算。雾计算指计算任务被卸载至雾层并由其中一个雾集群执行。云计算是将任务交由集中式云服务器 计算。假设每个雾集群的计算资源被所有卸载到此集群的用户所共享,定义雾集群 的最大承载计算能力为。雾计算模式下,用户 的任务在集群 的计算时延和能耗为Tn,exeu=Cufn,eu(3)En,exeu=efn,euCu(4)fn,eunueud其中,表示雾集群 分给移动用户 的计算频率,为能量转换系数。当启动云计算模式时,用户 的计算任务在云服务器 的执行时间为Td,exeu=Cufdu(5)如文献15,在云计算
16、模式下本文不考虑中心云服务器产生的计算能耗。由于云服务器具有强大的计算能力,能够为用户提供充足的算力,因此如文献16一样,本文云服务器的计算频率是固定的,即不考虑对选择云计算模式的用户进行资源配置。2.2 通信模型S=0 1,2,.,N,N+101,2,.,NNN+1bu,s 0,1本文将任务留在本集群中计算的模式命名为近端卸载(ProximalOffloading,PO),这种模式节省了额外的传输时间。若用户所在集群的任务累积负载较大,集群中的LC会将部分任务迁移到轻负载集群执行以实现全局负载均衡这种模式命名为远端卸载(RemoteOffloading,RO)。所有的计算节点用表示,其中 代
17、表用户的移动设备,表示个雾集群,为集中式云服务器。式(6)定义2元决策变量为用户的任务执行策略。bu,s=bu,0=1,本地计算Nn=1bu,n=1,雾计算bu,n+1=1,云计算(6)K(n)=Uu=1bu,nnBK(n)u(1)近端卸载:通过无线信道将任务上传至区域内的LC中,然后由LC传输至本集群内具有计算能力的网络边缘设备中执行。定义为集群 中需要卸载的用户数,总带宽被个卸载用户均分。为了避免任务上传时集群内的用户间干扰,采用正交频分多址(OrthogonalFrequencyDivisionMultipleAccess,OFDMA)技术进行正交子信道分配。因此用户 的信息传输速率可以
18、表示为Ru(ptu,K(n)=BK(n)log2(1+ptuHuBN0/K(n)(7)ptuuHuuBN0u其中,代表用户 的上传功率。是用户 与负载控制器的无线信道增益,和分别为信道总带宽和噪声功率密度。在近端卸载模式下,用户 的任务传输能耗和时间分别为Ttransu=LuRu(ptu,K(n)(8)Etransu=ptu Ttransu=LuptuRu(ptu,K(n)(9)类似于文献16,17,由于计算任务的输出数据量远小于任务的输入数据量,本文不考虑计算输出结果的回传时间和能耗开销。RnndRdnunnd(2)远端卸载:假设FC之间的数据传输速率是固定的,用表示。FC与集中式云服务器
19、间的传输速率为。所以用户 的计算任务由集群 迁移至集群和云服务器 的时延分别为Ttransn,n=LuRnn(10)Ttransn,d=LuRdn(11)u综上所述,考虑到用户任务的计算模型、通信模型和卸载策略,在基于集群协作的云雾混合计算中用户 的计算任务总执行时间和总能耗分别为T=bu,0Tlu+bu,n(Ttransu+Tn,exeu+Ttransn,n)+bu,n+1(Ttransu+Td,exeu+Ttransn,d)(12)E=bu,0Elu+bu,n(Etransu+En,exeu)+bu,n+1Etransu(13)3 问题构建本文提出联合计算、通信资源分配和任务调度策略的优化
20、模型,在考虑系统负载均衡的同时满足时延和能耗开销(SystemLatency-EnergyCost,SLEC)最小化。SLECSLECu=u T+u Eu 0,1u 0,1u定义1是用户在任务调度决策下执行某种计算方式(本地计算、雾计算或者云计算)时产生的时延和能耗加权和,表示为。和是权重因子,分别用来衡量用户 对任务完成时间和能量消耗的偏好。Ln=Uu=1bu,nCunLBDLBD=N/Nn=1Ln L2L定义2为集群 的负载量,表示集群内用户计算量的总和。为负载均衡度(Load-banlancingDegree,LBD),它由系统中各集群任务负载量方差的倒数表示,其值越小代表负载分配越均衡
21、。,其中代表雾集群的平均负载值。第7期杨守义等:基于集群协作的云雾混合计算资源分配和负载均衡策略2425本文负载均衡的实现采用分布式策略,在集群可承载计算总量和用户数阈值的约束下,通过负载控制器的预处置寻求全局最优雾节点,从而实现系统LBD最小化。LC从用户层接收任务描述,根据各用户任务计算量的大小,将任务映射到雾层最佳可用资源上实现网络路由和资源管理,最终执行雾集群的选择,实现负载均衡的同时满足系统时延和能耗最小化。pufn,eubu,sSLEC=Uu=1SLECu本文目的是从资源分配和负载均衡两个角度出发,联合优化,和卸载决策从而使整个系统的最小化。基于此构建了一个联合资源分配和负载均衡(
22、JointResourceAllocationandLoadBalance,JRALB)模型来表示SLEC最小化问题OPT-1:minfn,eu,ptu,bu,sUu=1SLECus.t.C1:bu,s 0,1,u UC2:N+1n=1bu 1,u UOC3:Nn=1bu,n fn,eu Fn,u UO,n NC4:0 ptu pmaxu,u UOC5:0 Uu=1bu,n Capn,u UO,n N(14)UO=1,2,.,UoffFnnCapnnC1C2其中,是所有选择卸载计算的用户集合,表示雾集群 正常负载状态的计算资源阈值,表示雾集群 能够容纳的最大用户数。和C3nC4C5确保每位用户
23、只能选择一种计算方式。保证了雾集群 的计算资源分配总和不会导致其进入过载状态。规定了卸载过程中传输功率的上下阈值。表示雾集群服务的用户数必须在其容纳范围内。4 问题分解OPT 1根据目标函数及其约束条件可以看出JRALB是一个混合整数非线性规划问题(Mixed-IntegerNonLinearProgramming,MINLP),它是非确定多项式难度(Non-deterministicPolynomialhard,NP-hard)问题且难以直接求解。由于优化变量间互不耦合,因此将JRALB问题分解为两个独立的子问题:资源分配和卸载决策OPT-1:minbu,sminfn,eu,ptuUoffu
24、=1SLECu,s.t.C1C5(15)4.1 资源分配fn,euptu本节在特定的卸载策略下对资源分配问题即最佳计算频率和最优传输功率进行优化。只有当用户选择卸载计算时资源分配问题成立,所以JRALB问题又可以表示为OPT-2:minfn,eu,ptuUoffu=1u(Ttransu+Tn,exeu+Ttransn,n)+u(Etransu+En,exeu),s.t.C3:Nn=1bu,n fn,eu Fn,u UO,n N,C4:0 ptu pmaxu,u UO(16)OPT-2将式(3)、式(4)和式(8)式(10)代入式(16),问题可被转化为OPT-2:minfn,eu,ptuUof
25、fu=1uCu+uLufn,eu/Rnn+ueCu(fn,eu)2fn,eu+uLuK(n)+uLuK(n)ptuBlog2(1+(K(n)Huptu)/BN0)(17)fn,euptuC3C4ptufn,eu由式(17)可以看出,和是独立的,且约束和也是互不耦合的。本文选择用二分搜索迭代法和KKT条件分别求解最佳的传输功率和计算频率。ufn,euOPT 3(1)计算频率分配:LC分配给用户 的最佳计算频率通过优化子问题得到OPT-3:minfn,euUoffu=1uCu+uLufn,eu/Rnn+ueCu(fn,eu)2fn,eu,s.t.Nn=1bu,n fn,eu Fn,u UO,n N
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 集群 协作 云雾 混合 计算 资源 分配 负载 均衡 策略
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。