随着人工智能^[1]、元宇宙、大规模超高清直播^[2]等计算密集型应用的蓬勃发展，如何满足快速增长的算力需求已经成为当前互联网所面临的一大挑战. 近年来，算力网络作为一种以“算”为中心、以“网”为骨干的全新网络化计算框架，为满足快速增长的计算资源需求提供了全新的解决思路. 算力网络通过整合网络中包括云数据中心、边缘计算服务器、终端设备等计算单元的资源，来支持弹性、泛在的计算资源获取，从而实现大规模、高密度的计算资源调度. 作为一种算力为核心的网络架构，如何实现高效的资源调度是保障算力网络性能的关键，同时也是最大的挑战.

首先，计算单元在地理上是分散的，且不同计算单元在设备能力、网络条件上都会存在差异. 算力网络中的计算任务也是随机到达的，如何在高度异构的场景下实现任务的动态卸载是算力网络面临的首要问题. 一些研究工作^[3-5]试图将异构场景下的资源调度问题表述为非凸优化问题，并证明了其NP-难. 解决这类问题需要启发式算法，但由于算力网络中的端节点行为具有随机性，启发式算法在理论上难以保证性能. 强化学习（reinforcement learning, RL）^[6-7]做为一种面向动态系统最优控制的解决方案也被部分工作采用. 基于强化学习方法通过将资源调度问题制定为马尔可夫决策过程（Markov decision process, MDP）来适应系统变化. 通过观察决策和环境之间的相互作用，RL代理迭代优化策略以获得最优的长期效用. 由于系统状态变化是不可预测的，确保输出决策的最优性需要RL方法在训练模型时探索系统状态变化，给资源调度算法带来了不可避免的时延问题.

此外，算力网络中潜在的计算资源提供者可能来自不同的运营商甚至是个体用户，给资源供给的可信和安全带来了隐患，传统依赖于第三方可信平台方法始终存在着开销和可扩展性问题. 近年来，区块链技术被认为是解决这个问题的一个有效方案. 区块链中关于资源的使用或提供都将由区块链的所有参与者进行验证，在实现去中心化资源管理的同时也保证了数据难以被篡改. 文献[8]等尝试利用区块链来支持面向资源调度卸载的激励机制. 一些工作，如文献[9]应用区块链来解决分布式学习系统中的数据安全问题. 文献[10-11]等研究使用区块链构建联邦学习框架. 然而，如何将区块链与算力网络结合从而支持可信、高效的资源调度仍然是一项十分具有挑战的工作. 其主要问题是在算力网络中操作区块链的成本很高. 每个区块链节点都需要生成区块，并通过共识算法达成协议. 如工作量证明（proof of work, PoW）共识机制就是计算密集型的. 例如，比特币所采用的PoW每年耗电量为204TW·h，几乎相当于整个泰国的耗电量. 然而PoW每秒的处理事务数只有4.6个，这对于计算任务频繁发布的算力网络来说是不可接受的. 因此，需要考虑更高吞吐量和节能特性的委托权益证明（DPoS）^[12]或实用的拜占庭容错（PBFT）^[13]等共识机制. 然而，这些共识算法不可避免地会给算力网络资源分配带来额外的延迟和成本. 这些问题要求设计基于区块链的算力网络，可以在维护区块链时重用资源消耗，并允许对资源分配做出快速决策.

可以看出，现有解决方案虽然针对算力网络分布式、异构化的资源特性，提出了诸多方法来试图解决任务调度问题，然而这些方法仍然以集中式的调度为主，部分基于区块链的解决方案虽然考虑到的算力网络分布式的特性，区块链所带来的额外开销这一问题仍没有得到有效解决，导致了相关的卸载方法性能难以满足需求. 因此，本文提出了一种区块链赋能的资源调度（blockchain empowered resource allocation，BCERA）算法. BCERA与现有解决方案的最显著区别在于，它将资源调度纳入区块链的共识机制中，从而提高资源利用率，利用区块链参与者的人群智能来解决复杂的资源调度问题. 具体来说，区块链参与者通过解决卸载问题达成协议，而不仅仅是应用传统的共识机制. 结果最好的参与者将被选出输出区块，包括资源交易信息. 为此，我们将BCERA中的资源调度问题表述为马尔可夫决策过程. 每个区块链参与者都应用了RL方法来解决这个问题. 区块链参与者通过比较各自输出策略的最优性，进一步争夺区块输出权. 此外，本文还提出了一种保证计算单元诚实性的激励机制. 本文的主要贡献包括2个方面：

1）提出了BCERA，其中区块链在维护资源调度信息和执行资源调度方面起着核心作用. BCERA的区块链节点通过解决算力网络资源调度问题达成共识. 每个区块链节点输出资源调度结果，并在给定约束内选择效用最大化的资源调度效用的策略节点来负责出块. 这样的设计提高了区块链参与者的资源利用率，减少了时间开销. 此外，BCERA可以从不同区块链参与者之间的竞争来选择最优策略以提高资源调度性能.

2）本文将算力网络资源调度问题表述为MDP. 由于瓶颈链路上的带宽竞争会显著影响卸载性能，所提出的问题不仅像大多数现有解决方案那样关注任务处理的延迟或能量消耗，而且还考虑了网络条件的动态性. 为了解决这个问题，允许每个区块链参与者使用RL方法. 为了进一步确保在处理卸载任务时的可信赖性，本文提出了一种集成智能合约功能的激励机制.

通过基于原型系统的实验验证，首先比较了BCERA与几种广泛使用的解决方案DPoS和PBFT的区块链吞吐量和延迟，说明了BCERA的可行性；还比较了几种基于RL方法在损失收敛、总奖励、总体延迟和资源使用方面的资源调度性.

1.   相关工作

1.1   算力网络场景下的计算资源调度

