Time-Dependent Network Topology Optimization for LEO Satellite Constellations

Abstract

Today’s Low Earth Orbit (LEO) satellite networks, exemplified by SpaceX’s Starlink, play a crucial role in delivering global internet access to millions of users. However, managing the dynamic and expansive nature of these networks poses significant challenges in designing optimal satellite topologies over time. In this paper, we introduce the Dynamic Time-Expanded Graph (DTEG)-based Optimal Topology Design (DoTD) algorithm to tackle these challenges effectively. We first formulate a novel space network topology optimization problem encompassing a multi-objective function – maximize network capacity, minimize latency, and mitigate link churn – under key inter-satellite link constraints. Our proposed approach addresses this optimization problem by transforming the objective functions and constraints into a time-dependent scoring function. This empowers each LEO satellite to assess potential connections based on their dynamic performance scores, ensuring robust network performance over time without scalability issues. Additionally, we provide proof of the score function’s boundary to prove that it will not approach infinity, thus allowing each satellite to consistently evaluate others over time. For evaluation purposes, we utilize a realistic Mininetbased LEO satellite emulation tool that leverages Starlink’s TwoLine Element (TLE) data. Comparative evaluation against two baseline methods – Greedy and +Grid, demonstrates the superior performance of our algorithm in optimizing network efficiency and resilience.

Index Terms—Starlink, LEO satellite, Dynamic TimeExpanded Graph, +Grid, OSPF, SpaceNet, and ISLs.

以SpaceX的星链（Starlink）为代表的当今低地球轨道（LEO）卫星网络，在为全球数百万用户提供互联网接入方面扮演着至关重要的角色。然而，管理这些网络的动态性和广阔性，给随时间推移设计最优的卫星拓扑带来了巨大挑战。在本文中，我们提出了一种基于动态时间扩展图（DTEG）的最优拓扑设计（DoTD）算法，以有效应对这些挑战。我们首先构建了一个新颖的空间网络拓扑优化问题，其包含一个多目标函数——在关键的星间链路约束下，最大化网络容量、最小化延迟并减轻链路抖动。我们提出的方法通过将目标函数和约束转换为一个时变评分函数来解决此优化问题。这使得每颗LEO卫星能够基于其动态性能得分来评估潜在的连接，从而在没有可扩展性问题的情况下，确保网络性能随时间的稳健性。此外，我们提供了该评分函数边界的证明，以证实其不会趋近于无穷大，从而让每颗卫星能随时间持续地评估其他卫星。在评估方面，我们利用了一个基于Mininet的、并采用星链“两行轨道根数”（TLE）数据的真实LEO卫星仿真工具。与两种基线方法 —— 贪心算法（Greedy）和+Grid算法 —— 的对比评估，证明了我们的算法在优化网络效率和弹性方面的优越性能。

Introduction

The terrestrial 5G network has proven successful in achieving ultra-low latency of 1 ms and very high internet speeds, with peak data rates of up to 20 Gbps (downlink) and 10 Gbps (uplink), and user experience data rates of 100 Mbps (downlink) and 50 Mbps (uplink) [2]. Despite these advancements, challenges remain for 5G terrestrial networks. The high deployment cost causes fewer installations of 5G base stations (BSs) in rural areas. Additionally, installing 5G terrestrial networks can be impossible or difficult in harsh environments, such as wilderness areas, oceanic regions, and isolated mountains [3]. This demonstrates that the 5G terrestrial network is not yet capable of providing high data rates and low-latency access for users anywhere and anytime.

地面5G网络在实现1毫秒的超低延迟和极高的互联网速度方面已证明是成功的，其峰值数据速率高达20 Gbps（下行）和10 Gbps（上行），用户体验速率也达到了100 Mbps（下行）和50 Mbps（上行）[2]。尽管取得了这些进步，5G地面网络仍然面临挑战。高昂的部署成本导致农村地区的5G基站（BSs）安装数量较少。此外，在恶劣环境（如荒野、海洋区域和偏远山区）中安装5G地面网络可能极其困难甚至无法实现[3]。这表明，5G地面网络尚未能为用户提供无时无刻、无处不在的高速率和低延迟接入。

