Energy-effect Tasks Scheduling By Phoenix¶

Tip

一般 INFOCOM 这种巨长的算法设计我都选择让 Gemini 2.5Pro 来解读...

PHOENIX的算法设计核心思想是分层解耦和启发式决策。由于直接求解整个网络的能量优化问题（SBEO问题）是NP-hard的，作者设计了一套多步骤、分层次的调度算法，将一个复杂的全局优化问题分解为几个更易于处理的子问题。

TL; DR

Python
IF (有可用地面站 AND 卸载到地面站能在截止时间前完成):
    /*
     * 优先级 1: 零电池消耗方案 (最优先)
     * 决策: 卸载到地面站
     */
    执行 [星地卸载]

ELSE:
    /*
     * 地面站不可用或太慢，考虑在轨处理
     */
    IF (在本地处理能在截止时间前完成):
        /*
         * 优先级 2: 本地处理方案
         */
        IF (等到下一个[光照时段]再处理, 仍能满足截止时间):
            /*
             * 优先级 2.1: 优先用太阳能 (延迟处理)
             * 决策: 等待光照，本地处理
             */
             执行 [延迟本地处理]

        ELSE:
            /*
             * 优先级 2.2: 为保时效只能用电池 (立即处理)
             * 决策: 立即用电池，本地处理
             */
             执行 [实时本地处理]
        END IF

    ELSE:
        /*
         * 本地处理也无法满足时限，只能寻求星间协作
         * 优先级 3: 星间协作方案 (最后选择)
         * 决策: 卸载给“处理轨道集”中能量最充足的卫星
         */
         执行 [星间卸载]
    END IF
END IF

第一步：问题建模与优化目标定义 (SEC Battery Energy Optimization Problem)¶

在设计算法之前，论文首先对整个系统进行了数学建模，并明确了优化目标。这是所有算法设计的基础。

网络与任务建模 (图1)：
- 网络拓扑：系统被建模为一个随时间变化的图 \(G_t = (V, E_t)\)，节点 \(V\) 包括卫星（SAT）和地面站（GS）。节点间的可见性（连接）用二进制变量 \(Vis_{i,j}^t\) 表示。
- 任务定义：每个任务 \(T_k\) 被定义为一个元组，包含了任务源卫星、任务大小、计算需求、到达时间和截止时间等关键信息。
- 决策变量：引入了关键的决策变量，如 \(\tau_{i,j,t}^k\) 表示任务 \(k\) 是否通过链路 \((i,j)\) 传输， \(z_{i,k}^t\) 表示节点 \(i\) 是否在时间 \(t\) 处理任务 \(k\)。
能耗建模与优化目标 (图3)：
- 能量消耗：精确建模了卫星的能量消耗，总功耗 = 电子设备基础功耗 + 发射功率 - 太阳能板发电功率。当发电功率不足以覆盖消耗时，就需要动用电池。
- 核心优化目标：算法的最终目标是最小化所有卫星电池的最大放电深度（Depth-of-Discharge, DoD）。如公式(7)所示：\(\min \max_{s \in SAT, t \in T} (1 - B_{s,t}/B_{s}^{col})\)。DoD是衡量电池消耗的关键指标，直接关系到电池寿命和卫星的整体寿命。最小化最大DoD意味着避免任何单颗卫星的电池被过度消耗，从而延长整个星座网络的健康寿命。
- 约束条件：优化必须满足一系列现实约束，如：一颗卫星在同一时间只能处理一个任务（公式8）、任务必须在卸载完成后才能开始处理（公式9）、任务必须在截止时间前完成（公式10）。

精髓提炼：这一步的精髓在于，它没有选择简单的“最小化总能耗”作为目标，而是选择了更贴近实际、更能反映系统健康状况的“最小化最大DoD”，体现了对卫星电池寿命这一核心瓶颈的深刻理解。

第二步：分层调度策略——从轨道级到卫星级¶

由于SBEO问题是NP-hard的，无法直接求解。PHOENIX采用了一种“先粗后精”的两层调度策略，先在宏观的轨道层面进行资源分配，再在微观的单星层面进行具体的卸载决策。

2.1 集中式轨道分配 (算法1：Sunlight-aware Orbit Assignment)¶

这一步由地面任务中心执行，属于粗粒度的、离线的策略。

目的：为了避免所有卫星在决策时盲目地向全网广播和查询，任务中心预先进行规划，将整个星座的轨道划分为不同的功能集。
输入：未来一段时间内各轨道的光照时长预测 (sunlit) 和任务量预测 (target)。
核心机制 (图4)：
1. 评估能力与需求：对于每个轨道，评估其总光照时长（代表能量供应能力）和预计承载的任务量（代表能量需求）。
2. 背包问题建模：将轨道分配问题建模为一个0/1背包问题。这里的“背包”是总的任务需求，“物品”是每个轨道，“物品的重量”是该轨道的任务处理能力，“物品的价值”也是其处理能力（目标是让价值恰好等于重量）。
3. 轨道分组：求解背包问题，将一部分轨道选入“处理子集 (alternative subset)”，这些轨道将共同负责处理需要卸载的任务。剩下的轨道则构成“空闲子集 (idle subset)”，它们主要处理自己的任务，不作为卸载目标。
输出：“处理子集”的分配方案。

