1. 引言

随着物联网与5G技术的推动，大量计算密集型任务出现[1] [2]，如对于智慧医疗、智慧交通和工业互联网而言，这些任务对计算资源要求较高，而自身设备因计算能力有限，难以高效处理。

为减轻地面设备计算负担，现有研究利用地面网络对任务进行卸载，例如文献[3]通过车载终端将计算任务卸载至地面边缘服务器，减少计算负担，提高系统性能；文献[4]将地面物联网终端产生的计算任务卸载至云中心、农业服务器和移动边缘计算MEC服务器，最小化系统的总长期成本。

为支持偏远地区无地面网络区域的设备进行任务卸载，现有研究将任务通过卫星中继传输到地面云计算中心，例如文献[5]提出一种用于物联网网络的卫星MEC模型，将地面设备产生的计算任务通过卫星网络中继到地面云计算中心；文献[6]针对卫星边缘计算网络场景，提出一种新的卫星边缘计算卸载策略，实现卫星与地面云计算中心之间的协同资源共享。

通过卫星中转至地面云计算中心会导致传输时延长等问题[7]，为减少任务传输时延，将计算能力下沉到卫星网络内部[8]。现有研究将任务直接卸载至低轨卫星网络，例如文献[9]为降低总任务处理时延，利用星地协同边缘计算架构，将计算任务卸载至卫星网络。文献[10]提出一种基于深度强化学习的任务卸载决策方法，优化在低轨卫星网络中的任务处理时间。文献[11]提出一种基于DDPG的低延迟卸载策略，优化任务处理时延。文献[12]研究卫星边缘计算中的任务卸载问题，提出一种多智能体算法，通过集中训练并分布式执行，有效降低了任务处理时延。

相较于地面基站而言，LEO卫星和地面用户之间的距离是处于变化状态的，而这种距离上的变化很可能会引发更高的传输延迟情况出现。并且，由于受到功耗、体积以及载重等多方面因素的限制，LEO卫星所具备的计算资源较稀缺，要想满足全部用户的任务卸载需求存在较大难度。因此，高效地运用整体LEO卫星星座有限的资源，对任务卸载策略进行优化，已然成为一个全新的挑战。此外，在实际应用中，诸多任务存在依赖关系(例如卫星遥感数据的采集与预处理)，各子任务需要以前一子任务输出为依赖，且仅当全部子任务完成时，整个任务才算完结，这无疑加剧了任务卸载策略制定的复杂性。再者，卫星网络覆盖范围广，加之任务本身具有复杂依赖关系，致使在大规模且多约束的应用场景中，求解相关问题的难度显著提升。因此，在动态变化的低轨卫星网络环境中，将具有复杂依赖关系任务的非线性DAG拓扑结构转换为一组线性且可并行处理的任务集合，并实现全域网络卸载是个难题。

为了解决上述难题，本研究旨在处理低轨卫星网络中具有复杂依赖关系任务卸载的问题，设计适应网络动态变化和任务非线性变化的卸载策略，充分利用卫星网络的全局计算能力，降低任务处理时延。本文的主要贡献如下：1) 基于有向无环图DAG对任务内部依赖关系进行建模，为高效处理依赖任务的拓扑信息，采用图神经网络GCN学习DAG特征，将具有复杂依赖关系的任务进行分解，以时延优化为目标构建任务卸载模型；2) 为有效卸载各子任务，利用深度Q网络算法，将每个区域控制器视为独立智能体，使其自主处理状态和动作，以应对网络空间的复杂性。

2. 系统模型和问题描述

如图1所示，本文将低轨卫星网络划分为H个控制域，各控制域含K颗配备MEC服务器的卫星，控制器为控制域中心卫星，负责处理任务请求及卸载，能有效处理请求并利用网络全局计算能力处理复杂任务。

本文聚焦地面网络无法覆盖的远程场景，服务地面网关及卫星直连区域。地面终端设备GU产生具有复杂依赖关系任务后发送至最近低轨卫星，卫星接收请求后转至所在控制域控制器，控制器依网络状态与任务需求指定各子任务卸载目标区域，再将结果返回卫星，卫星把子任务传至对应卸载区域的控制器。控制器接收子任务卸载请求后，依据网络资源、计算能力及负载情况，决策子任务在控制域内的具体卸载目标，保障任务高效执行与资源合理利用。

