本文研究内容将作为 OpenRaaS 的一部分，目的是探讨适合于 OpenRaaS 的调度算法。由于 OpenRaaS 环境本身的复杂性，以及其研究领域的受限性，我们希望在一个更加泛用、简单的环境内开展调度算法的设计工作。该应用环境可以与 OpenRaaS 的背景设计存在偏差，但一些基本要点必须与之吻合，尤其是作为核心的双决策主体问题。
按照 OpenRaaS 的调度流程，环境设计的过程中需要满足以下特性：
- 两个决策主体——leader + follower
- leader 负责选择 follower，并为 follower 调配一个资源池
- follower 负责执行具体的任务，该任务由来自它自己以及资源池中的资源来完成
- 核心问题——partial observation
- leader 只有局部视野，它不清楚 follower 与资源池中具体某项资源的网络链路关系
- follower 具有更多的视野，但它不能总是向 leader 汇报
- 性能指标——多个 QoS 值
- 受到 follower 自身条件、follower 的决策模型、从资源池中选择的 host machine 的影响
- 优化目标——基于这些 QoS 值的 social welfare
- social welfare = (unity-price) + (price-cost) 是 leader 的目标
- 决策变量——follower 能观测到的资源单价，或者资源池内容
- price-cost 是 follower 的目标，所以可以通过 price 来控制 follower 的决策
- 本质上是控制 follower 能够看见的每个 QoS 指标的权重，它在策略中会根据这些权重估算目标
- follower 从资源池中选择资源，所以控制资源池内容能够控制 follower 的决策
- price-cost 是 follower 的目标，所以可以通过 price 来控制 follower 的决策
我们选用的模型是雾计算。其中，参与计算的节点都是边缘侧的服务设备，既可以是自愿提供算力的可信第三方设备，也可以是无线接入网中（RAN）基站上的服务器。雾计算致力于池化这些异构的用户侧设备，因此一种有效的雾计算方案是通过虚拟机或容器来利用这些异构的资源：当任务到来时，被分配的服务器将根据任务内容从云盘（另一个设备）中获取能够支持该服务的虚拟机（VM），整个过程类似数据中心对 on-rack 设备的池化。这个过程需要两类节点：计算节点与存储节点。前者就是参与雾计算的节点，负责提供边缘算力；后者既可以是边缘节点，也可以是云数据中心，负责为计算节点提供 VM。在这个模型中，我们采用资源即服务（RaaS）的方法对资源进行池化，也就是每个设备只关心自己提供的资源类型与资源量，而不关心具体提供的服务内容。因此，调度与计价都被有效简化。
我们提出一种基于雾计算的合作边缘计算（CEC）方案，其中边缘设备的资源是池化的，以地理空间上的小区为单位进行管理。在每个小区中存在一个 leader 节点
为了简化建模，我们采用标准的计算卸载任务，并根据任务完成时间来决定用户的权益（utility）。该建模中采用三个 QoS 指标：传输速度，服务延迟，与计算性能。在计算卸载的场景下，它们可以共同反映在任务从发起到完成的时间间隔上。于是，多 QoS 本质上回到了单目标：
- 总时间 = 任务上传时间 + VM 加载时间 + 任务处理时间 + 结果下发时间
- 任务上传时间 = task size / 用户-计算节点带宽 + 用户-计算节点延迟
- VM 加载时间 = VM block size / min(计算-存储节点带宽, 存储介质读取速度) + 计算-存储节点延迟
- 任务处理时间 = task 所需 cycles 数 / 计算节点的频率
- 结果下发时间 = result size / 用户-计算节点带宽 + 用户-计算节点延迟
其中，因为 VM 是挂载到
由于本文探讨的是 leader 与 follower 博弈与合作的问题，因此不强调
当编号为
对于一个编号为
于是任务完成时间 $\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^)$ 代表任务上传时间，$t_{vm}(i,f^,d^)$ 是第一个 VM 区块的加载时间，$block_1^{vm_i}$ 是该区块的大小，$t_p(i,f^)$ 是任务处理时间，$t_d(i,f^)$ 是结果下发时间。$bw^{uf^}$、$lt^{uf^}$ 是用户与计算节点间链路的带宽与延迟，$bw^{f^d^}$、$lt^{f^d^}$ 是计算与存储节点间链路的带宽与延迟。注意，对于节点
- p_s^{f^} \cdot s_i \cdot [t_{vm}(i,f^,d^) + t_p(i,f^)] + p_s^{f^} \cdot b\overline{loc}k^{vm_i} \cdot t_p(i,f^) + p_s^{f^} \cdot e_i \cdot t_d(i,f^),
$$
这里的
$b\overline{loc}k^{vm_i}$ 表示$vm_i$ 平均每个区块的大小，我们假定 $f^$ 用完一个区块就会立即释放。对于存储节点 $d^$，由于本模型只涉及 VM 的下载而不涉及对缓存内容的调度，在此我们并不关心它的具体存储开销，因此其完成任务$i$ 的成本被表示为： $$ Cost_2^{task}(i,f^,d^) = p_{vm}^{d^} \cdot [t_{vm}(i,f^,d^) + t_p(i,f^)]. $$ 任务$i$ 的总成本 $Cost^{task}(i, f^, d^) = Cost_1^{task}(i, f^, d^) + Cost_2^{task}(i, f^, d^)$。
令一个时隙（slot）大小为
令给定区域内有
\sum_{j \in N_m} \sum_{t \in T} Cost^{slot}(j, t), $$
其中，决策变量是三个指示变量：$x_i \in {0, 1}$ 指示是否接受任务
\forall i \in [1,N_i],\ \forall k \in N_m,\quad &x_{ik}^d \cdot R(sid_i) \in {0} \cup VM^k, \
\forall i \in [1,N_i],\ \forall j \in N_m,\quad
&x_{ij}^f \cdot [s_i + b\overline{loc}k^{R(sid_i)}] \le S^j,\
\forall a,b \in [1, N_i],\ \forall j \in N_m,\quad &x_{aj}^f \cdot t_a \ge x_{bj}^f \cdot [t_b + \sum_{k \in N_m}x_{ik}^d \Delta t(b, j, k)] \ \bigcup \ &x_{bj}^f \cdot t_b \ge x_{aj}^f \cdot [t_a + \sum_{k \in N_m}x_{ik}^d \Delta t(a, j, k)],\
\forall i \in [1,N_i],\quad &x_i = \sum_{j \in N_m}x_{ij}^f,\ x_i = \sum_{k \in N_m}x_{ik}^d, \
\forall i \in [1,N_i],\quad &0 \le \sum_{j \in N_m}x_{ij}^f \le 1,\ 0 \le \sum_{k \in N_m}x_{ik}^d \le 1, \
\forall i \in [1,N_i],\ \forall j \in N_m,\quad &x_i \in {0, 1},\ x_{ij}^f \in {0, 1},\ x_{ij}^d \in {0, 1}.
\end{aligned}
$$
基于这些决策变量，可以得到指示变量的表达式
$$ \begin{aligned}
x_{link}(j,t) &= \left{ \begin{array}{lr} 1, & \quad t_i \le t < t_i + t_u(i,j) + t_{vm}(i,j) \ \bigcup \ t_i + \Delta t(i,j,k) - t_d(i,j) \le t < t_i + \Delta t(i,j,k) \& |{\exists i \in [1, N_i],\ \exists k \in N_m,\ x{ij}^f = 1,\ x_{ik}^d = 1},\ 0, & others.\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \end{array} \right. \
\
x_{vm}(k,t) &= \left{
\begin{array}{lr}
1, & \quad \quad \ \
t_i + t_u(i,j) \le t < t_i + t_u(i,j) + t_{vm}(i,j,k) + t_p(i,j)
|{\exists i \in [1, N_i],\ \exists j \in N_m,\ x{ij}^f = 1,\ x_{ik}^d = 1},\
0, & others.\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \ \ \
\end{array}
\right. \
\
x_p(j,t) &= \left{ \begin{array}{lr} \delta_t \cdot c^j, & t_i + t_u(i,j) + t_{vm}(i,j,k) \le\ t < t_i + t_u(i,j) + t_{vm}(i,j,k) \ + \& t_p(i,j) |{\exists i \in [1, N_i],\ \exists k \in N_m,\ x{ij}^f = 1,\ x_{ik}^d = 1}, \ w_i - \delta_t \cdot c^j \cdot [t_p(i,j)-1], & t_i + \Delta t(i,j,k) - t_d(i,j) -1 \le t < t_i + \Delta t(i,j,k) - t_d(i,j) \& |{\exists i \in [1, N_i],\ \exists k \in N_m,\ x{ij}^f = 1,\ x_{ik}^d = 1},\ 0, & others.\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\ \ \ \end{array} \right. \
\
x_s(j,t) &= \left{ \begin{array}{lr} s_i, & \ t_i + t_u(i,j) \ \le \ t \ < \ t_i + t_u(i,j) + t_{vm}(i,j,k) |{\exists i \in [1, N_i],\ \exists k \in N_m,\ x{ij}^f = 1,\ x_{ik}^d = 1},\ s_i + b\overline{loc}k^{vm_i}, & t_i + t_u(i,j) + t_{vm}(i,j,k) \ \le \ t \ < \ t_i+\ t_u(i,j)\ +\ t_{vm}(i,j,k)\ +\ t_p(i,j) \& |{\exists i \in [1, N_i],\ \exists k \in N_m,\ x{ij}^f = 1,\ x_{ik}^d = 1},\ e_i, & t_i + \Delta t(i,j,k) - t_d(i,j) \le t < t_i + \Delta t(i,j,k) |{\exists i \in [1, N_i],\ \exists k \in N_m,\ x{ij}^f = 1,\ x_{ik}^d = 1},\ 0, \quad \ \ & others.\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \ \ \ \end{array} \right. \
\end{aligned}
$$
虽然我们能够建模出在
由于欠缺具体的链路信息，$l$ 只能对目标函数值进行估测，比如使用端口信息估计链路信息
作为解决方案，$l$ 将只决定
- 边缘节点在参与其他业务的过程中已经知道与部分其他节点的链路情况。如以前合作的历史信息，或者从属一个运营商的节点自己有维护它们间的链路信息。
- 边缘节点可能有自己的偏好，但一定是理性的。理性意味着它们会坚持符合自己利益的策略，不会胡乱选择。
- 边缘节点和
$l$ 的利益不一定是相同的，哪怕$l$ 谨慎的设置了对它的定价以激励它朝着 Social Welfare 努力。- 边缘节点同时还在承接其他计算服务，它额外有一个选择
$\hat{t}_{vm}$ 较大的存储节点的倾向； - 边缘节点同时还在承接其他存储服务，它额外有一个选择
$\hat{t}_{vm}$ 较小的存储节点的倾向； - 边缘节点来自某个运营商，它会更倾向于选择相同运营商的节点。
- 边缘节点同时还在承接其他计算服务，它额外有一个选择
上述过程很明显是一局 stackelberg 游戏，因为它满足：
- 存在 leader 与 follower 两个决策主体，各自采用独立的策略，并遵守严格的先后顺序；
- 二者策略的目标函数都包括对方的决策变量，leader 会在考虑 follower 策略的同时采取最大化自身收益的策略；
- Follower 的策略是从有限行为集合中选择出单个行为的过程，必定存在让优化目标最大的最佳策略，同时理性的边缘节点会坚持以该最佳策略行动，因此 stackelberg-nash equilibria 存在。
按照 stackelberg 的求解思路，$l$ 会在已知
-
$f$ 的具体行为决策对$l$ 是未知的，$l$ 如何根据$f$ 的策略来解决它的最优化问题； -
$l$ 该通过什么方式来影响$f$ 的决策内容。
在一个服务小区内，leader 节点
我们将 leader 的决策设计为在线算法，即每次任务到来时立即处理该任务，而非收集一段时间
S. T. \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad K_{ij}& = \mu_f^j(B(i),INFO({x_{ik}^{CA}})),\
INFO({x_{ik}^{CA}})=\bigcup_{k \in N_m} &x_{ik}^{CA} \cdot { k,\ CSP(k),\ p_{vm}^k,\ min(bw^k,rd^k),\ lt^k },\
0 \le & \sum_{j \in N_m} x_{ij}^f \le 1,\ x_i = \sum_{j \in N_m}x_{ij}^f,\
\forall k \in N_m,\quad &x_{ik}^{CA} \cdot R(sid_i) \in {0} \cup VM^k,\
\forall j \in N_m,\quad
&x_{ij}^f \cdot [s_i + b\overline{loc}k^{R(sid_i)}] \le S^j,\
\forall a,b \in [1, N_i],\ \forall j \in N_m,\quad &x_{aj}^f \cdot t_a \ge x_{bj}^f \cdot [t_b + \Delta t(b, j, K_{ij}] \ \bigcup \ &x_{bj}^f \cdot t_b \ge x_{aj}^f \cdot [t_a + \Delta t(a, j, K_{ij}],\
\forall k \in N_m,\quad &x_i \in {0, 1},\ x_{ij}^f \in {0, 1},\ x_{ik}^{CA} \in {0, 1}. \end{aligned} $$
其中，决策变量
在这个模型中，$l$ 通过修改
-
${x_{ij}^f}$ ：在用户就近区域内，贪心地选出资源较为丰富的一个作为$f$ ，以提供合适的 QoS； -
${x_{ik}^{CA}}$ ：在所有包含$vm_i = R(sid_i)$ 的存储节点中选择出一部分备选者（candidates），以控制$f$ 的决策范围，避免其选择到一些明显偏离$l$ 目标的节点； -
${x_i}$ ：上述任何一个过程中发生错误，或者根据局部观测信息估计的目标函数值小于 0，都及时终止并抛弃任务。
在这个建模中，我们主要讨论 leader 与 follower 节点之间的交互及其对优化问题的影响。因此，我们将重点关注决定决策变量
在游戏中，$f$ 的具体策略将被视为
- 生成
$k$ 组随机的测试组合$ST$ ，其中的第$i$ 组表示为$st_i = {B_i, INFO_i}|_{i \in [1,k]} \in ST$ ，$INFO_i$ 是$m$ 个虚拟节点的信息，包括的内容如前面同名函数所示； - 当节点
$j$ 加入该雾计算系统时，$l$ 依次向其发起上述$k$ 组测试组合$ST$ ； - 节点
$j$ 对每个测试样例进行决策，并向$l$ 返还决策结果（所选的目标存储节点编号）； - 每获得一个测试样例的结果，$l$ 都直接向节点
$j$ 发起任务终止的指令，并接着进入下一个测试样例； -
$l$ 收集这$k$ 个结果，并将之按顺序排列为长为$k$ 的向量$TA_j$ 。
在该方案中，所有存储节点都是虚拟的，因此边缘节点只能用估计的链路信息进行决策，避免异构的网络环境对处在不同区域的同种节点的决策结果的影响。这些虚拟的节点具有随机的运营商所属和上传性能，只要测试数量
上述过程所得到的标签信息
在一次任务中，$l$ 首先计算决策变量
对于一个计算节点
S.T. \quad \quad \quad \quad \sum_{k \in N_m} &x_l^t \in {0, 1},\
\forall k \in N_m,&\quad x_k^t \in {0, 1}.
\end{aligned}
$$
其中，$Price(i,j,k)$ 表示任务
由于本文不讨论定价函数对
对于偏好函数，本文设计四种策略：
- 无偏好：$Bias_0(i,j,k) = 0$；
- 计算保守型：边缘节点同时还在承接其他计算服务，它希望降低单位时间内的计算资源占用，$Bias_1(i,j,k) = - \beta \cdot \frac{t_c}{\Delta \hat{t}(i,j,k)}$；
- 存储保守型：边缘节点同时还在承接其他存储服务，它希望减少存储资源的占用时间，$Bias_2(i,j,k) = - \beta \cdot \frac{t_u + \hat{t}_{vm}+t_d}{\Delta \hat{t}(i,j,k)}$；
- 同运营商优先型：边缘节点倾向于选择相同运营商的节点，$Bias_3(i,j,k) = \left{ \begin{aligned} &\beta \cdot \Mu, \quad j=k,\ &0, \quad \quad \ others. \end{aligned} \right.$
上述表达式中，$\beta$ 是偏好项的系数，$\Mu$ 是一个较大的正实数。实际上，考虑到
由于作为
在本文中，虽然我们并不关注
通过将
不同于
作为一个 Stackelberg 游戏中的 leader，按照传统的求解思路，$l$ 的决策就是在给定
-
任务丢弃
- 采用应收尽收的原则，不主动丢弃任务
- 只有在资源不满足时才舍弃任务
- 因为本文的核心是
$l$ 与$f$ 的交互，所以只要固定这部分策略，就不影响我们的实验
-
独占性
-
$f$ 被分配给某个任务后，直到任务结束为止，就不能再分配给其他任务 -
$d$ 不应该被独占，否则需要有比用户数量多的$d$
-
-
选择
$f$ 时只考虑没有接受任务的节点，并判断其存储空间是否合适 -
选择
$d$ 时不管它是否正在繁忙，一律认为可用- 实际上
$d$ 只消耗硬盘读取与网络上传资源，我们假设所有节点的总能力远大于分配给一个服务的 bw 和 rd 资源，这个设计就是可解释的 - 这种简化，避免了我们在某个 slot 里的决策顺序问题，必定会有不错的训练效果（在论文中是否需要提及？）
- 实际上
-
$l$ 的行为- 由于
$N_m$ 很大，实际上$l$ 并不会从中直接选择 candidates - 我们先进行一次预处理，筛选出符合要求的所有节点
- 再将从这些节点按照性价比（单价/min(bw, rd)）选出靠前的 n_ca 个节点，若未满则补空（价格 1e6，速度 0），按序排列
-
$l$ 的决策函数输出的是这 n_ca 个节点各自的概率分布，将它们分别手动高斯采样（为了有效反向传播，先采样出标准正态分布$N_0$ ，再$\mu + N_0*\sigma$ 得到目标），采样结果 sigmoid 归一化后超过 0.5 就是设为 candidate
- 由于
-
与论文不同的细节
- 仿真中不区分 sid 和 vm，二者一样
- 仿真中不区分节点的 bw 和 lt，认为一个节点对于 VM 上传和计算卸载分配的资源一样，同时由于 VM 上传不会被视为对带宽资源的占用，这种设计在理论上能够解释
-
节点自己就有 vm 的情况
- 不执行调度，计价不包括 block 缓存与存储节点的部分
- 环境太简单了，没有对资源使用量上限的设计
- 一个服务器同时只能服务一个用户，不太合理
- 只要将 slot 切得很小，同一时刻就不会有太多用户请求
- 任务大小等参数设置应该围绕 slot，让大部分任务在 2-3 个 slots 内解决
- 先做一个简单的跑着看看
- 一个服务器同时只能服务一个用户，不太合理
- 我们假设平均单个数据块大小为 10MB 左右，计算结果大小为 1KB。