目前，融合云—边—端计算资源是实现算力网络的重要途径. 因此，高效地利用云—边—端资源来支持计算资源调度已经成为研究重点. Huang等人^[3]将计算资源调度问题构建为一个多任务分解的优化问题并提出了一种在线算法来实时的调度计算资源. 文献[4]将计算资源调度问题建模为一个混合整形问题并分解为数个子问题. 第1个子问题目标为最小化给定D2D通信对的计算资源使用，而第2个子问题目标为最大化可以支持的设备数量. Wen等人^[5]旨在提升边缘计算卸载任务的能效利用. Xing等人^[14]通过利用D2D链接来卸载任务到临近的移动节点从而最小化计算时延，同时优化了本地用户的计算资源调度. 考虑这些方法主要将问题建模为整型规划而大多数整型规划问题是NP难的，因此这些方法只能通过将问题放缩为一个凸优化问题来得到一个次优解.

此外，文献[9-11,14]方法都假设计算资源调度为确定性优化问题，而忽视了系统在运行过程中的随机变化. 实际情况与建模的差距进一步损害了资源调度的性能. 因此近年来不少学者开始运用RL的方法^[15]. 不同于上述确定性优化，RL方法通过求解MDP来逼近随机系统的长期最优解. Yi等人^[16]针对计算资源需求量巨大问题，运用深度强化来生成资源调度算法. 通过最大化累计奖励函数来离线训练一个深度Q网络. 根据训练好的深度Q网络所产生的策略来进行在线的任务调度决策. Chen等人^[17]考虑超密蜂窝场景的计算资源调度. 将资源调度问题构建成一个MDP并采用了一种基于双深度Q网络的强化学习方法来学习最优卸载策略. Zhang等人^[18]考虑了一个具有多数据中心的多接入的变换计算场景. 该场景中由于数据中心归属于不同的运营商，并且数据中心之间存在竞争，因此提出了一种基于RL的分布式任务调度方法. Liu等人^[19]利用RL来最小化边缘计算场景下的平均任务完成时间，并提出了一种基于反事实RL的分布式任务调度算法.

1.2   基于区块链的资源调度方法

近年来，不少学者开始研究如何将区块链融入到计算系统如云数据中心、边缘计算等. 区块链去中心化和防篡改的特点使得其对于分布式系统而言是一种十分有前景的解决方案. 不少研究工作都从不同角度展示了区块链对于分布式计算系统的价值^[20]. 例如，部分研究希望通过区块链来提升系统的可靠和安全性. 文献[21]提出了一种基于区块链的联邦学习应用交易平台FLEX. 该平台允许用户购买或者出售计算资源来训练自己的模型的同时保证数据隐私. 文献[10]提出了一种面向认知计算的区块链联邦学习框架. 其中，联邦学习在保护隐私的同时提供了高效的处理，而区块链实现了全分布式的资源管理. Cheng等人^[11]提出了一种资源议价和交易方法来优化边缘场景的计算资源分配并进一步用区块链来记录资源交易过程从而保证数据安全和隐私.

除了考虑安全因素以外，部分研究也希望通过区块链来实现可信的资源调度. 一般地，为了激励边缘节点参与到计算中，大多数计算系统都会采用激励机制来奖励那些贡献高的节点. 保证激励是可信的，即计算节点按照承诺提供相应的计算资源，系统在任务完成后为计算节点支付相应报酬^[20]. 文献[22]介绍了一种基于区块链的激励机制. 该方法通过维护一个连续的防篡改数据库来阻止边缘服务器篡改参与节点的信息. 文献[23]提出了一种基于区块链的边缘计算支持的物联网架构. 该架构设计了一系列部署在私有链上的智能合约以及一个基于异步优势Action-Critic （A3C）算法的资源调度机制. 文献[24]考虑了边缘场景下实时稳定的资源调度，并提出了一种横向区块链结构. 该结构中包含了上千个边缘数据节点，从而在提高链上数据记载效率同时实现跨链的数据共享.

文献[8]应用区块链来管理边缘节点资源调度. 文献[25]设计了一种基于区块链的CED计算结构. 区块链负责保证任务上传的安全性. Wu等人^[26]将CED场景下的资源分配建模为一个Lyapunov优化问题，其目标是最小化能耗和任务相应的时间. 通过求解这一问题，进一步设计了一种能耗效率的动态资源调度算法. 虽然文献[23-24]的策略考虑到将区块链融合到计算卸载中，但我们所提出的BCERA与之不同的是，BCERA中的区块链在数据记录、资源调度以及激励机制中都扮演着核心角色； BCERA还提出了一种改进的共识算法来允许区块链节点通过求解资源调度优化问题来实现共识；为了应对算力网络随机动态变化的计算资源和用户行为，本文采用多智能体强化学习的方法进行求解.

2.   系统概述

本节介绍BCERA的框架，BCERA是一种由区块链驱动的算力网络协同资源调度机制. 图1展示了BCERA的结构，它主要由3层组成：1）应用层包括运行在BCERA之上的各种网络应用程序，这些应用程序充当BCERA客户端，发布资源请求，并将任务卸载到算力网络中的计算单元. 2）区块链层在BCERA功能中起着核心作用，包括资源调度决策、资源管理和激励. 此外，区块链层还实现了改进的共识优化证明机制，通过优化BCERA的资源调度方案，使区块链能够竞争输出块的权利. 与区块链技术相结合，BCERA旨在提供可信、分布式、高性能的资源调度. 3）资源层维护计算单元信息，以支持BCERA的资源调度. 算力网络中的计算单元包括：1）计算能力稳定且强大，但资源消耗昂贵的数据中心或边缘计算服务器；2）移动或人携带的设备，提供有限和随机的资源.

图  1  BCERA框架

Figure  1.  BCERA framework

