CS Paper Radar

On the Lack of Periodicity of Walker Satellite Constellation Routing Tables

Chang-Sik Choi, François Baccelli

cs.IT cs.NImath.DS ·submitted 2026-09-29 02:50 UTC · v1

Abstract

In a referential that rotates with Earth, the dynamics of the configurations of satellites in a Delta Walker constellation can be analyzed as a dynamical system as a function of a translation on the torus. This paper extends this type of analysis to routing over a Walker constellation, leveraging fixed ground relays. It considers any deterministic, time-invariant routing rule on such a collection of satellites and relays. The main object of interest is the routing table associated with this rule, which specifies, for all source-destination pairs, a route made of satellites and relays between them, for instance the shortest, together with angular information on next hop at each step of the route, which is essential for beamforming in this context. The main result is that, for each such routing rule, the routing table inherits the dichotomy of the torus flow: when the ratio of the Earth-spin and satellite angular speeds is rational, the routing table process is periodic with the same period as the constellation. When it is irrational, the table is non periodic but admits ergodic long-run averages which can be computed as ensemble averages w.r.t. an explicit invariant measure. Simulations with mixed satellite--gateway greedy routing illustrate these findings in terms of both temporal and spectral properties of the Walker routing table time series. The paper also discusses how to define metrics that cope with such non periodic fluctuations when present. This is illustrated by a comparison of the round-trip times between two far away cities as offered by a Walker constellation using greedy routing on one side, and by the currently available terrestrial fiber on the other side. It is shown how ergodicity can be used to make this comparison between the time varying instantaneous round trip times of the constellation and the constant round trip time of the fiber network meaningful.

Comment
submitted to IEEE Journal

Closest papers

Nearest neighbours by meaning across the whole index.

Computing All-Pairs Shortest Communication Time Paths for Periodically Varying Satellite Networks

cs.NI cs.DC ·2026-10-12 ·Koushik Sinha, Dibakar Saha, Sai Puppala, Bhabani P. Sinha
similarity 0.57
Abstract

We address the problem of designing an efficient algorithm for computing the all-pairs shortest-time paths in time-varying networks, specifically targeting the dynamic topological characteristics of low earth orbit (LEO) satellite constellations. We model such temporal graphs as $G = (V, E_t)$, where $V=\{1, 2,\ldots , n\}$ is the set of $n$ vertices in the graph, and $E_t$ is the set of $M$ time-varying edges considered over a total time window of size $T = Mτ$, $τ$ being the duration of each interval in that time window. For such a network, our algorithm finds the all-pair shortest paths in $O(M^2n^3)$-time. A key advantage of our approach is its computational structure, which mirrors two matrix multiplication steps, first in the forward direction and then in the backward direction. This structure of the algorithm makes it exceptionally suitable for parallelization on SIMD architectures like GPUs, thereby offering a significant speedup over traditional shortest-path algorithms and enabling efficient, network-wide message routing in rapidly changing LEO satellite constellations.

0.23

Lightweight Onboard Routing and Topology Co-Construction for Autonomous GNSSs

eess.SY ·2026-09-07 ·Huan Yan, Juan A. Fraire, Rongqin Yang, Wenfeng Li, Kanglian Zhao
similarity 0.56
Abstract · 15 pages, 6 figs

Global navigation satellite systems (GNSSs) can already plan their inter-satellite link (ISL) topology onboard, leaving routing as the last step toward autonomous networking. In GNSS ISLs, each satellite links to at most one peer per time slot. We exploit this structure to replace end-to-end path search with a single backward sweep over the slots. The proposed method, DS-SMFP, propagates earliest-arrival times backward from each destination and outputs a STORE/FORWARD decision for every slot, satellite, and destination, in time linear in the number of slots and with working memory independent of the planning horizon. Because each slot needs only its own topology and the delivery state of the next one, routing can steer link selection while the topology is built. This slotwise dependency enables Master-Oriented Topology--Routing Co-Construction (MTRCC), which favors traffic to and from a master satellite performing onboard orbit determination. In a 24-h, 30-satellite BeiDou scenario, DS-SMFP matches the delays of Contact Graph Routing (CGR) and shortest path tree (SPT) routing while running over 180 times faster and using over 36 times less peak routing working memory. Compared with fair contact plan (FCP) topology, MTRCC reduces mean master-related traffic delays by over 10\%, with an approximately 3\% increase in mean PDOP. This paper provides a methodological foundation for efficient autonomous GNSS networking.

0.27

LEO Constellation Analysis for Satellite IoT: An Analysis of Coverage Gaps and Retransmissions

cs.IT ·2026-10-30 ·Lowie Rombouts, Jeroen Famaey, Roger Sanchez-Vital
similarity 0.54
Abstract