Figure 1. Computing architecture of LEO satellite network

图1. 低轨卫星网络计算架构

为了便于表达，本研究定义控制域集合为$SN=\left\{S{N}_1,S{N}_2\cdots S{N}_h\cdots S{N}_H\right\}$ ，其中域内卫星集合$S{N}_h=\left\{n_{h,1}\cdots n_{h,k}\cdots n_{h,K}\right\}$ ，使$S{N}_h\in N$ 。$GU=\left\{g{u}_1,\cdots ,g{u}_r,\cdots g{u}_R\right\}$ 表示地面终端设备集合。$T=\left\{t_1\cdots t_i\cdots t_L\right\}$ 表示时间集合，$VS=\left\{V_1,V_2\cdots V_q\cdots V_Q\right\}$ 是任务集合。此外，$\left(n_{h,j},n_{h,k}\right)$ 是从卫星$n_{h,j}$ 到$n_{h,k}$ 的星间链路，链路$\left(g{u}_r,n_{h,k}\right)$ 是从地面终端设备$g{u}_r$ 到卫星$n_{h,k}$ 的星地链路。

2.1. 链路通信模型

在时隙$t_i$ ，计算星间链路ISL从卫星$n_{h,j}$ 到卫星$n_{h,k}$ 的传输速率表示为：

$\begin{array}{c}{C}_i^{\left(h,j\right),\left(h,k\right)}=\frac{P{t}_i^{h,j}\cdot G_{tr}^{h,j}\cdot G_{re}^{h,k}\cdot L_t\cdot L{p}_i^{\left(h,j\right),\left(h,k\right)}}{K\cdot T\cdot {\left(\frac{Eb}{No}\right)}_{req}\cdot LM}\end{array}$ (1)

$\begin{array}{c}L{p}_i^{\left(h,j\right),\left(h,k\right)}={\left(\frac{c}{4\pi \cdot s{l}_i^{\left(h,j\right),\left(h,k\right)}\cdot F}\right)}^2\end{array}$ (2)

其中$P{t}_i^{h,j}$ 为在$t_i$ 时刻卫星$n_{h,j}$ 的传输功率，$G_{tr}^{h,j}$ 和$G_{re}^{h,k}$ 表示卫星$n_{h,j}$ 和卫星$n_{h,k}$ 的传输天线增益和接收天线增益，$L_t$ 是其他链路损耗，$L{p}_i^{\left(h,j\right),\left(\text{h},k\right)}$ 为在$t_i$ 时刻卫星$n_{h,j}$ 到卫星$n_{h,k}$ 星间的自由空间损耗，$c$ 为光速，$s{l}_i^{\left(h,j\right),\left(h,k\right)}$ 为$t_i$ 时刻卫星$n_{h,j}$ 到卫星$n_{h,k}$ 的链路长度，F为通信频率，K为玻尔兹曼常数，T为噪声温度，

${\left(Eb/No\right)}_{req}$ 为所需的每比特接收能量与一定噪声密度的比值，LM为链路余量。

将任务传输时延表述为星地链路传输时延和星间链路传输时延，其中星间链路传输时延表示为

$\begin{array}{c}t{d}_{q,n}={\displaystyle \sum }_{h=1}^H{\displaystyle \sum }_{j=1}^K{\displaystyle \sum }_{k=1}^K\left[M_{\left(h,j\right),\left(h,k\right)}\cdot \left(\frac{s{l}_i^{\left(h,j\right),\left(h,k\right)}}{c}\right)+\frac{{{\displaystyle \sum }}_{n=1}^U{\phi }_{q,n}^{\left(h,j\right),\left(h,k\right)}\cdot v_{q,n}}{C_i^{\left(r,k\right)}}\right]\end{array}$ (3)

其中$M_{\left(h,j\right),\left(\text{h},k\right)}$ 表示星间链路$s{l}_i^{\left(h,j\right),\left(\text{h},k\right)}$ 是否传输任务，$M_{\left(h,j\right),\left(\text{h},k\right)}\in \left\{0,1\right\}$ 。${\phi }_{q,n}^{\left(h,j\right),\left(\text{h},k\right)}$ 表示任务$v_{q,n}$ 是否占用链路$s{l}_i^{\left(h,j\right),\left(\text{h},k\right)}$ ，${\phi }_{q,n}^{\left(h,j\right),\left(\text{h},k\right)}\in \left\{0,1\right\}$ 。星地链路传输时延表示为：

