首页 理论教育提升调度算法性能的方法

提升调度算法性能的方法

【摘要】:9.4.5.2调度优化性能分别以32,64,80,100个任务量的仿真场景进行计算,对于每个场景进行100次仿真优化,优化结果取均值与标准遗传算法的优化结果进行比较,比较结果如表9-5所示。

以1颗中继卫星和4颗用户卫星组成的中继卫星系统作为仿真场景,中继卫星定位于东经10°,星上设有3个天线终端,分别为S波段单址天线、Ku波段单址天线和光学天线终端,可为用户星提供多条微波和激光链路。用户卫星的轨道参数均来自2010年6月美国AGI公司发布的全球卫星轨道数据库,光学天线终端性能参数依据欧洲空间局设计的EDRS计划进行设定,具体的终端天线参数如表9-3所示,用户星具体参数如表9-4所示,中继星和用户星轨道参数由STK导入,并通过STK中的链路仿真功能获得两者之间的可见时间窗口,仿真时间段为00∶00∶00~06∶00∶00。

表9-3 天线终端参数

表9-4 用户星基本情况

算法中交叉、变异概率P c和P m分别为0.8和0.2,种群规模M为60。

9.4.5.1 算法收敛特性

当任务规模为64时进行资源调度优化求解,为说明算法收敛特性,记录调度算法运行过程,图9-6、图9-7分别给出了标准遗传算法(SGA)和改进自适应小生境遗传算法收敛曲线。

图9-6 SGA进化收敛

图9-7 SANGA进化收敛

从图9-6的SGA算法进化过程可以看出,当迭代次数为60代左右时,种群个体的平均适应度值与最佳适应度值曲线基本上趋于重合,这时算法已基本收敛,算法进化陷入局部最优解,即使进行遗传操作也很难有新个体产生,这导致了SGA算法进化过程中种群的快速收敛,因而其局部搜索能力较差。而图9-7中的SANGA优化进化过程中,在迭代次数达到40代时,其种群中个体适应度函数的平均值曲线与最佳值曲线逐渐趋于一致,而40代之后直到迭代结束,平均适应度值曲线出现了多次较大幅度的震荡,同时个体最佳适应度值曲线一直低于平均适应度值,而未出现重合现象。算法引入了小生境思想,因而在其优化过程中通过计算合适的距离参数获得了较好的小生境环境。具体操作是在小生境距离范围内的所有个体中,施加一个较强的罚函数给其中较差的个体,极大增加其适应度值,则该个体在后续遗传进化操作中具有较大的淘汰概率,这样就能够保证在小生境距离范围中仅存唯一的优秀个体,不仅维护了种群多样性,而且使得个体在约束空间中均匀分布。而在进化过程中种群的平均适应度值趋于一致时时,自适应交叉、变异算子进行动态的调整,增加P c和P m能够增大新个体产生的概率,避免算法陷入局部最优解。同时在设计选择算子时引入了精英保留策略,使得遗传进化过程中的优良个体不会因为迭代过程而丢失,而总是能够得到保留并参与到下一代的种群进化中,在减小计算开销的同时有利于算法的寻优操作。

9.4.5.2 调度优化性能

分别以32,64,80,100个任务量的仿真场景进行计算,对于每个场景进行100次仿真优化,优化结果取均值与标准遗传算法的优化结果进行比较,比较结果如表9-5所示。

表9-5 SANGA与SGA优化结果对照表

表9-5显示了SANGA和SGA两种算法在对小任务量场景进行优化时,SANGA在任务完成量、权值完成率两方面的优化效果均优于SGA,两者的优化结果比较接近。随着仿真场景中任务量的逐渐增大,天线资源的调度安排冲突愈加激烈,这时SANGA的优势就更加凸显出来,调度结果中任务完成量及权值完成率均大幅度优于SGA的调度结果。

选取任务量为64时的场景,对比了两种算法的100次仿真中以任务优先级权值完成百分比作为优化目标的优化结果,两组数据对比如图9-8所示,图中SANGA的单次优化任务权值完成率达98%以上,在任务权值完成率方面SANGA优化性能明显优于SGA。

图9-8 历次仿真结果

选取具有32个任务量的仿真场景进行多次仿真计算并选取其中一个偏好解进行分析,其调度结果如图9-9所示。图9-9是3个天线资源上任务调度时间甘特图,显示了任务进行传输的具体时间及传输顺序,其中不同颜色的色块代表不同的任务,色块长度代表该任务的传输时间,色块上的标签代表任务序号及相应的优先级权值。

图9-9 调度结果甘特图

在图中所示的调度结果中,调度周期为21 600 s(6 h),全面调度任务传输完成时间为21 566 s,调度任务完成率为100%,即所有任务均能够顺利传输。激光链路传输速率高,因而与微波链路相比,相同的任务通过激光链路传输所需要的传输时间将大大缩短。由混合系统资源调度问题模型中的目标f 3可知,对于大数据量的任务,调度方案将优先采用激光天线终端进行传输。而激光链路除具有较强的中继传输能力外,还具有低终端功耗的优势,因此大部分任务都能够通过激光链路进行传输,激光天线终端的利用率较高;而当激光链路传输能力接近饱和时,则无法满足所有的任务传输需求,这时将选择微波传输任务,但微波链路的中继传输能力有限,因此S和Ku单址天线上安排的任务量较小。考虑到任务传输必须在特定的可见时间窗口内进行,本次调度结果表明了本算法在调度效率和任务完成率方面均具有明显优势,适用于求解具有多任务多天线资源的微波与激光混合链路中继卫星系统资源调度问题。