文献阅读笔记 # SpaceAerial-Assisted Computing Offloading for IoT Applications: A Learning-Based Approach

这次分享的是一篇 2019 年发表在《IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS》的文章 SCI 1区，通信 Top 期刊，IF=9.144

首次提出了 SAGIN 物-边-云/空-天-地 计算架构

Space/Aerial-Assisted Computing Offloading for IoT Applications: A Learning-Based Approach Abstract

物联网的计算卸载是一个挑战性问题（尤其是在边缘或云基础设施不可用的偏远地区）。本文提出一种空天地一体化网络边缘/云计算体系结构( space-air-ground integrated network ,SAGIN edge/cloud computing architecture)用于卸载计算密集型应用。
考虑到偏远地区的能源和计算约束，飞行的无人机提供接近用户的边缘计算，卫星提供云计算的接入。首先，对于无人机边缘服务器，我们提出了一种联合资源分配和任务调度方法，以有效地将计算资源分配给虚拟机（VM）并调度卸载的任务。其次，我们研究了 SAGIN 中的计算卸载问题，并提出了一种基于学习的方法来从动态 SAGIN 环境中学习最佳卸载策略。将卸载决策问题看作一个马尔可夫决策过程，采用 actor-critic 方法对问题求解。
仿真结果表明所提出的边缘虚拟机分配和任务调度方法可以以低复杂度实现接近最优的性能，与其他卸载方法相比，所提出的基于学习的计算卸载算法不仅收敛速度快，而且总成本更低。

Introduction

• 5G背景：高数据传输率、低延迟、高可靠性、大规模连接；缺点：大规模计算能力(massive computing capabilities)、在 5G 无线系统中，将部署超密集网络边缘设备：例如宏/小型蜂窝基站和 WiFi 接入点，这些设备可以提供呈指数级增长的边缘计算资源（但尚未得到充分利用）。
  eg. virtual reality and HD video streaming require a large amount of computing resources for rendering and video encoding/decoding, and the autonomous vehicles rely on computing for artificial intelligence (AI)-based steering control. 这些计算密集型应用对资源受限的终端设备(如物联网设备的电池和计算)提出了巨大挑战，这也促进了云计算——将计算密集型应用卸载到具有集中和丰富计算资源的云服务器上。虽然云计算可以显着降低用户的计算延迟和能耗，但由于终端用户与云服务器之间的传输距离较远，因此可能无法满足对延迟敏感的应用的需求。因此采用移动边缘计算（MEC）利用网络边缘的计算资源来提供高效和灵活的计算服务。
  MEC 中的许多重要问题已被广泛研究，包括卸载任务模型 [3]、[4]、能源效率 [5]-[7]、延迟减少 [8]-[10]，以及通信和计算的联合优化 [ 11]，[12]…

【本文场景】

• 郊区和农村地区不会部署大量5G基站但可能会部署大量IoT设备，并在这些地区执行某些计算要求相对较高的应用程序。 例如，传感信息的融合，特别是对高清声音或视频信息的处理，会很快耗尽 sink 节点的电池，并导致较大的处理延迟。
  【阅读疑问：因为智能农业、智能工厂或者车联网？或者山区的电网、边境的物联网检测设备？】
• 由于缺乏地面接入网络覆盖，典型的边缘和云计算范式无法应用于此类场景。 为此采用空天地一体化网络（SAGIN）架构来进行物联网应用的计算卸载。 SAGIN 将卫星网络、空中网络与地面网络相结合，为大区域提供无缝、灵活的网络覆盖和服务，可应用于智能交通系统、远程区域监控、灾害救援、大规模高速移动互联网接入[13]。SAGIN是一个多维异构网络(multidimensional heterogeneous network)，由卫星网络、空中网络和地面网络三个网段组成。 每个网段拥有不同的资源，受到不同的限制。
  • 低地球轨道（LEO）和地球静止（GEO）卫星构成了一个分层网络，其中LEO卫星提供高速接入，GEO卫星在LEO之间中继数据以进行长距离传输[14]。
  • 空中网络包括飞行无人机（UAV）、高纬度平台（HAP）和通信气球，可以按需部署在数据流量突发的地点，提供高速和动态的网络服务，如动态覆盖、 边缘计算、人群感知等[15]、[16]。 空中网络节点可以作为飞行边缘服务器，为物联网设备提供低延迟的边缘计算。
  • 卫星通信具有较低的通信速率和较高的传输延迟，但可以通过无缝覆盖和卫星骨干网络提供永远在线的云计算[17]。

然而，在物联网计算卸载中使用 SAGIN 引入了几个具有挑战性的问题。

• 首先，空中网络的高移动性导致动态的信道条件和覆盖范围(dynamic channel conditions and coverage)，导致服务器可用性和通信延迟的变化，应谨慎处理以保证 SAG-IoT 系统的性能。
• 其次，SAGIN中的不同网段具有不同的网络条件和资源约束。

本文提出了一个灵活的联合通信和计算的 SAGIN 框架，为远程物联网用户提供强大的边缘/云计算服务。在该框架下，提出了一种高效的计算卸载方法，该方法在考虑多维网络的动态性和资源约束的情况下，学习最小化延迟、能耗和服务器使用成本的加权和的最优卸载策略。