$\begin{array}{c}t{d}_q^{\left(r\right),\left(h,k\right)}=\frac{{{\displaystyle \sum }}_{n=1}^U{v}_{q,n}}{C_i^{\left(r\right),\left(h,k\right)}}\end{array}$ (4)

其中$C_i^{\left(r\right),\left(\text{h},k\right)}$ 为第$t_i$ 时隙地面设备$g{u}_r$ 到卫星$n_{h,k}$ 的速率。

2.2. 卫星任务队列模型

每个LEO卫星具有任务队列来存储卸载的任务。在时隙$t_i$ 开始时，$a{t}_{h,k}\left(i\right)$ 表示由卫星$n_{h,k}$ 执行卸载的任务：

$\begin{array}{c}a{t}_{h,k}\left(i\right)={\displaystyle \sum }_{n=1}^U\left({\omega }_{h,k}^{q,n}\cdot v_{q,n}\right)\end{array}$ (5)

其中${\omega }_{h,k}^{q,n}\in \left\{0,1\right\}$ 表示任务$v_{q,n}$ 是否卸载到卫星$n_{h,k}$ 的决策。$c{t}_{h,k}\left(i\right)$ 表示在时隙$t_i$ 卫星$n_{h,k}$ 已经计算完成的数据量。在$t_{i+1}$ 时隙卫星$n_{h,k}$ 的任务队列表示为：

$\begin{array}{c}{Q}_{h,k}^F\left(i+1\right)=\max \left\{Q_{h,k}^F\left(i\right)-c{t}_{h,k}\left(i\right),0\right\}+a{t}_{h,k}\left(i\right)\end{array}$ (6)

其中$Q_{h,k}^F\left(0\right)=0$ 。在时隙$t_{i+1}$ ，卫星$n_{h,k}$ 的剩余能源表示为：

$\begin{array}{c}b{e}_{i+1}^{h,k}=\min \left(b{e}_i^{h,k}-c{e}_n^{h,k}+e_i^{h,k},b{e}_{sa}^{max}\right)\end{array}$ (7)

其中$e_i^{h,k}$ 为卫星$n_{h,k}$ 在时隙$t_i$ 收获的能量，$b{e}_{sa}^{max}$ 表示卫星最大能量存储值。

2.3. 卫星计算模型

子任务$v_{\text{q},\text{n}}$ 在卫星$n_{h,k}$ 的计算延迟表示为：

$\begin{array}{c}c{d}_{q,n}^{h,k}=\frac{c_{q,n}\cdot s{d}_{q,n}}{f_{q,n}^{h,k}}\end{array}$ (8)

其中$f_{q,n}^{h,k}$ 是卫星$n_{h,k}$ 为$v_{q,n}$ 任务分配的计算资源。将子任务$v_{q,n}$ 排队延迟表示为：

$\begin{array}{c}q{d}_{q,n}^{h,k}=t_{q,n}^s-t_{q,n}^a\end{array}$ (9)

其中$t_{q,n}^a$ 为子任务$v_{q,n}$ 到达的时间，$t_{q,n}^s$ 为子任务$v_{q,n}$ 开始执行的时间。子任务$v_{q,n}$ 在卫星$n_{h,k}$ 的计算能耗表示为：

$\begin{array}{c}c{e}_{q,n}^{h,k}={\displaystyle \sum }_{h=1}^H{\displaystyle \sum }_{k=1}^K\left[\left(1-{\phi }_{h,k}^{q,n}\right){\mu }_{mob}^{h,k}\cdot {\left(f_{q,n}^{h,k}\right)}^3\cdot c{d}_{q,n}^{h,k}+{\phi }_{h,k}^{q,n}P{t}_i^{h,k}\right]\end{array}$ (10)

