Dynamic Scheduling of Hybrid Tasks with Time Windows in Data Relay Satellite Networks

Through the allocation of multi-antenna time blocks to spacecrafts, the data relay satellite network (DRSN) is capable of providing data relay within their visible intervals (i.e., time windows). During the relay process, the generated hybrid tasks incorporate common tasks, emergency tasks, and temporary tasks. However, higher priority unpredicted tasks (i.e., emergency tasks and temporary tasks) unpredictably preempt antenna resources, thereby resulting in more common tasks unsuccessful to relay. It is, therefore, nontrivial to investigate the dynamic hybrid task scheduling problem with time windows for the multi-antenna DRSN to efficiently and real-timely allocate multi-antenna time blocks aiming at accommodating more unpredicted tasks and reducing the number of unsuccessful common tasks. To this end, we propose a stochastic optimization framework to maximize the time average number of hybrid tasks by jointly optimizing the scheduling periods and the antenna time block allocation. For the tractability purpose, by leveraging its unique structure, we first equivalently transform it to a scheduling period adjustment (SPA) problem, embedded with a sequence of antenna time block allocation (ATBA) problems. Then, two efficient algorithms are developed to solve the SPA and ATBA problem, respectively. Finally, simulation results demonstrate that the proposed algorithm can significantly increase the time average number of hybrid tasks.