Research On Model And Algorithm Of Ant Colony Optimization For Satellite Data Transmission Scheduling

Satellite data transmission scheduling (SDTS) is an important practical and difficult theoretical problem urgently to be solved. Ordinary heuristic scheduling algorithm is hard to satisfy the demand of satellite data transmission scheduling. Ant colony optimization (ACO) algorithm based on colony intelligent has already become a typical algorithm for large-scale combinatorial optimization problems. Based on ACO theory, this dissertation proposes three solution construction graph-based SDTS Ant colony optimization algorithms and analyses the algorithms by experiment of simulation application system for exploring the availability of application of ACO in the SDTS and providing solution for ACO in SDTS. The main work and contributions include:(1) The satellite data transmission scheduling modelThe evaluation index system of satellite data transmission scheduling is proposed for evaluating the scheduling solution of ACO algorithms. These indices include tasks scheduling earning rate, satellites tasks scheduling earnings balance degree, utilization ratio of visible time windows on ground resource, data transmission load proportion degree in ground resources and so on. This part of dissertation founded the satellites data transmission scheduling model and mathematically described the modelling element such as satellites resource, ground resource, time windows, data transmission task, scheduling constraints.(2) The heuristics of satellite data transmission schedulingIn order to improving the knowledge utilization and performance of ACO algorithms, the author proposes satellite data transmission scheduling heuristics system which includes task scheduling heuristics and resource allocation heuristics. Propose task scheduling rule and calculating method for its heuristics based on task starting time, task profit attribute, task scheduling flexible degree, task scheduling conflict degree. Task scheduling heuristics is used to construct the sequence of task scheduling for ACO algorithm. Propose resource allocation rule and calculating method for its heuristics based on priority of resource, conflict of visible time window, timeplot of visible time window, and duration of visible time window. Resource allocation heuristics is used to construct the sequence of resource allocation and feasible solution.(3) ACO algorithm for satellite data transmission scheduling based on task scheduling relations graphFor the purpose of reseaching the availability of task scheduling relations graph in SDTS, ACO algorithms for SDTS based on task scheduling relations graph are proposed. The algorithms makes use of a self-adapting probabilistic decision model for the diversity of tasks scheduling sequence construction, and random selecting strategy for agility of tasks scheduling heuristics, and iteration repair local search based on resource allocation heuristics for improving solutions constructed by ants. A step-up global pheromone updating strategy is proposed for single-objective ACO algorithm, and a global pheromone updating strategy based on Pareto solution offset degree is proposed for multi-objective ACO algorithm.(4) ACO algorithm for satellite data transmission scheduling based on task scheduling positions graphIn order to researching the availability of task scheduling positions graph in SDTS, ACO algorithms for SDTS based on the task scheduling positions graph are proposed. A self-adapting probabilistic decision model based on pheromone evaluations is proposed for utilize the environment information and enhance the solution construction ability of algorithm. A guided selection strategy for task scheduling heuristics according to best-so-far solution is proposed for strengthening the self-choosing ability of algorithm. Iteration repair local search based on 2-Opt are proposed in the algorithms in order to improving the construction solution. A self-adapting global pheromone updating strategy based on pheromone deposits is proposed for single objective ACO algorithm, and a global pheromone updating strategy based on approximation ideality distance is proposed for multi-objective ACO algorithm.(5) ACO algorithm for satellite data transmission scheduling based on task data transmission operations graphIn order to researching the availability of data transmission operations solution construction graph, ACO algorithms for SDTS based on task data transmission operations graph are proposed. The algorithms construct the sequence of task scheduling, and then construct each task's resource allocation sequence, and a comprehensive utilize strategy by random weighting for heuristics is proposed. For enhancing diversity of the constructed task scheduling sequences, a pheromone updating strategy based on chaos variation is proposed for column pheromone vector. A global pheromone updating strategy based on compensate mechanism is proposed for single objective ACO algorithm, and a global pheromone updating strategy based on niche of Pareto solutions is proposed for multi-objective ACO algorithm.The author analyses simulation experiment and compares algorithms performance of above three ACO algorithms which are based on different solution construction graphs by simulation application systems. The numerical results show that all single-objective ACO algorithms based on three solution construction graph derive better solution than ordinary heuristics and most of the solutions are better than Genetic Algorithm and the running time is shorter than Genetic Algorithm in large scale scenario. All Multi-objective ACO algorithm that are on the basis of three solution construction graph can obtain Pareto optimum solutions which dominate the solution of ordinary heuristic algorithm which means the algorithms have strong ability of multi-objective optimization. Comparatively, ACO algorithm based on tasks data transmission operations graph has the best performance, the shortest running time. The performance of other two ACO algorithms based on other two solution construction graphs is almost the same and the quality of algorithm solution is affected greatly by the algorithm of solution element construction.