• 首先，无人机边缘服务器的计算资源虚拟为 VM，用于并行执行任务。本文把Joint VM 资源分配和任务调度问题表述为一个混合整数规划问题，并提出了一种有效的启发式算法。
• 其次 SAGIN 中的计算卸载问题被表述为马尔可夫决策过程 (MDP)。基于 actor-critic 学习算法来处理大型状态和动作空间。

据我们所知，本文是第一个研究 SAGIN 中计算卸载问题的工作，验证了 SAGIN 支持远程物联网用户计算密集型应用的可行性，并可以为 SAGIN 网络设计和远程计算卸载提供有用的指导。

主要贡献：

• 把 SAG-IoT computing offloading problem 定义为 MDP。提出一种 RL 方法解决问题。The system state is defined to integrate the historical network information to learn the system dynamics. In addition, a policy gradient based actor-critic learning algorithm is proposed to cope with problem of dimensionality curse and accelerate the learning speed.
• 采用 network virtulization 来灵活分配边缘服务器资源。把 joint edge server VM computation resource allocation and task scheduling 问题形式化为 mix-integer 规划问题并提出高效的启发式算法解决问题。

2 Related Work 2.A Mobile Edge Computing

• In edge computing,the computation task offloading mechanism determines the overall performance of the MEC system.
• In MEC system, the energy consumption and task delay rely not only on the task processing, but also on the communication of the related data of the task.

前述工作只关注固定的 MEC 场景，即边缘计算服务由蜂窝基站(cellular BSes)或 WiFi AP 提供，本文将无人机作为移动边缘服务器。本文考虑了能耗、任务处理延迟，UAV轨迹是通过学习而不是根据场景设计。

2.B Space-Air-Ground Integrated Network

3 System Model

3.A Network Model

考虑在偏远区域部署物联网设备执行某些具有计算要求的任务，例如监控和视频监控。在考虑的偏远地区没有蜂窝覆盖，因此考虑使用 SAGIN 为物联网设备提供网络功能，例如网络访问、边缘计算和缓存。
在 SAG-IoT 网络中，共有三个网段，即地面段、空中段和空间段。物联网设备构成地面部分，能源和计算能力有限。物联网设备上运行的应用程序可能会上传的数据和计算任务。在空中部分，飞行无人机可以作为边缘服务器，为地面用户提供边缘缓存和计算能力(Facebook Aquila 等飞行无人机可以通过使用太阳能电池板在不充电的情况下飞行数月)。无人机配置有固定的飞行轨迹，以服务于所考虑的区域。 在太空部分，一颗或多颗 LEO 卫星提供覆盖并通过卫星骨干网连接物联网设备与云服务器。

• IoT device（user） i i i 具有 C l C^l Cl 的本地计算能力(local computing capability)(本文假设所有IoT Device都相同)。
• 本地计算能耗： E l E^l El，与 C l C^l Cl有关。本地传输到 UAV 和 卫星的功耗分别定义为 E i e E_i^e Eie​ and E i c E_i^c Eic​ 。
• 边缘服务器 UAV 的计算资源被虚拟为 VMs (each for one specific application)。在 edge server k k k, 总计算资源(total computation resource)是 C e C^e Ce。分配给 VM v v v的计算资源是 C v e C^e_v Cve​。用户 i i i的任务 j j j的server usage cost of VM： B i , j e B^e_{i,j} Bi,je​。
• 对于无人机-地面通信，由于我们考虑的任务卸载决策，其时间尺度比传统资源调度时间（1 ms）长得多，因此只考虑大规模信道衰落。此外，由于不需要瞬时(instantaneous)信道信息，卫星控制的全局决策是可行的。 根据[25]，无人机与地面用户之间的路径损耗如下：
  
  其中 h 和 r 分别表示无人机飞行高度和无人机与地面用户之间的水平距离。 η L o S \eta_{LoS} ηLoS​ 和 η N L o S \eta_{NLoS} ηNLoS​ 分别表示在 LoS 和 NLoS 链路的自由空间路径损耗之上产生的附加损耗。 f c f_c fc​表示载波频率，c表示光速。
  PLoS 是无人机-地面链路的视距概率(line-of-sight probability)，可以通过下式计算:
  
  ( a , b , η L o S , η N L o S ) (a, b, \eta_{LoS}, \eta_{NLoS}) (a,b,ηLoS​,ηNLoS​) 环境相关变量。 例如，在偏远地区，它们的值为 (4.88, 0.43, 0.1, 21)。

无人机与地面通信使用总带宽为 B 的 WiFi 协议。如果 n 个 IoT 设备同时与一架无人机通信，则每个 IoT 设备获得的带宽由下式计算：

ρ是WiFi吞吐量效率(throughput efficiency)因子，ξ(n)是WiFi信道利用率函数（WiFi channel utilization function)，是关于服务用户数n的递减函数。
瞬时无人机-地面和地面-无人机数据速率可以计算为：

