跳转至

Algorithm Design

In this section, we first decompose the problem into topology design at a single time point and topology transition on time set, and prove the approximation between the original problem and the decomposed one. We then propose CSGI, the coordinated satellite-ground interconnecting algorithm in distributed ground stations.

A. Problem decomposition

Topology design at a single time point should solve the objective function (1) at time point \(t\) which can be transformed as follows: \(\(\min Tr(D \cdot (H^t)^T) \quad (6)\)\) We divide the GS set \(\mathcal{V}_G\) into several disjoint subsets \(\{\mathcal{V}_G^1, \mathcal{V}_G^2, \dots, \mathcal{V}_G^{\epsilon}\}\), where GS \(g_j\) and \(g_{j'}\) in different subsets have no communication requirement. Then \(D\) can be decomposed into:

\[ D = D^1 + D^2 + \dots + D^{\epsilon} \quad (7) \]
\[ D^m = (d_{jj'}^m)_{|N_G| \times |N_G|} = \begin{cases} d_{jj'}, & \text{if } g_j, g_{j'} \in \mathcal{V}_G^m \\ 0, & \text{otherwise} \end{cases} \quad (8) \]
\[ Tr(D \cdot (H^t)^T) = \sum_{m=1}^{\epsilon} Tr(D^m \cdot (H^t)^T) \quad (9) \]

The objective function (6) is equivalent to:

\[ \forall 1 \le m \le \epsilon, \min Tr(D^m \cdot (H^t)^T) \quad (10) \]

The scale of the problem can be reduced, as the solutions of \(\epsilon\) functions are independent of each other. The division of disjoint subsets can be easily achieved by using Disjoint Set Union. For the convenience of description later, we assume that \(\mathcal{V}_G\) is already one of the divided disjoint subsets. The algorithm of solving the topology design subproblem at time \(t\) is illustrated in V-B.

Topology design on time set \(\mathcal{T}\) cannot be simply decomposed into optimization design problems at multiple time points. However, we can reformulate the problem and propose a simple but effective topology transition algorithm. The result value \(opt^+\) of our algorithm and the theoretical optimal value \(opt^*\) can be controlled within a certain range. The optimal theoretical value \(opt^*\) can be written as follows:

\[ opt^* = \min \frac{\sum_{j=1}^{N_G} \sum_{j'=1}^{N_G} d_{jj'} h_{jj'}^{t_0}}{\sum_{j=1}^{N_G} \sum_{j'=1}^{N_G} d_{jj'}} \le \min \frac{\sum_{j=1}^{N_G} \sum_{j'=1}^{N_G} \max_{1 \le t \le T} d_{jj'} h_{jj'}^t}{\sum_{j=1}^{N_G} \sum_{j'=1}^{N_G} d_{jj'}} = opt \quad (11) \]

which is just the optimal value at the single time point \(t_0\). If we can control the \(|h_{jj'}^{t_0} - h_{jj'}^t| < \xi\), then \(opt^+ - opt^* < \xi\). We will show how to do this in V-C.

The flow of the whole algorithm is to perform a topology design at a single time point at the beginning, as shown in Algorithm 2, and then use the topology transition algorithm to perform the topology design at later time points, as shown in Algorithm 3. If the communication requirements of GS pairs \(D\) change, Algorithm 2 will be evoked again.

TL; DR

核心思想是: 将一个复杂、跨时间的全局优化问题，分解为两个更易于处理的子问题，并提出相应的求解策略

  1. 子问题一：单一时间点的拓扑设计

    • 目标：首先解决在某个特定时间点 \(t\) 如何设计最优网络拓扑的问题
    • 方法：通过一个数学变换（公式6），将原问题转化。核心技巧是，根据地面站（GS）之间的通信需求，使用不交集并查集 (Disjoint Set Union) 算法将所有GS分成若干个相互独立的组
    • 优势：这样一来，原来一个大的优化问题就被分解成了多个可以并行、独立求解的小问题（公式10），大大降低了问题的计算规模

  2. 子问题二：跨时间集的拓扑演进（转换）

    • 挑战：不能简单地在每个时间点都独立地求解最优拓扑，因为这会忽略跨时间的稳定性要求 (比如不同时间之间的需求依赖)
    • 策略（近似算法）：他们提出了一种近似策略
      • 首先，在初始时刻 \(t_0\) 计算出一个最优的拓扑方案（其值为 \(opt^*\)）
      • 然后，在后续的时间里，不再追求每个时刻的绝对最优，而是通过一个 “拓扑转换算法” 来调整网络，其目标是让后续任意时刻 \(t\) 的网络性能（跳数 \(h_{jj'}^t\)）与初始时刻的性能（\(h_{jj'}^{t_0}\)）差距尽可能小
      • 控制在 \(\xi\) 以内
    • 保证：通过这种方式，虽然得到的解（\(opt^+\)）不一定是全局理论最优解（\(opt^*\)），但可以保证其性能与最优解的差距在一个可控的范围内

整体算法流程：

  1. 开始：运行算法2，进行一次完整的、最优的“单一时间点拓扑设计”
  2. 后续：运行算法3（拓扑转换算法），在之前的基础上进行微调，以适应网络变化
  3. 例外：如果地面站之间的通信需求本身发生了变化，则需要重新触发算法2，进行一次全新的拓扑设计

B. Satellite-ground topology design at a single time point

Due to the large number of visible satellites of the GS, even the topology design at a single time point is very complicated, and it is difficult to find the optimal solution in a limited time. We design Algorithm 2 to approximately solve the optimal satellite-ground topology design at time \(t\). The core idea is to reduce the size of candidate satellites and prune possible options based on existing constraints and findings.

Proposition 1: The topology change interval between a GS pair will not exceed the remaining service time of satellites connected to the two GSes.

According to constraint (5) and proposition 1, the remaining service time of the access satellite should be guaranteed, ensuring the average topology interval exceeds \(\theta_T\). Therefore, we can first select the candidate satellite set where the satellite meets the minimum remaining service time requirement.

Proposition 2: The hop count from adjacent satellites in the same orbit or from adjacent satellites in the adjacent orbits to any satellite is similar (only one hop difference).

We then map the visible satellites of the GS at a certain time to the \(N \times M\) mesh where the coordinate of the satellite \(s_i\) is \((i^p, i^q)\). Figure 6 (left) shows the mesh where the visible satellites of the 6 GSes are mapped at a certain time under Kuiper. Taking the Sydney station as an example, the satellites are clearly converged into two clusters in the mesh. Figure 6 (right) shows the simulated constellation scene. The cluster on the left in the mesh corresponds to the satellites running from north to south in the simulated scene, and the cluster on the right corresponds to the satellites running from south to north. Based on proposition 2, it can be deduced that the hop count of satellites in the same cluster to any satellite are similar. We use the center point of each cluster, which may not be the real satellite, to replace all the satellites in the cluster. The number of candidate satellites of each GS can then be reduced to two. Line 2 in Algorithm 2 calculates the variable \(\theta\) as the minimum remaining service time requirement of satellites, ensuring the current average topology change interval is no less than \(\theta_T\). Line 7 to 8 select the candidate satellite set for the GS \(g_j\) that meets the remaining service time requirement and moves from north to south, denoted as \(SC_j^0\). Line 9 to 10 select the candidate satellite set that meets the remaining service time requirement and runs from north to south, denoted as \(SC_j^1\). Line 13 to 14 calculate the center point of \(SC_j^0\) and \(SC_j^1\), denoted as \(\mu_j^0\) and \(\mu_j^1\). Line 16 to 17 find the set of center points based on the objective function (10). This problem can be reduced to Facility Location Problem, which is known to be NP-Hard. The optimal solution can be directly computed when the number of GSes is a few dozen, and the approximate solution can be obtained by existing heuristic algorithms when the number of GSes is larger [17]. Each selected center point corresponds to a cluster of GS candidate satellites. The distance between the center points is calculated by Distance in Mesh Computation algorithm (DMC), which can be understood as the number of hops between the corresponding satellites. Finally, Line 18 to 21 select the access satellite from its selected cluster for every GS according to its distance between other center points.

单时间片算法

核心思想: 分步剪枝，降维简化

它通过一系列巧妙的步骤，将一个在海量卫星中进行选择的复杂问题，简化为一个在极少数“代表”中进行选择的简单问题。具体核心步骤如下：

  1. 第一次剪枝：基于“服务时间”

    • 根据命题1，为了保证网络的稳定性（即满足拓扑变化间隔不小于阈值 \(\theta_T\)），算法首先会剔除掉所有剩余服务时间不足的卫星
    • 这是第一轮筛选，保证了候选卫星的“质量”

  2. 第二次剪枝（核心步骤）：基于“聚类”

    • 洞察：根据命题2，物理位置上相邻的卫星（无论在同轨道还是邻近轨道），它们的路径特性（到其它任意卫星的跳数）都非常相似
    • 操作：
      • 将所有可见卫星映射到一个二维网格上
      • 观察到这些卫星会自然地形成几个簇 (Cluster)（例如，按卫星飞行方向分为“南下”和“北上”两个簇）
      • 关键简化：用一个虚拟的“中心点”来代表一整个簇的所有卫星
    • 效果：通过这种聚类和替代，每个地面站的候选卫星数量从几十个被锐减到极少数

  3. 最终决策：求解简化后的问题

    • 问题转化：为所有地面站从少数几个“中心点”中进行选择的问题，可以被转化为一个经典的 “设施选址问题” (Facility Location Problem)。这是一个已知的NP-Hard问题，但在地面站数量不多时有精确解，数量多时也有成熟的近似算法
    • 求解：算法求解这个“设施选址问题”，为每个地面站的“簇群”分配一个最优的“中心点”
    • 反向映射：最后，每个地面站再从被选定归属的那个真实卫星簇中，根据到其它“中心点”的距离等因素，挑选出最终要连接的那一颗卫星

总而言之，该算法通过 “服务时间过滤” 和 “空间位置聚类” 两大策略，极大地缩小了搜索空间，从而能够高效地找到一个近似最优的星地连接方案

C. Topology transition on time set

As illustrated before, assuming the optimal topology design at \(t_0\) has been computed, the optimization function at \(t\) can be transferred to control \(|h_{jj'}^t - h_{jj'}^{t_0}| < \xi\) and \(\xi > 0\) should be as small as possible. We design Algorithm 3 to supplement it. It is obvious that \(|h_{jj'}^t - h_{jj'}^{t_0}| = 0 < \xi\) if the topology is same at time \(t\) and \(t_0\). Therefore, the topology should be kept unchanged until one connected satellite moves out of the transmission range, as shown in line 3 to 10.

Proposition 3: If the satellite connected to \(g_j\) changes from \(s(x_1, y_1)\) to \(s(x_1 + \Delta x, y_1 + \Delta y)\), and the satellite connected to \(g_j'\) changes from \(s(x_2, y_2)\) to \(s(x_2 + \Delta x, y_2 + \Delta x)\), then \(h_{jj'}^t - h_{jj'}^{t_0} = 0\).

When the topology has to be changed, the remaining service time of candidate satellites should also be no less than the minimum service time requirement. Based on proposition 3, if the distributed GSes can handover satellite in the same mode through coordination, that is, the same number of inter-orbit spacing and intra-orbit spacing, \(\xi\) will be minimized. Line 12 to 17 get the set of possible inter-orbit and intra-orbit spacing before and after handover for each GS \(g_j\), denoted as \(\Delta^t XY_j\). Line 18 gets the most frequent element in these \(N_G\) sets, denoted as \((\Delta^t x, \Delta^t y)\). Line 19 to 27 decide which satellite to handover for each GS \(g_j\), according to their hops between \(s((\alpha_j^p + \Delta x)\%N, (\alpha_j^q + \Delta y)\%M)\).

核心目标是：当网络拓扑 必须 发生改变时，应如何选择新的连接，才能使得网络性能（以跳数 \(h_{jj'}^t\) 衡量）的 变化量 \(\xi\) 最小。这是一种在动态变化中追求“稳定”的策略

(1) 基本原则：能不换，则不换

算法的首选策略是维持现状。只要当前所有地面站（GS）连接的卫星都还在服务范围内，网络拓扑就保持不变。

  • 原因: 在这种情况下，网络的跳数 \(h_{jj'}^t\) 与初始时刻 \(t_0\) 的跳数 \(h_{jj'}^{t_0}\) 完全相同，性能变化量 \(\xi\) 自然为0。这是最理想的稳定状态
  • 触发条件: 只有当某个GS当前连接的卫星即将飞出服务范围，不得不进行切换时，才启动下面的切换算法

(2) 理论基础：“完美切换”的理想状态 (命题3)

命题3 (Proposition 3) 揭示了一个非常关键的几何学原理，是整个协同切换算法的理论基石。

  • 内容: 如果地面站 \(g_j\) 的接入卫星从坐标 \((x_1, y_1)\) 切换到 \((x_1+\Delta x, y_1+\Delta y)\)，同时另一个地面站 \(g_j'\) 的接入卫星也 按照完全相同的偏移量，从 \((x_2, y_2)\) 切换到 \((x_2+\Delta x, y_2+\Delta y)\)，那么这两个地面站之间的路径跳数将 保持不变 (\(h_{jj'}^t - h_{jj'}^{t_0} = 0\))

  • 深刻含义: 这意味着，如果所有地面站都能 “步调一致” 地行动，即它们的接入卫星在星座网格图上的移动模式（由偏移量 \((\Delta x, \Delta y)\) 定义）完全相同，那么整个网络的入口点相对几何关系就得以保持。这就像整个“接入层”进行了一次平移，而上层的星间路由路径得以维持，从而实现了性能无损的“完美切换”。此时，性能变化量 \(\xi\) 可以达到理论最小值 0

(3) 实践方法：通过“投票”实现的协同切换

在现实中，让所有GS都执行“完美切换”是极其困难的，因为每个GS上空可见的、满足服务时间要求的候选卫星各不相同。因此，算法采用了一种 近似 的协同策略，力求最大限度地接近“完美切换”的理想状态

该协同切换算法（Algorithm 3中描述）的步骤如下：

  1. 筛选候选者: 当必须切换时，对于每个GS，首先筛选出所有满足“最低剩余服务时间”要求的候选卫星。这保证了切换后的稳定性

  2. 统计“个人意愿”: 对每个GS（例如 \(g_j\)），计算出它切换到每一个候选卫星所对应的 偏移量 \((\Delta x, \Delta y)\) 。这样， 每个GS都会有一个自己可行的“切换模式”清单（\(\Delta^t XY_j\)）

  3. 寻找“集体共识”（投票）: 这是 协同 的关键。算法会汇总 所有 GS的“切换模式”清单，并从中找出被提及 频率最高 的那个偏移量，记为 \((\Delta^t x, \Delta^t y)\)。这个过程就像所有GS一起投票， 选出一个大家都最容易实现的“共同行动方案”

  4. 执行“协同切换”: 一旦“集体共识”的偏移量 \((\Delta^t x, \Delta^t y)\) 被确定，算法就会指导 每一个 GS，尽可能地去切换到一个符合该偏移量的新卫星上

总而言之，该拓扑转换方法是一种非常智能的动态调整策略。它 并非各自为战 地为每个GS寻找局部最优解，而是：

  • 追求稳定: 除非万不得已，否则保持网络不变
  • 追求协同: 在必须改变时，通过一种 投票 机制，让所有分布式地面站找到一个“共同的最佳切换模式”
  • 追求理想: 这种协同切换的目的，是为了让整个系统的行为无限逼近 命题3 所描述的 “完美切换” 理想状态，从而最大限度地抑制因切换带来的网络性能抖动，保证了网络在时间维度上的连续性和稳定性