基于并发联邦强化学习的物联网边缘计算资源分配

摘要

资源分配是物联网边缘计算中的一个基本研究问题，而强化学习正迅速成为一种常见的解决方案。目前大多数技术都涉及决策者来确定资源的分配方式和位置。在标准的云系统中，该决策者是中央服务器；在边缘系统中，决策者是边缘主机。这两种方法均存在缺点：边缘主机并不总是能够获取足够的全局信息以制定最优的资源分配策略，而中央服务器虽能做到这一点，却会牺牲隐私。因此，需要一种能够兼顾两者的解决方案。本文提出了一种新颖的资源分配方法，称为并发联邦强化学习。该方案继承了联邦学习的隐私保护特性、强化学习的复杂问题解决能力，并通过联合决策的形式引入了并发性，使得资源分配策略有利于全局系统的整体效用。实验表明，该方法在系统整体效用、任务完成速度和资源利用率方面均表现出最先进的性能。

索引术语

资源分配；深度强化学习；隐私保护

一、引言

边缘计算最初被构想为解决物联网系统网络蔓延的方案 [1]。随着物联网系统支持的设备越来越多，中央服务器无法及时应对计算负担。边缘计算将部分处理任务下放到终端设备，以减少对云中心的依赖。尽管这是一个巧妙的解决方案，但它也为云系统的未来发展带来了新的障碍。其中最重要的问题之一是如何在边缘节点与中心云之间最优地分配计算资源 [2]。

该问题的两种主要方法都涉及决策者。第一种更传统的方法是基于全局信息进行决策的全知控制器，该控制器可能是中央服务器、边缘设备或第三方系统。第二种较新的方法是将决策权交给边缘主机甚至终端设备，让每个设备根据本地信息自行确定最符合自身需求的资源分配方案。

全局方法能够实现良好的整体吞吐量，适用于希望最大化利用其基础设施的系统管理员。然而，这类方法使系统易受侵犯隐私与安全。局部方法减轻了中央服务器的负担，通常能提供良好的响应时间。但系统整体效率往往较差。基础设施通常无法得到充分利用，仍可能出现瓶颈。

我们的目标是开发一种资源分配方法，在不牺牲系统中任何一方隐私的情况下实现全局最优。这是一个具有挑战性的目标，因为为了保护隐私，各方必须隐藏或模糊其私有信息[5]，而在缺乏完整和清晰信息的情况下，实现全局最优可能十分困难。我们的解决方案是设计一种将联合决策引入联邦强化学习融合过程的资源分配方案。我们将该方案称为并发联邦强化学习，简称基于CFRL。

联邦学习最初是为移动计算环境提出的，它使移动设备能够协作学习预测模型，而不会因共享训练数据而侵犯终端用户的隐私[6]–[8]。相比之下，强化学习旨在解决高度复杂的序列决策问题。此后，强化学习模型与深度神经网络相结合，形成了深度强化学习，已证明能够应对战略人工智能中的一些 toughest 挑战，例如掌握围棋游戏 [9]。将这两种方案融合为联邦强化学习，结合了两种范式的优点，使决策者能够在不泄露各方训练数据隐私的情况下，做出战略上最优的决策[10]。然而，现有的联邦强化学习方法存在一个共同缺点，即每个客户端的本地模型必须上传到服务器以形成全局模型[11]–[15]。Geiping等人[16]的一项白帽研究表明，攻击者仅利用模型的梯度即可重建模型的输入数据。因此，由于服务器持有每个客户端的本地模型，任何能够访问服务器的人都可能使用 Geiping方法重建系统中任意或所有参与客户端的训练数据。

为了克服这一关键缺点，我们提出了并发作为一种新的决策类别，其中服务器与边缘主机共同进行资源分配决策。此外，在基于CFRL的算法中，边缘主机仅将其本地模型的输出共享给服务器，因此无论是服务器还是边缘主机都无法获知其他主机的输入数据或本地模型参数。服务器通过将奖励分配给各个边缘主机来引导学习过程，因此，同样地，无论是服务器还是边缘主机都无法获知其他主机的私有决策。

策略。尽管数据隐私永远无法做到100%保证，但该方案比标准的联邦学习提供了更强的隐私保护，并且不易受到模型推断攻击。

总之，我们的工作在以下方面对现有文献做出了主要贡献。
这是首个同时考虑边缘主机和服务器隐私的资源分配方法。
我们将并发的概念引入联邦强化学习，其中智能体和服务器共同做出决策，但双方从不共享其模型，仅共享输出和奖励。该新算法可应用于其他类似的协作场景。
•实验表明，即使各方仅共享有限的信息，该方法也能实现卓越的性能。
本文的其余部分组织如下。下一节回顾并比较了我们的研究与类似工作的异同。第三节介绍了强化学习和联邦学习方案的预备知识，随后在第四节中详细阐述了资源分配方法。第五节给出了关于隐私和效用的理论分析。第六节展示了实验以及与当前最先进的方法的比较，第七节对全文进行了简要总结，并指出了我们的未来工作方向。

II. 相关工作

强化学习作为边缘计算环境中资源分配工具已被广泛研究。因此，本文综述仅包含与我们研究密切相关的文献。关于边缘计算资源管理的全面综述可参见[2],[17]。

如前所述，用于资源分配的强化学习方法主要分为两类：一类具有本地决策者，另一类具有全局决策者。接下来将讨论每个类别中的相关研究。

A. 本地决策者

在具有本地决策者的方法中，资源分配策略通常由每个用户或边缘主机仅使用本地信息来制定。因此，每个实体都有旨在最大化自身效用的个体目标，同时尽可能地最大化所有实体的总体效用。当存在效用冲突时，优先独立最大化自身的效用，从而导致总体效用下降。

陈等人[18]考虑了移动用户将任务卸载到基站的情况。他们将选择基站的问题建模为马尔可夫决策过程，并通过深度强化学习来解决。该学习算法的输入包括移动用户的任务队列、基站的能量队列以及用户与基站之间的信道质量。输出策略指导手机选择哪些基站。