E i e − E_i^{e-} Eie−​: UAV对地面IoT的发射功率
L i L_i Li​: 对应物联网用户-无人机链路的路径损耗
σ 2 \sigma^2 σ2 高斯噪声的功率

星地通讯：恒定通信速率 r S G r_{SG} rSG​，通常小于无人机-地面通讯速率。卫星通过卫星骨干网连接到互联网/云。卫星和云之间的传输速率： r S C r_{SC} rSC​。云计算能力远高于物联网设备和边缘服务器，每个任务的处理速度为 C c C^c Cc。用户 i i i的任务 j j j的server usage cost: B i , j c B^c_{i,j} Bi,jc​

3.B Multi-User Multi-Task SAG-IoT Computing Offloading

本文假设有 M 个物联网用户和 N 个不同的计算应用程序，每个用户都在运行所有 N 个应用程序，导致系统中有 M × N 个计算任务。我们还考虑到 N 个应用程序具有一定的优先级，即如果同时调度多个任务，则应用程序编号较小的任务将比应用程序编号较大的任务更早地传输/处理。对于第 j 个应用程序，输入数据 H j i n H_j^{in} Hjin​、输出数据 H j o u t H_j^{out} Hjout​和工作量(workload) Z j Z_j Zj​。

这些任务可以在 IoT 设备上本地执行，但由于物联网设备的能量和计算能力有限，计算任务也可以卸载到无人机边缘服务器，或者通过卫星进一步卸载到云端。在每个时隙都会做出卸载决策，直到完成所有 M × N 个任务。The offloading decision is made in each time slot until all the M × N tasks are completed. 在时隙 t 的开始，剩余的任务用 M × N 矩阵 M ⃗ ( t ) \vec{M}(t) M (t) 表示， m i , j ( t ) = 1 m_{i,j}(t) = 1 mi,j​(t)=1表示 Task W i j W_{ij} Wij​未完成。在t时刻本地计算任务: X l ⃗ ( t ) \vec{X_l}(t) Xl​ ​(t)、卸载到边缘(uav)计算任务： X e ( t ) ⃗ \vec{X_e(t)} Xe​(t) ​、卸载到云端计算: X c ( t ) ⃗ \vec{X_c(t)} Xc​(t) ​。对应为1的变量表示在这一层计算。任务 W i j W_{ij} Wij​ 在时间 t 最多以一种形式调度，即卸载决策受限于：

没有在时隙 t 调度未完成的任务时，(7) 中的不等式成立。如果任务 W i j W_{ij} Wij​ 在本地处理或在时间 t 卸载到云端，我们认为任务可以有一定的延迟完成 m i , j ( t + 1 ) = 0 m_{i,j}(t+ 1) = 0 mi,j​(t+1)=0。被卸载到无人机边缘服务器的 W i j W_{ij} Wij​ 可能在t结束时没有完成并成功返回给用户i，两个可能原因是：1) 如果将多个任务卸载到一台无人机边缘服务器上，其中一些任务可能无法在时隙内完成；2) 由于无人机在移动，当任务 W i j W_{ij} Wij​ 在边缘服务器完成时，如果用户 i i i不在无人机的覆盖范围内，则无法将结果传回。

3.C Cost Model

计算任务卸载是为了最小化执行 M × N 个任务的系统成本。 在所考虑的 SAG-IoT 系统中，系统成本由两部分组成，即 延迟成本(Delay Cost) 和 能源和服务器使用成本(Energy and Server Usage Cost)。
(1) Delay Cost: 如果任务 W i j W_{ij} Wij​ 在时隙 t 被调度，则可以根据卸载决策计算延迟。 如果任务在本地调度，则延迟为：

其中 ε 是时隙的长度，ε(t-1) 是自任务生成以来经过的时间。由于物联网设备的计算能力较低，很可能在时隙 t 开始时有一些任务被安排在本地处理但尚未完成。 t i , j l t^l_{i,j} ti,jl​是用户 i 完成剩余本地处理任务的时间，可用剩余本地工作量除以本地处理能力 C l C^l Cl计算得出。

如果任务被卸载到无人机边缘服务器，并且在时隙 t 内返回结果给用户 i，则任务的总延迟可以计算为:

d i , j e d^e_{i,j} di,je​ 表示 UAV 边缘服务器中 W i j W_{ij} Wij​ 的处理延迟，这取决于第四节中提到的卸载决策和 VM 资源分配。 如果用户 i 的多个任务被边缘服务器调度，考虑根据优先级传输任务，计算将 W i j W_{ij} Wij​ 任务数据传输到服务器的时间: ∑ a = 1 j x i a e ( t ) H a i n \sum_{a=1}^j x^e_{ia}(t)H_a^{in} ∑a=1j​xiae​(t)Hain​。类似地，如果任务通过卫星卸载到云端，则延迟计算为：

(2) Energy and Server Usage Cost: 本地处理 W i j W_{ij} Wij​ 的能源成本可以计算为

如果在时隙 t，任务 W i j W_{ij} Wij​ 被卸载到无人机边缘服务器并且结果成功传输给用户 i，则能量和服务器使用成本可以计算为：