Non-terrestrial networks (NTN) have emerged as a promising solution to the limitations of terrestrial 5G networks. NTN refers to space network technology, which deploys satellites in low-Earth orbit (LEO) (approximately 160 km to 2, 000 km above the Earth’s surface) to provide network access for users in the air, on the sea, and on the ground around the globe [3], [4]. LEO satellites not only offer ubiquitous coverage but also feature low launch costs and simplicity of deployment [5], thus it becomes increasingly attractive to world-class companies launching their LEO satellite constellation projects such as Starlink, OneWeb, Amazon Kuiper, Telesat, Lightspeed, and Hongyan [6]–[8]. The leading space network service provider, Starlink, has already launched over 6, 078 satellites in LEO, of which 6, 006 are operational as of May 2024, with a total of 3 million subscribers. Starlink plans to deploy up to 42, 000 satellites to construct a LEO Mega-constellation, as reported by Space.com [9]. OneWeb, the second leading LEO provider, has successfully launched 633 LEO satellites as of Feb 2024, as reported by Spacenews.com [10]. Meanwhile, other companies have launched few or no operational LEO satellites yet, but they have plans to deploy them in the near future. Despite the success of space networks achieved by Starlink, it has also introduced numerous research challenges that require attention [11]. Each satellite can connect to any other within its range and visibility, prompting recent research to focus on topology designs for LEO satellites that optimizes end-to-end network capacity and reduced latency [12]–[17].

非地面网络（NTN）已成为一种有望解决地面5G网络局限性的方案。NTN指的是空间网络技术，它通过在低地球轨道（LEO）（距离地球表面约160公里至2000公里）部署卫星，为全球空中、海上和陆地的用户提供网络接入[3], [4]。LEO卫星不仅提供泛在覆盖，还具有低发射成本和部署简便的特点[5]，因此日益吸引世界级公司推出其LEO卫星星座项目，如星链（Starlink）、一网（OneWeb）、亚马逊柯伊伯（Amazon Kuiper）、Telesat、Lightspeed和鸿雁[6]–[8]。领先的空间网络服务提供商星链，截至2024年5月，已在LEO发射了超过6,078颗卫星，其中6,006颗在轨运行，拥有共计300万用户。据 Space.com 报道，星链计划部署多达42,000颗卫星以构建一个LEO巨型星座[9]。据 Spacenews.com 报道，第二大LEO提供商一网，截至2024年2月，已成功发射633颗LEO卫星[10]。与此同时，其他公司虽已发射的在轨运行LEO卫星很少或尚未发射，但都计划在不远的将来进行部署。尽管星链在空间网络领域取得了成功，它也带来了众多需要关注的研究挑战[11]。每颗卫星都能在其范围和可见性内与任何其他卫星连接，这促使近期的研究聚焦于为LEO卫星设计拓扑，以优化端到端网络容量并降低延迟[12]–[17]

