均衡调度（精选8篇）
均衡调度 篇1
0 引言
用户对于服务性能的要求, 使得单台服务器已经无法满足高并发度的用户请求。所以需要组成一个虚拟的计算机系统来响应用户的服务请求, 即一个有一定组织结构的服务器群组。既然这个群组内有多个单独的能独立处理服务器请求的计算机, 那如何充分利用这个群组内的每个独立的计算机, 使之利用率达到最大, 就是人们选择提高服务器群组整体性能的首选之路。其中, 最关键的当然是请求的分配均衡问题。我们的目标是所有的请求能较为均衡的分配到各个服务器单体上进行处理。
针对这个目标, 人们设计了一系列请求调度算法来使得用户请求均衡化, 即决定集群如何选择下一个集群节点, 将新的服务请求转发给它。
本文在研究了这些算法的基础上, 通过编写算法模拟程序, 比较各个调度算法的响应率。
1 负载均衡算法描述
1.1 轮转 (Round Robin) 算法[1]
轮转算法是一个简单经典的算法, 对每一个集群中的节点都一致对待, 即假定所有服务器的处理能力都是相同的, 对新发起的请求, 按照i= (i+1) mod n调度第i台服务器。其中i为上一次被调度的服务器, n为服务器的数量。此算法不适合服务器性能不一致的集群, 其最小调度粒度是请求, 所以当请求持续的时间变化较大的时候, 会出现负载不均衡的情况。
1.2 加权轮转 (Weighted Round Robin) 算法[2]
加权轮转算法是在轮转算法上演变而来, 不过对每一台服务器节点都有新增了权值, 来代表每一台服务器的处理能力, 也可以说是优先级。权值越大的服务器将会更多的被调度到。先找出权值最高的那几台服务器进行轮转调度, 然后减去所有权值的最小公倍数, 找出所有大于等于这个权值所对应的服务器, 以此循环, 直到没有更低权值的服务器存在。例如, 有服务器A、B、C, 权值分别为3、2、1, 则在一次调度中, 调度的顺序为AABABC, 然后重复这个顺序。加权轮转算法解决了传统轮转算法中性能不一致的时候的负载不均衡, 但是没有解决当请求持续时间方差较大的时候, 负载不均衡的情况。
1.3 最小连接数 (Least Connetions) 算法[3]
假设所有服务器的处理能力是相同的。通过服务器所处理的连接的多少, 来估计服务器负载。调度控制器需要记录所有服务器节点正在响应的连接数。当有新的请求到达的时候, 总是调度处理连接最少的那个服务器来进行响应。这样就能最大化的把负载平滑到所有服务器上。每当一个TCP连接断开或者超时的时候, 调度控制器中相应的连接数也会减一。但是问题也同样存在, 在服务器性能不同时, 其调度的效果就不理想, 会把更多的连接调度给处理能力差的服务器。
1.4 加权最小连接数 (Weighted Least Connections) 算法[4]
在最小连接数算法上发展而来, 如果加权轮转算法一样, 是在给每一个服务器加一个权值, 表示此台服务器处理数据的能力。加权最小连接调度在调度新连接时, 尽可能使服务器已建立的连接个数和其权值成比例。当前的新连接请求会被发送服务器i, 当且仅当服务器i满足以下条件
其中∑ConnectionCount为所有服务器当前连接数的总和, 并且ServerWeight[i]不为零。此公式可以等价化简为:
1.5 基于局部性的最少连接调度 (LBLC) [5]
此算法是针对Cache系统而设计的。负责均衡器负责调度目的IP相同的请求到同一台服务器上, 这样就可以让Cache的命中率更高。使得Cache的使用更多, 从而加强性能。
基于局部性的最少连接调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器, 若该服务器是可用的且没有超载, 将请求发送到该服务器;若服务器不存在, 或者该服务器超载且有服务器处于其一半的工作负载, 则用“最少连接”的原则选出一个可用的服务器, 将请求发送到该服务器。
2 算法仿真
2.1 流程设计
在页面中开辟内存, 新建选定算法的对象, 然后再读入Xml中的参数, 用这些参数初始化对象, 不断执行选定的算法, 当处理完所有请求以后, 显示结果, 显示被处理的请求数, 和进入服务器队列的请求数。一旦进入服务器队列, 则认为, 此请求遭遇网络堵塞, 将产生延迟, 假设一旦产生延迟, 此请求将被认为未被相应。最后计算每一次进入队列的请求数量, 取其平均值, 在页面显示。
2.2类图
BaseInfo为所有算法类中公用的属性所组成的基类, 所有算法类都继承与这个类。其InitBaseInfo方法, 可以对BaseInfo中的属性进行初始化。
每一个算法类中都有ClintRequestCount属性, 此属性表示初始化请求的数量。没当算法成功被执行一次后, ManagedRequest会加一, ResaultList中被分配到的服务器处理请求的数量也会加一, ConnCount中相对应的服务器连接数也会增加一。
在每一个算法类中都设计有List
AlgorithmType是一个枚举类, 枚举的是算法的名称。
ClassHelper是一个静态类。类中的方法都是各种被页面或者类重复调用的函数。比如Gcd方法返回的就是输入数组的最大公约数;ReadXmlFile方法, 返回的XmlNode, 用于读取Xml文件中的内容。如果类型不匹配, 则会提示Xml不合法。
每一个算法类都有一个Execute () 方法, 调用此方法, 就相当于使用此算法分配了一个请求。
加权算法会调用ClassHelper中的ReleseConnections () 方法, 是随机释放连接的方法, 产生随机数, 根据随机数来随机释放某几个服务器上某几个连接。
2.3 测试结果
2.4 结果分析
轮转算法性能没有最小连接数算法性能高, 进入队列的请求更多。
加权比不加权的算法性高, 在权值不相同的时候, 比权值相同加权算法更能体现其优点, 更好的分配请求, 平滑连接到各个服务器上, 减少服务器响应队列长度。在权值相同的时候, 不加权算法和加权算法性能差异不明显。
相同的算法, 在服务器权值相同的时候有更好的分配结果, 队列长度相对较少。
局部最小连接数算法拥有最好的性能, 有最小的队列长度。
综上所述, 流媒体服务器组所适合的负载均衡技术是, 基于直接路由技术的负载均衡, 因为下行流量为流媒体, 长时间持续的连接, 不通过调度器可以提高性能。因此, 适合流媒体服务器是基于局部性的最小连接, 因为他支持Cache, 可以有效提高缓存的使用效率, 并且可以有效把连接分配到集群中的服务器上。
3 结论
通过对以上5种调度算法的分析仿真比较, 我们得到, 在流媒体服务器组中相对比较适用的是基于局部性的最小连接算法。他能有效的平衡用户的请求, 同时它支持cache, 可以有效提高缓存的利用率。
摘要：随着计算机技术和网络的飞速发展, 用户对于网络和计算机的服务功能有了更强的依赖性。这也意味着对计算机和网络的整体性能有了更高的要求。然而单台计算机硬件性能的提升存在一些问题, 到达了一个瓶颈期, 所以利用多台计算机组成一个虚拟的计算机系统来响音用户请求成为了主流解决方案。本文从请求的调度算法进行分析, 实现调度算法, 并比较其性能的差异。
关键词：负载均衡,调度算法,轮转算法,最小连接数算法
参考文献
[1]向建军, 白欣, 左继章.一种用于实时集群的多任务负载均衡算法[J].计算机工程, 2003 (12) .
[2]余科军, 郑芸芸.分布式实时任务分配算法的设计与实现[J].福建电脑, 2007 (9) .
[3]王力共, 杨志新.电子政务平台服务器集群负载调度算法分析[J].湘南学院学报, 2006 (5) .
[4]马超.网络负载平衡系统的设计与实现[D].大连理工大学软件工程学位论文, 2005.
[5]吕丽平, 臧国轻.基于LVS服务器集群的研究[J].电脑知识与技术, 2010 (21) .
均衡调度 篇2
关键词：服务器集群；负载均衡；自适应
中图分类号： TP393.09 文献标识码： A 文章编号： 1673-1069（2016）17-153-2
0 引言
通常情况下，服务器集群中的网页查询任务采用的手段是动态嵌入对象，面对不同量或者类型的任务，服务器的负载量存在10-100倍的差异，对分布式系统的处理能力的有效利用能够保证多台服务器联合工作时负载的均衡。而一个良好的负载均衡手段能够最大程度的减少执行时间，计算机传输数据的开销，并根据服务器处理能力的不同分配相应的任务，使各个服务器的处理能力能够最大化的得到利用。
1 LVS集群负载均衡策略
国防科技大学的章文嵩率先提出了一种有效的负载均衡策略——LVS，通过后来不断地改进，该负载策略已经被广泛地运用在高性能的负载均衡系统中。随着网络技术的发展，客户端的任务请求数量逐渐增大，服务器端将会出现大小不一的负载量，传统的服务器技术难以及时地对客户的请求做出响应。搭建CentOS操作系统的LVS（LinuxVirtualServer）集群，Linux系统中自带有负载均衡策略，因此能够均衡不同用户的不同类型或者不同量的任务。集群技术的运用在一定程度上提高了数据检索的效率，减少了系统响应用户请求的时间。实际开发过程中，对服务器使用最小连接策略进行加权，依靠IPVS来实现负载均衡调度的实现，进而完成基于数据检索的Linux集群系统。不同服务器端的权值是其任务处理能力的衡量指标，一般情况下将权值定义为服务器端的性能与当前系统任务数的比值。该均衡调度对服务器分配任务主要依靠的是服务的任务处理能力和其连接的任务数，如果任务分配过于密集将会导致负载均衡器过载，出现阻碍系统运行的瓶颈。
LVS算法只将当前服务器链接的任务数量，但是仅仅用服务器当前的任务数量反映服务器的真实负载状况。因此为了更加准确地对服务器的负载情况进行分析，还需要对系统的性能、相应时间、开发费用等参数进行剖析，真正做到将服务器集群的运行效率提高。负载均衡器对服务器节点的任务处理能力以及各个服务器的负载状况的获取过程将对后续任务的均衡分配产生十分重要的影响。新兴的调度算法描述服务器的负载状况使用了两个指标，一是CPU的占有率；二是内存的空闲率。在进行任务分配前，不但要考虑服务器的处理能力不同，还需要考虑服务器的性能，进而保证集群服务器整体的效率最大化；为了更好地处理任务，服务器系统应当具有一定的伸缩性，当实际任务过多时，集群系统应该根据实际情况适量地增加服务器；此外，集群系统还应当具备负载的转移能力，当服务器连接的任务过多时，可以按照某种规则转给较闲的服务器。
2 动态自适应反馈的负载均衡策略
具有动态自适应的负载调度需要综合考虑服务器自身处理任务的性能和服务器节点链接的任务量两个指标。每个服务器叶子点能够根据已有的规则对自身的负载信息进行收集，并及时地将所收集的信息发送到负载均衡器上。使用动态的推送信息搜集服务器的负载信息，相对于负载均衡器主动去收集的方式而言，能够有效降低通信的开销，为负载均衡器减少负担。
分层负载均衡能够保证叶子节点同时并行处理，同时还能够保证真实事务服务器完全分布。另外，分层负载均衡为更高层次的负载均衡器提供使用聚合信息，对所连接的负载的改变能够及时做出应答。为了使集群系统中的信息流量减少，防止出现调度瓶颈，对处理器中的信息进行分组（簇），并把每簇中涉及到的服务器进行平行分层处理。此处理方法的主要目的是将主服务器的任务转移给一簇服务器，使该簇服务器成为“监督员”。 “监督员将对自己所获得的任务进行进一步的划分，并将划分的子任务分配给相应的叶节点，并对叶节点的处理结果进行收集。但是需要注意的是，分层方法虽然被广泛运用于线性阵列和树形拓扑结构，但若拓扑结构相对复杂，则分层方法将会失败。
2.1 自适应负载均衡
同一集群系统中的不同人物需求所需要的计算机的开销不同，由于不同用户对计算机的性能要求不同，并且所需要完成的任务也有所不同，因此常将用户任务分为两类：实时输入输出任务和实时CPU消耗型任务；使得最小连接调度算法进一步减小，产生均衡负载的新算法。
2.2 负载均衡流程
①二叉树排序算法主要是对负载的冗余值进行排序。如各个服务器的负载冗余值将会被负载均衡器收集并循环遍历，当某个服务器的负载冗余值超过最低限度时，便将此服务器入树，并构建二插排序树。②二叉排序树遍历。对二叉排序树进行中序遍历，形成一个递增的数列，服务器性能衡量指标（权值）将形成一个大小依次排列的序列。③任务分配。对服务器节点中序遍历后，按照服务器的现状和性能进行任务的分配，完成任务分配之后，各个服务器的负载值及其冗余值将会发生改变。
2.3 动态自适应反馈的负载均衡策略性能分析与评估
面向集群系统的负载均衡技术能够在整体上提升系统的性能，减少任务的响应时间，单个服务器的工作效率有所提高，整个系统的任务响应时间也将会提高。对于单片机系统而言，缓存方法是最好的改进系统性能的移植方法，结合缓存和传统的算法进行缓存结构的设计和实现，能够很好地改善服务器的运行时间。为测试系统效率，搭建3台服务器节点，采用基于直接路由方式构建Linux虚拟服务器集群，采用WAS（MicrosoftWebAp-plicationStressTool）作为模拟用户压力的测试工具，选择加权最小连接调度（wlc）算法作为对比其系统响应时间。实验依次以100、200到700的用户请求分7组进行模拟测试。
3 结束语
由于传统的Web集群负载均衡算法使用的是加权最小链接调度算法，因此可能出现负载不均衡的现象。为此在传统的加权调度算法的基础上，对原有的LVS算法进行了改进和优化。本文首先对传统的负载均衡算法的权值进行了重新分配，负载均衡器对各个服务器的CPU利用率和内存空闲率进行收集，确定新权值并传送到均衡器中，均衡器将根据新的权值进行任务的分配。其次，本文提出了动态自适应反馈的策略，为了减少均衡器的负担，采用的是服务器主动向均衡器主动反馈负载信息的方法。
参 考 文 献
[1] 邓珍荣，唐兴兴，黄文明，李寅威.一种Web服务器集群负载均衡调度算法[J].计算机应用与软件，2013（3010）：
53-56+101.
[2] 杨越，闫连山，张志勇，李赛飞.面向集群服务器大规模并发的改进负载均衡调度系统[J].微电子学与计算机，
2013，30（35512）：54-56+60.
[3] 任侠.基于动态自适应负载均衡的服务器集群优化策略[J].工业控制计算机，2015（2812）：38-39+41.
一种虚拟机负载均衡调度算法 篇3
目前, 在商业发展和开源技术研究中有多种虚拟化架构, 其中包括剑桥大学的XEN。在Xen中, 多个虚拟机同时运行在相互隔离的虚拟环境中, 共享底层物理硬件, 包括处理器资源, 且各个虚拟机能够以接近物理计算系统的性能运作[2]。Xen中常用的三种CPU调度算法包括:BVT (借用虚拟时间算法) 、SEDF (最早截止时间优先算法) 和基于信任值算法 (Credit) , 三种算法各有不同的性能瓶颈, 因此, 如何实现高效调度成为虚拟化技术中面临的更大挑战。
专利CN102053858A中提出了一种虚拟机调度算法, 通过监测虚拟机的CPU调度以及状态标识信息, 解决了锁抢占问题, 从而在多处理器架构中实现更精确的可调度状态监测, 提高底层物理CPU资源的利用率[3]。华中科技大学的金海提出了一种Xen虚拟化环境中动态感知音频应用的CPU调度算法, 通过设置合适的时间片大小以及增加实时优先级等策略, 提高了Xen中音频应用的播放性能[4]。
本文提出了一种SMP (对称多处理器) 系统中的动态负载均衡 调度算法 — 动态最早 截止时间 优先算法 (DLB_DEF) 来提高物 理CPU利用率 , 从而减少 空闲CPU。为了实现该算法, 我们设计了一种共享等待队列, 考虑到多处理器环境中cache和内存的同步关系, 使虚拟CPU在执行完任务之前都在同一个物理CPU上执行。仿真实验表明, 改进后的DLB_DEF算法能够优化系统性能, 并完全消除空闲物理CPU。
2SEDF算法以及SMP架构
2.1SEDF算法
在虚拟化计算环境中, 多个虚拟机通过分时调度策略共享物理处理器资源, 每个虚拟机就是一个域, 每个域对应一个或多个虚拟CPU (VCPU) [5]。因此, 如何公平高效地将物理CPU资源分配给多个虚拟机, 并使CPU有效利用率达到合理范围就是一个问题。
SEDF算法是一种基于最早截止时间策略的实时算法, 每个VCPU都会根据自身处理情况设置一个参数:最早截止期限 (deadline) , SEDF根据该时间参数决定VCPU的调度顺序[6], 而且VCPU的优先级根据deadline的改变而变化。SEDF算法将调度具有最早截止时间的VCPU, 从而保证虚拟机任务能及时完成。
每个域都设置一个三元组 (s, p, x) , 时间片s和周期时间p共同表示该域请求的CPU份额和时间, flag是一个boolean类型的值, 表示该域是否能够占用额外的CPU份额, 三个参数时间粒度的设置对调度的公平性影响很大。VCPU结构体的属性如图1所示, 每个PCPU包含2个双链表队列, 如图2所示。
runnableq队列中的VCPU都是处于running或runnable状态, 根据deadline参数排序, 队首的VCPU处于running状态, 而其他VCPU都处于runnable状态, 必须在deadline规定时间内执行调度;waitq队列中的VCPU处于runnable状态, 还未开始计时。
总之, SEDF算法可以通过参数动态配置VCPU的优先级, 因此在负载较大的实时系统中具有较高性能, 当系统负载较小时其CPU使用率可以达到100%, 然而, 随着负载逐渐增大, 一些任务就会发生时间错误, 错过截止期来不及处理而夭折。另外, SEDF算法不支持SMP架构, 从而不能实现对多CPU间全局负载均衡的控制。
2.2SMP架构
在SMP架构中, 多个处理器共享内存, 但每个处理器都对应一个私有cache, 大多数调度算法都遵循就近原则执行调度, 也就是说首选本地CPU来执行相应的任务, 从而提高cache命中率。当一个私有cache被修改后, 就要考虑内存和cache之间的一致性问题, 即不仅要确保修改后cache和相应内存之间的一致性, 而且要确保内存和其他cache之间的一致性。在执行过程中, VCPU可能会处于挂起状态, 比如时间片到或被其他事件阻塞, 此时VCPU虽然停止执行, 但是其对应的私有cache中还保存着运行时环境[7], 当处于挂起状态的VCPU被再次唤醒时, 使其在上次执行过的物理CPU上继续执行, 从而减少数据一致性产生, 即就近调度原则。
为了提高CPU资源的利用率, 就要重视cache和内存一致性带来的性能消耗问题。即VCPU在PCPU之间的频繁调度会产生严重的cache抖动, 进而使数据一致性问题产生额外的性能损耗, 严重降低CPU执行速度[8]。
3DLB_DEF算法的设计
通过上节中对SEDF算法的分析可知:SEDF在实时性环境中具有较好性能, 但不支持SMP架构, 如果一个CPU空闲, 它只能等待新的VCPU任务到来, 而此时其他CPU的任务量可能已经超载, 此时SMP架构中的多处理器系统的物理性能远低于具有相同处理器个数的系统。基于此研究结论, 本文提出一种基于SMP架构的虚拟机负载均衡调度算法——DLB_DEF算法。
在DLB_DEF算法中 , 共享队列share Waitq中的VCPU按照deadline参数进行排序, 且都处于runnable状态, 如图3所示为share Waitq结构体属性:
每个PCPU具有不同的等待时间权值, 即为对应runnableq队列中存放的VCPU的运行时间总和。当PCPU空闲时就从共享等待队列中调取VCPU任务, 同时, 考虑到cache就近原则, 将该VCPU任务上次执行过的PCPU记作pre_pcpu, 改进后CPU和VCPU的结构体属性分别如图4和图5所示:
假设物理机有M个可运行的PCPU, 如式 (1) 所示;式 (2) 为runnableq队列中的所有VCPU;式 (3) 为所有PCPU的weight集合;式 (4) 为weight集合中的最小时间权值。
改进后的动态负载均衡算法DLB_DEF与SEDF算法相同, PCPU都是优先调用具有最早截止期限的VCPU, 通过增加并实时更新共享等待队列share Waitq, 从而实现动态负载均衡。DLB_DEF算法如图6所示:
4仿真实验与结果
4.1仿真平台及环境配置
Schedsim是一种CPU调度模拟器, 提供了良好的接口, 能够实现先来先服务算法、短作业优先算法等多种常见的调度算法[9]。基于Schedsim, 本文设计并实现了SEDF算法和改进后的DLB_EDF算法, 并模拟了两种算法在不同数量处理器上的调度情况, 最后对两种算法调度的系统性能进行了分析和比较。
将SEDF和DLB_EDF中的一个VCPU任务记作一个进程, 由5个参数表示:进程ID号、优先级、就绪时间、执行时间和最早截止期限。为了满足仿真实验的需要, 假设PCPU个数最大为6, 配置5个进程池, 分别包含10、20、40、60、80个进程, 仿真实验步骤如下:
步骤1:创建的进程池至少符合以下要求:12个就绪时间相同而最早截止期限不同的进程, 22个就绪时间和最早截止期限都相同的进程, 32个执行时间不同而就绪时间和最早截止期限相同的进程, 42个分别具有不同的就绪时间、执行时间和最早截止期限的进程, 5就绪时间与执行时间之和大于最早截止期限的2个进程, 6将所有进程的最早截止期限设置为与优先级成反比。
步骤2:进程池中的所有进程入队。
步骤3:配置PCPU个数, 选择调度算法和调度模式。
步骤4:运行模拟器。
以下实验结果是以包含40个VCPU的进程池作为参考, 对每个进程池分别做10组测试, 并取10组数据的平均值。
4.2仿真结果分析
当两个算法的进程都完成时, 如图7、图8、图9分别为系统吞吐量、平均周转时间和平均应答时间的比较结果。
通过图7-9我们可以看到, 当PCPU个数为1时, 由于需要考虑cache就近原则, 因此DLB_DEF的系统吞吐量和任务完成率比SEDF算法略小, 但是平均周转时间以及平均响应时间比SEDF略大;当PCPU个数增多, 即在支持SMP架构的多 处理系统 中 , 具有负载 均衡策略 的DLB_DEF算法的各个性能指标都略超过SEDF, 系统吞吐量和任务完成率逐渐增大, 平均周转时间以及平均响应时间却逐渐减小。特别地, 当DLB_DEF和SEDF的系统吞吐量具有最大差值时, PCPU个数等于4, 即在PCPU为4时DLB_DEF算法具有最优性能。当PCPU个数继续增大为6时, SEDF算法由于空闲PCPU的出现而导致多种系统指标性能降低, 而此时, 在DLB_DEF算法中, 虽然PCPU个数增多, 但由于共享等待队列的互斥性, PCPU调用任务时等待互斥锁的解锁时间逐渐增大, 同时, 共享等待队列的更新也要占用更多时间, 因此, DLB_DEF算法的系统吞吐量、任务完成率、平均周转时间以及平均响应时间也逐渐达到平稳状态。
当PCPU个数逐渐增多时, 即具有更多处理器来执行系统任务时, SEDF和改进后的DLB_DEF算法的任务完成数和任务完成率都逐渐增大, 但是两者的完成率都达不到100%, 即有些VCPU由于错过截止时间而错过执行的机会, 但是DLB_DEF在总体上完成量比SEDF多。
5总结
本文主要对SEDF算法进行分析, 针对其不支持SMP架构的不足, 提出一种动态负载均衡算法DLB_DEF。该算法设计了一个共享等待队列存储VCPU任务, 并根据cache就近原则和PCPU的等待时间权值, VCPU可选择最优PCPU执行其任务。DLB_DEF算法不仅可以降低cache抖动带来的性能损耗, 还可以通过获取PCPU的最小等待权值来增大PCPU使用率。最后, 在Schedsim仿真环境中模拟SEDF和DLB_DEF, 仿真结果表明, DLB_DEF在系统吞吐量、平均周转时间和应答时间、进程完成率等性能指标上都略优于SEDF算法。目前仅在模拟环境中执行DLB_DEF算法, 下一步任务要将DLB_DEF嵌入到XEN源代码中并运行在真实虚拟环境中。
摘要：基于XEN的CPU调度算法已经广泛应用于很多实时系统中, 但是在多处理器系统中却很难实现负载均衡。本文提出一种虚拟机环境中支持SMP架构的CPU调度算法, 该算法在CPU调度算法中增加共享等待队列, 并基于cache缓存和内存的一致性问题, 使得虚拟环境中的多个处理器根据自身任务处理情况, 动态调整共享等待队列中VCPU的执行顺序, 这样就可以避免处理器空闲, 提高处理器使用率。通过仿真实验, 证明该算法支持CPU全局负载均衡, 可以避免cache和内存一致问题所产生的性能降低, 提高系统吞吐量, 降低VCPU执行的平均周转时间和响应时间, 使处理器资源得到充分利用。
关键词：XEN,虚拟机,CPU调度,SMP,负载均衡
参考文献
[1]怀进鹏, 李沁, 胡春明.基于虚拟机的虚拟计算环境的研究与发展[J].软件学报, 2007, 18 (8) :1016-1026.
[2]Paul Barham, Ian Pratt, Keir Fraser, et al, “Xen andthe art of virtualization, ”In SOSP’03:Proc of the nineteenth ACMsymposium on Operating systems principles, New York, ACM, 2003, 15:164-177.
[3]金海, 吴松, 石宣化, 等.一种虚拟CPU调度方法[P].中国专利, 102053858, 2011-05-11.
[4]Huacai Chen, Hai Jin, Kan Hu, et al.“Adaptiveaudio-aware scheduling in Xen virtual environment, ”In AICCSA’10:Proc of the ACS/IEEE International Conference on ComputerSystems and Applications.USA, IEEE Computer SocietyWashington, 2010:1-8.
[5]Hyunsik Choi, Saeyoung Han, Sungyong Park and EunjiYang, “A CPU Provision Scheme Considering Virtual MachineScheduling Delays in Xen Virtualized Environment, ”TENCON’09:2009 IEEE Region 10 Conference.2009:1-6.
[6]Xinjie Zhang, Dongsheng Yin, “Real-time Improvementof VCPU Scheduling Algorithm on Xen, ”In CSSS’11:ComputerScience and Service System.2011:1506-1509.
[7]常建忠, 刘晓建.虚拟机协同调度问题研究.计算机工程与应用, 2011, 47 (6) :38-41.
[8]Min Lee, A.S.Krishnakumar, P.Krishnan et al.“Supporting Soft Real-Time Tasks in the Xen Hypervisor, ”InVEE'10:Proceedings of the 6th ACM SIGPLAN/SIGOPSinternational conference on Virtual execution environments[J].New York, ACM, 2010, 45:97-108.
均衡调度 篇4
1 大数据网络的均衡调度平台设计
1.1 调度平台总体结构
大数据数据网络资源需要合理的平台才能更好地服务于用户,大数据网络的均衡调度平台能联合控制网络资源,还能监测物理资源和虚拟资源的运用状况。并按照用户的资源申请,供应可变化的大数据网络资源。通过基于能量评判的网络资源调度方法,来完成大数据网络物理资源与虚拟资源的均衡调度,确保大数据网络的负载均衡。大数据网络的均衡调度系统平台总体结构如图1 所示。
图1 所示的调度平台由服务模块、控制模块、虚拟化模块和物理资源模块四大部分组成。服务模块包括:用户控制、服务申请、服务控制、计费控制,主要是把各个资源转变为相应服务,利用Web门户的方式向用户供应。控制模块主要包括:资源控制、资源监控、服务部署以及资源调度,它是大数据网络的均衡调度平台系统的处理中间件,其能够实现大数据网络中的物理部件以及资源的合理处置以及调度。虚拟化模块可在虚拟化工具Virtual Box的辅助下,实现物理资源模块的虚拟化,还可以生成大量的虚拟机,来满足不同用户的不同需要。物理资源模块,囊括了标准不一的PC机、服务器、网络部件等。
1.2 平台的硬件功能模块组成
大数据网络均衡调度平台由资源定义模块、资源监测模块以及资源调度模块三大功能模块构成。如图2所示。大数据网络均衡调度平台基于资源管理方案,综合控制大数据网络的物理资源和虚拟资源,并且可面对用户的资源申请信息,检索当下所拥有的资源信息,并且按照一定的标准分派用户的资源申请。各模块的功能如下:
(1)资源定义模块。资源定义模块主要负责管理大数据网络的资源实体,采取的基本方法有创建、删除、修改、查询等。所谓资源实体,指的就是大数据网络、集群、物理主机、虚拟机以及虚拟机镜像等。
(2)资源监测模块。资源监测模块起到一个监督、视察的作用,主要针对大数据网络里的物理机和虚拟机的资源使用情形和运营状况。大数据网络节点的负载状况并不是始终如一的,它会因为时间的改变而千变万化,所以要收集每一个大数据网络节点的负载状况,以保证向用户分配资源与合理调度资源的顺利实施。通过设置在不同位置上的大数据网络节点里的监视设备,这个模块可以依照运行周期来收集大数据网络的资源使用情况,将网络监视设备布置在大数据网络服务器上,用来接收不同节点上监视设备输送出来的网络负载数据,并将已完成解析的数据储存到数据库中。对所有收集到的数据都要逐一研究,以便于指导虚拟机布置和负载均衡调节。
(3)资源调度模块。资源调度模块的数据来自资源监测模块,主要对大数据网络内每项物理机和虚拟机的资源负载状况进行计算,分置好各用户的虚拟机,通过基于能量评判的调度方法,实现大数据网络负载的均衡。资源调度模块采集并分析用户申请,根据用户需要设立虚拟机,并联系此时大数据网络资源的负载情况,在匹配的物理机上设置好虚拟机呈递给用户。
资源监测模块采集大数据网络中物理机和虚拟机的数据,基于获取的数据评估物理机的负载情况。如果物理机负载高于设置的阈值,则说明其负载超标,此时需要在该物理机中选取相应的虚拟机,并将大数据网络中未工作的服务器当成目标移动节点,对虚拟机进行移动,确保大数据网络实现负载均衡。
1.3 基于能量评判的大数据网络均衡调度模型设计
大数据网络均衡调度平台通过基于能量评判的调度方法,对网络中的资源进行均衡调度。基于能量评判的网络均衡调度模型中的资源节点和网络任务间的相关参数含义为:集合R ={r1,r2,⋯,rn} 用于描述n个异构资源节点构建的网络情况;集合T ={t1,t2,⋯,tm} 用于描述m个网络任务;设置ETij描述资源节点rj实施任务ti花费的时间;Bj用于描述资源节点rj的初始能量值。Ej用于描述特定时间里资源节点rj实施任务要花费的能量值;Cj用于描述特定时间里资源节点rj沟通单元数量数据的耗能量;BWj用于描述资源节点rj的网络带宽。网络数据调度模型的耗能是指,任务ti通过资源rj的本地计算耗能量EECij与实施任务时间ETij和耗能量率有着紧密的联系,如式(1)所示:
任务ti利用网络沟通的思维来考虑资源rj里沟通的耗能量CECij,将单元数据量的网络传递时间界定成网络带宽BWj的最后一位数,如果任务传递的数据量为Gi,网络沟通耗能量如式(2)所示:
ECij表示测量网络任务匹配到网络资源中的耗能量,有:
式(3)中的耗能量值ECij是一个资源rj在调度里的耗能量状态,但模型应考虑总体调度环境,完成能量的改进。所以需要增加一个衡量数值ECavg,ECavg用于描述全部网络资源的平均耗能量率,同时也是调度计算耗能量的衡量规范。 ECavg值同调度能耗具有正相关性,ECavg的表达式如下:
基于能量评判的大数据网络均衡调度的具体过程为:
(1)将大数据网络资源调度任务集T里的全部任务,映射到资源节点集R中的全部资源节点上,通过检测模块计算出全部相匹配的代价值Cost(i,j) 。
(2)记忆模块设置大数据网络资源集里的全部资源节点状态为未标记。
(3)随意提取大数据网络资源调度任务集中的1 个任务ti,将其映射到代价值Cost(i,j) 中最小的资源节点rj上,同时计算出Cost(i,j) 值,这个值表示最小代价。
(4)获取映射值,它的含义是当把大数据网络资源调度任务,映射到rj以外的任意资源节点的过程,就会产生更多的能耗,映射值就是最小代价和第二小的代价间的差值。
(5)分析大数据网络资源节点rj的标示状态:假设资源节点没有标示,在大数据网络资源调度任务集T里过滤任务ti,设置资源节点rj为已标记;假设资源点是标记状态,对比待映射到资源节点rj中的任务帐和任务ti映射值,如果rj的映射值较小,那么要把帐再次返还到任务集T里,并把ti映射到rj中,在任务集T里过滤ti。
(6)循环运行过程(3)~过程(5),直到不能将新大数据网络资源调度任务支配出去。
(7)被支配的新大数据网络资源调度任务资源节点的准备时间Di与资源结余能量值,在当前迭代中完成实时调整。
(8)循环运行过程(2)~过程(7),自适应调度模块进行数次迭代,一直到任务集里的全部任务都完成,并计算ECavg的数值。通过调控ECavg值,实现大数据网络负载的控制,确保大数据网络负载均衡。
2 代码设计
大数据网络均衡调度平台,通过塑造通信连接类Socket Connection类和一些物理监视器彼此创立联系,得到需要调度的数据,关键代码如下:
3 实验分析
为了验证本文方法的有效性,需要进行相关的实验分析。实验研究本文方法和启发式调度方法,对于某大型电子商务网络服务器在能量评判、吞吐率以及CPU利用率上的性能对比。实验针对不同的任务数,对两种方法进行调度检测,循环运行100 次,分析两种方法的平均能量消耗率,结果如图3 所示。
由图3 可知,与启发式调度方法对比,本文方法的平均能耗率较低,同时随着任务数的逐渐提升,能量消耗率呈现平稳变化趋势,但是启发式调度方法却存在较高波动。主要是启发式调度方法在调度网络资源过程中仅考虑任务完成时间,对高能耗的运算能量高的资源进行调度,使得能量消耗率高并且具有加大的波动。
实验统计两种方法在发送任务数过程中的吞吐率和时延,结果如表1 所示。
由表1 可知,当任务数较小时,两个算法的吞吐率相差不大,但是启发式调度方法的时延高于本文方法。说明当任务数增加,网络负载提升情况下,本文方法可针对大数据网络环境进行资源自适应的调整,并且具有较高的吞吐率,大数据均衡调度优势充分表现出来。实验通过图4 分析两种方法的CPU利用率情况。
分析图4 可得,本文方法的CPU利用率始终高于启发式调度方法,并且变化较为平稳,本文方法具有较高的负载均衡效果。
4 结语
本文提出一种基于能量评判的大数据网络均衡调度平台;平台由服务模块、控制模块、虚拟化模块和物理资源模块组成,包括资源定义模块、资源监测模块以及资源调度模块三大功能模块。调度平台基于能量评判的网络资源调度算法,在一定的时间区间内完成能量消耗最佳为最终目标,全面分析了大数据网络资源调度中的能量评判问题,给出了调度平台采集数据的关键代码。实验结果说明,所设计平台的平均能耗率、吞吐率以及CPU利用率指标都较优,具有较高的负载均衡效果。
摘要：当前的数据调度平台以数据完成时间实现网络资源的调度,将任务完成时间当成网络均衡调度的基础,未考虑大数据网络的能耗指标,无法实现真正的网络均衡调度。提出基于能量评判的大数据网络均衡调度平台,平台由服务模块、控制模块、虚拟化模块和物理资源模块组成,包括资源定义模块、资源监测模块以及资源调度模块三大功能模块。设计一种基于能量评判的网络资源调度模型,在一定的时间区间内,以能量消耗最佳为约束条件,全面分析大数据网络资源调度中的能量评判问题,给出调度平台采集数据的关键代码。实验结果表明,所设计平台的平均能耗率、吞吐率以及CPU利用率指标都较优,具有较高的负载均衡效果。
关键词：大数据网络,均衡调度平台,网络资源调度,能量评判
参考文献
[1]潘飞,蒋从锋,徐向华,等.负载相关的虚拟机放置策略[J].小型微型计算机系统,2013,34(3):520-524.
[2]邓维,刘方明,金海,等.云计算数据中心的新能源应用:研究现状与趋势[J].计算机学报,2013,36(3):582-598.
[3]魏彦红.BI-Paa S平台中BI应用的调度方案的研宄与实现[D].北京:北京邮电大学,2014.
[4]张洁.Agent的制造系统调度与控制[M].北京:国防工业出版社,2013:18-21.
[5]魏晓辉,付庆午,李洪亮.Hadoop平台下基于资源预测的Delay调度算法[J].吉林大学学报(理学版),2013,51(1):101-106.
[6]胡丹,于炯,英昌甜,等.Hadoop平台下改进的LATE调度算法[J].计算机工程与应用,2014(4):86-89.
[7]柯何杨,杨群,王立松,等.Hadoop延迟调度中延迟时间间隔的合理设置[J].计算机应用与软件,2013(12):207-210.
[8]刘莉,姜明华.异构集群下的任务调度算法研究[J].计算机应用研究,2014,31(1):80-84.
均衡调度 篇5
关键词：数据库,稀疏度,均衡调度,数据库优化访问
0 引言
随着信息技术和大数据技术的快速发展,大数据库作为存储数据信息的重要载体,对数据库的优化访问是提高数据查询和调度性能的关键。Web大型数据库广泛应用于大型的网络信息数据和云存储信息数据的存储和调度架构中。对Web大型数据库的频繁访问过程中,进行特征分区和数据文本的指向性索引,有利于提高数据库访问性能。研究大型Web数据库的优化访问技术,在数据库优化设计和数据传输存储等领域中具有重要的应用价值,相关算法研究也受到人们的重视。
传统方法中对Web大型数据库的访问方法主要有基于自适应波束形成的特征分区方法、基于粒子群滤波的遗传算法、基于相关度特征分析的数据库访问方法等,通过提取大型数据库的级联相关匹配语义信息特征,采用文本索引和关键字数据查询方法,进行相关度匹配来实现数据库的访问[1,2,3]。上述方法在数据库访问过程中,通过遗传散布执行算子进行特征分区,对数据库中的语义信息进行融合和滤波处理,以提高数据库访问过程中的分辨能力和查准率。但是上述方法需要在高维的子空间中进行特征重构,随着数据增多,对数据库访问的效能下降,计算开销较大。对此,相关文献进行了算法改进设计。其中,文献[4]提出一种基于信息流减法聚类和模糊C均值调度的数据库访问算法,通过粗糙集索引实现数据库访问,但是该方法对数据库访问过程中的稀疏度均衡能力不好;文献[5]提出一种基于关键字有向图模型的数据库访问算法,然而该算法对非线性MIMO级联数据库频繁访问特征分区性能不好。针对上述问题,本文提出一种基于稀疏度均衡调度的数据库优化访问算法,首先构建数据库的分布结构模型,然后进行数据库访问的信息流特征提取和数据信息融合处理,并以此为基础,采用稀疏度均衡调度方法实现数据库的词频信息指向性分析,提高数据库访问能力。仿真实验进行了性能测试,得出有效性结论,并展示了较好的应用价值。
1 数据库存储结构与数据特征分布
1.1 数据库存储结构模型
近年来,随着人们对分布式数据库的深入研究与常态化应用,研究大型网络的Web分布式数据库访问技术,首先需分析数据库的存储结构模型。数据库采用界面接口来实现数据库的访问,Deep Web数据库则更为具体和复杂,需要提供更为详细的查询条件等,而搜索引擎接口相对简单,输入关键字查询即可实现数据库访问。在数据库查询过程中,给出数据库访问传输字节量的转移算子hi(t),所需传输字节的量是反映传输代价的衡量指标,数据集中选择K个实例,初始化数据簇中心F(xi,Aj(L)),i=1,2,...,m,j=1,2,...,k,得到在大型Web数据库中的数据库存储分布节点的融合中心矢量[6],并得到数据的属性集合为:
式(1)中,xji中的j是用来对子数据库系统的连续性区分标识。对词频进行有效估算,可以研究出某个词频数字W出现的频率。由此可见,在数据库访问中,通过词频估计,构建语义本体模型,如果不存在G3=(M3α,M3β,Y3),使得G1≤G3≤G2,则G2是G1的父结点(直接前驱),G1是G2的子结点表示。这与一般搜索引擎的访问具有一定相似性,通过Hassse图可生动地体现概念之间的泛化与例化关系,得到大型Web数据库中,为了实现优化访问,构建专家系统级联数据库,采用矢量控制输入模式,数据库的存储节点特征区间为:
在数据库访问中,数据库存储机制问题涉及对Deep Web数据库的宏观统计和决策问题,以及单个Deep Web数据库的查询效率问题。Web数据库动态索引的时频熵特征采样信息密度函数为:
基于ARMA模型法,构建数据库索引优化控制函数,得到语义信息流的准确预测结果收敛需要满足条件:
式中:
在特征分区递进中,在tk时刻实现数据库访问的语义信息分布式优化访问耦合控制,通过数据库的模板匹配进行数据库访问的信息采样,由于模型本身是分布式的,采用自回归调控模型,得到数据库分布的级联存储节点模型如下:
其中mi(t),pi(t)∈R,表示第i个结点对端到端数据库访问的时域长度和控制长度,ai和ci分别为缓冲区的数据调度速率,di是数据库访问的响应速率,bi(.)是第i个内容存储CS端口的调控函数,通过多层自相累积调度,实现访问信息的累加,单变量的语义特征信息时间序列为{xn},则在多模分布状态下数据库访问的调控函数形式为:
式(7)也被称为数据库知识存储的本体结构模型,采用语义实体模型构建方法,得到数据库访问的存储空间结构,基于时频特征查询的数据访问调度方法,通过特征提取和信息融合,提高数据的查准率。
1.2 数据库访问的语义信息特征提取与数据融合处理
在Web数据库存储机制分析和存储调度模型设计的基础上,进行数据库访问的语义信息特征提取和数据融合处理。数据库访问的语义信息调控函数bij(pj(t))是一个Hill形式的线性调频函数,bij(pj(t))的表达形式为:
其中,P为存储系统的阶数,如果静态分块数据链中的信息聚焦在多层中具有融合中心,则通过数据库的语义信息聚类,可提高数据的激活能力。假设j是i的激活因子,那么存储节点自适应特征匹配关联度为:
假设Web数据库中文本内容的语义状态特征为{xn},它作为一个连续系统,数据库中的文本模块区域定位特征描述为:
其中h(.)表示信息融合的空间函数,ωn为测试误差。采用相似度对偶耦合方法,得到存储空间组A={A1A2…An}在数据库存储空间的映射集合x=[…xi…xji…]T∈RnN为一个正交的矢量场,该矢量场具有非平稳的线性特征,且数据存储空间中数据的融合中心矢量具有光滑性,能有效反映信息流特征。假设数据库存储空间的维数为d,则对于R,采用匹配投影法进行数据库访问过程数据降维,特征空间中,有:R→R2d+1,数据访问特征空间的数据降维输出表示为:
根据经验模态分解模型,当词频融合状态的关联维数下降到初始值的1-1/e时,采用小波变尺度分解,得到数据库访问的语义信息特征提取结果为:
其中,Rs(n)表示存储空间的变尺度调整聚类中心的迭代系数,通过语义相似度求得变尺度调整聚类中心向量为:
上式中ρxy是一个无量纲的量,通过上述数据融合处理,得到数据库访问的中心聚类矢量最优,提高了数据访问的配准性能。
2 算法改进实现
在数据融合和存储机制分析的基础上,进行数据库访问优化,通过对Web大数据库的访问,提高数据库的查询和信息调度能力。传统方法采用基于信息流减法聚类和模糊C均值调度的数据库访问算法,对数据库访问过程中的稀疏度均衡能力不好。为了克服传统方法的弊端,本文提出一种基于稀疏度均衡调度的数据库优化访问算法,算法的改进实现过程描述如下:在数据库访问过程中,通过对语义波束指向性特征临界状态进行数学建模,得到稀疏度均衡调度指令为一个控制输入信号,稀疏度均衡调度的矢量特征为uj*(s;tk)。对于Web分布式数据库系统,由于稀疏度均衡调度的控制函数J*(.)的收敛性是保证数据库优化访问的前提条件,在系统相邻状态之间进行迭代循环,得到稀疏度均衡调度矢量表示为Ji*(.)。在有效的存储空间内,计算最佳的基函数,使x(T)∈Wp,稀疏度均衡调度的稳定性得以保证。通过数据库中海量数据的语义信息融合,从多状态数据结构中进行数据挖掘,得到数据挖掘的特征分解变换式R3表示为:
假设波束指向的时延尺度系数为τ,存储空间的最佳基函数的关联矢量X与Y的协方差记为Cov(X,Y),稀疏度均衡调度的索引深度可表示为:
初始化数据库索引起始时间点为t0,则相应的Web分布式数据库在稀疏度均衡调度的安全访问关联匹配量可表示为:
为了提高数据库访问过程中的语义波束指向性,通过稀疏度均衡调度作为数据库访问的特征输入,传递指向给级联数据库的二阶邻居节点,得到输出的访问控制指令为:
在索引递进tk时刻,数据库系统在不同的指向性路径控制下进行关联匹配,初始化向量设置,得到数据库访问的深度状态结构为:
通过稀疏度调度,实现数据库访问的均衡处理,提高了语义指向性聚焦能力,得到输出的数据库访问数据查询的关联指向性特征分别为:
其中,λmax(Qi)为语义本体模型的耦合矩阵,Qi为最大特征值。通过上述算法设计,提高了数据库访问性能。
3 仿真实验与结果分析
为了测试本文算法在实现Web数据库访问中的性能,进行仿真实验。仿真环境为:Inter Pentium 4 3 000MHz内存,操作系统为Windows 7。数据访问中,数据存储节点分布带宽为1 024Kbps,语义信息流时间序采样的中心频率为f0=1 000Hz,离散采样率为fs=10*f0Hz=10KHz,数据传输延时20ms,数据库访问的采样点N=1 100。根据上述仿真环境和参数设定,进行数据库访问,首先进行稀疏度特征提取,基于稀疏度均衡调度实现数据库查询和索引,得到采用本文算法和传统算法的数据库访问的稀疏度调度均衡性能对比结果如图1所示。
由图可见,原始的数据库访问的稀疏度特征杂乱无章,具有较强的非线性特征,难以形成有效的访问结果,而采用本文方法进行稀疏度均衡调度处理后,数据库中的信息流分布均衡,提高了数据库访问的查准率,展示了较好的性能。
4 结语
本文提出一种基于稀疏度均衡调度的数据库优化访问算法,首先构建数据库的分布结构模型,进行数据库访问的信息流特征提取和数据信息融合处理,然后以此为基础,采用稀疏度均衡调度方法实现数据库的词频信息指向性分析,提高数据库访问能力。仿真结果表明,利用该算法进行数据库访问的均衡性能较好,查准率较高,性能优越。
参考文献
[1]卫星,张建军,石雷,等.云计算数据中心服务器数量动态配置策略[J].电子与信息学报,2015,37(8):2007-2013.
[2]侯森,罗兴国,宋克.基于信息源聚类的最大熵加权信任分析算法[J].电子学报,2015,43(5):993-999.
[3]罗亮,吴文峻,张飞.面向云计算数据中心的能耗建模方法[J].软件学报,2014,25(7):1371-1387.
[4]辛宇,杨静,汤楚蘅,等.基于局部语义聚类的语义重叠社区发现算法[J].计算机研究与发展,2015,52(7):1510-1521.
[5]陆兴华,陈平华.基于定量递归联合熵特征重构的缓冲区流量预测算法[J].计算机科学,2015,42(4):68-71.
均衡调度 篇6
近年来关于云计算中的负载均衡问题是一个研究热点，如今已经有许多的负载均衡算法被提出以满足不同的优化目标。
最大最小算法(Max-Min)和最小最小算法(Max-Min)是一种启发式的调度算法，他们以任务的总执行时间最短为优化目标，Max-Min算法的核心思想是每次先计算任务在各个资源上的预计算时间，然后对最大最早完成时间的任务进行调度。对于元任务集合中长任务少短任务多的情况下，算法的执行效果较好。但是如果具体应用条件发生了变化，MaxMin算法的优势可能就不存在了[2]。
Max-Min算法和Max-Min算法却正好相反，它是先计算出任务在资源上的预计执行时间，再将最小且是最早完成时间的任务调度到资源节点上，这样会使任务的处理速度较快，任务完成时间短，但是由于每次都是把任务分配给执行最快的资源，这样很容易造成负载的严重不均，甚至一些服务器空载[3]。
基于此，本文提出了一种基于云环境下针对任务类型匹配的资源调度算法，该算法针对任务集中长短任务的不同分布情况来采取不同的调度算法，通过云仿真软件CloudSim3.0验证了该调度策略良好的调度效果。
1 相关工作
云计算环境下，有大量的负载均衡算法用于将任务调度到相应的计算资源上执行，根据优化的目标不同，算法各有优缺点。当前有国内外学者都相继提出了针对Max-Min算法和Max-Min的缺点的改进算法，Mao等人提出了利用任务状态表预测虚拟机实时负载和任务预计完成时间来动态调度任务[1]，这种方法虽然能够实现较好的负载均衡，但是由于需要维持任务状态表的实时更新，所以会使得开销比较大，任务响应时间偏长。Santhosh B等人提出了一种改进的Max-Min算法[4]，每次将任务集中的和平均任务长度最接近的任务分配给完成时间最短的任务。Upendra Bhoi等人提出一种增强型的Max-Min任务调度算法[5]，针对元任务集中大任务数很少而小任务很多的情况，提出了一种将最大任务优先调度到执行速度最慢的资源上。O.M.Elzeki等人提出一种改进Max-Min算法[6]，针对小型云计算环境下，将最大执行时间的任务分配给最小完成时间的任务。郑莉等人提出一种基于用户优先级的负载均衡算法[7]，该算法针对Min-Min算法进行改进，一开始用Min-Min算法进行任务分配处理，然后选择负载较重的资源进行资源的重新分配，观察负载重资源上的最短任务，并计算它在其他资源上的完成时间，如果小于任务跨度，那么将此任务从最终负载上移除，用其他资源进行处理。
上述介绍的种种算法，虽然在原有算法的基础上做出了一些改进，但是由于大都在特定的仿真环境下，比如说增强的Max-Min算法，作者给出的实验数据是长任务很少，而短任务很多的情形，所以所得结果会比原有算法性能更优，但是考虑到云环境下任务的动态特点，所以这些算法没有较强的适应能力。基于现有算法的局限性，提出了一种基于任务类型匹配的资源调度策略(TTM)，在此调度策略下通过与用单一使用Max-Min或者Min-Min算法相比较，验证了此算法在任务动态环境下具有较好的效果。
2 云环境下负载调度模型
2.1 负载均衡任务调度模型
负载均衡是云计算的主要问题之一，负载可以是内存、CPU处理能力、网络或者是时延负载[8]。它需要在不同的节点之间共享工作负载，从而提高资源利用率和系统的性能。本文通过深入分析了Max-Min算法和Max-Min算法的优缺点和所使用的场景，设计了一个新的调度策略，根据任务集中的任务长度分布情况来调用相应的算法，调度模型如图1所示。
此调度过程为，首先用户提交任务，通过作业管理器管理用户提交的任务，计算任务所需要的性能要求和其他的一些因素限制，运用不同的负载均衡算法将任务分配给不同的虚拟机去执行，当然这里的虚拟机是在物理服务器中创建的，所以考虑的是物理服务器的负载。
2.2 任务类型匹配负载均衡算法设计
云计算环境下由于任务的大小不一，云计算数据中心各节点的处理能力也不同，所以负载的的定义很复杂[9]，为了简化起见，做了2点假设。
1)各任务之间是独立的，互相之间没有依赖关系;
2)虚拟机的处理能力只考虑他的执行速度(MIPS)，没有考虑带宽和内存等其他因素。为了描述模型的方便，先做一些相关定义。
定义1:任务执行时间(TET)。
任务执行时间是一个任务在某个资源节点上的处理时间，假设任务i的长度为lengthi，虚拟机j的执行速度为MIPSj，那么任务i在虚拟机j上的执行时间为
定义2:任务预期完成时间(TCT)。
任务预期完成时间是任务在考虑分配给哪个虚拟机时要考虑的问题，看看任务在哪个虚拟机上能最快处理完成，即为准备时间，放在处理能力最强的虚拟机上完成时间不一定短，这个和执行时间不同。它等于开始执行的时间BETij加上Tij。
定义3:平均资源利用率和时间跨度。
资源利用率表示为所有虚拟机在整个任务处理过程中的资源平均利用率
式中:RUj表示虚拟j的资源利用率;Tei和Tbi表示任务i在资源上执行的结束时间和开始时间;T表示整个任务集处理完成所用时间;为所有资源平均资源利用率。时间跨度表示为任务全部处理完所需要的时间
定义4:集中任务预期完成时间标准差。
由于各个任务之间是独立的，所以标准差计算公式为
定义5:负载均衡度。
负载均衡度定义为各个虚拟机之间负载量的差别程度，用β表示
式中:m表示虚拟机的个数;S表示资源利用率的标准方差，当S越小是表明负载均衡度越高。
2.3 策略执行过程
对于到达的一批假设任务集为T{t1,t2,t3，…，tm}，他们的长度分别为length1,length2，…，lengthn，首先将到达的任务集中的任务按照长度进行升序或者降序排列，为了讨论方便假设为降序，在排好序的任务中找到连续几个值大于SD的地方，通过此方法可以找到任务长度明显变化的地方，记为Po，所以对于任务集中的任务分布可能有如下3种情形:
1)情形1，即如果Po<S/2，那么说明短任务数大于长任务数，此时应用Max-Min算法效果会比使用Min-Min效果好。
2)情形2，即如果Po>S/2，那么说明短任务数小于长任务数，此时应用Min-Min算法效果比较好些。
3)情形3，即如果任务长度间的差值没有大于SD，说明任务之间的长度都差不多，此时选择Min-Min算法处理下个任务，算法流程图如图2所示。
3 实验仿真结果及分析
为了验证本算法的有效性，采用CloudSim 3.0软件进行仿真实验，这是一款由澳大利亚墨尔本大学开发的云计算仿真工具，主要考察两个指标:任务总执行时间(Makespan)和负载均衡度(Load Balancing Level)，实验表明提出的算法优于单一采用Max-Min算法和Min-Min算法。
针对上述3种情形进行仿真实验，仿真中将资源数定位取10，一批任务的数量为1 000，刚开始任务是长度随机排列的，任务到达由泊松随机过程建模。仿真结果如图3、图4所示。
通过图3中的3种情形得比较可以看出，提出的算法在3种情形下均具有较短的时间跨度，情形1中由于有许多的段任务，而长任务量很少，多虚拟机并发执行的时间短，所以用Max-Min算法耗时比较长，而此时用Max-Min算法效果比较好。情形2恰好相反，短任务很少，长任务多，此时应用Max-Min算法就没有什么优势。情形3中子任务之间的长度差别很小，所以用Max-Min算法执行时间也较短。
同样以上3种仿真情形中使用TTM算法均具有较好的负载均衡效果，由于Max-Min算法的负载均衡效果本身要优于Min-Min算法，特别是当短任务很少、长任务多的情形。因此对于以上3种情形的负载均衡水平采用TTM算法会具有较好的性能。
4 结束语
本文主要针对云计算环境中的负载均衡问题进行了研究，在深入分析当前的两种经典的启发式负载均衡算法基础上，通过比较他们的优缺点，提出一种基于任务类型匹配的负载均衡算法，并通过CloudSim云仿真环境验证了此算法的可行性，提出的算法不仅加快了系统响应时间而且有效地平衡了虚拟机之间的负载，提高了用户的服务质量。由于研究工作是在已有的负载均衡算法上做的调度策略创新，而不是在原有的算法上做的改进，而且对于任务调度有较多因素没有考虑，比如通信的开销、执行任务的花费等，所以这也会是下一步的研究工作。
摘要：针对云计算环境下大量并行计算节点容易产生计算节点之间的负载不均问题,提出了一种基于任务类型匹配的负载均衡方案。该方案针对任务集中的多种不同长度的子任务类型情况进行判定,并对当前主流的Max-Min和Min-Min两种启发式负载均衡算法进行分析,综合其优缺点,并针对任务集的类型采用不同的算法进行任务调度。实验结果表明在该负载均衡的策略下,提出的方案具有比单一应用Max-Min或者Min-Min算法具有更好的负载均衡特性和更短的完成时间。
关键词：云计算,任务调度,负载均衡,Max-Min,Min-Min
参考文献
[1]MAO Y,CHEN X,LI X.Max-min task scheduling algorithm for load balance in cloud computing[C]//Proc.International Conference on Computer Science and Information Technology.[S.l.]:Springer India,2014:457-465.
[2]KANAKALA R,REDDY V K.Performance analysis of load balancing techniques in cloud computing environment[J].Telkomnika Indonesian Journal of Electrical Engineerin,2015,13(3):568-573.
[3]苏淑霞.面向云计算的任务调度算法研究[J].安徽大学学报:自然科学版,2014,38(5):24-30.
[4]SANTHOSH B.MANJAIAH D H.An improved task scheduling algorithm based on Max-Min for cloud computing[C]//Proc.International Conference on Advances in Computer&Communication Engineering.Bengaluru,India:IJIRCCE,2014:84-88.
[5]BHOI U,RAMANUJ P N.Enhanced Max-Min task scheduling algorithm in cloud computing[J].International Journal of Application or Innovation in Engineering&Management(IJAIEM),2013,2(4):259-264.
[6]ELZEKI O M,RESHAD M Z,ELSOUD M A.Improved Max-Min algorithm in cloud computing[J].International Journal of Computer Applications,2012,50(12):22-27.
[7]郑莉.云计算环境下资源调度关键技术研究[D].北京:北京邮电大学,2014.
[8]KHERANI F,VANIA J.Load balancing in cloud computing[J].International Journal of Engineering Development and Research(IJEDR),2014,12(1):907-912.
均衡调度 篇7
渲染技术是一种计算机图像生成技术, 它针对已构造的几何场景模型, 结合几何对象表面的色彩、纹理及材质定义, 考虑在各类可见光源环境下, 根据光照模型计算生成几何表面的色彩及光亮度, 并最终生成具有较高真实效果的场景图[1,2,3]。其关键点主要包括场景模型的简化和管理、光照模型、纹理映射、材质设置、渲染算法等。随着现代动漫制作中渲染计算量的不断增大, 渲染计算时间越来越长, 渲染已成为动漫产业快速重要支撑。随着计算机网络技术和中间件技术的发展, 将渲染技术与集群系统结合的集群渲染系统逐渐成为动漫及电影场景特效渲染的主流手段[5,6,7]。
紧随国外集群渲染系统的成熟发展, 国内渲染集群系统的建设近年来也得到迅速发展[8,9]。中国目前有国家级动漫基地50多个, 如上海多媒体公共服务平台在立体式制作软件方面使用Maya、3ds Max与Softimage/XSI等, 在渲染软件方面使用Mental Ray, 集群渲染系统采用Muster分发软件, 能够制作并渲染所有的立体动画, 同时也使用了清华同方的基于GPU的集群渲染系统;湖南的国家数字媒体技术产业化基地三维集群系统拥有100颗CPU。这其中大部分系统及相关研究[10,11,12]仅考虑使用简单的任务分配来完成任务的并行渲染工作, 存在渲染系统工作效率低、负载不均衡、容错能力差等问题。本文研究分析了一种基于任务生成时间和任务量的任务负载均衡调度算法, 仿真结果显示该算法可以有效提高系统使用效率、同时提升渲染集群的服务质量。
2 算法设计
集群渲染系统的负载均衡策略旨在采用各种手段解决系统中各节点工作负荷不平衡的问题[13], 使得集群渲染系统能够充分地发挥每个工作节点的性能, 实现渲染集群系统工作效率的最大化, 其中的核心组件是任务分配和节点调度管理。通常, 不同的任务分配及调度策略将导致系统牌不同的工作状态, 进而影响系统的整体性能及强壮性, 寻找适用于集群渲染系统的最优调度策略是非常有现实意义的研究工作[14,15,16]。本文提出了一种基于任务生成时间和任务量判别的负载均衡调度算法, 它主要结合了先来先服务算法及短时间优先算法的策略思想, 以有效提高渲染系统的整体工作效率, 获得更好的系统稳定性。
2.1 相关研究
2.1.1 先来先服务调度 (FCFS)
先来先服务调度算法 (FCFS) 是一种常用的服务调度算法[16], 该算法在系统进程调度和任务调度中均有广泛的应用。集群渲染系统中采用该调度算法时, 当有空闲资源可用时, 从等待任务队列中选择一个或者多个最先进入该队列的作业, 将它们调入任务执行队列, 然后分配某个工作节点执行该任务, 该任务被不间断执行直至任务完成。先来先服务 (FCFS) 算法比较有利于渲染工作量较大的任务, 而不利于工作量较小的任务, 虽然先来先服务 (FCFS) 算法的CPU利用率较高, 但会增加工作量较小渲染任务的等待时间, 影响任务响应质量。
2.1.2 短作业优先调度 (SJF)
短作业优先调度算法 (Shortest Job First) [17,18], 是指对短作业优先调度的算法, 它同样广泛用于系统的进程调度和任务调度。短作业优先调度算法在执行每次渲染任务调度时, 循环从等待任务队列中选择一个或者若干个估计运行时间最短的作业, 将他们调入任务的执行队列进行渲染, 直到任务完成。短作业优先调度算法 (SJF) 能有效地降低作业的平均等待时间, 提高系统吞吐量, 降低渲染时间较小任务的等待时间。然而短作业优先调度算法 (SJF) 也存在不容忽视的缺点: (1) 该算法对渲染任务量大的不利, 如果有一个渲染时间较长的任务进入系统的等待队列, 由于调度程序优先调度那些渲染时间较短的任务, 将导致时间较长的任务长期不被调用; (2) 由于作业的长短只是根据用户提供的估计执行时间而定的, 致使该算法不一定能真正做到短作业优先调度。
2.2 负载均衡调度算法
为了更有效地提高集群渲染系统节点CPU的资源利用率, 同时兼顾渲染任务的执行等待时间, 保证任务的响应即时性, 本文提出了一种基于任务生成时间和任务量的负载均衡调度算法。算法主要思想为:为渲染任务等待队列中的每个任务分配一个动态的调度优先级, 当系统可执行新任务时, 根据任务优先级, 先执行优先级高的任务。显然, 优先级的定义为上述调度算法的核心, 具体定义为:
其中, f (s) 为渲染任务产生时间的优先级函数, 借鉴先来先服务调度算法 (FCFS) 调度思想, 依据渲染任务的产生时间, 定义优先级函数f (s) 为:
Ts为等待队列中在任务s之前产生的未被调度执行的任务数, 显然, 越早产生的任务其值越大。此外, 考虑Ts有可能为0, f (s) 定义的分母式作加2处理平滑。式 (1) 中的定义h (s) 为渲染任务的计算任务量相关的优先级函数, 同时结合短作业优先调度算法 (SJF) 的思想, 将渲染任务量小的任务优先执行。定义任务量优先级函数h (s) 为:
Fs为在等待队列中根据渲染任务的帧数和渲染时间, 等待队列中任务量大于任务s的任务数量, 任务量越小优先级越高, 同样在h (s) 中将分母作加2考虑。式 (1) 中r为权重因子, 当r=1时, 均衡调度算法等同于先来先服务调度算法 (FCFS) , 当r=0时, 均衡调度算法等同于短作业优先调度算法 (SJF) 。结合上面定义, 均衡调度算法流程图具体如图1所示。
3 仿真分析
为了分析渲染任务调度算法性能, 将两台电脑以Client/Server架构模型搭建仿真平台。文中所有仿真实验均在Windows7+eclipse平台下完成, PC计算环境为CPU Intel Core (TM) i3-3240 3.40GHz, 内存4G。
实验中, 客户端模拟任务发生器不断产生任务, 服务器端模拟任务调度渲染。在客户端, 每1-15分种随机产生一个渲染时间1-20min、帧数为1-200的渲染任务, 模拟时长为3个小时;在服务器端, 服务器每5分钟扫描200个渲染节点是否空闲, 分别采用先来先服务调度算法 (FCFS) 、短作业优先调度算法 (SJF) 、负载均衡调度算法进行调度渲染。文中从等待时间、任务结束比和CPU利用率三个方面对调度算法进行比较评估, 定义:
由于真实渲染调度中并不能确定渲染任务每帧的渲染时间, 本次仿真实验分为两组, 每组进行10次仿真实验。第一组为实验一, 假设已知渲染任务每一帧的渲染时间, 则根据“渲染时间×渲染帧数”作为任务量大小进行优先级计算;实验二则假设渲染任务每一帧的渲染时间未知, 则直接将渲染帧数作为任务量大小进行优先级计算。两组实验中等待时间与任务结束比的10次运行统计结果用线盒图表示, 结果如图2示。此外, 表1与表2分别列出了两组实验结果的CPU的利用率情况。如此, 图2与表1、表2分别给出了先来先服务调度算法 (FCFS) 、短作业优先调度算法 (SJF) 和负载均衡调度算法在等待时间、任务结束比和CPU利用率三个性能指标上的对比结果。
从图2中可以看出, 在实验一中SJF算法在等待时间和任务结束比方面效果较好, 负载均衡调度算法次之, FCFS算法效果最差。而在实验二中由于时间未知, 负载均衡调度算法与SJF算法效果接近, 且从线盒图上显示负载均衡调度算法稳定性更好, 均值更优。表1和表2中对CPU利用率最优的结果进行了加粗显示, 从中可以看出在CPU利用率方面, 负载均衡调度算法的CPU利用率最高, FCFS算法次之, SJF算法效率最低。两类实验中, 负载均衡调度算法均有很好的性能表现, 能更好地满足集群渲染系统的任务调度负载均衡需求。
4 结束语
均衡调度 篇8
西气东输工程是我国进行天然气开发和运输的战略性工程,通过西气东输管道工程,实现对天然气由我国西部地区向东部地区的运输和调度。西气东输的管线网络全线采用自动化控制,供气范围覆盖中原、华东、长江三角洲地区。自新疆塔里木轮南油气田,向东经过库尔勒、吐鲁番、鄯善、张掖、武威、西安、洛阳、信阳、合肥、南京、常州等地区,这一项目的实施,为西部大开发、将西部地区的资源优势变为经济优势创造了条件。西气东输管线采取干支结合、配套建设方式进行,管道输气规模设计为每年120亿立方米。西气东输沿线通过分布在各地的压气站实现输送流量的压气和调度,通过对天然气管线输送流量进行优化均衡调度设计,实现对天然气管线运行工况的准确监测,研究天然气管线输送流量的均衡调度模型,在优化西气东输管道工程的工况和天然气传输的效率中具有重要意义,相关的算法和模型设计研究受到人们的极大重视[1]。
传统方法中,对天然气管线输送流量的调度方法主要有基于ARMA模型的流量预测算法、基于粒子群算法的天然气流量的调度算法和基于模糊C均值聚类的流量预测和均衡调度算法等[2,3],上述方法对天然气管线输送网络天然气流量的准确调度的本质是进行流量时间序列的特征分析和模型构建,采用现代的信号与信息处理方法进行流量信息的特征提取,实现天然气流量调度,由此取得了一定的研究成果,其中,文献[4]提出一种基于最大Lyapunov指数分离的天然气管线输送流量调度方法,通过最大Lyapunove预测方法进行流量预测,实现对西气东输天然气管线的输送流量工况的准确监测,但是该算法计算开销较大,实时监测性能不好。文献[5]采用线性时间序列Wolf一步预测方法进行天然气管线输送流量调度,而未能有效挖掘天然气管线输送网络中天然气流量的非线性特征,导致调度的准确性不好。
针对上述问题,本文提出一种基于定量递归分析的天然气管线输送流量均衡调度方法。首先构建了天然气管线的网络配置结构模型,进行输送流量序列的信号模型构建和非线性时间序列分析,对天然气流量进行相空间重构,在高维相空间中进行递归图构建,实现对天然气管线输送流量的定量递归分析,达到流量准确预测和均衡调度的目的,实现算法改进。最后通过仿真实验进行性能测试,得出有效性结论。
1 天然气管线的网络配置结构模型和天然气输送流量的时间序列分析
1.1 天然气管线的网络配置结构模型
为了实现对天然气管线输送网络的天然气流量均衡调度,需要首先分析天然气管线网络的天然气储运和输送传输机制及流量调度机制,在天然气管线输送环境下,进行天然气管线分布配置网络模型和压气站的配压节点分布模型分析,用一个二元有向图G=(V,E)表示天然气管线的网络配置结构,得到天然气管线分布配置网络的分布结构模型如图1所示。
其中,V是部署在天然气管线的网络配置的监测区域的管线分布顶点集;E是天然气管线分布配置网络在天然气供气和传输的覆盖区域G中所有边的集合。M1,M2,…,MN为压气站的分布节点,使用802.15.3a、802.15.4的专用网络协议进行天然气输送的流量信息采集和数据传输,进行天然气管线的网络数据收发和流量传输的模型构建。采用最常用的Bell模型(0/1模型)构建天然气管线分布配置网络的转发协议,得到天然气管线分布配置网络通信节点(xs,ys)与中继节点s的通信半径为d(s,p)。
天然气管线分布配置网络流量的鲁棒性模型中,假设天然气管线分布配置网络中2个相邻节点的覆盖贡献度具有相关性,选择管线分布覆盖效率i∈S的节点进行天然气传输流量的均衡配置[6,7,8,9,10],假设K{ri}为区域中天然气传输配置范围内的压气站分布节点的覆盖系数,ri(x)为mu(i,x)+np,其中mu(i,x)+np>0,m<0、n<0且为常数;u(i,x)表示控制簇头传输的适应度函数,在保证SN节点与sink之间进行天然气传输配置网络均衡下,提高管线的天然气输送吞吐量,选择自适应均衡策略,进行网络配置,在上述构建天然气管线的网络配置结构模型中进行流量均衡调度分析。
1.2 天然气输送流量的时间序列分析
天然气管线输送流量传输信道模型中,流量传输分为3个区域,通过链路LAN连接在不同的网格站点中实现对天然气流量的传输。采用离散频谱的分数阶傅立叶变换进行特征空间重组,构建天然气管线输送管道的路由分发的无向图G=(V,E),其中,p为多输入输出多跳网络中输送天然气管线系统的负荷预测阶数,用ann(u,r1,r2,a)表示以节点u为圆心的得到功率向量V=[V1,V2,…,Vm]∈Rm×m的辐射半径,可以为任意实数,采用非线性时间序列分析方法,假设给定监测的天然气管线输送网络信道的数据流量表示为:
其中,Ui为天然气管线输送流量时间序列的时间标量序列,其表现为一种随机变量,假设x(n)为天然气管线输送流量预测的时间序列组合,〈x(n)〉代表对x(n)取均值:
在上述进行了天然气管线输送流量调度信息流时间序列重构的基础上,进行流量监测的频率响应配置,得到天然气管线输送流量时间序列的特征向量幅值和自相关特征状态为:
其中,t表示对天然气管线输送流量的时间采样间隔,在天然气管线输送流量序列的d×L维广域子空间中,通过提取联合熵特征实现相空间重构,得到重构的相空间为:
其中,τ为时延,m为流量相空间的嵌入维数,从而形成m维状态空间,在m维相空间中,采用一个紧缩的非线性差分方程描述天然气输送流量时间序列的高维特征状态为:
其中,M是d维的非线性动力系统的时间窗口,h是M上的流量配置的传递函数,计算天然气管线输送流量时间序列的几何不变量,得到了该状态空间中的几何吸引子si=(xi,xi+τ,…,xi+(m-1)τ)T,构建天然气管线输送流量预测相关函数,至此实现对天然气管线输送网络天然气流量的时间序列,为进行流量调度提供准确的数据输入基础。
2 天然气管线输送流量均衡调度算法改进实现
2.1 问题描述及天然气管线输送流量均衡调度的定量递归分析
在上述进行了天然气管线的网络模型配置和流量的时间序列分析的基础上,进行天然气管线输送流量均衡调度算法改进,提高天然气管线运行工况的准确监测能力。分析当前方法可知,传统方法采用线性时间序列Wolf一步预测方法进行天然气管线输送流量调度,没能有效挖掘天然气管线输送网络中天然气流量的非线性特征,导致调度的准确性不好。为了克服传统方法的弊端,本文提出一种基于定量递归分析的天然气管线输送流量均衡调度方法。在高维相空间中进行递归图构建,实现对天然气管线输送流量的定量递归分析,天然气流量的递归图构建方法如下。首先进行天然气管线输送流的相空间轨迹重构,对天然气管线输送流量时间序列x(t)出现在分布区间i的概率随机变量满足αk≥0,,时间序列{x(t0+iΔt)},i=0,1,…,N-1,基于Takens嵌入定理,得到天然气管线流量的相空间重构轨迹为:
其中,K=N-(m-1)τ,表示天然气管线输送流量时间序列的正交特征向量,τ为时间延迟,m为嵌入维数,si=(xi,xi+τ,…,xi+(m-1)τ)T称为天然气管线输送流量序列的嵌入空间欧氏空间中的湍流环,其表达式为:
天然气流量的传输管道的均衡调度模型是一个n阶多输入多输出(MIMO)系统,描述如下:
其中,y∈Rm为时间标量序列向量;f∈Rm为流量时间序列的频谱分布函数,u∈Rm,通过自适应能量均衡,同时又针对流量时间序列的递归图展开分析,得到递归图中的谱特征为V(k)=[v1T(k),v2T(k),…,vNT(k)]T,天然气管线输送流量序列的统计信息的方差满足:
结合相空间重构轨迹的扩维测量方程,选择ρ=0.95,β=1.2,获得k-1时刻的天然气传输流量的聚类中心的最优值,得到递归图中的噪点和特征点w(k)与V(k)的相关性为:
由于天然气流量的自相关特征配准性,进行干扰抑制,干扰向量RV(k)是一正定的实对称阵,根据信息融合可以使得递归图中的噪点RV(k)可以唯一地分解成:
采用定量递归分析方法使得天然气流量传输的均衡偏差ση2最小,实现均衡调度控制,得到通过管线均衡调度控制后的输出数学表示为:
其中,rη=E[x[η]xs],xs=[x(η1),…,x(ηN)]T,Rss=E[xsxsT]∈RN×N。由此实现了基于定量递归分析的天然气管线输送流量的均衡调度。
2.2 改进算法实现步骤
综上分析,改进的天然气输送流量的均衡调度算法实现步骤如下:
1)对于传输管道中天然气传输流量的时间序列{xn}Nn=1,其采样时间序列长度为N,采用合适的嵌入维数m和延迟时间τ对天然气输送流量进行相空间重构,重构后的天然气流量的相空间的轨迹为:
计算重构后的流量时间序列的递归图第i点xi和第j点xj的聚类中心,表示为:
2)对于给定的xi,通过阈值寻优计算dij≤ε点的数目N(i),式中ε一般取特征空间的最优子函数,同时计算天然气管线输送流量序列的递归图的规则特征点数占总点数的比值Rm(r,i):
3)取每个Rm(r,i)的自然对数,同时求出递归图中的谱特征:
4)将相空间的嵌入维数增加到m+1,对上述步骤进行重复,可得出Rm+1(r,i)和AVm+1(r)。
5)求得天然气传输流量时间序列的近似熵的定义为:
限定初始迭代步数,在给定的初始值下进行流量均衡调度,得到输出为:
根据上述步骤进行算法优化设计,最后通过仿真实验进行性能测试和验证。
3 仿真实验与结果分析
为了验证本文设计算法在实现天然气管线输送流量均衡调度中的性能,进行仿真实验。采用Matlab仿真软件,参数设定为Gmax=30,D=12,c=3,NP=30,F=0.5,CR=0.1,m=2,天然气管线输送流量的初始采样频率f1=2.1 Hz,终止频率f2=0.23 Hz,权重系数ω设定为0.9。根据仿真环境和参数设定,进行天然气传输流量的均衡调度仿真,首先进行天然气管线中输送流量的原始序列采样,得到采样的流量时域波形如图2所示。
以上述的采样数据作为测试集,结合压气站给出的标准样本训练集,进行流量均衡调度,采用本文方法进行定量递归分析,构建流量的递归图,如图3所示。
从图可见,采用本文方法,在高维相空间中进行递归图构建,实现对天然气管线输送流量的定量递归分析,达到流量准确预测和均衡调度的目的,为了对比算法性能,采用本文方法和传统方法进行流量均衡调度,以流量调度的幅频响应为测试指标,得到对比结果如图4所示,从图可见,采用本文方法进行流量调度,幅频响应的指向性明显,旁瓣波束得到有效抑制,说明进行流量调度的均衡性较好,展示了本文方法的优越性。
4 结束语
本文研究天然气管线的流量均衡调度模型,通过对天然气管线输送流量进行优化均衡调度设计,实现对天然气管线运行工况的准确监测。本文提出一种基于定量递归分析的天然气管线输送流量均衡调度方法。首先构建了天然气管线的网络配置结构模型,进行输送流量序列的信号模型构建和非线性时间序列分析,对天然气流量进行相空间重构,在高维相空间中进行递归图构建,实现对天然气管线输送流量的定量递归分析,达到流量准确预测和均衡调度的目的,实现算法改进。仿真实验分析结果表明,采用该方法进行天然气管线输送流量均衡调度,天然气输送运行的工况得到改善,输送配置的均衡性较好,流量预测精度较高,调度效能增强。
参考文献
[1]杨雷,李贵鹏,张萍.改进的Wolf一步预测的网络异常流量检测[J].科技通报,2014,30(2):47-49.
[2]张曦文,赵尚弘,李勇军,等.基于空分复用的多信道机间紫外光通信定向MAC协议[J].激光技术,2016,40(3):451-455.
[3]邓博于,赵尚弘,李勇军,等.一种基于星间光链路的帧同步与频偏估计方法[J].激光技术,2016,40(2):264-269.
[4]PALOMARES I,MARTINEZ L,HERRERA F.A consensus model to detect and manage non-cooperative behaviors in large scale group decision making[J].IEEE Trans on Fuzzy System,2014,22(3):516-530.
[5]ZHANG H,WANG Z,LIU D A.Comprehensive review of stability analysis of continuous-time recurrent neural networks[J].IEEE Trans on Neural Networks and Learning Systems,2014,25(7):1229-1262.
[6]陆兴华,陈平华.基于定量递归联合熵特征重构的缓冲区流量预测算法[J].计算机科学,2015,42(4):68-71.
[7]翟海滨,张鸿,刘欣然,等.最小化出口流量花费的接入级P2P缓存容量设计方法[J].电子学报,2015,43(5):879-887.
[8]张骏,田泽,梅魁志,等.基于节点预测的直接Cache一致性协议[J].计算机学报,2014,37(3):700-720.
[9]PATCHARAMANEEPAKRON P,ARMOUR S,DOUFEXI A.Coordinated beamforming schemes based on modified signal-toleakage-plus-noise ratio precoding designs[J].IET Communications,2015,9(4):558-567.