面向机器人导航控制分布式计算的任务调度方法研究

论文摘要

未知环境下移动机器人的导航控制涉及大量的图像数据处理。为保证导航控制系统的有效性与实时性,需要使用分布式计算系统对图像进行并行处理。 任务调度是分布式计算系统的关键问题之一,常用的任务调度算法如表调度、Backfilling、FCFS等在系统轻负载时能到达较好的效果,但在重负载时调度效果并不理想。为此需要对调度算法加以改进,以更好地满足系统有效性和实时性的要求。 本文提出了一种基于代理的分布式计算框架——NCDCS（Navigation and Control Distributed Computing System）。该计算框架采用分层的结构,将系统划分为资源层、代理层、用户层。资源层由众多的计算节点构成;代理层包括有两类代理,资源代理和资源信息服务代理;用户层主要由客户节点构成,NCDCS系统上运行的任务由客户节点提交。NCDCS系统采用OpenLDAP结合Java RMI、Java Socket编程实现。 本文提出了一种任务调度方法——SAGMB（Scheduling Algorithm based on Genetic algorithm and Multiple-queue Backfilling）,该算法首先运用JRPA（Jobs Runtime Prediction Algorithm）任务预测算法对任务执行时间进行预测,再根据系统中各个主机的系统资源利用率自适应地运用遗传算法结合多队列Backfilling方法进行任务调度。 通过在NCDCS系统上对多队列Backfilling、FCFS和SAGMB任务调度算法的性能测试表明,三种调度算法在轻负载时性能相当,但在重负载下SAGMB调度算法相对于其他两种算法性能有明显的提高,并且在重负载下该系统的加速比也比较理想。 综上所述,采用SAGMB调度算法的NCDCS系统能够实现资源的优化分配,减少任务的平均执行时间,从而为整个移动机器人导航控制系统高效实时的运行提供了保证。

论文目录

• 第一章 绪论
• 1.1 研究背景与意义
• 1.1.1 移动机器人导航控制
• 1.1.2 分布式处理技术
• 1.2 研究现状
• 1.3 研究内容
• 1.4 论文结构
• 第二章 NCDCS的研究与设计
• 2.1 并行处理系统综述
• 2.1.1 集群计算系统
• 2.1.2 分布式处理系统
• 2.2 NCDCS系统设计
• 2.2.1 NCDCS结构模型
• 2.2.2 NCDCS故障模型
• 2.2.3 NCDCS安全模型
• 第三章 SAGMB任务调度算法设计
• 3.1 任务调度方法概述
• 3.1.1 启发式表调度算法
• 3.1.2 智能动态调度
• 3.2 SAGMB任务调度算法
• 3.2.1 SAGMB算法
• 3.2.2 任务执行时间预测
• 3.2.3 遗传算法
• 3.2.4 试验结果及其分析
• 第四章 NCDCS系统的实现
• 4.1 代理层节点实现
• 4.1.1 信息服务代理
• 4.1.2 资源代理
• 4.2 资源层节点实现
• 4.3 用户层节点实现
• 4.3.1 与计算节点交互操作
• 4.3.2 与资源代理交互操作
• 第五章 结论与展望
• 5.1 结论
• 5.2 展望
• 参考文献
• 致谢
• 攻读学位期间主要的研究成果