Inter-Satellite Links (ISLs) are poised to revolutionize space communication by enhancing data transmission speed and reliability [18]. The topology designs are based on the ISLs, which are established directly between satellites in orbit, thus allowing them to communicate with each other without relaying signals through GSs. ISLs play a crucial role in modern satellite networks, particularly in constellations and systems designed for global coverage with low latency [19], [20]. They are currently being used in SpaceX’s Starlink satellite network, which comprises thousands of broadband Internet satellites [21]. The +Grid topology is considered the default design for ISLs in Low Earth Orbit (LEO) satellite networks. In this topology, each satellite is connected to four nearby neighbors: two in the same orbital plane and two in adjacent orbital planes [22]. This Grid-like structure is relatively easy to design and implement; however, it suffers from significant drawbacks, such as shorter ISL ranges that increase ISL hop counts and end-to-end latency, a lack of consideration for the source and destination nodes when designing the topology, and insufficient flexibility to achieve optimal routing, all of which can affect the overall efficiency of the network. The ×Grid has been designed to provide efficiency improvement over the +Grid. Similar to the +Grid, this approach connects satellites in the same and adjacent orbital planes [16]. The key difference is that the +Grid connection is based on a star topology, whereas the ×Grid is based on a rectangular topology. This design minimizes connection overlaps and reduces ISL hop counts by an average factor of two. However, similar to traditional grid topologies, it applies a consistent connection pattern, which limits flexibility in dynamic scenarios. [17] proposed a topology design based on motifs to improve performance over the neighbor-grid topology. This approach utilizes frequently repeated patterns of connections, where each satellite is connected to its neighbors in the same manner, effectively reducing expensive link changes over time. With this design, performance metrics such as latency and capacity are improved by a factor of two compared to the neighbor grid. However, this approach still relies on the neighbor-based connection strategy, which lacks the flexibility to meet an optimal routing.

星间链路（ISL）通过提升数据传输速度和可靠性，有望彻底改变空间通信[18]。拓扑设计基于ISL，这些链路直接在轨道上的卫星之间建立，从而使它们能够相互通信而无需通过地面站（GSs）中继信号。ISL在现代卫星网络中扮演着至关重要的角色，尤其是在为实现低延迟全球覆盖而设计的星座和系统中[19], [20]。它们目前正被用于SpaceX的星链卫星网络，该网络由数千颗宽带互联网卫星组成[21]。

+Grid拓扑被认为是低地球轨道（LEO）卫星网络中ISL的默认设计

在这种拓扑中，每颗卫星与四个邻近的卫星相连：两个在同一轨道平面，两个在相邻轨道平面[22]。这种网格状结构相对容易设计和实现；然而，它存在显著的缺点，如较短的ISL距离导致ISL跳数和端到端延迟增加，设计拓扑时未考虑源节点和目的节点，以及缺乏实现最优路由的灵活性，这些都会影响网络的整体效率。

×Grid的设计旨在提升相较于+Grid的效率

与+Grid类似，该方法也连接同一和相邻轨道平面内的卫星[16]。关键区别在于+Grid连接基于星型拓扑，而×Grid基于矩形拓扑。这种设计最小化了连接重叠，并平均将ISL跳数减少了两倍。然而，与传统网格拓扑类似，它采用一致的连接模式，这限制了其在动态场景中的灵活性。

[17]提出了一种基于模体（motifs）的拓扑设计，以改进邻居网格拓扑的性能

该方法利用频繁重复的连接模式，每颗卫星都以相同的方式与其邻居连接，从而有效减少了随时间发生的昂贵的链路变更。通过这种设计，延迟和容量等性能指标相比邻居网格提升了两倍。然而，这种方法仍然依赖于基于邻居的连接策略，缺乏满足最优路由的灵活性。

