跳转至

SkyCastle at the Network Level: Constellation-wide Anchor Management

这一节数学和算法理论分析味太重了，看不动，直接让perplexity帮我读 🐶 😄

Understanding the Problem

问题描述

设：

  • \(S = \{s_1, s_2, ..., s_m\}\) 表示包含 \(m\) 颗卫星的集合；
  • \(U = \{u_1, u_2, ..., u_n\}\) 表示包含 \(n\) 个用户的集合；
  • \(G = \{g_1, g_2, ..., g_h\}\) 表示包含 \(h\) 个地面站（Ground Station, GS）的集合。

令二元变量 \(C_{i,j} = 1\)表示卫星 \(s_j\)管理卫星 \(s_i\)。假设时间被分割为离散时隙 \(\tau = \{t_1, t_2, ..., t_T\}\)。

定义以下二元变量：

  • \(\alpha_{i,j,k} = 1\)表示在时隙 \(t_k\)，用户 \(u_i\)能够看到卫星 \(s_j\)；
  • \(\alpha^*_{i,j,k} = 1\)表示在时隙 \(t_k\)，用户 \(u_i\)实际连接到卫星 \(s_j\)；
  • 类似地，\(\beta_{i,j,k} = 1\)表示地面站 \(g_i\)能够看到卫星 \(s_j\)，而 \(\beta^*_{i,j,k} = 1\)表示地面站实际连接到卫星。

我们用卫星之间的跳数（hops）来表示通信路径的延迟，并定义：

\(D_{i,j}\) 为卫星之间的最小跳数。

问题背景：

当发生跨集群切换（inter-cluster handover）时，用户需要选择新的锚点并重新获取地址，这可能会中断上层连接。因此，锚点管理器的目标是通过优化锚点部署和用户分配策略，在满足各种约束条件的情况下最大化用户被同一锚点管理的时间。

问题公式化

锚点部署与分配问题（Anchor Deployment and Assignment, ADA）可以形式化为以下优化问题：

目标函数：

\[ \text{max } \sum_{i=1}^{n} \sum_{p,q,A=1}^{m} \sum_{k=1}^{T} \alpha^*_{i,p,k} \cdot \alpha^*_{i,q,k-1} \cdot C_{p,A} \cdot C_{q,A} \]

该目标函数统计所有满足以下条件的四元组\((i, p, q, k)\)的数量：

  • 用户 \(u_i\) 在时隙 \((t_k, t_{k-1})\) 分别连接到卫星 \((s_p, s_q)\)；
  • 这两颗卫星属于由同一锚点管理的集群。

目标是最小化锚点切换次数，即最大化连接不中断率（Connection Uninterrupted Ratio, CUR）。

