Research On Scheduling Algorithm Of Distributed COmputing System For Robot Navigation Control

A large number of image data must be processed timely for controlling a mobile robot in unknown environment. In order to ensure navigation and control system's real time and high-performance, the image data should be parallel processing in a distributed way.Task scheduling is one of key problems in distributed computing system. Some popular scheduling algorithms, such as table scheduling, Backfilling and FCFS, can obtain a good result when the load is light, but when the load grows, the scheduling result is unsatisfactory because they can not optimize the resource distribution. So we must improve the scheduling algorithm.To work out a correct solution to mass information, plentiful tasks in the navigation control system, NCDCS (Navigation and Control Distributed Computing System) has been put forward in this thesis, which is based on Resource Broker. The system is hierarchical structure, which divided into three layers- resource layer, broker layer, user layer. Resource layer consists of lots of compute nodes; Broker layer includes Resource Broker and Resource Information Service; User layer is composed of client nodes, which can submit tasks to NCDCS. NCDCS is implemented with OpenLDAP, Java RMI and Java Socket.SAGMB (Scheduling Algorithm based on Genetic algorithm and Multiple-queue Backfilling) has been developed for NCDCS in this thesis. Firstly, the scheduling algorithm predicts the jobs' runtime in JPRA (Jobs Runtime Prediction Algorithm), then adaptive schedules tasks used genetic algorithm combining with multiple-queue Backfilling.The performance trial of Backfilling, FCFS and SAGMB in NCDCS shows that the schedule result is close when load is light, but SAGMB's performance improves greatly when load is heavy.in a word, NCDCS with SAGMB can optimize the resource distribution, reduce the average task's run-time, thereby it can ensure the high performance and real time of navigation control system.