4. 星间链路路由问题定义
星间链路（Inter-Satellite Link, ISL）路由与地面互联网路由最大的区别在于：网络拓扑本身是时变的。低轨（LEO）星座中，卫星以约 7.5 km/s 的速度绕地飞行，星间链路的通断、距离、时延都在持续变化，且这种变化在轨道动力学下是可预测的。因此，星间路由问题的本质不是"在静态图上找最短路径"，而是"在时间扩展图上，为业务流选择一条满足约束、优化目标函数的端到端路径"。本节把这个问题拆成四个要素：路由目标、约束条件、优化指标、问题分类，并给出可操作的建模方式。
一、路由目标：要解决什么
星间路由的目标可以分三个层次理解。第一层是可达性：在任意时刻，源卫星与目的卫星之间是否存在一条由当前可用 ISL 组成的路径。第二层是路径有效性：这条路径在业务传输的持续时间内是否始终可用，即路径上的每条链路在传输窗口内都不中断。第三层是目标最优性：在满足前两层的前提下，使某个或某组性能指标达到最优。可达性是硬门槛，有效性是时间维度的硬门槛，最优性才是路由算法真正比拼的地方。
以一条典型 LEO 极轨星座为例：卫星 A 在 t=0 时刻要把数据送到相隔 8 跳的卫星 B。若只按 t=0 的瞬时拓扑算最短路径，可能选到一条 3 跳后就会因轨道面交叉而断开的链路；正确做法是计算"路径在 [0, T] 内是否连续可用"，T 取业务传输时长。这就是星间路由与地面路由在目标定义上的根本差异。
二、约束条件：不能违反什么
约束条件决定了可行解空间，主要分四类。
- 拓扑约束：每条 ISL 只在特定时间窗口内存在。同轨相邻卫星链路通常持续存在，异轨链路随纬度变化周期性通断。路由必须只在链路"存在"的时间段内使用它。
- 资源约束：每颗卫星的星载路由器端口数有限（典型 4～6 个 ISL 端口），每条链路的带宽、缓冲区、发射功率有限。多业务并发时，链路容量是共享资源。
- 时延与跳数约束：某些业务（如测控指令）要求端到端时延不超过阈值，或跳数不超过上限，避免路径过长导致抖动累积。
- 生存性与可靠性约束：路径应尽量避免单点故障，或在关键节点失效时仍能维持连通。部分军事/应急场景要求路径不经过特定区域上空。
这些约束中，拓扑约束是星间路由特有的、也是最难处理的——它把静态图问题变成了时间依赖图问题。
三、优化指标：比什么
常见优化指标包括：端到端时延（传播时延 + 排队时延 + 处理时延）、时延抖动、丢包率、吞吐量、路径切换次数、负载均衡度、能耗。不同业务对这些指标的敏感度不同：语音/视频业务重时延与抖动，数据回传重吞吐量，而控制信令重可靠性与切换次数。
实际工程中很少只优化单一指标，而是采用加权组合或分层优化。例如把时延作为主目标，把切换次数作为次目标，在时延相近的候选路径中选切换更少的那条，以减少路由震荡。下面这张图给出了从"业务需求"到"约束筛选"再到"指标排序"的完整问题定义链路，并标出了四类约束与主要优化指标之间的对应关系。
四、问题分类：属于哪类问题
从数学结构看，星间路由问题可以按三个维度分类。
按时间维度：分为静态路由与动态路由。静态路由假设拓扑在路由计算周期内不变，适用于同轨链路或短时窗口；动态路由显式建模拓扑的时间演化，通常用时间扩展图（Time-Expanded Graph, TEG）把时间离散成若干时隙，每个时隙复制一份拓扑快照，再在快照之间加"存储边"表示数据在卫星上等待。这样，一条端到端路径就变成 TEG 上从 (源, t0) 到 (目的, t0+T) 的一条路径。
按优化目标数量：分为单目标路由与多目标路由。单目标通常求最短时延或最大吞吐；多目标则需要在 Pareto 前沿上做权衡，常用加权和法、分层优化或约束法处理。
按求解方式：分为集中式与分布式。集中式由地面或主控卫星收集全局拓扑，统一计算路由表再分发，适合星座规模较小、拓扑变化可预测的场景；分布式由各卫星基于本地信息与邻居交换协议（类似 OSPF/OLSR 的星载版本）自主决策，扩展性好但收敛速度受链路时延和拓扑变化率制约。
从计算复杂度看，静态最短路径是多项式可解的（Dijkstra, O(N²) 或 O(E log N)）；但一旦加入时间窗口、带宽容量、多业务并发等约束，问题往往退化为 NP-hard 的多约束路径问题。工程上通常不追求全局最优，而是用启发式算法（如基于 TEG 的时延约束最短路径、蚁群算法、遗传算法）在可接受的计算时间内得到近优解。
五、一个可操作的建模示例
假设某 LEO 星座有 72 颗卫星、6 个轨道面，每颗卫星 4 条 ISL。业务从卫星 S1 到 S8，传输时长 120 s，要求端到端时延不超过 80 ms，跳数不超过 6。建模步骤如下：
- 以 10 s 为时隙，把 120 s 划分为 12 个时隙，生成 12 张拓扑快照。
- 对每张快照，标记每条 ISL 的可用状态、传播时延（由星间距离除以光速得到，典型 1000～5000 km 对应 3.3～16.7 ms）和剩余带宽。
- 在快照之间加入存储边，权重为时隙长度 10 s（表示数据在卫星上等待一个时隙的代价）。
- 在 TEG 上搜索从 (S1, t0) 到 (S8, t0+120s) 的路径，约束为累计传播时延 ≤ 80 ms、跳数 ≤ 6。
- 若存在多条可行路径，按"时延优先、切换次数次之"排序，输出主路径与一条备份路径。
这个示例中，时延约束 80 ms 和跳数约束 6 是硬约束，切换次数是软目标。实际运行时，若主路径在某个时隙因链路中断而失效，备份路径可立即接管，避免业务中断。判断路由是否成功的依据是：在 120 s 内，端到端时延是否始终 ≤ 80 ms，且路径切换次数是否在可接受范围内（例如 ≤ 2 次）。
总结来说，星间链路路由问题的定义可以浓缩为一句话：在时间依赖的星座拓扑上，为业务流寻找一条满足拓扑、资源、时延与生存性约束，并使指定优化指标达到最优或近优的端到端路径。目标决定方向，约束划定边界，指标给出排序依据，分类帮助选择求解策略。四者缺一不可，共同构成后续路由算法设计与仿真的问题基础。