α 表示无人机服务器使用成本相对于物联网用户能耗的权重。考虑之前将任务卸载到 UAV 边缘服务器的时间未能在调度时隙内返回的情况的计算总能耗： ∑ a = 1 v x i j e ( t ) H j i n r G U ( t ) \sum_{a=1}^v x^e_{ij}(t)\frac{H_j^{in}}{r_{GU}(t)} ∑a=1v​xije​(t)rGU​(t)Hjin​​。
同样，如果将任务 W i j W_{ij} Wij​ 卸载到云端，则能源和服务器使用成本可以计算为：

β 表示云服务器使用成本相对于物联网用户能耗的权重。

4 COMPUTATION VM ALLOCATION

在时隙 t 中，可以将多个任务卸载到一个 UAV 边缘服务器。 在这种情况下，这些任务在不同的 VM 中并行执行，以减少处理延迟。 每个 VM 执行特定应用程序的任务。 本文研究了一个虚拟机分配(VM allocation)问题，在考虑任务卸载到边缘服务器的情况下将边缘服务器的计算资源分配给不同的虚拟机。考虑到 UAV 的移动，一些用户可能会丢失与 UAV 的链接。因此执行此类任务可能会导致分配给相应 VM 的资源过多。

例如，在图 2 中，考虑两个 VM 在 UAV 边缘服务器执行卸载的任务， t i , j t_{i,j} ti,j​ 是 VM i 中任务 j 的延迟(delay)要求。我们可以看到时延约束 t 2 , 1 t_{2,1} t2,1​ 非常严格，需要为 VM2 分配更多的计算资源才能在 deadline 之前完成相应的任务。 但由于边缘服务器的总计算资源是固定的，很可能分配给 VM1 的资源很少，VM1 中的三个任务都不能及时完成。 因此，我们共同优化无人机边缘服务器中的 VM 分配和任务调度，以减少系统总延迟。

在所考虑的问题中，有多种应用程序（Apps），记为 A = {1, . . . , N}，以及一个计算能力为 C cycles/s 的无人机边缘服务器。对于第 m 个 App，可能有多个卸载任务，记为 T m = { 1 , . . . , N m } T_m = \{1, . . . , N_m\} Tm​={1,...,Nm​}，计算工作量相同，但最大延迟要求不同。 Z m Z_m Zm​ 代表第 m 个 App 任务的计算工作量。 C = { c m ∣ m ∈ A } C = \{c_m | m ∈ A\} C={cm​∣m∈A} 代表计算资源变量。 c m c_m cm​ 是分配给执行 App m 的 VM 的计算资源。 Y = { y m , n ∣ m ∈ A , n ∈ T m } Y = \{y_{m,n} | m ∈ A, n ∈ T_m\} Y={ym,n​∣m∈A,n∈Tm​} 代表任务执行的决策变量， y m , n = 1 y_{m,n}=1 ym,n​=1 代表 App m 的 Task n 被调度和执行。
sum delay minimization problem 形式化如下：

t m , n t_{m,n} tm,n​ 是 App m 的任务 n 的时延约束， ε 是时隙长度。

t l c t_{lc} tlc​ 是卸载此任务的用户与无人机失去连接的时间。C1 约束每个任务在当前时隙执行时的最大延迟。 C2 限制 VM 的总计算资源不能超过 C。

可以看出(14)是一个难求解的混合整数规划问题。它涉及到连续变量 C 和 0-1 整数变量 Y。即使我们假设 C 是已知的，剩余子问题仍然是具有 0-1 整数约束的二次问题，这是具有非定矩阵(non-definite matrix)的 NP-hard 问题 [28]、[29]。这个问题通常通过特定的松弛方法(specific relaxation approach)重新表述，然后通过强大的凸优化技术(convex optimization techniques)来解决。 然而这种方法执行了大量的迭代，并对调度策略所知不多。 因此，我们有动力设计一种有效的低复杂度算法来获得次优解决方案。

在所提出的 VM 分配和任务调度算法中，我们假设对于每个 VM m， N m N_m Nm​ 个任务的时延约束进行了排序， t m , n ≤ t m , n + 1 t_{m,n} ≤ t_{m,n+1} tm,n​≤tm,n+1​。首先我们尝试分配 c m c_m cm​，假设所有任务都被调度，即 y m , n = 1 , ∀ m ∈ A , ∀ n ∈ T m y_{m,n} = 1, ∀m ∈ A, ∀n ∈ T_m ym,n​=1,∀m∈A,∀n∈Tm​。 分配结果将是:

给定分配结果，如果 ∑ m = 1 M c m > C \sum_{m=1}^M c_m > C ∑m=1M​cm​>C。这意味着并非所有任务都可以调度。 因此，我们选择不调度时延约束最苛刻的任务，即：

然后再次计算 VM 分配 c m c_m cm​。重复这个过程直到 ∑ m = 1 M c m < = C \sum_{m=1}^M c_m <= C ∑m=1M​cm​<=C并得到 VM 分配 C m C_m Cm​和任务调度 Y Y Y。对于通用 Y，VM 分配由下式计算：

未调度任务的选择由下式计算:

