System Model and Problem Formulation

SYSTEM MODEL AND PROBLEM FORMULATION¶

时间与网络拓扑
- 时间被离散为多个时隙 \(T = \{1, 2, \dots, T\}\)
- 每个时隙的网络拓扑用图 \(G_t(V, E_t)\) 表示，其中节点集 \(V = \{SAT \cup ES\}\) 包括卫星集 \(SAT\) 和边缘服务器集 \(ES\)，边集 \(E_t = \{ISL_t \cup USL_t\}\) 包括星间链路 (ISL) 和用户-卫星链路 (USL)
卫星与服务器分布
- 星座中卫星均匀分布，设轨道数为 \(N\)，每轨道卫星数为 \(M\)，则卫星集为 \(SAT = \{s_1, s_2, ..., s_{M*N}\}\)
- 边缘服务器总数为 \(K\)，服务器集为 \(ES = \{es_1, es_2, ..., es_K\}\)
分cluster机制
- 多个接入卫星和一个服务卫星组成cluster，为覆盖区域内提供边缘计算服务。\(M*N\) 个卫星划分为 \(K\) 个cluster ，表示为 \(Cluster^t = \{clust_1^t, clust_2^t, ..., clust_K^t\}\)
连接规则
- 按照 +grid 方案，每颗卫星与同轨道的两颗卫星及相邻轨道的两颗卫星建立 ISL 连接
用户-卫星链路
- 用户与最近的可视卫星建立 USL 连接，受最小仰角限制（如 Starlink 的 25°）。用户位置用经纬度和高度表示，用户迁移速度远慢于卫星，可视为静止

任务卸载流程
- 用户任务通过 USL 传输至接入卫星，再通过 ISL 转发至服务卫星处理
- 访问延迟 \(d_i^t\) 定义为接入卫星到服务卫星的延迟
访问延迟计算
- 平均访问延迟：
  
  \[ D^t = \frac{1}{M*N} \sum_{i=1}^{M*N} d_i^t \]
负载分配与平衡
- 接入卫星的任务到达率服从泊松过程，其累积到达率转发至对应cluster内的服务卫星。服务卫星的总任务到达率：
  
  \[ \phi_k^t = \sum_{s_i^t \in clust_k^t} \lambda_i^t \]
- 服务卫星实际处理负载受其能力限制，若超出容量，则丢弃溢出任务。负载平衡通过标准差衡量：
  
  \[ \sigma^t = \sqrt{\frac{1}{K} \sum_{k=1}^{K} (w_k^t - \bar{w}^t)^2} \]
用户服务率
- 衡量负载均衡收益，定义为：
  
  \[ \eta_t = \frac{1}{K} \sum_{k=1}^{K} \frac{w_k^t}{\phi_k^t} \]

优化目标
- 在给定无向图 \(G_t(V, E_t)\) 的情况下，确定边缘服务器位置和任务卸载策略，以同时最小化以下两项：
  - 平均访问延迟：\(D = \frac{1}{T} \sum_{t=1}^{T} D^t\)
  - 平均负载标准差：\(\sigma = \frac{1}{T} \sum_{t=1}^{T} \sigma^t\)
决策变量
- 二进制变量 \(x_j\)：表示是否在卫星 \(s_j\) 上部署边缘服务器
- 二进制变量 \(y_{i,j}^t\)：表示时隙 \(t\) 时接入卫星 \(s_i\) 是否将任务卸载至服务卫星 \(s_j\)
约束条件
- C1: 总服务器数为 \(K\)
- C2: 每个接入卫星只能连接一个服务卫星
- C3: 无服务器部署的卫星不可作为服务节点
- C4: 服务节点实际负载不能超过其处理能力
问题表达式
多目标优化问题定义如下：

\[ min_{x_j, y_{i,j}^t} \{D, \sigma\} \\ s.t.\quad C1-C5 \]