下载: 全尺寸图片 幻灯片

基于BCERA结构，本文定义了BCERA中的成员类型及其基本概念.

1）任务发布者. 应用程序或客户端通过指定其对资源的需求和QoS要求，将其任务卸载到算力网络中.

2）交易. 当客户端在BCERA中发出资源请求时，将生成一个包含资源和任务QoS要求的交易.分配给该任务的计算单元信息、结果、奖励也会记录到相应的交易中.

3）区块链节点. 区块链中的节点用于存储和处理交易信息. 类似于当前的区块链，区块链节点通过实现预先给定的目标来竞争出块.

4）计算单元. 贡献计算资源来处理资源调度的网络实体.

5）代理节点. 该实体为各种角色提供交互接口. 值得注意的是，代理将任务和计算单元信息转发到区块链. 其主要功能包括资源管理、资源调度和在区块链上部署激励机制. 代理可以是运营商提供的信任组件，也可以由多个实体协作实现.

6）奖励. 算力网络中有贡献的实体由区块链工作者和计算单元组成. 前者通过做出资源调度决策并记录事务而获得奖励，后者则通过使用其资源处理卸载任务而获得奖励.

3.   BCERA中的资源调度

本节将讨论BCERA中的资源调度问题. 首先给出了系统模型，其包括计算模型和通信模型. 资源调度问题可表述为MDP，特别地，由于算力网络本身的特性，调度问题是部分可观测的.

3.1   系统建模

3.1.1   通信模型

首先本文对BCERA做出4个假设：1）用户通过骨干链路和无线链路访问Cloud的计算资源；2）边缘计算服务器直接连接基站，其资源只能通过无线链路访问；3）客户端使用基站作为中继，从同一小区内的移动设备访问计算资源；4）系统时间是分片的，用${\cal{T}}=\{1,2, …, T\}$表示.系统在每个片内保持静态，不同片之间有系统状态会发生变化.

算力网络拓扑可以被建模成一个无向图$G(\mathcal{V}, \mathcal{E})$，其中$\mathcal{V}$和$\mathcal{E}$分别是节点和链接的集合. 设$V_{{\rm{u}}}, V_{{\rm{c}}}, V_{{\rm{e}}}, V_{{\rm{m}}}, V_{{\rm{r}}} \in \mathcal{V}$分别为任务发布者、云、边、端计算单元以及路由器的集合. 设$l(u, v) \in \mathcal{E}$表示节点$u, v \in v$之间的链路. 为了简化描述，将$l(u, v)$简化为$l$. 对于$\mathcal{E}$中的l，$c_{l}(t)$表示它在时隙t内的可用带宽. 考虑网络条件的动态性，将$c_{l}(t)$定义为区间$\left[0, c_{l}^{\max }\right]$上时隙t的随机变量，$c_{i}^{\max }$为l的容量.

设$b_{i}$和$x_{i}(t)$分别表示卸载任务i时需要传递的原始数据量和在时隙t内任务i的传输速率. 则有

其中$t_{0}$和$t^{\prime}$表示数据传输的开始时隙和结束时隙.$\Delta t$是t的时间长度.设$\overline{x_{i}}$表示平均传输速率，则有$b_{i}= \left(t^{\prime}-t_{0}\right) \Delta t \overline{x_{i}}$，传输延迟$\left(t^{\prime}-t_{0}\right) \Delta t$=$b_{i} / \overline{x_{i}}$.也就是说较高的平均传输速率可以减少原始数据的下载时间.在t期间，l的总体数据速率应在带宽限制之内，

其中$B_{l}(t)$表示使用链接l的任务集合. 式（2）约束可以用一个队长$V_{l}(t)$的虚拟队列模型来描述.这个虚拟队列表示等待在t传输的积压数据.队列到达速率是使用l的任务的总体数据速率，出速率可用带宽$c_{l}(t)$表示.$V_{l}(t)$的变化为

要使得链路l不发生拥塞，则$V_{l}(t)$必须稳定.

3.1.2   计算模型

回顾$V_{c},V_e,V_m$是算力网络中的计算单元，它们的可用计算资源由一个随机变量$F_{u}(t)$表示，并通过每秒CPU周期来衡量计算能力. 假设云计算和边缘计算服务器的计算能力是稳定的，即$F_{u}(t), u \in V_{c},V_e$. 而对于移动节点MDs来说，由于只能贡献空闲资源，因此提供的资源是动态的. 因此，$F_{u}(t), u \in V_{m}$是时隙t的随机变量. 对于每一个在时隙t生成的任务i，我们定义一个二元组$\left\{s_{i}(t), b_{i}\right\}$，其中$s_{i}(t)$表示处理任务i所需的计算资源， $b_{i}$是需要传递给计算单元的原始数据的大小. 假设计算单元在收到任务i的所有原始数据后开始执行任务i，则分配给节点u的任务i的任务处理延迟可以是交付延迟和执行时间的总和. 将在节点u等待处理的任务积压表示为时隙$Q_{u}(t)$. 队列输入为时隙t期间到达的任务对计算资源的总需求，出队列率为$F_{u}(t)$，$A_u(t)$为时隙t上由节点u处理的计算任务集合. 因此，$Q_{u}(t)$的动态可以描述为:

3.2   问题形式化描述

资源调度的主要目的是最小化任务执行的总体延迟和资源使用开销. 对于任何任务i，将执行延迟定义为处理时间和传输时间的总和：

其中$P_{i, u}(t)$为任务的处理时间. 对于任意计算节点u，单位资源使用的费率为${R}_{u}$，在u处处理任务i的收益可由$R_{u} s_{i}(t)$给出. 结合执行延迟和资源使用情况，定义任务执行的代价函数为：