边缘服务器 VM 分配和任务调度的完整算法如算法 1 所示。从算法中我们可以看出，最坏的情况（云无法及时完成任何卸载的任务）需要 N (N + 1)/2 次比较，其中 N 是卸载到无人机边缘服务器的总任务数。即使是最坏情况的复杂度 O ( N 2 ) O(N^2) O(N2) 也非常低，因此所提出的算法可以在动态 SAGIN 环境中有效地工作。

5 COMPUTATION OFFLOADING PROBLEM FORMULATION

我们为 SAG-IoT 系统设计了一种在线计算卸载方法，其中在每个时间段，物联网设备的计算任务被安排在本地处理，卸载到无人机边缘服务器，或者通过卫星卸载到云服务器，最终目的是为了在任务延迟、IoT用户能耗和边云服务开销等方面最小化系统总成本。这可以通过将计算卸载决策建模为 MDP 来实现。

SAG-IoT 计算卸载问题的 MDP 定义如下：
(1) States: 在时隙t开始，网络状态定义为: M ( t ) ⊗ T r ( t ) ⊗ P L ( t ) ⊗ P L ( t − 1 ) ⊗ P L ( t − 2 ) ⊗ ⋅ ⋅ ⋅ ⊗ P L ( t − t q ) M(t)⊗Tr(t)⊗PL(t)⊗PL(t−1)⊗PL(t−2)⊗· · ·⊗PL(t−tq) M(t)⊗Tr(t)⊗PL(t)⊗PL(t−1)⊗PL(t−2)⊗⋅⋅⋅⊗PL(t−tq)，并且 T r l ( t ) = { t 1 l ( t ) , t 2 l ( t ) , . . . t M l ( t ) } T^l_r(t) = \{t^l_1(t), t^l_2(t), . . . t^l_M(t)\} Trl​(t)={t1l​(t),t2l​(t),...tMl​(t)}表示每个用户本地处理完成任务所需的剩余时间。 P L ( t ) = { P L 1 ( t ) , P L 2 ( t ) , . . . , P L M ( t ) } PL(t) = \{PL_1(t), PL_2(t), . . . , PL_M(t)\} PL(t)={PL1​(t),PL2​(t),...,PLM​(t)} 是用户到对应 UAV 的路损(pathloss)向量。系统状态(state)包括当前和前 t q t_q tq​ 个时隙的路损信息，以便学习和预测路损信息。

(2) Actions: 在时隙 t 开始，系统采取调度用户任务的动作，即确定矩阵 X ⃗ l ( t ) , X ⃗ e ( t ) , X ⃗ c ( t ) \vec{X}_l(t),\vec{X}_e(t),\vec{X}_c(t) X l​(t),X e​(t),X c​(t)，即 x i j l , x i j e , x i j c x^l_{ij},x^e_{ij},x^c_{ij} xijl​,xije​,xijc​。令 a ( t ) = { X ⃗ l ( t ) , X ⃗ e ( t ) , X ⃗ c ( t ) } a(t) = \{\vec{X}_l(t), \vec{X}_e(t), \vec{X}_c(t)\} a(t)={X l​(t),X e​(t),X c​(t)}。在时隙0有 4 M N 4^{MN} 4MN 种可能的决策，当M或N很大的时候这个数会很大。

(3) Transition probability: 由于无人机-用户路损不受动作(action)影响，系统转移概率可以计算为：

具体来说，如果无人机的轨迹和飞行速度是固定的， PL(t + 1)会是特定的， p ( P L ( t + 1 ) ∣ P L ( t ) ) p(PL(t + 1)|PL(t)) p(PL(t+1)∣PL(t))为1。然而，由于无人机移动的不确定性， p ( P L ( t + 1 ) ∣ P L ( t ) ) p(PL(t + 1)|PL(t)) p(PL(t+1)∣PL(t)) 将难以建模。 T r l ( t + 1 ) T^l_r(t + 1) Trl​(t+1) 可以通过下式计算:

对于 p ( M ( t + 1 ) ∣ M ( t ) , a t ) p(M(t + 1)|M(t), a_t) p(M(t+1)∣M(t),at​)，很难准确建模。 例如，如果一个任务被卸载到无人机边缘服务器，该任务能否在时隙内完成取决于无人机数据传输速率、无人机计算资源分配、其他用户的决策和无人机的移动，这些都是动态且彼此关联。
(4) Reward: 为了最小化延迟、能量和服务器使用成本的加权和，我们使用成本函数 C ( s t , a t ) = ∑ i j C i , j ( s t , a t ) C(s_t, a_t) = \sum_{ij} C_{i,j}(s_t, a_t) C(st​,at​)=∑ij​Ci,j​(st​,at​)，其中 C i , j ( s t , a t ) C_{i,j}(s_t, a_t) Ci,j​(st​,at​) 是任务 W i j W_{ij} Wij​ 的成本函数，其计算方式如下：

将状态 s 的价值函数(value function) V 定义为从 s 开始在策略 π 下的期望长期贴现成本(expected long-term discounted cost)。