约束条件：

  1. 可见性约束： 用户只能连接到可见的卫星：

    \[ \alpha^*_{i,j,k} \leq \alpha_{i,j,k}, \quad \forall i \in [n], j \in [m], k \in [T] \]

  2. 地面站可见性约束： 地面站只能连接到可见的卫星：

    \[ \beta^*_{i,j,k} \leq \beta_{i,j,k}, \quad \forall i' \in [h], j \in [m], k \in [T] \]

  3. 延迟约束： 两颗卫星之间通过锚点的路径跳数不得超过最短路径跳数加上阈值\(\(H\)\)：

    \[ \alpha^*_{i,j,k} \cdot \beta^*_{i',j',k} \cdot [C_{j,A}(D_{j,A} + D_{A,j'}) - D_{j,j'}] \leq H \]

  4. 锚点分配约束： 每颗卫星必须由唯一一个锚点管理：

    \[ \sum_{j=1}^{m} C_{j,j'} = 1, \quad \forall j' \in [m] \]

算法 1：模式发现

该算法用于确定如何将卫星划分为集群，并选择每个集群的锚点。输入为在给定时间内可见的卫星集合和最大允许跳数 \(H\)。输出为一个表示集群模式的函数 \(f\)。

步骤：

  1. 初始化变量，包括候选锚点和最大集群大小
  2. 遍历每颗候选锚点卫星，计算其能管理的所有其他卫星组成的候选集群
  3. 如果候选集群满足延迟约束且大小大于当前最大集群，则更新最佳选择
  4. 返回最终确定的集群模式

引理 1：最大额外跳数

对于任意两颗卫星之间通过锚点传输数据，其路径跳数相较于最短路径最多增加两倍于锚点到源/目的地之间的跳数，即：

\[ D_{j,A} + D_{A,i} - D_{j,i} \leq 2D_{A,i} \]

证明思路：

将卫星轨道视为一个圆周，令每颗卫星的位置由其轨道编号和轨道内编号表示。通过几何分析得出，经过锚点传输的数据路径长度不会超过上述限制。

定理 1：NP 难度

证明 ADA 问题是 NP 难问题：

  • 假设每个用户一次只能看到一颗卫星（简化问题）。
  • 根据引理 1，满足延迟约束的候选集群可以在多项式时间内枚举。
  • 将每个候选集群视为一个“物品”，其权重为目标函数中的贡献值。
  • 将问题转化为一个带有容量限制的不相交多重背包问题（Disjunctively Constrained Knapsack Problem, DCKP），该问题已知是 NP 难问题。

因此，ADA 问题也是 NP 难。

Judiciously Deploying Anchors at LEO Satellites

问题分解与解决方法

为了解决锚点部署问题，作者将其分解为两个步骤：

  1. 确定锚点部署和集群划分方案：通过设计一个卫星集群模式，将用户通常的地理移动区域与在特定时间段内可见的卫星集合关联
  2. 设计用户选择锚点的算法：该算法旨在最大化连接的连续性比率

关键思想

  • 传统经验借鉴：在地面移动网络中，锚点的放置通常基于用户主要活动区域（如建筑物）的经验。作者将此类经验应用于卫星网络中，提出一个关键洞察：
    • 用户的常规地理移动区域可以映射到在一定时间内对用户可见的一组卫星
  • 卫星集群模式：定义为从卫星节点到卫星集合的映射关系，用函数\(f(s_A) \to S_A\)表示，其中\(s_A\)是某个卫星的锚点，\(S_A\)是其对应的卫星集群。该模式需满足：
    • 所有卫星与其锚点之间的相对位置固定
    • 使用尽可能少的实例覆盖整个星座中的所有卫星

锚点部署

  • 算法1：详细描述了如何从可见卫星中找到一个满足延迟约束的卫星集群模式
    • 遍历所有候选锚点，计算每个锚点对应的最大可见卫星数量（第4-6行）
    • 选择最大的候选集群并生成模式实例（第7-8行）
    • 最终得到完整模式（第9行）
  • 算法2：提出了启发式锚点部署算法：
    • 每轮优先选择包含最多剩余卫星的锚点（第3-8行）
    • 将属于该实例的卫星分配给该锚点管理（第9-10行）

锚点分配

采用 贪心算法 进行锚点分配，其核心思想包括：

  1. 尽量保持用户连接到同一集群内的已连接卫星和锚点
  2. 当初始或当前集群不可见时，选择新集群以延长连接时间

理论证明

作者通过定理2证明了上述贪心算法是最优的：

  • 假设当前贪心算法选择的锚点为 \(s_{Gr}(k)\)，最优算法选择为 \(s_{Opt}(k)\)
  • 若两者不同，则通过调整选择策略，可以逐步逼近最优解 \(Gr\)
  • 最终，通过归谬法证明贪心算法能够达到最优解

这一部分提出了一种高效的方法来解决LEO卫星网络中的锚点部署问题，包括设计集群划分模式和贪心分配算法。通过理论证明，该方法能够实现无缝且低延迟的互联网服务，同时最大化连接连续性比率。

Note

集群划分、锚点部署、锚点分配到用户