其中$\alpha_{i} \in[0,1]$和$\beta_{i} \in[0,1]$是权重. 给定第1项执行延迟的维度为秒，令$\alpha_{i}$的维度为1/s来消掉第1项. 据此，资源调度优化问题：

该问题的目标是最小化系统运行期间生成的所有任务的代价函数，其中$G(t)$表示在时隙t内生成的任务的集合.约束$\text { C1 }$表示资源调度的决策应该避免网络拥塞.此外，该问题的在线方法可以通过求解t的无约束优化问题^[27]:

其中V是一个非负参数. 使用相同链路的计算单元的决策$x_{i}(t)$通过第2项耦合. 优化$x_{i}(t)$以使整体延迟最小化是很困难的，因为它不仅需要考虑i的代价函数，还需要考虑链路上中其他节点的决策. 算力网络的计算单元可能由不同的运营商维护，因此不能直接观察式（2）中要求的链路限制. 也就是说，对于调度器来说，知道每个链接l的$V_{l}(t)$是困难的，只能得到$D_{i}(t)$的估计：

3.3   RL方法求解问题

所提出的问题是一个时变优化问题，也就是动态规划问题，这使得传统的确定性优化方法，如凸优化，不适合这种情况. 此外，由于系统状态不可预测，对系统变化进行建模并不容易. 也就是说，基于模型的动态规划方法如回溯法等也不能直接应用于这些问题. RL方法通过与环境的相互作用来解决随机优化问题，并通过观察反馈来进行决策，因此对于这一类问题是最具有可行性的办法. 与传统的优化方法不同，RL方法通过根据系统变化调整决策策略来实现长期最优. 这种探索使得RL^[28-29]方法在随机环境中有效地搜索最优解.

因此，可以应用各种基于RL的方法来解决这个问题. 这里，本文将讨论如何使用Action-Critc（AC）网络来解决这种方法. 我们首先将问题重新表述为MDP：

定义1 优化问题（7）的MDP由多元组$\mathcal{M}=\{\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, b_{0}\}$表示，其中：

1）$\mathcal{S}$为状态空间. 我们用元组$\mathcal{S}=\{\mathcal{Q}, \mathcal{V}, \mathcal{C}, \mathcal{N}\}$来表示，其中$\mathcal{Q}, \mathcal{V}, \mathcal{C}, \mathcal{N}$是所有计算单元等待处理任务集合，$\mathcal{V}$为所有链接的虚拟队列长度的值集，$C$为所有链接的可用带宽的值集，$\mathcal{N}= \left|N_{c}\right|, \left|N_e\right|,\left|N_m\right|$ .

2）$\mathcal{A}$为动作空间. BCERA需要决定哪个节点卸载任务和任务的数据率.t处的动作可以用一个二元组$(\boldsymbol{w}(t), \boldsymbol{x}(t))$表示.$\boldsymbol{w}(t)$由$\left|V_{{\rm{c}}} \cup V_{{\rm{e}}} \cup V_{{\rm{m}}}\right|$个一维向量组成，每个向量${\boldsymbol{w}}_{j}(t)$对应一个运行在计算单元j上的任务i.${\boldsymbol{w}}_{j}(t)$的分量$a_{i j}(t)$定义为：

$\boldsymbol{x}(t)$是一个$|G(t)|$维向量， $\boldsymbol{x}(t)=\left\{x_{i}(t)\right\}_{{i} \in G(t)}$.

3）$\mathcal{R}$是即时奖励.根据（8）有：

由于直接观测到$V_{l}(t)$很困难，通过式（12）（13）（14）来近似得到即时奖励：

其中$\Delta x_{i}(t)=x_{i}(t)-c_{l}(t)$.

$D_{i}(t)$逼近

用V除以$g\left(\boldsymbol{w}_{i}(t), {x}_{i}(t)\right)$：

对于每个i，将V改写为向量$\boldsymbol{V}_{i}:=\left\{c_{l}\right\}_{l \in U_{i}(t)}$.将$g\left(\boldsymbol{w}_{i}(t), x_{i}(t)\right) / V$替换为

由于端到端时延可以通过多种网络测量方法进行观测，因此可以很容易地推导出式（15）近似的$r' \left(\boldsymbol{w}_{i}(t), x_{i}(t)\right)$.

4）$\mathcal{P}$为概率转移${Pr}\left(b | s, \left(\boldsymbol{w}_{j}(t), {x}_{j}(t)\right)\right)$，由于无法获得系统动态的完整信息，假设只能在云和边处观察动态的$Q_{u}(t)$. 由于端节点庞大的数量和隐私问题，不可能观察到所有移动节点的$Q_{u}(t)$. 相反，假设只能拥有单元内所有MDs的队列平均值. 此外，BCERA只能观察到端到端延迟.

通过AC方法来求解问题（7）. AC是一种RL模型，它包括2个神经网络：1个Actor和1个Critic网络. Actor是策略网络，它根据当前观察到的系统状态在每次t输出动作，Critic根据Actor和奖励学习Critic函数.

1）Actor. 令$\pi_{\theta}\left({\boldsymbol{w}}(t), {\boldsymbol{x}}(t) | S_{t}\right)$定义输出策略，其中$\theta$表示Actor网络的参数， $S_{t}$表示t处的状态.网络通过基于梯度^[30]的方法迭代更新参数$\theta$:

其中 $A^{\pi_{\theta}}\left(S_{t}, {\boldsymbol{w}}(t), {\boldsymbol{x}}(t)\right)$是优势函数 ，$A^{\pi_\theta}\left(S_{t}, \boldsymbol{w}(t), {\boldsymbol{x}}(t)\right)= Q^{\pi_\theta}\left(S_{t}, \boldsymbol{w}(t), {\boldsymbol{x}}(t)\right)-V^{\pi_\theta}\left(S_{t}\right)$ $Q^{\pi_\theta}\left(S_{t} \boldsymbol{w}(t), {\boldsymbol{x}}(t)\right)$为动作-值函数，$V^{\pi_\theta}\left(S_{t}\right)$ 定义如文献[31].