刘等人 [19]提出了一种用于资源分配的深度强化学习算法，其中车辆作为边缘设备。在网络中，每辆车充当移动边缘服务器，向附近用户提供计算服务。当用户需要执行计算任务时，附近的车辆会决策该任务应由用户自身执行、由车辆服务器执行，还是应发送到固定边缘服务器以最大化网络效用。

刘等人[20]–[22]研究了使用基于智能体的强化学习进行资源分配。在[20],中，他们采用强化学习方法将每个终端设备建模为一个智能体，该智能体可决策是否将计算任务卸载到边缘主机。在[21],中，他们首先根据用户的优先级将终端用户分组为多个簇。然后，在每个簇中，每个被建模为智能体的用户应用深度强化学习来做出一系列任务卸载决策。在[22],中，物联网用户（即智能体）以聚合的方式进行计算卸载决策，其中每个智能体独立学习，并通过中央网关共享总体计算容量信号。

熊等人[4]提出了一种用于物联网边缘计算中资源分配的深度强化学习方法，以最小化任务的平均完成时间和请求资源的平均数量。每个边缘主机独立地学习如何将其计算资源分配给各自的任务。计算资源按时间划分为滑动窗口。为了提高学习性能，他们在经典的深度Q网络算法中引入了多个经验回放记忆，其中每个记忆对应一个资源请求。

B. 全局决策者

在全局信息方法中，决策通常由云服务器或全知控制器 [23]–[29], 做出，其目标是最大化系统的整体效用。然而，由于控制器必须从所有实体收集状态信息以制定最优资源分配策略，隐私成为一个问题。

魏等人 [3]在边缘计算中联合优化了内容缓存、计算卸载和无线资源分配，通过使用演员‐评论家深度强化学习最小化平均端到端延迟来解决其联合决策问题。评论家采用深度神经网络来估计状态和动作的价值函数，而演员则使用另一个深度神经网络表示参数化随机策略，以改进最终策略。采用这种方法，很少会出现陷入局部最优的问题。

屈等人 [30]将区块链技术融入深度强化学习中，用于资源分配，以确保物联网设备数据不被篡改。除了每个物联网设备的状态外，在学习过程中还考虑了区块链挖矿的奖励与成本。学习算法输出的决策不仅包括如何卸载任务，还包括是否进行区块链挖矿。

阿尔克尔姆等人 [31] 提出了一种增强的在线Q学习方案，用于资源分配，以实现最大物联网系统效用和物联网应用间的公平性。为了实现这两个目标，他们使用无妒忌特性 [32] 来量化公平性，并将公平性融入目标函数中。然后，通过使用Q学习方案优化目标函数，可以同时优化效用和公平性。

[13]和[33]均尝试将联邦学习应用于单个物联网设备以提升强化学习性能。在他们的研究中，联邦学习与强化学习是分别进行的。边缘主机使用强化学习训练本地模型，然后将该模型上传至服务器。服务器将这些本地模型聚合为全局模型，并将全局模型分发回边缘主机。相比之下，CRFL允许边缘主机和云服务器通过仅共享模型的输出和接收到的奖励来并发学习。这样可以保护边缘主机和云服务器的模型隐私。

C. 相关工作讨论

局部方法往往无法提供全系统速度或效率，因为做出决策的实体缺乏全局信息。相反，全局方法能够以最优方式管理资源，确保整个系统中的所有任务都能尽可能及时地完成。然而，这一过程会牺牲隐私。此外，一些联邦学习方法优先考虑学习性能而非隐私，从而削弱了使用该范式原本带来的优势。一些研究提出直接将联邦学习用作边缘计算中服务放置和资源分配的隐私保护方法[34]。然而，正如我们将在第五节‐B中讨论的，使用联邦学习的边缘主机仍然容易受到对抗性活动的影响。通过将联邦学习与强化学习相结合，并将并发决策引入架构中，我们提出的基于CFRL的算法在实现全局最优的同时，相较于传统联邦学习提供了更强的隐私保障。

III. 预备知识

A. 强化学习

强化学习基于一种试错式学习范式，最初旨在解决序列决策问题。形式上，序列决策过程可以建模为一个马尔可夫决策过程（MDP）[35],，表示为一个元组 〈S, A, T, R〉，其中S是状态集合， A是智能体可用的动作集合，T是转移函数， R是奖励函数。

在每一步中，智能体观察环境的状态 s ∈ S ，并根据其策略π选择一个动作 a ∈ A。执行该动作后，智能体获得一个实值奖励 r，环境则转移到新的状态 s ′ ∈ S。随后，智能体根据奖励 r和新状态 s ′更新其策略 π 。该策略 π可以表示为一个Q函数 Q(s, a)，用于估计智能体在状态 s下执行动作 a所能获得的奖励。通过该策略，智能体逐渐积累知识并改进其策略，以最大化其总的长期预期奖励。对于特定策略 π 的Q函数 Qπ(s, a)被定义为

$$
Qπ(s, a)= Eπ[
∞
∑
t=1
γ · r(st, at)|st= s, at= a], (1)
$$

其中 γ是折扣因子，最优策略 π∗是能够产生最大Q函数值的策略，即

$$
Q∗(s, a)= max π Qπ(s, a). (2)
$$

因此，寻找最优策略 π∗ 等价于推导最优Q函数 Q∗(s, a)，这可以通过贝尔曼方程实现：

$$
Q∗(s, a)= Eπ[r(st, at)+ γ max a′ Q∗(s′, a′)|st= s, at= a]. (3)
$$

因此，Q函数的值可以通过以下迭代更新来计算：

$$
Q(s, a)← Q(s, a)+ α[r(s, a)+ γ max a′ Q(s′, a′)− Q(s, a)]. (4)
$$