其中 γ ∈ [ 0 , 1 ] γ ∈ [0, 1] γ∈[0,1] 是一个折扣因子，并且期望从 s 开始覆盖所有可能的状态轨迹。 在线计算卸载方法是选择一个最优策略 π∗ 来最小化每个状态的价值函数。

6 RL-BASED OFFLOADING DECISION MAKING

在问题 (24) 中，由于 UAV 的移动和 UAV 边缘服务器 VM 动态分配，奖励函数和转移概率难以准确建模。 此外，随着系统规模的增加，即 M 和 N，呈指数增长的系统状态空间使系统变得难以处理。 因此，提出的在线计算卸载问题可以通过基于 model-free 的强化学习的方法来解决，例如 Q-learning [30] 和策略梯度方法 [31]。在本文中，我们提出了一种基于策略梯度方法的 SAG-IoT 系统的在线计算卸载方法。

在提出的在线计算卸载方法中，策略由向量 θ ∈ R d θ ∈ R^d θ∈Rd 参数化(parameterized by)，即 π ( a ∣ s , θ ) = P ( a t = a ∣ s t = s , θ t = θ ) π(a|s, θ) = P(a_t = a|s_t = s, θ_t = θ) π(a∣s,θ)=P(at​=a∣st​=s,θt​=θ)，在参数为 θ 的策略下，系统在时隙 t 处于状态 s 时执行动作 a。如果为状态的每个特征定义 θ，即 M ( t ) M(t) M(t)、 T r ( t ) T^r(t) Tr(t) 和 P L ( t ) PL(t) PL(t) 中的每个元素，则向量 θ 的长度为 M ( N + t q + 2 ) M(N + t_q + 2) M(N+tq​+2)。为了学习策略参数，我们首先定义 θ 的性能度量，用 J(θ) 表示。由于在线计算卸载问题是 episodic 的（当所有 MN 任务完成时，一个 episode 结束），我们将性能度量定义为 the total discounted cost of the episode of computing all tasks。用 τ 表示一个 episode 在 π(·|·, θ)策略下的状态-动作序列 s 0 , a 0 , s 1 , a 1 , . . . , s t m a x , a t m a x s_0, a_0, s_1, a_1, ...,s_{t_{max}}, a_{t_{max}} s0​,a0​,s1​,a1​,...,stmax​​,atmax​​，其中 t m a x t_{max} tmax​ 表示预设值，表示处理所有任务可能的最大时隙数。 然后我们可以将 J(θ) 作为初始状态 s 0 s_0 s0​ 的值函数：

为了学习最小化 J(θ) 的策略参数 θ，直观地说，我们可以使用梯度下降法逐步更新 θ：

φ 表示学习率。 根据策略梯度定理[32]，我们有：

q π ( s , a ) q_π(s, a) qπ​(s,a) 是策略 π 的状态-动作价值函数， G t = C t + γ C t + 1 + γ 2 C t + 2 . . G_t = C_t + γC_{t+1} + γ^2 C_{t+2} . . Gt​=Ct​+γCt+1​+γ2Ct+2​.. 是成本的贴现回报。 使用上述方法，我们可以通过以下方式更新 θ：

然而，尽管这种更新方法（称为 REINFORCE 方法 [33]）可以渐近收敛到局部最小值，但它通常会导致方差大并且学习缓慢。 在线 SAG-IoT 计算卸载中，状态空间和动作空间都很大，因此 REINFORCE 方法可能不适合。 为了进一步提高学习性能，我们因此采用了actor-critic方法，这种方法同时学习了策略和价值函数的近似[34]。 在 actor-critic 方法中，策略在每个时隙中更新，而不是在计算卸载的每个 episode 中更新。 因此，学习最优策略所需的样本数量可以显着减少，从而加速学习过程。具体来说，用 V ^ ( s t , ω ) \hat{V}(s_t, ω) V^(st​,ω) 表示状态 s t s_t st​ 的价值函数的估计，其中 ω ∈ R m ω ∈ R^m ω∈Rm 是拟合价值函数的参数向量。 然后，在每个时隙 t 中，θ 可以通过下式更新：

注意，在每个时隙中，估计值函数 V ^ \hat{V} V^ 的参数向量 ω 也根据下式更新：

其中 φ’ 是学习率，损失函数 L(ω) 定义为：

最后，在深度神经网络近似复杂函数的能力的推动下，我们采用深度学习架构来根据 θ 和估计的状态值函数(estimated state-value function)来学习策略。 算法 2 显示了针对 SAT-IoT 的完整在线计算卸载方法，其中 φ 和 φ‘ 分别是actor和critic的学习率。