2）Critic. Critic网络使用TD（$\lambda$）方法近似优势函数$A^{\pi_{\theta}}\left({S}_{t}, {\boldsymbol{w}}(t), {\boldsymbol{x}}(t)\right)$，其网络参数$\theta_{c}(t)$更新为：

其中$\gamma$和$\alpha$是学习率， $\sigma\left(s_{t}\right)$是指示函数，如果$s=s_{t}$，$\sigma\left(s_{t}\right)=1$，否则$\sigma(s_t)=0$.

根据设计，在每个t处，AC通过执行迭代优化卸载决策，直到达到迭代条件：

1）Actor网络根据观察状态$S_{t}$和$A^{\pi_{\theta_c(t)}}\left(S_t, \boldsymbol{w}(t), {\boldsymbol{x}}(t)\right)$输出资源调度动作$\left(\boldsymbol{w}_{i}(t), {{x}}_{i}(t)\right)$.

2）Critic根据动作$\left({\boldsymbol{w}}_{i}(t), x_{i}(t)\right)$获得奖励 $r^{\prime}\left(\boldsymbol{w}_{i}(t), x_{i}(t)\right)$，并根据TD（$\lambda$）估计$A^{\pi_{\theta_c(t)}}(·)$.

4.   BCERA区块链设计

4.1   智能合约设计

在BCERA中，区块链^[28-29]在计算资源调度中起着关键作用.具体而言，BCERA的区块链可以实现的功能为：1）维护算力网络中资源提供者的信息；2）验证并记录资源调度信息；3）BCERA的资源分配管理；4）根据任务完成情况进行奖惩分配.BCERA通过智能合约来实现这些功能，智能合约是一种基于区块链的分布式可信协议，设计的智能合约为：

1）注册合约. 为计算单元创建 “公钥”，这是节点的唯一全局标识，可用于加密发送到对应用户的消息，以实现安全通信.一旦节点调用了这个智能合约，它还会定期将自己的资源状态更新到区块链.

2）任务发布合约. 当客户向BCERA提交任务卸载请求时，将调用该合约创建一个交易来记录任务信息，包括资源和QoS要求等. 任务信息是由一个六元$S=\{T I D,\; R e q ,\; d u r, \; re (T I D), \;Q u a(T I D), \;com\}$构成，其中TID是任务的唯一ID，Req是CPU频率、存储空间等资源需求的细节，dur是持续时间，re（TID）是完成任务的奖励，Qua （TID）是任务处理的延迟约束等QoS要求，com用于指示任务是否完成.

3）资源调度合约. 在每个t期间，BCERA根据共识机制生成的资源调度方案将任务分配给计算节点，分配给每个任务i的节点信息将写入任务i的交易中.

4）奖励合约. 当节点完成任务或达到资源提供期限时，奖励合约将根据BCERA激励机制决定是否将奖励分配给计算节点.

根据智能合约的功能，参与计算任务卸载的计算节点、任务发布者等通过区块链上的智能合约就能够实现任务卸载而不需要直接通信或者可信的第三方，并在区块链节点的协助下确定任务调度策略，因此实现了可信的协同任务卸载.

4.2   资源管理

BCERA中的任务调度流程如图2所示，BCERA中计算资源具有地理分布和随机提供的特点. 因此，能够及时更新节点资源状态的资源进行管理，对于资源调度的性能至关重要. 在时隙t内，当计算单元j加入请求时，BCERA调用注册合约生成ID，并记录CPU频率、内存大小等资源信息. 区块链维护t内生成的区块中的信息和记录，以确保提供可靠的资源. 一旦节点加入BCERA，节点将在每个时隙t更新可用资源，以确保资源调度方案始终能够根据最新的资源状态做出决策. 当节点需要退出BCERA时，将发送退出通知，注册合约将向区块添加新信息，将计算单元j的可用资源设置为零.

图  2  BCERA工作流程

Figure  2.  Workflow of BCERA

下载: 全尺寸图片 幻灯片

4.3   资源调度流程

BCERA中每个时隙t的资源调度划分为3个阶段.

1）观察阶段. 区块链中的优化器观察到达队列中的任务和每个任务的资源需求和原始数据量i. 同时，BCERA获取系统状态包括每个计算单元的承载任务 $Q_{u}(t)$、计算能力$F_{u}(t)$、计算节点与任务发布者之间的端到端延迟. 在实际应用中，对于一个客户端i，到最近的基站的延迟是$d_{i}^{s}(t)$，而计算节点j到同一个基站的延迟是$d_{j}^{e}(t)$. 本文使用$$d_{i}^{s}(t)+d_{j}^{e}(t)$来近似$D_{i j}(t)$.

2）决策阶段. 根据状态信息，BCERA中的区块链节点调用RL模型输出资源调度动作，并就最优方案进行共识. 该协议的细节是由提出的共识机制——最优性共识（POO）算法来完成的，这将在4.4节中详细描述.

3）卸载阶段. 代理节点根据任务分配$w_{i}(t)$将任务分配给计算单元，并将$x_{i}(t)$通告任务发布者. 每个发布者以数据速率$x_{i}(t)$上传任务的原始数据. 一旦计算节点接收到原始数据，它们将开始处理任务，并在任务完成后返回结果.

4.4   BCERA共识算法POO

BCERA与现有区块链驱动计算平台的主要区别在于，BCERA将资源调度优化纳入共识机制^[28]，在支持高性能资源调度的同时，尝试重用区块链所拥有的计算和通信资源.为了实现这一目标，BCERA提出了一种共识机制，即最优性共识（proof of optimum， POO），POO包含4个步骤：