Low Earth Orbit (LEO) constellations are a promising way to connect Internet of Things (IoT) devices beyond terrestrial coverage, yet the intermittent visibility of their satellites imposes hard constraints on system and protocol design. Coverage probability and other snapshot statistics, which are often computed without accounting for the terminal's latitude, are insufficient for this purpose. Designers also need the temporal structure of coverage: the rate of coverage gaps, their duration distribution and mean, and quantities such as the probability that a retransmission succeeds after an initial transmission has failed. We develop an ergodic framework for Walker Star constellations in which these quantities reduce to spatial integrals over a two-dimensional torus that can be evaluated efficiently. We validate the framework against a seven-day Simplified General Perturbations 4 (SGP4) simulation of the Iridium NEXT constellation and find close agreement for the coverage probability, the revisit-time distribution, and the retransmission success probability. A comparison of Walker Star configurations further shows that constellations with similar satellite counts can yield substantially different packet-delivery probabilities with at most one retransmission, depending on the number of orbital planes. The results show that the ergodic model accurately gives the long-run values that finite time-domain simulations can only approximate, providing researchers with a tractable basis for the analytical modelling of IoT connectivity over non-terrestrial networks (NTN).

0.19

Satellite Infrastructure Sharing: Orbit-Structured Stochastic Geometry Modeling and Connectivity Analysis in Heterogeneous Satellite Networks

cs.IT eess.SPmath.PR ·2026-08-12 ·Chang-Sik Choi
top venue similarity 0.48
Abstract · submitted to IEEE Transactions on Wireless Communications

This paper develops an analytical framework to evaluate the feasibility and performance of satellite infrastructure sharing among multiple low Earth orbit (LEO) satellite operators. Motivated by the growing demand for universal connectivity under limited satellite resources, the proposed model captures uncoordinated deployments where independently operated constellations coexist without predefined orbital agreements. To describe such heterogeneous configurations, the spherical Cox point process is employed to jointly generate orbital structures and satellites. Then, each satellite is further assigned a random communication range, reflecting variations in coverage capability across operators. The overall coverage region is modeled through a spherical Cox-Boolean model that captures the spatial overlap of individual satellite spherical footprints on Earth. Using the proposed framework, the feasibility and benefits of satellite infrastructure sharing are mathematically analyzed, and closed-form expressions are derived for key performance metrics such as the connection probability, connection number, and downlink signal characteristics including the nearest serving distance, total received signal power, and the signal-to-interference ratio (SIR) distribution in the interference-limited regime. The analytical results, validated through system-level simulations, provide a tractable characterization of how orbital geometry governs coverage, connectivity, and interference, and reveal the inherent trade-offs induced by coverage overlap in heterogeneous satellite constellations.

0.29

Joint Geometric and QoS-Aware Routing in Optical LEO Satellite Networks via DRL

eess.SP ·2026-10-01 ·Abdulrahman Al-Hababi, Meysam Ghanbari, Mohammad Taghi Dabiri, Rula Ammuri, Mazen Hasna +1 more
similarity 0.48
Abstract

Optical inter satellite links ISLs are becoming the backbone of modern LEO constellations offering high capacity and low latency but introducing stringent geometric and physical layer constraints Routing in such networks must therefore account for time varying topology jitter induced outage and the heterogeneous reliability of intra and inter plane optical links aspects that classical shortest path or existing learning based schemes do not fully capture This paper develops a joint geometric and QoS aware routing framework for optical LEO networks We derive a closed form outage expression under Gaussian beam propagation with pointing errors and obtain analytical maximum feasible link ranges for different ISL classes These relations remove beam divergence from the optimization variables and embed optical feasibility directly into the routing layer leading to a latency reliability capacity constrained routing formulation that is proved to be NP hard To enable scalable decision making we cast snapshot routing as a Markov decision process and introduce an angle constrained masked deep Q network AC MDQN that integrates optical feasibility masks potential based latency shaping and a geometry aware corridor filter around the source destination great circle path This design significantly reduces the effective action space complexity while preserving near optimal routing choices Simulations on a Starlink like constellation demonstrate that AC MDQN achieves end to end latency within 1 to 2 percent of constrained shortest path solutions remains robust under varying pointing jitter and supports controllable hop latency trade offs through reward design The results confirm that the proposed framework provides an efficient and physically consistent routing solution for large scale optical LEO networks

0.24

Stochastic Geometry Analysis and Optimization for Multi-LEO Satellite-Assisted Communications

eess.SP ·2026-10-22 ·Xu Hu, Bin Lin, Ping Wang, Xiao Lu, Weihua Zhuang +1 more
published similarity 0.48
Abstract