所提出的基于 RL 的卸载方法的实现如图 3 所示，它由 SAGIN 环境、计算卸载 reward evaluator、an actor network, a critic network, 和 a temporal-difference component组成。 系统状态可以从当前的 SAGIN 环境中观察到，然后发送到 actor 网络和 critic 网络作为输入。Actor 网络根据 a n = π θ ( s ) a_n = π_θ(s) an​=πθ​(s) 生成动作 a，并更新策略 θ。很容易看出，在时隙 t，对于任意任务 W i j W_{ij} Wij​，决策 x i j ( t ) x_{ij}(t) xij​(t) 有四种可能性，即不调度、本地处理、卸载到边缘和卸载到云端。因此，我们将这四种可能的决策 x i j x_{ij} xij​ 映射为整数 0、1、2、3。设计actor网络的两个输出层，即σ和μ，它们可以组成M×N正态分布的随机变量来表示每个任务的动作。critic network estimates the value function V ^ ( s t , ω ) \hat{V}(s_t,ω) V^(st​,ω)，并更新参数ω。The reward of a state-action pair is evaluated by the reward evaluator, and is used to calculate the temporal-difference (TD): η = C t + γ V ^ ( s t + 1 , ω ) − V ^ ( s t , ω ) \eta = C_t + γ\hat{V}(s_{t+1}, ω) − \hat{V}(s_t, ω) η=Ct​+γV^(st+1​,ω)−V^(st​,ω)，用于更新策略参数 θ 和critic network参数 ω。

7 PERFORMANCE EVALUATION

A. Simulation Configurations
在本节中，我们评估了针对无人机边缘服务器提出的联合 VM 资源分配和任务调度方案，以及用于 SAG-IoT 系统的基于 RL 的在线计算卸载方法。 在模拟中，我们考虑一个 1 km × 1 km 的偏远区域，其中 M = 30 个物联网用户固定部署在该区域。 IoT 用户运行 N = 5 个不同的应用程序，因此每个用户有 5 个任务要处理。 我们选择基于 ARM Cortex-M 的物联网设备作为地面用户。
参考[35]和[36]，物联网设备计算能力 C l C_l Cl​设置为200 MC/s（MC = 1 0 6 10^6 106 cycles），本地任务处理的能耗为141 mW。 如 [37] 中所定义，物联网用户对无人机和卫星的发射和接收功率，即 E e E^e Ee、 E e − E^{e−} Ee− 和 E c E^c Ec 设置为 200 mW。 5 架无人机作为物联网计算的空中飞行边缘服务器。

根据 Wu 等人的工作 [38] ，这里采用实用的无人机-地面信道 公式(1)，UAV移动轨迹被规划于最大化最小吞吐量。参考[39]，边缘服务器的计算资源 C e C^e Ce 设置为 3 GC/s（GC = 1 0 9 10^9 109 cycles），而云服务器分配给每个任务的计算资源 C c C^c Cc，设置为 10 GC/s。

对于卫星和远程云，我们考虑在计算卸载的一个 episode 中，有一颗 LEO 卫星提供对该区域的全覆盖，并且星地通信速率 r S G r_{SG} rSG​ 设置为 10 Mbps，这是在高吞吐量卫星通信系统 ViaSat-1 中观测到的平均传输速率。

卫星-云传输速率也受到卫星-地面传输速率的限制，因此我们设置 r S C = r S G = 10 M b p s r_{SC} = r_{SG} =10 Mbps rSC​=rSG​=10Mbps。 Different computation tasks may have different computation to data ratios；为了模拟简单，我们选择 x264 VBR 编码的计算-数据的比率，即 1300 cycles/byte， Z = 1300 H i n Z = 1300H^{in} Z=1300Hin [40]。 H j i n H_j^{in} Hjin​ 和 H j o u t H_j^{out} Hjout​ 分别在 5 MB 和 15 MB 之间以及 1 MB 和 5 MB 之间随机选择。

我们将边缘服务器/云服务器的使用成本 B i j e B_{ij}^e Bije​ 和 B i j c B_{ij}^c Bijc​ 设置为执行任务 W i j W_{ij} Wij​ 的 CPU cycls，即 W i j W_{ij} Wij​ 的工作负载。 此外，α = 1 0 − 10 10^{−10} 10−10 J/cycle， β = 4 × 1 0 − 10 J / c y c l e β = 4 × 10^{−10} J/cycle β=4×10−10J/cycle，对于每个用户 i， ω ˉ i \bar{ω}_i ωˉi​ = 1 J/s。 详细的仿真参数如表 II 所示，除非另有说明。

B. VM Computing Resource Allocation and Task Scheduling
我们首先评估提出的 VM 计算资源分配和任务调度算法。 我们将启发式算法与“蛮力”方法和“随机”方法进行比较。 在“Brute-force”中，穷举搜索用于寻找最优的未调度任务，实现了上界性能，但计算复杂度高。 在“随机方法”中，随机选择未调度的任务。
（这里略写，只写关键结论，详细内容参考原文）

• Fig.4 (a)&(b) 显示所提出的启发式算法可以达到与暴力最优解方法非常接近的性能，证明了所提出算法的效率。
  

• Fig.5 显示了所提出的启发式算法与“蛮力”方法的运行时间比较。所提出的启发式算法当卸载任务的数量增加时，运行时间呈二次增长，这验证了我们在第四节中的分析。（暴力指数增长）
  

