Multi-tree genetic programming for adaptive dynamic fault-tolerant task scheduling of satellite edge computing

Satellite Edge Computing (SEC) leverages Low Earth Orbit (LEO) satellites to provide real-time computing services globally. However, dynamic resource availability, heterogeneous task requirements, and frequent failures pose challenges to effective scheduling and fault tolerance. In this work, we propose a Genetic Programming Hyper-Heuristic (GPHH) method to learn scheduling strategies and fault-tolerant strategies for the SEC system simultaneously. Firstly, we formulate a comprehensive problem model for joint dynamic task scheduling and fault tolerance in SEC, aiming to improve task success rates for computational tasks with heterogeneous service requirements. Secondly, we design a selection rule of fault-tolerant strategies that dynamically chooses between task resubmission and replication based on task attributes and real-time resource states. Finally, to ensure adaptive real-time decision-making in dynamic environments, we propose a Multi-Tree Genetic Programming (MTGP) method to automatically learn the routing rule, queuing rule, and selection rule of fault-tolerant strategies. Experimental results show that the task success rate improvement under MTGP is about 3 %-40 % in different scenarios compared to the baseline methods. Moreover, the three tree-based rules evolved by MTGP exhibit strong interpretability, effectively capturing the intricate correlations between scheduling and fault-tolerant strategies.