非深度版本的强化学习无法处理高度复杂的问题，例如涉及大量状态和/或动作的问题。这是因为用于存储状态‐动作对 Q(s, a)的Q值的Q表变得过于庞大，难以及时更新和维护。Mnih等人[36]提出将深度Q网络(DQN)引入该方案，从而产生了深度强化学习。在深度强化学习中， Q表由神经网络近似表示，即 Q(s, a; θ)，其开销远小于维护一个大型Q表。其中， θ表示网络的权重，状态 s作为输入，输出为Q值向量，每个值对应一个动作 a。这种新的、更高效的架构能够处理高度复杂的问题。

为了学习 Q(s, a; θ)的最优值，使用均方误差损失函数 L(θ)来更新权重 θ。

$$
L(θ)= 1
|B|∑
e ∈ B
[(r(s, a)+ γ max
a ′ Q(s ′, a′; θ)− Q(s, a; θ)) 2 ], (5)
$$

其中 e= 〈s, a, r(s, a) s′〉是一个经验样本，表示具有奖励的状态转移；而 B是用于训练DQN的经验样本批次。最小化 L(θ)等同于减小贝尔曼方程中的均方误差。

B. 联邦学习

联邦学习由谷歌于2017年首次提出，作为标准集中式机器学习的一种替代方法[37]。在联邦学习中，各个用户协作学习一个共享预测模型，而无需将每个用户本地设备上的私有数据作为训练数据进行共享。尽管并非绝对安全，但这种范式确实能够防范多种类型的隐私攻击，因此已被应用于多个实际应用中[7]。

图1 展示了一个典型联邦学习框架的结构。训练中心将一个基于通用数据训练而成的通用学习模型分发给网络中的所有设备，以完成一项广泛任务——例如图像处理。

在第一次学习迭代中，每个客户端（也称为用户）从训练中心将其下载到本地设备。他们利用自身的本地数据对模型进行改进，并通过安全通信通道将改进的摘要作为小幅更新发送回服务器。云服务器将所有更新汇总，形成整体改进的共享模型。此过程不断重复，直到各客户端在后续步骤中下载每次更新后的全局模型。在整个过程中，任何客户端的数据都不会与训练中心或其他客户端共享，数据始终保留在本地设备上。

然而，在联邦学习中，不共享数据并不足以保护数据隐私，因为高级攻击方法可以利用模型参数来重构训练数据[16]。现有的防御方法包括差分隐私[38],、安全聚合 [39]和安全多方计算[40]。然而，差分隐私可能会显著降低所得到模型的准确性[41]；安全聚合可能需要巨大的计算成本[16]；安全多方计算可能由于在客户端之间传递令牌而产生额外的通信开销[40]。这些现有防御方法的缺点促使我们开发一种安全高效的联邦学习框架，用于物联网边缘计算中的资源分配。

C. 联邦强化学习

将深度强化学习与联邦学习相结合，产生了一种新的计算范式——联邦深度强化学习[10]，其中每个用户训练一个本地DQN，而中心训练一个通用DQN。在每次学习迭代中，中心向每个用户发送一个策略。每个用户遵循该策略执行动作并获得奖励。随后，每个用户利用所接收的奖励更新其本地DQN。同时，每个用户将她的奖励信号返回给中心，中心则基于这些奖励信号更新通用DQN。

IV. 并发联邦强化学习（CFRL）方法

A. 我们方法的概述

考虑一个由一台服务器和多个边缘主机组成的边缘计算系统。每个边缘主机为其服务的多个物联网设备提供支持，这些设备定期上传需要处理的任务。任务在等待调度时被存储在边缘主机的队列中。边缘主机根据队列中的任务，与服务器协作监控和管理其资源分配，根据自身拥有的资源进行任务调度或将工作卸载到服务器。目标是尽快完成整个系统中的所有任务。

该全局目标被建模为一个包含三个变量的马尔可夫决策过程：状态、动作和奖励。对于边缘主机而言，其状态是它们的状态，动作为其资源分配策略。由于目标是快速完成任务，因此奖励基于平均任务完成时间给出。对于服务器而言，其状态由边缘主机制定的资源分配策略组成，动作为服务器的资源划分策略。服务器的奖励基于为边缘主机预留的资源数量以及代表边缘主机完成的任务数量。

在接下来的章节中，我们将描述该框架的流程、各个变量以及相关算法。该方案的概述如图2所示，全文所使用的符号总结见表I。

符号	含义
S	状态空间
A	动作/策略空间
T	转移函数
R	奖励函数
ne	边缘主机的数量
C	边缘主机的资源分配状态矩阵
τ	边缘主机的资源需求向量
m	边缘主机拥有的资源数量
n	时间滑动窗口的长度
cτi	分配给任务 τi 的资源数量
t	时间步索引
tτi	任务 τi 的起始时间步
nτ	服务器拥有的资源数量
d1,…, dne	服务器预留用于边缘主机的资源划分
uτi	完成任务 τi 的效用
tqτi	任务 τi 在队列中停留的时间步数
t0	发送任务到服务器的时间步数
re	边缘主机的奖励
rs	服务器的奖励
λ	泊松分布的均值速率

B. 学习过程

每个学习轮次包含三个阶段：策略创建阶段、策略执行阶段和模型更新阶段。在策略创建阶段，每个边缘主机制定本地资源分配策略，并将其共享给服务器。然后，服务器生成资源划分策略，为每个边缘主机预留资源。这两类策略均通过深度强化学习算法构建。在策略执行阶段，边缘主机可按照所制定的策略将自身资源分配给队列中的任务，或可将任务发送至服务器进行处理。

其预留资源。如果任务成功分配，边缘主机会获得奖励。同样，服务器也会根据其预留的资源数量以及完成的任务数量获得奖励。在最终模型更新阶段，边缘主机和服务器都使用所获得的奖励来更新其本地DQN。

C. 状态

每个边缘主机的状态被描述为一个状态 s，该状态形式化地定义为一个二元组
$$
S={s|s= \langle C, \tau \rangle}, (6)
$$
其中，$C$ 是表示资源分配状态的矩阵，$\tau$ 是指定每个任务资源需求的向量。因此，状态 $s$ 可以按照图3以矩阵形式表示。

