使用深度强化学习算法求解的基于 Stackelberg 博弈模型的雾计算典型场景建模.zip

# 使用深度强化学习算法求解的基于 Stackelberg 博弈模型的雾计算典型场景建模 ## 研究背景 ### 背景来源 ​ 本文研究内容将作为 OpenRaaS 的一部分，目的是探讨适合于 OpenRaaS 的调度算法。由于 OpenRaaS 环境本身的复杂性，以及其研究领域的受限性，我们希望在一个更加泛用、简单的环境内开展调度算法的设计工作。该应用环境可以与 OpenRaaS 的背景设计存在偏差，但一些基本要点必须与之吻合，尤其是作为核心的双决策主体问题。 ### 基本要点 ​ 按照 OpenRaaS 的调度流程，环境设计的过程中需要满足以下特性： 1. 两个决策主体——leader + follower - leader 负责选择 follower，并为 follower 调配一个资源池 - follower 负责执行具体的任务，该任务由来自它自己以及资源池中的资源来完成 2. 核心问题——partial observation - leader 只有局部视野，它不清楚 follower 与资源池中具体某项资源的网络链路关系 - follower 具有更多的视野，但它不能总是向 leader 汇报 3. 性能指标——多个 QoS 值 - 受到 follower 自身条件、follower 的决策模型、从资源池中选择的 host machine 的影响 4. 优化目标——基于这些 QoS 值的 social welfare - social welfare = (unity-price) + (price-cost) 是 leader 的目标 5. 决策变量——follower 能观测到的资源单价，或者资源池内容 - price-cost 是 follower 的目标，所以可以通过 price 来控制 follower 的决策 - 本质上是控制 follower 能够看见的每个 QoS 指标的权重，它在策略中会根据这些权重估算目标 - follower 从资源池中选择资源，所以控制资源池内容能够控制 follower 的决策 ### 问题设计 ​ 我们选用的模型是雾计算。其中，参与计算的节点都是边缘侧的服务设备，既可以是自愿提供算力的可信第三方设备，也可以是无线接入网中（RAN）基站上的服务器。雾计算致力于池化这些异构的用户侧设备，因此一种有效的雾计算方案是通过虚拟机或容器来利用这些异构的资源：当任务到来时，被分配的服务器将根据任务内容从云盘（另一个设备）中获取能够支持该服务的虚拟机（VM），整个过程类似数据中心对 on-rack 设备的池化。这个过程需要两类节点：计算节点与存储节点。前者就是参与雾计算的节点，负责提供边缘算力；后者既可以是边缘节点，也可以是云数据中心，负责为计算节点提供 VM。在这个模型中，我们采用资源即服务（RaaS）的方法对资源进行池化，也就是每个设备只关心自己提供的资源类型与资源量，而不关心具体提供的服务内容。因此，调度与计价都被有效简化。 ​ 我们提出一种基于雾计算的合作边缘计算（CEC）方案，其中边缘设备的资源是池化的，以地理空间上的小区为单位进行管理。在每个小区中存在一个 leader 节点 $l$，它负责管理与调度池化的资源。当一个任务到来时，它将被用户所在小区的基站接收，并转发给 $l$，然后 $l$ 根据任务内容在小区内选择出合适的计算和存储资源来提供服务。我们认为任务不能被分配到其他的小区去，因为过远的距离将影响边缘计算的低延迟性能。在这个方案中，参与雾计算的边缘设备因为其移动性和无线链路的不确定性，由 $l$ 动态维护所有节点间的链路信息实际上是不可取的。因此 $l$ 无法对 QoS 目标进行精确量化，完全依靠 $l$ 进行调度可能导致服务质量的下降。因此，$l$ 只选择一个 follower 节点 $f$ 作为计算节点，并选出一批合适的存储站点 $D$ 告知 $f$，之后交由 $f$ 自行决定最佳的 $d \in D$。 ​ 为了简化建模，我们采用标准的计算卸载任务，并根据任务完成时间来决定用户的权益（utility）。该建模中采用三个 QoS 指标：传输速度，服务延迟，与计算性能。在计算卸载的场景下，它们可以共同反映在任务从发起到完成的时间间隔上。于是，多 QoS 本质上回到了单目标： 1. **总时间 = 任务上传时间 + VM 加载时间 + 任务处理时间 + 结果下发时间** 2. 任务上传时间 = task size / 用户-计算节点带宽 + 用户-计算节点延迟 3. VM 加载时间 = VM block size / min(计算-存储节点带宽, 存储介质读取速度) + 计算-存储节点延迟 4. 任务处理时间 = task 所需 cycles 数 / 计算节点的频率 5. 结果下发时间 = result size / 用户-计算节点带宽 + 用户-计算节点延迟 ​ 其中，因为 VM 是挂载到 $f$ 上的，任务到来时 $f$ 不需要下载全部的 VM，而是“即用即取”。它会以数据块（block）的形式依次缓存接下来将使用的内容，因此只有在请求第一个数据块时需要等待其加载。对于 $f$ 来说，无论任务上传还是 VM 加载，都是占用的下载带宽，因此二者无法简单地同时进行，在此设置为顺序加载。 ​ 由于本文探讨的是 leader 与 follower 博弈与合作的问题，因此不强调 $l$ 选择 $f$ 的策略。在此，我们采用一个最朴素的贪心策略进行 $f$ 的选择：从用户所在小区内选择一个能够立即执行该任务的、根据局部观测信息（partial observation）有最大目标估计值的计算节点。 ## 基础模型 ### 系统设计 ​ 当编号为 $u_i$ 的用户设备发起编号为 $i$ 的任务时，任务信息 $B_i=\{i,t_i,s_i,w_i,sid_i,b_i(*)\}$ 将被递交给其所在区域的 leader 节点 $L(u)$。其中 $t_i$ 是任务到达时间，$s_i$ 是本地上传数据大小，$w_i$ 是完成该任务需要的 CPU 周期数，$sid_i$ 表示该任务的类型，对应一个能够提供该类服务的 $vm_i$，$b_i(*)$ 是期望价值函数。函数 $R(sid_i)=vm_i$ 用于检索该任务对应的虚拟机编号（若无特别说明，本文默认所有编号从 1 开始）。值得注意的是，$b_i(*)$ 并不是定价函数 $v_i(*)$，它代表的是用户心中的估价，在此我们采用线性函数 $b_i(\Delta t) = \beta_i - \alpha_i \Delta t$ 的形式。随后，$l$ 直接在小区内搜索出一个满足要求的 $f_i$，并将能够提供 $v m_i$ 的存储节点 $D_i$ 集合下发给 $f_i$。$f_i$ 根据自身的策略选出一个 $d_i \in D_i$，处理完任务后，将大小为 $e_i$ 的计算结果返还给用户 $u_i$。 ​ 对于一个编号为 $f$ 的计算节点，它的计算能力 $c^f$ 表示其 CPU 频率，按照使用的 CPU 周期数进行计价，单价为 $p_c^f$。其链路延迟 $lt^f$，分配给计算相关文件缓存的上下行链路带宽 $bw^f$，按照使用时间计价，单位价格为 $p_{link}^f$。其可用于缓存 offloaded data 与 VM 的存储空间大小 $S^f$，按照占用的量与时间计价，单位价格为 $p_s^f$。对于一个编号为 $d$ 的存储节点，它会维护一个集合 $VM^d$ 存放它本地持有的虚拟机编号，对外提供出口链路与存储介质两种资源，这些资源有链路延迟 $lt^d$，分配给 VM 上传的链路带宽 $bw^d$，存储介质读取速度 $rd^d$。它们都按照使用时间进行计价，因为二者同时进行，总计单位价格为 $p_{vm}^d$。 ​ 于是任务完成时间 $\Delta t(i,f^*,d^*)$ 可以被表示为： $$ \begin{aligned} \Delta t(i,f^*,d^*) &= t_u(i,f^*) + t_{vm}(i,f^*,d^*) + t_p(i,f^*) + t_d(i,f^*), \\ t_u(i,f^*) &= \frac{s_i}{bw^{uf^*}} + lt^{uf^*}, \\ t_{vm}(i,f^*,d^*) &= \frac{block_1^{vm_i}}{min(bw^{f^*d^*},rd^{d^*})} + lt^{f^*d^*}, \\ t_p(i,f^*) &= \frac{w_i}{c^{f^*}}, \\ t_d(i,f^*) &= \frac{e_i}{bw^{uf^*}} + lt^{uf^*}, \end{aligned} $$ 其中，$f^*$ 是任务 $i$ 所选的计算节点，$d^*$ 是 $f^*$ 选择的存储节点，$t_u(i,f^*)$ 代