Throughput-Optimal Joint Routing and Scheduling for Low-Earth-Orbit Satellite Networks

When optimizing communication patterns in wireless networks, routing and link scheduling cannot be handled separately but must be addressed jointly. Various linear programming formulations were proposed for static networks to optimize routing while ensuring schedulability of the achieved result. However, most of these approaches do not allow to obtain an optimal transmission schedule directly. Even if they do, they do not scale well to practically relevant network sizes. Node mobility further complicates the effort. Here, we consider satellite networks, which are characterized by time-varying, yet predictable topologies. We present a novel approach for the joint optimization of routing and link scheduling. It is based on linear programming and provides a constructive way to generate transmission schedules. To reduce the computational complexity, we decompose the problem and apply a series of optimization steps resulting in an optimal transmission schedule. As an exemplary use case we optimize the throughput of a network consisting of 18 low-earth-orbit satellites. Our evaluation results validate the optimality of our joint routing and scheduling approach and demonstrate its applicability to a real-world use case.