0	1	1	0	0
0	1	1	0	0
0	1	1	0	0
0	1	1	0	0
0	0	0	0	0
0	0	1	1	1
					.
					.
					.

矩阵
4 6 4
队列中的任务
. . .

图3：边缘主机的状态(s)
矩阵 $C$ 是一个 $m \times n$ 矩阵，其中 $m$ 是边缘主机所拥有的资源数量，$n$ 是长度滑动窗口。矩阵 $C$ 中的每个值都是一个二进制标志，其中0表示资源在给定时间步可用，1表示该资源已被分配。$C$ 中的每一行表示一个资源 $c_i, 1 \leq i \leq m$ 在未来 $n$ 个时间步内的调度情况。例如，在$C$的第一行中，资源$c_1$已被分配，并将在时间步 $t_2$ 和 $t_3$ 中被使用。注意，这些资源 $c_1,…, c_m$ 具有相同的功能，我们仅为了表述简便而使用了不同的下标。矩阵$C$的列代表滑动窗口中的时间步，随着时间推移，窗口向左移动一列。时间步的长度（例如一秒、一毫秒或一天）取决于具体应用。

向量 $\tau=[\tau_1,…, \tau_n]$ 是一个 $n$维向量，表示完成队列中的任务 $n$ 所需的资源。向量中的每个分量表示相应任务所需的资源数量。例如，在图3的向量 $\tau$ 中，第一个任务 $\tau_1$ 所需的资源数量为4：$\tau_1= 4$，而第二个任务 $\tau_2$ 所需的资源数量为6：$\tau_2= 6$。为了便于表示，我们使用 $\tau_i$ 同时表示第 $i$ 个任务的名称以及第 $i$ 个任务所需的资源数量。

D. 动作

如图所示，边缘主机的动作空间与服务器不同。以下使用一个非常简单的示例进行说明，在该示例中每个时间步仅需将资源分配给一个任务。实际上，资源分配动作是一种策略，可能涉及边缘主机队列中的多个任务。

1) 每个边缘主机的动作 ：形式上，边缘主机动作 $e$ 是一个二元组，定义为：
$$
A_e={a|a= \langle c, t \rangle}, (7)
$$
其中 $c \in{1,…, m}$ 和 $t \in{1,…, n}$。因此，一个动作 $a= \langle c, t \rangle$ 表示从第 $t$ 个时间步开始，直到任务完成的时间步，在矩阵$C$的可用位置中进行的一系列资源分配 $c$。例如，假设任务 $\tau_1$ 需要6个资源，即 $\tau_1= 6$。一种可能的动作是 $a= \langle 3, 1 \rangle$，这意味着该任务在时间步1获得3个资源，在时间步2再获得3个资源，如图4所示。

	1	1		0	0
	1	1		0	0
	1	1		0	0
	1	1			0
			0	0	0
	0	0	0	0	0

一种分配操作 对于任务，其 需要6个资源 最低的 可用索引

图4：任务 $\tau_1$ 的一个边缘主机动作示例。此动作需要6个资源。

对于给定的任务 $\tau_i, 1 \leq i \leq n$，动作集为 $A_e(\tau_i) = {a_{\tau_i}|a_{\tau_i}= \langle c_{\tau_i}, t_{\tau_i} \rangle \cup \langle 0, 0 \rangle}$，其中 $c_{\tau_i} \in{c|\tau_i \mod c= 0}$，且 $t_{\tau_i} ={t|C_t = 0}$。这里，$C_t$ 是矩阵 $C$ 的一个子矩阵。$C_t$ 的行数为 $c_{\tau_i}$，而列数为 $\tau_i / c_{\tau_i}$，如图4所示。动作 $\langle 0, 0 \rangle$ 表示该任务被发送到服务器，因为边缘主机没有足够的可用资源来执行该任务。

2) 服务器的动作 ：服务器的目标是完成边缘主机无法处理的任务。因此，服务器的动作实际上是资源分配。例如，假设服务器有10个资源，并且有两个边缘主机。服务器的一个可能动作为 $\langle 3, 7 \rangle$，这意味着将3个资源分配给第一个边缘主机，7个资源分配给第二个边缘主机。注意，服务器不必分配其全部资源。因此，$\langle 2, 5 \rangle$ 是另一个可能的动作。

假设有 $n_e$ 个边缘主机，且服务器拥有 $n_r$ 资源，则服务器的动作集为 $A_s={a_s|a_s=\langle d_1,…, d_{n_e} \rangle}$，其中每个 $0 \leq d_i \leq n_r$、$i \in[1, n_e]$ 和 $\sum_{i=1}^{n_e} d_i \leq n_r$。

E. 奖励

如前所述，整体目标是尽快完成系统中的所有任务。因此，边缘主机的奖励根据完成任务所用的时间步数来确定。形式上，给定状态 $s$ 和动作 $a_{\tau_i}=\langle c_{\tau_i}, t_{\tau_i} \rangle$，其中 $i \in[1, n]$，边缘主机 $r_e$ 的奖励定义为：
$$
r_e=
\begin{cases}
u_{\tau_i} - (t_{\tau_i} + \frac{\tau_i}{c_{\tau_i}}) & \text{if task } \tau_i \text{ is allocated successfully;} \
-1 & \text{if } \tau_i \text{ is allocated unsuccessfully;} \
u_{\tau_i} - t_0 & \text{if } \tau_i \text{ is sent to the server}
\end{cases}
(8)
$$
这里，$u_{\tau_i}$ 是任务 $\tau_i$ 的效用，$t^q_{\tau_i}$ 是任务 $\tau_i$ 在队列中停留的时间步数，$t_0$ 是一个常数，表示将任务发送到服务器所需的时间步数。根据奖励 $r_e$ 的定义，如果动作 $a_{\tau_i}$ 成功分配了任务 $\tau_i$，边缘主机获得的奖励等于该任务的效用减去完成该任务所用的时间步数。我们假设 $u_{\tau_i} > (t_{\tau_i} + \frac{\tau_i}{c_{\tau_i}})$，否则边缘主机将没有动力去完成任何任务。相反，如果任务分配不成功，任务将在队列中保留到下一个时间步，动作 $a_{\tau_i}$ 将导致一个大小为1的惩罚。当任务 $\tau_i$ 被发送到服务器时，即动作为 $\langle 0, 0 \rangle$，将获得 $u_{\tau_i} - t_0$ 的奖励。我们假设 $u_{\tau_i} > t_0$，否则边缘主机将没有动力把任何任务发送到服务器。这三种奖励机制通过负奖励来抑制分配失败的情况；通过给予最高奖励来鼓励边缘主机以最短时间完成任务；同时也允许主机选择将任务委托给服务器以避免惩罚。