The topology-based neighbor strategies may work perfectly with an ideal satellite constellation to achieve optimal routing paths. For instance, LEO satellites should be deployed in orbital planes with the same or nearly the same altitude, and the inclination and Right Ascension of Ascending Node (RAAN) of the orbits should be equally spaced. This configuration optimizes the distance between parallel orbits and ensures that the distance between satellites within the same orbit is equally spaced, thus achieving optimal routing paths. However, achieving this ideal LEO satellite constellation is challenging. Based on real-time Two-Line Element (TLE) statistical data for LEO satellite experiment, the constellation is not ideal [23]. Not all orbital planes are parallel; some orbits intersect with others, resulting in satellites moving in non-parallel directions. The inclinations and RAANs of all orbits are not equally spaced, causing some orbits to be very close to each other, which increases hop counts for grid-based topologies. Additionally, the number of satellites in an orbit and their spacing are not evenly divided, and the perigees of orbits are not the same or nearly the same. These factors indicate that the topology design based on neighbor connections in the same and adjacent orbital planes may not always yield the optimal solution for real satellite constellations. Instead of selecting connections solely between neighbors, the authors in [22] conducted an in-depth investigation of LEO satellite topology. They analyzed key parameters that impact network performance, such as the number of orbits, the number of satellites per orbit, and inclination. This approach allows for connections between satellites with the most representative metrics, including maximum round-trip time, geodesic slowdown, and a low number of path changes. The ISLbased dynamic routing algorithm selects the optimal path that maximizes the utility function [24]. This algorithm improves key performance metrics (KPMs) such as packet drop rate, end-to-end delay, and throughput. Additionally, [25] leveraged deep reinforcement learning (DRL) to interact with satellite networks and select the optimal topology, which minimizes latency across all links. This approach achieves performance improvements in terms of latency, outperforming topologybased neighbor strategies like Motifs and +Grid by up to 8.48% and 42.86%, respectively.

基于邻居的拓扑策略在理想的卫星星座下可能完美地实现最优路由路径。例如，LEO卫星应部署在具有相同或近乎相同高度的轨道平面中，且轨道的倾角和升交点赤经（RAAN）应等距分布。这种配置优化了平行轨道间的距离，并确保了同一轨道内卫星间的距离等距，从而实现最优路由路径。然而，实现这种理想的LEO卫星星座是具有挑战性的。根据LEO卫星实验的实时两行轨道根数（TLE）统计数据，星座并非理想状态[23]。并非所有轨道平面都是平行的；一些轨道与其他轨道相交，导致卫星以非平行方向移动。所有轨道的倾角和升交点赤经并非等距分布，导致一些轨道彼此非常接近，这增加了基于网格的拓扑的跳数。此外，轨道内的卫星数量及其间距并非均匀划分，且轨道的近地点也并非相同或近乎相同。这些因素表明，基于同一和相邻轨道平面中邻居连接的拓扑设计，对于真实的卫星星座而言，可能并不总能产生最优解。文献[22]的作者们没有仅仅在邻居间选择连接，而是对LEO卫星拓扑进行了深入研究。他们分析了影响网络性能的关键参数，如轨道数量、每轨道卫星数量和轨道倾角。这种方法允许在具有最具代表性指标的卫星之间建立连接，这些指标包括最大往返时间、测地线减速和较少的路径变化次数。基于ISL的动态路由算法选择能够最大化效用函数的最佳路径[24]。该算法改进了如丢包率、端到端延迟和吞吐量等关键性能指标（KPMs）。此外，[25]利用深度强化学习（DRL）与卫星网络交互并选择最优拓扑，从而最小化所有链路的延迟。该方法在延迟方面取得了性能提升，分别比基于邻居的拓扑策略（如Motifs和+Grid）高出8.48%和42.86%

Research Challenge and Motivation (RCM): The challenge remains for neighbor-grid designs due to the imperfect LEO satellite constellations discussed above. The goal of gridbased topologies is to maximize satellite network performance. The research question should be why we select the nearest neighbors rather than focusing on selecting links based on their specific performance metrics. Selecting optimal paths according to their performance metrics can address concerns regarding the ideal constellation, which requires equal spacing between orbital planes, equally spaced LEO satellites within the same orbit, and similar or nearly identical perigees of orbits. This motivation drives the studies in [22], [24], [25] to develop various methods to select the topology that can directly maximize the KPMs of entire links, such as latency, link churn, packet loss rate, throughput, and utility function. However, a drawback of these previous studies is the lack of consideration for time-dependent performance, which is affected by the dynamic movement of satellites over time. These studies focus solely on selecting satellites based on their performance at each time step. Given the fast movement of LEO satellites, which can reach speeds of up to 7.66 km/s, the satellite selected at a previous time step may move far away from others or may select the next satellite that does not align with the optimal routing path from source to destination. Therefore, a novel research topic revolves around proposing an optimal topology design strategy that consistently selects satellites with high performance all the time.