其中${\mu }_{mob}^{h,k}$ 表示卫星$n_{h,k}$ 的有效能量系数，$f_{q,n}^{h,k}$ 是$n_{h,k}$ 分配给子任务$v_{q,n}$ 的计算能力。${\phi }_{h,k}^{q,n}\in \left\{0,1\right\}$ 是传输标志，当其等于0时表示在卫星$n_{h,k}$ 上为子任务$v_{q,n}$ 做计算，为1表示子任务$v_{q,n}$ 途径卫星$n_{h,k}$ 做传输，$P{t}_i^{h,k}$ 为第$t_i$ 时隙子任务经由卫星$n_{h,k}$ 时$n_{h,k}$ 的发送能量消耗，其中：

${\displaystyle \sum }_{h=1}^H{\displaystyle \sum }_{k=1}^K{\phi }_{h,k}^{q,n}=1$

3. 基于复杂依赖关系分解的任务卸载策略

如图2所示，本文利用DQN算法设计复杂依赖关系分解与任务卸载模型。该模型能够将具有复杂依赖关系的任务分解为多个子任务，并针对每个子任务进行卸载决策。具体由Env模块、Training模块和DQN Network模块三部分构成。

Figure 2. Structure diagram of the DQN algorithm integrated with GCN

图2. 融合图卷积网络的深度Q网络算法结构图

在Env模块中，任务依赖关系被建模为有向图，节点表示任务，边表示任务间的数据依赖。每个任务节点具有任务数据大小、计算需求、容忍时延等属性，而每颗卫星具有计算能力、通信带宽和能耗等约束条件。

在Training模块中，系统实时记录每次的历史状态、决策及奖励。通过随机抽样方式反复训练，持续优化卸载决策。

在DQN Network模块中，将GCN嵌入DQN Network模块，处理任务依赖并优化卸载决策。该模块由两个子网络组成，分别负责子任务的卸载区域选择及区域内最终的卫星决策和资源分配。首先，任务依赖关系建模为图结构，其中节点表示任务，边表示依赖关系。任务信息(任务描述及依赖关系)经GCN提取高阶特征，捕获上下文及全局依赖。区域状态信息(如卫星状态、通信链路)通过神经网络提取特征并生成区域表示。任务特征与区域特征融合后，输入全连接网络，生成子任务的卸载目标区域。任务接收卫星依据决策将子任务发送至目标区域控制器。控制器收到子任务请求后，通过第二子网络综合子任务需求和区域状态，生成最终决策，包括目标卫星选择及计算资源分配。

当DQN Network模块输出卸载决策后，Env模块根据策略开始执行任务，计算任务的执行时间、传输时间等，并判断任务是否成功完成，最后生成即时奖励。

3.1. 基于复杂依赖关系分析的任务分解

在Env模块中，本文采用有向无环图$G_q=\left(V_q,E_q\right)$ 表示任务之间的依赖关系，其中$V_q$ 表示任务集，$E_q$ 表示边集。为了便于描述，为具有复杂依赖关系的任务构建DAG时增加2个虚拟任务$v_{q,s}$ 和$v_{q,e}$ 。$v_{q,s}$ 表示开始任务，没有前驱任务；$v_{q,e}$ 表示结束任务，没有后继任务。这2个任务无需被卸载，即在本地执

行时所需时间为0，那么包含U个子任务的DAG任务集为$V_q=\left(v_{q,s},v_{q,1},v_{q,2}\cdots v_{q,U},v_{q,e}\right)$ 。有向边$\left(v,v^{\prime }\right)$ 表

示子任务$v$ 和$v^{\prime }$ 之间存在依赖关系，即任务$v$ 的输出是任务$v^{\prime }$ 的输入。将任务$v_{q,n}$ 建模为元组：

$\begin{array}{c}{v}_{q,n}=\left\{c_{q,n},s{d}_{q,n},{\rho }_{q,n}\right\}\end{array}$ (11)

其中$s{d}_{q,n}$ 是任务$v_{q,n}$ 的数据大小，$s{d}_{q,n}$ 遵循独立且同分布于$\left[s{d}^{\min },s{d}^{\max }\right]$ ，$c_{q,n}$ 表示计算任务$v_{q,n}$ 每bit所需的CPU周期数，遵循独立且同分布于$\left[c^{\min },c^{\max }\right]$ ，${\rho }_{q,n}$ 是表示任务的最大容忍时延。

Figure 3. Example diagram of parallelizable computational decomposition for dependent tasks

图3. 具有复杂依赖关系的任务可并行化计算分解示例图

