均衡调度（精选五篇）
均衡调度 篇1
关键词：Hadoop,负载均衡,MapReduce,调度算法
0 引言
Hadoop[1]执行MapReduce的过程主要分为Map和Reduce两个阶段[2],前者对数据进行划分和键值对处理,后者对划分后的数据片进行规约计算。然而Reducer所处理的数据是根据数据片的Key值分配的,由于数据本身特点的不确定性,K e y值的分布通常不均衡,从而导致Reducer分配到的数据量与资源也容易出现不均衡状况,在数据量较大的情况下会严重影响MapReduce的任务处理效率[3]。
针对该问题,本文通过研究Hadoop的任务调度原理,结合相关负载均衡调度算法,提出了一种新的动态优先级负载均衡算法(DPLB),实现集群作业的动态负载,提高了Hadoop集群的资源利用率和系统响应速度。
1 MapReduce在Hadoop上的任务调度
Hadoop MapReduce的任务调度主要由JobTracker和TaskTracker两个进程来完成。JobTracker的作用是作业控制、状态监控以及资源管理,TaskTracker的作用是执行JobTracker下达的命令,并且周期性地将节点资源使用情况以及任务运行状态等信息通过心跳机制[4]汇报给JobTracker。Hadoop MapReduce的任务执行过程如图1所示。
在作业调度过程中,当一个Maptask完成之后并不会主动将输出的数据发送给Reducer,而是由Reducetask通过向JobTracker询问自身的节点状态是否能接受工作任务,得到JobTracker允许后会通过http协议从完成的Maptask获取属于自己的数据块,并根据Key值进行排序,最后调用用户定义的Reduce函数进行处理并输出结果。合理的调度算法能够更充分地利用集群中的TaskTracker,提高集群的并行处理效率。
2 常用Hadoop作业调度算法
2.1 FIFO调度算法
FIFO调度算法[5]通过单队列结构来存放提交的作业,新到达的作业排在队列尾,队列头部的作业拥有最高的执行优先级。该算法的缺点是不利于多作业的并行执行,另外时间先后优先级的方式没有考虑作业之间的差异性,容易导致小作业的长时间等待,无法充分利用系统资源。
2.2 Capacity Scheduler调度算法
基于容量的调度[6]算法采用多队列结构,每个队列配置一定比例的资源,当JobTracker接到一个作业时,会对各队列当前可用资源比重进行比较,将作业分配给可用资源最多的队列。Capacity Scheduler算法灵活性较好,但在队列的资源配置上依赖经验设置,管理难度较大。
2.3 Fair Scheduler调度算法
公平调度算法[7]也采用多队列结构,不同的是该算法为每个用户配置了一个资源池,不管提交的作业有多少都能够保证每个用户分得均等的资源,并且允许每个资源池选择自己的调度方式。但该算法在分配资源池之前需要针对不同用户的数据特性做出不同的参数配置策略,因而在异构集群情况下的管理会变得十分复杂。
3 动态优先级负载均衡调度算法(DPLB)
3.1 算法思想
针对传统Hadoop集群调度算法的不足,提出DPLB(Dynamic Priority Load Balance,动态优先级负载均衡)算法。该算法利用TaskTracker周期性反馈的心跳信息计算节点负载情况与队列的任务承担能力,结合作业在队列中的等待时间与作业规模设计一种动态优先级,使小作业的等待时间减少,提高调度效率。
3.2 算法相关定义
3.2.1 节点负载能力NL与队列承载能力QL
节点负载能力计算主要依赖于TaskTracker发送的心跳信息,该信息包含的相关状态参数主要有:最大并行Map数、最大并行Reduce数、任务失败次数、CPU使用率、CPU频率、可用内存容量、可用磁盘空间以及磁盘I/O速率等。为了反映节点的负载能力,需要综合考虑这些信息,因此定义节点i的负载能力,如式(1):
根据各参数数量级的不同以及各项性能在计算中的重要性差异设计一组参数ki,这样在异构环境下能够通过心跳信息了解不同节点的负载能力。
任务队列的承载能力是JobTracker给队列分配任务的主要依据,可通过该队列所拥有的资源节点负载能力进行计算,即式(2):
3.2.2 动态优先级Pri
为了避免小作业在队列中长时间等待,对优先级计算方式进行改进,得到式(3):
其中,Twait表示作业在队列中的等待时间,Tres表示作业需要的资源量,由式(3)可以看出,作业的优先级会随着在队列中等待时间的增加而提高,同时考虑到了小作业优先执行的情况,作业需求的资源比越小,则优先级越高。
3.3 算法描述
基于心跳反馈的Hadoop动态负载均衡调度算法描述如下:
Step1:计算队列承载能力QL与当前并行的作业数TaskNum,若TaskNum达到最大并行作业数maxTask则转到Step10,否则转到Step2;
Step2:JobTracker将作业放入QL值最大的队列中;
Step3:遍历队列,根据Pri优先级进行作业排序;
Step4:计算各健康节点的负载能力NL,选出NL最高的健康节点;
Step5:判断该节点是否满足队列中一个作业的执行资源需求,满足则转Step6,否则转到Step9;
Step6:检查该节点的TaskTracker启动记录与任务失败记录,判断该节点是否健康,状态为true则转Step7,为false则转Step8;
Step7:将该节点的资源分配给该作业,转到Step1;
Step8:将该节点的健康状态标记为false,转到Step4;
Step9:将该作业转移至其它队列,转到Step3;
Step10:JobTask停止作业调度,算法结束。
过多的并行作业数量会对JobTracker造成很大负担,因此当并行的作业数量达到maxNum时会终止调度算法。另外,节点的健康与否主要由该节点执行上一个作业的失败次数来判断,若JobTracker检测到该节点在执行同一个任务时失败多次,则会将其标记为非健康节点,暂时脱离集群工作,直到管理员对该节点进行修复后将其重新分配给队列。
4 仿真实验结果与分析
4.1 实验环境与数据
根据实验室条件与设备情况,采用虚拟机搭建了4个节点的Hadoop集群,其中一个节点作为Master,其余3个节点作为Slave。为了体现异构环境,其中两台Slave虚拟主机配置为AMD单核CPU,主频2.9Gz,内存512M,硬盘大小为64G,另一台Slave与Master配置均为AMD双核CPU,主频2.9Gz,内存1G,系统采用Linux Redhat9.0,Hadoop版本为Hadoop1.2,代码编译采用Java jdk1.6.0_24。实验数据使用路透社的14 578条新闻集数据,在集群上运行K-均值聚类算法,聚类中心数设为200[8]。
4.2 实验结果与分析
实验使用DPLB算法与常用的3种Hadoop调度算法分别进行不同数据规模下的聚类分析,通过记录不同调度方式下的运行时间与节点负载情况来分析算法对Hadoop集群负载均衡的效果,结果如图2、图3所示。
从图2可以看出,DPLB算法在Hadoop作业执行的效率上与公平调度算法相当,但要优于FIFO算法与基于容量的调度算法。而在集群节点的负载均衡方面,DPLB算法取得了很好的效果。图3结果显示,DPLB算法在作业执行过程中对资源的占有量较高,究其原因在于实验中采用的数据集是条目较多的小文件,在DPLB的小作业相对优先的调度模式中使得并行的作业数增多,增加了节点压力,但在作业执行的整体效率上有明显提升。
5 结语
本文针对传统Hadoop作业调度模式可能出现的节点负载不均衡,以及资源利用率不高等问题,提出了一种动态优先级的负载均衡调度算法DPLB,通过实验证明了该算法在Hadoop集群作业的执行效率上要高于传统调度算法,并且能够有效实现集群节点的负载均衡。该算法在节点负载优化方面还有很大提升空间,后续将在此基础上重点研究如何降低TaskTracker的通信开销。
参考文献
[1]WHITE T.Hadoop:the definitive guide[M].O'Reilly,2012.
[2]DEAN B J.Mapreduce:simplified data processing on large clusters[J].Osdi’,2010,51(1):107-113.
[3]万聪,王翠荣,王聪,等.MapReduce模型中reduce阶段负载均衡分区算法研究[J].小型微型计算机系统,2015(2):240-243.
[4]关国栋,滕飞,杨燕.基于心跳超时机制的Hadoop实时容错技术[J].计算机应用,2015,35(10):2784-2788.
[5]王峰.Hadoop集群作业的调度算法[J].程序员,2009(12):119-121.
[6]CHEN H,CUI D.SLa-based hadoop capacity scheduler algorithm[C].2015International Conference on Electronic Science and Automation Control,2015.
[7]潘旭明.Map Reduce Fair Scheduler的高性能优化及超大规模集群模拟器设计及实现[D].杭州:浙江大学,2012.
基于负载均衡的云资源调度策略研究 篇2
关键词：云计算；云资源；负载均衡；调度策略
中图分类号：TP315 文献标识码：A 文章编号：1006-8937（2016）29-0079-02
在云计算当中对于资源及任务的调度将会使得云平台的整体性能，以及云服务的运营均会遭受严重的干扰。若对于云资源的管理以及负载均衡不恰当，便会使得在云平台当中并行任务的时候会造成负载不均衡情况的出现，进而使得云平台的整体性能、效率降低，产生极大的资源浪费情况。就这一问题展开相关的研究工作便具有极其重要的作用与价值，应当引起人们的重视与思考，据此下文将基于对云计算与云资源管理的基础理论之上，重点就负载均衡算法进行了深入的研究，进而提出了一类基于负载均衡的云资源调度机制。
1 云计算定义
在云计算技术的基础原理中，是利用网络等级进行划分的，促使海量的应用处理程序可被分解为数个不等的子程序系统，而后在服务器集群当红总开展应用搜索查询，并进而找出合适的应用请求进而针对用户予以处理，最终将所得到的结论反馈至用户。目前对于云计算概念的主流定义包括有：
用户可依据分钟（min）或是秒（s）来进行基础设施的应用时间的规划，而并非传统的天（d）或是周（W），从而便可实现对于资源的高效利用，以避免对资源的浪费。
云型结构是一类并行分布式系统，其通常是采用一系列的联网、虚拟化等计算机来实现不同服务层之间的协同，将计算机资源做到统一运用。
云计算是一项将多方面考量概念予以统一，例如发布，负载均衡，事物及架构模型等，云计算是软件系统的下一逻辑阶段。关于云计算的定义有一个最为简洁的概念，即为“因特网集成软件”。
2 云资源关键技术分析
云计算的发展是基于在长期的发展演变过程当中，对于多种技术手段予以融合之后所产生的一种新技术，其中主要就包括了虚拟化技术、网络计算以及Web2.0等相关技术，从而促使云计算平台的规模愈发庞大，结构也更为复杂，分布更加广泛且种类形式趋于多样化，针对不同的业务需求及商业目标，需设计出具有针对性、高效性的云计算平台资源调度策略算法，当前的分配调度策略主要涵括有先到先服务、负载均衡以及最高效的应用等。提升系统性能以及服务质量是云平台计算的关键性技术指标，而后伴随着云计算技术的持续发展与规模的扩张，使得能源损耗问题日渐严重且广受人们的重视，因而能源损耗对于成本及环境均会产生较大的影响。
在云计算平台资源调度关键技术中重点涵括以下几个方面的内容：
①调度策略：为资源调度管理当中最高等级的策略，需由相关的云平台经营者与管理者予以界限划定。其核心思想是为了明确调度资源的目标及明确在资源相对有限为了满足一切需求时所应采取的处置策略。
②优化目标：对于调度中心而言可应用不同的目标函数来进行资源调度优劣性的判定。当前所普遍应用的优化目标函数具备有满足用户请求最大化、资源利用最大化、利润最大化以及成本最低化等。
③调度算法：最为有效的调度算法是依据当前目标函数所形成的优化结果，不会损耗过多的资源且调度时间相对较短，因目前的调度算法基本都为NP-Hard问题，因此针对调度算法的设计大多选用近似优化的方式。
④调度系统架构：此架构通过云平台的急促结构其联系更为密切，目前云平台的建设大多选用分布式的结构形式，因而调度系统的架构往往也更加偏向于考虑多级分布式结构。
⑤云资源界定与互相制约关系：云平台大多采用虚拟资源并实施集中式管理，因而在实际管理的过程中必须要明确掌握各类资源及其互相之间的制约型关系，从而方可有助于调度算法对各类因素予以均衡。
3 基于负载均衡的云资源调度策略设计
3.1 整体设计框架
在位于云计算平台这一复杂且规模庞大的系统中，对于资源的管理往往会选用相对统一的管理软件，对于云资源采取资源规划，将相关的资源进行整合，而后依据资源所能够提供的服务性能将之划分为普通、高吞吐量、高密度以及相关的特殊资源，如果分类存在明显的差异性，在之后的实践应用当中，亦可在新增资源类型之中针对资源实施分组动态监控实时统计，如此一来也可解决针对预先配置云资源性能较低难以满足用户实际需求的问题。
在云资源及其平台间设置一个策略池，将相应的策略在此之中采取集中式的管理方式，在其内部可具体划分出性能有限、成本优先等策略集合。鉴于云资源相对较多，针对云资源的调度算法通常是为了满足于用户的实际需求所设置出的一类基础算法，同时再加之其他算法的应用，在策略池当中，应当首先依据服务类型将请求转到所对应的策略集之中予以资源选取，而后再利用负载均衡算法对系统负载予以均衡。之后，鉴于云计算面向服务的特征，首先可将其具体的服务依据所提供的应用类型予以划分，其中主要就包括有大数据量应用、大访问量应用以及大存储量应用。对于这三类服务类型，应选用不同的策略予以选取。其整体的框架结构，如图1所示。
3.2 详细设计过程
具体的负载均衡云资源调度策略可通过调度过程进行具体步骤的设计，其中主要就包括有以下几个过程：
①在云服务层，用户请求服务以及系统自动化的服务类型划分；
②将已完成类型划分的服务发送至相应的策略集当中，而后选取出所对应的具体算法内容；
③在经由策略集之中的资源选取之后，再统一实施负载平衡计算，对于系统资源采取负载调整；
④在经由上一环节策略池之中的资源调度后，再到资源池之中寻找相应的匹配资源，为用户实施资源分配；
⑤在用户将所申请的资源释放抑或是暂停应用之后，资源将会即刻回归为空闲资源状态，经由资源的动态化管理实施动态监测以有助于下一次的资源分配。
基于负载均衡的云资源调度过程，如图2所示。
4 结 语
总而言之，伴随着移动网络技术的快速发展云计算技术也已经表现出了强劲的发展势头，相应的云计算平台应用也愈发广泛且深入，然而伴随着云计算技术的快速发展，云平台的稳定性以及用户应用需求越来越高，对于云平台性能要求也随之升高，因而，云平台的设计工作也日渐趋向于完善，对于云平台的负载均衡以及资源调度设计工作其重要性自然也就更加关键。本次研究重点就目前云计算的发展及相关的关键技术予以了深入的分析，而后对于云计算所引出的基于负荷均衡的云资源调度策略及算法进行了细致分析，并基于此设计出了一种基于负载均衡的云资源调度策略。
参考文献：
[1] 张海洲.基于利用率和负载均衡的云资源调度算法研究[D].哈尔滨：哈 尔滨工业大学，2013.
[2] 柳红日.面向SLA和负载均衡及能耗的多目标云资源调度研究[D].哈 尔滨：哈尔滨工业大学，2014.
[3] 朱泽民，张青.基于多维QoS和云计算的资源负载均衡调度研究[J].计 算机测量与控制，2013，（1）.
均衡调度 篇3
ERP系统集成了先进的信息技术与管理思想, 为企业合理调配资源、最大化创造社会财富提供了坚实的基础。伴随着企业的不断发展壮大, ERP系统的规模及复杂性可能成倍增加, 而在信息化的背景下, 企业的各种业务也越来越多依赖于系统的运行。如何提高系统性能, 以更高的效率和更强的能力响应市场供求关系的变化便成为ERP系统实施与运维过程中需要重点考虑的问题。伴随着业务的发展, 系统将产生一批热点资源, 针对这些资源进行操作的进程将频繁产生或者以较大的数量并发产生, 这将导致与热点资源相关的网络节点成为系统瓶颈。那么, 如何在保证正常业务不受影响的前提下, 通过有效的进程调度策略达到系统负载均衡便具有重要的研究价值。
Stankovi提出的基于神经网络的全局动态物理负载均衡算法、Bryant提出的动态局部物理分布的次优算法以及Barak提出的全局动态负载均衡算法, 所针对的都是资源的复制与扩散问题。Hac提出了一种综合考虑文件与进程的负载均衡算法, 但复杂度较高, 无法适用于动态的实时环境。Hurley的方案仅以响应时间最小作为目标函数, 算法所考虑的因素局限性较强。在大型ERP系统中, 如若不进行良好规划, 负载不均衡现象更易出现, 所以有必要对系统实施负载均衡处理以提高其性能。均衡操作可以在不同的系统层次上进行, 如物理硬件层、网络传输层与应用层等。本文的研究目标是在已有的系统配置下, 不改变端系统和网络的底层硬件设施, 仅通过对应用程序进程进行合理调度, 从而使整个系统的运行性能达到更高水准, 因此, 重点研究应用层上的负载均衡算法。
1 问题模型及描述
负载均衡策略的指导思想是通过对应用程序进行适当调配, 达到对资源的优化利用, 以及实施并行运算, 来提高系统吞吐量, 缩短任务响应时间。其算法一般分为集中式和分布式两大类。在集中式算法中, 系统一般设置一个全局的汇聚节点, 存储整个网络的有关信息, 并负责监控其他各节点的负载情况, 再根据一定的策略发起全局的均衡操作。此类算法实现简单, 较适合中小规模的应用系统。但由于汇聚节点需要知道全局信息, 随着节点数的增加, 算法性能受端系统处理能力与网络带宽的影响增大, 从而使汇聚节点本身成为整个系统的瓶颈。而在分布式算法中, 无需设置全局性的汇聚节点, 各节点独立计算自身的负载信息, 并按照某种既定策略触发均衡操作, 所以避免了集中式算法在大规模应用的情况下复杂度较高和易发生单点失效的不足。根据上述分析, 提出了一种基于进程调度的动态负载均衡算法 (Load Balancing Algorithm based on Process Scheduling, LBAPS) , 该算法采用分布式策略, 所有节点均可在重载发生时发出均衡操作请求, 在进程调度层面与系统中其他节点协同完成均衡操作, 从而用较少的操作代价达到系统资源的优化配置。
1.1 模型定义
ERP系统网络可以表示为一个二维空间的完全图G= (V, E) , 其中, V是顶点集合, 表示系统中的网络节点, E V×V是边集合, 表示网络节点之间的链路。对于集合V中的每个元素v, 将在其上运行的进程分为两大类, 一类是正在执行的进程, 另一类是等待队列中的进程。Rp (v) 表示第一类进程所要耗费的系统资源, Qp (v) 表示等待队列的长度, 针对这2个指标均设置相应的阈值Rmax (v) 和Qmax (v) 以判断节点是否处于过载状态。
为了细致描述整个系统的负载状况, 这里将参与应用的ERP节点抽象为5种类型, 分别定义如下:
定义1:空载节点集SN={v/Rp (v) =0∧Qp (v) =0}。
定义2:轻载节点集SL={v/Rp (v)
定义3:当前过载节点集SN O={v/Rp (v) ≥Rmax (v) ∧Qp (v)
定义4:将来过载节点集SFO={v/Rp (v)
定义5:过载节点集SO={v/Rp (v) ≥Rmax (v) ∧Qp (v) ≥Qmax (v) }。
对于处理单元的颗粒度, 这里将其规定为若干进程合集的一个常数值UP, 假设前提是系统处于正常运转状态, 安全防范措施到位, 从而排除出现干扰或者恶意进程的可能性。另外, 还假设进程调度的过程可以平滑地进行, 当进程被调度到新的系统节点时, 其对资源的访问不受影响。
1.2 目标函数
LBAPS算法的出发点是通过合理的进程调度, 将进程从相对过载的节点迁移到相对轻载或者空载节点, 那么可以近似认为在某一个时间区间内, 系统的总负载量与平均负载量保持不变, 则从全局负载均衡的观点出发, 定义算法的目标函数如下:
式中, xv表示节点v的负载量, 表示系统负载量的算术平均值, 其表达式如下:
式中, |V|表示系统中参与应用的节点数。
2 LBAPS算法设计
2.1 进程调度规则
作为一种动态算法, LBAPS必须能够实时监控系统中各节点上负载的动态变化情况, 以及时调整进程分配, 合理优化节点上的资源利用, 要避免对正常的工作进程产生影响, 或者说要尽可能将影响降到最小。同时作为一种分布式算法, 系统中不存在任何集中引导节点, 每个节点均处于平等地位, 能够独立运行算法, 发起负载均衡操作, 所以为了避免由于算法的无规则运行以及进程的频繁往复迁移造成整个网络的拥塞与抖动, 定义如下进程调度规则。
规则1—过载节点发起调度规则
IF (v∈SO) &&IF (SN≠Φ||SL≠Φ) , v发起进程调度请求。
规则2—相对过载节点等待发起调度规则:
IF (v∈SNO∪SFO) &&IF (SN≠Φ||SL≠Φ) , IF (SO==Φ) v, 发起进程调度请求。
ELSE, 等待一个时间片。
以上两2个规则, 其总的前提是系统中存在轻载或空载节点。当出现过载节点时, 由过载节点直接发起均衡请求;当出现相对过载节点时, 它们将等待系统中的过载节点完成操作后再发起进程调度请求。本文为了方便描述, 忽略了对节点间交互动作的描述, 而在实际应用中, 所有集合信息与执行状态的获取可通过在线消息机制来实现。
2.2 负载均衡过程
如上所述, 负载均衡操作由系统中的过载节点与相对过载节点发起, 进程调度的方向为从 (相对) 过载节点向轻载或空载节点迁移, 结束条件为经过计算得到了目标函数F (V) 的近似最小值, 或者系统中不存在 (相对) 过载节点或不存在轻载节点与空载节点。算法伪代码如下:
其中, L为一预设常量, 其含义是在L次连续的计算中, 均不能优化目标函数的取值, 则在此情况下, 算法认为在当前网络环境下, 已无法通过进程调度策略对节点v进行负载均衡操作。
从上述伪代码可以看出, LBA-PS的执行过程主要包括内外两重循环。假设系统包含n个网络节点, 则外循环遍历所有过载节点与相对过载节点的复杂度为O (n) , 内循环虽然每次都随机地选取轻载或空载节点, 但显然其复杂度亦为O (n) 。故对于节点规模为n的系统, LBAPS算法的时间复杂度为O (n2) 。
3 实验及结论
本实验比较的是无负载均衡和启用LBAPS负载均衡2种模式下瓶颈节点占节点总数百分比的差异, 所谓瓶颈节点即定义3、4、5中所描述的集合元素。首先, 在二维平面上产生一定数量的节点, 为每个节点产生Rp (v) 和Qp (v) 。其中Rp (v) 抽象为并发进程数, 取值范围是[5];Qp (v) 抽象为顺序进程数, 取值范围是[20, 40]。同时, 每个节点还将一次性地产生各自的Rmax (v) 和Qmax (v) , 取值范围分别是[1,2]和[4]。其次, 按一定的频度为每个节点产生△Rp (v) 和△Qp (v) , 用来更新节点的Rp (v) 和Qp (v) , 2个△值的取值范围分别为[-2, 2]和[-10, 10]。图1中, 在每个节点规模下均产生10次△值, 之后通过执行LBAPS来比较瓶颈节点率的不同;图2中, 将节点规模固定为50, 通过△值产生次数的不同来比较2种模式下系统性能的差异。从图中不难看出, 实施了LBAPS策略后, 系统的整体性能显著提高。
4 结语
从进程调度的应用场景出发, 讨论了ERP系统负载均衡问题, 提出了一种动态的分布式负载均衡算法LBAPS。该算法不设置全局唯一的汇聚节点, 避免了集中式算法复杂度高以及易产生单点失效的问题。理论分析及仿真实验结果表明, 算法能够以较低的时间复杂度达到显著的负载均衡效果, 故而较适合应用在大规模节点的业务场景中。在接下来的工作中, 首先需要进一步研究进程迁移的代价问题, 避免因进程迁移带来额外的系统负担, 从而抵消甚至超过均衡操作所带来的收益;其次, 需要研究处理单元的颗粒度问题, 过大的颗粒度可能在系统中造成新的过载节点, 而过小的颗粒度又会在节点间产生频繁的进程迁移动作, 同时也增加了系统的通信开销;第三, 需要对文中所提出的节点状态模型进行更加细致深入的探讨, 从而使得抽象的模型更能反映现实应用的本质;第四, 还要研究进行资源迁移或者复制的有效机制, 使进程迁移能够平滑地进行, 从而减少对上层应用产生的影响。
摘要：针对ERP系统负载均衡问题展开研究, 提出了一种基于进程调度的分布式动态负载均衡算法LBAPS。通过对参与应用的节点进行合理分类, 算法制定了进程调度的若干规则, 系统节点在这些规则基础上协同进行均衡操作。理论分析指出, 算法运行的时间复杂度为节点规模的平方阶。仿真实验结果表明, 相对无负载均衡的系统, 本算法可以带来显著的优化效果。
关键词：ERP系统,进程调度,负载均衡,动态
参考文献
[1]Stankovic J A, Sidhu I S.An adaptive bidding algorithm for process, clusters and distributed groups[A].Proceedings of International Conference on Distributed Computing Systems[C], New York, NY, USA:IEEE, 1984:49-59.
[2]Bryant R M, Finkel R A.A stable distributed scheduling algorithm[A].Proceedings of International Wire and Cable Symposium[C], Los Alamitos, California, USA:Comput Soc Press, 1981:314-323.
[3]Barak A, Shiloh A.A distributed load-balancing policy for a multicomputer[J].Software:Practice and Experience, 1985, 15 (9) :901-913.
[4]Hac A.A distributed algorithm for performance improvement through file replication, file migration and process migration[J].IEEE Transactions on Software Engineering, 1989, 15 (11) :1459-1470.
[5]Hurley R T.File migration and file replication:a symbiotic relationship[J].IEEE Transactions on Parallel and Distributed Systems, 1996, 7 (6) :578-586.
[6]Wu Ming, Sun Xian-he.A General Self-adaptive Task Scheduling System for Non-dedicated Heterogeneous Computing[A].Proc.Of the IEEE International Conference on Cluster Computing[C].IEEE Press, 2003:354-361.
[7]梁根, 秦勇, 郭小雪, 等.基于动态多处理节点的分布式系统任务调度[J].计算机工程, 2009, 35 (9) :31-36.
均衡调度 篇4
随着Internet迅速发展, 信息化已经深入到各行各业。随着信息化的深入普及, 越来越多的Web服务器需要面对更高的访问量和数据量, 同时对系统提出了更高的要求, 大多数都要求系统24小时工作。然而随着访问人数的增加, 服务器反应能力下降, 会造成客户端事务处理超时。在单个服务器的情况下解决这类问题通常是升级主机, 但是单个主机的能力总是有限的, 当有大量请求的情况下可能使用更好的主机也无法解决问题, 而且购买高性能主机的成本是非常昂贵的。服务器集群由于其成本低和可扩展性好作为解决这类问题的有效方案, 选择好的负载均衡算法成为保证服务质量的关键。本文在研究现有的负载均衡调度算法的基础上, 针对Web服务器集群负载均衡的特性, 在一致性哈希算法[1]和基于临界加速递减动态负载均衡算法[2]的基础上, 提出了基于临界加速递减的一致性哈希负载均衡算法 (CHDMC) , 并根据Web服务器负载均衡的特性对算法进行优化和改进, 最后通过实验验证了该算法的有效性。
1 国内外研究现状
Web服务器集群是通过高速网络将相互独立的一组服务器互相链接起来, 对于访问者来说这一组服务器是一个单一的整体, 保证Web服务器集群效率的关键是Web服务器负载均衡调度算法。
目前经典的负载均衡算法有轮循算法、加权轮循算法、随机分配算法方面和动态反馈调度等[3,4,5]。在负载均衡调度算法改进的研究方面, 文献[6]结合系统资源类型和服务器权重系数, 依据服务器加权负载标准差, 进行真实服务器负载状况分析, 动态调整服务器权重系数, 对改进的最小链接算法进行调度, 实现负载均衡;文献[7]结合静态权重轮循算法和动态负载均衡, 提出一种自适应的综合动态负载均衡算法, 解决分布式文件系统的负载均衡;文献[8]提出了一个双层分配器负载平衡模型, 解决Web服务器负载均衡问题;文献[9]通过分析已有的负载均衡算法, 提出一种改进的动态反馈负载均衡算法, 调度器定时接收集群中每台服务器上报的性能参数, 计算每台服务器当前负载比例值, 根据该值计算每台服务器的分发权重, 以合理分配用户请求。
当服务器请求增加到一定量时, 响应时间的变化会出现抖动现象, 表明服务器即将进入饱和状态, 我们定义出现抖动现象到负载饱和状态这一负载区为临界区。临界加速递减MDC (Multiplicative Decrease in Critical area) 负载分配算法是通过增加进入临界区负载率, 防止服务器进入负载饱和的策略。为了保证负载均衡器具有较高的转发效率, 分配器不对每个请求任务本身的负荷进行分析, 而是动态监测请求任务被分配后对各个服务器工作负荷造成的影响;通过反馈服务器实际的工作负载状态, 再结合设定的服务器固有处理能力, 负载均衡器计算出每台服务器当前的负载率以及平均负载率。根据服务器应分配与之能力相匹配的负载的原则, 在后续的分配中, 对高于平均负载率的服务器减少分配给它的请求任务数量, 对低于平均负载率的服务器增加分配给它的请求任务数量, 以达到负载均衡的目标。
然而, Web请求任务对系统资源的消耗不仅与链接数量有关, 还与链接类型、所需资源类型、请求内容等多方面因素有关, 动态网页链接请求要涉及到数据库的并发访问和对数据库响应结果的综合处理, 其链接响应时间就远比读取一个静态文件或者HTML页面长, 这就要求负载均衡器需要实时地了解后端服务器节点的负载情况, 目前动态负载分配算法都是在负载均衡器分配之前分析服务器的负载状况进行负载调度, 这样会影响负载均衡器的转发效率, 从而会导致服务器集群总体效率下降。为此, 本文提出一种结合一致性哈希算法和临界加速递减算法的动态负载均衡算法, 该算法结合静态负载分配算法和动态负载分配算法的优点, 在Web服务器集群负载均衡方面有很好的效果。
2 本文算法分析
2.1 本文算法的设计思想
为了尽可能地提高Web服务器集群的服务质量和请求反应速度, 要求负载分配算法能够确保用户请求均衡分配的同时不影响请求分配速度。本文算法结合了一致性哈希负载分配算法和临界因子加速递减动态请求负载分配算法的优点, 做到“能者多劳, 均衡分配”的同时也不影响负载均衡器的分配效率, 算法流程如图1所示。
本文算法的设计思想是:一个任务请求到来时, 先通过加权一致性哈希算法计算出该任务所分配的服务器节点, 然后判断分配的服务器节点的负载率是否超过集群的平均负载率, 如果没有超过则把该请求分配给服务器节点, 如果超过则执行负载转移模块, 将该请求分配到集群中负载率最小的服务器节点, 当请求返回时负载衡器通过临界因子加速递减动态请求负载分配算法计算该服务器节点的负载率和集群的平均负载率。
2.2 加权一致性哈希算法中哈希函数的选取与实现
一致性哈希算法的基本算法本思想是, 采用哈希函数计算出服务器节点的哈希值, 然后将其放在一个0～232的环上, 再根据每个请求的关键字的值 (这个值可以是请求的IP地址、URL等) , 通过哈希函数将该请求的关键字的值映射到环上某个点, 如果该点没有映射到服务器上, 那么顺时针查找, 直到第一次找到有映射服务器的节点, 该节点就是确定的目标节点, 如果超过了232仍然找不到节点, 则命中第一个机器节点。如图2所示, 比如H (K) 的值介于A～B之间, 那么命中的机器节点应该是B节点。
采用基本一致性哈希算法进行后端服务器节点映射在实际应用中具有一定的局限性。因为服务器节点在环上的分配完全是随机产生的, 所以存在一定的概率造成服务器节点的分配不均衡, 使得整个集群负载不均衡。
针对以上问题本文采用了虚拟节点分配法优化系统性能。本文优化算法中, 虚拟节点的总数为N, 真实服务器映射的基本单位Ω, 则服务器虚拟节点的总数是Q=N·Ω (log (N) ) [10], 分a配给单个服务器的虚拟节点的个数为Q (i) =i·Q (其中aAi是第i个服务器节点的资源数, A=∑ai) , 然后采用一致性哈希的原则, 以虚拟服务器节点作为分配的基本单位, 沿着环为每个真实服务器节点分配虚拟节点。
本文采用的是MD5函数作为地址映射函数, 服务器虚拟节点的哈希值由MD5函数通过计算得到, 并且完成寻址, 服务器虚拟节点加入到环上的伪代码如下:
上面的流程大概可以这样归纳:node.Getn Copies得到每个真实服务器节点的虚拟节点个数, 四个虚拟节点为一组, 以getKey For Node方法得到这组虚拟节点的关键字, Md5对关键字编码后, 每个虚拟节点哈希值对应Md5码16个字节中的4个, 组成一个long型数值, 该值作为这个虚拟节点在环中的惟一Key。本算法中哈希函数的索引值为4字节, 这样虚拟节点的总数为232。
有了服务器虚拟节点在环上的分布后, 查找服务器节点的方法和基本一致性哈希算法类似, 当一个HTTP请求到来时, 通过Md5算法将HTTP请求的关键字映射到环上某个点, 如果该点没有映射到服务器上, 那么顺时针查找, 直到第一次找到有映射服务器的虚拟节点, 该节点就是确定的目标节点, 如果超过了232仍然找不到节点, 则命中第一个虚拟节点, 最后通过虚拟节点映射真实的服务器节点。
2.3 动态均衡服务器负载能力的表示及测定
(1) 固有负载能力的测定
确定动态负载均衡算法, 服务器负载能力的测试是关键, 本文是利用Apache JMeter对服务器负载进行检测, 测试配置:线程数1 500个, 时间间隔10 s, 循环次数5次, 结果如图3所示。
图3中横坐标表示发送请求个数, 纵坐标“实线”表示请求成功个数, “虚线”表示服务器响应时间 (以毫秒为单位) , 从图3中可以看出当请求达到5 500个左右时, 服务器请求成功率会突然降低, 并且持续一段时间, 这是系统软件为防止死机而采取的一种措施, 也称“拒绝服务”或“假死”现象, “假死”会对服务器的性能产生严重影响, 因此必须避免这种现象发生。我们认为出现假死时服务器已经处于饱和状态, 从上图可以看出这台服务器“假死”时服务器的响应时间为3 250 ms, 记个时间为Tmax, 当服务器的响应时间超过Tmax, 则服务器的可用资源为零;从上图可以看出服务器的最小响应时间为58 ms, 记这个时间为Tbas, Tbas就是系统维持运转的基本负载;从图3还可以明显看出当请求达到一定量时服务器的响应时间会出现“抖动”现象, 出现抖动的临界时间为1 649 ms, 记这个时间为Tcir, 我们定义从临界时间到服务器“假死”的区域为“假死”前的临界区, 这一区间为Tcir～Tmax。
(2) 动态负荷的表示及计算
由于用户请求任务对系统资源的消耗不仅与链接数量有关还与其他因素有关, 实时了解Web服务器集群中后端服务器节点的负载情况是将请求合理分配的前提, 下文给出了动态负荷表示的相关定义和计算。
定义1固有负载能力LoadCapacity (i) , 表示第i个服务器节点的固有资源数。
定义2服务器的当前负载Load (i) , 表示第i个服务器节点当前所使用的资源数。
定义3服务器负载率Resource (i) , 表示第i个服务器节点资源的利用率:
其中n为集群中服务器的个数, 当服务器负载均衡时有:
定义4在系统维持基本负载前也就是响应时间小于Tcri, 该服务器的当前负载可以定义为响应时间的函数, 该函数可以通过建模得出:
定义5递减因子α, 当服务器的响应时间进入临界区间时, 为了避免服务器进入“假死”状态, 我们必须减轻服务器的负载, 为此我们定义服务器负载率增加部分为递减因子α, 加入后服务器负载率的计算公式为:
算式中, 为服务器的临界深度, 由于每台服务器的临界深度不一样, 我们设置参数β来调整其递减的速度 (通常β的值为2) , 有了递减因子就可以主动控制服务器不出现“假死”状态[11]。
负载均衡器的主要作用是通过负载均衡算法转发HTTP请求到后端服务器节点, 服务器节点的负载率的计算是本文算法的关键, 由式 (2) 至式 (4) 可以得出服务器节点负载率计算公式:
由式 (5) 可以看出, 当一个HTTP请求成功返回到负载均衡器时, 我们可以通过请求响应时间t计算该节点的负载率, 为了确保Tbas、T cri和Tmax不受环境的影响, 我们统一由负载均衡器对后端服务器节点测试, 测得每个后端服务器节点的Tbas、T cri和Tmax作为参数事先写入负载均衡器。
计算完服务器节点的负载率后, 我们要计算服务器集群的平均负载率, 根据负载率的计算公式我们可以推导出平均负载率AveraRes的计算公式:
2.4 算法实现
当一个HTTP请求到达负载均衡器时, 负载均衡器首先将该请求加入到负载均衡队列末尾, 当请求队列中该请求前面的请求都已经分配完时, 负载均衡器通过加权一致性哈希算法, 计算出请求的哈希值 (其中请求关键字的值为请求的源IP地址, 可以确保同一个用户的请求能够分配给同一个后端服务器节点) , 找到对应的后端服务器节点, 然后判断在分配的后端服务器节点的负载率是否超过集群的平均负载率, 如果没有超过则将请求分配给该服务器节点, 如果超过了平均负载率, 将该请求分配给服务器集群中负载率最小的后端服务器节点, 负载均衡器记录该请求的转发时间, 以便当该请求返回到负载均衡器时, 通过请求返回时间和请求转发时间的差计算服务器节点的负载率, 负载均衡算法具体实现伪代码如下:
本算法通过改进的加权一致哈希算法分配后端服务器节点, 请求源IP地址最为关键字计算哈希值, 确保同一用户的请求分配到同一个后端服务器节点, 减少了用户会话转移的次数, 通过临界因子加速递减动态请求负载分配算法, 在请求到来时先将请求分配给后端服务器节点, 当请求返回时再通过请求响应时间计算服务器节点的负载率, 保证了后端服务器节点负载均衡的同时提高了请求转发的效率。
3 算法性能测试与结论
为了测试算法的性能, 根据现有的条件, 对所实现的负载均衡算法进行了性能测试。测试环境一台负载均衡器、后端三台真实服务器和一台数据库服务器。集群系统配置如表1所示。
测试环境的网络为高速局域网, 测试工具采用的是Apache Jmeter, 用加权轮询算法 (WRR) 、临界加速递减 (MDC) 与本文所实现的算法性能进行比较。测试请求是用户登录系统操作, 该请求不仅有静态页面, 还有数据库操作, 属于动态请求, 通过Apache Jmeter反馈的数据, 分析了请求的平均响应时间和请求成功数做了测试, 测试结果如图4、图5所示。
从图4可以看出当并发请求大于25 000个时, 本文算法平均响应时间要小于WRR算法和MDC算法, 并且随着并发请求个数的增加本文算法相对其他两种算法优势比较明显。从图5可以看出当并发请求个数不断增加时本文算法的请求成功率明显要比前两种算法高, 其中WRR算法成功率最低。测试结果表明本文算法不管是在请求成功率还是平均响应时间上相对于原有的算法有明显的提升。
4 结语
本文综合一致性哈希调度算法和基于临界加速递减动态负载均衡算法的优点, 结合Web服务器集群的特点, 提出了一种基于加权最小连接数调度的一致性哈希负载均衡算法, 在计算服务器负载率时加入了临界递减因子, 主动防止服务器进入“假死”状态。通过测试表明本文算法在负载均衡性能上有明显的提高, 本算法在Web服务器集群系统中具有非常广泛的应用前景。
参考文献
[1]Karger D, Lehman E, Leighton T, et al.Consistent Hashing and Random Trees:Distributed caching protocols for relieving hot spots on the world wide web[C]//Proceedings of the 29th Annual ACM Symposium on Theory of Computing, EI Paso, Texas:ACM, 1997:654-663.
[2]郭成城, 晏蒲柳.一种异构Web服务器集群动态负载均衡算法[J].计算机学报, 2005, 28 (2) :179-184.
[3]Dias D, Kish W.A scalable and highly available web server[C]//Compcon 96.Technologies for the Information Superhighway Digest of Papers, 1996:85-92.
[4]Cardellini V, Colajanni M, Yu P S.Dynamic load balancing on Webserver systems[J].Internet Computing, IEEE, 1999, 3 (3) :28-39.
[5]Casalicchio E, Tucci S.Static and dynamic scheduling algorithms for scalable Web server farm[C]//Parallel and Distributed Processing, 2001.Proceedings.Ninth Euromicro Workshop on, 2001:369-376.
[6]刘斌, 徐精明, 代素环, 等.基于Linux虚拟服务器的负载均衡算法[J].计算机工程, 2011, 37 (23) :279-287.
[7]张聪萍, 尹建伟.分布式文件系统的动态负载均衡算法[J].小型微型计算机系统, 2011, 32 (7) :1424-1426.
[8]王志晓, 牛强.基于双层分配器的Web服务集群负载平衡解决方案[J].计算机应用, 2006, 26 (2) :307-309.
[9]王春娟, 董丽丽, 贾丽.Web集群系统的负载均衡算法[J].计算机工程, 2010, 36 (2) :102-104.
均衡调度 篇5
关键词：无线传感器网络,低占空比,多任务,负载均衡,NP完全问题
0 引言
无线传感器网络(WSN)[1]在环境监测、结构监测、栖息地研究等跨时较长的领域具有巨大的应用潜力。为了解决传感器节点供能有限和要求系统寿命较长这一矛盾,许多研究建议无线传感器网络工作于低占空比模式[2,3]。低占空比无线传感器网络大大地延长了网络的寿命,但同时只有极短的时间供传感器接收数据。于是,低占空比工作模式无法避免地产生了两个问题:(1)如果刚好在其极短的可用时间内,多个节点向同一节点发送数据,则会导致严重的传输拥塞问题,进而导致分组丢失,降低网络性能。(2)由于传输拥塞,单跳传输时延变长,导致节点可能无法获得足够的带宽及时将收到的数据分组转发出去。在高速数据应用情况下,数据分组很可能由于缓冲器溢出而丢失。
如果网络中存在多个数据转发任务,则这两个问题可能会更加严重。如果传输调度设计不当,则网络转发能力在时间和空间层面将会无法得到有效利用。为了对具有时间约束的多数据转发任务进行协调,需进行细致的任务调度,根据负荷调度表,实现传感器的负荷平衡。然而,当前在低占空比无线传感器网络多任务调度性能提升方面研究不多。如何在时间约束条件下就给定的数据传输请求,确定最优调度方案,以实现负荷在传感器节点中的均匀分布,这一问题仍然没有解决。因此,在本文中,对低占空比无线传感网络多任务调度问题展开深入研究,并提出高效算法,以对任务进行调度,实现传感器均衡使用。
1 相关工作
人们已经就无线传感器网络调度算法展开了广泛研究,试图尽量减少通信时延,避免冲突,提高能源使用效率或公平性。Lu等人[4]研究了在每个传感器有占空比要求或平均只在1/K时隙内保持活跃状态的情况下,如何实现通信时延最小化[4];文献[5]提出了一种可以降低数据聚集应用时延的启发式调度算法;Gandham等人提出了一种可以实现无冲突调度的分布式边缘着色算法[6];Chipara等人[7]针对高数据率传感器网络应用,提出了一种称为动态无冲突查询调度(DCQS)的新的调度算法[2;Yu等人针对无线传感器网络数据聚集,提出一种无冲突分布式调度算法[8];Rao等人提出了一种实用性很强的分布式算法[9],计算出基于时隙的调度表后,可以为多跳无线网络提供端到端最大—最小公平性;Tan等人对时延约束条件下的分布式机会调度(DOS)算法展开研究,在两种不同类型的平均时延约束下实现吞吐量最大化[10]。
文献[2,11,12,13,14]对低占空比无线传感器网络的数据传输机制进行了研究。在文献[2]中,Guo等人对带有不可靠链路的低占空比无线传感网络机会泛洪技术进行了研究;文献[11]提出了一种新的无线传感器网络异步MAC协议(PA-MAC)。PA-MAC通过采用接收方发起数据传输机制、异步占空比机制以及节点唤醒时间估计机制,降低了节点的工作占空比,提高了网络的能量有效性。仿真结果表明,在保持网络性能的前提下,PA-MAC能够进一步降低节点工作的占空比,进而减少节点的能耗。文献[12]提出了一种动态数据发送协议DDF(dynamic data forwarding),它将异步占空比和实际的链路模型结合在一起。在DDF中,每个节点先选出一个候选节点集合,然后再把数据包发给集合中先醒来的节点,从而可以降低端到端的时延,保证包成功发送率和提高网络寿命。Gu等人[13]提出一种部分节点提升占空比算法,同时就汇节点布置提出一种方案,可以为通信时延提供实时化保证。文献[14]提出了一种动态数据转发算法(DSF),并在低占空比无线传感网络上进行了实验。本文工作不同于以上工作,不是为了避免冲突而对各条链路分开调度,而是综合考虑了多数据传输任务的负载均衡和时间调度问题。
2 网络模型和问题描述
2.1 网络模型
本文中,传感器网络被看成是一个无向图G(V,E),其中V表示传感器节点集合,E表示节点间无线链路集合。为了节约能量,节点工作于低占空比模式,节点V的工作周期V被划分为多个等时长的时隙。在每个工作周期中,节点V只在一个时隙内开启无线电设备,以接收数据,这一时隙为节点V的活跃时间,用Hv表示。在其余时隙内,节点V均处于休眠状态,直到自己发送数据为止。假设传感器节点已经同步[1],有相同的工作周期T,且每个节点提前知道相邻节点的活跃时间。
为简便起见,时隙长度设为1,并且看成是最短时隙。一项任务需要明确从源节点发出数据传输请求,通过给定路径,将数据发至目的节点。考虑网络中有n个任务,每个任务TASKi(1≤i≤n)表示为<vsi,vdi,PATHi,NODEi,Di>,其中vsi和vdi分别表示源节点和目的节点,PATHi和NODEi分别表示从vsi至vdi数据传输路径的边和节点,Di是任务的时间约束。如果节点u生成数据或在时隙j接收数据,则任务数据可在时隙j从节点u单跳传输至节点v,其中i≤j≤i+P且P为单跳时间约束。
时间调度表S记载了传感器节点的数据接收时间。具体地,安排表中的S(i,j)表示节点vj∈NODEi{vsi}接收任务TASKi数据的时间,S(i,di)表示任务TASKi的时延。如果对vp→vq∈PATHi有S(i,p)≤S(i,q)≤S(i,p)+P且S(i,di)≤Di,则判定S可行。确定时间安排表S后,节点vi在时间j时的负载为vi在时间j时收到的所有数据,表示为w(i,j)。为简便起见,任务TASKi的时间安排表也可表示为vsi→vki(tk1)→…→vdi(tdi),其中括号中的tj表示节点vj从数据传输路径上一节点处接收数据的时间。很显然,tdi=S(i,di)。图1展示了总线型拓扑结构低占空比传感器网络,网络任务是将节点v0的数据传输给v3。在时间1时生成数据,然后在时间2、2、4,数据发至v1,v2,v3。请注意,如果v0在时间3接收了其他数据,则这些数据无法在时间T内发至v3,原因是对v0→v1→v2→v3路径上的节点,在范围内没有合法的非降序时间序列。如图1所示。
2.2 问题描述
负载均衡(LB)问题可描述为:设无线传感器网络的工作周期为T,单跳时间约束为P,活跃时间Hvv∈V,有n个任务<vsi,vdi,PATHi,NODEi,Di>且1≤i≤n,现欲确定时间安排表S,以将每个时隙内的节点最大负载最小化。设x(i,j,k)为1—0整数变量,表示任务TASKi的数据是否在时间k被节点vj收到。
设1≤i≤n,有D*=max{Di},且w(j,k)=∑ni=1x(i,j,k),目标是实现以下吞吐量的最大化:
条件式(2)是保证每个任务的数据只来源于任务相关节点。条件式(3)用来约束各节点在睡眠状态时的接收数据能力。条件式(4)保证每个任务的数据在时间Di内能够沿着路径传输至目的地。条件式(5)用于约束每个任务的数据能够在P时延内通过逐个节点得以转发。w(j,k)表示节点vj在时间k的负载。
图2为负载均衡问题一个示例。(a)为网络拓扑结构及任务;(b)为T=5,P=D=8时的活跃和休眠节点;(c)最大负载W(S)=2时的最优调度方案,在时间3出现于节点v3,在时间5出现于节点v6。部分节点只有一次机会接收数据,比如说v1和v4,而其他节点有两个时隙可以接收数据,比如v3和v5。最大负载为2的最优调度表见图2(c),该调度表可以表示为:
不同的调度安排会导致不同的最大负载。例如,如果任务TASK2的时间安排变为v2→v3(3)→v5(3),则最大负载升为3。
3 基于树结构的多任务调度算法(SAT)
首先考虑如下负载均衡问题:所有任务的目的节点均为vs,路径构成一个根为vs的有向树(见图3(a)所示)。即:如果两条路径在节点v处交汇,则该两条路径以v为起点的其余部分完全相同。这种情况经常出现于传感器节点通过路由树采集数据等实际应用场景。本节中,出于简便,假设P=D*。
引理1对任一最优时间调度S,vs在某个时刻的负载等于W(S)。
证明假设任意时刻vs的负载均小于W(S),则必有节点Vj和时刻k满足w(j,k)=W(S)。既然vs是任务的唯一目的地,vj在k时接收到的数据最终将在p(p≤1)个时隙(t1,t2,…tp,ti<tj,1≤i<j≤p)内到达vs。因为vj在k时接收到的部分数据在时间t1到达vs,于是沿着路径存在一个从k至t1的节点活跃时间非降序列。因此,也有从kq至tq的非降活跃时间序列,且对2≤q≤p有kq=k+(tq-t1)。这表明vj在kq接收到的任何数据都可在时间tq传输给vs。因此,对vs将在tq(2≤q≤p)时间接收到的数据w(s,tq),可以把vj接收这些数据的时间从k时推迟至kq时。这一操作无需交替传输w(s,t),1≤t≤D*,就可生成一个可行的时间调度。
假设以上操作之后vj的负载是w'(j,k),由于vs可能从vj以外节点接收数据,因此有w'(j,k)≤w(s,t1)。此外,w(s,t1)<W(S),因此有w'(j,k)<W(S)。对k=1 to D*,如果w(j,k)=W(S),执行相关操作,当所有操作结束后,vj的最大负载小于W(S)。
最后,所有节点按拓扑次序执行相关操作。对节点u,只有它的所有子节点负载均衡之后,它自己才能负载均衡。由于拓扑结构是树结构,这一次序可以保证,u的负载无法通过操作被上层节点交替均衡。因此,这一过程完成后,除vs外的所有节点的最大负载均小于W(S),这与先前假设矛盾,证毕。
在树结构下,于时间k推迟其他节点向节点vj发送数据,以保证更新过后的负载w'(j,k)不大于w(s,t1),此时vs的负载保持不变。
引理1表明,如果能够找到一个可以实现vs最大负载最小化的可行性调度方案,那么这一调度方案总体来说也是最优的。本文设计了一种多项式时间算法SAT(树形布局调度算法),该算法的主要过程是:首先,为vs计算一张任务表,记载每个任务在数据准备阶段有多少时间可用于时间调度;然后计算vs负载再分配最优方案,在负载最小化步骤中,实现vs最大负载最小化;最后,在调度生成步骤,获得针对所有节点的可行性调度方案。
算法的主要思路是使用贪婪策略,在每列之和阈值为k的条件下,确定一个可行的调度方案。如果将任务表转化为优先级队列Q,则算法在时间i(i=1 to m)时调度任务数量小于等于k。具体地,如果在最先时间i,Q中任务数量小于等于k个,则在i时调度所有任务,并从Q中提取出所有任务;否则,在i时只调度和提取前k个任务,且其余任务的最早时间变为i+1。如果该步骤结束时一些任务仍没有被调度,算法会返回“假”;否则返回“真”及一个节点vs可行性调度方案A,其中A(i,j)=1表示在vs的第j个活跃时间调度了第i个任务。具体步骤见算法1伪代码。
算法1 SAT算法
算法1最多可以调度n个任务,每次调度需要O(n)次Q提取和更新操作,每次操作耗时为O(logn)。因此,贪婪算法的时间复杂度为O(n2logn)。另外,该上界是紧上界。最坏情况下,对1≤i≤n,有TASKi.e=1且TASKi.e=m(m≥n),同时k|n=0。算法在第i时间调度k个任务,需要n-(i-1)k次提取和更新操作,因此运行时间为:
引理2当且只当存在阈值为k的可行性调度方案时,贪婪算法才会返回“真”。
限于篇幅,引理2的证明在此略去。根据引理2,W(S)是让贪婪算法返回“真”的最小阈值k。因此,通过从范围1至n对k进行对分搜索,可以确定W(S)。负载最小化步骤需要O(nlogn)的时间来建立优先级队列,并在对分搜索每一步调用算法1,于是这一步的时间复杂度为O(n2logn)。
在调度方案生成步骤中,根据计算出来的节点vs的调度方案,这一步对其余节点的任务进行调度。考虑到对任务TASKi(1≤i≤n),有vp→vq∈PATHi,结点vq接收数据的最早时间是te(i,q)=min{t|t≤te(i,p)且vq在时间t处于活跃状态}。设在te(i,q)时间调度结点vq(vq≠vs),以接收任务TASKi的数据,而vs在它第j个活跃时间(不小于时间te(i,s))接收TASKi的数据。通过这种方法,可以获得最优方案。
定理1设有n个任务,及有m个节点的导出树,SAT算法可在O(mn2log2n)时间内计算出最优调度方案。
证明根据引理1和2,SAT算法计算出的最优方案S,对1≤t≤D*,有W(S)=w(vs,t)。在上文讨论中,数据准备步骤和负载最小化步骤分别需要时间O(mn+nlogn)和O(n2log2n)。因为方案生成步骤需要为树中每个节点调用一次算法1,因此它的时间复杂度为O(mn2log2n),是SAT算法运行时间的主要组成部分。证毕。
4 一般情况下的调度算法
在一般的负载均衡问题中,任务路径图不一定是树形结构。本节将证明,负载均衡问题是完全NP解题,然后给出一种近似算法及性能分析。
4.1 负载均衡问题的难度
考虑一种额外约束条件下的特殊的负载均衡问题(LBS问题):(1)T1=T2=…T|v|=T=1;(2)P=0,表明必须同时对NODEi节点进行调度,以接收TASKi的数据;(3)D1=…=Dn=3,即每个任务调度的延时不得大于3。
设存在一个由12个节点图和6个任务构成的约束组件。节点表示为A至K,6个任务的路径为PATHA=A→G→I→L,PATHB=B→G→J,PATHC=C→G→k L,PATHD=D→H→K PATHE=E→H→I,PATHF=F→H→J→L。任务的调度时间分别表示为tA,tB,tC,tD,tE,tF。使用约束组件是为了强制规定,在W(S)=1方案中,为TASKC和TASKF分配的时间相等,如引理3所示。
引理3当且只当tA=tD,tB=tE,且tC=tF时,才存在W(S)=1的6个任务调度方案S。
证明如果方案S有W(S)=1,则:(1)由于NODEA∩NO-DEB∩NODEC={G},因此tA≠tB≠tC;(2)因为NODEB∩NODEF={J},因此tB≠tF;(3)因为NODEA∩NODEF={L},因此tA≠tF。根据以上3个结论及tA,…,tF∈{1,2,3},于是有tC=tF。此外,NODEA∩NODEE={I},因此tA≠tE,进而tA=tD且tB≠tE。相反,如果tA=tD且tB=tE且tC=tF,设tA=tD=1,tB=tE=1,tC=tF=3,可以看出,一个节点在每个时隙期间最多从一个节点处接收数据,因此得出的方案S有W(S)=1。
定理2 LBS问题是NP完全问题
证明假设包含n个任务的LBS问题及对应方案S,结论W(S)>1可用规模为n的多项式时间加以证明。因此,LBS∈NP。然后,构建多项式时间归约,将可着色图问题(G3C)归约为LBS问题,因为G3C是NP完全问题[15],因此LBS问题也是NP完全问题。
4.2 一种启发式算法
既然问题是NP完全问题,提出一种称为SAG(普遍适用的调度算法)的启发式算法。主要思路是:首先计算一个初始安排方案,此方案下每个任务中的节点都会尽快地把数据转发给下一个单跳相邻节点,然后延迟部分节点的任务时间,以降低当前最大负载。
如图2所示,SAG算法的输出是时间调度方案S,用每个任务TASKi和节点vj∈NODEi的I(i,j)表示,意思是节点vj在其第I(i,j)个活跃时间时接收到TASKi的数据。知道S(i,j)表示v接收数据的时间,将I(i,j)转化为S(i,j)可表示为S(i,j)=time(I(i,j))。
首先,SAG算法计算节点vj接收TASKi数据的活跃时间的最小值I(i,j)。其次,节点vj在其第t个活跃时间的负载,设置为第t个活跃时间被调度的任务数量。然后,SAG算法继续寻找在k时间负载等于当前最大负载的节点vj,接着确定TASKi和延时δ,以便节点vj接收数据的时间可以被推迟至其第(I(i,j)+δ)个活跃时间,进而降低w(i,j)和W(S)的值。这里使用了两种操作:(1)任务TASKi在路径PATHi中节点vj和vj的后继节点的所有时间都被推迟了δ;(2)任务TASKi在路径PATHi中节点v的先前节点的所有时间都被推迟了δ。
算法将检查:(1)是否time(I(i,di)+δ)≤Di,即Vdi的推迟时间不大于Di;(2)是否time(I(i,j)+δ)-time(I(i,p))≤P,其中vp→vj∈PATHi。如果都是的话,且操作(1)有效,即经操作(1)改进过后的调度方案的最大负载得以降低,则SAG将执行操作(1)。此外,如果执行了操作(1)且操作(2)有效,则SAG算法执行操作(2)。
如果没有操作可以执行以降低W(S),则SAG算法终止。因为检测部分任务能否推迟δ时间需要耗时O(|V|2D*n),且一次操作至少可以使一个I(i,j)上升δ≥1(对各任务TASKi和vj∈V,1≤I(i,j)≤D*)),所以SAG算法终止需要时间O(|V|3D*2n2)。
算法2 SAG启发算法
5 仿真实验
为了评估本文算法的性能,利用TOSSIM[16]模拟器,在多种网络配置下,进行了全面的实验仿真。使用网络吞吐量作为主要指标,该指标计算方法为:
此外,实验还记录了任务延时,传感器节点存储溢出,及任意两个节点间的传输损失。为便于比较,实验也在转发任务数据时使用了“尽力”策略(BST)[2,3]。仿真结果既表明了开发高数据率多任务高效调度算法的迫切必要性,也证明了本文算法可以显著提升网络性能。
5.1 实验配置
实验中,在100 m×100 m方形区域上随机布置30~100个传感器节点,采用默认发射功率。时隙长度设为2秒,每个节点的工作周期T设为20个时隙,于是得出一个占空比为5%的网络。开始时,每个节点在各自工作期间从[1,T]内选择一个时隙作为其活跃时间。
仿真主要考虑第4节讨论的任务导出树情景。由CTP等路由协议构建路由树,然后根据路由树确定任务路径。对于普通情况下的任务,通过探测消息在固定长度的图上随机游走来构建路径。考虑参数包括:(1)网络规模N;(2)任务时间约束D*;(3)数据率R,用每个任务的分组数据来衡量;(4)节点的缓冲区大小B。
5.2 网络规模的影响
本实验中,网络节点数量设置为30、50、100,除汇点外的每个传感器任务由100个分组组成。每个任务的时间约束设置为100,缓冲区大小设置为100个分组。随着网络规模增大的实验结果显示于图4所示。在图4中,可以看到,SAT算法下的网络吞吐量远高于BST算法。
SAT算法下的任务平均时延大于BST算法(见图5)。但是两种算法的时延都小于时间约束D*=100。结果表明,SAT算法以增大时延为代价提升网络吞吐量。为进一步分析网络吞吐量下降的原因,实验统计了缓冲溢出和传输损失的时间。图6表明,随着网络规模增大,缓冲溢出和传输损失也会增大。图6的白色柱体代表传输损失,可以看出,当N=30和N=100时,BST算法下的溢出分组数量小于SAT,而BST算法的分组损失数量大于SAT,导致性能下降。当网络规模变大时,两种策略下的缓冲区平均使用率均会上升(见图7),且差异很小。
5.3 数据率的影响
改变每个任务的分组数量可以改变数据率。数据率上升时,拥塞和存储负载上升,进而网络吞吐量将会不可避免地下降。如图8所示,SAT算法的网络吞吐量几乎是BST的两倍。图9表明,SAT算法下的任务平均延时总是高于BST。当数据率从10上升到200时,分组丢失和缓冲溢出均会上升。BST的分组丢失要远高于SAT,而SAT的缓存溢出要略过于BST(见图10)。这些结果表明,当N=30时,SAT可以较低的缓存占用率,有效缓解时隙期间的传输拥塞(见图11)。
5.4 用户设置参数的影响
在实际应用中,用户可能需要为不同的任务提供不同大小的缓冲区,设置不同的时间约束。为了研究这两个用户参数的影响,实验考察了不同配置下的网络吞吐量。图12结果表明,SAT对时间延时约束更加敏感,而时间延时对BST算法下的网络吞吐量影响甚微。当可用缓存大小上升时,SAT下的网络吞吐量也会稍微上升,而BST会保持稳定,甚至当B=200时下降(见图13)。
5.5 SAG性能
最后,测试了本文SAG算法的性能。可以看出,网络规模变化时,SAG算法下的网络吞吐量上升了将近20%(见图14)。此外,当数据率变化时,SAG性能始终优于BST(见图15)。与图5结果相比,网络吞吐量下降得更慢。原因是因为与任务特性有关,也就是说,普遍情况下的任务数据流,比树形拓扑结构分布得更加均匀,因此传输拥塞和缓存溢出程度更低。
5.6 不同方案的性能比较
为了更好地体现本文方案的优越性,将本文的SAG方案与DSF方案和DDF方案在平均延迟方面进行了比较。实验结果如图16所示。可以看到,随着网络规模的增大,三种方案的平均延迟都在降低,其中本文方案和DSF方案的平均延迟要明显低于DDF方案。仔细分析其原因可知,这主要是由于在DDF中,每个节点需要先选出一个候选节点集合,然后再把数据包发给集合中先醒来的节点。这会导致两个问题:1)候选节点集合的计算将耗费较多的系统资源开销,且容易受到节点分布的影响;2)当网络中节点总数增多时,如何从众多的集合元素中选择最先醒来的节点将变得更加困难。这些都会增加DDF方案的数据传输延迟。
仔细观察图16还可以发现,本文方案(SAG)的延迟要稍稍低于DSF方案。这是因为SAG方案能在时间约束条件下就给定的数据传输请求,确定最优调度方案,以实现负荷在传感器节点中的均匀分布,因此当有多个数据率要求高、时间紧的数据传输任务时,SAG方案的性能表现更优。
6 结语