研究挑战与动机 (RCM)：由于上述不完美的LEO卫星星座，基于邻居的网格设计仍然面临挑战。基于网格的拓扑的目标是最大化卫星网络性能。研究问题应该是，为什么我们选择最近的邻居，而不是专注于根据其特定性能指标来选择链路。根据性能指标选择最优路径可以解决对理想星座的担忧，理想星座要求轨道平面间等距、同一轨道内LEO卫星等距分布，以及相似或近乎相同的轨道近地点。这一动机驱动了[22], [24], [25]中的研究，以开发各种方法来选择能够直接最大化整个链路KPMs（如延迟、链路抖动、丢包率、吞吐量和效用函数）的拓扑。然而，这些先前研究的一个缺点是缺乏对时变性能的考量，该性能会受到卫星随时间动态移动的影响。这些研究仅仅关注在每个时间步根据其性能选择卫星。鉴于LEO卫星高达7.66公里/秒的快速移动，前一时间步选择的卫星可能已经移动到很远的地方，或者其选择的下一颗卫星可能与从源到目的地的最优路由路径不符。因此，一个新的研究课题围绕着提出一种能够持续选择在所有时间内都具有高性能的卫星的最优拓扑设计策略。

In this study, we propose (i) a Dynamic Time-Expanded Graph (DTEG)-based Optimal Topology Design (DoTD) algorithm to optimize the time-variant satellite topology that maximizes network capacity and simultaneously, minimizes latency and link churn, even with the dynamic changes in space networks due to the fast movement of LEO satellites. Expanding on the previously developed xeoverse simulator [26], we released SpaceNet simulator as well as the source code and datasets to the community for further research [1]. The contributions of our study are outlined as follows.

• We analyze the visibility of LEO satellite by considering the elevation angle (EA) and key orbital parameters, including the argument of perigee, true anomaly, right ascension of the ascending node (RAAN), and inclination. Based on this analysis, we formulate a new space network topology optimization problem, where the multi-objective functions are network capacity, latency, and link churn. The optimization is subject to constraints, such as the visibility of LEO satellites, communication distance, ISL duplex, and the limited number of links that each satellite can select to create the network.

• We propose a novel DoTD algorithm to address the space network optimization problem. Using DoTD, the optimization problem is transformed into a time-dependent scoring function. This function is derived by normalizing the multiple objective functions to a common scale ranging from 0 to 1. This approach enables each LEO satellite to evaluate and choose other satellites for establishing the connections based on their achievable scores.

• We provide proofs demonstrating that: (1) the design of the score function remains finite, thus ensuring its validity for evaluation over time without limitations, (2) the proposed DoTD algorithm consistently achieves optimal performance, and (3) the time complexity of the DoTD algorithm is approximate to O(M 2 ).

• Finally, we augment our proposed DoTD algorithm with a Open Shortest Path First (OSPF) routing algorithm to further optimize the routing path for communication between GS sources and destinations.

在本研究中，我们提出 (i)一种基于动态时间扩展图（DTEG）的最优拓扑设计（DoTD）算法，以优化时变卫星拓扑，即使在由于LEO卫星快速移动导致空间网络动态变化的情况下，也能最大化网络容量，同时最小化延迟和链路抖动。在先前开发的xeoverse仿真器[26]的基础上，我们发布了SpaceNet仿真器以及源代码和数据集给社区以供进一步研究[1]。我们研究的贡献概述如下:

• 我们通过考虑仰角（EA）和关键轨道参数，包括近地点幅角、真近点角、升交点赤经（RAAN）和轨道倾角，来分析LEO卫星的可见性。基于此分析，我们构建了一个新的空间网络拓扑优化问题，其多目标函数为网络容量、延迟和链路抖动。该优化受到诸如LEO卫星可见性、通信距离、ISL双工以及每颗卫星为构建网络可选择的有限链路数量等约束

