ALGORITHM DESIGN AND EVALUATION

Network model

Definition 1: Timeslice

• 划分连续的时间 \(T\) 成许多时间间隙(time slice) \(T_1\), \(T_2\), \(T_3\) ...
• 认为：在不同的时间间隙之间，卫星-地面网络拓扑保持不变
  • eg. \(T_2\) 和 \(T_3\) 之间，卫星拓扑不变
• 在每一个Time Slice，GS都选择“离它最近”的Satellite

Definition 2: Max ISL length

• 理论硬件支持: 数万 km
• 实际数值: 5014 km

Definition 3: Network model

对于每个时间间隙, 比如 \(t\) = \(T_2\), 它对应有一个卫星网络 snapshot:

这是一张无向连通图:

\(G_t\) = (\(V\), \(E_t\))

• \(V\): 卫星节点
  • \(V\) = \(N\) x \(M\)
  • \(N\): orbital plane number
  • \(M\): satellite number on each orbit
• \(E_t\): 当前 Time Slice 的全部 ISLs
  • 每个节点的出度是 4

Definition 4: Hops and stretch between ground stations

• 地面站: \(g_i\) -> \(g_j\)
• 走的卫星: \(s_i\) -> \(s_j\)
• 卫星跳数: \(h_{ij}\)
• GS地面直线距离: \(d_{ij}\)

Problem formulation

• \(\alpha\) 较小时, \(h_{ij}\) 受系数制约较小, 因此我们更多关注于如何减小\(h_{ij}\)
• \(\alpha\) 较大时, \(h_{ij}\) 受系数制约过大, 改变它对于前项的数量级变化不大, 因此我们更多关注于如何减小 \(d_{ij}\)

Complexity analysis

O(\(TPN^2\))

• T: number of time slices
• P: number of traffic pairs
• N: node size