Low Earth orbit (LEO) satellites are vital in providing seamless connectivities to ground users (GUs). However, complex satellite-to-ground propagation and non-negligible satellite failure probabilities make single-satellite transmission unreliable. To address this issue, we consider a multi-LEO-satellite communication network (mLEO-CN), where a typical GU is served by multiple LEO satellites. The satellite locations are modeled as a binomial point process on a sphere and ordered according to their distances to the GU. To improve communication reliability, a serial communication scheme is adopted, in which the subsequent satellite is activated only when all preceding satellites fail to satisfy the target signal-to-noise ratio threshold. By employing the tool of stochastic geometry, we derive key performance metrics, including overall transmission success probability, average transmission rate, and end-to-end delay under the serial communication scheme by incorporating both shadowed Rician (SR) fading and satellite failure probabilities. To improve analytical tractability, we derive asymptotic expressions for the end-to-end transmission success probability in two special cases by leveraging the asymptotic expression of the SR fading model and a Gamma-distribution, and further propose a cluster-based approximation approach for the overall transmission success probability. Building on these analyses, we formulate an optimization problem to maximize the ratio of the overall transmission success probability to the end-to-end delay, and obtain its solution using a one-dimensional search approach. Numerical results validate the analysis, reveal the impact of key parameters, and identify the optimal number of serving LEO satellites under different constellation altitudes.

0.46

Resource Slicing for Time-Sensitive Data Traffic in Non-Terrestrial Networks with FSO ISLs

eess.SP ·2026-10-22 ·Abid Afridi, Alexis A. Dowhuszko, Risto Wichman, Jyri Hämäläinen
published similarity 0.47
Abstract · 6 pages, 7 figures, 1 table. Accepted for presentation at IEEE GLOBECOM 2026 Workshops

In multi-hop Low Earth Orbit (LEO) satellite networks, time-sensitive packets experience queueing across multiple satellite hops, causing per-hop waiting times that accumulate and make the maximum end-to-end (E2E) delay difficult to guarantee. This paper presents a novel multi-hop slicing framework that reserves time-frequency resources for each time-sensitive flow of data originating at each satellite, aiming to maintain the reservation of communication resources along every inter-satellite link (ISL) on its route to the ground station (GS). The number of time-frequency resource blocks (RBs) reserved per-hop is determined from the data packet arrival statistics, E2E delay budget, and target level of reliability. Reservations on consecutive links are temporally aligned to enable pipelined forwarding of the time-sensitive data flows aggregated from terrestrial user terminals on the different LEO satellites. We evaluate the proposed framework against conventional scheduling and resource-allocation baselines, including pure time-division multiple access (Pure-TDMA), first-in-first-out (FIFO), and farthest-satellite-first (FSF), over the same multi-hop LEO satellite path. Under light traffic conditions, the baseline schemes provide comparable delay performance; however, their high-percentile delays increase sharply as data traffic load grows, whereas the proposed framework exhibits substantially slower delay growth. At the high arrival rate and high reliability target considered, the proposed scheme requires about 31 ms, a factor of 2.5-6.8 lower than the 76, 180, and 210 ms required by FIFO, FSF, and Pure-TDMA.

0.43

IRIS: Intelligent Random Access with Integrated Shared Learning for Decentralized LEO Direct-to-Satellite Uplinks

cs.NI ·2026-11-04 ·Abdullah Al Noman, Gaurav Singh, Rameez Ahmed, Debashri Roy
similarity 0.47
Abstract

Grant-free uplink access in low-Earth-orbit (LEO) non-terrestrial networks (NTNs) poses a coordination challenge when multiple UEs share a satellite channel without real-time centralized scheduling under long propagation delays and time-varying channels. Conventional random access does not exploit peer context, leading to collisions and inefficient channel use as contention increases. To address this problem, we propose IRIS, a multi-agent reinforcement learning framework for decentralized grant-free direct-to-satellite (D2S) uplink access, with A2A-IRIS as its sidelink-assisted Agent-to-Agent (A2A) realization. Each UE executes a shared binary transmission policy using local traffic/channel information augmented by compact peer states exchanged over UE-to-UE sidelink, while Vanilla-IRIS serves as a local-only ablation. Evaluations in rural and suburban LEO D2S deployments use TLE-based trajectories propagated using the Simplified General Perturbations 4 (SGP4), with a Walker-Delta constellation as fallback. A2A-IRIS achieves 2.1579 and 5.4478 Mbps, corresponding to 99.9% and 96.1% of the respective scenario-specific upper bounds. Relative to Vanilla-IRIS, throughput improves by 40.8% and 325.0%, with collision rates of 0.0000 and 0.0433, while one- and two-epoch delayed centralized schedulers are outperformed by approximately 51--130%. A2A-IRIS also improves fairness, service coverage, and transmission efficiency with moderate Deep Q-Network (DQN) inference overhead. Active-UE load scalability results further show sustained performance over the evaluated load range. These results demonstrate the effectiveness of sidelink-assisted A2A coordination for decentralized LEO D2S uplink access under propagation delay and delayed channel feedback.

0.08