数据调度算法（精选8篇）
数据调度算法 篇1
1引言
目前,光纤网络、移动无线网络发展迅速,利用基础网络资源实现了云计算,其可以将分布于世界各地计算机终端、服务器连接在一起,利用分布式计算、透明计算、移动计算等技术,提高人们工作、生活和学习的信息化水平。 云计算技术长期的使用,已经积累了海量的数据资源,因此降低了人们搜索的有效性,也降低了数据搜索的实时性,为了提高数据存储调度效率,可以基于智能分级存储策略设计一个新的数据存储调度算法。
2云计算环境下数据存储调度算法设计
云计算环境中, 为了能够提高数据存储调度的效率,为用户提供更加的数据搜索利用体验,数据存储调度算法包含的关键功能包括六个方面,分别是元数据管理、文件估值、迁移控制、访问重定向、文件系统监视、数据迁移。
(1)元数据管理。 云计算环境中,为了保证数据的原子性、完整性,可以使用云数据进行描述,实现数据的迁移和访问重定向。
(2)数据对象估值。 数据对象估值可以根据数据资源访问频次、数据容量、读写模式、创建时间等属性对数据对象进行估值,以便能够反馈数据文件的访问量和活跃程度,进行数据迁移。
(3)数据迁移控制。 云计算环境下,用户访问数据对象时,可以根据数据对象估值实时的、动态的改变数据对象存储位置,以便能够将热点数据赋予较高的存储优先级位置,便于用户访问,提高资源命中率。
(4)数据访问重定向。 云计算时代,网络数据能够为用户提供透明的、分布式的服务,因此无论用户在哪个地方,只需要记住数据访问的逻辑地址,无需关系存储器的物理地址,如果数据物理地址发生改变,比如迁移到其它地方,使用数据访问重定向功能即可寻找到数据。
(5)文件系统监视。 文件系统监视可以实时的统计存储系统运行状态,计算系统延时、存储空间利用率、读写比例、文件访问命中率等,并且将这些辅助信息提供给迁移控制模块。
(6)数据迁移。 数据迁移可以放置在相关的迁移计划列表中,记录迁移数据的大小、存储位置、创建时间、 访问频次,同时采用相关的算法将数据迁移到合适的目标位置,数据迁移的主要目的是实现数据存储优化。
数据存储调度算法可以根据用户访问数据频次,将数据资源放置在不同的设备, 实现数据的自动化迁移, 以便提高数据的命中率,算法执行流程如图1所示。
3云计算环境下数据存储调度算法关键技术
数据存储调度算法在实验过程中,其关键技术包括三种,分别是数据分类技术、数据放置技术和数据迁移技术。
(1)数据分类技术。 云计算的快速发展积累了海量的数据资源,这些数据资源根据不同的分类标准,可以划分为文档数据、视频数据和图像数据等。 随着数据分类标准的不同, 不同定义和标准下数据的分类是不同的,数据分类是数据迁移的最基本条件。 目前,随着数据划分技术的快速改进,已经诞生了贝叶斯理论、聚类、神经网络、K均值、支持向量机等,可以将数据根据人们的需求动态的进行分类,更好的保存在不同类型的数据库中,以便人们访问。
(2)数据放置技术。 网络存储系统中,数据放置可以采用相关的原则,针对系统中新添加的数据、被迁移的数据放置在某一个特定的位置上, 数据放置可以采用更加科学的方法,直接影响数据读取、写入等访问操作效率, 影响用户使用感知。 网络数据放置存在两个关键技术:一是确定数据放置在何种类型的存储介质上; 二是数据放置的形式,随机放置、顺序放置或文件分割放置等。
(3)数据迁移技术。 云计算环境下,由于用户访问数据是一直动态变化的,因此数据访问频次均是在动态改变的,为了能够提高数据访问效率和命中率,需要根据网络存储的数据和相关的指标进行数据迁移。 数据迁移常用的技术包括同级数据迁移和异级数据迁移两种模式。 同级迁移模式能够根据相关的存储系统硬件容量的大小, 将集中出现在相关的存储系统中数据进行迁移, 目的是均衡各个存储设备的负载。 异级迁移模式则是在存储系统中经常发送的时间,可以更好地优化数据存储内容,实现自动化的迁移,异级迁移过程能够提高低性能存储设备向高性能存储设备的数据迁移,同时也可以向相反的方向迁移。
4结束语
云计算环境下,数据存储调度算法可以实现数据动态的、分布式的、透明的访问、读写数据资源,提高数据资源访问速度,同时能够保护数据的安全性,确保云计算时代网络存储系统能够满足人们的需求。
参考文献
[1]于珊珊,陈冬林,李伟等.基于SLA的云计算多数据中心任务调度算法[J].武汉理工大学学报:信息与管理工程版,2014,3:345-349.
[2]肖艳文,王金宝,李亚平等.云计算系统中能量有效的数据摆放算法和节点调度策略[J].计算机研究与发展,2013,S1:80-82.
[3]王强,李雄飞,王婧.云计算中的数据放置与任务调度算法[J].计算机研究与发展,2014,51(11):2416-2426.
数据调度算法 篇2
关键词：光突发交换,数据信道调度算法,丢包率
1 引言
随着宽带视频、多媒体业务的日益增长, 对传送网带宽和交换系统容量要求越来越高。目前DWDM技术, 使一根光纤上可利用带宽达到10 Tbit/s左右, 可以满足较长时间内对传送网带宽的要求。然而光电路交换继承了电路交换技术, 采用双向资源预约方式为源、目的节点之间建立光通路连接, 为每次数据交换传输设置固定的波长信道带宽, 数据交换完后释放光通路, 交换粒度粗, 带宽利用率低。光分组交换可达到较细的交换粒度, 在带宽利用率、延时和适应性等方面比较好, 但实现比较复杂, 而且光逻辑处理技术不成熟, 没有可用的光随机存储器。
光突发交换 (Optical Burst Switching, OBS) 结合了光电路交换和光分组交换的优点, 又克服了两者的不足, 易于实现, 能很好地支持突发业务, 并且具有适中的交换粒度和较高的带宽利用率, 因此成为当前最具有发展潜力的光交换技术。
在OBS网络中, 基本交换单元是突发, 突发是由相同的出口边缘路由器地址、具有相同服务质量要求的IP分组组成。OBS的特点是:突发数据分组 (DB) 和控制分组 (BHP) 的传输在物理信道和时间上是分离的, 控制分组提前于突发数据分组发送, 而突发数据分组等待一定时间 (偏置时间) 后, 不需等待回复确认信息, 直接在预先确定的信道上发送。在核心节点上, 控制分组经过光/电/光交换和电信息处理, 为相应的光突发数据分组预留资源, 使突发数据分组实现全光透明传输。
2 数据信道调度算法
在OBS网络中, 核心节点根据到达的BHP中包含的信息为后续到达的数据包DB安排合适的数据信道—信道调度。即当相应的BHP到达核心路由器后, 选择一条在DB到达光交换矩阵时可用的数据信道作为输出信道。当没有可用信道时, DB以及相应的BHP将被丢弃。因此在OBS网络核心节点处设计信道调度算法主要需要考虑以下两个方面: (1) DB的丢失率; (2) 算法执行时间。一个理想的调度算法应该在DB到达前, 能够尽快地处理相应的BHP, 并尽可能为该DB找到合适的信道。一个有效的调度算法可以通过快速地调度来降低DB的丢失率, 并且提高网络带宽的利用率。
2.1 最近可用信道算法 (LAUC)
首先假设每个光核心路由器有B个FDLs, 第i个FDL可以延时Q i1 (≤i≤B, Q0=) 0, 其中Qi=i×D (D为延时单元) 。假设不考虑交换时间, 不使用FDL的情况下, DB到达光交换矩阵的时间和离开的时间相同。
最近可用信道算法[1]只保留每个输出数据信道的最近使用时间 (LUT, Last Used Time) , 对于有K个数据信道, 令tj表示第j个信道的最近可用时间。LAUC算法的基本思想是为到达的数据突发选择最近可用未调度数据信道, 假定DB到达核心节点的时刻为t, DB的长度为L (用时间表示) , 调度器首先寻找在t时刻空闲的数据信道 (即tj
LAUC算法简单, 容易实现。调度器对每个数据信道只要获取一个参数—LUT。缺点是DB之间的空隙没有很好的应用, 使其链路利用率很低。FDL缓存的存储容量不仅取决于FDL的数目, 还取决于每个FDL的长度。因此FDL的延时单位D越大, 引入的空白越大, 信道利用率越低。为解决这个问题, 可以考虑采用具有空白填空的算法。
2.2 最近可用信道-插空算法 (LAUC-VF)
图1 (a) 中D1信道两个数据突发之间的空白信道容量没有被利用。LAUC-VF算法与LAUC算法相似[2], 只是LAUC-VF算法中新到达的数据突发可以填充信道的空白。假设持续长度为L的DB到达光核心节点的时间为t, 调度器首先查找在 (t, t+L) 时间内是否有可用信道。如果至少有一条可用信道, 调度器将选择一条最近可用的信道来传输DB。
图2是LAUC-VF算法示意图。5个数据信道中, 其中D1、D2、D3和D5在t时刻是可用的未使用信道。因为数据信道D3空隙太小, 无法容纳一个DB。由t-t2
2.3 FAFA算法
FAFA算法 (First-Arrival-First-Assignment) 与LAUC-VF算法相似, 调度器都是将最近可用信道分配给数据突发。但是FAFA算法是按照数据突发到达的顺序分配信道[3], LAUC-VF算法是按照BHP到达的顺序分配信道。当BHP在t时刻到达时, 在FAFA算法中, 调度器暂不为相应的突发分配信道, 而是等到数据突发到达之前的△时刻 (tsch=ts-△, ts是数据突发到达时刻) 。因此在 (ta, , tsch) 之间到达的数据突发, 不会由于其相应的BHP到达得晚而在信道分配上处于劣势。
图3比较了两种不同的波长预留方式。各种算法都是尽可能填充空白, 即任何波长信道都应该没有被占用或几乎被突发占用而没有任何时间间隙, 使其信道利用率提高。从图3 (b) 可以看出最上面的一个信道被3个新到的突发占用, 空白利用率很高。而图3 (a) 中第5个信道被第2个到达的突发占用, 虽然最上面的信道还没有被完全填充。这是因为LAUC-VF是按照BHP到达的顺序分配信道, 这样就使得到达晚的突发在到达早的突发之前传输, 造成第2个突发不能在信道1上传输, 使空白没有充分利用。
2.4 BHP收集调度算法
以上几种算法都是针对单个BHP或单个DB进行信道调度的, 而在核心节点处数据突发到来的顺序是无序的, 所以无法预知前后数据突发到达的时间, 可能对当前的BHP或DB来说, 该次调度是最合理的调度, 但对后续到达的BHP或DB, 该次调度为不合理调度。因此会造成数据信道使用不合理。为了使数据信道更加合理地利用, 因此提出一种BHP收集调度算法, 该算法的基本思想是:对一组BHP按其对应的数据突发DB到达的先后顺序来调度数据信道。
该算法是在核心节点的数据突发波长信道上按照数据突发到来的时间顺序划定某一时间窗口, 该时间窗口称为收集周期。收集周期可以固定配置, 也可以根据业务量情况动态调整。这个收集周期也是BHP缓冲的最大时间。当BHP到达一个空的缓冲区时, 标识该BHP为触发BHP, 并设置定时器的值为0, 启动定时器, 随后到达的BHP, 根据其突发到达的时间先后顺序插入队列中去, 当定时器的值等于最大缓冲时间时, 就把那些排在触发BHP前面的BHP和触发BHP作为一批BHP, 根据数据突发的偏置时间和长度, 采用LAUC-VF调度算法进行调度和处理, 调度其对应的DB到可用的数据信道。由于该算法需要对控制包进行队列缓存, 为保证突发端到端的延时, 对每一个BHP需要设置最大缓存时间OFF Time (即收集周期) , 通常OffTime>N/μ (N表示缓存的大小, μ是BHP的平均到达率) [4]。一旦位于队首的BHP在缓存中的停留时间超过了OFF Time, 即使没有新的BHP进入队列, 它也必须离开。因为该算法在收集周期内得到一组BHP, 可以收集更多信息, 并按照DB到达的顺序进行调度, 从而可以有效地调度突发, 极大地降低数据突发的丢失率。同时收集周期的大小也是影响性能的一个因素, 收集周期越大, 获取的BHP数量越多, 因此获取的信息越多, 调度越合理。然而业务对时延有一定的要求, 故对BHP的收集周期不能太大。并且一定要保证BHP比相对应的突发数据包先到达。由于收集周期是和偏置时间紧密相关的, 而偏置时间的确定又与业务所能忍受的最大延时、边缘节点的缓存深度以及突发数据通过核心节点的数目等因素的限制。假设最大偏置时间LOFFSET, 数据通过的核心节点数目为HMAX, 那么在一个核心节点处, BHP的最大延时为LBHP=LOFFSET HMAX。我们用TBHP来表示BHP在一个核心节点停留的总时间, 因此TBHP应小于LBHP, 收集周期的选择不能超过TBHP时, 才能保证该算法的实现。
如图4所示, A-G表示7个数据突发所对应的各自BHP, 而从A-G也表示为核心节点所规定的BHP收集周期, 这样它们所对应的数据突发在本节点的突发窗口时间段为 (TSTAR, TSTOP) 。从图中可看出, 如果按照一般的调度算法 (无FDL) , 则仅有A、C这两个数据突发能够成功调度。但是如果集中考虑, 统筹规划调度, 则{B、E、C}、{D、E、C}、{A、C}、{G、C}等4组数据突发可以成功调度输出, 因此提高了调度效率, 减少了数据突发丢失率。
3 性能比较
为了比较几种算法的突发包丢失率性能, 我们用OPNET软件进行了仿真实验。实验中假设光路由器有17个波长 (1个控制信道, 16个数据信道) , 其传输速率均为10 Gbit/s。在本仿真实验中, 突发的到达时间设定为指数分布, 突发长度设定为Guass分布, 因此可以获得一个以指数分布时间到达以及一个正态分布的突发长度[5]。
图5显示了业务负载为0.5～1.0时, 几种算法的突发丢失率的变化情况。可以看出, 业务负载增大, 突发丢失率也增大。但是LAUC算法的突发丢失率最大, 因为它不能填充每个信道上已调度数据突发间的空白。BHP收集调度算法的丢失率最低, 尤其在轻载的情况下有良好的性能, 因为它能更加合理地利用信道资源。
4 结论
从上面论述和仿真结果可以看出, LAUC算法简单, 容易实现, 但信道利用率最低, 突发丢失率最大;LAUC-VF算法可以填充数据信道间的空白, 因此信道利用率比LAUC算法要高, 丢包率有所改善。FAFA算法是对LAUC-VF算法的进一步改进, 使其信道利用率可以更高。而提出的BHP收集调度算法一次对多个BHP对应的数据突发进行集中调度, 实现了对已预约资源的优化, 使信道资源利用率更进一步提高, 从整体上降低了网络丢包率, 使网络性能得到提升。
参考文献
[1]Tumer J.Terabit burst switching[J].JHS, 1999, 8 (1) :69-84
[2]Xiong Y, Vandenhoute M, Cankaya H.Control architecture in optical burst switching WDM networks[J].IEEEJSAC, 2000, 18 (10) :1838-1851.
[3]Xu J.Efficient channel scheduling algorithms in optical burst switching networks[J].Proc INFOCOM, 2003, 3:2268-2278
[4]Saravut Charcranoon, El-Bawab Tarek S, Cankaya Hakki C, et al.Group-schediling for optical burst switching networks[A].GLOB ECOM’03[C].San Francisco, USA:IEEE, 2003, 5 (1-5) :2745-2749.
短作业优先调度算法 篇3
姓名：陈凯
学号：541413430202
地点：四教楼301
指导老师：张旭
专业班级：嵌入式软件14-02
实验名称：短作业优先调度算法
一、实验目的：
测试数据可以随即输入或从文件中读入。必须要考虑到作业的到达时间
最终能够计算每一个作业的周转时间。
二、实验内容：
模拟实现短作业调度算法，具体如下：
设置作业体：作业名，作业的到达时间，服务时间，作业间的链接指针 进程初始化：由用户输入作业名、作业的到达时间和服务时间进行初始化。显示函数：
1、显示当前调度的是哪个作业，后备队列中有哪些作业
2、最终显示每个作业的作业名、到达时间、服务时间、完成时间和周转时间
排序函数：对就已到达的作业按照服务时间进行排序。注意考虑到达时间 调度函数：每次从已到达的作业队列队首调度优一个作业执行。删除函数：作业结束后撤销。
三、实验代码
#include
char name[10];//进程名
floatarrivetime;//到达时间
floatservicetime;//服务时间
floatstarttime;
//开始时间
floatfinishtime;//完成时间 floatzztime;//周转时间 floatdqzztime;
//带权周转时间 };
sjf b[100];
//定义短作业优先算法进程的最大数量 voidSinput(sjf *p,int N)
//输入函数 { int i;
printf(“输入进程的名称、到达时间、服务时间:n”);for(i=0;i<=N-1;i++){
printf(“输入第%d进程的名称、到达时间、服务时间:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }
//输出函数 voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;
printf(“n执行顺序:n”);printf(“%s”,p[0].name);
for(k=1;k { printf(“-%s”,p[k].name);} printf(“n进程名tarrivetservicetstarttfinishtzztdqzzn”); for(k=0;k<=N-1;k++) { printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftnn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } } voidSsort(sjf *p,int N) //按短作业优先算法排序 { for(int i=1;i<=N-1;i++)for(int j=1;j<=i;j++) if(p[i].servicetime sjf temp;temp=p[i]; p[i]=p[j]; p[j]=temp;} } //运行结果 voidSdeal(sjf *p, float arrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,int N){ int k; for(k=0;k<=N-1;k++) { if(k==0){ p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime; } else { p[k].starttime=p[k-1].finishtime;//开始时间=前一个进程的完成时间 p[k].finishtime=p[k-1].finishtime+p[k].servicetime; //结束时间=前一个进程的完成时间+现在进程的服务时间 } } for(k=0;k<=N-1;k++){ p[k].zztime=p[k].finishtime-p[k].arrivetime; //周转时间=完成时间-到达时间 p[k].dqzztime=p[k].zztime/p[k].servicetime; //带权周转时间=周转时间/服务时间 } } void SJF(sjf *p,int N){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; Ssort(p,N); Sdeal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); SPrint(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);} void main()//主函数 { int M;printf(“------------短作业优先调度算法-----------n”);printf(“输入作业数:”);scanf(“%d”,&M); Sinput(b,M);SJF(b,M);} 四、实验结果 五、实验总结 通常工作流计算任务可以用一个有向无环图 (DAG, Directed Acyclic Graph) 表示, 其中, 节点表示一个计算任务, 边表示计算任务之间的关系。假设工作流计算任务集合用C={C1, C2, …, Cm, }表示, 云数据中心中的计算节点集合用R={R1, R2, …, Rn, }表示。在工作流计算任务执行时, 必须在计算任务与计算资源之间做一个合理的匹配或映射, 这即是所谓的工作流计算任务的调度问题。设计合理的工作流任务调度算法对于提高计算资源的利用率以及用户的服务质量具有重要意义。为此, 本文考虑工作流计算任务之间的控制依赖特性, 提出了一种基于任务复制的重调度优化算法, 并基于Cloud Sim验证了该算法的有效性。 一、基于任务复制的重调度优化算法 WQR (Work Queue with Replication) 是一种典型的计算任务复制调度算法, 通过在计算任务集合中随机选择一个计算任务调度到某一空闲的或者可用的计算节点上执行。对于某一计算任务来说, 这种调度算法并没有考虑计算任务本身的特性, 因此调度的结果往往造成为该计算任务分配的计算节点并不是最佳的。当系统中出现某一计算节点的计算能力强于目前所分配的计算节点时, WQR实现了一种复制调度策略, 即将该计算任务复制一个副本, 重新调度到计算能力更强的计算节点上执行, 如此可弥补之前非最佳调度造成的性能损失。但采用WQR算法, 在系统中可能同时执行同一个计算任务的多个副本, 造成计算资源的极大浪费。为此, 当某个副本先执行完, 将立即触发其它副本中止执行, 及时释放资源。 本文基于WQR算法的复制思想, 考虑工作流计算任务之间的控制依赖特性, 提出了一种基于任务复制的重调度优化算法, 目的是加速工作流计算任务的执行时间, 同时减少由于执行计算任务的副本造成的资源浪费。算法过程描述如下:1) 根据工作流计算任务之间的控制依赖关系, 将计算任务分层表示, 如图1例子所示, 包括12个计算任务;2) 对于没有先行任务的计算任务, 随机调度到一个空闲或者可用的计算节点上执行, 如果有先行任务, 必须等到先行任务执行完才能起到执行;3) 当所有的计算任务都分配了计算节点后, 如果系统中仍存在其他空闲可用的计算节点, 优先选择具有后续任务最多且没有被复制过的计算任务进行复制, 如果处于同一层内的计算任务具有相同数量的后续任务, 优先选择具有最少副本数的计算任务复制;4) 当某一计算任务的副本数量达到了规定的上限, 但系统中仍存在其他空闲可用的计算节点, 则重复3) 步;5) 如果某一计算任务的某个副本执行完成, 则中止该计算任务其他副本的执行, 释放计算资源。 二、仿真分析 本文在Cloud Sim仿真平台中搭建了一个仿真环境。以图1所示的工作流计算任务集合为例, 选择无复制的调度及WQR算法为比较对象, 分别从任务执行时间及计算资源使用情况两方面来验证上述算法的有效性。 从图2所示的仿真实验结果可以看出, 本文所设计的复制重调度优化算法由于考虑了工作流计算任务之间的控制依赖特性, 在选择计算任务进行复制及副本数量控制方面做了一些优化, 因此任务执行时间优于WQR算法及无复制的调度。但本文所设计的算法与WQR算法均需执行一定数量的副本, 相比无复制的调度而言, 造成了一定的计算资源的浪费。 三、结论 本文研究石油生产云数据中心中工作流计算任务的调度问题。考虑了工作流计算任务之间的控制依赖特性, 设计了一种基于任务复制的重调度优化算法。基于Cloud Sim的仿真实验验证了该算法的有效性。 参考文献 电力调度数据网是现代大型互联电网的重要组成部分,是实现电网调度自动化的基础[1,2]。随着电力系统向数字化方向的发展,电力系统的数据应用逐渐增多[3],对通信技术的要求也越来越多,电力系统传统的通信承载方式越来越难于满足用户的需求[4,5]。因此,将IP网络作为电力调度数据网络的主要数据承载方式,得到极大的发展。然而,由于电力调度数据网的覆盖面积不断增大,承载的业务种类逐渐增多,而由业务突发性引起的网络数据流的不确定性,进而在某一时刻,造成IP网络中某一节点或部分链路发生拥塞是不可避免的。调度数据网一旦出现信息拥塞,将很可能影响调度数据业务的正常运转,危害电力系统的生产管理和安全运行[6]。鉴于此,如何缓解节点或链路拥塞已成为影响电力调度数据网安全稳定运行、管理的关键问题。 拥塞规避是缓解网络中节点或链路拥塞的重要方法,其能有效地规避网络中的拥塞现象、均衡网络中的负载、进而为业务提供高质量的服务。传统的拥塞规避机制一般基于蚁群优化(Ant Colony Optimization, ACO)[7,8]或改进ACO算法[9,10,11,12]实现, 文献[7]中当检测到链路拥塞或即将发生拥塞时,从目的节点发送“拥塞应答蚂蚁”重新探索路径,当 “拥塞应答蚂蚁”到达拥塞节点,表明存在一条新的非拥塞路径。拥塞节点将立即切换到新路径,进而减缓拥塞状态。文献[9]采用与传统ACO相反的信息素引导模式,对信息素的更新引入惩罚和奖励机制,并在此基础上设计了一种能够规避拥塞的Qo S(Quality of Service,Qo S)路由算法求解单播路由问题,同时实现网络负载的均衡。文献[10-11] 在拥塞发生时采用双向蚂蚁寻路的方法,提高了新路径搜索的速度;使用新的寻路准则保障了认知网络的Qo S需求。虽然传统的拥塞规避方法有效规避了链路上的拥塞,但并未合理考虑节点拥塞状态和业务优先级,不能很好地规避节点拥塞。此外,利用ACO重新为低优先级业务选择路由时速度慢, 容易出现早熟收敛和停滞现象。 基于此,以IP网络作为电力调度数据网的主要数据承载方式,针对节点拥塞问题,提出基于业务优先级的拥塞规避算法( Congestion Avoidance algorithm based on the Service Priority, CASP )。首先,根据不同业务对时延和带宽的要求不同,将电力调度数据业务划分为具有不同优先级的6个等级。其次,对严重拥塞节点或中度拥塞节点缓存队列的数据按业务优先级进行位置调整,丢弃位于严重拥塞阈值后的低优先级业务,并通知被丢弃业务的源节点根据二进制粒子群优化(Binary Particle Swarm Optimization, BPSO)算法[13,14,15,16]重新进行路由选择。仿真结果表明,在规避节点拥塞时考虑业务优先级,优先保障高优先级业务的Qo S;丢弃低优先级业务,从而缓解了严重拥塞节点的拥塞程度; 综合考虑最短路径与网络资源,为被丢弃的低优先级业务寻找满足其要求的最优路径,优化了网络资源,均衡了网络负载。 1业务模型分析 随着信息与通信技术的迅速发展,电力调度数据网覆盖范围不断增加,其覆盖范围内设备种类繁杂,数量庞大,因此,业务流量增大,且由于电力调度数据网承载的部分业务具有随机性特点,容易造成网络节点拥塞。为优先保障时延要求较高且带宽需求较大业务的Qo S,在规避节点拥塞时应考虑业务优先级,对不同业务提供有差别的服务。 电力调度数据网承载的业务主要是安全I区、 安全II区和应急指挥系统业务。安全I区业务是以SCADA/EMS等调度自动化系统、安稳管理信息系统等为代表的实时监控业务,安全II区业务是以保护管理信息系统、电能计量遥测系统等为代表的调度运行管理业务[17,18]。当检测出节点发生拥塞时, 为了优先保证时延要求较高业务的Qo S,优先为最大容忍时延小的业务提供服务;此外,为了最大程度地缓解节点拥塞程度,优先确保带宽较大业务得到服务。因此,根据电力调度数据业务对时延、带宽的不同要求,将电力调度数据业务划分为具有不同优先级的6类业务,其中,时延小、带宽大的业务优先级最高。结合以上分析,调度数据网业务等级及优先级划分如表1所示,其中优先级标识Pr越大表示业务的优先级越高,现有调度数据网中宽带时延次敏感业务与宽带非实时业务较少,但随着电力信息通信网的宽带化发展,未来调度数据网承载的业务种类及其带宽需求也随之增加,此两类业务也随之出现。 2电力调度数据网拥塞规避算法 2.1拥塞检测方法 电力调度数据网中节点具有接收数据包和存储转发功能。由于将相邻节点传输过来的数据包存储在节点缓存区,当有大量相邻节点在某一时刻同时传输数据包经过此节点时,会导致节点发生拥塞。 为检测节点在某一时刻的拥塞状态,采用与文献[6] 相同的方法计算节点缓存区的数据包数量,并通过与上限、下限阈值比较进而确定当前节点状态。假设Qi,t表示t时刻节点i的缓存队列长度,Ri H、Ri L分别表示节点i的严重拥塞阈值和中度拥塞阈值, Flagi为节点拥塞状态标识,则检测节点拥塞的具体方法为: (1) 若Qi,t (2) 若Ri L≤Qi,t (3) 若Ri H≤ Qi,t,则表示节点i处于严重拥塞状态,Flagi=2。 2.2拥塞节点的规避策略 当检测到节点发生严重拥塞或中度拥塞时,对节点缓存区队列中的数据包按其业务优先级进行位置调整。假设时刻t拥塞节点i缓存队列中的数据包为具有不同优先级的S1,S2,…,S9,则图1示意了对拥塞节点i缓存队列中的数据按优先级进行位置调整的过程。 对拥塞节点i缓存队列中的数据按业务优先级进行位置调整后,将位于严重拥塞阈值后的低优先级业务丢弃,并发送消息通知被丢弃的低优先级业务源节点为其重新选择路由。由于重新选择路由时需要考虑不同路径的可用带宽和其传输时延两方面因素,则此优化问题为多目标优化问题。由于BPSO不要求被优化函数具有可微、可导、连续等性质, 并且具有收敛速度快,算法简单,容易实现,控制参数少,计算速度快等特点,选择BPSO来求解此多目标优化问题。 2.3 BPSO求解最优路径 2.3.1问题描述 针对电力调度数据业务对通信指标要求的不同,在为其重新选择路由时应综合考虑不同通信指标对业务的不同要求。根据电力调度数据业务对时延与带宽的要求构造相应的目标函数,以获取符合业务通信需求的传输路径。由于路径传输时延和其可用带宽具有不同量纲,缺乏统一的度量标准,难以进行比较和运算,必须对其进行归一化处理。对于路径传输时延,当其大于业务可容忍的最大时延时,不能保证业务的Qo S,因此不能选择此路径传输业务;当其小于可容忍的最大时延时,此路径可作为传输业务的备选路径。假设Dmax表示调度数据业务可容忍的最大传输时延,D(x)为备选路径x上的传输时延,则对路径x上的传输时延按式(1)进行归一化处理。 其中,,D(i)表示路径x上节点i的时延,D(l)表示路径x上链路l的传输时延。 假设以B(x)表示备选路径x的可用带宽, Bmax,Bmin分别表示可选路径集中可用带宽的最大值和最小值,则对路径x的可用带宽按式(2)进行归一化处理。 选择满足式(3)条件的路径x作为传输低优先级业务的最优路径。 其中:约束条件D(x)≤Dmax保证了调度业务在路径x上的可靠传输;B表示请求通信的业务所需带宽, 约束条件B(x)≥B保证了业务所需带宽不超过路径x的当前可用带宽。 2.3.2基于BPSO的路由选择优化模型求解 1)粒子编码 采用二进制粒子群编码方式。取源节点到目的节点的路径作为备选粒子,粒子的维数为m,表示粒子的位置信息,取1或0,分别对应节点是否在该路径上。 2)适应度函数评价 利用三角模融合算子[19]将路径传输时延和可用带宽进行融合,从而建立适应度函数,将多目标优化问题转化为单目标优化问题。适应度函数为 3)粒子更新 首先,将初始化的粒子位置作为粒子i初始的历史最优解Pi,从粒子群中找出适应度值最大的粒子位置作为初始的粒子群当前全局最优解Pg。对粒子i,将其当前适应度值和Pi所对应的适应度值作比较,若优于Pi的,则重置Pi;将Pi所对应的适应度值与Pg所对应的作比较,若其比Pg的更优,则重置Pg。 其次,如果当前全局最优解Pg满足最佳路由条件,则结束并输出当前最优解;否则,根据当前全局最优解和每个粒子的历史最优解更新粒子位置X(C),得到新的粒子群X(C+1)。 假设Xik(C),Vik(C)分别表示第C迭代次数时粒子i的第k维位置和速度,则第i个粒子的第k维速度更新公式为 其中:c1,c2为学习因子;ω 为惯性权重;rand( ) 是在[0,1]范围内的随机数;Pik(C)是至当前迭代次数粒子i经历的最好位置即粒子i的历史最优解;Pgk(C) 是至当前迭代次数粒子群中所有粒子经历的最好位置即粒子群当前全局最优解。 为了增强粒子群跳出局部最优的能力,在 ω 中引入自适应扰动机制。 式中,ωmax, ωmin分别是 ω 的极大值和极小值;L,C分别表示总的迭代次数和当前迭代次数;gmax是扰动因子g的极大值,g的计算公式参考文献[16]。 因此,第i个粒子的第k维位置更新公式为 其中, sig(·) 为sigmoid函数, 通常取sig(x)=1/(1+exp(-x))。 3仿真分析 为验证所提出的拥塞规避算法的性能,使用Matlab7.9仿真平台对CASP算法和未考虑业务优先级的拥塞规避算法的性能进行仿真对比分析。仿真模型为随机生成20个节点的网络拓扑图,并随机生成每条链路的时延和可用带宽。每条链路的可用带宽最大不超过200 MHz,网络时延不超过500 ms, 各个节点缓存区大小为50 MHz。仿真的网络拓扑结构如图2所示,各链路对应的时延和带宽如图标识,其中(D,B)表示链路上的时延(D/ms)和可用带宽(B/MHz)。仿真过程中,设置节点V1~V2为源节点, V18~V19为目的节点。 仿真过程中,随机产生各个节点的初始数据包分布,其业务类型与优先级按照表1所示的业务类型及优先级随机生成。以Ki表示节点i的数据处理能力,参考文献[6],由于实际的调度数据网通常采用分层设计原则,核心层、骨干层和接入层节点的数据处理能力有差异。为简化仿真过程,本文假设拓扑图中各个节点的数据处理能力相同,鉴于业务具有突发性特征,设置仿真场景为某一时刻网络中出现拥塞的场景。参考文献[15],将路由选择优化模型中的参数分别设置如下:c1=2,c2=2,ωmax=0.9,ωmin=0.4,gmax=10,G=10,最大迭代次数为200, 粒子群大小为40。 为验证BPSO算法具有较快的收敛速度,在粒子群大小和蚁群大小相同的情况下,仿真了BPSO算法、ACO算法的收敛特性。图3为分别采用BPSO算法、ACO算法求解从源节点到目的节点的最优路径问题时的收敛特性。可以看出,在粒子群大小与蚁群大小相同的情况下,分别采用BPSO算法、ACO算法求解同源、目的节点的最优路径时,采用BPSO算法能更快的收敛到最优解。 为体现本文提出的拥塞规避算法对高优先级业务需求的保证,对比2个拥塞规避算法。算法1中对拥塞节点缓存队列中的业务按先进先出的顺序进行处理,业务不分优先级;算法2是CASP算法。2个算法中丢弃的位于严重拥塞阈值后的业务均采用BPSO算法重新选择路由。 采用本文提出的拥塞检测方法,对网络中各个节点的拥塞状态进行实时检测,某时刻检测出严重拥塞节点为V9,中度拥塞节点为V3,V7和V13。 表2、表3分别为采用算法1、算法2规避节点拥塞的情况对比。在算法1中,当检测到节点处于严重拥塞状态时,丢弃位于严重拥塞阈值后的业务,并通知被丢弃业务的源节点根据BPSO算法为其重新选择路径。表2表明采用算法1为被节点V9丢弃的业务重新选择的路径与采用算法2时对应业务的路径的时延对比。根据算法1,在节点V9处被丢弃的业务1重新选择的路径为(2,6,12,8,14,15,19),其路径时延为212 ms,而在算法2中此业务的优先级为5,其传输路径和路径时延分别为(2,3,9,15,19)和84 ms。显然,算法1丢弃了时延要求较高的业务, 这是因为算法1中并未区分业务优先级,未对不同业务提供有差别的服务。此外,采用算法1时为丢弃业务选择的路径传输时延高于采用算法2时的, 这表明算法2较算法1为高优先级业务提供更好的服务。表3表明采用算法2为被丢弃低优先级业务重新选择的路径传输时延与算法1中对应业务的路径时延对比。结合表2与表3可知,采用算法2时节点V9处丢弃的业务优先级较采用算法1时丢弃的业务优先级低,并且从表3中可知,在V9处被丢弃的业务3重新选择的路径及其传输时延分别为(1,5,4,10,19)和236 ms,其业务优先级为0,但采用算法1时此低优先级级业务路径及其传输时延为(1,3,9,15,19)和156 ms,显然,采用算法2时选择的路径传输时延高于采用算法1时的,结合对表2的分析可知,采用算法2优先确保了高优先级业务的Qo S需求,对不同优先级业务提供有差别的服务。 4结论 根据不同调度数据业务对时延与带宽的需求不同,对调度数据业务进行了优先级划分。当检测到节点拥塞时,丢弃位于严重拥塞阈值后的低优先级业务,一方面优先保证了高优先级业务的Qo S需求,另一方面缓解了拥塞节点的拥塞程度;与传统的拥塞规避算法中采用的ACO算法相比,BPSO算法的收敛速度更快,节省了运行时间;此外,采用BPSO算法为被丢弃的低优先级业务重新选择路径时,综合考虑备选路径的时延与可用带宽,不仅保证了业务的服务质量,而且优化了网络资源,均衡了网络负载。 摘要：为了保障电力调度数据网的可靠性,提出一种基于业务优先级的电力调度数据网拥塞规避算法。首先,根据不同业务对时延、带宽要求的不同,将其划分为具有不同优先等级的业务。其次,判断节点的拥塞状态,并对严重拥塞或中度拥塞节点缓存队列中的数据按业务优先级进行位置调整,丢弃位于严重拥塞阈值后的低优先级业务,并通知其源节点重新选择路由。最后,建立适应度函数,根据二进制粒子群优化(Binary Particle Swarm Optimization,BPSO)算法进行路由重新选择。仿真结果表明,算法优先保证了高优先级业务的服务质量(Quality of Service,QoS),从而优化了网络资源,均衡了网络负载。 互联网技术的发展,硬件技术和通信技术的进步共同加快了计算机领域的进步。20世纪80年代出现了并行计算,支持同步的算法、程序和体系结构的开发。随后出现了分布式计算,它要求各个处理机之间能够协同计算,通过处理机间的通信共同解决问题。网格计算技术[1]的发展则迎合了21世纪并行与分布式计算技术的发展趋势,它是以资源共享为目的,支持对可计算资源的远程和并发的访问,用高速网络连接的地理上分布的可计算资源所组成的一个具有单一系统映像的高性能计算和信息服务环境。 网格资源包括计算资源、存储资源和通信资源。对于网格用户而言,它向网格系统提交任务,由网格调度程序按照某种调度策略把用户提交的任务分配给网格系统中的可用资源。如何使这些资源高效地完成计算任务是网格系统的研究重点之一。 由于在网格环境下的任务调度主要考虑的是一组相互独立、任务之间没有通信和数据依赖的元任务(metatask)映射。现有的任务调度算法可以分为在线模式(on-line)和批模式(batch-mode)两种。在线模式是任务一到来就加以映射,而批模式则是把任务收集起来等映射事件到来后才对这些任务进行集中映射。相比而言,批模式得到了大量的资源信息,从而可以做出更合理的任务映射策略。在这里讨论的是批处理模式的任务调度,即调度程序的执行周期到时再集中映射。 以时间跨度(makespan)为优化目标的任务—资源映射是一个NP完全问题,解决这类问题常用启发式算法。经典的批模式算法有Min-min、Max-min、Suffrage、遗传算法、蚁群算法等。T.Braun[3]等人通过对一些常用的算法进行了比较,在一定规模时遗传算法所求出的时间跨度要优于其他算法一些,但随着规模扩大,其收敛性降低[4],因此本文提出了将遗传算法和Min-min算法相结合的改进遗传算法的任务调度优化模型,该算法也适合大规模任务的调度,并进行了仿真实验。 1 问题描述 任务调度问题的实质[2]就是在一个有n个需要调度的任务、m个可用的资源(主机或集群) 的网格环境下,把n个子任务J={J1,J2,…,Jn}以合理的方式调度到m个资源R={R1,R2,…,Rm}上去,目的是得到尽可能小的总执行时间,提高系统吞吐量等。具体描述如下: (1) J是n个需要调度的任务集合,Ji表示第i个任务。每个任务的任务量大小用百万指令(MI)表示,且每个任务只能一个资源上执行完成。 (2) R是m个可用的资源集合,Rj表示第j个资源。每个资源的计算能力用百万指令每秒(MIPS)表示。 (3) n个任务在m个不同资源上的预测执行时间ETC( Expected Time to Compute)是一个n×m的矩阵。矩阵中的每一行代表某一个任务在m台资源上的不同执行时间,每一列代表在同一台资源上n个任务的不同执行时间。ETC(i,j)表示第i个任务在第j个资源上的执行时间。 (4) 资源j的最早可用时间为STARTTIME(j)。 (5) 把任务i所需的数据从存储系统传输到资源j上的传输时间为TRANS(i,j)。 (6) 第i个任务在第j台资源上的预测最小完成时间为MCT(i,j),则MCT(i,j)=STARTTIME(j)+TRANS(i,j)+ETC(i,j)。 (7) 任务i的最小完成时间为Ci,当任务分配给第j个资源时,Ci=MCT(i,j)。 (8) 所有任务都执行完成的时间为时间跨度(makespan),即makespan=Max{Ci,i=1,2,…,n}。 2 设计与实现 遗传算法(GA)是Holland于1975 年受生物进化论的启发而提出的,并行性和全局解空间搜索是GA的两个最显著的特点。网格任务调度问题是一个NP问题,在一定规模时,用遗传算法进行网格任务调度能得到很好的性能。Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的时间跨度。遗传算法随着调度规模的扩大,在一定调度时间限制内,它的收敛性会逐渐降低。因此,本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法。 2.1 Min-min算法 Min-min算法的主要思想如下(仍然考虑n个任务,m个执行单元的情况): (1) 对集合中每一个等待分配的任务T,分别计算出分配该任务到m台机器上的最小完成时间,这就得到了一个n×m的MCT矩阵。 当需要调度的任务集合非空时,反复执行以下操作直至集合为空: (2) 利用MCT矩阵,对集合中每一个等待分配的任务分别找到能够最短时间完成该任务的执行单元及最短完成时间,在所有的最短完成时间中找出最小的最短完成时间对应的任务a,设其对应的主机为b,把任务a分配到机器b上。 (3) 从任务集合中把任务a删除,同时更新MCT矩阵。 2.2 染色体的编码与解码 染色体的编码形式有很多种,可以采用直接编码(直接对子任务的执行状态编码)或者间接编码。本文采用间接编码方式,对每个子任务占用资源编码。染色体的长度等于子任务的数量,染色体中的每一位都是正整数,每一位的位置编号代表子任务的编号,而该位置上的正整数值代表该子任务所占用资源的编号。假设有10个子任务,3个可用资源,则染色体串长为10,每个基因的值则为随机产生的3个资源的编号,则可以随机产生了下面的一个染色体编码: {2,1,3,2,2,3,1,1,3,1} 这个染色体代表第一个任务由第二个资源上运行,第二个任务由第一个资源执行,以此类推,第十个任务由第一个资源执行。染色体以数组形式存放。 产生了一个染色体后,还必须对其进行解码,得到不同资源上任务的分布情况。将任务按照占用的资源分类,生成多组按照资源编号分类的任务序列,每个序列的编号就是某一个资源的编号,序列中的元素就是在该资源上执行的任务,这样我们就得到了所有任务在多个资源上运行的分布情况。以上面的染色体为例,解码后产生3个资源的任务序列: R1:{2,7,8,10} R2:{1,4,5} R3:{3,6,9} 这样就可以计算出每个资源完成该资源上分配的所有任务花费的时间,最大花费时间即为时间跨度。 2.3 初始种群生成与适应度函数 在网格环境下,对任务调度的实时性有较高的要求,为提高算法收敛的速度以及改善算法的结果,要求初始种群既具有随机性的个体,又具有一些比较优秀的个体。本调度算法是在Min-min算法基础上,采用遗传算法对其性能进行提高,又可以避免单独采用遗传算法对大规模任务资源匹配的低收敛性。我们可以先将用Min-min算法产生的染色体作为初始种群的优秀个体,再随机产生其他个体。 遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要,直接影响到遗传算法的收敛速度以及能否找到最优解。由于网格调度的目标是时间跨度尽可能小,因此适应度可定义为: fitness(i)=1/makespan(i) 即染色体i的适应度值等于该染色体的时间跨度的倒数。若时间跨度越小,则适应度值越大,被选择的可能性越大。 2.4 个体选择 选择操作是决定父代种群中哪些个体,以及能以多大可能性被挑选来复制或遗传到下一代的进化操作。选择算子以对个体的适应度评价为基础,其主要作用是对搜索提供导向:挑选最优秀个体,使算法避免无效搜索且能快速搜索到问题的最优解。 假设本算法的种群大小为popsize,为了保留优秀个体,先选择Min-min算法产生的个体和父代中的最优个体,其他的popsize-2个个体采用轮盘赌法[5]进行选择。个体的选择概率为: Pi=fitness(i)/∑fitness(j) 需要进行popsize-2轮选择。每一轮产生一个[0,1]均匀随机数,若该数位于某个体累积概率下的那个区间,则选择该个体。 2.5 交叉与变异 交叉的目的是为了在下一代产生新的个体,通过交叉操作,遗传算法的搜索能力能够得以飞跃地提高。这里的交叉算子采用多点交叉,对于m个交叉点的多点交叉,随机选择m个交叉位置,在交叉点之间的变量间续地相互交换,产生两个新的后代,但在第一位变量与第一交叉点之间的一段不做交换,交叉点的个数根据染色体的长度进行选择。多点交叉具有很强破坏性,可以促进解空间的搜索。 变异本身是一种局部随机搜索,与选择操作结合在一起,保证了遗传算法的有效性,是遗传算法具有局部的随机搜索能力,同时使得遗传算法保持种群的多样性,以防止出现非成熟收敛。 这里变异算子实质上就是将某个子任务迁移到另一个资源上执行,为了防止某个子任务在迁移后,执行的时间增大而造成种群退化,规定迁移后子任务占用的资源不是随机产生,而是在除了该子任务目前占用的资源外的资源集合中,选择使该子任务执行时间最短的资源,将其迁移到该资源上执行。 2.6 算法流程 (1) 随机产生n个任务,m个资源,根据任务的任务量大小和资源的计算能力生成一个n×m的初始MCT矩阵。 (2) 根据Min-min算法生成一条对应该调度的染色体。 (3) 随机产生大小为M的初始种群,根据每个资源上的子任务的执行序列,计算每条染色体的适应值。 (4) 选择染色体进行交叉操作和变异操作,计算新生成染色体的适应值,生成新的种群。 (5) 判断是否满足遗传算法的终止条件,如果满足,则停止计算,输出最小时间和对应的染色体;如果不满足,则返回(4)。 3 仿真结果与分析 本文的实验是对gridsim、遗传算法、Min-min算法深入研究的基础上进行的,任务的长度范围、资源的执行能力范围、任务分配给某一资源的执行时间等是模仿gridsim计算得到的,数据跟现实的情况比较相似。该算法用到的主要参数有:解的群体规模为20,交叉和变异概率分别为0.8和0.2,任务个数为表2中的几种,资源个数为10,算法终止条件设为到达一定的进化终止代数,最大进化代数设为100,如果算法连续20代没有找到更好的解我们则认为算法基本收敛。 图1描绘了三种算法时间跨度随任务数大小的变化曲线。从图中我们可以看出:改进GA相对于Min-min算法在性能上会普遍有所提高;对于GA,当任务数较少时(小于40个),性能对于Min-min算法也会提高,较小还高于IGA,随着任务数的增加,性能会逐渐下降,甚至还低于Min-min算法。所以GA不太适合用于大规模的网格任务调度,而本文提出的这种改进遗传算法对网格任务调度普遍适用。 4 结束语 用遗传算法和Min-min算法作为网格任务调度算法已经得到广泛的应用。当规模较小时,遗传算法被证明是一种最有效的启发式调度算法,但随着资源数和任务数的不断增加,遗传算法的性能逐渐降低,到达一定规模时甚至还低于Min-min算法,这样不仅性能得不到提高,而且还会增加调度时间。本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法,这种算法对于大规模任务调度性能也比较高。 由于本文在设计时没有将经济因素考虑在内,下一步的工作可以将开支预算与时间期限考虑在内,再结合本算法,可用于基于经济模型的网格任务调度。另外,模拟退火算法局部搜索能力比较强,遗传算法全局搜索能力较强,将两者结合搜索能力会尽一步提高,性能可能会有所提高。 参考文献 [1]Foster I,Kesselman C.The Grid-Blueprint for a New Computing Infra-structure.Morgan Kaufmann Publishers,1998. [2]Abraham A,Buyya R,Nath B.Nature’s heuristics for scheduling jobs on computational grids.In The8th IEEE International Conference on Advanced Computing and Communications India,2000. [3]Braun T,Siegel H,Beck N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems.Journal of Parallel and Distributed Computing,2001,61(6):810-837. [4]Carretero J,Xhafa F.Using genetic algorithms for scheduling jobs in large scale grid applications.In Workshop of the European Chapter on Metaheuristics EUME2005,Metaheuristics and Large Scale Optimiza-tion.Vilnius,Lithuania,2005(5):19-21. 信息物理融合系统 (Cyber-Physical System, 简称CPS) 是重要而且全新的研究领域。2007年7月, 美国总统科学技术顾问委员会 (PCAST) 在题为《挑战下的领先———竞争世界中的信息技术研发》的报告中将CPS列为八大关键信息技术的首位[1]。CPS是集3C (Computation、Communication、Control) [2]技术于一体的网络化物理设备系统, 可实现大型工程系统的实时感知、动态控制和信息服务, 在环境感知的基础上强调人、机、物的互联互通和深度融合, 高性能的计算能力是CPS必不可少的, 为CPS提供可能的分布式技术得以飞速发展。所谓分布式技术[3]主要指资源分布和计算分布, 资源分布是指资源分散的存储在不同计算机中;计算分布则是将计算任务分配给不同的计算节点进行分布处理, 实现快速准确的分布式管理, 保证系统的可靠性, 任务优化调度方法尤为重要。 本文在构建建筑环境CPS系统结构的基础上, 利用CPS可靠感知、实时传输、虚实同变的特点, 主要针对负责任务调度的传感器计算节点进行设计, 针对每个传感器计算节点, 按照调度优先级序列表进行任务的调度, 找寻任务被合理调度的过程, 实现更高的任务调度成功率, 有效降低任务总体完成时间。 1 CPS系统设计 世界国家的网络, 尤其是发展中国家的网络, 其资源利用率非常低。据有关统计, 网络系统的平均使用效率仅为30%左右, 甚至有的空闲率竟达到91%[4]当一些计算机处于重载状态时, 另一些计算机却处于轻载或空闲状态, 所以利用这些闲散资源为量大的计算任务服务, 能够有效的利用空闲资源, 完成大规模分布式计算, 同时可以提高系统性能[5]。 本文建筑环境CPS系统中, 在传感器普通节点中, 为其一部分节点即传感器计算节点增加配置了计算、分析和处理的功能, 实现安全资源管理、合理任务分配以及快速结果输出, 并提供各种资源环境接口。据此设计了如图一所示的CPS系统结构图。传感器普通节点感知的建筑物理环境数据信息以及用户终端的任务请求命令均发送至传感器计算节点中进行数据分析和任务处理, 信息中心将所有任务及处理结果储存, 方便用户查询, 同时根据任务处理结果发送控制命令, 通过执行器节点控制建筑物理环境。其中本文的任务调度设计主要由传感器计算节点来完成。 2 基于建筑环境CPS的RM任务调度设计 1973年1月, Liu和Layland在题为“Scheduling Algorithm for Multiprogramming in a Hard Real Time Environment”[6]的学术论文中提出了速率单调 (Rate monotonic-RM) 算法, 这是一种简单有效的按实时任务发生周期来分配任务优先级的方法, 即每个任务都有其固有的周期, 并按照任务周期的长短排列其优先级, 任务发生周期越短, 它的优先级越高, 调度总是从任务队列中先运行周期最短的任务。之后他们又相继提出了一系列基于RM调度算法的扩展算法, 均作为静态调度算法的典型代表算法被后人研究和应用。目前, RM调度算法[7]已经被用于控制系统[8]、容错系统[9]、网络系统[10]等各种不同的实时系统环境中。RM算法的任务调度过程如图二所示。 处于就绪状态的任务根据其优先级的先后等待运行, 而运行的任务可能会被更高优先级的任务抢占, 所以还需返回就绪状态, 重新排列。在RM算法中用定义DAG中的任务ti=[Ti, BLi*, Ui] (i=1, 2…, n) 来表示, 其中Ti为任务的周期, Li*表示任务的优先级 (Pi越小, 优先级越高) , 表示CPU负载率, 即所有任务的CPS负载率之和, Pi为ti的执行时间, Ti为ti任务的请求周期。 RM算法只考虑任务的周期, 为了同时兼顾具有同一周期的任务的优先级问题, 本节增加了优先权值;在调度任务的时候, 可能同时存在多个任务且其中一些任务周期很短、优先级较高, 因此本节增加了延迟状态。 2.1 增加优先权值 采用式 (1) 作为任务的优先权值。首先, 将请求任务中的一级任务标记为关键任务, 对于同一请求任务中的任务, 任务的优先级由其级数决定, 同一级的任务按优先权值排列, 但同一计算节点中需要调度的任务可能是多个请求任务中的子任务, 则按优先权值排列任务的同时还要兼顾是否为关键任务。 式 (1) 中, MP为处理单元计算能力中值, MC为链路传输能力中值。 2.2 增加延迟状态 在RM调度算法的就绪和运行两种原有状态的基础上, 增加了延迟状态, 即将未标记的非关键任务加入到延迟状态中, 使延迟状态的优先级小于就绪状态, 在就绪状态后被调度。同时, 未被标记的非关键任务只有加入到延迟状态中才可直接进入就绪状态, 其他非关键任务的请求则应首先进入延迟状态。任务ti在延迟状态中需要等待△1=r1-e1, 任务ti (i=2, 3, …, n-1) 需要等待△i=α×γi×Ui+1…n, 其中α∈[0, 1]。 当标记的关键任务ti进入到就绪状态时, ti优先进入任务调度序列表排列, 按照优先权值从大到小的顺序运行, 然后从延迟状态中选取优先权值最高的任务进入调度序列中, 等待运行;但当就绪列表中出现更高优先级的任务需要处理时, 此时运行的任务需要返回就绪状态或延迟状态 (关键任务返回就绪状态, 非关键任务返回延迟状态) 重新加入调度序列表等待运行, 如图三所示。 执行过程流程如图四所示, 将任务进行分类, 优先级高的和优先级相对较低的分别被定义为关键任务集S和非关键任务集N, 当当前任务完成时, S队列中的个数减1, 并判断S队列是否还有任务存在, 如果有, 继续调度运行;如果没有, 则将非空的N队列中的优先级最高的任务移入S中, 如此循环, 直至所有任务都完成, 其中Sum用于计数。 改进后的RM调度算法将非关键任务送入延迟状态, 推迟了其进入就绪状态的时间, 从而保护了已经进入就绪状态或已经运行的任务请求。 2.3 基于建筑环境CPS的RM任务调度设计 针对某一计算节点上的任务 (子任务) 的调度进行设计, 程序流程如图五所示。 输入:一个物理环境发出的任务信息或用户提出的任务信息 (G, t) , 其中:任务模型G, 时间限制t。 输出:最优调度列表f。 第1步:用式 (2) 判断当前系统是否调度可行, 如可行, 继续;否则重新进行路径选择, 找出其他合适的计算节点。 式 (2) 中, L () 表示一个任务的CPU占用率即负载的最小上界, 当n→∞时, L () →ln (2) ≈0.693, 当整个任务集的负载小于L () 时, RM算法调度可行。 第2步:检查就绪列表是否为空, 如果不为空, 继续;否则结束任务调度。 第3步:查询任务, 获取输入任务的有向无环图DAG参数。 第4步:随机生成的调度列表f, 求解过程中用于记录最新的调度列表。 第5步:通过式 (3) 、 (4) 算任务的优先级程度, 如果任务ti的优先级最高, 则更新调度列表;如果无最高优先级, 按照原调度列表运行。 第6步:判断是否满足最小makespan, 如果满足则结束;否则返回步骤5。 makespan表示任务的运行时间, 即任务从起始节点开始计算到终止节点完成计算所经历的时间长度, Pi, j (式3) 和Wi, j (式4) 所示: 式 (3) 中, Pi, j为执行代价, 表示任务ti在处理器节点Vj上的执行时间;假定任务ti运行在处理器节点Vf上, ti运行在处理器V上, 式 (4) 中, Wi, j为处理器Vf和Vt之间的通信时间, 如果任务ti、tj被分配到统一计算节点上, 通信时间为0。 在任务调度的过程中采用改进RM调度算法, 以运行时间最短为目标, 同时在延迟等待时间上兼顾了网络负载, 在以可计算复杂度的准确任务分配和蚁群的路径选择的基础上, 通过分别考虑关键任务和非关键任务的优先权值且增加延迟状态, 在缩短任务的执行时间和平衡方面均得到了一定的优化。 3 仿真结果与分析 在分布式CPS的计算节点中, 根据可计算复杂性的思想进行任务分配, 再采用动态调度算法进行任务调度, 并通过MATLAB仿真实验验证其优越性。 结合本文的分布式任务管理模型, 利用MAT-LAB进行仿真实验。20种传感器普通节点, 其中10个设置为传感器计算节点, 随机产生10、50、60、800和100个任务。资源的参数设置如表一所示。 对任务的完成时间makespan进行了仿真实验, 并通过与蚁群算法、遗传算法和Min-Min算法三种较为经典的任务调度算法的比较, 得出任务完成时间比较图, 如图六所示。采用本文算法, 任务完成时间均比其他三种算法短, 并随着任务数量的增加, 在缩短任务完成时间方面优势越来越明显。 在任务调度成功率方面, 本文算法较蚁群算法、遗传算法和Min-Min算法体现了优越性, 如图七所示。 从图七中可以看出, 本文算法的调度成功率几乎都达到了90%以上, 在网络环境复杂繁多的CPS中, 其具有非常好的应用前景。 通过仿真实验表明, 相对于蚁群算法、遗传算法和Min-Min算法三种比较经典的任务调度算法, 采用任务分配、路径选择和任务调度独立工作但结果又相互融合的方式进行任务调度的方案是可行的, 既可以加快任务处理的速度, 又可以增加任务调度成功率, 同时在任务分配和处理的同时, 通过图灵机服务器的记忆功能, 加快了未来数据访问速度和任务的处理速度。 参考文献 [1]President's Council of Advisers on Science and Technology (PCAST) , USA.Leadership Under Challenge:Information Technology R&D in a Competitive World:An Assessment of the Federal Networking and Information Technology R&D Program[EB/OL]. [2]何积丰.Cyber-physical Systems[J].中国计算机学会通讯, 2010, 6 (01) :25-29. [3]张栋, 吴春明, 姜明.分布式系统中资源分配的一致性算法综述[J].信息工程大学学报, 2009, 10 (01) :37-40. [4]王金良, 苏志强.网络使用研究进展——影响因素、后果变量及影响机制[J].西南大学学报 (社会科学版) , 2012, 38 (03) :82-88. [5]谭朋柳, 舒坚, 吴振华.一种信息—物理融合系统体系结构[J].计算机研究与发展, 2010, (S2) :312-316. [6]Lehoczky J P, Sha L, Ding Y.The rate-monotonic scheduling algorithm:exact characterization and average case behavior[C]Proceedings of the 10th Real-Time Systems Symposium, 1989:166-171. [7]Tindell K W, Burns A P, Wellings A J.An extendable approach for analysing fixed priority hard real-time tasks[J].Real-Time Systems, 1994, 6 (02) :133-151. [8]Ghosh S, Melhem R, MosséD, et al.Fault-tolerant rate-monotonic scheduling[J].Read-Time Systems, 1998, 15 (02) :149-181. [9]Pandya M, Malek M.Minimum achievable utilization for fault-tolerant processing of periodic tasks[J].IEEE Transactions on Computers, 1998, 47 (10) :1102-1112. 关键词：遗传算法,启发式算法,车间作业调度 1 引言 作业车间调度问题(Job—shop Secheduling Problem,JSP)是一类满足任务配置和顺序约束要求的资源分配问题,是最困难的组合优化问题之一[1],由于该问题计算复杂性过高,因此在工程实践中,大多采用启发式算法求其近优解.随着人工智能和计算机技术的发展,一些较复杂的优化方法得到了迅速发展,如神经网络、模拟退火和遗传算法等,并已成为调度理论的研究热点。 本文提出应用混合遗传算法即:在遗传算法中融入启发式算法的方法来解决生产调度的排序问题。遗传算法作为一种群体优化算法,通过选择、变异、交叉等操作,使解集性能不断得到进化,最终以较快的速度进行搜索,但其存在早熟和收敛性难以控制的问题。而传统的启发式算法结构简单,搜索速度快,但全局搜索能力差,容易陷入局部最优。因此把传统的启发式算法嵌入到遗传算法中构造一个能力更强的遗传算法对于解决复杂的优化问题是很有意义的。该算法将遗传计算的并行性、记忆功能和启发式算法的快速搜索能力相结合,提高了求解质量。 2 混合遗传算法 本文将传统的启发式算法和遗传算法结合起来,应用该混合遗传算法解决作业计划排序问题。针对遗传算法的早熟和收敛性的问题,加入启发式算法的一些规则,同时对遗传算法的一些关键参数(如交叉概率、变异概率)设置了自适应功能,使得算法在车间作业调度方面得到改进。 我们主要通过以下方式实现遗传算法的改进: (1)把启发式嵌入到初始化中,产生一个适应性好的初始解群。按这种方式,混合式遗传算法能够优于启发式算法。 (2)将启发式嵌入到评估函数中,将染色体解码为作业调度。 (3)自适应设计个体的交叉率与变异率。 其中,遗传算法被用于个体中的全局搜索,而启发式算法在染色体中施行局部探寻。由于遗传算法和启发式算法的互补性能,混合遗传算法将优于两种单独的算法。 3 生产调度问题描述 所谓调度,就是为了实现某一目的而对共同使用的资源进行时间分配。本文所说的生产调度问题,是指用一组机床加工一组零件,如何安排每台机器上的工件加工顺序,使得某种指标(比如,总的加工时间、总的加工费用或者相对加工时间等)最优。 一般零件的加工过程由若干工序组成,且应满足一定的约束关系,车间作业调度约束条件的数目和内容会随作业需求和作业环境的不同而不同,如零件生产的工艺需求、设备条件等。 本文定义P={P1,P2,…,Pn}代表n个工件的集合,M={M1,M2,…,Mm}代表m台机床的集合,工件Pi的工序数目为Ki,工件Pi的加工工序为Pi1(Ji1),Pi2(Ji2),…,Pi Ki(Ji Ki)(Ki∈Z+,i=1,2,…,n),其中Z+表示正整数,Ji Ki表示工件Pi第Ki道工序在某台机床上加工,(Ji Ki∈M)。STi Ki表示工件Pi第Ki工序的加工起始时间,ETi Ki表示工件Pi第Ki工序的加工终止时间。用Ti Ki表示工件Pi第Ki工序的加工时间。 基于以上的定义,作业调度要满足以下几个约束: 1.每个工件包含一个由多道工序组成的工序集合,工件的工序顺序是预先给定的。 2.一台机床仅能同时加工一个工件的一道工序。 3.不同工件的工序之间没有先后的约束。相同工件工序满足先后约束关系。 4.工序Pi Ki(Ji Ki)与Pi Ki+1(Ji Ki+1)之间的时间间隔为零,即STi Ki+1-ETi Ki=0。 5.STi Ki≥0,即每个工件的每道工序的开工时间一定大于或等于零。 6.∑Ti Ki=Ti(Ti为工件Pi的总加工时间),即要求所有工件在交工期前加工完毕。 4 混合遗传算法求解作业调度 ⑴.参数编码 应用遗传算法,必须将问题空间的参数转换成遗传空间的、由基因按一定结构组成的染色体或个体,这一转换操作就是编码。编码有基于工序的表达方法、基于工件的表达方法、基于位置“列表”的表达方法、基于机床的表达方法等。这里采用基于机床的表达方法。染色体编码为机床的序列,基于该机床序列,具体编码如下: 工件编号0 1,0 2,…n,每个工件的工序编号0 1,02,…k,机床编号01,02,…m。那么符号01.01.01表示工件01的01工序在设备01上完成。以3(工件)×3(机床)为例。假设工件中工序最多为4,机床对应不存在的加工工序则定义为00.00.00,工件工序加工必须满足工序先后关系的约束。则如表1所示,表示了工件、工序与机床的关系。 ⑵.初始种群的生成和适应度函数的设计 初始种群的产生采取随机产生的方式,这样容易达到解空间所有状态的遍历。通过约束条件检验判断其是否为可行解,若是,将其加入初始种群;否则淘汰。但是初始群体的随机产生加大了进化的代数,大大增加遗传算法的计算时间,这里加入了启发式算法,运用启发式算法的局部搜索能力强的特性,加快优良个体的产生。 个体的适应函数应该是工件总的加工时间单调递减函数,即总工时越小,个体适应度函数值越大;总工时越大,个体适应度函数值越小。个体i的适应函数定义为: 式中Cmax为f(x)的最大值估计。初始种群的生成流程图如图1所示。 ⑶.选择操作:采用了轮盘赌选择方法。若某个个体i, 其适应度为fi,则选择概率为:选择适应度最优的Pop Size个个体作为新一代种群。 ⑷.交叉操作:交叉算子采用一点交叉运算,对参与交叉运算的两个个体母体M和父体F依据自适应交叉概率Pc进行交叉运算。记参与交叉运算的两个个体母体M和父体F,M与F经交叉运算后产生的子代个体记为D和S,染色体长度为L。随机地生成整数p,1 式中,fmax—群体中最大的适应度值;favg—每代群体的平均适应度值;f'—要交叉的两个个体中较大的适应度值。 自适应调整与算法的收敛程度成反向,从而有效地防止了算法收敛于局部最优,并使好的进化结果得以保存。 ⑸.变异操作:变异操作采取互换变异,即先随机生成整数m,m取值范围为机器数量。在本机器上随机选择某一位,将此道工序与相临的工序互换。变异时要注意相临加工工序是否是同一工件的加工,如果是,变异后的染色体非法。自适应变异概率P?m定义如下: 式中,fmax—群体中最大的适应度值;favg—每代群体的平均适应度值;f—要变异个体的适应度值; ⑹.目标函数:本文将工件完工时间最小化作为目标,其目标函数为: 惩罚技术是用遗传算法解约束优化问题中最常用的技术[2]。本质上它是通过惩罚不可行解将约束问题转化为无约束问题。在遗传算法中,惩罚技术用来在每代的种群中保持部分不可行解,使遗传搜索可以从可行域和不可行域两边来达到最优解。 惩罚策略的主要问题是设计一个惩罚函数p(x),从而能有效地引导遗传搜索达到解空间的最好区域。对于本文研究的作业调度问题,根据上面的目标函数,相应的惩罚函数定义为所有工件的超期时间之和。设wai为工件i的超期时间段,则相应的惩罚函数表示则带有惩罚项的调度的目标函数表示为: 5 调度算法应用 为了检验的合理性,现采用文献[3]中的例2。该例由4台机器和8个工件组成,每个工件分别在4台机器上各加工一次,每个工件的加工路线与每道工序的加工时间按照文献[3]所示,如表2。 采用混合遗传算法进行作业计划排序,基本参数设置为:初始种群数=20,遗传代数=200代,经遗传算法重组运算后,作业计划的排序结果GANTT图如图2和3。由图中可见,最长加工路径为33,整个系统的设备空闲等待时间为2。 文献[3]中的例2的任务在文献[4]中用神经网络方法排序,最长加工路径为36;在文献[3]中采用基于效率函数方法经调度后,最长加工路径为33,但是设备的空闲等待时间为3。采用本文混合遗传算法经调度后,最长加工路径为33,设备的空闲等待时间为2。因此,根据例2的执行结果,采用本文研究的混合遗传算法进行作业计划排序,不仅所得的最长加工路径最短,而且设备利用率也是最高的。 6 结束语 车间调度问题已经证明为N P问题,难以找到能够求得最优解的确定性调度算法。又由于遗传算法的优良特性,因此,采用遗传算法对车间调度问题进行求解已成为求解该类问题的趋势。本文提出的基于混合遗传算法的调度算法,融入启发式规则,充分发挥遗传算法优势的同时,又加入启发式算法的快速搜索等优点,提高了分配效果。实例表明该算法能够取得较优的调度结果。 参考文献 [1]GERVEY M R,JOHSON D S,SOTHI R.The com-plexity of flowshop and jobshop scheduling[J].Mathematics and Operations Research1976(1):117-129. [2][日]玄光男,程润伟著,汪定伟,康加福,黄敏译,遗传算法与工程设计[M].北京:科学出版社,2000. [3]常会友,刘丕娥,张淑丽,王凤儒,基于效率函数求解的单件车间调度问题的算法[J].CIMS计算机集成制造系统.1998,(4):5-6数据调度算法 篇4
数据调度算法 篇5
数据调度算法 篇6
数据调度算法 篇7
数据调度算法 篇8