卫星网络中，由于单个卫星在同一时刻只能处理一个任务，为提高任务执行效率，通过任务分解与并行化，将可并行的任务卸载到多个卫星节点进行处理。如图3所示，一个具有复杂依赖关系的任务通过构建DAG被分解为多个子任务(节点表示子任务，边表示依赖关系)。基于任务依赖关系，将任务分为4组，第一组为子任务A，第二组为子任务B和D；第三组为子任务C和E；第四组为子任务𝐹。各组内任务被并行分配到不同的卫星节点中执行，能够充分利用卫星的计算资源减少任务处理时延。

将具有复杂依赖关系的任务$V_q$ 分解为多个可并行计算组，表示如下：

$\begin{array}{c}\begin{array}{c}{\varrho }_q=\left\{G_{q,1},G_{q,2},\cdots ,G_{q,z},\cdots ,G_{q,Z}\right\},\end{array}\\ G_{q,z}\in V_q\end{array}$ (12)

其中$G_z$ 表示第$z$ 个可并行计算组，并且$Z\le U$ 。

$\begin{array}{c}t{d}_{q,z}=\underset{v_{q,n}\in G_{q,z}}{\max }\left(t{d}_{q,n}\right)\end{array}$ (13)

$\begin{array}{c}g{d}_{q,z}=\underset{v_{q,n}\in G_{q,z}}{\max }\left(c{d}_{q,n}^{h,k}+q{d}_{q,n}^{h,k}\right)\end{array}$ (14)

其中$g{d}_{q,z}$ 为具有复杂依赖关系的任务$V_q$ 中第$z$ 个并行计算组的计算时延，$t{d}_{q,z}$ 为跨并行计算组之间的传输时延。

3.2. 任务卸载优化模型

在DQN Network模块中，将$Pred\left(G_{q,z}\right)$ 表示为并行计算组$G_{q,z}$ 的直接前驱集合，并行计算组$G_{q,z}$ 可能由多个前驱组成，那么$G_{q,z}$ 接收到的所有前驱任务后的前驱完成时延为：

$\begin{array}{c}p{d}_{q,z}=\underset{G_{q,z}\in Pred\left(G_{q,z}\right)}{\max }\left(t{d}_{q,z}+g{d}_{q,z}\right)\end{array}$ (15)

并行计算组$G_{q,z}$ 的开始时间为：

$\begin{array}{c}t{s}_{q,z}=\max \left(t{d}_{q,z},p{d}_{q,z}\right)\end{array}$ (16)

任务$v_{q,n}$ 的开始时间为：

$\begin{array}{c}t{s}_{q,n}=t{s}_{q,z}+q{d}_{q,n}^{h,k}\end{array}$ (17)

此外，定义$Succ\left(v_{q,n}\right)$ 为子任务$v_{q,n}$ 的直接后继集合。通过以上分析，一个具有复杂依赖关系任务的总完成时间可表示为：

$\begin{array}{c}T\left(V_q\right)=t{d}_q^{\left(r),(h,k\right)}+p{d}_{q,Z}+g{d}_{q,Z}\end{array}$ (18)

基于上述系统模型制定的优化问题，旨在针对具有复杂依赖关系的任务优化其任务执行时延。针对该计算架构联合优化其任务卸载策略，优化问题表述为：

$\begin{array}{c}\left(\text{P}1\right):\underset{x\left(q\right),f\left(q\right),}{\min }{\displaystyle \sum }_{q=1}^{Q}T\left(V_q\right)\end{array}$ (19)

$\begin{array}{c}0\le f_{q,n}^{h,k}\le f_{h,k}^{\max },\forall q,n,h,k\end{array}$ (19a)

$\begin{array}{c}t{d}_{q,z}\le \underset{v_{q,n}\in G_{q,z}}{\max }\left({\rho }_{q,n}\right),\forall q,z,w,n\end{array}$ (19b)

$\begin{array}{c}{\omega }_{h,k}^{q,n}\in \left\{0,1\right\}\end{array}$ (19c)

$\begin{array}{c}{\displaystyle \sum }_{h=1}^H{\displaystyle \sum }_{k=1}^K{\omega }_{h,k}^{q,n}=1\end{array}$ (19d)

