In this paper, we face the problem of ensuring reliability of Global Navigation Satellite Systems (GNSSs) in harsh channel conditions, where obstacles and scatter cause long outage events that cannot be counteracted with channel coding only. Our novel approach, stemming from information-theoretic considerations, is based on link-layer coding (LLC). LLC allows us to significantly improve the efficiency in terms of time-to-first-fix with respect to current operational GNSSs, which adopt carousel transmission. First, we investigate the maximum theoretical LLC gain under different Land Mobile Satellite channel conditions. Then, some practical LLC coding schemes, namely, fountain codes and a novel low-density parity-check plus low-rate repetition coding, are proposed and tested in realistic single-satellite and multi-satellite Land Mobile Satellite scenarios, considering the Galileo I/NAV message as study case. Simulation results show that our designed schemes largely improve on carousel transmission and achieve near-optimal performance with limited increase in complexity. Also, back-compatibility of LLC is assessed with respect to present-time GNSS specifications.