与边缘主机不同，服务器的奖励基于：1）为边缘主机预留的资源数量；以及 2）完成任务所用的时间步数量。形式上，给定动作 $\langle d_1 ,…, d_{n_e} \rangle$，服务器 $r_s$ 的奖励定义为：
$$
r_s=
\begin{cases}
-\sum_{i=1}^{n_e} d_i & \text{if no task is received,} \
u_{\tau_i} - \frac{d_{\tau_i}}{d_i^e} - \sum_{i=1}^{n_e} d_i & \text{if } \tau_i \text{ is received from host } i.
\end{cases}
(9)
$$
奖励 $r_s$ 的定义表明，通过执行动作 $\langle d_1,…, d_{n_e} \rangle$，如果未接收到任务，服务器将获得负奖励，因为其资源被空置保留。当接收到任务时，该任务的效用会计入服务器的奖励中。同样地，当同时接收到多个任务时，这些任务的效用也将计入服务器的奖励。该奖励 $r_s$ 的定义鼓励服务器仅在需要时才保留资源。

F. 算法

算法1：边缘主机的算法

1 随机初始化DQN（深度Q网络）的权重 $\theta$；
2 初始化经验回放缓冲区 $D= \emptyset$；
3 随机初始化每个动作的 Q值；
4 对于 $t= 1$ 到 $\infty$ 执行
5 接收服务器的奖励信号 $r^s_i$，其中 $i$ 表示当前的边缘主机；
6 观察状态 $s_t$；
7 对于给定任务 $\tau$，以概率 $\varepsilon$ 随机选择一个动作 $a_\tau$。否则选择 $a_\tau= \arg\max_a Q(s_t, a_\tau; \theta)$;
8 执行动作 $a_\tau$；
9 接收奖励 $r_e$ 并进入新状态 $s_{t+1}$；
10 将样本 $\langle s_t, a_\tau, r_e + r^s_i, s_{t+1} \rangle$ 放入 $D$；
11 从 $D$ 中随机选择一批样本 $B$；
12 使用公式5计算 $L(\theta)$；
13 使用梯度下降更新权重 $\theta$；
14 将输出 Q‐值向量 $Q(s_t)$ 发送给服务器；

每个边缘主机的深度强化学习算法在算法1中给出。在每个时间步，由 $i$ 索引的边缘主机接收来自服务器的奖励信号 $r^s_i$（第5行）。然后，边缘主机观测到一个状态 $s_t$（第6行）。对于给定任务 $\tau$，通过 $\varepsilon$‐greedy选择一个动作（第7行）。执行该动作后，边缘主机接收到奖励 $r_e$ 并更新其状态 $s_{t+1}$（第8和第9行）。将状态、动作和奖励组合成一个经验样本 $\langle s_t, a_\tau, r_e, s_{t+1} \rangle$，存储在回放缓冲集 $D$ 中（第10行）。随后，边缘主机从回放缓冲集 $D$ 中随机选取一批样本 $B$，用于计算损失函数 $L(\theta)$，并更新权重 $\theta$ （第11‐13行）。最后，在第14行，边缘主机将其本地DQN的输出，即一个 Q‐向量 $Q(s_t)$，发送给服务器。服务器也将采用一种深度强化学习算法（算法2）进行资源分配，并向边缘主机返回奖励信号。

一旦服务器从每个边缘主机接收到 Q‐值向量，它将这些向量组合成一个状态 $o_t$，该状态以矩阵形式表示（第5和第6行）。然后，服务器使用上一轮学习中获得的状态、动作和奖励创建一个经验样本$(o_{t-1}, a_{t-1}^s, r_{t-1}^s, o_t)$，并将该样本存储在回放缓冲集 $D’$ 中（第7行）。在下一轮学习之前，服务器无法观察到新的状态，直到它再次收到来自边缘主机的 Q‐值向量。服务器通过 $\varepsilon$‐贪心策略选择一个动作$a_s$，即一种资源划分策略（第8行）。执行该动作后，服务器获得奖励 $r_s$

算法2：服务器的算法

1 随机初始化DQN（深度Q网络）的权重 $\theta’$；
2 初始化经验回放缓冲区 $D’= \emptyset$；
3 随机初始化每个动作的 Q值；
4 对于 $t= 2$ 到 $\infty$ 执行
5 接收来自每个边缘主机的 Q‐值向量；
6 将这些向量组合并形成一个状态 $o_t$；
7 将样本$(o_{t-1}, a_{t-1}^s, r_{t-1}^s, o_t)$放入 $D’$ 中；
8 以概率 $\varepsilon$ 随机选择一个动作 $a_s$。否则选择 $a_s= \arg\max_a Q(o_t, a_s; \theta’)$;
9 执行动作 $a_s$ 并获得奖励 $r_s$；
10 从 $D’$ 中随机选择一批样本 $B’$；
11 使用公式5计算 $L’(\theta)$；
12 使用梯度下降更新权重 $\theta’$；
13 将奖励 $r_s$ 分成 $n_e$ 份，并发送每一份将片段返回给相应的边缘主机；

（第9行）。然后，服务器从回放集 $D’$ 中随机选择一批样本$B’$来计算损失函数 $L’(\theta)$，并更新权重 $\theta’$（第10‐12 行）。最后，服务器将奖励 $r_s$ 划分为 $n_e$ 份，其中 $n_e$ 是边缘主机的数量，并将每一份发送回一个边缘主机。奖励 $r_s$ 的划分使用算法3。

