CSSD DESIGN¶
CSSD (Cluster-based Server Deployment Design) 是一种针对 LEO 卫星星座的小规模服务器部署策略，旨在最小化平均访问延迟并尽可能平衡工作负载。
该设计将 K-median 问题（NP-hard 问题）作为理论基础，采用离线和在线两阶段方法解决！
离线阶段¶
离线阶段主要通过遗传算法（GA）确定服务器的最优部署位置：
- 在网络运营商指定的 K 个边缘服务器约束下，确定近似最优的战略部署位置
- 建立初始卸载映射关系，目标是最小化访问延迟
- 算法流程包括：
- 随机生成初始种群，每个染色体代表一种可行的服务器部署方案
- 通过适应度函数评估每个方案（适应度 = 1/平均访问延迟）
- 使用精英策略保留最优染色体
- 应用选择、交叉和变异等生物学启发的操作生成新一代解决方案
- 经过 G 代迭代后，选择适应度最高的染色体作为最终部署方案
在线阶段¶
在线阶段通过 基于集群动态信息的服务器分配算法 ，实时调整卸载映射关系：
- 利用卫星轨道感知获取实时工作负载信息
- 动态调整集群结构以平衡工作负载
- 当某个边缘服务器（集群头）工作负载高于平均水平时：
- 识别集群内访问延迟最高的卫星作为移除候选
- 寻找工作负载低于平均水平的其他集群头
- 将候选卫星重新分配到合适的集群
- 更新工作负载信息和卸载映射关系
这种方法在牺牲少量访问延迟的情况下，显著提高了系统的计算资源利用率，实现了工作负载的动态平衡。
在线阶段 讲人话
基于集群动态信息的服务器分配算法是CSSD设计中在线阶段的核心，它通过动态调整卫星集群结构来平衡工作负载。用一个具体例子详细解释这个过程：
假设我们有一个LEO卫星星座系统，其中部署了3个边缘服务器（集群头）es₁、es₂和es₃，每个服务器管理着一个卫星集群：
- 集群1 (es₁)：包含5颗接入卫星，当前工作负载为70%
- 集群2 (es₂)：包含3颗接入卫星，当前工作负载为40%
- 集群3 (es₃)：包含4颗接入卫星，当前工作负载为50%
系统平均工作负载为55.83% (加权平均)
步骤1：检测工作负载不平衡
系统通过卫星轨道感知机制获取实时工作负载信息，发现 es₁的工作负载(70%)明显高于系统平均工作负载(55.83%)，触发再平衡机制 。
步骤2：识别移除候选
算法检查集群1中的所有接入卫星， 找出访问延迟最高的卫星 。假设卫星s₅的访问延迟最高，它被标记为移除候选。
步骤3：寻找新的集群头
算法按照距离优先级对其他集群头进行排序，寻找工作负载低于平均值的集群头。在这个例子中，es₂(40%)和es₃(50%)都符合条件，但假设s₅到es₂的距离更近，所以选择es₂作为新的集群头。
步骤4：重新分配卫星
系统将s₅从集群1移除，并将其添加到集群2中：
- 集群1 (es₁)：现在包含4颗卫星，工作负载降至58%
- 集群2 (es₂)：现在包含4颗卫星，工作负载升至52%
- 集群3 (es₃)：保持不变，工作负载50%
步骤5：更新映射关系
系统更新工作负载信息和卸载映射关系：
- 取消s₅与es₁的卸载映射关系
- 建立s₅与es₂的新卸载映射关系
- 更新各集群的工作负载信息
通过这次调整，系统工作负载变得更加平衡（58%、52%、50%），最高与最低工作负载的差距从30%缩小到8%。
这种方法确实会牺牲一些访问延迟（例如s₅可能到es₂的延迟比到es₁略高），但换来的是更均衡的工作负载分布和更高的系统资源利用率，特别适合LEO卫星网络这种资源有限且动态变化的环境。