Shaping an optimization strategy¶

Now, we narrow down the search space using domain knowledge and key takeaways from the previous section. The outlined strategy helps optimization techniques converge faster.

Reducing the search space: As discussed earlier, the design of a single shell of a constellation deals with six parameters, i.e., h, i, e, o, n, and p. Since the topological structure is consistent and performance fluctuation is not significant over time, t could be ignored (takeaway (1)). Based on the observation of coverage metrics, these six parameters can be classified into two groups:

GROUP-I: Set of parameters that impacts the constellation’s coverage, i.e., h, e, and i.
GROUP-II: Set of parameters that do not impact coverage, i.e., o, n, and p.

Now, notice that when the parameters of GROUP-I are optimized, then in GROUP-II, any number of orbits o which is sufficiently larger than the number of satellites per orbit n at phase offset p = 0.5 produce higher throughput than any other combinations (takeaway (5)). Hence, in our search strategy, we keep o to its maximum value (which will determine the value of n as well), p = 0.5, and then optimize the values of h, e, and i. Therefore, the search space is reduced to these three parameters of GROUP-I.

Furthermore, the scope of varying h is limited by various non-networking factors, i.e., FCC, ITU regulation [19, 24], radiation hazards [73, 78], rate of orbital decays [86], etc. Apart from that, because of symmetric performance outcomes (takeaway (3)), we restrict the parameters i up to 90 ◦ . It is also desirable to avoid too low inclination to reduce the interference with GEO satellites that operate over the Equator [26]. The range of e is also limited by the satellites and GSes communication hardware, which is not incorporated in our implementation.

Proposed search strategy: After trimming down the search space, LEOCraft tries to optimize the values of i, e, and h by using Variable Neighborhood Search (VNS) [57,74] strategy. VNS starts with an initial solution x; in every iteration, it discovers the neighborhood of the current solution N(x) and takes the best neighborhood. The process is repeated until the convergence criteria are reached (i.e., the solution starts saturating). In LEOCraft, we use a random step size at every iteration. While choosing the initial solution, we observe that i ≈ 30 ◦ and e between 10 ◦ to 20 ◦ converge faster. The intuition behind this is that the median latitude of the 100 most populous cities is 29.6 ◦ , and lower elevation gives good throughput for high path diversity (takeaway (4)).

主要目标: 通过领域知识(Domain Knowledge)大幅度裁剪(Pruning)庞大的搜索空间, 从而让优化算法收敛得更快

1. 剔除时间维度与参数分组 (Reducing the search space)¶

剔除时间 (\(t\)): 基于上一章的洞见1(LEO 动态特性导致的性能波动很小), 在优化搜索时可以直接忽略时间维度 \(t\), 从而极大减少单次评估的计算量.
==参数解耦与分组: 作者将决定单壳层设计的 6 个核心参数分为了两组: ==
- GROUP-I(影响覆盖率的参数): 海拔 (\(h\))、仰角 (\(e\))、倾角 (\(i\)).
- GROUP-II(不影响覆盖率的参数): 轨道数 (\(o\))、每轨道卫星数 (\(n\))、相位偏移 (\(p\)).

2. 降维打击: 固定拓扑参数 (Fixing GROUP-II)¶

利用洞见直接定值:
- 基于上一章的洞见5, 作者发现只要 GROUP-I 的参数处于较优区间, 对于规模足够大的星座, 采用极大的轨道数 (\(o \gg n\)) 并设置相位偏移 \(p = 0. 5\) 总能带来更高的吞吐量.
搜索空间锐减:
- 因此, 在优化策略中, 作者直接将轨道数 \(o\) 设为最大允许值(这也同时决定了 \(n\) 的值), 并将 \(p\) 固定为 0. 5
- 这样一来, 原本 6 个维度的复杂搜索空间, 瞬间被降维(压缩)到了只剩 3 个参数(即 GROUP-I 的 \(h, e, i\))

3. 结合现实约束, 进一步缩减搜索边界 (Constraining GROUP-I)¶

对于剩下的三个参数, 作者也没有让算法去盲目全盘搜索, 而是结合了物理与现实的非网络因素进行边界限制:

限制海拔 (\(h\)): 其取值范围受到 FCC/ITU 政策法规、太空辐射危害、轨道衰减率等现实因素的严格限制.
限制倾角 (\(i\)):
- 由于网络性能在倾角上呈现对称性(洞见3), 搜索范围被砍掉一半, 限制在 \(90^\circ\) 以内
- 同时为了避免与地球同步轨道(GEO)卫星产生信号干扰, 也排除了极低倾角的选项
限制仰角 (\(e\)): 受限于卫星和地面站实际通信硬件的能力.

4. 提出高效的搜索算法: 可变邻域搜索 (Proposed search strategy: VNS)¶

算法选择:
- 在大幅修剪了搜索空间后, LEOCraft 采用可变邻域搜索(Variable Neighborhood Search, VNS)策略来寻找 \(h, e, i\) 的最优解.
聪明的初始值(Heuristics):
- VNS 算法需要一个起始解. 作者非常巧妙地将初始倾角设定在 \(i \approx 30^\circ\) 附近, 初始仰角 \(e\) 设定在 \(10^\circ\) 到 \(20^\circ\) 之间.
直觉依据:
- 因为全球人口最多的 100 个城市的中位数纬度刚好是 \(29. 6^\circ\), 而较低的仰角又能提供良好的路径多样性(洞见4)
- 从这个具有现实意义的"起点"开始搜索, 使得算法的收敛速度和效率远超传统的黑盒优化盲搜算法