算法3：服务器奖励的划分

1 输入：服务器的奖励 $r_s$；
2 输出：奖励 $r^s_1,…, r^s_{n_e}$；
3 对于 $i= 1$ 到 $n_e$ 执行
4 如果 边缘主机 $i$ 向服务器发送一个任务 $\tau_i$ 则
5 $r^s_i \leftarrow u_{\tau_i} - \frac{d_{\tau_i}}{d_i^e} - d_i$
6 else
7 $r^s_i \leftarrow -d_i$

奖励分配 $r_s$ 基于每个边缘主机预留的资源数量以及边缘主机是否向服务器发送任务。具体而言，对于边缘主机 $i$，假设其预留资源数量为 $d_i$，如果边缘主机 $i$ 将任务 $\tau_i$ 发送到服务器，则该边缘主机的奖励分配为 $i$, $r^s_i$（第 5行）；否则，该边缘主机的奖励分配为 $i$（第7行）。$-d_i$ 每次奖励分配都是一个信号，用于告知边缘主机其上一次动作对服务器而言是好还是不好。

V. 理论分析

A. 效用分析

基于CFRL的学习方案依赖于服务器通过奖励塑形来引导每个边缘主机的学习，即每个边缘主机的奖励会加上服务器奖励的一部分（算法1中的第10行）。奖励塑形是一种将领域知识融入强化学习以加速学习的方法[42]。一种标准的奖励塑形方法是修改原始过程的奖励，使算法能够更快地检测其动作的长期影响[43]。

奖励塑形函数的一种典型表述如下：
$$
F(s, s’)= \gamma\Phi(s’)-\Phi(s), (10)
$$
其中 $\Phi$ 是关于状态的实值函数。Ng等人[42]证明了，通过以公式10的形式，即 $r+F(s, s’)$，向原始奖励添加额外的奖励，可保证最终策略与原始策略等价。然而，在我们的问题中，奖励必须基于边缘主机和服务器的动作（算法 3）进行塑形。因此，实值函数$\Phi$最好定义在动作上而非状态上。因此，我们重新定义了奖励塑形函数为：
$$
\hat{F}(a^i_t, a^s_t, a^i_{t+1}, a^s_{t+1})=\gamma(\Phi(a^s_{t+1})+\Phi(a^i_{t+1}))-(\Phi(a^s_t)+\Phi(a^i_t)), (11)
$$
其中 $t$ 是时间步索引，$i$ 是边缘主机的索引，$a^i_t$ 是边缘主机 $i$ 在时间步 $t$ 采取的动作，$a^s_t$ 是服务器在时间步 $t$ 执行的动作。

为了证明以公式11形式塑造的奖励能够保证累积奖励的不变性，我们必须证明这一点。这引出了定理1。

定理1. 给定公式11中的奖励塑形函数，基于CFRL的方法保证边缘主机 $i$ 所获得的效用不变： $U(a_i)= U_\Phi(a_i)$，其中 $a_i$ 表示由一组状态和动作对组成的状态轨迹：
$$
a_i= \langle (s^i_0, a^i_0);…;(s^i_N, a^i_N) \rangle.
$$

证明。 给定 $U(a_i) = \sum_{t=0}^{N-1} \gamma^t [r(s^i_t, a^i_t) + \hat{F}]$ 和 ${v_0}(\cdot)(\cdot,\cdot,\hat{})$，我们有：
$$
U_\Phi(a_i)= \sum_{t=0}^{N-1} \gamma^t[r(s^i_t, a^i_t)+ \hat{F}]
= \sum_{t=0}^{N-1} \gamma^t[r(s^i_t, a^i_t)+\gamma(\Phi(a^s_{t+1})+\Phi(a^i_{t+1}))-(\Phi(a^s_t)+\Phi(a^i_t))]
= \sum_{t=0}^{N-1} \gamma^t r(s^i_t, a^i_t) + \sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^s_{t+1}) + \sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^i_{t+1}) - \sum_{t=0}^{N-1} \gamma^t \Phi(a^s_t) - \sum_{t=0}^{N-1} \gamma^t \Phi(a^i_t)
= U(a_i) + \sum_{t=1}^{N-1} \gamma^t \Phi(a^s_t) + \gamma^N \Phi(a^s_N) + \sum_{t=1}^{N-1} \gamma^t \Phi(a^i_t) + \gamma^N \Phi(a^i_N) - \sum_{t=1}^{N-1} \gamma^t \Phi(a^s_t) - \Phi(a^0_s) - \sum_{t=1}^{N-1} \gamma^t \Phi(a^i_t) - \Phi(a^0_i)
= U(a_i) + \gamma^N \Phi(a^s_N) + \gamma^N \Phi(a^i_N) - \Phi(a^0_s) - \Phi(a^0_i).
$$
为了保证效用的不变性， $U(a_i) = U_\Phi(a_i)$，我们需要确保 $\gamma^N \Phi(a^s_N) + \gamma^N \Phi(a^i_N) - \Phi(a^0_s) - \Phi(a^0_i) = 0$。

首先，由于服务器在时间步 $0$ 不向任何边缘主机提供奖励信号，因此 $\Phi(a^0_s)$ 和 $\Phi(a^0_i)$ 均等于 $0$。接下来，算法3规定服务器不对每个边缘主机的最后任务给予奖励。因此，两者 $\gamma^N \Phi(a^s_N)$ 和 $\gamma^N \Phi(a^i_N)$ 等于 $0$。此外，由于 $i$ 是系统中的任意边缘主机，该证明可应用于所有边缘主机。