1）优化器选择.与传统的DPoS类似，在时隙t， POO中的区块链节点根据帐户余额选出一组优化器$\left\{o_{b}\right\}_{b \in w(t)}$.对于在公链上部署BCERA的情况，只包括少量在优化过程中具有较高利益的节点，因为它们在行为上可以被信任，并且更愿意为系统贡献它们的资源.对于个体无信任问题的私有链或联盟链，所有个体都可以参与资源调度决策.另外，为了决策的实时性，需要设定一个提交结果的截止日期.

2）资源调度优化. 每个优化器o的输入来自$Q_{u}(t)$，$F_{u}(t)$，$D_{i j}(t)$，并使用策略$$\pi_{\theta}\left({\boldsymbol{w}}(t), {\boldsymbol{x}}(t) | S_{t}\right)$输出资源调度决策$\left\{\boldsymbol{w}_{i}(t)\right\}_{i \in G_{(t)},},\left\{x_{i}(t)\right\}_{i \in G_{(t)}}$.另外值得注意的是，考虑到系统规模大，卸载动作提交截止日期的严格限制，能力有限的优化器可能无法获取整个系统的状态，只能使用部分状态信息来优化卸载.具有强大计算和通信能力的优化器可能提供更好的资源调度方案，因为可以在给定时间内尽可能多地探索环境信息.

3）Leader选择. o得到运算结果，广播$\left\{\boldsymbol{w}_i(t)\right\}_{i \in G(t)}, \left\{x_i(t)\right\}_{i \in G(t)}$至其他优化器. 如果$\left\{\boldsymbol{w}_i(t)\right\}_{i \in G(t)}, \left\{x_i(t)\right\}_{i \in G(t)}$与截止日期不匹配，为了竞争的公平性，结果将被丢弃. 当获取其他优化器p得到的结果$\left\{\boldsymbol{w}_i^p(t)\right\}_{i \in G(t)},\left\{x_i^p(t)\right\}_{i \in G(t)}$，o首先检查$\left\{\boldsymbol{w}_i(t)\right\}_{i \in G(t)}, \left\{x_i(t)\right\}_{i \in G(t)}$满足${\boldsymbol{w}}_{i}(t) < \mid G(t)$.如果满足，添加$\left\{\boldsymbol{w}_i^p(t)\right\}_{i \in G(t)},\left\{x_i^p(t)\right\}_{i \in G(t)}$到可行解列表；否则，放弃. o选择奖励函数$\left\{{\boldsymbol{w}}_{i}^{p}(t)\right\}_{i \in G(t),} \left\{x_{i}^{p}(t)\right\}_{i \in G(t)}$排在可行列表的第一位的节点，并投票给它. 因此，性能最好的优化器将被选为内的Leader. 对于所有区块链节点都没有在规定时间内得到运算结果这一特殊情况，出块的任务由上一时隙的Leader负责.

4）区块的创建. 在优化器p被选择为Leader之后，p构建t内生成的区块. 每个区块包含M交易项，一旦达到大小限制，将生成包含后续交易的新区块. 新区块${ block }_i$将被广播到其他优化器来验证块中的交易. 如果大多数优化器投票认可，那么${ block }_i$将被认可为区块链；否则，拒绝. 具体来说，如果超过2/3的优化器同意，${ block }_i$被接受，同时奖励s将被分配给优化器. Leader p获得一半的奖励，其余的则均匀地分配给其他优化器.

算法1. POO共识算法.

/*优化器选择*/

① 　for each w in blockchain：

②　　投票选择m个节点为优化器；

③　　计算w的票数；

④　end for

⑤　根据节点得票数进行降序排序，并取前m　　　　　个作为优化器；

/*Leader选择*/

⑥　for each optimizer o:

⑦　通过$\pi_\theta\left(\boldsymbol{w}(t), {\boldsymbol{x}}(t) \mid Q_u(t), F_u(t), D_{i j}(t)\right)$生成动作；

⑧　for each received action:

⑨　　if $\left\{\boldsymbol{w}_i(t)\right\}_{i \in G(t)},\left\{x_i(t)\right\}_{i \in G(t)}$没超时

⑩　　　查看是否可行；

⑪　　　 if ${\boldsymbol{w}}_{i}(t) < |G(t)|, x_{4}(t) < x_{\max }(t)$

⑫　　　　将$\left\{\boldsymbol{w}_i(t)\right\}_{i \in G(t)},\left\{x_i(t)\right\}_{i \in G(t)}$添加到可行列　　　　　　　　表中；

⑬　　　 end if

⑭　　　根据$r^{\prime}\left(\boldsymbol{w}_{i}(t), x_{i}(t)\right)$对可行列表中的节点　　　　　　　 进行降序排序；

⑮　　　选$r'\left(\boldsymbol{w}_i^p(t), x_i^p(t)\right) > r'\left(\boldsymbol{w}_i^q(t), x_i^q(t)\right), \forall q$对应　　　　　　　的节点作为Leader；

⑯　　end if

⑰　end for

⑱ end for

⑲ /*出块和共识*/

⑳ for each block_i：

㉑　计算承认block_i的票数；

㉒　if 超过2/3的优化器承认block_i

㉓　　接受block_i作为区块上链；

㉔　　将50%的s的奖励转给Leader；

㉕　　将50%的s/（M−1）的奖励转给优化器；

㉖　else

㉗　　丢弃block_i；

㉘　end if

㉙ end for

5.   激励机制

由于算力网络包含大量第三方的资源，需要激励机制来保证参与者诚实、积极地参与计算资源贡献^[32-33]. 在激励机制中，对资源调度参与者的奖励或惩罚是以他们的贡献来衡量的. BCERA激励机制主要由2部分组成：1）奖励.设定任务发布者使用资源的奖励. 2）处罚. 对未能完成计算任务或提供虚假信息的节点予以处罚.