其中$x\left(q\right)=\left[x_1\left(q\right),x_2\left(q\right)\cdots x_U\left(q\right)\right]$ ，为任务$V_q$ 中子任务产生的卸载决策，$f\left(q\right)=\left[f_1\left(q\right),f_2\left(q\right)\cdots f_U\left(q\right)\right]$ ，

为任务$V_q$ 中子任务分配的计算能力。式(19a)确保计算资源不会超过最大计算能力，式(19b)确保并行计算任务组的最大容忍时延不超过组内任务最大容忍时延，式(19c)确保任务被卸载至低轨卫星上，式(19d)确保每个子任务只能被卸载至一颗配备MEC服务器的低轨卫星上。

P1是一个非线性优化问题，传统方法难以求解。为此，本文将卫星网络中的任务卸载建模为最优马尔可夫决策过程，以最小化系统平均任务处理时延为目标。针对任务的复杂依赖关系，提出基于DQN算法的任务卸载策略，优化多卫星网络中的任务处理时延。在资源受限条件下，该方法有效提升计算资源利用效率，减少任务处理时延，并适应动态环境变化。

3.3. 基于强化学习的任务卸载策略求解

在本文求解模型中，构建了一个基于马尔可夫决策过程(Markov Decision Process, MDP)的具有复杂依赖关系的任务卸载策略，MDP定义如下：

1) 状态空间：针对具有复杂依赖关系的任务卸载请求，定义状态空间为$S_i=\left\{G_q,Are{a}_i\right\}$ ，其中$G_q=\left\{V_q,E_q\right\}$ ，$V_q$ 表示任务集，$v_{q,n}\in V_q$ 表示子任务信息，$E_q$ 以邻接矩阵的方式表示各子任务之间的依赖关系，$Are{a}_i=\left\{Avg\left(Q_h^F\left(i+1\right),Avg\left(b{e}_i^h\right)\right)|h\in \left\{1,2\cdots H\right\}\right\}$ ，其中$Avg()$ 表示对某一区域所有卫星状态信息取平均。此外，针对子任务域内的卸载请求，本研究还定义状态空间$Sub{S}_{i,h}=\left\{v_{q,n},SubAre{a}_i\right\}$ ，其中$SubAre{a}_{i,h}=\left\{Q_{h,k}^F\left(i\right),b{e}_i^{h,k}|k\in \left\{1,2\cdots K\right\}\right\}$ 。

2) 动作空间：针对具有复杂依赖关系的任务卸载请求，定义动作空间为$A_i=\left\{{\omega }_h^{q,n}|h\in \left\{1,2\cdots H\right\}\right\}$ ，其中${\omega }_h^{q,n}$ 为子任务卸载目标区域$S{N}_h$ 。针对子任务卸载请求，定义动作空间为$Sub{A}_{i,h}=\left\{x\left(q\right),f\left(q\right)\right\}$ ，其中$x\left(q\right)$ 为域内卸载决策${\omega }_{h,k}^{q,n}$ ，$f\left(q\right)$ 为$V_q$ 分配的计算资源。

3) 奖励函数：奖励函数用于量化每个动作对目标优化的贡献。在本问题中，奖励函数为延迟惩罚。定义奖励函数为：

$\begin{array}{c}{R}_i=-De{l}_q\end{array}$ (20)

其中$De{l}_q$ 表示处理任务$V_q$ 的计算时延。

本文算法目标是通过最小化时间差分误差来更新Q网络的参数，使其能够更准确地预测不同状态–动作对的期望回报。通过引入目标网络，用于计算Q值的目标。目标值的计算公式为：