C. Deep RL-Based IoT Computing Offloading
在这一部分中，对所提出的基于 RL 的 SAG-IoT 计算卸载方法的性能进行了评估和比较。 为了展示我们提出的方法的效率，我们明确地将其与其他两种计算卸载方法进行比较，即“随机”和“Greedy on Edge”，如下所述。
(1) ‘随机’：每个任务随机选择一个时隙 t ∈ {1, 2, . . . , t m a x t_{max} tmax​} 和卸载决策（locally, edge, cloud）
(2) “Greedy on edge”：由于边缘计算通常可以提供较低的计算延迟和相对较低的价格，如果每个用户在无人机的覆盖范围内，都会将所有任务卸载到无人机边缘服务器。 否则，用户决定以一定的概率等待、在本地处理或卸载到云端。 在模拟中，我们将概率分别设置为 0.8、0.1 和 0.1。

图 6 显示了所提出的基于 RL 的计算卸载算法的收敛性能。 总成本由每个任务的成本之和计算得出，即延迟、能耗和服务器使用成本的加权和。 可以看出，该算法收敛得非常快，因为在大约第 10 episodes 时该算法已经收敛。 高收敛率源于采用的 actor-critic 算法，在该算法中，critic 网络判断和引导 actor 网络在每个时隙中学习策略，而不是在非 actor-critic 策略梯度方法的每episode 一次学习。 算法的快速收敛可以带来许多好处，例如部署更多用户和应用程序时可以快速重新配置，在动态环境中具有更大的灵活性等等。

图 7 显示了所提出的计算卸载方法相对于无人机服务器使用成本权重 α 的性能。 可以看出，所提出的基于 RL 的方法可以实现比其他方法最低的总成本，因为它可以通过与环境的交互来学习最佳卸载策略。 在三种方法中，“贪婪”方法的总成本最高。 这是因为“贪婪”方法迫使许多任务内容选择无人机信道和边缘服务器计算资源，这增加了完成任务的时间。 此外，由于无人机的移动性，在任务处理期间（包括上传、处理和传输结果），无人机可能飞走，导致用户失去连接。

在图 8 中，显示了成本的主要组成部分，即能耗（E + B·α（或 β））和加权延迟（ ω ˉ T \bar{ω}T ωˉT）。 可以看出，由于学习到的最优卸载策略，所提出的计算卸载方法可以实现最低的能耗和最低的延迟。 ‘Random’ 方法实现与基于 RL 的方案相似的总延迟的原因是，在基于 RL 的方案中，将任务传输到卫星时消耗了更多的能量，而在随机方案中，在本地处理任务时消耗了更多的能量，任务由于较长的本地处理延迟，因为更多的任务是使用“随机”方法在本地处理的（如图 10 所示）。然而，“贪婪”方法的能耗和延迟非常高，这是由于无人机边缘服务器中的任务执行失败导致相同任务的多次上传，从而消耗了物联网设备的大量能量并导致长时间延误。

图 9 显示了相对于云服务器使用成本权重 β 的总成本。 比较这三种方法，可以看出所提出的基于 RL 的计算卸载方法可以达到一个 episode 中最低的平均总成本。总成本随着 β 的增加而增加，因为 β 的增加导致 β B c βB^c βBc 的增加，而 β B c βB^c βBc 是总成本的一个组成部分。还可以看出，所提出的方法的总成本增加速度快于其他两种方法，这是因为在当前的模拟设置下，如果选择得当，卫星云卸载可以实现比本地处理和无人机相对更好的性能。因此，所提出的方法学习环境并以更高的概率选择云卸载。这个事实可以在图 10 中看到，它显示了每个卸载方法的每个卸载设备的选择次数。 对于所提出的方法，它比其他两种卸载方式更频繁地选择卫星云。与卫星-云相比，本地处理延迟更长，而无人机边缘可能会遭受竞争问题和无人机移动性高，尽管它具有传输速率高和服务器使用成本低的优点。 “随机”和“贪婪”方法选择本地处理和卫星-云的数量几乎相同。 “贪婪”方法更多选择 UAV-Edge，如果 UAV 当前不可用，它很可能会等待未来的 UAV 连接。

图 11 显示了相对于延迟权重的总成本，即 ω ˉ \bar{ω} ωˉ。随着 ω ˉ \bar{ω} ωˉ的增加，所有三种卸载方法的总成本都会增加，这是由于 ω ˉ T \bar{ω}T ωˉT 的增加，这是总成本的延迟部分。 然而，所提出的卸载方法可以实现三种方法中最低的总成本和较低的增长率，因为它可以从环境中学习一个最优策略来减少总任务延迟。

8 CONCLUSION

在本文中，我们研究了 SAGIN 中的物联网计算卸载问题。 我们提出了一种联合虚拟机分配和任务调度机制，以有效地将计算资源分配给无人机边缘服务器中的不同虚拟机。 为了卸载计算密集型任务，我们提出了一种基于 RL 的计算卸载方法来处理多维 SAGIN 资源并学习网络的动态情况。 深度神经网络、策略梯度和actor-critic方法已被用于提高学习性能。 仿真结果验证了所提方法的收敛性和有效性。 我们的工作可以为 SAGIN 中边缘/云计算这一重要但尚未充分探索的领域提供有价值的见解。 未来，我们将重点共同优化SAGIN中的通信、缓存和计算资源。