设${\boldsymbol{w}}_{i}^{*}(t), x_{i}^{*}(t)$为POO算法得到的最优解，对计算节点，定义代价因子为$C_{j t}\left({\boldsymbol{w}}_{i}^{*}(t), x_{i}^{*}(t)\right)$， $R_{j}(t)$为卸载任务i到j在t的代价. $C_{jt}\left({\boldsymbol{w}}_{i}^{*}(t), x_{i}^{*}(t)\right)$为一个${\boldsymbol{w}}_{i}^{*}(t), x_{i}^{*}(t)$的线性或者凸函数. 假设计算节点是理性的，那么激励机制会使$R(t)$不低于处理任务i的成本 $C_{j t}\left(x_{i}^{*}(t), {\boldsymbol{w}}_{i}^{*}(t)\right) < R_{i}(t)$. 设$C_{t}(·)=\max\limits _{i \in G(t)} C_{i}(·)$，定义t总的回报为

以$G(t)$ 为单位的计算单元根据其提供资源的容量共享$R(t)$的收益. 通过式（19）确定每个任务i的奖励：

根据式（19），有${R}_{i}(t) \geq C_{j t}\left({\boldsymbol{w}}_{i}^{*}(t), x_{i}^{*}(t)\right)$. 这表明为任务i提供资源是正收益的. 也就是说，奖励方案是个体理性的. 基于上述资源定价和奖励计算，本文提出的激励机制为：

1）freezing. 一旦发布者发出任务卸载请求，将记录并冻结向代理节点支付$R_{i}(t)$的款项.

2）rewarding. 发布者确认任务是否成功完成. 如果任务完成，奖励$R_{i}(t)$将自动解锁并转移到相应计算节点账户.

3）penalizing. 算力网络中的计算单元可以是便携设备，因此在提供资源时可能会违背承诺，从而损害系统性能和可持续性. 本文引入了“押金”的概念. 在节点j确认处理分配的任务后，j根据其提供资源和可靠性. 如果节点j完成任务，押金将被退回到j的账户；否则，保证金将被没收，以补偿其他参与节点的损失. 计算j处理i的押金， $D_{i}(t)=\gamma C_{j t}\left(x_{i}^{*}(t), {\boldsymbol{w}}_{k}^{*}(t)\right) /(\hbar(j))$，$\hbar$：随机变量.

6.   实　　验

基于区块链的一个原型系统来进行实验，区块链由4个worker组成，这些worker在一台服务器上实现（Intel i7-11700k, 8核1.7 GHz/32 GB）. 在每个块中，指定块ID、生成的时间戳、交易数量和章节IV中描述的交易信息. 除非另有说明，否则每个区块中的交易数量设置为10000. 每隔3 s，区块将被共识协议添加到区块链. 基于Pytorch构建了RL环境. RL模型采用卷积神经网络（CNN）作为模型. 在第一个卷积层之后是maxpooling层. 卷积层的输出通道分别为25，48，256，64，16. 内核大小层分别为9，2，7，3，3，3，4. 最后一层是完全连接的，并输出具有概率分布的动作. 为了模拟工人之间的差异，超参数包括学习率和效用函数的权重参数都是不同的. 本文进一步考虑了4种不同的RL方法：

1）DQN（deep Q network）. 该方法为每个客户端配备2个网络.${ Eval }_{\rm {net }}$估计状态动作值，${ Target }_{ \rm{net }}$维护${ Eval }_{\rm {net }}$的副本，以计算下一个状态值函数. 一个内存缓冲区缓存前200个动作. Batch大小设置为32. ${ Eval }_{ \rm{net }}$和${ Target }_{ \rm{net }}$之间的延迟是5个迭代.

2）AC（actor-critic network）. 该方法采用AC网络. Critic使用TD算法输出当前状态值函数，Actor根据Critic输出最小化动作的优势来输出动作分布.

3）A3C（asynchronous advantage actor-critic）.该方法通过引入并行处理扩展AC. 学习代理调用4个线程来训练模型，它们协作更新集成训练结果的分片模型.

4）MADQN （Multi-agent DQN）.该方法由4个学习agent组成，每个agent使用DQN网络独立生成策略.

为了进一步测试资源调度性能，本文将基于我们之前设计的协同视频转码平台的转码来测试资源调度性能. 每个设备都可以在这个平台上为视频转码贡献资源. 用户生成视频转码请求并决定卸载哪个计算节点. 然后将视频数据下发到目标计算节点. 转码完成后，转码内容将返回用户. 该平台由1台服务器作为云（Intel Xeon Platinum 8163, 8核2.5 Ghz/64 GB）、3台边缘服务器（Intel i7-11700 k, 8核1.7G Hz/32 GB）、4台笔记本电脑（Intel i7-7700 k, 4核4.25 Ghz/16 GB, AMD Ryzen 5，4核3.2 GHz/16 GB, Intel i7-10750 H, 6核2.6 GHz/16 GB, Intel i7-10510 U, 4核1.8 Ghz/16 GB）作为MDs和用户组成. 操作系统是CentOS 7，使用FFmpeg作为转码工具. 每个节点安装一个资源监视器来记录资源的变化. 有线链路带宽为100 Mbps. 转码视频内容的长度是一个随机变量$U[2,10]$，变量$U[a,b]$表示[a, b]范围内的均匀分布. 原始视频的转码比特率集包括1080 p（60 fps），1080 p（30 fps），720 p（60 fps），720 p（30 fps），480 p（30 fps）.

发布者在每个时隙随机生成若干个不同计算资源需求和视频大小的任务. 生成的任务数量遵循泊松分布$\lambda_{1}$. 生成2个连续任务之间的时隙数量遵循$U[5,20]$的均匀分布.