$\gamma =R+\gamma \underset{a\text{'}}{\max }{Q}_{target}\left(S^{\prime },A^{\prime };{\theta }^{-}\right)$

其中$R$ 是即时奖励，$\gamma$ 是折扣因子，$Q_{target}\left(S^{\prime },A^{\prime };{\theta }^{-}\right)$ 是目标网络预测下一状态的最大Q值。DQN通过最小化均方误差来优化主网络参数：

$L\left(\theta \right)=E_{\left(S,A,R,S^{\prime }\right)~D}\left[\gamma -Q{\left(S^{\prime },A^{\prime };\theta \right)}^2\right]$

其中$\gamma$ 是上述目标值，$\text{Q}\left(S^{\prime },A^{\prime };\theta \right)$ 是主网络输出的Q值。通过反向传播算法计算梯度，并使用优化器(如Adam或RMSprop)更新主网络的参数：

$\theta \leftarrow \theta -\alpha {\nabla }_{\theta }L\left(\theta \right)$

其中$\alpha \in \left(0,1\right)$ 为更新系数。此外，使用$ϵ$ -贪婪策略($ϵ$ -greedy policy)来平衡探索与利用。

3.4. 算法复杂度分析

本文所提基于DQN算法的卸载策略时间复杂度涵盖多层面：环境交互中，单任务执行与奖励生成复杂度均为$O\left(1\right)$ ，若单次训练包含N个任务交互，总复杂度为$O\left(N\right)$ ；DQN Network模块中，GCN特征提取的图构建复杂度为$O\left(V+E\right)$ ，其中V为节点数，E为边数，L层GCN总复杂度为$O\left(L\cdot E\cdot F_{in}\cdot F_{out}\right)$ ，$F_{in}/F_{out}$ 为输入和输出特征维度；第一子网络(卸载区域选择)全连接计算复杂度为$O\left(D\cdot H\cdot M\right)$ ，其中特征融合后维度为D，全连接层隐藏层神经元数为H，候选区域数为M；第二子网络(卫星决策与资源分配)为$O\left(S\cdot H^{\prime }\cdot A\right)$ ，其中输入特征维度为S，隐藏层神经元数为$H^{\prime }$ ，动作空间维度为A；Training模块中，经验池单次抽样复杂度为$O\left(B\right)$ ，若训练迭代T次、每次抽样B样本，总复杂度为$O\left(T\cdot B\right)$ 。算法最坏时间复杂度为$O\left(N+L\cdot E\cdot F_{in}\cdot F_{out}+D\cdot H\cdot M+S\cdot H^{\prime }\cdot A+T\cdot B\right)$ ，其通过GCN分解任务依赖关系、线性层网络决策有效控制复杂度，在保证卸载决策精度的同时，满足任务卸载的实时性需求。

4. 实验模拟与分析

4.1. 参数设置

在本文中，使用仿真实验来评估所提出算法的性能，实验数据来自STK软件。在仿真中，LEO卫星星座由36颗卫星组成，轨道倾角为55˚，高度为550公里，每个区域卫星规模为2 × 2。任务$V_q$ 的节

点数为10，依赖边数为10，星地链路带宽为80 Mhz，$s{d}_{q,n}$ 任务大小随机分布在$\left[s{d}^{\min },s{d}^{\max }\right]$ ，$c_{q,n}$ 独立且同分布于$\left[c^{\min },c^{\max }\right]$ ，详细参数如表1所示。

Table 1. Experimental parameters

表1. 实验参数

4.2. 仿真结果

本文分两部分来说明所提出策略的仿真效果。首先，评估所提方法的收敛性。其次，将所提出的策略与卸载策略性能进行比较，依次比较不同条件下的平均任务处理时延，展示所提策略的优越性。

1) 收敛性能

图4展示两个子网络的训练损失随回合数的变化，其中(a)为第一个子网络，(b)为第二个子网络。整体来看，两个子网络的损失初始较高，随后迅速下降并趋于稳定，表明模型实现有效策略学习。第一个子网络初始损失较大，前几千回合波动明显，但下降较快，约2000回合后趋于稳定，说明其能快速适应任务与区域特征的依赖关系，优化子任务卸载区域决策。第二个子网络同样快速收敛，波动更小，约2000回合后稳定，表明其能有效完成资源分配及最终卸载目标选择。

(a) (b)

Figure 4. Algorithm training loss diagram: (a) Training loss of network 1; (b) Training loss of network 2

图4. 算法训练损失图：(a) 网络1训练损失图；(b) 网络2训练损失图

Figure 5. Reward variation with training

图5. 随训练变化的奖励趋势图

图5展示奖励值随训练回合数的变化趋势。可以看出初期奖励值较低且波动较大，因为模型尚未建立有效决策机制。约2000回合后，奖励值显著提升，表明子网络逐步学习到有效策略。随后，尽管奖励值仍有波动，但总体保持较高水平，反映模型已基本收敛，能稳定生成卸载决策。

图6展示任务完成率的变化趋势。任务完成率基于任务的实际执行情况统计，当子任务失败时，整个任务记录为失败并停止计算。可以看出初期任务完成率较低，表明系统资源分配未优化，策略尚未收敛。随着训练的推进，策略逐渐优化子任务卸载策略，任务完成率快速提升并保持高水平，表明系统能高效完成任务，并具有较强的适应能力和鲁棒性。

图7展示任务执行时延的变化趋势。可以看出初期任务执行时延较低，因子任务计算失败未进入完整执行流程。随着任务完成率提升，更多任务被成功执行，时延上升。当任务完成率稳定后，时延在1.95秒至2.1秒之间波动并稳定。这表明尽管网络环境和计算负载动态变化，该策略能够适应并维持较低处理延迟。

Figure 6. Task completion rate variation

图6. 任务完成率变化趋势

Figure 7. Task processing latency variation

图7. 任务处理时延变化趋势图

Figure 8. The influence of satellite area scale variation on task processing delay

图8. 卫星区域规模变动对任务处理时延的影响

图8展示了卫星区域规模对任务处理时延的影响。初始时各曲线波动大，而后处理时延逐渐稳定，表明策略可适配不同网络规模。具体来说，小规模区域计算资源有限，初期任务卸载困难，导致时延波动剧烈，经后续学习训练得以稳定。大规模区域资源丰富，却因拓扑复杂、卸载决策多导致初期卸载任务策略低效，而后凭借不断学习实现稳定收敛。由此可见，区域规模的设置需要根据实际应用综合考虑以达最优任务处理效果。

2) 策略性能对比

