Multi-Round Message Scheduling for Fast GNSS Packet Broadcasting

Global navigation satellite systems (GNSSs) may transmit data to provide additional services. Since the resources reserved for these data are typically fixed and the message rate is low, we propose to split long messages into shorter packets and properly schedule their transmission from the entire constellation of satellites. Considering an efficient data transmission (useful for example for search and rescue messages), we aim at the scheduling of packets on the satellites on multiple rounds with two objectives: either a) the minimization of the maximum latency among all receivers, or b) the maximization of the average received packets per round. We first derive bounds on the performance of any GNSS single or multi-round scheduling solution, on which the proposed scheduling solutions are based. Then we introduce the scheduling problems that turn out to be integer linear programming (ILP) problems. Lastly, we assess their performance, showing that our solution minimizes the maximum latency, while the scheduling targeting the average latency outperforms existing literature solutions.