Temporal Netgrid Model-Based Dynamic Routing in Large-Scale Small Satellite Networks

In recent years, Small Satellite Networks (SSNs) are attracting increasing attention due to its economical prospects and advantages in high bandwidth and low latency. More and more companies and organizations are planning to construct large-scale SSNs to provide global services. In this way, the traffic pattern is more complicated because of random transmission requirements and stochastic packet generations/arrivals, and routing faces more challenges due to network scale and limited resource in small satellites. Traditional satellite routing algorithms, which attempt to exploit the predictable satellite's trajectory with time-discrete graph models, cannot handle these challenges. In this paper, we propose a novel Temporal Netgrid Model (TNM) to portray the time-varying topology of large-scale SSNs. In TNM, the whole space is divided into small cubes (i.e., netgrids) and then, satellites can be located by netgrids instead of coordinates. By doing so, we can construct a network topology for random traffic routing. Furthermore, an efficient Netgrid-based Shortest Path Routing (NSR) algorithm is proposed based on TNM; NSR attempts to find the optimal path from source netgrid to any other reachable netgrids. In this way, the routing complexity is significantly reduced. We also develop a Large-scale Satellite Network Simulator (LSNS) to validate our study. The results show that NSR achieves a significant reduction in computational complexity as well as near-optimal routing performance in terms of end-to-end delay and packet drop rate in scenarios of large-scale SSNs compared with existing satellite routing algorithms.