备注1. 在算法3中，服务器发送给边缘主机的奖励信号是基于服务器和边缘主机的当前动作。然而，在公式11中，$\hat{F}$ 奖励塑形函数要求塑形奖励基于服务器和边缘主机的当前动作以及下一动作。这看似不一致，但实际上并非如此。为了说明原因，我们必须重新审视求和项 $\sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^s_{t+1}) + \sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^i_{t+1})$，其中涉及了服务器和边缘主机的下一动作 $i$。通过对 $\sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^s_{t+1})$ 和 $\sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^i_{t+1})$ 进行拆分，我们得到
$$
\sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^s_{t+1}) + \sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^i_{t+1}) = \sum_{t=1}^{N-1} \gamma^t \Phi(a^s_t) + \gamma^N \Phi(a^s_N) + \sum_{t=1}^{N-1} \gamma^t \Phi(a^i_t) + \gamma^N \Phi(a^i_N).
(12)
$$
公式12表明，通过合理设置时间步索引，可以将下一动作纳入当前动作中。此外，如定理1的证明中所述，$\gamma^N \Phi(a^s_N)$ 和 $\gamma^N \Phi(a^i_N)$ 均等于 0。因此，我们得到
$$
\sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^s_{t+1}) + \sum_{t=0}^{N-1} \gamma^{t+1}\Phi(a^i_{t+1}) = \sum_{t=1}^{N-1} \gamma^t \Phi(a^s_t) + \sum_{t=1}^{N-1} \gamma^t \Phi(a^i_t),
$$
仅包含服务器和边缘主机的当前动作，解决了不一致性问题。

关于效用的最后一点，定理1 表明，即使服务器介入任务处理，每个边缘主机仍能获得其预期效用。由服务器处理任务将提高服务器的资源利用率，因为服务器自身的奖励是基于其为边缘主机保留并供自身使用的资源数量。

B. 隐私分析

如第I节所述，现有的基于联邦学习的方法容易受到对抗性活动的影响，而我们的方法能够在很大程度上克服这些影响。我们首先分析现有方法为何存在漏洞，然后解释我们的方法如何克服这一漏洞。

在现有的基于联邦学习的方法中，每个边缘主机必须将其模型参数更新（即梯度）与服务器共享。然而，服务器可以重构每个边缘主机的输入数据。服务器能够进行重构的原因如下所述。训练一个机器学习模型（例如神经网络）等价于使用损失函数 $L$ 和一组包含数据记录 $x_i$ 及相应标签 $y_i$ 的训练数据 $D$ 来优化网络的参数 $\theta$，以求解：
$$
L_\theta = \min_\theta \sum_{i=1}^{|D|} L_\theta(x_i, y_i), (13)
$$
其中 $i$ 是数据记录的索引。在联邦学习中，每个边缘主机将其梯度 $\nabla_\theta L_\theta(x_i, y_i)$ 与服务器共享。然后，服务器累积这些梯度，并使用以下方程更新整体权重：
$$
\theta^{t+1}= \theta^t - \frac{1}{N} \sum_{j=1}^{N} \nabla_\theta L^j_{\theta^t}, (14)
$$
其中 $t$ 是学习轮次的索引，$j$ 是边缘主机的索引，$N$ 表示边缘主机的数量。参数 $\theta^{t+1}$ 被发送回各个边缘主机以更新其本地参数。由于仅共享参数，关于数据记录（x, y）的信息被隐藏。然而，Geiping等人[16]表明，数据记录的信息（x, y）可以从参数1中恢复。给定一个无偏的全连接层，将输入$x_l$映射到输出，并在经过非线性激活函数（例如ReLU）之后： $x_{l+1}= \max(A_l x_l,0)$，其中 $A_l$ 为具有兼容维度的矩阵。然后，根据链式法则，$x_l$ 可通过以下表达式计算：
$$
\left(\frac{dL}{d(x_{l+1}) k}\right)^{-1} \cdot \left(\frac{dL}{d(A_l) {i,:}}\right)^T, (15)
$$
其中 $k$ 是维度的索引。

为了克服这一漏洞，在我们的并发联邦强化学习方法中，每个边缘主机不共享模型参数更新，而是仅与服务器共享其模型输出。然而，共享输出可能引发另一种漏洞：模型提取[44],[45]，其目的是通过窃取目标模型的结构（例如权重）来复制该模型的功能。一旦获得模型的结构，攻击者便可发起前述的输入重构攻击。例如，一种典型的模型提取方法基于方程求解[44]。给定一个用于二分类 $c= 2$ 的线性回归模型 $f$，其参数为$w \in \mathbb{R}^d$ 和 $\beta \in \mathbb{R}$，模型 $f$ 对给定数据记录 $x^ $ 输出的概率为$f(x^ ) = \sigma(w \cdot x^ + \beta)$，其中 $\sigma(t) = \frac{1}{1+e^{-t}}$。因此，权重$w$ 可通过求解线性方程$w = \sigma^{-1}(f(x^ )) - \beta / x^*$ 得到。一旦获得权重$w$，攻击者便可通过使用相应输出求解另一个线性方程：$x = (\sigma^{-1}(f(x)) - \beta)/w$ 来恢复任意输入数据记录 $x$。该攻击方法也可扩展到深度神经网络。以softmax模型为例，方程形式为：$f_k(x) = \frac{e^{w_k x+\beta_k}}{\sum_{j=0}^{c-1} e^{w_j x+\beta_j}}$。该方程组可通过最小化适当的损失函数（例如逻辑损失）来求解。然而，这些模型提取攻击有一个共同的缺点，即攻击者必须能够访问目标模型。因此，一种直观的防御方法是禁止对目标模型的访问。在我们的方法中，每个边缘主机拥有一个本地模型，该模型物理上位于各自主机上，并且不允许包括服务器在内的任何其他方访问。因此，我们的方法可自动避免模型提取攻击。

目前，大多数恢复数据的质量，如[16],所示，还不够好。然而，[16]中的工作提供了一种在联邦学习环境中恢复私有数据的新方法，初步结果证明不共享数据的安全性并不足够。

在极端情况下，如果攻击者以某种方式获得了目标模型的访问权限，我们可以采用私有预测接口 [46] 来防御攻击者。私有预测接口可以混淆模型的输出，从而迷惑攻击者。因此，即使攻击者能够访问模型，也无法利用模型的输出发起模型提取攻击。

