Faster Exploration and Exploitation for Communication Environment Awareness in Starlink

摘要

Environmental awareness is critical for maintaining robust connectivity in low Earth orbit (LEO) satellite networks. Starlink terminals construct a 123×123 obstruction map by passively recording signal quality from connected satellites. However, this process is slow: even under continuous operation, meaningful map coverage typically requires 6 to 12 hours, impractically slow for dynamic environments or short-term deployments. Building on Starlink’s existing capability, we investigate how intelligent satellite selection can further accelerate obstruction map construction, without requiring architectural changes. We formulate the problem as a multi-armed bandit with sleeping arms and introduce SkyBandit, a lightweight online learning algorithm that balances link quality with exploration of uncharted sky regions. SkyBandit achieves a regret bound of $O\left( {\sqrt {NT{\text{ln}}T} } \right)$, where N is the number of observed orbits over T rounds. Experiments using a refined version of xeoverse LEO emulator along with real Starlink measurement data demonstrate that SkyBandit reduces obstruction map convergence time to just around 3 hours, while preserving high-quality connections. To our knowledge, this is the first work to formalize and optimize obstruction map construction in LEO networks via principled sequential learning.