为了验证所提策略的优越性和可靠性，本文将其与以下任务卸载策略进行比较：

• DQN-SCCO策略：该策略[13]利用深度Q网络来实现最优卸载策略，为低轨卫星网络中的任务卸载提供有效解法。

• DDRATO策略：该策略[14]通过融合策略网络(Actor)和价值网络(Critic)实现对任务卸载策略的优化。

• Rand随机策略：在此策略中，卸载决策以随机的概率制定动作输出。

图9图展示了在依赖边数量固定为10的情况下，四种策略在不同节点数量(即子任务数量)下的任务执行时延对比。对于具有复杂依赖关系的任务，节点数量的增加意味着任务被分解成了更多的子任务需要处理。然而，由于依赖边数量的固定，任务之间的依赖关系并未增加，这允许更多的子任务能够被并行计算。因此，尽管节点数量增加，但是总任务执行时延的增长并不显著。这表明在这种特定条件下，任务的并行性被有效利用，从而在一定程度上抵消了节点数量增加带来的潜在时延增加。

图10对比了不同依赖边数量下各策略的任务处理时延。结果显示，随着依赖边数量增加，所有策略的时延均上升，但性能差异明显。本文所提策略表现最佳，时延最低且增长幅度最小，表明融合GCN的DQN算法能有效捕获任务依赖，提升任务卸载效率。DQN-SCCO并未融合GCN，所表现出时延显著增加。DDRATO性能略逊于DQN-SCCO，可能因其在复杂环境下对任务特性和资源分配的适应性不足。Random策略时延最高，且随依赖边数量增加增长最快，难以适应任务依赖的复杂性。

Figure 9. Comparison of task processing delays of different strategies under different numbers of sub-tasks when the number of dependency edges is fixed at 10

图9. 依赖边数量固定为10的情况下，不同策略在不同子任务数量下的任务处理时延对比

Figure 10. Comparison of task processing delays of different strategies under different numbers of sub-tasks with different numbers of dependency edges

图10. 不同依赖边数量下，不同策略在不同子任务数量下的任务处理时延对比

5. 总结

本文提出一种基于低轨卫星网络的具有复杂依赖关系的任务卸载策略，设计基于DQN的深度强化学习算法，帮助控制器节点在动态条件下实时优化具有复杂依赖关系的任务卸载决策。仿真实验分析表明所提策略能显著降低任务处理时延，展现优越的适应性与鲁棒性。

基金项目

国家自然科学基金资助项目(61602305, 61802257)；上海市自然科学基金资助项目(18ZR1426000, 19ZR1477600)。

NOTES

^*通讯作者。

参考文献