为了测试本文提出的资源调度优化的通用性，我们首先评估了4种RL方法DQN、A3C、AC、MADQN来解决该问题时的性能. 所研究的指标包括训练期间的损失方差（Loss值）和测试期间的单元处理延迟（unit delay, UD）.

1）Loss值变化. 从图3中可以看出，所有解都经历了快速下降的趋势，然后进入稳定阶段，说明算法收敛了. 造成这种现象的原因是学习智能体在一开始并没有对系统动态的先验知识，而是通过估计不同状态下的动作值来改进策略. 一旦学会了值函数或q值，智能体的策略就会收敛，使曲线稳定. 所有这些曲线都在2500 s附近收敛，表明它们在资源调度问题上具有相似的性能. 不同的是基于AC的方法的Loss值在900 s后先呈上升趋势，后呈下降趋势. 同时，DQN和MADQN的Loss值在训练过程中持续下降. 因此，在训练时间不足的情况下，优先使用DQN和MADQN进行资源调度.

图  3  训练过程中Loss值变化

Figure  3.  Loss variance during the training

下载: 全尺寸图片 幻灯片

2）测试过程中的单位延迟（UD）. 本文将UD定义为处理任务的一个单位原始数据的延迟. 通过600 s的数据集测试不同解决方案的UD，结果如图4所示. 从图4中可以看出，A3C是所有方案中时延最低的，大多数情况下其性能都优于其他方案. A3C的优点是AC模型总是比平均值更好地寻找动作. 此外，A3C使用4个不同的过程来探索同时实现更好性能的环境. 其他3个解决方案在性能上接近. DQN对应的曲线最初高于AC和MADQN， 300 s后相互变得非常接近. 基于此分析可以得出，所有这些RL方法都可以应用于解决CED资源调度问题. 因此，区块链工作者可以任意选择RL方法来输出卸载策略，因为很难找到在所有情况下都占主导地位的RL方法.

图  4  测试过程中的时延变化

Figure  4.  Delay variance during the test

下载: 全尺寸图片 幻灯片

3）交易验证延迟（transaction verifying delay, TVD）. TVD定义为向区块链发送和添加事务之间的时间间隔.图5、图6显示了2种不同到达模式下的平均TVD.

图  5  交易处理时延：动态到达率

Figure  5.  Transaction verifying delay: Burst arrival

下载: 全尺寸图片 幻灯片

图  6  交易处理时延：平稳到达率

Figure  6.  Transaction verifying delay: Stable arrival

下载: 全尺寸图片 幻灯片

①动态到达模式. 在5~15 s到达率（图中柱状）相对较高，达到8000，并在其余模拟时间内保持稳定；②稳定的到达模式. 在试验过程中，在大多数情况下到达率稳定在2800.

在动态到达模式下，3种方法的TVD都经历了10 s的上升后下降到5 s. 原因是5~15 s的到货率很高，超过了交易处理率. 因此，待处理事务的数量会增加，从而推高TVD. 当事务到达率低于处理率时，待处理积压减少. 在稳定模式的测试期间，所有曲线都在2 s附近波动. 造成这种波动的原因是，一旦包含的交易数量等于10000或达到3 s生成截止日期，每个区块就会被添加到区块链中. 因此，添加到几乎已满或接近构建截止日期的区块中的事务可以具有较低的延迟. 除此之外，由于工作者使用的RL网络经过训练，3种共识算法在TVD中具有相似的性能，并且与块处理延迟相比，优化过程相对较快.

4）资源调度性能. 基于设计的协同资源调度平台，将BCERA与我们之前提出的资源调度算法AGO^[1]和随机策略进行了比较. AGO基于随机网络优化框架确定资源调度策略，随机策略以均匀分布的方式选择节点卸载转码请求. 图7（a）（b）显示不同类型CPU的平均CPU和内存使用率. 从图7（a）（b）中可以看出，BCERA倾向于将调用端节点资源， AGO倾向于Edge服务器的资源使用. 这是因为我们提出的问题考虑了任务的处理延迟和传输能力. 严重依赖边缘服务器可能会使订阅者和边缘服务器之间的链接拥塞，从而增加整体延迟. 这一结论可以通过观察图7（c）得出，其中BCERA与AGO相比在边缘有更低的延迟. 此外，BCERA还节省了压力边带宽. 如图7 （c）所示，随机策略将任务均匀分配到2 ~ 3种类型的计算节点，因此在云端具有最高的处理延迟和吞吐量，这对于时间敏感的计算任务来说是不可取的.

图  7  资源调度性能

Figure  7.  Resouce allocation performance

下载: 全尺寸图片 幻灯片

7.   结　　论

本文提出了一种基于区块链的算力网络计算资源调度方案，即BCERA.首先给出BCERA的定义，它主要由应用层、区块链层和资源层组成.然后，将算力网络资源调度建模为马尔可夫决策过程，并说明如何使用强化学习方法来解决这个问题.针对BCERA的任务发布、资源调度和资源管理功能，本文进一步设计了4种智能合约，并给出了POO的详细设计.这种新颖的共识机制使每个区块链工作者能够通过解决制定的POMDP就输出块达成一致.

此外，本文还提供了一个激励机制，以确保诚信，并鼓励CUs为BCERA贡献资源.为了评估BCERA的性能，基于原型系统进行了一系列数值评估和模拟测试.特别地，在一个商业化的区块链平台BROP上实现了我们的设计，并在现实中测试了它的性能.仿真结果表明，提出的BCERA在使用POO时提高了资源利用率并减少了整体处理延迟.上述实验结果还表明，本文所提出的算法在任务处理时延、节点负载均衡以及资源利用率方面都优于现有的计算任务卸载方案.

作者贡献声明：衷璐洁提出了算法思路、实验方案以及论文的撰写；王目进行了方案优化和实现以及论文的撰写.