VI. 实验

A. 设置

为了评估基于CFRL，我们使用PyTorch 1.2.0开发了一个Python模拟器，包含一个服务器和 $n_e$ 个边缘主机。服务器拥有 $n_r$ 资源，每个边缘主机拥有 $m$ 资源，每个边缘主机的滑动窗口包含 $n$ 个时间片。因此，资源分配状态矩阵$C$的大小为$m \times n$。

实验设计配置如下。分配给每个边缘主机的任务集按照均值速率为 $\lambda$ 的泊松分布动态生成。即，在每个时间步平均生成 $\lambda$ 个任务用于调度。每个任务需要 $\tau$ 资源来完成，其中 $\tau$ 在给定范围内遵循离散均匀分布。

评估是相对于另外两种方法进行的：基于DRL的深度强化学习[4]，以及在[47]中表示为IP‐based的最优整数线性规划算法。

基于DRL的[4]是当前资源分配领域的最先进的方法。其对状态和动作的定义与基于CFRL的方法相似。然而，基于DRL的方法不考虑服务器，仅考虑单个边缘主机。相比之下，基于CFRL的方法考虑了多个边缘主机，要求它们与服务器以联邦学习的方式协同学习。因此，基于DRL的方法与基于CFRL的方法在性能上的差异反映了联邦学习和并发带来的优势，同时也提供了与本地方法的对比。

IP-based[47]。该方法是一种广泛使用的优化方法，已被应用于边缘计算环境中的资源分配，但收效甚微。这是一种集中式方法，通过直接整合各个边缘主机提供的信息来实现资源的最优分配。它对于复杂的边缘计算系统既不高效也不适用，但可作为全局方法的基准。

用于评估性能的四个评估指标是：
- 平均效用，用于衡量每个边缘主机完成任务所获得的奖励；
- 平均时间步，即完成一个任务所用的平均时间步数；
- 平均资源利用率，即每个任务的已使用资源数量与已分配资源数量之比；
- 平均通信开销，用于衡量每个边缘主机发送的任务数量的平均值

服务器2

B. 结果

实验在三种场景下进行。在第一种场景中，我们将边缘主机数量 $n_e$ 从2变化到4，同时将任务数量 $\lambda$ 固定为8，并从范围 [3, 5]内均匀抽取每个任务所需的资源数量 $\tau$。在第二种场景中，我们将任务数量 $\lambda$ 从6变化到14，同时将边缘主机数量 $n_e$ 固定为3，并从范围[3, 5]内均匀抽取每个任务所需的资源数量 $\tau$。在第三种场景中，我们通过[3, 5],[4, 6]和[5, 7]改变 $\tau$ 的范围，其中边缘主机的数量 $n_e$ 固定为3，任务数量 $\lambda$ 固定为8。在所有三种场景中，每台主机拥有10个资源，服务器拥有30个资源，滑动窗口长度设置为5。

图5显示了所有三种场景的结果。在每种情况下，基于CFRL的资源利用率均高于基于DRL的，且所有任务的完成时间更短。此外，基于CFRL方法所需的通信开销小于基于DRL的方法。我们将这一结果归因于在资源分配优化过程中实现了联合决策。基于DRL的方法仅在单个边缘主机级别上进行资源优化，未将服务器和边缘主机作为一个整体加以考虑。

这些结果提供了三个进一步的有趣观察。首先，如图 5(c)所示，随着边缘主机数量的增加，两种方法之间的资源利用率差异减小。增加主机数量显然会增加可用资源的数量，从而为任务安排提供了更大的灵活性，以最大化资源使用。这对任何资源分配方法都有帮助。

其次，图5(d)显示，随着边缘主机数量的增加，基于 CFRL-based和DRL-based方法的通信开销几乎保持不变。这是因为在上述两种方法中，边缘主机之间不进行交互，因此每个边缘主机关于将任务发送到服务器的决策独立于其他边缘主机。

第三，在图5(i)中，随着任务大小的增加，基于 CFRL和基于DRL的方法之间的平均效用差异扩大。这是因为更大的任务大小加剧了对资源的竞争。基于CFRL的方法基于平等主义理念，共同生成有利于整个系统的资源分配策略，而基于DRL的方法在竞争环境中更倾向于适者生存的理念。任何被忽视的任务都会降低整体利用率。

由于我们方法中的深度Q学习框架需要一个训练过程，因此图6通过展示三种方法在训练过程中的性能变化来补充图5的结果。这里，图6(b)、6(f)和6(j)显示，在学习的早期阶段，边缘主机使用基于CFRL的方法完成任务所需的时间比使用基于DRL的方法更长。这是因为最初，服务器和主机都没有太多知识。当多方共同学习时，一方可能对其他方产生负面影响，导致高时间消耗。相比之下，采用基于DRL的方法，各方独立地学习，因此不会受到他方的负面影响。然而，随着学习的进行，各方会积累知识，能够共享这些知识将带来非常积极的影响。因此，在学习的后期阶段，大多数任务的完成时间在使用基于CFRL方法时更短。

此外，图6(c)、6(g)和6(k)显示CFRL-based在早期阶段实现了很高的资源利用率，但在后期阶段急剧下降。一种可能这一现象的解释是，在早期阶段，各方分配给任务的资源少于后期阶段——可能采用一种“试水”式的策略。分配较少资源意味着更高的资源利用率，但会带来更高时间成本和更低效用。由于各方的目标是提高其效用，因此随着学习的推进以及对哪些分配策略最有效变得熟悉，各方可能倾向于为任务分配更多资源。

七、结论

本文提出了一种基于并发联邦强化学习（ CFRL-based）的资源分配新算法。该方法在尽可能保护服务器和边缘主机隐私的同时，兼顾任务完成的全局速度和效率。与最先进的深度强化学习方法相比，我们的算法为边缘主机提供了更高的效用，并且在整个系统范围内，任务能在更短的时间内完成。未来，我们计划引入一种正式的隐私保护机制。将我们的方法用于为边缘主机提供隐私保护的理论保证。