精髓提炼：这一步的精髓是通过集中式预规划和背包问题抽象，极大地缩小了单颗卫星在做卸载决策时的搜索空间。卫星不再需要考虑星座中的所有其他卫星，只需在指定的“处理子集”中寻找最优卸载目标，显著降低了决策的复杂度和通信开销。

2.2 分布式任务卸载决策 (算法2：Orbit-based Offloading)¶

这一步由产生任务的源卫星执行，是细粒度的、实时的决策。

目的：为当前新生成的任务找到最节能且满足时延的执行位置。
核心决策逻辑 (图4)：算法遵循一个清晰的优先级顺序：
1. 首选：卸载到地面站：检查是否有可用的地面站，并且通过星地链路传输任务能在截止时间前完成。这是最理想的节能方式，因为它完全不消耗任何卫星的电池。
2. 次选：本地处理 (光照优先)：如果无法卸载到地面，则调用Arrange函数（即算法3的逻辑）判断在本地处理是否可行。这里的关键是，它会优先尝试延迟到进入光照区再处理，以节省电池。只有当等待进入光照区会导致任务超时，它才会考虑在阴影区用电池处理。
3. 备选：星间卸载：如果前两者都不可行（例如，任务紧急，等不到本地进入光照区，也没有可用的地面站），则启动星间卸载。此时，它会向之前由算法1分配的“处理子集”中的所有卫星发送查询请求，询问它们的能量状态E[s]（综合了光照、电池电量和当前任务队列）。
4. 最终选择：源卫星选择回复能量状态E[s]最佳（即能量最充裕）的卫星作为卸载目标，并将任务发送过去。

精髓提炼：这一步的精髓在于其清晰的决策优先级。它将“零电池消耗”的地面站和“潜在零电池消耗”的本地光照处理放在最高优先级，只有在万不得已时才启动会消耗其他卫星电池的星间卸载。这体现了“能不用电池就绝不用”的设计哲学。

第三步：精细化处理时间安排 (算法3的逻辑描述)¶

这一步由最终确定要执行任务的卫星（无论是源卫星本地处理，还是接收了卸载任务的目标卫星）来执行。

目的：在确定了“在哪处理”之后，精确地决定“何时开始处理”。
核心机制 (图2)：
1. 计算时间边界：首先计算出两个关键的时间点：
  - 最早开始时间 (\(T_{earliest}\))：任务数据传输完成的时间。
  - 最晚开始时间 (\(T_{latest}\))：为了保证在任务截止时间前完成，处理工作最晚必须开始的时间点。
2. 寻找光照窗口：然后，寻找在 \([T_{earliest}, T_{latest}]\) 区间内的下一个光照时隙的起始时间 ( \(T_{sunlit}\) )。
3. 最终决策：
  - 如果 \(T_{sunlit}\) 存在且早于 \(T_{latest}\)，则将任务的开始时间安排在 \(T_{sunlit}\)。这意味着 “为了节省电池，我选择等到有太阳了再开始干活”
  - 如果下一个光照窗口来得太晚（晚于 \(T_{latest}\)），则将任务开始时间安排在 \(T_{latest}\)。这意味着 “为了不延误任务，我只能现在就用电池开始干活”

精髓提炼：这一步的精髓在于 在时延和能耗之间进行极致的权衡。它不是简单地“一有任务就做”，而是通过精确计算时间边界，在满足任务截止时间的前提下，尽可能地将计算任务推迟到有太阳能供给的时段，从而实现对电池能量的精细化管理

总结¶

PHOENIX的算法设计通过 “全局规划（轨道分配）+ 本地决策（卸载优先级）+ 精细执行（时间安排）” 的三步走策略，将一个复杂的、全局性的NP-hard问题，巧妙地分解为一系列逻辑清晰、计算开销可控的启发式步骤，最终在满足任务时效性的同时，实现了对卫星电池能耗的深度优化。

Tip

地面优先 (Ground First): 总是最先尝试完全不消耗星上电池的地面站方案
节能优先 (Energy First): 在必须由卫星处理时，总是优先考虑利用太阳能（即使需要延迟），而不是消耗宝贵的电池
时效兜底 (Deadline as Bottom-line): 只有在节能方案会导致任务超时的情况下，才会动用电池或启动更复杂的星间卸载来确保任务按时完成