• 我们提出了一种新颖的DoTD算法来解决空间网络优化问题。使用DoTD，该优化问题被转换为一个时变评分函数。该函数通过将多目标函数归一化到一个0到1的通用尺度而得出。这种方法使每颗LEO卫星能够根据其可达成的分数来评估和选择其他卫星以建立连接

• 我们提供了证明，表明：(1)所设计的评分函数保持有限，从而确保其在评估中随时间推移的有效性，不受限制；(2)所提出的DoTD算法能够持续实现最优性能；以及(3)DoTD算法的时间复杂度近似为O(M²)

• 最后，我们将我们提出的DoTD算法与开放最短路径优先（OSPF）路由算法相结合，以进一步优化地面站源和目的地之间的通信路由路径

Experiment: We experimentally evaluate by enhancing xeoverse [26] with the proposed DoTD algorithm along with two other baseline methods, Greedy and +Grid. Results show that the DoTD achieves an average capacity increase of 28.09%, a hop count decrement of 10.91%, and a latency reduction of 39.71% compared to the Greedy method. Surprisingly, it enhances capacity by up to 70.47%, reduces hop count by 81.82%, and decreases latency by up to 96.61% compared to the +Grid method. Additionally, DoTD significantly minimizes the link churn compared to those of greedy and +Grid, significantly improving service continuity and stability.

我们通过在xeoverse [26]上增强我们提出的DoTD算法以及另外两种基线方法——贪心算法（Greedy）和+Grid——来进行实验性评估。结果显示，与贪心算法相比，DoTD实现了平均28.09%的容量提升、10.91%的跳数减少和39.71%的延迟降低。令人惊讶的是，与+Grid方法相比，它将容量提升了高达70.47%，跳数减少了81.82%，延迟降低了高达96.61%。此外，与贪心算法和+Grid相比，DoTD显著最小化了链路抖动，极大地改善了服务的连续性和稳定性。

TL; DR

背景知识补充

(1) +Grid

(2) xGrid

(3) Motifs

PS: Based on this paper

(1) 核心:

引入了一个时变评分函数 (time-dependent scoring function) 来解决动态的拓扑优化问题

它摒弃了仅在当前时刻选择最佳链路的短视策略，而是通过一种类似动态规划的方法，让卫星能够评估并选择在未来一段时间内能持续提供高性能的连接

信念: 通过历史分数的迭代，将时间维度融入拓扑决策中，使得链路选择具有前瞻性，从而在动态变化的环境中保持网络的整体性能 (历史得分越高 -> 越稳定、性能越好 -> 未来良好的工作可能性越大)

(2) 相较于其他工作的亮点:

1. 传统的+Grid、×Grid等基于邻居的拓扑策略，在面对不规则、非理想的真实LEO星座时性能不佳
   1. 问题1: +Grid和×Grid等策略强制卫星连接其在“逻辑上”的邻居
   2. 比如: 最优路径可能是“斜着”连接一颗在非相邻轨道上的卫星，但+Grid的僵化规则不允许这样做。它只能在相邻轨道间“之”字形地前进
   3. 问题2: 在设计拓扑时，没有考虑数据传输的源和目的地 ，只是机械地执行本地连接规则 (缺乏全局视野)
2. 一些更先进的、基于当前性能指标（如DRL或效用函数）的优化方法，又忽略了卫星高速移动（高达7.66 km/s）带来的时变性问题
   1. 可能当前的连接, 对于这一时刻没问题, 但全然不适合下一时刻
   2. 因此, 目前这类优化都是基于 snapshot 来做的, 只考虑瞬时切片

最大的亮点是引入了“时间”作为拓扑设计的核心维度。通过结合历史得分的评分函数，DoTD能够选择在动态变化中持续保持高性能的链路，有效解决了现有方法“只顾眼前”的短视问题