Multitree Genetic Programming With Rule Reconstruction for Dynamic Task Scheduling in Integrated Cloud–Edge Satellite–Terrestrial Networks

Satellite-terrestrial networks (STNs) are a promising paradigm for providing Internet services for users globally. Since the dynamics of service resources and the uncertainty of computational requests, how the service resources in STNs can be efficiently exploited to execute differentiated computational tasks is an essential challenge. In this work, we investigate the dynamic task scheduling in the integrated cloud-edge STNs. First, we propose a cloud-edge collaborative computing framework in STNs, where the computational tasks of users can be processed collaboratively by satellite edge servers, terrestrial edge servers, and cloud servers. Based on this framework, a dynamic task scheduling problem is formulated with the objective of maximizing the task success rate. Second, to make effective real-time decisions at decision points in the dynamic scheduling process, we develop a scheduling heuristic with the routing rule and queuing rule, which incorporates dynamic features related to servers, computational tasks, and network environments. Third, to automatically learn the scheduling heuristic, we propose a multitree genetic programming with rule reconstruction (MTGPRR), which introduces a selective reconstruction operator. This operator increases the chance of matching good rules with other rules by recombining common individuals and elites. Experimental results demonstrate that the proposed MTGPRR performs significantly better than the state-of-the-art methods in improving the task success rate. Moreover, the evolved scheduling heuristic has good interpretability, which is important for practical applications.