跳转至

USER-DRIVEN NETWORKING ALGORITHM DESIGN

This section primarily comprises of three algorithms: the ideal networking for satellite network (INSN) algorithm, the dynamic matching networking for satellite network (DMNSN) algorithm, and the matching criterion for satellite network (MCSN) algorithm.

The INSN algorithm is responsible for generating ideal topologies for satellite networks under different time slices, which may not be practically deployable. The DMNSN algorithm aims to generate stable topologies that align with the requirements of the end-users. Finally, the MCSN algorithm is utilized to analyze the gap between the stable and ideal topologies at different times.

The relationship between these three algorithms is illustrated in Fig.4.

本节主要包含三种算法:

  • 理想卫星网络拓扑生成算法 (INSN): 在不同的 time slice 下生成卫星网络的理想拓扑结构，可能难以实际部署
  • 动态匹配卫星网络拓扑算法 (DMNSN): 对 INSN 实施“接地气化”，符合终端用户需求
  • 卫星网络匹配准则算法 (MCSN): 分析在不同 time slice 上: 稳定topo 和 理想topo 之间的差距

这三种算法之间的关系如 图 4 所示:

alt text

下面是对这三种算法的详细分析与解读:

(1) INSN算法: 生成理想动态拓扑

  • 目标: 在单一 time slice 内生成理论上的最优拓扑，作为性能基准
  • 输入:
    • 地面站点集合 \(\{S_m\}\)
    • 星间链路（ISL）的最大长度 \(L\)
    • 时间片编号 \(i\)
  • 输出: 当前时间片 \(G_i\) 的理想拓扑
  • 步骤:
    1. 找到所有可以长期稳定建立的星间链路，形成链路集合 \(\{E_N\}\)
    2. 根据卫星位置和链路长度，构建加权图 \(G_{dense}\)
    3. 使用 Dijkstra算法 计算地面站点对之间的最短路径，并将使用过的边加入最终集合 \(\{E'_N\}\)
    4. 最终输出无向非加权图 \(G_i\)，即当前时间片的理想拓扑

📌 INSN 提供了理论上的最优标准，但无法直接部署（可以作为baseline作为性能对比）

(2) DMNSN算法: 生成稳定拓扑

alt text

  • 目标: 解决 INSN 中因 time slice 变化导致的不稳定性问题，生成跨时间片稳定的目标拓扑
  • 输入:
    • 地面站点集合 \(\{S_m\}\)
    • 星间链路最大长度 \(L\)
  • 输出: 稳定目标拓扑 \(G\)
  • 步骤:
    1. 与INSN类似，找到所有可长期建立的链路集合 \(\{E_N\}\)，并构建初始图 \(G_{dense}\)
    2. 对每个时间点 \(t\)，计算卫星位置和链路权重，形成加权图 \(G_{minute}\)
    3. 使用 Dijkstra算法 计算最短路径，并记录使用过的边及其权重累计值
    4. 根据权重排序边集 \(\{E'_N\}\)，选择高频出现且满足约束条件（如源和目标未被选择超过四次）的边
    5. 最终输出无向非加权图 \(G\)，即跨时间片稳定的目标拓扑

📌 DMNSN 通过统计频繁出现的链路，实现了跨时间片更稳定、可用性更高的目标网络

DMNSN在干什么

DMNSN算法的核心目标: 解决INSN算法生成的理想动态拓扑在实际应用中的不稳定性问题。

由于卫星网络拓扑随时间片变化频繁，链路可能会出现“振荡”现象（即链路在不同时间片间频繁断开和重新建立）。因此，DMNSN旨在生成一个跨时间片稳定的目标拓扑，使网络性能更可靠，同时满足用户需求。

实现目标的方法

DMNSN通过以下步骤实现稳定拓扑设计：

  1. 初始链路集合构建：
    • 与INSN类似，首先找到所有可以长期稳定建立的星间链路，形成链路集合 \(\{E_N\}\)，并构建初始图 \(G_{dense}\)
  2. 动态权重计算：
    • 对每个时间点 \(t\)，根据卫星位置和链路长度计算加权图 \(G_{minute}\)。这里的 权重反映了链路的重要性或使用频率
  3. 路径记录与权重累计：
    • 使用 Dijkstra算法 计算地面站点之间的最短路径，并记录每条路径中使用过的边
    • 累计这些边的权重值，统计它们在一天内出现的频率
  4. 高频边筛选：
    • 根据权重排序边集 \(\{E'_N\}\)，优先选择高频出现的边
    • 为了避免单个节点过度参与连接，加入约束条件：源和目标节点不能被选择超过四次。如果某条边不满足条件，则将其丢弃
  5. 最终稳定拓扑生成：
    • 将筛选后的边集 \(\{E'_N\}\) 和节点集合 \(V_n\) 组合，生成无向非加权图 \(G\)，即跨时间片稳定的目标拓扑

关键点解析

  • 动态性问题解决： 通过统计一天内链路出现频率，DMNSN算法能够识别出“关键链路”，这些链路在多个时间片中保持稳定 ，从而减少因动态变化导致的不确定性
  • 约束条件设计： 通过限制节点连接次数（如不超过四次），确保网络设计均衡 ，避免过度集中于某些节点
  • 最终结果：生成的目标拓扑不仅具有较高的稳定性，还能尽可能接近INSN算法生成的理想动态拓扑

(3) MCSN算法: 匹配分析

  • 目标: 分析理想动态拓扑与实际稳定拓扑之间的匹配程度，并研究用户分布对目标拓扑的影响
  • 方法:
    • 利用匹配指数衡量两种拓扑之间的相似性
    • 确定影响匹配效果的因素，如用户分布对链路选择和性能优化的影响

📌 MCSN 则从分析角度出发，帮助理解用户需求与网络设计之间的关系